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 static int rta_fill_incremental (void)
 227 {
 228   int i;
 229   int n_runs = 0;
 230   int rerun  = TRUE;
 231   int old_ip_view = get_interprocedural_view();
 232
 233   set_interprocedural_view(0);     /* save this for later */
 234
 235   /* init_tables has added main_irg to _live_graphs */
 236
 237   /* Need to take care of graphs that are externally
 238      visible or sticky. Pretend that they are called: */
 239
 240   for (i = 0; i < get_irp_n_irgs(); i++) {
 241     ir_graph *graph = get_irp_irg (i);
 242     entity *ent = get_irg_entity (graph);
 243
 244     if ((visibility_external_visible == get_entity_visibility (ent)) ||
 245         (stickyness_sticky == get_entity_stickyness (ent))) {
 246       eset_insert (_live_graphs, graph);
 247       // printf("external visible: "); DDMG(graph);
 248     }
 249   }
 250
 251   while (rerun) {
 252     ir_graph *graph;
 253
 254     /* start off new */
 255     eset *live_graphs = _live_graphs;
 256     _live_graphs = eset_create ();
 257
 258     if (verbose > 1) {
 259       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 260     }
 261
 262     /* collect what we have found previously */
 263     eset_insert_all (_live_graphs, live_graphs);
 264
 265     rerun = FALSE;
 266     for (graph = eset_first (live_graphs);
 267          graph;
 268          graph = eset_next (live_graphs)) {
 269
 270       if (verbose > 1) {
 271         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 272         DDMEO(get_irg_entity (graph));
 273       }
 274
 275       rerun |= rta_fill_graph (graph);
 276     }
 277
 278     eset_destroy (live_graphs);
 279
 280     n_runs ++;
 281   }
 282
 283   set_interprocedural_view(old_ip_view); /* cover up our traces */
 284
 285   return (n_runs);
 286 }
 287
 288 /**
 289  * Count the number of graphs that we have found to be live.
 290  */
 291 static int stats (void)
 292 {
 293   int i;
 294   int n_live_graphs = 0;
 295   int n_graphs = get_irp_n_irgs();
 296
 297   for (i = 0; i < n_graphs; i++) {
 298     ir_graph *graph = get_irp_irg(i);
 299
 300     if (rta_is_alive_graph (graph)) {
 301       n_live_graphs ++;
 302     }
 303   }
 304
 305   return (n_live_graphs);
 306 }
 307
 308 /* remove a graph, part I */
 309 /*
 310    We removed the first graph to implement the entity, so we're
 311    abstract now.  Pretend that it wasn't there at all, and every
 312    entity that used to inherit this entity's graph is now abstract.
 313 */
 314 /* Since we *know* that this entity will not be called, this is OK. */
 315 static void force_description (entity *ent, entity *addr)
 316 {
 317   int i, n_over = get_entity_n_overwrittenby (ent);
 318
 319   set_entity_peculiarity (ent, peculiarity_description);
 320
 321   for (i = 0; i < n_over; i ++) {
 322     entity *over = get_entity_overwrittenby (ent, i);
 323
 324     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 325       /* We rely on the fact that cse is performed on the const_code_irg. */
 326       entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 327
 328       if (addr == my_addr) {
 329         force_description (over, addr);
 330       }
 331     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 332       /* check whether 'over' forces 'inheritance' of *our* graph: */
 333       ir_node *f_addr = get_atomic_ent_value (over);
 334       entity *impl_ent = get_SymConst_entity (f_addr);
 335
 336       assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
 337       if (impl_ent == addr) {
 338         assert (0 && "gibt's denn sowas");
 339         force_description (over, addr);
 340       }
 341     }
 342   }
 343 }
 344
 345 /**
 346    Initialize the static data structures.
 347 */
 348 static void init_tables (void)
 349 {
 350   int i, n_globs = get_class_n_members(get_glob_type());
 351
 352   _live_classes = eset_create ();
 353   _live_graphs  = eset_create ();
 354
 355   if (get_irp_main_irg ()) {
 356     eset_insert (_live_graphs, get_irp_main_irg ());
 357   }
 358
 359   /* Find static allocated classes */
 360   for (i = 0; i < n_globs; ++i) {
 361     type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
 362     if (is_Class_type(member_type))
 363       eset_insert(_live_classes, member_type);
 364   }
 365 }
 366
 367 /*
 368  * Initialize the RTA data structures, and perform RTA.
 369  * do_verbose If == 1, print statistics, if > 1, chatter about every detail
 370  */
 371 void rta_init (int do_verbose)
 372 {
 373   int i, n_runs = 0;
 374
 375   int rem_vpi = get_visit_pseudo_irgs();
 376   set_visit_pseudo_irgs(1);
 377
 378 # ifdef DEBUG_libfirm
 379   for (i = 0; i < get_irp_n_irgs(); i++) {
 380     irg_vrfy (get_irp_irg(i));
 381   }
 382   tr_vrfy ();
 383 # endif /* defined DEBUG_libfirm */
 384
 385   verbose = do_verbose;
 386
 387   init_tables ();
 388
 389   n_runs = rta_fill_incremental ();
 390
 391   if (verbose) {
 392     int n_live_graphs = stats ();
 393
 394     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 395     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 396     printf ("RTA: n_runs        = %i\n", n_runs);
 397   }
 398
 399 # ifdef DEBUG_libfirm
 400   for (i = 0; i < get_irp_n_irgs(); i++) {
 401     irg_vrfy (get_irp_irg(i));
 402   }
 403   tr_vrfy ();
 404 # endif /* defined DEBUG_libfirm */
 405
 406   set_visit_pseudo_irgs(rem_vpi);
 407 }
 408
 409 /**
 410  * walker for all types and entities
 411  *
 412  * Changes the peculiarity of entities that represents
 413  * dead graphs to peculiarity_description.
 414  */
 415 static void make_entity_to_description(type_or_ent *tore, void *env) {
 416   if (get_kind(tore) == k_entity) {
 417     entity *ent = (entity *)tore;
 418
 419     if ((is_Method_type(get_entity_type(ent)))                        &&
 420         (get_entity_peculiarity(ent) != peculiarity_description)      &&
 421         (get_entity_visibility(ent)  != visibility_external_allocated)   ) {
 422       ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
 423       if (!eset_contains (_live_graphs, irg)) {
 424         set_entity_peculiarity(ent, peculiarity_description);
 425         set_entity_irg(ent, NULL);
 426       }
 427     }
 428   }
 429 }
 430
 431 /* Delete all graphs that we have found to be dead from the program
 432    If verbose == 1, print statistics, if > 1, chatter about every detail
 433 */
 434 void rta_delete_dead_graphs (void)
 435 {
 436   int i;
 437   int n_graphs = get_irp_n_irgs ();
 438   ir_graph *graph = NULL;
 439   int n_dead_graphs = 0;
 440   ir_graph **dead_graphs;
 441
 442   int rem_vpi = get_visit_pseudo_irgs();
 443   set_visit_pseudo_irgs(1);
 444
 445   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 446
 447   dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
 448
 449   for (i = 0; i < n_graphs; i++) {
 450     graph = get_irp_irg(i);
 451
 452     if (rta_is_alive_graph (graph)) {
 453       /* do nothing (except some debugging fprintf`s :-) */
 454     } else {
 455 # ifdef DEBUG_libfirm
 456       entity *ent = get_irg_entity (graph);
 457       assert (visibility_external_visible != get_entity_visibility (ent));
 458 # endif /* defined DEBUG_libfirm */
 459
 460       dead_graphs[n_dead_graphs] = graph;
 461       n_dead_graphs ++;
 462     }
 463   }
 464
 465   type_walk(make_entity_to_description, NULL, NULL);
 466   for (i = 0; i < n_dead_graphs; ++i) {
 467     remove_irp_irg (dead_graphs[i]);
 468   }
 469
 470   if (verbose) {
 471     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 472   }
 473
 474   set_visit_pseudo_irgs(rem_vpi);
 475
 476   free(dead_graphs);
 477 }
 478
 479 /* Clean up the RTA data structures.  Call this after calling rta_init */
 480 void rta_cleanup (void)
 481 {
 482 # ifdef DEBUG_libfirm
 483   int i;
 484     for (i = 0; i < get_irp_n_irgs(); i++) {
 485       irg_vrfy (get_irp_irg(i));
 486     }
 487     tr_vrfy ();
 488 # endif /* defined DEBUG_libfirm */
 489
 490   if (_live_classes) {
 491     eset_destroy (_live_classes);
 492     _live_classes = NULL;
 493   }
 494
 495   if (_live_graphs) {
 496     eset_destroy (_live_graphs);
 497     _live_graphs = NULL;
 498   }
 499 }
 500
 501 /* Say whether this class might be instantiated at any point in the program: */
 502 int  rta_is_alive_class  (type   *clazz)
 503 {
 504   return (eset_contains (_live_classes, clazz));
 505 }
 506
 507 /* Say whether this graph might be run at any time in the program: */
 508 int  rta_is_alive_graph (ir_graph *graph)
 509 {
 510   return eset_contains (_live_graphs, graph);
 511 }
 512
 513 /* dump our opinion */
 514 void rta_report (void)
 515 {
 516   int i;
 517
 518   for (i = 0; i < get_irp_n_types(); ++i) {
 519     type *tp = get_irp_type(i);
 520     if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 521       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 522     }
 523   }
 524
 525   for (i = 0; i < get_irp_n_irgs(); i++) {
 526     if (rta_is_alive_graph (get_irp_irg(i))) {
 527       fprintf(stdout, "RTA: considered called: graph of ");
 528       DDMEO(get_irg_entity (get_irp_irg(i)));
 529     }
 530   }
 531 }
 532
 533
 534 /*
 535  * $Log$
 536  * Revision 1.33  2005/11/17 17:26:57  beck
 537  * removed bool type and depency from stdbool.h (not C89)
 538  *
 539  * Revision 1.32  2005/01/05 14:24:52  beck
 540  * renames all is_x*_type() functions to is_X*_type() to prevent name clash with EDG frontend
 541  *
 542  * Revision 1.31  2004/12/21 13:45:14  beck
 543  * removed C99 constructs
 544  *
 545  * Revision 1.30  2004/12/02 16:16:11  beck
 546  * fixed config.h include
 547  * used xmalloc instead of malloc
 548  *
 549  * Revision 1.29  2004/11/11 13:28:08  goetz
 550  * made pseudo irg aware
 551  *
 552  * Revision 1.28  2004/11/03 14:47:18  beck
 553  * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
 554  *
 555  * Revision 1.27  2004/10/21 07:23:34  goetz
 556  * comments
 557  *
 558  * Revision 1.26  2004/10/20 14:59:27  liekweg
 559  * Removed ecg
 560  *
 561  * Revision 1.25  2004/10/18 12:47:08  liekweg
 562  * avoid warning
 563  *
 564  * Revision 1.24  2004/09/24 13:59:04  beck
 565  * fixed doxygen comments, removed initialization for description entities
 566  *
 567  * Revision 1.23  2004/08/19 16:51:02  goetz
 568  * fixed some errors, pushed closer to inteded firm semantics
 569  *
 570  * Revision 1.22  2004/08/13 08:57:15  beyhan
 571  * normalized names of functions, enums ...
 572  * added suffix as argument to dumpers, removed global variable
 573  * removed support for tarval/Const
 574  *
 575  * Revision 1.21  2004/07/08 15:50:56  goetz
 576  * firmstat added
 577  *
 578  * Revision 1.20  2004/07/08 11:17:40  goetz
 579  * *** empty log message ***
 580  *
 581  * Revision 1.19  2004/07/06 12:30:37  beyhan
 582  * new SymConst semantics
 583  *
 584  * Revision 1.18  2004/06/27 21:17:41  liekweg
 585  * Added comment
 586  *
 587  * Revision 1.17  2004/06/25 13:45:13  liekweg
 588  * observe stickyness; minor refactoring
 589  *
 590  * Revision 1.16  2004/06/24 06:42:14  goetz
 591  * test of firm flags
 592  *
 593  * Revision 1.15  2004/06/18 15:47:19  liekweg
 594  * minor bug fix (go forward, not backward) --flo
 595  *
 596  * Revision 1.14  2004/06/18 13:12:43  liekweg
 597  * final bug fix (calls via consts)
 598  *
 599  * Revision 1.13  2004/06/17 16:34:33  liekweg
 600  * removed DD*s
 601  *
 602  * Revision 1.12  2004/06/17 16:33:33  liekweg
 603  * minor bug fix
 604  *
 605  * Revision 1.11  2004/06/17 14:21:13  liekweg
 606  * major bugfix
 607  *
 608  * Revision 1.10  2004/06/17 10:31:41  goetz
 609  * irscc: bugfix, can now deal with loops not reachable from start
 610  * cgana: bugfix, skip_Tuple
 611  * rta: improved
 612  *
 613  * Revision 1.9  2004/06/17 08:56:03  liekweg
 614  * Fixed typos in comments
 615  *
 616  * Revision 1.8  2004/06/17 08:33:01  liekweg
 617  * Added comments; added remove_irg
 618  *
 619  * Revision 1.6  2004/06/14 13:02:03  goetz
 620  * bugfixesbug
 621  *
 622  * Revision 1.5  2004/06/13 15:03:45  liekweg
 623  * RTA auf Iterative RTA aufgebohrt --flo
 624  *
 625  * Revision 1.4  2004/06/12 19:35:04  liekweg
 626  * Kommentare eingef"ugt --flo
 627  *
 628  * Revision 1.3  2004/06/12 17:09:46  liekweg
 629  * RTA works, outedges breaks.  "Yay." --flo
 630  *
 631  * Revision 1.2  2004/06/11 18:25:39  liekweg
 632  * Added todo
 633  *
 634  * Revision 1.1  2004/06/11 18:24:18  liekweg
 635  * Added RTA --flo
 636  *
 637  */