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