#define DEBUG_TYPE "regalloc"
-#include "RenderMachineFunction.h"
-#include "Spiller.h"
-#include "VirtRegMap.h"
+#include "llvm/CodeGen/RegAllocPBQP.h"
#include "RegisterCoalescer.h"
-#include "llvm/Module.h"
+#include "Spiller.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
-#include "llvm/CodeGen/RegAllocPBQP.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
#include "llvm/CodeGen/PBQP/Graph.h"
+#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
initializeLiveStacksPass(*PassRegistry::getPassRegistry());
initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
- initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
}
/// Return the pass name.
typedef std::vector<AllowedSet> AllowedSetMap;
typedef std::pair<unsigned, unsigned> RegPair;
typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
- typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
typedef std::set<unsigned> RegSet;
const TargetInstrInfo *tii;
const MachineLoopInfo *loopInfo;
MachineRegisterInfo *mri;
- RenderMachineFunction *rmf;
std::auto_ptr<Spiller> spiller;
LiveIntervals *lis;
const MachineLoopInfo *loopInfo,
const RegSet &vregs) {
- typedef std::vector<const LiveInterval*> LIVector;
- ArrayRef<SlotIndex> regMaskSlots = lis->getRegMaskSlots();
+ LiveIntervals *LIS = const_cast<LiveIntervals*>(lis);
MachineRegisterInfo *mri = &mf->getRegInfo();
const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
RegSet pregs;
// Collect the set of preg intervals, record that they're used in the MF.
- for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end();
- itr != end; ++itr) {
- if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
- pregs.insert(itr->first);
- mri->setPhysRegUsed(itr->first);
- }
+ for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) {
+ if (mri->def_empty(Reg))
+ continue;
+ pregs.insert(Reg);
+ mri->setPhysRegUsed(Reg);
}
- BitVector reservedRegs = tri->getReservedRegs(*mf);
-
// Iterate over vregs.
for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
vregItr != vregEnd; ++vregItr) {
unsigned vreg = *vregItr;
const TargetRegisterClass *trc = mri->getRegClass(vreg);
- const LiveInterval *vregLI = &lis->getInterval(vreg);
+ LiveInterval *vregLI = &LIS->getInterval(vreg);
+
+ // Record any overlaps with regmask operands.
+ BitVector regMaskOverlaps;
+ LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps);
// Compute an initial allowed set for the current vreg.
typedef std::vector<unsigned> VRAllowed;
ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf);
for (unsigned i = 0; i != rawOrder.size(); ++i) {
unsigned preg = rawOrder[i];
- if (!reservedRegs.test(preg)) {
- vrAllowed.push_back(preg);
- }
- }
-
- RegSet overlappingPRegs;
-
- // Record physical registers whose ranges overlap.
- for (RegSet::const_iterator pregItr = pregs.begin(),
- pregEnd = pregs.end();
- pregItr != pregEnd; ++pregItr) {
- unsigned preg = *pregItr;
- const LiveInterval *pregLI = &lis->getInterval(preg);
-
- if (pregLI->empty()) {
+ if (mri->isReserved(preg))
continue;
- }
- if (vregLI->overlaps(*pregLI))
- overlappingPRegs.insert(preg);
- }
+ // vregLI crosses a regmask operand that clobbers preg.
+ if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg))
+ continue;
- // Record any overlaps with regmask operands.
- BitVector regMaskOverlaps(tri->getNumRegs());
- for (ArrayRef<SlotIndex>::iterator rmItr = regMaskSlots.begin(),
- rmEnd = regMaskSlots.end();
- rmItr != rmEnd; ++rmItr) {
- SlotIndex rmIdx = *rmItr;
- if (vregLI->liveAt(rmIdx)) {
- MachineInstr *rmMI = lis->getInstructionFromIndex(rmIdx);
- const uint32_t* regMask = 0;
- for (MachineInstr::mop_iterator mopItr = rmMI->operands_begin(),
- mopEnd = rmMI->operands_end();
- mopItr != mopEnd; ++mopItr) {
- if (mopItr->isRegMask()) {
- regMask = mopItr->getRegMask();
- break;
- }
+ // vregLI overlaps fixed regunit interference.
+ bool Interference = false;
+ for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) {
+ if (vregLI->overlaps(LIS->getRegUnit(*Units))) {
+ Interference = true;
+ break;
}
- assert(regMask != 0 && "Couldn't find register mask.");
- regMaskOverlaps.setBitsNotInMask(regMask);
}
- }
-
- for (unsigned preg = 0; preg < tri->getNumRegs(); ++preg) {
- if (regMaskOverlaps.test(preg))
- overlappingPRegs.insert(preg);
- }
-
- for (RegSet::const_iterator pregItr = overlappingPRegs.begin(),
- pregEnd = overlappingPRegs.end();
- pregItr != pregEnd; ++pregItr) {
- unsigned preg = *pregItr;
-
- // Remove the register from the allowed set.
- VRAllowed::iterator eraseItr =
- std::find(vrAllowed.begin(), vrAllowed.end(), preg);
-
- if (eraseItr != vrAllowed.end()) {
- vrAllowed.erase(eraseItr);
- }
-
- // Also remove any aliases.
- const uint16_t *aliasItr = tri->getAliasSet(preg);
- if (aliasItr != 0) {
- for (; *aliasItr != 0; ++aliasItr) {
- VRAllowed::iterator eraseItr =
- std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);
+ if (Interference)
+ continue;
- if (eraseItr != vrAllowed.end()) {
- vrAllowed.erase(eraseItr);
- }
- }
- }
+ // preg is usable for this virtual register.
+ vrAllowed.push_back(preg);
}
// Construct the node.
PBQP::Graph &g = p->getGraph();
const TargetMachine &tm = mf->getTarget();
- CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo());
+ CoalescerPair cp(*tm.getRegisterInfo());
// Scan the machine function and add a coalescing cost whenever CoalescerPair
// gives the Ok.
loopInfo->getLoopDepth(mbb));
if (cp.isPhys()) {
- if (!lis->isAllocatable(dst)) {
+ if (!mf->getRegInfo().isAllocatable(dst)) {
continue;
}
au.addRequired<SlotIndexes>();
au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
+ au.addPreserved<LiveIntervals>();
//au.addRequiredID(SplitCriticalEdgesID);
if (customPassID)
au.addRequiredID(*customPassID);
au.addRequired<MachineLoopInfo>();
au.addPreserved<MachineLoopInfo>();
au.addRequired<VirtRegMap>();
- au.addRequired<RenderMachineFunction>();
+ au.addPreserved<VirtRegMap>();
MachineFunctionPass::getAnalysisUsage(au);
}
void RegAllocPBQP::findVRegIntervalsToAlloc() {
// Iterate over all live ranges.
- for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
- itr != end; ++itr) {
-
- // Ignore physical ones.
- if (TargetRegisterInfo::isPhysicalRegister(itr->first))
+ for (unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) {
+ unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+ if (mri->reg_nodbg_empty(Reg))
continue;
-
- LiveInterval *li = itr->second;
+ LiveInterval *li = &lis->getInterval(Reg);
// If this live interval is non-empty we will use pbqp to allocate it.
// Empty intervals we allocate in a simple post-processing stage in
if (problem.isPRegOption(vreg, alloc)) {
unsigned preg = problem.getPRegForOption(vreg, alloc);
- DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n");
+ DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> "
+ << tri->getName(preg) << "\n");
assert(preg != 0 && "Invalid preg selected.");
vrm->assignVirt2Phys(vreg, preg);
} else if (problem.isSpillOption(vreg, alloc)) {
vregsToAlloc.erase(vreg);
SmallVector<LiveInterval*, 8> newSpills;
- LiveRangeEdit LRE(lis->getInterval(vreg), newSpills, *mf, *lis, vrm);
+ LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm);
spiller->spill(LRE);
- DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: "
+ DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: "
<< LRE.getParent().weight << ", New vregs: ");
// Copy any newly inserted live intervals into the list of regs to
for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end();
itr != end; ++itr) {
assert(!(*itr)->empty() && "Empty spill range.");
- DEBUG(dbgs() << (*itr)->reg << " ");
+ DEBUG(dbgs() << PrintReg((*itr)->reg, tri) << " ");
vregsToAlloc.insert((*itr)->reg);
}
void RegAllocPBQP::finalizeAlloc() const {
- typedef LiveIntervals::iterator LIIterator;
- typedef LiveInterval::Ranges::const_iterator LRIterator;
-
// First allocate registers for the empty intervals.
for (RegSet::const_iterator
itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end();
itr != end; ++itr) {
LiveInterval *li = &lis->getInterval(*itr);
- unsigned physReg = vrm->getRegAllocPref(li->reg);
+ unsigned physReg = mri->getSimpleHint(li->reg);
if (physReg == 0) {
const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
vrm->assignVirt2Phys(li->reg, physReg);
}
-
- // Finally iterate over the basic blocks to compute and set the live-in sets.
- SmallVector<MachineBasicBlock*, 8> liveInMBBs;
- MachineBasicBlock *entryMBB = &*mf->begin();
-
- for (LIIterator liItr = lis->begin(), liEnd = lis->end();
- liItr != liEnd; ++liItr) {
-
- const LiveInterval *li = liItr->second;
- unsigned reg = 0;
-
- // Get the physical register for this interval
- if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
- reg = li->reg;
- } else if (vrm->isAssignedReg(li->reg)) {
- reg = vrm->getPhys(li->reg);
- } else {
- // Ranges which are assigned a stack slot only are ignored.
- continue;
- }
-
- if (reg == 0) {
- // Filter out zero regs - they're for intervals that were spilled.
- continue;
- }
-
- // Iterate over the ranges of the current interval...
- for (LRIterator lrItr = li->begin(), lrEnd = li->end();
- lrItr != lrEnd; ++lrItr) {
-
- // Find the set of basic blocks which this range is live into...
- if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) {
- // And add the physreg for this interval to their live-in sets.
- for (unsigned i = 0; i != liveInMBBs.size(); ++i) {
- if (liveInMBBs[i] != entryMBB) {
- if (!liveInMBBs[i]->isLiveIn(reg)) {
- liveInMBBs[i]->addLiveIn(reg);
- }
- }
- }
- liveInMBBs.clear();
- }
- }
- }
-
}
bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
lis = &getAnalysis<LiveIntervals>();
lss = &getAnalysis<LiveStacks>();
loopInfo = &getAnalysis<MachineLoopInfo>();
- rmf = &getAnalysis<RenderMachineFunction>();
vrm = &getAnalysis<VirtRegMap>();
spiller.reset(createInlineSpiller(*this, MF, *vrm));
mri->freezeReservedRegs(MF);
- DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
+ DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n");
// Allocator main loop:
//
// Find the vreg intervals in need of allocation.
findVRegIntervalsToAlloc();
+#ifndef NDEBUG
const Function* func = mf->getFunction();
std::string fqn =
func->getParent()->getModuleIdentifier() + "." +
func->getName().str();
- (void)fqn;
+#endif
// If there are non-empty intervals allocate them using pbqp.
if (!vregsToAlloc.empty()) {
// Finalise allocation, allocate empty ranges.
finalizeAlloc();
-
- rmf->renderMachineFunction("After PBQP register allocation.", vrm);
-
vregsToAlloc.clear();
emptyIntervalVRegs.clear();
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
- // Run rewriter
- vrm->rewrite(lis->getSlotIndexes());
-
- // All machine operands and other references to virtual registers have been
- // replaced. Remove the virtual registers.
- vrm->clearAllVirt();
- mri->clearVirtRegs();
-
return true;
}
projects / oota-llvm.git / blobdiff