[InstCombine] Refactor foldICmpMulConstant

This is a follow-up to 2ebfda2417
(replace "if" with "else if" since the cases nuw/nsw
were meant to be handled separately).

Test plan:
1/ ninja check-llv

[InstCombine] Refactor foldICmpMulConstant

This is a follow-up to 2ebfda2417
(replace "if" with "else if" since the cases nuw/nsw
were meant to be handled separately).

Test plan:
1/ ninja check-llvm check-clang check-lld
2/ Bootstrapped LLVM/Clang pass tests

(cherry picked from commit d982f1e0c69f3447c4520ae4c010520f62ed1174)

show more ...

[InstCombine] Improve folding of mul + icmp

This diff adds folds for patterns like X * A < B
where A, B are constants and "mul" has either "nsw" or "nuw".
(to address https://github.com/llvm/llvm-pr

[InstCombine] Improve folding of mul + icmp

This diff adds folds for patterns like X * A < B
where A, B are constants and "mul" has either "nsw" or "nuw".
(to address https://github.com/llvm/llvm-project/issues/56563).

Test plan:
1/ ninja check-llvm check-clang
2/ Bootstrapped LLVM/Clang pass tests

Differential revision: https://reviews.llvm.org/D130039

show more ...

[InstCombine] remove useless ‘InstCombiner::’. nfc

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D130220

[InstCombine] (ShiftValC >> Y) >s -1/<s 0 --> Y != 0/==0

We can do folds (ShiftValC >> Y) >s -1 --> Y != 0 and
(ShiftValC >> Y) <s 0 --> Y == 0, with ShiftValC < 0.

Alive2: https://alive2.llvm.org/

[InstCombine] (ShiftValC >> Y) >s -1/<s 0 --> Y != 0/==0

We can do folds (ShiftValC >> Y) >s -1 --> Y != 0 and
(ShiftValC >> Y) <s 0 --> Y == 0, with ShiftValC < 0.

Alive2: https://alive2.llvm.org/ce/z/-PRHfD

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D129726

show more ...

[IR] Remove Constant::canTrap() (NFC)

As integer div/rem constant expressions are no longer supported,
constants can no longer trap and are always safe to speculate.
Remove the Constant::canTrap() m

[IR] Remove Constant::canTrap() (NFC)

As integer div/rem constant expressions are no longer supported,
constants can no longer trap and are always safe to speculate.
Remove the Constant::canTrap() method and its usages.

show more ...

[InstCombine] improve fold for icmp_eq_and to icmp_ult

In D95959, the improve analysis for "C >> X" broken the fold
((%x & C) == 0) --> %x u< (-C) iff (-C) is power of two.

It simplifies C, but fai

[InstCombine] improve fold for icmp_eq_and to icmp_ult

In D95959, the improve analysis for "C >> X" broken the fold
((%x & C) == 0) --> %x u< (-C) iff (-C) is power of two.

It simplifies C, but fails to satisfy the fold condition.
This patch try to restore C before the fold.

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D128790

show more ...

[InstCombine] [NFC] use C.isNegatedPowerOf2() instead of (~C + 1).isPowerOf2()

Reviewed By: RKSimon

Differential Revision: https://reviews.llvm.org/D129103

[InstCombine] add code comment for icmp transform; NFC

This was accidentally left out of cc88445a9106

[InstCombine] Fix a Wparentheses warning in an assert. NFC

[InstCombine] canonicalize 'icmp (trunc X), C' to 'icmp (X & Mask), C'

I looked at canonicalizing in the other direction, but that causes
many potential regressions and infinite loops because we alr

[InstCombine] canonicalize 'icmp (trunc X), C' to 'icmp (X & Mask), C'

I looked at canonicalizing in the other direction, but that causes
many potential regressions and infinite loops because we already
(possibly wrongly) canonicalize "trunc X to i1" into an and+icmp.

This has a data layout restriction to avoid creating illegal
mask instructions, but we could remove that if we can show
that the backend can undo this when needed.

The motivating example from issue #56119 is modeled by the
PhaseOrdering test.

show more ...

[InstCombine] fix overzealous assert in icmp-shr fold

The assert was added with 0399473de886595d and is correct for that
pattern, but it is off-by-1 with the enhancement in d4f39d833332.

The transf

[InstCombine] fix overzealous assert in icmp-shr fold

The assert was added with 0399473de886595d and is correct for that
pattern, but it is off-by-1 with the enhancement in d4f39d833332.

The transforms are still correct with the new pre-condition:
https://alive2.llvm.org/ce/z/6_6ghm
https://alive2.llvm.org/ce/z/_GTBUt

And as shown in the new test, the transform is expected with
'ult' - in that case, the icmp reduces to test if the shift
amount is 0.

show more ...

[InstCombine] add fold for (ShiftC >> X) >u C

This is the 'ugt' sibling to:
0399473de886595d

Decrement the input compare constant (and implicitly
decrement the new compare constant):
https://alive2

[InstCombine] add fold for (ShiftC >> X) >u C

This is the 'ugt' sibling to:
0399473de886595d

Decrement the input compare constant (and implicitly
decrement the new compare constant):
https://alive2.llvm.org/ce/z/iELmct

show more ...

[IR] Remove support for extractvalue constant expression

This removes the extractvalue constant expression, as part of
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.
extrac

[IR] Remove support for extractvalue constant expression

This removes the extractvalue constant expression, as part of
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.
extractvalue is already not supported in bitcode, so we do not need
to worry about bitcode auto-upgrade.

Uses of ConstantExpr::getExtractValue() should be replaced with
IRBuilder::CreateExtractValue() (if the fact that the result is
constant is not important) or ConstantFoldExtractValueInstruction()
(if it is). Though for this particular case, it is also possible
and usually preferable to use getAggregateElement() instead.

The C API function LLVMConstExtractValue() is removed, as the
underlying constant expression no longer exists. Instead,
LLVMBuildExtractValue() should be used (which will constant fold
or create an instruction). Depending on the use-case,
LLVMGetAggregateElement() may also be used instead.

Differential Revision: https://reviews.llvm.org/D125795

show more ...

[InstCombine] Optimise shift+and+boolean conversion pattern to simple comparison

if (`C1` is pow2) & (`(C2 & ~(C1-1)) + C1)` is pow2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1));
htt

[InstCombine] Optimise shift+and+boolean conversion pattern to simple comparison

if (`C1` is pow2) & (`(C2 & ~(C1-1)) + C1)` is pow2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1));
https://alive2.llvm.org/ce/z/EJAl1R
((C1 << X) & C2) != 0 -> X < (Log2(C2+C1) - Log2(C1));
https://alive2.llvm.org/ce/z/3bVRVz

