GBE: structurized loop exit need an extra branching instruction when do reordering.HEADmaster

When we want to reorder the BBs and move the unstructured BB out-of the
structured block, we need to add a BRA to the block. If the exit of the
structured block is a loop, we need to append a unconditional BRA right
after the predicated BRA. Otherwise, we may lost the correct successor
if an unstructured BB is moved next to this BB.

After this patch, with loop optimization enabled, there is no regression
on both utests and piglit. But there are still a few regressions in opencv
test suite:
[----------] Global test environment tear-down
[==========] 8 tests from 2 test cases ran. (40041 ms total)
[  PASSED  ] 2 tests.
[  FAILED  ] 6 tests, listed below:
[  FAILED  ] OCL_Photo/FastNlMeansDenoising.Mat/2, where GetParam() = (Channels(2), false)
[  FAILED  ] OCL_Photo/FastNlMeansDenoising.Mat/3, where GetParam() = (Channels(2), true)
[  FAILED  ] OCL_Photo/FastNlMeansDenoisingColored.Mat/0, where GetParam() = (Channels(3), false)
[  FAILED  ] OCL_Photo/FastNlMeansDenoisingColored.Mat/1, where GetParam() = (Channels(3), true)
[  FAILED  ] OCL_Photo/FastNlMeansDenoisingColored.Mat/2, where GetParam() = (Channels(4), false)
[  FAILED  ] OCL_Photo/FastNlMeansDenoisingColored.Mat/3, where GetParam() = (Channels(4), true)

So let's keep this optimizaion disabled. Will enable it when I fixed all
the known issues.

Signed-off-by: Zhigang Gong <zhigang.gong@intel.com>
Reviewed-by: Luo <xionghu.luo@intel.com>

3 files changed, 38 insertions, 14 deletions

diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp
index deb65ef..3767d9c 100644
--- a/backend/src/ir/function.cpp
+++ b/backend/src/ir/function.cpp
@@ -260,14 +260,23 @@ namespace ir {
         jumpToNext = &bb;
         return;
       }
-      const BranchInstruction &insn = cast<BranchInstruction>(*last);
-      if (insn.getOpcode() == OP_BRA) {
+      ir::BasicBlock::iterator it = --bb.end();
+      uint32_t handledInsns = 0;
+      while ((handledInsns < 2 && it != bb.end()) &&
+             static_cast<ir::BranchInstruction *>(&*it)->getOpcode() == OP_BRA) {
+        const BranchInstruction &insn = cast<BranchInstruction>(*it);
+        if (insn.getOpcode() != OP_BRA)
+          break;
         const LabelIndex label = insn.getLabelIndex();
         BasicBlock *target = this->blocks[label];
         GBE_ASSERT(target != NULL);
         target->predecessors.insert(&bb);
         bb.successors.insert(target);
-        if ( insn.isPredicated() == true) jumpToNext = &bb;
+        if (insn.isPredicated() == true) jumpToNext = &bb;
+        // If we are going to handle the second bra, this bra must be a predicated bra
+        GBE_ASSERT(handledInsns == 0 || insn.isPredicated() == true);
+        --it;
+        ++handledInsns;
       }
     });
   }
