[basicaa] Recurse through a single phi input

[reames]

Summary

BasicAA knows how to analyze phis, but to control compile time, we're fairly limited in doing so. This patch looses that restriction when there is exactly one phi input (after discounting induction variable increments). The result of this is that we can handle more cases around nested and sibling loops with pointer induction variables.

A few points to note.

1. I could be even more restrictive here and restrict this to exactly one incoming value. (Right now, I allow one phi, and an arbitrary number of other values.) I don't have a strong preference here, reviewer comments welcome.

2. As seen in the test file, we're still missing cases which aren't *directly* based on phis (e.g. using the indvar increment). I believe this to be a separate problem and am going to explore this in another patch once this one lands.

3. As seen in the test file, this results in the unfortunate fact that using phivalues sometimes results in worse quality results. I believe this comes down to an oversight in how recursive phi detection was implemented for phivalues. I'm happy to tackle this in a follow up change.

[nikic]

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

Worth noting that D92401 handles the PhiValues case, as well as @sibling_loop, but that's another change that has pathological compile-time cases.

[reames]

Update to most restrictive form.

[reames]

In D97401#2585880, @nikic wrote:

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

I understand your hesitancy here, but let me explain why I think this should go forward regardless. Specifically, with the most restricted form of the patch as updated.

1. With the updated patch, we specifically only continue analysis when there's a single phi value being recursed on. Given that, this patch definitely can not create an exponential number of queries. It can still expose potential exponential that already exist by reaching deeper into the graph, but that's a separate issue.

2. This is a really critical case. Specifically, it's the case of a pointer induction variable in a loop nest. It seems really embarrassing to have LLVM miss this.

3. I'm general hesitant to block on progress on fixing an exponential issue. This isn't the only one we have and it isn't the first time we've hit one. In general, different contributors will be working on different corpus, and what shows in one place doesn't in another. We certainly don't want to take changes which make a problem markedly worse on anyone's corpus, but something that is orthogonal in practice (if not in theory) seems good to move forward with.

[fhahn]

In D97401#2589132, @reames wrote:

In D97401#2585880, @nikic wrote:

I'm rather leery of relaxing this until we have a reliably complexity limit for BasicAA (D96647 or similar). From past experience, it's very easy to open up new pathological compile-time cases in BasicAA, because it walks a really thin line to avoid exponential queries in the absence of complexity cutoffs.

I understand your hesitancy here, but let me explain why I think this should go forward regardless. Specifically, with the most restricted form of the patch as updated.

1. With the updated patch, we specifically only continue analysis when there's a single phi value being recursed on. Given that, this patch definitely can not create an exponential number of queries. It can still expose potential exponential that already exist by reaching deeper into the graph, but that's a separate issue.

2. This is a really critical case. Specifically, it's the case of a pointer induction variable in a loop nest. It seems really embarrassing to have LLVM miss this.

3. I'm general hesitant to block on progress on fixing an exponential issue. This isn't the only one we have and it isn't the first time we've hit one. In general, different contributors will be working on different corpus, and what shows in one place doesn't in another. We certainly don't want to take changes which make a problem markedly worse on anyone's corpus, but something that is orthogonal in practice (if not in theory) seems good to move forward with.

This approach seems like a relatively safe extensions of the PHI handling (in terms of introducing additional queries) to me, while giving some nice improvements. I tried this with -O3 & LTO on X86 and there's positive changes in a couple of benchmarks in terms of additional noalias results, improvements to removed stores, unrolling & additional vectorization.

With respect to 3., I would be cautious of introducing new exponential issues. But as you mentioned, I don't see how this patch would introduce new exponential behavior. If it exposes existing exponential behavior, we can revert & focus on fixing the behavior.

LGTM, but it would be good to wait a bit in case @nikic has concerns with the latest version.

[nikic]

Yes, this looks like a safe extension, as we're recursing down exactly one value. I think it's okay to apply this until we can come up with a more general solution to this problem space.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

for (Value *PV1 : PhiValueSet) {
       if (CheckForRecPhi(PV1))
         continue;
       V1Srcs.push_back(PV1);
     }
   } else {
     // If we don't have PhiInfo then just look at the operands of the phi itself
     // FIXME: Remove this once we can guarantee that we have PhiInfo always
     SmallPtrSet<Value *, 4> UniqueSrc;
+    Value *OnePhi = nullptr;
     for (Value *PV1 : PN->incoming_values()) {
-      if (isa<PHINode>(PV1))
-        // If any of the source itself is a PHI, return MayAlias conservatively
-        // to avoid compile time explosion. The worst possible case is if both
-        // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
-        // and 'n' are the number of PHI sources.
+      if (isa<PHINode>(PV1)) {
+        if (OnePhi && OnePhi != PV1) {
+          // To control potential compile time explosion, we choose to be
+          // conserviate when we have more than one Phi input.  It is important
+          // that we handle the single phi case as that lets us handle LCSSA
+          // phi nodes and (combined with the recursive phi handling) simple
+          // pointer induction variable patterns.
           return MayAlias;
+        }
+        OnePhi = PV1;
+      }
 
       if (CheckForRecPhi(PV1))
         continue;
 
       if (UniqueSrc.insert(PV1).second)
         V1Srcs.push_back(PV1);
     }
+
+    if (OnePhi && UniqueSrc.size() > 1)
+      // Out of an abundance of caution, allow only the trivial lcssa and
+      // recursive phi cases.
+      return MayAlias;
   }
 
   // If V1Srcs is empty then that means that the phi has no underlying non-phi
   // value. This should only be possible in blocks unreachable from the entry
   // block, but return MayAlias just in case.
   if (V1Srcs.empty())
     return MayAlias;
 

llvm/test/Analysis/BasicAA/recphi.ll

 exit:
   ret void
 }
 
 ; CHECK-LABEL: Function: nested_loop3
 ; CHECK: NoAlias: i8* %a, i8* %p.base
 ; CHECK: NoAlias: i8* %a, i8* %p.outer
 ; CHECK: NoAlias: i8* %a, i8* %p.outer.next
-; CHECK: MayAlias:  i8* %a, i8* %p.inner
+; NO-PHI-VALUES: NoAlias: i8* %a, i8* %p.inner
+; PHI-VALUES: MayAlias: i8* %a, i8* %p.inner
 ; CHECK: NoAlias: i8* %a, i8* %p.inner.next
-; TODO: %p.inner does not alias %a
 define void @nested_loop3(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %outer_loop
 
 outer_loop:
   %p.outer = phi i8* [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]
   %p.outer.next = getelementptr inbounds i8, i8* %p.outer, i64 10

 exit:
   ret void
 }
 
 ; CHECK-LABEL: Function: sibling_loop2
 ; CHECK: NoAlias: i8* %a, i8* %p.base
 ; CHECK: NoAlias: i8* %a, i8* %p1
 ; CHECK: NoAlias: i8* %a, i8* %p1.next
-; CHECK: MayAlias:  i8* %a, i8* %p2
+; NO-PHI-VALUES: NoAlias: i8* %a, i8* %p2
+; PHI-VALUES: MayAlias: i8* %a, i8* %p2
 ; CHECK: NoAlias: i8* %a, i8* %p2.next
-; TODO: %p2 does not alias %a
 define void @sibling_loop2(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %loop1
 
 loop1:
   %p1 = phi i8* [ %p.base, %entry ], [ %p1.next, %loop1 ]
   %p1.next = getelementptr inbounds i8, i8* %p1, i64 10