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 i, n, n_runs = 0;
 395
 396   int rem_vpi = get_visit_pseudo_irgs();
 397   set_visit_pseudo_irgs(1);
 398
 399 # ifdef DEBUG_libfirm
 400   n = get_irp_n_irgs();
 401   for (i = 0; i < n; i++) {
 402     irg_vrfy (get_irp_irg(i));
 403   }
 404   tr_vrfy ();
 405 # endif /* defined DEBUG_libfirm */
 406
 407   verbose = do_verbose;
 408
 409   init_tables ();
 410
 411   n_runs = rta_fill_incremental ();
 412
 413   if (verbose) {
 414     int n_live_graphs = stats ();
 415
 416     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 417     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 418     printf ("RTA: n_runs        = %i\n", n_runs);
 419   }
 420
 421 # ifdef DEBUG_libfirm
 422   for (i = 0; i < n; i++) {
 423     irg_vrfy (get_irp_irg(i));
 424   }
 425   tr_vrfy ();
 426 # endif /* defined DEBUG_libfirm */
 427
 428   set_visit_pseudo_irgs(rem_vpi);
 429 }
 430
 431 /**
 432  * walker for all types and entities
 433  *
 434  * Changes the peculiarity of entities that represents
 435  * dead graphs to peculiarity_description.
 436  */
 437 static void make_entity_to_description(type_or_ent *tore, void *env) {
 438   if (get_kind(tore) == k_entity) {
 439     entity *ent = (entity *)tore;
 440
 441     if ((is_Method_type(get_entity_type(ent)))                        &&
 442         (get_entity_peculiarity(ent) != peculiarity_description)      &&
 443         (get_entity_visibility(ent)  != visibility_external_allocated)   ) {
 444       ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
 445       if (!eset_contains (_live_graphs, irg)) {
 446         set_entity_peculiarity(ent, peculiarity_description);
 447         set_entity_irg(ent, NULL);
 448       }
 449     }
 450   }
 451 }
 452
 453 /* Delete all graphs that we have found to be dead from the program
 454    If verbose == 1, print statistics, if > 1, chatter about every detail
 455 */
 456 void rta_delete_dead_graphs (void)
 457 {
 458   int i;
 459   int n_graphs = get_irp_n_irgs ();
 460   ir_graph *graph = NULL;
 461   int n_dead_graphs = 0;
 462   ir_graph **dead_graphs;
 463
 464   int rem_vpi = get_visit_pseudo_irgs();
 465   set_visit_pseudo_irgs(1);
 466
 467   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 468
 469   dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
 470
 471   for (i = 0; i < n_graphs; i++) {
 472     graph = get_irp_irg(i);
 473
 474     if (rta_is_alive_graph (graph)) {
 475       /* do nothing (except some debugging fprintf`s :-) */
 476     } else {
 477 # ifdef DEBUG_libfirm
 478       entity *ent = get_irg_entity (graph);
 479       assert (visibility_external_visible != get_entity_visibility (ent));
 480 # endif /* defined DEBUG_libfirm */
 481
 482       dead_graphs[n_dead_graphs] = graph;
 483       n_dead_graphs ++;
 484     }
 485   }
 486
 487   type_walk(make_entity_to_description, NULL, NULL);
 488   for (i = 0; i < n_dead_graphs; ++i) {
 489     remove_irp_irg (dead_graphs[i]);
 490   }
 491
 492   if (verbose) {
 493     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 494   }
 495
 496   set_visit_pseudo_irgs(rem_vpi);
 497
 498   free(dead_graphs);
 499 }
 500
 501 /* Clean up the RTA data structures.  Call this after calling rta_init */
 502 void rta_cleanup (void)
 503 {
 504 # ifdef DEBUG_libfirm
 505   int i;
 506     for (i = 0; i < get_irp_n_irgs(); i++) {
 507       irg_vrfy (get_irp_irg(i));
 508     }
 509     tr_vrfy ();
 510 # endif /* defined DEBUG_libfirm */
 511
 512   if (_live_classes) {
 513     eset_destroy (_live_classes);
 514     _live_classes = NULL;
 515   }
 516
 517   if (_live_graphs) {
 518     eset_destroy (_live_graphs);
 519     _live_graphs = NULL;
 520   }
 521 }
 522
 523 /* Say whether this class might be instantiated at any point in the program: */
 524 int  rta_is_alive_class  (ir_type   *clazz)
 525 {
 526   return (eset_contains (_live_classes, clazz));
 527 }
 528
 529 /* Say whether this graph might be run at any time in the program: */
 530 int  rta_is_alive_graph (ir_graph *graph)
 531 {
 532   return eset_contains (_live_graphs, graph);
 533 }
 534
 535 /* dump our opinion */
 536 void rta_report (void)
 537 {
 538   int i;
 539
 540   for (i = 0; i < get_irp_n_types(); ++i) {
 541     ir_type *tp = get_irp_type(i);
 542     if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 543       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 544     }
 545   }
 546
 547   for (i = 0; i < get_irp_n_irgs(); i++) {
 548     if (rta_is_alive_graph (get_irp_irg(i))) {
 549       fprintf(stdout, "RTA: considered called: graph of ");
 550       DDMEO(get_irg_entity (get_irp_irg(i)));
 551     }
 552   }
 553 }
 554
 555
 556 /*
 557  * $Log$
 558  * Revision 1.36  2006/06/05 15:58:12  beck
 559  * added support for Thread local storage
 560  * added more doxygen docu
 561  *
 562  * Revision 1.35  2006/01/13 21:51:59  beck
 563  * renamed all types 'type' to 'ir_type'
 564  *
 565  * Revision 1.34  2006/01/02 15:01:16  beck
 566  * missing include added
 567  *
 568  * Revision 1.33  2005/11/17 17:26:57  beck
 569  * removed bool type and depency from stdbool.h (not C89)
 570  *
 571  * Revision 1.32  2005/01/05 14:24:52  beck
 572  * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
 573  *
 574  * Revision 1.31  2004/12/21 13:45:14  beck
 575  * removed C99 constructs
 576  *
 577  * Revision 1.30  2004/12/02 16:16:11  beck
 578  * fixed config.h include
 579  * used xmalloc instead of malloc
 580  *
 581  * Revision 1.29  2004/11/11 13:28:08  goetz
 582  * made pseudo irg aware
 583  *
 584  * Revision 1.28  2004/11/03 14:47:18  beck
 585  * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
 586  *
 587  * Revision 1.27  2004/10/21 07:23:34  goetz
 588  * comments
 589  *
 590  * Revision 1.26  2004/10/20 14:59:27  liekweg
 591  * Removed ecg
 592  *
 593  * Revision 1.25  2004/10/18 12:47:08  liekweg
 594  * avoid warning
 595  *
 596  * Revision 1.24  2004/09/24 13:59:04  beck
 597  * fixed doxygen comments, removed initialization for description entities
 598  *
 599  * Revision 1.23  2004/08/19 16:51:02  goetz
 600  * fixed some errors, pushed closer to inteded firm semantics
 601  *
 602  * Revision 1.22  2004/08/13 08:57:15  beyhan
 603  * normalized names of functions, enums ...
 604  * added suffix as argument to dumpers, removed global variable
 605  * removed support for tarval/Const
 606  *
 607  * Revision 1.21  2004/07/08 15:50:56  goetz
 608  * firmstat added
 609  *
 610  * Revision 1.20  2004/07/08 11:17:40  goetz
 611  * *** empty log message ***
 612  *
 613  * Revision 1.19  2004/07/06 12:30:37  beyhan
 614  * new SymConst semantics
 615  *
 616  * Revision 1.18  2004/06/27 21:17:41  liekweg
 617  * Added comment
 618  *
 619  * Revision 1.17  2004/06/25 13:45:13  liekweg
 620  * observe stickyness; minor refactoring
 621  *
 622  * Revision 1.16  2004/06/24 06:42:14  goetz
 623  * test of firm flags
 624  *
 625  * Revision 1.15  2004/06/18 15:47:19  liekweg
 626  * minor bug fix (go forward, not backward) --flo
 627  *
 628  * Revision 1.14  2004/06/18 13:12:43  liekweg
 629  * final bug fix (calls via consts)
 630  *
 631  * Revision 1.13  2004/06/17 16:34:33  liekweg
 632  * removed DD*s
 633  *
 634  * Revision 1.12  2004/06/17 16:33:33  liekweg
 635  * minor bug fix
 636  *
 637  * Revision 1.11  2004/06/17 14:21:13  liekweg
 638  * major bugfix
 639  *
 640  * Revision 1.10  2004/06/17 10:31:41  goetz
 641  * irscc: bugfix, can now deal with loops not reachable from start
 642  * cgana: bugfix, skip_Tuple
 643  * rta: improved
 644  *
 645  * Revision 1.9  2004/06/17 08:56:03  liekweg
 646  * Fixed typos in comments
 647  *
 648  * Revision 1.8  2004/06/17 08:33:01  liekweg
 649  * Added comments; added remove_irg
 650  *
 651  * Revision 1.6  2004/06/14 13:02:03  goetz
 652  * bugfixesbug
 653  *
 654  * Revision 1.5  2004/06/13 15:03:45  liekweg
 655  * RTA auf Iterative RTA aufgebohrt --flo
 656  *
 657  * Revision 1.4  2004/06/12 19:35:04  liekweg
 658  * Kommentare eingef"ugt --flo
 659  *
 660  * Revision 1.3  2004/06/12 17:09:46  liekweg
 661  * RTA works, outedges breaks.  "Yay." --flo
 662  *
 663  * Revision 1.2  2004/06/11 18:25:39  liekweg
 664  * Added todo
 665  *
 666  * Revision 1.1  2004/06/11 18:24:18  liekweg
 667  * Added RTA --flo
 668  *
 669  */