Stream: t-compiler/wg-mir-opt

Topic: Is CopyPropagation working correctly?


Jonas Schievink (May 25 2020 at 22:02, on Zulip):

These mir-opt tests all show empty diffs:

This one seems okay:

Jonas Schievink (May 25 2020 at 22:04, on Zulip):

My destination propagation pass will also make the latter a no-op. I guess we can remove the copy-prop pass entirely, it's slow and hasn't seen any significant improvements in years.

Félix Fischer (May 26 2020 at 00:10, on Zulip):

Ohh, that's super cool @Jonas Schievink

Félix Fischer (May 26 2020 at 00:10, on Zulip):

So I'm guessing that copy-prop and destination prop are the same optimization in this context?

Félix Fischer (May 26 2020 at 00:11, on Zulip):

Only they are different names

Félix Fischer (May 26 2020 at 00:11, on Zulip):

Like copy-prop is the old one, and dest-prop is the new one you're making?

Félix Fischer (May 26 2020 at 00:11, on Zulip):

Or is destination prop a generalization of copy prop?

Jonas Schievink (May 26 2020 at 10:54, on Zulip):

My understanding is that copy propagation is a general concept, not a specific optimization. The old copy propagation pass is very simplistic and only handles a couple of cases, so it's possible that my pass can optimize strictly more code, although I haven't checked this. Destination propagation is a somewhat more specific term that includes the way copies are propagated (by moving the x destination of some x = y; copy backwards to where y used to be).

Félix Fischer (May 26 2020 at 17:09, on Zulip):

Ahh, I see :)

Jonas Schievink (Sep 18 2020 at 23:03, on Zulip):

We now have a bit more data on this: https://github.com/rust-lang/rust/pull/76569#issuecomment-691162316

It looks like dest prop performs roughly the same number of propagations as the old copy prop pass, but they are different subsets, so copy prop is still beneficial.

This makes sense, since copy prop does forward propagation, while dest prop propagates backwards. Some propagations only work in one direction.

Jonas Schievink (Sep 18 2020 at 23:10, on Zulip):

(I'm still going to go ahead with the removal – turns out copy prop has been unsound for a while #76740, and we should be able to reuse a bunch of the logic from dest prop in a future forwards propagation pass)

nagisa (Sep 18 2020 at 23:57, on Zulip):

if you want best efficiency, you want to combine and interleave forward and back propagation together with const propagation in a single pass that does all of these things until it reaches a fixpoint.

nagisa (Sep 18 2020 at 23:58, on Zulip):

there are examples of instruction sequences where any one of the three missing would miss an optimisation.

nagisa (Sep 18 2020 at 23:59, on Zulip):

That said, we still haven’t an alias analysis in rustc, so I have no idea how y'all are planning to make any sound propagation optimisation.

Jonas Schievink (Sep 19 2020 at 00:00, on Zulip):

Sounds reasonable

Jonas Schievink (Sep 19 2020 at 00:00, on Zulip):

nagisa said:

That said, we still haven’t an alias analysis in rustc, so I have no idea how y'all are planning to make any sound propagation optimisation.

Currently by ignoring locals whose addresses are taken entirely

nagisa (Sep 19 2020 at 00:02, on Zulip):

hm, I have a feeling that this was not sufficient last time I looked at implementing propagation many many years ago, but I don’t remember if that was actually true anymore.

Jonas Schievink (Sep 19 2020 at 00:04, on Zulip):

There's lots of code in the dest prop pass to track conflicts between locals, if that's what you mean

Jonas Schievink (Sep 19 2020 at 00:06, on Zulip):

It also bails out when a candidate place contains indirection in general, etc.

Last update: Sep 28 2020 at 15:30UTC