[SCEV] More accurate calculation of max backedge count of some less-than loops
authorJohn Brawn <john.brawn@arm.com>
Tue, 18 Oct 2016 10:10:53 +0000 (10:10 +0000)
committerJohn Brawn <john.brawn@arm.com>
Tue, 18 Oct 2016 10:10:53 +0000 (10:10 +0000)
commitecf79300dd78b561f138c5d543b6d27d9ab766de
tree9e563897a1008479faf0fce176dcc66aed92cc09
parent692f4e95cf0ab7c58cbac2e5f12fbc4e87e07ea7
[SCEV] More accurate calculation of max backedge count of some less-than loops

In loops that look something like
 i = n;
 do {
  ...
 } while(i++ < n+k);
where k is a constant, the maximum backedge count is k (in fact the backedge
count will be either 0 or k, depending on whether n+k wraps). More generally
for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will
iterate either 0 or that constant number of times.

This allows for more loop unrolling with the recent upper bound loop unrolling
changes, and I'm working on a patch that will let loop unrolling additionally
make use of the loop being executed either 0 or k times (we need to retain the
loop comparison only on the first unrolled iteration).

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

llvm-svn: 284465
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/trip-count13.ll
llvm/test/Analysis/ScalarEvolution/trip-count14.ll [new file with mode: 0644]