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

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