[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] Handle trivial (ICMP_ULE, 0, B) in doesHold.

D152730 may add trivial pre-conditions of the form (ICMP_ULE, 0, B),
which won't be handled automatically by the constraint system, beca

[ConstraintElim] Handle trivial (ICMP_ULE, 0, B) in doesHold.

D152730 may add trivial pre-conditions of the form (ICMP_ULE, 0, B),
which won't be handled automatically by the constraint system, because
we don't add Var >= 0 for all variables in the unsigned system.

Handling the trivial condition explicitly here avoids having the
increase the number of rows in the system per variable.

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

Depends on D152730.

Fixes #63125.

Reviewed By: nikic

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

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 add nsw tests with negative constant.

[ConstraintElim] Split up large gep-arithmetic.ll test.

This should help avoid getting a single test file too large with future
additions.