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 #include "set.h"
  28 #include "hashptr.h"
  29
  30
  31 /* *************************************************************************** */
  32 /* initialize, global variables.                                               */
  33 /* *************************************************************************** */
  34
  35 /* *************************************************************************** */
  36 /* Another hash table, this time containing temperature values.                */
  37 /* *************************************************************************** */
  38
  39 typedef struct {
  40   firm_kind *kind;   /* An entity or type. */
  41   double    val1;
  42 } temperature_tp;
  43
  44 /* We use this set for all types and entities.  */
  45 static set *temperature_set = NULL;
  46
  47 static int temp_cmp(const void *e1, const void *e2, size_t size) {
  48   temperature_tp *ef1 = (temperature_tp *)e1;
  49   temperature_tp *ef2 = (temperature_tp *)e2;
  50   return (ef1->kind != ef2->kind);
  51 }
  52
  53 static INLINE unsigned int tem_hash(void *e) {
  54   void *v = (void *) ((temperature_tp *)e)->kind;
  55   return HASH_PTR(v);
  56 }
  57
  58 double get_entity_acc_estimated_n_loads (entity *ent) {
  59   return 0;
  60 }
  61 double get_entity_acc_estimated_n_stores(entity *ent) {
  62   return 0;
  63 }
  64
  65 void set_entity_acc_estimated_n_loads (entity *ent, double val) {
  66 }
  67 void set_entity_acc_estimated_n_stores(entity *ent, double val) {
  68 }
  69
  70 double get_type_acc_estimated_n_instances(type *tp) {
  71   return 0;
  72 }
  73 void set_type_acc_estimated_n_instances(type *tp, double val) {
  74 }
  75
  76 /*
  77 static INLINE void set_region_exec_freq(void *reg, double freq) {
  78   reg_exec_freq ef;
  79   ef.reg  = reg;
  80   ef.freq = freq;
  81   set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  82 }
  83
  84 INLINE double get_region_exec_freq(void *reg) {
  85   reg_exec_freq ef, *found;
  86   ef.reg  = reg;
  87   assert(exec_freq_set);
  88   found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
  89   if (found)
  90     return found->freq;
  91   else
  92     return 0;
  93 }
  94 */
  95
  96
  97 /* *************************************************************************** */
  98 /*   Access routines for irnodes                                               */
  99 /* *************************************************************************** */
 100
 101 /* The entities that can be accessed by this Sel node. */
 102 int get_Sel_n_accessed_entities(ir_node *sel) {
 103   return 1;
 104 }
 105
 106 entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
 107   return get_Sel_entity(sel);
 108 }
 109
 110 /* *************************************************************************** */
 111 /* The heuristic                                                               */
 112 /* *************************************************************************** */
 113
 114 int get_irn_loop_call_depth(ir_node *n) {
 115   ir_graph *irg = get_irn_irg(n);
 116   return get_irg_loop_depth(irg);
 117 }
 118
 119 int get_irn_loop_depth(ir_node *n) {
 120   ir_loop *l = get_irn_loop(get_nodes_block(n));
 121   if (l)
 122     return get_loop_depth(l);
 123   else
 124     return 0;
 125 }
 126
 127 int get_irn_recursion_depth(ir_node *n) {
 128   ir_graph *irg = get_irn_irg(n);
 129   return get_irg_recursion_depth(irg);
 130 }
 131
 132
 133 /**   @@@ the second version of the heuristic. */
 134 int get_weighted_loop_depth(ir_node *n) {
 135   int loop_call_depth = get_irn_loop_call_depth(n);
 136   int loop_depth      = get_irn_loop_depth(n);
 137   int recursion_depth = get_irn_recursion_depth(n);
 138
 139   return loop_call_depth + loop_depth + recursion_depth;
 140 }
 141
 142
 143 /* *************************************************************************** */
 144 /* The 2. heuristic                                                            */
 145 /* *************************************************************************** */
 146
 147 static int default_recursion_weight = 5;
 148
 149
 150 /* The final evaluation of a node.  In this function we can
 151    adapt the heuristic.  Combine execution freqency with
 152    recursion depth.
 153    @@@ the second version of the heuristic. */
 154 double get_irn_final_cost(ir_node *n) {
 155   double cost_loop   = get_irn_exec_freq(n);
 156   double cost_method = get_irg_method_execution_frequency(get_irn_irg(n));
 157   int    rec_depth   = get_irn_recursion_depth(n);
 158   double cost_rec    = pow(default_recursion_weight, rec_depth);
 159   return cost_loop*(cost_method + cost_rec);
 160 }
 161
 162 double get_type_estimated_n_instances(type *tp) {
 163   int i, n_allocs = get_type_n_allocs(tp);
 164   double n_instances = 0;
 165   for (i = 0; i < n_allocs; ++i) {
 166     ir_node *alloc = get_type_alloc(tp, i);
 167     n_instances += get_irn_final_cost(alloc);
 168   }
 169   return n_instances;
 170 }
 171
 172 double get_type_estimated_mem_consumption_bytes(type *tp) {
 173   assert(0);
 174   return 0.0;
 175 }
 176
 177 int get_type_estimated_n_fields(type *tp) {
 178   int s = 0;
 179   switch(get_type_tpop_code(tp)) {
 180
 181   case tpo_primitive:
 182   case tpo_pointer:
 183   case tpo_enumeration:
 184     s = 1;
 185     break;
 186
 187   case tpo_class:
 188     s = 1; /* dispatch pointer */
 189     /* fall through */
 190   case tpo_struct: {
 191     int i, n_mem = get_compound_n_members(tp);
 192     for (i = 0; i < n_mem; ++i) {
 193       entity *mem = get_compound_member(tp, i);
 194       if (get_entity_allocation(mem) == allocation_automatic) {
 195         s += get_type_estimated_n_fields(get_entity_type(mem));
 196       }
 197     }
 198   } break;
 199
 200   case tpo_array: {
 201     long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
 202     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 203     if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
 204         (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const)   ) {
 205       n_elt = get_array_upper_bound_int(tp, 0) - get_array_upper_bound_int(tp, 0);
 206     }
 207     s = n_elt;
 208   } break;
 209
 210   default: DDMT(tp); assert(0);
 211   }
 212
 213   return s;
 214 }
 215
 216 int get_type_estimated_size_bytes(type *tp) {
 217   int s = 0;
 218
 219   switch(get_type_tpop_code(tp)) {
 220
 221   case tpo_primitive:
 222   case tpo_pointer:
 223   case tpo_enumeration:
 224     s = get_mode_size_bytes(get_type_mode(tp));
 225     break;
 226
 227   case tpo_class:
 228     s = get_mode_size_bytes(mode_P_mach); /* dispatch pointer */
 229     /* fall through */
 230   case tpo_struct: {
 231     int i, n_mem = get_compound_n_members(tp);
 232     for (i = 0; i < n_mem; ++i) {
 233       entity *mem = get_compound_member(tp, i);
 234       s += get_type_estimated_size_bytes(get_entity_type(mem));
 235
 236       if (get_entity_allocation(mem) == allocation_automatic) {
 237       } /* allocation_automatic */
 238     }
 239   } break;
 240
 241   case tpo_array: {
 242     int elt_s = get_type_estimated_size_bytes(get_array_element_type(tp));
 243     long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
 244     assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
 245     if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
 246         (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const)   ) {
 247       n_elt = get_array_upper_bound_int(tp, 0) - get_array_lower_bound_int(tp, 0);
 248     }
 249     s = n_elt * elt_s;
 250     break;
 251   }
 252
 253   default: DDMT(tp); assert(0);
 254   }
 255
 256   return s;
 257 }
 258
 259 double get_type_estimated_n_casts(type *tp) {
 260   int i, n_casts = get_type_n_casts(tp);
 261   double n_instances = 0;
 262   for (i = 0; i < n_casts; ++i) {
 263     ir_node *cast = get_type_cast(tp, i);
 264     n_instances += get_irn_final_cost(cast);
 265   }
 266   return n_instances;
 267 }
 268
 269 double get_class_estimated_n_upcasts(type *clss) {
 270   double n_instances = 0;
 271   int i, j, n_casts, n_pointertypes;
 272
 273   n_casts = get_type_n_casts(clss);
 274   for (i = 0; i < n_casts; ++i) {
 275     ir_node *cast = get_type_cast(clss, i);
 276     if (get_irn_opcode(cast) != iro_Cast) continue;  /* Could be optimized away. */
 277
 278     if (is_Cast_upcast(cast))
 279       n_instances += get_irn_final_cost(cast);
 280   }
 281
 282   n_pointertypes = get_type_n_pointertypes_to(clss);
 283   for (j = 0; j < n_pointertypes; ++j) {
 284     n_instances += get_class_estimated_n_upcasts(get_type_pointertype_to(clss, j));
 285   }
 286
 287   return n_instances;
 288 }
 289
 290 double get_class_estimated_n_downcasts(type *clss) {
 291   double n_instances = 0;
 292   int i, j, n_casts, n_pointertypes;
 293
 294   n_casts = get_type_n_casts(clss);
 295   for (i = 0; i < n_casts; ++i) {
 296     ir_node *cast = get_type_cast(clss, i);
 297     if (get_irn_opcode(cast) != iro_Cast) continue;  /* Could be optimized away. */
 298
 299     if (is_Cast_downcast(cast))
 300       n_instances += get_irn_final_cost(cast);
 301   }
 302
 303   n_pointertypes = get_type_n_pointertypes_to(clss);
 304   for (j = 0; j < n_pointertypes; ++j) {
 305     n_instances += get_class_estimated_n_downcasts(get_type_pointertype_to(clss, j));
 306   }
 307
 308   return n_instances;
 309 }
 310
 311
 312 double get_class_estimated_dispatch_writes(type *clss) {
 313   return get_type_estimated_n_instances(clss);
 314 }
 315
 316 /** Returns the number of reads of the dispatch pointer. */
 317 double get_class_estimated_dispatch_reads (type *clss) {
 318   int i, n_mems = get_class_n_members(clss);
 319   double n_calls = 0;
 320   for (i = 0; i < n_mems; ++i) {
 321     entity *mem = get_class_member(clss, i);
 322     n_calls += get_entity_estimated_n_dyncalls(mem);
 323   }
 324   return n_calls;
 325 }
 326
 327 double get_class_estimated_n_dyncalls(type *clss) {
 328   return get_class_estimated_dispatch_reads(clss) +
 329          get_class_estimated_dispatch_writes(clss);
 330 }
 331
 332 double get_entity_estimated_n_loads(entity *ent) {
 333   int i, n_acc = get_entity_n_accesses(ent);
 334   double n_loads = 0;
 335   for (i = 0; i < n_acc; ++i) {
 336     ir_node *acc = get_entity_access(ent, i);
 337     if (get_irn_op(acc) == op_Load) {
 338       n_loads += get_irn_final_cost(acc);
 339     }
 340   }
 341   return n_loads;
 342 }
 343
 344 double get_entity_estimated_n_stores(entity *ent) {
 345   int i, n_acc = get_entity_n_accesses(ent);
 346   double n_stores = 0;
 347   for (i = 0; i < n_acc; ++i) {
 348     ir_node *acc = get_entity_access(ent, i);
 349     if (get_irn_op(acc) == op_Store)
 350       n_stores += get_irn_final_cost(acc);
 351   }
 352   return n_stores;
 353 }
 354
 355 /* @@@ Should we evaluate the callee array?  */
 356 double get_entity_estimated_n_calls(entity *ent) {
 357   int i, n_acc = get_entity_n_accesses(ent);
 358   double n_calls = 0;
 359   for (i = 0; i < n_acc; ++i) {
 360     ir_node *acc = get_entity_access(ent, i);
 361     if (get_irn_op(acc) == op_Call)
 362
 363       n_calls += get_irn_final_cost(acc);
 364   }
 365   return n_calls;
 366 }
 367
 368 double get_entity_estimated_n_dyncalls(entity *ent) {
 369   int i, n_acc = get_entity_n_accesses(ent);
 370   double n_calls = 0;
 371   for (i = 0; i < n_acc; ++i) {
 372     ir_node *acc = get_entity_access(ent, i);
 373
 374     /* Call->Sel(ent) combination */
 375     if ((get_irn_op(acc) == op_Call)  &&
 376         (get_irn_op(get_Call_ptr(acc)) == op_Sel)) {
 377       n_calls += get_irn_final_cost(acc);
 378
 379     /* MemOp->Sel combination for static, overwritten entities */
 380     } else if (is_memop(acc) && (get_irn_op(get_memop_ptr(acc)) == op_Sel)) {
 381       entity *ent = get_Sel_entity(get_memop_ptr(acc));
 382       if (is_Class_type(get_entity_owner(ent))) {
 383         /* We might call this for inner entities in compounds. */
 384         if (get_entity_n_overwrites(ent) > 0 ||
 385             get_entity_n_overwrittenby(ent) > 0) {
 386           n_calls += get_irn_final_cost(acc);
 387         }
 388       }
 389     }
 390
 391   }
 392   return n_calls;
 393 }
 394
 395 /* ------------------------------------------------------------------------- */
 396 /* Accumulate information in the type hierarchy.                             */
 397 /* This should go to co_read_profiling.c                                     */
 398 /* ------------------------------------------------------------------------- */
 399
 400 static void acc_temp (type *tp) {
 401   int i, n_subtypes, n_members;
 402   double inst;
 403
 404   assert(is_Class_type(tp));
 405
 406   /* Recursive descend. */
 407   n_subtypes = get_class_n_subtypes(tp);
 408   for (i = 0; i < n_subtypes; ++i) {
 409     type *stp = get_class_subtype(tp, i);
 410     if (type_not_visited(stp)) {
 411       acc_temp(stp);
 412     }
 413   }
 414
 415   /* Deal with entity numbers. */
 416   n_members = get_class_n_members(tp);
 417   for (i = 0; i < n_members; ++i) {
 418     entity *mem = get_class_member(tp, i);
 419     double acc_loads  = get_entity_estimated_n_loads (mem);
 420     double acc_writes = get_entity_estimated_n_stores(mem);
 421     int j, n_ov = get_entity_n_overwrittenby(mem);
 422     for (j = 0; j < n_ov; ++j) {
 423       entity *ov_mem = get_entity_overwrittenby(mem, j);
 424       acc_loads  += get_entity_acc_estimated_n_loads (ov_mem);
 425       acc_writes += get_entity_acc_estimated_n_stores(ov_mem);
 426     }
 427     set_entity_acc_estimated_n_loads (mem, acc_loads);
 428     set_entity_acc_estimated_n_stores(mem, acc_writes);
 429   }
 430
 431   /* Deal with type numbers. */
 432   inst = get_type_estimated_n_instances(tp);
 433   for (i = 0; i < n_subtypes; ++i) {
 434     type *stp = get_class_subtype(tp, i);
 435     inst += get_type_acc_estimated_n_instances(stp);
 436   }
 437   set_type_acc_estimated_n_instances(tp, inst);
 438
 439   mark_type_visited(tp);
 440 }
 441
 442 void accumulate_temperatures(void) {
 443   int i, n_types = get_irp_n_types();
 444   free_accumulated_temperatures();
 445
 446   inc_master_type_visited();
 447   for (i = 0; i < n_types; ++i) {
 448     type *tp = get_irp_type(i);
 449     if (is_Class_type(tp)) { /* For others there is nothing to accumulate. */
 450       int j, n_subtypes = get_class_n_subtypes(tp);
 451       int has_unmarked_subtype = false;
 452       for (j = 0; j < n_subtypes && !has_unmarked_subtype; ++j) {
 453               type *stp = get_class_subtype(tp, j);
 454               if (type_not_visited(stp)) has_unmarked_subtype = true;
 455       }
 456
 457       if (!has_unmarked_subtype)
 458               acc_temp(tp);
 459     }
 460   }
 461
 462   irp->temperature_state = temperature_consistent;
 463 }
 464
 465
 466 void free_accumulated_temperatures(void) {
 467   if (temperature_set) del_set(temperature_set);
 468   temperature_set = NULL;
 469   irp->temperature_state = temperature_none;
 470 }
 471
 472 /* ------------------------------------------------------------------------- */
 473 /* Auxiliary                                                                 */
 474 /* ------------------------------------------------------------------------- */
 475
 476 int is_jack_rts_name(ident *name) {
 477   return  0;
 478   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 479   if (id_is_prefix(new_id_from_str("["),     name)) return 1;
 480   if (id_is_prefix(new_id_from_str("gnu/"),  name)) return 1;
 481   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 482   if (id_is_prefix(new_id_from_str("CStringToCoreString"), name)) return 1;
 483
 484   return 0;
 485 }
 486
 487
 488 int is_jack_rts_class(type *t) {
 489   ident *name = get_type_ident(t);
 490   return is_jack_rts_name(name);
 491 }
 492
 493 #include "entity_t.h"  // for the assertion.
 494
 495 int is_jack_rts_entity(entity *e) {
 496   ident *name;
 497
 498   assert(e->ld_name);
 499   name = get_entity_ld_ident(e);
 500
 501   return is_jack_rts_name(name);
 502 }