diff options
Diffstat (limited to 'llvm/lib/CodeGen/RDFGraph.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/RDFGraph.cpp | 930 |
1 files changed, 454 insertions, 476 deletions
diff --git a/llvm/lib/CodeGen/RDFGraph.cpp b/llvm/lib/CodeGen/RDFGraph.cpp index dcb1a44c75e4..abf3b1e6fbb9 100644 --- a/llvm/lib/CodeGen/RDFGraph.cpp +++ b/llvm/lib/CodeGen/RDFGraph.cpp @@ -8,7 +8,6 @@ // // Target-independent, SSA-based data flow graph for register data flow (RDF). // -#include "llvm/CodeGen/RDFGraph.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -19,6 +18,7 @@ #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" @@ -38,64 +38,69 @@ #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; -} +namespace llvm::rdf { -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); +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) { - auto NA = P.G.addr<NodeBase*>(P.Obj); +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; - } + case NodeAttrs::Code: + switch (Kind) { + case NodeAttrs::Func: + OS << 'f'; 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; - } + case NodeAttrs::Block: + OS << 'b'; + break; + case NodeAttrs::Stmt: + OS << 's'; + break; + case NodeAttrs::Phi: + OS << 'p'; break; default: - OS << '?'; + 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) @@ -103,15 +108,14 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<NodeId> &P) { return OS; } -static void printRefHeader(raw_ostream &OS, const NodeAddr<RefNode*> RA, - const DataFlowGraph &G) { - OS << Print(RA.Id, G) << '<' - << Print(RA.Addr->getRegRef(G), G) << '>'; +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<NodeAddr<DefNode*>> &P) { +raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P) { printRefHeader(OS, P.Obj, P.G); OS << '('; if (NodeId N = P.Obj.Addr->getReachingDef()) @@ -128,7 +132,7 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<DefNode*>> &P) { return OS; } -raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) { +raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P) { printRefHeader(OS, P.Obj, P.G); OS << '('; if (NodeId N = P.Obj.Addr->getReachingDef()) @@ -139,8 +143,7 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) { return OS; } -raw_ostream &operator<< (raw_ostream &OS, - const Print<NodeAddr<PhiUseNode*>> &P) { +raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P) { printRefHeader(OS, P.Obj, P.G); OS << '('; if (NodeId N = P.Obj.Addr->getReachingDef()) @@ -154,22 +157,22 @@ raw_ostream &operator<< (raw_ostream &OS, return OS; } -raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<RefNode*>> &P) { +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; + 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) { +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); @@ -179,7 +182,7 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<NodeList> &P) { return OS; } -raw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) { +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); @@ -191,45 +194,43 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) { namespace { - template <typename T> - struct PrintListV { - PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} +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; - }; + 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; +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) { +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) << ']'; + << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']'; return OS; } -raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<StmtNode *>> &P) { +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(); - }); + 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()) @@ -240,32 +241,30 @@ raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<StmtNode *>> &P) { OS << T->getSymbolName(); } } - OS << " [" << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; + OS << " [" << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']'; return OS; } -raw_ostream &operator<< (raw_ostream &OS, - const Print<NodeAddr<InstrNode*>> &P) { +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; + 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<NodeAddr<BlockNode*>> &P) { +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 { + auto PrintBBs = [&OS](std::vector<int> Ns) -> void { unsigned N = Ns.size(); for (int I : Ns) { OS << "%bb." << I; @@ -289,20 +288,21 @@ raw_ostream &operator<< (raw_ostream &OS, OS << '\n'; for (auto I : P.Obj.Addr->members(P.G)) - OS << PrintNode<InstrNode*>(I, P.G) << '\n'; + 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(P.Obj.Id, P.G) << ": Function: " - << P.Obj.Addr->getCode()->getName() << '\n'; +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 << PrintNode<BlockNode *>(I, P.G) << '\n'; OS << "]\n"; return OS; } -raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) { +raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P) { OS << '{'; for (auto I : P.Obj) OS << ' ' << Print(I, P.G); @@ -310,16 +310,16 @@ raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) { return OS; } -raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterAggr> &P) { - P.Obj.print(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) << '>'; +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 << ' '; @@ -327,9 +327,6 @@ raw_ostream &operator<< (raw_ostream &OS, return OS; } -} // end namespace rdf -} // end namespace llvm - // Node allocation functions. // // Node allocator is like a slab memory allocator: it allocates blocks of @@ -340,13 +337,13 @@ raw_ostream &operator<< (raw_ostream &OS, // 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); + 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))) && + assert((Blocks.size() < ((size_t)1 << (8 * sizeof(NodeId) - BitsPerIndex))) && "Out of bits for block index"); ActiveEnd = P; } @@ -356,18 +353,17 @@ bool NodeAllocator::needNewBlock() { return true; char *ActiveBegin = Blocks.back(); - uint32_t Index = (ActiveEnd-ActiveBegin)/NodeMemSize; + uint32_t Index = (ActiveEnd - ActiveBegin) / NodeMemSize; return Index >= NodesPerBlock; } -NodeAddr<NodeBase*> NodeAllocator::New() { +Node 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) }; + 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; } @@ -376,9 +372,9 @@ 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) + if (A < B || A >= B + NodesPerBlock * NodeMemSize) continue; - uint32_t Idx = (A-B)/NodeMemSize; + uint32_t Idx = (A - B) / NodeMemSize; return makeId(i, Idx); } llvm_unreachable("Invalid node address"); @@ -391,7 +387,7 @@ void NodeAllocator::clear() { } // Insert node NA after "this" in the circular chain. -void NodeBase::append(NodeAddr<NodeBase*> NA) { +void NodeBase::append(Node NA) { NodeId Nx = Next; // If NA is already "next", do nothing. if (Next != NA.Id) { @@ -406,9 +402,9 @@ void NodeBase::append(NodeAddr<NodeBase*> NA) { 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); + 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 @@ -416,7 +412,7 @@ RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const { void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) { assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef); - Ref.PR = G.pack(RR); + RefData.PR = G.pack(RR); } // Set the register reference in the reference node based on a machine @@ -425,83 +421,82 @@ void RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) { assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)); (void)G; - Ref.Op = Op; + RefData.Op = Op; } // Get the owner of a given reference node. -NodeAddr<NodeBase*> RefNode::getOwner(const DataFlowGraph &G) { - NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); +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()); + 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(); +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, NodeAddr<DefNode*> DA) { - Ref.RD = DA.Id; - Ref.Sib = DA.Addr->getReachedUse(); +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. -NodeAddr<NodeBase*> CodeNode::getFirstMember(const DataFlowGraph &G) const { - if (Code.FirstM == 0) - return NodeAddr<NodeBase*>(); - return G.addr<NodeBase*>(Code.FirstM); +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. -NodeAddr<NodeBase*> CodeNode::getLastMember(const DataFlowGraph &G) const { - if (Code.LastM == 0) - return NodeAddr<NodeBase*>(); - return G.addr<NodeBase*>(Code.LastM); +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(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { - NodeAddr<NodeBase*> ML = getLastMember(G); +void CodeNode::addMember(Node NA, const DataFlowGraph &G) { + Node ML = getLastMember(G); if (ML.Id != 0) { ML.Addr->append(NA); } else { - Code.FirstM = NA.Id; + CodeData.FirstM = NA.Id; NodeId Self = G.id(this); NA.Addr->setNext(Self); } - Code.LastM = NA.Id; + CodeData.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) { +void CodeNode::addMemberAfter(Node MA, Node NA, const DataFlowGraph &G) { MA.Addr->append(NA); - if (Code.LastM == MA.Id) - Code.LastM = NA.Id; + if (CodeData.LastM == MA.Id) + CodeData.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); +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 (Code.LastM == MA.Id) { + if (CodeData.LastM == MA.Id) { // If it is the only member, set both first and last to 0. - Code.FirstM = Code.LastM = 0; + CodeData.FirstM = CodeData.LastM = 0; } else { // Otherwise, advance the first member. - Code.FirstM = MA.Addr->getNext(); + CodeData.FirstM = MA.Addr->getNext(); } return; } @@ -512,37 +507,37 @@ void CodeNode::removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { 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; + if (CodeData.LastM == NA.Id) + CodeData.LastM = MA.Id; return; } - MA = G.addr<NodeBase*>(MX); + 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; }; + static auto True = [](Node) -> 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()); +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()); + 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); +void BlockNode::addPhi(Phi PA, const DataFlowGraph &G) { + Node M = getFirstMember(G); if (M.Id == 0) { addMember(PA, G); return; @@ -552,15 +547,15 @@ void BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G) { 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; + 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); - NodeAddr<NodeBase*> MN = M; + Node MN = M; do { M = MN; - MN = G.addr<NodeBase*>(M.Addr->getNext()); + MN = G.addr<NodeBase *>(M.Addr->getNext()); assert(MN.Addr->getType() == NodeAttrs::Code); } while (MN.Addr->getKind() == NodeAttrs::Phi); @@ -571,19 +566,17 @@ void BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &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; - }; +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 NodeAddr<BlockNode*>(); + return Block(); } // Get the block node for the entry block in the given function. -NodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) { +Block FuncNode::getEntryBlock(const DataFlowGraph &G) { MachineBasicBlock *EntryB = &getCode()->front(); return findBlock(EntryB, G); } @@ -593,14 +586,14 @@ NodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) { // 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 { +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 { +bool TargetOperandInfo::isClobbering(const MachineInstr &In, + unsigned OpNum) const { const MachineOperand &Op = In.getOperand(OpNum); if (Op.isRegMask()) return true; @@ -612,8 +605,8 @@ bool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum) } // Check if the given instruction specifically requires -bool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum) - const { +bool TargetOperandInfo::isFixedReg(const MachineInstr &In, + unsigned OpNum) const { if (In.isCall() || In.isReturn() || In.isInlineAsm()) return true; // Check for a tail call. @@ -642,19 +635,20 @@ bool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum) // DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, - const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, - const MachineDominanceFrontier &mdf) + 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) { -} + LiveIns(PRI) {} DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, - const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, - const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi) + 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) { -} + LiveIns(PRI) {} // The implementation of the definition stack. // Each register reference has its own definition stack. In particular, @@ -663,7 +657,8 @@ DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, // Construct a stack iterator. DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S, - bool Top) : DS(S) { + bool Top) + : DS(S) { if (!Top) { // Initialize to bottom. Pos = 0; @@ -671,7 +666,7 @@ DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S, } // 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])) + while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos - 1])) Pos--; } @@ -695,7 +690,7 @@ void DataFlowGraph::DefStack::pop() { // 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)); + Stack.push_back(Def(nullptr, N)); } // Remove all nodes from the top of the stack, until the delimited for @@ -705,7 +700,7 @@ void DataFlowGraph::DefStack::clear_block(NodeId N) { assert(N != 0); unsigned P = Stack.size(); while (P > 0) { - bool Found = isDelimiter(Stack[P-1], N); + bool Found = isDelimiter(Stack[P - 1], N); P--; if (Found) break; @@ -723,7 +718,7 @@ unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const { assert(P < SS); do { P++; - IsDelim = isDelimiter(Stack[P-1]); + IsDelim = isDelimiter(Stack[P - 1]); } while (P < SS && IsDelim); assert(!IsDelim); return P; @@ -734,11 +729,11 @@ 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]); + bool IsDelim = isDelimiter(Stack[P - 1]); do { if (--P == 0) break; - IsDelim = isDelimiter(Stack[P-1]); + IsDelim = isDelimiter(Stack[P - 1]); } while (P > 0 && IsDelim); assert(!IsDelim); return P; @@ -746,11 +741,10 @@ unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { // Register information. -RegisterSet DataFlowGraph::getLandingPadLiveIns() const { - RegisterSet LR; +RegisterAggr DataFlowGraph::getLandingPadLiveIns() const { + RegisterAggr LR(getPRI()); const Function &F = MF.getFunction(); - const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() - : nullptr; + const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() : nullptr; const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering(); if (RegisterId R = TLI.getExceptionPointerRegister(PF)) LR.insert(RegisterRef(R)); @@ -778,8 +772,8 @@ NodeId DataFlowGraph::id(const NodeBase *P) const { } // Allocate a new node and set the attributes to Attrs. -NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) { - NodeAddr<NodeBase*> P = Memory.New(); +Node DataFlowGraph::newNode(uint16_t Attrs) { + Node P = Memory.New(); P.Addr->init(); P.Addr->setAttrs(Attrs); return P; @@ -787,16 +781,16 @@ NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) { // 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); +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) { - NodeAddr<RefNode*> RA = NA; + Ref RA = NA; RA.Addr->setReachingDef(0); RA.Addr->setSibling(0); if (NA.Addr->getKind() == NodeAttrs::Def) { - NodeAddr<DefNode*> DA = NA; + Def DA = NA; DA.Addr->setReachedDef(0); DA.Addr->setReachedUse(0); } @@ -806,75 +800,105 @@ NodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) { // 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); +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; } -NodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner, - RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) { - NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); +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; } -NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, - MachineOperand &Op, uint16_t Flags) { - NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); +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; } -NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, - RegisterRef RR, uint16_t Flags) { - NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); +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; } -NodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) { - NodeAddr<PhiNode*> PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); +Phi DataFlowGraph::newPhi(Block Owner) { + Phi 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); +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; } -NodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner, - MachineBasicBlock *BB) { - NodeAddr<BlockNode*> BA = newNode(NodeAttrs::Code | NodeAttrs::Block); +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; } -NodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) { - NodeAddr<FuncNode*> FA = newNode(NodeAttrs::Code | NodeAttrs::Func); +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(unsigned Options) { +void DataFlowGraph::build(const Config &config) { reset(); - Func = newFunc(&MF); + 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) { - NodeAddr<BlockNode*> BA = newBlock(Func, &B); + Block BA = newBlock(TheFunc, &B); BlockNodes.insert(std::make_pair(&B, BA)); for (MachineInstr &I : B) { if (I.isDebugInstr()) @@ -883,21 +907,13 @@ void DataFlowGraph::build(unsigned Options) { } } - 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)); + Block EA = TheFunc.Addr->getEntryBlock(*this); + NodeList Blocks = TheFunc.Addr->members(*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()) + for (std::pair<unsigned, unsigned> P : MRI.liveins()) LiveIns.insert(RegisterRef(P.first)); if (MRI.tracksLiveness()) { for (auto I : EntryB.liveins()) @@ -905,12 +921,12 @@ void DataFlowGraph::build(unsigned Options) { } // 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); + 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; - NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); + Def DA = newDef(PA, RR, PhiFlags); PA.Addr->addMember(DA, *this); } @@ -919,9 +935,9 @@ void DataFlowGraph::build(unsigned Options) { // 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(); + RegisterAggr EHRegs = getLandingPadLiveIns(); if (!EHRegs.empty()) { - for (NodeAddr<BlockNode*> BA : Blocks) { + for (Block BA : Blocks) { const MachineBasicBlock &B = *BA.Addr->getCode(); if (!B.isEHPad()) continue; @@ -932,15 +948,17 @@ void DataFlowGraph::build(unsigned Options) { Preds.push_back(findBlock(PB)); // Build phi nodes for each live-in. - for (RegisterRef RR : EHRegs) { - NodeAddr<PhiNode*> PA = newPhi(BA); + for (RegisterRef RR : EHRegs.refs()) { + if (RR.isReg() && !isTracked(RR)) + continue; + Phi PA = newPhi(BA); uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; // Add def: - NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); + Def 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); + for (Block PBA : Preds) { + PhiUse PUA = newPhiUse(PA, RR, PBA); PA.Addr->addMember(PUA, *this); } } @@ -949,24 +967,23 @@ void DataFlowGraph::build(unsigned Options) { // 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) + BlockRefsMap PhiM(getPRI()); + for (Block BA : Blocks) recordDefsForDF(PhiM, BA); - for (NodeAddr<BlockNode*> BA : Blocks) - buildPhis(PhiM, AllRefs, BA); + for (Block BA : Blocks) + buildPhis(PhiM, 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)) + if (!(BuildCfg.Options & BuildOptions::KeepDeadPhis)) removeUnusedPhis(); } RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const { - assert(PhysicalRegisterInfo::isRegMaskId(Reg) || - Register::isPhysicalRegister(Reg)); + assert(RegisterRef::isRegId(Reg) || RegisterRef::isMaskId(Reg)); assert(Reg != 0); if (Sub != 0) Reg = TRI.getSubReg(Reg, Sub); @@ -977,7 +994,8 @@ 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()); + return RegisterRef(getPRI().getRegMaskId(Op.getRegMask()), + LaneBitmask::getAll()); } // For each stack in the map DefM, push the delimiter for block B on it. @@ -1006,14 +1024,14 @@ void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { // Push all definitions from the instruction node IA to an appropriate // stack in DefM. -void DataFlowGraph::pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { +void DataFlowGraph::pushAllDefs(Instr 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) { +void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) { NodeSet Visited; std::set<RegisterId> Defined; @@ -1029,35 +1047,37 @@ void DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { // unspecified order), but the order does not matter from the data- // -flow perspective. - for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { + for (Def 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(); + Def 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)) { + for (RegisterId A : getPRI().getAliasSet(RR.Reg)) { + if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A))) + continue; // 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) + for (Node 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) { +void DataFlowGraph::pushDefs(Instr IA, DefStackMap &DefM) { NodeSet Visited; #ifndef NDEBUG std::set<RegisterId> Defined; @@ -1075,44 +1095,45 @@ void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { // unspecified order), but the order does not matter from the data- // -flow perspective. - for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { + for (Def 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(); + Def 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(RR, *this) << " in\n " << *MI << "in " - << printMBBReference(*MI->getParent()) << '\n'; + MachineInstr *MI = Stmt(IA).Addr->getCode(); + dbgs() << "Multiple definitions of register: " << Print(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)) { + for (RegisterId A : getPRI().getAliasSet(RR.Reg)) { + if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A))) + continue; // 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) + for (Node 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 { +NodeList DataFlowGraph::getRelatedRefs(Instr IA, Ref RA) const { assert(IA.Id != 0 && RA.Id != 0); NodeList Refs; @@ -1128,7 +1149,9 @@ NodeList DataFlowGraph::getRelatedRefs(NodeAddr<InstrNode*> IA, void DataFlowGraph::reset() { Memory.clear(); BlockNodes.clear(); - Func = NodeAddr<FuncNode*>(); + TrackedUnits.clear(); + ReservedRegs.clear(); + TheFunc = Func(); } // Return the next reference node in the instruction node IA that is related @@ -1137,36 +1160,38 @@ void DataFlowGraph::reset() { // 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 { +Ref DataFlowGraph::getNextRelated(Instr IA, Ref RA) const { assert(IA.Id != 0 && RA.Id != 0); - auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool { + auto IsRelated = [this, RA](Ref TA) -> bool { if (TA.Addr->getKind() != RA.Addr->getKind()) return false; - if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this)) + if (!getPRI().equal_to(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)) + + RegisterRef RR = RA.Addr->getRegRef(*this); + if (IA.Addr->getKind() == NodeAttrs::Stmt) { + auto Cond = [&IsRelated, RA](Ref TA) -> bool { + return IsRelated(TA) && &RA.Addr->getOp() == &TA.Addr->getOp(); + }; + return RA.Addr->getNextRef(RR, Cond, true, *this); + } + + assert(IA.Addr->getKind() == NodeAttrs::Phi); + auto Cond = [&IsRelated, RA](Ref TA) -> bool { + if (!IsRelated(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(); + return PhiUse(TA).Addr->getPredecessor() == + PhiUse(RA).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); + return RA.Addr->getNextRef(RR, Cond, true, *this); } // Find the next node related to RA in IA that satisfies condition P. @@ -1175,12 +1200,11 @@ NodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA, // 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 { +std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA, + Predicate P) const { assert(IA.Id != 0 && RA.Id != 0); - NodeAddr<RefNode*> NA; + Ref NA; NodeId Start = RA.Id; while (true) { NA = getNextRelated(IA, RA); @@ -1193,17 +1217,16 @@ DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, if (NA.Id != 0 && NA.Id != Start) return std::make_pair(RA, NA); - return std::make_pair(RA, NodeAddr<RefNode*>()); + return std::make_pair(RA, Ref()); } // 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) { +Ref DataFlowGraph::getNextShadow(Instr IA, Ref 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 { + auto IsShadow = [Flags](Ref TA) -> bool { return TA.Addr->getFlags() == Flags; }; auto Loc = locateNextRef(IA, RA, IsShadow); @@ -1211,30 +1234,18 @@ NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, return Loc.second; // Create a copy of RA and mark is as shadow. - NodeAddr<RefNode*> NA = cloneNode(RA); + Ref 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); +void DataFlowGraph::buildStmt(Block BA, MachineInstr &In) { + Stmt SA = newStmt(BA, &In); - auto isCall = [] (const MachineInstr &In) -> bool { + auto isCall = [](const MachineInstr &In) -> bool { if (In.isCall()) return true; // Is tail call? @@ -1251,14 +1262,14 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { return false; }; - auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool { + 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()) + for (const MachineOperand &Op : In.all_uses()) { + if (Op.getReg() == 0 || Op.isUndef()) continue; RegisterRef UR = makeRegRef(Op); - if (PRI.alias(DR, UR)) + if (getPRI().alias(DR, UR)) return false; } return true; @@ -1278,7 +1289,7 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) continue; Register R = Op.getReg(); - if (!R || !R.isPhysical()) + if (!R || !R.isPhysical() || !isTracked(RegisterRef(R))) continue; uint16_t Flags = NodeAttrs::None; if (TOI.isPreserving(In, OpN)) { @@ -1293,7 +1304,7 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { Flags |= NodeAttrs::Fixed; if (IsCall && Op.isDead()) Flags |= NodeAttrs::Dead; - NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + Def DA = newDef(SA, Op, Flags); SA.Addr->addMember(DA, *this); assert(!DoneDefs.test(R)); DoneDefs.set(R); @@ -1305,15 +1316,17 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { 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); + uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | NodeAttrs::Dead; + Def 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)))) + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { + if (!isTracked(RegisterRef(i))) + continue; + if (!(RM[i / 32] & (1u << (i % 32)))) DoneClobbers.set(i); + } } // Process implicit defs, skipping those that have already been added @@ -1323,7 +1336,7 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { if (!Op.isReg() || !Op.isDef() || !Op.isImplicit()) continue; Register R = Op.getReg(); - if (!R || !R.isPhysical() || DoneDefs.test(R)) + if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)) || DoneDefs.test(R)) continue; RegisterRef RR = makeRegRef(Op); uint16_t Flags = NodeAttrs::None; @@ -1342,7 +1355,7 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { continue; Flags |= NodeAttrs::Dead; } - NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + Def DA = newDef(SA, Op, Flags); SA.Addr->addMember(DA, *this); DoneDefs.set(R); } @@ -1352,22 +1365,21 @@ void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { if (!Op.isReg() || !Op.isUse()) continue; Register R = Op.getReg(); - if (!R || !R.isPhysical()) + if (!R || !R.isPhysical() || !isTracked(RegisterRef(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); + Use 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) { +void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, Block 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. @@ -1382,14 +1394,18 @@ void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, // 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)); + RegisterAggr Defs(getPRI()); + for (Instr IA : BA.Addr->members(*this)) { + for (Ref RA : IA.Addr->members_if(IsDef, *this)) { + RegisterRef RR = RA.Addr->getRegRef(*this); + if (RR.isReg() && isTracked(RR)) + Defs.insert(RR); + } + } // Calculate the iterated dominance frontier of BB. const MachineDominanceFrontier::DomSetType &DF = DFLoc->second; - SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end()); + 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()) @@ -1399,98 +1415,37 @@ void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, // 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()); + Block DBA = findBlock(DB); + PhiM[DBA.Id].insert(Defs); } } // 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) { +void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block 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); - } + const RegisterAggr &Defs = PhiM[BA.Id]; + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + + for (RegisterRef RR : Defs.refs()) { + Phi PA = newPhi(BA); + PA.Addr->addMember(newDef(PA, RR, PhiFlags), *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); - } + for (Block PBA : Preds) { + PA.Addr->addMember(newPhiUse(PA, RR, PBA), *this); } - - // Erase from MaxRefs all elements in the closure. - auto Begin = MaxRefs.begin(); - for (unsigned Idx : llvm::reverse(ClosureIdx)) - MaxRefs.erase(Begin + Idx); } } @@ -1503,16 +1458,16 @@ void DataFlowGraph::removeUnusedPhis() { // that are easily determinable to be unnecessary. SetVector<NodeId> PhiQ; - for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) { + for (Block BA : TheFunc.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) { + for (Node M : Ms) { if (M.Addr->getKind() != NodeAttrs::Def) continue; - NodeAddr<DefNode*> DA = M; + Def DA = M; if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0) return true; } @@ -1523,15 +1478,15 @@ void DataFlowGraph::removeUnusedPhis() { // 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]); + 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) { + for (Ref RA : Refs) { if (NodeId RD = RA.Addr->getReachingDef()) { - auto RDA = addr<DefNode*>(RD); - NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this); + auto RDA = addr<DefNode *>(RD); + Instr OA = RDA.Addr->getOwner(*this); if (IsPhi(OA)) PhiQ.insert(OA.Id); } @@ -1540,7 +1495,7 @@ void DataFlowGraph::removeUnusedPhis() { else unlinkUse(RA, true); } - NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this); + Block BA = PA.Addr->getOwner(*this); BA.Addr->removeMember(PA, *this); } } @@ -1549,15 +1504,14 @@ void DataFlowGraph::removeUnusedPhis() { // 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) { +void DataFlowGraph::linkRefUp(Instr 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); + RegisterAggr Defs(getPRI()); for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) { RegisterRef QR = I->Addr->getRegRef(*this); @@ -1573,7 +1527,7 @@ void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA, } // The reaching def. - NodeAddr<DefNode*> RDA = *I; + Def RDA = *I; // Pick the reached node. if (TAP.Id == 0) { @@ -1594,14 +1548,13 @@ void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA, // 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) { +void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) { #ifndef NDEBUG - RegisterSet Defs; + RegisterSet Defs(getPRI()); #endif // Link all nodes (upwards in the data-flow) with their reaching defs. - for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) { + for (Ref 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); @@ -1616,9 +1569,9 @@ void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA, continue; DefStack &DS = F->second; if (Kind == NodeAttrs::Use) - linkRefUp<UseNode*>(SA, RA, DS); + linkRefUp<UseNode *>(SA, RA, DS); else if (Kind == NodeAttrs::Def) - linkRefUp<DefNode*>(SA, RA, DS); + linkRefUp<DefNode *>(SA, RA, DS); else llvm_unreachable("Unexpected node in instruction"); } @@ -1626,14 +1579,14 @@ void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA, // 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) { +void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, Block BA) { // Push block delimiters. markBlock(BA.Id, DefM); - auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool { + auto IsClobber = [](Ref RA) -> bool { return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering); }; - auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool { + auto IsNoClobber = [](Ref RA) -> bool { return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering); }; @@ -1641,7 +1594,7 @@ void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) { // 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)) { + for (Instr 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) { @@ -1662,39 +1615,38 @@ void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) { MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); for (auto *I : *N) { MachineBasicBlock *SB = I->getBlock(); - NodeAddr<BlockNode*> SBA = findBlock(SB); + Block SBA = findBlock(SB); linkBlockRefs(DefM, SBA); } // Link the phi uses from the successor blocks. - auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool { + auto IsUseForBA = [BA](Node 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; + return PhiUse(NA).Addr->getPredecessor() == BA.Id; }; - RegisterSet EHLiveIns = getLandingPadLiveIns(); + RegisterAggr 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)) { + Block SBA = findBlock(SB); + for (Instr 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); + Ref RA = IA.Addr->getFirstMember(*this); assert(RA.Id != 0); - if (EHLiveIns.count(RA.Addr->getRegRef(*this))) + if (EHLiveIns.hasCoverOf(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; + PhiUse PUA = U; RegisterRef RR = PUA.Addr->getRegRef(*this); - linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]); + linkRefUp<UseNode *>(IA, PUA, DefM[RR.Reg]); } } } @@ -1704,7 +1656,7 @@ void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) { } // Remove the use node UA from any data-flow and structural links. -void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { +void DataFlowGraph::unlinkUseDF(Use UA) { NodeId RD = UA.Addr->getReachingDef(); NodeId Sib = UA.Addr->getSibling(); @@ -1713,8 +1665,8 @@ void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { return; } - auto RDA = addr<DefNode*>(RD); - auto TA = addr<UseNode*>(RDA.Addr->getReachedUse()); + auto RDA = addr<DefNode *>(RD); + auto TA = addr<UseNode *>(RDA.Addr->getReachedUse()); if (TA.Id == UA.Id) { RDA.Addr->setReachedUse(Sib); return; @@ -1726,12 +1678,12 @@ void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { TA.Addr->setSibling(UA.Addr->getSibling()); return; } - TA = addr<UseNode*>(S); + TA = addr<UseNode *>(S); } } // Remove the def node DA from any data-flow and structural links. -void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { +void DataFlowGraph::unlinkDefDF(Def DA) { // // RD // | reached @@ -1756,10 +1708,10 @@ void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { // 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 { + auto getAllNodes = [this](NodeId N) -> NodeList { NodeList Res; while (N) { - auto RA = addr<RefNode*>(N); + auto RA = addr<RefNode *>(N); // Keep the nodes in the exact sibling order. Res.push_back(RA); N = RA.Addr->getSibling(); @@ -1770,14 +1722,14 @@ void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse()); if (RD == 0) { - for (NodeAddr<RefNode*> I : ReachedDefs) + for (Ref I : ReachedDefs) I.Addr->setSibling(0); - for (NodeAddr<RefNode*> I : ReachedUses) + for (Ref I : ReachedUses) I.Addr->setSibling(0); } - for (NodeAddr<DefNode*> I : ReachedDefs) + for (Def I : ReachedDefs) I.Addr->setReachingDef(RD); - for (NodeAddr<UseNode*> I : ReachedUses) + for (Use I : ReachedUses) I.Addr->setReachingDef(RD); NodeId Sib = DA.Addr->getSibling(); @@ -1787,8 +1739,8 @@ void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { } // Update the reaching def node and remove DA from the sibling list. - auto RDA = addr<DefNode*>(RD); - auto TA = addr<DefNode*>(RDA.Addr->getReachedDef()); + 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. @@ -1802,20 +1754,46 @@ void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { TA.Addr->setSibling(Sib); break; } - TA = addr<DefNode*>(S); + 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()); + auto Last = Def(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()); + auto Last = Use(ReachedUses.back()); Last.Addr->setSibling(RDA.Addr->getReachedUse()); RDA.Addr->setReachedUse(ReachedUses.front().Id); } } + +bool DataFlowGraph::isTracked(RegisterRef RR) const { + return !disjoint(getPRI().getUnits(RR), TrackedUnits); +} + +bool DataFlowGraph::hasUntrackedRef(Stmt S, bool IgnoreReserved) const { + SmallVector<MachineOperand *> Ops; + + for (Ref R : S.Addr->members(*this)) { + Ops.push_back(&R.Addr->getOp()); + RegisterRef RR = R.Addr->getRegRef(*this); + if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.idx()]) + continue; + if (!isTracked(RR)) + return true; + } + for (const MachineOperand &Op : S.Addr->getCode()->operands()) { + if (!Op.isReg() && !Op.isRegMask()) + continue; + if (llvm::find(Ops, &Op) == Ops.end()) + return true; + } + return false; +} + +} // end namespace llvm::rdf |