vendor/llvm-project/llvmorg-12-init-17869-g8e464dd76bef

1 files changed, 104 insertions, 47 deletions

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>. <hal-00647369>
 //
 #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 <cstdint>
 #include <iterator>
 #include <map>
+#include <unordered_map>
 #include <utility>
 #include <vector>
 
@@ -108,7 +111,7 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
       const RegisterAggr &DefRRs) {
   NodeList RDefs; // Return value.
   SetVector<NodeId> DefQ;
-  SetVector<NodeId> Owners;
+  DenseMap<MachineInstr*, uint32_t> 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<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);
+    // 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<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 {
+
+  SmallSet<NodeId,32> 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<NodeId, NodeAddr<InstrNode*>> Owners;
+  std::map<MachineBasicBlock*, SmallVector<NodeId,32>> Blocks;
+  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);
+    NodeAddr<InstrNode*> 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<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.
+    NodeAddr<InstrNode*> OA = DFG.addr<InstrNode*>(A);
+    NodeAddr<InstrNode*> OB = DFG.addr<InstrNode*>(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<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.
+    if (StmtA && StmtB) {
+      const MachineInstr *InA = NodeAddr<StmtNode*>(OA).Addr->getCode();
+      const MachineInstr *InB = NodeAddr<StmtNode*>(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<NodeId> 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<MachineBasicBlock*> 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<NodeId> 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<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.
+  // 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<InstrNode*>(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<DefNode*> 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<DefNode*> 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<BlockNode*> BA : Blocks) {
     auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, 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<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.
+  std::unordered_map<NodeId,RegisterAggr> PhiDRs;  // Phi -> registers defined by it.
 
   // Go over all phis.
   for (NodeAddr<PhiNode*> PhiA : Phis) {
@@ -474,7 +514,7 @@ void Liveness::computePhiInfo() {
         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));
+          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<RegisterRef, RegisterRef>;
+  std::unordered_map<RegisterAggr, SubMap> 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<PhiNode*>(PhiUQ[i]);
     NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG);
@@ -619,17 +676,17 @@ void Liveness::computePhiInfo() {
 
     for (NodeAddr<UseNode*> UA : PUs) {
       std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
-      RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG));
+      RegisterRef UR = 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;
+        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<UseNode*> 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<DefNode*> D : getAllReachingDefs(UA))
         if (getBlockWithRef(D.Id) != B)
           LiveIn[RR.Reg].insert({D.Id,RR.Mask});