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