From 92897fda32f8df464e0056a7f1c7259303f6015e Mon Sep 17 00:00:00 2001
From: "Duncan P. N. Exon Smith" <dexonsmith@apple.com>
Date: Tue, 22 Apr 2014 03:31:37 +0000
Subject: blockfreq: Use pointers to loops instead of an index

Store pointers directly to loops inside the nodes.  This could have been
done without changing the type stored in `std::vector<>`.  However,
rather than computing the number of loops before constructing them
(which `LoopInfo` doesn't provide directly), I've switched to a
`vector<unique_ptr<LoopData>>`.

This adds some heap overhead, but the number of loops is typically
small.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206857 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/BlockFrequencyInfoImpl.h | 29 +++++++++++++-------------
 1 file changed, 15 insertions(+), 14 deletions(-)

(limited to 'include')

diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index bea9f79aeb..ca98a2e1d2 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -945,28 +945,30 @@ public:
     typedef SmallVector<std::pair<BlockNode, BlockMass>, 4> ExitMap;
     typedef SmallVector<BlockNode, 4> MemberList;
     BlockNode Header;       ///< Header.
+    bool IsPackaged;        ///< Whether this has been packaged.
     ExitMap Exits;          ///< Successor edges (and weights).
     MemberList Members;     ///< Members of the loop.
     BlockMass BackedgeMass; ///< Mass returned to loop header.
     BlockMass Mass;
     Float Scale;
 
-    LoopData(const BlockNode &Header) : Header(Header) {}
+    LoopData(const BlockNode &Header) : Header(Header), IsPackaged(false) {}
   };
 
   /// \brief Index of loop information.
   struct WorkingData {
+    LoopData *Loop;           ///< The loop this block is the header of.
     BlockNode ContainingLoop; ///< The block whose loop this block is inside.
-    uint32_t LoopIndex;       ///< Index into PackagedLoops.
     bool IsPackaged;          ///< Has ContainingLoop been packaged up?
-    bool IsAPackage;          ///< Has this block's loop been packaged up?
     BlockMass Mass;           ///< Mass distribution from the entry block.
 
-    WorkingData()
-        : LoopIndex(UINT32_MAX), IsPackaged(false), IsAPackage(false) {}
+    WorkingData() : Loop(nullptr), IsPackaged(false) {}
 
     bool hasLoopHeader() const { return ContainingLoop.isValid(); }
-    bool isLoopHeader() const { return LoopIndex != UINT32_MAX; }
+    bool isLoopHeader() const { return Loop; }
+
+    /// \brief Has this block's loop been packaged up?
+    bool isAPackage() const { return Loop && Loop->IsPackaged; }
   };
 
   /// \brief Unscaled probability weight.
@@ -1040,7 +1042,7 @@ public:
   std::vector<WorkingData> Working;
 
   /// \brief Indexed information about packaged loops.
-  std::vector<LoopData> PackagedLoops;
+  std::vector<std::unique_ptr<LoopData>> PackagedLoops;
 
   /// \brief Add all edges out of a packaged loop to the distribution.
   ///
@@ -1061,9 +1063,8 @@ public:
 
   LoopData &getLoopPackage(const BlockNode &Head) {
     assert(Head.Index < Working.size());
-    size_t Index = Working[Head.Index].LoopIndex;
-    assert(Index < PackagedLoops.size());
-    return PackagedLoops[Index];
+    assert(Working[Head.Index].Loop != nullptr);
+    return *Working[Head.Index].Loop;
   }
 
   /// \brief Distribute mass according to a distribution.
@@ -1428,8 +1429,8 @@ template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
     BlockNode Header = getNode(Loop->getHeader());
     assert(Header.isValid());
 
-    Working[Header.Index].LoopIndex = PackagedLoops.size();
-    PackagedLoops.emplace_back(Header);
+    PackagedLoops.emplace_back(new LoopData(Header));
+    Working[Header.Index].Loop = PackagedLoops.back().get();
     DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n");
   }
 
@@ -1452,7 +1453,7 @@ template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
     assert(HeaderData.isLoopHeader());
 
     Working[Index].ContainingLoop = Header;
-    PackagedLoops[HeaderData.LoopIndex].Members.push_back(Index);
+    HeaderData.Loop->Members.push_back(Index);
     DEBUG(dbgs() << " - loop = " << getBlockName(Header)
                  << ": member = " << getBlockName(Index) << "\n");
   }
@@ -1460,7 +1461,7 @@ 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 = PackagedLoops.rbegin(), LE = PackagedLoops.rend(); L != LE; ++L)
+  for (const auto &L : make_range(PackagedLoops.rbegin(), PackagedLoops.rend()))
     computeMassInLoop(L->Header);
 }
 
-- 
cgit v1.2.3