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