ScalarEvolution can't find iteration count without tail duplication

[llvmbot]

Bugzilla Link	1101
Resolution	FIXED
Resolved on	Feb 22, 2010 12:46
Version	trunk
OS	All
Attachments	A simple loop without tail duplication., A simple loop with tail duplication.
Reporter	LLVM Bugzilla Contributor

Extended Description

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.

[lattner]

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.

[lattner]

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.

[lattner]

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

[lattner]

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