On Wed, Dec 25, 2013 at 02:28:48AM +0000, Song, Ruiling wrote:
>
> See my two comments
> -----Original Message-----
> From: [email protected]
> [mailto:[email protected]] On Behalf Of Zhigang Gong
> Sent: Tuesday, December 24, 2013 2:29 PM
> To: Yang, Rong R
> Cc: Gong, Zhigang; [email protected]
> 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: [email protected]
> > [mailto:[email protected]] On Behalf Of Zhigang
> > Gong
> > Sent: Friday, December 20, 2013 3:27 PM
> > To: [email protected]
> > 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 <[email protected]>
> > ---
> > 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
> > [email protected]
> > http://lists.freedesktop.org/mailman/listinfo/beignet
> > _______________________________________________
> > Beignet mailing list
> > [email protected]
> > http://lists.freedesktop.org/mailman/listinfo/beignet
> _______________________________________________
> Beignet mailing list
> [email protected]
> http://lists.freedesktop.org/mailman/listinfo/beignet
_______________________________________________
Beignet mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/beignet
