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

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "config.h"
  27
  28 #include <adt/raw_bitset.h>
  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 "irloop_t.h"
  40 #include "ircons.h"
  41 #include "iredges_t.h"
  42 #include "irpass_t.h"
  43 #include "analyze_irg_args.h"
  44 #include "irhooks.h"
  45 #include "debug.h"
  46
  47 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  48
  49 /**
  50  * The walker environment for updating function calls.
  51  */
  52 typedef struct _env_t {
  53         unsigned n_calls_SymConst;
  54         unsigned n_calls_Sel;
  55         ir_node  *float_const_call_list;    /**< The list of all floating const function calls that will be changed. */
  56         ir_node  *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
  57         ir_node  *pure_call_list;           /**< The list of all pure function calls that will be changed. */
  58         ir_node  *nothrow_call_list;        /**< The list of all nothrow function calls that will be changed. */
  59         ir_node  *proj_list;                /**< The list of all potential Proj nodes that must be fixed. */
  60 } env_t;
  61
  62 /** If non-null, evaluates entities for being a heap alloc. */
  63 static check_alloc_entity_func is_alloc_entity = NULL;
  64
  65 /** Ready IRG's are marked in the ready set. */
  66 static unsigned *ready_set;
  67
  68 /** IRG's that are in progress are marked here. */
  69 static unsigned *busy_set;
  70
  71 /**
  72  * We misuse the mtp_property_inherited flag as temporary here.
  73  * The is ok, as we cannot set or get it anyway using the
  74  * get_addtional_properties API.
  75  */
  76 #define mtp_temporary  mtp_property_inherited
  77
  78 /**
  79  * Walker: Collect all calls to const and pure functions
  80  * to lists. Collect all Proj(Call) nodes into a Proj list.
  81  */
  82 static void collect_const_and_pure_calls(ir_node *node, void *env) {
  83         env_t     *ctx = env;
  84         ir_node   *call, *ptr;
  85         ir_entity *ent;
  86         unsigned  and_prop, or_prop, prop;
  87
  88         if (is_Call(node)) {
  89                 call = node;
  90
  91                 /* set the link to NULL for all non-const/pure calls */
  92                 set_irn_link(call, NULL);
  93                 ptr = get_Call_ptr(call);
  94                 if (is_Global(ptr)) {
  95                         ent = get_Global_entity(ptr);
  96
  97                         prop = get_entity_additional_properties(ent);
  98                         if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
  99                                 return;
 100                         ++ctx->n_calls_SymConst;
 101                 } else if (get_opt_closed_world() &&
 102                            is_Sel(ptr) &&
 103                            get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
 104                         /* If all possible callees are const functions, we can remove the memory edge. */
 105                         int i, n_callees = get_Call_n_callees(call);
 106                         if (n_callees == 0) {
 107                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 108                                    when executed as there is no implementation to call.  So better not
 109                                    optimize. */
 110                                 return;
 111                         }
 112
 113                         /* note that const function are a subset of pure ones */
 114                         and_prop = mtp_property_const | mtp_property_pure;
 115                         or_prop  = 0;
 116                         for (i = 0; i < n_callees; ++i) {
 117                                 ent = get_Call_callee(call, i);
 118                                 if (ent == unknown_entity) {
 119                                         /* we don't know which entity is called here */
 120                                         return;
 121                                 }
 122                                 prop      = get_entity_additional_properties(ent);
 123                                 and_prop &= prop;
 124                                 or_prop  &= prop;
 125                                 if (and_prop == mtp_no_property)
 126                                         return;
 127                         }
 128                         prop = and_prop | (or_prop & mtp_property_has_loop);
 129                         ++ctx->n_calls_Sel;
 130                 } else
 131                         return;
 132
 133                 /* ok, if we get here we found a call to a const or a pure function */
 134                 if (prop & mtp_property_pure) {
 135                         set_irn_link(call, ctx->pure_call_list);
 136                         ctx->pure_call_list = call;
 137                 } else {
 138                         if (prop & mtp_property_has_loop) {
 139                                 set_irn_link(call, ctx->nonfloat_const_call_list);
 140                                 ctx->nonfloat_const_call_list = call;
 141                         } else {
 142                                 set_irn_link(call, ctx->float_const_call_list);
 143                                 ctx->float_const_call_list = call;
 144                         }
 145                 }
 146         } else if (is_Proj(node)) {
 147                 /*
 148                  * Collect all memory and exception Proj's from
 149                  * calls.
 150                  */
 151                 call = get_Proj_pred(node);
 152                 if (! is_Call(call))
 153                         return;
 154
 155                 /* collect the Proj's in the Proj list */
 156                 switch (get_Proj_proj(node)) {
 157                 case pn_Call_M_regular:
 158                 case pn_Call_X_except:
 159                 case pn_Call_X_regular:
 160                 case pn_Call_M_except:
 161                         set_irn_link(node, ctx->proj_list);
 162                         ctx->proj_list = node;
 163                         break;
 164                 default:
 165                         break;
 166                 }
 167         }
 168 }  /* collect_const_and_pure_calls */
 169
 170 /**
 171  * Fix the list of collected Calls.
 172  *
 173  * @param irg  the graph that contained calls to pure functions
 174  * @param ctx  context
 175  */
 176 static void fix_const_call_lists(ir_graph *irg, env_t *ctx) {
 177         ir_node *call, *next, *mem, *proj;
 178         int exc_changed = 0;
 179         ir_graph *rem = current_ir_graph;
 180
 181         current_ir_graph = irg;
 182
 183         /* First step: fix all calls by removing their memory input and let
 184          * them floating.
 185          * The original memory input is preserved in their link fields. */
 186         for (call = ctx->float_const_call_list; call != NULL; call = next) {
 187                 next = get_irn_link(call);
 188                 mem  = get_Call_mem(call);
 189
 190                 set_irn_link(call, mem);
 191                 set_Call_mem(call, get_irg_no_mem(irg));
 192
 193                 /*
 194                  * Unfortunately we cannot simply set the node to 'float'.
 195                  * There is a reason for that:
 196                  *
 197                  * - The call might be inside a loop/if that is NOT entered
 198                  *   and calls a endless function. Setting the call to float
 199                  *   would allow to move it out from the loop/if causing this
 200                  *   function be called even if the loop/if is not entered ...
 201                  *
 202                  * This could be fixed using post-dominators for calls and Pin nodes
 203                  * but need some more analyzes to ensure that a call that potential
 204                  * never returns is not executed before some code that generates
 205                  * observable states...
 206                  */
 207
 208                 /* finally, this call can float */
 209                 set_irn_pinned(call, op_pin_state_floats);
 210                 hook_func_call(irg, call);
 211         }
 212
 213         /* Last step: fix all Proj's */
 214         for (proj = ctx->proj_list; proj != NULL; proj = next) {
 215                 next = get_irn_link(proj);
 216                 call = get_Proj_pred(proj);
 217                 mem  = get_irn_link(call);
 218
 219                 /* beware of calls in the pure call list */
 220                 if (!mem || is_Call(mem))
 221                         continue;
 222                 assert(get_irn_mode(mem) == mode_M);
 223
 224                 switch (get_Proj_proj(proj)) {
 225                 case pn_Call_M_regular: {
 226                         /* in dead code there might be cycles where proj == mem */
 227                         if (proj != mem)
 228                                 exchange(proj, mem);
 229                          break;
 230                 }
 231                 case pn_Call_X_except:
 232                 case pn_Call_M_except:
 233                         exc_changed = 1;
 234                         exchange(proj, get_irg_bad(irg));
 235                         break;
 236                 case pn_Call_X_regular: {
 237                         ir_node *block = get_nodes_block(call);
 238                         exc_changed = 1;
 239                         exchange(proj, new_r_Jmp(block));
 240                         break;
 241                 }
 242                 default:
 243                         ;
 244                 }
 245         }
 246
 247         /* changes were done ... */
 248         set_irg_outs_inconsistent(irg);
 249         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 250
 251         if (exc_changed) {
 252                 /* ... including exception edges */
 253                 set_irg_doms_inconsistent(irg);
 254         }
 255         current_ir_graph = rem;
 256 }  /* fix_const_call_list */
 257
 258 /**
 259  * Walker: Collect all calls to nothrow functions
 260  * to lists. Collect all Proj(Call) nodes into a Proj list.
 261  */
 262 static void collect_nothrow_calls(ir_node *node, void *env) {
 263         env_t *ctx = env;
 264         ir_node *call, *ptr;
 265         ir_entity *ent;
 266         unsigned prop;
 267
 268         if (is_Call(node)) {
 269                 call = node;
 270
 271                 /* set the link to NULL for all non-const/pure calls */
 272                 set_irn_link(call, NULL);
 273                 ptr = get_Call_ptr(call);
 274                 if (is_Global(ptr)) {
 275                         ent = get_Global_entity(ptr);
 276
 277                         prop = get_entity_additional_properties(ent);
 278                         if ((prop & mtp_property_nothrow) == 0)
 279                                 return;
 280                         ++ctx->n_calls_SymConst;
 281                 } else if (get_opt_closed_world() &&
 282                            is_Sel(ptr) &&
 283                            get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
 284                         /* If all possible callees are nothrow functions, we can remove the exception edge. */
 285                         int i, n_callees = get_Call_n_callees(call);
 286                         if (n_callees == 0) {
 287                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 288                                    when executed as there is no implementation to call.  So better not
 289                                    optimize. */
 290                                 return;
 291                         }
 292
 293                         /* note that const function are a subset of pure ones */
 294                         prop = mtp_property_nothrow;
 295                         for (i = 0; i < n_callees; ++i) {
 296                                 ent = get_Call_callee(call, i);
 297                                 if (ent == unknown_entity) {
 298                                         /* we don't know which entity is called here */
 299                                         return;
 300                                 }
 301                                 prop &= get_entity_additional_properties(ent);
 302                                 if (prop == mtp_no_property)
 303                                         return;
 304                         }
 305                         ++ctx->n_calls_Sel;
 306                 } else
 307                         return;
 308
 309                 /* ok, if we get here we found a call to a nothrow function */
 310                 set_irn_link(call, ctx->nothrow_call_list);
 311                 ctx->nothrow_call_list = call;
 312         } else if (is_Proj(node)) {
 313                 /*
 314                  * Collect all memory and exception Proj's from
 315                  * calls.
 316                  */
 317                 call = get_Proj_pred(node);
 318                 if (! is_Call(call))
 319                         return;
 320
 321                 /* collect the Proj's in the Proj list */
 322                 switch (get_Proj_proj(node)) {
 323                 case pn_Call_M_regular:
 324                 case pn_Call_X_except:
 325                 case pn_Call_X_regular:
 326                 case pn_Call_M_except:
 327                         set_irn_link(node, ctx->proj_list);
 328                         ctx->proj_list = node;
 329                         break;
 330                 default:
 331                         break;
 332                 }
 333         }
 334 }  /* collect_nothrow_calls */
 335
 336 /**
 337  * Fix the list of collected nothrow Calls.
 338  *
 339  * @param irg        the graph that contained calls to pure functions
 340  * @param call_list  the list of all call sites of const functions
 341  * @param proj_list  the list of all memory/exception Proj's of this call sites
 342  */
 343 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) {
 344         ir_node *call, *next, *proj;
 345         int exc_changed = 0;
 346         ir_graph *rem = current_ir_graph;
 347
 348         current_ir_graph = irg;
 349
 350         /* First step: go through the list of calls and mark them. */
 351         for (call = call_list; call; call = next) {
 352                 next = get_irn_link(call);
 353
 354                 /* current_ir_graph is in memory anyway, so it's a good marker */
 355                 set_irn_link(call, &current_ir_graph);
 356                 hook_func_call(irg, call);
 357         }
 358
 359         /* Second step: Remove all exception Proj's */
 360         for (proj = proj_list; proj; proj = next) {
 361                 next = get_irn_link(proj);
 362                 call = get_Proj_pred(proj);
 363
 364                 /* handle only marked calls */
 365                 if (get_irn_link(call) != &current_ir_graph)
 366                         continue;
 367
 368                 /* kill any exception flow */
 369                 switch (get_Proj_proj(proj)) {
 370                 case pn_Call_X_except:
 371                 case pn_Call_M_except:
 372                         exc_changed = 1;
 373                         exchange(proj, get_irg_bad(irg));
 374                         break;
 375                 case pn_Call_X_regular: {
 376                         ir_node *block = get_nodes_block(call);
 377                         exc_changed = 1;
 378                         exchange(proj, new_r_Jmp(block));
 379                         break;
 380                 }
 381                 default:
 382                         ;
 383                 }
 384         }
 385
 386         /* changes were done ... */
 387         set_irg_outs_inconsistent(irg);
 388         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 389
 390         if (exc_changed) {
 391                 /* ... including exception edges */
 392                 set_irg_doms_inconsistent(irg);
 393         }
 394         current_ir_graph = rem;
 395 }  /* fix_nothrow_call_list */
 396
 397 /* marking */
 398 #define SET_IRG_READY(irg)      rbitset_set(ready_set, get_irg_idx(irg))
 399 #define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
 400 #define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
 401 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
 402 #define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
 403
 404 /* forward */
 405 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
 406 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top);
 407
 408 /**
 409  * Calculate the bigger property of two. Handle the temporary flag right.
 410  */
 411 static unsigned max_property(unsigned a, unsigned b) {
 412         unsigned r, t = (a | b) & mtp_temporary;
 413         a &= ~mtp_temporary;
 414         b &= ~mtp_temporary;
 415
 416         if (a == mtp_no_property || b == mtp_no_property)
 417                 return mtp_no_property;
 418         r = a > b ? a : b;
 419         return r | t;
 420 }  /* max_property */
 421
 422 /**
 423  * Follow the memory chain starting at node and determine
 424  * the mtp_property.
 425  *
 426  * @return mtp_property_const if only calls of const functions are detected
 427  *         mtp_property_pure  if only Loads and const/pure calls detected
 428  *         mtp_no_property    else
 429  */
 430 static unsigned _follow_mem(ir_node *node) {
 431         unsigned m, mode = mtp_property_const;
 432         ir_node  *ptr;
 433         int i;
 434
 435         for (;;) {
 436                 if (mode == mtp_no_property)
 437                         return mtp_no_property;
 438
 439                 if (irn_visited_else_mark(node))
 440                         return mode;
 441
 442                 switch (get_irn_opcode(node)) {
 443                 case iro_Proj:
 444                         node = get_Proj_pred(node);
 445                         break;
 446
 447                 case iro_NoMem:
 448                         /* finish here */
 449                         return mode;
 450
 451                 case iro_Phi:
 452                 case iro_Sync:
 453                         /* do a dfs search */
 454                         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 455                                 m    = _follow_mem(get_irn_n(node, i));
 456                                 mode = max_property(mode, m);
 457                                 if (mode == mtp_no_property)
 458                                         return mtp_no_property;
 459                         }
 460                         return mode;
 461
 462                 case iro_Load:
 463                         /* Beware volatile Loads are NOT allowed in pure functions. */
 464                         if (get_Load_volatility(node) == volatility_is_volatile)
 465                                 return mtp_no_property;
 466                         mode = max_property(mode, mtp_property_pure);
 467                         node = get_Load_mem(node);
 468                         break;
 469
 470                 case iro_Call:
 471                         /* A call is only tolerable if its either constant or pure. */
 472                         ptr = get_Call_ptr(node);
 473                         if (is_SymConst_addr_ent(ptr)) {
 474                                 ir_entity *ent = get_SymConst_entity(ptr);
 475                                 ir_graph  *irg = get_entity_irg(ent);
 476
 477                                 if (irg == current_ir_graph) {
 478                                         /* A self-recursive call. The property did not depend on this call. */
 479                                 } else if (irg == NULL) {
 480                                         m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
 481                                         mode = max_property(mode, m);
 482                                 } else if (irg != NULL) {
 483                                         /* we have a graph, analyze it. */
 484                                         m = check_const_or_pure_function(irg, /*top=*/0);
 485                                         mode = max_property(mode, m);
 486                                 }
 487                         } else
 488                                 return mtp_no_property;
 489                         node = get_Call_mem(node);
 490                         break;
 491
 492                 default:
 493                         return mtp_no_property;
 494                 }
 495         }
 496 }  /* _follow_mem */
 497
 498 /**
 499  * Follow the memory chain starting at node and determine
 500  * the mtp_property.
 501  *
 502  * @return mtp_property_const if only calls of const functions are detected
 503  *         mtp_property_pure  if only Loads and const/pure calls detected
 504  *         mtp_no_property else
 505  */
 506 static unsigned follow_mem(ir_node *node, unsigned mode) {
 507         unsigned m;
 508
 509         m = _follow_mem(node);
 510         return max_property(mode, m);
 511 }  /* follow_mem */
 512
 513 /**
 514  * Check if a graph represents a const or a pure function.
 515  *
 516  * @param irg  the graph to check
 517  * @param top  if set, this is the top call
 518  */
 519 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 520         ir_node *end, *endbl;
 521         int j;
 522         unsigned prop = get_irg_additional_properties(irg);
 523         ir_graph *rem = current_ir_graph;
 524
 525         if (prop & mtp_property_const) {
 526                 /* already marked as a const function */
 527                 return mtp_property_const;
 528         }
 529         if (prop & mtp_property_pure) {
 530                 /* already marked as a pure function */
 531                 return mtp_property_pure;
 532         }
 533
 534         if (IS_IRG_READY(irg)) {
 535                 /* already checked */
 536                 return mtp_no_property;
 537         }
 538         if (IS_IRG_BUSY(irg)) {
 539                 /* we are still evaluate this method. Be optimistic,
 540                    return the best possible so far but mark the result as temporary. */
 541                 return mtp_temporary | mtp_property_const;
 542         }
 543         SET_IRG_BUSY(irg);
 544
 545         end   = get_irg_end(irg);
 546         endbl = get_nodes_block(end);
 547         prop  = mtp_property_const;
 548
 549         current_ir_graph = irg;
 550
 551         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 552         inc_irg_visited(irg);
 553         /* mark the initial mem: recursion of follow_mem() stops here */
 554         mark_irn_visited(get_irg_initial_mem(irg));
 555
 556         /* visit every Return */
 557         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 558                 ir_node   *node = get_Block_cfgpred(endbl, j);
 559                 ir_opcode code  = get_irn_opcode(node);
 560                 ir_node   *mem;
 561
 562                 /* Bad nodes usually do NOT produce anything, so it's ok */
 563                 if (code == iro_Bad)
 564                         continue;
 565
 566                 if (code == iro_Return) {
 567                         mem = get_Return_mem(node);
 568
 569                         /* Bad nodes usually do NOT produce anything, so it's ok */
 570                         if (is_Bad(mem))
 571                                 continue;
 572
 573                         if (mem != get_irg_initial_mem(irg))
 574                                 prop = max_property(prop, follow_mem(mem, prop));
 575                 } else {
 576                         /* Exception found. Cannot be const or pure. */
 577                         prop = mtp_no_property;
 578                         break;
 579                 }
 580                 if (prop == mtp_no_property)
 581                         break;
 582         }
 583
 584         if (prop != mtp_no_property) {
 585                 /* check, if a keep-alive exists */
 586                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 587                         ir_node *kept = get_End_keepalive(end, j);
 588
 589                         if (is_Block(kept)) {
 590                                 prop = mtp_no_property;
 591                                 break;
 592                         }
 593
 594                         if (mode_M != get_irn_mode(kept))
 595                                 continue;
 596
 597                         prop = max_property(prop, follow_mem(kept, prop));
 598                         if (prop == mtp_no_property)
 599                                 break;
 600                 }
 601         }
 602
 603         if (prop != mtp_no_property) {
 604                 if (top || (prop & mtp_temporary) == 0) {
 605                         /* We use the temporary flag here to mark optimistic result.
 606                            Set the property only if we are sure that it does NOT base on
 607                            temporary results OR if we are at top-level. */
 608                         set_irg_additional_property(irg, prop & ~mtp_temporary);
 609                         SET_IRG_READY(irg);
 610                 }
 611         }
 612         if (top)
 613                 SET_IRG_READY(irg);
 614         CLEAR_IRG_BUSY(irg);
 615         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 616         current_ir_graph = rem;
 617         return prop;
 618 }  /* check_const_or_pure_function */
 619
 620 /**
 621  * Handle calls to const functions.
 622  *
 623  * @param ctx  context
 624  */
 625 static void handle_const_Calls(env_t *ctx) {
 626         int i;
 627
 628         ctx->n_calls_SymConst = 0;
 629         ctx->n_calls_Sel      = 0;
 630
 631         /* all calls of const functions can be transformed */
 632         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 633                 ir_graph *irg  = get_irp_irg(i);
 634
 635                 ctx->float_const_call_list    = NULL;
 636                 ctx->nonfloat_const_call_list = NULL;
 637                 ctx->pure_call_list           = NULL;
 638                 ctx->proj_list                = NULL;
 639
 640                 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 641                 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
 642
 643                 if (ctx->float_const_call_list != NULL)
 644                         fix_const_call_lists(irg, ctx);
 645                 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 646         }
 647 }  /* handle_const_Calls */
 648
 649 /**
 650  * Handle calls to nothrow functions.
 651  *
 652  * @param ctx  context
 653  */
 654 static void handle_nothrow_Calls(env_t *ctx) {
 655         int i;
 656
 657         ctx->n_calls_SymConst = 0;
 658         ctx->n_calls_Sel      = 0;
 659
 660         /* all calls of const functions can be transformed */
 661         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 662                 ir_graph *irg  = get_irp_irg(i);
 663
 664                 ctx->nothrow_call_list = NULL;
 665                 ctx->proj_list         = NULL;
 666
 667                 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 668                 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
 669
 670                 if (ctx->nothrow_call_list)
 671                         fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
 672                 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 673         }
 674 }
 675
 676 /**
 677  * Check, whether a given node represents a return value of
 678  * a malloc like function (ie, new heap allocated memory).
 679  *
 680  * @param node  the node to check
 681  */
 682 static int is_malloc_call_result(const ir_node *node) {
 683         if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
 684                 /* Firm style high-level allocation */
 685                 return 1;
 686         }
 687         if (is_alloc_entity != NULL && is_Call(node)) {
 688                 ir_node *ptr = get_Call_ptr(node);
 689
 690                 if (is_Global(ptr)) {
 691                         ir_entity *ent = get_Global_entity(ptr);
 692                         return is_alloc_entity(ent);
 693                 }
 694         }
 695         return 0;
 696 }  /* is_malloc_call_result */
 697
 698 /**
 699  * Update a property depending on a call property.
 700  */
 701 static unsigned update_property(unsigned orig_prop, unsigned call_prop) {
 702         unsigned t = (orig_prop | call_prop) & mtp_temporary;
 703         unsigned r = orig_prop & call_prop;
 704         return r | t;
 705 }  /** update_property */
 706
 707 /**
 708  * Check if a node is stored.
 709  */
 710 static int is_stored(const ir_node *n) {
 711         const ir_edge_t *edge;
 712         const ir_node   *ptr;
 713
 714         foreach_out_edge(n, edge) {
 715                 const ir_node *succ = get_edge_src_irn(edge);
 716
 717                 switch (get_irn_opcode(succ)) {
 718                 case iro_Return:
 719                 case iro_Load:
 720                 case iro_Cmp:
 721                         /* ok */
 722                         break;
 723                 case iro_Store:
 724                         if (get_Store_value(succ) == n)
 725                                 return 1;
 726                         /* ok if its only the address input */
 727                         break;
 728                 case iro_Sel:
 729                 case iro_Cast:
 730                 case iro_Confirm:
 731                         if (is_stored(succ))
 732                                 return 1;
 733                         break;
 734                 case iro_Call:
 735                         ptr = get_Call_ptr(succ);
 736                         if (is_Global(ptr)) {
 737                                 ir_entity *ent = get_Global_entity(ptr);
 738                                 int       i;
 739
 740                                 /* we know the called entity */
 741                                 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
 742                                         if (get_Call_param(succ, i) == n) {
 743                                                 /* n is the i'th param of the call */
 744                                                 if (get_method_param_access(ent, i) & ptr_access_store) {
 745                                                         /* n is store in ent */
 746                                                         return 1;
 747                                                 }
 748                                         }
 749                                 }
 750                         } else {
 751                                 /* unknown call address */
 752                                 return 1;
 753                         }
 754                         break;
 755                 default:
 756                         /* bad, potential alias */
 757                         return 1;
 758                 }
 759         }
 760         return 0;
 761 }  /* is_stored */
 762
 763 /**
 764  * Check that the return value of an irg is not stored anywhere.
 765  *
 766  * return ~mtp_property_malloc if return values are stored, ~0 else
 767  */
 768 static unsigned check_stored_result(ir_graph *irg) {
 769         ir_node  *end_blk = get_irg_end_block(irg);
 770         int      i, j;
 771         unsigned res = ~0;
 772         int      old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
 773
 774         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 775                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 776
 777                 if (! is_Return(pred))
 778                         continue;
 779                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 780                         const ir_node *irn = get_Return_res(pred, j);
 781
 782                         if (is_stored(irn)) {
 783                                 /* bad, might create an alias */
 784                                 res = ~mtp_property_malloc;
 785                                 goto finish;
 786                         }
 787                 }
 788         }
 789 finish:
 790         if (! old_edges)
 791                 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 792         return res;
 793 }  /* check_stored_result */
 794
 795 /**
 796  * Check if a graph represents a nothrow or a malloc function.
 797  *
 798  * @param irg  the graph to check
 799  * @param top  if set, this is the top call
 800  */
 801 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) {
 802         ir_node   *end_blk = get_irg_end_block(irg);
 803         ir_entity *ent;
 804         ir_type   *mtp;
 805         int       i, j;
 806         unsigned  curr_prop = mtp_property_malloc | mtp_property_nothrow;
 807
 808         if (IS_IRG_READY(irg)) {
 809                 /* already checked */
 810                 return get_irg_additional_properties(irg);
 811         }
 812         if (IS_IRG_BUSY(irg)) {
 813                 /* we are still evaluate this method. Be optimistic,
 814                 return the best possible so far but mark the result as temporary. */
 815                 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
 816         }
 817         SET_IRG_BUSY(irg);
 818
 819         ent = get_irg_entity(irg);
 820         mtp = get_entity_type(ent);
 821
 822         if (get_method_n_ress(mtp) <= 0)
 823                 curr_prop &= ~mtp_property_malloc;
 824
 825         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 826                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 827
 828                 if (is_Return(pred)) {
 829                         if (curr_prop & mtp_property_malloc) {
 830                                 /* check, if malloc is called here */
 831                                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 832                                         ir_node *res = get_Return_res(pred, j);
 833
 834                                         /* skip Confirms and Casts */
 835                                         res = skip_HighLevel_ops(res);
 836                                         /* skip Proj's */
 837                                         while (is_Proj(res))
 838                                                 res = get_Proj_pred(res);
 839                                         if (is_malloc_call_result(res)) {
 840                                                 /* ok, this is a malloc */
 841                                         } else if (is_Call(res)) {
 842                                                 ir_node *ptr = get_Call_ptr(res);
 843
 844                                                 if (is_Global(ptr)) {
 845                                                         /* a direct call */
 846                                                         ir_entity *ent    = get_Global_entity(ptr);
 847                                                         ir_graph  *callee = get_entity_irg(ent);
 848
 849                                                         if (callee == irg) {
 850                                                                 /* A self-recursive call. The property did not depend on this call. */
 851                                                         } else if (callee != NULL) {
 852                                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
 853                                                                 curr_prop = update_property(curr_prop, prop);
 854                                                         } else {
 855                                                                 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
 856                                                         }
 857                                                 } else if (get_opt_closed_world() &&
 858                                                            is_Sel(ptr) &&
 859                                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 860                                                         /* check if all possible callees are malloc functions. */
 861                                                         int i, n_callees = get_Call_n_callees(res);
 862                                                         if (n_callees == 0) {
 863                                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 864                                                                    when executed as there is no implementation to call.  So better not
 865                                                                    optimize. */
 866                                                                 curr_prop &= ~mtp_property_malloc;
 867                                                                 continue;
 868                                                         }
 869
 870                                                         for (i = 0; i < n_callees; ++i) {
 871                                                                 ir_entity *ent = get_Call_callee(res, i);
 872                                                                 if (ent == unknown_entity) {
 873                                                                         /* we don't know which entity is called here */
 874                                                                         curr_prop &= ~mtp_property_malloc;
 875                                                                         break;
 876                                                                 }
 877                                                                 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
 878                                                                         curr_prop &= ~mtp_property_malloc;
 879                                                                         break;
 880                                                                 }
 881                                                         }
 882                                                         /* if we pass the for cycle, malloc is still ok */
 883                                                 } else {
 884                                                         /* unknown call */
 885                                                         curr_prop &= ~mtp_property_malloc;
 886                                                 }
 887                                         } else {
 888                                                 /* unknown return value */
 889                                                 curr_prop &= ~mtp_property_malloc;
 890                                         }
 891                                 }
 892                         }
 893                 } else if (curr_prop & mtp_property_nothrow) {
 894                         /* exception flow detected */
 895                         pred = skip_Proj(pred);
 896
 897                         if (is_Call(pred)) {
 898                                 ir_node *ptr = get_Call_ptr(pred);
 899
 900                                 if (is_Global(ptr)) {
 901                                         /* a direct call */
 902                                         ir_entity *ent    = get_Global_entity(ptr);
 903                                         ir_graph  *callee = get_entity_irg(ent);
 904
 905                                         if (callee == irg) {
 906                                                 /* A self-recursive call. The property did not depend on this call. */
 907                                         } else if (callee != NULL) {
 908                                                 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
 909                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
 910                                                 curr_prop = update_property(curr_prop, prop);
 911                                         } else {
 912                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
 913                                                         curr_prop &= ~mtp_property_nothrow;
 914                                         }
 915                                 } else if (get_opt_closed_world() &&
 916                                            is_Sel(ptr) &&
 917                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 918                                         /* check if all possible callees are nothrow functions. */
 919                                         int i, n_callees = get_Call_n_callees(pred);
 920                                         if (n_callees == 0) {
 921                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 922                                                    when executed as there is no implementation to call.  So better not
 923                                                    optimize. */
 924                                                 curr_prop &= ~mtp_property_nothrow;
 925                                                 continue;
 926                                         }
 927
 928                                         for (i = 0; i < n_callees; ++i) {
 929                                                 ir_entity *ent = get_Call_callee(pred, i);
 930                                                 if (ent == unknown_entity) {
 931                                                         /* we don't know which entity is called here */
 932                                                         curr_prop &= ~mtp_property_nothrow;
 933                                                         break;
 934                                                 }
 935                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
 936                                                         curr_prop &= ~mtp_property_nothrow;
 937                                                         break;
 938                                                 }
 939                                         }
 940                                         /* if we pass the for cycle, nothrow is still ok */
 941                                 } else {
 942                                         /* unknown call */
 943                                         curr_prop &= ~mtp_property_nothrow;
 944                                 }
 945                         } else {
 946                                 /* real exception flow possible. */
 947                                 curr_prop &= ~mtp_property_nothrow;
 948                         }
 949                 }
 950                 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
 951                         /* no need to search further */
 952                         break;
 953                 }
 954         }
 955
 956         if (curr_prop & mtp_property_malloc) {
 957                 /*
 958                  * Note that the malloc property means not only return newly allocated
 959                  * memory, but also that this memory is ALIAS FREE.
 960                  * To ensure that, we do NOT allow that the returned memory is somewhere
 961                  * stored.
 962              */
 963                 curr_prop &= check_stored_result(irg);
 964         }
 965
 966         if (curr_prop != mtp_no_property) {
 967                 if (top || (curr_prop & mtp_temporary) == 0) {
 968                         /* We use the temporary flag here to mark an optimistic result.
 969                            Set the property only if we are sure that it does NOT base on
 970                            temporary results OR if we are at top-level. */
 971                         set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
 972                         SET_IRG_READY(irg);
 973                 }
 974         }
 975         if (top)
 976                 SET_IRG_READY(irg);
 977         CLEAR_IRG_BUSY(irg);
 978         return curr_prop;
 979 }  /* check_nothrow_or_malloc */
 980
 981 /**
 982  * When a function was detected as "const", it might be moved out of loops.
 983  * This might be dangerous if the graph can contain endless loops.
 984  */
 985 static void check_for_possible_endless_loops(ir_graph *irg) {
 986         ir_loop *root_loop;
 987         assure_cf_loop(irg);
 988
 989         root_loop = get_irg_loop(irg);
 990         if (root_loop->flags & loop_outer_loop)
 991                 set_irg_additional_property(irg, mtp_property_has_loop);
 992 }
 993
 994 /*
 995  * optimize function calls by handling const functions
 996  */
 997 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
 998 {
 999         int i, last_idx;
1000         unsigned num_const   = 0;
1001         unsigned num_pure    = 0;
1002         unsigned num_nothrow = 0;
1003         unsigned num_malloc  = 0;
1004
1005         is_alloc_entity = callback;
1006
1007         /* prepare: mark all graphs as not analyzed */
1008         last_idx  = get_irp_last_idx();
1009         ready_set = rbitset_malloc(last_idx);
1010         busy_set  = rbitset_malloc(last_idx);
1011
1012         /* first step: detect, which functions are nothrow or malloc */
1013         DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1014         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1015                 ir_graph *irg = get_irp_irg(i);
1016                 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1017
1018                 if (prop & mtp_property_nothrow) {
1019                         ++num_nothrow;
1020                         DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1021                 } else if (prop & mtp_property_malloc) {
1022                         ++num_malloc;
1023                         DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1024                 }
1025         }
1026
1027         /* second step: remove exception edges: this must be done before the
1028            detection of const and pure functions take place. */
1029         if (force_run || num_nothrow > 0) {
1030                 env_t ctx;
1031
1032                 handle_nothrow_Calls(&ctx);
1033                 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1034                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1035                         ctx.n_calls_SymConst, ctx.n_calls_Sel));
1036         } else {
1037                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1038         }
1039
1040         rbitset_clear_all(ready_set, last_idx);
1041         rbitset_clear_all(busy_set, last_idx);
1042
1043         /* third step: detect, which functions are const or pure */
1044         DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1045         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1046                 ir_graph *irg = get_irp_irg(i);
1047                 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1048
1049                 if (prop & mtp_property_const) {
1050                         ++num_const;
1051                         DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1052                         check_for_possible_endless_loops(irg);
1053                 } else if (prop & mtp_property_pure) {
1054                         ++num_pure;
1055                         DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1056                 }
1057         }
1058
1059         if (force_run || num_const > 0) {
1060                 env_t ctx;
1061
1062                 handle_const_Calls(&ctx);
1063                 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1064                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1065                        ctx.n_calls_SymConst, ctx.n_calls_Sel));
1066         } else {
1067                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1068         }
1069         xfree(busy_set);
1070         xfree(ready_set);
1071 }  /* optimize_funccalls */
1072
1073 /* initialize the funccall optimization */
1074 void firm_init_funccalls(void) {
1075         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1076 }  /* firm_init_funccalls */
1077
1078 struct pass_t {
1079         ir_prog_pass_t          pass;
1080         int                     force_run;
1081         check_alloc_entity_func callback;
1082 };
1083
1084 /**
1085  * Wrapper for running optimize_funccalls() as an ir_prog pass.
1086  */
1087 static void pass_wrapper(ir_prog *irp, void *context)
1088 {
1089         struct pass_t *pass = context;
1090
1091         (void)irp;
1092         optimize_funccalls(pass->force_run, pass->callback);
1093 }  /* pass_wrapper */
1094
1095 /* Creates an ir_prog pass for optimize_funccalls. */
1096 ir_prog_pass_t *optimize_funccalls_pass(
1097         const char *name,
1098         int force_run, check_alloc_entity_func callback)
1099 {
1100         struct pass_t *pass = XMALLOCZ(struct pass_t);
1101
1102         pass->force_run = force_run;
1103         pass->callback  = callback;
1104
1105         return def_prog_pass_constructor(
1106                 &pass->pass, name ? name : "funccall", pass_wrapper);
1107 }  /* optimize_funccalls_pass */