Skip to content
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.

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

Cranelift: use egraphs by default #5181

Closed
fitzgen opened this issue Nov 2, 2022 · 4 comments · Fixed by #5587
Closed

Cranelift: use egraphs by default #5181

fitzgen opened this issue Nov 2, 2022 · 4 comments · Fixed by #5587
Labels
cranelift:mid-end clif-to-clif related passes, legalizations, etc... cranelift Issues related to the Cranelift code generator

Comments

@fitzgen
Copy link
Member

fitzgen commented Nov 2, 2022

It should be enabled by default. We should also define what the requirements we need to meet to enable it by default are.

cc @cfallin @jameysharp

@fitzgen fitzgen added cranelift Issues related to the Cranelift code generator cranelift:mid-end clif-to-clif related passes, legalizations, etc... labels Nov 2, 2022
@jameysharp
Copy link
Contributor

As far as I know there are two specific reasons we haven't done this yet:

  1. Compile speed regresses a little bit with egraphs turned on.
  2. We were encountering some fuzzing failures.

We have some ideas that might get the egraphs optimizer to parity with the current implementation and we want to play with those.

@cfallin
Copy link
Member

cfallin commented Nov 2, 2022

Indeed; to add a little more, the overall approach I want to take is to integrate the egraph data structure more completely into the DataFlowGraph. Basically, the PrimaryMap of ValueDefs can take the place of the "eclass nodes" in cranelift-egraph currently: alongside the other kinds of defs (instruction output, blockparam, alias), we can have a "union" kind. Then the multi-definition aspect of the aegraph can be represented directly in the CLIF.

Then the only other difference is that we can take "pure" insts and not place them in blocks before elaboration. So the egraph-mode becomes:

  • Allow multiple definitions of a value in the CLIF, by introducing a "union" kind of value (write this in the CLIF text format as e.g. v3 <- v1, v2 analogously to aliases currently);
  • Apply rewrite rules as soon as values are introduced, as we do in egraph-mode today (optimizations-during-build);
  • Do not place "pure" instructions in the Layout until elaboration. Elaboration consists of (i) choosing a canonical value for each value (a value->value map), and (ii) putting Insts in the Layout, possibly duplicating where needed;
  • Modifying the hashing in GVN a bit so that we hash insts based on canonical values (via a union-find forest) rather than latest-value-in-eclass values.

