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

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana/rta.c
   6  * Purpose:     Intraprozedural analyses to improve the call graph estimate.
   7  * Author:      Florian
   8  * Modified by:
   9  * Created:     09.06.2002
  10  * CVS-ID:      $$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15 /**
  16  * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es
  17  * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden
  18  * bestimmt.
  19  */
  20
  21 #include "rta.h"
  22
  23 # define TRUE 1
  24 # define FALSE 0
  25
  26 /* # define RTA_SET */
  27 # ifdef RTA_SET
  28 typedef struct rta_set_elt
  29 {
  30   struct rta_set_elt *_next;
  31   void *_obj;
  32 } rta_set_elt_t;
  33
  34 typedef struct rta_set
  35 {
  36   rta_set_elt_t *_list;
  37 } rta_set_t;
  38
  39 #  define SET_T rta_set_t
  40
  41 # else /* if defined RTA_SET */
  42 #  define SET_T eset
  43 #  define new_set eset_create
  44 #  define delete_set(SET)       eset_destroy(SET)
  45 #  define set_insert(SET,ELT)   eset_insert(SET,ELT)
  46 #  define set_contains(SET,ELT) eset_contains(SET,ELT)
  47 # endif /* defined RTA_SET */
  48
  49 static SET_T *_live_classes   = NULL;
  50 static SET_T *_live_fields    = NULL;
  51 static SET_T *_called_methods = NULL;
  52
  53 /* cache computed results */
  54 static SET_T *_live_graphs    = NULL;
  55 static SET_T *_dead_graphs    = NULL;
  56
  57 # ifdef RTA_SET
  58 /* Reinvent the wheel, err, set. */
  59 /* eset uses obstacks, which fucks up the graph somehow */
  60 static rta_set_t *new_set ()
  61 {
  62   rta_set_t *set = (rta_set_t*) xmalloc (sizeof (rta_set_t));
  63
  64   set->_list = NULL;
  65
  66   return (set);
  67 }
  68
  69 static void delete_set (rta_set_t *set)
  70 {
  71   rta_set_elt_t *elt = set->_list;
  72
  73   while (NULL != elt) {
  74     rta_set_elt_t *old = elt;
  75     elt = elt->_next;
  76
  77     old->_next = NULL;
  78     old->_obj  = NULL;
  79     free (old);
  80   }
  81
  82   free (set);
  83 }
  84
  85 static void set_insert (rta_set_t *set, void *obj)
  86 {
  87   rta_set_elt_t *elt = (rta_set_elt_t*) xmalloc (sizeof (rta_set_elt_t));
  88
  89   elt->_obj = obj;
  90   elt->_next = set->_list;
  91   set->_list = elt;
  92 }
  93
  94 static int set_contains (rta_set_t *set, void *obj)
  95 {
  96   rta_set_elt_t *elt = set->_list;
  97
  98   while (NULL != elt) {
  99     if (elt->_obj == obj) {
 100       return (TRUE);
 101     }
 102
 103     elt = elt->_next;
 104   }
 105
 106   return (FALSE);
 107 }
 108 # endif /* defined RTA_SET */
 109
 110 /* now the meat */
 111
 112 static void rta_act (ir_node *node, void *env)
 113 {
 114   opcode op = get_irn_opcode (node);
 115
 116   if (iro_Call == op) {
 117     entity *ent = NULL;
 118
 119     ir_node *ptr = get_Call_ptr (node);
 120     // test:  ptr.op == Const
 121
 122     if (iro_Sel == get_irn_opcode (ptr)) {
 123       ent = get_Sel_entity (ptr);
 124       set_insert (_called_methods, ent);
 125     }
 126
 127     if (ent) {
 128     }
 129   } else if (iro_Load  == op) {
 130     ir_node *ptr = get_Load_ptr (node);
 131     entity  *ent = NULL;
 132
 133     if (iro_Sel == get_irn_opcode (ptr)) {
 134       ent = get_Sel_entity (ptr);
 135     }
 136     if (ent) {
 137       set_insert (_live_fields, ent);
 138     }
 139   } else  if (iro_Store == op) {
 140     ir_node *ptr = get_Store_ptr (node);
 141     entity  *ent = NULL;
 142
 143     if (iro_Sel == get_irn_opcode (ptr)) {
 144       ent = get_Sel_entity (ptr);
 145     }
 146     if (ent) {
 147       set_insert (_live_fields, ent);
 148     }
 149   } else if (iro_Alloc == op) {
 150     type *type = get_Alloc_type (node);
 151     set_insert (_live_classes, type);
 152   }
 153 }
 154
 155 static void rta_fill_graph (ir_graph* graph)
 156 {
 157   irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL);
 158 }
 159
 160 static void rta_fill_all ()
 161 {
 162   int i;
 163
 164   for (i = 0; i < get_irp_n_irgs(); i++) {
 165     rta_fill_graph (get_irp_irg (i));
 166   }
 167 }
 168
 169 static int is_call_target (entity *method)
 170 {
 171   return (TRUE);
 172 }
 173
 174
 175 static ir_graph *get_implementing_graph (entity *method)
 176 {
 177   ir_graph *graph = get_entity_irg (method);
 178
 179   if (NULL == graph) {
 180     int i;
 181     int n_over = get_entity_n_overwrites (method);
 182
 183     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 184       entity *over = get_entity_overwrites (method, i);
 185       graph = get_implementing_graph (over);
 186     }
 187   }
 188
 189   assert (graph && "no graph");
 190
 191   return (graph);
 192 }
 193
 194 static int has_live_call (entity *method, ir_graph *graph)
 195 {
 196   int has_call = FALSE;
 197   int i, n_over;
 198
 199   if (get_irg_ent (graph) != method) {
 200     return (FALSE);
 201   }
 202
 203   if (is_call_target (method)) {
 204     return (TRUE);
 205   }
 206
 207   n_over = get_entity_n_overwrittenby (method);
 208   for (i = 0; !has_call && (i < n_over); i ++) {
 209     entity *over = get_entity_overwrittenby(method, i);
 210     has_call |= has_live_call (over, graph);
 211   }
 212
 213   return (has_call);
 214 }
 215
 216 static int has_graph (type *clazz, ir_graph *graph)
 217 {
 218   int has_the_graph = FALSE;
 219   int i;
 220   int n_sub;
 221
 222   if (set_contains (_live_classes, clazz)) {
 223     int n_meth = get_class_n_members (clazz);
 224
 225     for (i = 0; i < n_meth; i ++) {
 226       entity *member = get_class_member (clazz, i);
 227       if (is_method_type (get_entity_type (member))) {
 228         ir_graph *impl = get_entity_irg (member);
 229
 230         if (impl == graph) {
 231           return (TRUE);
 232         }
 233       } /* is_method */
 234     } /* all methods */
 235   } /* _live_classes.contains (clazz) */
 236
 237   n_sub = get_class_n_subtypes (clazz);
 238   for (i = 0; !has_the_graph && (i < n_sub); i ++) {
 239     type *sub = get_class_subtype (clazz, i);
 240
 241     has_the_graph |= has_graph (sub, graph);
 242   }
 243
 244   return (has_the_graph);
 245 }
 246
 247 static int has_live_class (entity *method, ir_graph *graph)
 248 {
 249   int has_class = FALSE;
 250   int i;
 251   int n_over;
 252   type *clazz;
 253
 254   if (get_implementing_graph (method) != graph) {
 255     return (FALSE);
 256   }
 257
 258   clazz = get_entity_owner (method);
 259   if (has_graph (clazz, graph)) {
 260     return (TRUE);
 261   }
 262
 263   n_over = get_entity_n_overwrittenby (method);
 264   for (i = 0; !has_class && (i < n_over); i ++) {
 265     entity *over = get_entity_overwrittenby (method, i);
 266     has_class |= has_live_class (over, graph);
 267   }
 268
 269   return (has_class);
 270 }
 271
 272
 273 void rta_init ()
 274 {
 275   fprintf (stdout, "BEGIN %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__);
 276
 277   _live_classes   = new_set ();
 278   _live_fields    = new_set ();
 279   _called_methods = new_set ();
 280
 281   _live_graphs = new_set ();
 282   _dead_graphs = new_set ();
 283
 284   fprintf (stdout, "FILL  %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__);
 285   rta_fill_all ();
 286   fprintf (stdout, "DONE  %s(%i): %s\n", __FILE__, __LINE__, __FUNCTION__);
 287
 288   /*
 289    * shold be:
 290    * rta_fill_queue ()
 291    */
 292 }
 293
 294 void rta_cleanup ()
 295 {
 296   if (_live_classes) {
 297     delete_set (_live_classes);
 298     _live_classes = NULL;
 299   }
 300
 301   if (_live_fields) {
 302     delete_set (_live_fields);
 303     _live_fields = NULL;
 304   }
 305
 306   if (_called_methods) {
 307     delete_set (_called_methods);
 308     _called_methods = NULL;
 309   }
 310
 311   if (_live_graphs) {
 312     delete_set (_live_graphs);
 313     _live_graphs = NULL;
 314   }
 315
 316   if (_dead_graphs) {
 317     delete_set (_dead_graphs);
 318     _dead_graphs = NULL;
 319   }
 320 }
 321
 322 int  rta_is_alive_class  (type   *clazz)
 323 {
 324   return (set_contains (_live_classes, clazz));
 325 }
 326
 327 int  rta_is_alive_graph (ir_graph *graph)
 328 {
 329   if (set_contains (_live_graphs, graph)) {
 330     return (TRUE);
 331   }
 332
 333   if (set_contains (_dead_graphs, graph)) {
 334     return (FALSE);
 335   }
 336
 337   entity *meth = get_irg_ent (graph);
 338
 339   if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
 340     set_insert (_live_graphs, graph);
 341
 342     return (TRUE);
 343   } else {
 344     set_insert (_dead_graphs, graph);
 345
 346     return (FALSE);
 347   }
 348 }
 349
 350 int  rta_is_alive_field  (entity *field)
 351 {
 352   return (set_contains (_live_fields, field));
 353 }
 354
 355
 356
 357 /*
 358  * $Log$
 359  * Revision 1.1  2004/06/11 18:24:18  liekweg
 360  * Added RTA --flo
 361  *
 362  */