[GVN LoadPRE] Extend the scope of optimization by using context to prove safety of speculation

[skatkov]

Summary

Use context to prove that load can be safely executed at a point where load is being hoisted.

Postpone the decision about safety of speculative load execution till the moment we know
where we hoist load and check safety at that context.

[lebedev.ri]

llvm/test/Transforms/GVN/loadpre-context.ll

1

Precommit please

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

1248

Why is that needed? We split critical edges right below. As far as I understand, we will insert loads into newly created split blocks which is safe.

[skatkov]

llvm/lib/Transforms/Scalar/GVN.cpp

1248

Imaging that we have a guard for null check in load's basic block and we plan to skip it (speculate). If we hoist load over this guard we can end up with a load from null address. This is not correct. We must ensure that on end of spilt block == entry to our basic block address can be proved a non-null.

[skatkov]

test is precomitted.

[reames]

LGTM w/minor fixes.

llvm/lib/Transforms/Scalar/GVN.cpp

1171–1172

Use "|=" please.

llvm/test/Transforms/GVN/loadpre-context.ll

4

"address" not "adress". Consistent spelling mistake in file, please fix.

98

I think your comment is missing some punctuation. This reads very oddly, reword please.

151

Please rename this to something like ro_foo. i.e. make the name explicit about being read only.

Alternatively, use the readnone attribute on the call instruction, not the decl.

Otherwise, you confuse the reader because it looks like you're hoisting a load past a mutating call. I had a comment all written before thinking to check the declaration. :)

[lebedev.ri]

Seems fine to me overall.

llvm/lib/Transforms/Scalar/GVN.cpp

1152–1154

This variable name doesn't parse for me.
Perhaps something like MustEnsureSafetyOfSpeculativeExecutetion

[skatkov]

llvm/lib/Transforms/Scalar/GVN.cpp

1171–1172

I do not need to execute ICF->hasICF(TmpBB) if I know that I need safe speculation already.

gives me exactly this wil

= will force the redundant execution of ICF->hasICF(TmpBB).

[skatkov]

Handled comments. Will wait for a day to give a chance for Roman, Philip and Max to take a look one more time.

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
                                         UnavailableBlocks.end());
 
   // Let's find the first basic block with more than one predecessor.  Walk
   // backwards through predecessors if needed.
   BasicBlock *LoadBB = LI->getParent();
   BasicBlock *TmpBB = LoadBB;
-  bool IsSafeToSpeculativelyExecute = isSafeToSpeculativelyExecute(LI);
 
   // Check that there is no implicit control flow instructions above our load in
   // its block. If there is an instruction that doesn't always pass the
   // execution to the following instruction, then moving through it may become
   // invalid. For example:
   //
   // int arr[LEN];
   // int index = ???;
   // ...
   // guard(0 <= index && index < LEN);
   // use(arr[index]);
   //
   // It is illegal to move the array access to any point above the guard,
   // because if the index is out of bounds we should deoptimize rather than
   // access the array.
   // Check that there is no guard in this block above our instruction.
-  if (!IsSafeToSpeculativelyExecute && ICF->isDominatedByICFIFromSameBlock(LI))
-    return false;
+  bool MustEnsureSafetyOfSpeculativeExecution =
+      ICF->isDominatedByICFIFromSameBlock(LI);
+
   while (TmpBB->getSinglePredecessor()) {
     TmpBB = TmpBB->getSinglePredecessor();
     if (TmpBB == LoadBB) // Infinite (unreachable) loop.
       return false;
     if (Blockers.count(TmpBB))
       return false;
 
     // If any of these blocks has more than one successor (i.e. if the edge we
     // just traversed was critical), then there are other paths through this
     // block along which the load may not be anticipated.  Hoisting the load
     // above this block would be adding the load to execution paths along
     // which it was not previously executed.
     if (TmpBB->getTerminator()->getNumSuccessors() != 1)
       return false;
 
     // Check that there is no implicit control flow in a block above.
-    if (!IsSafeToSpeculativelyExecute && ICF->hasICF(TmpBB))
-      return false;
+    MustEnsureSafetyOfSpeculativeExecution =
+        MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
   }
 
   assert(TmpBB);
   LoadBB = TmpBB;
 
   // Check to see how many predecessors have the loaded value fully
   // available.
   MapVector<BasicBlock *, Value *> PredLoads;
bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   // If this load is unavailable in multiple predecessors, reject it.
   // FIXME: If we could restructure the CFG, we could make a common pred with
   // all the preds that don't have an available LI and insert a new load into
   // that one block.
   if (NumUnavailablePreds != 1)
       return false;
 
+  // Now we know where we will insert load. We must ensure that it is safe
+  // to speculatively execute the load at that points.
+  if (MustEnsureSafetyOfSpeculativeExecution) {
+    if (CriticalEdgePred.size())
+      if (!isSafeToSpeculativelyExecute(LI, LoadBB->getFirstNonPHI(), DT))
+        return false;
+    for (auto &PL : PredLoads)
+      if (!isSafeToSpeculativelyExecute(LI, PL.first->getTerminator(), DT))
+        return false;
+  }
+
   // Split critical edges, and update the unavailable predecessors accordingly.
   for (BasicBlock *OrigPred : CriticalEdgePred) {
     BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
     assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
     PredLoads[NewPred] = nullptr;
     LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
                       << LoadBB->getName() << '\n');
   }

llvm/test/Transforms/GVN/loadpre-context.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -gvn --basic-aa -S | FileCheck %s
 
-; load may be speculated, adress is not null using context search.
+; load may be speculated, address is not null using context search.
 ; There is a critical edge.
 define i32 @loadpre_critical_edge(i32* align 8 dereferenceable_or_null(48) %arg, i32 %N) {
 ; CHECK-LABEL: @loadpre_critical_edge(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[ARG:%.*]], null
-; CHECK-NEXT:    br i1 [[CMP]], label [[NULL_EXIT:%.*]], label [[HEADER:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[NULL_EXIT:%.*]], label [[ENTRY_HEADER_CRIT_EDGE:%.*]]
+; CHECK:       entry.header_crit_edge:
+; CHECK-NEXT:    [[V_PRE:%.*]] = load i32, i32* [[ARG]], align 4
+; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @foo(i32 [[IV]])
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[ARG]], align 4
-; CHECK-NEXT:    [[SUM:%.*]] = add i32 [[NEW_V]], [[V]]
+; CHECK-NEXT:    [[V:%.*]] = phi i32 [ [[V_PRE]], [[ENTRY_HEADER_CRIT_EDGE]] ], [ [[SUM:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY_HEADER_CRIT_EDGE]] ], [ [[IV_NEXT:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @ro_foo(i32 [[IV]])
+; CHECK-NEXT:    [[SUM]] = add i32 [[NEW_V]], [[V]]
 ; CHECK-NEXT:    store i32 [[SUM]], i32* [[ARG]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[SUM]]
 ; CHECK:       null_exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %cmp = icmp eq i32* %arg, null
   br i1 %cmp, label %null_exit, label %header
 
 header:
   %iv = phi i32 [0, %entry], [%iv.next, %header]
-  %new_v = call i32 @foo(i32 %iv)
+; Call prevents to move load over due to it does not guarantee to return.
+  %new_v = call i32 @ro_foo(i32 %iv) readnone
   %v = load i32, i32* %arg
   %sum = add i32 %new_v, %v
   store i32 %sum, i32* %arg
   %iv.next = add i32 %iv, 1
   %cond = icmp eq i32 %iv.next, %N
   br i1 %cond, label %exit, label %header
 
 exit:
   ret i32 %sum
 
 null_exit:
   ret i32 0
 }
 
-; load may be speculated, adress is not null using context search.
+; load may be speculated, address is not null using context search.
 define i32 @loadpre_basic(i32* align 8 dereferenceable_or_null(48) %arg, i32 %N) {
 ; CHECK-LABEL: @loadpre_basic(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[ARG:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NULL_EXIT:%.*]], label [[PREHEADER:%.*]]
 ; CHECK:       preheader:
+; CHECK-NEXT:    [[V_PRE:%.*]] = load i32, i32* [[ARG]], align 4
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
+; CHECK-NEXT:    [[V:%.*]] = phi i32 [ [[V_PRE]], [[PREHEADER]] ], [ [[SUM:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @foo(i32 [[IV]])
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[ARG]], align 4
-; CHECK-NEXT:    [[SUM:%.*]] = add i32 [[NEW_V]], [[V]]
+; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @ro_foo(i32 [[IV]])
+; CHECK-NEXT:    [[SUM]] = add i32 [[NEW_V]], [[V]]
 ; CHECK-NEXT:    store i32 [[SUM]], i32* [[ARG]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[SUM]]
 ; CHECK:       null_exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %cmp = icmp eq i32* %arg, null
   br i1 %cmp, label %null_exit, label %preheader
 
 preheader:
   br label %header
 
 header:
   %iv = phi i32 [0, %preheader], [%iv.next, %header]
-  %new_v = call i32 @foo(i32 %iv)
+; Call prevents to move load over due to it does not guarantee to return.
+  %new_v = call i32 @ro_foo(i32 %iv) readnone
   %v = load i32, i32* %arg
   %sum = add i32 %new_v, %v
   store i32 %sum, i32* %arg
   %iv.next = add i32 %iv, 1
   %cond = icmp eq i32 %iv.next, %N
   br i1 %cond, label %exit, label %header
 
 exit:
   ret i32 %sum
 
 null_exit:
   ret i32 0
 }
 
-; load cannot be speculated, adress is not null check does not dominate the loop.
+; load cannot be speculated, check "address is not null" does not dominate the loop.
 define i32 @loadpre_maybe_null(i32* align 8 dereferenceable_or_null(48) %arg, i32 %N, i1 %c) {
 ; CHECK-LABEL: @loadpre_maybe_null(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[NULL_CHECK:%.*]], label [[PREHEADER:%.*]]
 ; CHECK:       null_check:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32* [[ARG:%.*]], null
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NULL_EXIT:%.*]], label [[PREHEADER]]
 ; CHECK:       preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @foo(i32 [[IV]])
+; CHECK-NEXT:    [[NEW_V:%.*]] = call i32 @ro_foo(i32 [[IV]])
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[ARG]], align 4
 ; CHECK-NEXT:    [[SUM:%.*]] = add i32 [[NEW_V]], [[V]]
 ; CHECK-NEXT:    store i32 [[SUM]], i32* [[ARG]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[SUM]]
 ; CHECK:       null_exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br i1 %c, label %null_check, label %preheader
 
 null_check:
   %cmp = icmp eq i32* %arg, null
   br i1 %cmp, label %null_exit, label %preheader
 
 preheader:
   br label %header
 
 header:
   %iv = phi i32 [0, %preheader], [%iv.next, %header]
-  %new_v = call i32 @foo(i32 %iv)
+; Call prevents to move load over due to it does not guarantee to return.
+  %new_v = call i32 @ro_foo(i32 %iv) readnone
   %v = load i32, i32* %arg
   %sum = add i32 %new_v, %v
   store i32 %sum, i32* %arg
   %iv.next = add i32 %iv, 1
   %cond = icmp eq i32 %iv.next, %N
   br i1 %cond, label %exit, label %header
 
 exit:
   ret i32 %sum
 
 null_exit:
   ret i32 0
 }
 
 ; Does not guarantee that returns.
-declare i32 @foo(i32) readnone
+declare i32 @ro_foo(i32) readnone