And remove dead code.

Fix: https://github.com/llvm/llvm-project/issues/56124

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D126591

show more ...

[InstCombine] add vector support for (A >> C) == (B >> C) --> (A^B) u< (1 << C)

Reviewed By: spatel, RKSimon

Differential Revision: https://reviews.llvm.org/D127398

[InstCombine] add fold for (ShiftC >> X) <u C

https://alive2.llvm.org/ce/z/RcdzM-

This fixes a regression noted in issue #56046.

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

Differential Revision: https://reviews.llvm.org/D126889

show more ...

[InstCombine] improve fold for icmp-ugt-ashr

Existing condition for
fold icmp ugt (ashr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
missed some boundary. It cause this fold don't work for

[InstCombine] improve fold for icmp-ugt-ashr

Existing condition for
fold icmp ugt (ashr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
missed some boundary. It cause this fold don't work for some cases, and the
reason is due to signed number overflow.

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D127188

show more ...

[InstCombine] fold icmp of sext bool based on limited range

X <=u (sext i1 Y) --> (X == 0) | Y

https://alive2.llvm.org/ce/z/W_tZzo

This is the conjugate/sibling pattern suggested with D126171
for

[InstCombine] fold icmp of sext bool based on limited range

X <=u (sext i1 Y) --> (X == 0) | Y

https://alive2.llvm.org/ce/z/W_tZzo

This is the conjugate/sibling pattern suggested with D126171
for a sign-extended bool value.

show more ...

[InstCombine] fold icmp equality with sdiv and SMIN

This extends the fold from D126410 / 3952c905ef08
to allow for the only case where it works with signed
division:
https://alive2.llvm.org/ce/z/k7_

[InstCombine] fold icmp equality with sdiv and SMIN

This extends the fold from D126410 / 3952c905ef08
to allow for the only case where it works with signed
division:
https://alive2.llvm.org/ce/z/k7_ypu

(X s/ Y) == SMIN --> (X == SMIN) && (Y == 1)
(X s/ Y) != SMIN --> (X != SMIN) || (Y != 1)

This is another improvement based on #55695.

show more ...

[InstCombine] reduce code duplication in icmp+div folds; NFC

[InstCombine] fold icmp equality with udiv and large constant

With large compare constant:
(X u/ Y) == C --> (X == C) && (Y == 1)
(X u/ Y) != C --> (X != C) || (Y != 1)

https://alive2.llvm.org/ce/z

[InstCombine] fold icmp equality with udiv and large constant

With large compare constant:
(X u/ Y) == C --> (X == C) && (Y == 1)
(X u/ Y) != C --> (X != C) || (Y != 1)

https://alive2.llvm.org/ce/z/EhKwh6

There are various potential missing icmp (div) transforms shown here:
https://github.com/llvm/llvm-project/issues/55695

This is a generalization for part of the udiv + equality.
I didn't check in detail, but some of those may only make sense as
codegen transforms.

This results in one extra instruction in IR, but it is better for
analysis, and looks much better in codegen on all targets that I tried.

Differential Revision: https://reviews.llvm.org/D126410

show more ...

[InstCombine] fold icmp of zext bool based on limited range

X <u (zext i1 Y) --> (X == 0) && Y

https://alive2.llvm.org/ce/z/avQDRY

This is a generalization of 4069cccf3b4ff4a based on the post-com

[InstCombine] fold icmp of zext bool based on limited range

X <u (zext i1 Y) --> (X == 0) && Y

https://alive2.llvm.org/ce/z/avQDRY

This is a generalization of 4069cccf3b4ff4a based on the post-commit suggestion.
This also adds the i1 type check and tests that were missing from the earlier
attempt; that commit caused several bot fails and was reverted.

Differential Revision: https://reviews.llvm.org/D126171

show more ...

Revert "[InstCombine] fold icmp with sub and bool"

This reverts commit 4069cccf3b4ff4afb743d3d371ead9e2d5491e3a.
This causes bot failures, and there's a possibly a better way to get this and other p

Revert "[InstCombine] fold icmp with sub and bool"

This reverts commit 4069cccf3b4ff4afb743d3d371ead9e2d5491e3a.
This causes bot failures, and there's a possibly a better way to get this and other patterns.

show more ...

[InstCombine] fold icmp with sub and bool

This is the specific pattern seen in #53432, but it can be extended
in multiple ways:
1. The 'zext' could be an 'and'
2. The 'sub' could be some other binop

[InstCombine] fold icmp with sub and bool

This is the specific pattern seen in #53432, but it can be extended
in multiple ways:
1. The 'zext' could be an 'and'
2. The 'sub' could be some other binop with a similar ==0 property (udiv).

There might be some way to generalize using knownbits, but that
would require checking that the 'bool' value is created with
some instruction that can be replaced with new icmp+logic.

https://alive2.llvm.org/ce/z/-KCfpa

show more ...