666426 - Ionmonkey: Build an explicit dominator tree

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Ryan Pearl [:rpearl]]

Some optimization passes need to traverse the CFG through the dominator tree. Therefore, this is probably a useful thing to expose to the rest of the JIT as well.

Comment 1

[Ryan Pearl [:rpearl]]

Attachment: build a dominator tree

This builds a dominator tree in an O(n^2) pass, using the algorithm from the paper "A Simple, Fast Dominance Algorithm" by Cooper et al. 

With careful engineering, the Lengauer-Tarjan which runs in O(n * log(n)) could be used. 

However, from the paper describing the current algorithm, 
"For the dominance calculation, the iterative algorithm runs about 2.5 times faster than Lengauer-Tarjan, on average. The improvement slowly decreases as the number of blocks increases. This is what we would expect: the Lengauer and Tarjan algorithm has a greater startup cost, which gets amortized in larger graphs. Of course, the Lengauer-Tarjan results should catch up quickly based on the relative asymptotic complexity. That this is not the case argues strongly that real-world codes have low connectivity of irreducible loops and their shapes allow for comparatively fast intersections."

Comment 2

[Ryan Pearl [:rpearl]]

Comment on attachment 541218 [details] [diff] [review]
build a dominator tree

This patch does not include the explicit dominator tree. New patch forthcoming.

Comment 3

[David Mandelin [:dmandelin]]

> "For the dominance calculation, the iterative algorithm runs about 2.5 times
> faster than Lengauer-Tarjan, on average. The improvement slowly decreases as
> the number of blocks increases. This is what we would expect: the Lengauer
> and Tarjan algorithm has a greater startup cost, which gets amortized in
> larger graphs. Of course, the Lengauer-Tarjan results should catch up
> quickly based on the relative asymptotic complexity. That this is not the
> case argues strongly that real-world codes have low connectivity of
> irreducible loops and their shapes allow for comparatively fast
> intersections."

Great find. This is exactly the kind of knowledge that we need to document and build up.

Comment 4

[Ryan Pearl [:rpearl]]

Attachment: build explicit tree

Patch now includes building an explicit tree with a list of children.

Comment 5

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 541237 [details] [diff] [review]
build explicit tree

Review of attachment 541237 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great, mostly style nits, though one big remark: the dominator-counting traversal seems complicated. Would it be easier to just propagate these counts by iterating in postorder?

::: js/src/ion/IonAnalysis.cpp
@@ +451,5 @@
>  }
>  
> +// A Simple, Fast Dominance Algorithm by Cooper et al.
> +static MBasicBlock *
> +intersectDominators(MBasicBlock *block1, MBasicBlock *block2)

StudlyCaps for statics.

@@ +487,5 @@
> +        // We start at 1, not 0, intentionally excluding the start node.
> +        for (size_t i = 1; i < graph.numBlocks(); i++) {
> +            MBasicBlock *block = graph.getBlock(i);
> +
> +            if(block->numPredecessors() == 0) continue;

continue goes on a new line, but can blocks other than the start block have no predecessors?

@@ +516,5 @@
> +
> +    for (size_t i = 1; i < graph.numBlocks(); i++) {
> +        MBasicBlock *child = graph.getBlock(i);
> +        MBasicBlock *parent = child->dominator();
> +        parent->addImmediateDominated(child);

This should be fallible

@@ +519,5 @@
> +        MBasicBlock *parent = child->dominator();
> +        parent->addImmediateDominated(child);
> +    }
> +
> +    // Now we have a tree. Traverse it once to build up the counts.

Please say exactly what the counts are.

@@ +549,5 @@
> +                return false;
> +
> +            for(size_t i = 0; i < immediates; i++)
> +                 if(!nodes.append(block->getImmediateDominated(i)))
> +                     return false;

Multi-line |for| needs braces.

::: js/src/ion/MIRGraph.h
@@ +344,5 @@
>      MStart *start() const {
>          return start_;
>      }
>  
> +    MBasicBlock *dominator() const {

Should this be "immediateDominator" to avoid confusion?

@@ +429,5 @@
>  
>      // Utility mark for traversal algorithms.
>      bool mark_;
> +
> +    Vector<MBasicBlock *, 1, IonAllocPolicy> immediateDominated_;

"immediatelyDominated_" might sound better

Comment 6

[Ryan Pearl [:rpearl]]

(In reply to comment #5)

> @@ +487,5 @@
> > +        // We start at 1, not 0, intentionally excluding the start node.
> > +        for (size_t i = 1; i < graph.numBlocks(); i++) {
> > +            MBasicBlock *block = graph.getBlock(i);
> > +
> > +            if(block->numPredecessors() == 0) continue;
> 
> continue goes on a new line, but can blocks other than the start block have
> no predecessors?

Good point. I guess I will assert it, since I rely on this fact.

> 
> @@ +519,5 @@
> > +        MBasicBlock *parent = child->dominator();
> > +        parent->addImmediateDominated(child);
> > +    }
> > +
> > +    // Now we have a tree. Traverse it once to build up the counts.
> 
> Please say exactly what the counts are.

In your overall comment, you say "Would it be easier to just propagate these counts by iterating in postorder?"

But this is an iterative postorder traversal of the dominator tree. Is there a simpler way to do one?

Comment 7

[Ryan Pearl [:rpearl]]

Attachment: simplify count propagation

Comment 8

[Ryan Pearl [:rpearl]]

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/2fba36231efe