Stream: git-wasmtime

Topic: wasmtime / Issue #2143 Relocation of DW_OP_{bra, skip} in...

view this post on Zulip Wasmtime GitHub notifications bot (Aug 19 2020 at 08:49):

github-actions[bot] commented on Issue #2143:

Subscribe to Label Action

cc @bnjbvr

<details>
This issue or pull request has been labeled: "cranelift", "cranelift:wasm"

Thus the following users have been cc'd because of the following labels:

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

view this post on Zulip Wasmtime GitHub notifications bot (Aug 21 2020 at 10:54):

ggreif commented on Issue #2143:

Suggested additional reviewer: @osa1

view this post on Zulip Wasmtime GitHub notifications bot (Aug 22 2020 at 20:13):

ggreif commented on Issue #2143:

I think it is better to squash all the commits before a merge and adding a better overall commit message.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 11:00):

ggreif commented on Issue #2143:

@yurydelendik Thanks for the review. I can't see where I have introduced O(n^2). The insertion of LandingPads is linear in the number of parts, just like the removal of uninteresting ones. Post-translation, building of the old_to_new should be linear (modulo HashMap internals) and the backpatching too.

I have contemplated about remembering the offset of every part that is pushed, but the parts are not 1:1 preserved in the transformation. With floating LandingPads this is not a problem. Attaching an original offset to every part is also tricky, because the translation process would have trouble doing the bookkeeping of offsets.

Regarding frame_base, yes, this is a hole still, but I need a better understanding what frame_base is for. Is it for the location expressions that guide into structure members?

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 13:25):

yurydelendik commented on Issue #2143:

I can't see where I have introduced O(n^2).

It is near filter_map(.. any()/all() ..).collect() and some old_to_new operations.

I need a better understanding what frame_base is for

This expression is coming from DW_AT_frame_base. (Discard my idea about offsetting, I was incorrect there) It shall be inlined during each DW_OP_fbreg operation.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 13:39):

yurydelendik commented on Issue #2143:

Attaching an original offset to every part is also tricky, because the translation process would have trouble doing the bookkeeping of offsets.

FWIW I am also thinking about having parts: Vec<(CompiledExpressionPart, usize)>, -- this will take care of bookkeeping. Though you will need to track parts last offset instead of first -- it is the same thing for this logic.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 13:40):

ggreif commented on Issue #2143:

Well, I get quadratic behaviour only when assuming # jumps are proportional to the # of DW_OPs. Similarly, old_to_new is bounded by the # of jumps times two. But in principle you are right.

Is it realistic that DW_AT_frame_base has jumps in it? Should be just bail if so?

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 13:42):

ggreif edited a comment on Issue #2143:

Well, I get quadratic behaviour only when assuming # jumps are proportional to the # of DW_OPs. Similarly, old_to_new is bounded by the # of jumps times two. But in principle you are right.

Is it realistic that DW_AT_frame_base has jumps in it? Should we just bail if so?

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 13:51):

yurydelendik commented on Issue #2143:

Is it realistic that DW_AT_frame_base has jumps in it? Should we just bail if so?

Yes, let's assume DW_AT_frame_base has no jumps, otherwise let's bail.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 14:27):

ggreif commented on Issue #2143:

FWIW I am also thinking about having parts: Vec<(CompiledExpressionPart, usize)>, -- this will take care of bookkeeping. Though you will need to track parts last offset instead of first -- it is the same thing for this logic.

I tried to go down that route, but got quickly lost in the build_with_locals bowels, string at ranges_builder and co.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 14:27):

ggreif edited a comment on Issue #2143:

FWIW I am also thinking about having parts: Vec<(CompiledExpressionPart, usize)>, -- this will take care of bookkeeping. Though you will need to track parts last offset instead of first -- it is the same thing for this logic.

I tried to go down that route, but got quickly lost in the build_with_locals bowels, staring at ranges_builder and co.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 25 2020 at 22:16):

yurydelendik commented on Issue #2143:

I feel a little bit intimidated by the old_to_new logic here. I hope there is a chance you can adapt my proposal at https://github.com/yurydelendik/wasmtime/tree/ggreif/main with this PR. (If not I will still try my best but it is too hard)

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 00:06):

ggreif commented on Issue #2143:

I am happy to look into your proposal (tomorrow, it is really late here)! Meanwhile the keys of old_to_new are the byte offsets for the DW_OPs before translation and the values in the map are the corresponding jump sources and targets of the in terms of the expanded location expression offsets. For every Code block preceded by a LandingPad I also add a few key->value mappings corresponding to the potential internal operation offsets. After the key->value map is fully built, I visit each jump_arc and look it up to obtain the translated jump arc. Since the source of the translated jump arc is directly behind the 3 byte DW_OP_bra/skip, we know how to backpatch the jump displacement.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 00:10):

ggreif edited a comment on Issue #2143:

I am happy to look into your proposal (tomorrow, it is really late here)! Meanwhile the keys of old_to_new are the byte offsets for the DW_OPs before translation and the values in the map are the corresponding jump sources and targets of the in terms of the expanded location expression offsets. For every Code block preceded by a LandingPad I also add a few key->value mappings corresponding to the potential internal operation offsets. After the key->value map is fully built, I visit each jump_arc and look it up to obtain the translated jump arc. Since the source of the translated jump arc is directly behind the 3 byte DW_OP_bra/skip, I know how to find the jump operation and then backpatch the jump displacement.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 10:10):

ggreif commented on Issue #2143:

I looked into your branch. You draw global ids from a static supply, which eliminates a bunch of offset complexity, and adds machinery in different other places. I still don't see where the pre-translation ids meet the post-translation ones. I'll look harder.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 10:20):

ggreif edited a comment on Issue #2143:

I looked into your branch. You draw global ids from a static supply, which eliminates a bunch of offset complexity, and adds machinery in different other places. I still don't see where the pre-translation ids meet the post-translation ones. I'll look harder.

I think I understand now. Feel free to file a PR against this branch.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 10:22):

ggreif edited a comment on Issue #2143:

I looked into your branch. You draw global ids from a static supply, which eliminates a bunch of offset complexity, and adds machinery in different other places. I still don't see where the pre-translation ids meet the post-translation ones. I'll look harder.

I think I understand now. You run a pre-pass on the original expression to fish for potential landing sites.

Feel free to file a PR against this branch.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 10:27):

ggreif edited a comment on Issue #2143:

I looked into your branch. You draw global ids from a static supply, which eliminates a bunch of offset complexity, and adds machinery in different other places. I still don't see where the pre-translation ids meet the post-translation ones. I'll look harder.

I think I understand now. You run a pre-pass on the original expression to fish for potential landing sites.

Feel free to file a PR against this branch. Done: https://github.com/ggreif/wasmtime/pull/1, ping me when you think I can merge.

view this post on Zulip Wasmtime GitHub notifications bot (Aug 26 2020 at 22:19):

yurydelendik commented on Issue #2143:

Thank you for the patch

Last updated: Dec 23 2024 at 12:05 UTC