src/comp/middle/last_use.rs

   1 import syntax::{visit, ast_util};
   2 import syntax::ast::*;
   3 import syntax::codemap::span;
   4 import std::list::{is_not_empty, list, nil, cons, tail};
   5 import core::{vec, option};
   6 import std::list;
   7
   8 // Last use analysis pass.
   9 //
  10 // Finds the last read of each value stored in a local variable or
  11 // callee-owned argument (arguments with by-move or by-copy passing
  12 // style). This is a limited form of liveness analysis, peformed
  13 // (perhaps foolishly) directly on the AST.
  14 //
  15 // The algorithm walks the AST, keeping a set of (def, last_use)
  16 // pairs. When the function is exited, or the local is overwritten,
  17 // the current set of last uses is marked with 'true' in a table.
  18 // Other branches may later overwrite them with 'false' again, since
  19 // they may find a use coming after them. (Marking an expression as a
  20 // last use is only done if it has not already been marked with
  21 // 'false'.)
  22 //
  23 // Some complexity is added to deal with joining control flow branches
  24 // (by `break` or conditionals), and for handling loops.
  25
  26 // Marks expr_paths that are last uses.
  27 type last_uses = std::map::hashmap<node_id, ()>;
  28
  29 tag seen { unset; seen(node_id); }
  30 tag block_type { func; loop; }
  31
  32 type set = [{def: node_id, exprs: list<node_id>}];
  33 type bl = @{type: block_type, mutable second: bool, mutable exits: [set]};
  34
  35 type ctx = {last_uses: std::map::hashmap<node_id, bool>,
  36             def_map: resolve::def_map,
  37             ref_map: alias::ref_map,
  38             tcx: ty::ctxt,
  39             // The current set of local last uses
  40             mutable current: set,
  41             mutable blocks: list<bl>};
  42
  43 fn find_last_uses(c: @crate, def_map: resolve::def_map,
  44                   ref_map: alias::ref_map, tcx: ty::ctxt) -> last_uses {
  45     let v = visit::mk_vt(@{visit_expr: visit_expr,
  46                            visit_fn: visit_fn
  47                            with *visit::default_visitor()});
  48     let cx = {last_uses: std::map::new_int_hash(),
  49               def_map: def_map,
  50               ref_map: ref_map,
  51               tcx: tcx,
  52               mutable current: [],
  53               mutable blocks: nil};
  54     visit::visit_crate(*c, cx, v);
  55     let mini_table = std::map::new_int_hash();
  56     cx.last_uses.items {|key, val|
  57         if val {
  58             mini_table.insert(key, ());
  59             let def_node = ast_util::def_id_of_def(def_map.get(key)).node;
  60             mini_table.insert(def_node, ());
  61         }
  62     }
  63     ret mini_table;
  64 }
  65
  66 fn is_block(cx: ctx, id: node_id) -> bool {
  67     alt ty::struct(cx.tcx, ty::node_id_to_monotype(cx.tcx, id)) {
  68       ty::ty_fn({proto: proto_block., _}) { true }
  69       _ { false }
  70     }
  71 }
  72
  73 fn visit_expr(ex: @expr, cx: ctx, v: visit::vt<ctx>) {
  74     alt ex.node {
  75       expr_ret(oexpr) {
  76         visit::visit_expr_opt(oexpr, cx, v);
  77         if !add_block_exit(cx, func) { leave_fn(cx); }
  78       }
  79       expr_fail(oexpr) {
  80         visit::visit_expr_opt(oexpr, cx, v);
  81         leave_fn(cx);
  82       }
  83       expr_break. { add_block_exit(cx, loop); }
  84       expr_while(_, _) | expr_do_while(_, _) {
  85         visit_block(loop, cx) {|| visit::visit_expr(ex, cx, v);}
  86       }
  87       expr_for(_, coll, blk) {
  88         v.visit_expr(coll, cx, v);
  89         visit_block(loop, cx) {|| visit::visit_block(blk, cx, v);}
  90       }
  91       expr_ternary(_, _, _) {
  92         v.visit_expr(ast_util::ternary_to_if(ex), cx, v);
  93       }
  94       expr_alt(input, arms) {
  95         v.visit_expr(input, cx, v);
  96         let before = cx.current, sets = [];
  97         for arm in arms {
  98             cx.current = before;
  99             v.visit_arm(arm, cx, v);
 100             sets += [cx.current];
 101         }
 102         cx.current = join_branches(sets);
 103       }
 104       expr_if(cond, then, els) {
 105         v.visit_expr(cond, cx, v);
 106         let cur = cx.current;
 107         visit::visit_block(then, cx, v);
 108         cx.current <-> cur;
 109         visit::visit_expr_opt(els, cx, v);
 110         cx.current = join_branches([cur, cx.current]);
 111       }
 112       expr_path(_) {
 113         let my_def = ast_util::def_id_of_def(cx.def_map.get(ex.id)).node;
 114         alt cx.ref_map.find(my_def) {
 115           option::some(root_id) { clear_in_current(cx, root_id, false); }
 116           _ {
 117             alt clear_if_path(cx, ex, v, false) {
 118               option::some(my_def) {
 119                 cx.current += [{def: my_def, exprs: cons(ex.id, @nil)}];
 120               }
 121               _ {}
 122             }
 123           }
 124         }
 125       }
 126       expr_swap(lhs, rhs) {
 127         clear_if_path(cx, lhs, v, false);
 128         clear_if_path(cx, rhs, v, false);
 129       }
 130       expr_move(dest, src) | expr_assign(dest, src) {
 131         v.visit_expr(src, cx, v);
 132         clear_if_path(cx, dest, v, true);
 133       }
 134       expr_assign_op(_, dest, src) {
 135         v.visit_expr(src, cx, v);
 136         v.visit_expr(dest, cx, v);
 137         clear_if_path(cx, dest, v, true);
 138       }
 139       expr_fn(_, _, _, cap_clause) {
 140         // n.b.: safe to ignore copies, as if they are unused
 141         // then they are ignored, otherwise they will show up
 142         // as freevars in the body.
 143
 144         vec::iter(cap_clause.moves) {|ci|
 145             clear_def_if_path(cx, cx.def_map.get(ci.id), true);
 146         }
 147         visit::visit_expr(ex, cx, v);
 148       }
 149       expr_call(f, args, _) {
 150         v.visit_expr(f, cx, v);
 151         let i = 0u, fns = [];
 152         let arg_ts = ty::ty_fn_args(cx.tcx, ty::expr_ty(cx.tcx, f));
 153         for arg in args {
 154             alt arg.node {
 155               expr_fn(proto_block., _, _, _) { fns += [arg]; }
 156               expr_fn_block(_, _) when is_block(cx, arg.id) { fns += [arg]; }
 157               _ {
 158                 alt arg_ts[i].mode {
 159                   by_mut_ref. { clear_if_path(cx, arg, v, false); }
 160                   _ { v.visit_expr(arg, cx, v); }
 161                 }
 162               }
 163             }
 164             i += 1u;
 165         }
 166         for f in fns { v.visit_expr(f, cx, v); }
 167       }
 168       _ { visit::visit_expr(ex, cx, v); }
 169     }
 170 }
 171
 172 fn visit_fn(fk: visit::fn_kind, decl: fn_decl, body: blk,
 173             sp: span, id: node_id,
 174             cx: ctx, v: visit::vt<ctx>) {
 175     let fty = ty::node_id_to_type(cx.tcx, id);
 176     let proto = ty::ty_fn_proto(cx.tcx, fty);
 177     if proto == proto_block {
 178         visit_block(func, cx, {||
 179             visit::visit_fn(fk, decl, body, sp, id, cx, v);
 180         });
 181     } else {
 182         alt cx.tcx.freevars.find(id) {
 183           some(vars) {
 184             for v in *vars {
 185                 clear_in_current(cx, ast_util::def_id_of_def(v.def).node,
 186                                  false);
 187             }
 188           }
 189           _ {}
 190         }
 191         let old = nil;
 192         cx.blocks <-> old;
 193         visit::visit_fn(fk, decl, body, sp, id, cx, v);
 194         cx.blocks <-> old;
 195         leave_fn(cx);
 196     }
 197 }
 198
 199 fn visit_block(tp: block_type, cx: ctx, visit: block()) {
 200     let local = @{type: tp, mutable second: false, mutable exits: []};
 201     cx.blocks = cons(local, @cx.blocks);
 202     visit();
 203     local.second = true;
 204     visit();
 205     let cx_blocks = cx.blocks;
 206     check is_not_empty(cx_blocks);
 207     cx.blocks = tail(cx_blocks);
 208     cx.current = join_branches(local.exits);
 209 }
 210
 211 fn add_block_exit(cx: ctx, tp: block_type) -> bool {
 212     let cur = cx.blocks;
 213     while cur != nil {
 214         alt cur {
 215           cons(b, tail) {
 216             if (b.type == tp) {
 217                 if !b.second { b.exits += [cx.current]; }
 218                 ret true;
 219             }
 220             cur = *tail;
 221           }
 222         }
 223     }
 224     ret false;
 225 }
 226
 227 fn join_branches(branches: [set]) -> set {
 228     let found: set = [], i = 0u, l = vec::len(branches);
 229     for set in branches {
 230         i += 1u;
 231         for {def, exprs} in set {
 232             if !vec::any(found, {|v| v.def == def}) {
 233                 let j = i, nne = exprs;
 234                 while j < l {
 235                     for {def: d2, exprs} in branches[j] {
 236                         if d2 == def {
 237                             list::iter(exprs) {|e|
 238                                 if !list::has(nne, e) { nne = cons(e, @nne); }
 239                             }
 240                         }
 241                     }
 242                     j += 1u;
 243                 }
 244                 found += [{def: def, exprs: nne}];
 245             }
 246         }
 247     }
 248     ret found;
 249 }
 250
 251 fn leave_fn(cx: ctx) {
 252     for {def, exprs} in cx.current {
 253         list::iter(exprs) {|ex_id|
 254             if !cx.last_uses.contains_key(ex_id) {
 255                 cx.last_uses.insert(ex_id, true);
 256             }
 257         }
 258     }
 259 }
 260
 261 fn clear_in_current(cx: ctx, my_def: node_id, to: bool) {
 262     for {def, exprs} in cx.current {
 263         if def == my_def {
 264             list::iter(exprs) {|expr|
 265                 if !to || !cx.last_uses.contains_key(expr) {
 266                      cx.last_uses.insert(expr, to);
 267                 }
 268             }
 269             cx.current = vec::filter(copy cx.current,
 270                                      {|x| x.def != my_def});
 271             break;
 272         }
 273     }
 274 }
 275
 276 fn clear_def_if_path(cx: ctx, d: def, to: bool)
 277     -> option<node_id> {
 278     alt d {
 279       def_local(def_id, let_copy.) | def_arg(def_id, by_copy.) |
 280       def_arg(def_id, by_move.) {
 281         clear_in_current(cx, def_id.node, to);
 282         some(def_id.node)
 283       }
 284       _ {
 285         none
 286       }
 287     }
 288 }
 289
 290 fn clear_if_path(cx: ctx, ex: @expr, v: visit::vt<ctx>, to: bool)
 291     -> option::t<node_id> {
 292     alt ex.node {
 293       expr_path(_) {
 294         ret clear_def_if_path(cx, cx.def_map.get(ex.id), to);
 295       }
 296       _ { v.visit_expr(ex, cx, v); }
 297     }
 298     ret option::none;
 299 }