ScalarEvolution: Compute exit counts for loops with a power-of-2 step.
authorBenjamin Kramer <benny.kra@googlemail.com>
Tue, 25 Mar 2014 16:25:12 +0000 (16:25 +0000)
committerBenjamin Kramer <benny.kra@googlemail.com>
Tue, 25 Mar 2014 16:25:12 +0000 (16:25 +0000)
commitc1c74fb2b4ae2bce68ff1587e3022a158297d936
treeb53b807d49d8b158c78f907738a6689f8c64811a
parent71a8d2baba951ad99baadd46f7738b9229fda91f
ScalarEvolution: Compute exit counts for loops with a power-of-2 step.

If we have a loop of the form
for (unsigned n = 0; n != (k & -32); n += 32) {}
then we know that n is always divisible by 32 and the loop must
terminate. Even if we have a condition where the loop counter will
overflow it'll always hold this invariant.

PR19183. Our loop vectorizer creates this pattern and it's also
occasionally formed by loop counters derived from pointers.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@204728 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Analysis/ScalarEvolution.cpp
test/Analysis/ScalarEvolution/trip-count-pow2.ll [new file with mode: 0644]