aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm12/include/llvm/CodeGen/RDFGraph.h
blob: f2d5a9e017b081410d0ffa8078c1069c10d35ea7 (plain) (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
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- RDFGraph.h -----------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Target-independent, SSA-based data flow graph for register data flow (RDF)
// for a non-SSA program representation (e.g. post-RA machine code).
//
//
// *** Introduction
//
// The RDF graph is a collection of nodes, each of which denotes some element
// of the program. There are two main types of such elements: code and refe-
// rences. Conceptually, "code" is something that represents the structure
// of the program, e.g. basic block or a statement, while "reference" is an
// instance of accessing a register, e.g. a definition or a use. Nodes are
// connected with each other based on the structure of the program (such as
// blocks, instructions, etc.), and based on the data flow (e.g. reaching
// definitions, reached uses, etc.). The single-reaching-definition principle
// of SSA is generally observed, although, due to the non-SSA representation
// of the program, there are some differences between the graph and a "pure"
// SSA representation.
//
//
// *** Implementation remarks
//
// Since the graph can contain a large number of nodes, memory consumption
// was one of the major design considerations. As a result, there is a single
// base class NodeBase which defines all members used by all possible derived
// classes. The members are arranged in a union, and a derived class cannot
// add any data members of its own. Each derived class only defines the
// functional interface, i.e. member functions. NodeBase must be a POD,
// which implies that all of its members must also be PODs.
// Since nodes need to be connected with other nodes, pointers have been
// replaced with 32-bit identifiers: each node has an id of type NodeId.
// There are mapping functions in the graph that translate between actual
// memory addresses and the corresponding identifiers.
// A node id of 0 is equivalent to nullptr.
//
//
// *** Structure of the graph
//
// A code node is always a collection of other nodes. For example, a code
// node corresponding to a basic block will contain code nodes corresponding
// to instructions. In turn, a code node corresponding to an instruction will
// contain a list of reference nodes that correspond to the definitions and
// uses of registers in that instruction. The members are arranged into a
// circular list, which is yet another consequence of the effort to save
// memory: for each member node it should be possible to obtain its owner,
// and it should be possible to access all other members. There are other
// ways to accomplish that, but the circular list seemed the most natural.
//
// +- CodeNode -+
// |            | <---------------------------------------------------+
// +-+--------+-+                                                     |
//   |FirstM  |LastM                                                  |
//   |        +-------------------------------------+                 |
//   |                                              |                 |
//   V                                              V                 |
//  +----------+ Next +----------+ Next       Next +----------+ Next  |
//  |          |----->|          |-----> ... ----->|          |----->-+
//  +- Member -+      +- Member -+                 +- Member -+
//
// The order of members is such that related reference nodes (see below)
// should be contiguous on the member list.
//
// A reference node is a node that encapsulates an access to a register,
// in other words, data flowing into or out of a register. There are two
// major kinds of reference nodes: defs and uses. A def node will contain
// the id of the first reached use, and the id of the first reached def.
// Each def and use will contain the id of the reaching def, and also the
// id of the next reached def (for def nodes) or use (for use nodes).
// The "next node sharing the same reaching def" is denoted as "sibling".
// In summary:
// - Def node contains: reaching def, sibling, first reached def, and first
// reached use.
// - Use node contains: reaching def and sibling.
//
// +-- DefNode --+
// | R2 = ...    | <---+--------------------+
// ++---------+--+     |                    |
//  |Reached  |Reached |                    |
//  |Def      |Use     |                    |
//  |         |        |Reaching            |Reaching
//  |         V        |Def                 |Def
//  |      +-- UseNode --+ Sib  +-- UseNode --+ Sib       Sib
//  |      | ... = R2    |----->| ... = R2    |----> ... ----> 0
//  |      +-------------+      +-------------+
//  V
// +-- DefNode --+ Sib
// | R2 = ...    |----> ...
// ++---------+--+
//  |         |
//  |         |
// ...       ...
//
// To get a full picture, the circular lists connecting blocks within a
// function, instructions within a block, etc. should be superimposed with
// the def-def, def-use links shown above.
// To illustrate this, consider a small example in a pseudo-assembly:
// foo:
//   add r2, r0, r1   ; r2 = r0+r1
//   addi r0, r2, 1   ; r0 = r2+1
//   ret r0           ; return value in r0
//
// The graph (in a format used by the debugging functions) would look like:
//
//   DFG dump:[
//   f1: Function foo
//   b2: === %bb.0 === preds(0), succs(0):
//   p3: phi [d4<r0>(,d12,u9):]
//   p5: phi [d6<r1>(,,u10):]
//   s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
//   s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
//   s14: ret [u15<r0>(d12):]
//   ]
//
// The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
// kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
// ment, d - def, u - use).
// The format of a def node is:
//   dN<R>(rd,d,u):sib,
// where
//   N   - numeric node id,
//   R   - register being defined
//   rd  - reaching def,
//   d   - reached def,
//   u   - reached use,
//   sib - sibling.
// The format of a use node is:
//   uN<R>[!](rd):sib,
// where
//   N   - numeric node id,
//   R   - register being used,
//   rd  - reaching def,
//   sib - sibling.
// Possible annotations (usually preceding the node id):
//   +   - preserving def,
//   ~   - clobbering def,
//   "   - shadow ref (follows the node id),
//   !   - fixed register (appears after register name).
//
// The circular lists are not explicit in the dump.
//
//
// *** Node attributes
//
// NodeBase has a member "Attrs", which is the primary way of determining
// the node's characteristics. The fields in this member decide whether
// the node is a code node or a reference node (i.e. node's "type"), then
// within each type, the "kind" determines what specifically this node
// represents. The remaining bits, "flags", contain additional information
// that is even more detailed than the "kind".
// CodeNode's kinds are:
// - Phi:   Phi node, members are reference nodes.
// - Stmt:  Statement, members are reference nodes.
// - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
// - Func:  The whole function. The members are basic block nodes.
// RefNode's kinds are:
// - Use.
// - Def.
//
// Meaning of flags:
// - Preserving: applies only to defs. A preserving def is one that can
//   preserve some of the original bits among those that are included in
//   the register associated with that def. For example, if R0 is a 32-bit
//   register, but a def can only change the lower 16 bits, then it will
//   be marked as preserving.
// - Shadow: a reference that has duplicates holding additional reaching
//   defs (see more below).
// - Clobbering: applied only to defs, indicates that the value generated
//   by this def is unspecified. A typical example would be volatile registers
//   after function calls.
// - Fixed: the register in this def/use cannot be replaced with any other
//   register. A typical case would be a parameter register to a call, or
//   the register with the return value from a function.
// - Undef: the register in this reference the register is assumed to have
//   no pre-existing value, even if it appears to be reached by some def.
//   This is typically used to prevent keeping registers artificially live
//   in cases when they are defined via predicated instructions. For example:
//     r0 = add-if-true cond, r10, r11                (1)
//     r0 = add-if-false cond, r12, r13, implicit r0  (2)
//     ... = r0                                       (3)
//   Before (1), r0 is not intended to be live, and the use of r0 in (3) is
//   not meant to be reached by any def preceding (1). However, since the
//   defs in (1) and (2) are both preserving, these properties alone would
//   imply that the use in (3) may indeed be reached by some prior def.
//   Adding Undef flag to the def in (1) prevents that. The Undef flag
//   may be applied to both defs and uses.
// - Dead: applies only to defs. The value coming out of a "dead" def is
//   assumed to be unused, even if the def appears to be reaching other defs
//   or uses. The motivation for this flag comes from dead defs on function
//   calls: there is no way to determine if such a def is dead without
//   analyzing the target's ABI. Hence the graph should contain this info,
//   as it is unavailable otherwise. On the other hand, a def without any
//   uses on a typical instruction is not the intended target for this flag.
//
// *** Shadow references
//
// It may happen that a super-register can have two (or more) non-overlapping
// sub-registers. When both of these sub-registers are defined and followed
// by a use of the super-register, the use of the super-register will not
// have a unique reaching def: both defs of the sub-registers need to be
// accounted for. In such cases, a duplicate use of the super-register is
// added and it points to the extra reaching def. Both uses are marked with
// a flag "shadow". Example:
// Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
//   set r0, 1        ; r0 = 1
//   set r1, 1        ; r1 = 1
//   addi t1, t0, 1   ; t1 = t0+1
//
// The DFG:
//   s1: set [d2<r0>(,,u9):]
//   s3: set [d4<r1>(,,u10):]
//   s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
//
// The statement s5 has two use nodes for t0: u7" and u9". The quotation
// mark " indicates that the node is a shadow.
//

#ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
#define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H

#include "RDFRegisters.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/MathExtras.h"
#include <cassert>
#include <cstdint>
#include <cstring>
#include <map>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

// RDF uses uint32_t to refer to registers. This is to ensure that the type
// size remains specific. In other places, registers are often stored using
// unsigned.
static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");

namespace llvm {

class MachineBasicBlock;
class MachineDominanceFrontier;
class MachineDominatorTree;
class MachineFunction;
class MachineInstr;
class MachineOperand;
class raw_ostream;
class TargetInstrInfo;
class TargetRegisterInfo;

namespace rdf {

  using NodeId = uint32_t;

  struct DataFlowGraph;

  struct NodeAttrs {
    enum : uint16_t {
      None          = 0x0000,   // Nothing

      // Types: 2 bits
      TypeMask      = 0x0003,
      Code          = 0x0001,   // 01, Container
      Ref           = 0x0002,   // 10, Reference

      // Kind: 3 bits
      KindMask      = 0x0007 << 2,
      Def           = 0x0001 << 2,  // 001
      Use           = 0x0002 << 2,  // 010
      Phi           = 0x0003 << 2,  // 011
      Stmt          = 0x0004 << 2,  // 100
      Block         = 0x0005 << 2,  // 101
      Func          = 0x0006 << 2,  // 110

      // Flags: 7 bits for now
      FlagMask      = 0x007F << 5,
      Shadow        = 0x0001 << 5,  // 0000001, Has extra reaching defs.
      Clobbering    = 0x0002 << 5,  // 0000010, Produces unspecified values.
      PhiRef        = 0x0004 << 5,  // 0000100, Member of PhiNode.
      Preserving    = 0x0008 << 5,  // 0001000, Def can keep original bits.
      Fixed         = 0x0010 << 5,  // 0010000, Fixed register.
      Undef         = 0x0020 << 5,  // 0100000, Has no pre-existing value.
      Dead          = 0x0040 << 5,  // 1000000, Does not define a value.
    };

    static uint16_t type(uint16_t T)  { return T & TypeMask; }
    static uint16_t kind(uint16_t T)  { return T & KindMask; }
    static uint16_t flags(uint16_t T) { return T & FlagMask; }

    static uint16_t set_type(uint16_t A, uint16_t T) {
      return (A & ~TypeMask) | T;
    }

    static uint16_t set_kind(uint16_t A, uint16_t K) {
      return (A & ~KindMask) | K;
    }

    static uint16_t set_flags(uint16_t A, uint16_t F) {
      return (A & ~FlagMask) | F;
    }

    // Test if A contains B.
    static bool contains(uint16_t A, uint16_t B) {
      if (type(A) != Code)
        return false;
      uint16_t KB = kind(B);
      switch (kind(A)) {
        case Func:
          return KB == Block;
        case Block:
          return KB == Phi || KB == Stmt;
        case Phi:
        case Stmt:
          return type(B) == Ref;
      }
      return false;
    }
  };

  struct BuildOptions {
    enum : unsigned {
      None          = 0x00,
      KeepDeadPhis  = 0x01,   // Do not remove dead phis during build.
    };
  };

  template <typename T> struct NodeAddr {
    NodeAddr() = default;
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}

    // Type cast (casting constructor). The reason for having this class
    // instead of std::pair.
    template <typename S> NodeAddr(const NodeAddr<S> &NA)
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}

    bool operator== (const NodeAddr<T> &NA) const {
      assert((Addr == NA.Addr) == (Id == NA.Id));
      return Addr == NA.Addr;
    }
    bool operator!= (const NodeAddr<T> &NA) const {
      return !operator==(NA);
    }

    T Addr = nullptr;
    NodeId Id = 0;
  };

  struct NodeBase;

  // Fast memory allocation and translation between node id and node address.
  // This is really the same idea as the one underlying the "bump pointer
  // allocator", the difference being in the translation. A node id is
  // composed of two components: the index of the block in which it was
  // allocated, and the index within the block. With the default settings,
  // where the number of nodes per block is 4096, the node id (minus 1) is:
  //
  // bit position:                11             0
  // +----------------------------+--------------+
  // | Index of the block         |Index in block|
  // +----------------------------+--------------+
  //
  // The actual node id is the above plus 1, to avoid creating a node id of 0.
  //
  // This method significantly improved the build time, compared to using maps
  // (std::unordered_map or DenseMap) to translate between pointers and ids.
  struct NodeAllocator {
    // Amount of storage for a single node.
    enum { NodeMemSize = 32 };

    NodeAllocator(uint32_t NPB = 4096)
        : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
          IndexMask((1 << BitsPerIndex)-1) {
      assert(isPowerOf2_32(NPB));
    }

    NodeBase *ptr(NodeId N) const {
      uint32_t N1 = N-1;
      uint32_t BlockN = N1 >> BitsPerIndex;
      uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
      return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
    }

    NodeId id(const NodeBase *P) const;
    NodeAddr<NodeBase*> New();
    void clear();

  private:
    void startNewBlock();
    bool needNewBlock();

    uint32_t makeId(uint32_t Block, uint32_t Index) const {
      // Add 1 to the id, to avoid the id of 0, which is treated as "null".
      return ((Block << BitsPerIndex) | Index) + 1;
    }

    const uint32_t NodesPerBlock;
    const uint32_t BitsPerIndex;
    const uint32_t IndexMask;
    char *ActiveEnd = nullptr;
    std::vector<char*> Blocks;
    using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>;
    AllocatorTy MemPool;
  };

  using RegisterSet = std::set<RegisterRef>;

  struct TargetOperandInfo {
    TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
    virtual ~TargetOperandInfo() = default;

    virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
    virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
    virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;

    const TargetInstrInfo &TII;
  };

  // Packed register reference. Only used for storage.
  struct PackedRegisterRef {
    RegisterId Reg;
    uint32_t MaskId;
  };

  struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
    LaneMaskIndex() = default;

    LaneBitmask getLaneMaskForIndex(uint32_t K) const {
      return K == 0 ? LaneBitmask::getAll() : get(K);
    }

    uint32_t getIndexForLaneMask(LaneBitmask LM) {
      assert(LM.any());
      return LM.all() ? 0 : insert(LM);
    }

    uint32_t getIndexForLaneMask(LaneBitmask LM) const {
      assert(LM.any());
      return LM.all() ? 0 : find(LM);
    }
  };

  struct NodeBase {
  public:
    // Make sure this is a POD.
    NodeBase() = default;

    uint16_t getType()  const { return NodeAttrs::type(Attrs); }
    uint16_t getKind()  const { return NodeAttrs::kind(Attrs); }
    uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
    NodeId   getNext()  const { return Next; }

    uint16_t getAttrs() const { return Attrs; }
    void setAttrs(uint16_t A) { Attrs = A; }
    void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }

    // Insert node NA after "this" in the circular chain.
    void append(NodeAddr<NodeBase*> NA);

    // Initialize all members to 0.
    void init() { memset(this, 0, sizeof *this); }

    void setNext(NodeId N) { Next = N; }

  protected:
    uint16_t Attrs;
    uint16_t Reserved;
    NodeId Next;                // Id of the next node in the circular chain.
    // Definitions of nested types. Using anonymous nested structs would make
    // this class definition clearer, but unnamed structs are not a part of
    // the standard.
    struct Def_struct  {
      NodeId DD, DU;          // Ids of the first reached def and use.
    };
    struct PhiU_struct  {
      NodeId PredB;           // Id of the predecessor block for a phi use.
    };
    struct Code_struct {
      void *CP;               // Pointer to the actual code.
      NodeId FirstM, LastM;   // Id of the first member and last.
    };
    struct Ref_struct {
      NodeId RD, Sib;         // Ids of the reaching def and the sibling.
      union {
        Def_struct Def;
        PhiU_struct PhiU;
      };
      union {
        MachineOperand *Op;   // Non-phi refs point to a machine operand.
        PackedRegisterRef PR; // Phi refs store register info directly.
      };
    };

    // The actual payload.
    union {
      Ref_struct Ref;
      Code_struct Code;
    };
  };
  // The allocator allocates chunks of 32 bytes for each node. The fact that
  // each node takes 32 bytes in memory is used for fast translation between
  // the node id and the node address.
  static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
        "NodeBase must be at most NodeAllocator::NodeMemSize bytes");

  using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>;
  using NodeSet = std::set<NodeId>;

  struct RefNode : public NodeBase {
    RefNode() = default;

    RegisterRef getRegRef(const DataFlowGraph &G) const;

    MachineOperand &getOp() {
      assert(!(getFlags() & NodeAttrs::PhiRef));
      return *Ref.Op;
    }

    void setRegRef(RegisterRef RR, DataFlowGraph &G);
    void setRegRef(MachineOperand *Op, DataFlowGraph &G);

    NodeId getReachingDef() const {
      return Ref.RD;
    }
    void setReachingDef(NodeId RD) {
      Ref.RD = RD;
    }

    NodeId getSibling() const {
      return Ref.Sib;
    }
    void setSibling(NodeId Sib) {
      Ref.Sib = Sib;
    }

    bool isUse() const {
      assert(getType() == NodeAttrs::Ref);
      return getKind() == NodeAttrs::Use;
    }

    bool isDef() const {
      assert(getType() == NodeAttrs::Ref);
      return getKind() == NodeAttrs::Def;
    }

    template <typename Predicate>
    NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
        const DataFlowGraph &G);
    NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
  };

  struct DefNode : public RefNode {
    NodeId getReachedDef() const {
      return Ref.Def.DD;
    }
    void setReachedDef(NodeId D) {
      Ref.Def.DD = D;
    }
    NodeId getReachedUse() const {
      return Ref.Def.DU;
    }
    void setReachedUse(NodeId U) {
      Ref.Def.DU = U;
    }

    void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
  };

  struct UseNode : public RefNode {
    void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
  };

  struct PhiUseNode : public UseNode {
    NodeId getPredecessor() const {
      assert(getFlags() & NodeAttrs::PhiRef);
      return Ref.PhiU.PredB;
    }
    void setPredecessor(NodeId B) {
      assert(getFlags() & NodeAttrs::PhiRef);
      Ref.PhiU.PredB = B;
    }
  };

  struct CodeNode : public NodeBase {
    template <typename T> T getCode() const {
      return static_cast<T>(Code.CP);
    }
    void setCode(void *C) {
      Code.CP = C;
    }

    NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
    NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
    void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
    void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
        const DataFlowGraph &G);
    void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);

    NodeList members(const DataFlowGraph &G) const;
    template <typename Predicate>
    NodeList members_if(Predicate P, const DataFlowGraph &G) const;
  };

  struct InstrNode : public CodeNode {
    NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
  };

  struct PhiNode : public InstrNode {
    MachineInstr *getCode() const {
      return nullptr;
    }
  };

  struct StmtNode : public InstrNode {
    MachineInstr *getCode() const {
      return CodeNode::getCode<MachineInstr*>();
    }
  };

  struct BlockNode : public CodeNode {
    MachineBasicBlock *getCode() const {
      return CodeNode::getCode<MachineBasicBlock*>();
    }

    void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
  };

  struct FuncNode : public CodeNode {
    MachineFunction *getCode() const {
      return CodeNode::getCode<MachineFunction*>();
    }

    NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
        const DataFlowGraph &G) const;
    NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
  };

  struct DataFlowGraph {
    DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
        const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
        const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);

    NodeBase *ptr(NodeId N) const;
    template <typename T> T ptr(NodeId N) const {
      return static_cast<T>(ptr(N));
    }

    NodeId id(const NodeBase *P) const;

    template <typename T> NodeAddr<T> addr(NodeId N) const {
      return { ptr<T>(N), N };
    }

    NodeAddr<FuncNode*> getFunc() const { return Func; }
    MachineFunction &getMF() const { return MF; }
    const TargetInstrInfo &getTII() const { return TII; }
    const TargetRegisterInfo &getTRI() const { return TRI; }
    const PhysicalRegisterInfo &getPRI() const { return PRI; }
    const MachineDominatorTree &getDT() const { return MDT; }
    const MachineDominanceFrontier &getDF() const { return MDF; }
    const RegisterAggr &getLiveIns() const { return LiveIns; }

    struct DefStack {
      DefStack() = default;

      bool empty() const { return Stack.empty() || top() == bottom(); }

    private:
      using value_type = NodeAddr<DefNode *>;
      struct Iterator {
        using value_type = DefStack::value_type;

        Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
        Iterator &down() { Pos = DS.nextDown(Pos); return *this; }

        value_type operator*() const {
          assert(Pos >= 1);
          return DS.Stack[Pos-1];
        }
        const value_type *operator->() const {
          assert(Pos >= 1);
          return &DS.Stack[Pos-1];
        }
        bool operator==(const Iterator &It) const { return Pos == It.Pos; }
        bool operator!=(const Iterator &It) const { return Pos != It.Pos; }

      private:
        friend struct DefStack;

        Iterator(const DefStack &S, bool Top);

        // Pos-1 is the index in the StorageType object that corresponds to
        // the top of the DefStack.
        const DefStack &DS;
        unsigned Pos;
      };

    public:
      using iterator = Iterator;

      iterator top() const { return Iterator(*this, true); }
      iterator bottom() const { return Iterator(*this, false); }
      unsigned size() const;

      void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
      void pop();
      void start_block(NodeId N);
      void clear_block(NodeId N);

    private:
      friend struct Iterator;

      using StorageType = std::vector<value_type>;

      bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
        return (P.Addr == nullptr) && (N == 0 || P.Id == N);
      }

      unsigned nextUp(unsigned P) const;
      unsigned nextDown(unsigned P) const;

      StorageType Stack;
    };

    // Make this std::unordered_map for speed of accessing elements.
    // Map: Register (physical or virtual) -> DefStack
    using DefStackMap = std::unordered_map<RegisterId, DefStack>;

    void build(unsigned Options = BuildOptions::None);
    void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
    void markBlock(NodeId B, DefStackMap &DefM);
    void releaseBlock(NodeId B, DefStackMap &DefM);

    PackedRegisterRef pack(RegisterRef RR) {
      return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
    }
    PackedRegisterRef pack(RegisterRef RR) const {
      return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
    }
    RegisterRef unpack(PackedRegisterRef PR) const {
      return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
    }

    RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
    RegisterRef makeRegRef(const MachineOperand &Op) const;
    RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;

    NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
        NodeAddr<RefNode*> RA) const;
    NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
        NodeAddr<RefNode*> RA, bool Create);
    NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
        NodeAddr<RefNode*> RA) const;

    NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
        NodeAddr<RefNode*> RA) const;

    NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
      return BlockNodes.at(BB);
    }

    void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
      unlinkUseDF(UA);
      if (RemoveFromOwner)
        removeFromOwner(UA);
    }

    void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
      unlinkDefDF(DA);
      if (RemoveFromOwner)
        removeFromOwner(DA);
    }

    // Some useful filters.
    template <uint16_t Kind>
    static bool IsRef(const NodeAddr<NodeBase*> BA) {
      return BA.Addr->getType() == NodeAttrs::Ref &&
             BA.Addr->getKind() == Kind;
    }

    template <uint16_t Kind>
    static bool IsCode(const NodeAddr<NodeBase*> BA) {
      return BA.Addr->getType() == NodeAttrs::Code &&
             BA.Addr->getKind() == Kind;
    }

    static bool IsDef(const NodeAddr<NodeBase*> BA) {
      return BA.Addr->getType() == NodeAttrs::Ref &&
             BA.Addr->getKind() == NodeAttrs::Def;
    }

    static bool IsUse(const NodeAddr<NodeBase*> BA) {
      return BA.Addr->getType() == NodeAttrs::Ref &&
             BA.Addr->getKind() == NodeAttrs::Use;
    }

    static bool IsPhi(const NodeAddr<NodeBase*> BA) {
      return BA.Addr->getType() == NodeAttrs::Code &&
             BA.Addr->getKind() == NodeAttrs::Phi;
    }

    static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
      uint16_t Flags = DA.Addr->getFlags();
      return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
    }

  private:
    void reset();

    RegisterSet getLandingPadLiveIns() const;

    NodeAddr<NodeBase*> newNode(uint16_t Attrs);
    NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
    NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
        MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
    NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
        RegisterRef RR, NodeAddr<BlockNode*> PredB,
        uint16_t Flags = NodeAttrs::PhiRef);
    NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
        MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
    NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
        RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
    NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
    NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
        MachineInstr *MI);
    NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
        MachineBasicBlock *BB);
    NodeAddr<FuncNode*> newFunc(MachineFunction *MF);

    template <typename Predicate>
    std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
    locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
        Predicate P) const;

    using BlockRefsMap = std::map<NodeId, RegisterSet>;

    void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
    void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
    void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
        NodeAddr<BlockNode*> BA);
    void removeUnusedPhis();

    void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
    void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
    template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
        NodeAddr<T> TA, DefStack &DS);
    template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
        NodeAddr<StmtNode*> SA, Predicate P);
    void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);

    void unlinkUseDF(NodeAddr<UseNode*> UA);
    void unlinkDefDF(NodeAddr<DefNode*> DA);

    void removeFromOwner(NodeAddr<RefNode*> RA) {
      NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
      IA.Addr->removeMember(RA, *this);
    }

    MachineFunction &MF;
    const TargetInstrInfo &TII;
    const TargetRegisterInfo &TRI;
    const PhysicalRegisterInfo PRI;
    const MachineDominatorTree &MDT;
    const MachineDominanceFrontier &MDF;
    const TargetOperandInfo &TOI;

    RegisterAggr LiveIns;
    NodeAddr<FuncNode*> Func;
    NodeAllocator Memory;
    // Local map:  MachineBasicBlock -> NodeAddr<BlockNode*>
    std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
    // Lane mask map.
    LaneMaskIndex LMI;
  };  // struct DataFlowGraph

  template <typename Predicate>
  NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
        bool NextOnly, const DataFlowGraph &G) {
    // Get the "Next" reference in the circular list that references RR and
    // satisfies predicate "Pred".
    auto NA = G.addr<NodeBase*>(getNext());

    while (NA.Addr != this) {
      if (NA.Addr->getType() == NodeAttrs::Ref) {
        NodeAddr<RefNode*> RA = NA;
        if (RA.Addr->getRegRef(G) == RR && P(NA))
          return NA;
        if (NextOnly)
          break;
        NA = G.addr<NodeBase*>(NA.Addr->getNext());
      } else {
        // We've hit the beginning of the chain.
        assert(NA.Addr->getType() == NodeAttrs::Code);
        NodeAddr<CodeNode*> CA = NA;
        NA = CA.Addr->getFirstMember(G);
      }
    }
    // Return the equivalent of "nullptr" if such a node was not found.
    return NodeAddr<RefNode*>();
  }

  template <typename Predicate>
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
    NodeList MM;
    auto M = getFirstMember(G);
    if (M.Id == 0)
      return MM;

    while (M.Addr != this) {
      if (P(M))
        MM.push_back(M);
      M = G.addr<NodeBase*>(M.Addr->getNext());
    }
    return MM;
  }

  template <typename T>
  struct Print {
    Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}

    const T &Obj;
    const DataFlowGraph &G;
  };

  template <typename T>
  struct PrintNode : Print<NodeAddr<T>> {
    PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
      : Print<NodeAddr<T>>(x, g) {}
  };

  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<NodeAddr<PhiUseNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<NodeAddr<StmtNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<NodeAddr<InstrNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<NodeAddr<BlockNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<NodeAddr<FuncNode *>> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
  raw_ostream &operator<<(raw_ostream &OS,
                          const Print<DataFlowGraph::DefStack> &P);

} // end namespace rdf

} // end namespace llvm

#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif