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
 364   _live_graphs = eset_create ();
 365
 366   if (get_irp_main_irg ()) {
 367     eset_insert (_live_graphs, get_irp_main_irg ());
 368   }
 369
 370   /* Find static allocated classes */
 371   for (i = 0; i < n_globs; ++i) {
 372     type *member_type = get_entity_type(get_class_member(get_glob_type(), i));
 373     if (is_class_type(member_type))
 374       eset_insert(_live_classes, member_type);
 375   }
 376 }
 377
 378 /* Initialise the RTA data structures, and perform RTA.
 379    @param   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 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         set_atomic_ent_value(ent, new_Const(mode_P, get_tarval_null(mode_P)));
 428       }
 429     }
 430   }
 431 }
 432
 433 /* Delete all graphs that we have found to be dead from the program
 434    If verbose == 1, print statistics, if > 1, chatter about every detail
 435 */
 436 void rta_delete_dead_graphs (void)
 437 {
 438   int i;
 439   int n_graphs = get_irp_n_irgs ();
 440   ir_graph *graph = NULL;
 441   int n_dead_graphs = 0;
 442
 443   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 444
 445   ir_graph *dead_graphs[get_irp_n_irgs()];
 446
 447   for (i = 0; i < n_graphs; i++) {
 448     graph = get_irp_irg(i);
 449
 450     if (rta_is_alive_graph (graph)) {
 451       /* do nothing (except some debugging fprintf`s :-) */
 452     } else {
 453 # ifdef DEBUG_libfirm
 454       entity *ent = get_irg_entity (graph);
 455       assert (visibility_external_visible != get_entity_visibility (ent));
 456 # endif /* defined DEBUG_libfirm */
 457
 458       dead_graphs[n_dead_graphs] = graph;
 459       n_dead_graphs ++;
 460     }
 461   }
 462
 463   current_ir_graph = get_const_code_irg();
 464   type_walk(make_entity_to_description, NULL, NULL);
 465   for (i = 0; i < n_dead_graphs; ++i) {
 466     remove_irp_irg (dead_graphs[i]);
 467   }
 468
 469   if (verbose) {
 470     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 471   }
 472 }
 473
 474 /* Clean up the RTA data structures.  Call this after calling rta_init */
 475 void rta_cleanup (void)
 476 {
 477 # ifdef DEBUG_libfirm
 478   int i;
 479     for (i = 0; i < get_irp_n_irgs(); i++) {
 480       irg_vrfy (get_irp_irg(i));
 481     }
 482     tr_vrfy ();
 483 # endif /* defined DEBUG_libfirm */
 484
 485   if (_live_classes) {
 486     eset_destroy (_live_classes);
 487     _live_classes = NULL;
 488   }
 489
 490   if (_live_graphs) {
 491     eset_destroy (_live_graphs);
 492     _live_graphs = NULL;
 493   }
 494 }
 495
 496 /* Say whether this class might be instantiated at any point in the program: */
 497 int  rta_is_alive_class  (type   *clazz)
 498 {
 499   return (eset_contains (_live_classes, clazz));
 500 }
 501
 502 /* Say whether this graph might be run at any time in the program: */
 503 int  rta_is_alive_graph (ir_graph *graph)
 504 {
 505   if (eset_contains (_live_graphs, graph)) {
 506     return (TRUE);
 507   }
 508
 509   return (FALSE);
 510 }
 511
 512 /* dump our opinion */
 513 void rta_report (void)
 514 {
 515   int i;
 516
 517   for (i = 0; i < get_irp_n_types(); ++i) {
 518     type *tp = get_irp_type(i);
 519     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 520       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 521     }
 522   }
 523
 524   for (i = 0; i < get_irp_n_irgs(); i++) {
 525     if (rta_is_alive_graph (get_irp_irg(i))) {
 526       fprintf(stdout, "RTA: considered called: graph of ");
 527       DDMEO(get_irg_entity (get_irp_irg(i)));
 528     }
 529   }
 530 }
 531
 532
 533 /*
 534  * $Log$
 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  */