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