[LoopDeletion] Use max trip count to break backedge in addition to exact one
authorPhilip Reames <listmail@philipreames.com>
Fri, 27 Aug 2021 21:18:38 +0000 (14:18 -0700)
committerPhilip Reames <listmail@philipreames.com>
Fri, 27 Aug 2021 21:19:44 +0000 (14:19 -0700)
commitc7b25e4359962f69890345aaf1b3aa4e440fbda7
treeb9be87c87fd8bbe078f54ea268fda2118b076113
parent9632ce14e4145187b5fe404bc45f092392fd4346
[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the exact trip count which requires *all* exits be analyzeable. I noticed while writing test cases for another patch that this disallows cases where one exit is provably taken paired with another which is unknown. This patch adds the upper bound case.

We could use a symbolic max trip count here instead, but we use an isKnownNonZero filter (presumably for compile time?) for the first-iteration reasoning. I decided this was a more obvious incremental step, and we could go back and untangle the schemes separately.

Differential Revision: https://reviews.llvm.org/D108833
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
llvm/test/Transforms/LoopDeletion/switch.ll
llvm/test/Transforms/LoopDeletion/zero-btc.ll