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