Unnatural loops with O0

Hello everybody,

we noticed that llvmgcc4.2-2.2 sometimes generates non-natural loops
when compiling to bytecode without any optimizations. Apparently what
happens is that the loop header is duplicated, which results in two
entry points for the loop. Since this could obstruct subsequent loop
optimizations, it might be interesting to further investigate this behavior.

To show the problem, I have included an example from libmad:

llvm-gcc -fdump-tree-all -O0 -I. -D_GNU_SOURCE -D__STDC_LIMIT_MACROS
-O0 -m32 -I/usr/include -c bit.c -o Output/bit.bc -emit-llvm

opt -print-cfg Output/bit.bc -o test.bc -f
dot -o test.ps -Tps cfg.mad_bit_crc.dot

In the CFG of mad_bit_crc(), the second while loop is entered from two
other basic blocks.

  From what I have seen, this does not happen in the front end. GCC does
transform the loop to a do-while, but does not duplicate the condition.

One work-around that I have found is to insert a label right before the
loop, s.t. LLVM is not allowed to duplicate the entry. However, it would
be great if there was some easier way to achieve this.

regards,
Adrian

bit-preprocessed.c.gz (5.86 KB)

this is actually a problem with the tailduplication pass of llvm. it does not
consider loops at all, and thus duplicates loop headers. the result is that
two paths now lead into the loop --> it is not natural anymore and further
loop optimizations fail.

besides, the tailduplication pass does not invalidate the loopinfo analysis,
as it should do in these cases.

i've attached a minimized version of adrians original testcase. you need to
adjust the tailduplication threshhold to trigger the tailduplication for this
example.

some more tests, using mibench (+some other benchmarks) with our llvm-2.1
based compiler, showed that in 29 benchmark programs 19 non-natural loops
appear - one single function contained 6 of them alone.

all but 5 of them could be avoided using a simple patch that disables tail
duplication of loop headers - 3 of them in one single function. the patch
applies and compiles with svn trunk, it also works for the small testcase,
but i did not run the testsuites.

florian

tailup-loop.c (149 Bytes)

taildup-loopheader.patch (2.09 KB)

we noticed that llvmgcc4.2-2.2 sometimes generates non-natural loops
when compiling to bytecode without any optimizations. Apparently what
happens is that the loop header is duplicated, which results in two
entry points for the loop.

this is actually a problem with the tailduplication pass of llvm. it does not
consider loops at all, and thus duplicates loop headers. the result is that
two paths now lead into the loop --> it is not natural anymore and further
loop optimizations fail.

We should not be running taildup at -O0. What do you see when you add -mllvm -debug-pass=Arguments?

besides, the tailduplication pass does not invalidate the loopinfo analysis,
as it should do in these cases.

+void TailDup::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<LoopInfo>();
+ AU.addPreserved<LoopInfo>();
+}

we noticed that llvmgcc4.2-2.2 sometimes generates non-natural loops
when compiling to bytecode without any optimizations. Apparently what
happens is that the loop header is duplicated, which results in two
entry points for the loop.

this is actually a problem with the tailduplication pass of llvm. it does not
consider loops at all, and thus duplicates loop headers. the result is that
two paths now lead into the loop --> it is not natural anymore and further
loop optimizations fail.

I think the patch was reverted because using loopinfo is bad for taildup to do. The best answer is to actually just remove the tail dup pass altogether. It is really bad for compile time performance, and has some other issues. A second best solution is to change it to do a quick depth first search of the CFG when it starts analyzing a function and just keep a SmallPtrSet of loop headers.

-Chris

I am reviving this thread because I am seeing the same thing (unnatural loops produced by llvm-gcc), but it is not limited to -O0 – I am seeing it for -O2 and -O3 as well.
Some of my research work is relying on LoopInfo to provide loop information for all loops, but it is missing these loops. Is there any work in the pipeline that aims to fix this?

Many thanks,
Marc

Not that I know of. There has been a project on the open projects list to write a pass that converts all loops to natural loops (through code duplication). That would be a nice and self-contained project if anyone is interested.

-Chris

Hi Chris,

Is there a compelling reason why llvm-gcc does not always produce natural loops. Is it a code size issue, or are there performance implications as well? I am seeing a simple ‘while’ loop compiled to an unnatural loop, without any gotos, breaks, or continues. What is the reason for this?

Marc

Hi Marc,

Is there a compelling reason why llvm-gcc does not always produce natural
loops. Is it a code size issue, or are there performance implications as
well? I am seeing a simple 'while' loop compiled to an unnatural loop,
without any gotos, breaks, or continues. What is the reason for this?

is it already an unnatural loop when it comes out of the gcc parts of
llvm-gcc (you can check this by compiling with: -O0 -emit-llvm)? Or
is it llvm itself that creates the unnatural loops?

Ciao,

Duncan.

Right. There is little we can do about the -O0 -emit-llvm code: this is a literal translation of what the GCC front-end gives us. If some *optimizer* is turning reducible loops into non-reducible control flow, then that is a completely different matter and I would consider that to be a serious bug.

If the gcc front-end is doing this to you, you can try out clang, which should not.

-Chris