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