I am reviving this thread because I am seeing the same thing (unnatural loops produced by llvm-gcc), but it is not limited to -O0 -- I am seeing it for -O2 and -O3 as well.<br>Some of my research work is relying on LoopInfo to provide loop information for all loops, but it is missing these loops.  Is there any work in the pipeline that aims to fix this?<br>
<br>Many thanks,<br>Marc<br><br><div class="gmail_quote">On Sat, Jun 21, 2008 at 2:09 PM, Chris Lattner <span dir="ltr"><<a href="mailto:sabre@nondot.org">sabre@nondot.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d"><br>
On Jun 11, 2008, at 6:27 AM, Florian Brandner wrote:<br>
<br>
</div><div class="Ih2E3d">> On Thursday 08 May 2008 18:33:48 Adrian Prantl wrote:<br>
>> we noticed that llvmgcc4.2-2.2 sometimes generates non-natural loops<br>
>> when compiling to bytecode without any optimizations. Apparently what<br>
>> happens is that the loop header is duplicated, which results in two<br>
>> entry points for the loop.<br>
><br>
> this is actually a problem with the tailduplication pass of llvm. it<br>
> does not<br>
> consider loops at all, and thus duplicates loop headers. the result<br>
> is that<br>
> two paths now lead into the loop --> it is not natural anymore and<br>
> further<br>
> loop optimizations fail.<br>
<br>
</div>I think the patch was reverted because using loopinfo is bad for<br>
taildup to do.  The best answer is to actually just remove the tail<br>
dup pass altogether.  It is really bad for compile time performance,<br>
and has some other issues.  A second best solution is to change it to<br>
do a quick depth first search of the CFG when it starts analyzing a<br>
function and just keep a SmallPtrSet of loop headers.<br>
<font color="#888888"><br>
-Chris<br>
</font><div><div></div><div class="Wj3C7c"><br>
><br>
><br>
> besides, the tailduplication pass does not invalidate the loopinfo<br>
> analysis,<br>
> as it should do in these cases.<br>
><br>
> i've attached a minimized version of adrians original testcase. you<br>
> need to<br>
> adjust the tailduplication threshhold to trigger the tailduplication<br>
> for this<br>
> example.<br>
><br>
> some more tests, using mibench (+some other benchmarks) with our<br>
> llvm-2.1<br>
> based compiler, showed that in 29 benchmark programs 19 non-natural<br>
> loops<br>
> appear - one single function contained 6 of them alone.<br>
><br>
> all but 5 of them could be avoided using a simple patch that<br>
> disables tail<br>
> duplication of loop headers - 3 of them in one single function. the<br>
> patch<br>
> applies and compiles with svn trunk, it also works for the small<br>
> testcase,<br>
> but i did not run the testsuites.<br>
><br>
> florian<br>
><br>
> --<br>
> Brandner Florian<br>
><br>
> CD Laboratory - Compilation Techniques for Embedded Processors<br>
> Institut für Computersprachen E185/1<br>
> Technische Universität Wien<br>
><br>
> Argentinierstraße 8 / 185<br>
> A-1040 Wien, Austria<br>
><br>
> Tel.: (+431) 58801-58521<br>
><br>
> E-Mail: <a href="mailto:brandner@complang.tuwien.ac.at">brandner@complang.tuwien.ac.at</a><br>
><br>
</div></div><div><div></div><div class="Wj3C7c">> <tailup-loop.c><taildup-<br>
> loopheader.patch>_______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div></div></blockquote></div><br>