llvm.org GIT mirror llvm / testing utils / TableGen / CodeGenDAGPatterns.h
testing

Tree @testing (Download .tar.gz)

CodeGenDAGPatterns.h @testingraw · 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
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file declares the CodeGenDAGPatterns class, which is used to read and
// represent the patterns present in a .td file for instructions.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
#define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H

#include "CodeGenHwModes.h"
#include "CodeGenIntrinsics.h"
#include "CodeGenTarget.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <array>
#include <map>
#include <set>
#include <vector>

namespace llvm {

class Record;
class Init;
class ListInit;
class DagInit;
class SDNodeInfo;
class TreePattern;
class TreePatternNode;
class CodeGenDAGPatterns;
class ComplexPattern;

/// This represents a set of MVTs. Since the underlying type for the MVT
/// is uint8_t, there are at most 256 values. To reduce the number of memory
/// allocations and deallocations, represent the set as a sequence of bits.
/// To reduce the allocations even further, make MachineValueTypeSet own
/// the storage and use std::array as the bit container.
struct MachineValueTypeSet {
  static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
                             uint8_t>::value,
                "Change uint8_t here to the SimpleValueType's type");
  static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1;
  using WordType = uint64_t;
  static unsigned constexpr WordWidth = CHAR_BIT*sizeof(WordType);
  static unsigned constexpr NumWords = Capacity/WordWidth;
  static_assert(NumWords*WordWidth == Capacity,
                "Capacity should be a multiple of WordWidth");

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  MachineValueTypeSet() {
    clear();
  }

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  unsigned size() const {
    unsigned Count = 0;
    for (WordType W : Words)
      Count += countPopulation(W);
    return Count;
  }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  void clear() {
    std::memset(Words.data(), 0, NumWords*sizeof(WordType));
  }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  bool empty() const {
    for (WordType W : Words)
      if (W != 0)
        return false;
    return true;
  }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  unsigned count(MVT T) const {
    return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
  }
  std::pair<MachineValueTypeSet&,bool> insert(MVT T) {
    bool V = count(T.SimpleTy);
    Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
    return {*this, V};
  }
  MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
    for (unsigned i = 0; i != NumWords; ++i)
      Words[i] |= S.Words[i];
    return *this;
  }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  void erase(MVT T) {
    Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
  }

  struct const_iterator {
    // Some implementations of the C++ library require these traits to be
    // defined.
    using iterator_category = std::forward_iterator_tag;
    using value_type = MVT;
    using difference_type = ptrdiff_t;
    using pointer = const MVT*;
    using reference = const MVT&;

    LLVM_ATTRIBUTE_ALWAYS_INLINE
    MVT operator*() const {
      assert(Pos != Capacity);
      return MVT::SimpleValueType(Pos);
    }
    LLVM_ATTRIBUTE_ALWAYS_INLINE
    const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
      Pos = End ? Capacity : find_from_pos(0);
    }
    LLVM_ATTRIBUTE_ALWAYS_INLINE
    const_iterator &operator++() {
      assert(Pos != Capacity);
      Pos = find_from_pos(Pos+1);
      return *this;
    }

    LLVM_ATTRIBUTE_ALWAYS_INLINE
    bool operator==(const const_iterator &It) const {
      return Set == It.Set && Pos == It.Pos;
    }
    LLVM_ATTRIBUTE_ALWAYS_INLINE
    bool operator!=(const const_iterator &It) const {
      return !operator==(It);
    }

  private:
    unsigned find_from_pos(unsigned P) const {
      unsigned SkipWords = P / WordWidth;
      unsigned SkipBits = P % WordWidth;
      unsigned Count = SkipWords * WordWidth;

      // If P is in the middle of a word, process it manually here, because
      // the trailing bits need to be masked off to use findFirstSet.
      if (SkipBits != 0) {
        WordType W = Set->Words[SkipWords];
        W &= maskLeadingOnes<WordType>(WordWidth-SkipBits);
        if (W != 0)
          return Count + findFirstSet(W);
        Count += WordWidth;
        SkipWords++;
      }

      for (unsigned i = SkipWords; i != NumWords; ++i) {
        WordType W = Set->Words[i];
        if (W != 0)
          return Count + findFirstSet(W);
        Count += WordWidth;
      }
      return Capacity;
    }

    const MachineValueTypeSet *Set;
    unsigned Pos;
  };

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  const_iterator begin() const { return const_iterator(this, false); }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  const_iterator end()   const { return const_iterator(this, true); }

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  bool operator==(const MachineValueTypeSet &S) const {
    return Words == S.Words;
  }
  LLVM_ATTRIBUTE_ALWAYS_INLINE
  bool operator!=(const MachineValueTypeSet &S) const {
    return !operator==(S);
  }

