Index: include/llvm/CodeGen/LiveRegUnits.h =================================================================== --- include/llvm/CodeGen/LiveRegUnits.h +++ include/llvm/CodeGen/LiveRegUnits.h @@ -76,6 +76,10 @@ /// The regmask has the same format as the one in the RegMask machine operand. void removeRegsInMask(const uint32_t *RegMask); + /// Adds register units not preserved by the regmask \p RegMask. + /// The regmask has the same format as the one in the RegMask machine operand. + void addRegsInMask(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) { @@ -88,6 +92,11 @@ /// Updates liveness when stepping backwards over the instruction \p MI. void stepBackward(const MachineInstr &MI); + /// Mark all register units live during instruction \p MI. + /// This can be used to accumulate live/unoccupied registers over a range of + /// instructions. + void accumulateBackward(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 Index: lib/CodeGen/LiveRegUnits.cpp =================================================================== --- lib/CodeGen/LiveRegUnits.cpp +++ lib/CodeGen/LiveRegUnits.cpp @@ -26,6 +26,15 @@ } } +void LiveRegUnits::addRegsInMask(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.set(U); + } + } +} + void LiveRegUnits::stepBackward(const MachineInstr &MI) { // Remove defined registers and regmask kills from the set. for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { @@ -51,6 +60,21 @@ } } +void LiveRegUnits::accumulateBackward(const MachineInstr &MI) { + // Add defs, uses and regmask clobbers to the set. + for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { + if (O->isReg()) { + unsigned Reg = O->getReg(); + if (!TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + if (!O->isDef() && !O->readsReg()) + continue; + addReg(Reg); + } else if (O->isRegMask()) + addRegsInMask(O->getRegMask()); + } +} + /// 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()) Index: lib/CodeGen/RegisterScavenging.cpp =================================================================== --- lib/CodeGen/RegisterScavenging.cpp +++ lib/CodeGen/RegisterScavenging.cpp @@ -355,10 +355,16 @@ return Survivor; } +/// Searches backwards for a register usable between \p From and \To. +/// - If there exists a free register that is not part of \p LiveOut, then +/// make_pair(Reg, MBB.end()) will be returned. +/// - Otherwise we continue searching backwards for a register that is unused +/// for the longest time. In this case make_pair(Reg, earliest use) is +/// returned. static std::pair -findSurvivorBackwards(const TargetRegisterInfo &TRI, +findSurvivorBackwards(const MachineRegisterInfo &MRI, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, - BitVector &Available, BitVector &Candidates) { + const LiveRegUnits &LiveOut, const TargetRegisterClass &RC) { bool FoundTo = false; unsigned Survivor = 0; MachineBasicBlock::iterator Pos; @@ -366,49 +372,53 @@ MachineBasicBlock::iterator I = From; unsigned InstrLimit = 25; unsigned InstrCountDown = InstrLimit; + const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); + LiveRegUnits Live(TRI); + 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); - } - } + Live.accumulateBackward(MI); 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. + // See if there is a register that was not live so far. + for (unsigned Reg : RC) { + if (!MRI.isReserved(Reg) && Live.available(Reg) && + LiveOut.available(Reg)) + 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) + if (Survivor == 0 || !Live.available(Survivor)) { + unsigned AvailableReg = 0; + for (unsigned Reg : RC) { + if (!MRI.isReserved(Reg) && Live.available(Reg)) { + AvailableReg = Reg; + break; + } + } + if (AvailableReg == 0) break; - Survivor = Reg; + Survivor = AvailableReg; } if (--InstrCountDown == 0 || I == MBB.begin()) break; + + // Keep going if we find another vreg, as we need to scavenge that later + // anyway and we may be lucky by scavenge this one register for both. + bool FoundVReg = false; + for (const MachineOperand &MO : MI.operands()) { + if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + FoundVReg = true; + break; + } + } if (FoundVReg) { // We found a vreg, reset the InstrLimit counter. InstrCountDown = InstrLimit; @@ -551,32 +561,25 @@ 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); + findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, RC); 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; + MachineBasicBlock::iterator SpillAfter = P.second; + if (Reg == 0) { + llvm_unreachable("No register left to scavenge!"); + } else if (MBB.end() == SpillAfter) { + DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n'); + } else { + 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); + ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillAfter, ReloadBefore); + Scavenged.Restore = std::prev(SpillAfter); LiveUnits.removeReg(Reg); DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI) - << " until " << *P.second); - } else { - DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n'); + << " until " << *SpillAfter); } return Reg; } Index: lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp =================================================================== --- lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp +++ lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp @@ -496,44 +496,29 @@ int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB) { - RegScavenger RS; - RS.enterBasicBlock(MBB); - RS.forward(MachineBasicBlock::iterator(G->getStart())); - // Can we find an appropriate register that is available throughout the life - // of the chain? - unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass; - BitVector AvailableRegs = RS.getRegsAvailable(TRI->getRegClass(RegClassID)); - for (MachineBasicBlock::iterator I = G->getStart(), E = G->getEnd(); - I != E; ++I) { - RS.forward(I); - AvailableRegs &= RS.getRegsAvailable(TRI->getRegClass(RegClassID)); - - // Remove any registers clobbered by a regmask or any def register that is - // immediately dead. - for (auto J : I->operands()) { - if (J.isRegMask()) - AvailableRegs.clearBitsNotInMask(J.getRegMask()); - - if (J.isReg() && J.isDef()) { - MCRegAliasIterator AI(J.getReg(), TRI, /*IncludeSelf=*/true); - if (J.isDead()) - for (; AI.isValid(); ++AI) - AvailableRegs.reset(*AI); -#ifndef NDEBUG - else - for (; AI.isValid(); ++AI) - assert(!AvailableRegs[*AI] && - "Non-dead def should have been removed by now!"); -#endif - } - } - } + // of the chain? Simulate liveness backwards until the end of the chain. + LiveRegUnits Units(*TRI); + Units.addLiveOuts(MBB); + MachineBasicBlock::iterator I = MBB.end(), ChainEnd = G->getEnd(); + do { + --I; + Units.stepBackward(*I); + } while (I != ChainEnd); + + // Check which register units are alive throughout the chain. + MachineBasicBlock::iterator ChainBegin = G->getStart(); + assert(ChainBegin != ChainEnd && "Chain should contain instructions"); + do { + --I; + Units.accumulateBackward(*I); + } while (I != ChainBegin); // Make sure we allocate in-order, to get the cheapest registers first. + unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass; auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID)); for (auto Reg : Ord) { - if (!AvailableRegs[Reg]) + if (!Units.available(Reg)) continue; if (C == getColor(Reg)) return Reg; Index: test/CodeGen/PowerPC/2010-02-12-saveCR.ll =================================================================== --- test/CodeGen/PowerPC/2010-02-12-saveCR.ll +++ test/CodeGen/PowerPC/2010-02-12-saveCR.ll @@ -8,15 +8,15 @@ ; Note that part of what is being checked here is proper register reuse. ; CHECK: mfcr [[T1:r[0-9]+]] ; cr2 ; CHECK: lis [[T2:r[0-9]+]], 1 -; CHECK: addi r3, r1, 72 ; CHECK: rotlwi [[T1]], [[T1]], 8 ; CHECK: ori [[T2]], [[T2]], 34540 ; CHECK: stwx [[T1]], r1, [[T2]] -; CHECK: lis [[T3:r[0-9]+]], 1 ; CHECK: mfcr [[T4:r[0-9]+]] ; cr3 -; CHECK: ori [[T3]], [[T3]], 34536 +; CHECK: lis [[T3:r[0-9]+]], 1 ; CHECK: rotlwi [[T4]], [[T4]], 12 +; CHECK: ori [[T3]], [[T3]], 34536 ; CHECK: stwx [[T4]], r1, [[T3]] +; CHECK: addi r3, r1, 72 %x = alloca [100000 x i8] ; <[100000 x i8]*> [#uses=1] %"alloca point" = bitcast i32 0 to i32 ; [#uses=0] %x1 = bitcast [100000 x i8]* %x to i8* ; [#uses=1] Index: test/CodeGen/PowerPC/vsx-spill.ll =================================================================== --- test/CodeGen/PowerPC/vsx-spill.ll +++ test/CodeGen/PowerPC/vsx-spill.ll @@ -16,9 +16,9 @@ ; CHECK-REG: blr ; CHECK-FISL: @foo1 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65384 -; CHECK-FISL: stxsdx 1, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65384 +; CHECK-FISL: stxsdx 1, 1, [[REG2]] ; CHECK-FISL: blr return: ; preds = %entry @@ -38,8 +38,8 @@ ; CHECK-FISL: @foo2 ; CHECK-FISL: xsadddp [[R1:[0-9]+]], 1, 1 -; CHECK-FISL: stxsdx [[R1]], [[R1]], 0 -; CHECK-FISL: lxsdx [[R1]], [[R1]], 0 +; CHECK-FISL: stxsdx [[R1]], [[R1]], {{[0-9]+}} +; CHECK-FISL: lxsdx [[R1]], [[R1]], {{[0-9]+}} ; CHECK-FISL: blr return: ; preds = %entry Index: test/CodeGen/PowerPC/vsx.ll =================================================================== --- test/CodeGen/PowerPC/vsx.ll +++ test/CodeGen/PowerPC/vsx.ll @@ -265,9 +265,9 @@ ; CHECK-FISL: xxlor 0, 37, 36 ; CHECK-FISL: xxlnor 36, 37, 36 ; CHECK-FISL: vor 2, 4, 4 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65520 -; CHECK-FISL: stxvd2x 0, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65520 +; CHECK-FISL: stxvd2x 0, 1, [[REG2]] ; CHECK-FISL: blr ; CHECK-LE-LABEL: @test14 @@ -294,9 +294,9 @@ ; CHECK-FISL: vor 5, 3, 3 ; CHECK-FISL: xxlnor 36, 36, 37 ; CHECK-FISL: vor 2, 4, 4 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65520 -; CHECK-FISL: stvx 0, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65520 +; CHECK-FISL: stvx 0, 1, [[REG2]] ; CHECK-FISL: blr ; CHECK-LE-LABEL: @test15 @@ -323,9 +323,9 @@ ; CHECK-FISL: vor 5, 3, 3 ; CHECK-FISL: xxlnor 36, 36, 37 ; CHECK-FISL: vor 2, 4, 4 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65520 -; CHECK-FISL: stvx 0, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65520 +; CHECK-FISL: stvx 0, 1, [[REG2]] ; CHECK-FISL: blr ; CHECK-LE-LABEL: @test16 @@ -378,9 +378,9 @@ ; CHECK-FISL: vor 0, 3, 3 ; CHECK-FISL: xxlandc 37, 37, 32 ; CHECK-FISL: vor 2, 5, 5 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65520 -; CHECK-FISL: stvx 4, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65520 +; CHECK-FISL: stvx 4, 1, [[REG2]] ; CHECK-FISL: blr ; CHECK-LE-LABEL: @test18 @@ -408,9 +408,9 @@ ; CHECK-FISL: vor 0, 3, 3 ; CHECK-FISL: xxlandc 37, 37, 32 ; CHECK-FISL: vor 2, 5, 5 -; CHECK-FISL: lis 0, -1 -; CHECK-FISL: ori 0, 0, 65520 -; CHECK-FISL: stvx 4, 1, 0 +; CHECK-FISL: lis [[REG:[0-9]+]], -1 +; CHECK-FISL: ori [[REG2:[0-9]+]], [[REG]], 65520 +; CHECK-FISL: stvx 4, 1, [[REG2]] ; CHECK-FISL: blr ; CHECK-LE-LABEL: @test19