[BasicAA] Fix for missing must alias information

[Gerolf]

Summary

BasicAA performs offset computations in 64b mode independent of the
target. For 32b mode this can result in missing must alias information when
the array offsets wrap-around. The fix checks for the target pointersize and
ensures offsets are computed as 32b offsets for 32b targets.

[reames]

This looks like it should be two separate patches. The mustalias logic should be expressible on 64 bit pointers independent of the wrap around. The 32 bit wrap around logic I'm a bit unclear on. I think that it's correct per the lang ref. At minimum, should be using uint32_t types. Preferably, you'd rephrase this in a generic way which worked for other pointer sizes (i.e. 48 bit?).

[Gerolf]

Philip, thank you for your initial review. This is the general and simplified
version you hinted at. Please take a look.

[reames]

Better, but.. why mask on only some updates vs every one or once at end?

lib/Analysis/BasicAliasAnalysis.cpp

328

Isn't shifting into the sign bit undefined behaviour?

I think what you really want to express is Offset % 0xFF..PointerSize..FF. Why not just write it that way?

461

This line is highly likely wrong. It looks like you're converting to a signed type, doing wrapping there, then converting back. That's suspicious at best.

I suspect you may need to change the signage of the existing code, but that should definitely be separate.

[Gerolf]

Regarding: "Better, but.. why mask on only some updates vs every one or once at end?"

I took the wrap-around out of inner loop and made sure it is done once for each PointerSize. If we can hoist that out of the loop then the BaseOffs wrap can be pushed out of the outer loop also. That requires at least additional checks on the assumption of a constant PointerSize. That needs a separate commit - if any.

lib/Analysis/BasicAliasAnalysis.cpp

328

In C++ (Section 5.8.2) it actually is well defined: The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled.
In older C standards I think at one point it was undefined and later implementation defined when the result did not fit.
And no, for we offset we actually need the sign extension. % doesn't do that.
So I think that code is fine. Agreed?

461

It is "correct" since the bits don't change in that cast: "correct" in the sense of being equivalent to the old code. But I agree with you that this should be an independent commit and take it out.

[Gerolf]

Philip, I removed the wrap for Scale as you suggested.
Please check if you agree with my comments. Thank you!

[llvm-commits]

Aside from the suspected UB (which I think Philip was right about,
see my comments inline below), this seems pretty obviously correct.

A have a couple of other nitpicks below, but after that LGTM.
Philip, did you have anything else on your side?

[reames]

I'm happy to defer to Duncan here.

lib/Analysis/BasicAliasAnalysis.cpp

324

correct -> precise. Very different in this context.

[Gerolf]

Thank you Duncan + Philip! Committed NFC is r259290+r259298, the actual fix is 259299. And you convinced me to finally get rid of my outdated C/C++ standards ... :-)

lib/Analysis/BasicAliasAnalysis.cpp

324

Done: r259300

[reames]

per previous comment from author patches have landed.

lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/Pass.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 using namespace llvm;
 
 /// Enable analysis of recursive PHI nodes.
 static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
                                           cl::init(false));
-
+#define DEBUG_TYPE "basicaa"
 /// SearchLimitReached / SearchTimes shows how often the limit of
 /// to decompose GEPs is reached. It will affect the precision
 /// of basic alias analysis.
-#define DEBUG_TYPE "basicaa"
 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
 /// in a cycle. Because we are analysing 'through' phi nodes we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
     return Result;
   }
 
   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 correct alias information.
+static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
+  assert(PointerSize <= 64 && "Invalide PointerSize!");
+  unsigned ShiftBits = 64 - PointerSize;
+  Offset <<= ShiftBits;
+  return Offset >> ShiftBits;
+}
+
 /// 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.
 ///
do {
 
     // Don't attempt to analyze GEPs over unsized objects.
     if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
       return V;
 
     unsigned AS = GEPOp->getPointerAddressSpace();
     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
     gep_type_iterator GTI = gep_type_begin(GEPOp);
+    unsigned PointerSize = DL.getPointerSizeInBits(AS);
     for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
          I != E; ++I) {
       const Value *Index = *I;
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
         // For a struct, add the member offset.
         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
         if (FieldNo == 0)
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
       }
 
       uint64_t Scale = DL.getTypeAllocSize(*GTI);
       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();
-      unsigned PointerSize = DL.getPointerSizeInBits(AS);
       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;
       Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
                                   SExtBits, DL, 0, AC, DT, NSW, NUW);
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
       if (unsigned ShiftBits = 64 - PointerSize) {
         Scale <<= ShiftBits;
         Scale = (int64_t)Scale >> ShiftBits;
       }
 
       if (Scale) {
         VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
                                   static_cast<int64_t>(Scale)};
         VarIndices.push_back(Entry);
       }
     }
 
+    // Take care of wrap-arounds
+    BaseOffs = adjustToPointerSize(BaseOffs, PointerSize);
     // Analyze the base pointer next.
     V = GEPOp->getOperand(0);
   } while (--MaxLookup);
 
   // If the chain of expressions is too deep, just return early.
   MaxLookupReached = true;
   SearchLimitReached++;
   return V;

test/Analysis/BasicAA/noalias-wraparound-bug.ll

+; RUN: opt -S -basicaa -gvn < %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"
+
+; We incorrectly returned noalias in the example below for "tmp5" and
+; "tmp12" returning i32 32, since basicaa converted the offsets to 64b
+; and missed the wrap-around
+
+define i32 @foo(i8* %buffer) {
+entry:
+  %tmp2 = getelementptr i8, i8* %buffer, i32 -2071408432
+  %tmp3 = bitcast i8* %tmp2 to i32*
+  %tmp4 = getelementptr i8, i8* %buffer, i32 128
+  %tmp5 = bitcast i8* %tmp4 to i32*
+  store i32 32, i32* %tmp5, align 4
+  %tmp12 = getelementptr i32, i32* %tmp3, i32 -1629631508
+  store i32 28, i32* %tmp12, align 4
+  %tmp13 = getelementptr i8, i8* %buffer, i32 128
+  %tmp14 = bitcast i8* %tmp13 to i32*
+  %tmp2083 = load i32, i32* %tmp14, align 4
+; CHECK: ret i32 28
+  ret i32 %tmp2083
+}