[GVN] Verify value equality before doing phi translation for call instruction

[wmi]

Summary

This is an updated version of https://reviews.llvm.org/D66909 to fix PR42605.

Basically, current phi translatation translates an old value number to an new value number for a call instruction based on the literal equality of call expression, without verifying there is no clobber in between. This is incorrect.

To get a finegrain check, use MachineDependence analysis to do the job. However, this is still not ideal. Although given a call instruction, MemoryDependenceResults::getCallDependencyFrom returns identical call instructions without clobber in between using MemDepResult with its DepType to be Def. However, identical is too strict here and we want it to be relaxed a little to consider phi-translation -- callee is the same, param operands can be different. That means changing the semantic of MemDepResult::Def and I don't know the potential impact.

So currently the patch is still conservative to only handle MemDepResult::NonFuncLocal, which means the current call has no function local clobber. If there is clobber, even if the clobber doesn't stand in between the current call and the call with the new value, we won't do phi-translate.

[wmi]

Add the missing testcase.

[asbirlea]

Thank you for the patch and offline discussion. LGTM.

[xbolva00]

Probably good candidate for 9.0.1.

@hans

[hans]

In D67013#1659786, @xbolva00 wrote:

Probably good candidate for 9.0.1.

@hans

I've put it on my list. Thanks!

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

class ValueTable {
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
     uint32_t lookupOrAddCall(CallInst *C);
     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
                               uint32_t Num, GVN &Gvn);
+    bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
+                          const BasicBlock *PhiBlock, GVN &Gvn);
     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
 
   public:
     ValueTable();
     ValueTable(const ValueTable &Arg);
     ValueTable(ValueTable &&Arg);
     ~ValueTable();

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

uint32_t GVN::ValueTable::phiTranslate(const BasicBlock *Pred,
   auto FindRes = PhiTranslateTable.find({Num, Pred});
   if (FindRes != PhiTranslateTable.end())
     return FindRes->second;
   uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
   PhiTranslateTable.insert({{Num, Pred}, NewNum});
   return NewNum;
 }
 
+// Return true if the value number \p Num and NewNum have equal value.
+// Return false if the result is unknown.
+bool GVN::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
+                                       const BasicBlock *Pred,
+                                       const BasicBlock *PhiBlock, GVN &Gvn) {
+  CallInst *Call = nullptr;
+  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
+  while (Vals) {
+    Call = dyn_cast<CallInst>(Vals->Val);
+    if (Call && Call->getParent() == PhiBlock)
+      break;
+    Vals = Vals->Next;
+  }
+
+  if (AA->doesNotAccessMemory(Call))
+    return true;
+
+  if (!MD || !AA->onlyReadsMemory(Call))
+    return false;
+
+  MemDepResult local_dep = MD->getDependency(Call);
+  if (!local_dep.isNonLocal())
+    return false;
+
+  const MemoryDependenceResults::NonLocalDepInfo &deps =
+      MD->getNonLocalCallDependency(Call);
+
+  // Check to see if the Call has no function local clobber.
+  for (unsigned i = 0; i < deps.size(); i++) {
+    if (deps[i].getResult().isNonFuncLocal())
+      return true;
+  }
+  return false;
+}
+
 /// Translate value number \p Num using phis, so that it has the values of
 /// the phis in BB.
 uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
                                            const BasicBlock *PhiBlock,
                                            uint32_t Num, GVN &Gvn) {
   if (PHINode *PN = NumberingPhi[Num]) {
     for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
       if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
if (Exp.varargs[0] > Exp.varargs[1]) {
       uint32_t Opcode = Exp.opcode >> 8;
       if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
         Exp.opcode = (Opcode << 8) |
                      CmpInst::getSwappedPredicate(
                          static_cast<CmpInst::Predicate>(Exp.opcode & 255));
     }
   }
 
-  if (uint32_t NewNum = expressionNumbering[Exp])
+  if (uint32_t NewNum = expressionNumbering[Exp]) {
+    if (Exp.opcode == Instruction::Call && NewNum != Num)
+      return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
     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)) {

llvm/trunk/test/Transforms/GVN/pr42605.ll

+; RUN: opt -gvn %s -S | FileCheck %s
+; PR42605. Check phi-translate won't translate the value number of a call
+; to the value of another call with clobber in between.
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = dso_local local_unnamed_addr global i32 0, align 4
+@.str = private unnamed_addr constant [8 x i8] c"%d, %d\0A\00", align 1
+
+; Function Attrs: nofree nounwind
+declare dso_local i32 @printf(i8* nocapture readonly, ...) local_unnamed_addr
+
+; Function Attrs: noinline norecurse nounwind readonly uwtable
+define dso_local i32 @_Z3gooi(i32 %i) local_unnamed_addr #0 {
+entry:
+  %t0 = load i32, i32* @global, align 4, !tbaa !2
+  %add = add nsw i32 %t0, %i
+  ret i32 %add
+}
+
+; Function Attrs: nofree nounwind uwtable
+define dso_local void @noclobber() local_unnamed_addr {
+entry:
+  %call = tail call i32 @_Z3gooi(i32 2)
+  %add = add nsw i32 %call, 5
+  %cmp = icmp sgt i32 %add, 2
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call1 = tail call i32 @_Z3gooi(i32 3)
+  %add2 = add nsw i32 %call1, 5
+  br label %if.end
+
+; Check pre happens after phitranslate.
+; CHECK-LABEL: @noclobber
+; CHECK: %add4.pre-phi = phi i32 [ %add2, %if.then ], [ %add, %entry ]
+; CHECK: printf(i8* getelementptr inbounds {{.*}}, i32 %add4.pre-phi)
+
+if.end:                                           ; preds = %if.then, %entry
+  %i.0 = phi i32 [ 3, %if.then ], [ 2, %entry ]
+  %global2.0 = phi i32 [ %add2, %if.then ], [ %add, %entry ]
+  %call3 = tail call i32 @_Z3gooi(i32 %i.0)
+  %add4 = add nsw i32 %call3, 5
+  %call5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i32 %global2.0, i32 %add4)
+  ret void
+}
+
+; Function Attrs: nofree nounwind uwtable
+define dso_local void @hasclobber() local_unnamed_addr {
+entry:
+  %call = tail call i32 @_Z3gooi(i32 2)
+  %add = add nsw i32 %call, 5
+  %cmp = icmp sgt i32 %add, 2
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call1 = tail call i32 @_Z3gooi(i32 3)
+  %add2 = add nsw i32 %call1, 5
+  br label %if.end
+
+; Check no pre happens.
+; CHECK-LABEL: @hasclobber
+; CHECK: %call3 = tail call i32 @_Z3gooi(i32 %i.0)
+; CHECK-NEXT: %add4 = add nsw i32 %call3, 5
+; CHECK-NEXT: printf(i8* getelementptr inbounds ({{.*}}, i32 %global2.0, i32 %add4)
+
+if.end:                                           ; preds = %if.then, %entry
+  %i.0 = phi i32 [ 3, %if.then ], [ 2, %entry ]
+  %global2.0 = phi i32 [ %add2, %if.then ], [ %add, %entry ]
+  store i32 5, i32* @global, align 4, !tbaa !2
+  %call3 = tail call i32 @_Z3gooi(i32 %i.0)
+  %add4 = add nsw i32 %call3, 5
+  %call5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i32 %global2.0, i32 %add4)
+  ret void
+}
+
+attributes #0 = { noinline norecurse nounwind readonly uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 10.0.0 (trunk 369798)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}