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

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