There are a bunch of nice outcomes from that (and once I saw it, I realized we basically must go this way, and a separate egraph doesn't make sense anymore):

  • Any CLIF is also almost an aegraph, trivially / by construction. (The lack of placement for pure nodes is the only difference).
  • There is no copying/translation of information between egraph nodes and CLIF instructions.
  • We get all the debugging benefits of the text format and other utilities surrounding CLIF.

I want to build all of this first, and suspect that when I do, the perf regressions we're seeing should go away. The reason for holding back before then is both because of the regression but also because if the design is going to change, we should do that before we rely on it as the default path.

I'm currently 100%-coding-time on another project but will hopefully be able to come back to this sometime soon-ish; @jameysharp and I have talked about collaborating on its implementation as well.

@bjorn3
Copy link
Contributor

bjorn3 commented Nov 2, 2022

Would it be possible to replace Layout with a different type while the function is in aegraph form, but keep DataFlowGraph in both cases? This would extend to more alternative representations like VSDG/sea of nodes or something with structured control flow (for eg wasm or spirv generation) with minimal (or no) changes to the core ir while at the same time minimizing code duplication.

@cfallin
Copy link
Member

cfallin commented Nov 2, 2022

Yep, we could go further in that direction as well; that's an interesting direction to explore.

cfallin added a commit that referenced this issue Jan 19, 2023
This PR follows up on #5382 and #5391, which rebuilt the egraph-based optimization framework to be more performant, by enabling it by default.

Based on performance results in #5382 (my measurements on SpiderMonkey and bjorn3's independent confirmation with cg_clif), it seems that this is reasonable to enable. Now that we have been fuzzing compiler configurations with egraph opts (#5388) for 6 weeks, having fixed a few fuzzbugs that came up (#5409, #5420, #5438) and subsequently received no further reports from OSS-Fuzz, I believe it is stable enough to rely on.

This PR enables `use_egraphs`, and also normalizes its meaning: previously it forced optimization (it basically meant "turn on the egraph optimization machinery"), now it runs egraph opts if the opt level indicates (it means "use egraphs to optimize if we are going to optimize"). The conditionals in the top-level pass driver are a little subtle, but will get simpler once we can remove the non-egraph path (which we plan to do eventually!).

Fixes #5181.
cfallin added a commit to cfallin/wasmtime that referenced this issue Apr 6, 2023
… option.

This PR removes the LICM, GVN, and preopt passes, and associated support
pieces, from `cranelift-codegen`. Not to worry, we still have
optimizations: the egraph framework subsumes all of these, and has been
on by default since bytecodealliance#5181.

A few decision points:

- Filetests for the legacy LICM, GVN and simple_preopt were removed too.
  As we built optimizations in the egraph framework we wrote new tests
  for the equivalent functionality, and many of the old tests were
  testing specific behaviors in the old implementations that may not be
  relevant anymore. However if folks prefer I could take a different
  approach here and try to port over all of the tests.

- The corresponding filetest modes (commands) were deleted too. The
  `test alias_analysis` mode remains, but no longer invokes a separate
  GVN first (since there is no separate GVN that will not also do alias
  analysis) so the tests were tweaked slightly to work with that. The
  egrpah testsuite also covers alias analysis.

- The `divconst_magic_numbers` module is removed since it's unused
  without `simple_preopt`, though this is the one remaining optimization
  we still need to build in the egraphs framework, pending bytecodealliance#5908. The
  magic numbers will live forever in git history so removing this in the
  meantime is not a major issue IMHO.

- The `use_egraphs` setting itself was removed at both the Cranelift and
  Wasmtime levels. It has been marked deprecated for a few releases now
  (Wasmtime 6.0, 7.0, upcoming 8.0, and corresponding Cranelift
  versions) so I think this is probably OK. As an alternative if anyone
  feels strongly, we could leave the setting and make it a no-op.
cfallin added a commit that referenced this issue Apr 6, 2023
… option. (#6167)

* Cranelift: remove non-egraphs optimization pipeline and `use_egraphs` option.

This PR removes the LICM, GVN, and preopt passes, and associated support
pieces, from `cranelift-codegen`. Not to worry, we still have
optimizations: the egraph framework subsumes all of these, and has been
on by default since #5181.

A few decision points:

- Filetests for the legacy LICM, GVN and simple_preopt were removed too.
  As we built optimizations in the egraph framework we wrote new tests
  for the equivalent functionality, and many of the old tests were
  testing specific behaviors in the old implementations that may not be
  relevant anymore. However if folks prefer I could take a different
  approach here and try to port over all of the tests.

- The corresponding filetest modes (commands) were deleted too. The
  `test alias_analysis` mode remains, but no longer invokes a separate
  GVN first (since there is no separate GVN that will not also do alias
  analysis) so the tests were tweaked slightly to work with that. The
  egrpah testsuite also covers alias analysis.

- The `divconst_magic_numbers` module is removed since it's unused
  without `simple_preopt`, though this is the one remaining optimization
  we still need to build in the egraphs framework, pending #5908. The
  magic numbers will live forever in git history so removing this in the
  meantime is not a major issue IMHO.

- The `use_egraphs` setting itself was removed at both the Cranelift and
  Wasmtime levels. It has been marked deprecated for a few releases now
  (Wasmtime 6.0, 7.0, upcoming 8.0, and corresponding Cranelift
  versions) so I think this is probably OK. As an alternative if anyone
  feels strongly, we could leave the setting and make it a no-op.

* Update test outputs for remaining test differences.
brendandburns pushed a commit to brendandburns/wasmtime that referenced this issue Apr 13, 2023
… option. (bytecodealliance#6167)

* Cranelift: remove non-egraphs optimization pipeline and `use_egraphs` option.

This PR removes the LICM, GVN, and preopt passes, and associated support
pieces, from `cranelift-codegen`. Not to worry, we still have
optimizations: the egraph framework subsumes all of these, and has been
on by default since bytecodealliance#5181.

A few decision points:

- Filetests for the legacy LICM, GVN and simple_preopt were removed too.
  As we built optimizations in the egraph framework we wrote new tests
  for the equivalent functionality, and many of the old tests were
  testing specific behaviors in the old implementations that may not be
  relevant anymore. However if folks prefer I could take a different
  approach here and try to port over all of the tests.

- The corresponding filetest modes (commands) were deleted too. The
  `test alias_analysis` mode remains, but no longer invokes a separate
  GVN first (since there is no separate GVN that will not also do alias
  analysis) so the tests were tweaked slightly to work with that. The
  egrpah testsuite also covers alias analysis.

- The `divconst_magic_numbers` module is removed since it's unused
  without `simple_preopt`, though this is the one remaining optimization
  we still need to build in the egraphs framework, pending bytecodealliance#5908. The
  magic numbers will live forever in git history so removing this in the
  meantime is not a major issue IMHO.

- The `use_egraphs` setting itself was removed at both the Cranelift and
  Wasmtime levels. It has been marked deprecated for a few releases now
  (Wasmtime 6.0, 7.0, upcoming 8.0, and corresponding Cranelift
  versions) so I think this is probably OK. As an alternative if anyone
  feels strongly, we could leave the setting and make it a no-op.

* Update test outputs for remaining test differences.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cranelift:mid-end clif-to-clif related passes, legalizations, etc... cranelift Issues related to the Cranelift code generator
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants