Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[wgsl] continuing block #579

Closed
litherum opened this issue Feb 29, 2020 · 34 comments
Closed

[wgsl] continuing block #579

litherum opened this issue Feb 29, 2020 · 34 comments
Labels
wgsl WebGPU Shading Language Issues
Projects
Milestone

Comments

@litherum
Copy link
Contributor

litherum commented Feb 29, 2020

The Problem

All loops in SPIR-V have this structure:

      OpLoopMerge %51 %52 None               ; structured loop

      /* loop body here, possibly including continue and break */

%52 = OpLabel                                ; continue target

      /* loop increment code */

      OpBranch %49                           ; loop back

(continue will jump you to %52, and break will jump you just after the loop back.)

Note that the loop increment code can contain arbitrary SPIR-V. In fact, it can even contain another whole loop! The only requirement is that the continue label dominate the backedge.

However, in human-writable languages, the contents of a for loop increment can't contain arbitrary code. They can only contain a single statement. Therefore, this is one of the numerous places where SPIR-V is more expressive than human writable languages.

WGSL strives to be a faithful vessel for SPIR-V source (among other things it strives for). Therefore, there's a desire for it to be able to represent this kind of control flow.

Option 1: continuing

This is what WGSL has today. You represent arbitrary code in the loop increment by giving the loop increment a whole block, with {}s.

loop {
    if (!(i < 10))
        break;

    /* loop body */

    continuing {
        i = i + 1;
        j = j + 1;
    }
}

This is the most faithful to the original SPIR-V. On the other hand, it's confusing to authors.

If additional loop types are added, authors need never write continuing. It can be relegated to "things that are only present to support SPIR-V compilers."

Option 2: Implicit functions

Force compilers producing WGSL to put the loop increment in a new function, which wasn't present in the original SPIR-V source.

fn invisibleFunction(i : ptr<function, i32>, j : ptr<function, i32>) {
    i = i + 1;
    j = j + 1;
}

...

for (i = 0; i < 10; invisibleFunction(i, j)) {
    /* loop body */
}

This is the most familiar to authors. On the other hand, scanning for variable references to build the argument list for invisibleFunction is a nonzero amount of work.

Option 3: Comma operator

If we allow all statements to be separated by commas, then we can represent arbitrary code by just a concatenation of the statements.

for (i = 0; i < 10; i = i + 1, j = j + 1) {
    /* loop body */
}

This means something like the following would be valid:

var i : i32 = 0, loop { ... }, i = j + 7;

The comma operator is already somewhat familiar to programmers of the C family of languages. Just like in those languages, its use would be fairly rare, and could perhaps be relegated to "things that are only present to support SPIR-V compilers." Authors writing normal code need not use it.

Option 4: Restrict the set of acceptable programs

Even though SPIR-V is more expressive than human-writable languages, it is being used as a vessel to represent source code written in those human-writable languages. Therefore, most SPIR-V programs wouldn't actually put multiple statements in the loop increment, because the original source code doesn't put multiple statements in the loop increment. Therefore, we could put restrictions on what we are willing to accept in the loop increment, such that it would only contain a single WGSL statement, and most, but not all, SPIR-V code would be compatible.

SPIR-V optimizers might make this analysis difficult, because who knows what code they will move into the loop increment.

There is already precedent for not representing all SPIR-V programs. There are certain operations which simply can't be representable in WGSL because they aren't representable in either HLSL or Metal Shading Language (for example, OpImageTexelPointer or putting volatile on loads/stores instead of variables). Therefore, any SPIR-V tool will already necessarily have to have a mode switch for WGSL.

The downside is we lose compatibility with more SPIR-V programs. The upside is tools can be simpler.

Option 5: Introduce invisible variables

This would move the loop increment inside the loop body, and add additional control flow around it.

If the original source looked like

for (i = 0; i < 10; [complicated loop increment code]) {
    if (...)
        continue;
    a();
}

This could be represented as

for (i = 0; i < 10; ) {
    bool shouldContinue = false;
    if (...)
        shouldContinue = true;
    if (!shouldContinue) {
        a();
    }
    [complicated loop increment code]
}
@litherum litherum added the wgsl WebGPU Shading Language Issues label Feb 29, 2020
@othermaciej
Copy link

