[ConstraintElim] Extend `checkOrAndOpImpliedByOther` to handle and/or expr trees. (#117123)

This patch extends `checkOrAndOpImpliedByOther` to handle and/or trees.
Limitation: At least one of the o

[ConstraintElim] Extend `checkOrAndOpImpliedByOther` to handle and/or expr trees. (#117123)

This patch extends `checkOrAndOpImpliedByOther` to handle and/or trees.
Limitation: At least one of the operands of root and/or instruction
should be an icmp. That is, this patch doesn't support expressions like
`(cmp1 & cmp2) & (cmp3 & cmp4)`.

Closes https://github.com/llvm/llvm-project/issues/117107.
Compile-time impact:
http://llvm-compile-time-tracker.com/compare.php?from=69cc3f096ccbdef526bbd5a065a25c95122e87ee&to=919416d2c4c71e3b9fe533af2c168a36c7893be5&stat=instructions%3Au

show more ...

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimizati

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimization in the
unsigned system, due to missing the information that all variables are
unsigned (non-negative).

Variables can be marked as non-negative by adding Var >= 0 for all
variables. This is done for arguments on ConstraintInfo construction and
after adding new variables. This handles cases like the ones outlined in
https://discourse.llvm.org/t/why-does-llvm-not-perform-range-analysis-on-integer-values/74341

The original example shared above is now handled without this change,
but adding another variable means that instcombine won't be able to
simplify examples like https://godbolt.org/z/hTnra7zdY

Adding the extra variables comes with a slight compile-time increase
https://llvm-compile-time-tracker.com/compare.php?from=7568b36a2bc1a1e496ec29246966ffdfc3a8b87f&to=641a47f0acce7755e340447386013a2e086f03d9&stat=instructions:u

stage1-O3 stage1-ReleaseThinLTO stage1-ReleaseLTO-g stage1-O0-g
+0.04% +0.07% +0.05% +0.02%
stage2-O3 stage2-O0-g stage2-clang
+0.05% +0.05% +0.05%

https://github.com/llvm/llvm-project/pull/76262

show more ...

[ConstraintElim] Use disjoint flag for decomposition (#74478)

Use the or disjoint flag for decomposing or into add, which will handle
cases that haveNoCommonBitsSet() may not be able to reinfer (e.

[ConstraintElim] Use disjoint flag for decomposition (#74478)

Use the or disjoint flag for decomposing or into add, which will handle
cases that haveNoCommonBitsSet() may not be able to reinfer (e.g.
because they require context-sensitive facts, which the call here does
not use.)

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

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

[ConstraintElimination] Add tests to check for `or` instruction decomposition if a constant operand is < 2^known_zero_bits of the first operand.

Reviewed By: fhahn

Differential Revision: https://re

[ConstraintElimination] Add tests to check for `or` instruction decomposition if a constant operand is < 2^known_zero_bits of the first operand.

Reviewed By: fhahn

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

show more ...

[ConstraintElimination] Generalize OR matching.

Extend OR handling to traverse chains of ORs.

[ConstraintElimination] Extend test coverage for OR chains.

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
I

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
In this patch focus has been put on test cases for ConstantMerge,
ConstraintElimination, CorrelatedValuePropagation, GlobalDCE,
GlobalOpt, SCCP, TailCallElim and PredicateInfo.

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

show more ...

[ConstraintElimination] Rewrite tests to reduce verification complexity.

This patch reduces the bitwidth of types certain tests operate and gets
rid of a number of @use(i1) calls and xor's the condi

[ConstraintElimination] Rewrite tests to reduce verification complexity.

This patch reduces the bitwidth of types certain tests operate and gets
rid of a number of @use(i1) calls and xor's the conditions together
instead, which eliminates all timeouts when verifying the tests.
See https://github.com/AliveToolkit/alive2/issues/744 for more details.

show more ...

[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] Add tests for select form and/or (NFC)

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

[ConstraintElimination] Add add/sub/and/or test cases.

This adds a new set of tests for upcoming constraint elimination
changes.