BasicAA: Recognize inttoptr as isEscapeSource

[JosephTremoulet]

Summary

Pointers escape when converted to integers, so a pointer produced by
converting an integer to a pointer must not be a local non-escaping
object.

[JosephTremoulet]

I've verified this doesn't break anything in check-all or in test-suite with SpecInt2017 included. I'm happy for suggestions if there are other testing paces this should be put through. Thanks.

[nikic]

I believe this is correct, and also not affected by open ptrtoint/inttoptr issues.

llvm/test/Analysis/BasicAA/noalias-inttoptr.ll

11

We should also have negative (MayAlias) tests for a) non-local object and b) local escaping object.

[JosephTremoulet]

• Include negative tests and alloca as well as noalias parameter

[JosephTremoulet]

In D101541#2725915, @nikic wrote:

I believe this is correct, and also not affected by open ptrtoint/inttoptr issues.

Thanks for confirming!

[nikic]

LGTM, but I'd suggest waiting a bit in case there are further comments -- it's a tricky area.

[aqjune]

isNonEscapingLocalObject returns true if the pointer is a noalias argument, and it's worth clarifying why this is okay somewhere.

The noalias argument case is slightly different from other cases because its address could have been ptrtoint-ed already. For example:

%i = ptrtoint i8* %ptr0 to i64
call void @f(i8* %ptr0, i64 %i)

define void @f(i8* noalias %ptr, i64 %i) {
  ; access %ptr <- isNonEscapingLocalObject(%ptr) is true, but
  ; access inttoptr(%i) <- this can exactly touch %ptr.
}

It isn't clear whether the second access is successfully done according to the definition of based-on in LangRef.
Should we clarify that noalias ptr (%ptr) is not based on the original pointer (%ptr0)?

[JosephTremoulet]

In D101541#2727752, @aqjune wrote:

isNonEscapingLocalObject returns true if the pointer is a noalias argument, and it's worth clarifying why this is okay somewhere.

The noalias argument case is slightly different from other cases because its address could have been ptrtoint-ed already. For example:

%i = ptrtoint i8* %ptr0 to i64
call void @f(i8* %ptr0, i64 %i)

define void @f(i8* noalias %ptr, i64 %i) {
  ; access %ptr <- isNonEscapingLocalObject(%ptr) is true, but
  ; access inttoptr(%i) <- this can exactly touch %ptr.
}

It isn't clear whether the second access is successfully done according to the definition of based-on in LangRef.
Should we clarify that noalias ptr (%ptr) is not based on the original pointer (%ptr0)?

