Changeset 246121 in webkit


Ignore:
Timestamp:
Jun 5, 2019 11:36:29 AM (5 years ago)
Author:
sbarati@apple.com
Message:

[WHLSL] Implement loop expressions
https://bugs.webkit.org/show_bug.cgi?id=195808
<rdar://problem/50746309>

Reviewed by Myles Maxfield.

Source/WebCore:

This patch makes continue/break break for "do/while/for" loops
in WHLSL. Because of the way we emit code where every expression
turns into a Metal statement, it's not convenient to emit native
Metal loop constructs. Instead, we model break/continue as if
we had goto.

For example, this WHLSL program:
`
for (INIT; COND; INC) {

if (b)

continue;

if (b2)

break;

}
`
would become something like:
`
INIT;
while (1) {

if (!COND)

break;

if (b)

goto increment;

if (b2)

goto exit;

increment:

INC;

}
exit:
`

However, Metal doesn't have goto, so we model goto using a run-once
loop and a variable indicating if we should break out early. This
"break out early" variable is initially set to false. We "should
break out early" when executing a WHLSL "break" statement. "continue"
is modeled as breaking out of the run-once loop, but not touching the
"break out early" variable. "break" is modeled as setting the "break
out early" variable to true, followed by breaking out of the run-once loop.
The above WHLSL will turn into this Metal:
`
bool breakOutOfCurrentLoop = false;
INIT;
while (1) {

if (!COND)

break;

do {

if (b) {

WHLSL 'continue'
break;

}
if (b2) {

WHLSL 'break'
breakOutOfCurrentLoop = true;
break;

}

} while (0);
if (breakOutOfCurrentLoop)

break;

INC;

}
`

This patch also found a bug with ForLoop where it held a Variant<VariableDeclarationsStatement, Expression>.
This is invalid to do since we mutate the AST in place. This means some phase
could replace VariableDeclarationsStatement with some other Statement, and
we'd be breaking the C++ type system. So this patch migrates ForLoop to hold
a statement instead. In general, AST nodes that point to other AST nodes
should use broad types unless we know apriori that a certain type will
never be replaced.

Tests: webgpu/whlsl-do-while-loop-break.html

webgpu/whlsl-do-while-loop-continue.html
webgpu/whlsl-do-while-loop.html
webgpu/whlsl-loops-break.html
webgpu/whlsl-loops-continue.html
webgpu/whlsl-loops.html
webgpu/whlsl-nested-loop.html
webgpu/whlsl-while-loop-break.html
webgpu/whlsl-while-loop-continue.html

  • Modules/webgpu/WHLSL/AST/WHLSLForLoop.h:

(WebCore::WHLSL::AST::ForLoop::ForLoop):
(WebCore::WHLSL::AST::ForLoop::initialization):

  • Modules/webgpu/WHLSL/Metal/WHLSLFunctionWriter.cpp:

(WebCore::WHLSL::Metal::FunctionDefinitionWriter::visit):
(WebCore::WHLSL::Metal::FunctionDefinitionWriter::emitLoop):

  • Modules/webgpu/WHLSL/WHLSLASTDumper.cpp:

(WebCore::WHLSL::ASTDumper::visit):

  • Modules/webgpu/WHLSL/WHLSLChecker.cpp:

(WebCore::WHLSL::Checker::visit):

  • Modules/webgpu/WHLSL/WHLSLParser.cpp:

(WebCore::WHLSL::Parser::parseForLoop):

  • Modules/webgpu/WHLSL/WHLSLPrepare.cpp:
  • Modules/webgpu/WHLSL/WHLSLStandardLibrary.txt:
  • Modules/webgpu/WHLSL/WHLSLVisitor.cpp:

(WebCore::WHLSL::Visitor::visit):

LayoutTests:

  • webgpu/whlsl-do-while-loop-break-expected.html: Added.
  • webgpu/whlsl-do-while-loop-break.html: Added.
  • webgpu/whlsl-do-while-loop-continue-expected.html: Added.
  • webgpu/whlsl-do-while-loop-continue.html: Added.
  • webgpu/whlsl-do-while-loop-expected.html: Added.
  • webgpu/whlsl-do-while-loop.html: Added.
  • webgpu/whlsl-loops-break-expected.html: Added.
  • webgpu/whlsl-loops-break.html: Added.
  • webgpu/whlsl-loops-continue-expected.html: Added.
  • webgpu/whlsl-loops-continue.html: Added.
  • webgpu/whlsl-loops-expected.html: Added.
  • webgpu/whlsl-loops.html: Added.
  • webgpu/whlsl-nested-loop-expected.html: Added.
  • webgpu/whlsl-nested-loop.html: Added.
  • webgpu/whlsl-while-loop-break-expected.html: Added.
  • webgpu/whlsl-while-loop-break.html: Added.
  • webgpu/whlsl-while-loop-continue-expected.html: Added.
  • webgpu/whlsl-while-loop-continue.html: Added.
