From ec761ad75cb55c3f7d618bad122c7bf4ec022dee Mon Sep 17 00:00:00 2001 From: Anna Thomas Date: Thu, 18 May 2017 13:12:18 +0000 Subject: [PATCH] [JumpThreading] Dont RAUW condition incorrectly 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 at the end of the block. RAUW replaces the uses at the guard/assume as well as uses before the guard/assume. Both of these are incorrect. For now, disable RAUW for conditions and fix the logic as a next step: https://reviews.llvm.org/D33257 Reviewers: sanjoy, reames, trentxintong Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33279 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@303349 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/JumpThreading.cpp | 31 ++++---- test/Transforms/JumpThreading/assume.ll | 44 +++++++++++ test/Transforms/JumpThreading/fold-not-thread.ll | 4 +- test/Transforms/JumpThreading/guards.ll | 94 ++++++++++++++++++++++++ 4 files changed, 154 insertions(+), 19 deletions(-) diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index ae353ea4459..54ab80e448f 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -833,15 +833,13 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) { 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; } @@ -1327,14 +1325,13 @@ bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, if (auto *CondInst = dyn_cast(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; } diff --git a/test/Transforms/JumpThreading/assume.ll b/test/Transforms/JumpThreading/assume.ll index 53010b71c72..3a039676e17 100644 --- a/test/Transforms/JumpThreading/assume.ll +++ b/test/Transforms/JumpThreading/assume.ll @@ -56,6 +56,50 @@ return: ; preds = %entry, %if.then 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 diff --git a/test/Transforms/JumpThreading/fold-not-thread.ll b/test/Transforms/JumpThreading/fold-not-thread.ll index 06ddc10e02b..f05169b31bc 100644 --- a/test/Transforms/JumpThreading/fold-not-thread.ll +++ b/test/Transforms/JumpThreading/fold-not-thread.ll @@ -133,10 +133,10 @@ L3: 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 diff --git a/test/Transforms/JumpThreading/guards.ll b/test/Transforms/JumpThreading/guards.ll index eac2b5dcd85..c5f72b113ef 100644 --- a/test/Transforms/JumpThreading/guards.ll +++ b/test/Transforms/JumpThreading/guards.ll @@ -181,3 +181,97 @@ Exit: ; 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 +} -- 2.11.0