LLVM 18.0.0git
RDFLiveness.cpp
Go to the documentation of this file.
1//===- RDFLiveness.cpp ----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Computation of the liveness information from the data-flow graph.
10//
11// The main functionality of this code is to compute block live-in
12// information. With the live-in information in place, the placement
13// of kill flags can also be recalculated.
14//
15// The block live-in calculation is based on the ideas from the following
16// publication:
17//
18// Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin.
19// "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
20// ACM Transactions on Architecture and Code Optimization, Association for
21// Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
22// and Embedded Architectures and Compilers", 8 (4),
23// <10.1145/2086696.2086706>. <hal-00647369>
24//
25#include "llvm/ADT/BitVector.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/STLExtras.h"
28#include "llvm/ADT/SetVector.h"
29#include "llvm/ADT/SmallSet.h"
39#include "llvm/MC/LaneBitmask.h"
44#include <algorithm>
45#include <cassert>
46#include <cstdint>
47#include <iterator>
48#include <map>
49#include <unordered_map>
50#include <utility>
51#include <vector>
52
53using namespace llvm;
54
55static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25),
57 cl::desc("Maximum recursion level"));
58
59namespace llvm::rdf {
60
62 OS << '{';
63 for (const auto &I : P.Obj) {
64 OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{';
65 for (auto J = I.second.begin(), E = I.second.end(); J != E;) {
66 OS << Print(J->first, P.G) << PrintLaneMaskShort(J->second);
67 if (++J != E)
68 OS << ',';
69 }
70 OS << '}';
71 }
72 OS << " }";
73 return OS;
74}
75
76// The order in the returned sequence is the order of reaching defs in the
77// upward traversal: the first def is the closest to the given reference RefA,
78// the next one is further up, and so on.
79// The list ends at a reaching phi def, or when the reference from RefA is
80// covered by the defs in the list (see FullChain).
81// This function provides two modes of operation:
82// (1) Returning the sequence of reaching defs for a particular reference
83// node. This sequence will terminate at the first phi node [1].
84// (2) Returning a partial sequence of reaching defs, where the final goal
85// is to traverse past phi nodes to the actual defs arising from the code
86// itself.
87// In mode (2), the register reference for which the search was started
88// may be different from the reference node RefA, for which this call was
89// made, hence the argument RefRR, which holds the original register.
90// Also, some definitions may have already been encountered in a previous
91// call that will influence register covering. The register references
92// already defined are passed in through DefRRs.
93// In mode (1), the "continuation" considerations do not apply, and the
94// RefRR is the same as the register in RefA, and the set DefRRs is empty.
95//
96// [1] It is possible for multiple phi nodes to be included in the returned
97// sequence:
98// SubA = phi ...
99// SubB = phi ...
100// ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB)
101// However, these phi nodes are independent from one another in terms of
102// the data-flow.
103
105 NodeAddr<RefNode *> RefA, bool TopShadows,
106 bool FullChain,
107 const RegisterAggr &DefRRs) {
108 NodeList RDefs; // Return value.
111
112 // Dead defs will be treated as if they were live, since they are actually
113 // on the data-flow path. They cannot be ignored because even though they
114 // do not generate meaningful values, they still modify registers.
115
116 // If the reference is undefined, there is nothing to do.
117 if (RefA.Addr->getFlags() & NodeAttrs::Undef)
118 return RDefs;
119
120 // The initial queue should not have reaching defs for shadows. The
121 // whole point of a shadow is that it will have a reaching def that
122 // is not aliased to the reaching defs of the related shadows.
123 NodeId Start = RefA.Id;
124 auto SNA = DFG.addr<RefNode *>(Start);
125 if (NodeId RD = SNA.Addr->getReachingDef())
126 DefQ.insert(RD);
127 if (TopShadows) {
128 for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA))
129 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef())
130 DefQ.insert(RD);
131 }
132
133 // Collect all the reaching defs, going up until a phi node is encountered,
134 // or there are no more reaching defs. From this set, the actual set of
135 // reaching defs will be selected.
136 // The traversal upwards must go on until a covering def is encountered.
137 // It is possible that a collection of non-covering (individually) defs
138 // will be sufficient, but keep going until a covering one is found.
139 for (unsigned i = 0; i < DefQ.size(); ++i) {
140 auto TA = DFG.addr<DefNode *>(DefQ[i]);
141 if (TA.Addr->getFlags() & NodeAttrs::PhiRef)
142 continue;
143 // Stop at the covering/overwriting def of the initial register reference.
144 RegisterRef RR = TA.Addr->getRegRef(DFG);
145 if (!DFG.IsPreservingDef(TA))
146 if (RegisterAggr::isCoverOf(RR, RefRR, PRI))
147 continue;
148 // Get the next level of reaching defs. This will include multiple
149 // reaching defs for shadows.
150 for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA))
151 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef())
152 DefQ.insert(RD);
153 // Don't visit sibling defs. They share the same reaching def (which
154 // will be visited anyway), but they define something not aliased to
155 // this ref.
156 }
157
158 // Return the MachineBasicBlock containing a given instruction.
159 auto Block = [this](NodeAddr<InstrNode *> IA) -> MachineBasicBlock * {
160 if (IA.Addr->getKind() == NodeAttrs::Stmt)
161 return NodeAddr<StmtNode *>(IA).Addr->getCode()->getParent();
162 assert(IA.Addr->getKind() == NodeAttrs::Phi);
163 NodeAddr<PhiNode *> PA = IA;
164 NodeAddr<BlockNode *> BA = PA.Addr->getOwner(DFG);
165 return BA.Addr->getCode();
166 };
167
169
170 // Remove all non-phi defs that are not aliased to RefRR, and separate
171 // the the remaining defs into buckets for containing blocks.
172 std::map<NodeId, NodeAddr<InstrNode *>> Owners;
173 std::map<MachineBasicBlock *, SmallVector<NodeId, 32>> Blocks;
174 for (NodeId N : DefQ) {
175 auto TA = DFG.addr<DefNode *>(N);
176 bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef;
177 if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG)))
178 continue;
179 Defs.insert(TA.Id);
180 NodeAddr<InstrNode *> IA = TA.Addr->getOwner(DFG);
181 Owners[TA.Id] = IA;
182 Blocks[Block(IA)].push_back(IA.Id);
183 }
184
185 auto Precedes = [this, &OrdMap](NodeId A, NodeId B) {
186 if (A == B)
187 return false;
190 bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt;
191 bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt;
192 if (StmtA && StmtB) {
193 const MachineInstr *InA = NodeAddr<StmtNode *>(OA).Addr->getCode();
194 const MachineInstr *InB = NodeAddr<StmtNode *>(OB).Addr->getCode();
195 assert(InA->getParent() == InB->getParent());
196 auto FA = OrdMap.find(InA);
197 if (FA != OrdMap.end())
198 return FA->second < OrdMap.find(InB)->second;
199 const MachineBasicBlock *BB = InA->getParent();
200 for (auto It = BB->begin(), E = BB->end(); It != E; ++It) {
201 if (It == InA->getIterator())
202 return true;
203 if (It == InB->getIterator())
204 return false;
205 }
206 llvm_unreachable("InA and InB should be in the same block");
207 }
208 // One of them is a phi node.
209 if (!StmtA && !StmtB) {
210 // Both are phis, which are unordered. Break the tie by id numbers.
211 return A < B;
212 }
213 // Only one of them is a phi. Phis always precede statements.
214 return !StmtA;
215 };
216
217 auto GetOrder = [&OrdMap](MachineBasicBlock &B) {
218 uint32_t Pos = 0;
219 for (MachineInstr &In : B)
220 OrdMap.insert({&In, ++Pos});
221 };
222
223 // For each block, sort the nodes in it.
224 std::vector<MachineBasicBlock *> TmpBB;
225 for (auto &Bucket : Blocks) {
226 TmpBB.push_back(Bucket.first);
227 if (Bucket.second.size() > 2)
228 GetOrder(*Bucket.first);
229 llvm::sort(Bucket.second, Precedes);
230 }
231
232 // Sort the blocks with respect to dominance.
233 llvm::sort(TmpBB,
234 [this](auto A, auto B) { return MDT.properlyDominates(A, B); });
235
236 std::vector<NodeId> TmpInst;
237 for (MachineBasicBlock *MBB : llvm::reverse(TmpBB)) {
238 auto &Bucket = Blocks[MBB];
239 TmpInst.insert(TmpInst.end(), Bucket.rbegin(), Bucket.rend());
240 }
241
242 // The vector is a list of instructions, so that defs coming from
243 // the same instruction don't need to be artificially ordered.
244 // Then, when computing the initial segment, and iterating over an
245 // instruction, pick the defs that contribute to the covering (i.e. is
246 // not covered by previously added defs). Check the defs individually,
247 // i.e. first check each def if is covered or not (without adding them
248 // to the tracking set), and then add all the selected ones.
249
250 // The reason for this is this example:
251 // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes).
252 // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be
253 // covered if we added A first, and A would be covered
254 // if we added B first.
255 // In this example we want both A and B, because we don't want to give
256 // either one priority over the other, since they belong to the same
257 // statement.
258
259 RegisterAggr RRs(DefRRs);
260
261 auto DefInSet = [&Defs](NodeAddr<RefNode *> TA) -> bool {
262 return TA.Addr->getKind() == NodeAttrs::Def && Defs.count(TA.Id);
263 };
264
265 for (NodeId T : TmpInst) {
266 if (!FullChain && RRs.hasCoverOf(RefRR))
267 break;
268 auto TA = DFG.addr<InstrNode *>(T);
269 bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA);
270 NodeList Ds;
271 for (NodeAddr<DefNode *> DA : TA.Addr->members_if(DefInSet, DFG)) {
272 RegisterRef QR = DA.Addr->getRegRef(DFG);
273 // Add phi defs even if they are covered by subsequent defs. This is
274 // for cases where the reached use is not covered by any of the defs
275 // encountered so far: the phi def is needed to expose the liveness
276 // of that use to the entry of the block.
277 // Example:
278 // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2.
279 // d2<R3>(d1,,u3), ...
280 // ..., u3<D1>(d2) This use needs to be live on entry.
281 if (FullChain || IsPhi || !RRs.hasCoverOf(QR))
282 Ds.push_back(DA);
283 }
284 llvm::append_range(RDefs, Ds);
285 for (NodeAddr<DefNode *> DA : Ds) {
286 // When collecting a full chain of definitions, do not consider phi
287 // defs to actually define a register.
288 uint16_t Flags = DA.Addr->getFlags();
289 if (!FullChain || !(Flags & NodeAttrs::PhiRef))
290 if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here.
291 RRs.insert(DA.Addr->getRegRef(DFG));
292 }
293 }
294
295 auto DeadP = [](const NodeAddr<DefNode *> DA) -> bool {
296 return DA.Addr->getFlags() & NodeAttrs::Dead;
297 };
298 llvm::erase_if(RDefs, DeadP);
299
300 return RDefs;
301}
302
303std::pair<NodeSet, bool>
305 NodeSet &Visited, const NodeSet &Defs) {
306 return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest);
307}
308
309std::pair<NodeSet, bool>
310Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
311 NodeSet &Visited, const NodeSet &Defs,
312 unsigned Nest, unsigned MaxNest) {
313 if (Nest > MaxNest)
314 return {NodeSet(), false};
315 // Collect all defined registers. Do not consider phis to be defining
316 // anything, only collect "real" definitions.
317 RegisterAggr DefRRs(PRI);
318 for (NodeId D : Defs) {
319 const auto DA = DFG.addr<const DefNode *>(D);
320 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
321 DefRRs.insert(DA.Addr->getRegRef(DFG));
322 }
323
324 NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs);
325 if (RDs.empty())
326 return {Defs, true};
327
328 // Make a copy of the preexisting definitions and add the newly found ones.
329 NodeSet TmpDefs = Defs;
330 for (NodeAddr<NodeBase *> R : RDs)
331 TmpDefs.insert(R.Id);
332
333 NodeSet Result = Defs;
334
335 for (NodeAddr<DefNode *> DA : RDs) {
336 Result.insert(DA.Id);
337 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
338 continue;
339 NodeAddr<PhiNode *> PA = DA.Addr->getOwner(DFG);
340 if (!Visited.insert(PA.Id).second)
341 continue;
342 // Go over all phi uses and get the reaching defs for each use.
343 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
344 const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
345 Nest + 1, MaxNest);
346 if (!T.second)
347 return {T.first, false};
348 Result.insert(T.first.begin(), T.first.end());
349 }
350 }
351
352 return {Result, true};
353}
354
355/// Find the nearest ref node aliased to RefRR, going upwards in the data
356/// flow, starting from the instruction immediately preceding Inst.
359 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(DFG);
360 NodeList Ins = BA.Addr->members(DFG);
361 NodeId FindId = IA.Id;
362 auto E = Ins.rend();
363 auto B =
364 std::find_if(Ins.rbegin(), E, [FindId](const NodeAddr<InstrNode *> T) {
365 return T.Id == FindId;
366 });
367 // Do not scan IA (which is what B would point to).
368 if (B != E)
369 ++B;
370
371 do {
372 // Process the range of instructions from B to E.
374 NodeList Refs = I.Addr->members(DFG);
376 // Scan all the refs in I aliased to RefRR, and return the one that
377 // is the closest to the output of I, i.e. def > clobber > use.
378 for (NodeAddr<RefNode *> R : Refs) {
379 if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR))
380 continue;
381 if (DFG.IsDef(R)) {
382 // If it's a non-clobbering def, just return it.
383 if (!(R.Addr->getFlags() & NodeAttrs::Clobbering))
384 return R;
385 Clob = R;
386 } else {
387 Use = R;
388 }
389 }
390 if (Clob.Id != 0)
391 return Clob;
392 if (Use.Id != 0)
393 return Use;
394 }
395
396 // Go up to the immediate dominator, if any.
397 MachineBasicBlock *BB = BA.Addr->getCode();
399 if (MachineDomTreeNode *N = MDT.getNode(BB)) {
400 if ((N = N->getIDom()))
401 BA = DFG.findBlock(N->getBlock());
402 }
403 if (!BA.Id)
404 break;
405
406 Ins = BA.Addr->members(DFG);
407 B = Ins.rbegin();
408 E = Ins.rend();
409 } while (true);
410
411 return NodeAddr<RefNode *>();
412}
413
415 const RegisterAggr &DefRRs) {
417
418 // If the original register is already covered by all the intervening
419 // defs, no more uses can be reached.
420 if (DefRRs.hasCoverOf(RefRR))
421 return Uses;
422
423 // Add all directly reached uses.
424 // If the def is dead, it does not provide a value for any use.
425 bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead;
426 NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0;
427 while (U != 0) {
428 auto UA = DFG.addr<UseNode *>(U);
429 if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) {
430 RegisterRef UR = UA.Addr->getRegRef(DFG);
431 if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR))
432 Uses.insert(U);
433 }
434 U = UA.Addr->getSibling();
435 }
436
437 // Traverse all reached defs. This time dead defs cannot be ignored.
438 for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) {
439 auto DA = DFG.addr<DefNode *>(D);
440 NextD = DA.Addr->getSibling();
441 RegisterRef DR = DA.Addr->getRegRef(DFG);
442 // If this def is already covered, it cannot reach anything new.
443 // Similarly, skip it if it is not aliased to the interesting register.
444 if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR))
445 continue;
446 NodeSet T;
447 if (DFG.IsPreservingDef(DA)) {
448 // If it is a preserving def, do not update the set of intervening defs.
449 T = getAllReachedUses(RefRR, DA, DefRRs);
450 } else {
451 RegisterAggr NewDefRRs = DefRRs;
452 NewDefRRs.insert(DR);
453 T = getAllReachedUses(RefRR, DA, NewDefRRs);
454 }
455 Uses.insert(T.begin(), T.end());
456 }
457 return Uses;
458}
459
461 RealUseMap.clear();
462
463 NodeList Phis;
464 NodeAddr<FuncNode *> FA = DFG.getFunc();
465 NodeList Blocks = FA.Addr->members(DFG);
466 for (NodeAddr<BlockNode *> BA : Blocks) {
467 auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
468 llvm::append_range(Phis, Ps);
469 }
470
471 // phi use -> (map: reaching phi -> set of registers defined in between)
472 std::map<NodeId, std::map<NodeId, RegisterAggr>> PhiUp;
473 std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation.
474 std::unordered_map<NodeId, RegisterAggr>
475 PhiDRs; // Phi -> registers defined by it.
476
477 // Go over all phis.
478 for (NodeAddr<PhiNode *> PhiA : Phis) {
479 // Go over all defs and collect the reached uses that are non-phi uses
480 // (i.e. the "real uses").
481 RefMap &RealUses = RealUseMap[PhiA.Id];
482 NodeList PhiRefs = PhiA.Addr->members(DFG);
483
484 // Have a work queue of defs whose reached uses need to be found.
485 // For each def, add to the queue all reached (non-phi) defs.
487 NodeSet PhiDefs;
488 RegisterAggr DRs(PRI);
489 for (NodeAddr<RefNode *> R : PhiRefs) {
490 if (!DFG.IsRef<NodeAttrs::Def>(R))
491 continue;
492 DRs.insert(R.Addr->getRegRef(DFG));
493 DefQ.insert(R.Id);
494 PhiDefs.insert(R.Id);
495 }
496 PhiDRs.insert(std::make_pair(PhiA.Id, DRs));
497
498 // Collect the super-set of all possible reached uses. This set will
499 // contain all uses reached from this phi, either directly from the
500 // phi defs, or (recursively) via non-phi defs reached by the phi defs.
501 // This set of uses will later be trimmed to only contain these uses that
502 // are actually reached by the phi defs.
503 for (unsigned i = 0; i < DefQ.size(); ++i) {
504 NodeAddr<DefNode *> DA = DFG.addr<DefNode *>(DefQ[i]);
505 // Visit all reached uses. Phi defs should not really have the "dead"
506 // flag set, but check it anyway for consistency.
507 bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead;
508 NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0;
509 while (UN != 0) {
510 NodeAddr<UseNode *> A = DFG.addr<UseNode *>(UN);
511 uint16_t F = A.Addr->getFlags();
512 if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) {
513 RegisterRef R = A.Addr->getRegRef(DFG);
514 RealUses[R.Reg].insert({A.Id, R.Mask});
515 }
516 UN = A.Addr->getSibling();
517 }
518 // Visit all reached defs, and add them to the queue. These defs may
519 // override some of the uses collected here, but that will be handled
520 // later.
521 NodeId DN = DA.Addr->getReachedDef();
522 while (DN != 0) {
523 NodeAddr<DefNode *> A = DFG.addr<DefNode *>(DN);
524 for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) {
525 uint16_t Flags = NodeAddr<DefNode *>(T).Addr->getFlags();
526 // Must traverse the reached-def chain. Consider:
527 // def(D0) -> def(R0) -> def(R0) -> use(D0)
528 // The reachable use of D0 passes through a def of R0.
529 if (!(Flags & NodeAttrs::PhiRef))
530 DefQ.insert(T.Id);
531 }
532 DN = A.Addr->getSibling();
533 }
534 }
535 // Filter out these uses that appear to be reachable, but really
536 // are not. For example:
537 //
538 // R1:0 = d1
539 // = R1:0 u2 Reached by d1.
540 // R0 = d3
541 // = R1:0 u4 Still reached by d1: indirectly through
542 // the def d3.
543 // R1 = d5
544 // = R1:0 u6 Not reached by d1 (covered collectively
545 // by d3 and d5), but following reached
546 // defs and uses from d1 will lead here.
547 for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE;) {
548 // For each reached register UI->first, there is a set UI->second, of
549 // uses of it. For each such use, check if it is reached by this phi,
550 // i.e. check if the set of its reaching uses intersects the set of
551 // this phi's defs.
552 NodeRefSet Uses = UI->second;
553 UI->second.clear();
554 for (std::pair<NodeId, LaneBitmask> I : Uses) {
555 auto UA = DFG.addr<UseNode *>(I.first);
556 // Undef flag is checked above.
557 assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0);
558 RegisterRef UseR(UI->first, I.second); // Ref from Uses
559 // R = intersection of the ref from the phi and the ref from Uses
560 RegisterRef R = PhiDRs.at(PhiA.Id).intersectWith(UseR);
561 if (!R)
562 continue;
563 // Calculate the exposed part of the reached use.
564 RegisterAggr Covered(PRI);
565 for (NodeAddr<DefNode *> DA : getAllReachingDefs(R, UA)) {
566 if (PhiDefs.count(DA.Id))
567 break;
568 Covered.insert(DA.Addr->getRegRef(DFG));
569 }
570 if (RegisterRef RC = Covered.clearIn(R)) {
571 // We are updating the map for register UI->first, so we need
572 // to map RC to be expressed in terms of that register.
573 RegisterRef S = PRI.mapTo(RC, UI->first);
574 UI->second.insert({I.first, S.Mask});
575 }
576 }
577 UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI);
578 }
579
580 // If this phi reaches some "real" uses, add it to the queue for upward
581 // propagation.
582 if (!RealUses.empty())
583 PhiUQ.push_back(PhiA.Id);
584
585 // Go over all phi uses and check if the reaching def is another phi.
586 // Collect the phis that are among the reaching defs of these uses.
587 // While traversing the list of reaching defs for each phi use, accumulate
588 // the set of registers defined between this phi (PhiA) and the owner phi
589 // of the reaching def.
590 NodeSet SeenUses;
591
592 for (auto I : PhiRefs) {
593 if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id))
594 continue;
596 if (PUA.Addr->getReachingDef() == 0)
597 continue;
598
599 RegisterRef UR = PUA.Addr->getRegRef(DFG);
600 NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs);
601 RegisterAggr DefRRs(PRI);
602
603 for (NodeAddr<DefNode *> D : Ds) {
604 if (D.Addr->getFlags() & NodeAttrs::PhiRef) {
605 NodeId RP = D.Addr->getOwner(DFG).Id;
606 std::map<NodeId, RegisterAggr> &M = PhiUp[PUA.Id];
607 auto F = M.find(RP);
608 if (F == M.end())
609 M.insert(std::make_pair(RP, DefRRs));
610 else
611 F->second.insert(DefRRs);
612 }
613 DefRRs.insert(D.Addr->getRegRef(DFG));
614 }
615
616 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(PhiA, PUA))
617 SeenUses.insert(T.Id);
618 }
619 }
620
621 if (Trace) {
622 dbgs() << "Phi-up-to-phi map with intervening defs:\n";
623 for (auto I : PhiUp) {
624 dbgs() << "phi " << Print(I.first, DFG) << " -> {";
625 for (auto R : I.second)
626 dbgs() << ' ' << Print(R.first, DFG) << Print(R.second, DFG);
627 dbgs() << " }\n";
628 }
629 }
630
631 // Propagate the reached registers up in the phi chain.
632 //
633 // The following type of situation needs careful handling:
634 //
635 // phi d1<R1:0> (1)
636 // |
637 // ... d2<R1>
638 // |
639 // phi u3<R1:0> (2)
640 // |
641 // ... u4<R1>
642 //
643 // The phi node (2) defines a register pair R1:0, and reaches a "real"
644 // use u4 of just R1. The same phi node is also known to reach (upwards)
645 // the phi node (1). However, the use u4 is not reached by phi (1),
646 // because of the intervening definition d2 of R1. The data flow between
647 // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0.
648 //
649 // When propagating uses up the phi chains, get the all reaching defs
650 // for a given phi use, and traverse the list until the propagated ref
651 // is covered, or until reaching the final phi. Only assume that the
652 // reference reaches the phi in the latter case.
653
654 // The operation "clearIn" can be expensive. For a given set of intervening
655 // defs, cache the result of subtracting these defs from a given register
656 // ref.
657 using RefHash = std::hash<RegisterRef>;
658 using RefEqual = std::equal_to<RegisterRef>;
659 using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
660 std::unordered_map<RegisterAggr, SubMap> Subs;
661 auto ClearIn = [](RegisterRef RR, const RegisterAggr &Mid, SubMap &SM) {
662 if (Mid.empty())
663 return RR;
664 auto F = SM.find(RR);
665 if (F != SM.end())
666 return F->second;
667 RegisterRef S = Mid.clearIn(RR);
668 SM.insert({RR, S});
669 return S;
670 };
671
672 // Go over all phis.
673 for (unsigned i = 0; i < PhiUQ.size(); ++i) {
674 auto PA = DFG.addr<PhiNode *>(PhiUQ[i]);
675 NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG);
676 RefMap &RUM = RealUseMap[PA.Id];
677
678 for (NodeAddr<UseNode *> UA : PUs) {
679 std::map<NodeId, RegisterAggr> &PUM = PhiUp[UA.Id];
680 RegisterRef UR = UA.Addr->getRegRef(DFG);
681 for (const std::pair<const NodeId, RegisterAggr> &P : PUM) {
682 bool Changed = false;
683 const RegisterAggr &MidDefs = P.second;
684 // Collect the set PropUp of uses that are reached by the current
685 // phi PA, and are not covered by any intervening def between the
686 // currently visited use UA and the upward phi P.
687
688 if (MidDefs.hasCoverOf(UR))
689 continue;
690 if (Subs.find(MidDefs) == Subs.end()) {
691 Subs.insert({MidDefs, SubMap(1, RefHash(), RefEqual(PRI))});
692 }
693 SubMap &SM = Subs.at(MidDefs);
694
695 // General algorithm:
696 // for each (R,U) : U is use node of R, U is reached by PA
697 // if MidDefs does not cover (R,U)
698 // then add (R-MidDefs,U) to RealUseMap[P]
699 //
700 for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) {
701 RegisterRef R(T.first);
702 // The current phi (PA) could be a phi for a regmask. It could
703 // reach a whole variety of uses that are not related to the
704 // specific upward phi (P.first).
705 const RegisterAggr &DRs = PhiDRs.at(P.first);
706 if (!DRs.hasAliasOf(R))
707 continue;
708 R = PRI.mapTo(DRs.intersectWith(R), T.first);
709 for (std::pair<NodeId, LaneBitmask> V : T.second) {
710 LaneBitmask M = R.Mask & V.second;
711 if (M.none())
712 continue;
713 if (RegisterRef SS = ClearIn(RegisterRef(R.Reg, M), MidDefs, SM)) {
714 NodeRefSet &RS = RealUseMap[P.first][SS.Reg];
715 Changed |= RS.insert({V.first, SS.Mask}).second;
716 }
717 }
718 }
719
720 if (Changed)
721 PhiUQ.push_back(P.first);
722 }
723 }
724 }
725
726 if (Trace) {
727 dbgs() << "Real use map:\n";
728 for (auto I : RealUseMap) {
729 dbgs() << "phi " << Print(I.first, DFG);
730 NodeAddr<PhiNode *> PA = DFG.addr<PhiNode *>(I.first);
731 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG);
732 if (!Ds.empty()) {
733 RegisterRef RR = NodeAddr<DefNode *>(Ds[0]).Addr->getRegRef(DFG);
734 dbgs() << '<' << Print(RR, DFG) << '>';
735 } else {
736 dbgs() << "<noreg>";
737 }
738 dbgs() << " -> " << Print(I.second, DFG) << '\n';
739 }
740 }
741}
742
744 // Populate the node-to-block map. This speeds up the calculations
745 // significantly.
746 NBMap.clear();
747 for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(DFG)) {
748 MachineBasicBlock *BB = BA.Addr->getCode();
749 for (NodeAddr<InstrNode *> IA : BA.Addr->members(DFG)) {
750 for (NodeAddr<RefNode *> RA : IA.Addr->members(DFG))
751 NBMap.insert(std::make_pair(RA.Id, BB));
752 NBMap.insert(std::make_pair(IA.Id, BB));
753 }
754 }
755
756 MachineFunction &MF = DFG.getMF();
757
758 // Compute IDF first, then the inverse.
759 decltype(IIDF) IDF;
760 for (MachineBasicBlock &B : MF) {
761 auto F1 = MDF.find(&B);
762 if (F1 == MDF.end())
763 continue;
764 SetVector<MachineBasicBlock *> IDFB(F1->second.begin(), F1->second.end());
765 for (unsigned i = 0; i < IDFB.size(); ++i) {
766 auto F2 = MDF.find(IDFB[i]);
767 if (F2 != MDF.end())
768 IDFB.insert(F2->second.begin(), F2->second.end());
769 }
770 // Add B to the IDF(B). This will put B in the IIDF(B).
771 IDFB.insert(&B);
772 IDF[&B].insert(IDFB.begin(), IDFB.end());
773 }
774
775 for (auto I : IDF)
776 for (auto *S : I.second)
777 IIDF[S].insert(I.first);
778
780
781 NodeAddr<FuncNode *> FA = DFG.getFunc();
782 NodeList Blocks = FA.Addr->members(DFG);
783
784 // Build the phi live-on-entry map.
785 for (NodeAddr<BlockNode *> BA : Blocks) {
786 MachineBasicBlock *MB = BA.Addr->getCode();
787 RefMap &LON = PhiLON[MB];
788 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) {
789 for (const RefMap::value_type &S : RealUseMap[P.Id])
790 LON[S.first].insert(S.second.begin(), S.second.end());
791 }
792 }
793
794 if (Trace) {
795 dbgs() << "Phi live-on-entry map:\n";
796 for (auto &I : PhiLON)
797 dbgs() << "block #" << I.first->getNumber() << " -> "
798 << Print(I.second, DFG) << '\n';
799 }
800
801 // Build the phi live-on-exit map. Each phi node has some set of reached
802 // "real" uses. Propagate this set backwards into the block predecessors
803 // through the reaching defs of the corresponding phi uses.
804 for (NodeAddr<BlockNode *> BA : Blocks) {
805 NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
806 for (NodeAddr<PhiNode *> PA : Phis) {
807 RefMap &RUs = RealUseMap[PA.Id];
808 if (RUs.empty())
809 continue;
810
811 NodeSet SeenUses;
812 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
813 if (!SeenUses.insert(U.Id).second)
814 continue;
816 if (PUA.Addr->getReachingDef() == 0)
817 continue;
818
819 // Each phi has some set (possibly empty) of reached "real" uses,
820 // that is, uses that are part of the compiled program. Such a use
821 // may be located in some farther block, but following a chain of
822 // reaching defs will eventually lead to this phi.
823 // Any chain of reaching defs may fork at a phi node, but there
824 // will be a path upwards that will lead to this phi. Now, this
825 // chain will need to fork at this phi, since some of the reached
826 // uses may have definitions joining in from multiple predecessors.
827 // For each reached "real" use, identify the set of reaching defs
828 // coming from each predecessor P, and add them to PhiLOX[P].
829 //
830 auto PrA = DFG.addr<BlockNode *>(PUA.Addr->getPredecessor());
831 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
832
833 for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
834 // We need to visit each individual use.
835 for (std::pair<NodeId, LaneBitmask> P : RS.second) {
836 // Create a register ref corresponding to the use, and find
837 // all reaching defs starting from the phi use, and treating
838 // all related shadows as a single use cluster.
839 RegisterRef S(RS.first, P.second);
840 NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs);
841 for (NodeAddr<DefNode *> D : Ds) {
842 // Calculate the mask corresponding to the visited def.
843 RegisterAggr TA(PRI);
844 TA.insert(D.Addr->getRegRef(DFG)).intersect(S);
845 LaneBitmask TM = TA.makeRegRef().Mask;
846 LOX[S.Reg].insert({D.Id, TM});
847 }
848 }
849 }
850
851 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(PA, PUA))
852 SeenUses.insert(T.Id);
853 } // for U : phi uses
854 } // for P : Phis
855 } // for B : Blocks
856
857 if (Trace) {
858 dbgs() << "Phi live-on-exit map:\n";
859 for (auto &I : PhiLOX)
860 dbgs() << "block #" << I.first->getNumber() << " -> "
861 << Print(I.second, DFG) << '\n';
862 }
863
864 RefMap LiveIn;
865 traverse(&MF.front(), LiveIn);
866
867 // Add function live-ins to the live-in set of the function entry block.
868 LiveMap[&MF.front()].insert(DFG.getLiveIns());
869
870 if (Trace) {
871 // Dump the liveness map
872 for (MachineBasicBlock &B : MF) {
873 std::vector<RegisterRef> LV;
874 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
875 LV.push_back(RegisterRef(LI.PhysReg, LI.LaneMask));
876 llvm::sort(LV, std::less<RegisterRef>(PRI));
877 dbgs() << printMBBReference(B) << "\t rec = {";
878 for (auto I : LV)
879 dbgs() << ' ' << Print(I, DFG);
880 dbgs() << " }\n";
881 // dbgs() << "\tcomp = " << Print(LiveMap[&B], DFG) << '\n';
882
883 LV.clear();
884 for (RegisterRef RR : LiveMap[&B].refs())
885 LV.push_back(RR);
886 llvm::sort(LV, std::less<RegisterRef>(PRI));
887 dbgs() << "\tcomp = {";
888 for (auto I : LV)
889 dbgs() << ' ' << Print(I, DFG);
890 dbgs() << " }\n";
891 }
892 }
893}
894
896 for (auto &B : DFG.getMF()) {
897 // Remove all live-ins.
898 std::vector<unsigned> T;
899 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
900 T.push_back(LI.PhysReg);
901 for (auto I : T)
902 B.removeLiveIn(I);
903 // Add the newly computed live-ins.
904 const RegisterAggr &LiveIns = LiveMap[&B];
905 for (RegisterRef R : LiveIns.refs())
906 B.addLiveIn({MCPhysReg(R.Reg), R.Mask});
907 }
908}
909
911 for (auto &B : DFG.getMF())
912 resetKills(&B);
913}
914
916 auto CopyLiveIns = [this](MachineBasicBlock *B, BitVector &LV) -> void {
917 for (auto I : B->liveins()) {
918 MCSubRegIndexIterator S(I.PhysReg, &TRI);
919 if (!S.isValid()) {
920 LV.set(I.PhysReg);
921 continue;
922 }
923 do {
925 if ((M & I.LaneMask).any())
926 LV.set(S.getSubReg());
927 ++S;
928 } while (S.isValid());
929 }
930 };
931
932 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
933 CopyLiveIns(B, LiveIn);
934 for (auto *SI : B->successors())
935 CopyLiveIns(SI, Live);
936
937 for (MachineInstr &MI : llvm::reverse(*B)) {
938 if (MI.isDebugInstr())
939 continue;
940
941 MI.clearKillInfo();
942 for (auto &Op : MI.all_defs()) {
943 // An implicit def of a super-register may not necessarily start a
944 // live range of it, since an implicit use could be used to keep parts
945 // of it live. Instead of analyzing the implicit operands, ignore
946 // implicit defs.
947 if (Op.isImplicit())
948 continue;
949 Register R = Op.getReg();
950 if (!R.isPhysical())
951 continue;
952 for (MCPhysReg SR : TRI.subregs_inclusive(R))
953 Live.reset(SR);
954 }
955 for (auto &Op : MI.all_uses()) {
956 if (Op.isUndef())
957 continue;
958 Register R = Op.getReg();
959 if (!R.isPhysical())
960 continue;
961 bool IsLive = false;
962 for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) {
963 if (!Live[*AR])
964 continue;
965 IsLive = true;
966 break;
967 }
968 if (!IsLive)
969 Op.setIsKill(true);
970 for (MCPhysReg SR : TRI.subregs_inclusive(R))
971 Live.set(SR);
972 }
973 }
974}
975
976// Helper function to obtain the basic block containing the reaching def
977// of the given use.
978MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
979 auto F = NBMap.find(RN);
980 if (F != NBMap.end())
981 return F->second;
982 llvm_unreachable("Node id not in map");
983}
984
985void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
986 // The LiveIn map, for each (physical) register, contains the set of live
987 // reaching defs of that register that are live on entry to the associated
988 // block.
989
990 // The summary of the traversal algorithm:
991 //
992 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
993 // and (U \in IDF(B) or B dom U).
994 //
995 // for (C : children) {
996 // LU = {}
997 // traverse(C, LU)
998 // LiveUses += LU
999 // }
1000 //
1001 // LiveUses -= Defs(B);
1002 // LiveUses += UpwardExposedUses(B);
1003 // for (C : IIDF[B])
1004 // for (U : LiveUses)
1005 // if (Rdef(U) dom C)
1006 // C.addLiveIn(U)
1007 //
1008
1009 // Go up the dominator tree (depth-first).
1010 MachineDomTreeNode *N = MDT.getNode(B);
1011 for (auto *I : *N) {
1012 RefMap L;
1013 MachineBasicBlock *SB = I->getBlock();
1014 traverse(SB, L);
1015
1016 for (auto S : L)
1017 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1018 }
1019
1020 if (Trace) {
1021 dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__
1022 << " after recursion into: {";
1023 for (auto *I : *N)
1024 dbgs() << ' ' << I->getBlock()->getNumber();
1025 dbgs() << " }\n";
1026 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1027 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1028 }
1029
1030 // Add reaching defs of phi uses that are live on exit from this block.
1031 RefMap &PUs = PhiLOX[B];
1032 for (auto &S : PUs)
1033 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1034
1035 if (Trace) {
1036 dbgs() << "after LOX\n";
1037 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1038 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1039 }
1040
1041 // The LiveIn map at this point has all defs that are live-on-exit from B,
1042 // as if they were live-on-entry to B. First, we need to filter out all
1043 // defs that are present in this block. Then we will add reaching defs of
1044 // all upward-exposed uses.
1045
1046 // To filter out the defs, first make a copy of LiveIn, and then re-populate
1047 // LiveIn with the defs that should remain.
1048 RefMap LiveInCopy = LiveIn;
1049 LiveIn.clear();
1050
1051 for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) {
1052 RegisterRef LRef(LE.first);
1053 NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled.
1054 const NodeRefSet &OldDefs = LE.second;
1055 for (NodeRef OR : OldDefs) {
1056 // R is a def node that was live-on-exit
1057 auto DA = DFG.addr<DefNode *>(OR.first);
1058 NodeAddr<InstrNode *> IA = DA.Addr->getOwner(DFG);
1059 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(DFG);
1060 if (B != BA.Addr->getCode()) {
1061 // Defs from a different block need to be preserved. Defs from this
1062 // block will need to be processed further, except for phi defs, the
1063 // liveness of which is handled through the PhiLON/PhiLOX maps.
1064 NewDefs.insert(OR);
1065 continue;
1066 }
1067
1068 // Defs from this block need to stop the liveness from being
1069 // propagated upwards. This only applies to non-preserving defs,
1070 // and to the parts of the register actually covered by those defs.
1071 // (Note that phi defs should always be preserving.)
1072 RegisterAggr RRs(PRI);
1073 LRef.Mask = OR.second;
1074
1075 if (!DFG.IsPreservingDef(DA)) {
1076 assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
1077 // DA is a non-phi def that is live-on-exit from this block, and
1078 // that is also located in this block. LRef is a register ref
1079 // whose use this def reaches. If DA covers LRef, then no part
1080 // of LRef is exposed upwards.A
1081 if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1082 continue;
1083 }
1084
1085 // DA itself was not sufficient to cover LRef. In general, it is
1086 // the last in a chain of aliased defs before the exit from this block.
1087 // There could be other defs in this block that are a part of that
1088 // chain. Check that now: accumulate the registers from these defs,
1089 // and if they all together cover LRef, it is not live-on-entry.
1090 for (NodeAddr<DefNode *> TA : getAllReachingDefs(DA)) {
1091 // DefNode -> InstrNode -> BlockNode.
1092 NodeAddr<InstrNode *> ITA = TA.Addr->getOwner(DFG);
1093 NodeAddr<BlockNode *> BTA = ITA.Addr->getOwner(DFG);
1094 // Reaching defs are ordered in the upward direction.
1095 if (BTA.Addr->getCode() != B) {
1096 // We have reached past the beginning of B, and the accumulated
1097 // registers are not covering LRef. The first def from the
1098 // upward chain will be live.
1099 // Subtract all accumulated defs (RRs) from LRef.
1100 RegisterRef T = RRs.clearIn(LRef);
1101 assert(T);
1102 NewDefs.insert({TA.Id, T.Mask});
1103 break;
1104 }
1105
1106 // TA is in B. Only add this def to the accumulated cover if it is
1107 // not preserving.
1108 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
1109 RRs.insert(TA.Addr->getRegRef(DFG));
1110 // If this is enough to cover LRef, then stop.
1111 if (RRs.hasCoverOf(LRef))
1112 break;
1113 }
1114 }
1115 }
1116
1117 emptify(LiveIn);
1118
1119 if (Trace) {
1120 dbgs() << "after defs in block\n";
1121 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1122 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1123 }
1124
1125 // Scan the block for upward-exposed uses and add them to the tracking set.
1126 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) {
1127 NodeAddr<InstrNode *> IA = I;
1128 if (IA.Addr->getKind() != NodeAttrs::Stmt)
1129 continue;
1130 for (NodeAddr<UseNode *> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
1131 if (UA.Addr->getFlags() & NodeAttrs::Undef)
1132 continue;
1133 RegisterRef RR = UA.Addr->getRegRef(DFG);
1134 for (NodeAddr<DefNode *> D : getAllReachingDefs(UA))
1135 if (getBlockWithRef(D.Id) != B)
1136 LiveIn[RR.Reg].insert({D.Id, RR.Mask});
1137 }
1138 }
1139
1140 if (Trace) {
1141 dbgs() << "after uses in block\n";
1142 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1143 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1144 }
1145
1146 // Phi uses should not be propagated up the dominator tree, since they
1147 // are not dominated by their corresponding reaching defs.
1148 RegisterAggr &Local = LiveMap[B];
1149 RefMap &LON = PhiLON[B];
1150 for (auto &R : LON) {
1151 LaneBitmask M;
1152 for (auto P : R.second)
1153 M |= P.second;
1154 Local.insert(RegisterRef(R.first, M));
1155 }
1156
1157 if (Trace) {
1158 dbgs() << "after phi uses in block\n";
1159 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1160 dbgs() << " Local: " << Print(Local, DFG) << '\n';
1161 }
1162
1163 for (auto *C : IIDF[B]) {
1164 RegisterAggr &LiveC = LiveMap[C];
1165 for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn)
1166 for (auto R : S.second)
1167 if (MDT.properlyDominates(getBlockWithRef(R.first), C))
1168 LiveC.insert(RegisterRef(S.first, R.second));
1169 }
1170}
1171
1172void Liveness::emptify(RefMap &M) {
1173 for (auto I = M.begin(), E = M.end(); I != E;)
1174 I = I->second.empty() ? M.erase(I) : std::next(I);
1175}
1176
1177} // namespace llvm::rdf
MachineBasicBlock & MBB
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:496
Rewrite Partial Register Uses
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
const char LLVMTargetMachineRef TM
static cl::opt< unsigned > MaxRecNest("rdf-liveness-max-rec", cl::init(25), cl::Hidden, cl::desc("Maximum recursion level"))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool IsDead
SI optimize exec mask operations pre RA
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Base class for the actual dominator tree node.
MCRegAliasIterator enumerates all registers aliasing Reg.
iterator_range< MCSubRegIterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
bool isValid() const
Returns true if this iterator is not yet at the end.
unsigned getSubRegIndex() const
Returns sub-register index of the current sub-register.
MCRegister getSubReg() const
Returns current sub-register.
iterator find(MachineBasicBlock *B)
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
const MachineBasicBlock & front() const
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
unsigned count(SUnit *SU) const
bool insert(SUnit *SU)
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
self_iterator getIterator()
Definition: ilist_node.h:82
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
Print(const T &, const DataFlowGraph &) -> Print< T >
uint32_t NodeId
Definition: RDFGraph.h:262
NodeAddr< BlockNode * > Block
Definition: RDFGraph.h:392
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:45
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
std::set< NodeId > NodeSet
Definition: RDFGraph.h:551
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1652
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2021
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
Pair of physical register and lane mask.
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:520
const RegisterAggr & getLiveIns() const
Definition: RDFGraph.h:700
static bool IsDef(const Node BA)
Definition: RDFGraph.h:825
Func getFunc() const
Definition: RDFGraph.h:693
static bool IsPreservingDef(const Def DA)
Definition: RDFGraph.h:840
NodeList getRelatedRefs(Instr IA, Ref RA) const
Definition: RDFGraph.cpp:1136
MachineFunction & getMF() const
Definition: RDFGraph.h:694
static bool IsRef(const Node BA)
Definition: RDFGraph.h:817
static bool IsUse(const Node BA)
Definition: RDFGraph.h:830
static bool IsCode(const Node BA)
Definition: RDFGraph.h:821
Block findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:799
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:689
Block findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const
Definition: RDFGraph.cpp:569
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
std::unordered_set< NodeRef > NodeRefSet
Definition: RDFLiveness.h:59
NodeAddr< RefNode * > getNearestAliasedRef(RegisterRef RefRR, NodeAddr< InstrNode * > IA)
Find the nearest ref node aliased to RefRR, going upwards in the data flow, starting from the instruc...
detail::NodeRef NodeRef
Definition: RDFLiveness.h:58
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
std::unordered_map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:60
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
bool alias(RegisterRef RA, RegisterRef RB) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
iterator_range< ref_iterator > refs() const
Definition: RDFRegisters.h:276
RegisterAggr & insert(RegisterRef RR)
RegisterRef clearIn(RegisterRef RR) const
bool hasAliasOf(RegisterRef RR) const
RegisterRef intersectWith(RegisterRef RR) const
bool hasCoverOf(RegisterRef RR) const
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
Definition: RDFRegisters.h:220