[ConstraintElim] Add support for decomposing gep nuw (#118639)

ConstraintElimination currently only supports decomposing gep nusw with
non-negative indices (with "non-negative" possibly being enfor

[ConstraintElim] Add support for decomposing gep nuw (#118639)

ConstraintElimination currently only supports decomposing gep nusw with
non-negative indices (with "non-negative" possibly being enforced via
pre-condition).

Add support for gep nuw, which directly gives us the necessary
guarantees for the decomposition.

show more ...

[ConstraintElim] Add tests for gep nuw (NFC)

[ConstraintElim] Use nusw flag for GEP decomposition

Check for nusw instead of inbounds when decomposing GEPs.

In this particular case, we can also look through multiple nusw
flags, because we will

[ConstraintElim] Use nusw flag for GEP decomposition

Check for nusw instead of inbounds when decomposing GEPs.

In this particular case, we can also look through multiple nusw
flags, because we will ultimately be working in the unsigned
constraint system.

show more ...

[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] Use collectOffset instead of custom GEP idx iteration.

Use collectOffset to collect scaled indices and constant offset for GEP
instead of custom code. This simplifies the logic in d

[ConstraintElim] Use collectOffset instead of custom GEP idx iteration.

Use collectOffset to collect scaled indices and constant offset for GEP
instead of custom code. This simplifies the logic in decomposeGEP and
allows to handle all cases supported by the generic helper.

show more ...

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

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

[ConstraintElimination] Update tests to use opaque pointers.

[ConstraintElimination] Generalize OR matching.

Extend OR handling to traverse chains of ORs.

[ConstraintElimination] Transfer info from SGE to unsigned system.

This patch adds a new transferToOtherSystem helper that tries to
transfer information from signed predicates to the unsigned system

[ConstraintElimination] Transfer info from SGE to unsigned system.

This patch adds a new transferToOtherSystem helper that tries to
transfer information from signed predicates to the unsigned system and
vice versa.

The initial version adds A >=u B for A >=s B && B >=s 0

https://alive2.llvm.org/ce/z/8b6F9i

show more ...

[ConstraintElimination] Add initial signed support.

This patch adds initial support for signed conditions. To do so,
ConstraintElimination maintains two separate systems, one with facts
from signed

[ConstraintElimination] Add initial signed support.

This patch adds initial support for signed conditions. To do so,
ConstraintElimination maintains two separate systems, one with facts
from signed and one for unsigned conditions.

To start with this means information from signed and unsigned conditions
is kept completely separate. When it is safe to do so, information from
signed conditions may be also transferred to the unsigned system and
vice versa. That's left for follow-ups.

In the initial version, de-composition of signed values just handles
constants and otherwise just uses the value, without trying to
decompose the operation. Again this can be extended in follow-up
changes.

The main benefit of this limited signed support is proving >=s 0
pre-conditions added in D118799. But even this initial version also
fixes PR53273.

Depends on D118799.

Reviewed By: reames

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

show more ...

[ConstraintElimination] Allow adding pre-conditions for constraints.

With this patch pre-conditions can be added to a list of constraints.
Constraints with pre-conditions can only be used if all pre

[ConstraintElimination] Allow adding pre-conditions for constraints.

With this patch pre-conditions can be added to a list of constraints.
Constraints with pre-conditions can only be used if all pre-conditions
are satisfied when the constraint is used.

The pre-conditions at the moment are specified as a list of
(Predicate, Value *,Value *) tuples. This allow easily checking them
like any other condition, using the existing infrastructure.

This then is used to limit GEP decomposition to cases where we can
prove that offsets are signed positive.

This fixes a couple of incorrect transforms where GEP offsets where
assumed to be signed positive, but they were not.

Note that this effectively disables GEP decomposition, as there's no
support for reasoning about signed predicates. D118806 adds initial
signed support.

Fixes PR49624.

Reviewed By: reames

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

show more ...

[ConstraintElimination] Add additional GEP arithmetic tests.

[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] Rewrite tests to reduce verification complexity.

This patch reduces the bitwidth of types certain tests operate and gets
rid of a number of @use(i1) calls and xor's the condi

[ConstraintElimination] Rewrite tests to reduce verification complexity.

This patch reduces the bitwidth of types certain tests operate and gets
rid of a number of @use(i1) calls and xor's the conditions together
instead, which eliminates all timeouts when verifying the tests.
See https://github.com/AliveToolkit/alive2/issues/744 for more details.

show more ...

[ConstraintElimination] Decompose a few more GEP indices.

This patch adds handling for zero-extended GEP indices.

[ConstraintElimination] Decompose zext for unsigned compares.

For unsigned compares, zext should be a no-op and we can add the
extended value to the constraint system.

[ConstraintElimination] Add additional tests.

Adds additional test cases with zexts, conditions that require temporary
indices.

[ConstraintElimination] Require GEPs to be inbounds for decomposition.

During decomposition, we assume the no-wrap properties of inbound GEPs.
Make sure the decomposed GEP is actually inbounds.

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