7 files changed, 215 insertions, 4 deletions
diff --git a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
index 960f51a842d..0d18ef63b8f 100644
--- a/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
+++ b/llvm/lib/CodeGen/GlobalISel/CMakeLists.txt
@@ -2,6 +2,8 @@
 set(GLOBAL_ISEL_FILES
       IRTranslator.cpp
       MachineIRBuilder.cpp
+      MachineLegalizeHelper.cpp
+      MachineLegalizePass.cpp
       MachineLegalizer.cpp
       RegBankSelect.cpp
       RegisterBank.cpp
diff --git a/llvm/lib/CodeGen/GlobalISel/GlobalISel.cpp b/llvm/lib/CodeGen/GlobalISel/GlobalISel.cpp
index 231e5ac82be..c0ea873bcfe 100644
--- a/llvm/lib/CodeGen/GlobalISel/GlobalISel.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/GlobalISel.cpp
@@ -25,6 +25,7 @@ void llvm::initializeGlobalISel(PassRegistry &Registry) {
 
 void llvm::initializeGlobalISel(PassRegistry &Registry) {
   initializeIRTranslatorPass(Registry);
+  initializeMachineLegalizePassPass(Registry);
   initializeRegBankSelectPass(Registry);
 }
 #endif // LLVM_BUILD_GLOBAL_ISEL
diff --git a/llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp b/llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp
index 220965ce660..2b91584c75d 100644
--- a/llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp
@@ -110,3 +110,35 @@ MachineInstr *MachineIRBuilder::buildFrameIndex(LLT Ty, unsigned Res, int Idx) {
   MIB.addImm(Idx);
   return NewMI;
 }
+
+MachineInstr *MachineIRBuilder::buildAdd(LLT Ty, unsigned Res, unsigned Op0,
+                                         unsigned Op1) {
+  return buildInstr(TargetOpcode::G_ADD, Ty, Res, Op0, Op1);
+}
+
+MachineInstr *MachineIRBuilder::buildExtract(LLT Ty, ArrayRef<unsigned> Results,
+                                             unsigned Src,
+                                             ArrayRef<unsigned> Indexes) {
+  assert(Results.size() == Indexes.size() && "inconsistent number of regs");
+
+  MachineInstr *NewMI = buildInstr(TargetOpcode::G_EXTRACT, Ty);
+  auto MIB = MachineInstrBuilder(getMF(), NewMI);
+  for (auto Res : Results)
+    MIB.addReg(Res, RegState::Define);
+
+  MIB.addReg(Src);
+
+  for (auto Idx : Indexes)
+    MIB.addImm(Idx);
+  return NewMI;
+}
+
+MachineInstr *MachineIRBuilder::buildSequence(LLT Ty, unsigned Res,
+                                              ArrayRef<unsigned> Ops) {
+  MachineInstr *NewMI = buildInstr(TargetOpcode::G_SEQUENCE, Ty);
+  auto MIB = MachineInstrBuilder(getMF(), NewMI);
+  MIB.addReg(Res, RegState::Define);
+  for (auto Op : Ops)
+    MIB.addReg(Op);
+  return NewMI;
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/MachineLegalizeHelper.cpp b/llvm/lib/CodeGen/GlobalISel/MachineLegalizeHelper.cpp
new file mode 100644
index 00000000000..55adbbd20ce
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/MachineLegalizeHelper.cpp
@@ -0,0 +1,98 @@
+//===-- llvm/CodeGen/GlobalISel/MachineLegalizeHelper.cpp -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file implements the MachineLegalizeHelper class to legalize
+/// individual instructions and the LegalizeMachineIR wrapper pass for the
+/// primary legalization.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h"
+#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+
+#include <sstream>
+
+#define DEBUG_TYPE "legalize-mir"
+
+using namespace llvm;
+
+MachineLegalizeHelper::MachineLegalizeHelper(MachineFunction &MF)
+  : MRI(MF.getRegInfo()) {
+  MIRBuilder.setMF(MF);
+}
+
+MachineLegalizeHelper::LegalizeResult MachineLegalizeHelper::legalizeInstr(
+    MachineInstr &MI, const MachineLegalizer &Legalizer) {
+  auto Action = Legalizer.getAction(MI);
+  switch (Action.first) {
+  case MachineLegalizer::Legal:
+    return AlreadyLegal;
+  case MachineLegalizer::NarrowScalar:
+    return narrowScalar(MI, Action.second);
+  case MachineLegalizer::WidenScalar:
+    return widenScalar(MI, Action.second);
+  case MachineLegalizer::FewerElements:
+    return fewerElementsVector(MI, Action.second);
+  default:
+    return UnableToLegalize;
+  }
+}
+
+void MachineLegalizeHelper::extractParts(unsigned Reg, LLT Ty, int NumParts,
+                                         SmallVectorImpl<unsigned> &VRegs) {
+  unsigned Size = Ty.getSizeInBits();
+  SmallVector<unsigned, 4> Indexes;
+  for (int i = 0; i < NumParts; ++i) {
+    VRegs.push_back(MRI.createGenericVirtualRegister(Size));
+    Indexes.push_back(i * Size);
+  }
+  MIRBuilder.buildExtract(Ty, VRegs, Reg, Indexes);
+}
+
+MachineLegalizeHelper::LegalizeResult
+MachineLegalizeHelper::narrowScalar(MachineInstr &MI, LLT NarrowTy) {
+  return UnableToLegalize;
+}
+
+MachineLegalizeHelper::LegalizeResult
+MachineLegalizeHelper::widenScalar(MachineInstr &MI, LLT WideTy) {
+  return UnableToLegalize;
+}
+
+MachineLegalizeHelper::LegalizeResult
+MachineLegalizeHelper::fewerElementsVector(MachineInstr &MI, LLT NarrowTy) {
+  switch (MI.getOpcode()) {
+  default:
+    return UnableToLegalize;
+  case TargetOpcode::G_ADD: {
+    unsigned NarrowSize = NarrowTy.getSizeInBits();
+    int NumParts = MI.getType().getSizeInBits() / NarrowSize;
+
+    MIRBuilder.setInstr(MI);
+
+    SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
+    extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
+    extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
+
+    for (int i = 0; i < NumParts; ++i) {
+      unsigned DstReg = MRI.createGenericVirtualRegister(NarrowSize);
+      MIRBuilder.buildAdd(NarrowTy, DstReg, Src1Regs[i], Src2Regs[i]);
+      DstRegs.push_back(DstReg);
+    }
+
+    MIRBuilder.buildSequence(MI.getType(), MI.getOperand(0).getReg(), DstRegs);
+    MI.eraseFromParent();
+    return Legalized;
+  }
+  }
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/MachineLegalizePass.cpp b/llvm/lib/CodeGen/GlobalISel/MachineLegalizePass.cpp
new file mode 100644
index 00000000000..4ddc82fc6b7
--- /dev/null
+++ b/llvm/lib/CodeGen/GlobalISel/MachineLegalizePass.cpp
@@ -0,0 +1,72 @@
+//===-- llvm/CodeGen/GlobalISel/MachineLegalizePass.cpp -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file implements the LegalizeHelper class to legalize individual
+/// instructions and the MachineLegalizePass wrapper pass for the primary
+/// legalization.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/MachineLegalizePass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h"
+#include "llvm/CodeGen/GlobalISel/MachineLegalizer.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+
+#define DEBUG_TYPE "legalize-mir"
+
+using namespace llvm;
+
+char MachineLegalizePass::ID = 0;
+INITIALIZE_PASS(MachineLegalizePass, DEBUG_TYPE,
+                "Legalize the Machine IR a function's Machine IR", false,
+                false);
+
+MachineLegalizePass::MachineLegalizePass() : MachineFunctionPass(ID) {
+  initializeMachineLegalizePassPass(*PassRegistry::getPassRegistry());
+}
+
+void MachineLegalizePass::init(MachineFunction &MF) {
+}
+
+bool MachineLegalizePass::runOnMachineFunction(MachineFunction &MF) {
+  DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
+  init(MF);
+  const MachineLegalizer &Legalizer = *MF.getSubtarget().getMachineLegalizer();
+  MachineLegalizeHelper Helper(MF);
+
+  // FIXME: an instruction may need more than one pass before it is legal. For
+  // example on most architectures <3 x i3> is doubly-illegal. It would
+  // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
+  // probably want a worklist of instructions rather than naive iterate until
+  // convergence for performance reasons.
+  bool Changed = false;
+  MachineBasicBlock::iterator NextMI;
+  for (auto &MBB : MF)
+    for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
+      // Get the next Instruction before we try to legalize, because there's a
+      // good chance MI will be deleted.
+      NextMI = std::next(MI);
+      auto Res = Helper.legalizeInstr(*MI, Legalizer);
+
+      // Error out if we couldn't legalize this instruction. We may want to fall
+      // back to DAG ISel instead in the future.
+      if (Res == MachineLegalizeHelper::UnableToLegalize) {
+        std::string Msg;
+        raw_string_ostream OS(Msg);
+        OS << "unable to legalize instruction: ";
+        MI->print(OS);
+        report_fatal_error(OS.str());
+      }
+
+      Changed |= Res == MachineLegalizeHelper::Legalized;
+    }
+  return Changed;
+}
diff --git a/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp b/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
index edd5ccfd9cd..600f7bc5973 100644
--- a/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/MachineLegalizer.cpp
@@ -28,10 +28,6 @@ MachineLegalizer::MachineLegalizer() : TablesInitialized(false) {
   DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
 }
 
-bool MachineLegalizer::legalizeInstr(MachineInstr &MI) const {
-  llvm_unreachable("Unimplemented functionality");
-}
-
 void MachineLegalizer::computeTables() {
   for (auto &Op : Actions) {
     LLT Ty = Op.first.second;
@@ -56,6 +52,11 @@ MachineLegalizer::getAction(unsigned Opcode, LLT Ty) const {
   // These *have* to be implemented for now, they're the fundamental basis of
   // how everything else is transformed.
 
+  // FIXME: the long-term plan calls for expansion in terms of load/store (if
+  // they're not legal).
+  if (Opcode == TargetOpcode::G_SEQUENCE || Opcode == TargetOpcode::G_EXTRACT)
+    return std::make_pair(Legal, Ty);
+
   auto ActionIt = Actions.find(std::make_pair(Opcode, Ty));
   if (ActionIt != Actions.end())
     return findLegalAction(Opcode, Ty, ActionIt->second);
diff --git a/llvm/lib/CodeGen/LLVMTargetMachine.cpp b/llvm/lib/CodeGen/LLVMTargetMachine.cpp
index 9eb43d2bec1..b18a186c122 100644
--- a/llvm/lib/CodeGen/LLVMTargetMachine.cpp
+++ b/llvm/lib/CodeGen/LLVMTargetMachine.cpp
@@ -165,6 +165,11 @@ addPassesToGenerateCode(LLVMTargetMachine *TM, PassManagerBase &PM,
     if (PassConfig->addIRTranslator())
       return nullptr;
 
+    PassConfig->addPreLegalizeMachineIR();
+
+    if (PassConfig->addLegalizeMachineIR())
+      return nullptr;
+
     // Before running the register bank selector, ask the target if it
     // wants to run some passes.
     PassConfig->addPreRegBankSelect();