nsz Git - libfirm/blob - ir/opt/funccall.c

   1 /*
   2  * Copyright (C) 1995-2007 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   Optimization of function calls.
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include <adt/raw_bitset.h>
  31
  32 #include "funccall_t.h"
  33
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "irgmod.h"
  37 #include "irgwalk.h"
  38 #include "irvrfy.h"
  39 #include "dbginfo_t.h"
  40 #include "irflag_t.h"
  41 #include "ircons.h"
  42 #include "irhooks.h"
  43 #include "debug.h"
  44
  45 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  46
  47 /**
  48  * The walker environment for rem_mem_from_const_fkt_calls
  49  */
  50 typedef struct _env_t {
  51         unsigned n_calls_SymConst;
  52         unsigned n_calls_Sel;
  53         ir_node  *const_call_list;       /**< The list of all const function calls that will be changed. */
  54         ir_node  *pure_call_list;        /**< The list of all pure function calls that will be changed. */
  55         ir_node  *proj_list;             /**< The list of all potential Proj nodes that must be fixed. */
  56 } env_t;
  57
  58 /** Ready IRG's are marked in the ready set. */
  59 static unsigned *ready_set;
  60
  61 /** IRG's that are in progress are marked here. */
  62 static unsigned *busy_set;
  63
  64 /**
  65  * We misuse the mtp_temporary flag as temporary here.
  66  * The is ok, as we cannot set or get it anyway.
  67  */
  68 #define mtp_temporary  mtp_property_inherited
  69
  70 /**
  71  * Collect all calls to const and pure functions
  72  * to lists. Collect all Proj(Call) nodes into a Proj list.
  73  */
  74 static void collect_calls(ir_node *node, void *env) {
  75         env_t *ctx = env;
  76         ir_node *call, *ptr;
  77         ir_entity *ent;
  78         unsigned mode;
  79
  80         if (is_Call(node)) {
  81                 call = node;
  82
  83                 /* set the link to NULL for all non-const/pure calls */
  84                 set_irn_link(call, NULL);
  85                 ptr = get_Call_ptr(call);
  86                 if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
  87                         ent = get_SymConst_entity(ptr);
  88
  89                         mode = get_entity_additional_properties(ent);
  90                         if ((mode & (mtp_property_const|mtp_property_pure)) == 0)
  91                                 return;
  92                         ++ctx->n_calls_SymConst;
  93                 } else if (get_opt_closed_world() &&
  94                            is_Sel(ptr) &&
  95                            get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
  96                         /* If all possible callees are const functions, we can remove the memory edge. */
  97                         int i, n_callees = get_Call_n_callees(call);
  98                         if (n_callees == 0) {
  99                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 100                                    when executed as there is no implementation to call.  So better not
 101                                    optimize. */
 102                                 return;
 103                         }
 104
 105                         /* note that const function are a subset of pure ones */
 106                         mode = mtp_property_const | mtp_property_pure;
 107                         for (i = 0; i < n_callees; ++i) {
 108                                 ent = get_Call_callee(call, i);
 109                                 if (ent == unknown_entity) {
 110                                         /* we don't know which entity is called here */
 111                                         return;
 112                                 }
 113                                 mode &= get_entity_additional_properties(ent);
 114                                 if (mode == 0)
 115                                         return;
 116                         }
 117                         ++ctx->n_calls_Sel;
 118                 } else
 119                         return;
 120
 121                 /* ok, if we get here we found a call to a const or a pure function */
 122                 if (mode & mtp_property_pure) {
 123                         set_irn_link(call, ctx->pure_call_list);
 124                         ctx->pure_call_list = call;
 125                 } else {
 126                         set_irn_link(call, ctx->const_call_list);
 127                         ctx->const_call_list = call;
 128                 }
 129         } else if (is_Proj(node)) {
 130                 /*
 131                  * Collect all memory and exception Proj's from
 132                  * calls.
 133                  */
 134                 call = get_Proj_pred(node);
 135                 if (! is_Call(call))
 136                         return;
 137
 138                 /* collect the Proj's in the Proj list */
 139                 switch (get_Proj_proj(node)) {
 140                 case pn_Call_M_regular:
 141                 case pn_Call_X_except:
 142                 case pn_Call_M_except:
 143                         set_irn_link(node, ctx->proj_list);
 144                         ctx->proj_list = node;
 145                         break;
 146                 default:
 147                         break;
 148                 }
 149         }
 150 }  /* collect_calls */
 151
 152 /**
 153  * Fix the list of collected Calls.
 154  *
 155  * @param irg        the graph that contained calls to pure functions
 156  * @param call_list  the list of all call sites of const functions
 157  * @param proj_list  the list of all memory/exception Proj's of this call sites
 158  */
 159 static void fix_const_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) {
 160         ir_node *call, *next, *mem, *proj;
 161         int exc_changed = 0;
 162         ir_graph *rem = current_ir_graph;
 163
 164         current_ir_graph = irg;
 165
 166         /* First step: fix all calls by removing it's memory input.
 167            It's original memory input is preserved in their link fields. */
 168         for (call = call_list; call; call = next) {
 169                 next = get_irn_link(call);
 170                 mem  = get_Call_mem(call);
 171
 172                 set_irn_link(call, mem);
 173                 set_Call_mem(call, get_irg_no_mem(irg));
 174
 175                 /*
 176                  * Sorrily we cannot simply set the node to 'float'.
 177                  * There is a reason for that:
 178                  *
 179                  * - The call might be inside a loop/if that is NOT entered
 180                  *   and calls a endless function. Setting the call to float
 181                  *   would allow to move it out from the loop/if causing this
 182                  *   function be called even if the loop/if is not entered ...
 183                  *
 184                  * This could be fixed using post-dominators for calls and Pin nodes
 185                  * but need some more analyzes to ensure that a call that potential
 186                  * never returns is not executed before some code that generates
 187                  * observable states...
 188                  */
 189
 190                 /* finally, this call can float
 191                 set_irn_pinned(call, op_pin_state_floats); */
 192                 hook_func_call(irg, call);
 193         }
 194
 195         /* Second step: fix all Proj's */
 196         for (proj = proj_list; proj; proj = next) {
 197                 next = get_irn_link(proj);
 198                 call = get_Proj_pred(proj);
 199                 mem  = get_irn_link(call);
 200
 201                 /* beware of calls in the pure call list */
 202                 if (! mem || get_irn_op(mem) == op_Call)
 203                         continue;
 204                 assert(get_irn_mode(mem) == mode_M);
 205
 206                 switch (get_Proj_proj(proj)) {
 207                 case pn_Call_M_regular: {
 208                         /* in dead code there might be cycles where proj == mem */
 209                         if (proj != mem)
 210                                 exchange(proj, mem);
 211                 } break;
 212                 case pn_Call_X_except:
 213                 case pn_Call_M_except:
 214                         exc_changed = 1;
 215                         exchange(proj, get_irg_bad(irg));
 216                         break;
 217                 default:
 218                         ;
 219                 }
 220         }
 221
 222         /* changes were done ... */
 223         set_irg_outs_inconsistent(irg);
 224         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 225
 226         if (exc_changed) {
 227                 /* ... including exception edges */
 228                 set_irg_doms_inconsistent(irg);
 229         }
 230         current_ir_graph = rem;
 231 }  /* fix_call_list */
 232
 233 /* marking */
 234 #define SET_IRG_READY(irg)      rbitset_set(ready_set, get_irg_idx(irg))
 235 #define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
 236 #define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
 237 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
 238 #define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
 239
 240 /* forward */
 241 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
 242
 243 /**
 244  * Calculate the bigger mode of two. Handle the temporary flag right.
 245  */
 246 static unsigned mode_max(unsigned a, unsigned b) {
 247         unsigned r, t = (a | b) & mtp_temporary;
 248         a &= ~mtp_temporary;
 249         b &= ~mtp_temporary;
 250
 251         if (a == mtp_no_property || b == mtp_no_property)
 252                 return mtp_no_property;
 253         r = a > b ? a : b;
 254         return r | t;
 255 }
 256
 257 /**
 258  * Follow the memory chain starting at node and determine
 259  * the mtp_property.
 260  *
 261  * @return mtp_property_const if only calls of const functions are detected
 262  *         mtp_property_pure if only Loads and const/pure
 263  *         calls detected
 264  *         mtp_no_property else
 265  */
 266 static unsigned _follow_mem(ir_node *node) {
 267         unsigned m, mode = mtp_property_const;
 268         ir_node  *ptr;
 269         int i;
 270
 271         for (;;) {
 272                 if (mode == mtp_no_property)
 273                         return mtp_no_property;
 274
 275                 if (irn_visited(node))
 276                         return mode;
 277
 278                 mark_irn_visited(node);
 279
 280                 switch (get_irn_opcode(node)) {
 281                 case iro_Proj:
 282                         node = get_Proj_pred(node);
 283                         break;
 284
 285                 case iro_NoMem:
 286                         /* finish here */
 287                         return mode;
 288
 289                 case iro_Phi:
 290                 case iro_Sync:
 291                         /* do a dfs search */
 292                         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 293                                 m    = _follow_mem(get_irn_n(node, i));
 294                                 mode = mode_max(mode, m);
 295                                 if (mode == mtp_no_property)
 296                                         return mtp_no_property;
 297                         }
 298                         return mode;
 299
 300                 case iro_Load:
 301                         /* Beware volatile Loads are NOT allowed in pure functions. */
 302                         if (get_Load_volatility(node) == volatility_is_volatile)
 303                                 return mtp_no_property;
 304                         mode = mode_max(mode, mtp_property_pure);
 305                         node = get_Load_mem(node);
 306                         break;
 307
 308                 case iro_Call:
 309                         /* A call is only tolerable if its either constant or pure. */
 310                         ptr = get_Call_ptr(node);
 311                         if (get_irn_op(ptr) == op_SymConst &&
 312                                 get_SymConst_kind(ptr) == symconst_addr_ent) {
 313                                 ir_entity *ent = get_SymConst_entity(ptr);
 314                                 ir_graph  *irg = get_entity_irg(ent);
 315
 316                                 if (irg == current_ir_graph) {
 317                                         /* A self-recursive call. The mode did not depend on this call. */
 318                                 } else if (irg == NULL) {
 319                                         m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
 320                                         mode = mode_max(mode, m);
 321                                 } else if (irg != NULL) {
 322                                         /* we have a graph, analyze it. */
 323                                         m = check_const_or_pure_function(irg, /*top=*/0);
 324                                         mode = mode_max(mode, m);
 325                                 }
 326                         } else
 327                                 return mtp_no_property;
 328                         node = get_Call_mem(node);
 329                         break;
 330
 331                 default:
 332                         return mtp_no_property;
 333                 }
 334         }
 335 }  /* _follow_mem */
 336
 337 /**
 338  * Follow the memory chain starting at node and determine
 339  * the mtp_property.
 340  *
 341  * @return mtp_property_const if only calls of const functions are detected
 342  *         mtp_property_pure if only Loads and const/pure
 343  *         calls detected
 344  *         0 else
 345  */
 346 static unsigned follow_mem(ir_graph *irg, ir_node *node, unsigned mode) {
 347         unsigned m;
 348
 349         m = _follow_mem(node);
 350         return mode_max(mode, m);
 351 }  /* follow_mem */
 352
 353 /*
 354  * Check if a graph represents a const function.
 355  *
 356  * @param irg  the graph
 357  * @param top  top call
 358  */
 359 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 360         ir_node *end, *endbl;
 361         int j;
 362         unsigned mode = get_irg_additional_properties(irg);
 363         ir_graph *rem = current_ir_graph;
 364
 365         if (mode & mtp_property_const) {
 366                 /* already marked as a const function */
 367                 return mtp_property_const;
 368         }
 369         if (mode & mtp_property_pure) {
 370                 /* already marked as a pure function */
 371                 return mtp_property_pure;
 372         }
 373
 374         if (IS_IRG_READY(irg)) {
 375                 /* already checked */
 376                 return mtp_no_property;
 377         }
 378         if (IS_IRG_BUSY(irg)) {
 379                 /* we are still evaluate this method. Be optimistic,
 380                    return the best possible so far but mark the result as temporary. */
 381                 return mtp_temporary | mtp_property_const;
 382         }
 383         SET_IRG_BUSY(irg);
 384
 385         end   = get_irg_end(irg);
 386         endbl = get_nodes_block(end);
 387         mode  = mtp_property_const;
 388
 389         current_ir_graph = irg;
 390
 391         inc_irg_visited(irg);
 392         /* mark the initial mem: recursion of follow_mem stops here */
 393         mark_irn_visited(get_irg_initial_mem(irg));
 394
 395         /* visit every Return */
 396         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 397                 ir_node *node = get_Block_cfgpred(endbl, j);
 398                 ir_op   *op   = get_irn_op(node);
 399                 ir_node *mem;
 400
 401                 /* Bad nodes usually do NOT produce anything, so it's ok */
 402                 if (op == op_Bad)
 403                         continue;
 404
 405                 if (op == op_Return) {
 406                         mem = get_Return_mem(node);
 407
 408                         /* Bad nodes usually do NOT produce anything, so it's ok */
 409                         if (is_Bad(mem))
 410                                 continue;
 411
 412                         if (mem != get_irg_initial_mem(irg))
 413                                 mode = mode_max(mode, follow_mem(irg, mem, mode));
 414                 } else {
 415                         /* Exception found. Cannot be const or pure. */
 416                         mode = mtp_no_property;
 417                         break;
 418                 }
 419                 if (mode == mtp_no_property)
 420                         break;
 421         }
 422
 423         if (mode != mtp_no_property) {
 424                 /* check, if a keep-alive exists */
 425                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 426                         ir_node *mem = get_End_keepalive(end, j);
 427
 428                         if (mode_M != get_irn_mode(mem))
 429                                 continue;
 430
 431                         mode = mode_max(mode, follow_mem(irg, mem, mode));
 432                         if (mode == mtp_no_property)
 433                                 break;
 434                 }
 435         }
 436
 437         if (mode) {
 438                 if (top || (mode & mtp_temporary) == 0) {
 439                         /* We use the temporary flag here to mark optimistic result.
 440                            Set the property only if we are sure that it does NOT base on
 441                            temporary results OR if we are at top-level. */
 442                         set_irg_additional_property(irg, mode & ~mtp_temporary);
 443                         SET_IRG_READY(irg);
 444                 }
 445         }
 446         if (top)
 447                 SET_IRG_READY(irg);
 448         CLEAR_IRG_BUSY(irg);
 449         current_ir_graph = rem;
 450         return mode;
 451 }  /* check_const_or_pure_function */
 452
 453 /**
 454  * Handle calls to const functions.
 455  */
 456 static void handle_const_Calls(env_t *ctx) {
 457         int i;
 458
 459         ctx->n_calls_SymConst = 0;
 460         ctx->n_calls_Sel      = 0;
 461
 462         /* all calls of const functions can be transformed */
 463         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 464                 ir_graph *irg  = get_irp_irg(i);
 465
 466                 ctx->const_call_list = NULL;
 467                 ctx->pure_call_list  = NULL;
 468                 ctx->proj_list = NULL;
 469                 irg_walk_graph(irg, NULL, collect_calls, ctx);
 470
 471                 if (ctx->const_call_list)
 472                         fix_const_call_list(irg, ctx->const_call_list, ctx->proj_list);
 473         }
 474 }  /* handle_const_Calls */
 475
 476 /*
 477  * optimize function calls by handling const functions
 478  */
 479 void optimize_funccalls(int force_run)
 480 {
 481         int i, n;
 482         unsigned num_const = 0;
 483         unsigned num_pure  = 0;
 484
 485         /* prepare: mark all graphs as not analyzed */
 486         n = get_irp_last_idx();
 487         ready_set = rbitset_malloc(n);
 488         busy_set  = rbitset_malloc(n);
 489
 490         /* first step: detect, which functions are const, i.e. do NOT touch any memory */
 491         DBG((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
 492         for (i = n - 1; i >= 0; --i) {
 493                 ir_graph *irg = get_irp_irg(i);
 494                 unsigned mode = check_const_or_pure_function(irg, /*top=*/1);
 495
 496                 if (mode & mtp_property_const) {
 497                         ++num_const;
 498                         DBG((dbg, LEVEL_2, "%+F has the const property\n", irg));
 499                 } else if (mode & mtp_property_pure) {
 500                         ++num_pure;
 501                         DBG((dbg, LEVEL_2, "%+F has the pure property\n", irg));
 502                 }
 503         }
 504
 505         if (force_run || num_const > 0) {
 506                 env_t ctx;
 507
 508                 handle_const_Calls(&ctx);
 509                 if (get_firm_verbosity()) {
 510                         DBG((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
 511                         DBG((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
 512                                ctx.n_calls_SymConst, ctx.n_calls_Sel));
 513                 }
 514         } else {
 515                 DBG((dbg, LEVEL_1, "No graphs without side effects detected\n"));
 516         }
 517         xfree(busy_set);
 518         xfree(ready_set);
 519 }  /* optimize_funccalls */
 520
 521 /* initialize the funccall optimization */
 522 void firm_init_funccalls(void)
 523 {
 524         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
 525 }  /* firm_init_funccalls */