wasmtime / PR #1647 Introduce peepmatic: a peephole optim... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / PR #1647 Introduce peepmatic: a peephole optim...

Wasmtime GitHub notifications bot (May 02 2020 at 00:23):

fitzgen opened PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 02 2020 at 00:23):

fitzgen requested sunfishcode for a review on PR #1647.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

Maybe construct this map on the fly from values when deserializing?

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

    False,

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

Is there any use for this function as opposed to using intern?

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

It would be nice to start this doc comment with a single sentence describing this type in short, followed by a blank line. Rustdoc will then show that sentence and only that sentence when visiting the documentation of the parent module.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

    /// Implicitly define the n^th RHS as a condition code.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

Is there any use for peephole optimization of adjust_sp_down{,_imm}?

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

"implicitly" is repeated for all variants.

Wasmtime GitHub notifications bot (May 02 2020 at 12:19):

bjorn3 created PR Review Comment:

    /// A map from a path (whose owned data is inside `arena`) to the canonical
    /// `PathId` we assigned it when interning it.
    map: HashMap<UnsafePath, PathId>,

    /// A map from a `PathId` index to an unsafe, self-borrowed path pointing
    /// into `arena`. It is safe to given these out as safe `Path`s, as long as
    /// the lifetime is not longer than this `PathInterner`'s lifetime.
    paths: Vec<UnsafePath>,

    /// Bump allocation arena for path data. The bump arena ensures that these
    /// allocations never move, and are therefore safe for self-references.

These show up when using --document-private-items.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

You can already match on ValueDef yourself.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Maybe require that src is already not in the layout?

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Please add a CI check that preopt.serialized is up to date.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Is 1 unreachable?

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Same here re size of 1.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

If this is for a signed operation, the immediate needs to be sign extended.

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Why are the constants here at the beginning, instead of at the end like in the real clif ir?

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

To be honest reading through this file was tiresome. Maybe a more rust like syntax would help with this?

Wasmtime GitHub notifications bot (May 02 2020 at 12:54):

bjorn3 created PR Review Comment:

Maybe avoid duplication by moving the linear::Optimization construction into the macro, leaving this closure to just return a Vec. Also you can try to cast the closure to fn(&mut dyn FnMut(&[u8]) -> PathId, &mut dyn FnMut(u64) -> IntegerId) -> Vec<linear::Increment> before calling it. This may help type inference enough to not need explicit type annotations here.

Wasmtime GitHub notifications bot (May 02 2020 at 12:58):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 02 2020 at 12:58):

bjorn3 created PR Review Comment:

This doesn't check if the peephole optimizers were up to date. Only that they can be rebuild.

Wasmtime GitHub notifications bot (May 02 2020 at 12:58):

bjorn3 deleted PR Review Comment.

Wasmtime GitHub notifications bot (May 08 2020 at 19:29):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 19:29):

fitzgen created PR Review Comment:

Yes, it is used when evaluating MatchOp::IntegerValue -- see peepmatic/crates/runtime/src/optimizer.rs.

Wasmtime GitHub notifications bot (May 08 2020 at 19:44):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 19:44):

fitzgen created PR Review Comment:

Nop is closer to True than False, but I think renaming it really clarifies anything here.

Wasmtime GitHub notifications bot (May 08 2020 at 19:49):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 19:49):

fitzgen created PR Review Comment:

Yes, to convert adjust_sp_down with a constant argument into an adjust_sp_down_imm.

Wasmtime GitHub notifications bot (May 08 2020 at 20:19):

fitzgen created PR Review Comment:

In clif, some immediates are at the beginning (e.g. condition codes) and some are at the end (e.g. constant values). For simplicity, I implemented peepmatic such that all immediates come first, followed by all operands. There is no inherent reason it needs to be this way.

Wasmtime GitHub notifications bot (May 08 2020 at 20:19):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:21):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:21):

fitzgen created PR Review Comment:

S-expressions are simple and easy to parse. Plus we have nice infrastructure for them in the wast crate. Syntax and parsing is largely busy work, and not the interesting bits of this work. If the cranelift team feels strongly, we can change this, but it isn't worth debating about before landing this PR.

Wasmtime GitHub notifications bot (May 08 2020 at 20:24):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:24):

fitzgen created PR Review Comment:

This is true, but it is nice having a convenience method, same as why Result<T, E> has an ok method.

Wasmtime GitHub notifications bot (May 08 2020 at 20:26):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:26):

fitzgen created PR Review Comment:

