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    Find out whether the given method could be the target of a
 235    polymorphic call.
 236 */
 237 static int is_call_target (entity *method)
 238 {
 239   int is_target = FALSE;
 240   int i;
 241   int n_over;
 242
 243   /* The method could be the target of a polymorphic call if it is
 244      called or if it overrides a method that is called. */
 245
 246   if (eset_contains (_called_methods, (entity*) method)) {
 247     return (TRUE);
 248   }
 249
 250   /* not called?  check methods in superclass(es) */
 251   n_over = get_entity_n_overwrites ((entity*) method);
 252   for (i = 0; !is_target && (i < n_over); i ++) {
 253     entity *over = get_entity_overwrites ((entity*) method, i);
 254     is_target |= is_call_target (over);
 255   }
 256
 257   return (is_target);
 258 }
 259
 260 /**
 261    Given a method, find the firm graph that implements that method.
 262 */
 263 static ir_graph *get_implementing_graph (entity *method)
 264 {
 265   ir_graph *graph = get_entity_irg ((entity*) method);
 266
 267   if (NULL == graph) {
 268     int i;
 269     int n_over = get_entity_n_overwrites ((entity*) method);
 270
 271     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 272       entity *over = get_entity_overwrites ((entity*) method, i);
 273       graph = get_implementing_graph (over);
 274     }
 275   }
 276
 277   /* we *must* always return a graph != NULL, *except* when we're used
 278      inside remove_irg or force_description */
 279   /* assert (graph && "no graph"); */
 280
 281   return (graph);
 282 }
 283
 284 /**
 285    Determine wether the given method is called through polymorphy with
 286    the given graph
 287 */
 288 static int has_live_downcall (entity *method, ir_graph *graph)
 289 {
 290   int has_downcall = FALSE;
 291   int i, n_over;
 292
 293   if (graph != get_entity_irg ((entity*) method)) {
 294     return (FALSE);
 295   }
 296
 297   if (eset_contains (_called_methods, method)) {
 298     return (TRUE);
 299   }
 300
 301   /* maybe we're overwritten by a method that is called? */
 302   n_over = get_entity_n_overwrittenby ((entity*) method);
 303   for (i = 0; !has_downcall && (i < n_over); i ++) {
 304     entity *over = get_entity_overwrittenby ((entity*) method, i);
 305     has_downcall |= has_live_downcall (over, graph);
 306   }
 307
 308   return (has_downcall);
 309 }
 310
 311 /**
 312    Determine whether the given method or one of its overwriters have
 313    been used in a call to the given graph.
 314 */
 315 static int has_live_call (entity *method, ir_graph *graph)
 316 {
 317   /* maybe we're called (possibly through polymorphy)? */
 318   if (is_call_target (method)) {
 319     return (TRUE);
 320   }
 321
 322   /* maybe our subclasses have seen a call? */
 323   if (has_live_downcall (method, graph)) {
 324     return (TRUE);
 325   }
 326
 327   return (FALSE);
 328 }
 329
 330
 331 /**
 332    Determine whether the given method could be used in a call to the
 333    given graph on a live class.
 334 */
 335 static int has_live_class (entity *method, ir_graph *graph)
 336 {
 337   int has_class = FALSE;
 338   int i;
 339   int n_over;
 340   type *clazz;
 341
 342   /* DON'T stop searching when an overwriting method provides a new graph */
 343
 344   clazz = get_entity_owner (method);
 345
 346   if (rta_is_alive_class (clazz)) {
 347     return (TRUE);
 348   }
 349
 350   n_over = get_entity_n_overwrites (method);
 351   for (i = 0; !has_class && (i < n_over); i ++) {
 352     entity *over = get_entity_overwrites (method, i);
 353     has_class |= has_live_class (over, graph);
 354   }
 355
 356   return (has_class);
 357 }
 358
 359 /*
 360    Count the number of graphs that we have found to be live.  Since
 361    this touches every graph of the irp, it also forces that each graph
 362    is either in _live_graphs xor in _dead_graphs.  This is useful if
 363    we use is_alive(ir_graph*) internally.
 364 */
 365 static int stats (void)
 366 {
 367   int i;
 368   int n_live_graphs = 0;
 369   int n_graphs = get_irp_n_irgs();
 370
 371   for (i = 0; i < n_graphs; i++) {
 372     ir_graph *graph = get_irp_irg(i);
 373
 374     if (rta_is_alive_graph (graph)) {
 375       n_live_graphs ++;
 376     }
 377   }
 378
 379   return (n_live_graphs);
 380 }
 381
 382 /* remove a graph, part I */
 383 /*
 384    We removed the first graph to implement the entity, so we're
 385    abstract now.  Pretend that it wasn't there at all, and every
 386    entity that used to inherit this entity's graph is now abstract.
 387 */
 388 /* Since we *know* that this entity will not be called, this is OK. */
 389 static void force_description (entity *ent, entity *addr)
 390 {
 391   int i, n_over = get_entity_n_overwrittenby (ent);
 392
 393   set_entity_peculiarity (ent, peculiarity_description);
 394
 395   for (i = 0; i < n_over; i ++) {
 396     entity *over = get_entity_overwrittenby (ent, i);
 397
 398     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 399       /* We rely on the fact that cse is performed on the const_code_irg. */
 400       entity *my_addr =
 401         tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
 402
 403       if (addr == my_addr) {
 404         force_description (over, addr);
 405       }
 406     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 407       /* check whether 'over' forces 'inheritance' of *our* graph: */
 408       ir_node *f_addr = get_atomic_ent_value (over);
 409       entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
 410
 411       assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
 412       if (impl_ent == addr) {
 413         assert (0 && "gibt's denn sowas");
 414         force_description (over, addr);
 415       }
 416     }
 417   }
 418 }
 419
 420 /* remove a graph, part II */
 421 /*
 422    Note: get_implementing_graph is not well defined here (graph->ent
 423    could overwrite more than one superclass implementation (graph).
 424    Since we *know* that this entity will not be called, this is OK.
 425 */
 426 static void remove_irg (ir_graph *graph)
 427 {
 428   entity *ent = get_irg_entity (graph);
 429
 430 /*   DDMEO (get_irg_ent(graph)); */
 431
 432   /* delete the ir_graph data */
 433   remove_irp_irg (graph);
 434   /* remove reference to the graph */
 435   set_entity_irg (ent, NULL);
 436   /* find the implementation (graph) from *some* superclass: */
 437   graph = get_implementing_graph (ent);
 438
 439   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 440     /* nothing to inherit!  pretend we're abstract */
 441     force_description (ent, ent);
 442   } else {
 443     /* pretend that we inherit the implementation (graph) from some superclass: */
 444     set_entity_peculiarity (ent, peculiarity_inherited);
 445
 446     exchange (get_atomic_ent_value (ent),
 447               get_atomic_ent_value (get_irg_ent(graph)));
 448   }
 449 }
 450
 451 /* Initialise the RTA data structures, and perform RTA.
 452    @param   verbose Iff != 0, print statistics as we go along
 453 */
 454 void rta_init (int verbose, int whole_world)
 455 {
 456   int n_live_graphs = get_irp_n_irgs ();
 457   int n_graphs = 0;
 458   int n_runs = 0;
 459
 460 # ifdef DEBUG_libfirm
 461   int i;
 462   for (i = 0; i < get_irp_n_irgs(); i++) {
 463     irg_vrfy (get_irp_irg(i));
 464   }
 465   tr_vrfy ();
 466 # endif /* defined DEBUG_libfirm */
 467
 468   init_tables ();
 469
 470   if (verbose && whole_world) {
 471     printf ("RTA: whole-world assumption\n");
 472   }
 473
 474   if (verbose) {
 475     printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 476   }
 477
 478   rta_fill_all (FALSE);
 479
 480   while (n_graphs != n_live_graphs) {
 481     n_graphs = n_live_graphs;
 482     n_runs ++;
 483     rta_fill_all (TRUE);
 484     n_live_graphs = stats ();
 485
 486     if (verbose) {
 487       printf ("RTA: run %i (%i graphs to go)\n", n_runs, n_live_graphs);
 488     }
 489   }
 490
 491   if (verbose) {
 492     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 493     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 494     printf ("RTA: n_runs        = %i\n", n_runs);
 495   }
 496
 497 # ifdef DEBUG_libfirm
 498   for (i = 0; i < get_irp_n_irgs(); i++) {
 499     irg_vrfy (get_irp_irg(i));
 500   }
 501   tr_vrfy ();
 502 # endif /* defined DEBUG_libfirm */
 503 }
 504
 505 /* Delete all graphs that we have found to be dead from the program */
 506 void rta_delete_dead_graphs ()
 507 {
 508   int i;
 509   int n_graphs = get_irp_n_irgs ();
 510   ir_graph *graph = NULL;
 511
 512   eset *dead_graphs = eset_create ();
 513
 514   for (i = 0; i < n_graphs; i++) {
 515     graph = get_irp_irg(i);
 516
 517     if (is_alive (graph, _live_graphs, _dead_graphs)) {
 518       /* do nothing (except some debugging fprintf`s :-) */
 519     } else {
 520 # ifdef DEBUG_libfirm
 521       entity *ent = get_irg_entity (graph);
 522       assert (whole_world ||
 523               (visibility_external_visible != get_entity_visibility (ent)));
 524 # endif /* defined DEBUG_libfirm */
 525
 526       eset_insert (dead_graphs, graph);
 527     }
 528   }
 529
 530   /* now delete the graphs. */
 531   for (graph = eset_first (dead_graphs);
 532        graph;
 533        graph = (ir_graph*) eset_next (dead_graphs)) {
 534     remove_irg (graph);
 535   }
 536 }
 537
 538 /* Clean up the RTA data structures.  Call this after calling rta_init */
 539 void rta_cleanup ()
 540 {
 541 # ifdef DEBUG_libfirm
 542   int i;
 543     for (i = 0; i < get_irp_n_irgs(); i++) {
 544       irg_vrfy (get_irp_irg(i));
 545     }
 546     tr_vrfy ();
 547 # endif /* defined DEBUG_libfirm */
 548
 549   if (_live_classes) {
 550     eset_destroy (_live_classes);
 551     _live_classes = NULL;
 552   }
 553
 554   if (_live_fields) {
 555     eset_destroy (_live_fields);
 556     _live_fields = NULL;
 557   }
 558
 559   if (_called_methods) {
 560     eset_destroy (_called_methods);
 561     _called_methods = NULL;
 562   }
 563
 564   if (_live_graphs) {
 565     eset_destroy (_live_graphs);
 566     _live_graphs = NULL;
 567   }
 568
 569   if (_dead_graphs) {
 570     eset_destroy (_dead_graphs);
 571     _dead_graphs = NULL;
 572   }
 573 }
 574
 575 /* Say whether this class might be instantiated at any point in the program: */
 576 int  rta_is_alive_class  (type   *clazz)
 577 {
 578   return (eset_contains (_live_classes, clazz));
 579 }
 580
 581 /* Say whether this graph might be run at any time in the program: */
 582 int  rta_is_alive_graph (ir_graph *graph)
 583 {
 584   int has_call  = FALSE;
 585   int has_class = FALSE;
 586
 587   if (eset_contains (_live_graphs, graph)) {
 588     return (TRUE);
 589   }
 590
 591   if (eset_contains (_dead_graphs, graph)) {
 592     return (FALSE);
 593   }
 594
 595   entity *meth = get_irg_ent (graph);
 596
 597   has_call  = has_live_call (meth, graph);
 598   has_class = has_live_class (meth, graph);
 599
 600   if (has_call && has_class) {
 601     eset_insert (_live_graphs, graph);
 602
 603     return (TRUE);
 604   } else {
 605     eset_insert (_dead_graphs, graph);
 606
 607     return (FALSE);
 608   }
 609 }
 610
 611 /* Say whether there have been any accesses to this field: */
 612 int  rta_is_alive_field  (entity *field)
 613 {
 614   return (eset_contains (_live_fields, field));
 615 }
 616
 617 /* dump our opinion */
 618 void rta_report (FILE *stream)
 619 {
 620   int i;
 621
 622   for (i = 0; i < get_irp_n_types(); ++i) {
 623     type *tp = get_irp_type(i);
 624     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 625       fprintf(stream, "RTA: considered allocated: "); DDMT(tp);
 626     }
 627   }
 628
 629   for (i = 0; i < get_irp_n_irgs(); i++) {
 630     if (rta_is_alive_graph (get_irp_irg(i))) {
 631       fprintf(stream, "RTA: considered called: graph of");
 632       DDMEO(get_irg_ent (get_irp_irg(i)));
 633     }
 634   }
 635 }
 636
 637
 638 /*
 639  * $Log$
 640  * Revision 1.11  2004/06/17 14:21:13  liekweg
 641  * major bugfix
 642  *
 643  * Revision 1.10  2004/06/17 10:31:41  goetz
 644  * irscc: bugfix, can now deal with loops not reachable from start
 645  * cgana: bugfix, skip_Tuple
 646  * rta: improved
 647  *
 648  * Revision 1.9  2004/06/17 08:56:03  liekweg
 649  * Fixed typos in comments
 650  *
 651  * Revision 1.8  2004/06/17 08:33:01  liekweg
 652  * Added comments; added remove_irg
 653  *
 654  * Revision 1.6  2004/06/14 13:02:03  goetz
 655  * bugfixesbug
 656  *
 657  * Revision 1.5  2004/06/13 15:03:45  liekweg
 658  * RTA auf Iterative RTA aufgebohrt --flo
 659  *
 660  * Revision 1.4  2004/06/12 19:35:04  liekweg
 661  * Kommentare eingef"ugt --flo
 662  *
 663  * Revision 1.3  2004/06/12 17:09:46  liekweg
 664  * RTA works, outedges breaks.  "Yay." --flo
 665  *
 666  * Revision 1.2  2004/06/11 18:25:39  liekweg
 667  * Added todo
 668  *
 669  * Revision 1.1  2004/06/11 18:24:18  liekweg
 670  * Added RTA --flo
 671  *
 672  */