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:      $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 #ifdef HAVE_CONFIG_H
  17 # include "config.h"
  18 #endif
  19
  20 #include "rta.h"
  21
  22 #include <stdlib.h>
  23
  24 #include "irnode_t.h"
  25 #include "irprog_t.h"
  26 #include "irgraph_t.h"
  27
  28 #include "eset.h"
  29 #include "irgwalk.h"
  30 #include "irgmod.h"
  31 #include "typewalk.h"
  32 #include "irvrfy.h"
  33 #include "trvrfy.h"
  34
  35 # ifndef TRUE
  36 #  define TRUE 1
  37 #  define FALSE 0
  38 # endif /* not defined TRUE */
  39
  40 /* flags */
  41 static int verbose     = 0;
  42
  43
  44 /* base data */
  45 static eset *_live_classes   = NULL;
  46
  47 /* cache computed results */
  48 static eset *_live_graphs    = NULL;
  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 #if 0
  56   ir_graph *graph = get_entity_irg ((entity*) method);
  57
  58   /* Search upwards in the overwrites graph. */
  59   /* GL: this will not work for multiple inheritance */
  60   if (NULL == graph) {
  61     int i;
  62     int n_over = get_entity_n_overwrites ((entity*) method);
  63
  64     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
  65       entity *over = get_entity_overwrites ((entity*) method, i);
  66       graph = get_implementing_graph (over);
  67     }
  68   }
  69
  70   /* GL   this is not valid in our remove irg algorithm ... which we removed by now ...  */
  71   assert(get_entity_peculiarity(method) == peculiarity_description
  72      || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
  73
  74   /* we *must* always return a graph != NULL, *except* when we're used
  75      inside remove_irg or force_description */
  76   /* assert (graph && "no graph"); */
  77
  78   return (graph);
  79 #else
  80   ir_graph *graph = NULL;
  81
  82   if (get_entity_peculiarity(method) != peculiarity_description)
  83     graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
  84
  85   return graph;
  86 #endif
  87 }
  88
  89 /**
  90  * Add a graph to the set of live graphs.
  91  *
  92  * @param graph  the graph to add
  93  * @return non-zero if the graph was added, zero
  94  *         if it was already in the live set
  95  */
  96 static int add_graph (ir_graph *graph)
  97 {
  98   if (!eset_contains (_live_graphs, graph)) {
  99     if (verbose > 1) {
 100       fprintf(stdout, "RTA:        new graph of ");
 101       DDMEO(get_irg_entity (graph));
 102     }
 103
 104     eset_insert (_live_graphs, graph);
 105     return (TRUE);
 106   }
 107
 108   return (FALSE);
 109 }
 110
 111 /**
 112  * Add a class to the set of live classes.
 113  *
 114  * @param clazz   the class to add
 115  * @return non-zero if the graph was added, zero
 116  *         if it was already in the live set
 117  */
 118 static int add_class (ir_type *clazz)
 119 {
 120   if (!eset_contains (_live_classes, clazz)) {
 121     if (verbose > 1) {
 122       fprintf(stdout, "RTA:        new class: ");
 123       DDMT(clazz);
 124     }
 125
 126     eset_insert (_live_classes, clazz);
 127     return (TRUE);
 128   }
 129
 130   return (FALSE);
 131 }
 132
 133 /** Given an entity, add all implementing graphs that belong to live classes
 134  *  to _live_graphs.
 135  *
 136  *  Iff additions occurred, return TRUE, else FALSE.
 137 */
 138 static int add_implementing_graphs (entity *method)
 139 {
 140   int i;
 141   int n_over = get_entity_n_overwrittenby (method);
 142   ir_graph *graph = get_entity_irg (method);
 143   int change = FALSE;
 144
 145   if (NULL == graph) {
 146     graph = get_implementing_graph (method);
 147   }
 148
 149   if (verbose > 1) {
 150     fprintf(stdout, "RTA:        new call to ");
 151     DDMEO(method);
 152   }
 153
 154   if (rta_is_alive_class (get_entity_owner (method))) {
 155     if (NULL != graph) {
 156       change = add_graph (graph);
 157     }
 158   }
 159
 160   for (i = 0; i < n_over; i ++) {
 161     entity *over = get_entity_overwrittenby (method, i);
 162     change |= add_implementing_graphs (over);
 163   }
 164
 165   return (change);
 166 }
 167
 168 /** Enter all method accesses and all class allocations into
 169  *  our tables.
 170  *
 171  *  Set *(int*)env to true iff (possibly) new graphs have been found.
 172  */
 173 static void rta_act (ir_node *node, void *env)
 174 {
 175   int *change = (int*) env;
 176   opcode op = get_irn_opcode (node);
 177
 178   if (iro_Call == op) {         /* CALL */
 179     entity *ent = NULL;
 180
 181     ir_node *ptr = get_Call_ptr (node);
 182
 183     /* CALL SEL */
 184     if (iro_Sel == get_irn_opcode (ptr)) {
 185       ent = get_Sel_entity (ptr);
 186       *change |= add_implementing_graphs (ent);
 187
 188       /* CALL SYMCONST */
 189     } else if (iro_SymConst == get_irn_opcode (ptr)) {
 190       if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 191         ir_graph *graph;
 192
 193         ent = get_SymConst_entity (ptr);
 194         graph = get_entity_irg (ent);
 195         if (graph) {
 196           *change |= add_graph (graph);
 197         } else {
 198           /* it's an external allocated thing. */
 199         }
 200       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
 201             /* Entities of kind addr_name may not be allocated in this compilation unit.
 202                If so, the frontend built faulty Firm.  So just ignore. */
 203             /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
 204         assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
 205       } else {
 206         /* other symconst. */
 207         assert(0 && "This SymConst can not be an address for a method call.");
 208       }
 209
 210       /* STRANGE */
 211     } else {
 212       DDMN(ptr);
 213       assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
 214     }
 215
 216   } else if (iro_Alloc == op) { /* ALLOC */
 217     ir_type *type = get_Alloc_type (node);
 218
 219     *change |= add_class (type);
 220   }
 221 }
 222
 223 /**
 224    Traverse the given graph to collect method accesses and
 225    object allocations.
 226 */
 227 static int rta_fill_graph (ir_graph* graph)
 228 {
 229   int change = FALSE;
 230   irg_walk_graph (graph, rta_act, NULL, &change);
 231   return change;
 232 }
 233
 234 /** Traverse all graphs to collect method accesses and object allocations.
 235  */
 236 static int rta_fill_incremental (void)
 237 {
 238   int i;
 239   int n_runs = 0;
 240   int rerun  = TRUE;
 241   int old_ip_view = get_interprocedural_view();
 242
 243   set_interprocedural_view(0);     /* save this for later */
 244
 245   /* init_tables has added main_irg to _live_graphs */
 246
 247   /* Need to take care of graphs that are externally
 248      visible or sticky. Pretend that they are called: */
 249
 250   for (i = 0; i < get_irp_n_irgs(); i++) {
 251     ir_graph *graph = get_irp_irg (i);
 252     entity *ent = get_irg_entity (graph);
 253
 254     if ((visibility_external_visible == get_entity_visibility (ent)) ||
 255         (stickyness_sticky == get_entity_stickyness (ent))) {
 256       eset_insert (_live_graphs, graph);
 257       // printf("external visible: "); DDMG(graph);
 258     }
 259   }
 260
 261   while (rerun) {
 262     ir_graph *graph;
 263
 264     /* start off new */
 265     eset *live_graphs = _live_graphs;
 266     _live_graphs = eset_create ();
 267
 268     if (verbose > 1) {
 269       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 270     }
 271
 272     /* collect what we have found previously */
 273     eset_insert_all (_live_graphs, live_graphs);
 274
 275     rerun = FALSE;
 276     for (graph = eset_first (live_graphs);
 277          graph;
 278          graph = eset_next (live_graphs)) {
 279
 280       if (verbose > 1) {
 281         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 282         DDMEO(get_irg_entity (graph));
 283       }
 284
 285       rerun |= rta_fill_graph (graph);
 286     }
 287
 288     eset_destroy (live_graphs);
 289
 290     n_runs ++;
 291   }
 292
 293   set_interprocedural_view(old_ip_view); /* cover up our traces */
 294
 295   return (n_runs);
 296 }
 297
 298 /**
 299  * Count the number of graphs that we have found to be live.
 300  */
 301 static int stats (void)
 302 {
 303   int i;
 304   int n_live_graphs = 0;
 305   int n_graphs = get_irp_n_irgs();
 306
 307   for (i = 0; i < n_graphs; i++) {
 308     ir_graph *graph = get_irp_irg(i);
 309
 310     if (rta_is_alive_graph (graph)) {
 311       n_live_graphs ++;
 312     }
 313   }
 314
 315   return (n_live_graphs);
 316 }
 317
 318 /* remove a graph, part I */
 319 /*
 320    We removed the first graph to implement the entity, so we're
 321    abstract now.  Pretend that it wasn't there at all, and every
 322    entity that used to inherit this entity's graph is now abstract.
 323 */
 324 /* Since we *know* that this entity will not be called, this is OK. */
 325 static void force_description (entity *ent, entity *addr)
 326 {
 327   int i, n_over = get_entity_n_overwrittenby (ent);
 328
 329   set_entity_peculiarity (ent, peculiarity_description);
 330
 331   for (i = 0; i < n_over; i ++) {
 332     entity *over = get_entity_overwrittenby (ent, i);
 333
 334     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 335       /* We rely on the fact that cse is performed on the const_code_irg. */
 336       entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 337
 338       if (addr == my_addr) {
 339         force_description (over, addr);
 340       }
 341     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 342       /* check whether 'over' forces 'inheritance' of *our* graph: */
 343       ir_node *f_addr = get_atomic_ent_value (over);
 344       entity *impl_ent = get_SymConst_entity (f_addr);
 345
 346       assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
 347       if (impl_ent == addr) {
 348         assert (0 && "gibt's denn sowas");
 349         force_description (over, addr);
 350       }
 351     }
 352   }
 353 }
 354
 355 /**
 356    Initialize the static data structures.
 357 */
 358 static void init_tables (void)
 359 {
 360   ir_type *tp;
 361   int i, n;
 362
 363   _live_classes = eset_create ();
 364   _live_graphs  = eset_create ();
 365
 366   if (get_irp_main_irg ()) {
 367     eset_insert (_live_graphs, get_irp_main_irg ());
 368   }
 369
 370   /* Find static allocated classes */
 371   tp = get_glob_type();
 372   n = get_class_n_members(tp);
 373   for (i = 0; i < n; ++i) {
 374     ir_type *member_type = get_entity_type(get_class_member(tp, i));
 375     if (is_Class_type(member_type))
 376       eset_insert(_live_classes, member_type);
 377   }
 378
 379   tp = get_tls_type();
 380   n = get_struct_n_members(tp);
 381   for (i = 0; i < n; ++i) {
 382     ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 383     if (is_Class_type(member_type))
 384       eset_insert(_live_classes, member_type);
 385   }
 386 }
 387
 388 /*
 389  * Initialize the RTA data structures, and perform RTA.
 390  * do_verbose If == 1, print statistics, if > 1, chatter about every detail
 391  */
 392 void rta_init (int do_verbose)
 393 {
 394   int n_runs = 0;
 395
 396   int rem_vpi = get_visit_pseudo_irgs();
 397   set_visit_pseudo_irgs(1);
 398
 399 # ifdef DEBUG_libfirm
 400   {
 401   int i, n;
 402   n = get_irp_n_irgs();
 403   for (i = 0; i < n; i++) {
 404     irg_vrfy (get_irp_irg(i));
 405   }
 406   tr_vrfy ();
 407   }
 408 # endif /* defined DEBUG_libfirm */
 409
 410   verbose = do_verbose;
 411
 412   init_tables ();
 413
 414   n_runs = rta_fill_incremental ();
 415
 416   if (verbose) {
 417     int n_live_graphs = stats ();
 418
 419     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 420     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 421     printf ("RTA: n_runs        = %i\n", n_runs);
 422   }
 423
 424 # ifdef DEBUG_libfirm
 425   {
 426   int n, i;
 427   for (i = 0; i < n; i++) {
 428     irg_vrfy (get_irp_irg(i));
 429   }
 430   tr_vrfy ();
 431   }
 432 # endif /* defined DEBUG_libfirm */
 433
 434   set_visit_pseudo_irgs(rem_vpi);
 435 }
 436
 437 /**
 438  * walker for all types and entities
 439  *
 440  * Changes the peculiarity of entities that represents
 441  * dead graphs to peculiarity_description.
 442  */
 443 static void make_entity_to_description(type_or_ent *tore, void *env) {
 444   if (get_kind(tore) == k_entity) {
 445     entity *ent = (entity *)tore;
 446
 447     if ((is_Method_type(get_entity_type(ent)))                        &&
 448         (get_entity_peculiarity(ent) != peculiarity_description)      &&
 449         (get_entity_visibility(ent)  != visibility_external_allocated)   ) {
 450       ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
 451       if (!eset_contains (_live_graphs, irg)) {
 452         set_entity_peculiarity(ent, peculiarity_description);
 453         set_entity_irg(ent, NULL);
 454       }
 455     }
 456   }
 457 }
 458
 459 /* Delete all graphs that we have found to be dead from the program
 460    If verbose == 1, print statistics, if > 1, chatter about every detail
 461 */
 462 void rta_delete_dead_graphs (void)
 463 {
 464   int i;
 465   int n_graphs = get_irp_n_irgs ();
 466   ir_graph *graph = NULL;
 467   int n_dead_graphs = 0;
 468   ir_graph **dead_graphs;
 469
 470   int rem_vpi = get_visit_pseudo_irgs();
 471   set_visit_pseudo_irgs(1);
 472
 473   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 474
 475   dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
 476
 477   for (i = 0; i < n_graphs; i++) {
 478     graph = get_irp_irg(i);
 479
 480     if (rta_is_alive_graph (graph)) {
 481       /* do nothing (except some debugging fprintf`s :-) */
 482     } else {
 483 # ifdef DEBUG_libfirm
 484       entity *ent = get_irg_entity (graph);
 485       assert (visibility_external_visible != get_entity_visibility (ent));
 486 # endif /* defined DEBUG_libfirm */
 487
 488       dead_graphs[n_dead_graphs] = graph;
 489       n_dead_graphs ++;
 490     }
 491   }
 492
 493   type_walk(make_entity_to_description, NULL, NULL);
 494   for (i = 0; i < n_dead_graphs; ++i) {
 495     remove_irp_irg (dead_graphs[i]);
 496   }
 497
 498   if (verbose) {
 499     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 500   }
 501
 502   set_visit_pseudo_irgs(rem_vpi);
 503
 504   free(dead_graphs);
 505 }
 506
 507 /* Clean up the RTA data structures.  Call this after calling rta_init */
 508 void rta_cleanup (void)
 509 {
 510 # ifdef DEBUG_libfirm
 511   int i;
 512     for (i = 0; i < get_irp_n_irgs(); i++) {
 513       irg_vrfy (get_irp_irg(i));
 514     }
 515     tr_vrfy ();
 516 # endif /* defined DEBUG_libfirm */
 517
 518   if (_live_classes) {
 519     eset_destroy (_live_classes);
 520     _live_classes = NULL;
 521   }
 522
 523   if (_live_graphs) {
 524     eset_destroy (_live_graphs);
 525     _live_graphs = NULL;
 526   }
 527 }
 528
 529 /* Say whether this class might be instantiated at any point in the program: */
 530 int  rta_is_alive_class  (ir_type   *clazz)
 531 {
 532   return (eset_contains (_live_classes, clazz));
 533 }
 534
 535 /* Say whether this graph might be run at any time in the program: */
 536 int  rta_is_alive_graph (ir_graph *graph)
 537 {
 538   return eset_contains (_live_graphs, graph);
 539 }
 540
 541 /* dump our opinion */
 542 void rta_report (void)
 543 {
 544   int i;
 545
 546   for (i = 0; i < get_irp_n_types(); ++i) {
 547     ir_type *tp = get_irp_type(i);
 548     if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 549       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 550     }
 551   }
 552
 553   for (i = 0; i < get_irp_n_irgs(); i++) {
 554     if (rta_is_alive_graph (get_irp_irg(i))) {
 555       fprintf(stdout, "RTA: considered called: graph of ");
 556       DDMEO(get_irg_entity (get_irp_irg(i)));
 557     }
 558   }
 559 }
 560
 561
 562 /*
 563  * $Log$
 564  * Revision 1.37  2006/12/11 15:28:48  matze
 565  * - Several warning fixes
 566  * - Fixes for compilation without DEBUG_libfirm
 567  * - Fixed for compilation without WITH_LIBCORE (but it's still broken)
 568  *
 569  * Revision 1.36  2006/06/05 15:58:12  beck
 570  * added support for Thread local storage
 571  * added more doxygen docu
 572  *
 573  * Revision 1.35  2006/01/13 21:51:59  beck
 574  * renamed all types 'type' to 'ir_type'
 575  *
 576  * Revision 1.34  2006/01/02 15:01:16  beck
 577  * missing include added
 578  *
 579  * Revision 1.33  2005/11/17 17:26:57  beck
 580  * removed bool type and depency from stdbool.h (not C89)
 581  *
 582  * Revision 1.32  2005/01/05 14:24:52  beck
 583  * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
 584  *
 585  * Revision 1.31  2004/12/21 13:45:14  beck
 586  * removed C99 constructs
 587  *
 588  * Revision 1.30  2004/12/02 16:16:11  beck
 589  * fixed config.h include
 590  * used xmalloc instead of malloc
 591  *
 592  * Revision 1.29  2004/11/11 13:28:08  goetz
 593  * made pseudo irg aware
 594  *
 595  * Revision 1.28  2004/11/03 14:47:18  beck
 596  * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
 597  *
 598  * Revision 1.27  2004/10/21 07:23:34  goetz
 599  * comments
 600  *
 601  * Revision 1.26  2004/10/20 14:59:27  liekweg
 602  * Removed ecg
 603  *
 604  * Revision 1.25  2004/10/18 12:47:08  liekweg
 605  * avoid warning
 606  *
 607  * Revision 1.24  2004/09/24 13:59:04  beck
 608  * fixed doxygen comments, removed initialization for description entities
 609  *
 610  * Revision 1.23  2004/08/19 16:51:02  goetz
 611  * fixed some errors, pushed closer to inteded firm semantics
 612  *
 613  * Revision 1.22  2004/08/13 08:57:15  beyhan
 614  * normalized names of functions, enums ...
 615  * added suffix as argument to dumpers, removed global variable
 616  * removed support for tarval/Const
 617  *
 618  * Revision 1.21  2004/07/08 15:50:56  goetz
 619  * firmstat added
 620  *
 621  * Revision 1.20  2004/07/08 11:17:40  goetz
 622  * *** empty log message ***
 623  *
 624  * Revision 1.19  2004/07/06 12:30:37  beyhan
 625  * new SymConst semantics
 626  *
 627  * Revision 1.18  2004/06/27 21:17:41  liekweg
 628  * Added comment
 629  *
 630  * Revision 1.17  2004/06/25 13:45:13  liekweg
 631  * observe stickyness; minor refactoring
 632  *
 633  * Revision 1.16  2004/06/24 06:42:14  goetz
 634  * test of firm flags
 635  *
 636  * Revision 1.15  2004/06/18 15:47:19  liekweg
 637  * minor bug fix (go forward, not backward) --flo
 638  *
 639  * Revision 1.14  2004/06/18 13:12:43  liekweg
 640  * final bug fix (calls via consts)
 641  *
 642  * Revision 1.13  2004/06/17 16:34:33  liekweg
 643  * removed DD*s
 644  *
 645  * Revision 1.12  2004/06/17 16:33:33  liekweg
 646  * minor bug fix
 647  *
 648  * Revision 1.11  2004/06/17 14:21:13  liekweg
 649  * major bugfix
 650  *
 651  * Revision 1.10  2004/06/17 10:31:41  goetz
 652  * irscc: bugfix, can now deal with loops not reachable from start
 653  * cgana: bugfix, skip_Tuple
 654  * rta: improved
 655  *
 656  * Revision 1.9  2004/06/17 08:56:03  liekweg
 657  * Fixed typos in comments
 658  *
 659  * Revision 1.8  2004/06/17 08:33:01  liekweg
 660  * Added comments; added remove_irg
 661  *
 662  * Revision 1.6  2004/06/14 13:02:03  goetz
 663  * bugfixesbug
 664  *
 665  * Revision 1.5  2004/06/13 15:03:45  liekweg
 666  * RTA auf Iterative RTA aufgebohrt --flo
 667  *
 668  * Revision 1.4  2004/06/12 19:35:04  liekweg
 669  * Kommentare eingef"ugt --flo
 670  *
 671  * Revision 1.3  2004/06/12 17:09:46  liekweg
 672  * RTA works, outedges breaks.  "Yay." --flo
 673  *
 674  * Revision 1.2  2004/06/11 18:25:39  liekweg
 675  * Added todo
 676  *
 677  * Revision 1.1  2004/06/11 18:24:18  liekweg
 678  * Added RTA --flo
 679  *
 680  */