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