Aliasing of constant pointers (inttoptr Const) for BasicAA

[andrew.zhogin]

Summary

This patch improves BasicAA to understand aliasing of constant pointers represented as inttoptr (Const).
It supports both IntToPtrInst (%a = inttoptr i32 16 to i32*) and ConstantExpr (store i32 1, i32* inttoptr (i32 16 to i32*)) nodes.
Pointers are considered 'NoAlias' if ptr1 + size1 <= ptr2 or ptr2 + size2 <= ptr1.
Pointers are considered 'MustAlias' if ptr1 == ptr2 and size1 == size2.
Pointers are considered 'PartialAlias' otherwise.
Also, there is a check of pointer type equality.

Constant pointer is a very rare case in common application code. But for some low-level programming (drivers, embedded e.t.c.) such optimization may be helpful.

[asl]

lib/Analysis/BasicAliasAnalysis.cpp

1530

Please follow LLVM style guidelines

[andrew.zhogin]

Style changes

[eli.friedman]

This is missing a check for the address-space; address-spaces other than zero can behave in strange ways.

This doesn't correctly account for the width of the pointer: it's possible two pointers could overlap via wraparound.

I don't this is really a good idea, anyway: this seems likely to break someone's code which accidentally forgot to mark a pointer volatile, and unlikely to actually help performance.

[andrew.zhogin]

if (V1Type == V2Type)

This should also check that address spaces are equal too, right?

[andrew.zhogin]

Added bitwidth check for constants.

[eli.friedman]

Please ignore my previous comments, they were overly terse and not quite correct.

Analyzing the numeric value of a pointer to determine two pointers are noalias is not safe, period.

On most operating systems, you can mmap() a page of memory to multiple addresses, and users will expect it to point to the same memory. The C++ standard addresses this explicitly for atomic operations: "Operations that are lock-free should also be address-free. That is, atomic operations on the same memory location via two different addresses will communicate atomically."

If you're dealing with unusual addressing systems, the pointer value also can't be used like this because the pointer could contain metadata that doesn't actually affect to the memory location.

It should be okay to determine that two pointers with the same value are MustAlias... but we already perform that check (see isValueEqualInPotentialCycles).

You could write a patch to return PartialAlias results for constant integer pointers where we can prove overlap, I guess.

lib/Analysis/BasicAliasAnalysis.cpp

 AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
                                       AAMDNodes V1AAInfo, const Value *V2,
                                       uint64_t V2Size, AAMDNodes V2AAInfo) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size == 0 || V2Size == 0)
     return NoAlias;
 
+  Type *V1Type = V1->getType();
+  Type *V2Type = V2->getType();
+
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCasts();
   V2 = V2->stripPointerCasts();
 
   // If V1 or V2 is undef, the result is NoAlias because we can always pick a
   // value for undef that aliases nothing in the program.
   if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
     return NoAlias;
AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
   }
   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
     AliasResult Result =
         aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo);
     if (Result != MayAlias)
       return AliasCache[Locs] = Result;
   }
 
+  // inttoptr(Const1) NoAlias inttoptr(Const2)
+  //   if (Const1 + V1Size <= Const2) || (Const2 + V2Size <= Const1)
+  // Only if types are equal
+  if (V1Type == V2Type) {
+    ConstantInt *C1 = 0;
+    ConstantInt *C2 = 0;
+    if (auto *I1 = dyn_cast<IntToPtrInst>(V1))
+      C1 = dyn_cast<ConstantInt>(I1->getOperand(0));
+    else if (auto *I1 = dyn_cast<ConstantExpr>(V1))
+      if (I1->getOpcode() == Instruction::IntToPtr)
+        C1 = dyn_cast<ConstantInt>(I1->getOperand(0));
+    if (auto *I2 = dyn_cast<IntToPtrInst>(V2))
+      C2 = dyn_cast<ConstantInt>(I2->getOperand(0));
+    else if (auto *I2 = dyn_cast<ConstantExpr>(V2))
+      if (I2->getOpcode() == Instruction::IntToPtr)
+        C2 = dyn_cast<ConstantInt>(I2->getOperand(0));
+    if (C1 && C2 && C1->getBitWidth() == C2->getBitWidth()) {
+      uint64_t C1Val = C1->getZExtValue();
+      uint64_t C2Val = C2->getZExtValue();
+      if (C1Val + V1Size <= C2Val || C2Val + V2Size <= C1Val)
+        return AliasCache[Locs] = NoAlias;
+      if (C1Val == C2Val && V1Size == V2Size)
+        return AliasCache[Locs] = MustAlias;
+      return AliasCache[Locs] = PartialAlias;
+    }
+  }
+
   // If both pointers are pointing into the same object and one of them
   // accesses the entire object, then the accesses must overlap in some way.
   if (O1 == O2)
     if ((V1Size != MemoryLocation::UnknownSize &&
          isObjectSize(O1, V1Size, DL, TLI)) ||
         (V2Size != MemoryLocation::UnknownSize &&
          isObjectSize(O2, V2Size, DL, TLI)))
       return AliasCache[Locs] = PartialAlias;

test/Analysis/BasicAA/noalias-consts.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
+
+declare i32* @captures(i32* %cap) nounwind readonly
+
+define void @no() nounwind {
+entry:
+  store i32 1, i32* inttoptr (i32 16 to i32*)
+  %l = load i32, i32* inttoptr (i32 20 to i32*)
+  ret void
+}
+
+; CHECK: NoAlias:      i32* inttoptr (i32 16 to i32*), i32* inttoptr (i32 20 to i32*)
+
+define void @no2() nounwind {
+entry:
+  %a = inttoptr i32 32 to i32*
+  %b = inttoptr i32 36 to i32*
+  store i32 1, i32* %a
+  %cap = call i32* @captures(i32* %b) nounwind readonly
+  %l = load i32, i32* %b
+  ret void
+}
+
+; CHECK: NoAlias:      i32* %a, i32* %b
+
+define void @partial() nounwind {
+entry:
+  store i32 1, i32* inttoptr (i32 16 to i32*)
+  %l = load i32, i32* inttoptr (i32 18 to i32*)
+  ret void
+}
+
+; CHECK: PartialAlias:  i32* inttoptr (i32 16 to i32*), i32* inttoptr (i32 18 to i32*)
+
+define void @partial2() nounwind {
+entry:
+  %c = inttoptr i32 16 to i32*
+  %d = inttoptr i32 18 to i32*
+  store i32 1, i32* %c
+  %cap = call i32* @captures(i32* %c) nounwind readonly
+  %l = load i32, i32* %d
+  ret void
+}
+
+; CHECK: PartialAlias:  i32* %c, i32* %d
+
+define void @must() nounwind {
+entry:
+  %e = inttoptr i32 28 to i32*
+  %f = inttoptr i32 28 to i32*
+  store i32 1, i32* %e
+  %cap = call i32* @captures(i32* %e) nounwind readonly
+  %l = load i32, i32* %f
+  ret void
+}
+
+; CHECK: MustAlias: i32* %e, i32* %f
+