[GlobalISel] Add tentative Selector-emitted tablegen backend.

[ab]

Summary

This adds a basic tablegen backend that analyzes the SelectionDAG patterns to find simple ones that are eligible for GlobalISel-emission.

That's similar to FastISel, with one notable difference: we're not fed ISD opcodes, so we need to map the SDNode operators to generic opcodes. That's done using GINodeEquiv in TargetGlobalISel.td.

Otherwise, this is mostly boilerplate, and lots of filtering of any kind of "complicated" pattern. On AArch64, this is sufficient to match G_ADD up to s64 (to ADDWrr/ADDXrr) and G_BR (to B).

This depends on a local patch that adds a "Widenable" flag to generic instructions (to express what we implicitly rely on about things like G_ADD being OK to do on wider types) (full diff at https://reviews.llvm.org/differential/diff/78609/).

But before we dive into the details, I'd like to get feedback about the approach: we discussed various alternatives:

• invent a new syntax, write new patterns: let's avoid duplicating all the work.
• invent a new syntax, convert older patterns (at checkin- or build-time): I don't think we're at a stage where we can make well-informed decisions about the eventual tablegen design. I'm hoping that, as we add support for SDAG constructs, we get more insight on what we'll eventually need. For now, emitting matchers from SDAG patterns is a small incremental step.
• mutate the existing representation (e.g., starting by adding a "GlobalISel" class to SDNode which have equivalents): we decided against that as one of our goal in the bring-up is to have absolute no impact whatsoever on SelectionDAG.

For the record, this currently generates:

bool AArch64InstructionSelector::selectImpl(MachineInstr &I) const {
  MachineRegisterInfo &MRI = I.getParent()->getParent()->getRegInfo();
  // Src: (add:i32 GPR32:i32:$Rn, GPR32:i32:$Rm)
  // Dst: (ADDWrr:i32 GPR32:i32:$Rn, GPR32:i32:$Rm)
  if ((I.getOpcode() == TargetOpcode::G_ADD) &&
      (MRI.getType(I.getOperand(0).getReg()).equalOrNarrower(LLT::scalar(32))) &&
      (MRI.getType(I.getOperand(1).getReg()).equalOrNarrower(LLT::scalar(32))) &&
      (MRI.getType(I.getOperand(2).getReg()).equalOrNarrower(LLT::scalar(32)))) {
    I.setDesc(TII.get(AArch64::ADDWrr));
    constrainSelectedInstRegOperands(I, TII, TRI, RBI);
    return true;
  }
  // Src: (add:i64 GPR64:i64:$Rn, GPR64:i64:$Rm)
  // Dst: (ADDXrr:i64 GPR64:i64:$Rn, GPR64:i64:$Rm)
  if ((I.getOpcode() == TargetOpcode::G_ADD) &&
      (MRI.getType(I.getOperand(0).getReg()).equalOrNarrower(LLT::scalar(64))) &&
      (MRI.getType(I.getOperand(1).getReg()).equalOrNarrower(LLT::scalar(64))) &&
      (MRI.getType(I.getOperand(2).getReg()).equalOrNarrower(LLT::scalar(64)))) {
    I.setDesc(TII.get(AArch64::ADDXrr));
    constrainSelectedInstRegOperands(I, TII, TRI, RBI);
    return true;
  }
  // Src: (br (bb:Other):$addr)
  // Dst: (B (bb:Other):$addr)
  if ((I.getOpcode() == TargetOpcode::G_BR) &&
      (I.getOperand(0).isMBB())) {
    I.setDesc(TII.get(AArch64::B));
    constrainSelectedInstRegOperands(I, TII, TRI, RBI);
    return true;
  }
  return false;
}

Note that there is no sorting done, so it's pure luck that we pick the s32 ADDWrr for smaller sizes (rather than ADDXrr). We'll need some higher-level sorting to order the matchers appropriately, but picking ADDXrr isn't incorrect anyway (though it might cause constrain failures).

Also note that there's a lot of redundant work done. I'm hoping we can optimize the matchers (much like SDAG does currently), to for instance take advantage of the fact that all operands have the same type (type0) so we don't need to check it again.

Finally, note that this isn't strictly correct with regards to register banks (they're never checked): we'll need to add tablegen support for bank definitions before we can land this.

[rovka]

Hi Ahmed,

I just wanted to say that I like the general idea here, I think it's a good start for some useful prototyping.
I'm looking forward to the register bank handling.

[dsanders]

From https://reviews.llvm.org/differential/diff/78609/:

/// Is this generic instruction "widenable", i.e., is this transform valid:
///   (G_ZEXT (op s8 a, b)) -> (op s32 (G_ZEXT a), (G_ZEXT b))

This transform isn't strictly valid and will produce the wrong result on overflow but that's often ok because LLVM-IR doesn't define the excess bits and there will be explicit extends for when it really matters. However, some targets like Mips do care what those bits are and may misbehave if the excess bits are wrong. Here's a few examples:

• 'addu' where one of the operands is 0x00000001_00000000 produces an unpredictable result on Mips64.
• 'addu' where one of the operands is 0x00000000_80000000 produces an unpredictable result on Mips64.
• 'addu' and 'daddu' will behave differently when given 0x80000000 and 0x80000000 with the former producing 0x0 and the latter producing 0x1_00000000.
• 'addu' and 'daddu' will behave differently when given 0x40000000 and 0x40000000 with the former producing 0xffffffff_80000000 and the latter producing 0x00000000_80000000.

The Widenable flag will eventually need to be controllable so that we can say that i1-i63 are widenable except for i32.

