//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "spiller"
+#define DEBUG_TYPE "regalloc"
#include "Spiller.h"
#include "LiveRangeEdit.h"
#include "SplitKit.h"
#include "VirtRegMap.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
+static cl::opt<bool>
+VerifySpills("verify-spills", cl::desc("Verify after each spill/split"));
+
+static cl::opt<bool>
+ExtraSpillerSplits("extra-spiller-splits",
+ cl::desc("Enable additional splitting during splitting"));
+
namespace {
class InlineSpiller : public Spiller {
MachineFunctionPass &pass_;
MachineFunction &mf_;
LiveIntervals &lis_;
+ LiveStacks &lss_;
+ MachineDominatorTree &mdt_;
MachineLoopInfo &loops_;
+ AliasAnalysis *aa_;
VirtRegMap &vrm_;
MachineFrameInfo &mfi_;
MachineRegisterInfo &mri_;
const TargetRegisterClass *rc_;
int stackSlot_;
- // Values of the current interval that can potentially remat.
- SmallPtrSet<VNInfo*, 8> reMattable_;
-
- // Values in reMattable_ that failed to remat at some point.
+ // Values that failed to remat at some point.
SmallPtrSet<VNInfo*, 8> usedValues_;
~InlineSpiller() {}
: pass_(pass),
mf_(mf),
lis_(pass.getAnalysis<LiveIntervals>()),
+ lss_(pass.getAnalysis<LiveStacks>()),
+ mdt_(pass.getAnalysis<MachineDominatorTree>()),
loops_(pass.getAnalysis<MachineLoopInfo>()),
+ aa_(&pass.getAnalysis<AliasAnalysis>()),
vrm_(vrm),
mfi_(*mf.getFrameInfo()),
mri_(mf.getRegInfo()),
void spill(LiveInterval *li,
SmallVectorImpl<LiveInterval*> &newIntervals,
- SmallVectorImpl<LiveInterval*> &spillIs);
+ const SmallVectorImpl<LiveInterval*> &spillIs);
void spill(LiveRangeEdit &);
Spiller *createInlineSpiller(MachineFunctionPass &pass,
MachineFunction &mf,
VirtRegMap &vrm) {
+ if (VerifySpills)
+ mf.verify(&pass);
return new InlineSpiller(pass, mf, vrm);
}
}
splitAnalysis_.analyze(&edit_->getParent());
// Try splitting around loops.
- if (const MachineLoop *loop = splitAnalysis_.getBestSplitLoop()) {
- SplitEditor(splitAnalysis_, lis_, vrm_, *edit_)
- .splitAroundLoop(loop);
- return true;
+ if (ExtraSpillerSplits) {
+ const MachineLoop *loop = splitAnalysis_.getBestSplitLoop();
+ if (loop) {
+ SplitEditor(splitAnalysis_, lis_, vrm_, mdt_, *edit_)
+ .splitAroundLoop(loop);
+ return true;
+ }
}
// Try splitting into single block intervals.
SplitAnalysis::BlockPtrSet blocks;
if (splitAnalysis_.getMultiUseBlocks(blocks)) {
- SplitEditor(splitAnalysis_, lis_, vrm_, *edit_)
+ SplitEditor(splitAnalysis_, lis_, vrm_, mdt_, *edit_)
.splitSingleBlocks(blocks);
return true;
}
// Try splitting inside a basic block.
- if (const MachineBasicBlock *MBB = splitAnalysis_.getBlockForInsideSplit()) {
- SplitEditor(splitAnalysis_, lis_, vrm_, *edit_)
- .splitInsideBlock(MBB);
- return true;
+ if (ExtraSpillerSplits) {
+ const MachineBasicBlock *MBB = splitAnalysis_.getBlockForInsideSplit();
+ if (MBB){
+ SplitEditor(splitAnalysis_, lis_, vrm_, mdt_, *edit_)
+ .splitInsideBlock(MBB);
+ return true;
+ }
}
return false;
bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex();
VNInfo *OrigVNI = edit_->getParent().getVNInfoAt(UseIdx);
+
if (!OrigVNI) {
DEBUG(dbgs() << "\tadding <undef> flags: ");
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
DEBUG(dbgs() << UseIdx << '\t' << *MI);
return true;
}
- if (!reMattable_.count(OrigVNI)) {
- DEBUG(dbgs() << "\tusing non-remat valno " << OrigVNI->id << ": "
- << UseIdx << '\t' << *MI);
- return false;
- }
- MachineInstr *OrigMI = lis_.getInstructionFromIndex(OrigVNI->def);
- if (!edit_->allUsesAvailableAt(OrigMI, OrigVNI->def, UseIdx, lis_)) {
+
+ LiveRangeEdit::Remat RM(OrigVNI);
+ if (!edit_->canRematerializeAt(RM, UseIdx, false, lis_)) {
usedValues_.insert(OrigVNI);
DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
return false;
}
- // If the instruction also writes edit_->getReg(), it had better not require the same
- // register for uses and defs.
+ // If the instruction also writes edit_->getReg(), it had better not require
+ // the same register for uses and defs.
bool Reads, Writes;
SmallVector<unsigned, 8> Ops;
tie(Reads, Writes) = MI->readsWritesVirtualRegister(edit_->getReg(), &Ops);
NewLI.markNotSpillable();
// Finally we can rematerialize OrigMI before MI.
- MachineBasicBlock &MBB = *MI->getParent();
- tii_.reMaterialize(MBB, MI, NewLI.reg, 0, OrigMI, tri_);
- MachineBasicBlock::iterator RematMI = MI;
- SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(--RematMI).getDefIndex();
- DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' << *RematMI);
+ SlotIndex DefIdx = edit_->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM,
+ lis_, tii_, tri_);
+ DEBUG(dbgs() << "\tremat: " << DefIdx << '\n');
// Replace operands
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
/// and trim the live ranges after.
void InlineSpiller::reMaterializeAll() {
// Do a quick scan of the interval values to find if any are remattable.
- reMattable_.clear();
- usedValues_.clear();
- for (LiveInterval::const_vni_iterator I = edit_->getParent().vni_begin(),
- E = edit_->getParent().vni_end(); I != E; ++I) {
- VNInfo *VNI = *I;
- if (VNI->isUnused())
- continue;
- MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def);
- if (!DefMI || !tii_.isTriviallyReMaterializable(DefMI))
- continue;
- reMattable_.insert(VNI);
- }
-
- // Often, no defs are remattable.
- if (reMattable_.empty())
+ if (!edit_->anyRematerializable(lis_, tii_, aa_))
return;
+ usedValues_.clear();
+
// Try to remat before all uses of edit_->getReg().
bool anyRemat = false;
for (MachineRegisterInfo::use_nodbg_iterator
// Remove any values that were completely rematted.
bool anyRemoved = false;
- for (SmallPtrSet<VNInfo*, 8>::iterator I = reMattable_.begin(),
- E = reMattable_.end(); I != E; ++I) {
+ for (LiveInterval::vni_iterator I = edit_->getParent().vni_begin(),
+ E = edit_->getParent().vni_end(); I != E; ++I) {
VNInfo *VNI = *I;
- if (VNI->hasPHIKill() || usedValues_.count(VNI))
+ if (VNI->hasPHIKill() || !edit_->didRematerialize(VNI) ||
+ usedValues_.count(VNI))
continue;
MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def);
DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI);
void InlineSpiller::insertSpill(LiveInterval &NewLI,
MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();
+
+ // Get the defined value. It could be an early clobber so keep the def index.
SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
+ VNInfo *VNI = edit_->getParent().getVNInfoAt(Idx);
+ assert(VNI && VNI->def.getDefIndex() == Idx && "Inconsistent VNInfo");
+ Idx = VNI->def;
+
tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_);
--MI; // Point to store instruction.
SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
void InlineSpiller::spill(LiveInterval *li,
SmallVectorImpl<LiveInterval*> &newIntervals,
- SmallVectorImpl<LiveInterval*> &spillIs) {
+ const SmallVectorImpl<LiveInterval*> &spillIs) {
LiveRangeEdit edit(*li, newIntervals, spillIs);
spill(edit);
+ if (VerifySpills)
+ mf_.verify(&pass_);
}
void InlineSpiller::spill(LiveRangeEdit &edit) {
edit_ = &edit;
- DEBUG(dbgs() << "Inline spilling " << edit.getParent() << "\n");
+ assert(!edit.getParent().isStackSlot() && "Trying to spill a stack slot.");
+ DEBUG(dbgs() << "Inline spilling "
+ << mri_.getRegClass(edit.getReg())->getName()
+ << ':' << edit.getParent() << "\n");
assert(edit.getParent().isSpillable() &&
"Attempting to spill already spilled value.");
- assert(!edit.getParent().isStackSlot() && "Trying to spill a stack slot.");
if (split())
return;
return;
rc_ = mri_.getRegClass(edit.getReg());
- stackSlot_ = vrm_.getStackSlot(edit.getReg());
- if (stackSlot_ == VirtRegMap::NO_STACK_SLOT)
- stackSlot_ = vrm_.assignVirt2StackSlot(edit.getReg());
+ stackSlot_ = vrm_.assignVirt2StackSlot(edit_->getReg());
+
+ // Update LiveStacks now that we are committed to spilling.
+ LiveInterval &stacklvr = lss_.getOrCreateInterval(stackSlot_, rc_);
+ assert(stacklvr.empty() && "Just created stack slot not empty");
+ stacklvr.getNextValue(SlotIndex(), 0, lss_.getVNInfoAllocator());
+ stacklvr.MergeRangesInAsValue(edit_->getParent(), stacklvr.getValNumInfo(0));
// Iterate over instructions using register.
for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(edit.getReg());