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