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

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