Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ 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 known. + bool isKnownToCauseUB() const { return getKnown(); } + + /// Return true if "undefined behavior" is known for a specific instruction. + virtual bool isKnownToCauseUB(Instruction *I) const = 0; + + /// 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 { Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -1987,6 +1987,102 @@ void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); } }; +/// -------------------- Undefined-Behavior Attributes ------------------------ + +struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior { + AAUndefinedBehaviorImpl(const IRPosition &IRP) : AAUndefinedBehavior(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AAUndefinedBehavior::initialize(A); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + size_t PrevSize = NoUBLoads.size(); + + auto CannotCauseUB = [&](Instruction &I) { + // Skip instructions that are already saved as assumed + // to not cause UB. + if (NoUBLoads.find(&I) != NoUBLoads.end() || + UBLoads.find(&I) != UBLoads.end()) + return true; + // Find whether it can cause UB by checking if the pointer + // is null. However, null dereference is defined for some + // targets, so it is assumed to cause UB only for those + // that it is not. + 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. + if (!llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) + UBLoads.insert(&I); + else + NoUBLoads.insert(&I); + return true; + }; + A.checkForAllInstructions(CannotCauseUB, *this, {Instruction::Load}); + if (PrevSize != NoUBLoads.size()) + return ChangeStatus::CHANGED; + return ChangeStatus::UNCHANGED; + } + + bool isKnownToCauseUB(Instruction *I) const override { + return (UBLoads.find(I) != UBLoads.end()); + } + + 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. @@ -2098,9 +2194,7 @@ } /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - indicatePessimisticFixpoint(); - } + void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { @@ -2579,12 +2673,14 @@ CI->takeName(II); replaceAllInstructionUsesWith(*II, *CI); - // If this is a nounwind + mayreturn invoke we only remove the unwind edge. - // This is done by moving the invoke into a new and dead block and connecting - // the normal destination of the invoke with a branch that follows the call - // replacement we created above. + // If this is a nounwind + mayreturn invoke we only remove the + // unwind edge. This is done by moving the invoke into a new and + // dead block and connecting the normal destination of the invoke + // with a branch that follows the call replacement we created + // above. if (MayReturn) { - BasicBlock *NewDeadBB = SplitBlock(BB, II, nullptr, nullptr, nullptr, ".i2c"); + BasicBlock *NewDeadBB = + SplitBlock(BB, II, nullptr, nullptr, nullptr, ".i2c"); assert(isa(BB->getTerminator()) && BB->getTerminator()->getNumSuccessors() == 1 && BB->getTerminator()->getSuccessor(0) == NewDeadBB); @@ -5523,6 +5619,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 +5926,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 +6049,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)