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/STLExtras.h" 27 #include "llvm/ADT/SetVector.h" 28 #include "llvm/CodeGen/MachineBasicBlock.h" 29 #include "llvm/CodeGen/MachineDominanceFrontier.h" 30 #include "llvm/CodeGen/MachineDominators.h" 31 #include "llvm/CodeGen/MachineFunction.h" 32 #include "llvm/CodeGen/MachineInstr.h" 33 #include "llvm/CodeGen/RDFLiveness.h" 34 #include "llvm/CodeGen/RDFGraph.h" 35 #include "llvm/CodeGen/RDFRegisters.h" 36 #include "llvm/CodeGen/TargetRegisterInfo.h" 37 #include "llvm/MC/LaneBitmask.h" 38 #include "llvm/MC/MCRegisterInfo.h" 39 #include "llvm/Support/CommandLine.h" 40 #include "llvm/Support/Debug.h" 41 #include "llvm/Support/ErrorHandling.h" 42 #include "llvm/Support/raw_ostream.h" 43 #include <algorithm> 44 #include <cassert> 45 #include <cstdint> 46 #include <iterator> 47 #include <map> 48 #include <utility> 49 #include <vector> 50 51 using namespace llvm; 52 using namespace rdf; 53 54 static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25), 55 cl::Hidden, cl::desc("Maximum recursion level")); 56 57 namespace llvm { 58 namespace rdf { 59 60 raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) { 61 OS << '{'; 62 for (auto &I : P.Obj) { 63 OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{'; 64 for (auto J = I.second.begin(), E = I.second.end(); J != E; ) { 65 OS << Print<NodeId>(J->first, P.G) << PrintLaneMaskOpt(J->second); 66 if (++J != E) 67 OS << ','; 68 } 69 OS << '}'; 70 } 71 OS << " }"; 72 return OS; 73 } 74 75 } // end namespace rdf 76 } // end namespace llvm 77 78 // The order in the returned sequence is the order of reaching defs in the 79 // upward traversal: the first def is the closest to the given reference RefA, 80 // the next one is further up, and so on. 81 // The list ends at a reaching phi def, or when the reference from RefA is 82 // covered by the defs in the list (see FullChain). 83 // This function provides two modes of operation: 84 // (1) Returning the sequence of reaching defs for a particular reference 85 // node. This sequence will terminate at the first phi node [1]. 86 // (2) Returning a partial sequence of reaching defs, where the final goal 87 // is to traverse past phi nodes to the actual defs arising from the code 88 // itself. 89 // In mode (2), the register reference for which the search was started 90 // may be different from the reference node RefA, for which this call was 91 // made, hence the argument RefRR, which holds the original register. 92 // Also, some definitions may have already been encountered in a previous 93 // call that will influence register covering. The register references 94 // already defined are passed in through DefRRs. 95 // In mode (1), the "continuation" considerations do not apply, and the 96 // RefRR is the same as the register in RefA, and the set DefRRs is empty. 97 // 98 // [1] It is possible for multiple phi nodes to be included in the returned 99 // sequence: 100 // SubA = phi ... 101 // SubB = phi ... 102 // ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB) 103 // However, these phi nodes are independent from one another in terms of 104 // the data-flow. 105 106 NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, 107 NodeAddr<RefNode*> RefA, bool TopShadows, bool FullChain, 108 const RegisterAggr &DefRRs) { 109 NodeList RDefs; // Return value. 110 SetVector<NodeId> DefQ; 111 SetVector<NodeId> Owners; 112 113 // Dead defs will be treated as if they were live, since they are actually 114 // on the data-flow path. They cannot be ignored because even though they 115 // do not generate meaningful values, they still modify registers. 116 117 // If the reference is undefined, there is nothing to do. 118 if (RefA.Addr->getFlags() & NodeAttrs::Undef) 119 return RDefs; 120 121 // The initial queue should not have reaching defs for shadows. The 122 // whole point of a shadow is that it will have a reaching def that 123 // is not aliased to the reaching defs of the related shadows. 124 NodeId Start = RefA.Id; 125 auto SNA = DFG.addr<RefNode*>(Start); 126 if (NodeId RD = SNA.Addr->getReachingDef()) 127 DefQ.insert(RD); 128 if (TopShadows) { 129 for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA)) 130 if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) 131 DefQ.insert(RD); 132 } 133 134 // Collect all the reaching defs, going up until a phi node is encountered, 135 // or there are no more reaching defs. From this set, the actual set of 136 // reaching defs will be selected. 137 // The traversal upwards must go on until a covering def is encountered. 138 // It is possible that a collection of non-covering (individually) defs 139 // will be sufficient, but keep going until a covering one is found. 140 for (unsigned i = 0; i < DefQ.size(); ++i) { 141 auto TA = DFG.addr<DefNode*>(DefQ[i]); 142 if (TA.Addr->getFlags() & NodeAttrs::PhiRef) 143 continue; 144 // Stop at the covering/overwriting def of the initial register reference. 145 RegisterRef RR = TA.Addr->getRegRef(DFG); 146 if (!DFG.IsPreservingDef(TA)) 147 if (RegisterAggr::isCoverOf(RR, RefRR, PRI)) 148 continue; 149 // Get the next level of reaching defs. This will include multiple 150 // reaching defs for shadows. 151 for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) 152 if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) 153 DefQ.insert(RD); 154 } 155 156 // Remove all non-phi defs that are not aliased to RefRR, and collect 157 // the owners of the remaining defs. 158 SetVector<NodeId> Defs; 159 for (NodeId N : DefQ) { 160 auto TA = DFG.addr<DefNode*>(N); 161 bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; 162 if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG))) 163 continue; 164 Defs.insert(TA.Id); 165 Owners.insert(TA.Addr->getOwner(DFG).Id); 166 } 167 168 // Return the MachineBasicBlock containing a given instruction. 169 auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* { 170 if (IA.Addr->getKind() == NodeAttrs::Stmt) 171 return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent(); 172 assert(IA.Addr->getKind() == NodeAttrs::Phi); 173 NodeAddr<PhiNode*> PA = IA; 174 NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG); 175 return BA.Addr->getCode(); 176 }; 177 // Less(A,B) iff instruction A is further down in the dominator tree than B. 178 auto Less = [&Block,this] (NodeId A, NodeId B) -> bool { 179 if (A == B) 180 return false; 181 auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B); 182 MachineBasicBlock *BA = Block(OA), *BB = Block(OB); 183 if (BA != BB) 184 return MDT.dominates(BB, BA); 185 // They are in the same block. 186 bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; 187 bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; 188 if (StmtA) { 189 if (!StmtB) // OB is a phi and phis dominate statements. 190 return true; 191 MachineInstr *CA = NodeAddr<StmtNode*>(OA).Addr->getCode(); 192 MachineInstr *CB = NodeAddr<StmtNode*>(OB).Addr->getCode(); 193 // The order must be linear, so tie-break such equalities. 194 if (CA == CB) 195 return A < B; 196 return MDT.dominates(CB, CA); 197 } else { 198 // OA is a phi. 199 if (StmtB) 200 return false; 201 // Both are phis. There is no ordering between phis (in terms of 202 // the data-flow), so tie-break this via node id comparison. 203 return A < B; 204 } 205 }; 206 207 std::vector<NodeId> Tmp(Owners.begin(), Owners.end()); 208 llvm::sort(Tmp, Less); 209 210 // The vector is a list of instructions, so that defs coming from 211 // the same instruction don't need to be artificially ordered. 212 // Then, when computing the initial segment, and iterating over an 213 // instruction, pick the defs that contribute to the covering (i.e. is 214 // not covered by previously added defs). Check the defs individually, 215 // i.e. first check each def if is covered or not (without adding them 216 // to the tracking set), and then add all the selected ones. 217 218 // The reason for this is this example: 219 // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes). 220 // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be 221 // covered if we added A first, and A would be covered 222 // if we added B first. 223 224 RegisterAggr RRs(DefRRs); 225 226 auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool { 227 return TA.Addr->getKind() == NodeAttrs::Def && 228 Defs.count(TA.Id); 229 }; 230 for (NodeId T : Tmp) { 231 if (!FullChain && RRs.hasCoverOf(RefRR)) 232 break; 233 auto TA = DFG.addr<InstrNode*>(T); 234 bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA); 235 NodeList Ds; 236 for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) { 237 RegisterRef QR = DA.Addr->getRegRef(DFG); 238 // Add phi defs even if they are covered by subsequent defs. This is 239 // for cases where the reached use is not covered by any of the defs 240 // encountered so far: the phi def is needed to expose the liveness 241 // of that use to the entry of the block. 242 // Example: 243 // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2. 244 // d2<R3>(d1,,u3), ... 245 // ..., u3<D1>(d2) This use needs to be live on entry. 246 if (FullChain || IsPhi || !RRs.hasCoverOf(QR)) 247 Ds.push_back(DA); 248 } 249 RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); 250 for (NodeAddr<DefNode*> DA : Ds) { 251 // When collecting a full chain of definitions, do not consider phi 252 // defs to actually define a register. 253 uint16_t Flags = DA.Addr->getFlags(); 254 if (!FullChain || !(Flags & NodeAttrs::PhiRef)) 255 if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here. 256 RRs.insert(DA.Addr->getRegRef(DFG)); 257 } 258 } 259 260 auto DeadP = [](const NodeAddr<DefNode*> DA) -> bool { 261 return DA.Addr->getFlags() & NodeAttrs::Dead; 262 }; 263 RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP))); 264 265 return RDefs; 266 } 267 268 std::pair<NodeSet,bool> 269 Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 270 NodeSet &Visited, const NodeSet &Defs) { 271 return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest); 272 } 273 274 std::pair<NodeSet,bool> 275 Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 276 NodeSet &Visited, const NodeSet &Defs, unsigned Nest, unsigned MaxNest) { 277 if (Nest > MaxNest) 278 return { NodeSet(), false }; 279 // Collect all defined registers. Do not consider phis to be defining 280 // anything, only collect "real" definitions. 281 RegisterAggr DefRRs(PRI); 282 for (NodeId D : Defs) { 283 const auto DA = DFG.addr<const DefNode*>(D); 284 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 285 DefRRs.insert(DA.Addr->getRegRef(DFG)); 286 } 287 288 NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs); 289 if (RDs.empty()) 290 return { Defs, true }; 291 292 // Make a copy of the preexisting definitions and add the newly found ones. 293 NodeSet TmpDefs = Defs; 294 for (NodeAddr<NodeBase*> R : RDs) 295 TmpDefs.insert(R.Id); 296 297 NodeSet Result = Defs; 298 299 for (NodeAddr<DefNode*> DA : RDs) { 300 Result.insert(DA.Id); 301 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 302 continue; 303 NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG); 304 if (Visited.count(PA.Id)) 305 continue; 306 Visited.insert(PA.Id); 307 // Go over all phi uses and get the reaching defs for each use. 308 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 309 const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs, 310 Nest+1, MaxNest); 311 if (!T.second) 312 return { T.first, false }; 313 Result.insert(T.first.begin(), T.first.end()); 314 } 315 } 316 317 return { Result, true }; 318 } 319 320 /// Find the nearest ref node aliased to RefRR, going upwards in the data 321 /// flow, starting from the instruction immediately preceding Inst. 322 NodeAddr<RefNode*> Liveness::getNearestAliasedRef(RegisterRef RefRR, 323 NodeAddr<InstrNode*> IA) { 324 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 325 NodeList Ins = BA.Addr->members(DFG); 326 NodeId FindId = IA.Id; 327 auto E = Ins.rend(); 328 auto B = std::find_if(Ins.rbegin(), E, 329 [FindId] (const NodeAddr<InstrNode*> T) { 330 return T.Id == FindId; 331 }); 332 // Do not scan IA (which is what B would point to). 333 if (B != E) 334 ++B; 335 336 do { 337 // Process the range of instructions from B to E. 338 for (NodeAddr<InstrNode*> I : make_range(B, E)) { 339 NodeList Refs = I.Addr->members(DFG); 340 NodeAddr<RefNode*> Clob, Use; 341 // Scan all the refs in I aliased to RefRR, and return the one that 342 // is the closest to the output of I, i.e. def > clobber > use. 343 for (NodeAddr<RefNode*> R : Refs) { 344 if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR)) 345 continue; 346 if (DFG.IsDef(R)) { 347 // If it's a non-clobbering def, just return it. 348 if (!(R.Addr->getFlags() & NodeAttrs::Clobbering)) 349 return R; 350 Clob = R; 351 } else { 352 Use = R; 353 } 354 } 355 if (Clob.Id != 0) 356 return Clob; 357 if (Use.Id != 0) 358 return Use; 359 } 360 361 // Go up to the immediate dominator, if any. 362 MachineBasicBlock *BB = BA.Addr->getCode(); 363 BA = NodeAddr<BlockNode*>(); 364 if (MachineDomTreeNode *N = MDT.getNode(BB)) { 365 if ((N = N->getIDom())) 366 BA = DFG.findBlock(N->getBlock()); 367 } 368 if (!BA.Id) 369 break; 370 371 Ins = BA.Addr->members(DFG); 372 B = Ins.rbegin(); 373 E = Ins.rend(); 374 } while (true); 375 376 return NodeAddr<RefNode*>(); 377 } 378 379 NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, 380 NodeAddr<DefNode*> DefA, const RegisterAggr &DefRRs) { 381 NodeSet Uses; 382 383 // If the original register is already covered by all the intervening 384 // defs, no more uses can be reached. 385 if (DefRRs.hasCoverOf(RefRR)) 386 return Uses; 387 388 // Add all directly reached uses. 389 // If the def is dead, it does not provide a value for any use. 390 bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead; 391 NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0; 392 while (U != 0) { 393 auto UA = DFG.addr<UseNode*>(U); 394 if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) { 395 RegisterRef UR = UA.Addr->getRegRef(DFG); 396 if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR)) 397 Uses.insert(U); 398 } 399 U = UA.Addr->getSibling(); 400 } 401 402 // Traverse all reached defs. This time dead defs cannot be ignored. 403 for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { 404 auto DA = DFG.addr<DefNode*>(D); 405 NextD = DA.Addr->getSibling(); 406 RegisterRef DR = DA.Addr->getRegRef(DFG); 407 // If this def is already covered, it cannot reach anything new. 408 // Similarly, skip it if it is not aliased to the interesting register. 409 if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR)) 410 continue; 411 NodeSet T; 412 if (DFG.IsPreservingDef(DA)) { 413 // If it is a preserving def, do not update the set of intervening defs. 414 T = getAllReachedUses(RefRR, DA, DefRRs); 415 } else { 416 RegisterAggr NewDefRRs = DefRRs; 417 NewDefRRs.insert(DR); 418 T = getAllReachedUses(RefRR, DA, NewDefRRs); 419 } 420 Uses.insert(T.begin(), T.end()); 421 } 422 return Uses; 423 } 424 425 void Liveness::computePhiInfo() { 426 RealUseMap.clear(); 427 428 NodeList Phis; 429 NodeAddr<FuncNode*> FA = DFG.getFunc(); 430 NodeList Blocks = FA.Addr->members(DFG); 431 for (NodeAddr<BlockNode*> BA : Blocks) { 432 auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 433 Phis.insert(Phis.end(), Ps.begin(), Ps.end()); 434 } 435 436 // phi use -> (map: reaching phi -> set of registers defined in between) 437 std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp; 438 std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation. 439 std::map<NodeId,RegisterAggr> PhiDRs; // Phi -> registers defined by it. 440 441 // Go over all phis. 442 for (NodeAddr<PhiNode*> PhiA : Phis) { 443 // Go over all defs and collect the reached uses that are non-phi uses 444 // (i.e. the "real uses"). 445 RefMap &RealUses = RealUseMap[PhiA.Id]; 446 NodeList PhiRefs = PhiA.Addr->members(DFG); 447 448 // Have a work queue of defs whose reached uses need to be found. 449 // For each def, add to the queue all reached (non-phi) defs. 450 SetVector<NodeId> DefQ; 451 NodeSet PhiDefs; 452 RegisterAggr DRs(PRI); 453 for (NodeAddr<RefNode*> R : PhiRefs) { 454 if (!DFG.IsRef<NodeAttrs::Def>(R)) 455 continue; 456 DRs.insert(R.Addr->getRegRef(DFG)); 457 DefQ.insert(R.Id); 458 PhiDefs.insert(R.Id); 459 } 460 PhiDRs.insert(std::make_pair(PhiA.Id, DRs)); 461 462 // Collect the super-set of all possible reached uses. This set will 463 // contain all uses reached from this phi, either directly from the 464 // phi defs, or (recursively) via non-phi defs reached by the phi defs. 465 // This set of uses will later be trimmed to only contain these uses that 466 // are actually reached by the phi defs. 467 for (unsigned i = 0; i < DefQ.size(); ++i) { 468 NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]); 469 // Visit all reached uses. Phi defs should not really have the "dead" 470 // flag set, but check it anyway for consistency. 471 bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead; 472 NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0; 473 while (UN != 0) { 474 NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN); 475 uint16_t F = A.Addr->getFlags(); 476 if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { 477 RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG)); 478 RealUses[R.Reg].insert({A.Id,R.Mask}); 479 } 480 UN = A.Addr->getSibling(); 481 } 482 // Visit all reached defs, and add them to the queue. These defs may 483 // override some of the uses collected here, but that will be handled 484 // later. 485 NodeId DN = DA.Addr->getReachedDef(); 486 while (DN != 0) { 487 NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN); 488 for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { 489 uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags(); 490 // Must traverse the reached-def chain. Consider: 491 // def(D0) -> def(R0) -> def(R0) -> use(D0) 492 // The reachable use of D0 passes through a def of R0. 493 if (!(Flags & NodeAttrs::PhiRef)) 494 DefQ.insert(T.Id); 495 } 496 DN = A.Addr->getSibling(); 497 } 498 } 499 // Filter out these uses that appear to be reachable, but really 500 // are not. For example: 501 // 502 // R1:0 = d1 503 // = R1:0 u2 Reached by d1. 504 // R0 = d3 505 // = R1:0 u4 Still reached by d1: indirectly through 506 // the def d3. 507 // R1 = d5 508 // = R1:0 u6 Not reached by d1 (covered collectively 509 // by d3 and d5), but following reached 510 // defs and uses from d1 will lead here. 511 for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) { 512 // For each reached register UI->first, there is a set UI->second, of 513 // uses of it. For each such use, check if it is reached by this phi, 514 // i.e. check if the set of its reaching uses intersects the set of 515 // this phi's defs. 516 NodeRefSet Uses = UI->second; 517 UI->second.clear(); 518 for (std::pair<NodeId,LaneBitmask> I : Uses) { 519 auto UA = DFG.addr<UseNode*>(I.first); 520 // Undef flag is checked above. 521 assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); 522 RegisterRef R(UI->first, I.second); 523 // Calculate the exposed part of the reached use. 524 RegisterAggr Covered(PRI); 525 for (NodeAddr<DefNode*> DA : getAllReachingDefs(R, UA)) { 526 if (PhiDefs.count(DA.Id)) 527 break; 528 Covered.insert(DA.Addr->getRegRef(DFG)); 529 } 530 if (RegisterRef RC = Covered.clearIn(R)) { 531 // We are updating the map for register UI->first, so we need 532 // to map RC to be expressed in terms of that register. 533 RegisterRef S = PRI.mapTo(RC, UI->first); 534 UI->second.insert({I.first, S.Mask}); 535 } 536 } 537 UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI); 538 } 539 540 // If this phi reaches some "real" uses, add it to the queue for upward 541 // propagation. 542 if (!RealUses.empty()) 543 PhiUQ.push_back(PhiA.Id); 544 545 // Go over all phi uses and check if the reaching def is another phi. 546 // Collect the phis that are among the reaching defs of these uses. 547 // While traversing the list of reaching defs for each phi use, accumulate 548 // the set of registers defined between this phi (PhiA) and the owner phi 549 // of the reaching def. 550 NodeSet SeenUses; 551 552 for (auto I : PhiRefs) { 553 if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id)) 554 continue; 555 NodeAddr<PhiUseNode*> PUA = I; 556 if (PUA.Addr->getReachingDef() == 0) 557 continue; 558 559 RegisterRef UR = PUA.Addr->getRegRef(DFG); 560 NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs); 561 RegisterAggr DefRRs(PRI); 562 563 for (NodeAddr<DefNode*> D : Ds) { 564 if (D.Addr->getFlags() & NodeAttrs::PhiRef) { 565 NodeId RP = D.Addr->getOwner(DFG).Id; 566 std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.Id]; 567 auto F = M.find(RP); 568 if (F == M.end()) 569 M.insert(std::make_pair(RP, DefRRs)); 570 else 571 F->second.insert(DefRRs); 572 } 573 DefRRs.insert(D.Addr->getRegRef(DFG)); 574 } 575 576 for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PhiA, PUA)) 577 SeenUses.insert(T.Id); 578 } 579 } 580 581 if (Trace) { 582 dbgs() << "Phi-up-to-phi map with intervening defs:\n"; 583 for (auto I : PhiUp) { 584 dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {"; 585 for (auto R : I.second) 586 dbgs() << ' ' << Print<NodeId>(R.first, DFG) 587 << Print<RegisterAggr>(R.second, DFG); 588 dbgs() << " }\n"; 589 } 590 } 591 592 // Propagate the reached registers up in the phi chain. 593 // 594 // The following type of situation needs careful handling: 595 // 596 // phi d1<R1:0> (1) 597 // | 598 // ... d2<R1> 599 // | 600 // phi u3<R1:0> (2) 601 // | 602 // ... u4<R1> 603 // 604 // The phi node (2) defines a register pair R1:0, and reaches a "real" 605 // use u4 of just R1. The same phi node is also known to reach (upwards) 606 // the phi node (1). However, the use u4 is not reached by phi (1), 607 // because of the intervening definition d2 of R1. The data flow between 608 // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0. 609 // 610 // When propagating uses up the phi chains, get the all reaching defs 611 // for a given phi use, and traverse the list until the propagated ref 612 // is covered, or until reaching the final phi. Only assume that the 613 // reference reaches the phi in the latter case. 614 615 for (unsigned i = 0; i < PhiUQ.size(); ++i) { 616 auto PA = DFG.addr<PhiNode*>(PhiUQ[i]); 617 NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG); 618 RefMap &RUM = RealUseMap[PA.Id]; 619 620 for (NodeAddr<UseNode*> UA : PUs) { 621 std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id]; 622 RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG)); 623 for (const std::pair<const NodeId, RegisterAggr> &P : PUM) { 624 bool Changed = false; 625 const RegisterAggr &MidDefs = P.second; 626 627 // Collect the set PropUp of uses that are reached by the current 628 // phi PA, and are not covered by any intervening def between the 629 // currently visited use UA and the upward phi P. 630 631 if (MidDefs.hasCoverOf(UR)) 632 continue; 633 634 // General algorithm: 635 // for each (R,U) : U is use node of R, U is reached by PA 636 // if MidDefs does not cover (R,U) 637 // then add (R-MidDefs,U) to RealUseMap[P] 638 // 639 for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) { 640 RegisterRef R(T.first); 641 // The current phi (PA) could be a phi for a regmask. It could 642 // reach a whole variety of uses that are not related to the 643 // specific upward phi (P.first). 644 const RegisterAggr &DRs = PhiDRs.at(P.first); 645 if (!DRs.hasAliasOf(R)) 646 continue; 647 R = PRI.mapTo(DRs.intersectWith(R), T.first); 648 for (std::pair<NodeId,LaneBitmask> V : T.second) { 649 LaneBitmask M = R.Mask & V.second; 650 if (M.none()) 651 continue; 652 if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) { 653 NodeRefSet &RS = RealUseMap[P.first][SS.Reg]; 654 Changed |= RS.insert({V.first,SS.Mask}).second; 655 } 656 } 657 } 658 659 if (Changed) 660 PhiUQ.push_back(P.first); 661 } 662 } 663 } 664 665 if (Trace) { 666 dbgs() << "Real use map:\n"; 667 for (auto I : RealUseMap) { 668 dbgs() << "phi " << Print<NodeId>(I.first, DFG); 669 NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first); 670 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); 671 if (!Ds.empty()) { 672 RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(DFG); 673 dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>'; 674 } else { 675 dbgs() << "<noreg>"; 676 } 677 dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n'; 678 } 679 } 680 } 681 682 void Liveness::computeLiveIns() { 683 // Populate the node-to-block map. This speeds up the calculations 684 // significantly. 685 NBMap.clear(); 686 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 687 MachineBasicBlock *BB = BA.Addr->getCode(); 688 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 689 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 690 NBMap.insert(std::make_pair(RA.Id, BB)); 691 NBMap.insert(std::make_pair(IA.Id, BB)); 692 } 693 } 694 695 MachineFunction &MF = DFG.getMF(); 696 697 // Compute IDF first, then the inverse. 698 decltype(IIDF) IDF; 699 for (MachineBasicBlock &B : MF) { 700 auto F1 = MDF.find(&B); 701 if (F1 == MDF.end()) 702 continue; 703 SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end()); 704 for (unsigned i = 0; i < IDFB.size(); ++i) { 705 auto F2 = MDF.find(IDFB[i]); 706 if (F2 != MDF.end()) 707 IDFB.insert(F2->second.begin(), F2->second.end()); 708 } 709 // Add B to the IDF(B). This will put B in the IIDF(B). 710 IDFB.insert(&B); 711 IDF[&B].insert(IDFB.begin(), IDFB.end()); 712 } 713 714 for (auto I : IDF) 715 for (auto S : I.second) 716 IIDF[S].insert(I.first); 717 718 computePhiInfo(); 719 720 NodeAddr<FuncNode*> FA = DFG.getFunc(); 721 NodeList Blocks = FA.Addr->members(DFG); 722 723 // Build the phi live-on-entry map. 724 for (NodeAddr<BlockNode*> BA : Blocks) { 725 MachineBasicBlock *MB = BA.Addr->getCode(); 726 RefMap &LON = PhiLON[MB]; 727 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) 728 for (const RefMap::value_type &S : RealUseMap[P.Id]) 729 LON[S.first].insert(S.second.begin(), S.second.end()); 730 } 731 732 if (Trace) { 733 dbgs() << "Phi live-on-entry map:\n"; 734 for (auto &I : PhiLON) 735 dbgs() << "block #" << I.first->getNumber() << " -> " 736 << Print<RefMap>(I.second, DFG) << '\n'; 737 } 738 739 // Build the phi live-on-exit map. Each phi node has some set of reached 740 // "real" uses. Propagate this set backwards into the block predecessors 741 // through the reaching defs of the corresponding phi uses. 742 for (NodeAddr<BlockNode*> BA : Blocks) { 743 NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 744 for (NodeAddr<PhiNode*> PA : Phis) { 745 RefMap &RUs = RealUseMap[PA.Id]; 746 if (RUs.empty()) 747 continue; 748 749 NodeSet SeenUses; 750 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 751 if (!SeenUses.insert(U.Id).second) 752 continue; 753 NodeAddr<PhiUseNode*> PUA = U; 754 if (PUA.Addr->getReachingDef() == 0) 755 continue; 756 757 // Each phi has some set (possibly empty) of reached "real" uses, 758 // that is, uses that are part of the compiled program. Such a use 759 // may be located in some farther block, but following a chain of 760 // reaching defs will eventually lead to this phi. 761 // Any chain of reaching defs may fork at a phi node, but there 762 // will be a path upwards that will lead to this phi. Now, this 763 // chain will need to fork at this phi, since some of the reached 764 // uses may have definitions joining in from multiple predecessors. 765 // For each reached "real" use, identify the set of reaching defs 766 // coming from each predecessor P, and add them to PhiLOX[P]. 767 // 768 auto PrA = DFG.addr<BlockNode*>(PUA.Addr->getPredecessor()); 769 RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; 770 771 for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) { 772 // We need to visit each individual use. 773 for (std::pair<NodeId,LaneBitmask> P : RS.second) { 774 // Create a register ref corresponding to the use, and find 775 // all reaching defs starting from the phi use, and treating 776 // all related shadows as a single use cluster. 777 RegisterRef S(RS.first, P.second); 778 NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs); 779 for (NodeAddr<DefNode*> D : Ds) { 780 // Calculate the mask corresponding to the visited def. 781 RegisterAggr TA(PRI); 782 TA.insert(D.Addr->getRegRef(DFG)).intersect(S); 783 LaneBitmask TM = TA.makeRegRef().Mask; 784 LOX[S.Reg].insert({D.Id, TM}); 785 } 786 } 787 } 788 789 for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PA, PUA)) 790 SeenUses.insert(T.Id); 791 } // for U : phi uses 792 } // for P : Phis 793 } // for B : Blocks 794 795 if (Trace) { 796 dbgs() << "Phi live-on-exit map:\n"; 797 for (auto &I : PhiLOX) 798 dbgs() << "block #" << I.first->getNumber() << " -> " 799 << Print<RefMap>(I.second, DFG) << '\n'; 800 } 801 802 RefMap LiveIn; 803 traverse(&MF.front(), LiveIn); 804 805 // Add function live-ins to the live-in set of the function entry block. 806 LiveMap[&MF.front()].insert(DFG.getLiveIns()); 807 808 if (Trace) { 809 // Dump the liveness map 810 for (MachineBasicBlock &B : MF) { 811 std::vector<RegisterRef> LV; 812 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 813 LV.push_back(RegisterRef(I->PhysReg, I->LaneMask)); 814 llvm::sort(LV); 815 dbgs() << printMBBReference(B) << "\t rec = {"; 816 for (auto I : LV) 817 dbgs() << ' ' << Print<RegisterRef>(I, DFG); 818 dbgs() << " }\n"; 819 //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n'; 820 821 LV.clear(); 822 const RegisterAggr &LG = LiveMap[&B]; 823 for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I) 824 LV.push_back(*I); 825 llvm::sort(LV); 826 dbgs() << "\tcomp = {"; 827 for (auto I : LV) 828 dbgs() << ' ' << Print<RegisterRef>(I, DFG); 829 dbgs() << " }\n"; 830 831 } 832 } 833 } 834 835 void Liveness::resetLiveIns() { 836 for (auto &B : DFG.getMF()) { 837 // Remove all live-ins. 838 std::vector<unsigned> T; 839 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 840 T.push_back(I->PhysReg); 841 for (auto I : T) 842 B.removeLiveIn(I); 843 // Add the newly computed live-ins. 844 const RegisterAggr &LiveIns = LiveMap[&B]; 845 for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) { 846 RegisterRef R = *I; 847 B.addLiveIn({MCPhysReg(R.Reg), R.Mask}); 848 } 849 } 850 } 851 852 void Liveness::resetKills() { 853 for (auto &B : DFG.getMF()) 854 resetKills(&B); 855 } 856 857 void Liveness::resetKills(MachineBasicBlock *B) { 858 auto CopyLiveIns = [this] (MachineBasicBlock *B, BitVector &LV) -> void { 859 for (auto I : B->liveins()) { 860 MCSubRegIndexIterator S(I.PhysReg, &TRI); 861 if (!S.isValid()) { 862 LV.set(I.PhysReg); 863 continue; 864 } 865 do { 866 LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex()); 867 if ((M & I.LaneMask).any()) 868 LV.set(S.getSubReg()); 869 ++S; 870 } while (S.isValid()); 871 } 872 }; 873 874 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); 875 CopyLiveIns(B, LiveIn); 876 for (auto SI : B->successors()) 877 CopyLiveIns(SI, Live); 878 879 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { 880 MachineInstr *MI = &*I; 881 if (MI->isDebugInstr()) 882 continue; 883 884 MI->clearKillInfo(); 885 for (auto &Op : MI->operands()) { 886 // An implicit def of a super-register may not necessarily start a 887 // live range of it, since an implicit use could be used to keep parts 888 // of it live. Instead of analyzing the implicit operands, ignore 889 // implicit defs. 890 if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) 891 continue; 892 Register R = Op.getReg(); 893 if (!Register::isPhysicalRegister(R)) 894 continue; 895 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 896 Live.reset(*SR); 897 } 898 for (auto &Op : MI->operands()) { 899 if (!Op.isReg() || !Op.isUse() || Op.isUndef()) 900 continue; 901 Register R = Op.getReg(); 902 if (!Register::isPhysicalRegister(R)) 903 continue; 904 bool IsLive = false; 905 for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) { 906 if (!Live[*AR]) 907 continue; 908 IsLive = true; 909 break; 910 } 911 if (!IsLive) 912 Op.setIsKill(true); 913 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 914 Live.set(*SR); 915 } 916 } 917 } 918 919 // Helper function to obtain the basic block containing the reaching def 920 // of the given use. 921 MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { 922 auto F = NBMap.find(RN); 923 if (F != NBMap.end()) 924 return F->second; 925 llvm_unreachable("Node id not in map"); 926 } 927 928 void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { 929 // The LiveIn map, for each (physical) register, contains the set of live 930 // reaching defs of that register that are live on entry to the associated 931 // block. 932 933 // The summary of the traversal algorithm: 934 // 935 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B 936 // and (U \in IDF(B) or B dom U). 937 // 938 // for (C : children) { 939 // LU = {} 940 // traverse(C, LU) 941 // LiveUses += LU 942 // } 943 // 944 // LiveUses -= Defs(B); 945 // LiveUses += UpwardExposedUses(B); 946 // for (C : IIDF[B]) 947 // for (U : LiveUses) 948 // if (Rdef(U) dom C) 949 // C.addLiveIn(U) 950 // 951 952 // Go up the dominator tree (depth-first). 953 MachineDomTreeNode *N = MDT.getNode(B); 954 for (auto I : *N) { 955 RefMap L; 956 MachineBasicBlock *SB = I->getBlock(); 957 traverse(SB, L); 958 959 for (auto S : L) 960 LiveIn[S.first].insert(S.second.begin(), S.second.end()); 961 } 962 963 if (Trace) { 964 dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__ 965 << " after recursion into: {"; 966 for (auto I : *N) 967 dbgs() << ' ' << I->getBlock()->getNumber(); 968 dbgs() << " }\n"; 969 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 970 dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; 971 } 972 973 // Add reaching defs of phi uses that are live on exit from this block. 974 RefMap &PUs = PhiLOX[B]; 975 for (auto &S : PUs) 976 LiveIn[S.first].insert(S.second.begin(), S.second.end()); 977 978 if (Trace) { 979 dbgs() << "after LOX\n"; 980 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 981 dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; 982 } 983 984 // The LiveIn map at this point has all defs that are live-on-exit from B, 985 // as if they were live-on-entry to B. First, we need to filter out all 986 // defs that are present in this block. Then we will add reaching defs of 987 // all upward-exposed uses. 988 989 // To filter out the defs, first make a copy of LiveIn, and then re-populate 990 // LiveIn with the defs that should remain. 991 RefMap LiveInCopy = LiveIn; 992 LiveIn.clear(); 993 994 for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) { 995 RegisterRef LRef(LE.first); 996 NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled. 997 const NodeRefSet &OldDefs = LE.second; 998 for (NodeRef OR : OldDefs) { 999 // R is a def node that was live-on-exit 1000 auto DA = DFG.addr<DefNode*>(OR.first); 1001 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); 1002 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 1003 if (B != BA.Addr->getCode()) { 1004 // Defs from a different block need to be preserved. Defs from this 1005 // block will need to be processed further, except for phi defs, the 1006 // liveness of which is handled through the PhiLON/PhiLOX maps. 1007 NewDefs.insert(OR); 1008 continue; 1009 } 1010 1011 // Defs from this block need to stop the liveness from being 1012 // propagated upwards. This only applies to non-preserving defs, 1013 // and to the parts of the register actually covered by those defs. 1014 // (Note that phi defs should always be preserving.) 1015 RegisterAggr RRs(PRI); 1016 LRef.Mask = OR.second; 1017 1018 if (!DFG.IsPreservingDef(DA)) { 1019 assert(!(IA.Addr->getFlags() & NodeAttrs::Phi)); 1020 // DA is a non-phi def that is live-on-exit from this block, and 1021 // that is also located in this block. LRef is a register ref 1022 // whose use this def reaches. If DA covers LRef, then no part 1023 // of LRef is exposed upwards.A 1024 if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef)) 1025 continue; 1026 } 1027 1028 // DA itself was not sufficient to cover LRef. In general, it is 1029 // the last in a chain of aliased defs before the exit from this block. 1030 // There could be other defs in this block that are a part of that 1031 // chain. Check that now: accumulate the registers from these defs, 1032 // and if they all together cover LRef, it is not live-on-entry. 1033 for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) { 1034 // DefNode -> InstrNode -> BlockNode. 1035 NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG); 1036 NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG); 1037 // Reaching defs are ordered in the upward direction. 1038 if (BTA.Addr->getCode() != B) { 1039 // We have reached past the beginning of B, and the accumulated 1040 // registers are not covering LRef. The first def from the 1041 // upward chain will be live. 1042 // Subtract all accumulated defs (RRs) from LRef. 1043 RegisterRef T = RRs.clearIn(LRef); 1044 assert(T); 1045 NewDefs.insert({TA.Id,T.Mask}); 1046 break; 1047 } 1048 1049 // TA is in B. Only add this def to the accumulated cover if it is 1050 // not preserving. 1051 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) 1052 RRs.insert(TA.Addr->getRegRef(DFG)); 1053 // If this is enough to cover LRef, then stop. 1054 if (RRs.hasCoverOf(LRef)) 1055 break; 1056 } 1057 } 1058 } 1059 1060 emptify(LiveIn); 1061 1062 if (Trace) { 1063 dbgs() << "after defs in block\n"; 1064 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 1065 dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; 1066 } 1067 1068 // Scan the block for upward-exposed uses and add them to the tracking set. 1069 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { 1070 NodeAddr<InstrNode*> IA = I; 1071 if (IA.Addr->getKind() != NodeAttrs::Stmt) 1072 continue; 1073 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { 1074 if (UA.Addr->getFlags() & NodeAttrs::Undef) 1075 continue; 1076 RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG)); 1077 for (NodeAddr<DefNode*> D : getAllReachingDefs(UA)) 1078 if (getBlockWithRef(D.Id) != B) 1079 LiveIn[RR.Reg].insert({D.Id,RR.Mask}); 1080 } 1081 } 1082 1083 if (Trace) { 1084 dbgs() << "after uses in block\n"; 1085 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 1086 dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; 1087 } 1088 1089 // Phi uses should not be propagated up the dominator tree, since they 1090 // are not dominated by their corresponding reaching defs. 1091 RegisterAggr &Local = LiveMap[B]; 1092 RefMap &LON = PhiLON[B]; 1093 for (auto &R : LON) { 1094 LaneBitmask M; 1095 for (auto P : R.second) 1096 M |= P.second; 1097 Local.insert(RegisterRef(R.first,M)); 1098 } 1099 1100 if (Trace) { 1101 dbgs() << "after phi uses in block\n"; 1102 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 1103 dbgs() << " Local: " << Print<RegisterAggr>(Local, DFG) << '\n'; 1104 } 1105 1106 for (auto C : IIDF[B]) { 1107 RegisterAggr &LiveC = LiveMap[C]; 1108 for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn) 1109 for (auto R : S.second) 1110 if (MDT.properlyDominates(getBlockWithRef(R.first), C)) 1111 LiveC.insert(RegisterRef(S.first, R.second)); 1112 } 1113 } 1114 1115 void Liveness::emptify(RefMap &M) { 1116 for (auto I = M.begin(), E = M.end(); I != E; ) 1117 I = I->second.empty() ? M.erase(I) : std::next(I); 1118 } 1119