Pushed.
> -----Original Message----- > From: Beignet [mailto:beignet-boun...@lists.freedesktop.org] On Behalf Of > Zhigang Gong > Sent: Monday, June 15, 2015 10:18 > To: Luo, Xionghu > Cc: beignet@lists.freedesktop.org > Subject: Re: [Beignet] [PATCH v2] reimplement structurize algorithm. > > LGTM, thanks. > > On Mon, Jun 08, 2015 at 03:19:47PM +0800, xionghu....@intel.com wrote: > > From: Luo Xionghu <xionghu....@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....@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@lists.freedesktop.org > > http://lists.freedesktop.org/mailman/listinfo/beignet > _______________________________________________ > Beignet mailing list > Beignet@lists.freedesktop.org > http://lists.freedesktop.org/mailman/listinfo/beignet _______________________________________________ Beignet mailing list Beignet@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/beignet