Location:
trunk
Files:
18 added
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/LayoutTests/ChangeLog

    r246118 r246121  
     12019-06-05  Saam Barati  <sbarati@apple.com>
     2
     3        [WHLSL] Implement loop expressions
     4        https://bugs.webkit.org/show_bug.cgi?id=195808
     5        <rdar://problem/50746309>
     6
     7        Reviewed by Myles Maxfield.
     8
     9        * webgpu/whlsl-do-while-loop-break-expected.html: Added.
     10        * webgpu/whlsl-do-while-loop-break.html: Added.
     11        * webgpu/whlsl-do-while-loop-continue-expected.html: Added.
     12        * webgpu/whlsl-do-while-loop-continue.html: Added.
     13        * webgpu/whlsl-do-while-loop-expected.html: Added.
     14        * webgpu/whlsl-do-while-loop.html: Added.
     15        * webgpu/whlsl-loops-break-expected.html: Added.
     16        * webgpu/whlsl-loops-break.html: Added.
     17        * webgpu/whlsl-loops-continue-expected.html: Added.
     18        * webgpu/whlsl-loops-continue.html: Added.
     19        * webgpu/whlsl-loops-expected.html: Added.
     20        * webgpu/whlsl-loops.html: Added.
     21        * webgpu/whlsl-nested-loop-expected.html: Added.
     22        * webgpu/whlsl-nested-loop.html: Added.
     23        * webgpu/whlsl-while-loop-break-expected.html: Added.
     24        * webgpu/whlsl-while-loop-break.html: Added.
     25        * webgpu/whlsl-while-loop-continue-expected.html: Added.
     26        * webgpu/whlsl-while-loop-continue.html: Added.
     27
    1282019-06-05  Wenson Hsieh  <wenson_hsieh@apple.com>
    229
  • trunk/Source/WebCore/ChangeLog

    r246118 r246121  
     12019-06-05  Saam Barati  <sbarati@apple.com>
     2
     3        [WHLSL] Implement loop expressions
     4        https://bugs.webkit.org/show_bug.cgi?id=195808
     5        <rdar://problem/50746309>
     6
     7        Reviewed by Myles Maxfield.
     8
     9        This patch makes continue/break break for "do/while/for" loops
     10        in WHLSL. Because of the way we emit code where every expression
     11        turns into a Metal statement, it's not convenient to emit native
     12        Metal loop constructs. Instead, we model break/continue as if
     13        we had goto.
     14       
     15        For example, this WHLSL program:
     16        ```
     17        for (INIT; COND; INC) {
     18            if (b)
     19                continue;
     20            if (b2)
     21                break;
     22        }
     23        ```
     24        would become something like:
     25        ```
     26        INIT;
     27        while (1) {
     28            if (!COND)
     29                break;
     30            if (b)
     31                goto increment;
     32            if (b2)
     33                goto exit;
     34        increment:
     35            INC;
     36        }
     37        exit:
     38        ```
     39       
     40        However, Metal doesn't have goto, so we model goto using a run-once
     41        loop and a variable indicating if we should break out early. This
     42        "break out early" variable is initially set to false. We "should
     43        break out early" when executing a WHLSL "break" statement. "continue"
     44        is modeled as breaking out of the run-once loop, but not touching the
     45        "break out early" variable. "break" is modeled as setting the "break
     46        out early" variable to true, followed by breaking out of the run-once loop.
     47        The above WHLSL will turn into this Metal:
     48        ```
     49        bool breakOutOfCurrentLoop = false;
     50        INIT;
     51        while (1) {
     52            if (!COND)
     53                break;
     54            do {
     55                if (b) {
     56                    // WHLSL 'continue'
     57                    break;
     58                }
     59                if (b2) {
     60                    // WHLSL 'break'
     61                    breakOutOfCurrentLoop = true;
     62                    break;
     63                }
     64            } while (0);
     65            if (breakOutOfCurrentLoop)
     66                break;
     67            INC;
     68        }
     69        ```
     70       
     71        This patch also found a bug with ForLoop where it held a Variant<VariableDeclarationsStatement, Expression>.
     72        This is invalid to do since we mutate the AST in place. This means some phase
     73        could replace VariableDeclarationsStatement with some other Statement, and
     74        we'd be breaking the C++ type system. So this patch migrates ForLoop to hold
     75        a statement instead. In general, AST nodes that point to other AST nodes
     76        should use broad types unless we know apriori that a certain type will
     77        never be replaced.
     78
     79        Tests: webgpu/whlsl-do-while-loop-break.html
     80               webgpu/whlsl-do-while-loop-continue.html
     81               webgpu/whlsl-do-while-loop.html
     82               webgpu/whlsl-loops-break.html
     83               webgpu/whlsl-loops-continue.html
     84               webgpu/whlsl-loops.html
     85               webgpu/whlsl-nested-loop.html
     86               webgpu/whlsl-while-loop-break.html
     87               webgpu/whlsl-while-loop-continue.html
     88
     89        * Modules/webgpu/WHLSL/AST/WHLSLForLoop.h:
     90        (WebCore::WHLSL::AST::ForLoop::ForLoop):
     91        (WebCore::WHLSL::AST::ForLoop::initialization):
     92        * Modules/webgpu/WHLSL/Metal/WHLSLFunctionWriter.cpp:
     93        (WebCore::WHLSL::Metal::FunctionDefinitionWriter::visit):
     94        (WebCore::WHLSL::Metal::FunctionDefinitionWriter::emitLoop):
     95        * Modules/webgpu/WHLSL/WHLSLASTDumper.cpp:
     96        (WebCore::WHLSL::ASTDumper::visit):
     97        * Modules/webgpu/WHLSL/WHLSLChecker.cpp:
     98        (WebCore::WHLSL::Checker::visit):
     99        * Modules/webgpu/WHLSL/WHLSLParser.cpp:
     100        (WebCore::WHLSL::Parser::parseForLoop):
     101        * Modules/webgpu/WHLSL/WHLSLPrepare.cpp:
     102        * Modules/webgpu/WHLSL/WHLSLStandardLibrary.txt:
     103        * Modules/webgpu/WHLSL/WHLSLVisitor.cpp:
     104        (WebCore::WHLSL::Visitor::visit):
     105
    11062019-06-05  Wenson Hsieh  <wenson_hsieh@apple.com>
    2107
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLForLoop.h

    r239930 r246121  
    4545class ForLoop : public Statement {
    4646public:
    47     ForLoop(Lexer::Token&& origin, Variant<VariableDeclarationsStatement, UniqueRef<Expression>>&& initialization, Optional<UniqueRef<Expression>>&& condition, Optional<UniqueRef<Expression>>&& increment, UniqueRef<Statement>&& body)
     47    ForLoop(Lexer::Token&& origin, Variant<UniqueRef<Statement>, UniqueRef<Expression>>&& initialization, Optional<UniqueRef<Expression>>&& condition, Optional<UniqueRef<Expression>>&& increment, UniqueRef<Statement>&& body)
    4848        : Statement(WTFMove(origin))
    4949        , m_initialization(WTFMove(initialization))
     
    6363    bool isForLoop() const override { return true; }
    6464
    65     Variant<VariableDeclarationsStatement, UniqueRef<Expression>>& initialization() { return m_initialization; }
     65    Variant<UniqueRef<Statement>, UniqueRef<Expression>>& initialization() { return m_initialization; }
    6666    Expression* condition() { return m_condition ? &*m_condition : nullptr; }
    6767    Expression* increment() { return m_increment ? &*m_increment : nullptr; }
     
    6969
    7070private:
    71     Variant<VariableDeclarationsStatement, UniqueRef<Expression>> m_initialization;
     71    Variant<UniqueRef<Statement>, UniqueRef<Expression>> m_initialization;
    7272    Optional<UniqueRef<Expression>> m_condition;
    7373    Optional<UniqueRef<Expression>> m_increment;
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/Metal/WHLSLFunctionWriter.cpp

    r245973 r246121  
    3636#include "WHLSLVisitor.h"
    3737#include <wtf/HashMap.h>
     38#include <wtf/SetForScope.h>
    3839#include <wtf/text/StringBuilder.h>
    3940
     
    140141    void visit(AST::VariableReference&) override;
    141142
     143    enum class LoopConditionLocation {
     144        BeforeBody,
     145        AfterBody
     146    };
     147    void emitLoop(LoopConditionLocation, AST::Expression* conditionExpression, AST::Expression* increment, AST::Statement& body);
     148
    142149    String constantExpressionString(AST::ConstantExpression&);
    143150
     
    156163    Layout& m_layout;
    157164    unsigned m_variableCount { 0 };
     165    String m_breakOutOfCurrentLoopEarlyVariable;
    158166};
    159167
     
    225233void FunctionDefinitionWriter::visit(AST::Break&)
    226234{
     235    ASSERT(m_breakOutOfCurrentLoopEarlyVariable.length());
     236    m_stringBuilder.append(makeString(m_breakOutOfCurrentLoopEarlyVariable, " = true;\n"));
    227237    m_stringBuilder.append("break;\n");
    228238}
     
    230240void FunctionDefinitionWriter::visit(AST::Continue&)
    231241{
    232     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=195808 Figure out which loop we're in, and run the increment code
    233     notImplemented();
    234 }
    235 
    236 void FunctionDefinitionWriter::visit(AST::DoWhileLoop& doWhileLoop)
    237 {
    238     m_stringBuilder.append("do {\n");
    239     checkErrorAndVisit(doWhileLoop.body());
    240     checkErrorAndVisit(doWhileLoop.conditional());
    241     m_stringBuilder.append(makeString("if (!", m_stack.takeLast(), ") break;\n"));
    242     m_stringBuilder.append(makeString("} while(true);\n"));
     242    ASSERT(m_breakOutOfCurrentLoopEarlyVariable.length());
     243    m_stringBuilder.append("break;\n");
    243244}
    244245
     
    254255}
    255256
     257void FunctionDefinitionWriter::emitLoop(LoopConditionLocation loopConditionLocation, AST::Expression* conditionExpression, AST::Expression* increment, AST::Statement& body)
     258{
     259    SetForScope<String> loopVariableScope(m_breakOutOfCurrentLoopEarlyVariable, generateNextVariableName());
     260
     261    m_stringBuilder.append(makeString("bool ", m_breakOutOfCurrentLoopEarlyVariable, " = false;\n"));
     262
     263    m_stringBuilder.append("while (true) {\n");
     264
     265    if (loopConditionLocation == LoopConditionLocation::BeforeBody && conditionExpression) {
     266        checkErrorAndVisit(*conditionExpression);
     267        m_stringBuilder.append(makeString("if (!", m_stack.takeLast(), ") break;\n"));
     268    }
     269
     270    m_stringBuilder.append("do {\n");
     271    checkErrorAndVisit(body);
     272    m_stringBuilder.append("} while(false); \n");
     273    m_stringBuilder.append(makeString("if (", m_breakOutOfCurrentLoopEarlyVariable, ") break;\n"));
     274
     275    if (increment) {
     276        checkErrorAndVisit(*increment);
     277        // Expression results get pushed to m_stack. We don't use the result
     278        // of increment, so we dispense of that now.
     279        m_stack.takeLast();
     280    }
     281
     282    if (loopConditionLocation == LoopConditionLocation::AfterBody && conditionExpression) {
     283        checkErrorAndVisit(*conditionExpression);
     284        m_stringBuilder.append(makeString("if (!", m_stack.takeLast(), ") break;\n"));
     285    }
     286
     287    m_stringBuilder.append("} \n");
     288}
     289
     290void FunctionDefinitionWriter::visit(AST::DoWhileLoop& doWhileLoop)
     291{
     292    emitLoop(LoopConditionLocation::AfterBody, &doWhileLoop.conditional(), nullptr, doWhileLoop.body());
     293}
     294
     295void FunctionDefinitionWriter::visit(AST::WhileLoop& whileLoop)
     296{
     297    emitLoop(LoopConditionLocation::BeforeBody, &whileLoop.conditional(), nullptr, whileLoop.body());
     298}
     299
    256300void FunctionDefinitionWriter::visit(AST::ForLoop& forLoop)
    257301{
    258     WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) {
    259         checkErrorAndVisit(variableDeclarationsStatement);
     302    m_stringBuilder.append("{\n");
     303
     304    WTF::visit(WTF::makeVisitor([&](AST::Statement& statement) {
     305        checkErrorAndVisit(statement);
    260306    }, [&](UniqueRef<AST::Expression>& expression) {
    261307        checkErrorAndVisit(expression);
     
    263309    }), forLoop.initialization());
    264310
    265     m_stringBuilder.append("for ( ; ; ) {\n");
    266     if (forLoop.condition()) {
    267         checkErrorAndVisit(*forLoop.condition());
    268         m_stringBuilder.append(makeString("if (!", m_stack.takeLast(), ") break;\n"));
    269     }
    270     checkErrorAndVisit(forLoop.body());
    271     if (forLoop.increment()) {
    272         checkErrorAndVisit(*forLoop.increment());
    273         m_stack.takeLast();
    274     }
     311    emitLoop(LoopConditionLocation::BeforeBody, forLoop.condition(), forLoop.increment(), forLoop.body());
    275312    m_stringBuilder.append("}\n");
    276313}
     
    332369{
    333370    Visitor::visit(variableDeclarationsStatement);
    334 }
    335 
    336 void FunctionDefinitionWriter::visit(AST::WhileLoop& whileLoop)
    337 {
    338     m_stringBuilder.append(makeString("while (true) {\n"));
    339     checkErrorAndVisit(whileLoop.conditional());
    340     m_stringBuilder.append(makeString("if (!", m_stack.takeLast(), ") break;\n"));
    341     checkErrorAndVisit(whileLoop.body());
    342     m_stringBuilder.append("}\n");
    343371}
    344372
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLASTDumper.cpp

    r245945 r246121  
    414414{
    415415    m_out.print("for (");
    416     WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) {
    417         visit(variableDeclarationsStatement);
     416    WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::Statement>& statement) {
     417        visit(statement);
    418418    }, [&](UniqueRef<AST::Expression>& expression) {
    419419        visit(expression);
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLChecker.cpp

    r245844 r246121  
    11901190void Checker::visit(AST::ForLoop& forLoop)
    11911191{
    1192     WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) {
    1193         checkErrorAndVisit(variableDeclarationsStatement);
     1192    WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::Statement>& statement) {
     1193        checkErrorAndVisit(statement);
    11941194    }, [&](UniqueRef<AST::Expression>& expression) {
    11951195        checkErrorAndVisit(expression);
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLParser.cpp

    r246108 r246121  
    14151415        return Unexpected<Error>(origin.error());
    14161416
    1417     auto parseRemainder = [&](Variant<AST::VariableDeclarationsStatement, UniqueRef<AST::Expression>>&& initialization) -> Expected<AST::ForLoop, Error> {
     1417    auto parseRemainder = [&](Variant<UniqueRef<AST::Statement>, UniqueRef<AST::Expression>>&& initialization) -> Expected<AST::ForLoop, Error> {
    14181418        auto semicolon = consumeType(Lexer::Token::Type::Semicolon);
    14191419        if (!semicolon)
     
    14541454        return parseVariableDeclarations();
    14551455    });
    1456     if (variableDeclarations)
    1457         return parseRemainder(WTFMove(*variableDeclarations));
     1456    if (variableDeclarations) {
     1457        UniqueRef<AST::Statement> declarationStatement = makeUniqueRef<AST::VariableDeclarationsStatement>(WTFMove(*variableDeclarations));
     1458        return parseRemainder(WTFMove(declarationStatement));
     1459    }
    14581460
    14591461    auto effectfulExpression = parseEffectfulExpression();
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLPrepare.cpp

    r245945 r246121  
    5858static constexpr bool dumpASTBeforeEachPass = false;
    5959static constexpr bool dumpASTAfterParsing = false;
    60 static constexpr bool dumpASTAtEnd = true;
     60static constexpr bool dumpASTAtEnd = false;
    6161static constexpr bool alwaysDumpPassFailures = false;
    6262static constexpr bool dumpPassFailure = dumpASTBeforeEachPass || dumpASTAfterParsing || dumpASTAtEnd || alwaysDumpPassFailures;
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLStandardLibrary.txt

    r245680 r246121  
    385385native float4 operator.w=(float4, float);
    386386
     387native float operator+(float, float);
     388native float operator-(float, float);
     389native int operator+(int, int);
     390native uint operator+(uint, uint);
     391native bool operator<(int, int);
     392native bool operator<(uint, uint);
     393native bool operator<(float, float);
     394
    387395native float ddx(float);
    388396native float ddy(float);
  • trunk/Source/WebCore/Modules/webgpu/WHLSL/WHLSLVisitor.cpp

    r245945 r246121  
    435435void Visitor::visit(AST::ForLoop& forLoop)
    436436{
    437     WTF::visit(WTF::makeVisitor([&](AST::VariableDeclarationsStatement& variableDeclarationsStatement) {
    438         checkErrorAndVisit(variableDeclarationsStatement);
     437    WTF::visit(WTF::makeVisitor([&](UniqueRef<AST::Statement>& statement) {
     438        checkErrorAndVisit(statement);
    439439    }, [&](UniqueRef<AST::Expression>& expression) {
    440440        checkErrorAndVisit(expression);
Note: See TracChangeset for help on using the changeset viewer.