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 if (get_SymConst_kind(ptr) == symconst_addr_name) {
 161                                 /* Entities of kind addr_name may not be allocated in this compilation unit.
 162                                 If so, the frontend built faulty Firm.  So just ignore. */
 163                                 /* if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch"))
 164                                 assert(ent && "couldn't determine entity of call to SymConst of kind addr_name."); */
 165                         } else {
 166                                 /* other symconst. */
 167                                 panic("This SymConst can not be an address for a method call.");
 168                         }
 169
 170                         /* STRANGE */
 171                 } else {
 172                         panic("Unexpected address expression: can not analyse, therefore can not do correct rta!");
 173                 }
 174         } else if (iro_Alloc == op) { /* ALLOC */
 175                 ir_type *type = get_Alloc_type(node);
 176
 177                 *change |= add_class(type);
 178         }
 179 }
 180
 181 /**
 182    Traverse the given graph to collect method accesses and
 183    object allocations.
 184 */
 185 static int rta_fill_graph(ir_graph* graph)
 186 {
 187         int change = FALSE;
 188         irg_walk_graph(graph, rta_act, NULL, &change);
 189         return change;
 190 }
 191
 192 /**
 193  * Traverse all graphs to collect method accesses and object allocations.
 194  */
 195 static int rta_fill_incremental(void)
 196 {
 197         int i;
 198         int n_runs = 0;
 199         int rerun  = TRUE;
 200 #ifdef INTERPROCEDURAL_VIEW
 201         int old_ip_view = get_interprocedural_view();
 202
 203         set_interprocedural_view(0);     /* save this for later */
 204 #endif
 205
 206         /* init_tables has added main_irg to _live_graphs */
 207
 208         /* Need to take care of graphs that are externally
 209            visible or sticky. Pretend that they are called: */
 210         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 211                 ir_graph *graph = get_irp_irg(i);
 212                 ir_entity *ent = get_irg_entity(graph);
 213                 ir_linkage linkage = get_entity_linkage(ent);
 214
 215                 if (entity_is_externally_visible(ent)
 216                                 || (linkage & IR_LINKAGE_HIDDEN_USER)) {
 217                         eset_insert(_live_graphs, graph);
 218                 }
 219         }
 220
 221         while (rerun) {
 222                 ir_graph *graph;
 223
 224                 /* start off new */
 225                 eset *live_graphs = _live_graphs;
 226                 _live_graphs = eset_create();
 227
 228                 DB((dbg, LEVEL_2, "RTA: RUN %i\n", n_runs));
 229
 230                 /* collect what we have found previously */
 231                 eset_insert_all(_live_graphs, live_graphs);
 232
 233                 rerun = FALSE;
 234                 for (graph = eset_first(live_graphs);
 235                      graph != NULL;
 236                      graph = eset_next(live_graphs)) {
 237                         DB((dbg, LEVEL_2, "RTA: RUN %i: considering graph of %+F\n", n_runs, graph));
 238                         rerun |= rta_fill_graph(graph);
 239                 }
 240                 eset_destroy(live_graphs);
 241                 ++n_runs;
 242         }
 243
 244 #ifdef INTERPROCEDURAL_VIEW
 245         set_interprocedural_view(old_ip_view); /* cover up our traces */
 246 #endif
 247
 248         return n_runs;
 249 }
 250
 251 #ifdef DEBUG_libfirm
 252 /**
 253  * Count the number of graphs that we have found to be live.
 254  */
 255 static int stats(void)
 256 {
 257         int i;
 258         int n_live_graphs = 0;
 259
 260         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 261                 ir_graph *graph = get_irp_irg(i);
 262
 263                 if (rta_is_alive_graph(graph))
 264                         ++n_live_graphs;
 265         }
 266
 267         return n_live_graphs;
 268 }
 269 #endif
 270
 271 /* remove a graph, part I */
 272 /*
 273    We removed the first graph to implement the entity, so we're
 274    abstract now.  Pretend that it wasn't there at all, and every
 275    entity that used to inherit this entity's graph is now abstract.
 276 */
 277
 278 /**
 279    Initialize the static data structures.
 280 */
 281 static void init_tables(void)
 282 {
 283         ir_type  *tp;
 284         int      i, n;
 285         ir_graph *irg;
 286
 287         _live_classes = eset_create();
 288         _live_graphs  = eset_create();
 289
 290         irg = get_irp_main_irg();
 291         if (irg != NULL) {
 292                 /* add the main irg to the live set if one is specified */
 293                 eset_insert(_live_graphs, irg);
 294         }
 295
 296         /* Find static allocated classes */
 297         tp = get_glob_type();
 298         n  = get_class_n_members(tp);
 299         for (i = 0; i < n; ++i) {
 300                 ir_type *member_type = get_entity_type(get_class_member(tp, i));
 301                 if (is_Class_type(member_type))
 302                         eset_insert(_live_classes, member_type);
 303         }
 304
 305         tp = get_tls_type();
 306         n  = get_struct_n_members(tp);
 307         for (i = 0; i < n; ++i) {
 308                 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 309                 if (is_Class_type(member_type))
 310                         eset_insert(_live_classes, member_type);
 311         }
 312
 313         /** @FIXME: add constructors/destructors */
 314 }
 315
 316 /*
 317  * Initialize the RTA data structures, and perform RTA.
 318  */
 319 void rta_init(void)
 320 {
 321         int n_runs = 0;
 322         int rem_vpi = get_visit_pseudo_irgs();
 323         set_visit_pseudo_irgs(1);
 324
 325         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 326
 327 # ifdef DEBUG_libfirm
 328         {
 329                 int i;
 330                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 331                         irg_vrfy(get_irp_irg(i));
 332                 }
 333                 tr_vrfy();
 334         }
 335 # endif /* defined DEBUG_libfirm */
 336
 337         init_tables();
 338
 339         n_runs = rta_fill_incremental();
 340
 341         DB((dbg, LEVEL_1, "RTA: n_graphs      = %i\n", get_irp_n_irgs()));
 342         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
 343         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 344
 345 # ifdef DEBUG_libfirm
 346         {
 347                 int i;
 348
 349                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 350                         irg_vrfy(get_irp_irg(i));
 351                 }
 352                 tr_vrfy();
 353         }
 354 # endif /* defined DEBUG_libfirm */
 355
 356         set_visit_pseudo_irgs(rem_vpi);
 357 }
 358
 359 /**
 360  * walker for all types and entities
 361  *
 362  * Changes the peculiarity of entities that represents
 363  * dead graphs to peculiarity_description.
 364  */
 365 static void make_entity_to_description(type_or_ent tore, void *env)
 366 {
 367         (void) env;
 368         if (is_entity(tore.ent)) {
 369                 ir_entity *ent = tore.ent;
 370
 371                 if ((is_Method_type(get_entity_type(ent))) &&
 372                         !entity_is_externally_visible(ent)) {
 373                         ir_graph *irg = get_entity_irg(ent);
 374                         if (irg != NULL && ! eset_contains(_live_graphs, irg)) {
 375                                 set_entity_peculiarity(ent, peculiarity_description);
 376                                 set_entity_irg(ent, NULL);
 377                         }
 378                 }
 379         }
 380 }
 381
 382 /* Delete all graphs that we have found to be dead from the program
 383    If verbose == 1, print statistics, if > 1, chatter about every detail
 384 */
 385 void rta_delete_dead_graphs(void)
 386 {
 387         int      i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 388         ir_graph *irg, *next_irg, *dead_irgs;
 389
 390         int rem_vpi = get_visit_pseudo_irgs();
 391         set_visit_pseudo_irgs(1);
 392
 393         irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
 394
 395         n_dead_irgs = 0;
 396         dead_irgs = NULL;
 397         for (i = n_graphs - 1; i >= 0; --i) {
 398                 irg = get_irp_irg(i);
 399
 400                 if (! rta_is_alive_graph(irg)) {
 401                         set_irg_link(irg, dead_irgs);
 402                         dead_irgs = irg;
 403                         ++n_dead_irgs;
 404                 }
 405         }
 406
 407         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 408         type_walk(make_entity_to_description, NULL, NULL);
 409         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 410                 next_irg = get_irg_link(irg);
 411                 remove_irp_irg(irg);
 412         }
 413
 414         DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
 415
 416         irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
 417         set_visit_pseudo_irgs(rem_vpi);
 418 }
 419
 420 /* Clean up the RTA data structures.  Call this after calling rta_init */
 421 void rta_cleanup(void)
 422 {
 423 # ifdef DEBUG_libfirm
 424         int i;
 425         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 426                 irg_vrfy(get_irp_irg(i));
 427         }
 428         tr_vrfy();
 429 # endif /* defined DEBUG_libfirm */
 430
 431         if (_live_classes != NULL) {
 432                 eset_destroy(_live_classes);
 433                 _live_classes = NULL;
 434         }
 435
 436         if (_live_graphs != NULL) {
 437                 eset_destroy(_live_graphs);
 438                 _live_graphs = NULL;
 439         }
 440 }
 441
 442 /* Say whether this class might be instantiated at any point in the program: */
 443 int rta_is_alive_class(ir_type *clazz)
 444 {
 445         return eset_contains(_live_classes, clazz);
 446 }
 447
 448 /* Say whether this graph might be run at any time in the program: */
 449 int rta_is_alive_graph(ir_graph *graph)
 450 {
 451         return eset_contains(_live_graphs, graph);
 452 }
 453
 454 /* dump our opinion */
 455 void rta_report(void)
 456 {
 457         int i, n;
 458
 459         n = get_irp_n_types();
 460         for (i = 0; i < n; ++i) {
 461                 ir_type *tp = get_irp_type(i);
 462                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 463                         ir_printf("RTA: considered allocated: %+F\n", tp);
 464                 }
 465         }
 466
 467         n = get_irp_n_irgs();
 468         for (i = 0; i < n; i++) {
 469                 ir_graph *irg = get_irp_irg(i);
 470                 if (rta_is_alive_graph(irg)) {
 471                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 472                 }
 473         }
 474 }