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

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