[Beignet] [PATCH 1/2] GBE: continue to refine interfering check.
Zhigang Gong
zhigang.gong at intel.com
Sun Sep 6 00:05:00 PDT 2015
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
More information about the Beignet
mailing list