[Machine Combiner] Refactor machine reassociation into a target-independent pass

[haicheng]

Summary

This patch refactors the machine reassociation pass into a target-independent pass. The only pass used by x86 now is this reassociation pass, not the machine combiner pass. There is no functional change in this patch. No change is found in the x86 assembly when complied with llvm-test-suite and spec2006.

This change address PR24522.

[mcrosier]

The intent of this patch is to remove the redundant code from the PPC backend and to expose the generic parts so that other backends (e.g., AArch64) can use this machinery. I've added Hal to assist/comment on the PPC changes, if he's interested.

[spatel]

I support refactoring the reassociation code to be target-independent, but I'm wondering: what is the benefit from making this a separate pass from MachineCombiner?

If I'm seeing it correctly, this patch has exactly duplicated a few hundred lines of code for MachineReassociation::reassociateInstructions() and its helpers from the existing pass.

[haicheng]

Thank you for your quick response, Sanjay.

This patch is trivial. As the next step, we will add the reassociation pass to other targets such as aarch64. In that case, aarch64 needs to run both reassociation and machine-combiner pass. We separate these two passes because of two reasons.

1. The machine-combiner pass searches and combines a pair of instructions (mul & add/sub), but the reassociation pass may optimize on a long chain of instructions. They may need different optimizations in the future (e.g. compilation time optimization).

2. If a target needs to run both passes, it may need different pattern enums. It might be ugly to put them in the same pass.

Please let us know your opinion.

[spatel]

In D12887#247071, @haicheng wrote:

1. The machine-combiner pass searches and combines a pair of instructions (mul & add/sub), but the reassociation pass may optimize on a long chain of instructions. They may need different optimizations in the future (e.g. compilation time optimization).

2. If a target needs to run both passes, it may need different pattern enums. It might be ugly to put them in the same pass.

Both of these are hypothetical problems that don't exist today. If these problems arise in practice, then certainly we could create a new pass to deal with them, but that should be a separate step IMO.

For this patch, I think we should just be refactoring the reassociation functions to live in MachineCombiner. That way, we eliminate the duplicated code from the x86 + PPC backends without duplicating all of the code that's already in MachineCombiner.

[Gerolf]

+1

[haicheng]

Thank you, Sanjay and Gerolf.

This time I refactor into the machine combiner pass. Verified again with llvm-test-suite and spec2006 that there is no functional change.

[spatel]

In D12887#247990, @haicheng wrote:

Thank you, Sanjay and Gerolf.

This time I refactor into the machine combiner pass. Verified again with llvm-test-suite and spec2006 that there is no functional change.

Thanks, Haicheng! This is much closer to what I imagined the refactoring would look like. :)

1. I don't think we need to distinguish between useMachineCombiner and useMachineReassociation. The reassociation patterns are just a subset of the combiner patterns. You can move what you are currently calling getMachineReassociationPatterns and genAlterReassocCodeSequence into the TargetInstrInfo base class implementations of getMachineCombinerPatterns and genAlternativeCodeSequence. Then the target overrides for those functions can choose to call the base implementation or not. When it's time to turn on the reassociation optimization for AArch, you just add a call to the base implementation ahead of the target-specific code that's already there. This will allow you to remove the isReassociation variable and associated if-checks in combineInstructions.

2. reassociateOps is still a bunch of target-independent duplicated code for PPC and x86. Can you pull that into MachineCombiner and make setSpecialOperandAttr a virtual function? It would only be overridden by x86 for now, but AArch might want to override that too.

[haicheng]

Thank you for your detailed comments, Sanjay. I did as what you suggested. Please check.

[Gerolf]

LGTM.

lib/CodeGen/TargetInstrInfo.cpp

550 ↗

