[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 extra tests with chained subs.

[ConstraintElim] Add test case for #76713

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

[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] Remove dead compares after simplification.

Remove compares after replacing all uses. Cleaning dead compares can
enable additional simplifications when adjusting the position of the

[ConstraintElim] Remove dead compares after simplification.

Remove compares after replacing all uses. Cleaning dead compares can
enable additional simplifications when adjusting the position of the
pass slightly. In particular, it seems like the additional dead
instructions may prevent SimplifyCFG performing some folds.

Reviewed By: nikic

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

show more ...

[ConstraintElim] Add test subtracting SIGNED_MIN.

[ConstraintElimination] Use AddOverflow for offset summation.

Fixes an incorrect transformation due to values overflowing
https://alive2.llvm.org/ce/z/uizoea

[ConstraintElimination] Add test where offset additions overflow.

[ConstraintElimination] Add tests inspired by PR54224.

[ConstraintElimination] Fix sign of sub decomposition.

Update the decomposition code to make sure the right coefficient (-1) is
used for the second operand of the subtract.

Fixes PR53123.

[ConstraintElimination] Add test from PR53123.

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
I

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
In this patch focus has been put on test cases for ConstantMerge,
ConstraintElimination, CorrelatedValuePropagation, GlobalDCE,
GlobalOpt, SCCP, TailCallElim and PredicateInfo.

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

show more ...

[ConstraintElimination] Extend test coverage.

This patch adds a lot of additional tests, focusing on loops and GEP
arithmetic. Some of the tests expose existing problems, which will be
fixed soon.

[ConstraintElimination] Decompose add nuw/sub nuw.

Make use of the more flexible constraint handling added in
a8a79c90699a7ae9dee07daf7281cbbd592bf6ea to decompose add nuw/sub nuw.

[ConstraintElimination] Add add/sub/and/or test cases.

This adds a new set of tests for upcoming constraint elimination
changes.