[IndVars] Eliminate loop exits with equivalent exit counts
authorPhilip Reames <listmail@philipreames.com>
Sun, 20 Oct 2019 23:38:02 +0000 (23:38 +0000)
committerPhilip Reames <listmail@philipreames.com>
Sun, 20 Oct 2019 23:38:02 +0000 (23:38 +0000)
commit8cbcd2f484a2bc6720d9fd66b71aeaf50a49bc70
tree5ef8241712111c4392c23e33ab64ba5c3bf2f275
parent7015a5c54b53d8d2297a3aa38bc32aab167bdcfc
[IndVars] Eliminate loop exits with equivalent exit counts

We can end up with two loop exits whose exit counts are equivalent, but whose textual representation is different and non-obvious. For the sub-case where we have a series of exits which dominate one another (common), eliminate any exits which would iterate *after* a previous exit on the exiting iteration.

As noted in the TODO being removed, I'd always thought this was a good idea, but I've now seen this in a real workload as well.

Interestingly, in review, Nikita pointed out there's let another oppurtunity to leverage SCEV's reasoning.  If we kept track of the min of dominanting exits so far, we could discharge exits with EC >= MDE.  This is less powerful than the existing transform (since later exits aren't considered), but potentially more powerful for any case where SCEV can prove a >= b, but neither a == b or a > b.  I don't have an example to illustrate that oppurtunity, but won't be suprised if we find one and return to handle that case as well.

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

llvm-svn: 375379
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
llvm/test/Transforms/IndVarSimplify/eliminate-exit.ll
llvm/test/Transforms/IndVarSimplify/loop-predication.ll
llvm/test/Transforms/IndVarSimplify/pr38674.ll