[RFC v2] "Alternative" matches for TableGen DAG patterns

[uweigand]

Summary

This is an alternative approach to implement the same goal as described here:
https://reviews.llvm.org/D48326
See the summary of that patch for more information.

The difference of this approach is that instead of using a new keyword ("alternative"), we rather extend the PatFrag class to allow specifying multiple alternative match patterns -- this approach was suggested by Krzysztof in comments to D48326.

As an example, the z_sadd fragment mentioned in D48326 would instead be written as follows:

def z_sadd : PatFrags<(ops node:$src1, node:$src2),
                      [(z_saddo node:$src1, node:$src2),
                       (add node:$src1, node:$src2)]>;

Implementation-wise, the major difference is that instead of expanding "alternative" nodes in a separate pass over the PatternsToMatch vector after instruction/pattern parsing was completed, we now directly expand multiple alternatives when inlining pattern fragments. That is, the InlinePatterFragments routine no longer performs an in-place update of one single pattern, but instead maps one input pattern to a set of output patterns.

However, a number of other implementation differences follow from that. This mostly results from the fact that there doesn't seem to be a good way to handle multiple alternatives for the "set" nodes in the main instruction pattern. The approach in D48326 would continue to fully inline pattern fragments before parsing main instructions patterns -- this would inline the "alternative" nodes, but still retain a single "set" node. Instead, with the new approach we now defer inlining pattern fragments until after the initial parsing of the instruction pattern, and only inline fragments on the resulting "PatternToMatch". However, this doesn't fully work, since before inlining we may no longer recognize all input/output nodes; therefore, FindPatternInputsAndOutputs will now do a partial inlining just on named nodes (that serve as inputs) and set destination nodes (that serve as outputs). Since type resolution only works after pattern inlining, this is likewise defered. As an effect, parsing of the DAG pattern now shares a lot more code between the Instruction and the Pattern case, which should be a good thing in any case ...

As a follow-on, we also need to update the two other places that currently still refer to the full instruction pattern (including the "set" and "implicit" nodes): these are InferFromPattern and EmitResultInstructionAsOperand. The former currently infers flags separately from Instruction and Pattern nodes; now it just uses the PatternToMatch list, which contains both. This required rewriting the way the "isBitcast" flag is inferred. The latter uses the instruction pattern to search for SDNPHasChain property flags. This is now moved to InferFromPattern as well (since it basically is the same operation).

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

For now, this patch should be NFC for all targets:

• for SystemZ I've verified that identical machine code is generated
• for all other targets except Sparc, all TableGen generated files are identical, so machine code must be identical too
• for Sparc, the TableGen generated file does change, because we're now running more type inference logic on Instruction patterns (which we used to run only on Pattern patterns), which allows TableGen to infer that the "iPTR:$dst" operand of LEAX_ADDri must actually have type i64. Since the pattern is only active when generating 64-bit code, this should likewise not cause any codegen changes.

A few open questions:

1. I've renamed the PatFrag class to PatFrags, holding a "list<dag> Fragments" instead of a "dag Fragment". Does the name make sense? Or should this be called something like MultiPatFrag, or PatFragAlternatives, or ...?
2. The original PatFrag is now a subclass of PatFrags, specialized to a single fragment. This required some changes to two targets (Hexagon and NVPTX) that directly accessed implementation details of PatFrag (specifically, the "Fragment" member). Should we instead leave PatFrag as is and and a nonrelated PatFrags class? This would make the implementation in TableGen a bit wordier ...
3. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

[tra]

NVPTX changes look good. I should probably revisit that code and see if can be simplified after latest improvements in TableGen.

[kparzysz]

I haven't looked at this in detail yet, but it's looking great. Thanks for tackling this!

[uweigand]

Ping?

[hfinkel]

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

As a follow-on, we also need to update the two other places that currently still refer to the full instruction pattern (including the "set" and "implicit" nodes): these are InferFromPattern and EmitResultInstructionAsOperand. The former currently infers flags separately from Instruction and Pattern nodes; now it just uses the PatternToMatch list, which contains both. This required rewriting the way the "isBitcast" flag is inferred. The latter uses the instruction pattern to search for SDNPHasChain property flags. This is now moved to InferFromPattern as well (since it basically is the same operation).

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

1. I've renamed the PatFrag class to PatFrags, holding a "list<dag> Fragments" instead of a "dag Fragment". Does the name make sense? Or should this be called something like MultiPatFrag, or PatFragAlternatives, or ...?

I think that PatFrags is good.

2. The original PatFrag is now a subclass of PatFrags, specialized to a single fragment. This required some changes to two targets (Hexagon and NVPTX) that directly accessed implementation details of PatFrag (specifically, the "Fragment" member). Should we instead leave PatFrag as is and and a nonrelated PatFrags class? This would make the implementation in TableGen a bit wordier ...

I think that it should be logically organized as you have in the patch. After this goes in, we should make sure to update the release notes and send a "heads up" email to llvm-dev for out-of-tree targets with instructions on how to update.

3. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

utils/TableGen/CodeGenDAGPatterns.cpp

3624

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

[uweigand]

In D48545#1160649, @hfinkel wrote:

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

Thanks for the review!

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

OK, I'll work on this as a follow-up.

3. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

OK, I'll continue to allow empty Fragments. Unfortunately, getting rid of null_frag is more difficult than I expected: since current code checks for null_frag so very early, many backends get away with patterns that are actually invalid even structurally (number of results don't match number of users; use of some TableGen operators inside a pattern that aren't even dag nodes at all) as long as there's a null_frag anywhere in there as well. Trying to define a null_frag as a PatFrags with empty fragment list means that TableGen would still ignore the pattern, but only after doing a structural parse first -- which now errors out.

Now, possibly we should still do it, and clean up those backends first. But that again should be a follow-on patch.

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

First of all, note that I just copied this piece of code including its FIXME from one place to another, so my patch doesn't change anything substantive here.

The actual problem that the FIXME calls out is simply this: An original instruction can be a list including (set) statements, (implicit) statements, and plain source patterns (like e.g. stores). Now, some code is currently written as if to allow any sequence of any of these (e.g. more than one set, an implict followed by a set, etc). But other code already imposes a much more strict ordering: the first element must be either a set or a plain source pattern, and any subsequent elements must all be implicits. The code following the FIXME is one place where this more strict assumption is made.

I assume the reason for calling out a FIXME was that at some point, it was thought that this restriction was unreasonably harsh, and we should actually allow more generic sequences? But as the code stands today, I'd rather take the opposite position: we should make the restrictive assumption, because only under this assumption can we actually transform the instruction pattern into a "Pat" style pattern. (What should it even mean, exactly, to have two set nodes? ) But if this is true, then it would make more sense to fix the other pieces of code, and simply enforce the strict rules everywhere ...

[hfinkel]

In D48545#1160900, @uweigand wrote:

In D48545#1160649, @hfinkel wrote:

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

Thanks for the review!

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

OK, I'll work on this as a follow-up.

3. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

OK, I'll continue to allow empty Fragments. Unfortunately, getting rid of null_frag is more difficult than I expected: since current code checks for null_frag so very early, many backends get away with patterns that are actually invalid even structurally (number of results don't match number of users; use of some TableGen operators inside a pattern that aren't even dag nodes at all) as long as there's a null_frag anywhere in there as well. Trying to define a null_frag as a PatFrags with empty fragment list means that TableGen would still ignore the pattern, but only after doing a structural parse first -- which now errors out.

Ah, okay. That makes sense.

Now, possibly we should still do it, and clean up those backends first. But that again should be a follow-on patch.

Given the constraints, allowing empty patterns still seems potentially useful, but it might not replace null_frag. I think that's okay too. I'd consider this particular item to be low priority.

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

First of all, note that I just copied this piece of code including its FIXME from one place to another, so my patch doesn't change anything substantive here.

The actual problem that the FIXME calls out is simply this: An original instruction can be a list including (set) statements, (implicit) statements, and plain source patterns (like e.g. stores). Now, some code is currently written as if to allow any sequence of any of these (e.g. more than one set, an implict followed by a set, etc). But other code already imposes a much more strict ordering: the first element must be either a set or a plain source pattern, and any subsequent elements must all be implicits. The code following the FIXME is one place where this more strict assumption is made.

I assume the reason for calling out a FIXME was that at some point, it was thought that this restriction was unreasonably harsh, and we should actually allow more generic sequences? But as the code stands today, I'd rather take the opposite position: we should make the restrictive assumption, because only under this assumption can we actually transform the instruction pattern into a "Pat" style pattern. (What should it even mean, exactly, to have two set nodes? ) But if this is true, then it would make more sense to fix the other pieces of code, and simply enforce the strict rules everywhere ...

Thanks for explaining, and I agree. I see nothing limiting about the stricter ordering.

include/llvm/Target/TargetSelectionDAG.td

 // They can take arguments and have C++ predicates that control whether they
 // match.  They are intended to make the patterns for common instructions more
 // compact and readable.
 //
 
 /// PatFrag - Represents a pattern fragment.  This can match something on the
 /// DAG, from a single node to multiple nested other fragments.
 ///
-class PatFrag<dag ops, dag frag, code pred = [{}],
+class PatFrags<dag ops, list<dag> frags, code pred = [{}],
                SDNodeXForm xform = NOOP_SDNodeXForm> : SDPatternOperator {
   dag Operands = ops;
-  dag Fragment = frag;
+  list<dag> Fragments = frags;
   code PredicateCode = pred;
   code GISelPredicateCode = [{}];
   code ImmediateCode = [{}];
   SDNodeXForm OperandTransform = xform;
 
   // Define a few pre-packaged predicates. This helps GlobalISel import
   // existing rules from SelectionDAG for many common cases.
   // They will be tested prior to the code in pred and must not be used in
class PatFrags<dag ops, list<dag> frags, code pred = [{}],
   // cast<LoadSDNode>(N)->getMemoryVT() == MVT::<VT>;
   // cast<StoreSDNode>(N)->getMemoryVT() == MVT::<VT>;
   ValueType MemoryVT = ?;
   // cast<LoadSDNode>(N)->getMemoryVT().getScalarType() == MVT::<VT>;
   // cast<StoreSDNode>(N)->getMemoryVT().getScalarType() == MVT::<VT>;
   ValueType ScalarMemoryVT = ?;
 }
 
+// PatFrag - A version of PatFrags matching only a single fragment.
+class PatFrag<dag ops, dag frag, code pred = [{}],
+              SDNodeXForm xform = NOOP_SDNodeXForm>
+  : PatFrags<ops, [frag], pred, xform>;
+
 // OutPatFrag is a pattern fragment that is used as part of an output pattern
 // (not an input pattern). These do not have predicates or transforms, but are
 // used to avoid repeated subexpressions in output patterns.
 class OutPatFrag<dag ops, dag frag>
  : PatFrag<ops, frag, [{}], NOOP_SDNodeXForm>;
 
 // PatLeaf's are pattern fragments that have no operands.  This is just a helper
 // to define immediates and other common things concisely.

lib/Target/Hexagon/HexagonPatterns.td

 // Converters from unary/binary SDNode to PatFrag.
 class pf1<SDNode Op> : PatFrag<(ops node:$a), (Op node:$a)>;
 class pf2<SDNode Op> : PatFrag<(ops node:$a, node:$b), (Op node:$a, node:$b)>;
 
 class Not2<PatFrag P>
   : PatFrag<(ops node:$A, node:$B), (P node:$A, (not node:$B))>;
 
 class Su<PatFrag Op>
-  : PatFrag<Op.Operands, Op.Fragment, [{ return hasOneUse(N); }],
+  : PatFrag<Op.Operands, !head(Op.Fragments), [{ return hasOneUse(N); }],
             Op.OperandTransform>;
 
 // Main selection macros.
 
 class OpR_R_pat<InstHexagon MI, PatFrag Op, ValueType ResVT, PatFrag RegPred>
   : Pat<(ResVT (Op RegPred:$Rs)), (MI RegPred:$Rs)>;
 
 class OpR_RI_pat<InstHexagon MI, PatFrag Op, ValueType ResType,

 def: Pat<(i1 (setlt I32:$Rs, s32_0ImmPred:$s10)),
          (C2_not (C2_cmpgti I32:$Rs, (SDEC1 imm:$s10)))>;
 def: Pat<(i1 (setult I32:$Rs, u32_0ImmPred:$u9)),
          (C2_not (C2_cmpgtui I32:$Rs, (UDEC1 imm:$u9)))>;
 
 // Patfrag to convert the usual comparison patfrags (e.g. setlt) to ones
 // that reverse the order of the operands.
 class RevCmp<PatFrag F>
-  : PatFrag<(ops node:$rhs, node:$lhs), F.Fragment, F.PredicateCode,
+  : PatFrag<(ops node:$rhs, node:$lhs), !head(F.Fragments), F.PredicateCode,
             F.OperandTransform>;
 
 def: OpR_RR_pat<C2_cmpeq,     seteq,          i1,   I32>;
 def: OpR_RR_pat<C2_cmpgt,     setgt,          i1,   I32>;
 def: OpR_RR_pat<C2_cmpgtu,    setugt,         i1,   I32>;
 def: OpR_RR_pat<C2_cmpgt,     RevCmp<setlt>,  i1,   I32>;
 def: OpR_RR_pat<C2_cmpgtu,    RevCmp<setult>, i1,   I32>;
 def: OpR_RR_pat<C2_cmpeqp,    seteq,          i1,   I64>;
: Pat<(Store Value:$val, Addr:$addr),
         (MI Addr:$addr, (ValueMod Value:$val))>;
 
 // Regular stores in the DAG have two operands: value and address.
 // Atomic stores also have two, but they are reversed: address, value.
 // To use atomic stores with the patterns, they need to have their operands
 // swapped. This relies on the knowledge that the F.Fragment uses names
 // "ptr" and "val".
 class AtomSt<PatFrag F>
-  : PatFrag<(ops node:$val, node:$ptr), F.Fragment, F.PredicateCode,
+  : PatFrag<(ops node:$val, node:$ptr), !head(F.Fragments), F.PredicateCode,
             F.OperandTransform> {
   let IsAtomic = F.IsAtomic;
   let MemoryVT = F.MemoryVT;
 }
 
 
 def IMM_BYTE : SDNodeXForm<imm, [{
   // -1 can be represented as 255, etc.

lib/Target/NVPTX/NVPTXIntrinsics.td

class WMMA_LOAD_INTR_HELPER<string Geometry, string Abc, string Layout,
   code match_shared = [{
    return ChkMemSDNodeAddressSpace(N, llvm::ADDRESS_SPACE_SHARED);
   }];
   code match_global = [{
    return ChkMemSDNodeAddressSpace(N, llvm::ADDRESS_SPACE_GLOBAL);
   }];
 
   let Operands = !if(WithStride, (ops node:$src, node:$ldm), (ops node:$src));
-  let Fragment = !foreach(tmp, Operands, !subst(ops, Intr, tmp));
+  let Fragments = [!foreach(tmp, Operands, !subst(ops, Intr, tmp))];
   let PredicateCode = !if(!eq(Space, ".shared"), match_shared,
                       !if(!eq(Space, ".global"), match_global, match_generic));
 }
 
 multiclass WMMA_LOAD_GALSTS<string Geometry, string Abc, string Layout,
                             string Space, string Type, NVPTXRegClass regclass,
                             bit WithStride> {
   def _avar:  WMMA_LOAD_GALSTOS<Geometry, Abc, Layout, Space, Type, regclass,
class WMMA_STORE_INTR_HELPER<string Geometry, string Layout, string Space,
   }];
 
   dag Args = !if(!eq(Type,"f16"),
                  (ops node:$dst, node:$r0, node:$r1, node:$r2, node:$r3),
                  (ops node:$dst, node:$r0, node:$r1, node:$r2, node:$r3,
                                  node:$r4, node:$r5, node:$r6, node:$r7));
   dag StrideArg = !if(WithStride, (ops node:$ldm), (ops));
   let Operands = !con(Args, StrideArg);
-  let Fragment = !foreach(tmp, Operands, !subst(ops, Intr, tmp));
+  let Fragments = [!foreach(tmp, Operands, !subst(ops, Intr, tmp))];
   let PredicateCode = !if(!eq(Space, ".shared"), match_shared,
                       !if(!eq(Space, ".global"), match_global, match_generic));
 }
 
 multiclass WMMA_STORE_D_GLSTS<string Geometry, string Layout, string Space,
                               string Type, NVPTXRegClass regclass,
                               bit WithStride> {
   def _avar:   WMMA_STORE_D_GLSTSO<Geometry, Layout, Space, Type, regclass,

lib/Target/SystemZ/SystemZInstrInfo.td

 //===----------------------------------------------------------------------===//
 // Addition
 //===----------------------------------------------------------------------===//
 
 // Addition producing a signed overflow flag.
 let Defs = [CC], CCValues = 0xF, CompareZeroCCMask = 0x8 in {
   // Addition of a register.
   let isCommutable = 1 in {
-    defm AR : BinaryRRAndK<"ar", 0x1A, 0xB9F8, z_saddo, GR32, GR32>;
-    defm AGR : BinaryRREAndK<"agr", 0xB908, 0xB9E8, z_saddo, GR64, GR64>;
+    defm AR : BinaryRRAndK<"ar", 0x1A, 0xB9F8, z_sadd, GR32, GR32>;
+    defm AGR : BinaryRREAndK<"agr", 0xB908, 0xB9E8, z_sadd, GR64, GR64>;
   }
   def AGFR : BinaryRRE<"agfr", 0xB918, null_frag, GR64, GR32>;
 
   // Addition to a high register.
   def AHHHR : BinaryRRFa<"ahhhr", 0xB9C8, null_frag, GRH32, GRH32, GRH32>,
               Requires<[FeatureHighWord]>;
   def AHHLR : BinaryRRFa<"ahhlr", 0xB9D8, null_frag, GRH32, GRH32, GR32>,
               Requires<[FeatureHighWord]>;
 
   // Addition of signed 16-bit immediates.
-  defm AHIMux : BinaryRIAndKPseudo<"ahimux", z_saddo, GRX32, imm32sx16>;
-  defm AHI  : BinaryRIAndK<"ahi",  0xA7A, 0xECD8, z_saddo, GR32, imm32sx16>;
-  defm AGHI : BinaryRIAndK<"aghi", 0xA7B, 0xECD9, z_saddo, GR64, imm64sx16>;
+  defm AHIMux : BinaryRIAndKPseudo<"ahimux", z_sadd, GRX32, imm32sx16>;
+  defm AHI  : BinaryRIAndK<"ahi",  0xA7A, 0xECD8, z_sadd, GR32, imm32sx16>;
+  defm AGHI : BinaryRIAndK<"aghi", 0xA7B, 0xECD9, z_sadd, GR64, imm64sx16>;
 
   // Addition of signed 32-bit immediates.
-  def AFIMux : BinaryRIPseudo<z_saddo, GRX32, simm32>,
+  def AFIMux : BinaryRIPseudo<z_sadd, GRX32, simm32>,
                Requires<[FeatureHighWord]>;
-  def AFI  : BinaryRIL<"afi",  0xC29, z_saddo, GR32, simm32>;
-  def AIH  : BinaryRIL<"aih",  0xCC8, z_saddo, GRH32, simm32>,
+  def AFI  : BinaryRIL<"afi",  0xC29, z_sadd, GR32, simm32>;
+  def AIH  : BinaryRIL<"aih",  0xCC8, z_sadd, GRH32, simm32>,
              Requires<[FeatureHighWord]>;
-  def AGFI : BinaryRIL<"agfi", 0xC28, z_saddo, GR64, imm64sx32>;
+  def AGFI : BinaryRIL<"agfi", 0xC28, z_sadd, GR64, imm64sx32>;
 
   // Addition of memory.
-  defm AH  : BinaryRXPair<"ah", 0x4A, 0xE37A, z_saddo, GR32, asextloadi16, 2>;
-  defm A   : BinaryRXPair<"a",  0x5A, 0xE35A, z_saddo, GR32, load, 4>;
-  def  AGH : BinaryRXY<"agh", 0xE338, z_saddo, GR64, asextloadi16, 2>,
+  defm AH  : BinaryRXPair<"ah", 0x4A, 0xE37A, z_sadd, GR32, asextloadi16, 2>;
+  defm A   : BinaryRXPair<"a",  0x5A, 0xE35A, z_sadd, GR32, load, 4>;
+  def  AGH : BinaryRXY<"agh", 0xE338, z_sadd, GR64, asextloadi16, 2>,
              Requires<[FeatureMiscellaneousExtensions2]>;
-  def  AGF : BinaryRXY<"agf", 0xE318, z_saddo, GR64, asextloadi32, 4>;
-  def  AG  : BinaryRXY<"ag",  0xE308, z_saddo, GR64, load, 8>;
+  def  AGF : BinaryRXY<"agf", 0xE318, z_sadd, GR64, asextloadi32, 4>;
+  def  AG  : BinaryRXY<"ag",  0xE308, z_sadd, GR64, load, 8>;
 
   // Addition to memory.
-  def ASI  : BinarySIY<"asi",  0xEB6A, null_frag, imm32sx8>;
-  def AGSI : BinarySIY<"agsi", 0xEB7A, null_frag, imm64sx8>;
+  def ASI  : BinarySIY<"asi",  0xEB6A, add, imm32sx8>;
+  def AGSI : BinarySIY<"agsi", 0xEB7A, add, imm64sx8>;
 }
-defm : SXB<z_saddo, GR64, AGFR>;
+defm : SXB<z_sadd, GR64, AGFR>;
 
 // Addition producing a carry.
 let Defs = [CC] in {
   // Addition of a register.
   let isCommutable = 1 in {
-    defm ALR : BinaryRRAndK<"alr", 0x1E, 0xB9FA, z_uaddo, GR32, GR32>;
-    defm ALGR : BinaryRREAndK<"algr", 0xB90A, 0xB9EA, z_uaddo, GR64, GR64>;
+    defm ALR : BinaryRRAndK<"alr", 0x1E, 0xB9FA, z_uadd, GR32, GR32>;
+    defm ALGR : BinaryRREAndK<"algr", 0xB90A, 0xB9EA, z_uadd, GR64, GR64>;
   }
   def ALGFR : BinaryRRE<"algfr", 0xB91A, null_frag, GR64, GR32>;
 
   // Addition to a high register.
   def ALHHHR : BinaryRRFa<"alhhhr", 0xB9CA, null_frag, GRH32, GRH32, GRH32>,
                Requires<[FeatureHighWord]>;
   def ALHHLR : BinaryRRFa<"alhhlr", 0xB9DA, null_frag, GRH32, GRH32, GR32>,
                Requires<[FeatureHighWord]>;
 
   // Addition of signed 16-bit immediates.
-  def ALHSIK  : BinaryRIE<"alhsik",  0xECDA, z_uaddo, GR32, imm32sx16>,
+  def ALHSIK  : BinaryRIE<"alhsik",  0xECDA, z_uadd, GR32, imm32sx16>,
                 Requires<[FeatureDistinctOps]>;
-  def ALGHSIK : BinaryRIE<"alghsik", 0xECDB, z_uaddo, GR64, imm64sx16>,
+  def ALGHSIK : BinaryRIE<"alghsik", 0xECDB, z_uadd, GR64, imm64sx16>,
                 Requires<[FeatureDistinctOps]>;
 
   // Addition of unsigned 32-bit immediates.
-  def ALFI  : BinaryRIL<"alfi",  0xC2B, z_uaddo, GR32, uimm32>;
-  def ALGFI : BinaryRIL<"algfi", 0xC2A, z_uaddo, GR64, imm64zx32>;
+  def ALFI  : BinaryRIL<"alfi",  0xC2B, z_uadd, GR32, uimm32>;
+  def ALGFI : BinaryRIL<"algfi", 0xC2A, z_uadd, GR64, imm64zx32>;
 
   // Addition of signed 32-bit immediates.
   def ALSIH : BinaryRIL<"alsih", 0xCCA, null_frag, GRH32, simm32>,
               Requires<[FeatureHighWord]>;
 
   // Addition of memory.
-  defm AL   : BinaryRXPair<"al", 0x5E, 0xE35E, z_uaddo, GR32, load, 4>;
-  def  ALGF : BinaryRXY<"algf", 0xE31A, z_uaddo, GR64, azextloadi32, 4>;
-  def  ALG  : BinaryRXY<"alg",  0xE30A, z_uaddo, GR64, load, 8>;
+  defm AL   : BinaryRXPair<"al", 0x5E, 0xE35E, z_uadd, GR32, load, 4>;
+  def  ALGF : BinaryRXY<"algf", 0xE31A, z_uadd, GR64, azextloadi32, 4>;
+  def  ALG  : BinaryRXY<"alg",  0xE30A, z_uadd, GR64, load, 8>;
 
   // Addition to memory.
   def ALSI  : BinarySIY<"alsi",  0xEB6E, null_frag, imm32sx8>;
   def ALGSI : BinarySIY<"algsi", 0xEB7E, null_frag, imm64sx8>;
 }
-defm : ZXB<z_uaddo, GR64, ALGFR>;
+defm : ZXB<z_uadd, GR64, ALGFR>;
 
 // Addition producing and using a carry.
 let Defs = [CC], Uses = [CC] in {
   // Addition of a register.
   def ALCR  : BinaryRRE<"alcr",  0xB998, z_addcarry, GR32, GR32>;
   def ALCGR : BinaryRRE<"alcgr", 0xB988, z_addcarry, GR64, GR64>;
 
   // Addition of memory.
   def ALC  : BinaryRXY<"alc",  0xE398, z_addcarry, GR32, load, 4>;
   def ALCG : BinaryRXY<"alcg", 0xE388, z_addcarry, GR64, load, 8>;
 }
 
 // Addition that does not modify the condition code.
 def ALSIHN : BinaryRIL<"alsihn", 0xCCB, null_frag, GRH32, simm32>,
              Requires<[FeatureHighWord]>;
 
-// Map plain addition to either arithmetic or logical operation.
-
-def : Pat<(add GR32:$src1, GR32:$src2),
-          (AR GR32:$src1, GR32:$src2)>;
-def : Pat<(add GR64:$src1, GR64:$src2),
-          (AGR GR64:$src1, GR64:$src2)>;
-defm : SXB<add, GR64, AGFR>;
-defm : ZXB<add, GR64, ALGFR>;
-
-def : Pat<(add GRX32:$src1, imm32sx16:$src2),
-          (AHIMux GRX32:$src1, imm32sx16:$src2)>, Requires<[FeatureHighWord]>;
-def : Pat<(add GR32:$src1, imm32sx16:$src2),
-          (AHI GR32:$src1, imm32sx16:$src2)>;
-def : Pat<(add GR64:$src1, imm64sx16:$src2),
-          (AGHI GR64:$src1, imm64sx16:$src2)>;
-def : Pat<(add GRX32:$src1, simm32:$src2),
-          (AFIMux GRX32:$src1, simm32:$src2)>, Requires<[FeatureHighWord]>;
-def : Pat<(add GR32:$src1, simm32:$src2),
-          (AFI GR32:$src1, simm32:$src2)>;
-def : Pat<(add GRH32:$src1, simm32:$src2),
-          (AIH GRH32:$src1, simm32:$src2)>, Requires<[FeatureHighWord]>;
-def : Pat<(add GR64:$src1, imm64sx32:$src2),
-          (AGFI GR64:$src1, imm64sx32:$src2)>;
-def : Pat<(add GR64:$src1, imm64zx32:$src2),
-          (ALGFI GR64:$src1, imm64zx32:$src2)>;
-
-def : Pat<(add GR32:$src1, (asextloadi16 bdxaddr12pair:$addr)),
-          (AH GR32:$src1, bdxaddr12pair:$addr)>;
-def : Pat<(add GR32:$src1, (asextloadi16 bdxaddr20pair:$addr)),
-          (AHY GR32:$src1, bdxaddr20pair:$addr)>;
-def : Pat<(add GR32:$src1, (load bdxaddr12pair:$addr)),
-          (A GR32:$src1, bdxaddr12pair:$addr)>;
-def : Pat<(add GR32:$src1, (load bdxaddr20pair:$addr)),
-          (AY GR32:$src1, bdxaddr20pair:$addr)>;
-def : Pat<(add GR64:$src1, (asextloadi16 bdxaddr20only:$addr)),
-          (AGH GR64:$src1, bdxaddr20only:$addr)>,
-      Requires<[FeatureMiscellaneousExtensions2]>;
-def : Pat<(add GR64:$src1, (asextloadi32 bdxaddr20only:$addr)),
-          (AGF GR64:$src1, bdxaddr20only:$addr)>;
-def : Pat<(add GR64:$src1, (azextloadi32 bdxaddr20only:$addr)),
-          (ALGF GR64:$src1, bdxaddr20only:$addr)>;
-def : Pat<(add GR64:$src1, (load bdxaddr20only:$addr)),
-          (AG GR64:$src1, bdxaddr20only:$addr)>;
-
-def : Pat<(store (add (load bdaddr20only:$addr), imm32sx8:$src2), bdaddr20only:$addr),
-          (ASI bdaddr20only:$addr, imm32sx8:$src2)>;
-def : Pat<(store (add (load bdaddr20only:$addr), imm64sx8:$src2), bdaddr20only:$addr),
-          (AGSI bdaddr20only:$addr, imm64sx8:$src2)>;
 
 //===----------------------------------------------------------------------===//
 // Subtraction
 //===----------------------------------------------------------------------===//
 
 // Subtraction producing a signed overflow flag.
 let Defs = [CC], CCValues = 0xF, CompareZeroCCMask = 0x8 in {
   // Subtraction of a register.
-  defm SR : BinaryRRAndK<"sr", 0x1B, 0xB9F9, z_ssubo, GR32, GR32>;
+  defm SR : BinaryRRAndK<"sr", 0x1B, 0xB9F9, z_ssub, GR32, GR32>;
   def SGFR : BinaryRRE<"sgfr", 0xB919, null_frag, GR64, GR32>;
-  defm SGR : BinaryRREAndK<"sgr", 0xB909, 0xB9E9, z_ssubo, GR64, GR64>;
+  defm SGR : BinaryRREAndK<"sgr", 0xB909, 0xB9E9, z_ssub, GR64, GR64>;
 
   // Subtraction from a high register.
   def SHHHR : BinaryRRFa<"shhhr", 0xB9C9, null_frag, GRH32, GRH32, GRH32>,
               Requires<[FeatureHighWord]>;
   def SHHLR : BinaryRRFa<"shhlr", 0xB9D9, null_frag, GRH32, GRH32, GR32>,
               Requires<[FeatureHighWord]>;
 
   // Subtraction of memory.
-  defm SH  : BinaryRXPair<"sh", 0x4B, 0xE37B, z_ssubo, GR32, asextloadi16, 2>;
-  defm S   : BinaryRXPair<"s", 0x5B, 0xE35B, z_ssubo, GR32, load, 4>;
-  def  SGH : BinaryRXY<"sgh", 0xE339, z_ssubo, GR64, asextloadi16, 2>,
+  defm SH  : BinaryRXPair<"sh", 0x4B, 0xE37B, z_ssub, GR32, asextloadi16, 2>;
+  defm S   : BinaryRXPair<"s", 0x5B, 0xE35B, z_ssub, GR32, load, 4>;
+  def  SGH : BinaryRXY<"sgh", 0xE339, z_ssub, GR64, asextloadi16, 2>,
              Requires<[FeatureMiscellaneousExtensions2]>;
-  def  SGF : BinaryRXY<"sgf", 0xE319, z_ssubo, GR64, asextloadi32, 4>;
-  def  SG  : BinaryRXY<"sg",  0xE309, z_ssubo, GR64, load, 8>;
+  def  SGF : BinaryRXY<"sgf", 0xE319, z_ssub, GR64, asextloadi32, 4>;
+  def  SG  : BinaryRXY<"sg",  0xE309, z_ssub, GR64, load, 8>;
 }
-defm : SXB<z_ssubo, GR64, SGFR>;
+defm : SXB<z_ssub, GR64, SGFR>;
 
 // Subtracting an immediate is the same as adding the negated immediate.
 let AddedComplexity = 1 in {
-  def : Pat<(z_ssubo GR32:$src1, imm32sx16n:$src2),
+  def : Pat<(z_ssub GR32:$src1, imm32sx16n:$src2),
             (AHIMux GR32:$src1, imm32sx16n:$src2)>,
         Requires<[FeatureHighWord]>;
-  def : Pat<(z_ssubo GR32:$src1, simm32n:$src2),
+  def : Pat<(z_ssub GR32:$src1, simm32n:$src2),
             (AFIMux GR32:$src1, simm32n:$src2)>,
         Requires<[FeatureHighWord]>;
-  def : Pat<(z_ssubo GR32:$src1, imm32sx16n:$src2),
+  def : Pat<(z_ssub GR32:$src1, imm32sx16n:$src2),
             (AHI GR32:$src1, imm32sx16n:$src2)>;
-  def : Pat<(z_ssubo GR32:$src1, simm32n:$src2),
+  def : Pat<(z_ssub GR32:$src1, simm32n:$src2),
             (AFI GR32:$src1, simm32n:$src2)>;
-  def : Pat<(z_ssubo GR64:$src1, imm64sx16n:$src2),
+  def : Pat<(z_ssub GR64:$src1, imm64sx16n:$src2),
             (AGHI GR64:$src1, imm64sx16n:$src2)>;
-  def : Pat<(z_ssubo GR64:$src1, imm64sx32n:$src2),
+  def : Pat<(z_ssub GR64:$src1, imm64sx32n:$src2),
             (AGFI GR64:$src1, imm64sx32n:$src2)>;
 }
 
 // Subtraction producing a carry.
 let Defs = [CC] in {
   // Subtraction of a register.
-  defm SLR : BinaryRRAndK<"slr", 0x1F, 0xB9FB, z_usubo, GR32, GR32>;
+  defm SLR : BinaryRRAndK<"slr", 0x1F, 0xB9FB, z_usub, GR32, GR32>;
   def SLGFR : BinaryRRE<"slgfr", 0xB91B, null_frag, GR64, GR32>;
-  defm SLGR : BinaryRREAndK<"slgr", 0xB90B, 0xB9EB, z_usubo, GR64, GR64>;
+  defm SLGR : BinaryRREAndK<"slgr", 0xB90B, 0xB9EB, z_usub, GR64, GR64>;
 
   // Subtraction from a high register.
   def SLHHHR : BinaryRRFa<"slhhhr", 0xB9CB, null_frag, GRH32, GRH32, GRH32>,
                Requires<[FeatureHighWord]>;
   def SLHHLR : BinaryRRFa<"slhhlr", 0xB9DB, null_frag, GRH32, GRH32, GR32>,
                Requires<[FeatureHighWord]>;
 
   // Subtraction of unsigned 32-bit immediates.
-  def SLFI  : BinaryRIL<"slfi",  0xC25, z_usubo, GR32, uimm32>;
-  def SLGFI : BinaryRIL<"slgfi", 0xC24, z_usubo, GR64, imm64zx32>;
+  def SLFI  : BinaryRIL<"slfi",  0xC25, z_usub, GR32, uimm32>;
+  def SLGFI : BinaryRIL<"slgfi", 0xC24, z_usub, GR64, imm64zx32>;
 
   // Subtraction of memory.
-  defm SL   : BinaryRXPair<"sl", 0x5F, 0xE35F, z_usubo, GR32, load, 4>;
-  def  SLGF : BinaryRXY<"slgf", 0xE31B, z_usubo, GR64, azextloadi32, 4>;
-  def  SLG  : BinaryRXY<"slg",  0xE30B, z_usubo, GR64, load, 8>;
+  defm SL   : BinaryRXPair<"sl", 0x5F, 0xE35F, z_usub, GR32, load, 4>;
+  def  SLGF : BinaryRXY<"slgf", 0xE31B, z_usub, GR64, azextloadi32, 4>;
+  def  SLG  : BinaryRXY<"slg",  0xE30B, z_usub, GR64, load, 8>;
 }
-defm : ZXB<z_usubo, GR64, SLGFR>;
+defm : ZXB<z_usub, GR64, SLGFR>;
 
 // Subtracting an immediate is the same as adding the negated immediate.
 let AddedComplexity = 1 in {
-  def : Pat<(z_usubo GR32:$src1, imm32sx16n:$src2),
+  def : Pat<(z_usub GR32:$src1, imm32sx16n:$src2),
             (ALHSIK GR32:$src1, imm32sx16n:$src2)>,
         Requires<[FeatureDistinctOps]>;
-  def : Pat<(z_usubo GR64:$src1, imm64sx16n:$src2),
+  def : Pat<(z_usub GR64:$src1, imm64sx16n:$src2),
             (ALGHSIK GR64:$src1, imm64sx16n:$src2)>,
         Requires<[FeatureDistinctOps]>;
 }
 
+// And vice versa in one special case (but we prefer addition).
+def : Pat<(add GR64:$src1, imm64zx32n:$src2),
+          (SLGFI GR64:$src1, imm64zx32n:$src2)>;
+
 // Subtraction producing and using a carry.
 let Defs = [CC], Uses = [CC] in {
   // Subtraction of a register.
   def SLBR  : BinaryRRE<"slbr",  0xB999, z_subcarry, GR32, GR32>;
   def SLBGR : BinaryRRE<"slbgr", 0xB989, z_subcarry, GR64, GR64>;
 
   // Subtraction of memory.
   def SLB  : BinaryRXY<"slb",  0xE399, z_subcarry, GR32, load, 4>;
   def SLBG : BinaryRXY<"slbg", 0xE389, z_subcarry, GR64, load, 8>;
 }
 
-// Map plain subtraction to either arithmetic or logical operation.
-
-def : Pat<(sub GR32:$src1, GR32:$src2),
-          (SR GR32:$src1, GR32:$src2)>;
-def : Pat<(sub GR64:$src1, GR64:$src2),
-          (SGR GR64:$src1, GR64:$src2)>;
-defm : SXB<sub, GR64, SGFR>;
-defm : ZXB<sub, GR64, SLGFR>;
-
-def : Pat<(add GR64:$src1, imm64zx32n:$src2),
-          (SLGFI GR64:$src1, imm64zx32n:$src2)>;
-
-def : Pat<(sub GR32:$src1, (asextloadi16 bdxaddr12pair:$addr)),
-          (SH GR32:$src1, bdxaddr12pair:$addr)>;
-def : Pat<(sub GR32:$src1, (asextloadi16 bdxaddr20pair:$addr)),
-          (SHY GR32:$src1, bdxaddr20pair:$addr)>;
-def : Pat<(sub GR32:$src1, (load bdxaddr12pair:$addr)),
-          (S GR32:$src1, bdxaddr12pair:$addr)>;
-def : Pat<(sub GR32:$src1, (load bdxaddr20pair:$addr)),
-          (SY GR32:$src1, bdxaddr20pair:$addr)>;
-def : Pat<(sub GR64:$src1, (asextloadi16 bdxaddr20only:$addr)),
-          (SGH GR64:$src1, bdxaddr20only:$addr)>,
-      Requires<[FeatureMiscellaneousExtensions2]>;
-def : Pat<(sub GR64:$src1, (asextloadi32 bdxaddr20only:$addr)),
-          (SGF GR64:$src1, bdxaddr20only:$addr)>;
-def : Pat<(sub GR64:$src1, (azextloadi32 bdxaddr20only:$addr)),
-          (SLGF GR64:$src1, bdxaddr20only:$addr)>;
-def : Pat<(sub GR64:$src1, (load bdxaddr20only:$addr)),
-          (SG GR64:$src1, bdxaddr20only:$addr)>;
 
 //===----------------------------------------------------------------------===//
 // AND
 //===----------------------------------------------------------------------===//
 
 let Defs = [CC] in {
   // ANDs of a register.
   let isCommutable = 1, CCValues = 0xC, CompareZeroCCMask = 0x8 in {

lib/Target/SystemZ/SystemZOperators.td

def z_iabs64 : PatFrag<(ops node:$src),
                             (sra node:$src, (i32 63)))>;
 def z_inegabs32 : PatFrag<(ops node:$src), (ineg (z_iabs32 node:$src))>;
 def z_inegabs64 : PatFrag<(ops node:$src), (ineg (z_iabs64 node:$src))>;
 
 // Integer multiply-and-add
 def z_muladd : PatFrag<(ops node:$src1, node:$src2, node:$src3),
                        (add (mul node:$src1, node:$src2), node:$src3)>;
 
+// Alternatives to match operations with or without an overflow CC result.
+def z_sadd : PatFrags<(ops node:$src1, node:$src2),
+                      [(z_saddo node:$src1, node:$src2),
+                       (add node:$src1, node:$src2)]>;
+def z_uadd : PatFrags<(ops node:$src1, node:$src2),
+                      [(z_uaddo node:$src1, node:$src2),
+                       (add node:$src1, node:$src2)]>;
+def z_ssub : PatFrags<(ops node:$src1, node:$src2),
+                      [(z_ssubo node:$src1, node:$src2),
+                       (sub node:$src1, node:$src2)]>;
+def z_usub : PatFrags<(ops node:$src1, node:$src2),
+                      [(z_usubo node:$src1, node:$src2),
+                       (sub node:$src1, node:$src2)]>;
+
 // Fused multiply-subtract, using the natural operand order.
 def fms : PatFrag<(ops node:$src1, node:$src2, node:$src3),
                   (fma node:$src1, node:$src2, (fneg node:$src3))>;
 
 // Fused multiply-add and multiply-subtract, but with the order of the
 // operands matching SystemZ's MA and MS instructions.
 def z_fma : PatFrag<(ops node:$src1, node:$src2, node:$src3),
                     (fma node:$src2, node:$src3, node:$src1)>;

utils/TableGen/CodeGenDAGPatterns.h

bool isIsomorphicTo(const TreePatternNode *N,
                       const MultipleUseVarSet &DepVars) const;
 
   /// SubstituteFormalArguments - Replace the formal arguments in this tree
   /// with actual values specified by ArgMap.
   void
   SubstituteFormalArguments(std::map<std::string, TreePatternNodePtr> &ArgMap);
 
   /// InlinePatternFragments - If this pattern refers to any pattern
-  /// fragments, inline them into place, giving us a pattern without any
-  /// PatFrag references.
-  TreePatternNodePtr InlinePatternFragments(TreePatternNodePtr T,
-                                            TreePattern &TP);
+  /// fragments, return the set of inlined versions (this can be more than
+  /// one if a PatFrags record has multiple alternatives).
+  void InlinePatternFragments(TreePatternNodePtr T,
+                              TreePattern &TP,
+                              std::vector<TreePatternNodePtr> &OutAlternatives);
 
   /// ApplyTypeConstraints - Apply all of the type constraints relevant to
   /// this node and its children in the tree.  This returns true if it makes a
   /// change, false otherwise.  If a type contradiction is found, flag an error.
   bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters);
 
   /// UpdateNodeType - Set the node type of N to VT if VT contains
   /// information.  If N already contains a conflicting type, then flag an
const std::string &getArgName(unsigned i) const {
     return Args[i];
   }
   std::vector<std::string> &getArgList() { return Args; }
 
   CodeGenDAGPatterns &getDAGPatterns() const { return CDP; }
 
   /// InlinePatternFragments - If this pattern refers to any pattern
   /// fragments, inline them into place, giving us a pattern without any
-  /// PatFrag references.
+  /// PatFrags references.  This may increase the number of trees in the
+  /// pattern if a PatFrags has multiple alternatives.
   void InlinePatternFragments() {
-    for (unsigned i = 0, e = Trees.size(); i != e; ++i)
-      Trees[i] = Trees[i]->InlinePatternFragments(Trees[i], *this);
+    std::vector<TreePatternNodePtr> Copy = Trees;
+    Trees.clear();
+    for (unsigned i = 0, e = Copy.size(); i != e; ++i)
+      Copy[i]->InlinePatternFragments(Copy[i], *this, Trees);
   }
 
   /// InferAllTypes - Infer/propagate as many types throughout the expression
   /// patterns as possible.  Return true if all types are inferred, false
   /// otherwise.  Bail out if a type contradiction is found.
   bool InferAllTypes(
       const StringMap<SmallVector<TreePatternNode *, 1>> *NamedTypes = nullptr);
 

 
 /// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
 /// that has a set ExecuteAlways / DefaultOps field.
 struct DAGDefaultOperand {
   std::vector<TreePatternNodePtr> DefaultOps;
 };
 
 class DAGInstruction {
-  std::unique_ptr<TreePattern> Pattern;
   std::vector<Record*> Results;
   std::vector<Record*> Operands;
   std::vector<Record*> ImpResults;
+  TreePatternNodePtr SrcPattern;
   TreePatternNodePtr ResultPattern;
 
 public:
-  DAGInstruction(std::unique_ptr<TreePattern> &&TP,
-                 const std::vector<Record*> &results,
+  DAGInstruction(const std::vector<Record*> &results,
                  const std::vector<Record*> &operands,
-                 const std::vector<Record*> &impresults)
-    : Pattern(std::move(TP)), Results(results), Operands(operands),
-      ImpResults(impresults), ResultPattern(nullptr) {}
+                 const std::vector<Record*> &impresults,
+                 TreePatternNodePtr srcpattern = nullptr,
+                 TreePatternNodePtr resultpattern = nullptr)
+    : Results(results), Operands(operands), ImpResults(impresults),
+      SrcPattern(srcpattern), ResultPattern(resultpattern) {}
 
-  TreePattern *getPattern() const { return Pattern.get(); }
   unsigned getNumResults() const { return Results.size(); }
   unsigned getNumOperands() const { return Operands.size(); }
   unsigned getNumImpResults() const { return ImpResults.size(); }
   const std::vector<Record*>& getImpResults() const { return ImpResults; }
 
-  void setResultPattern(TreePatternNodePtr R) { ResultPattern = R; }
-
   Record *getResult(unsigned RN) const {
     assert(RN < Results.size());
     return Results[RN];
   }
 
   Record *getOperand(unsigned ON) const {
     assert(ON < Operands.size());
     return Operands[ON];
   }
 
   Record *getImpResult(unsigned RN) const {
     assert(RN < ImpResults.size());
     return ImpResults[RN];
   }
 
+  TreePatternNodePtr getSrcPattern() const { return SrcPattern; }
   TreePatternNodePtr getResultPattern() const { return ResultPattern; }
 };
 
 /// This class represents a condition that has to be satisfied for a pattern
 /// to be tried. It is a generalization of a class "Pattern" from Target.td:
 /// in addition to the Target.td's predicates, this class can also represent
 /// conditions associated with HW modes. Both types will eventually become
 /// strings containing C++ code to be executed, the difference is in how

 /// processed to produce isel.
 class PatternToMatch {
 public:
   PatternToMatch(Record *srcrecord, std::vector<Predicate> preds,
                  TreePatternNodePtr src, TreePatternNodePtr dst,
                  std::vector<Record *> dstregs, int complexity,
                  unsigned uid, unsigned setmode = 0)
       : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
-        Predicates(std::move(preds)), Dstregs(std::move(dstregs)),
+        Predicates(preds), Dstregs(dstregs),
         AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}
 
   Record          *SrcRecord;   // Originating Record for the pattern.
   TreePatternNodePtr SrcPattern;      // Source pattern to match.
   TreePatternNodePtr DstPattern;      // Resulting pattern.
   std::vector<Predicate> Predicates;  // Top level predicate conditions
                                       // to match.
   std::vector<Record*> Dstregs; // Physical register defs being matched.
public:
   // Patterns to match information.
   typedef std::vector<PatternToMatch>::const_iterator ptm_iterator;
   ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); }
   ptm_iterator ptm_end() const { return PatternsToMatch.end(); }
   iterator_range<ptm_iterator> ptms() const { return PatternsToMatch; }
 
   /// Parse the Pattern for an instruction, and insert the result in DAGInsts.
   typedef std::map<Record*, DAGInstruction, LessRecordByID> DAGInstMap;
