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 is 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 eine Abschätzung
  18  * der aufgerufenen Methoden 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   /* Adding the GlobalType is pointless, since its methods are always
 374      called via a constant */
 375   /*
 376   if (get_glob_type ()) {
 377     eset_insert (_live_classes, get_glob_type ());
 378   }
 379   */
 380 }
 381
 382 /* Initialise the RTA data structures, and perform RTA.
 383    @param   do_verbose If == 1, print statistics, if > 1, chatter about every detail
 384    @param   do_whole_world Iff != 0, assume whole-world
 385 */
 386 void rta_init (int do_verbose, int do_whole_world)
 387 {
 388   int n_runs = 0;
 389
 390 # ifdef DEBUG_libfirm
 391   int i;
 392   for (i = 0; i < get_irp_n_irgs(); i++) {
 393     irg_vrfy (get_irp_irg(i));
 394   }
 395   tr_vrfy ();
 396 # endif /* defined DEBUG_libfirm */
 397
 398   whole_world = do_whole_world;
 399   verbose = do_verbose;
 400
 401   init_tables ();
 402
 403   n_runs = rta_fill_incremental ();
 404
 405   if (verbose) {
 406     int n_live_graphs = stats ();
 407
 408     if (whole_world) {
 409       printf ("RTA: whole-world assumption\n");
 410     }
 411     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 412     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 413     printf ("RTA: n_runs        = %i\n", n_runs);
 414   }
 415
 416 # ifdef DEBUG_libfirm
 417   for (i = 0; i < get_irp_n_irgs(); i++) {
 418     irg_vrfy (get_irp_irg(i));
 419   }
 420   tr_vrfy ();
 421 # endif /* defined DEBUG_libfirm */
 422 }
 423
 424 /* Delete all graphs that we have found to be dead from the program
 425    If verbose == 1, print statistics, if > 1, chatter about every detail
 426 */
 427 void rta_delete_dead_graphs (void)
 428 {
 429   int i;
 430   int n_graphs = get_irp_n_irgs ();
 431   ir_graph *graph = NULL;
 432   int n_dead_graphs = 0;
 433
 434   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 435
 436   eset *dead_graphs = eset_create ();
 437
 438   for (i = 0; i < n_graphs; i++) {
 439     graph = get_irp_irg(i);
 440
 441     if (rta_is_alive_graph (graph)) {
 442       /* do nothing (except some debugging fprintf`s :-) */
 443     } else {
 444 # ifdef DEBUG_libfirm
 445       entity *ent = get_irg_entity (graph);
 446       assert (whole_world ||
 447               (visibility_external_visible != get_entity_visibility (ent)));
 448 # endif /* defined DEBUG_libfirm */
 449
 450       n_dead_graphs ++;
 451       eset_insert (dead_graphs, graph);
 452     }
 453   }
 454
 455   /* now delete the graphs. */
 456   for (graph = eset_first (dead_graphs);
 457        graph;
 458        graph = (ir_graph*) eset_next (dead_graphs)) {
 459
 460     if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
 461       fprintf(stdout, "RTA: removing graph of ");
 462       DDMEO(get_irg_ent (graph));
 463     }
 464
 465     remove_irg (graph);
 466   }
 467
 468   if (verbose) {
 469     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 470   }
 471 }
 472
 473 /* Clean up the RTA data structures.  Call this after calling rta_init */
 474 void rta_cleanup (void)
 475 {
 476 # ifdef DEBUG_libfirm
 477   int i;
 478     for (i = 0; i < get_irp_n_irgs(); i++) {
 479       irg_vrfy (get_irp_irg(i));
 480     }
 481     tr_vrfy ();
 482 # endif /* defined DEBUG_libfirm */
 483
 484   if (_live_classes) {
 485     eset_destroy (_live_classes);
 486     _live_classes = NULL;
 487   }
 488
 489   if (_live_graphs) {
 490     eset_destroy (_live_graphs);
 491     _live_graphs = NULL;
 492   }
 493 }
 494
 495 /* Say whether this class might be instantiated at any point in the program: */
 496 int  rta_is_alive_class  (type   *clazz)
 497 {
 498   return (eset_contains (_live_classes, clazz));
 499 }
 500
 501 /* Say whether this graph might be run at any time in the program: */
 502 int  rta_is_alive_graph (ir_graph *graph)
 503 {
 504   if (eset_contains (_live_graphs, graph)) {
 505     return (TRUE);
 506   }
 507
 508   return (FALSE);
 509 }
 510
 511 /* dump our opinion */
 512 void rta_report (void)
 513 {
 514   int i;
 515
 516   for (i = 0; i < get_irp_n_types(); ++i) {
 517     type *tp = get_irp_type(i);
 518     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 519       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 520     }
 521   }
 522
 523   for (i = 0; i < get_irp_n_irgs(); i++) {
 524     if (rta_is_alive_graph (get_irp_irg(i))) {
 525       fprintf(stdout, "RTA: considered called: graph of ");
 526       DDMEO(get_irg_ent (get_irp_irg(i)));
 527     }
 528   }
 529 }
 530
 531
 532 /*
 533  * $Log$
 534  * Revision 1.18  2004/06/27 21:17:41  liekweg
 535  * Added comment
 536  *
 537  * Revision 1.17  2004/06/25 13:45:13  liekweg
 538  * observe stickyness; minor refactoring
 539  *
 540  * Revision 1.16  2004/06/24 06:42:14  goetz
 541  * test of firm flags
 542  *
 543  * Revision 1.15  2004/06/18 15:47:19  liekweg
 544  * minor bug fix (go forward, not backward) --flo
 545  *
 546  * Revision 1.14  2004/06/18 13:12:43  liekweg
 547  * final bug fix (calls via consts)
 548  *
 549  * Revision 1.13  2004/06/17 16:34:33  liekweg
 550  * removed DD*s
 551  *
 552  * Revision 1.12  2004/06/17 16:33:33  liekweg
 553  * minor bug fix
 554  *
 555  * Revision 1.11  2004/06/17 14:21:13  liekweg
 556  * major bugfix
 557  *
 558  * Revision 1.10  2004/06/17 10:31:41  goetz
 559  * irscc: bugfix, can now deal with loops not reachable from start
 560  * cgana: bugfix, skip_Tuple
 561  * rta: improved
 562  *
 563  * Revision 1.9  2004/06/17 08:56:03  liekweg
 564  * Fixed typos in comments
 565  *
 566  * Revision 1.8  2004/06/17 08:33:01  liekweg
 567  * Added comments; added remove_irg
 568  *
 569  * Revision 1.6  2004/06/14 13:02:03  goetz
 570  * bugfixesbug
 571  *
 572  * Revision 1.5  2004/06/13 15:03:45  liekweg
 573  * RTA auf Iterative RTA aufgebohrt --flo
 574  *
 575  * Revision 1.4  2004/06/12 19:35:04  liekweg
 576  * Kommentare eingef"ugt --flo
 577  *
 578  * Revision 1.3  2004/06/12 17:09:46  liekweg
 579  * RTA works, outedges breaks.  "Yay." --flo
 580  *
 581  * Revision 1.2  2004/06/11 18:25:39  liekweg
 582  * Added todo
 583  *
 584  * Revision 1.1  2004/06/11 18:24:18  liekweg
 585  * Added RTA --flo
 586  *
 587  */