On Wed, Nov 24, 2010 at 12:37 PM, Nick Lewycky <nicholas at mxc.ca> wrote:> Xinliang David Li wrote: > >> Hi, I browsed the LLVM inliner implementation, and it seems there is >> room for improvement. (I have not read it too carefully, so correct me >> if what I observed is wrong). >> >> First the good side of the inliner -- the function level summary and >> inline cost estimation is more elaborate and complete than gcc. For >> instance, it considers callsite arguments and the effects of >> optimization enabled by inlining. >> >> Now more to the weakness of the inliner: >> >> 1) It is bottom up. The inlining is not done in the order based on the >> priority of the callsites. It may leave important callsites (at top of >> the cg) unlined due to higher cost after inline cost update. It also >> eliminates the possibility of inline specialization. To change this, the >> inliner pass may not use the pass manager infrastructure . (I noticed a >> hack in the inliner to workaround the problem -- for static functions >> avoid inlining its callees if it causes it to become too big ..) >> >> 2) There seems to be only one inliner pass. For calls to small >> functions, it is better to perform early inlining as one of the local >> (per function) optimizations followed by scalar opt clean up. This will >> sharpen the summary information. (Note the inline summary update does >> not consider the possible cleanup) >> > > Hi David, > > You're correct that there's only one inliner pass, but I don't understand > how an early inliner would help. In LLVM's case, after we inline one > function into another, we run the entire stack of per-function optimizations > on it before deciding whether to inline it into its caller. This sharpens > the summary information before the inliner looks at the next SCC, as we go > bottom up. Is there something more that early inlining would do for us that > isn't achieved with this model? >Interesting -- LLVM does perform on the fly cleanups during inlining transformation -- this will make summary update precise. One thing I notice from the debug pass dump is that the 'deduce function attribute' pass happens before the clean up -- Is it intended? Thanks, David> > (Actually, there is another inliner pass, but it's for > __attribute__((always_inline)) so it's rather uninteresting.) > > > 3) recursive inlining is not supported >> >> 4) function with indirect branch is not inlined. What source construct >> does indirect branch instr correspond to ? variable jump? >> > > Right. It's for "goto *ptr;". > > Nick > > 5) fudge factor prefers functions with vector instructions -- why is that? >> >> 6) There is one heuristc used in inline-cost computation seems wrong: >> >> >> // Calls usually take a long time, so they make the inlining gain >> smaller. >> InlineCost += CalleeFI->Metrics.NumCalls * InlineConstants::CallPenalty; >> >> Does it try to block inlining of callees with lots of calls? Note >> inlining such a function only increase static call counts. >> >> >> Thanks, >> >> David >> >> >> >> _______________________________________________ >> 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/20101124/f3b5cfab/attachment.html>
Hi David,> Interesting -- LLVM does perform on the fly cleanups during inlining > transformation -- this will make summary update precise. One thing I notice from > the debug pass dump is that the 'deduce function attribute' pass happens before > the clean up -- Is it intended?you are correct. This is due to a limitation of the pass manager: it would clearly be better to run the function attributes pass after the per-function passes that follow the inliner, but currently if you try what happens is that first the inliner and on the fly cleanups get run on every function, and only when they have finished the function attributes pass gets run on every function. That means that function attributes of callees will not have been calculated when the inliner (and the subsequent function passes) process a function, which is bad. I think the pass manager should be fixed to not do this, at which point the function attributes pass could be moved later. Ciao, Duncan.
On Mon, Nov 29, 2010 at 1:17 AM, Duncan Sands <baldrick at free.fr> wrote:> Hi David, > > > Interesting -- LLVM does perform on the fly cleanups during inlining > > transformation -- this will make summary update precise. One thing I > notice from > > the debug pass dump is that the 'deduce function attribute' pass happens > before > > the clean up -- Is it intended? > > you are correct. This is due to a limitation of the pass manager: it would > clearly be better to run the function attributes pass after the > per-function > passes that follow the inliner, but currently if you try what happens is > that > first the inliner and on the fly cleanups get run on every function, and > only > when they have finished the function attributes pass gets run on every > function. That means that function attributes of callees will not have > been > calculated when the inliner (and the subsequent function passes) process a > function, which is bad. I think the pass manager should be fixed to not do > this, at which point the function attributes pass could be moved later. >So bottom up traversal of the (scc node of) callgraph is not sufficient to guarantee all callees are processed before the caller? Thanks, David> > Ciao, > > Duncan. > _______________________________________________ > 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/20101129/9f452e5a/attachment.html>
On Nov 29, 2010, at 1:17 AM, Duncan Sands wrote:> Hi David, > >> Interesting -- LLVM does perform on the fly cleanups during inlining >> transformation -- this will make summary update precise. One thing I notice from >> the debug pass dump is that the 'deduce function attribute' pass happens before >> the clean up -- Is it intended? > > you are correct. This is due to a limitation of the pass manager: it would > clearly be better to run the function attributes pass after the per-function > passes that follow the inliner, but currently if you try what happens is that > first the inliner and on the fly cleanups get run on every function, and only > when they have finished the function attributes pass gets run on every > function. That means that function attributes of callees will not have been > calculated when the inliner (and the subsequent function passes) process a > function, which is bad. I think the pass manager should be fixed to not do > this, at which point the function attributes pass could be moved later.I am not sure I understand this. Here is what I am seeing when I run 'opt -inline -instcombine -functionattrs' Target Data Layout No Alias Analysis (always returns 'may' alias) ModulePass Manager Basic CallGraph Construction Call Graph SCC Pass Manager Function Integration/Inlining FunctionPass Manager Combine redundant instructions Basic CallGraph Construction Call Graph SCC Pass Manager Deduce function attributes FunctionPass Manager Preliminary module verification Dominator Tree Construction Module Verifier Is this not what you expect ? - Devang