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

[ConstraintElimination] Remove dead variables when dropping constraints.

This patch extends ConstraintElimination to also remove dead variables
when removing a constraint. When a constraint is remov

[ConstraintElimination] Remove dead variables when dropping constraints.

This patch extends ConstraintElimination to also remove dead variables
when removing a constraint. When a constraint is removed because it is
out of scope, all new variables added for this constraint can also be
removed.

This keeps the total size of the systems much smaller, because it
reduces the number of variables drastically.

It also fixes a bug where variables where removed incorrectly.

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

show more ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[ConstraintElimination] Remove ConstraintListTy (NFCI).

This patch simplifies constraint handling by removing the
ConstraintListTy wrapper struct and moving the Preconditions directly
into Constrain

[ConstraintElimination] Remove ConstraintListTy (NFCI).

This patch simplifies constraint handling by removing the
ConstraintListTy wrapper struct and moving the Preconditions directly
into ConstraintTy. This reduces the amount of memory needed for managing
constraints.

The only use case for ConstraintListTy was adding 2 constraints to model
ICMP_EQ conditions. But this can be handled by adding an IsEq flag. When
adding an equality constraint, we need to add the constraint and the
inverted constraint.

show more ...

[ConstraintElimination] Support add with precondition.

If we can prove that an addition without wrap flags won't wrap, decompse
the operation.

Issue #48253

[ConstraintElimination] Remove unnecessary recursion (NFC).

Perform predicate normalization in a single switch, rather then going
through recursions.

[ConstraintElimination] Skip floating point compares. (NFC)

The solver only supports integer conditions. Adding floating point
compares to the worklist only adds extra work. Just skip them.

[ConstraintElimination] Remove redundant lookup (NFC).

[ConstraintElimination] Move some definitions closer to uses (NFC).

[llvm] Use = default (NFC)

[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] Handle degenerate case with branch to same dest.

When a conditional branch has the same block as both true and false
successor it is not safe to add the condition.

Fixes PR4

[ConstraintElimination] Handle degenerate case with branch to same dest.

When a conditional branch has the same block as both true and false
successor it is not safe to add the condition.

Fixes PR49819.

show more ...

[ConstraintElimination] Use constraints with 0 or 1 coefficients.

isConditionImplied is able to correctly handle 0 or 1 coefficients, so
let it handle those cases, rather than skipping them.

[ConstraintElimination] Use simplified constraint for == 0.

When checking x == 0, checking x u<= 0 is sufficient and simpler than
x u>= 0 && x u<= 0.

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

------

[ConstraintElimination] Use simplified constraint for == 0.

When checking x == 0, checking x u<= 0 is sufficient and simpler than
x u>= 0 && x u<= 0.

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

----------------------------------------
define i1 @src(i4 %a) {
%0:
%c = icmp eq i4 %a, 0
ret i1 %c
}
=>
define i1 @tgt(i4 %a) {
%0:
%c = icmp ule i4 %a, 0
ret i1 %c
}
Transformation seems to be correct!

show more ...

[ConstraintElimination] Introduce struct to manage constraints. (NFC)

This patch adds a struct to manage a list of constraints. It simplifies
a follow-up change, that adds pre-conditions that must h

[ConstraintElimination] Introduce struct to manage constraints. (NFC)

This patch adds a struct to manage a list of constraints. It simplifies
a follow-up change, that adds pre-conditions that must hold before a
list of constraints can be used.

show more ...

[ConstraintElimination] Fix sign of sub decomposition.

Update the decomposition code to make sure the right coefficient (-1) is
used for the second operand of the subtract.

Fixes PR53123.

[ConstraintElimination] Initial support for using info from assumes.

This patch adds initial support to use facts from @llvm.assume calls. It
intentionally does not handle all possible cases to keep

[ConstraintElimination] Initial support for using info from assumes.

This patch adds initial support to use facts from @llvm.assume calls. It
intentionally does not handle all possible cases to keep things simple
initially.

For now, the condition from an assume is made available on entry to the
containing block, if the assume is guaranteed to execute. Otherwise it
is only made available in the successor blocks.

show more ...

[NewPM] Don't mark AA analyses as preserved

Currently all AA analyses marked as preserved are stateless, not taking
into account their dependent analyses. So there's no need to mark them
as preserve

[NewPM] Don't mark AA analyses as preserved

Currently all AA analyses marked as preserved are stateless, not taking
into account their dependent analyses. So there's no need to mark them
as preserved, they won't be invalidated unless their analyses are.

SCEVAAResults was the one exception to this, it was treated like a
typical analysis result. Make it like the others and don't invalidate
unless SCEV is invalidated.

Reviewed By: asbirlea

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

show more ...

[ConstraintElimination] Only strip casts preserving the representation.

Things like addrspacecast may not be no-ops, so we should not look
through them.

[llvm] Use llvm::drop_begin (NFC)

[ConstraintElimination] Use unsigned > 0 instead of != 0.

ICMP_NE predicates cannot be directly represented as constraint. But we
can use ICMP_UGT instead ICMP_NE for %x != 0.

See https://alive2.ll

[ConstraintElimination] Use unsigned > 0 instead of != 0.

ICMP_NE predicates cannot be directly represented as constraint. But we
can use ICMP_UGT instead ICMP_NE for %x != 0.

See https://alive2.llvm.org/ce/z/XlLCsW

show more ...

[ConstraintElimination] Fix variables used for pattern matching.

Re-using the matched variable in the pattern does not work as expected.
This patch fixes that by introducing a new variable for the 2

[ConstraintElimination] Fix variables used for pattern matching.

Re-using the matched variable in the pattern does not work as expected.
This patch fixes that by introducing a new variable for the 2nd level
match.

show more ...

[ConstraintElimination] Decompose a few more GEP indices.

This patch adds handling for zero-extended GEP indices.

[ConstraintElimination] Improve index handing during constraint building.

This patch improves the index management during constraint building.
Previously, the code rejected constraints which used va

[ConstraintElimination] Improve index handing during constraint building.

This patch improves the index management during constraint building.
Previously, the code rejected constraints which used values that were not
part of Value2Index, but after combining the coefficients of the new
indices were 0 (if ShouldAdd was 0).

In those cases, no new indices need to be added. Instead of adding to
Value2Index directly, add new indices to the NewIndices map. The caller
can then check if it needs to add any new indices.

This enables checking constraints like `a + x <= a + n` to `x <= n`,
even if there is no constraint for `a` directly.

show more ...