Add the ability to compute trip counts that are only controlled by constants
authorChris Lattner <sabre@nondot.org>
Sat, 17 Apr 2004 18:36:24 +0000 (18:36 +0000)
committerChris Lattner <sabre@nondot.org>
Sat, 17 Apr 2004 18:36:24 +0000 (18:36 +0000)
commit7980fb9007b7e13446053daa6a5110aeeb7016dd
treeba94f169a8246aef1107201216c7e18163fdbdbe
parent4f1134e51ae293536843dcd7fa1147acdc39dec7
Add the ability to compute trip counts that are only controlled by constants
even if the loop is using expressions that we can't compute as a closed-form.
This allows us to calculate that this function always returns 55:

int test() {
  double X;
  int Count = 0;
  for (X = 100; X > 1; X = sqrt(X), ++Count)
    /*empty*/;
  return Count;
}

And allows us to compute trip counts for loops like:

        int h = 1;
         do h = 3 * h + 1; while (h <= 256);

(which occurs in bzip2), and for this function, which occurs after inlining
and other optimizations:

int popcount()
{
   int x = 666;
  int result = 0;
  while (x != 0) {
    result = result + (x & 0x1);
    x = x >> 1;
  }
  return result;
}

We still cannot compute the exit values of result or h in the two loops above,
which means we cannot delete the loop, but we are getting closer.  Being able to
compute a constant trip count for these two loops will allow us to unroll them
completely though.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13017 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Analysis/ScalarEvolution.cpp