]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
223e47cc LB |
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 | ||
1a4d82fc JJ |
11 | //! A classic liveness analysis based on dataflow over the AST. Computes, |
12 | //! for each local variable in a function, whether that variable is live | |
13 | //! at a given point. Program execution points are identified by their | |
14 | //! id. | |
15 | //! | |
16 | //! # Basic idea | |
17 | //! | |
18 | //! The basic model is that each local variable is assigned an index. We | |
19 | //! represent sets of local variables using a vector indexed by this | |
20 | //! index. The value in the vector is either 0, indicating the variable | |
21 | //! is dead, or the id of an expression that uses the variable. | |
22 | //! | |
23 | //! We conceptually walk over the AST in reverse execution order. If we | |
24 | //! find a use of a variable, we add it to the set of live variables. If | |
25 | //! we find an assignment to a variable, we remove it from the set of live | |
26 | //! variables. When we have to merge two flows, we take the union of | |
27 | //! those two flows---if the variable is live on both paths, we simply | |
28 | //! pick one id. In the event of loops, we continue doing this until a | |
29 | //! fixed point is reached. | |
30 | //! | |
31 | //! ## Checking initialization | |
32 | //! | |
33 | //! At the function entry point, all variables must be dead. If this is | |
34 | //! not the case, we can report an error using the id found in the set of | |
35 | //! live variables, which identifies a use of the variable which is not | |
36 | //! dominated by an assignment. | |
37 | //! | |
38 | //! ## Checking moves | |
39 | //! | |
40 | //! After each explicit move, the variable must be dead. | |
41 | //! | |
42 | //! ## Computing last uses | |
43 | //! | |
44 | //! Any use of the variable where the variable is dead afterwards is a | |
45 | //! last use. | |
46 | //! | |
47 | //! # Implementation details | |
48 | //! | |
49 | //! The actual implementation contains two (nested) walks over the AST. | |
50 | //! The outer walk has the job of building up the ir_maps instance for the | |
51 | //! enclosing function. On the way down the tree, it identifies those AST | |
52 | //! nodes and variable IDs that will be needed for the liveness analysis | |
53 | //! and assigns them contiguous IDs. The liveness id for an AST node is | |
c34b1796 AL |
54 | //! called a `live_node` (it's a newtype'd usize) and the id for a variable |
55 | //! is called a `variable` (another newtype'd usize). | |
1a4d82fc JJ |
56 | //! |
57 | //! On the way back up the tree, as we are about to exit from a function | |
58 | //! declaration we allocate a `liveness` instance. Now that we know | |
59 | //! precisely how many nodes and variables we need, we can allocate all | |
60 | //! the various arrays that we will need to precisely the right size. We then | |
61 | //! perform the actual propagation on the `liveness` instance. | |
62 | //! | |
63 | //! This propagation is encoded in the various `propagate_through_*()` | |
64 | //! methods. It effectively does a reverse walk of the AST; whenever we | |
65 | //! reach a loop node, we iterate until a fixed point is reached. | |
66 | //! | |
67 | //! ## The `Users` struct | |
68 | //! | |
69 | //! At each live node `N`, we track three pieces of information for each | |
70 | //! variable `V` (these are encapsulated in the `Users` struct): | |
71 | //! | |
72 | //! - `reader`: the `LiveNode` ID of some node which will read the value | |
73 | //! that `V` holds on entry to `N`. Formally: a node `M` such | |
74 | //! that there exists a path `P` from `N` to `M` where `P` does not | |
75 | //! write `V`. If the `reader` is `invalid_node()`, then the current | |
76 | //! value will never be read (the variable is dead, essentially). | |
77 | //! | |
78 | //! - `writer`: the `LiveNode` ID of some node which will write the | |
79 | //! variable `V` and which is reachable from `N`. Formally: a node `M` | |
80 | //! such that there exists a path `P` from `N` to `M` and `M` writes | |
81 | //! `V`. If the `writer` is `invalid_node()`, then there is no writer | |
82 | //! of `V` that follows `N`. | |
83 | //! | |
84 | //! - `used`: a boolean value indicating whether `V` is *used*. We | |
85 | //! distinguish a *read* from a *use* in that a *use* is some read that | |
86 | //! is not just used to generate a new value. For example, `x += 1` is | |
87 | //! a read but not a use. This is used to generate better warnings. | |
88 | //! | |
89 | //! ## Special Variables | |
90 | //! | |
91 | //! We generate various special variables for various, well, special purposes. | |
92 | //! These are described in the `specials` struct: | |
93 | //! | |
94 | //! - `exit_ln`: a live node that is generated to represent every 'exit' from | |
95 | //! the function, whether it be by explicit return, panic, or other means. | |
96 | //! | |
97 | //! - `fallthrough_ln`: a live node that represents a fallthrough | |
98 | //! | |
99 | //! - `no_ret_var`: a synthetic variable that is only 'read' from, the | |
100 | //! fallthrough node. This allows us to detect functions where we fail | |
101 | //! to return explicitly. | |
102 | //! - `clean_exit_var`: a synthetic variable that is only 'read' from the | |
103 | //! fallthrough node. It is only live if the function could converge | |
104 | //! via means other than an explicit `return` expression. That is, it is | |
105 | //! only dead if the end of the function's block can never be reached. | |
106 | //! It is the responsibility of typeck to ensure that there are no | |
107 | //! `return` expressions in a function declared as diverging. | |
108 | use self::LoopKind::*; | |
109 | use self::LiveNodeKind::*; | |
110 | use self::VarKind::*; | |
111 | ||
112 | use middle::def::*; | |
223e47cc LB |
113 | use middle::pat_util; |
114 | use middle::ty; | |
1a4d82fc JJ |
115 | use lint; |
116 | use util::nodemap::NodeMap; | |
117 | ||
c34b1796 AL |
118 | use std::{fmt, usize}; |
119 | use std::io::prelude::*; | |
120 | use std::io; | |
c34b1796 | 121 | use std::rc::Rc; |
e9174d1e | 122 | use syntax::ast::{self, NodeId}; |
1a4d82fc | 123 | use syntax::codemap::{BytePos, original_sp, Span}; |
c1a9b12d | 124 | use syntax::parse::token::special_idents; |
1a4d82fc | 125 | use syntax::ptr::P; |
e9174d1e SL |
126 | |
127 | use rustc_front::hir::Expr; | |
128 | use rustc_front::hir; | |
129 | use rustc_front::print::pprust::{expr_to_string, block_to_string}; | |
92a42be0 | 130 | use rustc_front::intravisit::{self, Visitor, FnKind}; |
1a4d82fc JJ |
131 | |
132 | /// For use with `propagate_through_loop`. | |
133 | enum LoopKind<'a> { | |
134 | /// An endless `loop` loop. | |
135 | LoopLoop, | |
136 | /// A `while` loop, with the given expression as condition. | |
137 | WhileLoop(&'a Expr), | |
1a4d82fc JJ |
138 | } |
139 | ||
c34b1796 AL |
140 | #[derive(Copy, Clone, PartialEq)] |
141 | struct Variable(usize); | |
1a4d82fc JJ |
142 | |
143 | #[derive(Copy, PartialEq)] | |
c34b1796 | 144 | struct LiveNode(usize); |
223e47cc | 145 | |
1a4d82fc | 146 | impl Variable { |
c34b1796 | 147 | fn get(&self) -> usize { let Variable(v) = *self; v } |
1a4d82fc JJ |
148 | } |
149 | ||
150 | impl LiveNode { | |
c34b1796 | 151 | fn get(&self) -> usize { let LiveNode(v) = *self; v } |
1a4d82fc JJ |
152 | } |
153 | ||
154 | impl Clone for LiveNode { | |
155 | fn clone(&self) -> LiveNode { | |
156 | LiveNode(self.get()) | |
157 | } | |
158 | } | |
159 | ||
c34b1796 | 160 | #[derive(Copy, Clone, PartialEq, Debug)] |
223e47cc | 161 | enum LiveNodeKind { |
1a4d82fc JJ |
162 | FreeVarNode(Span), |
163 | ExprNode(Span), | |
164 | VarDefNode(Span), | |
223e47cc LB |
165 | ExitNode |
166 | } | |
167 | ||
1a4d82fc JJ |
168 | fn live_node_kind_to_string(lnk: LiveNodeKind, cx: &ty::ctxt) -> String { |
169 | let cm = cx.sess.codemap(); | |
223e47cc | 170 | match lnk { |
1a4d82fc JJ |
171 | FreeVarNode(s) => { |
172 | format!("Free var node [{}]", cm.span_to_string(s)) | |
173 | } | |
174 | ExprNode(s) => { | |
175 | format!("Expr node [{}]", cm.span_to_string(s)) | |
176 | } | |
177 | VarDefNode(s) => { | |
178 | format!("Var def node [{}]", cm.span_to_string(s)) | |
179 | } | |
180 | ExitNode => "Exit node".to_string(), | |
223e47cc LB |
181 | } |
182 | } | |
183 | ||
1a4d82fc | 184 | impl<'a, 'tcx, 'v> Visitor<'v> for IrMaps<'a, 'tcx> { |
e9174d1e SL |
185 | fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v hir::FnDecl, |
186 | b: &'v hir::Block, s: Span, id: NodeId) { | |
1a4d82fc JJ |
187 | visit_fn(self, fk, fd, b, s, id); |
188 | } | |
e9174d1e | 189 | fn visit_local(&mut self, l: &hir::Local) { visit_local(self, l); } |
1a4d82fc | 190 | fn visit_expr(&mut self, ex: &Expr) { visit_expr(self, ex); } |
e9174d1e | 191 | fn visit_arm(&mut self, a: &hir::Arm) { visit_arm(self, a); } |
1a4d82fc | 192 | } |
223e47cc | 193 | |
1a4d82fc | 194 | pub fn check_crate(tcx: &ty::ctxt) { |
92a42be0 | 195 | tcx.map.krate().visit_all_items(&mut IrMaps::new(tcx)); |
223e47cc | 196 | tcx.sess.abort_if_errors(); |
223e47cc LB |
197 | } |
198 | ||
85aaf69f | 199 | impl fmt::Debug for LiveNode { |
1a4d82fc JJ |
200 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
201 | write!(f, "ln({})", self.get()) | |
202 | } | |
223e47cc LB |
203 | } |
204 | ||
85aaf69f | 205 | impl fmt::Debug for Variable { |
1a4d82fc JJ |
206 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
207 | write!(f, "v({})", self.get()) | |
208 | } | |
223e47cc LB |
209 | } |
210 | ||
211 | // ______________________________________________________________________ | |
212 | // Creating ir_maps | |
213 | // | |
214 | // This is the first pass and the one that drives the main | |
215 | // computation. It walks up and down the IR once. On the way down, | |
216 | // we count for each function the number of variables as well as | |
217 | // liveness nodes. A liveness node is basically an expression or | |
218 | // capture clause that does something of interest: either it has | |
219 | // interesting control flow or it uses/defines a local variable. | |
220 | // | |
221 | // On the way back up, at each function node we create liveness sets | |
222 | // (we now know precisely how big to make our various vectors and so | |
223 | // forth) and then do the data-flow propagation to compute the set | |
224 | // of live variables at each program point. | |
225 | // | |
226 | // Finally, we run back over the IR one last time and, using the | |
227 | // computed liveness, check various safety conditions. For example, | |
228 | // there must be no live nodes at the definition site for a variable | |
229 | // unless it has an initializer. Similarly, each non-mutable local | |
230 | // variable must not be assigned if there is some successor | |
231 | // assignment. And so forth. | |
232 | ||
970d7e83 | 233 | impl LiveNode { |
1a4d82fc | 234 | fn is_valid(&self) -> bool { |
c34b1796 | 235 | self.get() != usize::MAX |
970d7e83 | 236 | } |
223e47cc LB |
237 | } |
238 | ||
c34b1796 | 239 | fn invalid_node() -> LiveNode { LiveNode(usize::MAX) } |
223e47cc LB |
240 | |
241 | struct CaptureInfo { | |
242 | ln: LiveNode, | |
1a4d82fc | 243 | var_nid: NodeId |
223e47cc LB |
244 | } |
245 | ||
c34b1796 | 246 | #[derive(Copy, Clone, Debug)] |
223e47cc | 247 | struct LocalInfo { |
1a4d82fc | 248 | id: NodeId, |
9346a6ac | 249 | name: ast::Name |
223e47cc LB |
250 | } |
251 | ||
c34b1796 | 252 | #[derive(Copy, Clone, Debug)] |
223e47cc | 253 | enum VarKind { |
9346a6ac | 254 | Arg(NodeId, ast::Name), |
223e47cc | 255 | Local(LocalInfo), |
1a4d82fc JJ |
256 | ImplicitRet, |
257 | CleanExit | |
223e47cc LB |
258 | } |
259 | ||
1a4d82fc JJ |
260 | struct IrMaps<'a, 'tcx: 'a> { |
261 | tcx: &'a ty::ctxt<'tcx>, | |
223e47cc | 262 | |
c34b1796 AL |
263 | num_live_nodes: usize, |
264 | num_vars: usize, | |
1a4d82fc JJ |
265 | live_node_map: NodeMap<LiveNode>, |
266 | variable_map: NodeMap<Variable>, | |
267 | capture_info_map: NodeMap<Rc<Vec<CaptureInfo>>>, | |
268 | var_kinds: Vec<VarKind>, | |
269 | lnks: Vec<LiveNodeKind>, | |
223e47cc LB |
270 | } |
271 | ||
1a4d82fc JJ |
272 | impl<'a, 'tcx> IrMaps<'a, 'tcx> { |
273 | fn new(tcx: &'a ty::ctxt<'tcx>) -> IrMaps<'a, 'tcx> { | |
274 | IrMaps { | |
275 | tcx: tcx, | |
276 | num_live_nodes: 0, | |
277 | num_vars: 0, | |
85aaf69f SL |
278 | live_node_map: NodeMap(), |
279 | variable_map: NodeMap(), | |
280 | capture_info_map: NodeMap(), | |
1a4d82fc JJ |
281 | var_kinds: Vec::new(), |
282 | lnks: Vec::new(), | |
283 | } | |
223e47cc | 284 | } |
223e47cc | 285 | |
1a4d82fc | 286 | fn add_live_node(&mut self, lnk: LiveNodeKind) -> LiveNode { |
223e47cc LB |
287 | let ln = LiveNode(self.num_live_nodes); |
288 | self.lnks.push(lnk); | |
289 | self.num_live_nodes += 1; | |
290 | ||
1a4d82fc JJ |
291 | debug!("{:?} is of kind {}", ln, |
292 | live_node_kind_to_string(lnk, self.tcx)); | |
223e47cc LB |
293 | |
294 | ln | |
295 | } | |
296 | ||
1a4d82fc | 297 | fn add_live_node_for_node(&mut self, node_id: NodeId, lnk: LiveNodeKind) { |
223e47cc LB |
298 | let ln = self.add_live_node(lnk); |
299 | self.live_node_map.insert(node_id, ln); | |
300 | ||
1a4d82fc | 301 | debug!("{:?} is node {}", ln, node_id); |
223e47cc LB |
302 | } |
303 | ||
1a4d82fc | 304 | fn add_variable(&mut self, vk: VarKind) -> Variable { |
223e47cc LB |
305 | let v = Variable(self.num_vars); |
306 | self.var_kinds.push(vk); | |
307 | self.num_vars += 1; | |
308 | ||
309 | match vk { | |
1a4d82fc | 310 | Local(LocalInfo { id: node_id, .. }) | Arg(node_id, _) => { |
223e47cc | 311 | self.variable_map.insert(node_id, v); |
970d7e83 | 312 | }, |
1a4d82fc | 313 | ImplicitRet | CleanExit => {} |
223e47cc LB |
314 | } |
315 | ||
1a4d82fc | 316 | debug!("{:?} is {:?}", v, vk); |
223e47cc LB |
317 | |
318 | v | |
319 | } | |
320 | ||
1a4d82fc JJ |
321 | fn variable(&self, node_id: NodeId, span: Span) -> Variable { |
322 | match self.variable_map.get(&node_id) { | |
223e47cc LB |
323 | Some(&var) => var, |
324 | None => { | |
1a4d82fc JJ |
325 | self.tcx |
326 | .sess | |
327 | .span_bug(span, &format!("no variable registered for id {}", | |
c34b1796 | 328 | node_id)); |
223e47cc LB |
329 | } |
330 | } | |
331 | } | |
332 | ||
1a4d82fc JJ |
333 | fn variable_name(&self, var: Variable) -> String { |
334 | match self.var_kinds[var.get()] { | |
9346a6ac | 335 | Local(LocalInfo { name, .. }) | Arg(_, name) => { |
c1a9b12d | 336 | name.to_string() |
970d7e83 | 337 | }, |
1a4d82fc JJ |
338 | ImplicitRet => "<implicit-ret>".to_string(), |
339 | CleanExit => "<clean-exit>".to_string() | |
223e47cc LB |
340 | } |
341 | } | |
342 | ||
1a4d82fc JJ |
343 | fn set_captures(&mut self, node_id: NodeId, cs: Vec<CaptureInfo>) { |
344 | self.capture_info_map.insert(node_id, Rc::new(cs)); | |
223e47cc LB |
345 | } |
346 | ||
1a4d82fc JJ |
347 | fn lnk(&self, ln: LiveNode) -> LiveNodeKind { |
348 | self.lnks[ln.get()] | |
223e47cc | 349 | } |
1a4d82fc | 350 | } |
223e47cc | 351 | |
1a4d82fc | 352 | impl<'a, 'tcx, 'v> Visitor<'v> for Liveness<'a, 'tcx> { |
e9174d1e SL |
353 | fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v hir::FnDecl, |
354 | b: &'v hir::Block, s: Span, n: NodeId) { | |
1a4d82fc JJ |
355 | check_fn(self, fk, fd, b, s, n); |
356 | } | |
e9174d1e | 357 | fn visit_local(&mut self, l: &hir::Local) { |
1a4d82fc JJ |
358 | check_local(self, l); |
359 | } | |
360 | fn visit_expr(&mut self, ex: &Expr) { | |
361 | check_expr(self, ex); | |
362 | } | |
e9174d1e | 363 | fn visit_arm(&mut self, a: &hir::Arm) { |
1a4d82fc | 364 | check_arm(self, a); |
223e47cc | 365 | } |
223e47cc LB |
366 | } |
367 | ||
1a4d82fc JJ |
368 | fn visit_fn(ir: &mut IrMaps, |
369 | fk: FnKind, | |
e9174d1e SL |
370 | decl: &hir::FnDecl, |
371 | body: &hir::Block, | |
1a4d82fc JJ |
372 | sp: Span, |
373 | id: ast::NodeId) { | |
374 | debug!("visit_fn"); | |
223e47cc LB |
375 | |
376 | // swap in a new set of IR maps for this function body: | |
1a4d82fc | 377 | let mut fn_maps = IrMaps::new(ir.tcx); |
223e47cc | 378 | |
1a4d82fc | 379 | debug!("creating fn_maps: {:?}", &fn_maps as *const IrMaps); |
223e47cc | 380 | |
85aaf69f | 381 | for arg in &decl.inputs { |
1a4d82fc JJ |
382 | pat_util::pat_bindings(&ir.tcx.def_map, |
383 | &*arg.pat, | |
384 | |_bm, arg_id, _x, path1| { | |
385 | debug!("adding argument {}", arg_id); | |
b039eaaf | 386 | let name = path1.node; |
9346a6ac | 387 | fn_maps.add_variable(Arg(arg_id, name)); |
1a4d82fc | 388 | }) |
223e47cc LB |
389 | }; |
390 | ||
223e47cc LB |
391 | // gather up the various local variables, significant expressions, |
392 | // and so forth: | |
92a42be0 | 393 | intravisit::walk_fn(&mut fn_maps, fk, decl, body, sp); |
223e47cc LB |
394 | |
395 | // Special nodes and variables: | |
1a4d82fc | 396 | // - exit_ln represents the end of the fn, either by return or panic |
223e47cc LB |
397 | // - implicit_ret_var is a pseudo-variable that represents |
398 | // an implicit return | |
399 | let specials = Specials { | |
400 | exit_ln: fn_maps.add_live_node(ExitNode), | |
401 | fallthrough_ln: fn_maps.add_live_node(ExitNode), | |
1a4d82fc JJ |
402 | no_ret_var: fn_maps.add_variable(ImplicitRet), |
403 | clean_exit_var: fn_maps.add_variable(CleanExit) | |
223e47cc LB |
404 | }; |
405 | ||
406 | // compute liveness | |
1a4d82fc JJ |
407 | let mut lsets = Liveness::new(&mut fn_maps, specials); |
408 | let entry_ln = lsets.compute(decl, body); | |
223e47cc LB |
409 | |
410 | // check for various error conditions | |
1a4d82fc JJ |
411 | lsets.visit_block(body); |
412 | lsets.check_ret(id, sp, fk, entry_ln, body); | |
223e47cc LB |
413 | lsets.warn_about_unused_args(decl, entry_ln); |
414 | } | |
415 | ||
e9174d1e | 416 | fn visit_local(ir: &mut IrMaps, local: &hir::Local) { |
1a4d82fc JJ |
417 | pat_util::pat_bindings(&ir.tcx.def_map, &*local.pat, |_, p_id, sp, path1| { |
418 | debug!("adding local variable {}", p_id); | |
b039eaaf | 419 | let name = path1.node; |
1a4d82fc JJ |
420 | ir.add_live_node_for_node(p_id, VarDefNode(sp)); |
421 | ir.add_variable(Local(LocalInfo { | |
223e47cc | 422 | id: p_id, |
9346a6ac | 423 | name: name |
223e47cc | 424 | })); |
1a4d82fc | 425 | }); |
92a42be0 | 426 | intravisit::walk_local(ir, local); |
223e47cc LB |
427 | } |
428 | ||
e9174d1e | 429 | fn visit_arm(ir: &mut IrMaps, arm: &hir::Arm) { |
85aaf69f | 430 | for pat in &arm.pats { |
1a4d82fc JJ |
431 | pat_util::pat_bindings(&ir.tcx.def_map, &**pat, |bm, p_id, sp, path1| { |
432 | debug!("adding local variable {} from match with bm {:?}", | |
223e47cc | 433 | p_id, bm); |
b039eaaf | 434 | let name = path1.node; |
1a4d82fc JJ |
435 | ir.add_live_node_for_node(p_id, VarDefNode(sp)); |
436 | ir.add_variable(Local(LocalInfo { | |
223e47cc | 437 | id: p_id, |
9346a6ac | 438 | name: name |
223e47cc | 439 | })); |
1a4d82fc | 440 | }) |
223e47cc | 441 | } |
92a42be0 | 442 | intravisit::walk_arm(ir, arm); |
223e47cc LB |
443 | } |
444 | ||
1a4d82fc | 445 | fn visit_expr(ir: &mut IrMaps, expr: &Expr) { |
223e47cc LB |
446 | match expr.node { |
447 | // live nodes required for uses or definitions of variables: | |
e9174d1e | 448 | hir::ExprPath(..) => { |
c34b1796 | 449 | let def = ir.tcx.def_map.borrow().get(&expr.id).unwrap().full_def(); |
1a4d82fc JJ |
450 | debug!("expr {}: path that leads to {:?}", expr.id, def); |
451 | if let DefLocal(..) = def { | |
452 | ir.add_live_node_for_node(expr.id, ExprNode(expr.span)); | |
223e47cc | 453 | } |
92a42be0 | 454 | intravisit::walk_expr(ir, expr); |
223e47cc | 455 | } |
e9174d1e | 456 | hir::ExprClosure(..) => { |
223e47cc LB |
457 | // Interesting control flow (for loops can contain labeled |
458 | // breaks or continues) | |
1a4d82fc | 459 | ir.add_live_node_for_node(expr.id, ExprNode(expr.span)); |
223e47cc LB |
460 | |
461 | // Make a live_node for each captured variable, with the span | |
462 | // being the location that the variable is used. This results | |
463 | // in better error messages than just pointing at the closure | |
464 | // construction site. | |
1a4d82fc | 465 | let mut call_caps = Vec::new(); |
c1a9b12d | 466 | ir.tcx.with_freevars(expr.id, |freevars| { |
85aaf69f | 467 | for fv in freevars { |
b039eaaf | 468 | if let DefLocal(_, rv) = fv.def { |
1a4d82fc JJ |
469 | let fv_ln = ir.add_live_node(FreeVarNode(fv.span)); |
470 | call_caps.push(CaptureInfo {ln: fv_ln, | |
471 | var_nid: rv}); | |
472 | } | |
223e47cc | 473 | } |
1a4d82fc JJ |
474 | }); |
475 | ir.set_captures(expr.id, call_caps); | |
223e47cc | 476 | |
92a42be0 | 477 | intravisit::walk_expr(ir, expr); |
223e47cc LB |
478 | } |
479 | ||
480 | // live nodes required for interesting control flow: | |
e9174d1e | 481 | hir::ExprIf(..) | hir::ExprMatch(..) | hir::ExprWhile(..) | hir::ExprLoop(..) => { |
1a4d82fc | 482 | ir.add_live_node_for_node(expr.id, ExprNode(expr.span)); |
92a42be0 | 483 | intravisit::walk_expr(ir, expr); |
1a4d82fc | 484 | } |
e9174d1e | 485 | hir::ExprBinary(op, _, _) if ::rustc_front::util::lazy_binop(op.node) => { |
1a4d82fc | 486 | ir.add_live_node_for_node(expr.id, ExprNode(expr.span)); |
92a42be0 | 487 | intravisit::walk_expr(ir, expr); |
223e47cc LB |
488 | } |
489 | ||
490 | // otherwise, live nodes are not required: | |
e9174d1e SL |
491 | hir::ExprIndex(..) | hir::ExprField(..) | hir::ExprTupField(..) | |
492 | hir::ExprVec(..) | hir::ExprCall(..) | hir::ExprMethodCall(..) | | |
493 | hir::ExprTup(..) | hir::ExprBinary(..) | hir::ExprAddrOf(..) | | |
494 | hir::ExprCast(..) | hir::ExprUnary(..) | hir::ExprBreak(_) | | |
495 | hir::ExprAgain(_) | hir::ExprLit(_) | hir::ExprRet(..) | | |
496 | hir::ExprBlock(..) | hir::ExprAssign(..) | hir::ExprAssignOp(..) | | |
497 | hir::ExprStruct(..) | hir::ExprRepeat(..) | | |
b039eaaf | 498 | hir::ExprInlineAsm(..) | hir::ExprBox(..) | |
e9174d1e | 499 | hir::ExprRange(..) => { |
92a42be0 | 500 | intravisit::walk_expr(ir, expr); |
223e47cc LB |
501 | } |
502 | } | |
503 | } | |
504 | ||
505 | // ______________________________________________________________________ | |
506 | // Computing liveness sets | |
507 | // | |
508 | // Actually we compute just a bit more than just liveness, but we use | |
509 | // the same basic propagation framework in all cases. | |
510 | ||
1a4d82fc | 511 | #[derive(Clone, Copy)] |
223e47cc LB |
512 | struct Users { |
513 | reader: LiveNode, | |
514 | writer: LiveNode, | |
515 | used: bool | |
516 | } | |
517 | ||
518 | fn invalid_users() -> Users { | |
519 | Users { | |
520 | reader: invalid_node(), | |
521 | writer: invalid_node(), | |
522 | used: false | |
523 | } | |
524 | } | |
525 | ||
c34b1796 | 526 | #[derive(Copy, Clone)] |
223e47cc LB |
527 | struct Specials { |
528 | exit_ln: LiveNode, | |
529 | fallthrough_ln: LiveNode, | |
1a4d82fc JJ |
530 | no_ret_var: Variable, |
531 | clean_exit_var: Variable | |
223e47cc LB |
532 | } |
533 | ||
c34b1796 AL |
534 | const ACC_READ: u32 = 1; |
535 | const ACC_WRITE: u32 = 2; | |
536 | const ACC_USE: u32 = 4; | |
223e47cc | 537 | |
1a4d82fc JJ |
538 | struct Liveness<'a, 'tcx: 'a> { |
539 | ir: &'a mut IrMaps<'a, 'tcx>, | |
223e47cc | 540 | s: Specials, |
1a4d82fc JJ |
541 | successors: Vec<LiveNode>, |
542 | users: Vec<Users>, | |
223e47cc LB |
543 | // The list of node IDs for the nested loop scopes |
544 | // we're in. | |
1a4d82fc | 545 | loop_scope: Vec<NodeId>, |
223e47cc LB |
546 | // mappings from loop node ID to LiveNode |
547 | // ("break" label should map to loop node ID, | |
548 | // it probably doesn't now) | |
1a4d82fc JJ |
549 | break_ln: NodeMap<LiveNode>, |
550 | cont_ln: NodeMap<LiveNode> | |
223e47cc LB |
551 | } |
552 | ||
1a4d82fc JJ |
553 | impl<'a, 'tcx> Liveness<'a, 'tcx> { |
554 | fn new(ir: &'a mut IrMaps<'a, 'tcx>, specials: Specials) -> Liveness<'a, 'tcx> { | |
555 | let num_live_nodes = ir.num_live_nodes; | |
556 | let num_vars = ir.num_vars; | |
557 | Liveness { | |
558 | ir: ir, | |
559 | s: specials, | |
c1a9b12d SL |
560 | successors: vec![invalid_node(); num_live_nodes], |
561 | users: vec![invalid_users(); num_live_nodes * num_vars], | |
1a4d82fc | 562 | loop_scope: Vec::new(), |
85aaf69f SL |
563 | break_ln: NodeMap(), |
564 | cont_ln: NodeMap(), | |
1a4d82fc | 565 | } |
223e47cc | 566 | } |
223e47cc | 567 | |
1a4d82fc JJ |
568 | fn live_node(&self, node_id: NodeId, span: Span) -> LiveNode { |
569 | match self.ir.live_node_map.get(&node_id) { | |
223e47cc LB |
570 | Some(&ln) => ln, |
571 | None => { | |
572 | // This must be a mismatch between the ir_map construction | |
573 | // above and the propagation code below; the two sets of | |
574 | // code have to agree about which AST nodes are worth | |
575 | // creating liveness nodes for. | |
1a4d82fc JJ |
576 | self.ir.tcx.sess.span_bug( |
577 | span, | |
578 | &format!("no live node registered for node {}", | |
c34b1796 | 579 | node_id)); |
223e47cc | 580 | } |
223e47cc LB |
581 | } |
582 | } | |
583 | ||
1a4d82fc | 584 | fn variable(&self, node_id: NodeId, span: Span) -> Variable { |
223e47cc LB |
585 | self.ir.variable(node_id, span) |
586 | } | |
587 | ||
e9174d1e | 588 | fn pat_bindings<F>(&mut self, pat: &hir::Pat, mut f: F) where |
1a4d82fc JJ |
589 | F: FnMut(&mut Liveness<'a, 'tcx>, LiveNode, Variable, Span, NodeId), |
590 | { | |
591 | pat_util::pat_bindings(&self.ir.tcx.def_map, pat, |_bm, p_id, sp, _n| { | |
223e47cc LB |
592 | let ln = self.live_node(p_id, sp); |
593 | let var = self.variable(p_id, sp); | |
1a4d82fc JJ |
594 | f(self, ln, var, sp, p_id); |
595 | }) | |
223e47cc LB |
596 | } |
597 | ||
e9174d1e | 598 | fn arm_pats_bindings<F>(&mut self, pat: Option<&hir::Pat>, f: F) where |
1a4d82fc JJ |
599 | F: FnMut(&mut Liveness<'a, 'tcx>, LiveNode, Variable, Span, NodeId), |
600 | { | |
601 | match pat { | |
602 | Some(pat) => { | |
603 | self.pat_bindings(pat, f); | |
604 | } | |
605 | None => {} | |
223e47cc LB |
606 | } |
607 | } | |
608 | ||
e9174d1e | 609 | fn define_bindings_in_pat(&mut self, pat: &hir::Pat, succ: LiveNode) |
1a4d82fc JJ |
610 | -> LiveNode { |
611 | self.define_bindings_in_arm_pats(Some(pat), succ) | |
223e47cc LB |
612 | } |
613 | ||
e9174d1e | 614 | fn define_bindings_in_arm_pats(&mut self, pat: Option<&hir::Pat>, succ: LiveNode) |
1a4d82fc | 615 | -> LiveNode { |
223e47cc | 616 | let mut succ = succ; |
1a4d82fc JJ |
617 | self.arm_pats_bindings(pat, |this, ln, var, _sp, _id| { |
618 | this.init_from_succ(ln, succ); | |
619 | this.define(ln, var); | |
223e47cc | 620 | succ = ln; |
1a4d82fc | 621 | }); |
223e47cc LB |
622 | succ |
623 | } | |
624 | ||
c34b1796 | 625 | fn idx(&self, ln: LiveNode, var: Variable) -> usize { |
1a4d82fc | 626 | ln.get() * self.ir.num_vars + var.get() |
223e47cc LB |
627 | } |
628 | ||
1a4d82fc JJ |
629 | fn live_on_entry(&self, ln: LiveNode, var: Variable) |
630 | -> Option<LiveNodeKind> { | |
223e47cc LB |
631 | assert!(ln.is_valid()); |
632 | let reader = self.users[self.idx(ln, var)].reader; | |
633 | if reader.is_valid() {Some(self.ir.lnk(reader))} else {None} | |
634 | } | |
635 | ||
636 | /* | |
637 | Is this variable live on entry to any of its successor nodes? | |
638 | */ | |
1a4d82fc JJ |
639 | fn live_on_exit(&self, ln: LiveNode, var: Variable) |
640 | -> Option<LiveNodeKind> { | |
641 | let successor = self.successors[ln.get()]; | |
642 | self.live_on_entry(successor, var) | |
223e47cc LB |
643 | } |
644 | ||
1a4d82fc | 645 | fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool { |
223e47cc LB |
646 | assert!(ln.is_valid()); |
647 | self.users[self.idx(ln, var)].used | |
648 | } | |
649 | ||
1a4d82fc JJ |
650 | fn assigned_on_entry(&self, ln: LiveNode, var: Variable) |
651 | -> Option<LiveNodeKind> { | |
223e47cc LB |
652 | assert!(ln.is_valid()); |
653 | let writer = self.users[self.idx(ln, var)].writer; | |
654 | if writer.is_valid() {Some(self.ir.lnk(writer))} else {None} | |
655 | } | |
656 | ||
1a4d82fc JJ |
657 | fn assigned_on_exit(&self, ln: LiveNode, var: Variable) |
658 | -> Option<LiveNodeKind> { | |
659 | let successor = self.successors[ln.get()]; | |
660 | self.assigned_on_entry(successor, var) | |
223e47cc LB |
661 | } |
662 | ||
1a4d82fc | 663 | fn indices2<F>(&mut self, ln: LiveNode, succ_ln: LiveNode, mut op: F) where |
c34b1796 | 664 | F: FnMut(&mut Liveness<'a, 'tcx>, usize, usize), |
1a4d82fc | 665 | { |
85aaf69f SL |
666 | let node_base_idx = self.idx(ln, Variable(0)); |
667 | let succ_base_idx = self.idx(succ_ln, Variable(0)); | |
668 | for var_idx in 0..self.ir.num_vars { | |
1a4d82fc | 669 | op(self, node_base_idx + var_idx, succ_base_idx + var_idx); |
223e47cc LB |
670 | } |
671 | } | |
672 | ||
1a4d82fc | 673 | fn write_vars<F>(&self, |
c34b1796 | 674 | wr: &mut Write, |
1a4d82fc JJ |
675 | ln: LiveNode, |
676 | mut test: F) | |
c34b1796 AL |
677 | -> io::Result<()> where |
678 | F: FnMut(usize) -> LiveNode, | |
1a4d82fc | 679 | { |
223e47cc | 680 | let node_base_idx = self.idx(ln, Variable(0)); |
85aaf69f | 681 | for var_idx in 0..self.ir.num_vars { |
223e47cc LB |
682 | let idx = node_base_idx + var_idx; |
683 | if test(idx).is_valid() { | |
1a4d82fc | 684 | try!(write!(wr, " {:?}", Variable(var_idx))); |
223e47cc LB |
685 | } |
686 | } | |
1a4d82fc | 687 | Ok(()) |
223e47cc LB |
688 | } |
689 | ||
1a4d82fc | 690 | fn find_loop_scope(&self, |
b039eaaf | 691 | opt_label: Option<ast::Name>, |
1a4d82fc JJ |
692 | id: NodeId, |
693 | sp: Span) | |
694 | -> NodeId { | |
223e47cc | 695 | match opt_label { |
1a4d82fc JJ |
696 | Some(_) => { |
697 | // Refers to a labeled loop. Use the results of resolve | |
698 | // to find with one | |
c34b1796 AL |
699 | match self.ir.tcx.def_map.borrow().get(&id).map(|d| d.full_def()) { |
700 | Some(DefLabel(loop_id)) => loop_id, | |
1a4d82fc JJ |
701 | _ => self.ir.tcx.sess.span_bug(sp, "label on break/loop \ |
702 | doesn't refer to a loop") | |
703 | } | |
704 | } | |
223e47cc LB |
705 | None => { |
706 | // Vanilla 'break' or 'loop', so use the enclosing | |
707 | // loop scope | |
9346a6ac | 708 | if self.loop_scope.is_empty() { |
1a4d82fc | 709 | self.ir.tcx.sess.span_bug(sp, "break outside loop"); |
970d7e83 | 710 | } else { |
1a4d82fc | 711 | *self.loop_scope.last().unwrap() |
223e47cc LB |
712 | } |
713 | } | |
714 | } | |
715 | } | |
716 | ||
1a4d82fc JJ |
717 | #[allow(unused_must_use)] |
718 | fn ln_str(&self, ln: LiveNode) -> String { | |
719 | let mut wr = Vec::new(); | |
720 | { | |
c34b1796 | 721 | let wr = &mut wr as &mut Write; |
1a4d82fc JJ |
722 | write!(wr, "[ln({:?}) of kind {:?} reads", ln.get(), self.ir.lnk(ln)); |
723 | self.write_vars(wr, ln, |idx| self.users[idx].reader); | |
724 | write!(wr, " writes"); | |
725 | self.write_vars(wr, ln, |idx| self.users[idx].writer); | |
726 | write!(wr, " precedes {:?}]", self.successors[ln.get()]); | |
223e47cc | 727 | } |
1a4d82fc | 728 | String::from_utf8(wr).unwrap() |
223e47cc LB |
729 | } |
730 | ||
1a4d82fc JJ |
731 | fn init_empty(&mut self, ln: LiveNode, succ_ln: LiveNode) { |
732 | self.successors[ln.get()] = succ_ln; | |
223e47cc LB |
733 | |
734 | // It is not necessary to initialize the | |
735 | // values to empty because this is the value | |
736 | // they have when they are created, and the sets | |
737 | // only grow during iterations. | |
738 | // | |
739 | // self.indices(ln) { |idx| | |
740 | // self.users[idx] = invalid_users(); | |
741 | // } | |
742 | } | |
743 | ||
1a4d82fc | 744 | fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) { |
223e47cc | 745 | // more efficient version of init_empty() / merge_from_succ() |
1a4d82fc JJ |
746 | self.successors[ln.get()] = succ_ln; |
747 | ||
748 | self.indices2(ln, succ_ln, |this, idx, succ_idx| { | |
749 | this.users[idx] = this.users[succ_idx] | |
223e47cc | 750 | }); |
1a4d82fc | 751 | debug!("init_from_succ(ln={}, succ={})", |
223e47cc LB |
752 | self.ln_str(ln), self.ln_str(succ_ln)); |
753 | } | |
754 | ||
1a4d82fc JJ |
755 | fn merge_from_succ(&mut self, |
756 | ln: LiveNode, | |
757 | succ_ln: LiveNode, | |
758 | first_merge: bool) | |
759 | -> bool { | |
223e47cc LB |
760 | if ln == succ_ln { return false; } |
761 | ||
762 | let mut changed = false; | |
1a4d82fc JJ |
763 | self.indices2(ln, succ_ln, |this, idx, succ_idx| { |
764 | changed |= copy_if_invalid(this.users[succ_idx].reader, | |
765 | &mut this.users[idx].reader); | |
766 | changed |= copy_if_invalid(this.users[succ_idx].writer, | |
767 | &mut this.users[idx].writer); | |
768 | if this.users[succ_idx].used && !this.users[idx].used { | |
769 | this.users[idx].used = true; | |
223e47cc LB |
770 | changed = true; |
771 | } | |
1a4d82fc | 772 | }); |
223e47cc | 773 | |
1a4d82fc JJ |
774 | debug!("merge_from_succ(ln={:?}, succ={}, first_merge={}, changed={})", |
775 | ln, self.ln_str(succ_ln), first_merge, changed); | |
223e47cc LB |
776 | return changed; |
777 | ||
778 | fn copy_if_invalid(src: LiveNode, dst: &mut LiveNode) -> bool { | |
1a4d82fc JJ |
779 | if src.is_valid() && !dst.is_valid() { |
780 | *dst = src; | |
781 | true | |
782 | } else { | |
783 | false | |
223e47cc | 784 | } |
223e47cc LB |
785 | } |
786 | } | |
787 | ||
788 | // Indicates that a local variable was *defined*; we know that no | |
789 | // uses of the variable can precede the definition (resolve checks | |
790 | // this) so we just clear out all the data. | |
1a4d82fc | 791 | fn define(&mut self, writer: LiveNode, var: Variable) { |
223e47cc LB |
792 | let idx = self.idx(writer, var); |
793 | self.users[idx].reader = invalid_node(); | |
794 | self.users[idx].writer = invalid_node(); | |
795 | ||
1a4d82fc | 796 | debug!("{:?} defines {:?} (idx={}): {}", writer, var, |
223e47cc LB |
797 | idx, self.ln_str(writer)); |
798 | } | |
799 | ||
800 | // Either read, write, or both depending on the acc bitset | |
c34b1796 | 801 | fn acc(&mut self, ln: LiveNode, var: Variable, acc: u32) { |
1a4d82fc JJ |
802 | debug!("{:?} accesses[{:x}] {:?}: {}", |
803 | ln, acc, var, self.ln_str(ln)); | |
804 | ||
223e47cc | 805 | let idx = self.idx(ln, var); |
1a4d82fc | 806 | let user = &mut self.users[idx]; |
223e47cc LB |
807 | |
808 | if (acc & ACC_WRITE) != 0 { | |
809 | user.reader = invalid_node(); | |
810 | user.writer = ln; | |
811 | } | |
812 | ||
813 | // Important: if we both read/write, must do read second | |
814 | // or else the write will override. | |
815 | if (acc & ACC_READ) != 0 { | |
816 | user.reader = ln; | |
817 | } | |
818 | ||
819 | if (acc & ACC_USE) != 0 { | |
820 | user.used = true; | |
821 | } | |
223e47cc LB |
822 | } |
823 | ||
824 | // _______________________________________________________________________ | |
825 | ||
e9174d1e | 826 | fn compute(&mut self, decl: &hir::FnDecl, body: &hir::Block) -> LiveNode { |
223e47cc LB |
827 | // if there is a `break` or `again` at the top level, then it's |
828 | // effectively a return---this only occurs in `for` loops, | |
829 | // where the body is really a closure. | |
830 | ||
1a4d82fc | 831 | debug!("compute: using id for block, {}", block_to_string(body)); |
223e47cc | 832 | |
1a4d82fc | 833 | let exit_ln = self.s.exit_ln; |
223e47cc | 834 | let entry_ln: LiveNode = |
1a4d82fc JJ |
835 | self.with_loop_nodes(body.id, exit_ln, exit_ln, |
836 | |this| this.propagate_through_fn_block(decl, body)); | |
223e47cc LB |
837 | |
838 | // hack to skip the loop unless debug! is enabled: | |
1a4d82fc | 839 | debug!("^^ liveness computation results for body {} (entry={:?})", |
223e47cc | 840 | { |
85aaf69f | 841 | for ln_idx in 0..self.ir.num_live_nodes { |
1a4d82fc | 842 | debug!("{:?}", self.ln_str(LiveNode(ln_idx))); |
223e47cc | 843 | } |
1a4d82fc | 844 | body.id |
223e47cc | 845 | }, |
1a4d82fc | 846 | entry_ln); |
223e47cc LB |
847 | |
848 | entry_ln | |
849 | } | |
850 | ||
e9174d1e | 851 | fn propagate_through_fn_block(&mut self, _: &hir::FnDecl, blk: &hir::Block) |
1a4d82fc | 852 | -> LiveNode { |
223e47cc LB |
853 | // the fallthrough exit is only for those cases where we do not |
854 | // explicitly return: | |
1a4d82fc JJ |
855 | let s = self.s; |
856 | self.init_from_succ(s.fallthrough_ln, s.exit_ln); | |
857 | if blk.expr.is_none() { | |
858 | self.acc(s.fallthrough_ln, s.no_ret_var, ACC_READ) | |
223e47cc | 859 | } |
1a4d82fc | 860 | self.acc(s.fallthrough_ln, s.clean_exit_var, ACC_READ); |
223e47cc | 861 | |
1a4d82fc | 862 | self.propagate_through_block(blk, s.fallthrough_ln) |
223e47cc LB |
863 | } |
864 | ||
e9174d1e | 865 | fn propagate_through_block(&mut self, blk: &hir::Block, succ: LiveNode) |
1a4d82fc JJ |
866 | -> LiveNode { |
867 | let succ = self.propagate_through_opt_expr(blk.expr.as_ref().map(|e| &**e), succ); | |
868 | blk.stmts.iter().rev().fold(succ, |succ, stmt| { | |
92a42be0 | 869 | self.propagate_through_stmt(stmt, succ) |
1a4d82fc | 870 | }) |
223e47cc LB |
871 | } |
872 | ||
e9174d1e | 873 | fn propagate_through_stmt(&mut self, stmt: &hir::Stmt, succ: LiveNode) |
1a4d82fc | 874 | -> LiveNode { |
223e47cc | 875 | match stmt.node { |
e9174d1e | 876 | hir::StmtDecl(ref decl, _) => { |
1a4d82fc JJ |
877 | self.propagate_through_decl(&**decl, succ) |
878 | } | |
223e47cc | 879 | |
e9174d1e | 880 | hir::StmtExpr(ref expr, _) | hir::StmtSemi(ref expr, _) => { |
1a4d82fc JJ |
881 | self.propagate_through_expr(&**expr, succ) |
882 | } | |
223e47cc LB |
883 | } |
884 | } | |
885 | ||
e9174d1e | 886 | fn propagate_through_decl(&mut self, decl: &hir::Decl, succ: LiveNode) |
1a4d82fc | 887 | -> LiveNode { |
223e47cc | 888 | match decl.node { |
e9174d1e | 889 | hir::DeclLocal(ref local) => { |
1a4d82fc | 890 | self.propagate_through_local(&**local, succ) |
223e47cc | 891 | } |
e9174d1e | 892 | hir::DeclItem(_) => succ, |
223e47cc LB |
893 | } |
894 | } | |
895 | ||
e9174d1e | 896 | fn propagate_through_local(&mut self, local: &hir::Local, succ: LiveNode) |
1a4d82fc | 897 | -> LiveNode { |
223e47cc LB |
898 | // Note: we mark the variable as defined regardless of whether |
899 | // there is an initializer. Initially I had thought to only mark | |
900 | // the live variable as defined if it was initialized, and then we | |
901 | // could check for uninit variables just by scanning what is live | |
902 | // at the start of the function. But that doesn't work so well for | |
903 | // immutable variables defined in a loop: | |
904 | // loop { let x; x = 5; } | |
905 | // because the "assignment" loops back around and generates an error. | |
906 | // | |
907 | // So now we just check that variables defined w/o an | |
908 | // initializer are not live at the point of their | |
909 | // initialization, which is mildly more complex than checking | |
910 | // once at the func header but otherwise equivalent. | |
911 | ||
1a4d82fc JJ |
912 | let succ = self.propagate_through_opt_expr(local.init.as_ref().map(|e| &**e), succ); |
913 | self.define_bindings_in_pat(&*local.pat, succ) | |
223e47cc LB |
914 | } |
915 | ||
1a4d82fc JJ |
916 | fn propagate_through_exprs(&mut self, exprs: &[P<Expr>], succ: LiveNode) |
917 | -> LiveNode { | |
918 | exprs.iter().rev().fold(succ, |succ, expr| { | |
919 | self.propagate_through_expr(&**expr, succ) | |
920 | }) | |
223e47cc LB |
921 | } |
922 | ||
1a4d82fc JJ |
923 | fn propagate_through_opt_expr(&mut self, |
924 | opt_expr: Option<&Expr>, | |
925 | succ: LiveNode) | |
926 | -> LiveNode { | |
927 | opt_expr.map_or(succ, |expr| self.propagate_through_expr(expr, succ)) | |
223e47cc LB |
928 | } |
929 | ||
1a4d82fc JJ |
930 | fn propagate_through_expr(&mut self, expr: &Expr, succ: LiveNode) |
931 | -> LiveNode { | |
932 | debug!("propagate_through_expr: {}", expr_to_string(expr)); | |
223e47cc LB |
933 | |
934 | match expr.node { | |
935 | // Interesting cases with control flow or which gen/kill | |
936 | ||
e9174d1e | 937 | hir::ExprPath(..) => { |
223e47cc LB |
938 | self.access_path(expr, succ, ACC_READ | ACC_USE) |
939 | } | |
940 | ||
e9174d1e | 941 | hir::ExprField(ref e, _) => { |
1a4d82fc JJ |
942 | self.propagate_through_expr(&**e, succ) |
943 | } | |
944 | ||
e9174d1e | 945 | hir::ExprTupField(ref e, _) => { |
1a4d82fc | 946 | self.propagate_through_expr(&**e, succ) |
223e47cc LB |
947 | } |
948 | ||
e9174d1e | 949 | hir::ExprClosure(_, _, ref blk) => { |
1a4d82fc JJ |
950 | debug!("{} is an ExprClosure", |
951 | expr_to_string(expr)); | |
223e47cc LB |
952 | |
953 | /* | |
954 | The next-node for a break is the successor of the entire | |
955 | loop. The next-node for a continue is the top of this loop. | |
956 | */ | |
1a4d82fc JJ |
957 | let node = self.live_node(expr.id, expr.span); |
958 | self.with_loop_nodes(blk.id, succ, node, |this| { | |
223e47cc LB |
959 | |
960 | // the construction of a closure itself is not important, | |
961 | // but we have to consider the closed over variables. | |
1a4d82fc JJ |
962 | let caps = match this.ir.capture_info_map.get(&expr.id) { |
963 | Some(caps) => caps.clone(), | |
964 | None => { | |
965 | this.ir.tcx.sess.span_bug(expr.span, "no registered caps"); | |
966 | } | |
967 | }; | |
968 | caps.iter().rev().fold(succ, |succ, cap| { | |
969 | this.init_from_succ(cap.ln, succ); | |
970 | let var = this.variable(cap.var_nid, expr.span); | |
971 | this.acc(cap.ln, var, ACC_READ | ACC_USE); | |
223e47cc | 972 | cap.ln |
1a4d82fc | 973 | }) |
223e47cc LB |
974 | }) |
975 | } | |
976 | ||
e9174d1e | 977 | hir::ExprIf(ref cond, ref then, ref els) => { |
223e47cc LB |
978 | // |
979 | // (cond) | |
980 | // | | |
981 | // v | |
982 | // (expr) | |
983 | // / \ | |
984 | // | | | |
985 | // v v | |
986 | // (then)(els) | |
987 | // | | | |
988 | // v v | |
989 | // ( succ ) | |
990 | // | |
1a4d82fc JJ |
991 | let else_ln = self.propagate_through_opt_expr(els.as_ref().map(|e| &**e), succ); |
992 | let then_ln = self.propagate_through_block(&**then, succ); | |
223e47cc LB |
993 | let ln = self.live_node(expr.id, expr.span); |
994 | self.init_from_succ(ln, else_ln); | |
995 | self.merge_from_succ(ln, then_ln, false); | |
1a4d82fc JJ |
996 | self.propagate_through_expr(&**cond, ln) |
997 | } | |
998 | ||
e9174d1e | 999 | hir::ExprWhile(ref cond, ref blk, _) => { |
1a4d82fc JJ |
1000 | self.propagate_through_loop(expr, WhileLoop(&**cond), &**blk, succ) |
1001 | } | |
1002 | ||
223e47cc LB |
1003 | // Note that labels have been resolved, so we don't need to look |
1004 | // at the label ident | |
e9174d1e | 1005 | hir::ExprLoop(ref blk, _) => { |
1a4d82fc | 1006 | self.propagate_through_loop(expr, LoopLoop, &**blk, succ) |
223e47cc LB |
1007 | } |
1008 | ||
e9174d1e | 1009 | hir::ExprMatch(ref e, ref arms, _) => { |
223e47cc LB |
1010 | // |
1011 | // (e) | |
1012 | // | | |
1013 | // v | |
1014 | // (expr) | |
1015 | // / | \ | |
1016 | // | | | | |
1017 | // v v v | |
1018 | // (..arms..) | |
1019 | // | | | | |
1020 | // v v v | |
1021 | // ( succ ) | |
1022 | // | |
1023 | // | |
1024 | let ln = self.live_node(expr.id, expr.span); | |
1025 | self.init_empty(ln, succ); | |
1026 | let mut first_merge = true; | |
85aaf69f | 1027 | for arm in arms { |
223e47cc | 1028 | let body_succ = |
1a4d82fc | 1029 | self.propagate_through_expr(&*arm.body, succ); |
223e47cc | 1030 | let guard_succ = |
1a4d82fc JJ |
1031 | self.propagate_through_opt_expr(arm.guard.as_ref().map(|e| &**e), body_succ); |
1032 | // only consider the first pattern; any later patterns must have | |
1033 | // the same bindings, and we also consider the first pattern to be | |
1034 | // the "authoritative" set of ids | |
223e47cc | 1035 | let arm_succ = |
1a4d82fc JJ |
1036 | self.define_bindings_in_arm_pats(arm.pats.first().map(|p| &**p), |
1037 | guard_succ); | |
223e47cc LB |
1038 | self.merge_from_succ(ln, arm_succ, first_merge); |
1039 | first_merge = false; | |
1040 | }; | |
1a4d82fc | 1041 | self.propagate_through_expr(&**e, ln) |
223e47cc LB |
1042 | } |
1043 | ||
e9174d1e | 1044 | hir::ExprRet(ref o_e) => { |
223e47cc | 1045 | // ignore succ and subst exit_ln: |
1a4d82fc JJ |
1046 | let exit_ln = self.s.exit_ln; |
1047 | self.propagate_through_opt_expr(o_e.as_ref().map(|e| &**e), exit_ln) | |
223e47cc LB |
1048 | } |
1049 | ||
e9174d1e | 1050 | hir::ExprBreak(opt_label) => { |
223e47cc | 1051 | // Find which label this break jumps to |
b039eaaf | 1052 | let sc = self.find_loop_scope(opt_label.map(|l| l.node.name), expr.id, expr.span); |
223e47cc LB |
1053 | |
1054 | // Now that we know the label we're going to, | |
1055 | // look it up in the break loop nodes table | |
1056 | ||
1a4d82fc | 1057 | match self.break_ln.get(&sc) { |
223e47cc | 1058 | Some(&b) => b, |
1a4d82fc JJ |
1059 | None => self.ir.tcx.sess.span_bug(expr.span, |
1060 | "break to unknown label") | |
223e47cc LB |
1061 | } |
1062 | } | |
1063 | ||
e9174d1e | 1064 | hir::ExprAgain(opt_label) => { |
970d7e83 | 1065 | // Find which label this expr continues to |
b039eaaf | 1066 | let sc = self.find_loop_scope(opt_label.map(|l| l.node.name), expr.id, expr.span); |
223e47cc LB |
1067 | |
1068 | // Now that we know the label we're going to, | |
1069 | // look it up in the continue loop nodes table | |
1070 | ||
1a4d82fc | 1071 | match self.cont_ln.get(&sc) { |
223e47cc | 1072 | Some(&b) => b, |
1a4d82fc JJ |
1073 | None => self.ir.tcx.sess.span_bug(expr.span, |
1074 | "loop to unknown label") | |
223e47cc LB |
1075 | } |
1076 | } | |
1077 | ||
e9174d1e | 1078 | hir::ExprAssign(ref l, ref r) => { |
223e47cc LB |
1079 | // see comment on lvalues in |
1080 | // propagate_through_lvalue_components() | |
1a4d82fc JJ |
1081 | let succ = self.write_lvalue(&**l, succ, ACC_WRITE); |
1082 | let succ = self.propagate_through_lvalue_components(&**l, succ); | |
1083 | self.propagate_through_expr(&**r, succ) | |
223e47cc LB |
1084 | } |
1085 | ||
e9174d1e | 1086 | hir::ExprAssignOp(_, ref l, ref r) => { |
223e47cc LB |
1087 | // see comment on lvalues in |
1088 | // propagate_through_lvalue_components() | |
1a4d82fc JJ |
1089 | let succ = self.write_lvalue(&**l, succ, ACC_WRITE|ACC_READ); |
1090 | let succ = self.propagate_through_expr(&**r, succ); | |
1091 | self.propagate_through_lvalue_components(&**l, succ) | |
223e47cc LB |
1092 | } |
1093 | ||
1094 | // Uninteresting cases: just propagate in rev exec order | |
1095 | ||
e9174d1e | 1096 | hir::ExprVec(ref exprs) => { |
85aaf69f | 1097 | self.propagate_through_exprs(&exprs[..], succ) |
223e47cc LB |
1098 | } |
1099 | ||
e9174d1e | 1100 | hir::ExprRepeat(ref element, ref count) => { |
1a4d82fc JJ |
1101 | let succ = self.propagate_through_expr(&**count, succ); |
1102 | self.propagate_through_expr(&**element, succ) | |
223e47cc LB |
1103 | } |
1104 | ||
e9174d1e | 1105 | hir::ExprStruct(_, ref fields, ref with_expr) => { |
1a4d82fc JJ |
1106 | let succ = self.propagate_through_opt_expr(with_expr.as_ref().map(|e| &**e), succ); |
1107 | fields.iter().rev().fold(succ, |succ, field| { | |
1108 | self.propagate_through_expr(&*field.expr, succ) | |
1109 | }) | |
223e47cc LB |
1110 | } |
1111 | ||
e9174d1e | 1112 | hir::ExprCall(ref f, ref args) => { |
c1a9b12d SL |
1113 | let diverges = !self.ir.tcx.is_method_call(expr.id) && |
1114 | self.ir.tcx.expr_ty_adjusted(&**f).fn_ret().diverges(); | |
1a4d82fc JJ |
1115 | let succ = if diverges { |
1116 | self.s.exit_ln | |
1117 | } else { | |
1118 | succ | |
1119 | }; | |
85aaf69f | 1120 | let succ = self.propagate_through_exprs(&args[..], succ); |
1a4d82fc | 1121 | self.propagate_through_expr(&**f, succ) |
223e47cc LB |
1122 | } |
1123 | ||
e9174d1e | 1124 | hir::ExprMethodCall(_, _, ref args) => { |
1a4d82fc | 1125 | let method_call = ty::MethodCall::expr(expr.id); |
c1a9b12d SL |
1126 | let method_ty = self.ir.tcx.tables.borrow().method_map[&method_call].ty; |
1127 | let succ = if method_ty.fn_ret().diverges() { | |
1a4d82fc JJ |
1128 | self.s.exit_ln |
1129 | } else { | |
1130 | succ | |
1131 | }; | |
85aaf69f | 1132 | self.propagate_through_exprs(&args[..], succ) |
223e47cc LB |
1133 | } |
1134 | ||
e9174d1e | 1135 | hir::ExprTup(ref exprs) => { |
85aaf69f | 1136 | self.propagate_through_exprs(&exprs[..], succ) |
223e47cc LB |
1137 | } |
1138 | ||
e9174d1e | 1139 | hir::ExprBinary(op, ref l, ref r) if ::rustc_front::util::lazy_binop(op.node) => { |
1a4d82fc | 1140 | let r_succ = self.propagate_through_expr(&**r, succ); |
223e47cc LB |
1141 | |
1142 | let ln = self.live_node(expr.id, expr.span); | |
1143 | self.init_from_succ(ln, succ); | |
1144 | self.merge_from_succ(ln, r_succ, false); | |
1145 | ||
1a4d82fc | 1146 | self.propagate_through_expr(&**l, ln) |
223e47cc LB |
1147 | } |
1148 | ||
e9174d1e | 1149 | hir::ExprIndex(ref l, ref r) | |
b039eaaf | 1150 | hir::ExprBinary(_, ref l, ref r) => { |
1a4d82fc JJ |
1151 | let r_succ = self.propagate_through_expr(&**r, succ); |
1152 | self.propagate_through_expr(&**l, r_succ) | |
223e47cc LB |
1153 | } |
1154 | ||
e9174d1e | 1155 | hir::ExprRange(ref e1, ref e2) => { |
1a4d82fc JJ |
1156 | let succ = e2.as_ref().map_or(succ, |e| self.propagate_through_expr(&**e, succ)); |
1157 | e1.as_ref().map_or(succ, |e| self.propagate_through_expr(&**e, succ)) | |
223e47cc LB |
1158 | } |
1159 | ||
b039eaaf | 1160 | hir::ExprBox(ref e) | |
e9174d1e SL |
1161 | hir::ExprAddrOf(_, ref e) | |
1162 | hir::ExprCast(ref e, _) | | |
b039eaaf | 1163 | hir::ExprUnary(_, ref e) => { |
1a4d82fc JJ |
1164 | self.propagate_through_expr(&**e, succ) |
1165 | } | |
1166 | ||
e9174d1e | 1167 | hir::ExprInlineAsm(ref ia) => { |
1a4d82fc JJ |
1168 | |
1169 | let succ = ia.outputs.iter().rev().fold(succ, |succ, &(_, ref expr, _)| { | |
1170 | // see comment on lvalues | |
1171 | // in propagate_through_lvalue_components() | |
1172 | let succ = self.write_lvalue(&**expr, succ, ACC_WRITE); | |
1173 | self.propagate_through_lvalue_components(&**expr, succ) | |
1174 | }); | |
1175 | // Inputs are executed first. Propagate last because of rev order | |
1176 | ia.inputs.iter().rev().fold(succ, |succ, &(_, ref expr)| { | |
1177 | self.propagate_through_expr(&**expr, succ) | |
1178 | }) | |
223e47cc LB |
1179 | } |
1180 | ||
e9174d1e | 1181 | hir::ExprLit(..) => { |
223e47cc LB |
1182 | succ |
1183 | } | |
1184 | ||
e9174d1e | 1185 | hir::ExprBlock(ref blk) => { |
1a4d82fc | 1186 | self.propagate_through_block(&**blk, succ) |
223e47cc | 1187 | } |
223e47cc LB |
1188 | } |
1189 | } | |
1190 | ||
1a4d82fc JJ |
1191 | fn propagate_through_lvalue_components(&mut self, |
1192 | expr: &Expr, | |
1193 | succ: LiveNode) | |
1194 | -> LiveNode { | |
223e47cc LB |
1195 | // # Lvalues |
1196 | // | |
1197 | // In general, the full flow graph structure for an | |
1198 | // assignment/move/etc can be handled in one of two ways, | |
1199 | // depending on whether what is being assigned is a "tracked | |
1200 | // value" or not. A tracked value is basically a local | |
1201 | // variable or argument. | |
1202 | // | |
1203 | // The two kinds of graphs are: | |
1204 | // | |
1205 | // Tracked lvalue Untracked lvalue | |
1206 | // ----------------------++----------------------- | |
1207 | // || | |
1208 | // | || | | |
1209 | // v || v | |
1210 | // (rvalue) || (rvalue) | |
1211 | // | || | | |
1212 | // v || v | |
1213 | // (write of lvalue) || (lvalue components) | |
1214 | // | || | | |
1215 | // v || v | |
1216 | // (succ) || (succ) | |
1217 | // || | |
1218 | // ----------------------++----------------------- | |
1219 | // | |
1220 | // I will cover the two cases in turn: | |
1221 | // | |
1222 | // # Tracked lvalues | |
1223 | // | |
1224 | // A tracked lvalue is a local variable/argument `x`. In | |
1225 | // these cases, the link_node where the write occurs is linked | |
1226 | // to node id of `x`. The `write_lvalue()` routine generates | |
1227 | // the contents of this node. There are no subcomponents to | |
1228 | // consider. | |
1229 | // | |
1230 | // # Non-tracked lvalues | |
1231 | // | |
1232 | // These are lvalues like `x[5]` or `x.f`. In that case, we | |
1233 | // basically ignore the value which is written to but generate | |
1234 | // reads for the components---`x` in these two examples. The | |
1235 | // components reads are generated by | |
1236 | // `propagate_through_lvalue_components()` (this fn). | |
1237 | // | |
1238 | // # Illegal lvalues | |
1239 | // | |
1240 | // It is still possible to observe assignments to non-lvalues; | |
1241 | // these errors are detected in the later pass borrowck. We | |
1242 | // just ignore such cases and treat them as reads. | |
1243 | ||
1244 | match expr.node { | |
e9174d1e SL |
1245 | hir::ExprPath(..) => succ, |
1246 | hir::ExprField(ref e, _) => self.propagate_through_expr(&**e, succ), | |
1247 | hir::ExprTupField(ref e, _) => self.propagate_through_expr(&**e, succ), | |
223e47cc LB |
1248 | _ => self.propagate_through_expr(expr, succ) |
1249 | } | |
1250 | } | |
1251 | ||
1252 | // see comment on propagate_through_lvalue() | |
c34b1796 | 1253 | fn write_lvalue(&mut self, expr: &Expr, succ: LiveNode, acc: u32) |
1a4d82fc | 1254 | -> LiveNode { |
223e47cc | 1255 | match expr.node { |
e9174d1e | 1256 | hir::ExprPath(..) => { |
85aaf69f SL |
1257 | self.access_path(expr, succ, acc) |
1258 | } | |
223e47cc LB |
1259 | |
1260 | // We do not track other lvalues, so just propagate through | |
1261 | // to their subcomponents. Also, it may happen that | |
1262 | // non-lvalues occur here, because those are detected in the | |
1263 | // later pass borrowck. | |
1264 | _ => succ | |
1265 | } | |
1266 | } | |
1267 | ||
c34b1796 | 1268 | fn access_path(&mut self, expr: &Expr, succ: LiveNode, acc: u32) |
1a4d82fc | 1269 | -> LiveNode { |
c34b1796 | 1270 | match self.ir.tcx.def_map.borrow().get(&expr.id).unwrap().full_def() { |
b039eaaf | 1271 | DefLocal(_, nid) => { |
223e47cc | 1272 | let ln = self.live_node(expr.id, expr.span); |
85aaf69f | 1273 | if acc != 0 { |
223e47cc LB |
1274 | self.init_from_succ(ln, succ); |
1275 | let var = self.variable(nid, expr.span); | |
1276 | self.acc(ln, var, acc); | |
1277 | } | |
1278 | ln | |
1279 | } | |
1a4d82fc | 1280 | _ => succ |
223e47cc LB |
1281 | } |
1282 | } | |
1283 | ||
1a4d82fc JJ |
1284 | fn propagate_through_loop(&mut self, |
1285 | expr: &Expr, | |
1286 | kind: LoopKind, | |
e9174d1e | 1287 | body: &hir::Block, |
1a4d82fc JJ |
1288 | succ: LiveNode) |
1289 | -> LiveNode { | |
223e47cc LB |
1290 | |
1291 | /* | |
1292 | ||
1293 | We model control flow like this: | |
1294 | ||
1295 | (cond) <--+ | |
1296 | | | | |
1297 | v | | |
1298 | +-- (expr) | | |
1299 | | | | | |
1300 | | v | | |
1301 | | (body) ---+ | |
1302 | | | |
1303 | | | |
1304 | v | |
1305 | (succ) | |
1306 | ||
1307 | */ | |
1308 | ||
1309 | ||
1310 | // first iteration: | |
1311 | let mut first_merge = true; | |
1312 | let ln = self.live_node(expr.id, expr.span); | |
1313 | self.init_empty(ln, succ); | |
1a4d82fc JJ |
1314 | match kind { |
1315 | LoopLoop => {} | |
1316 | _ => { | |
1317 | // If this is not a `loop` loop, then it's possible we bypass | |
1318 | // the body altogether. Otherwise, the only way is via a `break` | |
1319 | // in the loop body. | |
1320 | self.merge_from_succ(ln, succ, first_merge); | |
1321 | first_merge = false; | |
1322 | } | |
223e47cc | 1323 | } |
1a4d82fc JJ |
1324 | debug!("propagate_through_loop: using id for loop body {} {}", |
1325 | expr.id, block_to_string(body)); | |
223e47cc | 1326 | |
1a4d82fc JJ |
1327 | let cond_ln = match kind { |
1328 | LoopLoop => ln, | |
1a4d82fc JJ |
1329 | WhileLoop(ref cond) => self.propagate_through_expr(&**cond, ln), |
1330 | }; | |
1331 | let body_ln = self.with_loop_nodes(expr.id, succ, ln, |this| { | |
1332 | this.propagate_through_block(body, cond_ln) | |
223e47cc LB |
1333 | }); |
1334 | ||
1335 | // repeat until fixed point is reached: | |
1336 | while self.merge_from_succ(ln, body_ln, first_merge) { | |
1337 | first_merge = false; | |
1a4d82fc JJ |
1338 | |
1339 | let new_cond_ln = match kind { | |
1340 | LoopLoop => ln, | |
1a4d82fc JJ |
1341 | WhileLoop(ref cond) => { |
1342 | self.propagate_through_expr(&**cond, ln) | |
1343 | } | |
1344 | }; | |
1345 | assert!(cond_ln == new_cond_ln); | |
223e47cc | 1346 | assert!(body_ln == self.with_loop_nodes(expr.id, succ, ln, |
1a4d82fc | 1347 | |this| this.propagate_through_block(body, cond_ln))); |
223e47cc LB |
1348 | } |
1349 | ||
1350 | cond_ln | |
1351 | } | |
1352 | ||
1a4d82fc JJ |
1353 | fn with_loop_nodes<R, F>(&mut self, |
1354 | loop_node_id: NodeId, | |
1355 | break_ln: LiveNode, | |
1356 | cont_ln: LiveNode, | |
1357 | f: F) | |
1358 | -> R where | |
1359 | F: FnOnce(&mut Liveness<'a, 'tcx>) -> R, | |
1360 | { | |
1361 | debug!("with_loop_nodes: {} {}", loop_node_id, break_ln.get()); | |
223e47cc LB |
1362 | self.loop_scope.push(loop_node_id); |
1363 | self.break_ln.insert(loop_node_id, break_ln); | |
1364 | self.cont_ln.insert(loop_node_id, cont_ln); | |
1a4d82fc | 1365 | let r = f(self); |
223e47cc LB |
1366 | self.loop_scope.pop(); |
1367 | r | |
1368 | } | |
1369 | } | |
1370 | ||
1371 | // _______________________________________________________________________ | |
1372 | // Checking for error conditions | |
1373 | ||
e9174d1e | 1374 | fn check_local(this: &mut Liveness, local: &hir::Local) { |
1a4d82fc JJ |
1375 | match local.init { |
1376 | Some(_) => { | |
1377 | this.warn_about_unused_or_dead_vars_in_pat(&*local.pat); | |
1378 | }, | |
1379 | None => { | |
1380 | this.pat_bindings(&*local.pat, |this, ln, var, sp, id| { | |
1381 | this.warn_about_unused(sp, id, ln, var); | |
1382 | }) | |
223e47cc | 1383 | } |
223e47cc LB |
1384 | } |
1385 | ||
92a42be0 | 1386 | intravisit::walk_local(this, local); |
223e47cc LB |
1387 | } |
1388 | ||
e9174d1e | 1389 | fn check_arm(this: &mut Liveness, arm: &hir::Arm) { |
1a4d82fc JJ |
1390 | // only consider the first pattern; any later patterns must have |
1391 | // the same bindings, and we also consider the first pattern to be | |
1392 | // the "authoritative" set of ids | |
1393 | this.arm_pats_bindings(arm.pats.first().map(|p| &**p), |this, ln, var, sp, id| { | |
970d7e83 | 1394 | this.warn_about_unused(sp, id, ln, var); |
1a4d82fc | 1395 | }); |
92a42be0 | 1396 | intravisit::walk_arm(this, arm); |
223e47cc LB |
1397 | } |
1398 | ||
1a4d82fc | 1399 | fn check_expr(this: &mut Liveness, expr: &Expr) { |
223e47cc | 1400 | match expr.node { |
b039eaaf | 1401 | hir::ExprAssign(ref l, _) => { |
1a4d82fc | 1402 | this.check_lvalue(&**l); |
223e47cc | 1403 | |
92a42be0 | 1404 | intravisit::walk_expr(this, expr); |
223e47cc LB |
1405 | } |
1406 | ||
e9174d1e | 1407 | hir::ExprAssignOp(_, ref l, _) => { |
1a4d82fc | 1408 | this.check_lvalue(&**l); |
223e47cc | 1409 | |
92a42be0 | 1410 | intravisit::walk_expr(this, expr); |
223e47cc LB |
1411 | } |
1412 | ||
e9174d1e | 1413 | hir::ExprInlineAsm(ref ia) => { |
85aaf69f | 1414 | for &(_, ref input) in &ia.inputs { |
1a4d82fc | 1415 | this.visit_expr(&**input); |
223e47cc LB |
1416 | } |
1417 | ||
1418 | // Output operands must be lvalues | |
85aaf69f | 1419 | for &(_, ref out, _) in &ia.outputs { |
1a4d82fc JJ |
1420 | this.check_lvalue(&**out); |
1421 | this.visit_expr(&**out); | |
223e47cc LB |
1422 | } |
1423 | ||
92a42be0 | 1424 | intravisit::walk_expr(this, expr); |
1a4d82fc JJ |
1425 | } |
1426 | ||
223e47cc | 1427 | // no correctness conditions related to liveness |
e9174d1e SL |
1428 | hir::ExprCall(..) | hir::ExprMethodCall(..) | hir::ExprIf(..) | |
1429 | hir::ExprMatch(..) | hir::ExprWhile(..) | hir::ExprLoop(..) | | |
1430 | hir::ExprIndex(..) | hir::ExprField(..) | hir::ExprTupField(..) | | |
1431 | hir::ExprVec(..) | hir::ExprTup(..) | hir::ExprBinary(..) | | |
1432 | hir::ExprCast(..) | hir::ExprUnary(..) | hir::ExprRet(..) | | |
1433 | hir::ExprBreak(..) | hir::ExprAgain(..) | hir::ExprLit(_) | | |
1434 | hir::ExprBlock(..) | hir::ExprAddrOf(..) | | |
b039eaaf | 1435 | hir::ExprStruct(..) | hir::ExprRepeat(..) | |
e9174d1e SL |
1436 | hir::ExprClosure(..) | hir::ExprPath(..) | hir::ExprBox(..) | |
1437 | hir::ExprRange(..) => { | |
92a42be0 | 1438 | intravisit::walk_expr(this, expr); |
1a4d82fc | 1439 | } |
223e47cc LB |
1440 | } |
1441 | } | |
1442 | ||
1a4d82fc JJ |
1443 | fn check_fn(_v: &Liveness, |
1444 | _fk: FnKind, | |
e9174d1e SL |
1445 | _decl: &hir::FnDecl, |
1446 | _body: &hir::Block, | |
1a4d82fc JJ |
1447 | _sp: Span, |
1448 | _id: NodeId) { | |
223e47cc LB |
1449 | // do not check contents of nested fns |
1450 | } | |
1451 | ||
1a4d82fc JJ |
1452 | impl<'a, 'tcx> Liveness<'a, 'tcx> { |
1453 | fn fn_ret(&self, id: NodeId) -> ty::PolyFnOutput<'tcx> { | |
c1a9b12d | 1454 | let fn_ty = self.ir.tcx.node_id_to_type(id); |
1a4d82fc | 1455 | match fn_ty.sty { |
c1a9b12d | 1456 | ty::TyClosure(closure_def_id, ref substs) => |
85aaf69f | 1457 | self.ir.tcx.closure_type(closure_def_id, substs).sig.output(), |
c1a9b12d | 1458 | _ => fn_ty.fn_ret() |
1a4d82fc JJ |
1459 | } |
1460 | } | |
223e47cc | 1461 | |
1a4d82fc JJ |
1462 | fn check_ret(&self, |
1463 | id: NodeId, | |
1464 | sp: Span, | |
1465 | _fk: FnKind, | |
1466 | entry_ln: LiveNode, | |
e9174d1e | 1467 | body: &hir::Block) |
1a4d82fc JJ |
1468 | { |
1469 | // within the fn body, late-bound regions are liberated: | |
1470 | let fn_ret = | |
c1a9b12d | 1471 | self.ir.tcx.liberate_late_bound_regions( |
e9174d1e | 1472 | self.ir.tcx.region_maps.item_extent(body.id), |
1a4d82fc JJ |
1473 | &self.fn_ret(id)); |
1474 | ||
1475 | match fn_ret { | |
1476 | ty::FnConverging(t_ret) | |
1477 | if self.live_on_entry(entry_ln, self.s.no_ret_var).is_some() => { | |
1478 | ||
c1a9b12d | 1479 | if t_ret.is_nil() { |
1a4d82fc JJ |
1480 | // for nil return types, it is ok to not return a value expl. |
1481 | } else { | |
1482 | let ends_with_stmt = match body.expr { | |
9346a6ac | 1483 | None if !body.stmts.is_empty() => |
1a4d82fc | 1484 | match body.stmts.first().unwrap().node { |
e9174d1e | 1485 | hir::StmtSemi(ref e, _) => { |
c1a9b12d | 1486 | self.ir.tcx.expr_ty(&**e) == t_ret |
1a4d82fc JJ |
1487 | }, |
1488 | _ => false | |
1489 | }, | |
1490 | _ => false | |
1491 | }; | |
85aaf69f | 1492 | span_err!(self.ir.tcx.sess, sp, E0269, "not all control paths return a value"); |
1a4d82fc JJ |
1493 | if ends_with_stmt { |
1494 | let last_stmt = body.stmts.first().unwrap(); | |
1495 | let original_span = original_sp(self.ir.tcx.sess.codemap(), | |
1496 | last_stmt.span, sp); | |
1497 | let span_semicolon = Span { | |
1498 | lo: original_span.hi - BytePos(1), | |
1499 | hi: original_span.hi, | |
1500 | expn_id: original_span.expn_id | |
1501 | }; | |
1502 | self.ir.tcx.sess.span_help( | |
1503 | span_semicolon, "consider removing this semicolon:"); | |
1504 | } | |
1505 | } | |
223e47cc | 1506 | } |
1a4d82fc JJ |
1507 | ty::FnDiverging |
1508 | if self.live_on_entry(entry_ln, self.s.clean_exit_var).is_some() => { | |
85aaf69f | 1509 | span_err!(self.ir.tcx.sess, sp, E0270, |
1a4d82fc JJ |
1510 | "computation may converge in a function marked as diverging"); |
1511 | } | |
1512 | ||
1513 | _ => {} | |
223e47cc LB |
1514 | } |
1515 | } | |
1516 | ||
1a4d82fc | 1517 | fn check_lvalue(&mut self, expr: &Expr) { |
223e47cc | 1518 | match expr.node { |
e9174d1e | 1519 | hir::ExprPath(..) => { |
b039eaaf SL |
1520 | if let DefLocal(_, nid) = self.ir.tcx.def_map.borrow().get(&expr.id) |
1521 | .unwrap() | |
1522 | .full_def() { | |
1a4d82fc JJ |
1523 | // Assignment to an immutable variable or argument: only legal |
1524 | // if there is no later assignment. If this local is actually | |
1525 | // mutable, then check for a reassignment to flag the mutability | |
1526 | // as being used. | |
223e47cc LB |
1527 | let ln = self.live_node(expr.id, expr.span); |
1528 | let var = self.variable(nid, expr.span); | |
970d7e83 | 1529 | self.warn_about_dead_assign(expr.span, expr.id, ln, var); |
223e47cc | 1530 | } |
223e47cc | 1531 | } |
1a4d82fc JJ |
1532 | _ => { |
1533 | // For other kinds of lvalues, no checks are required, | |
1534 | // and any embedded expressions are actually rvalues | |
92a42be0 | 1535 | intravisit::walk_expr(self, expr); |
1a4d82fc | 1536 | } |
223e47cc LB |
1537 | } |
1538 | } | |
1539 | ||
1a4d82fc | 1540 | fn should_warn(&self, var: Variable) -> Option<String> { |
223e47cc | 1541 | let name = self.ir.variable_name(var); |
9346a6ac | 1542 | if name.is_empty() || name.as_bytes()[0] == ('_' as u8) { |
1a4d82fc JJ |
1543 | None |
1544 | } else { | |
1545 | Some(name) | |
1546 | } | |
223e47cc LB |
1547 | } |
1548 | ||
e9174d1e | 1549 | fn warn_about_unused_args(&self, decl: &hir::FnDecl, entry_ln: LiveNode) { |
85aaf69f | 1550 | for arg in &decl.inputs { |
1a4d82fc JJ |
1551 | pat_util::pat_bindings(&self.ir.tcx.def_map, |
1552 | &*arg.pat, | |
1553 | |_bm, p_id, sp, path1| { | |
223e47cc | 1554 | let var = self.variable(p_id, sp); |
1a4d82fc | 1555 | // Ignore unused self. |
b039eaaf SL |
1556 | let name = path1.node; |
1557 | if name != special_idents::self_.name { | |
92a42be0 SL |
1558 | if !self.warn_about_unused(sp, p_id, entry_ln, var) { |
1559 | if self.live_on_entry(entry_ln, var).is_none() { | |
1560 | self.report_dead_assign(p_id, sp, var, true); | |
1561 | } | |
1562 | } | |
1a4d82fc JJ |
1563 | } |
1564 | }) | |
223e47cc LB |
1565 | } |
1566 | } | |
1567 | ||
e9174d1e | 1568 | fn warn_about_unused_or_dead_vars_in_pat(&mut self, pat: &hir::Pat) { |
1a4d82fc JJ |
1569 | self.pat_bindings(pat, |this, ln, var, sp, id| { |
1570 | if !this.warn_about_unused(sp, id, ln, var) { | |
1571 | this.warn_about_dead_assign(sp, id, ln, var); | |
223e47cc | 1572 | } |
1a4d82fc | 1573 | }) |
223e47cc LB |
1574 | } |
1575 | ||
1a4d82fc JJ |
1576 | fn warn_about_unused(&self, |
1577 | sp: Span, | |
1578 | id: NodeId, | |
1579 | ln: LiveNode, | |
1580 | var: Variable) | |
1581 | -> bool { | |
223e47cc | 1582 | if !self.used_on_entry(ln, var) { |
970d7e83 | 1583 | let r = self.should_warn(var); |
85aaf69f | 1584 | if let Some(name) = r { |
223e47cc | 1585 | |
92a42be0 | 1586 | // annoying: for parameters in funcs like `fn(x: i32) |
223e47cc LB |
1587 | // {ret}`, there is only one node, so asking about |
1588 | // assigned_on_exit() is not meaningful. | |
1589 | let is_assigned = if ln == self.s.exit_ln { | |
1590 | false | |
1591 | } else { | |
1592 | self.assigned_on_exit(ln, var).is_some() | |
1593 | }; | |
1594 | ||
1595 | if is_assigned { | |
1a4d82fc JJ |
1596 | self.ir.tcx.sess.add_lint(lint::builtin::UNUSED_VARIABLES, id, sp, |
1597 | format!("variable `{}` is assigned to, but never used", | |
85aaf69f | 1598 | name)); |
92a42be0 | 1599 | } else if name != "self" { |
1a4d82fc | 1600 | self.ir.tcx.sess.add_lint(lint::builtin::UNUSED_VARIABLES, id, sp, |
85aaf69f | 1601 | format!("unused variable: `{}`", name)); |
223e47cc LB |
1602 | } |
1603 | } | |
970d7e83 LB |
1604 | true |
1605 | } else { | |
1606 | false | |
223e47cc | 1607 | } |
223e47cc LB |
1608 | } |
1609 | ||
1a4d82fc JJ |
1610 | fn warn_about_dead_assign(&self, |
1611 | sp: Span, | |
1612 | id: NodeId, | |
1613 | ln: LiveNode, | |
1614 | var: Variable) { | |
223e47cc | 1615 | if self.live_on_exit(ln, var).is_none() { |
92a42be0 SL |
1616 | self.report_dead_assign(id, sp, var, false); |
1617 | } | |
1618 | } | |
1619 | ||
1620 | fn report_dead_assign(&self, id: NodeId, sp: Span, var: Variable, is_argument: bool) { | |
1621 | if let Some(name) = self.should_warn(var) { | |
1622 | if is_argument { | |
1623 | self.ir.tcx.sess.add_lint(lint::builtin::UNUSED_ASSIGNMENTS, id, sp, | |
1624 | format!("value passed to `{}` is never read", name)); | |
1625 | } else { | |
1a4d82fc | 1626 | self.ir.tcx.sess.add_lint(lint::builtin::UNUSED_ASSIGNMENTS, id, sp, |
85aaf69f | 1627 | format!("value assigned to `{}` is never read", name)); |
223e47cc LB |
1628 | } |
1629 | } | |
1630 | } | |
92a42be0 | 1631 | } |