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

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