search for: ferrante

...random aside, the algorithm given in the original paper you cited is actually not quite the best way in practice. It performs more comparisons than strictly necessary. When I moved 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. Both of these things happened around 2005 (local SSA updating in GCC and replacement of the dominance frontier algorithm), so things may be different now.

...I could not figure out a way to determine if the dummy entry node is a member of the post-dominance frontier of a basic block. Is there a way to get that information? Regards, Ryan * "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Cytron, Ferrante, Rosen, Wegman, and Zadeck -- Ryan M. Lefever [http://www.ews.uiuc.edu/~lefever]

...gorithm given in the original > paper you cited is actually not quite the best way in practice. It > performs more comparisons than strictly necessary. When I moved 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/GWT...

...gorithm given in the original > paper you cited is actually not quite the best way in practice.  It > performs more comparisons than strictly necessary. When I moved 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: Ah, i was referring to the...

On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org> wrote: > Is there a reason this is better than the modified algorithm created > by Ferrante? > It looks like yours has as bad a worst case time bound in reality. > That is, the algorithm runs in O(sum of the size of all the dominance > frontiers). > > http://www.cs.rice.edu/~keith/Embed/dom.pdf > > See figure 5. It will only touch nodes actually in the dominance front...

Is there a reason this is better than the modified algorithm created by Ferrante? It looks like yours has as bad a worst case time bound in reality. That is, the algorithm runs in O(sum of the size of all the dominance frontiers). http://www.cs.rice.edu/~keith/Embed/dom.pdf See figure 5. It will only touch nodes actually in the dominance frontier. This is what GCC uses. The...

...e/exit nodes. LLVM functions always have a single entry node (the first BB in the function) and multiple exits are handled specially. -Chris > Regards, > Ryan > > > * "Efficiently Computing Static Single Assignment Form and the Control > Dependence Graph" by Cytron, Ferrante, Rosen, Wegman, and Zadeck > > -Chris -- http://nondot.org/sabre/ http://llvm.org/

...ted case. Number all the basic blocks, 0 to n-1 and build a vector mapping from integer to block. Requires O(n) time and space. For each block, compute the set containing it's dominance frontier, based on Figure 10 of * * *Efficiently Computing Static Single Assignment Form and ...* Cytron, Ferrante, Rosen, Wegman During the calculation, represent the current frontier, DF(X), as suggested in *An Efficient Representation for Sparse Sets* Briggs, Torczon This lets us add members and clear the set in constant time and allows us to enumerate the members in time proportional to the number of m...

Hi, Diego, Thanks for your quick reply. Inserting a copy instruction may not work here because I have a limitation of virtual register number. I need to assign registers with ssa form to registers without ssa form. I will look the source code you point out. Thanks Xiangyang On Fri, Apr 24, 2015 at 4:19 PM, Diego Novillo <dnovillo at google.com> wrote: > > > On Fri, Apr 24, 2015

Hi Arsen, I wrote a pass that computes a control dependence graph as described in Ferrante et al's "The Program Dependence Graph and Its Use in Optimization." It is available at https://github.com/thinkmoore/llvm-analysis. Cheers, Scott On Fri, Apr 12, 2013 at 5:04 PM, John Criswell <criswell at illinois.edu>wrote: > On 4/12/13 3:19 PM, Arsen wrote: > >&gt...

...ll the basic blocks, 0 to n-1 and build a vector mapping from integer to block. Requires O(n) time and space. > > For each block, compute the set containing it's dominance frontier, based on Figure 10 of > > Efficiently Computing Static Single Assignment Form and ... > Cytron, Ferrante, Rosen, Wegman > > During the calculation, represent the current frontier, DF(X), as suggested in > > An Efficient Representation for Sparse Sets > Briggs, Torczon > > This lets us add members and clear the set in constant time and allows us to enumerate the members in time...

On 4/12/13 3:19 PM, Arsen wrote: > Thank you John. > Actually the opt tool (from LLVM 3.2 version) can generate the needed graphs > (with pass "-domfrontier"). > But I just want to surely know is there some pass or builder which can be > integrated somehow so it will be possible directly to generate CDG? Yes and no. There's isn't a control dependence pass in LLVM

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. >> >> Ok, in that case, please check out include/llvm/Transforms/Utils/SSAUpdater.h, >> which is the

On Dec 23, 2011, at 1:35 PM, Preston Briggs wrote: > Reading the comments in Analysis/DominanceFrontier.h, I see a note that the structure is deprecated and we're not to use it for anything new. > > Has it been replaced with something equally useful, or shall I redo the calculation for myself, or ...? We're hoping to remove them, because they're inherently an N^2 data

Thank you John. Actually the opt tool (from LLVM 3.2 version) can generate the needed graphs (with pass "-domfrontier"). But I just want to surely know is there some pass or builder which can be integrated somehow so it will be possible directly to generate CDG? -- View this message in context: http://llvm.1065342.n5.nabble.com/Control-Dependence-Graph-builder-tp56687p56689.html Sent

...e analysis that you have implemented in the backends? At Argonne one of the application specific analyses we need to perform, activity analysis, has a forward and backward dataflow analysis component. Thanks, Michelle @inproceedings{Choi91, Author = {Jong-Deok Choi and Ron Cytron and Jeanne Ferrante}, Booktitle = {Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, Location = {Orlando, Florida, United States}, Pages = {55--66}, Publisher = {ACM Press}, Title = {Automatic construction of sparse data flow evaluation graphs}, Year = {1991}} @inpro...

Reading the comments in Analysis/DominanceFrontier.h, I see a note that the structure is deprecated and we're not to use it for anything new. Has it been replaced with something equally useful, or shall I redo the calculation for myself, or ...? Thanks, Preston -------------- next part -------------- An HTML attachment was scrubbed... URL:

Hi, I'm not able to answer your question. I'm wondering if you can create your own if it is just your own hobby project, or a project that you don't have to commit to the main repository. Creating DominatorFrontier seems to be expensive. However, if you are using bit-vector to represent a basic-block-set, I guess it can be done in linear time in practice. Following is the

Hi all, Does anyone know how to recreate the DominanceFronter and PostDominanceFrontier structures using the API of the latest release? To my knowledge, these are needed to implement a PRE pass (as done in the past<https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_13/lib/Transforms/Scalar/PRE.cpp>), but they were removed a while ago for efficiency reasons. Is there a better way to

...of flow diagrams <Introduces the concept of dominators, I believe.> 2) Lowry & Medlock '69: Object code optimization <For further discussion of the dominator concept.> 3) Allen '70: Control flow analysis 4) Allen & Cocke '76: A program data flow analysis procedure 5) Ferrante et al. '87: The program dependence graph and its use in optimization 6) Rosen et al. '88: Global value numbers and redundant computations 7) Alpern et al. '88: Detecting equality of variables in programs 8) Cytron et al. '91: Efficiently computing static single assignment form and t...