10 files changed, 221 insertions, 12 deletions
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/GISelAccessor.h b/llvm/include/llvm/CodeGen/GlobalISel/GISelAccessor.h
index 7c5ec9f3adc..8465bce2a06 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/GISelAccessor.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/GISelAccessor.h
@@ -17,6 +17,7 @@
 
 namespace llvm {
 class CallLowering;
+class MachineLegalizer;
 class RegisterBankInfo;
 
 /// The goal of this helper class is to gather the accessor to all
@@ -27,6 +28,9 @@ class RegisterBankInfo;
 struct GISelAccessor {
   virtual ~GISelAccessor() {}
   virtual const CallLowering *getCallLowering() const { return nullptr;}
+  virtual const MachineLegalizer *getMachineLegalizer() const {
+    return nullptr;
+  }
   virtual const RegisterBankInfo *getRegBankInfo() const { return nullptr;}
 };
 } // End namespace llvm;
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
index 6728f4f3fea..55eafb372f9 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
@@ -80,7 +80,7 @@ public:
   /// Set the insertion point to before (\p Before = true) or after
   /// (\p Before = false) \p MI.
   /// \pre MI must be in getMF().
-  void setInstr(MachineInstr &MI, bool Before = false);
+  void setInstr(MachineInstr &MI, bool Before = true);
   /// @}
 
   /// Set the debug location to \p DL for all the next build instructions.
@@ -152,6 +152,37 @@ public:
   /// \return The newly created instruction.
   MachineInstr *buildFrameIndex(LLT Ty, unsigned Res, int Idx);
 
