nsz Git - libfirm/blob - ir/ana/rta.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana/rta.c
   6  * Purpose:     Intraprozedural analyses 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 protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15 /**
  16  * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es
  17  * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden
  18  * bestimmt.
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include "rta.h"
  26
  27 #include <stdlib.h>
  28
  29 #include "irnode_t.h"
  30 #include "irprog.h"
  31
  32 #include "eset.h"
  33 #include "irgwalk.h"
  34 #include "irgmod.h"
  35 #include "irvrfy.h"
  36 #include "trvrfy.h"
  37
  38 # define TRUE 1
  39 # define FALSE 0
  40
  41 /* base data */
  42 static eset *_live_classes   = NULL;
  43
  44 /* cache computed results */
  45 static eset *_live_graphs    = NULL;
  46
  47 static int whole_world = 0;
  48 static int verbose     = 0;
  49
  50 /**
  51    Given a method, find the firm graph that implements that method.
  52 */
  53 static ir_graph *get_implementing_graph (entity *method)
  54 {
  55   ir_graph *graph = get_entity_irg ((entity*) method);
  56
  57   if (NULL == graph) {
  58     int i;
  59     int n_over = get_entity_n_overwrites ((entity*) method);
  60
  61     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
  62       entity *over = get_entity_overwrites ((entity*) method, i);
  63       graph = get_implementing_graph (over);
  64     }
  65   }
  66
  67   /* we *must* always return a graph != NULL, *except* when we're used
  68      inside remove_irg or force_description */
  69   /* assert (graph && "no graph"); */
  70
  71   return (graph);
  72 }
  73
  74 static int add_graph (ir_graph *graph)
  75 {
  76   if (!eset_contains (_live_graphs, graph)) {
  77     if (verbose > 1) {
  78       fprintf(stdout, "RTA:        new graph of ");
  79       DDMEO(get_irg_ent (graph));
  80     }
  81
  82     eset_insert (_live_graphs, graph);
  83     return (TRUE);
  84   }
  85
  86   return (FALSE);
  87 }
  88
  89 static int add_class (type *clazz)
  90 {
  91   if (!eset_contains (_live_classes, clazz)) {
  92   if (verbose > 1) {
  93     fprintf(stdout, "RTA:        new class: ");
  94     DDMT(clazz);
  95   }
  96
  97     eset_insert (_live_classes, clazz);
  98     return (TRUE);
  99   }
 100
 101   return (FALSE);
 102 }
 103
 104 /**
 105    Given an entity, add all implementing graphs that belong to live classes to _live_graphs.
 106
 107    Iff additions occurred, return TRUE, else FALSE.
 108 */
 109 static int add_implementing_graphs (entity *method)
 110 {
 111   int i;
 112   int n_over = get_entity_n_overwrittenby (method);
 113   ir_graph *graph = get_entity_irg (method);
 114   int change = FALSE;
 115
 116   if (NULL == graph) {
 117     graph = get_implementing_graph (method);
 118   }
 119
 120   if (verbose > 1) {
 121     fprintf(stdout, "RTA:        new call to ");
 122     DDMEO(method);
 123   }
 124
 125   if (rta_is_alive_class (get_entity_owner (method))) {
 126     if (NULL != graph) {
 127       change = add_graph (graph);
 128     }
 129   }
 130
 131   for (i = 0; i < n_over; i ++) {
 132     entity *over = get_entity_overwrittenby (method, i);
 133     change |= add_implementing_graphs (over);
 134   }
 135
 136   return (change);
 137 }
 138
 139 /**
 140    Enter all method accesses and all class allocations into
 141    our tables.
 142
 143    Set *(int*)env to true iff (possibly) new graphs have been found.
 144 */
 145 static void rta_act (ir_node *node, void *env)
 146 {
 147   int *change = (int*) env;
 148
 149   opcode op = get_irn_opcode (node);
 150
 151   if (iro_Call == op) {         /* CALL */
 152     entity *ent = NULL;
 153
 154     ir_node *ptr = get_Call_ptr (node);
 155
 156     if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
 157       ent = get_Sel_entity (ptr);
 158       *change = add_implementing_graphs (ent);
 159     } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
 160       ent = get_tarval_entity (get_Const_tarval (ptr));
 161       ir_graph *graph = get_entity_irg (ent);
 162       /* don't use get_implementing_graph on a Const! */
 163       if (graph) {
 164         *change = add_graph (graph);
 165       } else {
 166         /* it's an externally allocated thing. */
 167       }
 168     } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
 169       /* If this SymConst refers to a method the method is external_visible
 170          and therefore must be considered live anyways. */
 171       /* assert (ent && "couldn't determine entity of call to symConst"); */
 172     }
 173   } else if (iro_Alloc == op) { /* ALLOC */
 174     type *type = get_Alloc_type (node);
 175
 176     *change = add_class (type);
 177   }
 178 }
 179
 180 /**
 181    Traverse the given graph to collect method accesses and
 182    object allocations.
 183 */
 184 static int rta_fill_graph (ir_graph* graph)
 185 {
 186   int change = FALSE;
 187
 188   current_ir_graph = graph;
 189
 190   irg_walk (get_irg_end (graph), rta_act, NULL, &change);
 191
 192   return (change);
 193 }
 194
 195 /**
 196    Traverse all graphs to collect method accesses and object allocations.
 197
 198    @param rerun Whether to rely on is_alive in a second run
 199 */
 200 static int rta_fill_incremental (void)
 201 {
 202   int i;
 203   int n_runs = 0;
 204   int rerun  = TRUE;
 205   int old_ip_view = interprocedural_view;
 206
 207   interprocedural_view = 0;     /* save this for later */
 208
 209   /* init_tables has added main_irg to _live_graphs */
 210
 211   /* Need to take care of graphs that are externally
 212      visible. Pretend that they are called: */
 213
 214   if (! whole_world) {
 215     for (i = 0; i < get_irp_n_irgs(); i++) {
 216       ir_graph *graph = get_irp_irg (i);
 217
 218       entity *ent = get_irg_entity (graph);
 219       if (visibility_external_visible == get_entity_visibility (ent)) {
 220
 221         eset_insert (_live_graphs, graph);
 222
 223         /* eset_insert (_live_classes, get_entity_owner (ent)); */
 224       }
 225     }
 226   }
 227
 228   while (rerun) {
 229     ir_graph *graph;
 230
 231     /* start off new */
 232     eset *live_graphs = _live_graphs;
 233     _live_graphs = eset_create ();
 234
 235     if (verbose > 1) {
 236       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 237     }
 238
 239     /* collect what we have found previously */
 240     eset_insert_all (_live_graphs, live_graphs);
 241
 242     rerun = FALSE;
 243
 244     for (graph = eset_first (live_graphs);
 245          graph;
 246          graph = eset_next (live_graphs)) {
 247
 248       if (verbose > 1) {
 249         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 250         DDMEO(get_irg_ent (graph));
 251       }
 252
 253       rerun |= rta_fill_graph (graph);
 254     }
 255
 256     eset_destroy (live_graphs);
 257
 258     n_runs ++;
 259   }
 260
 261   interprocedural_view = old_ip_view; /* cover up our traces */
 262
 263   return (n_runs);
 264 }
 265
 266 /*
 267    Count the number of graphs that we have found to be live.
 268 */
 269 static int stats (void)
 270 {
 271   int i;
 272   int n_live_graphs = 0;
 273   int n_graphs = get_irp_n_irgs();
 274
 275   for (i = 0; i < n_graphs; i++) {
 276     ir_graph *graph = get_irp_irg(i);
 277
 278     if (rta_is_alive_graph (graph)) {
 279       n_live_graphs ++;
 280     }
 281   }
 282
 283   return (n_live_graphs);
 284 }
 285
 286 /* remove a graph, part I */
 287 /*
 288    We removed the first graph to implement the entity, so we're
 289    abstract now.  Pretend that it wasn't there at all, and every
 290    entity that used to inherit this entity's graph is now abstract.
 291 */
 292 /* Since we *know* that this entity will not be called, this is OK. */
 293 static void force_description (entity *ent, entity *addr)
 294 {
 295   int i, n_over = get_entity_n_overwrittenby (ent);
 296
 297   set_entity_peculiarity (ent, peculiarity_description);
 298
 299   for (i = 0; i < n_over; i ++) {
 300     entity *over = get_entity_overwrittenby (ent, i);
 301
 302     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 303       /* We rely on the fact that cse is performed on the const_code_irg. */
 304       entity *my_addr =
 305         tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
 306
 307       if (addr == my_addr) {
 308         force_description (over, addr);
 309       }
 310     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 311       /* check whether 'over' forces 'inheritance' of *our* graph: */
 312       ir_node *f_addr = get_atomic_ent_value (over);
 313       entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
 314
 315       assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
 316       if (impl_ent == addr) {
 317         assert (0 && "gibt's denn sowas");
 318         force_description (over, addr);
 319       }
 320     }
 321   }
 322 }
 323
 324 /* remove a graph, part II */
 325 /*
 326    Note: get_implementing_graph is not well defined here (graph->ent
 327    could overwrite more than one superclass implementation (graph).
 328    Since we *know* that this entity will not be called, this is OK.
 329 */
 330 static void remove_irg (ir_graph *graph)
 331 {
 332   entity *ent = get_irg_entity (graph);
 333
 334 /*   DDMEO (get_irg_ent(graph)); */
 335
 336   /* delete the ir_graph data */
 337   remove_irp_irg (graph);
 338   /* remove reference to the graph */
 339   set_entity_irg (ent, NULL);
 340   /* find the implementation (graph) from *some* superclass: */
 341   graph = get_implementing_graph (ent);
 342
 343   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 344     /* nothing to inherit!  pretend we're abstract */
 345     force_description (ent, ent);
 346   } else {
 347     /* pretend that we inherit the implementation (graph) from some superclass: */
 348     set_entity_peculiarity (ent, peculiarity_inherited);
 349
 350     exchange (get_atomic_ent_value (ent),
 351               get_atomic_ent_value (get_irg_ent(graph)));
 352   }
 353 }
 354
 355 /**
 356    Initialise the static data structures.
 357 */
 358 static void init_tables (void)
 359 {
 360   _live_classes   = eset_create ();
 361
 362   _live_graphs = eset_create ();
 363
 364   if (get_irp_main_irg ()) {
 365     eset_insert (_live_graphs, get_irp_main_irg ());
 366   }
 367
 368   /*
 369   if (get_glob_type ()) {
 370     eset_insert (_live_classes, get_glob_type ());
 371   }
 372   */
 373 }
 374
 375 /* Initialise the RTA data structures, and perform RTA.
 376    @param   do_verbose Iff != 0, print statistics as we go along
 377    @param   do_whole_world Iff != 0, assume whole-world
 378 */
 379 void rta_init (int do_verbose, int do_whole_world)
 380 {
 381   int n_live_graphs = 0;
 382   int n_runs = 0;
 383
 384 # ifdef DEBUG_libfirm
 385   int i;
 386   for (i = 0; i < get_irp_n_irgs(); i++) {
 387     irg_vrfy (get_irp_irg(i));
 388   }
 389   tr_vrfy ();
 390 # endif /* defined DEBUG_libfirm */
 391
 392   whole_world = do_whole_world;
 393   verbose = do_verbose;
 394
 395   init_tables ();
 396
 397   n_runs = rta_fill_incremental ();
 398
 399   n_live_graphs = stats ();
 400
 401   if (verbose) {
 402     if (whole_world) {
 403       printf ("RTA: whole-world assumption\n");
 404     }
 405     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 406     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 407     printf ("RTA: n_runs        = %i\n", n_runs);
 408   }
 409
 410 # ifdef DEBUG_libfirm
 411   for (i = 0; i < get_irp_n_irgs(); i++) {
 412     irg_vrfy (get_irp_irg(i));
 413   }
 414   tr_vrfy ();
 415 # endif /* defined DEBUG_libfirm */
 416 }
 417
 418 /* Delete all graphs that we have found to be dead from the program */
 419 void rta_delete_dead_graphs (void)
 420 {
 421   int i;
 422   int n_graphs = get_irp_n_irgs ();
 423   ir_graph *graph = NULL;
 424
 425   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 426
 427   eset *dead_graphs = eset_create ();
 428
 429   for (i = 0; i < n_graphs; i++) {
 430     graph = get_irp_irg(i);
 431
 432     if (rta_is_alive_graph (graph)) {
 433       /* do nothing (except some debugging fprintf`s :-) */
 434     } else {
 435 # ifdef DEBUG_libfirm
 436       entity *ent = get_irg_entity (graph);
 437       assert (whole_world ||
 438               (visibility_external_visible != get_entity_visibility (ent)));
 439 # endif /* defined DEBUG_libfirm */
 440
 441       eset_insert (dead_graphs, graph);
 442     }
 443   }
 444
 445   /* now delete the graphs. */
 446   for (graph = eset_first (dead_graphs);
 447        graph;
 448        graph = (ir_graph*) eset_next (dead_graphs)) {
 449
 450     if (verbose || get_opt_dead_method_elimination_verbose ()) {
 451       fprintf(stdout, "RTA: removing graph of ");
 452       DDMEO(get_irg_ent (graph));
 453     }
 454
 455     remove_irg (graph);
 456   }
 457 }
 458
 459 /* Clean up the RTA data structures.  Call this after calling rta_init */
 460 void rta_cleanup (void)
 461 {
 462 # ifdef DEBUG_libfirm
 463   int i;
 464     for (i = 0; i < get_irp_n_irgs(); i++) {
 465       irg_vrfy (get_irp_irg(i));
 466     }
 467     tr_vrfy ();
 468 # endif /* defined DEBUG_libfirm */
 469
 470   if (_live_classes) {
 471     eset_destroy (_live_classes);
 472     _live_classes = NULL;
 473   }
 474
 475   if (_live_graphs) {
 476     eset_destroy (_live_graphs);
 477     _live_graphs = NULL;
 478   }
 479 }
 480
 481 /* Say whether this class might be instantiated at any point in the program: */
 482 int  rta_is_alive_class  (type   *clazz)
 483 {
 484   return (eset_contains (_live_classes, clazz));
 485 }
 486
 487 /* Say whether this graph might be run at any time in the program: */
 488 int  rta_is_alive_graph (ir_graph *graph)
 489 {
 490   if (eset_contains (_live_graphs, graph)) {
 491     return (TRUE);
 492   }
 493
 494   return (FALSE);
 495 }
 496
 497 /* dump our opinion */
 498 void rta_report (void)
 499 {
 500   int i;
 501
 502   for (i = 0; i < get_irp_n_types(); ++i) {
 503     type *tp = get_irp_type(i);
 504     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 505       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 506     }
 507   }
 508
 509   for (i = 0; i < get_irp_n_irgs(); i++) {
 510     if (rta_is_alive_graph (get_irp_irg(i))) {
 511       fprintf(stdout, "RTA: considered called: graph of ");
 512       DDMEO(get_irg_ent (get_irp_irg(i)));
 513     }
 514   }
 515 }
 516
 517
 518 /*
 519  * $Log$
 520  * Revision 1.16  2004/06/24 06:42:14  goetz
 521  * test of firm flags
 522  *
 523  * Revision 1.15  2004/06/18 15:47:19  liekweg
 524  * minor bug fix (go forward, not backward) --flo
 525  *
 526  * Revision 1.14  2004/06/18 13:12:43  liekweg
 527  * final bug fix (calls via consts)
 528  *
 529  * Revision 1.13  2004/06/17 16:34:33  liekweg
 530  * removed DD*s
 531  *
 532  * Revision 1.12  2004/06/17 16:33:33  liekweg
 533  * minor bug fix
 534  *
 535  * Revision 1.11  2004/06/17 14:21:13  liekweg
 536  * major bugfix
 537  *
 538  * Revision 1.10  2004/06/17 10:31:41  goetz
 539  * irscc: bugfix, can now deal with loops not reachable from start
 540  * cgana: bugfix, skip_Tuple
 541  * rta: improved
 542  *
 543  * Revision 1.9  2004/06/17 08:56:03  liekweg
 544  * Fixed typos in comments
 545  *
 546  * Revision 1.8  2004/06/17 08:33:01  liekweg
 547  * Added comments; added remove_irg
 548  *
 549  * Revision 1.6  2004/06/14 13:02:03  goetz
 550  * bugfixesbug
 551  *
 552  * Revision 1.5  2004/06/13 15:03:45  liekweg
 553  * RTA auf Iterative RTA aufgebohrt --flo
 554  *
 555  * Revision 1.4  2004/06/12 19:35:04  liekweg
 556  * Kommentare eingef"ugt --flo
 557  *
 558  * Revision 1.3  2004/06/12 17:09:46  liekweg
 559  * RTA works, outedges breaks.  "Yay." --flo
 560  *
 561  * Revision 1.2  2004/06/11 18:25:39  liekweg
 562  * Added todo
 563  *
 564  * Revision 1.1  2004/06/11 18:24:18  liekweg
 565  * Added RTA --flo
 566  *
 567  */