summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r--llvm/lib/CodeGen/PrologEpilogInserter.cpp143
-rw-r--r--llvm/lib/CodeGen/RegisterScavenging.cpp205
2 files changed, 108 insertions, 240 deletions
diff --git a/llvm/lib/CodeGen/PrologEpilogInserter.cpp b/llvm/lib/CodeGen/PrologEpilogInserter.cpp
index 0d90fd3180c..20a9a394ebd 100644
--- a/llvm/lib/CodeGen/PrologEpilogInserter.cpp
+++ b/llvm/lib/CodeGen/PrologEpilogInserter.cpp
@@ -41,7 +41,6 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
-#include <algorithm>
#include <climits>
using namespace llvm;
@@ -1147,55 +1146,6 @@ void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
}
}
-/// Allocate a register for the virtual register \p VReg. The last use of
-/// \p VReg is around the current position of the register scavenger \p RS.
-/// \p ReserveAfter controls whether the scavenged register needs to be reserved
-/// after the current instruction, otherwise it will only be reserved before the
-/// current instruction.
-static unsigned scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS,
- unsigned VReg, bool ReserveAfter) {
-#ifndef NDEBUG
- // Verify that all definitions and uses are in the same basic block.
- const MachineBasicBlock *CommonMBB = nullptr;
- bool HadDef = false;
- for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
- MachineBasicBlock *MBB = MO.getParent()->getParent();
- if (CommonMBB == nullptr)
- CommonMBB = MBB;
- assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
- if (MO.isDef())
- HadDef = true;
- }
- assert(HadDef && "Must have at least 1 Def");
-#endif
-
- // We should only have one definition of the register. However to accomodate
- // the requirements of two address code we also allow definitions in
- // subsequent instructions provided they also read the register. That way
- // we get a single contiguous lifetime.
- //
- // Definitions in MRI.def_begin() are unordered, search for the first.
- const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
- MachineRegisterInfo::def_iterator FirstDef =
- std::find_if(MRI.def_begin(VReg), MRI.def_end(),
- [VReg, TRI](const MachineOperand &MO) {
- return !MO.getParent()->readsRegister(VReg, TRI);
- });
- assert(FirstDef != MRI.def_end() &&
- "Must have one definition that does not redefine vreg");
- MachineInstr &DefMI = *FirstDef->getParent();
-
- // The register scavenger will report a free register inserting an emergency
- // spill/reload if necessary.
- int SPAdj = 0;
- const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
- unsigned SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
- ReserveAfter, SPAdj);
- MRI.replaceRegWith(VReg, SReg);
- ++NumScavengedRegs;
- return SReg;
-}
-
/// doScavengeFrameVirtualRegs - Replace all frame index virtual registers
/// with physical registers. Use the register scavenger to find an
/// appropriate register to use.
@@ -1208,46 +1158,77 @@ doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS) {
// Run through the instructions and find any virtual registers.
MachineRegisterInfo &MRI = MF.getRegInfo();
for (MachineBasicBlock &MBB : MF) {
- RS->enterBasicBlockEnd(MBB);
-
- bool LastIterationHadVRegUses = false;
- for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
- --I;
- // Move RegScavenger to the position between *I and *std::next(I).
- RS->backward(I);
-
- // Look for unassigned vregs in the uses of *std::next(I).
- MachineBasicBlock::iterator N = std::next(I);
- if (LastIterationHadVRegUses) {
- const MachineInstr &NMI = *N;
- for (const MachineOperand &MO : NMI.operands()) {
- if (!MO.isReg() || !MO.readsReg())
- continue;
- unsigned Reg = MO.getReg();
- if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- unsigned SReg = scavengeVReg(MRI, *RS, Reg, true);
- RS->setRegUsed(SReg);
- }
- }
- }
+ RS->enterBasicBlock(MBB);
+
+ int SPAdj = 0;
+
+ // The instruction stream may change in the loop, so check MBB.end()
+ // directly.
+ for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ) {
+ // We might end up here again with a NULL iterator if we scavenged a
+ // register for which we inserted spill code for definition by what was
+ // originally the first instruction in MBB.
+ if (I == MachineBasicBlock::iterator(nullptr))
+ I = MBB.begin();
- // Look for unassigned vregs in the defs of *I.
- LastIterationHadVRegUses = false;
const MachineInstr &MI = *I;
+ MachineBasicBlock::iterator J = std::next(I);
+ MachineBasicBlock::iterator P =
+ I == MBB.begin() ? MachineBasicBlock::iterator(nullptr)
+ : std::prev(I);
+
+ // RS should process this instruction before we might scavenge at this
+ // location. This is because we might be replacing a virtual register
+ // defined by this instruction, and if so, registers killed by this
+ // instruction are available, and defined registers are not.
+ RS->forward(I);
+
for (const MachineOperand &MO : MI.operands()) {
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!TargetRegisterInfo::isVirtualRegister(Reg))
continue;
- // We have to look at all operands anyway so we can precalculate here
- // whether there is a reading operand. This allows use to skip the use
- // step in the next iteration if there was none.
- if (MO.readsReg())
- LastIterationHadVRegUses = true;
- if (MO.isDef())
- scavengeVReg(MRI, *RS, Reg, false);
+
+ // When we first encounter a new virtual register, it
+ // must be a definition.
+ assert(MO.isDef() && "frame index virtual missing def!");
+ // Scavenge a new scratch register
+ const TargetRegisterClass *RC = MRI.getRegClass(Reg);
+ unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
+
+ ++NumScavengedRegs;
+
+ // Replace this reference to the virtual register with the
+ // scratch register.
+ assert(ScratchReg && "Missing scratch register!");
+ MRI.replaceRegWith(Reg, ScratchReg);
+
+ // Because this instruction was processed by the RS before this
+ // register was allocated, make sure that the RS now records the
+ // register as being used.
+ RS->setRegUsed(ScratchReg);
}
+
+ // If the scavenger needed to use one of its spill slots, the
+ // spill code will have been inserted in between I and J. This is a
+ // problem because we need the spill code before I: Move I to just
+ // prior to J.
+ if (I != std::prev(J)) {
+ MBB.splice(J, &MBB, I);
+
+ // Before we move I, we need to prepare the RS to visit I again.
+ // Specifically, RS will assert if it sees uses of registers that
+ // it believes are undefined. Because we have already processed
+ // register kills in I, when it visits I again, it will believe that
+ // those registers are undefined. To avoid this situation, unprocess
+ // the instruction I.
+ assert(RS->getCurrentPosition() == I &&
+ "The register scavenger has an unexpected position");
+ I = P;
+ RS->unprocess(P);
+ } else
+ ++I;
}
}
}
diff --git a/llvm/lib/CodeGen/RegisterScavenging.cpp b/llvm/lib/CodeGen/RegisterScavenging.cpp
index c062bd01f60..79a698d494e 100644
--- a/llvm/lib/CodeGen/RegisterScavenging.cpp
+++ b/llvm/lib/CodeGen/RegisterScavenging.cpp
@@ -299,14 +299,6 @@ void RegScavenger::backward() {
}
}
- // Expire scavenge spill frameindex uses.
- for (ScavengedInfo &I : Scavenged) {
- if (I.Restore == &MI) {
- I.Reg = 0;
- I.Restore = nullptr;
- }
- }
-
if (MBBI == MBB->begin()) {
MBBI = MachineBasicBlock::iterator(nullptr);
Tracking = false;
@@ -406,72 +398,6 @@ unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
return Survivor;
}
-static std::pair<unsigned, MachineBasicBlock::iterator>
-findSurvivorBackwards(const TargetRegisterInfo &TRI,
- MachineBasicBlock::iterator From, MachineBasicBlock::iterator To,
- BitVector &Available, BitVector &Candidates) {
- bool FoundTo = false;
- unsigned Survivor = 0;
- MachineBasicBlock::iterator Pos;
- MachineBasicBlock &MBB = *From->getParent();
- MachineBasicBlock::iterator I = From;
- unsigned InstrLimit = 25;
- unsigned InstrCountDown = InstrLimit;
- for (;;) {
- const MachineInstr &MI = *I;
- if (MI.isDebugValue())
- continue;
-
- // Remove any candidates touched by instruction.
- bool FoundVReg = false;
- for (const MachineOperand &MO : MI.operands()) {
- if (MO.isRegMask()) {
- Candidates.clearBitsNotInMask(MO.getRegMask());
- continue;
- }
- if (!MO.isReg() || MO.isUndef())
- continue;
- unsigned Reg = MO.getReg();
- if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- FoundVReg = true;
- } else if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
- for (MCRegAliasIterator AI(Reg, &TRI, true); AI.isValid(); ++AI)
- Candidates.reset(*AI);
- }
- }
-
- if (I == To) {
- // If one of the available registers survived this long take it.
- Available &= Candidates;
- int Reg = Available.find_first();
- if (Reg != -1)
- return std::make_pair(Reg, MBB.end());
- // Otherwise we will continue up to InstrLimit instructions to fine
- // the register which is not defined/used for the longest time.
- FoundTo = true;
- Pos = To;
- }
- if (FoundTo) {
- if (Survivor == 0 || !Candidates.test(Survivor)) {
- int Reg = Candidates.find_first();
- if (Reg == -1)
- break;
- Survivor = Reg;
- }
- if (--InstrCountDown == 0 || I == MBB.begin())
- break;
- if (FoundVReg) {
- // We found a vreg, reset the InstrLimit counter.
- InstrCountDown = InstrLimit;
- Pos = I;
- }
- }
- --I;
- }
-
- return std::make_pair(Survivor, Pos);
-}
-
static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
unsigned i = 0;
while (!MI.getOperand(i).isFI()) {
@@ -481,16 +407,43 @@ static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
return i;
}
-RegScavenger::ScavengedInfo &
-RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
- MachineBasicBlock::iterator Before,
- MachineBasicBlock::iterator &UseMI) {
+unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
+ MachineBasicBlock::iterator I,
+ int SPAdj) {
+ MachineInstr &MI = *I;
+ const MachineFunction &MF = *MI.getParent()->getParent();
+ // Consider all allocatable registers in the register class initially
+ BitVector Candidates = TRI->getAllocatableSet(MF, RC);
+
+ // Exclude all the registers being used by the instruction.
+ for (const MachineOperand &MO : MI.operands()) {
+ if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
+ !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
+ Candidates.reset(MO.getReg());
+ }
+
+ // Try to find a register that's unused if there is one, as then we won't
+ // have to spill.
+ BitVector Available = getRegsAvailable(RC);
+ Available &= Candidates;
+ if (Available.any())
+ Candidates = Available;
+
+ // Find the register whose use is furthest away.
+ MachineBasicBlock::iterator UseMI;
+ unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
+
+ // If we found an unused register there is no reason to spill it.
+ if (!isRegUsed(SReg)) {
+ DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
+ return SReg;
+ }
+
// Find an available scavenging slot with size and alignment matching
// the requirements of the class RC.
- const MachineFunction &MF = *Before->getParent()->getParent();
const MachineFrameInfo &MFI = *MF.getFrameInfo();
- unsigned NeedSize = RC.getSize();
- unsigned NeedAlign = RC.getAlignment();
+ unsigned NeedSize = RC->getSize();
+ unsigned NeedAlign = RC->getAlignment();
unsigned SI = Scavenged.size(), Diff = UINT_MAX;
int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
@@ -525,108 +478,42 @@ RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
}
// Avoid infinite regress
- Scavenged[SI].Reg = Reg;
+ Scavenged[SI].Reg = SReg;
// If the target knows how to save/restore the register, let it do so;
// otherwise, use the emergency stack spill slot.
- if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
- // Spill the scavenged register before \p Before.
+ if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
+ // Spill the scavenged register before I.
int FI = Scavenged[SI].FrameIndex;
if (FI < FIB || FI >= FIE) {
std::string Msg = std::string("Error while trying to spill ") +
- TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) +
+ TRI->getName(SReg) + " from class " + TRI->getRegClassName(RC) +
": Cannot scavenge register without an emergency spill slot!";
report_fatal_error(Msg.c_str());
}
- TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex,
- &RC, TRI);
- MachineBasicBlock::iterator II = std::prev(Before);
+ TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
+ RC, TRI);
+ MachineBasicBlock::iterator II = std::prev(I);
unsigned FIOperandNum = getFrameIndexOperandNum(*II);
TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
// Restore the scavenged register before its use (or first terminator).
- TII->loadRegFromStackSlot(*MBB, UseMI, Reg, Scavenged[SI].FrameIndex,
- &RC, TRI);
+ TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
+ RC, TRI);
II = std::prev(UseMI);
FIOperandNum = getFrameIndexOperandNum(*II);
TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
}
- return Scavenged[SI];
-}
-
-unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
- MachineBasicBlock::iterator I,
- int SPAdj) {
- MachineInstr &MI = *I;
- const MachineFunction &MF = *MI.getParent()->getParent();
- // Consider all allocatable registers in the register class initially
- BitVector Candidates = TRI->getAllocatableSet(MF, RC);
-
- // Exclude all the registers being used by the instruction.
- for (const MachineOperand &MO : MI.operands()) {
- if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
- !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
- Candidates.reset(MO.getReg());
- }
-
- // Try to find a register that's unused if there is one, as then we won't
- // have to spill.
- BitVector Available = getRegsAvailable(RC);
- Available &= Candidates;
- if (Available.any())
- Candidates = Available;
-
- // Find the register whose use is furthest away.
- MachineBasicBlock::iterator UseMI;
- unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
- // If we found an unused register there is no reason to spill it.
- if (!isRegUsed(SReg)) {
- DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
- return SReg;
- }
+ Scavenged[SI].Restore = &*std::prev(UseMI);
- ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
- Scavenged.Restore = std::prev(UseMI);
+ // Doing this here leads to infinite regress.
+ // Scavenged[SI].Reg = SReg;
DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
"\n");
return SReg;
}
-
-unsigned RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
- MachineBasicBlock::iterator To,
- bool RestoreAfter, int SPAdj) {
- const MachineBasicBlock &MBB = *To->getParent();
- const MachineFunction &MF = *MBB.getParent();
- // Consider all allocatable registers in the register class initially
- BitVector Candidates = TRI->getAllocatableSet(MF, &RC);
-
- // Try to find a register that's unused if there is one, as then we won't
- // have to spill.
- BitVector Available = getRegsAvailable(&RC);
-
- // Find the register whose use is furthest away.
- MachineBasicBlock::iterator UseMI;
- std::pair<unsigned, MachineBasicBlock::iterator> P =
- findSurvivorBackwards(*TRI, MBBI, To, Available, Candidates);
- unsigned Reg = P.first;
- assert(Reg != 0 && "No register left to scavenge!");
- // Found an available register?
- if (!Available.test(Reg)) {
- MachineBasicBlock::iterator ReloadBefore =
- RestoreAfter ? std::next(MBBI) : MBBI;
- DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
- ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, P.second, ReloadBefore);
- Scavenged.Restore = std::prev(P.second);
- addRegUnits(RegUnitsAvailable, Reg);
- DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
- << " until " << *P.second);
- } else {
- DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
- }
- return Reg;
-}
OpenPOWER on IntegriCloud