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