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

[Zhigang Gong]

One major difference from the original version is this new method will not
treat those reduced blocks as one single node, thus it will miss some qualified
large while loop.

But it is ok to accept it as the first step to support while/loop completely,
especially it is much faster than the original method which need to call the
extreme slow pathBack.

Will push to master branch soon.

Thanks,
Zhigang Gong.

On Tue, Nov 18, 2014 at 09:37:54AM +0800, xionghu.luo at intel.com wrote:
> 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
> 
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet