Hi, the TOT llvm can't find the iteration count without tail duplication, I guess it's caused by the following code in ScalaEvoluation.cpp: // Currently we check for this by checking to see if the Exit branch goes to // the loop header. If so, we know it will always execute the same number of // times as the loop. More extensive analysis could be done to handle more // cases here. if (ExitBr->getSuccessor(0) != L->getHeader() && ExitBr->getSuccessor(1) != L->getHeader()) return UnknownValue; I need to disable tail duplication because it changes a while loop to a do- while loop by moving the exiting branch to the end of the loop body. I attached two files: (1) foo.bc : a simple loop without tail duplication (2) foo.taildup.bc: a simple loop with tail duplication. I ran "opt -indvar" on these two files, llvm failed to find trip count on the first example; but if I comment those three lines, it works fine and report the correct iteration count. Based on my understanding, those checking are not necessary since scalarevoluation works normally even the checking fails. Thanks.
Created attachment 551 [details] A simple loop without tail duplication.
Created attachment 552 [details] A simple loop with tail duplication.
This makes sense. The tail duplication pass does "loop rotation". This moves the exit condition from the top of the loop to the end of the loop, duplicating it so that the loop is not entered if the condition is false for the first iteration. For example: Before: Loop: if !condition goto Out loop body goto Loop Out: After: if !condition goto Out Loop: loop body if condition goto Loop Out: without this transformation, it is significantly harder to determine the trip count of the loop.
Also, specifically answering your question, it's not safe to disable those checks. Doing so makes the trip count be miscomputed for the case in bug 1015. Basically, we have to be sure the exit condition will be executed each time through the loop. In this specific case, it would also be safe to check to see if the loop exit block is the loop header. I'll investigate whether that fixes the issue in this case.
urg, due to recent bytecode format changes, I can't read your .bc files. Can you please attach a .ll file for the not tail duplicated case? Thanks, -Chris
I figured out my own testcase. Testcase here: Analysis/ScalarEvolution/trip-count.ll Patch here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070108/042645.html -Chris