[BasicAA] Fix a bug with relational reasoning across iterations

[reames]

Summary

Due to the recursion through phis basicaa does, the code needs to be extremely careful not to reason about equality between values which might represent distinct iterations. I'm generally skeptical of the correctness of the whole scheme, but this particular patch fixes one particular instance which is demonstrateable incorrect.

Interestingly, this appears to be the second attempted fix for the same issue. The former fix is incomplete and doesn't address the actual issue.

[reames]

llvm/test/Analysis/BasicAA/phi-aa.ll

179

Previously, we'd (falsely) conclude that %phi noalias %arrayidx5. Since the value of %idx can vary across iterations, this is wrong.

[jdoerfert]

Looks sensible to me. Second opinion preferred though.

[nikic]

LGTM

Due diligence: I was a bit concerned about dropping the known bits fallback (which we can retain even in cycles). After adding some AA stats, I see:

               | Baseline |    Patch
aa.NumMayAlias |  4920438 |  4920375
aa.NumNoAlias  | 27075701 | 27075764

So this actually marginally improves the AA results. Presumably that's because we can now handle the case where one of the indexes is a phi, but we're not in a cycle.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
   static DecomposedGEP
   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                          AssumptionCache *AC, DominatorTree *DT);
 
   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
       LocationSize ObjectAccessSize);
 
+  AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
+                                       LocationSize MaybeV1Size,
+                                       const GEPOperator *GEP2,
+                                       LocationSize MaybeV2Size,
+                                       const DataLayout &DL);
+
   /// A Heuristic for aliasGEP that searches for a constant offset
   /// between the variables.
   ///
   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
   /// will therefore conservatively refuse to decompose these expressions.
   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
   /// the addition overflows.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

return isModSet(createModRefInfo(getModRefBehavior(Call1)))
                : ModRefInfo::NoModRef;
 
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
-static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
+AliasResult BasicAAResult::aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                                     LocationSize MaybeV1Size,
                                                     const GEPOperator *GEP2,
                                                     LocationSize MaybeV2Size,
                                                     const DataLayout &DL) {
   assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
              GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
          GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
          "Expected GEPs with the same pointer operand");
 
   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
   // such that the struct field accesses provably cannot alias.
   // We also need at least two indices (the pointer, and the struct field).
if (isa<ArrayType>(Ty) || isa<VectorType>(Ty)) {
     // 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 we're not potentially reasoning about values from different
+      // iterations, see if we can prove them inequal.
       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.
-        if (GEP1LastIdx != GEP2LastIdx &&
-            GEP1LastIdx->getType() == GEP2LastIdx->getType()) {
-          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))
+      if (VisitedPhiBBs.empty() &&
+          isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
         return NoAlias;
     }
   }
   return MayAlias;
 }
 
 // If a we have (a) a GEP and (b) a pointer based on an alloca, and the
 // beginning of the object the GEP points would have a negative offset with

llvm/test/Analysis/BasicAA/phi-aa.ll

exit:
   %p = phi i8* [ %x, %true ], [ %y, %false ]
   %g = getelementptr inbounds i8, i8* %p, i64 1
   call void @llvm.memset.p0i8.i32(i8* %g, i8 0, i32 %size, i1 false)
   call void @llvm.memset.p0i8.i32(i8* %z, i8 0, i32 %size, i1 false)
   ret void
 }
 
 declare void @llvm.memset.p0i8.i32(i8*, i8, i32, i1)
+
+; CHECK-LABEL: unsound_inequality
+; CHECK: MayAlias:  i32* %arrayidx13, i32* %phi
+; CHECK: MayAlias:  i32* %arrayidx5, i32* %phi
+; CHECK: NoAlias:   i32* %arrayidx13, i32* %arrayidx5
+
+; When recursively reasoning about phis, we can't use predicates between
+; two values as we might be comparing the two from different iterations.
+define i32 @unsound_inequality(i32* %jj7, i32* %j) {
+entry:
+  %oa5 = alloca [100 x i32], align 16
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %phi = phi i32* [ %arrayidx13, %for.body ], [ %j, %entry ]
+  %idx = load i32, i32* %jj7, align 4
+  %arrayidx5 = getelementptr inbounds [100 x i32], [100 x i32]* %oa5, i64 0, i32 %idx
+  store i32 0, i32* %arrayidx5, align 4
+  store i32 0, i32* %phi, align 4
+  %notequal = add i32 %idx, 1
+  %arrayidx13 = getelementptr inbounds [100 x i32], [100 x i32]* %oa5, i64 0, i32 %notequal
+  store i32 0, i32* %arrayidx13, align 4
+  br label %for.body
+}