[LLVMdev] Unnatural loops with O0

Florian Brandner
2008-06-11T13:27:15Z

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>