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