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         ent = get_SymConst_entity (ptr);
 178         ir_graph *graph = get_entity_irg (ent);
 179         if (graph) {
 180           *change |= add_graph (graph);
 181         } else {
 182           /* it's an external allocated thing. */
 183         }
 184       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
 185         /* Entities of kind addr_name may not be allocated in this compilation unit.
 186            If so, the frontend built faulty Firm.  So just ignore. */
 187         /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
 188           assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
 189       } else {
 190         /* other symconst. */
 191         assert(0 && "This SymConst can not be an address for a method call.");
 192       }
 193
 194       /* STRANGE */
 195     } else {
 196       DDMN(ptr);
 197       assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
 198     }
 199
 200   } else if (iro_Alloc == op) { /* ALLOC */
 201     type *type = get_Alloc_type (node);
 202
 203     *change |= add_class (type);
 204   }
 205 }
 206
 207 /**
 208    Traverse the given graph to collect method accesses and
 209    object allocations.
 210 */
 211 static int rta_fill_graph (ir_graph* graph)
 212 {
 213   int change = FALSE;
 214
 215   current_ir_graph = graph;
 216
 217   irg_walk_graph (graph, rta_act, NULL, &change);
 218
 219   return (change);
 220 }
 221
 222 /** Traverse all graphs to collect method accesses and object allocations.
 223  *
 224  *  @param rerun Whether to rely on is_alive in a second run
 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(false);     /* 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    Initialise 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  * Initialise 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 n_runs = 0;
 374
 375   int rem_vpi = get_visit_pseudo_irgs();
 376   set_visit_pseudo_irgs(1);
 377
 378 # ifdef DEBUG_libfirm
 379   int i;
 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
 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   ir_graph *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
 477 /* Clean up the RTA data structures.  Call this after calling rta_init */
 478 void rta_cleanup (void)
 479 {
 480 # ifdef DEBUG_libfirm
 481   int i;
 482     for (i = 0; i < get_irp_n_irgs(); i++) {
 483       irg_vrfy (get_irp_irg(i));
 484     }
 485     tr_vrfy ();
 486 # endif /* defined DEBUG_libfirm */
 487
 488   if (_live_classes) {
 489     eset_destroy (_live_classes);
 490     _live_classes = NULL;
 491   }
 492
 493   if (_live_graphs) {
 494     eset_destroy (_live_graphs);
 495     _live_graphs = NULL;
 496   }
 497 }
 498
 499 /* Say whether this class might be instantiated at any point in the program: */
 500 int  rta_is_alive_class  (type   *clazz)
 501 {
 502   return (eset_contains (_live_classes, clazz));
 503 }
 504
 505 /* Say whether this graph might be run at any time in the program: */
 506 int  rta_is_alive_graph (ir_graph *graph)
 507 {
 508   return eset_contains (_live_graphs, graph);
 509 }
 510
 511 /* dump our opinion */
 512 void rta_report (void)
 513 {
 514   int i;
 515
 516   for (i = 0; i < get_irp_n_types(); ++i) {
 517     type *tp = get_irp_type(i);
 518     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 519       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 520     }
 521   }
 522
 523   for (i = 0; i < get_irp_n_irgs(); i++) {
 524     if (rta_is_alive_graph (get_irp_irg(i))) {
 525       fprintf(stdout, "RTA: considered called: graph of ");
 526       DDMEO(get_irg_entity (get_irp_irg(i)));
 527     }
 528   }
 529 }
 530
 531
 532 /*
 533  * $Log$
 534  * Revision 1.30  2004/12/02 16:16:11  beck
 535  * fixed config.h include
 536  * used xmalloc instead of malloc
 537  *
 538  * Revision 1.29  2004/11/11 13:28:08  goetz
 539  * made pseudo irg aware
 540  *
 541  * Revision 1.28  2004/11/03 14:47:18  beck
 542  * removed gloval intraprocedural_view variable and replaced by get_*() set_*() functions
 543  *
 544  * Revision 1.27  2004/10/21 07:23:34  goetz
 545  * comments
 546  *
 547  * Revision 1.26  2004/10/20 14:59:27  liekweg
 548  * Removed ecg
 549  *
 550  * Revision 1.25  2004/10/18 12:47:08  liekweg
 551  * avoid warning
 552  *
 553  * Revision 1.24  2004/09/24 13:59:04  beck
 554  * fixed doxygen comments, removed initialization for description entities
 555  *
 556  * Revision 1.23  2004/08/19 16:51:02  goetz
 557  * fixed some errors, pushed closer to inteded firm semantics
 558  *
 559  * Revision 1.22  2004/08/13 08:57:15  beyhan
 560  * normalized names of functions, enums ...
 561  * added suffix as argument to dumpers, removed global variable
 562  * removed support for tarval/Const
 563  *
 564  * Revision 1.21  2004/07/08 15:50:56  goetz
 565  * firmstat added
 566  *
 567  * Revision 1.20  2004/07/08 11:17:40  goetz
 568  * *** empty log message ***
 569  *
 570  * Revision 1.19  2004/07/06 12:30:37  beyhan
 571  * new SymConst semantics
 572  *
 573  * Revision 1.18  2004/06/27 21:17:41  liekweg
 574  * Added comment
 575  *
 576  * Revision 1.17  2004/06/25 13:45:13  liekweg
 577  * observe stickyness; minor refactoring
 578  *
 579  * Revision 1.16  2004/06/24 06:42:14  goetz
 580  * test of firm flags
 581  *
 582  * Revision 1.15  2004/06/18 15:47:19  liekweg
 583  * minor bug fix (go forward, not backward) --flo
 584  *
 585  * Revision 1.14  2004/06/18 13:12:43  liekweg
 586  * final bug fix (calls via consts)
 587  *
 588  * Revision 1.13  2004/06/17 16:34:33  liekweg
 589  * removed DD*s
 590  *
 591  * Revision 1.12  2004/06/17 16:33:33  liekweg
 592  * minor bug fix
 593  *
 594  * Revision 1.11  2004/06/17 14:21:13  liekweg
 595  * major bugfix
 596  *
 597  * Revision 1.10  2004/06/17 10:31:41  goetz
 598  * irscc: bugfix, can now deal with loops not reachable from start
 599  * cgana: bugfix, skip_Tuple
 600  * rta: improved
 601  *
 602  * Revision 1.9  2004/06/17 08:56:03  liekweg
 603  * Fixed typos in comments
 604  *
 605  * Revision 1.8  2004/06/17 08:33:01  liekweg
 606  * Added comments; added remove_irg
 607  *
 608  * Revision 1.6  2004/06/14 13:02:03  goetz
 609  * bugfixesbug
 610  *
 611  * Revision 1.5  2004/06/13 15:03:45  liekweg
 612  * RTA auf Iterative RTA aufgebohrt --flo
 613  *
 614  * Revision 1.4  2004/06/12 19:35:04  liekweg
 615  * Kommentare eingef"ugt --flo
 616  *
 617  * Revision 1.3  2004/06/12 17:09:46  liekweg
 618  * RTA works, outedges breaks.  "Yay." --flo
 619  *
 620  * Revision 1.2  2004/06/11 18:25:39  liekweg
 621  * Added todo
 622  *
 623  * Revision 1.1  2004/06/11 18:24:18  liekweg
 624  * Added RTA --flo
 625  *
 626  */