Hello everybody, 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. Since this could obstruct subsequent loop optimizations, it might be interesting to further investigate this behavior. To show the problem, I have included an example from libmad: llvm-gcc -fdump-tree-all -O0 -I. -D_GNU_SOURCE -D__STDC_LIMIT_MACROS -O0 -m32 -I/usr/include -c bit.c -o Output/bit.bc -emit-llvm opt -print-cfg Output/bit.bc -o test.bc -f dot -o test.ps -Tps cfg.mad_bit_crc.dot In the CFG of mad_bit_crc(), the second while loop is entered from two other basic blocks. From what I have seen, this does not happen in the front end. GCC does transform the loop to a do-while, but does not duplicate the condition. One work-around that I have found is to insert a label right before the loop, s.t. LLVM is not allowed to duplicate the entry. However, it would be great if there was some easier way to achieve this. regards, Adrian -------------- next part -------------- A non-text attachment was scrubbed... Name: bit-preprocessed.c.gz Type: application/x-gzip Size: 6003 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080508/80af7cd5/attachment.bin>
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>
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.We should not be running taildup at -O0. What do you see when you add - mllvm -debug-pass=Arguments?> > > besides, the tailduplication pass does not invalidate the loopinfo > analysis, > as it should do in these cases.+void TailDup::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<LoopInfo>(); + AU.addPreserved<LoopInfo>(); +} + It doesn't seem safe to say taildup preserves loopinfo even after your patch. Taildup is modifying the CFG.> > > 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.Thanks. I'll commit your patch. Evan> > > 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
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