From e5f602d82ca05d113c725fdfff405dcb7c5470f5 Mon Sep 17 00:00:00 2001 From: Juneyoung Lee Date: Tue, 21 Apr 2020 00:35:45 +0900 Subject: [PATCH] [ValueTracking] Let propagatesPoison support binops/unaryops/cast/etc. Summary: This patch makes propagatesPoison be more accurate by returning true on more bin ops/unary ops/casts/etc. The changed test in ScalarEvolution/nsw.ll was introduced by https://github.com/llvm/llvm-project/commit/a19edc4d15b0dae0210b90615775edd76f021008 . IIUC, the goal of the tests is to show that iv.inc's SCEV expression still has no-overflow flags even if the loop isn't in the wanted form. It becomes more accurate with this patch, so think this is okay. Reviewers: spatel, lebedev.ri, jdoerfert, reames, nikic, sanjoy Reviewed By: spatel, nikic Subscribers: regehr, nlopes, efriedma, fhahn, javed.absar, llvm-commits, hiraditya Tags: #llvm Differential Revision: https://reviews.llvm.org/D78615 --- llvm/include/llvm/Analysis/ValueTracking.h | 8 +++- llvm/lib/Analysis/ValueTracking.cpp | 37 ++++++---------- .../Transforms/Instrumentation/PoisonChecking.cpp | 25 +++++------ llvm/test/Analysis/ScalarEvolution/nsw.ll | 8 ++-- llvm/unittests/Analysis/ValueTrackingTest.cpp | 49 ++++++++++++++++++++++ 5 files changed, 82 insertions(+), 45 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h index fc9c254..caec932 100644 --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -562,8 +562,12 @@ class Value; bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L); - /// Return true if this function can prove that I is guaranteed to yield - /// poison if at least one of its operands is poison. + /// Return true if I yields poison or raises UB if any of its operands is + /// poison. + /// Formally, given I = `r = op v1 v2 .. vN`, propagatesPoison returns true + /// if, for all i, r is evaluated to poison or op raises UB if vi = poison. + /// To filter out operands that raise UB on poison, you can use + /// getGuaranteedNonPoisonOp. bool propagatesPoison(const Instruction *I); /// Return either nullptr or an operand of I such that I will trigger diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index b57a439..691e452 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -4938,35 +4938,22 @@ bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I, } bool llvm::propagatesPoison(const Instruction *I) { - // TODO: This should include all instructions apart from phis, selects and - // call-like instructions. switch (I->getOpcode()) { - case Instruction::Add: - case Instruction::Sub: - case Instruction::Xor: - case Instruction::Trunc: - case Instruction::BitCast: - case Instruction::AddrSpaceCast: - case Instruction::Mul: - case Instruction::Shl: - case Instruction::GetElementPtr: - // These operations all propagate poison unconditionally. Note that poison - // is not any particular value, so xor or subtraction of poison with - // itself still yields poison, not zero. - return true; - - case Instruction::AShr: - case Instruction::SExt: - // For these operations, one bit of the input is replicated across - // multiple output bits. A replicated poison bit is still poison. - return true; - + case Instruction::Freeze: + case Instruction::Select: + case Instruction::PHI: + case Instruction::Call: + case Instruction::Invoke: + return false; case Instruction::ICmp: - // Comparing poison with any value yields poison. This is why, for - // instance, x s< (x +nsw 1) can be folded to true. + case Instruction::FCmp: + case Instruction::GetElementPtr: return true; - default: + if (isa(I) || isa(I) || isa(I)) + return true; + + // Be conservative and return false. return false; } } diff --git a/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp b/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp index e6bb2a2..e5c338f 100644 --- a/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp +++ b/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp @@ -12,10 +12,10 @@ // LangRef. There are obvious parallels to the sanitizer tools, but this pass // is focused purely on the semantics of LLVM IR, not any particular source // language. If you're looking for something to see if your C/C++ contains -// UB, this is not it. -// +// UB, this is not it. +// // The rewritten semantics of each instruction will include the following -// components: +// components: // // 1) The original instruction, unmodified. // 2) A propagation rule which translates dynamic information about the poison @@ -38,7 +38,7 @@ // are well defined on the specific input used. // - Finding/confirming poison specific miscompiles by checking the poison // status of an input/IR pair is the same before and after an optimization -// transform. +// transform. // - Checking that a bugpoint reduction does not introduce UB which didn't // exist in the original program being reduced. // @@ -54,7 +54,7 @@ // moment, all arguments and return values are assumed not to be poison. // - Undef is not modeled. In particular, the optimizer's freedom to pick // concrete values for undef bits so as to maximize potential for producing -// poison is not modeled. +// poison is not modeled. // //===----------------------------------------------------------------------===// @@ -104,7 +104,7 @@ static Value *buildOrChain(IRBuilder<> &B, ArrayRef Ops) { static void generateCreationChecksForBinOp(Instruction &I, SmallVectorImpl &Checks) { assert(isa(I)); - + IRBuilder<> B(&I); Value *LHS = I.getOperand(0); Value *RHS = I.getOperand(1); @@ -266,21 +266,20 @@ static bool rewrite(Function &F) { for (BasicBlock &BB : F) for (auto I = BB.begin(); isa(&*I); I++) { auto *OldPHI = cast(&*I); - auto *NewPHI = PHINode::Create(Int1Ty, - OldPHI->getNumIncomingValues()); + auto *NewPHI = PHINode::Create(Int1Ty, OldPHI->getNumIncomingValues()); for (unsigned i = 0; i < OldPHI->getNumIncomingValues(); i++) NewPHI->addIncoming(UndefValue::get(Int1Ty), OldPHI->getIncomingBlock(i)); NewPHI->insertBefore(OldPHI); ValToPoison[OldPHI] = NewPHI; } - + for (BasicBlock &BB : F) for (Instruction &I : BB) { if (isa(I)) continue; IRBuilder<> B(cast(&I)); - + // Note: There are many more sources of documented UB, but this pass only // attempts to find UB triggered by propagation of poison. if (Value *Op = const_cast(getGuaranteedNonPoisonOp(&I))) @@ -332,7 +331,6 @@ PreservedAnalyses PoisonCheckingPass::run(Function &F, return rewrite(F) ? PreservedAnalyses::none() : PreservedAnalyses::all(); } - /* Major TODO Items: - Control dependent poison UB - Strict mode - (i.e. must analyze every operand) @@ -342,10 +340,7 @@ PreservedAnalyses PoisonCheckingPass::run(Function &F, Instructions w/Unclear Semantics: - shufflevector - It would seem reasonable for an out of bounds mask element - to produce poison, but the LangRef does not state. - - and/or - It would seem reasonable for poison to propagate from both - arguments, but LangRef doesn't state and propagatesPoison doesn't - include these two. + to produce poison, but the LangRef does not state. - all binary ops w/vector operands - The likely interpretation would be that any element overflowing should produce poison for the entire result, but the LangRef does not state. diff --git a/llvm/test/Analysis/ScalarEvolution/nsw.ll b/llvm/test/Analysis/ScalarEvolution/nsw.ll index ca24f9d..cb48aa9 100644 --- a/llvm/test/Analysis/ScalarEvolution/nsw.ll +++ b/llvm/test/Analysis/ScalarEvolution/nsw.ll @@ -223,8 +223,10 @@ leave: ret void } -define void @bad_postinc_nsw_b(i32 %n) { -; CHECK-LABEL: Classifying expressions for: @bad_postinc_nsw_b +; Unlike @bad_postinc_nsw_a(), the SCEV expression of %iv.inc has flag +; because poison can be propagated through 'and %iv.inc, 0'. +define void @postinc_poison_prop_through_and(i32 %n) { +; CHECK-LABEL: Classifying expressions for: @postinc_poison_prop_through_and entry: br label %loop @@ -233,7 +235,7 @@ loop: %iv.inc = add nsw i32 %iv, 7 %iv.inc.and = and i32 %iv.inc, 0 ; CHECK: %iv.inc = add nsw i32 %iv, 7 -; CHECK-NEXT: --> {7,+,7}<%loop> +; CHECK-NEXT: --> {7,+,7}<%loop> %becond = icmp ult i32 %iv.inc.and, %n br i1 %becond, label %loop, label %leave diff --git a/llvm/unittests/Analysis/ValueTrackingTest.cpp b/llvm/unittests/Analysis/ValueTrackingTest.cpp index 5e2feae..85456e6 100644 --- a/llvm/unittests/Analysis/ValueTrackingTest.cpp +++ b/llvm/unittests/Analysis/ValueTrackingTest.cpp @@ -668,6 +668,55 @@ TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) { EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); } +TEST(ValueTracking, propagatesPoison) { + std::string AsmHead = "declare i32 @g(i32)\n" + "define void @f(i32 %x, i32 %y, float %fx, float %fy, " + "i1 %cond, i8* %p) {\n"; + std::string AsmTail = " ret void\n}"; + // (propagates poison?, IR instruction) + SmallVector, 32> Data = { + {true, "add i32 %x, %y"}, + {true, "add nsw nuw i32 %x, %y"}, + {true, "ashr i32 %x, %y"}, + {true, "lshr exact i32 %x, 31"}, + {true, "fcmp oeq float %fx, %fy"}, + {true, "icmp eq i32 %x, %y"}, + {true, "getelementptr i8, i8* %p, i32 %x"}, + {true, "getelementptr inbounds i8, i8* %p, i32 %x"}, + {true, "bitcast float %fx to i32"}, + {false, "select i1 %cond, i32 %x, i32 %y"}, + {false, "freeze i32 %x"}, + {true, "udiv i32 %x, %y"}, + {true, "urem i32 %x, %y"}, + {true, "sdiv exact i32 %x, %y"}, + {true, "srem i32 %x, %y"}, + {false, "call i32 @g(i32 %x)"}}; + + std::string AssemblyStr = AsmHead; + for (auto &Itm : Data) + AssemblyStr += Itm.second + "\n"; + AssemblyStr += AsmTail; + + LLVMContext Context; + SMDiagnostic Error; + auto M = parseAssemblyString(AssemblyStr, Error, Context); + assert(M && "Bad assembly?"); + + auto *F = M->getFunction("f"); + assert(F && "Bad assembly?"); + + auto &BB = F->getEntryBlock(); + + int Index = 0; + for (auto &I : BB) { + if (isa(&I)) + break; + EXPECT_EQ(propagatesPoison(&I), Data[Index].first) + << "Incorrect answer at instruction " << Index << " = " << I; + Index++; + } +} + TEST(ValueTracking, canCreatePoison) { std::string AsmHead = "declare i32 @g(i32)\n" -- 2.7.4