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

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