2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Optimization of function calls.
23 * @author Michael Beck
28 #include <adt/raw_bitset.h>
33 #include "irgraph_t.h"
37 #include "dbginfo_t.h"
41 #include "iredges_t.h"
43 #include "iroptimize.h"
44 #include "analyze_irg_args.h"
48 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
51 * The walker environment for updating function calls.
53 typedef struct _env_t {
54 unsigned n_calls_SymConst;
56 ir_node *float_const_call_list; /**< The list of all floating const function calls that will be changed. */
57 ir_node *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
58 ir_node *pure_call_list; /**< The list of all pure function calls that will be changed. */
59 ir_node *nothrow_call_list; /**< The list of all nothrow function calls that will be changed. */
60 ir_node *proj_list; /**< The list of all potential Proj nodes that must be fixed. */
63 /** If non-null, evaluates entities for being a heap alloc. */
64 static check_alloc_entity_func is_alloc_entity = NULL;
66 /** Ready IRG's are marked in the ready set. */
67 static unsigned *ready_set;
69 /** IRG's that are in progress are marked here. */
70 static unsigned *busy_set;
73 * We misuse the mtp_property_inherited flag as temporary here.
74 * The is ok, as we cannot set or get it anyway using the
75 * get_addtional_properties API.
77 #define mtp_temporary mtp_property_inherited
80 * Walker: Collect all calls to const and pure functions
81 * to lists. Collect all Proj(Call) nodes into a Proj list.
83 static void collect_const_and_pure_calls(ir_node *node, void *env)
88 unsigned and_prop, or_prop, prop;
93 /* set the link to NULL for all non-const/pure calls */
94 set_irn_link(call, NULL);
95 ptr = get_Call_ptr(call);
97 ent = get_Global_entity(ptr);
99 prop = get_entity_additional_properties(ent);
100 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
102 ++ctx->n_calls_SymConst;
103 } else if (get_opt_closed_world() &&
105 get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
106 /* If all possible callees are const functions, we can remove the memory edge. */
107 int i, n_callees = get_Call_n_callees(call);
108 if (n_callees == 0) {
109 /* This is kind of strange: dying code or a Call that will raise an exception
110 when executed as there is no implementation to call. So better not
115 /* note that const function are a subset of pure ones */
116 and_prop = mtp_property_const | mtp_property_pure;
118 for (i = 0; i < n_callees; ++i) {
119 ent = get_Call_callee(call, i);
120 if (ent == unknown_entity) {
121 /* we don't know which entity is called here */
124 prop = get_entity_additional_properties(ent);
127 if (and_prop == mtp_no_property)
130 prop = and_prop | (or_prop & mtp_property_has_loop);
135 /* ok, if we get here we found a call to a const or a pure function */
136 if (prop & mtp_property_pure) {
137 set_irn_link(call, ctx->pure_call_list);
138 ctx->pure_call_list = call;
140 if (prop & mtp_property_has_loop) {
141 set_irn_link(call, ctx->nonfloat_const_call_list);
142 ctx->nonfloat_const_call_list = call;
144 set_irn_link(call, ctx->float_const_call_list);
145 ctx->float_const_call_list = call;
148 } else if (is_Proj(node)) {
150 * Collect all memory and exception Proj's from
153 call = get_Proj_pred(node);
157 /* collect the Proj's in the Proj list */
158 switch (get_Proj_proj(node)) {
160 case pn_Call_X_except:
161 case pn_Call_X_regular:
162 set_irn_link(node, ctx->proj_list);
163 ctx->proj_list = node;
169 } /* collect_const_and_pure_calls */
172 * Fix the list of collected Calls.
174 * @param irg the graph that contained calls to pure functions
177 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
179 ir_node *call, *next, *mem, *proj;
181 ir_graph *rem = current_ir_graph;
183 current_ir_graph = irg;
185 /* First step: fix all calls by removing their memory input and let
187 * The original memory input is preserved in their link fields. */
188 for (call = ctx->float_const_call_list; call != NULL; call = next) {
189 next = get_irn_link(call);
190 mem = get_Call_mem(call);
192 set_irn_link(call, mem);
193 set_Call_mem(call, get_irg_no_mem(irg));
196 * Unfortunately we cannot simply set the node to 'float'.
197 * There is a reason for that:
199 * - The call might be inside a loop/if that is NOT entered
200 * and calls a endless function. Setting the call to float
201 * would allow to move it out from the loop/if causing this
202 * function be called even if the loop/if is not entered ...
204 * This could be fixed using post-dominators for calls and Pin nodes
205 * but need some more analyzes to ensure that a call that potential
206 * never returns is not executed before some code that generates
207 * observable states...
210 /* finally, this call can float */
211 set_irn_pinned(call, op_pin_state_floats);
212 hook_func_call(irg, call);
215 /* Last step: fix all Proj's */
216 for (proj = ctx->proj_list; proj != NULL; proj = next) {
217 next = get_irn_link(proj);
218 call = get_Proj_pred(proj);
219 mem = get_irn_link(call);
221 /* beware of calls in the pure call list */
222 if (!mem || is_Call(mem))
224 assert(get_irn_mode(mem) == mode_M);
226 switch (get_Proj_proj(proj)) {
228 /* in dead code there might be cycles where proj == mem */
233 case pn_Call_X_except:
235 exchange(proj, get_irg_bad(irg));
237 case pn_Call_X_regular: {
238 ir_node *block = get_nodes_block(call);
240 exchange(proj, new_r_Jmp(block));
248 /* changes were done ... */
249 set_irg_outs_inconsistent(irg);
250 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
253 /* ... including exception edges */
254 set_irg_doms_inconsistent(irg);
256 current_ir_graph = rem;
257 } /* fix_const_call_list */
260 * Walker: Collect all calls to nothrow functions
261 * to lists. Collect all Proj(Call) nodes into a Proj list.
263 static void collect_nothrow_calls(ir_node *node, void *env)
273 /* set the link to NULL for all non-const/pure calls */
274 set_irn_link(call, NULL);
275 ptr = get_Call_ptr(call);
276 if (is_Global(ptr)) {
277 ent = get_Global_entity(ptr);
279 prop = get_entity_additional_properties(ent);
280 if ((prop & mtp_property_nothrow) == 0)
282 ++ctx->n_calls_SymConst;
283 } else if (get_opt_closed_world() &&
285 get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
286 /* If all possible callees are nothrow functions, we can remove the exception edge. */
287 int i, n_callees = get_Call_n_callees(call);
288 if (n_callees == 0) {
289 /* This is kind of strange: dying code or a Call that will raise an exception
290 when executed as there is no implementation to call. So better not
295 /* note that const function are a subset of pure ones */
296 prop = mtp_property_nothrow;
297 for (i = 0; i < n_callees; ++i) {
298 ent = get_Call_callee(call, i);
299 if (ent == unknown_entity) {
300 /* we don't know which entity is called here */
303 prop &= get_entity_additional_properties(ent);
304 if (prop == mtp_no_property)
311 /* ok, if we get here we found a call to a nothrow function */
312 set_irn_link(call, ctx->nothrow_call_list);
313 ctx->nothrow_call_list = call;
314 } else if (is_Proj(node)) {
316 * Collect all memory and exception Proj's from
319 call = get_Proj_pred(node);
323 /* collect the Proj's in the Proj list */
324 switch (get_Proj_proj(node)) {
326 case pn_Call_X_except:
327 case pn_Call_X_regular:
328 set_irn_link(node, ctx->proj_list);
329 ctx->proj_list = node;
335 } /* collect_nothrow_calls */
338 * Fix the list of collected nothrow Calls.
340 * @param irg the graph that contained calls to pure functions
341 * @param call_list the list of all call sites of const functions
342 * @param proj_list the list of all memory/exception Proj's of this call sites
344 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
346 ir_node *call, *next, *proj;
348 ir_graph *rem = current_ir_graph;
350 current_ir_graph = irg;
352 /* First step: go through the list of calls and mark them. */
353 for (call = call_list; call; call = next) {
354 next = get_irn_link(call);
356 /* current_ir_graph is in memory anyway, so it's a good marker */
357 set_irn_link(call, ¤t_ir_graph);
358 hook_func_call(irg, call);
361 /* Second step: Remove all exception Proj's */
362 for (proj = proj_list; proj; proj = next) {
363 next = get_irn_link(proj);
364 call = get_Proj_pred(proj);
366 /* handle only marked calls */
367 if (get_irn_link(call) != ¤t_ir_graph)
370 /* kill any exception flow */
371 switch (get_Proj_proj(proj)) {
372 case pn_Call_X_except:
374 exchange(proj, get_irg_bad(irg));
376 case pn_Call_X_regular: {
377 ir_node *block = get_nodes_block(call);
379 exchange(proj, new_r_Jmp(block));
387 /* changes were done ... */
388 set_irg_outs_inconsistent(irg);
389 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
392 /* ... including exception edges */
393 set_irg_doms_inconsistent(irg);
395 current_ir_graph = rem;
396 } /* fix_nothrow_call_list */
399 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
400 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
401 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
402 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
403 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
406 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
407 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top);
410 * Calculate the bigger property of two. Handle the temporary flag right.
412 static unsigned max_property(unsigned a, unsigned b)
414 unsigned r, t = (a | b) & mtp_temporary;
418 if (a == mtp_no_property || b == mtp_no_property)
419 return mtp_no_property;
425 * Follow the memory chain starting at node and determine
428 * @return mtp_property_const if only calls of const functions are detected
429 * mtp_property_pure if only Loads and const/pure calls detected
430 * mtp_no_property else
432 static unsigned _follow_mem(ir_node *node)
434 unsigned m, mode = mtp_property_const;
439 if (mode == mtp_no_property)
440 return mtp_no_property;
442 if (irn_visited_else_mark(node))
445 switch (get_irn_opcode(node)) {
447 node = get_Proj_pred(node);
456 /* do a dfs search */
457 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
458 m = _follow_mem(get_irn_n(node, i));
459 mode = max_property(mode, m);
460 if (mode == mtp_no_property)
461 return mtp_no_property;
466 /* Beware volatile Loads are NOT allowed in pure functions. */
467 if (get_Load_volatility(node) == volatility_is_volatile)
468 return mtp_no_property;
469 mode = max_property(mode, mtp_property_pure);
470 node = get_Load_mem(node);
474 /* A call is only tolerable if its either constant or pure. */
475 ptr = get_Call_ptr(node);
476 if (is_SymConst_addr_ent(ptr)) {
477 ir_entity *ent = get_SymConst_entity(ptr);
478 ir_graph *irg = get_entity_irg(ent);
480 if (irg == current_ir_graph) {
481 /* A self-recursive call. The property did not depend on this call. */
482 } else if (irg == NULL) {
483 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
484 mode = max_property(mode, m);
485 } else if (irg != NULL) {
486 /* we have a graph, analyze it. */
487 m = check_const_or_pure_function(irg, /*top=*/0);
488 mode = max_property(mode, m);
491 return mtp_no_property;
492 node = get_Call_mem(node);
496 return mtp_no_property;
502 * Follow the memory chain starting at node and determine
505 * @return mtp_property_const if only calls of const functions are detected
506 * mtp_property_pure if only Loads and const/pure calls detected
507 * mtp_no_property else
509 static unsigned follow_mem(ir_node *node, unsigned mode)
513 m = _follow_mem(node);
514 return max_property(mode, m);
518 * Check if a graph represents a const or a pure function.
520 * @param irg the graph to check
521 * @param top if set, this is the top call
523 static unsigned check_const_or_pure_function(ir_graph *irg, int top)
525 ir_node *end, *endbl;
527 unsigned prop = get_irg_additional_properties(irg);
528 ir_graph *rem = current_ir_graph;
530 if (prop & mtp_property_const) {
531 /* already marked as a const function */
532 return mtp_property_const;
534 if (prop & mtp_property_pure) {
535 /* already marked as a pure function */
536 return mtp_property_pure;
539 if (IS_IRG_READY(irg)) {
540 /* already checked */
541 return mtp_no_property;
543 if (IS_IRG_BUSY(irg)) {
544 /* we are still evaluate this method. Be optimistic,
545 return the best possible so far but mark the result as temporary. */
546 return mtp_temporary | mtp_property_const;
550 end = get_irg_end(irg);
551 endbl = get_nodes_block(end);
552 prop = mtp_property_const;
554 current_ir_graph = irg;
556 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
557 inc_irg_visited(irg);
558 /* mark the initial mem: recursion of follow_mem() stops here */
559 mark_irn_visited(get_irg_initial_mem(irg));
561 /* visit every Return */
562 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
563 ir_node *node = get_Block_cfgpred(endbl, j);
564 ir_opcode code = get_irn_opcode(node);
567 /* Bad nodes usually do NOT produce anything, so it's ok */
571 if (code == iro_Return) {
572 mem = get_Return_mem(node);
574 /* Bad nodes usually do NOT produce anything, so it's ok */
578 if (mem != get_irg_initial_mem(irg))
579 prop = max_property(prop, follow_mem(mem, prop));
581 /* Exception found. Cannot be const or pure. */
582 prop = mtp_no_property;
585 if (prop == mtp_no_property)
589 if (prop != mtp_no_property) {
590 /* check, if a keep-alive exists */
591 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
592 ir_node *kept = get_End_keepalive(end, j);
594 if (is_Block(kept)) {
595 prop = mtp_no_property;
599 if (mode_M != get_irn_mode(kept))
602 prop = max_property(prop, follow_mem(kept, prop));
603 if (prop == mtp_no_property)
608 if (prop != mtp_no_property) {
609 if (top || (prop & mtp_temporary) == 0) {
610 /* We use the temporary flag here to mark optimistic result.
611 Set the property only if we are sure that it does NOT base on
612 temporary results OR if we are at top-level. */
613 set_irg_additional_property(irg, prop & ~mtp_temporary);
620 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
621 current_ir_graph = rem;
623 } /* check_const_or_pure_function */
626 * Handle calls to const functions.
630 static void handle_const_Calls(env_t *ctx)
634 ctx->n_calls_SymConst = 0;
635 ctx->n_calls_Sel = 0;
637 /* all calls of const functions can be transformed */
638 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
639 ir_graph *irg = get_irp_irg(i);
641 ctx->float_const_call_list = NULL;
642 ctx->nonfloat_const_call_list = NULL;
643 ctx->pure_call_list = NULL;
644 ctx->proj_list = NULL;
646 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
647 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
649 if (ctx->float_const_call_list != NULL)
650 fix_const_call_lists(irg, ctx);
651 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
653 } /* handle_const_Calls */
656 * Handle calls to nothrow functions.
660 static void handle_nothrow_Calls(env_t *ctx)
664 ctx->n_calls_SymConst = 0;
665 ctx->n_calls_Sel = 0;
667 /* all calls of const functions can be transformed */
668 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
669 ir_graph *irg = get_irp_irg(i);
671 ctx->nothrow_call_list = NULL;
672 ctx->proj_list = NULL;
674 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
675 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
677 if (ctx->nothrow_call_list)
678 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
679 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
684 * Check, whether a given node represents a return value of
685 * a malloc like function (ie, new heap allocated memory).
687 * @param node the node to check
689 static int is_malloc_call_result(const ir_node *node)
691 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
692 /* Firm style high-level allocation */
695 if (is_alloc_entity != NULL && is_Call(node)) {
696 ir_node *ptr = get_Call_ptr(node);
698 if (is_Global(ptr)) {
699 ir_entity *ent = get_Global_entity(ptr);
700 return is_alloc_entity(ent);
704 } /* is_malloc_call_result */
707 * Update a property depending on a call property.
709 static unsigned update_property(unsigned orig_prop, unsigned call_prop)
711 unsigned t = (orig_prop | call_prop) & mtp_temporary;
712 unsigned r = orig_prop & call_prop;
714 } /** update_property */
717 * Check if a node is stored.
719 static int is_stored(const ir_node *n)
721 const ir_edge_t *edge;
724 foreach_out_edge(n, edge) {
725 const ir_node *succ = get_edge_src_irn(edge);
727 switch (get_irn_opcode(succ)) {
734 if (get_Store_value(succ) == n)
736 /* ok if its only the address input */
745 ptr = get_Call_ptr(succ);
746 if (is_Global(ptr)) {
747 ir_entity *ent = get_Global_entity(ptr);
750 /* we know the called entity */
751 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
752 if (get_Call_param(succ, i) == n) {
753 /* n is the i'th param of the call */
754 if (get_method_param_access(ent, i) & ptr_access_store) {
755 /* n is store in ent */
761 /* unknown call address */
766 /* bad, potential alias */
774 * Check that the return value of an irg is not stored anywhere.
776 * return ~mtp_property_malloc if return values are stored, ~0 else
778 static unsigned check_stored_result(ir_graph *irg)
780 ir_node *end_blk = get_irg_end_block(irg);
783 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
785 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
786 ir_node *pred = get_Block_cfgpred(end_blk, i);
788 if (! is_Return(pred))
790 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
791 const ir_node *irn = get_Return_res(pred, j);
793 if (is_stored(irn)) {
794 /* bad, might create an alias */
795 res = ~mtp_property_malloc;
802 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
804 } /* check_stored_result */
807 * Check if a graph represents a nothrow or a malloc function.
809 * @param irg the graph to check
810 * @param top if set, this is the top call
812 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top)
814 ir_node *end_blk = get_irg_end_block(irg);
818 unsigned curr_prop = mtp_property_malloc | mtp_property_nothrow;
820 if (IS_IRG_READY(irg)) {
821 /* already checked */
822 return get_irg_additional_properties(irg);
824 if (IS_IRG_BUSY(irg)) {
825 /* we are still evaluate this method. Be optimistic,
826 return the best possible so far but mark the result as temporary. */
827 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
831 ent = get_irg_entity(irg);
832 mtp = get_entity_type(ent);
834 if (get_method_n_ress(mtp) <= 0)
835 curr_prop &= ~mtp_property_malloc;
837 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
838 ir_node *pred = get_Block_cfgpred(end_blk, i);
840 if (is_Return(pred)) {
841 if (curr_prop & mtp_property_malloc) {
842 /* check, if malloc is called here */
843 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
844 ir_node *res = get_Return_res(pred, j);
846 /* skip Confirms and Casts */
847 res = skip_HighLevel_ops(res);
850 res = get_Proj_pred(res);
851 if (is_malloc_call_result(res)) {
852 /* ok, this is a malloc */
853 } else if (is_Call(res)) {
854 ir_node *ptr = get_Call_ptr(res);
856 if (is_Global(ptr)) {
858 ir_entity *ent = get_Global_entity(ptr);
859 ir_graph *callee = get_entity_irg(ent);
862 /* A self-recursive call. The property did not depend on this call. */
863 } else if (callee != NULL) {
864 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
865 curr_prop = update_property(curr_prop, prop);
867 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
869 } else if (get_opt_closed_world() &&
871 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
872 /* check if all possible callees are malloc functions. */
873 int i, n_callees = get_Call_n_callees(res);
874 if (n_callees == 0) {
875 /* This is kind of strange: dying code or a Call that will raise an exception
876 when executed as there is no implementation to call. So better not
878 curr_prop &= ~mtp_property_malloc;
882 for (i = 0; i < n_callees; ++i) {
883 ir_entity *ent = get_Call_callee(res, i);
884 if (ent == unknown_entity) {
885 /* we don't know which entity is called here */
886 curr_prop &= ~mtp_property_malloc;
889 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
890 curr_prop &= ~mtp_property_malloc;
894 /* if we pass the for cycle, malloc is still ok */
897 curr_prop &= ~mtp_property_malloc;
900 /* unknown return value */
901 curr_prop &= ~mtp_property_malloc;
905 } else if (curr_prop & mtp_property_nothrow) {
906 /* exception flow detected */
907 pred = skip_Proj(pred);
910 ir_node *ptr = get_Call_ptr(pred);
912 if (is_Global(ptr)) {
914 ir_entity *ent = get_Global_entity(ptr);
915 ir_graph *callee = get_entity_irg(ent);
918 /* A self-recursive call. The property did not depend on this call. */
919 } else if (callee != NULL) {
920 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
921 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
922 curr_prop = update_property(curr_prop, prop);
924 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
925 curr_prop &= ~mtp_property_nothrow;
927 } else if (get_opt_closed_world() &&
929 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
930 /* check if all possible callees are nothrow functions. */
931 int i, n_callees = get_Call_n_callees(pred);
932 if (n_callees == 0) {
933 /* This is kind of strange: dying code or a Call that will raise an exception
934 when executed as there is no implementation to call. So better not
936 curr_prop &= ~mtp_property_nothrow;
940 for (i = 0; i < n_callees; ++i) {
941 ir_entity *ent = get_Call_callee(pred, i);
942 if (ent == unknown_entity) {
943 /* we don't know which entity is called here */
944 curr_prop &= ~mtp_property_nothrow;
947 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
948 curr_prop &= ~mtp_property_nothrow;
952 /* if we pass the for cycle, nothrow is still ok */
955 curr_prop &= ~mtp_property_nothrow;
958 /* real exception flow possible. */
959 curr_prop &= ~mtp_property_nothrow;
962 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
963 /* no need to search further */
968 if (curr_prop & mtp_property_malloc) {
970 * Note that the malloc property means not only return newly allocated
971 * memory, but also that this memory is ALIAS FREE.
972 * To ensure that, we do NOT allow that the returned memory is somewhere
975 curr_prop &= check_stored_result(irg);
978 if (curr_prop != mtp_no_property) {
979 if (top || (curr_prop & mtp_temporary) == 0) {
980 /* We use the temporary flag here to mark an optimistic result.
981 Set the property only if we are sure that it does NOT base on
982 temporary results OR if we are at top-level. */
983 set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
991 } /* check_nothrow_or_malloc */
994 * When a function was detected as "const", it might be moved out of loops.
995 * This might be dangerous if the graph can contain endless loops.
997 static void check_for_possible_endless_loops(ir_graph *irg)
1000 assure_cf_loop(irg);
1002 root_loop = get_irg_loop(irg);
1003 if (root_loop->flags & loop_outer_loop)
1004 set_irg_additional_property(irg, mtp_property_has_loop);
1008 * optimize function calls by handling const functions
1010 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
1013 unsigned num_const = 0;
1014 unsigned num_pure = 0;
1015 unsigned num_nothrow = 0;
1016 unsigned num_malloc = 0;
1018 is_alloc_entity = callback;
1020 /* prepare: mark all graphs as not analyzed */
1021 last_idx = get_irp_last_idx();
1022 ready_set = rbitset_malloc(last_idx);
1023 busy_set = rbitset_malloc(last_idx);
1025 /* first step: detect, which functions are nothrow or malloc */
1026 DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1027 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1028 ir_graph *irg = get_irp_irg(i);
1029 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1031 if (prop & mtp_property_nothrow) {
1033 DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1034 } else if (prop & mtp_property_malloc) {
1036 DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1040 /* second step: remove exception edges: this must be done before the
1041 detection of const and pure functions take place. */
1042 if (force_run || num_nothrow > 0) {
1045 handle_nothrow_Calls(&ctx);
1046 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1047 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1048 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1050 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1053 rbitset_clear_all(ready_set, last_idx);
1054 rbitset_clear_all(busy_set, last_idx);
1056 /* third step: detect, which functions are const or pure */
1057 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1058 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1059 ir_graph *irg = get_irp_irg(i);
1060 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1062 if (prop & mtp_property_const) {
1064 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1065 check_for_possible_endless_loops(irg);
1066 } else if (prop & mtp_property_pure) {
1068 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1072 if (force_run || num_const > 0) {
1075 handle_const_Calls(&ctx);
1076 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1077 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1078 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1080 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1084 } /* optimize_funccalls */
1086 /* initialize the funccall optimization */
1087 void firm_init_funccalls(void)
1089 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1090 } /* firm_init_funccalls */
1093 ir_prog_pass_t pass;
1095 check_alloc_entity_func callback;
1099 * Wrapper for running optimize_funccalls() as an ir_prog pass.
1101 static int pass_wrapper(ir_prog *irp, void *context)
1103 struct pass_t *pass = context;
1106 optimize_funccalls(pass->force_run, pass->callback);
1108 } /* pass_wrapper */
1110 /* Creates an ir_prog pass for optimize_funccalls. */
1111 ir_prog_pass_t *optimize_funccalls_pass(
1113 int force_run, check_alloc_entity_func callback)
1115 struct pass_t *pass = XMALLOCZ(struct pass_t);
1117 pass->force_run = force_run;
1118 pass->callback = callback;
1120 return def_prog_pass_constructor(
1121 &pass->pass, name ? name : "funccall", pass_wrapper);
1122 } /* optimize_funccalls_pass */