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