[BasicAA] Fix BatchAA results for phi-phi assumptions
authorNikita Popov <nikita.ppv@gmail.com>
Sun, 22 Nov 2020 17:23:53 +0000 (18:23 +0100)
committerNikita Popov <nikita.ppv@gmail.com>
Wed, 6 Jan 2021 21:15:30 +0000 (22:15 +0100)
commitf6f6f6375d1a4bced8a6e79a78726ab32b8dd879
treec6bfae3da01c535024c19ce9051bfac66aed839e
parent0e874fc014be818a9c6782729f2c8e8273a7a906
[BasicAA] Fix BatchAA results for phi-phi assumptions

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 significantly
higher than the previous iteration of this patch:
https://llvm-compile-time-tracker.com/compare.php?from=c0bb9859de6991cc233e2dedb978dd118da8c382&to=c07112373279143e37568b5bcd293daf81a35973&stat=instructions
However, it should avoid the exponential runtime cases we run into
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 both more complicated and more expensive than I hoped,
but I wasn't able to come up with another solution that satisfies all
the constraints.

Differential Revision: https://reviews.llvm.org/D91936
llvm/include/llvm/Analysis/AliasAnalysis.h
llvm/include/llvm/Analysis/BasicAliasAnalysis.h
llvm/lib/Analysis/BasicAliasAnalysis.cpp
llvm/test/Analysis/BasicAA/phi-speculation.ll
llvm/unittests/Analysis/AliasAnalysisTest.cpp