From 02ff6d3f67b1bc03ce43126da03d9cf68d9cc99e Mon Sep 17 00:00:00 2001 From: mikedn Date: Tue, 3 Dec 2019 18:08:11 +0200 Subject: [PATCH] Address review feedback from the dominator tree PR (#348) --- src/coreclr/src/jit/block.cpp | 140 ------------------------------------- src/coreclr/src/jit/block.h | 2 - src/coreclr/src/jit/compiler.cpp | 2 - src/coreclr/src/jit/compiler.h | 12 ++-- src/coreclr/src/jit/flowgraph.cpp | 33 ++++----- src/coreclr/src/jit/ssabuilder.cpp | 6 +- 6 files changed, 22 insertions(+), 173 deletions(-) diff --git a/src/coreclr/src/jit/block.cpp b/src/coreclr/src/jit/block.cpp index cfb9dde..88f297d 100644 --- a/src/coreclr/src/jit/block.cpp +++ b/src/coreclr/src/jit/block.cpp @@ -1444,143 +1444,3 @@ bool BasicBlock::hasEHBoundaryOut() return returnVal; } - -//------------------------------------------------------------------------------ -// DisplayStaticSizes: display various static sizes of the BasicBlock data structure. -// -// Arguments: -// fout - where to write the output -// -// Return Value: -// None -// -// Note: This function only does something if MEASURE_BLOCK_SIZE is defined, which it might -// be in private Release builds. -// -/* static */ -void BasicBlock::DisplayStaticSizes(FILE* fout) -{ -#if MEASURE_BLOCK_SIZE - - BasicBlock* bbDummy = nullptr; - - fprintf(fout, "\n"); - fprintf(fout, "Offset / size of bbNext = %3u / %3u\n", offsetof(BasicBlock, bbNext), - sizeof(bbDummy->bbNext)); - fprintf(fout, "Offset / size of bbPrev = %3u / %3u\n", offsetof(BasicBlock, bbPrev), - sizeof(bbDummy->bbPrev)); - fprintf(fout, "Offset / size of bbFlags = %3u / %3u\n", offsetof(BasicBlock, bbFlags), - sizeof(bbDummy->bbFlags)); - fprintf(fout, "Offset / size of bbNum = %3u / %3u\n", offsetof(BasicBlock, bbNum), - sizeof(bbDummy->bbNum)); - fprintf(fout, "Offset / size of bbPostOrderNum = %3u / %3u\n", offsetof(BasicBlock, bbPostOrderNum), - sizeof(bbDummy->bbPostOrderNum)); - fprintf(fout, "Offset / size of bbRefs = %3u / %3u\n", offsetof(BasicBlock, bbRefs), - sizeof(bbDummy->bbRefs)); - fprintf(fout, "Offset / size of bbWeight = %3u / %3u\n", offsetof(BasicBlock, bbWeight), - sizeof(bbDummy->bbWeight)); - fprintf(fout, "Offset / size of bbJumpKind = %3u / %3u\n", offsetof(BasicBlock, bbJumpKind), - sizeof(bbDummy->bbJumpKind)); - fprintf(fout, "Offset / size of bbJumpOffs = %3u / %3u\n", offsetof(BasicBlock, bbJumpOffs), - sizeof(bbDummy->bbJumpOffs)); - fprintf(fout, "Offset / size of bbJumpDest = %3u / %3u\n", offsetof(BasicBlock, bbJumpDest), - sizeof(bbDummy->bbJumpDest)); - fprintf(fout, "Offset / size of bbJumpSwt = %3u / %3u\n", offsetof(BasicBlock, bbJumpSwt), - sizeof(bbDummy->bbJumpSwt)); - fprintf(fout, "Offset / size of bbEntryState = %3u / %3u\n", offsetof(BasicBlock, bbEntryState), - sizeof(bbDummy->bbEntryState)); - fprintf(fout, "Offset / size of bbStkTempsIn = %3u / %3u\n", offsetof(BasicBlock, bbStkTempsIn), - sizeof(bbDummy->bbStkTempsIn)); - fprintf(fout, "Offset / size of bbStkTempsOut = %3u / %3u\n", offsetof(BasicBlock, bbStkTempsOut), - sizeof(bbDummy->bbStkTempsOut)); - fprintf(fout, "Offset / size of bbTryIndex = %3u / %3u\n", offsetof(BasicBlock, bbTryIndex), - sizeof(bbDummy->bbTryIndex)); - fprintf(fout, "Offset / size of bbHndIndex = %3u / %3u\n", offsetof(BasicBlock, bbHndIndex), - sizeof(bbDummy->bbHndIndex)); - fprintf(fout, "Offset / size of bbCatchTyp = %3u / %3u\n", offsetof(BasicBlock, bbCatchTyp), - sizeof(bbDummy->bbCatchTyp)); - fprintf(fout, "Offset / size of bbStkDepth = %3u / %3u\n", offsetof(BasicBlock, bbStkDepth), - sizeof(bbDummy->bbStkDepth)); - fprintf(fout, "Offset / size of bbFPinVars = %3u / %3u\n", offsetof(BasicBlock, bbFPinVars), - sizeof(bbDummy->bbFPinVars)); - fprintf(fout, "Offset / size of bbCheapPreds = %3u / %3u\n", offsetof(BasicBlock, bbCheapPreds), - sizeof(bbDummy->bbCheapPreds)); - fprintf(fout, "Offset / size of bbPreds = %3u / %3u\n", offsetof(BasicBlock, bbPreds), - sizeof(bbDummy->bbPreds)); - fprintf(fout, "Offset / size of bbReach = %3u / %3u\n", offsetof(BasicBlock, bbReach), - sizeof(bbDummy->bbReach)); - fprintf(fout, "Offset / size of bbIDom = %3u / %3u\n", offsetof(BasicBlock, bbIDom), - sizeof(bbDummy->bbIDom)); - fprintf(fout, "Offset / size of bbDfsNum = %3u / %3u\n", offsetof(BasicBlock, bbDfsNum), - sizeof(bbDummy->bbDfsNum)); - fprintf(fout, "Offset / size of bbCodeOffs = %3u / %3u\n", offsetof(BasicBlock, bbCodeOffs), - sizeof(bbDummy->bbCodeOffs)); - fprintf(fout, "Offset / size of bbCodeOffsEnd = %3u / %3u\n", offsetof(BasicBlock, bbCodeOffsEnd), - sizeof(bbDummy->bbCodeOffsEnd)); - fprintf(fout, "Offset / size of bbVarUse = %3u / %3u\n", offsetof(BasicBlock, bbVarUse), - sizeof(bbDummy->bbVarUse)); - fprintf(fout, "Offset / size of bbVarDef = %3u / %3u\n", offsetof(BasicBlock, bbVarDef), - sizeof(bbDummy->bbVarDef)); - fprintf(fout, "Offset / size of bbLiveIn = %3u / %3u\n", offsetof(BasicBlock, bbLiveIn), - sizeof(bbDummy->bbLiveIn)); - fprintf(fout, "Offset / size of bbLiveOut = %3u / %3u\n", offsetof(BasicBlock, bbLiveOut), - sizeof(bbDummy->bbLiveOut)); - // Can't do bitfield bbMemoryUse, bbMemoryDef, bbMemoryLiveIn, bbMemoryLiveOut, bbMemoryHavoc - fprintf(fout, "Offset / size of bbMemorySsaPhiFunc = %3u / %3u\n", offsetof(BasicBlock, bbMemorySsaPhiFunc), - sizeof(bbDummy->bbMemorySsaPhiFunc)); - fprintf(fout, "Offset / size of bbMemorySsaNumIn = %3u / %3u\n", offsetof(BasicBlock, bbMemorySsaNumIn), - sizeof(bbDummy->bbMemorySsaNumIn)); - fprintf(fout, "Offset / size of bbMemorySsaNumOut = %3u / %3u\n", offsetof(BasicBlock, bbMemorySsaNumOut), - sizeof(bbDummy->bbMemorySsaNumOut)); - fprintf(fout, "Offset / size of bbScope = %3u / %3u\n", offsetof(BasicBlock, bbScope), - sizeof(bbDummy->bbScope)); - fprintf(fout, "Offset / size of bbCseGen = %3u / %3u\n", offsetof(BasicBlock, bbCseGen), - sizeof(bbDummy->bbCseGen)); -#if ASSERTION_PROP - fprintf(fout, "Offset / size of bbAssertionGen = %3u / %3u\n", offsetof(BasicBlock, bbAssertionGen), - sizeof(bbDummy->bbAssertionGen)); -#endif // ASSERTION_PROP - fprintf(fout, "Offset / size of bbCseIn = %3u / %3u\n", offsetof(BasicBlock, bbCseIn), - sizeof(bbDummy->bbCseIn)); -#if ASSERTION_PROP - fprintf(fout, "Offset / size of bbAssertionIn = %3u / %3u\n", offsetof(BasicBlock, bbAssertionIn), - sizeof(bbDummy->bbAssertionIn)); -#endif // ASSERTION_PROP - fprintf(fout, "Offset / size of bbCseOut = %3u / %3u\n", offsetof(BasicBlock, bbCseOut), - sizeof(bbDummy->bbCseOut)); -#if ASSERTION_PROP - fprintf(fout, "Offset / size of bbAssertionOut = %3u / %3u\n", offsetof(BasicBlock, bbAssertionOut), - sizeof(bbDummy->bbAssertionOut)); -#endif // ASSERTION_PROP - fprintf(fout, "Offset / size of bbEmitCookie = %3u / %3u\n", offsetof(BasicBlock, bbEmitCookie), - sizeof(bbDummy->bbEmitCookie)); - -#if defined(FEATURE_EH_FUNCLETS) && defined(_TARGET_ARM_) - fprintf(fout, "Offset / size of bbUnwindNopEmitCookie = %3u / %3u\n", offsetof(BasicBlock, bbUnwindNopEmitCookie), - sizeof(bbDummy->bbUnwindNopEmitCookie)); -#endif // defined(FEATURE_EH_FUNCLETS) && defined(_TARGET_ARM_) - -#ifdef VERIFIER - fprintf(fout, "Offset / size of bbStackIn = %3u / %3u\n", offsetof(BasicBlock, bbStackIn), - sizeof(bbDummy->bbStackIn)); - fprintf(fout, "Offset / size of bbStackOut = %3u / %3u\n", offsetof(BasicBlock, bbStackOut), - sizeof(bbDummy->bbStackOut)); - fprintf(fout, "Offset / size of bbTypesIn = %3u / %3u\n", offsetof(BasicBlock, bbTypesIn), - sizeof(bbDummy->bbTypesIn)); - fprintf(fout, "Offset / size of bbTypesOut = %3u / %3u\n", offsetof(BasicBlock, bbTypesOut), - sizeof(bbDummy->bbTypesOut)); -#endif // VERIFIER - -#ifdef DEBUG - fprintf(fout, "Offset / size of bbLoopNum = %3u / %3u\n", offsetof(BasicBlock, bbLoopNum), - sizeof(bbDummy->bbLoopNum)); -#endif // DEBUG - - fprintf(fout, "Offset / size of bbNatLoopNum = %3u / %3u\n", offsetof(BasicBlock, bbNatLoopNum), - sizeof(bbDummy->bbNatLoopNum)); - - fprintf(fout, "\n"); - fprintf(fout, "Size of BasicBlock = %3u\n", sizeof(BasicBlock)); - -#endif // MEASURE_BLOCK_SIZE -} diff --git a/src/coreclr/src/jit/block.h b/src/coreclr/src/jit/block.h index a886249..c4ef847 100644 --- a/src/coreclr/src/jit/block.h +++ b/src/coreclr/src/jit/block.h @@ -1189,8 +1189,6 @@ struct BasicBlock : private LIR::Range return false; } #endif // DEBUG - - static void DisplayStaticSizes(FILE* fout); }; template <> diff --git a/src/coreclr/src/jit/compiler.cpp b/src/coreclr/src/jit/compiler.cpp index a7cd81b..6eacc9e 100644 --- a/src/coreclr/src/jit/compiler.cpp +++ b/src/coreclr/src/jit/compiler.cpp @@ -1709,8 +1709,6 @@ void Compiler::compDisplayStaticSizes(FILE* fout) GenTree::DumpNodeSizes(fout); #endif - BasicBlock::DisplayStaticSizes(fout); - #if EMITTER_STATS emitterStaticStats(fout); #endif diff --git a/src/coreclr/src/jit/compiler.h b/src/coreclr/src/jit/compiler.h index 60dcacd..869267d 100644 --- a/src/coreclr/src/jit/compiler.h +++ b/src/coreclr/src/jit/compiler.h @@ -4786,12 +4786,8 @@ public: protected: bool fgReachable(BasicBlock* b1, BasicBlock* b2); // Returns true if block b1 can reach block b2 - void fgComputeDoms(); // Computes the immediate dominators for each basic block in the - // flow graph. We first assume the fields bbIDom on each - // basic block are invalid. This computation is needed later - // by fgBuildDomTree to build the dominance tree structure. - // Based on: A Simple, Fast Dominance Algorithm - // by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy + // Compute immediate dominators, the dominator tree and and its pre/post-order travsersal numbers. + void fgComputeDoms(); void fgCompDominatedByExceptionalEntryBlocks(); @@ -9771,7 +9767,7 @@ public: }; // end of class Compiler //--------------------------------------------------------------------------------------------------------------------- -// GenTreeVisitor: a flexible tree walker implemented using the curiosly-recurring-template pattern. +// GenTreeVisitor: a flexible tree walker implemented using the curiously-recurring-template pattern. // // This class implements a configurable walker for IR trees. There are five configuration options (defaults values are // shown in parentheses): @@ -10339,7 +10335,7 @@ public: } }; -// A dominator tree visitor implemented using the curiosly-recurring-template pattern, similar to GenTreeVisitor. +// A dominator tree visitor implemented using the curiously-recurring-template pattern, similar to GenTreeVisitor. template class DomTreeVisitor { diff --git a/src/coreclr/src/jit/flowgraph.cpp b/src/coreclr/src/jit/flowgraph.cpp index f954c47..080e2d5 100644 --- a/src/coreclr/src/jit/flowgraph.cpp +++ b/src/coreclr/src/jit/flowgraph.cpp @@ -2402,6 +2402,14 @@ void Compiler::fgDfsInvPostOrderHelper(BasicBlock* block, BlockSet& visited, uns } } +//------------------------------------------------------------------------ +// fgComputeDoms: Compute immediate dominators, the dominator tree and +// and its pre/post-order travsersal numbers. +// +// Notes: +// Immediate dominator computation is based on "A Simple, Fast Dominance Algorithm" +// by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. +// void Compiler::fgComputeDoms() { assert(!fgCheapPredsValid); @@ -2425,8 +2433,7 @@ void Compiler::fgComputeDoms() BlockSet processedBlks(BlockSetOps::MakeEmpty(this)); - fgBBInvPostOrder = new (this, CMK_DominatorMemory) BasicBlock*[fgBBNumMax + 1]; - memset(fgBBInvPostOrder, 0, sizeof(BasicBlock*) * (fgBBNumMax + 1)); + fgBBInvPostOrder = new (this, CMK_DominatorMemory) BasicBlock*[fgBBNumMax + 1]{}; fgDfsInvPostOrder(); noway_assert(fgBBInvPostOrder[0] == nullptr); @@ -2600,14 +2607,7 @@ DomTreeNode* Compiler::fgBuildDomTree() JITDUMP("\nInside fgBuildDomTree\n"); unsigned bbArraySize = fgBBNumMax + 1; - DomTreeNode* domTree = new (this, CMK_DominatorMemory) DomTreeNode[bbArraySize]; - - // Initialize all the data structures. - for (unsigned i = 0; i < bbArraySize; ++i) - { - domTree[i].firstChild = nullptr; - domTree[i].nextSibling = nullptr; - } + DomTreeNode* domTree = new (this, CMK_DominatorMemory) DomTreeNode[bbArraySize]{}; BasicBlock* imaginaryRoot = fgFirstBB->bbIDom; @@ -2624,7 +2624,7 @@ DomTreeNode* Compiler::fgBuildDomTree() // If the imaginary root is present then we'll need to create a forest instead of a tree. // Forest roots are chained via DomTreeNode::nextSibling and we keep track of this list's - // tail in order to append to it. The head of the list if fgFirstBB, by construction. + // tail in order to append to it. The head of the list is fgFirstBB, by construction. BasicBlock* rootListTail = fgFirstBB; // Traverse the entire block list to build the dominator tree. Skip fgFirstBB @@ -2705,15 +2705,8 @@ void Compiler::fgNumberDomTree(DomTreeNode* domTree) void Begin() { unsigned bbArraySize = m_compiler->fgBBNumMax + 1; - m_compiler->fgDomTreePreOrder = new (m_compiler, CMK_DominatorMemory) unsigned[bbArraySize]; - m_compiler->fgDomTreePostOrder = new (m_compiler, CMK_DominatorMemory) unsigned[bbArraySize]; - - // Initialize all the data structures. - for (unsigned i = 0; i < bbArraySize; ++i) - { - m_compiler->fgDomTreePreOrder[i] = 0; - m_compiler->fgDomTreePostOrder[i] = 0; - } + m_compiler->fgDomTreePreOrder = new (m_compiler, CMK_DominatorMemory) unsigned[bbArraySize]{}; + m_compiler->fgDomTreePostOrder = new (m_compiler, CMK_DominatorMemory) unsigned[bbArraySize]{}; // The preorder and postorder numbers. // We start from 1 to match the bbNum ordering. diff --git a/src/coreclr/src/jit/ssabuilder.cpp b/src/coreclr/src/jit/ssabuilder.cpp index 1313dc2..a84a916 100644 --- a/src/coreclr/src/jit/ssabuilder.cpp +++ b/src/coreclr/src/jit/ssabuilder.cpp @@ -1515,7 +1515,11 @@ void SsaBuilder::Build() m_visited = BitVecOps::MakeEmpty(&m_visitedTraits); // TODO-Cleanup: We currently have two dominance computations happening. We should unify them; for - // now, at least forget the results of the first. + // now, at least forget the results of the first. Note that this does not clear fgDomTreePreOrder + // and fgDomTreePostOrder nor does the subsequent code call fgNumberDomTree once the new dominator + // tree is built. The pre/post order numbers that were generated previously and used for loop + // recognition are still being used by optPerformHoistExpr via fgCreateLoopPreHeader. That's rather + // odd, considering that SetupBBRoot may have added a new block. for (BasicBlock* block = m_pCompiler->fgFirstBB; block != nullptr; block = block->bbNext) { block->bbIDom = nullptr; -- 2.7.4