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

MIR optimization tracking issue. #44285

Open
eddyb opened this issue Sep 3, 2017 · 8 comments

Comments

Projects
None yet
5 participants
@eddyb
Copy link
Member

commented Sep 3, 2017

As all efforts have more stalled, I'll use this to note down some ideas (cc @rust-lang/compiler):

  • rustc_mir::expand: take a MIR fragment (e.g. an intrinsic call) and lazily emit another MIR fragment which is the equivalent expansion
  • rustc_mir::reduce: generalized dataflow toolkit for writing localized transformations which must cause dataflow information to converge, and thus can be run until fixpoint
    • this will require require a lot of design work if we want to pull it off, at least for anything more than constant folding and CFG simplification
    • similar to expand but instead of (just) emitting a MIR fragment, a few blessed mutations (somewhat like @arielb1's patch tools) could be allowed, which are interpreted by the dataflow toolkit with minimal recomputation
  • extract and cache the points of the CFG through which dataflow might change during iterations (e.g. loop bodies and the backedges pointing to them) to minimize the copies of the dataflow state that must be kept around - that is, a function with no loops should complete forward dataflow with no per-block state caching (assuming RPO traversal)
    • would allow keeping more than plain bits without worrying as much about memory usage
    • could let us switch to EBBs without caching the non-EBB CFG, which is what @Mark-Simulacrum hit when he attempted EBBs
  • [#44308] use Local instead of Operand for index projections, so that Lvalue stops being a tree
  • [#44308] use Local instead of Lvalue in Storage{Live,Dead}
  • compress some lvalues (field/const-index paths) into [u8; 8] / u64 for O(1) dataflow lookup or even on-the-fly SROA
  • [#46142] split Operand::Consume into copies and moves, the latter invalidating all borrows
  • last-use analysis to turn the last copy of an unborrowed local into a move
    • MIR borrowck could do more here, at least in safe code
  • shrink/regenerate live ranges based on moves
  • propagate destinations backwards (and sources forward?) through moves
  • remove Rvalue::Aggregate in favor of field assignment and SetDiscriminant
    • SetDiscriminant(0) on non-enums can be pruned after borrowck runs
  • track fields and overlaps within a local, in def-use chains
  • mir::Place should not be a recursive datastructure (https://paper.dropbox.com/doc/Place-2.0-current-PR-status--AYpEHnZVlMVhug5z7XDxiqgbAg-vmbnFv8VkCEuL57QfWWMH)
  • Make Deref not a place projection (https://paper.dropbox.com/doc/Place-2.0--AYrQzvo5k2eL2v57XD__sDrZAg-9NjhX4N9I3dEt6YCJM8Ln)
  • Make Index not a place projection (https://paper.dropbox.com/doc/Place-2.0--AYrQzvo5k2eL2v57XD__sDrZAg-9NjhX4N9I3dEt6YCJM8Ln)
@arielb1

This comment has been minimized.

Copy link
Contributor

commented Sep 3, 2017

should SwitchInt and Assert (the two conditional terminators) always take an Lvalue and the constant case be replaced with a Goto by folding? Or is this too extreme?

Is that a normalization concern?

The MIR that enters borrowck etc. needs to have if-statements still present, otherwise we won't borrowck anything within an if false.

Second, if we're chasing normalization, the CFG changes made by SimplifyCfg are probably more important. I think one possibility is that we would store a worklist of MIR un-normalizations and have a "NormalizeMir" pass that runs over then and applies them. This is needed because sometimes we want a temporarily-unnormalized MIR, e.g. for keeping cfg-dependent info (dominatortree etc.) valid.

@arielb1

This comment has been minimized.

Copy link
Contributor

commented Sep 3, 2017

limit lvalues with projections to the LHS of an assignment, Rvalue::Ref and Rvalue::Use, as opposed to all Operand::Consume - index projections in particular make Lvalue a tree right now which complicates a lot of transformations

I'm not sure why complicated operands in function calls are worse than complicated operands in Rvalue::Use. OTOH, forcing array indexes to be an Lvalue::Local should get rid of the "tree-like"ness

@eddyb

This comment has been minimized.

Copy link
Member Author

commented Sep 3, 2017

The MIR that enters borrowck etc. needs to have if-statements still present, otherwise we won't borrowck anything within an if false.

I'd expect that to be if temp with temp = false; just before it, FWIW.

OTOH, forcing array indexes to be an Lvalue::Local should get rid of the "tree-like"ness

Yeah, I'm leaning in that direction myself, we'll see how clean I can make it.

@arielb1

This comment has been minimized.

Copy link
Contributor

commented Sep 3, 2017

I'd expect that to be if temp with temp = false; just before it, FWIW.

Nope. false is a valid operand, so we get a MIR if false. It's possible for the MIR builder to handle this, through.

I think that keeping an unnormalized SwitchInt is important for the same reason keeping an unnormalized CFG is important - we don't want to change things under our feet in the middle of a pass.

@eddyb

This comment has been minimized.

Copy link
Member Author

commented Sep 3, 2017

@arielb1 I mean that if if took an Lvalue so the only options were if temp and goto.

bors added a commit that referenced this issue Sep 5, 2017

Auto merge of #44308 - eddyb:local-index, r=arielb1
[MIR] Restrict ProjectionElem::Index and Storage{Live,Dead} to Local.

(see #44285)

r? @nikomatsakis
@nox

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2018

Seems like there is more interest this year about MIR optimisations in general, so pinging WG here.

Cc @rust-lang/wg-codegen

@steveklabnik

This comment has been minimized.

Copy link
Member

commented Feb 26, 2019

Triage: still a lot of interest, no movement yet that I'm aware of.

@oli-obk oli-obk added the metabug label Mar 5, 2019

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Mar 5, 2019

we now have the @rust-lang/wg-mir-opt working group. @spastorino is currently remodelling mir::Place as described in https://paper.dropbox.com/doc/Place-2.0-current-PR-status--AYpEHnZVlMVhug5z7XDxiqgbAg-vmbnFv8VkCEuL57QfWWMH

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.