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