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 calls detected
 343  *         mtp_no_property else
 344  */
 345 static unsigned follow_mem(ir_node *node, unsigned mode) {
 346         unsigned m;
 347
 348         m = _follow_mem(node);
 349         return mode_max(mode, m);
 350 }  /* follow_mem */
 351
 352 /*
 353  * Check if a graph represents a const function.
 354  *
 355  * @param irg  the graph
 356  * @param top  top call
 357  */
 358 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 359         ir_node *end, *endbl;
 360         int j;
 361         unsigned mode = get_irg_additional_properties(irg);
 362         ir_graph *rem = current_ir_graph;
 363
 364         if (mode & mtp_property_const) {
 365                 /* already marked as a const function */
 366                 return mtp_property_const;
 367         }
 368         if (mode & mtp_property_pure) {
 369                 /* already marked as a pure function */
 370                 return mtp_property_pure;
 371         }
 372
 373         if (IS_IRG_READY(irg)) {
 374                 /* already checked */
 375                 return mtp_no_property;
 376         }
 377         if (IS_IRG_BUSY(irg)) {
 378                 /* we are still evaluate this method. Be optimistic,
 379                    return the best possible so far but mark the result as temporary. */
 380                 return mtp_temporary | mtp_property_const;
 381         }
 382         SET_IRG_BUSY(irg);
 383
 384         end   = get_irg_end(irg);
 385         endbl = get_nodes_block(end);
 386         mode  = mtp_property_const;
 387
 388         current_ir_graph = irg;
 389
 390         inc_irg_visited(irg);
 391         /* mark the initial mem: recursion of follow_mem stops here */
 392         mark_irn_visited(get_irg_initial_mem(irg));
 393
 394         /* visit every Return */
 395         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 396                 ir_node *node = get_Block_cfgpred(endbl, j);
 397                 ir_op   *op   = get_irn_op(node);
 398                 ir_node *mem;
 399
 400                 /* Bad nodes usually do NOT produce anything, so it's ok */
 401                 if (op == op_Bad)
 402                         continue;
 403
 404                 if (op == op_Return) {
 405                         mem = get_Return_mem(node);
 406
 407                         /* Bad nodes usually do NOT produce anything, so it's ok */
 408                         if (is_Bad(mem))
 409                                 continue;
 410
 411                         if (mem != get_irg_initial_mem(irg))
 412                                 mode = mode_max(mode, follow_mem(mem, mode));
 413                 } else {
 414                         /* Exception found. Cannot be const or pure. */
 415                         mode = mtp_no_property;
 416                         break;
 417                 }
 418                 if (mode == mtp_no_property)
 419                         break;
 420         }
 421
 422         if (mode != mtp_no_property) {
 423                 /* check, if a keep-alive exists */
 424                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 425                         ir_node *mem = get_End_keepalive(end, j);
 426
 427                         if (mode_M != get_irn_mode(mem))
 428                                 continue;
 429
 430                         mode = mode_max(mode, follow_mem(mem, mode));
 431                         if (mode == mtp_no_property)
 432                                 break;
 433                 }
 434         }
 435
 436         if (mode != mtp_no_property) {
 437                 if (top || (mode & mtp_temporary) == 0) {
 438                         /* We use the temporary flag here to mark optimistic result.
 439                            Set the property only if we are sure that it does NOT base on
 440                            temporary results OR if we are at top-level. */
 441                         set_irg_additional_property(irg, mode & ~mtp_temporary);
 442                         SET_IRG_READY(irg);
 443                 }
 444         }
 445         if (top)
 446                 SET_IRG_READY(irg);
 447         CLEAR_IRG_BUSY(irg);
 448         current_ir_graph = rem;
 449         return mode;
 450 }  /* check_const_or_pure_function */
 451
 452 /**
 453  * Handle calls to const functions.
 454  */
 455 static void handle_const_Calls(env_t *ctx) {
 456         int i;
 457
 458         ctx->n_calls_SymConst = 0;
 459         ctx->n_calls_Sel      = 0;
 460
 461         /* all calls of const functions can be transformed */
 462         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 463                 ir_graph *irg  = get_irp_irg(i);
 464
 465                 ctx->const_call_list = NULL;
 466                 ctx->pure_call_list  = NULL;
 467                 ctx->proj_list = NULL;
 468                 irg_walk_graph(irg, NULL, collect_calls, ctx);
 469
 470                 if (ctx->const_call_list)
 471                         fix_const_call_list(irg, ctx->const_call_list, ctx->proj_list);
 472         }
 473 }  /* handle_const_Calls */
 474
 475 /*
 476  * optimize function calls by handling const functions
 477  */
 478 void optimize_funccalls(int force_run)
 479 {
 480         int i, n;
 481         unsigned num_const = 0;
 482         unsigned num_pure  = 0;
 483
 484         /* prepare: mark all graphs as not analyzed */
 485         n = get_irp_last_idx();
 486         ready_set = rbitset_malloc(n);
 487         busy_set  = rbitset_malloc(n);
 488
 489         /* first step: detect, which functions are const, i.e. do NOT touch any memory */
 490         DBG((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
 491         for (i = n - 1; i >= 0; --i) {
 492                 ir_graph *irg = get_irp_irg(i);
 493                 unsigned mode = check_const_or_pure_function(irg, /*top=*/1);
 494
 495                 if (mode & mtp_property_const) {
 496                         ++num_const;
 497                         DBG((dbg, LEVEL_2, "%+F has the const property\n", irg));
 498                 } else if (mode & mtp_property_pure) {
 499                         ++num_pure;
 500                         DBG((dbg, LEVEL_2, "%+F has the pure property\n", irg));
 501                 }
 502         }
 503
 504         if (force_run || num_const > 0) {
 505                 env_t ctx;
 506
 507                 handle_const_Calls(&ctx);
 508                 if (get_firm_verbosity()) {
 509                         DBG((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
 510                         DBG((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
 511                                ctx.n_calls_SymConst, ctx.n_calls_Sel));
 512                 }
 513         } else {
 514                 DBG((dbg, LEVEL_1, "No graphs without side effects detected\n"));
 515         }
 516         xfree(busy_set);
 517         xfree(ready_set);
 518 }  /* optimize_funccalls */
 519
 520 /* initialize the funccall optimization */
 521 void firm_init_funccalls(void)
 522 {
 523         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
 524 }  /* firm_init_funccalls */