Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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_CODEGEN_RDFGRAPH_H

#define LLVM_CODEGEN_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 <memory>

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

    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;

    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 &&