+
+/// findFirstUse - Calculate the distance to the first use of the
+/// specified register.
+MachineInstr*
+RegScavenger::findFirstUse(MachineBasicBlock *MBB,
+ MachineBasicBlock::iterator I, unsigned Reg,
+ unsigned &Dist) {
+ MachineInstr *UseMI = 0;
+ Dist = ~0U;
+ for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
+ RE = MRI->reg_end(); RI != RE; ++RI) {
+ MachineInstr *UDMI = &*RI;
+ if (UDMI->getParent() != MBB)
+ continue;
+ DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
+ if (DI == DistanceMap.end()) {
+ // If it's not in map, it's below current MI, let's initialize the
+ // map.
+ I = next(I);
+ unsigned Dist = CurrDist + 1;
+ while (I != MBB->end()) {
+ DistanceMap.insert(std::make_pair(I, Dist++));
+ I = next(I);
+ }
+ }
+ DI = DistanceMap.find(UDMI);
+ if (DI->second > CurrDist && DI->second < Dist) {
+ Dist = DI->second;
+ UseMI = UDMI;
+ }
+ }
+ return UseMI;
+}
+
+unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
+ MachineBasicBlock::iterator I,
+ int SPAdj) {
+ assert(ScavengingFrameIndex >= 0 &&
+ "Cannot scavenge a register without an emergency spill slot!");
+
+ // Mask off the registers which are not in the TargetRegisterClass.
+ BitVector Candidates(NumPhysRegs, false);
+ CreateRegClassMask(RC, Candidates);
+ Candidates ^= ReservedRegs & Candidates; // Do not include reserved registers.
+
+ // Exclude all the registers being used by the instruction.
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = I->getOperand(i);
+ if (MO.isReg())
+ Candidates.reset(MO.getReg());
+ }
+
+ // Find the register whose use is furthest away.
+ unsigned SReg = 0;
+ unsigned MaxDist = 0;
+ MachineInstr *MaxUseMI = 0;
+ int Reg = Candidates.find_first();
+ while (Reg != -1) {
+ unsigned Dist;
+ MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
+ for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
+ unsigned AsDist;
+ MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
+ if (AsDist < Dist) {
+ Dist = AsDist;
+ UseMI = AsUseMI;
+ }
+ }
+ if (Dist >= MaxDist) {
+ MaxDist = Dist;
+ MaxUseMI = UseMI;
+ SReg = Reg;
+ }
+ Reg = Candidates.find_next(Reg);
+ }
+
+ assert(ScavengedReg == 0 &&
+ "Scavenger slot is live, unable to scavenge another register!");
+
+ // Make sure SReg is marked as used. It could be considered available if it is
+ // one of the callee saved registers, but hasn't been spilled.
+ if (!isUsed(SReg)) {
+ MBB->addLiveIn(SReg);
+ setUsed(SReg);
+ }
+
+ // Spill the scavenged register before I.
+ TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
+ MachineBasicBlock::iterator II = prior(I);
+ TRI->eliminateFrameIndex(II, SPAdj, this);
+
+ // Restore the scavenged register before its use (or first terminator).
+ II = MaxUseMI
+ ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
+ TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
+ ScavengeRestore = prior(II);
+ ScavengedReg = SReg;
+ ScavengedRC = RC;
+
+ return SReg;
+}