[X86] Add MC level selection support for SHLD (64-bit only)

[avt77]

Summary

Depends on D43813. Depends on D41278. We'd like to be albe properly to select SHLD/SHRD instrs or alternative code sequences in dependence on target CPUs. This patch shows the possibility to do it. It supports only one intruction: SHLD(16/32/64)rri8 but it shows how we could do it. If the suggested way is acceptable for us I'll continue with new extended patches.

I tried to split the patch on 2 steps: the debug extension and the support of SHLD itself. Unfortunately I could not find any usage of Machine Combiner except mul-lohi.ll test but this test is not informative enough to show the improvements in the debug print. On the other hand X86 target code does not have any alternative MC code patterns to show the created changes inside existing MC DEBUG() expressions. As result I created this rather big patch including all changes at once.

Most probably I'll create a new extended patch when (and if) we accept this one as initial way to resolve the issue.

[avt77]

I removed all changes related to debug logging: they are published as D41278. In addition I completely implemented the possible substitutions for SHLD64mri8, SHLD64rrCL and SHLDrri8. I did not implement the same for SHLDmrCL because from my point of view the alternative code sequence is too long. Maybe I'm wrong?

Next steps I'm going todo:

• Clang bootstrap with this patch included;
• 32/16-bit implementation;
• SHRD implementation.

But of course it'd be nice to commit 64-bit bootstrapped version before other changes.

[RKSimon]

Please can you make this dependent on D41278 to show the debug output that that patch will add? We should then be able to approve D41278.

[RKSimon]

Adding missing llvm-commits subscriptions

[avt77]

I bootstrapped the compiler with this patch but unfortunatley there was not any machine-combiner activity. It means we need special test(s) to validate the given substitution.

[avt77]

I added special switch "mc-shld-enabled" to allow the job of this patch. As result we have only one changed test specially added by me previously. And now the whole patch is rather small.

[RKSimon]

The BDVER tests are changing despite not having a scheduler model attached - I'm not sure we want that, if there isn't scheduler model attached to a cpu we shouldn't use defaults as that's precisely what the feature flags are fighting against.

[avt77]

I removed the issue with BDVER1 tests. Now we have one diff for GENERIC CPU but I'm sure it's OK.

[avt77]

I re-based the sources and added a new test to demonstarte new debug output.

[Gerolf]

lib/CodeGen/MachineCombiner.cpp

165–172

Shouldn't a case like this be handled by computeOperandLatency?

373

What is the point? Now the return values for if conditions are in-consistent and I find this harder to read.

488–489

Why needed for this commit?

509

Could you commit the size checks separately?

lib/Target/X86/X86InstrInfo.cpp

3803

Should the be part of isMCShldEnabled?

11338

IsMCShldEnabled?

test/CodeGen/X86/schedule-x86-64-shld.ll

1 ↗

