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