[ConstraintElim] Move logic to remove stack entry to helper (NFC).

Preparation for follow-up patch that uses the logic in a separate place.

[ConstraintElim] Port `mul nuw` for unsigned to `mul nsw` to signed.

Add handling for `mul nsw` for signed systems based on the logic for
`mul nuw` for unsigned.

[ConstraintElim] Fix integer overflow in ConstraintSystem::negate.

This fixes another integer overflow that was exposed by a variant of the
test case from #62226.

[ConstraintElim] Fix integer overflow in getConstraint.

Use SubOverflow to avoid signed integer overflow when combining
coefficients.

Fixes #62226.

[ConstraintElimination] Transfer info from sgt %a, %b to ugt %a, %b if %b > 0

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

[ConstraintElimination] Add function arguments to constraint system before solving

If there is an optimisation opportunity and the function argument hasn’t been added to constraint
system through pr

[ConstraintElimination] Add function arguments to constraint system before solving

If there is an optimisation opportunity and the function argument hasn’t been added to constraint
system through previous facts we fail to optimise it.

It might be a good idea to start the constraint system with all the function arguments added to the system

Reviewed By: fhahn

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

show more ...

[ConstraintElim] Use GEPOperator instead of GetElementPtrInst.

The logic in ConstraintElimination should trivially apply to GEP
constant expressions as well, so update code to deal with GEPOperator

[ConstraintElim] Use GEPOperator instead of GetElementPtrInst.

The logic in ConstraintElimination should trivially apply to GEP
constant expressions as well, so update code to deal with GEPOperator
instead.

show more ...

[Transforms] Use *{Set,Map}::contains (NFC)

[ConstraintElimination] Fix UB after D145677

[ConstraintElimination] Fix undefined behaviour in shl decomposition

Add checks to prevent decomposing constants bigger than 64.
relates to https://github.com/llvm/llvm-project/issues/61127

Reviewe

[ConstraintElimination] Fix undefined behaviour in shl decomposition

Add checks to prevent decomposing constants bigger than 64.
relates to https://github.com/llvm/llvm-project/issues/61127

Reviewed By: fhahn

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

show more ...

[ConstraintElimination] Decompose or instruction if the constant operand < 2^known_zero_bits of the first operand.

The or operation can be represented as an add instruction.

Reviewed By: fhahn

Dif

[ConstraintElimination] Decompose or instruction if the constant operand < 2^known_zero_bits of the first operand.

The or operation can be represented as an add instruction.

Reviewed By: fhahn

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

show more ...

[IR] Add operator<< overload for CmpInst::Predicate (NFC)

I regularly try and fail to use this while debugging.

Recommit "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 02ae7e72b3f00969eeb579a2b4346082827f0b35.

include Value.h in ConstraintSystem.h

Revert "Recommit "[ConstraintElimination] Change debug output to display variable names.""

This reverts commit 2a2a6bfcfe8e62886542cb673ac8df349cf26499.

This causes build failures:

/home/npopo

Revert "Recommit "[ConstraintElimination] Change debug output to display variable names.""

This reverts commit 2a2a6bfcfe8e62886542cb673ac8df349cf26499.

This causes build failures:

/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp: In member function ‘llvm::SmallVector<std::__cxx11::basic_string<char> > llvm::ConstraintSystem::getVarNamesList() const’:
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:118:10: error: invalid use of incomplete type ‘class llvm::Value’
118 | if (V->getName().empty())
| ^~
In file included from /home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:9:
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:119:22: error: invalid use of incomplete type ‘class llvm::Value’
119 | OperandName = V->getNameOrAsOperand();
| ^~
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:121:41: error: invalid use of incomplete type ‘class llvm::Value’
121 | OperandName = std::string("%") + V->getName().str();
| ^~
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~

show more ...

Recommit "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 62d0e1a8541f93dfbf66d982f66da32676df2df7.

remove `dumpWithNames` function

Revert "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 869c87ad10e87db7c032c3464338ab9d50916510.

`dumpWithNames` function should be removed

[ConstraintElimination] Change debug output to display variable names.

Previously when constraint system outputs the rows in the system the variables used are x1,2...n making it hard to infer which

[ConstraintElimination] Change debug output to display variable names.

Previously when constraint system outputs the rows in the system the variables used are x1,2...n making it hard to infer which ones they relate to in the IR

Reviewed By: fhahn

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

show more ...

[ConstraintElim] Add reproducer remarks.

This patch adds an optimization remark for each performed optimization
containing a module that can be used to reproduce the transformation.

The reproducer

[ConstraintElim] Add reproducer remarks.

This patch adds an optimization remark for each performed optimization
containing a module that can be used to reproduce the transformation.

The reproducer function contains a series of @llvm.assume calls, one for
each condition currently in scope. For each condition, the operand
instruction are cloned until we reach operands that have an entry in the
constraint system. Those will then be added as function arguments.

The reproducer functions are minimal, that is, they only contain the
conditions required for a given simplification. The resulting IR is very
compact and can be used to verify each transformation individually.

It also provides a python script to extract the IR from the remarks and
create LLVM IR files from it.

Reviewed By: paquette

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

show more ...

Recommit "[ConstraintElimination] Move Value2Index map to ConstraintSystem (NFC)"

This reverts commit 665ee0cd57f92a112cf8e929d00768e282fb205a.

Fix comments and formatting style.

Revert "[ConstraintElimination] Move Value2Index map to ConstraintSystem (NFC)"

This reverts commit 40ffe9c167395256b43846733ab69eec17eead78.

Reverted because some comments where missed in the revi

Revert "[ConstraintElimination] Move Value2Index map to ConstraintSystem (NFC)"

This reverts commit 40ffe9c167395256b43846733ab69eec17eead78.

Reverted because some comments where missed in the review https://reviews.llvm.org/D142647

show more ...

[ConstraintElimination] Move Value2Index map to ConstraintSystem (NFC)

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

[ConstraintElim] Add option to limit number of rows tracked in system.

Once the constraint system grows too large in terms of number of rows,
queries can become very slow. This patch adds a new opti

[ConstraintElim] Add option to limit number of rows tracked in system.

Once the constraint system grows too large in terms of number of rows,
queries can become very slow. This patch adds a new option to limit the
number of rows tracked.

The python script below can be used to generate worst-case IR with a
chain of conditional branches with N branches.

With this limit, we get the following runtimes:
* python3 generate.py 100: 0.1s
* python3 generate.py 1000: 2s
* python3 generate.py 10000: 4s

Without the limit, the case with 1000 chained conditions takes 20+
seconds.

generate.py:
import sys

N = int(sys.argv[1])

args = []
checks = []

for i in range(0, N):
args.append('i32 %l{}'.format(i))
checks.append("""
bb{0}:
%c{0} = icmp uge i32 %l{0}, 100
br i1 %c{0}, label %bb{1}, label %exit
""".format(i, i+1))

print("""
define i1 @foo({0}) {{
{1}

bb{2}:
%c{2} = icmp uge i32 %l0, 100
ret i1 %c{2}

exit:
ret i1 false
}}
""".format(' ,'.join(args), '\n'.join(checks), N))

Reviewed By: nikic

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

show more ...

[ConstraintElim] Remove legacy pass implementation.

The pass is exclusively used with the new pass manager now, so remove
the legacy PM implementation.

[ConstraintElim] Address comments from D137840.

Reviewed By: nikic

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

[ConstraintElim] Fix sort order to not comparing insts in different bbs.

Update the sort order to make sure that comesBefore is never used from
conditional facts, which are instructions but may use

[ConstraintElim] Fix sort order to not comparing insts in different bbs.

Update the sort order to make sure that comesBefore is never used from
conditional facts, which are instructions but may use DFS numbers from
different blocks.

This fixes a crash in the added test on some platforms.

show more ...