[NewGVN] FIx phi-of-ops in the presence of memory read operations

[nlopes]

Summary

The phi-of-ops functionality has a function OpIsSafeForPHIOfOps to determine when it's safe to create the new phi. But this function only checks for the obvious dominator conditions and ignores memory.
This patch takes the conservative approach and disables phi-of-ops whenever there's a load that doesn't dominate the phi, as its value may be affected by a store inside the loop.

This can be improved later to check aliasing between the load/stores. I've added a few tests that show the missed cases.

fixes https://github.com/llvm/llvm-project/issues/53277

[asbirlea]

Thank you for sending this fix!
It feels like a pretty big hammer, but some of the tests being modified here are exact examples of the miscompile I was seeing. I'm good with it at this point.

llvm/lib/Transforms/Scalar/NewGVN.cpp

bool NewGVN::OpIsSafeForPHIOfOpsHelper(
   }
   // PHI in the same block.
   if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) {
     OpSafeForPHIOfOps.insert({V, false});
     return false;
   }
 
   auto *OrigI = cast<Instruction>(V);
+  // When we hit an instruction that reads memory (load, call, etc), we must
+  // consider any store that may happen in the loop. For now, we assume the
+  // worst: there is a store in the loop that alias with this read.
+  // The case where the load is outside the loop is already covered by the
+  // dominator check above.
+  // TODO: relax this condition
+  if (OrigI->mayReadFromMemory())
+    return false;
+
   for (auto *Op : OrigI->operand_values()) {
     if (!isa<Instruction>(Op))
       continue;
     // Stop now if we find an unsafe operand.
     auto OISIt = OpSafeForPHIOfOps.find(OrigI);
     if (OISIt != OpSafeForPHIOfOps.end()) {
       if (!OISIt->second) {
         OpSafeForPHIOfOps.insert({V, false});

llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=newgvn -enable-phi-of-ops=true -S -o - %s | FileCheck %s
 
-define void @store-in-loop(i8* %p, i8* %q) {
-; CHECK-LABEL: @store-in-loop(
+define void @hoisted-load(i8* %p, i8* %q) {
+; CHECK-LABEL: @hoisted-load(
 ; CHECK-NEXT:  bb56:
+; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
 ; CHECK-NEXT:    br label [[BB57:%.*]]
 ; CHECK:       bb57:
 ; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ]
 ; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ]
 ; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ]
-; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
 ; CHECK-NEXT:    [[N62]] = icmp ne i8 [[N60]], 2
 ; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]]
 ; CHECK:       bb229:
 ; CHECK-NEXT:    [[INC]] = add i8 [[IDX]], 1
 ; CHECK-NEXT:    store i8 [[INC]], i8* [[Q:%.*]], align 1
 ; CHECK-NEXT:    br label [[BB57]]
 ; CHECK:       bb237:
 ; CHECK-NEXT:    ret void
 ;
 bb56:
+  %n60 = load i8, i8* %p
+  br label %bb57
+
+bb57:
+  %n59 = phi i1 [ false, %bb229 ], [ true, %bb56 ]
+  %idx = phi i8 [0, %bb56], [%inc, %bb229]
+  %n62 = icmp ne i8 %n60, 2
+  %n63 = or i1 %n59, %n62
+  br i1 %n63, label %bb229, label %bb237
+
+bb229:
+  %inc = add i8 %idx, 1
+  store i8 %inc, i8* %q
+  br label %bb57
+
+bb237:
+  ret void
+}
+
+define void @store-in-loop(i8* %p, i8* %q) {
+; CHECK-LABEL: @store-in-loop(
+; CHECK-NEXT:  bb56:
+; CHECK-NEXT:    br label [[BB57:%.*]]
+; CHECK:       bb57:
+; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ]
+; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
+; CHECK-NEXT:    [[N62:%.*]] = icmp ne i8 [[N60]], 2
+; CHECK-NEXT:    [[N63:%.*]] = or i1 [[N59]], [[N62]]
+; CHECK-NEXT:    br i1 [[N63]], label [[BB229]], label [[BB237:%.*]]
+; CHECK:       bb229:
+; CHECK-NEXT:    [[INC]] = add i8 [[IDX]], 1
+; CHECK-NEXT:    store i8 [[INC]], i8* [[Q:%.*]], align 1
+; CHECK-NEXT:    br label [[BB57]]
+; CHECK:       bb237:
+; CHECK-NEXT:    ret void
+;
+bb56:
   br label %bb57
 
 bb57:
   %n59 = phi i1 [ false, %bb229 ], [ true, %bb56 ]
   %idx = phi i8 [0, %bb56], [%inc, %bb229]
   %n60 = load i8, i8* %p
   %n62 = icmp ne i8 %n60, 2
   %n63 = or i1 %n59, %n62
   br i1 %n63, label %bb229, label %bb237
 
 bb229:
   %inc = add i8 %idx, 1
   store i8 %inc, i8* %q
   br label %bb57
 
 bb237:
   ret void
 }
 
+; TODO: we should support this case
 define void @no-alias-store-in-loop(i8* noalias %p, i8* noalias %q) {
 ; CHECK-LABEL: @no-alias-store-in-loop(
 ; CHECK-NEXT:  bb56:
 ; CHECK-NEXT:    br label [[BB57:%.*]]
 ; CHECK:       bb57:
-; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ]
-; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ]
+; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ]
 ; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ]
 ; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
