[ValueTracking] Don't let isAddOfNonZero look at adds with a PHI node as input

[craig.topper]

Summary

This is a fix for the test case in PR32314.

Basic Alias Analysis can ask if two nodes are known non-equal after looking through a phi node to find a GEP. isAddOfNonZero saw an add of a constant from the same phi and said that its output couldn't be equal. But Basic Alias Analysis was really asking about the value from the previous loop iteration.

This patch at least makes that case not happen anymore, I'm not sure if there were still other ways this can fail. As was discussed in the bug, it looks like fixing BasicAA would be difficult so this patch seemed like a possible workaround

[hfinkel]

Can we add a mode (e.g. some extra boolean parameter) to ValueTracking to enable this kind of restriction? We could then enable this mode when in BasicAA. I don't want to, in general, disable things here to work around the fact that BasicAA is doing some unsound.

[craig.topper]

I couldn't come up with a bool variable name that I liked so I just taught BasicAA not to call isKnownNonEqual if one of the inputs is a PHI. Instead we'll just compute the known bits separately. I think we should add a helper method to KnownBits to check if two KnownBits structs are known non equal which would simplify the intersection check.

[Farhana]

What is the performance implication of this change-set? Have you done any performance testing? This seems to make the alias analysis very conservative. It is now going to find two non-equal numbers equal very easily.

[craig.topper]

Only one of the benchmarks I ran this through showed any effect on the compiled code. And the one benchmark that changed got slightly faster.

[craig.topper]

Ping

[• dberlin]

In D33136#773589, @Farhana wrote:

What is the performance implication of this change-set? Have you done any performance testing? This seems to make the alias analysis very conservative. It is now going to find two non-equal numbers equal very easily.

Other than rewrite it all, what are you suggesting he do?

[• dberlin]

I'm fine with this.
If we want better performance or better aliasing, we can do the hard work of doing it right.

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

if (isa<SequentialType>(Ty)) {
     // Because they cannot partially overlap and because fields in an array
     // cannot overlap, if we can prove the final indices are different between
     // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
     
     // If the last indices are constants, we've already checked they don't
     // equal each other so we can exit early.
     if (C1 && C2)
       return NoAlias;
-    if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
-                        GEP2->getOperand(GEP2->getNumOperands() - 1),
-                        DL))
+    {
+      Value *GEP1LastIdx = GEP1->getOperand(GEP1->getNumOperands() - 1);
+      Value *GEP2LastIdx = GEP2->getOperand(GEP2->getNumOperands() - 1);
+      if (isa<PHINode>(GEP1LastIdx) || isa<PHINode>(GEP2LastIdx)) {
+        // If one of the indices is a PHI node, be safe and only use
+        // computeKnownBits so we don't make any assumptions about the
+        // relationships between the two indices. This is important if we're
+        // asking about values from different loop iterations. See PR32314.
+        // TODO: We may be able to change the check so we only do this when
+        // we definitely looked through a PHINode.
+        KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
+        KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
+        if (Known1.Zero.intersects(Known2.One) ||
+            Known1.One.intersects(Known2.Zero))
           return NoAlias;
+      } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
+        return NoAlias;
+    }
     return MayAlias;
   } else if (!LastIndexedStruct || !C1 || !C2) {
     return MayAlias;
   }
 
   // We know that:
   // - both GEPs begin indexing from the exact same pointer;
   // - the last indices in both GEPs are constants, indexing into a struct;