Bug 201240 – [WHLSL] Add an analysis to verify that functions like control barriers and derivatives are not called in non-uniform control flow.

• Status: RESOLVED
• Resolution: WONTFIX
• Component: WebGPU

[Robin Morisset]

...

[Robin Morisset]

Created attachment 377492 [details]
WIP

Still a few things to do:
- debug a weird timeout that only happens on two tests when they are run automatically with run-webkit-tests (but not when run manually..)
- check that the performance cost of the analysis is negligible
- Improve the error messages
- Add tests for the various corner cases
- Most important: give the right metadata to various native functions.
- See if I can remove the non-const versions of some of the getters for which I added a const version.

[Robin Morisset]

Created attachment 377510 [details]
WIP

[Robin Morisset]

[DONE] debug a weird timeout that only happens on two tests when they are run automatically with run-webkit-tests (but not when run manually..)
 It was fixed by rebasing on ToT
[DONE] check that the performance cost of the analysis is negligible
 It takes about 5% as much time as the type checker
[DONE] Most important: give the right metadata to various native functions.
 It is still missing discard;, because it does not yet exist in the language, see https://bugs.webkit.org/show_bug.cgi?id=201246

[Robin Morisset]

Created attachment 377533 [details]
WIP

Fix stupid bug.

[Robin Morisset]

Created attachment 378025 [details]
Patch

[Robin Morisset]

Created attachment 378404 [details]
Patch

Just fixed some style nits.

[Robin Morisset]

Created attachment 378418 [details]
Patch

Fix an imprecision in the analysis of ternary expressions.

[Robin Morisset]

Created attachment 378426 [details]
Patch

Trivial rebase.

[Saam Barati]

Comment on attachment 378426 [details]
Patch

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

> Source/WebCore/ChangeLog:15
> +        The edges in the graph correspond to implication: A -> B means that if the expression/control-flow/variable corresponding to A must be uniform, then the expression/control-flow/variable corresponding to B must be uniform as well.

I’m a bit confused here. Can you give an example or two?

In the edge A->B, does B depend on A, or does A depend on B?

Like, does B have to be uniform for A to be uniform. Or if A is uniform does that imply B is?

[Robin Morisset]

