ShrinkWrapping.cpp [plain text]
#define DEBUG_TYPE "shrink-wrap"
#include "PrologEpilogInserter.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include <sstream>
using namespace llvm;
STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");
static cl::opt<bool>
ShrinkWrapping("shrink-wrap",
cl::desc("Shrink wrap callee-saved register spills/restores"));
static cl::opt<std::string>
ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
cl::desc("Shrink wrap the specified function"),
cl::value_desc("funcname"),
cl::init(""));
enum ShrinkWrapDebugLevel {
None, BasicInfo, Iterations, Details
};
static cl::opt<enum ShrinkWrapDebugLevel>
ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
cl::desc("Print shrink wrapping debugging information"),
cl::values(
clEnumVal(None , "disable debug output"),
clEnumVal(BasicInfo , "print basic DF sets"),
clEnumVal(Iterations, "print SR sets for each iteration"),
clEnumVal(Details , "print all DF sets"),
clEnumValEnd));
void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
if (ShrinkWrapping || ShrinkWrapFunc != "") {
AU.addRequired<MachineLoopInfo>();
AU.addRequired<MachineDominatorTree>();
}
AU.addPreserved<MachineLoopInfo>();
AU.addPreserved<MachineDominatorTree>();
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
MachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) {
assert(LP && "Machine loop is NULL.");
MachineBasicBlock* PHDR = LP->getLoopPreheader();
MachineLoop* PLP = LP->getParentLoop();
while (PLP) {
PHDR = PLP->getLoopPreheader();
PLP = PLP->getParentLoop();
}
return PHDR;
}
MachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) {
if (LP == 0)
return 0;
MachineLoop* PLP = LP->getParentLoop();
while (PLP) {
LP = PLP;
PLP = PLP->getParentLoop();
}
return LP;
}
bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
return (MBB && !MBB->empty() && MBB->back().isReturn());
}
void PEI::clearAnticAvailSets() {
AnticIn.clear();
AnticOut.clear();
AvailIn.clear();
AvailOut.clear();
}
void PEI::clearAllSets() {
ReturnBlocks.clear();
clearAnticAvailSets();
UsedCSRegs.clear();
CSRUsed.clear();
TLLoops.clear();
CSRSave.clear();
CSRRestore.clear();
}
void PEI::initShrinkWrappingInfo() {
clearAllSets();
EntryBlock = 0;
#ifndef NDEBUG
HasFastExitPath = false;
#endif
ShrinkWrapThisFunction = ShrinkWrapping;
#ifndef NDEBUG
if (ShrinkWrapFunc != "") {
std::string MFName = MF->getName().str();
ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
}
#endif
}
void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {
DEBUG(MF = &Fn);
initShrinkWrappingInfo();
DEBUG(if (ShrinkWrapThisFunction) {
dbgs() << "Place CSR spills/restores for "
<< MF->getName() << "\n";
});
if (calculateSets(Fn))
placeSpillsAndRestores(Fn);
}
bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {
bool changed = false;
SmallVector<MachineBasicBlock*, 4> successors;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
if (SUCC != MBB)
successors.push_back(SUCC);
}
unsigned i = 0, e = successors.size();
if (i != e) {
CSRegSet prevAnticOut = AnticOut[MBB];
MachineBasicBlock* SUCC = successors[i];
AnticOut[MBB] = AnticIn[SUCC];
for (++i; i != e; ++i) {
SUCC = successors[i];
AnticOut[MBB] &= AnticIn[SUCC];
}
if (prevAnticOut != AnticOut[MBB])
changed = true;
}
CSRegSet prevAnticIn = AnticIn[MBB];
AnticIn[MBB] = CSRUsed[MBB] | AnticOut[MBB];
if (prevAnticIn != AnticIn[MBB])
changed = true;
return changed;
}
bool PEI::calcAvailInOut(MachineBasicBlock* MBB) {
bool changed = false;
SmallVector<MachineBasicBlock*, 4> predecessors;
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock* PRED = *PI;
if (PRED != MBB)
predecessors.push_back(PRED);
}
unsigned i = 0, e = predecessors.size();
if (i != e) {
CSRegSet prevAvailIn = AvailIn[MBB];
MachineBasicBlock* PRED = predecessors[i];
AvailIn[MBB] = AvailOut[PRED];
for (++i; i != e; ++i) {
PRED = predecessors[i];
AvailIn[MBB] &= AvailOut[PRED];
}
if (prevAvailIn != AvailIn[MBB])
changed = true;
}
CSRegSet prevAvailOut = AvailOut[MBB];
AvailOut[MBB] = CSRUsed[MBB] | AvailIn[MBB];
if (prevAvailOut != AvailOut[MBB])
changed = true;
return changed;
}
void PEI::calculateAnticAvail(MachineFunction &Fn) {
clearAnticAvailSets();
bool changed = true;
unsigned iterations = 0;
while (changed) {
changed = false;
++iterations;
for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
changed |= calcAnticInOut(MBB);
changed |= calcAvailInOut(MBB);
}
}
DEBUG({
if (ShrinkWrapDebugging >= Details) {
dbgs()
<< "-----------------------------------------------------------\n"
<< " Antic/Avail Sets:\n"
<< "-----------------------------------------------------------\n"
<< "iterations = " << iterations << "\n"
<< "-----------------------------------------------------------\n"
<< "MBB | USED | ANTIC_IN | ANTIC_OUT | AVAIL_IN | AVAIL_OUT\n"
<< "-----------------------------------------------------------\n";
for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
dumpSets(MBB);
}
dbgs()
<< "-----------------------------------------------------------\n";
}
});
}
void PEI::propagateUsesAroundLoop(MachineBasicBlock* MBB, MachineLoop* LP) {
if (! MBB || !LP)
return;
std::vector<MachineBasicBlock*> loopBlocks = LP->getBlocks();
for (unsigned i = 0, e = loopBlocks.size(); i != e; ++i) {
MachineBasicBlock* LBB = loopBlocks[i];
if (LBB == MBB)
continue;
if (CSRUsed[LBB].contains(CSRUsed[MBB]))
continue;
CSRUsed[LBB] |= CSRUsed[MBB];
}
}
bool PEI::calculateSets(MachineFunction &Fn) {
const std::vector<CalleeSavedInfo> CSI =
Fn.getFrameInfo()->getCalleeSavedInfo();
if (CSI.empty()) {
DEBUG(if (ShrinkWrapThisFunction)
dbgs() << "DISABLED: " << Fn.getName()
<< ": uses no callee-saved registers\n");
return false;
}
EntryBlock = Fn.begin();
for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end();
MBB != E; ++MBB)
if (isReturnBlock(MBB))
ReturnBlocks.push_back(MBB);
DEBUG(if (ShrinkWrapThisFunction)
findFastExitPath());
if (Fn.size() > 500) {
DEBUG(if (ShrinkWrapThisFunction)
dbgs() << "DISABLED: " << Fn.getName()
<< ": too large (" << Fn.size() << " MBBs)\n");
ShrinkWrapThisFunction = false;
}
if (! ShrinkWrapThisFunction)
return false;
for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
UsedCSRegs.set(inx);
}
MachineLoopInfo &LI = getAnalysis<MachineLoopInfo>();
MachineDominatorTree &DT = getAnalysis<MachineDominatorTree>();
const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
bool allCSRUsesInEntryBlock = true;
for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end(); ++I) {
for (unsigned inx = 0, e = CSI.size(); inx != e; ++inx) {
unsigned Reg = CSI[inx].getReg();
for (unsigned opInx = 0, opEnd = I->getNumOperands();
opInx != opEnd; ++opInx) {
const MachineOperand &MO = I->getOperand(opInx);
if (! (MO.isReg() && (MO.isUse() || MO.isDef())))
continue;
unsigned MOReg = MO.getReg();
if (!MOReg)
continue;
if (MOReg == Reg ||
(TargetRegisterInfo::isPhysicalRegister(MOReg) &&
TargetRegisterInfo::isPhysicalRegister(Reg) &&
TRI->isSubRegister(Reg, MOReg))) {
CSRUsed[MBB].set(inx);
if (MBB != EntryBlock)
allCSRUsesInEntryBlock = false;
}
}
}
}
if (CSRUsed[MBB].empty())
continue;
if (MachineLoop* LP = LI.getLoopFor(MBB)) {
MachineBasicBlock* HDR = getTopLevelLoopPreheader(LP);
MachineLoop* PLP = getTopLevelLoopParent(LP);
if (! HDR) {
HDR = PLP->getHeader();
assert(HDR->pred_size() > 0 && "Loop header has no predecessors?");
MachineBasicBlock::pred_iterator PI = HDR->pred_begin();
HDR = *PI;
}
TLLoops[HDR] = PLP;
if (LP->getLoopDepth() > 1) {
for (MachineLoop* PLP = LP->getParentLoop(); PLP;
PLP = PLP->getParentLoop()) {
propagateUsesAroundLoop(MBB, PLP);
}
} else {
propagateUsesAroundLoop(MBB, LP);
}
}
}
if (allCSRUsesInEntryBlock) {
DEBUG(dbgs() << "DISABLED: " << Fn.getName()
<< ": all CSRs used in EntryBlock\n");
ShrinkWrapThisFunction = false;
} else {
bool allCSRsUsedInEntryFanout = true;
for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
SE = EntryBlock->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
if (CSRUsed[SUCC] != UsedCSRegs)
allCSRsUsedInEntryFanout = false;
}
if (allCSRsUsedInEntryFanout) {
DEBUG(dbgs() << "DISABLED: " << Fn.getName()
<< ": all CSRs used in imm successors of EntryBlock\n");
ShrinkWrapThisFunction = false;
}
}
if (ShrinkWrapThisFunction) {
CSRegSet CSRUsedInChokePoints;
for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
if (MBB == EntryBlock || CSRUsed[MBB].empty() || MBB->succ_size() < 1)
continue;
bool dominatesExitNodes = true;
for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
if (! DT.dominates(MBB, ReturnBlocks[ri])) {
dominatesExitNodes = false;
break;
}
if (dominatesExitNodes) {
CSRUsedInChokePoints |= CSRUsed[MBB];
if (CSRUsedInChokePoints == UsedCSRegs) {
DEBUG(dbgs() << "DISABLED: " << Fn.getName()
<< ": all CSRs used in choke point(s) at "
<< getBasicBlockName(MBB) << "\n");
ShrinkWrapThisFunction = false;
break;
}
}
}
}
if (! ShrinkWrapThisFunction)
return false;
DEBUG({
dbgs() << "ENABLED: " << Fn.getName();
if (HasFastExitPath)
dbgs() << " (fast exit path)";
dbgs() << "\n";
if (ShrinkWrapDebugging >= BasicInfo) {
dbgs() << "------------------------------"
<< "-----------------------------\n";
dbgs() << "UsedCSRegs = " << stringifyCSRegSet(UsedCSRegs) << "\n";
if (ShrinkWrapDebugging >= Details) {
dbgs() << "------------------------------"
<< "-----------------------------\n";
dumpAllUsed();
}
}
});
calculateAnticAvail(Fn);
return true;
}
bool PEI::addUsesForMEMERegion(MachineBasicBlock* MBB,
SmallVector<MachineBasicBlock*, 4>& blks) {
if (MBB->succ_size() < 2 && MBB->pred_size() < 2) {
bool processThisBlock = false;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
if (SUCC->pred_size() > 1) {
processThisBlock = true;
break;
}
}
if (!CSRRestore[MBB].empty() && MBB->succ_size() > 0) {
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock* PRED = *PI;
if (PRED->succ_size() > 1) {
processThisBlock = true;
break;
}
}
}
if (! processThisBlock)
return false;
}
CSRegSet prop;
if (!CSRSave[MBB].empty())
prop = CSRSave[MBB];
else if (!CSRRestore[MBB].empty())
prop = CSRRestore[MBB];
else
prop = CSRUsed[MBB];
if (prop.empty())
return false;
bool addedUses = false;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
if (SUCC == MBB)
continue;
if (! CSRUsed[SUCC].contains(prop)) {
CSRUsed[SUCC] |= prop;
addedUses = true;
blks.push_back(SUCC);
DEBUG(if (ShrinkWrapDebugging >= Iterations)
dbgs() << getBasicBlockName(MBB)
<< "(" << stringifyCSRegSet(prop) << ")->"
<< "successor " << getBasicBlockName(SUCC) << "\n");
}
}
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock* PRED = *PI;
if (PRED == MBB)
continue;
if (! CSRUsed[PRED].contains(prop)) {
CSRUsed[PRED] |= prop;
addedUses = true;
blks.push_back(PRED);
DEBUG(if (ShrinkWrapDebugging >= Iterations)
dbgs() << getBasicBlockName(MBB)
<< "(" << stringifyCSRegSet(prop) << ")->"
<< "predecessor " << getBasicBlockName(PRED) << "\n");
}
}
return addedUses;
}
bool PEI::addUsesForTopLevelLoops(SmallVector<MachineBasicBlock*, 4>& blks) {
bool addedUses = false;
for (DenseMap<MachineBasicBlock*, MachineLoop*>::iterator
I = TLLoops.begin(), E = TLLoops.end(); I != E; ++I) {
MachineBasicBlock* MBB = I->first;
MachineLoop* LP = I->second;
MachineBasicBlock* HDR = LP->getHeader();
SmallVector<MachineBasicBlock*, 4> exitBlocks;
CSRegSet loopSpills;
loopSpills = CSRSave[MBB];
if (CSRSave[MBB].empty()) {
loopSpills = CSRUsed[HDR];
assert(!loopSpills.empty() && "No CSRs used in loop?");
} else if (CSRRestore[MBB].contains(CSRSave[MBB]))
continue;
LP->getExitBlocks(exitBlocks);
assert(exitBlocks.size() > 0 && "Loop has no top level exit blocks?");
for (unsigned i = 0, e = exitBlocks.size(); i != e; ++i) {
MachineBasicBlock* EXB = exitBlocks[i];
if (! CSRUsed[EXB].contains(loopSpills)) {
CSRUsed[EXB] |= loopSpills;
addedUses = true;
DEBUG(if (ShrinkWrapDebugging >= Iterations)
dbgs() << "LOOP " << getBasicBlockName(MBB)
<< "(" << stringifyCSRegSet(loopSpills) << ")->"
<< getBasicBlockName(EXB) << "\n");
if (EXB->succ_size() > 1 || EXB->pred_size() > 1)
blks.push_back(EXB);
}
}
}
return addedUses;
}
bool PEI::calcSpillPlacements(MachineBasicBlock* MBB,
SmallVector<MachineBasicBlock*, 4> &blks,
CSRegBlockMap &prevSpills) {
bool placedSpills = false;
CSRegSet anticInPreds;
SmallVector<MachineBasicBlock*, 4> predecessors;
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock* PRED = *PI;
if (PRED != MBB)
predecessors.push_back(PRED);
}
unsigned i = 0, e = predecessors.size();
if (i != e) {
MachineBasicBlock* PRED = predecessors[i];
anticInPreds = UsedCSRegs - AnticIn[PRED];
for (++i; i != e; ++i) {
PRED = predecessors[i];
anticInPreds &= (UsedCSRegs - AnticIn[PRED]);
}
} else {
anticInPreds = UsedCSRegs;
}
CSRSave[MBB] |= (AnticIn[MBB] - AvailIn[MBB]) & anticInPreds;
if (! CSRSave[MBB].empty()) {
if (MBB == EntryBlock) {
for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri)
CSRRestore[ReturnBlocks[ri]] |= CSRSave[MBB];
} else {
if (CSRSave[EntryBlock].intersects(CSRSave[MBB])) {
CSRSave[MBB] = CSRSave[MBB] - CSRSave[EntryBlock];
}
}
}
placedSpills = (CSRSave[MBB] != prevSpills[MBB]);
prevSpills[MBB] = CSRSave[MBB];
if (placedSpills)
blks.push_back(MBB);
DEBUG(if (! CSRSave[MBB].empty() && ShrinkWrapDebugging >= Iterations)
dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRSave[MBB]) << "\n");
return placedSpills;
}
bool PEI::calcRestorePlacements(MachineBasicBlock* MBB,
SmallVector<MachineBasicBlock*, 4> &blks,
CSRegBlockMap &prevRestores) {
bool placedRestores = false;
CSRegSet availOutSucc;
SmallVector<MachineBasicBlock*, 4> successors;
for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
SE = MBB->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
if (SUCC != MBB)
successors.push_back(SUCC);
}
unsigned i = 0, e = successors.size();
if (i != e) {
MachineBasicBlock* SUCC = successors[i];
availOutSucc = UsedCSRegs - AvailOut[SUCC];
for (++i; i != e; ++i) {
SUCC = successors[i];
availOutSucc &= (UsedCSRegs - AvailOut[SUCC]);
}
} else {
if (! CSRUsed[MBB].empty() || ! AvailOut[MBB].empty()) {
availOutSucc = UsedCSRegs;
}
}
CSRRestore[MBB] |= (AvailOut[MBB] - AnticOut[MBB]) & availOutSucc;
if (MBB->succ_size() && ! CSRRestore[MBB].empty()) {
if (! CSRSave[EntryBlock].empty())
CSRRestore[MBB] = CSRRestore[MBB] - CSRSave[EntryBlock];
}
placedRestores = (CSRRestore[MBB] != prevRestores[MBB]);
prevRestores[MBB] = CSRRestore[MBB];
if (placedRestores)
blks.push_back(MBB);
DEBUG(if (! CSRRestore[MBB].empty() && ShrinkWrapDebugging >= Iterations)
dbgs() << "RESTORE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRRestore[MBB]) << "\n");
return placedRestores;
}
void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
CSRegBlockMap prevCSRSave;
CSRegBlockMap prevCSRRestore;
SmallVector<MachineBasicBlock*, 4> cvBlocks, ncvBlocks;
bool changed = true;
unsigned iterations = 0;
while (changed) {
changed = false;
++iterations;
DEBUG(if (ShrinkWrapDebugging >= Iterations)
dbgs() << "iter " << iterations
<< " --------------------------------------------------\n");
bool SRChanged = false;
for (MachineFunction::iterator MBBI = Fn.begin(), MBBE = Fn.end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
SRChanged |= calcSpillPlacements(MBB, cvBlocks, prevCSRSave);
SRChanged |= calcRestorePlacements(MBB, cvBlocks, prevCSRRestore);
}
changed |= addUsesForTopLevelLoops(cvBlocks);
if (changed || SRChanged) {
while (! cvBlocks.empty()) {
MachineBasicBlock* MBB = cvBlocks.pop_back_val();
changed |= addUsesForMEMERegion(MBB, ncvBlocks);
}
if (! ncvBlocks.empty()) {
cvBlocks = ncvBlocks;
ncvBlocks.clear();
}
}
if (changed) {
calculateAnticAvail(Fn);
CSRSave.clear();
CSRRestore.clear();
}
}
CSRegSet notSpilledInEntryBlock = (UsedCSRegs - CSRSave[EntryBlock]);
unsigned numSRReducedThisFunc = notSpilledInEntryBlock.count();
numSRReduced += numSRReducedThisFunc;
DEBUG(if (ShrinkWrapDebugging >= BasicInfo) {
dbgs() << "-----------------------------------------------------------\n";
dbgs() << "total iterations = " << iterations << " ( "
<< Fn.getName()
<< " " << numSRReducedThisFunc
<< " " << Fn.size()
<< " )\n";
dbgs() << "-----------------------------------------------------------\n";
dumpSRSets();
dbgs() << "-----------------------------------------------------------\n";
if (numSRReducedThisFunc)
verifySpillRestorePlacement();
});
}
#ifndef NDEBUG
void PEI::findFastExitPath() {
if (! EntryBlock)
return;
for (MachineBasicBlock::succ_iterator SI = EntryBlock->succ_begin(),
SE = EntryBlock->succ_end(); SI != SE; ++SI) {
MachineBasicBlock* SUCC = *SI;
HasFastExitPath = true;
if (isReturnBlock(SUCC)) {
if (ShrinkWrapDebugging >= BasicInfo)
dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
<< "->" << getBasicBlockName(SUCC) << "\n";
break;
}
std::string exitPath = getBasicBlockName(SUCC);
for (df_iterator<MachineBasicBlock*> BI = df_begin(SUCC),
BE = df_end(SUCC); BI != BE; ++BI) {
MachineBasicBlock* SBB = *BI;
if (SBB->succ_size() > 1) {
HasFastExitPath = false;
break;
}
exitPath += "->" + getBasicBlockName(SBB);
}
if (HasFastExitPath) {
if (ShrinkWrapDebugging >= BasicInfo)
dbgs() << "Fast exit path: " << getBasicBlockName(EntryBlock)
<< "->" << exitPath << "\n";
break;
}
}
}
void PEI::verifySpillRestorePlacement() {
unsigned numReturnBlocks = 0;
for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
if (isReturnBlock(MBB) || MBB->succ_size() == 0)
++numReturnBlocks;
}
for (CSRegBlockMap::iterator BI = CSRSave.begin(),
BE = CSRSave.end(); BI != BE; ++BI) {
MachineBasicBlock* MBB = BI->first;
CSRegSet spilled = BI->second;
CSRegSet restored;
if (spilled.empty())
continue;
DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(spilled)
<< " RESTORE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRRestore[MBB]) << "\n");
if (CSRRestore[MBB].intersects(spilled)) {
restored |= (CSRRestore[MBB] & spilled);
}
for (df_iterator<MachineBasicBlock*> BI = df_begin(MBB),
BE = df_end(MBB); BI != BE; ++BI) {
MachineBasicBlock* SBB = *BI;
if (SBB == MBB)
continue;
if (CSRSave[SBB].intersects(spilled) &&
!restored.contains(CSRSave[SBB] & spilled))
break;
if (CSRRestore[SBB].intersects(spilled))
restored |= (CSRRestore[SBB] & spilled);
if (isReturnBlock(SBB) || SBB->succ_size() == 0) {
if (restored != spilled) {
CSRegSet notRestored = (spilled - restored);
DEBUG(dbgs() << MF->getName() << ": "
<< stringifyCSRegSet(notRestored)
<< " spilled at " << getBasicBlockName(MBB)
<< " are never restored on path to return "
<< getBasicBlockName(SBB) << "\n");
}
restored.clear();
}
}
}
for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
BE = CSRRestore.end(); BI != BE; ++BI) {
MachineBasicBlock* MBB = BI->first;
CSRegSet restored = BI->second;
CSRegSet spilled;
if (restored.empty())
continue;
DEBUG(dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRSave[MBB])
<< " RESTORE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(restored) << "\n");
if (CSRSave[MBB].intersects(restored)) {
spilled |= (CSRSave[MBB] & restored);
}
for (idf_iterator<MachineBasicBlock*> BI = idf_begin(MBB),
BE = idf_end(MBB); BI != BE; ++BI) {
MachineBasicBlock* PBB = *BI;
if (PBB == MBB)
continue;
if (CSRRestore[PBB].intersects(restored) &&
!spilled.contains(CSRRestore[PBB] & restored))
break;
if (CSRSave[PBB].intersects(restored))
spilled |= (CSRSave[PBB] & restored);
}
if (spilled != restored) {
CSRegSet notSpilled = (restored - spilled);
DEBUG(dbgs() << MF->getName() << ": "
<< stringifyCSRegSet(notSpilled)
<< " restored at " << getBasicBlockName(MBB)
<< " are never spilled\n");
}
}
}
std::string PEI::getBasicBlockName(const MachineBasicBlock* MBB) {
if (!MBB)
return "";
if (MBB->getBasicBlock())
return MBB->getBasicBlock()->getName().str();
std::ostringstream name;
name << "_MBB_" << MBB->getNumber();
return name.str();
}
std::string PEI::stringifyCSRegSet(const CSRegSet& s) {
const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
const std::vector<CalleeSavedInfo> CSI =
MF->getFrameInfo()->getCalleeSavedInfo();
std::ostringstream srep;
if (CSI.size() == 0) {
srep << "[]";
return srep.str();
}
srep << "[";
CSRegSet::iterator I = s.begin(), E = s.end();
if (I != E) {
unsigned reg = CSI[*I].getReg();
srep << TRI->getName(reg);
for (++I; I != E; ++I) {
reg = CSI[*I].getReg();
srep << ",";
srep << TRI->getName(reg);
}
}
srep << "]";
return srep.str();
}
void PEI::dumpSet(const CSRegSet& s) {
DEBUG(dbgs() << stringifyCSRegSet(s) << "\n");
}
void PEI::dumpUsed(MachineBasicBlock* MBB) {
DEBUG({
if (MBB)
dbgs() << "CSRUsed[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRUsed[MBB]) << "\n";
});
}
void PEI::dumpAllUsed() {
for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
dumpUsed(MBB);
}
}
void PEI::dumpSets(MachineBasicBlock* MBB) {
DEBUG({
if (MBB)
dbgs() << getBasicBlockName(MBB) << " | "
<< stringifyCSRegSet(CSRUsed[MBB]) << " | "
<< stringifyCSRegSet(AnticIn[MBB]) << " | "
<< stringifyCSRegSet(AnticOut[MBB]) << " | "
<< stringifyCSRegSet(AvailIn[MBB]) << " | "
<< stringifyCSRegSet(AvailOut[MBB]) << "\n";
});
}
void PEI::dumpSets1(MachineBasicBlock* MBB) {
DEBUG({
if (MBB)
dbgs() << getBasicBlockName(MBB) << " | "
<< stringifyCSRegSet(CSRUsed[MBB]) << " | "
<< stringifyCSRegSet(AnticIn[MBB]) << " | "
<< stringifyCSRegSet(AnticOut[MBB]) << " | "
<< stringifyCSRegSet(AvailIn[MBB]) << " | "
<< stringifyCSRegSet(AvailOut[MBB]) << " | "
<< stringifyCSRegSet(CSRSave[MBB]) << " | "
<< stringifyCSRegSet(CSRRestore[MBB]) << "\n";
});
}
void PEI::dumpAllSets() {
for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
MBBI != MBBE; ++MBBI) {
MachineBasicBlock* MBB = MBBI;
dumpSets1(MBB);
}
}
void PEI::dumpSRSets() {
DEBUG({
for (MachineFunction::iterator MBB = MF->begin(), E = MF->end();
MBB != E; ++MBB) {
if (!CSRSave[MBB].empty()) {
dbgs() << "SAVE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRSave[MBB]);
if (CSRRestore[MBB].empty())
dbgs() << '\n';
}
if (!CSRRestore[MBB].empty() && !CSRSave[MBB].empty())
dbgs() << " "
<< "RESTORE[" << getBasicBlockName(MBB) << "] = "
<< stringifyCSRegSet(CSRRestore[MBB]) << "\n";
}
});
}
#endif