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
30 #include "irgraph_t.h"
33 #include "dbginfo_t.h"
37 #include "iredges_t.h"
39 #include "iroptimize.h"
40 #include "analyze_irg_args.h"
42 #include "raw_bitset.h"
45 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
48 * The walker environment for updating function calls.
50 typedef struct env_t {
51 size_t n_calls_SymConst;
53 ir_node *float_const_call_list; /**< The list of all floating const function calls that will be changed. */
54 ir_node *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
55 ir_node *pure_call_list; /**< The list of all pure function calls that will be changed. */
56 ir_node *nothrow_call_list; /**< The list of all nothrow function calls that will be changed. */
57 ir_node *proj_list; /**< The list of all potential Proj nodes that must be fixed. */
60 /** Ready IRG's are marked in the ready set. */
61 static unsigned *ready_set;
63 /** IRG's that are in progress are marked here. */
64 static unsigned *busy_set;
67 * We misuse the mtp_property_inherited flag as temporary here.
68 * The is ok, as we cannot set or get it anyway using the
69 * get_addtional_properties API.
71 #define mtp_temporary mtp_property_inherited
74 * Walker: Collect all calls to const and pure functions
75 * to lists. Collect all Proj(Call) nodes into a Proj list.
77 static void collect_const_and_pure_calls(ir_node *node, void *env)
79 env_t *ctx = (env_t*)env;
83 unsigned and_prop, or_prop, prop;
88 /* set the link to NULL for all non-const/pure calls */
89 set_irn_link(call, NULL);
90 ptr = get_Call_ptr(call);
91 if (is_SymConst_addr_ent(ptr)) {
92 ent = get_SymConst_entity(ptr);
94 prop = get_entity_additional_properties(ent);
95 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
97 ++ctx->n_calls_SymConst;
98 } else if (get_opt_closed_world() &&
100 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
101 /* If all possible callees are const functions, we can remove the memory edge. */
102 size_t i, n_callees = get_Call_n_callees(call);
103 if (n_callees == 0) {
104 /* This is kind of strange: dying code or a Call that will raise an exception
105 when executed as there is no implementation to call. So better not
110 /* note that const function are a subset of pure ones */
111 and_prop = mtp_property_const | mtp_property_pure;
113 for (i = 0; i < n_callees; ++i) {
114 ent = get_Call_callee(call, i);
115 if (is_unknown_entity(ent)) {
116 /* we don't know which entity is called here */
119 prop = get_entity_additional_properties(ent);
122 if (and_prop == mtp_no_property)
125 prop = and_prop | (or_prop & mtp_property_has_loop);
130 /* ok, if we get here we found a call to a const or a pure function */
131 if (prop & mtp_property_pure) {
132 set_irn_link(call, ctx->pure_call_list);
133 ctx->pure_call_list = call;
135 if (prop & mtp_property_has_loop) {
136 set_irn_link(call, ctx->nonfloat_const_call_list);
137 ctx->nonfloat_const_call_list = call;
139 set_irn_link(call, ctx->float_const_call_list);
140 ctx->float_const_call_list = call;
143 } else if (is_Proj(node)) {
145 * Collect all memory and exception Proj's from
148 call = get_Proj_pred(node);
152 /* collect the Proj's in the Proj list */
153 switch (get_Proj_proj(node)) {
155 case pn_Call_X_except:
156 case pn_Call_X_regular:
157 set_irn_link(node, ctx->proj_list);
158 ctx->proj_list = node;
164 } /* collect_const_and_pure_calls */
167 * Fix the list of collected Calls.
169 * @param irg the graph that contained calls to pure functions
172 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
174 ir_node *call, *next, *mem, *proj;
177 /* First step: fix all calls by removing their memory input and let
179 * The original memory input is preserved in their link fields. */
180 for (call = ctx->float_const_call_list; call != NULL; call = next) {
181 next = (ir_node*)get_irn_link(call);
182 mem = get_Call_mem(call);
184 set_irn_link(call, mem);
185 set_Call_mem(call, get_irg_no_mem(irg));
188 * Unfortunately we cannot simply set the node to 'float'.
189 * There is a reason for that:
191 * - The call might be inside a loop/if that is NOT entered
192 * and calls a endless function. Setting the call to float
193 * would allow to move it out from the loop/if causing this
194 * function be called even if the loop/if is not entered ...
196 * This could be fixed using post-dominators for calls and Pin nodes
197 * but need some more analyzes to ensure that a call that potential
198 * never returns is not executed before some code that generates
199 * observable states...
202 /* finally, this call can float */
203 set_irn_pinned(call, op_pin_state_floats);
204 hook_func_call(irg, call);
207 /* Last step: fix all Proj's */
208 for (proj = ctx->proj_list; proj != NULL; proj = next) {
209 next = (ir_node*)get_irn_link(proj);
210 call = get_Proj_pred(proj);
211 mem = (ir_node*)get_irn_link(call);
213 /* beware of calls in the pure call list */
214 if (!mem || is_Call(mem))
216 assert(get_irn_mode(mem) == mode_M);
218 switch (get_Proj_proj(proj)) {
220 /* in dead code there might be cycles where proj == mem */
225 case pn_Call_X_except:
227 exchange(proj, new_r_Bad(irg, mode_X));
229 case pn_Call_X_regular: {
230 ir_node *block = get_nodes_block(call);
232 exchange(proj, new_r_Jmp(block));
241 /* ... including exception edges */
242 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
243 | IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
245 } /* fix_const_call_list */
248 * Walker: Collect all calls to nothrow functions
249 * to lists. Collect all Proj(Call) nodes into a Proj list.
251 static void collect_nothrow_calls(ir_node *node, void *env)
253 env_t *ctx = (env_t*)env;
261 /* set the link to NULL for all non-const/pure calls */
262 set_irn_link(call, NULL);
263 ptr = get_Call_ptr(call);
264 if (is_SymConst_addr_ent(ptr)) {
265 ent = get_SymConst_entity(ptr);
267 prop = get_entity_additional_properties(ent);
268 if ((prop & mtp_property_nothrow) == 0)
270 ++ctx->n_calls_SymConst;
271 } else if (get_opt_closed_world() &&
273 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
274 /* If all possible callees are nothrow functions, we can remove the exception edge. */
275 size_t 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
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 (is_unknown_entity(ent)) {
288 /* we don't know which entity is called here */
291 prop &= get_entity_additional_properties(ent);
292 if (prop == mtp_no_property)
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)) {
304 * Collect all memory and exception Proj's from
307 call = get_Proj_pred(node);
311 /* collect the Proj's in the Proj list */
312 switch (get_Proj_proj(node)) {
314 case pn_Call_X_except:
315 case pn_Call_X_regular:
316 set_irn_link(node, ctx->proj_list);
317 ctx->proj_list = node;
323 } /* collect_nothrow_calls */
326 * Fix the list of collected nothrow Calls.
328 * @param irg the graph that contained calls to pure functions
329 * @param call_list the list of all call sites of const functions
330 * @param proj_list the list of all memory/exception Proj's of this call sites
332 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
334 ir_node *call, *next, *proj;
337 /* First step: go through the list of calls and mark them. */
338 for (call = call_list; call; call = next) {
339 next = (ir_node*)get_irn_link(call);
341 /* current_ir_graph is in memory anyway, so it's a good marker */
342 set_irn_link(call, ¤t_ir_graph);
343 hook_func_call(irg, call);
346 /* Second step: Remove all exception Proj's */
347 for (proj = proj_list; proj; proj = next) {
348 next = (ir_node*)get_irn_link(proj);
349 call = get_Proj_pred(proj);
351 /* handle only marked calls */
352 if (get_irn_link(call) != ¤t_ir_graph)
355 /* kill any exception flow */
356 switch (get_Proj_proj(proj)) {
357 case pn_Call_X_except:
359 exchange(proj, new_r_Bad(irg, mode_X));
361 case pn_Call_X_regular: {
362 ir_node *block = get_nodes_block(call);
364 exchange(proj, new_r_Jmp(block));
372 /* changes were done ... */
374 /* ... including exception edges */
375 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
376 | IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
378 } /* fix_nothrow_call_list */
381 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
382 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
383 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
384 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
385 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
388 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top);
391 * Calculate the bigger property of two. Handle the temporary flag right.
393 static mtp_additional_properties max_property(mtp_additional_properties a,
394 mtp_additional_properties b)
396 mtp_additional_properties r;
397 mtp_additional_properties t = (a | b) & mtp_temporary;
401 if (a == mtp_no_property || b == mtp_no_property)
402 return mtp_no_property;
408 * Follow the memory chain starting at node and determine
411 * @return mtp_property_const if only calls of const functions are detected
412 * mtp_property_pure if only Loads and const/pure calls detected
413 * mtp_no_property else
415 static mtp_additional_properties follow_mem_(ir_node *node)
417 mtp_additional_properties mode = mtp_property_const;
418 mtp_additional_properties m;
423 if (mode == mtp_no_property)
424 return mtp_no_property;
426 if (irn_visited_else_mark(node))
429 switch (get_irn_opcode(node)) {
431 node = get_Proj_pred(node);
440 /* do a dfs search */
441 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
442 m = follow_mem_(get_irn_n(node, i));
443 mode = max_property(mode, m);
444 if (mode == mtp_no_property)
445 return mtp_no_property;
450 /* Beware volatile Loads are NOT allowed in pure functions. */
451 if (get_Load_volatility(node) == volatility_is_volatile)
452 return mtp_no_property;
453 mode = max_property(mode, mtp_property_pure);
454 node = get_Load_mem(node);
458 /* A call is only tolerable if its either constant or pure. */
459 ptr = get_Call_ptr(node);
460 if (is_SymConst_addr_ent(ptr)) {
461 ir_entity *ent = get_SymConst_entity(ptr);
462 ir_graph *irg = get_entity_irg(ent);
465 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
466 mode = max_property(mode, m);
468 /* we have a graph, analyze it. */
469 m = check_const_or_pure_function(irg, /*top=*/0);
470 mode = max_property(mode, m);
473 return mtp_no_property;
474 node = get_Call_mem(node);
478 return mtp_no_property;
484 * Follow the memory chain starting at node and determine
487 * @return mtp_property_const if only calls of const functions are detected
488 * mtp_property_pure if only Loads and const/pure calls detected
489 * mtp_no_property else
491 static mtp_additional_properties follow_mem(ir_node *node, mtp_additional_properties mode)
493 mtp_additional_properties m = follow_mem_(node);
494 return max_property(mode, m);
498 * Check if a graph represents a const or a pure function.
500 * @param irg the graph to check
501 * @param top if set, this is the top call
503 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top)
505 ir_node *end, *endbl;
507 ir_entity *entity = get_irg_entity(irg);
508 ir_type *type = get_entity_type(entity);
509 size_t n_params = get_method_n_params(type);
511 mtp_additional_properties may_be_const = mtp_property_const;
512 mtp_additional_properties prop = get_irg_additional_properties(irg);
514 /* libfirm handles aggregate parameters by passing around pointers to
515 * stuff in memory, so if we have compound parameters we are never const */
516 for (i = 0; i < n_params; ++i) {
517 ir_type *param = get_method_param_type(type, i);
518 if (is_compound_type(param)) {
519 prop &= ~mtp_property_const;
520 may_be_const = mtp_no_property;
524 if (prop & mtp_property_const) {
525 /* already marked as a const function */
526 return mtp_property_const;
528 if (prop & mtp_property_pure) {
529 /* already marked as a pure function */
530 return mtp_property_pure;
533 if (IS_IRG_READY(irg)) {
534 /* already checked */
535 return mtp_no_property;
537 if (IS_IRG_BUSY(irg)) {
538 /* We are still evaluate this method.
539 * The function (indirectly) calls itself and thus may not terminate.
541 return mtp_no_property;
545 end = get_irg_end(irg);
546 endbl = get_nodes_block(end);
549 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
550 inc_irg_visited(irg);
551 /* mark the initial mem: recursion of follow_mem() stops here */
552 mark_irn_visited(get_irg_initial_mem(irg));
554 /* visit every Return */
555 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
556 ir_node *node = get_Block_cfgpred(endbl, j);
557 unsigned code = get_irn_opcode(node);
560 /* Bad nodes usually do NOT produce anything, so it's ok */
564 if (code == iro_Return) {
565 mem = get_Return_mem(node);
567 /* Bad nodes usually do NOT produce anything, so it's ok */
571 if (mem != get_irg_initial_mem(irg))
572 prop = max_property(prop, follow_mem(mem, prop));
574 /* Exception found. Cannot be const or pure. */
575 prop = mtp_no_property;
578 if (prop == mtp_no_property)
582 if (prop != mtp_no_property) {
583 /* check, if a keep-alive exists */
584 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
585 ir_node *kept = get_End_keepalive(end, j);
587 if (is_Block(kept)) {
588 prop = mtp_no_property;
592 if (mode_M != get_irn_mode(kept))
595 prop = max_property(prop, follow_mem(kept, prop));
596 if (prop == mtp_no_property)
602 /* Set the property only if we are at top-level. */
603 if (prop != mtp_no_property) {
604 add_irg_additional_properties(irg, prop);
609 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
611 } /* check_const_or_pure_function */
614 * Handle calls to const functions.
618 static void handle_const_Calls(env_t *ctx)
622 ctx->n_calls_SymConst = 0;
623 ctx->n_calls_Sel = 0;
625 /* all calls of const functions can be transformed */
626 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
627 ir_graph *irg = get_irp_irg(i);
629 ctx->float_const_call_list = NULL;
630 ctx->nonfloat_const_call_list = NULL;
631 ctx->pure_call_list = NULL;
632 ctx->proj_list = NULL;
634 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
635 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
637 if (ctx->float_const_call_list != NULL)
638 fix_const_call_lists(irg, ctx);
639 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
641 } /* handle_const_Calls */
644 * Handle calls to nothrow functions.
648 static void handle_nothrow_Calls(env_t *ctx)
652 ctx->n_calls_SymConst = 0;
653 ctx->n_calls_Sel = 0;
655 /* all calls of const functions can be transformed */
656 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
657 ir_graph *irg = get_irp_irg(i);
659 ctx->nothrow_call_list = NULL;
660 ctx->proj_list = NULL;
662 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
663 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
665 if (ctx->nothrow_call_list)
666 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
667 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
672 * Check, whether a given node represents a return value of
673 * a malloc like function (ie, new heap allocated memory).
675 * @param node the node to check
677 static int is_malloc_call_result(const ir_node *node)
679 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
680 /* Firm style high-level allocation */
683 /* TODO: check mtp_malloc */
688 * Update a property depending on a call property.
690 static mtp_additional_properties update_property(mtp_additional_properties orig_prop, mtp_additional_properties call_prop)
692 mtp_additional_properties t = (orig_prop | call_prop) & mtp_temporary;
693 mtp_additional_properties r = orig_prop & call_prop;
698 * Check if a node is stored.
700 static int is_stored(const ir_node *n)
702 const ir_edge_t *edge;
705 foreach_out_edge(n, edge) {
706 const ir_node *succ = get_edge_src_irn(edge);
708 switch (get_irn_opcode(succ)) {
715 if (get_Store_value(succ) == n)
717 /* ok if its only the address input */
726 ptr = get_Call_ptr(succ);
727 if (is_SymConst_addr_ent(ptr)) {
728 ir_entity *ent = get_SymConst_entity(ptr);
731 /* we know the called entity */
732 for (i = get_Call_n_params(succ); i > 0;) {
733 if (get_Call_param(succ, --i) == n) {
734 /* n is the i'th param of the call */
735 if (get_method_param_access(ent, i) & ptr_access_store) {
736 /* n is store in ent */
742 /* unknown call address */
747 /* bad, potential alias */
755 * Check that the return value of an irg is not stored anywhere.
757 * return ~mtp_property_malloc if return values are stored, ~0 else
759 static mtp_additional_properties check_stored_result(ir_graph *irg)
761 ir_node *end_blk = get_irg_end_block(irg);
763 mtp_additional_properties res = ~mtp_no_property;
764 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
766 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
767 ir_node *pred = get_Block_cfgpred(end_blk, i);
770 if (! is_Return(pred))
772 for (j = get_Return_n_ress(pred); j > 0;) {
773 const ir_node *irn = get_Return_res(pred, --j);
775 if (is_stored(irn)) {
776 /* bad, might create an alias */
777 res = ~mtp_property_malloc;
784 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
789 * Check if a graph represents a nothrow or a malloc function.
791 * @param irg the graph to check
792 * @param top if set, this is the top call
794 static mtp_additional_properties check_nothrow_or_malloc(ir_graph *irg, int top)
796 mtp_additional_properties curr_prop = mtp_property_malloc | mtp_property_nothrow;
797 ir_node *end_blk = get_irg_end_block(irg);
802 if (IS_IRG_READY(irg)) {
803 /* already checked */
804 return get_irg_additional_properties(irg);
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;
813 ent = get_irg_entity(irg);
814 mtp = get_entity_type(ent);
816 if (get_method_n_ress(mtp) <= 0)
817 curr_prop &= ~mtp_property_malloc;
819 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
820 ir_node *pred = get_Block_cfgpred(end_blk, i);
822 if (is_Return(pred)) {
823 if (curr_prop & mtp_property_malloc) {
826 /* check, if malloc is called here */
827 for (j = get_Return_n_ress(pred); j > 0;) {
828 ir_node *res = get_Return_res(pred, --j);
830 /* skip Confirms and Casts */
831 res = skip_HighLevel_ops(res);
834 res = get_Proj_pred(res);
835 if (is_malloc_call_result(res)) {
836 /* ok, this is a malloc */
837 } else if (is_Call(res)) {
838 ir_node *ptr = get_Call_ptr(res);
840 if (is_SymConst_addr_ent(ptr)) {
842 ir_entity *ent = get_SymConst_entity(ptr);
843 ir_graph *callee = get_entity_irg(ent);
846 /* A self-recursive call. The property did not depend on this call. */
847 } else if (callee != NULL) {
848 mtp_additional_properties prop = check_nothrow_or_malloc(callee, /*top=*/0);
849 curr_prop = update_property(curr_prop, prop);
851 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
853 } else if (get_opt_closed_world() &&
855 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
856 /* check if all possible callees are malloc functions. */
857 size_t i, n_callees = get_Call_n_callees(res);
858 if (n_callees == 0) {
859 /* This is kind of strange: dying code or a Call that will raise an exception
860 when executed as there is no implementation to call. So better not
862 curr_prop &= ~mtp_property_malloc;
866 for (i = 0; i < n_callees; ++i) {
867 ir_entity *ent = get_Call_callee(res, i);
868 if (is_unknown_entity(ent)) {
869 /* we don't know which entity is called here */
870 curr_prop &= ~mtp_property_malloc;
873 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
874 curr_prop &= ~mtp_property_malloc;
878 /* if we pass the for cycle, malloc is still ok */
881 curr_prop &= ~mtp_property_malloc;
884 /* unknown return value */
885 curr_prop &= ~mtp_property_malloc;
889 } else if (curr_prop & mtp_property_nothrow) {
890 /* exception flow detected */
891 pred = skip_Proj(pred);
894 ir_node *ptr = get_Call_ptr(pred);
896 if (is_SymConst_addr_ent(ptr)) {
898 ir_entity *ent = get_SymConst_entity(ptr);
899 ir_graph *callee = get_entity_irg(ent);
902 /* A self-recursive call. The property did not depend on this call. */
903 } else if (callee != NULL) {
904 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
905 mtp_additional_properties prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
906 curr_prop = update_property(curr_prop, prop);
908 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
909 curr_prop &= ~mtp_property_nothrow;
911 } else if (get_opt_closed_world() &&
913 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
914 /* check if all possible callees are nothrow functions. */
915 size_t i, n_callees = get_Call_n_callees(pred);
916 if (n_callees == 0) {
917 /* This is kind of strange: dying code or a Call that will raise an exception
918 when executed as there is no implementation to call. So better not
920 curr_prop &= ~mtp_property_nothrow;
924 for (i = 0; i < n_callees; ++i) {
925 ir_entity *ent = get_Call_callee(pred, i);
926 if (is_unknown_entity(ent)) {
927 /* we don't know which entity is called here */
928 curr_prop &= ~mtp_property_nothrow;
931 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
932 curr_prop &= ~mtp_property_nothrow;
936 /* if we pass the for cycle, nothrow is still ok */
939 curr_prop &= ~mtp_property_nothrow;
942 /* real exception flow possible. */
943 curr_prop &= ~mtp_property_nothrow;
946 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
947 /* no need to search further */
952 if (curr_prop & mtp_property_malloc) {
954 * Note that the malloc property means not only return newly allocated
955 * memory, but also that this memory is ALIAS FREE.
956 * To ensure that, we do NOT allow that the returned memory is somewhere
959 curr_prop &= check_stored_result(irg);
962 if (curr_prop != mtp_no_property) {
963 if (top || (curr_prop & mtp_temporary) == 0) {
964 /* We use the temporary flag here to mark an optimistic result.
965 Set the property only if we are sure that it does NOT base on
966 temporary results OR if we are at top-level. */
967 add_irg_additional_properties(irg, curr_prop & ~mtp_temporary);
975 } /* check_nothrow_or_malloc */
978 * When a function was detected as "const", it might be moved out of loops.
979 * This might be dangerous if the graph can contain endless loops.
981 static void check_for_possible_endless_loops(ir_graph *irg)
984 assure_loopinfo(irg);
986 root_loop = get_irg_loop(irg);
987 if (root_loop->flags & loop_outer_loop)
988 add_irg_additional_properties(irg, mtp_property_has_loop);
992 * optimize function calls by handling const functions
994 void optimize_funccalls(void)
999 size_t num_const = 0;
1000 size_t num_pure = 0;
1001 size_t num_nothrow = 0;
1002 size_t num_malloc = 0;
1004 /* prepare: mark all graphs as not analyzed */
1005 last_idx = get_irp_last_idx();
1006 ready_set = rbitset_malloc(last_idx);
1007 busy_set = rbitset_malloc(last_idx);
1009 /* first step: detect, which functions are nothrow or malloc */
1010 DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1011 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
1012 ir_graph *irg = get_irp_irg(i);
1013 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1015 if (prop & mtp_property_nothrow) {
1017 DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1018 } else if (prop & mtp_property_malloc) {
1020 DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1024 /* second step: remove exception edges: this must be done before the
1025 detection of const and pure functions take place. */
1026 handle_nothrow_Calls(&ctx);
1027 DB((dbg, LEVEL_1, "Detected %zu nothrow graphs, %zu malloc graphs.\n", num_nothrow, num_malloc));
1028 DB((dbg, LEVEL_1, "Optimizes %zu(SymConst) + %zu(Sel) calls to nothrow functions.\n",
1029 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1031 rbitset_clear_all(ready_set, last_idx);
1032 rbitset_clear_all(busy_set, last_idx);
1034 /* third step: detect, which functions are const or pure */
1035 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1036 for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
1037 ir_graph *irg = get_irp_irg(i);
1038 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1040 if (prop & mtp_property_const) {
1042 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1043 check_for_possible_endless_loops(irg);
1044 } else if (prop & mtp_property_pure) {
1046 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1050 handle_const_Calls(&ctx);
1051 DB((dbg, LEVEL_1, "Detected %zu const graphs, %zu pure graphs.\n", num_const, num_pure));
1052 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1053 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1059 /* initialize the funccall optimization */
1060 void firm_init_funccalls(void)
1062 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1065 /* Creates an ir_prog pass for optimize_funccalls. */
1066 ir_prog_pass_t *optimize_funccalls_pass(const char *name)
1068 return def_prog_pass(name ? name : "funccall", optimize_funccalls);