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) {
176 int get_type_estimated_n_fields(type *tp) {
178 switch(get_type_tpop_code(tp)) {
182 case tpo_enumeration:
187 s = 1; /* dispatch pointer */
190 int i, n_mem = get_compound_n_members(tp);
191 for (i = 0; i < n_mem; ++i) {
192 entity *mem = get_compound_member(tp, i);
193 if (get_entity_allocation(mem) == allocation_automatic) {
194 s += get_type_estimated_n_fields(get_entity_type(mem));
200 long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
201 assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
202 if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
203 (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const) ) {
204 n_elt = get_array_upper_bound_int(tp, 0) - get_array_upper_bound_int(tp, 0);
209 default: DDMT(tp); assert(0);
215 int get_type_estimated_size_bytes(type *tp) {
218 switch(get_type_tpop_code(tp)) {
222 case tpo_enumeration:
223 s = get_mode_size_bytes(get_type_mode(tp));
227 s = get_mode_size_bytes(mode_P_mach); /* dispatch pointer */
230 int i, n_mem = get_compound_n_members(tp);
231 for (i = 0; i < n_mem; ++i) {
232 entity *mem = get_compound_member(tp, i);
233 s += get_type_estimated_size_bytes(get_entity_type(mem));
235 if (get_entity_allocation(mem) == allocation_automatic) {
236 } /* allocation_automatic */
241 int elt_s = get_type_estimated_size_bytes(get_array_element_type(tp));
242 long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
243 assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
244 if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
245 (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const) ) {
246 n_elt = get_array_upper_bound_int(tp, 0) - get_array_lower_bound_int(tp, 0);
252 default: DDMT(tp); assert(0);
258 double get_type_estimated_n_casts(type *tp) {
259 int i, n_casts = get_type_n_casts(tp);
260 double n_instances = 0;
261 for (i = 0; i < n_casts; ++i) {
262 ir_node *cast = get_type_cast(tp, i);
263 n_instances += get_irn_final_cost(cast);
268 double get_class_estimated_n_upcasts(type *clss) {
269 double n_instances = 0;
270 int i, j, n_casts, n_pointertypes;
272 n_casts = get_type_n_casts(clss);
273 for (i = 0; i < n_casts; ++i) {
274 ir_node *cast = get_type_cast(clss, i);
275 if (get_irn_opcode(cast) != iro_Cast) continue; /* Could be optimized away. */
277 if (is_Cast_upcast(cast))
278 n_instances += get_irn_final_cost(cast);
281 n_pointertypes = get_type_n_pointertypes_to(clss);
282 for (j = 0; j < n_pointertypes; ++j) {
283 n_instances += get_class_estimated_n_upcasts(get_type_pointertype_to(clss, j));
289 double get_class_estimated_n_downcasts(type *clss) {
290 double n_instances = 0;
291 int i, j, n_casts, n_pointertypes;
293 n_casts = get_type_n_casts(clss);
294 for (i = 0; i < n_casts; ++i) {
295 ir_node *cast = get_type_cast(clss, i);
296 if (get_irn_opcode(cast) != iro_Cast) continue; /* Could be optimized away. */
298 if (is_Cast_downcast(cast))
299 n_instances += get_irn_final_cost(cast);
302 n_pointertypes = get_type_n_pointertypes_to(clss);
303 for (j = 0; j < n_pointertypes; ++j) {
304 n_instances += get_class_estimated_n_downcasts(get_type_pointertype_to(clss, j));
311 double get_class_estimated_dispatch_writes(type *clss) {
312 return get_type_estimated_n_instances(clss);
315 /** Returns the number of reads of the dispatch pointer. */
316 double get_class_estimated_dispatch_reads (type *clss) {
317 int i, n_mems = get_class_n_members(clss);
319 for (i = 0; i < n_mems; ++i) {
320 entity *mem = get_class_member(clss, i);
321 n_calls += get_entity_estimated_n_dyncalls(mem);
326 double get_class_estimated_n_dyncalls(type *clss) {
327 return get_class_estimated_dispatch_reads(clss) +
328 get_class_estimated_dispatch_writes(clss);
331 double get_entity_estimated_n_loads(entity *ent) {
332 int i, n_acc = get_entity_n_accesses(ent);
334 for (i = 0; i < n_acc; ++i) {
335 ir_node *acc = get_entity_access(ent, i);
336 if (get_irn_op(acc) == op_Load) {
337 n_loads += get_irn_final_cost(acc);
343 double get_entity_estimated_n_stores(entity *ent) {
344 int i, n_acc = get_entity_n_accesses(ent);
346 for (i = 0; i < n_acc; ++i) {
347 ir_node *acc = get_entity_access(ent, i);
348 if (get_irn_op(acc) == op_Store)
349 n_stores += get_irn_final_cost(acc);
354 /* @@@ Should we evaluate the callee array? */
355 double get_entity_estimated_n_calls(entity *ent) {
356 int i, n_acc = get_entity_n_accesses(ent);
358 for (i = 0; i < n_acc; ++i) {
359 ir_node *acc = get_entity_access(ent, i);
360 if (get_irn_op(acc) == op_Call)
362 n_calls += get_irn_final_cost(acc);
367 double get_entity_estimated_n_dyncalls(entity *ent) {
368 int i, n_acc = get_entity_n_accesses(ent);
370 for (i = 0; i < n_acc; ++i) {
371 ir_node *acc = get_entity_access(ent, i);
373 /* Call->Sel(ent) combination */
374 if ((get_irn_op(acc) == op_Call) &&
375 (get_irn_op(get_Call_ptr(acc)) == op_Sel)) {
376 n_calls += get_irn_final_cost(acc);
378 /* MemOp->Sel combination for static, overwritten entities */
379 } else if (is_memop(acc) && (get_irn_op(get_memop_ptr(acc)) == op_Sel)) {
380 entity *ent = get_Sel_entity(get_memop_ptr(acc));
381 if (is_Class_type(get_entity_owner(ent))) {
382 /* We might call this for inner entities in compounds. */
383 if (get_entity_n_overwrites(ent) > 0 ||
384 get_entity_n_overwrittenby(ent) > 0) {
385 n_calls += get_irn_final_cost(acc);
394 /* ------------------------------------------------------------------------- */
395 /* Accumulate information in the type hierarchy. */
396 /* This should go to co_read_profiling.c */
397 /* ------------------------------------------------------------------------- */
399 static void acc_temp (type *tp) {
400 assert(is_Class_type(tp));
402 int i, n_subtypes = get_class_n_subtypes(tp);
404 /* Recursive descend. */
405 for (i = 0; i < n_subtypes; ++i) {
406 type *stp = get_class_subtype(tp, i);
407 if (type_not_visited(stp)) {
412 /* Deal with entity numbers. */
413 int n_members = get_class_n_members(tp);
414 for (i = 0; i < n_members; ++i) {
415 entity *mem = get_class_member(tp, i);
416 double acc_loads = get_entity_estimated_n_loads (mem);
417 double acc_writes = get_entity_estimated_n_stores(mem);
418 int j, n_ov = get_entity_n_overwrittenby(mem);
419 for (j = 0; j < n_ov; ++j) {
420 entity *ov_mem = get_entity_overwrittenby(mem, j);
421 acc_loads += get_entity_acc_estimated_n_loads (ov_mem);
422 acc_writes += get_entity_acc_estimated_n_stores(ov_mem);
424 set_entity_acc_estimated_n_loads (mem, acc_loads);
425 set_entity_acc_estimated_n_stores(mem, acc_writes);
428 /* Deal with type numbers. */
429 double inst = get_type_estimated_n_instances(tp);
430 for (i = 0; i < n_subtypes; ++i) {
431 type *stp = get_class_subtype(tp, i);
432 inst += get_type_acc_estimated_n_instances(stp);
434 set_type_acc_estimated_n_instances(tp, inst);
436 mark_type_visited(tp);
439 void accumulate_temperatures(void) {
440 int i, n_types = get_irp_n_types();
441 free_accumulated_temperatures();
443 inc_master_type_visited();
444 for (i = 0; i < n_types; ++i) {
445 type *tp = get_irp_type(i);
446 if (is_Class_type(tp)) { /* For others there is nothing to accumulate. */
447 int j, n_subtypes = get_class_n_subtypes(tp);
448 int has_unmarked_subtype = false;
449 for (j = 0; j < n_subtypes && !has_unmarked_subtype; ++j) {
450 type *stp = get_class_subtype(tp, j);
451 if (type_not_visited(stp)) has_unmarked_subtype = true;
454 if (!has_unmarked_subtype)
459 irp->temperature_state = temperature_consistent;
463 void free_accumulated_temperatures(void) {
464 if (temperature_set) del_set(temperature_set);
465 temperature_set = NULL;
466 irp->temperature_state = temperature_none;
469 /* ------------------------------------------------------------------------- */
471 /* ------------------------------------------------------------------------- */
473 int is_jack_rts_name(ident *name) {
475 if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
476 if (id_is_prefix(new_id_from_str("["), name)) return 1;
477 if (id_is_prefix(new_id_from_str("gnu/"), name)) return 1;
478 if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
479 if (id_is_prefix(new_id_from_str("CStringToCoreString"), name)) return 1;
485 int is_jack_rts_class(type *t) {
486 ident *name = get_type_ident(t);
487 return is_jack_rts_name(name);
490 #include "entity_t.h" // for the assertion.
492 int is_jack_rts_entity(entity *e) {
496 name = get_entity_ld_ident(e);
498 return is_jack_rts_name(name);