@@ -324,7 +333,9 @@ namespace ir {
   BasicBlock::BasicBlock(Function &fn) : needEndif(true), needIf(true), endifLabel(0),
                                          matchingEndifLabel(0), matchingElseLabel(0),
                                          thisElseLabel(0), belongToStructure(false),
-                                         isStructureExit(false), matchingStructureEntry(NULL),
+                                         isStructureExit(false), isLoopExit(false),
+                                         hasExtraBra(false),
+                                         matchingStructureEntry(NULL),
                                          fn(fn) {
     this->nextBlock = this->prevBlock = NULL;
   }
diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index d0b595e..0f145c5 100644
--- a/backend/src/ir/function.hpp
+++ b/backend/src/ir/function.hpp
@@ -122,6 +122,11 @@ namespace ir {
      * identified structure. so if isStructureExit is false then matchingStructureEntry
      * is meaningless. */
     bool isStructureExit;
+    /* This block is an exit point of a loop block. It may not be exit point of
+       the large structure block. */
+    bool isLoopExit;
+    /* This block has an extra branch in the end of the block. */
+    bool hasExtraBra;
     BasicBlock *matchingStructureEntry;
     /* variable liveout is for if-else structure liveness analysis. eg. we have an sequence of
      * bbs of 0, 1, 2, 3, 4 and the CFG is as below:
diff --git a/backend/src/ir/structural_analysis.cpp b/backend/src/ir/structural_analysis.cpp
index 040a7e0..1e98629 100644
--- a/backend/src/ir/structural_analysis.cpp
+++ b/backend/src/ir/structural_analysis.cpp
@@ -59,20 +59,24 @@ namespace analysis
   }
   void ControlTree::handleSelfLoopNode(Node *loopnode, ir::LabelIndex& whileLabel)
   {
+              //NodeList::iterator child_iter = (*it)->children.begin();
     ir::BasicBlock *pbb = loopnode->getExit();
-    ir::BranchInstruction* pinsn = static_cast<ir::BranchInstruction *>(pbb->getLastInstruction());
-    ir::Register reg = pinsn->getPredicateIndex();
+    GBE_ASSERT(pbb->isLoopExit);
     ir::BasicBlock::iterator it = pbb->end();
     it--;
+    if (pbb->hasExtraBra)
+      it--;
+    ir::BranchInstruction* pinsn = static_cast<ir::BranchInstruction *>(&*it);
+    ir::Register reg = pinsn->getPredicateIndex();
     /* since this node is an while node, so we remove the BRA instruction at the bottom of the exit BB of 'node',
      * and insert WHILE instead
      */
-    pbb->erase(it);
     whileLabel = pinsn->getLabelIndex();
     ir::Instruction insn = ir::WHILE(whileLabel, reg);
     ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
-    pbb->append(*p_new_insn);
+    pbb->insertAt(it, *p_new_insn);
     pbb->whileLabel = whileLabel;
+    pbb->erase(it);
   }
 
   /* recursive mark the bbs' variable needEndif, the bbs all belong to node.*/
@@ -257,11 +261,15 @@ namespace analysis
     for(size_t i = 0; i < blocks.size(); ++i)
     {
       bbs[i] = blocks[i];
-      if(bbs[i]->getLastInstruction()->getOpcode() != ir::OP_BRA && i != blocks.size() - 1)
+      if(i != blocks.size() -1 &&
+         (bbs[i]->getLastInstruction()->getOpcode() != ir::OP_BRA ||
+         (bbs[i]->isStructureExit && bbs[i]->isLoopExit)))
       {
         ir::Instruction insn = ir::BRA(bbs[i]->getNextBlock()->getLabelIndex());
         ir::Instruction* pNewInsn = bbs[i]->getParent().newInstruction(insn);
         bbs[i]->append(*pNewInsn);
+        if (bbs[i]->isStructureExit && bbs[i]->isLoopExit)
+          bbs[i]->hasExtraBra = true;
       }
     }
 
@@ -337,6 +345,9 @@ namespace analysis
           it--;
 
           bbs[i]->erase(it);
+
+          if (bbs[i]->hasExtraBra)
+            bbs[i]->hasExtraBra = false;
         }
       }
     }
@@ -346,7 +357,6 @@ namespace analysis
     fn->sortLabels();
     fn->computeCFG();
 
-#if 1
     it = begin;
     while(it != end)
     {
@@ -384,9 +394,8 @@ namespace analysis
 
           case SelfLoop:
             {
-              NodeList::iterator child_iter = (*it)->children.begin();
               ir::LabelIndex whilelabel;
-              handleSelfLoopNode(*child_iter, whilelabel);
+              handleSelfLoopNode(*it, whilelabel);
             }
             break;
 
@@ -397,7 +406,6 @@ namespace analysis
 
       it++;
     }
-#endif
 
   }
 
@@ -868,7 +876,7 @@ namespace analysis
         Node* p = new SelfLoopNode(node);
 
         p->canBeHandled = true;
-
+        node->getExit()->isLoopExit = true;
         return insertNode(p);
       }
       else