]>
Commit | Line | Data |
---|---|---|
9e0c209e SL |
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. | |
4 | // | |
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. | |
10 | ||
11 | //! Def-use analysis. | |
12 | ||
13 | use rustc::mir::repr::{Local, Location, Lvalue, Mir}; | |
14 | use rustc::mir::visit::{LvalueContext, MutVisitor, Visitor}; | |
15 | use rustc_data_structures::indexed_vec::{Idx, IndexVec}; | |
16 | use std::marker::PhantomData; | |
17 | use std::mem; | |
18 | ||
19 | pub struct DefUseAnalysis<'tcx> { | |
20 | info: IndexVec<Local, Info<'tcx>>, | |
21 | mir_summary: MirSummary, | |
22 | } | |
23 | ||
24 | #[derive(Clone)] | |
25 | pub struct Info<'tcx> { | |
26 | pub defs_and_uses: Vec<Use<'tcx>>, | |
27 | } | |
28 | ||
29 | #[derive(Clone)] | |
30 | pub struct Use<'tcx> { | |
31 | pub context: LvalueContext<'tcx>, | |
32 | pub location: Location, | |
33 | } | |
34 | ||
35 | impl<'tcx> DefUseAnalysis<'tcx> { | |
36 | pub fn new(mir: &Mir<'tcx>) -> DefUseAnalysis<'tcx> { | |
37 | DefUseAnalysis { | |
38 | info: IndexVec::from_elem_n(Info::new(), mir.count_locals()), | |
39 | mir_summary: MirSummary::new(mir), | |
40 | } | |
41 | } | |
42 | ||
43 | pub fn analyze(&mut self, mir: &Mir<'tcx>) { | |
44 | let mut finder = DefUseFinder { | |
45 | info: mem::replace(&mut self.info, IndexVec::new()), | |
46 | mir_summary: self.mir_summary, | |
47 | }; | |
48 | finder.visit_mir(mir); | |
49 | self.info = finder.info | |
50 | } | |
51 | ||
52 | pub fn local_info(&self, local: Local) -> &Info<'tcx> { | |
53 | &self.info[local] | |
54 | } | |
55 | ||
56 | pub fn local_info_mut(&mut self, local: Local) -> &mut Info<'tcx> { | |
57 | &mut self.info[local] | |
58 | } | |
59 | ||
60 | fn mutate_defs_and_uses<F>(&self, local: Local, mir: &mut Mir<'tcx>, mut callback: F) | |
61 | where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, | |
62 | LvalueContext<'tcx>, | |
63 | Location) { | |
64 | for lvalue_use in &self.info[local].defs_and_uses { | |
65 | MutateUseVisitor::new(local, | |
66 | &mut callback, | |
67 | self.mir_summary, | |
68 | mir).visit_location(mir, lvalue_use.location) | |
69 | } | |
70 | } | |
71 | ||
72 | /// FIXME(pcwalton): This should update the def-use chains. | |
73 | pub fn replace_all_defs_and_uses_with(&self, | |
74 | local: Local, | |
75 | mir: &mut Mir<'tcx>, | |
76 | new_lvalue: Lvalue<'tcx>) { | |
77 | self.mutate_defs_and_uses(local, mir, |lvalue, _, _| *lvalue = new_lvalue.clone()) | |
78 | } | |
79 | } | |
80 | ||
81 | struct DefUseFinder<'tcx> { | |
82 | info: IndexVec<Local, Info<'tcx>>, | |
83 | mir_summary: MirSummary, | |
84 | } | |
85 | ||
86 | impl<'tcx> DefUseFinder<'tcx> { | |
87 | fn lvalue_mut_info(&mut self, lvalue: &Lvalue<'tcx>) -> Option<&mut Info<'tcx>> { | |
88 | let info = &mut self.info; | |
89 | self.mir_summary.local_index(lvalue).map(move |local| &mut info[local]) | |
90 | } | |
91 | } | |
92 | ||
93 | impl<'tcx> Visitor<'tcx> for DefUseFinder<'tcx> { | |
94 | fn visit_lvalue(&mut self, | |
95 | lvalue: &Lvalue<'tcx>, | |
96 | context: LvalueContext<'tcx>, | |
97 | location: Location) { | |
98 | if let Some(ref mut info) = self.lvalue_mut_info(lvalue) { | |
99 | info.defs_and_uses.push(Use { | |
100 | context: context, | |
101 | location: location, | |
102 | }) | |
103 | } | |
104 | self.super_lvalue(lvalue, context, location) | |
105 | } | |
106 | } | |
107 | ||
108 | impl<'tcx> Info<'tcx> { | |
109 | fn new() -> Info<'tcx> { | |
110 | Info { | |
111 | defs_and_uses: vec![], | |
112 | } | |
113 | } | |
114 | ||
115 | pub fn def_count(&self) -> usize { | |
116 | self.defs_and_uses.iter().filter(|lvalue_use| lvalue_use.context.is_mutating_use()).count() | |
117 | } | |
118 | ||
119 | pub fn def_count_not_including_drop(&self) -> usize { | |
120 | self.defs_and_uses.iter().filter(|lvalue_use| { | |
121 | lvalue_use.context.is_mutating_use() && !lvalue_use.context.is_drop() | |
122 | }).count() | |
123 | } | |
124 | ||
125 | pub fn use_count(&self) -> usize { | |
126 | self.defs_and_uses.iter().filter(|lvalue_use| { | |
127 | lvalue_use.context.is_nonmutating_use() | |
128 | }).count() | |
129 | } | |
130 | } | |
131 | ||
132 | struct MutateUseVisitor<'tcx, F> { | |
133 | query: Local, | |
134 | callback: F, | |
135 | mir_summary: MirSummary, | |
136 | phantom: PhantomData<&'tcx ()>, | |
137 | } | |
138 | ||
139 | impl<'tcx, F> MutateUseVisitor<'tcx, F> { | |
140 | fn new(query: Local, callback: F, mir_summary: MirSummary, _: &Mir<'tcx>) | |
141 | -> MutateUseVisitor<'tcx, F> | |
142 | where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) { | |
143 | MutateUseVisitor { | |
144 | query: query, | |
145 | callback: callback, | |
146 | mir_summary: mir_summary, | |
147 | phantom: PhantomData, | |
148 | } | |
149 | } | |
150 | } | |
151 | ||
152 | impl<'tcx, F> MutVisitor<'tcx> for MutateUseVisitor<'tcx, F> | |
153 | where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) { | |
154 | fn visit_lvalue(&mut self, | |
155 | lvalue: &mut Lvalue<'tcx>, | |
156 | context: LvalueContext<'tcx>, | |
157 | location: Location) { | |
158 | if self.mir_summary.local_index(lvalue) == Some(self.query) { | |
159 | (self.callback)(lvalue, context, location) | |
160 | } | |
161 | self.super_lvalue(lvalue, context, location) | |
162 | } | |
163 | } | |
164 | ||
165 | /// A small structure that enables various metadata of the MIR to be queried | |
166 | /// without a reference to the MIR itself. | |
167 | #[derive(Clone, Copy)] | |
168 | pub struct MirSummary { | |
169 | arg_count: usize, | |
170 | var_count: usize, | |
171 | temp_count: usize, | |
172 | } | |
173 | ||
174 | impl MirSummary { | |
175 | pub fn new(mir: &Mir) -> MirSummary { | |
176 | MirSummary { | |
177 | arg_count: mir.arg_decls.len(), | |
178 | var_count: mir.var_decls.len(), | |
179 | temp_count: mir.temp_decls.len(), | |
180 | } | |
181 | } | |
182 | ||
183 | pub fn local_index<'tcx>(&self, lvalue: &Lvalue<'tcx>) -> Option<Local> { | |
184 | match *lvalue { | |
185 | Lvalue::Arg(arg) => Some(Local::new(arg.index())), | |
186 | Lvalue::Var(var) => Some(Local::new(var.index() + self.arg_count)), | |
187 | Lvalue::Temp(temp) => { | |
188 | Some(Local::new(temp.index() + self.arg_count + self.var_count)) | |
189 | } | |
190 | Lvalue::ReturnPointer => { | |
191 | Some(Local::new(self.arg_count + self.var_count + self.temp_count)) | |
192 | } | |
193 | _ => None, | |
194 | } | |
195 | } | |
196 | } | |
197 |