Power9 - Add exploitation of oris/ori fusion

[nemanjai]

Summary

The patch teaches LLVM to schedule oris/ori together on Power9, because Power9 can fusing oris/ori into one instruction.

Note! Part of this patch overlaps with D22193, because D22193 provides macro fusion facilities.

[nemanjai]

lib/CodeGen/PostRASchedulerList.cpp

561

I am probably missing something, but I don't see any intervening code that might set NextClusterSucc between this assert that ensures it is not set and the code that queries it.

lib/Target/PowerPC/PPCMacroFusion.cpp

18

I may be mis-remembering what was actually done, but I thought there was some work recently to convert functions that take MachineInstr by-pointer to by-reference when they can't be null (which I think is the case here).

32

Can you add a comment about what this function does (including describing the parameters)?

65

Left over from debugging?

67

Since this switch statement will grow and I assume that we will perform the same action on all pairs, might it be a cleaner implementation to write a function to query if an opcode pair can be fused?
Something along the lines of:

bool areOpcodesFusable(unsigned Opcode1, unsigned Opcode 2) {
  static unsigned P9FusedOpcodes[] = {
    PPC::ORIS8, PPC::ORI8,
    PPC::ORIS,  PPC::ORI,
    //...
    0
  }
  for (unsigned i = 0; P9FusedOpcodes[i]; i += 2)
    if (P9FusedOpcodes[i] == Opcode1 && P9FusedOpcodes[i+1] == Opcode2)
      return true;
  return false;
}

Then in this function, we would just call:

