Uses gen asm instruction IF and ENDIF implement the structures which have been identified by structural analysis. Since this is experimental, so I made this invalid by default through macros, so if want to try this, you should add '#define TRANSFORM_UNSTRUCTURE' in file "structural_analysis.hpp".
Signed-off-by: Yongjia Zhang <[email protected]> --- backend/src/backend/gen_insn_selection.cpp | 82 ++++++++++++-- backend/src/ir/function.cpp | 2 +- backend/src/ir/function.hpp | 7 ++ backend/src/ir/structural_analysis.cpp | 171 ++++++++++++++++++++++++++++- backend/src/ir/structural_analysis.hpp | 12 +- 5 files changed, 262 insertions(+), 12 deletions(-) diff --git a/backend/src/backend/gen_insn_selection.cpp b/backend/src/backend/gen_insn_selection.cpp index 88ec408..a9f82d7 100644 --- a/backend/src/backend/gen_insn_selection.cpp +++ b/backend/src/backend/gen_insn_selection.cpp @@ -102,6 +102,7 @@ #include "ir/profile.hpp" #include "sys/cvar.hpp" #include "sys/vector.hpp" +#include "ir/structural_analysis.hpp" #include <algorithm> namespace gbe @@ -507,7 +508,7 @@ namespace gbe /*! IF indexed instruction */ void IF(Reg src, ir::LabelIndex jip, ir::LabelIndex uip); /*! ENDIF indexed instruction */ - void ENDIF(Reg src, ir::LabelIndex jip); + void ENDIF(Reg src, ir::LabelIndex jip, ir::LabelIndex endifLabel = ir::LabelIndex(0)); /*! BRD indexed instruction */ void BRD(Reg src, ir::LabelIndex jip); /*! BRC indexed instruction */ @@ -976,8 +977,11 @@ namespace gbe insn->index1 = uint16_t(uip); } - void Selection::Opaque::ENDIF(Reg src, ir::LabelIndex jip) { - this->block->endifLabel = this->newAuxLabel(); + void Selection::Opaque::ENDIF(Reg src, ir::LabelIndex jip, ir::LabelIndex endifLabel) { + if(endifLabel == 0) + this->block->endifLabel = this->newAuxLabel(); + else + this->block->endifLabel = endifLabel; this->LABEL(this->block->endifLabel); SelectionInstruction *insn = this->appendInsn(SEL_OP_ENDIF, 0, 1); insn->src(0) = src; @@ -1504,13 +1508,31 @@ namespace gbe this->block->isLargeBlock = true; } +#ifdef TRANSFORM_UNSTRUCTURE + const ir::BasicBlock *bb = insn.getParent(); + + needEndif = needEndif && bb->needEndif; if (needEndif) { + if(!bb->needIf) { + this->ENDIF(GenRegister::immd(0), bb->endifLabel, bb->endifLabel); + needEndif = false; + } + else { + const ir::BasicBlock *curr = insn.getParent(); + const ir::BasicBlock *next = curr->getNextBlock(); + this->ENDIF(GenRegister::immd(0), next->getLabelIndex()); + needEndif = false; + } + } +#endif +#ifndef TRANSFORM_UNSTRUCTURE + if(needEndif) { const ir::BasicBlock *curr = insn.getParent(); const ir::BasicBlock *next = curr->getNextBlock(); this->ENDIF(GenRegister::immd(0), next->getLabelIndex()); needEndif = false; } - +#endif // Output the code in the current basic block this->endBackwardGeneration(); } @@ -3174,6 +3196,11 @@ namespace gbe GBE_ASSERTM(label < GEN_MAX_LABEL, "We reached the maximum label number which is reserved for barrier handling"); sel.LABEL(label); +#ifdef TRANSFORM_UNSTRUCTURE + if(!insn.getParent()->needIf) + return true; +#endif + // Do not emit any code for the "returning" block. There is no need for it if (insn.getParent() == &sel.ctx.getFunction().getBottomBlock()) return true; @@ -3242,7 +3269,14 @@ namespace gbe } sel.push(); sel.curr.predicate = GEN_PREDICATE_NORMAL; - sel.IF(GenRegister::immd(0), sel.block->endifLabel, sel.block->endifLabel); +#ifdef TRANSFORM_UNSTRUCTURE + if(!insn.getParent()->needEndif && insn.getParent()->needIf) { + ir::LabelIndex label = insn.getParent()->endifLabel; + sel.IF(GenRegister::immd(0), label, label); + } + else +#endif + sel.IF(GenRegister::immd(0), sel.block->endifLabel, sel.block->endifLabel); sel.pop(); } @@ -3435,8 +3469,14 @@ namespace gbe // Update the PcIPs const LabelIndex jip = sel.ctx.getLabelIndex(&insn); sel.MOV(ip, GenRegister::immuw(uint16_t(dst))); - if (!sel.block->hasBarrier) - sel.ENDIF(GenRegister::immd(0), nextLabel); + if (!sel.block->hasBarrier) { +#ifdef TRANSFORM_UNSTRUCTURE + if(insn.getParent()->needEndif && !insn.getParent()->needIf) + sel.ENDIF(GenRegister::immd(0), insn.getParent()->endifLabel, insn.getParent()->endifLabel); + else +#endif + sel.ENDIF(GenRegister::immd(0), nextLabel); + } sel.block->endifOffset = -1; if (nextLabel == jip) return; // Branch to the jump target @@ -3494,8 +3534,14 @@ namespace gbe // Update the PcIPs sel.MOV(ip, GenRegister::immuw(uint16_t(dst))); sel.block->endifOffset = -1; - if (!sel.block->hasBarrier) - sel.ENDIF(GenRegister::immd(0), next); + if (!sel.block->hasBarrier) { +#ifdef TRANSFORM_UNSTRUCTURE + if(insn.getParent()->needEndif && !insn.getParent()->needIf) + sel.ENDIF(GenRegister::immd(0), insn.getParent()->endifLabel, insn.getParent()->endifLabel); + else +#endif + sel.ENDIF(GenRegister::immd(0), next); + } // Branch to the jump target sel.push(); sel.curr.execWidth = 1; @@ -3528,6 +3574,24 @@ namespace gbe else this->emitForwardBranch(sel, insn, dst, src); sel.pop(); + } + else if(opcode == OP_IF) { + const Register pred = insn.getPredicateIndex(); + const LabelIndex jip = insn.getLabelIndex(); + sel.push(); + sel.curr.physicalFlag = 0; + sel.curr.flagIndex = (uint64_t)pred; + sel.curr.inversePredicate = 1; + sel.curr.predicate = GEN_PREDICATE_NORMAL; + sel.IF(GenRegister::immd(0), jip, jip); + sel.curr.inversePredicate = 0; + sel.pop(); + } else if(opcode == OP_ENDIF) { + const LabelIndex label = insn.getLabelIndex(); + sel.push(); + sel.curr.predicate = GEN_PREDICATE_NONE; + sel.ENDIF(GenRegister::immd(0), label, label); + sel.pop(); } else NOT_IMPLEMENTED; diff --git a/backend/src/ir/function.cpp b/backend/src/ir/function.cpp index 83936ad..217cdb1 100644 --- a/backend/src/ir/function.cpp +++ b/backend/src/ir/function.cpp @@ -309,7 +309,7 @@ namespace ir { // Basic Block /////////////////////////////////////////////////////////////////////////// - BasicBlock::BasicBlock(Function &fn) : fn(fn) { + BasicBlock::BasicBlock(Function &fn) : fn(fn), needEndif(true), needIf(true) { this->nextBlock = this->prevBlock = NULL; } diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp index 2c60f4d..5b66637 100644 --- a/backend/src/ir/function.hpp +++ b/backend/src/ir/function.hpp @@ -82,6 +82,13 @@ namespace ir { } } set <Register> undefPhiRegs; + + /* these three are used by structure transforming */ + public: + bool needEndif; + bool needIf; + LabelIndex endifLabel; + private: friend class Function; //!< Owns the basic blocks BlockSet predecessors; //!< Incoming blocks diff --git a/backend/src/ir/structural_analysis.cpp b/backend/src/ir/structural_analysis.cpp index fad77b3..d092dda 100644 --- a/backend/src/ir/structural_analysis.cpp +++ b/backend/src/ir/structural_analysis.cpp @@ -15,6 +15,143 @@ namespace analysis } + 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++; + } + } + + + 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++; + } + } + + + void ControlTree::markStructuredNodes(Node *node) + { + node->mark = true; + NodeList::iterator it = node->children.begin(); + while(it != node->children.end()) + { + markStructuredNodes(*it); + it++; + } + } + + + void ControlTree::handleIfNode(Node *node, ir::LabelIndex& endiflabel) + { + 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--; + pbb->erase(it); + ir::Instruction insn = ir::IF(endiflabel, reg); + ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn); + pbb->append(*p_new_insn); + } + + + 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(); + /* use a label to mark the position of ENDIF */ + endiflabel = fn->newLabel(); + + ir::Instruction insn = ir::ENDIF(endiflabel); + ir::Instruction* p_new_insn = pbb->getParent().newInstruction(insn); + 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::handleStructuredNodes() + { + NodeVector::iterator it; + NodeVector::iterator end = nodes.end(); + NodeVector::iterator begin = nodes.begin(); + it = end; + it--; + + while(it != begin) + { + /* now only consider IfThen */ + if((*it)->type() == IfThen) + { + if(false == (*it)->mark && (*it)->canBeHandled) + { + markStructuredNodes(*it); + markNeedEndif(*it, false); + markNeedIf(*it, false); + markNeedIf(*((*it)->children.begin()), true); + markNeedEndif(*((*it)->children.begin()), true); + ir::BasicBlock* entry = (*it)->getEntry(); + ir::BasicBlock* eexit = (*it)->getExit(); + entry->needEndif = false; + eexit->needEndif = true; + entry->endifLabel = fn->newLabel(); + eexit->endifLabel = entry->endifLabel; + } + } + it--; + } + + 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); + child_iter--; + handleIfNode(*child_iter, endiflabel); + break; + } + } + it++; + } + } + + Node* ControlTree::insertNode(Node *p_node) { nodes.push_back(p_node); @@ -203,6 +340,18 @@ namespace analysis if(nodes.size() >=2 ) { Node* p = new BlockNode(nodes); + + NodeList::const_iterator iter = nodes.begin(); + while(iter != nodes.end()) + { + if((*iter)->canBeHandled == false) + { + p->canBeHandled = false; + break; + } + iter++; + } + return insertNode(p); } @@ -223,6 +372,10 @@ namespace analysis nset.insert(n); Node* p = new IfThenNode(node, n); + + if(node->canBeHandled == false || n->canBeHandled == false) + p->canBeHandled = false; + return insertNode(p); } @@ -237,6 +390,10 @@ namespace analysis nset.insert(m); Node* p = new IfThenNode(node, m); + + if(node->canBeHandled == false || m->canBeHandled == false) + p->canBeHandled = false; + return insertNode(p); } @@ -252,6 +409,9 @@ namespace analysis nset.insert(m); Node* p = new IfElseNode(node, n, m); + + p->canBeHandled = false; + return insertNode(p); } @@ -267,6 +427,9 @@ namespace analysis nset.insert(n); Node* p = new IfElseNode(node, m, n); + + p->canBeHandled = false; + return insertNode(p); } } @@ -304,6 +467,9 @@ namespace analysis if(node->succs().find(node) != node->succs().end()) { Node* p = new SelfLoopNode(node); + + p->canBeHandled = false; + return insertNode(p); } else @@ -328,6 +494,9 @@ namespace analysis node->preds().size() == 2 && (*m)->preds().size() == 1) { Node* p = new WhileLoopNode(node, *m); + + p->canBeHandled = false; + return insertNode(p); } } @@ -490,12 +659,12 @@ namespace analysis } } while(post_order.size()>1); - } void ControlTree::analyze() { initializeNodes(); structuralAnalysis(nodes_entry); + handleStructuredNodes(); } } diff --git a/backend/src/ir/structural_analysis.hpp b/backend/src/ir/structural_analysis.hpp index c23d0d5..005eac5 100644 --- a/backend/src/ir/structural_analysis.hpp +++ b/backend/src/ir/structural_analysis.hpp @@ -13,6 +13,8 @@ #include <list> #include <algorithm> +//#define TRANSFORM_UNSTRUCTURE + namespace analysis { using namespace std; @@ -40,7 +42,7 @@ namespace analysis class Node { public: - Node(RegionType rtype, const NodeList& children): has_barrier(false) + Node(RegionType rtype, const NodeList& children): has_barrier(false), mark(false), canBeHandled(true) { this->rtype = rtype; this->children = children; @@ -61,6 +63,8 @@ namespace analysis NodeList children; Node* fall_through; bool has_barrier; + bool mark; + bool canBeHandled; }; /* represents basic block */ @@ -265,6 +269,12 @@ namespace analysis bool isBackedge(const Node*, const Node*); bool pathBack(Node*, Node*); bool checkForBarrier(const ir::BasicBlock*); + void markStructuredNodes(Node *); + void markNeedEndif(Node *, bool); + void markNeedIf(Node *, bool); + void handleIfNode(Node *, ir::LabelIndex&); + void handleThenNode(Node *, ir::LabelIndex&); + void handleStructuredNodes(); private: NodeVector nodes; -- 1.8.3.2 _______________________________________________ Beignet mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/beignet
