[Beignet] [PATCH] reuse the loop info from llvm.

[xionghu.luo at intel.com]

From: Luo Xionghu <xionghu.luo at intel.com>

the original loop detect algorithm caused the luxmark building
performance 10x regression, this patch reused the loop info from llvm to
handle SelfLoopNode.
the trimmed path couldn't recognize nested while structures(if nodes in
while caused performance regression). also the simple while loop node
is still not handled yet.

Signed-off-by: Luo Xionghu <xionghu.luo at intel.com>
---
 backend/src/ir/structural_analysis.cpp |   53 +++++++++++++-------------------
 backend/src/ir/structural_analysis.hpp |    4 ---
 2 files changed, 21 insertions(+), 36 deletions(-)

diff --git a/backend/src/ir/structural_analysis.cpp b/backend/src/ir/structural_analysis.cpp
index 1e98629..21c04f3 100644
--- a/backend/src/ir/structural_analysis.cpp
+++ b/backend/src/ir/structural_analysis.cpp
@@ -667,21 +667,6 @@ namespace analysis
   }
 
 
-  bool ControlTree::pathBack(Node* m, Node* n)
-  {
-    for(NodeSet::const_iterator iter = n->preds().begin(); iter!= n->preds().end(); iter++)
-    {
-      if(isBackedge(*iter, n))
-      {
-        visited.clear();
-        if(path(m, *iter, n))
-          return true;
-      }
-    }
-
-    return false;
-  }
-
   /* this algorithm is from Muchnick's textbook(sec 7.7) (Advanced Compiler Design and Implementation) */
   Node* ControlTree::acyclicRegionType(Node* node, NodeSet& nset)
   {
@@ -841,7 +826,6 @@ namespace analysis
     return NULL;
   }
 
-
   bool ControlTree::path(Node *from, Node *to, Node *notthrough)
   {
 
@@ -863,9 +847,6 @@ namespace analysis
   }
 
 
-  /* this algorithm could work right, but it is quite inefficient, and
-   * we are not handling any cyclic regions at this moment, so here just
-   * ignore the identification of cyclic regions. */
   Node * ControlTree::cyclicRegionType(Node *node, NodeList &nset)
   {
     /* check for self-loop */
@@ -1029,23 +1010,34 @@ namespace analysis
           if(nset.find(entry) != nset.end())
             entry = region;
         }
-        // FIXME loop optimization is still buggy and under development, now disable it by default.
         else
         {
-#if 0
           reachUnder.clear();
           nset.clear();
-          for(NodeList::const_iterator m = post_order.begin(); m != post_order.end(); m++)
-          {
-            if(*m != n && pathBack(*m, n))
-            {
-              reachUnder.push_front(*m);
-              nset.insert(*m);
+
+          //reuse the loop info from llvm gaterLoopInfo.
+          const gbe::vector<ir::Loop *> &loops = fn->getLoops();
+          if(loops.size() == 0){
+            post_ctr++;
+            continue;
+          }
+
+          Node* loop_header = NULL;
+          for (auto l : loops) {
+            ir::BasicBlock &a = fn->getBlock(l->bbs[0]);
+            loop_header = bbmap.find(&a)->second;
+
+            if(loop_header == n){
+              for (auto bb : l->bbs) {
+                ir::BasicBlock &tmp = fn->getBlock(bb);
+                Node* node_ = bbmap.find(&tmp)->second;
+                reachUnder.push_front(node_);
+                nset.insert(node_);
+              }
+              break;
             }
           }
 
-          reachUnder.push_front(n);
-          nset.insert(n);
           region = cyclicRegionType(n, reachUnder);
 
           if(NULL != region)
@@ -1060,9 +1052,6 @@ namespace analysis
           {
             post_ctr++;
           }
-#else
-          post_ctr++;
-#endif
         }
       }
 
diff --git a/backend/src/ir/structural_analysis.hpp b/backend/src/ir/structural_analysis.hpp
index dc2f3c2..7aaa533 100644
--- a/backend/src/ir/structural_analysis.hpp
+++ b/backend/src/ir/structural_analysis.hpp
@@ -300,10 +300,6 @@ namespace analysis
     bool isCyclic(Node*);
     /* is this a back edge? */
     bool isBackedge(const Node*, const Node*);
-    /* returns true if there is a node k such that there is a
-     * (possibly empty) path from m to k that does not pass through n
-     * and an edge k->n that is a back edge, and false otherwise. */
-    bool pathBack(Node*, Node*);
     /* check if there is a barrier in a basic block */
     bool checkForBarrier(const ir::BasicBlock*);
     /* insert while instruction at the proper position of Node */
-- 
1.7.9.5