private:
  friend struct const_iterator;
  std::array<WordType,NumWords> Words;
};

struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
  using SetType = MachineValueTypeSet;

  TypeSetByHwMode() = default;
  TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
  TypeSetByHwMode(MVT::SimpleValueType VT)
    : TypeSetByHwMode(ValueTypeByHwMode(VT)) {}
  TypeSetByHwMode(ValueTypeByHwMode VT)
    : TypeSetByHwMode(ArrayRef<ValueTypeByHwMode>(&VT, 1)) {}
  TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList);

  SetType &getOrCreate(unsigned Mode) {
    if (hasMode(Mode))
      return get(Mode);
    return Map.insert({Mode,SetType()}).first->second;
  }

  bool isValueTypeByHwMode(bool AllowEmpty) const;
  ValueTypeByHwMode getValueTypeByHwMode() const;

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  bool isMachineValueType() const {
    return isDefaultOnly() && Map.begin()->second.size() == 1;
  }

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  MVT getMachineValueType() const {
    assert(isMachineValueType());
    return *Map.begin()->second.begin();
  }

  bool isPossible() const;

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  bool isDefaultOnly() const {
    return Map.size() == 1 && Map.begin()->first == DefaultMode;
  }

  bool insert(const ValueTypeByHwMode &VVT);
  bool constrain(const TypeSetByHwMode &VTS);
  template <typename Predicate> bool constrain(Predicate P);
  template <typename Predicate>
  bool assign_if(const TypeSetByHwMode &VTS, Predicate P);

  void writeToStream(raw_ostream &OS) const;
  static void writeToStream(const SetType &S, raw_ostream &OS);

  bool operator==(const TypeSetByHwMode &VTS) const;
  bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }

  void dump() const;
  void validate() const;

private:
  /// Intersect two sets. Return true if anything has changed.
  bool intersect(SetType &Out, const SetType &In);
};

raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T);

struct TypeInfer {
  TypeInfer(TreePattern &T) : TP(T), ForceMode(0) {}

  bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const {
    return VTS.isValueTypeByHwMode(AllowEmpty);
  }
  ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS,
                                bool AllowEmpty) const {
    assert(VTS.isValueTypeByHwMode(AllowEmpty));
    return VTS.getValueTypeByHwMode();
  }

  /// The protocol in the following functions (Merge*, force*, Enforce*,
  /// expand*) is to return "true" if a change has been made, "false"
  /// otherwise.

  bool MergeInTypeInfo(TypeSetByHwMode &Out, const TypeSetByHwMode &In);
  bool MergeInTypeInfo(TypeSetByHwMode &Out, MVT::SimpleValueType InVT) {
    return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
  }
  bool MergeInTypeInfo(TypeSetByHwMode &Out, ValueTypeByHwMode InVT) {
    return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
  }

  /// Reduce the set \p Out to have at most one element for each mode.
  bool forceArbitrary(TypeSetByHwMode &Out);

  /// The following four functions ensure that upon return the set \p Out
  /// will only contain types of the specified kind: integer, floating-point,
  /// scalar, or vector.
  /// If \p Out is empty, all legal types of the specified kind will be added
  /// to it. Otherwise, all types that are not of the specified kind will be
  /// removed from \p Out.
  bool EnforceInteger(TypeSetByHwMode &Out);
  bool EnforceFloatingPoint(TypeSetByHwMode &Out);
  bool EnforceScalar(TypeSetByHwMode &Out);
  bool EnforceVector(TypeSetByHwMode &Out);

  /// If \p Out is empty, fill it with all legal types. Otherwise, leave it
  /// unchanged.
  bool EnforceAny(TypeSetByHwMode &Out);
  /// Make sure that for each type in \p Small, there exists a larger type
  /// in \p Big.
  bool EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big);
  /// 1. Ensure that for each type T in \p Vec, T is a vector type, and that
  ///    for each type U in \p Elem, U is a scalar type.
  /// 2. Ensure that for each (scalar) type U in \p Elem, there exists a
  ///    (vector) type T in \p Vec, such that U is the element type of T.
  bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Elem);
  bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
                              const ValueTypeByHwMode &VVT);
  /// Ensure that for each type T in \p Sub, T is a vector type, and there
  /// exists a type U in \p Vec such that U is a vector type with the same
  /// element type as T and at least as many elements as T.
  bool EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
                                    TypeSetByHwMode &Sub);
  /// 1. Ensure that \p V has a scalar type iff \p W has a scalar type.
  /// 2. Ensure that for each vector type T in \p V, there exists a vector
  ///    type U in \p W, such that T and U have the same number of elements.
  /// 3. Ensure that for each vector type U in \p W, there exists a vector
  ///    type T in \p V, such that T and U have the same number of elements
  ///    (reverse of 2).
  bool EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W);
  /// 1. Ensure that for each type T in \p A, there exists a type U in \p B,
  ///    such that T and U have equal size in bits.
  /// 2. Ensure that for each type U in \p B, there exists a type T in \p A
  ///    such that T and U have equal size in bits (reverse of 1).
  bool EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B);

  /// For each overloaded type (i.e. of form *Any), replace it with the
  /// corresponding subset of legal, specific types.
  void expandOverloads(TypeSetByHwMode &VTS);
  void expandOverloads(TypeSetByHwMode::SetType &Out,
                       const TypeSetByHwMode::SetType &Legal);

  struct ValidateOnExit {
    ValidateOnExit(TypeSetByHwMode &T) : VTS(T) {}
    ~ValidateOnExit() { VTS.validate(); }
    TypeSetByHwMode &VTS;
  };

  TreePattern &TP;
  unsigned ForceMode;     // Mode to use when set.
  bool CodeGen = false;   // Set during generation of matcher code.