(On Diff #35125)

There is a lot of duplication in the comments. You could define the rules for reassociation once and simply refer to it. You could think of formalizing them and use them as verifier when the actual transformation happens.

563 ↗

(On Diff #35125)

It would be consistent with other functions if you pulled them out before the prototype.

[spatel]

LGTM too. Just a few inline nits.

include/llvm/CodeGen/MachineCombinerPattern.h

35

The comment should say that these are AArch64 patterns. It might even be worth making that explicit in the names like:
MC_AARCH64_MULADDW_OP1
but that can be a follow-on change since it will mean changing the AArch code.

include/llvm/Target/TargetInstrInfo.h

739

Extra line.

lib/CodeGen/TargetInstrInfo.cpp

630 ↗

(On Diff #35125)

I'm biased of course, but I think it's easier to understand the logic when the rows of the array are actually on different rows in the source.

[spatel]

include/llvm/CodeGen/MachineCombinerPattern.h

36–48

Forgot to mention: the AArch patterns should not specify an enum value directly. The reassociation patterns must specify a value from 0-3 because we use those values as indexes into an array (that's rather hacky, but changing it would be another follow-on commit).

[haicheng]

Fix the comments and other minor things. Thank you, everyone.

[spatel]

Marking review as closed; Chad committed this for Haicheng at r248164.

[mcrosier]

In D12887#250751, @spatel wrote:

Marking review as closed; Chad committed this for Haicheng at r248164.

Thanks, Sanjay. I meant to ask Haicheng to do the same, but it slipped my mind.

include/llvm/CodeGen/MachineCombinerPattern.h

 
 namespace llvm {
 
 /// Enumeration of instruction pattern supported by machine combiner
 ///
 ///
 namespace MachineCombinerPattern {
 // Forward declaration
-enum MC_PATTERN : int;
+enum MC_PATTERN : int {
+  // specific for reassociation
+  MC_REASSOC_AX_BY = 0,
+  MC_REASSOC_AX_YB = 1,
+  MC_REASSOC_XA_BY = 2,
+  MC_REASSOC_XA_YB = 3,
+
+  // AArch64 specific for combining mul & add/sub
+  MC_NONE = 4,
+  MC_MULADDW_OP1 = 5,
+  MC_MULADDW_OP2 = 6,
+  MC_MULSUBW_OP1 = 7,
+  MC_MULSUBW_OP2 = 8,
+  MC_MULADDWI_OP1 = 9,
+  MC_MULSUBWI_OP1 = 10,
+  MC_MULADDX_OP1 = 11,
+  MC_MULADDX_OP2 = 12,
+  MC_MULSUBX_OP1 = 13,
+  MC_MULSUBX_OP2 = 14,
+  MC_MULADDXI_OP1 = 15,
+  MC_MULSUBXI_OP1 = 16,
+};
 } // end namespace MachineCombinerPattern
 } // end namespace llvm
 
 #endif

include/llvm/Target/TargetInstrInfo.h

MachineInstr *foldMemoryOperand(MachineBasicBlock::iterator MI,
                                   ArrayRef<unsigned> Ops, int FrameIndex) const;
 
   /// Same as the previous version except it allows folding of any load and
   /// store from / to any address, not just from a specific stack slot.
   MachineInstr *foldMemoryOperand(MachineBasicBlock::iterator MI,
                                   ArrayRef<unsigned> Ops,
                                   MachineInstr *LoadMI) const;
 
+  /// Return true when a target supports MachineCombiner.
+  virtual bool useMachineCombiner() const { return false; }
+
   /// Return true when there is potentially a faster code sequence
   /// for an instruction chain ending in \p Root. All potential patterns are
   /// returned 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.
   /// \param Root - Instruction that could be combined with one of its operands
   /// \param Pattern - Vector of possible combination patterns
   virtual bool getMachineCombinerPatterns(
       MachineInstr &Root,
       SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Pattern) const {
     return false;
   }
 
   /// When getMachineCombinerPatterns() finds patterns, this function generates
   /// the instructions that could replace the original code sequence. The client
   /// has to decide whether the actual replacement is beneficial or not.
   /// \param Root - Instruction that could be combined with one of its operands
   /// \param Pattern - Combination pattern for Root
   /// \param InsInstrs - Vector of new instructions that implement P
   /// \param DelInstrs - Old instructions, including Root, that could be
   /// replaced by InsInstr
   /// \param InstrIdxForVirtReg - map of virtual register to instruction in
   /// InsInstr that defines it
   virtual void genAlternativeCodeSequence(
       MachineInstr &Root, MachineCombinerPattern::MC_PATTERN Pattern,
       SmallVectorImpl<MachineInstr *> &InsInstrs,
       SmallVectorImpl<MachineInstr *> &DelInstrs,
       DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
     return;
   }
 
-  /// Return true when a target supports MachineCombiner.
-  virtual bool useMachineCombiner() const { return false; }
+  /// Return true when a target supports MachineReassociation.
+  virtual bool useMachineReassociation(bool UnsafeFPMath) const {
+    return false;
+  }
+
+  /// Return true when \P Inst is both associative and commutative
+  virtual bool isAssociativeAndCommutative(const MachineInstr &Inst) const {
+    return false;
+  }
+
+  /// Return true when \P Inst has reassociable operands in the same \P MBB
+  virtual bool hasReassociableOperands(const MachineInstr &Inst,
+                                       const MachineBasicBlock *MBB) const {
+    return false;
+  }
+
+  /// Attempt to reassociate the instructions to reduce critical path length.
+  virtual void
+  reassociateOps(MachineInstr &Root, MachineInstr &Prev,
+                 MachineCombinerPattern::MC_PATTERN Pattern,
+                 SmallVectorImpl<MachineInstr *> &InsInstrs,
+                 SmallVectorImpl<MachineInstr *> &DelInstrs,
+                 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
+    return;
+  }
 
 protected:
   /// Target-dependent implementation for foldMemoryOperand.
   /// Target-independent code in foldMemoryOperand will
   /// take care of adding a MachineMemOperand to the newly created instruction.
   /// The instruction and any auxiliary instructions necessary will be inserted
   /// at InsertPt.
   virtual MachineInstr *foldMemoryOperandImpl(

lib/CodeGen/MachineCombiner.cpp

MachineCombiner() : MachineFunctionPass(ID) {
     initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   bool runOnMachineFunction(MachineFunction &MF) override;
   const char *getPassName() const override { return "Machine InstCombiner"; }
 
 private:
   bool doSubstitute(unsigned NewSize, unsigned OldSize);
-  bool combineInstructions(MachineBasicBlock *);
+  bool combineInstructions(MachineBasicBlock *, bool isReassociation);
   MachineInstr *getOperandDef(const MachineOperand &MO);
   unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
                     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
                     MachineTraceMetrics::Trace BlockTrace);
   unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
                       MachineTraceMetrics::Trace BlockTrace);
   bool
   improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
                            MachineTraceMetrics::Trace BlockTrace,
                            SmallVectorImpl<MachineInstr *> &InsInstrs,
                            DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
                            bool NewCodeHasLessInsts);
   bool preservesResourceLen(MachineBasicBlock *MBB,
                             MachineTraceMetrics::Trace BlockTrace,
                             SmallVectorImpl<MachineInstr *> &InsInstrs,
                             SmallVectorImpl<MachineInstr *> &DelInstrs);
   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
+
+  bool hasReassociableSibling(const MachineInstr &Inst, bool &Commuted);
+
+  bool isReassociationCandidate(const MachineInstr &Inst, bool &Commuted);
+
+  bool getMachineReassociationPatterns(
+      MachineInstr &Root,
+      SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Patterns);
+
+  void
+  genAlterReassocCodeSequence(MachineInstr &Root,
+                              MachineCombinerPattern::MC_PATTERN Pattern,
+                              SmallVectorImpl<MachineInstr *> &InsInstrs,
+                              SmallVectorImpl<MachineInstr *> &DelInstrs,
+                              DenseMap<unsigned, unsigned> &InstrIdxForVirtReg);
 };
 }
 
 char MachineCombiner::ID = 0;
 char &llvm::MachineCombinerID = MachineCombiner::ID;
 
 INITIALIZE_PASS_BEGIN(MachineCombiner, "machine-combiner",
                       "Machine InstCombiner", false, false)

 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
   if (OptSize && (NewSize < OldSize))
     return true;
   if (!TSchedModel.hasInstrSchedModelOrItineraries())
     return true;
   return false;
 }
 
