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_Global(ptr)) {
  94                         ent = get_Global_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 their memory input.
 175          * The 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                  * Unfortunately 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 || is_Call(mem))
 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_Global(ptr)) {
 265                         ent = get_Global_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 (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
 467                                 ir_entity *ent = get_SymConst_entity(ptr);
 468                                 ir_graph  *irg = get_entity_irg(ent);
 469
 470                                 if (irg == current_ir_graph) {
 471                                         /* A self-recursive call. The property did not depend on this call. */
 472                                 } else if (irg == NULL) {
 473                                         m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
 474                                         mode = max_property(mode, m);
 475                                 } else if (irg != NULL) {
 476                                         /* we have a graph, analyze it. */
 477                                         m = check_const_or_pure_function(irg, /*top=*/0);
 478                                         mode = max_property(mode, m);
 479                                 }
 480                         } else
 481                                 return mtp_no_property;
 482                         node = get_Call_mem(node);
 483                         break;
 484
 485                 default:
 486                         return mtp_no_property;
 487                 }
 488         }
 489 }  /* _follow_mem */
 490
 491 /**
 492  * Follow the memory chain starting at node and determine
 493  * the mtp_property.
 494  *
 495  * @return mtp_property_const if only calls of const functions are detected
 496  *         mtp_property_pure  if only Loads and const/pure calls detected
 497  *         mtp_no_property else
 498  */
 499 static unsigned follow_mem(ir_node *node, unsigned mode) {
 500         unsigned m;
 501
 502         m = _follow_mem(node);
 503         return max_property(mode, m);
 504 }  /* follow_mem */
 505
 506 /**
 507  * Check if a graph represents a const or a pure function.
 508  *
 509  * @param irg  the graph to check
 510  * @param top  if set, this is the top call
 511  */
 512 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
 513         ir_node *end, *endbl;
 514         int j;
 515         unsigned prop = get_irg_additional_properties(irg);
 516         ir_graph *rem = current_ir_graph;
 517
 518         if (prop & mtp_property_const) {
 519                 /* already marked as a const function */
 520                 return mtp_property_const;
 521         }
 522         if (prop & mtp_property_pure) {
 523                 /* already marked as a pure function */
 524                 return mtp_property_pure;
 525         }
 526
 527         if (IS_IRG_READY(irg)) {
 528                 /* already checked */
 529                 return mtp_no_property;
 530         }
 531         if (IS_IRG_BUSY(irg)) {
 532                 /* we are still evaluate this method. Be optimistic,
 533                    return the best possible so far but mark the result as temporary. */
 534                 return mtp_temporary | mtp_property_const;
 535         }
 536         SET_IRG_BUSY(irg);
 537
 538         end   = get_irg_end(irg);
 539         endbl = get_nodes_block(end);
 540         prop  = mtp_property_const;
 541
 542         current_ir_graph = irg;
 543
 544         inc_irg_visited(irg);
 545         /* mark the initial mem: recursion of follow_mem stops here */
 546         mark_irn_visited(get_irg_initial_mem(irg));
 547
 548         /* visit every Return */
 549         for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
 550                 ir_node   *node = get_Block_cfgpred(endbl, j);
 551                 ir_opcode code  = get_irn_opcode(node);
 552                 ir_node   *mem;
 553
 554                 /* Bad nodes usually do NOT produce anything, so it's ok */
 555                 if (code == iro_Bad)
 556                         continue;
 557
 558                 if (code == iro_Return) {
 559                         mem = get_Return_mem(node);
 560
 561                         /* Bad nodes usually do NOT produce anything, so it's ok */
 562                         if (is_Bad(mem))
 563                                 continue;
 564
 565                         if (mem != get_irg_initial_mem(irg))
 566                                 prop = max_property(prop, follow_mem(mem, prop));
 567                 } else {
 568                         /* Exception found. Cannot be const or pure. */
 569                         prop = mtp_no_property;
 570                         break;
 571                 }
 572                 if (prop == mtp_no_property)
 573                         break;
 574         }
 575
 576         if (prop != mtp_no_property) {
 577                 /* check, if a keep-alive exists */
 578                 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
 579                         ir_node *kept = get_End_keepalive(end, j);
 580
 581                         if (is_Block(kept)) {
 582                                 prop = mtp_no_property;
 583                                 break;
 584                         }
 585
 586                         if (mode_M != get_irn_mode(kept))
 587                                 continue;
 588
 589                         prop = max_property(prop, follow_mem(kept, prop));
 590                         if (prop == mtp_no_property)
 591                                 break;
 592                 }
 593         }
 594
 595         if (prop != mtp_no_property) {
 596                 if (top || (prop & mtp_temporary) == 0) {
 597                         /* We use the temporary flag here to mark optimistic result.
 598                            Set the property only if we are sure that it does NOT base on
 599                            temporary results OR if we are at top-level. */
 600                         set_irg_additional_property(irg, prop & ~mtp_temporary);
 601                         SET_IRG_READY(irg);
 602                 }
 603         }
 604         if (top)
 605                 SET_IRG_READY(irg);
 606         CLEAR_IRG_BUSY(irg);
 607         current_ir_graph = rem;
 608         return prop;
 609 }  /* check_const_or_pure_function */
 610
 611 /**
 612  * Handle calls to const functions.
 613  *
 614  * @param ctx  context
 615  */
 616 static void handle_const_Calls(env_t *ctx) {
 617         int i;
 618
 619         ctx->n_calls_SymConst = 0;
 620         ctx->n_calls_Sel      = 0;
 621
 622         /* all calls of const functions can be transformed */
 623         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 624                 ir_graph *irg  = get_irp_irg(i);
 625
 626                 ctx->const_call_list = NULL;
 627                 ctx->pure_call_list  = NULL;
 628                 ctx->proj_list = NULL;
 629                 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
 630
 631                 if (ctx->const_call_list) {
 632                         fix_const_call_list(irg, ctx->const_call_list, ctx->proj_list);
 633
 634                         /* this graph was changed, invalidate analysis info */
 635                         set_irg_outs_inconsistent(irg);
 636                         set_irg_doms_inconsistent(irg);
 637                 }
 638         }
 639 }  /* handle_const_Calls */
 640
 641 /**
 642  * Handle calls to nothrow functions.
 643  *
 644  * @param ctx  context
 645  */
 646 static void handle_nothrow_Calls(env_t *ctx) {
 647         int i;
 648
 649         ctx->n_calls_SymConst = 0;
 650         ctx->n_calls_Sel      = 0;
 651
 652         /* all calls of const functions can be transformed */
 653         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 654                 ir_graph *irg  = get_irp_irg(i);
 655
 656                 ctx->nothrow_call_list = NULL;
 657                 ctx->proj_list         = NULL;
 658                 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
 659
 660                 if (ctx->nothrow_call_list) {
 661                         fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
 662
 663                         /* this graph was changed, invalidate analysis info */
 664                         set_irg_outs_inconsistent(irg);
 665                         set_irg_doms_inconsistent(irg);
 666                 }
 667         }
 668 }
 669
 670 /**
 671  * Check, whether a given node represents a return value of
 672  * a malloc like function (ie, new heap allocated memory).
 673  *
 674  * @param node  the node to check
 675  */
 676 static int is_malloc_call_result(const ir_node *node) {
 677         if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
 678                 /* Firm style high-level allocation */
 679                 return 1;
 680         }
 681         if (is_alloc_entity != NULL && is_Call(node)) {
 682                 ir_node *ptr = get_Call_ptr(node);
 683
 684                 if (is_Global(ptr)) {
 685                         ir_entity *ent = get_Global_entity(ptr);
 686                         return is_alloc_entity(ent);
 687                 }
 688         }
 689         return 0;
 690 }  /* is_malloc_call_result */
 691
 692 /**
 693  * Update a property depending on a call property.
 694  */
 695 static unsigned update_property(unsigned orig_prop, unsigned call_prop) {
 696         unsigned t = (orig_prop | call_prop) & mtp_temporary;
 697         unsigned r = orig_prop & call_prop;
 698         return r | t;
 699 }  /** update_property */
 700
 701 /**
 702  * Check if a node is stored.
 703  */
 704 static int is_stored(const ir_node *n) {
 705         const ir_edge_t *edge;
 706         const ir_node   *ptr;
 707
 708         foreach_out_edge(n, edge) {
 709                 const ir_node *succ = get_edge_src_irn(edge);
 710
 711                 switch (get_irn_opcode(succ)) {
 712                 case iro_Return:
 713                 case iro_Load:
 714                 case iro_Cmp:
 715                         /* ok */
 716                         break;
 717                 case iro_Store:
 718                         if (get_Store_value(succ) == n)
 719                                 return 1;
 720                         /* ok if its only the address input */
 721                         break;
 722                 case iro_Sel:
 723                 case iro_Cast:
 724                 case iro_Confirm:
 725                         if (is_stored(succ))
 726                                 return 1;
 727                         break;
 728                 case iro_Call:
 729                         ptr = get_Call_ptr(succ);
 730                         if (is_Global(ptr)) {
 731                                 ir_entity *ent = get_Global_entity(ptr);
 732                                 int       i;
 733
 734                                 /* we know the called entity */
 735                                 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
 736                                         if (get_Call_param(succ, i) == n) {
 737                                                 /* n is the i'th param of the call */
 738                                                 if (get_method_param_access(ent, i) & ptr_access_store) {
 739                                                         /* n is store in ent */
 740                                                         return 1;
 741                                                 }
 742                                         }
 743                                 }
 744                         } else {
 745                                 /* unknown call address */
 746                                 return 1;
 747                         }
 748                         break;
 749                 default:
 750                         /* bad, potential alias */
 751                         return 1;
 752                 }
 753         }
 754         return 0;
 755 }  /* is_stored */
 756
 757 /**
 758  * Check that the return value of an irg is not stored anywhere.
 759  *
 760  * return ~mtp_property_malloc if return values are stored, ~0 else
 761  */
 762 static unsigned check_stored_result(ir_graph *irg) {
 763         ir_node  *end_blk = get_irg_end_block(irg);
 764         int      i, j;
 765         unsigned res = ~0;
 766         int      old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
 767
 768         for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
 769                 ir_node *pred = get_Block_cfgpred(end_blk, i);
 770
 771                 if (! is_Return(pred))
 772                         continue;
 773                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 774                         const ir_node *irn = get_Return_res(pred, j);
 775
 776                         if (is_stored(irn)) {
 777                                 /* bad, might create an alias */
 778                                 res = ~mtp_property_malloc;
 779                                 goto finish;
 780                         }
 781                 }
 782         }
 783 finish:
 784         if (! old_edges)
 785                 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 786         return res;
 787 }  /* check_stored_result */
 788
 789 /**
 790  * Check if a graph represents a nothrow or a malloc function.
 791  *
 792  * @param irg  the graph to check
 793  * @param top  if set, this is the top call
 794  */
 795 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) {
 796         ir_node   *end_blk = get_irg_end_block(irg);
 797         ir_entity *ent;
 798         ir_type   *mtp;
 799         int       i, j;
 800         unsigned  curr_prop = mtp_property_malloc | mtp_property_nothrow;
 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                                 /* check, if malloc is called here */
 825                                 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
 826                                         ir_node *res = get_Return_res(pred, j);
 827
 828                                         /* skip Confirms and Casts */
 829                                         res = skip_HighLevel_ops(res);
 830                                         /* skip Proj's */
 831                                         while (is_Proj(res))
 832                                                 res = get_Proj_pred(res);
 833                                         if (is_malloc_call_result(res)) {
 834                                                 /* ok, this is a malloc */
 835                                         } else if (is_Call(res)) {
 836                                                 ir_node *ptr = get_Call_ptr(res);
 837
 838                                                 if (is_Global(ptr)) {
 839                                                         /* a direct call */
 840                                                         ir_entity *ent    = get_Global_entity(ptr);
 841                                                         ir_graph  *callee = get_entity_irg(ent);
 842
 843                                                         if (callee == irg) {
 844                                                                 /* A self-recursive call. The property did not depend on this call. */
 845                                                         } else if (callee != NULL) {
 846                                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
 847                                                                 curr_prop = update_property(curr_prop, prop);
 848                                                         } else {
 849                                                                 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
 850                                                         }
 851                                                 } else if (get_opt_closed_world() &&
 852                                                            is_Sel(ptr) &&
 853                                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 854                                                         /* check if all possible callees are malloc functions. */
 855                                                         int i, n_callees = get_Call_n_callees(res);
 856                                                         if (n_callees == 0) {
 857                                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 858                                                                    when executed as there is no implementation to call.  So better not
 859                                                                    optimize. */
 860                                                                 curr_prop &= ~mtp_property_malloc;
 861                                                                 continue;
 862                                                         }
 863
 864                                                         for (i = 0; i < n_callees; ++i) {
 865                                                                 ir_entity *ent = get_Call_callee(res, i);
 866                                                                 if (ent == unknown_entity) {
 867                                                                         /* we don't know which entity is called here */
 868                                                                         curr_prop &= ~mtp_property_malloc;
 869                                                                         break;
 870                                                                 }
 871                                                                 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
 872                                                                         curr_prop &= ~mtp_property_malloc;
 873                                                                         break;
 874                                                                 }
 875                                                         }
 876                                                         /* if we pass the for cycle, malloc is still ok */
 877                                                 } else {
 878                                                         /* unknown call */
 879                                                         curr_prop &= ~mtp_property_malloc;
 880                                                 }
 881                                         } else {
 882                                                 /* unknown return value */
 883                                                 curr_prop &= ~mtp_property_malloc;
 884                                         }
 885                                 }
 886                         }
 887                 } else if (curr_prop & mtp_property_nothrow) {
 888                         /* exception flow detected */
 889                         pred = skip_Proj(pred);
 890
 891                         if (is_Call(pred)) {
 892                                 ir_node *ptr = get_Call_ptr(pred);
 893
 894                                 if (is_Global(ptr)) {
 895                                         /* a direct call */
 896                                         ir_entity *ent    = get_Global_entity(ptr);
 897                                         ir_graph  *callee = get_entity_irg(ent);
 898
 899                                         if (callee == irg) {
 900                                                 /* A self-recursive call. The property did not depend on this call. */
 901                                         } else if (callee != NULL) {
 902                                                 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
 903                                                 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
 904                                                 curr_prop = update_property(curr_prop, prop);
 905                                         } else {
 906                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
 907                                                         curr_prop &= ~mtp_property_nothrow;
 908                                         }
 909                                 } else if (get_opt_closed_world() &&
 910                                            is_Sel(ptr) &&
 911                                            get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
 912                                         /* check if all possible callees are nothrow functions. */
 913                                         int i, n_callees = get_Call_n_callees(pred);
 914                                         if (n_callees == 0) {
 915                                                 /* This is kind of strange:  dying code or a Call that will raise an exception
 916                                                    when executed as there is no implementation to call.  So better not
 917                                                    optimize. */
 918                                                 curr_prop &= ~mtp_property_nothrow;
 919                                                 continue;
 920                                         }
 921
 922                                         for (i = 0; i < n_callees; ++i) {
 923                                                 ir_entity *ent = get_Call_callee(pred, i);
 924                                                 if (ent == unknown_entity) {
 925                                                         /* we don't know which entity is called here */
 926                                                         curr_prop &= ~mtp_property_nothrow;
 927                                                         break;
 928                                                 }
 929                                                 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
 930                                                         curr_prop &= ~mtp_property_nothrow;
 931                                                         break;
 932                                                 }
 933                                         }
 934                                         /* if we pass the for cycle, nothrow is still ok */
 935                                 } else {
 936                                         /* unknown call */
 937                                         curr_prop &= ~mtp_property_nothrow;
 938                                 }
 939                         } else {
 940                                 /* real exception flow possible. */
 941                                 curr_prop &= ~mtp_property_nothrow;
 942                         }
 943                 }
 944                 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
 945                         /* no need to search further */
 946                         break;
 947                 }
 948         }
 949
 950         if (curr_prop & mtp_property_malloc) {
 951                 /*
 952                  * Note that the malloc property means not only return newly allocated
 953                  * memory, but also that this memory is ALIAS FREE.
 954                  * To ensure that, we do NOT allow that the returned memory is somewhere
 955                  * stored.
 956              */
 957                 curr_prop &= check_stored_result(irg);
 958         }
 959
 960         if (curr_prop != mtp_no_property) {
 961                 if (top || (curr_prop & mtp_temporary) == 0) {
 962                         /* We use the temporary flag here to mark an optimistic result.
 963                            Set the property only if we are sure that it does NOT base on
 964                            temporary results OR if we are at top-level. */
 965                         set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
 966                         SET_IRG_READY(irg);
 967                 }
 968         }
 969         if (top)
 970                 SET_IRG_READY(irg);
 971         CLEAR_IRG_BUSY(irg);
 972         return curr_prop;
 973 }  /* check_nothrow_or_malloc */
 974
 975 /*
 976  * optimize function calls by handling const functions
 977  */
 978 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
 979 {
 980         int i, last_idx;
 981         unsigned num_const   = 0;
 982         unsigned num_pure    = 0;
 983         unsigned num_nothrow = 0;
 984         unsigned num_malloc  = 0;
 985
 986         is_alloc_entity = callback;
 987
 988         /* prepare: mark all graphs as not analyzed */
 989         last_idx = get_irp_last_idx();
 990         ready_set = rbitset_malloc(last_idx);
 991         busy_set  = rbitset_malloc(last_idx);
 992
 993         /* first step: detect, which functions are nothrow or malloc */
 994         DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
 995         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 996                 ir_graph *irg = get_irp_irg(i);
 997                 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
 998
 999                 if (prop & mtp_property_nothrow) {
1000                         ++num_nothrow;
1001                         DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1002                 } else if (prop & mtp_property_malloc) {
1003                         ++num_malloc;
1004                         DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1005                 }
1006         }
1007
1008         /* second step: remove exception edges: this must be done before the
1009            detection of const and pure functions take place. */
1010         if (force_run || num_nothrow > 0) {
1011                 env_t ctx;
1012
1013                 handle_nothrow_Calls(&ctx);
1014                 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1015                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1016                         ctx.n_calls_SymConst, ctx.n_calls_Sel));
1017         } else {
1018                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1019         }
1020
1021         rbitset_clear_all(ready_set, last_idx);
1022         rbitset_clear_all(busy_set, last_idx);
1023
1024         /* third step: detect, which functions are const or pure */
1025         DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1026         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1027                 ir_graph *irg = get_irp_irg(i);
1028                 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1029
1030                 if (prop & mtp_property_const) {
1031                         ++num_const;
1032                         DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1033                 } else if (prop & mtp_property_pure) {
1034                         ++num_pure;
1035                         DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1036                 }
1037         }
1038
1039         if (force_run || num_const > 0) {
1040                 env_t ctx;
1041
1042                 handle_const_Calls(&ctx);
1043                 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1044                 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1045                        ctx.n_calls_SymConst, ctx.n_calls_Sel));
1046         } else {
1047                 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1048         }
1049         xfree(busy_set);
1050         xfree(ready_set);
1051 }  /* optimize_funccalls */
1052
1053 /* initialize the funccall optimization */
1054 void firm_init_funccalls(void) {
1055         FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1056 //      firm_dbg_set_mask(dbg, -1);
1057 }  /* firm_init_funccalls */