From ff2120a9ec53979fd4c2e5563716ca0af41e7012 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Thu, 16 Feb 2017 19:28:06 +0000 Subject: [PATCH] [RDF] Aggregate shadow phi uses into one cluster when propagating live info git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@295366 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/Hexagon/RDFLiveness.cpp | 125 +++++++++++++++++++------------------ lib/Target/Hexagon/RDFLiveness.h | 13 ++-- 2 files changed, 68 insertions(+), 70 deletions(-) diff --git a/lib/Target/Hexagon/RDFLiveness.cpp b/lib/Target/Hexagon/RDFLiveness.cpp index fbc6301437f..6710e5083d5 100644 --- a/lib/Target/Hexagon/RDFLiveness.cpp +++ b/lib/Target/Hexagon/RDFLiveness.cpp @@ -85,7 +85,8 @@ namespace rdf { // the data-flow. NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, - NodeAddr RefA, bool FullChain, const RegisterAggr &DefRRs) { + NodeAddr RefA, bool TopShadows, bool FullChain, + const RegisterAggr &DefRRs) { NodeList RDefs; // Return value. SetVector DefQ; SetVector Owners; @@ -105,6 +106,11 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, auto SNA = DFG.addr(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(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 @@ -252,7 +258,7 @@ NodeSet Liveness::getAllReachingDefsRec(RegisterRef RefRR, DefRRs.insert(DA.Addr->getRegRef(DFG)); } - NodeList RDs = getAllReachingDefs(RefRR, RefA, true, DefRRs); + NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs); if (RDs.empty()) return Defs; @@ -377,7 +383,7 @@ void Liveness::computePhiInfo() { NodeAddr A = DFG.addr(UN); uint16_t F = A.Addr->getFlags(); if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { - RegisterRef R = PRI.normalize(getRestrictedRegRef(A)); + RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG)); RealUses[R.Reg].insert({A.Id,R.Mask}); } UN = A.Addr->getSibling(); @@ -426,15 +432,11 @@ void Liveness::computePhiInfo() { assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); RegisterRef R(UI->first, I->second); NodeList RDs = getAllReachingDefs(R, UA); - if (any_of(RDs, InPhiDefs)) - ++I; - else - I = Uses.erase(I); + // If none of the reaching defs of R are from this phi, remove this + // use of R. + I = any_of(RDs, InPhiDefs) ? std::next(I) : Uses.erase(I); } - if (Uses.empty()) - UI = RealUses.erase(UI); - else - ++UI; + UI = Uses.empty() ? RealUses.erase(UI) : std::next(UI); } // If this phi reaches some "real" uses, add it to the queue for upward @@ -452,32 +454,29 @@ void Liveness::computePhiInfo() { for (auto I : PhiRefs) { if (!DFG.IsRef(I) || SeenUses.count(I.Id)) continue; - NodeAddr UA = I; - - // Given a phi use UA, traverse all related phi uses (including UA). - // The related phi uses may reach different phi nodes or may reach the - // same phi node. If multiple uses reach the same phi P, the intervening - // defs must be accumulated for all such uses. To group all such uses - // into one set, map their node ids to the first use id that reaches P. - std::map FirstUse; // Phi reached up -> first phi use. - - for (NodeAddr VA : DFG.getRelatedRefs(PhiA, UA)) { - SeenUses.insert(VA.Id); - RegisterAggr DefRRs(PRI); - for (NodeAddr DA : getAllReachingDefs(VA)) { - if (DA.Addr->getFlags() & NodeAttrs::PhiRef) { - NodeId RP = DA.Addr->getOwner(DFG).Id; - NodeId FU = FirstUse.insert({RP,VA.Id}).first->second; - std::map &M = PhiUp[FU]; - auto F = M.find(RP); - if (F == M.end()) - M.insert(std::make_pair(RP, DefRRs)); - else - F->second.insert(DefRRs); - } - DefRRs.insert(DA.Addr->getRegRef(DFG)); + NodeAddr 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 D : Ds) { + if (D.Addr->getFlags() & NodeAttrs::PhiRef) { + NodeId RP = D.Addr->getOwner(DFG).Id; + std::map &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 T : DFG.getRelatedRefs(PhiA, PUA)) + SeenUses.insert(T.Id); } } @@ -522,7 +521,7 @@ void Liveness::computePhiInfo() { for (NodeAddr UA : PUs) { std::map &PUM = PhiUp[UA.Id]; - RegisterRef UR = PRI.normalize(getRestrictedRegRef(UA)); + RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG)); for (const std::pair &P : PUM) { bool Changed = false; const RegisterAggr &MidDefs = P.second; @@ -645,30 +644,43 @@ void Liveness::computeLiveIns() { if (RUs.empty()) continue; + NodeSet SeenUses; for (auto U : PA.Addr->members_if(DFG.IsRef, DFG)) { + if (!SeenUses.insert(U.Id).second) + continue; NodeAddr PUA = U; if (PUA.Addr->getReachingDef() == 0) continue; - // Mark all reached "real" uses of P as live on exit in the - // predecessor. - // Remap all the RUs so that they have a correct reaching def. + // 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(PUA.Addr->getPredecessor()); RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; - RegisterRef UR = PRI.normalize(getRestrictedRegRef(PUA)); - for (const std::pair &T : RUs) { - // Check if T.first aliases UR? - LaneBitmask M; - for (std::pair P : T.second) - M |= P.second; - - RegisterRef S = DFG.restrictRef(RegisterRef(T.first, M), UR); - if (!S) - continue; - for (NodeAddr D : getAllReachingDefs(S, PUA)) - LOX[S.Reg].insert({D.Id, S.Mask}); + for (const std::pair &RS : RUs) { + // We need to visit each individual use. + for (std::pair 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 D : Ds) + LOX[S.Reg].insert({D.Id, S.Mask}); + } } + + for (NodeAddr T : DFG.getRelatedRefs(PA, PUA)) + SeenUses.insert(T.Id); } // for U : phi uses } // for P : Phis } // for B : Blocks @@ -810,17 +822,6 @@ void Liveness::resetKills(MachineBasicBlock *B) { } -RegisterRef Liveness::getRestrictedRegRef(NodeAddr RA) const { - assert(DFG.IsRef(RA)); - if (RA.Addr->getFlags() & NodeAttrs::Shadow) { - NodeId RD = RA.Addr->getReachingDef(); - assert(RD); - RA = DFG.addr(RD); - } - return RA.Addr->getRegRef(DFG); -} - - // Helper function to obtain the basic block containing the reaching def // of the given use. MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { diff --git a/lib/Target/Hexagon/RDFLiveness.h b/lib/Target/Hexagon/RDFLiveness.h index 756977fb386..76a3a4031b8 100644 --- a/lib/Target/Hexagon/RDFLiveness.h +++ b/lib/Target/Hexagon/RDFLiveness.h @@ -50,16 +50,17 @@ namespace rdf { Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), - MDF(g.getDF()), MRI(mri), LiveMap(g.getPRI()), Empty(), + MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()), Trace(false) {} NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA, - bool FullChain, const RegisterAggr &DefRRs); + bool TopShadows, bool FullChain, const RegisterAggr &DefRRs); NodeList getAllReachingDefs(NodeAddr RefA) { - return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, NoRegs); + return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, + false, NoRegs); } NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA) { - return getAllReachingDefs(RefRR, RefA, false, NoRegs); + return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); } NodeSet getAllReachingDefsRec(RegisterRef RefRR, NodeAddr RefA, NodeSet &Visited, const NodeSet &Defs); @@ -90,7 +91,6 @@ namespace rdf { const PhysicalRegisterInfo &PRI; const MachineDominatorTree &MDT; const MachineDominanceFrontier &MDF; - MachineRegisterInfo &MRI; LiveMapType LiveMap; const RefMap Empty; const RegisterAggr NoRegs; @@ -122,9 +122,6 @@ namespace rdf { // the dominator tree), create a map: block -> set of uses live on exit. std::map PhiLOX; - bool isRestrictedToRef(NodeAddr IA, NodeAddr RA, - RegisterRef RR) const; - RegisterRef getRestrictedRegRef(NodeAddr RA) const; MachineBasicBlock *getBlockWithRef(NodeId RN) const; void traverse(MachineBasicBlock *B, RefMap &LiveIn); void emptify(RefMap &M); -- 2.11.0