-; CHECK-NEXT:    [[N62]] = icmp ne i8 [[N60]], 2
-; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]]
+; CHECK-NEXT:    [[N62:%.*]] = icmp ne i8 [[N60]], 2
+; CHECK-NEXT:    [[N63:%.*]] = or i1 [[N59]], [[N62]]
+; CHECK-NEXT:    br i1 [[N63]], label [[BB229]], label [[BB237:%.*]]
 ; CHECK:       bb229:
 ; CHECK-NEXT:    [[INC]] = add i8 [[IDX]], 1
 ; CHECK-NEXT:    store i8 [[INC]], i8* [[Q:%.*]], align 1
 ; CHECK-NEXT:    br label [[BB57]]
 ; CHECK:       bb237:
 ; CHECK-NEXT:    ret void
 ;
 bb56:
bb237:
   ret void
 }
 
 define void @function-in-loop(i8* %p) {
 ; CHECK-LABEL: @function-in-loop(
 ; CHECK-NEXT:  bb56:
 ; CHECK-NEXT:    br label [[BB57:%.*]]
 ; CHECK:       bb57:
-; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ]
-; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ]
+; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ]
 ; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
-; CHECK-NEXT:    [[N62]] = icmp ne i8 [[N60]], 2
-; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]]
+; CHECK-NEXT:    [[N62:%.*]] = icmp ne i8 [[N60]], 2
+; CHECK-NEXT:    [[N63:%.*]] = or i1 [[N59]], [[N62]]
+; CHECK-NEXT:    br i1 [[N63]], label [[BB229]], label [[BB237:%.*]]
 ; CHECK:       bb229:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    br label [[BB57]]
 ; CHECK:       bb237:
 ; CHECK-NEXT:    ret void
 ;
 bb56:
   br label %bb57
 
 bb57:
   %n59 = phi i1 [ false, %bb229 ], [ true, %bb56 ]
   %n60 = load i8, i8* %p
   %n62 = icmp ne i8 %n60, 2
   %n63 = or i1 %n59, %n62
   br i1 %n63, label %bb229, label %bb237
 
 bb229:
   call void @f()
   br label %bb57
 
 bb237:
   ret void
 }
 
