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