Another one that's likely to be surprising is that ISD::TRUNCATE isn't a nop on Mips. It's a sign-extend for i32 (and technically for also i64 but that has no impact at the moment) and a zero extend for other sizes.

invent a new syntax, convert older patterns (at checkin- or build-time): I don't think we're at a stage where we can make
well-informed decisions about the eventual tablegen design. I'm hoping that, as we add support for SDAG constructs, we
get more insight on what we'll eventually need. For now, emitting matchers from SDAG patterns is a small incremental
step.

My current knowledge of GlobalISel is largely based on reading the code rather than writing it but FWIW I've been sketching a rough tablegen design as I've been catching up on GlobalISel and the sketch is broadly in line with this patch.

One thing I'd like to mention is that the current patch has what I'd call rule-level matching (Matcher), and instruction-property-level matching (MatchOpcode/MatchRegOpType/MatchMBBOp). I think we should have a level in between those two which represents an instruction without testing any properties of that instruction. It's probably best to think of it as a cursor position for the match. The reason for this, is that I expect we'll eventually want to match multiple instructions with a register-use in common and merge them together and this can't be represented by nesting dags in tablegen. For example, this could be used to match two load-words of the form:

(set s32_GPR:$dst1, (G_LOAD p0_GPR:$addr))
(set s32_GPR:$dst2, (G_LOAD (G_ADD p0_GPR:$addr, 4)))

and (subject to other predicates) merge them into a load-word-multiple:

(set2 s32_GPR:$dst1, s32_GPR32:$dst2, (G_LOAD2 p0_GPR:$addr))

utils/TableGen/GlobalISelEmitter.cpp

100

This is a nitpick but I think we should keep Matchers and Actions in separate class hierarchies for type checking purposes. They don't share much implementation and it doesn't make sense to put MatchOpcode in Matcher::Actions or MutateOpcode in Matcher::Matchers

123

We don't use the MVT directly. Would it be better to store the LLT and convert in the caller?

[ab]

• Split 'MatcherAction's from 'Matcher's
• Remove Widenable logic
• Add RegBank checking (asks RBI for the bank covering a class to check that the operand is in that bank; we'll update that once D27338 lands)

[ab]

In D26878#613434, @dsanders wrote:

From https://reviews.llvm.org/differential/diff/78609/:

/// Is this generic instruction "widenable", i.e., is this transform valid:
///   (G_ZEXT (op s8 a, b)) -> (op s32 (G_ZEXT a), (G_ZEXT b))

This transform isn't strictly valid and will produce the wrong result on overflow but that's often ok because LLVM-IR doesn't define the excess bits and there will be explicit extends for when it really matters. However, some targets like Mips do care what those bits are and may misbehave if the excess bits are wrong. Here's a few examples:

• 'addu' where one of the operands is 0x00000001_00000000 produces an unpredictable result on Mips64.
• 'addu' where one of the operands is 0x00000000_80000000 produces an unpredictable result on Mips64.
• 'addu' and 'daddu' will behave differently when given 0x80000000 and 0x80000000 with the former producing 0x0 and the latter producing 0x1_00000000.
• 'addu' and 'daddu' will behave differently when given 0x40000000 and 0x40000000 with the former producing 0xffffffff_80000000 and the latter producing 0x00000000_80000000.

That's interesting.. I'm guessing that means that *all* operations that produce a 32-bit result sign-extend it? (usually/always implicitly, as I see 'addu' does?)
How is that expressed in the current backend? Are operations that map to non-sign-extending instructions (if there are any?) explicitly legalized?

I don't think 'Widenable' is necessarily a problem: whether the selector decides to implicitly widen is only an isel decision: the operation still has to be marked legal in the first place. I think the core problem is that 'Widenable', as implemented in the original patch, introduces ambiguity in the selector. If we ensure that we only implicitly widen if there is no narrower legal alternative (so, on MIPS64, widen s8 to s32, and s48 to s64, but not s32 to s64), we should guarantee that the selector respects the legalizer's decision.

To be clear: the original patch is incomplete in that regard: it will happily select an s32 G_ADD to s64. Fixing that will require evaluating all patterns before emitting them. I'll think about it some more and create another thread for that. It's not obvious we can make it robust (what do we do if there's a legal s32 ADD requiring some predicate?) For now, let's remove the widening from this.

We can also remove the concept entirely, and go back to explicitly legalizing. After all, it is a compile-/run-time optimization!

The Widenable flag will eventually need to be controllable so that we can say that i1-i63 are widenable except for i32.

That's an option, but I'd rather not go down that road ;)

Another one that's likely to be surprising is that ISD::TRUNCATE isn't a nop on Mips. It's a sign-extend for i32 (and technically for also i64 but that has no impact at the moment) and a zero extend for other sizes.

Hmm, how is that represented in SelectionDAG? Aren't there combines that will try to fold away (aext (trunc x)) or (trunc (zext x)) ? Wouldn't avoid them require ISD::TRUNCATE be legalized?

invent a new syntax, convert older patterns (at checkin- or build-time): I don't think we're at a stage where we can make
well-informed decisions about the eventual tablegen design. I'm hoping that, as we add support for SDAG constructs, we
get more insight on what we'll eventually need. For now, emitting matchers from SDAG patterns is a small incremental
step.

My current knowledge of GlobalISel is largely based on reading the code rather than writing it but FWIW I've been sketching a rough tablegen design as I've been catching up on GlobalISel and the sketch is broadly in line with this patch.

One thing I'd like to mention is that the current patch has what I'd call rule-level matching (Matcher), and instruction-property-level matching (MatchOpcode/MatchRegOpType/MatchMBBOp). I think we should have a level in between those two which represents an instruction without testing any properties of that instruction. It's probably best to think of it as a cursor position for the match.

Absolutely! Unless you had something else in mind, I suspect we'll need something like that even for simple patterns with nested instructions, like this part of your example:

(set s32_GPR:$dst2, (G_LOAD (G_ADD p0_GPR:$addr, 4)))

That alone will require additional context. For now, I'd rather stick to the absolute simplest starting point.

utils/TableGen/GlobalISelEmitter.cpp

100

Fair enough; split it into 'Matcher' and 'MatchAction', and renamed 'Matcher' to 'MatcherEmitter'. Better names welcome ;)

