[Attributor] Use AAValueConstantRange to infer dereferencability.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

616 ↗

(On Diff #250458)

Isn't this almost the stripAndAccumulate code? How hard would it be to pass some kind of AttributorInfo object to that function (optionally) which triggers the lookup. Or more generically, a callback that takes a Value and returns a lower bound offset (plus indicates success/failure).

llvm/test/Transforms/Attributor/dereferenceable-1.ll

234

Isn't this the fill_range code?

[uenoku]

Thank you for working on this!!

As a high-level comment, please add full-context of diff(diff -U99999)

llvm/lib/Transforms/IPO/Attributor.cpp

511 ↗

(On Diff #250458)

Add commnent here

llvm/test/Transforms/Attributor/dereferenceable-1.ll

214

I think optimaly %ptr is dereferenceable(30).
Please add FIXME here.

[kuter]

Made the changes @jdoerfert asked for.

[kuter]

@jdoerfert

This patch is not complete yet.

Currently it can only use the known information. I would like to make it possible for it to use the assumed information as well.
The problem with that is:

We need to iterate over the uses and take the maximum of the current dereferancability that is indicated by that use.
this works fine for the known info. But since the lower bound of the assumed constant range can decrease over time,
taking max with existing state is a problem.

The way that the AAFromMustBeExecutedContext is wired makes things a bit tricky and
I would like to get your opinions on this before I proceed.

[jdoerfert]

Can you explain why we need to catch overflows now but not before? I mean, the values determine by the external analysis are valid lower bounds, what is different from versioning on them and making them constant in one of the versions.

In D76208#1931081, @kuter wrote:

@jdoerfert

This patch is not complete yet.

Currently it can only use the known information. I would like to make it possible for it to use the assumed information as well.
The problem with that is:

We need to iterate over the uses and take the maximum of the current dereferancability that is indicated by that use.
this works fine for the known info. But since the lower bound of the assumed constant range can decrease over time,
taking max with existing state is a problem.

The way that the AAFromMustBeExecutedContext is wired makes things a bit tricky and
I would like to get your opinions on this before I proceed.

I think we should finish this one and then do the following:

We actually don't want the minimal offset but the maximal known offset, right? In addition to renaming the function we will check if the range from AAConstantRange is known, if so, we take the maximum instead.

llvm/include/llvm/IR/Operator.h

563

= nullptr is not sufficient? unfortunate.
Nit: -value +Offset, or remove the names.

Please describe what external analysis exactly does here.

I like the solution of adding this callback though. We need more of these soon.

llvm/lib/IR/Value.cpp

644

Put the entire thing in an if (ExternalAnalysis) please. Or better !ExternaAnalysis then old code, else this code.
TBH, I'm not sure why we don't bail on overflow in the old code as well, maybe we should. Can you check if that would make any test fail?

llvm/lib/Transforms/IPO/Attributor.cpp

552 ↗

(On Diff #251274)

Style: UseAssumed, Range, Value, etc.

[kuter]

llvm/test/Transforms/Attributor/dereferenceable-1.ll

214

OK, I will.

For us to be able to deduce a 30, there would have to be separate mechanism that deduces the biggest number
that the "Value" in question is going to be guaranteed to take.

Perhaps we could use SCEV ?

234

No it is not. Currently this patch does not work with for loops.

This is because with for loops AAFromMustBeExecutedContext looks at the branch at the top;
calls the followUse() on both of the successors and it "and"s them together.

This is probably the reason why only a single test is affected by this patch.

I will address this issue with a separate patch that passes LoopInfo, DominatorTree and the PostDominatorTree
to the MustBeExecutedContextExplorer.

[kuter]

In D76208#1932759, @jdoerfert wrote:

Can you explain why we need to catch overflows now but not before? I mean, the values determine by the external analysis are valid lower bounds, what is different from versioning on them and making them constant in one of the versions.

In D76208#1931081, @kuter wrote:

@jdoerfert

This patch is not complete yet.

Currently it can only use the known information. I would like to make it possible for it to use the assumed information as well.
The problem with that is:

We need to iterate over the uses and take the maximum of the current dereferancability that is indicated by that use.
this works fine for the known info. But since the lower bound of the assumed constant range can decrease over time,
taking max with existing state is a problem.

The way that the AAFromMustBeExecutedContext is wired makes things a bit tricky and
I would like to get your opinions on this before I proceed.

I think we should finish this one and then do the following:

We actually don't want the minimal offset but the maximal known offset, right? In addition to renaming the function we will check if the range from AAConstantRange is known, if so, we take the maximum instead.

void internal test(int index, char *ptrArg) {
  ptrArg[index] = 'A';
}

test(10, ptrA);
test(30, ptrB);
test(40, ptrC);

Based on call sites the index argument of the test function would be in range [10, 40] right ?
but marking ptrArg dereferancable(41) would be wrong woudn't it ?

The reason that I made the stripAndAccumulateConstantOffsets overflow aware is that the range can be lower than what it can be in reality.
I thought that these differences can result in unintended underflows.

For accumulateConstantOffset, I think for non inbound GEP's overflows should be ok.
but for stripAndAccumulateConstantOffsets bailing out should probably be the default behaviour.

[jdoerfert]

In D76208#1932819, @kuter wrote:

In D76208#1932759, @jdoerfert wrote:

Can you explain why we need to catch overflows now but not before? I mean, the values determine by the external analysis are valid lower bounds, what is different from versioning on them and making them constant in one of the versions.

In D76208#1931081, @kuter wrote:

@jdoerfert

This patch is not complete yet.

Currently it can only use the known information. I would like to make it possible for it to use the assumed information as well.
The problem with that is:

We need to iterate over the uses and take the maximum of the current dereferancability that is indicated by that use.
this works fine for the known info. But since the lower bound of the assumed constant range can decrease over time,
taking max with existing state is a problem.

The way that the AAFromMustBeExecutedContext is wired makes things a bit tricky and
I would like to get your opinions on this before I proceed.

I think we should finish this one and then do the following:

We actually don't want the minimal offset but the maximal known offset, right? In addition to renaming the function we will check if the range from AAConstantRange is known, if so, we take the maximum instead.

void internal test(int index, char *ptrArg) {
  ptrArg[index] = 'A';
}

test(10, ptrA);
test(30, ptrB);
test(40, ptrC);

Based on call sites the index argument of the test function would be in range [10, 40] right ?
but marking ptrArg dereferancable(41) would be wrong woudn't it ?

Correct. First though was: we need something special for the loop case so we know we reach the upper bound. After all, that is probably the most important case to get.

The reason that I made the stripAndAccumulateConstantOffsets overflow aware is that the range can be lower than what it can be in reality.
I thought that these differences can result in unintended underflows.

I see. Agreed.

For accumulateConstantOffset, I think for non inbound GEP's overflows should be ok.
but for stripAndAccumulateConstantOffsets bailing out should probably be the default behaviour.

OK.

llvm/test/Transforms/Attributor/dereferenceable-1.ll

234

Right. That reminds me of D64974, though I'm unsure if we still need it. What we need is to make the explorer aware of CanProveNotTakenFirstIteration. Similar to the use of that function that exists, we can go to the non-exit block from a header in getMustBeExecutedNextInstruction (or findForwardJoinPoint) if we know that edge is taken at least once. To not loose the code after the loop we should add a stack of unexplored edges. The exit edge goes there if the loop is known not to be endless (see findForwardJoinPoint). If we are out of forward instructions we can pop an edge from the stack and continue. Alternatively, we could check if the loop was not endless when we visit the header for the second time.

[kuter]

Fixed styling, Added FIXME, Sperated new code.

[uenoku]

llvm/test/Transforms/Attributor/willreturn.ll

364

Why can't we get dereferenceable(4) for p in this case?

[kuter]

llvm/test/Transforms/Attributor/willreturn.ll

364

Ok for this example specifically, the variable n can be negative so the ans +=p[n] may never be executed.

But in general, this patch doesn't work with loops that are not do {} while (cond)

This is because AAFromMustBeExecutedContext is not aware when the first iteration is always going to be ran.

This needs to be addressed with a separate path and would probably improve many other deductions as well.

[baziotis]

llvm/test/Transforms/Attributor/willreturn.ll

364

IIUC, loop rotation can help here because it provides this guarantee.

[uenoku]

llvm/test/Transforms/Attributor/willreturn.ll

364

Oh, I thought %n is assumed to be positive:) Thanks.

[uenoku]

llvm/test/Transforms/Attributor/dereferenceable-1.ll

214

For us to be able to deduce a 30, there would have to be separate mechanism that deduces the biggest number

that the "Value" in question is going to be guaranteed to take.
Agreed.

Perhaps we could use SCEV ?

I think so, what I thought once is:
Assume that a loop is in the context and it is guaranteed to proceed to the last iteration, we can use the biggest number of the value. For inbounds gep, it is allowed to take that number as dereferenceable bytes, and for non-inbounds gep, if SCEV of the value is something like <0, +, 1>, we can take the biggest number as derefrenceable bytes.

[jdoerfert]

This is because AAFromMustBeExecutedContext is not aware when the first iteration is always going to be ran.
This needs to be addressed with a separate path and would probably improve many other deductions as well.

Agreed and agreed.

Perhaps we could use SCEV ?

[...]

We could. What we want (regardless of how) is to track in AAConstantRange (conceptually) two ranges: (1) potential value range, (2) known value range. This is not the same as the assumed/known we track now. Right now bot track the potential value range, that is what value can this llvm::Value potentially have at runtime. I think tracking the second, thus, what value is this llvm::Value going to have at runtime (if it is executed) could be tracked in the same AA or a different one, depending on how much logic we can share. This is also a follow up patch (or two).

---

I'll have to go through the logic in this patch tomorrow (=rested) but I think it looks pretty good.

[kuter]

In D76208#1936117, @jdoerfert wrote:

We could. What we want (regardless of how) is to track in AAConstantRange (conceptually) two ranges: (1) potential value range, (2) known value range. This is not the same as the assumed/known we track now. Right now bot track the potential value range, that is what value can this llvm::Value potentially have at runtime. I think tracking the second, thus, what value is this llvm::Value going to have at runtime (if it is executed) could be tracked in the same AA or a different one, depending on how much logic we can share. This is also a follow up patch (or two).

Agreed.

Currently AAConstantRange tracks the range that a "llvm::value" is guaranteed to be within in runtime.
But for loops, this is results in information loss.

So I think what you suggest is that we track a specific range for loop like situations.
for an actual loop this would be, the first and the last index of the counter.

and when we are propagating this range from phi nodes, select instructions, call sites (of internal functions) we would intersect them together.

For example:

void test_use(char  *ptrA, char *ptrB) {
  for (int i = 10; i < 100; i++) {
    test(ptrA, i); //i is in [10, 99] loop range.
  }
  for (int i = 5; i < 150; i++) {
    test(ptrB, i); //i is in [5, 149] loop range.
  }
}

//i is in [10, 99] loop range
//ptr is dereferencable(100)
void internal test(char *ptr, int i) {
  ptr[i] = 'A';
}

[jdoerfert]

We should finish this review and then focus on the next steps. I added more comments but I think the general logic is fine.

(Next step would be to rename the range in AAConstantRange to PossibleRange, or similar, and add a second range, e.g., ObservedRange which we need to deduce. We can then use the max(PossibleRange.minimum(), ObservedRange.maximum()) for dereferenceable deduction.

llvm/lib/IR/Operator.cpp

93

Style: I think it would be easier to read if you split the above if-else-cascade and use early exits:

 MinimalIndex = ConstOffset->getValue();
 continue;
}

// The operand is not constant, check if an external analysis was provided. 
if (!ExternalAnalysis)
  return false;

Do we need to track overflow *before* we use an external analysis? If not we don't need 75/76. Below we can than use UsedExternalAnalysis in 88 and remove it from 95. We should also be able to use a single overflowed flag.

110

Put the simple case first, maybe add a continue to avoid the "else"

llvm/lib/IR/Value.cpp

649

Simple case first please.

llvm/lib/Transforms/IPO/Attributor.cpp

552 ↗

(On Diff #251822)

Some names are still starting with a lower case letter.

Do we have a test where the assumed range minimum is negative?

3749 ↗

(On Diff #251822)

Merge in a single debug message and line.

3803 ↗

(On Diff #251822)

No need for the newline in the beginning. TBH, the entire message doesn't help much given that we see the update debug message already.

[kuter]

Eliminated redundant debug messages, Style fixes, Added negative test case,
Don't use external analysis if the get operand is a struct type.

[kuter]

llvm/lib/IR/Operator.cpp

93

We probably don't need to detect a overflow before the use of external analysis I was just being safe.

I am not sure what you mean by the early exit change.
We need to detect overflows that happen after we use ExternalAnalysis even if it was not caused by the value that the ExternalAnalysis have returned.

So the value of the ConstantOffset needs to pass through something that would detect a overflow if ExternalAnalysis is present and it has been used.

We could do it with a lambda like this:

  AddArrayIndex(ConstOffset->getValue());
  continue;
}

Also do we really need to have the old and the new code in this style:

if (!External Analysis) {
  //old
} else {
 //new
}

New code shouldn't really behave any different other than detecting overflows/underflows.

[jdoerfert]

llvm/lib/IR/Operator.cpp

93

1. When we want to check UsedExternal in order to determine if an overflow check is necessary not ExternalAnalysis.
2. We should create the lambda you mentioned.
3. Don't track overflowed outside of the lambda. In the lambda check if usedexternal is set, only if we track and act on overflows.

[kuter]

Simplfy accumulateConstantOffset

[jdoerfert]

Two more minor comments, other than that the code looks good. Please update so I can commit it.

llvm/lib/IR/Operator.cpp

59

Nit: Don't call it MinimalIndex as there might be use cases that over-approximate the number. Index is just fine I think.

llvm/lib/Transforms/IPO/Attributor.cpp

566 ↗

(On Diff #252668)

Nit: AllowNonInbounds and `Value above. Check other variable names as well.

[jdoerfert]

Apologies for the delay, can you rebase this and provide me with "Firstname Lastname <email>" from you so I can attribute it to you?

[kuter]

Rebased.
Small logic change in GEPOperator::accumulateConstantOffset to bailout on scalable vector types
except for when the offset is zero.
Not allowing zero breaks @test_accumulate_constant_offset_vscale_zero

see https://reviews.llvm.org/rGef64ba831194c7deac8882a325ea9bea64eb612a

[kuter]

In D76208#1956335, @jdoerfert wrote:

Apologies for the delay, can you rebase this and provide me with "Firstname Lastname <email>" from you so I can attribute it to you?

name, surname: Kuter Dinel
email: [e-mail]

llvm/include/llvm/IR/Operator.h

public:
   unsigned countNonConstantIndices() const {
     return count_if(make_range(idx_begin(), idx_end()), [](const Use& use) {
         return !isa<ConstantInt>(*use);
       });
   }
 
   /// Accumulate the constant address offset of this GEP if possible.
   ///
-  /// This routine accepts an APInt into which it will accumulate the constant
-  /// offset of this GEP if the GEP is in fact constant. If the GEP is not
-  /// all-constant, it returns false and the value of the offset APInt is
-  /// undefined (it is *not* preserved!). The APInt passed into this routine
-  /// must be at exactly as wide as the IntPtr type for the address space of the
-  /// base GEP pointer.
-  bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset) const;
+  /// This routine accepts an APInt into which it will try to accumulate the
+  /// constant offset of this GEP.
+  ///
+  /// If \p ExternalAnalysis is provided it will be used to calculate a offset
+  /// when a operand of GEP is not constant.
+  /// For example, for a value \p ExternalAnalysis might try to calculate a
+  /// lower bound. If \p ExternalAnalysis is successful, it should return true.
+  ///
+  /// If the \p ExternalAnalysis returns false or the value returned by \p
+  /// ExternalAnalysis results in a overflow/underflow, this routine returns
+  /// false and the value of the offset APInt is undefined (it is *not*
+  /// preserved!).
+  ///
+  /// The APInt passed into this routine must be at exactly as wide as the
+  /// IntPtr type for the address space of the base GEP pointer.
+  bool accumulateConstantOffset(
+      const DataLayout &DL, APInt &Offset,
+      function_ref<bool(Value &, APInt &)> ExternalAnalysis = nullptr) const;
 };
 
 class PtrToIntOperator
     : public ConcreteOperator<Operator, Instruction::PtrToInt> {
   friend class PtrToInt;
   friend class ConstantExpr;
 
 public:

llvm/include/llvm/IR/Value.h

#include "llvm/IR/Value.def"
   /// value, it returns 'this'.
   const Value *stripInBoundsConstantOffsets() const;
   Value *stripInBoundsConstantOffsets() {
     return const_cast<Value *>(
               static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
   }
 
   /// Accumulate the constant offset this value has compared to a base pointer.
-  /// Only 'getelementptr' instructions (GEPs) with constant indices are
-  /// accumulated but other instructions, e.g., casts, are stripped away as
-  /// well. The accumulated constant offset is added to \p Offset and the base
+  /// Only 'getelementptr' instructions (GEPs) are accumulated but other
+  /// instructions, e.g., casts, are stripped away as well.
+  /// The accumulated constant offset is added to \p Offset and the base
   /// pointer is returned.
   ///
   /// The APInt \p Offset has to have a bit-width equal to the IntPtr type for
   /// the address space of 'this' pointer value, e.g., use
   /// DataLayout::getIndexTypeSizeInBits(Ty).
   ///
-  /// If \p AllowNonInbounds is true, constant offsets in GEPs are stripped and
+  /// If \p AllowNonInbounds is true, offsets in GEPs are stripped and
   /// accumulated even if the GEP is not "inbounds".
   ///
+  /// If \p ExternalAnalysis is provided it will be used to calculate a offset
+  /// when a operand of GEP is not constant.
+  /// For example, for a value \p ExternalAnalysis might try to calculate a
+  /// lower bound. If \p ExternalAnalysis is successful, it should return true.
+  ///
   /// If this is called on a non-pointer value, it returns 'this' and the
   /// \p Offset is not modified.
   ///
   /// Note that this function will never return a nullptr. It will also never
   /// manipulate the \p Offset in a way that would not match the difference
   /// between the underlying value and the returned one. Thus, if no constant
   /// offset was found, the returned value is the underlying one and \p Offset
   /// is unchanged.
-  const Value *stripAndAccumulateConstantOffsets(const DataLayout &DL,
-                                                 APInt &Offset,
-                                                 bool AllowNonInbounds) const;
+  const Value *stripAndAccumulateConstantOffsets(
+      const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
+      function_ref<bool(Value &Value, APInt &Offset)> ExternalAnalysis =
+          nullptr) const;
   Value *stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset,
                                            bool AllowNonInbounds) {
     return const_cast<Value *>(
         static_cast<const Value *>(this)->stripAndAccumulateConstantOffsets(
             DL, Offset, AllowNonInbounds));
   }
 
   /// This is a wrapper around stripAndAccumulateConstantOffsets with the

llvm/lib/IR/Operator.cpp

Type *GEPOperator::getSourceElementType() const {
   return cast<GetElementPtrConstantExpr>(this)->getSourceElementType();
 }
 
 Type *GEPOperator::getResultElementType() const {
   if (auto *I = dyn_cast<GetElementPtrInst>(this))
     return I->getResultElementType();
   return cast<GetElementPtrConstantExpr>(this)->getResultElementType();
 }
-
-bool GEPOperator::accumulateConstantOffset(const DataLayout &DL,
-                                           APInt &Offset) const {
+bool GEPOperator::accumulateConstantOffset(
+    const DataLayout &DL, APInt &Offset,
+    function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
   assert(Offset.getBitWidth() ==
              DL.getIndexSizeInBits(getPointerAddressSpace()) &&
          "The offset bit width does not match DL specification.");
 
-  for (gep_type_iterator GTI = gep_type_begin(this), GTE = gep_type_end(this);
-       GTI != GTE; ++GTI) {
-    ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
-    if (!OpC)
+  bool UsedExternalAnalysis = false;
+  auto AccumulateOffset = [&](APInt Index, uint64_t Size) -> bool {
+    Index = Index.sextOrTrunc(Offset.getBitWidth());
+    APInt IndexedSize = APInt(Offset.getBitWidth(), Size);
+    // For array or vector indices, scale the index by the size of the type.
+    if (!UsedExternalAnalysis) {
+      Offset += Index * IndexedSize;
+    } else {
+      // External Analysis can return a result higher/lower than the value
+      // represents. We need to detect overflow/underflow.
+      bool Overflow = false;
+      APInt OffsetPlus = Index.smul_ov(IndexedSize, Overflow);
+      if (Overflow)
         return false;
-    if (OpC->isZero())
-      continue;
+      Offset = Offset.sadd_ov(OffsetPlus, Overflow);
+      if (Overflow)
+        return false;
+    }
+    return true;
+  };
 
-    // Scalable vectors have are multiplied by a runtime constant.
+  for (gep_type_iterator GTI = gep_type_begin(this), GTE = gep_type_end(this);
+       GTI != GTE; ++GTI) {
+    // Scalable vectors are have to be multiplied by a runtime constant.
+    bool ScalableType = false;
     if (auto *VecTy = dyn_cast<VectorType>(GTI.getIndexedType()))
-      if (VecTy->isScalable())
-        return false;
+      ScalableType = VecTy->isScalable();
 
+    Value *V = GTI.getOperand();
+    StructType *STy = GTI.getStructTypeOrNull();
+    // Handle ConstantInt if possible.
+    if (auto ConstOffset = dyn_cast<ConstantInt>(V)) {
+      if (ConstOffset->isZero())
+        continue;
+      // if the type is scalable and the constant is not zero (vscale * n * 0 =
+      // 0) bailout.
+      if (ScalableType)
+        return false;
       // Handle a struct index, which adds its field offset to the pointer.
-    if (StructType *STy = GTI.getStructTypeOrNull()) {
-      unsigned ElementIdx = OpC->getZExtValue();
+      if (STy) {
+        unsigned ElementIdx = ConstOffset->getZExtValue();
         const StructLayout *SL = DL.getStructLayout(STy);
-      Offset += APInt(Offset.getBitWidth(), SL->getElementOffset(ElementIdx));
+        // Element offset is in bytes.
+        if (!AccumulateOffset(
+                APInt(Offset.getBitWidth(), SL->getElementOffset(ElementIdx)),
+                1))
+          return false;
         continue;
       }
-
-    // For array or vector indices, scale the index by the size of the type.
-    APInt Index = OpC->getValue().sextOrTrunc(Offset.getBitWidth());
-    Offset += Index * APInt(Offset.getBitWidth(),
-                            DL.getTypeAllocSize(GTI.getIndexedType()));
+      if (!AccumulateOffset(ConstOffset->getValue(),
+                            DL.getTypeAllocSize(GTI.getIndexedType())))
+        return false;
+      continue;
+    }
+    // The operand is not constant, check if an external analysis was provided.
+    // External analsis is not applicable to a struct type.
+    if (!ExternalAnalysis || STy || ScalableType)
+      return false;
+    APInt AnalysisIndex;
+    if (!ExternalAnalysis(*V, AnalysisIndex))
+      return false;
+    UsedExternalAnalysis = true;
+    if (!AccumulateOffset(AnalysisIndex,
+                          DL.getTypeAllocSize(GTI.getIndexedType())))
+      return false;
   }
   return true;
 }
 }

llvm/lib/IR/Value.cpp

 const Value *Value::stripInBoundsConstantOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 }
 
 const Value *Value::stripPointerCastsAndInvariantGroups() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndInvariantGroups>(this);
 }
 
-const Value *
-Value::stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset,
-                                         bool AllowNonInbounds) const {
+const Value *Value::stripAndAccumulateConstantOffsets(
+    const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
+    function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
   if (!getType()->isPtrOrPtrVectorTy())
     return this;
 
   unsigned BitWidth = Offset.getBitWidth();
   assert(BitWidth == DL.getIndexTypeSizeInBits(getType()) &&
          "The offset bit width does not match the DL specification.");
 
   // Even though we don't look through PHI nodes, we could be called on an
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
 
       // If one of the values we have visited is an addrspacecast, then
       // the pointer type of this GEP may be different from the type
       // of the Ptr parameter which was passed to this function.  This
       // means when we construct GEPOffset, we need to use the size
       // of GEP's pointer type rather than the size of the original
       // pointer type.
       APInt GEPOffset(DL.getIndexTypeSizeInBits(V->getType()), 0);
-      if (!GEP->accumulateConstantOffset(DL, GEPOffset))
+      if (!GEP->accumulateConstantOffset(DL, GEPOffset, ExternalAnalysis))
         return V;
 
       // Stop traversal if the pointer offset wouldn't fit in the bit-width
       // provided by the Offset argument. This can happen due to AddrSpaceCast
       // stripping.
       if (GEPOffset.getMinSignedBits() > BitWidth)
         return V;
 
-      Offset += GEPOffset.sextOrTrunc(BitWidth);
+      // External Analysis can return a result higher/lower than the value
+      // represents. We need to detect overflow/underflow.
+      APInt GEPOffsetST = GEPOffset.sextOrTrunc(BitWidth);
+      if (!ExternalAnalysis) {
+        Offset += GEPOffsetST;
+      } else {
+        bool Overflow = false;
+        APInt OldOffset = Offset;
+        Offset = Offset.sadd_ov(GEPOffsetST, Overflow);
+        if (Overflow) {
+          Offset = OldOffset;
+          return V;
+        }
+      }
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
       if (!GA->isInterposable())
         V = GA->getAliasee();
     } else if (const auto *Call = dyn_cast<CallBase>(V)) {

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

static bool genericValueTraversal(
   // If we actually used liveness information so we have to record a dependence.
   if (AnyDead)
     A.recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL);
 
   // All values have been visited.
   return true;
 }
 
+const Value *stripAndAccumulateMinimalOffsets(
+    Attributor &A, const AbstractAttribute &QueryingAA, const Value *Val,
+    const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
+    bool UseAssumed = false) {
+
+  auto AttributorAnalysis = [&](Value &V, APInt &ROffset) -> bool {
+    const IRPosition &Pos = IRPosition::value(V);
+    // Only track dependence if we are going to use the assumed info.
+    const AAValueConstantRange &ValueConstantRangeAA =
+        A.getAAFor<AAValueConstantRange>(QueryingAA, Pos,
+                                         /* TrackDependence */ UseAssumed);
+    ConstantRange Range = UseAssumed ? ValueConstantRangeAA.getAssumed()
+                                     : ValueConstantRangeAA.getKnown();
+    // We can only use the lower part of the range because the upper part can
+    // be higher than what the value can really be.
+    ROffset = Range.getSignedMin();
+    return true;
+  };
+
+  return Val->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds,
+                                                AttributorAnalysis);
+}
+
+static const Value *getMinimalBaseOfAccsesPointerOperand(
+    Attributor &A, const AbstractAttribute &QueryingAA, const Instruction *I,
+    int64_t &BytesOffset, const DataLayout &DL, bool AllowNonInbounds = false) {
+  const Value *Ptr = getPointerOperand(I, /* AllowVolatile */ false);
+  if (!Ptr)
+    return nullptr;
+  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
+  const Value *Base = stripAndAccumulateMinimalOffsets(
+      A, QueryingAA, Ptr, DL, OffsetAPInt, AllowNonInbounds);
+
+  BytesOffset = OffsetAPInt.getSExtValue();
+  return Base;
+}
+
 static const Value *
 getBasePointerOfAccessPointerOperand(const Instruction *I, int64_t &BytesOffset,
                                      const DataLayout &DL,
                                      bool AllowNonInbounds = false) {
   const Value *Ptr = getPointerOperand(I, /* AllowVolatile */ false);
   if (!Ptr)
     return nullptr;
 
static int64_t getKnownNonNullAndDerefBytesForUse(
 
   // We need to follow common pointer manipulation uses to the accesses they
   // feed into. We can try to be smart to avoid looking through things we do not
   // like for now, e.g., non-inbounds GEPs.
   if (isa<CastInst>(I)) {
     TrackUse = true;
     return 0;
   }
-  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
-    if (GEP->hasAllConstantIndices()) {
-      TrackUse = true;
-      return 0;
-    }
+
+  if (isa<GetElementPtrInst>(I)) {
 
   int64_t Offset;
-  if (const Value *Base = getBasePointerOfAccessPointerOperand(I, Offset, DL)) {
+  const Value *Base =
+      getMinimalBaseOfAccsesPointerOperand(A, QueryingAA, I, Offset, DL);
+  if (Base) {
     if (Base == &AssociatedValue &&
         getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
       int64_t DerefBytes =
           (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()) + Offset;
 
       IsNonNull |= !NullPointerIsDefined;
       return std::max(int64_t(0), DerefBytes);
     }
   }
 
   /// Corner case when an offset is 0.
-  if (const Value *Base = getBasePointerOfAccessPointerOperand(
-          I, Offset, DL, /*AllowNonInbounds*/ true)) {
+  Base = getBasePointerOfAccessPointerOperand(I, Offset, DL,
+                                              /*AllowNonInbounds*/ true);
+  if (Base) {
     if (Offset == 0 && Base == &AssociatedValue &&
         getPointerOperand(I, /* AllowVolatile */ false) == UseV) {
       int64_t DerefBytes =
           (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType());
       IsNonNull |= !NullPointerIsDefined;
       return std::max(int64_t(0), DerefBytes);
     }
   }
struct AADereferenceableImpl : AADereferenceable {
 
   /// See AAFromMustBeExecutedContext
   bool followUse(Attributor &A, const Use *U, const Instruction *I,
                  AADereferenceable::StateType &State) {
     bool IsNonNull = false;
     bool TrackUse = false;
     int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
         A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
+    LLVM_DEBUG(dbgs() << "[AADereferenceable] Deref bytes: " << DerefBytes
+                      << " for instruction " << *I << "\n");
 
     addAccessedBytesForUse(A, U, I, State);
     State.takeKnownDerefBytesMaximum(DerefBytes);
     return TrackUse;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
struct AADereferenceableFloating
   AADereferenceableFloating(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     ChangeStatus Change = Base::updateImpl(A);
 
     const DataLayout &DL = A.getDataLayout();
 
-    auto VisitValueCB = [&](Value &V, const Instruction *, DerefState &T,
+    auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
                             bool Stripped) -> bool {
       unsigned IdxWidth =
           DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
       APInt Offset(IdxWidth, 0);
       const Value *Base =
-          V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+          stripAndAccumulateMinimalOffsets(A, *this, &V, DL, Offset, false);
 
       const auto &AA =
           A.getAAFor<AADereferenceable>(*this, IRPosition::value(*Base));
       int64_t DerefBytes = 0;
       if (!Stripped && this == &AA) {
         // Use IR information if we did not strip anything.
         // TODO: track globally.
         bool CanBeNull;
         DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
         T.GlobalState.indicatePessimisticFixpoint();
       } else {
         const DerefState &DS = static_cast<const DerefState &>(AA.getState());
         DerefBytes = DS.DerefBytesState.getAssumed();
         T.GlobalState &= DS.GlobalState;
       }
 
-      // TODO: Use `AAConstantRange` to infer dereferenceable bytes.
 
       // For now we do not try to "increase" dereferenceability due to negative
       // indices as we first have to come up with code to deal with loops and
       // for overflows of the dereferenceable bytes.
       int64_t OffsetSExt = Offset.getSExtValue();
       if (OffsetSExt < 0)
         OffsetSExt = 0;
 

llvm/test/Transforms/Attributor/dereferenceable-1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=16 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -passes=attributor-cgscc --attributor-disable=false -attributor-manifest-internal -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR_NPM
+
+
 ; FIXME: Figure out why we need 16 iterations here.
 
 ; UTC_ARGS: --disable
 
 declare void @deref_phi_user(i32* %a);
 
 ; TEST 1
 ; take mininimum of return values

 
 define void @deref_or_null_and_nonnull(i32* dereferenceable_or_null(100) %0) {
 ; ATTRIBUTOR: define void @deref_or_null_and_nonnull(i32* nocapture nofree nonnull writeonly align 4 dereferenceable(100) %0)
   store i32 1, i32* %0
   ret void
 }
 
 ; UTC_ARGS: --enable
 
-; TEST 8
-; Use Constant range in deereferenceable
+; TEST 8 (positive case)
+; Use constant range in dereferenceable
+
+define void @test8(i8* %ptr) #0 {
+; FIXME: %ptr should be dereferenceable(31)
+; ATTRIBUTOR_NPM: define void @test8(i8* nocapture nofree nonnull writeonly dereferenceable(21) %ptr)
+  br label %1
+1:                                                ; preds = %5, %0
+  %i.0 = phi i32 [ 20, %0 ], [ %4, %5 ]
+  %2 = sext i32 %i.0 to i64
+  %3 = getelementptr inbounds i8, i8* %ptr, i64 %2
+  store i8 32, i8* %3, align 1
+  %4 = add nsw i32 %i.0, 1
+  br label %5
+5:                                                ; preds = %1
+  %6 = icmp slt i32 %4, 30
+  br i1 %6, label %1, label %7
+
+7:                                                ; preds = %5
+  ret void
+}
+; 8.2 (negative case)
+; ATTRIBUTOR_NPM:void @test8_neg
+; ATTRIBUTOR_NPM-NOT: dereferenceable
+; ATTRIBUTOR_NPM-SAME: %ptr
+define void @test8_neg(i32 %i, i8* %ptr) #0 {
+  %1 = sext i32 %i to i64
+  %2 = getelementptr inbounds i8, i8* %ptr, i64 %1
+  store i8 65, i8* %2, align 1
+  ret void
+}
+
 ; void g(int *p, long long int *range){
 ;   int r = *range ; // [10, 99]
 ;   fill_range(p, *range);
 ; }
 
 ; void fill_range(int* p, long long int start){
 ;   for(long long int i = start;i<start+10;i++){
 ;     // If p[i] is inbounds, p is dereferenceable(40) at least.

llvm/test/Transforms/Attributor/willreturn.ll

 ;    for(int i = 0;i<10;i++){
 ;        ans += p[i];
 ;    }
 ;    return ans;
 ; }
 
 ; ATTRIBUTOR_MODULE: Function Attrs: argmemonly nofree noinline nosync nounwind readonly uwtable willreturn
 ; ATTRIBUTOR_CGSCC: Function Attrs: argmemonly nofree noinline norecurse nosync nounwind readonly uwtable willreturn
-; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture nofree readonly %0)
+; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture nofree nonnull readonly dereferenceable(4) %0)
 define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 {
   br label %3
 
 ; <label>:2:                                      ; preds = %3
   ret i32 %8
 
 ; <label>:3:                                      ; preds = %3, %1
   %4 = phi i64 [ 0, %1 ], [ %9, %3 ]
; <label>:8:                                      ; preds = %4, %8
   %13 = load i32, i32* %12, align 4
   %14 = add nsw i32 %13, %10
   %15 = add i32 %9, %3
   %16 = icmp eq i32 %15, %1
   br i1 %16, label %6, label %8
 }
 
 
 ; TEST 13 (positive case)
 ; Function Attrs: norecurse nounwind readonly uwtable
 ;  int loop_trip_dec(int n, int *p){
 ;    int ans = 0;
 ;    for(;n >= 0;n--){
 ;        ans += p[n];
 ;    }
 ;    return ans;
 ;  }