diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -563,34 +563,28 @@ const Loop *L); /// Return true if this function can prove that I is guaranteed to yield - /// full-poison (all bits poison) if at least one of its operands are - /// full-poison (all bits poison). - /// - /// The exact rules for how poison propagates through instructions have - /// not been settled as of 2015-07-10, so this function is conservative - /// and only considers poison to be propagated in uncontroversial - /// cases. There is no attempt to track values that may be only partially - /// poison. - bool propagatesFullPoison(const Instruction *I); + /// poison if at least one of its operands is poison. + /// If I raises immediate UB (e.g. load poison), propagatesPoison returns + /// false. + bool propagatesPoison(const Instruction *I); /// Return either nullptr or an operand of I such that I will trigger - /// undefined behavior if I is executed and that operand has a full-poison - /// value (all bits poison). - const Value *getGuaranteedNonFullPoisonOp(const Instruction *I); + /// undefined behavior if I is executed and that operand has a poison + /// value. + const Value *getGuaranteedNonPoisonOp(const Instruction *I); /// Return true if the given instruction must trigger undefined behavior. /// when I is executed with any operands which appear in KnownPoison holding - /// a full-poison value at the point of execution. + /// a poison value at the point of execution. bool mustTriggerUB(const Instruction *I, const SmallSet& KnownPoison); /// Return true if this function can prove that if PoisonI is executed - /// and yields a full-poison value (all bits poison), then that will - /// trigger undefined behavior. + /// and yields a poison value, then that will trigger undefined behavior. /// /// Note that this currently only considers the basic block that is /// the parent of I. - bool programUndefinedIfFullPoison(const Instruction *PoisonI); + bool programUndefinedIfPoison(const Instruction *PoisonI); /// Return true if I can create poison from non-poison operands. /// For vectors, canCreatePoison returns true if there is potential poison in diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -6072,7 +6072,7 @@ return false; // Only proceed if we can prove that I does not yield poison. - if (!programUndefinedIfFullPoison(I)) + if (!programUndefinedIfPoison(I)) return false; // At this point we know that if I is executed, then it does not wrap @@ -6152,7 +6152,7 @@ SmallVector PoisonStack; // We start by assuming \c I, the post-inc add recurrence, is poison. Only - // things that are known to be fully poison under that assumption go on the + // things that are known to be poison under that assumption go on the // PoisonStack. Pushed.insert(I); PoisonStack.push_back(I); @@ -6162,7 +6162,7 @@ const Instruction *Poison = PoisonStack.pop_back_val(); for (auto *PoisonUser : Poison->users()) { - if (propagatesFullPoison(cast(PoisonUser))) { + if (propagatesPoison(cast(PoisonUser))) { if (Pushed.insert(cast(PoisonUser)).second) PoisonStack.push_back(cast(PoisonUser)); } else if (auto *BI = dyn_cast(PoisonUser)) { diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -4719,7 +4719,7 @@ } if (auto I = dyn_cast(V)) { - if (programUndefinedIfFullPoison(I) && I->getType()->isIntegerTy(1)) + if (programUndefinedIfPoison(I) && I->getType()->isIntegerTy(1)) // Note: once we have an agreement that poison is a value-wise concept, // we can remove the isIntegerTy(1) constraint. return true; @@ -4845,41 +4845,31 @@ llvm_unreachable("Instruction not contained in its own parent basic block."); } -bool llvm::propagatesFullPoison(const Instruction *I) { - // TODO: This should include all instructions apart from phis, selects and - // call-like instructions. +bool llvm::propagatesPoison(const Instruction *I) { 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::UDiv: + case Instruction::SDiv: + case Instruction::URem: + case Instruction::SRem: + case Instruction::Freeze: + case Instruction::Select: + case Instruction::PHI: + case Instruction::Load: + 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; } } -const Value *llvm::getGuaranteedNonFullPoisonOp(const Instruction *I) { +const Value *llvm::getGuaranteedNonPoisonOp(const Instruction *I) { switch (I->getOpcode()) { case Instruction::Store: return cast(I)->getPointerOperand(); @@ -4917,12 +4907,12 @@ bool llvm::mustTriggerUB(const Instruction *I, const SmallSet& KnownPoison) { - auto *NotPoison = getGuaranteedNonFullPoisonOp(I); + auto *NotPoison = getGuaranteedNonPoisonOp(I); return (NotPoison && KnownPoison.count(NotPoison)); } -bool llvm::programUndefinedIfFullPoison(const Instruction *PoisonI) { +bool llvm::programUndefinedIfPoison(const Instruction *PoisonI) { // We currently only look for uses of poison values within the same basic // block, as that makes it easier to guarantee that the uses will be // executed given that PoisonI is executed. @@ -4955,7 +4945,7 @@ if (YieldsPoison.count(&I)) { for (const User *User : I.users()) { const Instruction *UserI = cast(User); - if (propagatesFullPoison(UserI)) + if (propagatesPoison(UserI)) YieldsPoison.insert(User); } } diff --git a/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp b/llvm/lib/Transforms/Instrumentation/PoisonChecking.cpp --- 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 void generateCreationChecksForBinOp(Instruction &I, SmallVectorImpl &Checks) { assert(isa(I)); - + IRBuilder<> B(&I); Value *LHS = I.getOperand(0); Value *RHS = I.getOperand(1); @@ -266,7 +266,7 @@ for (BasicBlock &BB : F) for (auto I = BB.begin(); isa(&*I); I++) { auto *OldPHI = cast(&*I); - auto *NewPHI = PHINode::Create(Int1Ty, + auto *NewPHI = PHINode::Create(Int1Ty, OldPHI->getNumIncomingValues()); for (unsigned i = 0; i < OldPHI->getNumIncomingValues(); i++) NewPHI->addIncoming(UndefValue::get(Int1Ty), @@ -274,16 +274,16 @@ 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(getGuaranteedNonFullPoisonOp(&I))) + if (Value *Op = const_cast(getGuaranteedNonPoisonOp(&I))) CreateAssertNot(B, getPoisonFor(ValToPoison, Op)); if (LocalCheck) @@ -294,7 +294,7 @@ } SmallVector Checks; - if (propagatesFullPoison(&I)) + if (propagatesPoison(&I)) for (Value *V : I.operands()) Checks.push_back(getPoisonFor(ValToPoison, V)); @@ -342,10 +342,9 @@ 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. + 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 propagatesFullPoison doesn't - include these two. + arguments, but LangRef doesn't 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/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1813,7 +1813,7 @@ // If we can't analyze propagation through this instruction, just skip it // and transitive users. Safe as false is a conservative result. - if (!propagatesFullPoison(I) && I != Root) + if (!propagatesPoison(I) && I != Root) continue; if (KnownPoison.insert(I).second) diff --git a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp --- a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp +++ b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp @@ -1214,13 +1214,13 @@ // Add I to DominatingExprs if it's an add/sub that can't sign overflow. if (match(I, m_NSWAdd(m_Value(LHS), m_Value(RHS)))) { - if (programUndefinedIfFullPoison(I)) { + if (programUndefinedIfPoison(I)) { const SCEV *Key = SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS)); DominatingAdds[Key].push_back(I); } } else if (match(I, m_NSWSub(m_Value(LHS), m_Value(RHS)))) { - if (programUndefinedIfFullPoison(I)) { + if (programUndefinedIfPoison(I)) { const SCEV *Key = SE->getAddExpr(SE->getUnknown(LHS), SE->getUnknown(RHS)); DominatingSubs[Key].push_back(I); diff --git a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll --- a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll +++ b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll @@ -205,7 +205,7 @@ ret void } -; Demonstrate why we need a Visited set in llvm::programUndefinedIfFullPoison. +; Demonstrate why we need a Visited set in llvm::programUndefinedIfPoison. define void @test-add-not-header5(float* %input, i32 %offset) { ; CHECK-LABEL: @test-add-not-header5 entry: diff --git a/llvm/test/Analysis/ScalarEvolution/nsw.ll b/llvm/test/Analysis/ScalarEvolution/nsw.ll --- a/llvm/test/Analysis/ScalarEvolution/nsw.ll +++ b/llvm/test/Analysis/ScalarEvolution/nsw.ll @@ -233,7 +233,7 @@ %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 --- a/llvm/unittests/Analysis/ValueTrackingTest.cpp +++ b/llvm/unittests/Analysis/ValueTrackingTest.cpp @@ -667,6 +667,55 @@ 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"}, + {false, "udiv i32 %x, %y"}, + {false, "urem i32 %x, %y"}, + {false, "sdiv exact i32 %x, %y"}, + {false, "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"