[ConstraintElim] Use isKnownNonNegative for condition transfer. (#72879)

Use isKnownNonNegative for information transfer. This can improve
results, in cases where ValueTracking can infer additional

[ConstraintElim] Use isKnownNonNegative for condition transfer. (#72879)

Use isKnownNonNegative for information transfer. This can improve
results, in cases where ValueTracking can infer additional non-negative
info, e.g. for phi nodes.

This allows simplifying the check from
https://github.com/llvm/llvm-project/issues/63126 by
ConstraintElimination. It is also simplified by IndVarSimplify now; note
the changes in llvm/test/Transforms/PhaseOrdering/loop-access-checks.ll,
due to this now being simplified earlier.

show more ...

[ConstraintElim] Remove redundant debug output (NFC).

The removed code was printing `Processing facts ...` a second time.

[ConstraintElim] Make sure add-rec is for the current loop.

Update addInfoForInductions to also check if the add-rec is for the
current loop. Otherwise we might add incorrect facts or crash.

Fixes

[ConstraintElim] Make sure add-rec is for the current loop.

Update addInfoForInductions to also check if the add-rec is for the
current loop. Otherwise we might add incorrect facts or crash.

Fixes a miscompile & crash introduced by 00396e6a1a0b.

show more ...

[ConstraintElim] Add missing check to make sure the bound is loop-invariant (#70555)

This PR adds a missing check for
https://github.com/llvm/llvm-project/commit/e6a1657fa30c747f4412fc47f567660ebe8

[ConstraintElim] Add missing check to make sure the bound is loop-invariant (#70555)

This PR adds a missing check for
https://github.com/llvm/llvm-project/commit/e6a1657fa30c747f4412fc47f567660ebe861a9e
to make sure the bound is loop-invariant.

Example:
```
define i32 @main() {
entry:
br label %for.header

for.header:
%ind1 = phi i64 [ %ind1.i, %for.latch ], [ 0, %entry ]
%ind2 = phi i64 [ %ind2.i, %for.latch ], [ 5, %entry ]
%rem = srem i64 %ind2, 4
%cmp6 = icmp eq i64 %ind1, %rem
br i1 %cmp6, label %exit1, label %for.latch

for.latch:
%ind2.i = add i64 %ind2, 1
%ind1.i = add i64 %ind1, 1
%cond = icmp eq i64 %ind1.i, 8
br i1 %cond, label %exit2, label %for.header

exit2:
%cmp = icmp eq i64 %rem, 0
%ret = zext i1 %cmp to i32
ret i32 %ret

exit1:
ret i32 0
}
```
We cannot infer `%ind1 <u %rem` from `icmp eq i64 %ind1, %rem` in the
loop since `%rem` is not a loop-invariant.

Fixes #70510.

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] Support decrementing inductions with step -1. (#68644)

Extend the logic in addInfoForInductions to support decrementing
inductions with a step of -1.

Fixes #64881.

[ConstraintElim] Support arbitrary incoming values for inductions (#68032)

Support arbitray incoming values for AddRecs by getting the loop
predecessor and checking if its SCEV matches the AddRec s

[ConstraintElim] Support arbitrary incoming values for inductions (#68032)

Support arbitray incoming values for AddRecs by getting the loop
predecessor and checking if its SCEV matches the AddRec start.

This is done after the existing check, which can help to catch cases
where the expression gets simplified by SCEV to either an IR constant or
existing value which can be used instead.

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] Add A < B if A is an increasing phi for A != B.

This patch adds additional logic to add additional facts for A != B, if
A is a monotonically increasing induction phi. The motivating

[ConstraintElim] Add A < B if A is an increasing phi for A != B.

This patch adds additional logic to add additional facts for A != B, if
A is a monotonically increasing induction phi. The motivating use case
for this is removing checks when using iterators with hardened libc++,
e.g. https://godbolt.org/z/zhKEP37vG.

The patch pulls in SCEV to detect AddRecs. If possible, the patch adds
the following facts for a AddRec phi PN with StartValue as incoming
value from the loo preheader and B being an upper bound for PN from a
condition in the loop header.

* (ICMP_UGE, PN, StartValue)
* (ICMP_ULT, PN, B) [if (ICMP_ULE, StartValue, B)]

The patch also adds an optional precondition to FactOrCheck (the new
DoesHold field) , which can be used to only add a fact if the
precondition holds at the point the fact is added to the constraint
system.

Depends on D151799.

Reviewed By: nikic

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

show more ...

[ConstraintElimination] Extend unsigned-to-signed fact transfer

Minor addition of transferring unsigned facts to signed comparisons.

Proofs: https://alive2.llvm.org/ce/z/nqqzHb

[ConstraintElim] Support adding facts from switch terminators. (#67061)

After 4a5bcbd5602, switch instructions can now be handled in a
straight-forward manner by adding (ICMP_EQ, ConditionVal, Case

[ConstraintElim] Support adding facts from switch terminators. (#67061)

After 4a5bcbd5602, switch instructions can now be handled in a
straight-forward manner by adding (ICMP_EQ, ConditionVal, CaseVal) for
te successor blocks per case.

show more ...

[ConstraintElim] Store conditional facts as (Predicate, Op0, Op1).

This allows to add facts even if no corresponding ICmp instruction
exists in the IR.

Reviewed By: nikic

Differential Revision: ht

[ConstraintElim] Store conditional facts as (Predicate, Op0, Op1).

This allows to add facts even if no corresponding ICmp instruction
exists in the IR.

Reviewed By: nikic

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

show more ...

[ConstraintElim] Use enum class to differentiate fact/check types (NFC).

Use an enum to clarify the type of fact or check in FactOrCheck, as
suggested in D158837.

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

[ConstraintElim] Add facts implied by MinMaxIntrinsic

Fixes https://github.com/llvm/llvm-project/issues/63896 and https://github.com/rust-lang/rust/issues/113757.
This patch adds facts implied by ll

[ConstraintElim] Add facts implied by MinMaxIntrinsic

Fixes https://github.com/llvm/llvm-project/issues/63896 and https://github.com/rust-lang/rust/issues/113757.
This patch adds facts implied by llvm.smin/smax/umin/umax intrinsics.

Reviewed By: fhahn

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

show more ...

[ConstraintElim] Store the triple Pred + LHS + RHS in ReproducerEntry instead of CmpInst + Not

This patch represents a condition with `Pred + LHS + RHS` in ReproducerEntry instead of `CmpInst + Not`

[ConstraintElim] Store the triple Pred + LHS + RHS in ReproducerEntry instead of CmpInst + Not

This patch represents a condition with `Pred + LHS + RHS` in ReproducerEntry instead of `CmpInst + Not`.
It avoids creating temporary ICmpInsts in D155412.

Reviewed By: nikic, fhahn

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

show more ...

[ConstraintElimination] Handle solving-only `ICMP_NE` predicates

Simplification of non-equality predicates for solving constraint
systems is now supported by checking the validity of related
inequal

[ConstraintElimination] Handle solving-only `ICMP_NE` predicates

Simplification of non-equality predicates for solving constraint
systems is now supported by checking the validity of related
inequalities and equalities.

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

show more ...

[ConstraintElim] Allow and check preconditions in doesHold.

Delegate checking of the constraint & its preconditions to the existing
::isValid. This reduces duplication and allows additional optimiza

[ConstraintElim] Allow and check preconditions in doesHold.

Delegate checking of the constraint & its preconditions to the existing
::isValid. This reduces duplication and allows additional optimizations
together with D152730.

show more ...

[ConstraintElim] Try to use first cmp to prove second cmp for ANDs.

This patch extends the existing logic to handle cases where we have
branch conditions of the form (AND icmp, icmp) where the first

[ConstraintElim] Try to use first cmp to prove second cmp for ANDs.

This patch extends the existing logic to handle cases where we have
branch conditions of the form (AND icmp, icmp) where the first icmp
implies the second. This can improve results in some cases, e.g. if
SimplifyCFG folded conditions from multiple branches to an AND.

The implementation handles this by adding a new type of check
(AndImpliedCheck), which are queued before conditional facts for the same
block.

When encountering AndImpliedChecks during solving, the first condition
is optimistically added to the constraint system, then we check if the
second icmp can be simplified, and finally the newly added entries are
removed.

The reason for doing things this way is to avoid clashes with signed
<-> unsigned condition transfer, which require us to re-order facts to
increase effectiveness.

Reviewed By: nikic, antoniofrighetto

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

show more ...

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

This allows easier re-use of the checking logic. Split off from D151799.

[ConstraintElim] Move FactOrCheck and State definitions to top. (NFC)

This will enable follow-up refactoring to use the State directly in the
constraint system, reducing the need to pass lots of arg

[ConstraintElim] Move FactOrCheck and State definitions to top. (NFC)

This will enable follow-up refactoring to use the State directly in the
constraint system, reducing the need to pass lots of arguments around.

show more ...

[ConstraintElim] Track and simplify conditions at use.

This patch updates ConstraintElimination to track uses of conditions in
the worklist. This allows simplifying conditions using the context that

[ConstraintElim] Track and simplify conditions at use.

This patch updates ConstraintElimination to track uses of conditions in
the worklist. This allows simplifying conditions using the context that
holds directly at the condition, instead of where the condition is
defined.

This allows us to catch more cases in practice: there are multiple
code-size changes for CTMark while compile-time remains unchanged:
https://llvm-compile-time-tracker.com/compare.php?from=4b020cca9363bebab4643f89cfa92ab2fcc7976c&to=7a6e84b8f029713c137814cd46eec775d24a54a1&stat=instructions:u

This should help to simplify D151799.

Reviewed By: nikic

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

show more ...

[ConstraintElimination] Handle `ICMP_EQ` predicates

Simplification of equality predicates is now supported by
transferring equalities into inequalities. This is achieved
by separately checking that

[ConstraintElimination] Handle `ICMP_EQ` predicates

Simplification of equality predicates is now supported by
transferring equalities into inequalities. This is achieved
by separately checking that both `isConditionImplied(A >= B)`
and `isConditionImplied(A <= B)` hold.

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

show more ...

[ConstraintElimination] Refactor `checkAndReplaceCondition` (NFC)

Handling `true` and `false` constant replacements is now abstracted
out into a single lambda function `ReplaceCmpWithConstant`, so a

[ConstraintElimination] Refactor `checkAndReplaceCondition` (NFC)

Handling `true` and `false` constant replacements is now abstracted
out into a single lambda function `ReplaceCmpWithConstant`, so as to
reduce code duplication.

show more ...