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         int rem_vpi = get_visit_pseudo_irgs();
 319         set_visit_pseudo_irgs(1);
 320
 321         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 322
 323 # ifdef DEBUG_libfirm
 324         {
 325                 int i;
 326                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 327                         irg_vrfy(get_irp_irg(i));
 328                 }
 329                 tr_vrfy();
 330         }
 331 # endif /* defined DEBUG_libfirm */
 332
 333         init_tables();
 334
 335         n_runs = rta_fill_incremental();
 336
 337         DB((dbg, LEVEL_1, "RTA: n_graphs      = %i\n", get_irp_n_irgs()));
 338         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
 339         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 340
 341 # ifdef DEBUG_libfirm
 342         {
 343                 int i;
 344
 345                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 346                         irg_vrfy(get_irp_irg(i));
 347                 }
 348                 tr_vrfy();
 349         }
 350 # endif /* defined DEBUG_libfirm */
 351
 352         set_visit_pseudo_irgs(rem_vpi);
 353 }
 354
 355 /**
 356  * walker for all types and entities
 357  *
 358  * Changes the peculiarity of entities that represents
 359  * dead graphs to peculiarity_description.
 360  */
 361 static void make_entity_to_description(type_or_ent tore, void *env)
 362 {
 363         (void) env;
 364         if (is_entity(tore.ent)) {
 365                 ir_entity *ent = tore.ent;
 366
 367                 if ((is_Method_type(get_entity_type(ent))) &&
 368                         !entity_is_externally_visible(ent)) {
 369                         ir_graph *irg = get_entity_irg(ent);
 370                         if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
 371                                 set_entity_peculiarity(ent, peculiarity_description);
 372                                 set_entity_irg(ent, NULL);
 373                         }
 374                 }
 375         }
 376 }
 377
 378 /* Delete all graphs that we have found to be dead from the program
 379    If verbose == 1, print statistics, if > 1, chatter about every detail
 380 */
 381 void rta_delete_dead_graphs(void)
 382 {
 383         int      i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 384         ir_graph *irg, *next_irg, *dead_irgs;
 385
 386         int rem_vpi = get_visit_pseudo_irgs();
 387         set_visit_pseudo_irgs(1);
 388
 389         irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
 390
 391         n_dead_irgs = 0;
 392         dead_irgs = NULL;
 393         for (i = n_graphs - 1; i >= 0; --i) {
 394                 irg = get_irp_irg(i);
 395
 396                 if (! rta_is_alive_graph(irg)) {
 397                         set_irg_link(irg, dead_irgs);
 398                         dead_irgs = irg;
 399                         ++n_dead_irgs;
 400                 }
 401         }
 402
 403         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 404         type_walk(make_entity_to_description, NULL, NULL);
 405         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 406                 next_irg = get_irg_link(irg);
 407                 remove_irp_irg(irg);
 408         }
 409
 410         DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
 411
 412         irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
 413         set_visit_pseudo_irgs(rem_vpi);
 414 }
 415
 416 /* Clean up the RTA data structures.  Call this after calling rta_init */
 417 void rta_cleanup(void)
 418 {
 419 # ifdef DEBUG_libfirm
 420         int i;
 421         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 422                 irg_vrfy(get_irp_irg(i));
 423         }
 424         tr_vrfy();
 425 # endif /* defined DEBUG_libfirm */
 426
 427         if (_live_classes != NULL) {
 428                 pset_new_destroy(_live_classes);
 429                 free(_live_classes);
 430                 _live_classes = NULL;
 431         }
 432
 433         if (_live_graphs != NULL) {
 434                 pset_new_destroy(_live_graphs);
 435                 free(_live_graphs);
 436                 _live_graphs = NULL;
 437         }
 438 }
 439
 440 /* Say whether this class might be instantiated at any point in the program: */
 441 int rta_is_alive_class(ir_type *clazz)
 442 {
 443         return pset_new_contains(_live_classes, clazz);
 444 }
 445
 446 /* Say whether this graph might be run at any time in the program: */
 447 int rta_is_alive_graph(ir_graph *graph)
 448 {
 449         return pset_new_contains(_live_graphs, graph);
 450 }
 451
 452 /* dump our opinion */
 453 void rta_report(void)
 454 {
 455         int i, n;
 456
 457         n = get_irp_n_types();
 458         for (i = 0; i < n; ++i) {
 459                 ir_type *tp = get_irp_type(i);
 460                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 461                         ir_printf("RTA: considered allocated: %+F\n", tp);
 462                 }
 463         }
 464
 465         n = get_irp_n_irgs();
 466         for (i = 0; i < n; i++) {
 467                 ir_graph *irg = get_irp_irg(i);
 468                 if (rta_is_alive_graph(irg)) {
 469                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 470                 }
 471         }
 472 }