[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] Don't decompose values wider than 64 bits (#68803)

Our coefficients are 64-bits, so adding/multiplying them can wrap in
64-bits even if there would be no wrapping the full bit widt

[ConstraintElim] Don't decompose values wider than 64 bits (#68803)

Our coefficients are 64-bits, so adding/multiplying them can wrap in
64-bits even if there would be no wrapping the full bit width.

The alternative would be to check for overflows during all adds/muls in
decomposition. I assume that we don't particularly care about handling
wide integers here, so I've opted to bail out.

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

show more ...

[ConstraintElim] Add test for #68751 (NFC)

[Tests][ConstraintElim] autogen newly-added case in large-constant-ints.ll (NFC)

I forgot to do this in 66ec5df3a7f33366455d50769e4e878544becea6 / https://reviews.llvm.org/D158810.

Since this is te

[Tests][ConstraintElim] autogen newly-added case in large-constant-ints.ll (NFC)

I forgot to do this in 66ec5df3a7f33366455d50769e4e878544becea6 / https://reviews.llvm.org/D158810.

Since this is testing for an assertion failure, the test checks don't matter, but we might as well avoid unnecessary churn the next time someone modifies this test.

show more ...

[ConstraintElim] fix crash with large constants in mul nsw

Another case of https://github.com/llvm/llvm-project/issues/55085.

The added test would trip an assertion due to calling `getSExtValue()`

[ConstraintElim] fix crash with large constants in mul nsw

Another case of https://github.com/llvm/llvm-project/issues/55085.

The added test would trip an assertion due to calling `getSExtValue()` on a value that doesn't fit in int64_t.

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

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 ...

[ConstraintElimination] Make decompose() infallible

decompose() currently returns a mix of {} and 0 + 1*V on failure.
This changes it to always return the 0 + 1*V form, thus making
decompose() infal

[ConstraintElimination] Make decompose() infallible

decompose() currently returns a mix of {} and 0 + 1*V on failure.
This changes it to always return the 0 + 1*V form, thus making
decompose() infallible.

This makes the code marginally more powerful, e.g. we now fold
sub_decomp_i80 by treating the constant as a symbolic value.

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

show more ...

[ConstraintElim] Use helper to allow overflow for coefficients of GEPs

If the arithmetic for indices of inbounds GEPs overflows, the result is
poison. This means it is also OK for the coefficients t

[ConstraintElim] Use helper to allow overflow for coefficients of GEPs

If the arithmetic for indices of inbounds GEPs overflows, the result is
poison. This means it is also OK for the coefficients to overflow. GEP
decomposition is limited to cases where the index size is <= 64 bit,
which can be represented by int64_t used for the coefficients in the
constraint system.

show more ...

[ConstraintElim] Replace custom GEP index handling by using existing code

Instead of duplicating the existing decomposition code for GEP indices
just use the existing code by calling the existing de

[ConstraintElim] Replace custom GEP index handling by using existing code

Instead of duplicating the existing decomposition code for GEP indices
just use the existing code by calling the existing decompose function on
the index expression and multiply the result's coefficients by the scale of
the index.

This both reduces code duplication and generalizes the pattern we can
handle.

show more ...

[ConstraintElim] Bail out for GEPs when index size > 64 bits.

Limit pointer decomposition to pointers with index sizes of at most 64
bits. int64_t is used for coefficients, so as long as the index s

[ConstraintElim] Bail out for GEPs when index size > 64 bits.

Limit pointer decomposition to pointers with index sizes of at most 64
bits. int64_t is used for coefficients, so as long as the index size <=
64 bits we should be able to represent all pointer offsets.

Pointer decomposition is limited to inbounds GEPs, so if a index
computation would overflow the result is poison, so it doesn't matter
that the coefficient overflows.

This allows replacing MulOverflow with regular multiplications.

show more ...

[ConstraintElimination] Add tests with 128 bit pointers.

[ConstraintElimination] Regenerate check lines for test.

Thanks @nikic for spotting that!

[ConstraintElimination] Include index type scale.

The current decomposition for GEPs did not correctly handle cases where
GEPs access different source types. Adjust the constraints by including
the

[ConstraintElimination] Include index type scale.

The current decomposition for GEPs did not correctly handle cases where
GEPs access different source types. Adjust the constraints by including
the indexed type-size as coefficients.

Further generalization to allow GEPs with more than one index is a
needed general follow-up improvement.

show more ...

[ConstraintElimination] Update tests to use opaque pointers.

[ConstraintElimination] Fix crash when combining results.

f213128b292d didn't account for the possibility that the result of
decompose may be empty. Fix that by explicitly checking. Use a newly
intr

[ConstraintElimination] Fix crash when combining results.

f213128b292d didn't account for the possibility that the result of
decompose may be empty. Fix that by explicitly checking. Use a newly
introduced helper to also reduce some duplication.

Thanks @bjope for finding the issue!

show more ...

[ConstraintElimination] Check if const. is small enough before using it

Check if the value of a ConstantInt is small enough to be used for
solving before calling getSExtValue.

Fixes #55085