nsz Git - libfirm/blob - ir/ana/field_temperature.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/field_temperature.c
   4  * Purpose:     Compute an estimate of field temperature, i.e., field access heuristic.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     21.7.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include "config.h"
  15 #endif
  16
  17 #include <math.h>
  18
  19 #include "field_temperature.h"
  20
  21 #include "trouts.h"
  22 #include "execution_frequency.h"
  23
  24 #include "irnode_t.h"
  25 #include "irgraph_t.h"
  26 #include "irprog_t.h"
  27 #include "entity_t.h"
  28 #include "irgwalk.h"
  29
  30 #include "array.h"
  31
  32 /* *************************************************************************** */
  33 /* initialize, global variables.                                               */
  34 /* *************************************************************************** */
  35
  36 /* *************************************************************************** */
  37 /*   Access routines for irnodes                                               */
  38 /* *************************************************************************** */
  39
  40 /* The entities that can be accessed by this Sel node. */
  41 int get_Sel_n_accessed_entities(ir_node *sel) {
  42   return 1;
  43 }
  44
  45 ir_entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
  46   return get_Sel_entity(sel);
  47 }
  48
  49 /* *************************************************************************** */
  50 /* The heuristic                                                               */
  51 /* *************************************************************************** */
  52
  53 int get_irn_loop_call_depth(ir_node *n) {
  54   ir_graph *irg = get_irn_irg(n);
  55   return get_irg_loop_depth(irg);
  56 }
  57
  58 int get_irn_cfloop_depth(ir_node *n) {
  59   ir_loop *l = get_irn_loop(get_nodes_block(n));
  60   if (l)
  61     return get_loop_depth(l);
  62   else
  63     return 0;
  64 }
  65
  66 int get_irn_recursion_depth(ir_node *n) {
  67   ir_graph *irg = get_irn_irg(n);
  68   return get_irg_recursion_depth(irg);
  69 }
  70
  71
  72 /**   @@@ the second version of the heuristic. */
  73 int get_weighted_loop_depth(ir_node *n) {
  74   int loop_call_depth = get_irn_loop_call_depth(n);
  75   int loop_depth      = get_irn_cfloop_depth(n);
  76   int recursion_depth = get_irn_recursion_depth(n);
  77
  78   return loop_call_depth + loop_depth + recursion_depth;
  79 }
  80
  81
  82 /* *************************************************************************** */
  83 /* The 2. heuristic                                                            */
  84 /* *************************************************************************** */
  85
  86 static int default_recursion_weight = 5;
  87
  88 /* The final evaluation of a node.  In this function we can
  89    adapt the heuristic.  Combine execution frequency with
  90    recursion depth.
  91    @@@ the second version of the heuristic.
  92
  93    Return 0 if the node is neither in a loop nor in a recursion.  */
  94 double get_irn_final_cost(ir_node *n) {
  95   double cost_loop   = get_irn_exec_freq(n);
  96   double cost_method = get_irg_method_execution_frequency(get_irn_irg(n));
  97   int    rec_depth   = get_irn_recursion_depth(n);
  98   double cost_rec    = 0;
  99
 100 #if 0
 101   if (get_irn_recursion_depth(n) == 0 &&
 102       get_irn_loop_depth(n) == 0 &&
 103       get_irg_method_loop_depth(get_irn_irg(n)) == 0)
 104     return 0;
 105 #else
 106   if (get_weighted_loop_depth(n) == 0) return 0;
 107 #endif
 108
 109   if (rec_depth) cost_rec = pow(default_recursion_weight, rec_depth);
 110   return cost_loop*(cost_method + cost_rec);
 111 }
 112
 113 double get_type_estimated_n_instances(ir_type *tp) {
 114   int i, n_allocs = get_type_n_allocs(tp);
 115   double n_instances = 0;
 116   for (i = 0; i < n_allocs; ++i) {
 117     ir_node *alloc = get_type_alloc(tp, i);
 118     n_instances += get_irn_final_cost(alloc);
 119   }
 120   return n_instances;
 121 }
 122
 123 double get_type_estimated_mem_consumption_bytes(ir_type *tp) {
 124   assert(0);
 125   return 0.0;
 126 }
 127
 128 int get_type_estimated_n_fields(ir_type *tp) {
 129   int s = 0;
 130   switch(get_type_tpop_code(tp)) {
 131
 132   case tpo_primitive:
 133   case tpo_pointer:
 134   case tpo_enumeration:
 135     s = 1;
 136     break;
 137
 138   case tpo_class:
 139     s = 1; /* dispatch pointer */
 140     /* fall through */
 141   case tpo_struct: {
 142     int i, n_mem = get_compound_n_members(tp);
 143     for (i = 0; i < n_mem; ++i) {
 144       ir_entity *mem = get_compound_member(tp, i);
 145       if (get_entity_allocation(mem) == allocation_automatic) {
 146         s += get_type_estimated_n_fields(get_entity_type(mem));
 147       }
 148     }
 149   } break;
 150
 151   case tpo_array: {
 152     long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
 153     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 154     if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
 155         (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const)   ) {
 156       n_elt = get_array_upper_bound_int(tp, 0) - get_array_upper_bound_int(tp, 0);
 157     }
 158     s = n_elt;
 159   } break;
 160
 161   default: DDMT(tp); assert(0);
 162   }
 163
 164   return s;
 165 }
 166
 167 int get_type_estimated_size_bytes(ir_type *tp) {
 168   int s = 0;
 169
 170   switch(get_type_tpop_code(tp)) {
 171
 172   case tpo_primitive:
 173   case tpo_pointer:
 174   case tpo_enumeration:
 175     s = get_mode_size_bytes(get_type_mode(tp));
 176     break;
 177
 178   case tpo_class:
 179     s = get_mode_size_bytes(mode_P_data); /* dispatch pointer */
 180     /* fall through */
 181   case tpo_struct: {
 182     int i, n_mem = get_compound_n_members(tp);
 183     for (i = 0; i < n_mem; ++i) {
 184       ir_entity *mem = get_compound_member(tp, i);
 185       s += get_type_estimated_size_bytes(get_entity_type(mem));
 186
 187       if (get_entity_allocation(mem) == allocation_automatic) {
 188       } /* allocation_automatic */
 189     }
 190   } break;
 191
 192   case tpo_array: {
 193     int elt_s = get_type_estimated_size_bytes(get_array_element_type(tp));
 194     long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
 195     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 196     if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
 197         (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const)   ) {
 198       n_elt = get_array_upper_bound_int(tp, 0) - get_array_lower_bound_int(tp, 0);
 199     }
 200     s = n_elt * elt_s;
 201     break;
 202   }
 203
 204   default: DDMT(tp); assert(0);
 205   }
 206
 207   return s;
 208 }
 209
 210 double get_type_estimated_n_casts(ir_type *tp) {
 211   int i, n_casts = get_type_n_casts(tp);
 212   double n_instances = 0;
 213   for (i = 0; i < n_casts; ++i) {
 214     ir_node *cast = get_type_cast(tp, i);
 215     n_instances += get_irn_final_cost(cast);
 216   }
 217   return n_instances;
 218 }
 219
 220 double get_class_estimated_n_upcasts(ir_type *clss) {
 221   double n_instances = 0;
 222   int i, j, n_casts, n_pointertypes;
 223
 224   n_casts = get_type_n_casts(clss);
 225   for (i = 0; i < n_casts; ++i) {
 226     ir_node *cast = get_type_cast(clss, i);
 227     if (get_irn_opcode(cast) != iro_Cast) continue;  /* Could be optimized away. */
 228
 229     if (is_Cast_upcast(cast))
 230       n_instances += get_irn_final_cost(cast);
 231   }
 232
 233   n_pointertypes = get_type_n_pointertypes_to(clss);
 234   for (j = 0; j < n_pointertypes; ++j) {
 235     n_instances += get_class_estimated_n_upcasts(get_type_pointertype_to(clss, j));
 236   }
 237
 238   return n_instances;
 239 }
 240
 241 double get_class_estimated_n_downcasts(ir_type *clss) {
 242   double n_instances = 0;
 243   int i, j, n_casts, n_pointertypes;
 244
 245   n_casts = get_type_n_casts(clss);
 246   for (i = 0; i < n_casts; ++i) {
 247     ir_node *cast = get_type_cast(clss, i);
 248     if (get_irn_opcode(cast) != iro_Cast) continue;  /* Could be optimized away. */
 249
 250     if (is_Cast_downcast(cast))
 251       n_instances += get_irn_final_cost(cast);
 252   }
 253
 254   n_pointertypes = get_type_n_pointertypes_to(clss);
 255   for (j = 0; j < n_pointertypes; ++j) {
 256     n_instances += get_class_estimated_n_downcasts(get_type_pointertype_to(clss, j));
 257   }
 258
 259   return n_instances;
 260 }
 261
 262
 263 double get_class_estimated_dispatch_writes(ir_type *clss) {
 264   return get_type_estimated_n_instances(clss);
 265 }
 266
 267 /** Returns the number of reads of the dispatch pointer. */
 268 double get_class_estimated_dispatch_reads (ir_type *clss) {
 269   int i, n_mems = get_class_n_members(clss);
 270   double n_calls = 0;
 271   for (i = 0; i < n_mems; ++i) {
 272     ir_entity *mem = get_class_member(clss, i);
 273     n_calls += get_entity_estimated_n_dyncalls(mem);
 274   }
 275   return n_calls;
 276 }
 277
 278 double get_class_estimated_n_dyncalls(ir_type *clss) {
 279   return get_class_estimated_dispatch_reads(clss) +
 280          get_class_estimated_dispatch_writes(clss);
 281 }
 282
 283 double get_entity_estimated_n_loads(ir_entity *ent) {
 284   int i, n_acc = get_entity_n_accesses(ent);
 285   double n_loads = 0;
 286   for (i = 0; i < n_acc; ++i) {
 287     ir_node *acc = get_entity_access(ent, i);
 288     if (get_irn_op(acc) == op_Load) {
 289       n_loads += get_irn_final_cost(acc);
 290     }
 291   }
 292   return n_loads;
 293 }
 294
 295 double get_entity_estimated_n_stores(ir_entity *ent) {
 296   int i, n_acc = get_entity_n_accesses(ent);
 297   double n_stores = 0;
 298   for (i = 0; i < n_acc; ++i) {
 299     ir_node *acc = get_entity_access(ent, i);
 300     if (get_irn_op(acc) == op_Store)
 301       n_stores += get_irn_final_cost(acc);
 302   }
 303   return n_stores;
 304 }
 305
 306 /* @@@ Should we evaluate the callee array?  */
 307 double get_entity_estimated_n_calls(ir_entity *ent) {
 308   int i, n_acc = get_entity_n_accesses(ent);
 309   double n_calls = 0;
 310   for (i = 0; i < n_acc; ++i) {
 311     ir_node *acc = get_entity_access(ent, i);
 312     if (get_irn_op(acc) == op_Call)
 313
 314       n_calls += get_irn_final_cost(acc);
 315   }
 316   return n_calls;
 317 }
 318
 319 double get_entity_estimated_n_dyncalls(ir_entity *ent) {
 320   int i, n_acc = get_entity_n_accesses(ent);
 321   double n_calls = 0;
 322   for (i = 0; i < n_acc; ++i) {
 323     ir_node *acc = get_entity_access(ent, i);
 324
 325     /* Call->Sel(ent) combination */
 326     if (is_Call(acc) && is_Sel(get_Call_ptr(acc))) {
 327       n_calls += get_irn_final_cost(acc);
 328
 329     /* MemOp->Sel combination for static, overwritten entities */
 330     } else if (is_memop(acc) && is_Sel(get_memop_ptr(acc))) {
 331       ir_entity *ent = get_Sel_entity(get_memop_ptr(acc));
 332       if (is_Class_type(get_entity_owner(ent))) {
 333         /* We might call this for inner entities in compounds. */
 334         if (get_entity_n_overwrites(ent) > 0 ||
 335             get_entity_n_overwrittenby(ent) > 0) {
 336           n_calls += get_irn_final_cost(acc);
 337         }
 338       }
 339     }
 340
 341   }
 342   return n_calls;
 343 }
 344
 345 /* ------------------------------------------------------------------------- */
 346 /* Auxiliary                                                                 */
 347 /* ------------------------------------------------------------------------- */
 348
 349 int is_jack_rts_name(ident *name) {
 350   if (id_is_suffix(new_id_from_str("Exception"), name)) return 1;
 351   if (id_is_suffix(new_id_from_str("Throwable"), name)) return 1;
 352   if (id_is_suffix(new_id_from_str("Error"),     name)) return 1;
 353
 354   return  0;
 355
 356   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 357   if (id_is_prefix(new_id_from_str("["),     name)) return 1;
 358   if (id_is_prefix(new_id_from_str("gnu/"),  name)) return 1;
 359   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 360   if (id_is_prefix(new_id_from_str("CStringToCoreString"), name)) return 1;
 361
 362   return 0;
 363 }
 364
 365
 366 int is_jack_rts_class(ir_type *t) {
 367   ident *name = get_type_ident(t);
 368   return is_jack_rts_name(name);
 369 }
 370
 371 #include "entity_t.h"  // for the assertion.
 372
 373 int is_jack_rts_entity(ir_entity *e) {
 374   ident *name;
 375
 376   assert(e->ld_name);
 377   name = get_entity_ld_ident(e);
 378
 379   return is_jack_rts_name(name);
 380 }