LoopAnalysisManager.cpp revision 314564
1//===- LoopAnalysisManager.cpp - Loop analysis management -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "llvm/Analysis/LoopAnalysisManager.h" 11#include "llvm/Analysis/BasicAliasAnalysis.h" 12#include "llvm/Analysis/GlobalsModRef.h" 13#include "llvm/Analysis/LoopInfo.h" 14#include "llvm/Analysis/ScalarEvolution.h" 15#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 16#include "llvm/IR/Dominators.h" 17 18using namespace llvm; 19 20// Explicit template instantiations and specialization defininitions for core 21// template typedefs. 22namespace llvm { 23template class AllAnalysesOn<Loop>; 24template class AnalysisManager<Loop, LoopStandardAnalysisResults &>; 25template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>; 26template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop, 27 LoopStandardAnalysisResults &>; 28 29bool 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 in reverse. 35 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist; 36 // Note that we want to walk the roots in reverse order because we will end 37 // up reversing the preorder sequence. However, it happens that the loop nest 38 // roots are in reverse order within the LoopInfo object. So we just walk 39 // forward here. 40 // FIXME: If we change the order of LoopInfo we will want to add a reverse 41 // here. 42 for (Loop *RootL : *LI) { 43 assert(PreOrderWorklist.empty() && 44 "Must start with an empty preorder walk worklist."); 45 PreOrderWorklist.push_back(RootL); 46 do { 47 Loop *L = PreOrderWorklist.pop_back_val(); 48 PreOrderWorklist.append(L->begin(), L->end()); 49 PreOrderLoops.push_back(L); 50 } while (!PreOrderWorklist.empty()); 51 } 52 53 // If this proxy or the loop info is going to be invalidated, we also need 54 // to clear all the keys coming from that analysis. We also completely blow 55 // away the loop analyses if any of the standard analyses provided by the 56 // loop pass manager go away so that loop analyses can freely use these 57 // without worrying about declaring dependencies on them etc. 58 // FIXME: It isn't clear if this is the right tradeoff. We could instead make 59 // loop analyses declare any dependencies on these and use the more general 60 // invalidation logic below to act on that. 61 auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>(); 62 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) || 63 Inv.invalidate<AAManager>(F, PA) || 64 Inv.invalidate<AssumptionAnalysis>(F, PA) || 65 Inv.invalidate<DominatorTreeAnalysis>(F, PA) || 66 Inv.invalidate<LoopAnalysis>(F, PA) || 67 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA)) { 68 // Note that the LoopInfo may be stale at this point, however the loop 69 // objects themselves remain the only viable keys that could be in the 70 // analysis manager's cache. So we just walk the keys and forcibly clear 71 // those results. Note that the order doesn't matter here as this will just 72 // directly destroy the results without calling methods on them. 73 for (Loop *L : PreOrderLoops) 74 InnerAM->clear(*L); 75 76 // We also need to null out the inner AM so that when the object gets 77 // destroyed as invalid we don't try to clear the inner AM again. At that 78 // point we won't be able to reliably walk the loops for this function and 79 // only clear results associated with those loops the way we do here. 80 // FIXME: Making InnerAM null at this point isn't very nice. Most analyses 81 // try to remain valid during invalidation. Maybe we should add an 82 // `IsClean` flag? 83 InnerAM = nullptr; 84 85 // Now return true to indicate this *is* invalid and a fresh proxy result 86 // needs to be built. This is especially important given the null InnerAM. 87 return true; 88 } 89 90 // Directly check if the relevant set is preserved so we can short circuit 91 // invalidating loops. 92 bool AreLoopAnalysesPreserved = 93 PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>(); 94 95 // Since we have a valid LoopInfo we can actually leave the cached results in 96 // the analysis manager associated with the Loop keys, but we need to 97 // propagate any necessary invalidation logic into them. We'd like to 98 // invalidate things in roughly the same order as they were put into the 99 // cache and so we walk the preorder list in reverse to form a valid 100 // postorder. 101 for (Loop *L : reverse(PreOrderLoops)) { 102 Optional<PreservedAnalyses> InnerPA; 103 104 // Check to see whether the preserved set needs to be adjusted based on 105 // function-level analysis invalidation triggering deferred invalidation 106 // for this loop. 107 if (auto *OuterProxy = 108 InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L)) 109 for (const auto &OuterInvalidationPair : 110 OuterProxy->getOuterInvalidations()) { 111 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; 112 const auto &InnerAnalysisIDs = OuterInvalidationPair.second; 113 if (Inv.invalidate(OuterAnalysisID, F, PA)) { 114 if (!InnerPA) 115 InnerPA = PA; 116 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) 117 InnerPA->abandon(InnerAnalysisID); 118 } 119 } 120 121 // Check if we needed a custom PA set. If so we'll need to run the inner 122 // invalidation. 123 if (InnerPA) { 124 InnerAM->invalidate(*L, *InnerPA); 125 continue; 126 } 127 128 // Otherwise we only need to do invalidation if the original PA set didn't 129 // preserve all Loop analyses. 130 if (!AreLoopAnalysesPreserved) 131 InnerAM->invalidate(*L, PA); 132 } 133 134 // Return false to indicate that this result is still a valid proxy. 135 return false; 136} 137 138template <> 139LoopAnalysisManagerFunctionProxy::Result 140LoopAnalysisManagerFunctionProxy::run(Function &F, 141 FunctionAnalysisManager &AM) { 142 return Result(*InnerAM, AM.getResult<LoopAnalysis>(F)); 143} 144} 145 146PreservedAnalyses llvm::getLoopPassPreservedAnalyses() { 147 PreservedAnalyses PA; 148 PA.preserve<AssumptionAnalysis>(); 149 PA.preserve<DominatorTreeAnalysis>(); 150 PA.preserve<LoopAnalysis>(); 151 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 152 PA.preserve<ScalarEvolutionAnalysis>(); 153 // TODO: What we really want to do here is preserve an AA category, but that 154 // concept doesn't exist yet. 155 PA.preserve<AAManager>(); 156 PA.preserve<BasicAA>(); 157 PA.preserve<GlobalsAA>(); 158 PA.preserve<SCEVAA>(); 159 return PA; 160} 161