nsz Git - libfirm/blob - ir/ana/rta.c

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