diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -1686,6 +1686,32 @@ static const char ID; }; +/// An abstract attribute for undefined behavior. +struct AAUndefinedBehavior + : public StateWrapper, + public IRPosition { + AAUndefinedBehavior(const IRPosition &IRP) : IRPosition(IRP) {} + + /// Return true if "undefined behavior" is assumed. + bool isAssumedToCauseUB() const { return getAssumed(); } + + /// Return true if "undefined behavior" is assumed for a specific instruction. + virtual bool isAssumedToCauseUB(Instruction *I) const = 0; + + /// Return true if "undefined behavior" is known. + bool isKnownToCauseUB() const { return getKnown(); } + + /// Return an IR position, see struct IRPosition. + const IRPosition &getIRPosition() const override { return *this; } + + /// Create an abstract attribute view for the position \p IRP. + static AAUndefinedBehavior &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// Unique ID (due to the unique address) + static const char ID; +}; + /// An abstract interface to determine reachability of point A to B. struct AAReachability : public StateWrapper, public IRPosition { diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -1987,6 +1987,98 @@ void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); } }; +/// -------------------- Undefined-Behavior Attributes ------------------------ + +struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior { + AAUndefinedBehaviorImpl(const IRPosition &IRP) : AAUndefinedBehavior(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + size_t PrevSize = NoUBLoads.size(); + + // TODO: We should not only check for load instructions. + auto InspectLoadForUB = [&](Instruction &I) { + // Skip instructions that are already saved. + if (NoUBLoads.count(&I) || UBLoads.count(&I)) + return true; + + Value *PtrOp = cast(&I)->getPointerOperand(); + + // A load is considered UB only if it dereferences a constant + // null pointer. + if (!isa(PtrOp)) { + NoUBLoads.insert(&I); + return true; + } + Type *PtrTy = PtrOp->getType(); + + // Because we only consider loads inside functions, + // assume that a parent function exists. + const Function *F = I.getFunction(); + + // A dereference on constant null is only considered UB + // if null dereference is _not_ defined for the target platform. + // TODO: Expand it to not only check constant values. + if (!llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) + UBLoads.insert(&I); + else + NoUBLoads.insert(&I); + return true; + }; + + A.checkForAllInstructions(InspectLoadForUB, *this, {Instruction::Load}); + if (PrevSize != NoUBLoads.size()) + return ChangeStatus::CHANGED; + return ChangeStatus::UNCHANGED; + } + + bool isAssumedToCauseUB(Instruction *I) const override { + return UBLoads.count(I); + } + + ChangeStatus manifest(Attributor &A) override { + if (!UBLoads.size()) + return ChangeStatus::UNCHANGED; + for (Instruction *I : UBLoads) + changeToUnreachable(I, /* UseLLVMTrap */ false); + return ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::getAsStr() + const std::string getAsStr() const override { + return getAssumed() ? "undefined-behavior" : "no-ub"; + } + +protected: + // A set of all the (live) load instructions that _are_ assumed to cause UB. + SmallPtrSet UBLoads; + +private: + // A set of all the (live) load instructions that are _not_ assumed to cause + // UB. + // Note: The correctness of the procedure depends on the fact that this + // set stops changing after some point. "Change" here means that the size + // of the set changes. The size of this set is monotonically increasing + // (we only add items to it) and is upper bounded by the number of load + // instructions in the processed function (we can never save more elements + // in this set than this number). Hence, the size of this set, at some + // point, will stop increasing, effectively reaching a fixpoint. + SmallPtrSet NoUBLoads; +}; + +struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl { + AAUndefinedBehaviorFunction(const IRPosition &IRP) + : AAUndefinedBehaviorImpl(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECL(UndefinedBehaviorInstruction, Instruction, + "Number of instructions known to have UB"); + BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) += + UBLoads.size(); + } +}; + /// ------------------------ Will-Return Attributes ---------------------------- // Helper function that checks whether a function has any cycle. @@ -5523,6 +5615,9 @@ // Every function might be "will-return". getOrCreateAAFor(FPos); + // Every function might contain instructions that cause "undefined behavior". + getOrCreateAAFor(FPos); + // Every function can be nounwind. getOrCreateAAFor(FPos); @@ -5827,6 +5922,7 @@ const char AANonNull::ID = 0; const char AANoRecurse::ID = 0; const char AAWillReturn::ID = 0; +const char AAUndefinedBehavior::ID = 0; const char AANoAlias::ID = 0; const char AAReachability::ID = 0; const char AANoReturn::ID = 0; @@ -5949,6 +6045,7 @@ CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability) +CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior) CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior) diff --git a/llvm/test/Transforms/Attributor/undefined_behavior.ll b/llvm/test/Transforms/Attributor/undefined_behavior.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Attributor/undefined_behavior.ll @@ -0,0 +1,38 @@ +; RUN: opt --attributor --attributor-disable=false -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; Test cases specifically designed for the "undefined behavior" abstract function attribute. +; We want to verify that whenever undefined behavior is assumed, the code becomes unreachable. +; We use FIXME's to indicate problems and missing attributes. + +; ATTRIBUTOR: define void @wholly_unreachable() +; ATTRIBUTOR-NEXT: unreachable +define void @wholly_unreachable() { + %a = load i32, i32* null + ret void +} + +; ATTRIBUTOR: define void @single_bb_unreachable(i1 %cond) +; ATTRIBUTOR-NEXT: br i1 %cond, label %t, label %e +; ATTRIBUTOR-EMPTY: +; ATTRIBUTOR-NEXT: t: +; ATTRIBUTOR-NEXT: unreachable +; ATTRIBUTOR-EMPTY: +; ATTRIBUTOR-NEXT: e: +; ATTRIBUTOR-NEXT: ret void +define void @single_bb_unreachable(i1 %cond) { + br i1 %cond, label %t, label %e +t: + %b = load i32, i32* null + br label %e +e: + ret void +} + +; ATTRIBUTOR: define void @null_pointer_is_defined() +; ATTRIBUTOR-NEXT: %a = load i32, i32* null +define void @null_pointer_is_defined() "null-pointer-is-valid"="true" { + %a = load i32, i32* null + ret void +}