[LLVMdev] Unnatural loops with O0

Evan Cheng
2008-06-11T19:03:53Z

On Jun 11, 2008, at 6:27 AM, Florian Brandner wrote:

> On Thursday 08 May 2008 18:33:48 Adrian Prantl wrote:
>> 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>();
+}
+

It doesn't seem safe to say taildup preserves loopinfo even after your
patch. Taildup is modifying the CFG.

>
>
> 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.

Thanks. I'll commit your patch.

Evan

>
>
> florian
>
> --
> Brandner Florian
>
> CD Laboratory - Compilation Techniques for Embedded Processors
> Institut für Computersprachen E185/1
> Technische Universität Wien
>
> Argentinierstraße 8 / 185
> A-1040 Wien, Austria
>
> Tel.: (+431) 58801-58521
>
> E-Mail: brandner at complang.tuwien.ac.at
>
> <tailup-loop.c><taildup-
> loopheader.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev