[LoopPred/WC] Use a dominating widenable condition to remove analyze loop exits
authorPhilip Reames <listmail@philipreames.com>
Mon, 18 Nov 2019 19:21:53 +0000 (11:21 -0800)
committerPhilip Reames <listmail@philipreames.com>
Mon, 18 Nov 2019 19:23:29 +0000 (11:23 -0800)
commitad5a84c883354e8bb595ebfd9971fe4a14b770fd
tree9125c03f37ca1fc672597035669f8b796d521ce6
parente15b26fbbd901315a1402f97e83abf29bdce9a9f
[LoopPred/WC] Use a dominating widenable condition to remove analyze loop exits

This implements a version of the predicateLoopExits transform from IndVarSimplify extended to exploit widenable conditions - and thus be much wider in scope of legality. The code structure ends up being almost entirely different, so I chose to duplicate this into the LoopPredication pass instead of trying to reuse the code in the IndVars.

The core notions of the transform are as follows:

    If we have a widenable condition which controls entry into the loop, we're allowed to widen it arbitrarily. Given that, it's simply a *profitability* question as to what conditions to fold into the widenable branch.
    To avoid pass ordering issues, we want to avoid widening cases that would otherwise be dischargeable. Or... widen in a form which can still be discharged. Thus, we phrase the transform as selecting one analyzeable exit from the set of analyzeable exits to keep. This avoids creating pass ordering complexities.
    Since none of the above proves that we actually exit through our analyzeable exits - we might exit through something else entirely - we limit ourselves to cases where a) the latch is analyzeable and b) the latch is predicted taken, and c) the exit being removed is statically cold.

Differential Revision: https://reviews.llvm.org/D69830
llvm/lib/Transforms/Scalar/LoopPredication.cpp
llvm/test/Transforms/LoopPredication/predicate-exits.ll [new file with mode: 0644]