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

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