[JumpThreading] Restrict PRE across instructions that don't pass control to successors

[mkazantsev]

Summary

PRE in JumpThreading should not be able to hoist copy of non-speculable loads across
instructions that don't always transfer execution to their successors, otherwise they may
introduce an unsafe load which otherwise would not be executed.

The same problem for GVN was fixed as rL316975.

[mkazantsev]

Ping.

[mkazantsev]

Guys, can anyone take a look? This is a fix for a miscompile which leads to functional bug.

[anna]

lgtm.

lib/Transforms/Scalar/JumpThreading.cpp

1337 ↗

(On Diff #123912)

Nit: s/We can only validly do it if/This is valid only if/

[anna]

This looks simple enough and similar to how we handle other optimizations in presence of guards (there were previous issues with JT around guards that were fixed with isGuaranteedToTransferExecutionToSuccessor as well).

Pls wait and see for a day or two if anyone has other comments.

[efriedma]

LGTM.

(It would be nice to add a testcase using "noalias" so it's obvious this isn't just a problem with llvm.experimental.guard().)

[mkazantsev]

Thanks! I will add more test cases in follow-up NFC.

[mkazantsev]

Comments addressed in merged patch (comment fixed & tests added).

[efriedma]

llvm/trunk/test/Transforms/JumpThreading/guards.ll

335

Did you mean to make this argument noalias?

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

bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
 
   // Okay, the loaded value is available in at least one (and maybe all!)
   // predecessors.  If the value is unavailable in more than one unique
   // predecessor, we want to insert a merge block for those common predecessors.
   // This ensures that we only have to insert one reload, thus not increasing
   // code size.
   BasicBlock *UnavailablePred = nullptr;
 
+  // If the value is unavailable in one of predecessors, we will end up
+  // inserting a new instruction into them. It is only valid if all the
+  // instructions before LI are guaranteed to pass execution to its successor,
+  // or if LI is safe to speculate.
+  // TODO: If this logic becomes more complex, and we will perform PRE insertion
+  // farther than to a predecessor, we need to reuse the code from GVN's PRE.
+  // It requires domination tree analysis, so for this simple case it is an
+  // overkill.
+  if (PredsScanned.size() != AvailablePreds.size() &&
+      !isSafeToSpeculativelyExecute(LI))
+    for (auto I = LoadBB->begin(); &*I != LI; ++I)
+      if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
+        return false;
+
   // If there is exactly one predecessor where the value is unavailable, the
   // already computed 'OneUnavailablePred' block is it.  If it ends in an
   // unconditional branch, we know that it isn't a critical edge.
   if (PredsScanned.size() == AvailablePreds.size()+1 &&
       OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
     UnavailablePred = OneUnavailablePred;
   } else if (PredsScanned.size() != AvailablePreds.size()) {
     // Otherwise, we had multiple unavailable predecessors or we had a critical

llvm/trunk/test/Transforms/JumpThreading/guards.ll

 L1:
   ret void
 L2:
   call void @f(i1 %cmp)
   ret void
 L3:
   ret void
 }
+
+; Make sure that we don't PRE a non-speculable load across a guard.
+define void @unsafe_pre_across_guard(i8* %p, i1 %load.is.valid) {
+
+; CHECK-LABEL: @unsafe_pre_across_guard(
+; CHECK-NOT:   loaded.pr
+; CHECK:       entry:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %load.is.valid) [ "deopt"() ]
+; CHECK-NEXT:    %loaded = load i8, i8* %p
+; CHECK-NEXT:    %continue = icmp eq i8 %loaded, 0
+; CHECK-NEXT:    br i1 %continue, label %exit, label %loop
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call void (i1, ...) @llvm.experimental.guard(i1 %load.is.valid) [ "deopt"() ]
+  %loaded = load i8, i8* %p
+  %continue = icmp eq i8 %loaded, 0
+  br i1 %continue, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; Make sure that we can safely PRE a speculable load across a guard.
+define void @safe_pre_across_guard(i8* noalias nocapture readonly dereferenceable(8) %p, i1 %load.is.valid) {
+
+; CHECK-LABEL: @safe_pre_across_guard(
+; CHECK:       entry:
+; CHECK-NEXT:    %loaded.pr = load i8, i8* %p
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %loaded = phi i8 [ %loaded, %loop ], [ %loaded.pr, %entry ]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %load.is.valid) [ "deopt"() ]
+; CHECK-NEXT:    %continue = icmp eq i8 %loaded, 0
+; CHECK-NEXT:    br i1 %continue, label %exit, label %loop
+
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call void (i1, ...) @llvm.experimental.guard(i1 %load.is.valid) [ "deopt"() ]
+  %loaded = load i8, i8* %p
+  %continue = icmp eq i8 %loaded, 0
+  br i1 %continue, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; Make sure that we don't PRE a non-speculable load across a call which may
+; alias with the load.
+define void @unsafe_pre_across_call(i8* %p) {
+
+; CHECK-LABEL: @unsafe_pre_across_call(
+; CHECK-NOT:   loaded.pr
+; CHECK:       entry:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    call i32 @f1()
+; CHECK-NEXT:    %loaded = load i8, i8* %p
+; CHECK-NEXT:    %continue = icmp eq i8 %loaded, 0
+; CHECK-NEXT:    br i1 %continue, label %exit, label %loop
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call i32 @f1()
+  %loaded = load i8, i8* %p
+  %continue = icmp eq i8 %loaded, 0
+  br i1 %continue, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+; Make sure that we can safely PRE a speculable load across a call.
+define void @safe_pre_across_call(i8* noalias nocapture readonly dereferenceable(8) %p) {
+
+; CHECK-LABEL: @safe_pre_across_call(
+; CHECK:       entry:
+; CHECK-NEXT:    %loaded.pr = load i8, i8* %p
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %loaded = phi i8 [ %loaded, %loop ], [ %loaded.pr, %entry ]
+; CHECK-NEXT:    call i32 @f1()
+; CHECK-NEXT:    %continue = icmp eq i8 %loaded, 0
+; CHECK-NEXT:    br i1 %continue, label %exit, label %loop
+
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call i32 @f1()
+  %loaded = load i8, i8* %p
+  %continue = icmp eq i8 %loaded, 0
+  br i1 %continue, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}