Bug 176967 - [WHLSL] Verify "logical mode" properties hold
Summary: [WHLSL] Verify "logical mode" properties hold
Status: RESOLVED MOVED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebGPU (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Myles C. Maxfield
URL:
Keywords:
: 179036 189064 (view as bug list)
Depends on: 177303
Blocks: 176199 189202
  Show dependency treegraph
 
Reported: 2017-09-14 16:30 PDT by Filip Pizlo
Modified: 2018-10-13 16:45 PDT (History)
1 user (show)

See Also:


Attachments
Start (8.13 KB, patch)
2017-10-27 18:37 PDT, Myles C. Maxfield
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2017-09-14 16:30:31 PDT
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.
Comment 1 Filip Pizlo 2017-09-14 16:46:31 PDT
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.
Comment 2 Filip Pizlo 2017-09-14 16:57:45 PDT
(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().
Comment 3 Filip Pizlo 2017-09-14 19:08:59 PDT
(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
Comment 4 Myles C. Maxfield 2017-10-27 17:23:42 PDT
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&[]<T>(thread vec2<T>* foo, uint index)
{
    if (index == 0)
        return &foo->x;
    if (index == 1)
        return &foo->y;
    trap;
}
Comment 5 Filip Pizlo 2017-10-27 17:37:22 PDT
(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&[]<T>(thread vec2<T>* 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.
Comment 6 Myles C. Maxfield 2017-10-27 17:46:45 PDT
(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&[]<T>(thread vec2<T>* 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.
Comment 7 Myles C. Maxfield 2017-10-27 17:47:01 PDT
(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&[]<T>(thread vec2<T>* 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?
Comment 8 Myles C. Maxfield 2017-10-27 18:37:47 PDT
Created attachment 325228 [details]
Start
Comment 9 Myles C. Maxfield 2017-10-27 19:37:35 PDT
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)
Comment 10 Myles C. Maxfield 2017-10-27 19:49:40 PDT
(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
Comment 11 Myles C. Maxfield 2017-10-27 19:57:29 PDT
(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()
Comment 12 Myles C. Maxfield 2017-10-27 21:09:15 PDT
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;
Comment 13 Myles C. Maxfield 2017-10-27 21:27:34 PDT
(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;
Comment 14 Myles C. Maxfield 2017-10-27 21:30:22 PDT
(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;
Comment 15 Myles C. Maxfield 2017-10-27 21:36:17 PDT
(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;
Comment 16 Myles C. Maxfield 2017-10-27 21:52:07 PDT
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.
Comment 17 Myles C. Maxfield 2017-10-27 22:10:19 PDT
(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).
Comment 18 Myles C. Maxfield 2017-10-30 00:20:48 PDT
I think I've almost finished this at https://bugs.webkit.org/show_bug.cgi?id=178986
Comment 19 Myles C. Maxfield 2018-08-29 17:06:06 PDT
*** Bug 189064 has been marked as a duplicate of this bug. ***
Comment 20 Myles C. Maxfield 2018-08-29 17:06:09 PDT
*** Bug 179036 has been marked as a duplicate of this bug. ***
Comment 21 Myles C. Maxfield 2018-09-24 10:41:49 PDT
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)?
Comment 22 Myles C. Maxfield 2018-10-13 16:45:22 PDT
Migrated to https://github.com/gpuweb/WHLSL/issues/138