diff options
Diffstat (limited to 'llvm/lib/CodeGen/RDFLiveness.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/RDFLiveness.cpp | 1118 |
1 files changed, 1118 insertions, 0 deletions
diff --git a/llvm/lib/CodeGen/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp new file mode 100644 index 000000000000..0bcd27f8ea45 --- /dev/null +++ b/llvm/lib/CodeGen/RDFLiveness.cpp @@ -0,0 +1,1118 @@ +//===- RDFLiveness.cpp ----------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Computation of the liveness information from the data-flow graph. +// +// The main functionality of this code is to compute block live-in +// information. With the live-in information in place, the placement +// of kill flags can also be recalculated. +// +// The block live-in calculation is based on the ideas from the following +// publication: +// +// Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin. +// "Efficient Liveness Computation Using Merge Sets and DJ-Graphs." +// ACM Transactions on Architecture and Code Optimization, Association for +// Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance +// and Embedded Architectures and Compilers", 8 (4), +// <10.1145/2086696.2086706>. <hal-00647369> +// +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominanceFrontier.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFRegisters.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <map> +#include <utility> +#include <vector> + +using namespace llvm; +using namespace rdf; + +static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25), + cl::Hidden, cl::desc("Maximum recursion level")); + +namespace llvm { +namespace rdf { + + raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) { + OS << '{'; + for (auto &I : P.Obj) { + OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{'; + for (auto J = I.second.begin(), E = I.second.end(); J != E; ) { + OS << Print<NodeId>(J->first, P.G) << PrintLaneMaskOpt(J->second); + if (++J != E) + OS << ','; + } + OS << '}'; + } + OS << " }"; + return OS; + } + +} // end namespace rdf +} // end namespace llvm + +// The order in the returned sequence is the order of reaching defs in the +// upward traversal: the first def is the closest to the given reference RefA, +// the next one is further up, and so on. +// The list ends at a reaching phi def, or when the reference from RefA is +// covered by the defs in the list (see FullChain). +// This function provides two modes of operation: +// (1) Returning the sequence of reaching defs for a particular reference +// node. This sequence will terminate at the first phi node [1]. +// (2) Returning a partial sequence of reaching defs, where the final goal +// is to traverse past phi nodes to the actual defs arising from the code +// itself. +// In mode (2), the register reference for which the search was started +// may be different from the reference node RefA, for which this call was +// made, hence the argument RefRR, which holds the original register. +// Also, some definitions may have already been encountered in a previous +// call that will influence register covering. The register references +// already defined are passed in through DefRRs. +// In mode (1), the "continuation" considerations do not apply, and the +// RefRR is the same as the register in RefA, and the set DefRRs is empty. +// +// [1] It is possible for multiple phi nodes to be included in the returned +// sequence: +// SubA = phi ... +// SubB = phi ... +// ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB) +// However, these phi nodes are independent from one another in terms of +// the data-flow. + +NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, + NodeAddr<RefNode*> RefA, bool TopShadows, bool FullChain, + const RegisterAggr &DefRRs) { + NodeList RDefs; // Return value. + SetVector<NodeId> DefQ; + SetVector<NodeId> Owners; + + // Dead defs will be treated as if they were live, since they are actually + // on the data-flow path. They cannot be ignored because even though they + // do not generate meaningful values, they still modify registers. + + // If the reference is undefined, there is nothing to do. + if (RefA.Addr->getFlags() & NodeAttrs::Undef) + return RDefs; + + // The initial queue should not have reaching defs for shadows. The + // whole point of a shadow is that it will have a reaching def that + // is not aliased to the reaching defs of the related shadows. + NodeId Start = RefA.Id; + auto SNA = DFG.addr<RefNode*>(Start); + if (NodeId RD = SNA.Addr->getReachingDef()) + DefQ.insert(RD); + if (TopShadows) { + for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA)) + if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) + DefQ.insert(RD); + } + + // Collect all the reaching defs, going up until a phi node is encountered, + // or there are no more reaching defs. From this set, the actual set of + // reaching defs will be selected. + // The traversal upwards must go on until a covering def is encountered. + // It is possible that a collection of non-covering (individually) defs + // will be sufficient, but keep going until a covering one is found. + for (unsigned i = 0; i < DefQ.size(); ++i) { + auto TA = DFG.addr<DefNode*>(DefQ[i]); + if (TA.Addr->getFlags() & NodeAttrs::PhiRef) + continue; + // Stop at the covering/overwriting def of the initial register reference. + RegisterRef RR = TA.Addr->getRegRef(DFG); + if (!DFG.IsPreservingDef(TA)) + if (RegisterAggr::isCoverOf(RR, RefRR, PRI)) + continue; + // Get the next level of reaching defs. This will include multiple + // reaching defs for shadows. + for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) + if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) + DefQ.insert(RD); + } + + // Remove all non-phi defs that are not aliased to RefRR, and collect + // the owners of the remaining defs. + SetVector<NodeId> Defs; + for (NodeId N : DefQ) { + auto TA = DFG.addr<DefNode*>(N); + bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; + if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG))) + continue; + Defs.insert(TA.Id); + Owners.insert(TA.Addr->getOwner(DFG).Id); + } + + // Return the MachineBasicBlock containing a given instruction. + auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* { + if (IA.Addr->getKind() == NodeAttrs::Stmt) + return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent(); + assert(IA.Addr->getKind() == NodeAttrs::Phi); + NodeAddr<PhiNode*> PA = IA; + NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG); + return BA.Addr->getCode(); + }; + // Less(A,B) iff instruction A is further down in the dominator tree than B. + auto Less = [&Block,this] (NodeId A, NodeId B) -> bool { + if (A == B) + return false; + auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B); + MachineBasicBlock *BA = Block(OA), *BB = Block(OB); + if (BA != BB) + return MDT.dominates(BB, BA); + // They are in the same block. + bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; + bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; + if (StmtA) { + if (!StmtB) // OB is a phi and phis dominate statements. + return true; + MachineInstr *CA = NodeAddr<StmtNode*>(OA).Addr->getCode(); + MachineInstr *CB = NodeAddr<StmtNode*>(OB).Addr->getCode(); + // The order must be linear, so tie-break such equalities. + if (CA == CB) + return A < B; + return MDT.dominates(CB, CA); + } else { + // OA is a phi. + if (StmtB) + return false; + // Both are phis. There is no ordering between phis (in terms of + // the data-flow), so tie-break this via node id comparison. + return A < B; + } + }; + + std::vector<NodeId> Tmp(Owners.begin(), Owners.end()); + llvm::sort(Tmp, Less); + + // The vector is a list of instructions, so that defs coming from + // the same instruction don't need to be artificially ordered. + // Then, when computing the initial segment, and iterating over an + // instruction, pick the defs that contribute to the covering (i.e. is + // not covered by previously added defs). Check the defs individually, + // i.e. first check each def if is covered or not (without adding them + // to the tracking set), and then add all the selected ones. + + // The reason for this is this example: + // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes). + // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be + // covered if we added A first, and A would be covered + // if we added B first. + + RegisterAggr RRs(DefRRs); + + auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool { + return TA.Addr->getKind() == NodeAttrs::Def && + Defs.count(TA.Id); + }; + for (NodeId T : Tmp) { + if (!FullChain && RRs.hasCoverOf(RefRR)) + break; + auto TA = DFG.addr<InstrNode*>(T); + bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA); + NodeList Ds; + for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) { + RegisterRef QR = DA.Addr->getRegRef(DFG); + // Add phi defs even if they are covered by subsequent defs. This is + // for cases where the reached use is not covered by any of the defs + // encountered so far: the phi def is needed to expose the liveness + // of that use to the entry of the block. + // Example: + // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2. + // d2<R3>(d1,,u3), ... + // ..., u3<D1>(d2) This use needs to be live on entry. + if (FullChain || IsPhi || !RRs.hasCoverOf(QR)) + Ds.push_back(DA); + } + RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); + for (NodeAddr<DefNode*> DA : Ds) { + // When collecting a full chain of definitions, do not consider phi + // defs to actually define a register. + uint16_t Flags = DA.Addr->getFlags(); + if (!FullChain || !(Flags & NodeAttrs::PhiRef)) + if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here. + RRs.insert(DA.Addr->getRegRef(DFG)); + } + } + + auto DeadP = [](const NodeAddr<DefNode*> DA) -> bool { + return DA.Addr->getFlags() & NodeAttrs::Dead; + }; + RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP))); + + return RDefs; +} + +std::pair<NodeSet,bool> +Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode*> RefA, + NodeSet &Visited, const NodeSet &Defs) { + return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest); +} + +std::pair<NodeSet,bool> +Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode*> RefA, + NodeSet &Visited, const NodeSet &Defs, unsigned Nest, unsigned MaxNest) { + if (Nest > MaxNest) + return { NodeSet(), false }; + // Collect all defined registers. Do not consider phis to be defining + // anything, only collect "real" definitions. + RegisterAggr DefRRs(PRI); + for (NodeId D : Defs) { + const auto DA = DFG.addr<const DefNode*>(D); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + DefRRs.insert(DA.Addr->getRegRef(DFG)); + } + + NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs); + if (RDs.empty()) + return { Defs, true }; + + // Make a copy of the preexisting definitions and add the newly found ones. + NodeSet TmpDefs = Defs; + for (NodeAddr<NodeBase*> R : RDs) + TmpDefs.insert(R.Id); + + NodeSet Result = Defs; + + for (NodeAddr<DefNode*> DA : RDs) { + Result.insert(DA.Id); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + continue; + NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG); + if (Visited.count(PA.Id)) + continue; + Visited.insert(PA.Id); + // Go over all phi uses and get the reaching defs for each use. + for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { + const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs, + Nest+1, MaxNest); + if (!T.second) + return { T.first, false }; + Result.insert(T.first.begin(), T.first.end()); + } + } + + return { Result, true }; +} + +/// Find the nearest ref node aliased to RefRR, going upwards in the data +/// flow, starting from the instruction immediately preceding Inst. +NodeAddr<RefNode*> Liveness::getNearestAliasedRef(RegisterRef RefRR, + NodeAddr<InstrNode*> IA) { + NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); + NodeList Ins = BA.Addr->members(DFG); + NodeId FindId = IA.Id; + auto E = Ins.rend(); + auto B = std::find_if(Ins.rbegin(), E, + [FindId] (const NodeAddr<InstrNode*> T) { + return T.Id == FindId; + }); + // Do not scan IA (which is what B would point to). + if (B != E) + ++B; + + do { + // Process the range of instructions from B to E. + for (NodeAddr<InstrNode*> I : make_range(B, E)) { + NodeList Refs = I.Addr->members(DFG); + NodeAddr<RefNode*> Clob, Use; + // Scan all the refs in I aliased to RefRR, and return the one that + // is the closest to the output of I, i.e. def > clobber > use. + for (NodeAddr<RefNode*> R : Refs) { + if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR)) + continue; + if (DFG.IsDef(R)) { + // If it's a non-clobbering def, just return it. + if (!(R.Addr->getFlags() & NodeAttrs::Clobbering)) + return R; + Clob = R; + } else { + Use = R; + } + } + if (Clob.Id != 0) + return Clob; + if (Use.Id != 0) + return Use; + } + + // Go up to the immediate dominator, if any. + MachineBasicBlock *BB = BA.Addr->getCode(); + BA = NodeAddr<BlockNode*>(); + if (MachineDomTreeNode *N = MDT.getNode(BB)) { + if ((N = N->getIDom())) + BA = DFG.findBlock(N->getBlock()); + } + if (!BA.Id) + break; + + Ins = BA.Addr->members(DFG); + B = Ins.rbegin(); + E = Ins.rend(); + } while (true); + + return NodeAddr<RefNode*>(); +} + +NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, + NodeAddr<DefNode*> DefA, const RegisterAggr &DefRRs) { + NodeSet Uses; + + // If the original register is already covered by all the intervening + // defs, no more uses can be reached. + if (DefRRs.hasCoverOf(RefRR)) + return Uses; + + // Add all directly reached uses. + // If the def is dead, it does not provide a value for any use. + bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead; + NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0; + while (U != 0) { + auto UA = DFG.addr<UseNode*>(U); + if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) { + RegisterRef UR = UA.Addr->getRegRef(DFG); + if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR)) + Uses.insert(U); + } + U = UA.Addr->getSibling(); + } + + // Traverse all reached defs. This time dead defs cannot be ignored. + for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { + auto DA = DFG.addr<DefNode*>(D); + NextD = DA.Addr->getSibling(); + RegisterRef DR = DA.Addr->getRegRef(DFG); + // If this def is already covered, it cannot reach anything new. + // Similarly, skip it if it is not aliased to the interesting register. + if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR)) + continue; + NodeSet T; + if (DFG.IsPreservingDef(DA)) { + // If it is a preserving def, do not update the set of intervening defs. + T = getAllReachedUses(RefRR, DA, DefRRs); + } else { + RegisterAggr NewDefRRs = DefRRs; + NewDefRRs.insert(DR); + T = getAllReachedUses(RefRR, DA, NewDefRRs); + } + Uses.insert(T.begin(), T.end()); + } + return Uses; +} + +void Liveness::computePhiInfo() { + RealUseMap.clear(); + + NodeList Phis; + NodeAddr<FuncNode*> FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + for (NodeAddr<BlockNode*> BA : Blocks) { + auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); + Phis.insert(Phis.end(), Ps.begin(), Ps.end()); + } + + // phi use -> (map: reaching phi -> set of registers defined in between) + std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp; + std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation. + std::map<NodeId,RegisterAggr> PhiDRs; // Phi -> registers defined by it. + + // Go over all phis. + for (NodeAddr<PhiNode*> PhiA : Phis) { + // Go over all defs and collect the reached uses that are non-phi uses + // (i.e. the "real uses"). + RefMap &RealUses = RealUseMap[PhiA.Id]; + NodeList PhiRefs = PhiA.Addr->members(DFG); + + // Have a work queue of defs whose reached uses need to be found. + // For each def, add to the queue all reached (non-phi) defs. + SetVector<NodeId> DefQ; + NodeSet PhiDefs; + RegisterAggr DRs(PRI); + for (NodeAddr<RefNode*> R : PhiRefs) { + if (!DFG.IsRef<NodeAttrs::Def>(R)) + continue; + DRs.insert(R.Addr->getRegRef(DFG)); + DefQ.insert(R.Id); + PhiDefs.insert(R.Id); + } + PhiDRs.insert(std::make_pair(PhiA.Id, DRs)); + + // Collect the super-set of all possible reached uses. This set will + // contain all uses reached from this phi, either directly from the + // phi defs, or (recursively) via non-phi defs reached by the phi defs. + // This set of uses will later be trimmed to only contain these uses that + // are actually reached by the phi defs. + for (unsigned i = 0; i < DefQ.size(); ++i) { + NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]); + // Visit all reached uses. Phi defs should not really have the "dead" + // flag set, but check it anyway for consistency. + bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead; + NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0; + while (UN != 0) { + NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN); + uint16_t F = A.Addr->getFlags(); + if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { + RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG)); + RealUses[R.Reg].insert({A.Id,R.Mask}); + } + UN = A.Addr->getSibling(); + } + // Visit all reached defs, and add them to the queue. These defs may + // override some of the uses collected here, but that will be handled + // later. + NodeId DN = DA.Addr->getReachedDef(); + while (DN != 0) { + NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN); + for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { + uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags(); + // Must traverse the reached-def chain. Consider: + // def(D0) -> def(R0) -> def(R0) -> use(D0) + // The reachable use of D0 passes through a def of R0. + if (!(Flags & NodeAttrs::PhiRef)) + DefQ.insert(T.Id); + } + DN = A.Addr->getSibling(); + } + } + // Filter out these uses that appear to be reachable, but really + // are not. For example: + // + // R1:0 = d1 + // = R1:0 u2 Reached by d1. + // R0 = d3 + // = R1:0 u4 Still reached by d1: indirectly through + // the def d3. + // R1 = d5 + // = R1:0 u6 Not reached by d1 (covered collectively + // by d3 and d5), but following reached + // defs and uses from d1 will lead here. + for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) { + // For each reached register UI->first, there is a set UI->second, of + // uses of it. For each such use, check if it is reached by this phi, + // i.e. check if the set of its reaching uses intersects the set of + // this phi's defs. + NodeRefSet Uses = UI->second; + UI->second.clear(); + for (std::pair<NodeId,LaneBitmask> I : Uses) { + auto UA = DFG.addr<UseNode*>(I.first); + // Undef flag is checked above. + assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); + RegisterRef R(UI->first, I.second); + // Calculate the exposed part of the reached use. + RegisterAggr Covered(PRI); + for (NodeAddr<DefNode*> DA : getAllReachingDefs(R, UA)) { + if (PhiDefs.count(DA.Id)) + break; + Covered.insert(DA.Addr->getRegRef(DFG)); + } + if (RegisterRef RC = Covered.clearIn(R)) { + // We are updating the map for register UI->first, so we need + // to map RC to be expressed in terms of that register. + RegisterRef S = PRI.mapTo(RC, UI->first); + UI->second.insert({I.first, S.Mask}); + } + } + UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI); + } + + // If this phi reaches some "real" uses, add it to the queue for upward + // propagation. + if (!RealUses.empty()) + PhiUQ.push_back(PhiA.Id); + + // Go over all phi uses and check if the reaching def is another phi. + // Collect the phis that are among the reaching defs of these uses. + // While traversing the list of reaching defs for each phi use, accumulate + // the set of registers defined between this phi (PhiA) and the owner phi + // of the reaching def. + NodeSet SeenUses; + + for (auto I : PhiRefs) { + if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id)) + continue; + NodeAddr<PhiUseNode*> PUA = I; + if (PUA.Addr->getReachingDef() == 0) + continue; + + RegisterRef UR = PUA.Addr->getRegRef(DFG); + NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs); + RegisterAggr DefRRs(PRI); + + for (NodeAddr<DefNode*> D : Ds) { + if (D.Addr->getFlags() & NodeAttrs::PhiRef) { + NodeId RP = D.Addr->getOwner(DFG).Id; + std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.Id]; + auto F = M.find(RP); + if (F == M.end()) + M.insert(std::make_pair(RP, DefRRs)); + else + F->second.insert(DefRRs); + } + DefRRs.insert(D.Addr->getRegRef(DFG)); + } + + for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PhiA, PUA)) + SeenUses.insert(T.Id); + } + } + + if (Trace) { + dbgs() << "Phi-up-to-phi map with intervening defs:\n"; + for (auto I : PhiUp) { + dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {"; + for (auto R : I.second) + dbgs() << ' ' << Print<NodeId>(R.first, DFG) + << Print<RegisterAggr>(R.second, DFG); + dbgs() << " }\n"; + } + } + + // Propagate the reached registers up in the phi chain. + // + // The following type of situation needs careful handling: + // + // phi d1<R1:0> (1) + // | + // ... d2<R1> + // | + // phi u3<R1:0> (2) + // | + // ... u4<R1> + // + // The phi node (2) defines a register pair R1:0, and reaches a "real" + // use u4 of just R1. The same phi node is also known to reach (upwards) + // the phi node (1). However, the use u4 is not reached by phi (1), + // because of the intervening definition d2 of R1. The data flow between + // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0. + // + // When propagating uses up the phi chains, get the all reaching defs + // for a given phi use, and traverse the list until the propagated ref + // is covered, or until reaching the final phi. Only assume that the + // reference reaches the phi in the latter case. + + for (unsigned i = 0; i < PhiUQ.size(); ++i) { + auto PA = DFG.addr<PhiNode*>(PhiUQ[i]); + NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG); + RefMap &RUM = RealUseMap[PA.Id]; + + for (NodeAddr<UseNode*> UA : PUs) { + std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id]; + RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG)); + for (const std::pair<const NodeId, RegisterAggr> &P : PUM) { + bool Changed = false; + const RegisterAggr &MidDefs = P.second; + + // Collect the set PropUp of uses that are reached by the current + // phi PA, and are not covered by any intervening def between the + // currently visited use UA and the upward phi P. + + if (MidDefs.hasCoverOf(UR)) + continue; + + // General algorithm: + // for each (R,U) : U is use node of R, U is reached by PA + // if MidDefs does not cover (R,U) + // then add (R-MidDefs,U) to RealUseMap[P] + // + for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) { + RegisterRef R(T.first); + // The current phi (PA) could be a phi for a regmask. It could + // reach a whole variety of uses that are not related to the + // specific upward phi (P.first). + const RegisterAggr &DRs = PhiDRs.at(P.first); + if (!DRs.hasAliasOf(R)) + continue; + R = PRI.mapTo(DRs.intersectWith(R), T.first); + for (std::pair<NodeId,LaneBitmask> V : T.second) { + LaneBitmask M = R.Mask & V.second; + if (M.none()) + continue; + if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) { + NodeRefSet &RS = RealUseMap[P.first][SS.Reg]; + Changed |= RS.insert({V.first,SS.Mask}).second; + } + } + } + + if (Changed) + PhiUQ.push_back(P.first); + } + } + } + + if (Trace) { + dbgs() << "Real use map:\n"; + for (auto I : RealUseMap) { + dbgs() << "phi " << Print<NodeId>(I.first, DFG); + NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first); + NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); + if (!Ds.empty()) { + RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(DFG); + dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>'; + } else { + dbgs() << "<noreg>"; + } + dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n'; + } + } +} + +void Liveness::computeLiveIns() { + // Populate the node-to-block map. This speeds up the calculations + // significantly. + NBMap.clear(); + for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { + MachineBasicBlock *BB = BA.Addr->getCode(); + for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { + for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) + NBMap.insert(std::make_pair(RA.Id, BB)); + NBMap.insert(std::make_pair(IA.Id, BB)); + } + } + + MachineFunction &MF = DFG.getMF(); + + // Compute IDF first, then the inverse. + decltype(IIDF) IDF; + for (MachineBasicBlock &B : MF) { + auto F1 = MDF.find(&B); + if (F1 == MDF.end()) + continue; + SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end()); + for (unsigned i = 0; i < IDFB.size(); ++i) { + auto F2 = MDF.find(IDFB[i]); + if (F2 != MDF.end()) + IDFB.insert(F2->second.begin(), F2->second.end()); + } + // Add B to the IDF(B). This will put B in the IIDF(B). + IDFB.insert(&B); + IDF[&B].insert(IDFB.begin(), IDFB.end()); + } + + for (auto I : IDF) + for (auto S : I.second) + IIDF[S].insert(I.first); + + computePhiInfo(); + + NodeAddr<FuncNode*> FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + + // Build the phi live-on-entry map. + for (NodeAddr<BlockNode*> BA : Blocks) { + MachineBasicBlock *MB = BA.Addr->getCode(); + RefMap &LON = PhiLON[MB]; + for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) + for (const RefMap::value_type &S : RealUseMap[P.Id]) + LON[S.first].insert(S.second.begin(), S.second.end()); + } + + if (Trace) { + dbgs() << "Phi live-on-entry map:\n"; + for (auto &I : PhiLON) + dbgs() << "block #" << I.first->getNumber() << " -> " + << Print<RefMap>(I.second, DFG) << '\n'; + } + + // Build the phi live-on-exit map. Each phi node has some set of reached + // "real" uses. Propagate this set backwards into the block predecessors + // through the reaching defs of the corresponding phi uses. + for (NodeAddr<BlockNode*> BA : Blocks) { + NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); + for (NodeAddr<PhiNode*> PA : Phis) { + RefMap &RUs = RealUseMap[PA.Id]; + if (RUs.empty()) + continue; + + NodeSet SeenUses; + for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { + if (!SeenUses.insert(U.Id).second) + continue; + NodeAddr<PhiUseNode*> PUA = U; + if (PUA.Addr->getReachingDef() == 0) + continue; + + // Each phi has some set (possibly empty) of reached "real" uses, + // that is, uses that are part of the compiled program. Such a use + // may be located in some farther block, but following a chain of + // reaching defs will eventually lead to this phi. + // Any chain of reaching defs may fork at a phi node, but there + // will be a path upwards that will lead to this phi. Now, this + // chain will need to fork at this phi, since some of the reached + // uses may have definitions joining in from multiple predecessors. + // For each reached "real" use, identify the set of reaching defs + // coming from each predecessor P, and add them to PhiLOX[P]. + // + auto PrA = DFG.addr<BlockNode*>(PUA.Addr->getPredecessor()); + RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; + + for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) { + // We need to visit each individual use. + for (std::pair<NodeId,LaneBitmask> P : RS.second) { + // Create a register ref corresponding to the use, and find + // all reaching defs starting from the phi use, and treating + // all related shadows as a single use cluster. + RegisterRef S(RS.first, P.second); + NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs); + for (NodeAddr<DefNode*> D : Ds) { + // Calculate the mask corresponding to the visited def. + RegisterAggr TA(PRI); + TA.insert(D.Addr->getRegRef(DFG)).intersect(S); + LaneBitmask TM = TA.makeRegRef().Mask; + LOX[S.Reg].insert({D.Id, TM}); + } + } + } + + for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PA, PUA)) + SeenUses.insert(T.Id); + } // for U : phi uses + } // for P : Phis + } // for B : Blocks + + if (Trace) { + dbgs() << "Phi live-on-exit map:\n"; + for (auto &I : PhiLOX) + dbgs() << "block #" << I.first->getNumber() << " -> " + << Print<RefMap>(I.second, DFG) << '\n'; + } + + RefMap LiveIn; + traverse(&MF.front(), LiveIn); + + // Add function live-ins to the live-in set of the function entry block. + LiveMap[&MF.front()].insert(DFG.getLiveIns()); + + if (Trace) { + // Dump the liveness map + for (MachineBasicBlock &B : MF) { + std::vector<RegisterRef> LV; + for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) + LV.push_back(RegisterRef(I->PhysReg, I->LaneMask)); + llvm::sort(LV); + dbgs() << printMBBReference(B) << "\t rec = {"; + for (auto I : LV) + dbgs() << ' ' << Print<RegisterRef>(I, DFG); + dbgs() << " }\n"; + //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n'; + + LV.clear(); + const RegisterAggr &LG = LiveMap[&B]; + for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I) + LV.push_back(*I); + llvm::sort(LV); + dbgs() << "\tcomp = {"; + for (auto I : LV) + dbgs() << ' ' << Print<RegisterRef>(I, DFG); + dbgs() << " }\n"; + + } + } +} + +void Liveness::resetLiveIns() { + for (auto &B : DFG.getMF()) { + // Remove all live-ins. + std::vector<unsigned> T; + for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) + T.push_back(I->PhysReg); + for (auto I : T) + B.removeLiveIn(I); + // Add the newly computed live-ins. + const RegisterAggr &LiveIns = LiveMap[&B]; + for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) { + RegisterRef R = *I; + B.addLiveIn({MCPhysReg(R.Reg), R.Mask}); + } + } +} + +void Liveness::resetKills() { + for (auto &B : DFG.getMF()) + resetKills(&B); +} + +void Liveness::resetKills(MachineBasicBlock *B) { + auto CopyLiveIns = [this] (MachineBasicBlock *B, BitVector &LV) -> void { + for (auto I : B->liveins()) { + MCSubRegIndexIterator S(I.PhysReg, &TRI); + if (!S.isValid()) { + LV.set(I.PhysReg); + continue; + } + do { + LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex()); + if ((M & I.LaneMask).any()) + LV.set(S.getSubReg()); + ++S; + } while (S.isValid()); + } + }; + + BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); + CopyLiveIns(B, LiveIn); + for (auto SI : B->successors()) + CopyLiveIns(SI, Live); + + for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { + MachineInstr *MI = &*I; + if (MI->isDebugInstr()) + continue; + + MI->clearKillInfo(); + for (auto &Op : MI->operands()) { + // An implicit def of a super-register may not necessarily start a + // live range of it, since an implicit use could be used to keep parts + // of it live. Instead of analyzing the implicit operands, ignore + // implicit defs. + if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) + continue; + Register R = Op.getReg(); + if (!Register::isPhysicalRegister(R)) + continue; + for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) + Live.reset(*SR); + } + for (auto &Op : MI->operands()) { + if (!Op.isReg() || !Op.isUse() || Op.isUndef()) + continue; + Register R = Op.getReg(); + if (!Register::isPhysicalRegister(R)) + continue; + bool IsLive = false; + for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) { + if (!Live[*AR]) + continue; + IsLive = true; + break; + } + if (!IsLive) + Op.setIsKill(true); + for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) + Live.set(*SR); + } + } +} + +// Helper function to obtain the basic block containing the reaching def +// of the given use. +MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { + auto F = NBMap.find(RN); + if (F != NBMap.end()) + return F->second; + llvm_unreachable("Node id not in map"); +} + +void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { + // The LiveIn map, for each (physical) register, contains the set of live + // reaching defs of that register that are live on entry to the associated + // block. + + // The summary of the traversal algorithm: + // + // R is live-in in B, if there exists a U(R), such that rdef(R) dom B + // and (U \in IDF(B) or B dom U). + // + // for (C : children) { + // LU = {} + // traverse(C, LU) + // LiveUses += LU + // } + // + // LiveUses -= Defs(B); + // LiveUses += UpwardExposedUses(B); + // for (C : IIDF[B]) + // for (U : LiveUses) + // if (Rdef(U) dom C) + // C.addLiveIn(U) + // + + // Go up the dominator tree (depth-first). + MachineDomTreeNode *N = MDT.getNode(B); + for (auto I : *N) { + RefMap L; + MachineBasicBlock *SB = I->getBlock(); + traverse(SB, L); + + for (auto S : L) + LiveIn[S.first].insert(S.second.begin(), S.second.end()); + } + + if (Trace) { + dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__ + << " after recursion into: {"; + for (auto I : *N) + dbgs() << ' ' << I->getBlock()->getNumber(); + dbgs() << " }\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Add reaching defs of phi uses that are live on exit from this block. + RefMap &PUs = PhiLOX[B]; + for (auto &S : PUs) + LiveIn[S.first].insert(S.second.begin(), S.second.end()); + + if (Trace) { + dbgs() << "after LOX\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // The LiveIn map at this point has all defs that are live-on-exit from B, + // as if they were live-on-entry to B. First, we need to filter out all + // defs that are present in this block. Then we will add reaching defs of + // all upward-exposed uses. + + // To filter out the defs, first make a copy of LiveIn, and then re-populate + // LiveIn with the defs that should remain. + RefMap LiveInCopy = LiveIn; + LiveIn.clear(); + + for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) { + RegisterRef LRef(LE.first); + NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled. + const NodeRefSet &OldDefs = LE.second; + for (NodeRef OR : OldDefs) { + // R is a def node that was live-on-exit + auto DA = DFG.addr<DefNode*>(OR.first); + NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); + NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); + if (B != BA.Addr->getCode()) { + // Defs from a different block need to be preserved. Defs from this + // block will need to be processed further, except for phi defs, the + // liveness of which is handled through the PhiLON/PhiLOX maps. + NewDefs.insert(OR); + continue; + } + + // Defs from this block need to stop the liveness from being + // propagated upwards. This only applies to non-preserving defs, + // and to the parts of the register actually covered by those defs. + // (Note that phi defs should always be preserving.) + RegisterAggr RRs(PRI); + LRef.Mask = OR.second; + + if (!DFG.IsPreservingDef(DA)) { + assert(!(IA.Addr->getFlags() & NodeAttrs::Phi)); + // DA is a non-phi def that is live-on-exit from this block, and + // that is also located in this block. LRef is a register ref + // whose use this def reaches. If DA covers LRef, then no part + // of LRef is exposed upwards.A + if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef)) + continue; + } + + // DA itself was not sufficient to cover LRef. In general, it is + // the last in a chain of aliased defs before the exit from this block. + // There could be other defs in this block that are a part of that + // chain. Check that now: accumulate the registers from these defs, + // and if they all together cover LRef, it is not live-on-entry. + for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) { + // DefNode -> InstrNode -> BlockNode. + NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG); + NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG); + // Reaching defs are ordered in the upward direction. + if (BTA.Addr->getCode() != B) { + // We have reached past the beginning of B, and the accumulated + // registers are not covering LRef. The first def from the + // upward chain will be live. + // Subtract all accumulated defs (RRs) from LRef. + RegisterRef T = RRs.clearIn(LRef); + assert(T); + NewDefs.insert({TA.Id,T.Mask}); + break; + } + + // TA is in B. Only add this def to the accumulated cover if it is + // not preserving. + if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) + RRs.insert(TA.Addr->getRegRef(DFG)); + // If this is enough to cover LRef, then stop. + if (RRs.hasCoverOf(LRef)) + break; + } + } + } + + emptify(LiveIn); + + if (Trace) { + dbgs() << "after defs in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Scan the block for upward-exposed uses and add them to the tracking set. + for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { + NodeAddr<InstrNode*> IA = I; + if (IA.Addr->getKind() != NodeAttrs::Stmt) + continue; + for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { + if (UA.Addr->getFlags() & NodeAttrs::Undef) + continue; + RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG)); + for (NodeAddr<DefNode*> D : getAllReachingDefs(UA)) + if (getBlockWithRef(D.Id) != B) + LiveIn[RR.Reg].insert({D.Id,RR.Mask}); + } + } + + if (Trace) { + dbgs() << "after uses in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Phi uses should not be propagated up the dominator tree, since they + // are not dominated by their corresponding reaching defs. + RegisterAggr &Local = LiveMap[B]; + RefMap &LON = PhiLON[B]; + for (auto &R : LON) { + LaneBitmask M; + for (auto P : R.second) + M |= P.second; + Local.insert(RegisterRef(R.first,M)); + } + + if (Trace) { + dbgs() << "after phi uses in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(Local, DFG) << '\n'; + } + + for (auto C : IIDF[B]) { + RegisterAggr &LiveC = LiveMap[C]; + for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn) + for (auto R : S.second) + if (MDT.properlyDominates(getBlockWithRef(R.first), C)) + LiveC.insert(RegisterRef(S.first, R.second)); + } +} + +void Liveness::emptify(RefMap &M) { + for (auto I = M.begin(), E = M.end(); I != E; ) + I = I->second.empty() ? M.erase(I) : std::next(I); +} |