search for: tarjan

...ved us to > the algorithm found in http://www.cs.rice.edu/~keith/Embed/dom.pdf, > Figure 5, it was ~30% faster (AFAIK, Jeanne Ferrante is somewhat > responsible for both algorithms :P). It is also a lot simpler to > explain, IMHO. There is a followup paper from other authors (including Tarjan himself) that discusses some implementation tricks for the Lengauer-Tarjan algorithm: http://www.cs.princeton.edu/~rwerneck/docs/GWTTA04.pdf They cite personal communication from Keith Cooper that a later more careful implementation of Lengauer-Tarjan led to different benchmark results than what...

On Fri, Jan 6, 2012 at 8:17 PM, Chris Lattner <clattner at apple.com> wrote: > > On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: > >>>> >>>> It's very like SSA construction, but must make provision >>>> testing anti dependences.  I had planned to use dominance frontiers to >>>> guide placement of phi nodes, as usual. >>>

Dear LLVM, Recently I incorporated code into my project such that function pointers were supported, however it seems that the TarjanSCC_iterator no longer works on the call graph... main() is no longer reached while the function pointers are... I can provide code, but I have a feeling there is a simple fix... Has anyone gone through this? Thanks, Dave

> Recently I incorporated code into my project such that function pointers > were supported, however it seems that the TarjanSCC_iterator no longer > works on the call graph... main() is no longer reached while the function > pointers are... I can provide code, but I have a feeling there is a > simple fix... Has anyone gone through this? I'll need some more details before I can help. I assume this has to...

...hree Which doesn't visit main. Vikram, could you look into this if you get a chance? -Chris ------------------- Pass code ---------------------------- #include "llvm/Analysis/CallGraph.h" #include "llvm/Function.h" #include "llvm/Pass.h" #include "Support/TarjanSCCIterator.h" struct Test : public Pass { virtual bool run(Module &F) { typedef TarjanSCC_iterator<CallGraph*> MyTarjan; CallGraph& callGraph = getAnalysis<CallGraph>(); for (MyTarjan I = tarj_begin(&callGraph), E = tarj_end(&callGraph); I != E; ++I)...

...you look into this if you get a > chance? > > -Chris > > ------------------- Pass code ---------------------------- > > #include "llvm/Analysis/CallGraph.h" > #include "llvm/Function.h" > #include "llvm/Pass.h" > #include "Support/TarjanSCCIterator.h" > > struct Test : public Pass { > virtual bool run(Module &F) { > typedef TarjanSCC_iterator<CallGraph*> MyTarjan; > CallGraph& callGraph = getAnalysis<CallGraph>(); > for (MyTarjan I = tarj_begin(&callGraph), E = tarj_end(...

Test Cases: (attached) Iteration code: (...) typedef TarjanSCC_iterator<CallGraph*> MyTarjan; CallGraph& callGraph = getAnalysis<CallGraph>(); MyTarjan iter = tarj_begin(&callGraph); MyTarjan end = tarj_end(&callGraph); while(iter!=end) iter++; (...) if you take the time to print out the function each non-looping node iter...

...the algorithm found in http://www.cs.rice.edu/~keith/Embed/dom.pdf, > Figure 5, it was ~30% faster (AFAIK, Jeanne Ferrante is somewhat > responsible for both algorithms :P). It is also a lot simpler to > explain, IMHO. > > > There is a followup paper from other authors (including Tarjan himself) that > discusses some implementation tricks for the Lengauer-Tarjan algorithm: Ah, i was referring to the *dominance frontier* computation, not the dominator computation. If you look, you'll see there is an algorithm in the paper that computes dominance frontiers touching only the...

...;b->c, with no edge > back to a). The inliner had already visited a, b, and c as a single > SCC. Now does it have to re-visit c, then b, then a, as single-node > SCC's? > btw: > One way that I have found it useful to think about this is in terms > of the visitation during Tarjan's SCC algorithm. I'll reference the > pseudocode in > https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm > . Inside the "strongconnect" routine when we have identified an SCC > (the true branch of `if (v.lowlink = v.index)` test ) we can v...

...t;a) into a path graph (a->b->c, with no edge back to a). The inliner had already visited a, b, and c as a single SCC. Now does it have to re-visit c, then b, then a, as single-node SCC's? btw: One way that I have found it useful to think about this is in terms of the visitation during Tarjan's SCC algorithm. I'll reference the pseudocode in https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm. Inside the "strongconnect" routine when we have identified an SCC (the true branch of `if (v.lowlink = v.index)` test ) we can visit stack[v.index:st...