private:
  TypeSetByHwMode getLegalTypes();

  /// Cached legal types.
  bool LegalTypesCached = false;
  TypeSetByHwMode::SetType LegalCache = {};
};

/// Set type used to track multiply used variables in patterns
typedef StringSet<> MultipleUseVarSet;

/// SDTypeConstraint - This is a discriminated union of constraints,
/// corresponding to the SDTypeConstraint tablegen class in Target.td.
struct SDTypeConstraint {
  SDTypeConstraint(Record *R, const CodeGenHwModes &CGH);

  unsigned OperandNo;   // The operand # this constraint applies to.
  enum {
    SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs,
    SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec,
    SDTCisSubVecOfVec, SDTCVecEltisVT, SDTCisSameNumEltsAs, SDTCisSameSizeAs
  } ConstraintType;

  union {   // The discriminated union.
    struct {
      unsigned OtherOperandNum;
    } SDTCisSameAs_Info;
    struct {
      unsigned OtherOperandNum;
    } SDTCisVTSmallerThanOp_Info;
    struct {
      unsigned BigOperandNum;
    } SDTCisOpSmallerThanOp_Info;
    struct {
      unsigned OtherOperandNum;
    } SDTCisEltOfVec_Info;
    struct {
      unsigned OtherOperandNum;
    } SDTCisSubVecOfVec_Info;
    struct {
      unsigned OtherOperandNum;
    } SDTCisSameNumEltsAs_Info;
    struct {
      unsigned OtherOperandNum;
    } SDTCisSameSizeAs_Info;
  } x;

  // The VT for SDTCisVT and SDTCVecEltisVT.
  // Must not be in the union because it has a non-trivial destructor.
  ValueTypeByHwMode VVT;

  /// ApplyTypeConstraint - Given a node in a pattern, apply this type
  /// constraint to the nodes operands.  This returns true if it makes a
  /// change, false otherwise.  If a type contradiction is found, an error
  /// is flagged.
  bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo,
                           TreePattern &TP) const;
};

/// SDNodeInfo - One of these records is created for each SDNode instance in
/// the target .td file.  This represents the various dag nodes we will be
/// processing.
class SDNodeInfo {
  Record *Def;
  StringRef EnumName;
  StringRef SDClassName;
  unsigned Properties;
  unsigned NumResults;
  int NumOperands;
  std::vector<SDTypeConstraint> TypeConstraints;
public:
  // Parse the specified record.
  SDNodeInfo(Record *R, const CodeGenHwModes &CGH);

  unsigned getNumResults() const { return NumResults; }

  /// getNumOperands - This is the number of operands required or -1 if
  /// variadic.
  int getNumOperands() const { return NumOperands; }
  Record *getRecord() const { return Def; }
  StringRef getEnumName() const { return EnumName; }
  StringRef getSDClassName() const { return SDClassName; }

  const std::vector<SDTypeConstraint> &getTypeConstraints() const {
    return TypeConstraints;
  }

  /// getKnownType - If the type constraints on this node imply a fixed type
  /// (e.g. all stores return void, etc), then return it as an
  /// MVT::SimpleValueType.  Otherwise, return MVT::Other.
  MVT::SimpleValueType getKnownType(unsigned ResNo) const;

  /// hasProperty - Return true if this node has the specified property.
  ///
  bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); }

  /// ApplyTypeConstraints - Given a node in a pattern, apply the type
  /// constraints for this node to the operands of the node.  This returns
  /// true if it makes a change, false otherwise.  If a type contradiction is
  /// found, an error is flagged.
  bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const;
};

/// TreePredicateFn - This is an abstraction that represents the predicates on
/// a PatFrag node.  This is a simple one-word wrapper around a pointer to
/// provide nice accessors.
class TreePredicateFn {
  /// PatFragRec - This is the TreePattern for the PatFrag that we
  /// originally came from.
  TreePattern *PatFragRec;
public:
  /// TreePredicateFn constructor.  Here 'N' is a subclass of PatFrag.
  TreePredicateFn(TreePattern *N);


