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
28 #include <adt/raw_bitset.h>
30 #include "funccall_t.h"
33 #include "irgraph_t.h"
37 #include "dbginfo_t.h"
41 #include "iredges_t.h"
43 #include "analyze_irg_args.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) {
86 unsigned and_prop, or_prop, prop;
91 /* set the link to NULL for all non-const/pure calls */
92 set_irn_link(call, NULL);
93 ptr = get_Call_ptr(call);
95 ent = get_Global_entity(ptr);
97 prop = get_entity_additional_properties(ent);
98 if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
100 ++ctx->n_calls_SymConst;
101 } else if (get_opt_closed_world() &&
103 get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
104 /* If all possible callees are const functions, we can remove the memory edge. */
105 int i, n_callees = get_Call_n_callees(call);
106 if (n_callees == 0) {
107 /* This is kind of strange: dying code or a Call that will raise an exception
108 when executed as there is no implementation to call. So better not
113 /* note that const function are a subset of pure ones */
114 and_prop = mtp_property_const | mtp_property_pure;
116 for (i = 0; i < n_callees; ++i) {
117 ent = get_Call_callee(call, i);
118 if (ent == unknown_entity) {
119 /* we don't know which entity is called here */
122 prop = get_entity_additional_properties(ent);
125 if (and_prop == mtp_no_property)
128 prop = and_prop | (or_prop & mtp_property_has_loop);
133 /* ok, if we get here we found a call to a const or a pure function */
134 if (prop & mtp_property_pure) {
135 set_irn_link(call, ctx->pure_call_list);
136 ctx->pure_call_list = call;
138 if (prop & mtp_property_has_loop) {
139 set_irn_link(call, ctx->nonfloat_const_call_list);
140 ctx->nonfloat_const_call_list = call;
142 set_irn_link(call, ctx->float_const_call_list);
143 ctx->float_const_call_list = call;
146 } else if (is_Proj(node)) {
148 * Collect all memory and exception Proj's from
151 call = get_Proj_pred(node);
155 /* collect the Proj's in the Proj list */
156 switch (get_Proj_proj(node)) {
157 case pn_Call_M_regular:
158 case pn_Call_X_except:
159 case pn_Call_X_regular:
160 case pn_Call_M_except:
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) {
177 ir_node *call, *next, *mem, *proj;
179 ir_graph *rem = current_ir_graph;
181 current_ir_graph = irg;
183 /* First step: fix all calls by removing their memory input and let
185 * The original memory input is preserved in their link fields. */
186 for (call = ctx->float_const_call_list; call != NULL; call = next) {
187 next = get_irn_link(call);
188 mem = get_Call_mem(call);
190 set_irn_link(call, mem);
191 set_Call_mem(call, get_irg_no_mem(irg));
194 * Unfortunately we cannot simply set the node to 'float'.
195 * There is a reason for that:
197 * - The call might be inside a loop/if that is NOT entered
198 * and calls a endless function. Setting the call to float
199 * would allow to move it out from the loop/if causing this
200 * function be called even if the loop/if is not entered ...
202 * This could be fixed using post-dominators for calls and Pin nodes
203 * but need some more analyzes to ensure that a call that potential
204 * never returns is not executed before some code that generates
205 * observable states...
208 /* finally, this call can float */
209 set_irn_pinned(call, op_pin_state_floats);
210 hook_func_call(irg, call);
213 /* Last step: fix all Proj's */
214 for (proj = ctx->proj_list; proj != NULL; proj = next) {
215 next = get_irn_link(proj);
216 call = get_Proj_pred(proj);
217 mem = get_irn_link(call);
219 /* beware of calls in the pure call list */
220 if (!mem || is_Call(mem))
222 assert(get_irn_mode(mem) == mode_M);
224 switch (get_Proj_proj(proj)) {
225 case pn_Call_M_regular: {
226 /* in dead code there might be cycles where proj == mem */
231 case pn_Call_X_except:
232 case pn_Call_M_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) {
271 /* set the link to NULL for all non-const/pure calls */
272 set_irn_link(call, NULL);
273 ptr = get_Call_ptr(call);
274 if (is_Global(ptr)) {
275 ent = get_Global_entity(ptr);
277 prop = get_entity_additional_properties(ent);
278 if ((prop & mtp_property_nothrow) == 0)
280 ++ctx->n_calls_SymConst;
281 } else if (get_opt_closed_world() &&
283 get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
284 /* If all possible callees are nothrow functions, we can remove the exception edge. */
285 int i, n_callees = get_Call_n_callees(call);
286 if (n_callees == 0) {
287 /* This is kind of strange: dying code or a Call that will raise an exception
288 when executed as there is no implementation to call. So better not
293 /* note that const function are a subset of pure ones */
294 prop = mtp_property_nothrow;
295 for (i = 0; i < n_callees; ++i) {
296 ent = get_Call_callee(call, i);
297 if (ent == unknown_entity) {
298 /* we don't know which entity is called here */
301 prop &= get_entity_additional_properties(ent);
302 if (prop == mtp_no_property)
309 /* ok, if we get here we found a call to a nothrow function */
310 set_irn_link(call, ctx->nothrow_call_list);
311 ctx->nothrow_call_list = call;
312 } else if (is_Proj(node)) {
314 * Collect all memory and exception Proj's from
317 call = get_Proj_pred(node);
321 /* collect the Proj's in the Proj list */
322 switch (get_Proj_proj(node)) {
323 case pn_Call_M_regular:
324 case pn_Call_X_except:
325 case pn_Call_X_regular:
326 case pn_Call_M_except:
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) {
344 ir_node *call, *next, *proj;
346 ir_graph *rem = current_ir_graph;
348 current_ir_graph = irg;
350 /* First step: go through the list of calls and mark them. */
351 for (call = call_list; call; call = next) {
352 next = get_irn_link(call);
354 /* current_ir_graph is in memory anyway, so it's a good marker */
355 set_irn_link(call, ¤t_ir_graph);
356 hook_func_call(irg, call);
359 /* Second step: Remove all exception Proj's */
360 for (proj = proj_list; proj; proj = next) {
361 next = get_irn_link(proj);
362 call = get_Proj_pred(proj);
364 /* handle only marked calls */
365 if (get_irn_link(call) != ¤t_ir_graph)
368 /* kill any exception flow */
369 switch (get_Proj_proj(proj)) {
370 case pn_Call_X_except:
371 case pn_Call_M_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);
406 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top);
409 * Calculate the bigger property of two. Handle the temporary flag right.
411 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) {
431 unsigned m, mode = mtp_property_const;
436 if (mode == mtp_no_property)
437 return mtp_no_property;
439 if (irn_visited_else_mark(node))
442 switch (get_irn_opcode(node)) {
444 node = get_Proj_pred(node);
453 /* do a dfs search */
454 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
455 m = _follow_mem(get_irn_n(node, i));
456 mode = max_property(mode, m);
457 if (mode == mtp_no_property)
458 return mtp_no_property;
463 /* Beware volatile Loads are NOT allowed in pure functions. */
464 if (get_Load_volatility(node) == volatility_is_volatile)
465 return mtp_no_property;
466 mode = max_property(mode, mtp_property_pure);
467 node = get_Load_mem(node);
471 /* A call is only tolerable if its either constant or pure. */
472 ptr = get_Call_ptr(node);
473 if (is_SymConst_addr_ent(ptr)) {
474 ir_entity *ent = get_SymConst_entity(ptr);
475 ir_graph *irg = get_entity_irg(ent);
477 if (irg == current_ir_graph) {
478 /* A self-recursive call. The property did not depend on this call. */
479 } else if (irg == NULL) {
480 m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
481 mode = max_property(mode, m);
482 } else if (irg != NULL) {
483 /* we have a graph, analyze it. */
484 m = check_const_or_pure_function(irg, /*top=*/0);
485 mode = max_property(mode, m);
488 return mtp_no_property;
489 node = get_Call_mem(node);
493 return mtp_no_property;
499 * Follow the memory chain starting at node and determine
502 * @return mtp_property_const if only calls of const functions are detected
503 * mtp_property_pure if only Loads and const/pure calls detected
504 * mtp_no_property else
506 static unsigned follow_mem(ir_node *node, unsigned mode) {
509 m = _follow_mem(node);
510 return max_property(mode, m);
514 * Check if a graph represents a const or a pure function.
516 * @param irg the graph to check
517 * @param top if set, this is the top call
519 static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
520 ir_node *end, *endbl;
522 unsigned prop = get_irg_additional_properties(irg);
523 ir_graph *rem = current_ir_graph;
525 if (prop & mtp_property_const) {
526 /* already marked as a const function */
527 return mtp_property_const;
529 if (prop & mtp_property_pure) {
530 /* already marked as a pure function */
531 return mtp_property_pure;
534 if (IS_IRG_READY(irg)) {
535 /* already checked */
536 return mtp_no_property;
538 if (IS_IRG_BUSY(irg)) {
539 /* we are still evaluate this method. Be optimistic,
540 return the best possible so far but mark the result as temporary. */
541 return mtp_temporary | mtp_property_const;
545 end = get_irg_end(irg);
546 endbl = get_nodes_block(end);
547 prop = mtp_property_const;
549 current_ir_graph = irg;
551 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
552 inc_irg_visited(irg);
553 /* mark the initial mem: recursion of follow_mem() stops here */
554 mark_irn_visited(get_irg_initial_mem(irg));
556 /* visit every Return */
557 for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
558 ir_node *node = get_Block_cfgpred(endbl, j);
559 ir_opcode code = get_irn_opcode(node);
562 /* Bad nodes usually do NOT produce anything, so it's ok */
566 if (code == iro_Return) {
567 mem = get_Return_mem(node);
569 /* Bad nodes usually do NOT produce anything, so it's ok */
573 if (mem != get_irg_initial_mem(irg))
574 prop = max_property(prop, follow_mem(mem, prop));
576 /* Exception found. Cannot be const or pure. */
577 prop = mtp_no_property;
580 if (prop == mtp_no_property)
584 if (prop != mtp_no_property) {
585 /* check, if a keep-alive exists */
586 for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
587 ir_node *kept = get_End_keepalive(end, j);
589 if (is_Block(kept)) {
590 prop = mtp_no_property;
594 if (mode_M != get_irn_mode(kept))
597 prop = max_property(prop, follow_mem(kept, prop));
598 if (prop == mtp_no_property)
603 if (prop != mtp_no_property) {
604 if (top || (prop & mtp_temporary) == 0) {
605 /* We use the temporary flag here to mark optimistic result.
606 Set the property only if we are sure that it does NOT base on
607 temporary results OR if we are at top-level. */
608 set_irg_additional_property(irg, prop & ~mtp_temporary);
615 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
616 current_ir_graph = rem;
618 } /* check_const_or_pure_function */
621 * Handle calls to const functions.
625 static void handle_const_Calls(env_t *ctx) {
628 ctx->n_calls_SymConst = 0;
629 ctx->n_calls_Sel = 0;
631 /* all calls of const functions can be transformed */
632 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
633 ir_graph *irg = get_irp_irg(i);
635 ctx->float_const_call_list = NULL;
636 ctx->nonfloat_const_call_list = NULL;
637 ctx->pure_call_list = NULL;
638 ctx->proj_list = NULL;
640 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
641 irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
643 if (ctx->float_const_call_list != NULL)
644 fix_const_call_lists(irg, ctx);
645 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
647 } /* handle_const_Calls */
650 * Handle calls to nothrow functions.
654 static void handle_nothrow_Calls(env_t *ctx) {
657 ctx->n_calls_SymConst = 0;
658 ctx->n_calls_Sel = 0;
660 /* all calls of const functions can be transformed */
661 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
662 ir_graph *irg = get_irp_irg(i);
664 ctx->nothrow_call_list = NULL;
665 ctx->proj_list = NULL;
667 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
668 irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);
670 if (ctx->nothrow_call_list)
671 fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
672 ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
677 * Check, whether a given node represents a return value of
678 * a malloc like function (ie, new heap allocated memory).
680 * @param node the node to check
682 static int is_malloc_call_result(const ir_node *node) {
683 if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
684 /* Firm style high-level allocation */
687 if (is_alloc_entity != NULL && is_Call(node)) {
688 ir_node *ptr = get_Call_ptr(node);
690 if (is_Global(ptr)) {
691 ir_entity *ent = get_Global_entity(ptr);
692 return is_alloc_entity(ent);
696 } /* is_malloc_call_result */
699 * Update a property depending on a call property.
701 static unsigned update_property(unsigned orig_prop, unsigned call_prop) {
702 unsigned t = (orig_prop | call_prop) & mtp_temporary;
703 unsigned r = orig_prop & call_prop;
705 } /** update_property */
708 * Check if a node is stored.
710 static int is_stored(const ir_node *n) {
711 const ir_edge_t *edge;
714 foreach_out_edge(n, edge) {
715 const ir_node *succ = get_edge_src_irn(edge);
717 switch (get_irn_opcode(succ)) {
724 if (get_Store_value(succ) == n)
726 /* ok if its only the address input */
735 ptr = get_Call_ptr(succ);
736 if (is_Global(ptr)) {
737 ir_entity *ent = get_Global_entity(ptr);
740 /* we know the called entity */
741 for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
742 if (get_Call_param(succ, i) == n) {
743 /* n is the i'th param of the call */
744 if (get_method_param_access(ent, i) & ptr_access_store) {
745 /* n is store in ent */
751 /* unknown call address */
756 /* bad, potential alias */
764 * Check that the return value of an irg is not stored anywhere.
766 * return ~mtp_property_malloc if return values are stored, ~0 else
768 static unsigned check_stored_result(ir_graph *irg) {
769 ir_node *end_blk = get_irg_end_block(irg);
772 int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);
774 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
775 ir_node *pred = get_Block_cfgpred(end_blk, i);
777 if (! is_Return(pred))
779 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
780 const ir_node *irn = get_Return_res(pred, j);
782 if (is_stored(irn)) {
783 /* bad, might create an alias */
784 res = ~mtp_property_malloc;
791 edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
793 } /* check_stored_result */
796 * Check if a graph represents a nothrow or a malloc function.
798 * @param irg the graph to check
799 * @param top if set, this is the top call
801 static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) {
802 ir_node *end_blk = get_irg_end_block(irg);
806 unsigned curr_prop = mtp_property_malloc | mtp_property_nothrow;
808 if (IS_IRG_READY(irg)) {
809 /* already checked */
810 return get_irg_additional_properties(irg);
812 if (IS_IRG_BUSY(irg)) {
813 /* we are still evaluate this method. Be optimistic,
814 return the best possible so far but mark the result as temporary. */
815 return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
819 ent = get_irg_entity(irg);
820 mtp = get_entity_type(ent);
822 if (get_method_n_ress(mtp) <= 0)
823 curr_prop &= ~mtp_property_malloc;
825 for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
826 ir_node *pred = get_Block_cfgpred(end_blk, i);
828 if (is_Return(pred)) {
829 if (curr_prop & mtp_property_malloc) {
830 /* check, if malloc is called here */
831 for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
832 ir_node *res = get_Return_res(pred, j);
834 /* skip Confirms and Casts */
835 res = skip_HighLevel_ops(res);
838 res = get_Proj_pred(res);
839 if (is_malloc_call_result(res)) {
840 /* ok, this is a malloc */
841 } else if (is_Call(res)) {
842 ir_node *ptr = get_Call_ptr(res);
844 if (is_Global(ptr)) {
846 ir_entity *ent = get_Global_entity(ptr);
847 ir_graph *callee = get_entity_irg(ent);
850 /* A self-recursive call. The property did not depend on this call. */
851 } else if (callee != NULL) {
852 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
853 curr_prop = update_property(curr_prop, prop);
855 curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
857 } else if (get_opt_closed_world() &&
859 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
860 /* check if all possible callees are malloc functions. */
861 int i, n_callees = get_Call_n_callees(res);
862 if (n_callees == 0) {
863 /* This is kind of strange: dying code or a Call that will raise an exception
864 when executed as there is no implementation to call. So better not
866 curr_prop &= ~mtp_property_malloc;
870 for (i = 0; i < n_callees; ++i) {
871 ir_entity *ent = get_Call_callee(res, i);
872 if (ent == unknown_entity) {
873 /* we don't know which entity is called here */
874 curr_prop &= ~mtp_property_malloc;
877 if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
878 curr_prop &= ~mtp_property_malloc;
882 /* if we pass the for cycle, malloc is still ok */
885 curr_prop &= ~mtp_property_malloc;
888 /* unknown return value */
889 curr_prop &= ~mtp_property_malloc;
893 } else if (curr_prop & mtp_property_nothrow) {
894 /* exception flow detected */
895 pred = skip_Proj(pred);
898 ir_node *ptr = get_Call_ptr(pred);
900 if (is_Global(ptr)) {
902 ir_entity *ent = get_Global_entity(ptr);
903 ir_graph *callee = get_entity_irg(ent);
906 /* A self-recursive call. The property did not depend on this call. */
907 } else if (callee != NULL) {
908 /* Note: we check here for nothrow only, so do NOT reset the malloc property */
909 unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
910 curr_prop = update_property(curr_prop, prop);
912 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
913 curr_prop &= ~mtp_property_nothrow;
915 } else if (get_opt_closed_world() &&
917 get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
918 /* check if all possible callees are nothrow functions. */
919 int i, n_callees = get_Call_n_callees(pred);
920 if (n_callees == 0) {
921 /* This is kind of strange: dying code or a Call that will raise an exception
922 when executed as there is no implementation to call. So better not
924 curr_prop &= ~mtp_property_nothrow;
928 for (i = 0; i < n_callees; ++i) {
929 ir_entity *ent = get_Call_callee(pred, i);
930 if (ent == unknown_entity) {
931 /* we don't know which entity is called here */
932 curr_prop &= ~mtp_property_nothrow;
935 if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
936 curr_prop &= ~mtp_property_nothrow;
940 /* if we pass the for cycle, nothrow is still ok */
943 curr_prop &= ~mtp_property_nothrow;
946 /* real exception flow possible. */
947 curr_prop &= ~mtp_property_nothrow;
950 if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
951 /* no need to search further */
956 if (curr_prop & mtp_property_malloc) {
958 * Note that the malloc property means not only return newly allocated
959 * memory, but also that this memory is ALIAS FREE.
960 * To ensure that, we do NOT allow that the returned memory is somewhere
963 curr_prop &= check_stored_result(irg);
966 if (curr_prop != mtp_no_property) {
967 if (top || (curr_prop & mtp_temporary) == 0) {
968 /* We use the temporary flag here to mark an optimistic result.
969 Set the property only if we are sure that it does NOT base on
970 temporary results OR if we are at top-level. */
971 set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
979 } /* check_nothrow_or_malloc */
982 * When a function was detected as "const", it might be moved out of loops.
983 * This might be dangerous if the graph can contain endless loops.
985 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 set_irg_additional_property(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) {
1075 FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
1076 } /* firm_init_funccalls */
1079 ir_prog_pass_t pass;
1081 check_alloc_entity_func callback;
1085 * Wrapper for running optimize_funccalls() as an ir_prog pass.
1087 static int pass_wrapper(ir_prog *irp, void *context)
1089 struct pass_t *pass = context;
1092 optimize_funccalls(pass->force_run, pass->callback);
1094 } /* pass_wrapper */
1096 /* Creates an ir_prog pass for optimize_funccalls. */
1097 ir_prog_pass_t *optimize_funccalls_pass(
1099 int force_run, check_alloc_entity_func callback)
1101 struct pass_t *pass = XMALLOCZ(struct pass_t);
1103 pass->force_run = force_run;
1104 pass->callback = callback;
1106 return def_prog_pass_constructor(
1107 &pass->pass, name ? name : "funccall", pass_wrapper);
1108 } /* optimize_funccalls_pass */