[X86] Break false dependencies for POPCNT, LZCNT, TZCNT

[myatsina]

Summary

Add POPCNT, LZCNT, TZCNT to the list of instructions that have false dependency.
Add a test to make sure BreakFalseDeps breaks the dependencies for these instructions.
Update affected tests.

This fixes bugzilla https://bugs.llvm.org/show_bug.cgi?id=33869

This is the last of 5 patches that fix bugzilla https://bugs.llvm.org/show_bug.cgi?id=33869
Previous patches:
https://reviews.llvm.org/D40330
https://reviews.llvm.org/D40331
https://reviews.llvm.org/D40332
https://reviews.llvm.org/D40333

[zvi]

I think we will need a subtarget feature indicating whether the false-dependency on these instructions happens. For starters, does this happen in AMD processors?

[craig.topper]

Yes we need a feature flag. As far as I know it doesn't happen on AMD. On Intel LZCNT/TZCNT have a problem on Sandybridge, ivybridge, haswell, broadwell. It's fixed on skylake. For popcnt, it has a problem on sandybridge, ivybridge, haswell, broadwell, skylake. I believe it is fixed in cannonlake.

[craig.topper]

lib/Target/X86/X86InstrInfo.cpp

8011

Why are the register forms missing? They have the problem too.

8245

Use XOR32rr on the 32-bit sub register. Shorter encoding and 0s the upper bits.

8255

XOR16rr is not a dependency breaking instruction. It still reads bits 31:16 of the register and passes them through.

[craig.topper]

lib/Target/X86/X86InstrInfo.cpp

8255

It doesn't look like gcc breaks the dependency on 16-bit versions. There is a real dependency there due to the need to preserve bits 31:16. But I would think the zeroing would still break the dependency on the previous iteration of the loop since the zeroing xor doesn't require execution resources.

[myatsina]

Added subtarget features.
Adding the rr versions of the instructions to hasPartialRegUpdate affected folding of memory operands for these instructions (if an instruction has partial reg update, then it folds only if optimizing for size) - Made a small adjustment the test to recreate the problematic scenario after this change.

[craig.topper]

What are you planning to do with 16-bit instructions? Like I said XOR16 is insufficient to break a dependency.

lib/Target/X86/X86InstrInfo.cpp

7972

Pass subtarget by const reference.

test/CodeGen/X86/bug3389.ll

1

The file name for this test case is missing a digit and we usually use "pr" instead of "bug". Though in this case I think you should name it something like more meaningful like bitcnt-false-dep.ll. We usually only name test cases with bug numbers when its a reduced test case for a crash or something where its harder to find a meaningful name.

4

Test 64-bit as well?

[myatsina]

In D40334#939939, @craig.topper wrote:

What are you planning to do with 16-bit instructions? Like I said XOR16 is insufficient to break a dependency.

I'm leading towards adding a 32bit XOR. Do you agree with that solution?

test/CodeGen/X86/bug3389.ll

87

Will fix this in the commit

[craig.topper]

I don't know if you'd be allowed to widen the register class to 32-bit without doing some live register analysis to know the upper bits aren't used later.

But the dependency on 16-bit isn't completely "false", its needed to preserve the upper bits due to how partial registers are implemented for all processors after Sandybridge. Zeroing the register would break the dependency, but you would still need to do that on for 16-bit instructions even on Skylake and Cannonlake. The fixes made to the 32/64 instructions on those CPUs didn't change anything about the 16-bit instruction.

So I think we should just remove the 16-bit instructions from this patch.

[myatsina]

Addressed comments.

[craig.topper]

lib/Target/X86/X86InstrInfo.cpp

8250

I think you need a .addreg(Reg, RegState::ImplicitDefine) here too. See the VXORPSrr code above.

[myatsina]

Added .addreg(Reg, RegState::ImplicitDefine)

[craig.topper]

LGTM

lib/Target/X86/X86.td