123

You're right, MVT doesn't really belong here, but the string is quite wasteful. Ideally, we'd use LLT itself (or fake it here), but that would have to move to libSupport, which seems gross.

Anyway, switched to a std::string LLT.

[dsanders]

In D26878#621671, @ab wrote:

In D26878#613434, @dsanders wrote:

From https://reviews.llvm.org/differential/diff/78609/:

/// Is this generic instruction "widenable", i.e., is this transform valid:
///   (G_ZEXT (op s8 a, b)) -> (op s32 (G_ZEXT a), (G_ZEXT b))

This transform isn't strictly valid and will produce the wrong result on overflow but that's often ok because LLVM-IR doesn't define the excess bits and there will be explicit extends for when it really matters. However, some targets like Mips do care what those bits are and may misbehave if the excess bits are wrong. Here's a few examples:

• 'addu' where one of the operands is 0x00000001_00000000 produces an unpredictable result on Mips64.
• 'addu' where one of the operands is 0x00000000_80000000 produces an unpredictable result on Mips64.
• 'addu' and 'daddu' will behave differently when given 0x80000000 and 0x80000000 with the former producing 0x0 and the latter producing 0x1_00000000.
• 'addu' and 'daddu' will behave differently when given 0x40000000 and 0x40000000 with the former producing 0xffffffff_80000000 and the latter producing 0x00000000_80000000.

That's interesting.. I'm guessing that means that *all* operations that produce a 32-bit result sign-extend it? (usually/always implicitly, as I see 'addu' does?)

Not quite, Mips has some 32-bit zero-extending operations on MIPS64. It's easier to explain the strategy that causes this quirk and work back from there.

The forwards compatibility strategy that the Mips ISA follows views the registers as being infinite-width. Particular versions of the ISA such as MIPS32 choose to implement a certain physical register width and all operations will notionally sign-extend that register-width to infinite-width. When a wider version of the ISA is invented, those notional sign-extensions become real sign-extensions to the new register-width (and notionally beyond to infinite-width). So far that's consistent with your guess, but the wider ISA also adds zero-extending versions of the operations on the previous register-width where it's useful (e.g. 32x32->64-bit unsigned multiplies on MIPS64).

How is that expressed in the current backend?

There are a couple calling convention legalizations (e.g. to make 'unsigned int' use ISD::ASSERT_SEXT) but it's mostly implicit. Mips just defines the bits that the DAG leaves undefined and people who work on Mips have to be careful not to break the consistency.

Are operations that map to non-sign-extending instructions (if there are any?) explicitly legalized?

There aren't any non-sign-extending instructions for register-width operations and the instruction selection picks the sign-extending instruction when working on register-width values regardless of the signedness of the operation.

I don't think 'Widenable' is necessarily a problem: whether the selector decides to implicitly widen is only an isel decision: the operation still has to be marked legal in the first place. I think the core problem is that 'Widenable', as implemented in the original patch, introduces ambiguity in the selector. If we ensure that we only implicitly widen if there is no narrower legal alternative (so, on MIPS64, widen s8 to s32, and s48 to s64, but not s32 to s64), we should guarantee that the selector respects the legalizer's decision.

Both parts of that sound right to me. I expect most targets will be able to defer widening but Mips will need to do it in the legalizer.

To be clear: the original patch is incomplete in that regard: it will happily select an s32 G_ADD to s64. Fixing that will require evaluating all patterns before emitting them. I'll think about it some more and create another thread for that. It's not obvious we can make it robust (what do we do if there's a legal s32 ADD requiring some predicate?) For now, let's remove the widening from this.

We can also remove the concept entirely, and go back to explicitly legalizing. After all, it is a compile-/run-time optimization!

The Widenable flag will eventually need to be controllable so that we can say that i1-i63 are widenable except for i32.

That's an option, but I'd rather not go down that road ;)

Another one that's likely to be surprising is that ISD::TRUNCATE isn't a nop on Mips. It's a sign-extend for i32 (and technically for also i64 but that has no impact at the moment) and a zero extend for other sizes.

Hmm, how is that represented in SelectionDAG? Aren't there combines that will try to fold away (aext (trunc x)) or (trunc (zext x)) ? Wouldn't avoid them require ISD::TRUNCATE be legalized?

It's just a normal ISD::TRUNCATE node without special legalization. There's a special-case instruction selection to emit a sign-extend for the 32-bit case and some folds to handle ISD::ASSERT_SEXT and similar.

Both of those examples are cases where SelectionDAG leaves the bits undefined and Mips defines them to be a sign-extension. In the first one, any extend is an extension using undefined bits so (aext (trunc x)) is equivalent to (trunc x) in terms of register value. Similarly, truncation leaves the truncated bits undefined. They'd normally retain their previous value but Mips changes them to a sign-extension.

invent a new syntax, convert older patterns (at checkin- or build-time): I don't think we're at a stage where we can make
well-informed decisions about the eventual tablegen design. I'm hoping that, as we add support for SDAG constructs, we
get more insight on what we'll eventually need. For now, emitting matchers from SDAG patterns is a small incremental
step.

