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.
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.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 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