  TreePattern *getOrigPatFragRecord() const { return PatFragRec; }

  /// isAlwaysTrue - Return true if this is a noop predicate.
  bool isAlwaysTrue() const;

  bool isImmediatePattern() const { return hasImmCode(); }

  /// getImmediatePredicateCode - Return the code that evaluates this pattern if
  /// this is an immediate predicate.  It is an error to call this on a
  /// non-immediate pattern.
  std::string getImmediatePredicateCode() const {
    std::string Result = getImmCode();
    assert(!Result.empty() && "Isn't an immediate pattern!");
    return Result;
  }

  bool operator==(const TreePredicateFn &RHS) const {
    return PatFragRec == RHS.PatFragRec;
  }

  bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); }

  /// Return the name to use in the generated code to reference this, this is
  /// "Predicate_foo" if from a pattern fragment "foo".
  std::string getFnName() const;

  /// getCodeToRunOnSDNode - Return the code for the function body that
  /// evaluates this predicate.  The argument is expected to be in "Node",
  /// not N.  This handles casting and conversion to a concrete node type as
  /// appropriate.
  std::string getCodeToRunOnSDNode() const;

  /// Get the data type of the argument to getImmediatePredicateCode().
  StringRef getImmType() const;

  /// Get a string that describes the type returned by getImmType() but is
  /// usable as part of an identifier.
  StringRef getImmTypeIdentifier() const;

  // Is the desired predefined predicate for a load?
  bool isLoad() const;
  // Is the desired predefined predicate for a store?
  bool isStore() const;

  /// Is this predicate the predefined unindexed load predicate?
  /// Is this predicate the predefined unindexed store predicate?
  bool isUnindexed() const;
  /// Is this predicate the predefined non-extending load predicate?
  bool isNonExtLoad() const;
  /// Is this predicate the predefined any-extend load predicate?
  bool isAnyExtLoad() const;
  /// Is this predicate the predefined sign-extend load predicate?
  bool isSignExtLoad() const;
  /// Is this predicate the predefined zero-extend load predicate?
  bool isZeroExtLoad() const;
  /// Is this predicate the predefined non-truncating store predicate?
  bool isNonTruncStore() const;
  /// Is this predicate the predefined truncating store predicate?
  bool isTruncStore() const;

  /// If non-null, indicates that this predicate is a predefined memory VT
  /// predicate for a load/store and returns the ValueType record for the memory VT.
  Record *getMemoryVT() const;
  /// If non-null, indicates that this predicate is a predefined memory VT
  /// predicate (checking only the scalar type) for load/store and returns the
  /// ValueType record for the memory VT.
  Record *getScalarMemoryVT() const;

private:
  bool hasPredCode() const;
  bool hasImmCode() const;
  std::string getPredCode() const;
  std::string getImmCode() const;
  bool immCodeUsesAPInt() const;
  bool immCodeUsesAPFloat() const;

  bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const;
};


/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped
/// patterns), and as such should be ref counted.  We currently just leak all
/// TreePatternNode objects!
class TreePatternNode {
  /// The type of each node result.  Before and during type inference, each
  /// result may be a set of possible types.  After (successful) type inference,
  /// each is a single concrete type.
  std::vector<TypeSetByHwMode> Types;

  /// Operator - The Record for the operator if this is an interior node (not
  /// a leaf).
  Record *Operator;

  /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf.
  ///
  Init *Val;

  /// Name - The name given to this node with the :$foo notation.
  ///
  std::string Name;

  /// PredicateFns - The predicate functions to execute on this node to check
  /// for a match.  If this list is empty, no predicate is involved.
  std::vector<TreePredicateFn> PredicateFns;

  /// TransformFn - The transformation function to execute on this node before
  /// it can be substituted into the resulting instruction on a pattern match.
  Record *TransformFn;

  std::vector<TreePatternNode*> Children;
public:
  TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch,
                  unsigned NumResults)
    : Operator(Op), Val(nullptr), TransformFn(nullptr), Children(Ch) {
    Types.resize(NumResults);
  }
  TreePatternNode(Init *val, unsigned NumResults)    // leaf ctor
    : Operator(nullptr), Val(val), TransformFn(nullptr) {
    Types.resize(NumResults);
  }
  ~TreePatternNode();

  bool hasName() const { return !Name.empty(); }
  const std::string &getName() const { return Name; }
  void setName(StringRef N) { Name.assign(N.begin(), N.end()); }

  bool isLeaf() const { return Val != nullptr; }

  // Type accessors.
  unsigned getNumTypes() const { return Types.size(); }
  ValueTypeByHwMode getType(unsigned ResNo) const {
    return Types[ResNo].getValueTypeByHwMode();
  }
  const std::vector<TypeSetByHwMode> &getExtTypes() const { return Types; }
  const TypeSetByHwMode &getExtType(unsigned ResNo) const {
    return Types[ResNo];
  }
  TypeSetByHwMode &getExtType(unsigned ResNo) { return Types[ResNo]; }
  void setType(unsigned ResNo, const TypeSetByHwMode &T) { Types[ResNo] = T; }
  MVT::SimpleValueType getSimpleType(unsigned ResNo) const {
    return Types[ResNo].getMachineValueType().SimpleTy;
  }

  bool hasConcreteType(unsigned ResNo) const {
    return Types[ResNo].isValueTypeByHwMode(false);
  }
  bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const {
    return Types[ResNo].empty();
  }

  Init *getLeafValue() const { assert(isLeaf()); return Val; }
  Record *getOperator() const { assert(!isLeaf()); return Operator; }

  unsigned getNumChildren() const { return Children.size(); }
  TreePatternNode *getChild(unsigned N) const { return Children[N]; }
  void setChild(unsigned i, TreePatternNode *N) {
    Children[i] = N;
  }

  /// hasChild - Return true if N is any of our children.
  bool hasChild(const TreePatternNode *N) const {
    for (unsigned i = 0, e = Children.size(); i != e; ++i)
      if (Children[i] == N) return true;
    return false;
  }

  bool hasProperTypeByHwMode() const;
  bool hasPossibleType() const;
  bool setDefaultMode(unsigned Mode);

  bool hasAnyPredicate() const { return !PredicateFns.empty(); }

  const std::vector<TreePredicateFn> &getPredicateFns() const {
    return PredicateFns;
  }
  void clearPredicateFns() { PredicateFns.clear(); }
  void setPredicateFns(const std::vector<TreePredicateFn> &Fns) {
    assert(PredicateFns.empty() && "Overwriting non-empty predicate list!");
    PredicateFns = Fns;
  }
  void addPredicateFn(const TreePredicateFn &Fn) {
    assert(!Fn.isAlwaysTrue() && "Empty predicate string!");
    if (!is_contained(PredicateFns, Fn))
      PredicateFns.push_back(Fn);
  }

  Record *getTransformFn() const { return TransformFn; }
  void setTransformFn(Record *Fn) { TransformFn = Fn; }

  /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
  /// CodeGenIntrinsic information for it, otherwise return a null pointer.
  const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const;

  /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
  /// return the ComplexPattern information, otherwise return null.
  const ComplexPattern *
  getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const;

  /// Returns the number of MachineInstr operands that would be produced by this
  /// node if it mapped directly to an output Instruction's
  /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it
  /// for Operands; otherwise 1.
  unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const;

  /// NodeHasProperty - Return true if this node has the specified property.
  bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;

  /// TreeHasProperty - Return true if any node in this tree has the specified
  /// property.
  bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;

  /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is
  /// marked isCommutative.
  bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const;

  void print(raw_ostream &OS) const;
  void dump() const;

public:   // Higher level manipulation routines.

  /// clone - Return a new copy of this tree.
  ///
  TreePatternNode *clone() const;

  /// RemoveAllTypes - Recursively strip all the types of this tree.
  void RemoveAllTypes();

  /// isIsomorphicTo - Return true if this node is recursively isomorphic to
  /// the specified node.  For this comparison, all of the state of the node
  /// is considered, except for the assigned name.  Nodes with differing names
  /// that are otherwise identical are considered isomorphic.
  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,
                                          TreePatternNode*> &ArgMap);

  /// InlinePatternFragments - If this pattern refers to any pattern
  /// fragments, inline them into place, giving us a pattern without any
  /// PatFrag references.
  TreePatternNode *InlinePatternFragments(TreePattern &TP);

  /// 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
  /// error.  This returns true if any information was updated.
  ///
  bool UpdateNodeType(unsigned ResNo, const TypeSetByHwMode &InTy,
                      TreePattern &TP);
  bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy,
                      TreePattern &TP);
  bool UpdateNodeType(unsigned ResNo, ValueTypeByHwMode InTy,
                      TreePattern &TP);

  // Update node type with types inferred from an instruction operand or result
  // def from the ins/outs lists.
  // Return true if the type changed.
  bool UpdateNodeTypeFromInst(unsigned ResNo, Record *Operand, TreePattern &TP);

  /// ContainsUnresolvedType - Return true if this tree contains any
  /// unresolved types.
  bool ContainsUnresolvedType(TreePattern &TP) const;

  /// canPatternMatch - If it is impossible for this pattern to match on this
  /// target, fill in Reason and return false.  Otherwise, return true.
  bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP);
};

inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) {
  TPN.print(OS);
  return OS;
}


/// TreePattern - Represent a pattern, used for instructions, pattern
/// fragments, etc.
///
class TreePattern {
  /// Trees - The list of pattern trees which corresponds to this pattern.
  /// Note that PatFrag's only have a single tree.
  ///
  std::vector<TreePatternNode*> Trees;

  /// NamedNodes - This is all of the nodes that have names in the trees in this
  /// pattern.
  StringMap<SmallVector<TreePatternNode*,1> > NamedNodes;

  /// TheRecord - The actual TableGen record corresponding to this pattern.
  ///
  Record *TheRecord;

  /// Args - This is a list of all of the arguments to this pattern (for
  /// PatFrag patterns), which are the 'node' markers in this pattern.
  std::vector<std::string> Args;

  /// CDP - the top-level object coordinating this madness.
  ///
  CodeGenDAGPatterns &CDP;

  /// isInputPattern - True if this is an input pattern, something to match.
  /// False if this is an output pattern, something to emit.
  bool isInputPattern;

  /// hasError - True if the currently processed nodes have unresolvable types
  /// or other non-fatal errors
  bool HasError;

  /// It's important that the usage of operands in ComplexPatterns is
  /// consistent: each named operand can be defined by at most one
  /// ComplexPattern. This records the ComplexPattern instance and the operand
  /// number for each operand encountered in a ComplexPattern to aid in that
  /// check.
  StringMap<std::pair<Record *, unsigned>> ComplexPatternOperands;

  TypeInfer Infer;

public:

  /// TreePattern constructor - Parse the specified DagInits into the
  /// current record.
  TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
              CodeGenDAGPatterns &ise);
  TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
              CodeGenDAGPatterns &ise);
  TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput,
              CodeGenDAGPatterns &ise);

  /// getTrees - Return the tree patterns which corresponds to this pattern.
  ///
  const std::vector<TreePatternNode*> &getTrees() const { return Trees; }
  unsigned getNumTrees() const { return Trees.size(); }
  TreePatternNode *getTree(unsigned i) const { return Trees[i]; }
  TreePatternNode *getOnlyTree() const {
    assert(Trees.size() == 1 && "Doesn't have exactly one pattern!");
    return Trees[0];
  }

  const StringMap<SmallVector<TreePatternNode*,1> > &getNamedNodesMap() {
    if (NamedNodes.empty())
      ComputeNamedNodes();
    return NamedNodes;
  }

  /// getRecord - Return the actual TableGen record corresponding to this
  /// pattern.
  ///
  Record *getRecord() const { return TheRecord; }

  unsigned getNumArgs() const { return Args.size(); }
  const std::string &getArgName(unsigned i) const {
    assert(i < Args.size() && "Argument reference out of range!");
    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.
  void InlinePatternFragments() {
    for (unsigned i = 0, e = Trees.size(); i != e; ++i)
      Trees[i] = Trees[i]->InlinePatternFragments(*this);
  }

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

  /// error - If this is the first error in the current resolution step,
  /// print it and set the error flag.  Otherwise, continue silently.
  void error(const Twine &Msg);
  bool hasError() const {
    return HasError;
  }
  void resetError() {
    HasError = false;
  }

  TypeInfer &getInfer() { return Infer; }

  void print(raw_ostream &OS) const;
  void dump() const;

private:
  TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName);
  void ComputeNamedNodes();
  void ComputeNamedNodes(TreePatternNode *N);
};


inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
                                            const TypeSetByHwMode &InTy,
                                            TreePattern &TP) {
  TypeSetByHwMode VTS(InTy);
  TP.getInfer().expandOverloads(VTS);
  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
}

inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
                                            MVT::SimpleValueType InTy,
                                            TreePattern &TP) {
  TypeSetByHwMode VTS(InTy);
  TP.getInfer().expandOverloads(VTS);
  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
}

inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
                                            ValueTypeByHwMode InTy,
                                            TreePattern &TP) {
  TypeSetByHwMode VTS(InTy);
  TP.getInfer().expandOverloads(VTS);
  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
}


/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
/// that has a set ExecuteAlways / DefaultOps field.
struct DAGDefaultOperand {
  std::vector<TreePatternNode*> DefaultOps;
};

class DAGInstruction {
  TreePattern *Pattern;
  std::vector<Record*> Results;
  std::vector<Record*> Operands;
  std::vector<Record*> ImpResults;
  TreePatternNode *ResultPattern;
public:
  DAGInstruction(TreePattern *TP,
                 const std::vector<Record*> &results,
                 const std::vector<Record*> &operands,
                 const std::vector<Record*> &impresults)
    : Pattern(TP), Results(results), Operands(operands),
      ImpResults(impresults), ResultPattern(nullptr) {}

  TreePattern *getPattern() const { return Pattern; }
  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(TreePatternNode *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];
  }

  TreePatternNode *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
/// these strings are generated.
class Predicate {
public:
  Predicate(Record *R, bool C = true) : Def(R), IfCond(C), IsHwMode(false) {
    assert(R->isSubClassOf("Predicate") &&
           "Predicate objects should only be created for records derived"
           "from Predicate class");
  }
  Predicate(StringRef FS, bool C = true) : Def(nullptr), Features(FS.str()),
    IfCond(C), IsHwMode(true) {}

  /// Return a string which contains the C++ condition code that will serve
  /// as a predicate during instruction selection.
  std::string getCondString() const {
    // The string will excute in a subclass of SelectionDAGISel.
    // Cast to std::string explicitly to avoid ambiguity with StringRef.
    std::string C = IsHwMode
        ? std::string("MF->getSubtarget().checkFeatures(\"" + Features + "\")")
        : std::string(Def->getValueAsString("CondString"));
    return IfCond ? C : "!("+C+')';
  }
  bool operator==(const Predicate &P) const {
    return IfCond == P.IfCond && IsHwMode == P.IsHwMode && Def == P.Def;
  }
  bool operator<(const Predicate &P) const {
    if (IsHwMode != P.IsHwMode)
      return IsHwMode < P.IsHwMode;
    assert(!Def == !P.Def && "Inconsistency between Def and IsHwMode");
    if (IfCond != P.IfCond)
      return IfCond < P.IfCond;
    if (Def)
      return LessRecord()(Def, P.Def);
    return Features < P.Features;
  }
  Record *Def;            ///< Predicate definition from .td file, null for
                          ///< HW modes.
  std::string Features;   ///< Feature string for HW mode.
  bool IfCond;            ///< The boolean value that the condition has to
                          ///< evaluate to for this predicate to be true.
  bool IsHwMode;          ///< Does this predicate correspond to a HW mode?
};

/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
/// processed to produce isel.
class PatternToMatch {
public:
  PatternToMatch(Record *srcrecord, const std::vector<Predicate> &preds,
                 TreePatternNode *src, TreePatternNode *dst,
                 const std::vector<Record*> &dstregs,
                 int complexity, unsigned uid, unsigned setmode = 0)
    : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
      Predicates(preds), Dstregs(std::move(dstregs)),
      AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}

  PatternToMatch(Record *srcrecord, std::vector<Predicate> &&preds,
                 TreePatternNode *src, TreePatternNode *dst,
                 std::vector<Record*> &&dstregs,
                 int complexity, unsigned uid, unsigned setmode = 0)
    : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
      Predicates(preds), Dstregs(std::move(dstregs)),
      AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}

  Record          *SrcRecord;   // Originating Record for the pattern.
  TreePatternNode *SrcPattern;  // Source pattern to match.
  TreePatternNode *DstPattern;  // Resulting pattern.
  std::vector<Predicate> Predicates;  // Top level predicate conditions
                                      // to match.
  std::vector<Record*> Dstregs; // Physical register defs being matched.
  int              AddedComplexity; // Add to matching pattern complexity.
  unsigned         ID;          // Unique ID for the record.
  unsigned         ForceMode;   // Force this mode in type inference when set.

  Record          *getSrcRecord()  const { return SrcRecord; }
  TreePatternNode *getSrcPattern() const { return SrcPattern; }
  TreePatternNode *getDstPattern() const { return DstPattern; }
  const std::vector<Record*> &getDstRegs() const { return Dstregs; }
  int         getAddedComplexity() const { return AddedComplexity; }
  const std::vector<Predicate> &getPredicates() const { return Predicates; }

  std::string getPredicateCheck() const;

  /// Compute the complexity metric for the input pattern.  This roughly
  /// corresponds to the number of nodes that are covered.
  int getPatternComplexity(const CodeGenDAGPatterns &CGP) const;
};

class CodeGenDAGPatterns {
  RecordKeeper &Records;
  CodeGenTarget Target;
  CodeGenIntrinsicTable Intrinsics;
  CodeGenIntrinsicTable TgtIntrinsics;

  std::map<Record*, SDNodeInfo, LessRecordByID> SDNodes;
  std::map<Record*, std::pair<Record*, std::string>, LessRecordByID>
      SDNodeXForms;
  std::map<Record*, ComplexPattern, LessRecordByID> ComplexPatterns;
  std::map<Record *, std::unique_ptr<TreePattern>, LessRecordByID>
      PatternFragments;
  std::map<Record*, DAGDefaultOperand, LessRecordByID> DefaultOperands;
  std::map<Record*, DAGInstruction, LessRecordByID> Instructions;

