GlobalISel: add an actual legalizer

[t.p.northover]

Summary

This is the final chunk of my original legalizer outline (well, there were a couple more transformations originally, but they're trivial from a review perspective). It adds a helper class to actually perform legalization, and a pass that currently iterates through a MachineFunction applying it to each instruction. Just one transformation is implemented for now.

[qcolombet]

Hi Tim,

LGTM modulo the name of the extract/sequence things. I don’t think it is a good idea to be close to the subreg world at this point.
See comment inlined.

Cheers,
-Quentin

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

155

I would prefer we stick to extract, extract subreg is highly correlated with sub registers, which is not what we do here.

If you have idea for a different name that would work as well :).
When I come up with the name I had "bitfield extract” in mind. But with can think that as a pack as well or a scatter. Pack/unpack for build_sequence/extract may be good because it shows up the symmetry between the two.

Anyhow, open to suggestion but not g_extract_subregs, it is too close to extract_subreg while being too different.

158

In my mind the size was not necessarily the same for all extracted operands.
That being said, we don’t have multiple types for now, nor actual use cases, so this is fine.

166

Ditto, stick with G_SEQUENCE, or G_BUILD_SEQUENCE.

172

Add a pre condition that the sum of the size of the arguments must be equal to the size of the \p Ty.

include/llvm/Target/GenericOpcodes.td

49

G_EXTRACT.

57

G_SEQUENCE.

lib/CodeGen/GlobalISel/MachineLegalizePass.cpp

28

Use DEBUG_TYPE

49

This may impact the APIs, so maybe we should settle that now.

lib/CodeGen/LLVMTargetMachine.cpp

170

if …
return nullptr;

test/CodeGen/AArch64/GlobalISel/legalize-add.mir

23

This one shouldn’t use DAG

[t.p.northover]

Thanks Quentin! Committed with the suggested changes as r276461.

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

158

Working on it (just whacking a SmallVector into the MachineInstr)! But I'll upgrade G_EXTRACT afterwards.

lib/CodeGen/GlobalISel/MachineLegalizePass.cpp

49

Soon, but adding enough to test a multi-step legalization would bloat this patch.

include/llvm/CodeGen/GlobalISel/GISelAccessor.h

 //
 //===----------------------------------------------------------------------===/
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_GISELACCESSOR_H
 #define LLVM_CODEGEN_GLOBALISEL_GISELACCESSOR_H
 
 namespace llvm {
 class CallLowering;
+class MachineLegalizer;
 class RegisterBankInfo;
 
 /// The goal of this helper class is to gather the accessor to all
 /// the APIs related to GlobalISel.
 /// It should be derived to feature an actual accessor to the GISel APIs.
 /// The reason why this is not simply done into the subtarget is to avoid
 /// spreading ifdefs around.
 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;
 #endif

include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

public:
   /// Set the insertion point to the beginning (\p Beginning = true) or end
   /// (\p Beginning = false) of \p MBB.
   /// \pre \p MBB must be contained by getMF().
   void setMBB(MachineBasicBlock &MBB, bool Beginning = false);
 
   /// 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.
   void setDebugLoc(const DebugLoc &DL) { this->DL = DL; }
 
   /// Build and insert <empty> = \p Opcode [\p Ty] <empty>.
   /// \p Ty is the type of the instruction if \p Opcode describes
   /// a generic machine instruction. \p Ty must be nullptr if \p Opcode
public:
 
   /// Build and insert <empty> = \p Opcode <empty>.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre not isPreISelGenericOpcode(\p Opcode)
   ///
   /// \return The newly created instruction.
   MachineInstr *buildInstr(unsigned Opcode);
+
+  /// 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_SUBREGS 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 *buildExtractSubregs(LLT Ty, ArrayRef<unsigned> Results,
+                                    unsigned Src, ArrayRef<unsigned> Indexes);
+
+  /// Build and insert \p Res<def> = G_REG_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.
+  ///
+  /// \return The newly created instruction.
+  MachineInstr *buildRegSequence(LLT Ty, unsigned Res, ArrayRef<unsigned> Ops);
 };
 
 } // End namespace llvm.
 #endif // LLVM_CODEGEN_GLOBALISEL_MACHINEIRBUILDER_H

include/llvm/CodeGen/GlobalISel/MachineLegalizeHelper.h

+//== 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

include/llvm/CodeGen/GlobalISel/MachineLegalizePass.h

+//== 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

include/llvm/CodeGen/GlobalISel/MachineLegalizer.h

enum LegalizeAction : std::uint8_t {
 
     /// This operation is completely unsupported on the target. A programming
     /// error has occurred.
     Unsupported,
   };
 
   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.
   void computeTables();
 
   /// More friendly way to set an action for common types that have an LLT
   /// representation.
   void setAction(unsigned Opcode, LLT Ty, LegalizeAction Action) {

include/llvm/CodeGen/TargetPassConfig.h

virtual bool addInstSelector() {
     return true;
   }
 
   /// This method should install an IR translator pass, which converts from
   /// LLVM code to machine instructions with possibly generic opcodes.
   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() {}
 
   /// This method should install a register bank selector pass, which
   /// assigns register banks to virtual registers without a register
   /// class or register banks.
   virtual bool addRegBankSelect() { return true; }
 

include/llvm/InitializePasses.h

 void initializeMachineBlockPlacementStatsPass(PassRegistry&);
 void initializeMachineBranchProbabilityInfoPass(PassRegistry&);
 void initializeMachineCSEPass(PassRegistry&);
 void initializeMachineCombinerPass(PassRegistry &);
 void initializeMachineCopyPropagationPass(PassRegistry&);
 void initializeMachineDominanceFrontierPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);
 void initializeMachineFunctionPrinterPassPass(PassRegistry&);
+void initializeMachineLegalizePassPass(PassRegistry&);
 void initializeMachineLICMPass(PassRegistry&);
 void initializeMachineLoopInfoPass(PassRegistry&);
 void initializeMachineModuleInfoPass(PassRegistry&);
 void initializeMachinePostDominatorTreePass(PassRegistry&);
 void initializeMachineRegionInfoPassPass(PassRegistry&);
 void initializeMachineSchedulerPass(PassRegistry&);
 void initializeMachineSinkingPass(PassRegistry&);
 void initializeMachineTraceMetricsPass(PassRegistry&);

include/llvm/Target/GenericOpcodes.td

 def G_OR : Instruction {
   let OutOperandList = (outs unknown:$dst);
   let InOperandList = (ins unknown:$src1, unknown:$src2);
   let hasSideEffects = 0;
   let isCommutable = 1;
 }
 
 //------------------------------------------------------------------------------
+// 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_SUBREGS : 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_REG_SEQUENCE : Instruction {
+  let OutOperandList = (outs unknown:$dst);
+  let InOperandList = (ins variable_ops);
+  let hasSideEffects = 0;
+}
+
+//------------------------------------------------------------------------------
 // Branches.
 //------------------------------------------------------------------------------
 // Generic unconditional branch.
 def G_BR : Instruction {
   let OutOperandList = (outs);
   let InOperandList = (ins unknown:$src1);
   let hasSideEffects = 0;
   let isBranch = 1;
   let isTerminator = 1;
 }
 
 // TODO: Add the other generic opcodes.

include/llvm/Target/TargetOpcodes.def

 HANDLE_TARGET_OPCODE_MARKER(PRE_ISEL_GENERIC_OPCODE_START, G_ADD)
 
 /// Generic Bitwise-AND instruction.
 HANDLE_TARGET_OPCODE(G_AND)
 
 /// Generic Bitwise-OR instruction.
 HANDLE_TARGET_OPCODE(G_OR)
 
