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

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