[Beignet] [PATCH] GBE: rewrite the liveness analysis routine.
Zhigang Gong
zhigang.gong at linux.intel.com
Tue Dec 24 18:54:11 PST 2013
On Wed, Dec 25, 2013 at 02:28:48AM +0000, Song, Ruiling wrote:
>
> See my two comments
> -----Original Message-----
> From: beignet-bounces at lists.freedesktop.org [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of Zhigang Gong
> Sent: Tuesday, December 24, 2013 2:29 PM
> To: Yang, Rong R
> Cc: Gong, Zhigang; beignet at lists.freedesktop.org
> Subject: Re: [Beignet] [PATCH] GBE: rewrite the liveness analysis routine.
>
> On Tue, Dec 24, 2013 at 05:27:43AM +0000, Yang, Rong R wrote:
> > One question.
> >
> >
> > -----Original Message-----
> > From: beignet-bounces at lists.freedesktop.org
> > [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of Zhigang
> > Gong
> > Sent: Friday, December 20, 2013 3:27 PM
> > To: beignet at lists.freedesktop.org
> > Cc: Gong, Zhigang
> > Subject: [Beignet] [PATCH] 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.
> >
> > Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
> > ---
> > backend/src/backend/gen_context.hpp | 4 ++
> > backend/src/backend/gen_reg_allocation.cpp | 10 +++-
> > backend/src/ir/liveness.cpp | 78 ++++++++++++++++++----------
> > backend/src/ir/liveness.hpp | 13 ++++-
> > backend/src/ir/profile.cpp | 3 +-
> > backend/src/ir/profile.hpp | 3 +-
> > 6 files changed, 81 insertions(+), 30 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..50746e0 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,9 +620,16 @@ 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);
> > + this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, firstID);
> > + }
> > +
> > >>>>> Is it should use lastID to calc maxID? And using firstID to calc minID in liveOut.
> I just discussed with Ruiling about this same question. It seems that we could ignore the maxID calculating in liveIn loop and the minID calculating in liveOut loop. If the following assumption is corret: I didn't remove both of them in this patch is just for safety.
>
> After discussion, I think we can change it to as below:
>
> for (auto reg : liveIn)
> this->intervals[reg].minID = std::min(this->intervals[reg].minID, firstID);
>
> for (auto reg : liveOut)
> this->intervals[reg].maxID = std::max(this->intervals[reg].maxID, lastID);
>
> Any comments for the above change?
> I prefer this change to make code clean.
> >
> > // 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); diff --git
> > a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp index
> > b0a4314..29d96c4 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) {
> > + WorkList.push_back(&bb);
> > + BlockInfo *info = liveness[&bb];
> > + info->liveOut.insert(ocl::retVal);
> > + }
> > + });
> > + // Now with iterative analysis, we compute liveout and livein sets
> > + this->computeLiveInOut();
> > +
> > }
> >
> > Liveness::~Liveness(void) {
> > @@ -65,30 +76,45 @@ 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 {
> > + const BasicBlock *curr = WorkList.front();
> > + WorkList.pop_front();
> > + BlockInfo *info = liveness[curr];
> > + for (auto currOutVar : info->liveOut)
> > + if (!info->varKill.contains(currOutVar))
> > + info->upwardUsed.insert(currOutVar);
> > + bool isChanged = false;
> > + for (auto prev : curr->getPredecessorSet()) {
> > + BlockInfo *prevInfo = liveness[prev];
> > + for (auto currInVar : info->upwardUsed) {
> > + auto changed = prevInfo->liveOut.insert(currInVar);
> > + if (changed.second) isChanged = true;
> > }
> > - });
> > - }
> > - }
> > + // XXX is it possible one block is appended twice?
>
> Consider BBs like below:
> A:
> Def %1
> Def %2
> BR C
> B:
> Use %2
> C:
> Use %1
> When you processing use %1 in C, you will add B and A into the worklist. Then you go on processing use %2 in B, you will again add A into the worklist. Am I right?
> So, if you can deal with it easily, just add it. Or you can change the comment and leave it for later refine.
Right, your analysis is correct. There is an optimization opportunity, but
I'm not 100% sure whether we should remove the possible duplicate appending
of the same block, and that's reason why I put a XXX there.
Thanks for pointing this out which make me think it over again and I think
we could avoid inserting a block to the work list if it is still there.
Thanks,
Zhigang Gong.
> > + if (isChanged) WorkList.push_back(prev);
> > + }
> > + } 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..16cd789 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"
> > @@ -87,6 +88,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 +126,13 @@ 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 */
> > + std::list <const BasicBlock*> 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
> > _______________________________________________
> > Beignet mailing list
> > Beignet at lists.freedesktop.org
> > http://lists.freedesktop.org/mailman/listinfo/beignet
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet
More information about the Beignet
mailing list