llvm.org GIT mirror llvm / release_70 utils / TableGen / DAGISelMatcherGen.cpp
release_70

Tree @release_70 (Download .tar.gz)

DAGISelMatcherGen.cpp @release_70raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "DAGISelMatcher.h"
#include "CodeGenDAGPatterns.h"
#include "CodeGenRegisters.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include <utility>
using namespace llvm;


/// getRegisterValueType - Look up and return the ValueType of the specified
/// register. If the register is a member of multiple register classes which
/// have different associated types, return MVT::Other.
static MVT::SimpleValueType getRegisterValueType(Record *R,
                                                 const CodeGenTarget &T) {
  bool FoundRC = false;
  MVT::SimpleValueType VT = MVT::Other;
  const CodeGenRegister *Reg = T.getRegBank().getReg(R);

  for (const auto &RC : T.getRegBank().getRegClasses()) {
    if (!RC.contains(Reg))
      continue;

    if (!FoundRC) {
      FoundRC = true;
      ValueTypeByHwMode VVT = RC.getValueTypeNum(0);
      if (VVT.isSimple())
        VT = VVT.getSimple().SimpleTy;
      continue;
    }

    // If this occurs in multiple register classes, they all have to agree.
#ifndef NDEBUG
    ValueTypeByHwMode T = RC.getValueTypeNum(0);
    assert((!T.isSimple() || T.getSimple().SimpleTy == VT) &&
           "ValueType mismatch between register classes for this register");
#endif
  }
  return VT;
}


namespace {
  class MatcherGen {
    const PatternToMatch &Pattern;
    const CodeGenDAGPatterns &CGP;

    /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
    /// out with all of the types removed.  This allows us to insert type checks
    /// as we scan the tree.
    TreePatternNodePtr PatWithNoTypes;

    /// VariableMap - A map from variable names ('$dst') to the recorded operand
    /// number that they were captured as.  These are biased by 1 to make
    /// insertion easier.
    StringMap<unsigned> VariableMap;

    /// This maintains the recorded operand number that OPC_CheckComplexPattern
    /// drops each sub-operand into. We don't want to insert these into
    /// VariableMap because that leads to identity checking if they are
    /// encountered multiple times. Biased by 1 like VariableMap for
    /// consistency.
    StringMap<unsigned> NamedComplexPatternOperands;

    /// NextRecordedOperandNo - As we emit opcodes to record matched values in
    /// the RecordedNodes array, this keeps track of which slot will be next to
    /// record into.
    unsigned NextRecordedOperandNo;

    /// MatchedChainNodes - This maintains the position in the recorded nodes
    /// array of all of the recorded input nodes that have chains.
    SmallVector<unsigned, 2> MatchedChainNodes;

    /// MatchedComplexPatterns - This maintains a list of all of the
    /// ComplexPatterns that we need to check. The second element of each pair
    /// is the recorded operand number of the input node.
    SmallVector<std::pair<const TreePatternNode*,
                          unsigned>, 2> MatchedComplexPatterns;

    /// PhysRegInputs - List list has an entry for each explicitly specified
    /// physreg input to the pattern.  The first elt is the Register node, the
    /// second is the recorded slot number the input pattern match saved it in.
    SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs;

    /// Matcher - This is the top level of the generated matcher, the result.
    Matcher *TheMatcher;

    /// CurPredicate - As we emit matcher nodes, this points to the latest check
    /// which should have future checks stuck into its Next position.
    Matcher *CurPredicate;
  public:
    MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);

    bool EmitMatcherCode(unsigned Variant);
    void EmitResultCode();

    Matcher *GetMatcher() const { return TheMatcher; }
  private:
    void AddMatcher(Matcher *NewNode);
    void InferPossibleTypes(unsigned ForceMode);

    // Matcher Generation.
    void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes,
                       unsigned ForceMode);
    void EmitLeafMatchCode(const TreePatternNode *N);
    void EmitOperatorMatchCode(const TreePatternNode *N,
                               TreePatternNode *NodeNoTypes,
                               unsigned ForceMode);

    /// If this is the first time a node with unique identifier Name has been
    /// seen, record it. Otherwise, emit a check to make sure this is the same
    /// node. Returns true if this is the first encounter.
    bool recordUniqueNode(const std::string &Name);

    // 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;
    }

    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);
    void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N,
                                        SmallVectorImpl<unsigned> &ResultOps);
    };

} // end anon namespace.

