[Beignet] [PATCH V2 4/5] Use instruction if else and endif manipulate structures
Yongjia Zhang
zhang_yong_jia at 126.com
Thu Jul 17 11:14:40 PDT 2014
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 <yongjia.zhang at intel.com>
---
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<std::pair<LabelIndex, LabelIndex>> 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<uint32_t> pos;
+ map<uint32_t, LabelIndex> exitMap;
+ map<uint32_t, LabelIndex> 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<BranchInstruction>(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<BranchInstruction>(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<BranchInstruction>(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<LabelIndex, LabelIndex> bwdTargets;
- for (int32_t blockID = 0; blockID < blockNum; ++blockID) {
+ for (int32_t blockID = 0; blockID <curr; ++blockID) {
const LabelIndex ownLabel = braTargets[blockID].first;
const LabelIndex target = braTargets[blockID].second;
if (ownLabel == noTarget) continue; // unused block
if (target == noTarget) continue; // no branch
if (target <= ownLabel) { // This is a backward jump
// Last block is just "RET". So, it cannot be the last block
- GBE_ASSERT(blockID < blockNum - 1);
+ GBE_ASSERT(blockID < curr - 1);
const LabelIndex fallThrough = braTargets[blockID+1].first;
bwdTargets.insert(std::make_pair(target, fallThrough));
}
@@ -531,15 +599,21 @@ namespace gbe
// Stores the current forward targets
set<LabelIndex> fwdTargets;
-
// Now retraverse the blocks and figure out all JIPs
- for (int32_t blockID = 0; blockID < blockNum; ++blockID) {
+ for (int32_t blockID = 0; blockID <curr; ++blockID) {
+
const LabelIndex ownLabel = braTargets[blockID].first;
const LabelIndex target = braTargets[blockID].second;
- const BasicBlock &bb = fn.getBlock(ownLabel);
- const Instruction *label = bb.getFirstInstruction();
+ LabelIndex tmp;
+ if(pos.find(blockID)!=pos.end())
+ tmp = exitMap[blockID];
+ else
+ tmp = ownLabel;
+ BasicBlock &bb = fn.getBlock(tmp);
+ Instruction *label = bb.getFirstInstruction();
+ if(pos.find(blockID)!=pos.end())
+ label = fn.getBlock(entryMap[blockID]).getFirstInstruction();
const Instruction *bra = bb.getLastInstruction();
-
// Expires the branches that point to us (if any)
auto it = fwdTargets.find(ownLabel);
if (it != fwdTargets.end()) fwdTargets.erase(it);
@@ -569,6 +643,7 @@ namespace gbe
auto jip = fwdTargets.lower_bound(LabelIndex(0));
JIPs.insert(std::make_pair(bra, *jip));
}
+
}
void Context::handleSLM(void) {
diff --git a/backend/src/backend/context.hpp b/backend/src/backend/context.hpp
index 3d3c6d4..24f2873 100644
--- a/backend/src/backend/context.hpp
+++ b/backend/src/backend/context.hpp
@@ -21,6 +21,7 @@
#define __GBE_CONTEXT_HPP__
#include "ir/instruction.hpp"
+#include "ir/function.hpp"
#include "backend/program.h"
#include "sys/set.hpp"
#include "sys/map.hpp"
diff --git a/backend/src/backend/gen_context.cpp b/backend/src/backend/gen_context.cpp
index 7b7dec3..2a4047a 100644
--- a/backend/src/backend/gen_context.cpp
+++ b/backend/src/backend/gen_context.cpp
@@ -126,7 +126,7 @@ namespace gbe
errCode = OUT_OF_RANGE_IF_ENDIF;
return false;
}
- p->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) {
--
1.8.3.2
More information about the Beignet
mailing list