[BasicAA] Don't extend pointer size

[nikic]

Summary

BasicAA GEP decomposition currently performs all calculation on the maximum pointer size, but at least 64-bit, with an option to double the size. The code comment claims that this improves analysis power when working with uint64_t indices on 32-bit systems. However, I don't see how this can be, at least while maintaining correctness:

When working on canonical code, the GEP indices will have GEP index size. If the original code worked on uint64_t with a 32-bit size_t, then there will be truncs inserted before use as a GEP index. Linear expression decomposition does not look through truncs, so this will be an opaque value as far as GEP decomposition is concerned. Working on a wider pointer size does not help here (or have any effect at all).

When working on non-canonical code (before first InstCombine), the GEP indices are implicitly truncated to GEP index size. The BasicAA code currently just ignores this fact completely, and pretends that this truncation doesn't happen. This is incorrect.

I believe that for correctness reasons, it is important to work on the actual GEP index size to properly model potential overflow. BasicAA tries to patch over the fact that it uses the wrong size (see adjustToPointerSize), but it only does that in limited cases (only for constant values, and not all of them either). I'd like to move this code towards always working on the correct size, and dropping these artificial pointer size adjustments is the first step towards that.

[nikic]

Rebase

[fhahn]

When working on non-canonical code (before first InstCombine), the GEP indices are implicitly truncated to GEP index size. The BasicAA code currently just ignores this fact completely, and pretends that this truncation doesn't happen. This is incorrect.

Agreed. For reference, this was added in D38662.

I'd like to move this code towards always working on the correct size, and dropping these artificial pointer size adjustments is the first step towards that.

I tried to add a test showing the issue in 413b7ac6b535, but it still gets it wrong with this patch I think. Do you know which other parts still need adjusting?

[nikic]

In D110657#3035992, @fhahn wrote:

I'd like to move this code towards always working on the correct size, and dropping these artificial pointer size adjustments is the first step towards that.

I tried to add a test showing the issue in 413b7ac6b535, but it still gets it wrong with this patch I think. Do you know which other parts still need adjusting?

We still need to model the actual truncation behavior. Here's my current WIP patch for that: https://gist.github.com/nikic/a9d40f6c739d60e0b6c66ce9edda4363 And there's a few more issues, e.g. our "all positive" code doesn't account for the fact that multiplying / adding positive numbers might make them non-positive.

[nikic]

Rebase over additional test, to show a case this fixes without additional truncation handling.

[fhahn]

LGTM, thanks! Might be good to wait a day or two with landing in case there are any more comments from the people who were involved D38662

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
 
 /// Enable analysis of recursive PHI nodes.
 static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden,
                                           cl::init(true));
 
-/// 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("basic-aa-force-at-least-64b",
-                                        cl::Hidden, cl::init(true));
-static cl::opt<bool> DoubleCalcBits("basic-aa-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

 /// that rely on two's complement wrap-arounds for precise alias information
 /// where the maximum pointer size is 64b.
 static APInt adjustToPointerSize(const 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;
-}
-
 namespace {
 // A linear transformation of a Value; this class represents
 // ZExt(SExt(V, SExtBits), ZExtBits) * Scale.
 struct VariableGEPIndex {
   ExtendedValue Val;
   APInt Scale;
 
   // Context instruction to use when querying information about this index.

 BasicAAResult::DecomposedGEP
 BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                       AssumptionCache *AC, DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
   SearchTimes++;
   const Instruction *CxtI = dyn_cast<Instruction>(V);
 
-  unsigned MaxPointerSize = getMaxPointerSize(DL);
+  unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
   DecomposedGEP Decomposed;
   Decomposed.Offset = APInt(MaxPointerSize, 0);
   Decomposed.HasCompileTimeConstantScale = true;
   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.

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

 ; RUN: opt -S -basic-aa -gvn < %s | FileCheck %s
-; RUN: opt -S -basic-aa -gvn -basic-aa-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)

llvm/test/Analysis/BasicAA/gep-implicit-trunc-32-bit-pointers.ll

 ;
   %gep.1 = getelementptr i8, i8* %ptr, i64 4294967296
   store i8 0, i8* %gep.1
   %gep.2 = getelementptr i8, i8* %ptr, i64 0
   store i8 1, i8* %gep.2
   ret void
 }
 
-; FIXME: This should also be MustAlias as in the previous test.
 define void @mustalias_overflow_in_32_with_var_index([1 x i8]* %ptr, i64 %n) {
 ; CHECK-LABEL: Function: mustalias_overflow_in_32_with_var_index
-; CHECK:       NoAlias:  i8* %gep.1, i8* %gep.2
+; CHECK:       MustAlias: i8* %gep.1, i8* %gep.2
 ;
   %gep.1 = getelementptr [1 x i8], [1 x i8]* %ptr, i64 %n, i64 4294967296
   store i8 0, i8* %gep.1
   %gep.2 = getelementptr [1 x i8], [1 x i8]* %ptr, i64 %n, i64 0
   store i8 1, i8* %gep.2
   ret void
 }