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 "irverify.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         unsigned 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
 192         /* init_tables has added main_irg to _live_graphs */
 193
 194         /* Need to take care of graphs that are externally
 195            visible or sticky. Pretend that they are called: */
 196         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 197                 ir_graph *graph = get_irp_irg(i);
 198                 ir_entity *ent = get_irg_entity(graph);
 199                 ir_linkage linkage = get_entity_linkage(ent);
 200
 201                 if (entity_is_externally_visible(ent)
 202                                 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
 203                         pset_new_insert(_live_graphs, graph);
 204                 }
 205         }
 206
 207         while (rerun) {
 208                 ir_graph *graph;
 209                 pset_new_iterator_t iter;
 210
 211                 /* start off new */
 212                 pset_new_t *live_graphs = _live_graphs;
 213                 _live_graphs = XMALLOC(pset_new_t);
 214                 pset_new_init(_live_graphs);
 215
 216                 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
 217
 218                 /* collect what we have found previously */
 219                 foreach_pset_new(live_graphs, ir_graph*, graph, iter) {
 220                         pset_new_insert(_live_graphs, graph);
 221                 }
 222
 223                 rerun = false;
 224                 foreach_pset_new(live_graphs, ir_graph*, graph, iter) {
 225                         DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
 226                         rerun |= rta_fill_graph(graph);
 227                 }
 228                 pset_new_destroy(live_graphs);
 229                 free(live_graphs);
 230                 ++n_runs;
 231         }
 232
 233         return n_runs;
 234 }
 235
 236 #ifdef DEBUG_libfirm
 237 /**
 238  * Count the number of graphs that we have found to be live.
 239  */
 240 static int stats(void)
 241 {
 242         int i;
 243         int n_live_graphs = 0;
 244
 245         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 246                 ir_graph *graph = get_irp_irg(i);
 247
 248                 if (rta_is_alive_graph(graph))
 249                         ++n_live_graphs;
 250         }
 251
 252         return n_live_graphs;
 253 }
 254 #endif
 255
 256 /* remove a graph, part I */
 257 /*
 258    We removed the first graph to implement the entity, so we're
 259    abstract now.  Pretend that it wasn't there at all, and every
 260    entity that used to inherit this entity's graph is now abstract.
 261 */
 262
 263 /**
 264    Initialize the static data structures.
 265 */
 266 static void init_tables(void)
 267 {
 268         ir_type  *tp;
 269         int      i, n;
 270         ir_graph *irg;
 271
 272         _live_classes = XMALLOC(pset_new_t);
 273         pset_new_init(_live_classes);
 274         _live_graphs  = XMALLOC(pset_new_t);
 275         pset_new_init(_live_graphs);
 276
 277         irg = get_irp_main_irg();
 278         if (irg != NULL) {
 279                 /* add the main irg to the live set if one is specified */
 280                 pset_new_insert(_live_graphs, irg);
 281         }
 282
 283         /* Find static allocated classes */
 284         tp = get_glob_type();
 285         n  = get_class_n_members(tp);
 286         for (i = 0; i < n; ++i) {
 287                 ir_type *member_type = get_entity_type(get_class_member(tp, i));
 288                 if (is_Class_type(member_type))
 289                         pset_new_insert(_live_classes, member_type);
 290         }
 291
 292         tp = get_tls_type();
 293         n  = get_struct_n_members(tp);
 294         for (i = 0; i < n; ++i) {
 295                 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 296                 if (is_Class_type(member_type))
 297                         pset_new_insert(_live_classes, member_type);
 298         }
 299
 300         /** @FIXME: add constructors/destructors */
 301 }
 302
 303 /*
 304  * Initialize the RTA data structures, and perform RTA.
 305  */
 306 void rta_init(void)
 307 {
 308         int n_runs = 0;
 309
 310         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 311
 312 # ifdef DEBUG_libfirm
 313         {
 314                 int i;
 315                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 316                         irg_verify(get_irp_irg(i), 0);
 317                 }
 318                 tr_verify();
 319         }
 320 # endif /* defined DEBUG_libfirm */
 321
 322         init_tables();
 323
 324         n_runs = rta_fill_incremental();
 325
 326         DB((dbg, LEVEL_1, "RTA: n_graphs      = %i\n", get_irp_n_irgs()));
 327         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
 328         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 329
 330 # ifdef DEBUG_libfirm
 331         {
 332                 int i;
 333
 334                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 335                         irg_verify(get_irp_irg(i), 0);
 336                 }
 337                 tr_verify();
 338         }
 339 # endif /* defined DEBUG_libfirm */
 340 }
 341
 342 /**
 343  * walker for all types and entities
 344  *
 345  * Changes the peculiarity of entities that represents
 346  * dead graphs to peculiarity_description.
 347  */
 348 static void make_entity_to_description(type_or_ent tore, void *env)
 349 {
 350         (void) env;
 351         if (is_entity(tore.ent)) {
 352                 ir_entity *ent = tore.ent;
 353
 354                 if ((is_Method_type(get_entity_type(ent))) &&
 355                         !entity_is_externally_visible(ent)) {
 356                         ir_graph *irg = get_entity_irg(ent);
 357                         if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
 358                                 set_entity_peculiarity(ent, peculiarity_description);
 359                                 set_entity_irg(ent, NULL);
 360                         }
 361                 }
 362         }
 363 }
 364
 365 /* Delete all graphs that we have found to be dead from the program
 366    If verbose == 1, print statistics, if > 1, chatter about every detail
 367 */
 368 void rta_delete_dead_graphs(void)
 369 {
 370         int      i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 371         ir_graph *irg, *next_irg, *dead_irgs;
 372
 373         irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
 374
 375         n_dead_irgs = 0;
 376         dead_irgs = NULL;
 377         for (i = n_graphs - 1; i >= 0; --i) {
 378                 irg = get_irp_irg(i);
 379
 380                 if (! rta_is_alive_graph(irg)) {
 381                         set_irg_link(irg, dead_irgs);
 382                         dead_irgs = irg;
 383                         ++n_dead_irgs;
 384                 }
 385         }
 386
 387         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 388         type_walk(make_entity_to_description, NULL, NULL);
 389         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 390                 next_irg = (ir_graph*) get_irg_link(irg);
 391                 remove_irp_irg(irg);
 392         }
 393
 394         DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
 395
 396         irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
 397 }
 398
 399 /* Clean up the RTA data structures.  Call this after calling rta_init */
 400 void rta_cleanup(void)
 401 {
 402 # ifdef DEBUG_libfirm
 403         int i;
 404         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 405                 irg_verify(get_irp_irg(i), 0);
 406         }
 407         tr_verify();
 408 # endif /* defined DEBUG_libfirm */
 409
 410         if (_live_classes != NULL) {
 411                 pset_new_destroy(_live_classes);
 412                 free(_live_classes);
 413                 _live_classes = NULL;
 414         }
 415
 416         if (_live_graphs != NULL) {
 417                 pset_new_destroy(_live_graphs);
 418                 free(_live_graphs);
 419                 _live_graphs = NULL;
 420         }
 421 }
 422
 423 /* Say whether this class might be instantiated at any point in the program: */
 424 int rta_is_alive_class(ir_type *clazz)
 425 {
 426         return pset_new_contains(_live_classes, clazz);
 427 }
 428
 429 /* Say whether this graph might be run at any time in the program: */
 430 int rta_is_alive_graph(ir_graph *graph)
 431 {
 432         return pset_new_contains(_live_graphs, graph);
 433 }
 434
 435 /* dump our opinion */
 436 void rta_report(void)
 437 {
 438         int i, n;
 439
 440         n = get_irp_n_types();
 441         for (i = 0; i < n; ++i) {
 442                 ir_type *tp = get_irp_type(i);
 443                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 444                         ir_printf("RTA: considered allocated: %+F\n", tp);
 445                 }
 446         }
 447
 448         n = get_irp_n_irgs();
 449         for (i = 0; i < n; i++) {
 450                 ir_graph *irg = get_irp_irg(i);
 451                 if (rta_is_alive_graph(irg)) {
 452                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 453                 }
 454         }
 455 }