draft fix liveness.fixliveness

Signed-off-by: Zhigang Gong <zhigang.gong@gmail.com>

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) {}