[Beignet] [PATCH 1/2] GBE: continue to refine interfering check.
Zhigang Gong
zhigang.gong at linux.intel.com
Wed Sep 16 17:38:38 PDT 2015
Ping for review.
Thanks.
On Sun, Sep 06, 2015 at 03:05:00PM +0800, Zhigang Gong wrote:
> More aggresive interfering check, even if both registers are in
> Livein set or Liveout set, they are still possible not interfering
> to each other.
>
> Signed-off-by: Zhigang Gong <zhigang.gong at intel.com>
> ---
> backend/src/ir/value.cpp | 117 ++++++++++++++++++++++++++++++++++++++++++-----
> backend/src/ir/value.hpp | 5 +-
> 2 files changed, 109 insertions(+), 13 deletions(-)
>
> diff --git a/backend/src/ir/value.cpp b/backend/src/ir/value.cpp
> index 19ecabf..75a100f 100644
> --- a/backend/src/ir/value.cpp
> +++ b/backend/src/ir/value.cpp
> @@ -577,6 +577,97 @@ namespace ir {
> }
> }
>
> + static void getBlockDefInsns(const BasicBlock *bb, const DefSet *dSet, Register r, set <const Instruction *> &defInsns) {
> + for (auto def : *dSet) {
> + auto defInsn = def->getInstruction();
> + if (defInsn->getParent() == bb)
> + defInsns.insert(defInsn);
> + }
> + }
> +
> + static bool liveinInterfere(const BasicBlock *bb, const Instruction *defInsn, Register r1) {
> + BasicBlock::const_iterator iter = BasicBlock::const_iterator(defInsn);
> + BasicBlock::const_iterator iterE = bb->end();
> +
> + if (defInsn->getOpcode() == OP_MOV &&
> + defInsn->getSrc(0) == r1)
> + return false;
> + while (iter != iterE) {
> + const Instruction *insn = iter.node();
> + for (unsigned i = 0; i < insn->getDstNum(); i++) {
> + Register dst = insn->getDst(i);
> + if (dst == r1)
> + return false;
> + }
> + for (unsigned i = 0; i < insn->getSrcNum(); i++) {
> + ir::Register src = insn->getSrc(i);
> + if (src == r1)
> + return true;
> + }
> + ++iter;
> + }
> +
> + return false;
> + }
> +
> + // r0 and r1 both are in Livein set.
> + // Only if r0/r1 is used after r1/r0 has been modified.
> + bool FunctionDAG::interfereLivein(const BasicBlock *bb, Register r0, Register r1) const {
> + set <const Instruction *> defInsns0, defInsns1;
> + auto defSet0 = getRegDef(r0);
> + auto defSet1 = getRegDef(r1);
> + getBlockDefInsns(bb, defSet0, r0, defInsns0);
> + getBlockDefInsns(bb, defSet1, r1, defInsns1);
> + if (defInsns0.size() == 0 && defInsns1.size() == 0)
> + return false;
> +
> + for (auto insn : defInsns0) {
> + if (liveinInterfere(bb, insn, r1))
> + return true;
> + }
> +
> + for (auto insn : defInsns1) {
> + if (liveinInterfere(bb, insn, r0))
> + return true;
> + }
> + return false;
> + }
> +
> + // r0 and r1 both are in Liveout set.
> + // Only if the last definition of r0/r1 is a MOV r0, r1 or MOV r1, r0,
> + // it will not introduce interfering in this BB.
> + bool FunctionDAG::interfereLiveout(const BasicBlock *bb, Register r0, Register r1) const {
> + set <const Instruction *> defInsns0, defInsns1;
> + auto defSet0 = getRegDef(r0);
> + auto defSet1 = getRegDef(r1);
> + getBlockDefInsns(bb, defSet0, r0, defInsns0);
> + getBlockDefInsns(bb, defSet1, r1, defInsns1);
> + if (defInsns0.size() == 0 && defInsns1.size() == 0)
> + return false;
> +
> + BasicBlock::const_iterator iter = --bb->end();
> + BasicBlock::const_iterator iterE = bb->begin();
> + do {
> + const Instruction *insn = iter.node();
> + for (unsigned i = 0; i < insn->getDstNum(); i++) {
> + Register dst = insn->getDst(i);
> + if (dst == r0 || dst == r1) {
> + if (insn->getOpcode() != OP_MOV)
> + return true;
> + if (dst == r0 && insn->getSrc(0) != r1)
> + return true;
> + if (dst == r1 && insn->getSrc(0) != r0)
> + return true;
> + return false;
> + }
> + }
> + --iter;
> + } while (iter != iterE);
> + return false;
> + }
> +
> + // check instructions after the def of r0, if there is any def of r1, then no interefere for this
> + // range. Otherwise, if there is any use of r1, then return true.
> bool FunctionDAG::interfere(const BasicBlock *bb, Register inReg, Register outReg) const {
> auto dSet = getRegDef(outReg);
> bool visited = false;
> @@ -608,13 +699,13 @@ namespace ir {
> }
>
> 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.
> + // There are three different interfering cases which need further checking:
> + // 1. Both registers are in the LiveIn register set.
> + // 2. Both registers are in the LiveOut register set.
> + // 3. One is in LiveIn set and the Other is in LiveOut set.
> + // For the above 3 cases, we need 3 different ways to check whether they really
> + // interfering to each other.
> set<const BasicBlock *> bbSet0;
> set<const BasicBlock *> bbSet1;
> getRegUDBBs(r0, bbSet0);
> @@ -629,15 +720,18 @@ namespace ir {
> set_intersection(liveInBBSet0.begin(), liveInBBSet0.end(),
> liveInBBSet1.begin(), liveInBBSet1.end(),
> std::inserter(intersect, intersect.begin()));
> - if (intersect.size() != 0)
> - return true;
> + for (auto bb : intersect) {
> + if (interfereLivein(bb, r0, r1))
> + 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;
> -
> + for (auto bb : intersect) {
> + if (interfereLiveout(bb, r0, r1))
> + return true;
> + }
> set<const BasicBlock *> OIIntersect, IOIntersect;
> set_intersection(liveOutBBSet0.begin(), liveOutBBSet0.end(),
> liveInBBSet1.begin(), liveInBBSet1.end(),
> @@ -647,7 +741,6 @@ namespace ir {
> if (interfere(bb, r1, r0))
> return true;
> }
> -
> set_intersection(liveInBBSet0.begin(), liveInBBSet0.end(),
> liveOutBBSet1.begin(), liveOutBBSet1.end(),
> std::inserter(IOIntersect, IOIntersect.begin()));
> diff --git a/backend/src/ir/value.hpp b/backend/src/ir/value.hpp
> index ba3ba01..730e8ad 100644
> --- a/backend/src/ir/value.hpp
> +++ b/backend/src/ir/value.hpp
> @@ -248,9 +248,12 @@ namespace ir {
> // 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;
> + /*! check whether two registers which are both in liveout set interfering in the current BB. */
> + bool interfereLiveout(const BasicBlock *bb, Register r0, Register r1) const;
> + /*! check whether two registers which are both in livein set interfering in the current BB. */
> + bool interfereLivein(const BasicBlock *bb, 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
More information about the Beignet
mailing list