From fc57a012f70d36608fcdccaed44df1f7d76e006d Mon Sep 17 00:00:00 2001 From: Yongjia Zhang Date: Fri, 18 Jul 2014 02:14:40 +0800 Subject: [PATCH] Use instruction if else and endif manipulate structures Use instruction if, else and endif manipulate the control flow of identified if-then and if-else structures at backend. but this is not enabled, just add the necessary code to backend. Signed-off-by: Yongjia Zhang Reviewed-by: Zhigang Gong --- backend/src/backend/context.cpp | 113 ++++++++++++++++++++++++----- backend/src/backend/context.hpp | 1 + backend/src/backend/gen_context.cpp | 13 +++- backend/src/backend/gen_insn_selection.cpp | 75 ++++++++++++++++--- backend/src/ir/liveness.cpp | 2 + 5 files changed, 172 insertions(+), 32 deletions(-) diff --git a/backend/src/backend/context.cpp b/backend/src/backend/context.cpp index 2f868d1..831421d 100644 --- a/backend/src/backend/context.cpp +++ b/backend/src/backend/context.cpp @@ -488,42 +488,110 @@ namespace gbe }); } + /* Because of the structural analysis, control flow of blocks inside a structure + * is manipulated by if, else and endif. so these blocks don't need jips. so here + * treats all the blocks belong to the same structure as a whole. + */ void Context::buildJIPs(void) { using namespace ir; - // Linearly store the branch target for each block and its own label const LabelIndex noTarget(fn.labelNum()); vector> braTargets; - int32_t curr = 0, blockNum = fn.blockNum(); - braTargets.resize(blockNum); - + int32_t curr = 0; // If some blocks are unused we mark them as such by setting their own label // as "invalid" (== noTarget) + int blockCount = 0; + // because some blocks maybe belong to the same structure, so the number of + // blocks we are dealing with may be less than the number of basic blocks. + // here calculate the actual block number we would handle. + fn.foreachBlock([&](const BasicBlock &bb) + { + if(bb.belongToStructure && bb.isStructureExit) + blockCount++; + else if(!bb.belongToStructure) + blockCount++; + }); + braTargets.resize(blockCount); + + LabelIndex structureExitLabel; + LabelIndex structureEntryLabel; + bool flag; + set pos; + map exitMap; + map entryMap; for (auto &bb : braTargets) bb = std::make_pair(noTarget, noTarget); fn.foreachBlock([&](const BasicBlock &bb) { - const LabelIndex ownLabel = bb.getLabelIndex(); - const Instruction *last = bb.getLastInstruction(); - if (last->getOpcode() != OP_BRA) - braTargets[curr++] = std::make_pair(ownLabel, noTarget); - else { - const BranchInstruction *bra = cast(last); - braTargets[curr++] = std::make_pair(ownLabel, bra->getLabelIndex()); + LabelIndex ownLabel; + Instruction *last; + flag = false; + // bb belongs to a structure and it's not the structure's exit, just simply insert + // the target of bra to JIPs. + if(bb.belongToStructure && !bb.isStructureExit) + { + last = bb.getLastInstruction(); + if(last->getOpcode() == OP_BRA) + { + BranchInstruction *bra = cast(last); + JIPs.insert(std::make_pair(bra, bra->getLabelIndex())); + } + return; } - }); + else + { + // bb belongs to a structure and it's the strucutre's exit, we treat this bb + // as the structure it belongs to, use the label of structure's entry as this + // structure's label and last instruction of structure's exit as this structure's + // last instruction. + if(bb.belongToStructure && bb.isStructureExit) + { + ownLabel = (bb.matchingStructureEntry)->getLabelIndex(); + last = bb.getLastInstruction(); + structureExitLabel = bb.getLabelIndex(); + structureEntryLabel = ownLabel; + flag = true; + } + // bb belongs to no structure. + else + { + ownLabel = bb.getLabelIndex(); + last = bb.getLastInstruction(); + } + if (last->getOpcode() != OP_BRA) + { + braTargets[curr++] = std::make_pair(ownLabel, noTarget); + if(flag) + { + pos.insert(curr-1); + exitMap[curr-1] = structureExitLabel; + entryMap[curr-1] = structureEntryLabel; + } + } + else { + const BranchInstruction *bra = cast(last); + braTargets[curr++] = std::make_pair(ownLabel, bra->getLabelIndex()); + if(flag) + { + exitMap[curr-1] = structureExitLabel; + entryMap[curr-1] = structureEntryLabel; + pos.insert(curr-1); + } + } + } + }); // Backward jumps are special. We must insert the label of the next block // when we hit the "DO" i.e. the target label of the backward branch (as in // do { } while) . So, we store the bwd jumps per targets // XXX does not use custom allocator std::multimap bwdTargets; - for (int32_t blockID = 0; blockID < blockNum; ++blockID) { + for (int32_t blockID = 0; blockID fwdTargets; - // Now retraverse the blocks and figure out all JIPs - for (int32_t blockID = 0; blockID < blockNum; ++blockID) { + for (int32_t blockID = 0; blockID patchJMPI(insnID, (((uip - insnID)) << 16) | ((jip - insnID))); + p->patchJMPI(insnID, ((uip - insnID) << 16) | (0x0000ffff & (jip - insnID))); } return true; } @@ -241,6 +241,17 @@ namespace gbe p->IF(src); } break; + case SEL_OP_ELSE: + { + insertJumpPos(insn); + /* + const ir::LabelIndex label(insn.index), label1(insn.index); + const LabelPair labelPair(label, label1); + const GenRegister src = ra->genReg(insn.src(0)); + this->branchPos3.push_back(std::make_pair(labelPair, p->store.size()));*/ + p->ELSE(src); + } + break; default: NOT_IMPLEMENTED; } } diff --git a/backend/src/backend/gen_insn_selection.cpp b/backend/src/backend/gen_insn_selection.cpp index 7022d3b..2a2476e 100644 --- a/backend/src/backend/gen_insn_selection.cpp +++ b/backend/src/backend/gen_insn_selection.cpp @@ -1547,10 +1547,15 @@ namespace gbe { // Bottom up code generation bool needEndif = this->block->hasBranch == false && !this->block->hasBarrier; - - if(needEndif) { - const ir::BasicBlock *next = bb.getNextBlock(); - this->ENDIF(GenRegister::immd(0), next->getLabelIndex()); + needEndif = needEndif && bb.needEndif; + if (needEndif) { + if(!bb.needIf) // this basic block is the exit of a structure + this->ENDIF(GenRegister::immd(0), bb.endifLabel, bb.endifLabel); + else { + const ir::BasicBlock *next = bb.getNextBlock(); + this->ENDIF(GenRegister::immd(0), next->getLabelIndex()); + needEndif = false; + } } for (int32_t insnID = insnNum-1; insnID >= 0; --insnID) { @@ -1588,7 +1593,6 @@ namespace gbe this->pop(); this->block->isLargeBlock = true; } - // Output the code in the current basic block this->endBackwardGeneration(); } @@ -3500,6 +3504,9 @@ namespace gbe GBE_ASSERTM(label < GEN_MAX_LABEL, "We reached the maximum label number which is reserved for barrier handling"); sel.LABEL(label); + if(!insn.getParent()->needIf) + return true; + // Do not emit any code for the "returning" block. There is no need for it if (insn.getParent() == &sel.ctx.getFunction().getBottomBlock()) return true; @@ -3570,7 +3577,12 @@ namespace gbe } sel.push(); sel.curr.predicate = GEN_PREDICATE_NORMAL; - sel.IF(GenRegister::immd(0), sel.block->endifLabel, sel.block->endifLabel); + if(!insn.getParent()->needEndif && insn.getParent()->needIf) { + ir::LabelIndex label = insn.getParent()->endifLabel; + sel.IF(GenRegister::immd(0), label, label); + } + else + sel.IF(GenRegister::immd(0), sel.block->endifLabel, sel.block->endifLabel); sel.pop(); } @@ -3776,9 +3788,15 @@ namespace gbe } else { // 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(insn.getParent()->needEndif) + sel.MOV(ip, GenRegister::immuw(uint16_t(dst))); + + if (!sel.block->hasBarrier) { + if(insn.getParent()->needEndif && !insn.getParent()->needIf) + sel.ENDIF(GenRegister::immd(0), insn.getParent()->endifLabel, insn.getParent()->endifLabel); + else if(insn.getParent()->needEndif) + sel.ENDIF(GenRegister::immd(0), nextLabel); + } sel.block->endifOffset = -1; if (nextLabel == jip) return; // Branch to the jump target @@ -3834,10 +3852,15 @@ namespace gbe } else { const LabelIndex next = bb.getNextBlock()->getLabelIndex(); // Update the PcIPs - sel.MOV(ip, GenRegister::immuw(uint16_t(dst))); + if(insn.getParent()->needEndif) + 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) { + if(insn.getParent()->needEndif && !insn.getParent()->needIf) + sel.ENDIF(GenRegister::immd(0), insn.getParent()->endifLabel, insn.getParent()->endifLabel); + else if(insn.getParent()->needEndif) + sel.ENDIF(GenRegister::immd(0), next); + } // Branch to the jump target sel.push(); sel.curr.execWidth = 1; @@ -3870,6 +3893,34 @@ 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(); + LabelIndex uip; + if(insn.getParent()->matchingEndifLabel != 0) + uip = insn.getParent()->matchingEndifLabel; + else + uip = jip; + sel.push(); + sel.curr.physicalFlag = 0; + sel.curr.flagIndex = (uint64_t)pred; + sel.curr.externFlag = 1; + sel.curr.inversePredicate = 1; + sel.curr.predicate = GEN_PREDICATE_NORMAL; + sel.IF(GenRegister::immd(0), jip, uip); + sel.curr.inversePredicate = 0; + sel.pop(); + } else if(opcode == OP_ENDIF) { + const LabelIndex label = insn.getLabelIndex(); + sel.push(); + sel.curr.noMask = 1; + sel.curr.predicate = GEN_PREDICATE_NONE; + sel.ENDIF(GenRegister::immd(0), label, label); + sel.pop(); + } else if(opcode == OP_ELSE) { + const LabelIndex label = insn.getLabelIndex(); + sel.ELSE(GenRegister::immd(0), label, insn.getParent()->thisElseLabel); } else NOT_IMPLEMENTED; diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp index afed476..2a0aa54 100644 --- a/backend/src/ir/liveness.cpp +++ b/backend/src/ir/liveness.cpp @@ -97,6 +97,8 @@ namespace ir { this->initInstruction(*info, insn); }); liveness[&bb] = info; + if(!bb.liveout.empty()) + info->liveOut.insert(bb.liveout.begin(), bb.liveout.end()); } void Liveness::initInstruction(BlockInfo &info, const Instruction &insn) { -- 2.7.4