[LLVMdev] Unnatural loops with O0

[Evan Cheng]

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