Subzero: Improve LoopAnalyzer Interface

src/IceLoopAnalyzer.h

 //===- subzero/src/IceLoopAnalyzer.h - Loop Analysis ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This analysis identifies loops in the CFG.
 //===----------------------------------------------------------------------===//
 
 #ifndef SUBZERO_SRC_ICELOOPANALYZER_H
 #define SUBZERO_SRC_ICELOOPANALYZER_H
 
 #include "IceDefs.h"
 
 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
   /// to innermost loops. By deleting the head of the loop from the graph, inner
   /// loops can be found. This assumes that the head node is not shared between
   /// loops but instead all paths to the head come from 'continue' constructs.
   ///
   /// This only computes the loop nest depth within the function and does not
   /// take into account whether the function was called from within a loop.
   // TODO(ascull): this currently uses a extension of Tarjan's algorithm with
   // 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;
 
   // TODO(ascull): classify the other fields
   class LoopNode {
     LoopNode() = delete;
     LoopNode operator=(const LoopNode &) = delete;
 
   public:
@@ skipping 50 matching lines @@
   LoopNodeList AllNodes;
   /// This is used as a replacement for the call stack.
   LoopNodePtrList WorkStack;
   /// Track which loop a node belongs to.
   LoopNodePtrList LoopStack;
   /// The index to assign to the next visited node.
   IndexT NextIndex = FirstDefinedIndex;
   /// 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
 
 #endif //  SUBZERO_SRC_ICELOOPANALYZER_H