[JumpThreading] Dont RAUW condition incorrectly

[anna]

Summary

We have a bug when RAUWing the condition if experimental.guard or assumes is a use of that
condition. This is because LazyValueInfo may have used the guards/assumes to identify the
value of the condition. We cannot use circular logic and apply the value back to
the guard/assume and change
the behaviour of the guard/assume.
For now, disable RAUW for conditions and fix the logic as a next
step: https://reviews.llvm.org/D33257

[anna]

test/Transforms/JumpThreading/assume.ll

61 ↗

(On Diff #99299)

I took this test case from Philip's patch: https://reviews.llvm.org/D28276.

I think this test case proves an important point: we *can never* use circular logic to fold assume, because there is no way of knowing whether control unconditionally reaches assume, i.e. the function may never be called.

So, we don't need something like the one below, although this makes it much clearer that it's illegal to fold the assume.

%notnull = icmp ne i32* %array, null
call exit()
llvm.assume(i1 %notnull)
br i1 %notnull, label %normal, label %error

[reames]

lib/Transforms/Scalar/JumpThreading.cpp

838 ↗

(On Diff #99299)

Er, I don't see why this is a circular logic bug? I though the problem was that we were using a fact from the end of the block to reason about uses of the value before the assume/guard?

[anna]

updated comments and added test to show that this is more than a circular logic bug.

[anna]

lib/Transforms/Scalar/JumpThreading.cpp

838 ↗

(On Diff #99299)

Yes. Bad phrasing on my part. This is *more* than a circular logic bug. I've updated the comment and add test cases to reflect that.

[anna]

While working on the actual fix for this, I realized the test comments for assumes need to be updated.
Specifically, the semantics for assume according to langref:

The intrinsic allows the optimizer to assume that the provided condition is always true whenever the control flow reaches the intrinsic call.

So, we *can* fold the assume and uses after the assume. What we cannot fold are uses *before* the assume.

[anna]

Updated the assume test cases.

[reames]

LGTM

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

if (CondBr && CondConst) {
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
         unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
         CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
         BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
         CondBr->eraseFromParent();
         if (CondCmp->use_empty())
           CondCmp->eraseFromParent();
-        else if (CondCmp->getParent() == BB) {
-          // If the fact we just learned is true for all uses of the
-          // condition, replace it with a constant value
-          auto *CI = Ret == LazyValueInfo::True ?
-            ConstantInt::getTrue(CondCmp->getType()) :
-            ConstantInt::getFalse(CondCmp->getType());
-          CondCmp->replaceAllUsesWith(CI);
-          CondCmp->eraseFromParent();
-        }
+        // TODO: We can safely replace *some* uses of the CondInst if it has
+        // exactly one value as returned by LVI. RAUW is incorrect in the
+        // presence of guards and assumes, that have the `Cond` as the use. This
+        // is because we use the guards/assume to reason about the `Cond` value
+        // at the end of block, but RAUW unconditionally replaces all uses
+        // including the guards/assumes themselves and the uses before the
+        // guard/assume.
         return true;
       }
 
       // We did not manage to simplify this branch, try to see whether
       // CondCmp depends on a known phi-select pattern.
       if (TryToUnfoldSelect(CondCmp, BB))
         return true;
     }
if (PredWithKnownDest ==
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
-        else if (OnlyVal && OnlyVal != MultipleVal &&
-                 CondInst->getParent() == BB) {
-          // If we just learned Cond is the same value for all uses of the
-          // condition, replace it with a constant value
-          CondInst->replaceAllUsesWith(OnlyVal);
-          if (!CondInst->mayHaveSideEffects())
-            CondInst->eraseFromParent();
-        }
+        // TODO: We can safely replace *some* uses of the CondInst if it has
+        // exactly one value as returned by LVI. RAUW is incorrect in the
+        // presence of guards and assumes, that have the `Cond` as the use. This
+        // is because we use the guards/assume to reason about the `Cond` value
+        // at the end of block, but RAUW unconditionally replaces all uses
+        // including the guards/assumes themselves and the uses before the
+        // guard/assume.
       }
       return true;
     }
   }
 
   // Determine which is the most common successor.  If we have many inputs and
   // this block is a switch, we want to start by threading the batch that goes
   // to the most popular destination first.  If we only know about one

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

if.then:                                          ; preds = %entry
   tail call void (...) @bar() #1
   br label %return
 
 return:                                           ; preds = %entry, %if.then
   %retval.0 = phi i32 [ 1, %if.then ], [ 0, %entry ]
   ret i32 %retval.0
 }
 
