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)
83 env_t *ctx = (env_t*)env;
87 unsigned and_prop, or_prop, prop;
92 /* set the link to NULL for all non-const/pure calls */
93 set_irn_link(call, NULL);
94 ptr = get_Call_ptr(call);
96 ent = get_Global_entity(ptr);
98 prop = get_entity_additional_properties(ent);
99 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
101 ++ctx->n_calls_SymConst;
102 } else if (get_opt_closed_world() &&
104 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
105 /* If all possible callees are const functions, we can remove the memory edge. */
106 int i, n_callees = get_Call_n_callees(call);
107 if (n_callees == 0) {
108 /* This is kind of strange: dying code or a Call that will raise an exception
109 when executed as there is no implementation to call. So better not
114 /* note that const function are a subset of pure ones */
115 and_prop = mtp_property_const | mtp_property_pure;
117 for (i = 0; i < n_callees; ++i) {
118 ent = get_Call_callee(call, i);
119 if (ent == unknown_entity) {
120 /* we don't know which entity is called here */
123 prop = get_entity_additional_properties(ent);
126 if (and_prop == mtp_no_property)
129 prop = and_prop | (or_prop & mtp_property_has_loop);
134 /* ok, if we get here we found a call to a const or a pure function */
135 if (prop & mtp_property_pure) {
136 set_irn_link(call, ctx->pure_call_list);
137 ctx->pure_call_list = call;
139 if (prop & mtp_property_has_loop) {
140 set_irn_link(call, ctx->nonfloat_const_call_list);
141 ctx->nonfloat_const_call_list = call;
143 set_irn_link(call, ctx->float_const_call_list);
144 ctx->float_const_call_list = call;
147 } else if (is_Proj(node)) {
149 * Collect all memory and exception Proj's from
152 call = get_Proj_pred(node);
156 /* collect the Proj's in the Proj list */
157 switch (get_Proj_proj(node)) {
159 case pn_Call_X_except:
160 case pn_Call_X_regular:
161 set_irn_link(node, ctx->proj_list);
162 ctx->proj_list = node;
168 } /* collect_const_and_pure_calls */
171 * Fix the list of collected Calls.
173 * @param irg the graph that contained calls to pure functions
176 static void fix_const_call_lists(ir_graph *irg, env_t *ctx)
178 ir_node *call, *next, *mem, *proj;
181 /* First step: fix all calls by removing their memory input and let
183 * The original memory input is preserved in their link fields. */
184 for (call = ctx->float_const_call_list; call != NULL; call = next) {
185 next = (ir_node*)get_irn_link(call);
186 mem = get_Call_mem(call);
188 set_irn_link(call, mem);
189 set_Call_mem(call, get_irg_no_mem(irg));
192 * Unfortunately we cannot simply set the node to 'float'.
193 * There is a reason for that:
195 * - The call might be inside a loop/if that is NOT entered
196 * and calls a endless function. Setting the call to float
197 * would allow to move it out from the loop/if causing this
198 * function be called even if the loop/if is not entered ...
200 * This could be fixed using post-dominators for calls and Pin nodes
201 * but need some more analyzes to ensure that a call that potential
202 * never returns is not executed before some code that generates
203 * observable states...
206 /* finally, this call can float */
207 set_irn_pinned(call, op_pin_state_floats);
208 hook_func_call(irg, call);
211 /* Last step: fix all Proj's */
212 for (proj = ctx->proj_list; proj != NULL; proj = next) {
213 next = (ir_node*)get_irn_link(proj);
214 call = get_Proj_pred(proj);
215 mem = (ir_node*)get_irn_link(call);
217 /* beware of calls in the pure call list */
218 if (!mem || is_Call(mem))
220 assert(get_irn_mode(mem) == mode_M);
222 switch (get_Proj_proj(proj)) {
224 /* in dead code there might be cycles where proj == mem */
229 case pn_Call_X_except:
231 exchange(proj, get_irg_bad(irg));
233 case pn_Call_X_regular: {
234 ir_node *block = get_nodes_block(call);
236 exchange(proj, new_r_Jmp(block));
244 /* changes were done ... */
245 set_irg_outs_inconsistent(irg);
246 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
249 /* ... including exception edges */
250 set_irg_doms_inconsistent(irg);
252 } /* fix_const_call_list */
255 * Walker: Collect all calls to nothrow functions
256 * to lists. Collect all Proj(Call) nodes into a Proj list.
258 static void collect_nothrow_calls(ir_node *node, void *env)
260 env_t *ctx = (env_t*)env;
268 /* set the link to NULL for all non-const/pure calls */
269 set_irn_link(call, NULL);
270 ptr = get_Call_ptr(call);
271 if (is_Global(ptr)) {
272 ent = get_Global_entity(ptr);
274 prop = get_entity_additional_properties(ent);
275 if ((prop & mtp_property_nothrow) == 0)
277 ++ctx->n_calls_SymConst;
278 } else if (get_opt_closed_world() &&
280 get_irg_callee_info_state(get_irn_irg(node)) == irg_callee_info_consistent) {
281 /* If all possible callees are nothrow functions, we can remove the exception edge. */
282 int i, n_callees = get_Call_n_callees(call);
283 if (n_callees == 0) {
284 /* This is kind of strange: dying code or a Call that will raise an exception
285 when executed as there is no implementation to call. So better not
290 /* note that const function are a subset of pure ones */
291 prop = mtp_property_nothrow;
292 for (i = 0; i < n_callees; ++i) {
293 ent = get_Call_callee(call, i);
294 if (ent == unknown_entity) {
295 /* we don't know which entity is called here */
298 prop &= get_entity_additional_properties(ent);
299 if (prop == mtp_no_property)
306 /* ok, if we get here we found a call to a nothrow function */
307 set_irn_link(call, ctx->nothrow_call_list);
308 ctx->nothrow_call_list = call;
309 } else if (is_Proj(node)) {
311 * Collect all memory and exception Proj's from
314 call = get_Proj_pred(node);
318 /* collect the Proj's in the Proj list */
319 switch (get_Proj_proj(node)) {
321 case pn_Call_X_except:
322 case pn_Call_X_regular:
323 set_irn_link(node, ctx->proj_list);
324 ctx->proj_list = node;
330 } /* collect_nothrow_calls */
333 * Fix the list of collected nothrow Calls.
335 * @param irg the graph that contained calls to pure functions
336 * @param call_list the list of all call sites of const functions
337 * @param proj_list the list of all memory/exception Proj's of this call sites
339 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
341 ir_node *call, *next, *proj;
344 /* First step: go through the list of calls and mark them. */
345 for (call = call_list; call; call = next) {
346 next = (ir_node*)get_irn_link(call);
348 /* current_ir_graph is in memory anyway, so it's a good marker */
349 set_irn_link(call, ¤t_ir_graph);
350 hook_func_call(irg, call);
353 /* Second step: Remove all exception Proj's */
354 for (proj = proj_list; proj; proj = next) {
355 next = (ir_node*)get_irn_link(proj);
356 call = get_Proj_pred(proj);
358 /* handle only marked calls */
359 if (get_irn_link(call) != ¤t_ir_graph)
362 /* kill any exception flow */
363 switch (get_Proj_proj(proj)) {
364 case pn_Call_X_except:
366 exchange(proj, get_irg_bad(irg));
368 case pn_Call_X_regular: {
369 ir_node *block = get_nodes_block(call);
371 exchange(proj, new_r_Jmp(block));
379 /* changes were done ... */
380 set_irg_outs_inconsistent(irg);
381 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
384 /* ... including exception edges */
385 set_irg_doms_inconsistent(irg);
387 } /* fix_nothrow_call_list */
390 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
391 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
392 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
393 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
394 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
397 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top);
400 * Calculate the bigger property of two. Handle the temporary flag right.
402 static mtp_additional_properties max_property(mtp_additional_properties a,
403 mtp_additional_properties b)
405 mtp_additional_properties r;
406 mtp_additional_properties t = (a | b) & mtp_temporary;
410 if (a == mtp_no_property || b == mtp_no_property)
411 return mtp_no_property;
417 * Follow the memory chain starting at node and determine
420 * @return mtp_property_const if only calls of const functions are detected
421 * mtp_property_pure if only Loads and const/pure calls detected
422 * mtp_no_property else
424 static mtp_additional_properties follow_mem_(ir_node *node)
426 mtp_additional_properties mode = mtp_property_const;
427 mtp_additional_properties m;
432 if (mode == mtp_no_property)
433 return mtp_no_property;
435 if (irn_visited_else_mark(node))
438 switch (get_irn_opcode(node)) {
440 node = get_Proj_pred(node);
449 /* do a dfs search */
450 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
451 m = follow_mem_(get_irn_n(node, i));
452 mode = max_property(mode, m);
453 if (mode == mtp_no_property)
454 return mtp_no_property;
459 /* Beware volatile Loads are NOT allowed in pure functions. */
460 if (get_Load_volatility(node) == volatility_is_volatile)
461 return mtp_no_property;
462 mode = max_property(mode, mtp_property_pure);
463 node = get_Load_mem(node);
467 /* A call is only tolerable if its either constant or pure. */
468 ptr = get_Call_ptr(node);
469 if (is_SymConst_addr_ent(ptr)) {
470 ir_entity *ent = get_SymConst_entity(ptr);
471 ir_graph *irg = get_entity_irg(ent);
473 if (irg == get_irn_irg(node)) {
474 /* A self-recursive call. The property did not depend on this call. */
475 } else if (irg == NULL) {
476 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
477 mode = max_property(mode, m);
478 } else if (irg != NULL) {
479 /* we have a graph, analyze it. */
480 m = check_const_or_pure_function(irg, /*top=*/0);
481 mode = max_property(mode, m);
484 return mtp_no_property;
485 node = get_Call_mem(node);
489 return mtp_no_property;
495 * Follow the memory chain starting at node and determine
498 * @return mtp_property_const if only calls of const functions are detected
499 * mtp_property_pure if only Loads and const/pure calls detected
500 * mtp_no_property else
502 static mtp_additional_properties follow_mem(ir_node *node, mtp_additional_properties mode)
504 mtp_additional_properties m = follow_mem_(node);
505 return max_property(mode, m);
509 * Check if a graph represents a const or a pure function.
511 * @param irg the graph to check
512 * @param top if set, this is the top call
514 static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, int top)
516 ir_node *end, *endbl;
518 mtp_additional_properties prop = get_irg_additional_properties(irg);
520 if (prop & mtp_property_const) {
521 /* already marked as a const function */
522 return mtp_property_const;
524 if (prop & mtp_property_pure) {
525 /* already marked as a pure function */
526 return mtp_property_pure;
529 if (IS_IRG_READY(irg)) {
530 /* already checked */
531 return mtp_no_property;
533 if (IS_IRG_BUSY(irg)) {
534 /* we are still evaluate this method. Be optimistic,
535 return the best possible so far but mark the result as temporary. */
536 return mtp_temporary | mtp_property_const;
540 end = get_irg_end(irg);
541 endbl = get_nodes_block(end);
542 prop = mtp_property_const;
544 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
545 inc_irg_visited(irg);
546 /* mark the initial mem: recursion of follow_mem() stops here */
547 mark_irn_visited(get_irg_initial_mem(irg));
549 /* visit every Return */
550 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
551 ir_node *node = get_Block_cfgpred(endbl, j);
552 unsigned code = get_irn_opcode(node);
555 /* Bad nodes usually do NOT produce anything, so it's ok */
559 if (code == iro_Return) {
560 mem = get_Return_mem(node);
562 /* Bad nodes usually do NOT produce anything, so it's ok */
566 if (mem != get_irg_initial_mem(irg))
567 prop = max_property(prop, follow_mem(mem, prop));
569 /* Exception found. Cannot be const or pure. */
570 prop = mtp_no_property;
573 if (prop == mtp_no_property)
577 if (prop != mtp_no_property) {
578 /* check, if a keep-alive exists */
579 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
580 ir_node *kept = get_End_keepalive(end, j);
582 if (is_Block(kept)) {
583 prop = mtp_no_property;
587 if (mode_M != get_irn_mode(kept))
590 prop = max_property(prop, follow_mem(kept, prop));
591 if (prop == mtp_no_property)
596 if (prop != mtp_no_property) {
597 if (top || (prop & mtp_temporary) == 0) {
598 /* We use the temporary flag here to mark optimistic result.
599 Set the property only if we are sure that it does NOT base on
600 temporary results OR if we are at top-level. */
601 add_irg_additional_properties(irg, prop & ~mtp_temporary);
608 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
610 } /* check_const_or_pure_function */
613 * Handle calls to const functions.
617 static void handle_const_Calls(env_t *ctx)
621 ctx->n_calls_SymConst = 0;
622 ctx->n_calls_Sel = 0;
624 /* all calls of const functions can be transformed */
625 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
626 ir_graph *irg = get_irp_irg(i);
628 ctx->float_const_call_list = NULL;
629 ctx->nonfloat_const_call_list = NULL;
630 ctx->pure_call_list = NULL;
631 ctx->proj_list = NULL;
633 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
634 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
636 if (ctx->float_const_call_list != NULL)
637 fix_const_call_lists(irg, ctx);
638 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
640 } /* handle_const_Calls */
643 * Handle calls to nothrow functions.
647 static void handle_nothrow_Calls(env_t *ctx)
651 ctx->n_calls_SymConst = 0;
652 ctx->n_calls_Sel = 0;
654 /* all calls of const functions can be transformed */
655 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
656 ir_graph *irg = get_irp_irg(i);
658 ctx->nothrow_call_list = NULL;
659 ctx->proj_list = NULL;
661 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
662 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
664 if (ctx->nothrow_call_list)
665 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
666 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
671 * Check, whether a given node represents a return value of
672 * a malloc like function (ie, new heap allocated memory).
674 * @param node the node to check
676 static int is_malloc_call_result(const ir_node *node)
678 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
679 /* Firm style high-level allocation */
682 if (is_alloc_entity != NULL && is_Call(node)) {
683 ir_node *ptr = get_Call_ptr(node);
685 if (is_Global(ptr)) {
686 ir_entity *ent = get_Global_entity(ptr);
687 return is_alloc_entity(ent);
691 } /* is_malloc_call_result */
694 * Update a property depending on a call property.
696 static mtp_additional_properties update_property(mtp_additional_properties orig_prop, mtp_additional_properties call_prop)
698 mtp_additional_properties t = (orig_prop | call_prop) & mtp_temporary;
699 mtp_additional_properties r = orig_prop & call_prop;
704 * Check if a node is stored.
706 static int is_stored(const ir_node *n)
708 const ir_edge_t *edge;
711 foreach_out_edge(n, edge) {
712 const ir_node *succ = get_edge_src_irn(edge);
714 switch (get_irn_opcode(succ)) {
721 if (get_Store_value(succ) == n)
723 /* ok if its only the address input */
732 ptr = get_Call_ptr(succ);
733 if (is_Global(ptr)) {
734 ir_entity *ent = get_Global_entity(ptr);
737 /* we know the called entity */
738 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
739 if (get_Call_param(succ, i) == n) {
740 /* n is the i'th param of the call */
741 if (get_method_param_access(ent, i) & ptr_access_store) {
742 /* n is store in ent */
748 /* unknown call address */
753 /* bad, potential alias */
761 * Check that the return value of an irg is not stored anywhere.
763 * return ~mtp_property_malloc if return values are stored, ~0 else
765 static mtp_additional_properties check_stored_result(ir_graph *irg)
767 ir_node *end_blk = get_irg_end_block(irg);
769 mtp_additional_properties res = ~mtp_no_property;
770 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
772 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
773 ir_node *pred = get_Block_cfgpred(end_blk, i);
775 if (! is_Return(pred))
777 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
778 const ir_node *irn = get_Return_res(pred, j);
780 if (is_stored(irn)) {
781 /* bad, might create an alias */
782 res = ~mtp_property_malloc;
789 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
794 * Check if a graph represents a nothrow or a malloc function.
796 * @param irg the graph to check
797 * @param top if set, this is the top call
799 static mtp_additional_properties check_nothrow_or_malloc(ir_graph *irg, int top)
801 mtp_additional_properties curr_prop = mtp_property_malloc | mtp_property_nothrow;
802 ir_node *end_blk = get_irg_end_block(irg);
807 if (IS_IRG_READY(irg)) {
808 /* already checked */
809 return get_irg_additional_properties(irg);
811 if (IS_IRG_BUSY(irg)) {
812 /* we are still evaluate this method. Be optimistic,
813 return the best possible so far but mark the result as temporary. */
814 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
818 ent = get_irg_entity(irg);
819 mtp = get_entity_type(ent);
821 if (get_method_n_ress(mtp) <= 0)
822 curr_prop &= ~mtp_property_malloc;
824 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
825 ir_node *pred = get_Block_cfgpred(end_blk, i);
827 if (is_Return(pred)) {
828 if (curr_prop & mtp_property_malloc) {
829 /* check, if malloc is called here */
830 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
831 ir_node *res = get_Return_res(pred, j);
833 /* skip Confirms and Casts */
834 res = skip_HighLevel_ops(res);
837 res = get_Proj_pred(res);
838 if (is_malloc_call_result(res)) {
839 /* ok, this is a malloc */
840 } else if (is_Call(res)) {
841 ir_node *ptr = get_Call_ptr(res);
843 if (is_Global(ptr)) {
845 ir_entity *ent = get_Global_entity(ptr);
846 ir_graph *callee = get_entity_irg(ent);
849 /* A self-recursive call. The property did not depend on this call. */
850 } else if (callee != NULL) {
851 mtp_additional_properties prop = check_nothrow_or_malloc(callee, /*top=*/0);
852 curr_prop = update_property(curr_prop, prop);
854 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
856 } else if (get_opt_closed_world() &&
858 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
859 /* check if all possible callees are malloc functions. */
860 int i, n_callees = get_Call_n_callees(res);
861 if (n_callees == 0) {
862 /* This is kind of strange: dying code or a Call that will raise an exception
863 when executed as there is no implementation to call. So better not
865 curr_prop &= ~mtp_property_malloc;
869 for (i = 0; i < n_callees; ++i) {
870 ir_entity *ent = get_Call_callee(res, i);
871 if (ent == unknown_entity) {
872 /* we don't know which entity is called here */
873 curr_prop &= ~mtp_property_malloc;
876 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
877 curr_prop &= ~mtp_property_malloc;
881 /* if we pass the for cycle, malloc is still ok */
884 curr_prop &= ~mtp_property_malloc;
887 /* unknown return value */
888 curr_prop &= ~mtp_property_malloc;
892 } else if (curr_prop & mtp_property_nothrow) {
893 /* exception flow detected */
894 pred = skip_Proj(pred);
897 ir_node *ptr = get_Call_ptr(pred);
899 if (is_Global(ptr)) {
901 ir_entity *ent = get_Global_entity(ptr);
902 ir_graph *callee = get_entity_irg(ent);
905 /* A self-recursive call. The property did not depend on this call. */
906 } else if (callee != NULL) {
907 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
908 mtp_additional_properties prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
909 curr_prop = update_property(curr_prop, prop);
911 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
912 curr_prop &= ~mtp_property_nothrow;
914 } else if (get_opt_closed_world() &&
916 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
917 /* check if all possible callees are nothrow functions. */
918 int i, n_callees = get_Call_n_callees(pred);
919 if (n_callees == 0) {
920 /* This is kind of strange: dying code or a Call that will raise an exception
921 when executed as there is no implementation to call. So better not
923 curr_prop &= ~mtp_property_nothrow;
927 for (i = 0; i < n_callees; ++i) {
928 ir_entity *ent = get_Call_callee(pred, i);
929 if (ent == unknown_entity) {
930 /* we don't know which entity is called here */
931 curr_prop &= ~mtp_property_nothrow;
934 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
935 curr_prop &= ~mtp_property_nothrow;
939 /* if we pass the for cycle, nothrow is still ok */
942 curr_prop &= ~mtp_property_nothrow;
945 /* real exception flow possible. */
946 curr_prop &= ~mtp_property_nothrow;
949 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
950 /* no need to search further */
955 if (curr_prop & mtp_property_malloc) {
957 * Note that the malloc property means not only return newly allocated
958 * memory, but also that this memory is ALIAS FREE.
959 * To ensure that, we do NOT allow that the returned memory is somewhere
962 curr_prop &= check_stored_result(irg);
965 if (curr_prop != mtp_no_property) {
966 if (top || (curr_prop & mtp_temporary) == 0) {
967 /* We use the temporary flag here to mark an optimistic result.
968 Set the property only if we are sure that it does NOT base on
969 temporary results OR if we are at top-level. */
970 add_irg_additional_properties(irg, curr_prop & ~mtp_temporary);
978 } /* check_nothrow_or_malloc */
981 * When a function was detected as "const", it might be moved out of loops.
982 * This might be dangerous if the graph can contain endless loops.
984 static void check_for_possible_endless_loops(ir_graph *irg)
989 root_loop = get_irg_loop(irg);
990 if (root_loop->flags & loop_outer_loop)
991 add_irg_additional_properties(irg, mtp_property_has_loop);
995 * optimize function calls by handling const functions
997 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
1000 unsigned num_const = 0;
1001 unsigned num_pure = 0;
1002 unsigned num_nothrow = 0;
1003 unsigned num_malloc = 0;
1005 is_alloc_entity = callback;
1007 /* prepare: mark all graphs as not analyzed */
1008 last_idx = get_irp_last_idx();
1009 ready_set = rbitset_malloc(last_idx);
1010 busy_set = rbitset_malloc(last_idx);
1012 /* first step: detect, which functions are nothrow or malloc */
1013 DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1014 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1015 ir_graph *irg = get_irp_irg(i);
1016 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1018 if (prop & mtp_property_nothrow) {
1020 DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1021 } else if (prop & mtp_property_malloc) {
1023 DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1027 /* second step: remove exception edges: this must be done before the
1028 detection of const and pure functions take place. */
1029 if (force_run || num_nothrow > 0) {
1032 handle_nothrow_Calls(&ctx);
1033 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1034 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1035 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1037 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1040 rbitset_clear_all(ready_set, last_idx);
1041 rbitset_clear_all(busy_set, last_idx);
1043 /* third step: detect, which functions are const or pure */
1044 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1045 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1046 ir_graph *irg = get_irp_irg(i);
1047 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1049 if (prop & mtp_property_const) {
1051 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1052 check_for_possible_endless_loops(irg);
1053 } else if (prop & mtp_property_pure) {
1055 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1059 if (force_run || num_const > 0) {
1062 handle_const_Calls(&ctx);
1063 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1064 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1065 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1067 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1071 } /* optimize_funccalls */
1073 /* initialize the funccall optimization */
1074 void firm_init_funccalls(void)
1076 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1077 } /* firm_init_funccalls */
1079 typedef struct pass_t {
1080 ir_prog_pass_t pass;
1082 check_alloc_entity_func callback;
1086 * Wrapper for running optimize_funccalls() as an ir_prog pass.
1088 static int pass_wrapper(ir_prog *irp, void *context)
1090 pass_t *pass = (pass_t*)context;
1093 optimize_funccalls(pass->force_run, pass->callback);
1095 } /* pass_wrapper */
1097 /* Creates an ir_prog pass for optimize_funccalls. */
1098 ir_prog_pass_t *optimize_funccalls_pass(
1100 int force_run, check_alloc_entity_func callback)
1102 struct pass_t *pass = XMALLOCZ(struct pass_t);
1104 pass->force_run = force_run;
1105 pass->callback = callback;
1107 return def_prog_pass_constructor(
1108 &pass->pass, name ? name : "funccall", pass_wrapper);
1109 } /* optimize_funccalls_pass */