diff options
Diffstat (limited to 'llvm/lib/Transforms/IPO/AttributorAttributes.cpp')
| -rw-r--r-- | llvm/lib/Transforms/IPO/AttributorAttributes.cpp | 1306 |
1 files changed, 1131 insertions, 175 deletions
diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp index 7e9fd61eeb41..d6127a8df628 100644 --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -13,15 +13,20 @@ #include "llvm/Transforms/IPO/Attributor.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumeBundleQueries.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instruction.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/NoFolder.h" #include "llvm/Support/CommandLine.h" @@ -42,6 +47,16 @@ static cl::opt<bool> ManifestInternal( static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128), cl::Hidden); +template <> +unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0; + +static cl::opt<unsigned, true> MaxPotentialValues( + "attributor-max-potential-values", cl::Hidden, + cl::desc("Maximum number of potential values to be " + "tracked for each position."), + cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues), + cl::init(7)); + STATISTIC(NumAAs, "Number of abstract attributes created"); // Some helper macros to deal with statistics tracking. @@ -117,6 +132,8 @@ PIPE_OPERATOR(AAMemoryLocation) PIPE_OPERATOR(AAValueConstantRange) PIPE_OPERATOR(AAPrivatizablePtr) PIPE_OPERATOR(AAUndefinedBehavior) +PIPE_OPERATOR(AAPotentialValues) +PIPE_OPERATOR(AANoUndef) #undef PIPE_OPERATOR } // namespace llvm @@ -435,7 +452,7 @@ static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA, const AAType &AA = A.getAAFor<AAType>(QueryingAA, RVPos); LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr() << " @ " << RVPos << "\n"); - const StateType &AAS = static_cast<const StateType &>(AA.getState()); + const StateType &AAS = AA.getState(); if (T.hasValue()) *T &= AAS; else @@ -485,7 +502,7 @@ static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, Optional<StateType> T; // The argument number which is also the call site argument number. - unsigned ArgNo = QueryingAA.getIRPosition().getArgNo(); + unsigned ArgNo = QueryingAA.getIRPosition().getCallSiteArgNo(); auto CallSiteCheck = [&](AbstractCallSite ACS) { const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo); @@ -497,7 +514,7 @@ static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, const AAType &AA = A.getAAFor<AAType>(QueryingAA, ACSArgPos); LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction() << " AA: " << AA.getAsStr() << " @" << ACSArgPos << "\n"); - const StateType &AAS = static_cast<const StateType &>(AA.getState()); + const StateType &AAS = AA.getState(); if (T.hasValue()) *T &= AAS; else @@ -554,8 +571,7 @@ struct AACallSiteReturnedFromReturned : public BaseType { IRPosition FnPos = IRPosition::returned(*AssociatedFunction); const AAType &AA = A.getAAFor<AAType>(*this, FnPos); - return clampStateAndIndicateChange( - S, static_cast<const StateType &>(AA.getState())); + return clampStateAndIndicateChange(S, AA.getState()); } }; @@ -722,7 +738,7 @@ struct AANoUnwindCallSite final : AANoUnwindImpl { void initialize(Attributor &A) override { AANoUnwindImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -735,9 +751,7 @@ struct AANoUnwindCallSite final : AANoUnwindImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AANoUnwind>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AANoUnwind::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -783,7 +797,7 @@ public: ReturnedValues.clear(); Function *F = getAssociatedFunction(); - if (!F) { + if (!F || F->isDeclaration()) { indicatePessimisticFixpoint(); return; } @@ -1052,9 +1066,10 @@ ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) { // map, NewRVsMap. decltype(ReturnedValues) NewRVsMap; - auto HandleReturnValue = [&](Value *RV, SmallSetVector<ReturnInst *, 4> &RIs) { - LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV - << " by #" << RIs.size() << " RIs\n"); + auto HandleReturnValue = [&](Value *RV, + SmallSetVector<ReturnInst *, 4> &RIs) { + LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #" + << RIs.size() << " RIs\n"); CallBase *CB = dyn_cast<CallBase>(RV); if (!CB || UnresolvedCalls.count(CB)) return; @@ -1128,11 +1143,13 @@ ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) { RVState RVS({NewRVsMap, Unused, RetValAAIt.second}); VisitReturnedValue(*CB->getArgOperand(Arg->getArgNo()), RVS, CB); continue; - } else if (isa<CallBase>(RetVal)) { + } + if (isa<CallBase>(RetVal)) { // Call sites are resolved by the callee attribute over time, no need to // do anything for us. continue; - } else if (isa<Constant>(RetVal)) { + } + if (isa<Constant>(RetVal)) { // Constants are valid everywhere, we can simply take them. NewRVsMap[RetVal].insert(RIs.begin(), RIs.end()); continue; @@ -1373,7 +1390,7 @@ struct AANoSyncCallSite final : AANoSyncImpl { void initialize(Attributor &A) override { AANoSyncImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -1386,8 +1403,7 @@ struct AANoSyncCallSite final : AANoSyncImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AANoSync>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), static_cast<const AANoSync::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -1439,7 +1455,7 @@ struct AANoFreeCallSite final : AANoFreeImpl { void initialize(Attributor &A) override { AANoFreeImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -1452,8 +1468,7 @@ struct AANoFreeCallSite final : AANoFreeImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AANoFree>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), static_cast<const AANoFree::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -1535,8 +1550,7 @@ struct AANoFreeCallSiteArgument final : AANoFreeFloating { 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())); + return clampStateAndIndicateChange(getState(), ArgAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -1672,21 +1686,33 @@ struct AANonNullImpl : AANonNull { Value &V = getAssociatedValue(); if (!NullIsDefined && hasAttr({Attribute::NonNull, Attribute::Dereferenceable}, - /* IgnoreSubsumingPositions */ false, &A)) + /* IgnoreSubsumingPositions */ false, &A)) { indicateOptimisticFixpoint(); - else if (isa<ConstantPointerNull>(V)) + return; + } + + if (isa<ConstantPointerNull>(V)) { indicatePessimisticFixpoint(); - else - AANonNull::initialize(A); + return; + } + + AANonNull::initialize(A); bool CanBeNull = true; - if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull)) - if (!CanBeNull) + if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull)) { + if (!CanBeNull) { indicateOptimisticFixpoint(); + return; + } + } - if (!getState().isAtFixpoint()) - if (Instruction *CtxI = getCtxI()) - followUsesInMBEC(*this, A, getState(), *CtxI); + if (isa<GlobalValue>(&getAssociatedValue())) { + indicatePessimisticFixpoint(); + return; + } + + if (Instruction *CtxI = getCtxI()) + followUsesInMBEC(*this, A, getState(), *CtxI); } /// See followUsesInMBEC @@ -1717,13 +1743,6 @@ struct AANonNullFloating : public AANonNullImpl { /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - if (!NullIsDefined) { - const auto &DerefAA = - A.getAAFor<AADereferenceable>(*this, getIRPosition()); - if (DerefAA.getAssumedDereferenceableBytes()) - return ChangeStatus::UNCHANGED; - } - const DataLayout &DL = A.getDataLayout(); DominatorTree *DT = nullptr; @@ -1742,8 +1761,7 @@ struct AANonNullFloating : public AANonNullImpl { T.indicatePessimisticFixpoint(); } else { // Use abstract attribute information. - const AANonNull::StateType &NS = - static_cast<const AANonNull::StateType &>(AA.getState()); + const AANonNull::StateType &NS = AA.getState(); T ^= NS; } return T.isValidState(); @@ -1763,9 +1781,14 @@ struct AANonNullFloating : public AANonNullImpl { /// NonNull attribute for function return value. struct AANonNullReturned final - : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl> { + : AAReturnedFromReturnedValues<AANonNull, AANonNull> { AANonNullReturned(const IRPosition &IRP, Attributor &A) - : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl>(IRP, A) {} + : AAReturnedFromReturnedValues<AANonNull, AANonNull>(IRP, A) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return getAssumed() ? "nonnull" : "may-null"; + } /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) } @@ -1879,7 +1902,7 @@ struct AANoRecurseCallSite final : AANoRecurseImpl { void initialize(Attributor &A) override { AANoRecurseImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -1892,9 +1915,7 @@ struct AANoRecurseCallSite final : AANoRecurseImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AANoRecurse>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AANoRecurse::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -1979,6 +2000,98 @@ struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior { return true; }; + auto InspectCallSiteForUB = [&](Instruction &I) { + // Check whether a callsite always cause UB or not + + // Skip instructions that are already saved. + if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I)) + return true; + + // Check nonnull and noundef argument attribute violation for each + // callsite. + CallBase &CB = cast<CallBase>(I); + Function *Callee = CB.getCalledFunction(); + if (!Callee) + return true; + for (unsigned idx = 0; idx < CB.getNumArgOperands(); idx++) { + // If current argument is known to be simplified to null pointer and the + // corresponding argument position is known to have nonnull attribute, + // the argument is poison. Furthermore, if the argument is poison and + // the position is known to have noundef attriubte, this callsite is + // considered UB. + if (idx >= Callee->arg_size()) + break; + Value *ArgVal = CB.getArgOperand(idx); + if (!ArgVal) + continue; + // Here, we handle three cases. + // (1) Not having a value means it is dead. (we can replace the value + // with undef) + // (2) Simplified to undef. The argument violate noundef attriubte. + // (3) Simplified to null pointer where known to be nonnull. + // The argument is a poison value and violate noundef attribute. + IRPosition CalleeArgumentIRP = IRPosition::callsite_argument(CB, idx); + auto &NoUndefAA = A.getAAFor<AANoUndef>(*this, CalleeArgumentIRP, + /* TrackDependence */ false); + if (!NoUndefAA.isKnownNoUndef()) + continue; + auto &ValueSimplifyAA = A.getAAFor<AAValueSimplify>( + *this, IRPosition::value(*ArgVal), /* TrackDependence */ false); + if (!ValueSimplifyAA.isKnown()) + continue; + Optional<Value *> SimplifiedVal = + ValueSimplifyAA.getAssumedSimplifiedValue(A); + if (!SimplifiedVal.hasValue() || + isa<UndefValue>(*SimplifiedVal.getValue())) { + KnownUBInsts.insert(&I); + continue; + } + if (!ArgVal->getType()->isPointerTy() || + !isa<ConstantPointerNull>(*SimplifiedVal.getValue())) + continue; + auto &NonNullAA = A.getAAFor<AANonNull>(*this, CalleeArgumentIRP, + /* TrackDependence */ false); + if (NonNullAA.isKnownNonNull()) + KnownUBInsts.insert(&I); + } + return true; + }; + + auto InspectReturnInstForUB = + [&](Value &V, const SmallSetVector<ReturnInst *, 4> RetInsts) { + // Check if a return instruction always cause UB or not + // Note: It is guaranteed that the returned position of the anchor + // scope has noundef attribute when this is called. + // We also ensure the return position is not "assumed dead" + // because the returned value was then potentially simplified to + // `undef` in AAReturnedValues without removing the `noundef` + // attribute yet. + + // When the returned position has noundef attriubte, UB occur in the + // following cases. + // (1) Returned value is known to be undef. + // (2) The value is known to be a null pointer and the returned + // position has nonnull attribute (because the returned value is + // poison). + bool FoundUB = false; + if (isa<UndefValue>(V)) { + FoundUB = true; + } else { + if (isa<ConstantPointerNull>(V)) { + auto &NonNullAA = A.getAAFor<AANonNull>( + *this, IRPosition::returned(*getAnchorScope()), + /* TrackDependence */ false); + if (NonNullAA.isKnownNonNull()) + FoundUB = true; + } + } + + if (FoundUB) + for (ReturnInst *RI : RetInsts) + KnownUBInsts.insert(RI); + return true; + }; + A.checkForAllInstructions(InspectMemAccessInstForUB, *this, {Instruction::Load, Instruction::Store, Instruction::AtomicCmpXchg, @@ -1986,6 +2099,22 @@ struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior { /* CheckBBLivenessOnly */ true); A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br}, /* CheckBBLivenessOnly */ true); + A.checkForAllCallLikeInstructions(InspectCallSiteForUB, *this); + + // If the returned position of the anchor scope has noundef attriubte, check + // all returned instructions. + if (!getAnchorScope()->getReturnType()->isVoidTy()) { + const IRPosition &ReturnIRP = IRPosition::returned(*getAnchorScope()); + if (!A.isAssumedDead(ReturnIRP, this, nullptr)) { + auto &RetPosNoUndefAA = + A.getAAFor<AANoUndef>(*this, ReturnIRP, + /* TrackDependence */ false); + if (RetPosNoUndefAA.isKnownNoUndef()) + A.checkForAllReturnedValuesAndReturnInsts(InspectReturnInstForUB, + *this); + } + } + if (NoUBPrevSize != AssumedNoUBInsts.size() || UBPrevSize != KnownUBInsts.size()) return ChangeStatus::CHANGED; @@ -2153,7 +2282,7 @@ struct AAWillReturnImpl : public AAWillReturn { AAWillReturn::initialize(A); Function *F = getAnchorScope(); - if (!F || !A.isFunctionIPOAmendable(*F) || mayContainUnboundedCycle(*F, A)) + if (!F || F->isDeclaration() || mayContainUnboundedCycle(*F, A)) indicatePessimisticFixpoint(); } @@ -2197,9 +2326,9 @@ struct AAWillReturnCallSite final : AAWillReturnImpl { /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - AAWillReturnImpl::initialize(A); + AAWillReturn::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || !A.isFunctionIPOAmendable(*F)) indicatePessimisticFixpoint(); } @@ -2212,9 +2341,7 @@ struct AAWillReturnCallSite final : AAWillReturnImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AAWillReturn>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AAWillReturn::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -2374,7 +2501,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { void initialize(Attributor &A) override { // See callsite argument attribute and callee argument attribute. const auto &CB = cast<CallBase>(getAnchorValue()); - if (CB.paramHasAttr(getArgNo(), Attribute::NoAlias)) + if (CB.paramHasAttr(getCallSiteArgNo(), Attribute::NoAlias)) indicateOptimisticFixpoint(); Value &Val = getAssociatedValue(); if (isa<ConstantPointerNull>(Val) && @@ -2389,7 +2516,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { const AAMemoryBehavior &MemBehaviorAA, const CallBase &CB, unsigned OtherArgNo) { // We do not need to worry about aliasing with the underlying IRP. - if (this->getArgNo() == (int)OtherArgNo) + if (this->getCalleeArgNo() == (int)OtherArgNo) return false; // If it is not a pointer or pointer vector we do not alias. @@ -2451,6 +2578,7 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { A.recordDependence(NoAliasAA, *this, DepClassTy::OPTIONAL); const IRPosition &VIRP = IRPosition::value(getAssociatedValue()); + const Function *ScopeFn = VIRP.getAnchorScope(); auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, VIRP, /* TrackDependence */ false); // Check whether the value is captured in the scope using AANoCapture. @@ -2459,16 +2587,18 @@ struct AANoAliasCallSiteArgument final : AANoAliasImpl { auto UsePred = [&](const Use &U, bool &Follow) -> bool { Instruction *UserI = cast<Instruction>(U.getUser()); - // If user if curr instr and only use. - if (UserI == getCtxI() && UserI->hasOneUse()) + // If UserI is the curr instruction and there is a single potential use of + // the value in UserI we allow the use. + // TODO: We should inspect the operands and allow those that cannot alias + // with the value. + if (UserI == getCtxI() && UserI->getNumOperands() == 1) return true; - const Function *ScopeFn = VIRP.getAnchorScope(); if (ScopeFn) { const auto &ReachabilityAA = A.getAAFor<AAReachability>(*this, IRPosition::function(*ScopeFn)); - if (!ReachabilityAA.isAssumedReachable(UserI, getCtxI())) + if (!ReachabilityAA.isAssumedReachable(A, *UserI, *getCtxI())) return true; if (auto *CB = dyn_cast<CallBase>(UserI)) { @@ -2554,6 +2684,14 @@ struct AANoAliasReturned final : AANoAliasImpl { AANoAliasReturned(const IRPosition &IRP, Attributor &A) : AANoAliasImpl(IRP, A) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AANoAliasImpl::initialize(A); + Function *F = getAssociatedFunction(); + if (!F || F->isDeclaration()) + indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::updateImpl(...). virtual ChangeStatus updateImpl(Attributor &A) override { @@ -2595,7 +2733,7 @@ struct AANoAliasCallSiteReturned final : AANoAliasImpl { void initialize(Attributor &A) override { AANoAliasImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -2608,8 +2746,7 @@ struct AANoAliasCallSiteReturned final : AANoAliasImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::returned(*F); auto &FnAA = A.getAAFor<AANoAlias>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), static_cast<const AANoAlias::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -2799,14 +2936,13 @@ struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl { 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())); + return clampStateAndIndicateChange(getState(), ArgAA.getState()); } /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { CallBase &CB = cast<CallBase>(getAnchorValue()); - Use &U = CB.getArgOperandUse(getArgNo()); + Use &U = CB.getArgOperandUse(getCallSiteArgNo()); assert(!isa<UndefValue>(U.get()) && "Expected undef values to be filtered out!"); UndefValue &UV = *UndefValue::get(U->getType()); @@ -2921,8 +3057,14 @@ struct AAIsDeadFunction : public AAIsDead { void initialize(Attributor &A) override { const Function *F = getAnchorScope(); if (F && !F->isDeclaration()) { - ToBeExploredFrom.insert(&F->getEntryBlock().front()); - assumeLive(A, F->getEntryBlock()); + // We only want to compute liveness once. If the function is not part of + // the SCC, skip it. + if (A.isRunOn(*const_cast<Function *>(F))) { + ToBeExploredFrom.insert(&F->getEntryBlock().front()); + assumeLive(A, F->getEntryBlock()); + } else { + indicatePessimisticFixpoint(); + } } } @@ -2985,6 +3127,10 @@ struct AAIsDeadFunction : public AAIsDead { /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; + bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const override { + return !AssumedLiveEdges.count(std::make_pair(From, To)); + } + /// See AbstractAttribute::trackStatistics() void trackStatistics() const override {} @@ -3062,6 +3208,9 @@ struct AAIsDeadFunction : public AAIsDead { /// Collection of instructions that are known to not transfer control. SmallSetVector<const Instruction *, 8> KnownDeadEnds; + /// Collection of all assumed live edges + DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> AssumedLiveEdges; + /// Collection of all assumed live BasicBlocks. DenseSet<const BasicBlock *> AssumedLiveBlocks; }; @@ -3177,18 +3326,23 @@ ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { const Instruction *I = Worklist.pop_back_val(); LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n"); + // Fast forward for uninteresting instructions. We could look for UB here + // though. + while (!I->isTerminator() && !isa<CallBase>(I)) { + Change = ChangeStatus::CHANGED; + I = I->getNextNode(); + } + AliveSuccessors.clear(); 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()); - } + assert(I->isTerminator() && + "Expected non-terminators to be handled already!"); + for (const BasicBlock *SuccBB : successors(I->getParent())) + AliveSuccessors.push_back(&SuccBB->front()); break; case Instruction::Call: UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I), @@ -3227,6 +3381,9 @@ ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { "Non-terminator expected to have a single successor!"); Worklist.push_back(AliveSuccessor); } else { + // record the assumed live edge + AssumedLiveEdges.insert( + std::make_pair(I->getParent(), AliveSuccessor->getParent())); if (assumeLive(A, *AliveSuccessor->getParent())) Worklist.push_back(AliveSuccessor); } @@ -3342,7 +3499,6 @@ struct AADereferenceableImpl : AADereferenceable { State.addAccessedBytes(Offset, Size); } } - return; } /// See followUsesInMBEC @@ -3420,12 +3576,11 @@ struct AADereferenceableFloating : AADereferenceableImpl { DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull); T.GlobalState.indicatePessimisticFixpoint(); } else { - const DerefState &DS = static_cast<const DerefState &>(AA.getState()); + const DerefState &DS = AA.getState(); DerefBytes = DS.DerefBytesState.getAssumed(); T.GlobalState &= DS.GlobalState; } - // 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. @@ -3697,14 +3852,27 @@ struct AAAlignFloating : AAAlignImpl { AAAlign::StateType &T, bool Stripped) -> bool { const auto &AA = A.getAAFor<AAAlign>(*this, IRPosition::value(V)); if (!Stripped && this == &AA) { + int64_t Offset; + unsigned Alignment = 1; + if (const Value *Base = + GetPointerBaseWithConstantOffset(&V, Offset, DL)) { + Align PA = Base->getPointerAlignment(DL); + // 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)), + uint32_t(PA.value())); + Alignment = llvm::PowerOf2Floor(gcd); + } else { + Alignment = V.getPointerAlignment(DL).value(); + } // Use only IR information if we did not strip anything. - Align PA = V.getPointerAlignment(DL); - T.takeKnownMaximum(PA.value()); + T.takeKnownMaximum(Alignment); T.indicatePessimisticFixpoint(); } else { // Use abstract attribute information. - const AAAlign::StateType &DS = - static_cast<const AAAlign::StateType &>(AA.getState()); + const AAAlign::StateType &DS = AA.getState(); T ^= DS; } return T.isValidState(); @@ -3727,8 +3895,16 @@ struct AAAlignFloating : AAAlignImpl { /// Align attribute for function return value. struct AAAlignReturned final : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> { - AAAlignReturned(const IRPosition &IRP, Attributor &A) - : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>(IRP, A) {} + using Base = AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>; + AAAlignReturned(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + Base::initialize(A); + Function *F = getAssociatedFunction(); + if (!F || F->isDeclaration()) + indicatePessimisticFixpoint(); + } /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) } @@ -3802,7 +3978,7 @@ struct AAAlignCallSiteReturned final void initialize(Attributor &A) override { Base::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -3818,7 +3994,7 @@ struct AANoReturnImpl : public AANoReturn { void initialize(Attributor &A) override { AANoReturn::initialize(A); Function *F = getAssociatedFunction(); - if (!F) + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); } @@ -3850,6 +4026,17 @@ struct AANoReturnCallSite final : AANoReturnImpl { AANoReturnCallSite(const IRPosition &IRP, Attributor &A) : AANoReturnImpl(IRP, A) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AANoReturnImpl::initialize(A); + if (Function *F = getAssociatedFunction()) { + const IRPosition &FnPos = IRPosition::function(*F); + auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos); + if (!FnAA.isAssumedNoReturn()) + indicatePessimisticFixpoint(); + } + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { // TODO: Once we have call site specific value information we can provide @@ -3859,9 +4046,7 @@ struct AANoReturnCallSite final : AANoReturnImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AANoReturn::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -3894,7 +4079,8 @@ struct AANoCaptureImpl : public AANoCapture { return; } - const Function *F = getArgNo() >= 0 ? getAssociatedFunction() : AnchorScope; + const Function *F = + isArgumentPosition() ? getAssociatedFunction() : AnchorScope; // Check what state the associated function can actually capture. if (F) @@ -3913,7 +4099,7 @@ struct AANoCaptureImpl : public AANoCapture { if (!isAssumedNoCaptureMaybeReturned()) return; - if (getArgNo() >= 0) { + if (isArgumentPosition()) { if (isAssumedNoCapture()) Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture)); else if (ManifestInternal) @@ -3949,7 +4135,7 @@ struct AANoCaptureImpl : public AANoCapture { State.addKnownBits(NOT_CAPTURED_IN_RET); // Check existing "returned" attributes. - int ArgNo = IRP.getArgNo(); + int ArgNo = IRP.getCalleeArgNo(); if (F.doesNotThrow() && ArgNo >= 0) { for (unsigned u = 0, e = F.arg_size(); u < e; ++u) if (F.hasParamAttribute(u, Attribute::Returned)) { @@ -4125,13 +4311,13 @@ private: ChangeStatus AANoCaptureImpl::updateImpl(Attributor &A) { const IRPosition &IRP = getIRPosition(); - const Value *V = - getArgNo() >= 0 ? IRP.getAssociatedArgument() : &IRP.getAssociatedValue(); + const Value *V = isArgumentPosition() ? IRP.getAssociatedArgument() + : &IRP.getAssociatedValue(); if (!V) return indicatePessimisticFixpoint(); const Function *F = - getArgNo() >= 0 ? IRP.getAssociatedFunction() : IRP.getAnchorScope(); + isArgumentPosition() ? IRP.getAssociatedFunction() : IRP.getAnchorScope(); assert(F && "Expected a function!"); const IRPosition &FnPos = IRPosition::function(*F); const auto &IsDeadAA = @@ -4248,9 +4434,7 @@ struct AANoCaptureCallSiteArgument final : AANoCaptureImpl { return indicatePessimisticFixpoint(); const IRPosition &ArgPos = IRPosition::argument(*Arg); auto &ArgAA = A.getAAFor<AANoCapture>(*this, ArgPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AANoCapture::StateType &>(ArgAA.getState())); + return clampStateAndIndicateChange(getState(), ArgAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -4366,24 +4550,35 @@ struct AAValueSimplifyImpl : AAValueSimplify { return true; } - bool askSimplifiedValueForAAValueConstantRange(Attributor &A) { + /// Returns a candidate is found or not + template <typename AAType> bool askSimplifiedValueFor(Attributor &A) { if (!getAssociatedValue().getType()->isIntegerTy()) return false; - const auto &ValueConstantRangeAA = - A.getAAFor<AAValueConstantRange>(*this, getIRPosition()); + const auto &AA = + A.getAAFor<AAType>(*this, getIRPosition(), /* TrackDependence */ false); - Optional<ConstantInt *> COpt = - ValueConstantRangeAA.getAssumedConstantInt(A); - if (COpt.hasValue()) { - if (auto *C = COpt.getValue()) - SimplifiedAssociatedValue = C; - else - return false; - } else { + Optional<ConstantInt *> COpt = AA.getAssumedConstantInt(A); + + if (!COpt.hasValue()) { SimplifiedAssociatedValue = llvm::None; + A.recordDependence(AA, *this, DepClassTy::OPTIONAL); + return true; } - return true; + if (auto *C = COpt.getValue()) { + SimplifiedAssociatedValue = C; + A.recordDependence(AA, *this, DepClassTy::OPTIONAL); + return true; + } + return false; + } + + bool askSimplifiedValueForOtherAAs(Attributor &A) { + if (askSimplifiedValueFor<AAValueConstantRange>(A)) + return true; + if (askSimplifiedValueFor<AAPotentialValues>(A)) + return true; + return false; } /// See AbstractAttribute::manifest(...). @@ -4468,7 +4663,7 @@ struct AAValueSimplifyArgument final : AAValueSimplifyImpl { auto PredForCallSite = [&](AbstractCallSite ACS) { const IRPosition &ACSArgPos = - IRPosition::callsite_argument(ACS, getArgNo()); + IRPosition::callsite_argument(ACS, getCallSiteArgNo()); // Check if a coresponding argument was found or if it is on not // associated (which can happen for callback calls). if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID) @@ -4490,7 +4685,7 @@ struct AAValueSimplifyArgument final : AAValueSimplifyImpl { bool AllCallSitesKnown; if (!A.checkForAllCallSites(PredForCallSite, *this, true, AllCallSitesKnown)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -4518,7 +4713,7 @@ struct AAValueSimplifyReturned : AAValueSimplifyImpl { }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -4587,10 +4782,76 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { indicatePessimisticFixpoint(); } + /// Check if \p ICmp is an equality comparison (==/!=) with at least one + /// nullptr. If so, try to simplify it using AANonNull on the other operand. + /// Return true if successful, in that case SimplifiedAssociatedValue will be + /// updated and \p Changed is set appropriately. + bool checkForNullPtrCompare(Attributor &A, ICmpInst *ICmp, + ChangeStatus &Changed) { + if (!ICmp) + return false; + if (!ICmp->isEquality()) + return false; + + // This is a comparison with == or !-. We check for nullptr now. + bool Op0IsNull = isa<ConstantPointerNull>(ICmp->getOperand(0)); + bool Op1IsNull = isa<ConstantPointerNull>(ICmp->getOperand(1)); + if (!Op0IsNull && !Op1IsNull) + return false; + + LLVMContext &Ctx = ICmp->getContext(); + // Check for `nullptr ==/!= nullptr` first: + if (Op0IsNull && Op1IsNull) { + Value *NewVal = ConstantInt::get( + Type::getInt1Ty(Ctx), ICmp->getPredicate() == CmpInst::ICMP_EQ); + assert(!SimplifiedAssociatedValue.hasValue() && + "Did not expect non-fixed value for constant comparison"); + SimplifiedAssociatedValue = NewVal; + indicateOptimisticFixpoint(); + Changed = ChangeStatus::CHANGED; + return true; + } + + // Left is the nullptr ==/!= non-nullptr case. We'll use AANonNull on the + // non-nullptr operand and if we assume it's non-null we can conclude the + // result of the comparison. + assert((Op0IsNull || Op1IsNull) && + "Expected nullptr versus non-nullptr comparison at this point"); + + // The index is the operand that we assume is not null. + unsigned PtrIdx = Op0IsNull; + auto &PtrNonNullAA = A.getAAFor<AANonNull>( + *this, IRPosition::value(*ICmp->getOperand(PtrIdx))); + if (!PtrNonNullAA.isAssumedNonNull()) + return false; + + // The new value depends on the predicate, true for != and false for ==. + Value *NewVal = ConstantInt::get(Type::getInt1Ty(Ctx), + ICmp->getPredicate() == CmpInst::ICMP_NE); + + assert((!SimplifiedAssociatedValue.hasValue() || + SimplifiedAssociatedValue == NewVal) && + "Did not expect to change value for zero-comparison"); + + bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + SimplifiedAssociatedValue = NewVal; + + if (PtrNonNullAA.isKnownNonNull()) + indicateOptimisticFixpoint(); + + Changed = HasValueBefore ? ChangeStatus::UNCHANGED : ChangeStatus ::CHANGED; + return true; + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + ChangeStatus Changed; + if (checkForNullPtrCompare(A, dyn_cast<ICmpInst>(&getAnchorValue()), + Changed)) + return Changed; + auto VisitValueCB = [&](Value &V, const Instruction *CtxI, bool &, bool Stripped) -> bool { auto &AA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V)); @@ -4608,7 +4869,7 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { if (!genericValueTraversal<AAValueSimplify, bool>( A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(), /* UseValueSimplify */ false)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -4683,7 +4944,8 @@ struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating { ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue()) : UndefValue::get(V.getType()); if (C) { - Use &U = cast<CallBase>(&getAnchorValue())->getArgOperandUse(getArgNo()); + Use &U = cast<CallBase>(&getAnchorValue()) + ->getArgOperandUse(getCallSiteArgNo()); // We can replace the AssociatedValue with the constant. if (&V != C && V.getType() == C->getType()) { if (A.changeUseAfterManifest(U, *C)) @@ -5002,7 +5264,7 @@ struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl { return getAssociatedValue().getType()->getPointerElementType(); Optional<Type *> Ty; - unsigned ArgNo = getIRPosition().getArgNo(); + unsigned ArgNo = getIRPosition().getCallSiteArgNo(); // Make sure the associated call site argument has the same type at all call // sites and it is an allocation we know is safe to privatize, for now that @@ -5265,8 +5527,9 @@ struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl { new StoreInst(F.getArg(ArgNo + u), Ptr, &IP); } } else if (auto *PrivArrayType = dyn_cast<ArrayType>(PrivType)) { - Type *PointeePtrTy = PrivArrayType->getElementType()->getPointerTo(); - uint64_t PointeeTySize = DL.getTypeStoreSize(PointeePtrTy); + Type *PointeeTy = PrivArrayType->getElementType(); + Type *PointeePtrTy = PointeeTy->getPointerTo(); + uint64_t PointeeTySize = DL.getTypeStoreSize(PointeeTy); for (unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) { Value *Ptr = constructPointer(PointeePtrTy, &Base, u * PointeeTySize, IRB, DL); @@ -5312,7 +5575,7 @@ struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl { for (unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) { Value *Ptr = constructPointer(PointeePtrTy, Base, u * PointeeTySize, IRB, DL); - LoadInst *L = new LoadInst(PointeePtrTy, Ptr, "", IP); + LoadInst *L = new LoadInst(PointeeTy, Ptr, "", IP); L->setAlignment(Alignment); ReplacementValues.push_back(L); } @@ -5356,10 +5619,14 @@ struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl { Function &ReplacementFn, Function::arg_iterator ArgIt) { BasicBlock &EntryBB = ReplacementFn.getEntryBlock(); Instruction *IP = &*EntryBB.getFirstInsertionPt(); - auto *AI = new AllocaInst(PrivatizableType.getValue(), 0, - Arg->getName() + ".priv", IP); + Instruction *AI = new AllocaInst(PrivatizableType.getValue(), 0, + Arg->getName() + ".priv", IP); createInitialization(PrivatizableType.getValue(), *AI, ReplacementFn, ArgIt->getArgNo(), *IP); + + if (AI->getType() != Arg->getType()) + AI = + BitCastInst::CreateBitOrPointerCast(AI, Arg->getType(), "", IP); Arg->replaceAllUsesWith(AI); for (CallInst *CI : TailCalls) @@ -5418,8 +5685,7 @@ struct AAPrivatizablePtrFloating : public AAPrivatizablePtrImpl { /// See AAPrivatizablePtrImpl::identifyPrivatizableType(...) Optional<Type *> identifyPrivatizableType(Attributor &A) override { - Value *Obj = - GetUnderlyingObject(&getAssociatedValue(), A.getInfoCache().getDL()); + Value *Obj = getUnderlyingObject(&getAssociatedValue()); if (!Obj) { LLVM_DEBUG(dbgs() << "[AAPrivatizablePtr] No underlying object found!\n"); return nullptr; @@ -5539,7 +5805,7 @@ struct AAMemoryBehaviorImpl : public AAMemoryBehavior { void initialize(Attributor &A) override { intersectAssumedBits(BEST_STATE); getKnownStateFromValue(getIRPosition(), getState()); - IRAttribute::initialize(A); + AAMemoryBehavior::initialize(A); } /// Return the memory behavior information encoded in the IR for \p IRP. @@ -5634,9 +5900,7 @@ struct AAMemoryBehaviorFloating : AAMemoryBehaviorImpl { /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { AAMemoryBehaviorImpl::initialize(A); - // Initialize the use vector with all direct uses of the associated value. - for (const Use &U : getAssociatedValue().uses()) - Uses.insert(&U); + addUsesOf(A, getAssociatedValue()); } /// See AbstractAttribute::updateImpl(...). @@ -5662,8 +5926,14 @@ private: void analyzeUseIn(Attributor &A, const Use *U, const Instruction *UserI); protected: + /// Add the uses of \p V to the `Uses` set we look at during the update step. + void addUsesOf(Attributor &A, const Value &V); + /// Container for (transitive) uses of the associated argument. - SetVector<const Use *> Uses; + SmallVector<const Use *, 8> Uses; + + /// Set to remember the uses we already traversed. + SmallPtrSet<const Use *, 8> Visited; }; /// Memory behavior attribute for function argument. @@ -5688,9 +5958,7 @@ struct AAMemoryBehaviorArgument : AAMemoryBehaviorFloating { if (!Arg || !A.isFunctionIPOAmendable(*(Arg->getParent()))) { indicatePessimisticFixpoint(); } else { - // Initialize the use vector with all direct uses of the associated value. - for (const Use &U : Arg->uses()) - Uses.insert(&U); + addUsesOf(A, *Arg); } } @@ -5725,14 +5993,21 @@ struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument { /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - if (Argument *Arg = getAssociatedArgument()) { - if (Arg->hasByValAttr()) { - addKnownBits(NO_WRITES); - removeKnownBits(NO_READS); - removeAssumedBits(NO_READS); - } + // If we don't have an associated attribute this is either a variadic call + // or an indirect call, either way, nothing to do here. + Argument *Arg = getAssociatedArgument(); + if (!Arg) { + indicatePessimisticFixpoint(); + return; + } + if (Arg->hasByValAttr()) { + addKnownBits(NO_WRITES); + removeKnownBits(NO_READS); + removeAssumedBits(NO_READS); } AAMemoryBehaviorArgument::initialize(A); + if (getAssociatedFunction()->isDeclaration()) + indicatePessimisticFixpoint(); } /// See AbstractAttribute::updateImpl(...). @@ -5744,9 +6019,7 @@ struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument { Argument *Arg = getAssociatedArgument(); const IRPosition &ArgPos = IRPosition::argument(*Arg); auto &ArgAA = A.getAAFor<AAMemoryBehavior>(*this, ArgPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AAMemoryBehavior::StateType &>(ArgAA.getState())); + return clampStateAndIndicateChange(getState(), ArgAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -5765,6 +6038,14 @@ struct AAMemoryBehaviorCallSiteReturned final : AAMemoryBehaviorFloating { AAMemoryBehaviorCallSiteReturned(const IRPosition &IRP, Attributor &A) : AAMemoryBehaviorFloating(IRP, A) {} + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AAMemoryBehaviorImpl::initialize(A); + Function *F = getAssociatedFunction(); + if (!F || F->isDeclaration()) + indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { // We do not annotate returned values. @@ -5814,10 +6095,8 @@ struct AAMemoryBehaviorCallSite final : AAMemoryBehaviorImpl { void initialize(Attributor &A) override { AAMemoryBehaviorImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F || !A.isFunctionIPOAmendable(*F)) { + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); - return; - } } /// See AbstractAttribute::updateImpl(...). @@ -5829,9 +6108,7 @@ struct AAMemoryBehaviorCallSite final : AAMemoryBehaviorImpl { Function *F = getAssociatedFunction(); const IRPosition &FnPos = IRPosition::function(*F); auto &FnAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); - return clampStateAndIndicateChange( - getState(), - static_cast<const AAMemoryBehavior::StateType &>(FnAA.getState())); + return clampStateAndIndicateChange(getState(), FnAA.getState()); } /// See AbstractAttribute::trackStatistics() @@ -5933,8 +6210,7 @@ ChangeStatus AAMemoryBehaviorFloating::updateImpl(Attributor &A) { // Check if the users of UserI should also be visited. if (followUsersOfUseIn(A, U, UserI)) - for (const Use &UserIUse : UserI->uses()) - Uses.insert(&UserIUse); + addUsesOf(A, *UserI); // If UserI might touch memory we analyze the use in detail. if (UserI->mayReadOrWriteMemory()) @@ -5945,6 +6221,28 @@ ChangeStatus AAMemoryBehaviorFloating::updateImpl(Attributor &A) { : ChangeStatus::UNCHANGED; } +void AAMemoryBehaviorFloating::addUsesOf(Attributor &A, const Value &V) { + SmallVector<const Use *, 8> WL; + for (const Use &U : V.uses()) + WL.push_back(&U); + + while (!WL.empty()) { + const Use *U = WL.pop_back_val(); + if (!Visited.insert(U).second) + continue; + + const Instruction *UserI = cast<Instruction>(U->getUser()); + if (UserI->mayReadOrWriteMemory()) { + Uses.push_back(U); + continue; + } + if (!followUsersOfUseIn(A, U, UserI)) + continue; + for (const Use &UU : UserI->uses()) + WL.push_back(&UU); + } +} + bool AAMemoryBehaviorFloating::followUsersOfUseIn(Attributor &A, const Use *U, const Instruction *UserI) { // The loaded value is unrelated to the pointer argument, no need to @@ -6096,7 +6394,7 @@ struct AAMemoryLocationImpl : public AAMemoryLocation { void initialize(Attributor &A) override { intersectAssumedBits(BEST_STATE); getKnownStateFromValue(A, getIRPosition(), getState()); - IRAttribute::initialize(A); + AAMemoryLocation::initialize(A); } /// Return the memory behavior information encoded in the IR for \p IRP. @@ -6259,6 +6557,13 @@ protected: using AccessSet = SmallSet<AccessInfo, 2, AccessInfo>; AccessSet *AccessKind2Accesses[llvm::CTLog2<VALID_STATE>()]; + /// Categorize the pointer arguments of CB that might access memory in + /// AccessedLoc and update the state and access map accordingly. + void + categorizeArgumentPointerLocations(Attributor &A, CallBase &CB, + AAMemoryLocation::StateType &AccessedLocs, + bool &Changed); + /// Return the kind(s) of location that may be accessed by \p V. AAMemoryLocation::MemoryLocationsKind categorizeAccessedLocations(Attributor &A, Instruction &I, bool &Changed); @@ -6324,6 +6629,7 @@ void AAMemoryLocationImpl::categorizePtrValue( auto VisitValueCB = [&](Value &V, const Instruction *, AAMemoryLocation::StateType &T, bool Stripped) -> bool { + // TODO: recognize the TBAA used for constant accesses. MemoryLocationsKind MLK = NO_LOCATIONS; assert(!isa<GEPOperator>(V) && "GEPs should have been stripped."); if (isa<UndefValue>(V)) @@ -6334,6 +6640,13 @@ void AAMemoryLocationImpl::categorizePtrValue( else MLK = NO_ARGUMENT_MEM; } else if (auto *GV = dyn_cast<GlobalValue>(&V)) { + // Reading constant memory is not treated as a read "effect" by the + // function attr pass so we won't neither. Constants defined by TBAA are + // similar. (We know we do not write it because it is constant.) + if (auto *GVar = dyn_cast<GlobalVariable>(GV)) + if (GVar->isConstant()) + return true; + if (GV->hasLocalLinkage()) MLK = NO_GLOBAL_INTERNAL_MEM; else @@ -6380,6 +6693,30 @@ void AAMemoryLocationImpl::categorizePtrValue( } } +void AAMemoryLocationImpl::categorizeArgumentPointerLocations( + Attributor &A, CallBase &CB, AAMemoryLocation::StateType &AccessedLocs, + bool &Changed) { + for (unsigned ArgNo = 0, E = CB.getNumArgOperands(); ArgNo < E; ++ArgNo) { + + // Skip non-pointer arguments. + const Value *ArgOp = CB.getArgOperand(ArgNo); + if (!ArgOp->getType()->isPtrOrPtrVectorTy()) + continue; + + // Skip readnone arguments. + const IRPosition &ArgOpIRP = IRPosition::callsite_argument(CB, ArgNo); + const auto &ArgOpMemLocationAA = A.getAAFor<AAMemoryBehavior>( + *this, ArgOpIRP, /* TrackDependence */ true, DepClassTy::OPTIONAL); + + if (ArgOpMemLocationAA.isAssumedReadNone()) + continue; + + // Categorize potentially accessed pointer arguments as if there was an + // access instruction with them as pointer. + categorizePtrValue(A, CB, *ArgOp, AccessedLocs, Changed); + } +} + AAMemoryLocation::MemoryLocationsKind AAMemoryLocationImpl::categorizeAccessedLocations(Attributor &A, Instruction &I, bool &Changed) { @@ -6441,28 +6778,8 @@ AAMemoryLocationImpl::categorizeAccessedLocations(Attributor &A, Instruction &I, // Now handle argument memory if it might be accessed. bool HasArgAccesses = ((~CBAssumedNotAccessedLocs) & NO_ARGUMENT_MEM); - if (HasArgAccesses) { - for (unsigned ArgNo = 0, E = CB->getNumArgOperands(); ArgNo < E; - ++ArgNo) { - - // Skip non-pointer arguments. - const Value *ArgOp = CB->getArgOperand(ArgNo); - if (!ArgOp->getType()->isPtrOrPtrVectorTy()) - continue; - - // Skip readnone arguments. - const IRPosition &ArgOpIRP = IRPosition::callsite_argument(*CB, ArgNo); - const auto &ArgOpMemLocationAA = A.getAAFor<AAMemoryBehavior>( - *this, ArgOpIRP, /* TrackDependence */ true, DepClassTy::OPTIONAL); - - if (ArgOpMemLocationAA.isAssumedReadNone()) - continue; - - // Categorize potentially accessed pointer arguments as if there was an - // access instruction with them as pointer. - categorizePtrValue(A, I, *ArgOp, AccessedLocs, Changed); - } - } + if (HasArgAccesses) + categorizeArgumentPointerLocations(A, *CB, AccessedLocs, Changed); LLVM_DEBUG( dbgs() << "[AAMemoryLocation] Accessed state after argument handling: " @@ -6514,7 +6831,9 @@ struct AAMemoryLocationFunction final : public AAMemoryLocationImpl { LLVM_DEBUG(dbgs() << "[AAMemoryLocation] Accessed locations for " << I << ": " << getMemoryLocationsAsStr(MLK) << "\n"); removeAssumedBits(inverseLocation(MLK, false, false)); - return true; + // Stop once only the valid bit set in the *not assumed location*, thus + // once we don't actually exclude any memory locations in the state. + return getAssumedNotAccessedLocation() != VALID_STATE; }; if (!A.checkForAllReadWriteInstructions(CheckRWInst, *this)) @@ -6546,10 +6865,8 @@ struct AAMemoryLocationCallSite final : AAMemoryLocationImpl { void initialize(Attributor &A) override { AAMemoryLocationImpl::initialize(A); Function *F = getAssociatedFunction(); - if (!F || !A.isFunctionIPOAmendable(*F)) { + if (!F || F->isDeclaration()) indicatePessimisticFixpoint(); - return; - } } /// See AbstractAttribute::updateImpl(...). @@ -6655,7 +6972,6 @@ struct AAValueConstantRangeImpl : AAValueConstantRange { if (!LVI || !CtxI) return getWorstState(getBitWidth()); return LVI->getConstantRange(&getAssociatedValue(), - const_cast<BasicBlock *>(CtxI->getParent()), const_cast<Instruction *>(CtxI)); } @@ -6759,10 +7075,13 @@ struct AAValueConstantRangeImpl : AAValueConstantRange { auto &V = getAssociatedValue(); if (!AssumedConstantRange.isEmptySet() && !AssumedConstantRange.isSingleElement()) { - if (Instruction *I = dyn_cast<Instruction>(&V)) + if (Instruction *I = dyn_cast<Instruction>(&V)) { + assert(I == getCtxI() && "Should not annotate an instruction which is " + "not the context instruction"); if (isa<CallInst>(I) || isa<LoadInst>(I)) if (setRangeMetadataIfisBetterRange(I, AssumedConstantRange)) Changed = ChangeStatus::CHANGED; + } } return Changed; @@ -6831,6 +7150,9 @@ struct AAValueConstantRangeFloating : AAValueConstantRangeImpl { return; } + if (isa<CallBase>(&V)) + return; + if (isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<CastInst>(&V)) return; // If it is a load instruction with range metadata, use it. @@ -7068,11 +7390,641 @@ struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating { AAValueConstantRangeCallSiteArgument(const IRPosition &IRP, Attributor &A) : AAValueConstantRangeFloating(IRP, A) {} + /// See AbstractAttribute::manifest() + ChangeStatus manifest(Attributor &A) override { + return ChangeStatus::UNCHANGED; + } + /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(value_range) } }; + +/// ------------------ Potential Values Attribute ------------------------- + +struct AAPotentialValuesImpl : AAPotentialValues { + using StateType = PotentialConstantIntValuesState; + + AAPotentialValuesImpl(const IRPosition &IRP, Attributor &A) + : AAPotentialValues(IRP, A) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + std::string Str; + llvm::raw_string_ostream OS(Str); + OS << getState(); + return OS.str(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + return indicatePessimisticFixpoint(); + } +}; + +struct AAPotentialValuesArgument final + : AAArgumentFromCallSiteArguments<AAPotentialValues, AAPotentialValuesImpl, + PotentialConstantIntValuesState> { + using Base = + AAArgumentFromCallSiteArguments<AAPotentialValues, AAPotentialValuesImpl, + PotentialConstantIntValuesState>; + AAPotentialValuesArgument(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + if (!getAnchorScope() || getAnchorScope()->isDeclaration()) { + indicatePessimisticFixpoint(); + } else { + Base::initialize(A); + } + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(potential_values) + } +}; + +struct AAPotentialValuesReturned + : AAReturnedFromReturnedValues<AAPotentialValues, AAPotentialValuesImpl> { + using Base = + AAReturnedFromReturnedValues<AAPotentialValues, AAPotentialValuesImpl>; + AAPotentialValuesReturned(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFloating : AAPotentialValuesImpl { + AAPotentialValuesFloating(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast<ConstantInt>(&V)) { + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa<UndefValue>(&V)) { + unionAssumedWithUndef(); + indicateOptimisticFixpoint(); + return; + } + + if (isa<BinaryOperator>(&V) || isa<ICmpInst>(&V) || isa<CastInst>(&V)) + return; + + if (isa<SelectInst>(V) || isa<PHINode>(V)) + return; + + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[AAPotentialValues] We give up: " + << getAssociatedValue() << "\n"); + } + + static bool calculateICmpInst(const ICmpInst *ICI, const APInt &LHS, + const APInt &RHS) { + ICmpInst::Predicate Pred = ICI->getPredicate(); + switch (Pred) { + case ICmpInst::ICMP_UGT: + return LHS.ugt(RHS); + case ICmpInst::ICMP_SGT: + return LHS.sgt(RHS); + case ICmpInst::ICMP_EQ: + return LHS.eq(RHS); + case ICmpInst::ICMP_UGE: + return LHS.uge(RHS); + case ICmpInst::ICMP_SGE: + return LHS.sge(RHS); + case ICmpInst::ICMP_ULT: + return LHS.ult(RHS); + case ICmpInst::ICMP_SLT: + return LHS.slt(RHS); + case ICmpInst::ICMP_NE: + return LHS.ne(RHS); + case ICmpInst::ICMP_ULE: + return LHS.ule(RHS); + case ICmpInst::ICMP_SLE: + return LHS.sle(RHS); + default: + llvm_unreachable("Invalid ICmp predicate!"); + } + } + + static APInt calculateCastInst(const CastInst *CI, const APInt &Src, + uint32_t ResultBitWidth) { + Instruction::CastOps CastOp = CI->getOpcode(); + switch (CastOp) { + default: + llvm_unreachable("unsupported or not integer cast"); + case Instruction::Trunc: + return Src.trunc(ResultBitWidth); + case Instruction::SExt: + return Src.sext(ResultBitWidth); + case Instruction::ZExt: + return Src.zext(ResultBitWidth); + case Instruction::BitCast: + return Src; + } + } + + static APInt calculateBinaryOperator(const BinaryOperator *BinOp, + const APInt &LHS, const APInt &RHS, + bool &SkipOperation, bool &Unsupported) { + Instruction::BinaryOps BinOpcode = BinOp->getOpcode(); + // Unsupported is set to true when the binary operator is not supported. + // SkipOperation is set to true when UB occur with the given operand pair + // (LHS, RHS). + // TODO: we should look at nsw and nuw keywords to handle operations + // that create poison or undef value. + switch (BinOpcode) { + default: + Unsupported = true; + return LHS; + case Instruction::Add: + return LHS + RHS; + case Instruction::Sub: + return LHS - RHS; + case Instruction::Mul: + return LHS * RHS; + case Instruction::UDiv: + if (RHS.isNullValue()) { + SkipOperation = true; + return LHS; + } + return LHS.udiv(RHS); + case Instruction::SDiv: + if (RHS.isNullValue()) { + SkipOperation = true; + return LHS; + } + return LHS.sdiv(RHS); + case Instruction::URem: + if (RHS.isNullValue()) { + SkipOperation = true; + return LHS; + } + return LHS.urem(RHS); + case Instruction::SRem: + if (RHS.isNullValue()) { + SkipOperation = true; + return LHS; + } + return LHS.srem(RHS); + case Instruction::Shl: + return LHS.shl(RHS); + case Instruction::LShr: + return LHS.lshr(RHS); + case Instruction::AShr: + return LHS.ashr(RHS); + case Instruction::And: + return LHS & RHS; + case Instruction::Or: + return LHS | RHS; + case Instruction::Xor: + return LHS ^ RHS; + } + } + + bool calculateBinaryOperatorAndTakeUnion(const BinaryOperator *BinOp, + const APInt &LHS, const APInt &RHS) { + bool SkipOperation = false; + bool Unsupported = false; + APInt Result = + calculateBinaryOperator(BinOp, LHS, RHS, SkipOperation, Unsupported); + if (Unsupported) + return false; + // If SkipOperation is true, we can ignore this operand pair (L, R). + if (!SkipOperation) + unionAssumed(Result); + return isValidState(); + } + + ChangeStatus updateWithICmpInst(Attributor &A, ICmpInst *ICI) { + auto AssumedBefore = getAssumed(); + Value *LHS = ICI->getOperand(0); + Value *RHS = ICI->getOperand(1); + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + auto &LHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*LHS)); + if (!LHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + auto &RHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*RHS)); + if (!RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + const DenseSet<APInt> &LHSAAPVS = LHSAA.getAssumedSet(); + const DenseSet<APInt> &RHSAAPVS = RHSAA.getAssumedSet(); + + // TODO: make use of undef flag to limit potential values aggressively. + bool MaybeTrue = false, MaybeFalse = false; + const APInt Zero(RHS->getType()->getIntegerBitWidth(), 0); + if (LHSAA.undefIsContained() && RHSAA.undefIsContained()) { + // The result of any comparison between undefs can be soundly replaced + // with undef. + unionAssumedWithUndef(); + } else if (LHSAA.undefIsContained()) { + bool MaybeTrue = false, MaybeFalse = false; + for (const APInt &R : RHSAAPVS) { + bool CmpResult = calculateICmpInst(ICI, Zero, R); + MaybeTrue |= CmpResult; + MaybeFalse |= !CmpResult; + if (MaybeTrue & MaybeFalse) + return indicatePessimisticFixpoint(); + } + } else if (RHSAA.undefIsContained()) { + for (const APInt &L : LHSAAPVS) { + bool CmpResult = calculateICmpInst(ICI, L, Zero); + MaybeTrue |= CmpResult; + MaybeFalse |= !CmpResult; + if (MaybeTrue & MaybeFalse) + return indicatePessimisticFixpoint(); + } + } else { + for (const APInt &L : LHSAAPVS) { + for (const APInt &R : RHSAAPVS) { + bool CmpResult = calculateICmpInst(ICI, L, R); + MaybeTrue |= CmpResult; + MaybeFalse |= !CmpResult; + if (MaybeTrue & MaybeFalse) + return indicatePessimisticFixpoint(); + } + } + } + if (MaybeTrue) + unionAssumed(APInt(/* numBits */ 1, /* val */ 1)); + if (MaybeFalse) + unionAssumed(APInt(/* numBits */ 1, /* val */ 0)); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithSelectInst(Attributor &A, SelectInst *SI) { + auto AssumedBefore = getAssumed(); + Value *LHS = SI->getTrueValue(); + Value *RHS = SI->getFalseValue(); + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + // TODO: Use assumed simplified condition value + auto &LHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*LHS)); + if (!LHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + auto &RHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*RHS)); + if (!RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + if (LHSAA.undefIsContained() && RHSAA.undefIsContained()) + // select i1 *, undef , undef => undef + unionAssumedWithUndef(); + else { + unionAssumed(LHSAA); + unionAssumed(RHSAA); + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithCastInst(Attributor &A, CastInst *CI) { + auto AssumedBefore = getAssumed(); + if (!CI->isIntegerCast()) + return indicatePessimisticFixpoint(); + assert(CI->getNumOperands() == 1 && "Expected cast to be unary!"); + uint32_t ResultBitWidth = CI->getDestTy()->getIntegerBitWidth(); + Value *Src = CI->getOperand(0); + auto &SrcAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*Src)); + if (!SrcAA.isValidState()) + return indicatePessimisticFixpoint(); + const DenseSet<APInt> &SrcAAPVS = SrcAA.getAssumedSet(); + if (SrcAA.undefIsContained()) + unionAssumedWithUndef(); + else { + for (const APInt &S : SrcAAPVS) { + APInt T = calculateCastInst(CI, S, ResultBitWidth); + unionAssumed(T); + } + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithBinaryOperator(Attributor &A, BinaryOperator *BinOp) { + auto AssumedBefore = getAssumed(); + Value *LHS = BinOp->getOperand(0); + Value *RHS = BinOp->getOperand(1); + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + auto &LHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*LHS)); + if (!LHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + auto &RHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*RHS)); + if (!RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + const DenseSet<APInt> &LHSAAPVS = LHSAA.getAssumedSet(); + const DenseSet<APInt> &RHSAAPVS = RHSAA.getAssumedSet(); + const APInt Zero = APInt(LHS->getType()->getIntegerBitWidth(), 0); + + // TODO: make use of undef flag to limit potential values aggressively. + if (LHSAA.undefIsContained() && RHSAA.undefIsContained()) { + if (!calculateBinaryOperatorAndTakeUnion(BinOp, Zero, Zero)) + return indicatePessimisticFixpoint(); + } else if (LHSAA.undefIsContained()) { + for (const APInt &R : RHSAAPVS) { + if (!calculateBinaryOperatorAndTakeUnion(BinOp, Zero, R)) + return indicatePessimisticFixpoint(); + } + } else if (RHSAA.undefIsContained()) { + for (const APInt &L : LHSAAPVS) { + if (!calculateBinaryOperatorAndTakeUnion(BinOp, L, Zero)) + return indicatePessimisticFixpoint(); + } + } else { + for (const APInt &L : LHSAAPVS) { + for (const APInt &R : RHSAAPVS) { + if (!calculateBinaryOperatorAndTakeUnion(BinOp, L, R)) + return indicatePessimisticFixpoint(); + } + } + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithPHINode(Attributor &A, PHINode *PHI) { + auto AssumedBefore = getAssumed(); + for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) { + Value *IncomingValue = PHI->getIncomingValue(u); + auto &PotentialValuesAA = A.getAAFor<AAPotentialValues>( + *this, IRPosition::value(*IncomingValue)); + if (!PotentialValuesAA.isValidState()) + return indicatePessimisticFixpoint(); + if (PotentialValuesAA.undefIsContained()) + unionAssumedWithUndef(); + else + unionAssumed(PotentialValuesAA.getAssumed()); + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + Value &V = getAssociatedValue(); + Instruction *I = dyn_cast<Instruction>(&V); + + if (auto *ICI = dyn_cast<ICmpInst>(I)) + return updateWithICmpInst(A, ICI); + + if (auto *SI = dyn_cast<SelectInst>(I)) + return updateWithSelectInst(A, SI); + + if (auto *CI = dyn_cast<CastInst>(I)) + return updateWithCastInst(A, CI); + + if (auto *BinOp = dyn_cast<BinaryOperator>(I)) + return updateWithBinaryOperator(A, BinOp); + + if (auto *PHI = dyn_cast<PHINode>(I)) + return updateWithPHINode(A, PHI); + + return indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFunction : AAPotentialValuesImpl { + AAPotentialValuesFunction(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("AAPotentialValues(Function|CallSite)::updateImpl will " + "not be called"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FN_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSite : AAPotentialValuesFunction { + AAPotentialValuesCallSite(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesFunction(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CS_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteReturned + : AACallSiteReturnedFromReturned<AAPotentialValues, AAPotentialValuesImpl> { + AAPotentialValuesCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AACallSiteReturnedFromReturned<AAPotentialValues, + AAPotentialValuesImpl>(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteArgument : AAPotentialValuesFloating { + AAPotentialValuesCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesFloating(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast<ConstantInt>(&V)) { + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa<UndefValue>(&V)) { + unionAssumedWithUndef(); + indicateOptimisticFixpoint(); + return; + } + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + Value &V = getAssociatedValue(); + auto AssumedBefore = getAssumed(); + auto &AA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(V)); + const auto &S = AA.getAssumed(); + unionAssumed(S); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(potential_values) + } +}; + +/// ------------------------ NoUndef Attribute --------------------------------- +struct AANoUndefImpl : AANoUndef { + AANoUndefImpl(const IRPosition &IRP, Attributor &A) : AANoUndef(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + if (getIRPosition().hasAttr({Attribute::NoUndef})) { + indicateOptimisticFixpoint(); + return; + } + Value &V = getAssociatedValue(); + if (isa<UndefValue>(V)) + indicatePessimisticFixpoint(); + else if (isa<FreezeInst>(V)) + indicateOptimisticFixpoint(); + else if (getPositionKind() != IRPosition::IRP_RETURNED && + isGuaranteedNotToBeUndefOrPoison(&V)) + indicateOptimisticFixpoint(); + else + AANoUndef::initialize(A); + } + + /// See followUsesInMBEC + bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I, + AANoUndef::StateType &State) { + const Value *UseV = U->get(); + const DominatorTree *DT = nullptr; + AssumptionCache *AC = nullptr; + InformationCache &InfoCache = A.getInfoCache(); + if (Function *F = getAnchorScope()) { + DT = InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*F); + AC = InfoCache.getAnalysisResultForFunction<AssumptionAnalysis>(*F); + } + State.setKnown(isGuaranteedNotToBeUndefOrPoison(UseV, AC, I, DT)); + bool TrackUse = false; + // Track use for instructions which must produce undef or poison bits when + // at least one operand contains such bits. + if (isa<CastInst>(*I) || isa<GetElementPtrInst>(*I)) + TrackUse = true; + return TrackUse; + } + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + return getAssumed() ? "noundef" : "may-undef-or-poison"; + } + + ChangeStatus manifest(Attributor &A) override { + // We don't manifest noundef attribute for dead positions because the + // associated values with dead positions would be replaced with undef + // values. + if (A.isAssumedDead(getIRPosition(), nullptr, nullptr)) + return ChangeStatus::UNCHANGED; + // A position whose simplified value does not have any value is + // considered to be dead. We don't manifest noundef in such positions for + // the same reason above. + auto &ValueSimplifyAA = A.getAAFor<AAValueSimplify>( + *this, getIRPosition(), /* TrackDependence */ false); + if (!ValueSimplifyAA.getAssumedSimplifiedValue(A).hasValue()) + return ChangeStatus::UNCHANGED; + return AANoUndef::manifest(A); + } +}; + +struct AANoUndefFloating : public AANoUndefImpl { + AANoUndefFloating(const IRPosition &IRP, Attributor &A) + : AANoUndefImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AANoUndefImpl::initialize(A); + if (!getState().isAtFixpoint()) + if (Instruction *CtxI = getCtxI()) + followUsesInMBEC(*this, A, getState(), *CtxI); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + auto VisitValueCB = [&](Value &V, const Instruction *CtxI, + AANoUndef::StateType &T, bool Stripped) -> bool { + const auto &AA = A.getAAFor<AANoUndef>(*this, IRPosition::value(V)); + if (!Stripped && this == &AA) { + T.indicatePessimisticFixpoint(); + } else { + const AANoUndef::StateType &S = + static_cast<const AANoUndef::StateType &>(AA.getState()); + T ^= S; + } + return T.isValidState(); + }; + + StateType T; + if (!genericValueTraversal<AANoUndef, StateType>( + A, getIRPosition(), *this, T, VisitValueCB, getCtxI())) + return indicatePessimisticFixpoint(); + + return clampStateAndIndicateChange(getState(), T); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noundef) } +}; + +struct AANoUndefReturned final + : AAReturnedFromReturnedValues<AANoUndef, AANoUndefImpl> { + AANoUndefReturned(const IRPosition &IRP, Attributor &A) + : AAReturnedFromReturnedValues<AANoUndef, AANoUndefImpl>(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noundef) } +}; + +struct AANoUndefArgument final + : AAArgumentFromCallSiteArguments<AANoUndef, AANoUndefImpl> { + AANoUndefArgument(const IRPosition &IRP, Attributor &A) + : AAArgumentFromCallSiteArguments<AANoUndef, AANoUndefImpl>(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noundef) } +}; + +struct AANoUndefCallSiteArgument final : AANoUndefFloating { + AANoUndefCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AANoUndefFloating(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noundef) } +}; + +struct AANoUndefCallSiteReturned final + : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl> { + AANoUndefCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl>(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noundef) } +}; } // namespace const char AAReturnedValues::ID = 0; @@ -7096,6 +8048,8 @@ const char AAPrivatizablePtr::ID = 0; const char AAMemoryBehavior::ID = 0; const char AAMemoryLocation::ID = 0; const char AAValueConstantRange::ID = 0; +const char AAPotentialValues::ID = 0; +const char AANoUndef::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -7205,6 +8159,8 @@ 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_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPotentialValues) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoUndef) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) |