149 lines · cpp
1//===- LoopAnalysisManager.cpp - Loop analysis management -----------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/LoopAnalysisManager.h"10#include "llvm/Analysis/AssumptionCache.h"11#include "llvm/Analysis/LoopInfo.h"12#include "llvm/Analysis/MemorySSA.h"13#include "llvm/Analysis/ScalarEvolution.h"14#include "llvm/IR/Dominators.h"15#include "llvm/IR/PassManagerImpl.h"16#include "llvm/Support/Compiler.h"17#include <optional>18 19using namespace llvm;20 21namespace llvm {22// Explicit template instantiations and specialization definitions for core23// template typedefs.24template class LLVM_EXPORT_TEMPLATE AllAnalysesOn<Loop>;25template class LLVM_EXPORT_TEMPLATE26 AnalysisManager<Loop, LoopStandardAnalysisResults &>;27template class LLVM_EXPORT_TEMPLATE28 InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;29template class LLVM_EXPORT_TEMPLATE OuterAnalysisManagerProxy<30 FunctionAnalysisManager, Loop, LoopStandardAnalysisResults &>;31 32bool LoopAnalysisManagerFunctionProxy::Result::invalidate(33 Function &F, const PreservedAnalyses &PA,34 FunctionAnalysisManager::Invalidator &Inv) {35 // First compute the sequence of IR units covered by this proxy. We will want36 // to visit this in postorder, but because this is a tree structure we can do37 // this by building a preorder sequence and walking it backwards. We also38 // want siblings in forward program order to match the LoopPassManager so we39 // get the preorder with siblings reversed.40 SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder();41 42 // If this proxy or the loop info is going to be invalidated, we also need43 // to clear all the keys coming from that analysis. We also completely blow44 // away the loop analyses if any of the standard analyses provided by the45 // loop pass manager go away so that loop analyses can freely use these46 // without worrying about declaring dependencies on them etc.47 // FIXME: It isn't clear if this is the right tradeoff. We could instead make48 // loop analyses declare any dependencies on these and use the more general49 // invalidation logic below to act on that.50 auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>();51 bool invalidateMemorySSAAnalysis = false;52 if (MSSAUsed)53 invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);54 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||55 Inv.invalidate<AAManager>(F, PA) ||56 Inv.invalidate<AssumptionAnalysis>(F, PA) ||57 Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||58 Inv.invalidate<LoopAnalysis>(F, PA) ||59 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||60 invalidateMemorySSAAnalysis) {61 // Note that the LoopInfo may be stale at this point, however the loop62 // objects themselves remain the only viable keys that could be in the63 // analysis manager's cache. So we just walk the keys and forcibly clear64 // those results. Note that the order doesn't matter here as this will just65 // directly destroy the results without calling methods on them.66 for (Loop *L : PreOrderLoops) {67 // NB! `L` may not be in a good enough state to run Loop::getName.68 InnerAM->clear(*L, "<possibly invalidated loop>");69 }70 71 // We also need to null out the inner AM so that when the object gets72 // destroyed as invalid we don't try to clear the inner AM again. At that73 // point we won't be able to reliably walk the loops for this function and74 // only clear results associated with those loops the way we do here.75 // FIXME: Making InnerAM null at this point isn't very nice. Most analyses76 // try to remain valid during invalidation. Maybe we should add an77 // `IsClean` flag?78 InnerAM = nullptr;79 80 // Now return true to indicate this *is* invalid and a fresh proxy result81 // needs to be built. This is especially important given the null InnerAM.82 return true;83 }84 85 // Directly check if the relevant set is preserved so we can short circuit86 // invalidating loops.87 bool AreLoopAnalysesPreserved =88 PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>();89 90 // Since we have a valid LoopInfo we can actually leave the cached results in91 // the analysis manager associated with the Loop keys, but we need to92 // propagate any necessary invalidation logic into them. We'd like to93 // invalidate things in roughly the same order as they were put into the94 // cache and so we walk the preorder list in reverse to form a valid95 // postorder.96 for (Loop *L : reverse(PreOrderLoops)) {97 std::optional<PreservedAnalyses> InnerPA;98 99 // Check to see whether the preserved set needs to be adjusted based on100 // function-level analysis invalidation triggering deferred invalidation101 // for this loop.102 if (auto *OuterProxy =103 InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))104 for (const auto &OuterInvalidationPair :105 OuterProxy->getOuterInvalidations()) {106 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;107 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;108 if (Inv.invalidate(OuterAnalysisID, F, PA)) {109 if (!InnerPA)110 InnerPA = PA;111 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)112 InnerPA->abandon(InnerAnalysisID);113 }114 }115 116 // Check if we needed a custom PA set. If so we'll need to run the inner117 // invalidation.118 if (InnerPA) {119 InnerAM->invalidate(*L, *InnerPA);120 continue;121 }122 123 // Otherwise we only need to do invalidation if the original PA set didn't124 // preserve all Loop analyses.125 if (!AreLoopAnalysesPreserved)126 InnerAM->invalidate(*L, PA);127 }128 129 // Return false to indicate that this result is still a valid proxy.130 return false;131}132 133template <>134LoopAnalysisManagerFunctionProxy::Result135LoopAnalysisManagerFunctionProxy::run(Function &F,136 FunctionAnalysisManager &AM) {137 return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));138}139} // namespace llvm140 141PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {142 PreservedAnalyses PA;143 PA.preserve<DominatorTreeAnalysis>();144 PA.preserve<LoopAnalysis>();145 PA.preserve<LoopAnalysisManagerFunctionProxy>();146 PA.preserve<ScalarEvolutionAnalysis>();147 return PA;148}149