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