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

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