1845 lines · cpp
1//===- RDFGraph.cpp -------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Target-independent, SSA-based data flow graph for register data flow (RDF).10//11#include "llvm/CodeGen/RDFGraph.h"12#include "llvm/ADT/BitVector.h"13#include "llvm/ADT/STLExtras.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/CodeGen/MachineBasicBlock.h"16#include "llvm/CodeGen/MachineDominanceFrontier.h"17#include "llvm/CodeGen/MachineDominators.h"18#include "llvm/CodeGen/MachineFunction.h"19#include "llvm/CodeGen/MachineInstr.h"20#include "llvm/CodeGen/MachineOperand.h"21#include "llvm/CodeGen/MachineRegisterInfo.h"22#include "llvm/CodeGen/RDFRegisters.h"23#include "llvm/CodeGen/TargetInstrInfo.h"24#include "llvm/CodeGen/TargetLowering.h"25#include "llvm/CodeGen/TargetRegisterInfo.h"26#include "llvm/CodeGen/TargetSubtargetInfo.h"27#include "llvm/IR/Function.h"28#include "llvm/MC/LaneBitmask.h"29#include "llvm/MC/MCInstrDesc.h"30#include "llvm/Support/ErrorHandling.h"31#include "llvm/Support/raw_ostream.h"32#include <cassert>33#include <cstdint>34#include <cstring>35#include <iterator>36#include <set>37#include <utility>38#include <vector>39 40// Printing functions. Have them here first, so that the rest of the code41// can use them.42namespace llvm::rdf {43 44raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P) {45 P.G.getPRI().print(OS, P.Obj);46 return OS;47}48 49raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P) {50 if (P.Obj == 0)51 return OS << "null";52 auto NA = P.G.addr<NodeBase *>(P.Obj);53 uint16_t Attrs = NA.Addr->getAttrs();54 uint16_t Kind = NodeAttrs::kind(Attrs);55 uint16_t Flags = NodeAttrs::flags(Attrs);56 switch (NodeAttrs::type(Attrs)) {57 case NodeAttrs::Code:58 switch (Kind) {59 case NodeAttrs::Func:60 OS << 'f';61 break;62 case NodeAttrs::Block:63 OS << 'b';64 break;65 case NodeAttrs::Stmt:66 OS << 's';67 break;68 case NodeAttrs::Phi:69 OS << 'p';70 break;71 default:72 OS << "c?";73 break;74 }75 break;76 case NodeAttrs::Ref:77 if (Flags & NodeAttrs::Undef)78 OS << '/';79 if (Flags & NodeAttrs::Dead)80 OS << '\\';81 if (Flags & NodeAttrs::Preserving)82 OS << '+';83 if (Flags & NodeAttrs::Clobbering)84 OS << '~';85 switch (Kind) {86 case NodeAttrs::Use:87 OS << 'u';88 break;89 case NodeAttrs::Def:90 OS << 'd';91 break;92 case NodeAttrs::Block:93 OS << 'b';94 break;95 default:96 OS << "r?";97 break;98 }99 break;100 default:101 OS << '?';102 break;103 }104 OS << P.Obj;105 if (Flags & NodeAttrs::Shadow)106 OS << '"';107 return OS;108}109 110static void printRefHeader(raw_ostream &OS, const Ref RA,111 const DataFlowGraph &G) {112 OS << Print(RA.Id, G) << '<' << Print(RA.Addr->getRegRef(G), G) << '>';113 if (RA.Addr->getFlags() & NodeAttrs::Fixed)114 OS << '!';115}116 117raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P) {118 printRefHeader(OS, P.Obj, P.G);119 OS << '(';120 if (NodeId N = P.Obj.Addr->getReachingDef())121 OS << Print(N, P.G);122 OS << ',';123 if (NodeId N = P.Obj.Addr->getReachedDef())124 OS << Print(N, P.G);125 OS << ',';126 if (NodeId N = P.Obj.Addr->getReachedUse())127 OS << Print(N, P.G);128 OS << "):";129 if (NodeId N = P.Obj.Addr->getSibling())130 OS << Print(N, P.G);131 return OS;132}133 134raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P) {135 printRefHeader(OS, P.Obj, P.G);136 OS << '(';137 if (NodeId N = P.Obj.Addr->getReachingDef())138 OS << Print(N, P.G);139 OS << "):";140 if (NodeId N = P.Obj.Addr->getSibling())141 OS << Print(N, P.G);142 return OS;143}144 145raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P) {146 printRefHeader(OS, P.Obj, P.G);147 OS << '(';148 if (NodeId N = P.Obj.Addr->getReachingDef())149 OS << Print(N, P.G);150 OS << ',';151 if (NodeId N = P.Obj.Addr->getPredecessor())152 OS << Print(N, P.G);153 OS << "):";154 if (NodeId N = P.Obj.Addr->getSibling())155 OS << Print(N, P.G);156 return OS;157}158 159raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &P) {160 switch (P.Obj.Addr->getKind()) {161 case NodeAttrs::Def:162 OS << PrintNode<DefNode *>(P.Obj, P.G);163 break;164 case NodeAttrs::Use:165 if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef)166 OS << PrintNode<PhiUseNode *>(P.Obj, P.G);167 else168 OS << PrintNode<UseNode *>(P.Obj, P.G);169 break;170 }171 return OS;172}173 174raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P) {175 unsigned N = P.Obj.size();176 for (auto I : P.Obj) {177 OS << Print(I.Id, P.G);178 if (--N)179 OS << ' ';180 }181 return OS;182}183 184raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P) {185 unsigned N = P.Obj.size();186 for (auto I : P.Obj) {187 OS << Print(I, P.G);188 if (--N)189 OS << ' ';190 }191 return OS;192}193 194namespace {195 196template <typename T> struct PrintListV {197 PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {}198 199 using Type = T;200 const NodeList &List;201 const DataFlowGraph &G;202};203 204template <typename T>205raw_ostream &operator<<(raw_ostream &OS, const PrintListV<T> &P) {206 unsigned N = P.List.size();207 for (NodeAddr<T> A : P.List) {208 OS << PrintNode<T>(A, P.G);209 if (--N)210 OS << ", ";211 }212 return OS;213}214 215} // end anonymous namespace216 217raw_ostream &operator<<(raw_ostream &OS, const Print<Phi> &P) {218 OS << Print(P.Obj.Id, P.G) << ": phi ["219 << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']';220 return OS;221}222 223raw_ostream &operator<<(raw_ostream &OS, const Print<Stmt> &P) {224 const MachineInstr &MI = *P.Obj.Addr->getCode();225 unsigned Opc = MI.getOpcode();226 OS << Print(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc);227 // Print the target for calls and branches (for readability).228 if (MI.isCall() || MI.isBranch()) {229 MachineInstr::const_mop_iterator T =230 llvm::find_if(MI.operands(), [](const MachineOperand &Op) -> bool {231 return Op.isMBB() || Op.isGlobal() || Op.isSymbol();232 });233 if (T != MI.operands_end()) {234 OS << ' ';235 if (T->isMBB())236 OS << printMBBReference(*T->getMBB());237 else if (T->isGlobal())238 OS << T->getGlobal()->getName();239 else if (T->isSymbol())240 OS << T->getSymbolName();241 }242 }243 OS << " [" << PrintListV<RefNode *>(P.Obj.Addr->members(P.G), P.G) << ']';244 return OS;245}246 247raw_ostream &operator<<(raw_ostream &OS, const Print<Instr> &P) {248 switch (P.Obj.Addr->getKind()) {249 case NodeAttrs::Phi:250 OS << PrintNode<PhiNode *>(P.Obj, P.G);251 break;252 case NodeAttrs::Stmt:253 OS << PrintNode<StmtNode *>(P.Obj, P.G);254 break;255 default:256 OS << "instr? " << Print(P.Obj.Id, P.G);257 break;258 }259 return OS;260}261 262raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &P) {263 MachineBasicBlock *BB = P.Obj.Addr->getCode();264 unsigned NP = BB->pred_size();265 std::vector<int> Ns;266 auto PrintBBs = [&OS](const std::vector<int> &Ns) -> void {267 unsigned N = Ns.size();268 for (int I : Ns) {269 OS << "%bb." << I;270 if (--N)271 OS << ", ";272 }273 };274 275 OS << Print(P.Obj.Id, P.G) << ": --- " << printMBBReference(*BB)276 << " --- preds(" << NP << "): ";277 for (MachineBasicBlock *B : BB->predecessors())278 Ns.push_back(B->getNumber());279 PrintBBs(Ns);280 281 unsigned NS = BB->succ_size();282 OS << " succs(" << NS << "): ";283 Ns.clear();284 for (MachineBasicBlock *B : BB->successors())285 Ns.push_back(B->getNumber());286 PrintBBs(Ns);287 OS << '\n';288 289 for (auto I : P.Obj.Addr->members(P.G))290 OS << PrintNode<InstrNode *>(I, P.G) << '\n';291 return OS;292}293 294raw_ostream &operator<<(raw_ostream &OS, const Print<Func> &P) {295 OS << "DFG dump:[\n"296 << Print(P.Obj.Id, P.G)297 << ": Function: " << P.Obj.Addr->getCode()->getName() << '\n';298 for (auto I : P.Obj.Addr->members(P.G))299 OS << PrintNode<BlockNode *>(I, P.G) << '\n';300 OS << "]\n";301 return OS;302}303 304raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P) {305 OS << '{';306 for (auto I : P.Obj)307 OS << ' ' << Print(I, P.G);308 OS << " }";309 return OS;310}311 312raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P) {313 OS << P.Obj;314 return OS;315}316 317raw_ostream &operator<<(raw_ostream &OS,318 const Print<DataFlowGraph::DefStack> &P) {319 for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E;) {320 OS << Print(I->Id, P.G) << '<' << Print(I->Addr->getRegRef(P.G), P.G)321 << '>';322 I.down();323 if (I != E)324 OS << ' ';325 }326 return OS;327}328 329// Node allocation functions.330//331// Node allocator is like a slab memory allocator: it allocates blocks of332// memory in sizes that are multiples of the size of a node. Each block has333// the same size. Nodes are allocated from the currently active block, and334// when it becomes full, a new one is created.335// There is a mapping scheme between node id and its location in a block,336// and within that block is described in the header file.337//338void NodeAllocator::startNewBlock() {339 void *T = MemPool.Allocate(NodesPerBlock * NodeMemSize, NodeMemSize);340 char *P = static_cast<char *>(T);341 Blocks.push_back(P);342 // Check if the block index is still within the allowed range, i.e. less343 // than 2^N, where N is the number of bits in NodeId for the block index.344 // BitsPerIndex is the number of bits per node index.345 assert((Blocks.size() < ((size_t)1 << (8 * sizeof(NodeId) - BitsPerIndex))) &&346 "Out of bits for block index");347 ActiveEnd = P;348}349 350bool NodeAllocator::needNewBlock() {351 if (Blocks.empty())352 return true;353 354 char *ActiveBegin = Blocks.back();355 uint32_t Index = (ActiveEnd - ActiveBegin) / NodeMemSize;356 return Index >= NodesPerBlock;357}358 359Node NodeAllocator::New() {360 if (needNewBlock())361 startNewBlock();362 363 uint32_t ActiveB = Blocks.size() - 1;364 uint32_t Index = (ActiveEnd - Blocks[ActiveB]) / NodeMemSize;365 Node NA = {reinterpret_cast<NodeBase *>(ActiveEnd), makeId(ActiveB, Index)};366 ActiveEnd += NodeMemSize;367 return NA;368}369 370NodeId NodeAllocator::id(const NodeBase *P) const {371 uintptr_t A = reinterpret_cast<uintptr_t>(P);372 for (unsigned i = 0, n = Blocks.size(); i != n; ++i) {373 uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]);374 if (A < B || A >= B + NodesPerBlock * NodeMemSize)375 continue;376 uint32_t Idx = (A - B) / NodeMemSize;377 return makeId(i, Idx);378 }379 llvm_unreachable("Invalid node address");380}381 382void NodeAllocator::clear() {383 MemPool.Reset();384 Blocks.clear();385 ActiveEnd = nullptr;386}387 388// Insert node NA after "this" in the circular chain.389void NodeBase::append(Node NA) {390 NodeId Nx = Next;391 // If NA is already "next", do nothing.392 if (Next != NA.Id) {393 Next = NA.Id;394 NA.Addr->Next = Nx;395 }396}397 398// Fundamental node manipulator functions.399 400// Obtain the register reference from a reference node.401RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const {402 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);403 if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)404 return G.unpack(RefData.PR);405 assert(RefData.Op != nullptr);406 return G.makeRegRef(*RefData.Op);407}408 409// Set the register reference in the reference node directly (for references410// in phi nodes).411void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) {412 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);413 assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef);414 RefData.PR = G.pack(RR);415}416 417// Set the register reference in the reference node based on a machine418// operand (for references in statement nodes).419void RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) {420 assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref);421 assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef));422 (void)G;423 RefData.Op = Op;424}425 426// Get the owner of a given reference node.427Node RefNode::getOwner(const DataFlowGraph &G) {428 Node NA = G.addr<NodeBase *>(getNext());429 430 while (NA.Addr != this) {431 if (NA.Addr->getType() == NodeAttrs::Code)432 return NA;433 NA = G.addr<NodeBase *>(NA.Addr->getNext());434 }435 llvm_unreachable("No owner in circular list");436}437 438// Connect the def node to the reaching def node.439void DefNode::linkToDef(NodeId Self, Def DA) {440 RefData.RD = DA.Id;441 RefData.Sib = DA.Addr->getReachedDef();442 DA.Addr->setReachedDef(Self);443}444 445// Connect the use node to the reaching def node.446void UseNode::linkToDef(NodeId Self, Def DA) {447 RefData.RD = DA.Id;448 RefData.Sib = DA.Addr->getReachedUse();449 DA.Addr->setReachedUse(Self);450}451 452// Get the first member of the code node.453Node CodeNode::getFirstMember(const DataFlowGraph &G) const {454 if (CodeData.FirstM == 0)455 return Node();456 return G.addr<NodeBase *>(CodeData.FirstM);457}458 459// Get the last member of the code node.460Node CodeNode::getLastMember(const DataFlowGraph &G) const {461 if (CodeData.LastM == 0)462 return Node();463 return G.addr<NodeBase *>(CodeData.LastM);464}465 466// Add node NA at the end of the member list of the given code node.467void CodeNode::addMember(Node NA, const DataFlowGraph &G) {468 Node ML = getLastMember(G);469 if (ML.Id != 0) {470 ML.Addr->append(NA);471 } else {472 CodeData.FirstM = NA.Id;473 NodeId Self = G.id(this);474 NA.Addr->setNext(Self);475 }476 CodeData.LastM = NA.Id;477}478 479// Add node NA after member node MA in the given code node.480void CodeNode::addMemberAfter(Node MA, Node NA, const DataFlowGraph &G) {481 MA.Addr->append(NA);482 if (CodeData.LastM == MA.Id)483 CodeData.LastM = NA.Id;484}485 486// Remove member node NA from the given code node.487void CodeNode::removeMember(Node NA, const DataFlowGraph &G) {488 Node MA = getFirstMember(G);489 assert(MA.Id != 0);490 491 // Special handling if the member to remove is the first member.492 if (MA.Id == NA.Id) {493 if (CodeData.LastM == MA.Id) {494 // If it is the only member, set both first and last to 0.495 CodeData.FirstM = CodeData.LastM = 0;496 } else {497 // Otherwise, advance the first member.498 CodeData.FirstM = MA.Addr->getNext();499 }500 return;501 }502 503 while (MA.Addr != this) {504 NodeId MX = MA.Addr->getNext();505 if (MX == NA.Id) {506 MA.Addr->setNext(NA.Addr->getNext());507 // If the member to remove happens to be the last one, update the508 // LastM indicator.509 if (CodeData.LastM == NA.Id)510 CodeData.LastM = MA.Id;511 return;512 }513 MA = G.addr<NodeBase *>(MX);514 }515 llvm_unreachable("No such member");516}517 518// Return the list of all members of the code node.519NodeList CodeNode::members(const DataFlowGraph &G) const {520 static auto True = [](Node) -> bool { return true; };521 return members_if(True, G);522}523 524// Return the owner of the given instr node.525Node InstrNode::getOwner(const DataFlowGraph &G) {526 Node NA = G.addr<NodeBase *>(getNext());527 528 while (NA.Addr != this) {529 assert(NA.Addr->getType() == NodeAttrs::Code);530 if (NA.Addr->getKind() == NodeAttrs::Block)531 return NA;532 NA = G.addr<NodeBase *>(NA.Addr->getNext());533 }534 llvm_unreachable("No owner in circular list");535}536 537// Add the phi node PA to the given block node.538void BlockNode::addPhi(Phi PA, const DataFlowGraph &G) {539 Node M = getFirstMember(G);540 if (M.Id == 0) {541 addMember(PA, G);542 return;543 }544 545 assert(M.Addr->getType() == NodeAttrs::Code);546 if (M.Addr->getKind() == NodeAttrs::Stmt) {547 // If the first member of the block is a statement, insert the phi as548 // the first member.549 CodeData.FirstM = PA.Id;550 PA.Addr->setNext(M.Id);551 } else {552 // If the first member is a phi, find the last phi, and append PA to it.553 assert(M.Addr->getKind() == NodeAttrs::Phi);554 Node MN = M;555 do {556 M = MN;557 MN = G.addr<NodeBase *>(M.Addr->getNext());558 assert(MN.Addr->getType() == NodeAttrs::Code);559 } while (MN.Addr->getKind() == NodeAttrs::Phi);560 561 // M is the last phi.562 addMemberAfter(M, PA, G);563 }564}565 566// Find the block node corresponding to the machine basic block BB in the567// given func node.568Block FuncNode::findBlock(const MachineBasicBlock *BB,569 const DataFlowGraph &G) const {570 auto EqBB = [BB](Node NA) -> bool { return Block(NA).Addr->getCode() == BB; };571 NodeList Ms = members_if(EqBB, G);572 if (!Ms.empty())573 return Ms[0];574 return Block();575}576 577// Get the block node for the entry block in the given function.578Block FuncNode::getEntryBlock(const DataFlowGraph &G) {579 MachineBasicBlock *EntryB = &getCode()->front();580 return findBlock(EntryB, G);581}582 583// Target operand information.584//585 586// For a given instruction, check if there are any bits of RR that can remain587// unchanged across this def.588bool TargetOperandInfo::isPreserving(const MachineInstr &In,589 unsigned OpNum) const {590 return TII.isPredicated(In);591}592 593// Check if the definition of RR produces an unspecified value.594bool TargetOperandInfo::isClobbering(const MachineInstr &In,595 unsigned OpNum) const {596 const MachineOperand &Op = In.getOperand(OpNum);597 if (Op.isRegMask())598 return true;599 assert(Op.isReg());600 if (In.isCall())601 if (Op.isDef() && Op.isDead())602 return true;603 return false;604}605 606// Check if the given instruction specifically requires607bool TargetOperandInfo::isFixedReg(const MachineInstr &In,608 unsigned OpNum) const {609 if (In.isCall() || In.isReturn() || In.isInlineAsm())610 return true;611 // Check for a tail call.612 if (In.isBranch())613 for (const MachineOperand &O : In.operands())614 if (O.isGlobal() || O.isSymbol())615 return true;616 617 const MCInstrDesc &D = In.getDesc();618 if (D.implicit_defs().empty() && D.implicit_uses().empty())619 return false;620 const MachineOperand &Op = In.getOperand(OpNum);621 // If there is a sub-register, treat the operand as non-fixed. Currently,622 // fixed registers are those that are listed in the descriptor as implicit623 // uses or defs, and those lists do not allow sub-registers.624 if (Op.getSubReg() != 0)625 return false;626 Register Reg = Op.getReg();627 ArrayRef<MCPhysReg> ImpOps =628 Op.isDef() ? D.implicit_defs() : D.implicit_uses();629 return is_contained(ImpOps, Reg);630}631 632//633// The data flow graph construction.634//635 636DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,637 const TargetRegisterInfo &tri,638 const MachineDominatorTree &mdt,639 const MachineDominanceFrontier &mdf)640 : DefaultTOI(std::make_unique<TargetOperandInfo>(tii)), MF(mf), TII(tii),641 TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(*DefaultTOI),642 LiveIns(PRI) {}643 644DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,645 const TargetRegisterInfo &tri,646 const MachineDominatorTree &mdt,647 const MachineDominanceFrontier &mdf,648 const TargetOperandInfo &toi)649 : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi),650 LiveIns(PRI) {}651 652// The implementation of the definition stack.653// Each register reference has its own definition stack. In particular,654// for a register references "Reg" and "Reg:subreg" will each have their655// own definition stacks.656 657// Construct a stack iterator.658DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S,659 bool Top)660 : DS(S) {661 if (!Top) {662 // Initialize to bottom.663 Pos = 0;664 return;665 }666 // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty).667 Pos = DS.Stack.size();668 while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos - 1]))669 Pos--;670}671 672// Return the size of the stack, including block delimiters.673unsigned DataFlowGraph::DefStack::size() const {674 unsigned S = 0;675 for (auto I = top(), E = bottom(); I != E; I.down())676 S++;677 return S;678}679 680// Remove the top entry from the stack. Remove all intervening delimiters681// so that after this, the stack is either empty, or the top of the stack682// is a non-delimiter.683void DataFlowGraph::DefStack::pop() {684 assert(!empty());685 unsigned P = nextDown(Stack.size());686 Stack.resize(P);687}688 689// Push a delimiter for block node N on the stack.690void DataFlowGraph::DefStack::start_block(NodeId N) {691 assert(N != 0);692 Stack.push_back(Def(nullptr, N));693}694 695// Remove all nodes from the top of the stack, until the delimited for696// block node N is encountered. Remove the delimiter as well. In effect,697// this will remove from the stack all definitions from block N.698void DataFlowGraph::DefStack::clear_block(NodeId N) {699 assert(N != 0);700 unsigned P = Stack.size();701 while (P > 0) {702 bool Found = isDelimiter(Stack[P - 1], N);703 P--;704 if (Found)705 break;706 }707 // This will also remove the delimiter, if found.708 Stack.resize(P);709}710 711// Move the stack iterator up by one.712unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const {713 // Get the next valid position after P (skipping all delimiters).714 // The input position P does not have to point to a non-delimiter.715 unsigned SS = Stack.size();716 bool IsDelim;717 assert(P < SS);718 do {719 P++;720 IsDelim = isDelimiter(Stack[P - 1]);721 } while (P < SS && IsDelim);722 assert(!IsDelim);723 return P;724}725 726// Move the stack iterator down by one.727unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const {728 // Get the preceding valid position before P (skipping all delimiters).729 // The input position P does not have to point to a non-delimiter.730 assert(P > 0 && P <= Stack.size());731 bool IsDelim = isDelimiter(Stack[P - 1]);732 do {733 if (--P == 0)734 break;735 IsDelim = isDelimiter(Stack[P - 1]);736 } while (P > 0 && IsDelim);737 assert(!IsDelim);738 return P;739}740 741// Register information.742 743RegisterAggr DataFlowGraph::getLandingPadLiveIns() const {744 RegisterAggr LR(getPRI());745 const Function &F = MF.getFunction();746 const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() : nullptr;747 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();748 if (RegisterId R = TLI.getExceptionPointerRegister(PF))749 LR.insert(RegisterRef(R));750 if (!isFuncletEHPersonality(classifyEHPersonality(PF))) {751 if (RegisterId R = TLI.getExceptionSelectorRegister(PF))752 LR.insert(RegisterRef(R));753 }754 return LR;755}756 757// Node management functions.758 759// Get the pointer to the node with the id N.760NodeBase *DataFlowGraph::ptr(NodeId N) const {761 if (N == 0)762 return nullptr;763 return Memory.ptr(N);764}765 766// Get the id of the node at the address P.767NodeId DataFlowGraph::id(const NodeBase *P) const {768 if (P == nullptr)769 return 0;770 return Memory.id(P);771}772 773// Allocate a new node and set the attributes to Attrs.774Node DataFlowGraph::newNode(uint16_t Attrs) {775 Node P = Memory.New();776 P.Addr->init();777 P.Addr->setAttrs(Attrs);778 return P;779}780 781// Make a copy of the given node B, except for the data-flow links, which782// are set to 0.783Node DataFlowGraph::cloneNode(const Node B) {784 Node NA = newNode(0);785 memcpy(NA.Addr, B.Addr, sizeof(NodeBase));786 // Ref nodes need to have the data-flow links reset.787 if (NA.Addr->getType() == NodeAttrs::Ref) {788 Ref RA = NA;789 RA.Addr->setReachingDef(0);790 RA.Addr->setSibling(0);791 if (NA.Addr->getKind() == NodeAttrs::Def) {792 Def DA = NA;793 DA.Addr->setReachedDef(0);794 DA.Addr->setReachedUse(0);795 }796 }797 return NA;798}799 800// Allocation routines for specific node types/kinds.801 802Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) {803 Use UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);804 UA.Addr->setRegRef(&Op, *this);805 return UA;806}807 808PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,809 uint16_t Flags) {810 PhiUse PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags);811 assert(Flags & NodeAttrs::PhiRef);812 PUA.Addr->setRegRef(RR, *this);813 PUA.Addr->setPredecessor(PredB.Id);814 return PUA;815}816 817Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) {818 Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);819 DA.Addr->setRegRef(&Op, *this);820 return DA;821}822 823Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) {824 Def DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags);825 assert(Flags & NodeAttrs::PhiRef);826 DA.Addr->setRegRef(RR, *this);827 return DA;828}829 830Phi DataFlowGraph::newPhi(Block Owner) {831 Phi PA = newNode(NodeAttrs::Code | NodeAttrs::Phi);832 Owner.Addr->addPhi(PA, *this);833 return PA;834}835 836Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) {837 Stmt SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt);838 SA.Addr->setCode(MI);839 Owner.Addr->addMember(SA, *this);840 return SA;841}842 843Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) {844 Block BA = newNode(NodeAttrs::Code | NodeAttrs::Block);845 BA.Addr->setCode(BB);846 Owner.Addr->addMember(BA, *this);847 return BA;848}849 850Func DataFlowGraph::newFunc(MachineFunction *MF) {851 Func FA = newNode(NodeAttrs::Code | NodeAttrs::Func);852 FA.Addr->setCode(MF);853 return FA;854}855 856// Build the data flow graph.857void DataFlowGraph::build(const Config &config) {858 reset();859 BuildCfg = config;860 MachineRegisterInfo &MRI = MF.getRegInfo();861 ReservedRegs = MRI.getReservedRegs();862 bool SkipReserved = BuildCfg.Options & BuildOptions::OmitReserved;863 864 auto Insert = [](auto &Set, auto &&Range) {865 Set.insert(Range.begin(), Range.end());866 };867 868 if (BuildCfg.TrackRegs.empty()) {869 std::set<RegisterId> BaseSet;870 if (BuildCfg.Classes.empty()) {871 // Insert every register.872 for (unsigned R = 1, E = getPRI().getTRI().getNumRegs(); R != E; ++R)873 BaseSet.insert(R);874 } else {875 for (const TargetRegisterClass *RC : BuildCfg.Classes) {876 for (MCPhysReg R : *RC)877 BaseSet.insert(R);878 }879 }880 for (RegisterId R : BaseSet) {881 if (SkipReserved && ReservedRegs[R])882 continue;883 Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));884 }885 } else {886 // Track set in Config overrides everything.887 for (unsigned R : BuildCfg.TrackRegs) {888 if (SkipReserved && ReservedRegs[R])889 continue;890 Insert(TrackedUnits, getPRI().getUnits(RegisterRef(R)));891 }892 }893 894 TheFunc = newFunc(&MF);895 896 if (MF.empty())897 return;898 899 for (MachineBasicBlock &B : MF) {900 Block BA = newBlock(TheFunc, &B);901 BlockNodes.insert(std::make_pair(&B, BA));902 for (MachineInstr &I : B) {903 if (I.isDebugInstr())904 continue;905 buildStmt(BA, I);906 }907 }908 909 Block EA = TheFunc.Addr->getEntryBlock(*this);910 NodeList Blocks = TheFunc.Addr->members(*this);911 912 // Collect function live-ins and entry block live-ins.913 MachineBasicBlock &EntryB = *EA.Addr->getCode();914 assert(EntryB.pred_empty() && "Function entry block has predecessors");915 for (std::pair<MCRegister, Register> P : MRI.liveins())916 LiveIns.insert(RegisterRef(P.first));917 if (MRI.tracksLiveness()) {918 for (auto I : EntryB.liveins())919 LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask));920 }921 922 // Add function-entry phi nodes for the live-in registers.923 for (RegisterRef RR : LiveIns.refs()) {924 if (RR.isReg() && !isTracked(RR)) // isReg is likely guaranteed925 continue;926 Phi PA = newPhi(EA);927 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;928 Def DA = newDef(PA, RR, PhiFlags);929 PA.Addr->addMember(DA, *this);930 }931 932 // Add phis for landing pads.933 // Landing pads, unlike usual backs blocks, are not entered through934 // branches in the program, or fall-throughs from other blocks. They935 // are entered from the exception handling runtime and target's ABI936 // may define certain registers as defined on entry to such a block.937 RegisterAggr EHRegs = getLandingPadLiveIns();938 if (!EHRegs.empty()) {939 for (Block BA : Blocks) {940 const MachineBasicBlock &B = *BA.Addr->getCode();941 if (!B.isEHPad())942 continue;943 944 // Prepare a list of NodeIds of the block's predecessors.945 NodeList Preds;946 for (MachineBasicBlock *PB : B.predecessors())947 Preds.push_back(findBlock(PB));948 949 // Build phi nodes for each live-in.950 for (RegisterRef RR : EHRegs.refs()) {951 if (RR.isReg() && !isTracked(RR))952 continue;953 Phi PA = newPhi(BA);954 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;955 // Add def:956 Def DA = newDef(PA, RR, PhiFlags);957 PA.Addr->addMember(DA, *this);958 // Add uses (no reaching defs for phi uses):959 for (Block PBA : Preds) {960 PhiUse PUA = newPhiUse(PA, RR, PBA);961 PA.Addr->addMember(PUA, *this);962 }963 }964 }965 }966 967 // Build a map "PhiM" which will contain, for each block, the set968 // of references that will require phi definitions in that block.969 // "PhiClobberM" map contains references that require phis for clobbering defs970 BlockRefsMap PhiM(getPRI());971 BlockRefsMap PhiClobberM(getPRI());972 for (Block BA : Blocks)973 recordDefsForDF(PhiM, PhiClobberM, BA);974 for (Block BA : Blocks)975 buildPhis(PhiM, BA);976 977 // Link all the refs. This will recursively traverse the dominator tree.978 // Phis for clobbering defs are added here.979 DefStackMap DM;980 linkBlockRefs(DM, PhiClobberM, EA);981 982 // Finally, remove all unused phi nodes.983 if (!(BuildCfg.Options & BuildOptions::KeepDeadPhis))984 removeUnusedPhis();985}986 987RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {988 assert(RegisterRef::isRegId(Reg) || RegisterRef::isMaskId(Reg));989 assert(Reg != 0);990 if (Sub != 0)991 Reg = TRI.getSubReg(Reg, Sub);992 return RegisterRef(Reg);993}994 995RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const {996 assert(Op.isReg() || Op.isRegMask());997 if (Op.isReg())998 return makeRegRef(Op.getReg(), Op.getSubReg());999 return RegisterRef(getPRI().getRegMaskId(Op.getRegMask()),1000 LaneBitmask::getAll());1001}1002 1003// For each stack in the map DefM, push the delimiter for block B on it.1004void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) {1005 // Push block delimiters.1006 for (auto &P : DefM)1007 P.second.start_block(B);1008}1009 1010// Remove all definitions coming from block B from each stack in DefM.1011void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) {1012 // Pop all defs from this block from the definition stack. Defs that were1013 // added to the map during the traversal of instructions will not have a1014 // delimiter, but for those, the whole stack will be emptied.1015 for (auto &P : DefM)1016 P.second.clear_block(B);1017 1018 // Finally, remove empty stacks from the map.1019 for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {1020 NextI = std::next(I);1021 // This preserves the validity of iterators other than I.1022 if (I->second.empty())1023 DefM.erase(I);1024 }1025}1026 1027// Push all definitions from the instruction node IA to an appropriate1028// stack in DefM.1029void DataFlowGraph::pushAllDefs(Instr IA, DefStackMap &DefM) {1030 pushClobbers(IA, DefM);1031 pushDefs(IA, DefM);1032}1033 1034// Push all definitions from the instruction node IA to an appropriate1035// stack in DefM.1036void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) {1037 NodeSet Visited;1038 std::set<RegisterId> Defined;1039 1040 // The important objectives of this function are:1041 // - to be able to handle instructions both while the graph is being1042 // constructed, and after the graph has been constructed, and1043 // - maintain proper ordering of definitions on the stack for each1044 // register reference:1045 // - if there are two or more related defs in IA (i.e. coming from1046 // the same machine operand), then only push one def on the stack,1047 // - if there are multiple unrelated defs of non-overlapping1048 // subregisters of S, then the stack for S will have both (in an1049 // unspecified order), but the order does not matter from the data-1050 // -flow perspective.1051 1052 for (Def DA : IA.Addr->members_if(IsDef, *this)) {1053 if (Visited.count(DA.Id))1054 continue;1055 if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))1056 continue;1057 1058 NodeList Rel = getRelatedRefs(IA, DA);1059 Def PDA = Rel.front();1060 RegisterRef RR = PDA.Addr->getRegRef(*this);1061 1062 // Push the definition on the stack for the register and all aliases.1063 // The def stack traversal in linkNodeUp will check the exact aliasing.1064 DefM[RR.Id].push(DA);1065 Defined.insert(RR.Id);1066 for (RegisterId A : getPRI().getAliasSet(RR)) {1067 if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A)))1068 continue;1069 // Check that we don't push the same def twice.1070 assert(A != RR.Id);1071 if (!Defined.count(A))1072 DefM[A].push(DA);1073 }1074 // Mark all the related defs as visited.1075 for (Node T : Rel)1076 Visited.insert(T.Id);1077 }1078}1079 1080// Push all definitions from the instruction node IA to an appropriate1081// stack in DefM.1082void DataFlowGraph::pushDefs(Instr IA, DefStackMap &DefM) {1083 NodeSet Visited;1084#ifndef NDEBUG1085 std::set<RegisterId> Defined;1086#endif1087 1088 // The important objectives of this function are:1089 // - to be able to handle instructions both while the graph is being1090 // constructed, and after the graph has been constructed, and1091 // - maintain proper ordering of definitions on the stack for each1092 // register reference:1093 // - if there are two or more related defs in IA (i.e. coming from1094 // the same machine operand), then only push one def on the stack,1095 // - if there are multiple unrelated defs of non-overlapping1096 // subregisters of S, then the stack for S will have both (in an1097 // unspecified order), but the order does not matter from the data-1098 // -flow perspective.1099 1100 for (Def DA : IA.Addr->members_if(IsDef, *this)) {1101 if (Visited.count(DA.Id))1102 continue;1103 if (DA.Addr->getFlags() & NodeAttrs::Clobbering)1104 continue;1105 1106 NodeList Rel = getRelatedRefs(IA, DA);1107 Def PDA = Rel.front();1108 RegisterRef RR = PDA.Addr->getRegRef(*this);1109#ifndef NDEBUG1110 // Assert if the register is defined in two or more unrelated defs.1111 // This could happen if there are two or more def operands defining it.1112 if (!Defined.insert(RR.Id).second) {1113 MachineInstr *MI = Stmt(IA).Addr->getCode();1114 dbgs() << "Multiple definitions of register: " << Print(RR, *this)1115 << " in\n " << *MI << "in " << printMBBReference(*MI->getParent())1116 << '\n';1117 llvm_unreachable(nullptr);1118 }1119#endif1120 // Push the definition on the stack for the register and all aliases.1121 // The def stack traversal in linkNodeUp will check the exact aliasing.1122 DefM[RR.Id].push(DA);1123 for (RegisterId A : getPRI().getAliasSet(RR)) {1124 if (RegisterRef::isRegId(A) && !isTracked(RegisterRef(A)))1125 continue;1126 // Check that we don't push the same def twice.1127 assert(A != RR.Id);1128 DefM[A].push(DA);1129 }1130 // Mark all the related defs as visited.1131 for (Node T : Rel)1132 Visited.insert(T.Id);1133 }1134}1135 1136// Return the list of all reference nodes related to RA, including RA itself.1137// See "getNextRelated" for the meaning of a "related reference".1138NodeList DataFlowGraph::getRelatedRefs(Instr IA, Ref RA) const {1139 assert(IA.Id != 0 && RA.Id != 0);1140 1141 NodeList Refs;1142 NodeId Start = RA.Id;1143 do {1144 Refs.push_back(RA);1145 RA = getNextRelated(IA, RA);1146 } while (RA.Id != 0 && RA.Id != Start);1147 return Refs;1148}1149 1150// Clear all information in the graph.1151void DataFlowGraph::reset() {1152 Memory.clear();1153 BlockNodes.clear();1154 TrackedUnits.clear();1155 ReservedRegs.clear();1156 TheFunc = Func();1157}1158 1159// Return the next reference node in the instruction node IA that is related1160// to RA. Conceptually, two reference nodes are related if they refer to the1161// same instance of a register access, but differ in flags or other minor1162// characteristics. Specific examples of related nodes are shadow reference1163// nodes.1164// Return the equivalent of nullptr if there are no more related references.1165Ref DataFlowGraph::getNextRelated(Instr IA, Ref RA) const {1166 assert(IA.Id != 0 && RA.Id != 0);1167 1168 auto IsRelated = [this, RA](Ref TA) -> bool {1169 if (TA.Addr->getKind() != RA.Addr->getKind())1170 return false;1171 if (!getPRI().equal_to(TA.Addr->getRegRef(*this),1172 RA.Addr->getRegRef(*this))) {1173 return false;1174 }1175 return true;1176 };1177 1178 RegisterRef RR = RA.Addr->getRegRef(*this);1179 if (IA.Addr->getKind() == NodeAttrs::Stmt) {1180 auto Cond = [&IsRelated, RA](Ref TA) -> bool {1181 return IsRelated(TA) && &RA.Addr->getOp() == &TA.Addr->getOp();1182 };1183 return RA.Addr->getNextRef(RR, Cond, true, *this);1184 }1185 1186 assert(IA.Addr->getKind() == NodeAttrs::Phi);1187 auto Cond = [&IsRelated, RA](Ref TA) -> bool {1188 if (!IsRelated(TA))1189 return false;1190 if (TA.Addr->getKind() != NodeAttrs::Use)1191 return true;1192 // For phi uses, compare predecessor blocks.1193 return PhiUse(TA).Addr->getPredecessor() ==1194 PhiUse(RA).Addr->getPredecessor();1195 };1196 return RA.Addr->getNextRef(RR, Cond, true, *this);1197}1198 1199// Find the next node related to RA in IA that satisfies condition P.1200// If such a node was found, return a pair where the second element is the1201// located node. If such a node does not exist, return a pair where the1202// first element is the element after which such a node should be inserted,1203// and the second element is a null-address.1204template <typename Predicate>1205std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA,1206 Predicate P) const {1207 assert(IA.Id != 0 && RA.Id != 0);1208 1209 Ref NA;1210 NodeId Start = RA.Id;1211 while (true) {1212 NA = getNextRelated(IA, RA);1213 if (NA.Id == 0 || NA.Id == Start)1214 break;1215 if (P(NA))1216 break;1217 RA = NA;1218 }1219 1220 if (NA.Id != 0 && NA.Id != Start)1221 return std::make_pair(RA, NA);1222 return std::make_pair(RA, Ref());1223}1224 1225// Get the next shadow node in IA corresponding to RA, and optionally create1226// such a node if it does not exist.1227Ref DataFlowGraph::getNextShadow(Instr IA, Ref RA, bool Create) {1228 assert(IA.Id != 0 && RA.Id != 0);1229 1230 uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;1231 auto IsShadow = [Flags](Ref TA) -> bool {1232 return TA.Addr->getFlags() == Flags;1233 };1234 auto Loc = locateNextRef(IA, RA, IsShadow);1235 if (Loc.second.Id != 0 || !Create)1236 return Loc.second;1237 1238 // Create a copy of RA and mark is as shadow.1239 Ref NA = cloneNode(RA);1240 NA.Addr->setFlags(Flags | NodeAttrs::Shadow);1241 IA.Addr->addMemberAfter(Loc.first, NA, *this);1242 return NA;1243}1244 1245// Create a new statement node in the block node BA that corresponds to1246// the machine instruction MI.1247void DataFlowGraph::buildStmt(Block BA, MachineInstr &In) {1248 Stmt SA = newStmt(BA, &In);1249 1250 auto isCall = [](const MachineInstr &In) -> bool {1251 if (In.isCall())1252 return true;1253 // Is tail call?1254 if (In.isBranch()) {1255 for (const MachineOperand &Op : In.operands())1256 if (Op.isGlobal() || Op.isSymbol())1257 return true;1258 // Assume indirect branches are calls. This is for the purpose of1259 // keeping implicit operands, and so it won't hurt on intra-function1260 // indirect branches.1261 if (In.isIndirectBranch())1262 return true;1263 }1264 return false;1265 };1266 1267 auto isDefUndef = [this](const MachineInstr &In, RegisterRef DR) -> bool {1268 // This instruction defines DR. Check if there is a use operand that1269 // would make DR live on entry to the instruction.1270 for (const MachineOperand &Op : In.all_uses()) {1271 if (Op.getReg() == 0 || Op.isUndef())1272 continue;1273 RegisterRef UR = makeRegRef(Op);1274 if (getPRI().alias(DR, UR))1275 return false;1276 }1277 return true;1278 };1279 1280 bool IsCall = isCall(In);1281 unsigned NumOps = In.getNumOperands();1282 1283 // Avoid duplicate implicit defs. This will not detect cases of implicit1284 // defs that define registers that overlap, but it is not clear how to1285 // interpret that in the absence of explicit defs. Overlapping explicit1286 // defs are likely illegal already.1287 BitVector DoneDefs(TRI.getNumRegs());1288 // Process explicit defs first.1289 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {1290 MachineOperand &Op = In.getOperand(OpN);1291 if (!Op.isReg() || !Op.isDef() || Op.isImplicit())1292 continue;1293 Register R = Op.getReg();1294 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)))1295 continue;1296 uint16_t Flags = NodeAttrs::None;1297 if (TOI.isPreserving(In, OpN)) {1298 Flags |= NodeAttrs::Preserving;1299 // If the def is preserving, check if it is also undefined.1300 if (isDefUndef(In, makeRegRef(Op)))1301 Flags |= NodeAttrs::Undef;1302 }1303 if (TOI.isClobbering(In, OpN))1304 Flags |= NodeAttrs::Clobbering;1305 if (TOI.isFixedReg(In, OpN))1306 Flags |= NodeAttrs::Fixed;1307 if (IsCall && Op.isDead())1308 Flags |= NodeAttrs::Dead;1309 Def DA = newDef(SA, Op, Flags);1310 SA.Addr->addMember(DA, *this);1311 assert(!DoneDefs.test(R));1312 DoneDefs.set(R);1313 }1314 1315 // Process reg-masks (as clobbers).1316 BitVector DoneClobbers(TRI.getNumRegs());1317 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {1318 MachineOperand &Op = In.getOperand(OpN);1319 if (!Op.isRegMask())1320 continue;1321 uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | NodeAttrs::Dead;1322 Def DA = newDef(SA, Op, Flags);1323 SA.Addr->addMember(DA, *this);1324 // Record all clobbered registers in DoneDefs.1325 const uint32_t *RM = Op.getRegMask();1326 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {1327 if (!isTracked(RegisterRef(i)))1328 continue;1329 if (!(RM[i / 32] & (1u << (i % 32))))1330 DoneClobbers.set(i);1331 }1332 }1333 1334 // Process implicit defs, skipping those that have already been added1335 // as explicit.1336 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {1337 MachineOperand &Op = In.getOperand(OpN);1338 if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())1339 continue;1340 Register R = Op.getReg();1341 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)) || DoneDefs.test(R))1342 continue;1343 RegisterRef RR = makeRegRef(Op);1344 uint16_t Flags = NodeAttrs::None;1345 if (TOI.isPreserving(In, OpN)) {1346 Flags |= NodeAttrs::Preserving;1347 // If the def is preserving, check if it is also undefined.1348 if (isDefUndef(In, RR))1349 Flags |= NodeAttrs::Undef;1350 }1351 if (TOI.isClobbering(In, OpN))1352 Flags |= NodeAttrs::Clobbering;1353 if (TOI.isFixedReg(In, OpN))1354 Flags |= NodeAttrs::Fixed;1355 if (IsCall && Op.isDead()) {1356 if (DoneClobbers.test(R))1357 continue;1358 Flags |= NodeAttrs::Dead;1359 }1360 Def DA = newDef(SA, Op, Flags);1361 SA.Addr->addMember(DA, *this);1362 DoneDefs.set(R);1363 }1364 1365 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {1366 MachineOperand &Op = In.getOperand(OpN);1367 if (!Op.isReg() || !Op.isUse())1368 continue;1369 Register R = Op.getReg();1370 if (!R || !R.isPhysical() || !isTracked(RegisterRef(R)))1371 continue;1372 uint16_t Flags = NodeAttrs::None;1373 if (Op.isUndef())1374 Flags |= NodeAttrs::Undef;1375 if (TOI.isFixedReg(In, OpN))1376 Flags |= NodeAttrs::Fixed;1377 Use UA = newUse(SA, Op, Flags);1378 SA.Addr->addMember(UA, *this);1379 }1380}1381 1382// Scan all defs in the block node BA and record in PhiM the locations of1383// phi nodes corresponding to these defs.1384// Clobbering defs in BA are recorded in PhiClobberM1385void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM,1386 BlockRefsMap &PhiClobberM, Block BA) {1387 // Check all defs from block BA and record them in each block in BA's1388 // iterated dominance frontier. This information will later be used to1389 // create phi nodes.1390 MachineBasicBlock *BB = BA.Addr->getCode();1391 assert(BB);1392 auto DFLoc = MDF.find(BB);1393 if (DFLoc == MDF.end() || DFLoc->second.empty())1394 return;1395 1396 // Traverse all instructions in the block and collect the set of all1397 // defined references. For each reference there will be a phi created1398 // in the block's iterated dominance frontier.1399 // This is done to make sure that each defined reference gets only one1400 // phi node, even if it is defined multiple times.1401 RegisterAggr Defs(getPRI());1402 RegisterAggr ClobberDefs(getPRI());1403 for (Instr IA : BA.Addr->members(*this)) {1404 for (Ref RA : IA.Addr->members_if(IsDef, *this)) {1405 RegisterRef RR = RA.Addr->getRegRef(*this);1406 if (!isTracked(RR))1407 continue;1408 if (RR.isReg())1409 Defs.insert(RR);1410 // Clobbering def1411 else if (RR.isMask())1412 ClobberDefs.insert(RR);1413 }1414 }1415 1416 // Calculate the iterated dominance frontier of BB.1417 const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;1418 SetVector<MachineBasicBlock *> IDF(llvm::from_range, DF);1419 for (unsigned i = 0; i < IDF.size(); ++i) {1420 auto F = MDF.find(IDF[i]);1421 if (F != MDF.end())1422 IDF.insert_range(F->second);1423 }1424 1425 // Finally, add the set of defs to each block in the iterated dominance1426 // frontier.1427 for (auto *DB : IDF) {1428 Block DBA = findBlock(DB);1429 PhiM[DBA.Id].insert(Defs);1430 PhiClobberM[DBA.Id].insert(ClobberDefs);1431 }1432}1433 1434// Given the locations of phi nodes in the map PhiM, create the phi nodes1435// that are located in the block node BA.1436void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block BA,1437 const DefStackMap &DefM) {1438 // Check if this blocks has any DF defs, i.e. if there are any defs1439 // that this block is in the iterated dominance frontier of.1440 auto HasDF = PhiM.find(BA.Id);1441 if (HasDF == PhiM.end() || HasDF->second.empty())1442 return;1443 1444 // Prepare a list of NodeIds of the block's predecessors.1445 NodeList Preds;1446 const MachineBasicBlock *MBB = BA.Addr->getCode();1447 for (MachineBasicBlock *PB : MBB->predecessors())1448 Preds.push_back(findBlock(PB));1449 1450 RegisterAggr PhiDefs(getPRI());1451 // DefM will be non empty when we are building phis1452 // for clobbering defs1453 if (!DefM.empty()) {1454 for (Instr IA : BA.Addr->members_if(IsPhi, *this)) {1455 for (Def DA : IA.Addr->members_if(IsDef, *this)) {1456 auto DR = DA.Addr->getRegRef(*this);1457 PhiDefs.insert(DR);1458 }1459 }1460 }1461 1462 MachineRegisterInfo &MRI = MF.getRegInfo();1463 const RegisterAggr &Defs = PhiM[BA.Id];1464 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;1465 1466 for (RegisterRef RR : Defs.refs()) {1467 if (!DefM.empty()) {1468 auto F = DefM.find(RR.Id);1469 // Do not create a phi for unallocatable registers, or for registers1470 // that are never livein to BA.1471 // If a phi exists for RR, do not create another.1472 if (!MRI.isAllocatable(RR.asMCReg()) || PhiDefs.hasCoverOf(RR) ||1473 F == DefM.end() || F->second.empty())1474 continue;1475 // Do not create a phi, if all reaching defs are clobbering1476 auto RDef = F->second.top();1477 if (RDef->Addr->getFlags() & NodeAttrs::Clobbering)1478 continue;1479 PhiDefs.insert(RR);1480 }1481 Phi PA = newPhi(BA);1482 PA.Addr->addMember(newDef(PA, RR, PhiFlags), *this);1483 1484 // Add phi uses.1485 for (Block PBA : Preds) {1486 PA.Addr->addMember(newPhiUse(PA, RR, PBA), *this);1487 }1488 }1489}1490 1491// Remove any unneeded phi nodes that were created during the build process.1492void DataFlowGraph::removeUnusedPhis() {1493 // This will remove unused phis, i.e. phis where each def does not reach1494 // any uses or other defs. This will not detect or remove circular phi1495 // chains that are otherwise dead. Unused/dead phis are created during1496 // the build process and this function is intended to remove these cases1497 // that are easily determinable to be unnecessary.1498 1499 SetVector<NodeId> PhiQ;1500 for (Block BA : TheFunc.Addr->members(*this)) {1501 for (auto P : BA.Addr->members_if(IsPhi, *this))1502 PhiQ.insert(P.Id);1503 }1504 1505 static auto HasUsedDef = [](NodeList &Ms) -> bool {1506 for (Node M : Ms) {1507 if (M.Addr->getKind() != NodeAttrs::Def)1508 continue;1509 Def DA = M;1510 if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)1511 return true;1512 }1513 return false;1514 };1515 1516 // Any phi, if it is removed, may affect other phis (make them dead).1517 // For each removed phi, collect the potentially affected phis and add1518 // them back to the queue.1519 while (!PhiQ.empty()) {1520 auto PA = addr<PhiNode *>(PhiQ[0]);1521 PhiQ.remove(PA.Id);1522 NodeList Refs = PA.Addr->members(*this);1523 if (HasUsedDef(Refs))1524 continue;1525 for (Ref RA : Refs) {1526 if (NodeId RD = RA.Addr->getReachingDef()) {1527 auto RDA = addr<DefNode *>(RD);1528 Instr OA = RDA.Addr->getOwner(*this);1529 if (IsPhi(OA))1530 PhiQ.insert(OA.Id);1531 }1532 if (RA.Addr->isDef())1533 unlinkDef(RA, true);1534 else1535 unlinkUse(RA, true);1536 }1537 Block BA = PA.Addr->getOwner(*this);1538 BA.Addr->removeMember(PA, *this);1539 }1540}1541 1542// For a given reference node TA in an instruction node IA, connect the1543// reaching def of TA to the appropriate def node. Create any shadow nodes1544// as appropriate.1545template <typename T>1546void DataFlowGraph::linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS) {1547 if (DS.empty())1548 return;1549 RegisterRef RR = TA.Addr->getRegRef(*this);1550 NodeAddr<T> TAP;1551 1552 // References from the def stack that have been examined so far.1553 RegisterAggr Defs(getPRI());1554 1555 for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {1556 RegisterRef QR = I->Addr->getRegRef(*this);1557 1558 // Skip all defs that we have already seen.1559 // If this completes a cover of RR, stop the stack traversal.1560 bool Seen = Defs.hasCoverOf(QR);1561 if (Seen)1562 continue;1563 1564 bool Cover = Defs.insert(QR).hasCoverOf(RR);1565 1566 // The reaching def.1567 Def RDA = *I;1568 1569 // Pick the reached node.1570 if (TAP.Id == 0) {1571 TAP = TA;1572 } else {1573 // Mark the existing ref as "shadow" and create a new shadow.1574 TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);1575 TAP = getNextShadow(IA, TAP, true);1576 }1577 1578 // Create the link.1579 TAP.Addr->linkToDef(TAP.Id, RDA);1580 1581 if (Cover)1582 break;1583 }1584}1585 1586// Create data-flow links for all reference nodes in the statement node SA.1587template <typename Predicate>1588void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) {1589#ifndef NDEBUG1590 RegisterSet Defs(getPRI());1591#endif1592 1593 // Link all nodes (upwards in the data-flow) with their reaching defs.1594 for (Ref RA : SA.Addr->members_if(P, *this)) {1595 uint16_t Kind = RA.Addr->getKind();1596 assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use);1597 RegisterRef RR = RA.Addr->getRegRef(*this);1598#ifndef NDEBUG1599 // Do not expect multiple defs of the same reference.1600 assert(Kind != NodeAttrs::Def || !Defs.count(RR));1601 Defs.insert(RR);1602#endif1603 1604 auto F = DefM.find(RR.Id);1605 if (F == DefM.end())1606 continue;1607 DefStack &DS = F->second;1608 if (Kind == NodeAttrs::Use)1609 linkRefUp<UseNode *>(SA, RA, DS);1610 else if (Kind == NodeAttrs::Def)1611 linkRefUp<DefNode *>(SA, RA, DS);1612 else1613 llvm_unreachable("Unexpected node in instruction");1614 }1615}1616 1617// Create data-flow links for all instructions in the block node BA. This1618// will include updating any phi nodes in BA.1619void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, BlockRefsMap &PhiClobberM,1620 Block BA) {1621 // Create phi nodes for clobbering defs.1622 // Since a huge number of registers can get clobbered, it would result in many1623 // phi nodes being created in the graph. Only create phi nodes that have a non1624 // clobbering reaching def. Use DefM to get not clobbering defs reaching a1625 // block.1626 buildPhis(PhiClobberM, BA, DefM);1627 1628 // Push block delimiters.1629 markBlock(BA.Id, DefM);1630 1631 auto IsClobber = [](Ref RA) -> bool {1632 return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);1633 };1634 auto IsNoClobber = [](Ref RA) -> bool {1635 return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);1636 };1637 1638 assert(BA.Addr && "block node address is needed to create a data-flow link");1639 // For each non-phi instruction in the block, link all the defs and uses1640 // to their reaching defs. For any member of the block (including phis),1641 // push the defs on the corresponding stacks.1642 for (Instr IA : BA.Addr->members(*this)) {1643 // Ignore phi nodes here. They will be linked part by part from the1644 // predecessors.1645 if (IA.Addr->getKind() == NodeAttrs::Stmt) {1646 linkStmtRefs(DefM, IA, IsUse);1647 linkStmtRefs(DefM, IA, IsClobber);1648 }1649 1650 // Push the definitions on the stack.1651 pushClobbers(IA, DefM);1652 1653 if (IA.Addr->getKind() == NodeAttrs::Stmt)1654 linkStmtRefs(DefM, IA, IsNoClobber);1655 1656 pushDefs(IA, DefM);1657 }1658 1659 // Recursively process all children in the dominator tree.1660 MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());1661 for (auto *I : *N) {1662 MachineBasicBlock *SB = I->getBlock();1663 Block SBA = findBlock(SB);1664 linkBlockRefs(DefM, PhiClobberM, SBA);1665 }1666 1667 // Link the phi uses from the successor blocks.1668 auto IsUseForBA = [BA](Node NA) -> bool {1669 if (NA.Addr->getKind() != NodeAttrs::Use)1670 return false;1671 assert(NA.Addr->getFlags() & NodeAttrs::PhiRef);1672 return PhiUse(NA).Addr->getPredecessor() == BA.Id;1673 };1674 1675 RegisterAggr EHLiveIns = getLandingPadLiveIns();1676 MachineBasicBlock *MBB = BA.Addr->getCode();1677 1678 for (MachineBasicBlock *SB : MBB->successors()) {1679 bool IsEHPad = SB->isEHPad();1680 Block SBA = findBlock(SB);1681 for (Instr IA : SBA.Addr->members_if(IsPhi, *this)) {1682 // Do not link phi uses for landing pad live-ins.1683 if (IsEHPad) {1684 // Find what register this phi is for.1685 Ref RA = IA.Addr->getFirstMember(*this);1686 assert(RA.Id != 0);1687 if (EHLiveIns.hasCoverOf(RA.Addr->getRegRef(*this)))1688 continue;1689 }1690 // Go over each phi use associated with MBB, and link it.1691 for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {1692 PhiUse PUA = U;1693 RegisterRef RR = PUA.Addr->getRegRef(*this);1694 linkRefUp<UseNode *>(IA, PUA, DefM[RR.Id]);1695 }1696 }1697 }1698 1699 // Pop all defs from this block from the definition stacks.1700 releaseBlock(BA.Id, DefM);1701}1702 1703// Remove the use node UA from any data-flow and structural links.1704void DataFlowGraph::unlinkUseDF(Use UA) {1705 NodeId RD = UA.Addr->getReachingDef();1706 NodeId Sib = UA.Addr->getSibling();1707 1708 if (RD == 0) {1709 assert(Sib == 0);1710 return;1711 }1712 1713 auto RDA = addr<DefNode *>(RD);1714 auto TA = addr<UseNode *>(RDA.Addr->getReachedUse());1715 if (TA.Id == UA.Id) {1716 RDA.Addr->setReachedUse(Sib);1717 return;1718 }1719 1720 while (TA.Id != 0) {1721 NodeId S = TA.Addr->getSibling();1722 if (S == UA.Id) {1723 TA.Addr->setSibling(UA.Addr->getSibling());1724 return;1725 }1726 TA = addr<UseNode *>(S);1727 }1728}1729 1730// Remove the def node DA from any data-flow and structural links.1731void DataFlowGraph::unlinkDefDF(Def DA) {1732 //1733 // RD1734 // | reached1735 // | def1736 // :1737 // .1738 // +----+1739 // ... -- | DA | -- ... -- 0 : sibling chain of DA1740 // +----+1741 // | | reached1742 // | : def1743 // | .1744 // | ... : Siblings (defs)1745 // |1746 // : reached1747 // . use1748 // ... : sibling chain of reached uses1749 1750 NodeId RD = DA.Addr->getReachingDef();1751 1752 // Visit all siblings of the reached def and reset their reaching defs.1753 // Also, defs reached by DA are now "promoted" to being reached by RD,1754 // so all of them will need to be spliced into the sibling chain where1755 // DA belongs.1756 auto getAllNodes = [this](NodeId N) -> NodeList {1757 NodeList Res;1758 while (N) {1759 auto RA = addr<RefNode *>(N);1760 // Keep the nodes in the exact sibling order.1761 Res.push_back(RA);1762 N = RA.Addr->getSibling();1763 }1764 return Res;1765 };1766 NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());1767 NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());1768 1769 if (RD == 0) {1770 for (Ref I : ReachedDefs)1771 I.Addr->setSibling(0);1772 for (Ref I : ReachedUses)1773 I.Addr->setSibling(0);1774 }1775 for (Def I : ReachedDefs)1776 I.Addr->setReachingDef(RD);1777 for (Use I : ReachedUses)1778 I.Addr->setReachingDef(RD);1779 1780 NodeId Sib = DA.Addr->getSibling();1781 if (RD == 0) {1782 assert(Sib == 0);1783 return;1784 }1785 1786 // Update the reaching def node and remove DA from the sibling list.1787 auto RDA = addr<DefNode *>(RD);1788 auto TA = addr<DefNode *>(RDA.Addr->getReachedDef());1789 if (TA.Id == DA.Id) {1790 // If DA is the first reached def, just update the RD's reached def1791 // to the DA's sibling.1792 RDA.Addr->setReachedDef(Sib);1793 } else {1794 // Otherwise, traverse the sibling list of the reached defs and remove1795 // DA from it.1796 while (TA.Id != 0) {1797 NodeId S = TA.Addr->getSibling();1798 if (S == DA.Id) {1799 TA.Addr->setSibling(Sib);1800 break;1801 }1802 TA = addr<DefNode *>(S);1803 }1804 }1805 1806 // Splice the DA's reached defs into the RDA's reached def chain.1807 if (!ReachedDefs.empty()) {1808 auto Last = Def(ReachedDefs.back());1809 Last.Addr->setSibling(RDA.Addr->getReachedDef());1810 RDA.Addr->setReachedDef(ReachedDefs.front().Id);1811 }1812 // Splice the DA's reached uses into the RDA's reached use chain.1813 if (!ReachedUses.empty()) {1814 auto Last = Use(ReachedUses.back());1815 Last.Addr->setSibling(RDA.Addr->getReachedUse());1816 RDA.Addr->setReachedUse(ReachedUses.front().Id);1817 }1818}1819 1820bool DataFlowGraph::isTracked(RegisterRef RR) const {1821 return !disjoint(getPRI().getUnits(RR), TrackedUnits);1822}1823 1824bool DataFlowGraph::hasUntrackedRef(Stmt S, bool IgnoreReserved) const {1825 SmallVector<MachineOperand *> Ops;1826 1827 for (Ref R : S.Addr->members(*this)) {1828 Ops.push_back(&R.Addr->getOp());1829 RegisterRef RR = R.Addr->getRegRef(*this);1830 if (IgnoreReserved && RR.isReg() && ReservedRegs[RR.asMCReg().id()])1831 continue;1832 if (!isTracked(RR))1833 return true;1834 }1835 for (const MachineOperand &Op : S.Addr->getCode()->operands()) {1836 if (!Op.isReg() && !Op.isRegMask())1837 continue;1838 if (!llvm::is_contained(Ops, &Op))1839 return true;1840 }1841 return false;1842}1843 1844} // end namespace llvm::rdf1845