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