Lines Matching +full:non +full:- +full:live
1 //===- RDFLiveness.cpp ----------------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Computation of the liveness information from the data-flow graph.
11 // The main functionality of this code is to compute block live-in
12 // information. With the live-in information in place, the placement
15 // The block live-in calculation is based on the ideas from the following
19 // "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
21 // Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
23 // <10.1145/2086696.2086706>. <hal-00647369>
55 static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25),
66 OS << Print(J->first, P.G) << PrintLaneMaskShort(J->second); in operator <<()
102 // the data-flow.
112 // Dead defs will be treated as if they were live, since they are actually in getAllReachingDefs()
113 // on the data-flow path. They cannot be ignored because even though they in getAllReachingDefs()
117 if (RefA.Addr->getFlags() & NodeAttrs::Undef) in getAllReachingDefs()
125 if (NodeId RD = SNA.Addr->getReachingDef()) in getAllReachingDefs()
128 for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA)) in getAllReachingDefs()
129 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef()) in getAllReachingDefs()
137 // It is possible that a collection of non-covering (individually) defs in getAllReachingDefs()
141 if (TA.Addr->getFlags() & NodeAttrs::PhiRef) in getAllReachingDefs()
144 RegisterRef RR = TA.Addr->getRegRef(DFG); in getAllReachingDefs()
150 for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) in getAllReachingDefs()
151 if (NodeId RD = NodeAddr<RefNode *>(S).Addr->getReachingDef()) in getAllReachingDefs()
159 auto Block = [this](NodeAddr<InstrNode *> IA) -> MachineBasicBlock * { in getAllReachingDefs()
160 if (IA.Addr->getKind() == NodeAttrs::Stmt) in getAllReachingDefs()
161 return NodeAddr<StmtNode *>(IA).Addr->getCode()->getParent(); in getAllReachingDefs()
162 assert(IA.Addr->getKind() == NodeAttrs::Phi); in getAllReachingDefs()
164 NodeAddr<BlockNode *> BA = PA.Addr->getOwner(DFG); in getAllReachingDefs()
165 return BA.Addr->getCode(); in getAllReachingDefs()
170 // Remove all non-phi defs that are not aliased to RefRR, and separate in getAllReachingDefs()
176 bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; in getAllReachingDefs()
177 if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG))) in getAllReachingDefs()
180 NodeAddr<InstrNode *> IA = TA.Addr->getOwner(DFG); in getAllReachingDefs()
190 bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; in getAllReachingDefs()
191 bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; in getAllReachingDefs()
193 const MachineInstr *InA = NodeAddr<StmtNode *>(OA).Addr->getCode(); in getAllReachingDefs()
194 const MachineInstr *InB = NodeAddr<StmtNode *>(OB).Addr->getCode(); in getAllReachingDefs()
195 assert(InA->getParent() == InB->getParent()); in getAllReachingDefs()
198 return FA->second < OrdMap.find(InB)->second; in getAllReachingDefs()
199 const MachineBasicBlock *BB = InA->getParent(); in getAllReachingDefs()
200 for (auto It = BB->begin(), E = BB->end(); It != E; ++It) { in getAllReachingDefs()
201 if (It == InA->getIterator()) in getAllReachingDefs()
203 if (It == InB->getIterator()) in getAllReachingDefs()
261 auto DefInSet = [&Defs](NodeAddr<RefNode *> TA) -> bool { in getAllReachingDefs()
262 return TA.Addr->getKind() == NodeAttrs::Def && Defs.count(TA.Id); in getAllReachingDefs()
271 for (NodeAddr<DefNode *> DA : TA.Addr->members_if(DefInSet, DFG)) { in getAllReachingDefs()
272 RegisterRef QR = DA.Addr->getRegRef(DFG); in getAllReachingDefs()
280 // ..., u3<D1>(d2) This use needs to be live on entry. in getAllReachingDefs()
288 uint16_t Flags = DA.Addr->getFlags(); in getAllReachingDefs()
291 RRs.insert(DA.Addr->getRegRef(DFG)); in getAllReachingDefs()
295 auto DeadP = [](const NodeAddr<DefNode *> DA) -> bool { in getAllReachingDefs()
296 return DA.Addr->getFlags() & NodeAttrs::Dead; in getAllReachingDefs()
320 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) in getAllReachingDefsRecImpl()
321 DefRRs.insert(DA.Addr->getRegRef(DFG)); in getAllReachingDefsRecImpl()
337 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) in getAllReachingDefsRecImpl()
339 NodeAddr<PhiNode *> PA = DA.Addr->getOwner(DFG); in getAllReachingDefsRecImpl()
343 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { in getAllReachingDefsRecImpl()
359 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(DFG); in getNearestAliasedRef()
360 NodeList Ins = BA.Addr->members(DFG); in getNearestAliasedRef()
374 NodeList Refs = I.Addr->members(DFG); in getNearestAliasedRef()
379 if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR)) in getNearestAliasedRef()
382 // If it's a non-clobbering def, just return it. in getNearestAliasedRef()
383 if (!(R.Addr->getFlags() & NodeAttrs::Clobbering)) in getNearestAliasedRef()
397 MachineBasicBlock *BB = BA.Addr->getCode(); in getNearestAliasedRef()
400 if ((N = N->getIDom())) in getNearestAliasedRef()
401 BA = DFG.findBlock(N->getBlock()); in getNearestAliasedRef()
406 Ins = BA.Addr->members(DFG); in getNearestAliasedRef()
425 bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead; in getAllReachedUses()
426 NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0; in getAllReachedUses()
429 if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) { in getAllReachedUses()
430 RegisterRef UR = UA.Addr->getRegRef(DFG); in getAllReachedUses()
434 U = UA.Addr->getSibling(); in getAllReachedUses()
438 for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { in getAllReachedUses()
440 NextD = DA.Addr->getSibling(); in getAllReachedUses()
441 RegisterRef DR = DA.Addr->getRegRef(DFG); in getAllReachedUses()
465 NodeList Blocks = FA.Addr->members(DFG); in computePhiInfo()
467 auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); in computePhiInfo()
471 // phi use -> (map: reaching phi -> set of registers defined in between) in computePhiInfo()
475 PhiDRs; // Phi -> registers defined by it. in computePhiInfo()
479 // Go over all defs and collect the reached uses that are non-phi uses in computePhiInfo()
482 NodeList PhiRefs = PhiA.Addr->members(DFG); in computePhiInfo()
485 // For each def, add to the queue all reached (non-phi) defs. in computePhiInfo()
492 DRs.insert(R.Addr->getRegRef(DFG)); in computePhiInfo()
498 // Collect the super-set of all possible reached uses. This set will in computePhiInfo()
500 // phi defs, or (recursively) via non-phi defs reached by the phi defs. in computePhiInfo()
507 bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead; in computePhiInfo()
508 NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0; in computePhiInfo()
511 uint16_t F = A.Addr->getFlags(); in computePhiInfo()
513 RegisterRef R = A.Addr->getRegRef(DFG); in computePhiInfo()
516 UN = A.Addr->getSibling(); in computePhiInfo()
521 NodeId DN = DA.Addr->getReachedDef(); in computePhiInfo()
524 for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { in computePhiInfo()
525 uint16_t Flags = NodeAddr<DefNode *>(T).Addr->getFlags(); in computePhiInfo()
526 // Must traverse the reached-def chain. Consider: in computePhiInfo()
527 // def(D0) -> def(R0) -> def(R0) -> use(D0) in computePhiInfo()
532 DN = A.Addr->getSibling(); in computePhiInfo()
548 // For each reached register UI->first, there is a set UI->second, of in computePhiInfo()
552 NodeRefSet Uses = UI->second; in computePhiInfo()
553 UI->second.clear(); in computePhiInfo()
557 assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); in computePhiInfo()
558 RegisterRef UseR(UI->first, I.second); // Ref from Uses in computePhiInfo()
568 Covered.insert(DA.Addr->getRegRef(DFG)); in computePhiInfo()
571 // We are updating the map for register UI->first, so we need in computePhiInfo()
573 RegisterRef S = PRI.mapTo(RC, UI->first); in computePhiInfo()
574 UI->second.insert({I.first, S.Mask}); in computePhiInfo()
577 UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI); in computePhiInfo()
596 if (PUA.Addr->getReachingDef() == 0) in computePhiInfo()
599 RegisterRef UR = PUA.Addr->getRegRef(DFG); in computePhiInfo()
604 if (D.Addr->getFlags() & NodeAttrs::PhiRef) { in computePhiInfo()
605 NodeId RP = D.Addr->getOwner(DFG).Id; in computePhiInfo()
611 F->second.insert(DefRRs); in computePhiInfo()
613 DefRRs.insert(D.Addr->getRegRef(DFG)); in computePhiInfo()
622 dbgs() << "Phi-up-to-phi map with intervening defs:\n"; in computePhiInfo()
624 dbgs() << "phi " << Print(I.first, DFG) << " -> {"; in computePhiInfo()
666 return F->second; in computePhiInfo()
675 NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG); in computePhiInfo()
680 RegisterRef UR = UA.Addr->getRegRef(DFG); in computePhiInfo()
698 // then add (R-MidDefs,U) to RealUseMap[P] in computePhiInfo()
731 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); in computePhiInfo()
733 RegisterRef RR = NodeAddr<DefNode *>(Ds[0]).Addr->getRegRef(DFG); in computePhiInfo()
738 dbgs() << " -> " << Print(I.second, DFG) << '\n'; in computePhiInfo()
744 // Populate the node-to-block map. This speeds up the calculations in computeLiveIns()
747 for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(DFG)) { in computeLiveIns()
748 MachineBasicBlock *BB = BA.Addr->getCode(); in computeLiveIns()
749 for (NodeAddr<InstrNode *> IA : BA.Addr->members(DFG)) { in computeLiveIns()
750 for (NodeAddr<RefNode *> RA : IA.Addr->members(DFG)) in computeLiveIns()
764 SetVector<MachineBasicBlock *> IDFB(F1->second.begin(), F1->second.end()); in computeLiveIns()
768 IDFB.insert(F2->second.begin(), F2->second.end()); in computeLiveIns()
782 NodeList Blocks = FA.Addr->members(DFG); in computeLiveIns()
784 // Build the phi live-on-entry map. in computeLiveIns()
786 MachineBasicBlock *MB = BA.Addr->getCode(); in computeLiveIns()
788 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) { in computeLiveIns()
795 dbgs() << "Phi live-on-entry map:\n"; in computeLiveIns()
797 dbgs() << "block #" << I.first->getNumber() << " -> " in computeLiveIns()
801 // Build the phi live-on-exit map. Each phi node has some set of reached in computeLiveIns()
805 NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); in computeLiveIns()
812 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { in computeLiveIns()
816 if (PUA.Addr->getReachingDef() == 0) in computeLiveIns()
830 auto PrA = DFG.addr<BlockNode *>(PUA.Addr->getPredecessor()); in computeLiveIns()
831 RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; in computeLiveIns()
844 TA.insert(D.Addr->getRegRef(DFG)).intersect(S); in computeLiveIns()
858 dbgs() << "Phi live-on-exit map:\n"; in computeLiveIns()
860 dbgs() << "block #" << I.first->getNumber() << " -> " in computeLiveIns()
867 // Add function live-ins to the live-in set of the function entry block. in computeLiveIns()
897 // Remove all live-ins. in resetLiveIns()
903 // Add the newly computed live-ins. in resetLiveIns()
916 auto CopyLiveIns = [this](MachineBasicBlock *B, BitVector &LV) -> void { in resetKills()
917 for (auto I : B->liveins()) { in resetKills()
932 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); in resetKills() local
934 for (auto *SI : B->successors()) in resetKills()
935 CopyLiveIns(SI, Live); in resetKills()
943 // An implicit def of a super-register may not necessarily start a in resetKills()
944 // live range of it, since an implicit use could be used to keep parts in resetKills()
945 // of it live. Instead of analyzing the implicit operands, ignore in resetKills()
953 Live.reset(SR); in resetKills()
963 if (!Live[*AR]) in resetKills()
971 Live.set(SR); in resetKills()
981 return F->second; in getBlockWithRef()
986 // The LiveIn map, for each (physical) register, contains the set of live in traverse()
987 // reaching defs of that register that are live on entry to the associated in traverse()
992 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B in traverse()
1001 // LiveUses -= Defs(B); in traverse()
1009 // Go up the dominator tree (depth-first). in traverse()
1013 MachineBasicBlock *SB = I->getBlock(); in traverse()
1021 dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__ in traverse()
1024 dbgs() << ' ' << I->getBlock()->getNumber(); in traverse()
1030 // Add reaching defs of phi uses that are live on exit from this block. in traverse()
1041 // The LiveIn map at this point has all defs that are live-on-exit from B, in traverse()
1042 // as if they were live-on-entry to B. First, we need to filter out all in traverse()
1044 // all upward-exposed uses. in traverse()
1046 // To filter out the defs, first make a copy of LiveIn, and then re-populate in traverse()
1056 // R is a def node that was live-on-exit in traverse()
1058 NodeAddr<InstrNode *> IA = DA.Addr->getOwner(DFG); in traverse()
1059 NodeAddr<BlockNode *> BA = IA.Addr->getOwner(DFG); in traverse()
1060 if (B != BA.Addr->getCode()) { in traverse()
1069 // propagated upwards. This only applies to non-preserving defs, in traverse()
1076 assert(!(IA.Addr->getFlags() & NodeAttrs::Phi)); in traverse()
1077 // DA is a non-phi def that is live-on-exit from this block, and in traverse()
1081 if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef)) in traverse()
1089 // and if they all together cover LRef, it is not live-on-entry. in traverse()
1091 // DefNode -> InstrNode -> BlockNode. in traverse()
1092 NodeAddr<InstrNode *> ITA = TA.Addr->getOwner(DFG); in traverse()
1093 NodeAddr<BlockNode *> BTA = ITA.Addr->getOwner(DFG); in traverse()
1095 if (BTA.Addr->getCode() != B) { in traverse()
1098 // upward chain will be live. in traverse()
1108 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) in traverse()
1109 RRs.insert(TA.Addr->getRegRef(DFG)); in traverse()
1125 // Scan the block for upward-exposed uses and add them to the tracking set. in traverse()
1126 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { in traverse()
1128 if (IA.Addr->getKind() != NodeAttrs::Stmt) in traverse()
1130 for (NodeAddr<UseNode *> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { in traverse()
1131 if (UA.Addr->getFlags() & NodeAttrs::Undef) in traverse()
1133 RegisterRef RR = UA.Addr->getRegRef(DFG); in traverse()
1174 I = I->second.empty() ? M.erase(I) : std::next(I); in emptify()