summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--backend/src/ir/function.hpp18
-rw-r--r--backend/src/ir/liveness.cpp108
-rw-r--r--backend/src/llvm/llvm_gen_backend.cpp1
3 files changed, 73 insertions, 54 deletions
diff --git a/backend/src/ir/function.hpp b/backend/src/ir/function.hpp
index 60679f17..f8e37a5d 100644
--- a/backend/src/ir/function.hpp
+++ b/backend/src/ir/function.hpp
@@ -81,8 +81,19 @@ namespace ir {
functor(*curr);
}
}
- void insertPhiReg(Register reg) { phiRegs.insert(reg); }
- bool isPhiReg(Register reg) { return phiRegs.find(reg) != phiRegs.end(); }
+ void insertPhiReg(Register reg, bool isDef = true) {
+ if (isDef)
+ phiRegs.insert(reg);
+ else
+ phiUseRegs.insert(reg);
+ }
+ bool isPhiReg(Register reg, bool isDef = true)
+ { return isDef ? (phiRegs.find(reg) != phiRegs.end())
+ : (phiUseRegs.find(reg) != phiUseRegs.end()); }
+ template <bool isDef, typename T>
+ INLINE void foreachPhiReg(const T &functor) const {
+ for (auto reg : isDef ? phiRegs : phiUseRegs) functor(reg);
+ }
private:
friend class Function; //!< Owns the basic blocks
BlockSet predecessors; //!< Incoming blocks
@@ -90,7 +101,7 @@ namespace ir {
BasicBlock *nextBlock; //!< Block allocated just after this one
BasicBlock *prevBlock; //!< Block allocated just before this one
Function &fn; //!< Function the block belongs to
- set<Register> phiRegs;
+ set<Register> phiMovRegs, phiRegs;
GBE_CLASS(BasicBlock);
};
@@ -322,6 +333,7 @@ namespace ir {
/*! Push stack size. */
INLINE void pushStackSize(uint32_t step) { this->stackSize += step; }
private:
+ /*! Get block from its label */
friend class Context; //!< Can freely modify a function
std::string name; //!< Function name
const Unit &unit; //!< Function belongs to this unit
diff --git a/backend/src/ir/liveness.cpp b/backend/src/ir/liveness.cpp
index 724d5c39..a60e1ac0 100644
--- a/backend/src/ir/liveness.cpp
+++ b/backend/src/ir/liveness.cpp
@@ -46,11 +46,6 @@ namespace ir {
});
// Now with iterative analysis, we compute liveout and livein sets
this->computeLiveInOut();
- for (auto it : extraWorkSet) {
- for (auto reg : it->liveOut) {
- it->extraLiveIn.insert(reg);
- }
- }
this->computeExtraLiveInOut();
}
@@ -162,55 +157,66 @@ Ln+1:
of current BB and then forward this extra liveIn to all the blocks. This is very similar
to the normal liveness analysis just with reverse direction.
*/
+ typedef set <const BasicBlock *> ConstBlockSet;
+ typedef map<Register, const BasicBlock *> PhiRegMap;
+ //typedef set<const BasicBlock *> BlockSet;
+ void computePhiMap(const BasicBlock *currBB, const BasicBlock *firstBB,
+ const BasicBlock *lastBB, PhiRegMap &map,
+ PhiRegMap &useMap, ConstBlockSet &bbSet,
+ DataFlowDirection dir) {
+ if (currBB->getLabelIndex() > lastBB->getLabelIndex() ||
+ currBB->getLabelIndex() < firstBB->getLabelIndex())
+ return;
+ // end if we already visited this bb.
+ if (bbSet.find(currBB) != bbSet.end())
+ return;
+ bbSet.insert(currBB);
+ currBB->foreachPhiReg<true>([&](Register reg) {
+ /*If two phi movs are in the predecMap, we don't need to care about it.*/
+ if (map.find(reg) == map.end())
+ map.insert(std::make_pair(reg, currBB));
+ });
+ currBB->foreachPhiReg<false>([&](Register reg) {
+ if (useMap.find(reg) == useMap.end())
+ useMap.insert(std::make_pair(reg, currBB));
+ })
+ if (dir == DF_PRED)
+ for (auto pred : currBB->getPredecessorSet())
+ computePhiMap(pred, firstBB, lastBB, map, useMap, bbSet, dir);
+ else
+ for (auto succ : currBB->getsuccessorSet())
+ computePhiMap(succ, firstBB, lastBB, map, useMap, bbSet, dir);
+ }
+
void Liveness::computeExtraLiveInOut(void) {
- while(!extraWorkSet.empty()) {
- struct BlockInfo *currInfo = *extraWorkSet.begin();
- extraWorkSet.erase(currInfo);
- for (auto currInVar : currInfo->extraLiveIn)
- currInfo->extraLiveOut.insert(currInVar);
- bool isChanged = false;
- for (auto succ : currInfo->bb.getSuccessorSet()) {
- BlockInfo *succInfo = liveness[succ];
- for (auto currOutVar : currInfo->extraLiveOut) {
- bool changed = false;
- if (!succInfo->upwardUsed.contains(currOutVar)) {
- auto it = succInfo->extraLiveIn.insert(currOutVar);
- changed = it.second;
- }
- if (changed) isChanged = true;
+ for (auto blockInfo : extraWorkSet) {
+ const BasicBlock *bb = &(blockInfo->bb);
+
+ BranchInstruction *lastInsn = (BranchInstruction *)bb->getLastInstruction();
+ GBE_ASSERT(lastInsn->getOpcode() == OP_BRA);
+ const BasicBlock *firstBB = &fn.getBlock(lastInsn->getLabelIndex());
+ GBE_ASSERT(lastInsn->getLabelIndex() <= bb->getLabelIndex());
+ PhiRegMap predPHIMap, succPHIMap, phiUseMap;
+ ConstBlockSet predBBSet, succBBMap;
+ computePhiMap(bb, firstBB, bb, predPHIMap, phiUseMap, predBBSet, DF_PRED);
+ printf("block %d predecessor: ", bb->getLabelIndex());
+ for(auto it : bbSet)
+ printf("%d ", it->getLabelIndex());
+ printf("block %d successor: ", bb->getLabelIndex());
+ computePhiMap(firstBB, firstBB, bb, succPHIMap, phiUseMap, succBBSet, DF_SUCC);
+ for(auto it : succBBSet)
+ printf("%d ", it->getLabelIndex());
+ // find overlapped phi mov registers then extent their liveness.
+ // This algorithm doesn't calculate any hole liveness information.
+ // If further optimization want to find out those hole, this algorithm
+ // need to be modified.
+ for (auto it : succPHIMap) {
+ if (phiUseMap.find(it.first) == phiUseMap.end()) {
+ printf("extent block %d\n", it.second->getLabelIndex());
+ liveness[it.second]->upwardUsed.insert(it.first);
}
- if (isChanged)
- extraWorkSet.insert(succInfo);}
- };
-#if 0
- fn.foreachBlock([this](const BasicBlock &bb){
- printf("label %d:\n", bb.getLabelIndex());
- BlockInfo *info = liveness[&bb];
- auto &outVarSet = info->liveOut;
- auto &inVarSet = info->upwardUsed;
- auto &extraInVarSet = info->extraLiveIn;
- auto &extraOutVarSet = info->extraLiveOut;
- printf("\n\tin Lives: ");
- for (auto inVar : inVarSet) {
- printf("%d ", inVar);
- }
- printf("\n\textra in Lives: ");
- for (auto inVar : extraInVarSet) {
- printf("%d ", inVar);
- }
- printf("\n");
- printf("\tout Lives: ");
- for (auto outVar : outVarSet) {
- printf("%d ", outVar);
- }
- printf("\n\textra out Lives: ");
- for (auto outVar : extraOutVarSet) {
- printf("%d ", outVar);
}
- printf("\n");
-
- });
-#endif
+ }
}
diff --git a/backend/src/llvm/llvm_gen_backend.cpp b/backend/src/llvm/llvm_gen_backend.cpp
index e53d50ad..a9f52bf3 100644
--- a/backend/src/llvm/llvm_gen_backend.cpp
+++ b/backend/src/llvm/llvm_gen_backend.cpp
@@ -1924,6 +1924,7 @@ namespace gbe
const ir::Register dst = this->getRegister(&I);
const ir::Register src = this->getRegister(copy);
ctx.MOV(type, dst, src);
+ ctx.getBasicBlock()->insertPhiReg(dst, false);
}
void GenWriter::regAllocateBranchInst(BranchInst &I) {}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 17:40:44 +0000