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 static void init_tables ()
  58 {
  59   _live_classes   = eset_create ();
  60   _live_fields    = eset_create ();
  61   _called_methods = eset_create ();
  62
  63   _live_graphs = eset_create ();
  64   _dead_graphs = eset_create ();
  65
  66   if (get_irp_main_irg ()) {
  67     eset_insert (_live_graphs, get_irp_main_irg ());
  68   }
  69
  70   if (get_glob_type ()) {
  71     eset_insert (_live_classes, get_glob_type ());
  72   }
  73
  74 }
  75
  76 /**
  77    Enter all method and field accesses and all class allocations into our tables.
  78 */
  79 static void rta_act (ir_node *node, void *env)
  80 {
  81   opcode op = get_irn_opcode (node);
  82
  83   if (iro_Call == op) {
  84     entity *ent = NULL;
  85
  86     ir_node *ptr = get_Call_ptr (node);
  87
  88     if (iro_Sel == get_irn_opcode (ptr)) {
  89       ent = get_Sel_entity (ptr);
  90     } else if (iro_Const == get_irn_opcode (ptr)) {
  91       ent = get_tarval_entity (get_Const_tarval (ptr));
  92     }
  93
  94     /* assert (ent); */
  95
  96     if (ent) {
  97       eset_insert (_called_methods, ent);
  98     }
  99   } else if (iro_Load  == op) {
 100     ir_node *ptr = get_Load_ptr (node);
 101     entity  *ent = NULL;
 102
 103     if (iro_Sel == get_irn_opcode (ptr)) {
 104       ent = get_Sel_entity (ptr);
 105     }
 106     if (ent) {
 107       eset_insert (_live_fields, ent);
 108     }
 109   } else  if (iro_Store == op) {
 110     ir_node *ptr = get_Store_ptr (node);
 111     entity  *ent = NULL;
 112
 113     if (iro_Sel == get_irn_opcode (ptr)) {
 114       ent = get_Sel_entity (ptr);
 115     }
 116     if (ent) {
 117       eset_insert (_live_fields, ent);
 118     }
 119   } else if (iro_Alloc == op) {
 120     type *type = get_Alloc_type (node);
 121
 122     eset_insert (_live_classes, type);
 123   }
 124 }
 125
 126 /**
 127 Traverse the given graph to collect method and field accesses and object allocations.
 128 */
 129 static void rta_fill_graph (ir_graph* graph)
 130 {
 131   if (NULL != graph) {
 132     if (NULL != get_irg_end_block (graph)) {
 133       irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL);
 134     }
 135   }
 136 }
 137
 138 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
 139 {
 140   if (eset_contains (live_graphs, graph)) {
 141     return (TRUE);
 142   }
 143
 144   if (eset_contains (dead_graphs, graph)) {
 145     return (FALSE);
 146   }
 147
 148   assert (0 && "what's up");
 149 }
 150
 151 /**
 152    Traverse all graphs to collect method and field accesses and object allocations.
 153
 154    @param rerun Whether to rely on is_alive in a second run
 155 */
 156 static void rta_fill_all (int rerun)
 157 {
 158   int i;
 159   int old_ip_view = interprocedural_view;
 160   eset *live_graphs = NULL;
 161   eset *dead_graphs = NULL;
 162
 163   interprocedural_view = 0;
 164
 165   if (rerun) {
 166     int i;
 167     int n_graphs = get_irp_n_irgs ();
 168
 169     /* force all graphs to be entered in either live_graphs or dead_graphs */
 170     for (i = 0; i < n_graphs; i ++) {
 171       rta_is_alive_graph (get_irp_irg (i));
 172     }
 173
 174     /* remember existing infos for later */
 175     live_graphs = _live_graphs;
 176     dead_graphs = _dead_graphs;
 177
 178     /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
 179     _live_graphs = NULL;
 180     _dead_graphs = NULL;
 181
 182     rta_cleanup ();
 183     init_tables ();
 184   }
 185
 186   /* consider all graphs, possibly taking into account existing infos */
 187   for (i = 0; i < get_irp_n_irgs(); i++) {
 188     ir_graph *graph = get_irp_irg (i);
 189
 190     if (!rerun || is_alive (graph, live_graphs, dead_graphs)) {
 191       rta_fill_graph (graph);
 192     }
 193   }
 194
 195   if (rerun) {
 196     /* clean up the tables that we have retained */
 197     eset_destroy (live_graphs);
 198     eset_destroy (dead_graphs);
 199   }
 200
 201   interprocedural_view = old_ip_view;
 202 }
 203
 204 /**
 205    Find out whether the given method could be the target of a
 206    polymorphic call.
 207 */
 208 static int is_call_target (const entity *method)
 209 {
 210   int is_target = FALSE;
 211   int i;
 212   int n_over;
 213
 214   /* The method could be the target of a polymorphic call if it is
 215      called or if it overrides a method that is called. */
 216
 217   if (eset_contains (_called_methods, (entity*) method)) {
 218     return (TRUE);
 219   }
 220
 221   /* not called?  check methods in superclass(es) */
 222   n_over = get_entity_n_overwrittenby ((entity*) method);
 223   for (i = 0; !is_target && (i < n_over); i ++) {
 224     entity *over = get_entity_overwrittenby ((entity*) method, i);
 225     is_target |= is_call_target (over);
 226   }
 227
 228   return (is_target);
 229 }
 230
 231 /**
 232    Given a method, find the firm graph that implements that method.
 233 */
 234 static ir_graph *get_implementing_graph (const entity *method)
 235 {
 236   ir_graph *graph = get_entity_irg ((entity*) method);
 237
 238   if (NULL == graph) {
 239     int i;
 240     int n_over = get_entity_n_overwrites ((entity*) method);
 241
 242     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 243       entity *over = get_entity_overwrites ((entity*) method, i);
 244       graph = get_implementing_graph (over);
 245     }
 246   }
 247
 248   assert (graph && "no graph");
 249
 250   return (graph);
 251 }
 252
 253 /**
 254    Determine whether the give method or one of its overwriter have
 255    been used in a call to the given graph.
 256 */
 257 static int has_live_call (entity *method, ir_graph *graph)
 258 {
 259   int has_call = FALSE;
 260   int i, n_over;
 261
 262   /* stop searching if a overwriting method comes with a new graph */
 263   if (get_irg_ent (graph) != method) {
 264     return (FALSE);
 265   }
 266
 267   /* maybe we're called (possibly through polymorphy)? */
 268   if (is_call_target (method)) {
 269     return (TRUE);
 270   }
 271
 272   /* maybe we're overwritten by a method that is called? */
 273   n_over = get_entity_n_overwrittenby ((entity*) method);
 274   for (i = 0; !has_call && (i < n_over); i ++) {
 275     entity *over = get_entity_overwrittenby((entity*) method, i);
 276     has_call |= has_live_call (over, graph);
 277   }
 278
 279   return (has_call);
 280 }
 281
 282 /**
 283    Determine whether the given class is live *and* uses the given
 284    graph at some point.
 285 */
 286 static int has_graph (type *clazz, ir_graph *graph)
 287 {
 288   int has_the_graph = FALSE;
 289   int i;
 290   int n_sub;
 291
 292   if (eset_contains (_live_classes, clazz)) {
 293     int n_meth = get_class_n_members (clazz);
 294
 295     for (i = 0; i < n_meth; i ++) {
 296       entity *member = get_class_member (clazz, i);
 297       if (is_method_type (get_entity_type (member))) {
 298         ir_graph *impl = get_entity_irg (member);
 299
 300         if (impl == graph) {
 301           return (TRUE);
 302         }
 303       } /* is_method */
 304     } /* all methods */
 305   } /* _live_classes.contains (clazz) */
 306
 307   /* our subclasses might be using that graph, no? */
 308   n_sub = get_class_n_subtypes (clazz);
 309   for (i = 0; !has_the_graph && (i < n_sub); i ++) {
 310     type *sub = get_class_subtype (clazz, i);
 311
 312     has_the_graph |= has_graph (sub, graph);
 313   }
 314
 315   return (has_the_graph);
 316 }
 317
 318 /**
 319    Determine wether the given method could be used in a call to the
 320    given graph on a live class.
 321 */
 322 static int has_live_class (entity *method, ir_graph *graph)
 323 {
 324   int has_class = FALSE;
 325   int i;
 326   int n_over;
 327   type *clazz;
 328
 329   /* const char *name = get_entity_name (method); */
 330
 331   /* stop searching when an overwriting method provides a new graph */
 332   if (get_implementing_graph (method) != graph) {
 333     return (FALSE);
 334   }
 335
 336   clazz = get_entity_owner (method);
 337
 338   if (has_graph (clazz, graph)) { /* this also checks whether clazz is live*/
 339     return (TRUE);
 340   }
 341
 342   n_over = get_entity_n_overwrittenby (method);
 343   for (i = 0; !has_class && (i < n_over); i ++) {
 344     entity *over = get_entity_overwrittenby (method, i);
 345     has_class |= has_live_class (over, graph);
 346   }
 347
 348   return (has_class);
 349 }
 350
 351 static int stats ()
 352 {
 353   int i;
 354   int n_live_graphs = 0;
 355   int n_graphs = get_irp_n_irgs();
 356
 357   for (i = 0; i < n_graphs; i++) {
 358     ir_graph *graph = get_irp_irg(i);
 359
 360     if (rta_is_alive_graph (graph)) {
 361       n_live_graphs ++;
 362     }
 363   }
 364
 365   return (n_live_graphs);
 366 }
 367
 368 void rta_init (int verbose)
 369 {
 370   int n_live_graphs = get_irp_n_irgs ();
 371   int n_graphs = 0;
 372   int n_runs = 0;
 373
 374   init_tables ();
 375
 376   printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 377   rta_fill_all (FALSE);
 378
 379   while (n_graphs != n_live_graphs) {
 380     n_graphs = n_live_graphs;
 381     n_runs ++;
 382     rta_fill_all (TRUE);
 383     n_live_graphs = stats ();
 384     if (verbose) {
 385       printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 386     }
 387   }
 388
 389   if (verbose) {
 390     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 391     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 392     printf ("RTA: n_runs        = %i\n", n_runs);
 393   }
 394 }
 395
 396 void rta_cleanup ()
 397 {
 398   if (_live_classes) {
 399     eset_destroy (_live_classes);
 400     _live_classes = NULL;
 401   }
 402
 403   if (_live_fields) {
 404     eset_destroy (_live_fields);
 405     _live_fields = NULL;
 406   }
 407
 408   if (_called_methods) {
 409     eset_destroy (_called_methods);
 410     _called_methods = NULL;
 411   }
 412
 413   if (_live_graphs) {
 414     eset_destroy (_live_graphs);
 415     _live_graphs = NULL;
 416   }
 417
 418   if (_dead_graphs) {
 419     eset_destroy (_dead_graphs);
 420     _dead_graphs = NULL;
 421   }
 422 }
 423
 424 int  rta_is_alive_class  (type   *clazz)
 425 {
 426   return (eset_contains (_live_classes, clazz));
 427 }
 428
 429 int  rta_is_alive_graph (ir_graph *graph)
 430 {
 431   if (eset_contains (_live_graphs, graph)) {
 432     return (TRUE);
 433   }
 434
 435   if (eset_contains (_dead_graphs, graph)) {
 436     return (FALSE);
 437   }
 438
 439   entity *meth = get_irg_ent (graph);
 440
 441   if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
 442     eset_insert (_live_graphs, graph);
 443
 444     return (TRUE);
 445   } else {
 446     eset_insert (_dead_graphs, graph);
 447
 448     return (FALSE);
 449   }
 450 }
 451
 452 int  rta_is_alive_field  (entity *field)
 453 {
 454   return (eset_contains (_live_fields, field));
 455 }
 456
 457
 458
 459 /*
 460  * $Log$
 461  * Revision 1.5  2004/06/13 15:03:45  liekweg
 462  * RTA auf Iterative RTA aufgebohrt --flo
 463  *
 464  * Revision 1.4  2004/06/12 19:35:04  liekweg
 465  * Kommentare eingef"ugt --flo
 466  *
 467  * Revision 1.3  2004/06/12 17:09:46  liekweg
 468  * RTA works, outedges breaks.  "Yay." --flo
 469  *
 470  * Revision 1.2  2004/06/11 18:25:39  liekweg
 471  * Added todo
 472  *
 473  * Revision 1.1  2004/06/11 18:24:18  liekweg
 474  * Added RTA --flo
 475  *
 476  */