+  /// Build and insert \p Res<def> = G_ADD \p Ty \p Op0, \p Op1
+  ///
+  /// G_ADD sets \p Res to the sum of integer parameters \p Op0 and \p Op1,
+  /// truncated to their width.
+  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  ///
+  /// \return The newly created instruction.
+  MachineInstr *buildAdd(LLT Ty, unsigned Res, unsigned Op0, unsigned Op1);
+
+  /// Build and insert `Res0<def>, ... = G_EXTRACT Ty Src, Idx0, ...`.
+  ///
+  /// If \p Ty has size N bits, G_EXTRACT sets \p Res[0] to bits `[Idxs[0],
+  /// Idxs[0] + N)` of \p Src and similarly for subsequent bit-indexes.
+  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  ///
+  /// \return The newly created instruction.
+  MachineInstr *buildExtract(LLT Ty, ArrayRef<unsigned> Results, unsigned Src,
+                             ArrayRef<unsigned> Indexes);
+
+  /// Build and insert \p Res<def> = G_SEQUENCE \p Ty \p Ops[0], ...
+  ///
+  /// G_SEQUENCE concatenates each element in Ops into a single register, where
+  /// Ops[0] starts at bit 0 of \p Res.
+  ///
+  /// \pre setBasicBlock or setMI must have been called.
+  /// \pre The sum of the input sizes must equal the result's size.
+  ///
+  /// \return The newly created instruction.
+  MachineInstr *buildSequence(LLT Ty, unsigned Res, ArrayRef<unsigned> Ops);
 };
 
 } // End namespace llvm.
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h
new file mode 100644
index 00000000000..7252fedac9e
--- /dev/null
+++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h
@@ -0,0 +1,92 @@
+//== llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h ----------- -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file A pass to convert the target-illegal operations created by IR -> MIR
+/// translation into ones the target expects to be able to select. This may
+/// occur in multiple phases, for example G_ADD <2 x i8> -> G_ADD <2 x i16> ->
+/// G_ADD <4 x i16>.
+///
+/// The MachineLegalizeHelper class is where most of the work happens, and is
+/// designed to be callable from other passes that find themselves with an
+/// illegal instruction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
+#define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZEHELPER_H
+
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/LowLevelType.h"
+
+namespace llvm {
+// Forward declarations.
+class MachineLegalizeInfo;
+class MachineLegalizer;
+class MachineRegisterInfo;
+
+class MachineLegalizeHelper {
+public:
+  enum LegalizeResult {
+    /// Instruction was already legal and no change was made to the
+    /// MachineFunction.
+    AlreadyLegal,
+
+    /// Instruction has been legalized and the MachineFunction changed.
+    Legalized,
+
+    /// Some kind of error has occurred and we could not legalize this
+    /// instruction.
+    UnableToLegalize,
+  };
+
+  MachineLegalizeHelper(MachineFunction &MF);
+
+  /// Replace \p MI by a sequence of legal instructions that can implement the
+  /// same operation. Note that this means \p MI may be deleted, so any iterator
+  /// steps should be performed before calling this function. \p Helper should
+  /// be initialized to the MachineFunction containing \p MI.
+  ///
+  /// Considered as an opaque blob, the legal code will use and define the same
+  /// registers as \p MI.
+  LegalizeResult legalizeInstr(MachineInstr &MI,
+                               const MachineLegalizer &Legalizer);
+
+  /// Legalize an instruction by reducing the width of the underlying scalar
+  /// type.
+  LegalizeResult narrowScalar(MachineInstr &MI, LLT NarrowTy);
+
+  /// Legalize an instruction by performing the operation on a wider scalar type
+  /// (for example a 16-bit addition can be safely performed at 32-bits
+  /// precision, ignoring the unused bits).
+  LegalizeResult widenScalar(MachineInstr &MI, LLT WideTy);
+
+  /// Legalize a vector instruction by splitting into multiple components, each
+  /// acting on the same scalar type as the original but with fewer elements.
+  LegalizeResult fewerElementsVector(MachineInstr &MI, LLT NarrowTy);
+
+  /// Legalize a vector instruction by increasing the number of vector elements
+  /// involved and ignoring the added elements later.
+  LegalizeResult moreElementsVector(MachineInstr &MI, LLT WideTy);
+
+private:
+
+  /// Helper function to split a wide generic register into bitwise blocks with
+  /// the given Type (which implies the number of blocks needed). The generic
+  /// registers created are appended to Ops, starting at bit 0 of Reg.
+  void extractParts(unsigned Reg, LLT Ty, int NumParts,
+                    SmallVectorImpl<unsigned> &Ops);
+
+  MachineIRBuilder MIRBuilder;
+  MachineRegisterInfo &MRI;
+};
+
+} // End namespace llvm.
+
+#endif
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizePass.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizePass.h
new file mode 100644
index 00000000000..e1cc32aa793
--- /dev/null
+++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizePass.h
@@ -0,0 +1,50 @@
+//== llvm/CodeGen/GlobalISel/MachineLegalizePass.h ------------- -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file A pass to convert the target-illegal operations created by IR -> MIR
+/// translation into ones the target expects to be able to select. This may
+/// occur in multiple phases, for example G_ADD <2 x i8> -> G_ADD <2 x i16> ->
+/// G_ADD <4 x i16>.
+///
+/// The LegalizeHelper class is where most of the work happens, and is designed
+/// to be callable from other passes that find themselves with an illegal
+/// instruction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
+#define LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
+
+#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+class MachineLegalizePass : public MachineFunctionPass {
+public:
+  static char ID;
+
+private:
+
+  /// Initialize the field members using \p MF.
+  void init(MachineFunction &MF);
+
+public:
+  // Ctor, nothing fancy.
+  MachineLegalizePass();
+
+  const char *getPassName() const override {
+    return "MachineLegalizePass";
+  }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+};
+} // End namespace llvm.
+
+#endif
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h
index 96ddadfc993..1ba1a75f32f 100644
--- a/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineLegalizer.h
@@ -71,17 +71,6 @@ public:
 
   MachineLegalizer();
 
-  /// Replace \p MI by a sequence of legal instructions that can implement the
-  /// same operation. Note that this means \p MI may be deleted, so any iterator
-  /// steps should be performed before calling this function.
-  ///
-  /// Considered as an opaque blob, the legal code will use and define the same
-  /// registers as \p MI.
-  ///
-  /// \returns true if the function is modified, false if the instruction was
-  /// already legal.
-  bool legalizeInstr(MachineInstr &MI) const;
-
   /// Compute any ancillary tables needed to quickly decide how an operation
   /// should be handled. This must be called after all "set*Action"methods but
   /// before any query is made or incorrect results may be returned.
diff --git a/llvm/include/llvm/CodeGen/TargetPassConfig.h b/llvm/include/llvm/CodeGen/TargetPassConfig.h
index 9309655a972..656433dd987 100644
--- a/llvm/include/llvm/CodeGen/TargetPassConfig.h
+++ b/llvm/include/llvm/CodeGen/TargetPassConfig.h
@@ -218,6 +218,14 @@ public:
   virtual bool addIRTranslator() { return true; }
 
   /// This method may be implemented by targets that want to run passes
