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