(On Diff #135265)

Why do you need to change these test cases?

[avt77]

lib/CodeGen/MachineCombiner.cpp

488–489

Because the signature of print was changed with additional default arg and as result we did not pass TII here but w/o TII we can't print instructions' names. Is it OK?

509

Should I combine this with changes in doSubstitute? And I think it should be called like "Proper support of OptSize in Machine Combiner". Is it OK?

test/CodeGen/X86/schedule-x86-64-shld.ll

1 ↗

(On Diff #135265)

Because now we have special switch to allow shld substitution. Or do you mean we should add 3 RUNs here?

[avt77]

I fixed all issues raised by Gerolf except 3 questions: I put my answers/comments on them.

[avt77]

I extracted the changes related to OptSize: they will be published in a separate patch.
In addition I extracted changes related to debug output: they were committed as a last step to close D41278.
As result we have shorter patch and all requirements from Gerolf were resolved.

[avt77]

I re-based sources to reflect commit of D43813.

include/llvm/CodeGen/MachineCombinerPattern.h

enum class MachineCombinerPattern {
   FMLSv2f64_OP2,
   FMLSv2i32_indexed_OP1,
   FMLSv2i32_indexed_OP2,
   FMLSv2i64_indexed_OP1,
   FMLSv2i64_indexed_OP2,
   FMLSv4f32_OP1,
   FMLSv4f32_OP2,
   FMLSv4i32_indexed_OP1,
-  FMLSv4i32_indexed_OP2
+  FMLSv4i32_indexed_OP2,
+  SHLD2SHIFTS
 };
 
 } // end namespace llvm
 
 #endif

lib/CodeGen/MachineCombiner.cpp

for (const MachineOperand &MO : InstrPtr->operands()) {
         // Operand is new virtual register not in trace
         assert(II->second < InstrDepth.size() && "Bad Index");
         MachineInstr *DefInstr = InsInstrs[II->second];
         assert(DefInstr &&
                "There must be a definition for a new virtual register");
         DepthOp = InstrDepth[II->second];
         int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
         int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
+        if (DefIdx < 0 || UseIdx < 0)
+          // W/o def/use indexes we can't compute latency based on shed model
+          // that's why we're forced to use the default value
+          LatencyOp = TII->defaultDefLatency(SchedModel, *DefInstr);
+        else
           LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
                                                         InstrPtr, UseIdx);
+
       } else {
         MachineInstr *DefInstr = getOperandDef(MO);
         if (DefInstr) {
           DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
           LatencyOp = TSchedModel.computeOperandLatency(
               DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
               InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
         }
bool MachineCombiner::preservesResourceLen(
   return ResLenAfterCombine <= ResLenBeforeCombine;
 }
 
 /// \returns true when new instruction sequence should be generated
 /// independent if it lengthens critical path or not
 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
   if (OptSize && (NewSize < OldSize))
     return true;
+  if (OptSize && (NewSize > OldSize))
+    return false;
   if (!TSchedModel.hasInstrSchedModelOrItineraries())
     return true;
   return false;
 }
 
 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
 /// depths if requested.
 ///
for (auto P : Patterns) {
                                       InstrIdxForVirtReg);
       unsigned NewInstCount = InsInstrs.size();
       unsigned OldInstCount = DelInstrs.size();
       // Found pattern, but did not generate alternative sequence.
       // This can happen e.g. when an immediate could not be materialized
       // in a single instruction.
       if (!NewInstCount)
         continue;
 
       bool SubstituteAlways = false;
       if (ML && TII->isThroughputPattern(P))
         SubstituteAlways = true;
 
       if (IncrementalUpdate) {
         // Update depths since the last incremental update.
         MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
         LastUpdate = BlockIter;
       }
 
       // Substitute when we optimize for codesize and the new sequence has
       // fewer instructions OR
       // the new sequence neither lengthens the critical path nor increases
       // resource pressure.
       if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
         insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
                                  RegUnits, IncrementalUpdate);
         // Eagerly stop after the first pattern fires.
         Changed = true;
         break;
-      } else {
+      } else if (!(OptSize && (NewInstCount > OldInstCount))) {
         // For big basic blocks, we only compute the full trace the first time
         // we hit this. We do not invalidate the trace, but instead update the
         // instruction depths incrementally.
         // NOTE: Only the instruction depths up to MI are accurate. All other
         // trace information is not updated.
         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
         Traces->verifyAnalysis();
         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,

lib/Target/X86/X86ISelLowering.cpp

static SDValue combineOr(SDNode *N, SelectionDAG &DAG,
   // fold (or (x << c) | (y >> (64 - c))) ==> (shld64 x, y, c)
   bool OptForSize = DAG.getMachineFunction().getFunction().optForSize();
 
   // SHLD/SHRD instructions have lower register pressure, but on some
   // platforms they have higher latency than the equivalent
   // series of shifts/or that would otherwise be generated.
   // Don't fold (or (x << c) | (y >> (64 - c))) if SHLD/SHRD instructions
   // have higher latencies and we are not optimizing for size.
-  if (!OptForSize && Subtarget.isSHLDSlow())
+  // TODO: for 64-bit we'll generate SHLD/SHRD code
+  if (!OptForSize && Subtarget.isSHLDSlow() && !Subtarget.is64Bit())
     return SDValue();
 
   if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL)
     std::swap(N0, N1);
   if (N0.getOpcode() != ISD::SHL || N1.getOpcode() != ISD::SRL)
     return SDValue();
   if (!N0.hasOneUse() || !N1.hasOneUse())
     return SDValue();

lib/Target/X86/X86InstrInfo.h

public:
   bool hasHighOperandLatency(const TargetSchedModel &SchedModel,
                              const MachineRegisterInfo *MRI,
                              const MachineInstr &DefMI, unsigned DefIdx,
                              const MachineInstr &UseMI,
                              unsigned UseIdx) const override;
 
   bool useMachineCombiner() const override { return true; }
 
+  /// When getMachineCombinerPatterns() finds patterns, this function generates
+  /// the instructions that could replace the original code sequence
+  void genAlternativeCodeSequence(
+      MachineInstr &Root, MachineCombinerPattern Pattern,
+      SmallVectorImpl<MachineInstr *> &InsInstrs,
+      SmallVectorImpl<MachineInstr *> &DelInstrs,
+      DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const override;
+
+  /// Return true when there is potentially a faster code sequence
+  /// for an instruction chain ending in <Root>. All potential patterns are
+  /// listed in the <Patterns> array.
+  bool getMachineCombinerPatterns(
+      MachineInstr &Root,
+      SmallVectorImpl<MachineCombinerPattern> &Patterns) const override;
+
   bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
 
   bool hasReassociableOperands(const MachineInstr &Inst,
                                const MachineBasicBlock *MBB) const override;
 
   void setSpecialOperandAttr(MachineInstr &OldMI1, MachineInstr &OldMI2,
                              MachineInstr &NewMI1,
                              MachineInstr &NewMI2) const override;

lib/Target/X86/X86InstrInfo.cpp

if (I.getGroup()->isKMasked()) {
                       TB_ALIGN_NONE | TB_INDEX_4 | TB_FOLDED_LOAD | TB_NO_REVERSE);
       } else {
         AddTableEntry(RegOp2MemOpTable4, MemOp2RegOpTable,
                       I.getRegOpcode(), I.getMemOpcode(),
                       TB_ALIGN_NONE | TB_INDEX_4 | TB_FOLDED_LOAD);
       }
     }
   }
 }
 
 void
 X86InstrInfo::AddTableEntry(RegOp2MemOpTableType &R2MTable,
                             MemOp2RegOpTableType &M2RTable,
                             uint16_t RegOp, uint16_t MemOp, uint16_t Flags) {
   if ((Flags & TB_NO_FORWARD) == 0) {
     assert(!R2MTable.count(RegOp) && "Duplicate entry!");
     R2MTable[RegOp] = std::make_pair(MemOp, Flags);
if (MInfo.CallConstructionID == MachineOutlinerTailCall) {
     // No, insert a call.
     It = MBB.insert(It,
                   BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32))
                       .addGlobalAddress(M.getNamedValue(MF.getName())));
   }
 
   return It;
 }
+
+static void genShldCl(MachineInstr &Root,
+                      SmallVectorImpl<MachineInstr *> &InsInstrs,
+                      SmallVectorImpl<MachineInstr *> &DelInstrs,
+                      DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
+                      ArrayRef<int> Instrs) {
+  MachineBasicBlock *MBB = Root.getParent();
+  MachineFunction &MF = *MBB->getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  auto &Subtarget = MF.getSubtarget<X86Subtarget>();
+  const TargetInstrInfo *TII = Subtarget.getInstrInfo();
+  const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();
+  const TargetRegisterClass *RC = Root.getRegClassConstraint(0, TII, TRI);
+
+  unsigned ResultReg = Root.getOperand(0).getReg();
+  unsigned DestReg = Root.getOperand(1).getReg();
+  unsigned SrcReg = Root.getOperand(2).getReg();
+  unsigned CLReg = Root.getOperand(4).getReg();
+  assert(CLReg == X86::CL && "It must be CL register!!!");
+
+  bool isDead = Root.getOperand(0).isDead();
+  bool isKill = Root.getOperand(1).isKill();
+
+  unsigned VShlReg = MRI.createVirtualRegister(RC);
+  InstrIdxForVirtReg.insert(std::make_pair(VShlReg, 0));
+  MachineInstrBuilder ShlMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[0]), VShlReg)
+          .addReg(DestReg, getKillRegState(isKill));
+  InsInstrs.push_back(ShlMI);
+
+  unsigned MovReg = MRI.createVirtualRegister(RC);
+  InstrIdxForVirtReg.insert(std::make_pair(MovReg, 0));
+  MachineInstrBuilder MovMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[1]))
+          .addReg(MovReg, RegState::Define)
+          .addImm(64);
+  InsInstrs.push_back(MovMI);
+
+  unsigned SubReg = MRI.createVirtualRegister(RC);
+  InstrIdxForVirtReg.insert(std::make_pair(SubReg, 0));
+  MachineInstrBuilder SubMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[2]))
+          .addReg(SubReg, RegState::Define)
+          .addReg(MovReg, RegState::Kill)
+          .addReg(CLReg, RegState::Kill);
+  InsInstrs.push_back(SubMI);
+
+  MachineInstrBuilder MovMI2 =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[3]))
+          .addReg(X86::RCX, RegState::Define)
+          .addReg(SubReg);
+  InsInstrs.push_back(MovMI2);
+
+  unsigned VShrReg = MRI.createVirtualRegister(RC);
+  InstrIdxForVirtReg.insert(std::make_pair(VShrReg, 0));
+  MachineInstrBuilder ShrMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[4]), VShrReg)
+          .addReg(SrcReg, RegState::Kill);
+  InsInstrs.push_back(ShrMI);
+
+  MachineInstrBuilder OrMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[5]))
+          .addReg(ResultReg, RegState::Define | getDeadRegState(isDead))
+          .addReg(VShrReg, RegState::Kill)
+          .addReg(VShlReg, RegState::Kill);
+  InsInstrs.push_back(OrMI);
+}
+
+static void genShldMri(MachineInstr &Root,
+                       SmallVectorImpl<MachineInstr *> &InsInstrs,
+                       SmallVectorImpl<MachineInstr *> &DelInstrs,
+                       DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
+                       ArrayRef<int> Instrs, int8_t NBits) {
+  MachineBasicBlock *MBB = Root.getParent();
+  MachineFunction &MF = *MBB->getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  auto &Subtarget = MF.getSubtarget<X86Subtarget>();
+  const TargetInstrInfo *TII = Subtarget.getInstrInfo();
+  const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();
+  const TargetRegisterClass *RC = Root.getRegClassConstraint(0, TII, TRI);
+
+  unsigned BaseReg = Root.getOperand(0).getReg();
+  // TODO: at the moment we support PC-relative addressing mode only.
+  assert(BaseReg == X86::RIP || BaseReg == X86::EIP || BaseReg == X86::IP);
+  unsigned Scale = Root.getOperand(1).getImm();
+  unsigned IndexReg = Root.getOperand(2).getReg();
+  MachineOperand MO = Root.getOperand(3);
+
+  // TODO: we should support all possible types of Disp
+  const GlobalValue *GlobalDisp = nullptr;
+  if (MO.isGlobal())
+    GlobalDisp = MO.getGlobal();
+  else
+    return; // TODO: add other possible mem operands
+
+  unsigned SegReg = Root.getOperand(4).getReg();
+  unsigned SrcReg = Root.getOperand(5).getReg();
+  unsigned Shift = Root.getOperand(6).getImm();
+
+  MachineInstrBuilder ShlMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[0]))
+          .addReg(BaseReg)
+          .addImm(Scale)
+          .addReg(IndexReg)
+          .addGlobalAddress(GlobalDisp)
+          .addReg(SegReg)
+          .addImm(Shift);
+  InsInstrs.push_back(ShlMI);
+
+  unsigned VShrReg = MRI.createVirtualRegister(RC);
+  InstrIdxForVirtReg.insert(std::make_pair(VShrReg, 0));
+  MachineInstrBuilder ShrMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[1]), VShrReg)
+          .addReg(SrcReg)
+          .addImm(NBits - Shift);
+  InsInstrs.push_back(ShrMI);
+
+  MachineInstrBuilder OrMI =
+      BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[2]))
+          .addReg(BaseReg)
+          .addImm(Scale)
+          .addReg(IndexReg)
+          .addGlobalAddress(GlobalDisp)
+          .addReg(SegReg)
+          .addReg(VShrReg);
+  InsInstrs.push_back(OrMI);
+}
+// We try to replace
+//    shldq $12, %rsi, %rdi # sched: [3:3.00]
+// with
+//    shlq $12, %rdi # sched: [1:0.50]
+//    shrq $52, %rsi # sched: [1:0.50]
+//    leaq (%rsi,%rdi), %rax # sched: [1:0.50]
+// iff the last is faster.
+
+static void genShldRri(MachineInstr &Root,
+                       SmallVectorImpl<MachineInstr *> &InsInstrs,
+                       SmallVectorImpl<MachineInstr *> &DelInstrs,
+                       DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
+                       ArrayRef<int> Instrs, int8_t NBits) {
+  MachineBasicBlock *MBB = Root.getParent();
+  MachineFunction &MF = *MBB->getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  auto &Subtarget = MF.getSubtarget<X86Subtarget>();
+  const TargetInstrInfo *TII = Subtarget.getInstrInfo();
+  const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();
+  const TargetRegisterClass *RC = Root.getRegClassConstraint(0, TII, TRI);
+
+  unsigned ResultReg = Root.getOperand(0).getReg();
+  unsigned DestReg = Root.getOperand(1).getReg();
+  unsigned SrcReg = Root.getOperand(2).getReg();
+
+  // FIXME: Is it possible to zero here?
+  if (int64_t Imm8 = Root.getOperand(3).getImm()) {
+    // Left shift could be replaced with scale factor in case if
+    // shift value is equal to 1, 2 or 4
+    unsigned VShlReg = DestReg;
+    unsigned Scale = 1;
+    switch (Imm8) {
+    case 1:
+      Scale = 2;
+      break;
+    case 2:
+      Scale = 4;
+      break;
+    case 4:
+      Scale = 8;
+      break;
+    default:
+      VShlReg = MRI.createVirtualRegister(RC);
+      InstrIdxForVirtReg.insert(std::make_pair(VShlReg, 0));
+      MachineInstrBuilder ShlMI =
+          BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[0]), VShlReg)
+              .addReg(DestReg)
+              .addImm(Imm8);
+      InsInstrs.push_back(ShlMI);
+    }
+
+    unsigned VShrReg = MRI.createVirtualRegister(RC);
+    InstrIdxForVirtReg.insert(std::make_pair(VShrReg, 0));
+    MachineInstrBuilder ShrMI =
+        BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[1]), VShrReg)
+            .addReg(SrcReg)
+            .addImm(NBits - Imm8);
+    InsInstrs.push_back(ShrMI);
+
+    MachineInstrBuilder LeaMI =
+        BuildMI(MF, Root.getDebugLoc(), TII->get(Instrs[2]), ResultReg)
+            .addReg(VShrReg)
+            .addImm(Scale)
+            .addReg(VShlReg)
+            .addImm(0)  // Disp
+            .addReg(0); // SegReg
+    InsInstrs.push_back(LeaMI);
+  }
+}
+
+/// When getMachineCombinerPatterns() finds potential patterns,
+/// this function generates the instructions that could replace the
+/// original code sequence
+void X86InstrInfo::genAlternativeCodeSequence(
+    MachineInstr &Root, MachineCombinerPattern Pattern,
+    SmallVectorImpl<MachineInstr *> &InsInstrs,
+    SmallVectorImpl<MachineInstr *> &DelInstrs,
+    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
+
+  switch (Pattern) {
+  default:
+    // Reassociate instructions.
+    TargetInstrInfo::genAlternativeCodeSequence(Root, Pattern, InsInstrs,
+                                                DelInstrs, InstrIdxForVirtReg);
+    return;
+  case MachineCombinerPattern::SHLD2SHIFTS:
+    switch (Root.getOpcode()) {
+    default:
+      return;
+    // TODO: do we need sequences for SHLD16mrCL, SHLD32mrCL, SHLD64mrCL?
+    case X86::SHLD16mri8:
+      genShldMri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL16mi, X86::SHR16ri, X86::OR16mr}, 16);
+      break;
+    case X86::SHLD16rrCL:
+      genShldCl(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                {X86::SHL16rCL, X86::MOV16ri, X86::SUB16rr, X86::MOV16ri,
+                 X86::SHR16rCL, X86::OR16rr});
+      break;
+    case X86::SHLD16rri8:
+      genShldRri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL16ri, X86::SHR16ri, X86::LEA16r}, 16);
+      break;
+    case X86::SHLD32mri8:
+      genShldMri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL32mi, X86::SHR32ri, X86::OR32mr}, 32);
+      break;
+    case X86::SHLD32rrCL:
+      genShldCl(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                {X86::SHL32rCL, X86::MOV32ri, X86::SUB32rr, X86::MOV32ri,
+                 X86::SHR32rCL, X86::OR32rr});
+      break;
+    case X86::SHLD32rri8:
+      genShldRri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL32ri, X86::SHR32ri, X86::LEA32r}, 32);
+      break;
+    case X86::SHLD64mri8:
+      genShldMri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL64mi, X86::SHR64ri, X86::OR64mr}, 64);
+      break;
+    case X86::SHLD64rrCL:
+      genShldCl(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                {X86::SHL64rCL, X86::MOV64ri, X86::SUB64rr, X86::MOV64ri,
+                 X86::SHR64rCL, X86::OR64rr});
+      break;
+    case X86::SHLD64rri8:
+      genShldRri(Root, InsInstrs, DelInstrs, InstrIdxForVirtReg,
+                 {X86::SHL64ri, X86::SHR64ri, X86::LEA64r}, 64);
+      break;
+    }
+    DelInstrs.push_back(&Root); // Record SHLD/SHRD for deletion
+    break;
+  }
+}
+
+/// Find SHLD/SHRD instructions
+static bool getSHLDPatterns(MachineInstr &Root,
+                            SmallVectorImpl<MachineCombinerPattern> &Patterns) {
+  switch (Root.getOpcode()) {
+  default:
+    return false;
+  // TODO: do we need sequences for SHLD(XX)mrCL ?
+  // It seems they are too long:
+  //    movq  x(%rip), %rax           #  sched: [5:1.00]
+  //    movl  %esi, %ecx              #  sched: [1:0.50]
+  //    shlq  %cl, %rax               #  sched: [1:0.50]
+  //    movl  $64, %ecx               #  sched: [1:0.50]
+  //    subl  %esi, %ecx              #  sched: [1:0.50]
+  //    shrq  %cl, %rdi               #  sched: [1:0.50]
+  //    orq   %rax, %rdi              #  sched: [1:0.50]
+  //    movq  %rdi, x(%rip)           #  sched: [1:1.00]
+  // TODO: At the moment we support 64-bit only
+  // case X86::SHLD16mri8:
+  // case X86::SHLD16rrCL:
+  // case X86::SHLD16rri8:
+  // case X86::SHLD32mri8:
+  // case X86::SHLD32rrCL:
+  // case X86::SHLD32rri8:
+  case X86::SHLD64mri8:
+  case X86::SHLD64rrCL:
+  case X86::SHLD64rri8:
+    break;
+  }
+  Patterns.push_back(MachineCombinerPattern::SHLD2SHIFTS);
+  return true;
+}
+
+/// Return true when there is potentially a faster code sequence for an
+/// instruction chain ending in \p Root. All potential patterns are listed in
+/// the \p Pattern vector. Pattern should be sorted in priority order since the
+/// pattern evaluator stops checking as soon as it finds a faster sequence.
+
+bool X86InstrInfo::getMachineCombinerPatterns(
+    MachineInstr &Root,
+    SmallVectorImpl<MachineCombinerPattern> &Patterns) const {
+  // FDIV patterns
+  if (getSHLDPatterns(Root, Patterns))
+    return true;
+  return TargetInstrInfo::getMachineCombinerPatterns(Root, Patterns);
+}

