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

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