[GVN] Remove stale entry in phitranslate cache when new phi is generated for PRE

[wmi]

Summary

When a new phi is generated for scalarpre of an expression, the phiTranslate cache will become stale: Before PRE, the candidate expression must not be available in a predecessor block, and phitranslate will cache the information. After PRE, the expression will become available in all predecessor blocks, so the related entry in phiTranslate cache becomes stale. The patch will simply remove the stale entry so phiTranslate can be recomputed next time.

The stale entry in phitranslate cache will not affect correctness but will cause missing PRE opportunity for later instructions.

[wmi]

Ping.

[davide]

LGTM, please make sure this doesn't break things as PRE in GVN is quite fragile :)

lib/Transforms/Scalar/GVN.cpp

2224 ↗

(On Diff #109035)

Please add a comment.

llvm/trunk/include/llvm/Transforms/Scalar/GVN.h

public:
     ~ValueTable();
 
     uint32_t lookupOrAdd(Value *V);
     uint32_t lookup(Value *V, bool Verify = true) const;
     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
                             Value *LHS, Value *RHS);
     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
                           uint32_t Num, GVN &Gvn);
+    void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
     void clear();
     void erase(Value *v);
     void setAliasAnalysis(AliasAnalysis *A) { AA = A; }
     AliasAnalysis *getAliasAnalysis() const { return AA; }
     void setMemDep(MemoryDependenceResults *M) { MD = M; }
     void setDomTree(DominatorTree *D) { DT = D; }

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

if (Exp.commutative) {
     }
   }
 
   if (uint32_t NewNum = expressionNumbering[Exp])
     return NewNum;
   return Num;
 }
 
+/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
+/// again.
+void GVN::ValueTable::eraseTranslateCacheEntry(uint32_t Num,
+                                               const BasicBlock &CurrBlock) {
+  for (const BasicBlock *Pred : predecessors(&CurrBlock)) {
+    auto FindRes = PhiTranslateTable.find({Num, Pred});
+    if (FindRes != PhiTranslateTable.end())
+      PhiTranslateTable.erase(FindRes);
+  }
+}
+
 // In order to find a leader for a given value number at a
 // specific basic block, we first obtain the list of all Values for that number,
 // and then scan the list to find one whose block dominates the block in
 // question.  This is fast because dominator tree queries consist of only
 // a few comparisons of DFS numbers.
 Value *GVN::findLeader(const BasicBlock *BB, uint32_t num) {
   LeaderTableEntry Vals = LeaderTable[num];
   if (!Vals.Val) return nullptr;
bool GVN::performScalarPRE(Instruction *CurInst) {
   for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
     if (Value *V = predMap[i].first)
       Phi->addIncoming(V, predMap[i].second);
     else
       Phi->addIncoming(PREInstr, PREPred);
   }
 
   VN.add(Phi, ValNo);
+  // After creating a new PHI for ValNo, the phi translate result for ValNo will
+  // be changed, so erase the related stale entries in phi translate cache.
+  VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
   addToLeaderTable(ValNo, Phi, CurrentBlock);
   Phi->setDebugLoc(CurInst->getDebugLoc());
   CurInst->replaceAllUsesWith(Phi);
   if (MD && Phi->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Phi);
   VN.erase(CurInst);
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 

llvm/trunk/test/Transforms/GVN/PRE/phi-translate-2.ll

 bb343:
   %t334 = load volatile i32, i32* %AttrFlag
   %tobool2 = icmp eq i32 %cond, 0
   br i1 %tobool2, label %critedge.loopexit, label %for.body
 
 critedge.loopexit:
   unreachable
 }
+
+; Check sub expression will be pre transformed.
+; CHECK-LABEL: @test5(
+; CHECK: entry:
+; CHECK: %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+; CHECK: br i1 %cmp
+; CHECK: if.then2:
+; CHECK: %[[PTRTOINT:.*]] = ptrtoint i32* %add.ptr to i64
+; CHECK: %[[SUB:.*]] = sub i64 %sub.ptr.lhs.cast, %[[PTRTOINT]]
+; CHECK: br label %if.end3
+; CHECK: if.end3:
+; CHECK: %[[PREPHI:.*]] = phi i64 [ %sub.ptr.sub, %if.else ], [ %[[SUB]], %if.then2 ], [ %sub.ptr.sub, %entry ]
+; CHECK: %[[DIV:.*]] = ashr exact i64 %[[PREPHI]], 2
+; CHECK: ret i64 %[[DIV]]
+
+declare void @bar(...) local_unnamed_addr #1
+
+; Function Attrs: nounwind uwtable
+define i64 @test5(i32* %start, i32* %e, i32 %n1, i32 %n2) local_unnamed_addr #0 {
+entry:
+  %sub.ptr.lhs.cast = ptrtoint i32* %e to i64
+  %sub.ptr.rhs.cast = ptrtoint i32* %start to i64
+  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+  %cmp = icmp sgt i64 %sub.ptr.sub, 4000
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:                                          ; preds = %entry
+  %cmp1 = icmp sgt i32 %n1, %n2
+  br i1 %cmp1, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %if.then
+  %add.ptr = getelementptr inbounds i32, i32* %start, i64 800
+  br label %if.end3
+
+if.else:                                          ; preds = %if.then
+  tail call void (...) @bar() #2
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.then2, %if.else, %entry
+  %p.0 = phi i32* [ %add.ptr, %if.then2 ], [ %start, %if.else ], [ %start, %entry ]
+  %sub.ptr.rhs.cast5 = ptrtoint i32* %p.0 to i64
+  %sub.ptr.sub6 = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast5
+  %sub.ptr.div7 = ashr exact i64 %sub.ptr.sub6, 2
+  ret i64 %sub.ptr.div7
+}