Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Differential D35844 Diff 108098 lib/CodeGen/BranchFolding.cpp

Changeset View

Standalone View

View Options

lib/CodeGen/BranchFolding.cpp

Show First 20 Lines • Show All 298 Lines • ▼ Show 20 Linesstatic unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
MachineBasicBlock::iterator &I2) { MachineBasicBlock::iterator &I2) {
I1 = MBB1->end(); I1 = MBB1->end();
I2 = MBB2->end(); I2 = MBB2->end();
unsigned TailLen = 0; unsigned TailLen = 0;
while (I1 != MBB1->begin() && I2 != MBB2->begin()) { while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
--I1; --I2; --I1; --I2;
// Skip debugging pseudos; necessary to avoid changing the code. // Skip debugging pseudos; necessary to avoid changing the code.
while (I1->isDebugValue()) { while (I1->isDirective()) {
if (I1==MBB1->begin()) { if (I1==MBB1->begin()) {
while (I2->isDebugValue()) { while (I2->isDirective()) {
if (I2==MBB2->begin()) if (I2==MBB2->begin())
// I1==DBG at begin; I2==DBG at begin // I1==DBG at begin; I2==DBG at begin
return TailLen; return TailLen;
--I2; --I2;
} }
++I2; ++I2;
// I1==DBG at begin; I2==non-DBG, or first of DBGs not at begin // I1==DBG at begin; I2==non-DBG, or first of DBGs not at begin
return TailLen; return TailLen;
} }
--I1; --I1;
} }
// I1==first (untested) non-DBG preceding known match // I1==first (untested) non-DBG preceding known match
while (I2->isDebugValue()) { while (I2->isDirective()) {
if (I2==MBB2->begin()) { if (I2==MBB2->begin()) {
++I1; ++I1;
// I1==non-DBG, or first of DBGs not at begin; I2==DBG at begin // I1==non-DBG, or first of DBGs not at begin; I2==DBG at begin
return TailLen; return TailLen;
} }
--I2; --I2;
} }
// I1, I2==first (untested) non-DBGs preceding known match // I1, I2==first (untested) non-DBGs preceding known match
Show All 26 Lines if (I2 == MBB2->begin() && I1 != MBB1->begin()) {
--I1; --I1;
while (I1->isDebugValue()) { while (I1->isDebugValue()) {
if (I1 == MBB1->begin()) if (I1 == MBB1->begin())
return TailLen; return TailLen;
--I1; --I1;
} }
++I1; ++I1;
} }
// Ensure that I1 and I2 do not point to a CFI_INSTRUCTION. This can happen if
// I1 and I2 are non-identical when compared and then one or both of them ends
// up pointing to a CFI instruction after being incremented. For example:
/*
BB1:
...
INSTRUCTION_A
ADD32ri8 <- last common instruction
...
BB2:
...
INSTRUCTION_B
CFI_INSTRUCTION
ADD32ri8 <- last common instruction
...
*/
// When INSTRUCTION_A and INSTRUCTION_B are compared as not equal, after
// incrementing the iterators, I1 will point to ADD, however I2 will point to
// the CFI instruction. Later on, this leads to BB2 being 'hacked off' at the
// wrong place (in ReplaceTailWithBranchTo()) which results in losing this CFI
// instruction.
while (I1 != MBB1->end() && I1->isCFIInstruction()) {
++I1;
}
while (I2 != MBB2->end() && I2->isCFIInstruction()) {
++I2;
}
return TailLen; return TailLen;
} }
void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst, void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
MachineBasicBlock *NewDest) { MachineBasicBlock *NewDest) {
TII->ReplaceTailWithBranchTo(OldInst, NewDest); TII->ReplaceTailWithBranchTo(OldInst, NewDest);
if (UpdateLiveIns) { if (UpdateLiveIns) {
Show All 39 LinesMachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
// Add the new block to the funclet. // Add the new block to the funclet.
const auto &FuncletI = FuncletMembership.find(&CurMBB); const auto &FuncletI = FuncletMembership.find(&CurMBB);
if (FuncletI != FuncletMembership.end()) { if (FuncletI != FuncletMembership.end()) {
auto n = FuncletI->second; auto n = FuncletI->second;
FuncletMembership[NewMBB] = n; FuncletMembership[NewMBB] = n;
} }
// Recalculate CFI info for CurMBB. Use existing incoming cfa offset and
// register.
CurMBB.recalculateCFIInfo(true);
// Recalculate CFI info for NewMBB. Use CurMBB's outgoing cfa offset and
// register as NewMBB's incoming.
NewMBB->recalculateCFIInfo(false, CurMBB.getOutgoingCFAOffset(),
CurMBB.getOutgoingCFARegister(),
CurMBB.getAdjustOutgoingCFAOffset());
return NewMBB; return NewMBB;
} }
/// EstimateRuntime - Make a rough estimate for how long it will take to run /// EstimateRuntime - Make a rough estimate for how long it will take to run
/// the specified code. /// the specified code.
static unsigned EstimateRuntime(MachineBasicBlock::iterator I, static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
MachineBasicBlock::iterator E) { MachineBasicBlock::iterator E) {
unsigned Time = 0; unsigned Time = 0;
for (; I != E; ++I) { for (; I != E; ++I) {
if (I->isDebugValue()) if (I->isDirective())
continue; continue;
if (I->isCall()) if (I->isCall())
Time += 10; Time += 10;
else if (I->mayLoad() || I->mayStore()) else if (I->mayLoad() || I->mayStore())
Time += 2; Time += 2;
else else
++Time; ++Time;
} }
▲ Show 20 Lines • Show All 337 Lines • ▼ Show 20 Lines if (i != commonTailIndex)
NextCommonInsts[i] = SameTails[i].getTailStartPos(); NextCommonInsts[i] = SameTails[i].getTailStartPos();
else { else {
assert(SameTails[i].getTailStartPos() == MBB->begin() && assert(SameTails[i].getTailStartPos() == MBB->begin() &&
"MBB is not a common tail only block"); "MBB is not a common tail only block");
} }
} }
for (auto &MI : *MBB) { for (auto &MI : *MBB) {
if (MI.isDebugValue()) if (MI.isDirective())
continue; continue;
DebugLoc DL = MI.getDebugLoc(); DebugLoc DL = MI.getDebugLoc();
for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) { for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
if (i == commonTailIndex) if (i == commonTailIndex)
continue; continue;
auto &Pos = NextCommonInsts[i]; auto &Pos = NextCommonInsts[i];
assert(Pos != SameTails[i].getBlock()->end() && assert(Pos != SameTails[i].getBlock()->end() &&
"Reached BB end within common tail"); "Reached BB end within common tail");
while (Pos->isDebugValue()) { while (Pos->isDirective()) {
++Pos; ++Pos;
assert(Pos != SameTails[i].getBlock()->end() && assert(Pos != SameTails[i].getBlock()->end() &&
"Reached BB end within common tail"); "Reached BB end within common tail");
} }
assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!"); assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc()); DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
NextCommonInsts[i] = ++Pos; NextCommonInsts[i] = ++Pos;
} }
Show All 16 LinesmergeOperations(MachineBasicBlock::iterator MBBIStartPos,
MachineBasicBlock::reverse_iterator MBBIE = MBB->rend(); MachineBasicBlock::reverse_iterator MBBIE = MBB->rend();
MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin(); MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend(); MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
while (CommonTailLen--) { while (CommonTailLen--) {
assert(MBBI != MBBIE && "Reached BB end within common tail length!"); assert(MBBI != MBBIE && "Reached BB end within common tail length!");
(void)MBBIE; (void)MBBIE;
if (MBBI->isDebugValue()) { if (MBBI->isDirective()) {
++MBBI; ++MBBI;
continue; continue;
} }
while ((MBBICommon != MBBIECommon) && MBBICommon->isDebugValue()) while ((MBBICommon != MBBIECommon) && MBBICommon->isDirective())
++MBBICommon; ++MBBICommon;
assert(MBBICommon != MBBIECommon && assert(MBBICommon != MBBIECommon &&
"Reached BB end within common tail length!"); "Reached BB end within common tail length!");
assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!"); assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");
// Merge MMOs from memory operations in the common block. // Merge MMOs from memory operations in the common block.
if (MBBICommon->mayLoad() || MBBICommon->mayStore()) if (MBBICommon->mayLoad() || MBBICommon->mayStore())
▲ Show 20 Lines • Show All 126 Lines • ▼ Show 20 Lines for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
if (commonTailIndex == i) if (commonTailIndex == i)
continue; continue;
DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber() DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
<< (i == e-1 ? "" : ", ")); << (i == e-1 ? "" : ", "));
// Merge operations (MMOs, undef flags) // Merge operations (MMOs, undef flags)
mergeOperations(SameTails[i].getTailStartPos(), *MBB); mergeOperations(SameTails[i].getTailStartPos(), *MBB);
// Hack the end off BB i, making it jump to BB commonTailIndex instead. // Hack the end off BB i, making it jump to BB commonTailIndex instead.
ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB); ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
// Recalculate CFI info for BB. Use existing incoming cfa offset and
// register.
SameTails[i].getBlock()->recalculateCFIInfo(true);
// BB i is no longer a predecessor of SuccBB; remove it from the worklist. // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
MergePotentials.erase(SameTails[i].getMPIter()); MergePotentials.erase(SameTails[i].getMPIter());
} }
DEBUG(dbgs() << "\n"); DEBUG(dbgs() << "\n");
// We leave commonTailIndex in the worklist in case there are other blocks // We leave commonTailIndex in the worklist in case there are other blocks
// that match it with a smaller number of instructions. // that match it with a smaller number of instructions.
MadeChange = true; MadeChange = true;
} }
▲ Show 20 Lines • Show All 394 Lines • ▼ Show 20 Lines if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
DuplicateDbg.eraseFromParent(); DuplicateDbg.eraseFromParent();
} }
} }
PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end()); PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
PrevBB.removeSuccessor(PrevBB.succ_begin()); PrevBB.removeSuccessor(PrevBB.succ_begin());
assert(PrevBB.succ_empty()); assert(PrevBB.succ_empty());
PrevBB.transferSuccessors(MBB); PrevBB.transferSuccessors(MBB);
MadeChange = true; MadeChange = true;
// Update CFI info for PrevBB.
PrevBB.mergeCFIInfo(MBB);
return MadeChange; return MadeChange;
} }
// If the previous branch *only* branches to *this* block (conditional or // If the previous branch *only* branches to *this* block (conditional or
// not) remove the branch. // not) remove the branch.
if (PriorTBB == MBB && !PriorFBB) { if (PriorTBB == MBB && !PriorFBB) {
TII->removeBranch(PrevBB); TII->removeBranch(PrevBB);
MadeChange = true; MadeChange = true;
▲ Show 20 Lines • Show All 621 Lines • Show Last 20 Lines