From f43272c76e2e0ba56d26f0e4b54dccb3e38628b0 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Fri, 11 Dec 2015 19:42:09 +0000 Subject: [PATCH] CodeGen: Redo analyzePhysRegs() and computeRegisterLiveness() computeRegisterLiveness() was broken in that it reported dead for a register even if a subregister was alive. I assume this was because the results of analayzePhysRegs() are hard to understand with respect to subregisters. This commit: Changes the results of analyzePhysRegs (=struct PhysRegInfo) to be clearly understandable, also renames the fields to avoid silent breakage of third-party code (and improve the grammar). Fix all (two) users of computeRegisterLiveness() in llvm: By reenabling it and removing workarounds for the bug. This fixes http://llvm.org/PR24535 and http://llvm.org/PR25033 Differential Revision: http://reviews.llvm.org/D15320 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255362 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/MachineBasicBlock.h | 9 ++-- include/llvm/CodeGen/MachineInstrBundle.h | 43 +++++++++------- lib/CodeGen/InlineSpiller.cpp | 2 +- lib/CodeGen/MachineBasicBlock.cpp | 46 ++++++++--------- lib/CodeGen/MachineInstrBundle.cpp | 43 ++++++++-------- .../AArch64/AArch64ConditionalCompares.cpp | 4 +- lib/Target/ARM/ARMBaseInstrInfo.cpp | 15 +----- lib/Target/X86/X86InstrInfo.cpp | 25 ++++----- test/CodeGen/X86/cmpxchg-clobber-flags.ll | 51 +++---------------- .../X86/peephole-na-phys-copy-folding.ll | 6 +-- 10 files changed, 94 insertions(+), 150 deletions(-) diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 57bd24ddddf..16a349fdeb1 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -696,12 +696,9 @@ public: /// Possible outcome of a register liveness query to computeRegisterLiveness() enum LivenessQueryResult { - LQR_Live, ///< Register is known to be live. - LQR_OverlappingLive, ///< Register itself is not live, but some overlapping - ///< register is. - LQR_Dead, ///< Register is known to be dead. - LQR_Unknown ///< Register liveness not decidable from local - ///< neighborhood. + LQR_Live, ///< Register is known to be (at least partially) live. + LQR_Dead, ///< Register is known to be fully dead. + LQR_Unknown ///< Register liveness not decidable from local neighborhood. }; /// Return whether (physical) register \p Reg has been ined and not diff --git a/include/llvm/CodeGen/MachineInstrBundle.h b/include/llvm/CodeGen/MachineInstrBundle.h index 4ec3c189ae0..4fbe206fceb 100644 --- a/include/llvm/CodeGen/MachineInstrBundle.h +++ b/include/llvm/CodeGen/MachineInstrBundle.h @@ -164,27 +164,32 @@ public: bool Tied; }; - /// PhysRegInfo - Information about a physical register used by a set of + /// Information about how a physical register Reg is used by a set of /// operands. struct PhysRegInfo { - /// Clobbers - Reg or an overlapping register is defined, or a regmask - /// clobbers Reg. - bool Clobbers; - - /// Defines - Reg or a super-register is defined. - bool Defines; - - /// Reads - Reg or a super-register is read. - bool Reads; - - /// ReadsOverlap - Reg or an overlapping register is read. - bool ReadsOverlap; - - /// DefinesDead - All defs of a Reg or a super-register are dead. - bool DefinesDead; - - /// There is a kill of Reg or a super-register. - bool Kills; + /// There is a regmask operand indicating Reg is clobbered. + /// \see MachineOperand::CreateRegMask(). + bool Clobbered; + + /// Reg or one of its aliases is defined. The definition may only cover + /// parts of the register. + bool Defined; + /// Reg or a super-register is defined. The definition covers the full + /// register. + bool FullyDefined; + + /// Reg or ont of its aliases is read. The register may only be read + /// partially. + bool Read; + /// Reg or a super-register is read. The full register is read. + bool FullyRead; + + /// Reg is FullyDefined and all defs of reg or an overlapping register are + /// dead. + bool DeadDef; + + /// There is a use operand of reg or a super-register with kill flag set. + bool Killed; }; /// analyzeVirtReg - Analyze how the current instruction or bundle uses a diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp index 0bb68c08373..7592ac27c41 100644 --- a/lib/CodeGen/InlineSpiller.cpp +++ b/lib/CodeGen/InlineSpiller.cpp @@ -1139,7 +1139,7 @@ foldMemoryOperand(ArrayRef > Ops, continue; MIBundleOperands::PhysRegInfo RI = MIBundleOperands(FoldMI).analyzePhysReg(Reg, &TRI); - if (RI.Defines) + if (RI.FullyDefined) continue; // FoldMI does not define this physreg. Remove the LI segment. assert(MO->isDead() && "Cannot fold physreg def"); diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index de91f0db75a..c8a5030e8d8 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -1178,33 +1178,33 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, do { --I; - MachineOperandIteratorBase::PhysRegInfo Analysis = + MachineOperandIteratorBase::PhysRegInfo Info = ConstMIOperands(I).analyzePhysReg(Reg, TRI); - if (Analysis.Defines) - // Outputs happen after inputs so they take precedence if both are - // present. - return Analysis.DefinesDead ? LQR_Dead : LQR_Live; + // Defs happen after uses so they take precedence if both are present. - if (Analysis.Kills || Analysis.Clobbers) - // Register killed, so isn't live. + // Register is dead after a dead def of the full register. + if (Info.DeadDef) return LQR_Dead; - - else if (Analysis.ReadsOverlap) - // Defined or read without a previous kill - live. - return Analysis.Reads ? LQR_Live : LQR_OverlappingLive; - + // Register is (at least partially) live after a def. + if (Info.Defined) + return LQR_Live; + // Register is dead after a full kill or clobber and no def. + if (Info.Killed || Info.Clobbered) + return LQR_Dead; + // Register must be live if we read it. + if (Info.Read) + return LQR_Live; } while (I != begin() && --N > 0); } // Did we get to the start of the block? if (I == begin()) { // If so, the register's state is definitely defined by the live-in state. - for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); - RAI.isValid(); ++RAI) { + for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid(); + ++RAI) if (isLiveIn(*RAI)) - return (*RAI == Reg) ? LQR_Live : LQR_OverlappingLive; - } + return LQR_Live; return LQR_Dead; } @@ -1216,16 +1216,14 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI, // If this is the last insn in the block, don't search forwards. if (I != end()) { for (++I; I != end() && N > 0; ++I, --N) { - MachineOperandIteratorBase::PhysRegInfo Analysis = + MachineOperandIteratorBase::PhysRegInfo Info = ConstMIOperands(I).analyzePhysReg(Reg, TRI); - if (Analysis.ReadsOverlap) - // Used, therefore must have been live. - return (Analysis.Reads) ? - LQR_Live : LQR_OverlappingLive; - - else if (Analysis.Clobbers || Analysis.Defines) - // Defined (but not read) therefore cannot have been live. + // Register is live when we read it here. + if (Info.Read) + return LQR_Live; + // Register is dead if we can fully overwrite or clobber it here. + if (Info.FullyDefined || Info.Clobbered) return LQR_Dead; } } diff --git a/lib/CodeGen/MachineInstrBundle.cpp b/lib/CodeGen/MachineInstrBundle.cpp index f6e45a4b7c7..3eaf4c5dea0 100644 --- a/lib/CodeGen/MachineInstrBundle.cpp +++ b/lib/CodeGen/MachineInstrBundle.cpp @@ -293,15 +293,17 @@ MachineOperandIteratorBase::PhysRegInfo MachineOperandIteratorBase::analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI) { bool AllDefsDead = true; - PhysRegInfo PRI = {false, false, false, false, false, false}; + PhysRegInfo PRI = {false, false, false, false, false, false, false}; assert(TargetRegisterInfo::isPhysicalRegister(Reg) && "analyzePhysReg not given a physical register!"); for (; isValid(); ++*this) { MachineOperand &MO = deref(); - if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) - PRI.Clobbers = true; // Regmask clobbers Reg. + if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) { + PRI.Clobbered = true; + continue; + } if (!MO.isReg()) continue; @@ -310,33 +312,28 @@ MachineOperandIteratorBase::analyzePhysReg(unsigned Reg, if (!MOReg || !TargetRegisterInfo::isPhysicalRegister(MOReg)) continue; - bool IsRegOrSuperReg = MOReg == Reg || TRI->isSuperRegister(MOReg, Reg); - bool IsRegOrOverlapping = MOReg == Reg || TRI->regsOverlap(MOReg, Reg); - - if (IsRegOrSuperReg && MO.readsReg()) { - // Reg or a super-reg is read, and perhaps killed also. - PRI.Reads = true; - PRI.Kills = MO.isKill(); - } - - if (IsRegOrOverlapping && MO.readsReg()) { - PRI.ReadsOverlap = true;// Reg or an overlapping register is read. - } - - if (!MO.isDef()) + if (!TRI->regsOverlap(MOReg, Reg)) continue; - if (IsRegOrSuperReg) { - PRI.Defines = true; // Reg or a super-register is defined. + bool Covered = TRI->isSuperRegisterEq(MOReg, Reg); + if (MO.readsReg()) { + PRI.Read = true; + if (Covered) { + PRI.FullyRead = true; + if (MO.isKill()) + PRI.Killed = true; + } + } else if (MO.isDef()) { + PRI.Defined = true; + if (Covered) + PRI.FullyDefined = true; if (!MO.isDead()) AllDefsDead = false; } - if (IsRegOrOverlapping) - PRI.Clobbers = true; // Reg or an overlapping reg is defined. } - if (AllDefsDead && PRI.Defines) - PRI.DefinesDead = true; // Reg or super-register was defined and was dead. + if (AllDefsDead && PRI.FullyDefined) + PRI.DeadDef = true; return PRI; } diff --git a/lib/Target/AArch64/AArch64ConditionalCompares.cpp b/lib/Target/AArch64/AArch64ConditionalCompares.cpp index b6c74244e64..920f4094a45 100644 --- a/lib/Target/AArch64/AArch64ConditionalCompares.cpp +++ b/lib/Target/AArch64/AArch64ConditionalCompares.cpp @@ -353,7 +353,7 @@ MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) { MIOperands::PhysRegInfo PRI = MIOperands(I).analyzePhysReg(AArch64::NZCV, TRI); - if (PRI.Reads) { + if (PRI.Read) { // The ccmp doesn't produce exactly the same flags as the original // compare, so reject the transform if there are uses of the flags // besides the terminators. @@ -362,7 +362,7 @@ MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) { return nullptr; } - if (PRI.Clobbers) { + if (PRI.Defined || PRI.Clobbered) { DEBUG(dbgs() << "Not convertible compare: " << *I); ++NumUnknNZCVDefs; return nullptr; diff --git a/lib/Target/ARM/ARMBaseInstrInfo.cpp b/lib/Target/ARM/ARMBaseInstrInfo.cpp index 62f1dae7839..49f32885266 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.cpp +++ b/lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -2029,15 +2029,6 @@ void llvm::emitARMRegPlusImmediate(MachineBasicBlock &MBB, } } -static bool isAnySubRegLive(unsigned Reg, const TargetRegisterInfo *TRI, - MachineInstr *MI) { - for (MCSubRegIterator Subreg(Reg, TRI, /* IncludeSelf */ true); - Subreg.isValid(); ++Subreg) - if (MI->getParent()->computeRegisterLiveness(TRI, *Subreg, MI) != - MachineBasicBlock::LQR_Dead) - return true; - return false; -} bool llvm::tryFoldSPUpdateIntoPushPop(const ARMSubtarget &Subtarget, MachineFunction &MF, MachineInstr *MI, unsigned NumBytes) { @@ -2112,11 +2103,9 @@ bool llvm::tryFoldSPUpdateIntoPushPop(const ARMSubtarget &Subtarget, // registers live within the function we might clobber a return value // register; the other way a register can be live here is if it's // callee-saved. - // TODO: Currently, computeRegisterLiveness() does not report "live" if a - // sub reg is live. When computeRegisterLiveness() works for sub reg, it - // can replace isAnySubRegLive(). if (isCalleeSavedRegister(CurReg, CSRegs) || - isAnySubRegLive(CurReg, TRI, MI)) { + MI->getParent()->computeRegisterLiveness(TRI, CurReg, MI) != + MachineBasicBlock::LQR_Dead) { // VFP pops don't allow holes in the register list, so any skip is fatal // for our transformation. GPR pops do, so we should just keep looking. if (IsVFPPushPop) diff --git a/lib/Target/X86/X86InstrInfo.cpp b/lib/Target/X86/X86InstrInfo.cpp index 34d4e90b310..c417a1c48ae 100644 --- a/lib/Target/X86/X86InstrInfo.cpp +++ b/lib/Target/X86/X86InstrInfo.cpp @@ -4439,22 +4439,17 @@ void X86InstrInfo::copyPhysReg(MachineBasicBlock &MBB, // first frame index. See X86FrameLowering.cpp - clobbersTheStack. - bool AXDead = (Reg == AX); - // FIXME: The above could figure out that AX is dead in more cases with: - // || (MachineBasicBlock::LQR_Dead == - // MBB.computeRegisterLiveness(&getRegisterInfo(), AX, MI)); - // - // Unfortunately this is slightly broken, see PR24535 and the likely - // related PR25033 PR24991 PR24992 PR25201. These issues seem to - // showcase sub-register / super-register confusion: a previous kill - // of AH but no kill of AL leads computeRegisterLiveness to - // erroneously conclude that AX is dead. - // - // Once fixed, also update cmpxchg-clobber-flags.ll and - // peephole-na-phys-copy-folding.ll. - - if (!AXDead) + bool AXDead = (Reg == AX) || + (MachineBasicBlock::LQR_Dead == + MBB.computeRegisterLiveness(&getRegisterInfo(), AX, MI)); + if (!AXDead) { + // FIXME: If computeRegisterLiveness() reported LQR_Unknown then AX may + // actually be dead. This is not a problem for correctness as we are just + // (unnecessarily) saving+restoring a dead register. However the + // MachineVerifier expects operands that read from dead registers + // to be marked with the "undef" flag. BuildMI(MBB, MI, DL, get(Push)).addReg(AX, getKillRegState(true)); + } if (FromEFLAGS) { BuildMI(MBB, MI, DL, get(X86::SETOr), X86::AL); BuildMI(MBB, MI, DL, get(X86::LAHF)); diff --git a/test/CodeGen/X86/cmpxchg-clobber-flags.ll b/test/CodeGen/X86/cmpxchg-clobber-flags.ll index c294dee4013..e21ba2a14cf 100644 --- a/test/CodeGen/X86/cmpxchg-clobber-flags.ll +++ b/test/CodeGen/X86/cmpxchg-clobber-flags.ll @@ -1,18 +1,11 @@ -; RUN: llc -mtriple=i386-linux-gnu %s -o - | FileCheck %s -check-prefix=i386 -; RUN: llc -mtriple=i386-linux-gnu -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=i386f - -; RUN: llc -mtriple=x86_64-linux-gnu %s -o - | FileCheck %s -check-prefix=x8664 -; RUN: llc -mtriple=x86_64-linux-gnu -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=x8664 -; RUN: llc -mtriple=x86_64-linux-gnu -mattr=+sahf %s -o - | FileCheck %s -check-prefix=x8664-sahf -; RUN: llc -mtriple=x86_64-linux-gnu -mattr=+sahf -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=x8664-sahf -; RUN: llc -mtriple=x86_64-linux-gnu -mcpu=corei7 %s -o - | FileCheck %s -check-prefix=x8664-sahf - -; FIXME: X86InstrInfo::copyPhysReg had code which figured out whether AX was -; live or not to avoid save / restore when it's not needed. See FIXME in -; that function for more details on which the code is currently -; disabled. The extra push/pop are marked below and can be removed once -; the issue is fixed. -; -verify-machineinstrs should also be added back in the RUN lines above. +; RUN: llc -verify-machineinstrs -mtriple=i386-linux-gnu %s -o - | FileCheck %s -check-prefix=i386 +; RUN: llc -verify-machineinstrs -mtriple=i386-linux-gnu -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=i386f + +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu %s -o - | FileCheck %s -check-prefix=x8664 +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=x8664 +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu -mattr=+sahf %s -o - | FileCheck %s -check-prefix=x8664-sahf +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu -mattr=+sahf -pre-RA-sched=fast %s -o - | FileCheck %s -check-prefix=x8664-sahf +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu -mcpu=corei7 %s -o - | FileCheck %s -check-prefix=x8664-sahf declare i32 @foo() declare i32 @bar(i64) @@ -28,34 +21,22 @@ define i64 @test_intervening_call(i64* %foo, i64 %bar, i64 %baz) { ; i386-NEXT: movl %edx, 4(%esp) ; i386-NEXT: movl %eax, (%esp) ; i386-NEXT: calll bar -; ** FIXME Next line isn't actually necessary. ** -; i386-NEXT: pushl %eax ; i386-NEXT: movl [[FLAGS]], %eax ; i386-NEXT: addb $127, %al ; i386-NEXT: sahf -; ** FIXME Next line isn't actually necessary. ** -; i386-NEXT: popl %eax ; i386-NEXT: jne ; i386f-LABEL: test_intervening_call: ; i386f: cmpxchg8b ; i386f-NEXT: movl %eax, (%esp) ; i386f-NEXT: movl %edx, 4(%esp) -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: pushl %eax ; i386f-NEXT: seto %al ; i386f-NEXT: lahf ; i386f-NEXT: movl %eax, [[FLAGS:%.*]] -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: popl %eax ; i386f-NEXT: calll bar -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: pushl %eax ; i386f-NEXT: movl [[FLAGS]], %eax ; i386f-NEXT: addb $127, %al ; i386f-NEXT: sahf -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: popl %eax ; i386f-NEXT: jne ; x8664-LABEL: test_intervening_call: @@ -77,13 +58,9 @@ define i64 @test_intervening_call(i64* %foo, i64 %bar, i64 %baz) { ; x8664-sahf-NEXT: popq %rax ; x8664-sahf-NEXT: movq %rax, %rdi ; x8664-sahf-NEXT: callq bar -; ** FIXME Next line isn't actually necessary. ** -; x8664-sahf-NEXT: pushq %rax ; x8664-sahf-NEXT: movq [[FLAGS]], %rax ; x8664-sahf-NEXT: addb $127, %al ; x8664-sahf-NEXT: sahf -; ** FIXME Next line isn't actually necessary. ** -; x8664-sahf-NEXT: popq %rax ; x8664-sahf-NEXT: jne %cx = cmpxchg i64* %foo, i64 %bar, i64 %baz seq_cst seq_cst @@ -152,13 +129,9 @@ cond.end: define i32 @test_feed_cmov(i32* %addr, i32 %desired, i32 %new) { ; i386-LABEL: test_feed_cmov: ; i386: cmpxchgl -; ** FIXME Next line isn't actually necessary. ** -; i386-NEXT: pushl %eax ; i386-NEXT: seto %al ; i386-NEXT: lahf ; i386-NEXT: movl %eax, [[FLAGS:%.*]] -; ** FIXME Next line isn't actually necessary. ** -; i386-NEXT: popl %eax ; i386-NEXT: calll foo ; i386-NEXT: pushl %eax ; i386-NEXT: movl [[FLAGS]], %eax @@ -168,13 +141,9 @@ define i32 @test_feed_cmov(i32* %addr, i32 %desired, i32 %new) { ; i386f-LABEL: test_feed_cmov: ; i386f: cmpxchgl -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: pushl %eax ; i386f-NEXT: seto %al ; i386f-NEXT: lahf ; i386f-NEXT: movl %eax, [[FLAGS:%.*]] -; ** FIXME Next line isn't actually necessary. ** -; i386f-NEXT: popl %eax ; i386f-NEXT: calll foo ; i386f-NEXT: pushl %eax ; i386f-NEXT: movl [[FLAGS]], %eax @@ -192,13 +161,9 @@ define i32 @test_feed_cmov(i32* %addr, i32 %desired, i32 %new) { ; x8664-sahf-LABEL: test_feed_cmov: ; x8664-sahf: cmpxchgl -; ** FIXME Next line isn't actually necessary. ** -; x8664-sahf: pushq %rax ; x8664-sahf: seto %al ; x8664-sahf-NEXT: lahf ; x8664-sahf-NEXT: movq %rax, [[FLAGS:%.*]] -; ** FIXME Next line isn't actually necessary. ** -; x8664-sahf-NEXT: popq %rax ; x8664-sahf-NEXT: callq foo ; x8664-sahf-NEXT: pushq %rax ; x8664-sahf-NEXT: movq [[FLAGS]], %rax diff --git a/test/CodeGen/X86/peephole-na-phys-copy-folding.ll b/test/CodeGen/X86/peephole-na-phys-copy-folding.ll index a8df33454e9..bf457814079 100644 --- a/test/CodeGen/X86/peephole-na-phys-copy-folding.ll +++ b/test/CodeGen/X86/peephole-na-phys-copy-folding.ll @@ -1,7 +1,5 @@ -; RUN: llc -mtriple=i386-linux-gnu %s -o - | FileCheck %s -; RUN: llc -mtriple=x86_64-linux-gnu -mattr=+sahf %s -o - | FileCheck %s - -; FIXME Add -verify-machineinstrs back when PR24535 is fixed. +; RUN: llc -verify-machineinstrs -mtriple=i386-linux-gnu %s -o - | FileCheck %s +; RUN: llc -verify-machineinstrs -mtriple=x86_64-linux-gnu -mattr=+sahf %s -o - | FileCheck %s ; The peephole optimizer can elide some physical register copies such as ; EFLAGS. Make sure the flags are used directly, instead of needlessly using -- 2.34.1