diff --git a/llvm/docs/NewPassManager.rst b/llvm/docs/NewPassManager.rst --- a/llvm/docs/NewPassManager.rst +++ b/llvm/docs/NewPassManager.rst @@ -140,6 +140,157 @@ ``AMDGPUTargetMachine::registerPassBuilderCallbacks()`` is an example of a backend adding passes to various parts of the pipeline. +Analyses +======== + +LLVM provides many analyses that passes can use, such as a dominator tree. +Calculating these can be expensive, so the new pass manager has +infrastructure to cache analyses and reuse them when possible. + +When a pass runs on some IR, it also receives an analysis manager which it +can query for analyses. Querying for an analysis will cause the manager to +check if it has already computed the result for the requested IR. If it does +and the result is still valid, it will return that. Otherwise it will +construct a new result by calling the analysis's ``run()`` method, cache it, +and return it. You can also ask the analysis manager to only return an +analysis if it's already cached. + +The analysis manager only provides analysis results for the same IR type as +what the pass runs on. For example, a function pass receives an analysis +manager that only provides function-level analyses. This works for many +passes which work on a fixed scope. However, some passes want to peer up or +down the IR hierarchy. For example, an SCC pass may want to look at function +analyses for the functions inside the SCC. Or it may want to look at some +immutable global analysis. In these cases, the analysis manager can provide a +proxy to a outer or inner level analysis manager. For example, to get a +``FunctionAnalysisManager`` from a ``CGSCCAnalysisManager``, you can call + +.. code-block:: c++ + + FunctionAnalysisManager &FAM = + AM.getResult(InitialC, CG) + .getManager(); + +and use ``FAM`` as a typical ``FunctionAnalysisManager`` that a function pass +would have access to. To get access to an outer level IR analysis, you can +call + +.. code-block:: c++ + + const auto &MAMProxy = + AM.getResult(InitialC, CG); + FooAnalysisResult *AR = MAMProxy.getCachedResult(M); + +Getting direct access to an outer level IR analysis manager is not allowed. +This is to keep in mind potential future pass concurrency. Since passes can +ask for a cached analysis result, allowing passes to trigger outer level +analysis computation could result in non-determinism if concurrency was +supported. Therefore a pass running on inner level IR cannot change the state +of outer level IR analyses. Another limitation is that outer level IR +analyses that are used must be immutable, or else they could be invalidated +by changes to inner level IR. + +As with any caching mechanism, we need some way to tell analysis managers +when results are no longer valid. Much of the analysis manager complexity +comes from trying to invalidate as few analysis results as possible to keep +compile times as low as possible. + +There are two ways to deal with potentially invalid analysis results. One is +to simply force clear the results. This should generally only be used when +the IR that the result is keyed on becomes invalid. For example, a function +is deleted, or a CGSCC has become invalid due to call graph changes. + +The typical way to invalidate analysis results is for a pass to declare what +types of analyses it preserves and what types it does not. When transforming +IR, a pass either has the option to update analyses alongside the IR +transformation, or tell the analysis manager that analyses are no longer +valid and should be invalidated. If a pass wants to keep some specific +analysis up to date, such as when updating it would be faster than +invalidating and recalculating it, the analysis itself may have methods to +update it for specific transformations, or there may be helper updaters like +``DomTreeUpdater`` for a ``DominatorTree``. Otherwise to mark some analysis +as no longer valid, the pass can return a ``PreservedAnalyses`` with the +proper analyses invalidated. + +.. code-block:: c++ + + // We've made no transformations that can affect any analyses. + return PreservedAnalyses::all(); + + // We've made transformations don't want to bother to update any analyses. + return PreservedAnalyses::none(); + + // We've specifically updated the dominator tree alongside any transformations, but other analysis results may be invalid. + PreservedAnalyses PA; + PA.preserve(); + return PA; + + // We haven't made any control flow changes, any analyses that only care about the control flow are still valid. + PreservedAnalyses PA; + PA.preserveSet(); + return PA; + +The pass manager will call the analysis manager's ``invalidate()`` method +with the pass's returned ``PreservedAnalyses``. (This can be also done +manually within the pass.) The analysis manager then calls ``invalidate()`` +on all of its cached analysis results to query if the analysis should be +invalidated based on the ``PreservedAnalyses``. + +An analysis should implement ``invalidate()`` like below, at least for simple +cases: + +.. code-block:: c++ + + bool FooAnalysisResult::invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &) { + auto PAC = PA.getChecker(); + return !(PAC.preserved() || PAC.preservedSet>()); + } + +This says that if the ``PreservedAnalyses`` specifically preserves +``FooAnalysis``, or if ``PreservedAnalyses`` preserves all analyses (implicit +in ``PAC.preserved()``), or if ``PreservedAnalyses`` preserves all function +analyses, the ``FooAnalysisResult`` should not be invalidated. There are +other sets like ``PAC.preservedSet()`` for analyses that are +preserved if no control flow within a function has been changed. + +If an analysis depends on other analyses, those analyses also need to be +checked if they are invalidated: + +.. code-block:: c++ + + bool FooAnalysisResult::invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &) { + auto PAC = PA.getChecker(); + if (!PAC.preserved() && !PAC.preservedSet>()) + return true; + + // Check transitive dependencies. + return Inv.invalidate(F, PA) || + Inv.invalidate(F, PA); + } + +Combining invalidation and analysis manager proxies results in some +complexity. For example, when we invalidating all analyses in a module pass, +we have to make sure that we also invalidate function analyses accessible via +any existing inner proxies. The inner proxy's ``invalidate()`` first checks +if the proxy itself should be invalidated. If so, that means the proxy may +contain pointers to IR that is no longer valid, meaning that the inner proxy +needs to completely clear all relevant analysis results. Otherwise the proxy +simply forwards the invalidation to the inner analysis manager. + +Generally for outer proxies, analysis results from the outer analysis manager +should be immutable, so invalidation shouldn't be a concern. However, it is +possible for some inner analysis to depend on some outer analysis, and when +the outer analysis is invalidated, we need to make sure that dependent inner +analyses are also invalidated. This actually happens with alias analysis +results. Alias analysis is a function-level analysis, but there are +module-level implementations of specific types of alias analysis. Currently +``GlobalsAA`` is the only module-level alias analysis and it generally is not +invalidated so this is not so much of a concern. See +``OuterAnalysisManagerProxy::Result::registerOuterAnalysisInvalidation()`` +for more details. + Status of the New and Legacy Pass Managers ==========================================