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