1 //===--- RDFLiveness.cpp --------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Computation of the liveness information from the data-flow graph.
12 // The main functionality of this code is to compute block live-in
13 // information. With the live-in information in place, the placement
14 // of kill flags can also be recalculated.
16 // The block live-in calculation is based on the ideas from the following
19 // Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin.
20 // "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
21 // ACM Transactions on Architecture and Code Optimization, Association for
22 // Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
23 // and Embedded Architectures and Compilers", 8 (4),
24 // <10.1145/2086696.2086706>. <hal-00647369>
27 #include "RDFLiveness.h"
28 #include "llvm/ADT/SetVector.h"
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/CodeGen/MachineDominanceFrontier.h"
31 #include "llvm/CodeGen/MachineDominators.h"
32 #include "llvm/CodeGen/MachineFunction.h"
33 #include "llvm/CodeGen/MachineRegisterInfo.h"
34 #include "llvm/Target/TargetRegisterInfo.h"
41 raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) {
43 for (auto I : P.Obj) {
44 OS << ' ' << Print<RegisterRef>(I.first, P.G) << '{';
45 for (auto J = I.second.begin(), E = I.second.end(); J != E; ) {
46 OS << Print<NodeId>(*J, P.G);
57 // The order in the returned sequence is the order of reaching defs in the
58 // upward traversal: the first def is the closest to the given reference RefA,
59 // the next one is further up, and so on.
60 // The list ends at a reaching phi def, or when the reference from RefA is
61 // covered by the defs in the list (see FullChain).
62 // This function provides two modes of operation:
63 // (1) Returning the sequence of reaching defs for a particular reference
64 // node. This sequence will terminate at the first phi node [1].
65 // (2) Returning a partial sequence of reaching defs, where the final goal
66 // is to traverse past phi nodes to the actual defs arising from the code
68 // In mode (2), the register reference for which the search was started
69 // may be different from the reference node RefA, for which this call was
70 // made, hence the argument RefRR, which holds the original register.
71 // Also, some definitions may have already been encountered in a previous
72 // call that will influence register covering. The register references
73 // already defined are passed in through DefRRs.
74 // In mode (1), the "continuation" considerations do not apply, and the
75 // RefRR is the same as the register in RefA, and the set DefRRs is empty.
77 // [1] It is possible for multiple phi nodes to be included in the returned
81 // ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB)
82 // However, these phi nodes are independent from one another in terms of
85 NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
86 NodeAddr<RefNode*> RefA, bool FullChain, const RegisterSet &DefRRs) {
87 SetVector<NodeId> DefQ;
88 SetVector<NodeId> Owners;
90 // The initial queue should not have reaching defs for shadows. The
91 // whole point of a shadow is that it will have a reaching def that
92 // is not aliased to the reaching defs of the related shadows.
93 NodeId Start = RefA.Id;
94 auto SNA = DFG.addr<RefNode*>(Start);
95 if (NodeId RD = SNA.Addr->getReachingDef())
98 // Collect all the reaching defs, going up until a phi node is encountered,
99 // or there are no more reaching defs. From this set, the actual set of
100 // reaching defs will be selected.
101 // The traversal upwards must go on until a covering def is encountered.
102 // It is possible that a collection of non-covering (individually) defs
103 // will be sufficient, but keep going until a covering one is found.
104 for (unsigned i = 0; i < DefQ.size(); ++i) {
105 auto TA = DFG.addr<DefNode*>(DefQ[i]);
106 if (TA.Addr->getFlags() & NodeAttrs::PhiRef)
108 // Stop at the covering/overwriting def of the initial register reference.
109 RegisterRef RR = TA.Addr->getRegRef();
110 if (RAI.covers(RR, RefRR)) {
111 uint16_t Flags = TA.Addr->getFlags();
112 if (!(Flags & NodeAttrs::Preserving))
115 // Get the next level of reaching defs. This will include multiple
116 // reaching defs for shadows.
117 for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA))
118 if (auto RD = NodeAddr<RefNode*>(S).Addr->getReachingDef())
122 // Remove all non-phi defs that are not aliased to RefRR, and collect
123 // the owners of the remaining defs.
124 SetVector<NodeId> Defs;
125 for (auto N : DefQ) {
126 auto TA = DFG.addr<DefNode*>(N);
127 bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef;
128 if (!IsPhi && !RAI.alias(RefRR, TA.Addr->getRegRef()))
131 Owners.insert(TA.Addr->getOwner(DFG).Id);
134 // Return the MachineBasicBlock containing a given instruction.
135 auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* {
136 if (IA.Addr->getKind() == NodeAttrs::Stmt)
137 return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent();
138 assert(IA.Addr->getKind() == NodeAttrs::Phi);
139 NodeAddr<PhiNode*> PA = IA;
140 NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG);
141 return BA.Addr->getCode();
143 // Less(A,B) iff instruction A is further down in the dominator tree than B.
144 auto Less = [&Block,this] (NodeId A, NodeId B) -> bool {
147 auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B);
148 MachineBasicBlock *BA = Block(OA), *BB = Block(OB);
150 return MDT.dominates(BB, BA);
151 // They are in the same block.
152 bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt;
153 bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt;
155 if (!StmtB) // OB is a phi and phis dominate statements.
157 auto CA = NodeAddr<StmtNode*>(OA).Addr->getCode();
158 auto CB = NodeAddr<StmtNode*>(OB).Addr->getCode();
159 // The order must be linear, so tie-break such equalities.
162 return MDT.dominates(CB, CA);
167 // Both are phis. There is no ordering between phis (in terms of
168 // the data-flow), so tie-break this via node id comparison.
173 std::vector<NodeId> Tmp(Owners.begin(), Owners.end());
174 std::sort(Tmp.begin(), Tmp.end(), Less);
176 // The vector is a list of instructions, so that defs coming from
177 // the same instruction don't need to be artificially ordered.
178 // Then, when computing the initial segment, and iterating over an
179 // instruction, pick the defs that contribute to the covering (i.e. is
180 // not covered by previously added defs). Check the defs individually,
181 // i.e. first check each def if is covered or not (without adding them
182 // to the tracking set), and then add all the selected ones.
184 // The reason for this is this example:
185 // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes).
186 // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be
187 // covered if we added A first, and A would be covered
188 // if we added B first.
191 RegisterSet RRs = DefRRs;
193 auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool {
194 return TA.Addr->getKind() == NodeAttrs::Def &&
198 if (!FullChain && RAI.covers(RRs, RefRR))
200 auto TA = DFG.addr<InstrNode*>(T);
201 bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA);
203 for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) {
204 auto QR = DA.Addr->getRegRef();
205 // Add phi defs even if they are covered by subsequent defs. This is
206 // for cases where the reached use is not covered by any of the defs
207 // encountered so far: the phi def is needed to expose the liveness
208 // of that use to the entry of the block.
210 // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2.
211 // d2<R3>(d1,,u3), ...
212 // ..., u3<D1>(d2) This use needs to be live on entry.
213 if (FullChain || IsPhi || !RAI.covers(RRs, QR))
216 RDefs.insert(RDefs.end(), Ds.begin(), Ds.end());
217 for (NodeAddr<DefNode*> DA : Ds) {
218 // When collecting a full chain of definitions, do not consider phi
219 // defs to actually define a register.
220 uint16_t Flags = DA.Addr->getFlags();
221 if (!FullChain || !(Flags & NodeAttrs::PhiRef))
222 if (!(Flags & NodeAttrs::Preserving))
223 RRs.insert(DA.Addr->getRegRef());
231 static const RegisterSet NoRegs;
233 NodeList Liveness::getAllReachingDefs(NodeAddr<RefNode*> RefA) {
234 return getAllReachingDefs(RefA.Addr->getRegRef(), RefA, false, NoRegs);
238 void Liveness::computePhiInfo() {
240 NodeAddr<FuncNode*> FA = DFG.getFunc();
241 auto Blocks = FA.Addr->members(DFG);
242 for (NodeAddr<BlockNode*> BA : Blocks) {
243 auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
244 Phis.insert(Phis.end(), Ps.begin(), Ps.end());
247 // phi use -> (map: reaching phi -> set of registers defined in between)
248 std::map<NodeId,std::map<NodeId,RegisterSet>> PhiUp;
249 std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation.
252 for (NodeAddr<PhiNode*> PhiA : Phis) {
253 // Go over all defs and collect the reached uses that are non-phi uses
254 // (i.e. the "real uses").
255 auto &RealUses = RealUseMap[PhiA.Id];
256 auto PhiRefs = PhiA.Addr->members(DFG);
258 // Have a work queue of defs whose reached uses need to be found.
259 // For each def, add to the queue all reached (non-phi) defs.
260 SetVector<NodeId> DefQ;
262 for (auto R : PhiRefs) {
263 if (!DFG.IsRef<NodeAttrs::Def>(R))
266 PhiDefs.insert(R.Id);
268 for (unsigned i = 0; i < DefQ.size(); ++i) {
269 NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]);
270 NodeId UN = DA.Addr->getReachedUse();
272 NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN);
273 if (!(A.Addr->getFlags() & NodeAttrs::PhiRef))
274 RealUses[getRestrictedRegRef(A)].insert(A.Id);
275 UN = A.Addr->getSibling();
277 NodeId DN = DA.Addr->getReachedDef();
279 NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN);
280 for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) {
281 uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags();
282 // Must traverse the reached-def chain. Consider:
283 // def(D0) -> def(R0) -> def(R0) -> use(D0)
284 // The reachable use of D0 passes through a def of R0.
285 if (!(Flags & NodeAttrs::PhiRef))
288 DN = A.Addr->getSibling();
291 // Filter out these uses that appear to be reachable, but really
292 // are not. For example:
295 // = R1:0 u2 Reached by d1.
297 // = R1:0 u4 Still reached by d1: indirectly through
300 // = R1:0 u6 Not reached by d1 (covered collectively
301 // by d3 and d5), but following reached
302 // defs and uses from d1 will lead here.
303 auto HasDef = [&PhiDefs] (NodeAddr<DefNode*> DA) -> bool {
304 return PhiDefs.count(DA.Id);
306 for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) {
307 // For each reached register UI->first, there is a set UI->second, of
308 // uses of it. For each such use, check if it is reached by this phi,
309 // i.e. check if the set of its reaching uses intersects the set of
311 auto &Uses = UI->second;
312 for (auto I = Uses.begin(), E = Uses.end(); I != E; ) {
313 auto UA = DFG.addr<UseNode*>(*I);
314 NodeList RDs = getAllReachingDefs(UI->first, UA);
315 if (std::any_of(RDs.begin(), RDs.end(), HasDef))
321 UI = RealUses.erase(UI);
326 // If this phi reaches some "real" uses, add it to the queue for upward
328 if (!RealUses.empty())
329 PhiUQ.push_back(PhiA.Id);
331 // Go over all phi uses and check if the reaching def is another phi.
332 // Collect the phis that are among the reaching defs of these uses.
333 // While traversing the list of reaching defs for each phi use, collect
334 // the set of registers defined between this phi (Phi) and the owner phi
335 // of the reaching def.
336 for (auto I : PhiRefs) {
337 if (!DFG.IsRef<NodeAttrs::Use>(I))
339 NodeAddr<UseNode*> UA = I;
340 auto &UpMap = PhiUp[UA.Id];
342 for (NodeAddr<DefNode*> DA : getAllReachingDefs(UA)) {
343 if (DA.Addr->getFlags() & NodeAttrs::PhiRef)
344 UpMap[DA.Addr->getOwner(DFG).Id] = DefRRs;
346 DefRRs.insert(DA.Addr->getRegRef());
352 dbgs() << "Phi-up-to-phi map:\n";
353 for (auto I : PhiUp) {
354 dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {";
355 for (auto R : I.second)
356 dbgs() << ' ' << Print<NodeId>(R.first, DFG)
357 << Print<RegisterSet>(R.second, DFG);
362 // Propagate the reached registers up in the phi chain.
364 // The following type of situation needs careful handling:
374 // The phi node (2) defines a register pair R1:0, and reaches a "real"
375 // use u4 of just R1. The same phi node is also known to reach (upwards)
376 // the phi node (1). However, the use u4 is not reached by phi (1),
377 // because of the intervening definition d2 of R1. The data flow between
378 // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0.
380 // When propagating uses up the phi chains, get the all reaching defs
381 // for a given phi use, and traverse the list until the propagated ref
382 // is covered, or until or until reaching the final phi. Only assume
383 // that the reference reaches the phi in the latter case.
385 for (unsigned i = 0; i < PhiUQ.size(); ++i) {
386 auto PA = DFG.addr<PhiNode*>(PhiUQ[i]);
387 auto &RealUses = RealUseMap[PA.Id];
388 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
389 NodeAddr<UseNode*> UA = U;
390 auto &UpPhis = PhiUp[UA.Id];
391 for (auto UP : UpPhis) {
392 bool Changed = false;
393 auto &MidDefs = UP.second;
394 // Collect the set UpReached of uses that are reached by the current
395 // phi PA, and are not covered by any intervening def between PA and
396 // the upward phi UP.
397 RegisterSet UpReached;
398 for (auto T : RealUses) {
399 if (!isRestricted(PA, UA, T.first))
401 if (!RAI.covers(MidDefs, T.first))
402 UpReached.insert(T.first);
404 if (UpReached.empty())
406 // Update the set PRUs of real uses reached by the upward phi UP with
407 // the actual set of uses (UpReached) that the UP phi reaches.
408 auto &PRUs = RealUseMap[UP.first];
409 for (auto R : UpReached) {
410 unsigned Z = PRUs[R].size();
411 PRUs[R].insert(RealUses[R].begin(), RealUses[R].end());
412 Changed |= (PRUs[R].size() != Z);
415 PhiUQ.push_back(UP.first);
421 dbgs() << "Real use map:\n";
422 for (auto I : RealUseMap) {
423 dbgs() << "phi " << Print<NodeId>(I.first, DFG);
424 NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first);
425 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG);
427 RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef();
428 dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>';
432 dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n';
438 void Liveness::computeLiveIns() {
439 // Populate the node-to-block map. This speeds up the calculations
442 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
443 MachineBasicBlock *BB = BA.Addr->getCode();
444 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
445 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
446 NBMap.insert(std::make_pair(RA.Id, BB));
447 NBMap.insert(std::make_pair(IA.Id, BB));
451 MachineFunction &MF = DFG.getMF();
453 // Compute IDF first, then the inverse.
456 auto F1 = MDF.find(&B);
459 SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end());
460 for (unsigned i = 0; i < IDFB.size(); ++i) {
461 auto F2 = MDF.find(IDFB[i]);
463 IDFB.insert(F2->second.begin(), F2->second.end());
465 // Add B to the IDF(B). This will put B in the IIDF(B).
467 IDF[&B].insert(IDFB.begin(), IDFB.end());
471 for (auto S : I.second)
472 IIDF[S].insert(I.first);
476 NodeAddr<FuncNode*> FA = DFG.getFunc();
477 auto Blocks = FA.Addr->members(DFG);
479 // Build the phi live-on-entry map.
480 for (NodeAddr<BlockNode*> BA : Blocks) {
481 MachineBasicBlock *MB = BA.Addr->getCode();
482 auto &LON = PhiLON[MB];
483 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG))
484 for (auto S : RealUseMap[P.Id])
485 LON[S.first].insert(S.second.begin(), S.second.end());
489 dbgs() << "Phi live-on-entry map:\n";
490 for (auto I : PhiLON)
491 dbgs() << "block #" << I.first->getNumber() << " -> "
492 << Print<RefMap>(I.second, DFG) << '\n';
495 // Build the phi live-on-exit map. Each phi node has some set of reached
496 // "real" uses. Propagate this set backwards into the block predecessors
497 // through the reaching defs of the corresponding phi uses.
498 for (NodeAddr<BlockNode*> BA : Blocks) {
499 auto Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG);
500 for (NodeAddr<PhiNode*> PA : Phis) {
501 auto &RUs = RealUseMap[PA.Id];
505 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) {
506 NodeAddr<PhiUseNode*> UA = U;
507 if (UA.Addr->getReachingDef() == 0)
510 // Mark all reached "real" uses of P as live on exit in the
512 // Remap all the RUs so that they have a correct reaching def.
513 auto PrA = DFG.addr<BlockNode*>(UA.Addr->getPredecessor());
514 auto &LOX = PhiLOX[PrA.Addr->getCode()];
516 RegisterRef RR = R.first;
517 if (!isRestricted(PA, UA, RR))
518 RR = getRestrictedRegRef(UA);
519 // The restricted ref may be different from the ref that was
520 // accessed in the "real use". This means that this phi use
521 // is not the one that carries this reference, so skip it.
522 if (!RAI.alias(R.first, RR))
524 for (auto D : getAllReachingDefs(RR, UA))
525 LOX[RR].insert(D.Id);
527 } // for U : phi uses
532 dbgs() << "Phi live-on-exit map:\n";
533 for (auto I : PhiLOX)
534 dbgs() << "block #" << I.first->getNumber() << " -> "
535 << Print<RefMap>(I.second, DFG) << '\n';
539 traverse(&MF.front(), LiveIn);
541 // Add function live-ins to the live-in set of the function entry block.
542 auto &EntryIn = LiveMap[&MF.front()];
543 for (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I)
544 EntryIn.insert({I->first,0});
547 // Dump the liveness map
549 BitVector LV(TRI.getNumRegs());
550 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
552 dbgs() << "BB#" << B.getNumber() << "\t rec = {";
553 for (int x = LV.find_first(); x >= 0; x = LV.find_next(x))
554 dbgs() << ' ' << Print<RegisterRef>({unsigned(x),0}, DFG);
556 dbgs() << "\tcomp = " << Print<RegisterSet>(LiveMap[&B], DFG) << '\n';
562 void Liveness::resetLiveIns() {
563 for (auto &B : DFG.getMF()) {
564 // Remove all live-ins.
565 std::vector<unsigned> T;
566 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I)
567 T.push_back(I->PhysReg);
570 // Add the newly computed live-ins.
571 auto &LiveIns = LiveMap[&B];
572 for (auto I : LiveIns) {
580 void Liveness::resetKills() {
581 for (auto &B : DFG.getMF())
586 void Liveness::resetKills(MachineBasicBlock *B) {
587 auto CopyLiveIns = [] (MachineBasicBlock *B, BitVector &LV) -> void {
588 for (auto I = B->livein_begin(), E = B->livein_end(); I != E; ++I)
592 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs());
593 CopyLiveIns(B, LiveIn);
594 for (auto SI : B->successors())
595 CopyLiveIns(SI, Live);
597 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) {
598 MachineInstr *MI = &*I;
599 if (MI->isDebugValue())
603 for (auto &Op : MI->operands()) {
604 if (!Op.isReg() || !Op.isDef())
606 unsigned R = Op.getReg();
607 if (!TargetRegisterInfo::isPhysicalRegister(R))
609 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
612 for (auto &Op : MI->operands()) {
613 if (!Op.isReg() || !Op.isUse())
615 unsigned R = Op.getReg();
616 if (!TargetRegisterInfo::isPhysicalRegister(R))
619 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) {
628 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR)
635 // For shadows, determine if RR is aliased to a reaching def of any other
636 // shadow associated with RA. If it is not, then RR is "restricted" to RA,
637 // and so it can be considered a value specific to RA. This is important
638 // for accurately determining values associated with phi uses.
639 // For non-shadows, this function returns "true".
640 bool Liveness::isRestricted(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
641 RegisterRef RR) const {
642 NodeId Start = RA.Id;
643 for (NodeAddr<RefNode*> TA = DFG.getNextShadow(IA, RA);
644 TA.Id != 0 && TA.Id != Start; TA = DFG.getNextShadow(IA, TA)) {
645 NodeId RD = TA.Addr->getReachingDef();
648 if (RAI.alias(RR, DFG.addr<DefNode*>(RD).Addr->getRegRef()))
655 RegisterRef Liveness::getRestrictedRegRef(NodeAddr<RefNode*> RA) const {
656 assert(DFG.IsRef<NodeAttrs::Use>(RA));
657 if (RA.Addr->getFlags() & NodeAttrs::Shadow) {
658 NodeId RD = RA.Addr->getReachingDef();
660 RA = DFG.addr<DefNode*>(RD);
662 return RA.Addr->getRegRef();
666 unsigned Liveness::getPhysReg(RegisterRef RR) const {
667 if (!TargetRegisterInfo::isPhysicalRegister(RR.Reg))
669 return RR.Sub ? TRI.getSubReg(RR.Reg, RR.Sub) : RR.Reg;
673 // Helper function to obtain the basic block containing the reaching def
675 MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const {
676 auto F = NBMap.find(RN);
677 if (F != NBMap.end())
679 llvm_unreachable("Node id not in map");
683 void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
684 // The LiveIn map, for each (physical) register, contains the set of live
685 // reaching defs of that register that are live on entry to the associated
688 // The summary of the traversal algorithm:
690 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B
691 // and (U \in IDF(B) or B dom U).
693 // for (C : children) {
699 // LiveUses -= Defs(B);
700 // LiveUses += UpwardExposedUses(B);
702 // for (U : LiveUses)
703 // if (Rdef(U) dom C)
707 // Go up the dominator tree (depth-first).
708 MachineDomTreeNode *N = MDT.getNode(B);
711 MachineBasicBlock *SB = I->getBlock();
715 LiveIn[S.first].insert(S.second.begin(), S.second.end());
719 dbgs() << LLVM_FUNCTION_NAME << " in BB#" << B->getNumber()
720 << " after recursion into";
722 dbgs() << ' ' << I->getBlock()->getNumber();
723 dbgs() << "\n LiveIn: " << Print<RefMap>(LiveIn, DFG);
724 dbgs() << "\n Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
727 // Add phi uses that are live on exit from this block.
728 RefMap &PUs = PhiLOX[B];
730 LiveIn[S.first].insert(S.second.begin(), S.second.end());
733 dbgs() << "after LOX\n";
734 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
735 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
738 // Stop tracking all uses defined in this block: erase those records
739 // where the reaching def is located in B and which cover all reached
744 for (auto I : Copy) {
745 auto &Defs = LiveIn[I.first];
747 for (auto R : I.second) {
748 auto DA = DFG.addr<DefNode*>(R);
749 RegisterRef DDR = DA.Addr->getRegRef();
750 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
751 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
752 // Defs from a different block need to be preserved. Defs from this
753 // block will need to be processed further, except for phi defs, the
754 // liveness of which is handled through the PhiLON/PhiLOX maps.
755 if (B != BA.Addr->getCode())
758 bool IsPreserving = DA.Addr->getFlags() & NodeAttrs::Preserving;
759 if (IA.Addr->getKind() != NodeAttrs::Phi && !IsPreserving) {
760 bool Covering = RAI.covers(DDR, I.first);
761 NodeId U = DA.Addr->getReachedUse();
762 while (U && Covering) {
763 auto DUA = DFG.addr<UseNode*>(U);
764 RegisterRef Q = DUA.Addr->getRegRef();
765 Covering = RAI.covers(DA.Addr->getRegRef(), Q);
766 U = DUA.Addr->getSibling();
774 // Non-covering defs from B.
775 for (auto R : Rest) {
776 auto DA = DFG.addr<DefNode*>(R);
777 RegisterRef DRR = DA.Addr->getRegRef();
779 for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) {
780 NodeAddr<InstrNode*> IA = TA.Addr->getOwner(DFG);
781 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
782 // Preserving defs do not count towards covering.
783 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
784 RRs.insert(TA.Addr->getRegRef());
785 if (BA.Addr->getCode() == B)
787 if (RAI.covers(RRs, DRR))
797 dbgs() << "after defs in block\n";
798 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
799 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
802 // Scan the block for upward-exposed uses and add them to the tracking set.
803 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) {
804 NodeAddr<InstrNode*> IA = I;
805 if (IA.Addr->getKind() != NodeAttrs::Stmt)
807 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
808 RegisterRef RR = UA.Addr->getRegRef();
809 for (auto D : getAllReachingDefs(UA))
810 if (getBlockWithRef(D.Id) != B)
811 LiveIn[RR].insert(D.Id);
816 dbgs() << "after uses in block\n";
817 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
818 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
821 // Phi uses should not be propagated up the dominator tree, since they
822 // are not dominated by their corresponding reaching defs.
823 auto &Local = LiveMap[B];
824 auto &LON = PhiLON[B];
826 Local.insert(R.first);
829 dbgs() << "after phi uses in block\n";
830 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n';
831 dbgs() << " Local: " << Print<RegisterSet>(Local, DFG) << '\n';
834 for (auto C : IIDF[B]) {
835 auto &LiveC = LiveMap[C];
836 for (auto S : LiveIn)
837 for (auto R : S.second)
838 if (MDT.properlyDominates(getBlockWithRef(R), C))
839 LiveC.insert(S.first);
844 void Liveness::emptify(RefMap &M) {
845 for (auto I = M.begin(), E = M.end(); I != E; )
846 I = I->second.empty() ? M.erase(I) : std::next(I);