* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
+#include <math.h>
+
#include "field_temperature.h"
+#include "trouts.h"
+#include "execution_frequency.h"
+
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irprog_t.h"
#include "irgwalk.h"
#include "array.h"
+#include "set.h"
+#include "hashptr.h"
+
/* *************************************************************************** */
/* initialize, global variables. */
/* *************************************************************************** */
-/* A list of Load and Store operations that have no analyseable address. */
-static ir_node **unrecognized_access = NULL;
-
-static void add_unrecognized_access(ir_node *n) {
- ARR_APP1(ir_node *, unrecognized_access, n);
-}
-
/* *************************************************************************** */
-/* Access routines for entities */
+/* Another hash table, this time containing temperature values. */
/* *************************************************************************** */
-int get_entity_n_accesses(entity *ent) {
- assert(ent && is_entity(ent));
+typedef struct {
+ firm_kind *kind; /* An entity or type. */
+ double val1;
+} temperature_tp;
- if (!ent->accesses) { ent->accesses = NEW_ARR_F(ir_node *, 0); }
+/* We use this set for all types and entities. */
+static set *temperature_set = NULL;
- return ARR_LEN(ent->accesses);
+static int temp_cmp(const void *e1, const void *e2, size_t size) {
+ temperature_tp *ef1 = (temperature_tp *)e1;
+ temperature_tp *ef2 = (temperature_tp *)e2;
+ return (ef1->kind != ef2->kind);
}
-ir_node *get_entity_access(entity *ent, int pos) {
- assert(0 <= pos && pos < get_entity_n_accesses(ent));
-
- return ent->accesses[pos];
+static INLINE unsigned int tem_hash(void *e) {
+ void *v = (void *) ((temperature_tp *)e)->kind;
+ return HASH_PTR(v);
}
-void add_entity_access(entity *ent, ir_node *n) {
- assert(ent && is_entity(ent));
- assert(n && is_ir_node(n));
+double get_entity_acc_estimated_n_loads (entity *ent) {
+ return 0;
+}
+double get_entity_acc_estimated_n_stores(entity *ent) {
+ return 0;
+}
- if (!ent->accesses) ent->accesses = NEW_ARR_F(ir_node *, 0);
+void set_entity_acc_estimated_n_loads (entity *ent, double val) {
+}
+void set_entity_acc_estimated_n_stores(entity *ent, double val) {
+}
- ARR_APP1(ir_node *, ent->accesses, n);
+double get_type_acc_estimated_n_instances(type *tp) {
+ return 0;
+}
+void set_type_acc_estimated_n_instances(type *tp, double val) {
}
-void set_entity_access(entity *ent, int pos, ir_node *n) {
- assert(0 <= pos && pos < get_entity_n_accesses(ent));
- assert(n && is_ir_node(n));
+/*
+static INLINE void set_region_exec_freq(void *reg, double freq) {
+ reg_exec_freq ef;
+ ef.reg = reg;
+ ef.freq = freq;
+ set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
+}
- ent->accesses[pos] = n;
+INLINE double get_region_exec_freq(void *reg) {
+ reg_exec_freq ef, *found;
+ ef.reg = reg;
+ assert(exec_freq_set);
+ found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef));
+ if (found)
+ return found->freq;
+ else
+ return 0;
}
+*/
/* *************************************************************************** */
-/* Access routines for types */
+/* Access routines for irnodes */
/* *************************************************************************** */
-/** Number of Alloc nodes that create an instance of this type */
-int get_type_n_allocations(type *tp) {
- assert(tp && is_type(tp));
-
- if (!tp->allocations) { tp->allocations = NEW_ARR_F(ir_node *, 0); }
-
- return ARR_LEN(tp->allocations);
+/* The entities that can be accessed by this Sel node. */
+int get_Sel_n_accessed_entities(ir_node *sel) {
+ return 1;
}
-/** Alloc node that create an instance of this type */
-ir_node *get_type_allocation(type *tp, int pos) {
- assert(0 <= pos && pos < get_type_n_allocations(tp));
-
- return tp->allocations[pos];
+entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
+ return get_Sel_entity(sel);
}
-void add_type_allocation(type *tp, ir_node *n) {
- assert(tp && is_type(tp));
- assert(n && is_ir_node(n));
-
- if (!tp->allocations) tp->allocations = NEW_ARR_F(ir_node *, 0);
+/* *************************************************************************** */
+/* The heuristic */
+/* *************************************************************************** */
- ARR_APP1(ir_node *, tp->allocations, n);
+int get_irn_loop_call_depth(ir_node *n) {
+ ir_graph *irg = get_irn_irg(n);
+ return get_irg_loop_depth(irg);
}
-void set_type_allocation(type *tp, int pos, ir_node *n) {
- assert(0 <= pos && pos < get_type_n_allocations(tp));
- assert(n && is_ir_node(n));
+int get_irn_loop_depth(ir_node *n) {
+ ir_loop *l = get_irn_loop(get_nodes_block(n));
+ if (l)
+ return get_loop_depth(l);
+ else
+ return 0;
+}
- tp->allocations[pos] = n;
+int get_irn_recursion_depth(ir_node *n) {
+ ir_graph *irg = get_irn_irg(n);
+ return get_irg_recursion_depth(irg);
}
+/** @@@ the second version of the heuristic. */
+int get_weighted_loop_depth(ir_node *n) {
+ int loop_call_depth = get_irn_loop_call_depth(n);
+ int loop_depth = get_irn_loop_depth(n);
+ int recursion_depth = get_irn_recursion_depth(n);
+
+ return loop_call_depth + loop_depth + recursion_depth;
+}
/* *************************************************************************** */
-/* Access routines for irnodes */
+/* The 2. heuristic */
/* *************************************************************************** */
-/* The entities that can be accessed by this Sel node. */
-int get_Sel_n_accessed_entities(ir_node *sel) {
- return 1;
+static int default_recursion_weight = 5;
+
+
+/* The final evaluation of a node. In this function we can
+ adapt the heuristic. Combine execution freqency with
+ recursion depth.
+ @@@ the second version of the heuristic. */
+double get_irn_final_cost(ir_node *n) {
+ double cost_loop = get_irn_exec_freq(n);
+ double cost_method = get_irg_method_execution_frequency(get_irn_irg(n));
+ int rec_depth = get_irn_recursion_depth(n);
+ double cost_rec = pow(default_recursion_weight, rec_depth);
+ return cost_loop*(cost_method + cost_rec);
}
-entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
- return get_Sel_entity(sel);
+double get_type_estimated_n_instances(type *tp) {
+ int i, n_allocs = get_type_n_allocs(tp);
+ double n_instances = 0;
+ for (i = 0; i < n_allocs; ++i) {
+ ir_node *alloc = get_type_alloc(tp, i);
+ n_instances += get_irn_final_cost(alloc);
+ }
+ return n_instances;
+}
+
+double get_type_estimated_mem_consumption_bytes(type *tp) {
+ assert(0);
+ return 0.0;
}
-/* An addr node is a SymConst or a Sel. */
-int get_addr_n_entities(ir_node *addr) {
- int n_ents;
+int get_type_estimated_n_fields(type *tp) {
+ int s = 0;
+ switch(get_type_tpop_code(tp)) {
- switch (get_irn_opcode(addr)) {
- case iro_Sel:
- /* Treat jack array sels? */
- n_ents = get_Sel_n_accessed_entities(addr);
+ case tpo_primitive:
+ case tpo_pointer:
+ case tpo_enumeration:
+ s = 1;
break;
- case iro_SymConst:
- if (get_SymConst_kind(addr) == symconst_addr_ent) {
- n_ents = 1;
- break;
+
+ case tpo_class:
+ s = 1; /* dispatch pointer */
+ /* fall through */
+ case tpo_struct: {
+ int i, n_mem = get_compound_n_members(tp);
+ for (i = 0; i < n_mem; ++i) {
+ entity *mem = get_compound_member(tp, i);
+ if (get_entity_allocation(mem) == allocation_automatic) {
+ s += get_type_estimated_n_fields(get_entity_type(mem));
+ }
}
- default:
- //assert(0 && "unexpected address expression");
- n_ents = 0;
+ } break;
+
+ case tpo_array: {
+ long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
+ assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
+ if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
+ (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const) ) {
+ n_elt = get_array_upper_bound_int(tp, 0) - get_array_upper_bound_int(tp, 0);
+ }
+ s = n_elt;
+ } break;
+
+ default: DDMT(tp); assert(0);
}
- return n_ents;
+ return s;
}
-/* An addr node is a SymConst or a Sel. */
-entity *get_addr_entity(ir_node *addr, int pos) {
- entity *ent;
+int get_type_estimated_size_bytes(type *tp) {
+ int s = 0;
- switch (get_irn_opcode(addr)) {
- case iro_Sel:
- /* Treat jack array sels? */
- assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
- ent = get_Sel_accessed_entity(addr, pos);
+ switch(get_type_tpop_code(tp)) {
+
+ case tpo_primitive:
+ case tpo_pointer:
+ case tpo_enumeration:
+ s = get_mode_size_bytes(get_type_mode(tp));
break;
- case iro_SymConst:
- if (get_SymConst_kind(addr) == symconst_addr_ent) {
- assert(pos == 0);
- ent = get_SymConst_entity(addr);
- break;
+
+ case tpo_class:
+ s = get_mode_size_bytes(mode_P_mach); /* dispatch pointer */
+ /* fall through */
+ case tpo_struct: {
+ int i, n_mem = get_compound_n_members(tp);
+ for (i = 0; i < n_mem; ++i) {
+ entity *mem = get_compound_member(tp, i);
+ s += get_type_estimated_size_bytes(get_entity_type(mem));
+
+ if (get_entity_allocation(mem) == allocation_automatic) {
+ } /* allocation_automatic */
}
- default:
- ent = NULL;
+ } break;
+
+ case tpo_array: {
+ int elt_s = get_type_estimated_size_bytes(get_array_element_type(tp));
+ long n_elt = DEFAULT_N_ARRAY_ELEMENTS;
+ assert(get_array_n_dimensions(tp) == 1 && "other not implemented");
+ if ((get_irn_op(get_array_lower_bound(tp, 0)) == op_Const) &&
+ (get_irn_op(get_array_upper_bound(tp, 0)) == op_Const) ) {
+ n_elt = get_array_upper_bound_int(tp, 0) - get_array_lower_bound_int(tp, 0);
+ }
+ s = n_elt * elt_s;
+ break;
}
- return ent;
-}
-
+ default: DDMT(tp); assert(0);
+ }
-int get_irn_loop_call_depth(ir_node *n) {
- ir_graph *irg = get_irn_irg(n);
- return get_irg_loop_depth(irg);
+ return s;
}
-int get_irn_loop_depth(ir_node *n) {
- return get_loop_depth(get_irn_loop(get_nodes_block(n)));
+double get_type_estimated_n_casts(type *tp) {
+ int i, n_casts = get_type_n_casts(tp);
+ double n_instances = 0;
+ for (i = 0; i < n_casts; ++i) {
+ ir_node *cast = get_type_cast(tp, i);
+ n_instances += get_irn_final_cost(cast);
+ }
+ return n_instances;
}
-int get_irn_recursion_depth(ir_node *n) {
- ir_graph *irg = get_irn_irg(n);
- return get_irg_recursion_depth(irg);
+double get_class_estimated_n_upcasts(type *clss) {
+ double n_instances = 0;
+ int i, j, n_casts, n_pointertypes;
+
+ n_casts = get_type_n_casts(clss);
+ for (i = 0; i < n_casts; ++i) {
+ ir_node *cast = get_type_cast(clss, i);
+ if (get_irn_opcode(cast) != iro_Cast) continue; /* Could be optimized away. */
+
+ if (is_Cast_upcast(cast))
+ n_instances += get_irn_final_cost(cast);
+ }
+
+ n_pointertypes = get_type_n_pointertypes_to(clss);
+ for (j = 0; j < n_pointertypes; ++j) {
+ n_instances += get_class_estimated_n_upcasts(get_type_pointertype_to(clss, j));
+ }
+
+ return n_instances;
}
+double get_class_estimated_n_downcasts(type *clss) {
+ double n_instances = 0;
+ int i, j, n_casts, n_pointertypes;
-/* *************************************************************************** */
-/* The heuristic */
-/* *************************************************************************** */
+ n_casts = get_type_n_casts(clss);
+ for (i = 0; i < n_casts; ++i) {
+ ir_node *cast = get_type_cast(clss, i);
+ if (get_irn_opcode(cast) != iro_Cast) continue; /* Could be optimized away. */
-int get_weighted_loop_depth(ir_node *n) {
- int loop_call_depth = get_irn_loop_call_depth(n);
- int loop_depth = get_irn_loop_depth(n);
- int recursion_depth = get_irn_recursion_depth(n);
+ if (is_Cast_downcast(cast))
+ n_instances += get_irn_final_cost(cast);
+ }
- return loop_call_depth + loop_depth + recursion_depth;
+ n_pointertypes = get_type_n_pointertypes_to(clss);
+ for (j = 0; j < n_pointertypes; ++j) {
+ n_instances += get_class_estimated_n_downcasts(get_type_pointertype_to(clss, j));
+ }
+
+ return n_instances;
}
-/* *************************************************************************** */
-/* The analyses */
-/* *************************************************************************** */
-void init_field_temperature(void) {
- assert(!unrecognized_access);
- unrecognized_access = NEW_ARR_F(ir_node *, 0);
+double get_class_estimated_dispatch_writes(type *clss) {
+ return get_type_estimated_n_instances(clss);
}
+/** Returns the number of reads of the dispatch pointer. */
+double get_class_estimated_dispatch_reads (type *clss) {
+ int i, n_mems = get_class_n_members(clss);
+ double n_calls = 0;
+ for (i = 0; i < n_mems; ++i) {
+ entity *mem = get_class_member(clss, i);
+ n_calls += get_entity_estimated_n_dyncalls(mem);
+ }
+ return n_calls;
+}
+
+double get_class_estimated_n_dyncalls(type *clss) {
+ return get_class_estimated_dispatch_reads(clss) +
+ get_class_estimated_dispatch_writes(clss);
+}
-void chain_accesses(ir_node *n, void *env) {
- int i, n_ents;
- ir_node *addr;
+double get_entity_estimated_n_loads(entity *ent) {
+ int i, n_acc = get_entity_n_accesses(ent);
+ double n_loads = 0;
+ for (i = 0; i < n_acc; ++i) {
+ ir_node *acc = get_entity_access(ent, i);
+ if (get_irn_op(acc) == op_Load) {
+ n_loads += get_irn_final_cost(acc);
+ }
+ }
+ return n_loads;
+}
- if (get_irn_op(n) == op_Alloc) {
- add_type_allocation(get_Alloc_type(n), n);
- return;
+double get_entity_estimated_n_stores(entity *ent) {
+ int i, n_acc = get_entity_n_accesses(ent);
+ double n_stores = 0;
+ for (i = 0; i < n_acc; ++i) {
+ ir_node *acc = get_entity_access(ent, i);
+ if (get_irn_op(acc) == op_Store)
+ n_stores += get_irn_final_cost(acc);
}
+ return n_stores;
+}
- if (is_memop(n)) {
- addr = get_memop_ptr(n);
- } else if (get_irn_op(n) == op_Call) {
- addr = get_Call_ptr(n);
- if (get_irn_op(addr) != op_Sel) return; /* Sels before Calls mean a Load / polymorphic Call. */
- } else {
- return;
+/* @@@ Should we evaluate the callee array? */
+double get_entity_estimated_n_calls(entity *ent) {
+ int i, n_acc = get_entity_n_accesses(ent);
+ double n_calls = 0;
+ for (i = 0; i < n_acc; ++i) {
+ ir_node *acc = get_entity_access(ent, i);
+ if (get_irn_op(acc) == op_Call)
+
+ n_calls += get_irn_final_cost(acc);
}
+ return n_calls;
+}
+
+double get_entity_estimated_n_dyncalls(entity *ent) {
+ int i, n_acc = get_entity_n_accesses(ent);
+ double n_calls = 0;
+ for (i = 0; i < n_acc; ++i) {
+ ir_node *acc = get_entity_access(ent, i);
+
+ /* Call->Sel(ent) combination */
+ if ((get_irn_op(acc) == op_Call) &&
+ (get_irn_op(get_Call_ptr(acc)) == op_Sel)) {
+ n_calls += get_irn_final_cost(acc);
+
+ /* MemOp->Sel combination for static, overwritten entities */
+ } else if (is_memop(acc) && (get_irn_op(get_memop_ptr(acc)) == op_Sel)) {
+ entity *ent = get_Sel_entity(get_memop_ptr(acc));
+ if (is_Class_type(get_entity_owner(ent))) {
+ /* We might call this for inner entities in compounds. */
+ if (get_entity_n_overwrites(ent) > 0 ||
+ get_entity_n_overwrittenby(ent) > 0) {
+ n_calls += get_irn_final_cost(acc);
+ }
+ }
+ }
- n_ents = get_addr_n_entities(addr);
- for (i = 0; i < n_ents; ++i) {
- entity *ent = get_addr_entity(addr, i);
- if (ent)
- add_entity_access(ent, n);
- else
- add_unrecognized_access(n);
}
+ return n_calls;
}
+/* ------------------------------------------------------------------------- */
+/* Accumulate information in the type hierarchy. */
+/* This should go to co_read_profiling.c */
+/* ------------------------------------------------------------------------- */
-/* compute the field temperature. */
-void compute_field_temperature(void) {
+static void acc_temp (type *tp) {
+ int i, n_subtypes, n_members;
+ double inst;
- int i, n_irgs = get_irp_n_irgs();
+ assert(is_Class_type(tp));
- init_field_temperature();
+ /* Recursive descend. */
+ n_subtypes = get_class_n_subtypes(tp);
+ for (i = 0; i < n_subtypes; ++i) {
+ type *stp = get_class_subtype(tp, i);
+ if (type_not_visited(stp)) {
+ acc_temp(stp);
+ }
+ }
- for (i=0; i < n_irgs; i++) {
- current_ir_graph = get_irp_irg(i);
- irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL);
+ /* Deal with entity numbers. */
+ n_members = get_class_n_members(tp);
+ for (i = 0; i < n_members; ++i) {
+ entity *mem = get_class_member(tp, i);
+ double acc_loads = get_entity_estimated_n_loads (mem);
+ double acc_writes = get_entity_estimated_n_stores(mem);
+ int j, n_ov = get_entity_n_overwrittenby(mem);
+ for (j = 0; j < n_ov; ++j) {
+ entity *ov_mem = get_entity_overwrittenby(mem, j);
+ acc_loads += get_entity_acc_estimated_n_loads (ov_mem);
+ acc_writes += get_entity_acc_estimated_n_stores(ov_mem);
+ }
+ set_entity_acc_estimated_n_loads (mem, acc_loads);
+ set_entity_acc_estimated_n_stores(mem, acc_writes);
}
-}
-/* free occupied memory, reset */
-void free_field_temperature(void) {
- DEL_ARR_F(unrecognized_access);
- unrecognized_access = NULL;
+ /* Deal with type numbers. */
+ inst = get_type_estimated_n_instances(tp);
+ for (i = 0; i < n_subtypes; ++i) {
+ type *stp = get_class_subtype(tp, i);
+ inst += get_type_acc_estimated_n_instances(stp);
+ }
+ set_type_acc_estimated_n_instances(tp, inst);
+
+ mark_type_visited(tp);
}
+void accumulate_temperatures(void) {
+ int i, n_types = get_irp_n_types();
+ free_accumulated_temperatures();
+
+ inc_master_type_visited();
+ for (i = 0; i < n_types; ++i) {
+ type *tp = get_irp_type(i);
+ if (is_Class_type(tp)) { /* For others there is nothing to accumulate. */
+ int j, n_subtypes = get_class_n_subtypes(tp);
+ int has_unmarked_subtype = false;
+ for (j = 0; j < n_subtypes && !has_unmarked_subtype; ++j) {
+ type *stp = get_class_subtype(tp, j);
+ if (type_not_visited(stp)) has_unmarked_subtype = true;
+ }
+
+ if (!has_unmarked_subtype)
+ acc_temp(tp);
+ }
+ }
+ irp->temperature_state = temperature_consistent;
+}
-/* *************************************************************************** */
-/* Auxiliary */
-/* *************************************************************************** */
+void free_accumulated_temperatures(void) {
+ if (temperature_set) del_set(temperature_set);
+ temperature_set = NULL;
+ irp->temperature_state = temperature_none;
+}
-int is_jack_rts_class(type *t) {
- ident *name = get_type_ident(t);
+/* ------------------------------------------------------------------------- */
+/* Auxiliary */
+/* ------------------------------------------------------------------------- */
+int is_jack_rts_name(ident *name) {
+ return 0;
if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
- if (id_is_prefix(new_id_from_str("["), name)) return 1;
- if (id_is_prefix(new_id_from_str("gnu/"), name)) return 1;
+ if (id_is_prefix(new_id_from_str("["), name)) return 1;
+ if (id_is_prefix(new_id_from_str("gnu/"), name)) return 1;
if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
+ if (id_is_prefix(new_id_from_str("CStringToCoreString"), name)) return 1;
return 0;
}
+
+
+int is_jack_rts_class(type *t) {
+ ident *name = get_type_ident(t);
+ return is_jack_rts_name(name);
+}
+
+#include "entity_t.h" // for the assertion.
+
+int is_jack_rts_entity(entity *e) {
+ ident *name;
+
+ assert(e->ld_name);
+ name = get_entity_ld_ident(e);
+
+ return is_jack_rts_name(name);
+}