[webkit-changes] [WebKit/WebKit] 46e2ec: [WGSL] Add new pass to sort global variables, stru...

[Tadeu Zagallo]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 46e2ecf4659831e5fbcf6701f47670a99c952590
      https://github.com/WebKit/WebKit/commit/46e2ecf4659831e5fbcf6701f47670a99c952590
  Author: Tadeu Zagallo <tzagallo at apple.com>
  Date:   2023-08-14 (Mon, 14 Aug 2023)

  Changed paths:
    A Source/WebGPU/WGSL/GlobalSorting.cpp
    A Source/WebGPU/WGSL/GlobalSorting.h
    M Source/WebGPU/WGSL/WGSL.cpp
    A Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-const.wgsl
    A Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-function.wgsl
    A Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-struct.wgsl
    A Source/WebGPU/WGSL/tests/invalid/reordering-cycle.wgsl
    A Source/WebGPU/WGSL/tests/invalid/reordering-redeclaration.wgsl
    A Source/WebGPU/WGSL/tests/valid/reordering.wgsl
    M Source/WebGPU/WebGPU.xcodeproj/project.pbxproj

  Log Message:
  -----------
  [WGSL] Add new pass to sort global variables, structs and functions
https://bugs.webkit.org/show_bug.cgi?id=259984
rdar://113639825

Reviewed by Dan Glastonbury.

Constands, structs and functions can refer to other declarations of the same type
defined later at the program, e.g. `const y = x * 2; const x = 1;` is a valid program.
To simplify things, we add a new pass, which will be the first pass to run after parsing.
The pass sorts the declarations and detects cycles. This way, the rest of the compiler
doesn't need to be concerned with ordering.

* Source/WebGPU/WGSL/GlobalSorting.cpp: Added.
(WGSL::Graph::Node::Node):
(WGSL::Graph::Node::astNode const):
(WGSL::Graph::Node::incomingEdges):
(WGSL::Graph::Node::outgoingEdges):
(WGSL::Graph::Edge::Edge):
(WGSL::Graph::Edge::remove):
(WGSL::Graph::Edge::source const):
(WGSL::Graph::Edge::target const):
(WGSL::Graph::Edge::operator== const):
(WGSL::Graph::EdgeHashTraits::constructDeletedValue):
(WGSL::Graph::EdgeHashTraits::isDeletedValue):
(WGSL::Graph::EdgeHash::hash):
(WGSL::Graph::EdgeHash::equal):
(WGSL::Graph::Graph):
(WGSL::Graph::nodes):
(WGSL::Graph::addNode):
(WGSL::Graph::getNode):
(WGSL::Graph::edges):
(WGSL::Graph::addEdge):
(WGSL::GraphBuilder<ASTNode>::visit):
(WGSL::GraphBuilder<ASTNode>::GraphBuilder):
(WGSL::GraphBuilder<ASTNode>::introduceVariable):
(WGSL::GraphBuilder<ASTNode>::readVariable const):
(WGSL::reorder):
(WGSL::reorderGlobals):
* Source/WebGPU/WGSL/GlobalSorting.h: Added.
* Source/WebGPU/WGSL/WGSL.cpp:
(WGSL::staticCheck):
* Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-const.wgsl: Added.
* Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-function.wgsl: Added.
* Source/WebGPU/WGSL/tests/invalid/reordering-cycle-self-struct.wgsl: Added.
* Source/WebGPU/WGSL/tests/invalid/reordering-cycle.wgsl: Added.
* Source/WebGPU/WGSL/tests/invalid/reordering-redeclaration.wgsl: Added.
* Source/WebGPU/WGSL/tests/valid/reordering.wgsl: Added.
* Source/WebGPU/WebGPU.xcodeproj/project.pbxproj:

Canonical link: https://commits.webkit.org/266862@main