[GlobalISel] Introduce a simple instruction selector.

[ab]

Summary

This is hopefully mostly straightforward, with various open questions
peppered around as FIXMEs.

This also includes a couple changes to MRI (around constrainRegClass and
gvreg sizes).  I'm not sure any of them is a good idea, but beyond that,
they cause anything that currently links in CodeGen to fail to link
(because GlobalISel is a separate library).
I'm not sure if this is a layering violation, or whether we should force
users to also link in GlobalISel (if they want to use GlobalISel).
Probably the former, in which case: any ideas where to put the changes?

Also, I don't think it's currently possibly to test the emission of
copies of defs without doing the fixup on non-generic instructions
(see FIXME).  Ideas welcome, otherwise I can just remove the code
for now.

[MatzeB]

I just looked at the MachineRegisterInfo parts. This is also a highlevel comment, not necessarily about this patch (which just continues the current direction): It seems to me like generic regs and "normal" vregs don't have that much in common, they mostly share the same kind of MachineOperand and the same def/use lists. Apart from that they contain different information (register bank + size vs. register class). Wouldn't it make sense to introduce a new MachineOperand kind for them and separate them from "normal" vregs?

lib/CodeGen/GlobalISel/InstructionSelect.cpp

38 ↗

(On Diff #64013)

Twine Message?

[arsenm]

lib/CodeGen/GlobalISel/InstructionSelect.cpp

22 ↗

(On Diff #64013)

instruction-select

27 ↗

(On Diff #64013)

Use DEBUG_TYPE macro

27–32 ↗

(On Diff #64013)

You can use INITIALIZE_PASS instead of repeating BEGIN/END

43–44 ↗

(On Diff #64013)

Single quotes around '\n'

71–72 ↗

(On Diff #64013)

Braces

lib/CodeGen/MachineRegisterInfo.cpp

47 ↗

(On Diff #64013)

1 bit condition registers?

lib/Target/AArch64/AArch64InstructionSelector.cpp

88 ↗

(On Diff #64013)

I don't think targets should need to have their own DEBUG here

157 ↗

(On Diff #64013)

Single quotes around '\n'

[echristo]

include/llvm/Target/TargetSubtargetInfo.h

93–95 ↗

(On Diff #64013)

Do you really intend for this to be a subtarget feature?

lib/CodeGen/MachineRegisterInfo.cpp

42 ↗

(On Diff #64013)

These ifdefs look like they should be made a bit more generic in some way?

142–145 ↗

(On Diff #64013)

Sadly, don't do this with commented out code. Perhaps something to fix first?

lib/Target/AArch64/AArch64InstructionSelector.cpp

103 ↗

(On Diff #64013)

These seem a bit ... overly assert-y.

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir

3 ↗

(On Diff #64013)

Comment this a bit more please, what you're checking for etc.

[t.p.northover]

lib/Target/AArch64/AArch64InstructionSelector.cpp

135 ↗

(On Diff #64013)

This can probably be based on I.getType() rather than singling out some particular register.

143 ↗

(On Diff #64013)

From here on seems like it would be better off outside the switch. It applies to the vast majority of instructions.

155 ↗

(On Diff #64013)

Do we have a policy on implicit ops on generic MachineInstrs? I'm guessing we don't expect there to be any, but if not we might want getNumExplicitOperands instead.

[dberris]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

32–35 ↗

(On Diff #64013)

Is a boolean sufficient for conveying the failure scenario for selection?

How do specific instruction selections convey the nuance of the failure? Could there be multiple passes on the same function caused by a failure to select -- maybe because there's not enough information yet?

For example, if an instruction is ignored by the selector, or replaced by a no-op, does it have to return failure? What will that cause the InstructionSelect pass to do? I'm not sure if that documentation has to happen in this interface or in the InstructionSelect pass instead.

lib/CodeGen/GlobalISel/InstructionSelect.cpp

62–63 ↗

(On Diff #64013)

Somewhat related to my question above on the InstructionSelector interface -- maybe we should delegate the selection error messaging to the implementation?

[• tstellarAMD]

lib/CodeGen/GlobalISel/InstructionSelect.cpp

61 ↗

(On Diff #64013)

Won't this will fail if the target decides to delete the instruction? I think targets should be allowed to delete the instruction, because updating MachineIntr in place is very tedious especially if you need to re-order the operands.

[• tstellarAMD]

lib/CodeGen/GlobalISel/InstructionSelect.cpp

61 ↗

(On Diff #64013)

Nevermind, this looks OK.

[ab]

• Extract gvreg parts of constrainRegClass into a wrapper in RegisterBankInfo (this also avoids the CodeGen->GISel layering problem)
• Add a short explanation for the added tests
• Various cleanups

[ab]

In D22373#484484, @MatzeB wrote:

I just looked at the MachineRegisterInfo parts. This is also a highlevel comment, not necessarily about this patch (which just continues the current direction): It seems to me like generic regs and "normal" vregs don't have that much in common, they mostly share the same kind of MachineOperand and the same def/use lists. Apart from that they contain different information (register bank + size vs. register class). Wouldn't it make sense to introduce a new MachineOperand kind for them and separate them from "normal" vregs?

I agree; I had a few ideas that I wrote down in the MRI FIXME. The one that I currently prefer is to have a type for gvregs, a different one for vregs (so, no 'unsigned' anymore), and overload the relevant parts of MRI/... based on that. WDYT?

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

32–35 ↗

(On Diff #64013)

The way I see it, the contract is very simple: after select(I) succeeds, 'I' cannot be generic anymore, and we cannot have introduced other generic instructions. Anything else is a failure from which we cannot recover.

So, specifically, if a non-generic instruction is ignored or deleted, all is well. But a generic instruction cannot be ignored, only deleted. Does that make sense?

If you're imagining things like:

%a = foo
%b = bar %a

and (ignoring ordering) failing to select %a, but being able to select %b: I don't think that's acceptable, the assumption being that every instruction at selection time is selectable.

We talked about introducing some sort of verifier for this, but I don't have a full answer to that yet.

include/llvm/Target/TargetSubtargetInfo.h

93–95 ↗

(On Diff #64013)

No, and I don't think the other GISel passes should be either, only the *Info/Selector classes should. Do you agree?

lib/CodeGen/GlobalISel/InstructionSelect.cpp

62–63 ↗

(On Diff #64013)

Hmm, I figured that would pretty much duplicate the exact same error message in each implementation. Do you envision useful differences?

lib/Target/AArch64/AArch64InstructionSelector.cpp

103 ↗

(On Diff #64013)

Isn't it? I changed it to pass those when constructing the selector in the subtarget; there's more awkwardness involved there (RBI vs Subtarget), would appreciate another look!

143 ↗

(On Diff #64013)

My gut feeling was to avoid generalizing for now, and make sure that better abstractions emerge as we support more instructions.

But for this specific piece of logic, I agree it's probably going to be very common. I extract it out into a "fixup operands" helper, let me know what you think.

155 ↗

(On Diff #64013)

I assumed we don't get implicit ops, but it's good that you mention that: I added an assert for now; we can revisit if we end up with a good reason to use them.

[ab]

lib/CodeGen/MachineRegisterInfo.cpp

138–141 ↗

(On Diff #64541)

Got around to investigating; fixed (and added the assert) in r276012.

[dberris]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

33–36 ↗

(On Diff #64541)

I'm thinking about this from the xray point of view, so let me expound a little.

Consider when for example we see a pseudo instruction like: PATCHABLE_FUNCTION_ENTER or PATCHABLE_RET -- right now it's selected on a per-platform basis when lowering. If we were to change this to become generic instructions instead (i.e. not pseudo instructions), we can then select the appropriate lowering by default (say, for PATCHABLE_FUNCTION_ENTER it would just disappear, and PATCHABLE_RET will just unpack the machine opcodes it wraps), and specialise on a per-platform basis.

We're thinking of cases where say we have other instructions that we'd like to conditionally prepend or append with the appropriate sleds, without having to explicitly mark them at a higher level too (for example, looking at tail exits, sibling exits, or even before/after calls to a whitelist of functions).

Maybe the question is whether XRay sled emission should happen at selection time, or stay in lowering as it is today?

lib/CodeGen/GlobalISel/InstructionSelect.cpp

63–64 ↗

(On Diff #64541)

I think adding more nuance to it might be useful -- say, instead of just 'cannot select an instruction' it could be that there might be cases that the instruction was malformed (some operands were outside some range, or some invariant was violated -- i.e. this should only appear once in a function but it appears multiple times). Maybe that's a legalisation issue though and the error might be better there. Maybe it'd be fine to extend later when we have more concrete cases where it matters.

[ab]

• Rebase onto LLT
• Fail instead of asserting on currently unsupported constructs
• Enforce a few additional constraints (in particular: generic ops can only have vreg operands, that have to be on the same bank)
• Don't constrain with COPYs (as we can't test this right now)

[ab]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

34–37 ↗

(On Diff #64915)

The XRay perspective is an interesting one. Have you considered treating this as a legalization problem? So, you insert your generic instructions at IR->MI translation time; the target declares how it wants to handle them. If they're not legal, do your common, target-independent, lowering. Would that make sense?

In general, I'd rather not have selection be "tentative", with fallbacks and whatnot. I think one shared goal is to be able to definitively tell whether a given instruction will be selectable or not, without actually trying to select it. The hope is to then be able to statically figure out the constructs that "cannot select".

include/llvm/Target/TargetSubtargetInfo.h

93–95 ↗

(On Diff #64915)

Sorry, I misread when I first answered. Let me try again ;)

Yes, the InstructionSelector is intentionally specific to a subtarget. Right now (especially for AArch64), there's not much to specialize, but I'm hoping that'll let us separate out feature-specific code (so instead of a monster TLI, we could maybe have a hierarchy, say avx512>avx>sse, if that makes sense?)

lib/CodeGen/GlobalISel/InstructionSelect.cpp

64–65 ↗

(On Diff #64915)

That's an interesting point; first, do you agree that any of these invariants being violated is a bug? (be it in the legalizer, or in the IR translator, or ...)

The general idea is: an extended machine verifier - specialized for each phase, via MF properties - would enforce these invariant. Anything coming into the selector has to be selectable. It's the responsibility of the legalizer (and target-specific transforms, if applicable) to create well-formed instructions by then.

[qcolombet]

Hi Ahmed,

Looks mostly good to me. Couple of inlined comment. Mainly, I believe we can avoid the ifdef in MRI::setRegClass and the getInstructionSelect may live somewhere else and take an additional parameter.

Cheers,
-Quentin

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

35 ↗

(On Diff #64915)

More accurately, I has been replaced by a sequence of instructions where this condition applies.
But I can live with that shortcut :).

include/llvm/CodeGen/TargetPassConfig.h

229 ↗

(On Diff #64915)

Add a comment for that method.
Also add an additional hook for inject PreGlobalInstructionSelect passes. (Could be a follow-up patch.)

include/llvm/Target/TargetSubtargetInfo.h

93–95 ↗

(On Diff #64915)

FWIW, that’s how I envisioned the thing, that being said, maybe we should have a different interface elsewhere, like getInstructionSelector(MF)?
The idea would be to have the avx512>avx etc. distinction but also things that depends on the function attribute like optimize for code size. The MF allows us to access the function attributes and the sub target.

lib/CodeGen/GlobalISel/InstructionSelect.cpp

51 ↗

(On Diff #64915)

Should this fixme appear in the IRTranslator instead?

52 ↗

(On Diff #64915)

Could you assert on an unchanged number of block within the loop or something, so that we know when we have to properly handle the case?

69 ↗

(On Diff #64915)

Agreed on all the FIXMEs, plus we should set a property after-isel on the function. That’s how we will selectively enable the new checks.

lib/CodeGen/MachineRegisterInfo.cpp

60 ↗

(On Diff #64915)

I would just clear the whole map at the end of the select pass. Will avoid the ifdef and the cost for the extract logic.

[ab]

Rebase and address Quentin's review comments:

• clear all vreg sizes once, at the end of isel; assert that the class agrees with that size
• expand on some comments
• add TargetPassConfig::addPreGlobalInstructionSelect callback

include/llvm/Target/TargetSubtargetInfo.h

93–95 ↗

(On Diff #64915)

You're right, I had not considered specializing on optsize. I'll have to think about the right solution for this. In the meantime, is yet another FIXME palatable? ;)

lib/CodeGen/GlobalISel/InstructionSelect.cpp

51 ↗

(On Diff #64915)

I'm not sure; I figured, select being the final step, anything that doesn't belong elsewhere ought to be set here.

52 ↗

(On Diff #64915)

Good idea; added an assert.

lib/CodeGen/MachineRegisterInfo.cpp

60 ↗

(On Diff #64915)

Eh, I'm no fan of either approach, but clearing once is certainly more efficient.

But really, I'm not sure the separate map is the best solution to begin with; it seems redundant and brittle. What do you think of querying the MI for the def size? (or maybe invert that relationship, and keep the type with the vreg info in the first place?).

[qcolombet]

lib/CodeGen/MachineRegisterInfo.cpp

60 ↗

(On Diff #65370)

Actually what I had in mind was to get the size from the type with, like you said, querying the MI for the def size (via getUniqueDef). However, we would still need to access this information from the vreg.
As having the type on the vreg, no, that does not work. Vregs can change type based on their uses (like and s64, add <2 x s32>).

But yeah, long term, this code shouldn't be needed. Add a comment about that?

[ab]

lib/CodeGen/MachineRegisterInfo.cpp

60 ↗

(On Diff #65370)

Actually what I had in mind was to get the size from the type with, like you said, querying the MI for the def size (via getUniqueDef). However, we would still need to access this information from the vreg.
As having the type on the vreg, no, that does not work. Vregs can change type based on their uses (like and s64, add <2 x s32>).

Right; I suppose you could see a vreg as having an "initial" type, the one on the def. The type(s) of an MI is then just the type(s) of its def(s). I admit it's also somewhat awkward, but at least avoids duplicating the info in a separate, seldom accessed, data structure. Thoughts?

But yeah, long term, this code shouldn't be needed. Add a comment about that?

SGTM, will do. While I'm there, anything else?

[qcolombet]

SGTM, will do. While I'm there, anything else?

I'd move constrainSelectedInstRegOperands in the based class (as a static) to have it available for all the targets.

Other than that LGTM, but please address the other comments first.

Cheers,
-Quentin

lib/CodeGen/MachineRegisterInfo.cpp

60 ↗

(On Diff #65370)

at least avoids duplicating the info in a separate [...] data structure.

Right now, yes, this is duplicated, but with what I had in mind, this is an indirect access: vreg -> getDef -> getType -> getSize. That's not pretty, but that works.

The type(s) of an MI is then just the type(s) of its def(s)

Honestly, the main reason why I discarded this design was because I thought it would have been confusing to ask for the type of some operand and get something not related to the operand. More over, the concept of having typed register is strange to me.
The bottom line is that it may indeed, be more efficient (fewer indirections), but in terms of concept I don't like it. If we manage to spin that in a reasonable manner, that would work.

Anyhow, this is something we need to clean-up at some point (do we actually need the size in the end?), but for now, let us stick on that.

[ab]

Thanks all for the reviews! Committed r276875.

In D22373#495341, @qcolombet wrote:

I'd move constrainSelectedInstRegOperands in the based class (as a static) to have it available for all the targets.

Done.

Other than that LGTM, but please address the other comments first.

Thanks, let me know if I missed anything. We'll still need to discuss the vreg size/type and subtarget/MF issues, but I don't think those are specific to any individual pass.

llvm/trunk/include/llvm/CodeGen/GlobalISel/GISelAccessor.h

 //
 //===----------------------------------------------------------------------===/
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_GISELACCESSOR_H
 #define LLVM_CODEGEN_GLOBALISEL_GISELACCESSOR_H
 
 namespace llvm {
 class CallLowering;
+class InstructionSelector;
 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 InstructionSelector *getInstructionSelector() const {
+    return nullptr;
+  }
   virtual const MachineLegalizer *getMachineLegalizer() const {
     return nullptr;
   }
   virtual const RegisterBankInfo *getRegBankInfo() const { return nullptr;}
 };
 } // End namespace llvm;
 #endif

llvm/trunk/include/llvm/CodeGen/GlobalISel/InstructionSelect.h

+//== llvm/CodeGen/GlobalISel/InstructionSelect.h -----------------*- 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 describes the interface of the MachineFunctionPass
+/// responsible for selecting (possibly generic) machine instructions to
+/// target-specific instructions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H
+#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+/// This pass is responsible for selecting generic machine instructions to
+/// target-specific instructions.  It relies on the InstructionSelector provided
+/// by the target.
+/// Selection is done by examining blocks in post-order, and instructions in
+/// reverse order.
+///
+/// \post for all inst in MF: not isPreISelGenericOpcode(inst.opcode)
+class InstructionSelect : public MachineFunctionPass {
+public:
+  static char ID;
+  const char *getPassName() const override { return "InstructionSelect"; }
+
+  InstructionSelect();
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+};
+} // End namespace llvm.
+
+#endif

llvm/trunk/include/llvm/CodeGen/GlobalISel/InstructionSelector.h

+//==-- llvm/CodeGen/GlobalISel/InstructionSelector.h -------------*- 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 API for the instruction selector.
+/// This class is responsible for selecting machine instructions.
+/// It's implemented by the target. It's used by the InstructionSelect pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
+#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
+
+namespace llvm {
+class MachineInstr;
+class RegisterBankInfo;
+class TargetInstrInfo;
+class TargetRegisterInfo;
+
+/// Provides the logic to select generic machine instructions.
+class InstructionSelector {
+public:
+  virtual ~InstructionSelector() {}
+
+  /// Select the (possibly generic) instruction \p I to only use target-specific
+  /// opcodes. It is OK to insert multiple instructions, but they cannot be
+  /// generic pre-isel instructions.
+  ///
+  /// \returns whether selection succeeded.
+  /// \pre  I.getParent() && I.getParent()->getParent()
+  /// \post
+  ///   if returns true:
+  ///     for I in all mutated/inserted instructions:
+  ///       !isPreISelGenericOpcode(I.getOpcode())
+  ///
+  virtual bool select(MachineInstr &I) const = 0;
+
+protected:
+  InstructionSelector();
+
+  /// Mutate the newly-selected instruction \p I to constrain its (possibly
+  /// generic) virtual register operands to the instruction's register class.
+  /// This could involve inserting COPYs before (for uses) or after (for defs).
+  /// This requires the number of operands to match the instruction description.
+  /// \returns whether operand regclass constraining succeeded.
+  ///
+  // FIXME: Not all instructions have the same number of operands. We should
+  // probably expose a constrain helper per operand and let the target selector
+  // constrain individual registers, like fast-isel.
+  bool constrainSelectedInstRegOperands(MachineInstr &I,
+                                        const TargetInstrInfo &TII,
+                                        const TargetRegisterInfo &TRI,
+                                        const RegisterBankInfo &RBI) const;
+};
+
+} // End namespace llvm.
+
+#endif

llvm/trunk/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h

virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B,
                             unsigned Size) const {
     // Optimistically assume that copies are coalesced. I.e., when
     // they are on the same bank, they are free.
     // Otherwise assume a non-zero cost of 1. The targets are supposed
     // to override that properly anyway if they care.
     return &A != &B;
   }
 
+  /// Constrain the (possibly generic) virtual register \p Reg to \p RC.
+  ///
+  /// \pre \p Reg is a virtual register that either has a bank or a class.
+  /// \returns The constrained register class, or nullptr if there is none.
+  /// \note This is a generic variant of MachineRegisterInfo::constrainRegClass
+  static const TargetRegisterClass *
+  constrainGenericRegister(unsigned Reg, const TargetRegisterClass &RC,
+                           MachineRegisterInfo &MRI);
+
   /// Identifier used when the related instruction mapping instance
   /// is generated by target independent code.
   /// Make sure not to use that identifier to avoid possible collision.
   static const unsigned DefaultMappingID;
 
   /// Identifier used when the related instruction mapping instance
   /// is generated by the default constructor.
   /// Make sure not to use that identifier.

llvm/trunk/include/llvm/CodeGen/MachineRegisterInfo.h

#endif
   /// Although the size should be set at build time, mir infrastructure
   /// is not yet able to do it.
   void setSize(unsigned VReg, unsigned Size);
 
   /// Create and return a new generic virtual register with a size of \p Size.
   /// \pre Size > 0.
   unsigned createGenericVirtualRegister(unsigned Size);
 
+  /// Remove all sizes associated to virtual registers (after instruction
+  /// selection and constraining of all generic virtual registers).
+  void clearVirtRegSizes();
+
   /// getNumVirtRegs - Return the number of virtual registers created.
   ///
   unsigned getNumVirtRegs() const { return VRegInfo.size(); }
 
   /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
   void clearVirtRegs();
 
   /// setRegAllocationHint - Specify a register allocation hint for the

llvm/trunk/include/llvm/CodeGen/TargetPassConfig.h

public:
   /// 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; }
 
+  /// This method may be implemented by targets that want to run passes
+  /// immediately before the (global) instruction selection.
+  virtual void addPreGlobalInstructionSelect() {}
+
+  /// This method should install a (global) instruction selector pass, which
+  /// converts possibly generic instructions to fully target-specific
+  /// instructions, thereby constraining all generic virtual registers to
+  /// register classes.
+  virtual bool addGlobalInstructionSelect() { return true; }
+
   /// Add the complete, standard set of LLVM CodeGen passes.
   /// Fully developed targets will not generally override this.
   virtual void addMachinePasses();
 
   /// Create an instance of ScheduleDAGInstrs to be run within the standard
   /// MachineScheduler pass for this function and target at the current
   /// optimization level.
   ///

llvm/trunk/include/llvm/InitializePasses.h

 void initializeInductiveRangeCheckEliminationPass(PassRegistry&);
 void initializeInferFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeInlineCostAnalysisPass(PassRegistry&);
 void initializeInstCountPass(PassRegistry&);
 void initializeInstNamerPass(PassRegistry&);
 void initializeInstSimplifierPass(PassRegistry&);
 void initializeInstrProfilingLegacyPassPass(PassRegistry &);
 void initializeInstructionCombiningPassPass(PassRegistry&);
+void initializeInstructionSelectPass(PassRegistry &);
 void initializeInterleavedAccessPass(PassRegistry &);
 void initializeInternalizeLegacyPassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAWrapperPassPass(PassRegistry &);
 void initializeLegacyLICMPassPass(PassRegistry&);
 void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(PassRegistry&);

llvm/trunk/include/llvm/Target/TargetSubtargetInfo.h

 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/Support/CodeGen.h"
 #include <vector>
 
 namespace llvm {
 
 class CallLowering;
 class DataLayout;
+class InstructionSelector;
 class MachineFunction;
 class MachineInstr;
 class MachineLegalizer;
 class RegisterBankInfo;
 class SDep;
 class SUnit;
 class TargetFrameLowering;
 class TargetInstrInfo;
public:
   virtual const TargetFrameLowering *getFrameLowering() const {
     return nullptr;
   }
   virtual const TargetLowering *getTargetLowering() const { return nullptr; }
   virtual const SelectionDAGTargetInfo *getSelectionDAGInfo() const {
     return nullptr;
   }
   virtual const CallLowering *getCallLowering() const { return nullptr; }
+
+  // FIXME: This lets targets specialize the selector by subtarget (which lets
+  // us do things like a dedicated avx512 selector).  However, we might want
+  // to also specialize selectors by MachineFunction, which would let us be
+  // aware of optsize/optnone and such.
+  virtual const InstructionSelector *getInstructionSelector() 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;

llvm/trunk/lib/CodeGen/GlobalISel/CMakeLists.txt

 # List of all GlobalISel files.
 set(GLOBAL_ISEL_FILES
       IRTranslator.cpp
+      InstructionSelect.cpp
+      InstructionSelector.cpp
       MachineIRBuilder.cpp
       MachineLegalizeHelper.cpp
       MachineLegalizePass.cpp
       MachineLegalizer.cpp
       RegBankSelect.cpp
       RegisterBank.cpp
       RegisterBankInfo.cpp
       )

llvm/trunk/lib/CodeGen/GlobalISel/GlobalISel.cpp

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

llvm/trunk/lib/CodeGen/GlobalISel/InstructionSelect.cpp

+//===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
+//
+//                     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 InstructionSelect class.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
+
+#define DEBUG_TYPE "instruction-select"
+
+using namespace llvm;
+
+char InstructionSelect::ID = 0;
+INITIALIZE_PASS(InstructionSelect, DEBUG_TYPE,
+                "Select target instructions out of generic instructions",
+                false, false);
+
+InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) {
+  initializeInstructionSelectPass(*PassRegistry::getPassRegistry());
+}
+
+static void reportSelectionError(const MachineInstr &MI, const Twine &Message) {
+  const MachineFunction &MF = *MI.getParent()->getParent();
+  std::string ErrStorage;
+  raw_string_ostream Err(ErrStorage);
+  Err << Message << ":\nIn function: " << MF.getName() << '\n' << MI << '\n';
+  report_fatal_error(Err.str());
+}
+
+bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
+  DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
+
+  const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
+  assert(ISel && "Cannot work without InstructionSelector");
+
+  // FIXME: freezeReservedRegs is now done in IRTranslator, but there are many
+  // other MF/MFI fields we need to initialize.
+
+#ifndef NDEBUG
+  // FIXME: We could introduce new blocks and will need to fix the outer loop.
+  // Until then, keep track of the number of blocks to assert that we don't.
+  const size_t NumBlocks = MF.size();
+#endif
+
+  for (MachineBasicBlock *MBB : post_order(&MF)) {
+    for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(),
+                                             End = MBB->rend();
+         MII != End;) {
+      MachineInstr &MI = *MII++;
+      DEBUG(dbgs() << "Selecting: " << MI << '\n');
+      if (!ISel->select(MI))
+        reportSelectionError(MI, "Cannot select");
+      // FIXME: It would be nice to dump all inserted instructions.  It's not
+      // obvious how, esp. considering select() can insert after MI.
+    }
+  }
+
+  assert(MF.size() == NumBlocks && "Inserting blocks is not supported yet");
+
+  // Check that we did select everything. Do this separately to make sure we
+  // didn't miss any newly inserted instructions.
+  // FIXME: This (and other checks) should move into a verifier, predicated on
+  // a "post-isel" MachineFunction property. That would also let us selectively
+  // enable it depending on build configuration.
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (isPreISelGenericOpcode(MI.getOpcode())) {
+        reportSelectionError(
+            MI, "Generic instruction survived instruction selection");
+      }
+    }
+  }
+
+  // Now that selection is complete, there are no more generic vregs.
+  // FIXME: We're still discussing what to do with the vreg->size map:
+  // it's somewhat redundant (with the def MIs type size), but having to
+  // examine MIs is also awkward.  Another alternative is to track the type on
+  // the vreg instead, but that's not ideal either, because it's saying that
+  // vregs have types, which they really don't. But then again, LLT is just
+  // a size and a "shape": it's probably the same information as regbank info.
+  MF.getRegInfo().clearVirtRegSizes();
+
+  // FIXME: Should we accurately track changes?
+  return true;
+}

llvm/trunk/lib/CodeGen/GlobalISel/InstructionSelector.cpp

+//===- llvm/CodeGen/GlobalISel/InstructionSelector.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 InstructionSelector class.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+#define DEBUG_TYPE "instructionselector"
+
+using namespace llvm;
+
+InstructionSelector::InstructionSelector() {}
+
+bool InstructionSelector::constrainSelectedInstRegOperands(
+    MachineInstr &I, const TargetInstrInfo &TII, const TargetRegisterInfo &TRI,
+    const RegisterBankInfo &RBI) const {
+  MachineBasicBlock &MBB = *I.getParent();
+  MachineFunction &MF = *MBB.getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+
+  for (unsigned OpI = 0, OpE = I.getNumExplicitOperands(); OpI != OpE; ++OpI) {
+    MachineOperand &MO = I.getOperand(OpI);
+    DEBUG(dbgs() << "Converting operand: " << MO << '\n');
+
+    assert(MO.isReg() && "Unsupported binop non-reg operand");
+
+    const TargetRegisterClass *RC = TII.getRegClass(I.getDesc(), OpI, &TRI, MF);
+    assert(RC && "Selected inst should have regclass operand");
+
+    // If the operand is a vreg, we should constrain its regclass, and only
+    // insert COPYs if that's impossible.
+    // If the operand is a physreg, we only insert COPYs if the register class
+    // doesn't contain the register.
+    if (RBI.constrainGenericRegister(MO.getReg(), *RC, MRI))
+      continue;
+
+    DEBUG(dbgs() << "Constraining with COPYs isn't implemented yet");
+    return false;
+  }
+  return true;
+}

llvm/trunk/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp

const RegisterBank *RegisterBankInfo::getRegBankFromConstraints(
 
   const RegisterBank &RegBank = getRegBankFromRegClass(*RC);
   // Sanity check that the target properly implemented getRegBankFromRegClass.
   assert(RegBank.covers(*RC) &&
          "The mapping of the register bank does not make sense");
   return &RegBank;
 }
 
+const TargetRegisterClass *RegisterBankInfo::constrainGenericRegister(
+    unsigned Reg, const TargetRegisterClass &RC, MachineRegisterInfo &MRI) {
+
+  // If the register already has a class, fallback to MRI::constrainRegClass.
+  auto &RegClassOrBank = MRI.getRegClassOrRegBank(Reg);
+  if (RegClassOrBank.is<const TargetRegisterClass *>())
+    return MRI.constrainRegClass(Reg, &RC);
+
+  const RegisterBank *RB = RegClassOrBank.get<const RegisterBank *>();
+  assert(RB && "Generic register does not have a register bank");
+
+  // Otherwise, all we can do is ensure the bank covers the class, and set it.
+  if (!RB->covers(RC))
+    return nullptr;
+
+  MRI.setRegClass(Reg, &RC);
+  return &RC;
+}
+
 RegisterBankInfo::InstructionMapping
 RegisterBankInfo::getInstrMappingImpl(const MachineInstr &MI) const {
   RegisterBankInfo::InstructionMapping Mapping(DefaultMappingID, /*Cost*/ 1,
                                                MI.getNumOperands());
   const MachineFunction &MF = *MI.getParent()->getParent();
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   const TargetRegisterInfo &TRI = *STI.getRegisterInfo();
   const MachineRegisterInfo &MRI = MF.getRegInfo();

llvm/trunk/lib/CodeGen/LLVMTargetMachine.cpp

if (LLVM_UNLIKELY(EnableGlobalISel)) {
 
     // Before running the register bank selector, ask the target if it
     // wants to run some passes.
     PassConfig->addPreRegBankSelect();
 
     if (PassConfig->addRegBankSelect())
       return nullptr;
 
+    PassConfig->addPreGlobalInstructionSelect();
+
+    if (PassConfig->addGlobalInstructionSelect())
+      return nullptr;
+
   } else if (PassConfig->addInstSelector())
     return nullptr;
 
   PassConfig->addMachinePasses();
 
   PassConfig->setInitialized();
 
   return &MMI.getContext();

llvm/trunk/lib/CodeGen/MachineRegisterInfo.cpp

MachineRegisterInfo::createGenericVirtualRegister(unsigned Size) {
   VRegInfo[Reg].first = static_cast<RegisterBank *>(nullptr);
   getVRegToSize()[Reg] = Size;
   RegAllocHints.grow(Reg);
   if (TheDelegate)
     TheDelegate->MRI_NoteNewVirtualRegister(Reg);
   return Reg;
 }
 
+void MachineRegisterInfo::clearVirtRegSizes() {
+#ifndef NDEBUG
+  // Verify that the size of the now-constrained vreg is unchanged.
+  for (auto &VRegToSize : getVRegToSize()) {
+    auto *RC = getRegClass(VRegToSize.first);
+    if (VRegToSize.second != (RC->getSize() * 8))
+      llvm_unreachable(
+          "Virtual register has explicit size different from its class size");
+  }
+#endif
+
+  getVRegToSize().clear();
+}
+
 /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
 void MachineRegisterInfo::clearVirtRegs() {
 #ifndef NDEBUG
   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
     if (!VRegInfo[Reg].second)
       continue;
     verifyUseList(Reg);

llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.h

+//===- AArch64InstructionSelector --------------------------------*- 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 InstructionSelector class for
+/// AArch64.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_AARCH64_AARCH64INSTRUCTIONSELECTOR_H
+#define LLVM_LIB_TARGET_AARCH64_AARCH64INSTRUCTIONSELECTOR_H
+
+#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+
+namespace llvm {
+class AArch64InstrInfo;
+class AArch64RegisterBankInfo;
+class AArch64RegisterInfo;
+class AArch64Subtarget;
+
+class AArch64InstructionSelector : public InstructionSelector {
+public:
+  AArch64InstructionSelector(const AArch64Subtarget &STI,
+                             const AArch64RegisterBankInfo &RBI);
+
+  virtual bool select(MachineInstr &I) const override;
+
+private:
+  const AArch64InstrInfo &TII;
+  const AArch64RegisterInfo &TRI;
+  const AArch64RegisterBankInfo &RBI;
+};
+
+} // End llvm namespace.
+#endif

llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.cpp

+//===- AArch64InstructionSelector.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 InstructionSelector class for
+/// AArch64.
+/// \todo This should be generated by TableGen.
+//===----------------------------------------------------------------------===//
+
+#include "AArch64InstructionSelector.h"
+#include "AArch64InstrInfo.h"
+#include "AArch64RegisterBankInfo.h"
+#include "AArch64RegisterInfo.h"
+#include "AArch64Subtarget.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "aarch64-isel"
+
+using namespace llvm;
+
+#ifndef LLVM_BUILD_GLOBAL_ISEL
+#error "You shouldn't build this"
+#endif
+
+AArch64InstructionSelector::AArch64InstructionSelector(
+    const AArch64Subtarget &STI, const AArch64RegisterBankInfo &RBI)
+    : InstructionSelector(), TII(*STI.getInstrInfo()),
+      TRI(*STI.getRegisterInfo()), RBI(RBI) {}
+
+/// Select the AArch64 opcode for the basic binary operation \p GenericOpc
+/// (such as G_OR or G_ADD), appropriate for the register bank \p RegBankID
+/// and of size \p OpSize.
+/// \returns \p GenericOpc if the combination is unsupported.
+static unsigned selectBinaryOp(unsigned GenericOpc, unsigned RegBankID,
+                               unsigned OpSize) {
+  switch (RegBankID) {
+  case AArch64::GPRRegBankID:
+    switch (OpSize) {
+    case 32:
+      switch (GenericOpc) {
+      case TargetOpcode::G_OR:
+        return AArch64::ORRWrr;
+      case TargetOpcode::G_ADD:
+        return AArch64::ADDWrr;
+      default:
+        return GenericOpc;
+      }
+    case 64:
+      switch (GenericOpc) {
+      case TargetOpcode::G_OR:
+        return AArch64::ORRXrr;
+      case TargetOpcode::G_ADD:
+        return AArch64::ADDXrr;
+      default:
+        return GenericOpc;
+      }
+    }
+  };
+  return GenericOpc;
+}
+
+bool AArch64InstructionSelector::select(MachineInstr &I) const {
+  assert(I.getParent() && "Instruction should be in a basic block!");
+  assert(I.getParent()->getParent() && "Instruction should be in a function!");
+
+  MachineBasicBlock &MBB = *I.getParent();
+  MachineFunction &MF = *MBB.getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+
+  // FIXME: Is there *really* nothing to be done here?  This assumes that
+  // no upstream pass introduces things like generic vreg on copies or
+  // target-specific instructions.
+  // We should document (and verify) that assumption.
+  if (!isPreISelGenericOpcode(I.getOpcode()))
+    return true;
+
+  if (I.getNumOperands() != I.getNumExplicitOperands()) {
+    DEBUG(dbgs() << "Generic instruction has unexpected implicit operands\n");
+    return false;
+  }
+
+  LLT Ty = I.getType();
+  assert(Ty.isValid() && "Generic instruction doesn't have a type");
+
+  // FIXME: Support unsized instructions (e.g., G_BR).
+  if (!Ty.isSized()) {
+    DEBUG(dbgs() << "Unsized generic instructions are unsupported\n");
+    return false;
+  }
+
+  // The size (in bits) of the operation, or 0 for the label type.
+  const unsigned OpSize = Ty.getSizeInBits();
+
+  switch (I.getOpcode()) {
+  case TargetOpcode::G_OR:
+  case TargetOpcode::G_ADD: {
+    DEBUG(dbgs() << "AArch64: Selecting: binop\n");
+
+    // Reject the various things we don't support yet.
+    {
+      const RegisterBank *PrevOpBank = nullptr;
+      for (auto &MO : I.operands()) {
+        // FIXME: Support non-register operands.
+        if (!MO.isReg()) {
+          DEBUG(dbgs() << "Generic inst non-reg operands are unsupported\n");
+          return false;
+        }
+
+        // FIXME: Can generic operations have physical registers operands? If
+        // so, this will need to be taught about that, and we'll need to get the
+        // bank out of the minimal class for the register.
+        // Either way, this needs to be documented (and possibly verified).
+        if (!TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
+          DEBUG(dbgs() << "Generic inst has physical register operand\n");
+          return false;
+        }
+
+        const RegisterBank *OpBank = RBI.getRegBank(MO.getReg(), MRI, TRI);
+        if (!OpBank) {
+          DEBUG(dbgs() << "Generic register has no bank or class\n");
+          return false;
+        }
+
+        if (PrevOpBank && OpBank != PrevOpBank) {
+          DEBUG(dbgs() << "Generic inst operands have different banks\n");
+          return false;
+        }
+        PrevOpBank = OpBank;
+      }
+    }
+
+    const unsigned DefReg = I.getOperand(0).getReg();
+    const RegisterBank &RB = *RBI.getRegBank(DefReg, MRI, TRI);
+
+    const unsigned NewOpc = selectBinaryOp(I.getOpcode(), RB.getID(), OpSize);
+    if (NewOpc == I.getOpcode())
+      return false;
+
+    I.setDesc(TII.get(NewOpc));
+    // FIXME: Should the type be always reset in setDesc?
+    I.setType(LLT());
+
+    // Now that we selected an opcode, we need to constrain the register
+    // operands to use appropriate classes.
+    return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
+  }
+  }
+
+  return false;
+}

llvm/trunk/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 InstructionSelector *getInstructionSelector() 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;
   }
 

llvm/trunk/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 InstructionSelector *AArch64Subtarget::getInstructionSelector() const {
+  assert(GISel && "Access to GlobalISel APIs not set");
+  return GISel->getInstructionSelector();
+}
+
 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();

llvm/trunk/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 "AArch64InstructionSelector.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/InstructionSelect.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"

 }
 
 AArch64TargetMachine::~AArch64TargetMachine() {}
 
 #ifdef LLVM_BUILD_GLOBAL_ISEL
 namespace {
 struct AArch64GISelActualAccessor : public GISelAccessor {
   std::unique_ptr<CallLowering> CallLoweringInfo;
+  std::unique_ptr<InstructionSelector> InstSelector;
   std::unique_ptr<MachineLegalizer> Legalizer;
   std::unique_ptr<RegisterBankInfo> RegBankInfo;
   const CallLowering *getCallLowering() const override {
     return CallLoweringInfo.get();
   }
+  const InstructionSelector *getInstructionSelector() const override {
+    return InstSelector.get();
+  }
   const class MachineLegalizer *getMachineLegalizer() const override {
     return Legalizer.get();
   }
   const RegisterBankInfo *getRegBankInfo() const override {
     return RegBankInfo.get();
   }
 };
 } // End anonymous namespace.

 #ifndef LLVM_BUILD_GLOBAL_ISEL
    GISelAccessor *GISel = new GISelAccessor();
 #else
     AArch64GISelActualAccessor *GISel =
         new AArch64GISelActualAccessor();
     GISel->CallLoweringInfo.reset(
         new AArch64CallLowering(*I->getTargetLowering()));
     GISel->Legalizer.reset(new AArch64MachineLegalizer());
-    GISel->RegBankInfo.reset(
-        new AArch64RegisterBankInfo(*I->getRegisterInfo()));
+
+    auto *RBI = new AArch64RegisterBankInfo(*I->getRegisterInfo());
+
+    // FIXME: At this point, we can't rely on Subtarget having RBI.
+    // It's awkward to mix passing RBI and the Subtarget; should we pass
+    // TII/TRI as well?
+    GISel->InstSelector.reset(new AArch64InstructionSelector(*I, *RBI));
+
+    GISel->RegBankInfo.reset(RBI);
 #endif
     I->setGISelAccessor(*GISel);
   }
   return I.get();
 }
 
 void AArch64leTargetMachine::anchor() { }
 
public:
 
   void addIRPasses()  override;
   bool addPreISel() override;
   bool addInstSelector() override;
 #ifdef LLVM_BUILD_GLOBAL_ISEL
   bool addIRTranslator() override;
   bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
+  bool addGlobalInstructionSelect() override;
 #endif
   bool addILPOpts() override;
   void addPreRegAlloc() override;
   void addPostRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 } // namespace

 bool AArch64PassConfig::addLegalizeMachineIR() {
   addPass(new MachineLegalizePass());
   return false;
 }
 bool AArch64PassConfig::addRegBankSelect() {
   addPass(new RegBankSelect());
   return false;
 }
+bool AArch64PassConfig::addGlobalInstructionSelect() {
+  addPass(new InstructionSelect());
+  return false;
+}
 #endif
 
 bool AArch64PassConfig::addILPOpts() {
   if (EnableCondOpt)
     addPass(createAArch64ConditionOptimizerPass());
   if (EnableCCMP)
     addPass(createAArch64ConditionalCompares());
   if (EnableMCR)

llvm/trunk/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
+      AArch64InstructionSelector.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()

llvm/trunk/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

public:
   void addIRPasses() override;
   bool addPreISel() override;
   void addMachineSSAOptimization() override;
   bool addInstSelector() override;
 #ifdef LLVM_BUILD_GLOBAL_ISEL
   bool addIRTranslator() override;
   bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
+  bool addGlobalInstructionSelect() override;
 #endif
   void addFastRegAlloc(FunctionPass *RegAllocPass) override;
   void addOptimizedRegAlloc(FunctionPass *RegAllocPass) override;
   void addPreRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 

 
 bool GCNPassConfig::addLegalizeMachineIR() {
   return false;
 }
 
 bool GCNPassConfig::addRegBankSelect() {
   return false;
 }
+
+bool GCNPassConfig::addGlobalInstructionSelect() {
+  return false;
+}
 #endif
 
 void GCNPassConfig::addPreRegAlloc() {
   // This needs to be run directly before register allocation because
   // earlier passes might recompute live intervals.
   // TODO: handle CodeGenOpt::None; fast RA ignores spill weights set by the pass
   if (getOptLevel() > CodeGenOpt::None) {
     insertPass(&MachineSchedulerID, &SIFixControlFlowLiveIntervalsID);

llvm/trunk/test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir

+# RUN: llc -O0 -run-pass=instruction-select -global-isel %s -o - | FileCheck %s
+# REQUIRES: global-isel
+
+# Test the instruction selector.
+# As we support more instructions, we need to split this up.
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64-apple-ios"
+
+  define void @add_s32_gpr() { ret void }
+  define void @add_s64_gpr() { ret void }
+
+  define void @or_s32_gpr() { ret void }
+  define void @or_s64_gpr() { ret void }
+
+...
+
+---
+# Check that we select a 32-bit GPR G_ADD into ADDWrr on GPR32.
+# Also check that we constrain the register class of the COPY to GPR32.
+# CHECK-LABEL: name: add_s32_gpr
+name:            add_s32_gpr
+alignment:       2
+isSSA:           true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %1 = ADDWrr %0, %0
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(32) = COPY %w0
+    %1(32) = G_ADD s32 %0, %0
+...
+
+---
+# Same as add_s32_gpr, for 64-bit operations.
+# CHECK-LABEL: name: add_s64_gpr
+name:            add_s64_gpr
+alignment:       2
+isSSA:           true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %x0
+# CHECK:    %1 = ADDXrr %0, %0
+body:             |
+  bb.0:
+    liveins: %x0
+
+    %0(64) = COPY %x0
+    %1(64) = G_ADD s64 %0, %0
+...
+
+---
+# Same as add_s32_gpr, for G_OR operations.
+# CHECK-LABEL: name: or_s32_gpr
+name:            or_s32_gpr
+alignment:       2
+isSSA:           true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %1 = ORRWrr %0, %0
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(32) = COPY %w0
+    %1(32) = G_OR s32 %0, %0
+...
+
+---
+# Same as add_s64_gpr, for G_OR operations.
+# CHECK-LABEL: name: or_s64_gpr
+name:            or_s64_gpr
+alignment:       2
+isSSA:           true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %x0
+# CHECK:    %1 = ORRXrr %0, %0
+body:             |
+  bb.0:
+    liveins: %x0
+
+    %0(64) = COPY %x0
+    %1(64) = G_OR s64 %0, %0
+...