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