[LLVMdev] Unnatural loops with O0

[Chris Lattner]

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.

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

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