My current knowledge of GlobalISel is largely based on reading the code rather than writing it but FWIW I've been sketching a rough tablegen design as I've been catching up on GlobalISel and the sketch is broadly in line with this patch.

One thing I'd like to mention is that the current patch has what I'd call rule-level matching (Matcher), and instruction-property-level matching (MatchOpcode/MatchRegOpType/MatchMBBOp). I think we should have a level in between those two which represents an instruction without testing any properties of that instruction. It's probably best to think of it as a cursor position for the match.

Absolutely! Unless you had something else in mind, I suspect we'll need something like that even for simple patterns with nested instructions, like this part of your example:

(set s32_GPR:$dst2, (G_LOAD (G_ADD p0_GPR:$addr, 4)))

That alone will require additional context. For now, I'd rather stick to the absolute simplest starting point.

That's a good point and it nicely unifies the nested match description with the multiple-roots one. The only difference between them is how the match position is found which is a task for the algorithm rather than the description.

[qcolombet]

Hi Ahmed,

Looks good to me.

Nitpicks below.

Cheers,
-Quentin

include/llvm/Target/TargetGlobalISel.td

22

Nitpick: Just a personal thing, but given the argument are i then node, I would have expected I then Node.

23

Just a forward looking thought. Do you think that we would need to support 1 to many patterns?
E.g., what will be the strategy for BUILD_VECTOR and the kind?

I am starting to think that we are defining patterns, just target independent ones.

lib/Target/AArch64/AArch64InstructionSelector.h

35

Could you document how that selectImpl is different from select and how they interact between each other?

utils/TableGen/GlobalISelEmitter.cpp

10

/// Doxygen style?

16

There is a word missing "[...] their GlobalISel _counterpart_".

16

I would add comment explaining how to get the list of patterns that are not supported and interpret why they are not supported.

76

What does it mean for the consumer of that function to have an invalid LLT?

Put differently, how can we get an invalid LLT? I would expect LLT to be a strict superset of MVT.

94

Shouldn't we rule out the patterns with physical registers as well?
Indeed, unless I am mistaken, we don't have emitter to add the implicit def/use for those operands.

308

bog?

[zvi]

Hi Ahmed, thanks for doing this work. I don't have much mileage in GlobalISel, but FWIW, this patch LGTM.

utils/TableGen/GlobalISelEmitter.cpp

340

Minor: make MRI be a const reference?

344

To the best of my knowledge there is no CodeGenDAGPatterns::ptms().

[dsanders]

include/llvm/Target/TargetGlobalISel.td

23

We haven't used it yet so I can't be sure but G_SEQUENCE seems like the gMIR equivalent of BUILD_VECTOR. Is that right?

utils/TableGen/GlobalISelEmitter.cpp

100

For 'Matcher', could you elaborate that it's matching properties of an operand (OperandPropertyMatcher?). That way we won't have to rename it when we add additional levels of matching. For example, I've added an InstructionMatcher in my current WIP and I suspect I'll find an OperandMatcher useful now that we can have multiple matchers on a single operand.

[qcolombet]

include/llvm/Target/TargetGlobalISel.td

23

Yep, that's a poor example. SEXTLOAD is probably a better one.

[ab]

Thanks for the reviews, all!

include/llvm/Target/TargetGlobalISel.td

23

Eventually we'll need to support many-to-1 or 1-to-many patterns (as Daniel mentioned), but those should still map, at their core, nodes to instructions. When we get to the point where we need to map one SDNode to multiple instructions (or the opposite), it will probably be time to switch to a first-class GISel representation! (and it's always possible to introduce new pseudo instructions to replace the target-specific ISD opcodes.)

utils/TableGen/GlobalISelEmitter.cpp

76

LLT alone isn't always compatible with MVT: things like iPTR require a DataLayout; the various 'iAny' types need extra logic, and then there are types that just don't have LLT equivalents (e.g., glue, or x86mmx today).

Added an explanation.

94

Good point; physregs that are "set" would be rejected when we look for RegisterClasses, but "implicit" defs are still a possibility.

100

What about opcode matching though? Are you thinking of a hierarchy of specialized Matchers ? I can see it being useful, but I wouldn't worry about renaming everything once we get there ;)

344

Good eye, separate commit in my local branch! I trimmed and squashed it when committing though, I didn't end up needing all the iterators and ranges I added.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

100

Yes, I'm planning to have a hierarchy of matchers where MatchOpcode will be an instruction matcher and will contain the others (with an extra layer in between).

I'm thinking of having the following kinds of matchers:

• Instruction: An instruction matcher to match opcodes will be the main one but this is also where I'm thinking of handling the GlobalISel equivalent of ComplexPattern.
• Instruction Property: Fastmath, nuw/nsw, volatile, etc. I've separated this from instruction matchers to prevent combinatorial explosion in the instruction matchers.
• Operand: Matching a single operand by index will be the main one but I'm thinking it will also includes sequences to support variadic instructions.
• Operand Property: Types, register banks, constants, etc. but will also contain sub-instruction matchers such as:
  • Operand must be def'd by the same instruction as another (for tied-registers, special-case simplifications, etc.)
  • Operand must be def'd by an instruction matching a given instruction matcher and the two must be safely foldable (for multi-instruction patterns)

include/llvm/Target/Target.td

 // Pull in the common support for calling conventions.
 //
 include "llvm/Target/TargetCallingConv.td"
 
 //===----------------------------------------------------------------------===//
 // Pull in the common support for DAG isel generation.
 //
 include "llvm/Target/TargetSelectionDAG.td"
+
+//===----------------------------------------------------------------------===//
+// Pull in the common support for Global ISel generation.
+//
+include "llvm/Target/TargetGlobalISel.td"

