Verify "logical mode" properties hold

[litherum]

Migrated from https://bugs.webkit.org/show_bug.cgi?id=176967:

At 2017-09-14T23:30:31Z, fpizlo@apple.com wrote:
In this mode:

• thread references (thread T^ and thread T[]) no longer get exempted from the isPrimitive check. Currently it's OK to have a pointer to a pointer, if it's a thread pointer. So, thread T^^ is OK but device T^^ is not OK. But, neither of these things are OK in logical, since storing to a pointer to a pointer would break the no-Phi rule of the underlying pointer. It would be like an assignment.

• bunch of control flow constraints on how pointers flow through the program.

[litherum]

At 2017-09-14T23:46:31Z, fpizlo@apple.com wrote:
I think that to lower to something like GLSL, we need to inline everything and then give each value node in the AST its own variable.

Then you can do pointer erasure. Every time you see a use of a pointer, figure out where it points, and then you will emit code that directly talks to that variable.

[litherum]

At 2017-09-14T23:57:45Z, fpizlo@apple.com wrote:
(In reply to Filip Pizlo from comment #1)

I think that to lower to something like GLSL, we need to inline everything
and then give each value node in the AST its own variable.

Actually, I think that the interpreter needs to do this as well - but only when the language is not in logical mode.

I'm about to make the storage locations of temporary expressions slightly observable.

Consider this:

thread T^ operator&[]<T>(thread T[], uint);

Obviously, we'd want this to work in this case:

int[42] foo() { ... }

void bar()
{
    int x = foo()[5];
    ...
}

I think that the easiest way to get there is to say that every temporary storage location gets its own predetermined EBuffer, as opposed to allocating EBuffers dynamically during execution. This ensures that if you do this:

thread Foo^ g_ptr;

thread Foo^ operator&[](thread Foo[] array, uint index)
{
    return g_ptr = &array[index];
}

void fuzz()
{
    ^g_ptr = Foo(...);
}

Foo buzz()
{
    return ^g_ptr;
}

and then this:

Foo[42] foo;
return foo[5]; // This will cause g_ptr to point to &foo[5]

or even this:

Foo[10] makeFoos() { .. }

Foo foo = makeFoos()[5]; // This will cause g_ptr to point to a temporary location associated with the call expression "makeFoos()".

then at least you will get very well defined behavior:

• the language defines exactly where g_ptr points.
• operator&[] is always called immediately before a load, store, or address-of operation in the source.

I think that the places where storage locations are created are exactly those places where the interpreter currently calls snapshot().

[litherum]

At 2017-09-15T02:08:59Z, fpizlo@apple.com wrote:
(In reply to Filip Pizlo from comment #2)

(In reply to Filip Pizlo from comment #1)

I think that to lower to something like GLSL, we need to inline everything
and then give each value node in the AST its own variable.

Actually, I think that the interpreter needs to do this as well - but only
when the language is not in logical mode.

I'm about to make the storage locations of temporary expressions slightly
observable.

Consider this:

thread T^ operator&[]<T>(thread T[], uint);

Obviously, we'd want this to work in this case:

int[42] foo() { ... }

void bar()
{
    int x = foo()[5];
    ...
}

I think that the easiest way to get there is to say that every temporary
storage location gets its own predetermined EBuffer, as opposed to
allocating EBuffers dynamically during execution. This ensures that if you
do this:

thread Foo^ g_ptr;

thread Foo^ operator&[](thread Foo[] array, uint index)
{
    return g_ptr = &array[index];
}

void fuzz()
{
    ^g_ptr = Foo(...);
}

Foo buzz()
{
    return ^g_ptr;
}

and then this:

Foo[42] foo;
return foo[5]; // This will cause g_ptr to point to &foo[5]

or even this:

Foo[10] makeFoos() { .. }

Foo foo = makeFoos()[5]; // This will cause g_ptr to point to a

temporary location associated with the call expression "makeFoos()".

then at least you will get very well defined behavior:

• the language defines exactly where g_ptr points.
• operator&[] is always called immediately before a load, store, or
  address-of operation in the source.

I think that the places where storage locations are created are exactly
those places where the interpreter currently calls snapshot().

Filed: https://bugs.webkit.org/show_bug.cgi?id=176973

[litherum]

At 2017-10-28T00:23:42Z, mmaxfield@apple.com wrote:
I think the current design of anders are incompatible with logical addressing mode. One of the tenants of logical addressing mode is that each function which returns a pointer only has a single return statement. However, vec2's ander looks like this:

thread T* operator&[](thread vec2* foo, uint index)
{
if (index == 0)
return &foo->x;
if (index == 1)
return &foo->y;
trap;
}

[litherum]

At 2017-10-28T00:37:22Z, fpizlo@apple.com wrote:
(In reply to Myles C. Maxfield from comment #4)

I think the current design of anders are incompatible with logical
addressing mode. One of the tenants of logical addressing mode is that each
function which returns a pointer only has a single return statement.
However, vec2's ander looks like this:

thread T* operator&[](thread vec2* foo, uint index)
{
if (index == 0)
return &foo->x;
if (index == 1)
return &foo->y;
trap;
}

vec2’s ander will be compiled as an intrinsic anyway.

Therefore, I recommend just turning off logical validation in the stdlib.

[litherum]

At 2017-10-28T00:46:45Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #4)

I think the current design of anders are incompatible with logical
addressing mode. One of the tenants of logical addressing mode is that each
function which returns a pointer only has a single return statement.
However, vec2's ander looks like this:

thread T* operator&[](thread vec2* foo, uint index)
{
if (index == 0)
return &foo->x;
if (index == 1)
return &foo->y;
trap;
}

I guess we could fix this by:

1. Enforcing that anders only get called by IndexExpressions. We wouldn't let the programmer just call an ander directly. This means that every call to an ander will be wrapped by a DereferenceExpression
2. Enforcing that every return site in an ander is of the form "return &thing;"

If we enforce these two rules, we can, in the compiler, special-case these resultant patterns, and make the DereferenceExpressions and the MakePtrExpressions cancel out.

Or, maybe since we inline everything anyway, we could just punch through any FunctionLikeBlocks and cancel out any pairs of DereferenceExpressions and the MakePtrExpressions we find.

[litherum]

At 2017-10-28T00:47:01Z, mmaxfield@apple.com wrote:
(In reply to Filip Pizlo from comment #5)

(In reply to Myles C. Maxfield from comment #4)

I think the current design of anders are incompatible with logical
addressing mode. One of the tenants of logical addressing mode is that each
function which returns a pointer only has a single return statement.
However, vec2's ander looks like this:

thread T* operator&[](thread vec2* foo, uint index)
{
if (index == 0)
return &foo->x;
if (index == 1)
return &foo->y;
trap;
}

vec2’s ander will be compiled as an intrinsic anyway.

Therefore, I recommend just turning off logical validation in the stdlib.

I think we're supporting anders for arbitrary user-defined structs, right?

[litherum]

At 2017-10-28T01:37:47Z, mmaxfield@apple.com wrote:
Created attachment 325228
Start

[litherum]

At 2017-10-28T02:37:35Z, mmaxfield@apple.com wrote:
If we do go the route of simply removing pairs of DereferenceExpressions MakePtrExpressions throughout the entire program (and punching through function calls to do it), there are a few interesting cases to test:

1. *&foo = 3
2. foo = *&bar
3. foo = *&bar = 3
4. **&&foo = 3
5. int* foo() {} ... *foo() = bar()
6. int[10]* foo() {} ... (*foo())[3] = 4

We'd need to be able punch through:

1. function calls
2. IdentityExpressions
3. nothing (when the MakePtrExpression is a direct child of the DereferenceExpression)

[litherum]

At 2017-10-28T02:49:40Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #9)

If we do go the route of simply removing pairs of DereferenceExpressions
MakePtrExpressions throughout the entire program (and punching through
function calls to do it), there are a few interesting cases to test:

1. *&foo = 3
2. foo = *&bar
3. foo = *&bar = 3
4. **&&foo = 3
5. int* foo() {} ... *foo() = bar()
6. int[10]* foo() {} ... (*foo())[3] = 4

We'd need to be able punch through:

1. function calls
2. IdentityExpressions
3. nothing (when the MakePtrExpression is a direct child of the
   DereferenceExpression)

Presumably we'd also want to punch through nested function calls

[litherum]

At 2017-10-28T02:57:29Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #10)

(In reply to Myles C. Maxfield from comment #9)

If we do go the route of simply removing pairs of DereferenceExpressions
MakePtrExpressions throughout the entire program (and punching through
function calls to do it), there are a few interesting cases to test:

1. *&foo = 3
2. foo = *&bar
3. foo = *&bar = 3
4. **&&foo = 3
5. int* foo() {} ... *foo() = bar()
6. int[10]* foo() {} ... (*foo())[3] = 4

We'd need to be able punch through:

1. function calls
2. IdentityExpressions
3. nothing (when the MakePtrExpression is a direct child of the
   DereferenceExpression)

Presumably we'd also want to punch through nested function calls

Also things like *foo() = *bar()

[litherum]

At 2017-10-28T04:09:15Z, mmaxfield@apple.com wrote:
It would also probably also have to handle the case of something like this:

thread int** foo(thread int** x, thread int** y, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x : y;
}

thread int* bar(thread int* x, thread int* y, ...) {
return *foo(&x, &y, ...);
}

...

int x;
int y;
*bar(&x, &y, ...) = 5;

[litherum]

At 2017-10-28T04:27:34Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #12)

It would also probably also have to handle the case of something like this:

thread int** foo(thread int** x, thread int** y, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x : y;
}

thread int* bar(thread int* x, thread int* y, ...) {
return *foo(&x, &y, ...);
}

...

int x;
int y;
*bar(&x, &y, ...) = 5;

If you're allowed to put pointers inside structs, this would be something like

StructA foo(StructB x, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x.a : x.b;
}

StructC bar(StructD y, ...) {
return foo(y.c, ...).d;
}

...

bar(instanceOfStructD, ...).e = 5;

[litherum]

At 2017-10-28T04:30:22Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #13)

(In reply to Myles C. Maxfield from comment #12)

It would also probably also have to handle the case of something like this:

thread int** foo(thread int** x, thread int** y, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x : y;
}

thread int* bar(thread int* x, thread int* y, ...) {
return *foo(&x, &y, ...);
}

...

int x;
int y;
*bar(&x, &y, ...) = 5;

If you're allowed to put pointers inside structs, this would be something
like

StructA foo(StructB x, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x.a : x.b;
}

StructC bar(StructD y, ...) {
return foo(y.c, ...).d;
}

...

bar(instanceOfStructD, ...).e = 5;

whoops, I meant

*bar(instanceOfStructD, ...).e = 5;

[litherum]

At 2017-10-28T04:36:17Z, mmaxfield@apple.com wrote:
(In reply to Myles C. Maxfield from comment #14)

(In reply to Myles C. Maxfield from comment #13)

(In reply to Myles C. Maxfield from comment #12)

It would also probably also have to handle the case of something like this:

thread int** foo(thread int** x, thread int** y, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x : y;
}

thread int* bar(thread int* x, thread int* y, ...) {
return *foo(&x, &y, ...);
}

...

int x;
int y;
*bar(&x, &y, ...) = 5;

If you're allowed to put pointers inside structs, this would be something
like

StructA foo(StructB x, ...) {
bool b = /* some computation that the compiler can't reduce */
return b ? x.a : x.b;
}

StructC bar(StructD y, ...) {
return foo(y.c, ...).d;
}

...

bar(instanceOfStructD, ...).e = 5;

whoops, I meant

*bar(instanceOfStructD, ...).e = 5;

I guess it could be

(*(bar(instanceOfStructD, ...).e)).f = 5;