[LLVMdev] Unnatural loops with O0

[Marc de Kruijf]

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

Many thanks,
Marc

On Sat, Jun 21, 2008 at 2:09 PM, Chris Lattner <sabre at nondot.org> wrote:

>
> 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
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090211/04af21ae/attachment.html>