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