Hi, I'm using pass ScalarEvolution to analyze the loop trip count on my application. And I found a possible bug in the code, that is in function SCEVAddRecExpr::getNumIterationsInRange(), Line 2905: 2904 // The exit value should be (End+A)/A. 2905 APInt ExitVal = (End + A).udiv(A); 2906 ConstantInt *ExitValue = ConstantInt::get(ExitVal); The divide should be sdiv, right? otherwise, the ExitVal will be zero when A = -1 For example, for (int i = 15; i > 7; --i) {} the exit value should be 7 not zero. Also, I think we should consider the possible overflow situation, for example, for (uint7 i = 0; i < 64; i += 2) {} The Range should be [0, 64) (type i7), so End = 63, A = 2, (End + A).sdiv(A) will be 97 instead of 32. This is due to overflow of the addition of End and A. They both are positive value, and the result should be 65 which in i7 type may be negative. Any comments? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081112/d951f057/attachment.html>
On Nov 12, 2008, at 1:30 AM, Zhou Sheng wrote:> Hi, > > I'm using pass ScalarEvolution to analyze the loop trip count on my > application. > And I found a possible bug in the code, that is in function > SCEVAddRecExpr::getNumIterationsInRange(), > Line 2905: > > 2904 // The exit value should be (End+A)/A. > 2905 APInt ExitVal = (End + A).udiv(A); > 2906 ConstantInt *ExitValue = ConstantInt::get(ExitVal); > > The divide should be sdiv, right? otherwise, the ExitVal will be > zero when A = -1 > > For example, for (int i = 15; i > 7; --i) {} the exit value > should be 7 not zero.The code immediately after the code you pasted above checks to see if the result value is out of range. In the case of your example code, the value is out of range, and ScalarEvolution falls back to a different algorithm for computing the exit value. Do you have an example where it ScalarEvolution computes the wrong exit value, or a specific case you're interested in where it misses an opportunity to compute an exit value? Dan
Seemingly Similar Threads
- [LLVMdev] Scalar Evolution and Loop Trip Count.
- [LLVMdev] scalar-evolution + indvars fail to get the loop trip count?
- [LLVMdev] scalar-evolution + indvars fail to get the loop trip count?
- [IndVars] Rewriting exit value of SCEV add expressions
- [RFC] New pass: LoopExitValues