[BasicAA] Use known lower bounds for index values for size based check.

[fhahn]

Summary

Currently, BasicAA does not exploit information about value ranges of
indexes. For example, consider the 2 pointers %a = %base and
%b = %base + %stride below, assuming they are used to access 4 elements.

If we know that %stride >= 4, we know the accesses do not alias. If
%stride is a constant, BasicAA currently gets that. But if the >= 4
constraint is encoded using an assume, it misses the NoAlias.

This patch extends DecomposedGEP to include an additional MinOtherOffset
field, which tracks the constant offset similar to the existing
OtherOffset, which the difference that it also includes non-negative
lower bounds on the range of the index value. When checking if the
distance between 2 accesses exceeds the access size, we can use this
improved bound.

For now this is limited to using non-negative lower bounds for indices,
as this conveniently skips cases where we do not have a useful lower
bound (because it is not constrained). We potential miss out in cases
where the lower bound is constrained but negative, but that can be
exploited in the future.

[fhahn]

ping

[asbirlea]

lgtm.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

622

s/We we find/If we find

[fhahn]

In D76194#2050329, @asbirlea wrote:

lgtm.

Thank you very much for taking a look! Rebased and comment addressed.

[nikic]

This change caused a 0.5% compile-time regression. The largest regression is 1.6% for lencod (with the q_matrix.c file at 3-4%). As the code-size changes are <= 0.01%, this optimization does not seem to trigger much in practice (and not at all for lencod). This seems like a somewhat unfavorable trade-off between compile-time and optimization power.

[fhahn]

In D76194#2065065, @nikic wrote:

This change caused a 0.5% compile-time regression. The largest regression is 1.6% for lencod (with the q_matrix.c file at 3-4%). As the code-size changes are <= 0.01%, this optimization does not seem to trigger much in practice (and not at all for lencod). This seems like a somewhat unfavorable trade-off between compile-time and optimization power.

Hm yeah that does not look great. I'll check to see if there's something we can do to limit the amount of extra work.

[Carrot]

@fhahn, could you help to take a look at https://bugs.llvm.org/show_bug.cgi?id=46335? It may be caused by this patch.

[fhahn]

In D76194#2104414, @Carrot wrote:

@fhahn, could you help to take a look at https://bugs.llvm.org/show_bug.cgi?id=46335? It may be caused by this patch.

Oh right, from the bug description I initially thought the issue is actually how another pass uses the result. But I was planning on taking a closer look at the compile-time impact and reverting the patch in the meantime. I'll take a closer look in the following days.

[asbirlea]

I think it would be best to revert while investigating; it looks like it would unblock folks, and it's a reasonably small change to recommit.

[fhahn]

I've reverted it for now: 9a7d80a32c8d

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
   struct DecomposedGEP {
     // Base pointer of the GEP
     const Value *Base;
     // Total constant offset w.r.t the base from indexing into structs
     APInt StructOffset;
     // Total constant offset w.r.t the base from indexing through
     // pointers/arrays/vectors
     APInt OtherOffset;
+    // Constant offset w.r.t the base from indexing through
+    // pointers/arrays/vectors, including the lower bounds of index variables,
+    // if there are any. Currently only known non-negative lower bounds are
+    // added.
+    APInt MinOtherOffset;
     // Scaled variable (non-constant) indices.
     SmallVector<VariableGEPIndex, 4> VarIndices;
     // Is GEP index scale compile-time constant.
     bool HasCompileTimeConstantScale;
   };
 
   /// Tracks phi nodes we have visited.
   ///

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
           DL.getStructLayout(STy)->getElementOffset(FieldNo);
         continue;
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero())
           continue;
-        Decomposed.OtherOffset +=
-            (DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() *
+        APInt Offset = (DL.getTypeAllocSize(GTI.getIndexedType()) *
                         CIdx->getValue().sextOrSelf(MaxPointerSize))
                            .sextOrTrunc(MaxPointerSize);
+        Decomposed.OtherOffset += Offset;
+        Decomposed.MinOtherOffset += Offset;
         continue;
       }
 
       GepHasConstantOffset = false;
 
       APInt Scale(MaxPointerSize,
                   DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
       unsigned ZExtBits = 0, SExtBits = 0;
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         Index = OrigIndex;
         IndexScale = 1;
         IndexOffset = 0;
 
         ZExtBits = SExtBits = 0;
         if (PointerSize > Width)
           SExtBits += PointerSize - Width;
       } else {
-        Decomposed.OtherOffset += IndexOffset.sextOrTrunc(MaxPointerSize) * Scale;
+        APInt Offset = IndexOffset.sextOrTrunc(MaxPointerSize) * Scale;
+        Decomposed.OtherOffset += Offset;
+        APInt IndexBound =
+            computeConstantRange(Index, true, AC, dyn_cast<Instruction>(GEPOp))
+                .getLower()
+                .sextOrTrunc(MaxPointerSize);
+        // If we find a non-negative lower bound for the index value, we can
+        // improve the known offset to include it. By just using non-negative
+        // lower bounds, we conveniently skip any index values for which we do
+        // not find a useful lower bound.
+        if (IndexBound.isNonNegative())
+          Decomposed.MinOtherOffset += Offset + IndexBound * Scale;
         Scale *= IndexScale.sextOrTrunc(MaxPointerSize);
       }
 
       // If we already had an occurrence of this index variable, merge this
       // scale into it.  For example, we want to handle:
       //   A[x][x] -> x*16 + x*4 -> x*20
       // This also ensures that 'x' only appears in the index list once.
       for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