+  /// immediately before legalization.
+  virtual void addPreLegalizeMachineIR() {}
+
+  /// This method should install a legalize pass, which converts the instruction
+  /// sequence into one that can be selected by the target.
+  virtual bool addLegalizeMachineIR() { return true; }
+
+  /// This method may be implemented by targets that want to run passes
   /// immediately before the register bank selection.
   virtual void addPreRegBankSelect() {}
 
diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h
index 1c0610dcf30..12a5f43ab92 100644
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -214,6 +214,7 @@ void initializeMachineCopyPropagationPass(PassRegistry&);
 void initializeMachineDominanceFrontierPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);
 void initializeMachineFunctionPrinterPassPass(PassRegistry&);
+void initializeMachineLegalizePassPass(PassRegistry&);
 void initializeMachineLICMPass(PassRegistry&);
 void initializeMachineLoopInfoPass(PassRegistry&);
 void initializeMachineModuleInfoPass(PassRegistry&);
diff --git a/llvm/include/llvm/Target/GenericOpcodes.td b/llvm/include/llvm/Target/GenericOpcodes.td
index 97036350171..4c297322aa7 100644
--- a/llvm/include/llvm/Target/GenericOpcodes.td
+++ b/llvm/include/llvm/Target/GenericOpcodes.td
@@ -58,6 +58,27 @@ def G_OR : Instruction {
 }
 
 //------------------------------------------------------------------------------
+// Variadic ops
+//------------------------------------------------------------------------------
+
+// Extract multiple registers specified size, starting from blocks given by
+// indexes. This will almost certainly be mapped to sub-register COPYs after
+// register banks have been selected.
+def G_EXTRACT : Instruction {
+  let OutOperandList = (outs variable_ops);
+  let InOperandList = (ins variable_ops);
+  let hasSideEffects = 0;
+}
+
+// Combine a sequence of generic vregs into a single larger value (starting at
+// bit 0).
+def G_SEQUENCE : Instruction {
+  let OutOperandList = (outs unknown:$dst);
+  let InOperandList = (ins variable_ops);
+  let hasSideEffects = 0;
+}
+
+//------------------------------------------------------------------------------
 // Branches.
 //------------------------------------------------------------------------------
 // Generic unconditional branch.
diff --git a/llvm/include/llvm/Target/TargetOpcodes.def b/llvm/include/llvm/Target/TargetOpcodes.def
index cfb0649191a..297ff82ccfd 100644
--- a/llvm/include/llvm/Target/TargetOpcodes.def
+++ b/llvm/include/llvm/Target/TargetOpcodes.def
@@ -172,6 +172,14 @@ HANDLE_TARGET_OPCODE(G_OR)
 /// stack-based object.
 HANDLE_TARGET_OPCODE(G_FRAME_INDEX)
 
+/// Generic instruction to extract blocks of bits from the register given
+/// (typically a sub-register COPY after instruction selection).
+HANDLE_TARGET_OPCODE(G_EXTRACT)
+
+/// Generic instruction to paste a variable number of components together into a
+/// larger register.
+HANDLE_TARGET_OPCODE(G_SEQUENCE)
+
 /// Generic BRANCH instruction. This is an unconditional branch.
 HANDLE_TARGET_OPCODE(G_BR)
 
diff --git a/llvm/include/llvm/Target/TargetSubtargetInfo.h b/llvm/include/llvm/Target/TargetSubtargetInfo.h
index b929070484f..750427debde 100644
--- a/llvm/include/llvm/Target/TargetSubtargetInfo.h
+++ b/llvm/include/llvm/Target/TargetSubtargetInfo.h
@@ -27,6 +27,7 @@ class CallLowering;
 class DataLayout;
 class MachineFunction;
 class MachineInstr;
+class MachineLegalizer;
 class RegisterBankInfo;
 class SDep;
 class SUnit;
@@ -94,6 +95,10 @@ public:
     return nullptr;
   }
 
+  virtual const MachineLegalizer *getMachineLegalizer() const {
+    return nullptr;
+  }
+
   /// getRegisterInfo - If register information is available, return it.  If
   /// not, return null.
   ///