+//===----------------------------------------------------------------------===//
+// Last Chance Recoloring
+//===----------------------------------------------------------------------===//
+
+/// mayRecolorAllInterferences - Check if the virtual registers that
+/// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
+/// recolored to free \p PhysReg.
+/// When true is returned, \p RecoloringCandidates has been augmented with all
+/// the live intervals that need to be recolored in order to free \p PhysReg
+/// for \p VirtReg.
+/// \p FixedRegisters contains all the virtual registers that cannot be
+/// recolored.
+bool
+RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
+ SmallLISet &RecoloringCandidates,
+ const SmallVirtRegSet &FixedRegisters) {
+ const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
+
+ for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
+ LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
+ // If there is LastChanceRecoloringMaxInterference or more interferences,
+ // chances are one would not be recolorable.
+ if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
+ LastChanceRecoloringMaxInterference && !ExhaustiveSearch) {
+ DEBUG(dbgs() << "Early abort: too many interferences.\n");
+ CutOffInfo |= CO_Interf;
+ return false;
+ }
+ for (unsigned i = Q.interferingVRegs().size(); i; --i) {
+ LiveInterval *Intf = Q.interferingVRegs()[i - 1];
+ // If Intf is done and sit on the same register class as VirtReg,
+ // it would not be recolorable as it is in the same state as VirtReg.
+ if ((getStage(*Intf) == RS_Done &&
+ MRI->getRegClass(Intf->reg) == CurRC) ||
+ FixedRegisters.count(Intf->reg)) {
+ DEBUG(dbgs() << "Early abort: the inteference is not recolorable.\n");
+ return false;
+ }
+ RecoloringCandidates.insert(Intf);
+ }
+ }
+ return true;
+}
+
+/// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
+/// its interferences.
+/// Last chance recoloring chooses a color for \p VirtReg and recolors every
+/// virtual register that was using it. The recoloring process may recursively
+/// use the last chance recoloring. Therefore, when a virtual register has been
+/// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
+/// be last-chance-recolored again during this recoloring "session".
+/// E.g.,
+/// Let
+/// vA can use {R1, R2 }
+/// vB can use { R2, R3}
+/// vC can use {R1 }
+/// Where vA, vB, and vC cannot be split anymore (they are reloads for
+/// instance) and they all interfere.
+///
+/// vA is assigned R1
+/// vB is assigned R2
+/// vC tries to evict vA but vA is already done.
+/// Regular register allocation fails.
+///
+/// Last chance recoloring kicks in:
+/// vC does as if vA was evicted => vC uses R1.
+/// vC is marked as fixed.
+/// vA needs to find a color.
+/// None are available.
+/// vA cannot evict vC: vC is a fixed virtual register now.
+/// vA does as if vB was evicted => vA uses R2.
+/// vB needs to find a color.
+/// R3 is available.
+/// Recoloring => vC = R1, vA = R2, vB = R3
+///
+/// \p Order defines the preferred allocation order for \p VirtReg.
+/// \p NewRegs will contain any new virtual register that have been created
+/// (split, spill) during the process and that must be assigned.
+/// \p FixedRegisters contains all the virtual registers that cannot be
+/// recolored.
+/// \p Depth gives the current depth of the last chance recoloring.
+/// \return a physical register that can be used for VirtReg or ~0u if none
+/// exists.
+unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
+ AllocationOrder &Order,
+ SmallVectorImpl<unsigned> &NewVRegs,
+ SmallVirtRegSet &FixedRegisters,
+ unsigned Depth) {
+ DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
+ // Ranges must be Done.
+ assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
+ "Last chance recoloring should really be last chance");
+ // Set the max depth to LastChanceRecoloringMaxDepth.
+ // We may want to reconsider that if we end up with a too large search space
+ // for target with hundreds of registers.
+ // Indeed, in that case we may want to cut the search space earlier.
+ if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
+ DEBUG(dbgs() << "Abort because max depth has been reached.\n");
+ CutOffInfo |= CO_Depth;
+ return ~0u;
+ }
+
+ // Set of Live intervals that will need to be recolored.
+ SmallLISet RecoloringCandidates;
+ // Record the original mapping virtual register to physical register in case
+ // the recoloring fails.
+ DenseMap<unsigned, unsigned> VirtRegToPhysReg;
+ // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
+ // this recoloring "session".
+ FixedRegisters.insert(VirtReg.reg);
+
+ Order.rewind();
+ while (unsigned PhysReg = Order.next()) {
+ DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
+ << PrintReg(PhysReg, TRI) << '\n');
+ RecoloringCandidates.clear();
+ VirtRegToPhysReg.clear();
+
+ // It is only possible to recolor virtual register interference.
+ if (Matrix->checkInterference(VirtReg, PhysReg) >
+ LiveRegMatrix::IK_VirtReg) {
+ DEBUG(dbgs() << "Some inteferences are not with virtual registers.\n");
+
+ continue;
+ }
+
+ // Early give up on this PhysReg if it is obvious we cannot recolor all
+ // the interferences.
+ if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
+ FixedRegisters)) {
+ DEBUG(dbgs() << "Some inteferences cannot be recolored.\n");
+ continue;
+ }
+
+ // RecoloringCandidates contains all the virtual registers that interfer
+ // with VirtReg on PhysReg (or one of its aliases).
+ // Enqueue them for recoloring and perform the actual recoloring.
+ PQueue RecoloringQueue;
+ for (SmallLISet::iterator It = RecoloringCandidates.begin(),
+ EndIt = RecoloringCandidates.end();
+ It != EndIt; ++It) {
+ unsigned ItVirtReg = (*It)->reg;
+ enqueue(RecoloringQueue, *It);
+ assert(VRM->hasPhys(ItVirtReg) &&
+ "Interferences are supposed to be with allocated vairables");
+
+ // Record the current allocation.
+ VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
+ // unset the related struct.
+ Matrix->unassign(**It);
+ }
+
+ // Do as if VirtReg was assigned to PhysReg so that the underlying
+ // recoloring has the right information about the interferes and
+ // available colors.
+ Matrix->assign(VirtReg, PhysReg);
+
+ // Save the current recoloring state.
+ // If we cannot recolor all the interferences, we will have to start again
+ // at this point for the next physical register.
+ SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
+ if (tryRecoloringCandidates(RecoloringQueue, NewVRegs, FixedRegisters,
+ Depth)) {
+ // Do not mess up with the global assignment process.
+ // I.e., VirtReg must be unassigned.
+ Matrix->unassign(VirtReg);
+ return PhysReg;
+ }
+
+ DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
+ << PrintReg(PhysReg, TRI) << '\n');
+
+ // The recoloring attempt failed, undo the changes.
+ FixedRegisters = SaveFixedRegisters;
+ Matrix->unassign(VirtReg);
+
+ for (SmallLISet::iterator It = RecoloringCandidates.begin(),
+ EndIt = RecoloringCandidates.end();
+ It != EndIt; ++It) {
+ unsigned ItVirtReg = (*It)->reg;
+ if (VRM->hasPhys(ItVirtReg))
+ Matrix->unassign(**It);
+ Matrix->assign(**It, VirtRegToPhysReg[ItVirtReg]);
+ }
+ }
+
+ // Last chance recoloring did not worked either, give up.
+ return ~0u;
+}
+
+/// tryRecoloringCandidates - Try to assign a new color to every register
+/// in \RecoloringQueue.
+/// \p NewRegs will contain any new virtual register created during the
+/// recoloring process.
+/// \p FixedRegisters[in/out] contains all the registers that have been
+/// recolored.
+/// \return true if all virtual registers in RecoloringQueue were successfully
+/// recolored, false otherwise.
+bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
+ SmallVectorImpl<unsigned> &NewVRegs,
+ SmallVirtRegSet &FixedRegisters,
+ unsigned Depth) {
+ while (!RecoloringQueue.empty()) {
+ LiveInterval *LI = dequeue(RecoloringQueue);
+ DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
+ unsigned PhysReg;
+ PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
+ if (PhysReg == ~0u || !PhysReg)
+ return false;
+ DEBUG(dbgs() << "Recoloring of " << *LI
+ << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
+ Matrix->assign(*LI, PhysReg);
+ FixedRegisters.insert(LI->reg);
+ }
+ return true;
+}