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 @@ -592,6 +592,18 @@ /// the parent of I. bool programUndefinedIfFullPoison(const Instruction *PoisonI); + /// Return true if I can create poison from non-poison operands. + /// If I is returning a vector value, true is returnd if it may contain + /// poison element when vectors without poison element are given. + bool canCreatePoison(const Instruction *I); + + /// Return true if V is poison given that ValAssumedPoison is already poison. + /// + /// If CtxI and DT are specified this method performs flow-sensitive analysis + bool impliesPoison(const Value *ValAssumedPoison, const Value *V, + const Instruction *CtxI = nullptr, + const DominatorTree *DT = nullptr); + /// Return true if this function can prove that V is never undef value /// or poison value. // 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 @@ -4592,6 +4592,135 @@ return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch); } +bool llvm::canCreatePoison(const Instruction *I) { + unsigned Opcode = I->getOpcode(); + + // Check whether opcode is a poison-generating operation + switch (Opcode) { + case Instruction::Shl: + case Instruction::AShr: + case Instruction::LShr: + // Shifts return poison if shiftwidth is larger than the bitwidth. + return true; + case Instruction::FPToSI: + case Instruction::FPToUI: + // fptosi/ui yields poison if the resulting value does not fit in the + // destination type. + return true; + case Instruction::Call: + case Instruction::CallBr: + case Instruction::Invoke: + // Function calls can return a poison value even if args are non-poison + // values. CallBr returns poison when jumping to indirect labels. + return true; + case Instruction::InsertElement: + case Instruction::ExtractElement: { + // If index exceeds the length of the vector, it returns poison + auto *VTy = dyn_cast(I->getOperand(0)->getType()); + unsigned IdxOp = I->getOpcode() == Instruction::InsertElement ? 2 : 1; + auto *Idx = dyn_cast(I->getOperand(IdxOp)); + if (!Idx || Idx->getZExtValue() >= VTy->getElementCount().Min) + return true; + return false; + } + default: + break; + } + + // See whether I has flags that may create poison + if (isa(I)) + return I->hasNoSignedWrap() || I->hasNoUnsignedWrap(); + if (isa(I)) + return I->isExact(); + if (auto *FP = dyn_cast(I)) { + auto FMF = FP->getFastMathFlags(); + return FMF.noNaNs() || FMF.noInfs(); + } + if (auto *GEP = dyn_cast(I)) + return GEP->isInBounds(); + + // Return false if I is known not to create poison + switch (Opcode) { + case Instruction::PHI: + case Instruction::Select: + case Instruction::URem: + case Instruction::SRem: + case Instruction::ShuffleVector: + case Instruction::ExtractValue: + case Instruction::InsertValue: + case Instruction::Freeze: + case Instruction::ICmp: + return false; + default: + if (isa(I)) + return false; + + // Be conservative and return true. + return true; + } +} + +bool llvm::impliesPoison(const Value *ValAssumedPoison, const Value *V, + const Instruction *CtxI, const DominatorTree *DT) { + if (isGuaranteedNotToBeUndefOrPoison(ValAssumedPoison, CtxI, DT)) + // The assumption is false, so we can say anything + return true; + + // Construct a set of values which are known to be poison from + // ValAssumedPoison. + SmallSet PoisonValues; + PoisonValues.insert(ValAssumedPoison); + const Instruction *PoisonI = dyn_cast(ValAssumedPoison); + unsigned Depth = 0; + + while (PoisonI && Depth < MaxDepth) { + // We'd like to know whether an operand of PoisonI is also poison. + if (canCreatePoison(PoisonI)) + // PoisonI can be a poison-generating instruction, so don't look further + break; + + const Value *NextVal = nullptr; + bool MoreThanOneCandidate = false; + for (auto &Op : PoisonI->operands()) { + if (!isGuaranteedNotToBeUndefOrPoison(Op.get(), CtxI, DT)) { + // Op can be poison. + if (NextVal) { + // There is more than one operand that can make PoisonI poison. + MoreThanOneCandidate = true; + break; + } + NextVal = Op.get(); + } + } + + if (NextVal == nullptr) { + // All operands are non-poison, so PoisonI cannot be poison! + return true; + } else if (MoreThanOneCandidate) + break; + + Depth++; + PoisonValues.insert(NextVal); + PoisonI = dyn_cast(NextVal); + } + + if (PoisonValues.count(V) != 0) + // V should be poison. + return true; + + // Let's look one level further, by seeing its arguments if I was an + // instruction. + auto *I = dyn_cast(V); + if (I && propagatesFullPoison(I)) { + for (auto &Op : I->operands()) + if (PoisonValues.count(Op.get())) + return true; + } + + return false; +} + + bool llvm::isGuaranteedNotToBeUndefOrPoison(const Value *V, const Instruction *CtxI, const DominatorTree *DT) { 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 @@ -44,11 +44,13 @@ if (!F) return; - A = nullptr; + A = B = nullptr; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { if (I->hasName()) { if (I->getName() == "A") A = &*I; + else if (I->getName() == "B") + B = &*I; } } ASSERT_TRUE(A) << "@test must have an instruction %A"; @@ -57,6 +59,7 @@ LLVMContext Context; std::unique_ptr M; Instruction *A = nullptr; + Instruction *B = nullptr; }; class MatchSelectPatternTest : public ValueTrackingTest { @@ -645,7 +648,7 @@ EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); } -// No guarantees for canonical IR in this analysis, so this just bails out. +// No guarantees for canonical IR in this analysis, so this just bails out. TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle) { parseAssembly( "define <2 x i32> @test() {\n" @@ -656,7 +659,7 @@ } // No guarantees for canonical IR in this analysis, so a shuffle element that -// references an undef value means this can't return any extra information. +// references an undef value means this can't return any extra information. TEST_F(ValueTrackingTest, ComputeNumSignBits_Shuffle2) { parseAssembly( "define <2 x i32> @test(<2 x i1> %x) {\n" @@ -667,6 +670,127 @@ EXPECT_EQ(ComputeNumSignBits(A, M->getDataLayout()), 1u); } +TEST_F(ValueTrackingTest, impliesPoisonTest_Identity) { + parseAssembly( + "define void @test(i32 %x, i32 %y) {\n" + " %A = add i32 %x, %y\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(A, A), 1u); +} + +TEST_F(ValueTrackingTest, impliesPoisonTest_ICmp) { + parseAssembly( + "define void @test(i32 %x) {\n" + " %B = icmp eq i32 %x, 0\n" + " %A = icmp eq i32 %x, 1\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(B, A), 1u); +} + +TEST_F(ValueTrackingTest, impliesPoisonTest_ICmpUnknown) { + parseAssembly( + "define void @test(i32 %x, i32 %y) {\n" + " %B = icmp eq i32 %x, %y\n" + " %A = icmp eq i32 %x, 1\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(B, A), 0u); +} + +TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay) { + parseAssembly( + "define void @test(i32 %x) {\n" + " %B = add nsw i32 %x, 1\n" + " %A = add i32 %B, 1\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(B, A), 1u); +} + +TEST_F(ValueTrackingTest, impliesPoisonTest_AddNswOkay2) { + parseAssembly( + "define void @test(i32 %x) {\n" + " %B = add i32 %x, 1\n" + " %A = add nsw i32 %B, 1\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(B, A), 1u); +} + +TEST_F(ValueTrackingTest, impliesPoisonTest_AddNsw) { + parseAssembly( + "define void @test(i32 %x) {\n" + " %B = add nsw i32 %x, 1\n" + " %A = add i32 %x, 1\n" + " ret void\n" + "}"); + EXPECT_EQ(impliesPoison(B, A), 0u); +} + +TEST(ValueTracking, canCreatePoison) { + std::string AsmHead = + "declare i32 @g(i32)\n" + "define void @f(i32 %x, i32 %y, float %fx, float %fy, i1 %cond, " + "<4 x i32> %vx, %svx, i8* %p) {\n"; + std::string AsmTail = " ret void\n}"; + // (can create poison?, IR instruction) + SmallVector, 32> Data = { + { false, "add i32 %x, %y" }, + { true, "add nsw nuw i32 %x, %y" }, + { true, "shl i32 %x, %y" }, + { true, "ashr i32 %x, %y" }, + { true, "lshr i32 %x, %y" }, + { false, "udiv i32 %x, %y" }, + { true, "udiv exact i32 %x, %y" }, + { false, "fadd float %fx, %fy" }, + { false, "getelementptr i8, i8* %p, i32 %x" }, + { true, "getelementptr inbounds i8, i8* %p, i32 %x" }, + { true, "fadd nnan float %fx, %fy" }, + { false, "urem i32 %x, %y" }, + { true, "fptoui float %fx to i32"}, + { true, "fptosi float %fx to i32"}, + { false, "bitcast float %fx to i32"}, + { false, "select i1 %cond, i32 %x, i32 %y" }, + { true, "select nnan i1 %cond, float %fx, float %fy" }, + { true, "extractelement <4 x i32> %vx, i32 %x" }, + { false, "extractelement <4 x i32> %vx, i32 3" }, + { true, "extractelement %svx, i32 4" }, + { true, "insertelement <4 x i32> %vx, i32 %x, i32 %y" }, + { false, "insertelement <4 x i32> %vx, i32 %x, i32 3" }, + { true, "insertelement %svx, i32 %x, i32 4" }, + { false, "freeze i32 %x" }, + { true, "call i32 @g(i32 %x)" }, + { true, "fcmp nnan oeq float %fx, %fy" }, + { false, "fcmp oeq float %fx, %fy" } + }; + + 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(canCreatePoison(&I), Data[Index].first) + << "Incorrect answer at instruction " << Index << " = " << I; + Index++; + } +} + TEST_F(ComputeKnownBitsTest, ComputeKnownBits) { parseAssembly( "define i32 @test(i32 %a, i32 %b) {\n"