src/librustc/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                 ~"sqrtf32" | ~"sqrtf64" | ~"powif32" | ~"powif64" |
 112                 ~"sinf32"  | ~"sinf64"  | ~"cosf32"  | ~"cosf64"  |
 113                 ~"powf32"  | ~"powf64"  | ~"expf32"  | ~"expf64"  |
 114                 ~"exp2f32" | ~"exp2f64" | ~"logf32"  | ~"logf64"  |
 115                 ~"log10f32"| ~"log10f64"| ~"log2f32" | ~"log2f64" |
 116                 ~"fmaf32"  | ~"fmaf64"  | ~"fabsf32" | ~"fabsf64" |
 117                 ~"floorf32"| ~"floorf64"| ~"ceilf32" | ~"ceilf64" |
 118                 ~"truncf32"| ~"truncf64" => 0,
 119
 120                 // would be cool to make these an enum instead of strings!
 121                 _ => fail ~"unknown intrinsic in type_use"
 122             };
 123             for uint::range(0u, n_tps) |n| { cx.uses[n] |= flags;}
 124         }
 125       }
 126       ast_map::node_dtor(_, dtor, _, _) => {
 127         handle_body(cx, dtor.node.body);
 128       }
 129       _ => fail ~"unknown node type in type_use"
 130     }
 131     let uses = vec::from_mut(copy cx.uses);
 132     ccx.type_use_cache.insert(fn_id, uses);
 133     uses
 134 }
 135
 136 fn type_needs(cx: ctx, use_: uint, ty: ty::t) {
 137     // Optimization -- don't descend type if all params already have this use
 138     for vec::each_mut(cx.uses) |u| {
 139         if *u & use_ != use_ {
 140             type_needs_inner(cx, use_, ty, @Nil);
 141             return;
 142         }
 143     }
 144 }
 145
 146 fn type_needs_inner(cx: ctx, use_: uint, ty: ty::t,
 147                     enums_seen: @List<def_id>) {
 148     do ty::maybe_walk_ty(ty) |ty| {
 149         if ty::type_has_params(ty) {
 150             match ty::get(ty).sty {
 151                 /*
 152                  This previously included ty_box -- that was wrong
 153                  because if we cast an @T to an trait (for example) and return
 154                  it, we depend on the drop glue for T (we have to write the
 155                  right tydesc into the result)
 156                  */
 157               ty::ty_fn(_) | ty::ty_ptr(_) | ty::ty_rptr(_, _)
 158                | ty::ty_trait(_, _, _) => false,
 159               ty::ty_enum(did, substs) => {
 160                 if option::is_none(&list::find(enums_seen, |id| *id == did)) {
 161                     let seen = @Cons(did, enums_seen);
 162                     for vec::each(*ty::enum_variants(cx.ccx.tcx, did)) |v| {
 163                         for vec::each(v.args) |aty| {
 164                             let t = ty::subst(cx.ccx.tcx, &substs, *aty);
 165                             type_needs_inner(cx, use_, t, seen);
 166                         }
 167                     }
 168                 }
 169                 false
 170               }
 171               ty::ty_param(p) => {
 172                 cx.uses[p.idx] |= use_;
 173                 false
 174               }
 175               _ => true
 176             }
 177         } else { false }
 178     }
 179 }
 180
 181 fn node_type_needs(cx: ctx, use_: uint, id: node_id) {
 182     type_needs(cx, use_, ty::node_id_to_type(cx.ccx.tcx, id));
 183 }
 184
 185 fn mark_for_expr(cx: ctx, e: @expr) {
 186     match e.node {
 187       expr_vstore(_, _) |
 188       expr_vec(_, _) |
 189       expr_rec(_, _) | expr_struct(*) | expr_tup(_) |
 190       expr_unary(box(_), _) | expr_unary(uniq(_), _) |
 191       expr_binary(add, _, _) |
 192       expr_copy(_) | expr_unary_move(_) | expr_repeat(*) => {
 193         node_type_needs(cx, use_repr, e.id);
 194       }
 195       expr_cast(base, _) => {
 196         let result_t = ty::node_id_to_type(cx.ccx.tcx, e.id);
 197         match ty::get(result_t).sty {
 198             ty::ty_trait(*) => {
 199               // When we're casting to an trait, we need the
 200               // tydesc for the expr that's being cast.
 201               node_type_needs(cx, use_tydesc, base.id);
 202             }
 203             _ => ()
 204         }
 205       }
 206       expr_binary(op, lhs, _) => {
 207         match op {
 208           eq | lt | le | ne | ge | gt => {
 209             node_type_needs(cx, use_tydesc, lhs.id)
 210           }
 211           _ => ()
 212         }
 213       }
 214       expr_path(_) => {
 215         do cx.ccx.tcx.node_type_substs.find(e.id).iter |ts| {
 216             let id = ast_util::def_id_of_def(cx.ccx.tcx.def_map.get(e.id));
 217             let uses_for_ts = type_uses_for(cx.ccx, id, ts.len());
 218             for vec::each2(uses_for_ts, *ts) |uses, subst| {
 219                 type_needs(cx, *uses, *subst)
 220             }
 221         }
 222       }
 223       expr_fn(*) | expr_fn_block(*) => {
 224         match ty::ty_fn_proto(ty::expr_ty(cx.ccx.tcx, e)) {
 225           ast::ProtoBare | ast::ProtoUniq => {}
 226           ast::ProtoBox | ast::ProtoBorrowed => {
 227             for vec::each(*freevars::get_freevars(cx.ccx.tcx, e.id)) |fv| {
 228                 let node_id = ast_util::def_id_of_def(fv.def).node;
 229                 node_type_needs(cx, use_repr, node_id);
 230             }
 231           }
 232         }
 233       }
 234       expr_assign(val, _) | expr_swap(val, _) | expr_assign_op(_, val, _) |
 235       expr_ret(Some(val)) => {
 236         node_type_needs(cx, use_repr, val.id);
 237       }
 238       expr_index(base, _) | expr_field(base, _, _) => {
 239         // FIXME (#2537): could be more careful and not count fields after
 240         // the chosen field.
 241         let base_ty = ty::node_id_to_type(cx.ccx.tcx, base.id);
 242         type_needs(cx, use_repr, ty::type_autoderef(cx.ccx.tcx, base_ty));
 243
 244         do option::iter(&cx.ccx.maps.method_map.find(e.id)) |mth| {
 245             match mth.origin {
 246               typeck::method_static(did) => {
 247                 do cx.ccx.tcx.node_type_substs.find(e.id).iter |ts| {
 248                     let type_uses = type_uses_for(cx.ccx, did, ts.len());
 249                     for vec::each2(type_uses, *ts) |uses, subst| {
 250                         type_needs(cx, *uses, *subst)
 251                     }
 252                 }
 253               }
 254               typeck::method_param({param_num: param, _}) => {
 255                 cx.uses[param] |= use_tydesc;
 256               }
 257               typeck::method_trait(*) | typeck::method_self(*) => (),
 258             }
 259         }
 260       }
 261       expr_log(_, _, val) => {
 262         node_type_needs(cx, use_tydesc, val.id);
 263       }
 264       expr_call(f, _, _) => {
 265           for vec::each(
 266               ty::ty_fn_args(ty::node_id_to_type(cx.ccx.tcx, f.id))
 267           ) |a| {
 268               match a.mode {
 269                   expl(by_move) | expl(by_copy) | expl(by_val) => {
 270                       type_needs(cx, use_repr, a.ty);
 271                   }
 272                   _ => ()
 273               }
 274           }
 275       }
 276       expr_paren(e) => mark_for_expr(cx, e),
 277       expr_match(*) | expr_block(_) | expr_if(*) |
 278       expr_while(*) | expr_fail(_) | expr_break(_) | expr_again(_) |
 279       expr_unary(_, _) | expr_lit(_) | expr_assert(_) |
 280       expr_mac(_) | expr_addr_of(_, _) |
 281       expr_ret(_) | expr_loop(_, _) |
 282       expr_loop_body(_) | expr_do_body(_) => ()
 283     }
 284 }
 285
 286 fn handle_body(cx: ctx, body: blk) {
 287     let v = visit::mk_vt(@{
 288         visit_expr: |e, cx, v| {
 289             visit::visit_expr(e, cx, v);
 290             mark_for_expr(cx, e);
 291         },
 292         visit_local: |l, cx, v| {
 293             visit::visit_local(l, cx, v);
 294             node_type_needs(cx, use_repr, l.node.id);
 295         },
 296         visit_pat: |p, cx, v| {
 297             visit::visit_pat(p, cx, v);
 298             node_type_needs(cx, use_repr, p.id);
 299         },
 300         visit_block: |b, cx, v| {
 301             visit::visit_block(b, cx, v);
 302             do option::iter(&b.node.expr) |e| {
 303                 node_type_needs(cx, use_repr, e.id);
 304             }
 305         },
 306         visit_item: |_i, _cx, _v| { },
 307         ..*visit::default_visitor()
 308     });
 309     v.visit_block(body, cx, v);
 310 }