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
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
15 #include "field_temperature.h"
18 #include "execution_frequency.h"
21 #include "irgraph_t.h"
31 /* *************************************************************************** */
32 /* initialize, global variables. */
33 /* *************************************************************************** */
35 /* *************************************************************************** */
36 /* Another hash table, this time containing temperature values. */
37 /* *************************************************************************** */
40 firm_kind *kind; /* An entity or type. */
44 /* We use this set for all types and entities. */
45 static set *temperature_set = NULL;
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);
53 static INLINE unsigned int tem_hash(void *e) {
54 void *v = (void *) ((temperature_tp *)e)->kind;
58 double get_entity_acc_estimated_n_loads (entity *ent) {
61 double get_entity_acc_estimated_n_stores(entity *ent) {
65 void set_entity_acc_estimated_n_loads (entity *ent, double val) {
67 void set_entity_acc_estimated_n_stores(entity *ent, double val) {
70 double get_type_acc_estimated_n_instances(type *tp) {
73 void set_type_acc_estimated_n_instances(type *tp, double val) {
77 static INLINE void set_region_exec_freq(void *reg, double freq) {
81 set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
84 INLINE double get_region_exec_freq(void *reg) {
85 reg_exec_freq ef, *found;
87 assert(exec_freq_set);
88 found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
97 /* *************************************************************************** */
98 /* Access routines for irnodes */
99 /* *************************************************************************** */
101 /* The entities that can be accessed by this Sel node. */
102 int get_Sel_n_accessed_entities(ir_node *sel) {
106 entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
107 return get_Sel_entity(sel);
110 /* *************************************************************************** */
112 /* *************************************************************************** */
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);
119 int get_irn_loop_depth(ir_node *n) {
120 ir_loop *l = get_irn_loop(get_nodes_block(n));
122 return get_loop_depth(l);
127 int get_irn_recursion_depth(ir_node *n) {
128 ir_graph *irg = get_irn_irg(n);
129 return get_irg_recursion_depth(irg);
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);
139 return loop_call_depth + loop_depth + recursion_depth;
143 /* *************************************************************************** */
144 /* The 2. heuristic */
145 /* *************************************************************************** */
147 static int default_recursion_weight = 5;
150 /* The final evaluation of a node. In this function we can
151 adapt the heuristic. Combine execution freqency with
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);
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);
172 double get_type_estimated_mem_consumption_bytes(type *tp) {
177 int get_type_estimated_n_fields(type *tp) {
179 switch(get_type_tpop_code(tp)) {
183 case tpo_enumeration:
188 s = 1; /* dispatch pointer */
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));
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);
210 default: DDMT(tp); assert(0);
216 int get_type_estimated_size_bytes(type *tp) {
219 switch(get_type_tpop_code(tp)) {
223 case tpo_enumeration:
224 s = get_mode_size_bytes(get_type_mode(tp));
228 s = get_mode_size_bytes(mode_P_mach); /* dispatch pointer */
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));
236 if (get_entity_allocation(mem) == allocation_automatic) {
237 } /* allocation_automatic */
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);
253 default: DDMT(tp); assert(0);
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);
269 double get_class_estimated_n_upcasts(type *clss) {
270 double n_instances = 0;
271 int i, j, n_casts, n_pointertypes;
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. */
278 if (is_Cast_upcast(cast))
279 n_instances += get_irn_final_cost(cast);
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));
290 double get_class_estimated_n_downcasts(type *clss) {
291 double n_instances = 0;
292 int i, j, n_casts, n_pointertypes;
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. */
299 if (is_Cast_downcast(cast))
300 n_instances += get_irn_final_cost(cast);
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));
312 double get_class_estimated_dispatch_writes(type *clss) {
313 return get_type_estimated_n_instances(clss);
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);
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);
327 double get_class_estimated_n_dyncalls(type *clss) {
328 return get_class_estimated_dispatch_reads(clss) +
329 get_class_estimated_dispatch_writes(clss);
332 double get_entity_estimated_n_loads(entity *ent) {
333 int i, n_acc = get_entity_n_accesses(ent);
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);
344 double get_entity_estimated_n_stores(entity *ent) {
345 int i, n_acc = get_entity_n_accesses(ent);
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);
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);
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)
363 n_calls += get_irn_final_cost(acc);
368 double get_entity_estimated_n_dyncalls(entity *ent) {
369 int i, n_acc = get_entity_n_accesses(ent);
371 for (i = 0; i < n_acc; ++i) {
372 ir_node *acc = get_entity_access(ent, i);
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);
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);
395 /* ------------------------------------------------------------------------- */
396 /* Accumulate information in the type hierarchy. */
397 /* This should go to co_read_profiling.c */
398 /* ------------------------------------------------------------------------- */
400 static void acc_temp (type *tp) {
401 int i, n_subtypes, n_members;
404 assert(is_Class_type(tp));
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)) {
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);
427 set_entity_acc_estimated_n_loads (mem, acc_loads);
428 set_entity_acc_estimated_n_stores(mem, acc_writes);
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);
437 set_type_acc_estimated_n_instances(tp, inst);
439 mark_type_visited(tp);
442 void accumulate_temperatures(void) {
443 int i, n_types = get_irp_n_types();
444 free_accumulated_temperatures();
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;
457 if (!has_unmarked_subtype)
462 irp->temperature_state = temperature_consistent;
466 void free_accumulated_temperatures(void) {
467 if (temperature_set) del_set(temperature_set);
468 temperature_set = NULL;
469 irp->temperature_state = temperature_none;
472 /* ------------------------------------------------------------------------- */
474 /* ------------------------------------------------------------------------- */
476 int is_jack_rts_name(ident *name) {
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;
488 int is_jack_rts_class(type *t) {
489 ident *name = get_type_ident(t);
490 return is_jack_rts_name(name);
493 #include "entity_t.h" // for the assertion.
495 int is_jack_rts_entity(entity *e) {
499 name = get_entity_ld_ident(e);
501 return is_jack_rts_name(name);