diff options
Diffstat (limited to 'llvm/lib/Transforms/IPO/Attributor.cpp')
| -rw-r--r-- | llvm/lib/Transforms/IPO/Attributor.cpp | 244 |
1 files changed, 226 insertions, 18 deletions
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp index 12b8a0ef9d00..d66140a726f6 100644 --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -183,6 +183,31 @@ ChangeStatus &llvm::operator&=(ChangeStatus &L, ChangeStatus R) { } ///} +bool AA::isNoSyncInst(Attributor &A, const Instruction &I, + const AbstractAttribute &QueryingAA) { + // We are looking for volatile instructions or non-relaxed atomics. + if (const auto *CB = dyn_cast<CallBase>(&I)) { + if (CB->hasFnAttr(Attribute::NoSync)) + return true; + + // Non-convergent and readnone imply nosync. + if (!CB->isConvergent() && !CB->mayReadOrWriteMemory()) + return true; + + if (AANoSync::isNoSyncIntrinsic(&I)) + return true; + + const auto &NoSyncAA = A.getAAFor<AANoSync>( + QueryingAA, IRPosition::callsite_function(*CB), DepClassTy::OPTIONAL); + return NoSyncAA.isAssumedNoSync(); + } + + if (!I.mayReadOrWriteMemory()) + return true; + + return !I.isVolatile() && !AANoSync::isNonRelaxedAtomic(&I); +} + bool AA::isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA, const Value &V) { if (auto *C = dyn_cast<Constant>(&V)) @@ -370,6 +395,162 @@ bool AA::getPotentialCopiesOfStoredValue( return true; } +static bool isAssumedReadOnlyOrReadNone(Attributor &A, const IRPosition &IRP, + const AbstractAttribute &QueryingAA, + bool RequireReadNone, bool &IsKnown) { + + IRPosition::Kind Kind = IRP.getPositionKind(); + if (Kind == IRPosition::IRP_FUNCTION || Kind == IRPosition::IRP_CALL_SITE) { + const auto &MemLocAA = + A.getAAFor<AAMemoryLocation>(QueryingAA, IRP, DepClassTy::NONE); + if (MemLocAA.isAssumedReadNone()) { + IsKnown = MemLocAA.isKnownReadNone(); + if (!IsKnown) + A.recordDependence(MemLocAA, QueryingAA, DepClassTy::OPTIONAL); + return true; + } + } + + const auto &MemBehaviorAA = + A.getAAFor<AAMemoryBehavior>(QueryingAA, IRP, DepClassTy::NONE); + if (MemBehaviorAA.isAssumedReadNone() || + (!RequireReadNone && MemBehaviorAA.isAssumedReadOnly())) { + IsKnown = RequireReadNone ? MemBehaviorAA.isKnownReadNone() + : MemBehaviorAA.isKnownReadOnly(); + if (!IsKnown) + A.recordDependence(MemBehaviorAA, QueryingAA, DepClassTy::OPTIONAL); + return true; + } + + return false; +} + +bool AA::isAssumedReadOnly(Attributor &A, const IRPosition &IRP, + const AbstractAttribute &QueryingAA, bool &IsKnown) { + return isAssumedReadOnlyOrReadNone(A, IRP, QueryingAA, + /* RequireReadNone */ false, IsKnown); +} +bool AA::isAssumedReadNone(Attributor &A, const IRPosition &IRP, + const AbstractAttribute &QueryingAA, bool &IsKnown) { + return isAssumedReadOnlyOrReadNone(A, IRP, QueryingAA, + /* RequireReadNone */ true, IsKnown); +} + +static bool +isPotentiallyReachable(Attributor &A, const Instruction &FromI, + const Instruction *ToI, const Function &ToFn, + const AbstractAttribute &QueryingAA, + std::function<bool(const Function &F)> GoBackwardsCB) { + LLVM_DEBUG(dbgs() << "[AA] isPotentiallyReachable @" << ToFn.getName() + << " from " << FromI << " [GBCB: " << bool(GoBackwardsCB) + << "]\n"); + + SmallPtrSet<const Instruction *, 8> Visited; + SmallVector<const Instruction *> Worklist; + Worklist.push_back(&FromI); + + while (!Worklist.empty()) { + const Instruction *CurFromI = Worklist.pop_back_val(); + if (!Visited.insert(CurFromI).second) + continue; + + const Function *FromFn = CurFromI->getFunction(); + if (FromFn == &ToFn) { + if (!ToI) + return true; + LLVM_DEBUG(dbgs() << "[AA] check " << *ToI << " from " << *CurFromI + << " intraprocedurally\n"); + const auto &ReachabilityAA = A.getAAFor<AAReachability>( + QueryingAA, IRPosition::function(ToFn), DepClassTy::OPTIONAL); + bool Result = ReachabilityAA.isAssumedReachable(A, *CurFromI, *ToI); + LLVM_DEBUG(dbgs() << "[AA] " << *CurFromI << " " + << (Result ? "can potentially " : "cannot ") << "reach " + << *ToI << " [Intra]\n"); + if (Result) + return true; + continue; + } + + // TODO: If we can go arbitrarily backwards we will eventually reach an + // entry point that can reach ToI. Only once this takes a set of blocks + // through which we cannot go, or once we track internal functions not + // accessible from the outside, it makes sense to perform backwards analysis + // in the absence of a GoBackwardsCB. + if (!GoBackwardsCB) { + LLVM_DEBUG(dbgs() << "[AA] check @" << ToFn.getName() << " from " + << *CurFromI << " is not checked backwards, abort\n"); + return true; + } + + // Check if the current instruction is already known to reach the ToFn. + const auto &FnReachabilityAA = A.getAAFor<AAFunctionReachability>( + QueryingAA, IRPosition::function(*FromFn), DepClassTy::OPTIONAL); + bool Result = FnReachabilityAA.instructionCanReach( + A, *CurFromI, ToFn, /* UseBackwards */ false); + LLVM_DEBUG(dbgs() << "[AA] " << *CurFromI << " in @" << FromFn->getName() + << " " << (Result ? "can potentially " : "cannot ") + << "reach @" << ToFn.getName() << " [FromFn]\n"); + if (Result) + return true; + + // If we do not go backwards from the FromFn we are done here and so far we + // could not find a way to reach ToFn/ToI. + if (!GoBackwardsCB(*FromFn)) + continue; + + LLVM_DEBUG(dbgs() << "Stepping backwards to the call sites of @" + << FromFn->getName() << "\n"); + + auto CheckCallSite = [&](AbstractCallSite ACS) { + CallBase *CB = ACS.getInstruction(); + if (!CB) + return false; + + if (isa<InvokeInst>(CB)) + return false; + + Instruction *Inst = CB->getNextNonDebugInstruction(); + Worklist.push_back(Inst); + return true; + }; + + bool AllCallSitesKnown; + Result = !A.checkForAllCallSites(CheckCallSite, *FromFn, + /* RequireAllCallSites */ true, + &QueryingAA, AllCallSitesKnown); + if (Result) { + LLVM_DEBUG(dbgs() << "[AA] stepping back to call sites from " << *CurFromI + << " in @" << FromFn->getName() + << " failed, give up\n"); + return true; + } + + LLVM_DEBUG(dbgs() << "[AA] stepped back to call sites from " << *CurFromI + << " in @" << FromFn->getName() + << " worklist size is: " << Worklist.size() << "\n"); + } + return false; +} + +bool AA::isPotentiallyReachable( + Attributor &A, const Instruction &FromI, const Instruction &ToI, + const AbstractAttribute &QueryingAA, + std::function<bool(const Function &F)> GoBackwardsCB) { + LLVM_DEBUG(dbgs() << "[AA] isPotentiallyReachable " << ToI << " from " + << FromI << " [GBCB: " << bool(GoBackwardsCB) << "]\n"); + const Function *ToFn = ToI.getFunction(); + return ::isPotentiallyReachable(A, FromI, &ToI, *ToFn, QueryingAA, + GoBackwardsCB); +} + +bool AA::isPotentiallyReachable( + Attributor &A, const Instruction &FromI, const Function &ToFn, + const AbstractAttribute &QueryingAA, + std::function<bool(const Function &F)> GoBackwardsCB) { + return ::isPotentiallyReachable(A, FromI, /* ToI */ nullptr, ToFn, QueryingAA, + GoBackwardsCB); +} + /// Return true if \p New is equal or worse than \p Old. static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { if (!Old.isIntAttribute()) @@ -704,9 +885,8 @@ void IRPosition::verify() { "Expected a nullptr for an invalid position!"); return; case IRP_FLOAT: - assert((!isa<CallBase>(&getAssociatedValue()) && - !isa<Argument>(&getAssociatedValue())) && - "Expected specialized kind for call base and argument values!"); + assert((!isa<Argument>(&getAssociatedValue())) && + "Expected specialized kind for argument values!"); return; case IRP_RETURNED: assert(isa<Function>(getAsValuePtr()) && @@ -900,7 +1080,7 @@ bool Attributor::isAssumedDead(const Use &U, UsedAssumedInformation, CheckBBLivenessOnly, DepClass); } - return isAssumedDead(IRPosition::value(*UserI), QueryingAA, FnLivenessAA, + return isAssumedDead(IRPosition::inst(*UserI), QueryingAA, FnLivenessAA, UsedAssumedInformation, CheckBBLivenessOnly, DepClass); } @@ -923,7 +1103,8 @@ bool Attributor::isAssumedDead(const Instruction &I, // If we have a context instruction and a liveness AA we use it. if (FnLivenessAA && FnLivenessAA->getIRPosition().getAnchorScope() == I.getFunction() && - FnLivenessAA->isAssumedDead(&I)) { + (CheckBBLivenessOnly ? FnLivenessAA->isAssumedDead(I.getParent()) + : FnLivenessAA->isAssumedDead(&I))) { if (QueryingAA) recordDependence(*FnLivenessAA, *QueryingAA, DepClass); if (!FnLivenessAA->isKnownDead(&I)) @@ -934,8 +1115,9 @@ bool Attributor::isAssumedDead(const Instruction &I, if (CheckBBLivenessOnly) return false; - const AAIsDead &IsDeadAA = getOrCreateAAFor<AAIsDead>( - IRPosition::value(I, CBCtx), QueryingAA, DepClassTy::NONE); + const IRPosition IRP = IRPosition::inst(I, CBCtx); + const AAIsDead &IsDeadAA = + getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClassTy::NONE); // Don't check liveness for AAIsDead. if (QueryingAA == &IsDeadAA) return false; @@ -1035,8 +1217,14 @@ bool Attributor::checkForAllUses( const Use *U = Worklist.pop_back_val(); if (isa<PHINode>(U->getUser()) && !Visited.insert(U).second) continue; - LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in " - << *U->getUser() << "\n"); + LLVM_DEBUG({ + if (auto *Fn = dyn_cast<Function>(U->getUser())) + dbgs() << "[Attributor] Check use: " << **U << " in " << Fn->getName() + << "\n"; + else + dbgs() << "[Attributor] Check use: " << **U << " in " << *U->getUser() + << "\n"; + }); bool UsedAssumedInformation = false; if (isAssumedDead(*U, &QueryingAA, LivenessAA, UsedAssumedInformation, CheckBBLivenessOnly, LivenessDepClass)) { @@ -1126,8 +1314,14 @@ bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred, SmallVector<const Use *, 8> Uses(make_pointer_range(Fn.uses())); for (unsigned u = 0; u < Uses.size(); ++u) { const Use &U = *Uses[u]; - LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << " in " - << *U.getUser() << "\n"); + LLVM_DEBUG({ + if (auto *Fn = dyn_cast<Function>(U)) + dbgs() << "[Attributor] Check use: " << Fn->getName() << " in " + << *U.getUser() << "\n"; + else + dbgs() << "[Attributor] Check use: " << *U << " in " << *U.getUser() + << "\n"; + }); bool UsedAssumedInformation = false; if (isAssumedDead(U, QueryingAA, nullptr, UsedAssumedInformation, /* CheckBBLivenessOnly */ true)) { @@ -1268,9 +1462,12 @@ static bool checkForAllInstructionsImpl( for (Instruction *I : *Insts) { // Skip dead instructions. if (A && !CheckPotentiallyDead && - A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA, - UsedAssumedInformation, CheckBBLivenessOnly)) + A->isAssumedDead(IRPosition::inst(*I), QueryingAA, LivenessAA, + UsedAssumedInformation, CheckBBLivenessOnly)) { + LLVM_DEBUG(dbgs() << "[Attributor] Instruction " << *I + << " is potentially dead, skip!\n";); continue; + } if (!Pred(*I)) return false; @@ -1329,7 +1526,7 @@ bool Attributor::checkForAllReadWriteInstructions( for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) { // Skip dead instructions. - if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA, + if (isAssumedDead(IRPosition::inst(*I), &QueryingAA, &LivenessAA, UsedAssumedInformation)) continue; @@ -1381,9 +1578,11 @@ void Attributor::runTillFixpoint() { InvalidAA->Deps.pop_back(); AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer()); if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) { + LLVM_DEBUG(dbgs() << " - recompute: " << *DepAA); Worklist.insert(DepAA); continue; } + LLVM_DEBUG(dbgs() << " - invalidate: " << *DepAA); DepAA->getState().indicatePessimisticFixpoint(); assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!"); if (!DepAA->getState().isValidState()) @@ -1433,6 +1632,9 @@ void Attributor::runTillFixpoint() { // Note that dependent ones are added above. Worklist.clear(); Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); + Worklist.insert(QueryAAsAwaitingUpdate.begin(), + QueryAAsAwaitingUpdate.end()); + QueryAAsAwaitingUpdate.clear(); } while (!Worklist.empty() && (IterationCounter++ < MaxFixedPointIterations || VerifyMaxFixpointIterations)); @@ -1492,6 +1694,12 @@ void Attributor::runTillFixpoint() { } } +void Attributor::registerForUpdate(AbstractAttribute &AA) { + assert(AA.isQueryAA() && + "Non-query AAs should not be required to register for updates!"); + QueryAAsAwaitingUpdate.insert(&AA); +} + ChangeStatus Attributor::manifestAttributes() { TimeTraceScope TimeScope("Attributor::manifestAttributes"); size_t NumFinalAAs = DG.SyntheticRoot.Deps.size(); @@ -1792,7 +2000,7 @@ ChangeStatus Attributor::cleanupIR() { // 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); + detachDeadBlocks(ToBeDeletedBBs, nullptr); } identifyDeadInternalFunctions(); @@ -1897,7 +2105,7 @@ ChangeStatus Attributor::updateAA(AbstractAttribute &AA) { /* CheckBBLivenessOnly */ true)) CS = AA.update(*this); - if (DV.empty()) { + if (!AA.isQueryAA() && DV.empty()) { // If the attribute did not query any non-fix information, the state // will not change and we can indicate that right away. AAState.indicateOptimisticFixpoint(); @@ -2601,12 +2809,12 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { auto CallSitePred = [&](Instruction &I) -> bool { auto &CB = cast<CallBase>(I); - IRPosition CBRetPos = IRPosition::callsite_returned(CB); + IRPosition CBInstPos = IRPosition::inst(CB); IRPosition CBFnPos = IRPosition::callsite_function(CB); // Call sites might be dead if they do not have side effects and no live // users. The return value might be dead if there are no live users. - getOrCreateAAFor<AAIsDead>(CBRetPos); + getOrCreateAAFor<AAIsDead>(CBInstPos); Function *Callee = CB.getCalledFunction(); // TODO: Even if the callee is not known now we might be able to simplify |