From fdc4c6b426aa6492ce3ed175fc6180aec5964fce Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Fri, 19 Aug 2016 03:03:24 +0000 Subject: [PATCH] Revert "RegScavenging: Add scavengeRegisterBackwards()" The ppc64 multistage bot fails on this. This reverts commit r279124. Also Revert "CodeGen: Add/Factor out LiveRegUnits class; NFCI" because it depends on the previous change This reverts commit r279171. llvm-svn: 279199 --- llvm/include/llvm/CodeGen/LiveRegUnits.h | 116 --------- llvm/include/llvm/CodeGen/RegisterScavenging.h | 32 +-- llvm/lib/CodeGen/CMakeLists.txt | 1 - llvm/lib/CodeGen/LiveRegUnits.cpp | 97 -------- llvm/lib/CodeGen/PrologEpilogInserter.cpp | 147 +++++------- llvm/lib/CodeGen/RegisterScavenging.cpp | 267 ++++++++------------- llvm/test/CodeGen/AMDGPU/captured-frame-index.ll | 4 +- .../CodeGen/Mips/emergency-spill-slot-near-fp.ll | 88 +++---- llvm/test/CodeGen/PowerPC/dyn-alloca-aligned.ll | 4 +- llvm/test/CodeGen/Thumb/large-stack.ll | 4 +- 10 files changed, 209 insertions(+), 551 deletions(-) delete mode 100644 llvm/include/llvm/CodeGen/LiveRegUnits.h delete mode 100644 llvm/lib/CodeGen/LiveRegUnits.cpp diff --git a/llvm/include/llvm/CodeGen/LiveRegUnits.h b/llvm/include/llvm/CodeGen/LiveRegUnits.h deleted file mode 100644 index b6bb8c6..0000000 --- a/llvm/include/llvm/CodeGen/LiveRegUnits.h +++ /dev/null @@ -1,116 +0,0 @@ -//===- llvm/CodeGen/LiveRegUnits.h - Register Unit Set ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -/// \file -/// A set of register units. It is intended for register liveness tracking. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_LIVEREGUNITS_H -#define LLVM_CODEGEN_LIVEREGUNITS_H - -#include "llvm/ADT/BitVector.h" -#include "llvm/Target/TargetRegisterInfo.h" - -namespace llvm { - -class MachineInstr; -class MachineBasicBlock; - -/// A set of register units used to track register liveness. -class LiveRegUnits { - const TargetRegisterInfo *TRI; - BitVector Units; - -public: - /// Constructs a new empty LiveRegUnits set. - LiveRegUnits() : TRI(nullptr) {} - - /// Constructs and initialize an empty LiveRegUnits set. - LiveRegUnits(const TargetRegisterInfo &TRI) { - init(TRI); - } - - /// Initialize and clear the set. - void init(const TargetRegisterInfo &TRI) { - this->TRI = &TRI; - Units.reset(); - Units.resize(TRI.getNumRegUnits()); - } - - /// Clears the set. - void clear() { Units.reset(); } - - /// Returns true if the set is empty. - bool empty() const { return Units.empty(); } - - /// Adds register units covered by physical register \p Reg. - void addReg(unsigned Reg) { - for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) - Units.set(*Unit); - } - - /// \brief Adds register units covered by physical register \p Reg that are - /// part of the lanemask \p Mask. - void addRegMasked(unsigned Reg, LaneBitmask Mask) { - for (MCRegUnitMaskIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { - LaneBitmask UnitMask = (*Unit).second; - if (UnitMask == 0 || (UnitMask & Mask) != 0) - Units.set((*Unit).first); - } - } - - /// Removes all register units covered by physical register \p Reg. - void removeReg(unsigned Reg) { - for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) - Units.reset(*Unit); - } - - /// Removes register units not preserved by the regmask \p RegMask. - /// The regmask has the same format as the one in the RegMask machine operand. - void removeRegsNotPreserved(const uint32_t *RegMask); - - /// Returns true if no part of physical register \p Reg is live. - bool available(unsigned Reg) const { - for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) { - if (Units.test(*Unit)) - return false; - } - return true; - } - - /// Updates liveness when stepping backwards over the instruction \p MI. - void stepBackward(const MachineInstr &MI); - - /// Adds registers living out of block \p MBB. - /// Live out registers are the union of the live-in registers of the successor - /// blocks and pristine registers. Live out registers of the end block are the - /// callee saved registers. - void addLiveOuts(const MachineBasicBlock &MBB); - - /// Adds registers living into block \p MBB. - void addLiveIns(const MachineBasicBlock &MBB); - - /// Adds all register units marked in the bitvector \p RegUnits. - void addUnits(const BitVector &RegUnits) { - Units |= RegUnits; - } - /// Removes all register units marked in the bitvector \p RegUnits. - void removeUnits(const BitVector &RegUnits) { - Units.reset(RegUnits); - } - /// Return the internal bitvector representation of the set. - const BitVector &getBitVector() const { - return Units; - } -}; - -} // namespace llvm - -#endif diff --git a/llvm/include/llvm/CodeGen/RegisterScavenging.h b/llvm/include/llvm/CodeGen/RegisterScavenging.h index 0b131a4..efaba17 100644 --- a/llvm/include/llvm/CodeGen/RegisterScavenging.h +++ b/llvm/include/llvm/CodeGen/RegisterScavenging.h @@ -19,7 +19,6 @@ #define LLVM_CODEGEN_REGISTERSCAVENGING_H #include "llvm/ADT/BitVector.h" -#include "llvm/CodeGen/LiveRegUnits.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineRegisterInfo.h" @@ -59,7 +58,10 @@ class RegScavenger { /// A vector of information on scavenged registers. SmallVector Scavenged; - LiveRegUnits LiveUnits; + /// The current state of each reg unit immediately before MBBI. + /// One bit per register unit. If bit is not set it means any + /// register containing that register unit is currently being used. + BitVector RegUnitsAvailable; // These BitVectors are only used internally to forward(). They are members // to avoid frequent reallocations. @@ -155,24 +157,12 @@ public: /// available and do the appropriate bookkeeping. SPAdj is the stack /// adjustment due to call frame, it's passed along to eliminateFrameIndex(). /// Returns the scavenged register. - /// This function performs worse if kill flags are incomplete, consider using - /// scavengeRegisterBackwards() instead! unsigned scavengeRegister(const TargetRegisterClass *RegClass, MachineBasicBlock::iterator I, int SPAdj); unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) { return scavengeRegister(RegClass, MBBI, SPAdj); } - /// Make a register of the specific register class available from the current - /// position backwards to the place before \p To. If \p RestoreAfter is true - /// this includes the instruction following the current position. - /// SPAdj is the stack adjustment due to call frame, it's passed along to - /// eliminateFrameIndex(). - /// Returns the scavenged register. - unsigned scavengeRegisterBackwards(const TargetRegisterClass &RC, - MachineBasicBlock::iterator To, - bool RestoreAfter, int SPAdj); - /// Tell the scavenger a register is used. void setRegUsed(unsigned Reg, LaneBitmask LaneMask = ~0u); private: @@ -181,11 +171,11 @@ private: /// setUsed / setUnused - Mark the state of one or a number of register units. /// - void setUsed(const BitVector &RegUnits) { - LiveUnits.addUnits(RegUnits); + void setUsed(BitVector &RegUnits) { + RegUnitsAvailable.reset(RegUnits); } - void setUnused(const BitVector &RegUnits) { - LiveUnits.removeUnits(RegUnits); + void setUnused(BitVector &RegUnits) { + RegUnitsAvailable |= RegUnits; } /// Processes the current instruction and fill the KillRegUnits and @@ -212,12 +202,6 @@ private: /// Mark live-in registers of basic block as used. void setLiveInsUsed(const MachineBasicBlock &MBB); - - /// Spill a register after position \p After and reload it before position - /// \p UseMI. - ScavengedInfo &spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj, - MachineBasicBlock::iterator After, - MachineBasicBlock::iterator &UseMI); }; } // End llvm namespace diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt index 7d390d8..f522435 100644 --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -44,7 +44,6 @@ add_llvm_library(LLVMCodeGen LiveRangeCalc.cpp LiveRangeEdit.cpp LiveRegMatrix.cpp - LiveRegUnits.cpp LiveStackAnalysis.cpp LiveVariables.cpp LLVMTargetMachine.cpp diff --git a/llvm/lib/CodeGen/LiveRegUnits.cpp b/llvm/lib/CodeGen/LiveRegUnits.cpp deleted file mode 100644 index 14da799..0000000 --- a/llvm/lib/CodeGen/LiveRegUnits.cpp +++ /dev/null @@ -1,97 +0,0 @@ -//===--- LiveRegUnits.cpp - Register Unit Set -----------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -/// \file This file imlements the LiveRegUnits set. -// -//===----------------------------------------------------------------------===// - -#include "llvm/CodeGen/LiveRegUnits.h" -#include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineInstrBundle.h" -using namespace llvm; - -void LiveRegUnits::removeRegsNotPreserved(const uint32_t *RegMask) { - for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) { - for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) { - if (MachineOperand::clobbersPhysReg(RegMask, *RootReg)) - Units.reset(U); - } - } -} - -void LiveRegUnits::stepBackward(const MachineInstr &MI) { - // Remove defined registers and regmask kills from the set. - for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { - if (O->isReg()) { - if (!O->isDef()) - continue; - unsigned Reg = O->getReg(); - if (!TargetRegisterInfo::isPhysicalRegister(Reg)) - continue; - removeReg(Reg); - } else if (O->isRegMask()) - removeRegsNotPreserved(O->getRegMask()); - } - - // Add uses to the set. - for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { - if (!O->isReg() || !O->readsReg()) - continue; - unsigned Reg = O->getReg(); - if (!TargetRegisterInfo::isPhysicalRegister(Reg)) - continue; - addReg(Reg); - } -} - -/// Add live-in registers of basic block \p MBB to \p LiveUnits. -static void addLiveIns(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) { - for (const auto &LI : MBB.liveins()) - LiveUnits.addRegMasked(LI.PhysReg, LI.LaneMask); -} - -static void addLiveOuts(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) { - // To get the live-outs we simply merge the live-ins of all successors. - for (const MachineBasicBlock *Succ : MBB.successors()) - addLiveIns(LiveUnits, *Succ); -} - -/// Add pristine registers to the given \p LiveUnits. This function removes -/// actually saved callee save registers when \p InPrologueEpilogue is false. -static void removeSavedRegs(LiveRegUnits &LiveUnits, const MachineFunction &MF, - const MachineFrameInfo &MFI, - const TargetRegisterInfo &TRI) { - for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) - LiveUnits.removeReg(Info.getReg()); -} - -void LiveRegUnits::addLiveOuts(const MachineBasicBlock &MBB) { - const MachineFunction &MF = *MBB.getParent(); - const MachineFrameInfo &MFI = MF.getFrameInfo(); - if (MFI.isCalleeSavedInfoValid()) { - for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) - addReg(*I); - if (!MBB.isReturnBlock()) - removeSavedRegs(*this, MF, MFI, *TRI); - } - ::addLiveOuts(*this, MBB); -} - -void LiveRegUnits::addLiveIns(const MachineBasicBlock &MBB) { - const MachineFunction &MF = *MBB.getParent(); - const MachineFrameInfo &MFI = MF.getFrameInfo(); - if (MFI.isCalleeSavedInfoValid()) { - for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) - addReg(*I); - if (&MBB != &MF.front()) - removeSavedRegs(*this, MF, MFI, *TRI); - } - ::addLiveIns(*this, MBB); -} diff --git a/llvm/lib/CodeGen/PrologEpilogInserter.cpp b/llvm/lib/CodeGen/PrologEpilogInserter.cpp index 7faf245..a167b3d 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 #include using namespace llvm; @@ -1146,55 +1145,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. @@ -1206,51 +1156,78 @@ static void doScavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger *RS) { // Run through the instructions and find any virtual registers. MachineRegisterInfo &MRI = MF.getRegInfo(); - const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); 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). - if (LastIterationHadVRegUses) { - MachineBasicBlock::iterator N = std::next(I); - 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); - N->addRegisterKilled(SReg, &TRI, false); - 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()) { - unsigned SReg = scavengeVReg(MRI, *RS, Reg, false); - I->addRegisterDead(SReg, &TRI, 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 cd088c7..953e535 100644 --- a/llvm/lib/CodeGen/RegisterScavenging.cpp +++ b/llvm/lib/CodeGen/RegisterScavenging.cpp @@ -32,7 +32,11 @@ using namespace llvm; #define DEBUG_TYPE "reg-scavenging" void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) { - LiveUnits.addRegMasked(Reg, LaneMask); + for (MCRegUnitMaskIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) { + LaneBitmask UnitMask = (*RUI).second; + if (UnitMask == 0 || (LaneMask & UnitMask) != 0) + RegUnitsAvailable.reset((*RUI).first); + } } void RegScavenger::init(MachineBasicBlock &MBB) { @@ -40,7 +44,6 @@ void RegScavenger::init(MachineBasicBlock &MBB) { TII = MF.getSubtarget().getInstrInfo(); TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); - LiveUnits.init(*TRI); assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) && "Target changed?"); @@ -53,6 +56,7 @@ void RegScavenger::init(MachineBasicBlock &MBB) { // Self-initialize. if (!this->MBB) { NumRegUnits = TRI->getNumRegUnits(); + RegUnitsAvailable.resize(NumRegUnits); KillRegUnits.resize(NumRegUnits); DefRegUnits.resize(NumRegUnits); TmpRegUnits.resize(NumRegUnits); @@ -65,17 +69,32 @@ void RegScavenger::init(MachineBasicBlock &MBB) { I->Restore = nullptr; } + // All register units start out unused. + RegUnitsAvailable.set(); + + // Pristine CSRs are not available. + BitVector PR = MF.getFrameInfo().getPristineRegs(MF); + for (int I = PR.find_first(); I>0; I = PR.find_next(I)) + setRegUsed(I); + Tracking = false; } +void RegScavenger::setLiveInsUsed(const MachineBasicBlock &MBB) { + for (const auto &LI : MBB.liveins()) + setRegUsed(LI.PhysReg, LI.LaneMask); +} + void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) { init(MBB); - LiveUnits.addLiveIns(MBB); + setLiveInsUsed(MBB); } void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) { init(MBB); - LiveUnits.addLiveOuts(MBB); + // Merge live-ins of successors to get live-outs. + for (const MachineBasicBlock *Succ : MBB.successors()) + setLiveInsUsed(*Succ); // Move internal iterator at the last instruction of the block. if (MBB.begin() != MBB.end()) { @@ -249,13 +268,34 @@ void RegScavenger::backward() { assert(Tracking && "Must be tracking to determine kills and defs"); const MachineInstr &MI = *MBBI; - LiveUnits.stepBackward(MI); - - // Expire scavenge spill frameindex uses. - for (ScavengedInfo &I : Scavenged) { - if (I.Restore == &MI) { - I.Reg = 0; - I.Restore = nullptr; + // Defined or clobbered registers are available now. + for (const MachineOperand &MO : MI.operands()) { + if (MO.isRegMask()) { + for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; + ++RU) { + for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) { + if (MO.clobbersPhysReg(*RURI)) { + RegUnitsAvailable.set(RU); + break; + } + } + } + } else if (MO.isReg() && MO.isDef()) { + unsigned Reg = MO.getReg(); + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || + isReserved(Reg)) + continue; + addRegUnits(RegUnitsAvailable, Reg); + } + } + // Mark read registers as unavailable. + for (const MachineOperand &MO : MI.uses()) { + if (MO.isReg() && MO.readsReg()) { + unsigned Reg = MO.getReg(); + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || + isReserved(Reg)) + continue; + removeRegUnits(RegUnitsAvailable, Reg); } } @@ -267,9 +307,12 @@ void RegScavenger::backward() { } bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const { - if (isReserved(Reg)) - return includeReserved; - return !LiveUnits.available(Reg); + if (includeReserved && isReserved(Reg)) + return true; + for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) + if (!RegUnitsAvailable.test(*RUI)) + return true; + return false; } unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { @@ -355,69 +398,6 @@ unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, return Survivor; } -static std::pair -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(); - unsigned InstrLimit = 25; - unsigned InstrCountDown = InstrLimit; - for (MachineBasicBlock::iterator I = From;; --I) { - const MachineInstr &MI = *I; - - // 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() || MO.isDebug()) - 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 find - // 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) { - // Keep searching when we find a vreg since the spilled register will - // be usefull for this other vreg as well later. - InstrCountDown = InstrLimit; - Pos = I; - } - } - } - - return std::make_pair(Survivor, Pos); -} - static unsigned getFrameIndexOperandNum(MachineInstr &MI) { unsigned i = 0; while (!MI.getOperand(i).isFI()) { @@ -427,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(); @@ -471,110 +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); + Scavenged[SI].Restore = &*std::prev(UseMI); - // 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; - } - - 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 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 ReloadAfter = - RestoreAfter ? std::next(MBBI) : MBBI; - MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter); - DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n'); - MachineBasicBlock::iterator SpillBefore = P.second; - ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore); - Scavenged.Restore = &*std::prev(SpillBefore); - LiveUnits.removeReg(Reg); - DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI) - << " until " << *SpillBefore); - } else { - DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n'); - } - return Reg; -} diff --git a/llvm/test/CodeGen/AMDGPU/captured-frame-index.ll b/llvm/test/CodeGen/AMDGPU/captured-frame-index.ll index bf6e48d..161c46b 100644 --- a/llvm/test/CodeGen/AMDGPU/captured-frame-index.ll +++ b/llvm/test/CodeGen/AMDGPU/captured-frame-index.ll @@ -140,8 +140,8 @@ define void @stored_fi_to_global_2_small_objects(float* addrspace(1)* %ptr) #0 { } ; GCN-LABEL: {{^}}stored_fi_to_global_huge_frame_offset: -; GCN-DAG: s_add_i32 [[BASE_1_OFF_0:s[0-9]+]], 0, 0x3ffc -; GCN-DAG: v_mov_b32_e32 [[BASE_0:v[0-9]+]], 0{{$}} +; GCN: s_add_i32 [[BASE_1_OFF_0:s[0-9]+]], 0, 0x3ffc +; GCN: v_mov_b32_e32 [[BASE_0:v[0-9]+]], 0{{$}} ; GCN: buffer_store_dword [[BASE_0]], v{{[0-9]+}}, s{{\[[0-9]+:[0-9]+\]}}, s{{[0-9]+}} offen ; GCN: v_mov_b32_e32 [[V_BASE_1_OFF_0:v[0-9]+]], [[BASE_1_OFF_0]] diff --git a/llvm/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll b/llvm/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll index 625abc1..a08b681 100644 --- a/llvm/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll +++ b/llvm/test/CodeGen/Mips/emergency-spill-slot-near-fp.ll @@ -1,62 +1,34 @@ -; RUN: llc -march=mipsel -O0 -relocation-model=pic < %s | FileCheck %s ; Check that register scavenging spill slot is close to $fp. -target triple="mipsel--" - -@var = external global i32 -@ptrvar = external global i8* - -; CHECK-LABEL: func: -define void @func() { - %space = alloca i32, align 4 - %stackspace = alloca[16384 x i32], align 4 - - ; ensure stackspace is not optimized out - %stackspace_casted = bitcast [16384 x i32]* %stackspace to i8* - store volatile i8* %stackspace_casted, i8** @ptrvar - - ; Load values to increase register pressure. - %v0 = load volatile i32, i32* @var - %v1 = load volatile i32, i32* @var - %v2 = load volatile i32, i32* @var - %v3 = load volatile i32, i32* @var - %v4 = load volatile i32, i32* @var - %v5 = load volatile i32, i32* @var - %v6 = load volatile i32, i32* @var - %v7 = load volatile i32, i32* @var - %v8 = load volatile i32, i32* @var - %v9 = load volatile i32, i32* @var - %v10 = load volatile i32, i32* @var - %v11 = load volatile i32, i32* @var - %v12 = load volatile i32, i32* @var - %v13 = load volatile i32, i32* @var - %v14 = load volatile i32, i32* @var - %v15 = load volatile i32, i32* @var - %v16 = load volatile i32, i32* @var - - ; Computing a stack-relative values needs an additional register. - ; We should get an emergency spill/reload for this. - ; CHECK: sw ${{.*}}, 0($sp) - ; CHECK: lw ${{.*}}, 0($sp) - store volatile i32 %v0, i32* %space +; RUN: llc -march=mipsel -O0 -relocation-model=pic < %s | FileCheck %s - ; store values so they are used. - store volatile i32 %v0, i32* @var - store volatile i32 %v1, i32* @var - store volatile i32 %v2, i32* @var - store volatile i32 %v3, i32* @var - store volatile i32 %v4, i32* @var - store volatile i32 %v5, i32* @var - store volatile i32 %v6, i32* @var - store volatile i32 %v7, i32* @var - store volatile i32 %v8, i32* @var - store volatile i32 %v9, i32* @var - store volatile i32 %v10, i32* @var - store volatile i32 %v11, i32* @var - store volatile i32 %v12, i32* @var - store volatile i32 %v13, i32* @var - store volatile i32 %v14, i32* @var - store volatile i32 %v15, i32* @var - store volatile i32 %v16, i32* @var +; CHECK: sw ${{.*}}, 8($sp) +; CHECK: lw ${{.*}}, 8($sp) - ret void +define i32 @main(i32 signext %argc, i8** %argv) #0 { +entry: + %retval = alloca i32, align 4 + %argc.addr = alloca i32, align 4 + %argv.addr = alloca i8**, align 4 + %v0 = alloca <16 x i8>, align 16 + %.compoundliteral = alloca <16 x i8>, align 16 + %v1 = alloca <16 x i8>, align 16 + %.compoundliteral1 = alloca <16 x i8>, align 16 + %unused_variable = alloca [16384 x i32], align 4 + %result = alloca <16 x i8>, align 16 + store i32 0, i32* %retval + store i32 %argc, i32* %argc.addr, align 4 + store i8** %argv, i8*** %argv.addr, align 4 + store <16 x i8> , <16 x i8>* %.compoundliteral + %0 = load <16 x i8>, <16 x i8>* %.compoundliteral + store <16 x i8> %0, <16 x i8>* %v0, align 16 + store <16 x i8> zeroinitializer, <16 x i8>* %.compoundliteral1 + %1 = load <16 x i8>, <16 x i8>* %.compoundliteral1 + store <16 x i8> %1, <16 x i8>* %v1, align 16 + %2 = load <16 x i8>, <16 x i8>* %v0, align 16 + %3 = load <16 x i8>, <16 x i8>* %v1, align 16 + %mul = mul <16 x i8> %2, %3 + store <16 x i8> %mul, <16 x i8>* %result, align 16 + ret i32 0 } + +attributes #0 = { noinline "no-frame-pointer-elim"="true" } diff --git a/llvm/test/CodeGen/PowerPC/dyn-alloca-aligned.ll b/llvm/test/CodeGen/PowerPC/dyn-alloca-aligned.ll index e0f2847..0de2e22 100644 --- a/llvm/test/CodeGen/PowerPC/dyn-alloca-aligned.ll +++ b/llvm/test/CodeGen/PowerPC/dyn-alloca-aligned.ll @@ -25,8 +25,8 @@ entry: ; CHECK-DAG: li [[REG1:[0-9]+]], -128 ; CHECK-DAG: neg [[REG2:[0-9]+]], -; CHECK: and [[REG3:[0-9]+]], [[REG2]], [[REG1]] -; CHECK: stdux {{[0-9]+}}, 1, [[REG3]] +; CHECK: and [[REG1]], [[REG2]], [[REG1]] +; CHECK: stdux {{[0-9]+}}, 1, [[REG1]] ; CHECK: blr diff --git a/llvm/test/CodeGen/Thumb/large-stack.ll b/llvm/test/CodeGen/Thumb/large-stack.ll index c72a67c..c5d1044 100644 --- a/llvm/test/CodeGen/Thumb/large-stack.ll +++ b/llvm/test/CodeGen/Thumb/large-stack.ll @@ -46,8 +46,8 @@ define i32 @test3() { ; CHECK-LABEL: test3: ; CHECK: ldr [[TEMP:r[0-7]]], ; CHECK: add sp, [[TEMP]] -; CHECK: ldr [[TEMP2:r[0-7]]], -; CHECK: add [[TEMP2]], sp +; CHECK: ldr [[TEMP]], +; CHECK: add [[TEMP]], sp ; EABI: ldr [[TEMP:r[0-7]]], ; EABI: add sp, [[TEMP]] ; IOS: subs r4, r7, #4 -- 2.7.4