...->b->c, with no edge back to a). The inliner had already visited a, b, and c as a single SCC. Now does it have to re-visit c, then b, then a, as single-node SCC's? > > > btw: > > One way that I have found it useful to think about this is in terms of the visitation during Tarjan's SCC algorithm. I'll reference the pseudocode in https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm <https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm>. Inside the "strongconnect" routine when we have identified a...

.... The inliner had already visited a, b, and c as a single SCC. Now does it have to re-visit c, then b, then a, as single-node SCC's? >>> >>> >>> btw: >>> >>> One way that I have found it useful to think about this is in terms of the visitation during Tarjan's SCC algorithm. I'll reference the pseudocode in https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm. Inside the "strongconnect" routine when we have identified an SCC (the true branch of `if (v.lowlink<http://v.lowlink> = v.index<http://v.in...

...gt;> inliner had already visited a, b, and c as a single SCC. Now does it have >> to re-visit c, then b, then a, as single-node SCC's? >> >> >> btw: >> >> One way that I have found it useful to think about this is in terms of >> the visitation during Tarjan's SCC algorithm. I'll reference the pseudocode >> in >> https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm. >> Inside the "strongconnect" routine when we have identified an SCC (the true >> branch of `if (v.lowlink = v.index)`...

...gle SCC. Now does it have >>>> to re-visit c, then b, then a, as single-node SCC's? >>>> >>>> >>>> btw: >>>> >>>> One way that I have found it useful to think about this is in terms of >>>> the visitation during Tarjan's SCC algorithm. I'll reference the pseudocode >>>> in >>>> https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm. >>>> Inside the "strongconnect" routine when we have identified an SCC (the true >>>> branc...

...td::vector<GlobalValue*> funcVect = theGraph.getNodeForValue(calli->getCalledFunction()).getNode()->getGlobals(); Doesn't appear to work... getCalledFunction() returns 0 Dave On Fri, 6 Dec 2002, Vikram Adve wrote: > P.S. I have also updated the CSIL tree. Just check out > TarjanSCCIterator.h. > > --Vikram > http://www.cs.uiuc.edu/~vadve > > > > From: David Crowe <dcrowe at tremor.crhc.uiuc.edu> > > Subject: [LLVMbugs] Re: [LLVMdev] Tarjan+function_ptrs == trouble ? > > Sender: llvmbugs-admin at cs.uiuc.edu > > Date: Fri, 6 De...

I found the chapters in Engineering a Compiler (Cooper and Torczon) perfectly match the code generator of LLVM. And this paper: Lengauer and Tarjan, A Fast Algorithm for Finding Dominators in a Flowgraph, ACM TOPLAS, Vol 1 , No.1, July 1979 I also would like to know more papers/books whose algorithms are implemented in LLVM. 在 星期二 19 十二月 2006 22:13，Fredrik Svensson 写道： > Hi, > > As Christmas approaches rapidly I would like to get so...

...le Doc <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing> if you prefer so. Please let us know what you think. ~Kuba ======================================================================= *1. Context* Currently LLVM uses the Simple Lengauer-Tarjan algorithm to build the (post)dominator tree. The only way to update it is by manually setting IDoms which is not obvious in many cases and can be extremely error-prone. And because updating it manually is so difficult, programmers tend to just recompute it after changing the CFG (by not AU.addPrese...

...ving the DominatorTree and PostDominatorTree in LLVM. The RFC that explains the motivations and plans can be found here: http://lists.llvm.org/pipermail/llvm-dev/2017-June/114045.html . Here’s a short summary of what changed upstream since posting it: - We switched from the Simple Lengauer-Tarjan algorithm for computing dominators to Semi-NCA, which is a bit faster in most cases. Although it is possible to construct a CFG that triggers the pathological quadratic complexity of Semi-NCA, we weren’t able to observe it in practice. - DomTreeNodes now automatically store their le...

...gt;>>> re-visit c, then b, then a, as single-node SCC's? > >>>> > >>>> > >>>> btw: > >>>> > >>>> One way that I have found it useful to think about this is in terms of > >>>> the visitation during Tarjan's SCC algorithm. I'll reference the > pseudocode > >>>> in > >>>> > https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm > . > >>>> Inside the "strongconnect" routine when we have identified an SCC &...

...%i.0, 1 br label %bb6 bb6: %i.0 = phi i32 [ 0, %entry ], [ %20, %bb5 ] There is a data flow loop between %20 and %i.0. The OSR paper has a nice figure showing data flow loops. Here is small excerpt from the OSR paper: "OSR is driven by a simple depth-first search of the SSA-graph, using Tarjan’s strongly-connected component finder. The SCC-finder lets OSR discover induction variables in topological order and process them as they are discovered. As the SCCs are discovered, they are processed by a set of mutually-recursive routines that test for induction variables and region constants...