Detecting counted loops

I need to be able to detect a well-behaved loop. (i.e one where exp1
assigns a value to an int i, exp2 compares i with a loop constant,
exp3 adjusts i by a loop constant, and the inner block has no
assignments to i.)

I need this because in Sun's Java VM garbage collection only takes
place at safepoints, so a potentially unbounded loop must call
safepoint() some time. However, safepoints are potentially very
costly, so we don't want to have them except where it is absolutely
necessary. Any loop that is known to be of finite duration does not
need to call safepoint().

I presume that LLVM can fairly easily find well-behaved loops in order
for it to do loop optimizations. I don't want to have to do the
analysis in my front-end if I can possibly avoid it. Is there some
logic in LLVM that I can call which will tell me where well-behaved
loops are? Or, perhaps, I might have to write a special-purpose
optimization pass to do this.

Thanks,
Andrew.

Hi Andrew,

Check out the LoopInfo pass and the ScalarEvolution code in include/llvm/Analysis. ScalarEvolution::getIterationCount is probably what you want.

-Chris

The ScalarEvolution analysis pass has what you need here.

In LLVM 2.5 and earlier, this was done with methods named
hasLoopInvariantIterationCount and getIterationCount. In
trunk, these have been renamed to
hasLoopInvariantBackedgeTakenCount and
getBackedgeTakenCount to more accurately describe the
value returned, for clients that care about the actual value.
In either case, if the returned value is not a
SCEVCouldNotCompute (you can use isa on a SCEVHandle
value directly), then the loop has a finite iteration count.

Dan