//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/Function.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
-#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
STATISTIC(NumIters , "Number of iterations performed");
STATISTIC(NumBacktracks, "Number of times we had to backtrack");
+STATISTIC(NumCoalesce, "Number of copies coalesced");
static RegisterRegAlloc
linearscanRegAlloc("linearscan", " linear scan register allocator",
MachineFunction* mf_;
const TargetMachine* tm_;
const MRegisterInfo* mri_;
+ const TargetInstrInfo* tii_;
+ MachineRegisterInfo *reginfo_;
+ BitVector allocatableRegs_;
LiveIntervals* li_;
+ const MachineLoopInfo *loopInfo;
/// handled_ - Intervals are added to the handled_ set in the order of their
/// start value. This is uses for backtracking.
// Make sure PassManager knows which analyses to make available
// to coalescing and which analyses coalescing invalidates.
AU.addRequiredTransitive<RegisterCoalescer>();
+ AU.addRequired<MachineLoopInfo>();
+ AU.addPreserved<MachineLoopInfo>();
+ AU.addPreservedID(MachineDominatorsID);
MachineFunctionPass::getAnalysisUsage(AU);
}
/// is available, or spill.
void assignRegOrStackSlotAtInterval(LiveInterval* cur);
+ /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
+ /// try allocate the definition the same register as the source register
+ /// if the register is not defined during live time of the interval. This
+ /// eliminate a copy. This is used to coalesce copies which were not
+ /// coalesced away before allocation either due to dest and src being in
+ /// different register classes or because the coalescer was overly
+ /// conservative.
+ unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
+
///
/// register handling helpers
///
RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
}
+/// attemptTrivialCoalescing - If a simple interval is defined by a copy,
+/// try allocate the definition the same register as the source register
+/// if the register is not defined during live time of the interval. This
+/// eliminate a copy. This is used to coalesce copies which were not
+/// coalesced away before allocation either due to dest and src being in
+/// different register classes or because the coalescer was overly
+/// conservative.
+unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
+ if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
+ return Reg;
+
+ VNInfo *vni = cur.getValNumInfo(0);
+ if (!vni->def || vni->def == ~1U || vni->def == ~0U)
+ return Reg;
+ MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
+ unsigned SrcReg, DstReg;
+ if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
+ return Reg;
+ if (MRegisterInfo::isVirtualRegister(SrcReg))
+ if (!vrm_->isAssignedReg(SrcReg))
+ return Reg;
+ else
+ SrcReg = vrm_->getPhys(SrcReg);
+ if (Reg == SrcReg)
+ return Reg;
+
+ const TargetRegisterClass *RC = reginfo_->getRegClass(cur.reg);
+ if (!RC->contains(SrcReg))
+ return Reg;
+
+ // Try to coalesce.
+ if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
+ DOUT << "Coalescing: " << cur << " -> " << mri_->getName(SrcReg) << '\n';
+ vrm_->clearVirt(cur.reg);
+ vrm_->assignVirt2Phys(cur.reg, SrcReg);
+ ++NumCoalesce;
+ return SrcReg;
+ }
+
+ return Reg;
+}
+
bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
mf_ = &fn;
tm_ = &fn.getTarget();
mri_ = tm_->getRegisterInfo();
+ tii_ = tm_->getInstrInfo();
+ reginfo_ = &mf_->getRegInfo();
+ allocatableRegs_ = mri_->getAllocatableSet(fn);
li_ = &getAnalysis<LiveIntervals>();
+ loopInfo = &getAnalysis<MachineLoopInfo>();
// We don't run the coalescer here because we have no reason to
// interact with it. If the coalescer requires interaction, it
for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
- mf_->setPhysRegUsed(i->second.reg);
+ reginfo_->setPhysRegUsed(i->second.reg);
fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
} else
unhandled_.push(&i->second);
// expire any remaining inactive intervals
DEBUG(for (IntervalPtrs::reverse_iterator
- i = inactive_.rbegin(); i != inactive_.rend(); )
+ i = inactive_.rbegin(); i != inactive_.rend(); ++i)
DOUT << "\tinterval " << *i->first << " expired\n");
inactive_.clear();
- // A brute force way of adding live-ins to every BB.
- MachineFunction::iterator MBB = mf_->begin();
- ++MBB; // Skip entry MBB.
- for (MachineFunction::iterator E = mf_->end(); MBB != E; ++MBB) {
- unsigned StartIdx = li_->getMBBStartIdx(MBB->getNumber());
- for (IntervalPtrs::iterator i = fixed_.begin(), e = fixed_.end();
- i != e; ++i)
- if (i->first->liveAt(StartIdx))
- MBB->addLiveIn(i->first->reg);
-
- for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
- LiveInterval *HI = handled_[i];
- unsigned Reg = HI->reg;
- if (vrm_->isAssignedReg(Reg) && HI->liveAt(StartIdx)) {
- assert(MRegisterInfo::isVirtualRegister(Reg));
- Reg = vrm_->getPhys(Reg);
- MBB->addLiveIn(Reg);
+ // Add live-ins to every BB except for entry. Also perform trivial coalescing.
+ MachineFunction::iterator EntryMBB = mf_->begin();
+ SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
+ for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
+ LiveInterval &cur = i->second;
+ unsigned Reg = 0;
+ bool isPhys = MRegisterInfo::isPhysicalRegister(cur.reg);
+ if (isPhys)
+ Reg = i->second.reg;
+ else if (vrm_->isAssignedReg(cur.reg))
+ Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
+ if (!Reg)
+ continue;
+ // Ignore splited live intervals.
+ if (!isPhys && vrm_->getPreSplitReg(cur.reg))
+ continue;
+ for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
+ I != E; ++I) {
+ const LiveRange &LR = *I;
+ if (li_->findLiveInMBBs(LR, LiveInMBBs)) {
+ for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
+ if (LiveInMBBs[i] != EntryMBB)
+ LiveInMBBs[i]->addLiveIn(Reg);
+ LiveInMBBs.clear();
}
}
}
std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
unsigned StartPosition = cur->beginNumber();
- const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(cur->reg);
+ const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
-
+
+ // If this live interval is defined by a move instruction and its source is
+ // assigned a physical register that is compatible with the target register
+ // class, then we should try to assign it the same register.
+ // This can happen when the move is from a larger register class to a smaller
+ // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
+ if (!cur->preference && cur->containsOneValue()) {
+ VNInfo *vni = cur->getValNumInfo(0);
+ if (vni->def && vni->def != ~1U && vni->def != ~0U) {
+ MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
+ unsigned SrcReg, DstReg;
+ if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+ unsigned Reg = 0;
+ if (MRegisterInfo::isPhysicalRegister(SrcReg))
+ Reg = SrcReg;
+ else if (vrm_->isAssignedReg(SrcReg))
+ Reg = vrm_->getPhys(SrcReg);
+ if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
+ cur->preference = Reg;
+ }
+ }
+ }
+
// for every interval in inactive we overlap with, mark the
// register as not free and update spill weights.
for (IntervalPtrs::const_iterator i = inactive_.begin(),
unsigned Reg = i->first->reg;
assert(MRegisterInfo::isVirtualRegister(Reg) &&
"Can only allocate virtual registers!");
- const TargetRegisterClass *RegRC = mf_->getSSARegMap()->getRegClass(Reg);
+ const TargetRegisterClass *RegRC = reginfo_->getRegClass(Reg);
// If this is not in a related reg class to the register we're allocating,
// don't check it.
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
// We got a register. However, if it's in the fixed_ list, we might
// conflict with it. Check to see if we conflict with it or any of its
// aliases.
- std::set<unsigned> RegAliases;
+ SmallSet<unsigned, 8> RegAliases;
for (const unsigned *AS = mri_->getAliasSet(physReg); *AS; ++AS)
RegAliases.insert(*AS);
if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
DOUT << "\t\t\tspilling(c): " << *cur << '\n';
std::vector<LiveInterval*> added =
- li_->addIntervalsForSpills(*cur, *vrm_, cur->reg);
+ li_->addIntervalsForSpills(*cur, loopInfo, *vrm_);
if (added.empty())
return; // Early exit if all spills were folded.
unsigned earliestStart = cur->beginNumber();
// set of spilled vregs (used later to rollback properly)
- std::set<unsigned> spilled;
+ SmallSet<unsigned, 32> spilled;
// spill live intervals of virtual regs mapped to the physical register we
// want to clear (and its aliases). We only spill those that overlap with the
DOUT << "\t\t\tspilling(a): " << *i->first << '\n';
earliestStart = std::min(earliestStart, i->first->beginNumber());
std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*i->first, *vrm_, reg);
+ li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(reg);
}
DOUT << "\t\t\tspilling(i): " << *i->first << '\n';
earliestStart = std::min(earliestStart, i->first->beginNumber());
std::vector<LiveInterval*> newIs =
- li_->addIntervalsForSpills(*i->first, *vrm_, reg);
+ li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_);
std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
spilled.insert(reg);
}
vrm_->clearVirt(i->reg);
unhandled_.push(i);
}
+
+ // It interval has a preference, it must be defined by a copy. Clear the
+ // preference now since the source interval allocation may have been undone
+ // as well.
+ i->preference = 0;
}
// Rewind the iterators in the active, inactive, and fixed lists back to the
std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
unsigned MaxInactiveCount = 0;
- const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(cur->reg);
+ const TargetRegisterClass *RC = reginfo_->getRegClass(cur->reg);
const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
// If this is not in a related reg class to the register we're allocating,
// don't check it.
- const TargetRegisterClass *RegRC = mf_->getSSARegMap()->getRegClass(reg);
+ const TargetRegisterClass *RegRC = reginfo_->getRegClass(reg);
if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
reg = vrm_->getPhys(reg);
++inactiveCounts[reg];
projects / oota-llvm.git / blobdiff