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

[Song, Ruiling]

> 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.

> +    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?

> +    // 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?
> +        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.
> +      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);
>