By my read, it isn't that %ptr isn't based on %ptr0 (I think it is based on %ptr0, though the LangRef based-on definition doesn't explicitly address copies from call arguments/parameters/returns, phis, selects, extractelement/extractvalue, etc.; maybe it should?).
Rather, I think that it's this language in the definition of noalias:

This indicates that memory locations accessed via pointer values
 :ref:`based <pointeraliasing>` on the argument or return value are not also
 accessed, during the execution of the function, via pointer values not
 *based* on the argument or return value. ... The caller shares the responsibility with the callee for
 ensuring that these requirements are met.

which means that the example you show is an incorrect use of the noalias attribute, because of the access via inttoptr(%i), which is not based on %ptr.

[aqjune]

In D101541#2729393, @JosephTremoulet wrote:

In D101541#2727752, @aqjune wrote:

isNonEscapingLocalObject returns true if the pointer is a noalias argument, and it's worth clarifying why this is okay somewhere.

The noalias argument case is slightly different from other cases because its address could have been ptrtoint-ed already. For example:

%i = ptrtoint i8* %ptr0 to i64
call void @f(i8* %ptr0, i64 %i)

define void @f(i8* noalias %ptr, i64 %i) {
  ; access %ptr <- isNonEscapingLocalObject(%ptr) is true, but
  ; access inttoptr(%i) <- this can exactly touch %ptr.
}

It isn't clear whether the second access is successfully done according to the definition of based-on in LangRef.
Should we clarify that noalias ptr (%ptr) is not based on the original pointer (%ptr0)?

By my read, it isn't that %ptr isn't based on %ptr0 (I think it is based on %ptr0, though the LangRef based-on definition doesn't explicitly address copies from call arguments/parameters/returns, phis, selects, extractelement/extractvalue, etc.; maybe it should?).
Rather, I think that it's this language in the definition of noalias:

This indicates that memory locations accessed via pointer values
 :ref:`based <pointeraliasing>` on the argument or return value are not also
 accessed, during the execution of the function, via pointer values not
 *based* on the argument or return value. ... The caller shares the responsibility with the callee for
 ensuring that these requirements are met.

which means that the example you show is an incorrect use of the noalias attribute, because of the access via inttoptr(%i), which is not based on %ptr.

Makes sense!

[nlopes]

There's this comment in isNonEscapingLocalObject:

// If this is an argument that corresponds to a byval or noalias argument,
// then it has not escaped before entering the function.  Check if it escapes
// inside the function.

Which supports this patch. Though this claim doesn't seem very clear to me. e.g. we mark memcpy's arguments with noalias. It's not guaranteed case that the input pointers haven't escaped before. So the exact meaning of noalias is not clear to me.
I've read the C11 standard re restrict, and it is omissive w.r.t. to int2ptr casts. Though I think this patch respects the spirit of the standard. We just need to nail the exact semantics of noalias at some point..
TL;DR: LGTM.

[JosephTremoulet]

In D101541#2732474, @nlopes wrote:

There's this comment in isNonEscapingLocalObject:

// If this is an argument that corresponds to a byval or noalias argument,
// then it has not escaped before entering the function.  Check if it escapes
// inside the function.

Which supports this patch. Though this claim doesn't seem very clear to me. e.g. we mark memcpy's arguments with noalias. It's not guaranteed case that the input pointers haven't escaped before. So the exact meaning of noalias is not clear to me.
I've read the C11 standard re restrict, and it is omissive w.r.t. to int2ptr casts. Though I think this patch respects the spirit of the standard. We just need to nail the exact semantics of noalias at some point..
TL;DR: LGTM.

Yeah I think the guarantee is something more like: if it did escape before the function, then it won't be accessed during the function via any pointer based on that escape (because such an access couldn't be based on the noalias parameter). But I'm technically misusing "based on" there, because it's defined as a predicate on pointer values, whereas "that escape" is a use...

Anyway, thanks!

[JosephTremoulet]

In D101541#2726412, @nikic wrote:

LGTM, but I'd suggest waiting a bit in case there are further comments -- it's a tricky area.

@nikic, a week later there have been two comments, both approvals. Do you think it's good to go now?

Thanks

[nikic]

@JosephTremoulet Yeah, that's more than enough! Please go ahead.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (isa<Argument>(V))
     return true;
 
   // The load case works because isNonEscapingLocalObject considers all
   // stores to be escapes (it passes true for the StoreCaptures argument
   // to PointerMayBeCaptured).
   if (isa<LoadInst>(V))
     return true;
 
+  // The inttoptr case works because isNonEscapingLocalObject considers all
+  // means of converting or equating a pointer to an int (ptrtoint, ptr store
+  // which could be followed by an integer load, ptr<->int compare) as
+  // escaping, and objects located at well-known addresses via platform-specific
+  // means cannot be considered non-escaping local objects.
+  if (isa<IntToPtrInst>(V))
+    return true;
+
   return false;
 }
 
 /// Returns the size of the object specified by V or UnknownSize if unknown.
 static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
                               const TargetLibraryInfo &TLI,
                               bool NullIsValidLoc,
                               bool RoundToAlign = false) {

llvm/test/Analysis/BasicAA/noalias-inttoptr.ll

+; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "p:64:64"
+
+declare void @escape(i8* %ptr)
+
+; Verify that unescaped noalias parameter does not alias inttoptr
+define void @test1(i8* noalias %P, i64 %Q_as_int) {
+  ; CHECK-LABEL: Function: test1:
+  ; CHECK: NoAlias: i8* %P, i8* %Q
+  %Q = inttoptr i64 %Q_as_int to i8*
+  store i8 0, i8* %P
+  store i8 1, i8* %Q
+  ret void
+}
+
+; Verify that unescaped alloca does not alias inttoptr
+define void @test2(i64 %Q_as_int) {
+  ; CHECK-LABEL: Function: test2:
+  ; CHECK: NoAlias: i8* %P, i8* %Q
+  %P = alloca i8
+  %Q = inttoptr i64 %Q_as_int to i8*
+  store i8 0, i8* %P
+  store i8 1, i8* %Q
+  ret void
+}
+
+; Verify that escaped noalias parameter may alias inttoptr
+define void @test3(i8* noalias %P, i64 %Q_as_int) {
+  ; CHECK-LABEL: Function: test3:
+  ; CHECK: MayAlias:  i8* %P, i8* %Q
+  call void @escape(i8* %P)
+  %Q = inttoptr i64 %Q_as_int to i8*
+  store i8 0, i8* %P
+  store i8 1, i8* %Q
+  ret void
+}
+
+; Verify that escaped alloca may alias inttoptr
+define void @test4(i64 %Q_as_int) {
+  ; CHECK-LABEL: Function: test4:
+  ; CHECK: MayAlias:  i8* %P, i8* %Q
+  %P = alloca i8
+  call void @escape(i8* %P)
+  %Q = inttoptr i64 %Q_as_int to i8*
+  store i8 0, i8* %P
+  store i8 1, i8* %Q
+  ret void
+}
+
+
+; Verify that global may alias inttoptr
+@G = external global i8
+define void @test5(i64 %Q_as_int) {
+  ; CHECK-LABEL: Function: test5:
+  ; CHECK: MayAlias:  i8* %Q, i8* @G
+  %Q = inttoptr i64 %Q_as_int to i8*
+  store i8 0, i8* @G
+  store i8 1, i8* %Q
+  ret void
+}