AliasResult BasicAAResult::aliasGEP(
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
   DecomposedGEP DecompGEP1, DecompGEP2;
   unsigned MaxPointerSize = getMaxPointerSize(DL);
   DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
   DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
   DecompGEP1.HasCompileTimeConstantScale =
       DecompGEP2.HasCompileTimeConstantScale = true;
+  DecompGEP1.MinOtherOffset = APInt(MaxPointerSize, 0);
+  DecompGEP2.MinOtherOffset = APInt(MaxPointerSize, 0);
 
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
   bool GEP2MaxLookupReached =
     DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
   // Don't attempt to analyze the decomposed GEP if index scale is not a
   // compile-time constant.
   if (!DecompGEP1.HasCompileTimeConstantScale ||
       !DecompGEP2.HasCompileTimeConstantScale)
     return MayAlias;
 
   APInt GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
   APInt GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
+  APInt GEP1BaseOffsetMin = DecompGEP1.StructOffset + DecompGEP1.MinOtherOffset;
+  APInt GEP2BaseOffsetMin = DecompGEP2.StructOffset + DecompGEP2.MinOtherOffset;
 
   assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
          "DecomposeGEPExpression returned a result different from "
          "GetUnderlyingObject");
 
   // If the GEP's offset relative to its base is such that the base would
   // fall below the start of the object underlying V2, then the GEP and V2
   // cannot alias.
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
 
     // If the max search depth is reached, the result is undefined
     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
       return MayAlias;
 
     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
     // symbolic difference.
     GEP1BaseOffset -= GEP2BaseOffset;
+    GEP1BaseOffsetMin -= GEP2BaseOffsetMin;
     GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
 
   } else {
     // Check to see if these two pointers are related by the getelementptr
     // instruction.  If one pointer is a GEP with a non-zero index of the other
     // pointer, we know they cannot alias.
 
     // If both accesses are unknown size, we can't do anything useful here.
if (!DecompGEP1.VarIndices.empty()) {
     if (V1Size != LocationSize::unknown() &&
         V2Size != LocationSize::unknown() && ModOffset.uge(V2Size.getValue()) &&
         (Modulo - ModOffset).uge(V1Size.getValue()))
       return NoAlias;
 
     // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
-    if (AllPositive && GEP1BaseOffset.sgt(0) &&
+    if (AllPositive && GEP1BaseOffsetMin.sgt(0) &&
         V2Size != LocationSize::unknown() &&
-        GEP1BaseOffset.uge(V2Size.getValue()))
+        GEP1BaseOffsetMin.uge(V2Size.getValue())) {
       return NoAlias;
+    }
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 GEP1BaseOffset, &AC, DT))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our

llvm/test/Analysis/BasicAA/assume-index-positive.ll

;
   %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
   %res.1 = fadd <6 x double> %lv.1, %lv.1
   %res.2 = fadd <6 x double> %lv.2, %lv.2
   store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
   store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
   ret void
 }
 
