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         size_t i;
 101         size_t 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_graph     *irg;
 267         ir_segment_t segment;
 268
 269         _live_classes = XMALLOC(pset_new_t);
 270         pset_new_init(_live_classes);
 271         _live_graphs  = XMALLOC(pset_new_t);
 272         pset_new_init(_live_graphs);
 273
 274         irg = get_irp_main_irg();
 275         if (irg != NULL) {
 276                 /* add the main irg to the live set if one is specified */
 277                 pset_new_insert(_live_graphs, irg);
 278         }
 279
 280         /* Find static allocated classes in all segments */
 281         for (segment = IR_SEGMENT_FIRST; segment <= IR_SEGMENT_LAST; ++segment) {
 282                 ir_type *tp = get_segment_type(segment);
 283                 size_t  n   = get_compound_n_members(tp);
 284                 size_t  i;
 285
 286                 for (i = 0; i < n; ++i) {
 287                         ir_type *member_type = get_entity_type(get_compound_member(tp, i));
 288                         if (is_Class_type(member_type))
 289                                 pset_new_insert(_live_classes, member_type);
 290                 }
 291         }
 292 }
 293
 294 /*
 295  * Initialize the RTA data structures, and perform RTA.
 296  */
 297 void rta_init(void)
 298 {
 299         int n_runs = 0;
 300
 301         FIRM_DBG_REGISTER(dbg, "firm.ana.rta");
 302
 303 # ifdef DEBUG_libfirm
 304         {
 305                 size_t i;
 306                 for (i = get_irp_n_irgs(); i > 0;) {
 307                         irg_verify(get_irp_irg(--i), 0);
 308                 }
 309                 tr_verify();
 310         }
 311 # endif /* defined DEBUG_libfirm */
 312
 313         init_tables();
 314
 315         n_runs = rta_fill_incremental();
 316
 317         DB((dbg, LEVEL_1, "RTA: n_graphs      = %zu\n", get_irp_n_irgs()));
 318         DB((dbg, LEVEL_1, "RTA: n_live_graphs = %zu\n", stats()));
 319         DB((dbg, LEVEL_1, "RTA: n_runs        = %i\n", n_runs));
 320
 321 # ifdef DEBUG_libfirm
 322         {
 323                 size_t i;
 324
 325                 for (i = get_irp_n_irgs(); i > 0;) {
 326                         irg_verify(get_irp_irg(--i), 0);
 327                 }
 328                 tr_verify();
 329         }
 330 # endif /* defined DEBUG_libfirm */
 331 }
 332
 333 /**
 334  * walker for all types and entities
 335  *
 336  * Changes the peculiarity of entities that represents
 337  * dead graphs to peculiarity_description.
 338  */
 339 static void make_entity_to_description(type_or_ent tore, void *env)
 340 {
 341         (void) env;
 342         if (is_entity(tore.ent)) {
 343                 ir_entity *ent = tore.ent;
 344
 345                 if ((is_Method_type(get_entity_type(ent))) &&
 346                         !entity_is_externally_visible(ent)) {
 347                         ir_graph *irg = get_entity_irg(ent);
 348                         if (irg != NULL && ! pset_new_contains(_live_graphs, irg)) {
 349                                 set_entity_peculiarity(ent, peculiarity_description);
 350                                 set_entity_irg(ent, NULL);
 351                         }
 352                 }
 353         }
 354 }
 355
 356 /* Delete all graphs that we have found to be dead from the program
 357    If verbose == 1, print statistics, if > 1, chatter about every detail
 358 */
 359 void rta_delete_dead_graphs(void)
 360 {
 361         size_t   i, n_dead_irgs, n_graphs = get_irp_n_irgs();
 362         ir_graph *irg, *next_irg, *dead_irgs;
 363
 364         irp_reserve_resources(irp, IRP_RESOURCE_IRG_LINK);
 365
 366         n_dead_irgs = 0;
 367         dead_irgs = NULL;
 368         for (i = n_graphs; i > 0;) {
 369                 irg = get_irp_irg(--i);
 370
 371                 if (! rta_is_alive_graph(irg)) {
 372                         set_irg_link(irg, dead_irgs);
 373                         dead_irgs = irg;
 374                         ++n_dead_irgs;
 375                 }
 376         }
 377
 378         /* Hmm, probably we need to run this only if dead_irgs is non-NULL */
 379         type_walk(make_entity_to_description, NULL, NULL);
 380         for (irg = dead_irgs; irg != NULL; irg = next_irg) {
 381                 next_irg = (ir_graph*) get_irg_link(irg);
 382                 remove_irp_irg(irg);
 383         }
 384
 385         DB((dbg, LEVEL_1, "RTA: dead methods = %zu\n", n_dead_irgs));
 386
 387         irp_free_resources(irp, IRP_RESOURCE_IRG_LINK);
 388 }
 389
 390 /* Clean up the RTA data structures.  Call this after calling rta_init */
 391 void rta_cleanup(void)
 392 {
 393 # ifdef DEBUG_libfirm
 394         size_t i;
 395         for (i = get_irp_n_irgs(); i > 0;) {
 396                 irg_verify(get_irp_irg(--i), 0);
 397         }
 398         tr_verify();
 399 # endif /* defined DEBUG_libfirm */
 400
 401         if (_live_classes != NULL) {
 402                 pset_new_destroy(_live_classes);
 403                 free(_live_classes);
 404                 _live_classes = NULL;
 405         }
 406
 407         if (_live_graphs != NULL) {
 408                 pset_new_destroy(_live_graphs);
 409                 free(_live_graphs);
 410                 _live_graphs = NULL;
 411         }
 412 }
 413
 414 /* Say whether this class might be instantiated at any point in the program: */
 415 int rta_is_alive_class(ir_type *clazz)
 416 {
 417         return pset_new_contains(_live_classes, clazz);
 418 }
 419
 420 /* Say whether this graph might be run at any time in the program: */
 421 int rta_is_alive_graph(ir_graph *graph)
 422 {
 423         return pset_new_contains(_live_graphs, graph);
 424 }
 425
 426 /* dump our opinion */
 427 void rta_report(void)
 428 {
 429         size_t i, n;
 430
 431         n = get_irp_n_types();
 432         for (i = 0; i < n; ++i) {
 433                 ir_type *tp = get_irp_type(i);
 434                 if (is_Class_type(tp) && rta_is_alive_class(tp)) {
 435                         ir_printf("RTA: considered allocated: %+F\n", tp);
 436                 }
 437         }
 438
 439         n = get_irp_n_irgs();
 440         for (i = 0; i < n; i++) {
 441                 ir_graph *irg = get_irp_irg(i);
 442                 if (rta_is_alive_graph(irg)) {
 443                         ir_printf("RTA: considered called: graph of %+F\n", irg);
 444                 }
 445         }
 446 }