1 //===--- RDFLiveness.cpp --------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Computation of the liveness information from the data-flow graph. 11 // 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. 15 // 16 // The block live-in calculation is based on the ideas from the following 17 // publication: 18 // 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> 25 // 26 #include "RDFGraph.h" 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" 35 36 using namespace llvm; 37 using namespace rdf; 38 39 namespace llvm { 40 namespace rdf { 41 template<> 42 raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) { 43 OS << '{'; 44 for (auto I : P.Obj) { 45 OS << ' ' << Print<RegisterRef>(I.first, P.G) << '{'; 46 for (auto J = I.second.begin(), E = I.second.end(); J != E; ) { 47 OS << Print<NodeId>(*J, P.G); 48 if (++J != E) 49 OS << ','; 50 } 51 OS << '}'; 52 } 53 OS << " }"; 54 return OS; 55 } 56 } // namespace rdf 57 } // namespace llvm 58 59 // The order in the returned sequence is the order of reaching defs in the 60 // upward traversal: the first def is the closest to the given reference RefA, 61 // the next one is further up, and so on. 62 // The list ends at a reaching phi def, or when the reference from RefA is 63 // covered by the defs in the list (see FullChain). 64 // This function provides two modes of operation: 65 // (1) Returning the sequence of reaching defs for a particular reference 66 // node. This sequence will terminate at the first phi node [1]. 67 // (2) Returning a partial sequence of reaching defs, where the final goal 68 // is to traverse past phi nodes to the actual defs arising from the code 69 // itself. 70 // In mode (2), the register reference for which the search was started 71 // may be different from the reference node RefA, for which this call was 72 // made, hence the argument RefRR, which holds the original register. 73 // Also, some definitions may have already been encountered in a previous 74 // call that will influence register covering. The register references 75 // already defined are passed in through DefRRs. 76 // In mode (1), the "continuation" considerations do not apply, and the 77 // RefRR is the same as the register in RefA, and the set DefRRs is empty. 78 // 79 // [1] It is possible for multiple phi nodes to be included in the returned 80 // sequence: 81 // SubA = phi ... 82 // SubB = phi ... 83 // ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB) 84 // However, these phi nodes are independent from one another in terms of 85 // the data-flow. 86 87 NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, 88 NodeAddr<RefNode*> RefA, bool FullChain, const RegisterSet &DefRRs) { 89 SetVector<NodeId> DefQ; 90 SetVector<NodeId> Owners; 91 92 // The initial queue should not have reaching defs for shadows. The 93 // whole point of a shadow is that it will have a reaching def that 94 // is not aliased to the reaching defs of the related shadows. 95 NodeId Start = RefA.Id; 96 auto SNA = DFG.addr<RefNode*>(Start); 97 if (NodeId RD = SNA.Addr->getReachingDef()) 98 DefQ.insert(RD); 99 100 // Collect all the reaching defs, going up until a phi node is encountered, 101 // or there are no more reaching defs. From this set, the actual set of 102 // reaching defs will be selected. 103 // The traversal upwards must go on until a covering def is encountered. 104 // It is possible that a collection of non-covering (individually) defs 105 // will be sufficient, but keep going until a covering one is found. 106 for (unsigned i = 0; i < DefQ.size(); ++i) { 107 auto TA = DFG.addr<DefNode*>(DefQ[i]); 108 if (TA.Addr->getFlags() & NodeAttrs::PhiRef) 109 continue; 110 // Stop at the covering/overwriting def of the initial register reference. 111 RegisterRef RR = TA.Addr->getRegRef(); 112 if (RAI.covers(RR, RefRR)) { 113 uint16_t Flags = TA.Addr->getFlags(); 114 if (!(Flags & NodeAttrs::Preserving)) 115 continue; 116 } 117 // Get the next level of reaching defs. This will include multiple 118 // reaching defs for shadows. 119 for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) 120 if (auto RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) 121 DefQ.insert(RD); 122 } 123 124 // Remove all non-phi defs that are not aliased to RefRR, and collect 125 // the owners of the remaining defs. 126 SetVector<NodeId> Defs; 127 for (auto N : DefQ) { 128 auto TA = DFG.addr<DefNode*>(N); 129 bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; 130 if (!IsPhi && !RAI.alias(RefRR, TA.Addr->getRegRef())) 131 continue; 132 Defs.insert(TA.Id); 133 Owners.insert(TA.Addr->getOwner(DFG).Id); 134 } 135 136 // Return the MachineBasicBlock containing a given instruction. 137 auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* { 138 if (IA.Addr->getKind() == NodeAttrs::Stmt) 139 return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent(); 140 assert(IA.Addr->getKind() == NodeAttrs::Phi); 141 NodeAddr<PhiNode*> PA = IA; 142 NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG); 143 return BA.Addr->getCode(); 144 }; 145 // Less(A,B) iff instruction A is further down in the dominator tree than B. 146 auto Less = [&Block,this] (NodeId A, NodeId B) -> bool { 147 if (A == B) 148 return false; 149 auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B); 150 MachineBasicBlock *BA = Block(OA), *BB = Block(OB); 151 if (BA != BB) 152 return MDT.dominates(BB, BA); 153 // They are in the same block. 154 bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; 155 bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; 156 if (StmtA) { 157 if (!StmtB) // OB is a phi and phis dominate statements. 158 return true; 159 auto CA = NodeAddr<StmtNode*>(OA).Addr->getCode(); 160 auto CB = NodeAddr<StmtNode*>(OB).Addr->getCode(); 161 // The order must be linear, so tie-break such equalities. 162 if (CA == CB) 163 return A < B; 164 return MDT.dominates(CB, CA); 165 } else { 166 // OA is a phi. 167 if (StmtB) 168 return false; 169 // Both are phis. There is no ordering between phis (in terms of 170 // the data-flow), so tie-break this via node id comparison. 171 return A < B; 172 } 173 }; 174 175 std::vector<NodeId> Tmp(Owners.begin(), Owners.end()); 176 std::sort(Tmp.begin(), Tmp.end(), Less); 177 178 // The vector is a list of instructions, so that defs coming from 179 // the same instruction don't need to be artificially ordered. 180 // Then, when computing the initial segment, and iterating over an 181 // instruction, pick the defs that contribute to the covering (i.e. is 182 // not covered by previously added defs). Check the defs individually, 183 // i.e. first check each def if is covered or not (without adding them 184 // to the tracking set), and then add all the selected ones. 185 186 // The reason for this is this example: 187 // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes). 188 // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be 189 // covered if we added A first, and A would be covered 190 // if we added B first. 191 192 NodeList RDefs; 193 RegisterSet RRs = DefRRs; 194 195 auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool { 196 return TA.Addr->getKind() == NodeAttrs::Def && 197 Defs.count(TA.Id); 198 }; 199 for (auto T : Tmp) { 200 if (!FullChain && RAI.covers(RRs, RefRR)) 201 break; 202 auto TA = DFG.addr<InstrNode*>(T); 203 bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA); 204 NodeList Ds; 205 for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) { 206 auto QR = DA.Addr->getRegRef(); 207 // Add phi defs even if they are covered by subsequent defs. This is 208 // for cases where the reached use is not covered by any of the defs 209 // encountered so far: the phi def is needed to expose the liveness 210 // of that use to the entry of the block. 211 // Example: 212 // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2. 213 // d2<R3>(d1,,u3), ... 214 // ..., u3<D1>(d2) This use needs to be live on entry. 215 if (FullChain || IsPhi || !RAI.covers(RRs, QR)) 216 Ds.push_back(DA); 217 } 218 RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); 219 for (NodeAddr<DefNode*> DA : Ds) { 220 // When collecting a full chain of definitions, do not consider phi 221 // defs to actually define a register. 222 uint16_t Flags = DA.Addr->getFlags(); 223 if (!FullChain || !(Flags & NodeAttrs::PhiRef)) 224 if (!(Flags & NodeAttrs::Preserving)) 225 RRs.insert(DA.Addr->getRegRef()); 226 } 227 } 228 229 return RDefs; 230 } 231 232 233 static const RegisterSet NoRegs; 234 235 NodeList Liveness::getAllReachingDefs(NodeAddr<RefNode*> RefA) { 236 return getAllReachingDefs(RefA.Addr->getRegRef(), RefA, false, NoRegs); 237 } 238 239 240 NodeSet Liveness::getAllReachingDefsRec(RegisterRef RefRR, 241 NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs) { 242 // Collect all defined registers. Do not consider phis to be defining 243 // anything, only collect "real" definitions. 244 RegisterSet DefRRs; 245 for (const auto D : Defs) { 246 const auto DA = DFG.addr<const DefNode*>(D); 247 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 248 DefRRs.insert(DA.Addr->getRegRef()); 249 } 250 251 auto RDs = getAllReachingDefs(RefRR, RefA, true, DefRRs); 252 if (RDs.empty()) 253 return Defs; 254 255 // Make a copy of the preexisting definitions and add the newly found ones. 256 NodeSet TmpDefs = Defs; 257 for (auto R : RDs) 258 TmpDefs.insert(R.Id); 259 260 NodeSet Result = Defs; 261 262 for (NodeAddr<DefNode*> DA : RDs) { 263 Result.insert(DA.Id); 264 if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 265 continue; 266 NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG); 267 if (Visited.count(PA.Id)) 268 continue; 269 Visited.insert(PA.Id); 270 // Go over all phi uses and get the reaching defs for each use. 271 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 272 const auto &T = getAllReachingDefsRec(RefRR, U, Visited, TmpDefs); 273 Result.insert(T.begin(), T.end()); 274 } 275 } 276 277 return Result; 278 } 279 280 281 NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, 282 NodeAddr<DefNode*> DefA, const RegisterSet &DefRRs) { 283 NodeSet Uses; 284 285 // If the original register is already covered by all the intervening 286 // defs, no more uses can be reached. 287 if (RAI.covers(DefRRs, RefRR)) 288 return Uses; 289 290 // Add all directly reached uses. 291 NodeId U = DefA.Addr->getReachedUse(); 292 while (U != 0) { 293 auto UA = DFG.addr<UseNode*>(U); 294 auto UR = UA.Addr->getRegRef(); 295 if (RAI.alias(RefRR, UR) && !RAI.covers(DefRRs, UR)) 296 Uses.insert(U); 297 U = UA.Addr->getSibling(); 298 } 299 300 // Traverse all reached defs. 301 for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { 302 auto DA = DFG.addr<DefNode*>(D); 303 NextD = DA.Addr->getSibling(); 304 auto DR = DA.Addr->getRegRef(); 305 // If this def is already covered, it cannot reach anything new. 306 // Similarly, skip it if it is not aliased to the interesting register. 307 if (RAI.covers(DefRRs, DR) || !RAI.alias(RefRR, DR)) 308 continue; 309 NodeSet T; 310 if (DA.Addr->getFlags() & NodeAttrs::Preserving) { 311 // If it is a preserving def, do not update the set of intervening defs. 312 T = getAllReachedUses(RefRR, DA, DefRRs); 313 } else { 314 RegisterSet NewDefRRs = DefRRs; 315 NewDefRRs.insert(DR); 316 T = getAllReachedUses(RefRR, DA, NewDefRRs); 317 } 318 Uses.insert(T.begin(), T.end()); 319 } 320 return Uses; 321 } 322 323 324 void Liveness::computePhiInfo() { 325 RealUseMap.clear(); 326 327 NodeList Phis; 328 NodeAddr<FuncNode*> FA = DFG.getFunc(); 329 auto Blocks = FA.Addr->members(DFG); 330 for (NodeAddr<BlockNode*> BA : Blocks) { 331 auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 332 Phis.insert(Phis.end(), Ps.begin(), Ps.end()); 333 } 334 335 // phi use -> (map: reaching phi -> set of registers defined in between) 336 std::map<NodeId,std::map<NodeId,RegisterSet>> PhiUp; 337 std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation. 338 339 // Go over all phis. 340 for (NodeAddr<PhiNode*> PhiA : Phis) { 341 // Go over all defs and collect the reached uses that are non-phi uses 342 // (i.e. the "real uses"). 343 auto &RealUses = RealUseMap[PhiA.Id]; 344 auto PhiRefs = PhiA.Addr->members(DFG); 345 346 // Have a work queue of defs whose reached uses need to be found. 347 // For each def, add to the queue all reached (non-phi) defs. 348 SetVector<NodeId> DefQ; 349 NodeSet PhiDefs; 350 for (auto R : PhiRefs) { 351 if (!DFG.IsRef<NodeAttrs::Def>(R)) 352 continue; 353 DefQ.insert(R.Id); 354 PhiDefs.insert(R.Id); 355 } 356 for (unsigned i = 0; i < DefQ.size(); ++i) { 357 NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]); 358 NodeId UN = DA.Addr->getReachedUse(); 359 while (UN != 0) { 360 NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN); 361 if (!(A.Addr->getFlags() & NodeAttrs::PhiRef)) 362 RealUses[getRestrictedRegRef(A)].insert(A.Id); 363 UN = A.Addr->getSibling(); 364 } 365 NodeId DN = DA.Addr->getReachedDef(); 366 while (DN != 0) { 367 NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN); 368 for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { 369 uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags(); 370 // Must traverse the reached-def chain. Consider: 371 // def(D0) -> def(R0) -> def(R0) -> use(D0) 372 // The reachable use of D0 passes through a def of R0. 373 if (!(Flags & NodeAttrs::PhiRef)) 374 DefQ.insert(T.Id); 375 } 376 DN = A.Addr->getSibling(); 377 } 378 } 379 // Filter out these uses that appear to be reachable, but really 380 // are not. For example: 381 // 382 // R1:0 = d1 383 // = R1:0 u2 Reached by d1. 384 // R0 = d3 385 // = R1:0 u4 Still reached by d1: indirectly through 386 // the def d3. 387 // R1 = d5 388 // = R1:0 u6 Not reached by d1 (covered collectively 389 // by d3 and d5), but following reached 390 // defs and uses from d1 will lead here. 391 auto HasDef = [&PhiDefs] (NodeAddr<DefNode*> DA) -> bool { 392 return PhiDefs.count(DA.Id); 393 }; 394 for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) { 395 // For each reached register UI->first, there is a set UI->second, of 396 // uses of it. For each such use, check if it is reached by this phi, 397 // i.e. check if the set of its reaching uses intersects the set of 398 // this phi's defs. 399 auto &Uses = UI->second; 400 for (auto I = Uses.begin(), E = Uses.end(); I != E; ) { 401 auto UA = DFG.addr<UseNode*>(*I); 402 NodeList RDs = getAllReachingDefs(UI->first, UA); 403 if (std::any_of(RDs.begin(), RDs.end(), HasDef)) 404 ++I; 405 else 406 I = Uses.erase(I); 407 } 408 if (Uses.empty()) 409 UI = RealUses.erase(UI); 410 else 411 ++UI; 412 } 413 414 // If this phi reaches some "real" uses, add it to the queue for upward 415 // propagation. 416 if (!RealUses.empty()) 417 PhiUQ.push_back(PhiA.Id); 418 419 // Go over all phi uses and check if the reaching def is another phi. 420 // Collect the phis that are among the reaching defs of these uses. 421 // While traversing the list of reaching defs for each phi use, collect 422 // the set of registers defined between this phi (Phi) and the owner phi 423 // of the reaching def. 424 for (auto I : PhiRefs) { 425 if (!DFG.IsRef<NodeAttrs::Use>(I)) 426 continue; 427 NodeAddr<UseNode*> UA = I; 428 auto &UpMap = PhiUp[UA.Id]; 429 RegisterSet DefRRs; 430 for (NodeAddr<DefNode*> DA : getAllReachingDefs(UA)) { 431 if (DA.Addr->getFlags() & NodeAttrs::PhiRef) 432 UpMap[DA.Addr->getOwner(DFG).Id] = DefRRs; 433 else 434 DefRRs.insert(DA.Addr->getRegRef()); 435 } 436 } 437 } 438 439 if (Trace) { 440 dbgs() << "Phi-up-to-phi map:\n"; 441 for (auto I : PhiUp) { 442 dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {"; 443 for (auto R : I.second) 444 dbgs() << ' ' << Print<NodeId>(R.first, DFG) 445 << Print<RegisterSet>(R.second, DFG); 446 dbgs() << " }\n"; 447 } 448 } 449 450 // Propagate the reached registers up in the phi chain. 451 // 452 // The following type of situation needs careful handling: 453 // 454 // phi d1<R1:0> (1) 455 // | 456 // ... d2<R1> 457 // | 458 // phi u3<R1:0> (2) 459 // | 460 // ... u4<R1> 461 // 462 // The phi node (2) defines a register pair R1:0, and reaches a "real" 463 // use u4 of just R1. The same phi node is also known to reach (upwards) 464 // the phi node (1). However, the use u4 is not reached by phi (1), 465 // because of the intervening definition d2 of R1. The data flow between 466 // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0. 467 // 468 // When propagating uses up the phi chains, get the all reaching defs 469 // for a given phi use, and traverse the list until the propagated ref 470 // is covered, or until or until reaching the final phi. Only assume 471 // that the reference reaches the phi in the latter case. 472 473 for (unsigned i = 0; i < PhiUQ.size(); ++i) { 474 auto PA = DFG.addr<PhiNode*>(PhiUQ[i]); 475 auto &RealUses = RealUseMap[PA.Id]; 476 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 477 NodeAddr<UseNode*> UA = U; 478 auto &UpPhis = PhiUp[UA.Id]; 479 for (auto UP : UpPhis) { 480 bool Changed = false; 481 auto &MidDefs = UP.second; 482 // Collect the set UpReached of uses that are reached by the current 483 // phi PA, and are not covered by any intervening def between PA and 484 // the upward phi UP. 485 RegisterSet UpReached; 486 for (auto T : RealUses) { 487 if (!isRestricted(PA, UA, T.first)) 488 continue; 489 if (!RAI.covers(MidDefs, T.first)) 490 UpReached.insert(T.first); 491 } 492 if (UpReached.empty()) 493 continue; 494 // Update the set PRUs of real uses reached by the upward phi UP with 495 // the actual set of uses (UpReached) that the UP phi reaches. 496 auto &PRUs = RealUseMap[UP.first]; 497 for (auto R : UpReached) { 498 unsigned Z = PRUs[R].size(); 499 PRUs[R].insert(RealUses[R].begin(), RealUses[R].end()); 500 Changed |= (PRUs[R].size() != Z); 501 } 502 if (Changed) 503 PhiUQ.push_back(UP.first); 504 } 505 } 506 } 507 508 if (Trace) { 509 dbgs() << "Real use map:\n"; 510 for (auto I : RealUseMap) { 511 dbgs() << "phi " << Print<NodeId>(I.first, DFG); 512 NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first); 513 NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); 514 if (!Ds.empty()) { 515 RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(); 516 dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>'; 517 } else { 518 dbgs() << "<noreg>"; 519 } 520 dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n'; 521 } 522 } 523 } 524 525 526 void Liveness::computeLiveIns() { 527 // Populate the node-to-block map. This speeds up the calculations 528 // significantly. 529 NBMap.clear(); 530 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 531 MachineBasicBlock *BB = BA.Addr->getCode(); 532 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 533 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 534 NBMap.insert(std::make_pair(RA.Id, BB)); 535 NBMap.insert(std::make_pair(IA.Id, BB)); 536 } 537 } 538 539 MachineFunction &MF = DFG.getMF(); 540 541 // Compute IDF first, then the inverse. 542 decltype(IIDF) IDF; 543 for (auto &B : MF) { 544 auto F1 = MDF.find(&B); 545 if (F1 == MDF.end()) 546 continue; 547 SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end()); 548 for (unsigned i = 0; i < IDFB.size(); ++i) { 549 auto F2 = MDF.find(IDFB[i]); 550 if (F2 != MDF.end()) 551 IDFB.insert(F2->second.begin(), F2->second.end()); 552 } 553 // Add B to the IDF(B). This will put B in the IIDF(B). 554 IDFB.insert(&B); 555 IDF[&B].insert(IDFB.begin(), IDFB.end()); 556 } 557 558 for (auto I : IDF) 559 for (auto S : I.second) 560 IIDF[S].insert(I.first); 561 562 computePhiInfo(); 563 564 NodeAddr<FuncNode*> FA = DFG.getFunc(); 565 auto Blocks = FA.Addr->members(DFG); 566 567 // Build the phi live-on-entry map. 568 for (NodeAddr<BlockNode*> BA : Blocks) { 569 MachineBasicBlock *MB = BA.Addr->getCode(); 570 auto &LON = PhiLON[MB]; 571 for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) 572 for (auto S : RealUseMap[P.Id]) 573 LON[S.first].insert(S.second.begin(), S.second.end()); 574 } 575 576 if (Trace) { 577 dbgs() << "Phi live-on-entry map:\n"; 578 for (auto I : PhiLON) 579 dbgs() << "block #" << I.first->getNumber() << " -> " 580 << Print<RefMap>(I.second, DFG) << '\n'; 581 } 582 583 // Build the phi live-on-exit map. Each phi node has some set of reached 584 // "real" uses. Propagate this set backwards into the block predecessors 585 // through the reaching defs of the corresponding phi uses. 586 for (NodeAddr<BlockNode*> BA : Blocks) { 587 auto Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 588 for (NodeAddr<PhiNode*> PA : Phis) { 589 auto &RUs = RealUseMap[PA.Id]; 590 if (RUs.empty()) 591 continue; 592 593 for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 594 NodeAddr<PhiUseNode*> UA = U; 595 if (UA.Addr->getReachingDef() == 0) 596 continue; 597 598 // Mark all reached "real" uses of P as live on exit in the 599 // predecessor. 600 // Remap all the RUs so that they have a correct reaching def. 601 auto PrA = DFG.addr<BlockNode*>(UA.Addr->getPredecessor()); 602 auto &LOX = PhiLOX[PrA.Addr->getCode()]; 603 for (auto R : RUs) { 604 RegisterRef RR = R.first; 605 if (!isRestricted(PA, UA, RR)) 606 RR = getRestrictedRegRef(UA); 607 // The restricted ref may be different from the ref that was 608 // accessed in the "real use". This means that this phi use 609 // is not the one that carries this reference, so skip it. 610 if (!RAI.alias(R.first, RR)) 611 continue; 612 for (auto D : getAllReachingDefs(RR, UA)) 613 LOX[RR].insert(D.Id); 614 } 615 } // for U : phi uses 616 } // for P : Phis 617 } // for B : Blocks 618 619 if (Trace) { 620 dbgs() << "Phi live-on-exit map:\n"; 621 for (auto I : PhiLOX) 622 dbgs() << "block #" << I.first->getNumber() << " -> " 623 << Print<RefMap>(I.second, DFG) << '\n'; 624 } 625 626 RefMap LiveIn; 627 traverse(&MF.front(), LiveIn); 628 629 // Add function live-ins to the live-in set of the function entry block. 630 auto &EntryIn = LiveMap[&MF.front()]; 631 for (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I) 632 EntryIn.insert({I->first,0}); 633 634 if (Trace) { 635 // Dump the liveness map 636 for (auto &B : MF) { 637 BitVector LV(TRI.getNumRegs()); 638 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 639 LV.set(I->PhysReg); 640 dbgs() << "BB#" << B.getNumber() << "\t rec = {"; 641 for (int x = LV.find_first(); x >= 0; x = LV.find_next(x)) 642 dbgs() << ' ' << Print<RegisterRef>({unsigned(x),0}, DFG); 643 dbgs() << " }\n"; 644 dbgs() << "\tcomp = " << Print<RegisterSet>(LiveMap[&B], DFG) << '\n'; 645 } 646 } 647 } 648 649 650 void Liveness::resetLiveIns() { 651 for (auto &B : DFG.getMF()) { 652 // Remove all live-ins. 653 std::vector<unsigned> T; 654 for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 655 T.push_back(I->PhysReg); 656 for (auto I : T) 657 B.removeLiveIn(I); 658 // Add the newly computed live-ins. 659 auto &LiveIns = LiveMap[&B]; 660 for (auto I : LiveIns) { 661 assert(I.Sub == 0); 662 B.addLiveIn(I.Reg); 663 } 664 } 665 } 666 667 668 void Liveness::resetKills() { 669 for (auto &B : DFG.getMF()) 670 resetKills(&B); 671 } 672 673 674 void Liveness::resetKills(MachineBasicBlock *B) { 675 auto CopyLiveIns = [] (MachineBasicBlock *B, BitVector &LV) -> void { 676 for (auto I = B->livein_begin(), E = B->livein_end(); I != E; ++I) 677 LV.set(I->PhysReg); 678 }; 679 680 BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); 681 CopyLiveIns(B, LiveIn); 682 for (auto SI : B->successors()) 683 CopyLiveIns(SI, Live); 684 685 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { 686 MachineInstr *MI = &*I; 687 if (MI->isDebugValue()) 688 continue; 689 690 MI->clearKillInfo(); 691 for (auto &Op : MI->operands()) { 692 // An implicit def of a super-register may not necessarily start a 693 // live range of it, since an implicit use could be used to keep parts 694 // of it live. Instead of analyzing the implicit operands, ignore 695 // implicit defs. 696 if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) 697 continue; 698 unsigned R = Op.getReg(); 699 if (!TargetRegisterInfo::isPhysicalRegister(R)) 700 continue; 701 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 702 Live.reset(*SR); 703 } 704 for (auto &Op : MI->operands()) { 705 if (!Op.isReg() || !Op.isUse()) 706 continue; 707 unsigned R = Op.getReg(); 708 if (!TargetRegisterInfo::isPhysicalRegister(R)) 709 continue; 710 bool IsLive = false; 711 for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) { 712 if (!Live[*AR]) 713 continue; 714 IsLive = true; 715 break; 716 } 717 if (IsLive) 718 continue; 719 Op.setIsKill(true); 720 for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 721 Live.set(*SR); 722 } 723 } 724 } 725 726 727 // For shadows, determine if RR is aliased to a reaching def of any other 728 // shadow associated with RA. If it is not, then RR is "restricted" to RA, 729 // and so it can be considered a value specific to RA. This is important 730 // for accurately determining values associated with phi uses. 731 // For non-shadows, this function returns "true". 732 bool Liveness::isRestricted(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, 733 RegisterRef RR) const { 734 NodeId Start = RA.Id; 735 for (NodeAddr<RefNode*> TA = DFG.getNextShadow(IA, RA); 736 TA.Id != 0 && TA.Id != Start; TA = DFG.getNextShadow(IA, TA)) { 737 NodeId RD = TA.Addr->getReachingDef(); 738 if (RD == 0) 739 continue; 740 if (RAI.alias(RR, DFG.addr<DefNode*>(RD).Addr->getRegRef())) 741 return false; 742 } 743 return true; 744 } 745 746 747 RegisterRef Liveness::getRestrictedRegRef(NodeAddr<RefNode*> RA) const { 748 assert(DFG.IsRef<NodeAttrs::Use>(RA)); 749 if (RA.Addr->getFlags() & NodeAttrs::Shadow) { 750 NodeId RD = RA.Addr->getReachingDef(); 751 assert(RD); 752 RA = DFG.addr<DefNode*>(RD); 753 } 754 return RA.Addr->getRegRef(); 755 } 756 757 758 unsigned Liveness::getPhysReg(RegisterRef RR) const { 759 if (!TargetRegisterInfo::isPhysicalRegister(RR.Reg)) 760 return 0; 761 return RR.Sub ? TRI.getSubReg(RR.Reg, RR.Sub) : RR.Reg; 762 } 763 764 765 // Helper function to obtain the basic block containing the reaching def 766 // of the given use. 767 MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { 768 auto F = NBMap.find(RN); 769 if (F != NBMap.end()) 770 return F->second; 771 llvm_unreachable("Node id not in map"); 772 } 773 774 775 void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { 776 // The LiveIn map, for each (physical) register, contains the set of live 777 // reaching defs of that register that are live on entry to the associated 778 // block. 779 780 // The summary of the traversal algorithm: 781 // 782 // R is live-in in B, if there exists a U(R), such that rdef(R) dom B 783 // and (U \in IDF(B) or B dom U). 784 // 785 // for (C : children) { 786 // LU = {} 787 // traverse(C, LU) 788 // LiveUses += LU 789 // } 790 // 791 // LiveUses -= Defs(B); 792 // LiveUses += UpwardExposedUses(B); 793 // for (C : IIDF[B]) 794 // for (U : LiveUses) 795 // if (Rdef(U) dom C) 796 // C.addLiveIn(U) 797 // 798 799 // Go up the dominator tree (depth-first). 800 MachineDomTreeNode *N = MDT.getNode(B); 801 for (auto I : *N) { 802 RefMap L; 803 MachineBasicBlock *SB = I->getBlock(); 804 traverse(SB, L); 805 806 for (auto S : L) 807 LiveIn[S.first].insert(S.second.begin(), S.second.end()); 808 } 809 810 if (Trace) { 811 dbgs() << LLVM_FUNCTION_NAME << " in BB#" << B->getNumber() 812 << " after recursion into"; 813 for (auto I : *N) 814 dbgs() << ' ' << I->getBlock()->getNumber(); 815 dbgs() << "\n LiveIn: " << Print<RefMap>(LiveIn, DFG); 816 dbgs() << "\n Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 817 } 818 819 // Add phi uses that are live on exit from this block. 820 RefMap &PUs = PhiLOX[B]; 821 for (auto S : PUs) 822 LiveIn[S.first].insert(S.second.begin(), S.second.end()); 823 824 if (Trace) { 825 dbgs() << "after LOX\n"; 826 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 827 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 828 } 829 830 // Stop tracking all uses defined in this block: erase those records 831 // where the reaching def is located in B and which cover all reached 832 // uses. 833 auto Copy = LiveIn; 834 LiveIn.clear(); 835 836 for (auto I : Copy) { 837 auto &Defs = LiveIn[I.first]; 838 NodeSet Rest; 839 for (auto R : I.second) { 840 auto DA = DFG.addr<DefNode*>(R); 841 RegisterRef DDR = DA.Addr->getRegRef(); 842 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); 843 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 844 // Defs from a different block need to be preserved. Defs from this 845 // block will need to be processed further, except for phi defs, the 846 // liveness of which is handled through the PhiLON/PhiLOX maps. 847 if (B != BA.Addr->getCode()) 848 Defs.insert(R); 849 else { 850 bool IsPreserving = DA.Addr->getFlags() & NodeAttrs::Preserving; 851 if (IA.Addr->getKind() != NodeAttrs::Phi && !IsPreserving) { 852 bool Covering = RAI.covers(DDR, I.first); 853 NodeId U = DA.Addr->getReachedUse(); 854 while (U && Covering) { 855 auto DUA = DFG.addr<UseNode*>(U); 856 RegisterRef Q = DUA.Addr->getRegRef(); 857 Covering = RAI.covers(DA.Addr->getRegRef(), Q); 858 U = DUA.Addr->getSibling(); 859 } 860 if (!Covering) 861 Rest.insert(R); 862 } 863 } 864 } 865 866 // Non-covering defs from B. 867 for (auto R : Rest) { 868 auto DA = DFG.addr<DefNode*>(R); 869 RegisterRef DRR = DA.Addr->getRegRef(); 870 RegisterSet RRs; 871 for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) { 872 NodeAddr<InstrNode*> IA = TA.Addr->getOwner(DFG); 873 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 874 // Preserving defs do not count towards covering. 875 if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) 876 RRs.insert(TA.Addr->getRegRef()); 877 if (BA.Addr->getCode() == B) 878 continue; 879 if (RAI.covers(RRs, DRR)) 880 break; 881 Defs.insert(TA.Id); 882 } 883 } 884 } 885 886 emptify(LiveIn); 887 888 if (Trace) { 889 dbgs() << "after defs in block\n"; 890 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 891 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 892 } 893 894 // Scan the block for upward-exposed uses and add them to the tracking set. 895 for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { 896 NodeAddr<InstrNode*> IA = I; 897 if (IA.Addr->getKind() != NodeAttrs::Stmt) 898 continue; 899 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { 900 RegisterRef RR = UA.Addr->getRegRef(); 901 for (auto D : getAllReachingDefs(UA)) 902 if (getBlockWithRef(D.Id) != B) 903 LiveIn[RR].insert(D.Id); 904 } 905 } 906 907 if (Trace) { 908 dbgs() << "after uses in block\n"; 909 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 910 dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 911 } 912 913 // Phi uses should not be propagated up the dominator tree, since they 914 // are not dominated by their corresponding reaching defs. 915 auto &Local = LiveMap[B]; 916 auto &LON = PhiLON[B]; 917 for (auto R : LON) 918 Local.insert(R.first); 919 920 if (Trace) { 921 dbgs() << "after phi uses in block\n"; 922 dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 923 dbgs() << " Local: " << Print<RegisterSet>(Local, DFG) << '\n'; 924 } 925 926 for (auto C : IIDF[B]) { 927 auto &LiveC = LiveMap[C]; 928 for (auto S : LiveIn) 929 for (auto R : S.second) 930 if (MDT.properlyDominates(getBlockWithRef(R), C)) 931 LiveC.insert(S.first); 932 } 933 } 934 935 936 void Liveness::emptify(RefMap &M) { 937 for (auto I = M.begin(), E = M.end(); I != E; ) 938 I = I->second.empty() ? M.erase(I) : std::next(I); 939 } 940 941