[Beignet] [PATCH v2 4/5] GBE: add some dag helper routines to check registers' interfering.

[Song, Ruiling]

LGTM

> -----Original Message-----
> From: Beignet [mailto:beignet-bounces at lists.freedesktop.org] On Behalf Of
> Zhigang Gong
> Sent: Sunday, September 6, 2015 3:04 PM
> To: beignet at lists.freedesktop.org
> Cc: Gong, Zhigang
> Subject: [Beignet] [PATCH v2 4/5] GBE: add some dag helper routines to check
> registers' interfering.
> 
> These helper function will be used in further phi mov optimization.
> 
> v2:
> remove the useless debug message code.
> 
> Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
> ---
>  backend/src/ir/value.cpp | 100
> +++++++++++++++++++++++++++++++++++++++++++++++
>  backend/src/ir/value.hpp |  13 ++++++
>  2 files changed, 113 insertions(+)
> 
> diff --git a/backend/src/ir/value.cpp b/backend/src/ir/value.cpp index
> 840fb5c..19ecabf 100644
> --- a/backend/src/ir/value.cpp
> +++ b/backend/src/ir/value.cpp
> @@ -558,6 +558,106 @@ namespace ir {
>      return it->second;
>    }
> 
> +  void FunctionDAG::getRegUDBBs(Register r, set<const BasicBlock *> &BBs)
> const{
> +    auto dSet = getRegDef(r);
> +    for (auto &def : *dSet)
> +      BBs.insert(def->getInstruction()->getParent());
> +    auto uSet = getRegUse(r);
> +    for (auto &use : *uSet)
> +      BBs.insert(use->getInstruction()->getParent());
> +  }
> +
> +  static void getLivenessBBs(const Liveness &liveness, Register r, const
> set<const BasicBlock *> &useDefSet,
> +                             set<const BasicBlock *> &liveInSet, set<const BasicBlock *>
> &liveOutSet){
> +    for (auto bb : useDefSet) {
> +      if (liveness.getLiveOut(bb).contains(r))
> +        liveOutSet.insert(bb);
> +      if (liveness.getLiveIn(bb).contains(r))
> +        liveInSet.insert(bb);
> +    }
> +  }
> +
> +  bool FunctionDAG::interfere(const BasicBlock *bb, Register inReg, Register
> outReg) const {
> +    auto dSet = getRegDef(outReg);
> +    bool visited = false;
> +    for (auto &def : *dSet) {
> +      auto defInsn = def->getInstruction();
> +      if (defInsn->getParent() == bb) {
> +        visited = true;
> +        if (defInsn->getOpcode() == OP_MOV && defInsn->getSrc(0) == inReg)
> +          continue;
> +        BasicBlock::const_iterator iter = BasicBlock::const_iterator(defInsn);
> +        BasicBlock::const_iterator iterE = bb->end();
> +        iter++;
> +        // check no use of phi in this basicblock between [phiCopySrc def, bb end]
> +        while (iter != iterE) {
> +          const ir::Instruction *insn = iter.node();
> +          // check phiUse
> +          for (unsigned i = 0; i < insn->getSrcNum(); i++) {
> +            ir::Register src = insn->getSrc(i);
> +            if (src == inReg)
> +              return true;
> +          }
> +          ++iter;
> +        }
> +      }
> +    }
> +    // We must visit the outReg at least once. Otherwise, something going
> wrong.
> +    GBE_ASSERT(visited);
> +    return false;
> +  }
> +
> +  bool FunctionDAG::interfere(const Liveness &liveness, Register r0, Register r1)
> const {
> +    // There are two interfering cases:
> +    //   1. Two registers are in the Livein set of the same BB.
> +    //   2. Two registers are in the Liveout set of the same BB.
> +    // If there are no any intersection BB, they are not interfering to each other.
> +    // If they are some intersection BBs, but one is only in the LiveIn and the
> other is
> +    // only in the Liveout, then we need to check whether they interefere each
> other in
> +    // that BB.
> +    set<const BasicBlock *> bbSet0;
> +    set<const BasicBlock *> bbSet1;
> +    getRegUDBBs(r0, bbSet0);
> +    getRegUDBBs(r1, bbSet1);
> +
> +    set<const BasicBlock *> liveInBBSet0, liveInBBSet1;
> +    set<const BasicBlock *> liveOutBBSet0, liveOutBBSet1;
> +    getLivenessBBs(liveness, r0, bbSet0, liveInBBSet0, liveOutBBSet0);
> +    getLivenessBBs(liveness, r1, bbSet1, liveInBBSet1, liveOutBBSet1);
> +
> +    set<const BasicBlock *> intersect;
> +    set_intersection(liveInBBSet0.begin(), liveInBBSet0.end(),
> +                     liveInBBSet1.begin(), liveInBBSet1.end(),
> +                     std::inserter(intersect, intersect.begin()));
> +    if (intersect.size() != 0)
> +      return true;
> +    intersect.clear();
> +    set_intersection(liveOutBBSet0.begin(), liveOutBBSet0.end(),
> +                     liveOutBBSet1.begin(), liveOutBBSet1.end(),
> +                     std::inserter(intersect, intersect.begin()));
> +    if (intersect.size() != 0)
> +      return true;
> +
> +    set<const BasicBlock *> OIIntersect, IOIntersect;
> +    set_intersection(liveOutBBSet0.begin(), liveOutBBSet0.end(),
> +                     liveInBBSet1.begin(), liveInBBSet1.end(),
> +                     std::inserter(OIIntersect, OIIntersect.begin()));
> +
> +    for (auto bb : OIIntersect) {
> +      if (interfere(bb, r1, r0))
> +        return true;
> +    }
> +
> +    set_intersection(liveInBBSet0.begin(), liveInBBSet0.end(),
> +                     liveOutBBSet1.begin(), liveOutBBSet1.end(),
> +                     std::inserter(IOIntersect, IOIntersect.begin()));
> +    for (auto bb : IOIntersect) {
> +      if (interfere(bb, r0, r1))
> +        return true;
> +    }
> +    return false;
> +  }
> +
>    std::ostream &operator<< (std::ostream &out, const FunctionDAG &dag) {
>      const Function &fn = dag.getFunction();
> 
> diff --git a/backend/src/ir/value.hpp b/backend/src/ir/value.hpp index
> a9e5108..ba3ba01 100644
> --- a/backend/src/ir/value.hpp
> +++ b/backend/src/ir/value.hpp
> @@ -238,6 +238,19 @@ namespace ir {
>      typedef map<ValueUse, DefSet*> UDGraph;
>      /*! The UseSet for each definition */
>      typedef map<ValueDef, UseSet*> DUGraph;
> +    /*! get register's use and define BB set */
> +    void getRegUDBBs(Register r, set<const BasicBlock *> &BBs) const;
> +    /*! get register's livein and liveout BB set */
> +    //void getLivenessBBs(const Liveness &liveness, Register r, set<const
> BasicBlock *> useDefSet,
> +    //                    set<const BasicBlock *> &liveInSet, set<const BasicBlock *>
> &liveOutSet) const;
> +    // check whether two register interering in the specific BB.
> +    // This function must be called at the following conditions:
> +    // 1. The outReg is in the BB's liveout set and not in the livein set.
> +    // 2. The inReg is in the BB's livein set but not in the livout set.
> +    bool interfere(const BasicBlock *bb, Register inReg, Register
> + outReg) const;
> +
> +    /*! check whether two register interfering to each other */
> +    bool interfere(const Liveness &liveness, Register r0, Register r1)
> + const;
>    private:
>      UDGraph udGraph;                   //!< All the UD chains
>      DUGraph duGraph;                   //!< All the DU chains
> --
> 1.9.1
> 
> _______________________________________________
> Beignet mailing list
> Beignet at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/beignet