MatcherGen::MatcherGen(const PatternToMatch &pattern,
                       const CodeGenDAGPatterns &cgp)
: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
  TheMatcher(nullptr), CurPredicate(nullptr) {
  // We need to produce the matcher tree for the patterns source pattern.  To do
  // this we need to match the structure as well as the types.  To do the type
  // matching, we want to figure out the fewest number of type checks we need to
  // emit.  For example, if there is only one integer type supported by a
  // target, there should be no type comparisons at all for integer patterns!
  //
  // To figure out the fewest number of type checks needed, clone the pattern,
  // remove the types, then perform type inference on the pattern as a whole.
  // If there are unresolved types, emit an explicit check for those types,
  // apply the type to the tree, then rerun type inference.  Iterate until all
  // types are resolved.
  //
  PatWithNoTypes = Pattern.getSrcPattern()->clone();
  PatWithNoTypes->RemoveAllTypes();

  // If there are types that are manifestly known, infer them.
  InferPossibleTypes(Pattern.ForceMode);
}

/// InferPossibleTypes - As we emit the pattern, we end up generating type
/// checks and applying them to the 'PatWithNoTypes' tree.  As we do this, we
/// want to propagate implied types as far throughout the tree as possible so
/// that we avoid doing redundant type checks.  This does the type propagation.
void MatcherGen::InferPossibleTypes(unsigned ForceMode) {
  // TP - Get *SOME* tree pattern, we don't care which.  It is only used for
  // diagnostics, which we know are impossible at this point.
  TreePattern &TP = *CGP.pf_begin()->second;
  TP.getInfer().CodeGen = true;
  TP.getInfer().ForceMode = ForceMode;

  bool MadeChange = true;
  while (MadeChange)
    MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
                                              true/*Ignore reg constraints*/);
}


/// AddMatcher - Add a matcher node to the current graph we're building.
void MatcherGen::AddMatcher(Matcher *NewNode) {
  if (CurPredicate)
    CurPredicate->setNext(NewNode);
  else
    TheMatcher = NewNode;
  CurPredicate = NewNode;
}


//===----------------------------------------------------------------------===//
// Pattern Match Generation
//===----------------------------------------------------------------------===//

/// EmitLeafMatchCode - Generate matching code for leaf nodes.
void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
  assert(N->isLeaf() && "Not a leaf?");

  // Direct match against an integer constant.
  if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) {
    // If this is the root of the dag we're matching, we emit a redundant opcode
    // check to ensure that this gets folded into the normal top-level
    // OpcodeSwitch.
    if (N == Pattern.getSrcPattern()) {
      const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm"));
      AddMatcher(new CheckOpcodeMatcher(NI));
    }

    return AddMatcher(new CheckIntegerMatcher(II->getValue()));
  }

  // An UnsetInit represents a named node without any constraints.
  if (isa<UnsetInit>(N->getLeafValue())) {
    assert(N->hasName() && "Unnamed ? leaf");
    return;
  }

  DefInit *DI = dyn_cast<DefInit>(N->getLeafValue());
  if (!DI) {
    errs() << "Unknown leaf kind: " << *N << "\n";
    abort();
  }

  Record *LeafRec = DI->getDef();

  // A ValueType leaf node can represent a register when named, or itself when
  // unnamed.
  if (LeafRec->isSubClassOf("ValueType")) {
    // A named ValueType leaf always matches: (add i32:$a, i32:$b).
    if (N->hasName())
      return;
    // An unnamed ValueType as in (sext_inreg GPR:$foo, i8).
    return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName()));
  }

  if (// Handle register references.  Nothing to do here, they always match.
      LeafRec->isSubClassOf("RegisterClass") ||
      LeafRec->isSubClassOf("RegisterOperand") ||
      LeafRec->isSubClassOf("PointerLikeRegClass") ||
      LeafRec->isSubClassOf("SubRegIndex") ||
      // Place holder for SRCVALUE nodes. Nothing to do here.
      LeafRec->getName() == "srcvalue")
    return;

  // If we have a physreg reference like (mul gpr:$src, EAX) then we need to
  // record the register
  if (LeafRec->isSubClassOf("Register")) {
    AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName().str(),
                                 NextRecordedOperandNo));
    PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++));
    return;
  }

  if (LeafRec->isSubClassOf("CondCode"))
    return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName()));

  if (LeafRec->isSubClassOf("ComplexPattern")) {
    // We can't model ComplexPattern uses that don't have their name taken yet.
    // The OPC_CheckComplexPattern operation implicitly records the results.
    if (N->getName().empty()) {
      std::string S;
      raw_string_ostream OS(S);
      OS << "We expect complex pattern uses to have names: " << *N;
      PrintFatalError(OS.str());
    }

    // Remember this ComplexPattern so that we can emit it after all the other
    // structural matches are done.
    unsigned InputOperand = VariableMap[N->getName()] - 1;
    MatchedComplexPatterns.push_back(std::make_pair(N, InputOperand));
    return;
  }

  errs() << "Unknown leaf kind: " << *N << "\n";
  abort();
}

void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
                                       TreePatternNode *NodeNoTypes,
                                       unsigned ForceMode) {
  assert(!N->isLeaf() && "Not an operator?");

  if (N->getOperator()->isSubClassOf("ComplexPattern")) {
    // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
    // "MY_PAT:op1:op2". We should already have validated that the uses are
    // consistent.
    std::string PatternName = N->getOperator()->getName();
    for (unsigned i = 0; i < N->getNumChildren(); ++i) {
      PatternName += ":";
      PatternName += N->getChild(i)->getName();
    }

    if (recordUniqueNode(PatternName)) {
      auto NodeAndOpNum = std::make_pair(N, NextRecordedOperandNo - 1);
      MatchedComplexPatterns.push_back(NodeAndOpNum);
    }

    return;
  }

  const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());

  // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
  // a constant without a predicate fn that has more than one bit set, handle
  // this as a special case.  This is usually for targets that have special
  // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
  // handling stuff).  Using these instructions is often far more efficient
  // than materializing the constant.  Unfortunately, both the instcombiner
  // and the dag combiner can often infer that bits are dead, and thus drop
  // them from the mask in the dag.  For example, it might turn 'AND X, 255'
  // into 'AND X, 254' if it knows the low bit is set.  Emit code that checks
  // to handle this.
  if ((N->getOperator()->getName() == "and" ||
       N->getOperator()->getName() == "or") &&
      N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() &&
      N->getPredicateFns().empty()) {
    if (IntInit *II = dyn_cast<IntInit>(N->getChild(1)->getLeafValue())) {
      if (!isPowerOf2_32(II->getValue())) {  // Don't bother with single bits.
        // If this is at the root of the pattern, we emit a redundant
        // CheckOpcode so that the following checks get factored properly under
        // a single opcode check.
        if (N == Pattern.getSrcPattern())
          AddMatcher(new CheckOpcodeMatcher(CInfo));

        // Emit the CheckAndImm/CheckOrImm node.
        if (N->getOperator()->getName() == "and")
          AddMatcher(new CheckAndImmMatcher(II->getValue()));
        else
          AddMatcher(new CheckOrImmMatcher(II->getValue()));

        // Match the LHS of the AND as appropriate.
        AddMatcher(new MoveChildMatcher(0));
        EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0), ForceMode);
        AddMatcher(new MoveParentMatcher());
        return;
      }
    }
  }

  // Check that the current opcode lines up.
  AddMatcher(new CheckOpcodeMatcher(CInfo));

  // If this node has memory references (i.e. is a load or store), tell the
  // interpreter to capture them in the memref array.
  if (N->NodeHasProperty(SDNPMemOperand, CGP))
    AddMatcher(new RecordMemRefMatcher());

  // If this node has a chain, then the chain is operand #0 is the SDNode, and
  // the child numbers of the node are all offset by one.
  unsigned OpNo = 0;
  if (N->NodeHasProperty(SDNPHasChain, CGP)) {
    // Record the node and remember it in our chained nodes list.
    AddMatcher(new RecordMatcher("'" + N->getOperator()->getName().str() +
                                         "' chained node",
                                 NextRecordedOperandNo));
    // Remember all of the input chains our pattern will match.
    MatchedChainNodes.push_back(NextRecordedOperandNo++);

    // Don't look at the input chain when matching the tree pattern to the
    // SDNode.
    OpNo = 1;

    // If this node is not the root and the subtree underneath it produces a
    // chain, then the result of matching the node is also produce a chain.
    // Beyond that, this means that we're also folding (at least) the root node
    // into the node that produce the chain (for example, matching
    // "(add reg, (load ptr))" as a add_with_memory on X86).  This is
    // problematic, if the 'reg' node also uses the load (say, its chain).
    // Graphically:
    //
    //         [LD]
    //         ^  ^
    //         |  \                              DAG's like cheese.
    //        /    |
    //       /    [YY]
    //       |     ^
    //      [XX]--/
    //
    // It would be invalid to fold XX and LD.  In this case, folding the two
    // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG'
    // To prevent this, we emit a dynamic check for legality before allowing
    // this to be folded.
    //
    const TreePatternNode *Root = Pattern.getSrcPattern();
    if (N != Root) {                             // Not the root of the pattern.
      // If there is a node between the root and this node, then we definitely
      // need to emit the check.
      bool NeedCheck = !Root->hasChild(N);

      // If it *is* an immediate child of the root, we can still need a check if
      // the root SDNode has multiple inputs.  For us, this means that it is an
      // intrinsic, has multiple operands, or has other inputs like chain or
      // glue).
      if (!NeedCheck) {
        const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator());
        NeedCheck =
          Root->getOperator() == CGP.get_intrinsic_void_sdnode() ||
          Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() ||
          Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() ||
          PInfo.getNumOperands() > 1 ||
          PInfo.hasProperty(SDNPHasChain) ||
          PInfo.hasProperty(SDNPInGlue) ||
          PInfo.hasProperty(SDNPOptInGlue);
      }

      if (NeedCheck)
        AddMatcher(new CheckFoldableChainNodeMatcher());
    }
  }

  // If this node has an output glue and isn't the root, remember it.
  if (N->NodeHasProperty(SDNPOutGlue, CGP) &&
      N != Pattern.getSrcPattern()) {
    // TODO: This redundantly records nodes with both glues and chains.

    // Record the node and remember it in our chained nodes list.
    AddMatcher(new RecordMatcher("'" + N->getOperator()->getName().str() +
                                         "' glue output node",
                                 NextRecordedOperandNo));
  }

  // If this node is known to have an input glue or if it *might* have an input
  // glue, capture it as the glue input of the pattern.
  if (N->NodeHasProperty(SDNPOptInGlue, CGP) ||
      N->NodeHasProperty(SDNPInGlue, CGP))
    AddMatcher(new CaptureGlueInputMatcher());

  for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
    // Get the code suitable for matching this child.  Move to the child, check
    // it then move back to the parent.
    AddMatcher(new MoveChildMatcher(OpNo));
    EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i), ForceMode);
    AddMatcher(new MoveParentMatcher());
  }
}

bool MatcherGen::recordUniqueNode(const std::string &Name) {
  unsigned &VarMapEntry = VariableMap[Name];
  if (VarMapEntry == 0) {
    // If it is a named node, we must emit a 'Record' opcode.
    AddMatcher(new RecordMatcher("$" + Name, NextRecordedOperandNo));
    VarMapEntry = ++NextRecordedOperandNo;
    return true;
  }

  // If we get here, this is a second reference to a specific name.  Since
  // we already have checked that the first reference is valid, we don't
  // have to recursively match it, just check that it's the same as the
  // previously named thing.
  AddMatcher(new CheckSameMatcher(VarMapEntry-1));
  return false;
}

void MatcherGen::EmitMatchCode(const TreePatternNode *N,
                               TreePatternNode *NodeNoTypes,
                               unsigned ForceMode) {
  // If N and NodeNoTypes don't agree on a type, then this is a case where we
  // need to do a type check.  Emit the check, apply the type to NodeNoTypes and
  // reinfer any correlated types.
  SmallVector<unsigned, 2> ResultsToTypeCheck;

  for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) {
    if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue;
    NodeNoTypes->setType(i, N->getExtType(i));
    InferPossibleTypes(ForceMode);
    ResultsToTypeCheck.push_back(i);
  }

  // If this node has a name associated with it, capture it in VariableMap. If
  // we already saw this in the pattern, emit code to verify dagness.
  if (!N->getName().empty())
    if (!recordUniqueNode(N->getName()))
      return;

  if (N->isLeaf())
    EmitLeafMatchCode(N);
  else
    EmitOperatorMatchCode(N, NodeNoTypes, ForceMode);

  // If there are node predicates for this node, generate their checks.
  for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
    AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i]));

  for (unsigned i = 0, e = ResultsToTypeCheck.size(); i != e; ++i)
    AddMatcher(new CheckTypeMatcher(N->getSimpleType(ResultsToTypeCheck[i]),
                                    ResultsToTypeCheck[i]));
}

/// EmitMatcherCode - Generate the code that matches the predicate of this
/// pattern for the specified Variant.  If the variant is invalid this returns
/// true and does not generate code, if it is valid, it returns false.
bool MatcherGen::EmitMatcherCode(unsigned Variant) {
  // If the root of the pattern is a ComplexPattern and if it is specified to
  // match some number of root opcodes, these are considered to be our variants.
  // Depending on which variant we're generating code for, emit the root opcode
  // check.
  if (const ComplexPattern *CP =
                   Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) {
    const std::vector<Record*> &OpNodes = CP->getRootNodes();
    assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match");
    if (Variant >= OpNodes.size()) return true;

    AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant])));
  } else {
    if (Variant != 0) return true;
  }

  // Emit the matcher for the pattern structure and types.
  EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes.get(),
                Pattern.ForceMode);

  // If the pattern has a predicate on it (e.g. only enabled when a subtarget
  // feature is around, do the check).
  if (!Pattern.getPredicateCheck().empty())
    AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck()));

  // Now that we've completed the structural type match, emit any ComplexPattern
  // checks (e.g. addrmode matches).  We emit this after the structural match
  // because they are generally more expensive to evaluate and more difficult to
  // factor.
  for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) {
    auto N = MatchedComplexPatterns[i].first;

    // Remember where the results of this match get stuck.
    if (N->isLeaf()) {
      NamedComplexPatternOperands[N->getName()] = NextRecordedOperandNo + 1;
    } else {
      unsigned CurOp = NextRecordedOperandNo;
      for (unsigned i = 0; i < N->getNumChildren(); ++i) {
        NamedComplexPatternOperands[N->getChild(i)->getName()] = CurOp + 1;
        CurOp += N->getChild(i)->getNumMIResults(CGP);
      }
    }

    // Get the slot we recorded the value in from the name on the node.
    unsigned RecNodeEntry = MatchedComplexPatterns[i].second;

    const ComplexPattern &CP = *N->getComplexPatternInfo(CGP);

    // Emit a CheckComplexPat operation, which does the match (aborting if it
    // fails) and pushes the matched operands onto the recorded nodes list.
    AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry,
                                          N->getName(), NextRecordedOperandNo));

    // Record the right number of operands.
    NextRecordedOperandNo += CP.getNumOperands();
    if (CP.hasProperty(SDNPHasChain)) {
      // If the complex pattern has a chain, then we need to keep track of the
      // fact that we just recorded a chain input.  The chain input will be
      // matched as the last operand of the predicate if it was successful.
      ++NextRecordedOperandNo; // Chained node operand.

      // It is the last operand recorded.
      assert(NextRecordedOperandNo > 1 &&
             "Should have recorded input/result chains at least!");
      MatchedChainNodes.push_back(NextRecordedOperandNo-1);
    }

    // TODO: Complex patterns can't have output glues, if they did, we'd want
    // to record them.
  }

  return false;
}


//===----------------------------------------------------------------------===//
// Node Result Generation
//===----------------------------------------------------------------------===//

void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N,
                                          SmallVectorImpl<unsigned> &ResultOps){
  assert(!N->getName().empty() && "Operand not named!");

  if (unsigned SlotNo = NamedComplexPatternOperands[N->getName()]) {
    // Complex operands have already been completely selected, just find the
    // right slot ant add the arguments directly.
    for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
      ResultOps.push_back(SlotNo - 1 + i);

    return;
  }

  unsigned SlotNo = getNamedArgumentSlot(N->getName());

  // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target
  // version of the immediate so that it doesn't get selected due to some other
  // node use.
  if (!N->isLeaf()) {
    StringRef OperatorName = N->getOperator()->getName();
    if (OperatorName == "imm" || OperatorName == "fpimm") {
      AddMatcher(new EmitConvertToTargetMatcher(SlotNo));
      ResultOps.push_back(NextRecordedOperandNo++);
      return;
    }
  }

  for (unsigned i = 0; i < N->getNumMIResults(CGP); ++i)
    ResultOps.push_back(SlotNo + i);
}

void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N,
                                         SmallVectorImpl<unsigned> &ResultOps) {
  assert(N->isLeaf() && "Must be a leaf");

  if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) {
    AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getSimpleType(0)));
    ResultOps.push_back(NextRecordedOperandNo++);
    return;
  }

  // If this is an explicit register reference, handle it.
  if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) {
    Record *Def = DI->getDef();
    if (Def->isSubClassOf("Register")) {
      const CodeGenRegister *Reg =
        CGP.getTargetInfo().getRegBank().getReg(Def);
      AddMatcher(new EmitRegisterMatcher(Reg, N->getSimpleType(0)));
      ResultOps.push_back(NextRecordedOperandNo++);
      return;
    }

    if (Def->getName() == "zero_reg") {
      AddMatcher(new EmitRegisterMatcher(nullptr, N->getSimpleType(0)));
      ResultOps.push_back(NextRecordedOperandNo++);
      return;
    }

    // Handle a reference to a register class. This is used
    // in COPY_TO_SUBREG instructions.
    if (Def->isSubClassOf("RegisterOperand"))
      Def = Def->getValueAsDef("RegClass");
    if (Def->isSubClassOf("RegisterClass")) {
      std::string Value = getQualifiedName(Def) + "RegClassID";
      AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32));
      ResultOps.push_back(NextRecordedOperandNo++);
      return;
    }

    // Handle a subregister index. This is used for INSERT_SUBREG etc.
    if (Def->isSubClassOf("SubRegIndex")) {
      std::string Value = getQualifiedName(Def);
      AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32));
      ResultOps.push_back(NextRecordedOperandNo++);
      return;
    }
  }

  errs() << "unhandled leaf node: \n";
  N->dump();
}

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;
}

static unsigned
numNodesThatMayLoadOrStore(const TreePatternNode *N,
                           const CodeGenDAGPatterns &CGP) {
  if (N->isLeaf())
    return 0;

  Record *OpRec = N->getOperator();
  if (!OpRec->isSubClassOf("Instruction"))
    return 0;

  unsigned Count = 0;
  if (mayInstNodeLoadOrStore(N, CGP))
    ++Count;

  for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
    Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP);

  return Count;
}

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);

  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);

    // FIXME2: this is checking the entire pattern, not just the node in
    // question, doing this just for the root seems like a total hack.
    TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP);
  }

  // NumResults - This is the number of results produced by the instruction in
  // the "outs" list.
  unsigned NumResults = Inst.getNumResults();

  // Number of operands we know the output instruction must have. If it is
  // variadic, we could have more operands.
  unsigned NumFixedOperands = II.Operands.size();

  SmallVector<unsigned, 8> InstOps;

  // Loop over all of the fixed operands of the instruction pattern, emitting
  // code to fill them all in. The node 'N' usually has number children equal to
  // the number of input operands of the instruction.  However, in cases where
  // there are predicate operands for an instruction, we need to fill in the
  // 'execute always' values. Match up the node operands to the instruction
  // operands to do this.
  unsigned ChildNo = 0;
  for (unsigned InstOpNo = NumResults, e = NumFixedOperands;
       InstOpNo != e; ++InstOpNo) {
    // Determine what to emit for this operand.
    Record *OperandNode = II.Operands[InstOpNo].Rec;
    if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
        !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) {
      // This is a predicate or optional def operand; emit the
      // 'default ops' operands.
      const DAGDefaultOperand &DefaultOp
        = CGP.getDefaultOperand(OperandNode);
      for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i)
        EmitResultOperand(DefaultOp.DefaultOps[i].get(), InstOps);
      continue;
    }

    // Otherwise this is a normal operand or a predicate operand without
    // 'execute always'; emit it.

    // For operands with multiple sub-operands we may need to emit
    // multiple child patterns to cover them all.  However, ComplexPattern
    // children may themselves emit multiple MI operands.
    unsigned NumSubOps = 1;
    if (OperandNode->isSubClassOf("Operand")) {
      DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");
      if (unsigned NumArgs = MIOpInfo->getNumArgs())
        NumSubOps = NumArgs;
    }

    unsigned FinalNumOps = InstOps.size() + NumSubOps;
    while (InstOps.size() < FinalNumOps) {
      const TreePatternNode *Child = N->getChild(ChildNo);
      unsigned BeforeAddingNumOps = InstOps.size();
      EmitResultOperand(Child, InstOps);
      assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands");

      // If the operand is an instruction and it produced multiple results, just
      // take the first one.
      if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction"))
        InstOps.resize(BeforeAddingNumOps+1);

      ++ChildNo;
    }
  }

  // If this is a variadic output instruction (i.e. REG_SEQUENCE), we can't
  // expand suboperands, use default operands, or other features determined from
  // the CodeGenInstruction after the fixed operands, which were handled
  // above. Emit the remaining instructions implicitly added by the use for
  // variable_ops.
  if (II.Operands.isVariadic) {
    for (unsigned I = ChildNo, E = N->getNumChildren(); I < E; ++I)
      EmitResultOperand(N->getChild(I), InstOps);
  }

  // If this node has input glue or explicitly specified input physregs, we
  // need to add chained and glued copyfromreg nodes and materialize the glue
  // input.
  if (isRoot && !PhysRegInputs.empty()) {
    // Emit all of the CopyToReg nodes for the input physical registers.  These
    // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src).
    for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i)
      AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second,
                                          PhysRegInputs[i].first));
    // Even if the node has no other glue inputs, the resultant node must be
    // glued to the CopyFromReg nodes we just generated.
    TreeHasInGlue = true;
  }

  // Result order: node results, chain, glue

  // Determine the result types.
  SmallVector<MVT::SimpleValueType, 4> ResultVTs;
  for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i)
    ResultVTs.push_back(N->getSimpleType(i));

  // If this is the root instruction of a pattern that has physical registers in
  // its result pattern, add output VTs for them.  For example, X86 has:
  //   (set AL, (mul ...))
  // This also handles implicit results like:
  //   (implicit EFLAGS)
  if (isRoot && !Pattern.getDstRegs().empty()) {
    // If the root came from an implicit def in the instruction handling stuff,
    // don't re-add it.
    Record *HandledReg = nullptr;
    if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)
      HandledReg = II.ImplicitDefs[0];

    for (Record *Reg : Pattern.getDstRegs()) {
      if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue;
      ResultVTs.push_back(getRegisterValueType(Reg, CGT));
    }
  }

  // If this is the root of the pattern and the pattern we're matching includes
  // a node that is variadic, mark the generated node as variadic so that it
  // gets the excess operands from the input DAG.
  int NumFixedArityOperands = -1;
  if (isRoot &&
      Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))
    NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren();

  // If this is the root node and multiple matched nodes in the input pattern
  // have MemRefs in them, have the interpreter collect them and plop them onto
  // this node. If there is just one node with MemRefs, leave them on that node
  // even if it is not the root.
  //
  // FIXME3: This is actively incorrect for result patterns with multiple
  // memory-referencing instructions.
  bool PatternHasMemOperands =
    Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP);

  bool NodeHasMemRefs = false;
  if (PatternHasMemOperands) {
    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));

  // The non-chain and non-glue results of the newly emitted node get recorded.
  for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) {
    if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break;
    OutputOps.push_back(NextRecordedOperandNo++);
  }
}

