Merging r370547:

------------------------------------------------------------------------
r370547 | wmi | 2019-08-30 16:01:22 -0700 (Fri, 30 Aug 2019) | 24 lines

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

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.

Differential Revision: https://reviews.llvm.org/D67013

------------------------------------------------------------------------

3 files changed, 128 insertions, 1 deletions

diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h
index 9fe00a9..5a3d6ac 100644
--- a/llvm/include/llvm/Transforms/Scalar/GVN.h
+++ b/llvm/include/llvm/Transforms/Scalar/GVN.h
@@ -120,6 +120,8 @@ public:
     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);
 
diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index 1a02e9d..542d3b3 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1522,6 +1522,41 @@ uint32_t GVN::ValueTable::phiTranslate(const BasicBlock *Pred,
   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,
@@ -1568,8 +1603,11 @@ uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
     }
   }
 
-  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;
 }
 
diff --git a/llvm/test/Transforms/GVN/pr42605.ll b/llvm/test/Transforms/GVN/pr42605.ll
new file mode 100644
index 0000000..542f6f9
--- /dev/null
+++ b/llvm/test/Transforms/GVN/pr42605.ll
@@ -0,0 +1,87 @@
+; 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"}