1362593Sdim//===- RDFGraph.cpp -------------------------------------------------------===// 2362593Sdim// 3362593Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4362593Sdim// See https://llvm.org/LICENSE.txt for license information. 5362593Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6362593Sdim// 7362593Sdim//===----------------------------------------------------------------------===// 8362593Sdim// 9362593Sdim// Target-independent, SSA-based data flow graph for register data flow (RDF). 10362593Sdim// 11362593Sdim#include "llvm/ADT/BitVector.h" 12362593Sdim#include "llvm/ADT/STLExtras.h" 13362593Sdim#include "llvm/ADT/SetVector.h" 14362593Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 15362593Sdim#include "llvm/CodeGen/MachineDominanceFrontier.h" 16362593Sdim#include "llvm/CodeGen/MachineDominators.h" 17362593Sdim#include "llvm/CodeGen/MachineFunction.h" 18362593Sdim#include "llvm/CodeGen/MachineInstr.h" 19362593Sdim#include "llvm/CodeGen/MachineOperand.h" 20362593Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 21362593Sdim#include "llvm/CodeGen/RDFGraph.h" 22362593Sdim#include "llvm/CodeGen/RDFRegisters.h" 23362593Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 24362593Sdim#include "llvm/CodeGen/TargetLowering.h" 25362593Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 26362593Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 27362593Sdim#include "llvm/IR/Function.h" 28362593Sdim#include "llvm/MC/LaneBitmask.h" 29362593Sdim#include "llvm/MC/MCInstrDesc.h" 30362593Sdim#include "llvm/MC/MCRegisterInfo.h" 31362593Sdim#include "llvm/Support/Debug.h" 32362593Sdim#include "llvm/Support/ErrorHandling.h" 33362593Sdim#include "llvm/Support/raw_ostream.h" 34362593Sdim#include <algorithm> 35362593Sdim#include <cassert> 36362593Sdim#include <cstdint> 37362593Sdim#include <cstring> 38362593Sdim#include <iterator> 39362593Sdim#include <set> 40362593Sdim#include <utility> 41362593Sdim#include <vector> 42362593Sdim 43362593Sdimusing namespace llvm; 44362593Sdimusing namespace rdf; 45362593Sdim 46362593Sdim// Printing functions. Have them here first, so that the rest of the code 47362593Sdim// can use them. 48362593Sdimnamespace llvm { 49362593Sdimnamespace rdf { 50362593Sdim 51362593Sdimraw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P) { 52362593Sdim if (!P.Mask.all()) 53362593Sdim OS << ':' << PrintLaneMask(P.Mask); 54362593Sdim return OS; 55362593Sdim} 56362593Sdim 57362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<RegisterRef> &P) { 58362593Sdim auto &TRI = P.G.getTRI(); 59362593Sdim if (P.Obj.Reg > 0 && P.Obj.Reg < TRI.getNumRegs()) 60362593Sdim OS << TRI.getName(P.Obj.Reg); 61362593Sdim else 62362593Sdim OS << '#' << P.Obj.Reg; 63362593Sdim OS << PrintLaneMaskOpt(P.Obj.Mask); 64362593Sdim return OS; 65362593Sdim} 66362593Sdim 67362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeId> &P) { 68362593Sdim auto NA = P.G.addr<NodeBase*>(P.Obj); 69362593Sdim uint16_t Attrs = NA.Addr->getAttrs(); 70362593Sdim uint16_t Kind = NodeAttrs::kind(Attrs); 71362593Sdim uint16_t Flags = NodeAttrs::flags(Attrs); 72362593Sdim switch (NodeAttrs::type(Attrs)) { 73362593Sdim case NodeAttrs::Code: 74362593Sdim switch (Kind) { 75362593Sdim case NodeAttrs::Func: OS << 'f'; break; 76362593Sdim case NodeAttrs::Block: OS << 'b'; break; 77362593Sdim case NodeAttrs::Stmt: OS << 's'; break; 78362593Sdim case NodeAttrs::Phi: OS << 'p'; break; 79362593Sdim default: OS << "c?"; break; 80362593Sdim } 81362593Sdim break; 82362593Sdim case NodeAttrs::Ref: 83362593Sdim if (Flags & NodeAttrs::Undef) 84362593Sdim OS << '/'; 85362593Sdim if (Flags & NodeAttrs::Dead) 86362593Sdim OS << '\\'; 87362593Sdim if (Flags & NodeAttrs::Preserving) 88362593Sdim OS << '+'; 89362593Sdim if (Flags & NodeAttrs::Clobbering) 90362593Sdim OS << '~'; 91362593Sdim switch (Kind) { 92362593Sdim case NodeAttrs::Use: OS << 'u'; break; 93362593Sdim case NodeAttrs::Def: OS << 'd'; break; 94362593Sdim case NodeAttrs::Block: OS << 'b'; break; 95362593Sdim default: OS << "r?"; break; 96362593Sdim } 97362593Sdim break; 98362593Sdim default: 99362593Sdim OS << '?'; 100362593Sdim break; 101362593Sdim } 102362593Sdim OS << P.Obj; 103362593Sdim if (Flags & NodeAttrs::Shadow) 104362593Sdim OS << '"'; 105362593Sdim return OS; 106362593Sdim} 107362593Sdim 108362593Sdimstatic void printRefHeader(raw_ostream &OS, const NodeAddr<RefNode*> RA, 109362593Sdim const DataFlowGraph &G) { 110362593Sdim OS << Print<NodeId>(RA.Id, G) << '<' 111362593Sdim << Print<RegisterRef>(RA.Addr->getRegRef(G), G) << '>'; 112362593Sdim if (RA.Addr->getFlags() & NodeAttrs::Fixed) 113362593Sdim OS << '!'; 114362593Sdim} 115362593Sdim 116362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<DefNode*>> &P) { 117362593Sdim printRefHeader(OS, P.Obj, P.G); 118362593Sdim OS << '('; 119362593Sdim if (NodeId N = P.Obj.Addr->getReachingDef()) 120362593Sdim OS << Print<NodeId>(N, P.G); 121362593Sdim OS << ','; 122362593Sdim if (NodeId N = P.Obj.Addr->getReachedDef()) 123362593Sdim OS << Print<NodeId>(N, P.G); 124362593Sdim OS << ','; 125362593Sdim if (NodeId N = P.Obj.Addr->getReachedUse()) 126362593Sdim OS << Print<NodeId>(N, P.G); 127362593Sdim OS << "):"; 128362593Sdim if (NodeId N = P.Obj.Addr->getSibling()) 129362593Sdim OS << Print<NodeId>(N, P.G); 130362593Sdim return OS; 131362593Sdim} 132362593Sdim 133362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) { 134362593Sdim printRefHeader(OS, P.Obj, P.G); 135362593Sdim OS << '('; 136362593Sdim if (NodeId N = P.Obj.Addr->getReachingDef()) 137362593Sdim OS << Print<NodeId>(N, P.G); 138362593Sdim OS << "):"; 139362593Sdim if (NodeId N = P.Obj.Addr->getSibling()) 140362593Sdim OS << Print<NodeId>(N, P.G); 141362593Sdim return OS; 142362593Sdim} 143362593Sdim 144362593Sdimraw_ostream &operator<< (raw_ostream &OS, 145362593Sdim const Print<NodeAddr<PhiUseNode*>> &P) { 146362593Sdim printRefHeader(OS, P.Obj, P.G); 147362593Sdim OS << '('; 148362593Sdim if (NodeId N = P.Obj.Addr->getReachingDef()) 149362593Sdim OS << Print<NodeId>(N, P.G); 150362593Sdim OS << ','; 151362593Sdim if (NodeId N = P.Obj.Addr->getPredecessor()) 152362593Sdim OS << Print<NodeId>(N, P.G); 153362593Sdim OS << "):"; 154362593Sdim if (NodeId N = P.Obj.Addr->getSibling()) 155362593Sdim OS << Print<NodeId>(N, P.G); 156362593Sdim return OS; 157362593Sdim} 158362593Sdim 159362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<RefNode*>> &P) { 160362593Sdim switch (P.Obj.Addr->getKind()) { 161362593Sdim case NodeAttrs::Def: 162362593Sdim OS << PrintNode<DefNode*>(P.Obj, P.G); 163362593Sdim break; 164362593Sdim case NodeAttrs::Use: 165362593Sdim if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef) 166362593Sdim OS << PrintNode<PhiUseNode*>(P.Obj, P.G); 167362593Sdim else 168362593Sdim OS << PrintNode<UseNode*>(P.Obj, P.G); 169362593Sdim break; 170362593Sdim } 171362593Sdim return OS; 172362593Sdim} 173362593Sdim 174362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeList> &P) { 175362593Sdim unsigned N = P.Obj.size(); 176362593Sdim for (auto I : P.Obj) { 177362593Sdim OS << Print<NodeId>(I.Id, P.G); 178362593Sdim if (--N) 179362593Sdim OS << ' '; 180362593Sdim } 181362593Sdim return OS; 182362593Sdim} 183362593Sdim 184362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) { 185362593Sdim unsigned N = P.Obj.size(); 186362593Sdim for (auto I : P.Obj) { 187362593Sdim OS << Print<NodeId>(I, P.G); 188362593Sdim if (--N) 189362593Sdim OS << ' '; 190362593Sdim } 191362593Sdim return OS; 192362593Sdim} 193362593Sdim 194362593Sdimnamespace { 195362593Sdim 196362593Sdim template <typename T> 197362593Sdim struct PrintListV { 198362593Sdim PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} 199362593Sdim 200362593Sdim using Type = T; 201362593Sdim const NodeList &List; 202362593Sdim const DataFlowGraph &G; 203362593Sdim }; 204362593Sdim 205362593Sdim template <typename T> 206362593Sdim raw_ostream &operator<< (raw_ostream &OS, const PrintListV<T> &P) { 207362593Sdim unsigned N = P.List.size(); 208362593Sdim for (NodeAddr<T> A : P.List) { 209362593Sdim OS << PrintNode<T>(A, P.G); 210362593Sdim if (--N) 211362593Sdim OS << ", "; 212362593Sdim } 213362593Sdim return OS; 214362593Sdim } 215362593Sdim 216362593Sdim} // end anonymous namespace 217362593Sdim 218362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<PhiNode*>> &P) { 219362593Sdim OS << Print<NodeId>(P.Obj.Id, P.G) << ": phi [" 220362593Sdim << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; 221362593Sdim return OS; 222362593Sdim} 223362593Sdim 224362593Sdimraw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<StmtNode *>> &P) { 225362593Sdim const MachineInstr &MI = *P.Obj.Addr->getCode(); 226362593Sdim unsigned Opc = MI.getOpcode(); 227362593Sdim OS << Print<NodeId>(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc); 228362593Sdim // Print the target for calls and branches (for readability). 229362593Sdim if (MI.isCall() || MI.isBranch()) { 230362593Sdim MachineInstr::const_mop_iterator T = 231362593Sdim llvm::find_if(MI.operands(), 232362593Sdim [] (const MachineOperand &Op) -> bool { 233362593Sdim return Op.isMBB() || Op.isGlobal() || Op.isSymbol(); 234362593Sdim }); 235362593Sdim if (T != MI.operands_end()) { 236362593Sdim OS << ' '; 237362593Sdim if (T->isMBB()) 238362593Sdim OS << printMBBReference(*T->getMBB()); 239362593Sdim else if (T->isGlobal()) 240362593Sdim OS << T->getGlobal()->getName(); 241362593Sdim else if (T->isSymbol()) 242362593Sdim OS << T->getSymbolName(); 243362593Sdim } 244362593Sdim } 245362593Sdim OS << " [" << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; 246362593Sdim return OS; 247362593Sdim} 248362593Sdim 249362593Sdimraw_ostream &operator<< (raw_ostream &OS, 250362593Sdim const Print<NodeAddr<InstrNode*>> &P) { 251362593Sdim switch (P.Obj.Addr->getKind()) { 252362593Sdim case NodeAttrs::Phi: 253362593Sdim OS << PrintNode<PhiNode*>(P.Obj, P.G); 254362593Sdim break; 255362593Sdim case NodeAttrs::Stmt: 256362593Sdim OS << PrintNode<StmtNode*>(P.Obj, P.G); 257362593Sdim break; 258362593Sdim default: 259362593Sdim OS << "instr? " << Print<NodeId>(P.Obj.Id, P.G); 260362593Sdim break; 261362593Sdim } 262362593Sdim return OS; 263362593Sdim} 264362593Sdim 265362593Sdimraw_ostream &operator<< (raw_ostream &OS, 266362593Sdim const Print<NodeAddr<BlockNode*>> &P) { 267362593Sdim MachineBasicBlock *BB = P.Obj.Addr->getCode(); 268362593Sdim unsigned NP = BB->pred_size(); 269362593Sdim std::vector<int> Ns; 270362593Sdim auto PrintBBs = [&OS] (std::vector<int> Ns) -> void { 271362593Sdim unsigned N = Ns.size(); 272362593Sdim for (int I : Ns) { 273362593Sdim OS << "%bb." << I; 274362593Sdim if (--N) 275362593Sdim OS << ", "; 276362593Sdim } 277362593Sdim }; 278362593Sdim 279362593Sdim OS << Print<NodeId>(P.Obj.Id, P.G) << ": --- " << printMBBReference(*BB) 280362593Sdim << " --- preds(" << NP << "): "; 281362593Sdim for (MachineBasicBlock *B : BB->predecessors()) 282362593Sdim Ns.push_back(B->getNumber()); 283362593Sdim PrintBBs(Ns); 284362593Sdim 285362593Sdim unsigned NS = BB->succ_size(); 286362593Sdim OS << " succs(" << NS << "): "; 287362593Sdim Ns.clear(); 288362593Sdim for (MachineBasicBlock *B : BB->successors()) 289362593Sdim Ns.push_back(B->getNumber()); 290362593Sdim PrintBBs(Ns); 291362593Sdim OS << '\n'; 292362593Sdim 293362593Sdim for (auto I : P.Obj.Addr->members(P.G)) 294362593Sdim OS << PrintNode<InstrNode*>(I, P.G) << '\n'; 295362593Sdim return OS; 296362593Sdim} 297362593Sdim 298362593Sdimraw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<FuncNode *>> &P) { 299362593Sdim OS << "DFG dump:[\n" << Print<NodeId>(P.Obj.Id, P.G) << ": Function: " 300362593Sdim << P.Obj.Addr->getCode()->getName() << '\n'; 301362593Sdim for (auto I : P.Obj.Addr->members(P.G)) 302362593Sdim OS << PrintNode<BlockNode*>(I, P.G) << '\n'; 303362593Sdim OS << "]\n"; 304362593Sdim return OS; 305362593Sdim} 306362593Sdim 307362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) { 308362593Sdim OS << '{'; 309362593Sdim for (auto I : P.Obj) 310362593Sdim OS << ' ' << Print<RegisterRef>(I, P.G); 311362593Sdim OS << " }"; 312362593Sdim return OS; 313362593Sdim} 314362593Sdim 315362593Sdimraw_ostream &operator<< (raw_ostream &OS, const Print<RegisterAggr> &P) { 316362593Sdim P.Obj.print(OS); 317362593Sdim return OS; 318362593Sdim} 319362593Sdim 320362593Sdimraw_ostream &operator<< (raw_ostream &OS, 321362593Sdim const Print<DataFlowGraph::DefStack> &P) { 322362593Sdim for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) { 323362593Sdim OS << Print<NodeId>(I->Id, P.G) 324362593Sdim << '<' << Print<RegisterRef>(I->Addr->getRegRef(P.G), P.G) << '>'; 325362593Sdim I.down(); 326362593Sdim if (I != E) 327362593Sdim OS << ' '; 328362593Sdim } 329362593Sdim return OS; 330362593Sdim} 331362593Sdim 332362593Sdim} // end namespace rdf 333362593Sdim} // end namespace llvm 334362593Sdim 335362593Sdim// Node allocation functions. 336362593Sdim// 337362593Sdim// Node allocator is like a slab memory allocator: it allocates blocks of 338362593Sdim// memory in sizes that are multiples of the size of a node. Each block has 339362593Sdim// the same size. Nodes are allocated from the currently active block, and 340362593Sdim// when it becomes full, a new one is created. 341362593Sdim// There is a mapping scheme between node id and its location in a block, 342362593Sdim// and within that block is described in the header file. 343362593Sdim// 344362593Sdimvoid NodeAllocator::startNewBlock() { 345362593Sdim void *T = MemPool.Allocate(NodesPerBlock*NodeMemSize, NodeMemSize); 346362593Sdim char *P = static_cast<char*>(T); 347362593Sdim Blocks.push_back(P); 348362593Sdim // Check if the block index is still within the allowed range, i.e. less 349362593Sdim // than 2^N, where N is the number of bits in NodeId for the block index. 350362593Sdim // BitsPerIndex is the number of bits per node index. 351362593Sdim assert((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) && 352362593Sdim "Out of bits for block index"); 353362593Sdim ActiveEnd = P; 354362593Sdim} 355362593Sdim 356362593Sdimbool NodeAllocator::needNewBlock() { 357362593Sdim if (Blocks.empty()) 358362593Sdim return true; 359362593Sdim 360362593Sdim char *ActiveBegin = Blocks.back(); 361362593Sdim uint32_t Index = (ActiveEnd-ActiveBegin)/NodeMemSize; 362362593Sdim return Index >= NodesPerBlock; 363362593Sdim} 364362593Sdim 365362593SdimNodeAddr<NodeBase*> NodeAllocator::New() { 366362593Sdim if (needNewBlock()) 367362593Sdim startNewBlock(); 368362593Sdim 369362593Sdim uint32_t ActiveB = Blocks.size()-1; 370362593Sdim uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize; 371362593Sdim NodeAddr<NodeBase*> NA = { reinterpret_cast<NodeBase*>(ActiveEnd), 372362593Sdim makeId(ActiveB, Index) }; 373362593Sdim ActiveEnd += NodeMemSize; 374362593Sdim return NA; 375362593Sdim} 376362593Sdim 377362593SdimNodeId NodeAllocator::id(const NodeBase *P) const { 378362593Sdim uintptr_t A = reinterpret_cast<uintptr_t>(P); 379362593Sdim for (unsigned i = 0, n = Blocks.size(); i != n; ++i) { 380362593Sdim uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]); 381362593Sdim if (A < B || A >= B + NodesPerBlock*NodeMemSize) 382362593Sdim continue; 383362593Sdim uint32_t Idx = (A-B)/NodeMemSize; 384362593Sdim return makeId(i, Idx); 385362593Sdim } 386362593Sdim llvm_unreachable("Invalid node address"); 387362593Sdim} 388362593Sdim 389362593Sdimvoid NodeAllocator::clear() { 390362593Sdim MemPool.Reset(); 391362593Sdim Blocks.clear(); 392362593Sdim ActiveEnd = nullptr; 393362593Sdim} 394362593Sdim 395362593Sdim// Insert node NA after "this" in the circular chain. 396362593Sdimvoid NodeBase::append(NodeAddr<NodeBase*> NA) { 397362593Sdim NodeId Nx = Next; 398362593Sdim // If NA is already "next", do nothing. 399362593Sdim if (Next != NA.Id) { 400362593Sdim Next = NA.Id; 401362593Sdim NA.Addr->Next = Nx; 402362593Sdim } 403362593Sdim} 404362593Sdim 405362593Sdim// Fundamental node manipulator functions. 406362593Sdim 407362593Sdim// Obtain the register reference from a reference node. 408362593SdimRegisterRef RefNode::getRegRef(const DataFlowGraph &G) const { 409362593Sdim assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); 410362593Sdim if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef) 411362593Sdim return G.unpack(Ref.PR); 412362593Sdim assert(Ref.Op != nullptr); 413362593Sdim return G.makeRegRef(*Ref.Op); 414362593Sdim} 415362593Sdim 416362593Sdim// Set the register reference in the reference node directly (for references 417362593Sdim// in phi nodes). 418362593Sdimvoid RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) { 419362593Sdim assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); 420362593Sdim assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef); 421362593Sdim Ref.PR = G.pack(RR); 422362593Sdim} 423362593Sdim 424362593Sdim// Set the register reference in the reference node based on a machine 425362593Sdim// operand (for references in statement nodes). 426362593Sdimvoid RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) { 427362593Sdim assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); 428362593Sdim assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)); 429362593Sdim (void)G; 430362593Sdim Ref.Op = Op; 431362593Sdim} 432362593Sdim 433362593Sdim// Get the owner of a given reference node. 434362593SdimNodeAddr<NodeBase*> RefNode::getOwner(const DataFlowGraph &G) { 435362593Sdim NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); 436362593Sdim 437362593Sdim while (NA.Addr != this) { 438362593Sdim if (NA.Addr->getType() == NodeAttrs::Code) 439362593Sdim return NA; 440362593Sdim NA = G.addr<NodeBase*>(NA.Addr->getNext()); 441362593Sdim } 442362593Sdim llvm_unreachable("No owner in circular list"); 443362593Sdim} 444362593Sdim 445362593Sdim// Connect the def node to the reaching def node. 446362593Sdimvoid DefNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { 447362593Sdim Ref.RD = DA.Id; 448362593Sdim Ref.Sib = DA.Addr->getReachedDef(); 449362593Sdim DA.Addr->setReachedDef(Self); 450362593Sdim} 451362593Sdim 452362593Sdim// Connect the use node to the reaching def node. 453362593Sdimvoid UseNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { 454362593Sdim Ref.RD = DA.Id; 455362593Sdim Ref.Sib = DA.Addr->getReachedUse(); 456362593Sdim DA.Addr->setReachedUse(Self); 457362593Sdim} 458362593Sdim 459362593Sdim// Get the first member of the code node. 460362593SdimNodeAddr<NodeBase*> CodeNode::getFirstMember(const DataFlowGraph &G) const { 461362593Sdim if (Code.FirstM == 0) 462362593Sdim return NodeAddr<NodeBase*>(); 463362593Sdim return G.addr<NodeBase*>(Code.FirstM); 464362593Sdim} 465362593Sdim 466362593Sdim// Get the last member of the code node. 467362593SdimNodeAddr<NodeBase*> CodeNode::getLastMember(const DataFlowGraph &G) const { 468362593Sdim if (Code.LastM == 0) 469362593Sdim return NodeAddr<NodeBase*>(); 470362593Sdim return G.addr<NodeBase*>(Code.LastM); 471362593Sdim} 472362593Sdim 473362593Sdim// Add node NA at the end of the member list of the given code node. 474362593Sdimvoid CodeNode::addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { 475362593Sdim NodeAddr<NodeBase*> ML = getLastMember(G); 476362593Sdim if (ML.Id != 0) { 477362593Sdim ML.Addr->append(NA); 478362593Sdim } else { 479362593Sdim Code.FirstM = NA.Id; 480362593Sdim NodeId Self = G.id(this); 481362593Sdim NA.Addr->setNext(Self); 482362593Sdim } 483362593Sdim Code.LastM = NA.Id; 484362593Sdim} 485362593Sdim 486362593Sdim// Add node NA after member node MA in the given code node. 487362593Sdimvoid CodeNode::addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA, 488362593Sdim const DataFlowGraph &G) { 489362593Sdim MA.Addr->append(NA); 490362593Sdim if (Code.LastM == MA.Id) 491362593Sdim Code.LastM = NA.Id; 492362593Sdim} 493362593Sdim 494362593Sdim// Remove member node NA from the given code node. 495362593Sdimvoid CodeNode::removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { 496362593Sdim NodeAddr<NodeBase*> MA = getFirstMember(G); 497362593Sdim assert(MA.Id != 0); 498362593Sdim 499362593Sdim // Special handling if the member to remove is the first member. 500362593Sdim if (MA.Id == NA.Id) { 501362593Sdim if (Code.LastM == MA.Id) { 502362593Sdim // If it is the only member, set both first and last to 0. 503362593Sdim Code.FirstM = Code.LastM = 0; 504362593Sdim } else { 505362593Sdim // Otherwise, advance the first member. 506362593Sdim Code.FirstM = MA.Addr->getNext(); 507362593Sdim } 508362593Sdim return; 509362593Sdim } 510362593Sdim 511362593Sdim while (MA.Addr != this) { 512362593Sdim NodeId MX = MA.Addr->getNext(); 513362593Sdim if (MX == NA.Id) { 514362593Sdim MA.Addr->setNext(NA.Addr->getNext()); 515362593Sdim // If the member to remove happens to be the last one, update the 516362593Sdim // LastM indicator. 517362593Sdim if (Code.LastM == NA.Id) 518362593Sdim Code.LastM = MA.Id; 519362593Sdim return; 520362593Sdim } 521362593Sdim MA = G.addr<NodeBase*>(MX); 522362593Sdim } 523362593Sdim llvm_unreachable("No such member"); 524362593Sdim} 525362593Sdim 526362593Sdim// Return the list of all members of the code node. 527362593SdimNodeList CodeNode::members(const DataFlowGraph &G) const { 528362593Sdim static auto True = [] (NodeAddr<NodeBase*>) -> bool { return true; }; 529362593Sdim return members_if(True, G); 530362593Sdim} 531362593Sdim 532362593Sdim// Return the owner of the given instr node. 533362593SdimNodeAddr<NodeBase*> InstrNode::getOwner(const DataFlowGraph &G) { 534362593Sdim NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); 535362593Sdim 536362593Sdim while (NA.Addr != this) { 537362593Sdim assert(NA.Addr->getType() == NodeAttrs::Code); 538362593Sdim if (NA.Addr->getKind() == NodeAttrs::Block) 539362593Sdim return NA; 540362593Sdim NA = G.addr<NodeBase*>(NA.Addr->getNext()); 541362593Sdim } 542362593Sdim llvm_unreachable("No owner in circular list"); 543362593Sdim} 544362593Sdim 545362593Sdim// Add the phi node PA to the given block node. 546362593Sdimvoid BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G) { 547362593Sdim NodeAddr<NodeBase*> M = getFirstMember(G); 548362593Sdim if (M.Id == 0) { 549362593Sdim addMember(PA, G); 550362593Sdim return; 551362593Sdim } 552362593Sdim 553362593Sdim assert(M.Addr->getType() == NodeAttrs::Code); 554362593Sdim if (M.Addr->getKind() == NodeAttrs::Stmt) { 555362593Sdim // If the first member of the block is a statement, insert the phi as 556362593Sdim // the first member. 557362593Sdim Code.FirstM = PA.Id; 558362593Sdim PA.Addr->setNext(M.Id); 559362593Sdim } else { 560362593Sdim // If the first member is a phi, find the last phi, and append PA to it. 561362593Sdim assert(M.Addr->getKind() == NodeAttrs::Phi); 562362593Sdim NodeAddr<NodeBase*> MN = M; 563362593Sdim do { 564362593Sdim M = MN; 565362593Sdim MN = G.addr<NodeBase*>(M.Addr->getNext()); 566362593Sdim assert(MN.Addr->getType() == NodeAttrs::Code); 567362593Sdim } while (MN.Addr->getKind() == NodeAttrs::Phi); 568362593Sdim 569362593Sdim // M is the last phi. 570362593Sdim addMemberAfter(M, PA, G); 571362593Sdim } 572362593Sdim} 573362593Sdim 574362593Sdim// Find the block node corresponding to the machine basic block BB in the 575362593Sdim// given func node. 576362593SdimNodeAddr<BlockNode*> FuncNode::findBlock(const MachineBasicBlock *BB, 577362593Sdim const DataFlowGraph &G) const { 578362593Sdim auto EqBB = [BB] (NodeAddr<NodeBase*> NA) -> bool { 579362593Sdim return NodeAddr<BlockNode*>(NA).Addr->getCode() == BB; 580362593Sdim }; 581362593Sdim NodeList Ms = members_if(EqBB, G); 582362593Sdim if (!Ms.empty()) 583362593Sdim return Ms[0]; 584362593Sdim return NodeAddr<BlockNode*>(); 585362593Sdim} 586362593Sdim 587362593Sdim// Get the block node for the entry block in the given function. 588362593SdimNodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) { 589362593Sdim MachineBasicBlock *EntryB = &getCode()->front(); 590362593Sdim return findBlock(EntryB, G); 591362593Sdim} 592362593Sdim 593362593Sdim// Target operand information. 594362593Sdim// 595362593Sdim 596362593Sdim// For a given instruction, check if there are any bits of RR that can remain 597362593Sdim// unchanged across this def. 598362593Sdimbool TargetOperandInfo::isPreserving(const MachineInstr &In, unsigned OpNum) 599362593Sdim const { 600362593Sdim return TII.isPredicated(In); 601362593Sdim} 602362593Sdim 603362593Sdim// Check if the definition of RR produces an unspecified value. 604362593Sdimbool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum) 605362593Sdim const { 606362593Sdim const MachineOperand &Op = In.getOperand(OpNum); 607362593Sdim if (Op.isRegMask()) 608362593Sdim return true; 609362593Sdim assert(Op.isReg()); 610362593Sdim if (In.isCall()) 611362593Sdim if (Op.isDef() && Op.isDead()) 612362593Sdim return true; 613362593Sdim return false; 614362593Sdim} 615362593Sdim 616362593Sdim// Check if the given instruction specifically requires 617362593Sdimbool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum) 618362593Sdim const { 619362593Sdim if (In.isCall() || In.isReturn() || In.isInlineAsm()) 620362593Sdim return true; 621362593Sdim // Check for a tail call. 622362593Sdim if (In.isBranch()) 623362593Sdim for (const MachineOperand &O : In.operands()) 624362593Sdim if (O.isGlobal() || O.isSymbol()) 625362593Sdim return true; 626362593Sdim 627362593Sdim const MCInstrDesc &D = In.getDesc(); 628362593Sdim if (!D.getImplicitDefs() && !D.getImplicitUses()) 629362593Sdim return false; 630362593Sdim const MachineOperand &Op = In.getOperand(OpNum); 631362593Sdim // If there is a sub-register, treat the operand as non-fixed. Currently, 632362593Sdim // fixed registers are those that are listed in the descriptor as implicit 633362593Sdim // uses or defs, and those lists do not allow sub-registers. 634362593Sdim if (Op.getSubReg() != 0) 635362593Sdim return false; 636362593Sdim Register Reg = Op.getReg(); 637362593Sdim const MCPhysReg *ImpR = Op.isDef() ? D.getImplicitDefs() 638362593Sdim : D.getImplicitUses(); 639362593Sdim if (!ImpR) 640362593Sdim return false; 641362593Sdim while (*ImpR) 642362593Sdim if (*ImpR++ == Reg) 643362593Sdim return true; 644362593Sdim return false; 645362593Sdim} 646362593Sdim 647362593Sdim// 648362593Sdim// The data flow graph construction. 649362593Sdim// 650362593Sdim 651362593SdimDataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, 652362593Sdim const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, 653362593Sdim const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi) 654362593Sdim : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi), 655362593Sdim LiveIns(PRI) { 656362593Sdim} 657362593Sdim 658362593Sdim// The implementation of the definition stack. 659362593Sdim// Each register reference has its own definition stack. In particular, 660362593Sdim// for a register references "Reg" and "Reg:subreg" will each have their 661362593Sdim// own definition stacks. 662362593Sdim 663362593Sdim// Construct a stack iterator. 664362593SdimDataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S, 665362593Sdim bool Top) : DS(S) { 666362593Sdim if (!Top) { 667362593Sdim // Initialize to bottom. 668362593Sdim Pos = 0; 669362593Sdim return; 670362593Sdim } 671362593Sdim // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty). 672362593Sdim Pos = DS.Stack.size(); 673362593Sdim while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos-1])) 674362593Sdim Pos--; 675362593Sdim} 676362593Sdim 677362593Sdim// Return the size of the stack, including block delimiters. 678362593Sdimunsigned DataFlowGraph::DefStack::size() const { 679362593Sdim unsigned S = 0; 680362593Sdim for (auto I = top(), E = bottom(); I != E; I.down()) 681362593Sdim S++; 682362593Sdim return S; 683362593Sdim} 684362593Sdim 685362593Sdim// Remove the top entry from the stack. Remove all intervening delimiters 686362593Sdim// so that after this, the stack is either empty, or the top of the stack 687362593Sdim// is a non-delimiter. 688362593Sdimvoid DataFlowGraph::DefStack::pop() { 689362593Sdim assert(!empty()); 690362593Sdim unsigned P = nextDown(Stack.size()); 691362593Sdim Stack.resize(P); 692362593Sdim} 693362593Sdim 694362593Sdim// Push a delimiter for block node N on the stack. 695362593Sdimvoid DataFlowGraph::DefStack::start_block(NodeId N) { 696362593Sdim assert(N != 0); 697362593Sdim Stack.push_back(NodeAddr<DefNode*>(nullptr, N)); 698362593Sdim} 699362593Sdim 700362593Sdim// Remove all nodes from the top of the stack, until the delimited for 701362593Sdim// block node N is encountered. Remove the delimiter as well. In effect, 702362593Sdim// this will remove from the stack all definitions from block N. 703362593Sdimvoid DataFlowGraph::DefStack::clear_block(NodeId N) { 704362593Sdim assert(N != 0); 705362593Sdim unsigned P = Stack.size(); 706362593Sdim while (P > 0) { 707362593Sdim bool Found = isDelimiter(Stack[P-1], N); 708362593Sdim P--; 709362593Sdim if (Found) 710362593Sdim break; 711362593Sdim } 712362593Sdim // This will also remove the delimiter, if found. 713362593Sdim Stack.resize(P); 714362593Sdim} 715362593Sdim 716362593Sdim// Move the stack iterator up by one. 717362593Sdimunsigned DataFlowGraph::DefStack::nextUp(unsigned P) const { 718362593Sdim // Get the next valid position after P (skipping all delimiters). 719362593Sdim // The input position P does not have to point to a non-delimiter. 720362593Sdim unsigned SS = Stack.size(); 721362593Sdim bool IsDelim; 722362593Sdim assert(P < SS); 723362593Sdim do { 724362593Sdim P++; 725362593Sdim IsDelim = isDelimiter(Stack[P-1]); 726362593Sdim } while (P < SS && IsDelim); 727362593Sdim assert(!IsDelim); 728362593Sdim return P; 729362593Sdim} 730362593Sdim 731362593Sdim// Move the stack iterator down by one. 732362593Sdimunsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { 733362593Sdim // Get the preceding valid position before P (skipping all delimiters). 734362593Sdim // The input position P does not have to point to a non-delimiter. 735362593Sdim assert(P > 0 && P <= Stack.size()); 736362593Sdim bool IsDelim = isDelimiter(Stack[P-1]); 737362593Sdim do { 738362593Sdim if (--P == 0) 739362593Sdim break; 740362593Sdim IsDelim = isDelimiter(Stack[P-1]); 741362593Sdim } while (P > 0 && IsDelim); 742362593Sdim assert(!IsDelim); 743362593Sdim return P; 744362593Sdim} 745362593Sdim 746362593Sdim// Register information. 747362593Sdim 748362593SdimRegisterSet DataFlowGraph::getLandingPadLiveIns() const { 749362593Sdim RegisterSet LR; 750362593Sdim const Function &F = MF.getFunction(); 751362593Sdim const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() 752362593Sdim : nullptr; 753362593Sdim const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering(); 754362593Sdim if (RegisterId R = TLI.getExceptionPointerRegister(PF)) 755362593Sdim LR.insert(RegisterRef(R)); 756362593Sdim if (!isFuncletEHPersonality(classifyEHPersonality(PF))) { 757362593Sdim if (RegisterId R = TLI.getExceptionSelectorRegister(PF)) 758362593Sdim LR.insert(RegisterRef(R)); 759362593Sdim } 760362593Sdim return LR; 761362593Sdim} 762362593Sdim 763362593Sdim// Node management functions. 764362593Sdim 765362593Sdim// Get the pointer to the node with the id N. 766362593SdimNodeBase *DataFlowGraph::ptr(NodeId N) const { 767362593Sdim if (N == 0) 768362593Sdim return nullptr; 769362593Sdim return Memory.ptr(N); 770362593Sdim} 771362593Sdim 772362593Sdim// Get the id of the node at the address P. 773362593SdimNodeId DataFlowGraph::id(const NodeBase *P) const { 774362593Sdim if (P == nullptr) 775362593Sdim return 0; 776362593Sdim return Memory.id(P); 777362593Sdim} 778362593Sdim 779362593Sdim// Allocate a new node and set the attributes to Attrs. 780362593SdimNodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) { 781362593Sdim NodeAddr<NodeBase*> P = Memory.New(); 782362593Sdim P.Addr->init(); 783362593Sdim P.Addr->setAttrs(Attrs); 784362593Sdim return P; 785362593Sdim} 786362593Sdim 787362593Sdim// Make a copy of the given node B, except for the data-flow links, which 788362593Sdim// are set to 0. 789362593SdimNodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) { 790362593Sdim NodeAddr<NodeBase*> NA = newNode(0); 791362593Sdim memcpy(NA.Addr, B.Addr, sizeof(NodeBase)); 792362593Sdim // Ref nodes need to have the data-flow links reset. 793362593Sdim if (NA.Addr->getType() == NodeAttrs::Ref) { 794362593Sdim NodeAddr<RefNode*> RA = NA; 795362593Sdim RA.Addr->setReachingDef(0); 796362593Sdim RA.Addr->setSibling(0); 797362593Sdim if (NA.Addr->getKind() == NodeAttrs::Def) { 798362593Sdim NodeAddr<DefNode*> DA = NA; 799362593Sdim DA.Addr->setReachedDef(0); 800362593Sdim DA.Addr->setReachedUse(0); 801362593Sdim } 802362593Sdim } 803362593Sdim return NA; 804362593Sdim} 805362593Sdim 806362593Sdim// Allocation routines for specific node types/kinds. 807362593Sdim 808362593SdimNodeAddr<UseNode*> DataFlowGraph::newUse(NodeAddr<InstrNode*> Owner, 809362593Sdim MachineOperand &Op, uint16_t Flags) { 810362593Sdim NodeAddr<UseNode*> UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); 811362593Sdim UA.Addr->setRegRef(&Op, *this); 812362593Sdim return UA; 813362593Sdim} 814362593Sdim 815362593SdimNodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner, 816362593Sdim RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) { 817362593Sdim NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); 818362593Sdim assert(Flags & NodeAttrs::PhiRef); 819362593Sdim PUA.Addr->setRegRef(RR, *this); 820362593Sdim PUA.Addr->setPredecessor(PredB.Id); 821362593Sdim return PUA; 822362593Sdim} 823362593Sdim 824362593SdimNodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, 825362593Sdim MachineOperand &Op, uint16_t Flags) { 826362593Sdim NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); 827362593Sdim DA.Addr->setRegRef(&Op, *this); 828362593Sdim return DA; 829362593Sdim} 830362593Sdim 831362593SdimNodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, 832362593Sdim RegisterRef RR, uint16_t Flags) { 833362593Sdim NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); 834362593Sdim assert(Flags & NodeAttrs::PhiRef); 835362593Sdim DA.Addr->setRegRef(RR, *this); 836362593Sdim return DA; 837362593Sdim} 838362593Sdim 839362593SdimNodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) { 840362593Sdim NodeAddr<PhiNode*> PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); 841362593Sdim Owner.Addr->addPhi(PA, *this); 842362593Sdim return PA; 843362593Sdim} 844362593Sdim 845362593SdimNodeAddr<StmtNode*> DataFlowGraph::newStmt(NodeAddr<BlockNode*> Owner, 846362593Sdim MachineInstr *MI) { 847362593Sdim NodeAddr<StmtNode*> SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt); 848362593Sdim SA.Addr->setCode(MI); 849362593Sdim Owner.Addr->addMember(SA, *this); 850362593Sdim return SA; 851362593Sdim} 852362593Sdim 853362593SdimNodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner, 854362593Sdim MachineBasicBlock *BB) { 855362593Sdim NodeAddr<BlockNode*> BA = newNode(NodeAttrs::Code | NodeAttrs::Block); 856362593Sdim BA.Addr->setCode(BB); 857362593Sdim Owner.Addr->addMember(BA, *this); 858362593Sdim return BA; 859362593Sdim} 860362593Sdim 861362593SdimNodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) { 862362593Sdim NodeAddr<FuncNode*> FA = newNode(NodeAttrs::Code | NodeAttrs::Func); 863362593Sdim FA.Addr->setCode(MF); 864362593Sdim return FA; 865362593Sdim} 866362593Sdim 867362593Sdim// Build the data flow graph. 868362593Sdimvoid DataFlowGraph::build(unsigned Options) { 869362593Sdim reset(); 870362593Sdim Func = newFunc(&MF); 871362593Sdim 872362593Sdim if (MF.empty()) 873362593Sdim return; 874362593Sdim 875362593Sdim for (MachineBasicBlock &B : MF) { 876362593Sdim NodeAddr<BlockNode*> BA = newBlock(Func, &B); 877362593Sdim BlockNodes.insert(std::make_pair(&B, BA)); 878362593Sdim for (MachineInstr &I : B) { 879362593Sdim if (I.isDebugInstr()) 880362593Sdim continue; 881362593Sdim buildStmt(BA, I); 882362593Sdim } 883362593Sdim } 884362593Sdim 885362593Sdim NodeAddr<BlockNode*> EA = Func.Addr->getEntryBlock(*this); 886362593Sdim NodeList Blocks = Func.Addr->members(*this); 887362593Sdim 888362593Sdim // Collect information about block references. 889362593Sdim RegisterSet AllRefs; 890362593Sdim for (NodeAddr<BlockNode*> BA : Blocks) 891362593Sdim for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) 892362593Sdim for (NodeAddr<RefNode*> RA : IA.Addr->members(*this)) 893362593Sdim AllRefs.insert(RA.Addr->getRegRef(*this)); 894362593Sdim 895362593Sdim // Collect function live-ins and entry block live-ins. 896362593Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 897362593Sdim MachineBasicBlock &EntryB = *EA.Addr->getCode(); 898362593Sdim assert(EntryB.pred_empty() && "Function entry block has predecessors"); 899362593Sdim for (std::pair<unsigned,unsigned> P : MRI.liveins()) 900362593Sdim LiveIns.insert(RegisterRef(P.first)); 901362593Sdim if (MRI.tracksLiveness()) { 902362593Sdim for (auto I : EntryB.liveins()) 903362593Sdim LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask)); 904362593Sdim } 905362593Sdim 906362593Sdim // Add function-entry phi nodes for the live-in registers. 907362593Sdim //for (std::pair<RegisterId,LaneBitmask> P : LiveIns) { 908362593Sdim for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) { 909362593Sdim RegisterRef RR = *I; 910362593Sdim NodeAddr<PhiNode*> PA = newPhi(EA); 911362593Sdim uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; 912362593Sdim NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); 913362593Sdim PA.Addr->addMember(DA, *this); 914362593Sdim } 915362593Sdim 916362593Sdim // Add phis for landing pads. 917362593Sdim // Landing pads, unlike usual backs blocks, are not entered through 918362593Sdim // branches in the program, or fall-throughs from other blocks. They 919362593Sdim // are entered from the exception handling runtime and target's ABI 920362593Sdim // may define certain registers as defined on entry to such a block. 921362593Sdim RegisterSet EHRegs = getLandingPadLiveIns(); 922362593Sdim if (!EHRegs.empty()) { 923362593Sdim for (NodeAddr<BlockNode*> BA : Blocks) { 924362593Sdim const MachineBasicBlock &B = *BA.Addr->getCode(); 925362593Sdim if (!B.isEHPad()) 926362593Sdim continue; 927362593Sdim 928362593Sdim // Prepare a list of NodeIds of the block's predecessors. 929362593Sdim NodeList Preds; 930362593Sdim for (MachineBasicBlock *PB : B.predecessors()) 931362593Sdim Preds.push_back(findBlock(PB)); 932362593Sdim 933362593Sdim // Build phi nodes for each live-in. 934362593Sdim for (RegisterRef RR : EHRegs) { 935362593Sdim NodeAddr<PhiNode*> PA = newPhi(BA); 936362593Sdim uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; 937362593Sdim // Add def: 938362593Sdim NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); 939362593Sdim PA.Addr->addMember(DA, *this); 940362593Sdim // Add uses (no reaching defs for phi uses): 941362593Sdim for (NodeAddr<BlockNode*> PBA : Preds) { 942362593Sdim NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA); 943362593Sdim PA.Addr->addMember(PUA, *this); 944362593Sdim } 945362593Sdim } 946362593Sdim } 947362593Sdim } 948362593Sdim 949362593Sdim // Build a map "PhiM" which will contain, for each block, the set 950362593Sdim // of references that will require phi definitions in that block. 951362593Sdim BlockRefsMap PhiM; 952362593Sdim for (NodeAddr<BlockNode*> BA : Blocks) 953362593Sdim recordDefsForDF(PhiM, BA); 954362593Sdim for (NodeAddr<BlockNode*> BA : Blocks) 955362593Sdim buildPhis(PhiM, AllRefs, BA); 956362593Sdim 957362593Sdim // Link all the refs. This will recursively traverse the dominator tree. 958362593Sdim DefStackMap DM; 959362593Sdim linkBlockRefs(DM, EA); 960362593Sdim 961362593Sdim // Finally, remove all unused phi nodes. 962362593Sdim if (!(Options & BuildOptions::KeepDeadPhis)) 963362593Sdim removeUnusedPhis(); 964362593Sdim} 965362593Sdim 966362593SdimRegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const { 967362593Sdim assert(PhysicalRegisterInfo::isRegMaskId(Reg) || 968362593Sdim Register::isPhysicalRegister(Reg)); 969362593Sdim assert(Reg != 0); 970362593Sdim if (Sub != 0) 971362593Sdim Reg = TRI.getSubReg(Reg, Sub); 972362593Sdim return RegisterRef(Reg); 973362593Sdim} 974362593Sdim 975362593SdimRegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const { 976362593Sdim assert(Op.isReg() || Op.isRegMask()); 977362593Sdim if (Op.isReg()) 978362593Sdim return makeRegRef(Op.getReg(), Op.getSubReg()); 979362593Sdim return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll()); 980362593Sdim} 981362593Sdim 982362593SdimRegisterRef DataFlowGraph::restrictRef(RegisterRef AR, RegisterRef BR) const { 983362593Sdim if (AR.Reg == BR.Reg) { 984362593Sdim LaneBitmask M = AR.Mask & BR.Mask; 985362593Sdim return M.any() ? RegisterRef(AR.Reg, M) : RegisterRef(); 986362593Sdim } 987362593Sdim#ifndef NDEBUG 988362593Sdim// RegisterRef NAR = PRI.normalize(AR); 989362593Sdim// RegisterRef NBR = PRI.normalize(BR); 990362593Sdim// assert(NAR.Reg != NBR.Reg); 991362593Sdim#endif 992362593Sdim // This isn't strictly correct, because the overlap may happen in the 993362593Sdim // part masked out. 994362593Sdim if (PRI.alias(AR, BR)) 995362593Sdim return AR; 996362593Sdim return RegisterRef(); 997362593Sdim} 998362593Sdim 999362593Sdim// For each stack in the map DefM, push the delimiter for block B on it. 1000362593Sdimvoid DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) { 1001362593Sdim // Push block delimiters. 1002362593Sdim for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) 1003362593Sdim I->second.start_block(B); 1004362593Sdim} 1005362593Sdim 1006362593Sdim// Remove all definitions coming from block B from each stack in DefM. 1007362593Sdimvoid DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { 1008362593Sdim // Pop all defs from this block from the definition stack. Defs that were 1009362593Sdim // added to the map during the traversal of instructions will not have a 1010362593Sdim // delimiter, but for those, the whole stack will be emptied. 1011362593Sdim for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) 1012362593Sdim I->second.clear_block(B); 1013362593Sdim 1014362593Sdim // Finally, remove empty stacks from the map. 1015362593Sdim for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) { 1016362593Sdim NextI = std::next(I); 1017362593Sdim // This preserves the validity of iterators other than I. 1018362593Sdim if (I->second.empty()) 1019362593Sdim DefM.erase(I); 1020362593Sdim } 1021362593Sdim} 1022362593Sdim 1023362593Sdim// Push all definitions from the instruction node IA to an appropriate 1024362593Sdim// stack in DefM. 1025362593Sdimvoid DataFlowGraph::pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { 1026362593Sdim pushClobbers(IA, DefM); 1027362593Sdim pushDefs(IA, DefM); 1028362593Sdim} 1029362593Sdim 1030362593Sdim// Push all definitions from the instruction node IA to an appropriate 1031362593Sdim// stack in DefM. 1032362593Sdimvoid DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { 1033362593Sdim NodeSet Visited; 1034362593Sdim std::set<RegisterId> Defined; 1035362593Sdim 1036362593Sdim // The important objectives of this function are: 1037362593Sdim // - to be able to handle instructions both while the graph is being 1038362593Sdim // constructed, and after the graph has been constructed, and 1039362593Sdim // - maintain proper ordering of definitions on the stack for each 1040362593Sdim // register reference: 1041362593Sdim // - if there are two or more related defs in IA (i.e. coming from 1042362593Sdim // the same machine operand), then only push one def on the stack, 1043362593Sdim // - if there are multiple unrelated defs of non-overlapping 1044362593Sdim // subregisters of S, then the stack for S will have both (in an 1045362593Sdim // unspecified order), but the order does not matter from the data- 1046362593Sdim // -flow perspective. 1047362593Sdim 1048362593Sdim for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { 1049362593Sdim if (Visited.count(DA.Id)) 1050362593Sdim continue; 1051362593Sdim if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering)) 1052362593Sdim continue; 1053362593Sdim 1054362593Sdim NodeList Rel = getRelatedRefs(IA, DA); 1055362593Sdim NodeAddr<DefNode*> PDA = Rel.front(); 1056362593Sdim RegisterRef RR = PDA.Addr->getRegRef(*this); 1057362593Sdim 1058362593Sdim // Push the definition on the stack for the register and all aliases. 1059362593Sdim // The def stack traversal in linkNodeUp will check the exact aliasing. 1060362593Sdim DefM[RR.Reg].push(DA); 1061362593Sdim Defined.insert(RR.Reg); 1062362593Sdim for (RegisterId A : PRI.getAliasSet(RR.Reg)) { 1063362593Sdim // Check that we don't push the same def twice. 1064362593Sdim assert(A != RR.Reg); 1065362593Sdim if (!Defined.count(A)) 1066362593Sdim DefM[A].push(DA); 1067362593Sdim } 1068362593Sdim // Mark all the related defs as visited. 1069362593Sdim for (NodeAddr<NodeBase*> T : Rel) 1070362593Sdim Visited.insert(T.Id); 1071362593Sdim } 1072362593Sdim} 1073362593Sdim 1074362593Sdim// Push all definitions from the instruction node IA to an appropriate 1075362593Sdim// stack in DefM. 1076362593Sdimvoid DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { 1077362593Sdim NodeSet Visited; 1078362593Sdim#ifndef NDEBUG 1079362593Sdim std::set<RegisterId> Defined; 1080362593Sdim#endif 1081362593Sdim 1082362593Sdim // The important objectives of this function are: 1083362593Sdim // - to be able to handle instructions both while the graph is being 1084362593Sdim // constructed, and after the graph has been constructed, and 1085362593Sdim // - maintain proper ordering of definitions on the stack for each 1086362593Sdim // register reference: 1087362593Sdim // - if there are two or more related defs in IA (i.e. coming from 1088362593Sdim // the same machine operand), then only push one def on the stack, 1089362593Sdim // - if there are multiple unrelated defs of non-overlapping 1090362593Sdim // subregisters of S, then the stack for S will have both (in an 1091362593Sdim // unspecified order), but the order does not matter from the data- 1092362593Sdim // -flow perspective. 1093362593Sdim 1094362593Sdim for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { 1095362593Sdim if (Visited.count(DA.Id)) 1096362593Sdim continue; 1097362593Sdim if (DA.Addr->getFlags() & NodeAttrs::Clobbering) 1098362593Sdim continue; 1099362593Sdim 1100362593Sdim NodeList Rel = getRelatedRefs(IA, DA); 1101362593Sdim NodeAddr<DefNode*> PDA = Rel.front(); 1102362593Sdim RegisterRef RR = PDA.Addr->getRegRef(*this); 1103362593Sdim#ifndef NDEBUG 1104362593Sdim // Assert if the register is defined in two or more unrelated defs. 1105362593Sdim // This could happen if there are two or more def operands defining it. 1106362593Sdim if (!Defined.insert(RR.Reg).second) { 1107362593Sdim MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); 1108362593Sdim dbgs() << "Multiple definitions of register: " 1109362593Sdim << Print<RegisterRef>(RR, *this) << " in\n " << *MI << "in " 1110362593Sdim << printMBBReference(*MI->getParent()) << '\n'; 1111362593Sdim llvm_unreachable(nullptr); 1112362593Sdim } 1113362593Sdim#endif 1114362593Sdim // Push the definition on the stack for the register and all aliases. 1115362593Sdim // The def stack traversal in linkNodeUp will check the exact aliasing. 1116362593Sdim DefM[RR.Reg].push(DA); 1117362593Sdim for (RegisterId A : PRI.getAliasSet(RR.Reg)) { 1118362593Sdim // Check that we don't push the same def twice. 1119362593Sdim assert(A != RR.Reg); 1120362593Sdim DefM[A].push(DA); 1121362593Sdim } 1122362593Sdim // Mark all the related defs as visited. 1123362593Sdim for (NodeAddr<NodeBase*> T : Rel) 1124362593Sdim Visited.insert(T.Id); 1125362593Sdim } 1126362593Sdim} 1127362593Sdim 1128362593Sdim// Return the list of all reference nodes related to RA, including RA itself. 1129362593Sdim// See "getNextRelated" for the meaning of a "related reference". 1130362593SdimNodeList DataFlowGraph::getRelatedRefs(NodeAddr<InstrNode*> IA, 1131362593Sdim NodeAddr<RefNode*> RA) const { 1132362593Sdim assert(IA.Id != 0 && RA.Id != 0); 1133362593Sdim 1134362593Sdim NodeList Refs; 1135362593Sdim NodeId Start = RA.Id; 1136362593Sdim do { 1137362593Sdim Refs.push_back(RA); 1138362593Sdim RA = getNextRelated(IA, RA); 1139362593Sdim } while (RA.Id != 0 && RA.Id != Start); 1140362593Sdim return Refs; 1141362593Sdim} 1142362593Sdim 1143362593Sdim// Clear all information in the graph. 1144362593Sdimvoid DataFlowGraph::reset() { 1145362593Sdim Memory.clear(); 1146362593Sdim BlockNodes.clear(); 1147362593Sdim Func = NodeAddr<FuncNode*>(); 1148362593Sdim} 1149362593Sdim 1150362593Sdim// Return the next reference node in the instruction node IA that is related 1151362593Sdim// to RA. Conceptually, two reference nodes are related if they refer to the 1152362593Sdim// same instance of a register access, but differ in flags or other minor 1153362593Sdim// characteristics. Specific examples of related nodes are shadow reference 1154362593Sdim// nodes. 1155362593Sdim// Return the equivalent of nullptr if there are no more related references. 1156362593SdimNodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA, 1157362593Sdim NodeAddr<RefNode*> RA) const { 1158362593Sdim assert(IA.Id != 0 && RA.Id != 0); 1159362593Sdim 1160362593Sdim auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool { 1161362593Sdim if (TA.Addr->getKind() != RA.Addr->getKind()) 1162362593Sdim return false; 1163362593Sdim if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this)) 1164362593Sdim return false; 1165362593Sdim return true; 1166362593Sdim }; 1167362593Sdim auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { 1168362593Sdim return Related(TA) && 1169362593Sdim &RA.Addr->getOp() == &TA.Addr->getOp(); 1170362593Sdim }; 1171362593Sdim auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { 1172362593Sdim if (!Related(TA)) 1173362593Sdim return false; 1174362593Sdim if (TA.Addr->getKind() != NodeAttrs::Use) 1175362593Sdim return true; 1176362593Sdim // For phi uses, compare predecessor blocks. 1177362593Sdim const NodeAddr<const PhiUseNode*> TUA = TA; 1178362593Sdim const NodeAddr<const PhiUseNode*> RUA = RA; 1179362593Sdim return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor(); 1180362593Sdim }; 1181362593Sdim 1182362593Sdim RegisterRef RR = RA.Addr->getRegRef(*this); 1183362593Sdim if (IA.Addr->getKind() == NodeAttrs::Stmt) 1184362593Sdim return RA.Addr->getNextRef(RR, RelatedStmt, true, *this); 1185362593Sdim return RA.Addr->getNextRef(RR, RelatedPhi, true, *this); 1186362593Sdim} 1187362593Sdim 1188362593Sdim// Find the next node related to RA in IA that satisfies condition P. 1189362593Sdim// If such a node was found, return a pair where the second element is the 1190362593Sdim// located node. If such a node does not exist, return a pair where the 1191362593Sdim// first element is the element after which such a node should be inserted, 1192362593Sdim// and the second element is a null-address. 1193362593Sdimtemplate <typename Predicate> 1194362593Sdimstd::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>> 1195362593SdimDataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, 1196362593Sdim Predicate P) const { 1197362593Sdim assert(IA.Id != 0 && RA.Id != 0); 1198362593Sdim 1199362593Sdim NodeAddr<RefNode*> NA; 1200362593Sdim NodeId Start = RA.Id; 1201362593Sdim while (true) { 1202362593Sdim NA = getNextRelated(IA, RA); 1203362593Sdim if (NA.Id == 0 || NA.Id == Start) 1204362593Sdim break; 1205362593Sdim if (P(NA)) 1206362593Sdim break; 1207362593Sdim RA = NA; 1208362593Sdim } 1209362593Sdim 1210362593Sdim if (NA.Id != 0 && NA.Id != Start) 1211362593Sdim return std::make_pair(RA, NA); 1212362593Sdim return std::make_pair(RA, NodeAddr<RefNode*>()); 1213362593Sdim} 1214362593Sdim 1215362593Sdim// Get the next shadow node in IA corresponding to RA, and optionally create 1216362593Sdim// such a node if it does not exist. 1217362593SdimNodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, 1218362593Sdim NodeAddr<RefNode*> RA, bool Create) { 1219362593Sdim assert(IA.Id != 0 && RA.Id != 0); 1220362593Sdim 1221362593Sdim uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; 1222362593Sdim auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { 1223362593Sdim return TA.Addr->getFlags() == Flags; 1224362593Sdim }; 1225362593Sdim auto Loc = locateNextRef(IA, RA, IsShadow); 1226362593Sdim if (Loc.second.Id != 0 || !Create) 1227362593Sdim return Loc.second; 1228362593Sdim 1229362593Sdim // Create a copy of RA and mark is as shadow. 1230362593Sdim NodeAddr<RefNode*> NA = cloneNode(RA); 1231362593Sdim NA.Addr->setFlags(Flags | NodeAttrs::Shadow); 1232362593Sdim IA.Addr->addMemberAfter(Loc.first, NA, *this); 1233362593Sdim return NA; 1234362593Sdim} 1235362593Sdim 1236362593Sdim// Get the next shadow node in IA corresponding to RA. Return null-address 1237362593Sdim// if such a node does not exist. 1238362593SdimNodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, 1239362593Sdim NodeAddr<RefNode*> RA) const { 1240362593Sdim assert(IA.Id != 0 && RA.Id != 0); 1241362593Sdim uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; 1242362593Sdim auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { 1243362593Sdim return TA.Addr->getFlags() == Flags; 1244362593Sdim }; 1245362593Sdim return locateNextRef(IA, RA, IsShadow).second; 1246362593Sdim} 1247362593Sdim 1248362593Sdim// Create a new statement node in the block node BA that corresponds to 1249362593Sdim// the machine instruction MI. 1250362593Sdimvoid DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { 1251362593Sdim NodeAddr<StmtNode*> SA = newStmt(BA, &In); 1252362593Sdim 1253362593Sdim auto isCall = [] (const MachineInstr &In) -> bool { 1254362593Sdim if (In.isCall()) 1255362593Sdim return true; 1256362593Sdim // Is tail call? 1257362593Sdim if (In.isBranch()) { 1258362593Sdim for (const MachineOperand &Op : In.operands()) 1259362593Sdim if (Op.isGlobal() || Op.isSymbol()) 1260362593Sdim return true; 1261362593Sdim // Assume indirect branches are calls. This is for the purpose of 1262362593Sdim // keeping implicit operands, and so it won't hurt on intra-function 1263362593Sdim // indirect branches. 1264362593Sdim if (In.isIndirectBranch()) 1265362593Sdim return true; 1266362593Sdim } 1267362593Sdim return false; 1268362593Sdim }; 1269362593Sdim 1270362593Sdim auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool { 1271362593Sdim // This instruction defines DR. Check if there is a use operand that 1272362593Sdim // would make DR live on entry to the instruction. 1273362593Sdim for (const MachineOperand &Op : In.operands()) { 1274362593Sdim if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef()) 1275362593Sdim continue; 1276362593Sdim RegisterRef UR = makeRegRef(Op); 1277362593Sdim if (PRI.alias(DR, UR)) 1278362593Sdim return false; 1279362593Sdim } 1280362593Sdim return true; 1281362593Sdim }; 1282362593Sdim 1283362593Sdim bool IsCall = isCall(In); 1284362593Sdim unsigned NumOps = In.getNumOperands(); 1285362593Sdim 1286362593Sdim // Avoid duplicate implicit defs. This will not detect cases of implicit 1287362593Sdim // defs that define registers that overlap, but it is not clear how to 1288362593Sdim // interpret that in the absence of explicit defs. Overlapping explicit 1289362593Sdim // defs are likely illegal already. 1290362593Sdim BitVector DoneDefs(TRI.getNumRegs()); 1291362593Sdim // Process explicit defs first. 1292362593Sdim for (unsigned OpN = 0; OpN < NumOps; ++OpN) { 1293362593Sdim MachineOperand &Op = In.getOperand(OpN); 1294362593Sdim if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) 1295362593Sdim continue; 1296362593Sdim Register R = Op.getReg(); 1297362593Sdim if (!R || !Register::isPhysicalRegister(R)) 1298362593Sdim continue; 1299362593Sdim uint16_t Flags = NodeAttrs::None; 1300362593Sdim if (TOI.isPreserving(In, OpN)) { 1301362593Sdim Flags |= NodeAttrs::Preserving; 1302362593Sdim // If the def is preserving, check if it is also undefined. 1303362593Sdim if (isDefUndef(In, makeRegRef(Op))) 1304362593Sdim Flags |= NodeAttrs::Undef; 1305362593Sdim } 1306362593Sdim if (TOI.isClobbering(In, OpN)) 1307362593Sdim Flags |= NodeAttrs::Clobbering; 1308362593Sdim if (TOI.isFixedReg(In, OpN)) 1309362593Sdim Flags |= NodeAttrs::Fixed; 1310362593Sdim if (IsCall && Op.isDead()) 1311362593Sdim Flags |= NodeAttrs::Dead; 1312362593Sdim NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); 1313362593Sdim SA.Addr->addMember(DA, *this); 1314362593Sdim assert(!DoneDefs.test(R)); 1315362593Sdim DoneDefs.set(R); 1316362593Sdim } 1317362593Sdim 1318362593Sdim // Process reg-masks (as clobbers). 1319362593Sdim BitVector DoneClobbers(TRI.getNumRegs()); 1320362593Sdim for (unsigned OpN = 0; OpN < NumOps; ++OpN) { 1321362593Sdim MachineOperand &Op = In.getOperand(OpN); 1322362593Sdim if (!Op.isRegMask()) 1323362593Sdim continue; 1324362593Sdim uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | 1325362593Sdim NodeAttrs::Dead; 1326362593Sdim NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); 1327362593Sdim SA.Addr->addMember(DA, *this); 1328362593Sdim // Record all clobbered registers in DoneDefs. 1329362593Sdim const uint32_t *RM = Op.getRegMask(); 1330362593Sdim for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) 1331362593Sdim if (!(RM[i/32] & (1u << (i%32)))) 1332362593Sdim DoneClobbers.set(i); 1333362593Sdim } 1334362593Sdim 1335362593Sdim // Process implicit defs, skipping those that have already been added 1336362593Sdim // as explicit. 1337362593Sdim for (unsigned OpN = 0; OpN < NumOps; ++OpN) { 1338362593Sdim MachineOperand &Op = In.getOperand(OpN); 1339362593Sdim if (!Op.isReg() || !Op.isDef() || !Op.isImplicit()) 1340362593Sdim continue; 1341362593Sdim Register R = Op.getReg(); 1342362593Sdim if (!R || !Register::isPhysicalRegister(R) || DoneDefs.test(R)) 1343362593Sdim continue; 1344362593Sdim RegisterRef RR = makeRegRef(Op); 1345362593Sdim uint16_t Flags = NodeAttrs::None; 1346362593Sdim if (TOI.isPreserving(In, OpN)) { 1347362593Sdim Flags |= NodeAttrs::Preserving; 1348362593Sdim // If the def is preserving, check if it is also undefined. 1349362593Sdim if (isDefUndef(In, RR)) 1350362593Sdim Flags |= NodeAttrs::Undef; 1351362593Sdim } 1352362593Sdim if (TOI.isClobbering(In, OpN)) 1353362593Sdim Flags |= NodeAttrs::Clobbering; 1354362593Sdim if (TOI.isFixedReg(In, OpN)) 1355362593Sdim Flags |= NodeAttrs::Fixed; 1356362593Sdim if (IsCall && Op.isDead()) { 1357362593Sdim if (DoneClobbers.test(R)) 1358362593Sdim continue; 1359362593Sdim Flags |= NodeAttrs::Dead; 1360362593Sdim } 1361362593Sdim NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); 1362362593Sdim SA.Addr->addMember(DA, *this); 1363362593Sdim DoneDefs.set(R); 1364362593Sdim } 1365362593Sdim 1366362593Sdim for (unsigned OpN = 0; OpN < NumOps; ++OpN) { 1367362593Sdim MachineOperand &Op = In.getOperand(OpN); 1368362593Sdim if (!Op.isReg() || !Op.isUse()) 1369362593Sdim continue; 1370362593Sdim Register R = Op.getReg(); 1371362593Sdim if (!R || !Register::isPhysicalRegister(R)) 1372362593Sdim continue; 1373362593Sdim uint16_t Flags = NodeAttrs::None; 1374362593Sdim if (Op.isUndef()) 1375362593Sdim Flags |= NodeAttrs::Undef; 1376362593Sdim if (TOI.isFixedReg(In, OpN)) 1377362593Sdim Flags |= NodeAttrs::Fixed; 1378362593Sdim NodeAddr<UseNode*> UA = newUse(SA, Op, Flags); 1379362593Sdim SA.Addr->addMember(UA, *this); 1380362593Sdim } 1381362593Sdim} 1382362593Sdim 1383362593Sdim// Scan all defs in the block node BA and record in PhiM the locations of 1384362593Sdim// phi nodes corresponding to these defs. 1385362593Sdimvoid DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, 1386362593Sdim NodeAddr<BlockNode*> BA) { 1387362593Sdim // Check all defs from block BA and record them in each block in BA's 1388362593Sdim // iterated dominance frontier. This information will later be used to 1389362593Sdim // create phi nodes. 1390362593Sdim MachineBasicBlock *BB = BA.Addr->getCode(); 1391362593Sdim assert(BB); 1392362593Sdim auto DFLoc = MDF.find(BB); 1393362593Sdim if (DFLoc == MDF.end() || DFLoc->second.empty()) 1394362593Sdim return; 1395362593Sdim 1396362593Sdim // Traverse all instructions in the block and collect the set of all 1397362593Sdim // defined references. For each reference there will be a phi created 1398362593Sdim // in the block's iterated dominance frontier. 1399362593Sdim // This is done to make sure that each defined reference gets only one 1400362593Sdim // phi node, even if it is defined multiple times. 1401362593Sdim RegisterSet Defs; 1402362593Sdim for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) 1403362593Sdim for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this)) 1404362593Sdim Defs.insert(RA.Addr->getRegRef(*this)); 1405362593Sdim 1406362593Sdim // Calculate the iterated dominance frontier of BB. 1407362593Sdim const MachineDominanceFrontier::DomSetType &DF = DFLoc->second; 1408362593Sdim SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end()); 1409362593Sdim for (unsigned i = 0; i < IDF.size(); ++i) { 1410362593Sdim auto F = MDF.find(IDF[i]); 1411362593Sdim if (F != MDF.end()) 1412362593Sdim IDF.insert(F->second.begin(), F->second.end()); 1413362593Sdim } 1414362593Sdim 1415362593Sdim // Finally, add the set of defs to each block in the iterated dominance 1416362593Sdim // frontier. 1417362593Sdim for (auto DB : IDF) { 1418362593Sdim NodeAddr<BlockNode*> DBA = findBlock(DB); 1419362593Sdim PhiM[DBA.Id].insert(Defs.begin(), Defs.end()); 1420362593Sdim } 1421362593Sdim} 1422362593Sdim 1423362593Sdim// Given the locations of phi nodes in the map PhiM, create the phi nodes 1424362593Sdim// that are located in the block node BA. 1425362593Sdimvoid DataFlowGraph::buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs, 1426362593Sdim NodeAddr<BlockNode*> BA) { 1427362593Sdim // Check if this blocks has any DF defs, i.e. if there are any defs 1428362593Sdim // that this block is in the iterated dominance frontier of. 1429362593Sdim auto HasDF = PhiM.find(BA.Id); 1430362593Sdim if (HasDF == PhiM.end() || HasDF->second.empty()) 1431362593Sdim return; 1432362593Sdim 1433362593Sdim // First, remove all R in Refs in such that there exists T in Refs 1434362593Sdim // such that T covers R. In other words, only leave those refs that 1435362593Sdim // are not covered by another ref (i.e. maximal with respect to covering). 1436362593Sdim 1437362593Sdim auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef { 1438362593Sdim for (RegisterRef I : RRs) 1439362593Sdim if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI)) 1440362593Sdim RR = I; 1441362593Sdim return RR; 1442362593Sdim }; 1443362593Sdim 1444362593Sdim RegisterSet MaxDF; 1445362593Sdim for (RegisterRef I : HasDF->second) 1446362593Sdim MaxDF.insert(MaxCoverIn(I, HasDF->second)); 1447362593Sdim 1448362593Sdim std::vector<RegisterRef> MaxRefs; 1449362593Sdim for (RegisterRef I : MaxDF) 1450362593Sdim MaxRefs.push_back(MaxCoverIn(I, AllRefs)); 1451362593Sdim 1452362593Sdim // Now, for each R in MaxRefs, get the alias closure of R. If the closure 1453362593Sdim // only has R in it, create a phi a def for R. Otherwise, create a phi, 1454362593Sdim // and add a def for each S in the closure. 1455362593Sdim 1456362593Sdim // Sort the refs so that the phis will be created in a deterministic order. 1457362593Sdim llvm::sort(MaxRefs); 1458362593Sdim // Remove duplicates. 1459362593Sdim auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); 1460362593Sdim MaxRefs.erase(NewEnd, MaxRefs.end()); 1461362593Sdim 1462362593Sdim auto Aliased = [this,&MaxRefs](RegisterRef RR, 1463362593Sdim std::vector<unsigned> &Closure) -> bool { 1464362593Sdim for (unsigned I : Closure) 1465362593Sdim if (PRI.alias(RR, MaxRefs[I])) 1466362593Sdim return true; 1467362593Sdim return false; 1468362593Sdim }; 1469362593Sdim 1470362593Sdim // Prepare a list of NodeIds of the block's predecessors. 1471362593Sdim NodeList Preds; 1472362593Sdim const MachineBasicBlock *MBB = BA.Addr->getCode(); 1473362593Sdim for (MachineBasicBlock *PB : MBB->predecessors()) 1474362593Sdim Preds.push_back(findBlock(PB)); 1475362593Sdim 1476362593Sdim while (!MaxRefs.empty()) { 1477362593Sdim // Put the first element in the closure, and then add all subsequent 1478362593Sdim // elements from MaxRefs to it, if they alias at least one element 1479362593Sdim // already in the closure. 1480362593Sdim // ClosureIdx: vector of indices in MaxRefs of members of the closure. 1481362593Sdim std::vector<unsigned> ClosureIdx = { 0 }; 1482362593Sdim for (unsigned i = 1; i != MaxRefs.size(); ++i) 1483362593Sdim if (Aliased(MaxRefs[i], ClosureIdx)) 1484362593Sdim ClosureIdx.push_back(i); 1485362593Sdim 1486362593Sdim // Build a phi for the closure. 1487362593Sdim unsigned CS = ClosureIdx.size(); 1488362593Sdim NodeAddr<PhiNode*> PA = newPhi(BA); 1489362593Sdim 1490362593Sdim // Add defs. 1491362593Sdim for (unsigned X = 0; X != CS; ++X) { 1492362593Sdim RegisterRef RR = MaxRefs[ClosureIdx[X]]; 1493362593Sdim uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; 1494362593Sdim NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); 1495362593Sdim PA.Addr->addMember(DA, *this); 1496362593Sdim } 1497362593Sdim // Add phi uses. 1498362593Sdim for (NodeAddr<BlockNode*> PBA : Preds) { 1499362593Sdim for (unsigned X = 0; X != CS; ++X) { 1500362593Sdim RegisterRef RR = MaxRefs[ClosureIdx[X]]; 1501362593Sdim NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA); 1502362593Sdim PA.Addr->addMember(PUA, *this); 1503362593Sdim } 1504362593Sdim } 1505362593Sdim 1506362593Sdim // Erase from MaxRefs all elements in the closure. 1507362593Sdim auto Begin = MaxRefs.begin(); 1508362593Sdim for (unsigned i = ClosureIdx.size(); i != 0; --i) 1509362593Sdim MaxRefs.erase(Begin + ClosureIdx[i-1]); 1510362593Sdim } 1511362593Sdim} 1512362593Sdim 1513362593Sdim// Remove any unneeded phi nodes that were created during the build process. 1514362593Sdimvoid DataFlowGraph::removeUnusedPhis() { 1515362593Sdim // This will remove unused phis, i.e. phis where each def does not reach 1516362593Sdim // any uses or other defs. This will not detect or remove circular phi 1517362593Sdim // chains that are otherwise dead. Unused/dead phis are created during 1518362593Sdim // the build process and this function is intended to remove these cases 1519362593Sdim // that are easily determinable to be unnecessary. 1520362593Sdim 1521362593Sdim SetVector<NodeId> PhiQ; 1522362593Sdim for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) { 1523362593Sdim for (auto P : BA.Addr->members_if(IsPhi, *this)) 1524362593Sdim PhiQ.insert(P.Id); 1525362593Sdim } 1526362593Sdim 1527362593Sdim static auto HasUsedDef = [](NodeList &Ms) -> bool { 1528362593Sdim for (NodeAddr<NodeBase*> M : Ms) { 1529362593Sdim if (M.Addr->getKind() != NodeAttrs::Def) 1530362593Sdim continue; 1531362593Sdim NodeAddr<DefNode*> DA = M; 1532362593Sdim if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0) 1533362593Sdim return true; 1534362593Sdim } 1535362593Sdim return false; 1536362593Sdim }; 1537362593Sdim 1538362593Sdim // Any phi, if it is removed, may affect other phis (make them dead). 1539362593Sdim // For each removed phi, collect the potentially affected phis and add 1540362593Sdim // them back to the queue. 1541362593Sdim while (!PhiQ.empty()) { 1542362593Sdim auto PA = addr<PhiNode*>(PhiQ[0]); 1543362593Sdim PhiQ.remove(PA.Id); 1544362593Sdim NodeList Refs = PA.Addr->members(*this); 1545362593Sdim if (HasUsedDef(Refs)) 1546362593Sdim continue; 1547362593Sdim for (NodeAddr<RefNode*> RA : Refs) { 1548362593Sdim if (NodeId RD = RA.Addr->getReachingDef()) { 1549362593Sdim auto RDA = addr<DefNode*>(RD); 1550362593Sdim NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this); 1551362593Sdim if (IsPhi(OA)) 1552362593Sdim PhiQ.insert(OA.Id); 1553362593Sdim } 1554362593Sdim if (RA.Addr->isDef()) 1555362593Sdim unlinkDef(RA, true); 1556362593Sdim else 1557362593Sdim unlinkUse(RA, true); 1558362593Sdim } 1559362593Sdim NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this); 1560362593Sdim BA.Addr->removeMember(PA, *this); 1561362593Sdim } 1562362593Sdim} 1563362593Sdim 1564362593Sdim// For a given reference node TA in an instruction node IA, connect the 1565362593Sdim// reaching def of TA to the appropriate def node. Create any shadow nodes 1566362593Sdim// as appropriate. 1567362593Sdimtemplate <typename T> 1568362593Sdimvoid DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA, 1569362593Sdim DefStack &DS) { 1570362593Sdim if (DS.empty()) 1571362593Sdim return; 1572362593Sdim RegisterRef RR = TA.Addr->getRegRef(*this); 1573362593Sdim NodeAddr<T> TAP; 1574362593Sdim 1575362593Sdim // References from the def stack that have been examined so far. 1576362593Sdim RegisterAggr Defs(PRI); 1577362593Sdim 1578362593Sdim for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) { 1579362593Sdim RegisterRef QR = I->Addr->getRegRef(*this); 1580362593Sdim 1581362593Sdim // Skip all defs that are aliased to any of the defs that we have already 1582362593Sdim // seen. If this completes a cover of RR, stop the stack traversal. 1583362593Sdim bool Alias = Defs.hasAliasOf(QR); 1584362593Sdim bool Cover = Defs.insert(QR).hasCoverOf(RR); 1585362593Sdim if (Alias) { 1586362593Sdim if (Cover) 1587362593Sdim break; 1588362593Sdim continue; 1589362593Sdim } 1590362593Sdim 1591362593Sdim // The reaching def. 1592362593Sdim NodeAddr<DefNode*> RDA = *I; 1593362593Sdim 1594362593Sdim // Pick the reached node. 1595362593Sdim if (TAP.Id == 0) { 1596362593Sdim TAP = TA; 1597362593Sdim } else { 1598362593Sdim // Mark the existing ref as "shadow" and create a new shadow. 1599362593Sdim TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow); 1600362593Sdim TAP = getNextShadow(IA, TAP, true); 1601362593Sdim } 1602362593Sdim 1603362593Sdim // Create the link. 1604362593Sdim TAP.Addr->linkToDef(TAP.Id, RDA); 1605362593Sdim 1606362593Sdim if (Cover) 1607362593Sdim break; 1608362593Sdim } 1609362593Sdim} 1610362593Sdim 1611362593Sdim// Create data-flow links for all reference nodes in the statement node SA. 1612362593Sdimtemplate <typename Predicate> 1613362593Sdimvoid DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA, 1614362593Sdim Predicate P) { 1615362593Sdim#ifndef NDEBUG 1616362593Sdim RegisterSet Defs; 1617362593Sdim#endif 1618362593Sdim 1619362593Sdim // Link all nodes (upwards in the data-flow) with their reaching defs. 1620362593Sdim for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) { 1621362593Sdim uint16_t Kind = RA.Addr->getKind(); 1622362593Sdim assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use); 1623362593Sdim RegisterRef RR = RA.Addr->getRegRef(*this); 1624362593Sdim#ifndef NDEBUG 1625362593Sdim // Do not expect multiple defs of the same reference. 1626362593Sdim assert(Kind != NodeAttrs::Def || !Defs.count(RR)); 1627362593Sdim Defs.insert(RR); 1628362593Sdim#endif 1629362593Sdim 1630362593Sdim auto F = DefM.find(RR.Reg); 1631362593Sdim if (F == DefM.end()) 1632362593Sdim continue; 1633362593Sdim DefStack &DS = F->second; 1634362593Sdim if (Kind == NodeAttrs::Use) 1635362593Sdim linkRefUp<UseNode*>(SA, RA, DS); 1636362593Sdim else if (Kind == NodeAttrs::Def) 1637362593Sdim linkRefUp<DefNode*>(SA, RA, DS); 1638362593Sdim else 1639362593Sdim llvm_unreachable("Unexpected node in instruction"); 1640362593Sdim } 1641362593Sdim} 1642362593Sdim 1643362593Sdim// Create data-flow links for all instructions in the block node BA. This 1644362593Sdim// will include updating any phi nodes in BA. 1645362593Sdimvoid DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) { 1646362593Sdim // Push block delimiters. 1647362593Sdim markBlock(BA.Id, DefM); 1648362593Sdim 1649362593Sdim auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool { 1650362593Sdim return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering); 1651362593Sdim }; 1652362593Sdim auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool { 1653362593Sdim return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering); 1654362593Sdim }; 1655362593Sdim 1656362593Sdim assert(BA.Addr && "block node address is needed to create a data-flow link"); 1657362593Sdim // For each non-phi instruction in the block, link all the defs and uses 1658362593Sdim // to their reaching defs. For any member of the block (including phis), 1659362593Sdim // push the defs on the corresponding stacks. 1660362593Sdim for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) { 1661362593Sdim // Ignore phi nodes here. They will be linked part by part from the 1662362593Sdim // predecessors. 1663362593Sdim if (IA.Addr->getKind() == NodeAttrs::Stmt) { 1664362593Sdim linkStmtRefs(DefM, IA, IsUse); 1665362593Sdim linkStmtRefs(DefM, IA, IsClobber); 1666362593Sdim } 1667362593Sdim 1668362593Sdim // Push the definitions on the stack. 1669362593Sdim pushClobbers(IA, DefM); 1670362593Sdim 1671362593Sdim if (IA.Addr->getKind() == NodeAttrs::Stmt) 1672362593Sdim linkStmtRefs(DefM, IA, IsNoClobber); 1673362593Sdim 1674362593Sdim pushDefs(IA, DefM); 1675362593Sdim } 1676362593Sdim 1677362593Sdim // Recursively process all children in the dominator tree. 1678362593Sdim MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); 1679362593Sdim for (auto I : *N) { 1680362593Sdim MachineBasicBlock *SB = I->getBlock(); 1681362593Sdim NodeAddr<BlockNode*> SBA = findBlock(SB); 1682362593Sdim linkBlockRefs(DefM, SBA); 1683362593Sdim } 1684362593Sdim 1685362593Sdim // Link the phi uses from the successor blocks. 1686362593Sdim auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool { 1687362593Sdim if (NA.Addr->getKind() != NodeAttrs::Use) 1688362593Sdim return false; 1689362593Sdim assert(NA.Addr->getFlags() & NodeAttrs::PhiRef); 1690362593Sdim NodeAddr<PhiUseNode*> PUA = NA; 1691362593Sdim return PUA.Addr->getPredecessor() == BA.Id; 1692362593Sdim }; 1693362593Sdim 1694362593Sdim RegisterSet EHLiveIns = getLandingPadLiveIns(); 1695362593Sdim MachineBasicBlock *MBB = BA.Addr->getCode(); 1696362593Sdim 1697362593Sdim for (MachineBasicBlock *SB : MBB->successors()) { 1698362593Sdim bool IsEHPad = SB->isEHPad(); 1699362593Sdim NodeAddr<BlockNode*> SBA = findBlock(SB); 1700362593Sdim for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) { 1701362593Sdim // Do not link phi uses for landing pad live-ins. 1702362593Sdim if (IsEHPad) { 1703362593Sdim // Find what register this phi is for. 1704362593Sdim NodeAddr<RefNode*> RA = IA.Addr->getFirstMember(*this); 1705362593Sdim assert(RA.Id != 0); 1706362593Sdim if (EHLiveIns.count(RA.Addr->getRegRef(*this))) 1707362593Sdim continue; 1708362593Sdim } 1709362593Sdim // Go over each phi use associated with MBB, and link it. 1710362593Sdim for (auto U : IA.Addr->members_if(IsUseForBA, *this)) { 1711362593Sdim NodeAddr<PhiUseNode*> PUA = U; 1712362593Sdim RegisterRef RR = PUA.Addr->getRegRef(*this); 1713362593Sdim linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]); 1714362593Sdim } 1715362593Sdim } 1716362593Sdim } 1717362593Sdim 1718362593Sdim // Pop all defs from this block from the definition stacks. 1719362593Sdim releaseBlock(BA.Id, DefM); 1720362593Sdim} 1721362593Sdim 1722362593Sdim// Remove the use node UA from any data-flow and structural links. 1723362593Sdimvoid DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { 1724362593Sdim NodeId RD = UA.Addr->getReachingDef(); 1725362593Sdim NodeId Sib = UA.Addr->getSibling(); 1726362593Sdim 1727362593Sdim if (RD == 0) { 1728362593Sdim assert(Sib == 0); 1729362593Sdim return; 1730362593Sdim } 1731362593Sdim 1732362593Sdim auto RDA = addr<DefNode*>(RD); 1733362593Sdim auto TA = addr<UseNode*>(RDA.Addr->getReachedUse()); 1734362593Sdim if (TA.Id == UA.Id) { 1735362593Sdim RDA.Addr->setReachedUse(Sib); 1736362593Sdim return; 1737362593Sdim } 1738362593Sdim 1739362593Sdim while (TA.Id != 0) { 1740362593Sdim NodeId S = TA.Addr->getSibling(); 1741362593Sdim if (S == UA.Id) { 1742362593Sdim TA.Addr->setSibling(UA.Addr->getSibling()); 1743362593Sdim return; 1744362593Sdim } 1745362593Sdim TA = addr<UseNode*>(S); 1746362593Sdim } 1747362593Sdim} 1748362593Sdim 1749362593Sdim// Remove the def node DA from any data-flow and structural links. 1750362593Sdimvoid DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { 1751362593Sdim // 1752362593Sdim // RD 1753362593Sdim // | reached 1754362593Sdim // | def 1755362593Sdim // : 1756362593Sdim // . 1757362593Sdim // +----+ 1758362593Sdim // ... -- | DA | -- ... -- 0 : sibling chain of DA 1759362593Sdim // +----+ 1760362593Sdim // | | reached 1761362593Sdim // | : def 1762362593Sdim // | . 1763362593Sdim // | ... : Siblings (defs) 1764362593Sdim // | 1765362593Sdim // : reached 1766362593Sdim // . use 1767362593Sdim // ... : sibling chain of reached uses 1768362593Sdim 1769362593Sdim NodeId RD = DA.Addr->getReachingDef(); 1770362593Sdim 1771362593Sdim // Visit all siblings of the reached def and reset their reaching defs. 1772362593Sdim // Also, defs reached by DA are now "promoted" to being reached by RD, 1773362593Sdim // so all of them will need to be spliced into the sibling chain where 1774362593Sdim // DA belongs. 1775362593Sdim auto getAllNodes = [this] (NodeId N) -> NodeList { 1776362593Sdim NodeList Res; 1777362593Sdim while (N) { 1778362593Sdim auto RA = addr<RefNode*>(N); 1779362593Sdim // Keep the nodes in the exact sibling order. 1780362593Sdim Res.push_back(RA); 1781362593Sdim N = RA.Addr->getSibling(); 1782362593Sdim } 1783362593Sdim return Res; 1784362593Sdim }; 1785362593Sdim NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef()); 1786362593Sdim NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse()); 1787362593Sdim 1788362593Sdim if (RD == 0) { 1789362593Sdim for (NodeAddr<RefNode*> I : ReachedDefs) 1790362593Sdim I.Addr->setSibling(0); 1791362593Sdim for (NodeAddr<RefNode*> I : ReachedUses) 1792362593Sdim I.Addr->setSibling(0); 1793362593Sdim } 1794362593Sdim for (NodeAddr<DefNode*> I : ReachedDefs) 1795362593Sdim I.Addr->setReachingDef(RD); 1796362593Sdim for (NodeAddr<UseNode*> I : ReachedUses) 1797362593Sdim I.Addr->setReachingDef(RD); 1798362593Sdim 1799362593Sdim NodeId Sib = DA.Addr->getSibling(); 1800362593Sdim if (RD == 0) { 1801362593Sdim assert(Sib == 0); 1802362593Sdim return; 1803362593Sdim } 1804362593Sdim 1805362593Sdim // Update the reaching def node and remove DA from the sibling list. 1806362593Sdim auto RDA = addr<DefNode*>(RD); 1807362593Sdim auto TA = addr<DefNode*>(RDA.Addr->getReachedDef()); 1808362593Sdim if (TA.Id == DA.Id) { 1809362593Sdim // If DA is the first reached def, just update the RD's reached def 1810362593Sdim // to the DA's sibling. 1811362593Sdim RDA.Addr->setReachedDef(Sib); 1812362593Sdim } else { 1813362593Sdim // Otherwise, traverse the sibling list of the reached defs and remove 1814362593Sdim // DA from it. 1815362593Sdim while (TA.Id != 0) { 1816362593Sdim NodeId S = TA.Addr->getSibling(); 1817362593Sdim if (S == DA.Id) { 1818362593Sdim TA.Addr->setSibling(Sib); 1819362593Sdim break; 1820362593Sdim } 1821362593Sdim TA = addr<DefNode*>(S); 1822362593Sdim } 1823362593Sdim } 1824362593Sdim 1825362593Sdim // Splice the DA's reached defs into the RDA's reached def chain. 1826362593Sdim if (!ReachedDefs.empty()) { 1827362593Sdim auto Last = NodeAddr<DefNode*>(ReachedDefs.back()); 1828362593Sdim Last.Addr->setSibling(RDA.Addr->getReachedDef()); 1829362593Sdim RDA.Addr->setReachedDef(ReachedDefs.front().Id); 1830362593Sdim } 1831362593Sdim // Splice the DA's reached uses into the RDA's reached use chain. 1832362593Sdim if (!ReachedUses.empty()) { 1833362593Sdim auto Last = NodeAddr<UseNode*>(ReachedUses.back()); 1834362593Sdim Last.Addr->setSibling(RDA.Addr->getReachedUse()); 1835362593Sdim RDA.Addr->setReachedUse(ReachedUses.front().Id); 1836362593Sdim } 1837362593Sdim} 1838