[docs][NewPM] Add more info on why accessing mutable outer analyses is disallowed

[aeubanks]

update

[aeubanks]

update

[rnk]

lgtm

Thanks for expanding our docs!

llvm/docs/NewPassManager.rst

327–328

I would skip the second alternative. Leaving pointers to freed data as cache keys is unsafe at any speed. The only two solutions that work are to not use the inner analysis, or to clear the results for a function before it is deleted.

Personally, I like to call this problem "the ABA problem", but Wikipedia says that has to do with concurrency, not cache keys.

[asbirlea]

Thank you for adding this information!!

llvm/docs/NewPassManager.rst

 call
 
 .. code-block:: c++
 
   const auto &MAMProxy =
       AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
   FooAnalysisResult *AR = MAMProxy.getCachedResult<FooAnalysis>(M);
 
-Getting direct access to an outer level IR analysis manager is not allowed.
-This is to keep in mind potential future pass concurrency, for example
-parallelizing function passes over different functions in a CGSCC or module.
-Since passes can ask for a cached analysis result, allowing passes to trigger
-outer level analysis computation could result in non-determinism if
+Asking for a cached and immutable outer level IR analysis is fine, but getting
+direct access to an outer level IR analysis manager to compute an outer level IR
+analysis is not allowed. This is for a couple reasons.
+
+The first reason is that running analyses across outer level IR in inner level
+IR passes can result in quadratic behavior. For example, a module analysis may
+scan every function and allowing function passes to run a module analysis may
+cause us to scan functions a quadratic number of times. If passes could keep
+outer level analyses up to date rather than computing them on demand this
+wouldn't be an issue, but so far this hasn't been necessary and there isn't
+infrastructure for this (aside from function analyses in loop passes as
+described below). Self-updating analyses that gracefully degrade also handle
+this problem (e.g. GlobalsAA), but they run into the issue of having to be
+manually recomputed somewhere in the optimization pipeline if we want precision,
+and they block potential future concurrency.
+
+The second reason is to keep in mind potential future pass concurrency, for
+example parallelizing function passes over different functions in a CGSCC or
+module. 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. Outer analyses unused by inner
-passes can and often will be invalidated by changes to inner level IR. These
-invalidations happen after the inner pass manager finishes, so accessing
-mutable analyses would give invalid results.
-
-The exception to the above is accessing function analyses in loop passes.
-Loop passes inherently require modifying the function the loop is in, and
-that includes some function analyses the loop analyses depend on. This
-discounts future concurrency over separate loops in a function, but that's a
-tradeoff due to how tightly a loop and its function are coupled. To make sure
-the function analyses loop passes use are valid, they are manually updated in
-the loop passes to ensure that invalidation is not necessary. There is a set
-of common function analyses that loop passes and analyses have access to
-which is passed into loop passes as a ``LoopStandardAnalysisResults``
-parameter. Other function analyses are not accessible from loop passes.
+invalidated by changes to inner level IR. Outer analyses unused by inner passes
+can and often will be invalidated by changes to inner level IR. These
+invalidations happen after the inner pass manager finishes, so accessing mutable
+analyses would give invalid results.
+
+The exception to not being able to access outer level analyses is accessing
+function analyses in loop passes. Loop passes often use function analyses such
+as the dominator tree. Loop passes inherently require modifying the function the
+loop is in, and that includes some function analyses the loop analyses depend
+on. This discounts future concurrency over separate loops in a function, but
+that's a tradeoff due to how tightly a loop and its function are coupled. To
+make sure the function analyses loop passes use are valid, they are manually
+updated in the loop passes to ensure that invalidation is not necessary. There
+is a set of common function analyses that loop passes and analyses have access
+to which is passed into loop passes as a ``LoopStandardAnalysisResults``
+parameter. Other mutable function analyses are not accessible from loop passes.
 
 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

 with the pass's returned ``PreservedAnalyses``. This can be also done
 manually within the pass:
 
 .. code-block:: c++
 
   FooModulePass::run(Module& M, ModuleAnalysisManager& AM) {
     auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 
-    // Invalidate all analysis results for function F
-    FAM.invalidate(F, PreservedAnalyses::none());
+    // Invalidate all analysis results for function F1.
+    FAM.invalidate(F1, PreservedAnalyses::none());
 
-    // Invalidate all analysis results
+    // Invalidate all analysis results across the entire module.
     AM.invalidate(M, PreservedAnalyses::none());
 
+    // Clear the entry in the analysis manager for function F2 if we've completely removed it from the module.
+    FAM.clear(F2);
+
     ...
   }
 
-This is especially important when a pass removes then adds a function. The
-analysis manager may store a pointer to a function that has been deleted, and
-if the pass creates a new function before invalidating analysis results, the
-new function may be at the same address as the old one, causing invalid
-cached results. This is also useful for being more precise about
-invalidation. Selectively invalidating analysis results only for functions
-modified in an SCC pass can allow more analysis results to remain. But except
-for complex fine-grain invalidation with inner proxies, passes should
-typically just return a proper ``PreservedAnalyses`` and let the pass manager
-deal with proper invalidation.
+Clearing results for deleted IR is especially important. The analysis manager
+may store a pointer to a function that has been deleted, and if the pass creates
+a new function before invalidating analysis results, the new function may be at
+the same address as the old one, causing invalid cached results. But if an inner
+analysis manager proxy is invalidated via a typical ``return
+PreservedAnalyses::none();``, it will automatically clear all of its cached
+analyses.
+
+Manually invalidating analysis results e.g. only invalidating analyses for
+functions modified in an SCC pass, can allow more analysis results to not be
+invalidated, potentially helping with compile times. But except for fine-grain
+invalidation with inner proxies, passes should typically just return a proper
+``PreservedAnalyses`` and let the pass manager deal with proper invalidation.
 
 Implementing Analysis Invalidation
 ==================================
 
 By default, an analysis is invalidated if ``PreservedAnalyses`` says that
 analyses on the IR unit it runs on are not preserved (see
 ``AnalysisResultModel::invalidate()``). An analysis can implement
 ``invalidate()`` to be more conservative when it comes to invalidation. For