[Beignet] [PATCH] GBE: handle dead loop BBs in liveness analysis.

[Yang, Rong R]

LGTM, thanks.

> -----Original Message-----
> From: Gong, Zhigang
> Sent: Friday, October 24, 2014 11:41
> To: beignet at lists.freedesktop.org
> Cc: yan.wang at linux.intel.com; Yang, Rong R; Gong, Zhigang
> Subject: [PATCH] GBE: handle dead loop BBs in liveness analysis.
> 
> Considering the following CFG, our previous liveness analysis will only back
> traverse from the exit point BB, thus the BB 6 and 7 will not be handled.
> 
>     4---
>     |   |
>     |   |
>     5 --|---> 10 ---> ret
>     |   |
>     |   |
>     6<--
>     |
>     |<--
>     7   |
>     |   |
>      ---
> 
> Although the CFG looks not a normal application as once it goes to block 6, it
> will enter a dead loop and will never return, we still need to compile it
> successfully.
> 
> This patch is to fix the bug at:
> https://bugs.freedesktop.org/show_bug.cgi?id=85362
> 
> Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
> ---
>  backend/src/ir/liveness.cpp | 11 ++++++++++-  backend/src/ir/liveness.hpp
> |  1 +
>  2 files changed, 11 insertions(+), 1 deletion(-)
> 
> diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp index
> eaf6728..35b935f 100644
> --- a/backend/src/ir/liveness.cpp
> +++ b/backend/src/ir/liveness.cpp
> @@ -41,7 +41,11 @@ namespace ir {
>        }
>      });
>      // Now with iterative analysis, we compute liveout and livein sets
> -    this->computeLiveInOut();
> +    while (unvisitBlocks.size()) {
> +      if (workSet.size() == 0)
> +        workSet.insert(--unvisitBlocks.end(), unvisitBlocks.end());
> +      this->computeLiveInOut();
> +    }
>      // extend register (def in loop, use out-of-loop) liveness to the whole loop
>      set<Register> extentRegs;
>      this->computeExtraLiveInOut(extentRegs);
> @@ -98,6 +102,7 @@ namespace ir {
>        this->initInstruction(*info, insn);
>      });
>      liveness[&bb] = info;
> +    unvisitBlocks.insert(info);
>      if(!bb.liveout.empty())
>        info->liveOut.insert(bb.liveout.begin(), bb.liveout.end());
>    }
> @@ -124,12 +129,16 @@ namespace ir {
>      while(!workSet.empty()) {
>        auto currInfo = *workSet.begin();
>        workSet.erase(currInfo);
> +      if (unvisitBlocks.find(currInfo) != unvisitBlocks.end())
> +        unvisitBlocks.erase(currInfo);
>        for (auto currOutVar : currInfo->liveOut)
>          if (!currInfo->varKill.contains(currOutVar))
>            currInfo->upwardUsed.insert(currOutVar);
>        bool isChanged = false;
>        for (auto prev : currInfo->bb.getPredecessorSet()) {
>          BlockInfo *prevInfo = liveness[prev];
> +        if (unvisitBlocks.find(currInfo) != unvisitBlocks.end())
> +          unvisitBlocks.erase(currInfo);
>          for (auto currInVar : currInfo->upwardUsed) {
>            if (!prevInfo->bb.undefPhiRegs.contains(currInVar)) {
>              auto changed = prevInfo->liveOut.insert(currInVar);
> diff --git a/backend/src/ir/liveness.hpp b/backend/src/ir/liveness.hpp index
> d55e00d..d1e1a53 100644
> --- a/backend/src/ir/liveness.hpp
> +++ b/backend/src/ir/liveness.hpp
> @@ -132,6 +132,7 @@ namespace ir {
>      /*! Set of work list block which has exit(return) instruction */
>      typedef set <struct BlockInfo*> WorkSet;
>      WorkSet workSet;
> +    WorkSet unvisitBlocks;
> 
>      /*! Use custom allocators */
>      GBE_CLASS(Liveness);
> --
> 1.8.3.2