lib/Target/Hexagon/RDFLiveness.cpp

   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