[Beignet] [PATCH v2] reimplement structurize algorithm.
Zhigang Gong
zhigang.gong at linux.intel.com
Sun Jun 14 19:17:46 PDT 2015
LGTM, thanks.
On Mon, Jun 08, 2015 at 03:19:47PM +0800, xionghu.luo at intel.com wrote:
> From: Luo Xionghu <xionghu.luo at intel.com>
>
> serial, loop and if pattern match from top to down.
>
> v2: remove recursive sort since the blocks are in order already, just
> copy it from Function;
> add comments to explain the pattern match process.
>
> Signed-off-by: Luo Xionghu <xionghu.luo at intel.com>
> ---
> backend/src/CMakeLists.txt | 2 +
> backend/src/ir/structurizer.cpp | 987 +++++++++++++++++++++++++++++++++++++++
> backend/src/ir/structurizer.hpp | 247 ++++++++++
> backend/src/llvm/llvm_to_gen.cpp | 15 +
> 4 files changed, 1251 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..cb8e11b
> --- /dev/null
> +++ b/backend/src/ir/structurizer.cpp
> @@ -0,0 +1,987 @@
> +/*
> + * 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();
> + }
> +
> + //copy the sequenced blocks to orderedBlks.
> + loops = fn->getLoops();
> + fn->foreachBlock([&](ir::BasicBlock &bb){
> + orderedBlks.push_back(bbmap[&bb]);
> + });
> + }
> +
> + 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;
> + }
> +
> + /* dump the block info for debug use, only SingleBlockType has label.*/
> + 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());
> + }
> + }
> +
> + /* transfer the predecessors and successors from the matched blocks to new mergedBB.
> + * if the blocks contains backage, should add a successor to itself to make a self loop.*/
> + 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;
> + }
> + }
> + }
> + }
> + }
> +
> + /* delete the matched blocks and replace it with mergedBB to reduce the CFG.
> + * the mergedBB should be inserted to the entry block position. */
> + 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);
> +
> + /* if the block has only one successor, and it's successor has only one predecessor
> + * and one successor. the block and the childBlk could be merged to a serial Block.*/
> + 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;
> + }
> +
> + /*match the selfLoop pattern with llvm info or check whether the compacted node has a backage to itself.*/
> + 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;
> + }
> +
> + /* match the if pattern(E: entry block; T: True block; F: False block; C: Converged block):
> + * for if-else pattern:
> + ** E
> + ** / \
> + ** T F
> + ** \ /
> + ** C
> + ** E has two edges T and F, T and F both have only one predecessor and one successor indepedently,
> + ** the successor of T and F must be the same. E's fallthrough need be treated as True edge.
> + *
> + * for if-then pattern E-T-C:
> + ** E
> + ** / |
> + ** T |
> + ** \ |
> + ** C
> + ** E has two edges T and C, T should have only one predecessor and one successor, the successor
> + ** of T must be C. if E's fallthrough is C, need inverse the predicate.
> + *
> + * for if-then pattern E-F-C:
> + ** E
> + ** | \
> + ** | F
> + ** | /
> + ** C
> + ** E has two edges C and F, F should have only one predecessor and one successor, the successor
> + ** of F must be C. if E's fallthrough is C, need inverse the predicate.
> + */
> + 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() ) {
> + // if-else 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(FalseBB);
> + ifSets.insert(TrueBB);
> + 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() ) {
> + // if-then 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() ) {
> + // if-then 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;
> + }
> +
> + /* match loop pattern, serail pattern, if pattern accordingly, update and replace block the CFG internally once matched. */
> + 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
> + {
> + increased = numSerialPatternMatch + numLoopPatternMatch + numIfPatternMatch;
> +
> + 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..8207644
> --- /dev/null
> +++ b/backend/src/ir/structurizer.hpp
> @@ -0,0 +1,247 @@
> +/*
> + * 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();
> + 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;
> + };
> +} /* 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
>
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet
More information about the Beignet
mailing list