include/llvm/Target/TargetGlobalISel.td

+//===- TargetGlobalISel.td - Common code for GlobalISel ----*- tablegen -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the target-independent interfaces used to support
+// SelectionDAG instruction selection patterns (specified in
+// TargetSelectionDAG.td) when generating GlobalISel instruction selectors.
+//
+// This is intended as a compatibility layer, to enable reuse of target
+// descriptions written for SelectionDAG without requiring explicit GlobalISel
+// support.  It will eventually supersede SelectionDAG patterns.
+//
+//===----------------------------------------------------------------------===//
+
+class GINodeEquiv<Instruction i, SDNode node> {
+  SDNode Node = node;
+  Instruction I = i;
+}
+
+def : GINodeEquiv<G_ADD, add>;
+def : GINodeEquiv<G_BR, br>;

lib/Target/AArch64/AArch64InstructionSelector.h

 public:
   AArch64InstructionSelector(const AArch64TargetMachine &TM,
                              const AArch64Subtarget &STI,
                              const AArch64RegisterBankInfo &RBI);
 
   virtual bool select(MachineInstr &I) const override;
 
 private:
+  bool selectImpl(MachineInstr &I) const;
+
   const AArch64TargetMachine &TM;
   const AArch64Subtarget &STI;
   const AArch64InstrInfo &TII;
   const AArch64RegisterInfo &TRI;
   const AArch64RegisterBankInfo &RBI;
 };
 
 } // End llvm namespace.
 #endif

lib/Target/AArch64/AArch64InstructionSelector.cpp

 #define DEBUG_TYPE "aarch64-isel"
 
 using namespace llvm;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
+#include "AArch64GenGlobalISel.inc"
+
 AArch64InstructionSelector::AArch64InstructionSelector(
     const AArch64TargetMachine &TM, const AArch64Subtarget &STI,
     const AArch64RegisterBankInfo &RBI)
   : InstructionSelector(), TM(TM), STI(STI), TII(*STI.getInstrInfo()),
       TRI(*STI.getRegisterInfo()), RBI(RBI) {}
 
 // FIXME: This should be target-independent, inferred from the types declared
 // for each class in the bank.
if (OpSize <= 32) {
       switch (GenericOpc) {
       case TargetOpcode::G_OR:
         return AArch64::ORRWrr;
       case TargetOpcode::G_XOR:
         return AArch64::EORWrr;
       case TargetOpcode::G_AND:
         return AArch64::ANDWrr;
       case TargetOpcode::G_ADD:
+        assert(OpSize != 32 && "s32 G_ADD should have been selected");
         return AArch64::ADDWrr;
       case TargetOpcode::G_SUB:
         return AArch64::SUBWrr;
       case TargetOpcode::G_SHL:
         return AArch64::LSLVWr;
       case TargetOpcode::G_LSHR:
         return AArch64::LSRVWr;
       case TargetOpcode::G_ASHR:
         return AArch64::ASRVWr;
       case TargetOpcode::G_SDIV:
         return AArch64::SDIVWr;
       case TargetOpcode::G_UDIV:
         return AArch64::UDIVWr;
       default:
         return GenericOpc;
       }
     } else if (OpSize == 64) {
       switch (GenericOpc) {
       case TargetOpcode::G_OR:
         return AArch64::ORRXrr;
       case TargetOpcode::G_XOR:
         return AArch64::EORXrr;
       case TargetOpcode::G_AND:
         return AArch64::ANDXrr;
-      case TargetOpcode::G_ADD:
       case TargetOpcode::G_GEP:
         return AArch64::ADDXrr;
       case TargetOpcode::G_SUB:
         return AArch64::SUBXrr;
       case TargetOpcode::G_SHL:
         return AArch64::LSLVXr;
       case TargetOpcode::G_LSHR:
         return AArch64::LSRVXr;
bool AArch64InstructionSelector::select(MachineInstr &I) const {
   }
 
 
   if (I.getNumOperands() != I.getNumExplicitOperands()) {
     DEBUG(dbgs() << "Generic instruction has unexpected implicit operands\n");
     return false;
   }
 
+  if (selectImpl(I))
+    return true;
+
   LLT Ty =
       I.getOperand(0).isReg() ? MRI.getType(I.getOperand(0).getReg()) : LLT{};
 
   switch (Opcode) {
-  case TargetOpcode::G_BR: {
-    I.setDesc(TII.get(AArch64::B));
-    return true;
-  }
-
   case TargetOpcode::G_BRCOND: {
     if (Ty.getSizeInBits() > 32) {
       // We shouldn't need this on AArch64, but it would be implemented as an
       // EXTRACT_SUBREG followed by a TBNZW because TBNZX has no encoding if the
       // bit being tested is < 32.
       DEBUG(dbgs() << "G_BRCOND has type: " << Ty
                    << ", expected at most 32-bits");
       return false;

lib/Target/AArch64/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS AArch64.td)
 
 tablegen(LLVM AArch64GenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM AArch64GenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM AArch64GenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM AArch64GenMCPseudoLowering.inc -gen-pseudo-lowering)
 tablegen(LLVM AArch64GenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM AArch64GenAsmWriter1.inc -gen-asm-writer -asmwriternum=1)
 tablegen(LLVM AArch64GenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM AArch64GenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM AArch64GenFastISel.inc -gen-fast-isel)
 tablegen(LLVM AArch64GenCallingConv.inc -gen-callingconv)
 tablegen(LLVM AArch64GenSubtargetInfo.inc -gen-subtarget)
 tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM AArch64GenSystemOperands.inc -gen-searchable-tables)
+if(LLVM_BUILD_GLOBAL_ISEL)
+  tablegen(LLVM AArch64GenGlobalISel.inc -gen-global-isel)
+endif()
 
 add_public_tablegen_target(AArch64CommonTableGen)
 
 # List of all GlobalISel files.
 set(GLOBAL_ISEL_FILES
       AArch64CallLowering.cpp
       AArch64InstructionSelector.cpp
       AArch64LegalizerInfo.cpp

utils/TableGen/CMakeLists.txt

add_tablegen(llvm-tblgen LLVM
   DAGISelMatcherEmitter.cpp
   DAGISelMatcherGen.cpp
   DAGISelMatcherOpt.cpp
   DAGISelMatcher.cpp
   DFAPacketizerEmitter.cpp
   DisassemblerEmitter.cpp
   FastISelEmitter.cpp
   FixedLenDecoderEmitter.cpp
+  GlobalISelEmitter.cpp
   InstrInfoEmitter.cpp
   IntrinsicEmitter.cpp
   OptParserEmitter.cpp
   PseudoLoweringEmitter.cpp
   RegisterInfoEmitter.cpp
   SearchableTableEmitter.cpp
   SubtargetEmitter.cpp
   SubtargetFeatureInfo.cpp
   TableGen.cpp
   Types.cpp
   X86DisassemblerTables.cpp
   X86ModRMFilters.cpp
   X86RecognizableInstr.cpp
   CTagsEmitter.cpp
   )

utils/TableGen/GlobalISelEmitter.cpp

+//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This tablegen backend emits code for use by the GlobalISel instruction
+// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
+//
+// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
+// backend, filters out the ones that are unsupported, maps
+// SelectionDAG-specific constructs to their GlobalISel (when applicable: MVT
+// to LLT;  SDNode to generic Instruction).
+//
+//===----------------------------------------------------------------------===//
+
+#include "CodeGenDAGPatterns.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineValueType.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenBackend.h"
+#include <string>
+using namespace llvm;
+
+#define DEBUG_TYPE "gisel-emitter"
+
+STATISTIC(NumPatternTotal, "Total number of patterns");
+STATISTIC(NumPatternSkipped, "Number of patterns skipped");
+STATISTIC(NumPatternEmitted, "Number of patterns emitted");
+
+static cl::opt<bool> WarnOnSkippedPatterns(
+    "warn-on-skipped-patterns",
+    cl::desc("Explain why a pattern was skipped for inclusion "
+             "in the GlobalISel selector"),
+    cl::init(false));
+
+namespace {
+
+class GlobalISelEmitter {
+public:
+  explicit GlobalISelEmitter(RecordKeeper &RK);
+  void run(raw_ostream &OS);
+
+private:
+  const RecordKeeper &RK;
+  const CodeGenDAGPatterns CGP;
+  const CodeGenTarget &Target;
+
+  /// Keep track of the equivalence between SDNodes and Instruction.
+  /// This is defined using 'GINodeEquiv' in the target description.
+  DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
+
+  void gatherNodeEquivs();
+  const CodeGenInstruction *findNodeEquiv(Record *N);
+
+  struct SkipReason {
+    std::string Reason;
+  };
+
+  /// Analyze pattern \p P, possibly emitting matching code for it to \p OS.
+  /// Otherwise, return a reason why this pattern was skipped for emission.
+  Optional<SkipReason> runOnPattern(const PatternToMatch &P,
+                                    raw_ostream &OS);
+};
+
+} // end anonymous namespace
+
+//===- Helper functions ---------------------------------------------------===//
+
+/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT().
+static std::string MVTToLLT(MVT::SimpleValueType SVT) {
+  std::string TyStr;
+  raw_string_ostream OS(TyStr);
+  MVT VT(SVT);
+  if (VT.isVector() && VT.getVectorNumElements() != 1) {
+    OS << "LLT::vector(" << VT.getVectorNumElements() << ", "
+       << VT.getScalarSizeInBits() << ")";
+  } else if (VT.isInteger() || VT.isFloatingPoint()) {
+    OS << "LLT::scalar(" << VT.getSizeInBits() << ")";
+  } else {
+    OS << "LLT()";
+  }
+  OS.flush();
+  return TyStr;
+}
+
+static bool isTrivialOperatorNode(const TreePatternNode *N) {
+  return !N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn();
+}
+
+//===- Matchers -----------------------------------------------------------===//
+
+struct Matcher {
+  virtual ~Matcher() {}
+  virtual void emit(raw_ostream &OS) const = 0;
+};
+
+raw_ostream &operator<<(raw_ostream &S, const Matcher &M) {
+  M.emit(S);
+  return S;
+}
+
+struct MatchAction {
+  virtual ~MatchAction() {}
+  virtual void emit(raw_ostream &OS) const = 0;
+};
+
+raw_ostream &operator<<(raw_ostream &S, const MatchAction &A) {
+  A.emit(S);
+  return S;
+}
+
+struct MatchOpcode : public Matcher {
+  MatchOpcode(const CodeGenInstruction *I) : I(I) {}
+  const CodeGenInstruction *I;
+
+  virtual void emit(raw_ostream &OS) const {
+    OS << "I.getOpcode() == " << I->Namespace << "::" << I->TheDef->getName();
+  }
+};
+
+struct MatchRegOpType : public Matcher {
+  MatchRegOpType(unsigned OpIdx, std::string Ty)
+      : OpIdx(OpIdx), Ty(Ty) {}
+  unsigned OpIdx;
+  std::string Ty;
+
+  virtual void emit(raw_ostream &OS) const {
+    OS << "MRI.getType(I.getOperand(" << OpIdx << ").getReg()) == (" << Ty
+       << ")";
+  }
+};
+
+struct MatchRegOpBank : public Matcher {
+  MatchRegOpBank(unsigned OpIdx, const CodeGenRegisterClass &RC)
+      : OpIdx(OpIdx), RC(RC) {}
+  unsigned OpIdx;
+  const CodeGenRegisterClass &RC;
+
+  virtual void emit(raw_ostream &OS) const {
+    OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
+       << "RegClass) == RBI.getRegBank(I.getOperand(" << OpIdx
+       << ").getReg(), MRI, TRI))";
+  }
+};
+
+struct MatchMBBOp : public Matcher {
+  MatchMBBOp(unsigned OpIdx) : OpIdx(OpIdx) {}
+  unsigned OpIdx;
+
+  virtual void emit(raw_ostream &OS) const {
+    OS << "I.getOperand(" << OpIdx << ").isMBB()";
+  }
+};
+
+struct MutateOpcode : public MatchAction {
+  MutateOpcode(const CodeGenInstruction *I) : I(I) {}
+  const CodeGenInstruction *I;
+
+  virtual void emit(raw_ostream &OS) const {
+    OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
+       << "));";
+  }
+};
+
+class MatcherEmitter {
+  const PatternToMatch &P;
+
+public:
+  std::vector<std::unique_ptr<Matcher>> Matchers;
+  std::vector<std::unique_ptr<MatchAction>> Actions;
+
+  MatcherEmitter(const PatternToMatch &P) : P(P) {}
+
+  void emit(raw_ostream &OS) {
+    if (Matchers.empty())
+      llvm_unreachable("Unexpected empty matcher!");
+
+    OS << "  // Src: " << *P.getSrcPattern() << "\n"
+       << "  // Dst: " << *P.getDstPattern() << "\n";
+
+    OS << "  if ((" << *Matchers.front() << ")";
+    for (auto &MA : makeArrayRef(Matchers).drop_front())
+      OS << " &&\n      (" << *MA << ")";
+    OS << ") {\n";
+
+    for (auto &MA : Actions)
+      OS << "    " << *MA << "\n";
+
+    OS << "    constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";
+    OS << "    return true;\n";
+    OS << "  }\n";
+  }
+};
+
+//===- GlobalISelEmitter class --------------------------------------------===//
+
+void GlobalISelEmitter::gatherNodeEquivs() {
+  assert(NodeEquivs.empty());
+  for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
+    NodeEquivs[Equiv->getValueAsDef("Node")] =
+        &Target.getInstruction(Equiv->getValueAsDef("I"));
+}
+
+const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) {
+  return NodeEquivs.lookup(N);
+}
+
+GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
+    : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
+
+//===- Emitter ------------------------------------------------------------===//
+
+Optional<GlobalISelEmitter::SkipReason>
+GlobalISelEmitter::runOnPattern(const PatternToMatch &P, raw_ostream &OS) {
+
+  // Keep track of the matchers and actions to emit.
+  MatcherEmitter M(P);
+
+  // First, analyze the whole pattern.
+  // If the entire pattern has a predicate (e.g., target features), ignore it.
+  if (!P.getPredicates()->getValues().empty())
+    return SkipReason{"Pattern has a predicate"};
+
+  // Next, analyze the pattern operators.
+  TreePatternNode *Src = P.getSrcPattern();
+  TreePatternNode *Dst = P.getDstPattern();
+
+  // If the root of either pattern isn't a simple operator, ignore it.
+  if (!isTrivialOperatorNode(Dst))
+    return SkipReason{"Dst pattern root isn't a trivial operator"};
+  if (!isTrivialOperatorNode(Src))
+    return SkipReason{"Src pattern root isn't a trivial operator"};
+
+  Record *DstOp = Dst->getOperator();
+  if (!DstOp->isSubClassOf("Instruction"))
+    return SkipReason{"Pattern operator isn't an instruction"};
+
+  auto &DstI = Target.getInstruction(DstOp);
+
+  auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
+  if (!SrcGIOrNull)
+    return SkipReason{"Pattern operator lacks an equivalent Instruction"};
+  auto &SrcGI = *SrcGIOrNull;
+
+  // The operators look good: match the opcode and mutate it to the new one.
+  M.Matchers.emplace_back(new MatchOpcode(&SrcGI));
+  M.Actions.emplace_back(new MutateOpcode(&DstI));
+
+  // Next, analyze the children, only accepting patterns that don't require
+  // any change to operands.
+  if (Src->getNumChildren() != Dst->getNumChildren())
+    return SkipReason{"Src/dst patterns have a different # of children"};
+
+  unsigned OpIdx = 0;
+
+  // Start with the defined operands (i.e., the results of the root operator).
+  if (DstI.Operands.NumDefs != Src->getExtTypes().size())
+    return SkipReason{"Src pattern results and dst MI defs are different"};
+
+  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
+    Record *DstIOpRec = DstI.Operands[OpIdx].Rec;
+    if (!DstIOpRec->isSubClassOf("RegisterClass"))
+      return SkipReason{"Dst MI def isn't a register class"};
+
+    M.Matchers.emplace_back(
+        new MatchRegOpType(OpIdx, MVTToLLT(Ty.getConcrete())));
+    M.Matchers.emplace_back(
+        new MatchRegOpBank(OpIdx, Target.getRegisterClass(DstIOpRec)));
+    ++OpIdx;
+  }
+
+  // Finally match the used operands (i.e., the children of the root operator).
+  for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
+    auto *SrcChild = Src->getChild(i);
+    auto *DstChild = Dst->getChild(i);
+
+    // Patterns can reorder operands.  Ignore those for now.
+    if (SrcChild->getName() != DstChild->getName())
+      return SkipReason{"Src/dst pattern children not in same order"};
+
+    // The only non-leaf child we accept is 'bb': it's an operator because
+    // BasicBlockSDNode isn't inline, but in MI it's just another operand.
+    if (!SrcChild->isLeaf()) {
+      if (DstChild->isLeaf() ||
+          SrcChild->getOperator() != DstChild->getOperator())
+        return SkipReason{"Src/dst pattern child operator mismatch"};
+
+      if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
+        auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
+        if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
+          M.Matchers.emplace_back(new MatchMBBOp(OpIdx++));
+          continue;
+        }
+      }
+      return SkipReason{"Src pattern child isn't a leaf node"};
+    }
+
+    if (SrcChild->getLeafValue() != DstChild->getLeafValue())
+      return SkipReason{"Src/dst pattern child leaf mismatch"};
+
+    // Otherwise, we're looking for a bog-standard RegisterClass operand.
+    if (SrcChild->hasAnyPredicate())
+      return SkipReason{"Src pattern child has predicate"};
+    auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef();
+    if (!ChildRec->isSubClassOf("RegisterClass"))
+      return SkipReason{"Src pattern child isn't a RegisterClass"};
+
+    ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
+    if (ChildTypes.size() != 1)
+      return SkipReason{"Src pattern child has multiple results"};
+
+    M.Matchers.emplace_back(
+        new MatchRegOpType(OpIdx, MVTToLLT(ChildTypes.front().getConcrete())));
+    M.Matchers.emplace_back(
+        new MatchRegOpBank(OpIdx, Target.getRegisterClass(ChildRec)));
+    ++OpIdx;
+  }
+
+  // We're done with this pattern!  Emit the processed result.
+  M.emit(OS);
+  ++NumPatternEmitted;
+  return None;
+}
+
+void GlobalISelEmitter::run(raw_ostream &OS) {
+  // Track the GINodeEquiv definitions.
+  gatherNodeEquivs();
+
+  emitSourceFileHeader(("Global Instruction Selector for the " +
+                       Target.getName() + " target").str(), OS);
+  OS << "bool " << Target.getName()
+     << "InstructionSelector::selectImpl"
+        "(MachineInstr &I) const {\n  MachineRegisterInfo &MRI = "
+        "I.getParent()->getParent()->getRegInfo();\n";
+
+  // Look through the SelectionDAG patterns we found, possibly emitting some.
+  for (const PatternToMatch &Pat : CGP.ptms()) {
+    ++NumPatternTotal;
+    if (auto SkipReason = runOnPattern(Pat, OS)) {
+      if (WarnOnSkippedPatterns) {
+        PrintWarning(Pat.getSrcRecord()->getLoc(),
+                     "Skipped pattern: " + SkipReason->Reason);
+      }
+      ++NumPatternSkipped;
+    }
+  }
+
+  OS << "  return false;\n}\n";
+}
+
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
+  GlobalISelEmitter(RK).run(OS);
+}
+} // End llvm namespace

