PR46874: Reset stack after visiting a node

[hiraditya]

Summary

When the stack is not reset it keeps previously visited Basic Block which results in bugs where an instruction is hoisted to a predecessor where the instruction
was not fully anticipable.

[hiraditya]

Rebase

[hiraditya]

clang-format

[sebpop]

Looks good to me.

[hiraditya]

PR: https://bugs.llvm.org/show_bug.cgi?id=46874

llvm/lib/Transforms/Scalar/GVNHoist.cpp

private:
   using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;
 
   // Push all the VNs corresponding to BB into RenameStack.
   void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
                        RenameStackType &RenameStack) {
     auto it1 = ValueBBs.find(BB);
     if (it1 != ValueBBs.end()) {
       // Iterate in reverse order to keep lower ranked values on the top.
+      LLVM_DEBUG(dbgs() << "\nVisiting: " <<  BB->getName()
+                        << " for pushing instructions on stack";);
       for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
         // Get the value of instruction I
         LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
         RenameStack[VI.first].push_back(VI.second);
       }
     }
   }
 
private:
   // store the last value you see. When you hit a CHI from a given edge, the
   // value to use as the argument is at the top of the stack, add the value to
   // CHI and pop.
   void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
     auto Root = PDT->getNode(nullptr);
     if (!Root)
       return;
     // Depth first walk on PDom tree to fill the CHIargs at each PDF.
-    RenameStackType RenameStack;
     for (auto Node : depth_first(Root)) {
       BasicBlock *BB = Node->getBlock();
       if (!BB)
         continue;
 
+      RenameStackType RenameStack;
       // Collect all values in BB and push to stack.
       fillRenameStack(BB, ValueBBs, RenameStack);
 
       // Fill outgoing values in each CHI corresponding to BB.
       fillChiArgs(BB, CHIBBs, RenameStack);
     }
   }
 

llvm/test/Transforms/GVNHoist/hoist-pr46874.ll

+; RUN: opt -gvn-hoist -S < %s | FileCheck %s
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@input = local_unnamed_addr global i32* null, align 8
+
+; Check that the load instruction is **not** hoisted
+; CHECK-LABEL: @_Z3fooPii
+; CHECK-LABEL: if.then:
+; CHECK-NEXT: load
+; CHECK-LABEL: if2:
+; CHECK: load
+; CHECK-LABEL: @main
+
+define i32 @_Z3fooPii(i32* %p, i32 %x) local_unnamed_addr  {
+entry:
+  %cmp.not = icmp eq i32* %p, null
+  br i1 %cmp.not, label %if.end3, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32, i32* %p, align 4, !tbaa !3
+  %add = add nsw i32 %0, %x
+  %cmp1 = icmp eq i32 %add, 4
+  br i1 %cmp1, label %if2, label %if.end3
+
+if.end3:                                          ; preds = %entry, %if.then
+  %x.addr.0 = phi i32 [ %add, %if.then ], [ %x, %entry ]
+  %add4 = add nsw i32 %x.addr.0, 2
+  br i1 %cmp.not, label %if.end11, label %if2
+
+if2:                                              ; preds = %if.end3, %if.then
+  %x.addr.1 = phi i32 [ 4, %if.then ], [ %x.addr.0, %if.end3 ]
+  %y.0 = phi i32 [ 2, %if.then ], [ %add4, %if.end3 ]
+  %1 = load i32, i32* %p, align 4, !tbaa !3
+  %add7 = add nsw i32 %x.addr.1, %1
+  %cmp8 = icmp eq i32 %add7, 5
+  br i1 %cmp8, label %end, label %if.end11
+
+if.end11:                                         ; preds = %if.end3, %if2
+  %x.addr.2 = phi i32 [ %add7, %if2 ], [ %x.addr.0, %if.end3 ]
+  %y.1 = phi i32 [ %y.0, %if2 ], [ %add4, %if.end3 ]
+  %add12 = add nsw i32 %y.1, %x.addr.2
+  br label %end
+
+end:                                              ; preds = %if2, %if.end11
+  %x.addr.3 = phi i32 [ 5, %if2 ], [ %x.addr.2, %if.end11 ]
+  %y.2 = phi i32 [ %y.0, %if2 ], [ %add12, %if.end11 ]
+  %add13 = add nsw i32 %x.addr.3, %y.2
+  ret i32 %add13
+}
+
+define i32 @main() local_unnamed_addr  {
+entry:
+  %0 = load i32*, i32** @input, align 8, !tbaa !7
+  %call = call i32 @_Z3fooPii(i32* %0, i32 0)
+  ret i32 %call
+}
+
+
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C++ TBAA"}
+!7 = !{!8, !8, i64 0}
+!8 = !{!"pointer@_ZTSPi", !5, i64 0}

