nsz Git - libfirm/blob - ir/ana/rta.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Interprocedural analysis to improve the call graph estimate.
  23  * @author   Florian
  24  * @version  09.06.2002
  25  * @version  $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include "rta.h"
  32
  33 #include <stdlib.h>
  34
  35 #include "irnode_t.h"
  36 #include "irprog_t.h"
  37 #include "irgraph_t.h"
  38
  39 #include "eset.h"
  40 #include "irgwalk.h"
  41 #include "irgmod.h"
  42 #include "irvrfy.h"
  43 #include "irprintf.h"
  44
  45 # ifndef TRUE
  46 #  define TRUE 1
  47 #  define FALSE 0
  48 # endif /* not defined TRUE */
  49
  50 /* flags */
  51 static int verbose     = 0;
  52
  53
  54 /* base data */
  55 static eset *_live_classes   = NULL;
  56
  57 /* cache computed results */
  58 static eset *_live_graphs    = NULL;
  59
  60 /**
  61    Given a method, find the firm graph that implements that method.
  62 */
  63 static ir_graph *get_implementing_graph (ir_entity *method)
  64 {
  65 #if 0
  66   ir_graph *graph = get_entity_irg ((ir_entity*) method);
  67
  68   /* Search upwards in the overwrites graph. */
  69   /* GL: this will not work for multiple inheritance */
  70   if (NULL == graph) {
  71     int i;
  72     int n_over = get_entity_n_overwrites ((ir_entity*) method);
  73
  74     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
  75       ir_entity *over = get_entity_overwrites ((ir_entity*) method, i);
  76       graph = get_implementing_graph (over);
  77     }
  78   }
  79
  80   /* GL   this is not valid in our remove irg algorithm ... which we removed by now ...  */
  81   assert(get_entity_peculiarity(method) == peculiarity_description
  82      || graph == get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method))));
  83
  84   /* we *must* always return a graph != NULL, *except* when we're used
  85      inside remove_irg or force_description */
  86   /* assert (graph && "no graph"); */
  87
  88   return (graph);
  89 #else
  90   ir_graph *graph = NULL;
  91
  92   if (get_entity_peculiarity(method) != peculiarity_description)
  93     graph = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(method)));
  94
  95   return graph;
  96 #endif
  97 }
  98
  99 /**
 100  * Add a graph to the set of live graphs.
 101  *
 102  * @param graph  the graph to add
 103  * @return non-zero if the graph was added, zero
 104  *         if it was already in the live set
 105  */
 106 static int add_graph (ir_graph *graph)
 107 {
 108   if (!eset_contains (_live_graphs, graph)) {
 109     if (verbose > 1) {
 110       ir_fprintf(stdout, "RTA:        new graph of %+F\n", graph);
 111     }
 112
 113     eset_insert (_live_graphs, graph);
 114     return (TRUE);
 115   }
 116
 117   return (FALSE);
 118 }
 119
 120 /**
 121  * Add a class to the set of live classes.
 122  *
 123  * @param clazz   the class to add
 124  * @return non-zero if the graph was added, zero
 125  *         if it was already in the live set
 126  */
 127 static int add_class (ir_type *clazz)
 128 {
 129   if (!eset_contains (_live_classes, clazz)) {
 130     if (verbose > 1) {
 131       ir_fprintf(stdout, "RTA:        new class: %+F\n", clazz);
 132     }
 133
 134     eset_insert (_live_classes, clazz);
 135     return (TRUE);
 136   }
 137
 138   return (FALSE);
 139 }
 140
 141 /** Given an entity, add all implementing graphs that belong to live classes
 142  *  to _live_graphs.
 143  *
 144  *  Iff additions occurred, return TRUE, else FALSE.
 145 */
 146 static int add_implementing_graphs (ir_entity *method)
 147 {
 148   int i;
 149   int n_over = get_entity_n_overwrittenby (method);
 150   ir_graph *graph = get_entity_irg (method);
 151   int change = FALSE;
 152
 153   if (NULL == graph) {
 154     graph = get_implementing_graph (method);
 155   }
 156
 157   if (verbose > 1) {
 158     ir_fprintf(stdout, "RTA:        new call to %+F\n", method);
 159   }
 160
 161   if (rta_is_alive_class (get_entity_owner (method))) {
 162     if (NULL != graph) {
 163       change = add_graph (graph);
 164     }
 165   }
 166
 167   for (i = 0; i < n_over; i ++) {
 168     ir_entity *over = get_entity_overwrittenby (method, i);
 169     change |= add_implementing_graphs (over);
 170   }
 171
 172   return (change);
 173 }
 174
 175 /** Enter all method accesses and all class allocations into
 176  *  our tables.
 177  *
 178  *  Set *(int*)env to true iff (possibly) new graphs have been found.
 179  */
 180 static void rta_act (ir_node *node, void *env)
 181 {
 182   int *change = (int*) env;
 183   ir_opcode op = get_irn_opcode (node);
 184
 185   if (iro_Call == op) {         /* CALL */
 186     ir_entity *ent = NULL;
 187
 188     ir_node *ptr = get_Call_ptr (node);
 189
 190     /* CALL SEL */
 191     if (iro_Sel == get_irn_opcode (ptr)) {
 192       ent = get_Sel_entity (ptr);
 193       *change |= add_implementing_graphs (ent);
 194
 195       /* CALL SYMCONST */
 196     } else if (iro_SymConst == get_irn_opcode (ptr)) {
 197       if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 198         ir_graph *graph;
 199
 200         ent = get_SymConst_entity (ptr);
 201         graph = get_entity_irg (ent);
 202         if (graph) {
 203           *change |= add_graph (graph);
 204         } else {
 205           /* it's an external allocated thing. */
 206         }
 207       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
 208             /* Entities of kind addr_name may not be allocated in this compilation unit.
 209                If so, the frontend built faulty Firm.  So just ignore. */
 210             /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
 211         assert (ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
 212       } else {
 213         /* other symconst. */
 214         assert(0 && "This SymConst can not be an address for a method call.");
 215       }
 216
 217       /* STRANGE */
 218     } else {
 219       assert(0 && "Unexpected address expression: can not analyse, therefore can not do correct rta!");
 220     }
 221
 222   } else if (iro_Alloc == op) { /* ALLOC */
 223     ir_type *type = get_Alloc_type (node);
 224
 225     *change |= add_class (type);
 226   }
 227 }
 228
 229 /**
 230    Traverse the given graph to collect method accesses and
 231    object allocations.
 232 */
 233 static int rta_fill_graph (ir_graph* graph)
 234 {
 235   int change = FALSE;
 236   irg_walk_graph (graph, rta_act, NULL, &change);
 237   return change;
 238 }
 239
 240 /** Traverse all graphs to collect method accesses and object allocations.
 241  */
 242 static int rta_fill_incremental (void)
 243 {
 244   int i;
 245   int n_runs = 0;
 246   int rerun  = TRUE;
 247 #ifdef INTERPROCEDURAL_VIEW
 248   int old_ip_view = get_interprocedural_view();
 249
 250   set_interprocedural_view(0);     /* save this for later */
 251 #endif
 252
 253   /* init_tables has added main_irg to _live_graphs */
 254
 255   /* Need to take care of graphs that are externally
 256      visible or sticky. Pretend that they are called: */
 257
 258   for (i = 0; i < get_irp_n_irgs(); i++) {
 259     ir_graph *graph = get_irp_irg (i);
 260     ir_entity *ent = get_irg_entity (graph);
 261
 262     if ((visibility_external_visible == get_entity_visibility (ent)) ||
 263         (stickyness_sticky == get_entity_stickyness (ent))) {
 264       eset_insert (_live_graphs, graph);
 265       // printf("external visible: "); DDMG(graph);
 266     }
 267   }
 268
 269   while (rerun) {
 270     ir_graph *graph;
 271
 272     /* start off new */
 273     eset *live_graphs = _live_graphs;
 274     _live_graphs = eset_create ();
 275
 276     if (verbose > 1) {
 277       fprintf(stdout, "RTA: RUN %i\n", n_runs);
 278     }
 279
 280     /* collect what we have found previously */
 281     eset_insert_all (_live_graphs, live_graphs);
 282
 283     rerun = FALSE;
 284     for (graph = eset_first (live_graphs);
 285          graph;
 286          graph = eset_next (live_graphs)) {
 287
 288       if (verbose > 1) {
 289         ir_fprintf(stdout, "RTA: RUN %i: considering graph of %+F\n", n_runs,
 290                         graph);
 291       }
 292
 293       rerun |= rta_fill_graph (graph);
 294     }
 295
 296     eset_destroy (live_graphs);
 297
 298     n_runs ++;
 299   }
 300
 301 #ifdef INTERPROCEDURAL_VIEW
 302   set_interprocedural_view(old_ip_view); /* cover up our traces */
 303 #endif
 304
 305   return (n_runs);
 306 }
 307
 308 /**
 309  * Count the number of graphs that we have found to be live.
 310  */
 311 static int stats (void)
 312 {
 313   int i;
 314   int n_live_graphs = 0;
 315   int n_graphs = get_irp_n_irgs();
 316
 317   for (i = 0; i < n_graphs; i++) {
 318     ir_graph *graph = get_irp_irg(i);
 319
 320     if (rta_is_alive_graph (graph)) {
 321       n_live_graphs ++;
 322     }
 323   }
 324
 325   return (n_live_graphs);
 326 }
 327
 328 /* remove a graph, part I */
 329 /*
 330    We removed the first graph to implement the entity, so we're
 331    abstract now.  Pretend that it wasn't there at all, and every
 332    entity that used to inherit this entity's graph is now abstract.
 333 */
 334 /* Since we *know* that this entity will not be called, this is OK. */
 335 static void force_description (ir_entity *ent, ir_entity *addr)
 336 {
 337   int i, n_over = get_entity_n_overwrittenby (ent);
 338
 339   set_entity_peculiarity (ent, peculiarity_description);
 340
 341   for (i = 0; i < n_over; i ++) {
 342     ir_entity *over = get_entity_overwrittenby (ent, i);
 343
 344     if (peculiarity_inherited == get_entity_peculiarity (over)) {
 345       /* We rely on the fact that cse is performed on the const_code_irg. */
 346       ir_entity *my_addr = get_SymConst_entity(get_atomic_ent_value(over));
 347
 348       if (addr == my_addr) {
 349         force_description (over, addr);
 350       }
 351     } else if (peculiarity_existent == get_entity_peculiarity (over)) {
 352       /* check whether 'over' forces 'inheritance' of *our* graph: */
 353       ir_node *f_addr = get_atomic_ent_value (over);
 354       ir_entity *impl_ent = get_SymConst_entity (f_addr);
 355
 356       assert(is_SymConst(f_addr) && "can't do complex addrs");
 357       if (impl_ent == addr) {
 358         assert (0 && "gibt's denn sowas");
 359         force_description (over, addr);
 360       }
 361     }
 362   }
 363 }
 364
 365 /**
 366    Initialize the static data structures.
 367 */
 368 static void init_tables (void)
 369 {
 370   ir_type *tp;
 371   int i, n;
 372
 373   _live_classes = eset_create ();
 374   _live_graphs  = eset_create ();
 375
 376   if (get_irp_main_irg ()) {
 377     eset_insert (_live_graphs, get_irp_main_irg ());
 378   }
 379
 380   /* Find static allocated classes */
 381   tp = get_glob_type();
 382   n = get_class_n_members(tp);
 383   for (i = 0; i < n; ++i) {
 384     ir_type *member_type = get_entity_type(get_class_member(tp, i));
 385     if (is_Class_type(member_type))
 386       eset_insert(_live_classes, member_type);
 387   }
 388
 389   tp = get_tls_type();
 390   n = get_struct_n_members(tp);
 391   for (i = 0; i < n; ++i) {
 392     ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 393     if (is_Class_type(member_type))
 394       eset_insert(_live_classes, member_type);
 395   }
 396 }
 397
 398 /*
 399  * Initialize the RTA data structures, and perform RTA.
 400  * do_verbose If == 1, print statistics, if > 1, chatter about every detail
 401  */
 402 void rta_init (int do_verbose)
 403 {
 404   int n_runs = 0;
 405
 406   int rem_vpi = get_visit_pseudo_irgs();
 407   set_visit_pseudo_irgs(1);
 408
 409 # ifdef DEBUG_libfirm
 410   {
 411     int i, n;
 412     n = get_irp_n_irgs();
 413     for (i = 0; i < n; i++) {
 414       irg_vrfy (get_irp_irg(i));
 415         }
 416     tr_vrfy ();
 417   }
 418 # endif /* defined DEBUG_libfirm */
 419
 420   verbose = do_verbose;
 421
 422   init_tables ();
 423
 424   n_runs = rta_fill_incremental ();
 425
 426   if (verbose) {
 427     int n_live_graphs = stats ();
 428
 429     printf ("RTA: n_graphs      = %i\n", get_irp_n_irgs ());
 430     printf ("RTA: n_live_graphs = %i\n", n_live_graphs);
 431     printf ("RTA: n_runs        = %i\n", n_runs);
 432   }
 433
 434 # ifdef DEBUG_libfirm
 435   {
 436     int i, n;
 437     n = get_irp_n_irgs();
 438     for (i = 0; i < n; i++) {
 439       irg_vrfy (get_irp_irg(i));
 440         }
 441     tr_vrfy ();
 442   }
 443 # endif /* defined DEBUG_libfirm */
 444
 445   set_visit_pseudo_irgs(rem_vpi);
 446 }
 447
 448 /**
 449  * walker for all types and entities
 450  *
 451  * Changes the peculiarity of entities that represents
 452  * dead graphs to peculiarity_description.
 453  */
 454 static void make_entity_to_description(type_or_ent tore, void *env) {
 455   (void) env;
 456   if (is_entity(tore.ent)) {
 457     ir_entity *ent = tore.ent;
 458
 459     if ((is_Method_type(get_entity_type(ent)))                        &&
 460         (get_entity_peculiarity(ent) != peculiarity_description)      &&
 461         (get_entity_visibility(ent)  != visibility_external_allocated)   ) {
 462       ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
 463       if (!eset_contains (_live_graphs, irg)) {
 464         set_entity_peculiarity(ent, peculiarity_description);
 465         set_entity_irg(ent, NULL);
 466       }
 467     }
 468   }
 469 }
 470
 471 /* Delete all graphs that we have found to be dead from the program
 472    If verbose == 1, print statistics, if > 1, chatter about every detail
 473 */
 474 void rta_delete_dead_graphs (void)
 475 {
 476   int i;
 477   int n_graphs = get_irp_n_irgs ();
 478   ir_graph *graph = NULL;
 479   int n_dead_graphs = 0;
 480   ir_graph **dead_graphs;
 481
 482   int rem_vpi = get_visit_pseudo_irgs();
 483   set_visit_pseudo_irgs(1);
 484
 485   dead_graphs = xmalloc(sizeof(*dead_graphs) * get_irp_n_irgs());
 486
 487   for (i = 0; i < n_graphs; i++) {
 488     graph = get_irp_irg(i);
 489
 490     if (rta_is_alive_graph (graph)) {
 491       /* do nothing (except some debugging fprintf`s :-) */
 492     } else {
 493 #ifndef NDEBUG
 494       ir_entity *ent = get_irg_entity (graph);
 495       assert (visibility_external_visible != get_entity_visibility (ent));
 496 #endif
 497
 498       dead_graphs[n_dead_graphs] = graph;
 499       n_dead_graphs ++;
 500     }
 501   }
 502
 503   type_walk(make_entity_to_description, NULL, NULL);
 504   for (i = 0; i < n_dead_graphs; ++i) {
 505     remove_irp_irg (dead_graphs[i]);
 506   }
 507
 508   if (verbose) {
 509     printf ("RTA: n_dead_graphs = %i\n", n_dead_graphs);
 510   }
 511
 512   set_visit_pseudo_irgs(rem_vpi);
 513
 514   free(dead_graphs);
 515 }
 516
 517 /* Clean up the RTA data structures.  Call this after calling rta_init */
 518 void rta_cleanup (void)
 519 {
 520 # ifdef DEBUG_libfirm
 521   int i;
 522     for (i = 0; i < get_irp_n_irgs(); i++) {
 523       irg_vrfy (get_irp_irg(i));
 524     }
 525     tr_vrfy ();
 526 # endif /* defined DEBUG_libfirm */
 527
 528   if (_live_classes) {
 529     eset_destroy (_live_classes);
 530     _live_classes = NULL;
 531   }
 532
 533   if (_live_graphs) {
 534     eset_destroy (_live_graphs);
 535     _live_graphs = NULL;
 536   }
 537 }
 538
 539 /* Say whether this class might be instantiated at any point in the program: */
 540 int  rta_is_alive_class  (ir_type   *clazz)
 541 {
 542   return (eset_contains (_live_classes, clazz));
 543 }
 544
 545 /* Say whether this graph might be run at any time in the program: */
 546 int  rta_is_alive_graph (ir_graph *graph)
 547 {
 548   return eset_contains (_live_graphs, graph);
 549 }
 550
 551 /* dump our opinion */
 552 void rta_report (void)
 553 {
 554   int i;
 555
 556   for (i = 0; i < get_irp_n_types(); ++i) {
 557     ir_type *tp = get_irp_type(i);
 558     if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 559       ir_fprintf(stdout, "RTA: considered allocated: %+F\n", tp);
 560     }
 561   }
 562
 563   for (i = 0; i < get_irp_n_irgs(); i++) {
 564     if (rta_is_alive_graph (get_irp_irg(i))) {
 565       ir_fprintf(stdout, "RTA: considered called: graph of %+F\n", get_irp_irg(i));
 566     }
 567   }
 568 }