[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] 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] Support conditions from loop preheaders

This patch extends the condition collection logic to allow adding
conditions from pre-headers to loop headers, by allowing cases where

[ConstraintElimination] Support conditions from loop preheaders

This patch extends the condition collection logic to allow adding
conditions from pre-headers to loop headers, by allowing cases where the
target block dominates some of its predecessors.

show more ...

[ConstraintElimination] Skip pointer casts.

We should be able to look through pointer casts that do not impact the
value.

[ConstraintElimination] Fix -Wunused-function in -DLLVM_ENABLE_ASSERTIONS=off build

[ConstraintElimination] Add nicer way to dump constraints (NFC).

Use ConstraintSystem::dump(Names) to display the result of decomposing a
condition.

[ConstraintElimination] Add support for EQ predicates.

A == B map to A >= B && A <= B
(https://alive2.llvm.org/ce/z/_dwxKn).

This extends the constraint construction to return a list of
constraints

[ConstraintElimination] Add support for EQ predicates.

A == B map to A >= B && A <= B
(https://alive2.llvm.org/ce/z/_dwxKn).

This extends the constraint construction to return a list of
constraints, which can be used to properly de-compose nested AND & OR.

show more ...

[ConstraintElimination] Negate IR condition directly.

Instead of using ConstraintSystem::negate when adding new constraints,
flip the condition in IR.

The main advantage is that EQ predicates can b

[ConstraintElimination] Negate IR condition directly.

Instead of using ConstraintSystem::negate when adding new constraints,
flip the condition in IR.

The main advantage is that EQ predicates can be represented by 2
constraints, which makes negating based on the constraint tricky. The IR
condition can easily negated.

show more ...

[ConstraintElimination] Verify CS and DFSInStack are in sync.(NFC)

After the main loop is done, we should have one constraint per item in
DFSInStack. Otherwise we added a constraint without a proper

[ConstraintElimination] Verify CS and DFSInStack are in sync.(NFC)

After the main loop is done, we should have one constraint per item in
DFSInStack. Otherwise we added a constraint without a proper DFSInStack
item.

show more ...

[CodeGen, Transforms] Use llvm::sort (NFC)

[ConstraintElimination] Add support for select form of and/or

This patch adds support for select form of and/or.
Currently there is an ongoing effort for moving towards using `select a, b, false` in

[ConstraintElimination] Add support for select form of and/or

This patch adds support for select form of and/or.
Currently there is an ongoing effort for moving towards using `select a, b, false` instead of `and i1 a, b` and
`select a, true, b` instead of `or i1 a, b` as well.
D93065 has links to relevant changes.

Alive2 proof: (undef input was disabled due to timeout :( )
- and: https://alive2.llvm.org/ce/z/AgvFbQ
- or: https://alive2.llvm.org/ce/z/KjLJyb

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

show more ...

[ConstraintElimination] Handle constraints with all zero var coeffs.

Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are alwa

[ConstraintElimination] Handle constraints with all zero var coeffs.

Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are always true/false.

show more ...

[ConstraintElimination] Make sure arguments of std:pow match.

This should fix a build failure on some systems, e.g. solaris11-sparcv9
http://lab.llvm.org:8014/#/builders/22

[ConstraintElimination] Decompose GEP %ptr, ZEXT(SHL()).

Add support to decompose a GEP with a ZEXT(SHL()) operand.

[ConstraintElimination] Decompose GEP %ptr, SHL().

Add support the decompose a GEP with an SHL operand.

[ConstraintElimination] Decompose GEP with arbitrary offsets.

This patch decomposes `GEP %x, %offset` as 0 + 1 * %x + 1 * %off.

[ConstraintElimination] Decompose add nuw/sub nuw.

Make use of the more flexible constraint handling added in
a8a79c90699a7ae9dee07daf7281cbbd592bf6ea to decompose add nuw/sub nuw.

[ConstraintElimination] Refactor constraint extraction (NFC).

This patch generalizes the extraction of a constraint for a given
condition. It allows decompose to return a vector of c * X pairs, whic

[ConstraintElimination] Refactor constraint extraction (NFC).

This patch generalizes the extraction of a constraint for a given
condition. It allows decompose to return a vector of c * X pairs, which
allows de-composing multiple instructions in the future.

It also adds more clarifying comments.

show more ...

[ConstraintElimination] Add support for And.

When processing conditional branches, if the condition is an AND of 2 compares
and the true successor only has the current block as predecessor, queue bo

[ConstraintElimination] Add support for And.

When processing conditional branches, if the condition is an AND of 2 compares
and the true successor only has the current block as predecessor, queue both
conditions for the true successor.

show more ...

[ConstraintElimination] Add support for Or.

When processing conditional branches, if the condition is an OR of 2 compares
and the false successor only has the current block as predecessor, queue bot

[ConstraintElimination] Add support for Or.

When processing conditional branches, if the condition is an OR of 2 compares
and the false successor only has the current block as predecessor, queue both
negated conditions for the false successor

show more ...

[NewPM] Port ConstraintElimination to the new pass manager

If -enable-constraint-elimination is specified, add it to the -O2/-O3 pipeline.
(-O1 uses a separate function now.)

Reviewed By: fhahn, ae

[NewPM] Port ConstraintElimination to the new pass manager

If -enable-constraint-elimination is specified, add it to the -O2/-O3 pipeline.
(-O1 uses a separate function now.)

Reviewed By: fhahn, aeubanks

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

show more ...

[ConstraintElimination] Internalize function/class and delete an implied condition. NFC

Delete an implied condition (E.NumIn <= CB.NumIn)

[ConstraintElimination] Add constraint elimination pass.

This patch is a first draft of a new pass that adds a more flexible way
to eliminate compares based on more complex constraints collected fro

[ConstraintElimination] Add constraint elimination pass.

This patch is a first draft of a new pass that adds a more flexible way
to eliminate compares based on more complex constraints collected from
dominating conditions.

In particular, it aims at simplifying conditions of the forms below
using a forward propagation approach, rather than instcomine-style
ad-hoc backwards walking of def-use chains.

if (x < y)
if (y < z)
if (x < z) <- simplify

or

if (x + 2 < y)
if (x + 1 < y) <- simplify assuming no wraps

The general approach is to collect conditions and blocks, sort them by
dominance and then iterate over the sorted list. Conditions are turned
into a linear inequality and add it to a system containing the linear
inequalities that hold on entry to the block. For blocks, we check each
compare against the system and see if it is implied by the constraints
in the system.

We also keep a stack of processed conditions and remove conditions from
the stack and the constraint system once they go out-of-scope (= do not
dominate the current block any longer).

Currently there still are the least the following areas for improvements

* Currently large unsigned constants cannot be added to the system
(coefficients must be represented as integers)
* The way constraints are managed currently is not very optimized.

Reviewed By: spatel

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

show more ...