search for: rwerneck

...g i've done basically says all our time is spent trying to get at successors and predecessors in dominance/post-dominance respectively, which takes basically no time in gcc, because the edge lists are an array. (Note that if you look at generic dominance code, like http://www.cs.princeton.edu/~rwerneck/dominators/, it's much faster than what we do on the same graphs. This is true even though we use the same algorithms .....) Given it seems unlikely we are going to change the internal representation anytime soon (or at least i've not seen a proposal), updating post-dom seems the easier an...

...done basically says all our time is spent trying to get at successors and predecessors in dominance/post-dominance respectively, which takes basically no time in gcc, because the edge lists are an array. > > (Note that if you look at generic dominance code, like http://www.cs.princeton.edu/~rwerneck/dominators/ <http://www.cs.princeton.edu/~rwerneck/dominators/>, it's much faster than what we do on the same graphs. This is true even though we use the same algorithms .....) > > Given it seems unlikely we are going to change the internal representation anytime soon (or at least...

What do you have in mind here? On Thu, Mar 24, 2016, 7:28 PM Daniel Berlin via llvm-dev < llvm-dev at lists.llvm.org> wrote: > Yeah, that was gonna be my question. > If so, my view is we should just bite the bullet and start threading post > dominance through the compiler. > (assuming anyone wants to help. I'm tackling the memoryssa updating stuff > with george ATM).

..., 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 they published. I added those tricks and some others to LLVM's implementation of Lengauer-Tarjan (the simple O(n log n) v...

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

...spent trying to get at successors and > > predecessors in dominance/post-dominance respectively, which takes > > basically no time in gcc, because the edge lists are an array. > > > (Note that if you look at generic dominance code, like > > http://www.cs.princeton.edu/~rwerneck/dominators/ , it's much > > faster > > than what we do on the same graphs. This is true even though we use > > the same algorithms .....) > > > Given it seems unlikely we are going to change the internal > > representation anytime soon (or at least i've no...

...y says all our time is spent trying to get at > successors and predecessors in dominance/post-dominance respectively, which > takes basically no time in gcc, because the edge lists are an array. > > (Note that if you look at generic dominance code, like > http://www.cs.princeton.edu/~rwerneck/dominators/, it's much faster than > what we do on the same graphs. This is true even though we use the same > algorithms .....) > > Given it seems unlikely we are going to change the internal representation > anytime soon (or at least i've not seen a proposal), updating post...

...is spent trying to get at >> successors and predecessors in dominance/post-dominance respectively, which >> takes basically no time in gcc, because the edge lists are an array. >> >> (Note that if you look at generic dominance code, like >> http://www.cs.princeton.edu/~rwerneck/dominators/ >> <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.princeton.edu_-257Erwerneck_dominators_&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=OUaq2P8-4iXMAqcItqLccu1gA856S_ElzN0I0tNjiFk&...

...gt;= 2 for each P in Predecessors(B) runner = P while runner != idom[B] DF(runner) += B runner = idom[runner] You can see this does a lot less work by skipping a lot of useless nodes, etc. It's also a lot simpler to explain :) > > 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 they published. I added those tricks and some others to LLVM's > implementation of Lengauer-Tarjan...

...et at >>> successors and predecessors in dominance/post-dominance respectively, which >>> takes basically no time in gcc, because the edge lists are an array. >>> >>> (Note that if you look at generic dominance code, like >>> http://www.cs.princeton.edu/~rwerneck/dominators/ >>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.cs.princeton.edu_-257Erwerneck_dominators_&d=CwMFaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=lFyiPUrFdOHdaobP7i4hoA&m=09bq6lIe4oGqpw_lE_NAxpN_v13km9w1s-BagEV_Qb8&s=OUaq2P8-4iXMAqcItqLccu1gA856S_ElzN0I0tNjiFk&...