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 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include <adt/raw_bitset.h>
  31
  32 #include "funccall_t.h"
  33
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "irgmod.h"
  37 #include "irgwalk.h"
  38 #include "irvrfy.h"
  39 #include "dbginfo_t.h"
  40 #include "irflag_t.h"
  41 #include "irloop_t.h"
  42 #include "ircons.h"
  43 #include "iredges_t.h"
  44 #include "analyze_irg_args.h"
  45 #include "irhooks.h"
  46 #include "debug.h"
  47
  48 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  49
  50 /**
  51  * The walker environment for updating function calls.
  52  */
  53 typedef struct _env_t {
  54         unsigned n_calls_SymConst;
  55         unsigned n_calls_Sel;
  56         ir_node  *float_const_call_list;    /**< The list of all floating const function calls that will be changed. */
  57         ir_node  *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
  58         ir_node  *pure_call_list;           /**< The list of all pure function calls that will be changed. */
  59         ir_node  *nothrow_call_list;        /**< The list of all nothrow function calls that will be changed. */
  60         ir_node  *proj_list;                /**< The list of all potential Proj nodes that must be fixed. */
  61 } env_t;
  62
  63 /** If non-null, evaluates entities for being a heap alloc. */
  64 static check_alloc_entity_func is_alloc_entity = NULL;
  65
  66 /** Ready IRG's are marked in the ready set. */
  67 static unsigned *ready_set;
  68
  69 /** IRG's that are in progress are marked here. */
  70 static unsigned *busy_set;
  71
  72 /**
  73  * We misuse the mtp_property_inherited flag as temporary here.
  74  * The is ok, as we cannot set or get it anyway using the
  75  * get_addtional_properties API.
  76  */
  77 #define mtp_temporary  mtp_property_inherited
  78
  79 /**
  80  * Walker: Collect all calls to const and pure functions
  81  * to lists. Collect all Proj(Call) nodes into a Proj list.
  82  */
  83 static void collect_const_and_pure_calls(ir_node *node, void *env) {
  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_regular:
 159                 case pn_Call_X_except:
 160                 case pn_Call_X_regular:
 161                 case pn_Call_M_except:
 162                         set_irn_link(node, ctx->proj_list);
 163                         ctx->proj_list = node;
 164                         break;
 165                 default:
 166                         break;
 167                 }
 168         }
 169 }  /* collect_const_and_pure_calls */
 170
 171 /**
 172  * Fix the list of collected Calls.
 173  *
 174  * @param irg  the graph that contained calls to pure functions
 175  * @param ctx  context
 176  */
 177 static void fix_const_call_lists(ir_graph *irg, env_t *ctx) {
 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_regular: {
 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                 case pn_Call_M_except:
 234                         exc_changed = 1;
 235                         exchange(proj, get_irg_bad(irg));
 236                         break;
 237                 case pn_Call_X_regular: {
 238                         ir_node *block = get_nodes_block(call);
 239                         exc_changed = 1;
 240                         exchange(proj, new_r_Jmp(irg, block));
 241                         break;
 242                 }
 243                 default:
 244                         ;
 245                 }
 246         }
 247
 248         /* changes were done ... */
 249         set_irg_outs_inconsistent(irg);
 250         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 251
 252         if (exc_changed) {
 253                 /* ... including exception edges */
 254                 set_irg_doms_inconsistent(irg);
 255         }
 256         current_ir_graph = rem;
 257 }  /* fix_const_call_list */
 258
 259 /**
 260  * Walker: Collect all calls to nothrow functions
 261  * to lists. Collect all Proj(Call) nodes into a Proj list.
 262  */
 263 static void collect_nothrow_calls(ir_node *node, void *env) {
 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_regular:
 325                 case pn_Call_X_except:
 326                 case pn_Call_X_regular:
 327                 case pn_Call_M_except:
 328                         set_irn_link(node, ctx->proj_list);
 329                         ctx->proj_list = node;
 330                         break;
 331                 default:
 332                         break;
 333                 }
 334         }
 335 }  /* collect_nothrow_calls */
 336
 337 /**
 338  * Fix the list of collected nothrow Calls.
 339  *
 340  * @param irg        the graph that contained calls to pure functions
 341  * @param call_list  the list of all call sites of const functions
 342  * @param proj_list  the list of all memory/exception Proj's of this call sites
 343  */
 344 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) {
 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                 case pn_Call_M_except:
 373                         exc_changed = 1;
 374                         exchange(proj, get_irg_bad(irg));
 375                         break;
 376                 case pn_Call_X_regular: {
 377                         ir_node *block = get_nodes_block(call);
 378                         exc_changed = 1;
 379                         exchange(proj, new_r_Jmp(irg, block));
 380                         break;
 381                 }
 382                 default:
 383                         ;
 384                 }
 385         }
 386
 387         /* changes were done ... */
 388         set_irg_outs_inconsistent(irg);
 389         set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
 390
 391         if (exc_changed) {
 392                 /* ... including exception edges */
 393                 set_irg_doms_inconsistent(irg);
 394         }
 395         current_ir_graph = rem;
 396 }  /* fix_nothrow_call_list */
 397
 398 /* marking */
 399 #define SET_IRG_READY(irg)      rbitset_set(ready_set, get_irg_idx(irg))
 400 #define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
 401 #define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
 402 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
 403 #define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
 404
 405 /* forward */
 406 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
 407 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top);
 408
 409 /**
 410  * Calculate the bigger property of two. Handle the temporary flag right.
 411  */
 412 static unsigned max_property(unsigned a, unsigned b) {
 413         unsigned r, t = (a | b) & mtp_temporary;
 414         a &= ~mtp_temporary;
 415         b &= ~mtp_temporary;
 416
 417         if (a == mtp_no_property || b == mtp_no_property)
 418                 return mtp_no_property;
 419         r = a > b ? a : b;
 420         return r | t;
 421 }  /* max_property */
 422
 423 /**
 424  * Follow the memory chain starting at node and determine
 425  * the mtp_property.
 426  *
 427  * @return mtp_property_const if only calls of const functions are detected
 428  *         mtp_property_pure if only Loads and const/pure
 429  *         calls detected
 430  *         mtp_no_property else
 431  */
 432 static unsigned _follow_mem(ir_node *node) {
 433         unsigned m, mode = mtp_property_const;
 434         ir_node  *ptr;
 435         int i;
 436
 437         for (;;) {
 438                 if (mode == mtp_no_property)
 439                         return mtp_no_property;
 440
 441                 if (irn_visited(node))
 442                         return mode;
 443
 444                 mark_irn_visited(node);
 445
 446                 switch (get_irn_opcode(node)) {
 447                 case iro_Proj:
 448                         node = get_Proj_pred(node);
 449                         break;
 450
 451                 case iro_NoMem:
 452                         /* finish here */
 453                         return mode;
 454
 455                 case iro_Phi:
 456                 case iro_Sync:
 457                         /* do a dfs search */
 458                         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 459                                 m    = _follow_mem(get_irn_n(node, i));
 460                                 mode = max_property(mode, m);
 461                                 if (mode == mtp_no_property)
 462                                         return mtp_no_property;
 463                         }
 464                         return mode;
 465
 466                 case iro_Load:
 467                         /* Beware volatile Loads are NOT allowed in pure functions. */
 468                         if (get_Load_volatility(node) == volatility_is_volatile)
 469                                 return mtp_no_property;
 470                         mode = max_property(mode, mtp_property_pure);
 471                         node = get_Load_mem(node);
 472                         break;
 473
 474                 case iro_Call:
 475                         /* A call is only tolerable if its either constant or pure. */
 476                         ptr = get_Call_ptr(node);
 477                         if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
 478                                 ir_entity *ent = get_SymConst_entity(ptr);
 479                                 ir_graph  *irg = get_entity_irg(ent);
 480
 481                                 if (irg == current_ir_graph) {
 482                                         /* A self-recursive call. The property did not depend on this call. */
 483                                 } else if (irg == NULL) {
 484                                         m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
 485                                         mode = max_property(mode, m);
 486                                 } else if (irg != NULL) {
 487                                         /* we have a graph, analyze it. */
 488                                         m = check_const_or_pure_function(irg, /*top=*/0);
 489                                         mode = max_property(mode, m);
 490                                 }
 491                         } else
 492                                 return mtp_no_property;
 493                         node = get_Call_mem(node);
 494                         break;
 495
 496                 default:
 497                         return mtp_no_property;
 498                 }
 499         }
 500 }  /* _follow_mem */
 501
 502 /**
 503  * Follow the memory chain starting at node and determine
 504  * the mtp_property.
 505  *
 506  * @return mtp_property_const if only calls of const functions are detected
 507  *         mtp_property_pure  if only Loads and const/pure calls detected
 508  *         mtp_no_property else
 509  */
 510 static unsigned follow_mem(ir_node *node, unsigned mode) {
 511         unsigned m;
 512
 513         m = _follow_mem(node);
 514         return max_property(mode, m);
 515 }  /* follow_mem */
 516
 517 /**
 518  * Check if a graph represents a const or a pure function.
 519  *
 520  * @param irg  the graph to check
 521  * @param top  if set, this is the top call
 522  */
 523 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 524         ir_node *end, *endbl;
 525         int j;
 526         unsigned prop = get_irg_additional_properties(irg);
 527         ir_graph *rem = current_ir_graph;
 528
 529         if (prop & mtp_property_const) {
 530                 /* already marked as a const function */
 531                 return mtp_property_const;
 532         }
 533         if (prop & mtp_property_pure) {
 534                 /* already marked as a pure function */
 535                 return mtp_property_pure;
 536         }
 537
 538         if (IS_IRG_READY(irg)) {
 539                 /* already checked */
 540                 return mtp_no_property;
 541         }
 542         if (IS_IRG_BUSY(irg)) {
 543                 /* we are still evaluate this method. Be optimistic,
 544                    return the best possible so far but mark the result as temporary. */
 545                 return mtp_temporary | mtp_property_const;
 546         }
 547         SET_IRG_BUSY(irg);
 548
 549         end   = get_irg_end(irg);
 550         endbl = get_nodes_block(end);
 551         prop  = mtp_property_const;
 552
 553         current_ir_graph = irg;
 554
 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         current_ir_graph = rem;
 619         return prop;
 620 }  /* check_const_or_pure_function */
 621
 622 /**
 623  * Handle calls to const functions.
 624  *
 625  * @param ctx  context
 626  */
 627 static void handle_const_Calls(env_t *ctx) {
 628         int i;
 629
 630         ctx->n_calls_SymConst = 0;
 631         ctx->n_calls_Sel      = 0;
 632
 633         /* all calls of const functions can be transformed */
 634         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 635                 ir_graph *irg  = get_irp_irg(i);
 636
 637                 ctx->float_const_call_list    = NULL;
 638                 ctx->nonfloat_const_call_list = NULL;
 639                 ctx->pure_call_list           = NULL;
 640                 ctx->proj_list                = NULL;
 641                 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
 642
 643                 if (ctx->float_const_call_list != NULL) {
 644                         fix_const_call_lists(irg, ctx);
 645
 646                         /* this graph was changed, invalidate analysis info */
 647                         set_irg_outs_inconsistent(irg);
 648                         set_irg_doms_inconsistent(irg);
 649                 }
 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         int i;
 660
 661         ctx->n_calls_SymConst = 0;
 662         ctx->n_calls_Sel      = 0;
 663
 664         /* all calls of const functions can be transformed */
 665         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 666                 ir_graph *irg  = get_irp_irg(i);
 667
 668                 ctx->nothrow_call_list = NULL;
 669                 ctx->proj_list         = NULL;
 670                 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
 671
 672                 if (ctx->nothrow_call_list) {
 673                         fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
 674
 675                         /* this graph was changed, invalidate analysis info */
 676                         set_irg_outs_inconsistent(irg);
 677                         set_irg_doms_inconsistent(irg);
 678                 }
 679         }
 680 }
 681
 682 /**
 683  * Check, whether a given node represents a return value of
 684  * a malloc like function (ie, new heap allocated memory).
 685  *
 686  * @param node  the node to check
 687  */
 688 static int is_malloc_call_result(const ir_node *node) {
 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         unsigned t = (orig_prop | call_prop) & mtp_temporary;
 709         unsigned r = orig_prop & call_prop;
 710         return r | t;
 711 }  /** update_property */
 712
 713 /**
 714  * Check if a node is stored.
 715  */
 716 static int is_stored(const ir_node *n) {
 717         const ir_edge_t *edge;
 718         const ir_node   *ptr;
 719
 720         foreach_out_edge(n, edge) {
 721                 const ir_node *succ = get_edge_src_irn(edge);
 722
 723                 switch (get_irn_opcode(succ)) {
 724                 case iro_Return:
 725                 case iro_Load:
 726                 case iro_Cmp:
 727                         /* ok */
 728                         break;
 729                 case iro_Store:
 730                         if (get_Store_value(succ) == n)
 731                                 return 1;
 732                         /* ok if its only the address input */
 733                         break;
 734                 case iro_Sel:
 735                 case iro_Cast:
 736                 case iro_Confirm:
 737                         if (is_stored(succ))
 738                                 return 1;
 739                         break;
 740                 case iro_Call:
 741                         ptr = get_Call_ptr(succ);
 742                         if (is_Global(ptr)) {
 743                                 ir_entity *ent = get_Global_entity(ptr);
 744                                 int       i;
 745
 746                                 /* we know the called entity */
 747                                 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
 748                                         if (get_Call_param(succ, i) == n) {
 749                                                 /* n is the i'th param of the call */
 750                                                 if (get_method_param_access(ent, i) & ptr_access_store) {
 751                                                         /* n is store in ent */
 752                                                         return 1;
 753                                                 }
 754                                         }
 755                                 }
 756                         } else {
 757                                 /* unknown call address */
 758                                 return 1;
 759                         }
 760                         break;
 761                 default:
 762                         /* bad, potential alias */
 763                         return 1;
 764                 }
 765         }
 766         return 0;
 767 }  /* is_stored */
 768
 769 /**
 770  * Check that the return value of an irg is not stored anywhere.
 771  *
 772  * return ~mtp_property_malloc if return values are stored, ~0 else
 773  */
 774 static unsigned check_stored_result(ir_graph *irg) {
 775         ir_node  *end_blk = get_irg_end_block(irg);
 776         int      i, j;
 777         unsigned res = ~0;
 778         int      old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
 779
 780         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 781                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 782
 783                 if (! is_Return(pred))
 784                         continue;
 785                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 786                         const ir_node *irn = get_Return_res(pred, j);
 787
 788                         if (is_stored(irn)) {
 789                                 /* bad, might create an alias */
 790                                 res = ~mtp_property_malloc;
 791                                 goto finish;
 792                         }
 793                 }
 794         }
 795 finish:
 796         if (! old_edges)
 797                 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 798         return res;
 799 }  /* check_stored_result */
 800
 801 /**
 802  * Check if a graph represents a nothrow or a malloc function.
 803  *
 804  * @param irg  the graph to check
 805  * @param top  if set, this is the top call
 806  */
 807 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) {
 808         ir_node   *end_blk = get_irg_end_block(irg);
 809         ir_entity *ent;
 810         ir_type   *mtp;
 811         int       i, j;
 812         unsigned  curr_prop = mtp_property_malloc | mtp_property_nothrow;
 813
 814         if (IS_IRG_READY(irg)) {
 815                 /* already checked */
 816                 return get_irg_additional_properties(irg);
 817         }
 818         if (IS_IRG_BUSY(irg)) {
 819                 /* we are still evaluate this method. Be optimistic,
 820                 return the best possible so far but mark the result as temporary. */
 821                 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
 822         }
 823         SET_IRG_BUSY(irg);
 824
 825         ent = get_irg_entity(irg);
 826         mtp = get_entity_type(ent);
 827
 828         if (get_method_n_ress(mtp) <= 0)
 829                 curr_prop &= ~mtp_property_malloc;
 830
 831         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 832                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 833
 834                 if (is_Return(pred)) {
 835                         if (curr_prop & mtp_property_malloc) {
 836                                 /* check, if malloc is called here */
 837                                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 838                                         ir_node *res = get_Return_res(pred, j);
 839
 840                                         /* skip Confirms and Casts */
 841                                         res = skip_HighLevel_ops(res);
 842                                         /* skip Proj's */
 843                                         while (is_Proj(res))
 844                                                 res = get_Proj_pred(res);
 845                                         if (is_malloc_call_result(res)) {
 846                                                 /* ok, this is a malloc */
 847                                         } else if (is_Call(res)) {
 848                                                 ir_node *ptr = get_Call_ptr(res);
 849
 850                                                 if (is_Global(ptr)) {
 851                                                         /* a direct call */
 852                                                         ir_entity *ent    = get_Global_entity(ptr);
 853                                                         ir_graph  *callee = get_entity_irg(ent);
 854
 855                                                         if (callee == irg) {
 856                                                                 /* A self-recursive call. The property did not depend on this call. */
 857                                                         } else if (callee != NULL) {
 858                                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
 859                                                                 curr_prop = update_property(curr_prop, prop);
 860                                                         } else {
 861                                                                 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
 862                                                         }
 863                                                 } else if (get_opt_closed_world() &&
 864                                                            is_Sel(ptr) &&
 865                                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 866                                                         /* check if all possible callees are malloc functions. */
 867                                                         int i, n_callees = get_Call_n_callees(res);
 868                                                         if (n_callees == 0) {
 869                                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 870                                                                    when executed as there is no implementation to call.  So better not
 871                                                                    optimize. */
 872                                                                 curr_prop &= ~mtp_property_malloc;
 873                                                                 continue;
 874                                                         }
 875
 876                                                         for (i = 0; i < n_callees; ++i) {
 877                                                                 ir_entity *ent = get_Call_callee(res, i);
 878                                                                 if (ent == unknown_entity) {
 879                                                                         /* we don't know which entity is called here */
 880                                                                         curr_prop &= ~mtp_property_malloc;
 881                                                                         break;
 882                                                                 }
 883                                                                 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
 884                                                                         curr_prop &= ~mtp_property_malloc;
 885                                                                         break;
 886                                                                 }
 887                                                         }
 888                                                         /* if we pass the for cycle, malloc is still ok */
 889                                                 } else {
 890                                                         /* unknown call */
 891                                                         curr_prop &= ~mtp_property_malloc;
 892                                                 }
 893                                         } else {
 894                                                 /* unknown return value */
 895                                                 curr_prop &= ~mtp_property_malloc;
 896                                         }
 897                                 }
 898                         }
 899                 } else if (curr_prop & mtp_property_nothrow) {
 900                         /* exception flow detected */
 901                         pred = skip_Proj(pred);
 902
 903                         if (is_Call(pred)) {
 904                                 ir_node *ptr = get_Call_ptr(pred);
 905
 906                                 if (is_Global(ptr)) {
 907                                         /* a direct call */
 908                                         ir_entity *ent    = get_Global_entity(ptr);
 909                                         ir_graph  *callee = get_entity_irg(ent);
 910
 911                                         if (callee == irg) {
 912                                                 /* A self-recursive call. The property did not depend on this call. */
 913                                         } else if (callee != NULL) {
 914                                                 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
 915                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
 916                                                 curr_prop = update_property(curr_prop, prop);
 917                                         } else {
 918                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
 919                                                         curr_prop &= ~mtp_property_nothrow;
 920                                         }
 921                                 } else if (get_opt_closed_world() &&
 922                                            is_Sel(ptr) &&
 923                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 924                                         /* check if all possible callees are nothrow functions. */
 925                                         int i, n_callees = get_Call_n_callees(pred);
 926                                         if (n_callees == 0) {
 927                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 928                                                    when executed as there is no implementation to call.  So better not
 929                                                    optimize. */
 930                                                 curr_prop &= ~mtp_property_nothrow;
 931                                                 continue;
 932                                         }
 933
 934                                         for (i = 0; i < n_callees; ++i) {
 935                                                 ir_entity *ent = get_Call_callee(pred, i);
 936                                                 if (ent == unknown_entity) {
 937                                                         /* we don't know which entity is called here */
 938                                                         curr_prop &= ~mtp_property_nothrow;
 939                                                         break;
 940                                                 }
 941                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
 942                                                         curr_prop &= ~mtp_property_nothrow;
 943                                                         break;
 944                                                 }
 945                                         }
 946                                         /* if we pass the for cycle, nothrow is still ok */
 947                                 } else {
 948                                         /* unknown call */
 949                                         curr_prop &= ~mtp_property_nothrow;
 950                                 }
 951                         } else {
 952                                 /* real exception flow possible. */
 953                                 curr_prop &= ~mtp_property_nothrow;
 954                         }
 955                 }
 956                 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
 957                         /* no need to search further */
 958                         break;
 959                 }
 960         }
 961
 962         if (curr_prop & mtp_property_malloc) {
 963                 /*
 964                  * Note that the malloc property means not only return newly allocated
 965                  * memory, but also that this memory is ALIAS FREE.
 966                  * To ensure that, we do NOT allow that the returned memory is somewhere
 967                  * stored.
 968              */
 969                 curr_prop &= check_stored_result(irg);
 970         }
 971
 972         if (curr_prop != mtp_no_property) {
 973                 if (top || (curr_prop & mtp_temporary) == 0) {
 974                         /* We use the temporary flag here to mark an optimistic result.
 975                            Set the property only if we are sure that it does NOT base on
 976                            temporary results OR if we are at top-level. */
 977                         set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
 978                         SET_IRG_READY(irg);
 979                 }
 980         }
 981         if (top)
 982                 SET_IRG_READY(irg);
 983         CLEAR_IRG_BUSY(irg);
 984         return curr_prop;
 985 }  /* check_nothrow_or_malloc */
 986
 987 /**
 988  * When a function was detected as "const", it might be moved out of loops.
 989  * This might be dangerous if the graph might contain endless loops.
 990  */
 991 static void check_for_possible_endless_loops(ir_graph *irg) {
 992         ir_loop *root_loop;
 993         assure_cf_loop(irg);
 994
 995         root_loop = get_irg_loop(irg);
 996         if (root_loop->flags & loop_outer_loop)
 997                 set_irg_additional_property(irg, mtp_property_has_loop);
 998 }
 999
