[Beignet] [PATCH 5/5] GBE: implement further phi mov optimization based on intra-BB interefering analysis.

[Zhigang Gong]

On Mon, Sep 21, 2015 at 03:09:12AM +0000, Song, Ruiling wrote:
> 
> 
> > But for some cases, many phi copy source registers are also phi copy value
> > which has multiple definitions. And they could all be reduced to one phi copy
> > register if there is no interfering in all BBs. This patch with the previous patches
> > could reduce the whole spilled register from 200+ to only 70 for a SGEMM kernel
> > and the performance could boost about 10 times.
> I am not sure what kind of phi/phiCopy  pattern are you referred to, as you don't give some IR piece to show that.
> Is it a loop inside loop CFG pattern? If you can give some extra info on the CFG or phi/phiCopy pattern, it would be nice.
> 
>  The idea of the patch did make sense to me. But as the code comment is little, some code are not easy for me to catch the underlying meaning.
> As the phi optimization is not a so-obvious algorithm, it would be better, so I can fully understand your algorithm details. I have add a note at the code-block that I don't understand well.
> 
> Thanks!
> Ruiling
> > +  void GenWriter::postPhiCopyOptimization(ir::Liveness &liveness,
> > +         ir::Function &fn, map <ir::Register, ir::Register> &replaceMap,
> > +         map <ir::Register, ir::Register> &redundantPhiCopyMap)  {
> > +    // When doing the first pass phi copy optimization, we skip all the phi src
> > MOV cases
> > +    // whoes phiSrdDefs are also a phi value. We leave it here when all phi copy
> > optimizations
> > +    // have been done. Then we don't need to worry about there are still
> > reducible phi copy remained.
> > +    // We only need to check whether those possible redundant phi copy pairs'
> > interfering to
> > +    // each other globally, by leverage the DAG information.
> > +    using namespace ir;
> > +
> > +    // Firstly, validate all possible redundant phi copy map and update liveness
> > information
> > +    // accordingly.
> I think you can add one line to explain why you need to validate the information.
redundant map and replace map are tracked independently. Some phiCopySrc may be replaced
after it was marked as redundant copy. So we need to check the replace map and correct
those replaced record in redundant map.

> 
> > +    if (replaceMap.size() != 0) {
> > +      for (auto pair : replaceMap) {
> > +        if (redundantPhiCopyMap.find(pair.first) != redundantPhiCopyMap.end()) {
> > +          auto it = redundantPhiCopyMap.find(pair.first);
> > +          Register phiCopy = it->second;
> > +          Register newPhiCopySrc = pair.second;
> > +          redundantPhiCopyMap.erase(it);
> > +          redundantPhiCopyMap.insert(std::make_pair(newPhiCopySrc, phiCopy));
> > +        }
> > +      }
> > +      liveness.replaceRegs(replaceMap);
> > +      replaceMap.clear();
> > +    }
> > +    if (redundantPhiCopyMap.size() == 0)
> > +      return;
> > +    auto dag = new FunctionDAG(liveness);
> > +
> > +    map<Register, Register> newRedundant;
> > +    map<Register, Register> *curRedundant = &redundantPhiCopyMap;
> > +    map<Register, Register> *nextRedundant = &newRedundant, tmp;
> > +    map<Register, Register> replacedRegs, revReplacedRegs;
> It would be nice to comment what revReplacedRegs used for?
replacedRegs is (from, to) map
revReplacedRegs is (to, from) map.
Both of them are required, because our dag doesn't support dynamic update
currently, thus if in the same pass, if one register is already replaced from
or replaced to, then we have to skip it in this round processing, because the
DAG information for these values/registers are not up-to-date. We have to
defer them into next round processing when DAG will be updated.

> 
> > +    // Do multi pass redundant phi copy elimination based on the global
> > interfering information.
> > +    // FIXME, we don't need to re-compute the whole DAG for each pass.
> > +    while (curRedundant->size() > 0) {
> > +      for (auto &pair : *curRedundant) {
> > +        auto phiCopySrc = pair.first;
> > +        auto phiCopy = pair.second;
> 
> I am not sure what's the check used for? Could you give more comment?
Please refer to the above comments.


> > +        if (replacedRegs.find(phiCopy) != replacedRegs.end() ||
> > +            revReplacedRegs.find(phiCopy) != revReplacedRegs.end() ||
> > +            revReplacedRegs.find(phiCopySrc) != revReplacedRegs.end())
> > +          continue;
> 
> Below lines make sense to me.
> > +        if (!dag->interfere(liveness, phiCopySrc, phiCopy)) {
> > +          const ir::DefSet *phiCopySrcDef = dag->getRegDef(phiCopySrc);
> > +          const ir::UseSet *phiCopySrcUse = dag->getRegUse(phiCopySrc);
> > +          for (auto &s : *phiCopySrcDef) {
> > +            const Instruction *phiSrcDefInsn = s->getInstruction();
> > +            if (phiSrcDefInsn->getOpcode() == ir::OP_MOV &&
> > +                phiSrcDefInsn->getSrc(0) == phiCopy) {
> > +               const_cast<Instruction *>(phiSrcDefInsn)->remove();
> > +               continue;
> > +            }
> > +            replaceDst(const_cast<Instruction *>(phiSrcDefInsn), phiCopySrc,
> > phiCopy);
> > +          }
> > +
> > +          for (auto &s : *phiCopySrcUse) {
> > +            const Instruction *phiSrcUseInsn = s->getInstruction();
> > +            if (phiSrcUseInsn->getOpcode() == ir::OP_MOV &&
> > +                phiSrcUseInsn->getDst(0) == phiCopy) {
> > +               const_cast<Instruction *>(phiSrcUseInsn)->remove();
> > +               continue;
> > +            }
> > +            replaceSrc(const_cast<Instruction *>(phiSrcUseInsn), phiCopySrc,
> > phiCopy);
> > +          }
> > +
> > +          replacedRegs.insert(std::make_pair(phiCopySrc, phiCopy));
> > +          revReplacedRegs.insert(std::make_pair(phiCopy, phiCopySrc));
> > +          curRedundant->erase(phiCopySrc);
> >          }
> >        }
> > +
> 
> 
> And again below code block is a little hard for me. I don't know what it is used for.
Also refer to my above comments. If we got some register replaced in this round of
optimization, then we need to update the remained curRedundant paris and prepare
for next round optimization.

This complexity could be resolved latter when I implement DAG dynamic update just like
the liveness information update method. Let's just do it step by step.

Thanks for the careful review comments.
Zhigang Gong.

> > +      if (replacedRegs.size() != 0) {
> > +        liveness.replaceRegs(replacedRegs);
> > +        for (auto &pair : *curRedundant) {
> > +          auto from = pair.first;
> > +          auto to = pair.second;
> > +          bool revisit = false;
> > +          if (replacedRegs.find(pair.second) != replacedRegs.end()) {
> > +            to = replacedRegs.find(to)->second;
> > +            revisit = true;
> > +          }
> > +          if (revReplacedRegs.find(from) != revReplacedRegs.end() ||
> > +              revReplacedRegs.find(to) != revReplacedRegs.end())
> > +            revisit = true;
> > +          if (revisit)
> > +            nextRedundant->insert(std::make_pair(from, to));
> > +        }
> > +        std::swap(curRedundant, nextRedundant);
> > +      } else
> > +        break;
> > +
> > +      break;
> > +      nextRedundant->clear();
> > +      replacedRegs.clear();
> > +      revReplacedRegs.clear();
> > +      delete dag;
> > +      dag = new ir::FunctionDAG(liveness);
> >      }
> >      delete dag;
> >    }
> > @@ -2754,8 +2872,12 @@ namespace gbe
> >      ir::Liveness liveness(fn);
> > 
> 
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet