-/// rewriteMBB - Keep track of which spills are available even after the
-/// register allocator is done with them. If possible, avoid reloading vregs.
-void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
- DOUT << MBB.getBasicBlock()->getName() << ":\n";
-
- MachineFunction &MF = *MBB.getParent();
-
- // Spills - Keep track of which spilled values are available in physregs so
- // that we can choose to reuse the physregs instead of emitting reloads.
- AvailableSpills Spills(MRI, TII);
-
- // MaybeDeadStores - When we need to write a value back into a stack slot,
- // keep track of the inserted store. If the stack slot value is never read
- // (because the value was used from some available register, for example), and
- // subsequently stored to, the original store is dead. This map keeps track
- // of inserted stores that are not used. If we see a subsequent store to the
- // same stack slot, the original store is deleted.
- std::vector<MachineInstr*> MaybeDeadStores;
- MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL);
-
- // ReMatDefs - These are rematerializable def MIs which are not deleted.
- SmallSet<MachineInstr*, 4> ReMatDefs;
-
- // Keep track of kill information.
- BitVector RegKills(MRI->getNumRegs());
- std::vector<MachineOperand*> KillOps;
- KillOps.resize(MRI->getNumRegs(), NULL);
-
- for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
- MII != E; ) {
- MachineInstr &MI = *MII;
- MachineBasicBlock::iterator NextMII = MII; ++NextMII;
- VirtRegMap::MI2VirtMapTy::const_iterator I, End;
-
- bool Erased = false;
- bool BackTracked = false;
-
- /// ReusedOperands - Keep track of operand reuse in case we need to undo
- /// reuse.
- ReuseInfo ReusedOperands(MI, MRI);
-
- // Loop over all of the implicit defs, clearing them from our available
- // sets.
- const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
- if (TID->ImplicitDefs) {
- const unsigned *ImpDef = TID->ImplicitDefs;
- for ( ; *ImpDef; ++ImpDef) {
- MF.setPhysRegUsed(*ImpDef);
- ReusedOperands.markClobbered(*ImpDef);
- Spills.ClobberPhysReg(*ImpDef);
- }
- }
-
- // Process all of the spilled uses and all non spilled reg references.
- for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
- MachineOperand &MO = MI.getOperand(i);
- if (!MO.isRegister() || MO.getReg() == 0)
- continue; // Ignore non-register operands.
-
- if (MRegisterInfo::isPhysicalRegister(MO.getReg())) {
- // Ignore physregs for spilling, but remember that it is used by this
- // function.
- MF.setPhysRegUsed(MO.getReg());
- ReusedOperands.markClobbered(MO.getReg());
- continue;
- }
-
- assert(MRegisterInfo::isVirtualRegister(MO.getReg()) &&
- "Not a virtual or a physical register?");
-
- unsigned VirtReg = MO.getReg();
- if (VRM.isAssignedReg(VirtReg)) {
- // This virtual register was assigned a physreg!
- unsigned Phys = VRM.getPhys(VirtReg);
- MF.setPhysRegUsed(Phys);
- if (MO.isDef())
- ReusedOperands.markClobbered(Phys);
- MI.getOperand(i).setReg(Phys);
- continue;
- }
-
- // This virtual register is now known to be a spilled value.
- if (!MO.isUse())
- continue; // Handle defs in the loop below (handle use&def here though)
-
- bool DoReMat = VRM.isReMaterialized(VirtReg);
- int SSorRMId = DoReMat
- ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
- int ReuseSlot = SSorRMId;
-
- // Check to see if this stack slot is available.
- unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
- if (!PhysReg && DoReMat) {
- // This use is rematerializable. But perhaps the value is available in
- // stack if the definition is not deleted. If so, check if we can
- // reuse the value.
- ReuseSlot = VRM.getStackSlot(VirtReg);
- if (ReuseSlot != VirtRegMap::NO_STACK_SLOT)
- PhysReg = Spills.getSpillSlotOrReMatPhysReg(ReuseSlot);
- }
- if (PhysReg) {
- // This spilled operand might be part of a two-address operand. If this
- // is the case, then changing it will necessarily require changing the
- // def part of the instruction as well. However, in some cases, we
- // aren't allowed to modify the reused register. If none of these cases
- // apply, reuse it.
- bool CanReuse = true;
- int ti = TID->getOperandConstraint(i, TOI::TIED_TO);
- if (ti != -1 &&
- MI.getOperand(ti).isRegister() &&
- MI.getOperand(ti).getReg() == VirtReg) {
- // Okay, we have a two address operand. We can reuse this physreg as
- // long as we are allowed to clobber the value and there isn't an
- // earlier def that has already clobbered the physreg.
- CanReuse = Spills.canClobberPhysReg(ReuseSlot) &&
- !ReusedOperands.isClobbered(PhysReg);
- }
-
- if (CanReuse) {
- // If this stack slot value is already available, reuse it!
- if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
- DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
- else
- DOUT << "Reusing SS#" << ReuseSlot;
- DOUT << " from physreg "
- << MRI->getName(PhysReg) << " for vreg"
- << VirtReg <<" instead of reloading into physreg "
- << MRI->getName(VRM.getPhys(VirtReg)) << "\n";
- MI.getOperand(i).setReg(PhysReg);
-
- // The only technical detail we have is that we don't know that
- // PhysReg won't be clobbered by a reloaded stack slot that occurs
- // later in the instruction. In particular, consider 'op V1, V2'.
- // If V1 is available in physreg R0, we would choose to reuse it
- // here, instead of reloading it into the register the allocator
- // indicated (say R1). However, V2 might have to be reloaded
- // later, and it might indicate that it needs to live in R0. When
- // this occurs, we need to have information available that
- // indicates it is safe to use R1 for the reload instead of R0.
- //
- // To further complicate matters, we might conflict with an alias,
- // or R0 and R1 might not be compatible with each other. In this
- // case, we actually insert a reload for V1 in R1, ensuring that
- // we can get at R0 or its alias.
- ReusedOperands.addReuse(i, ReuseSlot, PhysReg,
- VRM.getPhys(VirtReg), VirtReg);
- if (ti != -1)
- // Only mark it clobbered if this is a use&def operand.
- ReusedOperands.markClobbered(PhysReg);
- ++NumReused;
-
- if (MI.getOperand(i).isKill() &&
- ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) {
- // This was the last use and the spilled value is still available
- // for reuse. That means the spill was unnecessary!
- MachineInstr* DeadStore = MaybeDeadStores[ReuseSlot];
- if (DeadStore) {
- DOUT << "Removed dead store:\t" << *DeadStore;
- InvalidateKills(*DeadStore, RegKills, KillOps);
- MBB.erase(DeadStore);
- VRM.RemoveFromFoldedVirtMap(DeadStore);
- MaybeDeadStores[ReuseSlot] = NULL;
- ++NumDSE;
- }
- }
- continue;
- }
-
- // Otherwise we have a situation where we have a two-address instruction
- // whose mod/ref operand needs to be reloaded. This reload is already
- // available in some register "PhysReg", but if we used PhysReg as the
- // operand to our 2-addr instruction, the instruction would modify
- // PhysReg. This isn't cool if something later uses PhysReg and expects
- // to get its initial value.
- //
- // To avoid this problem, and to avoid doing a load right after a store,
- // we emit a copy from PhysReg into the designated register for this
- // operand.
- unsigned DesignatedReg = VRM.getPhys(VirtReg);
- assert(DesignatedReg && "Must map virtreg to physreg!");
-
- // Note that, if we reused a register for a previous operand, the
- // register we want to reload into might not actually be
- // available. If this occurs, use the register indicated by the
- // reuser.
- if (ReusedOperands.hasReuses())
- DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI,
- Spills, MaybeDeadStores, RegKills, KillOps, VRM);
-
- // If the mapped designated register is actually the physreg we have
- // incoming, we don't need to inserted a dead copy.
- if (DesignatedReg == PhysReg) {
- // If this stack slot value is already available, reuse it!
- if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
- DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
- else
- DOUT << "Reusing SS#" << ReuseSlot;
- DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg"
- << VirtReg
- << " instead of reloading into same physreg.\n";
- MI.getOperand(i).setReg(PhysReg);
- ReusedOperands.markClobbered(PhysReg);
- ++NumReused;
- continue;
- }
-
- const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
- MF.setPhysRegUsed(DesignatedReg);
- ReusedOperands.markClobbered(DesignatedReg);
- MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC);
-
- MachineInstr *CopyMI = prior(MII);
- UpdateKills(*CopyMI, RegKills, KillOps);
-
- // This invalidates DesignatedReg.
- Spills.ClobberPhysReg(DesignatedReg);
-
- Spills.addAvailable(ReuseSlot, &MI, DesignatedReg);
- MI.getOperand(i).setReg(DesignatedReg);
- DOUT << '\t' << *prior(MII);
- ++NumReused;
- continue;
- }
-
- // Otherwise, reload it and remember that we have it.
- PhysReg = VRM.getPhys(VirtReg);
- assert(PhysReg && "Must map virtreg to physreg!");
- const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
-
- // Note that, if we reused a register for a previous operand, the
- // register we want to reload into might not actually be
- // available. If this occurs, use the register indicated by the
- // reuser.
- if (ReusedOperands.hasReuses())
- PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
- Spills, MaybeDeadStores, RegKills, KillOps, VRM);
-
- MF.setPhysRegUsed(PhysReg);
- ReusedOperands.markClobbered(PhysReg);
- if (DoReMat) {
- MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg));
- ++NumReMats;
- } else {
- MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
- ++NumLoads;
- }
- // This invalidates PhysReg.
- Spills.ClobberPhysReg(PhysReg);
-
- // Any stores to this stack slot are not dead anymore.
- if (!DoReMat)
- MaybeDeadStores[SSorRMId] = NULL;
- Spills.addAvailable(SSorRMId, &MI, PhysReg);
- // Assumes this is the last use. IsKill will be unset if reg is reused
- // unless it's a two-address operand.
- if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1)
- MI.getOperand(i).setIsKill();
- MI.getOperand(i).setReg(PhysReg);
- UpdateKills(*prior(MII), RegKills, KillOps);
- DOUT << '\t' << *prior(MII);
- }
-
- DOUT << '\t' << MI;
-
- // If we have folded references to memory operands, make sure we clear all
- // physical registers that may contain the value of the spilled virtual
- // register
- SmallSet<int, 1> FoldedSS;
- for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
- DOUT << "Folded vreg: " << I->second.first << " MR: "
- << I->second.second;
- unsigned VirtReg = I->second.first;
- VirtRegMap::ModRef MR = I->second.second;
- if (VRM.isAssignedReg(VirtReg)) {
- DOUT << ": No stack slot!\n";
- continue;
- }
- int SS = VRM.getStackSlot(VirtReg);
- FoldedSS.insert(SS);
- DOUT << " - StackSlot: " << SS << "\n";
-
- // If this folded instruction is just a use, check to see if it's a
- // straight load from the virt reg slot.
- if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
- int FrameIdx;
- if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
- if (FrameIdx == SS) {
- // If this spill slot is available, turn it into a copy (or nothing)
- // instead of leaving it as a load!
- if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) {
- DOUT << "Promoted Load To Copy: " << MI;
- if (DestReg != InReg) {
- MRI->copyRegToReg(MBB, &MI, DestReg, InReg,
- MF.getSSARegMap()->getRegClass(VirtReg));
- // Revisit the copy so we make sure to notice the effects of the
- // operation on the destreg (either needing to RA it if it's
- // virtual or needing to clobber any values if it's physical).
- NextMII = &MI;
- --NextMII; // backtrack to the copy.
- BackTracked = true;
- } else
- DOUT << "Removing now-noop copy: " << MI;
-
- VRM.RemoveFromFoldedVirtMap(&MI);
- MBB.erase(&MI);
- Erased = true;
- goto ProcessNextInst;
- }
- }
- }
- }
-
- // If this reference is not a use, any previous store is now dead.
- // Otherwise, the store to this stack slot is not dead anymore.
- MachineInstr* DeadStore = MaybeDeadStores[SS];
- if (DeadStore) {
- if (!(MR & VirtRegMap::isRef)) { // Previous store is dead.
- // If we get here, the store is dead, nuke it now.
- assert(VirtRegMap::isMod && "Can't be modref!");
- DOUT << "Removed dead store:\t" << *DeadStore;
- InvalidateKills(*DeadStore, RegKills, KillOps);
- MBB.erase(DeadStore);
- VRM.RemoveFromFoldedVirtMap(DeadStore);
- ++NumDSE;