Translator: Implement an IR

The ANGLE compiler parses GLSL ES shaders and produces an Abstract
Syntax Tree (AST).  The use of AST is deceptively simple, as the
structure of this representation always matches the equivalent text
representation.  This simplicity can make the compiler initially more
approachable.

However, as compiler research, modern compiler best practices, and our
own experiences with the ANGLE compiler have shown, ASTs are harder to
analyze and transform. For example:

* Struct definitions may be in a number of surprising places in GLSL,
  such as a function’s return type. Reflecting this fact in the AST
  makes it tricky to apply transformations to the struct.

* The inability to include arbitrary blocks of code in many locations
  such as inside an `if` condition turns simple transformations (such as
  caching an expression with a side effect inside a temporary variable)
  into complex ones with many corner cases.

Instead, modern compilers include an Internal Representation (IR) that
is potentially far removed from the textual syntax of the language.
This comes with numerous benefits, such as the freedom to simplify and
rearrange type definitions, the flexibility of instruction flow
structure, etc, which in turn make more complex operations (such as
dead-code elimination) less burdensome.  In some projects, IRs
also allow the compiler to handle multiple textual formats (otherwise
known as front-ends).

While generating an IR from text is typically not complicated, one
possibly challenging aspect of IRs is going back to a textual
representation if needed (such as generating glsl, msl or hlsl in the
case of ANGLE), as the textual representation includes restrictions that
do not exist in the IR.

Given the number of bugs (security or otherwise) that constantly affect
ANGLE, there is a need for an IR to finally modernize this codebase.
The new WGSL backend for the translator is plagued with the same
complications that the SPIR-V generator has faced (such as lack of
ability to write to a swizzle expression), with extremely complicated
or in some cases no clear way of implementing them in the AST, so an IR
would simplify/unblock that work.
Finally, some needed optimizations (such as cross-stage dead-code
elimination) are needed for the ANGLE-for-Android project, but are
extremely difficult to do with the AST.

It’s time the translator was written to be based on an IR.  ANGLE
implements its own IR instead of reusing existing ones, such as SPIR-V,
mesa's NIR, or Tint's IR, because:

* It can be simpler e.g. compared to SPIR-V's highly flexible branching
* It can be tailored to ESSL e.g. compared to Tint's IR
* It can be in complete control e.g. compared to mesa's NIR

This change implements the following:

* GLSL->IR generation during parse
* IR transformation utilities, debug dump, documentation (see
  src/compiler/translator/ir/doc/README.md)
* An "astify" transformation that makes the IR suitable for AST and
  text-based output generation
* IR->AST generation after parse

The current AST generation during parse is still maintained because:

* It's used by validation, but that will ultimately be made unnecessary
  after the following point is no longer needed.
* It's simpler to keep the AST generation while the no-IR path is still
  supported.

With the rountrip through IR, a dozen transformations that try to make
the AST more malleable are made unnecessary.  However, at this point
when the IR is enabled, the overhead of creating it is present, while
the transformations are still complex and based on the AST.  The IR is
disabled until almost all transformations are ported and at least SPIR-V
generation is done directly from the IR.

To enable the IR, set `angle_ir = true` in `args.gn`.  Nearly all tests
pass with the IR enabled, though a few failures remain to be diagnosed.
One particular follow up fix is to port our compiler unittests to
end2end tests:

* They assume too much about the internals of the compiler, which is
  completely overhauled now
* The validation is too simplistic, where often transformation bugs are
  discovered only after trying to use the shader in a draw call (where
  multiple backends actually give the translator output to the native
  driver/compiler)

Bug: angleproject:349994211
Change-Id: I2ce917bf956d40af4545473b4a9068cf295878be
Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/5898761
Reviewed-by: Geoff Lang <geofflang@chromium.org>
Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org>
Reviewed-by: Matthew Denton <mpdenton@chromium.org>

• .gn[diff]
• .rustfmt.toml[Added - diff]
• BUILD.gn[diff]
• gni/angle.gni[diff]
• scripts/export_targets.py[diff]
• src/compiler.gni[diff]
• src/compiler/translator/Compiler.cpp[diff]
• src/compiler/translator/Compiler.h[diff]
• src/compiler/translator/Diagnostics.cpp[diff]
• src/compiler/translator/Diagnostics.h[diff]
• src/compiler/translator/ParseContext.cpp[diff]
• src/compiler/translator/ParseContext.h[diff]
• src/compiler/translator/PoolAlloc.cpp[diff]
• src/compiler/translator/PoolAlloc.h[diff]
• src/compiler/translator/ShaderLang.cpp[diff]
• src/compiler/translator/Symbol.h[diff]
• src/compiler/translator/SymbolTable.cpp[diff]
• src/compiler/translator/SymbolTable.h[diff]
• src/compiler/translator/Types.h[diff]
• src/compiler/translator/ValidateAST.cpp[diff]
• src/compiler/translator/glsl/OutputGLSLBase.cpp[diff]
• src/compiler/translator/ir/.gitignore[Added - diff]
• src/compiler/translator/ir/BUILD.gn[Added - diff]
• src/compiler/translator/ir/doc/README.md[Added - diff]
• src/compiler/translator/ir/src/ast.rs[Added - diff]
• src/compiler/translator/ir/src/builder.cpp[Added - diff]
• src/compiler/translator/ir/src/builder.h[Added - diff]
• src/compiler/translator/ir/src/builder.rs[Added - diff]
• src/compiler/translator/ir/src/compile.cpp[Added - diff]
• src/compiler/translator/ir/src/compile.h[Added - diff]
• src/compiler/translator/ir/src/compile.rs[Added - diff]
• src/compiler/translator/ir/src/debug.rs[Added - diff]
• src/compiler/translator/ir/src/instruction.rs[Added - diff]
• src/compiler/translator/ir/src/ir.rs[Added - diff]
• src/compiler/translator/ir/src/lib.rs[Added - diff]
• src/compiler/translator/ir/src/output.rs[Added - diff]
• src/compiler/translator/ir/src/output/glsl.rs[Added - diff]
• src/compiler/translator/ir/src/output/ir_to_legacy.cpp[Added - diff]
• src/compiler/translator/ir/src/output/ir_to_legacy.h[Added - diff]
• src/compiler/translator/ir/src/output/legacy.h[Added - diff]
• src/compiler/translator/ir/src/output/legacy.rs[Added - diff]
• src/compiler/translator/ir/src/pool_alloc.cpp[Added - diff]
• src/compiler/translator/ir/src/pool_alloc.h[Added - diff]
• src/compiler/translator/ir/src/transform.rs[Added - diff]
• src/compiler/translator/ir/src/transform/astify.rs[Added - diff]
• src/compiler/translator/ir/src/transform/dealias.rs[Added - diff]
• src/compiler/translator/ir/src/transform/propagate_precision.rs[Added - diff]
• src/compiler/translator/ir/src/traverser.rs[Added - diff]
• src/compiler/translator/ir/src/util.rs[Added - diff]
• src/compiler/translator/ir/src/validator.rs[Added - diff]
• src/compiler/translator/tree_ops/RewritePixelLocalStorage.cpp[diff]
• src/tests/BUILD.gn[diff]
• src/tests/gl_tests/PixelLocalStorageTest.cpp[diff]

git clone https://chromium.googlesource.com/angle/angle