blockfreq: Use LoopData directly

Instead of passing around loop headers, pass around `LoopData` directly.

<rdar://problem/14292693>

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207179 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index 78f7e8414254dcc39afaf0aed0dd3df9dc0c1f64..02c04fd174074fdb9f482749edc3f09ae8c135c2 100644 (file)
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -1058,8 +1058,7 @@ public:
   ///
   /// Adds all edges from LocalLoopHead to Dist.  Calls addToDist() to add each
   /// successor edge.
-  void addLoopSuccessorsToDist(const BlockNode &LoopHead,
-                               const BlockNode &LocalLoopHead,
+  void addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop,
                                Distribution &Dist);
 
   /// \brief Add an edge to the distribution.
@@ -1068,7 +1067,7 @@ public:
   /// edge is forward/exit/backedge is in the context of LoopHead.  Otherwise,
   /// every edge should be a forward edge (since all the loops are packaged
   /// up).
-  void addToDist(Distribution &Dist, const BlockNode &LoopHead,
+  void addToDist(Distribution &Dist, const LoopData *OuterLoop,
                  const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight);
 
   LoopData &getLoopPackage(const BlockNode &Head) {
@@ -1096,14 +1095,14 @@ public:
   /// but only actually distributed to the local successors.  The general mass
   /// should be split up between all three types of successors, but distributed
   /// only to exits and backedges.
-  void distributeMass(const BlockNode &Source, const BlockNode &LoopHead,
+  void distributeMass(const BlockNode &Source, LoopData *OuterLoop,
                       Distribution &Dist);
 
   /// \brief Compute the loop scale for a loop.
-  void computeLoopScale(const BlockNode &LoopHead);
+  void computeLoopScale(LoopData &Loop);
 
   /// \brief Package up a loop.
-  void packageLoop(const BlockNode &LoopHead);
+  void packageLoop(LoopData &Loop);
 
   /// \brief Finalize frequency metrics.
   ///
@@ -1330,10 +1329,9 @@ template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase {
   void initializeLoops();
   void runOnFunction(const FunctionT *F);
 
-  void propagateMassToSuccessors(const BlockNode &LoopHead,
-                                 const BlockNode &Node);
+  void propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node);
   void computeMassInLoops();
-  void computeMassInLoop(const BlockNode &LoopHead);
+  void computeMassInLoop(LoopData &Loop);
   void computeMassInFunction();
 
   std::string getBlockName(const BlockNode &Node) const override {
@@ -1472,22 +1470,23 @@ template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
   // Visit loops with the deepest first, and the top-level loops last.
   for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L)
-    computeMassInLoop(L->Header);
+    computeMassInLoop(*L);
 }
 
 template <class BT>
-void BlockFrequencyInfoImpl<BT>::computeMassInLoop(const BlockNode &LoopHead) {
+void BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
   // Compute mass in loop.
-  DEBUG(dbgs() << "compute-mass-in-loop: " << getBlockName(LoopHead) << "\n");
+  DEBUG(dbgs() << "compute-mass-in-loop: " << getBlockName(Loop.Header)
+               << "\n");
 
-  Working[LoopHead.Index].Mass = BlockMass::getFull();
-  propagateMassToSuccessors(LoopHead, LoopHead);
+  Working[Loop.Header.Index].Mass = BlockMass::getFull();
+  propagateMassToSuccessors(&Loop, Loop.Header);
 
-  for (const BlockNode &M : getLoopPackage(LoopHead).Members)
-    propagateMassToSuccessors(LoopHead, M);
+  for (const BlockNode &M : Loop.Members)
+    propagateMassToSuccessors(&Loop, M);
 
-  computeLoopScale(LoopHead);
-  packageLoop(LoopHead);
+  computeLoopScale(Loop);
+  packageLoop(Loop);
 }
 
 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
@@ -1503,31 +1502,35 @@ template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
     if (Working[Node.Index].hasLoopHeader())
       continue;
 
-    propagateMassToSuccessors(BlockNode(), Node);
+    propagateMassToSuccessors(nullptr, Node);
   }
 }
 
 template <class BT>
 void
-BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(const BlockNode &LoopHead,
+BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
                                                       const BlockNode &Node) {
   DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
   // Calculate probability for successors.
   Distribution Dist;
+  BlockNode LoopHead;
+  if (OuterLoop)
+    LoopHead = OuterLoop->Header;
   if (Node != LoopHead && Working[Node.Index].isLoopHeader())
-    addLoopSuccessorsToDist(LoopHead, Node, Dist);
+    addLoopSuccessorsToDist(OuterLoop, *Working[Node.Index].Loop, Dist);
   else {
     const BlockT *BB = getBlock(Node);
     for (auto SI = Successor::child_begin(BB), SE = Successor::child_end(BB);
          SI != SE; ++SI)
       // Do not dereference SI, or getEdgeWeight() is linear in the number of
       // successors.
-      addToDist(Dist, LoopHead, Node, getNode(*SI), BPI->getEdgeWeight(BB, SI));
+      addToDist(Dist, OuterLoop, Node, getNode(*SI),
+                BPI->getEdgeWeight(BB, SI));
   }
 
   // Distribute mass to successors, saving exit and backedge data in the
   // loop header.
-  distributeMass(Node, LoopHead, Dist);
+  distributeMass(Node, OuterLoop, Dist);
 }
 
 template <class BT>

diff --git a/lib/Analysis/BlockFrequencyInfoImpl.cpp b/lib/Analysis/BlockFrequencyInfoImpl.cpp
index 42c674983c40944385ae0a531fa5c2ec54e8abe7..8476eadbda67f79f0216192eb9678e4dd476f7e1 100644 (file)
--- a/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -653,13 +653,17 @@ static BlockMass &getPackageMass(BlockFrequencyInfoImplBase &BFI,
 }
 
 void BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,