+bool MachineCombiner::hasReassociableSibling(const MachineInstr &Inst,
+                                             bool &Commuted) {
+  const MachineBasicBlock *MBB = Inst.getParent();
+  const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
+  MachineInstr *MI1 = MRI.getUniqueVRegDef(Inst.getOperand(1).getReg());
+  MachineInstr *MI2 = MRI.getUniqueVRegDef(Inst.getOperand(2).getReg());
+  unsigned AssocOpcode = Inst.getOpcode();
+
+  // If only one operand has the same opcode and it's the second source operand,
+  // the operands must be commuted.
+  Commuted = MI1->getOpcode() != AssocOpcode && MI2->getOpcode() == AssocOpcode;
+  if (Commuted)
+    std::swap(MI1, MI2);
+
+  // 1. The previous instruction must be the same type as Inst.
+  // 2. The previous instruction must have virtual register definitions for its
+  //    operands in the same basic block as Inst.
+  // 3. The previous instruction's result must only be used by Inst.
+  if (MI1->getOpcode() == AssocOpcode &&
+      TII->hasReassociableOperands(*MI1, MBB) &&
+      MRI.hasOneNonDBGUse(MI1->getOperand(0).getReg()))
+    return true;
+
+  return false;
+}
+
+/// Return true if the input instruction is part of a chain of dependent ops
+/// that are suitable for reassociation, otherwise return false.
+/// If the instruction's operands must be commuted to have a previous
+/// instruction of the same type define the first source operand, Commuted will
+/// be set to true.
+bool MachineCombiner::isReassociationCandidate(const MachineInstr &Inst,
+                                               bool &Commuted) {
+  // 1. The operation must be associative and commutative.
+  // 2. The instruction must have virtual register definitions for its
+  //    operands in the same basic block.
+  // 3. The instruction must have a reassociable sibling.
+  if (TII->isAssociativeAndCommutative(Inst) &&
+      TII->hasReassociableOperands(Inst, Inst.getParent()) &&
+      hasReassociableSibling(Inst, Commuted))
+    return true;
+
+  return false;
+}
+
+/// Return true when there is potentially a faster code sequence
+/// for an instruction chain ending in <Root>. All potential patterns are
+/// output in the <Pattern> array.
+
+// FIXME: This has the potential to be expensive (compile time) while not
+// improving the code at all. Some ways to limit the overhead:
+// 1. Track successful transforms; bail out if hit rate gets too low.
+// 2. Only enable at -O3 or some other non-default optimization level.
+// 3. Pre-screen pattern candidates here: if an operand of the previous
+//    instruction is known to not increase the critical path, then don't match
+//    that pattern.
+bool MachineCombiner::getMachineReassociationPatterns(
+    MachineInstr &Root,
+    SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Patterns) {
+  // Look for this reassociation pattern:
+  //   B = A op X (Prev)
+  //   C = B op Y (Root)
+  bool Commute;
+  if (isReassociationCandidate(Root, Commute)) {
+    // We found a sequence of instructions that may be suitable for a
+    // reassociation of operands to increase ILP. Specify each commutation
+    // possibility for the Prev instruction in the sequence and let the
+    // machine combiner decide if changing the operands is worthwhile.
+    if (Commute) {
+      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_YB);
+      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_YB);
+    } else {
+      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_BY);
+      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_BY);
+    }
+    return true;
+  }
+
+  return false;
+}
+
+/// When getMachineCombinerPatterns() finds a pattern, this function generates
+/// the instructions that could replace the original code sequence.
+void MachineCombiner::genAlterReassocCodeSequence(
+    MachineInstr &Root, MachineCombinerPattern::MC_PATTERN Pattern,
+    SmallVectorImpl<MachineInstr *> &InsInstrs,
+    SmallVectorImpl<MachineInstr *> &DelInstrs,
+    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) {
+
+  MachineRegisterInfo &MRI = Root.getParent()->getParent()->getRegInfo();
+
+  // Select the previous instruction in the sequence based on the input pattern.
+  MachineInstr *Prev = nullptr;
+  switch (Pattern) {
+  case MachineCombinerPattern::MC_REASSOC_AX_BY:
+  case MachineCombinerPattern::MC_REASSOC_XA_BY:
+    Prev = MRI.getUniqueVRegDef(Root.getOperand(1).getReg());
+    break;
+  case MachineCombinerPattern::MC_REASSOC_AX_YB:
+  case MachineCombinerPattern::MC_REASSOC_XA_YB:
+    Prev = MRI.getUniqueVRegDef(Root.getOperand(2).getReg());
+    break;
+  default:
+    break;
+  }
+  assert(Prev && "Unknown pattern for machine reassociation");
+
+  TII->reassociateOps(Root, *Prev, Pattern, InsInstrs, DelInstrs,
+                      InstrIdxForVirtReg);
+
+  return;
+}
+
 /// Substitute a slow code sequence with a faster one by
 /// evaluating instruction combining pattern.
 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
 /// combining based on machine trace metrics. Only combine a sequence of
 /// instructions  when this neither lengthens the critical path nor increases
 /// resource pressure. When optimizing for codesize always combine when the new
 /// sequence is shorter.
-bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
+bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB,
+                                          bool isReassociation) {
   bool Changed = false;
   DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
 
   auto BlockIter = MBB->begin();
 
   while (BlockIter != MBB->end()) {
     auto &MI = *BlockIter++;
 
while (BlockIter != MBB->end()) {
     // critical path, don't use more resources) is met the new sequence gets
     // hooked up into the basic block before the old sequence is removed.
     //
     // The algorithm does not try to evaluate all patterns and pick the best.
     // This is only an artificial restriction though. In practice there is
     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
     // based on an internal cost heuristic.
 
-    if (TII->getMachineCombinerPatterns(MI, Patterns)) {
-      for (auto P : Patterns) {
-        SmallVector<MachineInstr *, 16> InsInstrs;
-        SmallVector<MachineInstr *, 16> DelInstrs;
-        DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
-        if (!MinInstr)
-          MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
-        MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
-        Traces->verifyAnalysis();
+    bool hasPatterns = false;
+
+    if (isReassociation)
+      hasPatterns = getMachineReassociationPatterns(MI, Patterns);
+    else
+      hasPatterns = TII->getMachineCombinerPatterns(MI, Patterns);
+
+    if (!hasPatterns)
+      continue;
+
+
+      if (isReassociation) {
+        genAlterReassocCodeSequence(MI, P, InsInstrs, DelInstrs,
+                                    InstrIdxForVirtReg);
+      } else {
         TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
                                         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;
-        // 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 (doSubstitute(NewInstCount, OldInstCount) ||
-            (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs,
-                                      InstrIdxForVirtReg,
-                                      NewInstCount < OldInstCount) &&
-             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs))) {
-          for (auto *InstrPtr : InsInstrs)
-            MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
-          for (auto *InstrPtr : DelInstrs)
-            InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
+      }
+
+          MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
 
-          Changed = true;
-          ++NumInstCombined;
 
-          Traces->invalidate(MBB);
-          Traces->verifyAnalysis();
-          // Eagerly stop after the first pattern fires.
-          break;
-        } else {
-          // Cleanup instructions of the alternative code sequence. There is no
-          // use for them.
-          MachineFunction *MF = MBB->getParent();
-          for (auto *InstrPtr : InsInstrs)
-            MF->DeleteMachineInstr(InstrPtr);
-        }
-        InstrIdxForVirtReg.clear();
-      }
-    }
-  }
 
   return Changed;
 }
 
 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   TII = STI.getInstrInfo();
   TRI = STI.getRegisterInfo();
   SchedModel = STI.getSchedModel();
   TSchedModel.init(SchedModel, &STI, TII);
   MRI = &MF.getRegInfo();
   Traces = &getAnalysis<MachineTraceMetrics>();
   MinInstr = 0;
   OptSize = MF.getFunction()->optForSize();
 
   DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
-  if (!TII->useMachineCombiner()) {
-    DEBUG(dbgs() << "  Skipping pass: Target does not support machine combiner\n");
+
+  bool UnsafeFPMath = MF.getTarget().Options.UnsafeFPMath;
+
+  if (!TII->useMachineCombiner() &&
+      !TII->useMachineReassociation(UnsafeFPMath)) {
+    DEBUG(dbgs()
+          << "  Skipping pass: Target does not support machine combiner\n");
     return false;
   }
 
   bool Changed = false;
 
   // Try to combine instructions.
-  for (auto &MBB : MF)
-    Changed |= combineInstructions(&MBB);
+  for (auto &MBB : MF) {
+    if (TII->useMachineCombiner())
+      Changed |= combineInstructions(&MBB, false);
+
+    if (TII->useMachineReassociation(UnsafeFPMath))
+      Changed |= combineInstructions(&MBB, true);
+  }
 
   return Changed;
 }

lib/Target/AArch64/AArch64InstrInfo.cpp

 //===- AArch64InstrInfo.cpp - AArch64 Instruction Information -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the AArch64 implementation of the TargetInstrInfo class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AArch64InstrInfo.h"
-#include "AArch64MachineCombinerPattern.h"
 #include "AArch64Subtarget.h"
 #include "MCTargetDesc/AArch64AddressingModes.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/MC/MCInst.h"

lib/Target/AArch64/AArch64MachineCombinerPattern.h

-//===- AArch64MachineCombinerPattern.h                                    -===//
-//===- AArch64 instruction pattern supported by combiner                  -===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines instruction pattern supported by combiner
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_LIB_TARGET_AARCH64_AARCH64MACHINECOMBINERPATTERN_H
-#define LLVM_LIB_TARGET_AARCH64_AARCH64MACHINECOMBINERPATTERN_H
-
-namespace llvm {
-
-/// Enumeration of instruction pattern supported by machine combiner
-///
-///
-namespace MachineCombinerPattern {
-enum MC_PATTERN : int {
-  MC_NONE = 0,
-  MC_MULADDW_OP1 = 1,
-  MC_MULADDW_OP2 = 2,
-  MC_MULSUBW_OP1 = 3,
-  MC_MULSUBW_OP2 = 4,
-  MC_MULADDWI_OP1 = 5,
-  MC_MULSUBWI_OP1 = 6,
-  MC_MULADDX_OP1 = 7,
-  MC_MULADDX_OP2 = 8,
-  MC_MULSUBX_OP1 = 9,
-  MC_MULSUBX_OP2 = 10,
-  MC_MULADDXI_OP1 = 11,
-  MC_MULSUBXI_OP1 = 12
-};
-} // end namespace MachineCombinerPattern
-} // end namespace llvm
-
-#endif

lib/Target/PowerPC/PPCInstrInfo.h

enum PPC970_Unit {
   PPC970_FPU    = 3 << PPC970_Shift,   // Floating Point Unit
   PPC970_CRU    = 4 << PPC970_Shift,   // Control Register Unit
   PPC970_VALU   = 5 << PPC970_Shift,   // Vector ALU
   PPC970_VPERM  = 6 << PPC970_Shift,   // Vector Permute Unit
   PPC970_BRU    = 7 << PPC970_Shift    // Branch Unit
 };
 } // end namespace PPCII
 
