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