[BasicAA] Support arbitrary pointer sizes (and fix an overflow bug)

[hfinkel]

Summary

Motivated by the discussion in D38499, this patch updates BasicAA to support arbitrary pointer sizes by switching most remaining non-APInt calculations to use APInt. The size of these APInts is set to the maximum pointer size (maximum over all address spaces described by the data layout string).

Most of this translation is straightforward (although needs to be checked carefully), but this patch contains a fix for a bug that revealed itself during this translation process. In order for test/Analysis/BasicAA/gep-and-alias.ll to pass, which is run with 32-bit pointers, the intermediate calculations must be performed using 64-bit integers. This is because, as noted in the patch, when GetLinearExpression decomposes an expression into C1*V+C2, and we then multiply this by Scale, and distribute, to get (C1*Scale)*V + C2*Scale, it can be the case that, even through C1*V+C2 does not overflow for relevant values of V, (C2*Scale) can overflow. If this happens, later logic will draw invalid conclusions from the (base) offset value. Thus, when initially applying the APInt conversion, because the maximum pointer size in this test is 32 bits, it started failing. Suspicious, I created a 64-bit version of this test (included here), and that failed (miscompiled) on trunk for a similar reason (the multiplication can overflow).

After fixing this overflow bug, the first test case (at least) in Analysis/BasicAA/q.bad.ll started failing. This is also a 32-bit test, and was relying on having 64-bit intermediate values to have BasicAA return an accurate result. In order to fix this problem, and because I believe that it is not uncommon to use i64 indexing expressions in 32-bit code (especially portable code using int64_t), it seems reasonable to always use at least 64-bit integers. In this way, we won't regress our analysis capabilities (and there's a command-line option added, so experimenting with this should be easy).

This should also fix the problem motivating D38499. Michael, can you please test this, improve the test case from D38499 so it can included, and generate additional test cases if possible for extra-large pointers.

Please review.

[efriedma]

because I believe that it is not uncommon to use i64 indexing expressions in 32-bit code

Whether or not that's true at the source-code level, it's should be uncommon at the IR level; instcombine will canonicalize GEP indexing to use pointer-width values.

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

I'm not sure I understand this comment.

