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