if(areOpcodesFusable(MI->getOpcode(), SU[Idx + 1].getInstr()->getOpcode())
  // ...

Of course, you might also want to take the actual instructions as arguments to areOpcodesFusable so that you would only return true if the requisite data dependency exists. It just seems like it would be easier to maintain a mapping this way.

test/CodeGen/PowerPC/fusing-constant.ll

17

Don't we want the fused instructions to be checked with CHECK-NEXT?

[amehsan]

Again, I do not see why you are changing PostRASchedulerList.cpp. We are going to switch to new post-ra MI-scheduler. You can enforce running that code by passing -mllvm misched-postra to clang for your experiments.

[MatzeB]

Can you explain why you need a custom mutator here? At first glance it looks like overriding TargetInstrInfo::shouldScheduleAdjacent() and using the default MacroFusion mutator is enough.

[cycheng]

In D22194#480485, @MatzeB wrote:

Can you explain why you need a custom mutator here? At first glance it looks like overriding TargetInstrInfo::shouldScheduleAdjacent() and using the default MacroFusion mutator is enough.

No, because default MacroFusion can only detect one pattern:

XXXInstr (on X86: Test, Cmp, Inc; On AArch64: CMN, CMP, TST, ALU)
BranchInstr

Also I didn't see any simple way to make MacroFusion more generic, so that's why we added a customized MacroFusion.

[cycheng]

lib/CodeGen/PostRASchedulerList.cpp

561

Or should I just set it to nullptr? Because we will call schedule several times, even though I thought I've processed it properly, but I just want to make sure again.

lib/Target/PowerPC/PPCMacroFusion.cpp

18

They can't be null, I can convert to by-reference as well.

65

Oh.. I thought I've removed it .. :P

67

Thanks, this is a good idea, I am working on a new version based on your suggestion here, it is table based design and would be able to handle our current requirements.

By the way, this design should be able to handle the following pattern in a more clear way.

1-to-1 pattern:

oris Rx,RA,SIh
ori Rt,Rx,SIl

xoris Rx,RA,SIh
xori Rt,Rx,SIl 

addis Rx,RA,SIh
addi Rt,Rx,SIl

1-to-n pattern:

op1: addis Rx,RA,SIh

op2: stb RS,Rx,SIl
     sth RS,Rx,SIl
     stw RS,Rx,SIl
     std RS,Rx,SIl

special requirement on op1 or op2:

op1: addi Rx,0,SI
op2: stdx RS,Rx,RB

test/CodeGen/PowerPC/fusing-constant.ll

17

Yes! I should use CHECK-NEXT, thanks a lot !!

[cycheng]

• Addressed Nemanjai's comments
• Implement a table based methodology for managing fusion instruction patterns, so we can have a cleaner way to add new patterns, query pattern, .. and so on.

[cycheng]

• Fix a bug when traversing fusion-table
• Support addi/{stdx,ldx} for Pwr9

[amehsan]

Not yet looked at everything. Will gradually add comments as I go through the code.

lib/CodeGen/PostRASchedulerList.cpp

574–589

IIUC, this implementation breaks an important invariant of the code: Anything that is in pending queue, and its operands are ready should be moved to the available queue. You should still let everything that is avaialble to go to available queue and then find a way to prioritize the one that you want there.

[amehsan]

In D22194#480257, @amehsan wrote:

Again, I do not see why you are changing PostRASchedulerList.cpp. We are going to switch to new post-ra MI-scheduler. You can enforce running that code by passing -mllvm misched-postra to clang for your experiments.

After conversation with Kit, it seems that our plans are somewhat different from what I thought. So no objection here.

[amehsan]

lib/CodeGen/PostRASchedulerList.cpp

606–612

Somewhere in this loop, you have to find a way to prioritize the cluster node. One potential way to do it (and there might be better ways) is to check if the last scheduled node has a cluster outgoing edge. If yes, continue your search in the queue until you reach that node.

[amehsan]

lib/Target/PowerPC/PPCISelLowering.cpp

1674–1681

Two comments here:

1- This should be separated to a different patch. This patch is focused on scheduling the code, such that fusion opportunities are caught. This piece of code, is about generating code that has more fusion opportunities. These are separate issues that has to be addressed separately.

2- Are you saying that we should always prefer (addi + stdx) to (addi + std) because the former pair can be fused? If yes, that is incorrect. This can significantly increase register pressure and costs us way more than what we gain from fusing two insns.

[cycheng]

Hi Ehsan,

Thanks for your review, and sorry for late response, I am reading your comments, but I might not be able to give responses and updated patch in the short period.

CY

[nemanjai]

Taking this over to abandon the revision as there are currently no plans to implement instruction fusion for Power9.

include/llvm/CodeGen/TargetPassConfig.h

 #include "llvm/Pass.h"
 #include "llvm/Support/CodeGen.h"
 #include <string>
 
 namespace llvm {
 
 class PassConfigImpl;
 class ScheduleDAGInstrs;
+class ScheduleDAGMutation;
 class TargetMachine;
 struct MachineSchedContext;
 
 // The old pass manager infrastructure is hidden in a legacy namespace now.
 namespace legacy {
 class PassManagerBase;
 }
 using legacy::PassManagerBase;
public:
 
   /// Similar to createMachineScheduler but used when postRA machine scheduling
   /// is enabled.
   virtual ScheduleDAGInstrs *
   createPostMachineScheduler(MachineSchedContext *C) const {
     return nullptr;
   }
 
+  /// When EnableMacroFusion is true, create target defined MacroFusion
+  /// instance to be run within default pre-scheduler.
+  ///
+  /// Return NULL to select the default MacroFusion.
+  virtual ScheduleDAGMutation *
+  createMacroFusion(ScheduleDAGInstrs *DAG) const {
+    return nullptr;
+  }
+
   /// printAndVerify - Add a pass to dump then verify the machine function, if
   /// those steps are enabled.
   ///
   void printAndVerify(const std::string &Banner);
 
   /// Add a pass to print the machine function if printing is enabled.
   void addPrintPass(const std::string &Banner);
 

lib/CodeGen/MachineScheduler.cpp

static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C) {
   // the interesting nodes in one pass.
   DAG->addMutation(make_unique<CopyConstrain>(DAG->TII, DAG->TRI));
   if (EnableMemOpCluster) {
     if (DAG->TII->enableClusterLoads())
       DAG->addMutation(make_unique<LoadClusterMutation>(DAG->TII, DAG->TRI));
     if (DAG->TII->enableClusterStores())
       DAG->addMutation(make_unique<StoreClusterMutation>(DAG->TII, DAG->TRI));
   }
-  if (EnableMacroFusion)
+  if (EnableMacroFusion) {
+    if (ScheduleDAGMutation *Fusion = C->PassConfig->createMacroFusion(DAG))
+      DAG->addMutation(std::unique_ptr<ScheduleDAGMutation>(Fusion));
+    else
       DAG->addMutation(make_unique<MacroFusion>(*DAG->TII, *DAG->TRI));
+  }
   return DAG;
 }
 
 static MachineSchedRegistry
 GenericSchedRegistry("converge", "Standard converging scheduler.",
                      createGenericSchedLive);
 
 //===----------------------------------------------------------------------===//

lib/CodeGen/PostRASchedulerList.cpp

class SchedulePostRATDList : public ScheduleDAGInstrs {
     LatencyPriorityQueue AvailableQueue;
 
     /// PendingQueue - This contains all of the instructions whose operands have
     /// been issued, but their results are not ready yet (due to the latency of
     /// the operation).  Once the operands becomes available, the instruction is
     /// added to the AvailableQueue.
     std::vector<SUnit*> PendingQueue;
 
+    /// Record the next node in a scheduled cluster.
+    SUnit *NextClusterSucc;
+
     /// HazardRec - The hazard recognizer to use.
     ScheduleHazardRecognizer *HazardRec;
 
     /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
     AntiDepBreaker *AntiDepBreak;
 
     /// AA - AliasAnalysis for making memory reference queries.
     AliasAnalysis *AA;

 INITIALIZE_PASS(PostRAScheduler, "post-RA-sched",
                 "Post RA top-down list latency scheduler", false, false)
 
 SchedulePostRATDList::SchedulePostRATDList(
     MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
     const RegisterClassInfo &RCI,
     TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
     SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
-    : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
-
+    : ScheduleDAGInstrs(MF, &MLI), NextClusterSucc(nullptr), AA(AA), EndIndex(0)
+{
   const InstrItineraryData *InstrItins =
       MF.getSubtarget().getInstrItineraryData();
   HazardRec =
       MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
           InstrItins, this);
   MF.getSubtarget().getPostRAMutations(Mutations);
 
   assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||

 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the PendingQueue if the count reaches zero.
 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
   SUnit *SuccSU = SuccEdge->getSUnit();
 
   if (SuccEdge->isWeak()) {
     --SuccSU->WeakPredsLeft;
+    // Cluster instructions get higher scheduling priority.
+    // If SuccSU is not blocked by any other predecessors, let scheduler pick
+    // SuccSU as next scheduling instruction.
+    if (SuccEdge->isCluster() && SuccSU->NumPredsLeft == 0)
+      NextClusterSucc = SuccSU;
     return;
   }
 #ifndef NDEBUG
   if (SuccSU->NumPredsLeft == 0) {
     dbgs() << "*** Scheduling failed! ***\n";
     SuccSU->dump(this);
     dbgs() << " has been released too many times!\n";
     llvm_unreachable(nullptr);
if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
       SUnits[i].isAvailable = true;
     }
   }
 
   // In any cycle where we can't schedule any instructions, we must
   // stall or emit a noop, depending on the target.
   bool CycleHasInsts = false;
 
+  assert(!NextClusterSucc && "Incorrect scheduling state.");
+
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
   std::vector<SUnit*> NotReady;
   Sequence.reserve(SUnits.size());
   while (!AvailableQueue.empty() || !PendingQueue.empty()) {
+    SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
+    bool HasNoopHazards = false;
+
+    // Clustered instructions get higher scheduling priority, because processor
+    // can work efficiently if these instructions can be scheduled nearby, so
+    // if we have clustered instructions, scheduling them first.
+    if (NextClusterSucc) {
+      // Wait until we have correct cycle count and no more hazard.
+      if (NextClusterSucc->getDepth() <= CurCycle &&
+          HazardRec->getHazardType(NextClusterSucc, 0/*no stalls*/) ==
+          ScheduleHazardRecognizer::NoHazard) {
+        for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i)
+          if (PendingQueue[i] == NextClusterSucc) {
+            PendingQueue.erase(PendingQueue.begin() + i);
+            break;
+          }
+
+        FoundSUnit = NextClusterSucc;
+        NextClusterSucc->isAvailable = true;
+        NextClusterSucc = nullptr;
+      }
+    } else {
       // Check to see if any of the pending instructions are ready to issue.  If
       // so, add them to the available queue.
       unsigned MinDepth = ~0u;
       for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
         if (PendingQueue[i]->getDepth() <= CurCycle) {
           AvailableQueue.push(PendingQueue[i]);
           PendingQueue[i]->isAvailable = true;
           PendingQueue[i] = PendingQueue.back();
           PendingQueue.pop_back();
           --i; --e;
         } else if (PendingQueue[i]->getDepth() < MinDepth)
           MinDepth = PendingQueue[i]->getDepth();
       }
 
       DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
 
-    SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
-    bool HasNoopHazards = false;
       while (!AvailableQueue.empty()) {
         SUnit *CurSUnit = AvailableQueue.pop();
 
         ScheduleHazardRecognizer::HazardType HT =
           HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
         if (HT == ScheduleHazardRecognizer::NoHazard) {
           if (HazardRec->ShouldPreferAnother(CurSUnit)) {
             if (!NotPreferredSUnit) {
               // If this is the first non-preferred node for this cycle, then
               // record it and continue searching for a preferred node. If this
               // is not the first non-preferred node, then treat it as though
               // there had been a hazard.
               NotPreferredSUnit = CurSUnit;
               continue;
             }
           } else {
             FoundSUnit = CurSUnit;
             break;
           }
         }
 
         // Remember if this is a noop hazard.
         HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
 
         NotReady.push_back(CurSUnit);
       }
+    }
 
     // If we have a non-preferred node, push it back onto the available list.
     // If we did not find a preferred node, then schedule this first
     // non-preferred node.
     if (NotPreferredSUnit) {
       if (!FoundSUnit) {
         DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
         FoundSUnit = NotPreferredSUnit;

lib/Target/PowerPC/CMakeLists.txt

add_llvm_target(PowerPCCodeGen
   PPCISelDAGToDAG.cpp
   PPCISelLowering.cpp
   PPCEarlyReturn.cpp
   PPCFastISel.cpp
   PPCFrameLowering.cpp
   PPCLoopPreIncPrep.cpp
   PPCMCInstLower.cpp
   PPCMachineFunctionInfo.cpp
+  PPCMacroFusion.cpp
   PPCMIPeephole.cpp
   PPCRegisterInfo.cpp
   PPCQPXLoadSplat.cpp
   PPCSubtarget.cpp
   PPCTargetMachine.cpp
   PPCTargetObjectFile.cpp
   PPCTargetTransformInfo.cpp
   PPCTOCRegDeps.cpp

lib/Target/PowerPC/PPC.td

list<SubtargetFeature> Power7FeatureList =
        FeatureMFTB, DeprecatedDST];
   list<SubtargetFeature> Power8SpecificFeatures =
       [DirectivePwr8, FeatureP8Altivec, FeatureP8Vector, FeatureP8Crypto,
        FeatureHTM, FeatureDirectMove, FeatureICBT, FeaturePartwordAtomic,
        FeatureFusion];
   list<SubtargetFeature> Power8FeatureList =
       !listconcat(Power7FeatureList, Power8SpecificFeatures);
   list<SubtargetFeature> Power9SpecificFeatures =
-      [FeatureP9Altivec, FeatureP9Vector, FeatureISA3_0];
+      [DirectivePwr9, FeatureP9Altivec, FeatureP9Vector, FeatureISA3_0];
   list<SubtargetFeature> Power9FeatureList =
       !listconcat(Power8FeatureList, Power9SpecificFeatures);
 }
 
 // Note: Future features to add when support is extended to more
 // recent ISA levels:
 //
 // DFP          p6, p6x, p7        decimal floating-point instructions

lib/Target/PowerPC/PPCISelLowering.cpp

 /// SelectAddressRegReg - Given the specified addressed, check to see if it
 /// can be represented as an indexed [r+r] operation.  Returns false if it
 /// can be more efficiently represented with [r+imm].
 bool PPCTargetLowering::SelectAddressRegReg(SDValue N, SDValue &Base,
                                             SDValue &Index,
                                             SelectionDAG &DAG) const {
   short imm = 0;
   if (N.getOpcode() == ISD::ADD) {
+    // Power9 can fuse [addi, stdx], so even N can be represented as [r+i], we
+    // still force it to use [r+r]
+    if (Subtarget.getDarwinDirective() == PPC::DIR_PWR9 &&
+        N->getValueType(0) == MVT::i64) {
+      Index = N.getOperand(0);
+      Base = N.getOperand(1);
+      return true;
+    }
     if (isIntS16Immediate(N.getOperand(1), imm))
       return false;    // r+i
     if (N.getOperand(1).getOpcode() == PPCISD::Lo)
       return false;    // r+i
 
     Base = N.getOperand(0);
     Index = N.getOperand(1);
     return true;

lib/Target/PowerPC/PPCMacroFusion.h

+//===-- PPCMacroFusion.h - PPC Instruction Fusion Logic --------*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_POWERPC_PPCMACROFUSION_H
+#define LLVM_LIB_TARGET_POWERPC_PPCMACROFUSION_H
+
+#include "llvm/CodeGen/ScheduleDAGMutation.h"
+
+namespace llvm {
+class TargetInstrInfo;
+class TargetRegisterInfo;
+
+// PPCMacroFusion - PPC specific macro-fusion implementation.
+class PPCMacroFusion : public ScheduleDAGMutation {
+  const TargetInstrInfo &TII;
+  const TargetRegisterInfo &TRI;
+public:
+  PPCMacroFusion(const TargetInstrInfo &TII, const TargetRegisterInfo &TRI)
+    : TII(TII), TRI(TRI) {}
+
+  void apply(ScheduleDAGInstrs *DAGInstrs) override;
+};
+}
+
+#endif

lib/Target/PowerPC/PPCMacroFusion.cpp

+//===-- PPCMacroFusion.cpp - PPC Instruction Fusion Logic -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// How to add a new fusion pairs to existing table?
+// 1. Insert a new pair to P*FusedInstrsTable, please put same Op1 pair together
+// 2. If matched pair require special check, we can add a callback to table for
+//    that pair
+//
+// How to add a new table?
+// 1. Define a new P*FusedInstrsTable
+// 2. Instantiating a PPCFusionTable by feeding newly defined table
+//
+//===----------------------------------------------------------------------===//
+
+#include "PPCMacroFusion.h"
+#include "PPCRegisterInfo.h"
+#include "PPCSubtarget.h"
+#include "llvm/CodeGen/MachineScheduler.h"
+using namespace llvm;
+
+// CheckCallback - Some fused-pairs require more specific checking, we can
+// implement and add new Callback in FusedInstrsTable for these fused-pairs.
+typedef bool (*CheckCallback)(const MachineInstr &First,
+                              const MachineInstr &Second);
+
+// FusionInfo - Describe each fused-pair: Opcode1, opcode2, should they have
+// data dependency, need further checking?
+struct FusionInfo {
+  unsigned Op1;
+  unsigned Op2;
+  bool NeedCheckDataDep;
+  CheckCallback FurtherCheck;
+};
+
+// Power9's Fused Instruction Table:
+const static FusionInfo P9FusedInstrsTable[] = {
+  {PPC::ORIS8,      PPC::ORI8,      true, nullptr},
+  {PPC::ORIS,       PPC::ORI,       true, nullptr},
+  {PPC::LI8,        PPC::LDX,       true, nullptr},
+  {PPC::LI8,        PPC::STDX,      true, nullptr}
+};
+
+// Returns true if Second instr reads a register written by First instr.
+static bool hasDataDep(const TargetRegisterInfo &TRI,
+                       const MachineInstr &First, const MachineInstr &Second) {
+  for (const MachineOperand &MO : Second.uses()) {
+    if (!MO.isReg() || !MO.readsReg())
+      continue;
+
+    unsigned Reg = MO.getReg();
+    if (First.modifiesRegister(Reg, &TRI))
+      return true;
+  }
+  return false;
+}
+
+// Add a weak cluster edge First->Second, so MI scheduler can schedule
+// First and Second adjacently.
+static void addClusterEdge(SUnit &First, SUnit &Second) {
+  // If there has been a First->Second edge, then set the edge's latency to
+  // zero, so (pre) scheduler is able to pick the Second instruction in the
+  // same cycle.
+  for (SDep &I: Second.Preds)
+    if (I.getSUnit() == &First) {
+      I.setLatency(0);
+      break;
+    }
+
+  for (SDep &I: First.Succs)
+    if (I.getSUnit() == &Second) {
+      I.setLatency(0);
+      break;
+    }
+
+  // FIXME: When adding new edge, should we check whether this new edge create
+  //        a cycle?
+  const SDep PredDep(&First, SDep::Cluster);
+  Second.addPred(PredDep, /*Required=*/!PredDep.isArtificial());
+}
+
+// PPCFusionTable - Manage FusedInstrsTable, and is responsible for judging
+// if an instruction pair is fusable.
+class PPCFusionTable {
+public:
+  // TableIndex - Index into FusedInstrsTable. See TableIndexMap comment.
+  struct TableIndex {
+    unsigned short StartRow;
+    unsigned short Size;
+
+    TableIndex(): StartRow(0), Size(0) {}
+    TableIndex(unsigned short StartRow, unsigned short Size)
+      : StartRow(StartRow), Size(Size) {}
+  };
+
+  PPCFusionTable(const FusionInfo *FIArray, unsigned TableSize)
+    : FusedInstrsTable(FIArray), TableSize(TableSize) {
+    initTableIndex(FIArray, TableSize);
+  }
+
+  void initTableIndex(const FusionInfo *FIArray, unsigned TableSize);
+
+  // areInstrsFusable - Test if First and Second is a legal fused pattern
+  bool areInstrsFusable(const TargetRegisterInfo &TRI,
+                        const MachineInstr &First,
+                        const MachineInstr &Second) const;
+private:
+  // TableIndexMap - Map Op1 to its TableIndex, then we can use TableIndex to
+  // find out all of Op1's pairs in the FusedInstrsTable.
+  SmallDenseMap<unsigned, TableIndex, 8> TableIndexMap;
+
+  // External defined fused instruction pairs.
+  const FusionInfo *FusedInstrsTable;
+  const unsigned TableSize;
+};
+
+void PPCFusionTable::initTableIndex(const FusionInfo *FIArray,
+                                    unsigned TableSize) {
+  TableIndex Index(0, 1 /* Size */);
+  unsigned CurOp1 = FIArray[0].Op1;
+
+  for (unsigned i = 1; i < TableSize; ++i) {
+    if (CurOp1 == FIArray[i].Op1)
+      ++Index.Size;
+    else {
+      assert(TableIndexMap.find(CurOp1) == TableIndexMap.end() &&
+             "The opcode has been added, opcode order in the table is wrong.");
+
+      TableIndexMap[CurOp1] = Index;
+
+      Index.StartRow += Index.Size;
+      Index.Size = 1;
+      CurOp1 = FIArray[i].Op1;
+    }
+  }
+
+  // Add the last record.
+  assert(TableIndexMap.find(CurOp1) == TableIndexMap.end() &&
+         "The opcode has been added, opcode order in the table is wrong.");
+  TableIndexMap[CurOp1] = Index;
+}
+
+bool PPCFusionTable::areInstrsFusable(const TargetRegisterInfo &TRI,
+                                      const MachineInstr &First,
+                                      const MachineInstr &Second) const {
+  auto Iter = TableIndexMap.find(First.getOpcode());
+  if (Iter == TableIndexMap.end())
+    return false;
+
+  const TableIndex &Idx = Iter->second;
+  for (unsigned i = Idx.StartRow; i < Idx.StartRow + Idx.Size; ++i)
+    if (FusedInstrsTable[i].Op2 == Second.getOpcode()) {
+      if (FusedInstrsTable[i].NeedCheckDataDep &&
+          !hasDataDep(TRI, First, Second))
+        return false;
+
+      if (FusedInstrsTable[i].FurtherCheck &&
+          !FusedInstrsTable[i].FurtherCheck(First, Second))
+        return false;
+
+      return true;
+    }
+
+  return false;
+}
+
+void PPCMacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
+  std::vector<SUnit> &SU = DAGInstrs->SUnits;
+  if (SU.size() < 2)
+    return;
+
+  const PPCSubtarget &Subtarget = DAGInstrs->MF.getSubtarget<PPCSubtarget>();
+  const PPCFusionTable *FT = nullptr;
+
+  switch (Subtarget.getDarwinDirective()) {
+    default: return;
+
+    case PPC::DIR_PWR9: {
+      const static PPCFusionTable
+        P9FusionTable(P9FusedInstrsTable, array_lengthof(P9FusedInstrsTable));
+
+      FT = &P9FusionTable;
+      break;
+    }
+  }
+
+  // Iterate over current scheduling region sequentially.
+  unsigned Idx = 0, LastIdx = SU.size() - 1;
+
+  while (Idx < LastIdx) {
+    // FIXME: Do we have any pattern that need to scan more SUs
+    //        (From Idx+1 to LastIdx)?
+    if (FT->areInstrsFusable(TRI,
+                             *SU[Idx].getInstr(), *SU[Idx + 1].getInstr())) {
+      addClusterEdge(SU[Idx], SU[Idx + 1]);
+      ++Idx;
+    }
+    ++Idx;
+  }
+}

lib/Target/PowerPC/PPCSubtarget.h

public:
   const SelectionDAGTargetInfo *getSelectionDAGInfo() const override {
     return &TSInfo;
   }
   const PPCRegisterInfo *getRegisterInfo() const override {
     return &getInstrInfo()->getRegisterInfo();
   }
   const PPCTargetMachine &getTargetMachine() const { return TM; }
 
+  void getPostRAMutations(std::vector<std::unique_ptr<ScheduleDAGMutation>>
+                          &Mutations) const override;
+
   /// initializeSubtargetDependencies - Initializes using a CPU and feature string
   /// so that we can use initializer lists for subtarget initialization.
   PPCSubtarget &initializeSubtargetDependencies(StringRef CPU, StringRef FS);
 
 private:
   void initializeEnvironment();
   void initSubtargetFeatures(StringRef CPU, StringRef FS);
 

lib/Target/PowerPC/PPCSubtarget.cpp

 //===-- PowerPCSubtarget.cpp - PPC Subtarget Information ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the PPC specific subclass of TargetSubtargetInfo.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PPCSubtarget.h"
 #include "PPC.h"
+#include "PPCMacroFusion.h"
 #include "PPCRegisterInfo.h"
 #include "PPCTargetMachine.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/Support/CommandLine.h"
if (TM.getRelocationModel() == Reloc::PIC_) {
     return flags;
   }
 
   if (GV->isStrongDefinitionForLinker())
     return flags;
   return flags | PPCII::MO_NLP_FLAG;
 }
 
+void PPCSubtarget::getPostRAMutations(
+    std::vector<std::unique_ptr<ScheduleDAGMutation>> &Mutations) const
+{
+  Mutations.push_back(make_unique<PPCMacroFusion>(*getInstrInfo(),
+                                                  *getRegisterInfo()));
+}
+
 bool PPCSubtarget::isELFv2ABI() const { return TM.isELFv2ABI(); }
 bool PPCSubtarget::isPPC64() const { return TM.isPPC64(); }

lib/Target/PowerPC/PPCTargetMachine.cpp

 //===-- PPCTargetMachine.cpp - Define TargetMachine for PowerPC -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Top-level implementation for the PowerPC target.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PPCTargetMachine.h"
 #include "PPC.h"
+#include "PPCMacroFusion.h"
 #include "PPCTargetObjectFile.h"
 #include "PPCTargetTransformInfo.h"
 #include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/TargetRegistry.h"
public:
   void addIRPasses() override;
   bool addPreISel() override;
   bool addILPOpts() override;
   bool addInstSelector() override;
   void addMachineSSAOptimization() override;
   void addPreRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
+  ScheduleDAGMutation *createMacroFusion(ScheduleDAGInstrs *DAG) const override;
 };
+
 } // namespace
 
 TargetPassConfig *PPCTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new PPCPassConfig(this, PM);
 }
 
 void PPCPassConfig::addIRPasses() {
   if (TM->getOptLevel() != CodeGenOpt::None)

 
 void PPCPassConfig::addPreEmitPass() {
   if (getOptLevel() != CodeGenOpt::None)
     addPass(createPPCEarlyReturnPass(), false);
   // Must run branch selection immediately preceding the asm printer.
   addPass(createPPCBranchSelectionPass(), false);
 }
 
+ScheduleDAGMutation *
+PPCPassConfig::createMacroFusion(ScheduleDAGInstrs *DAG) const {
+  return new PPCMacroFusion(*DAG->TII, *DAG->TRI);
+}
+
 TargetIRAnalysis PPCTargetMachine::getTargetIRAnalysis() {
   return TargetIRAnalysis([this](const Function &F) {
     return TargetTransformInfo(PPCTTIImpl(this, F));
   });
 }

test/CodeGen/PowerPC/fusing-addi-ldst.ll

+; RUN: llc < %s -march=ppc64 -mcpu=pwr9 -verify-machineinstrs | \
+; RUN:   FileCheck %s -check-prefix=CHECK-P9
+; RUN: llc < %s -march=ppc64 -mcpu=pwr8 -verify-machineinstrs | \
+; RUN:   FileCheck %s -check-prefix=CHECK-P8
+
+define void @fusingAddiStdx(i8* noalias nocapture readonly %src, 
+                            i8* noalias nocapture %dst) local_unnamed_addr {
+entry:
+  %add.ptr = getelementptr inbounds i8, i8* %src, i64 3
+  %0 = bitcast i8* %add.ptr to i64*
+  %1 = load i64, i64* %0, align 8
+  %add.ptr1 = getelementptr inbounds i8, i8* %dst, i64 2
+  %2 = bitcast i8* %add.ptr1 to i64*
+  store i64 %1, i64* %2, align 8
+  %add.ptr2 = getelementptr inbounds i8, i8* %src, i64 7
+  %3 = bitcast i8* %add.ptr2 to i64*
+  %4 = load i64, i64* %3, align 8
+  %add.ptr3 = getelementptr inbounds i8, i8* %dst, i64 6
+  %5 = bitcast i8* %add.ptr3 to i64*
+  store i64 %4, i64* %5, align 8
+  %add.ptr4 = getelementptr inbounds i8, i8* %src, i64 9
+  %6 = bitcast i8* %add.ptr4 to i64*
+  %7 = load i64, i64* %6, align 8
+  %add.ptr5 = getelementptr inbounds i8, i8* %dst, i64 8
+  %8 = bitcast i8* %add.ptr5 to i64*
+  store i64 %7, i64* %8, align 8
+  ret void
+
+; CHECK-P9-LABEL: @fusingAddiStdx
+; CHECK-P9: li [[REG0:[0-9]+]]
+; CHECK-NEXT-P9: ldx {{[0-9]+}}, [[REG0]]
+; CHECK-P9: li [[REG1:[0-9]+]]
+; CHECK-NEXT-P9: ldx {{[0-9]+}}, [[REG1]]
+; CHECK-P9: li [[REG2:[0-9]+]]
+; CHECK-NEXT-P9: ldx {{[0-9]+}}, [[REG2]]
+
+; CHECK-P9: li [[REG3:[0-9]+]]
+; CHECK-NEXT-P9: stdx {{[0-9]+}}, [[REG3]]
+; CHECK-P9: li [[REG4:[0-9]+]]
+; CHECK-NEXT-P9: stdx {{[0-9]+}}, [[REG4]]
+
+; CHECK-P8-LABEL: @fusingAddiStdx
+; CHECK-P8: ld
+; CHECK-P8: ld
+; CHECK-P8: ld
+; CHECK-P8: std
+; CHECK-P8: std
+; CHECK-P8: std
+}

test/CodeGen/PowerPC/fusing-constant.ll

+; RUN: llc < %s -march=ppc64 -mcpu=pwr9 -verify-machineinstrs | \
+; RUN:   FileCheck %s -check-prefix=CHECK-P9
+; RUN: llc < %s -march=ppc64 -mcpu=pwr8 -verify-machineinstrs | \
+; RUN:   FileCheck %s -check-prefix=CHECK-P8
+define i64 @fusingOrisOri(i64 %x, i64 %y, i64 %z) {
+entry:
+  %add = add nsw i64 %x, 4295163905
+  %add1 = add nsw i64 %y, 8590196738
+  %add2 = add nsw i64 %z, 12885229571
+  %and = and i64 %add1, %add
+  %and3 = and i64 %and, %add2
+  ret i64 %and3
+
+; CHECK-P9-LABEL: @fusingOrisOri
+; CHECK-P9: oris
+; CHECK-NEXT-P9: ori
+; CHECK-P9: oris
+; CHECK-NEXT-P9: ori
+; CHECK-P9: oris
+; CHECK-NEXT-P9: ori
+
+; CHECK-P8-LABEL: @fusingOrisOri
+; CHECK-P8: oris
+; CHECK-P8: oris
+; CHECK-P8: oris
+; CHECK-P8: ori
+; CHECK-P8: ori
+; CHECK-P8: ori
+}