-namespace MachineCombinerPattern {
-enum MC_PATTERN : int {
-  // These are commutative variants for reassociating a computation chain
-  // of the form:
-  //   B = A op X (Prev)
-  //   C = B op Y (Root)
-  MC_REASSOC_AX_BY = 0,
-  MC_REASSOC_AX_YB = 1,
-  MC_REASSOC_XA_BY = 2,
-  MC_REASSOC_XA_YB = 3,
-};
-} // end namespace MachineCombinerPattern
-
 class PPCSubtarget;
 class PPCInstrInfo : public PPCGenInstrInfo {
   PPCSubtarget &Subtarget;
   const PPCRegisterInfo RI;
 
   bool StoreRegToStackSlot(MachineFunction &MF,
                            unsigned SrcReg, bool isKill, int FrameIdx,
                            const TargetRegisterClass *RC,
bool hasLowDefLatency(const TargetSchedModel &SchedModel,
                         const MachineInstr *DefMI,
                         unsigned DefIdx) const override {
     // Machine LICM should hoist all instructions in low-register-pressure
     // situations; none are sufficiently free to justify leaving in a loop
     // body.
     return false;
   }
 
-  bool useMachineCombiner() const override {
-    return true;
-  }
-  
-  /// Return true when there is potentially a faster code sequence
-  /// for an instruction chain ending in <Root>. All potential patterns are
-  /// output in the <Pattern> array.
-  bool getMachineCombinerPatterns(
-      MachineInstr &Root,
-      SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &P) const override;
-  
-  /// When getMachineCombinerPatterns() finds a pattern, this function generates
-  /// the instructions that could replace the original code sequence.
-  void genAlternativeCodeSequence(
-          MachineInstr &Root, MachineCombinerPattern::MC_PATTERN P,
-          SmallVectorImpl<MachineInstr *> &InsInstrs,
-          SmallVectorImpl<MachineInstr *> &DelInstrs,
-          DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const override;
+  bool useMachineCombiner() const override { return false; }
+
+  bool useMachineReassociation(bool UnsafeFPMath) const override;
+
+  /// Return true when Inst is both associative and commutative
+  bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
+
+  /// Return true when Inst has reassociable operands in the same MBB
+  bool hasReassociableOperands(const MachineInstr &Inst,
+                               const MachineBasicBlock *MBB) const override;
+  void reassociateOps(
+      MachineInstr &Root, MachineInstr &Prev,
+      MachineCombinerPattern::MC_PATTERN Pattern,
 
   bool isCoalescableExtInstr(const MachineInstr &MI,
                              unsigned &SrcReg, unsigned &DstReg,
                              unsigned &SubIdx) const override;
   unsigned isLoadFromStackSlot(const MachineInstr *MI,
                                int &FrameIndex) const override;
   unsigned isStoreToStackSlot(const MachineInstr *MI,
                               int &FrameIndex) const override;

lib/Target/PowerPC/PPCInstrInfo.cpp

case PPC::DIR_PWR8:
       Latency += 2;
       break;
     }
   }
 
   return Latency;
 }
 
-static bool hasVirtualRegDefsInBasicBlock(const MachineInstr &Inst,
-                                          const MachineBasicBlock *MBB) {
+bool PPCInstrInfo::useMachineReassociation(bool UnsafeFPMath) const {
+  // Using the machine combiner in this way is potentially expensive, so
+  // restrict to when aggressive optimizations are desired.
+  if (Subtarget.getTargetMachine().getOptLevel() != CodeGenOpt::Aggressive)
+    return false;
+
+  // FP reassociation is only legal when we don't need strict IEEE semantics.
+  return UnsafeFPMath;
+}
+
+bool PPCInstrInfo::hasReassociableOperands(const MachineInstr &Inst,
+                                           const MachineBasicBlock *MBB) const {
   const MachineOperand &Op1 = Inst.getOperand(1);
   const MachineOperand &Op2 = Inst.getOperand(2);
   const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 
   // We need virtual register definitions.
   MachineInstr *MI1 = nullptr;
   MachineInstr *MI2 = nullptr;
   if (Op1.isReg() && TargetRegisterInfo::isVirtualRegister(Op1.getReg()))
     MI1 = MRI.getUniqueVRegDef(Op1.getReg());
   if (Op2.isReg() && TargetRegisterInfo::isVirtualRegister(Op2.getReg()))
     MI2 = MRI.getUniqueVRegDef(Op2.getReg());
 
   // And they need to be in the trace (otherwise, they won't have a depth).
   if (MI1 && MI2 && MI1->getParent() == MBB && MI2->getParent() == MBB)
     return true;
 
   return false;
 }
 
-static bool hasReassocSibling(const MachineInstr &Inst, bool &Commuted) {
-  const MachineBasicBlock *MBB = Inst.getParent();
-  const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
-  MachineInstr *MI1 = MRI.getUniqueVRegDef(Inst.getOperand(1).getReg());
-  MachineInstr *MI2 = MRI.getUniqueVRegDef(Inst.getOperand(2).getReg());
-  unsigned AssocOpcode = Inst.getOpcode();
-
-  // If only one operand has the same opcode and it's the second source operand,
-  // the operands must be commuted.
-  Commuted = MI1->getOpcode() != AssocOpcode && MI2->getOpcode() == AssocOpcode;
-  if (Commuted)
-    std::swap(MI1, MI2);
-
-  // 1. The previous instruction must be the same type as Inst.
-  // 2. The previous instruction must have virtual register definitions for its
-  //    operands in the same basic block as Inst.
-  // 3. The previous instruction's result must only be used by Inst.
-  if (MI1->getOpcode() == AssocOpcode &&
-      hasVirtualRegDefsInBasicBlock(*MI1, MBB) &&
-      MRI.hasOneNonDBGUse(MI1->getOperand(0).getReg()))
-    return true;
-
-  return false;
-}
-
 // This function does not list all associative and commutative operations, but
 // only those worth feeding through the machine combiner in an attempt to
 // reduce the critical path. Mostly, this means floating-point operations,
 // because they have high latencies (compared to other operations, such and
 // and/or, which are also associative and commutative, but have low latencies).
 //
 // The concept is that these operations can benefit from this kind of
 // transformation:
 //
 // A = ? op ?
 // B = A op X
 // C = B op Y
 // -->
 // A = ? op ?
 // B = X op Y
 // C = A op B
 //
 // breaking the dependency between A and B, allowing them to be executed in
 // parallel (or back-to-back in a pipeline) instead of depending on each other.
-static bool isAssociativeAndCommutative(unsigned Opcode) {
-  switch (Opcode) {
+bool PPCInstrInfo::isAssociativeAndCommutative(const MachineInstr &Inst) const {
+  switch (Inst.getOpcode()) {
   // FP Add:
   case PPC::FADD:
   case PPC::FADDS:
   // FP Multiply:
   case PPC::FMUL:
   case PPC::FMULS:
   // Altivec Add:
   case PPC::VADDFP:
bool PPCInstrInfo::isAssociativeAndCommutative(const MachineInstr &Inst) const {
   case PPC::QVFMULS:
   case PPC::QVFMULSs:
     return true;
   default:
     return false;
   }
 }
 
-/// Return true if the input instruction is part of a chain of dependent ops
-/// that are suitable for reassociation, otherwise return false.
-/// If the instruction's operands must be commuted to have a previous
-/// instruction of the same type define the first source operand, Commuted will
-/// be set to true.
-static bool isReassocCandidate(const MachineInstr &Inst, bool &Commuted) {
-  // 1. The operation must be associative and commutative.
-  // 2. The instruction must have virtual register definitions for its
-  //    operands in the same basic block.
-  // 3. The instruction must have a reassociable sibling.
-  if (isAssociativeAndCommutative(Inst.getOpcode()) &&
-      hasVirtualRegDefsInBasicBlock(Inst, Inst.getParent()) &&
-      hasReassocSibling(Inst, Commuted))
-    return true;
-
-  return false;
-}
-
-bool PPCInstrInfo::getMachineCombinerPatterns(MachineInstr &Root,
-        SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Patterns) const {
-  // Using the machine combiner in this way is potentially expensive, so
-  // restrict to when aggressive optimizations are desired.
-  if (Subtarget.getTargetMachine().getOptLevel() != CodeGenOpt::Aggressive)
-    return false;
-
-  // FP reassociation is only legal when we don't need strict IEEE semantics.
-  if (!Root.getParent()->getParent()->getTarget().Options.UnsafeFPMath)
-    return false;
-
-  // Look for this reassociation pattern:
-  //   B = A op X (Prev)
-  //   C = B op Y (Root)
-
-  // FIXME: We should also match FMA operations here, where we consider the
-  // 'part' of the FMA, either the addition or the multiplication, paired with
-  // an actual addition or multiplication.
-
-  bool Commute;
-  if (isReassocCandidate(Root, Commute)) {
-    // We found a sequence of instructions that may be suitable for a
-    // reassociation of operands to increase ILP. Specify each commutation
-    // possibility for the Prev instruction in the sequence and let the
-    // machine combiner decide if changing the operands is worthwhile.
-    if (Commute) {
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_YB);
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_YB);
-    } else {
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_BY);
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_BY);
-    }
-    return true;
-  }
-
-  return false;
-}
-
 /// Attempt the following reassociation to reduce critical path length:
 ///   B = A op X (Prev)
 ///   C = B op Y (Root)
 ///   ===>
 ///   B = X op Y
 ///   C = A op B
-static void reassociateOps(MachineInstr &Root, MachineInstr &Prev,
-                           MachineCombinerPattern::MC_PATTERN Pattern,
-                           SmallVectorImpl<MachineInstr *> &InsInstrs,
-                           SmallVectorImpl<MachineInstr *> &DelInstrs,
-                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) {
+void PPCInstrInfo::reassociateOps(
+    MachineInstr &Root, MachineInstr &Prev,
+    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
   MachineFunction *MF = Root.getParent()->getParent();
   MachineRegisterInfo &MRI = MF->getRegInfo();
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
   const TargetRegisterClass *RC = Root.getRegClassConstraint(0, TII, TRI);
 
   // This array encodes the operand index for each parameter because the
   // operands may be commuted. Each row corresponds to a pattern value,
   // and each column specifies the index of A, B, X, Y.
   unsigned OpIdx[4][4] = {
-    { 1, 1, 2, 2 },
-    { 1, 2, 2, 1 },
-    { 2, 1, 1, 2 },
-    { 2, 2, 1, 1 }
+      {1, 1, 2, 2}, 
+      {1, 2, 2, 1}, 
+      {2, 1, 1, 2}, 
+      {2, 2, 1, 1}
   };
 
   MachineOperand &OpA = Prev.getOperand(OpIdx[Pattern][0]);
   MachineOperand &OpB = Root.getOperand(OpIdx[Pattern][1]);
   MachineOperand &OpX = Prev.getOperand(OpIdx[Pattern][2]);
   MachineOperand &OpY = Root.getOperand(OpIdx[Pattern][3]);
   MachineOperand &OpC = Root.getOperand(0);
 
void PPCInstrInfo::reassociateOps(
 
   unsigned Opcode = Root.getOpcode();
   bool KillA = OpA.isKill();
   bool KillX = OpX.isKill();
   bool KillY = OpY.isKill();
 
   // Create new instructions for insertion.
   MachineInstrBuilder MIB1 =
       BuildMI(*MF, Prev.getDebugLoc(), TII->get(Opcode), NewVR)
           .addReg(RegX, getKillRegState(KillX))
           .addReg(RegY, getKillRegState(KillY));
   InsInstrs.push_back(MIB1);
 
   MachineInstrBuilder MIB2 =
       BuildMI(*MF, Root.getDebugLoc(), TII->get(Opcode), RegC)
           .addReg(RegA, getKillRegState(KillA))
           .addReg(NewVR, getKillRegState(true));
   InsInstrs.push_back(MIB2);
 
   // Record old instructions for deletion.
   DelInstrs.push_back(&Prev);
   DelInstrs.push_back(&Root);
 }
 
-void PPCInstrInfo::genAlternativeCodeSequence(
-    MachineInstr &Root,
-    MachineCombinerPattern::MC_PATTERN Pattern,
-    SmallVectorImpl<MachineInstr *> &InsInstrs,
-    SmallVectorImpl<MachineInstr *> &DelInstrs,
-    DenseMap<unsigned, unsigned> &InstIdxForVirtReg) const {
-  MachineRegisterInfo &MRI = Root.getParent()->getParent()->getRegInfo();
-
-  // Select the previous instruction in the sequence based on the input pattern.
-  MachineInstr *Prev = nullptr;
-  switch (Pattern) {
-    case MachineCombinerPattern::MC_REASSOC_AX_BY:
-    case MachineCombinerPattern::MC_REASSOC_XA_BY:
-      Prev = MRI.getUniqueVRegDef(Root.getOperand(1).getReg());
-      break;
-    case MachineCombinerPattern::MC_REASSOC_AX_YB:
-    case MachineCombinerPattern::MC_REASSOC_XA_YB:
-      Prev = MRI.getUniqueVRegDef(Root.getOperand(2).getReg());
-  }
-  assert(Prev && "Unknown pattern for machine combiner");
-
-  reassociateOps(Root, *Prev, Pattern, InsInstrs, DelInstrs, InstIdxForVirtReg);
-  return;
-}
-
 // Detect 32 -> 64-bit extensions where we may reuse the low sub-register.
 bool PPCInstrInfo::isCoalescableExtInstr(const MachineInstr &MI,
                                          unsigned &SrcReg, unsigned &DstReg,
                                          unsigned &SubIdx) const {
   switch (MI.getOpcode()) {
   default: return false;
   case PPC::EXTSW:
   case PPC::EXTSW_32_64:

lib/Target/X86/X86InstrInfo.h

 
 #define GET_INSTRINFO_HEADER
 #include "X86GenInstrInfo.inc"
 
 namespace llvm {
   class X86RegisterInfo;
   class X86Subtarget;
 
-  namespace MachineCombinerPattern {
-    enum MC_PATTERN : int {
-      // These are commutative variants for reassociating a computation chain
-      // of the form:
-      //   B = A op X (Prev)
-      //   C = B op Y (Root)
-      MC_REASSOC_AX_BY = 0,
-      MC_REASSOC_AX_YB = 1,
-      MC_REASSOC_XA_BY = 2,
-      MC_REASSOC_XA_YB = 3,
-    };
-  } // end namespace MachineCombinerPattern
-
 namespace X86 {
   // X86 specific condition code. These correspond to X86_*_COND in
   // X86InstrInfo.td. They must be kept in synch.
   enum CondCode {
     COND_A  = 0,
     COND_AE = 1,
     COND_B  = 2,
     COND_BE = 3,
public:
   bool isHighLatencyDef(int opc) const override;
 
   bool hasHighOperandLatency(const TargetSchedModel &SchedModel,
                              const MachineRegisterInfo *MRI,
                              const MachineInstr *DefMI, unsigned DefIdx,
                              const MachineInstr *UseMI,
                              unsigned UseIdx) const override;
 
-  
-  bool useMachineCombiner() const override {
+  bool useMachineCombiner() const override { return false; }
+  bool useMachineReassociation(bool UnsafeFPMath) const override {
     return true;
   }
-  
-  /// Return true when there is potentially a faster code sequence
-  /// for an instruction chain ending in <Root>. All potential patterns are
-  /// output in the <Pattern> array.
-  bool getMachineCombinerPatterns(
-      MachineInstr &Root,
-      SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &P) const override;
-  
-  /// When getMachineCombinerPatterns() finds a pattern, this function generates
-  /// the instructions that could replace the original code sequence.
-  void genAlternativeCodeSequence(
-          MachineInstr &Root, MachineCombinerPattern::MC_PATTERN P,
-          SmallVectorImpl<MachineInstr *> &InsInstrs,
-          SmallVectorImpl<MachineInstr *> &DelInstrs,
-          DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const override;
+  /// Return true when Inst is both associative and commutative
+  bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
+
+  /// Return true when Inst has reassociable operands in the same MBB
+  bool hasReassociableOperands(const MachineInstr &Inst,
+                               const MachineBasicBlock *MBB) const override;
+  void reassociateOps(
+      MachineInstr &Root, MachineInstr &Prev,
+      MachineCombinerPattern::MC_PATTERN Pattern,
 
   /// analyzeCompare - For a comparison instruction, return the source registers
   /// in SrcReg and SrcReg2 if having two register operands, and the value it
   /// compares against in CmpValue. Return true if the comparison instruction
   /// can be analyzed.
   bool analyzeCompare(const MachineInstr *MI, unsigned &SrcReg,
                       unsigned &SrcReg2, int &CmpMask,
                       int &CmpValue) const override;

lib/Target/X86/X86InstrInfo.cpp

 bool X86InstrInfo::
 hasHighOperandLatency(const TargetSchedModel &SchedModel,
                       const MachineRegisterInfo *MRI,
                       const MachineInstr *DefMI, unsigned DefIdx,
                       const MachineInstr *UseMI, unsigned UseIdx) const {
   return isHighLatencyDef(DefMI->getOpcode());
 }
 
-static bool hasReassociableOperands(const MachineInstr &Inst,
-                                    const MachineBasicBlock *MBB) {
+bool X86InstrInfo::hasReassociableOperands(const MachineInstr &Inst,
+                                           const MachineBasicBlock *MBB) const {
   assert((Inst.getNumOperands() == 3 || Inst.getNumOperands() == 4) &&
          "Reassociation needs binary operators");
   const MachineOperand &Op1 = Inst.getOperand(1);
   const MachineOperand &Op2 = Inst.getOperand(2);
   const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 
   // Integer binary math/logic instructions have a third source operand:
   // the EFLAGS register. That operand must be both defined here and never
   // used; ie, it must be dead. If the EFLAGS operand is live, then we can
   // not change anything because rearranging the operands could affect other
   // instructions that depend on the exact status flags (zero, sign, etc.)
   // that are set by using these particular operands with this operation.
   if (Inst.getNumOperands() == 4) {
     assert(Inst.getOperand(3).isReg() &&
            Inst.getOperand(3).getReg() == X86::EFLAGS &&
            "Unexpected operand in reassociable instruction");
     if (!Inst.getOperand(3).isDead())
       return false;
   }
-  
   // We need virtual register definitions for the operands that we will
   // reassociate.
   MachineInstr *MI1 = nullptr;
   MachineInstr *MI2 = nullptr;
   if (Op1.isReg() && TargetRegisterInfo::isVirtualRegister(Op1.getReg()))
     MI1 = MRI.getUniqueVRegDef(Op1.getReg());
   if (Op2.isReg() && TargetRegisterInfo::isVirtualRegister(Op2.getReg()))
     MI2 = MRI.getUniqueVRegDef(Op2.getReg());
 
   // And they need to be in the trace (otherwise, they won't have a depth).
   if (MI1 && MI2 && MI1->getParent() == MBB && MI2->getParent() == MBB)
     return true;
 
   return false;
 }
 
-static bool hasReassociableSibling(const MachineInstr &Inst, bool &Commuted) {
-  const MachineBasicBlock *MBB = Inst.getParent();
-  const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
-  MachineInstr *MI1 = MRI.getUniqueVRegDef(Inst.getOperand(1).getReg());
-  MachineInstr *MI2 = MRI.getUniqueVRegDef(Inst.getOperand(2).getReg());
-  unsigned AssocOpcode = Inst.getOpcode();
-
-  // If only one operand has the same opcode and it's the second source operand,
-  // the operands must be commuted.
-  Commuted = MI1->getOpcode() != AssocOpcode && MI2->getOpcode() == AssocOpcode;
-  if (Commuted)
-    std::swap(MI1, MI2);
-
-  // 1. The previous instruction must be the same type as Inst.
-  // 2. The previous instruction must have virtual register definitions for its
-  //    operands in the same basic block as Inst.
-  // 3. The previous instruction's result must only be used by Inst.
-  if (MI1->getOpcode() == AssocOpcode &&
-      hasReassociableOperands(*MI1, MBB) &&
-      MRI.hasOneNonDBGUse(MI1->getOperand(0).getReg()))
-    return true;
-
-  return false;
-}
-
 // TODO: There are many more machine instruction opcodes to match:
 //       1. Other data types (integer, vectors)
 //       2. Other math / logic operations (xor, or)
 //       3. Other forms of the same operation (intrinsics and other variants)
-static bool isAssociativeAndCommutative(const MachineInstr &Inst) {
+bool X86InstrInfo::isAssociativeAndCommutative(const MachineInstr &Inst) const {
   switch (Inst.getOpcode()) {
   case X86::AND8rr:
   case X86::AND16rr:
   case X86::AND32rr:
   case X86::AND64rr:
   case X86::OR8rr:
   case X86::OR16rr:
   case X86::OR32rr:
bool X86InstrInfo::isAssociativeAndCommutative(const MachineInstr &Inst) const {
   case X86::VMULSDrr:
   case X86::VMULSSrr:
     return Inst.getParent()->getParent()->getTarget().Options.UnsafeFPMath;
   default:
     return false;
   }
 }
 
-/// Return true if the input instruction is part of a chain of dependent ops
-/// that are suitable for reassociation, otherwise return false.
-/// If the instruction's operands must be commuted to have a previous
-/// instruction of the same type define the first source operand, Commuted will
-/// be set to true.
-static bool isReassociationCandidate(const MachineInstr &Inst, bool &Commuted) {
-  // 1. The operation must be associative and commutative.
-  // 2. The instruction must have virtual register definitions for its
-  //    operands in the same basic block.
-  // 3. The instruction must have a reassociable sibling.
-  if (isAssociativeAndCommutative(Inst) &&
-      hasReassociableOperands(Inst, Inst.getParent()) &&
-      hasReassociableSibling(Inst, Commuted))
-    return true;
-
-  return false;
-}
-
-// FIXME: This has the potential to be expensive (compile time) while not
-// improving the code at all. Some ways to limit the overhead:
-// 1. Track successful transforms; bail out if hit rate gets too low.
-// 2. Only enable at -O3 or some other non-default optimization level.
-// 3. Pre-screen pattern candidates here: if an operand of the previous
-//    instruction is known to not increase the critical path, then don't match
-//    that pattern.
-bool X86InstrInfo::getMachineCombinerPatterns(MachineInstr &Root,
-        SmallVectorImpl<MachineCombinerPattern::MC_PATTERN> &Patterns) const {
-  // TODO: There is nothing x86-specific here except the instruction type.
-  // This logic could be hoisted into the machine combiner pass itself.
-
-  // Look for this reassociation pattern:
-  //   B = A op X (Prev)
-  //   C = B op Y (Root)
-
-  bool Commute;
-  if (isReassociationCandidate(Root, Commute)) {
-    // We found a sequence of instructions that may be suitable for a
-    // reassociation of operands to increase ILP. Specify each commutation
-    // possibility for the Prev instruction in the sequence and let the
-    // machine combiner decide if changing the operands is worthwhile.
-    if (Commute) {
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_YB);
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_YB);
-    } else {
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_AX_BY);
-      Patterns.push_back(MachineCombinerPattern::MC_REASSOC_XA_BY);
-    }
-    return true;
-  }
-
-  return false;
-}
-
 /// This is an architecture-specific helper function of reassociateOps.
 /// Set special operand attributes for new instructions after reassociation.
 static void setSpecialOperandAttr(MachineInstr &OldMI1, MachineInstr &OldMI2,
                                   MachineInstr &NewMI1, MachineInstr &NewMI2) {
   // Integer instructions define an implicit EFLAGS source register operand as
   // the third source (fourth total) operand.
   if (OldMI1.getNumOperands() != 4 || OldMI2.getNumOperands() != 4)
     return;
 
   assert(NewMI1.getNumOperands() == 4 && NewMI2.getNumOperands() == 4 &&
          "Unexpected instruction type for reassociation");
-  
   MachineOperand &OldOp1 = OldMI1.getOperand(3);
   MachineOperand &OldOp2 = OldMI2.getOperand(3);
   MachineOperand &NewOp1 = NewMI1.getOperand(3);
   MachineOperand &NewOp2 = NewMI2.getOperand(3);
 
   assert(OldOp1.isReg() && OldOp1.getReg() == X86::EFLAGS && OldOp1.isDead() &&
          "Must have dead EFLAGS operand in reassociable instruction");
   assert(OldOp2.isReg() && OldOp2.getReg() == X86::EFLAGS && OldOp2.isDead() &&

 }
 
 /// Attempt the following reassociation to reduce critical path length:
 ///   B = A op X (Prev)
 ///   C = B op Y (Root)
 ///   ===>
 ///   B = X op Y
 ///   C = A op B
-static void reassociateOps(MachineInstr &Root, MachineInstr &Prev,
-                           MachineCombinerPattern::MC_PATTERN Pattern,
-                           SmallVectorImpl<MachineInstr *> &InsInstrs,
-                           SmallVectorImpl<MachineInstr *> &DelInstrs,
-                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) {
+void X86InstrInfo::reassociateOps(
+    MachineInstr &Root, MachineInstr &Prev,
+    DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
   MachineFunction *MF = Root.getParent()->getParent();
   MachineRegisterInfo &MRI = MF->getRegInfo();
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
   const TargetRegisterClass *RC = Root.getRegClassConstraint(0, TII, TRI);
 
   // This array encodes the operand index for each parameter because the
   // operands may be commuted. Each row corresponds to a pattern value,
   // and each column specifies the index of A, B, X, Y.
   unsigned OpIdx[4][4] = {
-    { 1, 1, 2, 2 },
-    { 1, 2, 2, 1 },
-    { 2, 1, 1, 2 },
-    { 2, 2, 1, 1 }
+      {1, 1, 2, 2}, 
+      {1, 2, 2, 1}, 
+      {2, 1, 1, 2}, 
+      {2, 2, 1, 1}
   };
 
   MachineOperand &OpA = Prev.getOperand(OpIdx[Pattern][0]);
   MachineOperand &OpB = Root.getOperand(OpIdx[Pattern][1]);
   MachineOperand &OpX = Prev.getOperand(OpIdx[Pattern][2]);
   MachineOperand &OpY = Root.getOperand(OpIdx[Pattern][3]);
   MachineOperand &OpC = Root.getOperand(0);
 
void X86InstrInfo::reassociateOps(
 
   unsigned Opcode = Root.getOpcode();
   bool KillA = OpA.isKill();
   bool KillX = OpX.isKill();
   bool KillY = OpY.isKill();
 
   // Create new instructions for insertion.
   MachineInstrBuilder MIB1 =
       BuildMI(*MF, Prev.getDebugLoc(), TII->get(Opcode), NewVR)
           .addReg(RegX, getKillRegState(KillX))
           .addReg(RegY, getKillRegState(KillY));
   MachineInstrBuilder MIB2 =
       BuildMI(*MF, Root.getDebugLoc(), TII->get(Opcode), RegC)
           .addReg(RegA, getKillRegState(KillA))
           .addReg(NewVR, getKillRegState(true));
 
   setSpecialOperandAttr(Root, Prev, *MIB1, *MIB2);
 
   // Record new instructions for insertion and old instructions for deletion.
   InsInstrs.push_back(MIB1);
   InsInstrs.push_back(MIB2);
   DelInstrs.push_back(&Prev);
   DelInstrs.push_back(&Root);
 }
 
-void X86InstrInfo::genAlternativeCodeSequence(
-    MachineInstr &Root,
-    MachineCombinerPattern::MC_PATTERN Pattern,
-    SmallVectorImpl<MachineInstr *> &InsInstrs,
-    SmallVectorImpl<MachineInstr *> &DelInstrs,
-    DenseMap<unsigned, unsigned> &InstIdxForVirtReg) const {
-  MachineRegisterInfo &MRI = Root.getParent()->getParent()->getRegInfo();
-
-  // Select the previous instruction in the sequence based on the input pattern.
-  MachineInstr *Prev = nullptr;
-  switch (Pattern) {
-    case MachineCombinerPattern::MC_REASSOC_AX_BY:
-    case MachineCombinerPattern::MC_REASSOC_XA_BY:
-      Prev = MRI.getUniqueVRegDef(Root.getOperand(1).getReg());
-      break;
-    case MachineCombinerPattern::MC_REASSOC_AX_YB:
-    case MachineCombinerPattern::MC_REASSOC_XA_YB:
-      Prev = MRI.getUniqueVRegDef(Root.getOperand(2).getReg());
-  }
-  assert(Prev && "Unknown pattern for machine combiner");
-
-  reassociateOps(Root, *Prev, Pattern, InsInstrs, DelInstrs, InstIdxForVirtReg);
-  return;
-}
-
 std::pair<unsigned, unsigned>
 X86InstrInfo::decomposeMachineOperandsTargetFlags(unsigned TF) const {
   return std::make_pair(TF, 0u);
 }
 
 ArrayRef<std::pair<unsigned, const char *>>
 X86InstrInfo::getSerializableDirectMachineOperandTargetFlags() const {
   using namespace X86II;