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_call(f, args, _) {
 140         v.visit_expr(f, cx, v);
 141         let i = 0u, fns = [];
 142         let arg_ts = ty::ty_fn_args(cx.tcx, ty::expr_ty(cx.tcx, f));
 143         for arg in args {
 144             alt arg.node {
 145               expr_fn(proto_block., _, _, _) { fns += [arg]; }
 146               expr_fn_block(_, _) when is_block(cx, arg.id) { fns += [arg]; }
 147               _ {
 148                 alt arg_ts[i].mode {
 149                   by_mut_ref. { clear_if_path(cx, arg, v, false); }
 150                   _ { v.visit_expr(arg, cx, v); }
 151                 }
 152               }
 153             }
 154             i += 1u;
 155         }
 156         for f in fns { v.visit_expr(f, cx, v); }
 157       }
 158       _ { visit::visit_expr(ex, cx, v); }
 159     }
 160 }
 161
 162 fn visit_fn(fk: visit::fn_kind, decl: fn_decl, body: blk,
 163             sp: span, id: node_id,
 164             cx: ctx, v: visit::vt<ctx>) {
 165     let fty = ty::node_id_to_type(cx.tcx, id);
 166     let proto = ty::ty_fn_proto(cx.tcx, fty);
 167     if proto == proto_block {
 168         visit_block(func, cx, {||
 169             visit::visit_fn(fk, decl, body, sp, id, cx, v);
 170         });
 171     } else {
 172         alt cx.tcx.freevars.find(id) {
 173           some(vars) {
 174             for v in *vars {
 175                 clear_in_current(cx, ast_util::def_id_of_def(v.def).node,
 176                                  false);
 177             }
 178           }
 179           _ {}
 180         }
 181         let old = nil;
 182         cx.blocks <-> old;
 183         visit::visit_fn(fk, decl, body, sp, id, cx, v);
 184         cx.blocks <-> old;
 185         leave_fn(cx);
 186     }
 187 }
 188
 189 fn visit_block(tp: block_type, cx: ctx, visit: block()) {
 190     let local = @{type: tp, mutable second: false, mutable exits: []};
 191     cx.blocks = cons(local, @cx.blocks);
 192     visit();
 193     local.second = true;
 194     visit();
 195     let cx_blocks = cx.blocks;
 196     check is_not_empty(cx_blocks);
 197     cx.blocks = tail(cx_blocks);
 198     cx.current = join_branches(local.exits);
 199 }
 200
 201 fn add_block_exit(cx: ctx, tp: block_type) -> bool {
 202     let cur = cx.blocks;
 203     while cur != nil {
 204         alt cur {
 205           cons(b, tail) {
 206             if (b.type == tp) {
 207                 if !b.second { b.exits += [cx.current]; }
 208                 ret true;
 209             }
 210             cur = *tail;
 211           }
 212         }
 213     }
 214     ret false;
 215 }
 216
 217 fn join_branches(branches: [set]) -> set {
 218     let found: set = [], i = 0u, l = vec::len(branches);
 219     for set in branches {
 220         i += 1u;
 221         for {def, exprs} in set {
 222             if !vec::any(found, {|v| v.def == def}) {
 223                 let j = i, nne = exprs;
 224                 while j < l {
 225                     for {def: d2, exprs} in branches[j] {
 226                         if d2 == def {
 227                             list::iter(exprs) {|e|
 228                                 if !list::has(nne, e) { nne = cons(e, @nne); }
 229                             }
 230                         }
 231                     }
 232                     j += 1u;
 233                 }
 234                 found += [{def: def, exprs: nne}];
 235             }
 236         }
 237     }
 238     ret found;
 239 }
 240
 241 fn leave_fn(cx: ctx) {
 242     for {def, exprs} in cx.current {
 243         list::iter(exprs) {|ex_id|
 244             if !cx.last_uses.contains_key(ex_id) {
 245                 cx.last_uses.insert(ex_id, true);
 246             }
 247         }
 248     }
 249 }
 250
 251 fn clear_in_current(cx: ctx, my_def: node_id, to: bool) {
 252     for {def, exprs} in cx.current {
 253         if def == my_def {
 254             list::iter(exprs) {|expr|
 255                 if !to || !cx.last_uses.contains_key(expr) {
 256                      cx.last_uses.insert(expr, to);
 257                 }
 258             }
 259             cx.current = vec::filter(copy cx.current,
 260                                      {|x| x.def != my_def});
 261             break;
 262         }
 263     }
 264 }
 265
 266 fn clear_if_path(cx: ctx, ex: @expr, v: visit::vt<ctx>, to: bool)
 267     -> option::t<node_id> {
 268     alt ex.node {
 269       expr_path(_) {
 270         alt cx.def_map.get(ex.id) {
 271           def_local(def_id, let_copy.) | def_arg(def_id, by_copy.) |
 272           def_arg(def_id, by_move.) {
 273             clear_in_current(cx, def_id.node, to);
 274             ret option::some(def_id.node);
 275           }
 276           _ {}
 277         }
 278       }
 279       _ { v.visit_expr(ex, cx, v); }
 280     }
 281     ret option::none;
 282 }