[BasicAA] Use index size instead of pointer size

[nikic]

Summary

When accumulating the GEP offset in BasicAA, we should use the pointer index size rather than the pointer size.

[reames]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

552

The use of maximum pointer/index size seems suspect here. Shouldn't we be working in the bitwidth of a single AS at all times?

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

552

GEP decomposition looks through address space casts, so the index size can change. It does mostly work with the index size of a single AS and then sext up to the maximum size, though the precise way it does so is not quite correct in some respects (wrt sext/mul commutativity and scale adjustment -- fixing this needs some more preliminary work though).

It would certainly make things easier if we could get away with not looking through address space casts, but I'm not sure that's viable.

[nikic]

Rebase

[nikic]

llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

509

@aardappel @tlively Is it okay to check the address space zero pointer size here? I don't really want to retain a separate getMaxPointerSize() method for only this usage, which looks like a bit of a hack anyway.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

509

Yes, AS 0 is the correct one to check here.

[aardappel]

llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

509

LGTM

[arichardson]

Thanks, this LGTM and should hopefully avoid some unnecessary extends to 128 bits for CHERI.

I think it would be nice if we could avoid the use of the max pointer/index size here but that is an unrelated change that can be looked into later.

[nlopes]

LGTM

llvm/include/llvm/IR/DataLayout.h

public:
   /// the backends/clients are updated.
   Align 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;
+  /// Returns the maximum index size over all address spaces.
+  unsigned getMaxIndexSize() 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;
+  /// Returns the maximum index size over all address spaces.
+  unsigned getMaxIndexSizeInBits() const {
+    return getMaxIndexSize() * 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

llvm/lib/Analysis/BasicAliasAnalysis.cpp

static LinearExpression GetLinearExpression(
   if (isa<SExtInst>(Val.V))
     return GetLinearExpression(
         Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)),
         DL, Depth + 1, AC, DT);
 
   return Val;
 }
 
-/// To ensure a pointer offset fits in an integer of size PointerSize
-/// (in bits) when that size is smaller than the maximum pointer size. This is
+/// To ensure a pointer offset fits in an integer of size IndexSize
+/// (in bits) when that size is smaller than the maximum index 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(const APInt &Offset, unsigned PointerSize) {
-  assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!");
-  unsigned ShiftBits = Offset.getBitWidth() - PointerSize;
+/// where the maximum index size is 64b.
+static APInt adjustToIndexSize(const APInt &Offset, unsigned IndexSize) {
+  assert(IndexSize <= Offset.getBitWidth() && "Invalid IndexSize!");
+  unsigned ShiftBits = Offset.getBitWidth() - IndexSize;
   return (Offset << ShiftBits).ashr(ShiftBits);
 }
 
 namespace {
 // A linear transformation of a Value; this class represents
 // ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
 struct VariableGEPIndex {
   CastedValue Val;

 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 = DL.getMaxPointerSizeInBits();
+  unsigned MaxIndexSize = DL.getMaxIndexSizeInBits();
   DecomposedGEP Decomposed;
-  Decomposed.Offset = APInt(MaxPointerSize, 0);
+  Decomposed.Offset = APInt(MaxIndexSize, 0);
   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()) {
           V = GA->getAliasee();
do {
     if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) {
       Decomposed.Base = V;
       return Decomposed;
     }
 
     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);
+    unsigned IndexSize = DL.getIndexSizeInBits(AS);
     // Assume all GEP operands are constants until proven otherwise.
     bool GepHasConstantOffset = true;
     for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
          I != E; ++I, ++GTI) {
       const Value *Index = *I;
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = GTI.getStructTypeOrNull()) {
         // For a struct, add the member offset.
         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
         if (FieldNo == 0)
           continue;
 
         Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo);
         continue;
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero())
           continue;
         Decomposed.Offset +=
             DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() *
-            CIdx->getValue().sextOrTrunc(MaxPointerSize);
+            CIdx->getValue().sextOrTrunc(MaxIndexSize);
         continue;
       }
 
       GepHasConstantOffset = false;
 
-      // If the integer type is smaller than the pointer size, it is implicitly
-      // sign extended to pointer size.
+      // If the integer type is smaller than the index size, it is implicitly
+      // sign extended or truncated to index size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
-      unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0;
-      unsigned TruncBits = PointerSize < Width ? Width - PointerSize : 0;
+      unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
+      unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
       LinearExpression LE = GetLinearExpression(
           CastedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
 
       // Scale by the type size.
       unsigned TypeSize =
           DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize();
-      LE = LE.mul(APInt(PointerSize, TypeSize), GEPOp->isInBounds());
-      Decomposed.Offset += LE.Offset.sextOrSelf(MaxPointerSize);
-      APInt Scale = LE.Scale.sextOrSelf(MaxPointerSize);
+      LE = LE.mul(APInt(IndexSize, TypeSize), GEPOp->isInBounds());
+      Decomposed.Offset += LE.Offset.sextOrSelf(MaxIndexSize);
+      APInt Scale = LE.Scale.sextOrSelf(MaxIndexSize);
 
       // 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].Val.V == LE.Val.V &&
             Decomposed.VarIndices[i].Val.hasSameCastsAs(LE.Val)) {
           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);
