Subzero: Improve LoopAnalyzer Interface

src/IceLoopAnalyzer.h

Index: src/IceLoopAnalyzer.h
diff --git a/src/IceLoopAnalyzer.h b/src/IceLoopAnalyzer.h
index 73458fa46aa38ae47b7257b44124644167a19417..67c10e257ff39b318a1ba9e506e75d79f0e93565 100644
--- a/src/IceLoopAnalyzer.h
+++ b/src/IceLoopAnalyzer.h
@@ -21,11 +21,8 @@ namespace Ice {
 /// Analyze a function's CFG for loops. The CFG must not change during the
 /// lifetime of this object.
 class LoopAnalyzer {

[John, 2016/07/15 21:13:30]

OK, you opened pandora's box... :)

This class is really a function. Why? Well, this object has very little state of
its own, and its use

LoopAnalyzer(this).getLoopInfo()

can be replaced by

findLoopsInCfg(this);

But this is really just

this->findLoops();

If I were to refactor this code, I would get rid of this class (LoopAnalyzer),
and keep the LoopInfo here.

-  LoopAnalyzer() = delete;
-  LoopAnalyzer(const LoopAnalyzer &) = delete;
-  LoopAnalyzer &operator=(const LoopAnalyzer &) = delete;
-
 public:
+  LoopAnalyzer() = default;
   explicit LoopAnalyzer(Cfg *Func);
 
   /// Use Tarjan's strongly connected components algorithm to identify outermost
@@ -39,10 +36,38 @@ public:
   // is bounded linear. ncbray suggests another algorithm which is linear in
   // practice but not bounded linear. I think it also finds dominators.
   // http://lenx.100871.net/papers/loop-SAS.pdf
-  CfgUnorderedMap<SizeT, CfgVector<SizeT>> getLoopInfo() { return Loops; }
+  //   CfgUnorderedMap<SizeT, CfgVector<SizeT>> getLoopInfo() { return Loops; }
+  class LoopInfo {
+  public:
+    LoopInfo() {}
+    LoopInfo(Cfg *Func, const CfgVector<CfgUnorderedSet<SizeT>> Loops)

[John, 2016/07/18 15:25:36]

A nice way to decrease memory usage: pass Loops by *, and then std::swap it.

[manasijm, 2016/07/18 22:27:47]

Should be 'moved' by default in new implementation.

+        : Func(Func), Loops(Loops) {
+      computeLoopMetaData();
+    };
+
+    template <typename F> void forEachLoop(F Callback) {

[John, 2016/07/15 21:13:30]

no need for this: just create a getter for LoopIndexForHeader (see the comment
in IceCfg.h)

[manasijm, 2016/07/18 22:27:47]

Done.

+      for (auto Pair : LoopIndexForHeader) {
+        Callback(Pair.first, Loops[Pair.second]);
+      }
+    }
+    CfgNode *getHeader(CfgNode *Node);

[John, 2016/07/18 15:25:36]

getHeader, and getBody aren't used anywhere. remove them?

[manasijm, 2016/07/18 22:27:47]

Done.

+    CfgNode *getPreHeader(CfgNode *Node);
+    const CfgUnorderedSet<SizeT> &getBody(CfgNode *Header);
+
+  private:
+    void computeLoopMetaData();
+    Cfg *Func = nullptr;
+    CfgVector<CfgUnorderedSet<SizeT>> Loops;

[John, 2016/07/18 15:25:36]

How about changing this vector to be a vector of structs

struct Loop {
  const CfgUnorderedSet<SizeT> Blocks;
  CfgNode const *Header;
  CfgNode const *PreHeader;
  Loop(CfgUnorderedSet<SizeT> &&B, CfgNode *H, CfgNode *P) : Blocks(B),
Header(H), PreHeader(P) {}
}

If you do this, and you change the constructor parameter to take a CfgVector*,
then you can initialize the Loops vector as following:

LoopInfo::LoopInfo(Cfg *Func, CfgVector<CfgUnorderedSet<SizeT>> *L) {
  L->reserve(L->size());
  std::sort(Loops->begin(), Loops->end(), ...);
  for (auto *Loop : Loops) {
    auto *Header = findHeader(Loop);
    auto *PreHeader = findPreHeader(Header);
    Loops.emplace_back(std::move(*Loop), Header, PreHeader);
  }
}

But now, your CfgVector<Loop> Loops member contains everything you need to know
about your loops. Therefore, you don't really need to create a

class LoopInfo {
 public:
  LoopInfo(Cfg *Func, CfgVector<CfgUnorderedSet<SizeT>> L);
  const CfgVector<Loop> &getLoops();

 private:
  CfgVector<Loop> Loops;
};

This is really bad OOP. Your interface really is

CfgVector<Loop> computeLoopInfo(CfgVector<CfgUnorderedSet<SizeT>> L) {
  CfgVector<Loop> Loops;

  // same as LoopInfo::LoopInfo above

  return Loops;
}

+    CfgUnorderedMap<SizeT, SizeT> HeaderForNode;
+    CfgUnorderedMap<SizeT, SizeT> PreheaderForHeader;
+    /// Stores indices to the Loops array.
+    CfgUnorderedMap<SizeT, SizeT> LoopIndexForHeader;
+  };
+  LoopInfo getLoopInfo() { return LoopInfo(Func, Loops); }
 
 private:
   void computeLoopNestDepth();
+
   using IndexT = uint32_t;
   static constexpr IndexT UndefinedIndex = 0;
   static constexpr IndexT FirstDefinedIndex = 1;
@@ -113,8 +138,9 @@ private:
   /// The number of nodes which have been marked deleted. This is used to track
   /// when the iteration should end.
   LoopNodePtrList::size_type NumDeletedNodes = 0;
-  /// Detailed loop information
-  CfgUnorderedMap<SizeT, CfgVector<SizeT>> Loops;
+
+  /// All the Loops, in descending order of size
+  CfgVector<CfgUnorderedSet<SizeT>> Loops;
 };
 
 } // end of namespace Ice