Note: There are a few cases of duplicates in user autocompletion which are being worked on.

Ionmonkey: Build an explicit dominator tree

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: rpearl, Assigned: rpearl)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

6 years ago
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.
(Assignee)

Comment 1

6 years ago
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."
Attachment #541218 - Flags: review?(dvander)
(Assignee)

Comment 2

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

This patch does not include the explicit dominator tree. New patch forthcoming.
Attachment #541218 - Attachment is obsolete: true
Attachment #541218 - Flags: review?(dvander)
> "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.
(Assignee)

Comment 4

6 years ago
Created attachment 541237 [details] [diff] [review]
build explicit tree

Patch now includes building an explicit tree with a list of children.
Attachment #541237 - Flags: review?(dvander)
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
Attachment #541237 - Flags: review?(dvander) → review+
(Assignee)

Comment 6

6 years ago
(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?
(Assignee)

Comment 7

6 years ago
Created attachment 541547 [details] [diff] [review]
simplify count propagation
Attachment #541237 - Attachment is obsolete: true
Attachment #541547 - Flags: review?(dvander)
(Assignee)

Updated

6 years ago
Attachment #541547 - Attachment is patch: true
Attachment #541547 - Flags: review?(dvander) → review+
(Assignee)

Comment 8

6 years ago
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/2fba36231efe
Status: ASSIGNED → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.