Improve SSA dominator tree memory usage (#15006)

There is no need to store the dominator tree children in a hashtable, a vector is sufficient. Given the way the tree is constructed duplicates cannot be added.

3 files changed, 35 insertions, 45 deletions

diff --git a/src/jit/copyprop.cpp b/src/jit/copyprop.cpp
index 3c59832da2..aaa0c247a7 100644
--- a/src/jit/copyprop.cpp
+++ b/src/jit/copyprop.cpp
@@ -431,7 +431,7 @@ void Compiler::optVnCopyProp()
     CompAllocator allocator(this, CMK_CopyProp);
 
     // Compute the domTree to use.
-    BlkToBlkSetMap* domTree = new (&allocator) BlkToBlkSetMap(&allocator);
+    BlkToBlkVectorMap* domTree = new (&allocator) BlkToBlkVectorMap(&allocator);
     domTree->Reallocate(fgBBcount * 3 / 2); // Prime the allocation
     SsaBuilder::ComputeDominators(this, domTree);
 
@@ -474,12 +474,12 @@ void Compiler::optVnCopyProp()
         optBlockCopyProp(block, &curSsaName);
 
         // Add dom children to work on.
-        BlkSet* pBlkSet;
-        if (domTree->Lookup(block, &pBlkSet))
+        BlkVector* domChildren = domTree->LookupPointer(block);
+        if (domChildren != nullptr)
         {
-            for (BlkSet::KeyIterator child = pBlkSet->Begin(); !child.Equal(pBlkSet->End()); ++child)
+            for (BasicBlock* child : *domChildren)
             {
-                worklist->push_back(BlockWork(child.Get()));
+                worklist->push_back(BlockWork(child));
             }
         }
     }
diff --git a/src/jit/ssabuilder.cpp b/src/jit/ssabuilder.cpp
index d64ba203ab..5bad254780 100644
--- a/src/jit/ssabuilder.cpp
+++ b/src/jit/ssabuilder.cpp
@@ -354,7 +354,7 @@ void SsaBuilder::ComputeImmediateDom(BasicBlock** postOrder, int count)
  * @remarks This would help us answer queries such as "a dom b?" in constant time.
  *          For example, if a dominated b, then Pre[a] < Pre[b] but Post[a] > Post[b]
  */
-void SsaBuilder::DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int* preIndex, int* postIndex)
+void SsaBuilder::DomTreeWalk(BasicBlock* curBlock, BlkToBlkVectorMap* domTree, int* preIndex, int* postIndex)
 {
     JITDUMP("[SsaBuilder::DomTreeWalk] block %s:\n", curBlock->dspToString());
 
@@ -362,14 +362,14 @@ void SsaBuilder::DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int*
     m_pDomPreOrder[curBlock->bbNum] = *preIndex;
     ++(*preIndex);
 
-    BlkSet* pBlkSet;
-    if (domTree->Lookup(curBlock, &pBlkSet))
+    BlkVector* domChildren = domTree->LookupPointer(curBlock);
+    if (domChildren != nullptr)
     {
-        for (BlkSet::KeyIterator ki = pBlkSet->Begin(); !ki.Equal(pBlkSet->End()); ++ki)
+        for (BasicBlock* child : *domChildren)
         {
-            if (curBlock != ki.Get())
+            if (curBlock != child)
             {
-                DomTreeWalk(ki.Get(), domTree, preIndex, postIndex);
+                DomTreeWalk(child, domTree, preIndex, postIndex);
             }
         }
     }
@@ -388,7 +388,7 @@ void SsaBuilder::DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int*
  *
  */
 /* static */
-void SsaBuilder::ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkSetMap* domTree)
+void SsaBuilder::ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkVectorMap* domTree)
 {
     BasicBlock* bbIDom = block->bbIDom;
 
@@ -399,16 +399,11 @@ void SsaBuilder::ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block
     }
 
     // If the bbIDom map key doesn't exist, create one.
