[Beignet] [PATCH] reimplement structurize algorithm.

xionghu.luo at intel.com xionghu.luo at intel.com
Wed Jun 3 22:56:27 PDT 2015


From: Luo Xionghu <xionghu.luo at intel.com>

serial, loop and if pattern match from top to down.

Signed-off-by: Luo Xionghu <xionghu.luo at intel.com>
---
 backend/src/CMakeLists.txt       |   2 +
 backend/src/ir/structurizer.cpp  | 962 +++++++++++++++++++++++++++++++++++++++
 backend/src/ir/structurizer.hpp  | 249 ++++++++++
 backend/src/llvm/llvm_to_gen.cpp |  15 +
 4 files changed, 1228 insertions(+)
 create mode 100644 backend/src/ir/structurizer.cpp
 create mode 100644 backend/src/ir/structurizer.hpp

diff --git a/backend/src/CMakeLists.txt b/backend/src/CMakeLists.txt
index 8f574d4..83fc168 100644
--- a/backend/src/CMakeLists.txt
+++ b/backend/src/CMakeLists.txt
@@ -68,6 +68,8 @@ set (GBE_SRC
     ir/printf.hpp
     ir/immediate.hpp
     ir/immediate.cpp
+    ir/structurizer.hpp
+    ir/structurizer.cpp
     backend/context.cpp
     backend/context.hpp
     backend/program.cpp
diff --git a/backend/src/ir/structurizer.cpp b/backend/src/ir/structurizer.cpp
new file mode 100644
index 0000000..66de84a
--- /dev/null
+++ b/backend/src/ir/structurizer.cpp
@@ -0,0 +1,962 @@
+/*
+ * Copyright © 2012 Intel Corporation
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "structurizer.hpp"
+#include "sys/cvar.hpp"
+
+using namespace llvm;
+namespace gbe {
+namespace ir {
+  CFGStructurizer::~CFGStructurizer()
+  {
+    BlockVector::iterator iter = blocks.begin();
+    BlockVector::iterator iter_end = blocks.end();
+    while(iter != iter_end)
+    {
+      delete *iter;
+      iter++;
+    }
+  }
+
+  void CFGStructurizer::handleSelfLoopBlock(Block *loopblock, LabelIndex& whileLabel)
+  {
+    //BlockList::iterator child_iter = (*it)->children.begin();
+    BasicBlock *pbb = loopblock->getExit();
+    GBE_ASSERT(pbb->isLoopExit);
+    BasicBlock::iterator it = pbb->end();
+    it--;
+    if (pbb->hasExtraBra)
+      it--;
+    BranchInstruction* pinsn = static_cast<BranchInstruction *>(&*it);
+
+    if(!pinsn->isPredicated()){
+      std::cout << "WARNING:" << "endless loop detected!" << std::endl;
+      return;
+    }
+    Register reg = pinsn->getPredicateIndex();
+    /* since this block is an while block, so we remove the BRA instruction at the bottom of the exit BB of 'block',
+     * and insert WHILE instead
+     */
+    whileLabel = pinsn->getLabelIndex();
+    Instruction insn = WHILE(whileLabel, reg);
+    Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    pbb->insertAt(it, *p_new_insn);
+    pbb->whileLabel = whileLabel;
+    pbb->erase(it);
+  }
+
+  /* recursive mark the bbs' variable needEndif*/
+  void CFGStructurizer::markNeedIf(Block *block, bool status)
+  {
+    if(block->type() == SingleBlockType)
+    {
+      BasicBlock* bb = ((SimpleBlock*)block)->getBasicBlock();
+      bb->needIf = status;
+      return;
+    }
+    BlockList::iterator it = block->children.begin();
+    while(it != block->children.end())
+    {
+      markNeedIf(*it,status);
+      it++;
+    }
+  }
+
+  /* recursive mark the bbs' variable needIf*/
+  void CFGStructurizer::markNeedEndif(Block *block, bool status)
+  {
+    if(block->type() == SingleBlockType)
+    {
+      BasicBlock* bb = ((SimpleBlock*)block)->getBasicBlock();
+      bb->needEndif = status;
+      return;
+    }
+
+    BlockList::iterator it = block->children.begin();
+    while(it != block->children.end())
+    {
+      markNeedEndif(*it, status);
+      it++;
+    }
+  }
+
+  /* recursive mark the bbs' variable mark*/
+  void CFGStructurizer::markStructuredBlocks(Block *block, bool status)
+  {
+    if(block->type() == SingleBlockType)
+    {
+      SimpleBlock* pbb = static_cast<SimpleBlock*>(block);
+      pbb->getBasicBlock()->belongToStructure = true;
+    }
+    block->mark = status;
+    BlockList::iterator it = block->children.begin();
+    while(it != block->children.end())
+    {
+      markStructuredBlocks(*it, status);
+      it++;
+    }
+  }
+
+  void CFGStructurizer::handleIfBlock(Block *block, LabelIndex& matchingEndifLabel, LabelIndex& matchingElseLabel)
+  {
+    BasicBlock *pbb = block->getExit();
+    BranchInstruction* pinsn = static_cast<BranchInstruction *>(pbb->getLastInstruction());
+    Register reg = pinsn->getPredicateIndex();
+    BasicBlock::iterator it = pbb->end();
+    it--;
+    /* since this block is an if block, so we remove the BRA instruction at the bottom of the exit BB of 'block',
+     * and insert IF instead
+     */
+    pbb->erase(it);
+    Instruction insn = IF(matchingElseLabel, reg, block->inversePredicate);
+    Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    pbb->append(*p_new_insn);
+    pbb->matchingEndifLabel = matchingEndifLabel;
+    pbb->matchingElseLabel = matchingElseLabel;
+  }
+
+  void CFGStructurizer::handleThenBlock(Block * block, LabelIndex& endiflabel)
+  {
+    BasicBlock *pbb = block->getExit();
+    BasicBlock::iterator it = pbb->end();
+    it--;
+    Instruction *p_last_insn = pbb->getLastInstruction();
+
+    endiflabel = fn->newLabel();
+    //pbb->thisEndifLabel = endiflabel;
+
+    Instruction insn = ENDIF(endiflabel);
+    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() == OP_BRA)
+    {
+      pbb->erase(it);
+      append_bra = true;
+    }
+    pbb->append(*p_new_insn);
+    if(append_bra)
+      pbb->append(*p_last_insn);
+  }
+
+  void CFGStructurizer::handleThenBlock2(Block *block, Block *elseblock, LabelIndex elseBBLabel)
+  {
+    BasicBlock *pbb = block->getExit();
+    BasicBlock::iterator it = pbb->end();
+    it--;
+    if((*it).getOpcode() == OP_BRA)
+      pbb->erase(it);
+
+    if(block->getExit()->getNextBlock() == elseblock->getEntry())
+      return;
+
+    // Add an unconditional jump to 'else' block
+    Instruction insn = BRA(elseBBLabel);
+    Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+    pbb->append(*p_new_insn);
+  }
+
+  void CFGStructurizer::handleElseBlock(Block * block, LabelIndex& elselabel, LabelIndex& endiflabel)
+  {
+    // to insert ENDIF properly
+    handleThenBlock(block, endiflabel);
+
+    BasicBlock *pbb = block->getEntry();
+    BasicBlock::iterator it = pbb->begin();
+    it++;
+
+    elselabel = fn->newLabel();
+    pbb->thisElseLabel = elselabel;
+
+    // insert ELSE properly
+    Instruction insn = ELSE(endiflabel);
+    Instruction* p_new_insn = pbb->getParent().newInstruction(insn);
+
+    pbb->insertAt(it, *p_new_insn);
+  }
+
+  void CFGStructurizer::handleStructuredBlocks()
+  {
+    BlockVector::iterator it;
+    BlockVector::iterator end = blocks.end();
+    BlockVector::iterator begin = blocks.begin();
+    it = end;
+    it--;
+    BlockVector::reverse_iterator rit = blocks.rbegin();
+    /* structured bbs only need if and endif insn to handle the execution
+     * in structure entry and exit BasicBlock, so we process the blocks backward, since
+     * the block at the back of blocks is always a 'not smaller' structure then
+     * the ones before it. we mark the blocks which are sub-blocks of the block
+     * we are dealing with, in order to ensure we are always handling the 'biggest'
+     * structures */
+    while(rit != blocks.rend())
+    {
+      if((*rit)->type() == IfThenType || (*rit)->type() == IfElseType|| (*rit)->type() == SelfLoopType)
+      {
+        if(false == (*rit)->mark && (*rit)->canBeHandled)
+        {
+          markStructuredBlocks(*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);
+          BasicBlock* entry = (*rit)->getEntry();
+          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 = blocks.rbegin();
+    gbe::vector<BasicBlock *> &bblocks = fn->getBlocks();
+    std::vector<BasicBlock *> bbs;
+    bbs.resize(bblocks.size());
+
+    /* here insert the bras to the BBs, which would
+     * simplify the reorder of basic blocks */
+    for(size_t i = 0; i < bblocks.size(); ++i)
+    {
+      bbs[i] = bblocks[i];
+      if(i != bblocks.size() -1 &&
+         (bbs[i]->getLastInstruction()->getOpcode() != OP_BRA ||
+         (bbs[i]->isStructureExit && bbs[i]->isLoopExit)))
+      {
+        Instruction insn = BRA(bbs[i]->getNextBlock()->getLabelIndex());
+        Instruction* pNewInsn = bbs[i]->getParent().newInstruction(insn);
+        bbs[i]->append(*pNewInsn);
+        if (bbs[i]->isStructureExit && bbs[i]->isLoopExit)
+          bbs[i]->hasExtraBra = true;
+      }
+    }
+
+    /* now, reorder the basic blocks to reduce the unconditional jump we inserted whose
+     * targets are the 'else' blocks. 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 != blocks.rend())
+    {
+      if(((*rit)->type() == IfThenType || (*rit)->type() == IfElseType || (*rit)->type() == SerialBlockType ||(*rit)->type() == SelfLoopType) &&
+          (*rit)->canBeHandled && (*rit)->mark == true)
+      {
+        markStructuredBlocks(*rit, false);
+        std::set<int> ns = getStructureBasicBlocksIndex(*rit, bbs);
+        BasicBlock *entry = (*rit)->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<BasicBlock *> unstruSeqHead;
+        std::vector<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<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() == OP_BRA &&
+         !((BranchInstruction*)(bbs[i]->getLastInstruction()))->isPredicated())
+      {
+        if(((BranchInstruction *)bbs[i]->getLastInstruction())->getLabelIndex() == bbs[i+1]->getLabelIndex())
+        {
+          BasicBlock::iterator it= bbs[i]->end();
+          it--;
+
+          bbs[i]->erase(it);
+
+          if (bbs[i]->hasExtraBra)
+            bbs[i]->hasExtraBra = false;
+        }
+      }
+    }
+    for(size_t i=0; i<bbs.size(); ++i)
+      bblocks[i] = bbs[i];
+
+    fn->sortLabels();
+    fn->computeCFG();
+
+    it = begin;
+    while(it != end)
+    {
+      if((*it)->canBeHandled)
+      {
+        switch((*it)->type())
+        {
+          case IfThenType:
+            {
+              BlockList::iterator child_iter = (*it)->children.end();
+              LabelIndex endiflabel;
+              child_iter--;
+              handleThenBlock(*child_iter, endiflabel); // this call would pass out the proper endiflabel for handleIfBlock's use.
+              child_iter--;
+              handleIfBlock(*child_iter, endiflabel, endiflabel);
+            }
+            break;
+
+          case IfElseType:
+            {
+              BlockList::iterator child_iter = (*it)->children.end();
+              LabelIndex endiflabel;
+              LabelIndex elselabel;
+              BlockList::iterator else_block;
+              child_iter--;
+              else_block= child_iter;
+              handleElseBlock(*child_iter, elselabel, endiflabel);
+              LabelIndex elseBBLabel = (*child_iter)->getEntry()->getLabelIndex();
+              child_iter--;
+              handleThenBlock2(*child_iter, *else_block, elseBBLabel);
+              child_iter--;
+              handleIfBlock(*child_iter, endiflabel, elselabel);
+            }
+            break;
+
+          case SelfLoopType:
+            {
+              LabelIndex whilelabel;
+              handleSelfLoopBlock(*it, whilelabel);
+            }
+            break;
+
+          default:
+            break;
+        }
+      }
+
+      it++;
+    }
+  }
+
+  void CFGStructurizer::getStructureSequence(Block *block, std::vector<BasicBlock*> &seq)
+  {
+    /* in the control tree, for if-then, if block is before then block; 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(block->type() == SingleBlockType)
+    {
+      seq.push_back(((SimpleBlock*)block)->getBasicBlock());
+      return;
+    }
+
+    BlockList::iterator iter = block->children.begin();
+    while(iter != block->children.end())
+    {
+      getStructureSequence(*iter, seq);
+      iter++;
+    }
+  }
+
+  std::set<int> CFGStructurizer::getStructureBasicBlocksIndex(Block* block, std::vector<BasicBlock *> &bbs)
+  {
+    std::set<int> result;
+    if(block->type() == SingleBlockType)
+    {
+      for(size_t i=0; i<bbs.size(); i++)
+      {
+        if(bbs[i] == ((SimpleBlock*)block)->getBasicBlock())
+        {
+          result.insert(i);
+          break;
+        }
+      }
+      return result;
+    }
+    BlockList::iterator iter = (block->children).begin();
+    BlockList::iterator end = (block->children).end();
+    while(iter != end)
+    {
+      std::set<int> ret = getStructureBasicBlocksIndex(*iter, bbs);
+      result.insert(ret.begin(), ret.end());
+      iter++;
+    }
+    return result;
+  }
+
+  std::set<BasicBlock *> CFGStructurizer::getStructureBasicBlocks(Block *block)
+  {
+    std::set<BasicBlock *> result;
+    if(block->type() == SingleBlockType)
+    {
+      result.insert(((SimpleBlock*)block)->getBasicBlock());
+      return result;
+    }
+    BlockList::iterator iter = (block->children).begin();
+    BlockList::iterator end = (block->children).end();
+    while(iter != end)
+    {
+      std::set<BasicBlock *> ret = getStructureBasicBlocks(*iter);
+      result.insert(ret.begin(), ret.end());
+      iter++;
+    }
+    return result;
+  }
+
+  Block* CFGStructurizer::insertBlock(Block *p_block)
+  {
+    blocks.push_back(p_block);
+    return p_block;
+  }
+
+  bool CFGStructurizer::checkForBarrier(const BasicBlock* bb)
+  {
+    BasicBlock::const_iterator iter = bb->begin();
+    BasicBlock::const_iterator iter_end = bb->end();
+    while(iter != iter_end)
+    {
+      if((*iter).getOpcode() == OP_SYNC)
+        return true;
+      iter++;
+    }
+
+    return false;
+  }
+
+  void CFGStructurizer::getLiveIn(BasicBlock& bb, std::set<Register>& livein)
+  {
+    BasicBlock::iterator iter = bb.begin();
+    std::set<Register> varKill;
+    while(iter != bb.end())
+    {
+      Instruction& insn = *iter;
+      const uint32_t srcNum = insn.getSrcNum();
+      const uint32_t dstNum = insn.getDstNum();
+      for(uint32_t srcID = 0; srcID < srcNum; ++srcID)
+      {
+        const Register reg = insn.getSrc(srcID);
+        if(varKill.find(reg) == varKill.end())
+          livein.insert(reg);
+      }
+      for(uint32_t dstID = 0; dstID < dstNum; ++dstID)
+      {
+        const Register reg = insn.getDst(dstID);
+        varKill.insert(reg);
+      }
+
+      iter++;
+    }
+  }
+
+  void CFGStructurizer::calculateNecessaryLiveout()
+  {
+    BlockVector::iterator iter = blocks.begin();
+
+    while(iter != blocks.end())
+    {
+      switch((*iter)->type())
+      {
+        case IfElseType:
+        {
+          std::set<BasicBlock *> bbs;
+          BlockList::iterator thenIter = (*iter)->children.begin();
+          thenIter++;
+          bbs = getStructureBasicBlocks(*thenIter);
+
+          Block *elseblock = *((*iter)->children.rbegin());
+          std::set<Register> livein;
+          getLiveIn(*(elseblock->getEntry()), livein);
+
+          std::set<BasicBlock *>::iterator bbiter = bbs.begin();
+          while(bbiter != bbs.end())
+          {
+            (*bbiter)->liveout.insert(livein.begin(), livein.end());
+            bbiter++;
+          }
+        }
+
+        default:
+          break;
+      }
+      iter++;
+    }
+  }
+
+  void CFGStructurizer::initializeBlocks()
+  {
+    BasicBlock& tmp_bb = fn->getTopBlock();
+    BasicBlock* p_tmp_bb = &tmp_bb;
+    Block* p = NULL;
+
+    if(NULL != p_tmp_bb)
+    {
+      Block *p_tmp_block = new SimpleBlock(p_tmp_bb);
+      p_tmp_block->label = p_tmp_bb->getLabelIndex();
+
+      if(checkForBarrier(p_tmp_bb))
+        p_tmp_block->hasBarrier() = true;
+
+      blocks.push_back(p_tmp_block);
+      bbmap[p_tmp_bb] = p_tmp_block;
+      bTobbmap[p_tmp_block] = p_tmp_bb;
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+      p = p_tmp_block;
+    }
+
+    while(p_tmp_bb != NULL)
+    {
+      Block *p_tmp_block = new SimpleBlock(p_tmp_bb);
+      p_tmp_block->label = p_tmp_bb->getLabelIndex();
+
+      if(checkForBarrier(p_tmp_bb))
+        p_tmp_block->hasBarrier() = true;
+
+      p->fallthrough() = p_tmp_block;
+      p = p_tmp_block;
+      blocks.push_back(p_tmp_block);
+      bbmap[p_tmp_bb] = p_tmp_block;
+      bTobbmap[p_tmp_block] = p_tmp_bb;
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+    }
+
+    if(NULL != p)
+      p->fallthrough() = NULL;
+
+    p_tmp_bb = &tmp_bb;
+
+    this->blocks_entry = bbmap[p_tmp_bb];
+
+    while(p_tmp_bb != NULL)
+    {
+      BlockSet::const_iterator iter_begin = p_tmp_bb->getPredecessorSet().begin();
+      BlockSet::const_iterator iter_end = p_tmp_bb->getPredecessorSet().end();
+      while(iter_begin != iter_end)
+      {
+        bbmap[p_tmp_bb]->predecessors().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]->successors().insert(bbmap[*iter_begin]);
+        iter_begin++;
+      }
+
+      p_tmp_bb = p_tmp_bb->getNextBlock();
+    }
+
+    loops = fn->getLoops();
+  }
+
+  void CFGStructurizer::orderBlocks(Block *start)
+  {
+    visited.insert(start);
+    BlockSets::iterator y;
+    BlockSets::iterator iter_begin = start->successors().begin();
+    BlockSets::iterator iter_end = start->successors().end();
+    orderedBlks.push_back(start);
+    for(y = iter_begin; y != iter_end; ++y )
+    {
+      if(visited.find(*y) != visited.end())
+        continue;
+      orderBlocks(*y);
+    }
+  }
+
+  void CFGStructurizer::outBlockTypes(BlockType type)
+  {
+    if(type == SerialBlockType)
+        std::cout << " T:["<< "Serial" <<"]"<< std::endl;
+    else if(type == IfThenType)
+        std::cout << " T:["<< "IfThen" <<"]"<< std::endl;
+    else if(type == IfElseType)
+        std::cout << " T:["<< "IfElse" <<"]"<< std::endl;
+    else if(type == SelfLoopType)
+        std::cout << " T:["<< "SelfLoop" <<"]"<< std::endl;
+    else
+        std::cout << " T:["<< "BasicBlock" <<"]"<< std::endl;
+  }
+
+  void CFGStructurizer::printOrderedBlocks()
+  {
+    size_t i = 0;
+    std::cout << "\n ordered Blocks ->  BasicBlocks -> Current BB: "<< *orderIter << std::endl;
+    for (auto iterBlk = orderedBlks.begin(), iterBlkEnd = orderedBlks.end(); iterBlk != iterBlkEnd; ++iterBlk, ++i) {
+      std::cout << "B:" << *iterBlk << " BB:" << bTobbmap[*iterBlk];
+      if((*iterBlk)->type() == SingleBlockType)
+        std::cout << " L:"<< bTobbmap[*iterBlk]->getLabelIndex() << std::endl;
+      else
+        outBlockTypes((*iterBlk)->type());
+    }
+  }
+
+  void CFGStructurizer::cfgUpdate(Block* mergedBB,  const BlockSets& blockBBs)
+  {
+    for(auto iter= blockBBs.begin(); iter != blockBBs.end(); iter++)
+    {
+      for(auto p = (*iter)->pred_begin(); p != (*iter)->pred_end(); p++)
+      {
+        if(blockBBs.find(*p) != blockBBs.end())
+          continue;
+
+        (*p)->successors().erase(*iter);
+        (*p)->successors().insert(mergedBB);
+        mergedBB->predecessors().insert(*p);
+
+        if((*p)->fallthrough() == *iter)
+          (*p)->fallthrough() = mergedBB;
+      }
+      for(auto s = (*iter)->succ_begin(); s != (*iter)->succ_end(); s++)
+      {
+        if(blockBBs.find(*s) != blockBBs.end())
+          continue;
+
+        (*s)->predecessors().erase(*iter);
+        (*s)->predecessors().insert(mergedBB);
+        mergedBB->successors().insert(*s);
+
+        if((*iter)->fallthrough() == *s)
+          mergedBB->fallthrough() = *s;
+      }
+    }
+
+    if(mergedBB->type() != SelfLoopType) {
+      for(auto iter= blockBBs.begin(); iter != blockBBs.end(); iter++)
+      {
+        for(auto s = (*iter)->succ_begin(); s != (*iter)->succ_end(); s++)
+        {
+          if(blockBBs.find(*s) == blockBBs.end())
+            continue;
+
+          LabelIndex l_iter = (*iter)->getEntry()->getLabelIndex();
+          LabelIndex l_succ = (*s)->getEntry()->getLabelIndex();
+          if(l_iter > l_succ)
+          {
+            mergedBB->predecessors().insert(mergedBB);
+            mergedBB->successors().insert(mergedBB);
+            return;
+          }
+        }
+      }
+    }
+  }
+
+  void CFGStructurizer::replace(Block* mergedBB,  BlockSets blockBBs)
+  {
+    lIterator iter, iterRep;
+    bool flag = false;
+    for(iter = orderedBlks.begin(); iter!= orderedBlks.end() && !blockBBs.empty();)
+    {
+      if(!blockBBs.erase(*iter))
+      {
+        iter++;
+        continue;
+      }
+      if(flag == false)
+      {
+        iter = orderedBlks.erase(iter);
+        iterRep = iter;
+        orderIter = orderedBlks.insert(iterRep, mergedBB);
+        flag = true;
+      }else
+      {
+        iter = orderedBlks.erase(iter);
+      }
+    }
+  }
+
+  Block* CFGStructurizer::mergeSerialBlock(BlockList& serialBBs)
+  {
+      Block* p = new SerialBlock(serialBBs);
+      BlockList::iterator iter = serialBBs.begin();
+      while(iter != serialBBs.end())
+      {
+        if((*iter)->canBeHandled == false)
+        {
+          p->canBeHandled = false;
+          break;
+        }
+        iter++;
+      }
+      return insertBlock(p);
+  }
+
+  BVAR(OCL_OUTPUT_STRUCTURIZE, false);
+  int CFGStructurizer::serialPatternMatch(Block *block) {
+    if (block->succ_size() != 1)
+      return 0;
+
+    if(block->hasBarrier())
+      return 0;
+
+    Block *childBlk = *block->succ_begin();
+    if (childBlk->pred_size() != 1 )
+      return 0;
+
+    BlockList serialBBs;//childBBs
+    BlockSets serialSets;
+    serialBBs.push_back(block);
+    serialBBs.push_back(childBlk);
+    serialSets.insert(block);
+    serialSets.insert(childBlk);
+
+    Block* mergedBB = mergeSerialBlock(serialBBs);
+    if(mergedBB == NULL)
+      return 0;
+
+    cfgUpdate(mergedBB, serialSets);
+    replace(mergedBB, serialSets);
+
+    if(OCL_OUTPUT_STRUCTURIZE)
+      printOrderedBlocks();
+    ++numSerialPatternMatch;
+    if(serialSets.find(blocks_entry) != serialSets.end())
+      blocks_entry = mergedBB;
+    return 1;
+  }
+
+  Block* CFGStructurizer::mergeLoopBlock(BlockList& loopSets)
+  {
+    if(loopSets.size() == 1)
+    {
+      Block* p = new SelfLoopBlock(*loopSets.begin());
+      p->canBeHandled = true;
+      (*loopSets.begin())->getExit()->isLoopExit = true;
+      return insertBlock(p);
+    }
+    return NULL;
+  }
+
+  int CFGStructurizer::loopPatternMatch(Block *block) {
+    Block* loop_header = NULL;
+    Block* b = block;
+    BlockSets loopSets;
+    BlockList loopBBs;
+
+    //if b is basic block , query the llvm loop info to find the loop whoose loop header is b;
+    if(block->type() == SingleBlockType){
+      for (auto l : loops) {
+        BasicBlock &a = fn->getBlock(l->bbs[0]);
+        loop_header = bbmap.find(&a)->second;
+
+        if(loop_header == b){
+          for (auto bb : l->bbs) {
+            BasicBlock &tmp = fn->getBlock(bb);
+            Block* block_ = bbmap.find(&tmp)->second;
+            loopBBs.push_front(block_);
+            loopSets.insert(block_);
+          }
+          break;
+        }
+      }
+    }else{
+      //b is compacted node, it would have a successor pointed to itself for self loop.
+      if(block->successors().find(b) != block->successors().end())
+      {
+        loopBBs.push_front(b);
+        loopSets.insert(b);
+      }
+    }
+
+    if(loopBBs.empty())
+      return 0;
+
+    Block* mergedBB = mergeLoopBlock(loopBBs);
+    if(mergedBB == NULL)
+      return 0;
+
+    cfgUpdate(mergedBB, loopSets);
+    replace(mergedBB, loopSets);
+
+    if(OCL_OUTPUT_STRUCTURIZE)
+      printOrderedBlocks();
+    ++numLoopPatternMatch;
+    if(loopSets.find(blocks_entry) != loopSets.end())
+      blocks_entry = mergedBB;
+    return 1;
+  }
+
+  int CFGStructurizer::ifPatternMatch(Block *block)
+  {
+    //two edges
+    if (block->succ_size() != 2)
+      return 0;
+
+    if(block->hasBarrier())
+      return 0;
+
+    int NumMatch = 0;
+    Block *TrueBB = *block->succ_begin();
+    Block *FalseBB = *(++block->succ_begin());
+    Block *mergedBB = NULL;
+    BlockSets ifSets;
+
+    assert (!TrueBB->succ_empty() || !FalseBB->succ_empty());
+    if (TrueBB->succ_size() == 1 && FalseBB->succ_size() == 1
+        && TrueBB->pred_size() == 1 && FalseBB->pred_size() == 1
+        && *TrueBB->succ_begin() == *FalseBB->succ_begin()
+        && !TrueBB->hasBarrier() && !FalseBB->hasBarrier() ) {
+      // Diamond pattern
+      ifSets.insert(block);
+      if(block->fallthrough() == TrueBB) {
+        ifSets.insert(TrueBB);
+        ifSets.insert(FalseBB);
+        mergedBB = new IfElseBlock(block, TrueBB, FalseBB);
+      }else if(block->fallthrough() == FalseBB) {
+        ifSets.insert(TrueBB);
+        ifSets.insert(FalseBB);
+        mergedBB = new IfElseBlock(block, FalseBB, TrueBB);
+      }else{
+        GBE_ASSERT(0);
+      }
+
+      if(block->canBeHandled == false || TrueBB->canBeHandled == false || FalseBB->canBeHandled == false)
+        block->canBeHandled = false;
+
+      insertBlock(mergedBB);
+    } else if (TrueBB->succ_size() == 1 && TrueBB->pred_size() == 1 &&
+        *TrueBB->succ_begin() == FalseBB && !TrueBB->hasBarrier() ) {
+      // Triangle pattern, false is empty
+      ifSets.insert(block);
+      ifSets.insert(TrueBB);
+      mergedBB = new IfThenBlock(block, TrueBB);
+      if(block->fallthrough() == FalseBB)
+        block->inversePredicate = false;
+
+      if(block->canBeHandled == false || TrueBB->canBeHandled == false)
+        block->canBeHandled = false;
+
+      insertBlock(mergedBB);
+    } else if (FalseBB->succ_size() == 1 && FalseBB->pred_size() == 1 &&
+        *FalseBB->succ_begin() == TrueBB && !FalseBB->hasBarrier() ) {
+      // Triangle pattern, true is empty
+      ifSets.insert(block);
+      ifSets.insert(FalseBB);
+      mergedBB = new IfThenBlock(block, FalseBB);
+      if(block->fallthrough() == TrueBB)
+        block->inversePredicate = false;
+
+      if(block->canBeHandled == false || FalseBB->canBeHandled == false)
+        block->canBeHandled = false;
+
+      insertBlock(mergedBB);
+    }
+    else{
+      return 0;
+    }
+
+    if(ifSets.empty())
+      return 0;
+
+    if(mergedBB == NULL)
+      return 0;
+
+    cfgUpdate(mergedBB, ifSets);
+    replace(mergedBB, ifSets);
+
+    if(OCL_OUTPUT_STRUCTURIZE)
+      printOrderedBlocks();
+    ++numIfPatternMatch;
+    if(ifSets.find(blocks_entry) != ifSets.end())
+      blocks_entry = mergedBB;
+    return NumMatch + 1;
+  }
+
+  int CFGStructurizer::patternMatch(Block *block) {
+    int NumMatch = 0;
+    NumMatch += loopPatternMatch(block);
+    NumMatch += serialPatternMatch(block);
+    NumMatch += ifPatternMatch(block);
+    return NumMatch;
+  }
+
+  void CFGStructurizer::blockPatternMatch()
+  {
+    int increased = 0;
+    do
+    {
+      orderedBlks.clear();
+      visited.clear();
+      increased = numSerialPatternMatch + numLoopPatternMatch + numIfPatternMatch;
+
+      orderBlocks(blocks_entry);
+      orderIter = orderedBlks.begin();
+
+      while(orderedBlks.size() > 1 && orderIter != orderedBlks.end())
+      {
+        if(OCL_OUTPUT_STRUCTURIZE)
+          printOrderedBlocks();
+        patternMatch(*orderIter);
+        orderIter++;
+      }
+      if(OCL_OUTPUT_STRUCTURIZE)
+        printOrderedBlocks();
+
+      if(increased == numSerialPatternMatch + numLoopPatternMatch + numIfPatternMatch)
+        break;
+
+    } while(orderedBlks.size()>1);
+    if(OCL_OUTPUT_STRUCTURIZE)
+      std::cout << "Serial:" << numSerialPatternMatch << "Loop:" << numLoopPatternMatch << "If:" << numIfPatternMatch << std::endl;
+  }
+
+  void CFGStructurizer::StructurizeBlocks()
+  {
+    initializeBlocks();
+    blockPatternMatch();
+    handleStructuredBlocks();
+    calculateNecessaryLiveout();
+  }
+} /* namespace ir */
+} /* namespace gbe */
diff --git a/backend/src/ir/structurizer.hpp b/backend/src/ir/structurizer.hpp
new file mode 100644
index 0000000..bed2271
--- /dev/null
+++ b/backend/src/ir/structurizer.hpp
@@ -0,0 +1,249 @@
+/*
+ * Copyright © 2012 Intel Corporation
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+#ifndef __STRUCTURIZER_HPP__
+#define __STRUCTURIZER_HPP__
+#include "llvm/ADT/SmallVector.h"
+#include "ir/unit.hpp"
+#include "ir/function.hpp"
+#include "ir/instruction.hpp"
+
+#include <iostream>
+#include <set>
+#include <map>
+#include <vector>
+#include <list>
+#include <algorithm>
+namespace gbe {
+namespace ir {
+  using namespace llvm;
+
+  enum BlockType
+  {
+    SingleBlockType = 0,
+    SerialBlockType,
+    IfThenType,
+    IfElseType,
+    SelfLoopType
+  };
+
+  /* Block*/
+  class Block;
+
+  typedef std::set<Block *> BlockSets;
+  typedef std::list<Block *> BlockList;
+  typedef std::vector<Block *> BlockVector;
+  typedef std::set<Block *>::iterator sIterator;
+  typedef std::list<Block *>::iterator lIterator;
+
+  class Block
+  {
+  public:
+    Block(BlockType type, const BlockList& children): has_barrier(false), mark(false), canBeHandled(true), inversePredicate(true)
+    {
+      this->btype = type;
+      this->children = children;
+    }
+    virtual ~Block() {}
+    Block*& fallthrough() { return fall_through; }
+    BlockSets& successors() { return successor; }
+    size_t succ_size() { return successor.size(); }
+    sIterator succ_begin() { return successor.begin(); }
+    sIterator succ_end() { return successor.end(); }
+    bool succ_empty() { return successor.empty(); }
+    BlockSets& predecessors() { return predecessor; }
+    size_t pred_size() { return predecessor.size(); }
+    sIterator pred_begin() { return predecessor.begin(); }
+    sIterator pred_end() { return predecessor.end(); }
+    bool& hasBarrier() { return has_barrier; }
+    BlockType type() { return btype; }
+    virtual BasicBlock* getEntry()
+    {
+      return (*(children.begin()))->getEntry();
+    }
+    virtual BasicBlock* getExit()
+    {
+      return (*(children.rbegin()))->getExit();
+    }
+
+  public:
+    BlockType btype;
+    Block* fall_through;
+    BlockSets predecessor;
+    BlockSets successor;
+    BlockList children;
+    bool has_barrier;
+    bool mark;
+    bool canBeHandled;
+    //label is for debug
+    int label;
+    /* inversePredicate should be false under two circumstance,
+     * fallthrough is the same with succs:
+     * (1) n->succs == m && block->fallthrough == m
+     * block
+     * | \
+     * |  \
+     * m<--n
+     * (2) m->succs == n && block->fallthrough == n
+     * block
+     * | \
+     * |  \
+     * m-->n
+     * */
+    bool inversePredicate;
+  };
+
+  /* represents basic block */
+  class SimpleBlock: public Block
+  {
+  public:
+    SimpleBlock(BasicBlock *p_bb) : Block(SingleBlockType, BlockList()) { this->p_bb = p_bb; }
+    virtual ~SimpleBlock() {}
+    BasicBlock* getBasicBlock() { return p_bb; }
+    virtual BasicBlock* getEntry() { return p_bb; }
+    virtual BasicBlock* getExit() { return p_bb; }
+    virtual BasicBlock* getFirstBB() { return p_bb; }
+  private:
+    BasicBlock *p_bb;
+  };
+
+  /* a serial of Blocks*/
+  class SerialBlock : public Block
+  {
+  public:
+    SerialBlock(BlockList& children) : Block(SerialBlockType, children) {}
+    virtual ~SerialBlock(){}
+  };
+
+  /* If-Then Block*/
+  class IfThenBlock : public Block
+  {
+  public:
+    IfThenBlock(Block* pred, Block* trueBlock) : Block(IfThenType, InitChildren(pred, trueBlock)) {}
+    virtual ~IfThenBlock() {}
+
+  private:
+    const BlockList InitChildren(Block* pred, Block* trueBlock)
+    {
+      BlockList children;
+      children.push_back(pred);
+      children.push_back(trueBlock);
+      return children;
+    }
+  };
+
+  /* If-Else Block*/
+  class IfElseBlock: public Block
+  {
+  public:
+    IfElseBlock(Block* pred, Block* trueBlock, Block* falseBlock) : Block(IfElseType, InitChildren(pred, trueBlock, falseBlock)) {}
+    virtual ~IfElseBlock() {}
+
+  private:
+    const BlockList InitChildren(Block* pred, Block* trueBlock, Block* falseBlock)
+    {
+      BlockList children;
+      children.push_back(pred);
+      children.push_back(trueBlock);
+      children.push_back(falseBlock);
+      return children;
+    }
+  };
+
+  /* Self loop Block*/
+  class SelfLoopBlock: public Block
+  {
+  public:
+    SelfLoopBlock(Block* block) : Block(SelfLoopType, InitChildren(block)) {}
+    virtual ~SelfLoopBlock() {}
+    virtual BasicBlock* getEntry()
+    {
+      return (*(children.begin()))->getEntry();
+    }
+    virtual BasicBlock* getExit()
+    {
+      return (*(children.begin()))->getExit();
+    }
+
+  private:
+    const BlockList InitChildren(Block * block)
+    {
+      BlockList children;
+      children.push_back(block);
+      return children;
+    }
+  };
+
+  class CFGStructurizer{
+    public:
+      CFGStructurizer(Function* fn) { this->fn = fn; numSerialPatternMatch = 0; numLoopPatternMatch = 0; numIfPatternMatch = 0;}
+      ~CFGStructurizer();
+
+      void StructurizeBlocks();
+
+    private:
+      int  numSerialPatternMatch;
+      int  numLoopPatternMatch;
+      int  numIfPatternMatch;
+
+      void outBlockTypes(BlockType type);
+      void printOrderedBlocks();
+      void blockPatternMatch();
+      void orderBlocks(Block *start);
+      int  serialPatternMatch(Block *block);
+      Block* mergeSerialBlock(BlockList& serialBB);
+      void cfgUpdate(Block* mergedBB,  const BlockSets& blockBBs);
+      void replace(Block* mergedBB,  BlockSets serialSets);
+      int  loopPatternMatch(Block *block);
+      Block* mergeLoopBlock(BlockList& loopSets);
+      int  ifPatternMatch(Block *block);
+      int  patternMatch(Block *block);
+
+    private:
+      void handleSelfLoopBlock(Block *loopblock, LabelIndex& whileLabel);
+      void markNeedIf(Block *block, bool status);
+      void markNeedEndif(Block *block, bool status);
+      void markStructuredBlocks(Block *block, bool status);
+      void handleIfBlock(Block *block, LabelIndex& matchingEndifLabel, LabelIndex& matchingElseLabel);
+      void handleThenBlock(Block * block, LabelIndex& endiflabel);
+      void handleThenBlock2(Block *block, Block *elseblock, LabelIndex elseBBLabel);
+      void handleElseBlock(Block * block, LabelIndex& elselabel, LabelIndex& endiflabel);
+      void handleStructuredBlocks();
+      void getStructureSequence(Block *block, std::vector<BasicBlock*> &seq);
+      std::set<int> getStructureBasicBlocksIndex(Block* block, std::vector<BasicBlock *> &bbs);
+      std::set<BasicBlock *> getStructureBasicBlocks(Block *block);
+      Block* insertBlock(Block *p_block);
+      bool checkForBarrier(const BasicBlock* bb);
+      void getLiveIn(BasicBlock& bb, std::set<Register>& livein);
+      void initializeBlocks();
+      void calculateNecessaryLiveout();
+
+    private:
+      Function *fn;
+      std::map<BasicBlock *, Block *> bbmap;
+      std::map<Block *, BasicBlock *> bTobbmap;
+      BlockVector blocks;
+      Block* blocks_entry;
+      gbe::vector<Loop *> loops;
+      BlockList orderedBlks;
+      BlockList::iterator orderIter;
+      BlockSets visited;
+  };
+} /* namespace ir */
+} /* namespace gbe */
+
+#endif
diff --git a/backend/src/llvm/llvm_to_gen.cpp b/backend/src/llvm/llvm_to_gen.cpp
index f16bf0f..e0f6bf2 100644
--- a/backend/src/llvm/llvm_to_gen.cpp
+++ b/backend/src/llvm/llvm_to_gen.cpp
@@ -61,6 +61,8 @@
 #include "sys/cvar.hpp"
 #include "sys/platform.hpp"
 #include "ir/unit.hpp"
+#include "ir/function.hpp"
+#include "ir/structurizer.hpp"
 
 #include <clang/CodeGen/CodeGenAction.h>
 
@@ -308,6 +310,19 @@ namespace gbe
     // Print the code extra optimization passes
     OUTPUT_BITCODE(AFTER_GEN, mod);
 
+    const ir::Unit::FunctionSet& fs = unit.getFunctionSet();
+    ir::Unit::FunctionSet::const_iterator iter = fs.begin();
+    while(iter != fs.end())
+    {
+      ir::CFGStructurizer *structurizer = new ir::CFGStructurizer(iter->second);
+      structurizer->StructurizeBlocks();
+      delete structurizer;
+      if (OCL_OUTPUT_CFG_GEN_IR)
+        iter->second->outputCFG();
+      iter++;
+    }
+
+
     delete libraryInfo;
     return true;
   }
-- 
1.9.1



More information about the Beignet mailing list