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 Liekweg
  24  * @version  09.06.2002
  25  * @version  $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "rta.h"
  30
  31 #include <stdlib.h>
  32 #include <stdbool.h>
  33
  34 #include "irnode_t.h"
  35 #include "irprog_t.h"
  36 #include "irgraph_t.h"
  37
  38 #include "pset_new.h"
  39 #include "irgwalk.h"
  40 #include "irgmod.h"
  41 #include "irvrfy.h"
  42 #include "irprintf.h"
  43 #include "debug.h"
  44 #include "error.h"
  45
  46 /** The debug handle. */
  47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  48
  49 /* base data */
  50 static pset_new_t *_live_classes = NULL;
  51
  52 /* cache computed results */
  53 static pset_new_t *_live_graphs  = NULL;
  54
  55 /**
  56  * Add a graph to the set of live graphs.
  57  *
  58  * @param graph  the graph to add
  59  * @return non-zero if the graph was added, zero
  60  *         if it was already in the live set
  61  */
  62 static bool add_graph(ir_graph *graph)
  63 {
  64         if (!pset_new_contains(_live_graphs, graph)) {
  65                 DB((dbg, LEVEL_2, "RTA:        new graph of %+F\n", graph));
  66
  67                 pset_new_insert(_live_graphs, graph);
  68                 return true;
  69         }
  70
  71         return false;
  72 }
  73
  74 /**
  75  * Add a class to the set of live classes.
  76  *
  77  * @param clazz   the class to add
  78  * @return non-zero if the graph was added, zero
  79  *         if it was already in the live set
  80  */
  81 static bool add_class(ir_type *clazz)
  82 {
  83         if (!pset_new_contains(_live_classes, clazz)) {
  84                 DB((dbg, LEVEL_2, "RTA:        new class: %+F\n", clazz));
  85
  86                 pset_new_insert(_live_classes, clazz);
  87                 return true;
  88         }
  89
  90         return false;
  91 }
  92
  93 /** Given an entity, add all implementing graphs that belong to live classes
  94  *  to _live_graphs.
  95  *
  96  *  Iff additions occurred, return true, else false.
  97 */
  98 static bool add_implementing_graphs(ir_entity *method)
  99 {
 100         int i;
 101         int n_over = get_entity_n_overwrittenby(method);
 102         ir_graph *graph = get_entity_irg(method);
 103         bool change = false;
 104
 105         if (NULL == graph)
 106                 graph = get_entity_irg(method);
 107
 108         DB((dbg, LEVEL_2, "RTA:        new call to %+F\n", method));
 109
 110         if (rta_is_alive_class(get_entity_owner(method))) {
 111                 if (NULL != graph)
 112                         change = add_graph(graph);
 113         }
 114
 115         for (i = 0; i < n_over; ++i) {
 116                 ir_entity *over = get_entity_overwrittenby(method, i);
 117                 change |= add_implementing_graphs(over);
 118         }
 119
 120         return change;
 121 }
 122
 123 /**
 124  * Walker: Enter all method accesses and all class allocations into
 125  * our tables.
 126  *
 127  * Set *(int*)env to true iff (possibly) new graphs have been found.
 128  */
 129 static void rta_act(ir_node *node, void *env)
 130 {
 131         bool *change = (bool*)env;
 132         ir_opcode op = get_irn_opcode(node);
 133
 134         if (iro_Call == op) {         /* CALL */
 135                 ir_entity *ent = NULL;
 136
 137                 ir_node *ptr = get_Call_ptr(node);
 138
 139                 /* CALL SEL */
 140                 if (iro_Sel == get_irn_opcode(ptr)) {
 141                         ent = get_Sel_entity(ptr);
 142                         *change |= add_implementing_graphs(ent);
 143
 144                         /* CALL SYMCONST */
 145                 } else if (iro_SymConst == get_irn_opcode(ptr)) {
 146                         if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 147                                 ir_graph *graph;
 148
 149                                 ent = get_SymConst_entity(ptr);
 150                                 graph = get_entity_irg(ent);
 151                                 if (graph) {
 152                                         *change |= add_graph(graph);
 153                                 } else {
 154                                         /* it's an external allocated thing. */
 155                                 }
 156                         } else {
 157                                 /* other symconst. */
 158                                 panic("This SymConst can not be an address for a method call.");
 159                         }
 160
 161                         /* STRANGE */
 162                 } else {
 163                         panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
 164                 }
 165         } else if (iro_Alloc == op) { /* ALLOC */
 166                 ir_type *type = get_Alloc_type(node);
 167
 168                 *change |= add_class(type);
 169         }
 170 }
 171
 172 /**
 173    Traverse the given graph to collect method accesses and
 174    object allocations.
 175 */
 176 static bool rta_fill_graph(ir_graph* graph)
 177 {
 178         bool change = false;
 179         irg_walk_graph(graph, rta_act, NULL, &change);
 180         return change;
 181 }
 182
 183 /**
 184  * Traverse all graphs to collect method accesses and object allocations.
 185  */
 186 static int rta_fill_incremental(void)
 187 {
 188         int  i;
 189         int  n_runs = 0;
 190         bool rerun  = true;
 191 #ifdef INTERPROCEDURAL_VIEW
 192         int  old_ip_view = get_interprocedural_view();
 193
 194         set_interprocedural_view(0);     /* save this for later */
 195 #endif
 196
 197         /* init_tables has added main_irg to _live_graphs */
 198
 199         /* Need to take care of graphs that are externally
 200            visible or sticky. Pretend that they are called: */
 201         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 202                 ir_graph *graph = get_irp_irg(i);
 203                 ir_entity *ent = get_irg_entity(graph);
 204                 ir_linkage linkage = get_entity_linkage(ent);
 205
 206                 if (entity_is_externally_visible(ent)
 207                                 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
 208                         pset_new_insert(_live_graphs, graph);
 209                 }
 210         }
 211
 212         while (rerun) {
 213                 ir_graph *graph;
 214                 pset_new_iterator_t iter;
 215
 216                 /* start off new */
 217                 pset_new_t *live_graphs = _live_graphs;
 218                 _live_graphs = XMALLOC(pset_new_t);
 219                 pset_new_init(_live_graphs);
 220
 221                 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
 222
 223                 /* collect what we have found previously */
 224                 foreach_pset_new(live_graphs, graph, iter) {
 225                         pset_new_insert(_live_graphs, graph);
 226                 }
 227
 228                 rerun = false;
 229                 foreach_pset_new(live_graphs, graph, iter) {
 230                         DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
 231                         rerun |= rta_fill_graph(graph);
 232                 }
 233                 pset_new_destroy(live_graphs);
 234                 free(live_graphs);
 235                 ++n_runs;
 236         }
 237
 238 #ifdef INTERPROCEDURAL_VIEW
 239         set_interprocedural_view(old_ip_view); /* cover up our traces */
 240 #endif
 241
 242         return n_runs;
 243 }
 244
 245 #ifdef DEBUG_libfirm
 246 /**
 247  * Count the number of graphs that we have found to be live.
 248  */
 249 static int stats(void)
 250 {
 251         int i;
 252         int n_live_graphs = 0;
 253
 254         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 255                 ir_graph *graph = get_irp_irg(i);
 256
 257                 if (rta_is_alive_graph(graph))
 258                         ++n_live_graphs;
 259         }
 260
 261         return n_live_graphs;
 262 }
 263 #endif
 264
 265 /* remove a graph, part I */
 266 /*
 267    We removed the first graph to implement the entity, so we're
 268    abstract now.  Pretend that it wasn't there at all, and every
 269    entity that used to inherit this entity's graph is now abstract.
 270 */
 271
 272 /**
 273    Initialize the static data structures.
 274 */
 275 static void init_tables(void)
 276 {
 277         ir_type  *tp;
 278         int      i, n;
 279         ir_graph *irg;
 280
 281         _live_classes = XMALLOC(pset_new_t);
 282         pset_new_init(_live_classes);
 283         _live_graphs  = XMALLOC(pset_new_t);
 284         pset_new_init(_live_graphs);
 285
 286         irg = get_irp_main_irg();
 287         if (irg != NULL) {
 288                 /* add the main irg to the live set if one is specified */
 289                 pset_new_insert(_live_graphs, irg);
 290         }
 291
 292         /* Find static allocated classes */
 293         tp = get_glob_type();
 294         n  = get_class_n_members(tp);
 295         for (i = 0; i < n; ++i) {
 296                 ir_type *member_type = get_entity_type(get_class_member(tp, i));
 297                 if (is_Class_type(member_type))
 298                         pset_new_insert(_live_classes, member_type);
 299         }
 300
 301         tp = get_tls_type();
 302         n  = get_struct_n_members(tp);
 303         for (i = 0; i < n; ++i) {
 304                 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 305                 if (is_Class_type(member_type))
 306                         pset_new_insert(_live_classes, member_type);
 307         }
 308
 309         /** @FIXME: add constructors/destructors */
 310 }
 311
 312 /*
 313  * Initialize the RTA data structures, and perform RTA.
 314  */
 315 void rta_init(void)
 316 {
 317         int n_runs = 0;
 318
 319         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 320
 321 # ifdef DEBUG_libfirm
 322         {
 323                 int i;
 324                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 325                         irg_vrfy(get_irp_irg(i));
 326                 }
 327                 tr_vrfy();
 328         }
 329 # endif /* defined DEBUG_libfirm */
 330
 331         init_tables();
 332
 333         n_runs = rta_fill_incremental();
 334
 335         DB((dbg, LEVEL_1, "RTA: n_graphs      = %i\n", get_irp_n_irgs()));
 336         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
 337         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 338
 339 # ifdef DEBUG_libfirm
 340         {
 341                 int i;
 342
 343                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 344                         irg_vrfy(get_irp_irg(i));
 345                 }
 346                 tr_vrfy();
 347         }
 348 # endif /* defined DEBUG_libfirm */
 349 }
 350
 351 /**
 352  * walker for all types and entities
 353  *
 354  * Changes the peculiarity of entities that represents
 355  * dead graphs to peculiarity_description.
 356  */
 357 static void make_entity_to_description(type_or_ent tore, void *env)
 358 {
 359         (void) env;
 360         if (is_entity(tore.ent)) {
 361                 ir_entity *ent = tore.ent;
 362
 363                 if ((is_Method_type(get_entity_type(ent))) &&
 364                         !entity_is_externally_visible(ent)) {
 365                         ir_graph *irg = get_entity_irg(ent);
 366                         if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
 367                                 set_entity_peculiarity(ent, peculiarity_description);
 368                                 set_entity_irg(ent, NULL);
 369                         }
 370                 }
 371         }
 372 }
 373
 374 /* Delete all graphs that we have found to be dead from the program
 375    If verbose == 1, print statistics, if > 1, chatter about every detail
 376 */
 377 void rta_delete_dead_graphs(void)
 378 {
 379         int      i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 380         ir_graph *irg, *next_irg, *dead_irgs;
 381
 382         irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
 383
 384         n_dead_irgs = 0;
 385         dead_irgs = NULL;
 386         for (i = n_graphs - 1; i >= 0; --i) {
 387                 irg = get_irp_irg(i);
 388
 389                 if (! rta_is_alive_graph(irg)) {
 390                         set_irg_link(irg, dead_irgs);
 391                         dead_irgs = irg;
 392                         ++n_dead_irgs;
 393                 }
 394         }
 395
 396         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 397         type_walk(make_entity_to_description, NULL, NULL);
 398         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 399                 next_irg = get_irg_link(irg);
 400                 remove_irp_irg(irg);
 401         }
 402
 403         DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
 404
 405         irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
 406 }
 407
 408 /* Clean up the RTA data structures.  Call this after calling rta_init */
 409 void rta_cleanup(void)
 410 {
 411 # ifdef DEBUG_libfirm
 412         int i;
 413         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 414                 irg_vrfy(get_irp_irg(i));
 415         }
 416         tr_vrfy();
 417 # endif /* defined DEBUG_libfirm */
 418
 419         if (_live_classes != NULL) {
 420                 pset_new_destroy(_live_classes);
 421                 free(_live_classes);
 422                 _live_classes = NULL;
 423         }
 424
 425         if (_live_graphs != NULL) {
 426                 pset_new_destroy(_live_graphs);
 427                 free(_live_graphs);
 428                 _live_graphs = NULL;
 429         }
 430 }
 431
 432 /* Say whether this class might be instantiated at any point in the program: */
 433 int rta_is_alive_class(ir_type *clazz)
 434 {
 435         return pset_new_contains(_live_classes, clazz);
 436 }
 437
 438 /* Say whether this graph might be run at any time in the program: */
 439 int rta_is_alive_graph(ir_graph *graph)
 440 {
 441         return pset_new_contains(_live_graphs, graph);
 442 }
 443
 444 /* dump our opinion */
 445 void rta_report(void)
 446 {
 447         int i, n;
 448
 449         n = get_irp_n_types();
 450         for (i = 0; i < n; ++i) {
 451                 ir_type *tp = get_irp_type(i);
 452                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 453                         ir_printf("RTA: considered allocated: %+F\n", tp);
 454                 }
 455         }
 456
 457         n = get_irp_n_irgs();
 458         for (i = 0; i < n; i++) {
 459                 ir_graph *irg = get_irp_irg(i);
 460                 if (rta_is_alive_graph(irg)) {
 461                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 462                 }
 463         }
 464 }