Change the way NoAlias assumptions in BasicAA are handled. Instead of handling this inside the phi-phi code, always initially insert a NoAlias result into the map and keep track whether it is used. If it is used, then we require that we also get back NoAlias from the recursive queries. Otherwise, the entry is changed to MayAlias.
Additionally, keep track of all location pairs we inserted that may still be based on assumptions higher up. If it turns out one of those assumptions is incorrect, we flush them from the cache.
The compile-time impact for the new implementation is higher than before: https://llvm-compile-time-tracker.com/compare.php?from=c0bb9859de6991cc233e2dedb978dd118da8c382&to=c07112373279143e37568b5bcd293daf81a35973&stat=instructions However, it avoids exponential runtime cases we run to if we don't cache assumption-based results entirely.
This also produces better results in some cases, because NoAlias assumptions can now start at any root, rather than just phi-phi pairs. This is not just relevant for analysis quality, but also for BatchAA consistency: Otherwise, results would once again depend on query order, though at least they wouldn't be wrong.
This ended up more complicated and more expansive than I hoped, but I wasn't able to come up with another solution that satisfies all the constraints.