1000 /*
1001  * optimize function calls by handling const functions
1002  */
1003 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
1004 {
1005         int i, last_idx;
1006         unsigned num_const   = 0;
1007         unsigned num_pure    = 0;
1008         unsigned num_nothrow = 0;
1009         unsigned num_malloc  = 0;
1010
1011         is_alloc_entity = callback;
1012
1013         /* prepare: mark all graphs as not analyzed */
1014         last_idx = get_irp_last_idx();
1015         ready_set = rbitset_malloc(last_idx);
1016         busy_set  = rbitset_malloc(last_idx);
1017
1018         /* first step: detect, which functions are nothrow or malloc */
1019         DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1020         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1021                 ir_graph *irg = get_irp_irg(i);
1022                 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1023
1024                 if (prop & mtp_property_nothrow) {
1025                         ++num_nothrow;
1026                         DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1027                 } else if (prop & mtp_property_malloc) {
1028                         ++num_malloc;
1029                         DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1030                 }
1031         }
1032
1033         /* second step: remove exception edges: this must be done before the
1034            detection of const and pure functions take place. */
1035         if (force_run || num_nothrow > 0) {
1036                 env_t ctx;
1037
1038                 handle_nothrow_Calls(&ctx);
1039                 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1040                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1041                         ctx.n_calls_SymConst, ctx.n_calls_Sel));
1042         } else {
1043                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1044         }
1045
1046         rbitset_clear_all(ready_set, last_idx);
1047         rbitset_clear_all(busy_set, last_idx);
1048
1049         /* third step: detect, which functions are const or pure */
1050         DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1051         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1052                 ir_graph *irg = get_irp_irg(i);
1053                 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1054
1055                 if (prop & mtp_property_const) {
1056                         ++num_const;
1057                         DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1058                         check_for_possible_endless_loops(irg);
1059                 } else if (prop & mtp_property_pure) {
1060                         ++num_pure;
1061                         DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1062                 }
1063         }
1064
1065         if (force_run || num_const > 0) {
1066                 env_t ctx;
1067
1068                 handle_const_Calls(&ctx);
1069                 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1070                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1071                        ctx.n_calls_SymConst, ctx.n_calls_Sel));
1072         } else {
1073                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1074         }
1075         xfree(busy_set);
1076         xfree(ready_set);
1077 }  /* optimize_funccalls */
1078
1079 /* initialize the funccall optimization */
1080 void firm_init_funccalls(void) {
1081         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1082 //      firm_dbg_set_mask(dbg, -1);
1083 }  /* firm_init_funccalls */