From 492b2bcbcfa72793b2084d970ddc382f52131d49 Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Tue, 15 Aug 2017 00:06:23 +0000 Subject: [PATCH] Merging r309945, r310779 and r310842: ------------------------------------------------------------------------ r309945 | spatel | 2017-08-03 08:07:37 -0700 (Thu, 03 Aug 2017) | 2 lines [BDCE] add tests to show invalid/incomplete transforms ------------------------------------------------------------------------ ------------------------------------------------------------------------ r310779 | spatel | 2017-08-12 09:41:08 -0700 (Sat, 12 Aug 2017) | 13 lines [BDCE] clear poison generators after turning a value into zero (PR33695, PR34037) nsw, nuw, and exact carry implicit assumptions about their operands, so we need to clear those after trivializing a value. We decided there was no danger for llvm.assume or metadata, so there's just a comment about that. This fixes miscompiles as shown in: https://bugs.llvm.org/show_bug.cgi?id=33695 https://bugs.llvm.org/show_bug.cgi?id=34037 Differential Revision: https://reviews.llvm.org/D36592 ------------------------------------------------------------------------ ------------------------------------------------------------------------ r310842 | spatel | 2017-08-14 08:13:46 -0700 (Mon, 14 Aug 2017) | 16 lines [BDCE] reduce scope of an assert (PR34179) The assert was added with r310779 and is usually correct, but as the test shows, not always. The 'volatile' on the load is needed to expose the faulty path because without it, DemandedBits would return that the load is just dead rather than not demanded, and so we wouldn't hit the bogus assert. Also, since the lambda is just a single-line now, get rid of it and inline the DB.isAllOnesValue() calls. This should fix (prevent execution of a faulty assert): https://bugs.llvm.org/show_bug.cgi?id=34179 ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_50@310898 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/BDCE.cpp | 44 ++++++++ .../Transforms/BDCE/invalidate-assumptions.ll | 100 ++++++++++++++++++ 2 files changed, 144 insertions(+) create mode 100644 test/Transforms/BDCE/invalidate-assumptions.ll diff --git a/lib/Transforms/Scalar/BDCE.cpp b/lib/Transforms/Scalar/BDCE.cpp index 61e8700f1cd..2e5618686ec 100644 --- a/lib/Transforms/Scalar/BDCE.cpp +++ b/lib/Transforms/Scalar/BDCE.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/BDCE.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DemandedBits.h" @@ -35,6 +36,46 @@ using namespace llvm; STATISTIC(NumRemoved, "Number of instructions removed (unused)"); STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)"); +/// If an instruction is trivialized (dead), then the chain of users of that +/// instruction may need to be cleared of assumptions that can no longer be +/// guaranteed correct. +static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) { + assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?"); + + // Initialize the worklist with eligible direct users. + SmallVector WorkList; + for (User *JU : I->users()) { + // If all bits of a user are demanded, then we know that nothing below that + // in the def-use chain needs to be changed. + auto *J = dyn_cast(JU); + if (J && !DB.getDemandedBits(J).isAllOnesValue()) + WorkList.push_back(J); + } + + // DFS through subsequent users while tracking visits to avoid cycles. + SmallPtrSet Visited; + while (!WorkList.empty()) { + Instruction *J = WorkList.pop_back_val(); + + // NSW, NUW, and exact are based on operands that might have changed. + J->dropPoisonGeneratingFlags(); + + // We do not have to worry about llvm.assume or range metadata: + // 1. llvm.assume demands its operand, so trivializing can't change it. + // 2. range metadata only applies to memory accesses which demand all bits. + + Visited.insert(J); + + for (User *KU : J->users()) { + // If all bits of a user are demanded, then we know that nothing below + // that in the def-use chain needs to be changed. + auto *K = dyn_cast(KU); + if (K && !Visited.count(K) && !DB.getDemandedBits(K).isAllOnesValue()) + WorkList.push_back(K); + } + } +} + static bool bitTrackingDCE(Function &F, DemandedBits &DB) { SmallVector Worklist; bool Changed = false; @@ -51,6 +92,9 @@ static bool bitTrackingDCE(Function &F, DemandedBits &DB) { // replacing all uses with something else. Then, if they don't need to // remain live (because they have side effects, etc.) we can remove them. DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n"); + + clearAssumptionsOfUsers(&I, DB); + // FIXME: In theory we could substitute undef here instead of zero. // This should be reconsidered once we settle on the semantics of // undef, poison, etc. diff --git a/test/Transforms/BDCE/invalidate-assumptions.ll b/test/Transforms/BDCE/invalidate-assumptions.ll new file mode 100644 index 00000000000..d165d74be86 --- /dev/null +++ b/test/Transforms/BDCE/invalidate-assumptions.ll @@ -0,0 +1,100 @@ +; RUN: opt -bdce %s -S | FileCheck %s + +; The 'nuw' on the subtract allows us to deduce that %setbit is not demanded. +; But if we change that value to '0', then the 'nuw' is no longer valid. If we don't +; remove the 'nuw', another pass (-instcombine) may make a transform based on an +; that incorrect assumption and we can miscompile: +; https://bugs.llvm.org/show_bug.cgi?id=33695 + +define i1 @PR33695(i1 %b, i8 %x) { +; CHECK-LABEL: @PR33695( +; CHECK-NEXT: [[SETBIT:%.*]] = or i8 %x, 64 +; CHECK-NEXT: [[LITTLE_NUMBER:%.*]] = zext i1 %b to i8 +; CHECK-NEXT: [[BIG_NUMBER:%.*]] = shl i8 0, 1 +; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]] +; CHECK-NEXT: [[TRUNC:%.*]] = trunc i8 [[SUB]] to i1 +; CHECK-NEXT: ret i1 [[TRUNC]] +; + %setbit = or i8 %x, 64 + %little_number = zext i1 %b to i8 + %big_number = shl i8 %setbit, 1 + %sub = sub nuw i8 %big_number, %little_number + %trunc = trunc i8 %sub to i1 + ret i1 %trunc +} + +; Similar to above, but now with more no-wrap. +; https://bugs.llvm.org/show_bug.cgi?id=34037 + +define i64 @PR34037(i64 %m, i32 %r, i64 %j, i1 %b, i32 %k, i64 %p) { +; CHECK-LABEL: @PR34037( +; CHECK-NEXT: [[CONV:%.*]] = zext i32 %r to i64 +; CHECK-NEXT: [[AND:%.*]] = and i64 %m, 0 +; CHECK-NEXT: [[NEG:%.*]] = xor i64 0, 34359738367 +; CHECK-NEXT: [[OR:%.*]] = or i64 %j, 0 +; CHECK-NEXT: [[SHL:%.*]] = shl i64 0, 29 +; CHECK-NEXT: [[CONV1:%.*]] = select i1 %b, i64 7, i64 0 +; CHECK-NEXT: [[SUB:%.*]] = sub i64 [[SHL]], [[CONV1]] +; CHECK-NEXT: [[CONV2:%.*]] = zext i32 %k to i64 +; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[SUB]], [[CONV2]] +; CHECK-NEXT: [[CONV4:%.*]] = and i64 %p, 65535 +; CHECK-NEXT: [[AND5:%.*]] = and i64 [[MUL]], [[CONV4]] +; CHECK-NEXT: ret i64 [[AND5]] +; + %conv = zext i32 %r to i64 + %and = and i64 %m, %conv + %neg = xor i64 %and, 34359738367 + %or = or i64 %j, %neg + %shl = shl i64 %or, 29 + %conv1 = select i1 %b, i64 7, i64 0 + %sub = sub nuw nsw i64 %shl, %conv1 + %conv2 = zext i32 %k to i64 + %mul = mul nsw i64 %sub, %conv2 + %conv4 = and i64 %p, 65535 + %and5 = and i64 %mul, %conv4 + ret i64 %and5 +} + +; This is a manufactured example based on the 1st test to prove that the +; assumption-killing algorithm stops at the call. Ie, it does not remove +; nsw/nuw from the 'add' because a call demands all bits of its argument. + +declare i1 @foo(i1) + +define i1 @poison_on_call_user_is_ok(i1 %b, i8 %x) { +; CHECK-LABEL: @poison_on_call_user_is_ok( +; CHECK-NEXT: [[SETBIT:%.*]] = or i8 %x, 64 +; CHECK-NEXT: [[LITTLE_NUMBER:%.*]] = zext i1 %b to i8 +; CHECK-NEXT: [[BIG_NUMBER:%.*]] = shl i8 0, 1 +; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[BIG_NUMBER]], [[LITTLE_NUMBER]] +; CHECK-NEXT: [[TRUNC:%.*]] = trunc i8 [[SUB]] to i1 +; CHECK-NEXT: [[CALL_RESULT:%.*]] = call i1 @foo(i1 [[TRUNC]]) +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i1 [[CALL_RESULT]], true +; CHECK-NEXT: [[MUL:%.*]] = mul i1 [[TRUNC]], [[ADD]] +; CHECK-NEXT: ret i1 [[MUL]] +; + %setbit = or i8 %x, 64 + %little_number = zext i1 %b to i8 + %big_number = shl i8 %setbit, 1 + %sub = sub nuw i8 %big_number, %little_number + %trunc = trunc i8 %sub to i1 + %call_result = call i1 @foo(i1 %trunc) + %add = add nsw nuw i1 %call_result, 1 + %mul = mul i1 %trunc, %add + ret i1 %mul +} + + +; We were asserting that all users of a trivialized integer-type instruction were +; also integer-typed, but that's too strong. The alloca has a pointer-type result. + +define void @PR34179(i32* %a) { +; CHECK-LABEL: @PR34179( +; CHECK-NEXT: [[T0:%.*]] = load volatile i32, i32* %a +; CHECK-NEXT: ret void +; + %t0 = load volatile i32, i32* %a + %vla = alloca i32, i32 %t0 + ret void +} + -- 2.50.1