Skip to content

Replacing Stack IR with Poppy IR #3059

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
5 of 12 tasks
tlively opened this issue Aug 18, 2020 · 0 comments
Open
5 of 12 tasks

Replacing Stack IR with Poppy IR #3059

tlively opened this issue Aug 18, 2020 · 0 comments
Assignees
@tlively
Labels
Poppy IR

Comments

@tlively
Copy link
Member

tlively commented Aug 18, 2020 •
edited
Loading

The latest code pushed to my stackify branch (diff) implements a new form of IR ("Poppy IR") that directly represents the stack machine structure of WebAssembly and is meant to replace Stack IR for performing final stack machine optimizations before binary writing. This new system is motivated primarily by our need to emit efficient multivalue blocks and functions, which Stack IR cannot optimize.

The code I've written so far is sufficient to demonstrate that Poppy IR works and can generate smaller code with simpler passes than the current Stack IR pipeline, but it is very much a prototype. There are no tests, the validator is incomplete, the unstackify pass is buggy, and the pass runner does not prevent users from running passes on the incorrect form of IR. That being said, most of what has been written has been extensively fuzzed (although is not bug-free) and I expect that most of the code will eventually be able to land with minimal modifications. You can try it yourself by building my branch and running with BINARYEN_USE_STACKIFY=1 in your environment.

