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 (get_SymConst_kind(ptr) == symconst_addr_ent) {
 170         ent = get_SymConst_entity (ptr);
 171         ir_graph *graph = get_entity_irg (ent);
 172         /* don't use get_implementing_graph on a Const! */
 173         if (graph) {
 174           *change = add_graph (graph);
 175         } else {
 176           /* it's an externally allocated thing. */
 177         }
 178       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
 179       /* If this SymConst refers to a method the method is external_visible
 180          and therefore must be considered live anyways. */
 181       /* assert (ent && "couldn't determine entity of call to symConst"); */
 182       } else {
 183         /* other symconst. */
 184       }
 185
 186     }
 187   } else if (iro_Alloc == op) { /* ALLOC */
 188     type *type = get_Alloc_type (node);
 189
 190     *change = add_class (type);
 191   }
 192 }
 193
 194 /**
 195    Traverse the given graph to collect method accesses and
 196    object allocations.
 197 */
 198 static int rta_fill_graph (ir_graph* graph)
 199 {
 200   int change = FALSE;
 201
 202   current_ir_graph = graph;
 203
 204   irg_walk (get_irg_end (graph), rta_act, NULL, &change);
 205
 206   return (change);
 207 }
 208
 209 /**
 210    Traverse all graphs to collect method accesses and object allocations.
 211
 212    @param rerun Whether to rely on is_alive in a second run
 213 */
 214 static int rta_fill_incremental (void)
 215 {
 216   int i;
 217   int n_runs = 0;
 218   int rerun  = TRUE;
 219   int old_ip_view = interprocedural_view;
 220
 221   interprocedural_view = 0;     /* save this for later */
 222
 223   /* init_tables has added main_irg to _live_graphs */
 224
 225   /* Need to take care of graphs that are externally
 226      visible or sticky. Pretend that they are called: */
 227
 228   for (i = 0; i < get_irp_n_irgs(); i++) {
 229     ir_graph *graph = get_irp_irg (i);
 230     entity *ent = get_irg_entity (graph);
 231
 232     if (((!whole_world) &&
 233          (visibility_external_visible == get_entity_visibility (ent))) ||
 234         (stickyness_sticky == get_entity_stickyness (ent))) {
 235       eset_insert (_live_graphs, graph);
 236     }
 237   }
 238
 239   while (rerun) {
 240     ir_graph *graph;
 241
 242     /* start off new */
 243     eset *live_graphs = _live_graphs;
 244     _live_graphs = eset_create ();
 245
 246     if (verbose > 1) {
 247       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 248     }
 249
 250     /* collect what we have found previously */
 251     eset_insert_all (_live_graphs, live_graphs);
 252
 253     rerun = FALSE;
 254
 255     for (graph = eset_first (live_graphs);
 256          graph;
 257          graph = eset_next (live_graphs)) {
 258
 259       if (verbose > 1) {
 260         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 261         DDMEO(get_irg_ent (graph));
 262       }
 263
 264       rerun |= rta_fill_graph (graph);
 265     }
 266
 267     eset_destroy (live_graphs);
 268
 269     n_runs ++;
 270   }
 271
 272   interprocedural_view = old_ip_view; /* cover up our traces */
 273
 274   return (n_runs);
 275 }
 276
 277 /*
 278    Count the number of graphs that we have found to be live.
 279 */
 280 static int stats (void)
 281 {
 282   int i;
 283   int n_live_graphs = 0;
 284   int n_graphs = get_irp_n_irgs();
 285
 286   for (i = 0; i < n_graphs; i++) {
 287     ir_graph *graph = get_irp_irg(i);
 288
 289     if (rta_is_alive_graph (graph)) {
 290       n_live_graphs ++;
 291     }
 292   }
 293
 294   return (n_live_graphs);
 295 }
 296
 297 /* remove a graph, part I */
 298 /*
 299    We removed the first graph to implement the entity, so we're
 300    abstract now.  Pretend that it wasn't there at all, and every
 301    entity that used to inherit this entity's graph is now abstract.
 302 */
 303 /* Since we *know* that this entity will not be called, this is OK. */
 304 static void force_description (entity *ent, entity *addr)
 305 {
 306   int i, n_over = get_entity_n_overwrittenby (ent);
 307
 308   set_entity_peculiarity (ent, peculiarity_description);
 309
 310   for (i = 0; i < n_over; i ++) {
 311     entity *over = get_entity_overwrittenby (ent, i);
 312
 313     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 314       /* We rely on the fact that cse is performed on the const_code_irg. */
 315       entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 316
 317       if (addr == my_addr) {
 318         force_description (over, addr);
 319       }
 320     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 321       /* check whether 'over' forces 'inheritance' of *our* graph: */
 322       ir_node *f_addr = get_atomic_ent_value (over);
 323       entity *impl_ent = get_SymConst_entity (f_addr);
 324
 325       assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
 326       if (impl_ent == addr) {
 327         assert (0 && "gibt's denn sowas");
 328         force_description (over, addr);
 329       }
 330     }
 331   }
 332 }
 333
 334 /* remove a graph, part II */
 335 /*
 336    Note: get_implementing_graph is not well defined here (graph->ent
 337    could overwrite more than one superclass implementation (graph).
 338    Since we *know* that this entity will not be called, this is OK.
 339 */
 340 static void remove_irg (ir_graph *graph)
 341 {
 342   entity *ent = get_irg_entity (graph);
 343   peculiarity pec = get_entity_peculiarity (ent);
 344
 345   /*   DDMEO (get_irg_ent(graph)); */
 346
 347   /* delete the ir_graph data */
 348   set_entity_peculiarity (ent, peculiarity_description);
 349   remove_irp_irg (graph);
 350   /* remove_irp_irg also removes the entities' reference to the graph */
 351   /*
 352     if (NULL != get_entity_irg (ent)) {
 353     set_entity_irg (ent, NULL);
 354     }
 355   */
 356   set_entity_peculiarity (ent, pec);
 357
 358   /* find the implementation (graph) from *some* superclass: */
 359   graph = get_implementing_graph (ent);
 360
 361   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 362     /* nothing to inherit!  pretend we're abstract */
 363     force_description (ent, ent);
 364   } else {
 365     /* pretend that we inherit the implementation (graph) from some superclass: */
 366     set_entity_peculiarity (ent, peculiarity_inherited);
 367
 368     exchange (get_atomic_ent_value (ent),
 369               get_atomic_ent_value (get_irg_ent(graph)));
 370   }
 371 }
 372
 373 /**
 374    Initialise the static data structures.
 375 */
 376 static void init_tables (void)
 377 {
 378   _live_classes   = eset_create ();
 379
 380   _live_graphs = eset_create ();
 381
 382   if (get_irp_main_irg ()) {
 383     eset_insert (_live_graphs, get_irp_main_irg ());
 384   }
 385
 386   /* Adding the GlobalType is pointless, since its methods are always
 387      called via a constant */
 388   /*
 389   if (get_glob_type ()) {
 390     eset_insert (_live_classes, get_glob_type ());
 391   }
 392   */
 393 }
 394
 395 /* Initialise the RTA data structures, and perform RTA.
 396    @param   do_verbose If == 1, print statistics, if > 1, chatter about every detail
 397    @param   do_whole_world Iff != 0, assume whole-world
 398 */
 399 void rta_init (int do_verbose, int do_whole_world)
 400 {
 401   int n_runs = 0;
 402
 403 # ifdef DEBUG_libfirm
 404   int i;
 405   for (i = 0; i < get_irp_n_irgs(); i++) {
 406     irg_vrfy (get_irp_irg(i));
 407   }
 408   tr_vrfy ();
 409 # endif /* defined DEBUG_libfirm */
 410
 411   whole_world = do_whole_world;
 412   verbose = do_verbose;
 413
 414   init_tables ();
 415
 416   n_runs = rta_fill_incremental ();
 417
 418   if (verbose) {
 419     int n_live_graphs = stats ();
 420
 421     if (whole_world) {
 422       printf ("RTA: whole-world assumption\n");
 423     }
 424     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 425     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 426     printf ("RTA: n_runs        = %i\n", n_runs);
 427   }
 428
 429 # ifdef DEBUG_libfirm
 430   for (i = 0; i < get_irp_n_irgs(); i++) {
 431     irg_vrfy (get_irp_irg(i));
 432   }
 433   tr_vrfy ();
 434 # endif /* defined DEBUG_libfirm */
 435 }
 436
 437 /* Delete all graphs that we have found to be dead from the program
 438    If verbose == 1, print statistics, if > 1, chatter about every detail
 439 */
 440 void rta_delete_dead_graphs (void)
 441 {
 442   int i;
 443   int n_graphs = get_irp_n_irgs ();
 444   ir_graph *graph = NULL;
 445   int n_dead_graphs = 0;
 446
 447   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 448
 449   eset *dead_graphs = eset_create ();
 450
 451   for (i = 0; i < n_graphs; i++) {
 452     graph = get_irp_irg(i);
 453
 454     if (rta_is_alive_graph (graph)) {
 455       /* do nothing (except some debugging fprintf`s :-) */
 456     } else {
 457 # ifdef DEBUG_libfirm
 458       entity *ent = get_irg_entity (graph);
 459       assert (whole_world ||
 460               (visibility_external_visible != get_entity_visibility (ent)));
 461 # endif /* defined DEBUG_libfirm */
 462
 463       n_dead_graphs ++;
 464       eset_insert (dead_graphs, graph);
 465     }
 466   }
 467
 468   /* now delete the graphs. */
 469   for (graph = eset_first (dead_graphs);
 470        graph;
 471        graph = (ir_graph*) eset_next (dead_graphs)) {
 472
 473     if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
 474       fprintf(stdout, "RTA: removing graph of ");
 475       DDMEO(get_irg_ent (graph));
 476     }
 477
 478     remove_irg (graph);
 479   }
 480
 481   if (verbose) {
 482     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 483   }
 484 }
 485
 486 /* Clean up the RTA data structures.  Call this after calling rta_init */
 487 void rta_cleanup (void)
 488 {
 489 # ifdef DEBUG_libfirm
 490   int i;
 491     for (i = 0; i < get_irp_n_irgs(); i++) {
 492       irg_vrfy (get_irp_irg(i));
 493     }
 494     tr_vrfy ();
 495 # endif /* defined DEBUG_libfirm */
 496
 497   if (_live_classes) {
 498     eset_destroy (_live_classes);
 499     _live_classes = NULL;
 500   }
 501
 502   if (_live_graphs) {
 503     eset_destroy (_live_graphs);
 504     _live_graphs = NULL;
 505   }
 506 }
 507
 508 /* Say whether this class might be instantiated at any point in the program: */
 509 int  rta_is_alive_class  (type   *clazz)
 510 {
 511   return (eset_contains (_live_classes, clazz));
 512 }
 513
 514 /* Say whether this graph might be run at any time in the program: */
 515 int  rta_is_alive_graph (ir_graph *graph)
 516 {
 517   if (eset_contains (_live_graphs, graph)) {
 518     return (TRUE);
 519   }
 520
 521   return (FALSE);
 522 }
 523
 524 /* dump our opinion */
 525 void rta_report (void)
 526 {
 527   int i;
 528
 529   for (i = 0; i < get_irp_n_types(); ++i) {
 530     type *tp = get_irp_type(i);
 531     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 532       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 533     }
 534   }
 535
 536   for (i = 0; i < get_irp_n_irgs(); i++) {
 537     if (rta_is_alive_graph (get_irp_irg(i))) {
 538       fprintf(stdout, "RTA: considered called: graph of ");
 539       DDMEO(get_irg_ent (get_irp_irg(i)));
 540     }
 541   }
 542 }
 543
 544
 545 /*
 546  * $Log$
 547  * Revision 1.19  2004/07/06 12:30:37  beyhan
 548  * new SymConst semantics
 549  *
 550  * Revision 1.18  2004/06/27 21:17:41  liekweg
 551  * Added comment
 552  *
 553  * Revision 1.17  2004/06/25 13:45:13  liekweg
 554  * observe stickyness; minor refactoring
 555  *
 556  * Revision 1.16  2004/06/24 06:42:14  goetz
 557  * test of firm flags
 558  *
 559  * Revision 1.15  2004/06/18 15:47:19  liekweg
 560  * minor bug fix (go forward, not backward) --flo
 561  *
 562  * Revision 1.14  2004/06/18 13:12:43  liekweg
 563  * final bug fix (calls via consts)
 564  *
 565  * Revision 1.13  2004/06/17 16:34:33  liekweg
 566  * removed DD*s
 567  *
 568  * Revision 1.12  2004/06/17 16:33:33  liekweg
 569  * minor bug fix
 570  *
 571  * Revision 1.11  2004/06/17 14:21:13  liekweg
 572  * major bugfix
 573  *
 574  * Revision 1.10  2004/06/17 10:31:41  goetz
 575  * irscc: bugfix, can now deal with loops not reachable from start
 576  * cgana: bugfix, skip_Tuple
 577  * rta: improved
 578  *
 579  * Revision 1.9  2004/06/17 08:56:03  liekweg
 580  * Fixed typos in comments
 581  *
 582  * Revision 1.8  2004/06/17 08:33:01  liekweg
 583  * Added comments; added remove_irg
 584  *
 585  * Revision 1.6  2004/06/14 13:02:03  goetz
 586  * bugfixesbug
 587  *
 588  * Revision 1.5  2004/06/13 15:03:45  liekweg
 589  * RTA auf Iterative RTA aufgebohrt --flo
 590  *
 591  * Revision 1.4  2004/06/12 19:35:04  liekweg
 592  * Kommentare eingef"ugt --flo
 593  *
 594  * Revision 1.3  2004/06/12 17:09:46  liekweg
 595  * RTA works, outedges breaks.  "Yay." --flo
 596  *
 597  * Revision 1.2  2004/06/11 18:25:39  liekweg
 598  * Added todo
 599  *
 600  * Revision 1.1  2004/06/11 18:24:18  liekweg
 601  * Added RTA --flo
 602  *
 603  */