X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Ffield_temperature.c;h=01352b58316eabd7e6e5fb9bf13d7ea9341a7683;hb=1ce3e22f3329f4186b264e1ca441fe5f8e45aa7f;hp=9afc3e6d82cd83551a0359255a1139a6f01b71dc;hpb=bd919edb2165a3b63a0e111acc14021c021733ce;p=libfirm

diff --git a/ir/ana/field_temperature.c b/ir/ana/field_temperature.c
index 9afc3e6d8..01352b583 100644
--- a/ir/ana/field_temperature.c
+++ b/ir/ana/field_temperature.c
@@ -1,22 +1,46 @@
 /*
- * Project:     libFIRM
- * File name:   ir/ana/field_temperature.c
- * Purpose:     Compute an estimate of field temperature, i.e., field access heuristic.
- * Author:      Goetz Lindenmaier
- * Modified by:
- * Created:     21.7.2004
- * CVS-ID:      $Id$
- * Copyright:   (c) 2004 Universität Karlsruhe
- * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
  */
 
+/**
+ * @file
+ * @brief     Compute an estimate of field temperature, i.e., field access heuristic.
+ * @author    Goetz Lindenmaier
+ * @date      21.7.2004
+ * @version   $Id$
+ */
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#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 "entity_t.h"
 #include "irgwalk.h"
+#include "error.h"
 
 #include "array.h"
 
@@ -24,242 +48,357 @@
 /* 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                                              */
+/*   Access routines for irnodes                                               */
 /* *************************************************************************** */
 
-int get_entity_n_accesses(entity *ent) {
-  assert(ent && is_entity(ent));
-
-  if (!ent->accesses) { ent->accesses = NEW_ARR_F(ir_node *, 0); }
+/* The entities that can be accessed by this Sel node. */
+int get_Sel_n_accessed_entities(ir_node *sel) {
+  (void) sel;
+  return 1;
+}
 
-  return ARR_LEN(ent->accesses);
+ir_entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
+  (void) pos;
+  return get_Sel_entity(sel);
 }
 
-ir_node *get_entity_access(entity *ent, int pos) {
-  assert(0 <= pos && pos < get_entity_n_accesses(ent));
+/* *************************************************************************** */
+/* The heuristic                                                               */
+/* *************************************************************************** */
 
-  return ent->accesses[pos];
+int get_irn_loop_call_depth(ir_node *n) {
+  ir_graph *irg = get_irn_irg(n);
+  return get_irg_loop_depth(irg);
 }
 
-void add_entity_access(entity *ent, ir_node *n) {
-  assert(ent && is_entity(ent));
-  assert(n && is_ir_node(n));
-
-  if (!ent->accesses) ent->accesses = NEW_ARR_F(ir_node *, 0);
+int get_irn_cfloop_depth(ir_node *n) {
+  ir_loop *l = get_irn_loop(get_nodes_block(n));
+  if (l)
+    return get_loop_depth(l);
+  else
+    return 0;
+}
 
-  ARR_APP1(ir_node *, ent->accesses, n);
+int get_irn_recursion_depth(ir_node *n) {
+  ir_graph *irg = get_irn_irg(n);
+  return get_irg_recursion_depth(irg);
 }
 
-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));
 
-  ent->accesses[pos] = n;
+/**   @@@ 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_cfloop_depth(n);
+  int recursion_depth = get_irn_recursion_depth(n);
+
+  return loop_call_depth + loop_depth + recursion_depth;
 }
 
 
 /* *************************************************************************** */
-/*   Access routines for types                                                 */
+/* The 2. heuristic                                                            */
 /* *************************************************************************** */
 
-/** 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);
+static int default_recursion_weight = 5;
+
+/* The final evaluation of a node.  In this function we can
+   adapt the heuristic.  Combine execution frequency with
+   recursion depth.
+   @@@ the second version of the heuristic.
+
+   Return 0 if the node is neither in a loop nor in a recursion.  */
+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    = 0;
+
+#if 0
+  if (get_irn_recursion_depth(n) == 0 &&
+      get_irn_loop_depth(n) == 0 &&
+      get_irg_method_loop_depth(get_irn_irg(n)) == 0)
+    return 0;
+#else
+  if (get_weighted_loop_depth(n) == 0) return 0;
+#endif
+
+  if (rec_depth) cost_rec = pow(default_recursion_weight, rec_depth);
+  return cost_loop*(cost_method + cost_rec);
 }
 
