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.Id].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 = 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(x: RR);
663 if (F != SM.end())
664 return F->second;
665 RegisterRef S = Mid.clearIn(RR);
666 SM.insert(x: {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 *>(N: PhiUQ[i]);
673 NodeList PUs = PA.Addr->members_if(P: DFG.IsRef<NodeAttrs::Use>, G: 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(G: 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(RR: UR))
687 continue;
688 SubMap &SM = Subs.try_emplace(k: MidDefs, args: 1, args: RefHash(), args: 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(k: P.first);
702 if (!DRs.hasAliasOf(RR: R))
703 continue;
704 R = PRI.mapTo(RR: DRs.intersectWith(RR: R), 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.Id, M), MidDefs, SM)) {
710 NodeRefSet &RS = RealUseMap[P.first][SS.Id];
711 Changed |= RS.insert(x: {V.first, SS.Mask}).second;
712 }
713 }
714 }
715
716 if (Changed)
717 PhiUQ.push_back(x: 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 *>(N: I.first);
727 NodeList Ds = PA.Addr->members_if(P: DFG.IsRef<NodeAttrs::Def>, G: DFG);
728 if (!Ds.empty()) {
729 RegisterRef RR = NodeAddr<DefNode *>(Ds[0]).Addr->getRegRef(G: DFG);
730 dbgs() << '<' << Print(RR, DFG) << '>';
731 } else {
732 dbgs() << "<noreg>";
733 }
734 dbgs() << " -> " << Print(I.second, DFG) << '\n';
735 }
736 }
737}
738
739void Liveness::computeLiveIns() {
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(G: DFG)) {
744 MachineBasicBlock *BB = BA.Addr->getCode();
745 for (NodeAddr<InstrNode *> IA : BA.Addr->members(G: DFG)) {
746 for (NodeAddr<RefNode *> RA : IA.Addr->members(G: DFG))
747 NBMap.insert(KV: std::make_pair(x&: RA.Id, y&: BB));
748 NBMap.insert(KV: std::make_pair(x&: IA.Id, y&: 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: &B);
758 if (F1 == MDF.end())
759 continue;
760 SetVector<MachineBasicBlock *> IDFB(llvm::from_range, F1->second);
761 for (unsigned i = 0; i < IDFB.size(); ++i) {
762 auto F2 = MDF.find(B: IDFB[i]);
763 if (F2 != MDF.end())
764 IDFB.insert_range(R: F2->second);
765 }
766 // Add B to the IDF(B). This will put B in the IIDF(B).
767 IDFB.insert(X: &B);
768 IDF[&B].insert(first: IDFB.begin(), last: IDFB.end());
769 }
770
771 for (auto I : IDF)
772 for (auto *S : I.second)
773 IIDF[S].insert(x: I.first);
774
775 computePhiInfo();
776
777 NodeAddr<FuncNode *> FA = DFG.getFunc();
778 NodeList Blocks = FA.Addr->members(G: 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(P: DFG.IsCode<NodeAttrs::Phi>, G: DFG)) {
785 for (const RefMap::value_type &S : RealUseMap[P.Id])
786 LON[S.first].insert(first: S.second.begin(), last: 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(P: DFG.IsCode<NodeAttrs::Phi>, G: 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(P: DFG.IsRef<NodeAttrs::Use>, G: DFG)) {
809 if (!SeenUses.insert(x: U.Id).second)
810 continue;
811 NodeAddr<PhiUseNode *> PUA = U;
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 *>(N: 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(RefRR: S, RefA: PUA, TopShadows: true, FullChain: false, DefRRs: NoRegs);
837 for (NodeAddr<DefNode *> D : Ds) {
838 // Calculate the mask corresponding to the visited def.
839 RegisterAggr TA(PRI);
840 TA.insert(RR: D.Addr->getRegRef(G: DFG)).intersect(RR: S);
841 LaneBitmask TM = TA.makeRegRef().Mask;
842 LOX[S.Id].insert(x: {D.Id, TM});
843 }
844 }
845 }
846
847 for (NodeAddr<PhiUseNode *> T : DFG.getRelatedRefs(IA: PA, RA: PUA))
848 SeenUses.insert(x: 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(B: &MF.front(), LiveIn);
862
863 // Add function live-ins to the live-in set of the function entry block.
864 LiveMap[&MF.front()].insert(RG: 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(x: RegisterRef(LI.PhysReg, LI.LaneMask));
872 llvm::sort(C&: LV, Comp: RegisterRefLess(PRI));
873 dbgs() << printMBBReference(MBB: 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(x: RR);
882 llvm::sort(C&: LV, Comp: RegisterRefLess(PRI));
883 dbgs() << "\tcomp = {";
884 for (auto I : LV)
885 dbgs() << ' ' << Print(I, DFG);
886 dbgs() << " }\n";
887 }
888 }
889}
890
891void Liveness::resetLiveIns() {
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(x: LI.PhysReg);
897 for (auto I : T)
898 B.removeLiveIn(Reg: I);
899 // Add the newly computed live-ins.
900 const RegisterAggr &LiveIns = LiveMap[&B];
901 for (RegisterRef R : LiveIns.refs())
902 B.addLiveIn(RegMaskPair: {R.asMCReg(), R.Mask});
903 }
904}
905
906void Liveness::resetKills() {
907 for (auto &B : DFG.getMF())
908 resetKills(B: &B);
909}
910
911void Liveness::resetKills(MachineBasicBlock *B) {
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(SubIdx: 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(C&: *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(Reg: R))
949 Live.reset(Idx: 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(Reg: 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(Val: 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(BB: B);
1007 for (auto *I : *N) {
1008 RefMap L;
1009 MachineBasicBlock *SB = I->getBlock();
1010 traverse(B: SB, LiveIn&: L);
1011
1012 for (auto S : L)
1013 LiveIn[S.first].insert(first: S.second.begin(), last: S.second.end());
1014 }
1015
1016 if (Trace) {
1017 dbgs() << "\n-- " << printMBBReference(MBB: *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(first: S.second.begin(), last: 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.Id]; // 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 *>(N: OR.first);
1054 NodeAddr<InstrNode *> IA = DA.Addr->getOwner(G: DFG);
1055 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(G: 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(x: 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(RR: DA.Addr->getRegRef(G: DFG)).hasCoverOf(RR: 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(RefA: DA)) {
1087 // DefNode -> InstrNode -> BlockNode.
1088 NodeAddr<InstrNode *> ITA = TA.Addr->getOwner(G: DFG);
1089 NodeAddr<BlockNode *> BTA = ITA.Addr->getOwner(G: 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(RR: LRef);
1097 assert(T);
1098 NewDefs.insert(x: {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(RR: TA.Addr->getRegRef(G: DFG));
1106 // If this is enough to cover LRef, then stop.
1107 if (RRs.hasCoverOf(RR: LRef))
1108 break;
1109 }
1110 }
1111 }
1112
1113 emptify(M&: 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(BB: B, G: DFG).Addr->members(G: DFG)) {
1123 NodeAddr<InstrNode *> IA = I;
1124 if (IA.Addr->getKind() != NodeAttrs::Stmt)
1125 continue;
1126 for (NodeAddr<UseNode *> UA : IA.Addr->members_if(P: DFG.IsUse, G: DFG)) {
1127 if (UA.Addr->getFlags() & NodeAttrs::Undef)
1128 continue;
1129 RegisterRef RR = UA.Addr->getRegRef(G: DFG);
1130 for (NodeAddr<DefNode *> D : getAllReachingDefs(RefA: UA))
1131 if (getBlockWithRef(RN: D.Id) != B)
1132 LiveIn[RR.Id].insert(x: {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(RR: 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(A: getBlockWithRef(RN: R.first), B: C))
1164 LiveC.insert(RR: 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(position: I) : std::next(x: I);
1171}
1172
1173} // namespace llvm::rdf
1174