[ConstraintElim] Try to use first cmp to prove second cmp for ANDs.
authorFlorian Hahn <flo@fhahn.com>
Wed, 28 Jun 2023 12:19:39 +0000 (13:19 +0100)
committerFlorian Hahn <flo@fhahn.com>
Wed, 28 Jun 2023 12:19:41 +0000 (13:19 +0100)
commit0ad6879a626edc2947b4a513e1473febb47e8072
treec5909b3a9b4e953190882a0ffaae09372788b405
parente9074d019e13b7ac658f5d3f39135e1cba00e625
[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
llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll
llvm/test/Transforms/ConstraintElimination/and.ll
llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll
llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll