From: Bart Van Assche <bvanassche@acm.org>
To: linux-sparse@vger.kernel.org
Cc: Bart Van Assche <bvanassche@acm.org>
Subject: [PATCH 14/20] simplify: Avoid undefined shifts and signed overflow in simplification
Date: Mon, 19 Oct 2026 10:56:27 -0700 [thread overview]
Message-ID: <20261019175633.415493-15-bvanassche@acm.org> (raw)
In-Reply-To: <20261019175633.415493-1-bvanassche@acm.org>
Use unsigned long long masks and arithmetic with sign_bit() and
bits_mask() in eval_op(), simplify_mul_div(), simplify_constant_mask(),
simplify_constant_rightside(), simplify_constant_unop(), and
simplify_cast(), guard shift counts in eval_op() against 64-bit overflow,
and skip 64-bit mask simplifications in simplify_shift() when insn->size
exceeds 64 bits.
Eliminate undefined host C behavior from signed 64-bit overflow during
constant negation, addition, and subtraction, and from out-of-range
shifts when simplifying 0-bit, 32-bit, 64-bit, or 128-bit integer
instructions.
Fixes: 29946c577c13 ("Do first-approximation constant binop simplification.")
Fixes: 08778dab2167 ("Simplify constant unops")
Fixes: 62cab21fe13b ("add support for __int128")
Fixes: 0b9963941148 ("simplify 'x | ~0' to '~0'")
Fixes: 97e6515a7944 ("unop: add helper eval_unop()")
Fixes: f1252a541ac8 ("simplify '(x * -1)' to '-x'")
Fixes: c68bfab0e487 ("simplify ((x & M) >> S) when (M >> S) == 0")
Fixes: cb4bed63e19e ("simplify ((x & M) << S) when (M << S) == 0")
Fixes: 3a729e93ba9f ("simplify ((x >> S) << S)")
Fixes: 1ed0dfb47362 ("cast: simplify TRUNC + ZEXT to AND")
Fixes: 5da4e09b4701 ("cast: simplify AND(ZEXT(x,M),N)")
Fixes: 780d796a478f ("cast: simplify [ZS]EXT(AND(x,M),N)")
Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
simplify.c | 53 ++++++++++++++++++++++++++---------------------------
1 file changed, 26 insertions(+), 27 deletions(-)
diff --git a/simplify.c b/simplify.c
index 68c5f9c74021..f20b6f1a9881 100644
--- a/simplify.c
+++ b/simplify.c
@@ -632,10 +632,11 @@ static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
long long left = src1->value;
long long right = src2->value;
unsigned long long ul, ur;
- long long res, mask, bits;
+ long long res;
+ unsigned long long mask, bits;
- mask = 1ULL << (size-1);
- bits = mask | (mask-1);
+ mask = sign_bit(size);
+ bits = bits_mask(size);
if (left & mask)
left |= ~bits;
@@ -646,17 +647,17 @@ static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
switch (op) {
case OP_NEG:
- res = -left;
+ res = -ul;
break;
case OP_NOT:
res = ~ul;
break;
case OP_ADD:
- res = left + right;
+ res = ul + ur;
break;
case OP_SUB:
- res = left - right;
+ res = ul - ur;
break;
case OP_MUL:
res = ul * ur;
@@ -688,17 +689,17 @@ static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
case OP_SHL:
if (ur >= size)
goto undef;
- res = left << right;
+ res = ur < 64 ? ul << ur : 0;
break;
case OP_LSR:
if (ur >= size)
goto undef;
- res = ul >> ur;
+ res = ur < 64 ? ul >> ur : 0;
break;
case OP_ASR:
if (ur >= size)
goto undef;
- res = left >> right;
+ res = left >> (ur < 63 ? ur : 63);
break;
/* Logical */
case OP_AND:
@@ -967,7 +968,7 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v
case OP_AND:
// replace (A & M) >> S
// by (A >> S) & (M >> S)
- if (!constant(def->src2))
+ if (!constant(def->src2) || insn->size > 64)
break;
mask = bits_mask(insn->size - value) << value;
omask = def->src2->value;
@@ -991,7 +992,7 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v
case OP_SHL:
// replace ((x << S) >> S)
// by (x & (-1 >> S))
- if (def->src2 != insn->src2)
+ if (def->src2 != insn->src2 || insn->size > 64)
break;
mask = bits_mask(insn->size - value);
goto replace_mask;
@@ -1003,7 +1004,7 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v
switch(DEF_OPCODE(def, pseudo)) {
case OP_AND:
// simplify (A & M) << S
- if (!constant(def->src2))
+ if (!constant(def->src2) || insn->size > 64)
break;
mask = bits_mask(insn->size) >> value;
omask = def->src2->value;
@@ -1017,7 +1018,7 @@ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long v
case OP_LSR:
// replace ((x >> S) << S)
// by (x & (-1 << S))
- if (def->src2 != insn->src2)
+ if (def->src2 != insn->src2 || insn->size > 64)
break;
mask = bits_mask(insn->size - value) << value;
goto replace_mask;
@@ -1056,8 +1057,8 @@ replace_mask:
static int simplify_mul_div(struct instruction *insn, long long value)
{
- unsigned long long sbit = 1ULL << (insn->size - 1);
- unsigned long long bits = sbit | (sbit - 1);
+ unsigned long long sbit = sign_bit(insn->size);
+ unsigned long long bits = bits_mask(insn->size);
if (value == 1)
return replace_with_pseudo(insn, insn->src1);
@@ -1523,7 +1524,7 @@ static int simplify_constant_mask(struct instruction *insn, unsigned long long m
osize = def->orig_type->bit_size;
/* fall through */
oldsize:
- omask = (1ULL << osize) - 1;
+ omask = bits_mask(osize);
nmask = mask & omask;
if (nmask == omask)
// the AND mask is redundant
@@ -1559,8 +1560,7 @@ static int simplify_const_rightadd(struct instruction *def, struct instruction *
static int simplify_constant_rightside(struct instruction *insn)
{
long long value = insn->src2->value;
- long long sbit = 1ULL << (insn->size - 1);
- long long bits = sbit | (sbit - 1);
+ unsigned long long bits = bits_mask(insn->size);
int changed = 0;
switch (insn->opcode) {
@@ -2138,19 +2138,19 @@ static int simplify_xor(struct instruction *insn)
static int simplify_constant_unop(struct instruction *insn)
{
long long val = insn->src1->value;
- long long res, mask;
+ unsigned long long res, mask;
switch (insn->opcode) {
case OP_NOT:
res = ~val;
break;
case OP_NEG:
- res = -val;
+ res = -(unsigned long long)val;
break;
case OP_SEXT:
- mask = 1ULL << (insn->orig_type->bit_size-1);
+ mask = sign_bit(insn->orig_type->bit_size);
if (val & mask)
- val |= ~(mask | (mask-1));
+ val |= ~bits_mask(insn->orig_type->bit_size);
/* fall through */
case OP_ZEXT:
case OP_TRUNC:
@@ -2159,8 +2159,7 @@ static int simplify_constant_unop(struct instruction *insn)
default:
return 0;
}
- mask = 1ULL << (insn->size-1);
- res &= mask | (mask-1);
+ res &= bits_mask(insn->size);
return replace_with_value(insn, res);
}
@@ -2329,12 +2328,12 @@ static int simplify_cast(struct instruction *insn)
insn->opcode = OP_AND;
mask = val->value;
- mask &= (1ULL << size) - 1;
+ mask &= bits_mask(size);
insn->src2 = value_pseudo(mask);
return REPEAT_CSE;
case OP_SEXT:
- if (val->value & (1 << (def->size - 1)))
+ if (val->value & sign_bit(def->size))
break;
// OK, sign bit is 0
case OP_ZEXT:
@@ -2426,7 +2425,7 @@ static int simplify_cast(struct instruction *insn)
if (size != def->orig_type->bit_size)
break;
insn->opcode = OP_AND;
- insn->src2 = value_pseudo((1ULL << def->size) - 1);
+ insn->src2 = value_pseudo(bits_mask(def->size));
return replace_pseudo(insn, &insn->src1, def->src);
}
break;
next prev parent reply other threads:[~2026-10-19 17:56 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-19 17:56 [PATCH 00/20] Sanitizer fixes, LLVM updates, and CI workflow Bart Van Assche
2026-10-19 17:56 ` [PATCH 01/20] doc: Update maintainer and mirror information Bart Van Assche
2026-10-19 17:56 ` [PATCH 02/20] ptrlist: Guard against null list in ptrlist operations Bart Van Assche
2026-10-19 17:56 ` [PATCH 03/20] bits: Guard against out-of-bounds bit shifts in bitmask helpers Bart Van Assche
2026-10-19 17:56 ` [PATCH 04/20] storage: Free hash table entries when freeing storage Bart Van Assche
2026-10-19 17:56 ` [PATCH 05/20] builtin: Bound argument array iteration in declare_builtin() Bart Van Assche
2026-10-19 17:56 ` [PATCH 06/20] c2xml: Use an unsigned shift in examine_modifiers() Bart Van Assche
2026-10-19 17:56 ` [PATCH 07/20] parse: Avoid incrementing rank on invalid long real specifiers Bart Van Assche
2026-10-19 17:56 ` [PATCH 08/20] pre-process: Avoid zero-length VLAs for parameterless macros Bart Van Assche
2026-10-19 17:56 ` [PATCH 09/20] pre-process: Avoid reading token->string on non-string tokens Bart Van Assche
2026-10-19 17:56 ` [PATCH 10/20] target: Avoid signed overflow in bit and byte conversion helpers Bart Van Assche
2026-10-19 17:56 ` [PATCH 11/20] evaluate: Use bitmask helpers in evaluate_ptr_add() Bart Van Assche
2026-10-19 17:56 ` [PATCH 12/20] linearize: Use bits_mask() in linearize_bitfield_insert() Bart Van Assche
2026-10-19 17:56 ` [PATCH 13/20] expand: Avoid undefined shifts and signed overflow in constant folding Bart Van Assche
2026-10-19 17:56 ` Bart Van Assche [this message]
2026-10-19 17:56 ` [PATCH 15/20] sparsec: Emit object files directly with llc -filetype=obj Bart Van Assche
2026-10-19 17:56 ` [PATCH 16/20] llvm: Stop calling LLVMConstGEP2() for string literals Bart Van Assche
2026-10-19 17:56 ` [PATCH 17/20] llvm: Free leaked allocations and LLVM objects Bart Van Assche
2026-10-19 17:56 ` [PATCH 18/20] parse: Accept an empty attribute argument list Bart Van Assche
2026-10-19 17:56 ` [PATCH 19/20] llvm: Use explicit LLVMContextRef instead of global context Bart Van Assche
2026-10-19 17:56 ` [PATCH 20/20] ci: Add a GitHub Actions workflow and CI scripts Bart Van Assche
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=20261019175633.415493-15-bvanassche@acm.org \
--to=bvanassche@acm.org \
--cc=linux-sparse@vger.kernel.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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox