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

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana/rta.c
   6  * Purpose:     Interprocedural analysis 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
  29 #include "irnode_t.h"
  30 #include "irprog.h"
  31
  32 #include "eset.h"
  33 #include "irgwalk.h"
  34 #include "irgmod.h"
  35 #include "irvrfy.h"
  36 #include "trvrfy.h"
  37
  38 # define TRUE 1
  39 # define FALSE 0
  40
  41 /* base data */
  42 static eset *_live_classes   = NULL;
  43
  44 /* cache computed results */
  45 static eset *_live_graphs    = NULL;
  46
  47 static int whole_world = 0;
  48 static int verbose     = 0;
  49
  50 /**
  51    Given a method, find the firm graph that implements that method.
  52 */
  53 static ir_graph *get_implementing_graph (entity *method)
  54 {
  55   ir_graph *graph = get_entity_irg ((entity*) method);
  56
  57   if (NULL == graph) {
  58     int i;
  59     int n_over = get_entity_n_overwrites ((entity*) method);
  60
  61     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
  62       entity *over = get_entity_overwrites ((entity*) method, i);
  63       graph = get_implementing_graph (over);
  64     }
  65   }
  66
  67   /* we *must* always return a graph != NULL, *except* when we're used
  68      inside remove_irg or force_description */
  69   /* assert (graph && "no graph"); */
  70
  71   return (graph);
  72 }
  73
  74 static int add_graph (ir_graph *graph)
  75 {
  76   if (!eset_contains (_live_graphs, graph)) {
  77     if (verbose > 1) {
  78       fprintf(stdout, "RTA:        new graph of ");
  79       DDMEO(get_irg_ent (graph));
  80     }
  81
  82     eset_insert (_live_graphs, graph);
  83     return (TRUE);
  84   }
  85
  86   return (FALSE);
  87 }
  88
  89 static int add_class (type *clazz)
  90 {
  91   if (!eset_contains (_live_classes, clazz)) {
  92   if (verbose > 1) {
  93     fprintf(stdout, "RTA:        new class: ");
  94     DDMT(clazz);
  95   }
  96
  97     eset_insert (_live_classes, clazz);
  98     return (TRUE);
  99   }
 100
 101   return (FALSE);
 102 }
 103
 104 /**
 105    Given an entity, add all implementing graphs that belong to live classes to _live_graphs.
 106
 107    Iff additions occurred, return TRUE, else FALSE.
 108 */
 109 static int add_implementing_graphs (entity *method)
 110 {
 111   int i;
 112   int n_over = get_entity_n_overwrittenby (method);
 113   ir_graph *graph = get_entity_irg (method);
 114   int change = FALSE;
 115
 116   if (NULL == graph) {
 117     graph = get_implementing_graph (method);
 118   }
 119
 120   if (verbose > 1) {
 121     fprintf(stdout, "RTA:        new call to ");
 122     DDMEO(method);
 123   }
 124
 125   if (rta_is_alive_class (get_entity_owner (method))) {
 126     if (NULL != graph) {
 127       change = add_graph (graph);
 128     }
 129   }
 130
 131   for (i = 0; i < n_over; i ++) {
 132     entity *over = get_entity_overwrittenby (method, i);
 133     change |= add_implementing_graphs (over);
 134   }
 135
 136   return (change);
 137 }
 138
 139 /**
 140    Enter all method accesses and all class allocations into
 141    our tables.
 142
 143    Set *(int*)env to true iff (possibly) new graphs have been found.
 144 */
 145 static void rta_act (ir_node *node, void *env)
 146 {
 147   int *change = (int*) env;
 148
 149   opcode op = get_irn_opcode (node);
 150
 151   if (iro_Call == op) {         /* CALL */
 152     entity *ent = NULL;
 153
 154     ir_node *ptr = get_Call_ptr (node);
 155
 156     if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
 157       ent = get_Sel_entity (ptr);
 158       *change = add_implementing_graphs (ent);
 159     } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
 160       ent = get_tarval_entity (get_Const_tarval (ptr));
 161       ir_graph *graph = get_entity_irg (ent);
 162       /* don't use get_implementing_graph on a Const! */
 163       if (graph) {
 164         *change = add_graph (graph);
 165       } else {
 166         /* it's an externally allocated thing. */
 167       }
 168     } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
 169       /* If this SymConst refers to a method the method is external_visible
 170          and therefore must be considered live anyways. */
 171       /* assert (ent && "couldn't determine entity of call to symConst"); */
 172     }
 173   } else if (iro_Alloc == op) { /* ALLOC */
 174     type *type = get_Alloc_type (node);
 175
 176     *change = add_class (type);
 177   }
 178 }
 179
 180 /**
 181    Traverse the given graph to collect method accesses and
 182    object allocations.
 183 */
 184 static int rta_fill_graph (ir_graph* graph)
 185 {
 186   int change = FALSE;
 187
 188   current_ir_graph = graph;
 189
 190   irg_walk (get_irg_end (graph), rta_act, NULL, &change);
 191
 192   return (change);
 193 }
 194
 195 /**
 196    Traverse all graphs to collect method accesses and object allocations.
 197
 198    @param rerun Whether to rely on is_alive in a second run
 199 */
 200 static int rta_fill_incremental (void)
 201 {
 202   int i;
 203   int n_runs = 0;
 204   int rerun  = TRUE;
 205   int old_ip_view = interprocedural_view;
 206
 207   interprocedural_view = 0;     /* save this for later */
 208
 209   /* init_tables has added main_irg to _live_graphs */
 210
 211   /* Need to take care of graphs that are externally
 212      visible or sticky. Pretend that they are called: */
 213
 214   for (i = 0; i < get_irp_n_irgs(); i++) {
 215     ir_graph *graph = get_irp_irg (i);
 216     entity *ent = get_irg_entity (graph);
 217
 218     if (((!whole_world) &&
 219          (visibility_external_visible == get_entity_visibility (ent))) ||
 220         (stickyness_sticky == get_entity_stickyness (ent))) {
 221       eset_insert (_live_graphs, graph);
 222     }
 223   }
 224
 225   while (rerun) {
 226     ir_graph *graph;
 227
 228     /* start off new */
 229     eset *live_graphs = _live_graphs;
 230     _live_graphs = eset_create ();
 231
 232     if (verbose > 1) {
 233       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 234     }
 235
 236     /* collect what we have found previously */
 237     eset_insert_all (_live_graphs, live_graphs);
 238
 239     rerun = FALSE;
 240
 241     for (graph = eset_first (live_graphs);
 242          graph;
 243          graph = eset_next (live_graphs)) {
 244
 245       if (verbose > 1) {
 246         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 247         DDMEO(get_irg_ent (graph));
 248       }
 249
 250       rerun |= rta_fill_graph (graph);
 251     }
 252
 253     eset_destroy (live_graphs);
 254
 255     n_runs ++;
 256   }
 257
 258   interprocedural_view = old_ip_view; /* cover up our traces */
 259
 260   return (n_runs);
 261 }
 262
 263 /*
 264    Count the number of graphs that we have found to be live.
 265 */
 266 static int stats (void)
 267 {
 268   int i;
 269   int n_live_graphs = 0;
 270   int n_graphs = get_irp_n_irgs();
 271
 272   for (i = 0; i < n_graphs; i++) {
 273     ir_graph *graph = get_irp_irg(i);
 274
 275     if (rta_is_alive_graph (graph)) {
 276       n_live_graphs ++;
 277     }
 278   }
 279
 280   return (n_live_graphs);
 281 }
 282
 283 /* remove a graph, part I */
 284 /*
 285    We removed the first graph to implement the entity, so we're
 286    abstract now.  Pretend that it wasn't there at all, and every
 287    entity that used to inherit this entity's graph is now abstract.
 288 */
 289 /* Since we *know* that this entity will not be called, this is OK. */
 290 static void force_description (entity *ent, entity *addr)
 291 {
 292   int i, n_over = get_entity_n_overwrittenby (ent);
 293
 294   set_entity_peculiarity (ent, peculiarity_description);
 295
 296   for (i = 0; i < n_over; i ++) {
 297     entity *over = get_entity_overwrittenby (ent, i);
 298
 299     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 300       /* We rely on the fact that cse is performed on the const_code_irg. */
 301       entity *my_addr =
 302         tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
 303
 304       if (addr == my_addr) {
 305         force_description (over, addr);
 306       }
 307     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 308       /* check whether 'over' forces 'inheritance' of *our* graph: */
 309       ir_node *f_addr = get_atomic_ent_value (over);
 310       entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
 311
 312       assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
 313       if (impl_ent == addr) {
 314         assert (0 && "gibt's denn sowas");
 315         force_description (over, addr);
 316       }
 317     }
 318   }
 319 }
 320
 321 /* remove a graph, part II */
 322 /*
 323    Note: get_implementing_graph is not well defined here (graph->ent
 324    could overwrite more than one superclass implementation (graph).
 325    Since we *know* that this entity will not be called, this is OK.
 326 */
 327 static void remove_irg (ir_graph *graph)
 328 {
 329   entity *ent = get_irg_entity (graph);
 330   peculiarity pec = get_entity_peculiarity (ent);
 331
 332   /*   DDMEO (get_irg_ent(graph)); */
 333
 334   /* delete the ir_graph data */
 335   set_entity_peculiarity (ent, peculiarity_description);
 336   remove_irp_irg (graph);
 337   /* remove_irp_irg also removes the entities' reference to the graph */
 338   /*
 339     if (NULL != get_entity_irg (ent)) {
 340     set_entity_irg (ent, NULL);
 341     }
 342   */
 343   set_entity_peculiarity (ent, pec);
 344
 345   /* find the implementation (graph) from *some* superclass: */
 346   graph = get_implementing_graph (ent);
 347
 348   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 349     /* nothing to inherit!  pretend we're abstract */
 350     force_description (ent, ent);
 351   } else {
 352     /* pretend that we inherit the implementation (graph) from some superclass: */
 353     set_entity_peculiarity (ent, peculiarity_inherited);
 354
 355     exchange (get_atomic_ent_value (ent),
 356               get_atomic_ent_value (get_irg_ent(graph)));
 357   }
 358 }
 359
 360 /**
 361    Initialise the static data structures.
 362 */
 363 static void init_tables (void)
 364 {
 365   _live_classes   = eset_create ();
 366
 367   _live_graphs = eset_create ();
 368
 369   if (get_irp_main_irg ()) {
 370     eset_insert (_live_graphs, get_irp_main_irg ());
 371   }
 372
 373   /*
 374   if (get_glob_type ()) {
 375     eset_insert (_live_classes, get_glob_type ());
 376   }
 377   */
 378 }
 379
 380 /* Initialise the RTA data structures, and perform RTA.
 381    @param   do_verbose If == 1, print statistics, if > 1, chatter about every detail
 382    @param   do_whole_world Iff != 0, assume whole-world
 383 */
 384 void rta_init (int do_verbose, int do_whole_world)
 385 {
 386   int n_runs = 0;
 387
 388 # ifdef DEBUG_libfirm
 389   int i;
 390   for (i = 0; i < get_irp_n_irgs(); i++) {
 391     irg_vrfy (get_irp_irg(i));
 392   }
 393   tr_vrfy ();
 394 # endif /* defined DEBUG_libfirm */
 395
 396   whole_world = do_whole_world;
 397   verbose = do_verbose;
 398
 399   init_tables ();
 400
 401   n_runs = rta_fill_incremental ();
 402
 403   if (verbose) {
 404     int n_live_graphs = stats ();
 405
 406     if (whole_world) {
 407       printf ("RTA: whole-world assumption\n");
 408     }
 409     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 410     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 411     printf ("RTA: n_runs        = %i\n", n_runs);
 412   }
 413
 414 # ifdef DEBUG_libfirm
 415   for (i = 0; i < get_irp_n_irgs(); i++) {
 416     irg_vrfy (get_irp_irg(i));
 417   }
 418   tr_vrfy ();
 419 # endif /* defined DEBUG_libfirm */
 420 }
 421
 422 /* Delete all graphs that we have found to be dead from the program
 423    If verbose == 1, print statistics, if > 1, chatter about every detail
 424 */
 425 void rta_delete_dead_graphs (void)
 426 {
 427   int i;
 428   int n_graphs = get_irp_n_irgs ();
 429   ir_graph *graph = NULL;
 430   int n_dead_graphs = 0;
 431
 432   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 433
 434   eset *dead_graphs = eset_create ();
 435
 436   for (i = 0; i < n_graphs; i++) {
 437     graph = get_irp_irg(i);
 438
 439     if (rta_is_alive_graph (graph)) {
 440       /* do nothing (except some debugging fprintf`s :-) */
 441     } else {
 442 # ifdef DEBUG_libfirm
 443       entity *ent = get_irg_entity (graph);
 444       assert (whole_world ||
 445               (visibility_external_visible != get_entity_visibility (ent)));
 446 # endif /* defined DEBUG_libfirm */
 447
 448       n_dead_graphs ++;
 449       eset_insert (dead_graphs, graph);
 450     }
 451   }
 452
 453   /* now delete the graphs. */
 454   for (graph = eset_first (dead_graphs);
 455        graph;
 456        graph = (ir_graph*) eset_next (dead_graphs)) {
 457
 458     if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
 459       fprintf(stdout, "RTA: removing graph of ");
 460       DDMEO(get_irg_ent (graph));
 461     }
 462
 463     remove_irg (graph);
 464   }
 465
 466   if (verbose) {
 467     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 468   }
 469 }
 470
 471 /* Clean up the RTA data structures.  Call this after calling rta_init */
 472 void rta_cleanup (void)
 473 {
 474 # ifdef DEBUG_libfirm
 475   int i;
 476     for (i = 0; i < get_irp_n_irgs(); i++) {
 477       irg_vrfy (get_irp_irg(i));
 478     }
 479     tr_vrfy ();
 480 # endif /* defined DEBUG_libfirm */
 481
 482   if (_live_classes) {
 483     eset_destroy (_live_classes);
 484     _live_classes = NULL;
 485   }
 486
 487   if (_live_graphs) {
 488     eset_destroy (_live_graphs);
 489     _live_graphs = NULL;
 490   }
 491 }
 492
 493 /* Say whether this class might be instantiated at any point in the program: */
 494 int  rta_is_alive_class  (type   *clazz)
 495 {
 496   return (eset_contains (_live_classes, clazz));
 497 }
 498
 499 /* Say whether this graph might be run at any time in the program: */
 500 int  rta_is_alive_graph (ir_graph *graph)
 501 {
 502   if (eset_contains (_live_graphs, graph)) {
 503     return (TRUE);
 504   }
 505
 506   return (FALSE);
 507 }
 508
 509 /* dump our opinion */
 510 void rta_report (void)
 511 {
 512   int i;
 513
 514   for (i = 0; i < get_irp_n_types(); ++i) {
 515     type *tp = get_irp_type(i);
 516     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 517       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 518     }
 519   }
 520
 521   for (i = 0; i < get_irp_n_irgs(); i++) {
 522     if (rta_is_alive_graph (get_irp_irg(i))) {
 523       fprintf(stdout, "RTA: considered called: graph of ");
 524       DDMEO(get_irg_ent (get_irp_irg(i)));
 525     }
 526   }
 527 }
 528
 529
 530 /*
 531  * $Log$
 532  * Revision 1.17  2004/06/25 13:45:13  liekweg
 533  * observe stickyness; minor refactoring
 534  *
 535  * Revision 1.16  2004/06/24 06:42:14  goetz
 536  * test of firm flags
 537  *
 538  * Revision 1.15  2004/06/18 15:47:19  liekweg
 539  * minor bug fix (go forward, not backward) --flo
 540  *
 541  * Revision 1.14  2004/06/18 13:12:43  liekweg
 542  * final bug fix (calls via consts)
 543  *
 544  * Revision 1.13  2004/06/17 16:34:33  liekweg
 545  * removed DD*s
 546  *
 547  * Revision 1.12  2004/06/17 16:33:33  liekweg
 548  * minor bug fix
 549  *
 550  * Revision 1.11  2004/06/17 14:21:13  liekweg
 551  * major bugfix
 552  *
 553  * Revision 1.10  2004/06/17 10:31:41  goetz
 554  * irscc: bugfix, can now deal with loops not reachable from start
 555  * cgana: bugfix, skip_Tuple
 556  * rta: improved
 557  *
 558  * Revision 1.9  2004/06/17 08:56:03  liekweg
 559  * Fixed typos in comments
 560  *
 561  * Revision 1.8  2004/06/17 08:33:01  liekweg
 562  * Added comments; added remove_irg
 563  *
 564  * Revision 1.6  2004/06/14 13:02:03  goetz
 565  * bugfixesbug
 566  *
 567  * Revision 1.5  2004/06/13 15:03:45  liekweg
 568  * RTA auf Iterative RTA aufgebohrt --flo
 569  *
 570  * Revision 1.4  2004/06/12 19:35:04  liekweg
 571  * Kommentare eingef"ugt --flo
 572  *
 573  * Revision 1.3  2004/06/12 17:09:46  liekweg
 574  * RTA works, outedges breaks.  "Yay." --flo
 575  *
 576  * Revision 1.2  2004/06/11 18:25:39  liekweg
 577  * Added todo
 578  *
 579  * Revision 1.1  2004/06/11 18:24:18  liekweg
 580  * Added RTA --flo
 581  *
 582  */