From 4e05788cc3d75a8b413aaa629ba813ce38d288a1 Mon Sep 17 00:00:00 2001 From: Hal Finkel Date: Tue, 26 Mar 2013 18:56:54 +0000 Subject: [PATCH] Update PEI's virtual-register-based scavenging to support multiple simultaneous mappings The previous algorithm could not deal properly with scavenging multiple virtual registers because it kept only one live virtual -> physical mapping (and iterated through operands in order). Now we don't maintain a current mapping, but rather use replaceRegWith to completely remove the virtual register as soon as the mapping is established. In order to allow the register scavenger to return a physical register killed by an instruction for definition by that same instruction, we now call RS->forward(I) prior to eliminating virtual registers defined in I. This requires a minor update to forward to ignore virtual registers. These new features will be tested in forthcoming commits. llvm-svn: 178058 --- llvm/include/llvm/CodeGen/RegisterScavenging.h | 7 +++- llvm/lib/CodeGen/PrologEpilogInserter.cpp | 53 ++++++++++++++++---------- llvm/lib/CodeGen/RegisterScavenging.cpp | 4 +- llvm/test/CodeGen/AArch64/alloca.ll | 6 +-- 4 files changed, 43 insertions(+), 27 deletions(-) diff --git a/llvm/include/llvm/CodeGen/RegisterScavenging.h b/llvm/include/llvm/CodeGen/RegisterScavenging.h index babb96b..0eb2b2a 100644 --- a/llvm/include/llvm/CodeGen/RegisterScavenging.h +++ b/llvm/include/llvm/CodeGen/RegisterScavenging.h @@ -94,8 +94,11 @@ public: } /// skipTo - Move the internal MBB iterator but do not update register states. - /// - void skipTo(MachineBasicBlock::iterator I) { MBBI = I; } + void skipTo(MachineBasicBlock::iterator I) { + if (I == MachineBasicBlock::iterator(NULL)) + Tracking = false; + MBBI = I; + } /// getRegsUsed - return all registers currently in use in used. void getRegsUsed(BitVector &used, bool includeReserved); diff --git a/llvm/lib/CodeGen/PrologEpilogInserter.cpp b/llvm/lib/CodeGen/PrologEpilogInserter.cpp index 413ce91..5a168dd 100644 --- a/llvm/lib/CodeGen/PrologEpilogInserter.cpp +++ b/llvm/lib/CodeGen/PrologEpilogInserter.cpp @@ -55,7 +55,6 @@ INITIALIZE_PASS_END(PEI, "prologepilog", "Prologue/Epilogue Insertion & Frame Finalization", false, false) -STATISTIC(NumVirtualFrameRegs, "Number of virtual frame regs encountered"); STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged"); STATISTIC(NumBytesStackSpace, "Number of bytes used for stack in all functions"); @@ -820,14 +819,20 @@ void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) { E = Fn.end(); BB != E; ++BB) { RS->enterBasicBlock(BB); - unsigned VirtReg = 0; - unsigned ScratchReg = 0; int SPAdj = 0; // The instruction stream may change in the loop, so check BB->end() // directly. for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { MachineInstr *MI = I; + MachineBasicBlock::iterator J = llvm::next(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 (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { if (MI->getOperand(i).isReg()) { MachineOperand &MO = MI->getOperand(i); @@ -837,29 +842,37 @@ void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) { if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; - ++NumVirtualFrameRegs; - - // Have we already allocated a scratch register for this virtual? - if (Reg != VirtReg) { - // When we first encounter a new virtual register, it - // must be a definition. - assert(MI->getOperand(i).isDef() && - "frame index virtual missing def!"); - // Scavenge a new scratch register - VirtReg = Reg; - const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg); - ScratchReg = RS->scavengeRegister(RC, I, SPAdj); - ++NumScavengedRegs; - } + // When we first encounter a new virtual register, it + // must be a definition. + assert(MI->getOperand(i).isDef() && + "frame index virtual missing def!"); + // Scavenge a new scratch register + const TargetRegisterClass *RC = Fn.getRegInfo().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!"); - MI->getOperand(i).setReg(ScratchReg); + Fn.getRegInfo().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->setUsed(ScratchReg); } } - RS->forward(I); - ++I; + + // 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 != llvm::prior(J)) { + BB->splice(J, BB, I++); + RS->skipTo(I == BB->begin() ? NULL : llvm::prior(I)); + } else + ++I; } } } diff --git a/llvm/lib/CodeGen/RegisterScavenging.cpp b/llvm/lib/CodeGen/RegisterScavenging.cpp index b54bf7d..4c85644 100644 --- a/llvm/lib/CodeGen/RegisterScavenging.cpp +++ b/llvm/lib/CodeGen/RegisterScavenging.cpp @@ -150,7 +150,7 @@ void RegScavenger::forward() { if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; if (MO.isUse()) { @@ -175,7 +175,7 @@ void RegScavenger::forward() { if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (!Reg || isReserved(Reg)) + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg)) continue; if (MO.isUse()) { if (MO.isUndef()) diff --git a/llvm/test/CodeGen/AArch64/alloca.ll b/llvm/test/CodeGen/AArch64/alloca.ll index 6421769..c62edf6 100644 --- a/llvm/test/CodeGen/AArch64/alloca.ll +++ b/llvm/test/CodeGen/AArch64/alloca.ll @@ -71,8 +71,8 @@ define void @test_variadic_alloca(i64 %n, ...) { ; CHECK: sub sp, sp, #208 ; CHECK: stp x29, x30, [sp, #192] ; CHECK: add x29, sp, #192 -; CHECK: sub x9, x29, #192 -; CHECK: add x8, x9, #0 +; CHECK: sub [[TMP:x[0-9]+]], x29, #192 +; CHECK: add x8, [[TMP]], #0 ; CHECK: str q7, [x8, #112] ; [...] ; CHECK: str q1, [x8, #16] @@ -131,4 +131,4 @@ define void @test_scoped_alloca(i64 %n) { ; CHECK: mov sp, [[SAVED_SP]] ret void -} \ No newline at end of file +} -- 2.7.4