Stream: git-wasmtime

Topic: wasmtime / PR #4249 [WIP / RFC] Cranelift: Basic support ...

Wasmtime GitHub notifications bot (Jun 09 2022 at 00:23):

cfallin opened PR #4249 from clif-egg to main:

This is a work-in-progress, and meant to sketch the direction I've been
thinking in for a mid-end framework. A proper BA RFC will come soon.

This PR builds a phase in the optimization pipeline that converts a CLIF
CFG into an egraph representing the function body. Each node represents
an original instruction or operator. The "skeleton" of side-effecting
instructions is retained, but non-side-effecting (pure) operators are
allowed to "float": the egraph will naturally deduplicate them during
build, and we will determine their proper place when we convert back to
a CFG representation.

The conversion from the egraph back to the CFG is done via a new
algorithm I call "scoped elaboration". The basic idea is to do a
preorder traversal of the domtree, and at each level, evaluate the
values of the eclasses called upon by the side-effect skeleton,
memoizing in an eclass-to-SSA-value map. This map is a scoped hashmap,
with scopes at each domtree level. In this way, (i) when a value is
computed in a location that dominates another instance of that value,
the first replacees the second; but (ii) we never produce "partially
dead" computations, i.e. we never hoist to a level in the domtree where
a node is not "anticipated" (always eventually computed). This exactly
matches what GVN does today. With a small tweak, it can also subsume
LICM: we need to be loop-nest-aware in our recursive eclass elaboration,
and potentially place nodes higher up the domtree (and higher up in the
scoped hashmap).

Unlike what I had been thinking in Monday's meeting, this produces CLIF
out of the egraph and then allows that to be lowered. It's overall
simpler and a better starting point (thanks @abrown for tipping me over
the edge in this). The way it produces CLIF now could be made more
efficient: it could reuse instructions already in the DFG for nodes that
are not duplicated (likely most of them) rather than clearing all and
repopulating.

This PR does not do anything to actually rewrite in the egraph. That's
the next step! I need to work out exactly how to integrate ISLE with
some sort of rewrite machinery. I have some ideas about efficient
dispatch with an "operand-tree discriminants shape analysis" on the
egraph and indexing rules by their matched shape; more to come.

cc @fitzgen @jameysharp @abrown @avanhatt @mlfbrown

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

• [ ] This has been discussed in issue #..., or if not, please tell us why
  here.

• [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.

• [ ] This PR contains test cases, if meaningful.

• [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the code of conduct.
-->

Wasmtime GitHub notifications bot (Jun 09 2022 at 00:25):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jun 09 2022 at 04:15):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jun 09 2022 at 07:18):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen submitted PR review.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

    /// extraction that disqualifies enodes (removes them from

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

I think this should probably be rewritten to use iteration + an explicit work stack, instead of stack recursion. Just to be more robust in the face of malicious input. I don't think we have any stack recursion anywhere else in Cranelift, afaik.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Ditto regarding recursion here.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Nitpick-y for sure, but I'm not a huge fan of the name Result for this type of node. I think Projection would be an improvement and Pick or something along those lines might be even better.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen submitted PR review.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

This is kinda funky, would be better IMO as

        assert!(
            !matches!(node, Node::Param { .. }),
            "Param nodes should already be inserted",
        );

which is a little funky because of !macro!() but also there could be a Node::is_param method to clean that up.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Shouldn't this always be absent at this point because there aren't any cycles in the egraph anymore and we check for whether it is in id_to_value and early exit if so at the very? Is this a property we can assert?

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

I think this would really benefit from an overview of the scoped elaboration algorithm up here at the top.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Similarly, the mutual recursion between visit_enode and visit_eclass should be rewritten with iteration and an explicit stack before we consider merging this.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

This would also benefit from a description of the algorithm here.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Ahhhh okay, so this panics if it is already present. That's a bit confusing, since given the method name I would assume that this silently returns if the entry already exists.

Maybe call this insert_and_assert_absent or even just insert_absent?

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Probably worth having test egraphs in the long run, since this combination of settings is a bit of a magical incantation.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

This seems to have had the redundant phi elimination pass run on it? Because the egraph isn't doing that yet, right? Another reason to have test egraph so that we aren't pulling in incidental/unrelated changes to these tests.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:00):

fitzgen created PR review comment:

Ditto recursion. (Will stop pointing it out now)

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:45):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:45):

cfallin created PR review comment:

Yes for sure, this is the plan!

Incidentally we'll probably want to audit egg itself for this property too...

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:50):

