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