Status
()
People
(Reporter: rpearl, Assigned: rpearl)
Tracking
(Blocks: 1 bug)
Firefox Tracking Flags
(Not tracked)
Details
Attachments
(1 attachment, 2 obsolete attachments)
7.48 KB,
patch

dvander
:
review+

Details  Diff  Splinter Review 
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•8 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 LengauerTarjan 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 LengauerTarjan, 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 LengauerTarjan results should catch up quickly based on the relative asymptotic complexity. That this is not the case argues strongly that realworld codes have low connectivity of irreducible loops and their shapes allow for comparatively fast intersections."
Attachment #541218 
Flags: review?(dvander)
(Assignee)  
Comment 2•8 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)
Comment 3•8 years ago


> "For the dominance calculation, the iterative algorithm runs about 2.5 times
> faster than LengauerTarjan, 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 LengauerTarjan results should catch up
> quickly based on the relative asymptotic complexity. That this is not the
> case argues strongly that realworld 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•8 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 dominatorcounting 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; Multiline 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•8 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•8 years ago


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

Attachment #541547 
Attachment is patch: true
Attachment #541547 
Flags: review?(dvander) → review+
(Assignee)  
Comment 8•8 years ago


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