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

[Zhigang Gong]

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