Bug 193487 - [WHLSL] Add the statement behavior checker
Summary: [WHLSL] Add the statement behavior checker
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Myles C. Maxfield
URL:
Keywords: InRadar
: 193437 (view as bug list)
Depends on:
Blocks:
 
Reported: 2019-01-16 02:42 PST by Myles C. Maxfield
Modified: 2019-01-20 21:41 PST (History)
7 users (show)

See Also:


Attachments
Patch (22.12 KB, patch)
2019-01-16 02:44 PST, Myles C. Maxfield
no flags Details | Formatted Diff | Diff
Patch (37.16 KB, patch)
2019-01-16 18:59 PST, Myles C. Maxfield
no flags Details | Formatted Diff | Diff
Patch (23.39 KB, patch)
2019-01-18 17:42 PST, Myles C. Maxfield
no flags Details | Formatted Diff | Diff
Patch (23.31 KB, patch)
2019-01-20 13:12 PST, Myles C. Maxfield
dino: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Myles C. Maxfield 2019-01-16 02:42:07 PST
[WHLSL] Add the statement behavior checker
Comment 1 Myles C. Maxfield 2019-01-16 02:44:11 PST
Created attachment 359262 [details]
Patch
Comment 2 Myles C. Maxfield 2019-01-16 02:44:50 PST
*** Bug 193437 has been marked as a duplicate of this bug. ***
Comment 3 Robin Morisset 2019-01-16 10:50:43 PST
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.
Comment 4 Myles C. Maxfield 2019-01-16 18:49:47 PST
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.
Comment 5 Myles C. Maxfield 2019-01-16 18:59:22 PST
Created attachment 359342 [details]
Patch
Comment 6 Robin Morisset 2019-01-17 10:22:48 PST
(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.
Comment 7 Myles C. Maxfield 2019-01-18 17:30:21 PST
(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
Comment 8 Myles C. Maxfield 2019-01-18 17:42:20 PST
Created attachment 359564 [details]
Patch
Comment 9 Myles C. Maxfield 2019-01-18 18:08:34 PST
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);
Comment 10 Myles C. Maxfield 2019-01-20 13:12:26 PST
Created attachment 359645 [details]
Patch
Comment 11 Dean Jackson 2019-01-20 16:23:42 PST
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.
Comment 12 Myles C. Maxfield 2019-01-20 21:40:26 PST
Committed r240227: <https://trac.webkit.org/changeset/240227>
Comment 13 Radar WebKit Bug Importer 2019-01-20 21:41:28 PST
<rdar://problem/47420528>