llvm dev - Jan 2019 - Reducing the number of ptrtoint/inttoptrs that are generated by LLVM

Hello Sanjoy,

Yep, combining it with propagateEquality of pointers may raise problem. :\

However I believe propagateEquality should be fixed properly, and adding
psub also suggests a solution for that. :)

It is sound to replace a pointer with another if subtraction of them is 0:

a = malloc()
free(a)
b = malloc() // Assume b == a numerically
if ((psub inbounds a b) == 0) { // a and b are pointing to different
objects, so the comparison becomes poison
  use(a)
}

=>

a = malloc()
free(a)
b = malloc() // Assume b == a numerically
if ((psub inbounds a b) == 0) {
  use(b)
}

Juneyoung Lee

On Fri, Jan 18, 2019 at 7:50 AM Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> On Mon, Jan 14, 2019 at 3:23 AM Juneyoung Lee via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > Patch https://reviews.llvm.org/D56598 adds llvm.psub(p1,p2) intrinsic
> function, which subtracts two pointers and returns the difference. Its
> semantic is as follows.
> >
> > If p1 and p2 point to different objects, and neither of them is based
on
> a pointer casted from an integer, `llvm.psub(p1, p2)` returns poison. For
> example,
>
> Are you proposing landing this in conjunction with some of the other
> stuff discussed in the twin allocation paper?  Otherwise isn't this
> problematic with propagateEquality of pointers?
>
> a = malloc()
> free(a)
> b = malloc() // Assume b == a numerically
> if (a == b) {
>   print(psub(b, b)) // prints 0
> }
>
> =>
>
> a = malloc()
> free(a)
> b = malloc() // Assume b == a numerically
> if (a == b) {
>   print(psub(a, b)) // prints poison
> }
>
> Though I admit propagateEquality of pointers has many other problems like
> this.
>
>
> -- Sanjoy
>

-- 

Juneyoung Lee
Software Foundation Lab, Seoul National University
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190118/8acf5329/attachment.html>

Ralf pointed out that psub cannot be used for propagating pointer equality
if pointer-cast integer is involved;

a = p
b = inttoptr(ptrtoint p)
if ((psub inbounds a b) == 0) {
use(b) // replacing b with a may be problematic, as it is essentially
folding inttoptr(ptrtoint p) -> p, which is discussed at
https://bugs.llvm.org/show_bug.cgi?id=34548
}

I'm sorry for the confusion. To propagate pointer equality, we certainly
need a better solution. :\

Juneyoung Lee

On Fri, Jan 18, 2019 at 4:57 PM Juneyoung Lee <juneyoung.lee at
sf.snu.ac.kr>
wrote:
> Hello Sanjoy,
>
> Yep, combining it with propagateEquality of pointers may raise problem. :\
>
> However I believe propagateEquality should be fixed properly, and adding
> psub also suggests a solution for that. :)
>
> It is sound to replace a pointer with another if subtraction of them is 0:
>
> a = malloc()
> free(a)
> b = malloc() // Assume b == a numerically
> if ((psub inbounds a b) == 0) { // a and b are pointing to different
> objects, so the comparison becomes poison
>   use(a)
> }
>
> =>
>
> a = malloc()
> free(a)
> b = malloc() // Assume b == a numerically
> if ((psub inbounds a b) == 0) {
>   use(b)
> }
>
> Juneyoung Lee
>
> On Fri, Jan 18, 2019 at 7:50 AM Sanjoy Das <sanjoy at
playingwithpointers.com>
> wrote:
>
>> On Mon, Jan 14, 2019 at 3:23 AM Juneyoung Lee via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> > Patch https://reviews.llvm.org/D56598 adds llvm.psub(p1,p2)
intrinsic
>> function, which subtracts two pointers and returns the difference. Its
>> semantic is as follows.
>> >
>> > If p1 and p2 point to different objects, and neither of them is
based
>> on a pointer casted from an integer, `llvm.psub(p1, p2)` returns
poison.
>> For example,
>>
>> Are you proposing landing this in conjunction with some of the other
>> stuff discussed in the twin allocation paper?  Otherwise isn't this
>> problematic with propagateEquality of pointers?
>>
>> a = malloc()
>> free(a)
>> b = malloc() // Assume b == a numerically
>> if (a == b) {
>>   print(psub(b, b)) // prints 0
>> }
>>
>> =>
>>
>> a = malloc()
>> free(a)
>> b = malloc() // Assume b == a numerically
>> if (a == b) {
>>   print(psub(a, b)) // prints poison
>> }
>>
>> Though I admit propagateEquality of pointers has many other problems
like
>> this.
>>
>>
>> -- Sanjoy
>>
>
>
> --
>
> Juneyoung Lee
> Software Foundation Lab, Seoul National University
>

-- 

Juneyoung Lee
Software Foundation Lab, Seoul National University
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190123/a2c258ec/attachment.html>

On Tue, Jan 22, 2019 at 11:07 AM Juneyoung Lee
<juneyoung.lee at sf.snu.ac.kr> wrote:
> Ralf pointed out that psub cannot be used for propagating pointer equality
if pointer-cast integer is involved;
>
> a = p
> b = inttoptr(ptrtoint p)
> if ((psub inbounds a b) == 0) {
> use(b) // replacing b with a may be problematic, as it is essentially
folding inttoptr(ptrtoint p) -> p, which is discussed at
https://bugs.llvm.org/show_bug.cgi?id=34548
> }
>
> I'm sorry for the confusion. To propagate pointer equality, we
certainly need a better solution. :\
I don't immediately see the problem.  Firstly because we branch on
(psub a b), a and b must have a common provenance.  If `a` is an
interior pointer to this common allocation then we're fine.  So the
only case where the psub will be == 0 and `a` will not be
dereferenceable is if a points to one past the end of some allocation.

The most obvious "full" example I can come up in this setting is:

// Assume the stack layout is x followed by y
int y[10];
int x[40];
int* a = &x[40]
int* b = inttoptr(ptrtoint a)
if ((psub inbounds a b) == 0) {
  *b = 9; // Sets y[0] = 9
}

But this code is problematic for other reasons (so I think it has to
be UB) -- if we allow assigning to y[0] like above then this breaks
alias analysis on alloca's right? `y` above is not escaped, so we
should be able to assume that nothing writes to it.

-- Sanjoy