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 #ifdef DEBUG_libfirm
 264 /**
 265  * Count the number of graphs that we have found to be live.
 266  */
 267 static int stats(void)
 268 {
 269         int i;
 270         int n_live_graphs = 0;
 271
 272         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 273                 ir_graph *graph = get_irp_irg(i);
 274
 275                 if (rta_is_alive_graph(graph))
 276                         ++n_live_graphs;
 277         }
 278
 279         return n_live_graphs;
 280 }
 281 #endif
 282
 283 /* remove a graph, part I */
 284 /*
 285    We removed the first graph to implement the entity, so we're
 286    abstract now.  Pretend that it wasn't there at all, and every
 287    entity that used to inherit this entity's graph is now abstract.
 288 */
 289
 290 /**
 291    Initialize the static data structures.
 292 */
 293 static void init_tables(void)
 294 {
 295         ir_type  *tp;
 296         int      i, n;
 297         ir_graph *irg;
 298
 299         _live_classes = eset_create();
 300         _live_graphs  = eset_create();
 301
 302         irg = get_irp_main_irg();
 303         if (irg != NULL) {
 304                 /* add the main irg to the live set if one is specified */
 305                 eset_insert(_live_graphs, irg);
 306         }
 307
 308         /* Find static allocated classes */
 309         tp = get_glob_type();
 310         n  = get_class_n_members(tp);
 311         for (i = 0; i < n; ++i) {
 312                 ir_type *member_type = get_entity_type(get_class_member(tp, i));
 313                 if (is_Class_type(member_type))
 314                         eset_insert(_live_classes, member_type);
 315         }
 316
 317         tp = get_tls_type();
 318         n  = get_struct_n_members(tp);
 319         for (i = 0; i < n; ++i) {
 320                 ir_type *member_type = get_entity_type(get_struct_member(tp, i));
 321                 if (is_Class_type(member_type))
 322                         eset_insert(_live_classes, member_type);
 323         }
 324
 325         /** @FIXME: add constructors/destructors */
 326 }
 327
 328 /*
 329  * Initialize the RTA data structures, and perform RTA.
 330  */
 331 void rta_init(void)
 332 {
 333         int n_runs = 0;
 334         int rem_vpi = get_visit_pseudo_irgs();
 335         set_visit_pseudo_irgs(1);
 336
 337         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 338
 339 # ifdef DEBUG_libfirm
 340         {
 341                 int i;
 342                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 343                         irg_vrfy(get_irp_irg(i));
 344                 }
 345                 tr_vrfy();
 346         }
 347 # endif /* defined DEBUG_libfirm */
 348
 349         init_tables();
 350
 351         n_runs = rta_fill_incremental();
 352
 353         DB((dbg, LEVEL_1, "RTA: n_graphs      = %i\n", get_irp_n_irgs()));
 354         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %i\n", stats()));
 355         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 356
 357 # ifdef DEBUG_libfirm
 358         {
 359                 int i;
 360
 361                 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 362                         irg_vrfy(get_irp_irg(i));
 363                 }
 364                 tr_vrfy();
 365         }
 366 # endif /* defined DEBUG_libfirm */
 367
 368         set_visit_pseudo_irgs(rem_vpi);
 369 }
 370
 371 /**
 372  * walker for all types and entities
 373  *
 374  * Changes the peculiarity of entities that represents
 375  * dead graphs to peculiarity_description.
 376  */
 377 static void make_entity_to_description(type_or_ent tore, void *env) {
 378         (void) env;
 379         if (is_entity(tore.ent)) {
 380                 ir_entity *ent = tore.ent;
 381
 382                 if ((is_Method_type(get_entity_type(ent)))                        &&
 383                     (get_entity_peculiarity(ent) != peculiarity_description)      &&
 384                     (get_entity_visibility(ent)  != visibility_external_allocated)   ) {
 385                         ir_graph *irg = get_entity_irg(get_SymConst_entity(get_atomic_ent_value(ent)));
 386                         if (! eset_contains(_live_graphs, irg)) {
 387                                 set_entity_peculiarity(ent, peculiarity_description);
 388                                 set_entity_irg(ent, NULL);
 389                         }
 390                 }
 391         }
 392 }
 393
 394 /* Delete all graphs that we have found to be dead from the program
 395    If verbose == 1, print statistics, if > 1, chatter about every detail
 396 */
 397 void rta_delete_dead_graphs(void)
 398 {
 399         int      i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 400         ir_graph *irg, *next_irg, *dead_irgs;
 401
 402         int rem_vpi = get_visit_pseudo_irgs();
 403         set_visit_pseudo_irgs(1);
 404
 405         irp_reserve_resources(irp, IR_RESOURCE_IRG_LINK);
 406
 407         n_dead_irgs = 0;
 408         dead_irgs = NULL;
 409         for (i = n_graphs - 1; i >= 0; --i) {
 410                 irg = get_irp_irg(i);
 411
 412                 if (! rta_is_alive_graph(irg)) {
 413 #ifndef NDEBUG
 414                         ir_entity *ent = get_irg_entity(irg);
 415                         assert(visibility_external_visible != get_entity_visibility(ent));
 416 #endif
 417                         set_irg_link(irg, dead_irgs);
 418                         dead_irgs = irg;
 419                         ++n_dead_irgs;
 420                 }
 421         }
 422
 423         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 424         type_walk(make_entity_to_description, NULL, NULL);
 425         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 426                 next_irg = get_irg_link(irg);
 427                 remove_irp_irg(irg);
 428         }
 429
 430         DB((dbg, LEVEL_1, "RTA: dead methods = %i\n", n_dead_irgs));
 431
 432         irp_free_resources(irp, IR_RESOURCE_IRG_LINK);
 433         set_visit_pseudo_irgs(rem_vpi);
 434 }
 435
 436 /* Clean up the RTA data structures.  Call this after calling rta_init */
 437 void rta_cleanup(void)
 438 {
 439 # ifdef DEBUG_libfirm
 440         int i;
 441         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 442                 irg_vrfy(get_irp_irg(i));
 443         }
 444         tr_vrfy();
 445 # endif /* defined DEBUG_libfirm */
 446
 447         if (_live_classes != NULL) {
 448                 eset_destroy(_live_classes);
 449                 _live_classes = NULL;
 450         }
 451
 452         if (_live_graphs != NULL) {
 453                 eset_destroy(_live_graphs);
 454                 _live_graphs = NULL;
 455         }
 456 }
 457
 458 /* Say whether this class might be instantiated at any point in the program: */
 459 int rta_is_alive_class(ir_type *clazz)
 460 {
 461         return eset_contains(_live_classes, clazz);
 462 }
 463
 464 /* Say whether this graph might be run at any time in the program: */
 465 int rta_is_alive_graph(ir_graph *graph)
 466 {
 467         return eset_contains(_live_graphs, graph);
 468 }
 469
 470 /* dump our opinion */
 471 void rta_report(void)
 472 {
 473         int i, n;
 474
 475         n = get_irp_n_types();
 476         for (i = 0; i < n; ++i) {
 477                 ir_type *tp = get_irp_type(i);
 478                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 479                         ir_printf("RTA: considered allocated: %+F\n", tp);
 480                 }
 481         }
 482
 483         n = get_irp_n_irgs();
 484         for (i = 0; i < n; i++) {
 485                 ir_graph *irg = get_irp_irg(i);
 486                 if (rta_is_alive_graph(irg)) {
 487                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 488                 }
 489         }
 490 }