+@g = external global i32
+
+; Check that we do prove a fact using an assume within the block.
+; FIXME: We can fold the assume based on the semantics of assume.
+; CHECK-LABEL: @can_fold_assume
+; CHECK: %notnull = icmp ne i32* %array, null
+; CHECK-NEXT: call void @llvm.assume(i1 %notnull)
+; CHECK-NEXT: ret void
+define void @can_fold_assume(i32* %array) {
+  %notnull = icmp ne i32* %array, null
+  call void @llvm.assume(i1 %notnull)
+  br i1 %notnull, label %normal, label %error
+
+normal:
+  ret void
+
+error:
+  store atomic i32 0, i32* @g unordered, align 4
+  ret void
+}
+
+declare void @f(i1)
+declare void @exit()
+; We can fold the assume but not the uses before the assume.
+define void @dont_fold_incorrectly(i32* %array) {
+; CHECK-LABEL:@dont_fold_incorrectly
+; CHECK: @f(i1 %notnull)
+; CHECK-NEXT: exit()
+; CHECK-NEXT: assume(i1 %notnull)
+; CHECK-NEXT: ret void
+  %notnull = icmp ne i32* %array, null
+  call void @f(i1 %notnull)
+  call void @exit()
+  call void @llvm.assume(i1 %notnull)
+  br i1 %notnull, label %normal, label %error
+
+normal:
+  ret void
+
+error:
+  store atomic i32 0, i32* @g unordered, align 4
+  ret void
+}
+
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1) #1
 
 declare void @bar(...)
 
 declare void @car(...)
 
 attributes #0 = { nounwind uwtable }
 attributes #1 = { nounwind }
 

llvm/trunk/test/Transforms/JumpThreading/fold-not-thread.ll

 L2:
   call void @f3()
   ret void
 L3:
   call void @f3()
   ret void
 }
 
-; Make sure we can do the RAUW for %add...
+; FIXME: Make sure we can do the RAUW for %add...
 ;
 ; CHECK-LABEL: @rauw_if_possible(
-; CHECK: call void @f4(i32 96) 
+; CHECK: call void @f4(i32 %add)
 define void @rauw_if_possible(i32 %value) nounwind {
 entry:
   %cmp = icmp eq i32 %value, 32
   br i1 %cmp, label %L0, label %L3 
 L0:
   call i32 @f2()
   call i32 @f2()
   %add = add i32 %value, 64

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

Parent:
   br label %Pred
 
 Exit:
 ; CHECK:       Merge:
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
 ; CHECK-NEXT:    ret void
   ret void
 }
+
+declare void @never_called()
+
+; Assume the guard is always taken and we deoptimize, so we never reach the
+; branch below that guard. We should *never* change the behaviour of a guard from
+; `must deoptimize` to `may deoptimize`, since this affects the program
+; semantics.
+define void @dont_fold_guard(i8* %addr, i32 %i, i32 %length) {
+; CHECK-LABEL: dont_fold_guard
+; CHECK: experimental.guard(i1 %wide.chk)
+
+entry:
+  br label %BBPred
+
+BBPred:
+ %cond = icmp eq i8* %addr, null
+ br i1 %cond, label %zero, label %not_zero
+
+zero:
+  unreachable
+
+not_zero:
+  %c1 = icmp ult i32 %i, %length
+  %c2 = icmp eq i32 %i, 0
+  %wide.chk = and i1 %c1, %c2
+  call void(i1, ...) @llvm.experimental.guard(i1 %wide.chk) [ "deopt"() ]
+  br i1 %c2, label %unreachedBB2, label %unreachedBB1
+
+unreachedBB2:
+  call void @never_called()
+  ret void
+
+unreachedBB1:
+  ret void
+}
+
+
+; same as dont_fold_guard1 but condition %cmp is not an instruction.
+; We cannot fold the guard under any circumstance.
+; FIXME: We can merge unreachableBB2 into not_zero.
+define void @dont_fold_guard2(i8* %addr, i1 %cmp, i32 %i, i32 %length) {
+; CHECK-LABEL: dont_fold_guard2
+; CHECK: guard(i1 %cmp)
+
+entry:
+  br label %BBPred
+
+BBPred:
+ %cond = icmp eq i8* %addr, null
+ br i1 %cond, label %zero, label %not_zero
+
+zero:
+  unreachable
+
+not_zero:
+  call void(i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  br i1 %cmp, label %unreachedBB2, label %unreachedBB1
+
+unreachedBB2:
+  call void @never_called()
+  ret void
+
+unreachedBB1:
+  ret void
+}
+
+; Same as dont_fold_guard1 but use switch instead of branch.
+; triggers source code `ProcessThreadableEdges`.
+declare void @f(i1)
+define void @dont_fold_guard3(i1 %cmp1, i32 %i) nounwind {
+; CHECK-LABEL: dont_fold_guard3 
+; CHECK-LABEL: L2:
+; CHECK-NEXT: %cmp = icmp eq i32 %i, 0 
+; CHECK-NEXT: guard(i1 %cmp)
+; CHECK-NEXT: @f(i1 %cmp)
+; CHECK-NEXT: ret void
+entry:
+  br i1 %cmp1, label %L0, label %L3 
+L0:
+  %cmp = icmp eq i32 %i, 0
+  call void(i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
+  switch i1 %cmp, label %L3 [
+    i1 false, label %L1
+    i1 true, label %L2
+    ]
+
+L1:
+  ret void
+L2:
+  call void @f(i1 %cmp)
+  ret void
+L3:
+  ret void
+}