Permalink
Fetching contributors…
Cannot retrieve contributors at this time
25869 lines (21989 sloc) 874 KB
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX XX
XX FlowGraph XX
XX XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*/
#include "jitpch.h"
#ifdef _MSC_VER
#pragma hdrstop
#endif
#include "allocacheck.h" // for alloca
#include "lower.h" // for LowerRange()
/*****************************************************************************/
void Compiler::fgInit()
{
impInit();
/* Initialization for fgWalkTreePre() and fgWalkTreePost() */
fgFirstBBScratch = nullptr;
#ifdef DEBUG
fgPrintInlinedMethods = JitConfig.JitPrintInlinedMethods() == 1;
#endif // DEBUG
/* We haven't yet computed the bbPreds lists */
fgComputePredsDone = false;
/* We haven't yet computed the bbCheapPreds lists */
fgCheapPredsValid = false;
/* We haven't yet computed the edge weight */
fgEdgeWeightsComputed = false;
fgHaveValidEdgeWeights = false;
fgSlopUsedInEdgeWeights = false;
fgRangeUsedInEdgeWeights = true;
fgNeedsUpdateFlowGraph = false;
fgCalledCount = BB_ZERO_WEIGHT;
/* We haven't yet computed the dominator sets */
fgDomsComputed = false;
#ifdef DEBUG
fgReachabilitySetsValid = false;
#endif // DEBUG
/* We don't know yet which loops will always execute calls */
fgLoopCallMarked = false;
/* We haven't created GC Poll blocks yet. */
fgGCPollsCreated = false;
/* Initialize the basic block list */
fgFirstBB = nullptr;
fgLastBB = nullptr;
fgFirstColdBlock = nullptr;
#if FEATURE_EH_FUNCLETS
fgFirstFuncletBB = nullptr;
fgFuncletsCreated = false;
#endif // FEATURE_EH_FUNCLETS
fgBBcount = 0;
#ifdef DEBUG
fgBBcountAtCodegen = 0;
#endif // DEBUG
fgBBNumMax = 0;
fgEdgeCount = 0;
fgDomBBcount = 0;
fgBBVarSetsInited = false;
fgReturnCount = 0;
// Initialize BlockSet data.
fgCurBBEpoch = 0;
fgCurBBEpochSize = 0;
fgBBSetCountInSizeTUnits = 0;
genReturnBB = nullptr;
/* We haven't reached the global morphing phase */
fgGlobalMorph = false;
fgModified = false;
#ifdef DEBUG
fgSafeBasicBlockCreation = true;
#endif // DEBUG
fgLocalVarLivenessDone = false;
/* Statement list is not threaded yet */
fgStmtListThreaded = false;
// Initialize the logic for adding code. This is used to insert code such
// as the code that raises an exception when an array range check fails.
fgAddCodeList = nullptr;
fgAddCodeModf = false;
for (int i = 0; i < SCK_COUNT; i++)
{
fgExcptnTargetCache[i] = nullptr;
}
/* Keep track of the max count of pointer arguments */
fgPtrArgCntMax = 0;
/* This global flag is set whenever we remove a statement */
fgStmtRemoved = false;
/* This global flag is set whenever we add a throw block for a RngChk */
fgRngChkThrowAdded = false; /* reset flag for fgIsCodeAdded() */
/* We will record a list of all BBJ_RETURN blocks here */
fgReturnBlocks = nullptr;
/* This is set by fgComputeReachability */
fgEnterBlks = BlockSetOps::UninitVal();
#ifdef DEBUG
fgEnterBlksSetValid = false;
#endif // DEBUG
#if !FEATURE_EH_FUNCLETS
ehMaxHndNestingCount = 0;
#endif // !FEATURE_EH_FUNCLETS
/* Init the fgBigOffsetMorphingTemps to be BAD_VAR_NUM. */
for (int i = 0; i < TYP_COUNT; i++)
{
fgBigOffsetMorphingTemps[i] = BAD_VAR_NUM;
}
fgNoStructPromotion = false;
fgNoStructParamPromotion = false;
optValnumCSE_phase = false; // referenced in fgMorphSmpOp()
#ifdef DEBUG
fgNormalizeEHDone = false;
#endif // DEBUG
#ifdef DEBUG
if (!compIsForInlining())
{
if ((JitConfig.JitNoStructPromotion() & 1) == 1)
{
fgNoStructPromotion = true;
}
if ((JitConfig.JitNoStructPromotion() & 2) == 2)
{
fgNoStructParamPromotion = true;
}
}
#endif // DEBUG
if (!compIsForInlining())
{
m_promotedStructDeathVars = nullptr;
}
#ifdef FEATURE_SIMD
fgPreviousCandidateSIMDFieldAsgStmt = nullptr;
#endif
}
bool Compiler::fgHaveProfileData()
{
if (compIsForInlining() || compIsForImportOnly())
{
return false;
}
return (fgProfileBuffer != nullptr);
}
bool Compiler::fgGetProfileWeightForBasicBlock(IL_OFFSET offset, unsigned* weightWB)
{
noway_assert(weightWB != nullptr);
unsigned weight = 0;
#ifdef DEBUG
unsigned hashSeed = fgStressBBProf();
if (hashSeed != 0)
{
unsigned hash = (info.compMethodHash() * hashSeed) ^ (offset * 1027);
// We need to especially stress the procedure splitting codepath. Therefore
// one third the time we should return a weight of zero.
// Otherwise we should return some random weight (usually between 0 and 288).
// The below gives a weight of zero, 44% of the time
if (hash % 3 == 0)
{
weight = 0;
}
else if (hash % 11 == 0)
{
weight = (hash % 23) * (hash % 29) * (hash % 31);
}
else
{
weight = (hash % 17) * (hash % 19);
}
// The first block is never given a weight of zero
if ((offset == 0) && (weight == 0))
{
weight = 1 + (hash % 5);
}
*weightWB = weight;
return true;
}
#endif // DEBUG
if (fgHaveProfileData() == false)
{
return false;
}
noway_assert(!compIsForInlining());
for (unsigned i = 0; i < fgProfileBufferCount; i++)
{
if (fgProfileBuffer[i].ILOffset == offset)
{
weight = fgProfileBuffer[i].ExecutionCount;
*weightWB = weight;
return true;
}
}
*weightWB = 0;
return true;
}
void Compiler::fgInstrumentMethod()
{
noway_assert(!compIsForInlining());
// Count the number of basic blocks in the method
int countOfBlocks = 0;
BasicBlock* block;
for (block = fgFirstBB; (block != nullptr); block = block->bbNext)
{
if (!(block->bbFlags & BBF_IMPORTED) || (block->bbFlags & BBF_INTERNAL))
{
continue;
}
countOfBlocks++;
}
// Allocate the profile buffer
ICorJitInfo::ProfileBuffer* bbProfileBufferStart;
HRESULT res = info.compCompHnd->allocBBProfileBuffer(countOfBlocks, &bbProfileBufferStart);
GenTree* stmt;
if (!SUCCEEDED(res))
{
// The E_NOTIMPL status is returned when we are profiling a generic method from a different assembly
if (res == E_NOTIMPL)
{
// In such cases we still want to add the method entry callback node
GenTreeArgList* args = gtNewArgList(gtNewIconEmbMethHndNode(info.compMethodHnd));
GenTree* call = gtNewHelperCallNode(CORINFO_HELP_BBT_FCN_ENTER, TYP_VOID, args);
stmt = gtNewStmt(call);
}
else
{
noway_assert(!"Error: failed to allocate bbProfileBuffer");
return;
}
}
else
{
// For each BasicBlock (non-Internal)
// 1. Assign the blocks bbCodeOffs to the ILOffset field of this blocks profile data.
// 2. Add an operation that increments the ExecutionCount field at the beginning of the block.
// Each (non-Internal) block has it own ProfileBuffer tuple [ILOffset, ExecutionCount]
// To start we initialize our current one with the first one that we allocated
//
ICorJitInfo::ProfileBuffer* bbCurrentBlockProfileBuffer = bbProfileBufferStart;
for (block = fgFirstBB; (block != nullptr); block = block->bbNext)
{
if (!(block->bbFlags & BBF_IMPORTED) || (block->bbFlags & BBF_INTERNAL))
{
continue;
}
// Assign the current block's IL offset into the profile data
bbCurrentBlockProfileBuffer->ILOffset = block->bbCodeOffs;
assert(bbCurrentBlockProfileBuffer->ExecutionCount == 0); // This value should already be zero-ed out
size_t addrOfCurrentExecutionCount = (size_t)&bbCurrentBlockProfileBuffer->ExecutionCount;
// Read Basic-Block count value
GenTree* valueNode =
gtNewIndOfIconHandleNode(TYP_INT, addrOfCurrentExecutionCount, GTF_ICON_BBC_PTR, false);
// Increment value by 1
GenTree* rhsNode = gtNewOperNode(GT_ADD, TYP_INT, valueNode, gtNewIconNode(1));
// Write new Basic-Block count value
GenTree* lhsNode = gtNewIndOfIconHandleNode(TYP_INT, addrOfCurrentExecutionCount, GTF_ICON_BBC_PTR, false);
GenTree* asgNode = gtNewAssignNode(lhsNode, rhsNode);
fgInsertStmtAtBeg(block, asgNode);
// Advance to the next ProfileBuffer tuple [ILOffset, ExecutionCount]
bbCurrentBlockProfileBuffer++;
// One less block
countOfBlocks--;
}
// Check that we allocated and initialized the same number of ProfileBuffer tuples
noway_assert(countOfBlocks == 0);
// Add the method entry callback node
GenTree* arg;
#ifdef FEATURE_READYTORUN_COMPILER
if (opts.IsReadyToRun())
{
mdMethodDef currentMethodToken = info.compCompHnd->getMethodDefFromMethod(info.compMethodHnd);
CORINFO_RESOLVED_TOKEN resolvedToken;
resolvedToken.tokenContext = MAKE_METHODCONTEXT(info.compMethodHnd);
resolvedToken.tokenScope = info.compScopeHnd;
resolvedToken.token = currentMethodToken;
resolvedToken.tokenType = CORINFO_TOKENKIND_Method;
info.compCompHnd->resolveToken(&resolvedToken);
arg = impTokenToHandle(&resolvedToken);
}
else
#endif
{
arg = gtNewIconEmbMethHndNode(info.compMethodHnd);
}
GenTreeArgList* args = gtNewArgList(arg);
GenTree* call = gtNewHelperCallNode(CORINFO_HELP_BBT_FCN_ENTER, TYP_VOID, args);
// Get the address of the first blocks ExecutionCount
size_t addrOfFirstExecutionCount = (size_t)&bbProfileBufferStart->ExecutionCount;
// Read Basic-Block count value
GenTree* valueNode = gtNewIndOfIconHandleNode(TYP_INT, addrOfFirstExecutionCount, GTF_ICON_BBC_PTR, false);
// Compare Basic-Block count value against zero
GenTree* relop = gtNewOperNode(GT_NE, TYP_INT, valueNode, gtNewIconNode(0, TYP_INT));
GenTree* colon = new (this, GT_COLON) GenTreeColon(TYP_VOID, gtNewNothingNode(), call);
GenTree* cond = gtNewQmarkNode(TYP_VOID, relop, colon);
stmt = gtNewStmt(cond);
}
fgEnsureFirstBBisScratch();
fgInsertStmtAtEnd(fgFirstBB, stmt);
}
/*****************************************************************************
*
* Create a basic block and append it to the current BB list.
*/
BasicBlock* Compiler::fgNewBasicBlock(BBjumpKinds jumpKind)
{
// This method must not be called after the exception table has been
// constructed, because it doesn't not provide support for patching
// the exception table.
noway_assert(compHndBBtabCount == 0);
BasicBlock* block;
/* Allocate the block descriptor */
block = bbNewBasicBlock(jumpKind);
noway_assert(block->bbJumpKind == jumpKind);
/* Append the block to the end of the global basic block list */
if (fgFirstBB)
{
fgLastBB->setNext(block);
}
else
{
fgFirstBB = block;
block->bbPrev = nullptr;
}
fgLastBB = block;
return block;
}
/*****************************************************************************
*
* Ensures that fgFirstBB is a scratch BasicBlock that we have added.
* This can be used to add initialization code (without worrying
* about other blocks jumping to it).
*
* Callers have to be careful that they do not mess up the order of things
* added to fgEnsureFirstBBisScratch in a way as to change semantics.
*/
void Compiler::fgEnsureFirstBBisScratch()
{
// This method does not update predecessor lists and so must only be called before they are computed.
assert(!fgComputePredsDone);
// Have we already allocated a scratch block?
if (fgFirstBBisScratch())
{
return;
}
assert(fgFirstBBScratch == nullptr);
BasicBlock* block = bbNewBasicBlock(BBJ_NONE);
if (fgFirstBB != nullptr)
{
// If we have profile data the new block will inherit fgFirstBlock's weight
if (fgFirstBB->hasProfileWeight())
{
block->inheritWeight(fgFirstBB);
}
fgInsertBBbefore(fgFirstBB, block);
}
else
{
noway_assert(fgLastBB == nullptr);
fgFirstBB = block;
fgLastBB = block;
}
noway_assert(fgLastBB != nullptr);
block->bbFlags |= (BBF_INTERNAL | BBF_IMPORTED);
fgFirstBBScratch = fgFirstBB;
#ifdef DEBUG
if (verbose)
{
printf("New scratch " FMT_BB "\n", block->bbNum);
}
#endif
}
bool Compiler::fgFirstBBisScratch()
{
if (fgFirstBBScratch != nullptr)
{
assert(fgFirstBBScratch == fgFirstBB);
assert(fgFirstBBScratch->bbFlags & BBF_INTERNAL);
assert(fgFirstBBScratch->countOfInEdges() == 1);
// Normally, the first scratch block is a fall-through block. However, if the block after it was an empty
// BBJ_ALWAYS block, it might get removed, and the code that removes it will make the first scratch block
// a BBJ_ALWAYS block.
assert((fgFirstBBScratch->bbJumpKind == BBJ_NONE) || (fgFirstBBScratch->bbJumpKind == BBJ_ALWAYS));
return true;
}
else
{
return false;
}
}
bool Compiler::fgBBisScratch(BasicBlock* block)
{
return fgFirstBBisScratch() && (block == fgFirstBB);
}
#ifdef DEBUG
// Check to see if block contains a statement but don't spend more than a certain
// budget doing this per method compiled.
// If the budget is exceeded, return 'answerOnBoundExceeded' as the answer.
/* static */
bool Compiler::fgBlockContainsStatementBounded(BasicBlock* block, GenTree* stmt, bool answerOnBoundExceeded /*= true*/)
{
const __int64 maxLinks = 1000000000;
assert(stmt->gtOper == GT_STMT);
__int64* numTraversed = &JitTls::GetCompiler()->compNumStatementLinksTraversed;
if (*numTraversed > maxLinks)
{
return answerOnBoundExceeded;
}
GenTree* curr = block->firstStmt();
do
{
(*numTraversed)++;
if (curr == stmt)
{
break;
}
curr = curr->gtNext;
} while (curr);
return curr != nullptr;
}
#endif // DEBUG
//------------------------------------------------------------------------
// fgInsertStmtAtBeg: Insert the given tree or statement at the start of the given basic block.
//
// Arguments:
// block - The block into which 'stmt' will be inserted.
// stmt - The statement to be inserted.
//
// Return Value:
// Returns the new (potentially) GT_STMT node.
//
// Notes:
// If 'stmt' is not already a statement, a new statement is created from it.
// We always insert phi statements at the beginning.
// In other cases, if there are any phi assignments and/or an assignment of
// the GT_CATCH_ARG, we insert after those.
GenTree* Compiler::fgInsertStmtAtBeg(BasicBlock* block, GenTree* stmt)
{
if (stmt->gtOper != GT_STMT)
{
stmt = gtNewStmt(stmt);
}
GenTree* list = block->firstStmt();
if (!stmt->IsPhiDefnStmt())
{
GenTree* insertBeforeStmt = block->FirstNonPhiDefOrCatchArgAsg();
if (insertBeforeStmt != nullptr)
{
return fgInsertStmtBefore(block, insertBeforeStmt, stmt);
}
else if (list != nullptr)
{
return fgInsertStmtAtEnd(block, stmt);
}
// Otherwise, we will simply insert at the beginning, below.
}
/* The new tree will now be the first one of the block */
block->bbTreeList = stmt;
stmt->gtNext = list;
/* Are there any statements in the block? */
if (list)
{
GenTree* last;
/* There is at least one statement already */
last = list->gtPrev;
noway_assert(last && last->gtNext == nullptr);
/* Insert the statement in front of the first one */
list->gtPrev = stmt;
stmt->gtPrev = last;
}
else
{
/* The block was completely empty */
stmt->gtPrev = stmt;
}
return stmt;
}
/*****************************************************************************
*
* Insert the given tree or statement at the end of the given basic block.
* Returns the (potentially) new GT_STMT node.
* If the block can be a conditional block, use fgInsertStmtNearEnd.
*/
GenTreeStmt* Compiler::fgInsertStmtAtEnd(BasicBlock* block, GenTree* node)
{
GenTree* list = block->firstStmt();
GenTreeStmt* stmt;
if (node->gtOper != GT_STMT)
{
stmt = gtNewStmt(node);
}
else
{
stmt = node->AsStmt();
}
assert(stmt->gtNext == nullptr); // We don't set it, and it needs to be this after the insert
if (list)
{
GenTree* last;
/* There is at least one statement already */
last = list->gtPrev;
noway_assert(last && last->gtNext == nullptr);
/* Append the statement after the last one */
last->gtNext = stmt;
stmt->gtPrev = last;
list->gtPrev = stmt;
}
else
{
/* The block is completely empty */
block->bbTreeList = stmt;
stmt->gtPrev = stmt;
}
return stmt;
}
/*****************************************************************************
*
* Insert the given tree or statement at the end of the given basic block, but before
* the GT_JTRUE, if present.
* Returns the (potentially) new GT_STMT node.
*/
GenTreeStmt* Compiler::fgInsertStmtNearEnd(BasicBlock* block, GenTree* node)
{
GenTreeStmt* stmt;
// This routine can only be used when in tree order.
assert(fgOrder == FGOrderTree);
if ((block->bbJumpKind == BBJ_COND) || (block->bbJumpKind == BBJ_SWITCH) || (block->bbJumpKind == BBJ_RETURN))
{
if (node->gtOper != GT_STMT)
{
stmt = gtNewStmt(node);
}
else
{
stmt = node->AsStmt();
}
GenTreeStmt* first = block->firstStmt();
noway_assert(first);
GenTreeStmt* last = block->lastStmt();
noway_assert(last && last->gtNext == nullptr);
GenTree* after = last->gtPrev;
#if DEBUG
if (block->bbJumpKind == BBJ_COND)
{
noway_assert(last->gtStmtExpr->gtOper == GT_JTRUE);
}
else if (block->bbJumpKind == BBJ_RETURN)
{
noway_assert((last->gtStmtExpr->gtOper == GT_RETURN) || (last->gtStmtExpr->gtOper == GT_JMP) ||
// BBJ_RETURN blocks in functions returning void do not get a GT_RETURN node if they
// have a .tail prefix (even if canTailCall returns false for these calls)
// code:Compiler::impImportBlockCode (search for the RET: label)
// Ditto for real tail calls (all code after them has been removed)
((last->gtStmtExpr->gtOper == GT_CALL) &&
((info.compRetType == TYP_VOID) || last->gtStmtExpr->AsCall()->IsTailCall())));
}
else
{
noway_assert(block->bbJumpKind == BBJ_SWITCH);
noway_assert(last->gtStmtExpr->gtOper == GT_SWITCH);
}
#endif // DEBUG
/* Append 'stmt' before 'last' */
stmt->gtNext = last;
last->gtPrev = stmt;
if (first == last)
{
/* There is only one stmt in the block */
block->bbTreeList = stmt;
stmt->gtPrev = last;
}
else
{
noway_assert(after && (after->gtNext == last));
/* Append 'stmt' after 'after' */
after->gtNext = stmt;
stmt->gtPrev = after;
}
return stmt;
}
else
{
return fgInsertStmtAtEnd(block, node);
}
}
/*****************************************************************************
*
* Insert the given statement "stmt" after GT_STMT node "insertionPoint".
* Returns the newly inserted GT_STMT node.
* Note that the gtPrev list of statement nodes is circular, but the gtNext list is not.
*/
GenTree* Compiler::fgInsertStmtAfter(BasicBlock* block, GenTree* insertionPoint, GenTree* stmt)
{
assert(block->bbTreeList != nullptr);
noway_assert(insertionPoint->gtOper == GT_STMT);
noway_assert(stmt->gtOper == GT_STMT);
assert(fgBlockContainsStatementBounded(block, insertionPoint));
assert(!fgBlockContainsStatementBounded(block, stmt, false));
if (insertionPoint->gtNext == nullptr)
{
// Ok, we want to insert after the last statement of the block.
stmt->gtNext = nullptr;
stmt->gtPrev = insertionPoint;
insertionPoint->gtNext = stmt;
// Update the backward link of the first statement of the block
// to point to the new last statement.
assert(block->bbTreeList->gtPrev == insertionPoint);
block->bbTreeList->gtPrev = stmt;
}
else
{
stmt->gtNext = insertionPoint->gtNext;
stmt->gtPrev = insertionPoint;
insertionPoint->gtNext->gtPrev = stmt;
insertionPoint->gtNext = stmt;
}
return stmt;
}
// Insert the given tree or statement before GT_STMT node "insertionPoint".
// Returns the newly inserted GT_STMT node.
GenTree* Compiler::fgInsertStmtBefore(BasicBlock* block, GenTree* insertionPoint, GenTree* stmt)
{
assert(block->bbTreeList != nullptr);
noway_assert(insertionPoint->gtOper == GT_STMT);
noway_assert(stmt->gtOper == GT_STMT);
assert(fgBlockContainsStatementBounded(block, insertionPoint));
assert(!fgBlockContainsStatementBounded(block, stmt, false));
if (insertionPoint == block->bbTreeList)
{
// We're inserting before the first statement in the block.
GenTree* list = block->bbTreeList;
GenTree* last = list->gtPrev;
stmt->gtNext = list;
stmt->gtPrev = last;
block->bbTreeList = stmt;
list->gtPrev = stmt;
}
else
{
stmt->gtNext = insertionPoint;
stmt->gtPrev = insertionPoint->gtPrev;
insertionPoint->gtPrev->gtNext = stmt;
insertionPoint->gtPrev = stmt;
}
return stmt;
}
/*****************************************************************************
*
* Insert the list of statements stmtList after the stmtAfter in block.
* Return the last statement stmtList.
*/
GenTree* Compiler::fgInsertStmtListAfter(BasicBlock* block, // the block where stmtAfter is in.
GenTree* stmtAfter, // the statement where stmtList should be inserted
// after.
GenTree* stmtList)
{
// Currently we can handle when stmtAfter and stmtList are non-NULL. This makes everything easy.
noway_assert(stmtAfter && stmtAfter->gtOper == GT_STMT);
noway_assert(stmtList && stmtList->gtOper == GT_STMT);
GenTree* stmtLast = stmtList->gtPrev; // Last statement in a non-empty list, circular in the gtPrev list.
noway_assert(stmtLast);
noway_assert(stmtLast->gtNext == nullptr);
GenTree* stmtNext = stmtAfter->gtNext;
if (!stmtNext)
{
stmtAfter->gtNext = stmtList;
stmtList->gtPrev = stmtAfter;
block->bbTreeList->gtPrev = stmtLast;
goto _Done;
}
stmtAfter->gtNext = stmtList;
stmtList->gtPrev = stmtAfter;
stmtLast->gtNext = stmtNext;
stmtNext->gtPrev = stmtLast;
_Done:
noway_assert(block->bbTreeList == nullptr || block->bbTreeList->gtPrev->gtNext == nullptr);
return stmtLast;
}
/*
Removes a block from the return block list
*/
void Compiler::fgRemoveReturnBlock(BasicBlock* block)
{
if (fgReturnBlocks == nullptr)
{
return;
}
if (fgReturnBlocks->block == block)
{
// It's the 1st entry, assign new head of list.
fgReturnBlocks = fgReturnBlocks->next;
return;
}
for (BasicBlockList* retBlocks = fgReturnBlocks; retBlocks->next != nullptr; retBlocks = retBlocks->next)
{
if (retBlocks->next->block == block)
{
// Found it; splice it out.
retBlocks->next = retBlocks->next->next;
return;
}
}
}
//------------------------------------------------------------------------
// fgGetPredForBlock: Find and return the predecessor edge corresponding to a given predecessor block.
//
// Arguments:
// block -- The block with the predecessor list to operate on.
// blockPred -- The predecessor block to find in the predecessor list.
//
// Return Value:
// The flowList edge corresponding to "blockPred". If "blockPred" is not in the predecessor list of "block",
// then returns nullptr.
//
// Assumptions:
// -- This only works on the full predecessor lists, not the cheap preds lists.
flowList* Compiler::fgGetPredForBlock(BasicBlock* block, BasicBlock* blockPred)
{
assert(block);
assert(blockPred);
assert(!fgCheapPredsValid);
flowList* pred;
for (pred = block->bbPreds; pred != nullptr; pred = pred->flNext)
{
if (blockPred == pred->flBlock)
{
return pred;
}
}
return nullptr;
}
//------------------------------------------------------------------------
// fgGetPredForBlock: Find and return the predecessor edge corresponding to a given predecessor block.
// Also returns the address of the pointer that points to this edge, to make it possible to remove this edge from the
// predecessor list without doing another linear search over the edge list.
//
// Arguments:
// block -- The block with the predecessor list to operate on.
// blockPred -- The predecessor block to find in the predecessor list.
// ptrToPred -- Out parameter: set to the address of the pointer that points to the returned predecessor edge.
//
// Return Value:
// The flowList edge corresponding to "blockPred". If "blockPred" is not in the predecessor list of "block",
// then returns nullptr.
//
// Assumptions:
// -- This only works on the full predecessor lists, not the cheap preds lists.
flowList* Compiler::fgGetPredForBlock(BasicBlock* block, BasicBlock* blockPred, flowList*** ptrToPred)
{
assert(block);
assert(blockPred);
assert(ptrToPred);
assert(!fgCheapPredsValid);
flowList** predPrevAddr;
flowList* pred;
for (predPrevAddr = &block->bbPreds, pred = *predPrevAddr; pred != nullptr;
predPrevAddr = &pred->flNext, pred = *predPrevAddr)
{
if (blockPred == pred->flBlock)
{
*ptrToPred = predPrevAddr;
return pred;
}
}
*ptrToPred = nullptr;
return nullptr;
}
//------------------------------------------------------------------------
// fgSpliceOutPred: Removes a predecessor edge for a block from the predecessor list.
//
// Arguments:
// block -- The block with the predecessor list to operate on.
// blockPred -- The predecessor block to remove from the predecessor list. It must be a predecessor of "block".
//
// Return Value:
// The flowList edge that was removed.
//
// Assumptions:
// -- "blockPred" must be a predecessor block of "block".
// -- This simply splices out the flowList object. It doesn't update block ref counts, handle duplicate counts, etc.
// For that, use fgRemoveRefPred() or fgRemoveAllRefPred().
// -- This only works on the full predecessor lists, not the cheap preds lists.
//
// Notes:
// -- This must walk the predecessor list to find the block in question. If the predecessor edge
// is found using fgGetPredForBlock(), consider using the version that hands back the predecessor pointer
// address instead, to avoid this search.
// -- Marks fgModified = true, since the flow graph has changed.
flowList* Compiler::fgSpliceOutPred(BasicBlock* block, BasicBlock* blockPred)
{
assert(!fgCheapPredsValid);
noway_assert(block->bbPreds);
flowList* oldEdge = nullptr;
// Is this the first block in the pred list?
if (blockPred == block->bbPreds->flBlock)
{
oldEdge = block->bbPreds;
block->bbPreds = block->bbPreds->flNext;
}
else
{
flowList* pred;
for (pred = block->bbPreds; (pred->flNext != nullptr) && (blockPred != pred->flNext->flBlock);
pred = pred->flNext)
{
// empty
}
oldEdge = pred->flNext;
if (oldEdge == nullptr)
{
noway_assert(!"Should always find the blockPred");
}
pred->flNext = pred->flNext->flNext;
}
// Any changes to the flow graph invalidate the dominator sets.
fgModified = true;
return oldEdge;
}
//------------------------------------------------------------------------
// fgAddRefPred: Increment block->bbRefs by one and add "blockPred" to the predecessor list of "block".
//
// Arguments:
// block -- A block to operate on.
// blockPred -- The predecessor block to add to the predecessor list.
// oldEdge -- Optional (default: nullptr). If non-nullptr, and a new edge is created (and the dup count
// of an existing edge is not just incremented), the edge weights are copied from this edge.
// initializingPreds -- Optional (default: false). Only set to "true" when the initial preds computation is
// happening.
//
// Return Value:
// The flow edge representing the predecessor.
//
// Assumptions:
// -- This only works on the full predecessor lists, not the cheap preds lists.
//
// Notes:
// -- block->bbRefs is incremented by one to account for the reduction in incoming edges.
// -- block->bbRefs is adjusted even if preds haven't been computed. If preds haven't been computed,
// the preds themselves aren't touched.
// -- fgModified is set if a new flow edge is created (but not if an existing flow edge dup count is incremented),
// indicating that the flow graph shape has changed.
flowList* Compiler::fgAddRefPred(BasicBlock* block,
BasicBlock* blockPred,
flowList* oldEdge /* = nullptr */,
bool initializingPreds /* = false */)
{
assert(block != nullptr);
assert(blockPred != nullptr);
block->bbRefs++;
if (!fgComputePredsDone && !initializingPreds)
{
// Why is someone trying to update the preds list when the preds haven't been created?
// Ignore them! This can happen when fgMorph is called before the preds list is created.
return nullptr;
}
assert(!fgCheapPredsValid);
flowList* flow;
// Keep the predecessor list in lowest to highest bbNum order. This allows us to discover the loops in
// optFindNaturalLoops from innermost to outermost.
//
// TODO-Throughput: Inserting an edge for a block in sorted order requires searching every existing edge.
// Thus, inserting all the edges for a block is quadratic in the number of edges. We need to either
// not bother sorting for debuggable code, or sort in optFindNaturalLoops, or better, make the code in
// optFindNaturalLoops not depend on order. This also requires ensuring that nobody else has taken a
// dependency on this order. Note also that we don't allow duplicates in the list; we maintain a flDupCount
// count of duplication. This also necessitates walking the flow list for every edge we add.
flowList** listp = &block->bbPreds;
while ((*listp != nullptr) && ((*listp)->flBlock->bbNum < blockPred->bbNum))
{
listp = &(*listp)->flNext;
}
if ((*listp != nullptr) && ((*listp)->flBlock == blockPred))
{
// The predecessor block already exists in the flow list; simply add to its duplicate count.
flow = *listp;
noway_assert(flow->flDupCount > 0);
flow->flDupCount++;
}
else
{
flow = new (this, CMK_FlowList) flowList();
#if MEASURE_BLOCK_SIZE
genFlowNodeCnt += 1;
genFlowNodeSize += sizeof(flowList);
#endif // MEASURE_BLOCK_SIZE
// Any changes to the flow graph invalidate the dominator sets.
fgModified = true;
// Insert the new edge in the list in the correct ordered location.
flow->flNext = *listp;
*listp = flow;
flow->flBlock = blockPred;
flow->flDupCount = 1;
if (fgHaveValidEdgeWeights)
{
// We are creating an edge from blockPred to block
// and we have already computed the edge weights, so
// we will try to setup this new edge with valid edge weights.
//
if (oldEdge != nullptr)
{
// If our caller has given us the old edge weights
// then we will use them.
//
flow->flEdgeWeightMin = oldEdge->flEdgeWeightMin;
flow->flEdgeWeightMax = oldEdge->flEdgeWeightMax;
}
else
{
// Set the max edge weight to be the minimum of block's or blockPred's weight
//
flow->flEdgeWeightMax = min(block->bbWeight, blockPred->bbWeight);
// If we are inserting a conditional block the minimum weight is zero,
// otherwise it is the same as the edge's max weight.
if (blockPred->NumSucc() > 1)
{
flow->flEdgeWeightMin = BB_ZERO_WEIGHT;
}
else
{
flow->flEdgeWeightMin = flow->flEdgeWeightMax;
}
}
}
else
{
flow->flEdgeWeightMin = BB_ZERO_WEIGHT;
flow->flEdgeWeightMax = BB_MAX_WEIGHT;
}
}
return flow;
}
//------------------------------------------------------------------------
// fgRemoveRefPred: Decrements the reference count of a predecessor edge from "blockPred" to "block",
// removing the edge if it is no longer necessary.
//
// Arguments:
// block -- A block to operate on.
// blockPred -- The predecessor block to remove from the predecessor list. It must be a predecessor of "block".
//
// Return Value:
// If the flow edge was removed (the predecessor has a "dup count" of 1),
// returns the flow graph edge that was removed. This means "blockPred" is no longer a predecessor of "block".
// Otherwise, returns nullptr. This means that "blockPred" is still a predecessor of "block" (because "blockPred"
// is a switch with multiple cases jumping to "block", or a BBJ_COND with both conditional and fall-through
// paths leading to "block").
//
// Assumptions:
// -- "blockPred" must be a predecessor block of "block".
// -- This only works on the full predecessor lists, not the cheap preds lists.
//
// Notes:
// -- block->bbRefs is decremented by one to account for the reduction in incoming edges.
// -- block->bbRefs is adjusted even if preds haven't been computed. If preds haven't been computed,
// the preds themselves aren't touched.
// -- fgModified is set if a flow edge is removed (but not if an existing flow edge dup count is decremented),
// indicating that the flow graph shape has changed.
flowList* Compiler::fgRemoveRefPred(BasicBlock* block, BasicBlock* blockPred)
{
noway_assert(block != nullptr);
noway_assert(blockPred != nullptr);
noway_assert(block->countOfInEdges() > 0);
block->bbRefs--;
// Do nothing if we haven't calculated the predecessor list yet.
// Yes, this does happen.
// For example the predecessor lists haven't been created yet when we do fgMorph.
// But fgMorph calls fgFoldConditional, which in turn calls fgRemoveRefPred.
if (!fgComputePredsDone)
{
return nullptr;
}
assert(!fgCheapPredsValid);
flowList** ptrToPred;
flowList* pred = fgGetPredForBlock(block, blockPred, &ptrToPred);
noway_assert(pred);
noway_assert(pred->flDupCount > 0);
pred->flDupCount--;
if (pred->flDupCount == 0)
{
// Splice out the predecessor edge since it's no longer necessary.
*ptrToPred = pred->flNext;
// Any changes to the flow graph invalidate the dominator sets.
fgModified = true;
return pred;
}
else
{
return nullptr;
}
}
//------------------------------------------------------------------------
// fgRemoveAllRefPreds: Removes a predecessor edge from one block to another, no matter what the "dup count" is.
//
// Arguments:
// block -- A block to operate on.
// blockPred -- The predecessor block to remove from the predecessor list. It must be a predecessor of "block".
//
// Return Value:
// Returns the flow graph edge that was removed. The dup count on the edge is no longer valid.
//
// Assumptions:
// -- "blockPred" must be a predecessor block of "block".
// -- This only works on the full predecessor lists, not the cheap preds lists.
//
// Notes:
// block->bbRefs is decremented to account for the reduction in incoming edges.
flowList* Compiler::fgRemoveAllRefPreds(BasicBlock* block, BasicBlock* blockPred)
{
assert(block != nullptr);
assert(blockPred != nullptr);
assert(fgComputePredsDone);
assert(!fgCheapPredsValid);
assert(block->countOfInEdges() > 0);
flowList** ptrToPred;
flowList* pred = fgGetPredForBlock(block, blockPred, &ptrToPred);
assert(pred != nullptr);
assert(pred->flDupCount > 0);
assert(block->bbRefs >= pred->flDupCount);
block->bbRefs -= pred->flDupCount;
// Now splice out the predecessor edge.
*ptrToPred = pred->flNext;
// Any changes to the flow graph invalidate the dominator sets.
fgModified = true;
return pred;
}
//------------------------------------------------------------------------
// fgRemoveAllRefPreds: Remove a predecessor edge, given the address of a pointer to it in the
// predecessor list, no matter what the "dup count" is.
//
// Arguments:
// block -- A block with the predecessor list to operate on.
// ptrToPred -- The address of a pointer to the predecessor to remove.
//
// Return Value:
// The removed predecessor edge. The dup count on the edge is no longer valid.
//
// Assumptions:
// -- The predecessor edge must be in the predecessor list for "block".
// -- This only works on the full predecessor lists, not the cheap preds lists.
//
// Notes:
// block->bbRefs is decremented by the dup count of the predecessor edge, to account for the reduction in incoming
// edges.
flowList* Compiler::fgRemoveAllRefPreds(BasicBlock* block, flowList** ptrToPred)
{
assert(block != nullptr);
assert(ptrToPred != nullptr);
assert(fgComputePredsDone);
assert(!fgCheapPredsValid);
assert(block->countOfInEdges() > 0);
flowList* pred = *ptrToPred;
assert(pred != nullptr);
assert(pred->flDupCount > 0);
assert(block->bbRefs >= pred->flDupCount);
block->bbRefs -= pred->flDupCount;
// Now splice out the predecessor edge.
*ptrToPred = pred->flNext;
// Any changes to the flow graph invalidate the dominator sets.
fgModified = true;
return pred;
}
/*
Removes all the appearances of block as predecessor of others
*/
void Compiler::fgRemoveBlockAsPred(BasicBlock* block)
{
assert(!fgCheapPredsValid);
PREFIX_ASSUME(block != nullptr);
BasicBlock* bNext;
switch (block->bbJumpKind)
{
case BBJ_CALLFINALLY:
if (!(block->bbFlags & BBF_RETLESS_CALL))
{
assert(block->isBBCallAlwaysPair());
/* The block after the BBJ_CALLFINALLY block is not reachable */
bNext = block->bbNext;
/* bNext is an unreachable BBJ_ALWAYS block */
noway_assert(bNext->bbJumpKind == BBJ_ALWAYS);
while (bNext->countOfInEdges() > 0)
{
fgRemoveRefPred(bNext, bNext->bbPreds->flBlock);
}
}
__fallthrough;
case BBJ_COND:
case BBJ_ALWAYS:
case BBJ_EHCATCHRET:
/* Update the predecessor list for 'block->bbJumpDest' and 'block->bbNext' */
fgRemoveRefPred(block->bbJumpDest, block);
if (block->bbJumpKind != BBJ_COND)
{
break;
}
/* If BBJ_COND fall through */
__fallthrough;
case BBJ_NONE:
/* Update the predecessor list for 'block->bbNext' */
fgRemoveRefPred(block->bbNext, block);
break;
case BBJ_EHFILTERRET:
block->bbJumpDest->bbRefs++; // To compensate the bbRefs-- inside fgRemoveRefPred
fgRemoveRefPred(block->bbJumpDest, block);
break;
case BBJ_EHFINALLYRET:
{
/* Remove block as the predecessor of the bbNext of all
BBJ_CALLFINALLY blocks calling this finally. No need
to look for BBJ_CALLFINALLY for fault handlers. */
unsigned hndIndex = block->getHndIndex();
EHblkDsc* ehDsc = ehGetDsc(hndIndex);
if (ehDsc->HasFinallyHandler())
{
BasicBlock* begBlk;
BasicBlock* endBlk;
ehGetCallFinallyBlockRange(hndIndex, &begBlk, &endBlk);
BasicBlock* finBeg = ehDsc->ebdHndBeg;
for (BasicBlock* bcall = begBlk; bcall != endBlk; bcall = bcall->bbNext)
{
if ((bcall->bbFlags & BBF_REMOVED) || bcall->bbJumpKind != BBJ_CALLFINALLY ||
bcall->bbJumpDest != finBeg)
{
continue;
}
assert(bcall->isBBCallAlwaysPair());
fgRemoveRefPred(bcall->bbNext, block);
}
}
}
break;
case BBJ_THROW:
case BBJ_RETURN:
break;
case BBJ_SWITCH:
{
unsigned jumpCnt = block->bbJumpSwt->bbsCount;
BasicBlock** jumpTab = block->bbJumpSwt->bbsDstTab;
do
{
fgRemoveRefPred(*jumpTab, block);
} while (++jumpTab, --jumpCnt);
break;
}
default:
noway_assert(!"Block doesn't have a valid bbJumpKind!!!!");
break;
}
}
/*****************************************************************************
* fgChangeSwitchBlock:
*
* We have a BBJ_SWITCH jump at 'oldSwitchBlock' and we want to move this
* switch jump over to 'newSwitchBlock'. All of the blocks that are jumped
* to from jumpTab[] need to have their predecessor lists updated by removing
* the 'oldSwitchBlock' and adding 'newSwitchBlock'.
*/
void Compiler::fgChangeSwitchBlock(BasicBlock* oldSwitchBlock, BasicBlock* newSwitchBlock)
{
noway_assert(oldSwitchBlock != nullptr);
noway_assert(newSwitchBlock != nullptr);
noway_assert(oldSwitchBlock->bbJumpKind == BBJ_SWITCH);
unsigned jumpCnt = oldSwitchBlock->bbJumpSwt->bbsCount;
BasicBlock** jumpTab = oldSwitchBlock->bbJumpSwt->bbsDstTab;
unsigned i;
// Walk the switch's jump table, updating the predecessor for each branch.
for (i = 0; i < jumpCnt; i++)
{
BasicBlock* bJump = jumpTab[i];
noway_assert(bJump != nullptr);
// Note that if there are duplicate branch targets in the switch jump table,
// fgRemoveRefPred()/fgAddRefPred() will do the right thing: the second and
// subsequent duplicates will simply subtract from and add to the duplicate
// count (respectively).
//
// Remove the old edge [oldSwitchBlock => bJump]
//
fgRemoveRefPred(bJump, oldSwitchBlock);
//
// Create the new edge [newSwitchBlock => bJump]
//
fgAddRefPred(bJump, newSwitchBlock);
}
if (m_switchDescMap != nullptr)
{
SwitchUniqueSuccSet uniqueSuccSet;
// If already computed and cached the unique descriptors for the old block, let's
// update those for the new block.
if (m_switchDescMap->Lookup(oldSwitchBlock, &uniqueSuccSet))
{
m_switchDescMap->Set(newSwitchBlock, uniqueSuccSet);
}
else
{
fgInvalidateSwitchDescMapEntry(newSwitchBlock);
}
fgInvalidateSwitchDescMapEntry(oldSwitchBlock);
}
}
/*****************************************************************************
* fgReplaceSwitchJumpTarget:
*
* We have a BBJ_SWITCH at 'blockSwitch' and we want to replace all entries
* in the jumpTab[] such that so that jumps that previously went to
* 'oldTarget' now go to 'newTarget'.
* We also must update the predecessor lists for 'oldTarget' and 'newPred'.
*/
void Compiler::fgReplaceSwitchJumpTarget(BasicBlock* blockSwitch, BasicBlock* newTarget, BasicBlock* oldTarget)
{
noway_assert(blockSwitch != nullptr);
noway_assert(newTarget != nullptr);
noway_assert(oldTarget != nullptr);
noway_assert(blockSwitch->bbJumpKind == BBJ_SWITCH);
// For the jump targets values that match oldTarget of our BBJ_SWITCH
// replace predecessor 'blockSwitch' with 'newTarget'
//
unsigned jumpCnt = blockSwitch->bbJumpSwt->bbsCount;
BasicBlock** jumpTab = blockSwitch->bbJumpSwt->bbsDstTab;
unsigned i = 0;
// Walk the switch's jump table looking for blocks to update the preds for
while (i < jumpCnt)
{
if (jumpTab[i] == oldTarget) // We will update when jumpTab[i] matches
{
// Remove the old edge [oldTarget from blockSwitch]
//
fgRemoveAllRefPreds(oldTarget, blockSwitch);
//
// Change the jumpTab entry to branch to the new location
//
jumpTab[i] = newTarget;
//
// Create the new edge [newTarget from blockSwitch]
//
flowList* newEdge = fgAddRefPred(newTarget, blockSwitch);
// Now set the correct value of newEdge->flDupCount
// and replace any other jumps in jumpTab[] that go to oldTarget.
//
i++;
while (i < jumpCnt)
{
if (jumpTab[i] == oldTarget)
{
//
// We also must update this entry in the jumpTab
//
jumpTab[i] = newTarget;
newTarget->bbRefs++;
//
// Increment the flDupCount
//
newEdge->flDupCount++;
}
i++; // Check the next entry in jumpTab[]
}
// Maintain, if necessary, the set of unique targets of "block."
UpdateSwitchTableTarget(blockSwitch, oldTarget, newTarget);
// Make sure the new target has the proper bits set for being a branch target.
newTarget->bbFlags |= BBF_HAS_LABEL | BBF_JMP_TARGET;
return; // We have replaced the jumps to oldTarget with newTarget
}
i++; // Check the next entry in jumpTab[] for a match
}
noway_assert(!"Did not find oldTarget in jumpTab[]");
}
//------------------------------------------------------------------------
// Compiler::fgReplaceJumpTarget: For a given block, replace the target 'oldTarget' with 'newTarget'.
//
// Arguments:
// block - the block in which a jump target will be replaced.
// newTarget - the new branch target of the block.
// oldTarget - the old branch target of the block.
//
// Notes:
// 1. Only branches are changed: BBJ_ALWAYS, the non-fallthrough path of BBJ_COND, BBJ_SWITCH, etc.
// We ignore other block types.
// 2. Only the first target found is updated. If there are multiple ways for a block
// to reach 'oldTarget' (e.g., multiple arms of a switch), only the first one found is changed.
// 3. The predecessor lists are not changed.
// 4. The switch table "unique successor" cache is invalidated.
//
// This function is most useful early, before the full predecessor lists have been computed.
//
void Compiler::fgReplaceJumpTarget(BasicBlock* block, BasicBlock* newTarget, BasicBlock* oldTarget)
{
assert(block != nullptr);
switch (block->bbJumpKind)
{
case BBJ_CALLFINALLY:
case BBJ_COND:
case BBJ_ALWAYS:
case BBJ_EHCATCHRET:
case BBJ_EHFILTERRET:
case BBJ_LEAVE: // This function will be called before import, so we still have BBJ_LEAVE
if (block->bbJumpDest == oldTarget)
{
block->bbJumpDest = newTarget;
}
break;
case BBJ_NONE:
case BBJ_EHFINALLYRET:
case BBJ_THROW:
case BBJ_RETURN:
break;
case BBJ_SWITCH:
unsigned jumpCnt;
jumpCnt = block->bbJumpSwt->bbsCount;
BasicBlock** jumpTab;
jumpTab = block->bbJumpSwt->bbsDstTab;
for (unsigned i = 0; i < jumpCnt; i++)
{
if (jumpTab[i] == oldTarget)
{
jumpTab[i] = newTarget;
break;
}
}
break;
default:
assert(!"Block doesn't have a valid bbJumpKind!!!!");
unreached();
break;
}
}
/*****************************************************************************
* Updates the predecessor list for 'block' by replacing 'oldPred' with 'newPred'.
* Note that a block can only appear once in the preds list (for normal preds, not
* cheap preds): if a predecessor has multiple ways to get to this block, then
* flDupCount will be >1, but the block will still appear exactly once. Thus, this
* function assumes that all branches from the predecessor (practically, that all
* switch cases that target this block) are changed to branch from the new predecessor,
* with the same dup count.
*
* Note that the block bbRefs is not changed, since 'block' has the same number of
* references as before, just from a different predecessor block.
*/
void Compiler::fgReplacePred(BasicBlock* block, BasicBlock* oldPred, BasicBlock* newPred)
{
noway_assert(block != nullptr);
noway_assert(oldPred != nullptr);
noway_assert(newPred != nullptr);
assert(!fgCheapPredsValid);
flowList* pred;
for (pred = block->bbPreds; pred != nullptr; pred = pred->flNext)
{
if (oldPred == pred->flBlock)
{
pred->flBlock = newPred;
break;
}
}
}
/*****************************************************************************
*
* Returns true if block b1 dominates block b2.
*/
bool Compiler::fgDominate(BasicBlock* b1, BasicBlock* b2)
{
noway_assert(fgDomsComputed);
assert(!fgCheapPredsValid);
//
// If the fgModified flag is false then we made some modifications to
// the flow graph, like adding a new block or changing a conditional branch
// into an unconditional branch.
//
// We can continue to use the dominator and reachable information to
// unmark loops as long as we haven't renumbered the blocks or we aren't
// asking for information about a new block
//
if (b2->bbNum > fgDomBBcount)
{
if (b1 == b2)
{
return true;
}
for (flowList* pred = b2->bbPreds; pred != nullptr; pred = pred->flNext)
{
if (!fgDominate(b1, pred->flBlock))
{
return false;
}
}
return b2->bbPreds != nullptr;
}
if (b1->bbNum > fgDomBBcount)
{
// if b1 is a loop preheader and Succ is its only successor, then all predecessors of
// Succ either are b1 itself or are dominated by Succ. Under these conditions, b1
// dominates b2 if and only if Succ dominates b2 (or if b2 == b1, but we already tested
// for this case)
if (b1->bbFlags & BBF_LOOP_PREHEADER)
{
noway_assert(b1->bbFlags & BBF_INTERNAL);
noway_assert(b1->bbJumpKind == BBJ_NONE);
return fgDominate(b1->bbNext, b2);
}
// unknown dominators; err on the safe side and return false
return false;
}
/* Check if b1 dominates b2 */
unsigned numA = b1->bbNum;
noway_assert(numA <= fgDomBBcount);
unsigned numB = b2->bbNum;
noway_assert(numB <= fgDomBBcount);
// What we want to ask here is basically if A is in the middle of the path from B to the root (the entry node)
// in the dominator tree. Turns out that can be translated as:
//
// A dom B <-> preorder(A) <= preorder(B) && postorder(A) >= postorder(B)
//
// where the equality holds when you ask if A dominates itself.
bool treeDom =
fgDomTreePreOrder[numA] <= fgDomTreePreOrder[numB] && fgDomTreePostOrder[numA] >= fgDomTreePostOrder[numB];
return treeDom;
}
/*****************************************************************************
*
* Returns true if block b1 can reach block b2.
*/
bool Compiler::fgReachable(BasicBlock* b1, BasicBlock* b2)
{
noway_assert(fgDomsComputed);
assert(!fgCheapPredsValid);
//
// If the fgModified flag is false then we made some modifications to
// the flow graph, like adding a new block or changing a conditional branch
// into an unconditional branch.
//
// We can continue to use the dominator and reachable information to
// unmark loops as long as we haven't renumbered the blocks or we aren't
// asking for information about a new block
//
if (b2->bbNum > fgDomBBcount)
{
if (b1 == b2)
{
return true;
}
for (flowList* pred = b2->bbPreds; pred != nullptr; pred = pred->flNext)
{
if (fgReachable(b1, pred->flBlock))
{
return true;
}
}
return false;
}
if (b1->bbNum > fgDomBBcount)
{
noway_assert(b1->bbJumpKind == BBJ_NONE || b1->bbJumpKind == BBJ_ALWAYS || b1->bbJumpKind == BBJ_COND);
if (b1->bbFallsThrough() && fgReachable(b1->bbNext, b2))
{
return true;
}
if (b1->bbJumpKind == BBJ_ALWAYS || b1->bbJumpKind == BBJ_COND)
{
return fgReachable(b1->bbJumpDest, b2);
}
return false;
}
/* Check if b1 can reach b2 */
assert(fgReachabilitySetsValid);
assert(BasicBlockBitSetTraits::GetSize(this) == fgDomBBcount + 1);
return BlockSetOps::IsMember(this, b2->bbReach, b1->bbNum);
}
/*****************************************************************************
* Update changed flow graph information.
*
* If the flow graph has changed, we need to recompute various information if we want to use
* it again.
*/
void Compiler::fgUpdateChangedFlowGraph()
{
// We need to clear this so we don't hit an assert calling fgRenumberBlocks().
fgDomsComputed = false;
JITDUMP("\nRenumbering the basic blocks for fgUpdateChangeFlowGraph\n");
fgRenumberBlocks();
fgComputePreds();
fgComputeEnterBlocksSet();
fgComputeReachabilitySets();
fgComputeDoms();
}
/*****************************************************************************
* Compute the bbReach sets.
*
* This can be called to recompute the bbReach sets after the flow graph changes, such as when the
* number of BasicBlocks change (and thus, the BlockSet epoch changes).
*
* Finally, this also sets the BBF_GC_SAFE_POINT flag on blocks.
*
* Assumes the predecessor lists are correct.
*
* TODO-Throughput: This algorithm consumes O(n^2) because we're using dense bitsets to
* represent reachability. While this yields O(1) time queries, it bloats the memory usage
* for large code. We can do better if we try to approach reachability by
* computing the strongly connected components of the flow graph. That way we only need
* linear memory to label every block with its SCC.
*/
void Compiler::fgComputeReachabilitySets()
{
assert(fgComputePredsDone);
assert(!fgCheapPredsValid);
#ifdef DEBUG
fgReachabilitySetsValid = false;
#endif // DEBUG
BasicBlock* block;
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
// Initialize the per-block bbReach sets. It creates a new empty set,
// because the block epoch could change since the previous initialization
// and the old set could have wrong size.
block->bbReach = BlockSetOps::MakeEmpty(this);
/* Mark block as reaching itself */
BlockSetOps::AddElemD(this, block->bbReach, block->bbNum);
}
/* Find the reachable blocks */
// Also, set BBF_GC_SAFE_POINT.
bool change;
BlockSet newReach(BlockSetOps::MakeEmpty(this));
do
{
change = false;
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
BlockSetOps::Assign(this, newReach, block->bbReach);
bool predGcSafe = (block->bbPreds != nullptr); // Do all of our predecessor blocks have a GC safe bit?
for (flowList* pred = block->bbPreds; pred != nullptr; pred = pred->flNext)
{
BasicBlock* predBlock = pred->flBlock;
/* Union the predecessor's reachability set into newReach */
BlockSetOps::UnionD(this, newReach, predBlock->bbReach);
if (!(predBlock->bbFlags & BBF_GC_SAFE_POINT))
{
predGcSafe = false;
}
}
if (predGcSafe)
{
block->bbFlags |= BBF_GC_SAFE_POINT;
}
if (!BlockSetOps::Equal(this, newReach, block->bbReach))
{
BlockSetOps::Assign(this, block->bbReach, newReach);
change = true;
}
}
} while (change);
#ifdef DEBUG
if (verbose)
{
printf("\nAfter computing reachability sets:\n");
fgDispReach();
}
fgReachabilitySetsValid = true;
#endif // DEBUG
}
/*****************************************************************************
* Compute the entry blocks set.
*
* Initialize fgEnterBlks to the set of blocks for which we don't have explicit control
* flow edges. These are the entry basic block and each of the EH handler blocks.
* For ARM, also include the BBJ_ALWAYS block of a BBJ_CALLFINALLY/BBJ_ALWAYS pair,
* to avoid creating "retless" calls, since we need the BBJ_ALWAYS for the purpose
* of unwinding, even if the call doesn't return (due to an explicit throw, for example).
*/
void Compiler::fgComputeEnterBlocksSet()
{
#ifdef DEBUG
fgEnterBlksSetValid = false;
#endif // DEBUG
fgEnterBlks = BlockSetOps::MakeEmpty(this);
/* Now set the entry basic block */
BlockSetOps::AddElemD(this, fgEnterBlks, fgFirstBB->bbNum);
assert(fgFirstBB->bbNum == 1);
if (compHndBBtabCount > 0)
{
/* Also 'or' in the handler basic blocks */
EHblkDsc* HBtab;
EHblkDsc* HBtabEnd;
for (HBtab = compHndBBtab, HBtabEnd = compHndBBtab + compHndBBtabCount; HBtab < HBtabEnd; HBtab++)
{
if (HBtab->HasFilter())
{
BlockSetOps::AddElemD(this, fgEnterBlks, HBtab->ebdFilter->bbNum);
}
BlockSetOps::AddElemD(this, fgEnterBlks, HBtab->ebdHndBeg->bbNum);
}
}
#if FEATURE_EH_FUNCLETS && defined(_TARGET_ARM_)
// TODO-ARM-Cleanup: The ARM code here to prevent creating retless calls by adding the BBJ_ALWAYS
// to the enter blocks is a bit of a compromise, because sometimes the blocks are already reachable,
// and it messes up DFS ordering to have them marked as enter block. We should prevent the
// creation of retless calls some other way.
for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->bbNext)
{
if (block->bbJumpKind == BBJ_CALLFINALLY)
{
assert(block->isBBCallAlwaysPair());
// Don't remove the BBJ_ALWAYS block that is only here for the unwinder. It might be dead
// if the finally is no-return, so mark it as an entry point.
BlockSetOps::AddElemD(this, fgEnterBlks, block->bbNext->bbNum);
}
}
#endif // FEATURE_EH_FUNCLETS && defined(_TARGET_ARM_)
#ifdef DEBUG
if (verbose)
{
printf("Enter blocks: ");
BlockSetOps::Iter iter(this, fgEnterBlks);
unsigned bbNum = 0;
while (iter.NextElem(&bbNum))
{
printf(FMT_BB " ", bbNum);
}
printf("\n");
}
#endif // DEBUG
#ifdef DEBUG
fgEnterBlksSetValid = true;
#endif // DEBUG
}
/*****************************************************************************
* Remove unreachable blocks.
*
* Return true if any unreachable blocks were removed.
*/
bool Compiler::fgRemoveUnreachableBlocks()
{
assert(!fgCheapPredsValid);
assert(fgReachabilitySetsValid);
bool hasLoops = false;
bool hasUnreachableBlocks = false;
BasicBlock* block;
/* Record unreachable blocks */
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
/* Internal throw blocks are also reachable */
if (fgIsThrowHlpBlk(block))
{
goto SKIP_BLOCK;
}
else if (block == genReturnBB)
{
// Don't remove statements for the genReturnBB block, as we might have special hookups there.
// For example, <BUGNUM> in VSW 364383, </BUGNUM>
// the profiler hookup needs to have the "void GT_RETURN" statement
// to properly set the info.compProfilerCallback flag.
goto SKIP_BLOCK;
}
else
{
// If any of the entry blocks can reach this block, then we skip it.
if (!BlockSetOps::IsEmptyIntersection(this, fgEnterBlks, block->bbReach))
{
goto SKIP_BLOCK;
}
}
// Remove all the code for the block
fgUnreachableBlock(block);
// Make sure that the block was marked as removed */
noway_assert(block->bbFlags & BBF_REMOVED);
// Some blocks mark the end of trys and catches
// and can't be removed. We convert these into
// empty blocks of type BBJ_THROW
if (block->bbFlags & BBF_DONT_REMOVE)
{
bool bIsBBCallAlwaysPair = block->isBBCallAlwaysPair();
/* Unmark the block as removed, */
/* clear BBF_INTERNAL as well and set BBJ_IMPORTED */
block->bbFlags &= ~(BBF_REMOVED | BBF_INTERNAL | BBF_NEEDS_GCPOLL);
block->bbFlags |= BBF_IMPORTED;
block->bbJumpKind = BBJ_THROW;
block->bbSetRunRarely();
#if FEATURE_EH_FUNCLETS && defined(_TARGET_ARM_)
// If this is a <BBJ_CALLFINALLY, BBJ_ALWAYS> pair, we have to clear BBF_FINALLY_TARGET flag on
// the target node (of BBJ_ALWAYS) since BBJ_CALLFINALLY node is getting converted to a BBJ_THROW.
if (bIsBBCallAlwaysPair)
{
noway_assert(block->bbNext->bbJumpKind == BBJ_ALWAYS);
fgClearFinallyTargetBit(block->bbNext->bbJumpDest);
}
#endif // FEATURE_EH_FUNCLETS && defined(_TARGET_ARM_)
}
else
{
/* We have to call fgRemoveBlock next */
hasUnreachableBlocks = true;
}
continue;
SKIP_BLOCK:;
// if (block->isRunRarely())
// continue;
if (block->bbJumpKind == BBJ_RETURN)
{
continue;
}
/* Set BBF_LOOP_HEAD if we have backwards branches to this block */
unsigned blockNum = block->bbNum;
for (flowList* pred = block->bbPreds; pred != nullptr; pred = pred->flNext)
{
BasicBlock* predBlock = pred->flBlock;
if (blockNum <= predBlock->bbNum)
{
if (predBlock->bbJumpKind == BBJ_CALLFINALLY)
{
continue;
}
/* If block can reach predBlock then we have a loop head */
if (BlockSetOps::IsMember(this, predBlock->bbReach, blockNum))
{
hasLoops = true;
/* Set the BBF_LOOP_HEAD flag */
block->bbFlags |= BBF_LOOP_HEAD;
break;
}
}
}
}
fgHasLoops = hasLoops;
if (hasUnreachableBlocks)
{
// Now remove the unreachable blocks
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
// If we mark the block with BBF_REMOVED then
// we need to call fgRemovedBlock() on it
if (block->bbFlags & BBF_REMOVED)
{
fgRemoveBlock(block, true);
// When we have a BBJ_CALLFINALLY, BBJ_ALWAYS pair; fgRemoveBlock will remove
// both blocks, so we must advance 1 extra place in the block list
//
if (block->isBBCallAlwaysPair())
{
block = block->bbNext;
}
}
}
}
return hasUnreachableBlocks;
}
/*****************************************************************************
*
* Function called to compute the dominator and reachable sets.
*
* Assumes the predecessor lists are computed and correct.
*/
void Compiler::fgComputeReachability()
{
#ifdef DEBUG
if (verbose)
{
printf("*************** In fgComputeReachability\n");
}
fgVerifyHandlerTab();
// Make sure that the predecessor lists are accurate
assert(fgComputePredsDone);
fgDebugCheckBBlist();
#endif // DEBUG
/* Create a list of all BBJ_RETURN blocks. The head of the list is 'fgReturnBlocks'. */
fgReturnBlocks = nullptr;
for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->bbNext)
{
// If this is a BBJ_RETURN block, add it to our list of all BBJ_RETURN blocks. This list is only
// used to find return blocks.
if (block->bbJumpKind == BBJ_RETURN)
{
fgReturnBlocks = new (this, CMK_Reachability) BasicBlockList(block, fgReturnBlocks);
}
}
// Compute reachability and then delete blocks determined to be unreachable. If we delete blocks, we
// need to loop, as that might have caused more blocks to become unreachable. This can happen in the
// case where a call to a finally is unreachable and deleted (maybe the call to the finally is
// preceded by a throw or an infinite loop), making the blocks following the finally unreachable.
// However, all EH entry blocks are considered global entry blocks, causing the blocks following the
// call to the finally to stay rooted, until a second round of reachability is done.
// The dominator algorithm expects that all blocks can be reached from the fgEnterBlks set.
unsigned passNum = 1;
bool changed;
do
{
// Just to be paranoid, avoid infinite loops; fall back to minopts.
if (passNum > 10)
{
noway_assert(!"Too many unreachable block removal loops");
}
/* Walk the flow graph, reassign block numbers to keep them in ascending order */
JITDUMP("\nRenumbering the basic blocks for fgComputeReachability pass #%u\n", passNum);
passNum++;
fgRenumberBlocks();
//
// Compute fgEnterBlks
//
fgComputeEnterBlocksSet();
//
// Compute bbReach
//
fgComputeReachabilitySets();
//
// Use reachability information to delete unreachable blocks.
// Also, determine if the flow graph has loops and set 'fgHasLoops' accordingly.
// Set the BBF_LOOP_HEAD flag on the block target of backwards branches.
//
changed = fgRemoveUnreachableBlocks();
} while (changed);
#ifdef DEBUG
if (verbose)
{
printf("\nAfter computing reachability:\n");
fgDispBasicBlocks(verboseTrees);
printf("\n");
}
fgVerifyHandlerTab();
fgDebugCheckBBlist(true);
#endif // DEBUG
//
// Now, compute the dominators
//
fgComputeDoms();
}
/** In order to be able to compute dominance, we need to first get a DFS reverse post order sort on the basic flow graph
* for the dominance algorithm to operate correctly. The reason why we need the DFS sort is because
* we will build the dominance sets using the partial order induced by the DFS sorting. With this
* precondition not holding true, the algorithm doesn't work properly.
*/
void Compiler::fgDfsInvPostOrder()
{
// NOTE: This algorithm only pays attention to the actual blocks. It ignores the imaginary entry block.
// visited : Once we run the DFS post order sort recursive algorithm, we mark the nodes we visited to avoid
// backtracking.
BlockSet visited(BlockSetOps::MakeEmpty(this));
// We begin by figuring out which basic blocks don't have incoming edges and mark them as
// start nodes. Later on we run the recursive algorithm for each node that we
// mark in this step.
BlockSet_ValRet_T startNodes = fgDomFindStartNodes();
// Make sure fgEnterBlks are still there in startNodes, even if they participate in a loop (i.e., there is
// an incoming edge into the block).
assert(fgEnterBlksSetValid);
#if FEATURE_EH_FUNCLETS && defined(_TARGET_ARM_)
//
// BlockSetOps::UnionD(this, startNodes, fgEnterBlks);
//
// This causes problems on ARM, because we for BBJ_CALLFINALLY/BBJ_ALWAYS pairs, we add the BBJ_ALWAYS
// to the enter blocks set to prevent flow graph optimizations from removing it and creating retless call finallies
// (BBF_RETLESS_CALL). This leads to an incorrect DFS ordering in some cases, because we start the recursive walk
// from the BBJ_ALWAYS, which is reachable from other blocks. A better solution would be to change ARM to avoid
// creating retless calls in a different way, not by adding BBJ_ALWAYS to fgEnterBlks.
//
// So, let us make sure at least fgFirstBB is still there, even if it participates in a loop.
BlockSetOps::AddElemD(this, startNodes, 1);
assert(fgFirstBB->bbNum == 1);
#else
BlockSetOps::UnionD(this, startNodes, fgEnterBlks);
#endif
assert(BlockSetOps::IsMember(this, startNodes, fgFirstBB->bbNum));
// Call the flowgraph DFS traversal helper.
unsigned postIndex = 1;
for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->bbNext)
{
// If the block has no predecessors, and we haven't already visited it (because it's in fgEnterBlks but also
// reachable from the first block), go ahead and traverse starting from this block.
if (BlockSetOps::IsMember(this, startNodes, block->bbNum) &&
!BlockSetOps::IsMember(this, visited, block->bbNum))
{
fgDfsInvPostOrderHelper(block, visited, &postIndex);
}
}
// After the DFS reverse postorder is completed, we must have visited all the basic blocks.
noway_assert(postIndex == fgBBcount + 1);
noway_assert(fgBBNumMax == fgBBcount);
#ifdef DEBUG
if (0 && verbose)
{
printf("\nAfter doing a post order traversal of the BB graph, this is the ordering:\n");
for (unsigned i = 1; i <= fgBBNumMax; ++i)
{
printf("%02u -> " FMT_BB "\n", i, fgBBInvPostOrder[i]->bbNum);
}
printf("\n");
}
#endif // DEBUG
}
BlockSet_ValRet_T Compiler::fgDomFindStartNodes()
{
unsigned j;
BasicBlock* block;
// startNodes :: A set that represents which basic blocks in the flow graph don't have incoming edges.
// We begin assuming everything is a start block and remove any block that is being referenced by another in its
// successor list.
BlockSet startNodes(BlockSetOps::MakeFull(this));
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
unsigned cSucc = block->NumSucc(this);
for (j = 0; j < cSucc; ++j)
{
BasicBlock* succ = block->GetSucc(j, this);
BlockSetOps::RemoveElemD(this, startNodes, succ->bbNum);
}
}
#ifdef DEBUG
if (verbose)
{
printf("\nDominator computation start blocks (those blocks with no incoming edges):\n");
BlockSetOps::Iter iter(this, startNodes);
unsigned bbNum = 0;
while (iter.NextElem(&bbNum))
{
printf(FMT_BB " ", bbNum);
}
printf("\n");
}
#endif // DEBUG
return startNodes;
}
//------------------------------------------------------------------------
// fgDfsInvPostOrderHelper: Helper to assign post-order numbers to blocks.
//
// Arguments:
// block - The starting entry block
// visited - The set of visited blocks
// count - Pointer to the Dfs counter
//
// Notes:
// Compute a non-recursive DFS traversal of the flow graph using an
// evaluation stack to assign post-order numbers.
void Compiler::fgDfsInvPostOrderHelper(BasicBlock* block, BlockSet& visited, unsigned* count)
{
// Assume we haven't visited this node yet (callers ensure this).
assert(!BlockSetOps::IsMember(this, visited, block->bbNum));
// Allocate a local stack to hold the DFS traversal actions necessary
// to compute pre/post-ordering of the control flowgraph.
ArrayStack<DfsBlockEntry> stack(getAllocator(CMK_ArrayStack));
// Push the first block on the stack to seed the traversal.
stack.Push(DfsBlockEntry(DSS_Pre, block));
// Flag the node we just visited to avoid backtracking.
BlockSetOps::AddElemD(this, visited, block->bbNum);
// The search is terminated once all the actions have been processed.
while (stack.Height() != 0)
{
DfsBlockEntry current = stack.Pop();
BasicBlock* currentBlock = current.dfsBlock;
if (current.dfsStackState == DSS_Pre)
{
// This is a pre-visit that corresponds to the first time the
// node is encountered in the spanning tree and receives pre-order
// numberings. By pushing the post-action on the stack here we
// are guaranteed to only process it after all of its successors
// pre and post actions are processed.
stack.Push(DfsBlockEntry(DSS_Post, currentBlock));
unsigned cSucc = currentBlock->NumSucc(this);
for (unsigned j = 0; j < cSucc; ++j)
{
BasicBlock* succ = currentBlock->GetSucc(j, this);
// If this is a node we haven't seen before, go ahead and process
if (!BlockSetOps::IsMember(this, visited, succ->bbNum))
{
// Push a pre-visit action for this successor onto the stack and
// mark it as visited in case this block has multiple successors
// to the same node (multi-graph).
stack.Push(DfsBlockEntry(DSS_Pre, succ));
BlockSetOps::AddElemD(this, visited, succ->bbNum);
}
}
}
else
{
// This is a post-visit that corresponds to the last time the
// node is visited in the spanning tree and only happens after
// all descendents in the spanning tree have had pre and post
// actions applied.
assert(current.dfsStackState == DSS_Post);
unsigned invCount = fgBBcount - *count + 1;
assert(1 <= invCount && invCount <= fgBBNumMax);
fgBBInvPostOrder[invCount] = currentBlock;
currentBlock->bbDfsNum = invCount;
++(*count);
}
}
}
void Compiler::fgComputeDoms()
{
assert(!fgCheapPredsValid);
#ifdef DEBUG
if (verbose)
{
printf("*************** In fgComputeDoms\n");
}
fgVerifyHandlerTab();
// Make sure that the predecessor lists are accurate.
// Also check that the blocks are properly, densely numbered (so calling fgRenumberBlocks is not necessary).
fgDebugCheckBBlist(true);
// Assert things related to the BlockSet epoch.
assert(fgBBcount == fgBBNumMax);
assert(BasicBlockBitSetTraits::GetSize(this) == fgBBNumMax + 1);
#endif // DEBUG
BlockSet processedBlks(BlockSetOps::MakeEmpty(this));
fgBBInvPostOrder = new (this, CMK_DominatorMemory) BasicBlock*[fgBBNumMax + 1];
memset(fgBBInvPostOrder, 0, sizeof(BasicBlock*) * (fgBBNumMax + 1));
fgDfsInvPostOrder();
noway_assert(fgBBInvPostOrder[0] == nullptr);
// flRoot and bbRoot represent an imaginary unique entry point in the flow graph.
// All the orphaned EH blocks and fgFirstBB will temporarily have its predecessors list
// (with bbRoot as the only basic block in it) set as flRoot.
// Later on, we clear their predecessors and let them to be nullptr again.
// Since we number basic blocks starting at one, the imaginary entry block is conveniently numbered as zero.
flowList flRoot;
BasicBlock bbRoot;
bbRoot.bbPreds = nullptr;
bbRoot.bbNum = 0;
bbRoot.bbIDom = &bbRoot;
bbRoot.bbDfsNum = 0;
bbRoot.bbFlags = 0;
flRoot.flNext = nullptr;
flRoot.flBlock = &bbRoot;
fgBBInvPostOrder[0] = &bbRoot;
// Mark both bbRoot and fgFirstBB processed
BlockSetOps::AddElemD(this, processedBlks, 0); // bbRoot == block #0
BlockSetOps::AddElemD(this, processedBlks, 1); // fgFirstBB == block #1
assert(fgFirstBB->bbNum == 1);
// Special case fgFirstBB to say its IDom is bbRoot.
fgFirstBB->bbIDom = &bbRoot;
BasicBlock* block = nullptr;
for (block = fgFirstBB->bbNext; block != nullptr; block = block->bbNext)
{
// If any basic block has no predecessors then we flag it as processed and temporarily
// mark its precedessor list to be flRoot. This makes the flowgraph connected,
// a precondition that is needed by the dominance algorithm to operate properly.
if (block->bbPreds == nullptr)
{
block->bbPreds = &flRoot;
block->bbIDom = &bbRoot;
BlockSetOps::AddElemD(this, processedBlks, block->bbNum);
}
else
{
block->bbIDom = nullptr;
}
}
// Mark the EH blocks as entry blocks and also flag them as processed.
if (compHndBBtabCount > 0)
{
EHblkDsc* HBtab;
EHblkDsc* HBtabEnd;
for (HBtab = compHndBBtab, HBtabEnd = compHndBBtab + compHndBBtabCount; HBtab < HBtabEnd; HBtab++)
{
if (HBtab->HasFilter())
{
HBtab->ebdFilter->bbIDom = &bbRoot;
BlockSetOps::AddElemD(this, processedBlks, HBtab->ebdFilter->bbNum);
}
HBtab->ebdHndBeg->bbIDom = &bbRoot;
BlockSetOps::AddElemD(this, processedBlks, HBtab->ebdHndBeg->bbNum);
}
}
// Now proceed to compute the immediate dominators for each basic block.
bool changed = true;
while (changed)
{
changed = false;
for (unsigned i = 1; i <= fgBBNumMax;
++i) // Process each actual block; don't process the imaginary predecessor block.
{
flowList* first = nullptr;
BasicBlock* newidom = nullptr;
block = fgBBInvPostOrder[i];
// If we have a block that has bbRoot as its bbIDom
// it means we flag it as processed and as an entry block so
// in this case we're all set.
if (block->bbIDom == &bbRoot)
{
continue;
}
// Pick up the first processed predecesor of the current block.
for (first = block->bbPreds; first != nullptr; first = first->flNext)
{
if (BlockSetOps::IsMember(this, processedBlks, first->flBlock->bbNum))
{
break;
}
}
noway_assert(first != nullptr);
// We assume the first processed predecessor will be the
// immediate dominator and then compute the forward flow analysis.
newidom = first->flBlock;
for (flowList* p = block->bbPreds; p != nullptr; p = p->flNext)
{
if (p->flBlock == first->flBlock)
{
continue;
}
if (p->flBlock->bbIDom != nullptr)
{
// fgIntersectDom is basically the set intersection between
// the dominance sets of the new IDom and the current predecessor
// Since the nodes are ordered in DFS inverse post order and
// IDom induces a tree, fgIntersectDom actually computes
// the lowest common ancestor in the dominator tree.
newidom = fgIntersectDom(p->flBlock, newidom);
}
}
// If the Immediate dominator changed, assign the new one
// to the current working basic block.
if (block->bbIDom != newidom)
{
noway_assert(newidom != nullptr);
block->bbIDom = newidom;
changed = true;
}
BlockSetOps::AddElemD(this, processedBlks, block->bbNum);
}
}
// As stated before, once we have computed immediate dominance we need to clear
// all the basic blocks whose predecessor list was set to flRoot. This
// reverts that and leaves the blocks the same as before.
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
if (block->bbPreds == &flRoot)
{
block->bbPreds = nullptr;
}
}
fgCompDominatedByExceptionalEntryBlocks();
#ifdef DEBUG
if (verbose)
{
fgDispDoms();
}
#endif
fgBuildDomTree();
fgModified = false;
fgDomBBcount = fgBBcount;
assert(fgBBcount == fgBBNumMax);
assert(BasicBlockBitSetTraits::GetSize(this) == fgDomBBcount + 1);
fgDomsComputed = true;
}
void Compiler::fgBuildDomTree()
{
unsigned i;
BasicBlock* block;
#ifdef DEBUG
if (verbose)
{
printf("\nInside fgBuildDomTree\n");
}
#endif // DEBUG
// domTree :: The dominance tree represented using adjacency lists. We use BasicBlockList to represent edges.
// Indexed by basic block number.
unsigned bbArraySize = fgBBNumMax + 1;
BasicBlockList** domTree = new (this, CMK_DominatorMemory) BasicBlockList*[bbArraySize];
fgDomTreePreOrder = new (this, CMK_DominatorMemory) unsigned[bbArraySize];
fgDomTreePostOrder = new (this, CMK_DominatorMemory) unsigned[bbArraySize];
// Initialize all the data structures.
for (i = 0; i < bbArraySize; ++i)
{
domTree[i] = nullptr;
fgDomTreePreOrder[i] = fgDomTreePostOrder[i] = 0;
}
// Build the dominance tree.
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
// If the immediate dominator is not the imaginary root (bbRoot)
// we proceed to append this block to the children of the dominator node.
if (block->bbIDom->bbNum != 0)
{
int bbNum = block->bbIDom->bbNum;
domTree[bbNum] = new (this, CMK_DominatorMemory) BasicBlockList(block, domTree[bbNum]);
}
else
{
// This means this block had bbRoot set as its IDom. We clear it out
// and convert the tree back to a forest.
block->bbIDom = nullptr;
}
}
#ifdef DEBUG
if (verbose)
{
printf("\nAfter computing the Dominance Tree:\n");
fgDispDomTree(domTree);
}
#endif // DEBUG
// Get the bitset that represents the roots of the dominance tree.
// Something to note here is that the dominance tree has been converted from a forest to a tree
// by using the bbRoot trick on fgComputeDoms. The reason we have a forest instead of a real tree
// is because we treat the EH blocks as entry nodes so the real dominance tree is not necessarily connected.
BlockSet_ValRet_T domTreeEntryNodes = fgDomTreeEntryNodes(domTree);
// The preorder and postorder numbers.
// We start from 1 to match the bbNum ordering.
unsigned preNum = 1;
unsigned postNum = 1;
// There will be nodes in the dominance tree that will not be reachable:
// the catch blocks that return since they don't have any predecessor.
// For that matter we'll keep track of how many nodes we can
// reach and assert at the end that we visited all of them.
unsigned domTreeReachable = fgBBcount;
// Once we have the dominance tree computed, we need to traverse it
// to get the preorder and postorder numbers for each node. The purpose of
// this is to achieve O(1) queries for of the form A dominates B.
for (i = 1; i <= fgBBNumMax; ++i)
{
if (BlockSetOps::IsMember(this, domTreeEntryNodes, i))
{
if (domTree[i] == nullptr)
{
// If this is an entry node but there's no children on this
// node, it means it's unreachable so we decrement the reachable
// counter.
--domTreeReachable;
}
else
{
// Otherwise, we do a DFS traversal of the dominator tree.
fgTraverseDomTree(i, domTree, &preNum, &postNum);
}
}
}
noway_assert(preNum == domTreeReachable + 1);
noway_assert(postNum == domTreeReachable + 1);
// Once we have all the reachable nodes numbered, we proceed to
// assign numbers to the non-reachable ones, just assign incrementing
// values. We must reach fgBBcount at the end.
for (i = 1; i <= fgBBNumMax; ++i)
{
if (BlockSetOps::IsMember(this, domTreeEntryNodes, i))
{
if (domTree[i] == nullptr)
{
fgDomTreePreOrder[i] = preNum++;
fgDomTreePostOrder[i] = postNum++;
}
}
}
noway_assert(preNum == fgBBNumMax + 1);
noway_assert(postNum == fgBBNumMax + 1);
noway_assert(fgDomTreePreOrder[0] == 0); // Unused first element
noway_assert(fgDomTreePostOrder[0] == 0); // Unused first element
#ifdef DEBUG
if (0 && verbose)
{
printf("\nAfter traversing the dominance tree:\n");
printf("PreOrder:\n");
for (i = 1; i <= fgBBNumMax; ++i)
{
printf(FMT_BB " : %02u\n", i, fgDomTreePreOrder[i]);
}
printf("PostOrder:\n");
for (i = 1; i <= fgBBNumMax; ++i)
{
printf(FMT_BB " : %02u\n", i, fgDomTreePostOrder[i]);
}
}
#endif // DEBUG
}
BlockSet_ValRet_T Compiler::fgDomTreeEntryNodes(BasicBlockList** domTree)
{
// domTreeEntryNodes :: Set that represents which basic blocks are roots of the dominator forest.
BlockSet domTreeEntryNodes(BlockSetOps::MakeFull(this));
// First of all we need to find all the roots of the dominance forest.
for (unsigned i = 1; i <= fgBBNumMax; ++i)
{
for (BasicBlockList* current = domTree[i]; current != nullptr; current = current->next)
{
BlockSetOps::RemoveElemD(this, domTreeEntryNodes, current->block->bbNum);
}
}
return domTreeEntryNodes;
}
#ifdef DEBUG
void Compiler::fgDispDomTree(BasicBlockList** domTree)
{
for (unsigned i = 1; i <= fgBBNumMax; ++i)
{
if (domTree[i] != nullptr)
{
printf(FMT_BB " : ", i);
for (BasicBlockList* current = domTree[i]; current != nullptr; current = current->next)
{
assert(current->block);
printf(FMT_BB " ", current->block->bbNum);
}
printf("\n");
}
}
printf("\n");
}
#endif // DEBUG
//------------------------------------------------------------------------
// fgTraverseDomTree: Assign pre/post-order numbers to the dominator tree.
//
// Arguments:
// bbNum - The basic block number of the starting block
// domTree - The dominator tree (as child block lists)
// preNum - Pointer to the pre-number counter
// postNum - Pointer to the post-number counter
//
// Notes:
// Runs a non-recursive DFS traversal of the dominator tree using an
// evaluation stack to assign pre-order and post-order numbers.
// These numberings are used to provide constant time lookup for
// ancestor/descendent tests between pairs of nodes in the tree.
void Compiler::fgTraverseDomTree(unsigned bbNum, BasicBlockList** domTree, unsigned* preNum, unsigned* postNum)
{
noway_assert(bbNum <= fgBBNumMax);
// If the block preorder number is not zero it means we already visited
// that node, so we skip it.
if (fgDomTreePreOrder[bbNum] == 0)
{
// If this is the first time we visit this node, both preorder and postnumber
// values must be zero.
noway_assert(fgDomTreePostOrder[bbNum] == 0);
// Allocate a local stack to hold the Dfs traversal actions necessary
// to compute pre/post-ordering of the dominator tree.
ArrayStack<DfsNumEntry> stack(getAllocator(CMK_ArrayStack));
// Push the first entry number on the stack to seed the traversal.
stack.Push(DfsNumEntry(DSS_Pre, bbNum));
// The search is terminated once all the actions have been processed.
while (stack.Height() != 0)
{
DfsNumEntry current = stack.Pop();
unsigned currentNum = current.dfsNum;
if (current.dfsStackState == DSS_Pre)
{
// This pre-visit action corresponds to the first time the
// node is encountered during the spanning traversal.
noway_assert(fgDomTreePreOrder[currentNum] == 0);
noway_assert(fgDomTreePostOrder[currentNum] == 0);
// Assign the preorder number on the first visit.
fgDomTreePreOrder[currentNum] = (*preNum)++;
// Push this nodes post-action on the stack such that all successors
// pre-order visits occur before this nodes post-action. We will assign
// its post-order numbers when we pop off the stack.
stack.Push(DfsNumEntry(DSS_Post, currentNum));
// For each child in the dominator tree process its pre-actions.
for (BasicBlockList* child = domTree[currentNum]; child != nullptr; child = child->next)
{
unsigned childNum = child->block->bbNum;
// This is a tree so never could have been visited
assert(fgDomTreePreOrder[childNum] == 0);
// Push the successor in the dominator tree for pre-actions.
stack.Push(DfsNumEntry(DSS_Pre, childNum));
}
}
else
{
// This post-visit action corresponds to the last time the node
// is encountered and only after all descendents in the spanning
// tree have had pre and post-order numbers assigned.
assert(current.dfsStackState == DSS_Post);
assert(fgDomTreePreOrder[currentNum] != 0);
assert(fgDomTreePostOrder[currentNum] == 0);
// Now assign this nodes post-order number.
fgDomTreePostOrder[currentNum] = (*postNum)++;
}
}
}
}
// This code finds the lowest common ancestor in the
// dominator tree between two basic blocks. The LCA in the Dominance tree
// represents the closest dominator between the two basic blocks. Used to
// adjust the IDom value in fgComputDoms.
BasicBlock* Compiler::fgIntersectDom(BasicBlock* a, BasicBlock* b)
{
BasicBlock* finger1 = a;
BasicBlock* finger2 = b;
while (finger1 != finger2)
{
while (finger1->bbDfsNum > finger2->bbDfsNum)
{
finger1 = finger1->bbIDom;
}
while (finger2->bbDfsNum > finger1->bbDfsNum)
{
finger2 = finger2->bbIDom;
}
}
return finger1;
}
// Return a BlockSet containing all the blocks that dominate 'block'.
BlockSet_ValRet_T Compiler::fgGetDominatorSet(BasicBlock* block)
{
assert(block != nullptr);
BlockSet domSet(BlockSetOps::MakeEmpty(this));
do
{
BlockSetOps::AddElemD(this, domSet, block->bbNum);
if (block == block->bbIDom)
{
break; // We found a cycle in the IDom list, so we're done.
}
block = block->bbIDom;
} while (block != nullptr);
return domSet;
}
/*****************************************************************************
*
* fgComputeCheapPreds: Function called to compute the BasicBlock::bbCheapPreds lists.
*
* No other block data is changed (e.g., bbRefs, bbFlags).
*
* The cheap preds lists are similar to the normal (bbPreds) predecessor lists, but are cheaper to
* compute and store, as follows:
* 1. A flow edge is typed BasicBlockList, which only has a block pointer and 'next' pointer. It doesn't
* have weights or a dup count.
* 2. The preds list for a block is not sorted by block number.
* 3. The predecessors of the block following a BBJ_CALLFINALLY (the corresponding BBJ_ALWAYS,
* for normal, non-retless calls to the finally) are not computed.
* 4. The cheap preds lists will contain duplicates if a single switch table has multiple branches
* to the same block. Thus, we don't spend the time looking for duplicates for every edge we insert.
*/
void Compiler::fgComputeCheapPreds()
{
noway_assert(!fgComputePredsDone); // We can't do this if we've got the full preds.
noway_assert(fgFirstBB != nullptr);
BasicBlock* block;
#ifdef DEBUG
if (verbose)
{
printf("\n*************** In fgComputeCheapPreds()\n");
fgDispBasicBlocks();
printf("\n");
}
#endif // DEBUG
// Clear out the cheap preds lists.
fgRemovePreds();
for (block = fgFirstBB; block != nullptr; block = block->bbNext)
{
switch (block->bbJumpKind)
{
case BBJ_COND:
fgAddCheapPred(block->bbJumpDest, block);
fgAddCheapPred(block->bbNext, block);
break;
case BBJ_CALLFINALLY:
case BBJ_LEAVE: // If fgComputeCheapPreds is called before all blocks are imported, BBJ_LEAVE blocks are
// still in the BB list.
case BBJ_ALWAYS:
case BBJ_EHCATCHRET:
fgAddCheapPred(block->bbJumpDest, block);
break;
case BBJ_NONE:
fgAddCheapPred(block->bbNext, block);
break;
case BBJ_EHFILTERRET:
// Connect end of filter to catch handler.
// In a well-formed program, this cannot be null. Tolerate here, so that we can call
// fgComputeCheapPreds before fgImport on an ill-formed program; the problem will be detected in
// fgImport.
if (block->bbJumpDest != nullptr)
{
fgAddCheapPred(block->bbJumpDest, block);
}
break;
case BBJ_SWITCH:
unsigned jumpCnt;
jumpCnt = block->bbJumpSwt->bbsCount;
BasicBlock** jumpTab;
jumpTab = block->bbJumpSwt->bbsDstTab;
do
{
fgAddCheapPred(*jumpTab, block);
} while (++jumpTab, --jumpCnt);
break;
case BBJ_EHFINALLYRET: // It's expensive to compute the preds for this case, so we don't for the cheap
// preds.
case BBJ_THROW:
case BBJ_RETURN:
break;
default:
noway_assert(!"Unexpected bbJumpKind");
break;
}
}
fgCheapPredsValid = true;
#ifdef DEBUG
if (verbose)
{
printf("\n*************** After fgComputeCheapPreds()\n");
fgDispBasicBlocks();
printf("\n");
}
#endif
}
/*****************************************************************************
* Add 'blockPred' to the cheap predecessor list of 'block'.
*/
void Compiler::fgAddCheapPred(BasicBlock* block, BasicBlock* blockPred)
{
assert(!fgComputePredsDone);
assert(block != nullptr);
assert(blockPred != nullptr);
block->bbCheapPreds = new (this, CMK_FlowList) BasicBlockList(blockPred, block->bbCheapPreds);
#if MEASURE_BLOCK_SIZE
genFlowNodeCnt += 1;
genFlowNodeSize += sizeof(BasicBlockList);
#endif // MEASURE_BLOCK_SIZE
}
/*****************************************************************************
* Remove 'blockPred' from the cheap predecessor list of 'block'.
* If there are duplicate edges, only remove one of them.
*/
void Compiler::fgRemoveCheapPred(BasicBlock* block, BasicBlock* blockPred)
{
assert(!fgComputePredsDone);
assert(fgCheapPredsValid);
flowList* oldEdge = nullptr;
assert(block != nullptr);
assert(blockPred != nullptr);
assert(block->bbCheapPreds != nullptr);
/* Is this the first block in the pred list? */
if (blockPred == block->bbCheapPreds->block)
{
block->bbCheapPreds = block->bbCheapPreds->next;
}
else
{
BasicBlockList* pred;
for (pred = block->bbCheapPreds; pred->next != nullptr; pred = pred->next)
{
if (blockPred == pred->next->block)
{
break;
}
}
noway_assert(pred->next != nullptr); // we better have found it!
pred->next = pred->next->next; // splice it out
}
}
void Compiler::fgRemovePreds()
{
C_ASSERT(offsetof(BasicBlock, bbPreds) ==
offsetof(BasicBlock, bbCheapPreds)); // bbPreds and bbCheapPreds are at the same place in a union,
C_ASSERT(sizeof(((BasicBlock*)nullptr)->bbPreds) ==
sizeof(((BasicBlock*)nullptr)->bbCheapPreds)); // and are the same size. So, this function removes both.
for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->bbNext)
{
block->bbPreds = nullptr;
}
fgComputePredsDone = false;
fgCheapPredsValid = false;
}
/*****************************************************************************
*
* Function called to compute the bbPreds lists.
*/
void Compiler::fgComputePreds()
{
noway_assert(fgFirstBB);
BasicBlock* block;
#ifdef DEBUG
if (verbose)
{
printf("\n*************** In fgComputePreds()\n");
fgDispBasicBlocks();
printf("\n");
}
#endif // DEBUG
// reset the refs count for each basic block
for (block = fgFirstBB; block; block = block->bbNext)
{
block->bbRefs = 0;
}
/* the first block is always reachable! */
fgFirstBB->bbRefs = 1;
/* Treat the initial block as a jump target */
fgFirstBB->bbFlags |= BBF_JMP_TARGET | BBF_HAS_LABEL;
fgRemovePreds();
for (block = fgFirstBB; block; block = block->bbNext)
{
switch (block->bbJumpKind)
{
case BBJ_CALLFINALLY:
if (!(block->bbFlags & BBF_RETLESS_CALL))
{
assert(block->isBBCallAlwaysPair());
/* Mark the next block as being a jump target,
since the call target will return there */
PREFIX_ASSUME(block->bbNext != nullptr);
block->bbNext->bbFlags |= (BBF_JMP_TARGET | BBF_HAS_LABEL);
}
__fallthrough;
case BBJ_LEAVE: // Sometimes fgComputePreds is called before all blocks are imported, so BBJ_LEAVE
// blocks are still in the BB list.
case BBJ_COND:
case BBJ_ALWAYS:
case BBJ_EHCATCHRET:
/* Mark the jump dest block as being a jump target */
block->bbJumpDest->bbFlags |= BBF_JMP_TARGET | BBF_HAS_LABEL;
fgAddRefPred(block->bbJumpDest, block, nullptr, true);
/* Is the next block reachable? */
if (block->bbJumpKind != BBJ_COND)
{
break;
}
noway_assert(block->bbNext);
/* Fall through, the next block is also reachable */
__fallthrough;
case BBJ_NONE:
fgAddRefPred(block->bbNext, block, nullptr, true);
break;
case BBJ_EHFILTERRET:
// Connect end of filter to catch handler.
// In a well-formed program, this cannot be null. Tolerate here, so that we can call
// fgComputePreds before fgImport on an ill-formed program; the problem will be detected in fgImport.
if (block->bbJumpDest != nullptr)
{
fgAddRefPred(block->bbJumpDest, block, nullptr, true);
}
break;
case BBJ_EHFINALLYRET:
{
/* Connect the end of the finally to the successor of
the call to this finally */
if (!block->hasHndIndex())
{
NO_WAY("endfinally outside a finally/fault block.");
}
unsigned hndIndex = block->getHndIndex();
EHblkDsc* ehDsc = ehGetDsc(hndIndex);
if (!ehDsc->HasFinallyOrFaultHandler())
{
NO_WAY("endfinally outside a finally/fault block.");
}
if (ehDsc->HasFinallyHandler())
{
// Find all BBJ_CALLFINALLY that branched to this finally handler.
BasicBlock* begBlk;
BasicBlock* endBlk;
ehGetCallFinallyBlockRange(hndIndex, &begBlk, &endBlk);
BasicBlock* finBeg = ehDsc->ebdHndBeg;
for (BasicBlock* bcall = begBlk; bcall != endBlk; bcall = bcall->bbNext)
{
if (bcall->bbJumpKind != BBJ_CALLFINALLY || bcall->bbJumpDest != finBeg)
{
continue;
}
noway_assert(bcall->isBBCallAlwaysPair());
fgAddRefPred(bcall->bbNext, block, nullptr, true);
}
}
}
break;
case BBJ_THROW:
case BBJ_RETURN:
break;
case BBJ_SWITCH:
unsigned jumpCnt;
jumpCnt = block->bbJumpSwt->bbsCount;
BasicBlock** jumpTab;
jumpTab = block->bbJumpSwt->bbsDstTab;
do
{
/* Mark the target block as being a jump target */
(*jumpTab)->bbFlags |= BBF_JMP_TARGET | BBF_HAS_LABEL;
fgAddRefPred(*jumpTab, block, nullptr, true);
} while (++jumpTab, --jumpCnt);
break;
default:
noway_assert(!"Unexpected bbJumpKind");
break;
}
}
for (unsigned EHnum = 0; EHnum < compHndBBtabCount; EHnum++)
{
EHblkDsc* ehDsc = ehGetDsc(EHnum);
if (ehDsc->HasFilter())
{
ehDsc->ebdFilter->bbFlags |= BBF_JMP_TARGET | BBF_HAS_LABEL;
// The first block of a filter has an artifical extra refcount.
ehDsc->ebdFilter->bbRefs++;
}
ehDsc->ebdHndBeg->bbFlags |= BBF_JMP_TARGET | BBF_HAS_LABEL;
// The first block of a handler has an artificial extra refcount.
ehDsc->ebdHndBeg->bbRefs++;
}
fgModified = false;
fgComputePredsDone = true;
#ifdef DEBUG
if (verbose)
{
printf("\n*************** After fgComputePreds()\n");
fgDispBasicBlocks();
printf("\n");
}
#endif
}
unsigned Compiler::fgNSuccsOfFinallyRet(BasicBlock* block)
{
BasicBlock* bb;
unsigned res;
fgSuccOfFinallyRetWork(block, ~0, &bb, &res);
return res;
}
BasicBlock* Compiler::fgSuccOfFinallyRet(BasicBlock* block, unsigned i)
{
BasicBlock* bb;
unsigned res;
fgSuccOfFinallyRetWork(block, i, &bb, &res);
return bb;
}
void Compiler::fgSuccOfFinallyRetWork(BasicBlock* block, unsigned i, BasicBlock** bres, unsigned* nres)
{
assert(block->hasHndIndex()); // Otherwise, endfinally outside a finally/fault block?
unsigned hndIndex = block->getHndIndex();
EHblkDsc* ehDsc = ehGetDsc(hndIndex);
assert(ehDsc->HasFinallyOrFaultHandler()); // Otherwise, endfinally outside a finally/fault block.
*bres = nullptr;
unsigned succNum = 0;
if (ehDsc->HasFinallyHandler())
{
BasicBlock* begBlk;
BasicBlock* endBlk;
ehGetCallFinallyBlockRange(hndIndex, &begBlk, &endBlk);
BasicBlock* finBeg = ehDsc->ebdHndBeg;
for (BasicBlock* bcall = begBlk; bcall != endBlk; bcall = bcall->bbNext)
{
if (bcall->bbJumpKind != BBJ_CALLFINALLY || bcall->bbJumpDest != finBeg)
{
continue;
}
assert(bcall->isBBCallAlwaysPair());
if (succNum == i)
{
*bres = bcall->bbNext;
return;
}
succNum++;
}
}
assert(i == ~0u || ehDsc->HasFaultHandler()); // Should reach here only for fault blocks.
if (i == ~0u)
{
*nres = succNum;
}
}
Compiler::SwitchUniqueSuccSet Compiler::GetDescriptorForSwitch(BasicBlock* switchBlk)
{
assert(switchBlk->bbJumpKind == BBJ_SWITCH);
BlockToSwitchDescMap* switchMap = GetSwitchDescMap();
SwitchUniqueSuccSet res;
if (switchMap->Lookup(switchBlk, &res))
{
return res;
}
else
{
// We must compute the descriptor. Find which are dups, by creating a bit set with the unique successors.
// We create a temporary bitset of blocks to compute the unique set of successor blocks,
// since adding a block's number twice leaves just one "copy" in the bitset. Note that
// we specifically don't use the BlockSet type, because doing so would require making a
// call to EnsureBasicBlockEpoch() to make sure the epoch is up-to-date. However, that
// can create a new epoch, thus invalidating all existing BlockSet objects, such as
// reachability information stored in the blocks. To avoid that, we just use a local BitVec.
BitVecTraits blockVecTraits(fgBBNumMax + 1, this);
BitVec uniqueSuccBlocks(BitVecOps::MakeEmpty(&blockVecTraits));
BasicBlock** jumpTable = switchBlk->bbJumpSwt->bbsDstTab;
unsigned jumpCount = switchBlk->bbJumpSwt->bbsCount;
for (unsigned i = 0; i < jumpCount; i++)
{
BasicBlock* targ = jumpTable[i];
BitVecOps::AddElemD(&blockVecTraits, uniqueSuccBlocks, targ->bbNum);
}
// Now we have a set of unique successors.
unsigned numNonDups = BitVecOps::Count(&blockVecTraits, uniqueSuccBlocks);
BasicBlock** nonDups = new (getAllocator()) BasicBlock*[numNonDups];
unsigned nonDupInd = 0;
// At this point, all unique targets are in "uniqueSuccBlocks". As we encounter each,
// add to nonDups, remove from "uniqueSuccBlocks".
for (unsigned i = 0; i < jumpCount; i++)
{
BasicBlock* targ = jumpTable[i];
if (BitVecOps::IsMember(&blockVecTraits, uniqueSuccBlocks, targ->bbNum))
{
nonDups[nonDupInd] = targ;
nonDupInd++;
BitVecOps::RemoveElemD(&blockVecTraits, uniqueSuccBlocks, targ->bbNum);
}
}
assert(nonDupInd == numNonDups);
assert(BitVecOps::Count(&blockVecTraits, uniqueSuccBlocks) == 0);
res.numDistinctSuccs = numNonDups;
res.nonDuplicates = nonDups;
switchMap->Set(switchBlk, res);
return res;
}
}
void Compiler::SwitchUniqueSuccSet::UpdateTarget(CompAllocator alloc,
BasicBlock* switchBlk,
BasicBlock* from,
BasicBlock* to)
{
assert(switchBlk->bbJumpKind == BBJ_SWITCH); // Precondition.
unsigned jmpTabCnt = switchBlk->bbJumpSwt->bbsCount;
BasicBlock** jmpTab = switchBlk->bbJumpSwt->bbsDstTab;
// Is "from" still in the switch table (because it had more than one entry before?)
bool fromStillPresent = false;
for (unsigned i = 0; i < jmpTabCnt; i++)
{
if (jmpTab[i] == from)
{
fromStillPresent = true;
break;
}
}
// Is "to" already in "this"?
bool toAlreadyPresent = false;
for (unsigned i = 0; i < numDistinctSuccs; i++)
{
if (nonDuplicates[i] == to)
{
toAlreadyPresent = true;
break;
}
}
// Four cases:
// If "from" is still present, and "to" is already present, do nothing
// If "from" is still present, and "to" is not, must reallocate to add an entry.
// If "from" is not still present, and "to" is not present, write "to" where "from" was.
// If "from" is not still present, but "to" is present, remove "from".
if (fromStillPresent && toAlreadyPresent)
{
return;
}
else if (fromStillPresent && !toAlreadyPresent)
{
// reallocate to add an entry
BasicBlock** newNonDups = new (alloc) BasicBlock*[numDistinctSuccs + 1];
memcpy(newNonDups, nonDuplicates, numDistinctSuccs * sizeof(BasicBlock*));
newNonDups[numDistinctSuccs] = to;
numDistinctSuccs++;
nonDuplicates = newNonDups;
}
else if (!fromStillPresent && !toAlreadyPresent)
{
#ifdef DEBUG
// write "to" where "from" was
bool foundFrom = false;
#endif // DEBUG
for (unsigned i = 0; i < numDistinctSuccs; i++)
{
if (nonDuplicates[i] == from)
{
nonDuplicates[i] = to;
#ifdef DEBUG
foundFrom = true;
#endif // DEBUG
break;
}
}
assert(foundFrom);
}
else
{
assert(!fromStillPresent && toAlreadyPresent);
#ifdef DEBUG
// remove "from".
bool foundFrom = false;
#endif // DEBUG
for (unsigned i = 0; i < numDistinctSuccs; i++)
{
if (nonDuplicates[i] == from)
{
nonDuplicates[i] = nonDuplicates[numDistinctSuccs - 1];
numDistinctSuccs--;
#ifdef DEBUG
foundFrom = true;
#endif // DEBUG
break;
}
}
assert(foundFrom);
}
}
/*****************************************************************************
*
* Simple utility function to remove an entry for a block in the switch desc
* map. So it can be called from other phases.
*
*/
void Compiler::fgInvalidateSwitchDescMapEntry(BasicBlock* block)
{
// Check if map has no entries yet.
if (m_switchDescMap != nullptr)
{
m_switchDescMap->Remove(block);
}
}
void Compiler::UpdateSwitchTableTarget(BasicBlock* switchBlk, BasicBlock* from, BasicBlock* to)
{
if (m_switchDescMap == nullptr)
{
return; // No mappings, nothing to do.
}
// Otherwise...
BlockToSwitchDescMap* switchMap = GetSwitchDescMap();
SwitchUniqueSuccSet* res = switchMap->LookupPointer(switchBlk);
if (res != nullptr)
{
// If no result, nothing to do. Otherwise, update it.
res->UpdateTarget(getAllocator(), switchBlk, from, to);
}
}
/*****************************************************************************
* For a block that is in a handler region, find the first block of the most-nested
* handler containing the block.
*/
BasicBlock* Compiler::fgFirstBlockOfHandler(BasicBlock* block)
{
assert(block->hasHndIndex());
return ehGetDsc(block->getHndIndex())->ebdHndBeg;
}
/*****************************************************************************
*
* Function called to find back edges and return blocks and mark them as needing GC Polls. This marks all
* blocks.
*/
void Compiler::fgMarkGCPollBlocks()
{
if (GCPOLL_NONE == opts.compGCPollType)
{
return;
}
#ifdef DEBUG
/* Check that the flowgraph data (bbNum, bbRefs, bbPreds) is up-to-date */
fgDebugCheckBBlist();
#endif
BasicBlock* block;
// Return blocks always need GC polls. In addition, all back edges (including those from switch
// statements) need GC polls. The poll is on the block with the outgoing back edge (or ret), rather than
// on the destination or on the edge itself.
for (block = fgFirstBB; block; block = block->bbNext)
{
bool blockNeedsPoll = false;
switch (block->bbJumpKind)
{
case BBJ_COND:
case BBJ_ALWAYS:
blockNeedsPoll = (block->bbJumpDest->bbNum <= block->bbNum);
break;
case BBJ_RETURN:
blockNeedsPoll = true;
break;
case BBJ_SWITCH:
unsigned jumpCnt;
jumpCnt = block->bbJumpSwt->bbsCount;
BasicBlock** jumpTab;
jumpTab = block->bbJumpSwt->bbsDstTab;
do
{
if ((*jumpTab)->bbNum <= block->bbNum)
{
blockNeedsPoll = true;
break;
}
} while (++jumpTab, --jumpCnt);
break;
default:
break;
}
if (blockNeedsPoll)
{
block->bbFlags |= BBF_NEEDS_GCPOLL;
}
}
}
void Compiler::fgInitBlockVarSets()
{
for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
{
block->InitVarSets(this);
}
fgBBVarSetsInited = true;
}
/*****************************************************************************
*
* The following does the final pass on BBF_NEEDS_GCPOLL and then actually creates the GC Polls.
*/
void Compiler::fgCreateGCPolls()
{
if (GCPOLL_NONE == opts.compGCPollType)
{
return;
}
bool createdPollBlocks = false;
#ifdef DEBUG
if (verbose)
{
printf("*************** In fgCreateGCPolls() for %s\n", info.compFullName);
}
#endif // DEBUG
if (!(opts.MinOpts() || opts.compDbgCode))
{
// Remove polls from well formed loops with a constant upper bound.
for (unsigned lnum = 0; lnum < optLoopCount; ++lnum)
{
// Look for constant counted loops that run for a short duration. This logic is very similar to
// what's in code:Compiler::optUnrollLoops, since they have similar constraints. However, this
// logic is much more permissive since we're not doing a complex transformation.
/* TODO-Cleanup:
* I feel bad cloning so much logic from optUnrollLoops
*/
// Filter out loops not meeting the obvious preconditions.
//
if (optLoopTable[lnum].lpFlags & LPFLG_REMOVED)
{
continue;
}
if (!(optLoopTable[lnum].lpFlags & LPFLG_CONST))
{
continue;
}
BasicBlock* head = optLoopTable[lnum].lpHead;
BasicBlock* bottom = optLoopTable[lnum].lpBottom;
// Loops dominated by GC_SAFE_POINT won't have this set.
if (!(bottom->bbFlags & BBF_NEEDS_GCPOLL))
{
continue;
}
/* Get the loop data:
- initial constant
- limit constant
- iterator
- iterator increment
- increment operation type (i.e. ASG_ADD, ASG_SUB, etc...)
- loop test type (i.e. GT_GE, GT_LT, etc...)
*/
int lbeg = optLoopTable[lnum].lpConstInit;
int llim = optLoopTable[lnum].lpConstLimit();
genTreeOps testOper = optLoopTable[lnum].lpTestOper();
int lvar = optLoopTable[lnum].lpIterVar();
int iterInc = optLoopTable[lnum].lpIterConst();
genTreeOps iterOper = optLoopTable[lnum].lpIterOper();
var_types iterOperType = optLoopTable[lnum].lpIterOperType();
bool unsTest = (optLoopTable[lnum].lpTestTree->gtFlags & GTF_UNSIGNED) != 0;
if (lvaTable[lvar].lvAddrExposed)
{ // Can't reason about the value of the iteration variable.
continue;
}
unsigned totalIter;
/* Find the number of iterations - the function returns false if not a constant number */
if (!optComputeLoopRep(lbeg, llim, iterInc, iterOper, iterOperType, testOper, unsTest,
// The value here doesn't matter for this variation of the optimization
true, &totalIter))
{
#ifdef DEBUG
if (verbose)
{
printf("Could not compute loop iterations for loop from " FMT_BB " to " FMT_BB, head->bbNum,
bottom->bbNum);
}
#endif // DEBUG
(void)head; // suppress gcc error.
continue;
}
/* Forget it if there are too many repetitions or not a constant loop */
static const unsigned ITER_LIMIT = 256;
if (totalIter > ITER_LIMIT)
{
continue;
}
// It is safe to elminate the poll from this loop.
bottom->bbFlags &= ~BBF_NEEDS_GCPOLL;
#ifdef DEBUG
if (verbose)
{
printf("Removing poll in block " FMT_BB " because it forms a bounded counted loop\n", bottom->bbNum);
}
#endif // DEBUG
}
}
// Final chance to optimize the polls. Move all polls in loops from the bottom of the loop up to the
// loop head. Also eliminate all epilog polls in non-leaf methods. This only works if we have dominator
// information.
if (fgDomsComputed)
{
for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
{
if (!(block->bbFlags & BBF_NEEDS_GCPOLL))
{
continue;
}
if (block->bbJumpKind == BBJ_COND || block->bbJumpKind == BBJ_ALWAYS)
{
// make sure that this is loop-like
if (!fgReachable(block->bbJumpDest, block))
{
block->bbFlags &= ~BBF_NEEDS_GCPOLL;
#ifdef DEBUG
if (verbose)
{
printf("Removing poll in block " FMT_BB " because it is not loop\n", block->bbNum);
}
#endif // DEBUG
continue;
}
}
else if (!(block->bbJumpKind == BBJ_RETURN || block->bbJumpKind == BBJ_SWITCH))
{
noway_assert(!"GC Poll on a block that has no control transfer.");
#ifdef DEBUG
if (verbose)
{
printf("Removing poll in block " FMT_BB " because it is not a jump\n", block->bbNum);
}
#endif // DEBUG
block->bbFlags &= ~BBF_NEEDS_GCPOLL;
continue;
}
// Because of block compaction, it's possible to end up with a block that is both poll and safe.
// Clean those up now.
if (block->bbFlags & BBF_GC_SAFE_POINT)
{
#ifdef DEBUG
if (verbose)
{
printf("Removing poll in return block " FMT_BB " because it is GC Safe\n", block->bbNum);
}
#endif // DEBUG
block->bbFlags &= ~BBF_NEEDS_GCPOLL;
continue;
}
if (block->bbJumpKind == BBJ_RETURN)
{
if (!optReachWithoutCall(fgFirstBB, block))
{
// check to see if there is a call along the path between the first block and the return
// block.
block->bbFlags &= ~BBF_NEEDS_GCPOLL;
#ifdef DEBUG
if (verbose)
{
printf("Removing poll in return block " FMT_BB " because it dominated by a call\n",
block->bbNum);
}
#endif // DEBUG
continue;
}
}
}
}
noway_assert(!fgGCPollsCreated);
BasicBlock* block;
fgGCPollsCreated = true;
// Walk through the blocks and hunt for a block that has BBF_NEEDS_GCPOLL
for (block = fgFirstBB; block; block = block->bbNext)
{
// Because of block compaction, it's possible to end up with a block that is both poll and safe.
// And if !fgDomsComputed, we won't have cleared them, so skip them now
if (!(block->bbFlags & BBF_NEEDS_GCPOLL) || (block->bbFlags & BBF_GC_SAFE_POINT))
{
continue;
}
// This block needs a poll. We either just insert a callout or we split the block and inline part of
// the test. This depends on the value of opts.compGCPollType.
// If we're doing GCPOLL_CALL, just insert a GT_CALL node before the last node in the block.
CLANG_FORMAT_COMMENT_ANCHOR;
#ifdef DEBUG
switch (block->bbJumpKind)
{
case BBJ_RETURN:
case BBJ_ALWAYS:
case BBJ_COND:
case BBJ_SWITCH:
break;
default:
noway_assert(!"Unknown block type for BBF_NEEDS_GCPOLL");
}
#endif // DEBUG
noway_assert(opts.compGCPollType);
GCPollType pollType = opts.compGCPollType;
// pollType is set to either CALL or INLINE at this point. Below is the list of places where we
// can't or don't want to emit an inline check. Check all of those. If after all of that we still
// have INLINE, then emit an inline check.
if (opts.MinOpts() || opts.compDbgCode)
{
#ifdef DEBUG
if (verbose)
{
printf("Selecting CALL poll in block " FMT_BB " because of debug/minopts\n", block->bbNum);
}
#endif // DEBUG
// Don't split blocks and create inlined polls unless we're optimizing.
pollType = GCPOLL_CALL;
}
else if (genReturnBB == block)
{
#ifdef DEBUG
if (verbose)
{
printf("Selecting CALL poll in block " FMT_BB " because it is the single return block\n", block->bbNum);
}
#endif // DEBUG
// we don't want to split the single return block
pollType = GCPOLL_CALL;
}
else if (BBJ_SWITCH == block->bbJumpKind)
{
#ifdef DEBUG
if (verbose)
{
printf("Selecting CALL poll in block " FMT_BB " because it is a loop formed by a SWITCH\n",
block->bbNum);
}
#endif // DEBUG
// I don't want to deal with all the outgoing edges of a switch block.
pollType = GCPOLL_CALL;
}
// TODO-Cleanup: potentially don't split if we're in an EH region.
createdPollBlocks |= fgCreateGCPoll(pollType, block);
}
// If we split a block to create a GC Poll, then rerun fgReorderBlocks to push the rarely run blocks out
// past the epilog. We should never split blocks unless we're optimizing.
if (createdPollBlocks)
{
noway_assert(!opts.MinOpts() && !opts.compDbgCode);
fgReorderBlocks();
}
}
/*****************************************************************************
*
* Actually create a GCPoll in the given block. Returns true if it created
* a basic block.
*/
bool Compiler::fgCreateGCPoll(GCPollType pollType, BasicBlock* block)
{
assert(!(block->bbFlags & BBF_GC_SAFE_POINT));
bool createdPollBlocks;
void* addrTrap;
void* pAddrOfCaptureThreadGlobal;
addrTrap = info.compCompHnd->getAddrOfCaptureThreadGlobal(&pAddrOfCaptureThreadGlobal);
#ifdef ENABLE_FAST_GCPOLL_HELPER
// I never want to split blocks if we've got two indirections here.
// This is a size trade-off assuming the VM has ENABLE_FAST_GCPOLL_HELPER.
// So don't do it when that is off
if (pAddrOfCaptureThreadGlobal != NULL)
{
pollType = GCPOLL_CALL;
}
#endif // ENABLE_FAST_GCPOLL_HELPER
if (GCPOLL_CALL == pollType)
{
createdPollBlocks = false;
GenTreeCall* call = gtNewHelperCallNode(CORINFO_HELP_POLL_GC, TYP_VOID);
// for BBJ_ALWAYS I don't need to insert it before the condition. Just append it.
if (block->bbJumpKind == BBJ_ALWAYS)
{
fgInsertStmtAtEnd(block, call);
}
else
{
GenTreeStmt* newStmt = fgInsertStmtNearEnd(block, call);
// For DDB156656, we need to associate the GC Poll with the IL offset (and therefore sequence
// point) of the tree before which we inserted the poll. One example of when this is a
// problem:
// if (...) { //1
// ...
// } //2
// else { //3
// ...
// }
// (gcpoll) //4
// return. //5
//
// If we take the if statement at 1, we encounter a jump at 2. This jumps over the else
// and lands at 4. 4 is where we inserted the gcpoll. However, that is associated with
// the sequence point a 3. Therefore, the debugger displays the wrong source line at the
// gc poll location.
//
// More formally, if control flow targets an instruction, that instruction must be the
// start of a new sequence point.
if (newStmt->gtNext)
{
// Is it possible for gtNext to be NULL?
noway_assert(newStmt->gtNext->gtOper == GT_STMT);
newStmt->gtStmtILoffsx = newStmt->gtNextStmt->gtStmtILoffsx;
}
}
block->bbFlags |= BBF_GC_SAFE_POINT;
#ifdef DEBUG
if (verbose)
{
printf("*** creating GC Poll in block " FMT_BB "\n", block->bbNum);
gtDispTreeList(block->bbTreeList);
}
#endif // DEBUG
}
else
{
created