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"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineDominanceFrontier.h"
32#include "llvm/CodeGen/MachineDominators.h"
33#include "llvm/CodeGen/MachineFunction.h"
34#include "llvm/CodeGen/MachineInstr.h"
35#include "llvm/CodeGen/RDFGraph.h"
36#include "llvm/CodeGen/RDFLiveness.h"
37#include "llvm/CodeGen/RDFRegisters.h"
38#include "llvm/CodeGen/TargetRegisterInfo.h"
39#include "llvm/MC/LaneBitmask.h"
40#include "llvm/MC/MCRegisterInfo.h"
41#include "llvm/Support/CommandLine.h"
42#include "llvm/Support/ErrorHandling.h"
43#include "llvm/Support/raw_ostream.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(Val: 25),
56 cl::Hidden,
57 cl::desc("Maximum recursion level"));
58
59namespace llvm::rdf {
60
61raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P) {
62 OS << '{';
63 for (const auto &I : P.Obj) {
64 OS << ' ' << printReg(Reg: I.first, TRI: &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
104NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
105 NodeAddr<RefNode *> RefA, bool TopShadows,
106 bool FullChain,
107 const RegisterAggr &DefRRs) {
108 NodeList RDefs; // Return value.
109 SetVector<NodeId> DefQ;
110 DenseMap<MachineInstr *, uint32_t> OrdMap;
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 *>(N: Start);
125 if (NodeId RD = SNA.Addr->getReachingDef())
126 DefQ.insert(X: RD);
127 if (TopShadows) {
128 for (auto S : DFG.getRelatedRefs(IA: RefA.Addr->getOwner(G: DFG), RA: RefA))
129 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef())
130 DefQ.insert(X: 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 *>(N: 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(G: DFG);
145 if (!DFG.IsPreservingDef(DA: TA))
146 if (RegisterAggr::isCoverOf(RA: RR, RB: 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(IA: TA.Addr->getOwner(G: DFG), RA: TA))
151 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef())
152 DefQ.insert(X: 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(G: DFG);
165 return BA.Addr->getCode();
166 };
167
168 SmallSet<NodeId, 32> Defs;
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(RA: RefRR, RB: TA.Addr->getRegRef(G: DFG)))
178 continue;
179 Defs.insert(V: TA.Id);
180 NodeAddr<InstrNode *> IA = TA.Addr->getOwner(G: DFG);
181 Owners[TA.Id] = IA;
182 Blocks[Block(IA)].push_back(Elt: 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 *>(N: A);
189 NodeAddr<InstrNode *> OB = DFG.addr<InstrNode *>(N: 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(Val: InA);
197 if (FA != OrdMap.end())
198 return FA->second < OrdMap.find(Val: 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(KV: {&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(x: Bucket.first);
227 if (Bucket.second.size() > 2)
228 GetOrder(*Bucket.first);
229 llvm::sort(C&: Bucket.second, Comp: Precedes);
230 }
231
232 // Sort the blocks with respect to dominance.
233 llvm::sort(C&: TmpBB,
234 Comp: [this](auto A, auto B) { return MDT.properlyDominates(A, B); });
235
236 std::vector<NodeId> TmpInst;
237 for (MachineBasicBlock *MBB : llvm::reverse(C&: TmpBB)) {
238 auto &Bucket = Blocks[MBB];
239 TmpInst.insert(position: TmpInst.end(), first: Bucket.rbegin(), last: 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(V: TA.Id);
263 };
264
265 for (NodeId T : TmpInst) {
266 if (!FullChain && RRs.hasCoverOf(RR: RefRR))
267 break;
268 auto TA = DFG.addr<InstrNode *>(N: T);
269 bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(BA: TA);
270 NodeList Ds;
271 for (NodeAddr<DefNode *> DA : TA.Addr->members_if(P: DefInSet, G: DFG)) {
272 RegisterRef QR = DA.Addr->getRegRef(G: 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(RR: QR))
282 Ds.push_back(Elt: DA);
283 }
284 llvm::append_range(C&: RDefs, R&: 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(RR: DA.Addr->getRegRef(G: DFG));
292 }
293 }
294
295 auto DeadP = [](const NodeAddr<DefNode *> DA) -> bool {
296 return DA.Addr->getFlags() & NodeAttrs::Dead;
297 };
298 llvm::erase_if(C&: RDefs, P: DeadP);
299
300 return RDefs;
301}
302
303std::pair<NodeSet, bool>
304Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
305 NodeSet &Visited, const NodeSet &Defs) {
306 return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, Nest: 0, MaxNest: 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 *>(N: D);
320 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
321 DefRRs.insert(RR: DA.Addr->getRegRef(G: DFG));
322 }
323
324 NodeList RDs = getAllReachingDefs(RefRR, RefA, TopShadows: false, FullChain: 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(x: R.Id);
332
333 NodeSet Result = Defs;
334
335 for (NodeAddr<DefNode *> DA : RDs) {
336 Result.insert(x: DA.Id);
337 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef))
338 continue;
339 NodeAddr<PhiNode *> PA = DA.Addr->getOwner(G: DFG);
340 if (!Visited.insert(x: 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(P: DFG.IsRef<NodeAttrs::Use>, G: DFG)) {
344 const auto &T = getAllReachingDefsRecImpl(RefRR, RefA: U, Visited, Defs: TmpDefs,
345 Nest: Nest + 1, MaxNest);
346 if (!T.second)
347 return {T.first, false};
348 Result.insert(first: T.first.begin(), last: 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.
357NodeAddr<RefNode *> Liveness::getNearestAliasedRef(RegisterRef RefRR,
358 NodeAddr<InstrNode *> IA) {
359 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(G: DFG);
360 NodeList Ins = BA.Addr->members(G: DFG);
361 NodeId FindId = IA.Id;
362 auto E = Ins.rend();
363 auto B =
364 std::find_if(first: Ins.rbegin(), last: E, pred: [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(x: B, y: E)) {
374 NodeList Refs = I.Addr->members(G: DFG);
375 NodeAddr<RefNode *> Clob, Use;
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(RA: R.Addr->getRegRef(G: DFG), RB: RefRR))
380 continue;
381 if (DFG.IsDef(BA: 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();
398 BA = NodeAddr<BlockNode *>();
399 if (MachineDomTreeNode *N = MDT.getNode(BB)) {
400 if ((N = N->getIDom()))
401 BA = DFG.findBlock(BB: N->getBlock());
402 }
403 if (!BA.Id)
404 break;
405
406 Ins = BA.Addr->members(G: DFG);
407 B = Ins.rbegin();
408 E = Ins.rend();
409 } while (true);
410
411 return NodeAddr<RefNode *>();
412}
413
414NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA,
415 const RegisterAggr &DefRRs) {
416 NodeSet Uses;
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(RR: 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 *>(N: U);
429 if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) {
430 RegisterRef UR = UA.Addr->getRegRef(G: DFG);
431 if (PRI.alias(RA: RefRR, RB: UR) && !DefRRs.hasCoverOf(RR: UR))
432 Uses.insert(x: 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 *>(N: D);
440 NextD = DA.Addr->getSibling();
441 RegisterRef DR = DA.Addr->getRegRef(G: 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(RR: DR) || !PRI.alias(RA: RefRR, RB: 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, DefA: DA, DefRRs);
450 } else {
451 RegisterAggr NewDefRRs = DefRRs;
452 NewDefRRs.insert(RR: DR);
453 T = getAllReachedUses(RefRR, DefA: DA, DefRRs: NewDefRRs);
454 }
455 Uses.insert(first: T.begin(), last: T.end());
456 }
457 return Uses;
458}
459
460void Liveness::computePhiInfo() {
461 RealUseMap.clear();
462
463 NodeList Phis;
464 NodeAddr<FuncNode *> FA = DFG.getFunc();
465 NodeList Blocks = FA.Addr->members(G: DFG);
466 for (NodeAddr<BlockNode *> BA : Blocks) {
467 auto Ps = BA.Addr->members_if(P: DFG.IsCode<NodeAttrs::Phi>, G: DFG);
468 llvm::append_range(C&: Phis, R&: 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(G: 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.
486 SetVector<NodeId> DefQ;
487 NodeSet PhiDefs;
488 RegisterAggr DRs(PRI);
489 for (NodeAddr<RefNode *> R : PhiRefs) {
490 if (!DFG.IsRef<NodeAttrs::Def>(BA: R))
491 continue;
492 DRs.insert(RR: R.Addr->getRegRef(G: DFG));
493 DefQ.insert(X: R.Id);
494 PhiDefs.insert(x: R.Id);
495 }
496 PhiDRs.insert(x: std::make_pair(x&: PhiA.Id, y&: 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 *>(N: 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 *>(N: UN);
511 uint16_t F = A.Addr->getFlags();
512 if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) {
513 RegisterRef R = A.Addr->getRegRef(G: DFG);
514 RealUses[R.Reg].insert(x: {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 *>(N: DN);
524 for (auto T : DFG.getRelatedRefs(IA: A.Addr->getOwner(G: DFG), RA: 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(X: 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 *>(N: 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(k: PhiA.Id).intersectWith(RR: 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(RefRR: R, RefA: UA)) {
566 if (PhiDefs.count(x: DA.Id))
567 break;
568 Covered.insert(RR: DA.Addr->getRegRef(G: DFG));
569 }
570 if (RegisterRef RC = Covered.clearIn(RR: 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(RR: RC, R: UI->first);
574 UI->second.insert(x: {I.first, S.Mask});
575 }
576 }
577 UI = UI->second.empty() ? RealUses.erase(position: UI) : std::next(x: 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(x: 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>(BA: I) || SeenUses.count(x: I.Id))
594 continue;
595 NodeAddr<PhiUseNode *> PUA = I;
596 if (PUA.Addr->getReachingDef() == 0)
597 continue;
598
599 RegisterRef UR = PUA.Addr->getRegRef(G: DFG);
600 NodeList Ds = getAllReachingDefs(RefRR: UR, RefA: PUA, TopShadows: true, FullChain: false, DefRRs: 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(G: DFG).Id;
606 auto [F, Inserted] = PhiUp[PUA.Id].try_emplace(k: RP, args&: DefRRs);
607 if (!Inserted)
608 F->second.insert(RG: DefRRs);
609 }
610 DefRRs.insert(RR: D.Addr->getRegRef(G: DFG));
611 }
612
613 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(IA: PhiA, RA: PUA))
614 SeenUses.insert(x: 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 = std::equal_to<RegisterRef>;
656 using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
657 std::unordered_map<RegisterAggr, SubMap> Subs;
658 auto ClearIn = [](RegisterRef RR, const RegisterAggr &Mid, SubMap &SM) {
659 if (Mid.empty())
660 return RR;
661 auto F = SM.find(x: RR);
662 if (F != SM.end())
663 return F->second;
664 RegisterRef S = Mid.clearIn(RR);
665 SM.insert(x: {RR, S});
666 return S;
667 };
668
669 // Go over all phis.
670 for (unsigned i = 0; i < PhiUQ.size(); ++i) {
671 auto PA = DFG.addr<PhiNode *>(N: PhiUQ[i]);
672 NodeList PUs = PA.Addr->members_if(P: DFG.IsRef<NodeAttrs::Use>, G: DFG);
673 RefMap &RUM = RealUseMap[PA.Id];
674
675 for (NodeAddr<UseNode *> UA : PUs) {
676 std::map<NodeId, RegisterAggr> &PUM = PhiUp[UA.Id];
677 RegisterRef UR = UA.Addr->getRegRef(G: DFG);
678 for (const std::pair<const NodeId, RegisterAggr> &P : PUM) {
679 bool Changed = false;
680 const RegisterAggr &MidDefs = P.second;
681 // Collect the set PropUp of uses that are reached by the current
682 // phi PA, and are not covered by any intervening def between the
683 // currently visited use UA and the upward phi P.
684
685 if (MidDefs.hasCoverOf(RR: UR))
686 continue;
687 SubMap &SM = Subs.try_emplace(k: MidDefs, args: 1, args: RefHash(), args: RefEqual(PRI))
688 .first->second;
689
690 // General algorithm:
691 // for each (R,U) : U is use node of R, U is reached by PA
692 // if MidDefs does not cover (R,U)
693 // then add (R-MidDefs,U) to RealUseMap[P]
694 //
695 for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) {
696 RegisterRef R(T.first);
697 // The current phi (PA) could be a phi for a regmask. It could
698 // reach a whole variety of uses that are not related to the
699 // specific upward phi (P.first).
700 const RegisterAggr &DRs = PhiDRs.at(k: P.first);
701 if (!DRs.hasAliasOf(RR: R))
702 continue;
703 R = PRI.mapTo(RR: DRs.intersectWith(RR: R), R: T.first);
704 for (std::pair<NodeId, LaneBitmask> V : T.second) {
705 LaneBitmask M = R.Mask & V.second;
706 if (M.none())
707 continue;
708 if (RegisterRef SS = ClearIn(RegisterRef(R.Reg, M), MidDefs, SM)) {
709 NodeRefSet &RS = RealUseMap[P.first][SS.Reg];
710 Changed |= RS.insert(x: {V.first, SS.Mask}).second;
711 }
712 }
713 }
714
715 if (Changed)
716 PhiUQ.push_back(x: P.first);
717 }
718 }
719 }
720
721 if (Trace) {
722 dbgs() << "Real use map:\n";
723 for (auto I : RealUseMap) {
724 dbgs() << "phi " << Print(I.first, DFG);
725 NodeAddr<PhiNode *> PA = DFG.addr<PhiNode *>(N: I.first);
726 NodeList Ds = PA.Addr->members_if(P: DFG.IsRef<NodeAttrs::Def>, G: DFG);
727 if (!Ds.empty()) {
728 RegisterRef RR = NodeAddr<DefNode *>(Ds[0]).Addr->getRegRef(G: DFG);
729 dbgs() << '<' << Print(RR, DFG) << '>';
730 } else {
731 dbgs() << "<noreg>";
732 }
733 dbgs() << " -> " << Print(I.second, DFG) << '\n';
734 }
735 }
736}
737
738void Liveness::computeLiveIns() {
739 // Populate the node-to-block map. This speeds up the calculations
740 // significantly.
741 NBMap.clear();
742 for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(G: DFG)) {
743 MachineBasicBlock *BB = BA.Addr->getCode();
744 for (NodeAddr<InstrNode *> IA : BA.Addr->members(G: DFG)) {
745 for (NodeAddr<RefNode *> RA : IA.Addr->members(G: DFG))
746 NBMap.insert(KV: std::make_pair(x&: RA.Id, y&: BB));
747 NBMap.insert(KV: std::make_pair(x&: IA.Id, y&: BB));
748 }
749 }
750
751 MachineFunction &MF = DFG.getMF();
752
753 // Compute IDF first, then the inverse.
754 decltype(IIDF) IDF;
755 for (MachineBasicBlock &B : MF) {
756 auto F1 = MDF.find(B: &B);
757 if (F1 == MDF.end())
758 continue;
759 SetVector<MachineBasicBlock *> IDFB(llvm::from_range, F1->second);
760 for (unsigned i = 0; i < IDFB.size(); ++i) {
761 auto F2 = MDF.find(B: IDFB[i]);
762 if (F2 != MDF.end())
763 IDFB.insert_range(R: F2->second);
764 }
765 // Add B to the IDF(B). This will put B in the IIDF(B).
766 IDFB.insert(X: &B);
767 IDF[&B].insert(first: IDFB.begin(), last: IDFB.end());
768 }
769
770 for (auto I : IDF)
771 for (auto *S : I.second)
772 IIDF[S].insert(x: I.first);
773
774 computePhiInfo();
775
776 NodeAddr<FuncNode *> FA = DFG.getFunc();
777 NodeList Blocks = FA.Addr->members(G: DFG);
778
779 // Build the phi live-on-entry map.
780 for (NodeAddr<BlockNode *> BA : Blocks) {
781 MachineBasicBlock *MB = BA.Addr->getCode();
782 RefMap &LON = PhiLON[MB];
783 for (auto P : BA.Addr->members_if(P: DFG.IsCode<NodeAttrs::Phi>, G: DFG)) {
784 for (const RefMap::value_type &S : RealUseMap[P.Id])
785 LON[S.first].insert(first: S.second.begin(), last: S.second.end());
786 }
787 }
788
789 if (Trace) {
790 dbgs() << "Phi live-on-entry map:\n";
791 for (auto &I : PhiLON)
792 dbgs() << "block #" << I.first->getNumber() << " -> "
793 << Print(I.second, DFG) << '\n';
794 }
795
796 // Build the phi live-on-exit map. Each phi node has some set of reached
797 // "real" uses. Propagate this set backwards into the block predecessors
798 // through the reaching defs of the corresponding phi uses.
799 for (NodeAddr<BlockNode *> BA : Blocks) {
800 NodeList Phis = BA.Addr->members_if(P: DFG.IsCode<NodeAttrs::Phi>, G: DFG);
801 for (NodeAddr<PhiNode *> PA : Phis) {
802 RefMap &RUs = RealUseMap[PA.Id];
803 if (RUs.empty())
804 continue;
805
806 NodeSet SeenUses;
807 for (auto U : PA.Addr->members_if(P: DFG.IsRef<NodeAttrs::Use>, G: DFG)) {
808 if (!SeenUses.insert(x: U.Id).second)
809 continue;
810 NodeAddr<PhiUseNode *> PUA = U;
811 if (PUA.Addr->getReachingDef() == 0)
812 continue;
813
814 // Each phi has some set (possibly empty) of reached "real" uses,
815 // that is, uses that are part of the compiled program. Such a use
816 // may be located in some farther block, but following a chain of
817 // reaching defs will eventually lead to this phi.
818 // Any chain of reaching defs may fork at a phi node, but there
819 // will be a path upwards that will lead to this phi. Now, this
820 // chain will need to fork at this phi, since some of the reached
821 // uses may have definitions joining in from multiple predecessors.
822 // For each reached "real" use, identify the set of reaching defs
823 // coming from each predecessor P, and add them to PhiLOX[P].
824 //
825 auto PrA = DFG.addr<BlockNode *>(N: PUA.Addr->getPredecessor());
826 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
827
828 for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
829 // We need to visit each individual use.
830 for (std::pair<NodeId, LaneBitmask> P : RS.second) {
831 // Create a register ref corresponding to the use, and find
832 // all reaching defs starting from the phi use, and treating
833 // all related shadows as a single use cluster.
834 RegisterRef S(RS.first, P.second);
835 NodeList Ds = getAllReachingDefs(RefRR: S, RefA: PUA, TopShadows: true, FullChain: false, DefRRs: NoRegs);
836 for (NodeAddr<DefNode *> D : Ds) {
837 // Calculate the mask corresponding to the visited def.
838 RegisterAggr TA(PRI);
839 TA.insert(RR: D.Addr->getRegRef(G: DFG)).intersect(RR: S);
840 LaneBitmask TM = TA.makeRegRef().Mask;
841 LOX[S.Reg].insert(x: {D.Id, TM});
842 }
843 }
844 }
845
846 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(IA: PA, RA: PUA))
847 SeenUses.insert(x: T.Id);
848 } // for U : phi uses
849 } // for P : Phis
850 } // for B : Blocks
851
852 if (Trace) {
853 dbgs() << "Phi live-on-exit map:\n";
854 for (auto &I : PhiLOX)
855 dbgs() << "block #" << I.first->getNumber() << " -> "
856 << Print(I.second, DFG) << '\n';
857 }
858
859 RefMap LiveIn;
860 traverse(B: &MF.front(), LiveIn);
861
862 // Add function live-ins to the live-in set of the function entry block.
863 LiveMap[&MF.front()].insert(RG: DFG.getLiveIns());
864
865 if (Trace) {
866 // Dump the liveness map
867 for (MachineBasicBlock &B : MF) {
868 std::vector<RegisterRef> LV;
869 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
870 LV.push_back(x: RegisterRef(LI.PhysReg, LI.LaneMask));
871 llvm::sort(C&: LV, Comp: std::less<RegisterRef>(PRI));
872 dbgs() << printMBBReference(MBB: B) << "\t rec = {";
873 for (auto I : LV)
874 dbgs() << ' ' << Print(I, DFG);
875 dbgs() << " }\n";
876 // dbgs() << "\tcomp = " << Print(LiveMap[&B], DFG) << '\n';
877
878 LV.clear();
879 for (RegisterRef RR : LiveMap[&B].refs())
880 LV.push_back(x: RR);
881 llvm::sort(C&: LV, Comp: std::less<RegisterRef>(PRI));
882 dbgs() << "\tcomp = {";
883 for (auto I : LV)
884 dbgs() << ' ' << Print(I, DFG);
885 dbgs() << " }\n";
886 }
887 }
888}
889
890void Liveness::resetLiveIns() {
891 for (auto &B : DFG.getMF()) {
892 // Remove all live-ins.
893 std::vector<MCRegister> T;
894 for (const MachineBasicBlock::RegisterMaskPair &LI : B.liveins())
895 T.push_back(x: LI.PhysReg);
896 for (auto I : T)
897 B.removeLiveIn(Reg: I);
898 // Add the newly computed live-ins.
899 const RegisterAggr &LiveIns = LiveMap[&B];
900 for (RegisterRef R : LiveIns.refs())
901 B.addLiveIn(RegMaskPair: {MCPhysReg(R.Reg), R.Mask});
902 }
903}
904
905void Liveness::resetKills() {
906 for (auto &B : DFG.getMF())
907 resetKills(B: &B);
908}
909
910void Liveness::resetKills(MachineBasicBlock *B) {
911 auto CopyLiveIns = [this](MachineBasicBlock *B, BitVector &LV) -> void {
912 for (auto I : B->liveins()) {
913 MCSubRegIndexIterator S(I.PhysReg, &TRI);
914 if (!S.isValid()) {
915 LV.set(I.PhysReg.id());
916 continue;
917 }
918 do {
919 LaneBitmask M = TRI.getSubRegIndexLaneMask(SubIdx: S.getSubRegIndex());
920 if ((M & I.LaneMask).any())
921 LV.set(S.getSubReg());
922 ++S;
923 } while (S.isValid());
924 }
925 };
926
927 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
928 CopyLiveIns(B, LiveIn);
929 for (auto *SI : B->successors())
930 CopyLiveIns(SI, Live);
931
932 for (MachineInstr &MI : llvm::reverse(C&: *B)) {
933 if (MI.isDebugInstr())
934 continue;
935
936 MI.clearKillInfo();
937 for (auto &Op : MI.all_defs()) {
938 // An implicit def of a super-register may not necessarily start a
939 // live range of it, since an implicit use could be used to keep parts
940 // of it live. Instead of analyzing the implicit operands, ignore
941 // implicit defs.
942 if (Op.isImplicit())
943 continue;
944 Register R = Op.getReg();
945 if (!R.isPhysical())
946 continue;
947 for (MCPhysReg SR : TRI.subregs_inclusive(Reg: R))
948 Live.reset(Idx: SR);
949 }
950 for (auto &Op : MI.all_uses()) {
951 if (Op.isUndef())
952 continue;
953 Register R = Op.getReg();
954 if (!R.isPhysical())
955 continue;
956 bool IsLive = false;
957 for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) {
958 if (!Live[(*AR).id()])
959 continue;
960 IsLive = true;
961 break;
962 }
963 if (!IsLive)
964 Op.setIsKill(true);
965 for (MCPhysReg SR : TRI.subregs_inclusive(Reg: R))
966 Live.set(SR);
967 }
968 }
969}
970
971// Helper function to obtain the basic block containing the reaching def
972// of the given use.
973MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
974 auto F = NBMap.find(Val: RN);
975 if (F != NBMap.end())
976 return F->second;
977 llvm_unreachable("Node id not in map");
978}
979
980void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
981 // The LiveIn map, for each (physical) register, contains the set of live
982 // reaching defs of that register that are live on entry to the associated
983 // block.
984
985 // The summary of the traversal algorithm:
986 //
987 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
988 // and (U \in IDF(B) or B dom U).
989 //
990 // for (C : children) {
991 // LU = {}
992 // traverse(C, LU)
993 // LiveUses += LU
994 // }
995 //
996 // LiveUses -= Defs(B);
997 // LiveUses += UpwardExposedUses(B);
998 // for (C : IIDF[B])
999 // for (U : LiveUses)
1000 // if (Rdef(U) dom C)
1001 // C.addLiveIn(U)
1002 //
1003
1004 // Go up the dominator tree (depth-first).
1005 MachineDomTreeNode *N = MDT.getNode(BB: B);
1006 for (auto *I : *N) {
1007 RefMap L;
1008 MachineBasicBlock *SB = I->getBlock();
1009 traverse(B: SB, LiveIn&: L);
1010
1011 for (auto S : L)
1012 LiveIn[S.first].insert(first: S.second.begin(), last: S.second.end());
1013 }
1014
1015 if (Trace) {
1016 dbgs() << "\n-- " << printMBBReference(MBB: *B) << ": " << __func__
1017 << " after recursion into: {";
1018 for (auto *I : *N)
1019 dbgs() << ' ' << I->getBlock()->getNumber();
1020 dbgs() << " }\n";
1021 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1022 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1023 }
1024
1025 // Add reaching defs of phi uses that are live on exit from this block.
1026 RefMap &PUs = PhiLOX[B];
1027 for (auto &S : PUs)
1028 LiveIn[S.first].insert(first: S.second.begin(), last: S.second.end());
1029
1030 if (Trace) {
1031 dbgs() << "after LOX\n";
1032 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1033 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1034 }
1035
1036 // The LiveIn map at this point has all defs that are live-on-exit from B,
1037 // as if they were live-on-entry to B. First, we need to filter out all
1038 // defs that are present in this block. Then we will add reaching defs of
1039 // all upward-exposed uses.
1040
1041 // To filter out the defs, first make a copy of LiveIn, and then re-populate
1042 // LiveIn with the defs that should remain.
1043 RefMap LiveInCopy = LiveIn;
1044 LiveIn.clear();
1045
1046 for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) {
1047 RegisterRef LRef(LE.first);
1048 NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled.
1049 const NodeRefSet &OldDefs = LE.second;
1050 for (NodeRef OR : OldDefs) {
1051 // R is a def node that was live-on-exit
1052 auto DA = DFG.addr<DefNode *>(N: OR.first);
1053 NodeAddr<InstrNode *> IA = DA.Addr->getOwner(G: DFG);
1054 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(G: DFG);
1055 if (B != BA.Addr->getCode()) {
1056 // Defs from a different block need to be preserved. Defs from this
1057 // block will need to be processed further, except for phi defs, the
1058 // liveness of which is handled through the PhiLON/PhiLOX maps.
1059 NewDefs.insert(x: OR);
1060 continue;
1061 }
1062
1063 // Defs from this block need to stop the liveness from being
1064 // propagated upwards. This only applies to non-preserving defs,
1065 // and to the parts of the register actually covered by those defs.
1066 // (Note that phi defs should always be preserving.)
1067 RegisterAggr RRs(PRI);
1068 LRef.Mask = OR.second;
1069
1070 if (!DFG.IsPreservingDef(DA)) {
1071 assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
1072 // DA is a non-phi def that is live-on-exit from this block, and
1073 // that is also located in this block. LRef is a register ref
1074 // whose use this def reaches. If DA covers LRef, then no part
1075 // of LRef is exposed upwards.A
1076 if (RRs.insert(RR: DA.Addr->getRegRef(G: DFG)).hasCoverOf(RR: LRef))
1077 continue;
1078 }
1079
1080 // DA itself was not sufficient to cover LRef. In general, it is
1081 // the last in a chain of aliased defs before the exit from this block.
1082 // There could be other defs in this block that are a part of that
1083 // chain. Check that now: accumulate the registers from these defs,
1084 // and if they all together cover LRef, it is not live-on-entry.
1085 for (NodeAddr<DefNode *> TA : getAllReachingDefs(RefA: DA)) {
1086 // DefNode -> InstrNode -> BlockNode.
1087 NodeAddr<InstrNode *> ITA = TA.Addr->getOwner(G: DFG);
1088 NodeAddr<BlockNode *> BTA = ITA.Addr->getOwner(G: DFG);
1089 // Reaching defs are ordered in the upward direction.
1090 if (BTA.Addr->getCode() != B) {
1091 // We have reached past the beginning of B, and the accumulated
1092 // registers are not covering LRef. The first def from the
1093 // upward chain will be live.
1094 // Subtract all accumulated defs (RRs) from LRef.
1095 RegisterRef T = RRs.clearIn(RR: LRef);
1096 assert(T);
1097 NewDefs.insert(x: {TA.Id, T.Mask});
1098 break;
1099 }
1100
1101 // TA is in B. Only add this def to the accumulated cover if it is
1102 // not preserving.
1103 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
1104 RRs.insert(RR: TA.Addr->getRegRef(G: DFG));
1105 // If this is enough to cover LRef, then stop.
1106 if (RRs.hasCoverOf(RR: LRef))
1107 break;
1108 }
1109 }
1110 }
1111
1112 emptify(M&: LiveIn);
1113
1114 if (Trace) {
1115 dbgs() << "after defs in block\n";
1116 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1117 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1118 }
1119
1120 // Scan the block for upward-exposed uses and add them to the tracking set.
1121 for (auto I : DFG.getFunc().Addr->findBlock(BB: B, G: DFG).Addr->members(G: DFG)) {
1122 NodeAddr<InstrNode *> IA = I;
1123 if (IA.Addr->getKind() != NodeAttrs::Stmt)
1124 continue;
1125 for (NodeAddr<UseNode *> UA : IA.Addr->members_if(P: DFG.IsUse, G: DFG)) {
1126 if (UA.Addr->getFlags() & NodeAttrs::Undef)
1127 continue;
1128 RegisterRef RR = UA.Addr->getRegRef(G: DFG);
1129 for (NodeAddr<DefNode *> D : getAllReachingDefs(RefA: UA))
1130 if (getBlockWithRef(RN: D.Id) != B)
1131 LiveIn[RR.Reg].insert(x: {D.Id, RR.Mask});
1132 }
1133 }
1134
1135 if (Trace) {
1136 dbgs() << "after uses in block\n";
1137 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1138 dbgs() << " Local: " << Print(LiveMap[B], DFG) << '\n';
1139 }
1140
1141 // Phi uses should not be propagated up the dominator tree, since they
1142 // are not dominated by their corresponding reaching defs.
1143 RegisterAggr &Local = LiveMap[B];
1144 RefMap &LON = PhiLON[B];
1145 for (auto &R : LON) {
1146 LaneBitmask M;
1147 for (auto P : R.second)
1148 M |= P.second;
1149 Local.insert(RR: RegisterRef(R.first, M));
1150 }
1151
1152 if (Trace) {
1153 dbgs() << "after phi uses in block\n";
1154 dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n';
1155 dbgs() << " Local: " << Print(Local, DFG) << '\n';
1156 }
1157
1158 for (auto *C : IIDF[B]) {
1159 RegisterAggr &LiveC = LiveMap[C];
1160 for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn)
1161 for (auto R : S.second)
1162 if (MDT.properlyDominates(A: getBlockWithRef(RN: R.first), B: C))
1163 LiveC.insert(RR: RegisterRef(S.first, R.second));
1164 }
1165}
1166
1167void Liveness::emptify(RefMap &M) {
1168 for (auto I = M.begin(), E = M.end(); I != E;)
1169 I = I->second.empty() ? M.erase(position: I) : std::next(x: I);
1170}
1171
1172} // namespace llvm::rdf
1173