[Beignet] [PATCH 1/4] GBE: rewrite the liveness analysis routine.
Song, Ruiling
ruiling.song at intel.com
Mon Dec 30 21:21:17 PST 2013
This patch LGTM
-----Original Message-----
From: beignet-bounces at lists.freedesktop.org [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of Zhigang Gong
Sent: Monday, December 30, 2013 7:07 PM
To: beignet at lists.freedesktop.org
Cc: Gong, Zhigang
Subject: [Beignet] [PATCH 1/4] GBE: rewrite the liveness analysis routine.
The previous implementation has two problems:
1. At the liveness analysis phase, the liveIn and liveOut computation is incorrect. The liveIn is not a static information it should be computed along with the liveOut during the backward data flow analysis.
2. At the register allocation phase, it only considers the liveOut information. Actually, we also need to consider the liveIn information.
v2:
a. Remove calculating maxID for the liveIn register set and remove calculating
minID for the liveOut register set.
b. Don't insert a bb to the liveness work list if it is already in the list.
Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
---
backend/src/backend/gen_context.hpp | 4 ++
backend/src/backend/gen_reg_allocation.cpp | 12 +++--
backend/src/ir/liveness.cpp | 75 ++++++++++++++++++----------
backend/src/ir/liveness.hpp | 37 +++++++++++++-
backend/src/ir/profile.cpp | 3 +-
backend/src/ir/profile.hpp | 3 +-
6 files changed, 100 insertions(+), 34 deletions(-)
diff --git a/backend/src/backend/gen_context.hpp b/backend/src/backend/gen_context.hpp
index f8ef8e0..b8c2bca 100644
--- a/backend/src/backend/gen_context.hpp
+++ b/backend/src/backend/gen_context.hpp
@@ -76,6 +76,10 @@ namespace gbe
INLINE const ir::Liveness::LiveOut &getLiveOut(const ir::BasicBlock *bb) const {
return this->liveness->getLiveOut(bb);
}
+ /*! Get the LiveIn information for the given block */
+ INLINE const ir::Liveness::UEVar &getLiveIn(const ir::BasicBlock *bb) const {
+ return this->liveness->getLiveIn(bb);
+ }
void collectShifter(GenRegister dest, GenRegister src);
void loadTopHalf(GenRegister dest, GenRegister src); diff --git a/backend/src/backend/gen_reg_allocation.cpp b/backend/src/backend/gen_reg_allocation.cpp
index 30f9e38..d7362dd 100644
--- a/backend/src/backend/gen_reg_allocation.cpp
+++ b/backend/src/backend/gen_reg_allocation.cpp
@@ -569,6 +569,7 @@ namespace gbe
int32_t insnID = 0;
for (auto &block : *selection.blockList) {
int32_t lastID = insnID;
+ int32_t firstID = insnID;
// Update the intervals of each used register. Note that we do not
// register allocate R0, so we skip all sub-registers in r0
for (auto &insn : block.insnList) { @@ -619,14 +620,17 @@ namespace gbe
insnID++;
}
+ // 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)
+ 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::BasicBlock *bb = block.bb;
const ir::Liveness::LiveOut &liveOut = ctx.getLiveOut(bb);
- for (auto reg : liveOut) {
- this->intervals[reg].minID = std::min(this->intervals[reg].minID, lastID);
+ for (auto reg : liveOut)
this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, lastID);
- }
}
// Sort both intervals in starting point and ending point increasing orders diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp index b0a4314..082285b 100644
--- a/backend/src/ir/liveness.cpp
+++ b/backend/src/ir/liveness.cpp
@@ -29,9 +29,20 @@ namespace ir {
Liveness::Liveness(Function &fn) : fn(fn) {
// Initialize UEVar and VarKill for each block
- fn.foreachBlock([this](const BasicBlock &bb) { this->initBlock(bb); });
- // Now with iterative analysis, we compute liveout sets
- this->computeLiveOut();
+ fn.foreachBlock([this](const BasicBlock &bb) {
+ this->initBlock(bb);
+ // If the bb has ret instruction, add it to the work list set.
+ const Instruction *lastInsn = bb.getLastInstruction();
+ const ir::Opcode op = lastInsn->getOpcode();
+ if (op == OP_RET) {
+ struct BlockInfo * info = liveness[&bb];
+ workList.push_back(info);
+ info->liveOut.insert(ocl::retVal);
+ }
+ });
+ // Now with iterative analysis, we compute liveout and livein sets
+ this->computeLiveInOut();
+
}
Liveness::~Liveness(void) {
@@ -65,30 +76,42 @@ namespace ir {
}
}
- void Liveness::computeLiveOut(void) {
- // First insert the UEVar from the successors
- foreach<DF_SUCC>([](BlockInfo &info, const BlockInfo &succ) {
- const UEVar &ueVarSet = succ.upwardUsed;
- // Iterate over all the registers in the UEVar of our successor
- for (auto ueVar : ueVarSet) info.liveOut.insert(ueVar);
- });
- // Now iterate on liveOut
- bool changed = true;
- while (changed) {
- changed = false;
- foreach<DF_SUCC>([&changed](BlockInfo &info, const BlockInfo &succ) {
- const UEVar &killSet = succ.varKill;
- const LiveOut &liveOut = succ.liveOut;
- // Iterate over all the registers in the UEVar of our successor
- for (auto living : liveOut) {
- if (killSet.contains(living)) continue;
- if (info.liveOut.contains(living)) continue;
- info.liveOut.insert(living);
- changed = true;
+// Use simple backward data flow analysis to solve the liveness problem.
+ void Liveness::computeLiveInOut(void) {
+ do {
+ struct BlockInfo *currInfo = workList.pop_front();
+ for (auto currOutVar : currInfo->liveOut)
+ if (!currInfo->varKill.contains(currOutVar))
+ currInfo->upwardUsed.insert(currOutVar);
+ bool isChanged = false;
+ for (auto prev : currInfo->bb.getPredecessorSet()) {
+ BlockInfo *prevInfo = liveness[prev];
+ for (auto currInVar : currInfo->upwardUsed) {
+ auto changed = prevInfo->liveOut.insert(currInVar);
+ if (changed.second) isChanged = true;
}
- });
- }
- }
+ if (isChanged ) workList.push_back(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;
+ printf("\tout Lives: ");
+ for (auto outVar : outVarSet) {
+ printf("%d ", outVar);
+ }
+ printf("\n\tin Lives: ");
+ for (auto inVar : inVarSet) {
+ printf("%d ", inVar);
+ }
+ printf("\n");
+ });
+#endif
+ }
/*! To pretty print the livfeness info */
static const uint32_t prettyInsnStrSize = 48; diff --git a/backend/src/ir/liveness.hpp b/backend/src/ir/liveness.hpp index ea5a157..30e43c0 100644
--- a/backend/src/ir/liveness.hpp
+++ b/backend/src/ir/liveness.hpp
@@ -24,6 +24,7 @@
#ifndef __GBE_IR_LIVENESS_HPP__
#define __GBE_IR_LIVENESS_HPP__
+#include <list>
#include "sys/map.hpp"
#include "sys/set.hpp"
#include "ir/register.hpp"
@@ -57,7 +58,7 @@ namespace ir {
typedef set<Register> VarKill;
/*! Per-block info */
struct BlockInfo : public NonCopyable {
- BlockInfo(const BasicBlock &bb) : bb(bb) {}
+ BlockInfo(const BasicBlock &bb) : bb(bb), inWorkList(false) {}
const BasicBlock &bb;
INLINE bool inUpwardUsed(Register reg) const {
return upwardUsed.contains(reg); @@ -71,6 +72,7 @@ namespace ir {
UEVar upwardUsed;
LiveOut liveOut;
VarKill varKill;
+ bool inWorkList;
};
/*! Gives for each block the variables alive at entry / exit */
typedef map<const BasicBlock*, BlockInfo*> Info; @@ -87,6 +89,12 @@ namespace ir {
const BlockInfo &info = this->getBlockInfo(bb);
return info.liveOut;
}
+ /*! Get the set of registers alive at the beginning of the block */
+ const UEVar &getLiveIn(const BasicBlock *bb) const {
+ const BlockInfo &info = this->getBlockInfo(bb);
+ return info.upwardUsed;
+ }
+
/*! 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 */ @@ -119,9 +127,34 @@ namespace ir {
/*! Initialize UEVar and VarKill per instruction */
void initInstruction(BlockInfo &info, const Instruction &insn);
/*! Now really compute LiveOut based on UEVar and VarKill */
- void computeLiveOut(void);
+ void computeLiveInOut(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;
+
/*! Use custom allocators */
GBE_CLASS(Liveness);
+
};
/*! Output a nice ASCII reprensation of the liveness */ diff --git a/backend/src/ir/profile.cpp b/backend/src/ir/profile.cpp index 10e0c59..b693c2b 100644
--- a/backend/src/ir/profile.cpp
+++ b/backend/src/ir/profile.cpp
@@ -40,7 +40,7 @@ namespace ir {
"stack_pointer",
"block_ip",
"barrier_id", "thread_number",
- "work_dimension", "sampler_info"
+ "work_dimension", "sampler_info", "retVal"
};
#if GBE_DEBUG
@@ -77,6 +77,7 @@ namespace ir {
DECL_NEW_REG(FAMILY_DWORD, threadn);
DECL_NEW_REG(FAMILY_DWORD, workdim);
DECL_NEW_REG(FAMILY_WORD, samplerinfo);
+ DECL_NEW_REG(FAMILY_WORD, retVal);
}
#undef DECL_NEW_REG
diff --git a/backend/src/ir/profile.hpp b/backend/src/ir/profile.hpp index 89dd69f..2f16741 100644
--- a/backend/src/ir/profile.hpp
+++ b/backend/src/ir/profile.hpp
@@ -65,7 +65,8 @@ namespace ir {
static const Register threadn = Register(21); // number of threads
static const Register workdim = Register(22); // work dimention.
static const Register samplerinfo = Register(23); // store sampler info.
- static const uint32_t regNum = 24; // number of special registers
+ static const Register retVal = Register(24); // helper register to do data flow analysis.
+ static const uint32_t regNum = 25; // number of special registers
extern const char *specialRegMean[]; // special register name.
} /* namespace ocl */
--
1.7.9.5
_______________________________________________
Beignet mailing list
Beignet at lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/beignet
More information about the Beignet
mailing list