void MatcherGen::
EmitResultSDNodeXFormAsOperand(const TreePatternNode *N,
                               SmallVectorImpl<unsigned> &ResultOps) {
  assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?");

  // Emit the operand.
  SmallVector<unsigned, 8> InputOps;

  // FIXME2: Could easily generalize this to support multiple inputs and outputs
  // to the SDNodeXForm.  For now we just support one input and one output like
  // the old instruction selector.
  assert(N->getNumChildren() == 1);
  EmitResultOperand(N->getChild(0), InputOps);

  // The input currently must have produced exactly one result.
  assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm");

  AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator()));
  ResultOps.push_back(NextRecordedOperandNo++);
}

void MatcherGen::EmitResultOperand(const TreePatternNode *N,
                                   SmallVectorImpl<unsigned> &ResultOps) {
  // This is something selected from the pattern we matched.
  if (!N->getName().empty())
    return EmitResultOfNamedOperand(N, ResultOps);

  if (N->isLeaf())
    return EmitResultLeafAsOperand(N, ResultOps);

  Record *OpRec = N->getOperator();
  if (OpRec->isSubClassOf("Instruction"))
    return EmitResultInstructionAsOperand(N, ResultOps);
  if (OpRec->isSubClassOf("SDNodeXForm"))
    return EmitResultSDNodeXFormAsOperand(N, ResultOps);
  errs() << "Unknown result node to emit code for: " << *N << '\n';
  PrintFatalError("Unknown node in result pattern!");
}

void MatcherGen::EmitResultCode() {
  // Patterns that match nodes with (potentially multiple) chain inputs have to
  // merge them together into a token factor.  This informs the generated code
  // what all the chained nodes are.
  if (!MatchedChainNodes.empty())
    AddMatcher(new EmitMergeInputChainsMatcher(MatchedChainNodes));

  // Codegen the root of the result pattern, capturing the resulting values.
  SmallVector<unsigned, 8> Ops;
  EmitResultOperand(Pattern.getDstPattern(), Ops);

  // At this point, we have however many values the result pattern produces.
  // However, the input pattern might not need all of these.  If there are
  // excess values at the end (such as implicit defs of condition codes etc)
  // just lop them off.  This doesn't need to worry about glue or chains, just
  // explicit results.
  //
  unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes();

  // If the pattern also has (implicit) results, count them as well.
  if (!Pattern.getDstRegs().empty()) {
    // If the root came from an implicit def in the instruction handling stuff,
    // don't re-add it.
    Record *HandledReg = nullptr;
    const TreePatternNode *DstPat = Pattern.getDstPattern();
    if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){
      const CodeGenTarget &CGT = CGP.getTargetInfo();
      CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator());

      if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)
        HandledReg = II.ImplicitDefs[0];
    }

    for (Record *Reg : Pattern.getDstRegs()) {
      if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue;
      ++NumSrcResults;
    }
  }

  assert(Ops.size() >= NumSrcResults && "Didn't provide enough results");
  Ops.resize(NumSrcResults);

  AddMatcher(new CompleteMatchMatcher(Ops, Pattern));
}


/// ConvertPatternToMatcher - Create the matcher for the specified pattern with
/// the specified variant.  If the variant number is invalid, this returns null.
Matcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern,
                                       unsigned Variant,
                                       const CodeGenDAGPatterns &CGP) {
  MatcherGen Gen(Pattern, CGP);

  // Generate the code for the matcher.
  if (Gen.EmitMatcherCode(Variant))
    return nullptr;

  // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence.
  // FIXME2: Split result code out to another table, and make the matcher end
  // with an "Emit <index>" command.  This allows result generation stuff to be
  // shared and factored?

  // If the match succeeds, then we generate Pattern.
  Gen.EmitResultCode();

  // Unconditional match.
  return Gen.GetMatcher();
}