1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Trivial copy propagation pass.
13 //! This uses def-use analysis to remove values that have exactly one def and one use, which must
16 //! To give an example, we look for patterns that look like:
22 //! where `DEST` and `SRC` are both locals of some form. We replace that with:
28 //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only
29 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
32 use rustc
::mir
::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind}
;
33 use rustc
::mir
::transform
::{MirPass, MirSource}
;
34 use rustc
::mir
::visit
::MutVisitor
;
35 use rustc
::ty
::TyCtxt
;
36 use util
::def_use
::DefUseAnalysis
;
38 pub struct CopyPropagation
;
40 impl MirPass
for CopyPropagation
{
41 fn run_pass
<'a
, 'tcx
>(&self,
42 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
44 mir
: &mut Mir
<'tcx
>) {
46 MirSource
::Const(_
) => {
47 // Don't run on constants, because constant qualification might reject the
51 MirSource
::Static(..) | MirSource
::Promoted(..) => {
52 // Don't run on statics and promoted statics, because trans might not be able to
53 // evaluate the optimized IR.
56 MirSource
::Fn(function_node_id
) => {
57 if tcx
.is_const_fn(tcx
.hir
.local_def_id(function_node_id
)) {
58 // Don't run on const functions, as, again, trans might not be able to evaluate
63 MirSource
::GeneratorDrop(_
) => (),
66 // We only run when the MIR optimization level is > 1.
67 // This avoids a slow pass, and messing up debug info.
68 if tcx
.sess
.opts
.debugging_opts
.mir_opt_level
<= 1 {
73 let mut def_use_analysis
= DefUseAnalysis
::new(mir
);
74 def_use_analysis
.analyze(mir
);
76 let mut changed
= false;
77 for dest_local
in mir
.local_decls
.indices() {
78 debug
!("Considering destination local: {:?}", dest_local
);
83 // The destination must have exactly one def.
84 let dest_use_info
= def_use_analysis
.local_info(dest_local
);
85 let dest_def_count
= dest_use_info
.def_count_not_including_drop();
86 if dest_def_count
== 0 {
87 debug
!(" Can't copy-propagate local: dest {:?} undefined",
91 if dest_def_count
> 1 {
92 debug
!(" Can't copy-propagate local: dest {:?} defined {} times",
94 dest_use_info
.def_count());
97 if dest_use_info
.use_count() == 0 {
98 debug
!(" Can't copy-propagate local: dest {:?} unused",
102 let dest_lvalue_def
= dest_use_info
.defs_and_uses
.iter().filter(|lvalue_def
| {
103 lvalue_def
.context
.is_mutating_use() && !lvalue_def
.context
.is_drop()
105 location
= dest_lvalue_def
.location
;
107 let basic_block
= &mir
[location
.block
];
108 let statement_index
= location
.statement_index
;
109 let statement
= match basic_block
.statements
.get(statement_index
) {
110 Some(statement
) => statement
,
112 debug
!(" Can't copy-propagate local: used in terminator");
117 // That use of the source must be an assignment.
118 match statement
.kind
{
119 StatementKind
::Assign(Lvalue
::Local(local
), Rvalue
::Use(ref operand
)) if
120 local
== dest_local
=> {
121 let maybe_action
= match *operand
{
122 Operand
::Consume(ref src_lvalue
) => {
123 Action
::local_copy(&mir
, &def_use_analysis
, src_lvalue
)
125 Operand
::Constant(ref src_constant
) => {
126 Action
::constant(src_constant
)
130 Some(this_action
) => action
= this_action
,
135 debug
!(" Can't copy-propagate local: source use is not an \
142 changed
= action
.perform(mir
, &def_use_analysis
, dest_local
, location
) || changed
;
143 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
144 // regenerating the chains.
155 PropagateLocalCopy(Local
),
156 PropagateConstant(Constant
<'tcx
>),
159 impl<'tcx
> Action
<'tcx
> {
160 fn local_copy(mir
: &Mir
<'tcx
>, def_use_analysis
: &DefUseAnalysis
, src_lvalue
: &Lvalue
<'tcx
>)
161 -> Option
<Action
<'tcx
>> {
162 // The source must be a local.
163 let src_local
= if let Lvalue
::Local(local
) = *src_lvalue
{
166 debug
!(" Can't copy-propagate local: source is not a local");
170 // We're trying to copy propagate a local.
171 // There must be exactly one use of the source used in a statement (not in a terminator).
172 let src_use_info
= def_use_analysis
.local_info(src_local
);
173 let src_use_count
= src_use_info
.use_count();
174 if src_use_count
== 0 {
175 debug
!(" Can't copy-propagate local: no uses");
178 if src_use_count
!= 1 {
179 debug
!(" Can't copy-propagate local: {} uses", src_use_info
.use_count());
183 // Verify that the source doesn't change in between. This is done conservatively for now,
184 // by ensuring that the source has exactly one mutation. The goal is to prevent things
191 // From being misoptimized into:
195 let src_def_count
= src_use_info
.def_count_not_including_drop();
196 // allow function arguments to be propagated
197 if src_def_count
> 1 ||
198 (src_def_count
== 0 && mir
.local_kind(src_local
) != LocalKind
::Arg
) {
199 debug
!(" Can't copy-propagate local: {} defs of src",
200 src_use_info
.def_count_not_including_drop());
204 Some(Action
::PropagateLocalCopy(src_local
))
207 fn constant(src_constant
: &Constant
<'tcx
>) -> Option
<Action
<'tcx
>> {
208 Some(Action
::PropagateConstant((*src_constant
).clone()))
213 def_use_analysis
: &DefUseAnalysis
<'tcx
>,
218 Action
::PropagateLocalCopy(src_local
) => {
219 // Eliminate the destination and the assignment.
221 // First, remove all markers.
223 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
224 debug
!(" Replacing all uses of {:?} with {:?} (local)",
227 for lvalue_use
in &def_use_analysis
.local_info(dest_local
).defs_and_uses
{
228 if lvalue_use
.context
.is_storage_marker() {
229 mir
.make_statement_nop(lvalue_use
.location
)
232 for lvalue_use
in &def_use_analysis
.local_info(src_local
).defs_and_uses
{
233 if lvalue_use
.context
.is_storage_marker() {
234 mir
.make_statement_nop(lvalue_use
.location
)
238 // Replace all uses of the destination local with the source local.
239 def_use_analysis
.replace_all_defs_and_uses_with(dest_local
, mir
, src_local
);
241 // Finally, zap the now-useless assignment instruction.
242 debug
!(" Deleting assignment");
243 mir
.make_statement_nop(location
);
247 Action
::PropagateConstant(src_constant
) => {
248 // First, remove all markers.
250 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
251 debug
!(" Replacing all uses of {:?} with {:?} (constant)",
254 let dest_local_info
= def_use_analysis
.local_info(dest_local
);
255 for lvalue_use
in &dest_local_info
.defs_and_uses
{
256 if lvalue_use
.context
.is_storage_marker() {
257 mir
.make_statement_nop(lvalue_use
.location
)
261 // Replace all uses of the destination local with the constant.
262 let mut visitor
= ConstantPropagationVisitor
::new(dest_local
,
264 for dest_lvalue_use
in &dest_local_info
.defs_and_uses
{
265 visitor
.visit_location(mir
, dest_lvalue_use
.location
)
268 // Zap the assignment instruction if we eliminated all the uses. We won't have been
269 // able to do that if the destination was used in a projection, because projections
270 // must have lvalues on their LHS.
271 let use_count
= dest_local_info
.use_count();
272 if visitor
.uses_replaced
== use_count
{
273 debug
!(" {} of {} use(s) replaced; deleting assignment",
274 visitor
.uses_replaced
,
276 mir
.make_statement_nop(location
);
278 } else if visitor
.uses_replaced
== 0 {
279 debug
!(" No uses replaced; not deleting assignment");
282 debug
!(" {} of {} use(s) replaced; not deleting assignment",
283 visitor
.uses_replaced
,
292 struct ConstantPropagationVisitor
<'tcx
> {
294 constant
: Constant
<'tcx
>,
295 uses_replaced
: usize,
298 impl<'tcx
> ConstantPropagationVisitor
<'tcx
> {
299 fn new(dest_local
: Local
, constant
: Constant
<'tcx
>)
300 -> ConstantPropagationVisitor
<'tcx
> {
301 ConstantPropagationVisitor
{
309 impl<'tcx
> MutVisitor
<'tcx
> for ConstantPropagationVisitor
<'tcx
> {
310 fn visit_operand(&mut self, operand
: &mut Operand
<'tcx
>, location
: Location
) {
311 self.super_operand(operand
, location
);
314 Operand
::Consume(Lvalue
::Local(local
)) if local
== self.dest_local
=> {}
318 *operand
= Operand
::Constant(box self.constant
.clone());
319 self.uses_replaced
+= 1