Here is a potential roadmap of discrete patches I plan to land to get Poppy IR upstream. I welcome discussion of how to better split up the work. As I land patches, I will check them off here and add links to the respective PRs.

  • Stack utils for analyzing Poppy IR with C++ API tests (Stack utils #3083)
  • Parsing of wast files directly to Poppy IR and validation (Poppy IR wast parsing and validation #3105)
  • Stackification with tests and fuzzing (Poppify pass #3541)
  • Unstackification with tests and fuzzing
  • Poppy IR optimization passes with tests and fuzzing
  • Pass runner integration and Stack IR replacement via environment variable
  • Remove Stack IR

Follow up work to immediately take advantage of Stack IR:

  • Move Binaryen to C++17 (prerequisite)
  • Replace wast parser with wasp

Follow up related investigative work:

  • Investigate removing unreachable control flow from Binaryen entirely.
  • Look at why Binaryen's DCE pass is so complicated and whether it could be shared with Poppy IR

Additional cleanup work to be done if at any point it would be helpful for achieving the other goals:

  • Move various test suites to a lit + FileCheck test framework
@tlively tlively self-assigned this Aug 18, 2020
@kripken kripken mentioned this issue Aug 19, 2020
Closed
tlively added a commit to tlively/binaryen that referenced this issue Aug 28, 2020
@tlively
Stack utils
685710f 
Implement and test utilities for manipulating and analyzing a new
stacky form of Binaryen IR that is able to express arbitrary stack
machine code. This new Stacky IR will eventually replace Stack IR, and
new optimization passes will be built with these utilities. See WebAssembly#3059.
@tlively tlively mentioned this issue Aug 28, 2020
Merged
tlively added a commit that referenced this issue Sep 8, 2020
@tlively
Stack utils (#3083)
a6816a2 
Implement and test utilities for manipulating and analyzing a new
stacky form of Binaryen IR that is able to express arbitrary stack
machine code. This new Poppy IR will eventually replace Stack IR, and
new optimization passes will be built with these utilities. See #3059.
@tlively tlively mentioned this issue Sep 8, 2020
Merged
tlively added a commit to tlively/binaryen that referenced this issue Sep 10, 2020
@tlively
Simplify BinaryenIRWriter
e04ce49 
BinaryenIRWriter was previously inconsistent about whether or not it
emitted an instruction if that instruction was not reachable.
Instructions that produced values were not emitted if they were
unreachable, but instructions that did not produce values were always
emitted. Additionally, blocks continued to emit their children even
after emitting an unreachable child.

Since it was not possible to tell whether an unreachable instruction's
parent would be emitted, BinaryenIRWriter had to be very defensive and
emit many extra `unreachable` instructions around unreachable code to
avoid type errors.

This PR unifies the logic for emitting all non-control flow
instructions and changes the behavior of BinaryenIRWriter so that it
never emits instructions that cannot be reached due to having
unreachable children. BinaryenIRWriter now also stops emitting
instructions inside blocks after the first unreachable
instruction. Together, these changes mean that extra `unreachable`
instructions only needed to be emitted after unreachable control flow
constructs.

This change will also simplify Poppy IR stackification (see WebAssembly#3059) by
guaranteeing that instructions with unreachable children will not be
emitted into the stackifier. This makes satisfying the Poppy IR rule
against unreachable Pops trivial, whereas previously satisfying this
rule would have required about about 700 additional lines of code to
recompute the types of all unreachable children for any instruction.
tlively added a commit to tlively/binaryen that referenced this issue Sep 10, 2020
@tlively
Simplify BinaryenIRWriter
69cac89 
BinaryenIRWriter was previously inconsistent about whether or not it
emitted an instruction if that instruction was not reachable.
Instructions that produced values were not emitted if they were
unreachable, but instructions that did not produce values were always
emitted. Additionally, blocks continued to emit their children even
after emitting an unreachable child.

Since it was not possible to tell whether an unreachable instruction's
parent would be emitted, BinaryenIRWriter had to be very defensive and
emit many extra `unreachable` instructions around unreachable code to
avoid type errors.

This PR unifies the logic for emitting all non-control flow
instructions and changes the behavior of BinaryenIRWriter so that it
never emits instructions that cannot be reached due to having
unreachable children. This means that extra `unreachable` instructions
now only need to be emitted after unreachable control flow
constructs. BinaryenIRWriter now also stops emitting instructions
inside blocks after the first unreachable instruction as an extra
optimization.

This change will also simplify Poppy IR stackification (see WebAssembly#3059) by
guaranteeing that instructions with unreachable children will not be
emitted into the stackifier. This makes satisfying the Poppy IR rule
against unreachable Pops trivial, whereas previously satisfying this
rule would have required about about 700 additional lines of code to
recompute the types of all unreachable children for any instruction.
@tlively tlively mentioned this issue Sep 10, 2020
Merged
tlively added a commit that referenced this issue Sep 11, 2020
@tlively
Simplify BinaryenIRWriter (#3110)
cd6f0d9 
BinaryenIRWriter was previously inconsistent about whether or not it
emitted an instruction if that instruction was not reachable.
Instructions that produced values were not emitted if they were
unreachable, but instructions that did not produce values were always
emitted. Additionally, blocks continued to emit their children even
after emitting an unreachable child.

Since it was not possible to tell whether an unreachable instruction's
parent would be emitted, BinaryenIRWriter had to be very defensive and
emit many extra `unreachable` instructions around unreachable code to
avoid type errors.

This PR unifies the logic for emitting all non-control flow
instructions and changes the behavior of BinaryenIRWriter so that it
never emits instructions that cannot be reached due to having
unreachable children. This means that extra `unreachable` instructions
now only need to be emitted after unreachable control flow
constructs. BinaryenIRWriter now also stops emitting instructions
inside blocks after the first unreachable instruction as an extra
optimization.

This change will also simplify Poppy IR stackification (see #3059) by
guaranteeing that instructions with unreachable children will not be
emitted into the stackifier. This makes satisfying the Poppy IR rule
against unreachable Pops trivial, whereas previously satisfying this
rule would have required about about 700 additional lines of code to
recompute the types of all unreachable children for any instruction.
tlively added a commit to tlively/binaryen that referenced this issue Sep 11, 2020
@tlively
Update Pop text format to handle tuples
dd6b2c6 
Previously Pops were printed as ({type}.pop), and if the popped type
was a tuple, something like ((i32, i64).pop) would get
printed. However, the parser didn't support pops of anything besides
single basic types.

This PR changes the text format to be (pop <type>*) and adds support
for parsing pops of tuples of basic types. The text format change is
designed to make parsing simpler. This change is necessary for writing
Poppy IR tests that contain break or return instructions that consume
multiple values (see WebAssembly#3059).
@tlively tlively mentioned this issue Sep 11, 2020
Merged
tlively added a commit that referenced this issue Sep 11, 2020
@tlively
Update Pop text format to handle tuples (#3116)
8ec8a0b 
Previously Pops were printed as ({type}.pop), and if the popped type was a
tuple, something like ((i32, i64).pop) would get printed. However, the parser
didn't support pops of anything besides single basic types.

This PR changes the text format to be (pop <type>*) and adds support for parsing
pops of tuples of basic types. The text format change is designed to make
parsing simpler. This change is necessary for writing Poppy IR tests (see #3059)
that contain break or return instructions that consume multiple values, since in
Poppy IR that requires tuple-typed pops.
@tlively tlively mentioned this issue Mar 14, 2022
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@tlively tlively

Labels
Poppy IR
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@tlively