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_X_regular:
 143                 case pn_Call_M_except:
 144                         set_irn_link(node, ctx->proj_list);
 145                         ctx->proj_list = node;
 146                         break;
 147                 default:
 148                         break;
 149                 }
 150         }
 151 }  /* collect_calls */
 152
 153 /**
 154  * Fix the list of collected Calls.
 155  *
 156  * @param irg        the graph that contained calls to pure functions
 157  * @param call_list  the list of all call sites of const functions
 158  * @param proj_list  the list of all memory/exception Proj's of this call sites
 159  */
 160 static void fix_const_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) {
 161         ir_node *call, *next, *mem, *proj;
 162         int exc_changed = 0;
 163         ir_graph *rem = current_ir_graph;
 164
 165         current_ir_graph = irg;
 166
 167         /* First step: fix all calls by removing it's memory input.
 168            It's original memory input is preserved in their link fields. */
 169         for (call = call_list; call; call = next) {
 170                 next = get_irn_link(call);
 171                 mem  = get_Call_mem(call);
 172
 173                 set_irn_link(call, mem);
 174                 set_Call_mem(call, get_irg_no_mem(irg));
 175
 176                 /*
 177                  * Sorrily we cannot simply set the node to 'float'.
 178                  * There is a reason for that:
 179                  *
 180                  * - The call might be inside a loop/if that is NOT entered
 181                  *   and calls a endless function. Setting the call to float
 182                  *   would allow to move it out from the loop/if causing this
 183                  *   function be called even if the loop/if is not entered ...
 184                  *
 185                  * This could be fixed using post-dominators for calls and Pin nodes
 186                  * but need some more analyzes to ensure that a call that potential
 187                  * never returns is not executed before some code that generates
 188                  * observable states...
 189                  */
 190
 191                 /* finally, this call can float
 192                 set_irn_pinned(call, op_pin_state_floats); */
 193                 hook_func_call(irg, call);
 194         }
 195
 196         /* Second step: fix all Proj's */
 197         for (proj = proj_list; proj; proj = next) {
 198                 next = get_irn_link(proj);
 199                 call = get_Proj_pred(proj);
 200                 mem  = get_irn_link(call);
 201
 202                 /* beware of calls in the pure call list */
 203                 if (! mem || get_irn_op(mem) == op_Call)
 204                         continue;
 205                 assert(get_irn_mode(mem) == mode_M);
 206
 207                 switch (get_Proj_proj(proj)) {
 208                 case pn_Call_M_regular: {
 209                         /* in dead code there might be cycles where proj == mem */
 210                         if (proj != mem)
 211                                 exchange(proj, mem);
 212                          break;
 213                 }
 214                 case pn_Call_X_except:
 215                 case pn_Call_M_except:
 216                         exc_changed = 1;
 217                         exchange(proj, get_irg_bad(irg));
 218                         break;
 219                 case pn_Call_X_regular: {
 220                         ir_node *block = get_nodes_block(call);
 221                         exc_changed = 1;
 222                         exchange(proj, new_r_Jmp(irg, block));
 223                         break;
 224                 }
 225                 default:
 226                         ;
 227                 }
 228         }
 229
 230         /* changes were done ... */
 231         set_irg_outs_inconsistent(irg);
 232         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 233
 234         if (exc_changed) {
 235                 /* ... including exception edges */
 236                 set_irg_doms_inconsistent(irg);
 237         }
 238         current_ir_graph = rem;
 239 }  /* fix_call_list */
 240
 241 /* marking */
 242 #define SET_IRG_READY(irg)      rbitset_set(ready_set, get_irg_idx(irg))
 243 #define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
 244 #define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
 245 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
 246 #define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
 247
 248 /* forward */
 249 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
 250
 251 /**
 252  * Calculate the bigger mode of two. Handle the temporary flag right.
 253  */
 254 static unsigned mode_max(unsigned a, unsigned b) {
 255         unsigned r, t = (a | b) & mtp_temporary;
 256         a &= ~mtp_temporary;
 257         b &= ~mtp_temporary;
 258
 259         if (a == mtp_no_property || b == mtp_no_property)
 260                 return mtp_no_property;
 261         r = a > b ? a : b;
 262         return r | t;
 263 }
 264
 265 /**
 266  * Follow the memory chain starting at node and determine
 267  * the mtp_property.
 268  *
 269  * @return mtp_property_const if only calls of const functions are detected
 270  *         mtp_property_pure if only Loads and const/pure
 271  *         calls detected
 272  *         mtp_no_property else
 273  */
 274 static unsigned _follow_mem(ir_node *node) {
 275         unsigned m, mode = mtp_property_const;
 276         ir_node  *ptr;
 277         int i;
 278
 279         for (;;) {
 280                 if (mode == mtp_no_property)
 281                         return mtp_no_property;
 282
 283                 if (irn_visited(node))
 284                         return mode;
 285
 286                 mark_irn_visited(node);
 287
 288                 switch (get_irn_opcode(node)) {
 289                 case iro_Proj:
 290                         node = get_Proj_pred(node);
 291                         break;
 292
 293                 case iro_NoMem:
 294                         /* finish here */
 295                         return mode;
 296
 297                 case iro_Phi:
 298                 case iro_Sync:
 299                         /* do a dfs search */
 300                         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 301                                 m    = _follow_mem(get_irn_n(node, i));
 302                                 mode = mode_max(mode, m);
 303                                 if (mode == mtp_no_property)
 304                                         return mtp_no_property;
 305                         }
 306                         return mode;
 307
 308                 case iro_Load:
 309                         /* Beware volatile Loads are NOT allowed in pure functions. */
 310                         if (get_Load_volatility(node) == volatility_is_volatile)
 311                                 return mtp_no_property;
 312                         mode = mode_max(mode, mtp_property_pure);
 313                         node = get_Load_mem(node);
 314                         break;
 315
 316                 case iro_Call:
 317                         /* A call is only tolerable if its either constant or pure. */
 318                         ptr = get_Call_ptr(node);
 319                         if (get_irn_op(ptr) == op_SymConst &&
 320                                 get_SymConst_kind(ptr) == symconst_addr_ent) {
 321                                 ir_entity *ent = get_SymConst_entity(ptr);
 322                                 ir_graph  *irg = get_entity_irg(ent);
 323
 324                                 if (irg == current_ir_graph) {
 325                                         /* A self-recursive call. The mode did not depend on this call. */
 326                                 } else if (irg == NULL) {
 327                                         m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
 328                                         mode = mode_max(mode, m);
 329                                 } else if (irg != NULL) {
 330                                         /* we have a graph, analyze it. */
 331                                         m = check_const_or_pure_function(irg, /*top=*/0);
 332                                         mode = mode_max(mode, m);
 333                                 }
 334                         } else
 335                                 return mtp_no_property;
 336                         node = get_Call_mem(node);
 337                         break;
 338
 339                 default:
 340                         return mtp_no_property;
 341                 }
 342         }
 343 }  /* _follow_mem */
 344
 345 /**
 346  * Follow the memory chain starting at node and determine
 347  * the mtp_property.
 348  *
 349  * @return mtp_property_const if only calls of const functions are detected
 350  *         mtp_property_pure  if only Loads and const/pure calls detected
 351  *         mtp_no_property else
 352  */
 353 static unsigned follow_mem(ir_node *node, unsigned mode) {
 354         unsigned m;
 355
 356         m = _follow_mem(node);
 357         return mode_max(mode, m);
 358 }  /* follow_mem */
 359
 360 /*
 361  * Check if a graph represents a const function.
 362  *
 363  * @param irg  the graph
 364  * @param top  top call
 365  */
 366 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 367         ir_node *end, *endbl;
 368         int j;
 369         unsigned mode = get_irg_additional_properties(irg);
 370         ir_graph *rem = current_ir_graph;
 371
 372         if (mode & mtp_property_const) {
 373                 /* already marked as a const function */
 374                 return mtp_property_const;
 375         }
 376         if (mode & mtp_property_pure) {
 377                 /* already marked as a pure function */
 378                 return mtp_property_pure;
 379         }
 380
 381         if (IS_IRG_READY(irg)) {
 382                 /* already checked */
 383                 return mtp_no_property;
 384         }
 385         if (IS_IRG_BUSY(irg)) {
 386                 /* we are still evaluate this method. Be optimistic,
 387                    return the best possible so far but mark the result as temporary. */
 388                 return mtp_temporary | mtp_property_const;
 389         }
 390         SET_IRG_BUSY(irg);
 391
 392         end   = get_irg_end(irg);
 393         endbl = get_nodes_block(end);
 394         mode  = mtp_property_const;
 395
 396         current_ir_graph = irg;
 397
 398         inc_irg_visited(irg);
 399         /* mark the initial mem: recursion of follow_mem stops here */
 400         mark_irn_visited(get_irg_initial_mem(irg));
 401
 402         /* visit every Return */
 403         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 404                 ir_node *node = get_Block_cfgpred(endbl, j);
 405                 ir_op   *op   = get_irn_op(node);
 406                 ir_node *mem;
 407
 408                 /* Bad nodes usually do NOT produce anything, so it's ok */
 409                 if (op == op_Bad)
 410                         continue;
 411
 412                 if (op == op_Return) {
 413                         mem = get_Return_mem(node);
 414
 415                         /* Bad nodes usually do NOT produce anything, so it's ok */
 416                         if (is_Bad(mem))
 417                                 continue;
 418
 419                         if (mem != get_irg_initial_mem(irg))
 420                                 mode = mode_max(mode, follow_mem(mem, mode));
 421                 } else {
 422                         /* Exception found. Cannot be const or pure. */
 423                         mode = mtp_no_property;
 424                         break;
 425                 }
 426                 if (mode == mtp_no_property)
 427                         break;
 428         }
 429
 430         if (mode != mtp_no_property) {
 431                 /* check, if a keep-alive exists */
 432                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 433                         ir_node *mem = get_End_keepalive(end, j);
 434
 435                         if (mode_M != get_irn_mode(mem))
 436                                 continue;
 437
 438                         mode = mode_max(mode, follow_mem(mem, mode));
 439                         if (mode == mtp_no_property)
 440                                 break;
 441                 }
 442         }
 443
 444         if (mode != mtp_no_property) {
 445                 if (top || (mode & mtp_temporary) == 0) {
 446                         /* We use the temporary flag here to mark optimistic result.
 447                            Set the property only if we are sure that it does NOT base on
 448                            temporary results OR if we are at top-level. */
 449                         set_irg_additional_property(irg, mode & ~mtp_temporary);
 450                         SET_IRG_READY(irg);
 451                 }
 452         }
 453         if (top)
 454                 SET_IRG_READY(irg);
 455         CLEAR_IRG_BUSY(irg);
 456         current_ir_graph = rem;
 457         return mode;
 458 }  /* check_const_or_pure_function */
 459
 460 /**
 461  * Handle calls to const functions.
 462  */
 463 static void handle_const_Calls(env_t *ctx) {
 464         int i;
 465
 466         ctx->n_calls_SymConst = 0;
 467         ctx->n_calls_Sel      = 0;
 468
 469         /* all calls of const functions can be transformed */
 470         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 471                 ir_graph *irg  = get_irp_irg(i);
 472
 473                 ctx->const_call_list = NULL;
 474                 ctx->pure_call_list  = NULL;
 475                 ctx->proj_list = NULL;
 476                 irg_walk_graph(irg, NULL, collect_calls, ctx);
 477
 478                 if (ctx->const_call_list)
 479                         fix_const_call_list(irg, ctx->const_call_list, ctx->proj_list);
 480         }
 481 }  /* handle_const_Calls */
 482
 483 /*
 484  * optimize function calls by handling const functions
 485  */
 486 void optimize_funccalls(int force_run)
 487 {
 488         int i, n;
 489         unsigned num_const = 0;
 490         unsigned num_pure  = 0;
 491
 492         /* prepare: mark all graphs as not analyzed */
 493         n = get_irp_last_idx();
 494         ready_set = rbitset_malloc(n);
 495         busy_set  = rbitset_malloc(n);
 496
 497         /* first step: detect, which functions are const, i.e. do NOT touch any memory */
 498         DBG((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
 499         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 500                 ir_graph *irg = get_irp_irg(i);
 501                 unsigned mode = check_const_or_pure_function(irg, /*top=*/1);
 502
 503                 if (mode & mtp_property_const) {
 504                         ++num_const;
 505                         DBG((dbg, LEVEL_2, "%+F has the const property\n", irg));
 506                 } else if (mode & mtp_property_pure) {
 507                         ++num_pure;
 508                         DBG((dbg, LEVEL_2, "%+F has the pure property\n", irg));
 509                 }
 510         }
 511
 512         if (force_run || num_const > 0) {
 513                 env_t ctx;
 514
 515                 handle_const_Calls(&ctx);
 516                 if (get_firm_verbosity()) {
 517                         DBG((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
 518                         DBG((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
 519                                ctx.n_calls_SymConst, ctx.n_calls_Sel));
 520                 }
 521         } else {
 522                 DBG((dbg, LEVEL_1, "No graphs without side effects detected\n"));
 523         }
 524         xfree(busy_set);
 525         xfree(ready_set);
 526 }  /* optimize_funccalls */
 527
 528 /* initialize the funccall optimization */
 529 void firm_init_funccalls(void)
 530 {
 531         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
 532 }  /* firm_init_funccalls */