in src/coreclr/jit/fgopt.cpp [3207:4365]
bool Compiler::fgReorderBlocks(bool useProfile)
{
noway_assert(opts.compDbgCode == false);
assert(UsesFunclets() == fgFuncletsCreated);
// We can't relocate anything if we only have one block
if (fgFirstBB->IsLast())
{
return false;
}
bool newRarelyRun = false;
bool movedBlocks = false;
bool optimizedSwitches = false;
bool optimizedBranches = false;
// First let us expand the set of run rarely blocks
newRarelyRun |= fgExpandRarelyRunBlocks();
#if defined(FEATURE_EH_WINDOWS_X86)
if (!UsesFunclets())
{
movedBlocks |= fgRelocateEHRegions();
}
#endif // FEATURE_EH_WINDOWS_X86
//
// If we are using profile weights we can change some
// switch jumps into conditional test and jump
//
if (fgIsUsingProfileWeights())
{
optimizedSwitches = fgOptimizeSwitchJumps();
if (optimizedSwitches)
{
fgUpdateFlowGraph();
}
}
if (useProfile)
{
if (JitConfig.JitDoReversePostOrderLayout())
{
fgDoReversePostOrderLayout();
fgMoveColdBlocks();
// Renumber blocks to facilitate LSRA's order of block visitation
// TODO: Consider removing this, and using traversal order in lSRA
//
fgRenumberBlocks();
return true;
}
// We will be reordering blocks, so ensure the false target of a BBJ_COND block is its next block
for (BasicBlock* block = fgFirstBB; block != nullptr; block = block->Next())
{
if (block->KindIs(BBJ_COND) && !block->NextIs(block->GetFalseTarget()))
{
if (block->CanRemoveJumpToTarget(block->GetTrueTarget(), this))
{
// Reverse the jump condition
GenTree* test = block->lastNode();
assert(test->OperIsConditionalJump());
test->AsOp()->gtOp1 = gtReverseCond(test->AsOp()->gtOp1);
FlowEdge* const newFalseEdge = block->GetTrueEdge();
FlowEdge* const newTrueEdge = block->GetFalseEdge();
block->SetTrueEdge(newTrueEdge);
block->SetFalseEdge(newFalseEdge);
assert(block->CanRemoveJumpToTarget(block->GetFalseTarget(), this));
}
else
{
BasicBlock* jmpBlk = fgConnectFallThrough(block, block->GetFalseTarget());
assert(jmpBlk != nullptr);
assert(block->NextIs(jmpBlk));
// Skip next block
block = jmpBlk;
}
}
}
}
#ifdef DEBUG
if (verbose)
{
printf("*************** In fgReorderBlocks()\n");
printf("\nInitial BasicBlocks");
fgDispBasicBlocks(verboseTrees);
printf("\n");
}
#endif // DEBUG
BasicBlock* bNext;
BasicBlock* bPrev;
BasicBlock* block;
unsigned XTnum;
EHblkDsc* HBtab;
// Iterate over every block, remembering our previous block in bPrev
for (bPrev = fgFirstBB, block = bPrev->Next(); block != nullptr; bPrev = block, block = block->Next())
{
//
// Consider relocating the rarely run blocks such that they are at the end of the method.
// We also consider reversing conditional branches so that they become a not taken forwards branch.
//
// Don't consider BBJ_CALLFINALLYRET; it should be processed together with BBJ_CALLFINALLY.
if (block->KindIs(BBJ_CALLFINALLYRET))
{
continue;
}
// If block is marked with a BBF_KEEP_BBJ_ALWAYS flag then we don't move the block
if (block->HasFlag(BBF_KEEP_BBJ_ALWAYS))
{
continue;
}
// Finally and handlers blocks are to be kept contiguous.
// TODO-CQ: Allow reordering within the handler region
if (block->hasHndIndex())
{
continue;
}
bool reorderBlock = useProfile;
const bool isRare = block->isRunRarely();
BasicBlock* bDest = nullptr;
bool forwardBranch = false;
bool backwardBranch = false;
// Setup bDest
if (bPrev->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET))
{
bDest = bPrev->GetTarget();
forwardBranch = fgIsForwardBranch(bPrev, bDest);
backwardBranch = !forwardBranch;
}
else if (bPrev->KindIs(BBJ_COND))
{
// fgReorderBlocks is called in more than one optimization phase,
// but only does any reordering in optOptimizeLayout.
// At that point, we expect implicit fallthrough to be restored for BBJ_COND blocks.
assert(bPrev->FalseTargetIs(block) || !reorderBlock);
bDest = bPrev->GetTrueTarget();
forwardBranch = fgIsForwardBranch(bPrev, bDest);
backwardBranch = !forwardBranch;
}
// We will look for bPrev as a non rarely run block followed by block as a rarely run block
//
if (bPrev->isRunRarely())
{
reorderBlock = false;
}
// If the weights of the bPrev, block and bDest were all obtained from a profile run
// then we can use them to decide if it is useful to reverse this conditional branch
weight_t profHotWeight = -1;
if (useProfile && bPrev->hasProfileWeight() && block->hasProfileWeight() &&
((bDest == nullptr) || bDest->hasProfileWeight()))
{
//
// All blocks have profile information
//
if (forwardBranch)
{
if (bPrev->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET))
{
if (bPrev->JumpsToNext())
{
bDest = nullptr;
goto CHECK_FOR_RARE;
}
// We can pull up the blocks that the unconditional jump branches to
// if the weight of bDest is greater or equal to the weight of block
// also the weight of bDest can't be zero.
// Don't reorder if bPrev's jump destination is the next block.
//
else if ((bDest->bbWeight < block->bbWeight) || (bDest->bbWeight == BB_ZERO_WEIGHT))
{
reorderBlock = false;
}
else
{
//
// If this remains true then we will try to pull up bDest to succeed bPrev
//
bool moveDestUp = true;
//
// The edge bPrev -> bDest must have a higher weight
// than every other edge into bDest
//
weight_t const weightToBeat = bPrev->GetTargetEdge()->getLikelyWeight();
// Examine all of the other edges into bDest
for (FlowEdge* const edge : bDest->PredEdges())
{
if (edge->getLikelyWeight() > weightToBeat)
{
moveDestUp = false;
break;
}
}
// Are we still good to move bDest up to bPrev?
if (moveDestUp)
{
//
// We will consider all blocks that have less weight than profHotWeight to be
// uncommonly run blocks as compared with the hot path of bPrev taken-jump to bDest
//
profHotWeight = bDest->bbWeight - 1;
}
else
{
if (block->isRunRarely())
{
// We will move any rarely run blocks blocks
profHotWeight = 0;
}
else
{
// We will move all blocks that have a weight less or equal to our fall through block
profHotWeight = block->bbWeight + 1;
}
// But we won't try to connect with bDest
bDest = nullptr;
}
}
}
else // (bPrev->KindIs(BBJ_COND))
{
noway_assert(bPrev->KindIs(BBJ_COND));
//
// We will reverse branch if the true edge's likelihood is more than 51%.
//
// We will set up profHotWeight to be maximum bbWeight that a block
// could have for us not to want to reverse the conditional branch.
//
// We will consider all blocks that have less weight than profHotWeight to be
// uncommonly run blocks compared to the weight of bPrev's true edge.
//
// We will check if bPrev's true edge weight
// is more than twice bPrev's false edge weight.
//
// bPrev --> [BB04, weight 100]
// | \.
// falseEdge ---------------> O \.
// [likelihood=0.33] V \.
// block --> [BB05, weight 33] \.
// \.
// trueEdge ------------------------------> O
// [likelihood=0.67] |
// V
// bDest ---------------> [BB08, weight 67]
//
assert(bPrev->FalseTargetIs(block));
FlowEdge* trueEdge = bPrev->GetTrueEdge();
FlowEdge* falseEdge = bPrev->GetFalseEdge();
noway_assert(trueEdge != nullptr);
noway_assert(falseEdge != nullptr);
// If we take the true branch more than half the time, we will reverse the branch.
if (trueEdge->getLikelihood() < 0.51)
{
reorderBlock = false;
}
else
{
// set profHotWeight
profHotWeight = falseEdge->getLikelyWeight() - 1;
}
}
}
else // not a forwardBranch
{
if (bPrev->bbFallsThrough())
{
goto CHECK_FOR_RARE;
}
// Here we should pull up the highest weight block remaining
// and place it here since bPrev does not fall through.
weight_t highestWeight = 0;
BasicBlock* candidateBlock = nullptr;
BasicBlock* lastNonFallThroughBlock = bPrev;
BasicBlock* bTmp = bPrev->Next();
while (bTmp != nullptr)
{
// Don't try to split a call finally pair
//
if (bTmp->isBBCallFinallyPair())
{
// Move bTmp forward
bTmp = bTmp->Next();
}
//
// Check for loop exit condition
//
if (bTmp == nullptr)
{
break;
}
//
// if its weight is the highest one we've seen and
// the EH regions allow for us to place bTmp after bPrev
//
if ((bTmp->bbWeight > highestWeight) && fgEhAllowsMoveBlock(bPrev, bTmp))
{
// When we have a current candidateBlock that is a conditional (or unconditional) jump
// to bTmp (which is a higher weighted block) then it is better to keep our current
// candidateBlock and have it fall into bTmp
//
if ((candidateBlock == nullptr) || !candidateBlock->KindIs(BBJ_COND, BBJ_ALWAYS) ||
(candidateBlock->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET) &&
(!candidateBlock->TargetIs(bTmp) || candidateBlock->JumpsToNext())) ||
(candidateBlock->KindIs(BBJ_COND) && !candidateBlock->TrueTargetIs(bTmp)))
{
// otherwise we have a new candidateBlock
//
highestWeight = bTmp->bbWeight;
candidateBlock = lastNonFallThroughBlock->Next();
}
}
const bool bTmpJumpsToNext = bTmp->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET) && bTmp->JumpsToNext();
if ((!bTmp->bbFallsThrough() && !bTmpJumpsToNext) || (bTmp->bbWeight == BB_ZERO_WEIGHT))
{
lastNonFallThroughBlock = bTmp;
}
bTmp = bTmp->Next();
}
// If we didn't find a suitable block then skip this
if (highestWeight == 0)
{
reorderBlock = false;
}
else
{
noway_assert(candidateBlock != nullptr);
// If the candidateBlock is the same a block then skip this
if (candidateBlock == block)
{
reorderBlock = false;
}
else
{
// Set bDest to the block that we want to come after bPrev
bDest = candidateBlock;
// set profHotWeight
profHotWeight = highestWeight - 1;
}
}
}
}
else // we don't have good profile info (or we are falling through)
{
CHECK_FOR_RARE:;
/* We only want to reorder when we have a rarely run */
/* block right after a normal block, */
/* (bPrev is known to be a normal block at this point) */
if (!isRare)
{
if (block->NextIs(bDest) && block->KindIs(BBJ_RETURN) && bPrev->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET))
{
// This is a common case with expressions like "return Expr1 && Expr2" -- move the return
// to establish fall-through.
}
else
{
reorderBlock = false;
}
}
else
{
/* If the jump target bDest is also a rarely run block then we don't want to do the reversal */
if (bDest && bDest->isRunRarely())
{
reorderBlock = false; /* Both block and bDest are rarely run */
}
else
{
// We will move any rarely run blocks blocks
profHotWeight = 0;
}
}
}
if (reorderBlock == false)
{
//
// Check for an unconditional branch to a conditional branch
// which also branches back to our next block
//
const bool optimizedBranch = fgOptimizeBranch(bPrev);
if (optimizedBranch)
{
noway_assert(bPrev->KindIs(BBJ_COND));
optimizedBranches = true;
}
continue;
}
// Now we need to determine which blocks should be moved
//
// We consider one of two choices:
//
// 1. Moving the fall-through blocks (or rarely run blocks) down to
// later in the method and hopefully connecting the jump dest block
// so that it becomes the fall through block
//
// And when bDest is not NULL, we also consider:
//
// 2. Moving the bDest block (or blocks) up to bPrev
// so that it could be used as a fall through block
//
// We will prefer option #1 if we are able to connect the jump dest
// block as the fall though block otherwise will we try to use option #2
//
//
// Consider option #1: relocating blocks starting at 'block'
// to later in flowgraph
//
// We set bStart to the first block that will be relocated
// and bEnd to the last block that will be relocated
BasicBlock* bStart = block;
BasicBlock* bEnd = bStart;
bNext = bEnd->Next();
bool connected_bDest = false;
if ((backwardBranch && !isRare) || block->HasFlag(BBF_DONT_REMOVE)) // Don't choose option #1 when block is the
// start of a try region
{
bStart = nullptr;
bEnd = nullptr;
}
else
{
while (true)
{
// Don't try to split a call finally pair
//
if (bEnd->isBBCallFinallyPair())
{
// Move bEnd and bNext forward
bEnd = bNext;
bNext = bNext->Next();
}
//
// Check for loop exit condition
//
if (bNext == nullptr)
{
break;
}
// Check if we've reached the funclets region, at the end of the function
if (bEnd->NextIs(fgFirstFuncletBB))
{
break;
}
if (bNext == bDest)
{
connected_bDest = true;
break;
}
// All the blocks must have the same try index
// and must not have the BBF_DONT_REMOVE flag set
if (!BasicBlock::sameTryRegion(bStart, bNext) || bNext->HasFlag(BBF_DONT_REMOVE))
{
// exit the loop, bEnd is now set to the
// last block that we want to relocate
break;
}
// If we are relocating rarely run blocks..
if (isRare)
{
// ... then all blocks must be rarely run
if (!bNext->isRunRarely())
{
// exit the loop, bEnd is now set to the
// last block that we want to relocate
break;
}
}
else
{
// If we are moving blocks that are hot then all
// of the blocks moved must be less than profHotWeight */
if (bNext->bbWeight >= profHotWeight)
{
// exit the loop, bEnd is now set to the
// last block that we would relocate
break;
}
}
// Move bEnd and bNext forward
bEnd = bNext;
bNext = bNext->Next();
}
// Set connected_bDest to true if moving blocks [bStart .. bEnd]
// connects with the jump dest of bPrev (i.e bDest) and
// thus allows bPrev fall through instead of jump.
if (bNext == bDest)
{
connected_bDest = true;
}
}
// Now consider option #2: Moving the jump dest block (or blocks)
// up to bPrev
//
// The variables bStart2, bEnd2 and bPrev2 are used for option #2
//
// We will setup bStart2 to the first block that will be relocated
// and bEnd2 to the last block that will be relocated
// and bPrev2 to be the lexical pred of bDest
//
// If after this calculation bStart2 is NULL we cannot use option #2,
// otherwise bStart2, bEnd2 and bPrev2 are all non-NULL and we will use option #2
BasicBlock* bStart2 = nullptr;
BasicBlock* bEnd2 = nullptr;
BasicBlock* bPrev2 = nullptr;
// If option #1 didn't connect bDest and bDest isn't NULL
if ((connected_bDest == false) && (bDest != nullptr) &&
// The jump target cannot be moved if it has the BBF_DONT_REMOVE flag set
!bDest->HasFlag(BBF_DONT_REMOVE))
{
// We will consider option #2: relocating blocks starting at 'bDest' to succeed bPrev
//
// setup bPrev2 to be the lexical pred of bDest
bPrev2 = block;
while (bPrev2 != nullptr)
{
if (bPrev2->NextIs(bDest))
{
break;
}
bPrev2 = bPrev2->Next();
}
if ((bPrev2 != nullptr) && fgEhAllowsMoveBlock(bPrev, bDest))
{
// We have decided that relocating bDest to be after bPrev is best
// Set bStart2 to the first block that will be relocated
// and bEnd2 to the last block that will be relocated
//
// Assigning to bStart2 selects option #2
//
bStart2 = bDest;
bEnd2 = bStart2;
bNext = bEnd2->Next();
while (true)
{
// Don't try to split a call finally pair
//
if (bEnd2->isBBCallFinallyPair())
{
noway_assert(bNext->KindIs(BBJ_CALLFINALLYRET));
// Move bEnd2 and bNext forward
bEnd2 = bNext;
bNext = bNext->Next();
}
// Check for the Loop exit conditions
if (bNext == nullptr)
{
break;
}
if (bEnd2->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET) && bEnd2->JumpsToNext())
{
// Treat jumps to next block as fall-through
}
else if (bEnd2->bbFallsThrough() == false)
{
break;
}
// If we are relocating rarely run blocks..
// All the blocks must have the same try index,
// and must not have the BBF_DONT_REMOVE flag set
if (!BasicBlock::sameTryRegion(bStart2, bNext) || bNext->HasFlag(BBF_DONT_REMOVE))
{
// exit the loop, bEnd2 is now set to the
// last block that we want to relocate
break;
}
if (isRare)
{
/* ... then all blocks must not be rarely run */
if (bNext->isRunRarely())
{
// exit the loop, bEnd2 is now set to the
// last block that we want to relocate
break;
}
}
else
{
// If we are relocating hot blocks
// all blocks moved must be greater than profHotWeight
if (bNext->bbWeight <= profHotWeight)
{
// exit the loop, bEnd2 is now set to the
// last block that we want to relocate
break;
}
}
// Move bEnd2 and bNext forward
bEnd2 = bNext;
bNext = bNext->Next();
}
}
}
// If we are using option #1 then ...
if (bStart2 == nullptr)
{
// Don't use option #1 for a backwards branch
if (bStart == nullptr)
{
continue;
}
// .... Don't move a set of blocks that are already at the end of the main method
if (bEnd == fgLastBBInMainFunction())
{
continue;
}
}
#ifdef DEBUG
if (verbose)
{
if (bDest != nullptr)
{
if (bPrev->KindIs(BBJ_COND))
{
printf("Decided to reverse conditional branch at block " FMT_BB " branch to " FMT_BB " ",
bPrev->bbNum, bDest->bbNum);
}
else if (bPrev->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET))
{
printf("Decided to straighten unconditional branch at block " FMT_BB " branch to " FMT_BB " ",
bPrev->bbNum, bDest->bbNum);
}
else
{
printf("Decided to place hot code after " FMT_BB ", placed " FMT_BB " after this block ",
bPrev->bbNum, bDest->bbNum);
}
if (profHotWeight > 0)
{
printf("because of IBC profile data\n");
}
else
{
if (bPrev->bbFallsThrough())
{
printf("since it falls into a rarely run block\n");
}
else
{
printf("since it is succeeded by a rarely run block\n");
}
}
}
else
{
printf("Decided to relocate block(s) after block " FMT_BB " since they are %s block(s)\n", bPrev->bbNum,
block->isRunRarely() ? "rarely run" : "uncommonly run");
}
}
#endif // DEBUG
// We will set insertAfterBlk to the block the precedes our insertion range
// We will set bStartPrev to be the block that precedes the set of blocks that we are moving
BasicBlock* insertAfterBlk;
BasicBlock* bStartPrev;
if (bStart2 != nullptr)
{
// Option #2: relocating blocks starting at 'bDest' to follow bPrev
// Update bStart and bEnd so that we can use these two for all later operations
bStart = bStart2;
bEnd = bEnd2;
// Set bStartPrev to be the block that comes before bStart
bStartPrev = bPrev2;
// We will move [bStart..bEnd] to immediately after bPrev
insertAfterBlk = bPrev;
}
else
{
// option #1: Moving the fall-through blocks (or rarely run blocks) down to later in the method
// Set bStartPrev to be the block that come before bStart
bStartPrev = bPrev;
// We will move [bStart..bEnd] but we will pick the insert location later
insertAfterBlk = nullptr;
}
// We are going to move [bStart..bEnd] so they can't be NULL
noway_assert(bStart != nullptr);
noway_assert(bEnd != nullptr);
// bEnd can't be a BBJ_CALLFINALLY unless it is a RETLESS call
noway_assert(!bEnd->KindIs(BBJ_CALLFINALLY) || bEnd->HasFlag(BBF_RETLESS_CALL));
// bStartPrev must be set to the block that precedes bStart
noway_assert(bStartPrev->NextIs(bStart));
// Since we will be unlinking [bStart..bEnd],
// we need to compute and remember if bStart is in each of
// the try and handler regions
//
bool* fStartIsInTry = nullptr;
bool* fStartIsInHnd = nullptr;
if (compHndBBtabCount > 0)
{
fStartIsInTry = new (this, CMK_Generic) bool[compHndBBtabCount];
fStartIsInHnd = new (this, CMK_Generic) bool[compHndBBtabCount];
for (XTnum = 0, HBtab = compHndBBtab; XTnum < compHndBBtabCount; XTnum++, HBtab++)
{
fStartIsInTry[XTnum] = HBtab->InTryRegionBBRange(bStart);
fStartIsInHnd[XTnum] = HBtab->InHndRegionBBRange(bStart);
}
}
/* Temporarily unlink [bStart..bEnd] from the flow graph */
const bool bStartPrevJumpsToNext = bStartPrev->KindIs(BBJ_ALWAYS) && bStartPrev->JumpsToNext();
fgUnlinkRange(bStart, bEnd);
if (insertAfterBlk == nullptr)
{
// Find new location for the unlinked block(s)
// Set insertAfterBlk to the block which will precede the insertion point
if (!bStart->hasTryIndex() && isRare)
{
// We'll just insert the blocks at the end of the method. If the method
// has funclets, we will insert at the end of the main method but before
// any of the funclets. Note that we create funclets before we call
// fgReorderBlocks().
insertAfterBlk = fgLastBBInMainFunction();
noway_assert(insertAfterBlk != bPrev);
}
else
{
BasicBlock* startBlk;
BasicBlock* lastBlk;
EHblkDsc* ehDsc = ehInitTryBlockRange(bStart, &startBlk, &lastBlk);
BasicBlock* endBlk;
/* Setup startBlk and endBlk as the range to search */
if (ehDsc != nullptr)
{
endBlk = lastBlk->Next();
/*
Multiple (nested) try regions might start from the same BB.
For example,
try3 try2 try1
|--- |--- |--- BB01
| | | BB02
| | |--- BB03
| | BB04
| |------------ BB05
| BB06
|------------------- BB07
Now if we want to insert in try2 region, we will start with startBlk=BB01.
The following loop will allow us to start from startBlk==BB04.
*/
while (!BasicBlock::sameTryRegion(startBlk, bStart) && (startBlk != endBlk))
{
startBlk = startBlk->Next();
}
// startBlk cannot equal endBlk as it must come before endBlk
if (startBlk == endBlk)
{
goto CANNOT_MOVE;
}
// we also can't start searching the try region at bStart
if (startBlk == bStart)
{
// if bEnd is the last block in the method or
// or if bEnd->bbNext is in a different try region
// then we cannot move the blocks
//
if (bEnd->IsLast() || !BasicBlock::sameTryRegion(startBlk, bEnd->Next()))
{
goto CANNOT_MOVE;
}
startBlk = bEnd->Next();
// Check that the new startBlk still comes before endBlk
// startBlk cannot equal endBlk as it must come before endBlk
if (startBlk == endBlk)
{
goto CANNOT_MOVE;
}
BasicBlock* tmpBlk = startBlk;
while ((tmpBlk != endBlk) && (tmpBlk != nullptr))
{
tmpBlk = tmpBlk->Next();
}
// when tmpBlk is NULL that means startBlk is after endBlk
// so there is no way to move bStart..bEnd within the try region
if (tmpBlk == nullptr)
{
goto CANNOT_MOVE;
}
}
}
else
{
noway_assert(isRare == false);
/* We'll search through the entire main method */
startBlk = fgFirstBB;
endBlk = fgEndBBAfterMainFunction();
}
// Calculate nearBlk and jumpBlk and then call fgFindInsertPoint()
// to find our insertion block
//
{
// If the set of blocks that we are moving ends with a BBJ_ALWAYS to
// another [rarely run] block that comes after bPrev (forward branch)
// then we can set up nearBlk to eliminate this jump sometimes
//
BasicBlock* nearBlk = nullptr;
BasicBlock* jumpBlk = nullptr;
if (bEnd->KindIs(BBJ_ALWAYS, BBJ_CALLFINALLYRET) && !bEnd->JumpsToNext() &&
(!isRare || bEnd->GetTarget()->isRunRarely()) &&
fgIsForwardBranch(bEnd, bEnd->GetTarget(), bPrev))
{
// Set nearBlk to be the block in [startBlk..endBlk]
// such that nearBlk->NextIs(bEnd->JumpDest)
// if no such block exists then set nearBlk to NULL
nearBlk = startBlk;
jumpBlk = bEnd;
do
{
// We do not want to set nearBlk to bPrev
// since then we will not move [bStart..bEnd]
//
if (nearBlk != bPrev)
{
// Check if nearBlk satisfies our requirement
if (nearBlk->NextIs(bEnd->GetTarget()))
{
break;
}
}
// Did we reach the endBlk?
if (nearBlk == endBlk)
{
nearBlk = nullptr;
break;
}
// advance nearBlk to the next block
nearBlk = nearBlk->Next();
} while (nearBlk != nullptr);
}
// if nearBlk is NULL then we set nearBlk to be the
// first block that we want to insert after.
if (nearBlk == nullptr)
{
if (bDest != nullptr)
{
// we want to insert after bDest
nearBlk = bDest;
}
else
{
// we want to insert after bPrev
nearBlk = bPrev;
}
}
/* Set insertAfterBlk to the block which we will insert after. */
insertAfterBlk =
fgFindInsertPoint(bStart->bbTryIndex,
true, // Insert in the try region.
startBlk, endBlk, nearBlk, jumpBlk, bStart->bbWeight == BB_ZERO_WEIGHT);
}
/* See if insertAfterBlk is the same as where we started, */
/* or if we could not find any insertion point */
if ((insertAfterBlk == bPrev) || (insertAfterBlk == nullptr))
{
CANNOT_MOVE:;
/* We couldn't move the blocks, so put everything back */
/* relink [bStart .. bEnd] into the flow graph */
bPrev->SetNext(bStart);
if (!bEnd->IsLast())
{
bEnd->Next()->SetPrev(bEnd);
}
#ifdef DEBUG
if (verbose)
{
if (bStart != bEnd)
{
printf("Could not relocate blocks (" FMT_BB " .. " FMT_BB ")\n", bStart->bbNum,
bEnd->bbNum);
}
else
{
printf("Could not relocate block " FMT_BB "\n", bStart->bbNum);
}
}
#endif // DEBUG
continue;
}
}
}
noway_assert(insertAfterBlk != nullptr);
noway_assert(bStartPrev != nullptr);
noway_assert(bStartPrev != insertAfterBlk);
#ifdef DEBUG
movedBlocks = true;
if (verbose)
{
const char* msg;
if (bStart2 != nullptr)
{
msg = "hot";
}
else
{
if (isRare)
{
msg = "rarely run";
}
else
{
msg = "uncommon";
}
}
printf("Relocated %s ", msg);
if (bStart != bEnd)
{
printf("blocks (" FMT_BB " .. " FMT_BB ")", bStart->bbNum, bEnd->bbNum);
}
else
{
printf("block " FMT_BB, bStart->bbNum);
}
if (bPrev->KindIs(BBJ_COND))
{
printf(" by reversing conditional jump at " FMT_BB "\n", bPrev->bbNum);
}
else
{
printf("\n", bPrev->bbNum);
}
}
#endif // DEBUG
if (bPrev->KindIs(BBJ_COND))
{
/* Reverse the bPrev jump condition */
Statement* const condTestStmt = bPrev->lastStmt();
GenTree* const condTest = condTestStmt->GetRootNode();
noway_assert(condTest->gtOper == GT_JTRUE);
condTest->AsOp()->gtOp1 = gtReverseCond(condTest->AsOp()->gtOp1);
FlowEdge* const trueEdge = bPrev->GetTrueEdge();
FlowEdge* const falseEdge = bPrev->GetFalseEdge();
bPrev->SetTrueEdge(falseEdge);
bPrev->SetFalseEdge(trueEdge);
// may need to rethread
//
if (fgNodeThreading == NodeThreading::AllTrees)
{
JITDUMP("Rethreading " FMT_STMT "\n", condTestStmt->GetID());
gtSetStmtInfo(condTestStmt);
fgSetStmtSeq(condTestStmt);
}
if (bStart2 != nullptr)
{
noway_assert(insertAfterBlk == bPrev);
noway_assert(insertAfterBlk->NextIs(block));
}
}
// If we are moving blocks that are at the end of a try or handler
// we will need to shorten ebdTryLast or ebdHndLast
//
ehUpdateLastBlocks(bEnd, bStartPrev);
// If we are moving blocks into the end of a try region or handler region
// we will need to extend ebdTryLast or ebdHndLast so the blocks that we
// are moving are part of this try or handler region.
//
for (XTnum = 0, HBtab = compHndBBtab; XTnum < compHndBBtabCount; XTnum++, HBtab++)
{
// Are we moving blocks to the end of a try region?
if (HBtab->ebdTryLast == insertAfterBlk)
{
if (fStartIsInTry[XTnum])
{
// bStart..bEnd is in the try, so extend the try region
fgSetTryEnd(HBtab, bEnd);
}
}
// Are we moving blocks to the end of a handler region?
if (HBtab->ebdHndLast == insertAfterBlk)
{
if (fStartIsInHnd[XTnum])
{
// bStart..bEnd is in the handler, so extend the handler region
fgSetHndEnd(HBtab, bEnd);
}
}
}
/* We have decided to insert the block(s) after 'insertAfterBlk' */
fgMoveBlocksAfter(bStart, bEnd, insertAfterBlk);
if (bDest)
{
/* We may need to insert an unconditional branch after bPrev to bDest */
fgConnectFallThrough(bPrev, bDest);
}
else
{
/* If bPrev falls through, we must insert a jump to block */
fgConnectFallThrough(bPrev, block);
}
BasicBlock* bSkip = bEnd->Next();
/* If bEnd falls through, we must insert a jump to bNext */
fgConnectFallThrough(bEnd, bNext);
if (bStart2 == nullptr)
{
/* If insertAfterBlk falls through, we are forced to */
/* add a jump around the block(s) we just inserted */
fgConnectFallThrough(insertAfterBlk, bSkip);
}
else
{
/* We may need to insert an unconditional branch after bPrev2 to bStart */
fgConnectFallThrough(bPrev2, bStart);
}
#if DEBUG
if (verbose)
{
printf("\nAfter this change in fgReorderBlocks the BB graph is:");
fgDispBasicBlocks(verboseTrees);
printf("\n");
}
fgVerifyHandlerTab();
// Make sure that the predecessor lists are accurate
if (expensiveDebugCheckLevel >= 2)
{
fgDebugCheckBBlist();
}
#endif // DEBUG
// Set our iteration point 'block' to be the new bPrev->bbNext
// It will be used as the next bPrev
block = bPrev->Next();
} // end of for loop(bPrev,block)
const bool changed = movedBlocks || newRarelyRun || optimizedSwitches || optimizedBranches;
if (changed)
{
#if DEBUG
// Make sure that the predecessor lists are accurate
if (expensiveDebugCheckLevel >= 2)
{
fgDebugCheckBBlist();
}
#endif // DEBUG
}
return changed;
}