[BasicAA] Peak through IntToPtr(Load(%object))

[fhahn]

Summary

If we use a pointer generated by inttoptr(load(%object)), use object as
underlying object. I am not entirely sure if this is valid given the
GetUnderlyingObject semantics and would appreciate your feedback!

[fhahn]

This partly addresses https://bugs.llvm.org/show_bug.cgi?id=40735

[efriedma]

Could you describe why you think this is correct? As far as I can tell, the "underlying object" you're returning isn't even related to the input pointer.

[fhahn]

In D59009#1419379, @efriedma wrote:

Could you describe why you think this is correct? As far as I can tell, the "underlying object" you're returning isn't even related to the input pointer.

Hm, %addr = load i64, i64* %base, align 8 loads from the alloca'd location, but I am not entirely sure. The cast to i64* and inttoptr should do the same thing as the snippet below, unless I am missing something? (which is quite likely, as I am not very familiar with inttoptr)

define void @test1(i64 %arg) {
  %loc = alloca %struct.data*, align 8
  call void @init(%struct.data** %loc )

  %addr = load %struct.data*, %struct.data** %loc, align 8
  %offset.ptr = getelementptr inbounds %struct.data, %struct.data* %addr, i64 0, i32 1
  %offset = load i64, i64* %offset.ptr, align 8, !range !13
  %gep.1 = getelementptr inbounds %struct.data, %struct.data* %addr, i64 0, i32 2
  %gep.2 = getelementptr inbounds [20 x i64], [20 x i64]* %gep.1, i64 0, i64 %offset
  store i64 1, i64* %gep.2, align 8
  ret void
}

[fhahn]

Just realized this went one step too far up the chain. The underlying object is the loaded value from the stack, but we cannot return that from GetUnderlyingObject, because it does not have a pointer type. I'll try to think of something else.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/KnownBits.h"
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
 #include <utility>
 
 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
+using namespace PatternMatch;
 
 /// 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
do {
     }
 
     if (Op->getOpcode() == Instruction::BitCast ||
         Op->getOpcode() == Instruction::AddrSpaceCast) {
       V = Op->getOperand(0);
       continue;
     }
 
+    Value *Loc;
+    if (match(Op, m_IntToPtr(m_Load(m_Value(Loc))))) {
+      Decomposed.Base = Loc;
+      return false;
+    }
     const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
     if (!GEPOp) {
       if (const auto *Call = dyn_cast<CallBase>(V)) {
         // CaptureTracking can know about special capturing properties of some
         // intrinsics like launder.invariant.group, that can't be expressed with
         // the attributes, but have properties like returning aliasing pointer.
         // Because some analysis may assume that nocaptured pointer is not
         // returned from some special intrinsic (because function would have to

llvm/lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   return true;
 }
 
 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
                                  unsigned MaxLookup) {
   if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
+    Value *Loc;
+    if (match(V, m_IntToPtr(m_Load(m_Value(Loc))))) {
+      return Loc;
+    }
+
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;

llvm/test/Analysis/BasicAA/inttoptr.ll

+; RUN: opt -basicaa -aa-eval -print-no-aliases < %s 2>&1 --disable-output | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.data = type <{ i64*, i64, [20 x i64] }>
+
+declare void @init(%struct.data** %ptr)
+
+; CHECK-LABEL: Function: test1
+; CHECK: NoAlias: i64* %base, i64* %gep.2
+
+define void @test1(i64 %arg) {
+  %loc = alloca %struct.data*, align 8
+  %base = bitcast %struct.data** %loc to i64*
+  call void @init(%struct.data** %loc )
+
+  %addr = load i64, i64* %base, align 8
+  %ptr = inttoptr i64 %addr to %struct.data*
+  %offset.ptr = getelementptr inbounds %struct.data, %struct.data* %ptr, i64 0, i32 1
+  %offset = load i64, i64* %offset.ptr, align 8, !range !13
+  %gep.1 = getelementptr inbounds %struct.data, %struct.data* %ptr, i64 0, i32 2
+  %gep.2 = getelementptr inbounds [20 x i64], [20 x i64]* %gep.1, i64 0, i64 %offset
+  store i64 1, i64* %gep.2, align 8
+  ret void
+}
+
+
+; CHECK-LABEL: Function: test2
+; CHECK-NOT: NoAlias: i64* %base, i64* %gep.2
+define void @test2(i64 %arg) {
+  %loc = alloca %struct.data*, align 8
+  %base = bitcast %struct.data** %loc to i64*
+  call void @init(%struct.data** %loc )
+
+  %addr = load i64, i64* %base, align 8
+  %strip = and i64 %addr, 72057594037927928
+  %ptr = inttoptr i64 %strip to %struct.data*
+  %offset.ptr = getelementptr inbounds %struct.data, %struct.data* %ptr, i64 0, i32 1
+  %offset = load i64, i64* %offset.ptr, align 8, !range !13
+  %gep.1 = getelementptr inbounds %struct.data, %struct.data* %ptr, i64 0, i32 2
+  %gep.2 = getelementptr inbounds [20 x i64], [20 x i64]* %gep.1, i64 0, i64 %offset
+  store i64 1, i64* %gep.2, align 8
+  ret void
+}
+
+
+!13 = !{i64 0, i64 20}