2 * Copyright (C) 1995-2011 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 size_t 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 /** Ready IRG's are marked in the ready set. */
62 static unsigned *ready_set;
64 /** IRG's that are in progress are marked here. */
65 static unsigned *busy_set;
68 * We misuse the mtp_property_inherited flag as temporary here.
69 * The is ok, as we cannot set or get it anyway using the
70 * get_addtional_properties API.
72 #define mtp_temporary mtp_property_inherited
74 static bool has_compound_return_type(ir_node *node)
76 ir_type *mtp = get_Call_type(node);
77 size_t n_res = get_method_n_ress(mtp);
80 for (i = 0; i < n_res; ++i) {
81 ir_type *rtp = get_method_res_type(mtp, i);
83 if (is_compound_type(rtp)) {
92 * Walker: Collect all calls to const and pure functions
93 * to lists. Collect all Proj(Call) nodes into a Proj list.
95 static void collect_const_and_pure_calls(ir_node *node, void *env)
97 env_t *ctx = (env_t*)env;
101 unsigned and_prop, or_prop, prop;
106 /* set the link to NULL for all non-const/pure calls */
107 set_irn_link(call, NULL);
109 /* If the backend's calling convention handles compound return types
110 * via a hidden pointer argument, it is incorrect to regard this
111 * call as a call to a const/pure function.
112 * TODO: This might be overly conservative if the backend uses
113 * a different calling convention, e.g., for small structs. */
114 if (has_compound_return_type(node)) {
118 ptr = get_Call_ptr(call);
119 if (is_Global(ptr)) {
120 ent = get_Global_entity(ptr);
122 prop = get_entity_additional_properties(ent);
123 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
125 ++ctx->n_calls_SymConst;
126 } else if (get_opt_closed_world() &&
128 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
129 /* If all possible callees are const functions, we can remove the memory edge. */
130 size_t i, n_callees = get_Call_n_callees(call);
131 if (n_callees == 0) {
132 /* This is kind of strange: dying code or a Call that will raise an exception
133 when executed as there is no implementation to call. So better not
138 /* note that const function are a subset of pure ones */
139 and_prop = mtp_property_const | mtp_property_pure;
141 for (i = 0; i < n_callees; ++i) {
142 ent = get_Call_callee(call, i);
143 if (ent == unknown_entity) {
144 /* we don't know which entity is called here */
147 prop = get_entity_additional_properties(ent);
150 if (and_prop == mtp_no_property)
153 prop = and_prop | (or_prop & mtp_property_has_loop);
158 /* ok, if we get here we found a call to a const or a pure function */
159 if (prop & mtp_property_pure) {
160 set_irn_link(call, ctx->pure_call_list);
161 ctx->pure_call_list = call;
163 if (prop & mtp_property_has_loop) {
164 set_irn_link(call, ctx->nonfloat_const_call_list);
165 ctx->nonfloat_const_call_list = call;
167 set_irn_link(call, ctx->float_const_call_list);
168 ctx->float_const_call_list = call;
171 } else if (is_Proj(node)) {
173 * Collect all memory and exception Proj's from
176 call = get_Proj_pred(node);
180 /* collect the Proj's in the Proj list */
181 switch (get_Proj_proj(node)) {
183 case pn_Call_X_except:
184 case pn_Call_X_regular:
185 set_irn_link(node, ctx->proj_list);
186 ctx->proj_list = node;
192 } /* collect_const_and_pure_calls */
195 * Fix the list of collected Calls.
197 * @param irg the graph that contained calls to pure functions
200 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
202 ir_node *call, *next, *mem, *proj;
205 /* First step: fix all calls by removing their memory input and let
207 * The original memory input is preserved in their link fields. */
208 for (call = ctx->float_const_call_list; call != NULL; call = next) {
209 next = (ir_node*)get_irn_link(call);
210 mem = get_Call_mem(call);
212 set_irn_link(call, mem);
213 set_Call_mem(call, get_irg_no_mem(irg));
216 * Unfortunately we cannot simply set the node to 'float'.
217 * There is a reason for that:
219 * - The call might be inside a loop/if that is NOT entered
220 * and calls a endless function. Setting the call to float
221 * would allow to move it out from the loop/if causing this
222 * function be called even if the loop/if is not entered ...
224 * This could be fixed using post-dominators for calls and Pin nodes
225 * but need some more analyzes to ensure that a call that potential
226 * never returns is not executed before some code that generates
227 * observable states...
230 /* finally, this call can float */
231 set_irn_pinned(call, op_pin_state_floats);
232 hook_func_call(irg, call);
235 /* Last step: fix all Proj's */
236 for (proj = ctx->proj_list; proj != NULL; proj = next) {
237 next = (ir_node*)get_irn_link(proj);
238 call = get_Proj_pred(proj);
239 mem = (ir_node*)get_irn_link(call);
241 /* beware of calls in the pure call list */
242 if (!mem || is_Call(mem))
244 assert(get_irn_mode(mem) == mode_M);
246 switch (get_Proj_proj(proj)) {
248 /* in dead code there might be cycles where proj == mem */
253 case pn_Call_X_except:
255 exchange(proj, new_r_Bad(irg, mode_X));
257 case pn_Call_X_regular: {
258 ir_node *block = get_nodes_block(call);
260 exchange(proj, new_r_Jmp(block));
268 /* changes were done ... */
269 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
272 /* ... including exception edges */
273 set_irg_doms_inconsistent(irg);
275 } /* fix_const_call_list */
278 * Walker: Collect all calls to nothrow functions
279 * to lists. Collect all Proj(Call) nodes into a Proj list.
281 static void collect_nothrow_calls(ir_node *node, void *env)
283 env_t *ctx = (env_t*)env;
291 /* set the link to NULL for all non-const/pure calls */
292 set_irn_link(call, NULL);
293 ptr = get_Call_ptr(call);
294 if (is_Global(ptr)) {
295 ent = get_Global_entity(ptr);
297 prop = get_entity_additional_properties(ent);
298 if ((prop & mtp_property_nothrow) == 0)
300 ++ctx->n_calls_SymConst;
301 } else if (get_opt_closed_world() &&
303 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
304 /* If all possible callees are nothrow functions, we can remove the exception edge. */
305 size_t i, n_callees = get_Call_n_callees(call);
306 if (n_callees == 0) {
307 /* This is kind of strange: dying code or a Call that will raise an exception
308 when executed as there is no implementation to call. So better not
313 /* note that const function are a subset of pure ones */
314 prop = mtp_property_nothrow;
315 for (i = 0; i < n_callees; ++i) {
316 ent = get_Call_callee(call, i);
317 if (ent == unknown_entity) {
318 /* we don't know which entity is called here */
321 prop &= get_entity_additional_properties(ent);
322 if (prop == mtp_no_property)
329 /* ok, if we get here we found a call to a nothrow function */
330 set_irn_link(call, ctx->nothrow_call_list);
331 ctx->nothrow_call_list = call;
332 } else if (is_Proj(node)) {
334 * Collect all memory and exception Proj's from
337 call = get_Proj_pred(node);
341 /* collect the Proj's in the Proj list */
342 switch (get_Proj_proj(node)) {
344 case pn_Call_X_except:
345 case pn_Call_X_regular:
346 set_irn_link(node, ctx->proj_list);
347 ctx->proj_list = node;
353 } /* collect_nothrow_calls */
356 * Fix the list of collected nothrow Calls.
358 * @param irg the graph that contained calls to pure functions
359 * @param call_list the list of all call sites of const functions
360 * @param proj_list the list of all memory/exception Proj's of this call sites
362 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
364 ir_node *call, *next, *proj;
367 /* First step: go through the list of calls and mark them. */
368 for (call = call_list; call; call = next) {
369 next = (ir_node*)get_irn_link(call);
371 /* current_ir_graph is in memory anyway, so it's a good marker */
372 set_irn_link(call, ¤t_ir_graph);
373 hook_func_call(irg, call);
376 /* Second step: Remove all exception Proj's */
377 for (proj = proj_list; proj; proj = next) {
378 next = (ir_node*)get_irn_link(proj);
379 call = get_Proj_pred(proj);
381 /* handle only marked calls */
382 if (get_irn_link(call) != ¤t_ir_graph)
385 /* kill any exception flow */
386 switch (get_Proj_proj(proj)) {
387 case pn_Call_X_except:
389 exchange(proj, new_r_Bad(irg, mode_X));
391 case pn_Call_X_regular: {
392 ir_node *block = get_nodes_block(call);
394 exchange(proj, new_r_Jmp(block));
402 /* changes were done ... */
403 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
406 /* ... including exception edges */
407 set_irg_doms_inconsistent(irg);
409 } /* fix_nothrow_call_list */
412 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
413 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
414 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
415 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
416 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
419 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top);
422 * Calculate the bigger property of two. Handle the temporary flag right.
424 static mtp_additional_properties max_property(mtp_additional_properties a,
425 mtp_additional_properties b)
427 mtp_additional_properties r;
428 mtp_additional_properties t = (a | b) & mtp_temporary;
432 if (a == mtp_no_property || b == mtp_no_property)
433 return mtp_no_property;
439 * Follow the memory chain starting at node and determine
442 * @return mtp_property_const if only calls of const functions are detected
443 * mtp_property_pure if only Loads and const/pure calls detected
444 * mtp_no_property else
446 static mtp_additional_properties follow_mem_(ir_node *node)
448 mtp_additional_properties mode = mtp_property_const;
449 mtp_additional_properties m;
454 if (mode == mtp_no_property)
455 return mtp_no_property;
457 if (irn_visited_else_mark(node))
460 switch (get_irn_opcode(node)) {
462 node = get_Proj_pred(node);
471 /* do a dfs search */
472 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
473 m = follow_mem_(get_irn_n(node, i));
474 mode = max_property(mode, m);
475 if (mode == mtp_no_property)
476 return mtp_no_property;
481 /* Beware volatile Loads are NOT allowed in pure functions. */
482 if (get_Load_volatility(node) == volatility_is_volatile)
483 return mtp_no_property;
484 mode = max_property(mode, mtp_property_pure);
485 node = get_Load_mem(node);
489 /* A call is only tolerable if its either constant or pure. */
490 ptr = get_Call_ptr(node);
491 if (is_SymConst_addr_ent(ptr)) {
492 ir_entity *ent = get_SymConst_entity(ptr);
493 ir_graph *irg = get_entity_irg(ent);
496 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
497 mode = max_property(mode, m);
499 /* we have a graph, analyze it. */
500 m = check_const_or_pure_function(irg, /*top=*/0);
501 mode = max_property(mode, m);
504 return mtp_no_property;
505 node = get_Call_mem(node);
509 return mtp_no_property;
515 * Follow the memory chain starting at node and determine
518 * @return mtp_property_const if only calls of const functions are detected
519 * mtp_property_pure if only Loads and const/pure calls detected
520 * mtp_no_property else
522 static mtp_additional_properties follow_mem(ir_node *node, mtp_additional_properties mode)
524 mtp_additional_properties m = follow_mem_(node);
525 return max_property(mode, m);
529 * Check if a graph represents a const or a pure function.
531 * @param irg the graph to check
532 * @param top if set, this is the top call
534 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top)
536 ir_node *end, *endbl;
538 mtp_additional_properties prop = get_irg_additional_properties(irg);
540 if (prop & mtp_property_const) {
541 /* already marked as a const function */
542 return mtp_property_const;
544 if (prop & mtp_property_pure) {
545 /* already marked as a pure function */
546 return mtp_property_pure;
549 if (IS_IRG_READY(irg)) {
550 /* already checked */
551 return mtp_no_property;
553 if (IS_IRG_BUSY(irg)) {
554 /* We are still evaluate this method.
555 * The function (indirectly) calls itself and thus may not terminate.
557 return mtp_no_property;
561 end = get_irg_end(irg);
562 endbl = get_nodes_block(end);
563 prop = mtp_property_const;
565 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
566 inc_irg_visited(irg);
567 /* mark the initial mem: recursion of follow_mem() stops here */
568 mark_irn_visited(get_irg_initial_mem(irg));
570 /* visit every Return */
571 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
572 ir_node *node = get_Block_cfgpred(endbl, j);
573 unsigned code = get_irn_opcode(node);
576 /* Bad nodes usually do NOT produce anything, so it's ok */
580 if (code == iro_Return) {
581 mem = get_Return_mem(node);
583 /* Bad nodes usually do NOT produce anything, so it's ok */
587 if (mem != get_irg_initial_mem(irg))
588 prop = max_property(prop, follow_mem(mem, prop));
590 /* Exception found. Cannot be const or pure. */
591 prop = mtp_no_property;
594 if (prop == mtp_no_property)
598 if (prop != mtp_no_property) {
599 /* check, if a keep-alive exists */
600 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
601 ir_node *kept = get_End_keepalive(end, j);
603 if (is_Block(kept)) {
604 prop = mtp_no_property;
608 if (mode_M != get_irn_mode(kept))
611 prop = max_property(prop, follow_mem(kept, prop));
612 if (prop == mtp_no_property)
618 /* Set the property only if we are at top-level. */
619 if (prop != mtp_no_property) {
620 add_irg_additional_properties(irg, prop);
625 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
627 } /* check_const_or_pure_function */
630 * Handle calls to const functions.
634 static void handle_const_Calls(env_t *ctx)
638 ctx->n_calls_SymConst = 0;
639 ctx->n_calls_Sel = 0;
641 /* all calls of const functions can be transformed */
642 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
643 ir_graph *irg = get_irp_irg(i);
645 ctx->float_const_call_list = NULL;
646 ctx->nonfloat_const_call_list = NULL;
647 ctx->pure_call_list = NULL;
648 ctx->proj_list = NULL;
650 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
651 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
653 if (ctx->float_const_call_list != NULL)
654 fix_const_call_lists(irg, ctx);
655 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
657 } /* handle_const_Calls */
660 * Handle calls to nothrow functions.
664 static void handle_nothrow_Calls(env_t *ctx)
668 ctx->n_calls_SymConst = 0;
669 ctx->n_calls_Sel = 0;
671 /* all calls of const functions can be transformed */
672 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
673 ir_graph *irg = get_irp_irg(i);
675 ctx->nothrow_call_list = NULL;
676 ctx->proj_list = NULL;
678 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
679 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
681 if (ctx->nothrow_call_list)
682 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
683 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
688 * Check, whether a given node represents a return value of
689 * a malloc like function (ie, new heap allocated memory).
691 * @param node the node to check
693 static int is_malloc_call_result(const ir_node *node)
695 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
696 /* Firm style high-level allocation */
699 /* TODO: check mtp_malloc */
704 * Update a property depending on a call property.
706 static mtp_additional_properties update_property(mtp_additional_properties orig_prop, mtp_additional_properties call_prop)
708 mtp_additional_properties t = (orig_prop | call_prop) & mtp_temporary;
709 mtp_additional_properties r = orig_prop & call_prop;
714 * Check if a node is stored.
716 static int is_stored(const ir_node *n)
718 const ir_edge_t *edge;
721 foreach_out_edge(n, edge) {
722 const ir_node *succ = get_edge_src_irn(edge);
724 switch (get_irn_opcode(succ)) {
731 if (get_Store_value(succ) == n)
733 /* ok if its only the address input */
742 ptr = get_Call_ptr(succ);
743 if (is_Global(ptr)) {
744 ir_entity *ent = get_Global_entity(ptr);
747 /* we know the called entity */
748 for (i = get_Call_n_params(succ); i > 0;) {
749 if (get_Call_param(succ, --i) == n) {
750 /* n is the i'th param of the call */
751 if (get_method_param_access(ent, i) & ptr_access_store) {
752 /* n is store in ent */
758 /* unknown call address */
763 /* bad, potential alias */
771 * Check that the return value of an irg is not stored anywhere.
773 * return ~mtp_property_malloc if return values are stored, ~0 else
775 static mtp_additional_properties check_stored_result(ir_graph *irg)
777 ir_node *end_blk = get_irg_end_block(irg);
779 mtp_additional_properties res = ~mtp_no_property;
780 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
782 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
783 ir_node *pred = get_Block_cfgpred(end_blk, i);
786 if (! is_Return(pred))
788 for (j = get_Return_n_ress(pred); j > 0;) {
789 const ir_node *irn = get_Return_res(pred, --j);
791 if (is_stored(irn)) {
792 /* bad, might create an alias */
793 res = ~mtp_property_malloc;
800 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
805 * Check if a graph represents a nothrow or a malloc function.
807 * @param irg the graph to check
808 * @param top if set, this is the top call
810 static mtp_additional_properties check_nothrow_or_malloc(ir_graph *irg, int top)
812 mtp_additional_properties curr_prop = mtp_property_malloc | mtp_property_nothrow;
813 ir_node *end_blk = get_irg_end_block(irg);
818 if (IS_IRG_READY(irg)) {
819 /* already checked */
820 return get_irg_additional_properties(irg);
822 if (IS_IRG_BUSY(irg)) {
823 /* we are still evaluate this method. Be optimistic,
824 return the best possible so far but mark the result as temporary. */
825 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
829 ent = get_irg_entity(irg);
830 mtp = get_entity_type(ent);
832 if (get_method_n_ress(mtp) <= 0)
833 curr_prop &= ~mtp_property_malloc;
835 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
836 ir_node *pred = get_Block_cfgpred(end_blk, i);
838 if (is_Return(pred)) {
839 if (curr_prop & mtp_property_malloc) {
842 /* check, if malloc is called here */
843 for (j = get_Return_n_ress(pred); j > 0;) {
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 mtp_additional_properties 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 size_t 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 mtp_additional_properties 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 size_t 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 add_irg_additional_properties(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 add_irg_additional_properties(irg, mtp_property_has_loop);
1008 * optimize function calls by handling const functions
1010 void optimize_funccalls(void)
1015 size_t num_const = 0;
1016 size_t num_pure = 0;
1017 size_t num_nothrow = 0;
1018 size_t num_malloc = 0;
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 = 0, n = get_irp_n_irgs(); i < n; ++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 handle_nothrow_Calls(&ctx);
1043 DB((dbg, LEVEL_1, "Detected %zu nothrow graphs, %zu malloc graphs.\n", num_nothrow, num_malloc));
1044 DB((dbg, LEVEL_1, "Optimizes %zu(SymConst) + %zu(Sel) calls to nothrow functions.\n",
1045 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1047 rbitset_clear_all(ready_set, last_idx);
1048 rbitset_clear_all(busy_set, last_idx);
1050 /* third step: detect, which functions are const or pure */
1051 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1052 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
1053 ir_graph *irg = get_irp_irg(i);
1054 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1056 if (prop & mtp_property_const) {
1058 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1059 check_for_possible_endless_loops(irg);
1060 } else if (prop & mtp_property_pure) {
1062 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1066 handle_const_Calls(&ctx);
1067 DB((dbg, LEVEL_1, "Detected %zu const graphs, %zu pure graphs.\n", num_const, num_pure));
1068 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1069 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1075 /* initialize the funccall optimization */
1076 void firm_init_funccalls(void)
1078 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1081 /* Creates an ir_prog pass for optimize_funccalls. */
1082 ir_prog_pass_t *optimize_funccalls_pass(const char *name)
1084 return def_prog_pass(name ? name : "funccall", optimize_funccalls);