(In reply to Saam Barati from comment #9)
> Comment on attachment 378426 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=378426&action=review
> 
> > Source/WebCore/ChangeLog:15
> > +        The edges in the graph correspond to implication: A -> B means that if the expression/control-flow/variable corresponding to A must be uniform, then the expression/control-flow/variable corresponding to B must be uniform as well.
> 
> I’m a bit confused here. Can you give an example or two?
> 
> In the edge A->B, does B depend on A, or does A depend on B?
> 
> Like, does B have to be uniform for A to be uniform. Or if A is uniform does
> that imply B is?

It reads '"A must be uniform" implies "B must be uniform"'.
I realize it is a bit backwards to have the node be "X must be uniform" instead of "X is/can be uniform" but it is the trick to being able to compute metadata per-function.

So for example in the code:
if (foo())
  barrier();
else
  {}
There are four nodes:
- A: control-flow before the if
- B: return value of foo()
- C: control-flow within the if branches
- D: control-flow after the if
By the rule for if, we get D -> C, C -> B and C -> A.
By the rule for barriers, we get mustBeUniform -> C
Finally there will be some more implications depending on the metadata for foo().

[Robin Morisset]

> By the rule for if, we get D -> C, C -> B and C -> A.

As discussed with Saam on slack, the D -> C edge will be removed by reconvergence as long as foo() cannot discard. I did not mention it to simplify the example.

[Saam Barati]

Comment on attachment 378426 [details]
Patch

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

I'm just starting to wrap my head around this code. I'm going to continue to review tomorrow, but I will leave a first round of comments.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCodeLocation.h:93
> +        if (m_startOffset != std::numeric_limits<unsigned>::max())

this isn't possible given using 31 bits. I think you just want "if (*this)"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:52
> +    LogScope(String&& string)

should be: const char*

we don't actually want to construct a string here

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:62
> +    String m_string;

ditto

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:65
> +typedef unsigned UniformityNode;

nit: "using UniformityNode = unsigned"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:68
> +    UniformityNode value;

maybe one sentence describing what this is.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:71
> +    // Invariant 2: value -> controlFlow, meaning that the value can only be uniform if the controlFlow is as well.

I don't know what this arrow means. I think you need to explain this invariant more

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:72
> +    UniformityNode controlFlow;

maybe we can name this something like "afterExecution"? controlFlow as a name doesn't imply if it's before or after

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:80
> +    Nothing = 1 << 4,

We discussed this in person, and I suggested naming this something like Normal. But thinking about it more, what about something like NextInstruction?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:82
> +    // TODO: decide whether or not to add an InfiniteLoop behavior.

Please use FIXME instead of TODO (there are a bunch of places with this in this file, I won't comment on all of them).

If these are things that should be addressed, please file a bug for each one and link to it

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:87
> +    // If we want to forbid that kind of thing we can simply add an extra InfiniteLoop behavior to all loops, preventing re-convergence after them.

I don't get why we care. In general, we can't prove if a loop is infinite.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:91
> +    // The order is relevant: the lower the value the more restrictive on call-sites.

can you explain what you mean by "more restrictive on call-sites"?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:103
> +    FunctionMetadataFlag cannotBeUniform;

this is a very weird combination of type and variable name. I'm super confused what it represents. The name sort of implies to me that it should be a boolean, but clearly it isn't

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:125
> +            ASTDumper dumper;
> +            dumper.visit(const_cast<AST::FunctionDefinition&>(functionDefinition));
> +            dataLogLn(dumper.toString());

you want: `dataLogLn(FunctionDefinitionDumper(functionDefinition));`

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:130
> +    // It can also recursively visit all callees of the function.

"all callees of the function"? Do you mean callers? Or things this functions calls?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:162
> +        // What must always be uniform when calling this function?

Can you give more explanation here?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:173
> +            auto node = m_cannotBeUniform;
> +            StringBuilder stringBuilder;
> +            dataLogLn("Uniformity error!");
> +            while (node != m_mustBeUniform) {
> +                dataLogLn("\tBecause of location ", parents[node].second, " (node ", parents[node].first, " -> ", node, ")");
> +                node = parents[node].first;
> +            }

this logging should be under your verbose flag

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:174
> +            return makeUnexpected(Error("This function has a uniformity error "));

nit: remove trailing whitespace in error message

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:175
> +            // TODO: give a good error message.

nit: FIXME instead of TODO. Also, this should go before the above line, not after

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:178
> +        // What must be uniform when calling this function or it discards non-uniformly?

can you give more explanation here?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:182
> +        // What must be uniform when calling this function or it returns a non-uniform value?

can you give more explanation here?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:196
> +        // If there is a single way to exit a statement, it means that any divergence within it is meaningless,
> +        // and as long as we enter it in a uniform way we'll also exit it in a uniform way.

but you're returning what was input. What if the nextControlFlow is something like break? Why would we return what we were before break? I'm a bit confused.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:219
> +            auto controlFlow2 = generateFreshNode();

can we give this a better name. Maybe resultControlfLow?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:221
> +            auto conditionResult = validateRightValueExpression(loop.conditional(), controlFlow2);
> +            auto [controlFlowBody, behaviors] = validateStatement(loop.body(), controlFlow2);

why controlFlow2 here? Shouldn't the body depend on controlFlow, and the condition depend on controlFlowBody?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:284
> +            if (conditionResult.controlFlow != controlFlow)
> +                thenBehaviors.add(Behavior::Discard);

this can only be true if it added discard, right? Why not just merge them and assert it contains discard?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:289
> +            addImplication(resultNode, thenNode, branch.codeLocation());

why don't we need this when there isn't an else?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:314
> +            auto controlFlowExit = generateFreshNode();

I like this name. Would be good to use elsewhere too, like for loops and if

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:319
> +            if (exprResult.controlFlow != controlFlow)
> +                behaviors.add(Behavior::Nothing);

why Discard for this condition above, and Nothing here?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:326
> +                behaviors = behaviors | caseBehaviors;

don't we want to check that each case ends in fall through or break?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:441
> +                } else { // Native function declarations

nit: comment is unnecessary (especially given next LOC casts )

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:514
> +        case AST::Expression::Kind::Index: {

why isn't this sometimes m_cannotBeUniform depending on what we're loading from? (Since it's basically dereference)

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:518
> +            auto baseResult = validateRightValueExpression(indexExpr.base(), controlFlow);
> +            auto indexResult = validateRightValueExpression(indexExpr.indexExpression(), baseResult.controlFlow);

isn't evaluation order the opposite?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:522
> +            return { resultNode, indexResult.controlFlow };

and then this would be base.controlFlow

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:581
> +            if (leftResult.controlFlow == condResult.value && rightResult.controlFlow == condResult.value)
> +                return { resultValue, condResult.controlFlow };

why are you comparing to value and not controlFlow here? These kinds of conditions are confusing me.

for example, take: `variableReference ? a : b`

We'll mark this as discarding since the "value" for the recursive step on `variableReference` will return a value not equal to controlFlow of left/right

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:631
> +            dataLogLn("NOT_REACHED, ", (uint8_t) expr.kind());

nit: static_cast instead of C cast

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:640
> +        Vector<UniformityNode> worklist { source };
> +        dfsFrom(WTFMove(worklist), parents);

style nit: I'd just put this on one line

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:642
> +    void dfsFrom(Vector<UniformityNode>&& worklist, Vector<std::pair<UniformityNode, CodeLocation>>& parents)

rvalue ref is super weird given you don't actually take ownership

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:669
> +    UniformityNode generateFreshNode()

nit: naming suggestion: "nextNode"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:675
> +    void addImplication(UniformityNode source, UniformityNode target, CodeLocation codeLocation = CodeLocation())

this is an edge "source -> target"? Meaning, source depends on target?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:687
> +                case 0:
> +                    return String("mustBeUniform");
> +                case 1:
> +                    return String("cannotBeUniform");
> +                case 2:
> +                    return String("discardUniformity");
> +                case 3:
> +                    return String("controlFlowAtFunctionEntrance");

Why not just compare to the various "m_" fields representing these nodes?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:692
> +            // The semicolon at the end is useful to make vim's "gg=G" command work right.

nit: no need for this comment IMO

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:695
> +        (void) m_implications[source].append(std::make_pair(target, codeLocation));

remove "(void)"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:713
> +Expected<void, Error> checkStatementsAndUniformity(Program& program)

nit: maybe "checkStatementsBehaviorAndUniformity"?

[Saam Barati]

Comment on attachment 378426 [details]
Patch

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

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:252
> +            RELEASE_ASSERT(initBehaviors == Behavior::Nothing);

why is this guaranteed? It can be discard too, no?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:266
> +            addImplication(controlFlow2, controlFlowInit, loop.codeLocation());
> +            auto [controlFlowBody, behaviors] = validateStatement(loop.body(), controlFlow2);
> +            addImplication(controlFlow2, controlFlowBody, loop.codeLocation());
> +
> +            if (loop.condition()) {
> +                auto conditionResult = validateRightValueExpression(*loop.condition(), controlFlow2);
> +                addImplication(controlFlow2, conditionResult.value, loop.codeLocation());
> +                if (conditionResult.controlFlow != controlFlow2)
> +                    behaviors.add(Behavior::Discard);
> +            }
> +            if (loop.increment()) {
> +                auto incrementResult = validateRightValueExpression(*loop.increment(), controlFlow2);

why do all of these take controlFlow2 instead of chaining them in evaluation order?

[Robin Morisset]

Comment on attachment 378426 [details]
Patch

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

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:52
>> +    LogScope(String&& string)
> 
> should be: const char*
> 
> we don't actually want to construct a string here

ok, will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:65
>> +typedef unsigned UniformityNode;
> 
> nit: "using UniformityNode = unsigned"

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:68
>> +    UniformityNode value;
> 
> maybe one sentence describing what this is.

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:71
>> +    // Invariant 2: value -> controlFlow, meaning that the value can only be uniform if the controlFlow is as well.
> 
> I don't know what this arrow means. I think you need to explain this invariant more

This arrow means that if the node 'value' must be uniform, then so must the node 'controlFlow'.
Or said differently that 'controlFlow' cannot be non-uniform if 'value' is uniform.
I will add a sentence about it (it is the same for all implications throughout this file).

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:72
>> +    UniformityNode controlFlow;
> 
> maybe we can name this something like "afterExecution"? controlFlow as a name doesn't imply if it's before or after

Good suggestion, will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:80
>> +    Nothing = 1 << 4,
> 
> We discussed this in person, and I suggested naming this something like Normal. But thinking about it more, what about something like NextInstruction?

NextStatement or Normal, I'm fine with both (we don't have anything called Instruction in the language).
I agree that both are better than the current 'Nothing'.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:82
>> +    // TODO: decide whether or not to add an InfiniteLoop behavior.
> 
> Please use FIXME instead of TODO (there are a bunch of places with this in this file, I won't comment on all of them).
> 
> If these are things that should be addressed, please file a bug for each one and link to it

Will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:87
>> +    // If we want to forbid that kind of thing we can simply add an extra InfiniteLoop behavior to all loops, preventing re-convergence after them.
> 
> I don't get why we care. In general, we can't prove if a loop is infinite.

I agree that we cannot prove if a loop is finite or not. So if infinite loops are a security risk when before a derivatives we would have to conservatively mark all loops as potentially infinite.
In practice I doubt it is needed, but we should look into it. I will open a bug.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:91
>> +    // The order is relevant: the lower the value the more restrictive on call-sites.
> 
> can you explain what you mean by "more restrictive on call-sites"?

"more restrictive on call sites" = "fewer contexts in which it is valid to call this function".
Would it be clearer as an explanation?

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:103
>> +    FunctionMetadataFlag cannotBeUniform;
> 
> this is a very weird combination of type and variable name. I'm super confused what it represents. The name sort of implies to me that it should be a boolean, but clearly it isn't

I agree it is not super well named. maybe whatCannotBeUniform instead?

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:125
>> +            dataLogLn(dumper.toString());
> 
> you want: `dataLogLn(FunctionDefinitionDumper(functionDefinition));`

Thanks!

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:130
>> +    // It can also recursively visit all callees of the function.
> 
> "all callees of the function"? Do you mean callers? Or things this functions calls?

All functions that are called from this one.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:162
>> +        // What must always be uniform when calling this function?
> 
> Can you give more explanation here?

Is it even valid to call this function at all? (if not we error)
Does the control-flow have to be uniform when calling this function?
Which arguments if any must always be uniform when calling this function?

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:173
>> +            }
> 
> this logging should be under your verbose flag

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:174
>> +            return makeUnexpected(Error("This function has a uniformity error "));
> 
> nit: remove trailing whitespace in error message

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:175
>> +            // TODO: give a good error message.
> 
> nit: FIXME instead of TODO. Also, this should go before the above line, not after

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:178
>> +        // What must be uniform when calling this function or it discards non-uniformly?
> 
> can you give more explanation here?

Is it possible to ensure that this function won't discard non-uniformly?
Does it require calling it in uniform control-flow?
Does it require any of its arguments to be uniform?

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:182
>> +        // What must be uniform when calling this function or it returns a non-uniform value?
> 
> can you give more explanation here?

Is it possible to ensure that this function returns a uniform value?
Does it require calling it in uniform control-flow?
Does it require any of its arguments to be uniform?

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:196
>> +        // and as long as we enter it in a uniform way we'll also exit it in a uniform way.
> 
> but you're returning what was input. What if the nextControlFlow is something like break? Why would we return what we were before break? I'm a bit confused.

The behavior tells us _where_ we go next.
The controlFlow node tells us in which circumstance all threads in the threadgroup go to the same place.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:221
>> +            auto [controlFlowBody, behaviors] = validateStatement(loop.body(), controlFlow2);
> 
> why controlFlow2 here? Shouldn't the body depend on controlFlow, and the condition depend on controlFlowBody?

It is a loop, so the control-flow in the condition and in the body depend on each other. In practice it is easiest to have a single one (controlFlow2 above) for everything.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:252
>> +            RELEASE_ASSERT(initBehaviors == Behavior::Nothing);
> 
> why is this guaranteed? It can be discard too, no?

OOPS, good catch, I had not yet added discard to the pass when I wrote this release assert.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:266
>> +                auto incrementResult = validateRightValueExpression(*loop.increment(), controlFlow2);
> 
> why do all of these take controlFlow2 instead of chaining them in evaluation order?

Same as above, it is the trick to deal with loops.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:284
>> +                thenBehaviors.add(Behavior::Discard);
> 
> this can only be true if it added discard, right? Why not just merge them and assert it contains discard?

Because the condition is an expression so it has no behaviors.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:289
>> +            addImplication(resultNode, thenNode, branch.codeLocation());
> 
> why don't we need this when there isn't an else?

Because in that case elseNode would be the same as conditionResult.value, so we would have resultNode -> thenNode and resultNode ->conditionResult.value, but we already have thenNode -> conditionResult.value by construction.
So resultNode would basically be redundant, just pointing to thenNode. We may as well return thenNode directly.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:319
>> +                behaviors.add(Behavior::Nothing);
> 
> why Discard for this condition above, and Nothing here?

Oops, another mistake I did. Should be discard here too, will fix.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:326
>> +                behaviors = behaviors | caseBehaviors;
> 
> don't we want to check that each case ends in fall through or break?

We also accept return/discard. The only behavior that we forbid for this is Nothing, and we do the check in the next case (AST::Statement::Kind::SwitchCase 10 lines below)

[Robin Morisset]

Comment on attachment 378426 [details]
Patch

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

Thank you very much for the thorough review!

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:514
>> +        case AST::Expression::Kind::Index: {
> 
> why isn't this sometimes m_cannotBeUniform depending on what we're loading from? (Since it's basically dereference)

I should double-check this, it is possible that we should return m_cannotBeUniform in the case of array references.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:518
>> +            auto indexResult = validateRightValueExpression(indexExpr.indexExpression(), baseResult.controlFlow);
> 
> isn't evaluation order the opposite?

I am pretty sure that it goes left-to-right, evaluating the base before the index.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:581
>> +                return { resultValue, condResult.controlFlow };
> 
> why are you comparing to value and not controlFlow here? These kinds of conditions are confusing me.
> 
> for example, take: `variableReference ? a : b`
> 
> We'll mark this as discarding since the "value" for the recursive step on `variableReference` will return a value not equal to controlFlow of left/right

Ah, the thing is that we want to compare the controlFlow after the branch to the controlFlow at the beginning of it.
The controlFlow after it is leftResult.controlFlow (as you suggested above I will rename it to something clearer).
The controlFlow at the beginning of it is condResult.value (that is what it means to pass condResult.value in auto leftResult = validateRightValueExpression(ternary.bodyExpression(), condResult.value);.
As long as neither a nor b discard in your example, recursing into them should not allocate new nodes for the control-flow, so they will return the same node returned as the value of the variableReference.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:631
>> +            dataLogLn("NOT_REACHED, ", (uint8_t) expr.kind());
> 
> nit: static_cast instead of C cast

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:640
>> +        dfsFrom(WTFMove(worklist), parents);
> 
> style nit: I'd just put this on one line

will do.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:642
>> +    void dfsFrom(Vector<UniformityNode>&& worklist, Vector<std::pair<UniformityNode, CodeLocation>>& parents)
> 
> rvalue ref is super weird given you don't actually take ownership

I don't see it as this weird, since no-one is using the vector afterwards, but I can take the Vector itself if you prefer.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:675
>> +    void addImplication(UniformityNode source, UniformityNode target, CodeLocation codeLocation = CodeLocation())
> 
> this is an edge "source -> target"? Meaning, source depends on target?

yes source -> target.
Meaning that if source must be uniform then so must target.
Or equivalently that if target cannot be uniform then source cannot be uniform either.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:687
>> +                    return String("controlFlowAtFunctionEntrance");
> 
> Why not just compare to the various "m_" fields representing these nodes?

I think I originally wrote this code outside of the class. You are right that it is absurd, will fix to use the m_ fields.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:713
>> +Expected<void, Error> checkStatementsAndUniformity(Program& program)
> 
> nit: maybe "checkStatementsBehaviorAndUniformity"?

ok, can do.

[Robin Morisset]

Comment on attachment 378426 [details]
Patch

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

>>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:687
>>> +                    return String("controlFlowAtFunctionEntrance");
>> 
>> Why not just compare to the various "m_" fields representing these nodes?
> 
> I think I originally wrote this code outside of the class. You are right that it is absurd, will fix to use the m_ fields.

It turns out to have a reasonable reason after all: 0/1/2/3 are constants (easily usable as cases of a switch), but the m_ fields are not constexpr.

[Saam Barati]

(In reply to Robin Morisset from comment #16)
> Comment on attachment 378426 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=378426&action=review
> 
> >>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:687
> >>> +                    return String("controlFlowAtFunctionEntrance");
> >> 
> >> Why not just compare to the various "m_" fields representing these nodes?
> > 
> > I think I originally wrote this code outside of the class. You are right that it is absurd, will fix to use the m_ fields.
> 
> It turns out to have a reasonable reason after all: 0/1/2/3 are constants
> (easily usable as cases of a switch), but the m_ fields are not constexpr.

Why do you need a switch?

[Robin Morisset]

Created attachment 378585 [details]
Patch

Fix some issues found by Saam

[Saam Barati]

Comment on attachment 378585 [details]
Patch

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

Will continue to review later

> LayoutTests/webgpu/whlsl/js/test-harness.js:299
> +        if (this._device === undefined)
> +            return;

please throw an error here and add the new "_loaded" assert that I added for other things. This is a recent change. Look at https://trac.webkit.org/changeset/249787/webkit

> Source/WebCore/ChangeLog:12
> +        - Some specific expression must return a uniform value (i.e. the same in all thread)

"all thread" => "all threads"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:219
> +            auto controlFlow2 = generateFreshNode();

nit: maybe "loopSummary" as a name?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:252
> +            RELEASE_ASSERT(initBehaviors == Behavior::Nothing);

same as prior review. this looks wrong b/c discard

[Saam Barati]

Comment on attachment 378585 [details]
Patch

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

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:71
> +    // Invariant 2: value -> controlFlow, meaning that the value can only be uniform if the controlFlow is as well.

it's worth a comment in this file on how the whole analysis works. You have this in changelog, but it should live here too. If you have that comment above this, then drawing this graph edge will make sense.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:426
> +            auto leftResult = validateLeftValueExpression(assignment.left(), controlFlow);
> +            auto rightResult = validateRightValueExpression(assignment.right(), leftResult.controlFlow);

shouldn't this order be flipped?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:672
> +        return m_nextValidNode++;

why have this value instead of just using .size() on m_implications? This is the only place that increments/appends to that vector

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:715
> +    HashSet<AST::FunctionDeclaration*> visited;

this seems unused

[Robin Morisset]

(In reply to Saam Barati from comment #19)
> Comment on attachment 378585 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=378585&action=review
> 
> Will continue to review later
> 
> > LayoutTests/webgpu/whlsl/js/test-harness.js:299
> > +        if (this._device === undefined)
> > +            return;
> 
> please throw an error here and add the new "_loaded" assert that I added for
> other things. This is a recent change. Look at
> https://trac.webkit.org/changeset/249787/webkit

will do.

> > Source/WebCore/ChangeLog:12
> > +        - Some specific expression must return a uniform value (i.e. the same in all thread)
> 
> "all thread" => "all threads"

will do.

[Robin Morisset]

(In reply to Saam Barati from comment #20)
> Comment on attachment 378585 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=378585&action=review
> 
> > Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:71
> > +    // Invariant 2: value -> controlFlow, meaning that the value can only be uniform if the controlFlow is as well.
> 
> it's worth a comment in this file on how the whole analysis works. You have
> this in changelog, but it should live here too. If you have that comment
> above this, then drawing this graph edge will make sense.

will do.

> > Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:426
> > +            auto leftResult = validateLeftValueExpression(assignment.left(), controlFlow);
> > +            auto rightResult = validateRightValueExpression(assignment.right(), leftResult.controlFlow);
> 
> shouldn't this order be flipped?

I don't see why? We evaluate the left side before the right side.

> > Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:672
> > +        return m_nextValidNode++;
> 
> why have this value instead of just using .size() on m_implications? This is
> the only place that increments/appends to that vector

Good idea.

> > Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:715
> > +    HashSet<AST::FunctionDeclaration*> visited;
> 
> this seems unused

Good catch, I'm removing it.

[Robin Morisset]

Created attachment 378768 [details]
Patch

Implemented Saam's suggestion + the analysis now supports comma on the left-side of assignment.
I don't believe it is a good idea to have them, but https://bugs.webkit.org/show_bug.cgi?id=201251 introduced them, and dealing with them is much easier than finding how to avoid generating them in that other pass.

[Saam Barati]

Comment on attachment 378768 [details]
Patch

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

r=me

I'd like you to address my earlier comments that weren't addressed before landing. Most of them are uninteresting comments, like creating bugs, and changing TODO to FIXME, etc.

> Source/WebCore/ChangeLog:24
> +        Its error messages are also still terrible, I hope to improve them in a later patch that will make the source accessible to all passes.

please link to a bug for this here

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCodeLocation.h:94
> +        if (m_startOffset != std::numeric_limits<unsigned>::max())
> +            out.print(m_startOffset, "-", m_endOffset);

this is still wrong. See my earlier comment

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLPrepare.cpp:94
> +static constexpr bool alwaysDumpPassFailures = true;

revert this

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:45
> + The former is a fairly straightforward kind of analysis listing for each statement the ways that control-flow can exit it (its "Behaviors"), in order to forbid things like "continue;" outside of loops, reaching the end of non-void functions, "fallthrough;" outside of switches, etc..

"etc.." => "etc."

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:56
> + 17

remove

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:89
> +    // Invariant 2: value -> controlFlow, meaning that the value can only be uniform if the controlFlow is as well.

"controlFlow" => "controlFlowAfter"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:101
> +    // TODO: decide whether or not to add an InfiniteLoop behavior.

As I mentioned in prior comments, these should be FIXMEs. All ideally linking to a bug

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:126
> +    // so controlFlow is always MustBeUniformToReturnUniformly or lower.

"or lower" => "or lower for non-void functions"

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:146
> +            ASTDumper dumper;
> +            dumper.visit(const_cast<AST::FunctionDefinition&>(functionDefinition));
> +            dataLogLn(dumper.toString());

same comment as prior comment

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:155
> +        if (m_functionMetadata.contains(&m_functionDefinition))
> +            return m_functionMetadata.get(&m_functionDefinition);

you should avoid two hash lookups here by doing:

{
    auto iter = m_functionMetadata.find(&m_functionDefinition);
    if (item != m_functionMetadata.end())
        return iter->value;
}

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:163
> +            RELEASE_ASSERT(node);

why?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:196
> +            auto node = m_cannotBeUniform;
> +            StringBuilder stringBuilder;
> +            dataLogLn("Uniformity error!");
> +            while (node != m_mustBeUniform) {
> +                dataLogLn("\tBecause of location ", parents[node].second, " (node ", parents[node].first, " -> ", node, ")");
> +                node = parents[node].first;
> +            }
> +            return makeUnexpected(Error("This function has a uniformity error "));
> +            // TODO: give a good error message.

you didn't address my comments here from previous patch

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:430
> +        const auto& lastStatement = statements[statements.size() - 1];

nit: you want .last()

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:465
> +                } else { // Native function declarations

same as previous nit: no need for this comment

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLStatementBehaviorChecker.cpp:656
> +            // FIXME: we should never arrive here, but for now I have this code as a work-around for a bug in the property resolver.

can you just run this before the property resolver? Seems like there is no need for this code. PropertyResolver should not change the uniformity of programs.

[Myles C. Maxfield]

WHLSL is no longer relevant.