It's true that C2*Scale can overflow, but I'm not sure it makes sense to try to address that here. The multiply by the scale can overflow no matter where the scale comes from (assuming the GEP isn't marked inbounds).

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

Can you please elaborate?

If this overflows, then the offset here isn't an offset, and the reasoning done later won't be correct.

In the test case, the GEPs are marked as inbounds. I don't think that's relevant here.

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

Consider the following testcase:

target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
define i32* @b1(i32 *%a) {
%r = getelementptr i32, i32* %a, i32 -2147483648
ret i32* %r
}
define i32* @b2(i32 *%a) {
%o = add i32 -2147483648, 0
%r = getelementptr i32, i32* %a, i32 %o
ret i32* %r
}

In both cases, %a and %r should be mustalias. If you run "-aa-eval", we somehow conclude that the pointers are mustalias in b1, and noalias in b2. If you're trying to make overflow well-behaved, it doesn't make sense to treat the overflow introduced by GetLinearExpression differently from the overflow inherent in scaling.

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

I agree, however, as I attempted to explain in the comment:

1. The problem is not in GetLinearExpression itself, it is with how the results of GetLinearExpression are being used here.
2. What's happening here, where we're multiplying by the scale (which by itself is always fine), and applying the distributive property, can introduce an overflow in cases where an overflow might not have existed in the original program.

I believe that the test cases demonstrate this: there are certainly values for the function parameters for which they'll be no overflow in the address calculations.

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

I think aliasGEP needs to be changed to accept that decompsed GEP arithmetic will overflow, or somehow adopt much more restrictive overflow checking (in many more places than this patch does).

---

Suppose we want to adopt more restrictive overflow checking. First, so we have an expression (C1*V+C2)*Scale. If we treat (C1*V+C2) as opaque, there's one place this can overflow: the multiply by Scale. Currently, we completely ignore this possibility.

So now, instead of treating the inner expression as opaque, we want to decompose it to something like (C1*Scale)*V+C2*Scale. There are four arithmetic operations here. All four of them can potentially overflow. And two of them can't be overflow-checked here because V isn't known at compile-time.

Given that, I don't see how overflow-checking C2 * Scale accomplishes anything except hiding the problem for your exact testcase.

[mppf]

@hfinkel - I'm obviously not your main reviewer, but I did spend a few minutes looking at this.

First, it appears that this changeset addresses the problem I was having. I'm running in to a new problem with 128-bit pointers when using trunk (vs LLVM 4 or 5) which I'll suggest a fix for / bug report once I've got something minimized. I'll be working on that as well as generating a better test case for this BasicAA issue.

Thanks!

lib/Analysis/BasicAliasAnalysis.cpp

379 ↗

(On Diff #118126)

This is meant to just take the bottom PointerSize bits. Shouldn't you use APInt.trunc to express it more simply?

387 ↗

(On Diff #118126)

I find it surprising that you needed to do this, but I don't have a great understanding of what's going on. In the change description, you pointed out

This is because, as noted in the patch, when GetLinearExpression decomposes an expression into C1*V+C2, and we then multiply this by Scale, and distribute, to get (C1*Scale)*V + C2*Scale, it can be the case that, even through C1*V+C2 does not overflow for relevant values of V, (C2*Scale) can overflow. If this happens, later logic will draw invalid conclusions from the (base) offset value.

Can you explain why it's not sufficient to do these computations in the number ring for the GEP? E.g. if all GEPs were with 32-bit pointers, mathematically the distribution should work if everything is done with 32-bit numbers, including with overflow. And the LLVM spec says that is what these GEPs mean...

Is it just that the alias analysis pass then conservatively throws up its hands if overflow occurred? Or is it the case that the computations done here might cross different pointer sizes?

492 ↗

(On Diff #118126)

I'm probably missing something, but isn't .sextOrSelf(x).sextOrTrunc(x) going to do the same thing as .sextOrTrunc(x) ?

553 ↗

(On Diff #118126)

I've never seen !! used like this before. Is it intentional? Is it the same as if (Scale != 0) ? If so, wouldn't that be clearer?

1098 ↗

(On Diff #118126)

This addition seems surprising to me. Why wouldn't we just use APInt for the computation below? Is this a workaround for something?

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

379 ↗

(On Diff #118126)

Yes, where the result is sign extended. We can't just trunc the APInt, however, or its size will be wrong (I believe that this function ends up dealing with cases where we're dealing with a pointer size that'smaller than the maximum/initial one).

You're right, however, that writing Offset.trunc(PointerSize).sextOrSelf(PrevBitWidth) would be clearer.

387 ↗

(On Diff #118126)

I don't have a great answer to this question, but I can say that some of the logic here doesn't work if we assume that we're working mod 2^n. For one thing, I think that makes it very hard to do any kind of relational comparisons. a < b does not have a useful meaning if a and b are both really congruence classes (i.e., if all we know is that a is really a + k*2^n, for some k, and b is really b + j*2^n, for some j, then it's impossible to conclude which number is greater or smaller than some other).

As I recall, we were specifically running into a issue with this check:

// 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) && GEP1BaseOffset.uge(V2Size))
  return NoAlias;

The GEP1BaseOffset > 0 isn't something you can meaningfully do if all we know is the value is some element of its congruence class (because, in that case, all numbers are positive and negative). The other comparison has this problem too.

492 ↗

(On Diff #118126)

I think you've overlooked one parenthesis.

I'm trying to match the original code here, so I'm sign extending CIdx before the multiplication. It seemed like the result of the multiplication may have returned a 64-bit APInt (even if it was originally 32-bits), and so in that case, we need to truncate again (and there is no truncOrSelf). Looking through the APInt source code, I can't explain that behavior, so I'll look at this again.

519 ↗

(On Diff #118126)

I think aliasGEP needs to be changed to accept that decompsed GEP arithmetic will overflow, or somehow adopt much more restrictive overflow checking (in many more places than this patch does).

I think that it does need to be changed, but if we can fix it like this, that probably preserves our optimization abilities. Changing it in other ways, AFAIKT, will weaken it (perhaps unnecessarily). The only other place I see that might have this issue (introducing new compile-time overflows) is in BasicAAResult::constantOffsetHeuristic. There may, however, be a more-general problem...

If we treat (C1*V+C2) as opaque, there's one place this can overflow: the multiply by Scale. Currently, we completely ignore this possibility.

If it is opaque, then it is just a value (regardless of whether or not its computation depended on some overflowing result). Is there something we'd need to do?

So now, instead of treating the inner expression as opaque, we want to decompose it to something like (C1*Scale)*V+C2*Scale. There are four arithmetic operations here. All four of them can potentially overflow. And two of them can't be overflow-checked here because V isn't known at compile-time.

When I looked at this previously, my thought had been that only the C2*Scale overflow could happen in well-defined code. I may have been wrong about that. The issue is that if C1*Scale overflows then C1*V is likely to overflow in the original program. That, however, is clearly not necessarily true. So, yes, I agree, we should check that too.

Then there's the other two operations. They, indeed, might overflow. I don't see anything to prevent them from overflowing even if the original expression did not (essentially in some cases where |V| < Scale and |C1|,|C2| are large in the right ways). In the face of such overflows, the decomposition may not be sound, unfortunately.

Given that, I don't see how overflow-checking C2 * Scale accomplishes anything except hiding the problem for your exact testcase.

This may be a fair criticism. I think that the general problem of dealing with overflows is going to need a careful audit and a lot of changes. There's a lot of logic here that likely isn't completely sound. However, I don't want to make things worse, certainly, and this was a pre-existing regression test. I should check for C1*Scale overflow too (to avoid making anything worse).

More-general pre-existing problems, however, I'd recommend treating as orthogonal to this change. I think that more-consistently using APInts makes addressing these problems easier, not harder, in follow-up work.

553 ↗

(On Diff #118126)

Yea, it's intentional. IIRC, APInt does not have a Boolean conversion. This is used other places in LLVM's codebase.

1098 ↗

(On Diff #118126)

Ah, sort of. Updating StructLayout::getElementOffset to take an APInt does not seem worthwhile. You're right, however: this is the wrong test. It should say:

if (C1->getActiveBits() > 64 || C2->getActiveBits() > 64)

[mppf]

First, it appears that this changeset addresses the problem I was having. I'm running in to a new problem with 128-bit pointers when using trunk (vs LLVM 4 or 5) which I'll suggest a fix for / bug report once I've got something minimized. I'll be working on that as well as generating a better test case for this BasicAA issue.

@hfinkel fyi, the new problem I mentioned (since LLVM 5) appears to be due to D37460. It actually doesn't have anything to do with 128-bit pointers. I'll comment on that (closed) review to bring up the issue, but let me know if a different action is more appropriate. Thanks!

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

I think that more-consistently using APInts makes addressing these problems easier, not harder, in follow-up work.

Okay, this makes sense.

[mppf]

This change is still important to me. What needs to happen next for it to make progress? Thanks!

[greened]

I read through the comments and it seems like everything has been addressed. Does anything more need to happen to have this land?

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

519 ↗

(On Diff #118126)

This still needs to be updated (at least, the comment needs to change).

1098 ↗

(On Diff #118126)

This still needs to be updated.

[mppf]

Note that this commit is related:

commit 4b3289612268b4fbbf578256a15d31e3f5033003
Author: Davide Italiano <[e-mail]>
Date: Mon Jan 15 01:40:18 2018 +0000

[BasicAA] Stop crashing when dealing with pointers > 64 bits.

An alternative (and probably better) fix would be that of
making `Scale` an APInt, and there's a patch floating around
to do this. As we're still discussing it, at least stop crashing
in the meanwhile (added bonus, we now have a regression test for
this situation).

Fixes PR35843.

Thanks to Eli for suggesting the fix and Simon for reporting and
reducing the bug.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@322467 91177308-0d34-0410-b5e6-96231b3b80d8

[mppf]

Updating to LLVM master, fix comment, fix a check, add a test

[mppf]

Fixing compilation problem. Now passes check-llvm.

[mppf]

I think this patch is updated and ready to go. I'v additionally confirmed that this patch resolves the issue (present on LLVM master) with the test in D38501.

[mppf]

hey @efriedma - @hfinkel and I are wondering if you have any comments on this updated revision of BasicAA improvements. Thanks!

[hfinkel]

In D38662#1290796, @mppf wrote:

hey @efriedma - @hfinkel and I are wondering if you have any comments on this updated revision of BasicAA improvements. Thanks!

I think that we can move forward with this. Thanks for updating. It's not a complete solution (as Eli has pointed out), but does improve the status quo. LGTM.

[xbolva00]

Maybe this commit is responsible for big slowdown in AARCH64 LTO?

https://lnt.llvm.org/db_default/v4/nts/119000

rL350219 and rL350221 could not cause it.

llvm/trunk/include/llvm/Analysis/BasicAliasAnalysis.h

struct VariableGEPIndex {
 
     // We need to track what extensions we've done as we consider the same Value
     // with different extensions as different variables in a GEP's linear
     // expression;
     // e.g.: if V == -1, then sext(x) != zext(x).
     unsigned ZExtBits;
     unsigned SExtBits;
 
-    int64_t Scale;
+    APInt Scale;
 
     bool operator==(const VariableGEPIndex &Other) const {
       return V == Other.V && ZExtBits == Other.ZExtBits &&
              SExtBits == Other.SExtBits && Scale == Other.Scale;
     }
 
     bool operator!=(const VariableGEPIndex &Other) const {
       return !operator==(Other);
     }
   };
 
   // Represents the internal structure of a GEP, decomposed into a base pointer,
   // constant offsets, and variable scaled indices.
   struct DecomposedGEP {
     // Base pointer of the GEP
     const Value *Base;
     // Total constant offset w.r.t the base from indexing into structs
-    int64_t StructOffset;
+    APInt StructOffset;
     // Total constant offset w.r.t the base from indexing through
     // pointers/arrays/vectors
-    int64_t OtherOffset;
+    APInt OtherOffset;
     // Scaled variable (non-constant) indices.
     SmallVector<VariableGEPIndex, 4> VarIndices;
   };
 
   /// Track alias queries to guard against recursion.
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheTy = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheTy AliasCache;
private:
   /// 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.
   bool
   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
                           LocationSize V1Size, LocationSize V2Size,
-                          int64_t BaseOffset, AssumptionCache *AC,
+                          APInt BaseOffset, AssumptionCache *AC,
                           DominatorTree *DT);
 
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                           const SmallVectorImpl<VariableGEPIndex> &Src);
 
   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,

llvm/trunk/include/llvm/IR/DataLayout.h

public:
   /// the backends/clients are updated.
   unsigned getPointerPrefAlignment(unsigned AS = 0) const;
 
   /// Layout pointer size
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   unsigned getPointerSize(unsigned AS = 0) const;
 
+  /// Returns the maximum pointer size over all address spaces.
+  unsigned getMaxPointerSize() const;
+
   // Index size used for address calculation.
   unsigned getIndexSize(unsigned AS) const;
 
   /// Return the address spaces containing non-integral pointers.  Pointers in
   /// this address space don't have a well-defined bitwise representation.
   ArrayRef<unsigned> getNonIntegralAddressSpaces() const {
     return NonIntegralAddressSpaces;
   }
public:
 
   /// Layout pointer size, in bits
   /// FIXME: The defaults need to be removed once all of
   /// the backends/clients are updated.
   unsigned getPointerSizeInBits(unsigned AS = 0) const {
     return getPointerSize(AS) * 8;
   }
 
+  /// Returns the maximum pointer size over all address spaces.
+  unsigned getMaxPointerSizeInBits() const {
+    return getMaxPointerSize() * 8;
+  }
+
   /// Size in bits of index used for address calculation in getelementptr.
   unsigned getIndexSizeInBits(unsigned AS) const {
     return getIndexSize(AS) * 8;
   }
 
   /// Layout pointer size, in bits, based on the type.  If this function is
   /// called with a pointer type, then the type size of the pointer is returned.
   /// If this function is called with a vector of pointers, then the type size

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

 
 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
 
 /// Enable analysis of recursive PHI nodes.
 static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
                                           cl::init(false));
+
+/// By default, even on 32-bit architectures we use 64-bit integers for
+/// calculations. This will allow us to more-aggressively decompose indexing
+/// expressions calculated using i64 values (e.g., long long in C) which is
+/// common enough to worry about.
+static cl::opt<bool> ForceAtLeast64Bits("basicaa-force-at-least-64b",
+                                        cl::Hidden, cl::init(true));
+static cl::opt<bool> DoubleCalcBits("basicaa-double-calc-bits",
+                                    cl::Hidden, cl::init(false));
+
 /// SearchLimitReached / SearchTimes shows how often the limit of
 /// to decompose GEPs is reached. It will affect the precision
 /// of basic alias analysis.
 STATISTIC(SearchLimitReached, "Number of times the limit to "
                               "decompose GEPs is reached");
 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
 
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
/*static*/ const Value *BasicAAResult::GetLinearExpression(
   }
 
   Scale = 1;
   Offset = 0;
   return V;
 }
 
 /// To ensure a pointer offset fits in an integer of size PointerSize
-/// (in bits) when that size is smaller than 64. This is an issue in
-/// particular for 32b programs with negative indices that rely on two's
-/// complement wrap-arounds for precise alias information.
-static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
-  assert(PointerSize <= 64 && "Invalid PointerSize!");
-  unsigned ShiftBits = 64 - PointerSize;
-  return (int64_t)((uint64_t)Offset << ShiftBits) >> ShiftBits;
+/// (in bits) when that size is smaller than the maximum pointer size. This is
+/// an issue, for example, in particular for 32b pointers with negative indices
+/// that rely on two's complement wrap-arounds for precise alias information
+/// where the maximum pointer size is 64b.
+static APInt adjustToPointerSize(APInt Offset, unsigned PointerSize) {
+  assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!");
+  unsigned ShiftBits = Offset.getBitWidth() - PointerSize;
+  return (Offset << ShiftBits).ashr(ShiftBits);
+}
+
+static unsigned getMaxPointerSize(const DataLayout &DL) {
+  unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
+  if (MaxPointerSize < 64 && ForceAtLeast64Bits) MaxPointerSize = 64;
+  if (DoubleCalcBits) MaxPointerSize *= 2;
+
+  return MaxPointerSize;
 }
 
 /// If V is a symbolic pointer expression, decompose it into a base pointer
 /// with a constant offset and a number of scaled symbolic offsets.
 ///
 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
 /// specified amount, but which may have other unrepresented high bits. As
 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
 ///
 /// When DataLayout is around, this function is capable of analyzing everything
 /// that GetUnderlyingObject can look through. To be able to do that
 /// GetUnderlyingObject and DecomposeGEPExpression must use the same search
 /// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
 /// through pointer casts.
 bool BasicAAResult::DecomposeGEPExpression(const Value *V,
        DecomposedGEP &Decomposed, const DataLayout &DL, AssumptionCache *AC,
        DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
   SearchTimes++;
 
-  Decomposed.StructOffset = 0;
-  Decomposed.OtherOffset = 0;
+  unsigned MaxPointerSize = getMaxPointerSize(DL);
   Decomposed.VarIndices.clear();
   do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (!Op) {
       // The only non-operator case we can handle are GlobalAliases.
       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
         if (!GA->isInterposable()) {
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         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()) * CIdx->getSExtValue();
+          (DL.getTypeAllocSize(GTI.getIndexedType()) *
+            CIdx->getValue().sextOrSelf(MaxPointerSize))
+              .sextOrTrunc(MaxPointerSize);
         continue;
       }
 
       GepHasConstantOffset = false;
 
-      uint64_t Scale = DL.getTypeAllocSize(GTI.getIndexedType());
+      APInt Scale(MaxPointerSize, DL.getTypeAllocSize(GTI.getIndexedType()));
       unsigned ZExtBits = 0, SExtBits = 0;
 
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       if (PointerSize > Width)
         SExtBits += PointerSize - Width;
 
       // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
       bool NSW = true, NUW = true;
+      const Value *OrigIndex = Index;
       Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
                                   SExtBits, DL, 0, AC, DT, NSW, NUW);
 
-      // All GEP math happens in the width of the pointer type,
-      // so we can truncate the value to 64-bits as we don't handle
-      // currently pointers larger than 64 bits and we would crash
-      // later. TODO: Make `Scale` an APInt to avoid this problem.
-      if (IndexScale.getBitWidth() > 64)
-        IndexScale = IndexScale.sextOrTrunc(64);
-
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
-      Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
-      Scale *= IndexScale.getSExtValue();
+
+      // It can be the case that, even through C1*V+C2 does not overflow for
+      // relevant values of V, (C2*Scale) can overflow. In that case, we cannot
+      // decompose the expression in this way.
+      //
+      // FIXME: C1*Scale and the other operations in the decomposed
+      // (C1*Scale)*V+C2*Scale can also overflow. We should check for this
+      // possibility.
+      APInt WideScaledOffset = IndexOffset.sextOrTrunc(MaxPointerSize*2) *
+                                 Scale.sext(MaxPointerSize*2);
+      if (WideScaledOffset.getMinSignedBits() > MaxPointerSize) {
+        Index = OrigIndex;
+        IndexScale = 1;
+        IndexOffset = 0;
+
+        ZExtBits = SExtBits = 0;
+        if (PointerSize > Width)
+          SExtBits += PointerSize - Width;
+      } else {
+        Decomposed.OtherOffset += IndexOffset.sextOrTrunc(MaxPointerSize) * 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) {
         if (Decomposed.VarIndices[i].V == Index &&
             Decomposed.VarIndices[i].ZExtBits == ZExtBits &&
             Decomposed.VarIndices[i].SExtBits == SExtBits) {
           Scale += Decomposed.VarIndices[i].Scale;
           Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
           break;
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
       Scale = adjustToPointerSize(Scale, PointerSize);
 
-      if (Scale) {
-        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
-                                  static_cast<int64_t>(Scale)};
+      if (!!Scale) {
+        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
     if (GepHasConstantOffset) {
       Decomposed.StructOffset =
           adjustToPointerSize(Decomposed.StructOffset, PointerSize);
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
 
   ConstantInt *C1 =
       dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
   ConstantInt *C2 =
       dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
 
   // If the last (struct) indices are constants and are equal, the other indices
   // might be also be dynamically equal, so the GEPs can alias.
-  if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
+  if (C1 && C2) {
+    unsigned BitWidth = std::max(C1->getBitWidth(), C2->getBitWidth());
+    if (C1->getValue().sextOrSelf(BitWidth) ==
+        C2->getValue().sextOrSelf(BitWidth))
       return MayAlias;
+  }
 
   // Find the last-indexed type of the GEP, i.e., the type you'd get if
   // you stripped the last index.
   // On the way, look at each indexed type.  If there's something other
   // than an array, different indices can lead to different final types.
   SmallVector<Value *, 8> IntermediateIndices;
 
   // Insert the first index; we don't need to check the type indexed
if (C1 && C2)
       } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
         return NoAlias;
     }
     return MayAlias;
   } else if (!LastIndexedStruct || !C1 || !C2) {
     return MayAlias;
   }
 
+  if (C1->getValue().getActiveBits() > 64 ||
+      C2->getValue().getActiveBits() > 64)
+    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;
   // - said indices are different, hence, the pointed-to fields are different;
   // - both GEPs only index through arrays prior to that.
   //
   // This lets us determine that the struct that GEP1 indexes into and the
   // struct that GEP2 indexes into must either precisely overlap or be
bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
   // We need the object to be an alloca or a globalvariable, and want to know
   // the offset of the pointer from the object precisely, so no variable
   // indices are allowed.
   if (!(isa<AllocaInst>(DecompObject.Base) ||
         isa<GlobalVariable>(DecompObject.Base)) ||
       !DecompObject.VarIndices.empty())
     return false;
 
-  int64_t ObjectBaseOffset = DecompObject.StructOffset +
-                             DecompObject.OtherOffset;
+  APInt ObjectBaseOffset = DecompObject.StructOffset +
 
   // If the GEP has no variable indices, we know the precise offset
   // from the base, then use it. If the GEP has variable indices,
   // we can't get exact GEP offset to identify pointer alias. So return
   // false in that case.
   if (!DecompGEP.VarIndices.empty())
     return false;
-  int64_t GEPBaseOffset = DecompGEP.StructOffset;
+
+  APInt GEPBaseOffset = DecompGEP.StructOffset;
   GEPBaseOffset += DecompGEP.OtherOffset;
 
-  return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
+  return GEPBaseOffset.sge(ObjectBaseOffset + (int64_t)ObjectAccessSize);
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
 /// another pointer.
 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
 /// V2.
 AliasResult
 BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
                         const AAMDNodes &V1AAInfo, const Value *V2,
                         LocationSize V2Size, const AAMDNodes &V2AAInfo,
                         const Value *UnderlyingV1, const Value *UnderlyingV2) {
   DecomposedGEP DecompGEP1, DecompGEP2;
+  unsigned MaxPointerSize = getMaxPointerSize(DL);
+  DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
+  DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
+
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
   bool GEP2MaxLookupReached =
     DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
-  int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
-  int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
+  APInt GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
+  APInt GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
 
   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.
BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size,
   if (GEP1BaseOffset == 0 && DecompGEP1.VarIndices.empty())
     return MustAlias;
 
   // If there is a constant difference between the pointers, but the difference
   // is less than the size of the associated memory object, then we know
   // that the objects are partially overlapping.  If the difference is
   // greater, we know they do not overlap.
   if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
-    if (GEP1BaseOffset >= 0) {
+    if (GEP1BaseOffset.sge(0)) {
       if (V2Size != LocationSize::unknown()) {
-        if ((uint64_t)GEP1BaseOffset < V2Size.getValue())
+        if (GEP1BaseOffset.ult(V2Size.getValue()))
           return PartialAlias;
         return NoAlias;
       }
     } else {
       // We have the situation where:
       // +                +
       // | BaseOffset     |
       // ---------------->|
       // |-->V1Size       |-------> V2Size
       // GEP1             V2
       // We need to know that V2Size is not unknown, otherwise we might have
       // stripped a gep with negative index ('gep <ptr>, -1, ...).
       if (V1Size != LocationSize::unknown() &&
           V2Size != LocationSize::unknown()) {
-        if (-(uint64_t)GEP1BaseOffset < V1Size.getValue())
+        if ((-GEP1BaseOffset).ult(V1Size.getValue()))
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
-    uint64_t Modulo = 0;
+    APInt Modulo(MaxPointerSize, 0);
     bool AllPositive = true;
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
 
       // Try to distinguish something like &A[i][1] against &A[42][0].
       // Grab the least significant bit set in any of the scales. We
       // don't need std::abs here (even if the scale's negative) as we'll
       // be ^'ing Modulo with itself later.
-      Modulo |= (uint64_t)DecompGEP1.VarIndices[i].Scale;
+      Modulo |= DecompGEP1.VarIndices[i].Scale;
 
       if (AllPositive) {
         // If the Value could change between cycles, then any reasoning about
         // the Value this cycle may not hold in the next cycle. We'll just
         // give up if we can't determine conditions that hold for every cycle:
         const Value *V = DecompGEP1.VarIndices[i].V;
 
         KnownBits Known = computeKnownBits(V, DL, 0, &AC, nullptr, DT);
         bool SignKnownZero = Known.isNonNegative();
         bool SignKnownOne = Known.isNegative();
 
         // Zero-extension widens the variable, and so forces the sign
         // bit to zero.
         bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
         SignKnownZero |= IsZExt;
         SignKnownOne &= !IsZExt;
 
         // If the variable begins with a zero then we know it's
         // positive, regardless of whether the value is signed or
         // unsigned.
-        int64_t Scale = DecompGEP1.VarIndices[i].Scale;
+        APInt Scale = DecompGEP1.VarIndices[i].Scale;
         AllPositive =
-            (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
+            (SignKnownZero && Scale.sge(0)) || (SignKnownOne && Scale.slt(0));
       }
     }
 
     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses
     // mod Modulo. Check whether that difference guarantees that the
     // two locations do not alias.
-    uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
+    APInt ModOffset = GEP1BaseOffset & (Modulo - 1);
     if (V1Size != LocationSize::unknown() &&
-        V2Size != LocationSize::unknown() && ModOffset >= V2Size.getValue() &&
-        V1Size.getValue() <= Modulo - ModOffset)
+        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 > 0 &&
+    if (AllPositive && GEP1BaseOffset.sgt(0) &&
         V2Size != LocationSize::unknown() &&
-        V2Size.getValue() <= (uint64_t)GEP1BaseOffset)
+        GEP1BaseOffset.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
void BasicAAResult::GetIndexDifference(
     SmallVectorImpl<VariableGEPIndex> &Dest,
     const SmallVectorImpl<VariableGEPIndex> &Src) {
   if (Src.empty())
     return;
 
   for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     const Value *V = Src[i].V;
     unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
-    int64_t Scale = Src[i].Scale;
+    APInt Scale = Src[i].Scale;
 
     // Find V in Dest.  This is N^2, but pointer indices almost never have more
     // than a few variable indexes.
     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
       if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
           Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
         continue;
 
       // If we found it, subtract off Scale V's from the entry in Dest.  If it
       // goes to zero, remove the entry.
       if (Dest[j].Scale != Scale)
         Dest[j].Scale -= Scale;
       else
         Dest.erase(Dest.begin() + j);
       Scale = 0;
       break;
     }
 
     // If we didn't consume this entry, add it to the end of the Dest list.
-    if (Scale) {
+    if (!!Scale) {
       VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
       Dest.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices,
-    LocationSize MaybeV1Size, LocationSize MaybeV2Size, int64_t BaseOffset,
+    LocationSize MaybeV1Size, LocationSize MaybeV2Size, APInt BaseOffset,
     AssumptionCache *AC, DominatorTree *DT) {
   if (VarIndices.size() != 2 || MaybeV1Size == LocationSize::unknown() ||
       MaybeV2Size == LocationSize::unknown())
     return false;
 
   const uint64_t V1Size = MaybeV1Size.getValue();
   const uint64_t V2Size = MaybeV2Size.getValue();
 
bool BasicAAResult::constantOffsetHeuristic(
 
   // If we've been sext'ed then zext'd the maximum difference between Var0 and
   // Var1 is possible to calculate, but we're just interested in the absolute
   // minimum difference between the two. The minimum distance may occur due to
   // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
   // the minimum distance between %i and %i + 5 is 3.
   APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
   MinDiff = APIntOps::umin(MinDiff, Wrapped);
-  uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
+  APInt MinDiffBytes =
+    MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs();
 
   // We can't definitely say whether GEP1 is before or after V2 due to wrapping
   // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
   // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
   // V2Size can fit in the MinDiffBytes gap.
-  return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
-         V2Size + std::abs(BaseOffset) <= MinDiffBytes;
+  return MinDiffBytes.uge(V1Size + BaseOffset.abs()) &&
+         MinDiffBytes.uge(V2Size + BaseOffset.abs());
 }
 
 //===----------------------------------------------------------------------===//
 // BasicAliasAnalysis Pass
 //===----------------------------------------------------------------------===//
 
 AnalysisKey BasicAA::Key;
 

llvm/trunk/lib/IR/DataLayout.cpp

unsigned DataLayout::getPointerSize(unsigned AS) const {
   PointersTy::const_iterator I = findPointerLowerBound(AS);
   if (I == Pointers.end() || I->AddressSpace != AS) {
     I = findPointerLowerBound(0);
     assert(I->AddressSpace == 0);
   }
   return I->TypeByteWidth;
 }
 
+unsigned DataLayout::getMaxPointerSize() const {
+  unsigned MaxPointerSize = 0;
+  for (auto &P : Pointers)
+    MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
+
+  return MaxPointerSize;
+}
+
 unsigned DataLayout::getPointerTypeSizeInBits(Type *Ty) const {
   assert(Ty->isPtrOrPtrVectorTy() &&
          "This should only be called with a pointer or pointer vector type");
   Ty = Ty->getScalarType();
   return getPointerSizeInBits(cast<PointerType>(Ty)->getAddressSpace());
 }
 
 unsigned DataLayout::getIndexSize(unsigned AS) const {

llvm/trunk/test/Analysis/BasicAA/128-bit-ptr.ll

+; This testcase consists of alias relations on 128-bit pointers that
+; should be completely resolvable by basicaa.
+
+; RUN: opt < %s -basicaa -aa-eval -print-no-aliases -print-may-aliases -print-must-aliases -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-i128:128:128-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128-p100:128:64:64-p101:128:64:64"
+
+
+; test0 is similar to SimpleCases.ll
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test0
+; CHECK-NOT:   MayAlias:
+define void @test0(%T addrspace(100)* %P) {
+  %A = getelementptr %T, %T addrspace(100)* %P, i64 0
+  %B = getelementptr %T, %T addrspace(100)* %P, i64 0, i32 0
+  %C = getelementptr %T, %T addrspace(100)* %P, i64 0, i32 1
+  %D = getelementptr %T, %T addrspace(100)* %P, i64 0, i32 1, i64 0
+  %E = getelementptr %T, %T addrspace(100)* %P, i64 0, i32 1, i64 5
+  ret void
+}
+
+; test1 checks that >64 bits of index can be considered.
+; If BasicAA is truncating the arithmetic, it will conclude
+; that %A and %B must alias when in fact they must not.
+
+; CHECK:     Function: test1
+; CHECK-NOT:   MustAlias:
+; CHECK:       NoAlias:
+; CHECK-SAME:  %A
+; CHECK-SAME:  %B
+define void @test1(double addrspace(100)* %P, i128 %i) {
+  ; 1180591620717411303424 is 2**70
+  ;  590295810358705651712 is 2**69
+  %i70 = add i128 %i, 1180591620717411303424 
+  %i69 = add i128 %i, 590295810358705651712
+  %A = getelementptr double, double addrspace(100)* %P, i128 %i70
+  %B = getelementptr double, double addrspace(100)* %P, i128 %i69
+  ret void
+}
+
+; test2 checks that >64 bits of index can be considered
+; and computes the same address in two ways to ensure that
+; they are considered equivalent.
+
+; CHECK: Function: test2
+; CHECK: MustAlias:
+; CHECK-SAME: %A
+; CHECK-SAME: %C
+define void @test2(double addrspace(100)* %P, i128 %i) {
+  ; 1180591620717411303424 is 2**70
+  ;  590295810358705651712 is 2**69
+  %i70 = add i128 %i, 1180591620717411303424 
+  %i69 = add i128 %i, 590295810358705651712
+  %j70 = add i128 %i69, 590295810358705651712 
+  %A = getelementptr double, double addrspace(100)* %P, i128 %i70
+  %C = getelementptr double, double addrspace(100)* %P, i128 %j70
+  ret void
+}

llvm/trunk/test/Analysis/BasicAA/gep-and-alias-64.ll

+; RUN: opt -S -basicaa -gvn < %s | FileCheck %s
+
+target datalayout = "e-m:o-p:64:64-f64:32:64-f80:128-n8:16:32-S128"
+target triple = "x86_64-apple-macosx10.6.0"
+
+; The load and store address in the loop body could alias so the load
+; can't be hoisted above the store and out of the loop.
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
+
+define i64 @foo(i64 %x, i64 %z, i64 %n) {
+entry:
+  %pool = alloca [59 x i64], align 4
+  %tmp = bitcast [59 x i64]* %pool to i8*
+  call void @llvm.memset.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
+  %cmp3 = icmp eq i64 %n, 0
+  br i1 %cmp3, label %for.end, label %for.body.lr.ph
+
+for.body.lr.ph:                                   ; preds = %entry
+  %add = add i64 %z, %x
+  %and = and i64 %add, 9223372036854775807
+  %sub = add nsw i64 %and, -9223372036844814062
+  %arrayidx = getelementptr inbounds [59 x i64], [59 x i64]* %pool, i64 0, i64 %sub
+  %arrayidx1 = getelementptr inbounds [59 x i64], [59 x i64]* %pool, i64 0, i64 42
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.04 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  store i64 %i.04, i64* %arrayidx, align 4
+  %tmp1 = load i64, i64* %arrayidx1, align 4
+  %inc = add nuw i64 %i.04, 1
+  %exitcond = icmp ne i64 %inc, %n
+  br i1 %exitcond, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  %lcssa = phi i64 [ %tmp1, %for.body ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %s = phi i64 [ 0, %entry ], [ %lcssa, %for.end.loopexit ]
+; CHECK: ret i64 %s
+  ret i64 %s
+}

llvm/trunk/test/Analysis/BasicAA/gep-and-alias.ll

 ; RUN: opt -S -basicaa -gvn < %s | FileCheck %s
+; RUN: opt -S -basicaa -gvn -basicaa-force-at-least-64b=0 < %s | FileCheck %s
 
 target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
 target triple = "i386-apple-macosx10.6.0"
 
 ; The load and store address in the loop body could alias so the load
 ; can't be hoisted above the store and out of the loop.
 
 declare void @llvm.memset.p0i8.i32(i8* nocapture writeonly, i8, i32, i1)