Recommit "[ConstraintElimination] Transfer info from ULT to signed system."

This reverts commit 94ed2caf708818dd3a0b376bbce56e53c0956f1e.

The issue with no-determinism with the test has been fixed

Recommit "[ConstraintElimination] Transfer info from ULT to signed system."

This reverts commit 94ed2caf708818dd3a0b376bbce56e53c0956f1e.

The issue with no-determinism with the test has been fixed in
d9526e8a52ca9d5.

show more ...

[ConstraintElimination] Use stable_sort to sort worklist.

If there are multiple constraints in the same block, at the moment the
order they are processed may be different depending on the sort
imple

[ConstraintElimination] Use stable_sort to sort worklist.

If there are multiple constraints in the same block, at the moment the
order they are processed may be different depending on the sort
implementation.

Use stable_sort to ensure consistent ordering.

show more ...

Revert "[ConstraintElimination] Transfer info from ULT to signed system."

This reverts commit 316e106f49c4c86f3485d69d1539e2aed12251c0.

This breaks a bot with expensive checks.

[ConstraintElimination] Transfer info from ULT to signed system.

If A u< B holds, then A s>= 0 && A s< B holds if B s>= 0.

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

[ConstraintElimination] Transfer info from SLT to unsigned system.

If A s< B holds, then A u< also holds, if A s>= 0.

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

[ConstraintElimination] Transfer info from SGT to unsigned system.

If A >s B then A >=u 0, if B >=s -1.

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

[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] Update addFact to take Predicate and ops (NFC).

This allows adding facts without necessarily having a corresponding
CmpInst.

[ConstraintElimination] Remove unneeded StackEntry::Condition (NFC).

The field was only used for debug printing. Print constraint from the
system instead.

[ConstraintElimination] Move logic to check condition to helper (NFC).

[ConstraintElimination] Move logic to get a constraint to helper (NFC).

[ConstraintElimination] Move logic to add constraint to helper (NFC).

[ConstraintElimination] Move StackEntry up, to allow use earlier (NFC).

[ConstraintElimination] Support constraints with only const ops.

Remove the early exit if both constraints contain no variables. This
restriction is unnecessayr for correctness and removing it simpl

[ConstraintElimination] Support constraints with only const ops.

Remove the early exit if both constraints contain no variables. This
restriction is unnecessayr for correctness and removing it simplifies
handling of trivial constant conditions in follow-up changes.

show more ...

[Scalar] Remove isValidSingle (NFC)

The last use was removed on Feb 18, 2022 in commit
00ab91b70d21f72af59e4e198c6dc819452405af.

[ConstraintElimination] Simplify ssub(A,B) if B s>=b && B s>=0.

A first patch to use the reasoning in ConstraintElimination to simplify
sub with overflow to a regular sub, if the operation is guaran

[ConstraintElimination] Simplify ssub(A,B) if B s>=b && B s>=0.

A first patch to use the reasoning in ConstraintElimination to simplify
sub with overflow to a regular sub, if the operation is guaranteed to
not overflow.

Reviewed By: spatel

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

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

[ConstraintElimination] Move logic to build worklist to helper (NFC).

This refactor makes it easier to extend the logic to collect information
from blocks in the future, without even further increas

[ConstraintElimination] Move logic to build worklist to helper (NFC).

This refactor makes it easier to extend the logic to collect information
from blocks in the future, without even further increasing the size of
eliminateConstriants.

show more ...

[ConstraintElimination] Move ConstraintInfo after ConstraintTy. (NFC)

Code movement to it slightly easier to use ConstraintTy & co in
ConstraintInfo directly, for follow-up patches.

[ConstraintElimination] Use AddOverflow for offset summation.

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

[ConstraintElimination] Add missing dominance check.

When dealing with an unconditional branch, the condition can only added
if BB properly dominates the successor.

[ConstraintElimination] Support BBs with single successor in CanAdd.

If BB has a single successor, conditions can be added safely.

[ConstraintElimination] Remove over-eager assertion.

After moving the CanAdd check in c60cdb44f7ecb4b02ed and using it for
the assume cases as well, the passed in block may not have a branch
instru

[ConstraintElimination] Remove over-eager assertion.

After moving the CanAdd check in c60cdb44f7ecb4b02ed and using it for
the assume cases as well, the passed in block may not have a branch
instruction as terminator. This can trigger the assertion. Given the new
use case, it doesn't add value any longer and can be removed.

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

show more ...

[ConstraintElimination] Use ZExtValue for unsigned decomposition.

When decomposing constraints for unsigned conditions, we can use
negative values by zero-extending them, as long as they are less th

[ConstraintElimination] Use ZExtValue for unsigned decomposition.

When decomposing constraints for unsigned conditions, we can use
negative values by zero-extending them, as long as they are less than
the maximum constraint value.

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

show more ...

[ConstraintElimination] Only add cond from assume to succs if valid.

Add missing CanAdd check before adding a condition from an assume
to the successor blocks. When adding information from assume to

[ConstraintElimination] Only add cond from assume to succs if valid.

Add missing CanAdd check before adding a condition from an assume
to the successor blocks. When adding information from assume to
successor blocks we need to perform the same CanAdd as we do for adding
a condition from a branch.

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

show more ...