Bug Summary

File:lib/Target/Hexagon/RDFGraph.cpp
Warning:line 1582, column 21
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/STLExtras.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/CodeGen/MachineBasicBlock.h"
16#include "llvm/CodeGen/MachineDominanceFrontier.h"
17#include "llvm/CodeGen/MachineDominators.h"
18#include "llvm/CodeGen/MachineFunction.h"
19#include "llvm/CodeGen/MachineInstr.h"
20#include "llvm/CodeGen/MachineOperand.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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) {
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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 567, __PRETTY_FUNCTION__))
;
568 if (M.Addr->getKind() == NodeAttrs::Stmt) {
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~svn306458/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());
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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 580, __PRETTY_FUNCTION__))
;
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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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~svn306458/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);
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())
1
Assuming the condition is false
2
Taking false branch
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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 907, __PRETTY_FUNCTION__))
;
908 for (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I)
3
Loop condition is false. Execution continues on line 910
909 LiveIns.insert(RegisterRef(I->first));
910 if (MRI.tracksLiveness()) {
4
Taking false branch
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 for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) {
5
Loop condition is false. Execution continues on line 930
918 RegisterRef RR = *I;
919 NodeAddr<PhiNode*> PA = newPhi(EA);
920 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
921 NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
922 PA.Addr->addMember(DA, *this);
923 }
924
925 // Add phis for landing pads.
926 // Landing pads, unlike usual backs blocks, are not entered through
927 // branches in the program, or fall-throughs from other blocks. They
928 // are entered from the exception handling runtime and target's ABI
929 // may define certain registers as defined on entry to such a block.
930 RegisterSet EHRegs = getLandingPadLiveIns();
931 if (!EHRegs.empty()) {
6
Assuming the condition is false
7
Taking false branch
932 for (NodeAddr<BlockNode*> BA : Blocks) {
933 const MachineBasicBlock &B = *BA.Addr->getCode();
934 if (!B.isEHPad())
935 continue;
936
937 // Prepare a list of NodeIds of the block's predecessors.
938 NodeList Preds;
939 for (MachineBasicBlock *PB : B.predecessors())
940 Preds.push_back(findBlock(PB));
941
942 // Build phi nodes for each live-in.
943 for (RegisterRef RR : EHRegs) {
944 NodeAddr<PhiNode*> PA = newPhi(BA);
945 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
946 // Add def:
947 NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
948 PA.Addr->addMember(DA, *this);
949 // Add uses (no reaching defs for phi uses):
950 for (NodeAddr<BlockNode*> PBA : Preds) {
951 NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
952 PA.Addr->addMember(PUA, *this);
953 }
954 }
955 }
956 }
957
958 // Build a map "PhiM" which will contain, for each block, the set
959 // of references that will require phi definitions in that block.
960 BlockRefsMap PhiM;
961 for (NodeAddr<BlockNode*> BA : Blocks)
8
Assuming '__begin' is equal to '__end'
962 recordDefsForDF(PhiM, RefM, BA);
963 for (NodeAddr<BlockNode*> BA : Blocks)
9
Assuming '__begin' is equal to '__end'
964 buildPhis(PhiM, RefM, BA);
965
966 // Link all the refs. This will recursively traverse the dominator tree.
967 DefStackMap DM;
968 linkBlockRefs(DM, EA);
969
970 // Finally, remove all unused phi nodes.
971 if (!(Options & BuildOptions::KeepDeadPhis))
10
Assuming the condition is true
11
Taking true branch
972 removeUnusedPhis();
12
Calling 'DataFlowGraph::removeUnusedPhis'
973}
974
975RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const {
976 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 977, __PRETTY_FUNCTION__))
977 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 977, __PRETTY_FUNCTION__))
;
978 assert(Reg != 0)((Reg != 0) ? static_cast<void> (0) : __assert_fail ("Reg != 0"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 978, __PRETTY_FUNCTION__))
;
979 if (Sub != 0)
980 Reg = TRI.getSubReg(Reg, Sub);
981 return RegisterRef(Reg);
982}
983
984RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const {
985 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 985, __PRETTY_FUNCTION__))
;
986 if (Op.isReg())
987 return makeRegRef(Op.getReg(), Op.getSubReg());
988 return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll());
989}
990
991RegisterRef DataFlowGraph::restrictRef(RegisterRef AR, RegisterRef BR) const {
992 if (AR.Reg == BR.Reg) {
993 LaneBitmask M = AR.Mask & BR.Mask;
994 return M.any() ? RegisterRef(AR.Reg, M) : RegisterRef();
995 }
996#ifndef NDEBUG
997// RegisterRef NAR = PRI.normalize(AR);
998// RegisterRef NBR = PRI.normalize(BR);
999// assert(NAR.Reg != NBR.Reg);
1000#endif
1001 // This isn't strictly correct, because the overlap may happen in the
1002 // part masked out.
1003 if (PRI.alias(AR, BR))
1004 return AR;
1005 return RegisterRef();
1006}
1007
1008// For each stack in the map DefM, push the delimiter for block B on it.
1009void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) {
1010 // Push block delimiters.
1011 for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I)
1012 I->second.start_block(B);
1013}
1014
1015// Remove all definitions coming from block B from each stack in DefM.
1016void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) {
1017 // Pop all defs from this block from the definition stack. Defs that were
1018 // added to the map during the traversal of instructions will not have a
1019 // delimiter, but for those, the whole stack will be emptied.
1020 for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I)
1021 I->second.clear_block(B);
1022
1023 // Finally, remove empty stacks from the map.
1024 for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) {
1025 NextI = std::next(I);
1026 // This preserves the validity of iterators other than I.
1027 if (I->second.empty())
1028 DefM.erase(I);
1029 }
1030}
1031
1032// Push all definitions from the instruction node IA to an appropriate
1033// stack in DefM.
1034void DataFlowGraph::pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
1035 pushClobbers(IA, DefM);
1036 pushDefs(IA, DefM);
1037}
1038
1039// Push all definitions from the instruction node IA to an appropriate
1040// stack in DefM.
1041void DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
1042 NodeSet Visited;
1043 std::set<RegisterId> Defined;
1044
1045 // The important objectives of this function are:
1046 // - to be able to handle instructions both while the graph is being
1047 // constructed, and after the graph has been constructed, and
1048 // - maintain proper ordering of definitions on the stack for each
1049 // register reference:
1050 // - if there are two or more related defs in IA (i.e. coming from
1051 // the same machine operand), then only push one def on the stack,
1052 // - if there are multiple unrelated defs of non-overlapping
1053 // subregisters of S, then the stack for S will have both (in an
1054 // unspecified order), but the order does not matter from the data-
1055 // -flow perspective.
1056
1057 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
1058 if (Visited.count(DA.Id))
1059 continue;
1060 if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering))
1061 continue;
1062
1063 NodeList Rel = getRelatedRefs(IA, DA);
1064 NodeAddr<DefNode*> PDA = Rel.front();
1065 RegisterRef RR = PDA.Addr->getRegRef(*this);
1066
1067 // Push the definition on the stack for the register and all aliases.
1068 // The def stack traversal in linkNodeUp will check the exact aliasing.
1069 DefM[RR.Reg].push(DA);
1070 Defined.insert(RR.Reg);
1071 for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
1072 // Check that we don't push the same def twice.
1073 assert(A != RR.Reg)((A != RR.Reg) ? static_cast<void> (0) : __assert_fail (
"A != RR.Reg", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1073, __PRETTY_FUNCTION__))
;
1074 if (!Defined.count(A))
1075 DefM[A].push(DA);
1076 }
1077 // Mark all the related defs as visited.
1078 for (NodeAddr<NodeBase*> T : Rel)
1079 Visited.insert(T.Id);
1080 }
1081}
1082
1083// Push all definitions from the instruction node IA to an appropriate
1084// stack in DefM.
1085void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) {
1086 NodeSet Visited;
1087#ifndef NDEBUG
1088 std::set<RegisterId> Defined;
1089#endif
1090
1091 // The important objectives of this function are:
1092 // - to be able to handle instructions both while the graph is being
1093 // constructed, and after the graph has been constructed, and
1094 // - maintain proper ordering of definitions on the stack for each
1095 // register reference:
1096 // - if there are two or more related defs in IA (i.e. coming from
1097 // the same machine operand), then only push one def on the stack,
1098 // - if there are multiple unrelated defs of non-overlapping
1099 // subregisters of S, then the stack for S will have both (in an
1100 // unspecified order), but the order does not matter from the data-
1101 // -flow perspective.
1102
1103 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) {
1104 if (Visited.count(DA.Id))
1105 continue;
1106 if (DA.Addr->getFlags() & NodeAttrs::Clobbering)
1107 continue;
1108
1109 NodeList Rel = getRelatedRefs(IA, DA);
1110 NodeAddr<DefNode*> PDA = Rel.front();
1111 RegisterRef RR = PDA.Addr->getRegRef(*this);
1112#ifndef NDEBUG
1113 // Assert if the register is defined in two or more unrelated defs.
1114 // This could happen if there are two or more def operands defining it.
1115 if (!Defined.insert(RR.Reg).second) {
1116 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
1117 dbgs() << "Multiple definitions of register: "
1118 << Print<RegisterRef>(RR, *this) << " in\n " << *MI
1119 << "in BB#" << MI->getParent()->getNumber() << '\n';
1120 llvm_unreachable(nullptr)::llvm::llvm_unreachable_internal(nullptr, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1120)
;
1121 }
1122#endif
1123 // Push the definition on the stack for the register and all aliases.
1124 // The def stack traversal in linkNodeUp will check the exact aliasing.
1125 DefM[RR.Reg].push(DA);
1126 for (RegisterId A : PRI.getAliasSet(RR.Reg)) {
1127 // Check that we don't push the same def twice.
1128 assert(A != RR.Reg)((A != RR.Reg) ? static_cast<void> (0) : __assert_fail (
"A != RR.Reg", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1128, __PRETTY_FUNCTION__))
;
1129 DefM[A].push(DA);
1130 }
1131 // Mark all the related defs as visited.
1132 for (NodeAddr<NodeBase*> T : Rel)
1133 Visited.insert(T.Id);
1134 }
1135}
1136
1137// Return the list of all reference nodes related to RA, including RA itself.
1138// See "getNextRelated" for the meaning of a "related reference".
1139NodeList DataFlowGraph::getRelatedRefs(NodeAddr<InstrNode*> IA,
1140 NodeAddr<RefNode*> RA) const {
1141 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1141, __PRETTY_FUNCTION__))
;
1142
1143 NodeList Refs;
1144 NodeId Start = RA.Id;
1145 do {
1146 Refs.push_back(RA);
1147 RA = getNextRelated(IA, RA);
1148 } while (RA.Id != 0 && RA.Id != Start);
1149 return Refs;
1150}
1151
1152// Clear all information in the graph.
1153void DataFlowGraph::reset() {
1154 Memory.clear();
1155 BlockNodes.clear();
1156 Func = NodeAddr<FuncNode*>();
1157}
1158
1159// Return the next reference node in the instruction node IA that is related
1160// to RA. Conceptually, two reference nodes are related if they refer to the
1161// same instance of a register access, but differ in flags or other minor
1162// characteristics. Specific examples of related nodes are shadow reference
1163// nodes.
1164// Return the equivalent of nullptr if there are no more related references.
1165NodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA,
1166 NodeAddr<RefNode*> RA) const {
1167 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1167, __PRETTY_FUNCTION__))
;
1168
1169 auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool {
1170 if (TA.Addr->getKind() != RA.Addr->getKind())
1171 return false;
1172 if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this))
1173 return false;
1174 return true;
1175 };
1176 auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
1177 return Related(TA) &&
1178 &RA.Addr->getOp() == &TA.Addr->getOp();
1179 };
1180 auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool {
1181 if (!Related(TA))
1182 return false;
1183 if (TA.Addr->getKind() != NodeAttrs::Use)
1184 return true;
1185 // For phi uses, compare predecessor blocks.
1186 const NodeAddr<const PhiUseNode*> TUA = TA;
1187 const NodeAddr<const PhiUseNode*> RUA = RA;
1188 return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor();
1189 };
1190
1191 RegisterRef RR = RA.Addr->getRegRef(*this);
1192 if (IA.Addr->getKind() == NodeAttrs::Stmt)
1193 return RA.Addr->getNextRef(RR, RelatedStmt, true, *this);
1194 return RA.Addr->getNextRef(RR, RelatedPhi, true, *this);
1195}
1196
1197// Find the next node related to RA in IA that satisfies condition P.
1198// If such a node was found, return a pair where the second element is the
1199// located node. If such a node does not exist, return a pair where the
1200// first element is the element after which such a node should be inserted,
1201// and the second element is a null-address.
1202template <typename Predicate>
1203std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
1204DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
1205 Predicate P) const {
1206 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1206, __PRETTY_FUNCTION__))
;
1207
1208 NodeAddr<RefNode*> NA;
1209 NodeId Start = RA.Id;
1210 while (true) {
1211 NA = getNextRelated(IA, RA);
1212 if (NA.Id == 0 || NA.Id == Start)
1213 break;
1214 if (P(NA))
1215 break;
1216 RA = NA;
1217 }
1218
1219 if (NA.Id != 0 && NA.Id != Start)
1220 return std::make_pair(RA, NA);
1221 return std::make_pair(RA, NodeAddr<RefNode*>());
1222}
1223
1224// Get the next shadow node in IA corresponding to RA, and optionally create
1225// such a node if it does not exist.
1226NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA,
1227 NodeAddr<RefNode*> RA, bool Create) {
1228 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1228, __PRETTY_FUNCTION__))
;
1229
1230 uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1231 auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
1232 return TA.Addr->getFlags() == Flags;
1233 };
1234 auto Loc = locateNextRef(IA, RA, IsShadow);
1235 if (Loc.second.Id != 0 || !Create)
1236 return Loc.second;
1237
1238 // Create a copy of RA and mark is as shadow.
1239 NodeAddr<RefNode*> NA = cloneNode(RA);
1240 NA.Addr->setFlags(Flags | NodeAttrs::Shadow);
1241 IA.Addr->addMemberAfter(Loc.first, NA, *this);
1242 return NA;
1243}
1244
1245// Get the next shadow node in IA corresponding to RA. Return null-address
1246// if such a node does not exist.
1247NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA,
1248 NodeAddr<RefNode*> RA) const {
1249 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1249, __PRETTY_FUNCTION__))
;
1250 uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow;
1251 auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool {
1252 return TA.Addr->getFlags() == Flags;
1253 };
1254 return locateNextRef(IA, RA, IsShadow).second;
1255}
1256
1257// Create a new statement node in the block node BA that corresponds to
1258// the machine instruction MI.
1259void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) {
1260 NodeAddr<StmtNode*> SA = newStmt(BA, &In);
1261
1262 auto isCall = [] (const MachineInstr &In) -> bool {
1263 if (In.isCall())
1264 return true;
1265 // Is tail call?
1266 if (In.isBranch()) {
1267 for (const MachineOperand &Op : In.operands())
1268 if (Op.isGlobal() || Op.isSymbol())
1269 return true;
1270 // Assume indirect branches are calls. This is for the purpose of
1271 // keeping implicit operands, and so it won't hurt on intra-function
1272 // indirect branches.
1273 if (In.isIndirectBranch())
1274 return true;
1275 }
1276 return false;
1277 };
1278
1279 auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool {
1280 // This instruction defines DR. Check if there is a use operand that
1281 // would make DR live on entry to the instruction.
1282 for (const MachineOperand &Op : In.operands()) {
1283 if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef())
1284 continue;
1285 RegisterRef UR = makeRegRef(Op);
1286 if (PRI.alias(DR, UR))
1287 return false;
1288 }
1289 return true;
1290 };
1291
1292 bool IsCall = isCall(In);
1293 unsigned NumOps = In.getNumOperands();
1294
1295 // Avoid duplicate implicit defs. This will not detect cases of implicit
1296 // defs that define registers that overlap, but it is not clear how to
1297 // interpret that in the absence of explicit defs. Overlapping explicit
1298 // defs are likely illegal already.
1299 BitVector DoneDefs(TRI.getNumRegs());
1300 // Process explicit defs first.
1301 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1302 MachineOperand &Op = In.getOperand(OpN);
1303 if (!Op.isReg() || !Op.isDef() || Op.isImplicit())
1304 continue;
1305 unsigned R = Op.getReg();
1306 if (!R || !TargetRegisterInfo::isPhysicalRegister(R))
1307 continue;
1308 uint16_t Flags = NodeAttrs::None;
1309 if (TOI.isPreserving(In, OpN)) {
1310 Flags |= NodeAttrs::Preserving;
1311 // If the def is preserving, check if it is also undefined.
1312 if (isDefUndef(In, makeRegRef(Op)))
1313 Flags |= NodeAttrs::Undef;
1314 }
1315 if (TOI.isClobbering(In, OpN))
1316 Flags |= NodeAttrs::Clobbering;
1317 if (TOI.isFixedReg(In, OpN))
1318 Flags |= NodeAttrs::Fixed;
1319 if (IsCall && Op.isDead())
1320 Flags |= NodeAttrs::Dead;
1321 NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1322 SA.Addr->addMember(DA, *this);
1323 assert(!DoneDefs.test(R))((!DoneDefs.test(R)) ? static_cast<void> (0) : __assert_fail
("!DoneDefs.test(R)", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1323, __PRETTY_FUNCTION__))
;
1324 DoneDefs.set(R);
1325 }
1326
1327 // Process reg-masks (as clobbers).
1328 BitVector DoneClobbers(TRI.getNumRegs());
1329 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1330 MachineOperand &Op = In.getOperand(OpN);
1331 if (!Op.isRegMask())
1332 continue;
1333 uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed |
1334 NodeAttrs::Dead;
1335 NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1336 SA.Addr->addMember(DA, *this);
1337 // Record all clobbered registers in DoneDefs.
1338 const uint32_t *RM = Op.getRegMask();
1339 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i)
1340 if (!(RM[i/32] & (1u << (i%32))))
1341 DoneClobbers.set(i);
1342 }
1343
1344 // Process implicit defs, skipping those that have already been added
1345 // as explicit.
1346 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1347 MachineOperand &Op = In.getOperand(OpN);
1348 if (!Op.isReg() || !Op.isDef() || !Op.isImplicit())
1349 continue;
1350 unsigned R = Op.getReg();
1351 if (!R || !TargetRegisterInfo::isPhysicalRegister(R) || DoneDefs.test(R))
1352 continue;
1353 RegisterRef RR = makeRegRef(Op);
1354 uint16_t Flags = NodeAttrs::None;
1355 if (TOI.isPreserving(In, OpN)) {
1356 Flags |= NodeAttrs::Preserving;
1357 // If the def is preserving, check if it is also undefined.
1358 if (isDefUndef(In, RR))
1359 Flags |= NodeAttrs::Undef;
1360 }
1361 if (TOI.isClobbering(In, OpN))
1362 Flags |= NodeAttrs::Clobbering;
1363 if (TOI.isFixedReg(In, OpN))
1364 Flags |= NodeAttrs::Fixed;
1365 if (IsCall && Op.isDead()) {
1366 if (DoneClobbers.test(R))
1367 continue;
1368 Flags |= NodeAttrs::Dead;
1369 }
1370 NodeAddr<DefNode*> DA = newDef(SA, Op, Flags);
1371 SA.Addr->addMember(DA, *this);
1372 DoneDefs.set(R);
1373 }
1374
1375 for (unsigned OpN = 0; OpN < NumOps; ++OpN) {
1376 MachineOperand &Op = In.getOperand(OpN);
1377 if (!Op.isReg() || !Op.isUse())
1378 continue;
1379 unsigned R = Op.getReg();
1380 if (!R || !TargetRegisterInfo::isPhysicalRegister(R))
1381 continue;
1382 uint16_t Flags = NodeAttrs::None;
1383 if (Op.isUndef())
1384 Flags |= NodeAttrs::Undef;
1385 if (TOI.isFixedReg(In, OpN))
1386 Flags |= NodeAttrs::Fixed;
1387 NodeAddr<UseNode*> UA = newUse(SA, Op, Flags);
1388 SA.Addr->addMember(UA, *this);
1389 }
1390}
1391
1392// Build a map that for each block will have the set of all references from
1393// that block, and from all blocks dominated by it.
1394void DataFlowGraph::buildBlockRefs(NodeAddr<BlockNode*> BA,
1395 BlockRefsMap &RefM) {
1396 RegisterSet &Refs = RefM[BA.Id];
1397 MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());
1398 assert(N)((N) ? static_cast<void> (0) : __assert_fail ("N", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1398, __PRETTY_FUNCTION__))
;
1399 for (auto I : *N) {
1400 MachineBasicBlock *SB = I->getBlock();
1401 NodeAddr<BlockNode*> SBA = findBlock(SB);
1402 buildBlockRefs(SBA, RefM);
1403 const RegisterSet &RefsS = RefM[SBA.Id];
1404 Refs.insert(RefsS.begin(), RefsS.end());
1405 }
1406
1407 for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
1408 for (NodeAddr<RefNode*> RA : IA.Addr->members(*this))
1409 Refs.insert(RA.Addr->getRegRef(*this));
1410}
1411
1412// Scan all defs in the block node BA and record in PhiM the locations of
1413// phi nodes corresponding to these defs.
1414void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM,
1415 NodeAddr<BlockNode*> BA) {
1416 // Check all defs from block BA and record them in each block in BA's
1417 // iterated dominance frontier. This information will later be used to
1418 // create phi nodes.
1419 MachineBasicBlock *BB = BA.Addr->getCode();
1420 assert(BB)((BB) ? static_cast<void> (0) : __assert_fail ("BB", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1420, __PRETTY_FUNCTION__))
;
1421 auto DFLoc = MDF.find(BB);
1422 if (DFLoc == MDF.end() || DFLoc->second.empty())
1423 return;
1424
1425 // Traverse all instructions in the block and collect the set of all
1426 // defined references. For each reference there will be a phi created
1427 // in the block's iterated dominance frontier.
1428 // This is done to make sure that each defined reference gets only one
1429 // phi node, even if it is defined multiple times.
1430 RegisterSet Defs;
1431 for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this))
1432 for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this))
1433 Defs.insert(RA.Addr->getRegRef(*this));
1434
1435 // Calculate the iterated dominance frontier of BB.
1436 const MachineDominanceFrontier::DomSetType &DF = DFLoc->second;
1437 SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end());
1438 for (unsigned i = 0; i < IDF.size(); ++i) {
1439 auto F = MDF.find(IDF[i]);
1440 if (F != MDF.end())
1441 IDF.insert(F->second.begin(), F->second.end());
1442 }
1443
1444 // Get the register references that are reachable from this block.
1445 RegisterSet &Refs = RefM[BA.Id];
1446 for (auto DB : IDF) {
1447 NodeAddr<BlockNode*> DBA = findBlock(DB);
1448 const RegisterSet &RefsD = RefM[DBA.Id];
1449 Refs.insert(RefsD.begin(), RefsD.end());
1450 }
1451
1452 // Finally, add the set of defs to each block in the iterated dominance
1453 // frontier.
1454 for (auto DB : IDF) {
1455 NodeAddr<BlockNode*> DBA = findBlock(DB);
1456 PhiM[DBA.Id].insert(Defs.begin(), Defs.end());
1457 }
1458}
1459
1460// Given the locations of phi nodes in the map PhiM, create the phi nodes
1461// that are located in the block node BA.
1462void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM,
1463 NodeAddr<BlockNode*> BA) {
1464 // Check if this blocks has any DF defs, i.e. if there are any defs
1465 // that this block is in the iterated dominance frontier of.
1466 auto HasDF = PhiM.find(BA.Id);
1467 if (HasDF == PhiM.end() || HasDF->second.empty())
1468 return;
1469
1470 // First, remove all R in Refs in such that there exists T in Refs
1471 // such that T covers R. In other words, only leave those refs that
1472 // are not covered by another ref (i.e. maximal with respect to covering).
1473
1474 auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef {
1475 for (RegisterRef I : RRs)
1476 if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI))
1477 RR = I;
1478 return RR;
1479 };
1480
1481 RegisterSet MaxDF;
1482 for (RegisterRef I : HasDF->second)
1483 MaxDF.insert(MaxCoverIn(I, HasDF->second));
1484
1485 std::vector<RegisterRef> MaxRefs;
1486 RegisterSet &RefB = RefM[BA.Id];
1487 for (RegisterRef I : MaxDF)
1488 MaxRefs.push_back(MaxCoverIn(I, RefB));
1489
1490 // Now, for each R in MaxRefs, get the alias closure of R. If the closure
1491 // only has R in it, create a phi a def for R. Otherwise, create a phi,
1492 // and add a def for each S in the closure.
1493
1494 // Sort the refs so that the phis will be created in a deterministic order.
1495 std::sort(MaxRefs.begin(), MaxRefs.end());
1496 // Remove duplicates.
1497 auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end());
1498 MaxRefs.erase(NewEnd, MaxRefs.end());
1499
1500 auto Aliased = [this,&MaxRefs](RegisterRef RR,
1501 std::vector<unsigned> &Closure) -> bool {
1502 for (unsigned I : Closure)
1503 if (PRI.alias(RR, MaxRefs[I]))
1504 return true;
1505 return false;
1506 };
1507
1508 // Prepare a list of NodeIds of the block's predecessors.
1509 NodeList Preds;
1510 const MachineBasicBlock *MBB = BA.Addr->getCode();
1511 for (MachineBasicBlock *PB : MBB->predecessors())
1512 Preds.push_back(findBlock(PB));
1513
1514 while (!MaxRefs.empty()) {
1515 // Put the first element in the closure, and then add all subsequent
1516 // elements from MaxRefs to it, if they alias at least one element
1517 // already in the closure.
1518 // ClosureIdx: vector of indices in MaxRefs of members of the closure.
1519 std::vector<unsigned> ClosureIdx = { 0 };
1520 for (unsigned i = 1; i != MaxRefs.size(); ++i)
1521 if (Aliased(MaxRefs[i], ClosureIdx))
1522 ClosureIdx.push_back(i);
1523
1524 // Build a phi for the closure.
1525 unsigned CS = ClosureIdx.size();
1526 NodeAddr<PhiNode*> PA = newPhi(BA);
1527
1528 // Add defs.
1529 for (unsigned X = 0; X != CS; ++X) {
1530 RegisterRef RR = MaxRefs[ClosureIdx[X]];
1531 uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving;
1532 NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags);
1533 PA.Addr->addMember(DA, *this);
1534 }
1535 // Add phi uses.
1536 for (NodeAddr<BlockNode*> PBA : Preds) {
1537 for (unsigned X = 0; X != CS; ++X) {
1538 RegisterRef RR = MaxRefs[ClosureIdx[X]];
1539 NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA);
1540 PA.Addr->addMember(PUA, *this);
1541 }
1542 }
1543
1544 // Erase from MaxRefs all elements in the closure.
1545 auto Begin = MaxRefs.begin();
1546 for (unsigned i = ClosureIdx.size(); i != 0; --i)
1547 MaxRefs.erase(Begin + ClosureIdx[i-1]);
1548 }
1549}
1550
1551// Remove any unneeded phi nodes that were created during the build process.
1552void DataFlowGraph::removeUnusedPhis() {
1553 // This will remove unused phis, i.e. phis where each def does not reach
1554 // any uses or other defs. This will not detect or remove circular phi
1555 // chains that are otherwise dead. Unused/dead phis are created during
1556 // the build process and this function is intended to remove these cases
1557 // that are easily determinable to be unnecessary.
1558
1559 SetVector<NodeId> PhiQ;
1560 for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) {
13
Assuming '__begin' is equal to '__end'
1561 for (auto P : BA.Addr->members_if(IsPhi, *this))
1562 PhiQ.insert(P.Id);
1563 }
1564
1565 static auto HasUsedDef = [](NodeList &Ms) -> bool {
1566 for (NodeAddr<NodeBase*> M : Ms) {
1567 if (M.Addr->getKind() != NodeAttrs::Def)
1568 continue;
1569 NodeAddr<DefNode*> DA = M;
1570 if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0)
1571 return true;
1572 }
1573 return false;
1574 };
1575
1576 // Any phi, if it is removed, may affect other phis (make them dead).
1577 // For each removed phi, collect the potentially affected phis and add
1578 // them back to the queue.
1579 while (!PhiQ.empty()) {
14
Assuming the condition is true
15
Loop condition is true. Entering loop body
18
Assuming the condition is true
19
Loop condition is true. Entering loop body
23
Assuming the condition is true
24
Loop condition is true. Entering loop body
1580 auto PA = addr<PhiNode*>(PhiQ[0]);
25
Null pointer value stored to 'PA.Addr'
1581 PhiQ.remove(PA.Id);
1582 NodeList Refs = PA.Addr->members(*this);
26
Called C++ object pointer is null
1583 if (HasUsedDef(Refs))
16
Taking false branch
20
Assuming the condition is true
21
Taking true branch
1584 continue;
22
Execution continues on line 1579
1585 for (NodeAddr<RefNode*> RA : Refs) {
17
Assuming '__begin' is equal to '__end'
1586 if (NodeId RD = RA.Addr->getReachingDef()) {
1587 auto RDA = addr<DefNode*>(RD);
1588 NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this);
1589 if (IsPhi(OA))
1590 PhiQ.insert(OA.Id);
1591 }
1592 if (RA.Addr->isDef())
1593 unlinkDef(RA, true);
1594 else
1595 unlinkUse(RA, true);
1596 }
1597 NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this);
1598 BA.Addr->removeMember(PA, *this);
1599 }
1600}
1601
1602// For a given reference node TA in an instruction node IA, connect the
1603// reaching def of TA to the appropriate def node. Create any shadow nodes
1604// as appropriate.
1605template <typename T>
1606void DataFlowGraph::linkRefUp(NodeAddr<InstrNode*> IA, NodeAddr<T> TA,
1607 DefStack &DS) {
1608 if (DS.empty())
1609 return;
1610 RegisterRef RR = TA.Addr->getRegRef(*this);
1611 NodeAddr<T> TAP;
1612
1613 // References from the def stack that have been examined so far.
1614 RegisterAggr Defs(PRI);
1615
1616 for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) {
1617 RegisterRef QR = I->Addr->getRegRef(*this);
1618
1619 // Skip all defs that are aliased to any of the defs that we have already
1620 // seen. If this completes a cover of RR, stop the stack traversal.
1621 bool Alias = Defs.hasAliasOf(QR);
1622 bool Cover = Defs.insert(QR).hasCoverOf(RR);
1623 if (Alias) {
1624 if (Cover)
1625 break;
1626 continue;
1627 }
1628
1629 // The reaching def.
1630 NodeAddr<DefNode*> RDA = *I;
1631
1632 // Pick the reached node.
1633 if (TAP.Id == 0) {
1634 TAP = TA;
1635 } else {
1636 // Mark the existing ref as "shadow" and create a new shadow.
1637 TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow);
1638 TAP = getNextShadow(IA, TAP, true);
1639 }
1640
1641 // Create the link.
1642 TAP.Addr->linkToDef(TAP.Id, RDA);
1643
1644 if (Cover)
1645 break;
1646 }
1647}
1648
1649// Create data-flow links for all reference nodes in the statement node SA.
1650template <typename Predicate>
1651void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA,
1652 Predicate P) {
1653#ifndef NDEBUG
1654 RegisterSet Defs;
1655#endif
1656
1657 // Link all nodes (upwards in the data-flow) with their reaching defs.
1658 for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) {
1659 uint16_t Kind = RA.Addr->getKind();
1660 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1660, __PRETTY_FUNCTION__))
;
1661 RegisterRef RR = RA.Addr->getRegRef(*this);
1662#ifndef NDEBUG
1663 // Do not expect multiple defs of the same reference.
1664 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1664, __PRETTY_FUNCTION__))
;
1665 Defs.insert(RR);
1666#endif
1667
1668 auto F = DefM.find(RR.Reg);
1669 if (F == DefM.end())
1670 continue;
1671 DefStack &DS = F->second;
1672 if (Kind == NodeAttrs::Use)
1673 linkRefUp<UseNode*>(SA, RA, DS);
1674 else if (Kind == NodeAttrs::Def)
1675 linkRefUp<DefNode*>(SA, RA, DS);
1676 else
1677 llvm_unreachable("Unexpected node in instruction")::llvm::llvm_unreachable_internal("Unexpected node in instruction"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1677)
;
1678 }
1679}
1680
1681// Create data-flow links for all instructions in the block node BA. This
1682// will include updating any phi nodes in BA.
1683void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA) {
1684 // Push block delimiters.
1685 markBlock(BA.Id, DefM);
1686
1687 auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool {
1688 return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering);
1689 };
1690 auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool {
1691 return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering);
1692 };
1693
1694 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1694, __PRETTY_FUNCTION__))
;
1695 // For each non-phi instruction in the block, link all the defs and uses
1696 // to their reaching defs. For any member of the block (including phis),
1697 // push the defs on the corresponding stacks.
1698 for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) {
1699 // Ignore phi nodes here. They will be linked part by part from the
1700 // predecessors.
1701 if (IA.Addr->getKind() == NodeAttrs::Stmt) {
1702 linkStmtRefs(DefM, IA, IsUse);
1703 linkStmtRefs(DefM, IA, IsClobber);
1704 }
1705
1706 // Push the definitions on the stack.
1707 pushClobbers(IA, DefM);
1708
1709 if (IA.Addr->getKind() == NodeAttrs::Stmt)
1710 linkStmtRefs(DefM, IA, IsNoClobber);
1711
1712 pushDefs(IA, DefM);
1713 }
1714
1715 // Recursively process all children in the dominator tree.
1716 MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode());
1717 for (auto I : *N) {
1718 MachineBasicBlock *SB = I->getBlock();
1719 NodeAddr<BlockNode*> SBA = findBlock(SB);
1720 linkBlockRefs(DefM, SBA);
1721 }
1722
1723 // Link the phi uses from the successor blocks.
1724 auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool {
1725 if (NA.Addr->getKind() != NodeAttrs::Use)
1726 return false;
1727 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~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1727, __PRETTY_FUNCTION__))
;
1728 NodeAddr<PhiUseNode*> PUA = NA;
1729 return PUA.Addr->getPredecessor() == BA.Id;
1730 };
1731
1732 RegisterSet EHLiveIns = getLandingPadLiveIns();
1733 MachineBasicBlock *MBB = BA.Addr->getCode();
1734
1735 for (MachineBasicBlock *SB : MBB->successors()) {
1736 bool IsEHPad = SB->isEHPad();
1737 NodeAddr<BlockNode*> SBA = findBlock(SB);
1738 for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) {
1739 // Do not link phi uses for landing pad live-ins.
1740 if (IsEHPad) {
1741 // Find what register this phi is for.
1742 NodeAddr<RefNode*> RA = IA.Addr->getFirstMember(*this);
1743 assert(RA.Id != 0)((RA.Id != 0) ? static_cast<void> (0) : __assert_fail (
"RA.Id != 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1743, __PRETTY_FUNCTION__))
;
1744 if (EHLiveIns.count(RA.Addr->getRegRef(*this)))
1745 continue;
1746 }
1747 // Go over each phi use associated with MBB, and link it.
1748 for (auto U : IA.Addr->members_if(IsUseForBA, *this)) {
1749 NodeAddr<PhiUseNode*> PUA = U;
1750 RegisterRef RR = PUA.Addr->getRegRef(*this);
1751 linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]);
1752 }
1753 }
1754 }
1755
1756 // Pop all defs from this block from the definition stacks.
1757 releaseBlock(BA.Id, DefM);
1758}
1759
1760// Remove the use node UA from any data-flow and structural links.
1761void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) {
1762 NodeId RD = UA.Addr->getReachingDef();
1763 NodeId Sib = UA.Addr->getSibling();
1764
1765 if (RD == 0) {
1766 assert(Sib == 0)((Sib == 0) ? static_cast<void> (0) : __assert_fail ("Sib == 0"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1766, __PRETTY_FUNCTION__))
;
1767 return;
1768 }
1769
1770 auto RDA = addr<DefNode*>(RD);
1771 auto TA = addr<UseNode*>(RDA.Addr->getReachedUse());
1772 if (TA.Id == UA.Id) {
1773 RDA.Addr->setReachedUse(Sib);
1774 return;
1775 }
1776
1777 while (TA.Id != 0) {
1778 NodeId S = TA.Addr->getSibling();
1779 if (S == UA.Id) {
1780 TA.Addr->setSibling(UA.Addr->getSibling());
1781 return;
1782 }
1783 TA = addr<UseNode*>(S);
1784 }
1785}
1786
1787// Remove the def node DA from any data-flow and structural links.
1788void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) {
1789 //
1790 // RD
1791 // | reached
1792 // | def
1793 // :
1794 // .
1795 // +----+
1796 // ... -- | DA | -- ... -- 0 : sibling chain of DA
1797 // +----+
1798 // | | reached
1799 // | : def
1800 // | .
1801 // | ... : Siblings (defs)
1802 // |
1803 // : reached
1804 // . use
1805 // ... : sibling chain of reached uses
1806
1807 NodeId RD = DA.Addr->getReachingDef();
1808
1809 // Visit all siblings of the reached def and reset their reaching defs.
1810 // Also, defs reached by DA are now "promoted" to being reached by RD,
1811 // so all of them will need to be spliced into the sibling chain where
1812 // DA belongs.
1813 auto getAllNodes = [this] (NodeId N) -> NodeList {
1814 NodeList Res;
1815 while (N) {
1816 auto RA = addr<RefNode*>(N);
1817 // Keep the nodes in the exact sibling order.
1818 Res.push_back(RA);
1819 N = RA.Addr->getSibling();
1820 }
1821 return Res;
1822 };
1823 NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef());
1824 NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse());
1825
1826 if (RD == 0) {
1827 for (NodeAddr<RefNode*> I : ReachedDefs)
1828 I.Addr->setSibling(0);
1829 for (NodeAddr<RefNode*> I : ReachedUses)
1830 I.Addr->setSibling(0);
1831 }
1832 for (NodeAddr<DefNode*> I : ReachedDefs)
1833 I.Addr->setReachingDef(RD);
1834 for (NodeAddr<UseNode*> I : ReachedUses)
1835 I.Addr->setReachingDef(RD);
1836
1837 NodeId Sib = DA.Addr->getSibling();
1838 if (RD == 0) {
1839 assert(Sib == 0)((Sib == 0) ? static_cast<void> (0) : __assert_fail ("Sib == 0"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/lib/Target/Hexagon/RDFGraph.cpp"
, 1839, __PRETTY_FUNCTION__))
;
1840 return;
1841 }
1842
1843 // Update the reaching def node and remove DA from the sibling list.
1844 auto RDA = addr<DefNode*>(RD);
1845 auto TA = addr<DefNode*>(RDA.Addr->getReachedDef());
1846 if (TA.Id == DA.Id) {
1847 // If DA is the first reached def, just update the RD's reached def
1848 // to the DA's sibling.
1849 RDA.Addr->setReachedDef(Sib);
1850 } else {
1851 // Otherwise, traverse the sibling list of the reached defs and remove
1852 // DA from it.
1853 while (TA.Id != 0) {
1854 NodeId S = TA.Addr->getSibling();
1855 if (S == DA.Id) {
1856 TA.Addr->setSibling(Sib);
1857 break;
1858 }
1859 TA = addr<DefNode*>(S);
1860 }
1861 }
1862
1863 // Splice the DA's reached defs into the RDA's reached def chain.
1864 if (!ReachedDefs.empty()) {
1865 auto Last = NodeAddr<DefNode*>(ReachedDefs.back());
1866 Last.Addr->setSibling(RDA.Addr->getReachedDef());
1867 RDA.Addr->setReachedDef(ReachedDefs.front().Id);
1868 }
1869 // Splice the DA's reached uses into the RDA's reached use chain.
1870 if (!ReachedUses.empty()) {
1871 auto Last = NodeAddr<UseNode*>(ReachedUses.back());
1872 Last.Addr->setSibling(RDA.Addr->getReachedUse());
1873 RDA.Addr->setReachedUse(ReachedUses.front().Id);
1874 }
1875}