src/rustc/middle/trans/type_use.rs

   1 // Determines the ways in which a generic function body depends
   2 // on its type parameters. Used to aggressively reuse compiled
   3 // function bodies for different types.
   4
   5 // This unfortunately depends on quite a bit of knowledge about the
   6 // details of the language semantics, and is likely to accidentally go
   7 // out of sync when something is changed. It could be made more
   8 // powerful by distinguishing between functions that only need to know
   9 // the size and alignment of a type, and those that also use its
  10 // drop/take glue. But this would increase the fragility of the code
  11 // to a ridiculous level, and probably not catch all that many extra
  12 // opportunities for reuse.
  13
  14 // (An other approach to doing what this code does is to instrument
  15 // the translation code to set flags whenever it does something like
  16 // alloca a type or get a tydesc. This would not duplicate quite as
  17 // much information, but have the disadvantage of being very
  18 // invasive.)
  19
  20 use std::map::HashMap;
  21 use std::list;
  22 use std::list::{List, Cons, Nil};
  23 use metadata::csearch;
  24 use syntax::ast::*, syntax::ast_util, syntax::visit;
  25 use syntax::ast_map;
  26 use common::*;
  27
  28 type type_uses = uint; // Bitmask
  29 const use_repr: uint = 1u;   /* Dependency on size/alignment/mode and
  30                                 take/drop glue */
  31 const use_tydesc: uint = 2u; /* Takes the tydesc, or compares */
  32
  33 type ctx = {ccx: @crate_ctxt,
  34             uses: ~[mut type_uses]};
  35
  36 fn type_uses_for(ccx: @crate_ctxt, fn_id: def_id, n_tps: uint)
  37     -> ~[type_uses] {
  38     match ccx.type_use_cache.find(fn_id) {
  39       Some(uses) => return uses,
  40       None => ()
  41     }
  42
  43     let fn_id_loc = if fn_id.crate == local_crate {
  44         fn_id
  45     } else {
  46         inline::maybe_instantiate_inline(ccx, fn_id, true)
  47     };
  48
  49     // Conservatively assume full use for recursive loops
  50     ccx.type_use_cache.insert(fn_id, vec::from_elem(n_tps, 3u));
  51
  52     let cx = {ccx: ccx, uses: vec::to_mut(vec::from_elem(n_tps, 0u))};
  53     match ty::get(ty::lookup_item_type(cx.ccx.tcx, fn_id).ty).sty {
  54         ty::ty_fn(ref fn_ty) => {
  55             for vec::each(fn_ty.sig.inputs) |arg| {
  56                 match ty::resolved_mode(ccx.tcx, arg.mode) {
  57                     by_val | by_move | by_copy => {
  58                         type_needs(cx, use_repr, arg.ty);
  59                     }
  60                     by_ref => {}
  61                 }
  62             }
  63         }
  64         _ => ()
  65     }
  66
  67     if fn_id_loc.crate != local_crate {
  68         let uses = vec::from_mut(copy cx.uses);
  69         ccx.type_use_cache.insert(fn_id, uses);
  70         return uses;
  71     }
  72     let map_node = match ccx.tcx.items.find(fn_id_loc.node) {
  73         Some(x) => x,
  74         None    => ccx.sess.bug(fmt!("type_uses_for: unbound item ID %?",
  75                                      fn_id_loc))
  76     };
  77     match map_node {
  78       ast_map::node_item(@{node: item_fn(_, _, _, body), _}, _) |
  79       ast_map::node_method(@{body, _}, _, _) => {
  80         handle_body(cx, body);
  81       }
  82       ast_map::node_trait_method(*) => {
  83         // This will be a static trait method. For now, we just assume
  84         // it fully depends on all of the type information. (Doing
  85         // otherwise would require finding the actual implementation).
  86         for uint::range(0u, n_tps) |n| { cx.uses[n] |= use_repr|use_tydesc;}
  87       }
  88       ast_map::node_variant(_, _, _) => {
  89         for uint::range(0u, n_tps) |n| { cx.uses[n] |= use_repr;}
  90       }
  91       ast_map::node_foreign_item(i@@{node: foreign_item_fn(*), _},
  92                                  abi, _) => {
  93         if abi == foreign_abi_rust_intrinsic {
  94             let flags = match cx.ccx.sess.str_of(i.ident) {
  95                 ~"size_of"  | ~"pref_align_of"    | ~"min_align_of" |
  96                 ~"init"     | ~"reinterpret_cast" |
  97                 ~"move_val" | ~"move_val_init" => use_repr,
  98
  99                 ~"get_tydesc" | ~"needs_drop" => use_tydesc,
 100
 101                 ~"atomic_cxchg"    | ~"atomic_cxchg_acq"|
 102                 ~"atomic_cxchg_rel"| ~"atomic_xchg"     |
 103                 ~"atomic_xadd"     | ~"atomic_xsub"     |
 104                 ~"atomic_xchg_acq" | ~"atomic_xadd_acq" |
 105                 ~"atomic_xsub_acq" | ~"atomic_xchg_rel" |
 106                 ~"atomic_xadd_rel" | ~"atomic_xsub_rel" => 0,
 107
 108                 ~"visit_tydesc"  | ~"forget" | ~"addr_of" |
 109                 ~"frame_address" | ~"morestack_addr" => 0,
 110
 111                 // would be cool to make these an enum instead of strings!
 112                 _ => fail ~"unknown intrinsic in type_use"
 113             };
 114             for uint::range(0u, n_tps) |n| { cx.uses[n] |= flags;}
 115         }
 116       }
 117       ast_map::node_dtor(_, dtor, _, _) => {
 118         handle_body(cx, dtor.node.body);
 119       }
 120       _ => fail ~"unknown node type in type_use"
 121     }
 122     let uses = vec::from_mut(copy cx.uses);
 123     ccx.type_use_cache.insert(fn_id, uses);
 124     uses
 125 }
 126
 127 fn type_needs(cx: ctx, use_: uint, ty: ty::t) {
 128     // Optimization -- don't descend type if all params already have this use
 129     for vec::each_mut(cx.uses) |u| {
 130         if *u & use_ != use_ {
 131             type_needs_inner(cx, use_, ty, @Nil);
 132             return;
 133         }
 134     }
 135 }
 136
 137 fn type_needs_inner(cx: ctx, use_: uint, ty: ty::t,
 138                     enums_seen: @List<def_id>) {
 139     do ty::maybe_walk_ty(ty) |ty| {
 140         if ty::type_has_params(ty) {
 141             match ty::get(ty).sty {
 142                 /*
 143                  This previously included ty_box -- that was wrong
 144                  because if we cast an @T to an trait (for example) and return
 145                  it, we depend on the drop glue for T (we have to write the
 146                  right tydesc into the result)
 147                  */
 148               ty::ty_fn(_) | ty::ty_ptr(_) | ty::ty_rptr(_, _)
 149                | ty::ty_trait(_, _, _) => false,
 150               ty::ty_enum(did, substs) => {
 151                 if option::is_none(&list::find(enums_seen, |id| *id == did)) {
 152                     let seen = @Cons(did, enums_seen);
 153                     for vec::each(*ty::enum_variants(cx.ccx.tcx, did)) |v| {
 154                         for vec::each(v.args) |aty| {
 155                             let t = ty::subst(cx.ccx.tcx, &substs, *aty);
 156                             type_needs_inner(cx, use_, t, seen);
 157                         }
 158                     }
 159                 }
 160                 false
 161               }
 162               ty::ty_param(p) => {
 163                 cx.uses[p.idx] |= use_;
 164                 false
 165               }
 166               _ => true
 167             }
 168         } else { false }
 169     }
 170 }
 171
 172 fn node_type_needs(cx: ctx, use_: uint, id: node_id) {
 173     type_needs(cx, use_, ty::node_id_to_type(cx.ccx.tcx, id));
 174 }
 175
 176 fn mark_for_expr(cx: ctx, e: @expr) {
 177     match e.node {
 178       expr_vstore(_, _) |
 179       expr_vec(_, _) |
 180       expr_rec(_, _) | expr_struct(*) | expr_tup(_) |
 181       expr_unary(box(_), _) | expr_unary(uniq(_), _) |
 182       expr_binary(add, _, _) |
 183       expr_copy(_) | expr_move(_, _) | expr_unary_move(_) |
 184       expr_repeat(*) => {
 185         node_type_needs(cx, use_repr, e.id);
 186       }
 187       expr_cast(base, _) => {
 188         let result_t = ty::node_id_to_type(cx.ccx.tcx, e.id);
 189         match ty::get(result_t).sty {
 190             ty::ty_trait(*) => {
 191               // When we're casting to an trait, we need the
 192               // tydesc for the expr that's being cast.
 193               node_type_needs(cx, use_tydesc, base.id);
 194             }
 195             _ => ()
 196         }
 197       }
 198       expr_binary(op, lhs, _) => {
 199         match op {
 200           eq | lt | le | ne | ge | gt => {
 201             node_type_needs(cx, use_tydesc, lhs.id)
 202           }
 203           _ => ()
 204         }
 205       }
 206       expr_path(_) => {
 207         do cx.ccx.tcx.node_type_substs.find(e.id).iter |ts| {
 208             let id = ast_util::def_id_of_def(cx.ccx.tcx.def_map.get(e.id));
 209             let uses_for_ts = type_uses_for(cx.ccx, id, ts.len());
 210             for vec::each2(uses_for_ts, *ts) |uses, subst| {
 211                 type_needs(cx, *uses, *subst)
 212             }
 213         }
 214       }
 215       expr_fn(*) | expr_fn_block(*) => {
 216         match ty::ty_fn_proto(ty::expr_ty(cx.ccx.tcx, e)) {
 217           ty::proto_bare | ty::proto_vstore(ty::vstore_uniq) => {}
 218           ty::proto_vstore(ty::vstore_box) |
 219           ty::proto_vstore(ty::vstore_slice(_)) => {
 220             for vec::each(*freevars::get_freevars(cx.ccx.tcx, e.id)) |fv| {
 221                 let node_id = ast_util::def_id_of_def(fv.def).node;
 222                 node_type_needs(cx, use_repr, node_id);
 223             }
 224           }
 225           ty::proto_vstore(ty::vstore_fixed(_)) =>
 226             fail ~"vstore_fixed not allowed here"
 227         }
 228       }
 229       expr_assign(val, _) | expr_swap(val, _) | expr_assign_op(_, val, _) |
 230       expr_ret(Some(val)) => {
 231         node_type_needs(cx, use_repr, val.id);
 232       }
 233       expr_index(base, _) | expr_field(base, _, _) => {
 234         // FIXME (#2537): could be more careful and not count fields after
 235         // the chosen field.
 236         let base_ty = ty::node_id_to_type(cx.ccx.tcx, base.id);
 237         type_needs(cx, use_repr, ty::type_autoderef(cx.ccx.tcx, base_ty));
 238
 239         do option::iter(&cx.ccx.maps.method_map.find(e.id)) |mth| {
 240             match mth.origin {
 241               typeck::method_static(did) => {
 242                 do cx.ccx.tcx.node_type_substs.find(e.id).iter |ts| {
 243                     let type_uses = type_uses_for(cx.ccx, did, ts.len());
 244                     for vec::each2(type_uses, *ts) |uses, subst| {
 245                         type_needs(cx, *uses, *subst)
 246                     }
 247                 }
 248               }
 249               typeck::method_param({param_num: param, _}) => {
 250                 cx.uses[param] |= use_tydesc;
 251               }
 252               typeck::method_trait(*) | typeck::method_self(*) => (),
 253             }
 254         }
 255       }
 256       expr_log(_, _, val) => {
 257         node_type_needs(cx, use_tydesc, val.id);
 258       }
 259       expr_call(f, _, _) => {
 260           for vec::each(
 261               ty::ty_fn_args(ty::node_id_to_type(cx.ccx.tcx, f.id))
 262           ) |a| {
 263               match a.mode {
 264                   expl(by_move) | expl(by_copy) | expl(by_val) => {
 265                       type_needs(cx, use_repr, a.ty);
 266                   }
 267                   _ => ()
 268               }
 269           }
 270       }
 271       expr_match(*) | expr_block(_) | expr_if(*) |
 272       expr_while(*) | expr_fail(_) | expr_break(_) | expr_again(_) |
 273       expr_unary(_, _) | expr_lit(_) | expr_assert(_) |
 274       expr_mac(_) | expr_addr_of(_, _) |
 275       expr_ret(_) | expr_loop(_, _) |
 276       expr_loop_body(_) | expr_do_body(_) => ()
 277     }
 278 }
 279
 280 fn handle_body(cx: ctx, body: blk) {
 281     let v = visit::mk_vt(@{
 282         visit_expr: |e, cx, v| {
 283             visit::visit_expr(e, cx, v);
 284             mark_for_expr(cx, e);
 285         },
 286         visit_local: |l, cx, v| {
 287             visit::visit_local(l, cx, v);
 288             node_type_needs(cx, use_repr, l.node.id);
 289         },
 290         visit_pat: |p, cx, v| {
 291             visit::visit_pat(p, cx, v);
 292             node_type_needs(cx, use_repr, p.id);
 293         },
 294         visit_block: |b, cx, v| {
 295             visit::visit_block(b, cx, v);
 296             do option::iter(&b.node.expr) |e| {
 297                 node_type_needs(cx, use_repr, e.id);
 298             }
 299         },
 300         visit_item: |_i, _cx, _v| { },
 301         ..*visit::default_visitor()
 302     });
 303     v.visit_block(body, cx, v);
 304 }