diff options
author | Zhigang Gong <zhigang.gong@intel.com> | 2015-09-24 08:47:28 +0800 |
---|---|---|
committer | Yang Rong <rong.r.yang@intel.com> | 2015-10-08 16:35:53 +0800 |
commit | db03fad28a59338a1b885dd71b1363106658d4fb (patch) | |
tree | b9e7e1d94e5f6f1c0d732ee904463f5536a31e09 /backend | |
parent | 02750c042a325507bdeb23777d61ee8d4e048c10 (diff) |
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@intel.com>
Reviewed-by: Ruiling Song <ruiling.song@intel.com>
Diffstat (limited to 'backend')
-rw-r--r-- | backend/src/ir/value.cpp | 100 | ||||
-rw-r--r-- | backend/src/ir/value.hpp | 13 |
2 files changed, 113 insertions, 0 deletions
diff --git a/backend/src/ir/value.cpp b/backend/src/ir/value.cpp index 840fb5c8..19ecabf6 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 a9e51084..ba3ba01f 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 |