  // Specific SDNode definitions:
  Record *intrinsic_void_sdnode;
  Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode;

  /// PatternsToMatch - All of the things we are matching on the DAG.  The first
  /// value is the pattern to match, the second pattern is the result to
  /// emit.
  std::vector<PatternToMatch> PatternsToMatch;

  TypeSetByHwMode LegalVTS;

public:
  CodeGenDAGPatterns(RecordKeeper &R);

  CodeGenTarget &getTargetInfo() { return Target; }
  const CodeGenTarget &getTargetInfo() const { return Target; }
  const TypeSetByHwMode &getLegalTypes() const { return LegalVTS; }

  Record *getSDNodeNamed(const std::string &Name) const;

  const SDNodeInfo &getSDNodeInfo(Record *R) const {
    auto F = SDNodes.find(R);
    assert(F != SDNodes.end() && "Unknown node!");
    return F->second;
  }

  // Node transformation lookups.
  typedef std::pair<Record*, std::string> NodeXForm;
  const NodeXForm &getSDNodeTransform(Record *R) const {
    auto F = SDNodeXForms.find(R);
    assert(F != SDNodeXForms.end() && "Invalid transform!");
    return F->second;
  }

  typedef std::map<Record*, NodeXForm, LessRecordByID>::const_iterator
          nx_iterator;
  nx_iterator nx_begin() const { return SDNodeXForms.begin(); }
  nx_iterator nx_end() const { return SDNodeXForms.end(); }


  const ComplexPattern &getComplexPattern(Record *R) const {
    auto F = ComplexPatterns.find(R);
    assert(F != ComplexPatterns.end() && "Unknown addressing mode!");
    return F->second;
  }

  const CodeGenIntrinsic &getIntrinsic(Record *R) const {
    for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
      if (Intrinsics[i].TheDef == R) return Intrinsics[i];
    for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
      if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i];
    llvm_unreachable("Unknown intrinsic!");
  }

  const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const {
    if (IID-1 < Intrinsics.size())
      return Intrinsics[IID-1];
    if (IID-Intrinsics.size()-1 < TgtIntrinsics.size())
      return TgtIntrinsics[IID-Intrinsics.size()-1];
    llvm_unreachable("Bad intrinsic ID!");
  }

  unsigned getIntrinsicID(Record *R) const {
    for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
      if (Intrinsics[i].TheDef == R) return i;
    for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
      if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size();
    llvm_unreachable("Unknown intrinsic!");
  }

  const DAGDefaultOperand &getDefaultOperand(Record *R) const {
    auto F = DefaultOperands.find(R);
    assert(F != DefaultOperands.end() &&"Isn't an analyzed default operand!");
    return F->second;
  }

  // Pattern Fragment information.
  TreePattern *getPatternFragment(Record *R) const {
    auto F = PatternFragments.find(R);
    assert(F != PatternFragments.end() && "Invalid pattern fragment request!");
    return F->second.get();
  }
  TreePattern *getPatternFragmentIfRead(Record *R) const {
    auto F = PatternFragments.find(R);
    if (F == PatternFragments.end())
      return nullptr;
    return F->second.get();
  }

  typedef std::map<Record *, std::unique_ptr<TreePattern>,
                   LessRecordByID>::const_iterator pf_iterator;
  pf_iterator pf_begin() const { return PatternFragments.begin(); }
  pf_iterator pf_end() const { return PatternFragments.end(); }
  iterator_range<pf_iterator> ptfs() const { return PatternFragments; }

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

  Record *get_intrinsic_void_sdnode() const {
    return intrinsic_void_sdnode;
  }
  Record *get_intrinsic_w_chain_sdnode() const {
    return intrinsic_w_chain_sdnode;
  }
  Record *get_intrinsic_wo_chain_sdnode() const {
    return intrinsic_wo_chain_sdnode;
  }

  bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); }

private:
  void ParseNodeInfo();
  void ParseNodeTransforms();
  void ParseComplexPatterns();
  void ParsePatternFragments(bool OutFrags = false);
  void ParseDefaultOperands();
  void ParseInstructions();
  void ParsePatterns();
  void ExpandHwModeBasedTypes();
  void InferInstructionFlags();
  void GenerateVariants();
  void VerifyInstructionFlags();

  std::vector<Predicate> makePredList(ListInit *L);

  void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM);
  void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
                                   std::map<std::string,
                                   TreePatternNode*> &InstInputs,
                                   std::map<std::string,
                                   TreePatternNode*> &InstResults,
                                   std::vector<Record*> &InstImpResults);
};


inline bool SDNodeInfo::ApplyTypeConstraints(TreePatternNode *N,
                                             TreePattern &TP) const {
    bool MadeChange = false;
    for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i)
      MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP);
    return MadeChange;
  }
} // end namespace llvm

#endif