summaryrefslogtreecommitdiff
path: root/src/jit/ssabuilder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/jit/ssabuilder.cpp')
-rw-r--r--src/jit/ssabuilder.cpp223
1 files changed, 125 insertions, 98 deletions
diff --git a/src/jit/ssabuilder.cpp b/src/jit/ssabuilder.cpp
index 2da6902464..f0ee461c45 100644
--- a/src/jit/ssabuilder.cpp
+++ b/src/jit/ssabuilder.cpp
@@ -27,87 +27,6 @@ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
namespace
{
/**
- * Visits basic blocks in the depth first order and arranges them in the order of
- * their DFS finish time.
- *
- * @param block The fgFirstBB or entry block.
- * @param comp A pointer to compiler.
- * @param visited In pointer initialized to false and of size at least fgMaxBBNum.
- * @param count Out pointer for count of all nodes reachable by DFS.
- * @param postOrder Out poitner to arrange the blocks and of size at least fgMaxBBNum.
- */
-static void TopologicalSortHelper(BasicBlock* block, Compiler* comp, bool* visited, int* count, BasicBlock** postOrder)
-{
- visited[block->bbNum] = true;
-
- ArrayStack<BasicBlock*> blocks(comp);
- ArrayStack<AllSuccessorIter> iterators(comp);
- ArrayStack<AllSuccessorIter> ends(comp);
-
- // there are three stacks used here and all should be same height
- // the first is for blocks
- // the second is the iterator to keep track of what succ of the block we are looking at
- // and the third is the end marker iterator
- blocks.Push(block);
- iterators.Push(block->GetAllSuccs(comp).begin());
- ends.Push(block->GetAllSuccs(comp).end());
-
- while (blocks.Height() > 0)
- {
- block = blocks.Top();
-
-#ifdef DEBUG
- if (comp->verboseSsa)
- {
- printf("[SsaBuilder::TopologicalSortHelper] Visiting BB%02u: ", block->bbNum);
- printf("[");
- unsigned numSucc = block->NumSucc(comp);
- for (unsigned i = 0; i < numSucc; ++i)
- {
- printf("BB%02u, ", block->GetSucc(i, comp)->bbNum);
- }
- EHSuccessorIter end = block->GetEHSuccs(comp).end();
- for (EHSuccessorIter ehsi = block->GetEHSuccs(comp).begin(); ehsi != end; ++ehsi)
- {
- printf("[EH]BB%02u, ", (*ehsi)->bbNum);
- }
- printf("]\n");
- }
-#endif
-
- if (iterators.TopRef() != ends.TopRef())
- {
- // if the block on TOS still has unreached successors, visit them
- AllSuccessorIter& iter = iterators.TopRef();
- BasicBlock* succ = *iter;
- ++iter;
- // push the child
-
- if (!visited[succ->bbNum])
- {
- blocks.Push(succ);
- iterators.Push(succ->GetAllSuccs(comp).begin());
- ends.Push(succ->GetAllSuccs(comp).end());
- visited[succ->bbNum] = true;
- }
- }
- else
- {
- // all successors have been visited
- blocks.Pop();
- iterators.Pop();
- ends.Pop();
-
- postOrder[*count] = block;
- block->bbPostOrderNum = *count;
- *count += 1;
-
- DBG_SSA_JITDUMP("postOrder[%d] = [%p] and BB%02u\n", *count, dspPtr(block), block->bbNum);
- }
- }
-}
-
-/**
* Method that finds a common IDom parent, much like least common ancestor.
*
* @param finger1 A basic block that might share IDom ancestor with finger2.
@@ -184,6 +103,8 @@ void Compiler::fgResetForSsa()
{
lvaTable[i].lvPerSsaData.Reset();
}
+ lvHeapPerSsaData.Reset();
+ m_heapSsaMap = nullptr;
for (BasicBlock* blk = fgFirstBB; blk != nullptr; blk = blk->bbNext)
{
// Eliminate phis.
@@ -197,6 +118,32 @@ void Compiler::fgResetForSsa()
blk->bbTreeList->gtPrev = last;
}
}
+
+ // Clear post-order numbers and SSA numbers; SSA construction will overwrite these,
+ // but only for reachable code, so clear them to avoid analysis getting confused
+ // by stale annotations in unreachable code.
+ blk->bbPostOrderNum = 0;
+ for (GenTreeStmt* stmt = blk->firstStmt(); stmt != nullptr; stmt = stmt->getNextStmt())
+ {
+ for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree != nullptr; tree = tree->gtNext)
+ {
+ if (tree->IsLocal())
+ {
+ tree->gtLclVarCommon.SetSsaNum(SsaConfig::RESERVED_SSA_NUM);
+ continue;
+ }
+
+ Compiler::IndirectAssignmentAnnotation* pIndirAssign = nullptr;
+ if ((tree->OperGet() != GT_ASG) || !GetIndirAssignMap()->Lookup(tree, &pIndirAssign) ||
+ (pIndirAssign == nullptr))
+ {
+ continue;
+ }
+
+ pIndirAssign->m_defSsaNum = SsaConfig::RESERVED_SSA_NUM;
+ pIndirAssign->m_useSsaNum = SsaConfig::RESERVED_SSA_NUM;
+ }
+ }
}
}
@@ -222,27 +169,97 @@ SsaBuilder::SsaBuilder(Compiler* pCompiler, IAllocator* pIAllocator)
{
}
-/**
- * Topologically sort the graph and return the number of nodes visited.
- *
- * @param postOrder The array in which the arranged basic blocks have to be returned.
- * @param count The size of the postOrder array.
- *
- * @return The number of nodes visited while performing DFS on the graph.
- */
+//------------------------------------------------------------------------
+// TopologicalSort: Topologically sort the graph and return the number of nodes visited.
+//
+// Arguments:
+// postOrder - The array in which the arranged basic blocks have to be returned.
+// count - The size of the postOrder array.
+//
+// Return Value:
+// The number of nodes visited while performing DFS on the graph.
+
int SsaBuilder::TopologicalSort(BasicBlock** postOrder, int count)
{
- // Allocate and initialize visited flags.
- bool* visited = (bool*)alloca(count * sizeof(bool));
- memset(visited, 0, count * sizeof(bool));
+ Compiler* comp = m_pCompiler;
+
+ BitVecTraits traits(comp->fgBBNumMax + 1, comp);
+ BitVec BITVEC_INIT_NOCOPY(visited, BitVecOps::MakeEmpty(&traits));
// Display basic blocks.
- DBEXEC(VERBOSE, m_pCompiler->fgDispBasicBlocks());
- DBEXEC(VERBOSE, m_pCompiler->fgDispHandlerTab());
+ DBEXEC(VERBOSE, comp->fgDispBasicBlocks());
+ DBEXEC(VERBOSE, comp->fgDispHandlerTab());
- // Call the recursive helper.
- int postIndex = 0;
- TopologicalSortHelper(m_pCompiler->fgFirstBB, m_pCompiler, visited, &postIndex, postOrder);
+ // Compute order.
+ int postIndex = 0;
+ BasicBlock* block = comp->fgFirstBB;
+ BitVecOps::AddElemD(&traits, visited, block->bbNum);
+
+ ArrayStack<BasicBlock*> blocks(comp);
+ ArrayStack<AllSuccessorIter> iterators(comp);
+ ArrayStack<AllSuccessorIter> ends(comp);
+
+ // there are three stacks used here and all should be same height
+ // the first is for blocks
+ // the second is the iterator to keep track of what succ of the block we are looking at
+ // and the third is the end marker iterator
+ blocks.Push(block);
+ iterators.Push(block->GetAllSuccs(comp).begin());
+ ends.Push(block->GetAllSuccs(comp).end());
+
+ while (blocks.Height() > 0)
+ {
+ block = blocks.Top();
+
+#ifdef DEBUG
+ if (comp->verboseSsa)
+ {
+ printf("[SsaBuilder::TopologicalSort] Visiting BB%02u: ", block->bbNum);
+ printf("[");
+ unsigned numSucc = block->NumSucc(comp);
+ for (unsigned i = 0; i < numSucc; ++i)
+ {
+ printf("BB%02u, ", block->GetSucc(i, comp)->bbNum);
+ }
+ EHSuccessorIter end = block->GetEHSuccs(comp).end();
+ for (EHSuccessorIter ehsi = block->GetEHSuccs(comp).begin(); ehsi != end; ++ehsi)
+ {
+ printf("[EH]BB%02u, ", (*ehsi)->bbNum);
+ }
+ printf("]\n");
+ }
+#endif
+
+ if (iterators.TopRef() != ends.TopRef())
+ {
+ // if the block on TOS still has unreached successors, visit them
+ AllSuccessorIter& iter = iterators.TopRef();
+ BasicBlock* succ = *iter;
+ ++iter;
+
+ // push the children
+ if (!BitVecOps::IsMember(&traits, visited, succ->bbNum))
+ {
+ blocks.Push(succ);
+ iterators.Push(succ->GetAllSuccs(comp).begin());
+ ends.Push(succ->GetAllSuccs(comp).end());
+ BitVecOps::AddElemD(&traits, visited, succ->bbNum);
+ }
+ }
+ else
+ {
+ // all successors have been visited
+ blocks.Pop();
+ iterators.Pop();
+ ends.Pop();
+
+ postOrder[postIndex] = block;
+ block->bbPostOrderNum = postIndex;
+ postIndex += 1;
+
+ DBG_SSA_JITDUMP("postOrder[%d] = [%p] and BB%02u\n", postIndex, dspPtr(block), block->bbNum);
+ }
+ }
// In the absence of EH (because catch/finally have no preds), this should be valid.
// assert(postIndex == (count - 1));
@@ -1686,7 +1703,17 @@ void SsaBuilder::Build()
JITDUMP("[SsaBuilder] Max block count is %d.\n", blockCount);
// Allocate the postOrder array for the graph.
- BasicBlock** postOrder = (BasicBlock**)alloca(blockCount * sizeof(BasicBlock*));
+
+ BasicBlock** postOrder;
+
+ if (blockCount > DEFAULT_MIN_OPTS_BB_COUNT)
+ {
+ postOrder = new (m_pCompiler->getAllocator()) BasicBlock*[blockCount];
+ }
+ else
+ {
+ postOrder = (BasicBlock**)alloca(blockCount * sizeof(BasicBlock*));
+ }
// Topologically sort the graph.
int count = TopologicalSort(postOrder, blockCount);