Displaying 3 results from an estimated 3 matches for "domchildren".
2012 Jan 07
1
[LLVMdev] dominance frontiers
...ntiers touching only the nodes that are
*actually in* the dominance frontier :)
The algorithm in the cytron/et al paper looks like this:
for each X in a bottom-up traversal of the dominator tree do
DF(X) = empty
for each Y in Successors(X)
if (idom(Y) != X) then DF(X) += Y
for each Z in DomChildren(X)
for each Y in DF(Z)
if (idom(Y) != X then DF(X) += Y
You can see that this does more comparisons than strictly necessary.
OTOH, the algorithm by Ferrante that Harvey gives is:
for each B in all basic blocks
if the length of Predecessors(B) >= 2
for each P in Predecessors(B)...
2012 Jan 07
0
[LLVMdev] dominance frontiers
On Jan 6, 2012, at 8:27 PM, Daniel Berlin wrote:
> Note: GCC takes exactly the same approach as LLVM here, for exactly
> the reason chris specifies.
> In fact, until we started local SSA updating (which is now many years
> ago, but ...), dominance frontier calculation for ssa updating was in
> the top 10 profile functions for GCC compiles of large source files.
> I had tried a
2012 Jan 07
2
[LLVMdev] dominance frontiers
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.
>>>