[BasicAA] Handle PHIs without incoming values gracefully

[DaniilSuchkov]

Summary

This change fixes a bug introduced by

commit f6f6f6375d1a4bced8a6e79a78726ab32b8dd879
Author: Nikita Popov <[e-mail]>
Date:   Sun Nov 22 18:23:53 2020 +0100

    [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

Now for empty PHIs, instead of crashing on assert(hasVal()) in Optional's internals, we'll return NoAlias, as we did before that patch.

[nikic]

LGTM. I was going to suggest that you add a direct AA test, but apparently there is no way to write an empty phi in textual LLVM IR, at least not that I can see. Weird limitation.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize,
   return MergeAliasResults(ThisAlias, Alias);
 }
 
 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
 /// another.
 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
                                     const Value *V2, LocationSize V2Size,
                                     AAQueryInfo &AAQI) {
+  if (!PN->getNumIncomingValues())
+    return AliasResult::NoAlias;
   // If the values are PHIs in the same block, we can do a more precise
   // as well as efficient check: just check for aliases between the values
   // on corresponding edges.
   if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
     if (PN2->getParent() == PN->getParent()) {
       Optional<AliasResult> Alias;
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         AliasResult ThisAlias = getBestAAResults().alias(

llvm/test/Transforms/JumpThreading/aa-crash-phi-no-args.ll

-; XFAIL: *
 ; REQUIRES: asserts
 ; RUN: opt -jump-threading -aa-pipeline basic-aa -S -disable-output %s
 ; RUN: opt -passes=jump-threading -aa-pipeline basic-aa -S -disable-output %s
 
 define void @foo(i8** %arg1, i32* %arg2) {
 bb:
   br label %bb1