Some notes:

  • C/C++ for loops are often written using comma operators when there are multiple index variables. They are not exceedingly rare in those languages.

  • C/C++ comma operators can only separate expressions, not statements (which is ok there because assignment is an expression). Likewise in JavaScript. A comma operator separating arbitrary statements would be unfamiliar. But probably less so than the current loop syntax.

  • We could have both a normal-seeming for loop and also the weird loop/continuing for SPIR-V that does the weird thing (presumably only SPIR-V that's not generated from a human-writable language). This doesn't seem to be one of the listed options.

  • It seems like while loops with break statements could represent all the semantics of loop/continuing while also being more natural to authors. (I don't know if they are more general than what SPIR-V can represent.)

@litherum
Copy link
Contributor Author

litherum commented Mar 1, 2020

I believe option 3: Comma operator is the only solution that:

  1. is familiar to C/C++ programmers
  2. gets rid of continuing, and
  3. is a faithful match to the original SPIR-V source.

@dj2
Copy link
Member

dj2 commented Mar 1, 2020

The comma operator doesn't allow you to do more complicated things like if and loops inside the continuing block.

@othermaciej
Copy link

It does allow that if it's a statement separator and not an expression separator. (Which is admittedly weird. But such continue blocks are likely to be uncommon, both in WGSL and in SPIR-V, except perhaps as artifacts of code motion optimizations done at the SPIR-V level.)

@tangmi
Copy link

tangmi commented Mar 1, 2020

Edit 2: This entire post is in response to option 3 in the original post.

Is there a possibility to allow something that unifies statement and body_stmt in the for initializer and increment spots?

for_initializer_or_continuing:
  : statement
  | body_stmt

for_loop:
  FOR PAREN_LEFT for_initializer_or_continuing SEMICOLON primary_expression(?) SEMICOLON for_initializer_or_continuing PAREN_RIGHT body_stmt

Could allow something goofy like this:

# common (human-generated) case
for (i = 0; i < 10; i = i + 1) {
    # loop body
}

# loop with complex initial and continuing blocks
for ({
    i = 0;
    j = 0;
}; i < 10; {
    i = i + 1;
    j = j + 1;
}) {
    # advanced loop body
}
Alternate whitespace formatting example
# minified
for({i=0;j=0;};i<10;{i=i+1;j=j+1;}){
    # advanced loop body
}

# expanded
for (
    {
        i = 0;
        j = 0;
    };
    i < 10;
    {
        i = i + 1;
        j = j + 1;
    }
) {
    # advanced loop body
}

Note: I'm unsure of the implications of this beyond the superficial parsing/syntax in this comment.

Edit: Here's some slightly less subjective arguments for a style like this:

  • Reuses existing syntax: body_stmt is used everywhere in the language from function bodies to if branches. Reusing the syntax will maintain consistency on declaring a statements list (while the comma operator in option 3 above introduces an new syntax).
  • Is uncommon: Given that very complex continuing blocks are expected to be less common, a lot of the perceived ugliness would only appear in the "converted from optimized SPIR-V" case and could be justified with "this is machine-generated WGSL" (while still being relatively readable).

@dj2
Copy link
Member

dj2 commented Mar 1, 2020

That looks a lot worse then just loop continuing so I think is a step backwards.

@tangmi
Copy link

tangmi commented Mar 1, 2020

Unfortunately I'm not sure if there's an objectively "best" answer, given the nature of the problem... I've updated my post above with (hopefully) some more objective reasoning, for future consideration.

@othermaciej
Copy link

A while loop with a break statement could almost entirely capture the semantics of loop/continuing, but it would require duplicating the condition. They could be collapsed when transforming back to SPIR-V. But whether this is ok depends on just how preserving the SPIR-V -> WGSL -> SPIR-V round trip needs to be.

@dj2
Copy link
Member

dj2 commented Mar 2, 2020

You have no way of knowing the continuation block for a while with a break. So your loop merge would always have an empty continuing.

@kdashg
Copy link
Contributor

kdashg commented Mar 2, 2020

I think continuing is foreign-looking but promising. Syntactic sugar for multi-variable for loops is pretty low on my priorities. FWIW I generally recommend against them in code review. These days it's all about for (const auto i : IntegerRange(10) anyway. :)

As in the example I posted in #569, I think the current wgsl translation of the for-loop concept isn't that bad.

@dneto0
Copy link
Contributor

dneto0 commented Mar 7, 2020

Nitpick: There is no "OpContinue" or "OpBreak" in SPIR-V. break and continue are statements in C, and in WGSL. In SPIR-V whether a CFG edge (from a branch branch) is a (valid) edge depends on a bunch of things (see the spec).

First off, you are only required to have a "continuing" block for a particular loop if there actually is a "continue" statement for that loop. Sorry if that's not clear.

So @litherum that first example can be written as:

loop {
    if (!(i < 10))
        break;

    /* loop body */

    i = i + 1;
    j = j + 1;
 
}

Which seems fine to me. In fact, you can get better, and I suggest you follow the lead of Turing and Perl, and write the break first and its firing condition afterward:

loop {
     break if (!(i<10));
     /* loop body */
     i = i + 1;
     j = j + 1;
}

But here's where "unless" comes to the rescue:

loop {
     break unless i < 10;
     /* loop body */
     i = i + 1;
     j = j + 1;
}

Or if you really dislike unless, push the inversion through the "unless":

loop {
     break if i >= 10;
     /* loop body */
     i = i + 1;
     j = j + 1;
}

Seems clear enough to me. That's super readable for beginners. (Turing is a teaching langauage widely used for a couple of decades. It would have "exit when" instead of "break if" in this example. Perl is swiss-army chainsaw and it would have "last if" in this example.)

Now let's assume there is at least one continue statement in a given loop. That's what forces us to have a place to jump to.

About @litherum's options:

Option 1: This is what we put into the WGSL proposal. You've mostly intuited the reasons why.
I'll add more colour, however.

In C, GLSL, and HLSL the "update" portion of the for loop normally only contains an increment, or something like that. It can have a function call, or several separated by commas.
That called function can have a very complex control flow graph. It may call other functions, etc.

In GPU compilers it is extraordinarily common to fully in inline every function down from the entry point. That's true for a lot of reasons I won't get into now, but that's just how it works. (It's also why shader languages disallow cycles in the call graph.)
Full inlining gets the programmer to the code that they need in order to meet their targets (e.g. perf).

For HLSL compilation, it's even stronger than that. We have found through experience with a broad corpus of shaders that full inlining is the first step in a recipe for "legalizing" HLSL shaders so they actually map to a valid thing that can run on the GPU.

I refer you to https://www.khronos.org/assets/uploads/developers/library/2018-gdc-webgl-and-gltf/2-Vulkan-HLSL-There-and-Back-Again_Mar18.pdf for an overview, and https://github.com/microsoft/DirectXShaderCompiler/blob/master/docs/SPIRV-Cookbook.rst for a bunch of true-to-life examples of source code that are on the face of it totally invalid but made to work via the legalization recipe we put into DXC's HLSL -> SPIR-V flow. (The same recipe is used for Glslang's HLSL --> SPIR-V flow.)

Now, that said, a lot of shaders you'll see coming to WebGPU will be fully inlined. We better have a general solution to this "complex thing in the continue construct" challenge. Because a lot of people are going to be staring at their especially complex code having been pushed through an often complex toolchain.

Second, the "continuing" construct means the "continue" statement is a forward branch. It's not a backward branch to the middle of the "for" statement. That means the loop backedge in WGSL is the only branch in control flow that goes backward (from bottom of source to top of source). This is exceedingly clear when you think of control flow from first principles.

Do this with a friend who hasn't programmed before: Trace your finger through the control flow for a C-style for loop with all 3 clauses active. In each regular iteration, your finger reverses direction twice, and when leaving the test clause, jumps over the update/continue clause to reach the body. That's just confusing when you think about it.

The "continuing" construct avoids that. You always go forward, down in the source text, except for that one backedge at the end of the loop that takes up to the top. Easy peasy.

Option 2: implicit functions, also called "outlining". That doesn't cut it, I hope that's clear. Yes, you'd have to chase down all the names that cross boundaries into and out of that continuing clause. So we reject it.

Option 3: Doesn't cut it. It's not general enough.

Option 4: Restrict the possible program.

But why? That's giving up.

@othermaciej
Copy link

othermaciej commented Mar 7, 2020

Why is Option 3 not general enough? What can it not do? (Note that in Myles's proposal, comma is a statement separator, not just an expression separator, so it is as general as continuing; allowing a block anywhere that a statement is allowed would achieve the same effect.)

@litherum
Copy link
Contributor Author

litherum commented Mar 9, 2020

Nitpick: There is no "OpContinue" or "OpBreak" in SPIR-V.

Whoops, you're right! I've updated the original post.

@litherum
Copy link
Contributor Author

Also Option 6 as described by @tangmi. This is as powerful as option 3 (which, I agree with @othermaciej, is powerful enough if you consider the comma to be a statement separator, rather than an expression separator).

I actually agree with your "trace your finger" analogy: to a new programmer, for loops are not the most intuitive things in the world. However, there is something to be said for similarity with other languages. Javascript has for loops, and every popular human writable shading language has for loops. None of them have continuing. I think we can assume that all authors of WebGPU & WGSL will be familiar with some human writable programming language. Part of being readable and writable by humans implies major language features are at least somewhat familiar. Loop increments are a major language feature.

It also makes sense for the language to be designed such that, where possible, a compiler emitting WGSL wouldn't use an entirely distinct set of facilities from a human author. In general, we should try to avoid creating two distinct languages inside WGSL (one for compilers and one for humans). I understand this is not possible in all cases, but I believe continuing is one case where it is possible.

@kainino0x
Copy link
Contributor

On the other hand, it's confusing to authors.

It's certainly unfamiliar, but it's not totally clear from that post that continuing actually confused anyone.

If additional loop types are added, authors need never write continuing. It can be relegated to "things that are only present to support SPIR-V compilers."

This is OK to me (though I am about to argue for it to be occasionally handwritten). I actually agree that for is a useful syntax because it puts all of the info on "what iterations occur" on one line [except for breaks, continues, and (ew) modification of the loop variable inside the loop condition (wish we could easily add range-based for-loops - which allow languages like Rust to completely forgo C-style for-loops - but don't think we can)].

However I'm opposed to using for-with-block-continuing to replace loop, partly because it complicates things and makes the syntax unfamiliar (IMO unnecessarily), and mostly because it's significantly harder to read generated code. (Yes, I think generated code can and should be reasonably readable, and I do not think there is a significant implementation cost to having the loop syntax and the for syntax be different.)

I'm going to make up some numbers now for the sake of argument.

  • I estimate 95% of for-loops in shaders look like for (int i = 0; i < 10; i++). I.e., no comma needed.
  • I estimate that of the remainder, 80% do not use continue and therefore can be written like this:
    int j = 1; for (int i = 0; i < 10; i++) { body; j *= 2; }
  • I think it's okay for the remaining 1% case to use loop/continuing. Or just duplicate the j = j * 2; line.

From this I arrive at the opinion that:

  • We should have loop/continuing.
  • We should have C-style for as a sugar: for (stmt; expr; stmt) { blocks }, where:
    • stmts cannot be blocks.
    • there are no comma separators in either of the two stmts (could maybe be added much later if we really see demand for it).

(BTW, I'm potentially okay with commas in the long run, but strongly against the comma operator which requires things like i += 1 to be expressions, among other strange pitfalls.)

@kainino0x
Copy link
Contributor

kainino0x commented Mar 10, 2020

Completely orthogonal to the above post, I've been toying with this idea:

loop {
  break if i >= 10;
  if (i == j) {
    goto continue;
  }  // or `goto continue if i == j`
continue:
  i = i + 1;
  j = j * 2;
}

This would be a totally special syntax - goto continue is an atomic piece of syntax and continue: is an atomic piece of syntax, you cannot use any other label: or any other goto statement. (edit: forgot "not")

I think it has three very minor benefits: it's immediately readable to someone who has seen goto before, it clearly expresses that control flow passes from line 5 to line 7 (edit: maybe not, since our switch doesn't work that way), and it makes it clear that no statements can appear after the continuing { } block.

@kdashg
Copy link
Contributor

kdashg commented Mar 10, 2020

What if we went more primitive?
From

loop {
    if (!(i < 10))
        break;

    foo();

    if (i & 1 == 0)
        continue;
        
    bar();
    ...

    continuing {
        i = i + 1;
        j = j + 1;
    }
}

Now without continue/continuing:

loop {
    if (!(i < 10))
        break;

    foo();

    if (!(i & 1 == 0)) {
        bar();
        ...
    }

    i = i + 1;
    j = j + 1;
}

I like primitives, so I feel like it continue is being difficult, we should consider removing it. Yes it makes some things a little less clean to write, but it's not bad. That feels like MVP for me!


Worth mentioning, but you can also desugar continuing without hidden local variables if you have a break N:

loop {
    loop {
      if (!(i < 10))
          break 2;

      foo();

      if (i & 1 == 0) {
          // breaking the inner loop continues the outer
          break; // aka `break 1;`
      }
          
      bar();
      ...
      break;
    }

    i = i + 1;
    j = j + 1;
}

In this case the inner loop is really a do{}while(false) block, which fwiw I think is the block construct in WASM.

@kainino0x
Copy link
Contributor

I think if we removed the continuing concept entirely there would be no way to map a lot of SPIR-V to WGSL.

I was thinking about multi-level breaks at one point too, and I'm hesitant to add them. But now that I think about it... are they needed to express some SPIR-V?

@kainino0x
Copy link
Contributor

kainino0x commented Mar 10, 2020

Actually, now I see your interesting idea over in #581 (comment) about whether continue is really needed.

@kdashg
Copy link
Contributor

kdashg commented Mar 10, 2020

(Aside: I wanted to know more about where the idea of continuing comes from, so I took a shot at translating from SPIR-V. Maybe it's useful to others, but it doesn't directly matter for the below. (Also I transcribed the PDF, since I have trouble copy/pasting from it)
Link: https://hackmd.io/3RtFD1_MRa6YZSxm5TXrwQ )

I think I see what continuing is about now, for instance:

  %10 = OpTypePointer Function <i32>
  %11 = OpTypePointer Output <i32>
  %12 = OpVariable %11 Output
...
  %99 = OpVariable %10 Function
  OpStore %99 <i32 0>           ; i = 0
  
%100 = OpLabel
  OpLoopMerge %200 %190 None
  OpBranch %110
  
%110 = OpLabel
  %111 = OpLoad <i32> %20
  %112 = OpSLessThan <bool> %111 <i32 4>
  OpBranchConditional %112 %120 %200      ; if (i < 4) then pass else break
  
%120 = OpLabel
  %122 = OpIEqual <bool> %111 <i32 1>
  OpBranchConditional %122 %190 %120   ; if (i == 1) then continue else pass
  
%120 = OpLabel
  %121 = OpLoad <i32> %12
  %122 = OpIAdd <i32> %121 <i32 1>
  OpStore %12 %122                  ; result = result + 1;
  OpBranch %150

%190 = OpLabel
  %191 = OpLoad <i32> %99      
  %192 = OpIAdd <i32> %191 <i32 1>
  OpStore %99 %192                  ; i = i + 1;
  OpBranch %100
%200 = OpLabel  // loop merge target

Currently:

out result : i32;
...
var i = i32(0);
loop {
  if (!(i < 4)) break;
  if (i == 1) continue;
  result = result + 1;
  continuing { i = i + 1; }
}

But without continuing...:

out result : i32;
...
var i = i32(0);
loop {
  loop {
    if (!(i < 4)) break 2;
    if (i == 1) break 1;
    result = result + 1;
    break 1;
  }
  i = i + 1;
}

Consider these classifications:

  • Any loop with only break (including a break instead of implicit end-of-block continue) is actually a do {} while (false) "do-block", and will have no loop emitted.
  • The "continuing block" is whatever the last label-block in the loop's non-breaking branches. (can be an empty label-block)
out result : i32;
...
var i = i32(0);
loop {
  do {
    if (!(i < 4)) break 2; // branch to after loop
    if (i == 1) break 1; // branch to after do
    result = result + 1;
    // branch to after do
  }
  branch to continue
  continuing {
    i = i + 1;
    branch to top of loop
  }
}
  out result : i32;
...
  var i = i32(0);
loop merge breaking continuing
label top-of-loop:
  if (!(i < 4)) branch breaking;
  if (i == 1) branch continuing;
  result = result + 1;
  branch continuing;
label continuing:
  i = i + 1;
  branch top-of-loop;
label breaking:

Too crazy? I think it's worth a thought, though it definitely pushes the bounds of 'directly translatable' back a bit. Simpler on the WGSL side, though.

Honestly if continuing only showed up in compiled code, I think that'd be fine too, but it'd be nice to not special-case this block if we can reasonably infer it?

@othermaciej
Copy link

Too crazy? I think it's worth a thought, though it definitely pushes the bounds of 'directly translatable' back a bit. Simpler on the WGSL side, though.

I think this obscures the structured control flow and start to look like programming with goto. If only one back edge is allowed, this makes it hard to explain what branches are allowed. loop merge is also tricky to understand. I had to read the SPIR-V docs to understand it even after your examples, and I'm still not sure what purpose it serves.

@dneto0
Copy link
Contributor

dneto0 commented Mar 10, 2020

Hey @jdashg
I took your fragment shader, removed "noperspective", added location layouts (for ins and outs), and a set/binding for the uniform, then compiled it with Glslang, then shoved it through my prototype translator to (proposed WGSL)

This is what I get:


import "GLSL.std.450" as std::glsl;

entry_point fragment as "main" = main;

type Arr = [[stride 16]] array<vec4<f32>,5>;
type S = struct {
  [[offset 0]] b : u32;
  [[offset 16]] v : Arr;
  [[offset 96]] i : i32;
};
type blockName = [[block]] struct {
  [[offset 0]] s : S;
  [[offset 112]] cond : u32;
};

[[set 0, binding 0]] var<uniform> _ : blockName;
[[location 0]] var<out> color : vec4<f32>;
[[location 0]] var<in> color1 : vec4<f32>;
[[location 2]] var<in> color2 : vec4<f32>;
[[location 1]] var<in> multiplier : vec4<f32>;

fn main() -> void {
  var scale : vec4<f32>;
  var i : i32;
  scale = vec4<f32>(1.,1.,2.,1.);
  const x_24 : u32 = _.cond;
  if ((x_24 !== 0)) {
    const x_34 : vec4<f32> = color1;
    const x_39 : vec4<f32> = _.s.v[2];
    color = (x_34 + x_39);
  } else {
    const x_43 : vec4<f32> = color2;
    const x_45 : vec4<f32> = scale;
    color = (std::glsl::sqrt(x_43) * x_45);
  }
  i = 0;
  loop {
    const x_54 : i32 = i;
    break unless ((x_54 :< 4));
    const x_58 : vec4<f32> = multiplier;
    const x_59 : vec4<f32> = color;
    color = (x_59 * x_58);
    continuing {
      const x_61 : i32 = i;
      i = (x_61 + 1);
    }
  }
  return;
}

Note that there is no "continue" statement in the original, so there is no "continue" statement in the final. I could work harder to remove the "continuing" and have the the last two statements be free floating at the end.

I'll repeat: you only need a continuing clause if you have a continue statement targeting it


edited to fix a copy-paste error: added the terminating return and brace

@dneto0
Copy link
Contributor

dneto0 commented Mar 10, 2020

And before anyone says "oh my that's wordy", my prototype puts each load and each store in its own statement. That explains the plethora of temporaries.

@dneto0
Copy link
Contributor

dneto0 commented Mar 10, 2020

FYI: If you're trying to understand control flow graphs in SPIR-V, use spirv-cfg from SPIRV-Tools. It emits a GraphViz graph for the CFG of each function, with annotations of merge and continue targets for merge instructions.

$ spirv-cfg x.spv -o x.dot
$ cat x.dot
digraph {
legend_merge_src [shape=plaintext, label=""];
legend_merge_dest [shape=plaintext, label=""];
legend_merge_src -> legend_merge_dest [label=" merge",style=dashed];
legend_continue_src [shape=plaintext, label=""];
legend_continue_dest [shape=plaintext, label=""];
legend_continue_src -> legend_continue_dest [label=" continue",style=dotted];
5 [label="5
Fn main entry", shape=box];
5 -> 28;
5 -> 41;
5 -> 29 [style=dashed];
28 [label="28"];
28 -> 29;
41 [label="41"];
41 -> 29;
29 [label="29"];
29 -> 49;
49 [label="49"];
49 -> 53;
49 -> 51 [style=dashed];
49 -> 52 [style=dotted];
53 [label="53"];
53 -> 50;
53 -> 51;
50 [label="50"];
50 -> 52;
52 [label="52"];
52 -> 49;
51 [label="51"];
}
$ dot -Tpng x.dot -ox.png

The result:

x

It looks a little weird because of how GraphiViz plots the final block (number 52 with the return) as higher than the loop backedge block (number 52).

@grorg
Copy link
Contributor

grorg commented Mar 10, 2020

Discussed at 2020-03-10 Teleconference

@litherum
Copy link
Contributor Author

litherum commented Mar 13, 2020

There's another proposal (I think we're up to number 7 now?): Allow the third clause of the for loop to be a single statement. In the grammar, assignments (which are the common case for the third clause) are represented as assignment_stmt, which is already a statement.

for (i = 0; i < 10; if (true) { [complicated loop increment] }) {
    ...
}

This requires one of:

  1. Specifying that the third clause is scoped as-if it was at the end of the loop body, so it can use variables declared inside the loop body
  2. Hoisting all variables declared inside the loop body which are referenced inside the increment, so that they're declared just above the top of the loop. Because SPIR-V has dominance scoping, any driver which accepts SPIR-V would likely already have lifetime analysis (so not every variable has to be in-scope at the last line of the function), so it's plausible that hoisting doesn't necessarily have performance problems.
  3. Hoisting, just like 2 above, but apply the inverse transformation when compiling from WGSL -> SPIR-V. This is another case where unconditionally applying this reverse transformation is a win-win: either we faithfully reproduce the original source, or we improve the program.

@kainino0x
Copy link
Contributor

kainino0x commented Mar 13, 2020

I don't think WGSL has to do any such scoping/hoisting. Won't a compiler generating WGSL from SPIR-V hoist place all variables to at the top of the function anyway? (Because "All OpVariable instructions in a function must be in the first block in the function")

@litherum
Copy link
Contributor Author

const foo : i32 = ...; does not correspond to OpVariable. It corresponds to an SSA Id.

@kainino0x
Copy link
Contributor

Ah. consts aren't possible to hoist, though (the value could depend on the code in the body), so any SPIR-V SSA ids in the body would have to be converted into WGSL variables.

@litherum
Copy link
Contributor Author

In option 3 above, none of the SPIR-V representations would have them hoisted. They would only be hoisted in WGSL. When compiling WGSL to SPIR-V, the reverse transformation would sink them into the loop and demote them to SSA Ids.

@kainino0x
Copy link
Contributor

Gotcha.

@grorg grorg removed the for meeting label Mar 17, 2020
@dj2 dj2 added this to Discussion in WGSL Mar 24, 2020
@dneto0
Copy link
Contributor

dneto0 commented Apr 15, 2020

FYI. I posted #711 which fills in a lot of missing info from the original draft.

@Kangz
Copy link
Contributor

Kangz commented Feb 2, 2022

The continuing block has stayed pretty stable since the discussion on this issue. Is this ok to close?

@Kangz Kangz added this to the V1.0 milestone Feb 2, 2022
@kdashg kdashg closed this as completed Feb 8, 2022
WGSL automation moved this from Needs Discussion to Done Feb 8, 2022
@kdashg
Copy link
Contributor

kdashg commented Feb 16, 2022

WGSL meeting minutes 2022-02-08
* RM: We were strongly opposed to having just loop/continuing, but now that we have for loops, we’re satisfied here. I would like to propose `while` loops, but not needed immediately.
* MM: So therefore, I think we can just close this issue.

ben-clayton pushed a commit to ben-clayton/gpuweb that referenced this issue Sep 6, 2022
* createRenderPipelineAsync validation

Refactor the valitadion of createRenderPipeline, and add validation tests
for createRenderPipelineAsync.

* Code improve

Improve the code, and merge sample_count_must_be_equal_to_the_one_of_every_attachment_in_the_render_pass
in createRenderPipeline.spec.ts into render_pass_or_bundle_and_pipeline,sample_count
in attachment_compatibility.spec.ts.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
wgsl WebGPU Shading Language Issues
Projects
WGSL
Done
Development

No branches or pull requests

9 participants