From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
To: linux-sparse@vger.kernel.org
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Subject: [SPARSE 1/4] canonicalize constant signed compares toward zero
Date: Sun, 18 Apr 2021 17:32:30 +0200 [thread overview]
Message-ID: <20210418153233.45234-2-luc.vanoostenryck@gmail.com> (raw)
In-Reply-To: <20210418153233.45234-1-luc.vanoostenryck@gmail.com>
Currently, signed compares against a constant are canonicalized
toward the smallest possible constant. So, the following
canonicalization are done:
x < 256 --> x <= 255
x < -2047 --> x <= -2048
This has two advantages:
1) it maximalizes the number of constants possible for a given bit size.
2) it allows to remove all < and all >=
But it has also a serious disadvantages: a simple comparison against
zero, like:
x >= 0
is canonicalized into:
x > -1
Which can be more costly for some architectures if translated as such ,
is also less readable than the version using 0 and is also sometimes
quite more complicated to match in some simplification patterns.
So, canonicalize it using 'towards 0' / using the smallest constant
in absolute value.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 34 +++++++++---
validation/optim/canonical-cmp-zero.c | 74 +++++++++++++++++++++++++++
2 files changed, 102 insertions(+), 6 deletions(-)
create mode 100644 validation/optim/canonical-cmp-zero.c
diff --git a/simplify.c b/simplify.c
index 9e3514d838a9..e0e4f9ebcba9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1178,38 +1178,52 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
switch (insn->opcode) {
case OP_SET_LT:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x < SMIN) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN)
return replace_binop_value(insn, OP_SET_EQ, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
break;
case OP_SET_LE:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x <= SMAX) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX)
return replace_binop_value(insn, OP_SET_NE, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_LT, (value + 1) & bits);
break;
case OP_SET_GE:
+ if (!value)
+ break;
if (value == sign_bit(size)) // (x >= SMIN) --> 1
return replace_with_pseudo(insn, value_pseudo(1));
if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX)
return replace_opcode(insn, OP_SET_EQ);
if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN)
return replace_binop_value(insn, OP_SET_NE, sign_bit(size));
- changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
+ if (!(value & sign_bit(size)))
+ changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
break;
case OP_SET_GT:
+ if (!value)
+ break;
if (value == sign_mask(size)) // (x > SMAX) --> 0
return replace_with_pseudo(insn, value_pseudo(0));
if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN)
return replace_opcode(insn, OP_SET_NE);
if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX)
return replace_binop_value(insn, OP_SET_EQ, sign_mask(size));
+ if (value & sign_bit(size))
+ changed |= replace_binop_value(insn, OP_SET_GE, (value + 1) & bits);
break;
case OP_SET_B:
@@ -1271,8 +1285,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if ((value & bits) != value)
return replace_with_value(insn, 1);
break;
- case OP_SET_LE:
+ case OP_SET_LE: case OP_SET_LT:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_LT)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1282,8 +1298,10 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if (value == 0)
return replace_opcode(insn, OP_SET_EQ);
break;
- case OP_SET_GT:
+ case OP_SET_GT: case OP_SET_GE:
value = sign_extend(value, def->size);
+ if (insn->opcode == OP_SET_GE)
+ value -= 1;
if (bits & sign_bit(def->size))
break;
if (value < 0)
@@ -1340,16 +1358,20 @@ static int simplify_compare_constant(struct instruction *insn, long long value)
if (bits >= value)
return replace_with_value(insn, 1);
break;
+ case OP_SET_LT:
+ value -= 1;
case OP_SET_LE:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 1);
}
break;
+ case OP_SET_GE:
+ value -= 1;
case OP_SET_GT:
- value = sign_extend(value, def->size);
if (bits & sign_bit(def->size)) {
+ value = sign_extend(value, def->size);
if (value >= -1)
return replace_with_value(insn, 0);
}
diff --git a/validation/optim/canonical-cmp-zero.c b/validation/optim/canonical-cmp-zero.c
new file mode 100644
index 000000000000..e01a00e637b6
--- /dev/null
+++ b/validation/optim/canonical-cmp-zero.c
@@ -0,0 +1,74 @@
+int f00(int x) { return x >= 0; }
+int f01(int x) { return x > -1; }
+int f02(int x) { return x < 1; }
+int f03(int x) { return x <= 0; }
+
+int f10(int x) { return x < 16; }
+int f11(int x) { return x <= 15; }
+
+int f20(int x) { return x > -9; }
+int f21(int x) { return x >= -8; }
+
+/*
+ * check-name: canonical-cmp-zero
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+f00:
+.L0:
+ <entry-point>
+ setge.32 %r2 <- %arg1, $0
+ ret.32 %r2
+
+
+f01:
+.L2:
+ <entry-point>
+ setge.32 %r5 <- %arg1, $0
+ ret.32 %r5
+
+
+f02:
+.L4:
+ <entry-point>
+ setle.32 %r8 <- %arg1, $0
+ ret.32 %r8
+
+
+f03:
+.L6:
+ <entry-point>
+ setle.32 %r11 <- %arg1, $0
+ ret.32 %r11
+
+
+f10:
+.L8:
+ <entry-point>
+ setle.32 %r14 <- %arg1, $15
+ ret.32 %r14
+
+
+f11:
+.L10:
+ <entry-point>
+ setle.32 %r17 <- %arg1, $15
+ ret.32 %r17
+
+
+f20:
+.L12:
+ <entry-point>
+ setge.32 %r20 <- %arg1, $0xfffffff8
+ ret.32 %r20
+
+
+f21:
+.L14:
+ <entry-point>
+ setge.32 %r23 <- %arg1, $0xfffffff8
+ ret.32 %r23
+
+
+ * check-output-end
+ */
--
2.31.1
next prev parent reply other threads:[~2021-04-18 15:32 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-04-18 15:32 [SPARSE 0/4] fix/improve canonicalization of signed compares Luc Van Oostenryck
2021-04-18 15:32 ` Luc Van Oostenryck [this message]
2021-04-18 15:32 ` [SPARSE 2/4] add testcases for AND(x > 0, x <= C) --> x u<= C Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 3/4] add helper is_positive() Luc Van Oostenryck
2021-04-18 15:32 ` [SPARSE 4/4] simplify AND(x >= 0, x < C) --> (unsigned)x < C Luc Van Oostenryck
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210418153233.45234-2-luc.vanoostenryck@gmail.com \
--to=luc.vanoostenryck@gmail.com \
--cc=linux-sparse@vger.kernel.org \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.