Stream: t-compiler/wg-mir-opt

Topic: Identity match optimization


Simon Vandel Sillesen (Jul 23 2020 at 17:45, on Zulip):

Playing around with different snippets of code, I found these that are somewhat interesting:
https://rust.godbolt.org/z/EYW9na

https://rust.godbolt.org/z/Mc8Ksa

Thoughts on the above?

Wesley Wiser (Jul 23 2020 at 17:50, on Zulip):

I would have expected SimplifyArmIdentity to optimize the MIR to a move

I rewrote a lot of that pass to try to get it working without depending on the copy propagation pass which is unlikely to be stabilized anytime soon. I wonder if one of the other mir-opt-level >= 2 passes is causing it to not trigger?

This seems to be a more complex variant of the first snippet. When in the Some(_) variant, x.unwrap() should be the same value as the variant value.

I'm surprised unwrap isn't getting inlined. I would think it's a good candidate.

Simon Vandel Sillesen (Jul 23 2020 at 18:03, on Zulip):

I wonder if one of the other mir-opt-level >= 2 passes is causing it to not trigger?

How would one check this? Does a parameter exist to enable/disable passes? Write a MIR-opt test?

I would think it's a good candidate.

Is debug logs the easiest way to verify why this did not fire?

Wesley Wiser (Jul 23 2020 at 18:06, on Zulip):

How would one check this? Does a parameter exist to enable/disable passes? Write a MIR-opt test?

The "easiest" thing to do would probably be to build rustc locally and remove this check to see if it works without -Zmir-opt-level=3

Wesley Wiser (Jul 23 2020 at 18:06, on Zulip):

Is debug logs the easiest way to verify why this did not fire?

Yeah, in particular RUSTC_LOG=rustc_mir::transform::inline should give you what you need

Wesley Wiser (Jul 23 2020 at 18:06, on Zulip):

er the last part might be Inline or inliner I forget

Simon Vandel Sillesen (Jul 23 2020 at 18:13, on Zulip):

https://rust.godbolt.org/z/EYW9na

So I checked all variants {0,1,2,3} of -Zmir-opt-level and all included a discriminant check in the final MIR. It is reasonable to have this eliminated, right? Am I understanding it correctly that that would be the job of SimplifyArmIdentity?

Wesley Wiser (Jul 23 2020 at 18:13, on Zulip):

I think you're right

Wesley Wiser (Jul 23 2020 at 18:14, on Zulip):

I recall even writing a test similar to this

Wesley Wiser (Jul 23 2020 at 18:14, on Zulip):

Yeah https://github.com/rust-lang/rust/blob/39a295f52637817ba8584cb9bcebef91fd0a9f4f/src/test/mir-opt/simplify-arm.rs

Wesley Wiser (Jul 23 2020 at 18:16, on Zulip):

Oh no, looks like this didn't work then either https://github.com/rust-lang/rust/commit/6de6d70ae0a21b779d63d885438c7214e17e7a6d#diff-835a5cded6e7812bdecc1a577fcefe29

Wesley Wiser (Jul 23 2020 at 18:18, on Zulip):

I guess the pass needs some additional logic to understand that discriminant(_0) = 0 is the same as _0 = move _1; for the None case

Simon Vandel Sillesen (Jul 23 2020 at 18:36, on Zulip):

I could take a look into it. Do you have any idea/pointers on the top of your head that could help me, or should I just dive into it?

Wesley Wiser (Jul 23 2020 at 18:39, on Zulip):

Without having thought a lot about it, it seems like there's probably two approaches you could take:

Wesley Wiser (Jul 23 2020 at 18:40, on Zulip):

I'm pulling up that code to see if I have any other suggestions

Wesley Wiser (Jul 23 2020 at 18:41, on Zulip):

Actually

Wesley Wiser (Jul 23 2020 at 18:41, on Zulip):

https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/simplify_try.rs#L184

Wesley Wiser (Jul 23 2020 at 18:42, on Zulip):

I wonder if it isn't triggering because it doesn't see a statement like this https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/simplify_try.rs#L188

Wesley Wiser (Jul 23 2020 at 18:43, on Zulip):

If that's true, then you just need to make matching that statement optional.

Simon Vandel Sillesen (Jul 23 2020 at 18:47, on Zulip):

Could be! I don't have rustc locally yet, so I might first take a look at this in the weekend

Wesley Wiser (Jul 23 2020 at 18:47, on Zulip):

Sounds good! Feel free to ask questions if you get stuck :slight_smile:

Simon Vandel Sillesen (Jul 23 2020 at 20:19, on Zulip):

