[ConstraintElim] Decompose sext-like insts for signed predicates (#82344)

Alive2: https://alive2.llvm.org/ce/z/A8dtGp
Fixes #82271.

[ConstraintElim] Add facts for llvm.abs >= 0 (#79070)

Add facts for llvm.abs >= 0.

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

[ConstraintElim] Simplify `MinMaxIntrinsic` (#75306)

This patch replaces min/max intrinsic with one of its operands if
possible.
Alive2: https://alive2.llvm.org/ce/z/LoHfYf
Fixes #75155.

[ConstraintElimination] Use std::move in the constructor (NFC) (#79259)

Moving the contents of Coefficients saves 0.43% of heap allocations
during the compilation of a large preprocessed file, name

[ConstraintElimination] Use std::move in the constructor (NFC) (#79259)

Moving the contents of Coefficients saves 0.43% of heap allocations
during the compilation of a large preprocessed file, namely
X86ISelLowering.cpp, for the X86 target.

show more ...

[ConstraintElim] Make sure min/max intrinsic results are not poison.

The result of umin may be poison and in that case the added constraints
are not be valid in contexts where poison doesn't cause U

[ConstraintElim] Make sure min/max intrinsic results are not poison.

The result of umin may be poison and in that case the added constraints
are not be valid in contexts where poison doesn't cause UB. Only queue
facts for min/max intrinsics if the result is guaranteed to not be
poison.

This could be improved in the future, by only adding the fact when
solving conditions using the result value.

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

show more ...

[ConstraintElim] Remove unused checkCondition() parameters (NFC)

[ConstraintElim] Support signed induction variables (#77103)

When adding information for induction variables, add both unsigned and
signed constraints, with corresponding signed and unsigned
preco

[ConstraintElim] Support signed induction variables (#77103)

When adding information for induction variables, add both unsigned and
signed constraints, with corresponding signed and unsigned
preconditions.

I believe the logic here is equally valid for signed/unsigned, we just
need to add preconditions of the same type.

show more ...

[ConstraintElim] Decompose shl nsw for signed predicates (#76961)

shl nsw x, shift can be interpreted as mul nsw x, (1<<shift), except
when shift is bw-1 (https://alive2.llvm.org/ce/z/vDh2xT). Use

[ConstraintElim] Decompose shl nsw for signed predicates (#76961)

shl nsw x, shift can be interpreted as mul nsw x, (1<<shift), except
when shift is bw-1 (https://alive2.llvm.org/ce/z/vDh2xT). Use this when
decomposing shl. The equivalent decomposition for the unsigned case
already exists.

show more ...

[ConstraintElim] Add debug output for failed preconditions

Print debug output if a constraint does not get added due to a
failed precondition.

[ConstraintElim] Use SCEV to check for multiples (#76925)

When adding constraints for induction variables, if the step is not one,
we need to make sure that (end-start) is a multiple of step, other

[ConstraintElim] Use SCEV to check for multiples (#76925)

When adding constraints for induction variables, if the step is not one,
we need to make sure that (end-start) is a multiple of step, otherwise
we might step over the end value.

Currently this only supports one specific pattern for pointers, where
the end is a gep of the start with an appropriate offset.

Generalize this by using SCEV to check for multiples, which also makes
this work for integer IVs.

show more ...

[ConstraintElim] Use SmallDenseMap (NFC)

The number of variables in the constraint is usually very small.
Use SmallDenseMap to avoid allocations.

[ConstraintElim] Replace NUWSub decomp with recursive decomp of ops.

The current patterns for NUWSub decompositions do not handle negative
constants correctly at the moment (causing #76713).

Replac

[ConstraintElim] Replace NUWSub decomp with recursive decomp of ops.

The current patterns for NUWSub decompositions do not handle negative
constants correctly at the moment (causing #76713).

Replace the incorrect pattern by more general code that recursively
decomposes the operands and then combines the results. This is already
done in most other places that handle operators like add/mul.

This means we fall back to the general constant handling code (fixes the
mis-compile) while also being able to support reasoning about
decomposable expressions in the SUB operands.

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

show more ...

[ConstraintElim] Add facts implied by llvm.abs (#73189)

Add "abs(x) >=s x" fact.

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

Test plan: ninja check-all

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimizati

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimization in the
unsigned system, due to missing the information that all variables are
unsigned (non-negative).

Variables can be marked as non-negative by adding Var >= 0 for all
variables. This is done for arguments on ConstraintInfo construction and
after adding new variables. This handles cases like the ones outlined in
https://discourse.llvm.org/t/why-does-llvm-not-perform-range-analysis-on-integer-values/74341

The original example shared above is now handled without this change,
but adding another variable means that instcombine won't be able to
simplify examples like https://godbolt.org/z/hTnra7zdY

Adding the extra variables comes with a slight compile-time increase
https://llvm-compile-time-tracker.com/compare.php?from=7568b36a2bc1a1e496ec29246966ffdfc3a8b87f&to=641a47f0acce7755e340447386013a2e086f03d9&stat=instructions:u

stage1-O3 stage1-ReleaseThinLTO stage1-ReleaseLTO-g stage1-O0-g
+0.04% +0.07% +0.05% +0.02%
stage2-O3 stage2-O0-g stage2-clang
+0.05% +0.05% +0.05%

https://github.com/llvm/llvm-project/pull/76262

show more ...

[ConstraintElim] Extend AND implication logic to support OR as well. (#76044)

Extend the logic check if an operand of an AND is implied by the other
to also support OR. This is done by checking if

[ConstraintElim] Extend AND implication logic to support OR as well. (#76044)

Extend the logic check if an operand of an AND is implied by the other
to also support OR. This is done by checking if !op1 implies op2 or vice
versa.

show more ...

[ConstraintElim] Check if second op implies first for And. (#75750)

Generalize checkAndSecondOpImpliedByFirst to also check if the second
operand implies the first.

[Transforms] Fix a warning

This patch fixes:

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp:1112:13: error:
unused function 'dumpUnpackedICmp' [-Werror,-Wunused-function]

[ConstraintElim] Refactor `checkCondition`. NFC. (#75319)

This patch refactors `checkCondition` to handle min/max intrinsic calls
in #75306.

[NFC] Fix typo in ConstraintElimination assertion. (#75151)

unsinged => unsigned

Co-authored-by: Thomas Symalla <tsymalla@amd.com>

[Transforms] Remove unnecessary includes (NFC)

[ConstraintElim] Use disjoint flag for decomposition (#74478)

Use the or disjoint flag for decomposing or into add, which will handle
cases that haveNoCommonBitsSet() may not be able to reinfer (e.

[ConstraintElim] Use disjoint flag for decomposition (#74478)

Use the or disjoint flag for decomposing or into add, which will handle
cases that haveNoCommonBitsSet() may not be able to reinfer (e.g.
because they require context-sensitive facts, which the call here does
not use.)

show more ...

[ConstraintElim] Refactor GEP offset collection.

Move GEP offset collection to separate helper function and collect
variable and constant offsets in OffsetResult. For now, this only
supports 1 Varia

[ConstraintElim] Refactor GEP offset collection.

Move GEP offset collection to separate helper function and collect
variable and constant offsets in OffsetResult. For now, this only
supports 1 VariableOffset, but the new code structure can be more easily
extended to handle more offsets in the future.

The refactoring drops the check that the VariableOffset >= -1 * constant
offset. This is not needed to check whether the constraint is
monotonically increasing. The constant factors can be ignored, the
constraint will be monotonically increasing if all variables are
positive.

See https://alive2.llvm.org/ce/z/ah2uSQ,
https://alive2.llvm.org/ce/z/NCADNZ

show more ...

Recommit "[ConstraintElim] Treat ConstantPointerNull as constant offset 0."

This reverts commit 58286f9c665ad4aa748779d559f2f296de704094.

Now with the test correctly updated.

Original message:

Recommit "[ConstraintElim] Treat ConstantPointerNull as constant offset 0."

This reverts commit 58286f9c665ad4aa748779d559f2f296de704094.

Now with the test correctly updated.

Original message:
Treat ConstantPointerNull (null) as constant offset 0 in the constraint
instead of a variable. This slightly reduces the number of variables. I
was not able to find a test case where this actually caused any changes.

show more ...

Revert "[ConstraintElim] Treat ConstantPointerNull as constant offset 0."

This reverts commit 23628137ea9e7a2942d6a691ea74a7697564e65b.

Revert as this is causing some test failures.

[ConstraintElim] Treat ConstantPointerNull as constant offset 0.

Treat ConstantPointerNull (null) as constant offset 0 in the constraint
instead of a variable. This slightly reduces the number of va

[ConstraintElim] Treat ConstantPointerNull as constant offset 0.

Treat ConstantPointerNull (null) as constant offset 0 in the constraint
instead of a variable. This slightly reduces the number of variables. I
was not able to find a test case where this actually caused any changes.

show more ...