[GISel]: Implement GlobalISel combiner API.

https://reviews.llvm.org/D41373

The various components are

GICombinerHelper contains transformations that are common to all
targets. Targets can pick and choose which transformations (at
function/opcode granularity) each pass uses via configuring a
GICombinerInfo.

GICombiner contains some common code and it does the traversal,
driving of combines, worklist management and iterating until
convergence.

GICombinerInfo is an interface with a virtual method called combine.
The combiner info will allow targets to pick and choose (or
implement their own specific combines). CombineInfos can make
use of available combines in GICombineHelper to configure the
transformations for a particular pass. Currently this approach allows
cherry picking transformations from helpers (at function/opcode
granularity) and also allows early returning on specific
transformations. Targets also get to prioritize whether target specific
combines run before/after the opt-in generic combines. Ideally we would
like this part to be configured by both C++ and Tablegen. The
CombinerInfo also has a field which indicates how to deal with
IllegalOps (ie - should we allow to create them/or legalize them?).

A CombinerPass would configure a CombinerInfo, create the GICombiner
with the Info, and call
GICombiner::combineMachineInstrs(MachineFunction&).
This organization is very similar to the GISelLegalizer.

llvm-svn: 323392

3 files changed, 124 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
index 2db90f8888c..e68ed179558 100644
--- a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -1,6 +1,8 @@
 add_llvm_library(LLVMGlobalISel
         CallLowering.cpp
         GlobalISel.cpp
+        Combiner.cpp
+        CombinerHelper.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
diff --git a/llvm/lib/CodeGen/GlobalISel/Combiner.cpp b/llvm/lib/CodeGen/GlobalISel/Combiner.cpp
new file mode 100644
index 00000000000..dbc9dbc53de
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/Combiner.cpp
@@ -0,0 +1,81 @@
+//===-- lib/CodeGen/GlobalISel/GICombiner.cpp -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file constains common code to combine machine functions at generic
+// level.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/Combiner.h"
+#include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "gi-combiner"
+
+using namespace llvm;
+
+Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
+    : CInfo(Info), TPC(TPC) {
+  (void)this->TPC; // FIXME: Remove when used.
+}
+
+bool Combiner::combineMachineInstrs(MachineFunction &MF) {
+  // If the ISel pipeline failed, do not bother running this pass.
+  // FIXME: Should this be here or in individual combiner passes.
+  if (MF.getProperties().hasProperty(
+          MachineFunctionProperties::Property::FailedISel))
+    return false;
+
+  MRI = &MF.getRegInfo();
+  Builder.setMF(MF);
+
+  DEBUG(dbgs() << "Generic MI Combiner for: " << MF.getName() << '\n');
+
+  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
+
+  bool MFChanged = false;
+  bool Changed;
+
+  do {
+    // Collect all instructions. Do a post order traversal for basic blocks and
+    // insert with list bottom up, so while we pop_back_val, we'll traverse top
+    // down RPOT.
+    Changed = false;
+    GISelWorkList<512> WorkList;
+    for (MachineBasicBlock *MBB : post_order(&MF)) {
+      if (MBB->empty())
+        continue;
+      for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
+        MachineInstr *CurMI = &*MII;
+        ++MII;
+        // Erase dead insts before even adding to the list.
+        if (isTriviallyDead(*CurMI, *MRI)) {
+          DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
+          CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
+          continue;
+        }
+        WorkList.insert(CurMI);
+      }
+    }
+    // Main Loop. Process the instructions here.
+    while (!WorkList.empty()) {
+      MachineInstr *CurrInst = WorkList.pop_back_val();
+      DEBUG(dbgs() << "Try combining " << *CurrInst << "\n";);
+      Changed |= CInfo.combine(*CurrInst, Builder);
+    }
+    MFChanged |= Changed;
+  } while (Changed);
+
+  return MFChanged;
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp b/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
new file mode 100644
index 00000000000..44e904a6391
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
@@ -0,0 +1,41 @@
+//== ---lib/CodeGen/GlobalISel/GICombinerHelper.cpp --------------------- == //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+#define DEBUG_TYPE "gi-combine"
+
+using namespace llvm;
+
+CombinerHelper::CombinerHelper(MachineIRBuilder &B) :
+  Builder(B), MRI(Builder.getMF().getRegInfo()) {}
+
+bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
+  if (MI.getOpcode() != TargetOpcode::COPY)
+    return false;
+  unsigned DstReg = MI.getOperand(0).getReg();
+  unsigned SrcReg = MI.getOperand(1).getReg();
+  LLT DstTy = MRI.getType(DstReg);
+  LLT SrcTy = MRI.getType(SrcReg);
+  // Simple Copy Propagation.
+  // a(sx) = COPY b(sx) -> Replace all uses of a with b.
+  if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy) {
+    MI.eraseFromParent();
+    MRI.replaceRegWith(DstReg, SrcReg);
+    return true;
+  }
+  return false;
+}
+
+bool CombinerHelper::tryCombine(MachineInstr &MI) {
+  return tryCombineCopy(MI);
+}