+/// Generic instruction to extract blocks of bits from the register given
+/// (typically a sub-register COPY after instruction selection).
+HANDLE_TARGET_OPCODE(G_EXTRACT_SUBREGS)
+
+/// Generic instruction to paste a variable number of components together into a
+/// larger register.
+HANDLE_TARGET_OPCODE(G_REG_SEQUENCE)
+
 /// Generic BRANCH instruction. This is an unconditional branch.
 HANDLE_TARGET_OPCODE(G_BR)
 
 // TODO: Add more generic opcodes as we move along.
 
 /// Marker for the end of the generic opcode.
 /// This is used to check if an opcode is in the range of the
 /// generic opcodes.
 HANDLE_TARGET_OPCODE_MARKER(PRE_ISEL_GENERIC_OPCODE_END, G_BR)
 
 /// BUILTIN_OP_END - This must be the last enum value in this list.
 /// The target-specific post-isel opcode values start here.
 HANDLE_TARGET_OPCODE_MARKER(GENERIC_OP_END, PRE_ISEL_GENERIC_OPCODE_END)

include/llvm/Target/TargetSubtargetInfo.h

 #include <vector>
 
 namespace llvm {
 
 class CallLowering;
 class DataLayout;
 class MachineFunction;
 class MachineInstr;
+class MachineLegalizer;
 class RegisterBankInfo;
 class SDep;
 class SUnit;
 class TargetFrameLowering;
 class TargetInstrInfo;
 class TargetLowering;
 class TargetRegisterClass;
 class TargetRegisterInfo;
public:
   }
   virtual const CallLowering *getCallLowering() const { return nullptr; }
   /// Target can subclass this hook to select a different DAG scheduler.
   virtual RegisterScheduler::FunctionPassCtor
       getDAGScheduler(CodeGenOpt::Level) const {
     return nullptr;
   }
 
+  virtual const MachineLegalizer *getMachineLegalizer() const {
+    return nullptr;
+  }
+
   /// getRegisterInfo - If register information is available, return it.  If
   /// not, return null.
   ///
   virtual const TargetRegisterInfo *getRegisterInfo() const { return nullptr; }
 
   /// If the information for the register banks is available, return it.
   /// Otherwise return nullptr.
   virtual const RegisterBankInfo *getRegBankInfo() const { return nullptr; }

lib/CodeGen/GlobalISel/CMakeLists.txt

 # List of all GlobalISel files.
 set(GLOBAL_ISEL_FILES
       IRTranslator.cpp
       MachineIRBuilder.cpp
+      MachineLegalizeHelper.cpp
+      MachineLegalizePass.cpp
       MachineLegalizer.cpp
       RegBankSelect.cpp
       RegisterBank.cpp
       RegisterBankInfo.cpp
       )
 
 # Add GlobalISel files to the dependencies if the user wants to build it.
 if(LLVM_BUILD_GLOBAL_ISEL)

lib/CodeGen/GlobalISel/GlobalISel.cpp

 
 void llvm::initializeGlobalISel(PassRegistry &Registry) {
 }
 
 #else
 
 void llvm::initializeGlobalISel(PassRegistry &Registry) {
   initializeIRTranslatorPass(Registry);
+  initializeMachineLegalizePassPass(Registry);
   initializeRegBankSelectPass(Registry);
 }
 #endif // LLVM_BUILD_GLOBAL_ISEL

lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

 }
 
 MachineInstr *MachineIRBuilder::buildInstr(unsigned Opcode, LLT Ty,
                                            MachineBasicBlock &BB) {
   MachineInstr *NewMI = buildInstr(Opcode, Ty);
   MachineInstrBuilder(getMF(), NewMI).addMBB(&BB);
   return NewMI;
 }
+
+MachineInstr *MachineIRBuilder::buildAdd(LLT Ty, unsigned Res, unsigned Op0,
+                                         unsigned Op1) {
+  return buildInstr(TargetOpcode::G_ADD, Ty, Res, Op0, Op1);
+}
+
+MachineInstr *
+MachineIRBuilder::buildExtractSubregs(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_SUBREGS, 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::buildRegSequence(LLT Ty, unsigned Res,
+                                                 ArrayRef<unsigned> Ops) {
+  MachineInstr *NewMI = buildInstr(TargetOpcode::G_REG_SEQUENCE, Ty);
+  auto MIB = MachineInstrBuilder(getMF(), NewMI);
+  MIB.addReg(Res, RegState::Define);
+  for (auto Op : Ops)
+    MIB.addReg(Op);
+  return NewMI;
+}

lib/CodeGen/GlobalISel/MachineLegalizeHelper.cpp

+//===-- 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.buildExtractSubregs(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.buildRegSequence(MI.getType(), MI.getOperand(0).getReg(),
+                                DstRegs);
+    MI.eraseFromParent();
+    return Legalized;
+  }
+  }
+}

