Page MenuHomePhabricator

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

Differential D35844 Diff 119589 lib/CodeGen/BranchFolding.cpp

Changeset View

Standalone View

View Options

lib/CodeGen/BranchFolding.cpp

Show First 20 Lines • Show All 285 Lines • ▼ Show 20 Lines
static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) { static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) {
MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr(); MachineBasicBlock::const_iterator I = MBB.getLastNonDebugInstr();
if (I == MBB.end()) if (I == MBB.end())
return 0; return 0;
return HashMachineInstr(*I); return HashMachineInstr(*I);
} }
// Whether MI should be counted as an instruction when calculating common tail.
static bool countsAsInstruction(const MachineInstr &MI) {
return !(MI.isDebugValue() || MI.isCFIInstruction());
}
/// ComputeCommonTailLength - Given two machine basic blocks, compute the number /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
/// of instructions they actually have in common together at their end. Return /// of instructions they actually have in common together at their end. Return
/// iterators for the first shared instruction in each block. /// iterators for the first shared instruction in each block.
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
MachineBasicBlock *MBB2, MachineBasicBlock *MBB2,
MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I1,
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 (!countsAsInstruction(*I1)) {
if (I1==MBB1->begin()) { if (I1==MBB1->begin()) {
while (I2->isDebugValue()) { while (!countsAsInstruction(*I2)) {
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 (!countsAsInstruction(*I2)) {
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) {
if (UpdateLiveIns) { if (UpdateLiveIns) {
// OldInst should always point to an instruction. // OldInst should always point to an instruction.
MachineBasicBlock &OldMBB = *OldInst->getParent(); MachineBasicBlock &OldMBB = *OldInst->getParent();
▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines
} }
/// 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 (!countsAsInstruction(*I))
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 343 Lines • ▼ Show 20 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 (!countsAsInstruction(*MBBI)) {
++MBBI; ++MBBI;
continue; continue;
} }
while ((MBBICommon != MBBIECommon) && MBBICommon->isDebugValue()) while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
++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 All 23 Lines if (i != commonTailIndex) {
mergeOperations(SameTails[i].getTailStartPos(), *MBB); mergeOperations(SameTails[i].getTailStartPos(), *MBB);
} 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 (!countsAsInstruction(MI))
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 (!countsAsInstruction(*Pos)) {
++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 20 Lines • Show All 1,184 Lines • Show Last 20 Lines