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