[BasicAA] Fix -basicaa-recphi for geps with negative offsets

[dmgreen]

Summary

As shown in D82998, the basic-aa-recphi option can cause miscompiles for gep's with negative constants. The option checks for recursive phi, that recurse through a contant gep. If it finds one, it performs aliasing calculations using the other phi operands with an unknown size, to specify that an unknown number of elements after the initial value are potentially accessed. This works fine expect where the constant is negative, as the size is still considered to be positive. So this patch checks to make sure that the constant is also positive.

I will not attempt to turn the option back on until after the branch is made next week, to give us lots of time to catch anything else. But this should hopefully fix the issues.

[hfinkel]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1686–1687

I would like to see the "The option checks for recursive phi, that recurse through a contant gep. If it finds one, it performs aliasing calculations using the other phi operands with an unknown size, to specify that an unknown number of elements after the initial value are potentially accessed. This works fine expect where the constant is negative, as the size is still considered to be positive. " part from the patch description -- that information -- in the comment here.

Also, can you make a lambda function do avoid the duplication of the comment and the condition in two places?

[efriedma]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1689

Please avoid getSExtValue() when you can, in favor of APInt methods.

Do we need to check the GEP is inbounds?

[dmgreen]

Thanks. This creates a lambda, adds inbounds and isNegative, and updates some comments.

[hfinkel]

LGTM

[xbolva00]

https://llvm-compile-time-tracker.com/compare.php?from=c74cfd40452d68966c0f22f85773aeef32118974&to=311fafd2c90aed5b3fed9566503eebe629f1e979&stat=instructions

Seems like a minor compile time regression.
@nikic

[nikic]

@xbolva00 This is an artifact I've noticed a few times. When this code in BasicAA is changed, there is a measurable compile-time impact even for changes that should be NFC. I suspect that it triggers some inlining heuristic in a visible way, but never looked into it. I don't think there's anything problematic in this commit itself (it changes functionality that is currently disabled.)

[hans]

Pushed to 11.x as 00ed5355e45b4d7e84366619dbbbb9df9b4aa816

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (PN2->getParent() == PN->getParent()) {
             AAQI.AliasCache.insert(std::make_pair(Locs, OrigAliasResult));
         assert(!Pair.second && "Entry must have existed");
         Pair.first->second = OrigAliasResult;
       }
       return Alias;
     }
 
   SmallVector<Value *, 4> V1Srcs;
+  // For a recursive phi, that recurses through a contant gep, we can perform
+  // aliasing calculations using the other phi operands with an unknown size to
+  // specify that an unknown number of elements after the initial value are
+  // potentially accessed.
   bool isRecursive = false;
-  if (PV)  {
+  auto CheckForRecPhi = [&](Value *PV) {
+    if (!EnableRecPhiAnalysis)
+      return false;
+    if (GEPOperator *PVGEP = dyn_cast<GEPOperator>(PV)) {
+      // Check whether the incoming value is a GEP that advances the pointer
+      // result of this PHI node (e.g. in a loop). If this is the case, we
+      // would recurse and always get a MayAlias. Handle this case specially
+      // below. We need to ensure that the phi is inbounds and has a constant
+      // positive operand so that we can check for alias with the initial value
+      // and an unknown but positive size.
+      if (PVGEP->getPointerOperand() == PN && PVGEP->isInBounds() &&
+          PVGEP->getNumIndices() == 1 && isa<ConstantInt>(PVGEP->idx_begin()) &&
+          !cast<ConstantInt>(PVGEP->idx_begin())->isNegative()) {
+        isRecursive = true;
+        return true;
+      }
+    }
+    return false;
+  };
+
+  if (PV) {
     // If we have PhiValues then use it to get the underlying phi values.
     const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
     // If we have more phi values than the search depth then 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 (PhiValueSet.size() > MaxLookupSearchDepth)
       return MayAlias;
     // Add the values to V1Srcs
     for (Value *PV1 : PhiValueSet) {
-      if (EnableRecPhiAnalysis) {
-        if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
-          // Check whether the incoming value is a GEP that advances the pointer
-          // result of this PHI node (e.g. in a loop). If this is the case, we
-          // would recurse and always get a MayAlias. Handle this case specially
-          // below.
-          if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
-              isa<ConstantInt>(PV1GEP->idx_begin())) {
-            isRecursive = true;
-            continue;
-          }
-        }
-      }
+      if (CheckForRecPhi(PV1))
       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;
     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.
         return MayAlias;
 
-      if (EnableRecPhiAnalysis)
-        if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
-          // Check whether the incoming value is a GEP that advances the pointer
-          // result of this PHI node (e.g. in a loop). If this is the case, we
-          // would recurse and always get a MayAlias. Handle this case specially
-          // below.
-          if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
-              isa<ConstantInt>(PV1GEP->idx_begin())) {
-            isRecursive = true;
-            continue;
-          }
-        }
+      if (CheckForRecPhi(PV1))
 
       if (UniqueSrc.insert(PV1).second)
         V1Srcs.push_back(PV1);
     }
   }
 
   // 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

