Add a static alias analysis #3336

alan-baker · 2022-08-16T19:34:08Z

Replace the aliasing section with a static analysis
- topological ordering
- disallows potential aliasing
  - same root identifier used as multiple pointer arguments
  - pointer parameter aliasing a global variable

github-actions · 2022-08-16T19:38:41Z

Previews, as seen when this build job started (bf5074d):
WebGPU _{webgpu.idl | Explainer | Correspondence Reference}
WGSL _{grammar.js | wgsl.lalr.txt}

wgsl/index.bs

krogovin · 2022-08-17T07:45:21Z

One main stinker with this is that error's relating to pointer alias-ing can only be detected by "diving into" a function that takes pointer arguments; so if someone is using a shader library then an internal change to the library can make the users of that library have their code go from acceptable into unacceptable even though the interface did not change.

Maybe to have something more simple and shallow as follows:

two pointer types: one for read-only and one for read and write
a call to a function taking pointers is illegal if the same pointer to read-write value is passed to more than one argument.

I think this prevents any possibility of aliasing and makes the error check simple and makes the function declarations king.

alan-baker · 2022-08-17T14:18:54Z

One main stinker with this is that error's relating to pointer alias-ing can only be detected by "diving into" a function that takes pointer arguments; so if someone is using a shader library then an internal change to the library can make the users of that library have their code go from acceptable into unacceptable even though the interface did not change.

Maybe to have something more simple and shallow as follows:

two pointer types: one for read-only and one for read and write

a call to a function taking pointers is illegal if the same pointer to read-write value is passed to more than one argument.

I think this prevents any possibility of aliasing and makes the error check simple and makes the function declarations king.

This analysis already handles the your proposed check without needing the extra pointer types. The problem with your proposal is that it misses aliases with module-scope variables, which the reason you have to look into the functions.

krogovin · 2022-08-17T16:43:21Z

This analysis already handles the your proposed check without needing the extra pointer types. The problem with your proposal is that it misses aliases with module-scope variables, which the reason you have to look into the functions.

Can you provide an example? I don't see issue....

alan-baker · 2022-08-17T17:02:11Z

Look at f5, f6, and f7 in the examples in this PR.

jimblandy

Yes, this looks great. Just some requested clarifications and suggestions.

jimblandy · 2022-08-30T17:26:51Z

wgsl/index.bs

+* Pointer parameters that are [=write access|written=].
+* Pointer parameters that are [=read access|read=].


This should clarify that parameters may be passed along to functions called from this function, and that the callees' usage is included in this.

jimblandy · 2022-08-30T17:29:56Z

wgsl/index.bs

+    corresponding parameter is in the written parameter set.
+* An argument of pointer type has a root identifier that is a global variable where:
+    * the corresponding parameter is in the set of written pointer parameters
+        and the modue-scope variable is in either the written or read set of


jimblandy · 2022-08-30T17:36:20Z

wgsl/index.bs

-
-<div class='example wgsl' heading='Aliased memory views'>
+A WGSL program [=shader-creation error|must not=] contain any potential aliases.
+The program is analyzed from the leaves of the callgraph upwards (e.g. topological order).


editorial: Suggest "(that is, in topological order)". "e.g." is "for example".

jimblandy · 2022-08-30T17:41:04Z

wgsl/index.bs

+        module-scope variables for the called function, or
+    * the corresponding parameter is in the set of read pointer parameters and
+        the module-scope variable is in the written set of module-scope
+        variables for the called function.


Suggestion: I think this might be a bit easier to follow if it were split into three cases:

parameter read, module-scope written

parameter written, module-scope read

both parameter and module-scope written

As it is now, the two cases are not quite symmetrical and it took me a few tries to see that they are correct as written.

Just a suggestion, if you think it's indeed clearer.

wgsl/index.bs

kdashg · 2022-09-06T07:40:24Z

WGSL 2022-08-30 Minutes