def FeatureSlowLEA : SubtargetFeature<"slow-lea", "SlowLEA", "true",
                                    "LEA instruction with certain arguments is slow">;
 def FeatureSlow3OpsLEA : SubtargetFeature<"slow-3ops-lea", "Slow3OpsLEA", "true",
                                    "LEA instruction with 3 ops or certain registers is slow">;
 def FeatureSlowIncDec : SubtargetFeature<"slow-incdec", "SlowIncDec", "true",
                                    "INC and DEC instructions are slower than ADD and SUB">;
 def FeatureSoftFloat
     : SubtargetFeature<"soft-float", "UseSoftFloat", "true",
                        "Use software floating point features.">;
+def FeaturePOPCNTFalseDeps : SubtargetFeature<"false-deps-popcnt",
+                                     "HasPOPCNTFalseDeps", "true",
+                                     "POPCNT has a false dependency on dest register">;
+def FeatureLZCNTFalseDeps : SubtargetFeature<"false-deps-lzcnt-tzcnt",
+                                     "HasLZCNTFalseDeps", "true",
+                                     "LZCNT/TZCNT have a false dependency on dest register">;
 // On some X86 processors, there is no performance hazard to writing only the
 // lower parts of a YMM or ZMM register without clearing the upper part.
 def FeatureFastPartialYMMorZMMWrite
     : SubtargetFeature<"fast-partial-ymm-or-zmm-write",
                        "HasFastPartialYMMorZMMWrite",
                        "true", "Partial writes to YMM/ZMM registers are fast">;
 // FeatureFastScalarFSQRT should be enabled if scalar FSQRT has shorter latency
 // than the corresponding NR code. FeatureFastVectorFSQRT should be enabled if
