Move RDF from Hexagon to Codegen

RDF is designed to be target agnostic. Therefore it would be useful to have it available for other targets, such as X86.

Based on a previous patch by Krzysztof Parzyszek

Differential Revision: https://reviews.llvm.org/D75932

13 files changed, 16 insertions, 4711 deletions

diff --git a/llvm/lib/Target/Hexagon/CMakeLists.txt b/llvm/lib/Target/Hexagon/CMakeLists.txt
index 3536aa81fb2..747f14e0cec 100644
--- a/llvm/lib/Target/Hexagon/CMakeLists.txt
+++ b/llvm/lib/Target/Hexagon/CMakeLists.txt
@@ -64,9 +64,6 @@ add_llvm_target(HexagonCodeGen
   HexagonVLIWPacketizer.cpp
   RDFCopy.cpp
   RDFDeadCode.cpp
-  RDFGraph.cpp
-  RDFLiveness.cpp
-  RDFRegisters.cpp
 )
 
 add_subdirectory(AsmParser)
diff --git a/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp b/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp
index 886034d9601..f1fe51f5e54 100644
--- a/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp
@@ -12,9 +12,6 @@
 #include "HexagonInstrInfo.h"
 #include "HexagonSubtarget.h"
 #include "MCTargetDesc/HexagonBaseInfo.h"
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
-#include "RDFRegisters.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
@@ -27,6 +24,9 @@
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
+#include "llvm/CodeGen/RDFRegisters.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/MCInstrDesc.h"
diff --git a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
index 517ad1c6ee7..f26e23befde 100644
--- a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
@@ -11,9 +11,6 @@
 #include "MCTargetDesc/HexagonBaseInfo.h"
 #include "RDFCopy.h"
 #include "RDFDeadCode.h"
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
-#include "RDFRegisters.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
@@ -24,6 +21,9 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
+#include "llvm/CodeGen/RDFRegisters.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
diff --git a/llvm/lib/Target/Hexagon/RDFCopy.cpp b/llvm/lib/Target/Hexagon/RDFCopy.cpp
index a9d39fd4b2d..34d58f0a7a2 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.cpp
+++ b/llvm/lib/Target/Hexagon/RDFCopy.cpp
@@ -11,13 +11,13 @@
 //===----------------------------------------------------------------------===//
 
 #include "RDFCopy.h"
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
-#include "RDFRegisters.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
+#include "llvm/CodeGen/RDFRegisters.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/MC/MCRegisterInfo.h"
diff --git a/llvm/lib/Target/Hexagon/RDFCopy.h b/llvm/lib/Target/Hexagon/RDFCopy.h
index 1450ab88484..99b18a75d8c 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.h
+++ b/llvm/lib/Target/Hexagon/RDFCopy.h
@@ -9,9 +9,9 @@
 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H
 #define LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H
 
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
-#include "RDFRegisters.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
+#include "llvm/CodeGen/RDFRegisters.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include <map>
 #include <vector>
diff --git a/llvm/lib/Target/Hexagon/RDFDeadCode.cpp b/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
index af86c7b1956..5a98debd3c0 100644
--- a/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
+++ b/llvm/lib/Target/Hexagon/RDFDeadCode.cpp
@@ -9,13 +9,13 @@
 // RDF-based generic dead code elimination.
 
 #include "RDFDeadCode.h"
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
 #include "llvm/Support/Debug.h"
 
 #include <queue>
diff --git a/llvm/lib/Target/Hexagon/RDFDeadCode.h b/llvm/lib/Target/Hexagon/RDFDeadCode.h
index 7f91977e1d6..859c8161d35 100644
--- a/llvm/lib/Target/Hexagon/RDFDeadCode.h
+++ b/llvm/lib/Target/Hexagon/RDFDeadCode.h
@@ -23,8 +23,8 @@
 #ifndef RDF_DEADCODE_H
 #define RDF_DEADCODE_H
 
-#include "RDFGraph.h"
-#include "RDFLiveness.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
 #include "llvm/ADT/SetVector.h"
 
 namespace llvm {
diff --git a/llvm/lib/Target/Hexagon/RDFGraph.cpp b/llvm/lib/Target/Hexagon/RDFGraph.cpp
deleted file mode 100644
index 0cb35dc9881..00000000000
--- a/llvm/lib/Target/Hexagon/RDFGraph.cpp
+++ /dev/null
@@ -1,1835 +0,0 @@
-//===- RDFGraph.cpp -------------------------------------------------------===//
-//
-// 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).
-//
-#include "RDFGraph.h"
-#include "RDFRegisters.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
-#include "llvm/CodeGen/MachineDominanceFrontier.h"
-#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineOperand.h"
-#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/TargetInstrInfo.h"
-#include "llvm/CodeGen/TargetLowering.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/CodeGen/TargetSubtargetInfo.h"
-#include "llvm/IR/Function.h"
-#include "llvm/MC/LaneBitmask.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <cassert>
-#include <cstdint>
-#include <cstring>
-#include <iterator>
-#include <set>
-#include <utility>
-#include <vector>
-
-using namespace llvm;
-using namespace rdf;
-
-// Printing functions. Have them here first, so that the rest of the code
-// can use them.
-namespace llvm {
-namespace rdf {
-
-raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P) {
-  if (!P.Mask.all())
-    OS << ':' << PrintLaneMask(P.Mask);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterRef> &P) {
-  auto &TRI = P.G.getTRI();
-  if (P.Obj.Reg > 0 && P.Obj.Reg < TRI.getNumRegs())
-    OS << TRI.getName(P.Obj.Reg);
-  else
-    OS << '#' << P.Obj.Reg;
-  OS << PrintLaneMaskOpt(P.Obj.Mask);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeId> &P) {
-  auto NA = P.G.addr<NodeBase*>(P.Obj);
-  uint16_t Attrs = NA.Addr->getAttrs();
-  uint16_t Kind = NodeAttrs::kind(Attrs);
-  uint16_t Flags = NodeAttrs::flags(Attrs);
-  switch (NodeAttrs::type(Attrs)) {
-    case NodeAttrs::Code:
-      switch (Kind) {
-        case NodeAttrs::Func:   OS << 'f'; break;
-        case NodeAttrs::Block:  OS << 'b'; break;
-        case NodeAttrs::Stmt:   OS << 's'; break;
-        case NodeAttrs::Phi:    OS << 'p'; break;
-        default:                OS << "c?"; break;
-      }
-      break;
-    case NodeAttrs::Ref:
-      if (Flags & NodeAttrs::Undef)
-        OS << '/';
-      if (Flags & NodeAttrs::Dead)
-        OS << '\\';
-      if (Flags & NodeAttrs::Preserving)
-        OS << '+';
-      if (Flags & NodeAttrs::Clobbering)
-        OS << '~';
-      switch (Kind) {
-        case NodeAttrs::Use:    OS << 'u'; break;
-        case NodeAttrs::Def:    OS << 'd'; break;
-        case NodeAttrs::Block:  OS << 'b'; break;
-        default:                OS << "r?"; break;
-      }
-      break;
-    default:
-      OS << '?';
-      break;
-  }
-  OS << P.Obj;
-  if (Flags & NodeAttrs::Shadow)
-    OS << '"';
-  return OS;
-}
-
-static void printRefHeader(raw_ostream &OS, const NodeAddr<RefNode*> RA,
-                const DataFlowGraph &G) {
-  OS << Print<NodeId>(RA.Id, G) << '<'
-     << Print<RegisterRef>(RA.Addr->getRegRef(G), G) << '>';
-  if (RA.Addr->getFlags() & NodeAttrs::Fixed)
-    OS << '!';
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<DefNode*>> &P) {
-  printRefHeader(OS, P.Obj, P.G);
-  OS << '(';
-  if (NodeId N = P.Obj.Addr->getReachingDef())
-    OS << Print<NodeId>(N, P.G);
-  OS << ',';
-  if (NodeId N = P.Obj.Addr->getReachedDef())
-    OS << Print<NodeId>(N, P.G);
-  OS << ',';
-  if (NodeId N = P.Obj.Addr->getReachedUse())
-    OS << Print<NodeId>(N, P.G);
-  OS << "):";
-  if (NodeId N = P.Obj.Addr->getSibling())
-    OS << Print<NodeId>(N, P.G);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) {
-  printRefHeader(OS, P.Obj, P.G);
-  OS << '(';
-  if (NodeId N = P.Obj.Addr->getReachingDef())
-    OS << Print<NodeId>(N, P.G);
-  OS << "):";
-  if (NodeId N = P.Obj.Addr->getSibling())
-    OS << Print<NodeId>(N, P.G);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS,
-      const Print<NodeAddr<PhiUseNode*>> &P) {
-  printRefHeader(OS, P.Obj, P.G);
-  OS << '(';
-  if (NodeId N = P.Obj.Addr->getReachingDef())
-    OS << Print<NodeId>(N, P.G);
-  OS << ',';
-  if (NodeId N = P.Obj.Addr->getPredecessor())
-    OS << Print<NodeId>(N, P.G);
-  OS << "):";
-  if (NodeId N = P.Obj.Addr->getSibling())
-    OS << Print<NodeId>(N, P.G);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<RefNode*>> &P) {
-  switch (P.Obj.Addr->getKind()) {
-    case NodeAttrs::Def:
-      OS << PrintNode<DefNode*>(P.Obj, P.G);
-      break;
-    case NodeAttrs::Use:
-      if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef)
-        OS << PrintNode<PhiUseNode*>(P.Obj, P.G);
-      else
-        OS << PrintNode<UseNode*>(P.Obj, P.G);
-      break;
-  }
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeList> &P) {
-  unsigned N = P.Obj.size();
-  for (auto I : P.Obj) {
-    OS << Print<NodeId>(I.Id, P.G);
-    if (--N)
-      OS << ' ';
-  }
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) {
-  unsigned N = P.Obj.size();
-  for (auto I : P.Obj) {
-    OS << Print<NodeId>(I, P.G);
-    if (--N)
-      OS << ' ';
-  }
-  return OS;
-}
-
-namespace {
-
-  template <typename T>
-  struct PrintListV {
-    PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {}
-
-    using Type = T;
-    const NodeList &List;
-    const DataFlowGraph &G;
-  };
-
-  template <typename T>
-  raw_ostream &operator<< (raw_ostream &OS, const PrintListV<T> &P) {
-    unsigned N = P.List.size();
-    for (NodeAddr<T> A : P.List) {
-      OS << PrintNode<T>(A, P.G);
-      if (--N)
-        OS << ", ";
-    }
-    return OS;
-  }
-
-} // end anonymous namespace
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<PhiNode*>> &P) {
-  OS << Print<NodeId>(P.Obj.Id, P.G) << ": phi ["
-     << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']';
-  return OS;
-}
-
-raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<StmtNode *>> &P) {
-  const MachineInstr &MI = *P.Obj.Addr->getCode();
-  unsigned Opc = MI.getOpcode();
-  OS << Print<NodeId>(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc);
-  // Print the target for calls and branches (for readability).
-  if (MI.isCall() || MI.isBranch()) {
-    MachineInstr::const_mop_iterator T =
-          llvm::find_if(MI.operands(),
-                        [] (const MachineOperand &Op) -> bool {
-                          return Op.isMBB() || Op.isGlobal() || Op.isSymbol();
-                        });
-    if (T != MI.operands_end()) {
-      OS << ' ';
-      if (T->isMBB())
-        OS << printMBBReference(*T->getMBB());
-      else if (T->isGlobal())
-        OS << T->getGlobal()->getName();
-      else if (T->isSymbol())
-        OS << T->getSymbolName();
-    }
-  }
-  OS << " [" << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']';
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS,
-      const Print<NodeAddr<InstrNode*>> &P) {
-  switch (P.Obj.Addr->getKind()) {
-    case NodeAttrs::Phi:
-      OS << PrintNode<PhiNode*>(P.Obj, P.G);
-      break;
-    case NodeAttrs::Stmt:
-      OS << PrintNode<StmtNode*>(P.Obj, P.G);
-      break;
-    default:
-      OS << "instr? " << Print<NodeId>(P.Obj.Id, P.G);
-      break;
-  }
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS,
-      const Print<NodeAddr<BlockNode*>> &P) {
-  MachineBasicBlock *BB = P.Obj.Addr->getCode();
-  unsigned NP = BB->pred_size();
-  std::vector<int> Ns;
-  auto PrintBBs = [&OS] (std::vector<int> Ns) -> void {
-    unsigned N = Ns.size();
-    for (int I : Ns) {
-      OS << "%bb." << I;
-      if (--N)
-        OS << ", ";
-    }
-  };
-
-  OS << Print<NodeId>(P.Obj.Id, P.G) << ": --- " << printMBBReference(*BB)
-     << " --- preds(" << NP << "): ";
-  for (MachineBasicBlock *B : BB->predecessors())
-    Ns.push_back(B->getNumber());
-  PrintBBs(Ns);
-
-  unsigned NS = BB->succ_size();
-  OS << "  succs(" << NS << "): ";
-  Ns.clear();
-  for (MachineBasicBlock *B : BB->successors())
-    Ns.push_back(B->getNumber());
-  PrintBBs(Ns);
-  OS << '\n';
-
-  for (auto I : P.Obj.Addr->members(P.G))
-    OS << PrintNode<InstrNode*>(I, P.G) << '\n';
-  return OS;
-}
-
-raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<FuncNode *>> &P) {
-  OS << "DFG dump:[\n" << Print<NodeId>(P.Obj.Id, P.G) << ": Function: "
-     << P.Obj.Addr->getCode()->getName() << '\n';
-  for (auto I : P.Obj.Addr->members(P.G))
-    OS << PrintNode<BlockNode*>(I, P.G) << '\n';
-  OS << "]\n";
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) {
-  OS << '{';
-  for (auto I : P.Obj)
-    OS << ' ' << Print<RegisterRef>(I, P.G);
-  OS << " }";
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterAggr> &P) {
-  P.Obj.print(OS);
-  return OS;
-}
-
-raw_ostream &operator<< (raw_ostream &OS,
-      const Print<DataFlowGraph::DefStack> &P) {
-  for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) {
-    OS << Print<NodeId>(I->Id, P.G)
-       << '<' << Print<RegisterRef>(I->Addr->getRegRef(P.G), P.G) << '>';
-    I.down();
-    if (I != E)
-      OS << ' ';
-  }
-  return OS;
-}
-
-} // end namespace rdf
-} // end namespace llvm
-
-// Node allocation functions.
-//
-// Node allocator is like a slab memory allocator: it allocates blocks of
-// memory in sizes that are multiples of the size of a node. Each block has
-// the same size. Nodes are allocated from the currently active block, and
-// when it becomes full, a new one is created.
-// There is a mapping scheme between node id and its location in a block,
-// and within that block is described in the header file.
-//
-void NodeAllocator::startNewBlock() {
-  void *T = MemPool.Allocate(NodesPerBlock*NodeMemSize, NodeMemSize);
-  char *P = static_cast<char*>(T);
-  Blocks.push_back(P);
-  // Check if the block index is still within the allowed range, i.e. less
-  // than 2^N, where N is the number of bits in NodeId for the block index.
-  // BitsPerIndex is the number of bits per node index.
-  assert((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) &&
-         "Out of bits for block index");
-  ActiveEnd = P;
-}
-
-bool NodeAllocator::needNewBlock() {
-  if (Blocks.empty())
-    return true;
-
-  char *ActiveBegin = Blocks.back();
-  uint32_t Index = (ActiveEnd-ActiveBegin)/NodeMemSize;
-  return Index >= NodesPerBlock;
-}
-
-NodeAddr<NodeBase*> NodeAllocator::New() {
-  if (needNewBlock())
-    startNewBlock();
-
-  uint32_t ActiveB = Blocks.size()-1;
-  uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize;
-  NodeAddr<NodeBase*> NA = { reinterpret_cast<NodeBase*>(ActiveEnd),
-                             makeId(ActiveB, Index) };
-  ActiveEnd += NodeMemSize;
-  return NA;
-}
-
-NodeId NodeAllocator::id(const NodeBase *P) const {
-  uintptr_t A = reinterpret_cast<uintptr_t>(P);
-  for (unsigned i = 0, n = Blocks.size(); i != n; ++i) {
-    uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]);
-    if (A < B || A >= B + NodesPerBlock*NodeMemSize)
-      continue;
-    uint32_t Idx = (A-B)/NodeMemSize;
-    return makeId(i, Idx);
-  }
-  llvm_unreachable("Invalid node address");
-}
-
-void NodeAllocator::clear() {
-  MemPool.Reset();
-  Blocks.clear();
-  ActiveEnd = nullptr;
-}
-
-// Insert node NA after "this" in the circular chain.
-void NodeBase::append(NodeAddr<NodeBase*> NA) {
-  NodeId Nx = Next;
-  // If NA is already "next", do nothing.
-  if (Next != NA.Id) {
-    Next = NA.Id;
-    NA.Addr->Next = Nx;
-  }
-}
-
-// Fundamental node manipulator functions.
-
-// Obtain the register reference from a reference node.
-RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const {
-  assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
-  if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)
-    return G.unpack(Ref.PR);
-  assert(Ref.Op != nullptr);
-  return G.makeRegRef(*Ref.Op);
-}
-
-// Set the register reference in the reference node directly (for references
-// in phi nodes).
-void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) {
-  assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
-  assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef);
-  Ref.PR = G.pack(RR);
-}
-
-// Set the register reference in the reference node based on a machine
-// operand (for references in statement nodes).
-void RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) {
-  assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);
-  assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef));
-  (void)G;
-  Ref.Op = Op;
-}
-
-// Get the owner of a given reference node.
-NodeAddr<NodeBase*> RefNode::getOwner(const DataFlowGraph &G) {
-  NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext());
-
-  while (NA.Addr != this) {
-    if (NA.Addr->getType() == NodeAttrs::Code)
-      return NA;
-    NA = G.addr<NodeBase*>(NA.Addr->getNext());
-  }
-  llvm_unreachable("No owner in circular list");
-}
-
-// Connect the def node to the reaching def node.
-void DefNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) {
-  Ref.RD = DA.Id;
-  Ref.Sib = DA.Addr->getReachedDef();
-  DA.Addr->setReachedDef(Self);
-}
-
-// Connect the use node to the reaching def node.
-void UseNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) {
-  Ref.RD = DA.Id;
-  Ref.Sib = DA.Addr->getReachedUse();
-  DA.Addr->setReachedUse(Self);
-}
-
-// Get the first member of the code node.
-NodeAddr<NodeBase*> CodeNode::getFirstMember(const DataFlowGraph &G) const {
-  if (Code.FirstM == 0)
-    return NodeAddr<NodeBase*>();
-  return G.addr<NodeBase*>(Code.FirstM);
-}
-
-// Get the last member of the code node.
-NodeAddr<NodeBase*> CodeNode::getLastMember(const DataFlowGraph &G) const {
-  if (Code.LastM == 0)
-    return NodeAddr<NodeBase*>();
-  return G.addr<NodeBase*>(Code.LastM);
-}
-
-// Add node NA at the end of the member list of the given code node.
-void CodeNode::addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) {
-  NodeAddr<NodeBase*> ML = getLastMember(G);
-  if (ML.Id != 0) {
-    ML.Addr->append(NA);
-  } else {
-    Code.FirstM = NA.Id;
-    NodeId Self = G.id(this);
-    NA.Addr->setNext(Self);
-  }
-  Code.LastM = NA.Id;
-}
-
-// Add node NA after member node MA in the given code node.
-void CodeNode::addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
-      const DataFlowGraph &G) {
-  MA.Addr->append(NA);
-  if (Code.LastM == MA.Id)
-    Code.LastM = NA.Id;
-}
-
-// Remove member node NA from the given code node.
-void CodeNode::removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) {
-  NodeAddr<NodeBase*> MA = getFirstMember(G);
-  assert(MA.Id != 0);
-
-  // Special handling if the member to remove is the first member.
-  if (MA.Id == NA.Id) {
-    if (Code.LastM == MA.Id) {
-      // If it is the only member, set both first and last to 0.
-      Code.FirstM = Code.LastM = 0;
-    } else {
-      // Otherwise, advance the first member.
-      Code.FirstM = MA.Addr->getNext();
-    }
-    return;
-  }
-
-  while (MA.Addr != this) {
-    NodeId MX = MA.Addr->getNext();
-    if (MX == NA.Id) {
-      MA.Addr->setNext(NA.Addr->getNext());
-      // If the member to remove happens to be the last one, update the
-      // LastM indicator.
-      if (Code.LastM == NA.Id)
-        Code.LastM = MA.Id;
-      return;
-    }
-    MA = G.addr<NodeBase*>(MX);
-  }
-  llvm_unreachable("No such member");
-}
-
-// Return the list of all members of the code node.
-NodeList CodeNode::members(const DataFlowGraph &G) const {
-  static auto True = [] (NodeAddr<NodeBase*>) -> bool { return true; };
-  return members_if(True, G);
-}
-
-// Return the owner of the given instr node.
-NodeAddr<NodeBase*> InstrNode::getOwner(const DataFlowGraph &G) {
-  NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext());
-
-  while (NA.Addr != this) {
-    assert(NA.Addr->getType() == NodeAttrs::Code);
-    if (NA.Addr->getKind() == NodeAttrs::Block)
-      return NA;
-    NA = G.addr<NodeBase*>(NA.Addr->getNext());
-  }
-  llvm_unreachable("No owner in circular list");
-}
-
-// Add the phi node PA to the given block node.
-void BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G) {
-  NodeAddr<NodeBase*> M = getFirstMember(G);
-  if (M.Id == 0) {
-    addMember(PA, G);
-    return;
-  }
-
-  assert(M.Addr->getType() == NodeAttrs::Code);
-  if (M.Addr->getKind() == NodeAttrs::Stmt) {
-    // If the first member of the block is a statement, insert the phi as
-    // the first member.
-    Code.FirstM = PA.Id;
-    PA.Addr->setNext(M.Id);
-  } else {
-    // If the first member is a phi, find the last phi, and append PA to it.
-    assert(M.Addr->getKind() == NodeAttrs::Phi);
-    NodeAddr<NodeBase*> MN = M;
-    do {
-      M = MN;
-      MN = G.addr<NodeBase*>(M.Addr->getNext());
-      assert(MN.Addr->getType() == NodeAttrs::Code);
-    } while (MN.Addr->getKind() == NodeAttrs::Phi);
-
-    // M is the last phi.
-    addMemberAfter(M, PA, G);
-  }
-}
-
-// Find the block node corresponding to the machine basic block BB in the
-// given func node.
-NodeAddr<BlockNode*> FuncNode::findBlock(const MachineBasicBlock *BB,
-      const DataFlowGraph &G) const {
-  auto EqBB = [BB] (NodeAddr<NodeBase*> NA) -> bool {
-    return NodeAddr<BlockNode*>(NA).Addr->getCode() == BB;
-  };
-  NodeList Ms = members_if(EqBB, G);
-  if (!Ms.empty())
-    return Ms[0];
-  return NodeAddr<BlockNode*>();
-}
-
-// Get the block node for the entry block in the given function.
-NodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) {
-  MachineBasicBlock *EntryB = &getCode()->front();
-  return findBlock(EntryB, G);
-}
-
-// Target operand information.
-//
-
-// For a given instruction, check if there are any bits of RR that can remain
-// unchanged across this def.
-bool TargetOperandInfo::isPreserving(const MachineInstr &In, unsigned OpNum)
-      const {
-  return TII.isPredicated(In);
-}
-
-// Check if the definition of RR produces an unspecified value.
-bool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum)
-      const {
-  const MachineOperand &Op = In.getOperand(OpNum);
-  if (Op.isRegMask())
-    return true;
-  assert(Op.isReg());
-  if (In.isCall())
-    if (Op.isDef() && Op.isDead())
-      return true;
-  return false;
-}
-
-// Check if the given instruction specifically requires
-bool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum)
-      const {
-  if (In.isCall() || In.isReturn() || In.isInlineAsm())
-    return true;
-  // Check for a tail call.
-  if (In.isBranch())
-    for (const MachineOperand &O : In.operands())
-      if (O.isGlobal() || O.isSymbol())
-        return true;
-
-  const MCInstrDesc &D = In.getDesc();
-  if (!D.getImplicitDefs() && !D.getImplicitUses())
-    return false;
-  const MachineOperand &Op = In.getOperand(OpNum);
-  // If there is a sub-register, treat the operand as non-fixed. Currently,
-  // fixed registers are those that are listed in the descriptor as implicit
-  // uses or defs, and those lists do not allow sub-registers.
-  if (Op.getSubReg() != 0)
-    return false;
-  Register Reg = Op.getReg();
-  const MCPhysReg *ImpR = Op.isDef() ? D.getImplicitDefs()
-                                     : D.getImplicitUses();
-  if (!ImpR)
-    return false;
-  while (*ImpR)
-    if (*ImpR++ == Reg)
-      return true;
-  return false;
-}
-
-//
-// The data flow graph construction.
-//
-
-DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
-      const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
-      const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi)
-    : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi),
-      LiveIns(PRI) {
-}
-
-// The implementation of the definition stack.
-// Each register reference has its own definition stack. In particular,
-// for a register references "Reg" and "Reg:subreg" will each have their
-// own definition stacks.
-
-// Construct a stack iterator.
-DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S,
-      bool Top) : DS(S) {
-  if (!Top) {
-    // Initialize to bottom.
-    Pos = 0;
-    return;
-  }
-  // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty).
-  Pos = DS.Stack.size();
-  while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos-1]))
-    Pos--;
-}
-
-// Return the size of the stack, including block delimiters.
-unsigned DataFlowGraph::DefStack::size() const {
-  unsigned S = 0;
-  for (auto I = top(), E = bottom(); I != E; I.down())
-    S++;
-  return S;
-}
-
-// Remove the top entry from the stack. Remove all intervening delimiters
-// so that after this, the stack is either empty, or the top of the stack
-// is a non-delimiter.
-void DataFlowGraph::DefStack::pop() {
-  assert(!empty());
-  unsigned P = nextDown(Stack.size());
-  Stack.resize(P);
-}
-
-// Push a delimiter for block node N on the stack.
-void DataFlowGraph::DefStack::start_block(NodeId N) {
-  assert(N != 0);
-  Stack.push_back(NodeAddr<DefNode*>(nullptr, N));
-}
-
-// Remove all nodes from the top of the stack, until the delimited for
-// block node N is encountered. Remove the delimiter as well. In effect,
-// this will remove from the stack all definitions from block N.
-void DataFlowGraph::DefStack::clear_block(NodeId N) {
-  assert(N != 0);
-  unsigned P = Stack.size();
-  while (P > 0) {
-    bool Found = isDelimiter(Stack[P-1], N);
-    P--;
-    if (Found)
-      break;
-  }
-  // This will also remove the delimiter, if found.
-  Stack.resize(P);
-}
-
-// Move the stack iterator up by one.
-unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const {
-  // Get the next valid position after P (skipping all delimiters).
-  // The input position P does not have to point to a non-delimiter.
-  unsigned SS = Stack.size();
-  bool IsDelim;
-  assert(P < SS);
-  do {
-    P++;
-    IsDelim = isDelimiter(Stack[P-1]);
-  } while (P < SS && IsDelim);
-  assert(!IsDelim);
-  return P;
-}
-
-// Move the stack iterator down by one.
-unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const {
-  // Get the preceding valid position before P (skipping all delimiters).
-  // The input position P does not have to point to a non-delimiter.
-  assert(P > 0 && P <= Stack.size());
-  bool IsDelim = isDelimiter(Stack[P-1]);
-  do {
-    if (--P == 0)
-      break;
-    IsDelim = isDelimiter(Stack[P-1]);
-  } while (P > 0 && IsDelim);
-  assert(!IsDelim);
-  return P;
-}
-
-// Register information.
-
-RegisterSet DataFlowGraph::getLandingPadLiveIns() const {
-  RegisterSet LR;
-  const Function &F = MF.getFunction();
-  const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn()
-                                            : nullptr;
-  const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
-  if (RegisterId R = TLI.getExceptionPointerRegister(PF))
-    LR.insert(RegisterRef(R));
-  if (RegisterId R = TLI.getExceptionSelectorRegister(PF))
-    LR.insert(RegisterRef(R));
-  return LR;
-}
-
-// Node management functions.
-
-// Get the pointer to the node with the id N.
-NodeBase *DataFlowGraph::ptr(NodeId N) const {
-  if (N == 0)
-    return nullptr;
-  return Memory.ptr(N);
-}
-
-// Get the id of the node at the address P.
-NodeId DataFlowGraph::id(const NodeBase *P) const {
-  if (P == nullptr)
-    return 0;
-  return Memory.id(P);
-}
-
-// Allocate a new node and set the attributes to Attrs.
-NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) {
-  NodeAddr<NodeBase*> P = Memory.New();
-  P.Addr->init();
-  P.Addr->setAttrs(Attrs);
-  return P;
-}
-
-// Make a copy of the given node B, except for the data-flow links, which
-// are set to 0.
-NodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) {
-  NodeAddr<NodeBase*> NA = newNode(0);
-  memcpy(NA.Addr, B.Addr, sizeof(NodeBase));
-  // Ref nodes need to have the data-flow links reset.
-  if (NA.Addr->getType() == NodeAttrs::Ref) {
-    NodeAddr<RefNode*> RA = NA;
-    RA.Addr->setReachingDef(0);
-    RA.Addr->setSibling(0);
-    if (NA.Addr->getKind() == NodeAttrs::Def) {
-      NodeAddr<DefNode*> DA = NA;
-      DA.Addr->setReachedDef(0);
-      DA.Addr->setReachedUse(0);
-    }
-  }
-  return NA;
-}
-
-// Allocation routines for specific node types/kinds.
-
-NodeAddr<UseNode*> DataFlowGraph::newUse(NodeAddr<InstrNode*> Owner,
-      MachineOperand &Op, uint16_t Flags) {
-  NodeAddr<UseNode*> UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
-  UA.Addr->setRegRef(&Op, *this);
-  return UA;
-}
-
-NodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner,
-      RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) {
-  NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);
-  assert(Flags & NodeAttrs::PhiRef);
-  PUA.Addr->setRegRef(RR, *this);
-  PUA.Addr->setPredecessor(PredB.Id);
-  return PUA;
-}
-
-NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner,
-      MachineOperand &Op, uint16_t Flags) {
-  NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
-  DA.Addr->setRegRef(&Op, *this);
-  return DA;
-}
-
-NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner,
-      RegisterRef RR, uint16_t Flags) {
-  NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);
-  assert(Flags & NodeAttrs::PhiRef);
-  DA.Addr->setRegRef(RR, *this);
-  return DA;
-}
-
-NodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) {
-  NodeAddr<PhiNode*> PA = newNode(NodeAttrs::Code | NodeAttrs::Phi);
-  Owner.Addr->addPhi(PA, *this);
-  return PA;
-}
-
-NodeAddr<StmtNode*> DataFlowGraph::newStmt(NodeAddr<BlockNode*> Owner,
-      MachineInstr *MI) {
-  NodeAddr<StmtNode*> SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt);
-  SA.Addr->setCode(MI);
-  Owner.Addr->addMember(SA, *this);
-  return SA;
-}
-
-NodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner,
-      MachineBasicBlock *BB) {
-  NodeAddr<BlockNode*> BA = newNode(NodeAttrs::Code | NodeAttrs::Block);
-  BA.Addr->setCode(BB);
-  Owner.Addr->addMember(BA, *this);
-  return BA;
-}
-
-NodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) {
-  NodeAddr<FuncNode*> FA = newNode(NodeAttrs::Code | NodeAttrs::Func);
-  FA.Addr->setCode(MF);
-  return FA;
-}
-
-// Build the data flow graph.
-void DataFlowGraph::build(unsigned Options) {
-  reset();
-  Func = newFunc(&MF);
-
-  if (MF.empty())
-    return;
-
-  for (MachineBasicBlock &B : MF) {
-    NodeAddr<BlockNode*> BA = newBlock(Func, &B);
-    BlockNodes.insert(std::make_pair(&B, BA));
-    for (MachineInstr &I : B) {
-      if (I.isDebugInstr())
-        continue;
-      buildStmt(BA, I);
-    }
-  }
-
-  NodeAddr<BlockNode*> EA = Func.Addr->getEntryBlock(*this);
-  NodeList Blocks = Func.Addr->members(*this);
-
-  // Collect information about block references.
-  RegisterSet AllRefs;
-  for (NodeAddr<BlockNode*> BA : Blocks)
-    for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
-      for (NodeAddr<RefNode*> RA : IA.Addr->members(*this))
-        AllRefs.insert(RA.Addr->getRegRef(*this));
-
-  // Collect function live-ins and entry block live-ins.
-  MachineRegisterInfo &MRI = MF.getRegInfo();
-  MachineBasicBlock &EntryB = *EA.Addr->getCode();
-  assert(EntryB.pred_empty() && "Function entry block has predecessors");
-  for (std::pair<unsigned,unsigned> P : MRI.liveins())
-    LiveIns.insert(RegisterRef(P.first));
-  if (MRI.tracksLiveness()) {
-    for (auto I : EntryB.liveins())
-      LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask));
-  }
-
-  // Add function-entry phi nodes for the live-in registers.
-  //for (std::pair<RegisterId,LaneBitmask> P : LiveIns) {
-  for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) {
-    RegisterRef RR = *I;
-    NodeAddr<PhiNode*> PA = newPhi(EA);
-    uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
-    NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
-    PA.Addr->addMember(DA, *this);
-  }
-
-  // Add phis for landing pads.
-  // Landing pads, unlike usual backs blocks, are not entered through
-  // branches in the program, or fall-throughs from other blocks. They
-  // are entered from the exception handling runtime and target's ABI
-  // may define certain registers as defined on entry to such a block.
-  RegisterSet EHRegs = getLandingPadLiveIns();
-  if (!EHRegs.empty()) {
-    for (NodeAddr<BlockNode*> BA : Blocks) {
-      const MachineBasicBlock &B = *BA.Addr->getCode();
-      if (!B.isEHPad())
-        continue;
-
-      // Prepare a list of NodeIds of the block's predecessors.
-      NodeList Preds;
-      for (MachineBasicBlock *PB : B.predecessors())
-        Preds.push_back(findBlock(PB));
-
-      // Build phi nodes for each live-in.
-      for (RegisterRef RR : EHRegs) {
-        NodeAddr<PhiNode*> PA = newPhi(BA);
-        uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
-        // Add def:
-        NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
-        PA.Addr->addMember(DA, *this);
-        // Add uses (no reaching defs for phi uses):
-        for (NodeAddr<BlockNode*> PBA : Preds) {
-          NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
-          PA.Addr->addMember(PUA, *this);
-        }
-      }
-    }
-  }
-
-  // Build a map "PhiM" which will contain, for each block, the set
-  // of references that will require phi definitions in that block.
-  BlockRefsMap PhiM;
-  for (NodeAddr<BlockNode*> BA : Blocks)
-    recordDefsForDF(PhiM, BA);
-  for (NodeAddr<BlockNode*> BA : Blocks)
-    buildPhis(PhiM, AllRefs, BA);
-
-  // Link all the refs. This will recursively traverse the dominator tree.
-  DefStackMap DM;
-  linkBlockRefs(DM, EA);
-
-  // Finally, remove all unused phi nodes.
-  if (!(Options & BuildOptions::KeepDeadPhis))
-    removeUnusedPhis();
-}
-
-RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
-  assert(PhysicalRegisterInfo::isRegMaskId(Reg) ||
-         Register::isPhysicalRegister(Reg));
-  assert(Reg != 0);
-  if (Sub != 0)
-    Reg = TRI.getSubReg(Reg, Sub);
-  return RegisterRef(Reg);
-}
-
-RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const {
-  assert(Op.isReg() || Op.isRegMask());
-  if (Op.isReg())
-    return makeRegRef(Op.getReg(), Op.getSubReg());
-  return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll());
-}
-
-RegisterRef DataFlowGraph::restrictRef(RegisterRef AR, RegisterRef BR) const {
-  if (AR.Reg == BR.Reg) {
-    LaneBitmask M = AR.Mask & BR.Mask;
-    return M.any() ? RegisterRef(AR.Reg, M) : RegisterRef();
-  }
-#ifndef NDEBUG
-//  RegisterRef NAR = PRI.normalize(AR);
-//  RegisterRef NBR = PRI.normalize(BR);
-//  assert(NAR.Reg != NBR.Reg);
-#endif
-  // This isn't strictly correct, because the overlap may happen in the
-  // part masked out.
-  if (PRI.alias(AR, BR))
-    return AR;
-  return RegisterRef();
-}
-
-// For each stack in the map DefM, push the delimiter for block B on it.
-void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) {
-  // Push block delimiters.
-  for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I)
-    I->second.start_block(B);
-}
-
-// Remove all definitions coming from block B from each stack in DefM.
-void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) {
-  // Pop all defs from this block from the definition stack. Defs that were
-  // added to the map during the traversal of instructions will not have a
-  // delimiter, but for those, the whole stack will be emptied.
-  for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I)
-    I->second.clear_block(B);
-
-  // Finally, remove empty stacks from the map.
-  for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {
-    NextI = std::next(I);
-    // This preserves the validity of iterators other than I.
-    if (I->second.empty())
-      DefM.erase(I);
-  }
-}
-
-// Push all definitions from the instruction node IA to an appropriate
-// stack in DefM.
-void DataFlowGraph::pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
-  pushClobbers(IA, DefM);
-  pushDefs(IA, DefM);
-}
-
-// Push all definitions from the instruction node IA to an appropriate
-// stack in DefM.
-void DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
-  NodeSet Visited;
-  std::set<RegisterId> Defined;
-
-  // The important objectives of this function are:
-  // - to be able to handle instructions both while the graph is being
-  //   constructed, and after the graph has been constructed, and
-  // - maintain proper ordering of definitions on the stack for each
-  //   register reference:
-  //   - if there are two or more related defs in IA (i.e. coming from
-  //     the same machine operand), then only push one def on the stack,
-  //   - if there are multiple unrelated defs of non-overlapping
-  //     subregisters of S, then the stack for S will have both (in an
-  //     unspecified order), but the order does not matter from the data-
-  //     -flow perspective.
-
-  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
-    if (Visited.count(DA.Id))
-      continue;
-    if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))
-      continue;
-
-    NodeList Rel = getRelatedRefs(IA, DA);
-    NodeAddr<DefNode*> PDA = Rel.front();
-    RegisterRef RR = PDA.Addr->getRegRef(*this);
-
-    // Push the definition on the stack for the register and all aliases.
-    // The def stack traversal in linkNodeUp will check the exact aliasing.
-    DefM[RR.Reg].push(DA);
-    Defined.insert(RR.Reg);
-    for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
-      // Check that we don't push the same def twice.
-      assert(A != RR.Reg);
-      if (!Defined.count(A))
-        DefM[A].push(DA);
-    }
-    // Mark all the related defs as visited.
-    for (NodeAddr<NodeBase*> T : Rel)
-      Visited.insert(T.Id);
-  }
-}
-
-// Push all definitions from the instruction node IA to an appropriate
-// stack in DefM.
-void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
-  NodeSet Visited;
-#ifndef NDEBUG
-  std::set<RegisterId> Defined;
-#endif
-
-  // The important objectives of this function are:
-  // - to be able to handle instructions both while the graph is being
-  //   constructed, and after the graph has been constructed, and
-  // - maintain proper ordering of definitions on the stack for each
-  //   register reference:
-  //   - if there are two or more related defs in IA (i.e. coming from
-  //     the same machine operand), then only push one def on the stack,
-  //   - if there are multiple unrelated defs of non-overlapping
-  //     subregisters of S, then the stack for S will have both (in an
-  //     unspecified order), but the order does not matter from the data-
-  //     -flow perspective.
-
-  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
-    if (Visited.count(DA.Id))
-      continue;
-    if (DA.Addr->getFlags() & NodeAttrs::Clobbering)
-      continue;
-
-    NodeList Rel = getRelatedRefs(IA, DA);
-    NodeAddr<DefNode*> PDA = Rel.front();
-    RegisterRef RR = PDA.Addr->getRegRef(*this);
-#ifndef NDEBUG
-    // Assert if the register is defined in two or more unrelated defs.
-    // This could happen if there are two or more def operands defining it.
-    if (!Defined.insert(RR.Reg).second) {
-      MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
-      dbgs() << "Multiple definitions of register: "
-             << Print<RegisterRef>(RR, *this) << " in\n  " << *MI << "in "
-             << printMBBReference(*MI->getParent()) << '\n';
-      llvm_unreachable(nullptr);
-    }
-#endif
-    // Push the definition on the stack for the register and all aliases.
-    // The def stack traversal in linkNodeUp will check the exact aliasing.
-    DefM[RR.Reg].push(DA);
-    for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
-      // Check that we don't push the same def twice.
-      assert(A != RR.Reg);
-      DefM[A].push(DA);
-    }
-    // Mark all the related defs as visited.
-    for (NodeAddr<NodeBase*> T : Rel)
-      Visited.insert(T.Id);
-  }
-}
-
-// Return the list of all reference nodes related to RA, including RA itself.
-// See "getNextRelated" for the meaning of a "related reference".
-NodeList DataFlowGraph::getRelatedRefs(NodeAddr<InstrNode*> IA,
-      NodeAddr<RefNode*> RA) const {
-  assert(IA.Id != 0 && RA.Id != 0);
-
-  NodeList Refs;
-  NodeId Start = RA.Id;
-  do {
-    Refs.push_back(RA);
-    RA = getNextRelated(IA, RA);
-  } while (RA.Id != 0 && RA.Id != Start);
-  return Refs;
-}
-
-// Clear all information in the graph.
-void DataFlowGraph::reset() {
-  Memory.clear();
-  BlockNodes.clear();
-  Func = NodeAddr<FuncNode*>();
-}
-
-// Return the next reference node in the instruction node IA that is related
-// to RA. Conceptually, two reference nodes are related if they refer to the
-// same instance of a register access, but differ in flags or other minor
-// characteristics. Specific examples of related nodes are shadow reference
-// nodes.
-// Return the equivalent of nullptr if there are no more related references.
-NodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA,
-      NodeAddr<RefNode*> RA) const {
-  assert(IA.Id != 0 && RA.Id != 0);
-
-  auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool {
-    if (TA.Addr->getKind() != RA.Addr->getKind())
-      return false;
-    if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this))
-      return false;
-    return true;
-  };
-  auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
-    return Related(TA) &&
-           &RA.Addr->getOp() == &TA.Addr->getOp();
-  };
-  auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
-    if (!Related(TA))
-      return false;
-    if (TA.Addr->getKind() != NodeAttrs::Use)
-      return true;
-    // For phi uses, compare predecessor blocks.
-    const NodeAddr<const PhiUseNode*> TUA = TA;
-    const NodeAddr<const PhiUseNode*> RUA = RA;
-    return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor();
-  };
-
-  RegisterRef RR = RA.Addr->getRegRef(*this);
-  if (IA.Addr->getKind() == NodeAttrs::Stmt)
-    return RA.Addr->getNextRef(RR, RelatedStmt, true, *this);
-  return RA.Addr->getNextRef(RR, RelatedPhi, true, *this);
-}
-
-// Find the next node related to RA in IA that satisfies condition P.
-// If such a node was found, return a pair where the second element is the
-// located node. If such a node does not exist, return a pair where the
-// first element is the element after which such a node should be inserted,
-// and the second element is a null-address.
-template <typename Predicate>
-std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
-DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
-      Predicate P) const {
-  assert(IA.Id != 0 && RA.Id != 0);
-
-  NodeAddr<RefNode*> NA;
-  NodeId Start = RA.Id;
-  while (true) {
-    NA = getNextRelated(IA, RA);
-    if (NA.Id == 0 || NA.Id == Start)
-      break;
-    if (P(NA))
-      break;
-    RA = NA;
-  }
-
-  if (NA.Id != 0 && NA.Id != Start)
-    return std::make_pair(RA, NA);
-  return std::make_pair(RA, NodeAddr<RefNode*>());
-}
-
-// Get the next shadow node in IA corresponding to RA, and optionally create
-// such a node if it does not exist.
-NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA,
-      NodeAddr<RefNode*> RA, bool Create) {
-  assert(IA.Id != 0 && RA.Id != 0);
-
-  uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
-  auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
-    return TA.Addr->getFlags() == Flags;
-  };
-  auto Loc = locateNextRef(IA, RA, IsShadow);
-  if (Loc.second.Id != 0 || !Create)
-    return Loc.second;
-
-  // Create a copy of RA and mark is as shadow.
-  NodeAddr<RefNode*> NA = cloneNode(RA);
-  NA.Addr->setFlags(Flags | NodeAttrs::Shadow);
-  IA.Addr->addMemberAfter(Loc.first, NA, *this);
-  return NA;
-}
-
-// Get the next shadow node in IA corresponding to RA. Return null-address
-// if such a node does not exist.
-NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA,
-      NodeAddr<RefNode*> RA) const {
-  assert(IA.Id != 0 && RA.Id != 0);
-  uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
-  auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
-    return TA.Addr->getFlags() == Flags;
-  };
-  return locateNextRef(IA, RA, IsShadow).second;
-}
-
-// Create a new statement node in the block node BA that corresponds to
-// the machine instruction MI.
-void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) {
-  NodeAddr<StmtNode*> SA = newStmt(BA, &In);
-
-  auto isCall = [] (const MachineInstr &In) -> bool {
-    if (In.isCall())
-      return true;
-    // Is tail call?
-    if (In.isBranch()) {
-      for (const MachineOperand &Op : In.operands())
-        if (Op.isGlobal() || Op.isSymbol())
-          return true;
-      // Assume indirect branches are calls. This is for the purpose of
-      // keeping implicit operands, and so it won't hurt on intra-function
-      // indirect branches.
-      if (In.isIndirectBranch())
-        return true;
-    }
-    return false;
-  };
-
-  auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool {
-    // This instruction defines DR. Check if there is a use operand that
-    // would make DR live on entry to the instruction.
-    for (const MachineOperand &Op : In.operands()) {
-      if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef())
-        continue;
-      RegisterRef UR = makeRegRef(Op);
-      if (PRI.alias(DR, UR))
-        return false;
-    }
-    return true;
-  };
-
-  bool IsCall = isCall(In);
-  unsigned NumOps = In.getNumOperands();
-
-  // Avoid duplicate implicit defs. This will not detect cases of implicit
-  // defs that define registers that overlap, but it is not clear how to
-  // interpret that in the absence of explicit defs. Overlapping explicit
-  // defs are likely illegal already.
-  BitVector DoneDefs(TRI.getNumRegs());
-  // Process explicit defs first.
-  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
-    MachineOperand &Op = In.getOperand(OpN);
-    if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
-      continue;
-    Register R = Op.getReg();
-    if (!R || !Register::isPhysicalRegister(R))
-      continue;
-    uint16_t Flags = NodeAttrs::None;
-    if (TOI.isPreserving(In, OpN)) {
-      Flags |= NodeAttrs::Preserving;
-      // If the def is preserving, check if it is also undefined.
-      if (isDefUndef(In, makeRegRef(Op)))
-        Flags |= NodeAttrs::Undef;
-    }
-    if (TOI.isClobbering(In, OpN))
-      Flags |= NodeAttrs::Clobbering;
-    if (TOI.isFixedReg(In, OpN))
-      Flags |= NodeAttrs::Fixed;
-    if (IsCall && Op.isDead())
-      Flags |= NodeAttrs::Dead;
-    NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
-    SA.Addr->addMember(DA, *this);
-    assert(!DoneDefs.test(R));
-    DoneDefs.set(R);
-  }
-
-  // Process reg-masks (as clobbers).
-  BitVector DoneClobbers(TRI.getNumRegs());
-  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
-    MachineOperand &Op = In.getOperand(OpN);
-    if (!Op.isRegMask())
-      continue;
-    uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed |
-                     NodeAttrs::Dead;
-    NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
-    SA.Addr->addMember(DA, *this);
-    // Record all clobbered registers in DoneDefs.
-    const uint32_t *RM = Op.getRegMask();
-    for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i)
-      if (!(RM[i/32] & (1u << (i%32))))
-        DoneClobbers.set(i);
-  }
-
-  // Process implicit defs, skipping those that have already been added
-  // as explicit.
-  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
-    MachineOperand &Op = In.getOperand(OpN);
-    if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())
-      continue;
-    Register R = Op.getReg();
-    if (!R || !Register::isPhysicalRegister(R) || DoneDefs.test(R))
-      continue;
-    RegisterRef RR = makeRegRef(Op);
-    uint16_t Flags = NodeAttrs::None;
-    if (TOI.isPreserving(In, OpN)) {
-      Flags |= NodeAttrs::Preserving;
-      // If the def is preserving, check if it is also undefined.
-      if (isDefUndef(In, RR))
-        Flags |= NodeAttrs::Undef;
-    }
-    if (TOI.isClobbering(In, OpN))
-      Flags |= NodeAttrs::Clobbering;
-    if (TOI.isFixedReg(In, OpN))
-      Flags |= NodeAttrs::Fixed;
-    if (IsCall && Op.isDead()) {
-      if (DoneClobbers.test(R))
-        continue;
-      Flags |= NodeAttrs::Dead;
-    }
-    NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
-    SA.Addr->addMember(DA, *this);
-    DoneDefs.set(R);
-  }
-
-  for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
-    MachineOperand &Op = In.getOperand(OpN);
-    if (!Op.isReg() || !Op.isUse())
-      continue;
-    Register R = Op.getReg();
-    if (!R || !Register::isPhysicalRegister(R))
-      continue;
-    uint16_t Flags = NodeAttrs::None;
-    if (Op.isUndef())
-      Flags |= NodeAttrs::Undef;
-    if (TOI.isFixedReg(In, OpN))
-      Flags |= NodeAttrs::Fixed;
-    NodeAddr<UseNode*> UA = newUse(SA, Op, Flags);
-    SA.Addr->addMember(UA, *this);
-  }
-}
-
-// Scan all defs in the block node BA and record in PhiM the locations of
-// phi nodes corresponding to these defs.
-void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,
-      NodeAddr<BlockNode*> BA) {
-  // Check all defs from block BA and record them in each block in BA's
-  // iterated dominance frontier. This information will later be used to
-  // create phi nodes.
-  MachineBasicBlock *BB = BA.Addr->getCode();
-  assert(BB);
-  auto DFLoc = MDF.find(BB);
-  if (DFLoc == MDF.end() || DFLoc->second.empty())
-    return;
-
-  // Traverse all instructions in the block and collect the set of all
-  // defined references. For each reference there will be a phi created
-  // in the block's iterated dominance frontier.
-  // This is done to make sure that each defined reference gets only one
-  // phi node, even if it is defined multiple times.
-  RegisterSet Defs;
-  for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
-    for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this))
-      Defs.insert(RA.Addr->getRegRef(*this));
-
-  // Calculate the iterated dominance frontier of BB.
-  const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;
-  SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end());
-  for (unsigned i = 0; i < IDF.size(); ++i) {
-    auto F = MDF.find(IDF[i]);
-    if (F != MDF.end())
-      IDF.insert(F->second.begin(), F->second.end());
-  }
-
-  // Finally, add the set of defs to each block in the iterated dominance
-  // frontier.
-  for (auto DB : IDF) {
-    NodeAddr<BlockNode*> DBA = findBlock(DB);
-    PhiM[DBA.Id].insert(Defs.begin(), Defs.end());
-  }
-}
-
-// Given the locations of phi nodes in the map PhiM, create the phi nodes
-// that are located in the block node BA.
-void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
-      NodeAddr<BlockNode*> BA) {
-  // Check if this blocks has any DF defs, i.e. if there are any defs
-  // that this block is in the iterated dominance frontier of.
-  auto HasDF = PhiM.find(BA.Id);
-  if (HasDF == PhiM.end() || HasDF->second.empty())
-    return;
-
-  // First, remove all R in Refs in such that there exists T in Refs
-  // such that T covers R. In other words, only leave those refs that
-  // are not covered by another ref (i.e. maximal with respect to covering).
-
-  auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef {
-    for (RegisterRef I : RRs)
-      if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI))
-        RR = I;
-    return RR;
-  };
-
-  RegisterSet MaxDF;
-  for (RegisterRef I : HasDF->second)
-    MaxDF.insert(MaxCoverIn(I, HasDF->second));
-
-  std::vector<RegisterRef> MaxRefs;
-  for (RegisterRef I : MaxDF)
-    MaxRefs.push_back(MaxCoverIn(I, AllRefs));
-
-  // Now, for each R in MaxRefs, get the alias closure of R. If the closure
-  // only has R in it, create a phi a def for R. Otherwise, create a phi,
-  // and add a def for each S in the closure.
-
-  // Sort the refs so that the phis will be created in a deterministic order.
-  llvm::sort(MaxRefs);
-  // Remove duplicates.
-  auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end());
-  MaxRefs.erase(NewEnd, MaxRefs.end());
-
-  auto Aliased = [this,&MaxRefs](RegisterRef RR,
-                                 std::vector<unsigned> &Closure) -> bool {
-    for (unsigned I : Closure)
-      if (PRI.alias(RR, MaxRefs[I]))
-        return true;
-    return false;
-  };
-
-  // Prepare a list of NodeIds of the block's predecessors.
-  NodeList Preds;
-  const MachineBasicBlock *MBB = BA.Addr->getCode();
-  for (MachineBasicBlock *PB : MBB->predecessors())
-    Preds.push_back(findBlock(PB));
-
-  while (!MaxRefs.empty()) {
-    // Put the first element in the closure, and then add all subsequent
-    // elements from MaxRefs to it, if they alias at least one element
-    // already in the closure.
-    // ClosureIdx: vector of indices in MaxRefs of members of the closure.
-    std::vector<unsigned> ClosureIdx = { 0 };
-    for (unsigned i = 1; i != MaxRefs.size(); ++i)
-      if (Aliased(MaxRefs[i], ClosureIdx))
-        ClosureIdx.push_back(i);
-
-    // Build a phi for the closure.
-    unsigned CS = ClosureIdx.size();
-    NodeAddr<PhiNode*> PA = newPhi(BA);
-
-    // Add defs.
-    for (unsigned X = 0; X != CS; ++X) {
-      RegisterRef RR = MaxRefs[ClosureIdx[X]];
-      uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
-      NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
-      PA.Addr->addMember(DA, *this);
-    }
-    // Add phi uses.
-    for (NodeAddr<BlockNode*> PBA : Preds) {
-      for (unsigned X = 0; X != CS; ++X) {
-        RegisterRef RR = MaxRefs[ClosureIdx[X]];
-        NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
-        PA.Addr->addMember(PUA, *this);
-      }
-    }
-
-    // Erase from MaxRefs all elements in the closure.
-    auto Begin = MaxRefs.begin();
-    for (unsigned i = ClosureIdx.size(); i != 0; --i)
-      MaxRefs.erase(Begin + ClosureIdx[i-1]);
-  }
-}
-
-// Remove any unneeded phi nodes that were created during the build process.
-void DataFlowGraph::removeUnusedPhis() {
-  // This will remove unused phis, i.e. phis where each def does not reach
-  // any uses or other defs. This will not detect or remove circular phi
-  // chains that are otherwise dead. Unused/dead phis are created during
-  // the build process and this function is intended to remove these cases
-  // that are easily determinable to be unnecessary.
-
-  SetVector<NodeId> PhiQ;
-  for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) {
-    for (auto P : BA.Addr->members_if(IsPhi, *this))
-      PhiQ.insert(P.Id);
-  }
-
-  static auto HasUsedDef = [](NodeList &Ms) -> bool {
-    for (NodeAddr<NodeBase*> M : Ms) {
-      if (M.Addr->getKind() != NodeAttrs::Def)
-        continue;
-      NodeAddr<DefNode*> DA = M;
-      if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)
-        return true;
-    }
-    return false;
-  };
-
-  // Any phi, if it is removed, may affect other phis (make them dead).
-  // For each removed phi, collect the potentially affected phis and add
-  // them back to the queue.
-  while (!PhiQ.empty()) {
-    auto PA = addr<PhiNode*>(PhiQ[0]);
-    PhiQ.remove(PA.Id);
-    NodeList Refs = PA.Addr->members(*this);
-    if (HasUsedDef(Refs))
-      continue;
-    for (NodeAddr<RefNode*> RA : Refs) {
-      if (NodeId RD = RA.Addr->getReachingDef()) {
-        auto RDA = addr<DefNode*>(RD);
-        NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this);
-        if (IsPhi(OA))
-          PhiQ.insert(OA.Id);
-      }
-      if (RA.Addr->isDef())
-        unlinkDef(RA, true);
-      else
-        unlinkUse(RA, true);
-    }
-    NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this);
-    BA.Addr->removeMember(PA, *this);
-  }
-}
-
-// For a given reference node TA in an instruction node IA, connect the
-// reaching def of TA to the appropriate def node. Create any shadow nodes
-// as appropriate.
-template <typename T>
-void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA,
-      DefStack &DS) {
-  if (DS.empty())
-    return;
-  RegisterRef RR = TA.Addr->getRegRef(*this);
-  NodeAddr<T> TAP;
-
-  // References from the def stack that have been examined so far.
-  RegisterAggr Defs(PRI);
-
-  for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {
-    RegisterRef QR = I->Addr->getRegRef(*this);
-
-    // Skip all defs that are aliased to any of the defs that we have already
-    // seen. If this completes a cover of RR, stop the stack traversal.
-    bool Alias = Defs.hasAliasOf(QR);
-    bool Cover = Defs.insert(QR).hasCoverOf(RR);
-    if (Alias) {
-      if (Cover)
-        break;
-      continue;
-    }
-
-    // The reaching def.
-    NodeAddr<DefNode*> RDA = *I;
-
-    // Pick the reached node.
-    if (TAP.Id == 0) {
-      TAP = TA;
-    } else {
-      // Mark the existing ref as "shadow" and create a new shadow.
-      TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);
-      TAP = getNextShadow(IA, TAP, true);
-    }
-
-    // Create the link.
-    TAP.Addr->linkToDef(TAP.Id, RDA);
-
-    if (Cover)
-      break;
-  }
-}
-
-// Create data-flow links for all reference nodes in the statement node SA.
-template <typename Predicate>
-void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA,
-      Predicate P) {
-#ifndef NDEBUG
-  RegisterSet Defs;
-#endif
-
-  // Link all nodes (upwards in the data-flow) with their reaching defs.
-  for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) {
-    uint16_t Kind = RA.Addr->getKind();
-    assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use);
-    RegisterRef RR = RA.Addr->getRegRef(*this);
-#ifndef NDEBUG
-    // Do not expect multiple defs of the same reference.
-    assert(Kind != NodeAttrs::Def || !Defs.count(RR));
-    Defs.insert(RR);
-#endif
-
-    auto F = DefM.find(RR.Reg);
-    if (F == DefM.end())
-      continue;
-    DefStack &DS = F->second;
-    if (Kind == NodeAttrs::Use)
-      linkRefUp<UseNode*>(SA, RA, DS);
-    else if (Kind == NodeAttrs::Def)
-      linkRefUp<DefNode*>(SA, RA, DS);
-    else
-      llvm_unreachable("Unexpected node in instruction");
-  }
-}
-
-// Create data-flow links for all instructions in the block node BA. This
-// will include updating any phi nodes in BA.
-void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) {
-  // Push block delimiters.
-  markBlock(BA.Id, DefM);
-
-  auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool {
-    return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);
-  };
-  auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool {
-    return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);
-  };
-
-  assert(BA.Addr && "block node address is needed to create a data-flow link");
-  // For each non-phi instruction in the block, link all the defs and uses
-  // to their reaching defs. For any member of the block (including phis),
-  // push the defs on the corresponding stacks.
-  for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) {
-    // Ignore phi nodes here. They will be linked part by part from the
-    // predecessors.
-    if (IA.Addr->getKind() == NodeAttrs::Stmt) {
-      linkStmtRefs(DefM, IA, IsUse);
-      linkStmtRefs(DefM, IA, IsClobber);
-    }
-
-    // Push the definitions on the stack.
-    pushClobbers(IA, DefM);
-
-    if (IA.Addr->getKind() == NodeAttrs::Stmt)
-      linkStmtRefs(DefM, IA, IsNoClobber);
-
-    pushDefs(IA, DefM);
-  }
-
-  // Recursively process all children in the dominator tree.
-  MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());
-  for (auto I : *N) {
-    MachineBasicBlock *SB = I->getBlock();
-    NodeAddr<BlockNode*> SBA = findBlock(SB);
-    linkBlockRefs(DefM, SBA);
-  }
-
-  // Link the phi uses from the successor blocks.
-  auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool {
-    if (NA.Addr->getKind() != NodeAttrs::Use)
-      return false;
-    assert(NA.Addr->getFlags() & NodeAttrs::PhiRef);
-    NodeAddr<PhiUseNode*> PUA = NA;
-    return PUA.Addr->getPredecessor() == BA.Id;
-  };
-
-  RegisterSet EHLiveIns = getLandingPadLiveIns();
-  MachineBasicBlock *MBB = BA.Addr->getCode();
-
-  for (MachineBasicBlock *SB : MBB->successors()) {
-    bool IsEHPad = SB->isEHPad();
-    NodeAddr<BlockNode*> SBA = findBlock(SB);
-    for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) {
-      // Do not link phi uses for landing pad live-ins.
-      if (IsEHPad) {
-        // Find what register this phi is for.
-        NodeAddr<RefNode*> RA = IA.Addr->getFirstMember(*this);
-        assert(RA.Id != 0);
-        if (EHLiveIns.count(RA.Addr->getRegRef(*this)))
-          continue;
-      }
-      // Go over each phi use associated with MBB, and link it.
-      for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {
-        NodeAddr<PhiUseNode*> PUA = U;
-        RegisterRef RR = PUA.Addr->getRegRef(*this);
-        linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]);
-      }
-    }
-  }
-
-  // Pop all defs from this block from the definition stacks.
-  releaseBlock(BA.Id, DefM);
-}
-
-// Remove the use node UA from any data-flow and structural links.
-void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) {
-  NodeId RD = UA.Addr->getReachingDef();
-  NodeId Sib = UA.Addr->getSibling();
-
-  if (RD == 0) {
-    assert(Sib == 0);
-    return;
-  }
-
-  auto RDA = addr<DefNode*>(RD);
-  auto TA = addr<UseNode*>(RDA.Addr->getReachedUse());
-  if (TA.Id == UA.Id) {
-    RDA.Addr->setReachedUse(Sib);
-    return;
-  }
-
-  while (TA.Id != 0) {
-    NodeId S = TA.Addr->getSibling();
-    if (S == UA.Id) {
-      TA.Addr->setSibling(UA.Addr->getSibling());
-      return;
-    }
-    TA = addr<UseNode*>(S);
-  }
-}
-
-// Remove the def node DA from any data-flow and structural links.
-void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) {
-  //
-  //         RD
-  //         | reached
-  //         | def
-  //         :
-  //         .
-  //        +----+
-  // ... -- | DA | -- ... -- 0  : sibling chain of DA
-  //        +----+
-  //         |  | reached
-  //         |  : def
-  //         |  .
-  //         | ...  : Siblings (defs)
-  //         |
-  //         : reached
-  //         . use
-  //        ... : sibling chain of reached uses
-
-  NodeId RD = DA.Addr->getReachingDef();
-
-  // Visit all siblings of the reached def and reset their reaching defs.
-  // Also, defs reached by DA are now "promoted" to being reached by RD,
-  // so all of them will need to be spliced into the sibling chain where
-  // DA belongs.
-  auto getAllNodes = [this] (NodeId N) -> NodeList {
-    NodeList Res;
-    while (N) {
-      auto RA = addr<RefNode*>(N);
-      // Keep the nodes in the exact sibling order.
-      Res.push_back(RA);
-      N = RA.Addr->getSibling();
-    }
-    return Res;
-  };
-  NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());
-  NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());
-
-  if (RD == 0) {
-    for (NodeAddr<RefNode*> I : ReachedDefs)
-      I.Addr->setSibling(0);
-    for (NodeAddr<RefNode*> I : ReachedUses)
-      I.Addr->setSibling(0);
-  }
-  for (NodeAddr<DefNode*> I : ReachedDefs)
-    I.Addr->setReachingDef(RD);
-  for (NodeAddr<UseNode*> I : ReachedUses)
-    I.Addr->setReachingDef(RD);
-
-  NodeId Sib = DA.Addr->getSibling();
-  if (RD == 0) {
-    assert(Sib == 0);
-    return;
-  }
-
-  // Update the reaching def node and remove DA from the sibling list.
-  auto RDA = addr<DefNode*>(RD);
-  auto TA = addr<DefNode*>(RDA.Addr->getReachedDef());
-  if (TA.Id == DA.Id) {
-    // If DA is the first reached def, just update the RD's reached def
-    // to the DA's sibling.
-    RDA.Addr->setReachedDef(Sib);
-  } else {
-    // Otherwise, traverse the sibling list of the reached defs and remove
-    // DA from it.
-    while (TA.Id != 0) {
-      NodeId S = TA.Addr->getSibling();
-      if (S == DA.Id) {
-        TA.Addr->setSibling(Sib);
-        break;
-      }
-      TA = addr<DefNode*>(S);
-    }
-  }
-
-  // Splice the DA's reached defs into the RDA's reached def chain.
-  if (!ReachedDefs.empty()) {
-    auto Last = NodeAddr<DefNode*>(ReachedDefs.back());
-    Last.Addr->setSibling(RDA.Addr->getReachedDef());
-    RDA.Addr->setReachedDef(ReachedDefs.front().Id);
-  }
-  // Splice the DA's reached uses into the RDA's reached use chain.
-  if (!ReachedUses.empty()) {
-    auto Last = NodeAddr<UseNode*>(ReachedUses.back());
-    Last.Addr->setSibling(RDA.Addr->getReachedUse());
-    RDA.Addr->setReachedUse(ReachedUses.front().Id);
-  }
-}
diff --git a/llvm/lib/Target/Hexagon/RDFGraph.h b/llvm/lib/Target/Hexagon/RDFGraph.h
deleted file mode 100644
index 585f43e116f..00000000000
--- a/llvm/lib/Target/Hexagon/RDFGraph.h
+++ /dev/null
@@ -1,968 +0,0 @@
-//===- 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*> getNextImp(NodeAddr<InstrNode*> IA,
-        NodeAddr<RefNode*> RA, bool Create);
-    NodeAddr<RefNode*> getNextImp(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
diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.cpp b/llvm/lib/Target/Hexagon/RDFLiveness.cpp
deleted file mode 100644
index e2c007c9d01..00000000000
--- a/llvm/lib/Target/Hexagon/RDFLiveness.cpp
+++ /dev/null
@@ -1,1118 +0,0 @@
-//===- RDFLiveness.cpp ----------------------------------------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-//
-// Computation of the liveness information from the data-flow graph.
-//
-// The main functionality of this code is to compute block live-in
-// information. With the live-in information in place, the placement
-// of kill flags can also be recalculated.
-//
-// The block live-in calculation is based on the ideas from the following
-// publication:
-//
-// Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin.
-// "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
-// ACM Transactions on Architecture and Code Optimization, Association for
-// Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
-// and Embedded Architectures and Compilers", 8 (4),
-// <10.1145/2086696.2086706>. <hal-00647369>
-//
-#include "RDFLiveness.h"
-#include "RDFGraph.h"
-#include "RDFRegisters.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
-#include "llvm/CodeGen/MachineDominanceFrontier.h"
-#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/MC/LaneBitmask.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <cassert>
-#include <cstdint>
-#include <iterator>
-#include <map>
-#include <utility>
-#include <vector>
-
-using namespace llvm;
-using namespace rdf;
-
-static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25),
-  cl::Hidden, cl::desc("Maximum recursion level"));
-
-namespace llvm {
-namespace rdf {
-
-  raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) {
-    OS << '{';
-    for (auto &I : P.Obj) {
-      OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{';
-      for (auto J = I.second.begin(), E = I.second.end(); J != E; ) {
-        OS << Print<NodeId>(J->first, P.G) << PrintLaneMaskOpt(J->second);
-        if (++J != E)
-          OS << ',';
-      }
-      OS << '}';
-    }
-    OS << " }";
-    return OS;
-  }
-
-} // end namespace rdf
-} // end namespace llvm
-
-// The order in the returned sequence is the order of reaching defs in the
-// upward traversal: the first def is the closest to the given reference RefA,
-// the next one is further up, and so on.
-// The list ends at a reaching phi def, or when the reference from RefA is
-// covered by the defs in the list (see FullChain).
-// This function provides two modes of operation:
-// (1) Returning the sequence of reaching defs for a particular reference
-// node. This sequence will terminate at the first phi node [1].
-// (2) Returning a partial sequence of reaching defs, where the final goal
-// is to traverse past phi nodes to the actual defs arising from the code
-// itself.
-// In mode (2), the register reference for which the search was started
-// may be different from the reference node RefA, for which this call was
-// made, hence the argument RefRR, which holds the original register.
-// Also, some definitions may have already been encountered in a previous
-// call that will influence register covering. The register references
-// already defined are passed in through DefRRs.
-// In mode (1), the "continuation" considerations do not apply, and the
-// RefRR is the same as the register in RefA, and the set DefRRs is empty.
-//
-// [1] It is possible for multiple phi nodes to be included in the returned
-// sequence:
-//   SubA = phi ...
-//   SubB = phi ...
-//   ...  = SuperAB(rdef:SubA), SuperAB"(rdef:SubB)
-// However, these phi nodes are independent from one another in terms of
-// the data-flow.
-
-NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
-      NodeAddr<RefNode*> RefA, bool TopShadows, bool FullChain,
-      const RegisterAggr &DefRRs) {
-  NodeList RDefs; // Return value.
-  SetVector<NodeId> DefQ;
-  SetVector<NodeId> Owners;
-
-  // Dead defs will be treated as if they were live, since they are actually
-  // on the data-flow path. They cannot be ignored because even though they
-  // do not generate meaningful values, they still modify registers.
-
-  // If the reference is undefined, there is nothing to do.
-  if (RefA.Addr->getFlags() & NodeAttrs::Undef)
-    return RDefs;
-
-  // The initial queue should not have reaching defs for shadows. The
-  // whole point of a shadow is that it will have a reaching def that
-  // is not aliased to the reaching defs of the related shadows.
-  NodeId Start = RefA.Id;
-  auto SNA = DFG.addr<RefNode*>(Start);
-  if (NodeId RD = SNA.Addr->getReachingDef())
-    DefQ.insert(RD);
-  if (TopShadows) {
-    for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA))
-      if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef())
-        DefQ.insert(RD);
-  }
-
-  // Collect all the reaching defs, going up until a phi node is encountered,
-  // or there are no more reaching defs. From this set, the actual set of
-  // reaching defs will be selected.
-  // The traversal upwards must go on until a covering def is encountered.
-  // It is possible that a collection of non-covering (individually) defs
-  // will be sufficient, but keep going until a covering one is found.
-  for (unsigned i = 0; i < DefQ.size(); ++i) {
-    auto TA = DFG.addr<DefNode*>(DefQ[i]);
-    if (TA.Addr->getFlags() & NodeAttrs::PhiRef)
-      continue;
-    // Stop at the covering/overwriting def of the initial register reference.
-    RegisterRef RR = TA.Addr->getRegRef(DFG);
-    if (!DFG.IsPreservingDef(TA))
-      if (RegisterAggr::isCoverOf(RR, RefRR, PRI))
-        continue;
-    // Get the next level of reaching defs. This will include multiple
-    // reaching defs for shadows.
-    for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA))
-      if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef())
-        DefQ.insert(RD);
-  }
-
-  // Remove all non-phi defs that are not aliased to RefRR, and collect
-  // the owners of the remaining defs.
-  SetVector<NodeId> Defs;
-  for (NodeId N : DefQ) {
-    auto TA = DFG.addr<DefNode*>(N);
-    bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef;
-    if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG)))
-      continue;
-    Defs.insert(TA.Id);
-    Owners.insert(TA.Addr->getOwner(DFG).Id);
-  }
-
-  // Return the MachineBasicBlock containing a given instruction.
-  auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* {
-    if (IA.Addr->getKind() == NodeAttrs::Stmt)
-      return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent();
-    assert(IA.Addr->getKind() == NodeAttrs::Phi);
-    NodeAddr<PhiNode*> PA = IA;
-    NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG);
-    return BA.Addr->getCode();
-  };
-  // Less(A,B) iff instruction A is further down in the dominator tree than B.
-  auto Less = [&Block,this] (NodeId A, NodeId B) -> bool {
-    if (A == B)
-      return false;
-    auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B);
-    MachineBasicBlock *BA = Block(OA), *BB = Block(OB);
-    if (BA != BB)
-      return MDT.dominates(BB, BA);
-    // They are in the same block.
-    bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt;
-    bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt;
-    if (StmtA) {
-      if (!StmtB)   // OB is a phi and phis dominate statements.
-        return true;
-      MachineInstr *CA = NodeAddr<StmtNode*>(OA).Addr->getCode();
-      MachineInstr *CB = NodeAddr<StmtNode*>(OB).Addr->getCode();
-      // The order must be linear, so tie-break such equalities.
-      if (CA == CB)
-        return A < B;
-      return MDT.dominates(CB, CA);
-    } else {
-      // OA is a phi.
-      if (StmtB)
-        return false;
-      // Both are phis. There is no ordering between phis (in terms of
-      // the data-flow), so tie-break this via node id comparison.
-      return A < B;
-    }
-  };
-
-  std::vector<NodeId> Tmp(Owners.begin(), Owners.end());
-  llvm::sort(Tmp, Less);
-
-  // The vector is a list of instructions, so that defs coming from
-  // the same instruction don't need to be artificially ordered.
-  // Then, when computing the initial segment, and iterating over an
-  // instruction, pick the defs that contribute to the covering (i.e. is
-  // not covered by previously added defs). Check the defs individually,
-  // i.e. first check each def if is covered or not (without adding them
-  // to the tracking set), and then add all the selected ones.
-
-  // The reason for this is this example:
-  // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes).
-  // *d3<C>              If A \incl BuC, and B \incl AuC, then *d2 would be
-  //                     covered if we added A first, and A would be covered
-  //                     if we added B first.
-
-  RegisterAggr RRs(DefRRs);
-
-  auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool {
-    return TA.Addr->getKind() == NodeAttrs::Def &&
-           Defs.count(TA.Id);
-  };
-  for (NodeId T : Tmp) {
-    if (!FullChain && RRs.hasCoverOf(RefRR))
-      break;
-    auto TA = DFG.addr<InstrNode*>(T);
-    bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA);
-    NodeList Ds;
-    for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) {
-      RegisterRef QR = DA.Addr->getRegRef(DFG);
-      // Add phi defs even if they are covered by subsequent defs. This is
-      // for cases where the reached use is not covered by any of the defs
-      // encountered so far: the phi def is needed to expose the liveness
-      // of that use to the entry of the block.
-      // Example:
-      //   phi d1<R3>(,d2,), ...  Phi def d1 is covered by d2.
-      //   d2<R3>(d1,,u3), ...
-      //   ..., u3<D1>(d2)        This use needs to be live on entry.
-      if (FullChain || IsPhi || !RRs.hasCoverOf(QR))
-        Ds.push_back(DA);
-    }
-    RDefs.insert(RDefs.end(), Ds.begin(), Ds.end());
-    for (NodeAddr<DefNode*> DA : Ds) {
-      // When collecting a full chain of definitions, do not consider phi
-      // defs to actually define a register.
-      uint16_t Flags = DA.Addr->getFlags();
-      if (!FullChain || !(Flags & NodeAttrs::PhiRef))
-        if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here.
-          RRs.insert(DA.Addr->getRegRef(DFG));
-    }
-  }
-
-  auto DeadP = [](const NodeAddr<DefNode*> DA) -> bool {
-    return DA.Addr->getFlags() & NodeAttrs::Dead;
-  };
-  RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP)));
-
-  return RDefs;
-}
-
-std::pair<NodeSet,bool>
-Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode*> RefA,
-      NodeSet &Visited, const NodeSet &Defs) {
-  return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest);
-}
-
-std::pair<NodeSet,bool>
-Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode*> RefA,
-      NodeSet &Visited, const NodeSet &Defs, unsigned Nest, unsigned MaxNest) {
-  if (Nest > MaxNest)
-    return { NodeSet(), false };
-  // Collect all defined registers. Do not consider phis to be defining
-  // anything, only collect "real" definitions.
-  RegisterAggr DefRRs(PRI);
-  for (NodeId D : Defs) {
-    const auto DA = DFG.addr<const DefNode*>(D);
-    if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
-      DefRRs.insert(DA.Addr->getRegRef(DFG));
-  }
-
-  NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs);
-  if (RDs.empty())
-    return { Defs, true };
-
-  // Make a copy of the preexisting definitions and add the newly found ones.
-  NodeSet TmpDefs = Defs;
-  for (NodeAddr<NodeBase*> R : RDs)
-    TmpDefs.insert(R.Id);
-
-  NodeSet Result = Defs;
-
-  for (NodeAddr<DefNode*> DA : RDs) {
-    Result.insert(DA.Id);
-    if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
-      continue;
-    NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG);
-    if (Visited.count(PA.Id))
-      continue;
-    Visited.insert(PA.Id);
-    // Go over all phi uses and get the reaching defs for each use.
-    for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
-      const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
-                                                Nest+1, MaxNest);
-      if (!T.second)
-        return { T.first, false };
-      Result.insert(T.first.begin(), T.first.end());
-    }
-  }
-
-  return { Result, true };
-}
-
-/// Find the nearest ref node aliased to RefRR, going upwards in the data
-/// flow, starting from the instruction immediately preceding Inst.
-NodeAddr<RefNode*> Liveness::getNearestAliasedRef(RegisterRef RefRR,
-      NodeAddr<InstrNode*> IA) {
-  NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
-  NodeList Ins = BA.Addr->members(DFG);
-  NodeId FindId = IA.Id;
-  auto E = Ins.rend();
-  auto B = std::find_if(Ins.rbegin(), E,
-                        [FindId] (const NodeAddr<InstrNode*> T) {
-                          return T.Id == FindId;
-                        });
-  // Do not scan IA (which is what B would point to).
-  if (B != E)
-    ++B;
-
-  do {
-    // Process the range of instructions from B to E.
-    for (NodeAddr<InstrNode*> I : make_range(B, E)) {
-      NodeList Refs = I.Addr->members(DFG);
-      NodeAddr<RefNode*> Clob, Use;
-      // Scan all the refs in I aliased to RefRR, and return the one that
-      // is the closest to the output of I, i.e. def > clobber > use.
-      for (NodeAddr<RefNode*> R : Refs) {
-        if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR))
-          continue;
-        if (DFG.IsDef(R)) {
-          // If it's a non-clobbering def, just return it.
-          if (!(R.Addr->getFlags() & NodeAttrs::Clobbering))
-            return R;
-          Clob = R;
-        } else {
-          Use = R;
-        }
-      }
-      if (Clob.Id != 0)
-        return Clob;
-      if (Use.Id != 0)
-        return Use;
-    }
-
-    // Go up to the immediate dominator, if any.
-    MachineBasicBlock *BB = BA.Addr->getCode();
-    BA = NodeAddr<BlockNode*>();
-    if (MachineDomTreeNode *N = MDT.getNode(BB)) {
-      if ((N = N->getIDom()))
-        BA = DFG.findBlock(N->getBlock());
-    }
-    if (!BA.Id)
-      break;
-
-    Ins = BA.Addr->members(DFG);
-    B = Ins.rbegin();
-    E = Ins.rend();
-  } while (true);
-
-  return NodeAddr<RefNode*>();
-}
-
-NodeSet Liveness::getAllReachedUses(RegisterRef RefRR,
-      NodeAddr<DefNode*> DefA, const RegisterAggr &DefRRs) {
-  NodeSet Uses;
-
-  // If the original register is already covered by all the intervening
-  // defs, no more uses can be reached.
-  if (DefRRs.hasCoverOf(RefRR))
-    return Uses;
-
-  // Add all directly reached uses.
-  // If the def is dead, it does not provide a value for any use.
-  bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead;
-  NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0;
-  while (U != 0) {
-    auto UA = DFG.addr<UseNode*>(U);
-    if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) {
-      RegisterRef UR = UA.Addr->getRegRef(DFG);
-      if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR))
-        Uses.insert(U);
-    }
-    U = UA.Addr->getSibling();
-  }
-
-  // Traverse all reached defs. This time dead defs cannot be ignored.
-  for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) {
-    auto DA = DFG.addr<DefNode*>(D);
-    NextD = DA.Addr->getSibling();
-    RegisterRef DR = DA.Addr->getRegRef(DFG);
-    // If this def is already covered, it cannot reach anything new.
-    // Similarly, skip it if it is not aliased to the interesting register.
-    if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR))
-      continue;
-    NodeSet T;
-    if (DFG.IsPreservingDef(DA)) {
-      // If it is a preserving def, do not update the set of intervening defs.
-      T = getAllReachedUses(RefRR, DA, DefRRs);
-    } else {
-      RegisterAggr NewDefRRs = DefRRs;
-      NewDefRRs.insert(DR);
-      T = getAllReachedUses(RefRR, DA, NewDefRRs);
-    }
-    Uses.insert(T.begin(), T.end());
-  }
-  return Uses;
-}
-
-void Liveness::computePhiInfo() {
-  RealUseMap.clear();
-
-  NodeList Phis;
-  NodeAddr<FuncNode*> FA = DFG.getFunc();
-  NodeList Blocks = FA.Addr->members(DFG);
-  for (NodeAddr<BlockNode*> BA : Blocks) {
-    auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
-    Phis.insert(Phis.end(), Ps.begin(), Ps.end());
-  }
-
-  // phi use -> (map: reaching phi -> set of registers defined in between)
-  std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp;
-  std::vector<NodeId> PhiUQ;  // Work list of phis for upward propagation.
-  std::map<NodeId,RegisterAggr> PhiDRs;  // Phi -> registers defined by it.
-
-  // Go over all phis.
-  for (NodeAddr<PhiNode*> PhiA : Phis) {
-    // Go over all defs and collect the reached uses that are non-phi uses
-    // (i.e. the "real uses").
-    RefMap &RealUses = RealUseMap[PhiA.Id];
-    NodeList PhiRefs = PhiA.Addr->members(DFG);
-
-    // Have a work queue of defs whose reached uses need to be found.
-    // For each def, add to the queue all reached (non-phi) defs.
-    SetVector<NodeId> DefQ;
-    NodeSet PhiDefs;
-    RegisterAggr DRs(PRI);
-    for (NodeAddr<RefNode*> R : PhiRefs) {
-      if (!DFG.IsRef<NodeAttrs::Def>(R))
-        continue;
-      DRs.insert(R.Addr->getRegRef(DFG));
-      DefQ.insert(R.Id);
-      PhiDefs.insert(R.Id);
-    }
-    PhiDRs.insert(std::make_pair(PhiA.Id, DRs));
-
-    // Collect the super-set of all possible reached uses. This set will
-    // contain all uses reached from this phi, either directly from the
-    // phi defs, or (recursively) via non-phi defs reached by the phi defs.
-    // This set of uses will later be trimmed to only contain these uses that
-    // are actually reached by the phi defs.
-    for (unsigned i = 0; i < DefQ.size(); ++i) {
-      NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]);
-      // Visit all reached uses. Phi defs should not really have the "dead"
-      // flag set, but check it anyway for consistency.
-      bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead;
-      NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0;
-      while (UN != 0) {
-        NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN);
-        uint16_t F = A.Addr->getFlags();
-        if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) {
-          RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG));
-          RealUses[R.Reg].insert({A.Id,R.Mask});
-        }
-        UN = A.Addr->getSibling();
-      }
-      // Visit all reached defs, and add them to the queue. These defs may
-      // override some of the uses collected here, but that will be handled
-      // later.
-      NodeId DN = DA.Addr->getReachedDef();
-      while (DN != 0) {
-        NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN);
-        for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) {
-          uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags();
-          // Must traverse the reached-def chain. Consider:
-          //   def(D0) -> def(R0) -> def(R0) -> use(D0)
-          // The reachable use of D0 passes through a def of R0.
-          if (!(Flags & NodeAttrs::PhiRef))
-            DefQ.insert(T.Id);
-        }
-        DN = A.Addr->getSibling();
-      }
-    }
-    // Filter out these uses that appear to be reachable, but really
-    // are not. For example:
-    //
-    // R1:0 =          d1
-    //      = R1:0     u2     Reached by d1.
-    //   R0 =          d3
-    //      = R1:0     u4     Still reached by d1: indirectly through
-    //                        the def d3.
-    //   R1 =          d5
-    //      = R1:0     u6     Not reached by d1 (covered collectively
-    //                        by d3 and d5), but following reached
-    //                        defs and uses from d1 will lead here.
-    for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) {
-      // For each reached register UI->first, there is a set UI->second, of
-      // uses of it. For each such use, check if it is reached by this phi,
-      // i.e. check if the set of its reaching uses intersects the set of
-      // this phi's defs.
-      NodeRefSet Uses = UI->second;
-      UI->second.clear();
-      for (std::pair<NodeId,LaneBitmask> I : Uses) {
-        auto UA = DFG.addr<UseNode*>(I.first);
-        // Undef flag is checked above.
-        assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0);
-        RegisterRef R(UI->first, I.second);
-        // Calculate the exposed part of the reached use.
-        RegisterAggr Covered(PRI);
-        for (NodeAddr<DefNode*> DA : getAllReachingDefs(R, UA)) {
-          if (PhiDefs.count(DA.Id))
-            break;
-          Covered.insert(DA.Addr->getRegRef(DFG));
-        }
-        if (RegisterRef RC = Covered.clearIn(R)) {
-          // We are updating the map for register UI->first, so we need
-          // to map RC to be expressed in terms of that register.
-          RegisterRef S = PRI.mapTo(RC, UI->first);
-          UI->second.insert({I.first, S.Mask});
-        }
-      }
-      UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI);
-    }
-
-    // If this phi reaches some "real" uses, add it to the queue for upward
-    // propagation.
-    if (!RealUses.empty())
-      PhiUQ.push_back(PhiA.Id);
-
-    // Go over all phi uses and check if the reaching def is another phi.
-    // Collect the phis that are among the reaching defs of these uses.
-    // While traversing the list of reaching defs for each phi use, accumulate
-    // the set of registers defined between this phi (PhiA) and the owner phi
-    // of the reaching def.
-    NodeSet SeenUses;
-
-    for (auto I : PhiRefs) {
-      if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id))
-        continue;
-      NodeAddr<PhiUseNode*> PUA = I;
-      if (PUA.Addr->getReachingDef() == 0)
-        continue;
-
-      RegisterRef UR = PUA.Addr->getRegRef(DFG);
-      NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs);
-      RegisterAggr DefRRs(PRI);
-
-      for (NodeAddr<DefNode*> D : Ds) {
-        if (D.Addr->getFlags() & NodeAttrs::PhiRef) {
-          NodeId RP = D.Addr->getOwner(DFG).Id;
-          std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.Id];
-          auto F = M.find(RP);
-          if (F == M.end())
-            M.insert(std::make_pair(RP, DefRRs));
-          else
-            F->second.insert(DefRRs);
-        }
-        DefRRs.insert(D.Addr->getRegRef(DFG));
-      }
-
-      for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PhiA, PUA))
-        SeenUses.insert(T.Id);
-    }
-  }
-
-  if (Trace) {
-    dbgs() << "Phi-up-to-phi map with intervening defs:\n";
-    for (auto I : PhiUp) {
-      dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {";
-      for (auto R : I.second)
-        dbgs() << ' ' << Print<NodeId>(R.first, DFG)
-               << Print<RegisterAggr>(R.second, DFG);
-      dbgs() << " }\n";
-    }
-  }
-
-  // Propagate the reached registers up in the phi chain.
-  //
-  // The following type of situation needs careful handling:
-  //
-  //   phi d1<R1:0>  (1)
-  //        |
-  //   ... d2<R1>
-  //        |
-  //   phi u3<R1:0>  (2)
-  //        |
-  //   ... u4<R1>
-  //
-  // The phi node (2) defines a register pair R1:0, and reaches a "real"
-  // use u4 of just R1. The same phi node is also known to reach (upwards)
-  // the phi node (1). However, the use u4 is not reached by phi (1),
-  // because of the intervening definition d2 of R1. The data flow between
-  // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0.
-  //
-  // When propagating uses up the phi chains, get the all reaching defs
-  // for a given phi use, and traverse the list until the propagated ref
-  // is covered, or until reaching the final phi. Only assume that the
-  // reference reaches the phi in the latter case.
-
-  for (unsigned i = 0; i < PhiUQ.size(); ++i) {
-    auto PA = DFG.addr<PhiNode*>(PhiUQ[i]);
-    NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG);
-    RefMap &RUM = RealUseMap[PA.Id];
-
-    for (NodeAddr<UseNode*> UA : PUs) {
-      std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
-      RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG));
-      for (const std::pair<const NodeId, RegisterAggr> &P : PUM) {
-        bool Changed = false;
-        const RegisterAggr &MidDefs = P.second;
-
-        // Collect the set PropUp of uses that are reached by the current
-        // phi PA, and are not covered by any intervening def between the
-        // currently visited use UA and the upward phi P.
-
-        if (MidDefs.hasCoverOf(UR))
-          continue;
-
-        // General algorithm:
-        //   for each (R,U) : U is use node of R, U is reached by PA
-        //     if MidDefs does not cover (R,U)
-        //       then add (R-MidDefs,U) to RealUseMap[P]
-        //
-        for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) {
-          RegisterRef R(T.first);
-          // The current phi (PA) could be a phi for a regmask. It could
-          // reach a whole variety of uses that are not related to the
-          // specific upward phi (P.first).
-          const RegisterAggr &DRs = PhiDRs.at(P.first);
-          if (!DRs.hasAliasOf(R))
-            continue;
-          R = PRI.mapTo(DRs.intersectWith(R), T.first);
-          for (std::pair<NodeId,LaneBitmask> V : T.second) {
-            LaneBitmask M = R.Mask & V.second;
-            if (M.none())
-              continue;
-            if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) {
-              NodeRefSet &RS = RealUseMap[P.first][SS.Reg];
-              Changed |= RS.insert({V.first,SS.Mask}).second;
-            }
-          }
-        }
-
-        if (Changed)
-          PhiUQ.push_back(P.first);
-      }
-    }
-  }
-
-  if (Trace) {
-    dbgs() << "Real use map:\n";
-    for (auto I : RealUseMap) {
-      dbgs() << "phi " << Print<NodeId>(I.first, DFG);
-      NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first);
-      NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG);
-      if (!Ds.empty()) {
-        RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(DFG);
-        dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>';
-      } else {
-        dbgs() << "<noreg>";
-      }
-      dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n';
-    }
-  }
-}
-
-void Liveness::computeLiveIns() {
-  // Populate the node-to-block map. This speeds up the calculations
-  // significantly.
-  NBMap.clear();
-  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
-    MachineBasicBlock *BB = BA.Addr->getCode();
-    for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
-      for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
-        NBMap.insert(std::make_pair(RA.Id, BB));
-      NBMap.insert(std::make_pair(IA.Id, BB));
-    }
-  }
-
-  MachineFunction &MF = DFG.getMF();
-
-  // Compute IDF first, then the inverse.
-  decltype(IIDF) IDF;
-  for (MachineBasicBlock &B : MF) {
-    auto F1 = MDF.find(&B);
-    if (F1 == MDF.end())
-      continue;
-    SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end());
-    for (unsigned i = 0; i < IDFB.size(); ++i) {
-      auto F2 = MDF.find(IDFB[i]);
-      if (F2 != MDF.end())
-        IDFB.insert(F2->second.begin(), F2->second.end());
-    }
-    // Add B to the IDF(B). This will put B in the IIDF(B).
-    IDFB.insert(&B);
-    IDF[&B].insert(IDFB.begin(), IDFB.end());
-  }
-
-  for (auto I : IDF)
-    for (auto S : I.second)
-      IIDF[S].insert(I.first);
-
-  computePhiInfo();
-
-  NodeAddr<FuncNode*> FA = DFG.getFunc();
-  NodeList Blocks = FA.Addr->members(DFG);
-
-  // Build the phi live-on-entry map.
-  for (NodeAddr<BlockNode*> BA : Blocks) {
-    MachineBasicBlock *MB = BA.Addr->getCode();
-    RefMap &LON = PhiLON[MB];
-    for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG))
-      for (const RefMap::value_type &S : RealUseMap[P.Id])
-        LON[S.first].insert(S.second.begin(), S.second.end());
-  }
-
-  if (Trace) {
-    dbgs() << "Phi live-on-entry map:\n";
-    for (auto &I : PhiLON)
-      dbgs() << "block #" << I.first->getNumber() << " -> "
-             << Print<RefMap>(I.second, DFG) << '\n';
-  }
-
-  // Build the phi live-on-exit map. Each phi node has some set of reached
-  // "real" uses. Propagate this set backwards into the block predecessors
-  // through the reaching defs of the corresponding phi uses.
-  for (NodeAddr<BlockNode*> BA : Blocks) {
-    NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
-    for (NodeAddr<PhiNode*> PA : Phis) {
-      RefMap &RUs = RealUseMap[PA.Id];
-      if (RUs.empty())
-        continue;
-
-      NodeSet SeenUses;
-      for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
-        if (!SeenUses.insert(U.Id).second)
-          continue;
-        NodeAddr<PhiUseNode*> PUA = U;
-        if (PUA.Addr->getReachingDef() == 0)
-          continue;
-
-        // Each phi has some set (possibly empty) of reached "real" uses,
-        // that is, uses that are part of the compiled program. Such a use
-        // may be located in some farther block, but following a chain of
-        // reaching defs will eventually lead to this phi.
-        // Any chain of reaching defs may fork at a phi node, but there
-        // will be a path upwards that will lead to this phi. Now, this
-        // chain will need to fork at this phi, since some of the reached
-        // uses may have definitions joining in from multiple predecessors.
-        // For each reached "real" use, identify the set of reaching defs
-        // coming from each predecessor P, and add them to PhiLOX[P].
-        //
-        auto PrA = DFG.addr<BlockNode*>(PUA.Addr->getPredecessor());
-        RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
-
-        for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
-          // We need to visit each individual use.
-          for (std::pair<NodeId,LaneBitmask> P : RS.second) {
-            // Create a register ref corresponding to the use, and find
-            // all reaching defs starting from the phi use, and treating
-            // all related shadows as a single use cluster.
-            RegisterRef S(RS.first, P.second);
-            NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs);
-            for (NodeAddr<DefNode*> D : Ds) {
-              // Calculate the mask corresponding to the visited def.
-              RegisterAggr TA(PRI);
-              TA.insert(D.Addr->getRegRef(DFG)).intersect(S);
-              LaneBitmask TM = TA.makeRegRef().Mask;
-              LOX[S.Reg].insert({D.Id, TM});
-            }
-          }
-        }
-
-        for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PA, PUA))
-          SeenUses.insert(T.Id);
-      }  // for U : phi uses
-    }  // for P : Phis
-  }  // for B : Blocks
-
-  if (Trace) {
-    dbgs() << "Phi live-on-exit map:\n";
-    for (auto &I : PhiLOX)
-      dbgs() << "block #" << I.first->getNumber() << " -> "
-             << Print<RefMap>(I.second, DFG) << '\n';
-  }
-
-  RefMap LiveIn;
-  traverse(&MF.front(), LiveIn);
-
-  // Add function live-ins to the live-in set of the function entry block.
-  LiveMap[&MF.front()].insert(DFG.getLiveIns());
-
-  if (Trace) {
-    // Dump the liveness map
-    for (MachineBasicBlock &B : MF) {
-      std::vector<RegisterRef> LV;
-      for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
-        LV.push_back(RegisterRef(I->PhysReg, I->LaneMask));
-      llvm::sort(LV);
-      dbgs() << printMBBReference(B) << "\t rec = {";
-      for (auto I : LV)
-        dbgs() << ' ' << Print<RegisterRef>(I, DFG);
-      dbgs() << " }\n";
-      //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n';
-
-      LV.clear();
-      const RegisterAggr &LG = LiveMap[&B];
-      for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I)
-        LV.push_back(*I);
-      llvm::sort(LV);
-      dbgs() << "\tcomp = {";
-      for (auto I : LV)
-        dbgs() << ' ' << Print<RegisterRef>(I, DFG);
-      dbgs() << " }\n";
-
-    }
-  }
-}
-
-void Liveness::resetLiveIns() {
-  for (auto &B : DFG.getMF()) {
-    // Remove all live-ins.
-    std::vector<unsigned> T;
-    for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
-      T.push_back(I->PhysReg);
-    for (auto I : T)
-      B.removeLiveIn(I);
-    // Add the newly computed live-ins.
-    const RegisterAggr &LiveIns = LiveMap[&B];
-    for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) {
-      RegisterRef R = *I;
-      B.addLiveIn({MCPhysReg(R.Reg), R.Mask});
-    }
-  }
-}
-
-void Liveness::resetKills() {
-  for (auto &B : DFG.getMF())
-    resetKills(&B);
-}
-
-void Liveness::resetKills(MachineBasicBlock *B) {
-  auto CopyLiveIns = [this] (MachineBasicBlock *B, BitVector &LV) -> void {
-    for (auto I : B->liveins()) {
-      MCSubRegIndexIterator S(I.PhysReg, &TRI);
-      if (!S.isValid()) {
-        LV.set(I.PhysReg);
-        continue;
-      }
-      do {
-        LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex());
-        if ((M & I.LaneMask).any())
-          LV.set(S.getSubReg());
-        ++S;
-      } while (S.isValid());
-    }
-  };
-
-  BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
-  CopyLiveIns(B, LiveIn);
-  for (auto SI : B->successors())
-    CopyLiveIns(SI, Live);
-
-  for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) {
-    MachineInstr *MI = &*I;
-    if (MI->isDebugInstr())
-      continue;
-
-    MI->clearKillInfo();
-    for (auto &Op : MI->operands()) {
-      // An implicit def of a super-register may not necessarily start a
-      // live range of it, since an implicit use could be used to keep parts
-      // of it live. Instead of analyzing the implicit operands, ignore
-      // implicit defs.
-      if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
-        continue;
-      Register R = Op.getReg();
-      if (!Register::isPhysicalRegister(R))
-        continue;
-      for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
-        Live.reset(*SR);
-    }
-    for (auto &Op : MI->operands()) {
-      if (!Op.isReg() || !Op.isUse() || Op.isUndef())
-        continue;
-      Register R = Op.getReg();
-      if (!Register::isPhysicalRegister(R))
-        continue;
-      bool IsLive = false;
-      for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) {
-        if (!Live[*AR])
-          continue;
-        IsLive = true;
-        break;
-      }
-      if (!IsLive)
-        Op.setIsKill(true);
-      for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
-        Live.set(*SR);
-    }
-  }
-}
-
-// Helper function to obtain the basic block containing the reaching def
-// of the given use.
-MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
-  auto F = NBMap.find(RN);
-  if (F != NBMap.end())
-    return F->second;
-  llvm_unreachable("Node id not in map");
-}
-
-void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
-  // The LiveIn map, for each (physical) register, contains the set of live
-  // reaching defs of that register that are live on entry to the associated
-  // block.
-
-  // The summary of the traversal algorithm:
-  //
-  // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
-  // and (U \in IDF(B) or B dom U).
-  //
-  // for (C : children) {
-  //   LU = {}
-  //   traverse(C, LU)
-  //   LiveUses += LU
-  // }
-  //
-  // LiveUses -= Defs(B);
-  // LiveUses += UpwardExposedUses(B);
-  // for (C : IIDF[B])
-  //   for (U : LiveUses)
-  //     if (Rdef(U) dom C)
-  //       C.addLiveIn(U)
-  //
-
-  // Go up the dominator tree (depth-first).
-  MachineDomTreeNode *N = MDT.getNode(B);
-  for (auto I : *N) {
-    RefMap L;
-    MachineBasicBlock *SB = I->getBlock();
-    traverse(SB, L);
-
-    for (auto S : L)
-      LiveIn[S.first].insert(S.second.begin(), S.second.end());
-  }
-
-  if (Trace) {
-    dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__
-           << " after recursion into: {";
-    for (auto I : *N)
-      dbgs() << ' ' << I->getBlock()->getNumber();
-    dbgs() << " }\n";
-    dbgs() << "  LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
-    dbgs() << "  Local:  " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
-  }
-
-  // Add reaching defs of phi uses that are live on exit from this block.
-  RefMap &PUs = PhiLOX[B];
-  for (auto &S : PUs)
-    LiveIn[S.first].insert(S.second.begin(), S.second.end());
-
-  if (Trace) {
-    dbgs() << "after LOX\n";
-    dbgs() << "  LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
-    dbgs() << "  Local:  " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
-  }
-
-  // The LiveIn map at this point has all defs that are live-on-exit from B,
-  // as if they were live-on-entry to B. First, we need to filter out all
-  // defs that are present in this block. Then we will add reaching defs of
-  // all upward-exposed uses.
-
-  // To filter out the defs, first make a copy of LiveIn, and then re-populate
-  // LiveIn with the defs that should remain.
-  RefMap LiveInCopy = LiveIn;
-  LiveIn.clear();
-
-  for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) {
-    RegisterRef LRef(LE.first);
-    NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled.
-    const NodeRefSet &OldDefs = LE.second;
-    for (NodeRef OR : OldDefs) {
-      // R is a def node that was live-on-exit
-      auto DA = DFG.addr<DefNode*>(OR.first);
-      NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
-      NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
-      if (B != BA.Addr->getCode()) {
-        // Defs from a different block need to be preserved. Defs from this
-        // block will need to be processed further, except for phi defs, the
-        // liveness of which is handled through the PhiLON/PhiLOX maps.
-        NewDefs.insert(OR);
-        continue;
-      }
-
-      // Defs from this block need to stop the liveness from being
-      // propagated upwards. This only applies to non-preserving defs,
-      // and to the parts of the register actually covered by those defs.
-      // (Note that phi defs should always be preserving.)
-      RegisterAggr RRs(PRI);
-      LRef.Mask = OR.second;
-
-      if (!DFG.IsPreservingDef(DA)) {
-        assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
-        // DA is a non-phi def that is live-on-exit from this block, and
-        // that is also located in this block. LRef is a register ref
-        // whose use this def reaches. If DA covers LRef, then no part
-        // of LRef is exposed upwards.A
-        if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
-          continue;
-      }
-
-      // DA itself was not sufficient to cover LRef. In general, it is
-      // the last in a chain of aliased defs before the exit from this block.
-      // There could be other defs in this block that are a part of that
-      // chain. Check that now: accumulate the registers from these defs,
-      // and if they all together cover LRef, it is not live-on-entry.
-      for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) {
-        // DefNode -> InstrNode -> BlockNode.
-        NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG);
-        NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG);
-        // Reaching defs are ordered in the upward direction.
-        if (BTA.Addr->getCode() != B) {
-          // We have reached past the beginning of B, and the accumulated
-          // registers are not covering LRef. The first def from the
-          // upward chain will be live.
-          // Subtract all accumulated defs (RRs) from LRef.
-          RegisterRef T = RRs.clearIn(LRef);
-          assert(T);
-          NewDefs.insert({TA.Id,T.Mask});
-          break;
-        }
-
-        // TA is in B. Only add this def to the accumulated cover if it is
-        // not preserving.
-        if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
-          RRs.insert(TA.Addr->getRegRef(DFG));
-        // If this is enough to cover LRef, then stop.
-        if (RRs.hasCoverOf(LRef))
-          break;
-      }
-    }
-  }
-
-  emptify(LiveIn);
-
-  if (Trace) {
-    dbgs() << "after defs in block\n";
-    dbgs() << "  LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
-    dbgs() << "  Local:  " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
-  }
-
-  // Scan the block for upward-exposed uses and add them to the tracking set.
-  for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) {
-    NodeAddr<InstrNode*> IA = I;
-    if (IA.Addr->getKind() != NodeAttrs::Stmt)
-      continue;
-    for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
-      if (UA.Addr->getFlags() & NodeAttrs::Undef)
-        continue;
-      RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG));
-      for (NodeAddr<DefNode*> D : getAllReachingDefs(UA))
-        if (getBlockWithRef(D.Id) != B)
-          LiveIn[RR.Reg].insert({D.Id,RR.Mask});
-    }
-  }
-
-  if (Trace) {
-    dbgs() << "after uses in block\n";
-    dbgs() << "  LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
-    dbgs() << "  Local:  " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n';
-  }
-
-  // Phi uses should not be propagated up the dominator tree, since they
-  // are not dominated by their corresponding reaching defs.
-  RegisterAggr &Local = LiveMap[B];
-  RefMap &LON = PhiLON[B];
-  for (auto &R : LON) {
-    LaneBitmask M;
-    for (auto P : R.second)
-      M |= P.second;
-    Local.insert(RegisterRef(R.first,M));
-  }
-
-  if (Trace) {
-    dbgs() << "after phi uses in block\n";
-    dbgs() << "  LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
-    dbgs() << "  Local:  " << Print<RegisterAggr>(Local, DFG) << '\n';
-  }
-
-  for (auto C : IIDF[B]) {
-    RegisterAggr &LiveC = LiveMap[C];
-    for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn)
-      for (auto R : S.second)
-        if (MDT.properlyDominates(getBlockWithRef(R.first), C))
-          LiveC.insert(RegisterRef(S.first, R.second));
-  }
-}
-
-void Liveness::emptify(RefMap &M) {
-  for (auto I = M.begin(), E = M.end(); I != E; )
-    I = I->second.empty() ? M.erase(I) : std::next(I);
-}
diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.h b/llvm/lib/Target/Hexagon/RDFLiveness.h
deleted file mode 100644
index ea489027172..00000000000
--- a/llvm/lib/Target/Hexagon/RDFLiveness.h
+++ /dev/null
@@ -1,151 +0,0 @@
-//===- RDFLiveness.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
-//
-//===----------------------------------------------------------------------===//
-//
-// Recalculate the liveness information given a data flow graph.
-// This includes block live-ins and kill flags.
-
-#ifndef LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H
-#define LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H
-
-#include "RDFGraph.h"
-#include "RDFRegisters.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/MC/LaneBitmask.h"
-#include <map>
-#include <set>
-#include <utility>
-
-namespace llvm {
-
-class MachineBasicBlock;
-class MachineDominanceFrontier;
-class MachineDominatorTree;
-class MachineRegisterInfo;
-class TargetRegisterInfo;
-
-namespace rdf {
-
-  struct Liveness {
-  public:
-    // This is really a std::map, except that it provides a non-trivial
-    // default constructor to the element accessed via [].
-    struct LiveMapType {
-      LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {}
-
-      RegisterAggr &operator[] (MachineBasicBlock *B) {
-        return Map.emplace(B, Empty).first->second;
-      }
-
-    private:
-      RegisterAggr Empty;
-      std::map<MachineBasicBlock*,RegisterAggr> Map;
-    };
-
-    using NodeRef = std::pair<NodeId, LaneBitmask>;
-    using NodeRefSet = std::set<NodeRef>;
-    // RegisterId in RefMap must be normalized.
-    using RefMap = std::map<RegisterId, NodeRefSet>;
-
-    Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g)
-        : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()),
-          MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {}
-
-    NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA,
-        bool TopShadows, bool FullChain, const RegisterAggr &DefRRs);
-
-    NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) {
-      return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false,
-                                false, NoRegs);
-    }
-
-    NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) {
-      return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
-    }
-
-    NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA,
-        const RegisterAggr &DefRRs);
-
-    NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) {
-      return getAllReachedUses(RefRR, DefA, NoRegs);
-    }
-
-    std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR,
-        NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs);
-
-    NodeAddr<RefNode*> getNearestAliasedRef(RegisterRef RefRR,
-        NodeAddr<InstrNode*> IA);
-
-    LiveMapType &getLiveMap() { return LiveMap; }
-    const LiveMapType &getLiveMap() const { return LiveMap; }
-
-    const RefMap &getRealUses(NodeId P) const {
-      auto F = RealUseMap.find(P);
-      return F == RealUseMap.end() ? Empty : F->second;
-    }
-
-    void computePhiInfo();
-    void computeLiveIns();
-    void resetLiveIns();
-    void resetKills();
-    void resetKills(MachineBasicBlock *B);
-
-    void trace(bool T) { Trace = T; }
-
-  private:
-    const DataFlowGraph &DFG;
-    const TargetRegisterInfo &TRI;
-    const PhysicalRegisterInfo &PRI;
-    const MachineDominatorTree &MDT;
-    const MachineDominanceFrontier &MDF;
-    LiveMapType LiveMap;
-    const RefMap Empty;
-    const RegisterAggr NoRegs;
-    bool Trace = false;
-
-    // Cache of mapping from node ids (for RefNodes) to the containing
-    // basic blocks. Not computing it each time for each node reduces
-    // the liveness calculation time by a large fraction.
-    using NodeBlockMap = DenseMap<NodeId, MachineBasicBlock *>;
-    NodeBlockMap NBMap;
-
-    // Phi information:
-    //
-    // RealUseMap
-    // map: NodeId -> (map: RegisterId -> NodeRefSet)
-    //      phi id -> (map: register -> set of reached non-phi uses)
-    std::map<NodeId, RefMap> RealUseMap;
-
-    // Inverse iterated dominance frontier.
-    std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF;
-
-    // Live on entry.
-    std::map<MachineBasicBlock*,RefMap> PhiLON;
-
-    // Phi uses are considered to be located at the end of the block that
-    // they are associated with. The reaching def of a phi use dominates the
-    // block that the use corresponds to, but not the block that contains
-    // the phi itself. To include these uses in the liveness propagation (up
-    // the dominator tree), create a map: block -> set of uses live on exit.
-    std::map<MachineBasicBlock*,RefMap> PhiLOX;
-
-    MachineBasicBlock *getBlockWithRef(NodeId RN) const;
-    void traverse(MachineBasicBlock *B, RefMap &LiveIn);
-    void emptify(RefMap &M);
-
-    std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR,
-        NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs,
-        unsigned Nest, unsigned MaxNest);
-  };
-
-  raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P);
-
-} // end namespace rdf
-
-} // end namespace llvm
-
-#endif // LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H
diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.cpp b/llvm/lib/Target/Hexagon/RDFRegisters.cpp
deleted file mode 100644
index b5675784e34..00000000000
--- a/llvm/lib/Target/Hexagon/RDFRegisters.cpp
+++ /dev/null
@@ -1,380 +0,0 @@
-//===- RDFRegisters.cpp ---------------------------------------------------===//
-//
-// 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
-//
-//===----------------------------------------------------------------------===//
-
-#include "RDFRegisters.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineOperand.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/MC/LaneBitmask.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/raw_ostream.h"
-#include <cassert>
-#include <cstdint>
-#include <set>
-#include <utility>
-
-using namespace llvm;
-using namespace rdf;
-
-PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri,
-      const MachineFunction &mf)
-    : TRI(tri) {
-  RegInfos.resize(TRI.getNumRegs());
-
-  BitVector BadRC(TRI.getNumRegs());
-  for (const TargetRegisterClass *RC : TRI.regclasses()) {
-    for (MCPhysReg R : *RC) {
-      RegInfo &RI = RegInfos[R];
-      if (RI.RegClass != nullptr && !BadRC[R]) {
-        if (RC->LaneMask != RI.RegClass->LaneMask) {
-          BadRC.set(R);
-          RI.RegClass = nullptr;
-        }
-      } else
-        RI.RegClass = RC;
-    }
-  }
-
-  UnitInfos.resize(TRI.getNumRegUnits());
-
-  for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) {
-    if (UnitInfos[U].Reg != 0)
-      continue;
-    MCRegUnitRootIterator R(U, &TRI);
-    assert(R.isValid());
-    RegisterId F = *R;
-    ++R;
-    if (R.isValid()) {
-      UnitInfos[U].Mask = LaneBitmask::getAll();
-      UnitInfos[U].Reg = F;
-    } else {
-      for (MCRegUnitMaskIterator I(F, &TRI); I.isValid(); ++I) {
-        std::pair<uint32_t,LaneBitmask> P = *I;
-        UnitInfo &UI = UnitInfos[P.first];
-        UI.Reg = F;
-        if (P.second.any()) {
-          UI.Mask = P.second;
-        } else {
-          if (const TargetRegisterClass *RC = RegInfos[F].RegClass)
-            UI.Mask = RC->LaneMask;
-          else
-            UI.Mask = LaneBitmask::getAll();
-        }
-      }
-    }
-  }
-
-  for (const uint32_t *RM : TRI.getRegMasks())
-    RegMasks.insert(RM);
-  for (const MachineBasicBlock &B : mf)
-    for (const MachineInstr &In : B)
-      for (const MachineOperand &Op : In.operands())
-        if (Op.isRegMask())
-          RegMasks.insert(Op.getRegMask());
-
-  MaskInfos.resize(RegMasks.size()+1);
-  for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) {
-    BitVector PU(TRI.getNumRegUnits());
-    const uint32_t *MB = RegMasks.get(M);
-    for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
-      if (!(MB[i/32] & (1u << (i%32))))
-        continue;
-      for (MCRegUnitIterator U(i, &TRI); U.isValid(); ++U)
-        PU.set(*U);
-    }
-    MaskInfos[M].Units = PU.flip();
-  }
-}
-
-RegisterRef PhysicalRegisterInfo::normalize(RegisterRef RR) const {
-  return RR;
-}
-
-std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
-  // Do not include RR in the alias set.
-  std::set<RegisterId> AS;
-  assert(isRegMaskId(Reg) || Register::isPhysicalRegister(Reg));
-  if (isRegMaskId(Reg)) {
-    // XXX SLOW
-    const uint32_t *MB = getRegMaskBits(Reg);
-    for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
-      if (MB[i/32] & (1u << (i%32)))
-        continue;
-      AS.insert(i);
-    }
-    for (const uint32_t *RM : RegMasks) {
-      RegisterId MI = getRegMaskId(RM);
-      if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI)))
-        AS.insert(MI);
-    }
-    return AS;
-  }
-
-  for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI)
-    AS.insert(*AI);
-  for (const uint32_t *RM : RegMasks) {
-    RegisterId MI = getRegMaskId(RM);
-    if (aliasRM(RegisterRef(Reg), RegisterRef(MI)))
-      AS.insert(MI);
-  }
-  return AS;
-}
-
-bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const {
-  assert(Register::isPhysicalRegister(RA.Reg));
-  assert(Register::isPhysicalRegister(RB.Reg));
-
-  MCRegUnitMaskIterator UMA(RA.Reg, &TRI);
-  MCRegUnitMaskIterator UMB(RB.Reg, &TRI);
-  // Reg units are returned in the numerical order.
-  while (UMA.isValid() && UMB.isValid()) {
-    // Skip units that are masked off in RA.
-    std::pair<RegisterId,LaneBitmask> PA = *UMA;
-    if (PA.second.any() && (PA.second & RA.Mask).none()) {
-      ++UMA;
-      continue;
-    }
-    // Skip units that are masked off in RB.
-    std::pair<RegisterId,LaneBitmask> PB = *UMB;
-    if (PB.second.any() && (PB.second & RB.Mask).none()) {
-      ++UMB;
-      continue;
-    }
-
-    if (PA.first == PB.first)
-      return true;
-    if (PA.first < PB.first)
-      ++UMA;
-    else if (PB.first < PA.first)
-      ++UMB;
-  }
-  return false;
-}
-
-bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const {
-  assert(Register::isPhysicalRegister(RR.Reg) && isRegMaskId(RM.Reg));
-  const uint32_t *MB = getRegMaskBits(RM.Reg);
-  bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32));
-  // If the lane mask information is "full", e.g. when the given lane mask
-  // is a superset of the lane mask from the register class, check the regmask
-  // bit directly.
-  if (RR.Mask == LaneBitmask::getAll())
-    return !Preserved;
-  const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass;
-  if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask)
-    return !Preserved;
-
-  // Otherwise, check all subregisters whose lane mask overlaps the given
-  // mask. For each such register, if it is preserved by the regmask, then
-  // clear the corresponding bits in the given mask. If at the end, all
-  // bits have been cleared, the register does not alias the regmask (i.e.
-  // is it preserved by it).
-  LaneBitmask M = RR.Mask;
-  for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) {
-    LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex());
-    if ((SM & RR.Mask).none())
-      continue;
-    unsigned SR = SI.getSubReg();
-    if (!(MB[SR/32] & (1u << (SR%32))))
-      continue;
-    // The subregister SR is preserved.
-    M &= ~SM;
-    if (M.none())
-      return false;
-  }
-
-  return true;
-}
-
-bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const {
-  assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg));
-  unsigned NumRegs = TRI.getNumRegs();
-  const uint32_t *BM = getRegMaskBits(RM.Reg);
-  const uint32_t *BN = getRegMaskBits(RN.Reg);
-
-  for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) {
-    // Intersect the negations of both words. Disregard reg=0,
-    // i.e. 0th bit in the 0th word.
-    uint32_t C = ~BM[w] & ~BN[w];
-    if (w == 0)
-      C &= ~1;
-    if (C)
-      return true;
-  }
-
-  // Check the remaining registers in the last word.
-  unsigned TailRegs = NumRegs % 32;
-  if (TailRegs == 0)
-    return false;
-  unsigned TW = NumRegs / 32;
-  uint32_t TailMask = (1u << TailRegs) - 1;
-  if (~BM[TW] & ~BN[TW] & TailMask)
-    return true;
-
-  return false;
-}
-
-RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, unsigned R) const {
-  if (RR.Reg == R)
-    return RR;
-  if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg))
-    return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask));
-  if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) {
-    const RegInfo &RI = RegInfos[R];
-    LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask
-                                  : LaneBitmask::getAll();
-    LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(Idx, RR.Mask);
-    return RegisterRef(R, M & RCM);
-  }
-  llvm_unreachable("Invalid arguments: unrelated registers?");
-}
-
-bool RegisterAggr::hasAliasOf(RegisterRef RR) const {
-  if (PhysicalRegisterInfo::isRegMaskId(RR.Reg))
-    return Units.anyCommon(PRI.getMaskUnits(RR.Reg));
-
-  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
-    std::pair<uint32_t,LaneBitmask> P = *U;
-    if (P.second.none() || (P.second & RR.Mask).any())
-      if (Units.test(P.first))
-        return true;
-  }
-  return false;
-}
-
-bool RegisterAggr::hasCoverOf(RegisterRef RR) const {
-  if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) {
-    BitVector T(PRI.getMaskUnits(RR.Reg));
-    return T.reset(Units).none();
-  }
-
-  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
-    std::pair<uint32_t,LaneBitmask> P = *U;
-    if (P.second.none() || (P.second & RR.Mask).any())
-      if (!Units.test(P.first))
-        return false;
-  }
-  return true;
-}
-
-RegisterAggr &RegisterAggr::insert(RegisterRef RR) {
-  if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) {
-    Units |= PRI.getMaskUnits(RR.Reg);
-    return *this;
-  }
-
-  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
-    std::pair<uint32_t,LaneBitmask> P = *U;
-    if (P.second.none() || (P.second & RR.Mask).any())
-      Units.set(P.first);
-  }
-  return *this;
-}
-
-RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) {
-  Units |= RG.Units;
-  return *this;
-}
-
-RegisterAggr &RegisterAggr::intersect(RegisterRef RR) {
-  return intersect(RegisterAggr(PRI).insert(RR));
-}
-
-RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) {
-  Units &= RG.Units;
-  return *this;
-}
-
-RegisterAggr &RegisterAggr::clear(RegisterRef RR) {
-  return clear(RegisterAggr(PRI).insert(RR));
-}
-
-RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) {
-  Units.reset(RG.Units);
-  return *this;
-}
-
-RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const {
-  RegisterAggr T(PRI);
-  T.insert(RR).intersect(*this);
-  if (T.empty())
-    return RegisterRef();
-  RegisterRef NR = T.makeRegRef();
-  assert(NR);
-  return NR;
-}
-
-RegisterRef RegisterAggr::clearIn(RegisterRef RR) const {
-  return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
-}
-
-RegisterRef RegisterAggr::makeRegRef() const {
-  int U = Units.find_first();
-  if (U < 0)
-    return RegisterRef();
-
-  auto AliasedRegs = [this] (uint32_t Unit, BitVector &Regs) {
-    for (MCRegUnitRootIterator R(Unit, &PRI.getTRI()); R.isValid(); ++R)
-      for (MCSuperRegIterator S(*R, &PRI.getTRI(), true); S.isValid(); ++S)
-        Regs.set(*S);
-  };
-
-  // Find the set of all registers that are aliased to all the units
-  // in this aggregate.
-
-  // Get all the registers aliased to the first unit in the bit vector.
-  BitVector Regs(PRI.getTRI().getNumRegs());
-  AliasedRegs(U, Regs);
-  U = Units.find_next(U);
-
-  // For each other unit, intersect it with the set of all registers
-  // aliased that unit.
-  while (U >= 0) {
-    BitVector AR(PRI.getTRI().getNumRegs());
-    AliasedRegs(U, AR);
-    Regs &= AR;
-    U = Units.find_next(U);
-  }
-
-  // If there is at least one register remaining, pick the first one,
-  // and consolidate the masks of all of its units contained in this
-  // aggregate.
-
-  int F = Regs.find_first();
-  if (F <= 0)
-    return RegisterRef();
-
-  LaneBitmask M;
-  for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {
-    std::pair<uint32_t,LaneBitmask> P = *I;
-    if (Units.test(P.first))
-      M |= P.second.none() ? LaneBitmask::getAll() : P.second;
-  }
-  return RegisterRef(F, M);
-}
-
-void RegisterAggr::print(raw_ostream &OS) const {
-  OS << '{';
-  for (int U = Units.find_first(); U >= 0; U = Units.find_next(U))
-    OS << ' ' << printRegUnit(U, &PRI.getTRI());
-  OS << " }";
-}
-
-RegisterAggr::rr_iterator::rr_iterator(const RegisterAggr &RG,
-      bool End)
-    : Owner(&RG) {
-  for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) {
-    RegisterRef R = RG.PRI.getRefForUnit(U);
-    Masks[R.Reg] |= R.Mask;
-  }
-  Pos = End ? Masks.end() : Masks.begin();
-  Index = End ? Masks.size() : 0;
-}
diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.h b/llvm/lib/Target/Hexagon/RDFRegisters.h
deleted file mode 100644
index 4afaf80e465..00000000000
--- a/llvm/lib/Target/Hexagon/RDFRegisters.h
+++ /dev/null
@@ -1,240 +0,0 @@
-//===- RDFRegisters.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
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H
-#define LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H
-
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/MC/LaneBitmask.h"
-#include <cassert>
-#include <cstdint>
-#include <map>
-#include <set>
-#include <vector>
-
-namespace llvm {
-
-class MachineFunction;
-class raw_ostream;
-
-namespace rdf {
-
-  using RegisterId = uint32_t;
-
-  // Template class for a map translating uint32_t into arbitrary types.
-  // The map will act like an indexed set: upon insertion of a new object,
-  // it will automatically assign a new index to it. Index of 0 is treated
-  // as invalid and is never allocated.
-  template <typename T, unsigned N = 32>
-  struct IndexedSet {
-    IndexedSet() { Map.reserve(N); }
-
-    T get(uint32_t Idx) const {
-      // Index Idx corresponds to Map[Idx-1].
-      assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size());
-      return Map[Idx-1];
-    }
-
-    uint32_t insert(T Val) {
-      // Linear search.
-      auto F = llvm::find(Map, Val);
-      if (F != Map.end())
-        return F - Map.begin() + 1;
-      Map.push_back(Val);
-      return Map.size();  // Return actual_index + 1.
-    }
-
-    uint32_t find(T Val) const {
-      auto F = llvm::find(Map, Val);
-      assert(F != Map.end());
-      return F - Map.begin() + 1;
-    }
-
-    uint32_t size() const { return Map.size(); }
-
-    using const_iterator = typename std::vector<T>::const_iterator;
-
-    const_iterator begin() const { return Map.begin(); }
-    const_iterator end() const { return Map.end(); }
-
-  private:
-    std::vector<T> Map;
-  };
-
-  struct RegisterRef {
-    RegisterId Reg = 0;
-    LaneBitmask Mask = LaneBitmask::getNone();
-
-    RegisterRef() = default;
-    explicit RegisterRef(RegisterId R, LaneBitmask M = LaneBitmask::getAll())
-      : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {}
-
-    operator bool() const {
-      return Reg != 0 && Mask.any();
-    }
-
-    bool operator== (const RegisterRef &RR) const {
-      return Reg == RR.Reg && Mask == RR.Mask;
-    }
-
-    bool operator!= (const RegisterRef &RR) const {
-      return !operator==(RR);
-    }
-
-    bool operator< (const RegisterRef &RR) const {
-      return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask);
-    }
-  };
-
-
-  struct PhysicalRegisterInfo {
-    PhysicalRegisterInfo(const TargetRegisterInfo &tri,
-                         const MachineFunction &mf);
-
-    static bool isRegMaskId(RegisterId R) {
-      return Register::isStackSlot(R);
-    }
-
-    RegisterId getRegMaskId(const uint32_t *RM) const {
-      return Register::index2StackSlot(RegMasks.find(RM));
-    }
-
-    const uint32_t *getRegMaskBits(RegisterId R) const {
-      return RegMasks.get(Register::stackSlot2Index(R));
-    }
-
-    RegisterRef normalize(RegisterRef RR) const;
-
-    bool alias(RegisterRef RA, RegisterRef RB) const {
-      if (!isRegMaskId(RA.Reg))
-        return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB);
-      return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB);
-    }
-
-    std::set<RegisterId> getAliasSet(RegisterId Reg) const;
-
-    RegisterRef getRefForUnit(uint32_t U) const {
-      return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
-    }
-
-    const BitVector &getMaskUnits(RegisterId MaskId) const {
-      return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
-    }
-
-    RegisterRef mapTo(RegisterRef RR, unsigned R) const;
-    const TargetRegisterInfo &getTRI() const { return TRI; }
-
-  private:
-    struct RegInfo {
-      const TargetRegisterClass *RegClass = nullptr;
-    };
-    struct UnitInfo {
-      RegisterId Reg = 0;
-      LaneBitmask Mask;
-    };
-    struct MaskInfo {
-      BitVector Units;
-    };
-
-    const TargetRegisterInfo &TRI;
-    IndexedSet<const uint32_t*> RegMasks;
-    std::vector<RegInfo> RegInfos;
-    std::vector<UnitInfo> UnitInfos;
-    std::vector<MaskInfo> MaskInfos;
-
-    bool aliasRR(RegisterRef RA, RegisterRef RB) const;
-    bool aliasRM(RegisterRef RR, RegisterRef RM) const;
-    bool aliasMM(RegisterRef RM, RegisterRef RN) const;
-  };
-
-  struct RegisterAggr {
-    RegisterAggr(const PhysicalRegisterInfo &pri)
-        : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
-    RegisterAggr(const RegisterAggr &RG) = default;
-
-    bool empty() const { return Units.none(); }
-    bool hasAliasOf(RegisterRef RR) const;
-    bool hasCoverOf(RegisterRef RR) const;
-
-    static bool isCoverOf(RegisterRef RA, RegisterRef RB,
-                          const PhysicalRegisterInfo &PRI) {
-      return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
-    }
-
-    RegisterAggr &insert(RegisterRef RR);
-    RegisterAggr &insert(const RegisterAggr &RG);
-    RegisterAggr &intersect(RegisterRef RR);
-    RegisterAggr &intersect(const RegisterAggr &RG);
-    RegisterAggr &clear(RegisterRef RR);
-    RegisterAggr &clear(const RegisterAggr &RG);
-
-    RegisterRef intersectWith(RegisterRef RR) const;
-    RegisterRef clearIn(RegisterRef RR) const;
-    RegisterRef makeRegRef() const;
-
-    void print(raw_ostream &OS) const;
-
-    struct rr_iterator {
-      using MapType = std::map<RegisterId, LaneBitmask>;
-
-    private:
-      MapType Masks;
-      MapType::iterator Pos;
-      unsigned Index;
-      const RegisterAggr *Owner;
-
-    public:
-      rr_iterator(const RegisterAggr &RG, bool End);
-
-      RegisterRef operator*() const {
-        return RegisterRef(Pos->first, Pos->second);
-      }
-
-      rr_iterator &operator++() {
-        ++Pos;
-        ++Index;
-        return *this;
-      }
-
-      bool operator==(const rr_iterator &I) const {
-        assert(Owner == I.Owner);
-        (void)Owner;
-        return Index == I.Index;
-      }
-
-      bool operator!=(const rr_iterator &I) const {
-        return !(*this == I);
-      }
-    };
-
-    rr_iterator rr_begin() const {
-      return rr_iterator(*this, false);
-    }
-    rr_iterator rr_end() const {
-      return rr_iterator(*this, true);
-    }
-
-  private:
-    BitVector Units;
-    const PhysicalRegisterInfo &PRI;
-  };
-
-  // Optionally print the lane mask, if it is not ~0.
-  struct PrintLaneMaskOpt {
-    PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {}
-    LaneBitmask Mask;
-  };
-  raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P);
-
-} // end namespace rdf
-
-} // end namespace llvm
-
-#endif // LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H