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
31 #include "irgraph_t.h"
34 #include "dbginfo_t.h"
38 #include "iredges_t.h"
40 #include "iroptimize.h"
41 #include "analyze_irg_args.h"
43 #include "raw_bitset.h"
46 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
49 * The walker environment for updating function calls.
51 typedef struct env_t {
52 unsigned n_calls_SymConst;
54 ir_node *float_const_call_list; /**< The list of all floating const function calls that will be changed. */
55 ir_node *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
56 ir_node *pure_call_list; /**< The list of all pure function calls that will be changed. */
57 ir_node *nothrow_call_list; /**< The list of all nothrow function calls that will be changed. */
58 ir_node *proj_list; /**< The list of all potential Proj nodes that must be fixed. */
61 /** If non-null, evaluates entities for being a heap alloc. */
62 static check_alloc_entity_func is_alloc_entity = NULL;
64 /** Ready IRG's are marked in the ready set. */
65 static unsigned *ready_set;
67 /** IRG's that are in progress are marked here. */
68 static unsigned *busy_set;
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.
75 #define mtp_temporary mtp_property_inherited
78 * Walker: Collect all calls to const and pure functions
79 * to lists. Collect all Proj(Call) nodes into a Proj list.
81 static void collect_const_and_pure_calls(ir_node *node, void *env)
86 unsigned and_prop, or_prop, prop;
91 /* set the link to NULL for all non-const/pure calls */
92 set_irn_link(call, NULL);
93 ptr = get_Call_ptr(call);
95 ent = get_Global_entity(ptr);
97 prop = get_entity_additional_properties(ent);
98 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
100 ++ctx->n_calls_SymConst;
101 } else if (get_opt_closed_world() &&
103 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
104 /* If all possible callees are const functions, we can remove the memory edge. */
105 int i, n_callees = get_Call_n_callees(call);
106 if (n_callees == 0) {
107 /* This is kind of strange: dying code or a Call that will raise an exception
108 when executed as there is no implementation to call. So better not
113 /* note that const function are a subset of pure ones */
114 and_prop = mtp_property_const | mtp_property_pure;
116 for (i = 0; i < n_callees; ++i) {
117 ent = get_Call_callee(call, i);
118 if (ent == unknown_entity) {
119 /* we don't know which entity is called here */
122 prop = get_entity_additional_properties(ent);
125 if (and_prop == mtp_no_property)
128 prop = and_prop | (or_prop & mtp_property_has_loop);
133 /* ok, if we get here we found a call to a const or a pure function */
134 if (prop & mtp_property_pure) {
135 set_irn_link(call, ctx->pure_call_list);
136 ctx->pure_call_list = call;
138 if (prop & mtp_property_has_loop) {
139 set_irn_link(call, ctx->nonfloat_const_call_list);
140 ctx->nonfloat_const_call_list = call;
142 set_irn_link(call, ctx->float_const_call_list);
143 ctx->float_const_call_list = call;
146 } else if (is_Proj(node)) {
148 * Collect all memory and exception Proj's from
151 call = get_Proj_pred(node);
155 /* collect the Proj's in the Proj list */
156 switch (get_Proj_proj(node)) {
158 case pn_Call_X_except:
159 case pn_Call_X_regular:
160 set_irn_link(node, ctx->proj_list);
161 ctx->proj_list = node;
167 } /* collect_const_and_pure_calls */
170 * Fix the list of collected Calls.
172 * @param irg the graph that contained calls to pure functions
175 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
177 ir_node *call, *next, *mem, *proj;
180 /* First step: fix all calls by removing their memory input and let
182 * The original memory input is preserved in their link fields. */
183 for (call = ctx->float_const_call_list; call != NULL; call = next) {
184 next = get_irn_link(call);
185 mem = get_Call_mem(call);
187 set_irn_link(call, mem);
188 set_Call_mem(call, get_irg_no_mem(irg));
191 * Unfortunately we cannot simply set the node to 'float'.
192 * There is a reason for that:
194 * - The call might be inside a loop/if that is NOT entered
195 * and calls a endless function. Setting the call to float
196 * would allow to move it out from the loop/if causing this
197 * function be called even if the loop/if is not entered ...
199 * This could be fixed using post-dominators for calls and Pin nodes
200 * but need some more analyzes to ensure that a call that potential
201 * never returns is not executed before some code that generates
202 * observable states...
205 /* finally, this call can float */
206 set_irn_pinned(call, op_pin_state_floats);
207 hook_func_call(irg, call);
210 /* Last step: fix all Proj's */
211 for (proj = ctx->proj_list; proj != NULL; proj = next) {
212 next = get_irn_link(proj);
213 call = get_Proj_pred(proj);
214 mem = get_irn_link(call);
216 /* beware of calls in the pure call list */
217 if (!mem || is_Call(mem))
219 assert(get_irn_mode(mem) == mode_M);
221 switch (get_Proj_proj(proj)) {
223 /* in dead code there might be cycles where proj == mem */
228 case pn_Call_X_except:
230 exchange(proj, get_irg_bad(irg));
232 case pn_Call_X_regular: {
233 ir_node *block = get_nodes_block(call);
235 exchange(proj, new_r_Jmp(block));
243 /* changes were done ... */
244 set_irg_outs_inconsistent(irg);
245 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
248 /* ... including exception edges */
249 set_irg_doms_inconsistent(irg);
251 } /* fix_const_call_list */
254 * Walker: Collect all calls to nothrow functions
255 * to lists. Collect all Proj(Call) nodes into a Proj list.
257 static void collect_nothrow_calls(ir_node *node, void *env)
267 /* set the link to NULL for all non-const/pure calls */
268 set_irn_link(call, NULL);
269 ptr = get_Call_ptr(call);
270 if (is_Global(ptr)) {
271 ent = get_Global_entity(ptr);
273 prop = get_entity_additional_properties(ent);
274 if ((prop & mtp_property_nothrow) == 0)
276 ++ctx->n_calls_SymConst;
277 } else if (get_opt_closed_world() &&
279 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
280 /* If all possible callees are nothrow functions, we can remove the exception edge. */
281 int i, n_callees = get_Call_n_callees(call);
282 if (n_callees == 0) {
283 /* This is kind of strange: dying code or a Call that will raise an exception
284 when executed as there is no implementation to call. So better not
289 /* note that const function are a subset of pure ones */
290 prop = mtp_property_nothrow;
291 for (i = 0; i < n_callees; ++i) {
292 ent = get_Call_callee(call, i);
293 if (ent == unknown_entity) {
294 /* we don't know which entity is called here */
297 prop &= get_entity_additional_properties(ent);
298 if (prop == mtp_no_property)
305 /* ok, if we get here we found a call to a nothrow function */
306 set_irn_link(call, ctx->nothrow_call_list);
307 ctx->nothrow_call_list = call;
308 } else if (is_Proj(node)) {
310 * Collect all memory and exception Proj's from
313 call = get_Proj_pred(node);
317 /* collect the Proj's in the Proj list */
318 switch (get_Proj_proj(node)) {
320 case pn_Call_X_except:
321 case pn_Call_X_regular:
322 set_irn_link(node, ctx->proj_list);
323 ctx->proj_list = node;
329 } /* collect_nothrow_calls */
332 * Fix the list of collected nothrow Calls.
334 * @param irg the graph that contained calls to pure functions
335 * @param call_list the list of all call sites of const functions
336 * @param proj_list the list of all memory/exception Proj's of this call sites
338 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
340 ir_node *call, *next, *proj;
343 /* First step: go through the list of calls and mark them. */
344 for (call = call_list; call; call = next) {
345 next = get_irn_link(call);
347 /* current_ir_graph is in memory anyway, so it's a good marker */
348 set_irn_link(call, ¤t_ir_graph);
349 hook_func_call(irg, call);
352 /* Second step: Remove all exception Proj's */
353 for (proj = proj_list; proj; proj = next) {
354 next = get_irn_link(proj);
355 call = get_Proj_pred(proj);
357 /* handle only marked calls */
358 if (get_irn_link(call) != ¤t_ir_graph)
361 /* kill any exception flow */
362 switch (get_Proj_proj(proj)) {
363 case pn_Call_X_except:
365 exchange(proj, get_irg_bad(irg));
367 case pn_Call_X_regular: {
368 ir_node *block = get_nodes_block(call);
370 exchange(proj, new_r_Jmp(block));
378 /* changes were done ... */
379 set_irg_outs_inconsistent(irg);
380 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
383 /* ... including exception edges */
384 set_irg_doms_inconsistent(irg);
386 } /* fix_nothrow_call_list */
389 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
390 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
391 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
392 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
393 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
396 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
399 * Calculate the bigger property of two. Handle the temporary flag right.
401 static unsigned max_property(unsigned a, unsigned b)
403 unsigned r, t = (a | b) & mtp_temporary;
407 if (a == mtp_no_property || b == mtp_no_property)
408 return mtp_no_property;
414 * Follow the memory chain starting at node and determine
417 * @return mtp_property_const if only calls of const functions are detected
418 * mtp_property_pure if only Loads and const/pure calls detected
419 * mtp_no_property else
421 static unsigned _follow_mem(ir_node *node)
423 unsigned m, mode = mtp_property_const;
428 if (mode == mtp_no_property)
429 return mtp_no_property;
431 if (irn_visited_else_mark(node))
434 switch (get_irn_opcode(node)) {
436 node = get_Proj_pred(node);
445 /* do a dfs search */
446 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
447 m = _follow_mem(get_irn_n(node, i));
448 mode = max_property(mode, m);
449 if (mode == mtp_no_property)
450 return mtp_no_property;
455 /* Beware volatile Loads are NOT allowed in pure functions. */
456 if (get_Load_volatility(node) == volatility_is_volatile)
457 return mtp_no_property;
458 mode = max_property(mode, mtp_property_pure);
459 node = get_Load_mem(node);
463 /* A call is only tolerable if its either constant or pure. */
464 ptr = get_Call_ptr(node);
465 if (is_SymConst_addr_ent(ptr)) {
466 ir_entity *ent = get_SymConst_entity(ptr);
467 ir_graph *irg = get_entity_irg(ent);
469 if (irg == get_irn_irg(node)) {
470 /* A self-recursive call. The property did not depend on this call. */
471 } else if (irg == NULL) {
472 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
473 mode = max_property(mode, m);
474 } else if (irg != NULL) {
475 /* we have a graph, analyze it. */
476 m = check_const_or_pure_function(irg, /*top=*/0);
477 mode = max_property(mode, m);
480 return mtp_no_property;
481 node = get_Call_mem(node);
485 return mtp_no_property;
491 * Follow the memory chain starting at node and determine
494 * @return mtp_property_const if only calls of const functions are detected
495 * mtp_property_pure if only Loads and const/pure calls detected
496 * mtp_no_property else
498 static unsigned follow_mem(ir_node *node, unsigned mode)
502 m = _follow_mem(node);
503 return max_property(mode, m);
507 * Check if a graph represents a const or a pure function.
509 * @param irg the graph to check
510 * @param top if set, this is the top call
512 static unsigned check_const_or_pure_function(ir_graph *irg, int top)
514 ir_node *end, *endbl;
516 unsigned prop = get_irg_additional_properties(irg);
518 if (prop & mtp_property_const) {
519 /* already marked as a const function */
520 return mtp_property_const;
522 if (prop & mtp_property_pure) {
523 /* already marked as a pure function */
524 return mtp_property_pure;
527 if (IS_IRG_READY(irg)) {
528 /* already checked */
529 return mtp_no_property;
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;
538 end = get_irg_end(irg);
539 endbl = get_nodes_block(end);
540 prop = mtp_property_const;
542 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
543 inc_irg_visited(irg);
544 /* mark the initial mem: recursion of follow_mem() stops here */
545 mark_irn_visited(get_irg_initial_mem(irg));
547 /* visit every Return */
548 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
549 ir_node *node = get_Block_cfgpred(endbl, j);
550 ir_opcode code = get_irn_opcode(node);
553 /* Bad nodes usually do NOT produce anything, so it's ok */
557 if (code == iro_Return) {
558 mem = get_Return_mem(node);
560 /* Bad nodes usually do NOT produce anything, so it's ok */
564 if (mem != get_irg_initial_mem(irg))
565 prop = max_property(prop, follow_mem(mem, prop));
567 /* Exception found. Cannot be const or pure. */
568 prop = mtp_no_property;
571 if (prop == mtp_no_property)
575 if (prop != mtp_no_property) {
576 /* check, if a keep-alive exists */
577 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
578 ir_node *kept = get_End_keepalive(end, j);
580 if (is_Block(kept)) {
581 prop = mtp_no_property;
585 if (mode_M != get_irn_mode(kept))
588 prop = max_property(prop, follow_mem(kept, prop));
589 if (prop == mtp_no_property)
594 if (prop != mtp_no_property) {
595 if (top || (prop & mtp_temporary) == 0) {
596 /* We use the temporary flag here to mark optimistic result.
597 Set the property only if we are sure that it does NOT base on
598 temporary results OR if we are at top-level. */
599 set_irg_additional_property(irg, prop & ~mtp_temporary);
606 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
608 } /* check_const_or_pure_function */
611 * Handle calls to const functions.
615 static void handle_const_Calls(env_t *ctx)
619 ctx->n_calls_SymConst = 0;
620 ctx->n_calls_Sel = 0;
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);
626 ctx->float_const_call_list = NULL;
627 ctx->nonfloat_const_call_list = NULL;
628 ctx->pure_call_list = NULL;
629 ctx->proj_list = NULL;
631 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
632 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
634 if (ctx->float_const_call_list != NULL)
635 fix_const_call_lists(irg, ctx);
636 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
638 } /* handle_const_Calls */
641 * Handle calls to nothrow functions.
645 static void handle_nothrow_Calls(env_t *ctx)
649 ctx->n_calls_SymConst = 0;
650 ctx->n_calls_Sel = 0;
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);
656 ctx->nothrow_call_list = NULL;
657 ctx->proj_list = NULL;
659 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
660 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
662 if (ctx->nothrow_call_list)
663 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
664 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
669 * Check, whether a given node represents a return value of
670 * a malloc like function (ie, new heap allocated memory).
672 * @param node the node to check
674 static int is_malloc_call_result(const ir_node *node)
676 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
677 /* Firm style high-level allocation */
680 if (is_alloc_entity != NULL && is_Call(node)) {
681 ir_node *ptr = get_Call_ptr(node);
683 if (is_Global(ptr)) {
684 ir_entity *ent = get_Global_entity(ptr);
685 return is_alloc_entity(ent);
689 } /* is_malloc_call_result */
692 * Update a property depending on a call property.
694 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;
699 } /** update_property */
702 * Check if a node is stored.
704 static int is_stored(const ir_node *n)
706 const ir_edge_t *edge;
709 foreach_out_edge(n, edge) {
710 const ir_node *succ = get_edge_src_irn(edge);
712 switch (get_irn_opcode(succ)) {
719 if (get_Store_value(succ) == n)
721 /* ok if its only the address input */
730 ptr = get_Call_ptr(succ);
731 if (is_Global(ptr)) {
732 ir_entity *ent = get_Global_entity(ptr);
735 /* we know the called entity */
736 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
737 if (get_Call_param(succ, i) == n) {
738 /* n is the i'th param of the call */
739 if (get_method_param_access(ent, i) & ptr_access_store) {
740 /* n is store in ent */
746 /* unknown call address */
751 /* bad, potential alias */
759 * Check that the return value of an irg is not stored anywhere.
761 * return ~mtp_property_malloc if return values are stored, ~0 else
763 static unsigned check_stored_result(ir_graph *irg)
765 ir_node *end_blk = get_irg_end_block(irg);
768 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
770 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
771 ir_node *pred = get_Block_cfgpred(end_blk, i);
773 if (! is_Return(pred))
775 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
776 const ir_node *irn = get_Return_res(pred, j);
778 if (is_stored(irn)) {
779 /* bad, might create an alias */
780 res = ~mtp_property_malloc;
787 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
789 } /* check_stored_result */
792 * Check if a graph represents a nothrow or a malloc function.
794 * @param irg the graph to check
795 * @param top if set, this is the top call
797 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top)
799 ir_node *end_blk = get_irg_end_block(irg);
803 unsigned curr_prop = mtp_property_malloc | mtp_property_nothrow;
805 if (IS_IRG_READY(irg)) {
806 /* already checked */
807 return get_irg_additional_properties(irg);
809 if (IS_IRG_BUSY(irg)) {
810 /* we are still evaluate this method. Be optimistic,
811 return the best possible so far but mark the result as temporary. */
812 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
816 ent = get_irg_entity(irg);
817 mtp = get_entity_type(ent);
819 if (get_method_n_ress(mtp) <= 0)
820 curr_prop &= ~mtp_property_malloc;
822 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
823 ir_node *pred = get_Block_cfgpred(end_blk, i);
825 if (is_Return(pred)) {
826 if (curr_prop & mtp_property_malloc) {
827 /* check, if malloc is called here */
828 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
829 ir_node *res = get_Return_res(pred, j);
831 /* skip Confirms and Casts */
832 res = skip_HighLevel_ops(res);
835 res = get_Proj_pred(res);
836 if (is_malloc_call_result(res)) {
837 /* ok, this is a malloc */
838 } else if (is_Call(res)) {
839 ir_node *ptr = get_Call_ptr(res);
841 if (is_Global(ptr)) {
843 ir_entity *ent = get_Global_entity(ptr);
844 ir_graph *callee = get_entity_irg(ent);
847 /* A self-recursive call. The property did not depend on this call. */
848 } else if (callee != NULL) {
849 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
850 curr_prop = update_property(curr_prop, prop);
852 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
854 } else if (get_opt_closed_world() &&
856 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
857 /* check if all possible callees are malloc functions. */
858 int i, n_callees = get_Call_n_callees(res);
859 if (n_callees == 0) {
860 /* This is kind of strange: dying code or a Call that will raise an exception
861 when executed as there is no implementation to call. So better not
863 curr_prop &= ~mtp_property_malloc;
867 for (i = 0; i < n_callees; ++i) {
868 ir_entity *ent = get_Call_callee(res, i);
869 if (ent == unknown_entity) {
870 /* we don't know which entity is called here */
871 curr_prop &= ~mtp_property_malloc;
874 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
875 curr_prop &= ~mtp_property_malloc;
879 /* if we pass the for cycle, malloc is still ok */
882 curr_prop &= ~mtp_property_malloc;
885 /* unknown return value */
886 curr_prop &= ~mtp_property_malloc;
890 } else if (curr_prop & mtp_property_nothrow) {
891 /* exception flow detected */
892 pred = skip_Proj(pred);
895 ir_node *ptr = get_Call_ptr(pred);
897 if (is_Global(ptr)) {
899 ir_entity *ent = get_Global_entity(ptr);
900 ir_graph *callee = get_entity_irg(ent);
903 /* A self-recursive call. The property did not depend on this call. */
904 } else if (callee != NULL) {
905 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
906 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
907 curr_prop = update_property(curr_prop, prop);
909 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
910 curr_prop &= ~mtp_property_nothrow;
912 } else if (get_opt_closed_world() &&
914 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
915 /* check if all possible callees are nothrow functions. */
916 int i, n_callees = get_Call_n_callees(pred);
917 if (n_callees == 0) {
918 /* This is kind of strange: dying code or a Call that will raise an exception
919 when executed as there is no implementation to call. So better not
921 curr_prop &= ~mtp_property_nothrow;
925 for (i = 0; i < n_callees; ++i) {
926 ir_entity *ent = get_Call_callee(pred, i);
927 if (ent == unknown_entity) {
928 /* we don't know which entity is called here */
929 curr_prop &= ~mtp_property_nothrow;
932 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
933 curr_prop &= ~mtp_property_nothrow;
937 /* if we pass the for cycle, nothrow is still ok */
940 curr_prop &= ~mtp_property_nothrow;
943 /* real exception flow possible. */
944 curr_prop &= ~mtp_property_nothrow;
947 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
948 /* no need to search further */
953 if (curr_prop & mtp_property_malloc) {
955 * Note that the malloc property means not only return newly allocated
956 * memory, but also that this memory is ALIAS FREE.
957 * To ensure that, we do NOT allow that the returned memory is somewhere
960 curr_prop &= check_stored_result(irg);
963 if (curr_prop != mtp_no_property) {
964 if (top || (curr_prop & mtp_temporary) == 0) {
965 /* We use the temporary flag here to mark an optimistic result.
966 Set the property only if we are sure that it does NOT base on
967 temporary results OR if we are at top-level. */
968 set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
976 } /* check_nothrow_or_malloc */
979 * When a function was detected as "const", it might be moved out of loops.
980 * This might be dangerous if the graph can contain endless loops.
982 static void check_for_possible_endless_loops(ir_graph *irg)
987 root_loop = get_irg_loop(irg);
988 if (root_loop->flags & loop_outer_loop)
989 set_irg_additional_property(irg, mtp_property_has_loop);
993 * optimize function calls by handling const functions
995 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
998 unsigned num_const = 0;
999 unsigned num_pure = 0;
1000 unsigned num_nothrow = 0;
1001 unsigned num_malloc = 0;
1003 is_alloc_entity = callback;
1005 /* prepare: mark all graphs as not analyzed */
1006 last_idx = get_irp_last_idx();
1007 ready_set = rbitset_malloc(last_idx);
1008 busy_set = rbitset_malloc(last_idx);
1010 /* first step: detect, which functions are nothrow or malloc */
1011 DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1012 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1013 ir_graph *irg = get_irp_irg(i);
1014 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1016 if (prop & mtp_property_nothrow) {
1018 DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1019 } else if (prop & mtp_property_malloc) {
1021 DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1025 /* second step: remove exception edges: this must be done before the
1026 detection of const and pure functions take place. */
1027 if (force_run || num_nothrow > 0) {
1030 handle_nothrow_Calls(&ctx);
1031 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1032 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1033 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1035 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1038 rbitset_clear_all(ready_set, last_idx);
1039 rbitset_clear_all(busy_set, last_idx);
1041 /* third step: detect, which functions are const or pure */
1042 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1043 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1044 ir_graph *irg = get_irp_irg(i);
1045 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1047 if (prop & mtp_property_const) {
1049 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1050 check_for_possible_endless_loops(irg);
1051 } else if (prop & mtp_property_pure) {
1053 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1057 if (force_run || num_const > 0) {
1060 handle_const_Calls(&ctx);
1061 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1062 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1063 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1065 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1069 } /* optimize_funccalls */
1071 /* initialize the funccall optimization */
1072 void firm_init_funccalls(void)
1074 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1075 } /* firm_init_funccalls */
1078 ir_prog_pass_t pass;
1080 check_alloc_entity_func callback;
1084 * Wrapper for running optimize_funccalls() as an ir_prog pass.
1086 static int pass_wrapper(ir_prog *irp, void *context)
1088 struct pass_t *pass = context;
1091 optimize_funccalls(pass->force_run, pass->callback);
1093 } /* pass_wrapper */
1095 /* Creates an ir_prog pass for optimize_funccalls. */
1096 ir_prog_pass_t *optimize_funccalls_pass(
1098 int force_run, check_alloc_entity_func callback)
1100 struct pass_t *pass = XMALLOCZ(struct pass_t);
1102 pass->force_run = force_run;
1103 pass->callback = callback;
1105 return def_prog_pass_constructor(
1106 &pass->pass, name ? name : "funccall", pass_wrapper);
1107 } /* optimize_funccalls_pass */