+static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
+ const MachineFunction &MF) {
+ const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF);
+ for (unsigned i = 0; CSR[i] != 0; ++i)
+ if (TRI.regsOverlap(reg, CSR[i]))
+ return true;
+ return false;
+}
+
+void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
+ Spiller &VRegSpiller) {
+ MachineFunction &MF = G.getMetadata().MF;
+
+ LiveIntervals &LIS = G.getMetadata().LIS;
+ const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
+ const TargetRegisterInfo &TRI =
+ *G.getMetadata().MF.getSubtarget().getRegisterInfo();
+
+ std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
+
+ while (!Worklist.empty()) {
+ unsigned VReg = Worklist.back();
+ Worklist.pop_back();
+
+ const TargetRegisterClass *TRC = MRI.getRegClass(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.
+ std::vector<unsigned> VRegAllowed;
+ ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
+ for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
+ unsigned PReg = RawPRegOrder[I];
+ if (MRI.isReserved(PReg))
+ continue;
+
+ // vregLI crosses a regmask operand that clobbers preg.
+ if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
+ continue;
+
+ // 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;
+ }
+ }
+ if (Interference)
+ continue;
+
+ // preg is usable for this virtual register.
+ VRegAllowed.push_back(PReg);
+ }
+
+ // Check for vregs that have no allowed registers. These should be
+ // pre-spilled and the new vregs added to the worklist.
+ if (VRegAllowed.empty()) {
+ SmallVector<unsigned, 8> NewVRegs;
+ spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
+ Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
+ continue;
+ }
+
+ PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
+
+ // Tweak cost of callee saved registers, as using then force spilling and
+ // restoring them. This would only happen in the prologue / epilogue though.
+ for (unsigned i = 0; i != VRegAllowed.size(); ++i)
+ if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
+ NodeCosts[1 + i] += 1.0;
+
+ PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
+ G.getNodeMetadata(NId).setVReg(VReg);
+ G.getNodeMetadata(NId).setAllowedRegs(
+ G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
+ G.getMetadata().setNodeIdForVReg(VReg, NId);
+ }
+}
+
+void RegAllocPBQP::spillVReg(unsigned VReg,
+ SmallVectorImpl<unsigned> &NewIntervals,
+ MachineFunction &MF, LiveIntervals &LIS,
+ VirtRegMap &VRM, Spiller &VRegSpiller) {
+
+ VRegsToAlloc.erase(VReg);
+ LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM);
+ VRegSpiller.spill(LRE);
+
+ const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
+ (void)TRI;
+ 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
+ // allocate.
+ for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
+ I != E; ++I) {
+ const LiveInterval &LI = LIS.getInterval(*I);
+ assert(!LI.empty() && "Empty spill range.");
+ DEBUG(dbgs() << PrintReg(LI.reg, &TRI) << " ");
+ VRegsToAlloc.insert(LI.reg);
+ }
+
+ DEBUG(dbgs() << ")\n");
+}
+
+bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
+ const PBQP::Solution &Solution,
+ VirtRegMap &VRM,
+ Spiller &VRegSpiller) {
+ MachineFunction &MF = G.getMetadata().MF;
+ LiveIntervals &LIS = G.getMetadata().LIS;
+ const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
+ (void)TRI;
+