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
  17  * die Menge der instantiierten Klassen bestimmt, und daraus eine Abschätzung
  18  * der aufgerufenen Methoden 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_t.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_entity (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_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
 160       if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 161         ent = get_SymConst_entity (ptr);
 162         ir_graph *graph = get_entity_irg (ent);
 163         /* don't use get_implementing_graph on a SymConst! */
 164         if (graph) {
 165           *change = add_graph (graph);
 166         } else {
 167           /* it's an external allocated thing. */
 168         }
 169       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
 170       /* If this SymConst refers to a method the method is external_visible
 171          and therefore must be considered live anyways. */
 172       /* assert (ent && "couldn't determine entity of call to symConst"); */
 173       } else {
 174         /* other symconst. */
 175       }
 176
 177     }
 178   } else if (iro_Alloc == op) { /* ALLOC */
 179     type *type = get_Alloc_type (node);
 180
 181     *change = add_class (type);
 182   }
 183 }
 184
 185 /**
 186    Traverse the given graph to collect method accesses and
 187    object allocations.
 188 */
 189 static int rta_fill_graph (ir_graph* graph)
 190 {
 191   int change = FALSE;
 192
 193   current_ir_graph = graph;
 194
 195   irg_walk (get_irg_end (graph), rta_act, NULL, &change);
 196
 197   return (change);
 198 }
 199
 200 /**
 201    Traverse all graphs to collect method accesses and object allocations.
 202
 203    @param rerun Whether to rely on is_alive in a second run
 204 */
 205 static int rta_fill_incremental (void)
 206 {
 207   int i;
 208   int n_runs = 0;
 209   int rerun  = TRUE;
 210   int old_ip_view = interprocedural_view;
 211
 212   interprocedural_view = 0;     /* save this for later */
 213
 214   /* init_tables has added main_irg to _live_graphs */
 215
 216   /* Need to take care of graphs that are externally
 217      visible or sticky. Pretend that they are called: */
 218
 219   for (i = 0; i < get_irp_n_irgs(); i++) {
 220     ir_graph *graph = get_irp_irg (i);
 221     entity *ent = get_irg_entity (graph);
 222
 223     if (((!whole_world) &&
 224          (visibility_external_visible == get_entity_visibility (ent))) ||
 225         (stickyness_sticky == get_entity_stickyness (ent))) {
 226       eset_insert (_live_graphs, graph);
 227     }
 228   }
 229
 230   while (rerun) {
 231     ir_graph *graph;
 232
 233     /* start off new */
 234     eset *live_graphs = _live_graphs;
 235     _live_graphs = eset_create ();
 236
 237     if (verbose > 1) {
 238       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 239     }
 240
 241     /* collect what we have found previously */
 242     eset_insert_all (_live_graphs, live_graphs);
 243
 244     rerun = FALSE;
 245
 246     for (graph = eset_first (live_graphs);
 247          graph;
 248          graph = eset_next (live_graphs)) {
 249
 250       if (verbose > 1) {
 251         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 252         DDMEO(get_irg_entity (graph));
 253       }
 254
 255       rerun |= rta_fill_graph (graph);
 256     }
 257
 258     eset_destroy (live_graphs);
 259
 260     n_runs ++;
 261   }
 262
 263   interprocedural_view = old_ip_view; /* cover up our traces */
 264
 265   return (n_runs);
 266 }
 267
 268 /*
 269    Count the number of graphs that we have found to be live.
 270 */
 271 static int stats (void)
 272 {
 273   int i;
 274   int n_live_graphs = 0;
 275   int n_graphs = get_irp_n_irgs();
 276
 277   for (i = 0; i < n_graphs; i++) {
 278     ir_graph *graph = get_irp_irg(i);
 279
 280     if (rta_is_alive_graph (graph)) {
 281       n_live_graphs ++;
 282     }
 283   }
 284
 285   return (n_live_graphs);
 286 }
 287
 288 /* remove a graph, part I */
 289 /*
 290    We removed the first graph to implement the entity, so we're
 291    abstract now.  Pretend that it wasn't there at all, and every
 292    entity that used to inherit this entity's graph is now abstract.
 293 */
 294 /* Since we *know* that this entity will not be called, this is OK. */
 295 static void force_description (entity *ent, entity *addr)
 296 {
 297   int i, n_over = get_entity_n_overwrittenby (ent);
 298
 299   set_entity_peculiarity (ent, peculiarity_description);
 300
 301   for (i = 0; i < n_over; i ++) {
 302     entity *over = get_entity_overwrittenby (ent, i);
 303
 304     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 305       /* We rely on the fact that cse is performed on the const_code_irg. */
 306       entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 307
 308       if (addr == my_addr) {
 309         force_description (over, addr);
 310       }
 311     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 312       /* check whether 'over' forces 'inheritance' of *our* graph: */
 313       ir_node *f_addr = get_atomic_ent_value (over);
 314       entity *impl_ent = get_SymConst_entity (f_addr);
 315
 316       assert ((get_irn_op(f_addr) == op_SymConst) && "can't do complex addrs");
 317       if (impl_ent == addr) {
 318         assert (0 && "gibt's denn sowas");
 319         force_description (over, addr);
 320       }
 321     }
 322   }
 323 }
 324
 325 /* remove a graph, part II */
 326 /*
 327    Note: get_implementing_graph is not well defined here (graph->ent
 328    could overwrite more than one superclass implementation (graph).
 329    Since we *know* that this entity will not be called, this is OK.
 330 */
 331 static void remove_irg (ir_graph *graph)
 332 {
 333   entity *ent = get_irg_entity (graph);
 334   peculiarity pec = get_entity_peculiarity (ent);
 335
 336   /*   DDMEO (get_irg_entity(graph)); */
 337
 338   /* delete the ir_graph data */
 339   set_entity_peculiarity (ent, peculiarity_description);
 340   remove_irp_irg (graph);
 341   /* remove_irp_irg also removes the entities' reference to the graph */
 342   /*
 343     if (NULL != get_entity_irg (ent)) {
 344     set_entity_irg (ent, NULL);
 345     }
 346   */
 347   set_entity_peculiarity (ent, pec);
 348
 349   /* find the implementation (graph) from *some* superclass: */
 350   graph = get_implementing_graph (ent);
 351
 352   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 353     /* nothing to inherit!  pretend we're abstract */
 354     force_description (ent, ent);
 355   } else {
 356     /* pretend that we inherit the implementation (graph) from some superclass: */
 357     set_entity_peculiarity (ent, peculiarity_inherited);
 358
 359     exchange (get_atomic_ent_value (ent),
 360               get_atomic_ent_value (get_irg_entity(graph)));
 361   }
 362 }
 363
 364 /**
 365    Initialise the static data structures.
 366 */
 367 static void init_tables (void)
 368 {
 369   _live_classes   = eset_create ();
 370
 371   _live_graphs = eset_create ();
 372
 373   if (get_irp_main_irg ()) {
 374     eset_insert (_live_graphs, get_irp_main_irg ());
 375   }
 376
 377   /* Adding the GlobalType is pointless, since its methods are always
 378      called via a constant */
 379   /*
 380   if (get_glob_type ()) {
 381     eset_insert (_live_classes, get_glob_type ());
 382   }
 383   */
 384 }
 385
 386 /* Initialise the RTA data structures, and perform RTA.
 387    @param   do_verbose If == 1, print statistics, if > 1, chatter about every detail
 388    @param   do_whole_world Iff != 0, assume whole-world
 389 */
 390 void rta_init (int do_verbose, int do_whole_world)
 391 {
 392   int n_runs = 0;
 393
 394 # ifdef DEBUG_libfirm
 395   int i;
 396   for (i = 0; i < get_irp_n_irgs(); i++) {
 397     irg_vrfy (get_irp_irg(i));
 398   }
 399   tr_vrfy ();
 400 # endif /* defined DEBUG_libfirm */
 401
 402   whole_world = do_whole_world;
 403   verbose = do_verbose;
 404
 405   init_tables ();
 406
 407   n_runs = rta_fill_incremental ();
 408
 409   if (verbose) {
 410     int n_live_graphs = stats ();
 411
 412     if (whole_world) {
 413       printf ("RTA: whole-world assumption\n");
 414     }
 415     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 416     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 417     printf ("RTA: n_runs        = %i\n", n_runs);
 418   }
 419
 420 # ifdef DEBUG_libfirm
 421   for (i = 0; i < get_irp_n_irgs(); i++) {
 422     irg_vrfy (get_irp_irg(i));
 423   }
 424   tr_vrfy ();
 425 # endif /* defined DEBUG_libfirm */
 426 }
 427
 428 /* Delete all graphs that we have found to be dead from the program
 429    If verbose == 1, print statistics, if > 1, chatter about every detail
 430 */
 431 void rta_delete_dead_graphs (void)
 432 {
 433   int i;
 434   int n_graphs = get_irp_n_irgs ();
 435   ir_graph *graph = NULL;
 436   int n_dead_graphs = 0;
 437
 438   if (!get_optimize() || !get_opt_dead_method_elimination()) return;
 439
 440   eset *dead_graphs = eset_create ();
 441
 442   for (i = 0; i < n_graphs; i++) {
 443     graph = get_irp_irg(i);
 444
 445     if (rta_is_alive_graph (graph)) {
 446       /* do nothing (except some debugging fprintf`s :-) */
 447     } else {
 448 # ifdef DEBUG_libfirm
 449       entity *ent = get_irg_entity (graph);
 450       assert (whole_world ||
 451               (visibility_external_visible != get_entity_visibility (ent)));
 452 # endif /* defined DEBUG_libfirm */
 453
 454       n_dead_graphs ++;
 455       eset_insert (dead_graphs, graph);
 456     }
 457   }
 458
 459   /* now delete the graphs. */
 460   for (graph = eset_first (dead_graphs);
 461        graph;
 462        graph = (ir_graph*) eset_next (dead_graphs)) {
 463
 464     if ((verbose > 1) || get_opt_dead_method_elimination_verbose ()) {
 465       fprintf(stdout, "RTA: removing graph of ");
 466       DDMEO(get_irg_entity (graph));
 467     }
 468
 469     remove_irg (graph);
 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   if (eset_contains (_live_graphs, graph)) {
 509     return (TRUE);
 510   }
 511
 512   return (FALSE);
 513 }
 514
 515 /* dump our opinion */
 516 void rta_report (void)
 517 {
 518   int i;
 519
 520   for (i = 0; i < get_irp_n_types(); ++i) {
 521     type *tp = get_irp_type(i);
 522     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 523       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 524     }
 525   }
 526
 527   for (i = 0; i < get_irp_n_irgs(); i++) {
 528     if (rta_is_alive_graph (get_irp_irg(i))) {
 529       fprintf(stdout, "RTA: considered called: graph of ");
 530       DDMEO(get_irg_entity (get_irp_irg(i)));
 531     }
 532   }
 533 }
 534
 535
 536 /*
 537  * $Log$
 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  */