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 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include "rta.h"
  26
  27 #include <stdlib.h>
  28 #include "cgana.h"              /* get_implementation */
  29
  30 #include "irnode_t.h"
  31 #include "irprog.h"
  32
  33 #include "eset.h"
  34 /* #include "pmap.h" */
  35 /* #include "array.h" */
  36 #include "irgwalk.h"
  37 /* #include "ircons.h" */
  38 /* #include "irgmod.h" */
  39 /* #include "irflag_t.h" */
  40
  41 /* #include "dbginfo_t.h" */
  42
  43 # define TRUE 1
  44 # define FALSE 0
  45
  46 /* base data */
  47 static eset *_live_classes   = NULL;
  48 static eset *_live_fields    = NULL;
  49 static eset *_called_methods = NULL;
  50
  51 /* cache computed results */
  52 static eset *_live_graphs    = NULL;
  53 static eset *_dead_graphs    = NULL;
  54
  55 /* now the meat */
  56
  57 /**
  58    Enter all method and field accesses and all class allocations into our tables.
  59 */
  60 static void rta_act (ir_node *node, void *env)
  61 {
  62   opcode op = get_irn_opcode (node);
  63
  64   if (iro_Call == op) {
  65     entity *ent = NULL;
  66
  67     ir_node *ptr = get_Call_ptr (node);
  68
  69     if (iro_Sel == get_irn_opcode (ptr)) {
  70       ent = get_Sel_entity (ptr);
  71     } else if (iro_Const == get_irn_opcode (ptr)) {
  72       ent = get_tarval_entity (get_Const_tarval (ptr));
  73     }
  74
  75     assert (ent);
  76
  77     if (ent) {
  78       eset_insert (_called_methods, ent);
  79     }
  80   } else if (iro_Load  == op) {
  81     ir_node *ptr = get_Load_ptr (node);
  82     entity  *ent = NULL;
  83
  84     if (iro_Sel == get_irn_opcode (ptr)) {
  85       ent = get_Sel_entity (ptr);
  86     }
  87     if (ent) {
  88       eset_insert (_live_fields, ent);
  89     }
  90   } else  if (iro_Store == op) {
  91     ir_node *ptr = get_Store_ptr (node);
  92     entity  *ent = NULL;
  93
  94     if (iro_Sel == get_irn_opcode (ptr)) {
  95       ent = get_Sel_entity (ptr);
  96     }
  97     if (ent) {
  98       eset_insert (_live_fields, ent);
  99     }
 100   } else if (iro_Alloc == op) {
 101     type *type = get_Alloc_type (node);
 102
 103     eset_insert (_live_classes, type);
 104   }
 105 }
 106
 107 /**
 108 Traverse the given graph to collect method and field accesses and object allocations.
 109 */
 110 static void rta_fill_graph (ir_graph* graph)
 111 {
 112   if (NULL != graph) {
 113     if (NULL != get_irg_end_block (graph)) {
 114       irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL);
 115     }
 116   }
 117 }
 118
 119 /**
 120 Traverse all graphs to collect method and field accesses and object allocations.
 121 */
 122 static void rta_fill_all ()
 123 {
 124   int i;
 125   int old_ip_view = interprocedural_view;
 126
 127   interprocedural_view = 0;
 128   for (i = 0; i < get_irp_n_irgs(); i++) {
 129     rta_fill_graph (get_irp_irg (i));
 130   }
 131   interprocedural_view = old_ip_view;
 132 }
 133
 134 /**
 135    Find out whether the given method could be the target of a
 136    polymorphic call.
 137 */
 138 static int is_call_target (const entity *method)
 139 {
 140   int is_target = FALSE;
 141   int i;
 142   int n_over;
 143
 144   /* The method could be the target of a polymorphic call if it is
 145      called or if it overrides a method that is called. */
 146
 147   if (eset_contains (_called_methods, (entity*) method)) {
 148     return (TRUE);
 149   }
 150
 151   /* not called?  check methods in superclass(es) */
 152   n_over = get_entity_n_overwrittenby ((entity*) method);
 153   for (i = 0; !is_target && (i < n_over); i ++) {
 154     entity *over = get_entity_overwrittenby ((entity*) method, i);
 155     is_target |= is_call_target (over);
 156   }
 157
 158   return (is_target);
 159 }
 160
 161 /**
 162    Given a method, find the firm graph that implements that method.
 163 */
 164 static ir_graph *get_implementing_graph (const entity *method)
 165 {
 166   ir_graph *graph = get_entity_irg ((entity*) method);
 167
 168   if (NULL == graph) {
 169     int i;
 170     int n_over = get_entity_n_overwrites ((entity*) method);
 171
 172     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 173       entity *over = get_entity_overwrites ((entity*) method, i);
 174       graph = get_implementing_graph (over);
 175     }
 176   }
 177
 178   assert (graph && "no graph");
 179
 180   return (graph);
 181 }
 182
 183 /**
 184    Determine whether the give method or one of its overwriter have
 185    been used in a call to the given graph.
 186 */
 187 static int has_live_call (entity *method, ir_graph *graph)
 188 {
 189   int has_call = FALSE;
 190   int i, n_over;
 191
 192   /* stop searching if a overwriting method comes with a new graph */
 193   if (get_irg_ent (graph) != method) {
 194     return (FALSE);
 195   }
 196
 197   /* maybe we're called (possibly through polymorphy)? */
 198   if (is_call_target (method)) {
 199     return (TRUE);
 200   }
 201
 202   /* maybe we're overwritten by a method that is called? */
 203   n_over = get_entity_n_overwrittenby ((entity*) method);
 204   for (i = 0; !has_call && (i < n_over); i ++) {
 205     entity *over = get_entity_overwrittenby((entity*) method, i);
 206     has_call |= has_live_call (over, graph);
 207   }
 208
 209   return (has_call);
 210 }
 211
 212 /**
 213    Determine whether the given class is live *and* uses the given
 214    graph at some point.
 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 (eset_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   /* our subclasses might be using that graph, no? */
 238   n_sub = get_class_n_subtypes (clazz);
 239   for (i = 0; !has_the_graph && (i < n_sub); i ++) {
 240     type *sub = get_class_subtype (clazz, i);
 241
 242     has_the_graph |= has_graph (sub, graph);
 243   }
 244
 245   return (has_the_graph);
 246 }
 247
 248 /**
 249    Determine wether the given method could be used in a call to the
 250    given graph on a live class.
 251 */
 252 static int has_live_class (entity *method, ir_graph *graph)
 253 {
 254   int has_class = FALSE;
 255   int i;
 256   int n_over;
 257   type *clazz;
 258
 259   /* const char *name = get_entity_name (method); */
 260
 261   /* stop searching when an overwriting method provides a new graph */
 262   if (get_implementing_graph (method) != graph) {
 263     return (FALSE);
 264   }
 265
 266   clazz = get_entity_owner (method);
 267
 268   if (has_graph (clazz, graph)) { /* this also checks whether clazz is live*/
 269     return (TRUE);
 270   }
 271
 272   n_over = get_entity_n_overwrittenby (method);
 273   for (i = 0; !has_class && (i < n_over); i ++) {
 274     entity *over = get_entity_overwrittenby (method, i);
 275     has_class |= has_live_class (over, graph);
 276   }
 277
 278   return (has_class);
 279 }
 280
 281 static int rta_check (ir_graph *graph)
 282 {
 283   return (rta_is_alive_graph (graph));
 284 }
 285
 286
 287 void rta_init ()
 288 {
 289   _live_classes   = eset_create ();
 290   _live_fields    = eset_create ();
 291   _called_methods = eset_create ();
 292
 293   _live_graphs = eset_create ();
 294   _dead_graphs = eset_create ();
 295
 296   /*
 297    * shold be:
 298    * rta_fill_queue ()
 299    */
 300   if (get_irp_main_irg ()) {
 301     eset_insert (_live_graphs, get_irp_main_irg ());
 302   }
 303
 304   if (get_glob_type ()) {
 305     eset_insert (_live_classes, get_glob_type ());
 306   }
 307
 308   rta_fill_all ();
 309 }
 310
 311 void rta_cleanup ()
 312 {
 313   int i;
 314   int n_live_graphs = 0;
 315   int n_graphs = get_irp_n_irgs();
 316
 317   for (i = 0; i < n_graphs; i++) {
 318     ir_graph *graph = get_irp_irg(i);
 319
 320     if (rta_check (graph)) {
 321       const char *name = get_entity_name (get_irg_ent (graph));;
 322
 323       n_live_graphs ++;
 324
 325       fprintf (stdout, "LIVE  %s\n", name);
 326     }
 327   }
 328
 329   fprintf (stdout, "RES   %s: %i graphs, %i live\n", __FUNCTION__, n_graphs, n_live_graphs);
 330
 331   if (_live_classes) {
 332     eset_destroy (_live_classes);
 333     _live_classes = NULL;
 334   }
 335
 336   if (_live_fields) {
 337     eset_destroy (_live_fields);
 338     _live_fields = NULL;
 339   }
 340
 341   if (_called_methods) {
 342     eset_destroy (_called_methods);
 343     _called_methods = NULL;
 344   }
 345
 346   if (_live_graphs) {
 347     eset_destroy (_live_graphs);
 348     _live_graphs = NULL;
 349   }
 350
 351   if (_dead_graphs) {
 352     eset_destroy (_dead_graphs);
 353     _dead_graphs = NULL;
 354   }
 355 }
 356
 357 int  rta_is_alive_class  (type   *clazz)
 358 {
 359   return (eset_contains (_live_classes, clazz));
 360 }
 361
 362 int  rta_is_alive_graph (ir_graph *graph)
 363 {
 364   if (eset_contains (_live_graphs, graph)) {
 365     return (TRUE);
 366   }
 367
 368   if (eset_contains (_dead_graphs, graph)) {
 369     return (FALSE);
 370   }
 371
 372   entity *meth = get_irg_ent (graph);
 373
 374   if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
 375     eset_insert (_live_graphs, graph);
 376
 377     return (TRUE);
 378   } else {
 379     eset_insert (_dead_graphs, graph);
 380
 381     return (FALSE);
 382   }
 383 }
 384
 385 int  rta_is_alive_field  (entity *field)
 386 {
 387   return (eset_contains (_live_fields, field));
 388 }
 389
 390
 391
 392 /*
 393  * $Log$
 394  * Revision 1.4  2004/06/12 19:35:04  liekweg
 395  * Kommentare eingef"ugt --flo
 396  *
 397  * Revision 1.3  2004/06/12 17:09:46  liekweg
 398  * RTA works, outedges breaks.  "Yay." --flo
 399  *
 400  * Revision 1.2  2004/06/11 18:25:39  liekweg
 401  * Added todo
 402  *
 403  * Revision 1.1  2004/06/11 18:24:18  liekweg
 404  * Added RTA --flo
 405  *
 406  */