-/** 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));
+double get_type_estimated_n_instances(ir_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;
+}
 
-  return tp->allocations[pos];
+double get_type_estimated_mem_consumption_bytes(ir_type *tp) {
+  (void) tp;
+  assert(0);
+  return 0.0;
 }
 
-void add_type_allocation(type *tp, ir_node *n) {
-  assert(tp && is_type(tp));
-  assert(n && is_ir_node(n));
+int get_type_estimated_n_fields(ir_type *tp) {
+  int s = 0;
+  switch(get_type_tpop_code(tp)) {
 
-  if (!tp->allocations) tp->allocations = NEW_ARR_F(ir_node *, 0);
+  case tpo_primitive:
+  case tpo_pointer:
+  case tpo_enumeration:
+    s = 1;
+    break;
 
-  ARR_APP1(ir_node *, tp->allocations, n);
-}
+  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) {
+      ir_entity *mem = get_compound_member(tp, i);
+      if (get_entity_allocation(mem) == allocation_automatic) {
+	s += get_type_estimated_n_fields(get_entity_type(mem));
+      }
+    }
+  } 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;
 
-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));
+  default:
+    panic("Unsupported type in get_type_estimated_n_fields %+F", tp);
+  }
 
-  tp->allocations[pos] = n;
+  return s;
 }
 
+int get_type_estimated_size_bytes(ir_type *tp) {
+  int s = 0;
 
+  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;
 
-/* *************************************************************************** */
-/*   Access routines for irnodes                                               */
-/* *************************************************************************** */
+  case tpo_class:
+    s = get_mode_size_bytes(mode_P_data); /* dispatch pointer */
+    /* fall through */
+  case tpo_struct: {
+    int i, n_mem = get_compound_n_members(tp);
+    for (i = 0; i < n_mem; ++i) {
+      ir_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 */
+    }
+  } 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;
+  }
 
-/* The entities that can be accessed by this Sel node. */
-int get_Sel_n_accessed_entities(ir_node *sel) {
-  return 1;
+  default: assert(0);
+  }
+
+  return s;
 }
 
-entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
-  return get_Sel_entity(sel);
+double get_type_estimated_n_casts(ir_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;
 }
 
-/* An addr node is a SymConst or a Sel. */
-int get_addr_n_entities(ir_node *addr) {
-  int n_ents;
+double get_class_estimated_n_upcasts(ir_type *clss) {
+  double n_instances = 0;
+  int i, j, n_casts, n_pointertypes;
 
-  switch (get_irn_opcode(addr)) {
-  case iro_Sel:
-    /* Treat jack array sels? */
-    n_ents = get_Sel_n_accessed_entities(addr);
-    break;
-  case iro_SymConst:
-    if (get_SymConst_kind(addr) == symconst_addr_ent) {
-      n_ents = 1;
-      break;
-    }
-  default:
-    //assert(0 && "unexpected address expression");
-    n_ents = 0;
+  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);
   }
 
-  return n_ents;
+  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;
 }
 
-/* An addr node is a SymConst or a Sel. */
-entity *get_addr_entity(ir_node *addr, int pos) {
-  entity *ent;
+double get_class_estimated_n_downcasts(ir_type *clss) {
+  double n_instances = 0;
+  int i, j, n_casts, n_pointertypes;
 
-  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);
-    break;
-  case iro_SymConst:
-    if (get_SymConst_kind(addr) == symconst_addr_ent) {
-      assert(pos == 0);
-      ent = get_SymConst_entity(addr);
-      break;
-    }
-  default:
-    ent = NULL;
+  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_downcast(cast))
+      n_instances += get_irn_final_cost(cast);
   }
 
-  return ent;
+  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;
 }
 
 
-int get_irn_loop_call_depth(ir_node *n) {
-  ir_graph *irg = get_irn_irg(n);
-  return get_irg_loop_depth(irg);
+double get_class_estimated_dispatch_writes(ir_type *clss) {
+  return get_type_estimated_n_instances(clss);
 }
 
-int get_irn_loop_depth(ir_node *n) {
-  get_loop_depth(get_irn_loop(get_nodes_block(n)));
+/** Returns the number of reads of the dispatch pointer. */
+double get_class_estimated_dispatch_reads (ir_type *clss) {
+  int i, n_mems = get_class_n_members(clss);
+  double n_calls = 0;
+  for (i = 0; i < n_mems; ++i) {
+    ir_entity *mem = get_class_member(clss, i);
+    n_calls += get_entity_estimated_n_dyncalls(mem);
+  }
+  return n_calls;
 }
 
-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_dyncalls(ir_type *clss) {
+  return get_class_estimated_dispatch_reads(clss) +
+         get_class_estimated_dispatch_writes(clss);
 }
 
-
-/* *************************************************************************** */
-/* 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;
+double get_entity_estimated_n_loads(ir_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;
 }
 
-/* *************************************************************************** */
-/* The analyses                                                                */
-/* *************************************************************************** */
-
-void init_field_temperature(void) {
-  assert(!unrecognized_access);
-  unrecognized_access = NEW_ARR_F(ir_node *, 0);
+double get_entity_estimated_n_stores(ir_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;
 }
 
+/* @@@ Should we evaluate the callee array?  */
+double get_entity_estimated_n_calls(ir_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)
 
-void chain_accesses(ir_node *n, void *env) {
-  int i, n_ents;
-  ir_node *addr;
-
-  if (get_irn_op(n) == op_Alloc) {
-    add_type_allocation(get_Alloc_type(n), n);
-    return;
+      n_calls += get_irn_final_cost(acc);
   }
+  return n_calls;
+}
 
-  if (is_memop(n)) {
-    addr = get_memop_ptr(n);
-  } else {
-    return;
-  }
+double get_entity_estimated_n_dyncalls(ir_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 (is_Call(acc) && is_Sel(get_Call_ptr(acc))) {
+      n_calls += get_irn_final_cost(acc);
+
+    /* MemOp->Sel combination for static, overwritten entities */
+    } else if (is_memop(acc) && is_Sel(get_memop_ptr(acc))) {
+      ir_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;
 }
 
+#if 0
+/* Move this to the jack compiler */
 
-/* compute the field temperature. */
-void compute_field_temperature(void) {
+/* ------------------------------------------------------------------------- */
+/* Auxiliary                                                                 */
+/* ------------------------------------------------------------------------- */
 
-  int i, n_irgs = get_irp_n_irgs();
+int is_jack_rts_name(ident *name) {
+  if (id_is_suffix(new_id_from_str("Exception"), name)) return 1;
+  if (id_is_suffix(new_id_from_str("Throwable"), name)) return 1;
+  if (id_is_suffix(new_id_from_str("Error"),     name)) return 1;
 
-  init_field_temperature();
+  return  0;
 
-  for (i=0; i < n_irgs; i++) {
-    current_ir_graph = get_irp_irg(i);
-    irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL);
-  }
-}
+  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("java/"), name)) return 1;
+  if (id_is_prefix(new_id_from_str("CStringToCoreString"), name)) return 1;
 
-/* free occupied memory, reset */
-void free_field_temperature(void) {
-  DEL_ARR_F(unrecognized_access);
-  unrecognized_access = NULL;
+  return 0;
 }
 
 
+int is_jack_rts_class(ir_type *t) {
+  ident *name = get_type_ident(t);
+  return is_jack_rts_name(name);
+}
 
-/* *************************************************************************** */
-/* Auxiliary                                                                   */
-/* *************************************************************************** */
-
+#include "entity_t.h"  // for the assertion.
 
-int is_jack_rts_class(type *t) {
-  ident *name = get_type_ident(t);
+int is_jack_rts_entity(ir_entity *e) {
+  ident *name;
 
-  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("java/"), name)) return 1;
+  assert(e->ld_name);
+  name = get_entity_ld_ident(e);
 
-  return 0;
+  return is_jack_rts_name(name);
 }
+
+#endif /* if 0 */