Subzero: Loop Invariant Code Motion

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
@@ skipping 18 matching lines @@
   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
+  // is bounded linear. ncbray suggests another algorithm whichis  linear in

[Jim Stichnoth, 2016/07/12 10:51:51]

undo this

   // practice but not bounded linear. I think it also finds dominators.
   // http://lenx.100871.net/papers/loop-SAS.pdf
-  void computeLoopNestDepth();
+  CfgUnorderedMap<SizeT, CfgVector<SizeT>> getLoopInfo() { return 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 18 matching lines @@
 
     void setOnStack(bool NewValue = true) { OnStack = NewValue; }
     bool isOnStack() const { return OnStack; }
 
     void setDeleted() { Deleted = true; }
     bool isDeleted() const { return Deleted; }
 
     void incrementLoopNestDepth();
     bool hasSelfEdge() const;
 
+    CfgNode *getNode() { return BB; }
+
   private:
     CfgNode *BB;
     NodeList::const_iterator Succ;
     IndexT Index;
     IndexT LowLink;
     bool OnStack;
     bool Deleted = false;
   };
 
   using LoopNodeList = CfgVector<LoopNode>;
@@ skipping 10 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;
 };
 
 } // end of namespace Ice
 
 #endif //  SUBZERO_SRC_ICELOOPANALYZER_H