llvm dev - Jul 2010 - [LLVMdev] Fail to unroll loop on simple examples.

Hi all,

I have tried to use the loop-unroll pass on a large example, but without
success. So I have tried on smaller examples, and I did not get more
success.

My simplest example is attached. It comes from this C code (using llvm-gcc,
but similar result with clang):

int main (int argc, char *argv[]) {
  int i;
  for (i = 0; i!=5; ++i) {}
  return 0;
}

I use this command (version 2.8svn, from July 1st)
~/Build/llvm-trunk/Release/bin/opt -mem2reg -indvars -loop-unroll -stats
loop.ll | llvm-dis

Whereas ScalarEvolution can compute the loop count, LoopInfo fails because
the conditional branch is not in the expected block. If I provide the loop
count with -unroll-count=5, then the function UnrollLoop fails form the same
reason. The pass "-loopsimplify" has no effect.

If I add the pass "-loop-rotate" before "-indvars", then the
loop is
successfully unrolled. However, I think this pass may increase the size of
the code for all loops, including the loops that cannot be unrolled.

Is this a bug? Or is there any other pass that can help UnrollLoop?


-- 
Claude Helmstetter
+86 186 0895 4884 / +33 6 32 99 06 00
http://formes.asia/people/Claude.Helmstetter/
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100701/ca0cf370/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loop.ll
Type: application/octet-stream
Size: 920 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100701/ca0cf370/attachment.obj>

[I am a newcomer to llvm, so don't believe me.]

Hi Claude, 

I added -debug to the command line in an attempt to study your example, and got
out this:

Loop Unroll: F[main] Loop %bb1
  Loop Size = 4
  Can't unroll; loop not terminated by a conditional branch.

The source code for that is on line 116 (or so) in
lib/Transforms/Utils/LoopUnroll.cpp

Based on a quick look at the source code, this looks like a bug in LLVM to me,
e.g. perhaps the test is applied on a wrong block?  But more probably I am just
missing something.

--Pekka Nikander

On 2010-07 -01, at 13:48 , Claude Helmstetter wrote:
> Hi all,
> 
> I have tried to use the loop-unroll pass on a large example, but without
success. So I have tried on smaller examples, and I did not get more success.
> 
> My simplest example is attached. It comes from this C code (using llvm-gcc,
but similar result with clang):
> 
> int main (int argc, char *argv[]) {
>   int i;
>   for (i = 0; i!=5; ++i) {}
>   return 0;
> }
> 
> I use this command (version 2.8svn, from July 1st)
> ~/Build/llvm-trunk/Release/bin/opt -mem2reg -indvars -loop-unroll -stats
loop.ll | llvm-dis
> 
> Whereas ScalarEvolution can compute the loop count, LoopInfo fails because
the conditional branch is not in the expected block. If I provide the loop count
with -unroll-count=5, then the function UnrollLoop fails form the same reason.
The pass "-loopsimplify" has no effect.
> 
> If I add the pass "-loop-rotate" before "-indvars",
then the loop is successfully unrolled. However, I think this pass may increase
the size of the code for all loops, including the loops that cannot be unrolled.
> 
> Is this a bug? Or is there any other pass that can help UnrollLoop?
> 
> 
> -- 
> Claude Helmstetter
> +86 186 0895 4884 / +33 6 32 99 06 00
> http://formes.asia/people/Claude.Helmstetter/
> 
> <loop.ll>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Thu, Jul 1, 2010 at 12:33 PM, Pekka Nikander
<pekka.nikander at nomadiclab.com> wrote:
> [I am a newcomer to llvm, so don't believe me.]
>
> Hi Claude,
>
> I added -debug to the command line in an attempt to study your example, and
got out this:
>
> Loop Unroll: F[main] Loop %bb1
>  Loop Size = 4
>  Can't unroll; loop not terminated by a conditional branch.
>
> The source code for that is on line 116 (or so) in
lib/Transforms/Utils/LoopUnroll.cpp
>
> Based on a quick look at the source code, this looks like a bug in LLVM to
me, e.g. perhaps the test is applied on a wrong block?  But more probably I am
just missing something.
Missed optimization... the loop unroller needs work to work on more
than extremely simple loops.

-Eli