From b60736ec1405bb0a8dd40989f67ef4c93da068ab Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Tue, 16 Feb 2021 21:13:02 +0100 Subject: Vendor import of llvm-project main 8e464dd76bef, the last commit before the upstream release/12.x branch was created. --- llvm/lib/CodeGen/RDFLiveness.cpp | 151 +++++++++++++++++++++++++++------------ 1 file changed, 104 insertions(+), 47 deletions(-) (limited to 'llvm/lib/CodeGen/RDFLiveness.cpp') diff --git a/llvm/lib/CodeGen/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp index 0bcd27f8ea45..76bf0c280970 100644 --- a/llvm/lib/CodeGen/RDFLiveness.cpp +++ b/llvm/lib/CodeGen/RDFLiveness.cpp @@ -23,8 +23,10 @@ // <10.1145/2086696.2086706>. // #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominanceFrontier.h" #include "llvm/CodeGen/MachineDominators.h" @@ -45,6 +47,7 @@ #include #include #include +#include #include #include @@ -108,7 +111,7 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, const RegisterAggr &DefRRs) { NodeList RDefs; // Return value. SetVector DefQ; - SetVector Owners; + DenseMap OrdMap; // 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 @@ -151,18 +154,9 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) if (NodeId RD = NodeAddr(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 Defs; - for (NodeId N : DefQ) { - auto TA = DFG.addr(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); + // Don't visit sibling defs. They share the same reaching def (which + // will be visited anyway), but they define something not aliased to + // this ref. } // Return the MachineBasicBlock containing a given instruction. @@ -174,38 +168,80 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, NodeAddr 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 { + + SmallSet Defs; + + // Remove all non-phi defs that are not aliased to RefRR, and segregate + // the the remaining defs into buckets for containing blocks. + std::map> Owners; + std::map> Blocks; + for (NodeId N : DefQ) { + auto TA = DFG.addr(N); + bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; + if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG))) + continue; + Defs.insert(TA.Id); + NodeAddr IA = TA.Addr->getOwner(DFG); + Owners[TA.Id] = IA; + Blocks[Block(IA)].push_back(IA.Id); + } + + auto Precedes = [this,&OrdMap] (NodeId A, NodeId B) { if (A == B) return false; - auto OA = DFG.addr(A), OB = DFG.addr(B); - MachineBasicBlock *BA = Block(OA), *BB = Block(OB); - if (BA != BB) - return MDT.dominates(BB, BA); - // They are in the same block. + NodeAddr OA = DFG.addr(A); + NodeAddr OB = DFG.addr(B); 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(OA).Addr->getCode(); - MachineInstr *CB = NodeAddr(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. + if (StmtA && StmtB) { + const MachineInstr *InA = NodeAddr(OA).Addr->getCode(); + const MachineInstr *InB = NodeAddr(OB).Addr->getCode(); + assert(InA->getParent() == InB->getParent()); + auto FA = OrdMap.find(InA); + if (FA != OrdMap.end()) + return FA->second < OrdMap.find(InB)->second; + const MachineBasicBlock *BB = InA->getParent(); + for (auto It = BB->begin(), E = BB->end(); It != E; ++It) { + if (It == InA->getIterator()) + return true; + if (It == InB->getIterator()) + return false; + } + llvm_unreachable("InA and InB should be in the same block"); + } + // One of them is a phi node. + if (!StmtA && !StmtB) { + // Both are phis, which are unordered. Break the tie by id numbers. return A < B; } + // Only one of them is a phi. Phis always precede statements. + return !StmtA; }; - std::vector Tmp(Owners.begin(), Owners.end()); - llvm::sort(Tmp, Less); + auto GetOrder = [&OrdMap] (MachineBasicBlock &B) { + uint32_t Pos = 0; + for (MachineInstr &In : B) + OrdMap.insert({&In, ++Pos}); + }; + + // For each block, sort the nodes in it. + std::vector TmpBB; + for (auto &Bucket : Blocks) { + TmpBB.push_back(Bucket.first); + if (Bucket.second.size() > 2) + GetOrder(*Bucket.first); + llvm::sort(Bucket.second, Precedes); + } + + // Sort the blocks with respect to dominance. + llvm::sort(TmpBB, + [this](auto A, auto B) { return MDT.properlyDominates(A, B); }); + + std::vector TmpInst; + for (auto I = TmpBB.rbegin(), E = TmpBB.rend(); I != E; ++I) { + auto &Bucket = Blocks[*I]; + TmpInst.insert(TmpInst.end(), Bucket.rbegin(), Bucket.rend()); + } // The vector is a list of instructions, so that defs coming from // the same instruction don't need to be artificially ordered. @@ -220,6 +256,9 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, // *d3 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. + // In this example we want both A and B, because we don't want to give + // either one priority over the other, since they belong to the same + // statement. RegisterAggr RRs(DefRRs); @@ -227,7 +266,8 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, return TA.Addr->getKind() == NodeAttrs::Def && Defs.count(TA.Id); }; - for (NodeId T : Tmp) { + + for (NodeId T : TmpInst) { if (!FullChain && RRs.hasCoverOf(RefRR)) break; auto TA = DFG.addr(T); @@ -246,7 +286,7 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, if (FullChain || IsPhi || !RRs.hasCoverOf(QR)) Ds.push_back(DA); } - RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); + llvm::append_range(RDefs, Ds); for (NodeAddr DA : Ds) { // When collecting a full chain of definitions, do not consider phi // defs to actually define a register. @@ -260,7 +300,7 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR, auto DeadP = [](const NodeAddr DA) -> bool { return DA.Addr->getFlags() & NodeAttrs::Dead; }; - RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP))); + llvm::erase_if(RDefs, DeadP); return RDefs; } @@ -430,13 +470,13 @@ void Liveness::computePhiInfo() { NodeList Blocks = FA.Addr->members(DFG); for (NodeAddr BA : Blocks) { auto Ps = BA.Addr->members_if(DFG.IsCode, DFG); - Phis.insert(Phis.end(), Ps.begin(), Ps.end()); + llvm::append_range(Phis, Ps); } // phi use -> (map: reaching phi -> set of registers defined in between) std::map> PhiUp; std::vector PhiUQ; // Work list of phis for upward propagation. - std::map PhiDRs; // Phi -> registers defined by it. + std::unordered_map PhiDRs; // Phi -> registers defined by it. // Go over all phis. for (NodeAddr PhiA : Phis) { @@ -474,7 +514,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(A.Addr->getRegRef(DFG)); + RegisterRef R = A.Addr->getRegRef(DFG); RealUses[R.Reg].insert({A.Id,R.Mask}); } UN = A.Addr->getSibling(); @@ -612,6 +652,23 @@ void Liveness::computePhiInfo() { // is covered, or until reaching the final phi. Only assume that the // reference reaches the phi in the latter case. + // The operation "clearIn" can be expensive. For a given set of intervening + // defs, cache the result of subtracting these defs from a given register + // ref. + using SubMap = std::unordered_map; + std::unordered_map Subs; + auto ClearIn = [] (RegisterRef RR, const RegisterAggr &Mid, SubMap &SM) { + if (Mid.empty()) + return RR; + auto F = SM.find(RR); + if (F != SM.end()) + return F->second; + RegisterRef S = Mid.clearIn(RR); + SM.insert({RR, S}); + return S; + }; + + // Go over all phis. for (unsigned i = 0; i < PhiUQ.size(); ++i) { auto PA = DFG.addr(PhiUQ[i]); NodeList PUs = PA.Addr->members_if(DFG.IsRef, DFG); @@ -619,17 +676,17 @@ void Liveness::computePhiInfo() { for (NodeAddr UA : PUs) { std::map &PUM = PhiUp[UA.Id]; - RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG)); + RegisterRef UR = UA.Addr->getRegRef(DFG); for (const std::pair &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; + SubMap &SM = Subs[MidDefs]; // General algorithm: // for each (R,U) : U is use node of R, U is reached by PA @@ -649,7 +706,7 @@ void Liveness::computePhiInfo() { LaneBitmask M = R.Mask & V.second; if (M.none()) continue; - if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) { + if (RegisterRef SS = ClearIn(RegisterRef(R.Reg, M), MidDefs, SM)) { NodeRefSet &RS = RealUseMap[P.first][SS.Reg]; Changed |= RS.insert({V.first,SS.Mask}).second; } @@ -1073,7 +1130,7 @@ void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { for (NodeAddr UA : IA.Addr->members_if(DFG.IsUse, DFG)) { if (UA.Addr->getFlags() & NodeAttrs::Undef) continue; - RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG)); + RegisterRef RR = UA.Addr->getRegRef(DFG); for (NodeAddr D : getAllReachingDefs(UA)) if (getBlockWithRef(D.Id) != B) LiveIn[RR.Reg].insert({D.Id,RR.Mask}); -- cgit v1.3