So to get started I ran ./build/x86_64-unknown-linux-gnu/stage1/bin/rustc src/test/mir-opt/simplify-arm.rs -Zmir-opt-level=3 -Zdump-mir=id. In the mir_dump folder I see SimplifyArmIdentity has run once. In it, it does some removal of a discriminant (same as https://github.com/rust-lang/rust/commit/6de6d70ae0a21b779d63d885438c7214e17e7a6d#diff-ab0af5b1ef4e6c28783346a47901e771R29 ). However there is still a discriminant left. Is that remaining discriminant to be removed in this pass? I then ran RUSTC_LOG=rustc_mir::transform::simplify_try ./build/x86_64-unknown-linux-gnu/stage1/bin/rustc src/test/mir-opt/simplify-arm.rs -Zmir-opt-level=3 2>log to check whether the pass would run again. I could only find the single pass of it

Simon Vandel Sillesen (Jul 23 2020 at 20:22, on Zulip):

So the pass does remove something and tracesSUCCESS: optimization applies!. Would it make sense to check why it does not remove the discriminant in the current pass, or is that on purpose, and it actually has to be removed in another pass?

Wesley Wiser (Jul 23 2020 at 20:24, on Zulip):

Is that remaining discriminant to be removed in this pass?

Yeah, that's the goal but it isn't working right now.

I could only find the single pass of it

I think what's probably happening is that this https://github.com/rust-lang/rust/blob/39a295f52637817ba8584cb9bcebef91fd0a9f4f/src/librustc_mir/transform/simplify_try.rs#L202 is returning None which the ? means that get_arm_identity_info returns None and so the pass doesn't trigger a second time.

Simon Vandel Sillesen (Jul 23 2020 at 20:58, on Zulip):

I added traces for the output of match_get_variant_field and match_set_variant_field. They never actually return None, so I guess it is something else that doesn't match the structure. The feedback loop for this is pretty slow - do you have experience attaching a debugger to rustc when running a test?

Wesley Wiser (Jul 23 2020 at 21:01, on Zulip):

I've generally not found it to be pleasant because rustc is too slow to use without optimizations and that makes debugging hard.

Wesley Wiser (Jul 23 2020 at 21:01, on Zulip):

Are you using the -i incremental build option?

Wesley Wiser (Jul 23 2020 at 21:01, on Zulip):

You also only need a stage 1 build.

Wesley Wiser (Jul 23 2020 at 21:02, on Zulip):

I usually use ./x.py build --stage 1 -i src/libstd when working on MIR stuff and that cuts the compilation time to 3-4 minutes.

Simon Vandel Sillesen (Jul 23 2020 at 21:08, on Zulip):

I didn't but i'll give it a go :) Is SimplifyArmIdentity really the only pass needed to completely remove any switchInt and discriminant in https://github.com/rust-lang/rust/commit/6de6d70ae0a21b779d63d885438c7214e17e7a6d#diff-ab0af5b1ef4e6c28783346a47901e771R15 ? I don't understand the current pass, but is it currently tuned to see that a switch on a discriminant, where all arms just evaluate to their corresponding discriminant values? Along the lines you mentioned about logic that sees that discriminant(_0) = 0 is the same as _0 = move _1; for the None case

Wesley Wiser (Jul 23 2020 at 21:21, on Zulip):

Is SimplifyArmIdentity really the only pass needed to completely remove any switchInt and discriminant in https://github.com/rust-lang/rust/commit/6de6d70ae0a21b779d63d885438c7214e17e7a6d#diff-ab0af5b1ef4e6c28783346a47901e771R15 ?

Should be yeah. Basically this pass just looks for blocks that copy all of an enum variant to a different local. What is doesn't seem to handle is when that variant has no fields so all we have to do is set the discriminant.

Wesley Wiser (Jul 23 2020 at 21:22, on Zulip):

The other pass is the one that looks for switches where all of the target blocks have equal bodies and then replaces the switch with a goto for one of the bodies.

Simon Vandel Sillesen (Jul 24 2020 at 20:34, on Zulip):

What is the overhead of running a MIR-opt pass? To me, it would be simpler to have a simple pass that turns discriminant(PLACE) = VAR_INDEX; into PLACE = move VAR_INDEX; iff VAR_INDEX is a field-less variant of the enum pointed to by PLACE.

Wesley Wiser (Jul 24 2020 at 20:38, on Zulip):

In general, there's not a lot of overhead.

Simon Vandel Sillesen (Jul 24 2020 at 20:44, on Zulip):

Hmm, I was kind of afraid of mixing the simpler logic of the fieldless enum discriminant with the more complex, existing logic. But maybe I can just add a specialised check for the fieldless enum discriminant before this https://github.com/rust-lang/rust/blob/39a295f52637817ba8584cb9bcebef91fd0a9f4f/src/librustc_mir/transform/simplify_try.rs#L378 ?

Simon Vandel Sillesen (Jul 24 2020 at 20:44, on Zulip):

So the two optimization variants are somewhat separated

Simon Vandel Sillesen (Jul 25 2020 at 16:03, on Zulip):

@Wesley Wiser I added a draft PR here https://github.com/rust-lang/rust/pull/74748 . It's a draft as it has errors when building core. Any ideas?
It does seem to work though. I tested it by making it run only at level 3, which did allow SimplifyBranchSame and later passes to eliminate the match

Simon Vandel Sillesen (Jul 25 2020 at 22:57, on Zulip):

PR errors should be fixed now and is ready for first review

Wesley Wiser (Jul 27 2020 at 14:49, on Zulip):

Thanks @Simon Vandel Sillesen! I will try to leave a review tonight.

Simon Vandel Sillesen (Jul 27 2020 at 21:07, on Zulip):

(deleted)

Last update: Jan 22 2021 at 13:30UTC