(previously WGSL pointer aliasing rules · Issue #1457)
AB: Writeup of JBs proposed analysis
JB: Great that I can sketch and AB writes language. Couldn’t find any problems with what is written, a few editorial and clarifications. Otherwise looks fine to me. Looks like it prevents cases between inout and ptr implementation and preserves the future facing options that we are aiming for. I like the language proposed in PR.
MM: Haven’t read yet. Couple questions though. One is the distinction between globals and parameters. Understand it is possible inside a function if it takes a param by reference so it can name a global and pass in as param. Imagine this analysis makes this a compile error?
AB: Maintains the distinction that something has to write to be an issue. Majority of work is to compare global to param. Paraa to param is easy at call site.
MM: Next, if no globals still some analysis to do, don’t think that’s trivial as the caller could have … or maybe it is trivial
AB: It’s relatively trivial. Trace to the root identifier. Functions can’t return pointers so they’re all based on small identifier expressions. In fact, passing param to function it’s quite restricted in what you can pass in that it has to be address of or param.
MM: Ok, so it isn't’ possible to write a program where a function gets called a root identifiers for the values passed in alias but also are declared in different functions. That parts cool. Other statement about it’s reasonable to have a struct foo, bar, and baz inside each other. Foo owns bar which owns baz. Reasonable for function to accept foo and baz as params. This analysis would forbid if the foo and baz are passed as aliases. I think that would be a common case. Little unfortunate it would be disallowed. Think it’s important for buffers with nested structs and you want to pass in leaf node and top level struct as sibling params. This would be disallowed which is unfortunate.
AB: Have a lot of ptr param restrictions already. No storage or uniform buffers, have to also remove workgroup. It’s function and private. Separate restriction on declaration, either another param or address of variable. Can’t subscope the memory locations prior to any of these changes (until we have more powerful pointers)
MM: Why not send pointer to member of buffer, seems like common use case.
AB: SPIRV doesn’t allow it.
MM: How does GLSL compile something? Copyin copyout?
AB: When you reference part of the buffer it isn’t passed as pointer. Either use global directly or load what’s needed and pass in and hope compiler optimizes as necessary. Similar restrictions exist in HLSL where hoping compiler does fast thing
MM: Interesting question is HLSL and GLLS allows author to say phrase please pass in member of buffer by reference
AB: No, not by reference. Can pass in what is equivalent to part similar to WGSL by passing in part of array. HLSL an dGLSL copy in/out is not true reference.
MM: Think talking past each other. Program is function takes in/out and caller passes a field of a buffer.
AB: This is what TR brought up as issue in hlsl with shared memory. Inout param with part of shared memory buffer the copying means every invocation is touching everything and the trampling which may or may not occur means you don’t get what you want. Don’t know who is writing the result, whichever invocation is last. Similar thing for something with our storage buffer, every invocation has a race as each invocation is writing all locations even if they didn’t intend. Seems like good thing to disallow.
JB: Think for TRs concern it would be nice to have concrete example. Have ideas of what we’re discussing but is a bit nebulous
AB: Imagine array of shared memory and inside function use invocation id to write 1 element of the array. Because in/out every invocation copies in and out. The last invocation clobbers all results.
MM: Not program I was describing.
- void foo(inout int x) { … }
- foo(myArray[thread_id])
MM: Think this would be common and unfortunate fi WGSL authors can’t describe this
AB: Capable of describing it but not with ref param. Use return value and assign back to array read from.
MM: Right have to do copy in and out themselves. Think it’s unfortunate as wouldn't need to do it in GLSL or HLSL to do copy in and out.
AB: Don’t know, feels like nitpicking as in function there is an assignment whereas in WGSL you have an assignment. Doesn’t seem onerous to do such a transformation. Would be problematic is when you have to deal with memory locations that would then be affected by every invocation.
JB: Think if we want to say in/out with ptrs and then give ptrs which can’t do what in/out does is disappointing. Don’t know what to do about that if SPIR-V can’t express as seems pretty fatal. Can see MM’s point about it being less than ideal
MM: Think proposal here is WGSL -> SPIR-V compiler would do what GLSL -> SPIR-V would do which is emit extra copy instructions to represent program.
AB: This one example where pre-divided memory where every invocation touches own reason but have to worry about case where someone passes case adn does the thread_id inside the function instead of at the boundary. Do we know everyone is going to write that way? Have feed back from TR where they’ve seen workgroup memory passed as in/out and that’s unreliable depending on underlying hardware. Are we concerned about allowing 1 case and other cases are unportable which would be surprising or do we say restructure code slightly in order to handle scalar case (where you split memory up and reassign it).
JB: My priorities are portable behaviour comes before making WGSL pointers a perfect substitute for other shader languages’ features, like in/out. Would definitely prefer the behaviour be restricted and portable then more featureful.
MM: Just to bring up again, the counter argument is we add in/out to WGSL and that would be both portable and featureful.
AB: But only so portable as it used in just the right way. Doesn’t take a way footgun of clobbering one array value with another and getting unexpected results. It’s defined but not what I want it to be. It’s a gotcha. Do you have the rest of the rules around these things? To me in/out is historical and backwards looking. Think it’s bad idea to keep with language moving forward. To say we need an attribute which is possibly a complicated compiler transform because someone doesn’t want a read/assignment seems overboard.
MM: You said the compiler transform is complicated and the users isn't, but those are the same complexity. Having trouble understanding what you mean by footgun, would appreciate an example
AB: With in/out and ordering you’re passing same location twice. With compiler transform it has to deal with all cases, but for user they have a specific case. Not the only case the compiler has to worry about.
MM: Could ask to get a couple lines of example code?
GR: Think the idea is if we defined alias these two params this is what will happen, how many folks will actually read spec to see how in/out works and how many do it by mistake and shoot themselves in the foot.
AB: foo(x, x) has a footgun
JB: If restrict reading to just proposed change and not all of ptr restrictions it’s easier to understand
MM: Is foo(x,x) the every member assigning example?
JB: Here’s an example of TR’s concerning code:
- void foo(inout int x[100]) { … use x[i] … }
- foo(myArray)
AB: Take your example and … then in/out looks like every member of the array and copies every element in and out.
MM: Feel like that’s orthogonal, is it possible to assign over all members of array with a single operation we have that already
AB: As in/out is described that’s exactly what will happen. DN filed issue that TR described about workgroup memory which has some details. (wgsl: pointer-to-workgroup in user-defined functions #3276)

Fixes gpuweb#1457 * Replace the aliasing section with a static analysis * topological ordering * disallows potential aliasing * same root identifier used as multiple pointer arguments * pointer parameter aliasing a global variable

* clarifications * updated example * fix typos

github-actions · 2022-09-06T18:48:40Z

Previews, as seen when this build job started (1cf9e61):
WebGPU _{webgpu.idl | Explainer | Correspondence Reference}
WGSL _{grammar.js | wgsl.lalr.txt}

dneto0

Thanks!

kdashg · 2022-09-09T23:17:42Z

WGSL 2022-09-06 Minutes

(previously WGSL pointer aliasing rules · Issue #1457)
AB: Integrated feedback from DN and JB and converted to PR. Waiting on MM feedback.
MM: Not prepared for feedback at this time. Another week?
KG: Think that's OK.

dneto0 · 2022-09-20T19:02:30Z

Agreed to land this on 2022-09-20

kdashg · 2022-09-20T19:33:12Z

WGSL 2022-09-20 Minutes

(previously WGSL pointer aliasing rules · Issue #1457)
KG: DG took look earlier and some nits. Does Apple have thoughts
MM: Both read and understand. Seems to do what it says on tin. View this and previous issue as single thing.
KG: Is there a path out of this combined issue that doesn't want this PR?
MM: Think DNs comment about if we had inout wed' still want this we think that's reasonable. We just don't want acceptance of this PR to have bearing on larger issue but if we can make progress now that's fine.
AB: Having inout would change the stuff about global variables would no longer apply and would only have callsite issue. Just in function.
KG: Just part of language we could ditch?
AB: Sure.
KG: Then think we should take this and have slightly firmer ground for discussions.
KG: Will give some thought on how we can make forward progress
MM: Was wondering about opinions on returning tuples
DN: Well and good, but late in the date for v1. Maybe for post-v1. Users will want this feature, will see existing shaders and want a log cognitive load translation to WGSL.
KG: That's my gut feeling. Like tuples and love destructuring and think all languages should have but they're generally tolerable to not have in v1 and we've triaged accordingly. But, if that is the sword to cut the knot then would like to talk to JB to see how bad it would sound implementation wise. Would be a way to get this kind of thing if implementation load isn't too hight and isnt' load to existing authors vs what thye have today. So think it should be a bit on the table.
JB: Haven't been talking tuples as I thought we didn't want to introduce into spec as we want v1. Tuples are fine, they're much smaller then other things. If multiple value return, destructed assign/binding would help move past would be interested in looking at proposals.
GR: Do we have a date we'd like to hit for v1
JB: Last year.
GR: Right, ASAP depends on P.
DN: Think we are losing a lot of value which folks don't have functionality they can use. There is only so much polishing of rocks I want to do.
KG: Right. Need to think if implementation cost isnt' too hight and we can jump into that soon rather then continuing to discuss as it's difficult to get consensen. Maybe time difference there, even given all have to do impl work it might be acceptable.
DN: Someone needs proposal that addresses unifiority analysis and is coherent with spec.
MM: If src level translation then uniformity falls out.
KG: Hope that's what we can do, not that I want that many translations, if already shown true then could hoist on that framework
JB: Don't like the spec to have too much of that stuff. Nicer to go into uniformity and see the constructs described.
Resolved: Merge this (but remember that this doesn’t sway the larger discussion on function out-params)

alan-baker added the wgsl WebGPU Shading Language Issues label Aug 16, 2022

alan-baker added this to the V1.0 milestone Aug 16, 2022

alan-baker requested a review from jimblandy August 16, 2022 19:34

alan-baker mentioned this pull request Aug 16, 2022

WGSL pointer aliasing rules #1457

Closed

djg reviewed Aug 17, 2022

View reviewed changes

wgsl/index.bs Show resolved Hide resolved

wgsl/index.bs Show resolved Hide resolved

jimblandy approved these changes Aug 30, 2022

View reviewed changes

dneto0 requested changes Aug 30, 2022

View reviewed changes

wgsl/index.bs Outdated Show resolved Hide resolved

wgsl/index.bs Outdated Show resolved Hide resolved

wgsl/index.bs Outdated Show resolved Hide resolved

wgsl/index.bs Show resolved Hide resolved

wgsl/index.bs Outdated Show resolved Hide resolved

alan-baker marked this pull request as ready for review September 6, 2022 18:28

alan-baker added 4 commits September 6, 2022 14:39

Add a static alias analysis

f46421e

Fixes gpuweb#1457 * Replace the aliasing section with a static analysis * topological ordering * disallows potential aliasing * same root identifier used as multiple pointer arguments * pointer parameter aliasing a global variable

fix examples

e4ab498

Changes for review

756bad1

* clarifications * updated example * fix typos

remove stray backtick

1cf9e61

alan-baker force-pushed the alias-analysis branch from b9f1184 to 1cf9e61 Compare September 6, 2022 18:45

alan-baker requested a review from dneto0 September 6, 2022 19:16

dneto0 approved these changes Sep 7, 2022

View reviewed changes

litherum mentioned this pull request Sep 13, 2022

wgsl: pointer-to-workgroup in user-defined functions #3276

Closed

dneto0 merged commit 8c70bfa into gpuweb:main Sep 20, 2022

dneto0 mentioned this pull request Sep 20, 2022

wgsl: user-defined functions with ptr params must satisfy aliasing restrictions gpuweb/cts#1852

Closed

		* Pointer parameters that are [=write access\|written=].
		* Pointer parameters that are [=read access\|read=].

Add a static alias analysis #3336

Add a static alias analysis #3336

Uh oh!

Conversation

alan-baker commented Aug 16, 2022

Uh oh!

github-actions bot commented Aug 16, 2022

Uh oh!

Uh oh!

Uh oh!

krogovin commented Aug 17, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alan-baker commented Aug 17, 2022

Uh oh!

krogovin commented Aug 17, 2022

Uh oh!

alan-baker commented Aug 17, 2022

Uh oh!

jimblandy left a comment

Choose a reason for hiding this comment

Uh oh!

jimblandy Aug 30, 2022

Choose a reason for hiding this comment

Uh oh!

jimblandy Aug 30, 2022

Choose a reason for hiding this comment

Uh oh!

jimblandy Aug 30, 2022

Choose a reason for hiding this comment

Uh oh!

jimblandy Aug 30, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

kdashg commented Sep 6, 2022

Uh oh!

github-actions bot commented Sep 6, 2022

Uh oh!

dneto0 left a comment

Choose a reason for hiding this comment

Uh oh!

kdashg commented Sep 9, 2022

Uh oh!

dneto0 commented Sep 20, 2022

Uh oh!

kdashg commented Sep 20, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

krogovin commented Aug 17, 2022 •

edited

Loading