llvm/test/Analysis/BasicAA/recphi.ll

 ; CHECK-LABEL: Function: reverse: 6 pointers, 0 call sites
 ; CHECK:         MustAlias:    [10 x i32]* %tab, i8* %0
 ; CHECK:         MustAlias:    [10 x i32]* %tab, i32* %arrayidx
 ; CHECK:         MustAlias:    i32* %arrayidx, i8* %0
 ; CHECK:         PartialAlias: [10 x i32]* %tab, i32* %arrayidx1
 ; CHECK:         NoAlias:      i32* %arrayidx1, i8* %0
 ; CHECK:         NoAlias:      i32* %arrayidx, i32* %arrayidx1
 ; CHECK:         MayAlias:     [10 x i32]* %tab, i32* %p.addr.05.i
-; CHECK:         NoAlias:      i32* %p.addr.05.i, i8* %0
-; CHECK:         NoAlias:      i32* %arrayidx, i32* %p.addr.05.i
+; CHECK:         MayAlias:     i32* %p.addr.05.i, i8* %0
+; CHECK:         MayAlias:     i32* %arrayidx, i32* %p.addr.05.i
 ; CHECK:         MayAlias:     i32* %arrayidx1, i32* %p.addr.05.i
 ; CHECK:         MayAlias:     [10 x i32]* %tab, i32* %incdec.ptr.i
 ; CHECK:         MayAlias:     i32* %incdec.ptr.i, i8* %0
 ; CHECK:         MayAlias:     i32* %arrayidx, i32* %incdec.ptr.i
 ; CHECK:         MayAlias:     i32* %arrayidx1, i32* %incdec.ptr.i
 ; CHECK:         NoAlias:      i32* %incdec.ptr.i, i32* %p.addr.05.i
 define i32 @reverse() nounwind {
 entry:

 if.end: ; preds = %f.exit
   ret i32 0
 }
 
 ; CHECK-LABEL: Function: negative: 6 pointers, 1 call sites
 ; CHECK:         NoAlias:      [3 x i16]* %int_arr.10, i16** %argv.6.par
 ; CHECK:         NoAlias:      i16* %_tmp1, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp1
-; CHECK:         NoAlias:      i16* %ls1.9.0, i16** %argv.6.par
+; CHECK:         MayAlias:     i16* %ls1.9.0, i16** %argv.6.par
 ; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %ls1.9.0
-; CHECK:         NoAlias:      i16* %_tmp7, i16** %argv.6.par
+; CHECK:         MayAlias:     i16* %_tmp7, i16** %argv.6.par
 ; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %_tmp7
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %_tmp7
 ; CHECK:         NoAlias:      i16* %_tmp7, i16* %ls1.9.0
 ; CHECK:         NoAlias:      i16* %_tmp11, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp11
 ; CHECK:         NoAlias:      i16* %_tmp1, i16* %_tmp11
-; CHECK:         NoAlias:      i16* %_tmp11, i16* %ls1.9.0
+; CHECK:         MayAlias:     i16* %_tmp11, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp11, i16* %_tmp7
 ; CHECK:         Both ModRef:  Ptr: i16** %argv.6.par  <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 ; CHECK:         NoModRef:  Ptr: [3 x i16]* %int_arr.10        <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 ; CHECK:         NoModRef:  Ptr: i16* %_tmp1   <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 ; CHECK:         Both ModRef:  Ptr: i16* %ls1.9.0      <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 ; CHECK:         Both ModRef:  Ptr: i16* %_tmp7        <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 ; CHECK:         NoModRef:  Ptr: i16* %_tmp11  <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 define i16 @negative(i16 %argc.5.par, i16** nocapture readnone %argv.6.par) {