[LLVMdev] Detecting counted loops

[Dan Gohman]

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

On Feb 24, 2009, at 8:46 AM, Andrew Haley wrote:

> 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.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev