//===- 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 "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/RDFGraph.h"

#include "llvm/CodeGen/RDFRegisters.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/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>

// Printing functions. Have them here first, so that the rest of the code

// can use them.

namespace llvm::rdf {

raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P) {

  P.G.getPRI().print(OS, P.Obj);

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P) {

  if (P.Obj == 0)

    return OS << "null";

  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 Ref RA,

                           const DataFlowGraph &G) {

  OS << Print(RA.Id, G) << '<' << Print(RA.Addr->getRegRef(G), G) << '>';

  if (RA.Addr->getFlags() & NodeAttrs::Fixed)

    OS << '!';

}

raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P) {

  printRefHeader(OS, P.Obj, P.G);

  OS << '(';

  if (NodeId N = P.Obj.Addr->getReachingDef())

    OS << Print(N, P.G);

  OS << ',';

  if (NodeId N = P.Obj.Addr->getReachedDef())

    OS << Print(N, P.G);

  OS << ',';

  if (NodeId N = P.Obj.Addr->getReachedUse())

    OS << Print(N, P.G);

  OS << "):";

  if (NodeId N = P.Obj.Addr->getSibling())

    OS << Print(N, P.G);

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P) {

  printRefHeader(OS, P.Obj, P.G);

  OS << '(';

  if (NodeId N = P.Obj.Addr->getReachingDef())

    OS << Print(N, P.G);

  OS << "):";

  if (NodeId N = P.Obj.Addr->getSibling())

    OS << Print(N, P.G);

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P) {

  printRefHeader(OS, P.Obj, P.G);

  OS << '(';

  if (NodeId N = P.Obj.Addr->getReachingDef())

    OS << Print(N, P.G);

  OS << ',';

  if (NodeId N = P.Obj.Addr->getPredecessor())

    OS << Print(N, P.G);

  OS << "):";

  if (NodeId N = P.Obj.Addr->getSibling())

    OS << Print(N, P.G);

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &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(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(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<Phi> &P) {

  OS << Print(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<Stmt> &P) {

  const MachineInstr &MI = *P.Obj.Addr->getCode();

  unsigned Opc = MI.getOpcode();

  OS << Print(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<Instr> &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(P.Obj.Id, P.G);

    break;

  }

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &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(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<Func> &P) {

  OS << "DFG dump:[\n"

     << Print(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(I, P.G);

  OS << " }";

  return OS;

}

raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P) {

  OS << P.Obj;

  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(I->Id, P.G) << '<' << Print(I->Addr->getRegRef(P.G), P.G)

       << '>';

    I.down();

    if (I != E)

      OS << ' ';

  }

  return OS;

}

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

}

Node NodeAllocator::New() {

  if (needNewBlock())

    startNewBlock();

  uint32_t ActiveB = Blocks.size() - 1;

  uint32_t Index = (ActiveEnd - Blocks[ActiveB]) / NodeMemSize;

  Node 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(Node 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(RefData.PR);

  assert(RefData.Op != nullptr);

  return G.makeRegRef(*RefData.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);

  RefData.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;

  RefData.Op = Op;

}

// Get the owner of a given reference node.

Node RefNode::getOwner(const DataFlowGraph &G) {

  Node 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, Def DA) {

  RefData.RD = DA.Id;

  RefData.Sib = DA.Addr->getReachedDef();

  DA.Addr->setReachedDef(Self);

}

// Connect the use node to the reaching def node.

void UseNode::linkToDef(NodeId Self, Def DA) {

  RefData.RD = DA.Id;

  RefData.Sib = DA.Addr->getReachedUse();

  DA.Addr->setReachedUse(Self);

}

// Get the first member of the code node.

Node CodeNode::getFirstMember(const DataFlowGraph &G) const {

  if (CodeData.FirstM == 0)

    return Node();

  return G.addr<NodeBase *>(CodeData.FirstM);

}

// Get the last member of the code node.

Node CodeNode::getLastMember(const DataFlowGraph &G) const {

  if (CodeData.LastM == 0)

    return Node();

  return G.addr<NodeBase *>(CodeData.LastM);

}

// Add node NA at the end of the member list of the given code node.

void CodeNode::addMember(Node NA, const DataFlowGraph &G) {

  Node ML = getLastMember(G);

  if (ML.Id != 0) {

    ML.Addr->append(NA);

  } else {

    CodeData.FirstM = NA.Id;

    NodeId Self = G.id(this);

    NA.Addr->setNext(Self);

  }

  CodeData.LastM = NA.Id;

}

// Add node NA after member node MA in the given code node.

void CodeNode::addMemberAfter(Node MA, Node NA, const DataFlowGraph &G) {

  MA.Addr->append(NA);

  if (CodeData.LastM == MA.Id)

    CodeData.LastM = NA.Id;

}

// Remove member node NA from the given code node.

void CodeNode::removeMember(Node NA, const DataFlowGraph &G) {

  Node MA = getFirstMember(G);

  assert(MA.Id != 0);

  // Special handling if the member to remove is the first member.

  if (MA.Id == NA.Id) {

    if (CodeData.LastM == MA.Id) {

      // If it is the only member, set both first and last to 0.

      CodeData.FirstM = CodeData.LastM = 0;

    } else {

      // Otherwise, advance the first member.

      CodeData.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 (CodeData.LastM == NA.Id)

        CodeData.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 = [](Node) -> bool { return true; };

  return members_if(True, G);

}

// Return the owner of the given instr node.

Node InstrNode::getOwner(const DataFlowGraph &G) {

  Node 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(Phi PA, const DataFlowGraph &G) {

  Node 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.

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

    Node 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.

Block FuncNode::findBlock(const MachineBasicBlock *BB,

                          const DataFlowGraph &G) const {

  auto EqBB = [BB](Node NA) -> bool { return Block(NA).Addr->getCode() == BB; };

  NodeList Ms = members_if(EqBB, G);

  if (!Ms.empty())

    return Ms[0];

  return Block();

}

// Get the block node for the entry block in the given function.

Block 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.implicit_defs().empty() && D.implicit_uses().empty())

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

  ArrayRef<MCPhysReg> ImpOps =

      Op.isDef() ? D.implicit_defs() : D.implicit_uses();

  return is_contained(ImpOps, Reg);

}

//

// The data flow graph construction.

//

DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,

                             const TargetRegisterInfo &tri,

                             const MachineDominatorTree &mdt,

                             const MachineDominanceFrontier &mdf)

    : DefaultTOI(std::make_unique<TargetOperandInfo>(tii)), MF(mf), TII(tii),

      TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(*DefaultTOI),

      LiveIns(PRI) {}

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(Def(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.

RegisterAggr DataFlowGraph::getLandingPadLiveIns() const {

  RegisterAggr LR(getPRI());

  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 (!isFuncletEHPersonality(classifyEHPersonality(PF))) {

    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.

Node DataFlowGraph::newNode(uint16_t Attrs) {

  Node 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.

Node DataFlowGraph::cloneNode(const Node B) {

  Node 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) {

    Ref RA = NA;

    RA.Addr->setReachingDef(0);

    RA.Addr->setSibling(0);

    if (NA.Addr->getKind() == NodeAttrs::Def) {

      Def DA = NA;

      DA.Addr->setReachedDef(0);

      DA.Addr->setReachedUse(0);

    }

  }

  return NA;

}

// Allocation routines for specific node types/kinds.

Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {

  Use UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);

  UA.Addr->setRegRef(&Op, *this);

  return UA;

}

PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,

                                uint16_t Flags) {

  PhiUse PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);

  assert(Flags & NodeAttrs::PhiRef);

  PUA.Addr->setRegRef(RR, *this);

  PUA.Addr->setPredecessor(PredB.Id);

  return PUA;

}

Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {

  Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);

  DA.Addr->setRegRef(&Op, *this);

  return DA;

}

Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {

  Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);

  assert(Flags & NodeAttrs::PhiRef);

  DA.Addr->setRegRef(RR, *this);

  return DA;

}

Phi DataFlowGraph::newPhi(Block Owner) {

  Phi PA = newNode(NodeAttrs::Code | NodeAttrs::Phi);

  Owner.Addr->addPhi(PA, *this);

  return PA;

}

Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {

  Stmt SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt);

  SA.Addr->setCode(MI);

  Owner.Addr->addMember(SA, *this);

  return SA;

}

Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {

  Block BA = newNode(NodeAttrs::Code | NodeAttrs::Block);

  BA.Addr->setCode(BB);

  Owner.Addr->addMember(BA, *this);

  return BA;

}

Func DataFlowGraph::newFunc(MachineFunction *MF) {

  Func FA = newNode(NodeAttrs::Code | NodeAttrs::Func);

  FA.Addr->setCode(MF);

  return FA;

}

// Build the data flow graph.

void DataFlowGraph::build(const Config &config) {

  reset();

  BuildCfg = config;

  MachineRegisterInfo &MRI = MF.getRegInfo();

  ReservedRegs = MRI.getReservedRegs();

  bool SkipReserved = BuildCfg.Options & BuildOptions::OmitReserved;

  auto Insert = [](auto &Set, auto &&Range) {

    Set.insert(Range.begin(), Range.end());

  };

  if (BuildCfg.TrackRegs.empty()) {

    std::set<RegisterId> BaseSet;

    if (BuildCfg.Classes.empty()) {

      // Insert every register.

      for (unsigned R = 0, E = getPRI().getTRI().getNumRegs(); R != E; ++R)

        BaseSet.insert(R);

    } else {

      for (const TargetRegisterClass *RC : BuildCfg.Classes) {

        for (MCPhysReg R : *RC)

          BaseSet.insert(R);

      }

    }

    for (RegisterId R : BaseSet) {

      if (SkipReserved && ReservedRegs[R])

        continue;

      Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));

    }

  } else {

    // Track set in Config overrides everything.

    for (unsigned R : BuildCfg.TrackRegs) {

      if (SkipReserved && ReservedRegs[R])

        continue;

      Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));

    }

  }

  TheFunc = newFunc(&MF);

  if (MF.empty())

    return;

  for (MachineBasicBlock &B : MF) {

    Block BA = newBlock(TheFunc, &B);

    BlockNodes.insert(std::make_pair(&B, BA));

    for (MachineInstr &I : B) {

      if (I.isDebugInstr())

        continue;

      buildStmt(BA, I);

    }

  }

  Block EA = TheFunc.Addr->getEntryBlock(*this);

  NodeList Blocks = TheFunc.Addr->members(*this);

  // Collect function live-ins and entry block live-ins.

  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 (RegisterRef RR : LiveIns.refs()) {

    if (RR.isReg() && !isTracked(RR)) // isReg is likely guaranteed

      continue;

    Phi PA = newPhi(EA);

    uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;

    Def 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.

  RegisterAggr EHRegs = getLandingPadLiveIns();

  if (!EHRegs.empty()) {

    for (Block 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.refs()) {

        if (RR.isReg() && !isTracked(RR))

          continue;

        Phi PA = newPhi(BA);

        uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;

        // Add def:

        Def DA = newDef(PA, RR, PhiFlags);

        PA.Addr->addMember(DA, *this);

        // Add uses (no reaching defs for phi uses):

        for (Block PBA : Preds) {

          PhiUse PUA = newPhiUse(PA, RR, PBA);

          PA.Addr->addMember(PUA, *this);

        }

      }