[InstCombine] fold unsigned predicates on srem result (#122520)

This allows optimization of more signed floor implementations when the
divisor is a known power of two to an arithmetic shift.

Pro

[InstCombine] fold unsigned predicates on srem result (#122520)

This allows optimization of more signed floor implementations when the
divisor is a known power of two to an arithmetic shift.

Proof for the implemented optimizations:
https://alive2.llvm.org/ce/z/j6C-Nz

Proof for the test cases:
https://alive2.llvm.org/ce/z/M_PBjw

---------

Co-authored-by: Jacob Young <jacobly0@users.noreply.github.com>

show more ...

[ValueTracking] Move `getFlippedStrictnessPredicateAndConstant` into ValueTracking. NFC. (#122064)

Needed by https://github.com/llvm/llvm-project/pull/121958.

[InstCombine] Compute result directly on APInts

If the bitwidth is 2 and we add two 1s, the result may overflow.
This is fine in terms of correctness, but triggers the APInt ctor
assertion. Fix this

[InstCombine] Compute result directly on APInts

If the bitwidth is 2 and we add two 1s, the result may overflow.
This is fine in terms of correctness, but triggers the APInt ctor
assertion. Fix this by performing the calculation directly on APInts.

Fixes the issue reported in:
https://github.com/llvm/llvm-project/pull/114539#issuecomment-2574845003

show more ...

[InstCombine] Check no wrap flags before folding icmp of GEPs with same indices (#121628)

Alive2: https://alive2.llvm.org/ce/z/Dr3Sbe
Closes https://github.com/llvm/llvm-project/issues/121581.

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key p

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key pieces of infrastructure that must be updated to match a CmpInst
respecting samesign information. Implement this change to Cmp-matchers.

This is a preparatory step in migrating the codebase over to
CmpPredicate. Since we no functional changes are desired at this stage,
we have chosen not to migrate CmpPredicate::operator==(CmpPredicate)
calls to use CmpPredicate::getMatching(), as that would have visible
impact on tests that are not yet written: instead, we call
CmpPredicate::operator==(Predicate), preserving the old behavior, while
also inserting a few FIXME comments for follow-ups.

show more ...

[InstCombine] Fix type mismatch in `foldICmpBinOpEqualityWithConstant` (#119068)

Closes https://github.com/llvm/llvm-project/issues/119063.

Reapply [InstCombine] Support gep nuw in icmp folds (#118472)

The profile runtime test failure this caused has been addressed in:
https://github.com/llvm/llvm-project/pull/118782

-----

Unsigned ic

Reapply [InstCombine] Support gep nuw in icmp folds (#118472)

The profile runtime test failure this caused has been addressed in:
https://github.com/llvm/llvm-project/pull/118782

-----

Unsigned icmp of gep nuw folds to unsigned icmp of offsets. Unsigned
icmp of gep nusw nuw folds to unsigned samesign icmp of offsets.

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

show more ...

[InstCombine] Fold `icmp spred (X *nsw Z), (Y *nsw Z) -> icmp pred Z, 0` if `scmp(X, Y)` is known (#118726)

```
icmp spred (X *nsw Z), (Y *nsw Z) -> icmp swap(spred) Z, 0 if X s< Y
icmp spred (X *

[InstCombine] Fold `icmp spred (X *nsw Z), (Y *nsw Z) -> icmp pred Z, 0` if `scmp(X, Y)` is known (#118726)

```
icmp spred (X *nsw Z), (Y *nsw Z) -> icmp swap(spred) Z, 0 if X s< Y
icmp spred (X *nsw Z), (Y *nsw Z) -> icmp spred Z, 0 if X s> Y
```
Alive2: https://alive2.llvm.org/ce/z/F2D0GE

show more ...

Revert "[InstCombine] Support gep nuw in icmp folds" (#118698)

Reverts llvm/llvm-project#118472

Breaks profile tests on i386
https://lab.llvm.org/buildbot/#/builders/66/builds/7009

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign in

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign information,
in order to ease extending large portions of the codebase that take a
CmpInst::Predicate to respect the samesign flag.

We have chosen to demonstrate the utility of this new abstraction by
migrating parts of ValueTracking, InstructionSimplify, and InstCombine
from CmpInst::Predicate to llvm::CmpPredicate. There should be no
functional changes, as we don't perform any extra optimizations with
samesign in this patch, or use CmpPredicate::getMatching.

The design approach taken by this patch allows for unaudited callers of
APIs that take a llvm::CmpPredicate to silently drop the samesign
information; it does not pose a correctness issue, and allows us to
migrate the codebase piece-wise.

show more ...

[InstCombine] Support gep nuw in icmp folds (#118472)

Unsigned icmp of gep nuw folds to unsigned icmp of offsets. Unsigned
icmp of gep nusw nuw folds to unsigned samesign icmp of offsets.

Proofs

[InstCombine] Support gep nuw in icmp folds (#118472)

Unsigned icmp of gep nuw folds to unsigned icmp of offsets. Unsigned
icmp of gep nusw nuw folds to unsigned samesign icmp of offsets.

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

show more ...

[InstCombine] Support nusw in icmp of two geps with same base

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

[InstCombine] Support nusw in icmp of gep with base

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

[InstCombine] Fold `icmp spred (and X, highmask), C1` into `icmp spred X, C2` (#118197)

Alive2: https://alive2.llvm.org/ce/z/Ffg64g
Closes https://github.com/llvm/llvm-project/issues/104772.

[PatternMatch] Introduce m_c_Select (#114328)

This matches m_Select(m_Value(), L, R) or m_Select(m_Value(), R, L).

[InstCombine] Remove unused variable in InstCombineCompares.cpp (NFC)

/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp:3190:14:
error: unused variable 'CmpBW' [-Werror,-Wunused

[InstCombine] Remove unused variable in InstCombineCompares.cpp (NFC)

/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp:3190:14:
error: unused variable 'CmpBW' [-Werror,-Wunused-variable]
unsigned CmpBW = Ty->getScalarSizeInBits();
^
1 error generated.

show more ...

[InstCombine] Fold zext(X) + C2 pred C -> X + C3 pred C4 (#110511)

Motivating case from
https://github.com/torvalds/linux/blob/9852d85ec9d492ebef56dc5f229416c925758edc/drivers/gpu/drm/drm_edid.c#L5

[InstCombine] Fold zext(X) + C2 pred C -> X + C3 pred C4 (#110511)

Motivating case from
https://github.com/torvalds/linux/blob/9852d85ec9d492ebef56dc5f229416c925758edc/drivers/gpu/drm/drm_edid.c#L5238-L5240:
```
define i1 @src(i8 noundef %v13) {
entry:
%conv1 = zext i8 %v13 to i32
%add = add nsw i32 %conv1, -4
%cmp = icmp ult i32 %add, 3
%cmp4 = icmp slt i8 %v13, 4
%cond = select i1 %cmp4, i1 true, i1 %cmp
ret i1 %cond
}

define i1 @tgt(i8 noundef %v13) {
entry:
%cmp4 = icmp slt i8 %v13, 7
ret i1 %cmp4
}
```

show more ...

[InstCombine] Use KnownBits predicate helpers (#115874)

Inside foldICmpUsingKnownBits(), instead of rolling our own logic based
on min/max values, make use of ICmpInst::compare() working on KnownBi

[InstCombine] Use KnownBits predicate helpers (#115874)

Inside foldICmpUsingKnownBits(), instead of rolling our own logic based
on min/max values, make use of ICmpInst::compare() working on KnownBits.
This gives better results for the equality predicates. In practice, the
improvement is only for pointers, because isKnownNonEqual() handles the
non-pointer case.

I've adjusted some tests to prevent the new fold from triggering, to
retain their original intent of testing constant expressions.

show more ...

[InstCombine] Fold (sext(a) & c1) == c2 to (a & c3) == trunc(c2) (#112646)

Fixes https://github.com/llvm/llvm-project/issues/85830.

Updated Alive proof: https://alive2.llvm.org/ce/z/KnvoP5

[InstCombine] Remove unused includes (NFC) (#114709)

Identified with misc-include-cleaner.

[InstCombine] Optimize away certain additions using modular arithmetic

We can turn:
```
%add = add i8 %arg, C1
%and = and i8 %add, C2
%cmp = icmp eq i1 %and, C3
```

into:
```
%and = and i8

[InstCombine] Optimize away certain additions using modular arithmetic

We can turn:
```
%add = add i8 %arg, C1
%and = and i8 %add, C2
%cmp = icmp eq i1 %and, C3
```

into:
```
%and = and i8 %arg, C2
%cmp = icmp eq i1 %and, (C3 - C1) & C2
```

This is only worth doing if the sequence is the sole user of the addition
operation.

show more ...

Reapply "[InstCombine] Folding `(icmp eq/ne (and X, -P2), INT_MIN)`" (#111236)

The underlying issue with msan was fixed by #113200

[InstCombine] Simplify code with SmallMapVector::operator[] (NFC) (#113022)

[LLVM] Make more use of IRBuilder::CreateIntrinsic. NFC. (#112706)

Convert many instances of:
Fn = Intrinsic::getOrInsertDeclaration(...);
CreateCall(Fn, ...)
to the equivalent CreateIntrinsi

[LLVM] Make more use of IRBuilder::CreateIntrinsic. NFC. (#112706)

Convert many instances of:
Fn = Intrinsic::getOrInsertDeclaration(...);
CreateCall(Fn, ...)
to the equivalent CreateIntrinsic call.

show more ...

[InstCombine] Set `samesign` when converting signed predicates into unsigned (#112642)

Alive2: https://alive2.llvm.org/ce/z/6cqdt-