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 static eset *_live_fields    = NULL;
  44 static eset *_called_methods = NULL;
  45
  46 /* cache computed results */
  47 static eset *_live_graphs    = NULL;
  48 static eset *_dead_graphs    = NULL;
  49
  50 static int whole_world = 0;
  51
  52 /**
  53    Initialise the static data structures.
  54 */
  55 static void init_tables (void)
  56 {
  57   _live_classes   = eset_create ();
  58   _live_fields    = eset_create ();
  59   _called_methods = eset_create ();
  60
  61   _live_graphs = eset_create ();
  62   _dead_graphs = eset_create ();
  63
  64   if (get_irp_main_irg ()) {
  65     eset_insert (_live_graphs, get_irp_main_irg ());
  66   }
  67
  68   if (get_glob_type ()) {
  69     eset_insert (_live_classes, get_glob_type ());
  70   }
  71 }
  72
  73 /**
  74    Enter all method and field accesses and all class allocations into
  75    our tables.
  76 */
  77 static void rta_act (ir_node *node, void *env)
  78 {
  79   opcode op = get_irn_opcode (node);
  80
  81   if (iro_Call == op) {         /* CALL */
  82     entity *ent = NULL;
  83
  84     ir_node *ptr = get_Call_ptr (node);
  85
  86     if (iro_Sel == get_irn_opcode (ptr)) { /* CALL SEL */
  87       ent = get_Sel_entity (ptr);
  88     } else if (iro_Const == get_irn_opcode (ptr)) { /* CALL CONST */
  89       ent = get_tarval_entity (get_Const_tarval (ptr));
  90
  91     } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
  92       /* If this SymConst refers to a method the method is external_visible
  93      and therefore must be considered live anyways. */
  94       /* assert (ent && "couldn't determine entity of call to symConst"); */
  95     }
  96
  97     if (ent) {
  98       eset_insert (_called_methods, ent);
  99     }
 100   } else if (iro_Load  == op) { /* LOAD */
 101     ir_node *ptr = get_Load_ptr (node);
 102     entity  *ent = NULL;
 103
 104     if (iro_Sel == get_irn_opcode (ptr)) {
 105       ent = get_Sel_entity (ptr);
 106     }
 107     if (ent) {
 108       eset_insert (_live_fields, ent);
 109     }
 110   } else  if (iro_Store == op) { /* STORE */
 111     ir_node *ptr = get_Store_ptr (node);
 112     entity  *ent = NULL;
 113
 114     if (iro_Sel == get_irn_opcode (ptr)) {
 115       ent = get_Sel_entity (ptr);
 116     }
 117     if (ent) {
 118       eset_insert (_live_fields, ent);
 119     }
 120   } else if (iro_Alloc == op) { /* ALLOC */
 121     type *type = get_Alloc_type (node);
 122
 123     eset_insert (_live_classes, type);
 124   }
 125 }
 126
 127 /**
 128    Traverse the given graph to collect method and field accesses and
 129    object allocations.
 130 */
 131 static void rta_fill_graph (ir_graph* graph)
 132 {
 133   if (NULL != graph) {
 134     if (NULL != get_irg_end (graph)) {
 135       current_ir_graph = graph;
 136
 137       irg_walk (get_irg_end (graph), rta_act, NULL, NULL);
 138     }
 139   }
 140 }
 141
 142 /**
 143    Check whether the given graph is alive based on the contents of the
 144    given esets.
 145 */
 146 static int is_alive (ir_graph *graph, eset *live_graphs, eset *dead_graphs)
 147 {
 148   if (eset_contains (live_graphs, graph)) {
 149     return (TRUE);
 150   }
 151
 152   if (eset_contains (dead_graphs, graph)) {
 153     return (FALSE);
 154   }
 155
 156   assert (0 && "graph neither live not dead (shouldn't happen)");
 157 }
 158
 159 /**
 160    Traverse all graphs to collect method and field accesses and object allocations.
 161
 162    @param rerun Whether to rely on is_alive in a second run
 163 */
 164 static void rta_fill_all (int rerun)
 165 {
 166   int i;
 167   int old_ip_view = interprocedural_view;
 168   eset *live_graphs = NULL;
 169   eset *dead_graphs = NULL;
 170
 171   interprocedural_view = 0;     /* save this for later */
 172
 173   if (rerun) {
 174     int n_graphs = get_irp_n_irgs ();
 175
 176     /* force all graphs to be entered in either live_graphs or dead_graphs */
 177     for (i = 0; i < n_graphs; i ++) {
 178       rta_is_alive_graph (get_irp_irg (i));
 179     }
 180
 181     /* remember existing infos for later */
 182     live_graphs = _live_graphs;
 183     dead_graphs = _dead_graphs;
 184
 185     /* ensure that live_graphs and dead_graphs aren't deallocated by rta_cleanup */
 186     _live_graphs = NULL;
 187     _dead_graphs = NULL;
 188
 189     rta_cleanup ();
 190     init_tables ();
 191   }
 192
 193   /* Consider all graphs, possibly taking into account existing infos */
 194   for (i = 0; i < get_irp_n_irgs(); i++) {
 195     ir_graph *graph = get_irp_irg (i);
 196
 197     if (! whole_world) {
 198       /* Need to take care of graphs that are externally
 199          visible. Pretend that they are called: */
 200       entity *ent = get_irg_entity (graph);
 201       if (visibility_external_visible == get_entity_visibility (ent)) {
 202         eset_insert (_called_methods, ent);
 203
 204         if (get_entity_irg (ent)) {
 205           eset_insert (_live_graphs, get_entity_irg (ent));
 206         }
 207
 208         eset_insert (_live_classes, get_entity_owner (ent));
 209       }
 210     }
 211
 212     /* now check the graph */
 213     if (rerun) {
 214       if (is_alive (graph, live_graphs, dead_graphs)) {
 215         rta_fill_graph (graph);
 216       } else {
 217         /* nothing (except debugging printf's :-) */
 218       }
 219     } else {
 220       rta_fill_graph (graph);
 221     }
 222   }
 223
 224   if (rerun) {
 225     /* clean up the tables that we have retained */
 226     eset_destroy (live_graphs);
 227     eset_destroy (dead_graphs);
 228   }
 229
 230   interprocedural_view = old_ip_view; /* cover up our traces */
 231 }
 232
 233 /**
 234    Given a method, find the firm graph that implements that method.
 235 */
 236 static ir_graph *get_implementing_graph (entity *method)
 237 {
 238   ir_graph *graph = get_entity_irg ((entity*) method);
 239
 240   if (NULL == graph) {
 241     int i;
 242     int n_over = get_entity_n_overwrites ((entity*) method);
 243
 244     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 245       entity *over = get_entity_overwrites ((entity*) method, i);
 246       graph = get_implementing_graph (over);
 247     }
 248   }
 249
 250   /* we *must* always return a graph != NULL, *except* when we're used
 251      inside remove_irg or force_description */
 252   /* assert (graph && "no graph"); */
 253
 254   return (graph);
 255 }
 256
 257 /* -------------------------------------------------------------------
 258    Method Calls
 259    ------------------------------------------------------------------- */
 260 /**
 261    Find out whether the given method could be the target of a
 262    polymorphic call.
 263 */
 264 static int has_live_upcall (entity *method)
 265 {
 266   int is_target = FALSE;
 267   int i;
 268   int n_over;
 269
 270   /* The method could be the target of a polymorphic call if it is
 271      called or if it overrides a method that is called. */
 272
 273   if (eset_contains (_called_methods, (entity*) method)) {
 274     return (TRUE);
 275   }
 276
 277   /* not called?  check methods in superclass(es) */
 278   n_over = get_entity_n_overwrites ((entity*) method);
 279   for (i = 0; !is_target && (i < n_over); i ++) {
 280     entity *over = get_entity_overwrites ((entity*) method, i);
 281     is_target |= has_live_upcall (over);
 282   }
 283
 284   return (is_target);
 285 }
 286
 287 /**
 288    Determine wether the given method is called through polymorphy with
 289    the given graph
 290 */
 291 static int has_live_downcall (entity *method, ir_graph *graph)
 292 {
 293   int has_downcall = FALSE;
 294   int i, n_over;
 295
 296   if (graph != get_entity_irg ((entity*) method)) {
 297     return (FALSE);
 298   }
 299
 300   if (eset_contains (_called_methods, method)) {
 301     return (TRUE);
 302   }
 303
 304   /* maybe we're overwritten by a method that is called? */
 305   n_over = get_entity_n_overwrittenby ((entity*) method);
 306   for (i = 0; !has_downcall && (i < n_over); i ++) {
 307     entity *over = get_entity_overwrittenby ((entity*) method, i);
 308     has_downcall |= has_live_downcall (over, graph);
 309   }
 310
 311   return (has_downcall);
 312 }
 313
 314 /**
 315    Determine whether the given method or one of its overwriters have
 316    been used in a call to the given graph.
 317 */
 318 static int has_live_call (entity *method, ir_graph *graph)
 319 {
 320   /* maybe we're called (possibly through polymorphy)? */
 321   if (has_live_upcall (method)) {
 322     return (TRUE);
 323   }
 324
 325   /* maybe our subclasses have seen a call? */
 326   if (has_live_downcall (method, graph)) {
 327     return (TRUE);
 328   }
 329
 330   return (FALSE);
 331 }
 332
 333 /* -------------------------------------------------------------------
 334    Class Instantiations
 335    ------------------------------------------------------------------- */
 336 static int has_live_superclass (entity *method, ir_graph *graph)
 337 {
 338   int has_super = FALSE;
 339   int i;
 340   int n_over;
 341
 342   /* The method could be the target of a polymorphic call if it is
 343      called or if it overrides a method that is called. */
 344
 345   if (eset_contains (_live_classes, get_entity_owner (method))) {
 346     return (TRUE);
 347   }
 348
 349   /* not allocated?  check methods in superclass(es) */
 350   n_over = get_entity_n_overwrites ((entity*) method);
 351   for (i = 0; !has_super && (i < n_over); i ++) {
 352     entity *over = get_entity_overwrites ((entity*) method, i);
 353     has_super |= has_live_superclass (over, graph);
 354   }
 355
 356   return (has_super);
 357 }
 358
 359 static int has_live_subclass (entity *method, ir_graph *graph)
 360 {
 361   int has_sub = FALSE;
 362   int i;
 363   int n_over;
 364
 365   /* a class that doesn't use the graph in question can't help here: */
 366   ir_graph *impl = get_implementing_graph (method);
 367
 368   /* this function is only called starting at 'graph's method, and
 369      we're checking *downwards*, so impl must be != NULL */
 370   assert (impl);
 371   if (impl != graph) {
 372     return (FALSE);
 373   }
 374
 375   /* otherwise, an instantiated class helps a lot! */
 376   if (rta_is_alive_class (get_entity_owner (method))) {
 377     return (TRUE);
 378   }
 379
 380   /* maybe our subclasses use this graph *and* have been instantiated ? */
 381   n_over = get_entity_n_overwrittenby ((entity*) method);
 382   for (i = 0; !has_sub && (i < n_over); i ++) {
 383     entity *over = get_entity_overwrittenby ((entity*) method, i);
 384     has_sub |= has_live_subclass (over, graph);
 385   }
 386
 387   return (has_sub);
 388 }
 389
 390
 391 /**
 392    Determine whether the given method could be used in a call to the
 393    given graph on a live class.
 394 */
 395 static int has_live_class (entity *method, ir_graph *graph)
 396 {
 397   /* maybe we're called (possibly through polymorphy)? */
 398   if (has_live_superclass (method, graph)) {
 399     return (TRUE);
 400   }
 401
 402   /* maybe our subclasses have seen a call? */
 403   if (has_live_subclass (method, graph)) {
 404     return (TRUE);
 405   }
 406
 407   return (FALSE);
 408
 409 }
 410
 411 /*
 412    Count the number of graphs that we have found to be live.  Since
 413    this touches every graph of the irp, it also forces that each graph
 414    is either in _live_graphs xor in _dead_graphs.  This is useful if
 415    we use is_alive(ir_graph*) internally.
 416 */
 417 static int stats (void)
 418 {
 419   int i;
 420   int n_live_graphs = 0;
 421   int n_graphs = get_irp_n_irgs();
 422
 423   for (i = 0; i < n_graphs; i++) {
 424     ir_graph *graph = get_irp_irg(i);
 425
 426     if (rta_is_alive_graph (graph)) {
 427       n_live_graphs ++;
 428     }
 429   }
 430
 431   return (n_live_graphs);
 432 }
 433
 434 /* remove a graph, part I */
 435 /*
 436    We removed the first graph to implement the entity, so we're
 437    abstract now.  Pretend that it wasn't there at all, and every
 438    entity that used to inherit this entity's graph is now abstract.
 439 */
 440 /* Since we *know* that this entity will not be called, this is OK. */
 441 static void force_description (entity *ent, entity *addr)
 442 {
 443   int i, n_over = get_entity_n_overwrittenby (ent);
 444
 445   set_entity_peculiarity (ent, peculiarity_description);
 446
 447   for (i = 0; i < n_over; i ++) {
 448     entity *over = get_entity_overwrittenby (ent, i);
 449
 450     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 451       /* We rely on the fact that cse is performed on the const_code_irg. */
 452       entity *my_addr =
 453         tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
 454
 455       if (addr == my_addr) {
 456         force_description (over, addr);
 457       }
 458     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 459       /* check whether 'over' forces 'inheritance' of *our* graph: */
 460       ir_node *f_addr = get_atomic_ent_value (over);
 461       entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
 462
 463       assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
 464       if (impl_ent == addr) {
 465         assert (0 && "gibt's denn sowas");
 466         force_description (over, addr);
 467       }
 468     }
 469   }
 470 }
 471
 472 /* remove a graph, part II */
 473 /*
 474    Note: get_implementing_graph is not well defined here (graph->ent
 475    could overwrite more than one superclass implementation (graph).
 476    Since we *know* that this entity will not be called, this is OK.
 477 */
 478 static void remove_irg (ir_graph *graph)
 479 {
 480   entity *ent = get_irg_entity (graph);
 481
 482 /*   DDMEO (get_irg_ent(graph)); */
 483
 484   /* delete the ir_graph data */
 485   remove_irp_irg (graph);
 486   /* remove reference to the graph */
 487   set_entity_irg (ent, NULL);
 488   /* find the implementation (graph) from *some* superclass: */
 489   graph = get_implementing_graph (ent);
 490
 491   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 492     /* nothing to inherit!  pretend we're abstract */
 493     force_description (ent, ent);
 494   } else {
 495     /* pretend that we inherit the implementation (graph) from some superclass: */
 496     set_entity_peculiarity (ent, peculiarity_inherited);
 497
 498     exchange (get_atomic_ent_value (ent),
 499               get_atomic_ent_value (get_irg_ent(graph)));
 500   }
 501 }
 502
 503 /* Initialise the RTA data structures, and perform RTA.
 504    @param   verbose Iff != 0, print statistics as we go along
 505 */
 506 void rta_init (int verbose, int do_whole_world)
 507 {
 508   int n_live_graphs = get_irp_n_irgs ();
 509   int n_graphs = 0;
 510   int n_runs = 0;
 511
 512   whole_world = do_whole_world;
 513
 514 # ifdef DEBUG_libfirm
 515   int i;
 516   for (i = 0; i < get_irp_n_irgs(); i++) {
 517     irg_vrfy (get_irp_irg(i));
 518   }
 519   tr_vrfy ();
 520 # endif /* defined DEBUG_libfirm */
 521
 522   init_tables ();
 523
 524   if (verbose && whole_world) {
 525     printf ("RTA: whole-world assumption\n");
 526   }
 527
 528   if (verbose) {
 529     printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 530   }
 531
 532   rta_fill_all (FALSE);
 533
 534   while (n_graphs != n_live_graphs) {
 535     n_graphs = n_live_graphs;
 536     n_runs ++;
 537     rta_fill_all (TRUE);
 538     n_live_graphs = stats ();
 539
 540     if (verbose) {
 541       printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 542     }
 543   }
 544
 545   if (verbose) {
 546     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 547     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 548     printf ("RTA: n_runs        = %i\n", n_runs);
 549   }
 550
 551 # ifdef DEBUG_libfirm
 552   for (i = 0; i < get_irp_n_irgs(); i++) {
 553     irg_vrfy (get_irp_irg(i));
 554   }
 555   tr_vrfy ();
 556 # endif /* defined DEBUG_libfirm */
 557 }
 558
 559 /* Delete all graphs that we have found to be dead from the program */
 560 void rta_delete_dead_graphs ()
 561 {
 562   int i;
 563   int n_graphs = get_irp_n_irgs ();
 564   ir_graph *graph = NULL;
 565
 566   eset *dead_graphs = eset_create ();
 567
 568   for (i = 0; i < n_graphs; i++) {
 569     graph = get_irp_irg(i);
 570
 571     if (is_alive (graph, _live_graphs, _dead_graphs)) {
 572       /* do nothing (except some debugging fprintf`s :-) */
 573     } else {
 574 # ifdef DEBUG_libfirm
 575       entity *ent = get_irg_entity (graph);
 576       assert (whole_world ||
 577               (visibility_external_visible != get_entity_visibility (ent)));
 578 # endif /* defined DEBUG_libfirm */
 579
 580       eset_insert (dead_graphs, graph);
 581     }
 582   }
 583
 584   /* now delete the graphs. */
 585   for (graph = eset_first (dead_graphs);
 586        graph;
 587        graph = (ir_graph*) eset_next (dead_graphs)) {
 588     remove_irg (graph);
 589   }
 590 }
 591
 592 /* Clean up the RTA data structures.  Call this after calling rta_init */
 593 void rta_cleanup ()
 594 {
 595 # ifdef DEBUG_libfirm
 596   int i;
 597     for (i = 0; i < get_irp_n_irgs(); i++) {
 598       irg_vrfy (get_irp_irg(i));
 599     }
 600     tr_vrfy ();
 601 # endif /* defined DEBUG_libfirm */
 602
 603   if (_live_classes) {
 604     eset_destroy (_live_classes);
 605     _live_classes = NULL;
 606   }
 607
 608   if (_live_fields) {
 609     eset_destroy (_live_fields);
 610     _live_fields = NULL;
 611   }
 612
 613   if (_called_methods) {
 614     eset_destroy (_called_methods);
 615     _called_methods = NULL;
 616   }
 617
 618   if (_live_graphs) {
 619     eset_destroy (_live_graphs);
 620     _live_graphs = NULL;
 621   }
 622
 623   if (_dead_graphs) {
 624     eset_destroy (_dead_graphs);
 625     _dead_graphs = NULL;
 626   }
 627 }
 628
 629 /* Say whether this class might be instantiated at any point in the program: */
 630 int  rta_is_alive_class  (type   *clazz)
 631 {
 632   return (eset_contains (_live_classes, clazz));
 633 }
 634
 635 /* Say whether this graph might be run at any time in the program: */
 636 int  rta_is_alive_graph (ir_graph *graph)
 637 {
 638   int has_call  = FALSE;
 639   int has_class = FALSE;
 640
 641   if (eset_contains (_live_graphs, graph)) {
 642     return (TRUE);
 643   }
 644
 645   if (eset_contains (_dead_graphs, graph)) {
 646     return (FALSE);
 647   }
 648
 649   entity *meth = get_irg_ent (graph);
 650
 651   has_call  = has_live_call (meth, graph);
 652   has_class = has_live_class (meth, graph);
 653
 654   if (has_call && has_class) {
 655     eset_insert (_live_graphs, graph);
 656
 657     return (TRUE);
 658   } else {
 659     eset_insert (_dead_graphs, graph);
 660
 661     return (FALSE);
 662   }
 663 }
 664
 665 /* Say whether there have been any accesses to this field: */
 666 int  rta_is_alive_field  (entity *field)
 667 {
 668   return (eset_contains (_live_fields, field));
 669 }
 670
 671 /* dump our opinion */
 672 void rta_report (FILE *stream)
 673 {
 674   int i;
 675
 676   for (i = 0; i < get_irp_n_types(); ++i) {
 677     type *tp = get_irp_type(i);
 678     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 679       fprintf(stream, "RTA: considered allocated: "); DDMT(tp);
 680     }
 681   }
 682
 683   for (i = 0; i < get_irp_n_irgs(); i++) {
 684     if (rta_is_alive_graph (get_irp_irg(i))) {
 685       fprintf(stream, "RTA: considered called: graph of");
 686       DDMEO(get_irg_ent (get_irp_irg(i)));
 687     }
 688   }
 689 }
 690
 691
 692 /*
 693  * $Log$
 694  * Revision 1.13  2004/06/17 16:34:33  liekweg
 695  * removed DD*s
 696  *
 697  * Revision 1.12  2004/06/17 16:33:33  liekweg
 698  * minor bug fix
 699  *
 700  * Revision 1.11  2004/06/17 14:21:13  liekweg
 701  * major bugfix
 702  *
 703  * Revision 1.10  2004/06/17 10:31:41  goetz
 704  * irscc: bugfix, can now deal with loops not reachable from start
 705  * cgana: bugfix, skip_Tuple
 706  * rta: improved
 707  *
 708  * Revision 1.9  2004/06/17 08:56:03  liekweg
 709  * Fixed typos in comments
 710  *
 711  * Revision 1.8  2004/06/17 08:33:01  liekweg
 712  * Added comments; added remove_irg
 713  *
 714  * Revision 1.6  2004/06/14 13:02:03  goetz
 715  * bugfixesbug
 716  *
 717  * Revision 1.5  2004/06/13 15:03:45  liekweg
 718  * RTA auf Iterative RTA aufgebohrt --flo
 719  *
 720  * Revision 1.4  2004/06/12 19:35:04  liekweg
 721  * Kommentare eingef"ugt --flo
 722  *
 723  * Revision 1.3  2004/06/12 17:09:46  liekweg
 724  * RTA works, outedges breaks.  "Yay." --flo
 725  *
 726  * Revision 1.2  2004/06/11 18:25:39  liekweg
 727  * Added todo
 728  *
 729  * Revision 1.1  2004/06/11 18:24:18  liekweg
 730  * Added RTA --flo
 731  *
 732  */