-                                           const BlockNode &LoopHead,
+                                           const LoopData *OuterLoop,
                                            const BlockNode &Pred,
                                            const BlockNode &Succ,
                                            uint64_t Weight) {
   if (!Weight)
     Weight = 1;
 
+  BlockNode LoopHead;
+  if (OuterLoop)
+    LoopHead = OuterLoop->Header;
+
 #ifndef NDEBUG
   auto debugSuccessor = [&](const char *Type, const BlockNode &Resolved) {
     dbgs() << "  =>"
@@ -698,18 +702,14 @@ void BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,
 }
 
 void BlockFrequencyInfoImplBase::addLoopSuccessorsToDist(
-    const BlockNode &LoopHead, const BlockNode &LocalLoopHead,
-    Distribution &Dist) {
-  LoopData &LoopPackage = getLoopPackage(LocalLoopHead);
-  const LoopData::ExitMap &Exits = LoopPackage.Exits;
-
+    const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist) {
   // Copy the exit map into Dist.
-  for (const auto &I : Exits)
-    addToDist(Dist, LoopHead, LocalLoopHead, I.first, I.second.getMass());
+  for (const auto &I : Loop.Exits)
+    addToDist(Dist, OuterLoop, Loop.Header, I.first, I.second.getMass());
 
   // We don't need this map any more.  Clear it to prevent quadratic memory
   // usage in deeply nested loops with irreducible control flow.
-  LoopPackage.Exits.clear();
+  Loop.Exits.clear();
 }
 
 /// \brief Get the maximum allowed loop scale.
@@ -719,41 +719,39 @@ void BlockFrequencyInfoImplBase::addLoopSuccessorsToDist(
 static Float getMaxLoopScale() { return Float(1, 12); }
 
 /// \brief Compute the loop scale for a loop.
-void BlockFrequencyInfoImplBase::computeLoopScale(const BlockNode &LoopHead) {
+void BlockFrequencyInfoImplBase::computeLoopScale(LoopData &Loop) {
   // Compute loop scale.
-  DEBUG(dbgs() << "compute-loop-scale: " << getBlockName(LoopHead) << "\n");
+  DEBUG(dbgs() << "compute-loop-scale: " << getBlockName(Loop.Header) << "\n");
 
   // LoopScale == 1 / ExitMass
   // ExitMass == HeadMass - BackedgeMass
-  LoopData &LoopPackage = getLoopPackage(LoopHead);
-  BlockMass ExitMass = BlockMass::getFull() - LoopPackage.BackedgeMass;
+  BlockMass ExitMass = BlockMass::getFull() - Loop.BackedgeMass;
 
   // Block scale stores the inverse of the scale.
-  LoopPackage.Scale = ExitMass.toFloat().inverse();
+  Loop.Scale = ExitMass.toFloat().inverse();
 
   DEBUG(dbgs() << " - exit-mass = " << ExitMass << " (" << BlockMass::getFull()
-               << " - " << LoopPackage.BackedgeMass << ")\n"
-               << " - scale = " << LoopPackage.Scale << "\n");
+               << " - " << Loop.BackedgeMass << ")\n"
+               << " - scale = " << Loop.Scale << "\n");
 
-  if (LoopPackage.Scale > getMaxLoopScale()) {
-    LoopPackage.Scale = getMaxLoopScale();
+  if (Loop.Scale > getMaxLoopScale()) {
+    Loop.Scale = getMaxLoopScale();
     DEBUG(dbgs() << " - reduced-to-max-scale: " << getMaxLoopScale() << "\n");
   }
 }
 
 /// \brief Package up a loop.
-void BlockFrequencyInfoImplBase::packageLoop(const BlockNode &LoopHead) {
-  DEBUG(dbgs() << "packaging-loop: " << getBlockName(LoopHead) << "\n");
-  auto &PackagedLoop = getLoopPackage(LoopHead);
-  PackagedLoop.IsPackaged = true;
+void BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) {
+  DEBUG(dbgs() << "packaging-loop: " << getBlockName(Loop.Header) << "\n");
+  Loop.IsPackaged = true;
   DEBUG(for (const BlockNode &M
-             : PackagedLoop.Members) {
+             : Loop.Members) {
                dbgs() << " - node: " << getBlockName(M.Index) << "\n";
              });
 }
 
 void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
-                                                const BlockNode &LoopHead,
+                                                LoopData *OuterLoop,
                                                 Distribution &Dist) {
   BlockMass Mass = getPackageMass(*this, Source);
   DEBUG(dbgs() << "  => mass:  " << Mass
@@ -776,9 +774,9 @@ void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
   (void)debugAssign;
 #endif
 
-  LoopData *LoopPackage = 0;
-  if (LoopHead.isValid())
-    LoopPackage = &getLoopPackage(LoopHead);
+  BlockNode LoopHead;
+  if (OuterLoop)
+    LoopHead = OuterLoop->Header;
   for (const Weight &W : Dist.Weights) {
     // Check for a local edge (forward and non-exit).
     if (W.Type == Weight::Local) {
@@ -789,12 +787,12 @@ void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
     }
 
     // Backedges and exits only make sense if we're processing a loop.
-    assert(LoopPackage && "backedge or exit outside of loop");
+    assert(OuterLoop && "backedge or exit outside of loop");
 
     // Check for a backedge.
     if (W.Type == Weight::Backedge) {
       BlockMass Back = D.takeBackedgeMass(W.Amount);
-      LoopPackage->BackedgeMass += Back;
+      OuterLoop->BackedgeMass += Back;
       DEBUG(debugAssign(BlockNode(), Back, "back"));
       continue;
     }
@@ -802,7 +800,7 @@ void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
     // This must be an exit.
     assert(W.Type == Weight::Exit);
     BlockMass Exit = D.takeExitMass(W.Amount);
-    LoopPackage->Exits.push_back(std::make_pair(W.TargetNode, Exit));
+    OuterLoop->Exits.push_back(std::make_pair(W.TargetNode, Exit));
     DEBUG(debugAssign(W.TargetNode, Exit, "exit"));
   }
 }