utils/TableGen/TableGen.cpp

enum ActionType {
   GenIntrinsic,
   GenTgtIntrinsic,
   PrintEnums,
   PrintSets,
   GenOptParserDefs,
   GenCTags,
   GenAttributes,
   GenSearchableTables,
+  GenGlobalISel,
 };
 
 namespace {
   cl::opt<ActionType>
   Action(cl::desc("Action to perform:"),
          cl::values(clEnumValN(PrintRecords, "print-records",
                                "Print all records to stdout (default)"),
                     clEnumValN(GenEmitter, "gen-emitter",
Action(cl::desc("Action to perform:"),
                                "Print expanded sets for testing DAG exprs"),
                     clEnumValN(GenOptParserDefs, "gen-opt-parser-defs",
                                "Generate option definitions"),
                     clEnumValN(GenCTags, "gen-ctags",
                                "Generate ctags-compatible index"),
                     clEnumValN(GenAttributes, "gen-attrs",
                                "Generate attributes"),
                     clEnumValN(GenSearchableTables, "gen-searchable-tables",
-                               "Generate generic binary-searchable table")));
+                               "Generate generic binary-searchable table"),
+                    clEnumValN(GenGlobalISel, "gen-global-isel",
+                               "Generate GlobalISel selector")));
 
   cl::opt<std::string>
   Class("class", cl::desc("Print Enum list for this class"),
           cl::value_desc("class name"));
 
 bool LLVMTableGenMain(raw_ostream &OS, RecordKeeper &Records) {
   switch (Action) {
   case PrintRecords:
case GenCTags:
     EmitCTags(Records, OS);
     break;
   case GenAttributes:
     EmitAttributes(Records, OS);
     break;
   case GenSearchableTables:
     EmitSearchableTables(Records, OS);
     break;
+  case GenGlobalISel:
+    EmitGlobalISel(Records, OS);
+    break;
   }
 
   return false;
 }
 }
 
 int main(int argc, char **argv) {
   sys::PrintStackTraceOnErrorSignal(argv[0]);

utils/TableGen/TableGenBackends.h

 void EmitPseudoLowering(RecordKeeper &RK, raw_ostream &OS);
 void EmitRegisterInfo(RecordKeeper &RK, raw_ostream &OS);
 void EmitSubtarget(RecordKeeper &RK, raw_ostream &OS);
 void EmitMapTable(RecordKeeper &RK, raw_ostream &OS);
 void EmitOptParser(RecordKeeper &RK, raw_ostream &OS);
 void EmitCTags(RecordKeeper &RK, raw_ostream &OS);
 void EmitAttributes(RecordKeeper &RK, raw_ostream &OS);
 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS);
+void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS);
 
 } // End llvm namespace
 
 #endif