Last Comment Bug 666426 - Ionmonkey: Build an explicit dominator tree
: Ionmonkey: Build an explicit dominator tree
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Ryan Pearl [:rpearl]
:
Mentors:
Depends on:
Blocks: IonMonkey 659729
  Show dependency treegraph
 
Reported: 2011-06-22 16:08 PDT by Ryan Pearl [:rpearl]
Modified: 2011-06-24 22:14 PDT (History)
5 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
build a dominator tree (5.35 KB, patch)
2011-06-22 16:15 PDT, Ryan Pearl [:rpearl]
no flags Details | Diff | Splinter Review
build explicit tree (7.84 KB, patch)
2011-06-22 17:10 PDT, Ryan Pearl [:rpearl]
dvander: review+
Details | Diff | Splinter Review
simplify count propagation (7.48 KB, patch)
2011-06-23 16:33 PDT, Ryan Pearl [:rpearl]
dvander: review+
Details | Diff | Splinter Review

Description Ryan Pearl [:rpearl] 2011-06-22 16:08:35 PDT
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] 2011-06-22 16:15:42 PDT
Created attachment 541218 [details] [diff] [review]
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] 2011-06-22 16:24:50 PDT
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] 2011-06-22 17:03:30 PDT
> "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] 2011-06-22 17:10:19 PDT
Created attachment 541237 [details] [diff] [review]
build explicit tree

Patch now includes building an explicit tree with a list of children.
Comment 5 David Anderson [:dvander] 2011-06-22 18:40:21 PDT
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] 2011-06-22 20:41:46 PDT
(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] 2011-06-23 16:33:49 PDT
Created attachment 541547 [details] [diff] [review]
simplify count propagation

Note You need to log in before you can comment on or make changes to this bug.