llvm dev - Dec 2017 - Why is remalloc not marked as noalias?

Hello,

According to my understanding, it seems that the result of realloc will not
technically alias the original pointer. When the realloc is done in-place
the reference <http://en.cppreference.com/w/c/memory/realloc> says:
"The original pointer ptr is invalidated and any access to it is undefined
behavior (even if reallocation was in-place)."

Additionally from the C11 standard
<https://port70.net/~nsz/c/c11/n1570.html#6.2.4p2> we have:
"The value of a pointer becomes indeterminate when the object it points to
(or just past) reaches the end of its lifetime"

Is this enough to infer that we can safely mark realloc as noalias?

-- 
Regards
Bhatu
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171226/d4208ae4/attachment.html>

Hi, Bhatu,

I agree. The return from realloc is always a new allocation (in C's 
model, even if the same pointer is returned).

The core issue is that we don't generally add the noalias return 
attribute to malloc in a specific way, but rely on the system headers 
marking malloc with __attribute__((malloc)). The GCC docs explain why 
realloc is not marked with that attribute 
(https://gcc.gnu.org/onlinedocs/gcc-7.1.0/gcc/Common-Function-Attributes.html#Common-Function-Attributes),
but it has to do with a property of the GCC attribute that we don't 
capture with our noalias return attribute (that the memory contains no 
live pointers to other objects).

That having been said, the relevant property of being allocation-like 
should already be captured by LLVM's analysis:
> /// \brief Tests if a value is a call or invoke to a function that 
> returns a
> /// NoAlias pointer (including malloc/calloc/realloc/strdup-like 
> functions).
> bool llvm::isNoAliasFn(...
it recognized realloc and several other functions in this regard even if 
they're not marked with noalias. The core problem, however, is that our 
AA intrastructure is looking at the noalias attribute directly (instead 
of calling isNoAliasFn). Please feel free to submit a patch. 
Specifically, in lib/Analysis/AliasAnalysis.cpp, we have:
> bool llvm::isNoAliasCall(const Value *V) {
>   if (auto CS = ImmutableCallSite(V))
>     return CS.hasRetAttr(Attribute::NoAlias);
>   return false;
> }
We should remove the current implementation of llvm::isNoAliasCall, and 
rename llvm::isNoAliasFn to llvm::isNoAliasCall (llvm::isNoAliasFn has 
only one caller, in MemoryDependenceAnalysis, so just update that call 
site). Then update some relevant test case (e.g., 
test/Analysis/BasicAA/2008-11-23-NoaliasRet.ll). If you can't submit a 
patch, please open a bug report (and tag it with the beginner keyword).

  -Hal

On 12/26/2017 04:13 AM, Bhatu via llvm-dev wrote:
> Hello,
>
> According to my understanding, it seems that the result of realloc 
> will not technically alias the original pointer. When the realloc is 
> done in-place the reference 
> <http://en.cppreference.com/w/c/memory/realloc> says:
> "The original pointer ptr is invalidated and any access to it is 
> undefined behavior (even if reallocation was in-place)."
>
> Additionally from theC11 standard 
> <https://port70.net/%7Ensz/c/c11/n1570.html#6.2.4p2> we have:
> "The value of a pointer becomes indeterminate when the object it 
> points to (or just past) reaches the end of its lifetime"
>
> Is this enough to infer that we can safely mark realloc as noalias?
>
> -- 
> Regards
> Bhatu
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180107/6fd7ca88/attachment.html>

On 26 Dec 2017, at 10:13, Bhatu via llvm-dev <llvm-dev at lists.llvm.org>
wrote:
> 
> According to my understanding, it seems that the result of realloc will not
technically alias the original pointer. When the realloc is done in-place the
reference says:
> "The original pointer ptr is invalidated and any access to it is
undefined behavior (even if reallocation was in-place)."
> 
> Additionally from the C11 standard we have:
> "The value of a pointer becomes indeterminate when the object it
points to (or just past) reaches the end of its lifetime"
> 
> Is this enough to infer that we can safely mark realloc as noalias? 
Realloc is tricky in practice and has caused us to rethink pointer equality on
CHERI.  We’ve observed that this is a fairly common idiom:

char *new = realloc(old, someLength);
if (new != old)
{
	// Update some copies of old to use new
}

This was problematic for us, because old and new had the same address but
different bounds information and we were treating comparisons of pointers as
equal if they pointed to the same location.

This is problematic with noalias, because if the result of realloc is guaranteed
never to alias with any existing pointer then this comparison is trivially true.
This won’t break any of the code that I’ve seen, but it will mean that we’re
optimising away the fast path and leaving only the slow path (which doesn’t
quite accord with how most programmers understand the notion of optimisation).

Note that this code does contain undefined behaviour, but as our prior work has
shown, so does pretty much any nontrivial C program.

David

On 01/08/2018 04:40 AM, David Chisnall via llvm-dev
wrote:
> On 26 Dec 2017, at 10:13, Bhatu via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> According to my understanding, it seems that the result of realloc will
not technically alias the original pointer. When the realloc is done in-place
the reference says:
>> "The original pointer ptr is invalidated and any access to it is
undefined behavior (even if reallocation was in-place)."
>>
>> Additionally from the C11 standard we have:
>> "The value of a pointer becomes indeterminate when the object it
points to (or just past) reaches the end of its lifetime"
>>
>> Is this enough to infer that we can safely mark realloc as noalias?
> Realloc is tricky in practice and has caused us to rethink pointer equality
on CHERI.  We’ve observed that this is a fairly common idiom:
>
> char *new = realloc(old, someLength);
> if (new != old)
> {
> 	// Update some copies of old to use new
> }
>
> This was problematic for us, because old and new had the same address but
different bounds information and we were treating comparisons of pointers as
equal if they pointed to the same location.
>
> This is problematic with noalias, because if the result of realloc is
guaranteed never to alias with any existing pointer then this comparison is
trivially true.  This won’t break any of the code that I’ve seen, but it will
mean that we’re optimising away the fast path and leaving only the slow path
(which doesn’t quite accord with how most programmers understand the notion of
optimisation).
Because in general we can't (and don't) use noalias to decide on pointer
equality, we won't optimize away the comparison. I think we're okay in 
this regard.
>
> Note that this code does contain undefined behaviour, but as our prior work
has shown, so does pretty much any nontrivial C program.
Indeed ;)

  -Hal
>
> David
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory