llvm dev - Apr 2009 - [LLVMdev] Strange loop unrolling problem (partially solved)

I am having a strange problem with loop unrolling. Attached is
a small example that demonstrates what happens.

There is a for-loop with a known trip count, and some control
flow inside the loop. If the condition of the control flow only
depends on the loop index and loop invariant variables, the loop
is not unrolled. However, if the condition involves potentially
loop variant variables, the loop does get unrolled.

The volatile variable assignments are there just to keep loop
body from disappearing completely. In the real case this
is derived from, the loop body contains some inline assembly.

The code within #ifdef MODIFY_V2 in the attached C code is in
fact dead code, as the condition of the if statement is never
true. However, including this dead code in the compilation
causes unrolling to take place.

Am I missing something or should I file a bug? I tried looking
around at LoopUnroll.cpp and UnrollLoop.cpp, but did not find
an immediate cause for this. From the debug output it looks like
instcombine is doing different things in the two cases.
-- 
Pertti
-------------- next part --------------
A non-text attachment was scrubbed...
Name: unroll.c
Type: text/x-csrc
Size: 380 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090422/70b9e70d/attachment.c>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Makefile
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090422/70b9e70d/attachment.ksh>

Pertti Kellomäki wrote:
> I am having a strange problem with loop unrolling.
Forgot to mention that this happens both with 2.5 and svn trunk.
-- 
Pertti

A short while ago I wrote about the strange loop unrolling
behavior we encountered. The problem was that with -O3,
the following loop does not get unrolled if the ifdef'ed
dead code is not present.

------------------------------------
extern volatile int v1;

int unroll() {
   int i;
   int v2 = 0;

   for(i = 0; i < 3; i++) {
     if (i == v2) { v1 = 1000;
     } else { v1 = 1001;
     }
#ifdef MODIFY_V2
     // Dead code
     if (i == 3) { v2 = v2 + 1; }
#endif
   }
   return v2;
}
-----------------------------------

It turns out that the reason unrolling does not work
in the simpler case is that some optimization pass figures
out that the `then' branch of the if is always executed, and
lifts it above the loop header. This confuses the loop trip
count code, and unrolling does not take place. The dead code
simply makes the optimization pass give up on the loop so
the structure is preserved.

Any ideas which pass does the lifting of the `then' branch?
I have my eyes no jump threading, but I don't understand the
loop transformations well enough yet to know if it simply
makes the problem manifest itself rather than creating it.

Unrolling is absolutely crucial for the application we have.
The loops that do not get unrolled are inner loops in a DSP
application, and unless we get big fat basic blocks, we don't
get much speedup from the VLIW-like machine we are targeting.
-- 
Pertti

Hi,
> Any ideas which pass does the lifting of the `then' branch?
if optimizing with "opt -std-compile-opts" shows this problem
then you can find the problematic pass using the following
method:
(1) run "opt -std-compile-opts -debug-pass=Arguments" to find
out which passes opt is running.
(2) run opt with that list of passes rather than -std-compile-opts.
(3) drop passes from the end of the list as long as the problematic
transform is still happening.  At some point the problem will
disappear when you drop a pass.  Then that pass is presumably
doing the transform.  A more sophisticated version of this is
to do bisection on the list of passes.

Ciao,

Duncan.

On Apr 27, 2009, at 5:26 AM, Pertti Kellomäki wrote:
> A short while ago I wrote about the strange loop unrolling
> behavior we encountered. The problem was that with -O3,
> the following loop does not get unrolled if the ifdef'ed
> dead code is not present.
Hi Pertti,

This is a major problem of the jump threading pass.  I've fixed it in  
r70820, thanks for bringing this up!

-Chris