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

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