Bug 193487 – [WHLSL] Add the statement behavior checker

• Component: New Bugs
• Status: RESOLVED FIXED

[Myles C. Maxfield]

[WHLSL] Add the statement behavior checker

[Myles C. Maxfield]

Created attachment 359262 [details]
Patch

[Myles C. Maxfield]

*** Bug 193437 has been marked as a duplicate of this bug. ***

[Robin Morisset]

Comment on attachment 359262 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359262&action=review

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:96
> +        // FIXME: The spec says to add "Nothing" here, but I think the spec is wrong.

Consider the following case:
```
do {
  break;
} while (true);
```

This code would clearly have the behavior {Nothing} (meaning that control-flow can flow to the next statement), but the loop body only has the behavior {Break}.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:103
> +        auto initialization = WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) -> Optional<OptionSet<Behavior>> {

I am not sure I completely understand this code. Does it work correctly for loops like for(;;) { ... if(foo) break; } ?
In which case is the if(!initialization) case hit?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:136
> +    void visit(AST::SwitchCase& switchCase) override

What is the point of this override?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:162
> +        // FIXME: The spec says to add "Nothing" here, but I think the spec is wrong.

Same comment as for loops above: the following code must have a behavior of {Nothing}:
```
switch(x) {
default:
break;
}
```

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:232
> +            continue;

I disagree, even void functions must have the behaviors of their bodies checked.
In particular, we must verify that there is no break/continue/fallthrough that are outside of a loop/switch in their bodies.
I would unconditionally run the statementBehaviorChecker, just later tolerate Nothing in the set of behaviors for the function body if the function has a return type of void.

[Myles C. Maxfield]

Comment on attachment 359262 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359262&action=review

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:96
>> +        // FIXME: The spec says to add "Nothing" here, but I think the spec is wrong.
> 
> Consider the following case:
> ```
> do {
>   break;
> } while (true);
> ```
> 
> This code would clearly have the behavior {Nothing} (meaning that control-flow can flow to the next statement), but the loop body only has the behavior {Break}.

On the other hand,
```
int foo() {
  do {
    return 42;
  } while (true);
}
```
should be correct, but the current analysis would say this program is incorrect.

It should probably add Nothing only conditionally, perhaps if the result after removing Break and Continue is the empty set.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:103
>> +        auto initialization = WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) -> Optional<OptionSet<Behavior>> {
> 
> I am not sure I completely understand this code. Does it work correctly for loops like for(;;) { ... if(foo) break; } ?
> In which case is the if(!initialization) case hit?

The grammar says:
forStmt: FOR '(' (variableDecls | effectfulExpr) ';' expr? ';' expr? ')' stmt ;
I believe that, given that grammar, "for(;;)" would fail to parse.

variableDecls maps to { Nothing } and effectfulExpr maps to { Nothing } as well, which I think is fine because for loops may execute 0 times (unless we want to try to go down the rabbit hole of interrogating the condition to determine if the loop will execute or not)

This visitor is just determining whether the initialization is a variableDecls or an effectfulExpr. Expressions are not statements, so it doesn't recurse in that case, but a VariableDeclarationsStatement is a statement, so it recurses in that case. If the recusion causes error(), this visitor returns nullopt, so we can take an early out below.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:136
>> +    void visit(AST::SwitchCase& switchCase) override
> 
> What is the point of this override?

Just clarity. I wanted to be explicit that I didn't just forget to write the function.

[Myles C. Maxfield]

Created attachment 359342 [details]
Patch

[Robin Morisset]

(In reply to Myles C. Maxfield from comment #4)
> Comment on attachment 359262 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=359262&action=review
> 
> >> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:96
> >> +        // FIXME: The spec says to add "Nothing" here, but I think the spec is wrong.
> > 
> > Consider the following case:
> > ```
> > do {
> >   break;
> > } while (true);
> > ```
> > 
> > This code would clearly have the behavior {Nothing} (meaning that control-flow can flow to the next statement), but the loop body only has the behavior {Break}.
> 
> On the other hand,
> ```
> int foo() {
>   do {
>     return 42;
>   } while (true);
> }
> ```
> should be correct, but the current analysis would say this program is
> incorrect.
> 
> It should probably add Nothing only conditionally, perhaps if the result
> after removing Break and Continue is the empty set.

That would indeed be more precise, I am just not sure it is required to reach that level of precision right now (as long as we err in the safe direction of rejected too many programs).

> 
> >> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:103
> >> +        auto initialization = WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) -> Optional<OptionSet<Behavior>> {
> > 
> > I am not sure I completely understand this code. Does it work correctly for loops like for(;;) { ... if(foo) break; } ?
> > In which case is the if(!initialization) case hit?
> 
> The grammar says:
> forStmt: FOR '(' (variableDecls | effectfulExpr) ';' expr? ';' expr? ')'
> stmt ;
> I believe that, given that grammar, "for(;;)" would fail to parse.
> 
> variableDecls maps to { Nothing } and effectfulExpr maps to { Nothing } as
> well, which I think is fine because for loops may execute 0 times (unless we
> want to try to go down the rabbit hole of interrogating the condition to
> determine if the loop will execute or not)
> 
> This visitor is just determining whether the initialization is a
> variableDecls or an effectfulExpr. Expressions are not statements, so it
> doesn't recurse in that case, but a VariableDeclarationsStatement is a
> statement, so it recurses in that case. If the recusion causes error(), this
> visitor returns nullopt, so we can take an early out below.

Variable declarations are a very special kind of statement. In particular, this checker will never do anything but return {Nothing} on them. In particular I don't expect it to
ever error. So I would just not recurse on it and skip this check.

> 
> >> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:136
> >> +    void visit(AST::SwitchCase& switchCase) override
> > 
> > What is the point of this override?
> 
> Just clarity. I wanted to be explicit that I didn't just forget to write the
> function.

Ok, I personally found it more confusing than if there was nothing, but it is your choice.

[Myles C. Maxfield]

(In reply to Robin Morisset from comment #6)
> (In reply to Myles C. Maxfield from comment #4)
> > Comment on attachment 359262 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=359262&action=review
> > 
> > >> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:96
> > >> +        // FIXME: The spec says to add "Nothing" here, but I think the spec is wrong.
> > > 
> > > Consider the following case:
> > > ```
> > > do {
> > >   break;
> > > } while (true);
> > > ```
> > > 
> > > This code would clearly have the behavior {Nothing} (meaning that control-flow can flow to the next statement), but the loop body only has the behavior {Break}.
> > 
> > On the other hand,
> > ```
> > int foo() {
> >   do {
> >     return 42;
> >   } while (true);
> > }
> > ```
> > should be correct, but the current analysis would say this program is
> > incorrect.
> > 
> > It should probably add Nothing only conditionally, perhaps if the result
> > after removing Break and Continue is the empty set.
> 
> That would indeed be more precise, I am just not sure it is required to
> reach that level of precision right now (as long as we err in the safe
> direction of rejected too many programs).

https://github.com/gpuweb/WHLSL/issues/314

[Myles C. Maxfield]

Created attachment 359564 [details]
Patch

[Myles C. Maxfield]

Comment on attachment 359564 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359564&action=review

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:112
> +        m_stack.append(OptionSet<Behavior>::fromRaw(initialization->toRaw() | b.toRaw()));

Whoops, this should be m_stack.append(b);

[Myles C. Maxfield]

Created attachment 359645 [details]
Patch

[Dean Jackson]

Comment on attachment 359645 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=359645&action=review

> Source/WebCore/ChangeLog:19
> +        * Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp: Added.
> +        (WebCore::WHLSL::StatementBehaviorChecker::takeFunctionBehavior):
> +        (WebCore::WHLSL::checkStatementBehavior):
> +        * Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.h: Added.
> +        * Sources.txt:
> +        * WebCore.xcodeproj/project.pbxproj:

Why doesn't this mention WHLSLLoopChecker's removal?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:145
> +            reduction = OptionSet<Behavior>::fromRaw(reduction.toRaw() | b.toRaw());

I believe you can do reduction |= b;
constexpr friend OptionSet operator|(OptionSet lhs, OptionSet rhs)

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:171
> +        m_stack.append(OptionSet<Behavior>::fromRaw(b.toRaw() | bPrime.toRaw()));

Ditto.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:201
> +            reduction = OptionSet<Behavior>::fromRaw(reduction.toRaw() | b.toRaw());

Ditto.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:207
> +        m_stack.append(OptionSet<Behavior>::fromRaw(reduction.toRaw() | b.toRaw()));

Ditto.

[Myles C. Maxfield]

Committed r240227: <https://trac.webkit.org/changeset/240227>

[Radar WebKit Bug Importer]

<rdar://problem/47420528>