LLVM 22.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;
188 NodeAddr<InstrNode *> OA = DFG.addr<InstrNode *>(A);
189 NodeAddr<InstrNode *> OB = DFG.addr<InstrNode *>(B);
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.
373 for (NodeAddr<InstrNode *> I : make_range(B, 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 auto [F, Inserted] = PhiUp[PUA.Id].try_emplace(RP, DefRRs);
607 if (!Inserted)
608 F->second.insert(DefRRs);
609 }
610 DefRRs.insert(D.Addr->getRegRef(DFG));
611 }
612
613 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(PhiA, PUA))
614 SeenUses.insert(T.Id);
615 }
616 }
617
618 if (Trace) {
619 dbgs() << "Phi-up-to-phi map with intervening defs:\n";
620 for (auto I : PhiUp) {
621 dbgs() << "phi " << Print(I.first, DFG) << " -> {";
622 for (auto R : I.second)
623 dbgs() << ' ' << Print(R.first, DFG) << Print(R.second, DFG);
624 dbgs() << " }\n";
625 }
626 }
627
628 // Propagate the reached registers up in the phi chain.
629 //
630 // The following type of situation needs careful handling:
631 //
632 // phi d1<R1:0> (1)
633 // |
634 // ... d2<R1>
635 // |
636 // phi u3<R1:0> (2)
637 // |
638 // ... u4<R1>
639 //
640 // The phi node (2) defines a register pair R1:0, and reaches a "real"
641 // use u4 of just R1. The same phi node is also known to reach (upwards)
642 // the phi node (1). However, the use u4 is not reached by phi (1),
643 // because of the intervening definition d2 of R1. The data flow between
644 // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0.
645 //
646 // When propagating uses up the phi chains, get the all reaching defs
647 // for a given phi use, and traverse the list until the propagated ref
648 // is covered, or until reaching the final phi. Only assume that the
649 // reference reaches the phi in the latter case.
650
651 // The operation "clearIn" can be expensive. For a given set of intervening
652 // defs, cache the result of subtracting these defs from a given register
653 // ref.
654 using RefHash = std::hash<RegisterRef>;
655 using RefEqual = RegisterRefEqualTo;
656 using SubMap =
657 std::unordered_map<RegisterRef, RegisterRef, RefHash, RefEqual>;
658 std::unordered_map<RegisterAggr, SubMap> Subs;
659 auto ClearIn = [](RegisterRef RR, const RegisterAggr &Mid, SubMap &SM) {
660 if (Mid.empty())
661 return RR;
662 auto F = SM.find(RR);
663 if (F != SM.end())
664 return F->second;
665 RegisterRef S = Mid.clearIn(RR);
666 SM.insert({RR, S});
667 return S;
668 };
669
670 // Go over all phis.
671 for (unsigned i = 0; i < PhiUQ.size(); ++i) {
672 auto PA = DFG.addr<PhiNode *>(PhiUQ[i]);
673 NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG);
674 RefMap &RUM = RealUseMap[PA.Id];
675
676 for (NodeAddr<UseNode *> UA : PUs) {
677 std::map<NodeId, RegisterAggr> &PUM = PhiUp[UA.Id];
678 RegisterRef UR = UA.Addr->getRegRef(DFG);
679 for (const std::pair<const NodeId, RegisterAggr> &P : PUM) {
680 bool Changed = false;
681 const RegisterAggr &MidDefs = P.second;
682 // Collect the set PropUp of uses that are reached by the current
683 // phi PA, and are not covered by any intervening def between the
684 // currently visited use UA and the upward phi P.
685
686 if (MidDefs.hasCoverOf(UR))
687 continue;
688 SubMap &SM = Subs.try_emplace(MidDefs, 1, RefHash(), RefEqual(PRI))
689 .first->second;
690
691 // General algorithm:
692 // for each (R,U) : U is use node of R, U is reached by PA
693 // if MidDefs does not cover (R,U)
694 // then add (R-MidDefs,U) to RealUseMap[P]
695 //
696 for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) {
697 RegisterRef R(T.first);
698 // The current phi (PA) could be a phi for a regmask. It could
699 // reach a whole variety of uses that are not related to the
700 // specific upward phi (P.first).
701 const RegisterAggr &DRs = PhiDRs.at(P.first);
702 if (!DRs.hasAliasOf(R))
703 continue;
704 R = PRI.mapTo(DRs.intersectWith(R), T.first);
705 for (std::pair<NodeId, LaneBitmask> V : T.second) {
706 LaneBitmask M = R.Mask & V.second;
707 if (M.none())
708 continue;
709 if (RegisterRef SS = ClearIn(RegisterRef(R.Reg, M), MidDefs, SM)) {
710 NodeRefSet &RS = RealUseMap[P.first][SS.Reg];
711 Changed |= RS.insert({V.first, SS.Mask}).second;
712 }
713 }
714 }
715
716 if (Changed)
717 PhiUQ.push_back(P.first);
718 }
719 }
720 }
721
722 if (Trace) {
723 dbgs() << "Real use map:\n";
724 for (auto I : RealUseMap) {
725 dbgs() << "phi " << Print(I.first, DFG);
726 NodeAddr<PhiNode *> PA = DFG.addr<PhiNode *>(I.first);
727 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG);
728 if (!Ds.empty()) {
729 RegisterRef RR = NodeAddr<DefNode *>(Ds[0]).Addr->getRegRef(DFG);
730 dbgs() << '<' << Print(RR, DFG) << '>';
731 } else {
732 dbgs() << "<noreg>";
733 }
734 dbgs() << " -> " << Print(I.second, DFG) << '\n';
735 }
736 }
737}
738
740 // Populate the node-to-block map. This speeds up the calculations
741 // significantly.
742 NBMap.clear();
743 for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(DFG)) {
744 MachineBasicBlock *BB = BA.Addr->getCode();
745 for (NodeAddr<InstrNode *> IA : BA.Addr->members(DFG)) {
746 for (NodeAddr<RefNode *> RA : IA.Addr->members(DFG))
747 NBMap.insert(std::make_pair(RA.Id, BB));
748 NBMap.insert(std::make_pair(IA.Id, BB));
749 }
750 }
751
752 MachineFunction &MF = DFG.getMF();
753
754 // Compute IDF first, then the inverse.
755 decltype(IIDF) IDF;
756 for (MachineBasicBlock &B : MF) {
757 auto F1 = MDF.find(&B);
758 if (F1 == MDF.end())
759 continue;
761 for (unsigned i = 0; i < IDFB.size(); ++i) {
762 auto F2 = MDF.find(IDFB[i]);
763 if (F2 != MDF.end())
764 IDFB.insert_range(F2->second);
765 }
766 // Add B to the IDF(B). This will put B in the IIDF(B).
767 IDFB.insert(&B);
768 IDF[&B].insert(IDFB.begin(), IDFB.end());
769 }
770
771 for (auto I : IDF)
772 for (auto *S : I.second)
773 IIDF[S].insert(I.first);
774
776
777 NodeAddr<FuncNode *> FA = DFG.getFunc();
778 NodeList Blocks = FA.Addr->members(DFG);
779
780 // Build the phi live-on-entry map.
781 for (NodeAddr<BlockNode *> BA : Blocks) {
782 MachineBasicBlock *MB = BA.Addr->getCode();
783 RefMap &LON = PhiLON[MB];
784 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) {
785 for (const RefMap::value_type &S : RealUseMap[P.Id])
786 LON[S.first].insert(S.second.begin(), S.second.end());
787 }
788 }
789
790 if (Trace) {
791 dbgs() << "Phi live-on-entry map:\n";
792 for (auto &I : PhiLON)
793 dbgs() << "block #" << I.first->getNumber() << " -> "
794 << Print(I.second, DFG) << '\n';
795 }
796
797 // Build the phi live-on-exit map. Each phi node has some set of reached
798 // "real" uses. Propagate this set backwards into the block predecessors
799 // through the reaching defs of the corresponding phi uses.
800 for (NodeAddr<BlockNode *> BA : Blocks) {
801 NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
802 for (NodeAddr<PhiNode *> PA : Phis) {
803 RefMap &RUs = RealUseMap[PA.Id];
804 if (RUs.empty())
805 continue;
806
807 NodeSet SeenUses;
808 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
809 if (!SeenUses.insert(U.Id).second)
810 continue;
812 if (PUA.Addr->getReachingDef() == 0)
813 continue;
814
815 // Each phi has some set (possibly empty) of reached "real" uses,
816 // that is, uses that are part of the compiled program. Such a use
817 // may be located in some farther block, but following a chain of
818 // reaching defs will eventually lead to this phi.
819 // Any chain of reaching defs may fork at a phi node, but there
820 // will be a path upwards that will lead to this phi. Now, this
821 // chain will need to fork at this phi, since some of the reached
822 // uses may have definitions joining in from multiple predecessors.
823 // For each reached "real" use, identify the set of reaching defs
824 // coming from each predecessor P, and add them to PhiLOX[P].
825 //
826 auto PrA = DFG.addr<BlockNode *>(PUA.Addr->getPredecessor());
827 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
828
829 for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
830 // We need to visit each individual use.
831 for (std::pair<NodeId, LaneBitmask> P : RS.second) {
832 // Create a register ref corresponding to the use, and find
833 // all reaching defs starting from the phi use, and treating
834 // all related shadows as a single use cluster.
835 RegisterRef S(RS.first, P.second);
836 NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs);
837 for (NodeAddr<DefNode *> D : Ds) {
838 // Calculate the mask corresponding to the visited def.
839 RegisterAggr TA(PRI);
840 TA.insert(D.Addr->getRegRef(DFG)).intersect(S);
841 LaneBitmask TM = TA.makeRegRef().Mask;
842 LOX[S.Reg].insert({D.Id, TM});
843 }
844 }
845 }
846
847 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(PA, PUA))
848 SeenUses.insert(T.Id);
849 } // for U : phi uses
850 } // for P : Phis
851 } // for B : Blocks
852
853 if (Trace) {
854 dbgs() << "Phi live-on-exit map:\n";
855 for (auto &I : PhiLOX)
856 dbgs() << "block #" << I.first->getNumber() << " -> "
857 << Print(I.second, DFG) << '\n';
858 }
859
860 RefMap LiveIn;
861 traverse(&MF.front(), LiveIn);
862
863 // Add function live-ins to the live-in set of the function entry block.
864 LiveMap[&MF.front()].insert(DFG.getLiveIns());
865
866 if (Trace) {
867 // Dump the liveness map
868 for (MachineBasicBlock &B : MF) {
869 std::vector<RegisterRef> LV;
870 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
871 LV.push_back(RegisterRef(LI.PhysReg, LI.LaneMask));
872 llvm::sort(LV, RegisterRefLess(PRI));
873 dbgs() << printMBBReference(B) << "\t rec = {";
874 for (auto I : LV)
875 dbgs() << ' ' << Print(I, DFG);
876 dbgs() << " }\n";
877 // dbgs() << "\tcomp = " << Print(LiveMap[&B], DFG) << '\n';
878
879 LV.clear();
880 for (RegisterRef RR : LiveMap[&B].refs())
881 LV.push_back(RR);
882 llvm::sort(LV, RegisterRefLess(PRI));
883 dbgs() << "\tcomp = {";
884 for (auto I : LV)
885 dbgs() << ' ' << Print(I, DFG);
886 dbgs() << " }\n";
887 }
888 }
889}
890
892 for (auto &B : DFG.getMF()) {
893 // Remove all live-ins.
894 std::vector<MCRegister> T;
895 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
896 T.push_back(LI.PhysReg);
897 for (auto I : T)
898 B.removeLiveIn(I);
899 // Add the newly computed live-ins.
900 const RegisterAggr &LiveIns = LiveMap[&B];
901 for (RegisterRef R : LiveIns.refs())
902 B.addLiveIn({MCPhysReg(R.Reg), R.Mask});
903 }
904}
905
907 for (auto &B : DFG.getMF())
908 resetKills(&B);
909}
910
912 auto CopyLiveIns = [this](MachineBasicBlock *B, BitVector &LV) -> void {
913 for (auto I : B->liveins()) {
914 MCSubRegIndexIterator S(I.PhysReg, &TRI);
915 if (!S.isValid()) {
916 LV.set(I.PhysReg.id());
917 continue;
918 }
919 do {
920 LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex());
921 if ((M & I.LaneMask).any())
922 LV.set(S.getSubReg());
923 ++S;
924 } while (S.isValid());
925 }
926 };
927
928 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
929 CopyLiveIns(B, LiveIn);
930 for (auto *SI : B->successors())
931 CopyLiveIns(SI, Live);
932
933 for (MachineInstr &MI : llvm::reverse(*B)) {
934 if (MI.isDebugInstr())
935 continue;
936
937 MI.clearKillInfo();
938 for (auto &Op : MI.all_defs()) {
939 // An implicit def of a super-register may not necessarily start a
940 // live range of it, since an implicit use could be used to keep parts
941 // of it live. Instead of analyzing the implicit operands, ignore
942 // implicit defs.
943 if (Op.isImplicit())
944 continue;
945 Register R = Op.getReg();
946 if (!R.isPhysical())
947 continue;
948 for (MCPhysReg SR : TRI.subregs_inclusive(R))
949 Live.reset(SR);
950 }
951 for (auto &Op : MI.all_uses()) {
952 if (Op.isUndef())
953 continue;
954 Register R = Op.getReg();
955 if (!R.isPhysical())
956 continue;
957 bool IsLive = false;
958 for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) {
959 if (!Live[(*AR).id()])
960 continue;
961 IsLive = true;
962 break;
963 }
964 if (!IsLive)
965 Op.setIsKill(true);
966 for (MCPhysReg SR : TRI.subregs_inclusive(R))
967 Live.set(SR);
968 }
969 }
970}
971
972// Helper function to obtain the basic block containing the reaching def
973// of the given use.
974MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
975 auto F = NBMap.find(RN);
976 if (F != NBMap.end())
977 return F->second;
978 llvm_unreachable("Node id not in map");
979}
980
981void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
982 // The LiveIn map, for each (physical) register, contains the set of live
983 // reaching defs of that register that are live on entry to the associated
984 // block.
985
986 // The summary of the traversal algorithm:
987 //
988 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
989 // and (U \in IDF(B) or B dom U).
990 //
991 // for (C : children) {
992 // LU = {}
993 // traverse(C, LU)
994 // LiveUses += LU
995 // }
996 //
997 // LiveUses -= Defs(B);
998 // LiveUses += UpwardExposedUses(B);
999 // for (C : IIDF[B])
1000 // for (U : LiveUses)
1001 // if (Rdef(U) dom C)
1002 // C.addLiveIn(U)
1003 //
1004
1005 // Go up the dominator tree (depth-first).
1006 MachineDomTreeNode *N = MDT.getNode(B);
1007 for (auto *I : *N) {
1008 RefMap L;
1009 MachineBasicBlock *SB = I->getBlock();
1010 traverse(SB, L);
1011
1012 for (auto S : L)
1013 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1014 }
1015
1016 if (Trace) {
1017 dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__
1018 << " after recursion into: {";
1019 for (auto *I : *N)
1020 dbgs() << ' ' << I->getBlock()->getNumber();
1021 dbgs() << " }\n";
1022 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1023 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1024 }
1025
1026 // Add reaching defs of phi uses that are live on exit from this block.
1027 RefMap &PUs = PhiLOX[B];
1028 for (auto &S : PUs)
1029 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1030
1031 if (Trace) {
1032 dbgs() << "after LOX\n";
1033 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1034 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1035 }
1036
1037 // The LiveIn map at this point has all defs that are live-on-exit from B,
1038 // as if they were live-on-entry to B. First, we need to filter out all
1039 // defs that are present in this block. Then we will add reaching defs of
1040 // all upward-exposed uses.
1041
1042 // To filter out the defs, first make a copy of LiveIn, and then re-populate
1043 // LiveIn with the defs that should remain.
1044 RefMap LiveInCopy = LiveIn;
1045 LiveIn.clear();
1046
1047 for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) {
1048 RegisterRef LRef(LE.first);
1049 NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled.
1050 const NodeRefSet &OldDefs = LE.second;
1051 for (NodeRef OR : OldDefs) {
1052 // R is a def node that was live-on-exit
1053 auto DA = DFG.addr<DefNode *>(OR.first);
1054 NodeAddr<InstrNode *> IA = DA.Addr->getOwner(DFG);
1055 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(DFG);
1056 if (B != BA.Addr->getCode()) {
1057 // Defs from a different block need to be preserved. Defs from this
1058 // block will need to be processed further, except for phi defs, the
1059 // liveness of which is handled through the PhiLON/PhiLOX maps.
1060 NewDefs.insert(OR);
1061 continue;
1062 }
1063
1064 // Defs from this block need to stop the liveness from being
1065 // propagated upwards. This only applies to non-preserving defs,
1066 // and to the parts of the register actually covered by those defs.
1067 // (Note that phi defs should always be preserving.)
1068 RegisterAggr RRs(PRI);
1069 LRef.Mask = OR.second;
1070
1071 if (!DFG.IsPreservingDef(DA)) {
1072 assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
1073 // DA is a non-phi def that is live-on-exit from this block, and
1074 // that is also located in this block. LRef is a register ref
1075 // whose use this def reaches. If DA covers LRef, then no part
1076 // of LRef is exposed upwards.A
1077 if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1078 continue;
1079 }
1080
1081 // DA itself was not sufficient to cover LRef. In general, it is
1082 // the last in a chain of aliased defs before the exit from this block.
1083 // There could be other defs in this block that are a part of that
1084 // chain. Check that now: accumulate the registers from these defs,
1085 // and if they all together cover LRef, it is not live-on-entry.
1086 for (NodeAddr<DefNode *> TA : getAllReachingDefs(DA)) {
1087 // DefNode -> InstrNode -> BlockNode.
1088 NodeAddr<InstrNode *> ITA = TA.Addr->getOwner(DFG);
1089 NodeAddr<BlockNode *> BTA = ITA.Addr->getOwner(DFG);
1090 // Reaching defs are ordered in the upward direction.
1091 if (BTA.Addr->getCode() != B) {
1092 // We have reached past the beginning of B, and the accumulated
1093 // registers are not covering LRef. The first def from the
1094 // upward chain will be live.
1095 // Subtract all accumulated defs (RRs) from LRef.
1096 RegisterRef T = RRs.clearIn(LRef);
1097 assert(T);
1098 NewDefs.insert({TA.Id, T.Mask});
1099 break;
1100 }
1101
1102 // TA is in B. Only add this def to the accumulated cover if it is
1103 // not preserving.
1104 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
1105 RRs.insert(TA.Addr->getRegRef(DFG));
1106 // If this is enough to cover LRef, then stop.
1107 if (RRs.hasCoverOf(LRef))
1108 break;
1109 }
1110 }
1111 }
1112
1113 emptify(LiveIn);
1114
1115 if (Trace) {
1116 dbgs() << "after defs in block\n";
1117 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1118 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1119 }
1120
1121 // Scan the block for upward-exposed uses and add them to the tracking set.
1122 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) {
1123 NodeAddr<InstrNode *> IA = I;
1124 if (IA.Addr->getKind() != NodeAttrs::Stmt)
1125 continue;
1126 for (NodeAddr<UseNode *> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
1127 if (UA.Addr->getFlags() & NodeAttrs::Undef)
1128 continue;
1129 RegisterRef RR = UA.Addr->getRegRef(DFG);
1130 for (NodeAddr<DefNode *> D : getAllReachingDefs(UA))
1131 if (getBlockWithRef(D.Id) != B)
1132 LiveIn[RR.Reg].insert({D.Id, RR.Mask});
1133 }
1134 }
1135
1136 if (Trace) {
1137 dbgs() << "after uses in block\n";
1138 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1139 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1140 }
1141
1142 // Phi uses should not be propagated up the dominator tree, since they
1143 // are not dominated by their corresponding reaching defs.
1144 RegisterAggr &Local = LiveMap[B];
1145 RefMap &LON = PhiLON[B];
1146 for (auto &R : LON) {
1147 LaneBitmask M;
1148 for (auto P : R.second)
1149 M |= P.second;
1150 Local.insert(RegisterRef(R.first, M));
1151 }
1152
1153 if (Trace) {
1154 dbgs() << "after phi uses in block\n";
1155 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1156 dbgs() << " Local: " << Print(Local, DFG) << '\n';
1157 }
1158
1159 for (auto *C : IIDF[B]) {
1160 RegisterAggr &LiveC = LiveMap[C];
1161 for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn)
1162 for (auto R : S.second)
1163 if (MDT.properlyDominates(getBlockWithRef(R.first), C))
1164 LiveC.insert(RegisterRef(S.first, R.second));
1165 }
1166}
1167
1168void Liveness::emptify(RefMap &M) {
1169 for (auto I = M.begin(), E = M.end(); I != E;)
1170 I = I->second.empty() ? M.erase(I) : std::next(I);
1171}
1172
1173} // namespace llvm::rdf
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
This file implements the BitVector class.
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")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
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 T
#define P(N)
static cl::opt< unsigned > MaxRecNest("rdf-liveness-max-rec", cl::init(25), cl::Hidden, cl::desc("Maximum recursion level"))
Remove Loads Into Fake Uses
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.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
BitVector & reset()
Definition BitVector.h:411
BitVector & set()
Definition BitVector.h:370
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:167
iterator end()
Definition DenseMap.h:81
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:222
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
MCRegAliasIterator enumerates all registers aliasing Reg.
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.
const MachineBasicBlock & front() const
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
const MachineBasicBlock * getParent() 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:59
size_type size() const
Determine the number of elements in the SetVector.
Definition SetVector.h:102
void insert_range(Range &&R)
Definition SetVector.h:175
iterator end()
Get an iterator to the end of the SetVector.
Definition SetVector.h:111
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition SetVector.h:105
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:150
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:133
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition SmallSet.h:175
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:183
self_iterator getIterator()
Definition ilist_node.h:123
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
Changed
#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)
NodeAddr< BlockNode * > Block
Definition RDFGraph.h:392
Print(const T &, const DataFlowGraph &) -> Print< T >
uint32_t NodeId
Definition RDFGraph.h:262
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition RDFGraph.cpp:44
std::set< NodeId > NodeSet
Definition RDFGraph.h:551
SmallVector< Node, 4 > NodeList
Definition RDFGraph.h:550
This is an optimization pass for GlobalISel generic memory operations.
constexpr from_range_t from_range
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 range R to container C.
Definition STLExtras.h:2116
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1624
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition MCRegister.h:21
DWARFExpression::Operation Op
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:2100
LLVM_ABI 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.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
Pair of physical register and lane mask.
NodeAddr< T > addr(NodeId N) const
Definition RDFGraph.h:689
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)
NodeId getSibling() const
Definition RDFGraph.h:569
iterator_range< ref_iterator > refs() const
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)