Add structure identification on ir level

Add tool structures and functions for identifying if-then and
if-else structures on Gen IR level.

Signed-off-by: Yongjia Zhang <yongjia.zhang@intel.com>
Reviewed-by: Zhigang Gong <zhigang.gong@linux.intel.com>

6 files changed, 1464 insertions, 9 deletions

diff --git a/backend/src/CMakeLists.txt b/backend/src/CMakeLists.txt
index 4fa84873..47504822 100644
--- a/backend/src/CMakeLists.txt
+++ b/backend/src/CMakeLists.txt
@@ -134,6 +134,8 @@ else (GBE_USE_BLOB)
     ir/lowering.hpp
     ir/printf.cpp
     ir/printf.hpp
+    ir/structural_analysis.cpp
+    ir/structural_analysis.hpp
     backend/context.cpp
     backend/context.hpp
     backend/program.cpp
diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp
index a46108ea..519a70b8 100644
--- a/backend/src/ir/function.cpp
+++ b/backend/src/ir/function.cpp
@@ -126,7 +126,7 @@ namespace ir {
     }
 
     // Reset the label to block mapping
-    this->labels.resize(last);
+    //this->labels.resize(last);
     foreachBlock([&](BasicBlock &bb) {
       const Instruction *first = bb.getFirstInstruction();
       const LabelInstruction *label = cast<LabelInstruction>(first);
@@ -185,7 +185,7 @@ namespace ir {
       return &bb == this->blocks[0];
   }
 
-  const BasicBlock &Function::getTopBlock(void) const {
+  BasicBlock &Function::getTopBlock(void) const {
     GBE_ASSERT(blockNum() > 0 && blocks[0] != NULL);
     return *blocks[0];
   }
@@ -202,7 +202,7 @@ namespace ir {
     return *blocks[n-1];
   }
 
-  const BasicBlock &Function::getBlock(LabelIndex label) const {
+  BasicBlock &Function::getBlock(LabelIndex label) const {
     GBE_ASSERT(label < labelNum() && labels[label] != NULL);
     return *labels[label];
   }
@@ -245,7 +245,7 @@ namespace ir {
       }
       if (bb.size() == 0) return;
       Instruction *last = bb.getLastInstruction();
-      if (last->isMemberOf<BranchInstruction>() == false) {
+      if (last->isMemberOf<BranchInstruction>() == false || last->getOpcode() == OP_ENDIF || last->getOpcode() == OP_ELSE) {
         jumpToNext = &bb;
         return;
       }
@@ -310,7 +310,11 @@ namespace ir {
   // Basic Block
   ///////////////////////////////////////////////////////////////////////////
 
-  BasicBlock::BasicBlock(Function &fn) : fn(fn) {
+  BasicBlock::BasicBlock(Function &fn) : needEndif(true), needIf(true), endifLabel(0),
+                                         matchingEndifLabel(0), matchingElseLabel(0),
+                                         thisElseLabel(0), belongToStructure(false),
+                                         isStructureExit(false), matchingStructureEntry(NULL),
+                                         fn(fn) {
     this->nextBlock = this->prevBlock = NULL;
   }
 
@@ -325,6 +329,11 @@ namespace ir {
     this->push_back(&insn);
   }
 
+  void BasicBlock::insertAt(iterator pos, Instruction &insn) {
+    insn.setParent(this);
+    this->insert(pos, &insn);
+  }
+
   Instruction *BasicBlock::getFirstInstruction(void) const {
     GBE_ASSERT(this->begin() != this->end());
     const Instruction &insn = *this->begin();
diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index 0886b509..2710b17a 100644
--- a/backend/src/ir/function.hpp
+++ b/backend/src/ir/function.hpp
@@ -31,6 +31,7 @@
 #include "ir/sampler.hpp"
 #include "ir/printf.hpp"
 #include "ir/image.hpp"
+#include "ir/structural_analysis.hpp"
 #include "sys/vector.hpp"
 #include "sys/set.hpp"
 #include "sys/map.hpp"
@@ -40,7 +41,6 @@
 
 namespace gbe {
 namespace ir {
-
   /*! Commonly used in the CFG */
   typedef set<BasicBlock*> BlockSet;
   class Unit; // Function belongs to a unit
@@ -59,6 +59,7 @@ namespace ir {
     ~BasicBlock(void);
     /*! Append a new instruction at the end of the stream */
     void append(Instruction &insn);
+    void insertAt(iterator pos, Instruction &insn);
     /*! Get the parent function */
     Function &getParent(void) { return fn; }
     const Function &getParent(void) const { return fn; }
@@ -84,6 +85,63 @@ namespace ir {
     }
     set <Register> undefPhiRegs;
     set <Register> definedPhiRegs;
+  /* these three are used by structure transforming */
+  public:
+    /* if needEndif is true, it means that this bb is the exit of an
+     * outermost structure, so this block needs another endif to match
+     * the if inserted at the entry of this structure, otherwise this
+     * block is in the middle of a structure, there's no need to insert
+     * extra endif. */
+    bool needEndif;
+    /* if needIf is true, it means that this bb is the entry of an
+     * outermost structure, so this block needs an if instruction just
+     * like other unstructured bbs. otherwise this block is in the
+     * middle of a structure, there's no need to insert an if. */
+    bool needIf;
+    /* since we need to insert an if and endif at the entry and exit
+     * bb of an outermost structure respectively, so the endif is not
+     * in the same bb with if, in order to get the endif's position,
+     * we need to store the endif label in the entry bb. */
+    LabelIndex endifLabel;
+    /* the identified if-then and if-else structure contains more than
+     * one bbs, in order to insert if, else and endif properly, we give
+     * all the IF ELSE and ENDIF a label for convenience. matchingEndifLabel
+     * is used when inserts instruction if and else, and matchingElseLabel
+     * is used when inserts instruction if. */
+    LabelIndex matchingEndifLabel;
+    LabelIndex matchingElseLabel;
+    /* IR ELSE's target is the matching ENDIF's LabelIndex, thisElseLabel
+     * is used to store the virtual label of the instruction just below
+     * ELSE. */
+    LabelIndex thisElseLabel;
+    /* betongToStructure is used as a mark of wether this bb belongs to an
+     * identified structure. */
+    bool belongToStructure;
+    /* isStructureExit and matchingStructureEntry is used for buildJIPs at
+     * backend, isStructureExit is true means the bb is an identified structure's
+     * exit bb, while matchingStructureEntry means the entry bb of the same
+     * identified structure. so if isStructureExit is false then matchingStructureEntry
+     * is meaningless. */
+    bool isStructureExit;
+    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:
+     *  0
+     *  |\
+     *  1 \
+     *  |  2
+     *  4  |
+     *   \ /
+     *    3
+     * we would identify 1 and 4 an sequence structure and 0 1 4 2 an if-else structure.
+     * since we will insert an else instruction at the top of bb 2, we have to add an
+     * unconditional jump at the bottom of bb 4 to bb 2 for executing the inserted else. this
+     * would cause a change of CFG. at origin, bb 2 always executes before bb 4, but after
+     * this insertion, bb 2 may executes after bb 4 which leads to bb 2's livein(i.e. part of
+     * bb 0's liveout) may be destroyed by bb 4. so we inserted the livein of the entry of
+     * else node into all the basic blocks belong to 'then' part while the liveout is
+     * calculated in structural_analysis.cpp:calculateNecessaryLiveout(); */
+    std::set<Register> liveout;
   private:
     friend class Function; //!< Owns the basic blocks
     BlockSet predecessors; //!< Incoming blocks
@@ -277,13 +335,13 @@ namespace ir {
     /*! Says if this is the top basic block (entry point) */
     bool isEntryBlock(const BasicBlock &bb) const;
     /*! Get function the entry point block */
-    const BasicBlock &getTopBlock(void) const;
+    BasicBlock &getTopBlock(void) const;
     /*! Get the last block */
     const BasicBlock &getBottomBlock(void) const;
     /*! Get the last block */
     BasicBlock &getBottomBlock(void);
     /*! Get block from its label */
-    const BasicBlock &getBlock(LabelIndex label) const;
+    BasicBlock &getBlock(LabelIndex label) const;
     /*! Get the label instruction from its label index */
     const LabelInstruction *getLabelInstruction(LabelIndex index) const;
     /*! Return the number of instructions of the largest basic block */
@@ -354,6 +412,7 @@ namespace ir {
     /*! add the loop info for later liveness analysis */
     void addLoop(const vector<LabelIndex> &bbs, const vector<std::pair<LabelIndex, LabelIndex>> &exits);
     INLINE const vector<Loop * > &getLoops() { return loops; }
+    vector<BasicBlock *> &getBlocks() { return blocks; }
   private:
     friend class Context;           //!< Can freely modify a function
     std::string name;               //!< Function name
diff --git a/backend/src/ir/instruction.cpp b/backend/src/ir/instruction.cpp
index f714ecf7..30068935 100644
--- a/backend/src/ir/instruction.cpp
+++ b/backend/src/ir/instruction.cpp
@@ -1656,10 +1656,17 @@ DECL_MEM_FN(GetImageInfoInstruction, const uint8_t, getImageIndex(void), getImag
 
   std::ostream &operator<< (std::ostream &out, const Instruction &insn) {
     const Function &fn = insn.getFunction();
+    const BasicBlock *bb = insn.getParent();
     switch (insn.getOpcode()) {
 #define DECL_INSN(OPCODE, CLASS) \
       case OP_##OPCODE: \
-        reinterpret_cast<const internal::CLASS&>(insn).out(out, fn); \
+          if(OP_##OPCODE == OP_ELSE) \
+          { \
+            reinterpret_cast<const internal::CLASS&>(insn).out(out, fn); \
+            out << "  <**>label: " << bb->thisElseLabel; \
+            break; \
+          } \
+          reinterpret_cast<const internal::CLASS&>(insn).out(out, fn); \
         break;
 #include "instruction.hxx"
 #undef DECL_INSN
diff --git a/backend/src/ir/structural_analysis.cpp b/backend/src/ir/structural_analysis.cpp
new file mode 100644
index 00000000..dfc21183
--- /dev/null
+++ b/backend/src/ir/structural_analysis.cpp
@@ -0,0 +1,1046 @@
+/*
+ * structural_analysis.hpp
+ * This code is derived from the ControlTree.h and ControlTree.cpp of
+ * project gpuocelot by Yongjia Zhang.
+ * The original copyright of gpuocelot appears below in its entirety.
+ */
+
+/*
+ * Copyright 2011
+ * GEORGIA TECH RESEARCH CORPORATION
+ * ALL RIGHTS RESERVED
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *     * Redistributions of source code must retain the above copyright
+ * notice,   this list of conditions and the following disclaimers.
+ *     * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimers in the
+ *       documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of GEORGIA TECH RESEARCH CORPORATION nor the
+ * names of  its contributors may be used to endorse or promote
+ * products derived  from this software without specific prior
+ * written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY GEORGIA TECH RESEARCH CORPORATION ''AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GEORGIA TECH RESEARCH
+ * CORPORATION BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You agree that the Software will not be shipped, transferred, exported,
+ * or re-exported directly into any country prohibited by the United States
+ * Export Administration Act and the regulations thereunder nor will be
+ * used for any purpose prohibited by the Act.
+ */
+
+
+#include "structural_analysis.hpp"
+
+namespace analysis
+{
+  ControlTree::~ControlTree()
+  {
+    NodeVector::iterator iter = nodes.begin();
+    NodeVector::iterator iter_end = nodes.end();
+    while(iter != iter_end)
+    {
+      delete *iter;
+      iter++;
+    }
+  }
+
+  /* recursive mark the bbs' variable needEndif, the bbs all belong to node.*/
+  void ControlTree::markNeedIf(Node *node, bool status)
+  {
+    if(node->type() == BasicBlock)
+    {
+      ir::BasicBlock* bb = ((BasicBlockNode*)node)->getBasicBlock();
+      bb->needIf = status;
+      return;
+    }
+    NodeList::iterator it = node->children.begin();
+    while(it != node->children.end())
+    {
+      markNeedIf(*it,status);
+      it++;
+    }
+  }
+
+  /* recursive mark the bbs' variable needIf, the bbs all belong to node.*/
+  void ControlTree::markNeedEndif(Node *node, bool status)
+  {
+    if(node->type() == BasicBlock)
+    {
+      ir::BasicBlock* bb = ((BasicBlockNode*)node)->getBasicBlock();
+      bb->needEndif = status;
+      return;
+    }
+
+    NodeList::iterator it = node->children.begin();
+    while(it != node->children.end())
+    {
+      markNeedEndif(*it, status);
+      it++;
+    }
+  }
+
+  /* recursive mark the bbs' variable mark, the bbs all belong to node. */
+  void ControlTree::markStructuredNodes(Node *node, bool status)
+  {
+    if(node->type() == BasicBlock)
+    {
+      BasicBlockNode* pbb = static_cast<BasicBlockNode *>(node);
+      pbb->getBasicBlock()->belongToStructure = true;
+    }
+    node->mark = status;
+    NodeList::iterator it = node->children.begin();
+    while(it != node->children.end())
+    {
+      markStructuredNodes(*it, status);
+      it++;
+    }
+  }
+
+  void ControlTree::handleIfNode(Node *node, ir::LabelIndex& matchingEndifLabel, ir::LabelIndex& matchingElseLabel)
+  {
+    ir::BasicBlock *pbb = node->getExit();
+    ir::BranchInstruction* pinsn = static_cast<ir::BranchInstruction *>(pbb->getLastInstruction());
+    ir::Register reg = pinsn->getPredicateIndex();
+    ir::BasicBlock::iterator it = pbb->end();
+    it--;
+    /* since this node is an if node, so we remove the BRA instruction at the bottom of the exit BB of 'node',
+     * and insert IF instead
+     */
+    pbb->erase(it);
+    ir::Instruction insn = ir::IF(matchingElseLabel, reg);
+    ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    pbb->append(*p_new_insn);
+    pbb->matchingEndifLabel = matchingEndifLabel;
+    pbb->matchingElseLabel = matchingElseLabel;
+  }
+
+  void ControlTree::handleThenNode(Node *node, ir::LabelIndex& endiflabel)
+  {
+    ir::BasicBlock *pbb = node->getExit();
+    ir::BasicBlock::iterator it = pbb->end();
+    it--;
+    ir::Instruction *p_last_insn = pbb->getLastInstruction();
+
+    endiflabel = fn->newLabel();
+    //pbb->thisEndifLabel = endiflabel;
+
+    ir::Instruction insn = ir::ENDIF(endiflabel);
+    ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    // we need to insert ENDIF before the BRA(if exists).
+    bool append_bra = false;
+    if((*it).getOpcode() == ir::OP_BRA)
+    {
+      pbb->erase(it);
+      append_bra = true;
+    }
+    pbb->append(*p_new_insn);
+    if(append_bra)
+      pbb->append(*p_last_insn);
+  }
+
+
+  void ControlTree::handleThenNode2(Node *node, Node *elsenode, ir::LabelIndex elseBBLabel)
+  {
+    ir::BasicBlock *pbb = node->getExit();
+    ir::BasicBlock::iterator it = pbb->end();
+    it--;
+    if((*it).getOpcode() == ir::OP_BRA)
+      pbb->erase(it);
+
+    if(node->getExit()->getNextBlock() == elsenode->getEntry())
+      return;
+
+    // Add an unconditional jump to 'else' block
+    ir::Instruction insn = ir::BRA(elseBBLabel);
+    ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    pbb->append(*p_new_insn);
+  }
+
+
+  void ControlTree::handleElseNode(Node* node, ir::LabelIndex& elselabel, ir::LabelIndex& endiflabel)
+  {
+    // to insert ENDIF properly
+    handleThenNode(node, endiflabel);
+
+    ir::BasicBlock *pbb = node->getEntry();
+    ir::BasicBlock::iterator it = pbb->begin();
+    it++;
+
+    elselabel = fn->newLabel();
+    pbb->thisElseLabel = elselabel;
+
+    // insert ELSE properly
+    ir::Instruction insn = ir::ELSE(endiflabel);
+    ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+
+    pbb->insertAt(it, *p_new_insn);
+  }
+
+
+  void ControlTree::handleStructuredNodes()
+  {
+    NodeVector::iterator it;
+    NodeVector::iterator end = nodes.end();
+    NodeVector::iterator begin = nodes.begin();
+    it = end;
+    it--;
+    NodeVector::reverse_iterator rit = nodes.rbegin();
+    /* structured bbs only need if and endif insn to handle the execution
+     * in structure entry and exit BasicBlock, so we process the nodes backward, since
+     * the node at the back of nodes is always a 'not smaller' structure then
+     * the ones before it. we mark the nodes which are sub-nodes of the node
+     * we are dealing with, in order to ensure we are always handling the 'biggest'
+     * structures */
+    while(rit != nodes.rend())
+    {
+      if((*rit)->type() == IfThen || (*rit)->type() == IfElse)
+      {
+        if(false == (*rit)->mark && (*rit)->canBeHandled)
+        {
+          markStructuredNodes(*rit, true);
+          /* only the entry bb of this structure needs 'if' at backend and
+           * only the exit bb of this structure needs 'endif' at backend
+           * see comment about needEndif and needIf at function.hpp for detail. */
+          markNeedEndif(*rit, false);
+          markNeedIf(*rit, false);
+          ir::BasicBlock* entry = (*rit)->getEntry();
+          ir::BasicBlock* eexit = (*rit)->getExit();
+          entry->needIf = true;
+          eexit->needEndif = true;
+          entry->endifLabel = fn->newLabel();
+          eexit->endifLabel = entry->endifLabel;
+          eexit->isStructureExit = true;
+          eexit->matchingStructureEntry = entry;
+        }
+      }
+      rit++;
+    }
+
+    rit = nodes.rbegin();
+    gbe::vector<ir::BasicBlock *> &blocks = fn->getBlocks();
+    std::vector<ir::BasicBlock *> bbs;
+    bbs.resize(blocks.size());
+
+    /* here insert the bras to the BBs, which would
+     * simplify the reorder of basic blocks */
+    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)
+      {
+        ir::Instruction insn = ir::BRA(bbs[i]->getNextBlock()->getLabelIndex());
+        ir::Instruction* pNewInsn = bbs[i]->getParent().newInstruction(insn);
+        bbs[i]->append(*pNewInsn);
+      }
+    }
+
+    /* now, reorder the basic blocks to reduce the unconditional jump we inserted whose
+     * targets are the 'else' nodes. the algorithm is quite simple, just put the unstructured
+     * BBs(maybe belong to another structure, but not this one) in front of the entry BB of
+     * this structure in front of all the others and put the other unstructured BBs at the
+     * back of the others. the sequence of structured is get through function getStructureSequence.
+     */
+    while(rit != nodes.rend())
+    {
+      if(((*rit)->type() == IfThen || (*rit)->type() == IfElse || (*rit)->type() == Block) &&
+          (*rit)->canBeHandled && (*rit)->mark == true)
+      {
+        markStructuredNodes(*rit, false);
+        std::set<int> ns = getStructureBasicBlocksIndex(*rit, bbs);
+        ir::BasicBlock *entry = (*it)->getEntry();
+
+        int entryIndex = *(ns.begin());
+        for(size_t i=0; i<bbs.size(); ++i)
+        {
+          if(bbs[i] == entry)
+            entryIndex = i;
+        }
+
+        std::set<int>::iterator iter = ns.begin();
+        int index = *iter;
+
+        std::vector<ir::BasicBlock *> unstruSeqHead;
+        std::vector<ir::BasicBlock *> unstruSeqTail;
+
+        iter = ns.begin();
+        while(iter != ns.end())
+        {
+          if(index != *iter)
+          {
+            if(index < entryIndex)
+              unstruSeqHead.push_back(bbs[index]);
+            else
+              unstruSeqTail.push_back(bbs[index]);
+            index++;
+          }
+          else
+          {
+            index++;
+            iter++;
+          }
+        }
+
+        std::vector<ir::BasicBlock *> struSeq;
+        getStructureSequence(*rit, struSeq);
+
+        int firstindex = *(ns.begin());
+        for(size_t i = 0; i < unstruSeqHead.size(); ++i)
+          bbs[firstindex++] = unstruSeqHead[i];
+        for(size_t i = 0; i < struSeq.size(); ++i)
+          bbs[firstindex++] = struSeq[i];
+        for(size_t i = 0; i < unstruSeqTail.size(); ++i)
+          bbs[firstindex++] = unstruSeqTail[i];
+      }
+      rit++;
+    }
+
+   /* now, erase the BRAs inserted before whose targets are their fallthrough blocks */
+    for(size_t i=0; i<bbs.size(); ++i)
+    {
+      if(bbs[i]->getLastInstruction()->getOpcode() == ir::OP_BRA &&
+         !((ir::BranchInstruction*)(bbs[i]->getLastInstruction()))->isPredicated())
+      {
+        if(((ir::BranchInstruction *)bbs[i]->getLastInstruction())->getLabelIndex() == bbs[i+1]->getLabelIndex())
+        {
+          ir::BasicBlock::iterator it= bbs[i]->end();
+          it--;
+
+          bbs[i]->erase(it);
+        }
+      }
+    }
+    for(size_t i=0; i<bbs.size(); ++i)
+      blocks[i] = bbs[i];
+
+    fn->sortLabels();
+    fn->computeCFG();
+
+#if 1
+    it = begin;
+    while(it != end)
+    {
+      if((*it)->canBeHandled)
+      {
+        switch((*it)->type())
+        {
+          case IfThen:
+            {
+              NodeList::iterator child_iter = (*it)->children.end();
+              ir::LabelIndex endiflabel;
+              child_iter--;
+              handleThenNode(*child_iter, endiflabel); // this call would pass out the proper endiflabel for handleIfNode's use.
+              child_iter--;
+              handleIfNode(*child_iter, endiflabel, endiflabel);
+            }
+            break;
+
+          case IfElse:
+            {
+              NodeList::iterator child_iter = (*it)->children.end();
+              ir::LabelIndex endiflabel;
+              ir::LabelIndex elselabel;
+              NodeList::iterator else_node;
+              child_iter--;
+              else_node = child_iter;
+              handleElseNode(*child_iter, elselabel, endiflabel);
+              ir::LabelIndex elseBBLabel = (*child_iter)->getEntry()->getLabelIndex();
+              child_iter--;
+              handleThenNode2(*child_iter, *else_node, elseBBLabel);
+              child_iter--;
+              handleIfNode(*child_iter, endiflabel, elselabel);
+            }
+            break;
+
+          default:
+            break;
+        }
+      }
+
+      it++;
+    }
+#endif
+
+  }
+
+  void ControlTree::getStructureSequence(Node *node, std::vector<ir::BasicBlock*> &seq)
+  {
+    /* in the control tree, for if-then, if node is before then node; for if-else, the
+     * stored sequence is if-then-else, for block structure, the stored sequence is just
+     * their executed sequence. so we could just get the structure sequence by recrusive
+     * calls getStructureSequence to all the elements in children one by one.
+     */
+    if(node->type() == BasicBlock)
+    {
+      seq.push_back(((BasicBlockNode *)node)->getBasicBlock());
+      return;
+    }
+
+    NodeList::iterator iter = node->children.begin();
+    while(iter != node->children.end())
+    {
+      getStructureSequence(*iter, seq);
+      iter++;
+    }
+
+  }
+
+
+  std::set<int> ControlTree::getStructureBasicBlocksIndex(Node* node, std::vector<ir::BasicBlock *> &bbs)
+  {
+    std::set<int> result;
+    if(node->type() == BasicBlock)
+    {
+      for(size_t i=0; i<bbs.size(); i++)
+      {
+        if(bbs[i] == ((BasicBlockNode *)node)->getBasicBlock())
+        {
+          result.insert(i);
+          break;
+        }
+      }
+      return result;
+    }
+    NodeList::iterator iter = (node->children).begin();
+    NodeList::iterator end = (node->children).end();
+    while(iter != end)
+    {
+      std::set<int> ret = getStructureBasicBlocksIndex(*iter, bbs);
+      result.insert(ret.begin(), ret.end());
+      iter++;
+    }
+    return result;
+  }
+
+
+  std::set<ir::BasicBlock *> ControlTree::getStructureBasicBlocks(Node *node)
+  {
+    std::set<ir::BasicBlock *> result;
+    if(node->type() == BasicBlock)
+    {
+      result.insert(((BasicBlockNode *)node)->getBasicBlock());
+      return result;
+    }
+    NodeList::iterator iter = (node->children).begin();
+    NodeList::iterator end = (node->children).end();
+    while(iter != end)
+    {
+      std::set<ir::BasicBlock *> ret = getStructureBasicBlocks(*iter);
+      result.insert(ret.begin(), ret.end());
+      iter++;
+    }
+    return result;
+  }
+
+
+  Node* ControlTree::insertNode(Node *p_node)
+  {
+    nodes.push_back(p_node);
+    return p_node;
+  }
+
+
+  bool ControlTree::checkForBarrier(const ir::BasicBlock* bb)
+  {
+    ir::BasicBlock::const_iterator iter = bb->begin();
+    ir::BasicBlock::const_iterator iter_end = bb->end();
+    while(iter != iter_end)
+    {
+      if((*iter).getOpcode() == ir::OP_SYNC)
+        return true;
+      iter++;
+    }
+
+    return false;
+  }
+
+
+  void ControlTree::getLiveIn(ir::BasicBlock& bb, std::set<ir::Register>& livein)
+  {
+    ir::BasicBlock::iterator iter = bb.begin();
+    std::set<ir::Register> varKill;
+    while(iter != bb.end())
+    {
+      ir::Instruction& insn = *iter;
+      const uint32_t srcNum = insn.getSrcNum();
+      const uint32_t dstNum = insn.getDstNum();
+      for(uint32_t srcID = 0; srcID < srcNum; ++srcID)
+      {
+        const ir::Register reg = insn.getSrc(srcID);
+        if(varKill.find(reg) == varKill.end())
+          livein.insert(reg);
+      }
+      for(uint32_t dstID = 0; dstID < dstNum; ++dstID)
+      {
+        const ir::Register reg = insn.getDst(dstID);
+        varKill.insert(reg);
+      }
+
+      iter++;
+    }
+  }
+
+  void ControlTree::calculateNecessaryLiveout()
+  {
+    NodeVector::iterator iter = nodes.begin();
+
+    while(iter != nodes.end())
+    {
+      switch((*iter)->type())
+      {
+        case IfElse:
+        {
+          std::set<ir::BasicBlock *> bbs;
+          NodeList::iterator thenIter = (*iter)->children.begin();
+          thenIter++;
+          bbs = getStructureBasicBlocks(*thenIter);
+
+          Node *elseNode = *((*iter)->children.rbegin());
+          std::set<ir::Register> livein;
+          getLiveIn(*(elseNode->getEntry()), livein);
+
+          std::set<ir::BasicBlock *>::iterator bbiter = bbs.begin();
+          while(bbiter != bbs.end())
+          {
+            (*bbiter)->liveout.insert(livein.begin(), livein.end());
+            bbiter++;
+          }
+        }
+
+        default:
+          break;
+      }
+      iter++;
+    }
+  }
+
+
+  void ControlTree::initializeNodes()
+  {
+    ir::BasicBlock& tmp_bb = fn->getTopBlock();
+    ir::BasicBlock* p_tmp_bb = &tmp_bb;
+    Node* p = NULL;
+
+    if(NULL != p_tmp_bb)
+    {
+      Node *p_tmp_node = new BasicBlockNode(p_tmp_bb);
+      p_tmp_node->label = p_tmp_bb->getLabelIndex();
+
+      if(checkForBarrier(p_tmp_bb))
+        p_tmp_node->hasBarrier() = true;
+
+      nodes.push_back(p_tmp_node);
+      bbmap[p_tmp_bb] = p_tmp_node;
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+      p = p_tmp_node;
+    }
+
+    while(p_tmp_bb != NULL)
+    {
+      Node *p_tmp_node = new BasicBlockNode(p_tmp_bb);
+      p_tmp_node->label = p_tmp_bb->getLabelIndex();
+
+      if(checkForBarrier(p_tmp_bb))
+        p_tmp_node->hasBarrier() = true;
+
+      p->fallthrough() = p_tmp_node;
+      p = p_tmp_node;
+      nodes.push_back(p_tmp_node);
+      bbmap[p_tmp_bb] = p_tmp_node;
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+    }
+
+    if(NULL != p)
+      p->fallthrough() = NULL;
+
+    p_tmp_bb = &tmp_bb;
+
+    this->nodes_entry = bbmap[p_tmp_bb];
+
+    while(p_tmp_bb != NULL)
+    {
+      ir::BlockSet::const_iterator iter_begin = p_tmp_bb->getPredecessorSet().begin();
+      ir::BlockSet::const_iterator iter_end = p_tmp_bb->getPredecessorSet().end();
+      while(iter_begin != iter_end)
+      {
+        bbmap[p_tmp_bb]->preds().insert(bbmap[*iter_begin]);
+        iter_begin++;
+      }
+
+      iter_begin = p_tmp_bb->getSuccessorSet().begin();
+      iter_end = p_tmp_bb->getSuccessorSet().end();
+      while(iter_begin != iter_end)
+      {
+        bbmap[p_tmp_bb]->succs().insert(bbmap[*iter_begin]);
+        iter_begin++;
+      }
+
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+    }
+  }
+
+
+  void ControlTree::DFSPostOrder(Node *start)
+  {
+    visited.insert(start);
+    NodeSet::iterator y;
+    NodeSet::iterator iter_begin = start->succs().begin();
+    NodeSet::iterator iter_end = start->succs().end();
+    for(y = iter_begin; y != iter_end; ++y )
+    {
+      if(visited.find(*y) != visited.end())
+        continue;
+      DFSPostOrder(*y);
+    }
+    post_order.push_back(start);
+  }
+
+
+  bool ControlTree::isCyclic(Node* node)
+  {
+    if(node->type() == NaturalLoop ||
+       node->type() == WhileLoop ||
+       node->type() == SelfLoop)
+      return true;
+
+    return false;
+  }
+
+
+  bool ControlTree::isBackedge(const Node* head, const Node* tail)
+  {
+    const Node* match[] = {head, tail};
+    NodeList::iterator n = find_first_of(post_order.begin(), post_order.end(), match, match + 2);
+
+    if(*n == head)
+      return true;
+    if(*n == tail)
+      return false;
+
+    return false;
+  }
+
+
+  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)
+  {
+    nset.clear();
+    Node *n;
+    bool p, s, barrier;
+    NodeList nodes;
+
+    n = node;
+    p = true;
+    s = (n->succs().size()==1);
+    barrier = n->hasBarrier();
+    while(p && s && !barrier)
+    {
+      if(nset.insert(n).second)
+        nodes.push_back(n);
+      n = *(n->succs().begin());
+      barrier = n->hasBarrier();
+      p = (n->preds().size() == 1);
+      s = (n->succs().size() == 1);
+    }
+
+    if(p && !barrier)
+    {
+      if(nset.insert(n).second)
+        nodes.push_back(n);
+    }
+
+    n = node;
+    p = (n->preds().size() == 1);
+    s = true;
+    barrier = n->hasBarrier();
+
+    while(p && s && !barrier)
+    {
+      if(nset.insert(n).second)
+        nodes.push_front(n);
+      n = *(n->preds().begin());
+      barrier = n->hasBarrier();
+      p = (n->preds().size() == 1);
+      s = (n->succs().size() == 1);
+    }
+
+    if(s && !barrier)
+    {
+      if(nset.insert(n).second)
+        nodes.push_front(n);
+    }
+
+    node = n;
+
+    if(nodes.size() >=2 )
+    {
+      Node* p = new BlockNode(nodes);
+      NodeList::iterator iter = nodes.begin();
+      while(iter != nodes.end())
+      {
+        if((*iter)->canBeHandled == false)
+        {
+          p->canBeHandled = false;
+          break;
+        }
+        iter++;
+      }
+
+      return insertNode(p);
+    }
+
+    else if(node->succs().size() == 2)
+    {
+      Node *m;
+      m = *(node->succs().begin());
+      n = *(++(node->succs().begin()));
+
+      /* check for if node then n */
+      if(n->succs().size() == 1 &&
+         n->preds().size() == 1 &&
+         *(n->succs().begin()) == m &&
+         !n->hasBarrier() && !node->hasBarrier())
+      {
+        nset.clear();
+        nset.insert(node);
+        nset.insert(n);
+
+        Node* p = new IfThenNode(node, n);
+
+        if(node->canBeHandled == false || n->canBeHandled == false)
+          p->canBeHandled = false;
+
+        return insertNode(p);
+      }
+
+      /* check for if node then m */
+      if(m->succs().size() == 1 &&
+         m->preds().size() == 1 &&
+         *(m->succs().begin()) == n &&
+         !m->hasBarrier() && !node->hasBarrier())
+      {
+        nset.clear();
+        nset.insert(node);
+        nset.insert(m);
+
+        Node* p = new IfThenNode(node, m);
+
+        if(node->canBeHandled == false || m->canBeHandled == false)
+          p->canBeHandled = false;
+
+        return insertNode(p);
+      }
+
+      /* check for if node then n else m */
+      if(m->succs().size() == 1 && n->succs().size() == 1 &&
+         m->preds().size() == 1 && n->preds().size() == 1 &&
+         *(m->succs().begin()) == *(n->succs().begin()) &&
+         node->fallthrough() == n && !m->hasBarrier() && !n->hasBarrier() && !node->hasBarrier())
+      {
+        nset.clear();
+        nset.insert(node);
+        nset.insert(n);
+        nset.insert(m);
+
+        Node* p = new IfElseNode(node, n, m);
+
+        if(node->canBeHandled == false ||
+           m->canBeHandled == false ||
+           n->canBeHandled == false)
+          p->canBeHandled = false;
+
+        return insertNode(p);
+      }
+
+      /* check for if node then m else n */
+      if(m->succs().size() == 1 && n->succs().size() == 1 &&
+         m->preds().size() == 1 && n->preds().size() == 1 &&
+         *(m->succs().begin()) == *(n->succs().begin()) &&
+         node->fallthrough() == m && !m->hasBarrier() && !n->hasBarrier() &&!node->hasBarrier())
+      {
+        nset.clear();
+        nset.insert(node);
+        nset.insert(m);
+        nset.insert(n);
+
+        Node* p = new IfElseNode(node, m, n);
+
+        if(node->canBeHandled == false ||
+           m->canBeHandled == false ||
+           n->canBeHandled == false)
+          p->canBeHandled = false;
+        return insertNode(p);
+      }
+    }
+
+    return NULL;
+  }
+
+
+  bool ControlTree::path(Node *from, Node *to, Node *notthrough)
+  {
+
+    if(from == notthrough || visited.find(from) != visited.end())
+      return false;
+
+    if(from == to)
+      return true;
+
+    visited.insert(from);
+
+    for(NodeSet::const_iterator s = from->succs().begin(); s != from->succs().end(); s++)
+    {
+      if(path(*s, to, notthrough))
+        return true;
+    }
+
+    return false;
+  }
+
+
+  /* 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)
+  {
+#if 0
+    /* check for self-loop */
+    if(nset.size() == 1)
+    {
+      if(node->succs().find(node) != node->succs().end())
+      {
+        Node* p = new SelfLoopNode(node);
+
+        p->canBeHandled = false;
+
+        return insertNode(p);
+      }
+      else
+        return NULL;
+    }
+
+    /* check for improper region */
+    for(NodeList::const_iterator m = nset.begin(); m != nset.end(); m++)
+    {
+      visited.clear();
+      if(!path(node, *m))
+        return NULL;
+    }
+
+    /* check for while loop */
+    NodeList::iterator m;
+    for(m = nset.begin(); m != nset.end(); ++m)
+    {
+      if(*m == node)
+        continue;
+      if(node->succs().size() == 2 && (*m)->succs().size() == 1 &&
+         node->preds().size() == 2 && (*m)->preds().size() == 1)
+      {
+        Node* p = new WhileLoopNode(node, *m);
+
+        p->canBeHandled = false;
+
+        return insertNode(p);
+      }
+    }
+#endif
+    return NULL;
+  }
+
+
+  /* this algorithm is from Muchnick's textbook(sec 7.7) (Advanced Compiler Design and Implementation) */
+  void ControlTree::reduce(Node* node,  NodeSet nodeSet)
+  {
+    NodeSet::iterator n;
+    for(n = nodeSet.begin(); n != nodeSet.end(); n++)
+    {
+      NodeSet::iterator p;
+      for(p = (*n)->preds().begin(); p != (*n)->preds().end(); p++)
+      {
+        if(nodeSet.find(*p) != nodeSet.end())
+          continue;
+
+        (*p)->succs().erase(*n);
+
+        (*p)->succs().insert(node);
+        node->preds().insert(*p);
+
+        if((*p)->fallthrough() == *n)
+          (*p)->fallthrough() = node;
+      }
+
+
+     NodeSet::iterator s;
+     for(s = (*n)->succs().begin(); s != (*n)->succs().end(); s++)
+     {
+        if(nodeSet.find(*s) != nodeSet.end())
+          continue;
+
+       (*s)->preds().erase(*n);
+
+       (*s)->preds().insert(node);
+       node->succs().insert(*s);
+
+       if((*n)->fallthrough() == *s)
+         node->fallthrough() = *s;
+     }
+    }
+
+    if(!isCyclic(node))
+    {
+      for(n = nodeSet.begin(); n != nodeSet.end(); n++)
+      {
+        bool shouldbreak = false;
+        NodeSet::iterator p;
+        for(p = (*n)->preds().begin(); p != (*n)->preds().end(); p++)
+        {
+          if(nodeSet.find(*p) == nodeSet.end())
+            continue;
+
+          if(isBackedge(*p, *n))
+          {
+            node->preds().insert(node);
+            node->succs().insert(node);
+
+            shouldbreak = true;
+            break;
+          }
+        }
+
+        if(shouldbreak)
+          break;
+      }
+    }
+
+    compact(node, nodeSet);
+  }
+
+
+  /* this algorithm is from Muchnick's textbook(sec 7.7) (Advanced Compiler Design and Implementation) */
+  void ControlTree::compact(Node* node,  NodeSet nodeSet)
+  {
+    NodeList::iterator n, pos;
+    for(n = post_order.begin(); n!= post_order.end() && !nodeSet.empty();)
+    {
+      if(!nodeSet.erase(*n))
+      {
+        n++;
+        continue;
+      }
+
+      n = post_order.erase(n);
+      pos = n;
+    }
+
+    post_ctr = post_order.insert(pos, node);
+  }
+
+
+  /* this algorithm is from Muchnick's textbook(sec 7.7) (Advanced Compiler Design and Implementation) */
+  void ControlTree::structuralAnalysis(Node *entry)
+  {
+    Node* n;
+    NodeSet nset;
+    NodeList reachUnder;
+    bool changed;
+    do
+    {
+      changed = false;
+      post_order.clear();
+      visited.clear();
+
+      DFSPostOrder(entry);
+      post_ctr = post_order.begin();
+
+      while(post_order.size() > 1 && post_ctr != post_order.end())
+      {
+        n = *post_ctr;
+        Node* region = acyclicRegionType(n, nset);
+
+        if( NULL != region)
+        {
+          changed = true;
+
+          reduce(region, nset);
+
+          if(nset.find(entry) != nset.end())
+            entry = region;
+        }
+        else
+        {
+        /* We now only deal with acyclic regions at this moment. */
+#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);
+            }
+          }
+
+          reachUnder.push_front(n);
+          nset.insert(n);
+          region = cyclicRegionType(n, reachUnder);
+
+          if(NULL != region)
+          {
+            reduce(region, nset);
+            changed = true;
+
+            if(nset.find(entry) != nset.end())
+              entry = region;
+          }
+          else
+          {
+#endif
+            post_ctr++;
+         // }
+        }
+      }
+
+      if(!changed)
+        break;
+
+    } while(post_order.size()>1);
+
+  }
+
+  void ControlTree::analyze()
+  {
+    initializeNodes();
+    structuralAnalysis(nodes_entry);
+    handleStructuredNodes();
+    calculateNecessaryLiveout();
+  }
+}
diff --git a/backend/src/ir/structural_analysis.hpp b/backend/src/ir/structural_analysis.hpp
new file mode 100644
index 00000000..06c2f5f7
--- /dev/null
+++ b/backend/src/ir/structural_analysis.hpp
@@ -0,0 +1,332 @@
+/*
+ * structural_analysis.hpp
+ * This code is derived from the ControlTree.h and ControlTree.cpp of
+ * project gpuocelot by Yongjia Zhang.
+ * The original copyright of gpuocelot appears below in its entirety.
+ */
+
+/*
+ * Copyright 2011
+ * GEORGIA TECH RESEARCH CORPORATION
+ * ALL RIGHTS RESERVED
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *     * Redistributions of source code must retain the above copyright
+ * notice,   this list of conditions and the following disclaimers.
+ *     * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimers in the
+ *       documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of GEORGIA TECH RESEARCH CORPORATION nor the
+ * names of  its contributors may be used to endorse or promote
+ * products derived  from this software without specific prior
+ * written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY GEORGIA TECH RESEARCH CORPORATION ''AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GEORGIA TECH RESEARCH
+ * CORPORATION BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You agree that the Software will not be shipped, transferred, exported,
+ * or re-exported directly into any country prohibited by the United States
+ * Export Administration Act and the regulations thereunder nor will be
+ * used for any purpose prohibited by the Act.
+ */
+
+
+#ifndef __STRUCTURAL_ANALYSIS_HPP__
+#define __STRUCTURAL_ANALYSIS_HPP__
+
+#include "ir/unit.hpp"
+#include "ir/function.hpp"
+#include "ir/instruction.hpp"
+
+#include <iostream>
+#include <unordered_set>
+#include <unordered_map>
+#include <vector>
+#include <map>
+#include <list>
+#include <algorithm>
+#include <set>
+#define TRANSFORM_UNSTRUCTURE
+
+namespace analysis
+{
+  using namespace std;
+  using namespace gbe;
+
+  enum RegionType
+  {
+    BasicBlock = 0,
+    Block,
+    IfThen,
+    IfElse,
+    SelfLoop,
+    WhileLoop,
+    NaturalLoop
+  } ;
+
+  /* control tree virtual node */
+  class Node;
+
+  typedef unordered_set<Node *> NodeSet;
+  typedef list<Node *> NodeList;
+  typedef std::vector<Node *> NodeVector;
+
+  /* control tree virtual node */
+  class Node
+  {
+  public:
+    Node(RegionType rtype, const NodeList& children): has_barrier(false), mark(false), canBeHandled(true)
+    {
+      this->rtype = rtype;
+      this->children = children;
+    }
+    virtual ~Node() {}
+    NodeSet& preds() { return pred; }
+    NodeSet& succs() { return succ; }
+    Node*& fallthrough() { return fall_through; }
+    bool& hasBarrier() { return has_barrier; }
+    RegionType type() { return rtype; }
+    virtual ir::BasicBlock* getEntry()
+    {
+      return (*(children.begin()))->getEntry();
+    }
+    virtual ir::BasicBlock* getExit()
+    {
+      return (*(children.rbegin()))->getExit();
+    }
+
+  public:
+    RegionType rtype;
+    NodeSet pred;
+    NodeSet succ;
+    NodeList children;
+    Node* fall_through;
+    bool has_barrier;
+    bool mark;
+    bool canBeHandled;
+    //label is for debug
+    int label;
+  };
+
+  /* represents basic block */
+  class BasicBlockNode : public Node
+  {
+  public:
+    BasicBlockNode(ir::BasicBlock *p_bb) : Node(BasicBlock, NodeList()) { this->p_bb = p_bb; }
+    virtual ~BasicBlockNode() {}
+    ir::BasicBlock* getBasicBlock() { return p_bb; }
+    virtual ir::BasicBlock* getEntry() { return p_bb; }
+    virtual ir::BasicBlock* getExit() { return p_bb; }
+    virtual ir::BasicBlock* getFirstBB() { return p_bb; }
+  private:
+    ir::BasicBlock *p_bb;
+  };
+
+  /* a sequence of nodes */
+  class BlockNode : public Node
+  {
+  public:
+    BlockNode(NodeList& children) : Node(Block, children) {}
+    virtual ~BlockNode(){}
+  };
+
+  /* If-Then structure node */
+  class IfThenNode : public Node
+  {
+  public:
+    IfThenNode(Node* cond, Node* ifTrue) : Node(IfThen, BuildChildren(cond, ifTrue)) {}
+    virtual ~IfThenNode() {}
+
+  private:
+    const NodeList BuildChildren(Node* cond, Node* ifTrue)
+    {
+      NodeList children;
+      children.push_back(cond);
+      children.push_back(ifTrue);
+      return children;
+    }
+  };
+
+  /* If-Else structure node */
+  class IfElseNode : public Node
+  {
+  public:
+    IfElseNode(Node* cond, Node* ifTrue, Node* ifFalse) : Node(IfElse, BuildChildren(cond, ifTrue, ifFalse)) {}
+    virtual ~IfElseNode() {}
+
+  private:
+    const NodeList BuildChildren(Node* cond, Node* ifTrue, Node* ifFalse)
+    {
+      NodeList children;
+      children.push_back(cond);
+      children.push_back(ifTrue);
+      children.push_back(ifFalse);
+      return children;
+    }
+  };
+
+#if 0
+  /* Self loop structure node */
+  class SelfLoopNode : public Node
+  {
+  public:
+    SelfLoopNode(Node* node) : Node(SelfLoop, BuildChildren(node)) {}
+    virtual ~SelfLoopNode() {}
+    virtual ir::BasicBlock* getEntry()
+    {
+      return (*(children.begin()))->getEntry();
+    }
+    virtual ir::BasicBlock* getExit()
+    {
+      return (*(children.begin()))->getExit();
+    }
+
+  private:
+    const NodeList BuildChildren(Node *node)
+    {
+      NodeList children;
+      children.push_back(node);
+      return children;
+    }
+  };
+
+  /* While loop structure node */
+  class WhileLoopNode : public Node
+  {
+  public:
+    WhileLoopNode(Node* cond, Node* execute) : Node(WhileLoop, BuildChildren(cond, execute)) {}
+    virtual ~WhileLoopNode() {}
+    virtual ir::BasicBlock* getEntry()
+    {
+      return (*(children.begin()))->getEntry();
+    }
+    virtual ir::BasicBlock* getExit()
+    {
+      return (*(children.begin()))->getExit();
+    }
+
+  private:
+    const NodeList BuildChildren(Node* cond, Node* execute)
+    {
+      NodeList children;
+      children.push_back(cond);
+      children.push_back(execute);
+      return children;
+    }
+
+  };
+
+  /* Natural loop structure node */
+  class NaturalLoopNode : public Node
+  {
+  public:
+    NaturalLoopNode(const NodeList& children): Node(NaturalLoop, children){}
+    virtual ~NaturalLoopNode() {}
+    virtual ir::BasicBlock* getEntry()
+    {
+      //TODO implement it
+      return NULL;
+    }
+    virtual ir::BasicBlock* getExit()
+    {
+      //TODO implement it
+      return NULL;
+    }
+  };
+#endif
+
+  /* computes the control tree, and do the structure identification during the computation */
+  class ControlTree
+  {
+  public:
+    void analyze();
+
+    ControlTree(ir::Function* fn) { this->fn = fn; }
+    ~ControlTree();
+
+  private:
+    /* create a sequence of BasicBlockNodes, which are refered to the basic blocks in the function */
+    void initializeNodes();
+    /* insert a new Node, and returns the pointer of the node */
+    Node* insertNode(Node *);
+    /* do the structural analysis */
+    void structuralAnalysis(Node * entry);
+    /* do the dfs post order traverse of the current CFG */
+    void DFSPostOrder(Node *start);
+    /* returns true if there is a (possibly empty) path from m to k that does not pass through n */
+    bool path(Node *m, Node *k, Node *n = NULL);
+    /* link region node into abstract flowgraph, adjust the predecessor and successor functions, and augment the control tree */
+    void reduce(Node* node,  NodeSet nodeSet);
+    /* adds node to the control tree, inserts node into _post
+     * at the highest-numbered position of a node in nodeSet, removes
+     * the nodes in nodeSet from _post, compacts the remaining nodes at
+     * the beginning of _post, and sets _postCtr to the index of node
+     * in the resulting postorder */
+    void compact(Node* node,  NodeSet nodeSet);
+    Node* getNodesEntry() const  { return nodes_entry;}
+    /* determines whether node is the entry node of an acyclic
+     * control structure and returns its region. Stores in nset the set
+     * of nodes in the identified control structure */
+    Node* acyclicRegionType(Node* node, NodeSet& nset);
+    /* determines whether node is the entry node of a cyclic
+     * control structure and returns its region. Stores in nset the set
+     * of nodes in the identified control structure */
+    Node* cyclicRegionType(Node*, NodeList&);
+    /* is this a cyclic region? */
+    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*);
+    /* mark all the BasicBlockNodes of the control tree node n as status */
+    void markStructuredNodes(Node *n, bool status);
+    /* mark all the ir::BasicBlocks' needEndIf of n as status */
+    void markNeedEndif(Node * n, bool status);
+    /* mark all the ir::BasicBlocks' needIf of n as status */
+    void markNeedIf(Node *, bool);
+    /* insert IF instruction at the proper position of Node */
+    void handleIfNode(Node *, ir::LabelIndex&, ir::LabelIndex&);
+    /* insert ENDIF instruction at the proper position of Node, this Node is
+       the 'then' node of identified if-then structure */
+    void handleThenNode(Node *, ir::LabelIndex&);
+    /* handle the then node of identified if-else structure */
+    void handleThenNode2(Node *, Node *, ir::LabelIndex);
+    /* insert ELSE instruction at the proper position of Node */
+    void handleElseNode(Node *, ir::LabelIndex&, ir::LabelIndex&);
+    /* this calls other functions to finish the handling of identified structure blocks */
+    void handleStructuredNodes();
+    std::set<int> getStructureBasicBlocksIndex(Node *, std::vector<ir::BasicBlock *> &);
+    std::set<ir::BasicBlock *> getStructureBasicBlocks(Node*);
+    /* get livein of bb */
+    void getLiveIn(ir::BasicBlock& bb, std::set<ir::Register>& livein);
+    /* see comment of BasicBlock::liveout in function.hpp for detail. */
+    void calculateNecessaryLiveout();
+    /* get the exectutive sequence of structure n */
+    void getStructureSequence(Node* n, std::vector<ir::BasicBlock*> &v);
+  private:
+    ir::Function *fn;
+    NodeVector nodes;
+    Node* nodes_entry;
+    unordered_map<ir::BasicBlock *, Node *> bbmap;
+    NodeList post_order;
+    NodeSet visited;
+    NodeList::iterator post_ctr;
+  };
+}
+#endif