//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "splitter"
+#define DEBUG_TYPE "regalloc"
#include "SplitKit.h"
#include "LiveRangeEdit.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
AllowSplit("spiller-splits-edges",
cl::desc("Allow critical edge splitting during spilling"));
+//===----------------------------------------------------------------------===//
+// Edge Bundles
+//===----------------------------------------------------------------------===//
+
+/// compute - Compute the edge bundles for MF. Bundles depend only on the CFG.
+void EdgeBundles::compute(const MachineFunction *mf) {
+ MF = mf;
+ EC.clear();
+ EC.grow(2 * MF->size());
+
+ for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E;
+ ++I) {
+ const MachineBasicBlock &MBB = *I;
+ unsigned OutE = 2 * MBB.getNumber() + 1;
+ // Join the outgoing bundle with the ingoing bundles of all successors.
+ for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
+ SE = MBB.succ_end(); SI != SE; ++SI)
+ EC.join(OutE, 2 * (*SI)->getNumber());
+ }
+ EC.compress();
+}
+
+/// view - Visualize the annotated bipartite CFG with Graphviz.
+void EdgeBundles::view() const {
+ ViewGraph(*this, "EdgeBundles");
+}
+
+/// Specialize WriteGraph, the standard implementation won't work.
+raw_ostream &llvm::WriteGraph(raw_ostream &O, const EdgeBundles &G,
+ bool ShortNames,
+ const std::string &Title) {
+ const MachineFunction *MF = G.getMachineFunction();
+
+ O << "digraph {\n";
+ for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
+ I != E; ++I) {
+ unsigned BB = I->getNumber();
+ O << "\t\"BB#" << BB << "\" [ shape=box ]\n"
+ << '\t' << G.getBundle(BB, false) << " -> \"BB#" << BB << "\"\n"
+ << "\t\"BB#" << BB << "\" -> " << G.getBundle(BB, true) << '\n';
+ }
+ O << "}\n";
+ return O;
+}
+
+
//===----------------------------------------------------------------------===//
// Split Analysis
//===----------------------------------------------------------------------===//
analyzeUses();
}
-const MachineLoop *SplitAnalysis::getBestSplitLoop() {
- assert(curli_ && "Call analyze() before getBestSplitLoop");
+void SplitAnalysis::getSplitLoops(LoopPtrSet &Loops) {
+ assert(curli_ && "Call analyze() before getSplitLoops");
if (usingLoops_.empty())
- return 0;
+ return;
- LoopPtrSet Loops;
LoopBlocks Blocks;
BlockPtrSet CriticalExits;
// FIXME: We could split a live range with multiple uses in a peripheral
// block and still make progress. However, it is possible that splitting
// another live range will insert copies into a peripheral block, and
- // there is a small chance we can enter an infinity loop, inserting copies
+ // there is a small chance we can enter an infinite loop, inserting copies
// forever.
// For safety, stick to splitting live ranges with uses outside the
// periphery.
- DEBUG(dbgs() << ": multiple peripheral uses\n");
+ DEBUG(dbgs() << ": multiple peripheral uses");
break;
case ContainedInLoop:
DEBUG(dbgs() << ": fully contained\n");
Loops.insert(Loop);
}
- DEBUG(dbgs() << " getBestSplitLoop found " << Loops.size()
+ DEBUG(dbgs() << " getSplitLoops found " << Loops.size()
<< " candidate loops.\n");
+}
+const MachineLoop *SplitAnalysis::getBestSplitLoop() {
+ LoopPtrSet Loops;
+ getSplitLoops(Loops);
if (Loops.empty())
return 0;
return Best;
}
+/// isBypassLoop - Return true if curli is live through Loop and has no uses
+/// inside the loop. Bypass loops are candidates for splitting because it can
+/// prevent interference inside the loop.
+bool SplitAnalysis::isBypassLoop(const MachineLoop *Loop) {
+ // If curli is live into the loop header and there are no uses in the loop, it
+ // must be live in the entire loop and live on at least one exiting edge.
+ return !usingLoops_.count(Loop) &&
+ lis_.isLiveInToMBB(*curli_, Loop->getHeader());
+}
+
+/// getBypassLoops - Get all the maximal bypass loops. These are the bypass
+/// loops whose parent is not a bypass loop.
+void SplitAnalysis::getBypassLoops(LoopPtrSet &BypassLoops) {
+ SmallVector<MachineLoop*, 8> Todo(loops_.begin(), loops_.end());
+ while (!Todo.empty()) {
+ MachineLoop *Loop = Todo.pop_back_val();
+ if (!usingLoops_.count(Loop)) {
+ // This is either a bypass loop or completely irrelevant.
+ if (lis_.isLiveInToMBB(*curli_, Loop->getHeader()))
+ BypassLoops.insert(Loop);
+ // Either way, skip the child loops.
+ continue;
+ }
+
+ // The child loops may be bypass loops.
+ Todo.append(Loop->begin(), Loop->end());
+ }
+}
+
+
//===----------------------------------------------------------------------===//
// LiveIntervalMap
//===----------------------------------------------------------------------===//
addSimpleRange(I->start, std::min(End, I->end), I->valno);
}
-VNInfo *LiveIntervalMap::defByCopyFrom(unsigned Reg,
- const VNInfo *ParentVNI,
- MachineBasicBlock &MBB,
- MachineBasicBlock::iterator I) {
- const TargetInstrDesc &TID = MBB.getParent()->getTarget().getInstrInfo()->
- get(TargetOpcode::COPY);
- MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), TID, li_->reg).addReg(Reg);
- SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
- VNInfo *VNI = defValue(ParentVNI, DefIdx);
- VNI->setCopy(MI);
- li_->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), VNI));
- return VNI;
-}
//===----------------------------------------------------------------------===//
// Split Editor
: sa_(sa), lis_(lis), vrm_(vrm),
mri_(vrm.getMachineFunction().getRegInfo()),
tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()),
+ tri_(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
edit_(edit),
dupli_(lis_, mdt, edit.getParent()),
openli_(lis_, mdt, edit.getParent())
{
+ // We don't need an AliasAnalysis since we will only be performing
+ // cheap-as-a-copy remats anyway.
+ edit_.anyRematerializable(lis_, tii_, 0);
}
bool SplitEditor::intervalsLiveAt(SlotIndex Idx) const {
return false;
}
+VNInfo *SplitEditor::defFromParent(LiveIntervalMap &Reg,
+ VNInfo *ParentVNI,
+ SlotIndex UseIdx,
+ MachineBasicBlock &MBB,
+ MachineBasicBlock::iterator I) {
+ VNInfo *VNI = 0;
+ MachineInstr *CopyMI = 0;
+ SlotIndex Def;
+
+ // Attempt cheap-as-a-copy rematerialization.
+ LiveRangeEdit::Remat RM(ParentVNI);
+ if (edit_.canRematerializeAt(RM, UseIdx, true, lis_)) {
+ Def = edit_.rematerializeAt(MBB, I, Reg.getLI()->reg, RM,
+ lis_, tii_, tri_);
+ } else {
+ // Can't remat, just insert a copy from parent.
+ CopyMI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY),
+ Reg.getLI()->reg).addReg(edit_.getReg());
+ Def = lis_.InsertMachineInstrInMaps(CopyMI).getDefIndex();
+ }
+
+ // Define the value in Reg.
+ VNI = Reg.defValue(ParentVNI, Def);
+ VNI->setCopy(CopyMI);
+
+ // Add minimal liveness for the new value.
+ if (UseIdx < Def)
+ UseIdx = Def;
+ Reg.getLI()->addRange(LiveRange(Def, UseIdx.getNextSlot(), VNI));
+ return VNI;
+}
+
/// Create a new virtual register and live interval.
void SplitEditor::openIntv() {
assert(!openli_.getLI() && "Previous LI not closed before openIntv");
-
if (!dupli_.getLI())
dupli_.reset(&edit_.create(mri_, lis_, vrm_));
/// not live before Idx, a COPY is not inserted.
void SplitEditor::enterIntvBefore(SlotIndex Idx) {
assert(openli_.getLI() && "openIntv not called before enterIntvBefore");
+ Idx = Idx.getUseIndex();
DEBUG(dbgs() << " enterIntvBefore " << Idx);
- VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(Idx.getUseIndex());
+ VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(Idx);
if (!ParentVNI) {
DEBUG(dbgs() << ": not live\n");
return;
truncatedValues.insert(ParentVNI);
MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
assert(MI && "enterIntvBefore called with invalid index");
- VNInfo *VNI = openli_.defByCopyFrom(edit_.getReg(), ParentVNI,
- *MI->getParent(), MI);
- openli_.getLI()->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI));
+
+ defFromParent(openli_, ParentVNI, Idx, *MI->getParent(), MI);
+
DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
}
/// enterIntvAtEnd - Enter openli at the end of MBB.
void SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
assert(openli_.getLI() && "openIntv not called before enterIntvAtEnd");
- SlotIndex End = lis_.getMBBEndIdx(&MBB);
+ SlotIndex End = lis_.getMBBEndIdx(&MBB).getPrevSlot();
DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << End);
- VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(End.getPrevSlot());
+ VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(End);
if (!ParentVNI) {
DEBUG(dbgs() << ": not live\n");
return;
}
DEBUG(dbgs() << ": valno " << ParentVNI->id);
truncatedValues.insert(ParentVNI);
- VNInfo *VNI = openli_.defByCopyFrom(edit_.getReg(), ParentVNI,
- MBB, MBB.getFirstTerminator());
- // Make sure openli is live out of MBB.
- openli_.getLI()->addRange(LiveRange(VNI->def, End, VNI));
+ defFromParent(openli_, ParentVNI, End, MBB, MBB.getFirstTerminator());
DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
}
DEBUG(dbgs() << " leaveIntvAfter " << Idx);
// The interval must be live beyond the instruction at Idx.
- VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(Idx.getBoundaryIndex());
+ Idx = Idx.getBoundaryIndex();
+ VNInfo *ParentVNI = edit_.getParent().getVNInfoAt(Idx);
if (!ParentVNI) {
DEBUG(dbgs() << ": not live\n");
return;
DEBUG(dbgs() << ": valno " << ParentVNI->id);
MachineBasicBlock::iterator MII = lis_.getInstructionFromIndex(Idx);
- MachineBasicBlock *MBB = MII->getParent();
- VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI, *MBB,
- llvm::next(MII));
+ VNInfo *VNI = defFromParent(dupli_, ParentVNI, Idx,
+ *MII->getParent(), llvm::next(MII));
+
+ // Make sure that openli is properly extended from Idx to the new copy.
+ // FIXME: This shouldn't be necessary for remats.
+ openli_.addSimpleRange(Idx, VNI->def, ParentVNI);
- // Finally we must make sure that openli is properly extended from Idx to the
- // new copy.
- openli_.addSimpleRange(Idx.getBoundaryIndex(), VNI->def, ParentVNI);
DEBUG(dbgs() << ": " << *openli_.getLI() << '\n');
}
return;
}
- // We are going to insert a back copy, so we must have a dupli_.
- VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI,
- MBB, MBB.SkipPHIsAndLabels(MBB.begin()));
+ VNInfo *VNI = defFromParent(dupli_, ParentVNI, Start, MBB,
+ MBB.SkipPHIsAndLabels(MBB.begin()));
// Finally we must make sure that openli is properly extended from Start to
// the new copy.
for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(reg),
RE = mri_.reg_end(); RI != RE;) {
MachineOperand &MO = RI.getOperand();
+ unsigned OpNum = RI.getOperandNo();
MachineInstr *MI = MO.getParent();
++RI;
if (MI->isDebugValue()) {
DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'<< Idx);
assert(LI && "No register was live at use");
MO.setReg(LI->reg);
+ if (MO.isUse() && !MI->isRegTiedToDefOperand(OpNum))
+ MO.setIsKill(LI->killedAt(Idx.getDefIndex()));
DEBUG(dbgs() << '\t' << *MI);
}
}
// Create new live interval for the loop.
openIntv();
- // Insert copies in the predecessors.
- for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
- E = Blocks.Preds.end(); I != E; ++I) {
- MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
- enterIntvAtEnd(MBB);
+ // Insert copies in the predecessors if live-in to the header.
+ if (lis_.isLiveInToMBB(edit_.getParent(), Loop->getHeader())) {
+ for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
+ E = Blocks.Preds.end(); I != E; ++I) {
+ MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
+ enterIntvAtEnd(MBB);
+ }
}
// Switch all loop blocks.
projects / oota-llvm.git / blobdiff