llvm/test/Transforms/GVNHoist/pr37445.ll

 ; RUN: opt < %s -early-cse-memssa -gvn-hoist -S | FileCheck %s
 
 ; Make sure opt won't crash and that this pair of
-; instructions (load, icmp) is hoisted successfully
-; from bb45 and bb58 to bb41.
+; instructions (load, icmp) are not hoisted.
+; Although it is safe to hoist the loads from bb45 to
+; bb41, gvn-hoist does not have appropriate mechanism
+; to handle corner cases (see PR46874) when these instructions
+; were hoisted.
+; FIXME: Hoist loads from bb58 and bb45 to bb41.
 
 @g_10 = external global i32, align 4
 @g_536 = external global i8*, align 8
 @g_1629 = external global i32**, align 8
 @g_963 = external global i32**, align 8
 @g_1276 = external global i32**, align 8
 
 ;CHECK-LABEL: @func_22
safe_div_func_uint8_t_u_u.exit:
   br i1 %tmp35, label %bb36, label %bb41
 
 bb36:
   %tmp38 = sext i32 %tmp3.0 to i64
   %tmp40 = trunc i64 %tmp38 to i32
   br label %bb12
 
 ;CHECK: bb41:
-;CHECK:   %tmp47 = load i32, i32* %arg1, align 4
-;CHECK:   %tmp48 = icmp eq i32 %tmp47, 0
 
 bb41:
   %tmp43 = load i32, i32* %arg, align 4
   %tmp44 = icmp eq i32 %tmp43, 0
   br i1 %tmp44, label %bb52, label %bb45
 
 ;CHECK:     bb45:
-;CHECK-NOT:   %tmp47 = load i32, i32* %arg1, align 4
-;CHECK-NOT:   %tmp48 = icmp eq i32 %tmp47, 0
+;CHECK:   %tmp47 = load i32, i32* %arg1, align 4
+;CHECK:   %tmp48 = icmp eq i32 %tmp47, 0
 
 bb45:
   %tmp47 = load i32, i32* %arg1, align 4
   %tmp48 = icmp eq i32 %tmp47, 0
   br i1 %tmp48, label %bb50, label %bb64
 
 bb50:
   %tmp51 = load volatile i32**, i32*** @g_963, align 8
   unreachable
 
 bb52:
   %tmp8.0 = phi i32 [ undef, %bb41 ], [ %tmp57, %bb55 ]
   %tmp54 = icmp slt i32 %tmp8.0, 3
   br i1 %tmp54, label %bb55, label %bb58
 
 bb55:
   %tmp57 = add nsw i32 %tmp8.0, 1
   br label %bb52
 
-;CHECK:     bb58:
-;CHECK-NOT:   %tmp60 = load i32, i32* %arg1, align 4
-;CHECK-NOT:   %tmp61 = icmp eq i32 %tmp60, 0
+;CHECK: bb58:
+;CHECK: %tmp60 = load i32, i32* %arg1, align 4
+;CHECK: %tmp61 = icmp eq i32 %tmp60, 0
+;CHECK: bb62:
+;CHECK: load
+;CHECK: bb64:
+;CHECK: load
 
 bb58:
   %tmp60 = load i32, i32* %arg1, align 4
   %tmp61 = icmp eq i32 %tmp60, 0
   br i1 %tmp61, label %bb62, label %bb64
 
 bb62:
   %tmp63 = load volatile i32**, i32*** @g_1276, align 8