Bug Summary

File:lib/Target/Hexagon/RDFGraph.cpp
Warning:line 1648, column 26
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name RDFGraph.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn361465/build-llvm/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-9~svn361465/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn361465/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn361465/build-llvm/lib/Target/Hexagon -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn361465=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-05-24-031927-21217-1 -x c++ /build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.cpp -faddrsig

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

/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h

1//===- RDFGraph.h -----------------------------------------------*- C++ -*-===//
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// for a non-SSA program representation (e.g. post-RA machine code).
11//
12//
13// *** Introduction
14//
15// The RDF graph is a collection of nodes, each of which denotes some element
16// of the program. There are two main types of such elements: code and refe-
17// rences. Conceptually, "code" is something that represents the structure
18// of the program, e.g. basic block or a statement, while "reference" is an
19// instance of accessing a register, e.g. a definition or a use. Nodes are
20// connected with each other based on the structure of the program (such as
21// blocks, instructions, etc.), and based on the data flow (e.g. reaching
22// definitions, reached uses, etc.). The single-reaching-definition principle
23// of SSA is generally observed, although, due to the non-SSA representation
24// of the program, there are some differences between the graph and a "pure"
25// SSA representation.
26//
27//
28// *** Implementation remarks
29//
30// Since the graph can contain a large number of nodes, memory consumption
31// was one of the major design considerations. As a result, there is a single
32// base class NodeBase which defines all members used by all possible derived
33// classes. The members are arranged in a union, and a derived class cannot
34// add any data members of its own. Each derived class only defines the
35// functional interface, i.e. member functions. NodeBase must be a POD,
36// which implies that all of its members must also be PODs.
37// Since nodes need to be connected with other nodes, pointers have been
38// replaced with 32-bit identifiers: each node has an id of type NodeId.
39// There are mapping functions in the graph that translate between actual
40// memory addresses and the corresponding identifiers.
41// A node id of 0 is equivalent to nullptr.
42//
43//
44// *** Structure of the graph
45//
46// A code node is always a collection of other nodes. For example, a code
47// node corresponding to a basic block will contain code nodes corresponding
48// to instructions. In turn, a code node corresponding to an instruction will
49// contain a list of reference nodes that correspond to the definitions and
50// uses of registers in that instruction. The members are arranged into a
51// circular list, which is yet another consequence of the effort to save
52// memory: for each member node it should be possible to obtain its owner,
53// and it should be possible to access all other members. There are other
54// ways to accomplish that, but the circular list seemed the most natural.
55//
56// +- CodeNode -+
57// | | <---------------------------------------------------+
58// +-+--------+-+ |
59// |FirstM |LastM |
60// | +-------------------------------------+ |
61// | | |
62// V V |
63// +----------+ Next +----------+ Next Next +----------+ Next |
64// | |----->| |-----> ... ----->| |----->-+
65// +- Member -+ +- Member -+ +- Member -+
66//
67// The order of members is such that related reference nodes (see below)
68// should be contiguous on the member list.
69//
70// A reference node is a node that encapsulates an access to a register,
71// in other words, data flowing into or out of a register. There are two
72// major kinds of reference nodes: defs and uses. A def node will contain
73// the id of the first reached use, and the id of the first reached def.
74// Each def and use will contain the id of the reaching def, and also the
75// id of the next reached def (for def nodes) or use (for use nodes).
76// The "next node sharing the same reaching def" is denoted as "sibling".
77// In summary:
78// - Def node contains: reaching def, sibling, first reached def, and first
79// reached use.
80// - Use node contains: reaching def and sibling.
81//
82// +-- DefNode --+
83// | R2 = ... | <---+--------------------+
84// ++---------+--+ | |
85// |Reached |Reached | |
86// |Def |Use | |
87// | | |Reaching |Reaching
88// | V |Def |Def
89// | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib
90// | | ... = R2 |----->| ... = R2 |----> ... ----> 0
91// | +-------------+ +-------------+
92// V
93// +-- DefNode --+ Sib
94// | R2 = ... |----> ...
95// ++---------+--+
96// | |
97// | |
98// ... ...
99//
100// To get a full picture, the circular lists connecting blocks within a
101// function, instructions within a block, etc. should be superimposed with
102// the def-def, def-use links shown above.
103// To illustrate this, consider a small example in a pseudo-assembly:
104// foo:
105// add r2, r0, r1 ; r2 = r0+r1
106// addi r0, r2, 1 ; r0 = r2+1
107// ret r0 ; return value in r0
108//
109// The graph (in a format used by the debugging functions) would look like:
110//
111// DFG dump:[
112// f1: Function foo
113// b2: === %bb.0 === preds(0), succs(0):
114// p3: phi [d4<r0>(,d12,u9):]
115// p5: phi [d6<r1>(,,u10):]
116// s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
117// s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
118// s14: ret [u15<r0>(d12):]
119// ]
120//
121// The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
122// kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
123// ment, d - def, u - use).
124// The format of a def node is:
125// dN<R>(rd,d,u):sib,
126// where
127// N - numeric node id,
128// R - register being defined
129// rd - reaching def,
130// d - reached def,
131// u - reached use,
132// sib - sibling.
133// The format of a use node is:
134// uN<R>[!](rd):sib,
135// where
136// N - numeric node id,
137// R - register being used,
138// rd - reaching def,
139// sib - sibling.
140// Possible annotations (usually preceding the node id):
141// + - preserving def,
142// ~ - clobbering def,
143// " - shadow ref (follows the node id),
144// ! - fixed register (appears after register name).
145//
146// The circular lists are not explicit in the dump.
147//
148//
149// *** Node attributes
150//
151// NodeBase has a member "Attrs", which is the primary way of determining
152// the node's characteristics. The fields in this member decide whether
153// the node is a code node or a reference node (i.e. node's "type"), then
154// within each type, the "kind" determines what specifically this node
155// represents. The remaining bits, "flags", contain additional information
156// that is even more detailed than the "kind".
157// CodeNode's kinds are:
158// - Phi: Phi node, members are reference nodes.
159// - Stmt: Statement, members are reference nodes.
160// - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
161// - Func: The whole function. The members are basic block nodes.
162// RefNode's kinds are:
163// - Use.
164// - Def.
165//
166// Meaning of flags:
167// - Preserving: applies only to defs. A preserving def is one that can
168// preserve some of the original bits among those that are included in
169// the register associated with that def. For example, if R0 is a 32-bit
170// register, but a def can only change the lower 16 bits, then it will
171// be marked as preserving.
172// - Shadow: a reference that has duplicates holding additional reaching
173// defs (see more below).
174// - Clobbering: applied only to defs, indicates that the value generated
175// by this def is unspecified. A typical example would be volatile registers
176// after function calls.
177// - Fixed: the register in this def/use cannot be replaced with any other
178// register. A typical case would be a parameter register to a call, or
179// the register with the return value from a function.
180// - Undef: the register in this reference the register is assumed to have
181// no pre-existing value, even if it appears to be reached by some def.
182// This is typically used to prevent keeping registers artificially live
183// in cases when they are defined via predicated instructions. For example:
184// r0 = add-if-true cond, r10, r11 (1)
185// r0 = add-if-false cond, r12, r13, implicit r0 (2)
186// ... = r0 (3)
187// Before (1), r0 is not intended to be live, and the use of r0 in (3) is
188// not meant to be reached by any def preceding (1). However, since the
189// defs in (1) and (2) are both preserving, these properties alone would
190// imply that the use in (3) may indeed be reached by some prior def.
191// Adding Undef flag to the def in (1) prevents that. The Undef flag
192// may be applied to both defs and uses.
193// - Dead: applies only to defs. The value coming out of a "dead" def is
194// assumed to be unused, even if the def appears to be reaching other defs
195// or uses. The motivation for this flag comes from dead defs on function
196// calls: there is no way to determine if such a def is dead without
197// analyzing the target's ABI. Hence the graph should contain this info,
198// as it is unavailable otherwise. On the other hand, a def without any
199// uses on a typical instruction is not the intended target for this flag.
200//
201// *** Shadow references
202//
203// It may happen that a super-register can have two (or more) non-overlapping
204// sub-registers. When both of these sub-registers are defined and followed
205// by a use of the super-register, the use of the super-register will not
206// have a unique reaching def: both defs of the sub-registers need to be
207// accounted for. In such cases, a duplicate use of the super-register is
208// added and it points to the extra reaching def. Both uses are marked with
209// a flag "shadow". Example:
210// Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
211// set r0, 1 ; r0 = 1
212// set r1, 1 ; r1 = 1
213// addi t1, t0, 1 ; t1 = t0+1
214//
215// The DFG:
216// s1: set [d2<r0>(,,u9):]
217// s3: set [d4<r1>(,,u10):]
218// s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
219//
220// The statement s5 has two use nodes for t0: u7" and u9". The quotation
221// mark " indicates that the node is a shadow.
222//
223
224#ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
225#define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
226
227#include "RDFRegisters.h"
228#include "llvm/ADT/SmallVector.h"
229#include "llvm/MC/LaneBitmask.h"
230#include "llvm/Support/Allocator.h"
231#include "llvm/Support/MathExtras.h"
232#include <cassert>
233#include <cstdint>
234#include <cstring>
235#include <map>
236#include <set>
237#include <unordered_map>
238#include <utility>
239#include <vector>
240
241// RDF uses uint32_t to refer to registers. This is to ensure that the type
242// size remains specific. In other places, registers are often stored using
243// unsigned.
244static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
245
246namespace llvm {
247
248class MachineBasicBlock;
249class MachineDominanceFrontier;
250class MachineDominatorTree;
251class MachineFunction;
252class MachineInstr;
253class MachineOperand;
254class raw_ostream;
255class TargetInstrInfo;
256class TargetRegisterInfo;
257
258namespace rdf {
259
260 using NodeId = uint32_t;
261
262 struct DataFlowGraph;
263
264 struct NodeAttrs {
265 enum : uint16_t {
266 None = 0x0000, // Nothing
267
268 // Types: 2 bits
269 TypeMask = 0x0003,
270 Code = 0x0001, // 01, Container
271 Ref = 0x0002, // 10, Reference
272
273 // Kind: 3 bits
274 KindMask = 0x0007 << 2,
275 Def = 0x0001 << 2, // 001
276 Use = 0x0002 << 2, // 010
277 Phi = 0x0003 << 2, // 011
278 Stmt = 0x0004 << 2, // 100
279 Block = 0x0005 << 2, // 101
280 Func = 0x0006 << 2, // 110
281
282 // Flags: 7 bits for now
283 FlagMask = 0x007F << 5,
284 Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs.
285 Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values.
286 PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode.
287 Preserving = 0x0008 << 5, // 0001000, Def can keep original bits.
288 Fixed = 0x0010 << 5, // 0010000, Fixed register.
289 Undef = 0x0020 << 5, // 0100000, Has no pre-existing value.
290 Dead = 0x0040 << 5, // 1000000, Does not define a value.
291 };
292
293 static uint16_t type(uint16_t T) { return T & TypeMask; }
294 static uint16_t kind(uint16_t T) { return T & KindMask; }
295 static uint16_t flags(uint16_t T) { return T & FlagMask; }
296
297 static uint16_t set_type(uint16_t A, uint16_t T) {
298 return (A & ~TypeMask) | T;
299 }
300
301 static uint16_t set_kind(uint16_t A, uint16_t K) {
302 return (A & ~KindMask) | K;
303 }
304
305 static uint16_t set_flags(uint16_t A, uint16_t F) {
306 return (A & ~FlagMask) | F;
307 }
308
309 // Test if A contains B.
310 static bool contains(uint16_t A, uint16_t B) {
311 if (type(A) != Code)
312 return false;
313 uint16_t KB = kind(B);
314 switch (kind(A)) {
315 case Func:
316 return KB == Block;
317 case Block:
318 return KB == Phi || KB == Stmt;
319 case Phi:
320 case Stmt:
321 return type(B) == Ref;
322 }
323 return false;
324 }
325 };
326
327 struct BuildOptions {
328 enum : unsigned {
329 None = 0x00,
330 KeepDeadPhis = 0x01, // Do not remove dead phis during build.
331 };
332 };
333
334 template <typename T> struct NodeAddr {
335 NodeAddr() = default;
336 NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
337
338 // Type cast (casting constructor). The reason for having this class
339 // instead of std::pair.
340 template <typename S> NodeAddr(const NodeAddr<S> &NA)
341 : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
27
Null pointer value stored to 'RA.Addr'
342
343 bool operator== (const NodeAddr<T> &NA) const {
344 assert((Addr == NA.Addr) == (Id == NA.Id))(((Addr == NA.Addr) == (Id == NA.Id)) ? static_cast<void>
(0) : __assert_fail ("(Addr == NA.Addr) == (Id == NA.Id)", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 344, __PRETTY_FUNCTION__))
;
345 return Addr == NA.Addr;
346 }
347 bool operator!= (const NodeAddr<T> &NA) const {
348 return !operator==(NA);
349 }
350
351 T Addr = nullptr;
352 NodeId Id = 0;
353 };
354
355 struct NodeBase;
356
357 // Fast memory allocation and translation between node id and node address.
358 // This is really the same idea as the one underlying the "bump pointer
359 // allocator", the difference being in the translation. A node id is
360 // composed of two components: the index of the block in which it was
361 // allocated, and the index within the block. With the default settings,
362 // where the number of nodes per block is 4096, the node id (minus 1) is:
363 //
364 // bit position: 11 0
365 // +----------------------------+--------------+
366 // | Index of the block |Index in block|
367 // +----------------------------+--------------+
368 //
369 // The actual node id is the above plus 1, to avoid creating a node id of 0.
370 //
371 // This method significantly improved the build time, compared to using maps
372 // (std::unordered_map or DenseMap) to translate between pointers and ids.
373 struct NodeAllocator {
374 // Amount of storage for a single node.
375 enum { NodeMemSize = 32 };
376
377 NodeAllocator(uint32_t NPB = 4096)
378 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
379 IndexMask((1 << BitsPerIndex)-1) {
380 assert(isPowerOf2_32(NPB))((isPowerOf2_32(NPB)) ? static_cast<void> (0) : __assert_fail
("isPowerOf2_32(NPB)", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 380, __PRETTY_FUNCTION__))
;
381 }
382
383 NodeBase *ptr(NodeId N) const {
384 uint32_t N1 = N-1;
385 uint32_t BlockN = N1 >> BitsPerIndex;
386 uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
387 return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
388 }
389
390 NodeId id(const NodeBase *P) const;
391 NodeAddr<NodeBase*> New();
392 void clear();
393
394 private:
395 void startNewBlock();
396 bool needNewBlock();
397
398 uint32_t makeId(uint32_t Block, uint32_t Index) const {
399 // Add 1 to the id, to avoid the id of 0, which is treated as "null".
400 return ((Block << BitsPerIndex) | Index) + 1;
401 }
402
403 const uint32_t NodesPerBlock;
404 const uint32_t BitsPerIndex;
405 const uint32_t IndexMask;
406 char *ActiveEnd = nullptr;
407 std::vector<char*> Blocks;
408 using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>;
409 AllocatorTy MemPool;
410 };
411
412 using RegisterSet = std::set<RegisterRef>;
413
414 struct TargetOperandInfo {
415 TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
416 virtual ~TargetOperandInfo() = default;
417
418 virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
419 virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
420 virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
421
422 const TargetInstrInfo &TII;
423 };
424
425 // Packed register reference. Only used for storage.
426 struct PackedRegisterRef {
427 RegisterId Reg;
428 uint32_t MaskId;
429 };
430
431 struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
432 LaneMaskIndex() = default;
433
434 LaneBitmask getLaneMaskForIndex(uint32_t K) const {
435 return K == 0 ? LaneBitmask::getAll() : get(K);
436 }
437
438 uint32_t getIndexForLaneMask(LaneBitmask LM) {
439 assert(LM.any())((LM.any()) ? static_cast<void> (0) : __assert_fail ("LM.any()"
, "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 439, __PRETTY_FUNCTION__))
;
440 return LM.all() ? 0 : insert(LM);
441 }
442
443 uint32_t getIndexForLaneMask(LaneBitmask LM) const {
444 assert(LM.any())((LM.any()) ? static_cast<void> (0) : __assert_fail ("LM.any()"
, "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 444, __PRETTY_FUNCTION__))
;
445 return LM.all() ? 0 : find(LM);
446 }
447 };
448
449 struct NodeBase {
450 public:
451 // Make sure this is a POD.
452 NodeBase() = default;
453
454 uint16_t getType() const { return NodeAttrs::type(Attrs); }
455 uint16_t getKind() const { return NodeAttrs::kind(Attrs); }
456 uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
457 NodeId getNext() const { return Next; }
458
459 uint16_t getAttrs() const { return Attrs; }
460 void setAttrs(uint16_t A) { Attrs = A; }
461 void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
462
463 // Insert node NA after "this" in the circular chain.
464 void append(NodeAddr<NodeBase*> NA);
465
466 // Initialize all members to 0.
467 void init() { memset(this, 0, sizeof *this); }
468
469 void setNext(NodeId N) { Next = N; }
470
471 protected:
472 uint16_t Attrs;
473 uint16_t Reserved;
474 NodeId Next; // Id of the next node in the circular chain.
475 // Definitions of nested types. Using anonymous nested structs would make
476 // this class definition clearer, but unnamed structs are not a part of
477 // the standard.
478 struct Def_struct {
479 NodeId DD, DU; // Ids of the first reached def and use.
480 };
481 struct PhiU_struct {
482 NodeId PredB; // Id of the predecessor block for a phi use.
483 };
484 struct Code_struct {
485 void *CP; // Pointer to the actual code.
486 NodeId FirstM, LastM; // Id of the first member and last.
487 };
488 struct Ref_struct {
489 NodeId RD, Sib; // Ids of the reaching def and the sibling.
490 union {
491 Def_struct Def;
492 PhiU_struct PhiU;
493 };
494 union {
495 MachineOperand *Op; // Non-phi refs point to a machine operand.
496 PackedRegisterRef PR; // Phi refs store register info directly.
497 };
498 };
499
500 // The actual payload.
501 union {
502 Ref_struct Ref;
503 Code_struct Code;
504 };
505 };
506 // The allocator allocates chunks of 32 bytes for each node. The fact that
507 // each node takes 32 bytes in memory is used for fast translation between
508 // the node id and the node address.
509 static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
510 "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
511
512 using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>;
513 using NodeSet = std::set<NodeId>;
514
515 struct RefNode : public NodeBase {
516 RefNode() = default;
517
518 RegisterRef getRegRef(const DataFlowGraph &G) const;
519
520 MachineOperand &getOp() {
521 assert(!(getFlags() & NodeAttrs::PhiRef))((!(getFlags() & NodeAttrs::PhiRef)) ? static_cast<void
> (0) : __assert_fail ("!(getFlags() & NodeAttrs::PhiRef)"
, "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 521, __PRETTY_FUNCTION__))
;
522 return *Ref.Op;
523 }
524
525 void setRegRef(RegisterRef RR, DataFlowGraph &G);
526 void setRegRef(MachineOperand *Op, DataFlowGraph &G);
527
528 NodeId getReachingDef() const {
529 return Ref.RD;
530 }
531 void setReachingDef(NodeId RD) {
532 Ref.RD = RD;
533 }
534
535 NodeId getSibling() const {
536 return Ref.Sib;
537 }
538 void setSibling(NodeId Sib) {
539 Ref.Sib = Sib;
540 }
541
542 bool isUse() const {
543 assert(getType() == NodeAttrs::Ref)((getType() == NodeAttrs::Ref) ? static_cast<void> (0) :
__assert_fail ("getType() == NodeAttrs::Ref", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 543, __PRETTY_FUNCTION__))
;
544 return getKind() == NodeAttrs::Use;
545 }
546
547 bool isDef() const {
548 assert(getType() == NodeAttrs::Ref)((getType() == NodeAttrs::Ref) ? static_cast<void> (0) :
__assert_fail ("getType() == NodeAttrs::Ref", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 548, __PRETTY_FUNCTION__))
;
549 return getKind() == NodeAttrs::Def;
550 }
551
552 template <typename Predicate>
553 NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
554 const DataFlowGraph &G);
555 NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
556 };
557
558 struct DefNode : public RefNode {
559 NodeId getReachedDef() const {
560 return Ref.Def.DD;
561 }
562 void setReachedDef(NodeId D) {
563 Ref.Def.DD = D;
564 }
565 NodeId getReachedUse() const {
566 return Ref.Def.DU;
567 }
568 void setReachedUse(NodeId U) {
569 Ref.Def.DU = U;
570 }
571
572 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
573 };
574
575 struct UseNode : public RefNode {
576 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
577 };
578
579 struct PhiUseNode : public UseNode {
580 NodeId getPredecessor() const {
581 assert(getFlags() & NodeAttrs::PhiRef)((getFlags() & NodeAttrs::PhiRef) ? static_cast<void>
(0) : __assert_fail ("getFlags() & NodeAttrs::PhiRef", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 581, __PRETTY_FUNCTION__))
;
582 return Ref.PhiU.PredB;
583 }
584 void setPredecessor(NodeId B) {
585 assert(getFlags() & NodeAttrs::PhiRef)((getFlags() & NodeAttrs::PhiRef) ? static_cast<void>
(0) : __assert_fail ("getFlags() & NodeAttrs::PhiRef", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 585, __PRETTY_FUNCTION__))
;
586 Ref.PhiU.PredB = B;
587 }
588 };
589
590 struct CodeNode : public NodeBase {
591 template <typename T> T getCode() const {
592 return static_cast<T>(Code.CP);
593 }
594 void setCode(void *C) {
595 Code.CP = C;
596 }
597
598 NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
599 NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
600 void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
601 void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
602 const DataFlowGraph &G);
603 void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
604
605 NodeList members(const DataFlowGraph &G) const;
606 template <typename Predicate>
607 NodeList members_if(Predicate P, const DataFlowGraph &G) const;
608 };
609
610 struct InstrNode : public CodeNode {
611 NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
612 };
613
614 struct PhiNode : public InstrNode {
615 MachineInstr *getCode() const {
616 return nullptr;
617 }
618 };
619
620 struct StmtNode : public InstrNode {
621 MachineInstr *getCode() const {
622 return CodeNode::getCode<MachineInstr*>();
623 }
624 };
625
626 struct BlockNode : public CodeNode {
627 MachineBasicBlock *getCode() const {
628 return CodeNode::getCode<MachineBasicBlock*>();
629 }
630
631 void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
632 };
633
634 struct FuncNode : public CodeNode {
635 MachineFunction *getCode() const {
636 return CodeNode::getCode<MachineFunction*>();
637 }
638
639 NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
640 const DataFlowGraph &G) const;
641 NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
642 };
643
644 struct DataFlowGraph {
645 DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
646 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
647 const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
648
649 NodeBase *ptr(NodeId N) const;
650 template <typename T> T ptr(NodeId N) const {
651 return static_cast<T>(ptr(N));
652 }
653
654 NodeId id(const NodeBase *P) const;
655
656 template <typename T> NodeAddr<T> addr(NodeId N) const {
657 return { ptr<T>(N), N };
658 }
659
660 NodeAddr<FuncNode*> getFunc() const { return Func; }
661 MachineFunction &getMF() const { return MF; }
662 const TargetInstrInfo &getTII() const { return TII; }
663 const TargetRegisterInfo &getTRI() const { return TRI; }
664 const PhysicalRegisterInfo &getPRI() const { return PRI; }
665 const MachineDominatorTree &getDT() const { return MDT; }
666 const MachineDominanceFrontier &getDF() const { return MDF; }
667 const RegisterAggr &getLiveIns() const { return LiveIns; }
668
669 struct DefStack {
670 DefStack() = default;
671
672 bool empty() const { return Stack.empty() || top() == bottom(); }
673
674 private:
675 using value_type = NodeAddr<DefNode *>;
676 struct Iterator {
677 using value_type = DefStack::value_type;
678
679 Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
680 Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
681
682 value_type operator*() const {
683 assert(Pos >= 1)((Pos >= 1) ? static_cast<void> (0) : __assert_fail (
"Pos >= 1", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 683, __PRETTY_FUNCTION__))
;
684 return DS.Stack[Pos-1];
685 }
686 const value_type *operator->() const {
687 assert(Pos >= 1)((Pos >= 1) ? static_cast<void> (0) : __assert_fail (
"Pos >= 1", "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 687, __PRETTY_FUNCTION__))
;
688 return &DS.Stack[Pos-1];
689 }
690 bool operator==(const Iterator &It) const { return Pos == It.Pos; }
691 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
692
693 private:
694 friend struct DefStack;
695
696 Iterator(const DefStack &S, bool Top);
697
698 // Pos-1 is the index in the StorageType object that corresponds to
699 // the top of the DefStack.
700 const DefStack &DS;
701 unsigned Pos;
702 };
703
704 public:
705 using iterator = Iterator;
706
707 iterator top() const { return Iterator(*this, true); }
708 iterator bottom() const { return Iterator(*this, false); }
709 unsigned size() const;
710
711 void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
712 void pop();
713 void start_block(NodeId N);
714 void clear_block(NodeId N);
715
716 private:
717 friend struct Iterator;
718
719 using StorageType = std::vector<value_type>;
720
721 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
722 return (P.Addr == nullptr) && (N == 0 || P.Id == N);
723 }
724
725 unsigned nextUp(unsigned P) const;
726 unsigned nextDown(unsigned P) const;
727
728 StorageType Stack;
729 };
730
731 // Make this std::unordered_map for speed of accessing elements.
732 // Map: Register (physical or virtual) -> DefStack
733 using DefStackMap = std::unordered_map<RegisterId, DefStack>;
734
735 void build(unsigned Options = BuildOptions::None);
736 void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
737 void markBlock(NodeId B, DefStackMap &DefM);
738 void releaseBlock(NodeId B, DefStackMap &DefM);
739
740 PackedRegisterRef pack(RegisterRef RR) {
741 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
742 }
743 PackedRegisterRef pack(RegisterRef RR) const {
744 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
745 }
746 RegisterRef unpack(PackedRegisterRef PR) const {
747 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
748 }
749
750 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
751 RegisterRef makeRegRef(const MachineOperand &Op) const;
752 RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
753
754 NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
755 NodeAddr<RefNode*> RA) const;
756 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
757 NodeAddr<RefNode*> RA, bool Create);
758 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
759 NodeAddr<RefNode*> RA) const;
760 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
761 NodeAddr<RefNode*> RA, bool Create);
762 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
763 NodeAddr<RefNode*> RA) const;
764
765 NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
766 NodeAddr<RefNode*> RA) const;
767
768 NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
769 return BlockNodes.at(BB);
770 }
771
772 void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
773 unlinkUseDF(UA);
774 if (RemoveFromOwner)
775 removeFromOwner(UA);
776 }
777
778 void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
779 unlinkDefDF(DA);
780 if (RemoveFromOwner)
781 removeFromOwner(DA);
782 }
783
784 // Some useful filters.
785 template <uint16_t Kind>
786 static bool IsRef(const NodeAddr<NodeBase*> BA) {
787 return BA.Addr->getType() == NodeAttrs::Ref &&
788 BA.Addr->getKind() == Kind;
789 }
790
791 template <uint16_t Kind>
792 static bool IsCode(const NodeAddr<NodeBase*> BA) {
793 return BA.Addr->getType() == NodeAttrs::Code &&
794 BA.Addr->getKind() == Kind;
795 }
796
797 static bool IsDef(const NodeAddr<NodeBase*> BA) {
798 return BA.Addr->getType() == NodeAttrs::Ref &&
799 BA.Addr->getKind() == NodeAttrs::Def;
800 }
801
802 static bool IsUse(const NodeAddr<NodeBase*> BA) {
803 return BA.Addr->getType() == NodeAttrs::Ref &&
804 BA.Addr->getKind() == NodeAttrs::Use;
805 }
806
807 static bool IsPhi(const NodeAddr<NodeBase*> BA) {
808 return BA.Addr->getType() == NodeAttrs::Code &&
809 BA.Addr->getKind() == NodeAttrs::Phi;
810 }
811
812 static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
813 uint16_t Flags = DA.Addr->getFlags();
814 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
815 }
816
817 private:
818 void reset();
819
820 RegisterSet getLandingPadLiveIns() const;
821
822 NodeAddr<NodeBase*> newNode(uint16_t Attrs);
823 NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
824 NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
825 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
826 NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
827 RegisterRef RR, NodeAddr<BlockNode*> PredB,
828 uint16_t Flags = NodeAttrs::PhiRef);
829 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
830 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
831 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
832 RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
833 NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
834 NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
835 MachineInstr *MI);
836 NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
837 MachineBasicBlock *BB);
838 NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
839
840 template <typename Predicate>
841 std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
842 locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
843 Predicate P) const;
844
845 using BlockRefsMap = std::map<NodeId, RegisterSet>;
846
847 void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
848 void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
849 void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
850 NodeAddr<BlockNode*> BA);
851 void removeUnusedPhis();
852
853 void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
854 void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
855 template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
856 NodeAddr<T> TA, DefStack &DS);
857 template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
858 NodeAddr<StmtNode*> SA, Predicate P);
859 void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
860
861 void unlinkUseDF(NodeAddr<UseNode*> UA);
862 void unlinkDefDF(NodeAddr<DefNode*> DA);
863
864 void removeFromOwner(NodeAddr<RefNode*> RA) {
865 NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
866 IA.Addr->removeMember(RA, *this);
867 }
868
869 MachineFunction &MF;
870 const TargetInstrInfo &TII;
871 const TargetRegisterInfo &TRI;
872 const PhysicalRegisterInfo PRI;
873 const MachineDominatorTree &MDT;
874 const MachineDominanceFrontier &MDF;
875 const TargetOperandInfo &TOI;
876
877 RegisterAggr LiveIns;
878 NodeAddr<FuncNode*> Func;
879 NodeAllocator Memory;
880 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
881 std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
882 // Lane mask map.
883 LaneMaskIndex LMI;
884 }; // struct DataFlowGraph
885
886 template <typename Predicate>
887 NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
888 bool NextOnly, const DataFlowGraph &G) {
889 // Get the "Next" reference in the circular list that references RR and
890 // satisfies predicate "Pred".
891 auto NA = G.addr<NodeBase*>(getNext());
892
893 while (NA.Addr != this) {
894 if (NA.Addr->getType() == NodeAttrs::Ref) {
895 NodeAddr<RefNode*> RA = NA;
896 if (RA.Addr->getRegRef(G) == RR && P(NA))
897 return NA;
898 if (NextOnly)
899 break;
900 NA = G.addr<NodeBase*>(NA.Addr->getNext());
901 } else {
902 // We've hit the beginning of the chain.
903 assert(NA.Addr->getType() == NodeAttrs::Code)((NA.Addr->getType() == NodeAttrs::Code) ? static_cast<
void> (0) : __assert_fail ("NA.Addr->getType() == NodeAttrs::Code"
, "/build/llvm-toolchain-snapshot-9~svn361465/lib/Target/Hexagon/RDFGraph.h"
, 903, __PRETTY_FUNCTION__))
;
904 NodeAddr<CodeNode*> CA = NA;
905 NA = CA.Addr->getFirstMember(G);
906 }
907 }
908 // Return the equivalent of "nullptr" if such a node was not found.
909 return NodeAddr<RefNode*>();
910 }
911
912 template <typename Predicate>
913 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
914 NodeList MM;
915 auto M = getFirstMember(G);
916 if (M.Id == 0)
20
Taking false branch
917 return MM;
918
919 while (M.Addr != this) {
21
Assuming the condition is true
22
Loop condition is true. Entering loop body
25
Loop condition is true. Entering loop body
920 if (P(M))
23
Taking false branch
26
Calling constructor for 'NodeAddr<llvm::rdf::RefNode *>'
28
Returning from constructor for 'NodeAddr<llvm::rdf::RefNode *>'
29
Calling 'operator()'
921 MM.push_back(M);
922 M = G.addr<NodeBase*>(M.Addr->getNext());
24
Null pointer value stored to 'M.Addr'
923 }
924 return MM;
925 }
926
927 template <typename T>
928 struct Print {
929 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
930
931 const T &Obj;
932 const DataFlowGraph &G;
933 };
934
935 template <typename T>
936 struct PrintNode : Print<NodeAddr<T>> {
937 PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
938 : Print<NodeAddr<T>>(x, g) {}
939 };
940
941 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
942 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
943 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
944 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
945 raw_ostream &operator<<(raw_ostream &OS,
946 const Print<NodeAddr<PhiUseNode *>> &P);
947 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
948 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
949 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
950 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
951 raw_ostream &operator<<(raw_ostream &OS,
952 const Print<NodeAddr<StmtNode *>> &P);
953 raw_ostream &operator<<(raw_ostream &OS,
954 const Print<NodeAddr<InstrNode *>> &P);
955 raw_ostream &operator<<(raw_ostream &OS,
956 const Print<NodeAddr<BlockNode *>> &P);
957 raw_ostream &operator<<(raw_ostream &OS,
958 const Print<NodeAddr<FuncNode *>> &P);
959 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
960 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
961 raw_ostream &operator<<(raw_ostream &OS,
962 const Print<DataFlowGraph::DefStack> &P);
963
964} // end namespace rdf
965
966} // end namespace llvm
967
968#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H