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
  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_ent (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_Const == get_irn_opcode (ptr)) { /* CALL CONST */
 160       ent = get_tarval_entity (get_Const_tarval (ptr));
 161       ir_graph *graph = get_entity_irg (ent);
 162       /* don't use get_implementing_graph on a Const! */
 163       if (graph) {
 164         *change = add_graph (graph);
 165       } else {
 166         /* it's an externally allocated thing. */
 167       }
 168     } else if (iro_SymConst == get_irn_opcode (ptr)) { /* CALL SYMCONST */
 169       /* If this SymConst refers to a method the method is external_visible
 170          and therefore must be considered live anyways. */
 171       /* assert (ent && "couldn't determine entity of call to symConst"); */
 172     }
 173   } else if (iro_Alloc == op) { /* ALLOC */
 174     type *type = get_Alloc_type (node);
 175
 176     *change = add_class (type);
 177   }
 178 }
 179
 180 /**
 181    Traverse the given graph to collect method accesses and
 182    object allocations.
 183 */
 184 static int rta_fill_graph (ir_graph* graph)
 185 {
 186   int change = FALSE;
 187
 188   current_ir_graph = graph;
 189
 190   irg_walk (get_irg_end (graph), rta_act, NULL, &change);
 191
 192   return (change);
 193 }
 194
 195 /**
 196    Traverse all graphs to collect method accesses and object allocations.
 197
 198    @param rerun Whether to rely on is_alive in a second run
 199 */
 200 static int rta_fill_incremental (void)
 201 {
 202   int i;
 203   int n_runs = 0;
 204   int rerun  = TRUE;
 205   int old_ip_view = interprocedural_view;
 206
 207   interprocedural_view = 0;     /* save this for later */
 208
 209   /* init_tables has added main_irg to _live_graphs */
 210
 211   /* Need to take care of graphs that are externally
 212      visible. Pretend that they are called: */
 213
 214   if (! whole_world) {
 215     for (i = 0; i < get_irp_n_irgs(); i++) {
 216       ir_graph *graph = get_irp_irg (i);
 217
 218       entity *ent = get_irg_entity (graph);
 219       if (visibility_external_visible == get_entity_visibility (ent)) {
 220
 221         eset_insert (_live_graphs, graph);
 222
 223         /* eset_insert (_live_classes, get_entity_owner (ent)); */
 224       }
 225     }
 226   }
 227
 228   while (rerun) {
 229     ir_graph *graph;
 230
 231     /* start off new */
 232     eset *live_graphs = _live_graphs;
 233     _live_graphs = eset_create ();
 234
 235     if (verbose > 1) {
 236       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 237     }
 238
 239     /* collect what we have found previously */
 240     eset_insert_all (_live_graphs, live_graphs);
 241
 242     rerun = FALSE;
 243
 244     for (graph = eset_first (live_graphs);
 245          graph;
 246          graph = eset_next (live_graphs)) {
 247
 248       if (verbose > 1) {
 249         fprintf(stdout, "RTA: RUN %i: considering graph of ", n_runs);
 250         DDMEO(get_irg_ent (graph));
 251       }
 252
 253       rerun |= rta_fill_graph (graph);
 254     }
 255
 256     eset_destroy (live_graphs);
 257
 258     n_runs ++;
 259   }
 260
 261   interprocedural_view = old_ip_view; /* cover up our traces */
 262
 263   return (n_runs);
 264 }
 265
 266 /*
 267    Count the number of graphs that we have found to be live.
 268 */
 269 static int stats (void)
 270 {
 271   int i;
 272   int n_live_graphs = 0;
 273   int n_graphs = get_irp_n_irgs();
 274
 275   for (i = 0; i < n_graphs; i++) {
 276     ir_graph *graph = get_irp_irg(i);
 277
 278     if (rta_is_alive_graph (graph)) {
 279       n_live_graphs ++;
 280     }
 281   }
 282
 283   return (n_live_graphs);
 284 }
 285
 286 /* remove a graph, part I */
 287 /*
 288    We removed the first graph to implement the entity, so we're
 289    abstract now.  Pretend that it wasn't there at all, and every
 290    entity that used to inherit this entity's graph is now abstract.
 291 */
 292 /* Since we *know* that this entity will not be called, this is OK. */
 293 static void force_description (entity *ent, entity *addr)
 294 {
 295   int i, n_over = get_entity_n_overwrittenby (ent);
 296
 297   set_entity_peculiarity (ent, peculiarity_description);
 298
 299   for (i = 0; i < n_over; i ++) {
 300     entity *over = get_entity_overwrittenby (ent, i);
 301
 302     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 303       /* We rely on the fact that cse is performed on the const_code_irg. */
 304       entity *my_addr =
 305         tarval_to_entity(get_Const_tarval(get_atomic_ent_value(over)));
 306
 307       if (addr == my_addr) {
 308         force_description (over, addr);
 309       }
 310     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 311       /* check whether 'over' forces 'inheritance' of *our* graph: */
 312       ir_node *f_addr = get_atomic_ent_value (over);
 313       entity *impl_ent = tarval_to_entity (get_Const_tarval (f_addr));
 314
 315       assert ((get_irn_op(f_addr) == op_Const) && "can't do complex addrs");
 316       if (impl_ent == addr) {
 317         assert (0 && "gibt's denn sowas");
 318         force_description (over, addr);
 319       }
 320     }
 321   }
 322 }
 323
 324 /* remove a graph, part II */
 325 /*
 326    Note: get_implementing_graph is not well defined here (graph->ent
 327    could overwrite more than one superclass implementation (graph).
 328    Since we *know* that this entity will not be called, this is OK.
 329 */
 330 static void remove_irg (ir_graph *graph)
 331 {
 332   entity *ent = get_irg_entity (graph);
 333
 334 /*   DDMEO (get_irg_ent(graph)); */
 335
 336   /* delete the ir_graph data */
 337   remove_irp_irg (graph);
 338   /* remove reference to the graph */
 339   set_entity_irg (ent, NULL);
 340   /* find the implementation (graph) from *some* superclass: */
 341   graph = get_implementing_graph (ent);
 342
 343   if (TRUE || (NULL == graph)) { /* always pretend to be 'abstract'; let the others figure this out */
 344     /* nothing to inherit!  pretend we're abstract */
 345     force_description (ent, ent);
 346   } else {
 347     /* pretend that we inherit the implementation (graph) from some superclass: */
 348     set_entity_peculiarity (ent, peculiarity_inherited);
 349
 350     exchange (get_atomic_ent_value (ent),
 351               get_atomic_ent_value (get_irg_ent(graph)));
 352   }
 353 }
 354
 355 /**
 356    Initialise the static data structures.
 357 */
 358 static void init_tables (void)
 359 {
 360   _live_classes   = eset_create ();
 361
 362   _live_graphs = eset_create ();
 363
 364   if (get_irp_main_irg ()) {
 365     eset_insert (_live_graphs, get_irp_main_irg ());
 366   }
 367
 368   /*
 369   if (get_glob_type ()) {
 370     eset_insert (_live_classes, get_glob_type ());
 371   }
 372   */
 373 }
 374
 375 /* Initialise the RTA data structures, and perform RTA.
 376    @param   do_verbose Iff != 0, print statistics as we go along
 377    @param   do_whole_world Iff != 0, assume whole-world
 378 */
 379 void rta_init (int do_verbose, int do_whole_world)
 380 {
 381   int n_live_graphs = 0;
 382   int n_runs = 0;
 383
 384 # ifdef DEBUG_libfirm
 385   int i;
 386   for (i = 0; i < get_irp_n_irgs(); i++) {
 387     irg_vrfy (get_irp_irg(i));
 388   }
 389   tr_vrfy ();
 390 # endif /* defined DEBUG_libfirm */
 391
 392   whole_world = do_whole_world;
 393   verbose = do_verbose;
 394
 395   init_tables ();
 396
 397   n_runs = rta_fill_incremental ();
 398
 399   n_live_graphs = stats ();
 400
 401   if (verbose) {
 402     if (whole_world) {
 403       printf ("RTA: whole-world assumption\n");
 404     }
 405     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 406     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 407     printf ("RTA: n_runs        = %i\n", n_runs);
 408   }
 409
 410 # ifdef DEBUG_libfirm
 411   for (i = 0; i < get_irp_n_irgs(); i++) {
 412     irg_vrfy (get_irp_irg(i));
 413   }
 414   tr_vrfy ();
 415 # endif /* defined DEBUG_libfirm */
 416 }
 417
 418 /* Delete all graphs that we have found to be dead from the program */
 419 void rta_delete_dead_graphs (void)
 420 {
 421   int i;
 422   int n_graphs = get_irp_n_irgs ();
 423   ir_graph *graph = NULL;
 424
 425   eset *dead_graphs = eset_create ();
 426
 427   for (i = 0; i < n_graphs; i++) {
 428     graph = get_irp_irg(i);
 429
 430     if (rta_is_alive_graph (graph)) {
 431       /* do nothing (except some debugging fprintf`s :-) */
 432     } else {
 433 # ifdef DEBUG_libfirm
 434       entity *ent = get_irg_entity (graph);
 435       assert (whole_world ||
 436               (visibility_external_visible != get_entity_visibility (ent)));
 437 # endif /* defined DEBUG_libfirm */
 438
 439       eset_insert (dead_graphs, graph);
 440     }
 441   }
 442
 443   /* now delete the graphs. */
 444   for (graph = eset_first (dead_graphs);
 445        graph;
 446        graph = (ir_graph*) eset_next (dead_graphs)) {
 447
 448     if (verbose) {
 449       fprintf(stdout, "RTA: removing graph of ");
 450       DDMEO(get_irg_ent (graph));
 451     }
 452
 453     remove_irg (graph);
 454   }
 455 }
 456
 457 /* Clean up the RTA data structures.  Call this after calling rta_init */
 458 void rta_cleanup (void)
 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   if (_live_classes) {
 469     eset_destroy (_live_classes);
 470     _live_classes = NULL;
 471   }
 472
 473   if (_live_graphs) {
 474     eset_destroy (_live_graphs);
 475     _live_graphs = NULL;
 476   }
 477 }
 478
 479 /* Say whether this class might be instantiated at any point in the program: */
 480 int  rta_is_alive_class  (type   *clazz)
 481 {
 482   return (eset_contains (_live_classes, clazz));
 483 }
 484
 485 /* Say whether this graph might be run at any time in the program: */
 486 int  rta_is_alive_graph (ir_graph *graph)
 487 {
 488   if (eset_contains (_live_graphs, graph)) {
 489     return (TRUE);
 490   }
 491
 492   return (FALSE);
 493 }
 494
 495 /* dump our opinion */
 496 void rta_report (void)
 497 {
 498   int i;
 499
 500   for (i = 0; i < get_irp_n_types(); ++i) {
 501     type *tp = get_irp_type(i);
 502     if (is_class_type(tp) && rta_is_alive_class(tp)) {
 503       fprintf(stdout, "RTA: considered allocated: "); DDMT(tp);
 504     }
 505   }
 506
 507   for (i = 0; i < get_irp_n_irgs(); i++) {
 508     if (rta_is_alive_graph (get_irp_irg(i))) {
 509       fprintf(stdout, "RTA: considered called: graph of ");
 510       DDMEO(get_irg_ent (get_irp_irg(i)));
 511     }
 512   }
 513 }
 514
 515
 516 /*
 517  * $Log$
 518  * Revision 1.15  2004/06/18 15:47:19  liekweg
 519  * minor bug fix (go forward, not backward) --flo
 520  *
 521  * Revision 1.14  2004/06/18 13:12:43  liekweg
 522  * final bug fix (calls via consts)
 523  *
 524  * Revision 1.13  2004/06/17 16:34:33  liekweg
 525  * removed DD*s
 526  *
 527  * Revision 1.12  2004/06/17 16:33:33  liekweg
 528  * minor bug fix
 529  *
 530  * Revision 1.11  2004/06/17 14:21:13  liekweg
 531  * major bugfix
 532  *
 533  * Revision 1.10  2004/06/17 10:31:41  goetz
 534  * irscc: bugfix, can now deal with loops not reachable from start
 535  * cgana: bugfix, skip_Tuple
 536  * rta: improved
 537  *
 538  * Revision 1.9  2004/06/17 08:56:03  liekweg
 539  * Fixed typos in comments
 540  *
 541  * Revision 1.8  2004/06/17 08:33:01  liekweg
 542  * Added comments; added remove_irg
 543  *
 544  * Revision 1.6  2004/06/14 13:02:03  goetz
 545  * bugfixesbug
 546  *
 547  * Revision 1.5  2004/06/13 15:03:45  liekweg
 548  * RTA auf Iterative RTA aufgebohrt --flo
 549  *
 550  * Revision 1.4  2004/06/12 19:35:04  liekweg
 551  * Kommentare eingef"ugt --flo
 552  *
 553  * Revision 1.3  2004/06/12 17:09:46  liekweg
 554  * RTA works, outedges breaks.  "Yay." --flo
 555  *
 556  * Revision 1.2  2004/06/11 18:25:39  liekweg
 557  * Added todo
 558  *
 559  * Revision 1.1  2004/06/11 18:24:18  liekweg
 560  * Added RTA --flo
 561  *
 562  */