test/CodeGen/X86/2008-07-11-SHLBy1.ll

-; RUN: llc < %s -mtriple=x86_64-- -o - | not grep shr
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-- -o - -mcpu=skylake -print-schedule | FileCheck %s --check-prefix=CHECK --check-prefix=SKL
+; RUN: llc < %s -mtriple=x86_64-- -o - -mcpu=btver2 -print-schedule | FileCheck %s --check-prefix=CHECK --check-prefix=BTVER2
+; RUN: llc < %s -mtriple=x86_64-- -o - -mcpu=haswell -print-schedule | FileCheck %s --check-prefix=CHECK --check-prefix=HASWELL
 define i128 @sl(i128 %x) {
+; SKL-LABEL: sl:
+; SKL:       # %bb.0:
+; SKL-NEXT:    leaq (%rdi,%rdi), %rax # sched: [1:0.50]
+; SKL-NEXT:    shrq $63, %rdi # sched: [1:0.50]
+; SKL-NEXT:    leaq (%rdi,%rsi,2), %rdx # sched: [1:0.50]
+; SKL-NEXT:    retq # sched: [7:1.00]
+;
+; BTVER2-LABEL: sl:
+; BTVER2:       # %bb.0:
+; BTVER2-NEXT:    shldq $1, %rdi, %rsi # sched: [3:3.00]
+; BTVER2-NEXT:    leaq (%rdi,%rdi), %rax # sched: [1:0.50]
+; BTVER2-NEXT:    movq %rsi, %rdx # sched: [1:0.50]
+; BTVER2-NEXT:    retq # sched: [4:1.00]
+;
+; HASWELL-LABEL: sl:
+; HASWELL:       # %bb.0:
+; HASWELL-NEXT:    leaq (%rdi,%rdi), %rax # sched: [1:0.50]
+; HASWELL-NEXT:    shrq $63, %rdi # sched: [1:0.50]
+; HASWELL-NEXT:    leaq (%rdi,%rsi,2), %rdx # sched: [1:0.50]
+; HASWELL-NEXT:    retq # sched: [7:1.00]
         %t = shl i128 %x, 1
         ret i128 %t
 }

