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"
35 #include "dbginfo_t.h"
39 #include "iredges_t.h"
41 #include "iroptimize.h"
42 #include "analyze_irg_args.h"
44 #include "raw_bitset.h"
47 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
50 * The walker environment for updating function calls.
52 typedef struct _env_t {
53 unsigned n_calls_SymConst;
55 ir_node *float_const_call_list; /**< The list of all floating const function calls that will be changed. */
56 ir_node *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
57 ir_node *pure_call_list; /**< The list of all pure function calls that will be changed. */
58 ir_node *nothrow_call_list; /**< The list of all nothrow function calls that will be changed. */
59 ir_node *proj_list; /**< The list of all potential Proj nodes that must be fixed. */
62 /** If non-null, evaluates entities for being a heap alloc. */
63 static check_alloc_entity_func is_alloc_entity = NULL;
65 /** Ready IRG's are marked in the ready set. */
66 static unsigned *ready_set;
68 /** IRG's that are in progress are marked here. */
69 static unsigned *busy_set;
72 * We misuse the mtp_property_inherited flag as temporary here.
73 * The is ok, as we cannot set or get it anyway using the
74 * get_addtional_properties API.
76 #define mtp_temporary mtp_property_inherited
79 * Walker: Collect all calls to const and pure functions
80 * to lists. Collect all Proj(Call) nodes into a Proj list.
82 static void collect_const_and_pure_calls(ir_node *node, void *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(current_ir_graph) == 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;
180 ir_graph *rem = current_ir_graph;
182 current_ir_graph = irg;
184 /* First step: fix all calls by removing their memory input and let
186 * The original memory input is preserved in their link fields. */
187 for (call = ctx->float_const_call_list; call != NULL; call = next) {
188 next = get_irn_link(call);
189 mem = get_Call_mem(call);
191 set_irn_link(call, mem);
192 set_Call_mem(call, get_irg_no_mem(irg));
195 * Unfortunately we cannot simply set the node to 'float'.
196 * There is a reason for that:
198 * - The call might be inside a loop/if that is NOT entered
199 * and calls a endless function. Setting the call to float
200 * would allow to move it out from the loop/if causing this
201 * function be called even if the loop/if is not entered ...
203 * This could be fixed using post-dominators for calls and Pin nodes
204 * but need some more analyzes to ensure that a call that potential
205 * never returns is not executed before some code that generates
206 * observable states...
209 /* finally, this call can float */
210 set_irn_pinned(call, op_pin_state_floats);
211 hook_func_call(irg, call);
214 /* Last step: fix all Proj's */
215 for (proj = ctx->proj_list; proj != NULL; proj = next) {
216 next = get_irn_link(proj);
217 call = get_Proj_pred(proj);
218 mem = get_irn_link(call);
220 /* beware of calls in the pure call list */
221 if (!mem || is_Call(mem))
223 assert(get_irn_mode(mem) == mode_M);
225 switch (get_Proj_proj(proj)) {
227 /* in dead code there might be cycles where proj == mem */
232 case pn_Call_X_except:
234 exchange(proj, get_irg_bad(irg));
236 case pn_Call_X_regular: {
237 ir_node *block = get_nodes_block(call);
239 exchange(proj, new_r_Jmp(block));
247 /* changes were done ... */
248 set_irg_outs_inconsistent(irg);
249 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
252 /* ... including exception edges */
253 set_irg_doms_inconsistent(irg);
255 current_ir_graph = rem;
256 } /* fix_const_call_list */
259 * Walker: Collect all calls to nothrow functions
260 * to lists. Collect all Proj(Call) nodes into a Proj list.
262 static void collect_nothrow_calls(ir_node *node, void *env)
272 /* set the link to NULL for all non-const/pure calls */
273 set_irn_link(call, NULL);
274 ptr = get_Call_ptr(call);
275 if (is_Global(ptr)) {
276 ent = get_Global_entity(ptr);
278 prop = get_entity_additional_properties(ent);
279 if ((prop & mtp_property_nothrow) == 0)
281 ++ctx->n_calls_SymConst;
282 } else if (get_opt_closed_world() &&
284 get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
285 /* If all possible callees are nothrow functions, we can remove the exception edge. */
286 int i, n_callees = get_Call_n_callees(call);
287 if (n_callees == 0) {
288 /* This is kind of strange: dying code or a Call that will raise an exception
289 when executed as there is no implementation to call. So better not
294 /* note that const function are a subset of pure ones */
295 prop = mtp_property_nothrow;
296 for (i = 0; i < n_callees; ++i) {
297 ent = get_Call_callee(call, i);
298 if (ent == unknown_entity) {
299 /* we don't know which entity is called here */
302 prop &= get_entity_additional_properties(ent);
303 if (prop == mtp_no_property)
310 /* ok, if we get here we found a call to a nothrow function */
311 set_irn_link(call, ctx->nothrow_call_list);
312 ctx->nothrow_call_list = call;
313 } else if (is_Proj(node)) {
315 * Collect all memory and exception Proj's from
318 call = get_Proj_pred(node);
322 /* collect the Proj's in the Proj list */
323 switch (get_Proj_proj(node)) {
325 case pn_Call_X_except:
326 case pn_Call_X_regular:
327 set_irn_link(node, ctx->proj_list);
328 ctx->proj_list = node;
334 } /* collect_nothrow_calls */
337 * Fix the list of collected nothrow Calls.
339 * @param irg the graph that contained calls to pure functions
340 * @param call_list the list of all call sites of const functions
341 * @param proj_list the list of all memory/exception Proj's of this call sites
343 static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list)
345 ir_node *call, *next, *proj;
347 ir_graph *rem = current_ir_graph;
349 current_ir_graph = irg;
351 /* First step: go through the list of calls and mark them. */
352 for (call = call_list; call; call = next) {
353 next = get_irn_link(call);
355 /* current_ir_graph is in memory anyway, so it's a good marker */
356 set_irn_link(call, ¤t_ir_graph);
357 hook_func_call(irg, call);
360 /* Second step: Remove all exception Proj's */
361 for (proj = proj_list; proj; proj = next) {
362 next = get_irn_link(proj);
363 call = get_Proj_pred(proj);
365 /* handle only marked calls */
366 if (get_irn_link(call) != ¤t_ir_graph)
369 /* kill any exception flow */
370 switch (get_Proj_proj(proj)) {
371 case pn_Call_X_except:
373 exchange(proj, get_irg_bad(irg));
375 case pn_Call_X_regular: {
376 ir_node *block = get_nodes_block(call);
378 exchange(proj, new_r_Jmp(block));
386 /* changes were done ... */
387 set_irg_outs_inconsistent(irg);
388 set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);
391 /* ... including exception edges */
392 set_irg_doms_inconsistent(irg);
394 current_ir_graph = rem;
395 } /* fix_nothrow_call_list */
398 #define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg))
399 #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg))
400 #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg))
401 #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
402 #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg))
405 static unsigned check_const_or_pure_function(ir_graph *irg, int top);
408 * Calculate the bigger property of two. Handle the temporary flag right.
410 static unsigned max_property(unsigned a, unsigned b)
412 unsigned r, t = (a | b) & mtp_temporary;
416 if (a == mtp_no_property || b == mtp_no_property)
417 return mtp_no_property;
423 * Follow the memory chain starting at node and determine
426 * @return mtp_property_const if only calls of const functions are detected
427 * mtp_property_pure if only Loads and const/pure calls detected
428 * mtp_no_property else
430 static unsigned _follow_mem(ir_node *node)
432 unsigned m, mode = mtp_property_const;
437 if (mode == mtp_no_property)
438 return mtp_no_property;
440 if (irn_visited_else_mark(node))
443 switch (get_irn_opcode(node)) {
445 node = get_Proj_pred(node);
454 /* do a dfs search */
455 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
456 m = _follow_mem(get_irn_n(node, i));
457 mode = max_property(mode, m);
458 if (mode == mtp_no_property)
459 return mtp_no_property;
464 /* Beware volatile Loads are NOT allowed in pure functions. */
465 if (get_Load_volatility(node) == volatility_is_volatile)
466 return mtp_no_property;
467 mode = max_property(mode, mtp_property_pure);
468 node = get_Load_mem(node);
472 /* A call is only tolerable if its either constant or pure. */
473 ptr = get_Call_ptr(node);
474 if (is_SymConst_addr_ent(ptr)) {
475 ir_entity *ent = get_SymConst_entity(ptr);
476 ir_graph *irg = get_entity_irg(ent);
478 if (irg == current_ir_graph) {
479 /* A self-recursive call. The property did not depend on this call. */
480 } else if (irg == NULL) {
481 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
482 mode = max_property(mode, m);
483 } else if (irg != NULL) {
484 /* we have a graph, analyze it. */
485 m = check_const_or_pure_function(irg, /*top=*/0);
486 mode = max_property(mode, m);
489 return mtp_no_property;
490 node = get_Call_mem(node);
494 return mtp_no_property;
500 * Follow the memory chain starting at node and determine
503 * @return mtp_property_const if only calls of const functions are detected
504 * mtp_property_pure if only Loads and const/pure calls detected
505 * mtp_no_property else
507 static unsigned follow_mem(ir_node *node, unsigned mode)
511 m = _follow_mem(node);
512 return max_property(mode, m);
516 * Check if a graph represents a const or a pure function.
518 * @param irg the graph to check
519 * @param top if set, this is the top call
521 static unsigned check_const_or_pure_function(ir_graph *irg, int top)
523 ir_node *end, *endbl;
525 unsigned prop = get_irg_additional_properties(irg);
526 ir_graph *rem = current_ir_graph;
528 if (prop & mtp_property_const) {
529 /* already marked as a const function */
530 return mtp_property_const;
532 if (prop & mtp_property_pure) {
533 /* already marked as a pure function */
534 return mtp_property_pure;
537 if (IS_IRG_READY(irg)) {
538 /* already checked */
539 return mtp_no_property;
541 if (IS_IRG_BUSY(irg)) {
542 /* we are still evaluate this method. Be optimistic,
543 return the best possible so far but mark the result as temporary. */
544 return mtp_temporary | mtp_property_const;
548 end = get_irg_end(irg);
549 endbl = get_nodes_block(end);
550 prop = mtp_property_const;
552 current_ir_graph = irg;
554 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
555 inc_irg_visited(irg);
556 /* mark the initial mem: recursion of follow_mem() stops here */
557 mark_irn_visited(get_irg_initial_mem(irg));
559 /* visit every Return */
560 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
561 ir_node *node = get_Block_cfgpred(endbl, j);
562 ir_opcode code = get_irn_opcode(node);
565 /* Bad nodes usually do NOT produce anything, so it's ok */
569 if (code == iro_Return) {
570 mem = get_Return_mem(node);
572 /* Bad nodes usually do NOT produce anything, so it's ok */
576 if (mem != get_irg_initial_mem(irg))
577 prop = max_property(prop, follow_mem(mem, prop));
579 /* Exception found. Cannot be const or pure. */
580 prop = mtp_no_property;
583 if (prop == mtp_no_property)
587 if (prop != mtp_no_property) {
588 /* check, if a keep-alive exists */
589 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
590 ir_node *kept = get_End_keepalive(end, j);
592 if (is_Block(kept)) {
593 prop = mtp_no_property;
597 if (mode_M != get_irn_mode(kept))
600 prop = max_property(prop, follow_mem(kept, prop));
601 if (prop == mtp_no_property)
606 if (prop != mtp_no_property) {
607 if (top || (prop & mtp_temporary) == 0) {
608 /* We use the temporary flag here to mark optimistic result.
609 Set the property only if we are sure that it does NOT base on
610 temporary results OR if we are at top-level. */
611 set_irg_additional_property(irg, prop & ~mtp_temporary);
618 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
619 current_ir_graph = rem;
621 } /* check_const_or_pure_function */
624 * Handle calls to const functions.
628 static void handle_const_Calls(env_t *ctx)
632 ctx->n_calls_SymConst = 0;
633 ctx->n_calls_Sel = 0;
635 /* all calls of const functions can be transformed */
636 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
637 ir_graph *irg = get_irp_irg(i);
639 ctx->float_const_call_list = NULL;
640 ctx->nonfloat_const_call_list = NULL;
641 ctx->pure_call_list = NULL;
642 ctx->proj_list = NULL;
644 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
645 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
647 if (ctx->float_const_call_list != NULL)
648 fix_const_call_lists(irg, ctx);
649 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
651 } /* handle_const_Calls */
654 * Handle calls to nothrow functions.
658 static void handle_nothrow_Calls(env_t *ctx)
662 ctx->n_calls_SymConst = 0;
663 ctx->n_calls_Sel = 0;
665 /* all calls of const functions can be transformed */
666 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
667 ir_graph *irg = get_irp_irg(i);
669 ctx->nothrow_call_list = NULL;
670 ctx->proj_list = NULL;
672 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
673 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
675 if (ctx->nothrow_call_list)
676 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
677 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
682 * Check, whether a given node represents a return value of
683 * a malloc like function (ie, new heap allocated memory).
685 * @param node the node to check
687 static int is_malloc_call_result(const ir_node *node)
689 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
690 /* Firm style high-level allocation */
693 if (is_alloc_entity != NULL && is_Call(node)) {
694 ir_node *ptr = get_Call_ptr(node);
696 if (is_Global(ptr)) {
697 ir_entity *ent = get_Global_entity(ptr);
698 return is_alloc_entity(ent);
702 } /* is_malloc_call_result */
705 * Update a property depending on a call property.
707 static unsigned update_property(unsigned orig_prop, unsigned call_prop)
709 unsigned t = (orig_prop | call_prop) & mtp_temporary;
710 unsigned r = orig_prop & call_prop;
712 } /** update_property */
715 * Check if a node is stored.
717 static int is_stored(const ir_node *n)
719 const ir_edge_t *edge;
722 foreach_out_edge(n, edge) {
723 const ir_node *succ = get_edge_src_irn(edge);
725 switch (get_irn_opcode(succ)) {
732 if (get_Store_value(succ) == n)
734 /* ok if its only the address input */
743 ptr = get_Call_ptr(succ);
744 if (is_Global(ptr)) {
745 ir_entity *ent = get_Global_entity(ptr);
748 /* we know the called entity */
749 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
750 if (get_Call_param(succ, i) == n) {
751 /* n is the i'th param of the call */
752 if (get_method_param_access(ent, i) & ptr_access_store) {
753 /* n is store in ent */
759 /* unknown call address */
764 /* bad, potential alias */
772 * Check that the return value of an irg is not stored anywhere.
774 * return ~mtp_property_malloc if return values are stored, ~0 else
776 static unsigned check_stored_result(ir_graph *irg)
778 ir_node *end_blk = get_irg_end_block(irg);
781 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
783 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
784 ir_node *pred = get_Block_cfgpred(end_blk, i);
786 if (! is_Return(pred))
788 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
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);
802 } /* check_stored_result */
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 unsigned check_nothrow_or_malloc(ir_graph *irg, int top)
812 ir_node *end_blk = get_irg_end_block(irg);
816 unsigned curr_prop = mtp_property_malloc | mtp_property_nothrow;
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) {
840 /* check, if malloc is called here */
841 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
842 ir_node *res = get_Return_res(pred, j);
844 /* skip Confirms and Casts */
845 res = skip_HighLevel_ops(res);
848 res = get_Proj_pred(res);
849 if (is_malloc_call_result(res)) {
850 /* ok, this is a malloc */
851 } else if (is_Call(res)) {
852 ir_node *ptr = get_Call_ptr(res);
854 if (is_Global(ptr)) {
856 ir_entity *ent = get_Global_entity(ptr);
857 ir_graph *callee = get_entity_irg(ent);
860 /* A self-recursive call. The property did not depend on this call. */
861 } else if (callee != NULL) {
862 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
863 curr_prop = update_property(curr_prop, prop);
865 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
867 } else if (get_opt_closed_world() &&
869 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
870 /* check if all possible callees are malloc functions. */
871 int i, n_callees = get_Call_n_callees(res);
872 if (n_callees == 0) {
873 /* This is kind of strange: dying code or a Call that will raise an exception
874 when executed as there is no implementation to call. So better not
876 curr_prop &= ~mtp_property_malloc;
880 for (i = 0; i < n_callees; ++i) {
881 ir_entity *ent = get_Call_callee(res, i);
882 if (ent == unknown_entity) {
883 /* we don't know which entity is called here */
884 curr_prop &= ~mtp_property_malloc;
887 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
888 curr_prop &= ~mtp_property_malloc;
892 /* if we pass the for cycle, malloc is still ok */
895 curr_prop &= ~mtp_property_malloc;
898 /* unknown return value */
899 curr_prop &= ~mtp_property_malloc;
903 } else if (curr_prop & mtp_property_nothrow) {
904 /* exception flow detected */
905 pred = skip_Proj(pred);
908 ir_node *ptr = get_Call_ptr(pred);
910 if (is_Global(ptr)) {
912 ir_entity *ent = get_Global_entity(ptr);
913 ir_graph *callee = get_entity_irg(ent);
916 /* A self-recursive call. The property did not depend on this call. */
917 } else if (callee != NULL) {
918 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
919 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
920 curr_prop = update_property(curr_prop, prop);
922 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
923 curr_prop &= ~mtp_property_nothrow;
925 } else if (get_opt_closed_world() &&
927 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
928 /* check if all possible callees are nothrow functions. */
929 int i, n_callees = get_Call_n_callees(pred);
930 if (n_callees == 0) {
931 /* This is kind of strange: dying code or a Call that will raise an exception
932 when executed as there is no implementation to call. So better not
934 curr_prop &= ~mtp_property_nothrow;
938 for (i = 0; i < n_callees; ++i) {
939 ir_entity *ent = get_Call_callee(pred, i);
940 if (ent == unknown_entity) {
941 /* we don't know which entity is called here */
942 curr_prop &= ~mtp_property_nothrow;
945 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
946 curr_prop &= ~mtp_property_nothrow;
950 /* if we pass the for cycle, nothrow is still ok */
953 curr_prop &= ~mtp_property_nothrow;
956 /* real exception flow possible. */
957 curr_prop &= ~mtp_property_nothrow;
960 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
961 /* no need to search further */
966 if (curr_prop & mtp_property_malloc) {
968 * Note that the malloc property means not only return newly allocated
969 * memory, but also that this memory is ALIAS FREE.
970 * To ensure that, we do NOT allow that the returned memory is somewhere
973 curr_prop &= check_stored_result(irg);
976 if (curr_prop != mtp_no_property) {
977 if (top || (curr_prop & mtp_temporary) == 0) {
978 /* We use the temporary flag here to mark an optimistic result.
979 Set the property only if we are sure that it does NOT base on
980 temporary results OR if we are at top-level. */
981 set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
989 } /* check_nothrow_or_malloc */
992 * When a function was detected as "const", it might be moved out of loops.
993 * This might be dangerous if the graph can contain endless loops.
995 static void check_for_possible_endless_loops(ir_graph *irg)
1000 root_loop = get_irg_loop(irg);
1001 if (root_loop->flags & loop_outer_loop)
1002 set_irg_additional_property(irg, mtp_property_has_loop);
1006 * optimize function calls by handling const functions
1008 void optimize_funccalls(int force_run, check_alloc_entity_func callback)
1011 unsigned num_const = 0;
1012 unsigned num_pure = 0;
1013 unsigned num_nothrow = 0;
1014 unsigned num_malloc = 0;
1016 is_alloc_entity = callback;
1018 /* prepare: mark all graphs as not analyzed */
1019 last_idx = get_irp_last_idx();
1020 ready_set = rbitset_malloc(last_idx);
1021 busy_set = rbitset_malloc(last_idx);
1023 /* first step: detect, which functions are nothrow or malloc */
1024 DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
1025 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1026 ir_graph *irg = get_irp_irg(i);
1027 unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);
1029 if (prop & mtp_property_nothrow) {
1031 DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
1032 } else if (prop & mtp_property_malloc) {
1034 DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
1038 /* second step: remove exception edges: this must be done before the
1039 detection of const and pure functions take place. */
1040 if (force_run || num_nothrow > 0) {
1043 handle_nothrow_Calls(&ctx);
1044 DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
1045 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
1046 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1048 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1051 rbitset_clear_all(ready_set, last_idx);
1052 rbitset_clear_all(busy_set, last_idx);
1054 /* third step: detect, which functions are const or pure */
1055 DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1056 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1057 ir_graph *irg = get_irp_irg(i);
1058 unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1060 if (prop & mtp_property_const) {
1062 DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1063 check_for_possible_endless_loops(irg);
1064 } else if (prop & mtp_property_pure) {
1066 DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1070 if (force_run || num_const > 0) {
1073 handle_const_Calls(&ctx);
1074 DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
1075 DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
1076 ctx.n_calls_SymConst, ctx.n_calls_Sel));
1078 DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1082 } /* optimize_funccalls */
1084 /* initialize the funccall optimization */
1085 void firm_init_funccalls(void)
1087 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1088 } /* firm_init_funccalls */
1091 ir_prog_pass_t pass;
1093 check_alloc_entity_func callback;
1097 * Wrapper for running optimize_funccalls() as an ir_prog pass.
1099 static int pass_wrapper(ir_prog *irp, void *context)
1101 struct pass_t *pass = context;
1104 optimize_funccalls(pass->force_run, pass->callback);
1106 } /* pass_wrapper */
1108 /* Creates an ir_prog pass for optimize_funccalls. */
1109 ir_prog_pass_t *optimize_funccalls_pass(
1111 int force_run, check_alloc_entity_func callback)
1113 struct pass_t *pass = XMALLOCZ(struct pass_t);
1115 pass->force_run = force_run;
1116 pass->callback = callback;
1118 return def_prog_pass_constructor(
1119 &pass->pass, name ? name : "funccall", pass_wrapper);
1120 } /* optimize_funccalls_pass */