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