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