lib/CodeGen/GlobalISel/MachineLegalizePass.cpp

+//===-- 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, "legalize-mir",
+                "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;
+}

lib/CodeGen/GlobalISel/MachineLegalizer.cpp

 #include "llvm/IR/Type.h"
 #include "llvm/Target/TargetOpcodes.h"
 using namespace llvm;
 
 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;
     if (!Ty.isVector())
       continue;
 
     auto &Entry =
         MaxLegalVectorElts[std::make_pair(Op.first.first, Ty.getElementType())];
     Entry = std::max(Entry, Ty.getNumElements());
   }
 
   TablesInitialized = true;
 }
 
 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
 // probably going to need specialized lookup structures for various types before
 // we have any hope of doing well with something like <13 x i3>. Even the common
 // cases should do better than what we have now.
 std::pair<MachineLegalizer::LegalizeAction, LLT>
 MachineLegalizer::getAction(unsigned Opcode, LLT Ty) const {
   assert(TablesInitialized && "backend forgot to call computeTables");
   // 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_REG_SEQUENCE ||
+      Opcode == TargetOpcode::G_EXTRACT_SUBREGS)
+    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);
 
   if (!Ty.isVector()) {
     auto DefaultAction = DefaultActions.find(Opcode);
     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
       return std::make_pair(Legal, Ty);

lib/CodeGen/LLVMTargetMachine.cpp

if (EnableFastISelOption == cl::BOU_TRUE ||
        TM->getO0WantsFastISel()))
     TM->setFastISel(true);
 
   // Ask the target for an isel.
   if (LLVM_UNLIKELY(EnableGlobalISel)) {
     if (PassConfig->addIRTranslator())
       return nullptr;
 
+    PassConfig->addPreLegalizeMachineIR();
+
+    PassConfig->addLegalizeMachineIR();
+
     // Before running the register bank selector, ask the target if it
     // wants to run some passes.
     PassConfig->addPreRegBankSelect();
 
     if (PassConfig->addRegBankSelect())
       return nullptr;
 
   } else if (PassConfig->addInstSelector())

lib/Target/AArch64/AArch64MachineLegalizer.h

+//===- AArch64Machinelegalizer --------------------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file declares the targeting of the Machinelegalizer class for
+/// AArch64.
+/// \todo This should be generated by TableGen.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_AARCH64_AARCH64MACHINELEGALIZER_H
+#define LLVM_LIB_TARGET_AARCH64_AARCH64MACHINELEGALIZER_H
+
+#include "llvm/CodeGen/GlobalISel/Machinelegalizer.h"
+
+namespace llvm {
+
+class LLVMContext;
+
+/// This class provides the information for the target register banks.
+class AArch64MachineLegalizer : public MachineLegalizer {
+public:
+  AArch64MachineLegalizer();
+};
+} // End llvm namespace.
+#endif

lib/Target/AArch64/AArch64MachineLegalizer.cpp

+//===- AArch64MachineLegalizer.cpp -------------------------------*- C++ -*-==//
+//
+//                     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 targeting of the Machinelegalizer class for
+/// AArch64.
+/// \todo This should be generated by TableGen.
+//===----------------------------------------------------------------------===//
+
+#include "AArch64MachineLegalizer.h"
+#include "llvm/CodeGen/ValueTypes.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/Target/TargetOpcodes.h"
+
+using namespace llvm;
+
+#ifndef LLVM_BUILD_GLOBAL_ISEL
+#error "You shouldn't build this"
+#endif
+
+AArch64MachineLegalizer::AArch64MachineLegalizer() {
+  setAction(TargetOpcode::G_ADD, LLT::vector(2, 64), Legal);
+  computeTables();
+}

