From 0ca0ddafe51ec12bea16ab970edd1c3c5a4e76c4 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Thu, 14 Sep 2017 15:53:11 +0000 Subject: [PATCH] [IfConversion] More simple, correct dead/kill liveness handling Patch by Jesper Antonsson. Differential Revision: https://reviews.llvm.org/D37611 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@313268 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LivePhysRegs.h | 9 +++ lib/CodeGen/IfConversion.cpp | 55 +-------------- lib/CodeGen/LivePhysRegs.cpp | 67 +++++++++++++++++-- .../Hexagon/branch-folder-hoist-kills.mir | 4 +- test/CodeGen/Hexagon/ifcvt-impuse-livein.mir | 2 +- test/CodeGen/Hexagon/ifcvt-live-subreg.mir | 6 +- .../Hexagon/livephysregs-add-pristines.mir | 2 +- 7 files changed, 81 insertions(+), 64 deletions(-) diff --git a/include/llvm/CodeGen/LivePhysRegs.h b/include/llvm/CodeGen/LivePhysRegs.h index b3dcd86b2bb..a37ca137919 100644 --- a/include/llvm/CodeGen/LivePhysRegs.h +++ b/include/llvm/CodeGen/LivePhysRegs.h @@ -108,6 +108,12 @@ public: /// Returns true if register \p Reg and no aliasing register is in the set. bool available(const MachineRegisterInfo &MRI, unsigned Reg) const; + /// Remove defined registers and regmask kills from the set. + void removeDefs(const MachineInstr &MI); + + /// Add uses to the set. + void addUses(const MachineInstr &MI); + /// Simulates liveness when stepping backwards over an instruction(bundle). /// Remove Defs, add uses. This is the recommended way of calculating /// liveness. @@ -168,6 +174,9 @@ inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) { /// instance \p LiveRegs. void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB); +/// Recomputes dead and kill flags in \p MBB. +void recomputeLivenessFlags(MachineBasicBlock &MBB); + /// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB. /// Does not add reserved registers. void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs); diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index a0ce2541583..05600bbc0a8 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -179,7 +179,6 @@ namespace { MachineRegisterInfo *MRI; LivePhysRegs Redefs; - LivePhysRegs DontKill; bool PreRegAlloc; bool MadeChange; @@ -461,6 +460,9 @@ bool IfConverter::runOnMachineFunction(MachineFunction &MF) { } } + if (RetVal && MRI->tracksLiveness()) + recomputeLivenessFlags(*BBI.BB); + Change |= RetVal; NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev + @@ -1380,13 +1382,6 @@ static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) { MIB.addReg(Reg, RegState::Implicit | RegState::Define); continue; } - assert(Op.isReg() && "Register operand required"); - if (Op.isDead()) { - // If we found a dead def, but it needs to be live, then remove the dead - // flag. - if (Redefs.contains(Op.getReg())) - Op.setIsDead(false); - } if (LiveBeforeMI.count(Reg)) MIB.addReg(Reg, RegState::Implicit); else { @@ -1403,26 +1398,6 @@ static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) { } } -/// Remove kill flags from operands with a registers in the \p DontKill set. -static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) { - for (MIBundleOperands O(MI); O.isValid(); ++O) { - if (!O->isReg() || !O->isKill()) - continue; - if (DontKill.contains(O->getReg())) - O->setIsKill(false); - } -} - -/// Walks a range of machine instructions and removes kill flags for registers -/// in the \p DontKill set. -static void RemoveKills(MachineBasicBlock::iterator I, - MachineBasicBlock::iterator E, - const LivePhysRegs &DontKill, - const MCRegisterInfo &MCRI) { - for (MachineInstr &MI : make_range(I, E)) - RemoveKills(MI, DontKill); -} - /// If convert a simple (split, no rejoin) sub-CFG. bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()]; @@ -1453,16 +1428,12 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { llvm_unreachable("Unable to reverse branch condition!"); Redefs.init(*TRI); - DontKill.init(*TRI); if (MRI->tracksLiveness()) { // Initialize liveins to the first BB. These are potentiall redefined by // predicated instructions. Redefs.addLiveIns(CvtMBB); Redefs.addLiveIns(NextMBB); - // Compute a set of registers which must not be killed by instructions in - // BB1: This is everything live-in to BB2. - DontKill.addLiveIns(NextMBB); } // Remove the branches from the entry so we can add the contents of the true @@ -1478,7 +1449,6 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { BBI.BB->removeSuccessor(&CvtMBB, true); } else { // Predicate the instructions in the true block. - RemoveKills(CvtMBB.begin(), CvtMBB.end(), DontKill, *TRI); PredicateBlock(*CvtBBI, CvtMBB.end(), Cond); // Merge converted block into entry block. The BB to Cvt edge is removed @@ -1567,8 +1537,6 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { Redefs.addLiveIns(NextMBB); } - DontKill.clear(); - bool HasEarlyExit = CvtBBI->FalseBB != nullptr; BranchProbability CvtNext, CvtFalse, BBNext, BBCvt; @@ -1751,25 +1719,12 @@ bool IfConverter::IfConvertDiamondCommon( --NumDups1; } - // Compute a set of registers which must not be killed by instructions in BB1: - // This is everything used+live in BB2 after the duplicated instructions. We - // can compute this set by simulating liveness backwards from the end of BB2. - DontKill.init(*TRI); if (MRI->tracksLiveness()) { - for (const MachineInstr &MI : make_range(MBB2.rbegin(), ++DI2.getReverse())) - DontKill.stepBackward(MI); - for (const MachineInstr &MI : make_range(MBB1.begin(), DI1)) { SmallVector, 4> Dummy; Redefs.stepForward(MI, Dummy); } } - // Kill flags in the true block for registers living into the false block - // must be removed. This should be done before extracting the common - // instructions from the beginning of the MBB1, since these instructions - // can actually differ between MBB1 and MBB2 in terms of flags. - RemoveKills(MBB1.begin(), MBB1.end(), DontKill, *TRI); - BBI.BB->splice(BBI.BB->end(), &MBB1, MBB1.begin(), DI1); MBB2.erase(MBB2.begin(), DI2); @@ -2085,10 +2040,6 @@ void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI, // If the predicated instruction now redefines a register as the result of // if-conversion, add an implicit kill. UpdatePredRedefs(*MI, Redefs); - - // Some kill flags may not be correct anymore. - if (!DontKill.empty()) - RemoveKills(*MI, DontKill); } if (!IgnoreBr) { diff --git a/lib/CodeGen/LivePhysRegs.cpp b/lib/CodeGen/LivePhysRegs.cpp index c3e46d3e0b8..779f601e402 100644 --- a/lib/CodeGen/LivePhysRegs.cpp +++ b/lib/CodeGen/LivePhysRegs.cpp @@ -40,10 +40,8 @@ void LivePhysRegs::removeRegsInMask(const MachineOperand &MO, } } -/// Simulates liveness when stepping backwards over an instruction(bundle): -/// Remove Defs, add uses. This is the recommended way of calculating liveness. -void LivePhysRegs::stepBackward(const MachineInstr &MI) { - // Remove defined registers and regmask kills from the set. +/// Remove defined registers and regmask kills from the set. +void LivePhysRegs::removeDefs(const MachineInstr &MI) { for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { if (O->isReg()) { if (!O->isDef()) @@ -55,8 +53,10 @@ void LivePhysRegs::stepBackward(const MachineInstr &MI) { } else if (O->isRegMask()) removeRegsInMask(*O); } +} - // Add uses to the set. +/// Add uses to the set. +void LivePhysRegs::addUses(const MachineInstr &MI) { for (ConstMIBundleOperands O(MI); O.isValid(); ++O) { if (!O->isReg() || !O->readsReg()) continue; @@ -67,6 +67,16 @@ void LivePhysRegs::stepBackward(const MachineInstr &MI) { } } +/// Simulates liveness when stepping backwards over an instruction(bundle): +/// Remove Defs, add uses. This is the recommended way of calculating liveness. +void LivePhysRegs::stepBackward(const MachineInstr &MI) { + // Remove defined registers and regmask kills from the set. + removeDefs(MI); + + // Add uses to the set. + addUses(MI); +} + /// Simulates liveness when stepping forward over an instruction(bundle): Remove /// killed-uses, add defs. This is the not recommended way, because it depends /// on accurate kill flags. If possible use stepBackward() instead of this @@ -265,6 +275,53 @@ void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) { } } +void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) { + const MachineFunction &MF = *MBB.getParent(); + const MachineRegisterInfo &MRI = MF.getRegInfo(); + const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); + + // We walk through the block backwards and start with the live outs. + LivePhysRegs LiveRegs; + LiveRegs.init(TRI); + LiveRegs.addLiveOutsNoPristines(MBB); + + for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) { + // Recompute dead flags. + for (MIBundleOperands MO(MI); MO.isValid(); ++MO) { + if (!MO->isReg() || !MO->isDef() || MO->isDebug()) + continue; + + unsigned Reg = MO->getReg(); + if (Reg == 0) + continue; + assert(TargetRegisterInfo::isPhysicalRegister(Reg)); + + bool IsNotLive = LiveRegs.available(MRI, Reg); + MO->setIsDead(IsNotLive); + } + + // Step backward over defs. + LiveRegs.removeDefs(MI); + + // Recompute kill flags. + for (MIBundleOperands MO(MI); MO.isValid(); ++MO) { + if (!MO->isReg() || !MO->readsReg() || MO->isDebug()) + continue; + + unsigned Reg = MO->getReg(); + if (Reg == 0) + continue; + assert(TargetRegisterInfo::isPhysicalRegister(Reg)); + + bool IsNotLive = LiveRegs.available(MRI, Reg); + MO->setIsKill(IsNotLive); + } + + // Complete the stepbackward. + LiveRegs.addUses(MI); + } +} + void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB) { computeLiveIns(LiveRegs, MBB); diff --git a/test/CodeGen/Hexagon/branch-folder-hoist-kills.mir b/test/CodeGen/Hexagon/branch-folder-hoist-kills.mir index a746d826265..47da85b2308 100644 --- a/test/CodeGen/Hexagon/branch-folder-hoist-kills.mir +++ b/test/CodeGen/Hexagon/branch-folder-hoist-kills.mir @@ -16,7 +16,7 @@ # %R1 = A2_sxth %R0 ; hoisted, kills r0 # A2_nop %P0 # %R0 = C2_cmoveit %P0, 2, %R0 ; predicated A2_tfrsi -# %R0 = C2_cmoveif %P0, 1, %R0 ; predicated A2_tfrsi +# %R0 = C2_cmoveif killed %P0, 1, %R0 ; predicated A2_tfrsi # %R0 = A2_add %R0, %R1 # J2_jumpr %R31, %PC # @@ -24,7 +24,7 @@ # CHECK: %r1 = A2_sxth killed %r0 # CHECK: %r0 = C2_cmoveit %p0, 2 # CHECK-NOT: implicit-def %r0 -# CHECK: %r0 = C2_cmoveif %p0, 1, implicit %r0 +# CHECK: %r0 = C2_cmoveif killed %p0, 1, implicit killed %r0 --- name: fred diff --git a/test/CodeGen/Hexagon/ifcvt-impuse-livein.mir b/test/CodeGen/Hexagon/ifcvt-impuse-livein.mir index 780b9cedf7f..267bb219e1c 100644 --- a/test/CodeGen/Hexagon/ifcvt-impuse-livein.mir +++ b/test/CodeGen/Hexagon/ifcvt-impuse-livein.mir @@ -32,7 +32,7 @@ body: | ; block bb.1 in the original diamond. After if-conversion, the diamond ; became a single block, and so r2 is now live on entry to the instructions ; originating from bb.2. - ; CHECK: %r2 = C2_cmoveit %p1, 1, implicit %r2 + ; CHECK: %r2 = C2_cmoveit %p1, 1, implicit killed %r2 %r2 = A2_tfrsi 1 bb.3: liveins: %r0, %r2 diff --git a/test/CodeGen/Hexagon/ifcvt-live-subreg.mir b/test/CodeGen/Hexagon/ifcvt-live-subreg.mir index 12cc086bd34..388257135c1 100644 --- a/test/CodeGen/Hexagon/ifcvt-live-subreg.mir +++ b/test/CodeGen/Hexagon/ifcvt-live-subreg.mir @@ -8,8 +8,8 @@ # CHECK-LABEL: bb.0: # CHECK: liveins: %r0, %r1, %p0, %d8 # CHECK: %d8 = A2_combinew killed %r0, killed %r1 -# CHECK: %d8 = L2_ploadrdf_io %p0, %r29, 0, implicit %d8 -# CHECK: J2_jumprf %p0, killed %r31, implicit-def %pc, implicit-def %pc, implicit killed %d8 +# CHECK: %d8 = L2_ploadrdf_io %p0, %r29, 0, implicit killed %d8 +# CHECK: J2_jumprf killed %p0, %r31, implicit-def %pc, implicit-def %pc, implicit %d8 --- | define void @foo() { @@ -35,7 +35,7 @@ body: | J2_jumpf killed %p0, %bb.2, implicit-def %pc bb.1: - liveins: %d0, %r17 + liveins: %r17 %r0 = A2_tfrsi 0 %r1 = A2_tfrsi 0 A2_nop ; non-predicable diff --git a/test/CodeGen/Hexagon/livephysregs-add-pristines.mir b/test/CodeGen/Hexagon/livephysregs-add-pristines.mir index 7579b17e1ff..fcb3a4a3dbf 100644 --- a/test/CodeGen/Hexagon/livephysregs-add-pristines.mir +++ b/test/CodeGen/Hexagon/livephysregs-add-pristines.mir @@ -2,7 +2,7 @@ # The register r23 is live on the path bb.0->bb.2->bb.3. Make sure we add # an implicit use of r23 to the predicated redefinition: -# CHECK: %r23 = A2_tfrt %p0, killed %r1, implicit %r23 +# CHECK: %r23 = A2_tfrt killed %p0, killed %r1, implicit killed %r23 # LivePhysRegs::addPristines could accidentally remove a callee-saved # register, if it determined that it wasn't pristine. Doing that caused -- 2.40.0