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 "opt_init.h"
  29
  30 #include "irnode_t.h"
  31 #include "irgraph_t.h"
  32 #include "irgmod.h"
  33 #include "irgwalk.h"
  34 #include "dbginfo_t.h"
  35 #include "irflag_t.h"
  36 #include "irloop_t.h"
  37 #include "ircons.h"
  38 #include "iredges_t.h"
  39 #include "irpass_t.h"
  40 #include "iroptimize.h"
  41 #include "analyze_irg_args.h"
  42 #include "irhooks.h"
  43 #include "raw_bitset.h"
  44 #include "debug.h"
  45
  46 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  47
  48 /**
  49  * The walker environment for updating function calls.
  50  */
  51 typedef struct env_t {
  52         unsigned n_calls_SymConst;
  53         unsigned n_calls_Sel;
  54         ir_node  *float_const_call_list;    /**< The list of all floating const function calls that will be changed. */
  55         ir_node  *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
  56         ir_node  *pure_call_list;           /**< The list of all pure function calls that will be changed. */
  57         ir_node  *nothrow_call_list;        /**< The list of all nothrow function calls that will be changed. */
  58         ir_node  *proj_list;                /**< The list of all potential Proj nodes that must be fixed. */
  59 } env_t;
  60
  61 /** If non-null, evaluates entities for being a heap alloc. */
  62 static check_alloc_entity_func is_alloc_entity = NULL;
  63
  64 /** Ready IRG's are marked in the ready set. */
  65 static unsigned *ready_set;
  66
  67 /** IRG's that are in progress are marked here. */
  68 static unsigned *busy_set;
  69
  70 /**
  71  * We misuse the mtp_property_inherited flag as temporary here.
  72  * The is ok, as we cannot set or get it anyway using the
  73  * get_addtional_properties API.
  74  */
  75 #define mtp_temporary  mtp_property_inherited
  76
  77 /**
  78  * Walker: Collect all calls to const and pure functions
  79  * to lists. Collect all Proj(Call) nodes into a Proj list.
  80  */
  81 static void collect_const_and_pure_calls(ir_node *node, void *env)
  82 {
  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:
 158                 case pn_Call_X_except:
 159                 case pn_Call_X_regular:
 160                         set_irn_link(node, ctx->proj_list);
 161                         ctx->proj_list = node;
 162                         break;
 163                 default:
 164                         break;
 165                 }
 166         }
 167 }  /* collect_const_and_pure_calls */
 168
 169 /**
 170  * Fix the list of collected Calls.
 171  *
 172  * @param irg  the graph that contained calls to pure functions
 173  * @param ctx  context
 174  */
 175 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
 176 {
 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: {
 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                         exc_changed = 1;
 233                         exchange(proj, get_irg_bad(irg));
 234                         break;
 235                 case pn_Call_X_regular: {
 236                         ir_node *block = get_nodes_block(call);
 237                         exc_changed = 1;
 238                         exchange(proj, new_r_Jmp(block));
 239                         break;
 240                 }
 241                 default:
 242                         break;
 243                 }
 244         }
 245
 246         /* changes were done ... */
 247         set_irg_outs_inconsistent(irg);
 248         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 249
 250         if (exc_changed) {
 251                 /* ... including exception edges */
 252                 set_irg_doms_inconsistent(irg);
 253         }
 254         current_ir_graph = rem;
 255 }  /* fix_const_call_list */
 256
 257 /**
 258  * Walker: Collect all calls to nothrow functions
 259  * to lists. Collect all Proj(Call) nodes into a Proj list.
 260  */
 261 static void collect_nothrow_calls(ir_node *node, void *env)
 262 {
 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:
 324                 case pn_Call_X_except:
 325                 case pn_Call_X_regular:
 326                         set_irn_link(node, ctx->proj_list);
 327                         ctx->proj_list = node;
 328                         break;
 329                 default:
 330                         break;
 331                 }
 332         }
 333 }  /* collect_nothrow_calls */
 334
 335 /**
 336  * Fix the list of collected nothrow Calls.
 337  *
 338  * @param irg        the graph that contained calls to pure functions
 339  * @param call_list  the list of all call sites of const functions
 340  * @param proj_list  the list of all memory/exception Proj's of this call sites
 341  */
 342 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
 343 {
 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                         exc_changed = 1;
 372                         exchange(proj, get_irg_bad(irg));
 373                         break;
 374                 case pn_Call_X_regular: {
 375                         ir_node *block = get_nodes_block(call);
 376                         exc_changed = 1;
 377                         exchange(proj, new_r_Jmp(block));
 378                         break;
 379                 }
 380                 default:
 381                         break;
 382                 }
 383         }
 384
 385         /* changes were done ... */
 386         set_irg_outs_inconsistent(irg);
 387         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 388
 389         if (exc_changed) {
 390                 /* ... including exception edges */
 391                 set_irg_doms_inconsistent(irg);
 392         }
 393         current_ir_graph = rem;
 394 }  /* fix_nothrow_call_list */
 395
 396 /* marking */
 397 #define SET_IRG_READY(irg)  rbitset_set(ready_set, get_irg_idx(irg))
 398 #define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
 399 #define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
 400 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
 401 #define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
 402
 403 /* forward */
 404 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
 405
 406 /**
 407  * Calculate the bigger property of two. Handle the temporary flag right.
 408  */
 409 static unsigned max_property(unsigned a, unsigned b)
 410 {
 411         unsigned r, t = (a | b) & mtp_temporary;
 412         a &= ~mtp_temporary;
 413         b &= ~mtp_temporary;
 414
 415         if (a == mtp_no_property || b == mtp_no_property)
 416                 return mtp_no_property;
 417         r = a > b ? a : b;
 418         return r | t;
 419 }  /* max_property */
 420
 421 /**
 422  * Follow the memory chain starting at node and determine
 423  * the mtp_property.
 424  *
 425  * @return mtp_property_const if only calls of const functions are detected
 426  *         mtp_property_pure  if only Loads and const/pure calls detected
 427  *         mtp_no_property    else
 428  */
 429 static unsigned _follow_mem(ir_node *node)
 430 {
 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 {
 508         unsigned m;
 509
 510         m = _follow_mem(node);
 511         return max_property(mode, m);
 512 }  /* follow_mem */
 513
 514 /**
 515  * Check if a graph represents a const or a pure function.
 516  *
 517  * @param irg  the graph to check
 518  * @param top  if set, this is the top call
 519  */
 520 static unsigned check_const_or_pure_function(ir_graph *irg, int top)
 521 {
 522         ir_node *end, *endbl;
 523         int j;
 524         unsigned prop = get_irg_additional_properties(irg);
 525         ir_graph *rem = current_ir_graph;
 526
 527         if (prop & mtp_property_const) {
 528                 /* already marked as a const function */
 529                 return mtp_property_const;
 530         }
 531         if (prop & mtp_property_pure) {
 532                 /* already marked as a pure function */
 533                 return mtp_property_pure;
 534         }
 535
 536         if (IS_IRG_READY(irg)) {
 537                 /* already checked */
 538                 return mtp_no_property;
 539         }
 540         if (IS_IRG_BUSY(irg)) {
 541                 /* we are still evaluate this method. Be optimistic,
 542                    return the best possible so far but mark the result as temporary. */
 543                 return mtp_temporary | mtp_property_const;
 544         }
 545         SET_IRG_BUSY(irg);
 546
 547         end   = get_irg_end(irg);
 548         endbl = get_nodes_block(end);
 549         prop  = mtp_property_const;
 550
 551         current_ir_graph = irg;
 552
 553         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 554         inc_irg_visited(irg);
 555         /* mark the initial mem: recursion of follow_mem() stops here */
 556         mark_irn_visited(get_irg_initial_mem(irg));
 557
 558         /* visit every Return */
 559         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 560                 ir_node   *node = get_Block_cfgpred(endbl, j);
 561                 ir_opcode code  = get_irn_opcode(node);
 562                 ir_node   *mem;
 563
 564                 /* Bad nodes usually do NOT produce anything, so it's ok */
 565                 if (code == iro_Bad)
 566                         continue;
 567
 568                 if (code == iro_Return) {
 569                         mem = get_Return_mem(node);
 570
 571                         /* Bad nodes usually do NOT produce anything, so it's ok */
 572                         if (is_Bad(mem))
 573                                 continue;
 574
 575                         if (mem != get_irg_initial_mem(irg))
 576                                 prop = max_property(prop, follow_mem(mem, prop));
 577                 } else {
 578                         /* Exception found. Cannot be const or pure. */
 579                         prop = mtp_no_property;
 580                         break;
 581                 }
 582                 if (prop == mtp_no_property)
 583                         break;
 584         }
 585
 586         if (prop != mtp_no_property) {
 587                 /* check, if a keep-alive exists */
 588                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 589                         ir_node *kept = get_End_keepalive(end, j);
 590
 591                         if (is_Block(kept)) {
 592                                 prop = mtp_no_property;
 593                                 break;
 594                         }
 595
 596                         if (mode_M != get_irn_mode(kept))
 597                                 continue;
 598
 599                         prop = max_property(prop, follow_mem(kept, prop));
 600                         if (prop == mtp_no_property)
 601                                 break;
 602                 }
 603         }
 604
 605         if (prop != mtp_no_property) {
 606                 if (top || (prop & mtp_temporary) == 0) {
 607                         /* We use the temporary flag here to mark optimistic result.
 608                            Set the property only if we are sure that it does NOT base on
 609                            temporary results OR if we are at top-level. */
 610                         set_irg_additional_property(irg, prop & ~mtp_temporary);
 611                         SET_IRG_READY(irg);
 612                 }
 613         }
 614         if (top)
 615                 SET_IRG_READY(irg);
 616         CLEAR_IRG_BUSY(irg);
 617         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 618         current_ir_graph = rem;
 619         return prop;
 620 }  /* check_const_or_pure_function */
 621
 622 /**
 623  * Handle calls to const functions.
 624  *
 625  * @param ctx  context
 626  */
 627 static void handle_const_Calls(env_t *ctx)
 628 {
 629         int i;
 630
 631         ctx->n_calls_SymConst = 0;
 632         ctx->n_calls_Sel      = 0;
 633
 634         /* all calls of const functions can be transformed */
 635         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 636                 ir_graph *irg  = get_irp_irg(i);
 637
 638                 ctx->float_const_call_list    = NULL;
 639                 ctx->nonfloat_const_call_list = NULL;
 640                 ctx->pure_call_list           = NULL;
 641                 ctx->proj_list                = NULL;
 642
 643                 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 644                 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
 645
 646                 if (ctx->float_const_call_list != NULL)
 647                         fix_const_call_lists(irg, ctx);
 648                 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 649         }
 650 }  /* handle_const_Calls */
 651
 652 /**
 653  * Handle calls to nothrow functions.
 654  *
 655  * @param ctx  context
 656  */
 657 static void handle_nothrow_Calls(env_t *ctx)
 658 {
 659         int i;
 660
 661         ctx->n_calls_SymConst = 0;
 662         ctx->n_calls_Sel      = 0;
 663
 664         /* all calls of const functions can be transformed */
 665         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 666                 ir_graph *irg  = get_irp_irg(i);
 667
 668                 ctx->nothrow_call_list = NULL;
 669                 ctx->proj_list         = NULL;
 670
 671                 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 672                 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
 673
 674                 if (ctx->nothrow_call_list)
 675                         fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
 676                 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 677         }
 678 }
 679
 680 /**
 681  * Check, whether a given node represents a return value of
 682  * a malloc like function (ie, new heap allocated memory).
 683  *
 684  * @param node  the node to check
 685  */
 686 static int is_malloc_call_result(const ir_node *node)
 687 {
 688         if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
 689                 /* Firm style high-level allocation */
 690                 return 1;
 691         }
 692         if (is_alloc_entity != NULL && is_Call(node)) {
 693                 ir_node *ptr = get_Call_ptr(node);
 694
 695                 if (is_Global(ptr)) {
 696                         ir_entity *ent = get_Global_entity(ptr);
 697                         return is_alloc_entity(ent);
 698                 }
 699         }
 700         return 0;
 701 }  /* is_malloc_call_result */
 702
 703 /**
 704  * Update a property depending on a call property.
 705  */
 706 static unsigned update_property(unsigned orig_prop, unsigned call_prop)
 707 {
 708         unsigned t = (orig_prop | call_prop) & mtp_temporary;
 709         unsigned r = orig_prop & call_prop;
 710         return r | t;
 711 }  /** update_property */
 712
 713 /**
 714  * Check if a node is stored.
 715  */
 716 static int is_stored(const ir_node *n)
 717 {
 718         const ir_edge_t *edge;
 719         const ir_node   *ptr;
 720
 721         foreach_out_edge(n, edge) {
 722                 const ir_node *succ = get_edge_src_irn(edge);
 723
 724                 switch (get_irn_opcode(succ)) {
 725                 case iro_Return:
 726                 case iro_Load:
 727                 case iro_Cmp:
 728                         /* ok */
 729                         break;
 730                 case iro_Store:
 731                         if (get_Store_value(succ) == n)
 732                                 return 1;
 733                         /* ok if its only the address input */
 734                         break;
 735                 case iro_Sel:
 736                 case iro_Cast:
 737                 case iro_Confirm:
 738                         if (is_stored(succ))
 739                                 return 1;
 740                         break;
 741                 case iro_Call:
 742                         ptr = get_Call_ptr(succ);
 743                         if (is_Global(ptr)) {
 744                                 ir_entity *ent = get_Global_entity(ptr);
 745                                 int       i;
 746
 747                                 /* we know the called entity */
 748                                 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
 749                                         if (get_Call_param(succ, i) == n) {
 750                                                 /* n is the i'th param of the call */
 751                                                 if (get_method_param_access(ent, i) & ptr_access_store) {
 752                                                         /* n is store in ent */
 753                                                         return 1;
 754                                                 }
 755                                         }
 756                                 }
 757                         } else {
 758                                 /* unknown call address */
 759                                 return 1;
 760                         }
 761                         break;
 762                 default:
 763                         /* bad, potential alias */
 764                         return 1;
 765                 }
 766         }
 767         return 0;
 768 }  /* is_stored */
 769
 770 /**
 771  * Check that the return value of an irg is not stored anywhere.
 772  *
 773  * return ~mtp_property_malloc if return values are stored, ~0 else
 774  */
 775 static unsigned check_stored_result(ir_graph *irg)
 776 {
 777         ir_node  *end_blk = get_irg_end_block(irg);
 778         int      i, j;
 779         unsigned res = ~0;
 780         int      old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
 781
 782         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 783                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 784
 785                 if (! is_Return(pred))
 786                         continue;
 787                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 788                         const ir_node *irn = get_Return_res(pred, j);
 789
 790                         if (is_stored(irn)) {
 791                                 /* bad, might create an alias */
 792                                 res = ~mtp_property_malloc;
 793                                 goto finish;
 794                         }
 795                 }
 796         }
 797 finish:
 798         if (! old_edges)
 799                 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 800         return res;
 801 }  /* check_stored_result */
 802
 803 /**
 804  * Check if a graph represents a nothrow or a malloc function.
 805  *
 806  * @param irg  the graph to check
 807  * @param top  if set, this is the top call
 808  */
 809 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top)
 810 {
 811         ir_node   *end_blk = get_irg_end_block(irg);
 812         ir_entity *ent;
 813         ir_type   *mtp;
 814         int       i, j;
 815         unsigned  curr_prop = mtp_property_malloc | mtp_property_nothrow;
 816
 817         if (IS_IRG_READY(irg)) {
 818                 /* already checked */
 819                 return get_irg_additional_properties(irg);
 820         }
 821         if (IS_IRG_BUSY(irg)) {
 822                 /* we are still evaluate this method. Be optimistic,
 823                 return the best possible so far but mark the result as temporary. */
 824                 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
 825         }
 826         SET_IRG_BUSY(irg);
 827
 828         ent = get_irg_entity(irg);
 829         mtp = get_entity_type(ent);
 830
 831         if (get_method_n_ress(mtp) <= 0)
 832                 curr_prop &= ~mtp_property_malloc;
 833
 834         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 835                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 836
 837                 if (is_Return(pred)) {
 838                         if (curr_prop & mtp_property_malloc) {
 839                                 /* check, if malloc is called here */
 840                                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 841                                         ir_node *res = get_Return_res(pred, j);
 842
 843                                         /* skip Confirms and Casts */
 844                                         res = skip_HighLevel_ops(res);
 845                                         /* skip Proj's */
 846                                         while (is_Proj(res))
 847                                                 res = get_Proj_pred(res);
 848                                         if (is_malloc_call_result(res)) {
 849                                                 /* ok, this is a malloc */
 850                                         } else if (is_Call(res)) {
 851                                                 ir_node *ptr = get_Call_ptr(res);
 852
 853                                                 if (is_Global(ptr)) {
 854                                                         /* a direct call */
 855                                                         ir_entity *ent    = get_Global_entity(ptr);
 856                                                         ir_graph  *callee = get_entity_irg(ent);
 857
 858                                                         if (callee == irg) {
 859                                                                 /* A self-recursive call. The property did not depend on this call. */
 860                                                         } else if (callee != NULL) {
 861                                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
 862                                                                 curr_prop = update_property(curr_prop, prop);
 863                                                         } else {
 864                                                                 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
 865                                                         }
 866                                                 } else if (get_opt_closed_world() &&
 867                                                            is_Sel(ptr) &&
 868                                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 869                                                         /* check if all possible callees are malloc functions. */
 870                                                         int i, n_callees = get_Call_n_callees(res);
 871                                                         if (n_callees == 0) {
 872                                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 873                                                                    when executed as there is no implementation to call.  So better not
 874                                                                    optimize. */
 875                                                                 curr_prop &= ~mtp_property_malloc;
 876                                                                 continue;
 877                                                         }
 878
 879                                                         for (i = 0; i < n_callees; ++i) {
 880                                                                 ir_entity *ent = get_Call_callee(res, i);
 881                                                                 if (ent == unknown_entity) {
 882                                                                         /* we don't know which entity is called here */
 883                                                                         curr_prop &= ~mtp_property_malloc;
 884                                                                         break;
 885                                                                 }
 886                                                                 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
 887                                                                         curr_prop &= ~mtp_property_malloc;
 888                                                                         break;
 889                                                                 }
 890                                                         }
 891                                                         /* if we pass the for cycle, malloc is still ok */
 892                                                 } else {
 893                                                         /* unknown call */
 894                                                         curr_prop &= ~mtp_property_malloc;
 895                                                 }
 896                                         } else {
 897                                                 /* unknown return value */
 898                                                 curr_prop &= ~mtp_property_malloc;
 899                                         }
 900                                 }
 901                         }
 902                 } else if (curr_prop & mtp_property_nothrow) {
 903                         /* exception flow detected */
 904                         pred = skip_Proj(pred);
 905
 906                         if (is_Call(pred)) {
 907                                 ir_node *ptr = get_Call_ptr(pred);
 908
 909                                 if (is_Global(ptr)) {
 910                                         /* a direct call */
 911                                         ir_entity *ent    = get_Global_entity(ptr);
 912                                         ir_graph  *callee = get_entity_irg(ent);
 913
 914                                         if (callee == irg) {
 915                                                 /* A self-recursive call. The property did not depend on this call. */
 916                                         } else if (callee != NULL) {
 917                                                 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
 918                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
 919                                                 curr_prop = update_property(curr_prop, prop);
 920                                         } else {
 921                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
 922                                                         curr_prop &= ~mtp_property_nothrow;
 923                                         }
 924                                 } else if (get_opt_closed_world() &&
 925                                            is_Sel(ptr) &&
 926                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 927                                         /* check if all possible callees are nothrow functions. */
 928                                         int i, n_callees = get_Call_n_callees(pred);
 929                                         if (n_callees == 0) {
 930                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 931                                                    when executed as there is no implementation to call.  So better not
 932                                                    optimize. */
 933                                                 curr_prop &= ~mtp_property_nothrow;
 934                                                 continue;
 935                                         }
 936
 937                                         for (i = 0; i < n_callees; ++i) {
 938                                                 ir_entity *ent = get_Call_callee(pred, i);
 939                                                 if (ent == unknown_entity) {
 940                                                         /* we don't know which entity is called here */
 941                                                         curr_prop &= ~mtp_property_nothrow;
 942                                                         break;
 943                                                 }
 944                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
 945                                                         curr_prop &= ~mtp_property_nothrow;
 946                                                         break;
 947                                                 }
 948                                         }
 949                                         /* if we pass the for cycle, nothrow is still ok */
 950                                 } else {
 951                                         /* unknown call */
 952                                         curr_prop &= ~mtp_property_nothrow;
 953                                 }
 954                         } else {
 955                                 /* real exception flow possible. */
 956                                 curr_prop &= ~mtp_property_nothrow;
 957                         }
 958                 }
 959                 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
 960                         /* no need to search further */
 961                         break;
 962                 }
 963         }
 964
 965         if (curr_prop & mtp_property_malloc) {
 966                 /*
 967                  * Note that the malloc property means not only return newly allocated
 968                  * memory, but also that this memory is ALIAS FREE.
 969                  * To ensure that, we do NOT allow that the returned memory is somewhere
 970                  * stored.
 971              */
 972                 curr_prop &= check_stored_result(irg);
 973         }
 974
 975         if (curr_prop != mtp_no_property) {
 976                 if (top || (curr_prop & mtp_temporary) == 0) {
 977                         /* We use the temporary flag here to mark an optimistic result.
 978                            Set the property only if we are sure that it does NOT base on
 979                            temporary results OR if we are at top-level. */
 980                         set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
 981                         SET_IRG_READY(irg);
 982                 }
 983         }
 984         if (top)
 985                 SET_IRG_READY(irg);
 986         CLEAR_IRG_BUSY(irg);
 987         return curr_prop;
 988 }  /* check_nothrow_or_malloc */
 989
 990 /**
 991  * When a function was detected as "const", it might be moved out of loops.
 992  * This might be dangerous if the graph can contain endless loops.
 993  */
 994 static void check_for_possible_endless_loops(ir_graph *irg)
 995 {
 996         ir_loop *root_loop;
 997         assure_cf_loop(irg);
 998
 999         root_loop = get_irg_loop(irg);
1000         if (root_loop->flags & loop_outer_loop)
1001                 set_irg_additional_property(irg, mtp_property_has_loop);
1002 }
1003
1004 /*
1005  * optimize function calls by handling const functions
1006  */
1007 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
1008 {
1009         int i, last_idx;
1010         unsigned num_const   = 0;
1011         unsigned num_pure    = 0;
1012         unsigned num_nothrow = 0;
1013         unsigned num_malloc  = 0;
1014
1015         is_alloc_entity = callback;
1016
1017         /* prepare: mark all graphs as not analyzed */
1018         last_idx  = get_irp_last_idx();
1019         ready_set = rbitset_malloc(last_idx);
1020         busy_set  = rbitset_malloc(last_idx);
1021
1022         /* first step: detect, which functions are nothrow or malloc */
1023         DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1024         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1025                 ir_graph *irg = get_irp_irg(i);
1026                 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1027
1028                 if (prop & mtp_property_nothrow) {
1029                         ++num_nothrow;
1030                         DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1031                 } else if (prop & mtp_property_malloc) {
1032                         ++num_malloc;
1033                         DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1034                 }
1035         }
1036
1037         /* second step: remove exception edges: this must be done before the
1038            detection of const and pure functions take place. */
1039         if (force_run || num_nothrow > 0) {
1040                 env_t ctx;
1041
1042                 handle_nothrow_Calls(&ctx);
1043                 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1044                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1045                         ctx.n_calls_SymConst, ctx.n_calls_Sel));
1046         } else {
1047                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1048         }
1049
1050         rbitset_clear_all(ready_set, last_idx);
1051         rbitset_clear_all(busy_set, last_idx);
1052
1053         /* third step: detect, which functions are const or pure */
1054         DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1055         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1056                 ir_graph *irg = get_irp_irg(i);
1057                 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1058
1059                 if (prop & mtp_property_const) {
1060                         ++num_const;
1061                         DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1062                         check_for_possible_endless_loops(irg);
1063                 } else if (prop & mtp_property_pure) {
1064                         ++num_pure;
1065                         DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1066                 }
1067         }
1068
1069         if (force_run || num_const > 0) {
1070                 env_t ctx;
1071
1072                 handle_const_Calls(&ctx);
1073                 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1074                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1075                        ctx.n_calls_SymConst, ctx.n_calls_Sel));
1076         } else {
1077                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1078         }
1079         xfree(busy_set);
1080         xfree(ready_set);
1081 }  /* optimize_funccalls */
1082
1083 /* initialize the funccall optimization */
1084 void firm_init_funccalls(void)
1085 {
1086         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1087 }  /* firm_init_funccalls */
1088
1089 struct pass_t {
1090         ir_prog_pass_t          pass;
1091         int                     force_run;
1092         check_alloc_entity_func callback;
1093 };
1094
1095 /**
1096  * Wrapper for running optimize_funccalls() as an ir_prog pass.
1097  */
1098 static int pass_wrapper(ir_prog *irp, void *context)
1099 {
1100         struct pass_t *pass = context;
1101
1102         (void)irp;
1103         optimize_funccalls(pass->force_run, pass->callback);
1104         return 0;
1105 }  /* pass_wrapper */
1106
1107 /* Creates an ir_prog pass for optimize_funccalls. */
1108 ir_prog_pass_t *optimize_funccalls_pass(
1109         const char *name,
1110         int force_run, check_alloc_entity_func callback)
1111 {
1112         struct pass_t *pass = XMALLOCZ(struct pass_t);
1113
1114         pass->force_run = force_run;
1115         pass->callback  = callback;
1116
1117         return def_prog_pass_constructor(
1118                 &pass->pass, name ? name : "funccall", pass_wrapper);
1119 }  /* optimize_funccalls_pass */