def SNBFeatures : ProcessorFeatures<[], [
   FeatureFastScalarFSQRT,
   FeatureFastSHLDRotate,
   FeatureSlowIncDec,
   FeatureMacroFusion
 ]>;
 
 class SandyBridgeProc<string Name> : ProcModel<Name, SandyBridgeModel,
                                                SNBFeatures.Value, [
-  FeatureSlowUAMem32
+  FeatureSlowUAMem32,
+  FeaturePOPCNTFalseDeps
 ]>;
 def : SandyBridgeProc<"sandybridge">;
 def : SandyBridgeProc<"corei7-avx">; // Legacy alias.
 
 def IVBFeatures : ProcessorFeatures<SNBFeatures.Value, [
   FeatureRDRAND,
   FeatureF16C,
   FeatureFSGSBase
 ]>;
 
 class IvyBridgeProc<string Name> : ProcModel<Name, SandyBridgeModel,
                                              IVBFeatures.Value, [
-  FeatureSlowUAMem32
+  FeatureSlowUAMem32,
+  FeaturePOPCNTFalseDeps
 ]>;
 def : IvyBridgeProc<"ivybridge">;
 def : IvyBridgeProc<"core-avx-i">; // Legacy alias.
 
 def HSWFeatures : ProcessorFeatures<IVBFeatures.Value, [
   FeatureAVX2,
   FeatureBMI,
   FeatureBMI2,
   FeatureERMSB,
   FeatureFMA,
   FeatureLZCNT,
   FeatureMOVBE
 ]>;
 
 class HaswellProc<string Name> : ProcModel<Name, HaswellModel,
                                            HSWFeatures.Value, [
-  ProcIntelHSW
+  ProcIntelHSW,
+  FeaturePOPCNTFalseDeps,
+  FeatureLZCNTFalseDeps
 ]>;
 def : HaswellProc<"haswell">;
 def : HaswellProc<"core-avx2">; // Legacy alias.
 
 def BDWFeatures : ProcessorFeatures<HSWFeatures.Value, [
   FeatureADX,
   FeatureRDSEED
 ]>;
 class BroadwellProc<string Name> : ProcModel<Name, BroadwellModel,
                                              BDWFeatures.Value, [
-  ProcIntelBDW
+  ProcIntelBDW,
+  FeaturePOPCNTFalseDeps,
+  FeatureLZCNTFalseDeps
 ]>;
 def : BroadwellProc<"broadwell">;
 
 def SKLFeatures : ProcessorFeatures<BDWFeatures.Value, [
   FeatureMPX,
   FeatureRTM,
   FeatureXSAVEC,
   FeatureXSAVES,
   FeatureSGX,
   FeatureCLFLUSHOPT,
   FeatureFastVectorFSQRT
 ]>;
 
 class SkylakeClientProc<string Name> : ProcModel<Name, SkylakeClientModel,
                                                  SKLFeatures.Value, [
-  ProcIntelSKL
+  ProcIntelSKL,
+  FeaturePOPCNTFalseDeps
 ]>;
 def : SkylakeClientProc<"skylake">;
 
 def KNLFeatures : ProcessorFeatures<IVBFeatures.Value, [
   FeatureAVX512,
   FeatureERI,
   FeatureCDI,
   FeaturePFI,

lib/Target/X86/X86InstrInfo.cpp

 ///   movss (%rdi), %xmm0
 ///   cvtss2sd %xmm0, %xmm0
 ///
 /// Instead of
 ///   cvtss2sd (%rdi), %xmm0
 ///
 /// FIXME: This should be turned into a TSFlags.
 ///
-static bool hasPartialRegUpdate(unsigned Opcode) {
+static bool hasPartialRegUpdate(unsigned Opcode, X86Subtarget &Subtarget) {
   switch (Opcode) {
   case X86::CVTSI2SSrr:
   case X86::CVTSI2SSrm:
   case X86::CVTSI2SS64rr:
   case X86::CVTSI2SS64rm:
   case X86::CVTSI2SDrr:
   case X86::CVTSI2SDrm:
   case X86::CVTSI2SD64rr:
static bool hasPartialRegUpdate(unsigned Opcode, X86Subtarget &Subtarget) {
   case X86::SQRTSSm:
   case X86::SQRTSSr_Int:
   case X86::SQRTSSm_Int:
   case X86::SQRTSDr:
   case X86::SQRTSDm:
   case X86::SQRTSDr_Int:
   case X86::SQRTSDm_Int:
     return true;
+  // GPR
+  case X86::POPCNT16rm:
+  case X86::POPCNT16rr:
+  case X86::POPCNT32rm:
+  case X86::POPCNT32rr:
+  case X86::POPCNT64rm:
+  case X86::POPCNT64rr:
+    return Subtarget.hasPOPCNTFalseDeps();
+  case X86::LZCNT16rm:
+  case X86::LZCNT16rr:
+  case X86::LZCNT32rm:
+  case X86::LZCNT32rr:
+  case X86::LZCNT64rm:
+  case X86::LZCNT64rr:
+  case X86::TZCNT16rm:
+  case X86::TZCNT16rr:
+  case X86::TZCNT32rm:
+  case X86::TZCNT32rr:
+  case X86::TZCNT64rm:
+  case X86::TZCNT64rr:
+    return Subtarget.hasLZCNTFalseDeps();
   }
 
   return false;
 }
 
 /// Inform the BreakFalseDeps pass how many idle
 /// instructions we would like before a partial register update.
 unsigned X86InstrInfo::getPartialRegUpdateClearance(
     const MachineInstr &MI, unsigned OpNum,
     const TargetRegisterInfo *TRI) const {
-  if (OpNum != 0 || !hasPartialRegUpdate(MI.getOpcode()))
+  if (OpNum != 0 || !hasPartialRegUpdate(MI.getOpcode(), Subtarget))
     return 0;
 
   // If MI is marked as reading Reg, the partial register update is wanted.
   const MachineOperand &MO = MI.getOperand(0);
   unsigned Reg = MO.getReg();
   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     if (MO.readsReg() || MI.readsVirtualRegister(Reg))
       return 0;
if (X86::VR128RegClass.contains(Reg)) {
     // Use vxorps to clear the full ymm register.
     // It wants to read and write the xmm sub-register.
     unsigned XReg = TRI->getSubReg(Reg, X86::sub_xmm);
     BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), get(X86::VXORPSrr), XReg)
         .addReg(XReg, RegState::Undef)
         .addReg(XReg, RegState::Undef)
         .addReg(Reg, RegState::ImplicitDefine);
     MI.addRegisterKilled(Reg, TRI, true);
+  } else if (X86::GR64RegClass.contains(Reg)) {
+    // Using XOR32rr because it has shorter encoding and zeros up the upper bits
+    // as well.
+    unsigned XReg = TRI->getSubReg(Reg, X86::sub_32bit);
+    BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), get(X86::XOR32rr), Reg)
+        .addReg(XReg, RegState::Undef)
+        .addReg(XReg, RegState::Undef);
+    MI.addRegisterKilled(Reg, TRI, true);
+  } else if (X86::GR32RegClass.contains(Reg)) {
+    BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), get(X86::XOR32rr), Reg)
+        .addReg(Reg, RegState::Undef)
+        .addReg(Reg, RegState::Undef);
+    MI.addRegisterKilled(Reg, TRI, true);
+  } else if (X86::GR16RegClass.contains(Reg)) {
+    BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), get(X86::XOR16rr), Reg)
+        .addReg(Reg, RegState::Undef)
+        .addReg(Reg, RegState::Undef);
+    MI.addRegisterKilled(Reg, TRI, true);
   }
 }
 
 static void addOperands(MachineInstrBuilder &MIB, ArrayRef<MachineOperand> MOs,
                         int PtrOffset = 0) {
   unsigned NumAddrOps = MOs.size();
 
   if (NumAddrOps < 4) {
MachineInstr *X86InstrInfo::foldMemoryOperandImpl(
   if (isSlowTwoMemOps && !MF.getFunction()->optForMinSize() &&
       (MI.getOpcode() == X86::CALL32r || MI.getOpcode() == X86::CALL64r ||
        MI.getOpcode() == X86::PUSH16r || MI.getOpcode() == X86::PUSH32r ||
        MI.getOpcode() == X86::PUSH64r))
     return nullptr;
 
   // Avoid partial register update stalls unless optimizing for size.
   // TODO: we should block undef reg update as well.
-  if (!MF.getFunction()->optForSize() && hasPartialRegUpdate(MI.getOpcode()))
+  if (!MF.getFunction()->optForSize() &&
+      hasPartialRegUpdate(MI.getOpcode(), Subtarget))
     return nullptr;
 
   unsigned NumOps = MI.getDesc().getNumOperands();
   bool isTwoAddr =
       NumOps > 1 && MI.getDesc().getOperandConstraint(1, MCOI::TIED_TO) != -1;
 
   // FIXME: AsmPrinter doesn't know how to handle
   // X86II::MO_GOT_ABSOLUTE_ADDRESS after folding.
X86InstrInfo::foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
                                     int FrameIndex, LiveIntervals *LIS) const {
   // Check switch flag
   if (NoFusing)
     return nullptr;
 
   // Unless optimizing for size, don't fold to avoid partial
   // register update stalls
   // TODO: we should block undef reg update as well.
-  if (!MF.getFunction()->optForSize() && hasPartialRegUpdate(MI.getOpcode()))
+  if (!MF.getFunction()->optForSize() &&
+      hasPartialRegUpdate(MI.getOpcode(), Subtarget))
     return nullptr;
 
   // Don't fold subreg spills, or reloads that use a high subreg.
   for (auto Op : Ops) {
     MachineOperand &MO = MI.getOperand(Op);
     auto SubReg = MO.getSubReg();
     if (SubReg && (MO.isDef() || SubReg == X86::sub_8bit_hi))
       return nullptr;
if (isLoadFromStackSlot(LoadMI, FrameIndex)) {
     return foldMemoryOperandImpl(MF, MI, Ops, InsertPt, FrameIndex, LIS);
   }
 
   // Check switch flag
   if (NoFusing) return nullptr;
 
   // Avoid partial register update stalls unless optimizing for size.
   // TODO: we should block undef reg update as well.
-  if (!MF.getFunction()->optForSize() && hasPartialRegUpdate(MI.getOpcode()))
+  if (!MF.getFunction()->optForSize() &&
+      hasPartialRegUpdate(MI.getOpcode(), Subtarget))
     return nullptr;
 
   // Determine the alignment of the load.
   unsigned Alignment = 0;
   if (LoadMI.hasOneMemOperand())
     Alignment = (*LoadMI.memoperands_begin())->getAlignment();
   else
     switch (LoadMI.getOpcode()) {

lib/Target/X86/X86Subtarget.h

protected:
   /// True if this processor has the CMPXCHG16B instruction;
   /// this is true for most x86-64 chips, but not the first AMD chips.
   bool HasCmpxchg16b;
 
   /// True if the LEA instruction should be used for adjusting
   /// the stack pointer. This is an optimization for Intel Atom processors.
   bool UseLeaForSP;
 
+  /// True if POPCNT instruction has a false dependency on the destination register.
+  bool HasPOPCNTFalseDeps;
+
+  /// True if LZCNT/TZCNT instructions have a false dependency on the destination register.
+  bool HasLZCNTFalseDeps;
+
   /// True if there is no performance penalty to writing only the lower parts
   /// of a YMM or ZMM register without clearing the upper part.
   bool HasFastPartialYMMorZMMWrite;
 
   /// True if hardware SQRTSS instruction is at least as fast (latency) as
   /// RSQRTSS followed by a Newton-Raphson iteration.
   bool HasFastScalarFSQRT;
 
public:
   bool isPMULLDSlow() const { return IsPMULLDSlow; }
   bool isUnalignedMem16Slow() const { return IsUAMem16Slow; }
   bool isUnalignedMem32Slow() const { return IsUAMem32Slow; }
   int getGatherOverhead() const { return GatherOverhead; }
   int getScatterOverhead() const { return ScatterOverhead; }
   bool hasSSEUnalignedMem() const { return HasSSEUnalignedMem; }
   bool hasCmpxchg16b() const { return HasCmpxchg16b; }
   bool useLeaForSP() const { return UseLeaForSP; }
+  bool hasPOPCNTFalseDeps() const { return HasPOPCNTFalseDeps; }
+  bool hasLZCNTFalseDeps() const { return HasLZCNTFalseDeps; }
   bool hasFastPartialYMMorZMMWrite() const {
     return HasFastPartialYMMorZMMWrite;
   }
   bool hasFastScalarFSQRT() const { return HasFastScalarFSQRT; }
   bool hasFastVectorFSQRT() const { return HasFastVectorFSQRT; }
   bool hasFastLZCNT() const { return HasFastLZCNT; }
   bool hasFastSHLDRotate() const { return HasFastSHLDRotate; }
   bool hasMacroFusion() const { return HasMacroFusion; }

lib/Target/X86/X86Subtarget.cpp

void X86Subtarget::initializeEnvironment() {
   HasCLWB = false;
   IsPMULLDSlow = false;
   IsSHLDSlow = false;
   IsUAMem16Slow = false;
   IsUAMem32Slow = false;
   HasSSEUnalignedMem = false;
   HasCmpxchg16b = false;
   UseLeaForSP = false;
+  HasPOPCNTFalseDeps = false;
+  HasLZCNTFalseDeps = false;
   HasFastPartialYMMorZMMWrite = false;
   HasFastScalarFSQRT = false;
   HasFastVectorFSQRT = false;
   HasFastLZCNT = false;
   HasFastSHLDRotate = false;
   HasMacroFusion = false;
   HasERMSB = false;
   HasSlowDivide32 = false;

test/CodeGen/X86/bug3389.ll

+; RUN: llc < %s -mtriple=i386-unknown-linux-gnu -mcpu=haswell -mattr=+bmi,+lzcnt | FileCheck %s --check-prefix=HSW
+; RUN: llc < %s -mtriple=i386-unknown-linux-gnu -mcpu=skylake -mattr=+bmi,+lzcnt | FileCheck %s --check-prefix=SKL
+
+declare i32 @llvm.ctpop.i32(i32)
+declare i32 @llvm.cttz.i32(i32, i1)
+declare i32 @llvm.ctlz.i32(i32, i1)
+
+define i32 @loopdep_popcnt(i32* nocapture %x, double* nocapture %y) nounwind {
+entry:
+  %vx = load i32, i32* %x
+  br label %loop
+loop:
+  %i = phi i32 [ 1, %entry ], [ %inc, %loop ]
+  %s1 = phi i32 [ %vx, %entry ], [ %s2, %loop ]
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %j = tail call i32 @llvm.ctpop.i32(i32 %i)
+  %s2 = add i32 %s1, %j
+  %inc = add nsw i32 %i, 1
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %exitcond = icmp eq i32 %inc, 156250000
+  br i1 %exitcond, label %ret, label %loop
+ret:
+  ret i32 %s2
+
+;HSW-LABEL:@loopdep_popcnt
+;HSW: xorl [[GPR0:%e[a-d]x]], [[GPR0]]
+;HSW-NEXT: popcntl {{.*}}, [[GPR0]]
+
+;SKL-LABEL:@loopdep_popcnt
+;SKL: xorl [[GPR0:%e[a-d]x]], [[GPR0]]
+;SKL-NEXT: popcntl {{.*}}, [[GPR0]]
+}
+
+define i32 @loopdep_tzct(i32* nocapture %x, double* nocapture %y) nounwind {
+entry:
+  %vx = load i32, i32* %x
+  br label %loop
+loop:
+  %i = phi i32 [ 1, %entry ], [ %inc, %loop ]
+  %s1 = phi i32 [ %vx, %entry ], [ %s2, %loop ]
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %j = call i32 @llvm.cttz.i32( i32 %i, i1 true )
+  %s2 = add i32 %s1, %j
+  %inc = add nsw i32 %i, 1
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %exitcond = icmp eq i32 %inc, 156250000
+  br i1 %exitcond, label %ret, label %loop
+ret:
+  ret i32 %s2
+
+;HSW-LABEL:@loopdep_tzct
+;HSW: xorl [[GPR0:%e[a-d]x]], [[GPR0]]
+;HSW-NEXT: tzcntl {{.*}}, [[GPR0]]
+
+; This false dependecy issue was fixed in Skylake
+;SKL-LABEL:@loopdep_tzct
+;SKL-NOT: xorl
+;SKL: tzcntl
+}
+
+define i32 @loopdep_lzct(i32* nocapture %x, double* nocapture %y) nounwind {
+entry:
+  %vx = load i32, i32* %x
+  br label %loop
+loop:
+  %i = phi i32 [ 1, %entry ], [ %inc, %loop ]
+  %s1 = phi i32 [ %vx, %entry ], [ %s2, %loop ]
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %j = call i32 @llvm.ctlz.i32( i32 %i, i1 true )
+  %s2 = add i32 %s1, %j
+  %inc = add nsw i32 %i, 1
+  tail call void asm sideeffect "", "~{eax},~{ebx},~{ecx},~{edx},~{esi},~{edi},~{ebp},~{dirflag},~{fpsr},~{flags}"()
+  %exitcond = icmp eq i32 %inc, 156250000
+  br i1 %exitcond, label %ret, label %loop
+ret:
+  ret i32 %s2
+
+;HSW-LABEL:@loopdep_lzct
+;HSW: xorl [[GPR0:%e[a-d]x]], [[GPR0]]
+;HSW-NEXT: lzcntl {{.*}}, [[GPR0]]
+
+; This false dependecy issue was fixed in Skylake
+;SKL-LABEL:@loopdep_lzct
+;SKL-NOT: xorl
+;SKL: lzcntl
+}
 No newline at end of file