This would require that we remove it ourselves before calling this method, which would be a bunch of duplication.

Wasmtime GitHub notifications bot (May 08 2020 at 20:30):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:30):

fitzgen created PR Review Comment:

This is something we could do in the future with a custom serialization and deserialization implementation.

Wasmtime GitHub notifications bot (May 08 2020 at 20:44):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:44):

bjorn3 created PR Review Comment:

This order is confusing for isub_imm.

Wasmtime GitHub notifications bot (May 08 2020 at 20:44):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:44):

fitzgen created PR Review Comment:

Nice idea!

Wasmtime GitHub notifications bot (May 08 2020 at 20:47):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 08 2020 at 20:47):

fitzgen created PR Review Comment:

I haven't been able to create a test case where I can observe the lack of sign extension, and the fact that the existing code wasn't doing this either makes me think it isn't necessary. Can you provide a test case that shows this?

Wasmtime GitHub notifications bot (May 08 2020 at 20:48):

fitzgen updated PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 08 2020 at 21:35):

fitzgen updated PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 08 2020 at 22:13):

fitzgen updated PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 12 2020 at 19:29):

fitzgen updated PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 12 2020 at 19:34):

bjorn3 submitted PR Review.

Wasmtime GitHub notifications bot (May 12 2020 at 19:34):

bjorn3 created PR Review Comment:

See https://github.com/bytecodealliance/wasmtime/issues/1095

Wasmtime GitHub notifications bot (May 12 2020 at 20:46):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 12 2020 at 20:46):

fitzgen created PR Review Comment:

Thanks. I'll work on fixing #1095 at the InstructionBuilder level, as suggested in that issue, rather than in this PR.

Wasmtime GitHub notifications bot (May 13 2020 at 23:48):

sunfishcode submitted PR Review.

Wasmtime GitHub notifications bot (May 13 2020 at 23:48):

sunfishcode submitted PR Review.

Wasmtime GitHub notifications bot (May 13 2020 at 23:48):

sunfishcode created PR Review Comment:

I don't see the func or isa lifetimes being used outside of this declaration, so it's not clear why do_preopt's signature changed here. Does the optimizer have any state that lives longer than the do_preopt call?

Wasmtime GitHub notifications bot (May 14 2020 at 14:47):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 14 2020 at 14:47):

fitzgen created PR Review Comment:

This might be left over from some bits that ultimately got thrown away; I'll try and remove it and on the off chance that I can't, then I'll have an explanation for why not ;)

Wasmtime GitHub notifications bot (May 14 2020 at 14:52):

fitzgen submitted PR Review.

Wasmtime GitHub notifications bot (May 14 2020 at 14:52):

fitzgen created PR Review Comment:

Ok, these are removed.

Wasmtime GitHub notifications bot (May 14 2020 at 14:52):

fitzgen updated PR #1647 from integrate-peepmatic to master:

This PR introduces peepmatic, a peephole optimizations DSL and peephole optimizer compiler.

Developers write a set of optimizations in the DSL, and then peepmatic compiles the set of optimizations into an efficient peephole optimizer:
DSL ----peepmatic----> Peephole Optimizer
The generated peephole optimizer has all of its optimizations' left-hand sides collapsed into a compact transducer automaton that makes matching candidate instruction sequences fast.

The DSL's optimizations may be written by hand or discovered mechanically with a superoptimizer like [Souper][]. Eventually, peepmatic should have a verifier that ensures that the DSL's optimizations are sound, similar to what [Alive][] does for LLVM optimizations.

[Souper]: https://github.com/google/souper
[Alive]: https://github.com/AliveToolkit/alive2

Learn More

cranelift/peepmatic/README.md has an overview of the DSL and implementation

Here is a slide deck I am presenting at the 2020-05-04 Cranelift meeting

Current Status

I've ported most of simple_preopt.rs to peepmatic's DSL

All tests are passing

I've been doing lots and lots of fuzzing

Next Steps

This work is not complete, but I think it is at a good point to merge into Cranelift and then evolve in-tree.

The next steps after landing this PR are:

Port the rest of simple_preopt.rs over to peepmatic

Port postopt.rs over to peepmatic

Optimize the runtime that interprets the generated peephole optimizations transducers and applies them

Extend peepmatic to work with the new backend's MachInst and vcode

For even further future directions, see the discussion in the slides, linked above.

Wasmtime GitHub notifications bot (May 14 2020 at 16:02):

fitzgen merged PR #1647.

Last updated: Dec 23 2024 at 12:05 UTC