diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp | 2811 |
1 files changed, 2316 insertions, 495 deletions
diff --git a/contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp b/contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp index 95f47345d8fd..f2995817eaf8 100644 --- a/contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/contrib/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp @@ -23,14 +23,18 @@ #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/CFG.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Verifier.h" +#include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -53,6 +57,8 @@ STATISTIC(NumAttributesValidFixpoint, "Number of abstract attributes in a valid fixpoint state"); STATISTIC(NumAttributesManifested, "Number of abstract attributes manifested in IR"); +STATISTIC(NumAttributesFixedDueToRequiredDependences, + "Number of abstract attributes fixed due to required dependences"); // Some helper macros to deal with statistics tracking. // @@ -98,6 +104,36 @@ STATISTIC(NumAttributesManifested, STATS_DECLTRACK(NAME, Floating, \ ("Number of floating values known to be '" #NAME "'")) +// Specialization of the operator<< for abstract attributes subclasses. This +// disambiguates situations where multiple operators are applicable. +namespace llvm { +#define PIPE_OPERATOR(CLASS) \ + raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) { \ + return OS << static_cast<const AbstractAttribute &>(AA); \ + } + +PIPE_OPERATOR(AAIsDead) +PIPE_OPERATOR(AANoUnwind) +PIPE_OPERATOR(AANoSync) +PIPE_OPERATOR(AANoRecurse) +PIPE_OPERATOR(AAWillReturn) +PIPE_OPERATOR(AANoReturn) +PIPE_OPERATOR(AAReturnedValues) +PIPE_OPERATOR(AANonNull) +PIPE_OPERATOR(AANoAlias) +PIPE_OPERATOR(AADereferenceable) +PIPE_OPERATOR(AAAlign) +PIPE_OPERATOR(AANoCapture) +PIPE_OPERATOR(AAValueSimplify) +PIPE_OPERATOR(AANoFree) +PIPE_OPERATOR(AAHeapToStack) +PIPE_OPERATOR(AAReachability) +PIPE_OPERATOR(AAMemoryBehavior) +PIPE_OPERATOR(AAValueConstantRange) + +#undef PIPE_OPERATOR +} // namespace llvm + // TODO: Determine a good default value. // // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads @@ -120,6 +156,10 @@ static cl::opt<bool> DisableAttributor( cl::desc("Disable the attributor inter-procedural deduction pass."), cl::init(true)); +static cl::opt<bool> AnnotateDeclarationCallSites( + "attributor-annotate-decl-cs", cl::Hidden, + cl::desc("Annotate call sites of function declarations."), cl::init(false)); + static cl::opt<bool> ManifestInternal( "attributor-manifest-internal", cl::Hidden, cl::desc("Manifest Attributor internal string attributes."), @@ -147,6 +187,74 @@ ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) { } ///} +Argument *IRPosition::getAssociatedArgument() const { + if (getPositionKind() == IRP_ARGUMENT) + return cast<Argument>(&getAnchorValue()); + + // Not an Argument and no argument number means this is not a call site + // argument, thus we cannot find a callback argument to return. + int ArgNo = getArgNo(); + if (ArgNo < 0) + return nullptr; + + // Use abstract call sites to make the connection between the call site + // values and the ones in callbacks. If a callback was found that makes use + // of the underlying call site operand, we want the corresponding callback + // callee argument and not the direct callee argument. + Optional<Argument *> CBCandidateArg; + SmallVector<const Use *, 4> CBUses; + ImmutableCallSite ICS(&getAnchorValue()); + AbstractCallSite::getCallbackUses(ICS, CBUses); + for (const Use *U : CBUses) { + AbstractCallSite ACS(U); + assert(ACS && ACS.isCallbackCall()); + if (!ACS.getCalledFunction()) + continue; + + for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) { + + // Test if the underlying call site operand is argument number u of the + // callback callee. + if (ACS.getCallArgOperandNo(u) != ArgNo) + continue; + + assert(ACS.getCalledFunction()->arg_size() > u && + "ACS mapped into var-args arguments!"); + if (CBCandidateArg.hasValue()) { + CBCandidateArg = nullptr; + break; + } + CBCandidateArg = ACS.getCalledFunction()->getArg(u); + } + } + + // If we found a unique callback candidate argument, return it. + if (CBCandidateArg.hasValue() && CBCandidateArg.getValue()) + return CBCandidateArg.getValue(); + + // If no callbacks were found, or none used the underlying call site operand + // exclusively, use the direct callee argument if available. + const Function *Callee = ICS.getCalledFunction(); + if (Callee && Callee->arg_size() > unsigned(ArgNo)) + return Callee->getArg(ArgNo); + + return nullptr; +} + +/// For calls (and invokes) we will only replace instruction uses to not disturb +/// the old style call graph. +/// TODO: Remove this once we get rid of the old PM. +static void replaceAllInstructionUsesWith(Value &Old, Value &New) { + if (!isa<CallBase>(Old)) + return Old.replaceAllUsesWith(&New); + SmallVector<Use *, 8> Uses; + for (Use &U : Old.uses()) + if (isa<Instruction>(U.getUser())) + Uses.push_back(&U); + for (Use *U : Uses) + U->set(&New); +} + /// Recursively visit all values that might become \p IRP at some point. This /// will be done by looking through cast instructions, selects, phis, and calls /// with the "returned" attribute. Once we cannot look through the value any @@ -234,7 +342,7 @@ static bool genericValueTraversal( // If we actually used liveness information so we have to record a dependence. if (AnyDead) - A.recordDependence(*LivenessAA, QueryingAA); + A.recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL); // All values have been visited. return true; @@ -282,34 +390,18 @@ static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, llvm_unreachable("Expected enum or string attribute!"); } -static const Value *getPointerOperand(const Instruction *I) { - if (auto *LI = dyn_cast<LoadInst>(I)) - if (!LI->isVolatile()) - return LI->getPointerOperand(); - if (auto *SI = dyn_cast<StoreInst>(I)) - if (!SI->isVolatile()) - return SI->getPointerOperand(); - - if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) - if (!CXI->isVolatile()) - return CXI->getPointerOperand(); - - if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) - if (!RMWI->isVolatile()) - return RMWI->getPointerOperand(); - - return nullptr; -} -static const Value *getBasePointerOfAccessPointerOperand(const Instruction *I, - int64_t &BytesOffset, - const DataLayout &DL) { - const Value *Ptr = getPointerOperand(I); +static const Value * +getBasePointerOfAccessPointerOperand(const Instruction *I, int64_t &BytesOffset, + const DataLayout &DL, + bool AllowNonInbounds = false) { + const Value *Ptr = + Attributor::getPointerOperand(I, /* AllowVolatile */ false); if (!Ptr) return nullptr; return GetPointerBaseWithConstantOffset(Ptr, BytesOffset, DL, - /*AllowNonInbounds*/ false); + AllowNonInbounds); } ChangeStatus AbstractAttribute::update(Attributor &A) { @@ -328,7 +420,7 @@ ChangeStatus AbstractAttribute::update(Attributor &A) { } ChangeStatus -IRAttributeManifest::manifestAttrs(Attributor &A, IRPosition &IRP, +IRAttributeManifest::manifestAttrs(Attributor &A, const IRPosition &IRP, const ArrayRef<Attribute> &DeducedAttrs) { Function *ScopeFn = IRP.getAssociatedFunction(); IRPosition::Kind PK = IRP.getPositionKind(); @@ -457,13 +549,20 @@ bool IRPosition::hasAttr(ArrayRef<Attribute::AttrKind> AKs, } void IRPosition::getAttrs(ArrayRef<Attribute::AttrKind> AKs, - SmallVectorImpl<Attribute> &Attrs) const { - for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) + SmallVectorImpl<Attribute> &Attrs, + bool IgnoreSubsumingPositions) const { + for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) { for (Attribute::AttrKind AK : AKs) { const Attribute &Attr = EquivIRP.getAttr(AK); if (Attr.getKindAsEnum() == AK) Attrs.push_back(Attr); } + // The first position returned by the SubsumingPositionIterator is + // always the position itself. If we ignore subsuming positions we + // are done after the first iteration. + if (IgnoreSubsumingPositions) + break; + } } void IRPosition::verify() { @@ -517,38 +616,24 @@ void IRPosition::verify() { } namespace { -/// Helper functions to clamp a state \p S of type \p StateType with the +/// Helper function to clamp a state \p S of type \p StateType with the /// information in \p R and indicate/return if \p S did change (as-in update is /// required to be run again). -/// -///{ template <typename StateType> -ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R); - -template <> -ChangeStatus clampStateAndIndicateChange<IntegerState>(IntegerState &S, - const IntegerState &R) { +ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) { auto Assumed = S.getAssumed(); S ^= R; return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; } -template <> -ChangeStatus clampStateAndIndicateChange<BooleanState>(BooleanState &S, - const BooleanState &R) { - return clampStateAndIndicateChange<IntegerState>(S, R); -} -///} - /// Clamp the information known for all returned values of a function /// (identified by \p QueryingAA) into \p S. template <typename AAType, typename StateType = typename AAType::StateType> static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA, StateType &S) { LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for " - << static_cast<const AbstractAttribute &>(QueryingAA) - << " into " << S << "\n"); + << QueryingAA << " into " << S << "\n"); assert((QueryingAA.getIRPosition().getPositionKind() == IRPosition::IRP_RETURNED || @@ -593,7 +678,8 @@ struct AAComposeTwoGenericDeduction /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - ChangeStatus ChangedF = F<AAType, G<AAType, Base, StateType>, StateType>::updateImpl(A); + ChangeStatus ChangedF = + F<AAType, G<AAType, Base, StateType>, StateType>::updateImpl(A); ChangeStatus ChangedG = G<AAType, Base, StateType>::updateImpl(A); return ChangedF | ChangedG; } @@ -621,8 +707,7 @@ template <typename AAType, typename StateType = typename AAType::StateType> static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, StateType &S) { LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for " - << static_cast<const AbstractAttribute &>(QueryingAA) - << " into " << S << "\n"); + << QueryingAA << " into " << S << "\n"); assert(QueryingAA.getIRPosition().getPositionKind() == IRPosition::IRP_ARGUMENT && @@ -718,7 +803,7 @@ struct AAFromMustBeExecutedContext : public Base { void initialize(Attributor &A) override { Base::initialize(A); - IRPosition &IRP = this->getIRPosition(); + const IRPosition &IRP = this->getIRPosition(); Instruction *CtxI = IRP.getCtxI(); if (!CtxI) @@ -739,21 +824,16 @@ struct AAFromMustBeExecutedContext : public Base { MustBeExecutedContextExplorer &Explorer = A.getInfoCache().getMustBeExecutedContextExplorer(); - SetVector<const Use *> NextUses; - - for (const Use *U : Uses) { + auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); + for (unsigned u = 0; u < Uses.size(); ++u) { + const Use *U = Uses[u]; if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) { - auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); - bool Found = EIt.count(UserI); - while (!Found && ++EIt != EEnd) - Found = EIt.getCurrentInst() == UserI; + bool Found = Explorer.findInContextOf(UserI, EIt, EEnd); if (Found && Base::followUse(A, U, UserI)) for (const Use &Us : UserI->uses()) - NextUses.insert(&Us); + Uses.insert(&Us); } } - for (const Use *U : NextUses) - Uses.insert(U); return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; } @@ -994,13 +1074,15 @@ ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) { auto ReplaceCallSiteUsersWith = [](CallBase &CB, Constant &C) { if (CB.getNumUses() == 0 || CB.isMustTailCall()) return ChangeStatus::UNCHANGED; - CB.replaceAllUsesWith(&C); + replaceAllInstructionUsesWith(CB, C); return ChangeStatus::CHANGED; }; // If the assumed unique return value is an argument, annotate it. if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) { - getIRPosition() = IRPosition::argument(*UniqueRVArg); + // TODO: This should be handled differently! + this->AnchorVal = UniqueRVArg; + this->KindOrArgNo = UniqueRVArg->getArgNo(); Changed = IRAttribute::manifest(A); } else if (auto *RVC = dyn_cast<Constant>(UniqueRV.getValue())) { // We can replace the returned value with the unique returned constant. @@ -1010,14 +1092,18 @@ ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) { if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) if (CB->isCallee(&U)) { Constant *RVCCast = - ConstantExpr::getTruncOrBitCast(RVC, CB->getType()); + CB->getType() == RVC->getType() + ? RVC + : ConstantExpr::getTruncOrBitCast(RVC, CB->getType()); Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed; } } else { assert(isa<CallBase>(AnchorValue) && "Expcected a function or call base anchor!"); Constant *RVCCast = - ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType()); + AnchorValue.getType() == RVC->getType() + ? RVC + : ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType()); Changed = ReplaceCallSiteUsersWith(cast<CallBase>(AnchorValue), *RVCCast); } if (Changed == ChangeStatus::CHANGED) @@ -1157,8 +1243,7 @@ ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) { const auto &RetValAA = A.getAAFor<AAReturnedValues>( *this, IRPosition::function(*CB->getCalledFunction())); LLVM_DEBUG(dbgs() << "[AAReturnedValues] Found another AAReturnedValues: " - << static_cast<const AbstractAttribute &>(RetValAA) - << "\n"); + << RetValAA << "\n"); // Skip dead ends, thus if we do not know anything about the returned // call we mark it as unresolved and it will stay that way. @@ -1393,7 +1478,7 @@ ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) { auto CheckRWInstForNoSync = [&](Instruction &I) { /// We are looking for volatile instructions or Non-Relaxed atomics. - /// FIXME: We should ipmrove the handling of intrinsics. + /// FIXME: We should improve the handling of intrinsics. if (isa<IntrinsicInst>(&I) && isNoSyncIntrinsic(&I)) return true; @@ -1532,6 +1617,115 @@ struct AANoFreeCallSite final : AANoFreeImpl { void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); } }; +/// NoFree attribute for floating values. +struct AANoFreeFloating : AANoFreeImpl { + AANoFreeFloating(const IRPosition &IRP) : AANoFreeImpl(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)} + + /// See Abstract Attribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + const IRPosition &IRP = getIRPosition(); + + const auto &NoFreeAA = + A.getAAFor<AANoFree>(*this, IRPosition::function_scope(IRP)); + if (NoFreeAA.isAssumedNoFree()) + return ChangeStatus::UNCHANGED; + + Value &AssociatedValue = getIRPosition().getAssociatedValue(); + auto Pred = [&](const Use &U, bool &Follow) -> bool { + Instruction *UserI = cast<Instruction>(U.getUser()); + if (auto *CB = dyn_cast<CallBase>(UserI)) { + if (CB->isBundleOperand(&U)) + return false; + if (!CB->isArgOperand(&U)) + return true; + unsigned ArgNo = CB->getArgOperandNo(&U); + + const auto &NoFreeArg = A.getAAFor<AANoFree>( + *this, IRPosition::callsite_argument(*CB, ArgNo)); + return NoFreeArg.isAssumedNoFree(); + } + + if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) || + isa<PHINode>(UserI) || isa<SelectInst>(UserI)) { + Follow = true; + return true; + } + + // Unknown user. + return false; + }; + if (!A.checkForAllUses(Pred, *this, AssociatedValue)) + return indicatePessimisticFixpoint(); + + return ChangeStatus::UNCHANGED; + } +}; + +/// NoFree attribute for a call site argument. +struct AANoFreeArgument final : AANoFreeFloating { + AANoFreeArgument(const IRPosition &IRP) : AANoFreeFloating(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) } +}; + +/// NoFree attribute for call site arguments. +struct AANoFreeCallSiteArgument final : AANoFreeFloating { + AANoFreeCallSiteArgument(const IRPosition &IRP) : AANoFreeFloating(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Once we have call site specific value information we can provide + // call site specific liveness information and then it makes + // sense to specialize attributes for call sites arguments instead of + // redirecting requests to the callee argument. + Argument *Arg = getAssociatedArgument(); + if (!Arg) + return indicatePessimisticFixpoint(); + const IRPosition &ArgPos = IRPosition::argument(*Arg); + auto &ArgAA = A.getAAFor<AANoFree>(*this, ArgPos); + return clampStateAndIndicateChange( + getState(), static_cast<const AANoFree::StateType &>(ArgAA.getState())); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)}; +}; + +/// NoFree attribute for function return value. +struct AANoFreeReturned final : AANoFreeFloating { + AANoFreeReturned(const IRPosition &IRP) : AANoFreeFloating(IRP) { + llvm_unreachable("NoFree is not applicable to function returns!"); + } + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + llvm_unreachable("NoFree is not applicable to function returns!"); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("NoFree is not applicable to function returns!"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override {} +}; + +/// NoFree attribute deduction for a call site return value. +struct AANoFreeCallSiteReturned final : AANoFreeFloating { + AANoFreeCallSiteReturned(const IRPosition &IRP) : AANoFreeFloating(IRP) {} + + ChangeStatus manifest(Attributor &A) override { + return ChangeStatus::UNCHANGED; + } + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) } +}; + /// ------------------------ NonNull Argument Attribute ------------------------ static int64_t getKnownNonNullAndDerefBytesForUse( Attributor &A, AbstractAttribute &QueryingAA, Value &AssociatedValue, @@ -1558,30 +1752,49 @@ static int64_t getKnownNonNullAndDerefBytesForUse( unsigned ArgNo = ICS.getArgumentNo(U); IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo); - auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP); + // As long as we only use known information there is no need to track + // dependences here. + auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP, + /* TrackDependence */ false); IsNonNull |= DerefAA.isKnownNonNull(); return DerefAA.getKnownDereferenceableBytes(); } + // We need to follow common pointer manipulation uses to the accesses they + // feed into. We can try to be smart to avoid looking through things we do not + // like for now, e.g., non-inbounds GEPs. + if (isa<CastInst>(I)) { + TrackUse = true; + return 0; + } + if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) + if (GEP->hasAllConstantIndices()) { + TrackUse = true; + return 0; + } + int64_t Offset; if (const Value *Base = getBasePointerOfAccessPointerOperand(I, Offset, DL)) { - if (Base == &AssociatedValue && getPointerOperand(I) == UseV) { + if (Base == &AssociatedValue && + Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { int64_t DerefBytes = - Offset + (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()); + (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()) + Offset; IsNonNull |= !NullPointerIsDefined; - return DerefBytes; + return std::max(int64_t(0), DerefBytes); } } - if (const Value *Base = - GetPointerBaseWithConstantOffset(UseV, Offset, DL, - /*AllowNonInbounds*/ false)) { - auto &DerefAA = - A.getAAFor<AADereferenceable>(QueryingAA, IRPosition::value(*Base)); - IsNonNull |= (!NullPointerIsDefined && DerefAA.isKnownNonNull()); - IsNonNull |= (!NullPointerIsDefined && (Offset != 0)); - int64_t DerefBytes = DerefAA.getKnownDereferenceableBytes(); - return std::max(int64_t(0), DerefBytes - Offset); + + /// Corner case when an offset is 0. + if (const Value *Base = getBasePointerOfAccessPointerOperand( + I, Offset, DL, /*AllowNonInbounds*/ true)) { + if (Offset == 0 && Base == &AssociatedValue && + Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { + int64_t DerefBytes = + (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()); + IsNonNull |= !NullPointerIsDefined; + return std::max(int64_t(0), DerefBytes); + } } return 0; @@ -1599,6 +1812,8 @@ struct AANonNullImpl : AANonNull { if (!NullIsDefined && hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) indicateOptimisticFixpoint(); + else if (isa<ConstantPointerNull>(getAssociatedValue())) + indicatePessimisticFixpoint(); else AANonNull::initialize(A); } @@ -1609,7 +1824,7 @@ struct AANonNullImpl : AANonNull { bool TrackUse = false; getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse); - takeKnownMaximum(IsNonNull); + setKnown(IsNonNull); return TrackUse; } @@ -1629,24 +1844,6 @@ struct AANonNullFloating using Base = AAFromMustBeExecutedContext<AANonNull, AANonNullImpl>; AANonNullFloating(const IRPosition &IRP) : Base(IRP) {} - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - Base::initialize(A); - - if (isAtFixpoint()) - return; - - const IRPosition &IRP = getIRPosition(); - const Value &V = IRP.getAssociatedValue(); - const DataLayout &DL = A.getDataLayout(); - - // TODO: This context sensitive query should be removed once we can do - // context sensitive queries in the genericValueTraversal below. - if (isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, IRP.getCtxI(), - /* TODO: DT */ nullptr)) - indicateOptimisticFixpoint(); - } - /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { ChangeStatus Change = Base::updateImpl(A); @@ -1654,20 +1851,24 @@ struct AANonNullFloating return Change; if (!NullIsDefined) { - const auto &DerefAA = A.getAAFor<AADereferenceable>(*this, getIRPosition()); + const auto &DerefAA = + A.getAAFor<AADereferenceable>(*this, getIRPosition()); if (DerefAA.getAssumedDereferenceableBytes()) return Change; } const DataLayout &DL = A.getDataLayout(); - auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, + DominatorTree *DT = nullptr; + InformationCache &InfoCache = A.getInfoCache(); + if (const Function *Fn = getAnchorScope()) + DT = InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Fn); + + auto VisitValueCB = [&](Value &V, AANonNull::StateType &T, bool Stripped) -> bool { const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V)); if (!Stripped && this == &AA) { - if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, - /* CtxI */ getCtxI(), - /* TODO: DT */ nullptr)) + if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, getCtxI(), DT)) T.indicatePessimisticFixpoint(); } else { // Use abstract attribute information. @@ -1814,6 +2015,208 @@ struct AANoRecurseCallSite final : AANoRecurseImpl { 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(...). + // through a pointer (i.e. also branches etc.) + ChangeStatus updateImpl(Attributor &A) override { + const size_t UBPrevSize = KnownUBInsts.size(); + const size_t NoUBPrevSize = AssumedNoUBInsts.size(); + + auto InspectMemAccessInstForUB = [&](Instruction &I) { + // Skip instructions that are already saved. + if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I)) + return true; + + // If we reach here, we know we have an instruction + // that accesses memory through a pointer operand, + // for which getPointerOperand() should give it to us. + const Value *PtrOp = + Attributor::getPointerOperand(&I, /* AllowVolatile */ true); + assert(PtrOp && + "Expected pointer operand of memory accessing instruction"); + + // A memory access through a pointer is considered UB + // only if the pointer has constant null value. + // TODO: Expand it to not only check constant values. + if (!isa<ConstantPointerNull>(PtrOp)) { + AssumedNoUBInsts.insert(&I); + return true; + } + const Type *PtrTy = PtrOp->getType(); + + // Because we only consider instructions inside functions, + // assume that a parent function exists. + const Function *F = I.getFunction(); + + // A memory access using constant null pointer is only considered UB + // if null pointer is _not_ defined for the target platform. + if (llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) + AssumedNoUBInsts.insert(&I); + else + KnownUBInsts.insert(&I); + return true; + }; + + auto InspectBrInstForUB = [&](Instruction &I) { + // A conditional branch instruction is considered UB if it has `undef` + // condition. + + // Skip instructions that are already saved. + if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I)) + return true; + + // We know we have a branch instruction. + auto BrInst = cast<BranchInst>(&I); + + // Unconditional branches are never considered UB. + if (BrInst->isUnconditional()) + return true; + + // Either we stopped and the appropriate action was taken, + // or we got back a simplified value to continue. + Optional<Value *> SimplifiedCond = + stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst); + if (!SimplifiedCond.hasValue()) + return true; + AssumedNoUBInsts.insert(&I); + return true; + }; + + A.checkForAllInstructions(InspectMemAccessInstForUB, *this, + {Instruction::Load, Instruction::Store, + Instruction::AtomicCmpXchg, + Instruction::AtomicRMW}); + A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br}); + if (NoUBPrevSize != AssumedNoUBInsts.size() || + UBPrevSize != KnownUBInsts.size()) + return ChangeStatus::CHANGED; + return ChangeStatus::UNCHANGED; + } + + bool isKnownToCauseUB(Instruction *I) const override { + return KnownUBInsts.count(I); + } + + bool isAssumedToCauseUB(Instruction *I) const override { + // In simple words, if an instruction is not in the assumed to _not_ + // cause UB, then it is assumed UB (that includes those + // in the KnownUBInsts set). The rest is boilerplate + // is to ensure that it is one of the instructions we test + // for UB. + + switch (I->getOpcode()) { + case Instruction::Load: + case Instruction::Store: + case Instruction::AtomicCmpXchg: + case Instruction::AtomicRMW: + return !AssumedNoUBInsts.count(I); + case Instruction::Br: { + auto BrInst = cast<BranchInst>(I); + if (BrInst->isUnconditional()) + return false; + return !AssumedNoUBInsts.count(I); + } break; + default: + return false; + } + return false; + } + + ChangeStatus manifest(Attributor &A) override { + if (KnownUBInsts.empty()) + return ChangeStatus::UNCHANGED; + for (Instruction *I : KnownUBInsts) + A.changeToUnreachableAfterManifest(I); + return ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::getAsStr() + const std::string getAsStr() const override { + return getAssumed() ? "undefined-behavior" : "no-ub"; + } + + /// Note: The correctness of this analysis depends on the fact that the + /// following 2 sets will stop changing after some point. + /// "Change" here means that their size changes. + /// The size of each set is monotonically increasing + /// (we only add items to them) and it is upper bounded by the number of + /// instructions in the processed function (we can never save more + /// elements in either set than this number). Hence, at some point, + /// they will stop increasing. + /// Consequently, at some point, both sets will have stopped + /// changing, effectively making the analysis reach a fixpoint. + + /// Note: These 2 sets are disjoint and an instruction can be considered + /// one of 3 things: + /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in + /// the KnownUBInsts set. + /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior + /// has a reason to assume it). + /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior + /// could not find a reason to assume or prove that it can cause UB, + /// hence it assumes it doesn't. We have a set for these instructions + /// so that we don't reprocess them in every update. + /// Note however that instructions in this set may cause UB. + +protected: + /// A set of all live instructions _known_ to cause UB. + SmallPtrSet<Instruction *, 8> KnownUBInsts; + +private: + /// A set of all the (live) instructions that are assumed to _not_ cause UB. + SmallPtrSet<Instruction *, 8> AssumedNoUBInsts; + + // Should be called on updates in which if we're processing an instruction + // \p I that depends on a value \p V, one of the following has to happen: + // - If the value is assumed, then stop. + // - If the value is known but undef, then consider it UB. + // - Otherwise, do specific processing with the simplified value. + // We return None in the first 2 cases to signify that an appropriate + // action was taken and the caller should stop. + // Otherwise, we return the simplified value that the caller should + // use for specific processing. + Optional<Value *> stopOnUndefOrAssumed(Attributor &A, const Value *V, + Instruction *I) { + const auto &ValueSimplifyAA = + A.getAAFor<AAValueSimplify>(*this, IRPosition::value(*V)); + Optional<Value *> SimplifiedV = + ValueSimplifyAA.getAssumedSimplifiedValue(A); + if (!ValueSimplifyAA.isKnown()) { + // Don't depend on assumed values. + return llvm::None; + } + if (!SimplifiedV.hasValue()) { + // If it is known (which we tested above) but it doesn't have a value, + // then we can assume `undef` and hence the instruction is UB. + KnownUBInsts.insert(I); + return llvm::None; + } + Value *Val = SimplifiedV.getValue(); + if (isa<UndefValue>(Val)) { + KnownUBInsts.insert(I); + return llvm::None; + } + return Val; + } +}; + +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) += + KnownUBInsts.size(); + } +}; + /// ------------------------ Will-Return Attributes ---------------------------- // Helper function that checks whether a function has any cycle. @@ -1914,6 +2317,32 @@ struct AAWillReturnCallSite final : AAWillReturnImpl { void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); } }; +/// -------------------AAReachability Attribute-------------------------- + +struct AAReachabilityImpl : AAReachability { + AAReachabilityImpl(const IRPosition &IRP) : AAReachability(IRP) {} + + const std::string getAsStr() const override { + // TODO: Return the number of reachable queries. + return "reachable"; + } + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + return indicatePessimisticFixpoint(); + } +}; + +struct AAReachabilityFunction final : public AAReachabilityImpl { + AAReachabilityFunction(const IRPosition &IRP) : AAReachabilityImpl(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); } +}; + /// ------------------------ NoAlias Argument Attribute ------------------------ struct AANoAliasImpl : AANoAlias { @@ -1954,8 +2383,43 @@ struct AANoAliasFloating final : AANoAliasImpl { /// NoAlias attribute for an argument. struct AANoAliasArgument final : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> { - AANoAliasArgument(const IRPosition &IRP) - : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>(IRP) {} + using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>; + AANoAliasArgument(const IRPosition &IRP) : Base(IRP) {} + + /// See AbstractAttribute::update(...). + ChangeStatus updateImpl(Attributor &A) override { + // We have to make sure no-alias on the argument does not break + // synchronization when this is a callback argument, see also [1] below. + // If synchronization cannot be affected, we delegate to the base updateImpl + // function, otherwise we give up for now. + + // If the function is no-sync, no-alias cannot break synchronization. + const auto &NoSyncAA = A.getAAFor<AANoSync>( + *this, IRPosition::function_scope(getIRPosition())); + if (NoSyncAA.isAssumedNoSync()) + return Base::updateImpl(A); + + // If the argument is read-only, no-alias cannot break synchronization. + const auto &MemBehaviorAA = + A.getAAFor<AAMemoryBehavior>(*this, getIRPosition()); + if (MemBehaviorAA.isAssumedReadOnly()) + return Base::updateImpl(A); + + // If the argument is never passed through callbacks, no-alias cannot break + // synchronization. + if (A.checkForAllCallSites( + [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this, + true)) + return Base::updateImpl(A); + + // TODO: add no-alias but make sure it doesn't break synchronization by + // introducing fake uses. See: + // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel, + // International Workshop on OpenMP 2018, + // http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf + + return indicatePessimisticFixpoint(); + } /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) } @@ -1987,6 +2451,8 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { // (i) Check whether noalias holds in the definition. auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, IRP); + LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] check definition: " << V + << " :: " << NoAliasAA << "\n"); if (!NoAliasAA.isAssumedNoAlias()) return indicatePessimisticFixpoint(); @@ -2008,6 +2474,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { // (iii) Check there is no other pointer argument which could alias with the // value. + // TODO: AbstractCallSite ImmutableCallSite ICS(&getAnchorValue()); for (unsigned i = 0; i < ICS.getNumArgOperands(); i++) { if (getArgNo() == (int)i) @@ -2018,7 +2485,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { if (const Function *F = getAnchorScope()) { if (AAResults *AAR = A.getInfoCache().getAAResultsForFunction(*F)) { - bool IsAliasing = AAR->isNoAlias(&getAssociatedValue(), ArgOp); + bool IsAliasing = !AAR->isNoAlias(&getAssociatedValue(), ArgOp); LLVM_DEBUG(dbgs() << "[Attributor][NoAliasCSArg] Check alias between " "callsite arguments " @@ -2026,7 +2493,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { << getAssociatedValue() << " " << *ArgOp << " => " << (IsAliasing ? "" : "no-") << "alias \n"); - if (IsAliasing) + if (!IsAliasing) continue; } } @@ -2108,42 +2575,229 @@ struct AANoAliasCallSiteReturned final : AANoAliasImpl { /// -------------------AAIsDead Function Attribute----------------------- -struct AAIsDeadImpl : public AAIsDead { - AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {} +struct AAIsDeadValueImpl : public AAIsDead { + AAIsDeadValueImpl(const IRPosition &IRP) : AAIsDead(IRP) {} + + /// See AAIsDead::isAssumedDead(). + bool isAssumedDead() const override { return getAssumed(); } + + /// See AAIsDead::isAssumedDead(BasicBlock *). + bool isAssumedDead(const BasicBlock *BB) const override { return false; } + + /// See AAIsDead::isKnownDead(BasicBlock *). + bool isKnownDead(const BasicBlock *BB) const override { return false; } + + /// See AAIsDead::isAssumedDead(Instruction *I). + bool isAssumedDead(const Instruction *I) const override { + return I == getCtxI() && isAssumedDead(); + } + + /// See AAIsDead::isKnownDead(Instruction *I). + bool isKnownDead(const Instruction *I) const override { + return I == getCtxI() && getKnown(); + } + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return isAssumedDead() ? "assumed-dead" : "assumed-live"; + } +}; + +struct AAIsDeadFloating : public AAIsDeadValueImpl { + AAIsDeadFloating(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - const Function *F = getAssociatedFunction(); - if (F && !F->isDeclaration()) - exploreFromEntry(A, F); + if (Instruction *I = dyn_cast<Instruction>(&getAssociatedValue())) + if (!wouldInstructionBeTriviallyDead(I)) + indicatePessimisticFixpoint(); + if (isa<UndefValue>(getAssociatedValue())) + indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + auto UsePred = [&](const Use &U, bool &Follow) { + Instruction *UserI = cast<Instruction>(U.getUser()); + if (CallSite CS = CallSite(UserI)) { + if (!CS.isArgOperand(&U)) + return false; + const IRPosition &CSArgPos = + IRPosition::callsite_argument(CS, CS.getArgumentNo(&U)); + const auto &CSArgIsDead = A.getAAFor<AAIsDead>(*this, CSArgPos); + return CSArgIsDead.isAssumedDead(); + } + if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) { + const IRPosition &RetPos = IRPosition::returned(*RI->getFunction()); + const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, RetPos); + return RetIsDeadAA.isAssumedDead(); + } + Follow = true; + return wouldInstructionBeTriviallyDead(UserI); + }; + + if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) + return indicatePessimisticFixpoint(); + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + Value &V = getAssociatedValue(); + if (auto *I = dyn_cast<Instruction>(&V)) + if (wouldInstructionBeTriviallyDead(I)) { + A.deleteAfterManifest(*I); + return ChangeStatus::CHANGED; + } + + if (V.use_empty()) + return ChangeStatus::UNCHANGED; + + UndefValue &UV = *UndefValue::get(V.getType()); + bool AnyChange = A.changeValueAfterManifest(V, UV); + return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; } - void exploreFromEntry(Attributor &A, const Function *F) { - ToBeExploredPaths.insert(&(F->getEntryBlock().front())); + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(IsDead) + } +}; - for (size_t i = 0; i < ToBeExploredPaths.size(); ++i) - if (const Instruction *NextNoReturnI = - findNextNoReturn(A, ToBeExploredPaths[i])) - NoReturnCalls.insert(NextNoReturnI); +struct AAIsDeadArgument : public AAIsDeadFloating { + AAIsDeadArgument(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} - // Mark the block live after we looked for no-return instructions. - assumeLive(A, F->getEntryBlock()); + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (!getAssociatedFunction()->hasExactDefinition()) + indicatePessimisticFixpoint(); } - /// Find the next assumed noreturn instruction in the block of \p I starting - /// from, thus including, \p I. - /// - /// The caller is responsible to monitor the ToBeExploredPaths set as new - /// instructions discovered in other basic block will be placed in there. - /// - /// \returns The next assumed noreturn instructions in the block of \p I - /// starting from, thus including, \p I. - const Instruction *findNextNoReturn(Attributor &A, const Instruction *I); + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Changed = AAIsDeadFloating::manifest(A); + Argument &Arg = *getAssociatedArgument(); + if (Arg.getParent()->hasLocalLinkage()) + if (A.registerFunctionSignatureRewrite( + Arg, /* ReplacementTypes */ {}, + Attributor::ArgumentReplacementInfo::CalleeRepairCBTy{}, + Attributor::ArgumentReplacementInfo::ACSRepairCBTy{})) + return ChangeStatus::CHANGED; + return Changed; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) } +}; + +struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl { + AAIsDeadCallSiteArgument(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (isa<UndefValue>(getAssociatedValue())) + indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Once we have call site specific value information we can provide + // call site specific liveness information and then it makes + // sense to specialize attributes for call sites arguments instead of + // redirecting requests to the callee argument. + Argument *Arg = getAssociatedArgument(); + if (!Arg) + return indicatePessimisticFixpoint(); + const IRPosition &ArgPos = IRPosition::argument(*Arg); + auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos); + return clampStateAndIndicateChange( + getState(), static_cast<const AAIsDead::StateType &>(ArgAA.getState())); + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + CallBase &CB = cast<CallBase>(getAnchorValue()); + Use &U = CB.getArgOperandUse(getArgNo()); + assert(!isa<UndefValue>(U.get()) && + "Expected undef values to be filtered out!"); + UndefValue &UV = *UndefValue::get(U->getType()); + if (A.changeUseAfterManifest(U, UV)) + return ChangeStatus::CHANGED; + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) } +}; + +struct AAIsDeadReturned : public AAIsDeadValueImpl { + AAIsDeadReturned(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + + auto PredForCallSite = [&](AbstractCallSite ACS) { + if (ACS.isCallbackCall()) + return false; + const IRPosition &CSRetPos = + IRPosition::callsite_returned(ACS.getCallSite()); + const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, CSRetPos); + return RetIsDeadAA.isAssumedDead(); + }; + + if (!A.checkForAllCallSites(PredForCallSite, *this, true)) + return indicatePessimisticFixpoint(); + + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + // TODO: Rewrite the signature to return void? + bool AnyChange = false; + UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType()); + auto RetInstPred = [&](Instruction &I) { + ReturnInst &RI = cast<ReturnInst>(I); + if (!isa<UndefValue>(RI.getReturnValue())) + AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV); + return true; + }; + A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret}); + return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) } +}; + +struct AAIsDeadCallSiteReturned : public AAIsDeadFloating { + AAIsDeadCallSiteReturned(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(IsDead) } +}; + +struct AAIsDeadFunction : public AAIsDead { + AAIsDeadFunction(const IRPosition &IRP) : AAIsDead(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + const Function *F = getAssociatedFunction(); + if (F && !F->isDeclaration()) { + ToBeExploredFrom.insert(&F->getEntryBlock().front()); + assumeLive(A, F->getEntryBlock()); + } + } /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" + - std::to_string(getAssociatedFunction()->size()) + "][#NRI " + - std::to_string(NoReturnCalls.size()) + "]"; + std::to_string(getAssociatedFunction()->size()) + "][#TBEP " + + std::to_string(ToBeExploredFrom.size()) + "][#KDE " + + std::to_string(KnownDeadEnds.size()) + "]"; } /// See AbstractAttribute::manifest(...). @@ -2164,73 +2818,22 @@ struct AAIsDeadImpl : public AAIsDead { // function allows to catch asynchronous exceptions. bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F); - for (const Instruction *NRC : NoReturnCalls) { - Instruction *I = const_cast<Instruction *>(NRC); - BasicBlock *BB = I->getParent(); - Instruction *SplitPos = I->getNextNode(); - // TODO: mark stuff before unreachable instructions as dead. - - if (auto *II = dyn_cast<InvokeInst>(I)) { - // If we keep the invoke the split position is at the beginning of the - // normal desitination block (it invokes a noreturn function after all). - BasicBlock *NormalDestBB = II->getNormalDest(); - SplitPos = &NormalDestBB->front(); - - /// Invoke is replaced with a call and unreachable is placed after it if - /// the callee is nounwind and noreturn. Otherwise, we keep the invoke - /// and only place an unreachable in the normal successor. - if (Invoke2CallAllowed) { - if (II->getCalledFunction()) { - const IRPosition &IPos = IRPosition::callsite_function(*II); - const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos); - if (AANoUnw.isAssumedNoUnwind()) { - LLVM_DEBUG(dbgs() - << "[AAIsDead] Replace invoke with call inst\n"); - // We do not need an invoke (II) but instead want a call followed - // by an unreachable. However, we do not remove II as other - // abstract attributes might have it cached as part of their - // results. Given that we modify the CFG anyway, we simply keep II - // around but in a new dead block. To avoid II being live through - // a different edge we have to ensure the block we place it in is - // only reached from the current block of II and then not reached - // at all when we insert the unreachable. - SplitBlockPredecessors(NormalDestBB, {BB}, ".i2c"); - CallInst *CI = createCallMatchingInvoke(II); - CI->insertBefore(II); - CI->takeName(II); - II->replaceAllUsesWith(CI); - SplitPos = CI->getNextNode(); - } - } - } - - if (SplitPos == &NormalDestBB->front()) { - // If this is an invoke of a noreturn function the edge to the normal - // destination block is dead but not necessarily the block itself. - // TODO: We need to move to an edge based system during deduction and - // also manifest. - assert(!NormalDestBB->isLandingPad() && - "Expected the normal destination not to be a landingpad!"); - if (NormalDestBB->getUniquePredecessor() == BB) { - assumeLive(A, *NormalDestBB); - } else { - BasicBlock *SplitBB = - SplitBlockPredecessors(NormalDestBB, {BB}, ".dead"); - // The split block is live even if it contains only an unreachable - // instruction at the end. - assumeLive(A, *SplitBB); - SplitPos = SplitBB->getTerminator(); - HasChanged = ChangeStatus::CHANGED; - } - } - } - - if (isa_and_nonnull<UnreachableInst>(SplitPos)) + KnownDeadEnds.set_union(ToBeExploredFrom); + for (const Instruction *DeadEndI : KnownDeadEnds) { + auto *CB = dyn_cast<CallBase>(DeadEndI); + if (!CB) + continue; + const auto &NoReturnAA = + A.getAAFor<AANoReturn>(*this, IRPosition::callsite_function(*CB)); + bool MayReturn = !NoReturnAA.isAssumedNoReturn(); + if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB))) continue; - BB = SplitPos->getParent(); - SplitBlock(BB, SplitPos); - changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false); + if (auto *II = dyn_cast<InvokeInst>(DeadEndI)) + A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II)); + else + A.changeToUnreachableAfterManifest( + const_cast<Instruction *>(DeadEndI->getNextNode())); HasChanged = ChangeStatus::CHANGED; } @@ -2244,6 +2847,12 @@ struct AAIsDeadImpl : public AAIsDead { /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override {} + + /// Returns true if the function is assumed dead. + bool isAssumedDead() const override { return false; } + /// See AAIsDead::isAssumedDead(BasicBlock *). bool isAssumedDead(const BasicBlock *BB) const override { assert(BB->getParent() == getAssociatedFunction() && @@ -2272,8 +2881,14 @@ struct AAIsDeadImpl : public AAIsDead { if (!AssumedLiveBlocks.count(I->getParent())) return true; - // If it is not after a noreturn call, than it is live. - return isAfterNoReturn(I); + // If it is not after a liveness barrier it is live. + const Instruction *PrevI = I->getPrevNode(); + while (PrevI) { + if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI)) + return true; + PrevI = PrevI->getPrevNode(); + } + return false; } /// See AAIsDead::isKnownDead(Instruction *I). @@ -2281,9 +2896,6 @@ struct AAIsDeadImpl : public AAIsDead { return getKnown() && isAssumedDead(I); } - /// Check if instruction is after noreturn call, in other words, assumed dead. - bool isAfterNoReturn(const Instruction *I) const; - /// Determine if \p F might catch asynchronous exceptions. static bool mayCatchAsynchronousExceptions(const Function &F) { return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F); @@ -2291,9 +2903,9 @@ struct AAIsDeadImpl : public AAIsDead { /// Assume \p BB is (partially) live now and indicate to the Attributor \p A /// that internal function called from \p BB should now be looked at. - void assumeLive(Attributor &A, const BasicBlock &BB) { + bool assumeLive(Attributor &A, const BasicBlock &BB) { if (!AssumedLiveBlocks.insert(&BB).second) - return; + return false; // We assume that all of BB is (probably) live now and if there are calls to // internal functions we will assume that those are now live as well. This @@ -2304,140 +2916,219 @@ struct AAIsDeadImpl : public AAIsDead { if (const Function *F = ICS.getCalledFunction()) if (F->hasLocalLinkage()) A.markLiveInternalFunction(*F); + return true; } - /// Collection of to be explored paths. - SmallSetVector<const Instruction *, 8> ToBeExploredPaths; + /// Collection of instructions that need to be explored again, e.g., we + /// did assume they do not transfer control to (one of their) successors. + SmallSetVector<const Instruction *, 8> ToBeExploredFrom; + + /// Collection of instructions that are known to not transfer control. + SmallSetVector<const Instruction *, 8> KnownDeadEnds; /// Collection of all assumed live BasicBlocks. DenseSet<const BasicBlock *> AssumedLiveBlocks; - - /// Collection of calls with noreturn attribute, assumed or knwon. - SmallSetVector<const Instruction *, 4> NoReturnCalls; }; -struct AAIsDeadFunction final : public AAIsDeadImpl { - AAIsDeadFunction(const IRPosition &IRP) : AAIsDeadImpl(IRP) {} +static bool +identifyAliveSuccessors(Attributor &A, const CallBase &CB, + AbstractAttribute &AA, + SmallVectorImpl<const Instruction *> &AliveSuccessors) { + const IRPosition &IPos = IRPosition::callsite_function(CB); + + const auto &NoReturnAA = A.getAAFor<AANoReturn>(AA, IPos); + if (NoReturnAA.isAssumedNoReturn()) + return !NoReturnAA.isKnownNoReturn(); + if (CB.isTerminator()) + AliveSuccessors.push_back(&CB.getSuccessor(0)->front()); + else + AliveSuccessors.push_back(CB.getNextNode()); + return false; +} - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { - STATS_DECL(PartiallyDeadBlocks, Function, - "Number of basic blocks classified as partially dead"); - BUILD_STAT_NAME(PartiallyDeadBlocks, Function) += NoReturnCalls.size(); +static bool +identifyAliveSuccessors(Attributor &A, const InvokeInst &II, + AbstractAttribute &AA, + SmallVectorImpl<const Instruction *> &AliveSuccessors) { + bool UsedAssumedInformation = + identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors); + + // First, determine if we can change an invoke to a call assuming the + // callee is nounwind. This is not possible if the personality of the + // function allows to catch asynchronous exceptions. + if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) { + AliveSuccessors.push_back(&II.getUnwindDest()->front()); + } else { + const IRPosition &IPos = IRPosition::callsite_function(II); + const auto &AANoUnw = A.getAAFor<AANoUnwind>(AA, IPos); + if (AANoUnw.isAssumedNoUnwind()) { + UsedAssumedInformation |= !AANoUnw.isKnownNoUnwind(); + } else { + AliveSuccessors.push_back(&II.getUnwindDest()->front()); + } } -}; + return UsedAssumedInformation; +} -bool AAIsDeadImpl::isAfterNoReturn(const Instruction *I) const { - const Instruction *PrevI = I->getPrevNode(); - while (PrevI) { - if (NoReturnCalls.count(PrevI)) - return true; - PrevI = PrevI->getPrevNode(); +static Optional<ConstantInt *> +getAssumedConstant(Attributor &A, const Value &V, AbstractAttribute &AA, + bool &UsedAssumedInformation) { + const auto &ValueSimplifyAA = + A.getAAFor<AAValueSimplify>(AA, IRPosition::value(V)); + Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(A); + UsedAssumedInformation |= !ValueSimplifyAA.isKnown(); + if (!SimplifiedV.hasValue()) + return llvm::None; + if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) + return llvm::None; + return dyn_cast_or_null<ConstantInt>(SimplifiedV.getValue()); +} + +static bool +identifyAliveSuccessors(Attributor &A, const BranchInst &BI, + AbstractAttribute &AA, + SmallVectorImpl<const Instruction *> &AliveSuccessors) { + bool UsedAssumedInformation = false; + if (BI.getNumSuccessors() == 1) { + AliveSuccessors.push_back(&BI.getSuccessor(0)->front()); + } else { + Optional<ConstantInt *> CI = + getAssumedConstant(A, *BI.getCondition(), AA, UsedAssumedInformation); + if (!CI.hasValue()) { + // No value yet, assume both edges are dead. + } else if (CI.getValue()) { + const BasicBlock *SuccBB = + BI.getSuccessor(1 - CI.getValue()->getZExtValue()); + AliveSuccessors.push_back(&SuccBB->front()); + } else { + AliveSuccessors.push_back(&BI.getSuccessor(0)->front()); + AliveSuccessors.push_back(&BI.getSuccessor(1)->front()); + UsedAssumedInformation = false; + } } - return false; + return UsedAssumedInformation; } -const Instruction *AAIsDeadImpl::findNextNoReturn(Attributor &A, - const Instruction *I) { - const BasicBlock *BB = I->getParent(); - const Function &F = *BB->getParent(); - - // Flag to determine if we can change an invoke to a call assuming the callee - // is nounwind. This is not possible if the personality of the function allows - // to catch asynchronous exceptions. - bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F); - - // TODO: We should have a function that determines if an "edge" is dead. - // Edges could be from an instruction to the next or from a terminator - // to the successor. For now, we need to special case the unwind block - // of InvokeInst below. - - while (I) { - ImmutableCallSite ICS(I); - - if (ICS) { - const IRPosition &IPos = IRPosition::callsite_function(ICS); - // Regarless of the no-return property of an invoke instruction we only - // learn that the regular successor is not reachable through this - // instruction but the unwind block might still be. - if (auto *Invoke = dyn_cast<InvokeInst>(I)) { - // Use nounwind to justify the unwind block is dead as well. - const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos); - if (!Invoke2CallAllowed || !AANoUnw.isAssumedNoUnwind()) { - assumeLive(A, *Invoke->getUnwindDest()); - ToBeExploredPaths.insert(&Invoke->getUnwindDest()->front()); - } +static bool +identifyAliveSuccessors(Attributor &A, const SwitchInst &SI, + AbstractAttribute &AA, + SmallVectorImpl<const Instruction *> &AliveSuccessors) { + bool UsedAssumedInformation = false; + Optional<ConstantInt *> CI = + getAssumedConstant(A, *SI.getCondition(), AA, UsedAssumedInformation); + if (!CI.hasValue()) { + // No value yet, assume all edges are dead. + } else if (CI.getValue()) { + for (auto &CaseIt : SI.cases()) { + if (CaseIt.getCaseValue() == CI.getValue()) { + AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front()); + return UsedAssumedInformation; } - - const auto &NoReturnAA = A.getAAFor<AANoReturn>(*this, IPos); - if (NoReturnAA.isAssumedNoReturn()) - return I; } - - I = I->getNextNode(); + AliveSuccessors.push_back(&SI.getDefaultDest()->front()); + return UsedAssumedInformation; + } else { + for (const BasicBlock *SuccBB : successors(SI.getParent())) + AliveSuccessors.push_back(&SuccBB->front()); } + return UsedAssumedInformation; +} - // get new paths (reachable blocks). - for (const BasicBlock *SuccBB : successors(BB)) { - assumeLive(A, *SuccBB); - ToBeExploredPaths.insert(&SuccBB->front()); - } +ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { + ChangeStatus Change = ChangeStatus::UNCHANGED; - // No noreturn instruction found. - return nullptr; -} + LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/" + << getAssociatedFunction()->size() << "] BBs and " + << ToBeExploredFrom.size() << " exploration points and " + << KnownDeadEnds.size() << " known dead ends\n"); -ChangeStatus AAIsDeadImpl::updateImpl(Attributor &A) { - ChangeStatus Status = ChangeStatus::UNCHANGED; + // Copy and clear the list of instructions we need to explore from. It is + // refilled with instructions the next update has to look at. + SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(), + ToBeExploredFrom.end()); + decltype(ToBeExploredFrom) NewToBeExploredFrom; - // Temporary collection to iterate over existing noreturn instructions. This - // will alow easier modification of NoReturnCalls collection - SmallVector<const Instruction *, 8> NoReturnChanged; + SmallVector<const Instruction *, 8> AliveSuccessors; + while (!Worklist.empty()) { + const Instruction *I = Worklist.pop_back_val(); + LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n"); - for (const Instruction *I : NoReturnCalls) - NoReturnChanged.push_back(I); + AliveSuccessors.clear(); - for (const Instruction *I : NoReturnChanged) { - size_t Size = ToBeExploredPaths.size(); + bool UsedAssumedInformation = false; + switch (I->getOpcode()) { + // TODO: look for (assumed) UB to backwards propagate "deadness". + default: + if (I->isTerminator()) { + for (const BasicBlock *SuccBB : successors(I->getParent())) + AliveSuccessors.push_back(&SuccBB->front()); + } else { + AliveSuccessors.push_back(I->getNextNode()); + } + break; + case Instruction::Call: + UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I), + *this, AliveSuccessors); + break; + case Instruction::Invoke: + UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I), + *this, AliveSuccessors); + break; + case Instruction::Br: + UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I), + *this, AliveSuccessors); + break; + case Instruction::Switch: + UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I), + *this, AliveSuccessors); + break; + } - const Instruction *NextNoReturnI = findNextNoReturn(A, I); - if (NextNoReturnI != I) { - Status = ChangeStatus::CHANGED; - NoReturnCalls.remove(I); - if (NextNoReturnI) - NoReturnCalls.insert(NextNoReturnI); + if (UsedAssumedInformation) { + NewToBeExploredFrom.insert(I); + } else { + Change = ChangeStatus::CHANGED; + if (AliveSuccessors.empty() || + (I->isTerminator() && AliveSuccessors.size() < I->getNumSuccessors())) + KnownDeadEnds.insert(I); } - // Explore new paths. - while (Size != ToBeExploredPaths.size()) { - Status = ChangeStatus::CHANGED; - if (const Instruction *NextNoReturnI = - findNextNoReturn(A, ToBeExploredPaths[Size++])) - NoReturnCalls.insert(NextNoReturnI); + LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: " + << AliveSuccessors.size() << " UsedAssumedInformation: " + << UsedAssumedInformation << "\n"); + + for (const Instruction *AliveSuccessor : AliveSuccessors) { + if (!I->isTerminator()) { + assert(AliveSuccessors.size() == 1 && + "Non-terminator expected to have a single successor!"); + Worklist.push_back(AliveSuccessor); + } else { + if (assumeLive(A, *AliveSuccessor->getParent())) + Worklist.push_back(AliveSuccessor); + } } } - LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: " - << AssumedLiveBlocks.size() << " Total number of blocks: " - << getAssociatedFunction()->size() << "\n"); + ToBeExploredFrom = std::move(NewToBeExploredFrom); // If we know everything is live there is no need to query for liveness. - if (NoReturnCalls.empty() && - getAssociatedFunction()->size() == AssumedLiveBlocks.size()) { - // Indicating a pessimistic fixpoint will cause the state to be "invalid" - // which will cause the Attributor to not return the AAIsDead on request, - // which will prevent us from querying isAssumedDead(). - indicatePessimisticFixpoint(); - assert(!isValidState() && "Expected an invalid state!"); - Status = ChangeStatus::CHANGED; - } - - return Status; + // Instead, indicating a pessimistic fixpoint will cause the state to be + // "invalid" and all queries to be answered conservatively without lookups. + // To be in this state we have to (1) finished the exploration and (3) not + // discovered any non-trivial dead end and (2) not ruled unreachable code + // dead. + if (ToBeExploredFrom.empty() && + getAssociatedFunction()->size() == AssumedLiveBlocks.size() && + llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) { + return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0; + })) + return indicatePessimisticFixpoint(); + return Change; } /// Liveness information for a call sites. -struct AAIsDeadCallSite final : AAIsDeadImpl { - AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadImpl(IRP) {} +struct AAIsDeadCallSite final : AAIsDeadFunction { + AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadFunction(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { @@ -2463,10 +3154,9 @@ struct AAIsDeadCallSite final : AAIsDeadImpl { template <> ChangeStatus clampStateAndIndicateChange<DerefState>(DerefState &S, const DerefState &R) { - ChangeStatus CS0 = clampStateAndIndicateChange<IntegerState>( - S.DerefBytesState, R.DerefBytesState); - ChangeStatus CS1 = - clampStateAndIndicateChange<IntegerState>(S.GlobalState, R.GlobalState); + ChangeStatus CS0 = + clampStateAndIndicateChange(S.DerefBytesState, R.DerefBytesState); + ChangeStatus CS1 = clampStateAndIndicateChange(S.GlobalState, R.GlobalState); return CS0 | CS1; } @@ -2496,16 +3186,49 @@ struct AADereferenceableImpl : AADereferenceable { const StateType &getState() const override { return *this; } /// } + /// Helper function for collecting accessed bytes in must-be-executed-context + void addAccessedBytesForUse(Attributor &A, const Use *U, + const Instruction *I) { + const Value *UseV = U->get(); + if (!UseV->getType()->isPointerTy()) + return; + + Type *PtrTy = UseV->getType(); + const DataLayout &DL = A.getDataLayout(); + int64_t Offset; + if (const Value *Base = getBasePointerOfAccessPointerOperand( + I, Offset, DL, /*AllowNonInbounds*/ true)) { + if (Base == &getAssociatedValue() && + Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { + uint64_t Size = DL.getTypeStoreSize(PtrTy->getPointerElementType()); + addAccessedBytes(Offset, Size); + } + } + return; + } + /// See AAFromMustBeExecutedContext bool followUse(Attributor &A, const Use *U, const Instruction *I) { bool IsNonNull = false; bool TrackUse = false; int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse( A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse); + + addAccessedBytesForUse(A, U, I); takeKnownDerefBytesMaximum(DerefBytes); return TrackUse; } + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Change = AADereferenceable::manifest(A); + if (isAssumedNonNull() && hasAttr(Attribute::DereferenceableOrNull)) { + removeAttrs({Attribute::DereferenceableOrNull}); + return ChangeStatus::CHANGED; + } + return Change; + } + void getDeducedAttributes(LLVMContext &Ctx, SmallVectorImpl<Attribute> &Attrs) const override { // TODO: Add *_globally support @@ -2564,6 +3287,8 @@ struct AADereferenceableFloating T.GlobalState &= DS.GlobalState; } + // TODO: Use `AAConstantRange` to infer dereferenceable bytes. + // For now we do not try to "increase" dereferenceability due to negative // indices as we first have to come up with code to deal with loops and // for overflows of the dereferenceable bytes. @@ -2654,30 +3379,6 @@ struct AADereferenceableCallSiteReturned final AADereferenceable, AADereferenceableImpl>; AADereferenceableCallSiteReturned(const IRPosition &IRP) : Base(IRP) {} - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - Base::initialize(A); - Function *F = getAssociatedFunction(); - if (!F) - indicatePessimisticFixpoint(); - } - - /// See AbstractAttribute::updateImpl(...). - ChangeStatus updateImpl(Attributor &A) override { - // TODO: Once we have call site specific value information we can provide - // call site specific liveness information and then it makes - // sense to specialize attributes for call sites arguments instead of - // redirecting requests to the callee argument. - - ChangeStatus Change = Base::updateImpl(A); - Function *F = getAssociatedFunction(); - const IRPosition &FnPos = IRPosition::returned(*F); - auto &FnAA = A.getAAFor<AADereferenceable>(*this, FnPos); - return Change | - clampStateAndIndicateChange( - getState(), static_cast<const DerefState &>(FnAA.getState())); - } - /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(dereferenceable); @@ -2686,16 +3387,69 @@ struct AADereferenceableCallSiteReturned final // ------------------------ Align Argument Attribute ------------------------ +static unsigned int getKnownAlignForUse(Attributor &A, + AbstractAttribute &QueryingAA, + Value &AssociatedValue, const Use *U, + const Instruction *I, bool &TrackUse) { + // We need to follow common pointer manipulation uses to the accesses they + // feed into. + if (isa<CastInst>(I)) { + // Follow all but ptr2int casts. + TrackUse = !isa<PtrToIntInst>(I); + return 0; + } + if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) { + if (GEP->hasAllConstantIndices()) { + TrackUse = true; + return 0; + } + } + + unsigned Alignment = 0; + if (ImmutableCallSite ICS = ImmutableCallSite(I)) { + if (ICS.isBundleOperand(U) || ICS.isCallee(U)) + return 0; + + unsigned ArgNo = ICS.getArgumentNo(U); + IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo); + // As long as we only use known information there is no need to track + // dependences here. + auto &AlignAA = A.getAAFor<AAAlign>(QueryingAA, IRP, + /* TrackDependence */ false); + Alignment = AlignAA.getKnownAlign(); + } + + const Value *UseV = U->get(); + if (auto *SI = dyn_cast<StoreInst>(I)) + Alignment = SI->getAlignment(); + else if (auto *LI = dyn_cast<LoadInst>(I)) + Alignment = LI->getAlignment(); + + if (Alignment <= 1) + return 0; + + auto &DL = A.getDataLayout(); + int64_t Offset; + + if (const Value *Base = GetPointerBaseWithConstantOffset(UseV, Offset, DL)) { + if (Base == &AssociatedValue) { + // BasePointerAddr + Offset = Alignment * Q for some integer Q. + // So we can say that the maximum power of two which is a divisor of + // gcd(Offset, Alignment) is an alignment. + + uint32_t gcd = + greatestCommonDivisor(uint32_t(abs((int32_t)Offset)), Alignment); + Alignment = llvm::PowerOf2Floor(gcd); + } + } + + return Alignment; +} struct AAAlignImpl : AAAlign { AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {} - // Max alignemnt value allowed in IR - static const unsigned MAX_ALIGN = 1U << 29; - /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - takeAssumedMinimum(MAX_ALIGN); - SmallVector<Attribute, 4> Attrs; getAttrs({Attribute::Alignment}, Attrs); for (const Attribute &Attr : Attrs) @@ -2718,7 +3472,7 @@ struct AAAlignImpl : AAAlign { if (SI->getPointerOperand() == &AnchorVal) if (SI->getAlignment() < getAssumedAlign()) { STATS_DECLTRACK(AAAlign, Store, - "Number of times alignemnt added to a store"); + "Number of times alignment added to a store"); SI->setAlignment(Align(getAssumedAlign())); Changed = ChangeStatus::CHANGED; } @@ -2727,7 +3481,7 @@ struct AAAlignImpl : AAAlign { if (LI->getAlignment() < getAssumedAlign()) { LI->setAlignment(Align(getAssumedAlign())); STATS_DECLTRACK(AAAlign, Load, - "Number of times alignemnt added to a load"); + "Number of times alignment added to a load"); Changed = ChangeStatus::CHANGED; } } @@ -2748,6 +3502,16 @@ struct AAAlignImpl : AAAlign { Attrs.emplace_back( Attribute::getWithAlignment(Ctx, Align(getAssumedAlign()))); } + /// See AAFromMustBeExecutedContext + bool followUse(Attributor &A, const Use *U, const Instruction *I) { + bool TrackUse = false; + + unsigned int KnownAlign = + getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse); + takeKnownMaximum(KnownAlign); + + return TrackUse; + } /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { @@ -2758,11 +3522,14 @@ struct AAAlignImpl : AAAlign { }; /// Align attribute for a floating value. -struct AAAlignFloating : AAAlignImpl { - AAAlignFloating(const IRPosition &IRP) : AAAlignImpl(IRP) {} +struct AAAlignFloating : AAFromMustBeExecutedContext<AAAlign, AAAlignImpl> { + using Base = AAFromMustBeExecutedContext<AAAlign, AAAlignImpl>; + AAAlignFloating(const IRPosition &IRP) : Base(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { + Base::updateImpl(A); + const DataLayout &DL = A.getDataLayout(); auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, @@ -2808,9 +3575,12 @@ struct AAAlignReturned final /// Align attribute for function argument. struct AAAlignArgument final - : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl> { + : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AAAlign, + AAAlignImpl> { AAAlignArgument(const IRPosition &IRP) - : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl>(IRP) {} + : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AAAlign, + AAAlignImpl>( + IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(aligned) } @@ -2824,35 +3594,39 @@ struct AAAlignCallSiteArgument final : AAAlignFloating { return AAAlignImpl::manifest(A); } + /// See AbstractAttribute::updateImpl(Attributor &A). + ChangeStatus updateImpl(Attributor &A) override { + ChangeStatus Changed = AAAlignFloating::updateImpl(A); + if (Argument *Arg = getAssociatedArgument()) { + const auto &ArgAlignAA = A.getAAFor<AAAlign>( + *this, IRPosition::argument(*Arg), /* TrackDependence */ false, + DepClassTy::OPTIONAL); + takeKnownMaximum(ArgAlignAA.getKnownAlign()); + } + return Changed; + } + /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) } }; /// Align attribute deduction for a call site return value. -struct AAAlignCallSiteReturned final : AAAlignImpl { - AAAlignCallSiteReturned(const IRPosition &IRP) : AAAlignImpl(IRP) {} +struct AAAlignCallSiteReturned final + : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AAAlign, + AAAlignImpl> { + using Base = + AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AAAlign, + AAAlignImpl>; + AAAlignCallSiteReturned(const IRPosition &IRP) : Base(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - AAAlignImpl::initialize(A); + Base::initialize(A); Function *F = getAssociatedFunction(); if (!F) indicatePessimisticFixpoint(); } - /// See AbstractAttribute::updateImpl(...). - ChangeStatus updateImpl(Attributor &A) override { - // TODO: Once we have call site specific value information we can provide - // call site specific liveness information and then it makes - // sense to specialize attributes for call sites arguments instead of - // redirecting requests to the callee argument. - Function *F = getAssociatedFunction(); - const IRPosition &FnPos = IRPosition::returned(*F); - auto &FnAA = A.getAAFor<AAAlign>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), static_cast<const AAAlign::StateType &>(FnAA.getState())); - } - /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(align); } }; @@ -2865,7 +3639,7 @@ struct AANoReturnImpl : public AANoReturn { void initialize(Attributor &A) override { AANoReturn::initialize(A); Function *F = getAssociatedFunction(); - if (!F || F->hasFnAttribute(Attribute::WillReturn)) + if (!F) indicatePessimisticFixpoint(); } @@ -2876,9 +3650,6 @@ struct AANoReturnImpl : public AANoReturn { /// See AbstractAttribute::updateImpl(Attributor &A). virtual ChangeStatus updateImpl(Attributor &A) override { - const auto &WillReturnAA = A.getAAFor<AAWillReturn>(*this, getIRPosition()); - if (WillReturnAA.isKnownWillReturn()) - return indicatePessimisticFixpoint(); auto CheckForNoReturn = [](Instruction &) { return false; }; if (!A.checkForAllInstructions(CheckForNoReturn, *this, {(unsigned)Instruction::Ret})) @@ -2924,7 +3695,16 @@ struct AANoCaptureImpl : public AANoCapture { /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - AANoCapture::initialize(A); + if (hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ true)) { + indicateOptimisticFixpoint(); + return; + } + Function *AnchorScope = getAnchorScope(); + if (isFnInterfaceKind() && + (!AnchorScope || !AnchorScope->hasExactDefinition())) { + indicatePessimisticFixpoint(); + return; + } // You cannot "capture" null in the default address space. if (isa<ConstantPointerNull>(getAssociatedValue()) && @@ -2933,13 +3713,11 @@ struct AANoCaptureImpl : public AANoCapture { return; } - const IRPosition &IRP = getIRPosition(); - const Function *F = - getArgNo() >= 0 ? IRP.getAssociatedFunction() : IRP.getAnchorScope(); + const Function *F = getArgNo() >= 0 ? getAssociatedFunction() : AnchorScope; // Check what state the associated function can actually capture. if (F) - determineFunctionCaptureCapabilities(IRP, *F, *this); + determineFunctionCaptureCapabilities(getIRPosition(), *F, *this); else indicatePessimisticFixpoint(); } @@ -2967,7 +3745,7 @@ struct AANoCaptureImpl : public AANoCapture { /// state in memory and through "returning/throwing", respectively. static void determineFunctionCaptureCapabilities(const IRPosition &IRP, const Function &F, - IntegerState &State) { + BitIntegerState &State) { // TODO: Once we have memory behavior attributes we should use them here. // If we know we cannot communicate or write to memory, we do not care about @@ -2992,7 +3770,7 @@ struct AANoCaptureImpl : public AANoCapture { // Check existing "returned" attributes. int ArgNo = IRP.getArgNo(); if (F.doesNotThrow() && ArgNo >= 0) { - for (unsigned u = 0, e = F.arg_size(); u< e; ++u) + for (unsigned u = 0, e = F.arg_size(); u < e; ++u) if (F.hasParamAttribute(u, Attribute::Returned)) { if (u == unsigned(ArgNo)) State.removeAssumedBits(NOT_CAPTURED_IN_RET); @@ -3036,7 +3814,7 @@ struct AACaptureUseTracker final : public CaptureTracker { /// the search is stopped with \p CapturedInMemory and \p CapturedInInteger /// conservatively set to true. AACaptureUseTracker(Attributor &A, AANoCapture &NoCaptureAA, - const AAIsDead &IsDeadAA, IntegerState &State, + const AAIsDead &IsDeadAA, AANoCapture::StateType &State, SmallVectorImpl<const Value *> &PotentialCopies, unsigned &RemainingUsesToExplore) : A(A), NoCaptureAA(NoCaptureAA), IsDeadAA(IsDeadAA), State(State), @@ -3155,7 +3933,7 @@ private: const AAIsDead &IsDeadAA; /// The state currently updated. - IntegerState &State; + AANoCapture::StateType &State; /// Set of potential copies of the tracked value. SmallVectorImpl<const Value *> &PotentialCopies; @@ -3238,9 +4016,11 @@ ChangeStatus AANoCaptureImpl::updateImpl(Attributor &A) { while (T.isAssumed(NO_CAPTURE_MAYBE_RETURNED) && Idx < PotentialCopies.size()) Tracker.valueMayBeCaptured(PotentialCopies[Idx++]); - AAAlign::StateType &S = getState(); + AANoCapture::StateType &S = getState(); auto Assumed = S.getAssumed(); S.intersectAssumedBits(T.getAssumed()); + if (!isAssumedNoCaptureMaybeReturned()) + return indicatePessimisticFixpoint(); return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; } @@ -3257,6 +4037,14 @@ struct AANoCaptureArgument final : AANoCaptureImpl { struct AANoCaptureCallSiteArgument final : AANoCaptureImpl { AANoCaptureCallSiteArgument(const IRPosition &IRP) : AANoCaptureImpl(IRP) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (Argument *Arg = getAssociatedArgument()) + if (Arg->hasByValAttr()) + indicateOptimisticFixpoint(); + AANoCaptureImpl::initialize(A); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { // TODO: Once we have call site specific value information we can provide @@ -3375,6 +4163,28 @@ struct AAValueSimplifyImpl : AAValueSimplify { return true; } + bool askSimplifiedValueForAAValueConstantRange(Attributor &A) { + if (!getAssociatedValue().getType()->isIntegerTy()) + return false; + + const auto &ValueConstantRangeAA = + A.getAAFor<AAValueConstantRange>(*this, getIRPosition()); + + Optional<ConstantInt *> COpt = + ValueConstantRangeAA.getAssumedConstantInt(A); + if (COpt.hasValue()) { + if (auto *C = COpt.getValue()) + SimplifiedAssociatedValue = C; + else + return false; + } else { + // FIXME: It should be llvm::None but if you set llvm::None, + // values are mistakenly infered as `undef` now. + SimplifiedAssociatedValue = &getAssociatedValue(); + } + return true; + } + /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { ChangeStatus Changed = ChangeStatus::UNCHANGED; @@ -3389,7 +4199,7 @@ struct AAValueSimplifyImpl : AAValueSimplify { if (!V.user_empty() && &V != C && V.getType() == C->getType()) { LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C << "\n"); - V.replaceAllUsesWith(C); + A.changeValueAfterManifest(V, *C); Changed = ChangeStatus::CHANGED; } } @@ -3397,6 +4207,15 @@ struct AAValueSimplifyImpl : AAValueSimplify { return Changed | AAValueSimplify::manifest(A); } + /// See AbstractState::indicatePessimisticFixpoint(...). + ChangeStatus indicatePessimisticFixpoint() override { + // NOTE: Associated value will be returned in a pessimistic fixpoint and is + // regarded as known. That's why`indicateOptimisticFixpoint` is called. + SimplifiedAssociatedValue = &getAssociatedValue(); + indicateOptimisticFixpoint(); + return ChangeStatus::CHANGED; + } + protected: // An assumed simplified value. Initially, it is set to Optional::None, which // means that the value is not clear under current assumption. If in the @@ -3408,20 +4227,49 @@ protected: struct AAValueSimplifyArgument final : AAValueSimplifyImpl { AAValueSimplifyArgument(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} + void initialize(Attributor &A) override { + AAValueSimplifyImpl::initialize(A); + if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration()) + indicatePessimisticFixpoint(); + if (hasAttr({Attribute::InAlloca, Attribute::StructRet, Attribute::Nest}, + /* IgnoreSubsumingPositions */ true)) + indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { + // Byval is only replacable if it is readonly otherwise we would write into + // the replaced value and not the copy that byval creates implicitly. + Argument *Arg = getAssociatedArgument(); + if (Arg->hasByValAttr()) { + const auto &MemAA = A.getAAFor<AAMemoryBehavior>(*this, getIRPosition()); + if (!MemAA.isAssumedReadOnly()) + return indicatePessimisticFixpoint(); + } + bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); auto PredForCallSite = [&](AbstractCallSite ACS) { // Check if we have an associated argument or not (which can happen for // callback calls). - if (Value *ArgOp = ACS.getCallArgOperand(getArgNo())) - return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue); - return false; + Value *ArgOp = ACS.getCallArgOperand(getArgNo()); + if (!ArgOp) + return false; + // We can only propagate thread independent values through callbacks. + // This is different to direct/indirect call sites because for them we + // know the thread executing the caller and callee is the same. For + // callbacks this is not guaranteed, thus a thread dependent value could + // be different for the caller and callee, making it invalid to propagate. + if (ACS.isCallbackCall()) + if (auto *C = dyn_cast<Constant>(ArgOp)) + if (C->isThreadDependent()) + return false; + return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue); }; if (!A.checkForAllCallSites(PredForCallSite, *this, true)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -3447,7 +4295,8 @@ struct AAValueSimplifyReturned : AAValueSimplifyImpl { }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -3468,7 +4317,7 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { Value &V = getAnchorValue(); // TODO: add other stuffs - if (isa<Constant>(V) || isa<UndefValue>(V)) + if (isa<Constant>(V)) indicatePessimisticFixpoint(); } @@ -3480,10 +4329,10 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { auto &AA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V)); if (!Stripped && this == &AA) { // TODO: Look the instruction and check recursively. + LLVM_DEBUG( dbgs() << "[Attributor][ValueSimplify] Can't be stripped more : " << V << "\n"); - indicatePessimisticFixpoint(); return false; } return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); @@ -3492,7 +4341,8 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { if (!genericValueTraversal<AAValueSimplify, BooleanState>( A, getIRPosition(), *this, static_cast<BooleanState &>(*this), VisitValueCB)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -3601,7 +4451,7 @@ struct AAHeapToStackImpl : public AAHeapToStack { AI = new BitCastInst(AI, MallocCall->getType(), "malloc_bc", AI->getNextNode()); - MallocCall->replaceAllUsesWith(AI); + replaceAllInstructionUsesWith(*MallocCall, *AI); if (auto *II = dyn_cast<InvokeInst>(MallocCall)) { auto *NBB = II->getNormalDest(); @@ -3645,76 +4495,80 @@ ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) { const Function *F = getAssociatedFunction(); const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F); - auto UsesCheck = [&](Instruction &I) { - SmallPtrSet<const Use *, 8> Visited; - SmallVector<const Use *, 8> Worklist; - - for (Use &U : I.uses()) - Worklist.push_back(&U); + MustBeExecutedContextExplorer &Explorer = + A.getInfoCache().getMustBeExecutedContextExplorer(); - while (!Worklist.empty()) { - const Use *U = Worklist.pop_back_val(); - if (!Visited.insert(U).second) - continue; - - auto *UserI = U->getUser(); + auto FreeCheck = [&](Instruction &I) { + const auto &Frees = FreesForMalloc.lookup(&I); + if (Frees.size() != 1) + return false; + Instruction *UniqueFree = *Frees.begin(); + return Explorer.findInContextOf(UniqueFree, I.getNextNode()); + }; + auto UsesCheck = [&](Instruction &I) { + bool ValidUsesOnly = true; + bool MustUse = true; + auto Pred = [&](const Use &U, bool &Follow) -> bool { + Instruction *UserI = cast<Instruction>(U.getUser()); if (isa<LoadInst>(UserI)) - continue; + return true; if (auto *SI = dyn_cast<StoreInst>(UserI)) { - if (SI->getValueOperand() == U->get()) { - LLVM_DEBUG(dbgs() << "[H2S] escaping store to memory: " << *UserI << "\n"); - return false; + if (SI->getValueOperand() == U.get()) { + LLVM_DEBUG(dbgs() + << "[H2S] escaping store to memory: " << *UserI << "\n"); + ValidUsesOnly = false; + } else { + // A store into the malloc'ed memory is fine. } - // A store into the malloc'ed memory is fine. - continue; + return true; } - - // NOTE: Right now, if a function that has malloc pointer as an argument - // frees memory, we assume that the malloc pointer is freed. - - // TODO: Add nofree callsite argument attribute to indicate that pointer - // argument is not freed. if (auto *CB = dyn_cast<CallBase>(UserI)) { - if (!CB->isArgOperand(U)) - continue; - - if (CB->isLifetimeStartOrEnd()) - continue; - + if (!CB->isArgOperand(&U) || CB->isLifetimeStartOrEnd()) + return true; // Record malloc. if (isFreeCall(UserI, TLI)) { - FreesForMalloc[&I].insert( - cast<Instruction>(const_cast<User *>(UserI))); - continue; + if (MustUse) { + FreesForMalloc[&I].insert(UserI); + } else { + LLVM_DEBUG(dbgs() << "[H2S] free potentially on different mallocs: " + << *UserI << "\n"); + ValidUsesOnly = false; + } + return true; } - // If a function does not free memory we are fine - const auto &NoFreeAA = - A.getAAFor<AANoFree>(*this, IRPosition::callsite_function(*CB)); + unsigned ArgNo = CB->getArgOperandNo(&U); - unsigned ArgNo = U - CB->arg_begin(); const auto &NoCaptureAA = A.getAAFor<AANoCapture>( *this, IRPosition::callsite_argument(*CB, ArgNo)); - if (!NoCaptureAA.isAssumedNoCapture() || !NoFreeAA.isAssumedNoFree()) { + // If a callsite argument use is nofree, we are fine. + const auto &ArgNoFreeAA = A.getAAFor<AANoFree>( + *this, IRPosition::callsite_argument(*CB, ArgNo)); + + if (!NoCaptureAA.isAssumedNoCapture() || + !ArgNoFreeAA.isAssumedNoFree()) { LLVM_DEBUG(dbgs() << "[H2S] Bad user: " << *UserI << "\n"); - return false; + ValidUsesOnly = false; } - continue; + return true; } - if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI)) { - for (Use &U : UserI->uses()) - Worklist.push_back(&U); - continue; + if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) || + isa<PHINode>(UserI) || isa<SelectInst>(UserI)) { + MustUse &= !(isa<PHINode>(UserI) || isa<SelectInst>(UserI)); + Follow = true; + return true; } - - // Unknown user. + // Unknown user for which we can not track uses further (in a way that + // makes sense). LLVM_DEBUG(dbgs() << "[H2S] Unknown user: " << *UserI << "\n"); - return false; - } - return true; + ValidUsesOnly = false; + return true; + }; + A.checkForAllUses(Pred, *this, I); + return ValidUsesOnly; }; auto MallocCallocCheck = [&](Instruction &I) { @@ -3730,8 +4584,8 @@ ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) { if (IsMalloc) { if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(0))) - if (Size->getValue().sle(MaxHeapToStackSize)) - if (UsesCheck(I)) { + if (Size->getValue().ule(MaxHeapToStackSize)) + if (UsesCheck(I) || FreeCheck(I)) { MallocCalls.insert(&I); return true; } @@ -3740,8 +4594,8 @@ ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) { if (auto *Num = dyn_cast<ConstantInt>(I.getOperand(0))) if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(1))) if ((Size->getValue().umul_ov(Num->getValue(), Overflow)) - .sle(MaxHeapToStackSize)) - if (!Overflow && UsesCheck(I)) { + .ule(MaxHeapToStackSize)) + if (!Overflow && (UsesCheck(I) || FreeCheck(I))) { MallocCalls.insert(&I); return true; } @@ -3767,8 +4621,10 @@ struct AAHeapToStackFunction final : public AAHeapToStackImpl { /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECL(MallocCalls, Function, - "Number of MallocCalls converted to allocas"); - BUILD_STAT_NAME(MallocCalls, Function) += MallocCalls.size(); + "Number of malloc calls converted to allocas"); + for (auto *C : MallocCalls) + if (!BadMallocCalls.count(C)) + ++BUILD_STAT_NAME(MallocCalls, Function); } }; @@ -3787,9 +4643,10 @@ struct AAMemoryBehaviorImpl : public AAMemoryBehavior { /// Return the memory behavior information encoded in the IR for \p IRP. static void getKnownStateFromValue(const IRPosition &IRP, - IntegerState &State) { + BitIntegerState &State, + bool IgnoreSubsumingPositions = false) { SmallVector<Attribute, 2> Attrs; - IRP.getAttrs(AttrKinds, Attrs); + IRP.getAttrs(AttrKinds, Attrs, IgnoreSubsumingPositions); for (const Attribute &Attr : Attrs) { switch (Attr.getKindAsEnum()) { case Attribute::ReadNone: @@ -3829,7 +4686,7 @@ struct AAMemoryBehaviorImpl : public AAMemoryBehavior { /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { - IRPosition &IRP = getIRPosition(); + const IRPosition &IRP = getIRPosition(); // Check if we would improve the existing attributes first. SmallVector<Attribute, 4> DeducedAttrs; @@ -3911,12 +4768,25 @@ struct AAMemoryBehaviorArgument : AAMemoryBehaviorFloating { /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - AAMemoryBehaviorFloating::initialize(A); + intersectAssumedBits(BEST_STATE); + const IRPosition &IRP = getIRPosition(); + // TODO: Make IgnoreSubsumingPositions a property of an IRAttribute so we + // can query it when we use has/getAttr. That would allow us to reuse the + // initialize of the base class here. + bool HasByVal = + IRP.hasAttr({Attribute::ByVal}, /* IgnoreSubsumingPositions */ true); + getKnownStateFromValue(IRP, getState(), + /* IgnoreSubsumingPositions */ HasByVal); // Initialize the use vector with all direct uses of the associated value. Argument *Arg = getAssociatedArgument(); - if (!Arg || !Arg->getParent()->hasExactDefinition()) + if (!Arg || !Arg->getParent()->hasExactDefinition()) { indicatePessimisticFixpoint(); + } else { + // Initialize the use vector with all direct uses of the associated value. + for (const Use &U : Arg->uses()) + Uses.insert(&U); + } } ChangeStatus manifest(Attributor &A) override { @@ -3929,7 +4799,6 @@ struct AAMemoryBehaviorArgument : AAMemoryBehaviorFloating { return AAMemoryBehaviorFloating::manifest(A); } - /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { if (isAssumedReadNone()) @@ -3945,6 +4814,19 @@ struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument { AAMemoryBehaviorCallSiteArgument(const IRPosition &IRP) : AAMemoryBehaviorArgument(IRP) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (Argument *Arg = getAssociatedArgument()) { + if (Arg->hasByValAttr()) { + addKnownBits(NO_WRITES); + removeKnownBits(NO_READS); + removeAssumedBits(NO_READS); + } + } else { + } + AAMemoryBehaviorArgument::initialize(A); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { // TODO: Once we have call site specific value information we can provide @@ -3956,7 +4838,7 @@ struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument { auto &ArgAA = A.getAAFor<AAMemoryBehavior>(*this, ArgPos); return clampStateAndIndicateChange( getState(), - static_cast<const AANoCapture::StateType &>(ArgAA.getState())); + static_cast<const AAMemoryBehavior::StateType &>(ArgAA.getState())); } /// See AbstractAttribute::trackStatistics() @@ -4036,7 +4918,8 @@ struct AAMemoryBehaviorCallSite final : AAMemoryBehaviorImpl { const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); return clampStateAndIndicateChange( - getState(), static_cast<const AAAlign::StateType &>(FnAA.getState())); + getState(), + static_cast<const AAMemoryBehavior::StateType &>(FnAA.getState())); } /// See AbstractAttribute::trackStatistics() @@ -4090,19 +4973,26 @@ ChangeStatus AAMemoryBehaviorFloating::updateImpl(Attributor &A) { // First, check the function scope. We take the known information and we avoid // work if the assumed information implies the current assumed information for - // this attribute. - const auto &FnMemAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); - S.addKnownBits(FnMemAA.getKnown()); - if ((S.getAssumed() & FnMemAA.getAssumed()) == S.getAssumed()) - return ChangeStatus::UNCHANGED; + // this attribute. This is a valid for all but byval arguments. + Argument *Arg = IRP.getAssociatedArgument(); + AAMemoryBehavior::base_t FnMemAssumedState = + AAMemoryBehavior::StateType::getWorstState(); + if (!Arg || !Arg->hasByValAttr()) { + const auto &FnMemAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); + FnMemAssumedState = FnMemAA.getAssumed(); + S.addKnownBits(FnMemAA.getKnown()); + if ((S.getAssumed() & FnMemAA.getAssumed()) == S.getAssumed()) + return ChangeStatus::UNCHANGED; + } // Make sure the value is not captured (except through "return"), if // it is, any information derived would be irrelevant anyway as we cannot // check the potential aliases introduced by the capture. However, no need // to fall back to anythign less optimistic than the function state. - const auto &ArgNoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP); + const auto &ArgNoCaptureAA = A.getAAFor<AANoCapture>( + *this, IRP, /* TrackDependence */ true, DepClassTy::OPTIONAL); if (!ArgNoCaptureAA.isAssumedNoCaptureMaybeReturned()) { - S.intersectAssumedBits(FnMemAA.getAssumed()); + S.intersectAssumedBits(FnMemAssumedState); return ChangeStatus::CHANGED; } @@ -4223,7 +5113,451 @@ void AAMemoryBehaviorFloating::analyzeUseIn(Attributor &A, const Use *U, if (UserI->mayWriteToMemory()) removeAssumedBits(NO_WRITES); } +/// ------------------ Value Constant Range Attribute ------------------------- + +struct AAValueConstantRangeImpl : AAValueConstantRange { + using StateType = IntegerRangeState; + AAValueConstantRangeImpl(const IRPosition &IRP) : AAValueConstantRange(IRP) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + std::string Str; + llvm::raw_string_ostream OS(Str); + OS << "range(" << getBitWidth() << ")<"; + getKnown().print(OS); + OS << " / "; + getAssumed().print(OS); + OS << ">"; + return OS.str(); + } + + /// Helper function to get a SCEV expr for the associated value at program + /// point \p I. + const SCEV *getSCEV(Attributor &A, const Instruction *I = nullptr) const { + if (!getAnchorScope()) + return nullptr; + + ScalarEvolution *SE = + A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>( + *getAnchorScope()); + + LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>( + *getAnchorScope()); + + if (!SE || !LI) + return nullptr; + + const SCEV *S = SE->getSCEV(&getAssociatedValue()); + if (!I) + return S; + + return SE->getSCEVAtScope(S, LI->getLoopFor(I->getParent())); + } + + /// Helper function to get a range from SCEV for the associated value at + /// program point \p I. + ConstantRange getConstantRangeFromSCEV(Attributor &A, + const Instruction *I = nullptr) const { + if (!getAnchorScope()) + return getWorstState(getBitWidth()); + + ScalarEvolution *SE = + A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>( + *getAnchorScope()); + + const SCEV *S = getSCEV(A, I); + if (!SE || !S) + return getWorstState(getBitWidth()); + + return SE->getUnsignedRange(S); + } + + /// Helper function to get a range from LVI for the associated value at + /// program point \p I. + ConstantRange + getConstantRangeFromLVI(Attributor &A, + const Instruction *CtxI = nullptr) const { + if (!getAnchorScope()) + return getWorstState(getBitWidth()); + + LazyValueInfo *LVI = + A.getInfoCache().getAnalysisResultForFunction<LazyValueAnalysis>( + *getAnchorScope()); + + if (!LVI || !CtxI) + return getWorstState(getBitWidth()); + return LVI->getConstantRange(&getAssociatedValue(), + const_cast<BasicBlock *>(CtxI->getParent()), + const_cast<Instruction *>(CtxI)); + } + + /// See AAValueConstantRange::getKnownConstantRange(..). + ConstantRange + getKnownConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const override { + if (!CtxI || CtxI == getCtxI()) + return getKnown(); + + ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); + ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); + return getKnown().intersectWith(SCEVR).intersectWith(LVIR); + } + + /// See AAValueConstantRange::getAssumedConstantRange(..). + ConstantRange + getAssumedConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const override { + // TODO: Make SCEV use Attributor assumption. + // We may be able to bound a variable range via assumptions in + // Attributor. ex.) If x is assumed to be in [1, 3] and y is known to + // evolve to x^2 + x, then we can say that y is in [2, 12]. + + if (!CtxI || CtxI == getCtxI()) + return getAssumed(); + + ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); + ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); + return getAssumed().intersectWith(SCEVR).intersectWith(LVIR); + } + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + // Intersect a range given by SCEV. + intersectKnown(getConstantRangeFromSCEV(A, getCtxI())); + + // Intersect a range given by LVI. + intersectKnown(getConstantRangeFromLVI(A, getCtxI())); + } + + /// Helper function to create MDNode for range metadata. + static MDNode * + getMDNodeForConstantRange(Type *Ty, LLVMContext &Ctx, + const ConstantRange &AssumedConstantRange) { + Metadata *LowAndHigh[] = {ConstantAsMetadata::get(ConstantInt::get( + Ty, AssumedConstantRange.getLower())), + ConstantAsMetadata::get(ConstantInt::get( + Ty, AssumedConstantRange.getUpper()))}; + return MDNode::get(Ctx, LowAndHigh); + } + + /// Return true if \p Assumed is included in \p KnownRanges. + static bool isBetterRange(const ConstantRange &Assumed, MDNode *KnownRanges) { + + if (Assumed.isFullSet()) + return false; + + if (!KnownRanges) + return true; + + // If multiple ranges are annotated in IR, we give up to annotate assumed + // range for now. + + // TODO: If there exists a known range which containts assumed range, we + // can say assumed range is better. + if (KnownRanges->getNumOperands() > 2) + return false; + + ConstantInt *Lower = + mdconst::extract<ConstantInt>(KnownRanges->getOperand(0)); + ConstantInt *Upper = + mdconst::extract<ConstantInt>(KnownRanges->getOperand(1)); + + ConstantRange Known(Lower->getValue(), Upper->getValue()); + return Known.contains(Assumed) && Known != Assumed; + } + + /// Helper function to set range metadata. + static bool + setRangeMetadataIfisBetterRange(Instruction *I, + const ConstantRange &AssumedConstantRange) { + auto *OldRangeMD = I->getMetadata(LLVMContext::MD_range); + if (isBetterRange(AssumedConstantRange, OldRangeMD)) { + if (!AssumedConstantRange.isEmptySet()) { + I->setMetadata(LLVMContext::MD_range, + getMDNodeForConstantRange(I->getType(), I->getContext(), + AssumedConstantRange)); + return true; + } + } + return false; + } + + /// See AbstractAttribute::manifest() + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + ConstantRange AssumedConstantRange = getAssumedConstantRange(A); + assert(!AssumedConstantRange.isFullSet() && "Invalid state"); + + auto &V = getAssociatedValue(); + if (!AssumedConstantRange.isEmptySet() && + !AssumedConstantRange.isSingleElement()) { + if (Instruction *I = dyn_cast<Instruction>(&V)) + if (isa<CallInst>(I) || isa<LoadInst>(I)) + if (setRangeMetadataIfisBetterRange(I, AssumedConstantRange)) + Changed = ChangeStatus::CHANGED; + } + + return Changed; + } +}; + +struct AAValueConstantRangeArgument final : public AAValueConstantRangeImpl { + + AAValueConstantRangeArgument(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Use AAArgumentFromCallSiteArguments + + IntegerRangeState S(getBitWidth()); + clampCallSiteArgumentStates<AAValueConstantRange, IntegerRangeState>( + A, *this, S); + + // TODO: If we know we visited all incoming values, thus no are assumed + // dead, we can take the known information from the state T. + return clampStateAndIndicateChange<IntegerRangeState>(this->getState(), S); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(value_range) + } +}; + +struct AAValueConstantRangeReturned : AAValueConstantRangeImpl { + AAValueConstantRangeReturned(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Use AAReturnedFromReturnedValues + + // TODO: If we know we visited all returned values, thus no are assumed + // dead, we can take the known information from the state T. + + IntegerRangeState S(getBitWidth()); + + clampReturnedValueStates<AAValueConstantRange, IntegerRangeState>(A, *this, + S); + return clampStateAndIndicateChange<StateType>(this->getState(), S); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(value_range) + } +}; + +struct AAValueConstantRangeFloating : AAValueConstantRangeImpl { + AAValueConstantRangeFloating(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AAValueConstantRange::initialize(A); + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast<ConstantInt>(&V)) { + unionAssumed(ConstantRange(C->getValue())); + indicateOptimisticFixpoint(); + return; + } + + if (isa<UndefValue>(&V)) { + indicateOptimisticFixpoint(); + return; + } + + if (auto *I = dyn_cast<Instruction>(&V)) + if (isa<BinaryOperator>(I) || isa<CmpInst>(I)) { + Value *LHS = I->getOperand(0); + Value *RHS = I->getOperand(1); + + if (LHS->getType()->isIntegerTy() && RHS->getType()->isIntegerTy()) + return; + } + + // If it is a load instruction with range metadata, use it. + if (LoadInst *LI = dyn_cast<LoadInst>(&V)) + if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) { + intersectKnown(getConstantRangeFromMetadata(*RangeMD)); + return; + } + + // Otherwise we give up. + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[Attributor][AAValueConstantRange] We give up: " + << getAssociatedValue()); + } + + bool calculateBinaryOperator(Attributor &A, BinaryOperator *BinOp, + IntegerRangeState &T, Instruction *CtxI) { + Value *LHS = BinOp->getOperand(0); + Value *RHS = BinOp->getOperand(1); + + auto &LHSAA = + A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS)); + auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); + + auto &RHSAA = + A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS)); + auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); + + auto AssumedRange = LHSAARange.binaryOp(BinOp->getOpcode(), RHSAARange); + + T.unionAssumed(AssumedRange); + + // TODO: Track a known state too. + + return T.isValidState(); + } + + bool calculateCmpInst(Attributor &A, CmpInst *CmpI, IntegerRangeState &T, + Instruction *CtxI) { + Value *LHS = CmpI->getOperand(0); + Value *RHS = CmpI->getOperand(1); + + auto &LHSAA = + A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS)); + auto &RHSAA = + A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS)); + + auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); + auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); + + // If one of them is empty set, we can't decide. + if (LHSAARange.isEmptySet() || RHSAARange.isEmptySet()) + return true; + + bool MustTrue = false, MustFalse = false; + + auto AllowedRegion = + ConstantRange::makeAllowedICmpRegion(CmpI->getPredicate(), RHSAARange); + + auto SatisfyingRegion = ConstantRange::makeSatisfyingICmpRegion( + CmpI->getPredicate(), RHSAARange); + + if (AllowedRegion.intersectWith(LHSAARange).isEmptySet()) + MustFalse = true; + + if (SatisfyingRegion.contains(LHSAARange)) + MustTrue = true; + + assert((!MustTrue || !MustFalse) && + "Either MustTrue or MustFalse should be false!"); + + if (MustTrue) + T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 1))); + else if (MustFalse) + T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 0))); + else + T.unionAssumed(ConstantRange(/* BitWidth */ 1, /* isFullSet */ true)); + + LLVM_DEBUG(dbgs() << "[AAValueConstantRange] " << *CmpI << " " << LHSAA + << " " << RHSAA << "\n"); + + // TODO: Track a known state too. + return T.isValidState(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + Instruction *CtxI = getCtxI(); + auto VisitValueCB = [&](Value &V, IntegerRangeState &T, + bool Stripped) -> bool { + Instruction *I = dyn_cast<Instruction>(&V); + if (!I) { + + // If the value is not instruction, we query AA to Attributor. + const auto &AA = + A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(V)); + + // Clamp operator is not used to utilize a program point CtxI. + T.unionAssumed(AA.getAssumedConstantRange(A, CtxI)); + + return T.isValidState(); + } + + if (auto *BinOp = dyn_cast<BinaryOperator>(I)) + return calculateBinaryOperator(A, BinOp, T, CtxI); + else if (auto *CmpI = dyn_cast<CmpInst>(I)) + return calculateCmpInst(A, CmpI, T, CtxI); + else { + // Give up with other instructions. + // TODO: Add other instructions + T.indicatePessimisticFixpoint(); + return false; + } + }; + + IntegerRangeState T(getBitWidth()); + + if (!genericValueTraversal<AAValueConstantRange, IntegerRangeState>( + A, getIRPosition(), *this, T, VisitValueCB)) + return indicatePessimisticFixpoint(); + + return clampStateAndIndicateChange(getState(), T); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(value_range) + } +}; + +struct AAValueConstantRangeFunction : AAValueConstantRangeImpl { + AAValueConstantRangeFunction(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("AAValueConstantRange(Function|CallSite)::updateImpl will " + "not be called"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(value_range) } +}; + +struct AAValueConstantRangeCallSite : AAValueConstantRangeFunction { + AAValueConstantRangeCallSite(const IRPosition &IRP) + : AAValueConstantRangeFunction(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(value_range) } +}; + +struct AAValueConstantRangeCallSiteReturned : AAValueConstantRangeReturned { + AAValueConstantRangeCallSiteReturned(const IRPosition &IRP) + : AAValueConstantRangeReturned(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + // If it is a load instruction with range metadata, use the metadata. + if (CallInst *CI = dyn_cast<CallInst>(&getAssociatedValue())) + if (auto *RangeMD = CI->getMetadata(LLVMContext::MD_range)) + intersectKnown(getConstantRangeFromMetadata(*RangeMD)); + + AAValueConstantRangeReturned::initialize(A); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(value_range) + } +}; +struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating { + AAValueConstantRangeCallSiteArgument(const IRPosition &IRP) + : AAValueConstantRangeFloating(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(value_range) + } +}; /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -4234,6 +5568,8 @@ bool Attributor::isAssumedDead(const AbstractAttribute &AA, if (!CtxI) return false; + // TODO: Find a good way to utilize fine and coarse grained liveness + // information. if (!LivenessAA) LivenessAA = &getAAFor<AAIsDead>(AA, IRPosition::function(*CtxI->getFunction()), @@ -4247,7 +5583,58 @@ bool Attributor::isAssumedDead(const AbstractAttribute &AA, return false; // We actually used liveness information so we have to record a dependence. - recordDependence(*LivenessAA, AA); + recordDependence(*LivenessAA, AA, DepClassTy::OPTIONAL); + + return true; +} + +bool Attributor::checkForAllUses( + const function_ref<bool(const Use &, bool &)> &Pred, + const AbstractAttribute &QueryingAA, const Value &V) { + const IRPosition &IRP = QueryingAA.getIRPosition(); + SmallVector<const Use *, 16> Worklist; + SmallPtrSet<const Use *, 16> Visited; + + for (const Use &U : V.uses()) + Worklist.push_back(&U); + + LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size() + << " initial uses to check\n"); + + if (Worklist.empty()) + return true; + + bool AnyDead = false; + const Function *ScopeFn = IRP.getAnchorScope(); + const auto *LivenessAA = + ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn), + /* TrackDependence */ false) + : nullptr; + + while (!Worklist.empty()) { + const Use *U = Worklist.pop_back_val(); + if (!Visited.insert(U).second) + continue; + LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << "\n"); + if (Instruction *UserI = dyn_cast<Instruction>(U->getUser())) + if (LivenessAA && LivenessAA->isAssumedDead(UserI)) { + LLVM_DEBUG(dbgs() << "[Attributor] Dead user: " << *UserI << ": " + << *LivenessAA << "\n"); + AnyDead = true; + continue; + } + + bool Follow = false; + if (!Pred(*U, Follow)) + return false; + if (!Follow) + continue; + for (const Use &UU : U->getUser()->uses()) + Worklist.push_back(&UU); + } + + if (AnyDead) + recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL); return true; } @@ -4284,10 +5671,12 @@ bool Attributor::checkForAllCallSites( for (const Use &U : Fn.uses()) { AbstractCallSite ACS(&U); if (!ACS) { - LLVM_DEBUG(dbgs() << "[Attributor] Function " - << Fn.getName() + LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName() << " has non call site use " << *U.get() << " in " << *U.getUser() << "\n"); + // BlockAddress users are allowed. + if (isa<BlockAddress>(U.getUser())) + continue; return false; } @@ -4296,14 +5685,14 @@ bool Attributor::checkForAllCallSites( const auto *LivenessAA = lookupAAFor<AAIsDead>(IRPosition::function(*Caller), QueryingAA, - /* TrackDependence */ false); + /* TrackDependence */ false); // Skip dead calls. if (LivenessAA && LivenessAA->isAssumedDead(I)) { // We actually used liveness information so we have to record a // dependence. if (QueryingAA) - recordDependence(*LivenessAA, *QueryingAA); + recordDependence(*LivenessAA, *QueryingAA, DepClassTy::OPTIONAL); continue; } @@ -4313,8 +5702,7 @@ bool Attributor::checkForAllCallSites( if (!RequireAllCallSites) continue; LLVM_DEBUG(dbgs() << "[Attributor] User " << EffectiveUse->getUser() - << " is an invalid use of " - << Fn.getName() << "\n"); + << " is an invalid use of " << Fn.getName() << "\n"); return false; } @@ -4417,7 +5805,7 @@ bool Attributor::checkForAllInstructions( // If we actually used liveness information so we have to record a dependence. if (AnyDead) - recordDependence(LivenessAA, QueryingAA); + recordDependence(LivenessAA, QueryingAA, DepClassTy::OPTIONAL); return true; } @@ -4451,7 +5839,7 @@ bool Attributor::checkForAllReadWriteInstructions( // If we actually used liveness information so we have to record a dependence. if (AnyDead) - recordDependence(LivenessAA, QueryingAA); + recordDependence(LivenessAA, QueryingAA, DepClassTy::OPTIONAL); return true; } @@ -4467,7 +5855,7 @@ ChangeStatus Attributor::run(Module &M) { unsigned IterationCounter = 1; SmallVector<AbstractAttribute *, 64> ChangedAAs; - SetVector<AbstractAttribute *> Worklist; + SetVector<AbstractAttribute *> Worklist, InvalidAAs; Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end()); bool RecomputeDependences = false; @@ -4478,6 +5866,29 @@ ChangeStatus Attributor::run(Module &M) { LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter << ", Worklist size: " << Worklist.size() << "\n"); + // For invalid AAs we can fix dependent AAs that have a required dependence, + // thereby folding long dependence chains in a single step without the need + // to run updates. + for (unsigned u = 0; u < InvalidAAs.size(); ++u) { + AbstractAttribute *InvalidAA = InvalidAAs[u]; + auto &QuerriedAAs = QueryMap[InvalidAA]; + LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has " + << QuerriedAAs.RequiredAAs.size() << "/" + << QuerriedAAs.OptionalAAs.size() + << " required/optional dependences\n"); + for (AbstractAttribute *DepOnInvalidAA : QuerriedAAs.RequiredAAs) { + AbstractState &DOIAAState = DepOnInvalidAA->getState(); + DOIAAState.indicatePessimisticFixpoint(); + ++NumAttributesFixedDueToRequiredDependences; + assert(DOIAAState.isAtFixpoint() && "Expected fixpoint state!"); + if (!DOIAAState.isValidState()) + InvalidAAs.insert(DepOnInvalidAA); + } + if (!RecomputeDependences) + Worklist.insert(QuerriedAAs.OptionalAAs.begin(), + QuerriedAAs.OptionalAAs.end()); + } + // If dependences (=QueryMap) are recomputed we have to look at all abstract // attributes again, regardless of what changed in the last iteration. if (RecomputeDependences) { @@ -4493,22 +5904,35 @@ ChangeStatus Attributor::run(Module &M) { // changed to the work list. for (AbstractAttribute *ChangedAA : ChangedAAs) { auto &QuerriedAAs = QueryMap[ChangedAA]; - Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end()); + Worklist.insert(QuerriedAAs.OptionalAAs.begin(), + QuerriedAAs.OptionalAAs.end()); + Worklist.insert(QuerriedAAs.RequiredAAs.begin(), + QuerriedAAs.RequiredAAs.end()); } LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter << ", Worklist+Dependent size: " << Worklist.size() << "\n"); - // Reset the changed set. + // Reset the changed and invalid set. ChangedAAs.clear(); + InvalidAAs.clear(); // Update all abstract attribute in the work list and record the ones that // changed. for (AbstractAttribute *AA : Worklist) - if (!isAssumedDead(*AA, nullptr)) - if (AA->update(*this) == ChangeStatus::CHANGED) + if (!AA->getState().isAtFixpoint() && !isAssumedDead(*AA, nullptr)) { + QueriedNonFixAA = false; + if (AA->update(*this) == ChangeStatus::CHANGED) { ChangedAAs.push_back(AA); + if (!AA->getState().isValidState()) + InvalidAAs.insert(AA); + } else if (!QueriedNonFixAA) { + // If the attribute did not query any non-fix information, the state + // will not change and we can indicate that right away. + AA->getState().indicateOptimisticFixpoint(); + } + } // Check if we recompute the dependences in the next iteration. RecomputeDependences = (DepRecomputeInterval > 0 && @@ -4552,7 +5976,10 @@ ChangeStatus Attributor::run(Module &M) { } auto &QuerriedAAs = QueryMap[ChangedAA]; - ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end()); + ChangedAAs.append(QuerriedAAs.OptionalAAs.begin(), + QuerriedAAs.OptionalAAs.end()); + ChangedAAs.append(QuerriedAAs.RequiredAAs.begin(), + QuerriedAAs.RequiredAAs.end()); } LLVM_DEBUG({ @@ -4611,27 +6038,85 @@ ChangeStatus Attributor::run(Module &M) { LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " << ToBeDeletedFunctions.size() << " functions and " << ToBeDeletedBlocks.size() << " blocks and " - << ToBeDeletedInsts.size() << " instructions\n"); + << ToBeDeletedInsts.size() << " instructions and " + << ToBeChangedUses.size() << " uses\n"); + + SmallVector<Instruction *, 32> DeadInsts; + SmallVector<Instruction *, 32> TerminatorsToFold; + + for (auto &It : ToBeChangedUses) { + Use *U = It.first; + Value *NewV = It.second; + Value *OldV = U->get(); + LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() + << " instead of " << *OldV << "\n"); + U->set(NewV); + if (Instruction *I = dyn_cast<Instruction>(OldV)) + if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) && + isInstructionTriviallyDead(I)) { + DeadInsts.push_back(I); + } + if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) { + Instruction *UserI = cast<Instruction>(U->getUser()); + if (isa<UndefValue>(NewV)) { + ToBeChangedToUnreachableInsts.insert(UserI); + } else { + TerminatorsToFold.push_back(UserI); + } + } + } + for (auto &V : InvokeWithDeadSuccessor) + if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) { + bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind); + bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn); + bool Invoke2CallAllowed = + !AAIsDeadFunction::mayCatchAsynchronousExceptions( + *II->getFunction()); + assert((UnwindBBIsDead || NormalBBIsDead) && + "Invoke does not have dead successors!"); + BasicBlock *BB = II->getParent(); + BasicBlock *NormalDestBB = II->getNormalDest(); + if (UnwindBBIsDead) { + Instruction *NormalNextIP = &NormalDestBB->front(); + if (Invoke2CallAllowed) { + changeToCall(II); + NormalNextIP = BB->getTerminator(); + } + if (NormalBBIsDead) + ToBeChangedToUnreachableInsts.insert(NormalNextIP); + } else { + assert(NormalBBIsDead && "Broken invariant!"); + if (!NormalDestBB->getUniquePredecessor()) + NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead"); + ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front()); + } + } + for (auto &V : ToBeChangedToUnreachableInsts) + if (Instruction *I = dyn_cast_or_null<Instruction>(V)) + changeToUnreachable(I, /* UseLLVMTrap */ false); + for (Instruction *I : TerminatorsToFold) + ConstantFoldTerminator(I->getParent()); + for (Instruction *I : ToBeDeletedInsts) { - if (!I->use_empty()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - I->eraseFromParent(); + I->replaceAllUsesWith(UndefValue::get(I->getType())); + if (!isa<PHINode>(I) && isInstructionTriviallyDead(I)) + DeadInsts.push_back(I); + else + I->eraseFromParent(); } + RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); + if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { SmallVector<BasicBlock *, 8> ToBeDeletedBBs; ToBeDeletedBBs.reserve(NumDeadBlocks); ToBeDeletedBBs.append(ToBeDeletedBlocks.begin(), ToBeDeletedBlocks.end()); - DeleteDeadBlocks(ToBeDeletedBBs); - STATS_DECLTRACK(AAIsDead, BasicBlock, - "Number of dead basic blocks deleted."); - } - - STATS_DECL(AAIsDead, Function, "Number of dead functions deleted."); - for (Function *Fn : ToBeDeletedFunctions) { - Fn->replaceAllUsesWith(UndefValue::get(Fn->getType())); - Fn->eraseFromParent(); - STATS_TRACK(AAIsDead, Function); + // Actually we do not delete the blocks but squash them into a single + // unreachable but untangling branches that jump here is something we need + // to do in a more generic way. + DetatchDeadBlocks(ToBeDeletedBBs, nullptr); + STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted."); + BUILD_STAT_NAME(AAIsDead, BasicBlock) += ToBeDeletedBlocks.size(); } // Identify dead internal functions and delete them. This happens outside @@ -4651,22 +6136,33 @@ ChangeStatus Attributor::run(Module &M) { if (!F) continue; - const auto *LivenessAA = - lookupAAFor<AAIsDead>(IRPosition::function(*F)); - if (LivenessAA && - !checkForAllCallSites([](AbstractCallSite ACS) { return false; }, - *LivenessAA, true)) + if (!checkForAllCallSites( + [this](AbstractCallSite ACS) { + return ToBeDeletedFunctions.count( + ACS.getInstruction()->getFunction()); + }, + *F, true, nullptr)) continue; - STATS_TRACK(AAIsDead, Function); - F->replaceAllUsesWith(UndefValue::get(F->getType())); - F->eraseFromParent(); + ToBeDeletedFunctions.insert(F); InternalFns[u] = nullptr; FoundDeadFn = true; } } } + STATS_DECL(AAIsDead, Function, "Number of dead functions deleted."); + BUILD_STAT_NAME(AAIsDead, Function) += ToBeDeletedFunctions.size(); + + // Rewrite the functions as requested during manifest. + ManifestChange = ManifestChange | rewriteFunctionSignatures(); + + for (Function *Fn : ToBeDeletedFunctions) { + Fn->deleteBody(); + Fn->replaceAllUsesWith(UndefValue::get(Fn->getType())); + Fn->eraseFromParent(); + } + if (VerifyMaxFixpointIterations && IterationCounter != MaxFixpointIterations) { errs() << "\n[Attributor] Fixpoint iteration done after: " @@ -4679,6 +6175,252 @@ ChangeStatus Attributor::run(Module &M) { return ManifestChange; } +bool Attributor::registerFunctionSignatureRewrite( + Argument &Arg, ArrayRef<Type *> ReplacementTypes, + ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, + ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB) { + + auto CallSiteCanBeChanged = [](AbstractCallSite ACS) { + // Forbid must-tail calls for now. + return !ACS.isCallbackCall() && !ACS.getCallSite().isMustTailCall(); + }; + + Function *Fn = Arg.getParent(); + // Avoid var-arg functions for now. + if (Fn->isVarArg()) { + LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n"); + return false; + } + + // Avoid functions with complicated argument passing semantics. + AttributeList FnAttributeList = Fn->getAttributes(); + if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) || + FnAttributeList.hasAttrSomewhere(Attribute::StructRet) || + FnAttributeList.hasAttrSomewhere(Attribute::InAlloca)) { + LLVM_DEBUG( + dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n"); + return false; + } + + // Avoid callbacks for now. + if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr)) { + LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n"); + return false; + } + + auto InstPred = [](Instruction &I) { + if (auto *CI = dyn_cast<CallInst>(&I)) + return !CI->isMustTailCall(); + return true; + }; + + // Forbid must-tail calls for now. + // TODO: + bool AnyDead; + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn); + if (!checkForAllInstructionsImpl(OpcodeInstMap, InstPred, nullptr, AnyDead, + {Instruction::Call})) { + LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n"); + return false; + } + + SmallVectorImpl<ArgumentReplacementInfo *> &ARIs = ArgumentReplacementMap[Fn]; + if (ARIs.size() == 0) + ARIs.resize(Fn->arg_size()); + + // If we have a replacement already with less than or equal new arguments, + // ignore this request. + ArgumentReplacementInfo *&ARI = ARIs[Arg.getArgNo()]; + if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) { + LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n"); + return false; + } + + // If we have a replacement already but we like the new one better, delete + // the old. + if (ARI) + delete ARI; + + // Remember the replacement. + ARI = new ArgumentReplacementInfo(*this, Arg, ReplacementTypes, + std::move(CalleeRepairCB), + std::move(ACSRepairCB)); + + return true; +} + +ChangeStatus Attributor::rewriteFunctionSignatures() { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + + for (auto &It : ArgumentReplacementMap) { + Function *OldFn = It.getFirst(); + + // Deleted functions do not require rewrites. + if (ToBeDeletedFunctions.count(OldFn)) + continue; + + const SmallVectorImpl<ArgumentReplacementInfo *> &ARIs = It.getSecond(); + assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!"); + + SmallVector<Type *, 16> NewArgumentTypes; + SmallVector<AttributeSet, 16> NewArgumentAttributes; + + // Collect replacement argument types and copy over existing attributes. + AttributeList OldFnAttributeList = OldFn->getAttributes(); + for (Argument &Arg : OldFn->args()) { + if (ArgumentReplacementInfo *ARI = ARIs[Arg.getArgNo()]) { + NewArgumentTypes.append(ARI->ReplacementTypes.begin(), + ARI->ReplacementTypes.end()); + NewArgumentAttributes.append(ARI->getNumReplacementArgs(), + AttributeSet()); + } else { + NewArgumentTypes.push_back(Arg.getType()); + NewArgumentAttributes.push_back( + OldFnAttributeList.getParamAttributes(Arg.getArgNo())); + } + } + + FunctionType *OldFnTy = OldFn->getFunctionType(); + Type *RetTy = OldFnTy->getReturnType(); + + // Construct the new function type using the new arguments types. + FunctionType *NewFnTy = + FunctionType::get(RetTy, NewArgumentTypes, OldFnTy->isVarArg()); + + LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName() + << "' from " << *OldFn->getFunctionType() << " to " + << *NewFnTy << "\n"); + + // Create the new function body and insert it into the module. + Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(), + OldFn->getAddressSpace(), ""); + OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn); + NewFn->takeName(OldFn); + NewFn->copyAttributesFrom(OldFn); + + // Patch the pointer to LLVM function in debug info descriptor. + NewFn->setSubprogram(OldFn->getSubprogram()); + OldFn->setSubprogram(nullptr); + + // Recompute the parameter attributes list based on the new arguments for + // the function. + LLVMContext &Ctx = OldFn->getContext(); + NewFn->setAttributes(AttributeList::get( + Ctx, OldFnAttributeList.getFnAttributes(), + OldFnAttributeList.getRetAttributes(), NewArgumentAttributes)); + + // Since we have now created the new function, splice the body of the old + // function right into the new function, leaving the old rotting hulk of the + // function empty. + NewFn->getBasicBlockList().splice(NewFn->begin(), + OldFn->getBasicBlockList()); + + // Set of all "call-like" instructions that invoke the old function mapped + // to their new replacements. + SmallVector<std::pair<CallBase *, CallBase *>, 8> CallSitePairs; + + // Callback to create a new "call-like" instruction for a given one. + auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) { + CallBase *OldCB = cast<CallBase>(ACS.getInstruction()); + const AttributeList &OldCallAttributeList = OldCB->getAttributes(); + + // Collect the new argument operands for the replacement call site. + SmallVector<Value *, 16> NewArgOperands; + SmallVector<AttributeSet, 16> NewArgOperandAttributes; + for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) { + unsigned NewFirstArgNum = NewArgOperands.size(); + (void)NewFirstArgNum; // only used inside assert. + if (ArgumentReplacementInfo *ARI = ARIs[OldArgNum]) { + if (ARI->ACSRepairCB) + ARI->ACSRepairCB(*ARI, ACS, NewArgOperands); + assert(ARI->getNumReplacementArgs() + NewFirstArgNum == + NewArgOperands.size() && + "ACS repair callback did not provide as many operand as new " + "types were registered!"); + // TODO: Exose the attribute set to the ACS repair callback + NewArgOperandAttributes.append(ARI->ReplacementTypes.size(), + AttributeSet()); + } else { + NewArgOperands.push_back(ACS.getCallArgOperand(OldArgNum)); + NewArgOperandAttributes.push_back( + OldCallAttributeList.getParamAttributes(OldArgNum)); + } + } + + assert(NewArgOperands.size() == NewArgOperandAttributes.size() && + "Mismatch # argument operands vs. # argument operand attributes!"); + assert(NewArgOperands.size() == NewFn->arg_size() && + "Mismatch # argument operands vs. # function arguments!"); + + SmallVector<OperandBundleDef, 4> OperandBundleDefs; + OldCB->getOperandBundlesAsDefs(OperandBundleDefs); + + // Create a new call or invoke instruction to replace the old one. + CallBase *NewCB; + if (InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) { + NewCB = + InvokeInst::Create(NewFn, II->getNormalDest(), II->getUnwindDest(), + NewArgOperands, OperandBundleDefs, "", OldCB); + } else { + auto *NewCI = CallInst::Create(NewFn, NewArgOperands, OperandBundleDefs, + "", OldCB); + NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind()); + NewCB = NewCI; + } + + // Copy over various properties and the new attributes. + uint64_t W; + if (OldCB->extractProfTotalWeight(W)) + NewCB->setProfWeight(W); + NewCB->setCallingConv(OldCB->getCallingConv()); + NewCB->setDebugLoc(OldCB->getDebugLoc()); + NewCB->takeName(OldCB); + NewCB->setAttributes(AttributeList::get( + Ctx, OldCallAttributeList.getFnAttributes(), + OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes)); + + CallSitePairs.push_back({OldCB, NewCB}); + return true; + }; + + // Use the CallSiteReplacementCreator to create replacement call sites. + bool Success = + checkForAllCallSites(CallSiteReplacementCreator, *OldFn, true, nullptr); + (void)Success; + assert(Success && "Assumed call site replacement to succeed!"); + + // Rewire the arguments. + auto OldFnArgIt = OldFn->arg_begin(); + auto NewFnArgIt = NewFn->arg_begin(); + for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); + ++OldArgNum, ++OldFnArgIt) { + if (ArgumentReplacementInfo *ARI = ARIs[OldArgNum]) { + if (ARI->CalleeRepairCB) + ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt); + NewFnArgIt += ARI->ReplacementTypes.size(); + } else { + NewFnArgIt->takeName(&*OldFnArgIt); + OldFnArgIt->replaceAllUsesWith(&*NewFnArgIt); + ++NewFnArgIt; + } + } + + // Eliminate the instructions *after* we visited all of them. + for (auto &CallSitePair : CallSitePairs) { + CallBase &OldCB = *CallSitePair.first; + CallBase &NewCB = *CallSitePair.second; + OldCB.replaceAllUsesWith(&NewCB); + OldCB.eraseFromParent(); + } + + ToBeDeletedFunctions.insert(OldFn); + + Changed = ChangeStatus::CHANGED; + } + + return Changed; +} + void Attributor::initializeInformationCache(Function &F) { // Walk all instructions to find interesting instructions that might be @@ -4710,6 +6452,9 @@ void Attributor::initializeInformationCache(Function &F) { case Instruction::Invoke: case Instruction::CleanupRet: case Instruction::CatchSwitch: + case Instruction::AtomicRMW: + case Instruction::AtomicCmpXchg: + case Instruction::Br: case Instruction::Resume: case Instruction::Ret: IsInterestingOpcode = true; @@ -4721,9 +6466,26 @@ void Attributor::initializeInformationCache(Function &F) { } } +void Attributor::recordDependence(const AbstractAttribute &FromAA, + const AbstractAttribute &ToAA, + DepClassTy DepClass) { + if (FromAA.getState().isAtFixpoint()) + return; + + if (DepClass == DepClassTy::REQUIRED) + QueryMap[&FromAA].RequiredAAs.insert( + const_cast<AbstractAttribute *>(&ToAA)); + else + QueryMap[&FromAA].OptionalAAs.insert( + const_cast<AbstractAttribute *>(&ToAA)); + QueriedNonFixAA = true; +} + void Attributor::identifyDefaultAbstractAttributes(Function &F) { if (!VisitedFunctions.insert(&F).second) return; + if (F.isDeclaration()) + return; IRPosition FPos = IRPosition::function(F); @@ -4735,6 +6497,9 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { // Every function might be "will-return". getOrCreateAAFor<AAWillReturn>(FPos); + // Every function might contain instructions that cause "undefined behavior". + getOrCreateAAFor<AAUndefinedBehavior>(FPos); + // Every function can be nounwind. getOrCreateAAFor<AANoUnwind>(FPos); @@ -4766,6 +6531,9 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { IRPosition RetPos = IRPosition::returned(F); + // Every returned value might be dead. + getOrCreateAAFor<AAIsDead>(RetPos); + // Every function might be simplified. getOrCreateAAFor<AAValueSimplify>(RetPos); @@ -4811,16 +6579,41 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { // Every argument with pointer type might be marked // "readnone/readonly/writeonly/..." getOrCreateAAFor<AAMemoryBehavior>(ArgPos); + + // Every argument with pointer type might be marked nofree. + getOrCreateAAFor<AANoFree>(ArgPos); } } auto CallSitePred = [&](Instruction &I) -> bool { CallSite CS(&I); - if (CS.getCalledFunction()) { - for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) { + if (Function *Callee = CS.getCalledFunction()) { + // Skip declerations except if annotations on their call sites were + // explicitly requested. + if (!AnnotateDeclarationCallSites && Callee->isDeclaration() && + !Callee->hasMetadata(LLVMContext::MD_callback)) + return true; + + if (!Callee->getReturnType()->isVoidTy() && !CS->use_empty()) { + + IRPosition CSRetPos = IRPosition::callsite_returned(CS); + + // Call site return values might be dead. + getOrCreateAAFor<AAIsDead>(CSRetPos); + + // Call site return integer values might be limited by a constant range. + if (Callee->getReturnType()->isIntegerTy()) { + getOrCreateAAFor<AAValueConstantRange>(CSRetPos); + } + } + + for (int i = 0, e = CS.getNumArgOperands(); i < e; i++) { IRPosition CSArgPos = IRPosition::callsite_argument(CS, i); + // Every call site argument might be dead. + getOrCreateAAFor<AAIsDead>(CSArgPos); + // Call site argument might be simplified. getOrCreateAAFor<AAValueSimplify>(CSArgPos); @@ -4838,6 +6631,13 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { // Call site argument attribute "align". getOrCreateAAFor<AAAlign>(CSArgPos); + + // Call site argument attribute + // "readnone/readonly/writeonly/..." + getOrCreateAAFor<AAMemoryBehavior>(CSArgPos); + + // Call site argument attribute "nofree". + getOrCreateAAFor<AANoFree>(CSArgPos); } } return true; @@ -4903,11 +6703,24 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) { << Pos.getAnchorValue().getName() << "@" << Pos.getArgNo() << "]}"; } -raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerState &S) { +template <typename base_ty, base_ty BestState, base_ty WorstState> +raw_ostream & +llvm::operator<<(raw_ostream &OS, + const IntegerStateBase<base_ty, BestState, WorstState> &S) { return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")" << static_cast<const AbstractState &>(S); } +raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) { + OS << "range-state(" << S.getBitWidth() << ")<"; + S.getKnown().print(OS); + OS << " / "; + S.getAssumed().print(OS); + OS << ">"; + + return OS << static_cast<const AbstractState &>(S); +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) { return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : "")); } @@ -4963,7 +6776,9 @@ static bool runAttributorOnModule(Module &M, AnalysisGetter &AG) { A.identifyDefaultAbstractAttributes(F); } - return A.run(M) == ChangeStatus::CHANGED; + bool Changed = A.run(M) == ChangeStatus::CHANGED; + assert(!verifyModule(M, &errs()) && "Module verification failed!"); + return Changed; } PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { @@ -5011,7 +6826,9 @@ const char AANoFree::ID = 0; 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; const char AAIsDead::ID = 0; const char AADereferenceable::ID = 0; @@ -5020,6 +6837,7 @@ const char AANoCapture::ID = 0; const char AAValueSimplify::ID = 0; const char AAHeapToStack::ID = 0; const char AAMemoryBehavior::ID = 0; +const char AAValueConstantRange::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -5115,11 +6933,9 @@ const char AAMemoryBehavior::ID = 0; CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoUnwind) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoSync) -CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoRecurse) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAWillReturn) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn) -CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull) @@ -5127,10 +6943,15 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) +CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) +CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree) 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) |