[Beignet] [PATCH] GBE: Implement an extra liveness analysis for the Gen backend.
Zhigang Gong
zhigang.gong at intel.com
Wed Jan 22 22:18:12 PST 2014
Consider the following scenario, %100's normal liveness will start from Ln-1's
position. In normal analysis, the Ln-1 is not Ln's predecessor, thus the liveness
of %100 will be passed to Ln and then will not be passed to L0.
But considering we are running on a multilane with predication's vector machine.
The unconditional BR in Ln-1 may be removed and it will enter Ln with a subset of
the revert set of Ln-1's predication. For example when running Ln-1, the active lane
is 0-7, then at Ln the active lane is 8-15. Then at the end of Ln, a subset of 8-15
will jump to L0. If a register %10 is allocated the same GRF as %100, given the fact
that their normal liveness doesn't overlapped, the a subset of 8-15 lanes will be
modified. If the %10 and %100 are the same vector data type, then we are fine. But if
%100 is a float vector, and the %10 is a bool or short vector, then we hit a bug here.
L0:
...
%10 = 5
...
Ln-1:
%100 = 2
BR Ln+1
Ln:
...
BR(%xxx) L0
Ln+1:
%101 = %100 + 2;
...
The solution to fix this issue is to build an extra liveness analysis. We will start with
those BBs with backward jump. Then pass all the liveOut register as extra liveIn
of current BB and then forward this extra liveIn to all the blocks. This is very similar
to the normal liveness analysis just with reverse direction.
Thanks yang rong who found this bug.
Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
---
backend/src/backend/gen_context.hpp | 9 +++
backend/src/backend/gen_reg_allocation.cpp | 11 ++-
backend/src/ir/liveness.cpp | 118 ++++++++++++++++++++++++++--
backend/src/ir/liveness.hpp | 41 ++++------
4 files changed, 143 insertions(+), 36 deletions(-)
diff --git a/backend/src/backend/gen_context.hpp b/backend/src/backend/gen_context.hpp
index 9c7fc9e..6cfc295 100644
--- a/backend/src/backend/gen_context.hpp
+++ b/backend/src/backend/gen_context.hpp
@@ -83,6 +83,15 @@ namespace gbe
return this->liveness->getLiveIn(bb);
}
+ /*! Get the extra liveOut information for the given block */
+ INLINE const ir::Liveness::LiveOut &getExtraLiveOut(const ir::BasicBlock *bb) const {
+ return this->liveness->getExtraLiveOut(bb);
+ }
+ /*! Get the extra LiveIn information for the given block */
+ INLINE const ir::Liveness::UEVar &getExtraLiveIn(const ir::BasicBlock *bb) const {
+ return this->liveness->getExtraLiveIn(bb);
+ }
+
void collectShifter(GenRegister dest, GenRegister src);
void loadTopHalf(GenRegister dest, GenRegister src);
void storeTopHalf(GenRegister dest, GenRegister src);
diff --git a/backend/src/backend/gen_reg_allocation.cpp b/backend/src/backend/gen_reg_allocation.cpp
index 51a9f76..4e33240 100644
--- a/backend/src/backend/gen_reg_allocation.cpp
+++ b/backend/src/backend/gen_reg_allocation.cpp
@@ -628,14 +628,17 @@ namespace gbe
// All registers alive at the begining of the block must update their intervals.
const ir::BasicBlock *bb = block.bb;
- const ir::Liveness::UEVar &liveIn = ctx.getLiveIn(bb);
- for (auto reg : liveIn)
+ for (auto reg : ctx.getLiveIn(bb))
this->intervals[reg].minID = std::min(this->intervals[reg].minID, firstID);
+ for (auto reg : ctx.getExtraLiveIn(bb))
+ this->intervals[reg].minID = std::min(this->intervals[reg].minID, firstID);
// All registers alive at the end of the block must have their intervals
// updated as well
- const ir::Liveness::LiveOut &liveOut = ctx.getLiveOut(bb);
- for (auto reg : liveOut)
+ for (auto reg : ctx.getLiveOut(bb))
+ this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, lastID);
+
+ for (auto reg : ctx.getExtraLiveOut(bb))
this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, lastID);
}
diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp
index 082285b..6c3a477 100644
--- a/backend/src/ir/liveness.cpp
+++ b/backend/src/ir/liveness.cpp
@@ -34,15 +34,25 @@ namespace ir {
// If the bb has ret instruction, add it to the work list set.
const Instruction *lastInsn = bb.getLastInstruction();
const ir::Opcode op = lastInsn->getOpcode();
+ struct BlockInfo * info = liveness[&bb];
if (op == OP_RET) {
- struct BlockInfo * info = liveness[&bb];
- workList.push_back(info);
+ workSet.insert(info);
info->liveOut.insert(ocl::retVal);
+ } else if (op == OP_BRA) {
+ // If this is a backward jump, put it to the extra work list.
+ if (((BranchInstruction*)lastInsn)->getLabelIndex() < bb.getLabelIndex())
+ extraWorkSet.insert(info);
}
});
// Now with iterative analysis, we compute liveout and livein sets
this->computeLiveInOut();
-
+ for (auto it : extraWorkSet) {
+ for (auto reg : it->liveOut) {
+ if (!it->upwardUsed.contains(reg))
+ it->extraLiveIn.insert(reg);
+ }
+ }
+ this->computeExtraLiveInOut();
}
Liveness::~Liveness(void) {
@@ -78,8 +88,9 @@ namespace ir {
// Use simple backward data flow analysis to solve the liveness problem.
void Liveness::computeLiveInOut(void) {
- do {
- struct BlockInfo *currInfo = workList.pop_front();
+ while(!workSet.empty()) {
+ auto currInfo = *workSet.begin();
+ workSet.erase(currInfo);
for (auto currOutVar : currInfo->liveOut)
if (!currInfo->varKill.contains(currOutVar))
currInfo->upwardUsed.insert(currOutVar);
@@ -90,29 +101,120 @@ namespace ir {
auto changed = prevInfo->liveOut.insert(currInVar);
if (changed.second) isChanged = true;
}
- if (isChanged ) workList.push_back(prevInfo);
+ if (isChanged )
+ workSet.insert(prevInfo);
}
- } while (!workList.empty());
-
+ };
#if 0
fn.foreachBlock([this](const BasicBlock &bb){
printf("label %d:\n", bb.getLabelIndex());
BlockInfo *info = liveness[&bb];
auto &outVarSet = info->liveOut;
auto &inVarSet = info->upwardUsed;
+ auto &extraInVarSet = info->extraLiveIn;
+ auto &extraOutVarSet = info->extraLiveOut;
+ printf("\n\tin Lives: ");
+ for (auto inVar : inVarSet) {
+ printf("%d ", inVar);
+ }
+ printf("\n");
printf("\tout Lives: ");
for (auto outVar : outVarSet) {
printf("%d ", outVar);
}
+ printf("\n");
+
+ });
+#endif
+ }
+
+/*
+ Consider the following scenario, %100's normal liveness will start from Ln-1's
+ position. In normal analysis, the Ln-1 is not Ln's predecessor, thus the liveness
+ of %100 will be passed to Ln and then will not be passed to L0.
+
+ But considering we are running on a multilane with predication's vector machine.
+ The unconditional BR in Ln-1 may be removed and it will enter Ln with a subset of
+ the revert set of Ln-1's predication. For example when running Ln-1, the active lane
+ is 0-7, then at Ln the active lane is 8-15. Then at the end of Ln, a subset of 8-15
+ will jump to L0. If a register %10 is allocated the same GRF as %100, given the fact
+ that their normal liveness doesn't overlapped, the a subset of 8-15 lanes will be
+ modified. If the %10 and %100 are the same vector data type, then we are fine. But if
+ %100 is a float vector, and the %10 is a bool or short vector, then we hit a bug here.
+
+L0:
+ ...
+ %10 = 5
+ ...
+Ln-1:
+ %100 = 2
+ BR Ln+1
+
+Ln:
+ ...
+ BR(%xxx) L0
+
+Ln+1:
+ %101 = %100 + 2;
+ ...
+
+ The solution to fix this issue is to build another liveness data. We will start with
+ those BBs with backward jump. Then pass all the liveOut register as extra liveIn
+ of current BB and then forward this extra liveIn to all the blocks. This is very similar
+ to the normal liveness analysis just with reverse direction.
+*/
+ void Liveness::computeExtraLiveInOut(void) {
+ while(!extraWorkSet.empty()) {
+ struct BlockInfo *currInfo = *extraWorkSet.begin();
+ extraWorkSet.erase(currInfo);
+ for (auto currInVar : currInfo->extraLiveIn)
+ currInfo->extraLiveOut.insert(currInVar);
+ bool isChanged = false;
+ for (auto succ : currInfo->bb.getSuccessorSet()) {
+ BlockInfo *succInfo = liveness[succ];
+ for (auto currOutVar : currInfo->extraLiveOut) {
+ bool changed = false;
+ if (!succInfo->upwardUsed.contains(currOutVar)) {
+ auto it = succInfo->extraLiveIn.insert(currOutVar);
+ changed = it.second;
+ }
+ if (changed) isChanged = true;
+ }
+ if (isChanged)
+ extraWorkSet.insert(succInfo);}
+ };
+#if 0
+ fn.foreachBlock([this](const BasicBlock &bb){
+ printf("label %d:\n", bb.getLabelIndex());
+ BlockInfo *info = liveness[&bb];
+ auto &outVarSet = info->liveOut;
+ auto &inVarSet = info->upwardUsed;
+ auto &extraInVarSet = info->extraLiveIn;
+ auto &extraOutVarSet = info->extraLiveOut;
printf("\n\tin Lives: ");
for (auto inVar : inVarSet) {
printf("%d ", inVar);
}
+ printf("\n\textra in Lives: ");
+ for (auto inVar : extraInVarSet) {
+ printf("%d ", inVar);
+ }
printf("\n");
+ printf("\tout Lives: ");
+ for (auto outVar : outVarSet) {
+ printf("%d ", outVar);
+ }
+ printf("\n\textra out Lives: ");
+ for (auto outVar : extraOutVarSet) {
+ printf("%d ", outVar);
+ }
+ printf("\n");
+
});
#endif
}
+
/*! To pretty print the livfeness info */
static const uint32_t prettyInsnStrSize = 48;
static const uint32_t prettyRegStrSize = 5;
diff --git a/backend/src/ir/liveness.hpp b/backend/src/ir/liveness.hpp
index 30e43c0..9198eae 100644
--- a/backend/src/ir/liveness.hpp
+++ b/backend/src/ir/liveness.hpp
@@ -58,7 +58,7 @@ namespace ir {
typedef set<Register> VarKill;
/*! Per-block info */
struct BlockInfo : public NonCopyable {
- BlockInfo(const BasicBlock &bb) : bb(bb), inWorkList(false) {}
+ BlockInfo(const BasicBlock &bb) : bb(bb) {}
const BasicBlock &bb;
INLINE bool inUpwardUsed(Register reg) const {
return upwardUsed.contains(reg);
@@ -69,10 +69,11 @@ namespace ir {
INLINE bool inVarKill(Register reg) const {
return varKill.contains(reg);
}
+ UEVar extraLiveIn;
+ LiveOut extraLiveOut;
UEVar upwardUsed;
LiveOut liveOut;
VarKill varKill;
- bool inWorkList;
};
/*! Gives for each block the variables alive at entry / exit */
typedef map<const BasicBlock*, BlockInfo*> Info;
@@ -95,6 +96,17 @@ namespace ir {
return info.upwardUsed;
}
+ /*! Get the set of extra registers alive at the end of the block */
+ const LiveOut &getExtraLiveOut(const BasicBlock *bb) const {
+ const BlockInfo &info = this->getBlockInfo(bb);
+ return info.extraLiveOut;
+ }
+ /*! Get the set of extra registers alive at the beginning of the block */
+ const UEVar &getExtraLiveIn(const BasicBlock *bb) const {
+ const BlockInfo &info = this->getBlockInfo(bb);
+ return info.extraLiveIn;
+ }
+
/*! Return the function the liveness was computed on */
INLINE const Function &getFunction(void) const { return fn; }
/*! Actually do something for each successor / predecessor of *all* blocks */
@@ -128,29 +140,10 @@ namespace ir {
void initInstruction(BlockInfo &info, const Instruction &insn);
/*! Now really compute LiveOut based on UEVar and VarKill */
void computeLiveInOut(void);
+ void computeExtraLiveInOut(void);
/*! Set of work list block which has exit(return) instruction */
- typedef std::list <struct BlockInfo*> BlockInfoList;
-
- /*! helper structure to maintain the liveness work list.
- don't add the block if it is already in the list. */
- struct LivenessWorkList : BlockInfoList {
-
- void push_back(struct BlockInfo *info) {
- if (info->inWorkList)
- return;
- info->inWorkList = true;
- BlockInfoList::push_back(info);
- }
-
- struct BlockInfo * pop_front() {
- struct BlockInfo *biFront = front();
- BlockInfoList::pop_front();
- if (biFront)
- biFront->inWorkList = false;
- return biFront;
- }
-
- } workList;
+ typedef set <struct BlockInfo*> WorkSet;
+ WorkSet workSet, extraWorkSet;
/*! Use custom allocators */
GBE_CLASS(Liveness);
--
1.7.9.5
More information about the Beignet
mailing list