#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
using namespace llvm;
-static cl::opt<bool>
-AllowSplit("spiller-splits-edges",
- cl::desc("Allow critical edge splitting during spilling"));
-
STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple, "Number of splits that were simple");
void SplitAnalysis::clear() {
UseSlots.clear();
- UsingInstrs.clear();
- UsingBlocks.clear();
- LiveBlocks.clear();
+ UseBlocks.clear();
+ ThroughBlocks.clear();
CurLI = 0;
}
// If CurLI is live into a landing pad successor, move the last split point
// back to the call that may throw.
- if (LPad && LSP.second.isValid() && !LIS.isLiveInToMBB(*CurLI, LPad))
+ if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad))
return LSP.second;
else
return LSP.first;
/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
void SplitAnalysis::analyzeUses() {
+ assert(UseSlots.empty() && "Call clear first");
+
+ // First get all the defs from the interval values. This provides the correct
+ // slots for early clobbers.
+ for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(),
+ E = CurLI->vni_end(); I != E; ++I)
+ if (!(*I)->isPHIDef() && !(*I)->isUnused())
+ UseSlots.push_back((*I)->def);
+
+ // Get use slots form the use-def chain.
const MachineRegisterInfo &MRI = MF.getRegInfo();
- for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg),
- E = MRI.reg_end(); I != E; ++I) {
- MachineOperand &MO = I.getOperand();
- if (MO.isUse() && MO.isUndef())
- continue;
- MachineInstr *MI = MO.getParent();
- if (MI->isDebugValue() || !UsingInstrs.insert(MI))
- continue;
- UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex());
- MachineBasicBlock *MBB = MI->getParent();
- UsingBlocks[MBB]++;
- }
+ for (MachineRegisterInfo::use_nodbg_iterator
+ I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
+ ++I)
+ if (!I.getOperand().isUndef())
+ UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex());
+
array_pod_sort(UseSlots.begin(), UseSlots.end());
+ // Remove duplicates, keeping the smaller slot for each instruction.
+ // That is what we want for early clobbers.
+ UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
+ SlotIndex::isSameInstr),
+ UseSlots.end());
+
// Compute per-live block info.
if (!calcLiveBlockInfo()) {
// FIXME: calcLiveBlockInfo found inconsistencies in the live range.
DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
const_cast<LiveIntervals&>(LIS)
.shrinkToUses(const_cast<LiveInterval*>(CurLI));
- LiveBlocks.clear();
+ UseBlocks.clear();
+ ThroughBlocks.clear();
bool fixed = calcLiveBlockInfo();
(void)fixed;
assert(fixed && "Couldn't fix broken live interval");
}
DEBUG(dbgs() << "Analyze counted "
- << UsingInstrs.size() << " instrs, "
- << UsingBlocks.size() << " blocks, "
- << LiveBlocks.size() << " spanned.\n");
+ << UseSlots.size() << " instrs in "
+ << UseBlocks.size() << " blocks, through "
+ << NumThroughBlocks << " blocks.\n");
}
/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
bool SplitAnalysis::calcLiveBlockInfo() {
+ ThroughBlocks.resize(MF.getNumBlockIDs());
+ NumThroughBlocks = 0;
if (CurLI->empty())
return true;
BI.Def = LVI->start;
// Find the first and last uses in the block.
- BI.Uses = hasUses(MFI);
- if (BI.Uses && UseI != UseE) {
+ bool Uses = UseI != UseE && *UseI < Stop;
+ if (Uses) {
BI.FirstUse = *UseI;
assert(BI.FirstUse >= Start);
do ++UseI;
// Don't set LiveThrough when the block has a gap.
BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
- LiveBlocks.push_back(BI);
-
+ if (Uses)
+ UseBlocks.push_back(BI);
+ else {
+ ++NumThroughBlocks;
+ ThroughBlocks.set(BI.MBB->getNumber());
+ }
// FIXME: This should never happen. The live range stops or starts without a
// corresponding use. An earlier pass did something wrong.
- if (!BI.LiveThrough && !BI.Uses)
+ if (!BI.LiveThrough && !Uses)
return false;
// LVI is now at LVE or LVI->end >= Stop.
return I != Orig.begin() && (--I)->end == Idx;
}
-void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const {
- for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) {
- unsigned count = UsingBlocks.lookup(*I);
- OS << " BB#" << (*I)->getNumber();
- if (count)
- OS << '(' << count << ')';
- }
-}
-
void SplitAnalysis::analyze(const LiveInterval *li) {
clear();
CurLI = li;
}
/// Create a new virtual register and live interval.
-void SplitEditor::openIntv() {
+unsigned SplitEditor::openIntv() {
assert(!OpenIdx && "Previous LI not closed before openIntv");
// Create the complement as index 0.
// Create the open interval.
OpenIdx = Edit->size();
Edit->create(LIS, VRM);
+ return OpenIdx;
+}
+
+void SplitEditor::selectIntv(unsigned Idx) {
+ assert(Idx != 0 && "Cannot select the complement interval");
+ assert(Idx < Edit->size() && "Can only select previously opened interval");
+ OpenIdx = Idx;
}
SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
"Range cannot span basic blocks");
// The complement interval will be extended as needed by extendRange().
- markComplexMapped(0, ParentVNI);
+ if (ParentVNI)
+ markComplexMapped(0, ParentVNI);
DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
RegAssign.insert(Start, End, OpenIdx);
DEBUG(dump());
/// may be an advantage to split CurLI for the duration of the block.
bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
// If CurLI is local to one block, there is no point to splitting it.
- if (LiveBlocks.size() <= 1)
+ if (UseBlocks.size() <= 1)
return false;
// Add blocks with multiple uses.
- for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
- const BlockInfo &BI = LiveBlocks[i];
- if (!BI.Uses)
- continue;
- unsigned Instrs = UsingBlocks.lookup(BI.MBB);
- if (Instrs <= 1)
- continue;
- if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
+ for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) {
+ const BlockInfo &BI = UseBlocks[i];
+ if (BI.FirstUse == BI.LastUse)
continue;
Blocks.insert(BI.MBB);
}
/// basic block in Blocks.
void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
-
- for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
- const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
- if (!BI.Uses || !Blocks.count(BI.MBB))
+ ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks();
+ for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+ const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
+ if (!Blocks.count(BI.MBB))
continue;
openIntv();