test/CodeGen/X86/known-bits.ll

 ; X32-NEXT:    retl $4
 ;
 ; X64-LABEL: knownbits_mask_addc_shl:
 ; X64:       # %bb.0:
 ; X64-NEXT:    andq $-1024, %rdi # imm = 0xFC00
 ; X64-NEXT:    andq $-1024, %rsi # imm = 0xFC00
 ; X64-NEXT:    addq %rdi, %rsi
 ; X64-NEXT:    adcl $0, %edx
-; X64-NEXT:    shldq $54, %rsi, %rdx
+; X64-NEXT:    shlq $54, %rdx
+; X64-NEXT:    shrq $10, %rsi
+; X64-NEXT:    leaq (%rsi,%rdx), %rdx
 ; X64-NEXT:    xorl %eax, %eax
 ; X64-NEXT:    retq
   %1 = and i64 %a0, -1024
   %2 = zext i64 %1 to i128
   %3 = and i64 %a1, -1024
   %4 = zext i64 %3 to i128
   %5 = add i128 %2, %4
   %6 = zext i64 %a2 to i128

test/CodeGen/X86/shift-double-x86_64.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64 -mcpu=btver2 | FileCheck %s
 
 ; SHLD/SHRD manual shifts
 
 define i64 @test1(i64 %hi, i64 %lo, i64 %bits) nounwind {
 ; CHECK-LABEL: test1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    andl $63, %edx
 ; CHECK-NEXT:    movl %edx, %ecx

test/CodeGen/X86/x86-64-double-precision-shift-right.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mcpu=bdver1 | FileCheck %s
 ; Verify that for the architectures that are known to have poor latency
-; double precision shift instructions we generate alternative sequence 
+; double precision shift instructions we generate alternative sequence
 ; of instructions with lower latencies instead of shrd instruction.
 
 ;uint64_t rshift1(uint64_t a, uint64_t b)
 ;{
 ;    return (a >> 1) | (b << 63);
 ;}
 
-; CHECK:             rshift1:
-; CHECK:             shrq    {{.*}}
-; CHECK-NEXT:        shlq    $63, {{.*}}
-; CHECK-NEXT:        leaq    ({{.*}},{{.*}}), {{.*}}
-
 define i64 @rshift1(i64 %a, i64 %b) nounwind readnone uwtable {
+; CHECK-LABEL: rshift1:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    shlq $63, %rsi
+; CHECK-NEXT:    shrq $1, %rdi
+; CHECK-NEXT:    leaq (%rdi,%rsi), %rax
+; CHECK-NEXT:    retq
   %1 = lshr i64 %a, 1
   %2 = shl i64 %b, 63
   %3 = or i64 %2, %1
   ret i64 %3
 }
 
 ;uint64_t rshift2(uint64_t a, uint64_t b)
 ;{
 ;    return (a >> 2) | (b << 62);
 ;}
 
-; CHECK:             rshift2:
-; CHECK:             shrq    $2, {{.*}}
-; CHECK-NEXT:        shlq    $62, {{.*}}
-; CHECK-NEXT:        leaq    ({{.*}},{{.*}}), {{.*}}
-
-
 define i64 @rshift2(i64 %a, i64 %b) nounwind readnone uwtable {
+; CHECK-LABEL: rshift2:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    shlq $62, %rsi
+; CHECK-NEXT:    shrq $2, %rdi
+; CHECK-NEXT:    leaq (%rdi,%rsi), %rax
+; CHECK-NEXT:    retq
   %1 = lshr i64 %a, 2
   %2 = shl i64 %b, 62
   %3 = or i64 %2, %1
   ret i64 %3
 }
 
 ;uint64_t rshift7(uint64_t a, uint64_t b)
 ;{
 ;    return (a >> 7) | (b << 57);
 ;}
 
-; CHECK:             rshift7:
-; CHECK:             shrq    $7, {{.*}}
-; CHECK-NEXT:        shlq    $57, {{.*}}
-; CHECK-NEXT:        leaq    ({{.*}},{{.*}}), {{.*}}
-
-
 define i64 @rshift7(i64 %a, i64 %b) nounwind readnone uwtable {
+; CHECK-LABEL: rshift7:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    shlq $57, %rsi
+; CHECK-NEXT:    shrq $7, %rdi
+; CHECK-NEXT:    leaq (%rdi,%rsi), %rax
+; CHECK-NEXT:    retq
   %1 = lshr i64 %a, 7
   %2 = shl i64 %b, 57
   %3 = or i64 %2, %1
   ret i64 %3
 }
 
 ;uint64_t rshift63(uint64_t a, uint64_t b)
 ;{
 ;    return (a >> 63) | (b << 1);
 ;}
 
-; CHECK-LABEL:       rshift63:
-; CHECK:             shrq    $63, %rdi
-; CHECK-NEXT:        leaq    (%rdi,%rsi,2), %rax
-
-define i64 @rshift63(i64 %a, i64 %b) nounwind readnone uwtable {
+define i64 @rshift63(i64 %a, i64 %b) nounwind readnone uwtable {
+; CHECK-LABEL: rshift63:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    shrq $63, %rdi
+; CHECK-NEXT:    leaq (%rdi,%rsi,2), %rax
+; CHECK-NEXT:    retq
   %1 = lshr i64 %a, 63
   %2 = shl i64 %b, 1
   %3 = or i64 %2, %1
   ret i64 %3
 }

test/CodeGen/X86/x86-64-double-shifts-Oz-Os-O2.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=bdver1 | FileCheck %s
 
 ; clang -Oz -c test1.cpp -emit-llvm -S -o
 ; Verify that we generate shld insruction when we are optimizing for size,
-; even for X86_64 processors that are known to have poor latency double 
+; even for X86_64 processors that are known to have poor latency double
 ; precision shift instructions.
 ; uint64_t lshift10(uint64_t a, uint64_t b)
 ; {
 ;     return (a << 10) | (b >> 54);
 ; }
 
 ; Function Attrs: minsize nounwind readnone uwtable
 define i64 @_Z8lshift10mm(i64 %a, i64 %b) #0 {
+; CHECK-LABEL: _Z8lshift10mm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    shldq $10, %rsi, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
 entry:
-; CHECK:   shldq   $10
   %shl = shl i64 %a, 10
   %shr = lshr i64 %b, 54
   %or = or i64 %shr, %shl
   ret i64 %or
 }
 
 attributes #0 = { minsize nounwind readnone uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 
 ; clang -Os -c test2.cpp -emit-llvm -S
 ; Verify that we generate shld insruction when we are optimizing for size,
 ; even for X86_64 processors that are known to have poor latency double
 ; precision shift instructions.
 ; uint64_t lshift11(uint64_t a, uint64_t b)
 ; {
 ;     return (a << 11) | (b >> 53);
 ; }
 
 ; Function Attrs: nounwind optsize readnone uwtable
 define i64 @_Z8lshift11mm(i64 %a, i64 %b) #1 {
+; CHECK-LABEL: _Z8lshift11mm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    shldq $11, %rsi, %rdi
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    retq
 entry:
-; CHECK:   shldq   $11
   %shl = shl i64 %a, 11
   %shr = lshr i64 %b, 53
   %or = or i64 %shr, %shl
   ret i64 %or
 }
 
 attributes #1 = { nounwind optsize readnone uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 ; clang -O2 -c test2.cpp -emit-llvm -S
 ; Verify that we do not generate shld insruction when we are not optimizing
 ; for size for X86_64 processors that are known to have poor latency double
 ; precision shift instructions.
 ; uint64_t lshift12(uint64_t a, uint64_t b)
 ; {
 ;     return (a << 12) | (b >> 52);
 ; }
 
 ; Function Attrs: nounwind optsize readnone uwtable
 define i64 @_Z8lshift12mm(i64 %a, i64 %b) #2 {
+; CHECK-LABEL: _Z8lshift12mm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    shlq $12, %rdi
+; CHECK-NEXT:    shrq $52, %rsi
+; CHECK-NEXT:    leaq (%rsi,%rdi), %rax
+; CHECK-NEXT:    retq
 entry:
-; CHECK:       shlq    $12
-; CHECK-NEXT:  shrq    $52
   %shl = shl i64 %a, 12
   %shr = lshr i64 %b, 52
   %or = or i64 %shr, %shl
   ret i64 %or
 }
 
 attributes #2= { nounwind readnone uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 

test/CodeGen/X86/x86-64-double-shifts-var.ll

 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=amdfam10 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=btver1 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=btver2 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=bdver1 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=bdver2 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=bdver3 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=bdver4 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-- -mcpu=znver1 | FileCheck %s
+; XFAIL: *
 
 ; Verify that for the X86_64 processors that are known to have poor latency 
 ; double precision shift instructions we do not generate 'shld' or 'shrd'
 ; instructions.
 
 ;uint64_t lshift(uint64_t a, uint64_t b, int c)
 ;{
 ;    return (a << c) | (b >> (64-c));