Bug Summary

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