-  const DAGInstruction &parseInstructionPattern(
+  void parseInstructionPattern(
       CodeGenInstruction &CGI, ListInit *Pattern,
       DAGInstMap &DAGInsts);
 
   const DAGInstruction &getInstruction(Record *R) const {
     auto F = Instructions.find(R);
     assert(F != Instructions.end() && "Unknown instruction!");
     return F->second;
   }
private:
   void ParsePatterns();
   void ExpandHwModeBasedTypes();
   void InferInstructionFlags();
   void GenerateVariants();
   void VerifyInstructionFlags();
 
   std::vector<Predicate> makePredList(ListInit *L);
 
+  void ParseOnePattern(Record *TheDef,
+                       TreePattern &Pattern, TreePattern &Result,
+                       const std::vector<Record *> &InstImpResults);
   void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM);
   void FindPatternInputsAndOutputs(
       TreePattern &I, TreePatternNodePtr Pat,
       std::map<std::string, TreePatternNodePtr> &InstInputs,
       std::map<std::string, TreePatternNodePtr> &InstResults,
       std::vector<Record *> &InstImpResults);
 };
 

utils/TableGen/CodeGenDAGPatterns.cpp

if (Operator->getName() == "set" ||
     return 0;  // All return nothing.
 
   if (Operator->isSubClassOf("Intrinsic"))
     return CDP.getIntrinsic(Operator).IS.RetVTs.size();
 
   if (Operator->isSubClassOf("SDNode"))
     return CDP.getSDNodeInfo(Operator).getNumResults();
 
-  if (Operator->isSubClassOf("PatFrag")) {
+  if (Operator->isSubClassOf("PatFrags")) {
     // If we've already parsed this pattern fragment, get it.  Otherwise, handle
     // the forward reference case where one pattern fragment references another
     // before it is processed.
-    if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator))
-      return PFRec->getOnlyTree()->getNumTypes();
+    if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) {
+      // The number of results of a fragment with alternative records is the
+      // maximum number of results across all alternatives.
+      unsigned NumResults = 0;
+      for (auto T : PFRec->getTrees())
+        NumResults = std::max(NumResults, T->getNumTypes());
+      return NumResults;
+    }
 
-    // Get the result tree.
-    DagInit *Tree = Operator->getValueAsDag("Fragment");
+    ListInit *LI = Operator->getValueAsListInit("Fragments");
+    assert(LI && "Invalid Fragment");
+    unsigned NumResults = 0;
+    for (Init *I : LI->getValues()) {
       Record *Op = nullptr;
-    if (Tree)
-      if (DefInit *DI = dyn_cast<DefInit>(Tree->getOperator()))
+      if (DagInit *Dag = dyn_cast<DagInit>(I))
+        if (DefInit *DI = dyn_cast<DefInit>(Dag->getOperator()))
           Op = DI->getDef();
       assert(Op && "Invalid Fragment");
-    return GetNumNodeResults(Op, CDP);
+      NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP));
+    }
+    return NumResults;
   }
 
   if (Operator->isSubClassOf("Instruction")) {
     CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);
 
     unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;
 
     // Subtract any defaulted outputs.
for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
     } else {
       getChild(i)->SubstituteFormalArguments(ArgMap);
     }
   }
 }
 
 
 /// InlinePatternFragments - If this pattern refers to any pattern
-/// fragments, inline them into place, giving us a pattern without any
-/// PatFrag references.
-TreePatternNodePtr TreePatternNode::InlinePatternFragments(TreePatternNodePtr T,
-                                                           TreePattern &TP) {
+/// fragments, return the set of inlined versions (this can be more than
+/// one if a PatFrags record has multiple alternatives).
+void TreePatternNode::InlinePatternFragments(
+  TreePatternNodePtr T, TreePattern &TP,
+  std::vector<TreePatternNodePtr> &OutAlternatives) {
+
   if (TP.hasError())
-    return nullptr;
+    return;
+
+  if (isLeaf()) {
+    OutAlternatives.push_back(T);  // nothing to do.
+    return;
+  }
 
-  if (isLeaf())
-    return T; // nothing to do.
   Record *Op = getOperator();
 
-  if (!Op->isSubClassOf("PatFrag")) {
-    // Just recursively inline children nodes.
+  if (!Op->isSubClassOf("PatFrags")) {
+    if (getNumChildren() == 0) {
+      OutAlternatives.push_back(T);
+      return;
+    }
+
+    // Recursively inline children nodes.
+    std::vector<std::vector<TreePatternNodePtr> > ChildAlternatives;
+    ChildAlternatives.resize(getNumChildren());
     for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
       TreePatternNodePtr Child = getChildShared(i);
-      TreePatternNodePtr NewChild = Child->InlinePatternFragments(Child, TP);
+      Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]);
+      // If there are no alternatives for any child, there are no
+      // alternatives for this expression as whole.
+      if (ChildAlternatives[i].empty())
+        return;
 
+      for (auto NewChild : ChildAlternatives[i])
         assert((Child->getPredicateFns().empty() ||
                 NewChild->getPredicateFns() == Child->getPredicateFns()) &&
                "Non-empty child predicate clobbered!");
+    }
 
-      setChild(i, std::move(NewChild));
+    // The end result is an all-pairs construction of the resultant pattern.
+    std::vector<unsigned> Idxs;
+    Idxs.resize(ChildAlternatives.size());
+    bool NotDone;
+    do {
+      // Create the variant and add it to the output list.
+      std::vector<TreePatternNodePtr> NewChildren;
+      for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i)
+        NewChildren.push_back(ChildAlternatives[i][Idxs[i]]);
+      TreePatternNodePtr R = std::make_shared<TreePatternNode>(
+          getOperator(), NewChildren, getNumTypes());
+
+      // Copy over properties.
+      R->setName(getName());
+      R->setPredicateFns(getPredicateFns());
+      R->setTransformFn(getTransformFn());
+      for (unsigned i = 0, e = getNumTypes(); i != e; ++i)
+        R->setType(i, getExtType(i));
+
+      // Register alternative.
+      OutAlternatives.push_back(R);
+
+      // Increment indices to the next permutation by incrementing the
+      // indices from last index backward, e.g., generate the sequence
+      // [0, 0], [0, 1], [1, 0], [1, 1].
+      int IdxsIdx;
+      for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
+        if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size())
+          Idxs[IdxsIdx] = 0;
+        else
+          break;
       }
-    return T;
+      NotDone = (IdxsIdx >= 0);
+    } while (NotDone);
+
+    return;
   }
 
   // Otherwise, we found a reference to a fragment.  First, look up its
   // TreePattern record.
   TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);
 
   // Verify that we are passing the right number of operands.
   if (Frag->getNumArgs() != Children.size()) {
     TP.error("'" + Op->getName() + "' fragment requires " +
              Twine(Frag->getNumArgs()) + " operands!");
-    return {nullptr};
+    return;
   }
 
-  TreePatternNodePtr FragTree = Frag->getOnlyTree()->clone();
-
-  TreePredicateFn PredFn(Frag);
-  if (!PredFn.isAlwaysTrue())
-    FragTree->addPredicateFn(PredFn);
-
-  // Resolve formal arguments to their actual value.
-  if (Frag->getNumArgs()) {
-    // Compute the map of formal to actual arguments.
-    std::map<std::string, TreePatternNodePtr> ArgMap;
-    for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {
-      const TreePatternNodePtr &Child = getChildShared(i);
-      ArgMap[Frag->getArgName(i)] = Child->InlinePatternFragments(Child, TP);
-    }
+    ArgMap[Frag->getArgName(i)] = Child;
 
+  // Loop over all fragment alternatives.
+  for (auto Alternative : Frag->getTrees()) {
+    TreePatternNodePtr FragTree = Alternative->clone();
+
+    TreePredicateFn PredFn(Frag);
+    if (!PredFn.isAlwaysTrue())
+      FragTree->addPredicateFn(PredFn);
+
+    // Resolve formal arguments to their actual value.
+    if (Frag->getNumArgs())
       FragTree->SubstituteFormalArguments(ArgMap);
-  }
 
+    // Transfer types.  Note that the resolved alternative may have fewer
+    // (but not more) results than the PatFrags node.
     FragTree->setName(getName());
-  for (unsigned i = 0, e = Types.size(); i != e; ++i)
+    for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i)
       FragTree->UpdateNodeType(i, getExtType(i), TP);
 
     // Transfer in the old predicates.
     for (const TreePredicateFn &Pred : getPredicateFns())
       FragTree->addPredicateFn(Pred);
 
     // The fragment we inlined could have recursive inlining that is needed.  See
     // if there are any pattern fragments in it and inline them as needed.
-  return FragTree->InlinePatternFragments(FragTree, TP);
+    FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives);
+  }
 }
 
 /// getImplicitType - Check to see if the specified record has an implicit
 /// type which should be applied to it.  This will infer the type of register
 /// references from the register file information, for example.
 ///
 /// When Unnamed is set, return the type of a DAG operand with no name, such as
 /// the F8RC register class argument in:
if (R->isSubClassOf("RegisterClass")) {
     // In a named operand, the register class provides the possible set of
     // types.
     if (NotRegisters)
       return TypeSetByHwMode(); // Unknown.
     const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
     return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes());
   }
 
-  if (R->isSubClassOf("PatFrag")) {
+  if (R->isSubClassOf("PatFrags")) {
     assert(ResNo == 0 && "FIXME: PatFrag with multiple results?");
     // Pattern fragment types will be resolved when they are inlined.
     return TypeSetByHwMode(); // Unknown.
   }
 
   if (R->isSubClassOf("Register")) {
     assert(ResNo == 0 && "Registers only produce one result!");
     if (NotRegisters)
if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) {
         break;
       }
       return MadeChange;
     }
 
     return false;
   }
 
-  // special handling for set, which isn't really an SDNode.
-  if (getOperator()->getName() == "set") {
-    assert(getNumTypes() == 0 && "Set doesn't produce a value");
-    assert(getNumChildren() >= 2 && "Missing RHS of a set?");
-    unsigned NC = getNumChildren();
-
-    TreePatternNode *SetVal = getChild(NC-1);
-    bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters);
-
-    for (unsigned i = 0; i < NC-1; ++i) {
-      TreePatternNode *Child = getChild(i);
-      MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters);
-
-      // Types of operands must match.
-      MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP);
-      MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP);
-    }
-    return MadeChange;
-  }
-
-  if (getOperator()->getName() == "implicit") {
-    assert(getNumTypes() == 0 && "Node doesn't produce a value");
-
-    bool MadeChange = false;
-    for (unsigned i = 0; i < getNumChildren(); ++i)
-      MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
-    return MadeChange;
-  }
-
   if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {
     bool MadeChange = false;
 
     // Apply the result type to the node.
     unsigned NumRetVTs = Int->IS.RetVTs.size();
     unsigned NumParamVTs = Int->IS.ParamVTs.size();
 
     for (unsigned i = 0, e = NumRetVTs; i != e; ++i)

 TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
                                                  StringRef OpName) {
   if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {
     Record *R = DI->getDef();
 
     // Direct reference to a leaf DagNode or PatFrag?  Turn it into a
     // TreePatternNode of its own.  For example:
     ///   (foo GPR, imm) -> (foo GPR, (imm))
-    if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag"))
+    if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags"))
       return ParseTreePattern(
         DagInit::get(DI, nullptr,
                      std::vector<std::pair<Init*, StringInit*> >()),
         OpName);
 
     // Input argument?
     TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1);
     if (R->getName() == "node" && !OpName.empty()) {
if (Operator->isSubClassOf("ValueType")) {
     New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);
 
     if (!OpName.empty())
       error("ValueType cast should not have a name!");
     return New;
   }
 
   // Verify that this is something that makes sense for an operator.
-  if (!Operator->isSubClassOf("PatFrag") &&
+  if (!Operator->isSubClassOf("PatFrags") &&
       !Operator->isSubClassOf("SDNode") &&
       !Operator->isSubClassOf("Instruction") &&
       !Operator->isSubClassOf("SDNodeXForm") &&
       !Operator->isSubClassOf("Intrinsic") &&
       !Operator->isSubClassOf("ComplexPattern") &&
       Operator->getName() != "set" &&
       Operator->getName() != "implicit")
     error("Unrecognized node '" + Operator->getName() + "'!");

 
 
 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
 /// file, building up the PatternFragments map.  After we've collected them all,
 /// inline fragments together as necessary, so that there are no references left
 /// inside a pattern fragment to a pattern fragment.
 ///
 void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {
-  std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag");
+  std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags");
 
   // First step, parse all of the fragments.
   for (Record *Frag : Fragments) {
     if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
       continue;
 
-    DagInit *Tree = Frag->getValueAsDag("Fragment");
+    ListInit *LI = Frag->getValueAsListInit("Fragments");
     TreePattern *P =
         (PatternFragments[Frag] = llvm::make_unique<TreePattern>(
-             Frag, Tree, !Frag->isSubClassOf("OutPatFrag"),
+             Frag, LI, !Frag->isSubClassOf("OutPatFrag"),
              *this)).get();
 
     // Validate the argument list, converting it to set, to discard duplicates.
     std::vector<std::string> &Args = P->getArgList();
     // Copy the args so we can take StringRefs to them.
     auto ArgsCopy = Args;
     SmallDenseSet<StringRef, 4> OperandsSet;
     OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());
for (Record *Frag : Fragments) {
     if (!OperandsSet.empty())
       P->error("Operands list does not contain an entry for operand '" +
                *OperandsSet.begin() + "'!");
 
     // If there is a code init for this fragment, keep track of the fact that
     // this fragment uses it.
     TreePredicateFn PredFn(P);
     if (!PredFn.isAlwaysTrue())
-      P->getOnlyTree()->addPredicateFn(PredFn);
+      for (auto T : P->getTrees())
+        T->addPredicateFn(PredFn);
 
     // If there is a node transformation corresponding to this, keep track of
     // it.
     Record *Transform = Frag->getValueAsDef("OperandTransform");
     if (!getSDNodeTransform(Transform).second.empty())    // not noop xform?
-      P->getOnlyTree()->setTransformFn(Transform);
+      for (auto T : P->getTrees())
+        T->setTransformFn(Transform);
   }
 
   // Now that we've parsed all of the tree fragments, do a closure on them so
   // that there are not references to PatFrags left inside of them.
   for (Record *Frag : Fragments) {
     if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
       continue;
 
static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat,
   } else {
     assert(Slot->getNumChildren() == 0 && "can't be a use with children!");
     SlotRec = Slot->getOperator();
   }
 
   // Ensure that the inputs agree if we've already seen this input.
   if (Rec != SlotRec)
     I.error("All $" + Pat->getName() + " inputs must agree with each other");
+  // Ensure that the types can agree as well.
+  Slot->UpdateNodeType(0, Pat->getExtType(0), I);
+  Pat->UpdateNodeType(0, Slot->getExtType(0), I);
   if (Slot->getExtTypes() != Pat->getExtTypes())
     I.error("All $" + Pat->getName() + " inputs must agree with each other");
   return true;
 }
 
 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
 /// part of "I", the instruction), computing the set of inputs and outputs of
 /// the pattern.  Report errors if we see anything naughty.
 void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
     TreePattern &I, TreePatternNodePtr Pat,
     std::map<std::string, TreePatternNodePtr> &InstInputs,
     std::map<std::string, TreePatternNodePtr> &InstResults,
     std::vector<Record *> &InstImpResults) {
+
+  // The instruction pattern still has unresolved fragments.  For *named*
+  // nodes we must resolve those here.  This may not result in multiple
+  // alternatives.
+  if (!Pat->getName().empty()) {
+    TreePattern SrcPattern(I.getRecord(), Pat, true, *this);
+    SrcPattern.InlinePatternFragments();
+    SrcPattern.InferAllTypes();
+    Pat = SrcPattern.getOnlyTree();
+  }
+
   if (Pat->isLeaf()) {
     bool isUse = HandleUse(I, Pat, InstInputs);
     if (!isUse && Pat->getTransformFn())
       I.error("Cannot specify a transform function for a non-input value!");
     return;
   }
 
   if (Pat->getOperator()->getName() == "implicit") {
void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
 
   if (Pat->getTransformFn())
     I.error("Cannot specify a transform function on a set node!");
 
   // Check the set destinations.
   unsigned NumDests = Pat->getNumChildren()-1;
   for (unsigned i = 0; i != NumDests; ++i) {
     TreePatternNodePtr Dest = Pat->getChildShared(i);
+    // For set destinations we also must resolve fragments here.
+    TreePattern DestPattern(I.getRecord(), Dest, false, *this);
+    DestPattern.InlinePatternFragments();
+    DestPattern.InferAllTypes();
+    Dest = DestPattern.getOnlyTree();
+
     if (!Dest->isLeaf())
       I.error("set destination should be a register!");
 
     DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
     if (!Val) {
       I.error("set destination should be a register!");
       continue;
     }

 class InstAnalyzer {
   const CodeGenDAGPatterns &CDP;
 public:
   bool hasSideEffects;
   bool mayStore;
   bool mayLoad;
   bool isBitcast;
   bool isVariadic;
+  bool hasChain;
 
   InstAnalyzer(const CodeGenDAGPatterns &cdp)
     : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),
-      isBitcast(false), isVariadic(false) {}
-
-  void Analyze(const TreePattern *Pat) {
-    // Assume only the first tree is the pattern. The others are clobber nodes.
-    AnalyzeNode(Pat->getTree(0).get());
-  }
+      isBitcast(false), isVariadic(false), hasChain(false) {}
 
   void Analyze(const PatternToMatch &Pat) {
-    AnalyzeNode(Pat.getSrcPattern());
+    const TreePatternNode *N = Pat.getSrcPattern();
+    AnalyzeNode(N);
+    // These properties are detected only on the root node.
+    isBitcast = IsNodeBitcast(N);
   }
 
 private:
   bool IsNodeBitcast(const TreePatternNode *N) const {
     if (hasSideEffects || mayLoad || mayStore || isVariadic)
       return false;
 
-    if (N->getNumChildren() != 2)
-      return false;
-
-    const TreePatternNode *N0 = N->getChild(0);
-    if (!N0->isLeaf() || !isa<DefInit>(N0->getLeafValue()))
-      return false;
-
-    const TreePatternNode *N1 = N->getChild(1);
-    if (N1->isLeaf())
+    if (N->isLeaf())
       return false;
-    if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf())
+    if (N->getNumChildren() != 1 || !N->getChild(0)->isLeaf())
       return false;
 
-    const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator());
+    const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator());
     if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1)
       return false;
     return OpInfo.getEnumName() == "ISD::BITCAST";
   }
 
 public:
   void AnalyzeNode(const TreePatternNode *N) {
     if (N->isLeaf()) {
if (N->isLeaf()) {
       }
       return;
     }
 
     // Analyze children.
     for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
       AnalyzeNode(N->getChild(i));
 
-    // Ignore set nodes, which are not SDNodes.
-    if (N->getOperator()->getName() == "set") {
-      isBitcast = IsNodeBitcast(N);
-      return;
-    }
-
     // Notice properties of the node.
     if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;
     if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;
     if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;
     if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;
+    if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true;
 
     if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
       // If this is an intrinsic, analyze it.
       if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref)
         mayLoad = true;// These may load memory.
 
       if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod)
         mayStore = true;// Intrinsics that can write to memory are 'mayStore'.
static bool InferFromPattern(CodeGenInstruction &InstInfo,
   }
 
   // Transfer inferred flags.
   InstInfo.hasSideEffects |= PatInfo.hasSideEffects;
   InstInfo.mayStore |= PatInfo.mayStore;
   InstInfo.mayLoad |= PatInfo.mayLoad;
 
   // These flags are silently added without any verification.
+  // FIXME: To match historical behavior of TableGen, for now add those flags
+  // only when we're inferring from the primary instruction pattern.
+  if (PatDef->isSubClassOf("Instruction")) {
     InstInfo.isBitcast |= PatInfo.isBitcast;
+    InstInfo.hasChain |= PatInfo.hasChain;
+    InstInfo.hasChain_Inferred = true;
+  }
 
   // Don't infer isVariadic. This flag means something different on SDNodes and
   // instructions. For example, a CALL SDNode is variadic because it has the
   // call arguments as operands, but a CALL instruction is not variadic - it
   // has argument registers as implicit, not explicit uses.
 
   return Error;
 }
static bool checkOperandClass(CGIOperandList::OperandInfo &OI,
 
   // Patterns can also be ComplexPattern instances.
   if (Leaf->isSubClassOf("ComplexPattern"))
     return true;
 
   return false;
 }
 
-const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
+void CodeGenDAGPatterns::parseInstructionPattern(
     CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) {
 
   assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!");
 
   // Parse the instruction.
-  auto I = llvm::make_unique<TreePattern>(CGI.TheDef, Pat, true, *this);
-  // Inline pattern fragments into it.
-  I->InlinePatternFragments();
-
-  // Infer as many types as possible.  If we cannot infer all of them, we can
-  // never do anything with this instruction pattern: report it to the user.
-  if (!I->InferAllTypes())
-    I->error("Could not infer all types in pattern!");
+  TreePattern I(CGI.TheDef, Pat, true, *this);
 
   // InstInputs - Keep track of all of the inputs of the instruction, along
   // with the record they are declared as.
   std::map<std::string, TreePatternNodePtr> InstInputs;
 
   // InstResults - Keep track of all the virtual registers that are 'set'
   // in the instruction, including what reg class they are.
   std::map<std::string, TreePatternNodePtr> InstResults;
 
   std::vector<Record*> InstImpResults;
 
   // Verify that the top-level forms in the instruction are of void type, and
   // fill in the InstResults map.
   SmallString<32> TypesString;
-  for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
+  for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) {
     TypesString.clear();
-    TreePatternNodePtr Pat = I->getTree(j);
+    TreePatternNodePtr Pat = I.getTree(j);
     if (Pat->getNumTypes() != 0) {
       raw_svector_ostream OS(TypesString);
       for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
         if (k > 0)
           OS << ", ";
         Pat->getExtType(k).writeToStream(OS);
       }
-      I->error("Top-level forms in instruction pattern should have"
+      I.error("Top-level forms in instruction pattern should have"
                " void types, has types " +
                OS.str());
     }
 
     // Find inputs and outputs, and verify the structure of the uses/defs.
-    FindPatternInputsAndOutputs(*I, Pat, InstInputs, InstResults,
+    FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
                                 InstImpResults);
   }
 
   // Now that we have inputs and outputs of the pattern, inspect the operands
   // list for the instruction.  This determines the order that operands are
   // added to the machine instruction the node corresponds to.
   unsigned NumResults = InstResults.size();
 
   // Parse the operands list from the (ops) list, validating it.
-  assert(I->getArgList().empty() && "Args list should still be empty here!");
+  assert(I.getArgList().empty() && "Args list should still be empty here!");
 
   // Check that all of the results occur first in the list.
   std::vector<Record*> Results;
   SmallVector<TreePatternNodePtr, 2> ResNodes;
   for (unsigned i = 0; i != NumResults; ++i) {
     if (i == CGI.Operands.size())
-      I->error("'" + InstResults.begin()->first +
+      I.error("'" + InstResults.begin()->first +
                "' set but does not appear in operand list!");
     const std::string &OpName = CGI.Operands[i].Name;
 
     // Check that it exists in InstResults.
     TreePatternNodePtr RNode = InstResults[OpName];
     if (!RNode)
-      I->error("Operand $" + OpName + " does not exist in operand list!");
+      I.error("Operand $" + OpName + " does not exist in operand list!");
 
 
     Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();
     ResNodes.push_back(std::move(RNode));
     if (!R)
-      I->error("Operand $" + OpName + " should be a set destination: all "
+      I.error("Operand $" + OpName + " should be a set destination: all "
                "outputs must occur before inputs in operand list!");
 
     if (!checkOperandClass(CGI.Operands[i], R))
-      I->error("Operand $" + OpName + " class mismatch!");
+      I.error("Operand $" + OpName + " class mismatch!");
 
     // Remember the return type.
     Results.push_back(CGI.Operands[i].Rec);
 
     // Okay, this one checks out.
     InstResults.erase(OpName);
   }
 
   // Loop over the inputs next.  Make a copy of InstInputs so we can destroy
   // the copy while we're checking the inputs.
   std::map<std::string, TreePatternNodePtr> InstInputsCheck(InstInputs);
 
   std::vector<TreePatternNodePtr> ResultNodeOperands;
   std::vector<Record*> Operands;
   for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {
     CGIOperandList::OperandInfo &Op = CGI.Operands[i];
     const std::string &OpName = Op.Name;
     if (OpName.empty())
-      I->error("Operand #" + Twine(i) + " in operands list has no name!");
+      I.error("Operand #" + Twine(i) + " in operands list has no name!");
 
     if (!InstInputsCheck.count(OpName)) {
       // If this is an operand with a DefaultOps set filled in, we can ignore
       // this.  When we codegen it, we will do so as always executed.
       if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {
         // Does it have a non-empty DefaultOps field?  If so, ignore this
         // operand.
         if (!getDefaultOperand(Op.Rec).DefaultOps.empty())
           continue;
       }
-      I->error("Operand $" + OpName +
+      I.error("Operand $" + OpName +
                " does not appear in the instruction pattern");
     }
     TreePatternNodePtr InVal = InstInputsCheck[OpName];
     InstInputsCheck.erase(OpName);   // It occurred, remove from map.
 
     if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {
       Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef();
       if (!checkOperandClass(Op, InRec))
-        I->error("Operand $" + OpName + "'s register class disagrees"
+        I.error("Operand $" + OpName + "'s register class disagrees"
                  " between the operand and pattern");
     }
     Operands.push_back(Op.Rec);
 
     // Construct the result for the dest-pattern operand list.
     TreePatternNodePtr OpNode = InVal->clone();
 
     // No predicate is useful on the result.
     OpNode->clearPredicateFns();
 
     // Promote the xform function to be an explicit node if set.
     if (Record *Xform = OpNode->getTransformFn()) {
       OpNode->setTransformFn(nullptr);
       std::vector<TreePatternNodePtr> Children;
       Children.push_back(OpNode);
       OpNode = std::make_shared<TreePatternNode>(Xform, Children,
                                                  OpNode->getNumTypes());
     }
 
     ResultNodeOperands.push_back(std::move(OpNode));
   }
 
   if (!InstInputsCheck.empty())
-    I->error("Input operand $" + InstInputsCheck.begin()->first +
-             " occurs in pattern but not in operands list!");
+    I.error("Input operand $" + InstInputsCheck.begin()->first +
 
   TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>(
-      I->getRecord(), ResultNodeOperands,
-      GetNumNodeResults(I->getRecord(), *this));
+      I.getRecord(), ResultNodeOperands,
+      GetNumNodeResults(I.getRecord(), *this));
   // Copy fully inferred output node types to instruction result pattern.
   for (unsigned i = 0; i != NumResults; ++i) {
     assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled");
     ResultPattern->setType(i, ResNodes[i]->getExtType(0));
   }
 
+  // FIXME: Assume only the first tree is the pattern. The others are clobber
+  // nodes.
+  TreePatternNodePtr Pattern = I.getTree(0);
+  TreePatternNodePtr SrcPattern;
+  if (Pattern->getOperator()->getName() == "set") {
+    SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
+  } else{
+    // Not a set (store or something?)
+    SrcPattern = Pattern;
+  }
+
   // Create and insert the instruction.
   // FIXME: InstImpResults should not be part of DAGInstruction.
-  Record *R = I->getRecord();
-  DAGInstruction &TheInst =
-      DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R),
-                       std::forward_as_tuple(std::move(I), Results, Operands,
-                                             InstImpResults)).first->second;
-
-  // Use a temporary tree pattern to infer all types and make sure that the
-  // constructed result is correct.  This depends on the instruction already
-  // being inserted into the DAGInsts map.
-  TreePattern Temp(TheInst.getPattern()->getRecord(), ResultPattern, false,
-                   *this);
-  Temp.InferAllTypes(&TheInst.getPattern()->getNamedNodesMap());
+  Record *R = I.getRecord();
+                   std::forward_as_tuple(Results, Operands, InstImpResults,
+                                         SrcPattern, ResultPattern));
 
-  TheInst.setResultPattern(Temp.getOnlyTree());
-
-  return TheInst;
+  LLVM_DEBUG(I.dump());
 }
 
 /// ParseInstructions - Parse all of the instructions, inlining and resolving
 /// any fragments involved.  This populates the Instructions list with fully
 /// resolved instructions.
 void CodeGenDAGPatterns::ParseInstructions() {
   std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
 
if (!LI || LI->empty() || hasNullFragReference(LI)) {
         for (unsigned j = InstInfo.Operands.NumDefs,
                e = InstInfo.Operands.size(); j < e; ++j)
           Operands.push_back(InstInfo.Operands[j].Rec);
       }
 
       // Create and insert the instruction.
       std::vector<Record*> ImpResults;
       Instructions.insert(std::make_pair(Instr,
-                          DAGInstruction(nullptr, Results, Operands, ImpResults)));
+                            DAGInstruction(Results, Operands, ImpResults)));
       continue;  // no pattern.
     }
 
     CodeGenInstruction &CGI = Target.getInstruction(Instr);
-    const DAGInstruction &DI = parseInstructionPattern(CGI, LI, Instructions);
-
-    (void)DI;
-    LLVM_DEBUG(DI.getPattern()->dump());
+    parseInstructionPattern(CGI, LI, Instructions);
   }
 
   // If we can, convert the instructions to be patterns that are matched!
   for (auto &Entry : Instructions) {
+    Record *Instr = Entry.first;
     DAGInstruction &TheInst = Entry.second;
-    TreePattern *I = TheInst.getPattern();
-    if (!I) continue;  // No pattern.
+    TreePatternNodePtr SrcPattern = TheInst.getSrcPattern();
+    TreePatternNodePtr ResultPattern = TheInst.getResultPattern();
 
-    if (PatternRewriter)
-      PatternRewriter(I);
-    // FIXME: Assume only the first tree is the pattern. The others are clobber
-    // nodes.
-    TreePatternNodePtr Pattern = I->getTree(0);
-    TreePatternNodePtr SrcPattern;
-    if (Pattern->getOperator()->getName() == "set") {
-      SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
-    } else{
-      // Not a set (store or something?)
-      SrcPattern = Pattern;
+    if (SrcPattern && ResultPattern) {
+      TreePattern Pattern(Instr, SrcPattern, true, *this);
+      TreePattern Result(Instr, ResultPattern, false, *this);
+      ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults());
     }
-
-    Record *Instr = Entry.first;
-    ListInit *Preds = Instr->getValueAsListInit("Predicates");
-    int Complexity = Instr->getValueAsInt("AddedComplexity");
-    AddPatternToMatch(
-        I,
-        PatternToMatch(Instr, makePredList(Preds), SrcPattern,
-                       TheInst.getResultPattern(), TheInst.getImpResults(),
-                       Complexity, Instr->getID()));
   }
 }
 
 typedef std::pair<TreePatternNode *, unsigned> NameRecord;
 
 static void FindNames(TreePatternNode *P,
                       std::map<std::string, NameRecord> &Names,
                       TreePattern *PatternTop) {
void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,
 
   PatternsToMatch.push_back(PTM);
 }
 
 void CodeGenDAGPatterns::InferInstructionFlags() {
   ArrayRef<const CodeGenInstruction*> Instructions =
     Target.getInstructionsByEnumValue();
 
-  // First try to infer flags from the primary instruction pattern, if any.
-  SmallVector<CodeGenInstruction*, 8> Revisit;
   unsigned Errors = 0;
-  for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
-    CodeGenInstruction &InstInfo =
-      const_cast<CodeGenInstruction &>(*Instructions[i]);
-
-    // Get the primary instruction pattern.
-    const TreePattern *Pattern = getInstruction(InstInfo.TheDef).getPattern();
-    if (!Pattern) {
-      if (InstInfo.hasUndefFlags())
-        Revisit.push_back(&InstInfo);
-      continue;
-    }
-    InstAnalyzer PatInfo(*this);
-    PatInfo.Analyze(Pattern);
-    Errors += InferFromPattern(InstInfo, PatInfo, InstInfo.TheDef);
-  }
 
-  // Second, look for single-instruction patterns defined outside the
-  // instruction.
+  // Try to infer flags from all patterns in PatternToMatch.  These include
+  // both the primary instruction patterns (which always come first) and
+  // patterns defined outside the instruction.
   for (const PatternToMatch &PTM : ptms()) {
     // We can only infer from single-instruction patterns, otherwise we won't
     // know which instruction should get the flags.
     SmallVector<Record*, 8> PatInstrs;
     getInstructionsInTree(PTM.getDstPattern(), PatInstrs);
     if (PatInstrs.size() != 1)
       continue;
 
     // Get the single instruction.
     CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());
 
     // Only infer properties from the first pattern. We'll verify the others.
     if (InstInfo.InferredFrom)
       continue;
 
     InstAnalyzer PatInfo(*this);
     PatInfo.Analyze(PTM);
     Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());
   }
 
   if (Errors)
     PrintFatalError("pattern conflicts");
 
-  // Revisit instructions with undefined flags and no pattern.
+  // If requested by the target, guess any undefined properties.
   if (Target.guessInstructionProperties()) {
-    for (CodeGenInstruction *InstInfo : Revisit) {
+    for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
+      CodeGenInstruction *InstInfo =
+        const_cast<CodeGenInstruction *>(Instructions[i]);
       if (InstInfo->InferredFrom)
         continue;
       // The mayLoad and mayStore flags default to false.
       // Conservatively assume hasSideEffects if it wasn't explicit.
       if (InstInfo->hasSideEffects_Unset)
         InstInfo->hasSideEffects = true;
     }
     return;
   }
 
   // Complain about any flags that are still undefined.
-  for (CodeGenInstruction *InstInfo : Revisit) {
+  for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
+    CodeGenInstruction *InstInfo =
+      const_cast<CodeGenInstruction *>(Instructions[i]);
     if (InstInfo->InferredFrom)
       continue;
     if (InstInfo->hasSideEffects_Unset)
       PrintError(InstInfo->TheDef->getLoc(),
                  "Can't infer hasSideEffects from patterns");
     if (InstInfo->mayStore_Unset)
       PrintError(InstInfo->TheDef->getLoc(),
                  "Can't infer mayStore from patterns");
for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) {
     // Otherwise, force its type to an arbitrary choice.
     if (TI.forceArbitrary(N->getExtType(i)))
       return true;
   }
 
   return false;
 }
 
-void CodeGenDAGPatterns::ParsePatterns() {
-  std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
-
-  for (Record *CurPattern : Patterns) {
-    DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
-
-    // If the pattern references the null_frag, there's nothing to do.
-    if (hasNullFragReference(Tree))
-      continue;
+void CodeGenDAGPatterns::ParseOnePattern(Record *TheDef,
+       TreePattern &Pattern, TreePattern &Result,
+       const std::vector<Record *> &InstImpResults) {
 
-    TreePattern Pattern(CurPattern, Tree, true, *this);
-
-    // Inline pattern fragments into it.
-    Pattern.InlinePatternFragments();
-
-    ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
-    if (LI->empty()) continue;  // no pattern.
-
-    // Parse the instruction.
-    TreePattern Result(CurPattern, LI, false, *this);
-
-    // Inline pattern fragments into it.
-    Result.InlinePatternFragments();
+  // Inline pattern fragments and expand multiple alternatives.
 
-    if (Result.getNumTrees() != 1)
-      Result.error("Cannot handle instructions producing instructions "
-                   "with temporaries yet!");
+    Result.error("Cannot use multi-alternative fragments in result pattern!");
 
-    bool IterateInference;
-    bool InferredAllPatternTypes, InferredAllResultTypes;
-    do {
-      // Infer as many types as possible.  If we cannot infer all of them, we
-      // can never do anything with this pattern: report it to the user.
-      InferredAllPatternTypes =
-          Pattern.InferAllTypes(&Pattern.getNamedNodesMap());
+  // Infer types.
 
-      // Infer as many types as possible.  If we cannot infer all of them, we
-      // can never do anything with this pattern: report it to the user.
-      InferredAllResultTypes =
-          Result.InferAllTypes(&Pattern.getNamedNodesMap());
 
-      IterateInference = false;
 
-      // Apply the type of the result to the source pattern.  This helps us
-      // resolve cases where the input type is known to be a pointer type (which
-      // is considered resolved), but the result knows it needs to be 32- or
-      // 64-bits.  Infer the other way for good measure.
-      for (unsigned i = 0, e = std::min(Result.getTree(0)->getNumTypes(),
-                                        Pattern.getTree(0)->getNumTypes());
-           i != e; ++i) {
-        IterateInference = Pattern.getTree(0)->UpdateNodeType(
-            i, Result.getTree(0)->getExtType(i), Result);
-        IterateInference |= Result.getTree(0)->UpdateNodeType(
-            i, Pattern.getTree(0)->getExtType(i), Result);
+    for (auto T : Pattern.getTrees())
+      for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(),
+                                        T->getNumTypes());
+        IterateInference |= T->UpdateNodeType(
+            i, Result.getOnlyTree()->getExtType(i), Result);
+        IterateInference |= Result.getOnlyTree()->UpdateNodeType(
+            i, T->getExtType(i), Result);
       }
 
-      // If our iteration has converged and the input pattern's types are fully
-      // resolved but the result pattern is not fully resolved, we may have a
-      // situation where we have two instructions in the result pattern and
-      // the instructions require a common register class, but don't care about
-      // what actual MVT is used.  This is actually a bug in our modelling:
-      // output patterns should have register classes, not MVTs.
-      //
-      // In any case, to handle this, we just go through and disambiguate some
-      // arbitrary types to the result pattern's nodes.
-      if (!IterateInference && InferredAllPatternTypes &&
-          !InferredAllResultTypes)
-        IterateInference =
-            ForceArbitraryInstResultType(Result.getTree(0).get(), Result);
-    } while (IterateInference);
 
-    // Verify that we inferred enough types that we can do something with the
-    // pattern and result.  If these fire the user has to add type casts.
-    if (!InferredAllPatternTypes)
-      Pattern.error("Could not infer all types in pattern!");
-    if (!InferredAllResultTypes) {
-      Pattern.dump();
-      Result.error("Could not infer all types in pattern result!");
-    }
 
-    // Validate that the input pattern is correct.
-    std::map<std::string, TreePatternNodePtr> InstInputs;
-    std::map<std::string, TreePatternNodePtr> InstResults;
-    std::vector<Record*> InstImpResults;
-    for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
-      FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
-                                  InstResults, InstImpResults);
-
-    // Promote the xform function to be an explicit node if set.
-    const TreePatternNodePtr &DstPattern = Result.getOnlyTree();
-    std::vector<TreePatternNodePtr> ResultNodeOperands;
-    for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) {
-      TreePatternNodePtr OpNode = DstPattern->getChildShared(ii);
-      if (Record *Xform = OpNode->getTransformFn()) {
-        OpNode->setTransformFn(nullptr);
-        std::vector<TreePatternNodePtr> Children;
-        Children.push_back(OpNode);
-        OpNode = std::make_shared<TreePatternNode>(Xform, Children,
-                                                   OpNode->getNumTypes());
-      }
-      ResultNodeOperands.push_back(OpNode);
-    }
 