+      // index size.
+      Scale = adjustToIndexSize(Scale, IndexSize);
 
       if (!!Scale) {
         VariableGEPIndex Entry = {LE.Val, Scale, CxtI, LE.IsNSW};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
     if (GepHasConstantOffset)
-      Decomposed.Offset = adjustToPointerSize(Decomposed.Offset, PointerSize);
+      Decomposed.Offset = adjustToIndexSize(Decomposed.Offset, IndexSize);
 
     // Analyze the base pointer next.
     V = GEPOp->getOperand(0);
   } while (--MaxLookup);
 
   // If the chain of expressions is too deep, just return early.
   Decomposed.Base = V;
   SearchLimitReached++;
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
     KnownBits Known =
         computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT);
     CR = CR.intersectWith(
         ConstantRange::fromKnownBits(Known, /* Signed */ true),
         ConstantRange::Signed);
     CR = Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth());
 
     assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
-           "Bit widths are normalized to MaxPointerSize");
+           "Bit widths are normalized to MaxIndexSize");
     if (Index.IsNSW)
       OffsetRange = OffsetRange.add(CR.smul_sat(ConstantRange(Scale)));
     else
       OffsetRange = OffsetRange.add(CR.smul_fast(ConstantRange(Scale)));
   }
 
   // We now have accesses at two offsets from the same base:
   //  1. (...)*GCD + DecompGEP1.Offset with size V1Size

llvm/lib/IR/DataLayout.cpp

 Align DataLayout::getPointerPrefAlignment(unsigned AS) const {
   return getPointerAlignElem(AS).PrefAlign;
 }
 
 unsigned DataLayout::getPointerSize(unsigned AS) const {
   return getPointerAlignElem(AS).TypeByteWidth;
 }
 
-unsigned DataLayout::getMaxPointerSize() const {
-  unsigned MaxPointerSize = 0;
+unsigned DataLayout::getMaxIndexSize() const {
+  unsigned MaxIndexSize = 0;
   for (auto &P : Pointers)
-    MaxPointerSize = std::max(MaxPointerSize, P.TypeByteWidth);
+    MaxIndexSize = std::max(MaxIndexSize, P.IndexWidth);
 
-  return MaxPointerSize;
+  return MaxIndexSize;
 }
 
 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());
 }

llvm/lib/Target/WebAssembly/WebAssemblyAsmPrinter.cpp

for (const SubtargetFeatureKV &KV : WebAssemblyFeatureKV) {
     EmitFeature(KV.Key);
   }
   // This pseudo-feature tells the linker whether shared memory would be safe
   EmitFeature("shared-mem");
 
   // This is an "architecture", not a "feature", but we emit it as such for
   // the benefit of tools like Binaryen and consistency with other producers.
   // FIXME: Subtarget is null here, so can't Subtarget->hasAddr64() ?
-  if (M.getDataLayout().getMaxPointerSize() == 8) {
+  if (M.getDataLayout().getPointerSize() == 8) {
     // Can't use EmitFeature since "wasm-feature-memory64" is not a module
     // flag.
     EmittedFeatures.push_back({wasm::WASM_FEATURE_PREFIX_USED, "memory64"});
   }
 
   if (EmittedFeatures.size() == 0)
     return;
 

llvm/test/Analysis/BasicAA/index-size.ll

+; RUN: opt -basic-aa -aa-eval -print-all-alias-modref-info -disable-output %s 2>&1 | FileCheck %s
+
+target datalayout = "p:64:64:64:32"
+
+; gep.1 and gep.2 must alias, because they are truncated to the index size
+; (32-bit), not the pointer size (64-bit).
+define void @mustalias_due_to_index_size(i8* %ptr) {
+; CHECK-LABEL: Function: mustalias_due_to_index_size
+; CHECK-NEXT: MustAlias: i8* %gep.1, i8* %ptr
+; CHECK-NEXT: MustAlias: i8* %gep.2, i8* %ptr
+; CHECK-NEXT: MustAlias: i8* %gep.1, i8* %gep.2
+;
+  %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
+}