-    BlkSet* pBlkSet;
-    if (!domTree->Lookup(bbIDom, &pBlkSet))
-    {
-        pBlkSet = new (domTree->GetAllocator()) BlkSet(domTree->GetAllocator());
-        domTree->Set(bbIDom, pBlkSet);
-    }
+    BlkVector* domChildren = domTree->Emplace(bbIDom, domTree->GetAllocator());
 
     DBG_SSA_JITDUMP("Inserting BB%02u as dom child of BB%02u.\n", block->bbNum, bbIDom->bbNum);
     // Insert the block into the block's set.
-    pBlkSet->Set(block, true);
+    domChildren->push_back(block);
 }
 
 /**
@@ -421,7 +416,7 @@ void SsaBuilder::ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block
  *
  */
 /* static */
-void SsaBuilder::ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree)
+void SsaBuilder::ComputeDominators(Compiler* pCompiler, BlkToBlkVectorMap* domTree)
 {
     JITDUMP("*************** In SsaBuilder::ComputeDominators(Compiler*, ...)\n");
 
@@ -445,7 +440,7 @@ void SsaBuilder::ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree)
  * @param domTree A map of (block -> set of blocks) tree representation that is empty.
  *
  */
-void SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSetMap* domTree)
+void SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkVectorMap* domTree)
 {
     JITDUMP("*************** In SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, ...)\n");
 
@@ -481,21 +476,16 @@ void SsaBuilder::ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSe
  * @param domTree A map of (block -> set of blocks) tree representation.
  */
 /* static */
-void SsaBuilder::DisplayDominators(BlkToBlkSetMap* domTree)
+void SsaBuilder::DisplayDominators(BlkToBlkVectorMap* domTree)
 {
     printf("After computing dominator tree: \n");
-    for (BlkToBlkSetMap::KeyIterator nodes = domTree->Begin(); !nodes.Equal(domTree->End()); ++nodes)
+    for (BlkToBlkVectorMap::KeyIterator nodes = domTree->Begin(); !nodes.Equal(domTree->End()); ++nodes)
     {
         printf("BB%02u := {", nodes.Get()->bbNum);
-
-        BlkSet* pBlkSet = nodes.GetValue();
-        for (BlkSet::KeyIterator ki = pBlkSet->Begin(); !ki.Equal(pBlkSet->End()); ++ki)
+        int index = 0;
+        for (BasicBlock* child : nodes.GetValue())
         {
-            if (!ki.Equal(pBlkSet->Begin()))
-            {
-                printf(",");
-            }
-            printf("BB%02u", ki.Get()->bbNum);
+            printf("%sBB%02u", (index++ == 0) ? "" : ",", child->bbNum);
         }
         printf("}\n");
     }
@@ -1619,7 +1609,7 @@ void SsaBuilder::BlockPopStacks(BasicBlock* block, SsaRenameState* pRenameState)
  *      and Destruction of Static Single Assignment Form."
  */
 
-void SsaBuilder::RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenameState)
+void SsaBuilder::RenameVariables(BlkToBlkVectorMap* domTree, SsaRenameState* pRenameState)
 {
     JITDUMP("*************** In SsaBuilder::RenameVariables()\n");
 
@@ -1712,13 +1702,13 @@ void SsaBuilder::RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenam
             AssignPhiNodeRhsVariables(block, pRenameState);
 
             // Recurse with the block's DOM children.
-            BlkSet* pBlkSet;
-            if (domTree->Lookup(block, &pBlkSet))
+            BlkVector* domChildren = domTree->LookupPointer(block);
+            if (domChildren != nullptr)
             {
-                for (BlkSet::KeyIterator child = pBlkSet->Begin(); !child.Equal(pBlkSet->End()); ++child)
+                for (BasicBlock* child : *domChildren)
                 {
-                    DBG_SSA_JITDUMP("[SsaBuilder::RenameVariables](pushing dom child BB%02u)\n", child.Get()->bbNum);
-                    blocksToDo->push_back(BlockWork(child.Get()));
+                    DBG_SSA_JITDUMP("[SsaBuilder::RenameVariables](pushing dom child BB%02u)\n", child->bbNum);
+                    blocksToDo->push_back(BlockWork(child));
                 }
             }
         }
@@ -1832,7 +1822,7 @@ void SsaBuilder::Build()
     ComputeImmediateDom(postOrder, count);
 
     // Compute the dominator tree.
-    BlkToBlkSetMap* domTree = new (&m_allocator) BlkToBlkSetMap(&m_allocator);
+    BlkToBlkVectorMap* domTree = new (&m_allocator) BlkToBlkVectorMap(&m_allocator);
     ComputeDominators(postOrder, count, domTree);
     EndPhase(PHASE_BUILD_SSA_DOMS);
 
diff --git a/src/jit/ssabuilder.h b/src/jit/ssabuilder.h
index 3b1ca22289..602f853399 100644
--- a/src/jit/ssabuilder.h
+++ b/src/jit/ssabuilder.h
@@ -43,7 +43,7 @@ public:
     // Using IDom of each basic block, compute the whole domTree. If a block "b" has IDom "i",
     // then, block "b" is dominated by "i". The mapping then is i -> { ..., b, ... }, in
     // other words, "domTree" is a tree represented by nodes mapped to their children.
-    static void ComputeDominators(Compiler* pCompiler, BlkToBlkSetMap* domTree);
+    static void ComputeDominators(Compiler* pCompiler, BlkToBlkVectorMap* domTree);
 
 private:
     // Ensures that the basic block graph has a root for the dominator graph, by ensuring
@@ -69,21 +69,21 @@ private:
     // as children.) Requires "preIndex" and "postIndex" to be initialized to 0 at entry into recursion.
     // Computes arrays "m_pDomPreOrder" and "m_pDomPostOrder" of block indices such that the blocks of a
     // "domTree" are in pre and postorder respectively.
-    void DomTreeWalk(BasicBlock* curBlock, BlkToBlkSetMap* domTree, int* preIndex, int* postIndex);
+    void DomTreeWalk(BasicBlock* curBlock, BlkToBlkVectorMap* domTree, int* preIndex, int* postIndex);
 #endif
 
-    // Requires all blocks to have computed "bbIDom." Requires "domTree" to be a preallocated BlkToBlkSetMap.
+    // Requires all blocks to have computed "bbIDom." Requires "domTree" to be a preallocated BlkToBlkVectorMap.
     // Helper to compute "domTree" from the pre-computed bbIDom of the basic blocks.
-    static void ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkSetMap* domTree);
+    static void ConstructDomTreeForBlock(Compiler* pCompiler, BasicBlock* block, BlkToBlkVectorMap* domTree);
 
     // Requires "postOrder" to hold the blocks of the flowgraph in topologically sorted order. Requires
     // count to be the valid entries in the "postOrder" array. Computes "domTree" as a adjacency list
     // like object, i.e., a set of blocks with a set of blocks as children defining the DOM relation.
-    void ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkSetMap* domTree);
+    void ComputeDominators(BasicBlock** postOrder, int count, BlkToBlkVectorMap* domTree);
 
 #ifdef DEBUG
     // Display the dominator tree.
-    static void DisplayDominators(BlkToBlkSetMap* domTree);
+    static void DisplayDominators(BlkToBlkVectorMap* domTree);
 #endif // DEBUG
 
     // Compute flow graph dominance frontiers.
@@ -101,7 +101,7 @@ private:
     // Requires "domTree" to be the dominator tree relation defined by a DOM b.
     // Requires "pRenameState" to have counts and stacks at their initial state.
     // Assigns gtSsaNames to all variables.
-    void RenameVariables(BlkToBlkSetMap* domTree, SsaRenameState* pRenameState);
+    void RenameVariables(BlkToBlkVectorMap* domTree, SsaRenameState* pRenameState);
 
     // Requires "block" to be any basic block participating in variable renaming, and has at least a
     // definition that pushed a ssa number into the rename stack for a variable. Requires "pRenameState"