jameysharp created PR review comment:

I know some key parts of egg are structured as a workqueue but I haven't audited it to check if that's true everywhere. In fact there are APIs (such as the Pattern and CostFunction traits) that as I recall have default implementations that are recursive, but can be implemented iteratively if the client code puts in the work.

Wasmtime GitHub notifications bot (Jun 09 2022 at 22:50):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Jun 09 2022 at 23:06):

cfallin created PR review comment:

Yes, I think so. I think we'll actually want to do something equivalent to redundant-phis as a rewrite rule eventually (you're probably thinking along these lines too :-) ); I need to think through how exactly to do this best without introducing cycles in the egraph from the blockparam nodes (or maybe we do, and just ignore during elaboration).

Wasmtime GitHub notifications bot (Jun 09 2022 at 23:06):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jul 08 2022 at 06:20):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 08 2022 at 06:22):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 18 2022 at 03:46):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 19 2022 at 07:39):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 19 2022 at 08:05):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 20 2022 at 06:19):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 20 2022 at 06:26):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 22 2022 at 05:01):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 23 2022 at 00:24):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 23 2022 at 00:31):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 27 2022 at 06:41):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 27 2022 at 06:48):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 27 2022 at 07:25):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 29 2022 at 03:41):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 30 2022 at 01:34):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Jul 30 2022 at 01:41):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 03 2022 at 04:41):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 03 2022 at 07:33):

lqd submitted PR review.

Wasmtime GitHub notifications bot (Aug 03 2022 at 07:33):

lqd created PR review comment:

This looks unused ? (was it the reason for also allowing non_camel_case_types ?)

Wasmtime GitHub notifications bot (Aug 03 2022 at 07:35):

lqd submitted PR review.

Wasmtime GitHub notifications bot (Aug 03 2022 at 07:35):

lqd created PR review comment:

how about "e-dag" instead of "acyclic e-graph" ?

Wasmtime GitHub notifications bot (Aug 03 2022 at 07:36):

lqd edited PR review comment.

Wasmtime GitHub notifications bot (Aug 03 2022 at 15:41):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 03 2022 at 15:41):

cfallin created PR review comment:

It's used by the generated code actually! For multi-extractors now there is an iterator protocol with an iterator type provided per extractor.

The non-camel-case type name is a little awkward indeed, but I wanted to make it derived directly from the extractor name (and all these are camel-case) and not have the ISLE compiler understand snake-to-camel-case conversion, so snake-case it is...

Wasmtime GitHub notifications bot (Aug 03 2022 at 15:43):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 03 2022 at 15:43):

cfallin created PR review comment:

That could work too but I have some more acronymming based on aegraph (writeup to come) so I want to stick with this for now :-)

Wasmtime GitHub notifications bot (Aug 06 2022 at 00:22):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 00:34):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 03:30):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 03:42):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 05:48):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 06:42):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 07:50):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 17:16):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 06 2022 at 17:49):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 07 2022 at 00:24):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 07 2022 at 03:24):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 07 2022 at 19:52):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 07 2022 at 23:14):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 08 2022 at 03:33):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 08 2022 at 04:56):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 08 2022 at 04:57):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 08 2022 at 06:19):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 09 2022 at 08:01):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 10 2022 at 00:47):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 10 2022 at 01:51):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 04:16):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 05:00):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 05:33):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 05:49):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 06:03):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 06:06):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 06:23):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 07:18):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 11 2022 at 07:47):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:23):

cfallin updated PR #4249 from clif-egg to main.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:32):

bjorn3 created PR review comment:

Does this mean it will do egraph optimizations even if opt_level is set to none?

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:32):

bjorn3 submitted PR review.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:35):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:35):

cfallin created PR review comment:

This is a work-in-progress branch and I'm doing some hacking on some benchmarking infrastructure, and I wanted to name points-in-time by hashes only, without a separate config. We will definitely not enable opts if opts are disabled. Please note the commit comment and please disregard throwaway commits on my work-in-progress branch; there will be ample opportunity to review when the real PRs come.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:38):

bjorn3 submitted PR review.

Wasmtime GitHub notifications bot (Aug 17 2022 at 17:38):

bjorn3 created PR review comment:

Didn't see the commit message as I was looking at the github diff view for all changes since the last notification.

Wasmtime GitHub notifications bot (Sep 23 2022 at 22:28):

cfallin closed without merge PR #4249.

Last updated: Nov 22 2024 at 17:03 UTC