nsz Git - libfirm/blob - ir/ana/field_temperature.c

   1 /*
   2  * Project:     libFIRM
   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
   6  * Modified by:
   7  * Created:     21.7.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #include "field_temperature.h"
  14
  15 #include "irnode_t.h"
  16 #include "irgraph_t.h"
  17 #include "irprog_t.h"
  18 #include "entity_t.h"
  19 #include "irgwalk.h"
  20
  21 #include "array.h"
  22
  23 /* *************************************************************************** */
  24 /* initialize, global variables.                                               */
  25 /* *************************************************************************** */
  26
  27 /* A list of Load and Store operations that have no analyseable address. */
  28 static ir_node **unrecognized_access = NULL;
  29
  30 static void add_unrecognized_access(ir_node *n) {
  31   ARR_APP1(ir_node *, unrecognized_access, n);
  32 }
  33
  34 /* *************************************************************************** */
  35 /*   Access routines for entities                                              */
  36 /* *************************************************************************** */
  37
  38 int get_entity_n_accesses(entity *ent) {
  39   assert(ent && is_entity(ent));
  40
  41   if (!ent->accesses) { ent->accesses = NEW_ARR_F(ir_node *, 0); }
  42
  43   return ARR_LEN(ent->accesses);
  44 }
  45
  46 ir_node *get_entity_access(entity *ent, int pos) {
  47   assert(0 <= pos && pos < get_entity_n_accesses(ent));
  48
  49   return ent->accesses[pos];
  50 }
  51
  52 void add_entity_access(entity *ent, ir_node *n) {
  53   assert(ent && is_entity(ent));
  54   assert(n && is_ir_node(n));
  55
  56   if (!ent->accesses) ent->accesses = NEW_ARR_F(ir_node *, 0);
  57
  58   ARR_APP1(ir_node *, ent->accesses, n);
  59 }
  60
  61 void set_entity_access(entity *ent, int pos, ir_node *n) {
  62   assert(0 <= pos && pos < get_entity_n_accesses(ent));
  63   assert(n && is_ir_node(n));
  64
  65   ent->accesses[pos] = n;
  66 }
  67
  68
  69 /* *************************************************************************** */
  70 /*   Access routines for types                                                 */
  71 /* *************************************************************************** */
  72
  73 /** Number of Alloc nodes that create an instance of this type */
  74 int get_type_n_allocations(type *tp) {
  75   assert(tp && is_type(tp));
  76
  77   if (!tp->allocations) { tp->allocations = NEW_ARR_F(ir_node *, 0); }
  78
  79   return ARR_LEN(tp->allocations);
  80 }
  81
  82 /** Alloc node that create an instance of this type */
  83 ir_node *get_type_allocation(type *tp, int pos) {
  84   assert(0 <= pos && pos < get_type_n_allocations(tp));
  85
  86   return tp->allocations[pos];
  87 }
  88
  89 void add_type_allocation(type *tp, ir_node *n) {
  90   assert(tp && is_type(tp));
  91   assert(n && is_ir_node(n));
  92
  93   if (!tp->allocations) tp->allocations = NEW_ARR_F(ir_node *, 0);
  94
  95   ARR_APP1(ir_node *, tp->allocations, n);
  96 }
  97
  98 void set_type_allocation(type *tp, int pos, ir_node *n) {
  99   assert(0 <= pos && pos < get_type_n_allocations(tp));
 100   assert(n && is_ir_node(n));
 101
 102   tp->allocations[pos] = n;
 103 }
 104
 105
 106
 107
 108 /* *************************************************************************** */
 109 /*   Access routines for irnodes                                               */
 110 /* *************************************************************************** */
 111
 112 /* The entities that can be accessed by this Sel node. */
 113 int get_Sel_n_accessed_entities(ir_node *sel) {
 114   return 1;
 115 }
 116
 117 entity *get_Sel_accessed_entity(ir_node *sel, int pos) {
 118   return get_Sel_entity(sel);
 119 }
 120
 121 /* An addr node is a SymConst or a Sel. */
 122 int get_addr_n_entities(ir_node *addr) {
 123   int n_ents;
 124
 125   switch (get_irn_opcode(addr)) {
 126   case iro_Sel:
 127     /* Treat jack array sels? */
 128     n_ents = get_Sel_n_accessed_entities(addr);
 129     break;
 130   case iro_SymConst:
 131     if (get_SymConst_kind(addr) == symconst_addr_ent) {
 132       n_ents = 1;
 133       break;
 134     }
 135   default:
 136     //assert(0 && "unexpected address expression");
 137     n_ents = 0;
 138   }
 139
 140   return n_ents;
 141 }
 142
 143 /* An addr node is a SymConst or a Sel. */
 144 entity *get_addr_entity(ir_node *addr, int pos) {
 145   entity *ent;
 146
 147   switch (get_irn_opcode(addr)) {
 148   case iro_Sel:
 149     /* Treat jack array sels? */
 150     assert (0 <= pos && pos < get_Sel_n_accessed_entities(addr));
 151     ent = get_Sel_accessed_entity(addr, pos);
 152     break;
 153   case iro_SymConst:
 154     if (get_SymConst_kind(addr) == symconst_addr_ent) {
 155       assert(pos == 0);
 156       ent = get_SymConst_entity(addr);
 157       break;
 158     }
 159   default:
 160     ent = NULL;
 161   }
 162
 163   return ent;
 164 }
 165
 166
 167 int get_irn_loop_call_depth(ir_node *n) {
 168   ir_graph *irg = get_irn_irg(n);
 169   return get_irg_loop_depth(irg);
 170 }
 171
 172 int get_irn_loop_depth(ir_node *n) {
 173   return get_loop_depth(get_irn_loop(get_nodes_block(n)));
 174 }
 175
 176 int get_irn_recursion_depth(ir_node *n) {
 177   ir_graph *irg = get_irn_irg(n);
 178   return get_irg_recursion_depth(irg);
 179 }
 180
 181
 182 /* *************************************************************************** */
 183 /* The heuristic                                                               */
 184 /* *************************************************************************** */
 185
 186 int get_weighted_loop_depth(ir_node *n) {
 187   int loop_call_depth = get_irn_loop_call_depth(n);
 188   int loop_depth      = get_irn_loop_depth(n);
 189   int recursion_depth = get_irn_recursion_depth(n);
 190
 191   return loop_call_depth + loop_depth + recursion_depth;
 192 }
 193
 194 /* *************************************************************************** */
 195 /* The analyses                                                                */
 196 /* *************************************************************************** */
 197
 198 void init_field_temperature(void) {
 199   assert(!unrecognized_access);
 200   unrecognized_access = NEW_ARR_F(ir_node *, 0);
 201 }
 202
 203
 204 void chain_accesses(ir_node *n, void *env) {
 205   int i, n_ents;
 206   ir_node *addr;
 207
 208   if (get_irn_op(n) == op_Alloc) {
 209     add_type_allocation(get_Alloc_type(n), n);
 210     return;
 211   }
 212
 213   if (is_memop(n)) {
 214     addr = get_memop_ptr(n);
 215   } else {
 216     return;
 217   }
 218
 219   n_ents = get_addr_n_entities(addr);
 220   for (i = 0; i < n_ents; ++i) {
 221     entity *ent = get_addr_entity(addr, i);
 222     if (ent)
 223       add_entity_access(ent, n);
 224     else
 225       add_unrecognized_access(n);
 226   }
 227 }
 228
 229
 230 /* compute the field temperature. */
 231 void compute_field_temperature(void) {
 232
 233   int i, n_irgs = get_irp_n_irgs();
 234
 235   init_field_temperature();
 236
 237   for (i=0; i < n_irgs; i++) {
 238     current_ir_graph = get_irp_irg(i);
 239     irg_walk_graph(current_ir_graph, NULL, chain_accesses, NULL);
 240   }
 241 }
 242
 243 /* free occupied memory, reset */
 244 void free_field_temperature(void) {
 245   DEL_ARR_F(unrecognized_access);
 246   unrecognized_access = NULL;
 247 }
 248
 249
 250
 251 /* *************************************************************************** */
 252 /* Auxiliary                                                                   */
 253 /* *************************************************************************** */
 254
 255
 256 int is_jack_rts_class(type *t) {
 257   ident *name = get_type_ident(t);
 258
 259   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 260   if (id_is_prefix(new_id_from_str("["), name)) return 1;
 261   if (id_is_prefix(new_id_from_str("gnu/"), name)) return 1;
 262   if (id_is_prefix(new_id_from_str("java/"), name)) return 1;
 263
 264   return 0;
 265 }