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