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