-    TreePatternNodePtr DstShared =
-        DstPattern->isLeaf()
-            ? DstPattern
-            : std::make_shared<TreePatternNode>(DstPattern->getOperator(),
-                                                ResultNodeOperands,
-                                                DstPattern->getNumTypes());
 
-    for (unsigned i = 0, e = Result.getOnlyTree()->getNumTypes(); i != e; ++i)
-      DstShared->setType(i, Result.getOnlyTree()->getExtType(i));
 
-    TreePattern Temp(Result.getRecord(), DstShared, false, *this);
-    Temp.InferAllTypes();
 
-    // A pattern may end up with an "impossible" type, i.e. a situation
-    // where all types have been eliminated for some node in this pattern.
-    // This could occur for intrinsics that only make sense for a specific
-    // value type, and use a specific register class. If, for some mode,
-    // that register class does not accept that type, the type inference
-    // will lead to a contradiction, which is not an error however, but
-    // a sign that this pattern will simply never match.
-    if (Pattern.getTree(0)->hasPossibleType() &&
-        Temp.getOnlyTree()->hasPossibleType()) {
-      ListInit *Preds = CurPattern->getValueAsListInit("Predicates");
-      int Complexity = CurPattern->getValueAsInt("AddedComplexity");
-      if (PatternRewriter)
-        PatternRewriter(&Pattern);
+  ListInit *Preds = TheDef->getValueAsListInit("Predicates");
+  int Complexity = TheDef->getValueAsInt("AddedComplexity");
+
+  if (PatternRewriter)
+    PatternRewriter(&Pattern);
+
+  if (Temp.getOnlyTree()->hasPossibleType())
+    for (auto T : Pattern.getTrees())
+      if (T->hasPossibleType())
         AddPatternToMatch(&Pattern,
-                        PatternToMatch(CurPattern, makePredList(Preds),
-                                       Pattern.getTree(0), Temp.getOnlyTree(),
-                                       std::move(InstImpResults), Complexity,
-                                       CurPattern->getID()));
-    }
+                          PatternToMatch(TheDef, makePredList(Preds),
+                                         T, Temp.getOnlyTree(),
+                                         InstImpResults, Complexity,
+                                         TheDef->getID()));
+
+void CodeGenDAGPatterns::ParsePatterns() {
+  std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
+
+  for (Record *CurPattern : Patterns) {
+    DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
+
+    // If the pattern references the null_frag, there's nothing to do.
+    if (hasNullFragReference(Tree))
+      continue;
+
+    TreePattern Pattern(CurPattern, Tree, true, *this);
+
+    ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
+    if (LI->empty()) continue;  // no pattern.
+
+    // Parse the instruction.
+    TreePattern Result(CurPattern, LI, false, *this);
+
+    if (Result.getNumTrees() != 1)
+      Result.error("Cannot handle instructions producing instructions "
+                   "with temporaries yet!");
+
+    // Validate that the input pattern is correct.
+    std::map<std::string, TreePatternNodePtr> InstInputs;
+    std::map<std::string, TreePatternNodePtr> InstResults;
+    std::vector<Record*> InstImpResults;
+    for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
+      FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
+                                  InstResults, InstImpResults);
+
+    ParseOnePattern(CurPattern, Pattern, Result, InstImpResults);
   }
 }
 
 static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {
   for (const TypeSetByHwMode &VTS : N->getExtTypes())
     for (const auto &I : VTS)
       Modes.insert(I.first);
 

utils/TableGen/CodeGenInstruction.h

public:
     bool isCodeGenOnly : 1;
     bool isPseudo : 1;
     bool isRegSequence : 1;
     bool isExtractSubreg : 1;
     bool isInsertSubreg : 1;
     bool isConvergent : 1;
     bool hasNoSchedulingInfo : 1;
     bool FastISelShouldIgnore : 1;
+    bool hasChain : 1;
+    bool hasChain_Inferred : 1;
 
     std::string DeprecatedReason;
     bool HasComplexDeprecationPredicate;
 
     /// Are there any undefined flags?
     bool hasUndefFlags() const {
       return mayLoad_Unset || mayStore_Unset || hasSideEffects_Unset;
     }

utils/TableGen/CodeGenInstruction.cpp

CodeGenInstruction::CodeGenInstruction(Record *R)
   isAsCheapAsAMove = R->getValueAsBit("isAsCheapAsAMove");
   hasExtraSrcRegAllocReq = R->getValueAsBit("hasExtraSrcRegAllocReq");
   hasExtraDefRegAllocReq = R->getValueAsBit("hasExtraDefRegAllocReq");
   isCodeGenOnly = R->getValueAsBit("isCodeGenOnly");
   isPseudo = R->getValueAsBit("isPseudo");
   ImplicitDefs = R->getValueAsListOfDefs("Defs");
   ImplicitUses = R->getValueAsListOfDefs("Uses");
 
+  // This flag is only inferred from the pattern.
+  hasChain = false;
+  hasChain_Inferred = false;
+
   // Parse Constraints.
   ParseConstraints(R->getValueAsString("Constraints"), Operands);
 
   // Parse the DisableEncoding field.
   Operands.ProcessDisableEncoding(R->getValueAsString("DisableEncoding"));
 
   // First check for a ComplexDeprecationPredicate.
   if (R->getValue("ComplexDeprecationPredicate")) {

utils/TableGen/DAGISelEmitter.cpp

bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {
     if (LHSCost < RHSCost) return true;
     if (LHSCost > RHSCost) return false;
 
     unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP);
     unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP);
     if (LHSPatSize < RHSPatSize) return true;
     if (LHSPatSize > RHSPatSize) return false;
 
-    // Sort based on the UID of the pattern, giving us a deterministic ordering
-    // if all other sorting conditions fail.
-    assert(LHS == RHS || LHS->ID != RHS->ID);
+    // Sort based on the UID of the pattern, to reflect source order.
+    // Note that this is not guaranteed to be unique, since a single source
+    // pattern may have been resolved into multiple match patterns due to
+    // alternative fragments.  To ensure deterministic output, always use
+    // std::stable_sort with this predicate.
     return LHS->ID < RHS->ID;
   }
 };
 } // End anonymous namespace
 
 
 void DAGISelEmitter::run(raw_ostream &OS) {
   emitSourceFileHeader("DAG Instruction Selector for the " +
void DAGISelEmitter::run(raw_ostream &OS) {
   // Add all the patterns to a temporary list so we can sort them.
   std::vector<const PatternToMatch*> Patterns;
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
        I != E; ++I)
     Patterns.push_back(&*I);
 
   // We want to process the matches in order of minimal cost.  Sort the patterns
   // so the least cost one is at the start.
-  llvm::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP));
+  std::stable_sort(Patterns.begin(), Patterns.end(),
+                   PatternSortingPredicate(CGP));
 
 
   // Convert each variant of each pattern into a Matcher.
   std::vector<Matcher*> PatternMatchers;
   for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
     for (unsigned Variant = 0; ; ++Variant) {
       if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP))
         PatternMatchers.push_back(M);

utils/TableGen/DAGISelMatcherGen.cpp

private:
     // Result Code Generation.
     unsigned getNamedArgumentSlot(StringRef Name) {
       unsigned VarMapEntry = VariableMap[Name];
       assert(VarMapEntry != 0 &&
              "Variable referenced but not defined and not caught earlier!");
       return VarMapEntry-1;
     }
 
-    /// GetInstPatternNode - Get the pattern for an instruction.
-    const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins,
-                                              const TreePatternNode *N);
-
     void EmitResultOperand(const TreePatternNode *N,
                            SmallVectorImpl<unsigned> &ResultOps);
     void EmitResultOfNamedOperand(const TreePatternNode *N,
                                   SmallVectorImpl<unsigned> &ResultOps);
     void EmitResultLeafAsOperand(const TreePatternNode *N,
                                  SmallVectorImpl<unsigned> &ResultOps);
     void EmitResultInstructionAsOperand(const TreePatternNode *N,
                                         SmallVectorImpl<unsigned> &ResultOps);
if (Def->isSubClassOf("SubRegIndex")) {
       return;
     }
   }
 
   errs() << "unhandled leaf node: \n";
   N->dump();
 }
 
-/// GetInstPatternNode - Get the pattern for an instruction.
-///
-const TreePatternNode *MatcherGen::
-GetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) {
-  const TreePattern *InstPat = Inst.getPattern();
-
-  // FIXME2?: Assume actual pattern comes before "implicit".
-  TreePatternNode *InstPatNode;
-  if (InstPat)
-    InstPatNode = InstPat->getTree(0).get();
-  else if (/*isRoot*/ N == Pattern.getDstPattern())
-    InstPatNode = Pattern.getSrcPattern();
-  else
-    return nullptr;
-
-  if (InstPatNode && !InstPatNode->isLeaf() &&
-      InstPatNode->getOperator()->getName() == "set")
-    InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1);
-
-  return InstPatNode;
-}
-
 static bool
 mayInstNodeLoadOrStore(const TreePatternNode *N,
                        const CodeGenDAGPatterns &CGP) {
   Record *Op = N->getOperator();
   const CodeGenTarget &CGT = CGP.getTargetInfo();
   CodeGenInstruction &II = CGT.getInstruction(Op);
   return II.mayLoad || II.mayStore;
 }

 void MatcherGen::
 EmitResultInstructionAsOperand(const TreePatternNode *N,
                                SmallVectorImpl<unsigned> &OutputOps) {
   Record *Op = N->getOperator();
   const CodeGenTarget &CGT = CGP.getTargetInfo();
   CodeGenInstruction &II = CGT.getInstruction(Op);
   const DAGInstruction &Inst = CGP.getInstruction(Op);
 
-  // If we can, get the pattern for the instruction we're generating. We derive
-  // a variety of information from this pattern, such as whether it has a chain.
-  //
-  // FIXME2: This is extremely dubious for several reasons, not the least of
-  // which it gives special status to instructions with patterns that Pat<>
-  // nodes can't duplicate.
-  const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N);
-
-  // NodeHasChain - Whether the instruction node we're creating takes chains.
-  bool NodeHasChain = InstPatNode &&
-                      InstPatNode->TreeHasProperty(SDNPHasChain, CGP);
-
-  // Instructions which load and store from memory should have a chain,
-  // regardless of whether they happen to have an internal pattern saying so.
-  if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP)
-      && (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||
-          II.hasSideEffects))
-      NodeHasChain = true;
-
   bool isRoot = N == Pattern.getDstPattern();
 
   // TreeHasOutGlue - True if this tree has glue.
   bool TreeHasInGlue = false, TreeHasOutGlue = false;
   if (isRoot) {
     const TreePatternNode *SrcPat = Pattern.getSrcPattern();
     TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) ||
                     SrcPat->TreeHasProperty(SDNPInGlue, CGP);
unsigned NumNodesThatLoadOrStore =
       numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP);
     bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) &&
                                    NumNodesThatLoadOrStore == 1;
     NodeHasMemRefs =
       NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) ||
                                              NumNodesThatLoadOrStore != 1));
   }
 
+  // Determine whether we need to attach a chain to this node.
+  bool NodeHasChain = false;
+  if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP)) {
+    // For some instructions, we were able to infer from the pattern whether
+    // they should have a chain.  Otherwise, attach the chain to the root.
+    //
+    // FIXME2: This is extremely dubious for several reasons, not the least of
+    // which it gives special status to instructions with patterns that Pat<>
+    // nodes can't duplicate.
+    if (II.hasChain_Inferred)
+      NodeHasChain = II.hasChain;
+    else
+      NodeHasChain = isRoot;
+    // Instructions which load and store from memory should have a chain,
+    // regardless of whether they happen to have a pattern saying so.
+    if (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||
+        II.hasSideEffects)
+      NodeHasChain = true;
+  }
+
   assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) &&
          "Node has no result");
 
   AddMatcher(new EmitNodeMatcher(II.Namespace.str()+"::"+II.TheDef->getName().str(),
                                  ResultVTs, InstOps,
                                  NodeHasChain, TreeHasInGlue, TreeHasOutGlue,
                                  NodeHasMemRefs, NumFixedArityOperands,
                                  NextRecordedOperandNo));