lib/Target/AArch64/AArch64Subtarget.h

public:
   const AArch64TargetLowering *getTargetLowering() const override {
     return &TLInfo;
   }
   const AArch64InstrInfo *getInstrInfo() const override { return &InstrInfo; }
   const AArch64RegisterInfo *getRegisterInfo() const override {
     return &getInstrInfo()->getRegisterInfo();
   }
   const CallLowering *getCallLowering() const override;
+  const MachineLegalizer *getMachineLegalizer() const override;
   const RegisterBankInfo *getRegBankInfo() const override;
   const Triple &getTargetTriple() const { return TargetTriple; }
   bool enableMachineScheduler() const override { return true; }
   bool enablePostRAScheduler() const override {
     return UsePostRAScheduler;
   }
 
   /// Returns ARM processor family.

lib/Target/AArch64/AArch64Subtarget.cpp

: AArch64GenSubtargetInfo(TT, CPU, FS), ReserveX18(TT.isOSDarwin()),
       InstrInfo(initializeSubtargetDependencies(FS)), TSInfo(),
       TLInfo(TM, *this), GISel() {}
 
 const CallLowering *AArch64Subtarget::getCallLowering() const {
   assert(GISel && "Access to GlobalISel APIs not set");
   return GISel->getCallLowering();
 }
 
+const MachineLegalizer *AArch64Subtarget::getMachineLegalizer() const {
+  assert(GISel && "Access to GlobalISel APIs not set");
+  return GISel->getMachineLegalizer();
+}
+
 const RegisterBankInfo *AArch64Subtarget::getRegBankInfo() const {
   assert(GISel && "Access to GlobalISel APIs not set");
   return GISel->getRegBankInfo();
 }
 
 /// Find the target operand flags that describe how a global value should be
 /// referenced for the current subtarget.
 unsigned char

lib/Target/AArch64/AArch64TargetMachine.cpp

 //===-- AArch64TargetMachine.cpp - Define TargetMachine for AArch64 -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //
 //===----------------------------------------------------------------------===//
 
 #include "AArch64.h"
 #include "AArch64CallLowering.h"
+#include "AArch64MachineLegalizer.h"
 #include "AArch64RegisterBankInfo.h"
 #include "AArch64TargetMachine.h"
 #include "AArch64TargetObjectFile.h"
 #include "AArch64TargetTransformInfo.h"
 #include "llvm/CodeGen/GlobalISel/IRTranslator.h"
+#include "llvm/CodeGen/GlobalISel/MachineLegalizePass.h"
 #include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"

 }
 
 AArch64TargetMachine::~AArch64TargetMachine() {}
 
 #ifdef LLVM_BUILD_GLOBAL_ISEL
 namespace {
 struct AArch64GISelActualAccessor : public GISelAccessor {
   std::unique_ptr<CallLowering> CallLoweringInfo;
+  std::unique_ptr<MachineLegalizer> MachineLegalizer;
   std::unique_ptr<RegisterBankInfo> RegBankInfo;
   const CallLowering *getCallLowering() const override {
     return CallLoweringInfo.get();
   }
+  const class MachineLegalizer *getMachineLegalizer() const override {
+    return MachineLegalizer.get();
+  }
   const RegisterBankInfo *getRegBankInfo() const override {
     return RegBankInfo.get();
   }
 };
 } // End anonymous namespace.
 #endif
 
 const AArch64Subtarget *
I = llvm::make_unique<AArch64Subtarget>(TargetTriple, CPU, FS, *this,
                                             Subtarget.isLittleEndian());
 #ifndef LLVM_BUILD_GLOBAL_ISEL
    GISelAccessor *GISel = new GISelAccessor();
 #else
     AArch64GISelActualAccessor *GISel =
         new AArch64GISelActualAccessor();
     GISel->CallLoweringInfo.reset(
         new AArch64CallLowering(*I->getTargetLowering()));
