[LLVMdev] Unnatural loops with O0

[Florian Brandner]

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. 

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
	
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tailup-loop.c
Type: text/x-csrc
Size: 149 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080611/43841b2a/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: taildup-loopheader.patch
Type: text/x-diff
Size: 2139 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080611/43841b2a/attachment.patch>