+
+define void @test5(double* %ptr, i32 %stride) {
+; CHECK-LABEL: Function: test5: 4 pointers, 1 call sites
+; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.1, double* %ptr
+; CHECK-NEXT:  NoAlias:    double* %col.ptr.2, double* %ptr
+; CHECK-NEXT:  MayAlias:   <6 x double>* %col.ptr.1, double* %col.ptr.2
+; CHECK-NEXT:  NoAlias:    <6 x double>* %col.ptr.2.cast, double* %ptr
+; CHECK-NEXT:  MayAlias:   <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast
+; CHECK-NEXT:  MustAlias:  <6 x double>* %col.ptr.2.cast, double* %col.ptr.2
+; CHECK-NEXT:  NoModRef:  Ptr: double* %ptr <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.1 <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: double* %col.ptr.2   <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.2.cast    <->  call void @llvm.assume(i1 %gt)
+;
+  %gt = icmp sge i32 %stride, 5
+  call void @llvm.assume(i1 %gt)
+  %col.ptr.1 = bitcast double* %ptr to <6 x double>*
+  %lv.1 = load <6 x double>, <6 x double>* %col.ptr.1, align 8
+  %col.ptr.2= getelementptr double, double* %ptr, i32 %stride
+  %col.ptr.2.cast = bitcast double* %col.ptr.2 to <6 x double>*
+  %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
+  %res.1 = fadd <6 x double> %lv.1, %lv.1
+  %res.2 = fadd <6 x double> %lv.2, %lv.2
+  store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
+  store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
+  ret void
+}
+
+define void @test6(double* %ptr, i32 %stride) {
+; CHECK-LABEL: Function: test6: 4 pointers, 1 call sites
+; CHECK-NEXT:  MustAlias:  <6 x double>* %col.ptr.1, double* %ptr
+; CHECK-NEXT:  NoAlias:    double* %col.ptr.2, double* %ptr
+; CHECK-NEXT:  NoAlias:    <6 x double>* %col.ptr.1, double* %col.ptr.2
+; CHECK-NEXT:  NoAlias:    <6 x double>* %col.ptr.2.cast, double* %ptr
+; CHECK-NEXT:  NoAlias:    <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast
+; CHECK-NEXT:  MustAlias:  <6 x double>* %col.ptr.2.cast, double* %col.ptr.2
+; CHECK-NEXT:  NoModRef:  Ptr: double* %ptr <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.1 <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: double* %col.ptr.2   <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.2.cast    <->  call void @llvm.assume(i1 %gt)
+;
+  %gt = icmp sge i32 %stride, 6
+  call void @llvm.assume(i1 %gt)
+  %col.ptr.1 = bitcast double* %ptr to <6 x double>*
+  %lv.1 = load <6 x double>, <6 x double>* %col.ptr.1, align 8
+  %col.ptr.2= getelementptr double, double* %ptr, i32 %stride
+  %col.ptr.2.cast = bitcast double* %col.ptr.2 to <6 x double>*
+  %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
+  %res.1 = fadd <6 x double> %lv.1, %lv.1
+  %res.2 = fadd <6 x double> %lv.2, %lv.2
+  store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
+  store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
+  ret void
+}
+
+define void @test7(double* %ptr, i32 %stride) {
+; CHECK-LABEL: Function: test7: 4 pointers, 1 call sites
+; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.1, double* %ptr
+; CHECK-NEXT:  MayAlias:    double* %col.ptr.2, double* %ptr
+; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, double* %col.ptr.2
+; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.2.cast, double* %ptr
+; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast
+; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.2.cast, double* %col.ptr.2
+; CHECK-NEXT:  NoModRef:  Ptr: double* %ptr <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.1 <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: double* %col.ptr.2   <->  call void @llvm.assume(i1 %gt)
+; CHECK-NEXT:  NoModRef:  Ptr: <6 x double>* %col.ptr.2.cast    <->  call void @llvm.assume(i1 %gt)
+;
+  %gt = icmp sge i32 %stride, 0
+  call void @llvm.assume(i1 %gt)
+  %col.ptr.1 = bitcast double* %ptr to <6 x double>*
+  %lv.1 = load <6 x double>, <6 x double>* %col.ptr.1, align 8
+  %col.ptr.2= getelementptr double, double* %ptr, i32 %stride
+  %col.ptr.2.cast = bitcast double* %col.ptr.2 to <6 x double>*
+  %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
+  %res.1 = fadd <6 x double> %lv.1, %lv.1
+  %res.2 = fadd <6 x double> %lv.2, %lv.2
+  store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
+  store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
+  ret void
+}
+
 declare void @llvm.assume(i1 %cond)

llvm/test/Analysis/BasicAA/bug.23626.ll

 ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-darwin13.4.0"
 
 ; CHECK-LABEL: compute1
 ; CHECK: MayAlias:  i32* %arrayidx8, i32* %out
-; CHECK: MayAlias:  i32* %arrayidx11, i32* %out
+; CHECK: NoAlias: i32* %arrayidx11, i32* %out
 ; CHECK: MayAlias:  i32* %arrayidx11, i32* %arrayidx8
-; CHECK: MayAlias:  i32* %arrayidx14, i32* %out
+; CHECK: NoAlias: i32* %arrayidx14, i32* %out
 ; CHECK: MayAlias:  i32* %arrayidx14, i32* %arrayidx8
 ; CHECK: MayAlias:  i32* %arrayidx11, i32* %arrayidx14
 define void @compute1(i32 %num.0.lcssa, i32* %out) {
   %idxprom = zext i32 %num.0.lcssa to i64
   %arrayidx8 = getelementptr inbounds i32, i32* %out, i64 %idxprom
   %add9 = or i32 %num.0.lcssa, 1
   %idxprom10 = zext i32 %add9 to i64
   %arrayidx11 = getelementptr inbounds i32, i32* %out, i64 %idxprom10