+    GISel->MachineLegalizer.reset(new AArch64MachineLegalizer());
     GISel->RegBankInfo.reset(
         new AArch64RegisterBankInfo(*I->getRegisterInfo()));
 #endif
     I->setGISelAccessor(*GISel);
   }
   return I.get();
 }
 
AArch64TargetMachine &getAArch64TargetMachine() const {
     return getTM<AArch64TargetMachine>();
   }
 
   void addIRPasses()  override;
   bool addPreISel() override;
   bool addInstSelector() override;
 #ifdef LLVM_BUILD_GLOBAL_ISEL
   bool addIRTranslator() override;
+  bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
 #endif
   bool addILPOpts() override;
   void addPreRegAlloc() override;
   void addPostRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
bool AArch64PassConfig::addInstSelector() {
   return false;
 }
 
 #ifdef LLVM_BUILD_GLOBAL_ISEL
 bool AArch64PassConfig::addIRTranslator() {
   addPass(new IRTranslator());
   return false;
 }
+bool AArch64PassConfig::addLegalizeMachineIR() {
+  addPass(new MachineLegalizePass());
+  return false;
+}
 bool AArch64PassConfig::addRegBankSelect() {
   addPass(new RegBankSelect());
   return false;
 }
 #endif
 
 bool AArch64PassConfig::addILPOpts() {
   if (EnableCondOpt)

lib/Target/AArch64/CMakeLists.txt

 tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM AArch64GenSystemOperands.inc -gen-searchable-tables)
 
 add_public_tablegen_target(AArch64CommonTableGen)
 
 # List of all GlobalISel files.
 set(GLOBAL_ISEL_FILES
       AArch64CallLowering.cpp
+      AArch64MachineLegalizer.cpp
       AArch64RegisterBankInfo.cpp
       )
 
 # Add GlobalISel files to the dependencies if the user wants to build it.
 if(LLVM_BUILD_GLOBAL_ISEL)
   set(GLOBAL_ISEL_BUILD_FILES ${GLOBAL_ISEL_FILES})
 else()
   set(GLOBAL_ISEL_BUILD_FILES"")

test/CodeGen/AArch64/GlobalISel/legalize-add.mir

+# RUN: llc -O0 -run-pass=legalize-mir -global-isel %s -o - 2>&1 | FileCheck %s
+# REQUIRES: global-isel
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64-apple-ios"
+  define void @test_vector_add() {
+  entry:
+    ret void
+  }
+...
+
+---
+name:            test_vector_add
+isSSA:           true
+registers:
+  - { id: 0, class: _ }
+  - { id: 1, class: _ }
+  - { id: 2, class: _ }
+body: |
+  bb.0.entry:
+    liveins: %q0, %q1, %q2, %q3
+    ; CHECK-DAG: name: test_vector_add
+    ; CHECK-DAG: [[LHS_LO:%.*]](128), [[LHS_HI:%.*]](128) = G_EXTRACT_SUBREGS <2 x s64> %0, 0, 128
+    ; CHECK-DAG: [[RHS_LO:%.*]](128), [[RHS_HI:%.*]](128) = G_EXTRACT_SUBREGS <2 x s64> %1, 0, 128
+    ; CHECK: [[RES_LO:%.*]](128) = G_ADD <2 x s64> [[LHS_LO]], [[RHS_LO]]
+    ; CHECK: [[RES_HI:%.*]](128) = G_ADD <2 x s64> [[LHS_HI]], [[RHS_HI]]
+    ; CHECK: %2(256) = G_REG_SEQUENCE <4 x s64> [[RES_LO]], [[RES_HI]]
+
+    %0(256) = G_REG_SEQUENCE <4 x s64> %q0, %q1
+    %1(256) = G_REG_SEQUENCE <4 x s64> %q2, %q3
+    %2(256) = G_ADD <4 x s64> %0, %1
+    %q0, %q1 = G_EXTRACT_SUBREGS <2 x s64> %2, 0, 128
+...