Created attachment 156927 [details] Add in DFGDominators immediate dominators computing function. Add immediate dominators information in Dominators class.
Attachment 156927 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/dfg/DFGDominators.cp..." exit_code: 1 Source/JavaScriptCore/dfg/DFGDominators.cpp:55: Missing space before { [whitespace/braces] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:122: Missing space before ( in for( [whitespace/parens] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:122: Missing space before { [whitespace/braces] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:123: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:125: Missing spaces around = [whitespace/operators] [4] Source/JavaScriptCore/dfg/DFGDominators.cpp:125: Missing space before ( in for( [whitespace/parens] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:125: Missing space before { [whitespace/braces] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:126: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/dfg/DFGDominators.cpp:128: Missing space before ( in if( [whitespace/parens] [5] Source/JavaScriptCore/dfg/DFGDominators.h:46: The parameter name "graph" adds no information, so it should be removed. [readability/parameter_name] [5] Source/JavaScriptCore/dfg/DFGGraph.cpp:325: Missing space after , [whitespace/comma] [3] Total errors found: 11 in 3 files If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 157712 [details] Add in DFGDominators immediate dominators computing function. with correct style
Comment on attachment 157712 [details] Add in DFGDominators immediate dominators computing function. View in context: https://bugs.webkit.org/attachment.cgi?id=157712&action=review > Source/JavaScriptCore/dfg/DFGDominators.h:59 > + bool isIDomChilds(BlockIndex from, BlockIndex to) const I would change this to immediatelyDominates(from, to). > Source/JavaScriptCore/dfg/DFGDominators.cpp:133 > +void Dominators::buildIDomRelation(Graph& graph) > +{ > + ASSERT(isValid()); > + unsigned numBlocks = graph.m_blocks.size(); > + > + for (unsigned j = 0; j < numBlocks; ++j) > + for (size_t i = 0; i < numBlocks; ++i) { > + if (!m_results[i].get(j)) // i(to), j(from) I need finde j->dominates set > + continue; > + m_resultsIDom[i].set(j); > + m_resultsIDom[j].clear(j); > + } > + > + for (unsigned i = 0; i < numBlocks; ++i) { > + if (!graph.m_blocks[i]) > + continue; > + for (unsigned j = 0; j < numBlocks; ++j) { > + if (!graph.m_blocks[j]) > + continue; > + if (!m_resultsIDom[i].get(j)) > + continue; > + m_resultsIDom[i].exclude(m_resultsIDom[j]); > + } > + } > +} This appears to implement the super-slow version of the algorithm. I would much prefer the Lengauer and Tarjan algorithm. Having an O(n^3) algorithm is probably not a good thing. > Source/JavaScriptCore/dfg/DFGGraph.cpp:325 > - dataLog("%s Dominates:", prefix); > + dataLog("%s Immediately Dominates:", prefix); > for (size_t i = 0; i < m_blocks.size(); ++i) { > - if (!m_dominators.dominates(blockIndex, i)) > + if (!m_dominators.isIDomChilds(blockIndex, i)) I would prefer if we printed both dominators and immediate dominators. Known all of the dominators (not just the immediate ones) is useful when looking at IR.
Created attachment 237133 [details] it begins
Created attachment 237181 [details] getting close
Created attachment 237192 [details] it's getting interesting
Created attachment 237203 [details] it is written
Created attachment 237240 [details] debugging It still has bugs.
Created attachment 237254 [details] still debugging
Created attachment 237268 [details] more progress
Created attachment 237283 [details] it works? Seems right.
Created attachment 237285 [details] the patch
Attachment 237285 [details] did not pass style-queue: ERROR: Source/JavaScriptCore/dfg/DFGDominators.cpp:225: Multi line control clauses should use braces. [whitespace/braces] [4] ERROR: Source/JavaScriptCore/dfg/DFGGraph.cpp:35: Alphabetical sorting problem. [build/include_order] [4] Total errors found: 2 in 21 files If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 237285 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=237285&action=review > Source/JavaScriptCore/dfg/DFGBlockWorklist.h:152 > +struct BlockWithOrder { > + BlockWithOrder() > + : block(nullptr) > + , order(PreOrder) > + { > + } > + > + BlockWithOrder(BasicBlock* block, VisitOrder order) > + : block(block) > + , order(order) > + { > + } > + > + typedef void* (BlockWithOrder::*UnspecifiedBoolType); > + operator UnspecifiedBoolType*() const > + { > + return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr; > + } > + > + BasicBlock* block; > + VisitOrder order; > +}; Why not just specialize the BlockWith<> template with VisitOrder? You could even typedef it if you liked how BlockWithOrder reads better than BlockWith<VisitOrder>.
Comment on attachment 237285 [details] the patch View in context: https://bugs.webkit.org/attachment.cgi?id=237285&action=review r=me with comments. > Source/JavaScriptCore/dfg/DFGDominators.cpp:114 > + // We're initially push with successorIndex = 0 regardless of whether or not we have s/We're initially/We initially/
(In reply to comment #14) > (From update of attachment 237285 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=237285&action=review > > > Source/JavaScriptCore/dfg/DFGBlockWorklist.h:152 > > +struct BlockWithOrder { > > + BlockWithOrder() > > + : block(nullptr) > > + , order(PreOrder) > > + { > > + } > > + > > + BlockWithOrder(BasicBlock* block, VisitOrder order) > > + : block(block) > > + , order(order) > > + { > > + } > > + > > + typedef void* (BlockWithOrder::*UnspecifiedBoolType); > > + operator UnspecifiedBoolType*() const > > + { > > + return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr; > > + } > > + > > + BasicBlock* block; > > + VisitOrder order; > > +}; > > Why not just specialize the BlockWith<> template with VisitOrder? You could even typedef it if you liked how BlockWithOrder reads better than BlockWith<VisitOrder>. I almost did that. I spent a lot of time optimizing for maximum clarity in loops like: while (BlockWithOrder item = worklist.pop()) { switch (item.order) { case PreOrder: worklist.pushPost(item.block); for (unsigned i = item.block->numSuccessors(); i--;) worklist.push(item.block->successor(i)); break; case PostOrder: result.append(item.block); break; } If I had done what you say then I'd be switching on item.data, which I felt was less clear. Note that we already have two loops that use BlockWithOrder. I suspect there will be more of them because postorder traversals are important in compilers.
Landed in http://trac.webkit.org/changeset/173072