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;

[litherum]

At 2017-10-28T04:52:07Z, mmaxfield@apple.com wrote:
So it seems like, if you move the Assignment all the way to the innermost return statements, you can have functions which return pointers and which have multiple return statements.

The requirement of not being able to assign to a pointer, however, still stands.

[litherum]

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

So it seems like, if you move the Assignment all the way to the innermost
return statements, you can have functions which return pointers and which
have multiple return statements.

The requirement of not being able to assign to a pointer, however, still
stands.

I guess this is a little bit moot because right now we don't have object literals, so a pointer inside an object will always be null. However, we want to add object literals. https://bugs.webkit.org/show_bug.cgi?id=178978

This will be pretty powerful. For example, you can have a struct with a pointer inside it, pass that by reference to a function (by taking a pointer to it), then that function can return a pointer to a field inside the struct, and the caller can then assign to that field (as long as the field doesn't itself contain a pointer).

[litherum]

At 2017-10-30T07:20:48Z, mmaxfield@apple.com wrote:
I think I've almost finished this at https://bugs.webkit.org/show_bug.cgi?id=178986

[litherum]

At 2018-08-30T00:06:06Z, mmaxfield@apple.com wrote:
*** Bug 189064 has been marked as a duplicate of this bug. ***

[litherum]

At 2018-08-30T00:06:09Z, mmaxfield@apple.com wrote:
*** Bug 179036 has been marked as a duplicate of this bug. ***

[litherum]

At 2018-09-24T17:41:49Z, mmaxfield@apple.com wrote:
We need to determine what the restrictions are on textures. Should they have the same restrictions as pointers? Maybe not, because arrays of textures are useful. Perhaps arrays of textures must only be passed in via the API, and cannot be built in the shader (like samplers)?