Bug Summary

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

Annotated Source Code

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