+; TODO: we should support this case
 define void @nowrite-function-in-loop(i8* %p) {
 ; CHECK-LABEL: @nowrite-function-in-loop(
 ; CHECK-NEXT:  bb56:
 ; CHECK-NEXT:    br label [[BB57:%.*]]
 ; CHECK:       bb57:
-; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ]
-; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ]
+; CHECK-NEXT:    [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ]
 ; CHECK-NEXT:    [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1
-; CHECK-NEXT:    [[N62]] = icmp ne i8 [[N60]], 2
-; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]]
+; CHECK-NEXT:    [[N62:%.*]] = icmp ne i8 [[N60]], 2
+; CHECK-NEXT:    [[N63:%.*]] = or i1 [[N59]], [[N62]]
+; CHECK-NEXT:    br i1 [[N63]], label [[BB229]], label [[BB237:%.*]]
 ; CHECK:       bb229:
 ; CHECK-NEXT:    call void @f() #[[ATTR0:[0-9]+]]
 ; CHECK-NEXT:    br label [[BB57]]
 ; CHECK:       bb237:
 ; CHECK-NEXT:    ret void
 ;
 bb56:
   br label %bb57

llvm/test/Transforms/NewGVN/storeoverstore.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -newgvn -enable-phi-of-ops=true -S < %s | FileCheck %s
 ; RUN: opt -passes=newgvn -enable-phi-of-ops=true -S -o - %s | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ;; All the loads in this testcase are useless, but it requires understanding that repeated
 ;; stores of the same value do not change the memory state to eliminate them.
 
 define i32 @foo(i32*, i32)  {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:    store i32 5, i32* [[TMP0:%.*]], align 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
-; CHECK:         br label [[TMP5]]
-; CHECK:         [[PHIOFOPS:%.*]] = phi i32 [ 10, [[TMP2:%.*]] ], [ 15, [[TMP4]] ]
-; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2]] ]
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP7:%.*]]
-; CHECK:         br label [[TMP7]]
-; CHECK:         [[DOT1:%.*]] = phi i32 [ [[PHIOFOPS]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ]
+; CHECK:       4:
+; CHECK-NEXT:    br label [[TMP5]]
+; CHECK:       5:
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP8:%.*]]
+; CHECK:       6:
+; CHECK-NEXT:    [[TMP7:%.*]] = add nsw i32 [[DOT0]], 5
+; CHECK-NEXT:    br label [[TMP8]]
+; CHECK:       8:
+; CHECK-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP7]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ]
 ; CHECK-NEXT:    ret i32 [[DOT1]]
 ;
   store i32 5, i32* %0, align 4
   %3 = icmp ne i32 %1, 0
   br i1 %3, label %4, label %7
 
 ; <label>:4:                                      ; preds = %2
   %5 = load i32, i32* %0, align 4

 
 ;; This is similar to the above, but it is a conditional store of the same value
 ;; which requires value numbering MemoryPhi properly to resolve.
 define i32 @foo2(i32*, i32)  {
 ; CHECK-LABEL: @foo2(
 ; CHECK-NEXT:    store i32 5, i32* [[TMP0:%.*]], align 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
-; CHECK:         br label [[TMP6:%.*]]
-; CHECK:         br label [[TMP6]]
-; CHECK:         [[PHIOFOPS:%.*]] = phi i32 [ 10, [[TMP5]] ], [ 15, [[TMP4]] ]
+; CHECK:       4:
+; CHECK-NEXT:    br label [[TMP6:%.*]]
+; CHECK:       5:
+; CHECK-NEXT:    br label [[TMP6]]
+; CHECK:       6:
 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP5]] ]
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP8:%.*]]
-; CHECK:         br label [[TMP8]]
-; CHECK:         [[DOT1:%.*]] = phi i32 [ [[PHIOFOPS]], [[TMP7]] ], [ [[DOT0]], [[TMP6]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP9:%.*]]
+; CHECK:       7:
+; CHECK-NEXT:    [[TMP8:%.*]] = add nsw i32 [[DOT0]], 5
+; CHECK-NEXT:    br label [[TMP9]]
+; CHECK:       9:
+; CHECK-NEXT:    [[DOT1:%.*]] = phi i32 [ [[TMP8]], [[TMP7]] ], [ [[DOT0]], [[TMP6]] ]
 ; CHECK-NEXT:    ret i32 [[DOT1]]
 ;
   store i32 5, i32* %0, align 4
   %3 = icmp ne i32 %1, 0
   br i1 %3, label %4, label %7
 
 ; <label>:4:                                      ; preds = %2
   %5 = load i32, i32* %0, align 4