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-exception 6 // 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 <optional> 17 18 using namespace llvm; 19 20 namespace llvm { 21 // Explicit template instantiations and specialization definitions for core 22 // template typedefs. 23 template class AllAnalysesOn<Loop>; 24 template class AnalysisManager<Loop, LoopStandardAnalysisResults &>; 25 template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>; 26 template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop, 27 LoopStandardAnalysisResults &>; 28 29 bool LoopAnalysisManagerFunctionProxy::Result::invalidate( 30 Function &F, const PreservedAnalyses &PA, 31 FunctionAnalysisManager::Invalidator &Inv) { 32 // First compute the sequence of IR units covered by this proxy. We will want 33 // to visit this in postorder, but because this is a tree structure we can do 34 // this by building a preorder sequence and walking it backwards. We also 35 // want siblings in forward program order to match the LoopPassManager so we 36 // get the preorder with siblings reversed. 37 SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder(); 38 39 // If this proxy or the loop info is going to be invalidated, we also need 40 // to clear all the keys coming from that analysis. We also completely blow 41 // away the loop analyses if any of the standard analyses provided by the 42 // loop pass manager go away so that loop analyses can freely use these 43 // without worrying about declaring dependencies on them etc. 44 // FIXME: It isn't clear if this is the right tradeoff. We could instead make 45 // loop analyses declare any dependencies on these and use the more general 46 // invalidation logic below to act on that. 47 auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>(); 48 bool invalidateMemorySSAAnalysis = false; 49 if (MSSAUsed) 50 invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA); 51 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) || 52 Inv.invalidate<AAManager>(F, PA) || 53 Inv.invalidate<AssumptionAnalysis>(F, PA) || 54 Inv.invalidate<DominatorTreeAnalysis>(F, PA) || 55 Inv.invalidate<LoopAnalysis>(F, PA) || 56 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) || 57 invalidateMemorySSAAnalysis) { 58 // Note that the LoopInfo may be stale at this point, however the loop 59 // objects themselves remain the only viable keys that could be in the 60 // analysis manager's cache. So we just walk the keys and forcibly clear 61 // those results. Note that the order doesn't matter here as this will just 62 // directly destroy the results without calling methods on them. 63 for (Loop *L : PreOrderLoops) { 64 // NB! `L` may not be in a good enough state to run Loop::getName. 65 InnerAM->clear(*L, "<possibly invalidated loop>"); 66 } 67 68 // We also need to null out the inner AM so that when the object gets 69 // destroyed as invalid we don't try to clear the inner AM again. At that 70 // point we won't be able to reliably walk the loops for this function and 71 // only clear results associated with those loops the way we do here. 72 // FIXME: Making InnerAM null at this point isn't very nice. Most analyses 73 // try to remain valid during invalidation. Maybe we should add an 74 // `IsClean` flag? 75 InnerAM = nullptr; 76 77 // Now return true to indicate this *is* invalid and a fresh proxy result 78 // needs to be built. This is especially important given the null InnerAM. 79 return true; 80 } 81 82 // Directly check if the relevant set is preserved so we can short circuit 83 // invalidating loops. 84 bool AreLoopAnalysesPreserved = 85 PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>(); 86 87 // Since we have a valid LoopInfo we can actually leave the cached results in 88 // the analysis manager associated with the Loop keys, but we need to 89 // propagate any necessary invalidation logic into them. We'd like to 90 // invalidate things in roughly the same order as they were put into the 91 // cache and so we walk the preorder list in reverse to form a valid 92 // postorder. 93 for (Loop *L : reverse(PreOrderLoops)) { 94 std::optional<PreservedAnalyses> InnerPA; 95 96 // Check to see whether the preserved set needs to be adjusted based on 97 // function-level analysis invalidation triggering deferred invalidation 98 // for this loop. 99 if (auto *OuterProxy = 100 InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L)) 101 for (const auto &OuterInvalidationPair : 102 OuterProxy->getOuterInvalidations()) { 103 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; 104 const auto &InnerAnalysisIDs = OuterInvalidationPair.second; 105 if (Inv.invalidate(OuterAnalysisID, F, PA)) { 106 if (!InnerPA) 107 InnerPA = PA; 108 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) 109 InnerPA->abandon(InnerAnalysisID); 110 } 111 } 112 113 // Check if we needed a custom PA set. If so we'll need to run the inner 114 // invalidation. 115 if (InnerPA) { 116 InnerAM->invalidate(*L, *InnerPA); 117 continue; 118 } 119 120 // Otherwise we only need to do invalidation if the original PA set didn't 121 // preserve all Loop analyses. 122 if (!AreLoopAnalysesPreserved) 123 InnerAM->invalidate(*L, PA); 124 } 125 126 // Return false to indicate that this result is still a valid proxy. 127 return false; 128 } 129 130 template <> 131 LoopAnalysisManagerFunctionProxy::Result 132 LoopAnalysisManagerFunctionProxy::run(Function &F, 133 FunctionAnalysisManager &AM) { 134 return Result(*InnerAM, AM.getResult<LoopAnalysis>(F)); 135 } 136 } 137 138 PreservedAnalyses llvm::getLoopPassPreservedAnalyses() { 139 PreservedAnalyses PA; 140 PA.preserve<DominatorTreeAnalysis>(); 141 PA.preserve<LoopAnalysis>(); 142 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 143 PA.preserve<ScalarEvolutionAnalysis>(); 144 return PA; 145 } 146