X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ffunccall.c;h=e379ddf8336ce911e57faf7e24daa5b7cadc6314;hb=aa834ed8cb6e39e4f25f1f6f6a3ba5e2b559cb64;hp=1093ef209f01ef358f3090544b72a747eaf57dd7;hpb=d935aa267d00966c360931d2f0f43008030c0592;p=libfirm diff --git a/ir/opt/funccall.c b/ir/opt/funccall.c index 1093ef209..e379ddf83 100644 --- a/ir/opt/funccall.c +++ b/ir/opt/funccall.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -21,28 +21,26 @@ * @file * @brief Optimization of function calls. * @author Michael Beck - * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif -#include - -#include "funccall_t.h" +#include "opt_init.h" +#include #include "irnode_t.h" #include "irgraph_t.h" #include "irgmod.h" #include "irgwalk.h" -#include "irvrfy.h" #include "dbginfo_t.h" #include "irflag_t.h" #include "irloop_t.h" #include "ircons.h" #include "iredges_t.h" +#include "irpass_t.h" +#include "iroptimize.h" #include "analyze_irg_args.h" #include "irhooks.h" +#include "raw_bitset.h" #include "debug.h" DEBUG_ONLY(static firm_dbg_module_t *dbg;) @@ -50,9 +48,7 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg;) /** * The walker environment for updating function calls. */ -typedef struct _env_t { - unsigned n_calls_SymConst; - unsigned n_calls_Sel; +typedef struct env_t { ir_node *float_const_call_list; /**< The list of all floating const function calls that will be changed. */ ir_node *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */ ir_node *pure_call_list; /**< The list of all pure function calls that will be changed. */ @@ -60,75 +56,33 @@ typedef struct _env_t { ir_node *proj_list; /**< The list of all potential Proj nodes that must be fixed. */ } env_t; -/** If non-null, evaluates entities for being a heap alloc. */ -static check_alloc_entity_func is_alloc_entity = NULL; - /** Ready IRG's are marked in the ready set. */ static unsigned *ready_set; /** IRG's that are in progress are marked here. */ static unsigned *busy_set; -/** - * We misuse the mtp_property_inherited flag as temporary here. - * The is ok, as we cannot set or get it anyway using the - * get_addtional_properties API. - */ -#define mtp_temporary mtp_property_inherited - /** * Walker: Collect all calls to const and pure functions * to lists. Collect all Proj(Call) nodes into a Proj list. */ -static void collect_const_and_pure_calls(ir_node *node, void *env) { - env_t *ctx = env; - ir_node *call, *ptr; - ir_entity *ent; - unsigned and_prop, or_prop, prop; +static void collect_const_and_pure_calls(ir_node *node, void *env) +{ + env_t *ctx = (env_t*)env; if (is_Call(node)) { - call = node; + ir_node *call = node; /* set the link to NULL for all non-const/pure calls */ set_irn_link(call, NULL); - ptr = get_Call_ptr(call); - if (is_Global(ptr)) { - ent = get_Global_entity(ptr); - - prop = get_entity_additional_properties(ent); - if ((prop & (mtp_property_const|mtp_property_pure)) == 0) - return; - ++ctx->n_calls_SymConst; - } else if (get_opt_closed_world() && - is_Sel(ptr) && - get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) { - /* If all possible callees are const functions, we can remove the memory edge. */ - int i, n_callees = get_Call_n_callees(call); - if (n_callees == 0) { - /* This is kind of strange: dying code or a Call that will raise an exception - when executed as there is no implementation to call. So better not - optimize. */ - return; - } + ir_node *ptr = get_Call_ptr(call); + if (!is_SymConst_addr_ent(ptr)) + return; - /* note that const function are a subset of pure ones */ - and_prop = mtp_property_const | mtp_property_pure; - or_prop = 0; - for (i = 0; i < n_callees; ++i) { - ent = get_Call_callee(call, i); - if (ent == unknown_entity) { - /* we don't know which entity is called here */ - return; - } - prop = get_entity_additional_properties(ent); - and_prop &= prop; - or_prop &= prop; - if (and_prop == mtp_no_property) - return; - } - prop = and_prop | (or_prop & mtp_property_has_loop); - ++ctx->n_calls_Sel; - } else + ir_entity *ent = get_SymConst_entity(ptr); + + unsigned prop = get_entity_additional_properties(ent); + if ((prop & (mtp_property_const|mtp_property_pure)) == 0) return; /* ok, if we get here we found a call to a const or a pure function */ @@ -149,16 +103,15 @@ static void collect_const_and_pure_calls(ir_node *node, void *env) { * Collect all memory and exception Proj's from * calls. */ - call = get_Proj_pred(node); - if (! is_Call(call)) + ir_node *call = get_Proj_pred(node); + if (!is_Call(call)) return; /* collect the Proj's in the Proj list */ switch (get_Proj_proj(node)) { - case pn_Call_M_regular: + case pn_Call_M: case pn_Call_X_except: case pn_Call_X_regular: - case pn_Call_M_except: set_irn_link(node, ctx->proj_list); ctx->proj_list = node; break; @@ -166,7 +119,7 @@ static void collect_const_and_pure_calls(ir_node *node, void *env) { break; } } -} /* collect_const_and_pure_calls */ +} /** * Fix the list of collected Calls. @@ -174,19 +127,17 @@ static void collect_const_and_pure_calls(ir_node *node, void *env) { * @param irg the graph that contained calls to pure functions * @param ctx context */ -static void fix_const_call_lists(ir_graph *irg, env_t *ctx) { - ir_node *call, *next, *mem, *proj; - int exc_changed = 0; - ir_graph *rem = current_ir_graph; - - current_ir_graph = irg; +static void fix_const_call_lists(ir_graph *irg, env_t *ctx) +{ + bool exc_changed = false; /* First step: fix all calls by removing their memory input and let * them floating. * The original memory input is preserved in their link fields. */ - for (call = ctx->float_const_call_list; call != NULL; call = next) { - next = get_irn_link(call); - mem = get_Call_mem(call); + ir_node *next; + for (ir_node *call = ctx->float_const_call_list; call != NULL; call = next) { + next = (ir_node*)get_irn_link(call); + ir_node *mem = get_Call_mem(call); set_irn_link(call, mem); set_Call_mem(call, get_irg_no_mem(irg)); @@ -212,10 +163,10 @@ static void fix_const_call_lists(ir_graph *irg, env_t *ctx) { } /* Last step: fix all Proj's */ - for (proj = ctx->proj_list; proj != NULL; proj = next) { - next = get_irn_link(proj); - call = get_Proj_pred(proj); - mem = get_irn_link(call); + for (ir_node *proj = ctx->proj_list; proj != NULL; proj = next) { + next = (ir_node*)get_irn_link(proj); + ir_node *call = get_Proj_pred(proj); + ir_node *mem = (ir_node*)get_irn_link(call); /* beware of calls in the pure call list */ if (!mem || is_Call(mem)) @@ -223,88 +174,55 @@ static void fix_const_call_lists(ir_graph *irg, env_t *ctx) { assert(get_irn_mode(mem) == mode_M); switch (get_Proj_proj(proj)) { - case pn_Call_M_regular: { + case pn_Call_M: { /* in dead code there might be cycles where proj == mem */ if (proj != mem) exchange(proj, mem); break; } case pn_Call_X_except: - case pn_Call_M_except: - exc_changed = 1; - exchange(proj, get_irg_bad(irg)); + exc_changed = true; + exchange(proj, new_r_Bad(irg, mode_X)); break; case pn_Call_X_regular: { ir_node *block = get_nodes_block(call); - exc_changed = 1; - exchange(proj, new_r_Jmp(irg, block)); + exc_changed = true; + exchange(proj, new_r_Jmp(block)); break; } default: - ; + break; } } - /* changes were done ... */ - set_irg_outs_inconsistent(irg); - set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent); - if (exc_changed) { /* ... including exception edges */ - set_irg_doms_inconsistent(irg); + clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO); } - current_ir_graph = rem; -} /* fix_const_call_list */ +} /** * Walker: Collect all calls to nothrow functions * to lists. Collect all Proj(Call) nodes into a Proj list. */ -static void collect_nothrow_calls(ir_node *node, void *env) { - env_t *ctx = env; - ir_node *call, *ptr; - ir_entity *ent; - unsigned prop; +static void collect_nothrow_calls(ir_node *node, void *env) +{ + env_t *ctx = (env_t*)env; if (is_Call(node)) { - call = node; + ir_node *call = node; /* set the link to NULL for all non-const/pure calls */ set_irn_link(call, NULL); - ptr = get_Call_ptr(call); - if (is_Global(ptr)) { - ent = get_Global_entity(ptr); - - prop = get_entity_additional_properties(ent); - if ((prop & mtp_property_nothrow) == 0) - return; - ++ctx->n_calls_SymConst; - } else if (get_opt_closed_world() && - is_Sel(ptr) && - get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) { - /* If all possible callees are nothrow functions, we can remove the exception edge. */ - int i, n_callees = get_Call_n_callees(call); - if (n_callees == 0) { - /* This is kind of strange: dying code or a Call that will raise an exception - when executed as there is no implementation to call. So better not - optimize. */ - return; - } + ir_node *ptr = get_Call_ptr(call); + if (!is_SymConst_addr_ent(ptr)) + return; - /* note that const function are a subset of pure ones */ - prop = mtp_property_nothrow; - for (i = 0; i < n_callees; ++i) { - ent = get_Call_callee(call, i); - if (ent == unknown_entity) { - /* we don't know which entity is called here */ - return; - } - prop &= get_entity_additional_properties(ent); - if (prop == mtp_no_property) - return; - } - ++ctx->n_calls_Sel; - } else + ir_entity *ent = get_SymConst_entity(ptr); + + unsigned prop = get_entity_additional_properties(ent); + if ((prop & mtp_property_nothrow) == 0) return; /* ok, if we get here we found a call to a nothrow function */ @@ -315,16 +233,15 @@ static void collect_nothrow_calls(ir_node *node, void *env) { * Collect all memory and exception Proj's from * calls. */ - call = get_Proj_pred(node); + ir_node *call = get_Proj_pred(node); if (! is_Call(call)) return; /* collect the Proj's in the Proj list */ switch (get_Proj_proj(node)) { - case pn_Call_M_regular: + case pn_Call_M: case pn_Call_X_except: case pn_Call_X_regular: - case pn_Call_M_except: set_irn_link(node, ctx->proj_list); ctx->proj_list = node; break; @@ -332,7 +249,7 @@ static void collect_nothrow_calls(ir_node *node, void *env) { break; } } -} /* collect_nothrow_calls */ +} /** * Fix the list of collected nothrow Calls. @@ -341,16 +258,15 @@ static void collect_nothrow_calls(ir_node *node, void *env) { * @param call_list the list of all call sites of const functions * @param proj_list the list of all memory/exception Proj's of this call sites */ -static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) { - ir_node *call, *next, *proj; - int exc_changed = 0; - ir_graph *rem = current_ir_graph; - - current_ir_graph = irg; +static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, + ir_node *proj_list) +{ + bool exc_changed = false; /* First step: go through the list of calls and mark them. */ - for (call = call_list; call; call = next) { - next = get_irn_link(call); + ir_node *next; + for (ir_node *call = call_list; call; call = next) { + next = (ir_node*)get_irn_link(call); /* current_ir_graph is in memory anyway, so it's a good marker */ set_irn_link(call, ¤t_ir_graph); @@ -358,9 +274,9 @@ static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *pr } /* Second step: Remove all exception Proj's */ - for (proj = proj_list; proj; proj = next) { - next = get_irn_link(proj); - call = get_Proj_pred(proj); + for (ir_node *proj = proj_list; proj; proj = next) { + next = (ir_node*)get_irn_link(proj); + ir_node *call = get_Proj_pred(proj); /* handle only marked calls */ if (get_irn_link(call) != ¤t_ir_graph) @@ -369,70 +285,65 @@ static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *pr /* kill any exception flow */ switch (get_Proj_proj(proj)) { case pn_Call_X_except: - case pn_Call_M_except: - exc_changed = 1; - exchange(proj, get_irg_bad(irg)); + exc_changed = true; + exchange(proj, new_r_Bad(irg, mode_X)); break; case pn_Call_X_regular: { ir_node *block = get_nodes_block(call); - exc_changed = 1; - exchange(proj, new_r_Jmp(irg, block)); + exc_changed = true; + exchange(proj, new_r_Jmp(block)); break; } default: - ; + break; } } /* changes were done ... */ - set_irg_outs_inconsistent(irg); - set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent); - if (exc_changed) { /* ... including exception edges */ - set_irg_doms_inconsistent(irg); + clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO); } - current_ir_graph = rem; -} /* fix_nothrow_call_list */ +} /* marking */ -#define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg)) +#define SET_IRG_READY(irg) rbitset_set(ready_set, get_irg_idx(irg)) #define IS_IRG_READY(irg) rbitset_is_set(ready_set, get_irg_idx(irg)) #define SET_IRG_BUSY(irg) rbitset_set(busy_set, get_irg_idx(irg)) #define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg)) #define IS_IRG_BUSY(irg) rbitset_is_set(busy_set, get_irg_idx(irg)) /* forward */ -static unsigned check_const_or_pure_function(ir_graph *irg, int top); -static unsigned check_nothrow_or_malloc(ir_graph *irg, int top); +static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, bool top); /** * Calculate the bigger property of two. Handle the temporary flag right. */ -static unsigned max_property(unsigned a, unsigned b) { - unsigned r, t = (a | b) & mtp_temporary; +static mtp_additional_properties max_property(mtp_additional_properties a, + mtp_additional_properties b) +{ + mtp_additional_properties t = (a | b) & mtp_temporary; a &= ~mtp_temporary; b &= ~mtp_temporary; if (a == mtp_no_property || b == mtp_no_property) return mtp_no_property; - r = a > b ? a : b; + mtp_additional_properties r = a > b ? a : b; return r | t; -} /* max_property */ +} /** * Follow the memory chain starting at node and determine * the mtp_property. * * @return mtp_property_const if only calls of const functions are detected - * mtp_property_pure if only Loads and const/pure - * calls detected - * mtp_no_property else + * mtp_property_pure if only Loads and const/pure calls detected + * mtp_no_property else */ -static unsigned _follow_mem(ir_node *node) { - unsigned m, mode = mtp_property_const; - ir_node *ptr; - int i; +static mtp_additional_properties follow_mem_(ir_node *node) +{ + mtp_additional_properties mode = mtp_property_const; for (;;) { if (mode == mtp_no_property) @@ -453,8 +364,8 @@ static unsigned _follow_mem(ir_node *node) { case iro_Phi: case iro_Sync: /* do a dfs search */ - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - m = _follow_mem(get_irn_n(node, i)); + for (int i = get_irn_arity(node) - 1; i >= 0; --i) { + mtp_additional_properties m = follow_mem_(get_irn_n(node, i)); mode = max_property(mode, m); if (mode == mtp_no_property) return mtp_no_property; @@ -469,33 +380,33 @@ static unsigned _follow_mem(ir_node *node) { node = get_Load_mem(node); break; - case iro_Call: + case iro_Call: { /* A call is only tolerable if its either constant or pure. */ - ptr = get_Call_ptr(node); - if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) { - ir_entity *ent = get_SymConst_entity(ptr); - ir_graph *irg = get_entity_irg(ent); - - if (irg == current_ir_graph) { - /* A self-recursive call. The property did not depend on this call. */ - } else if (irg == NULL) { - m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure); - mode = max_property(mode, m); - } else if (irg != NULL) { - /* we have a graph, analyze it. */ - m = check_const_or_pure_function(irg, /*top=*/0); - mode = max_property(mode, m); - } - } else + ir_node *ptr = get_Call_ptr(node); + if (!is_SymConst_addr_ent(ptr)) return mtp_no_property; + + ir_entity *ent = get_SymConst_entity(ptr); + ir_graph *irg = get_entity_irg(ent); + + mtp_additional_properties m; + if (irg == NULL) { + m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure); + mode = max_property(mode, m); + } else { + /* we have a graph, analyze it. */ + m = check_const_or_pure_function(irg, false); + mode = max_property(mode, m); + } node = get_Call_mem(node); break; + } default: return mtp_no_property; } } -} /* _follow_mem */ +} /** * Follow the memory chain starting at node and determine @@ -505,12 +416,11 @@ static unsigned _follow_mem(ir_node *node) { * mtp_property_pure if only Loads and const/pure calls detected * mtp_no_property else */ -static unsigned follow_mem(ir_node *node, unsigned mode) { - unsigned m; - - m = _follow_mem(node); +static mtp_additional_properties follow_mem(ir_node *node, mtp_additional_properties mode) +{ + mtp_additional_properties m = follow_mem_(node); return max_property(mode, m); -} /* follow_mem */ +} /** * Check if a graph represents a const or a pure function. @@ -518,11 +428,23 @@ static unsigned follow_mem(ir_node *node, unsigned mode) { * @param irg the graph to check * @param top if set, this is the top call */ -static unsigned check_const_or_pure_function(ir_graph *irg, int top) { - ir_node *end, *endbl; - int j; - unsigned prop = get_irg_additional_properties(irg); - ir_graph *rem = current_ir_graph; +static mtp_additional_properties check_const_or_pure_function(ir_graph *irg, bool top) +{ + ir_entity *entity = get_irg_entity(irg); + ir_type *type = get_entity_type(entity); + size_t n_params = get_method_n_params(type); + mtp_additional_properties may_be_const = mtp_property_const; + mtp_additional_properties prop = get_entity_additional_properties(entity); + + /* libfirm handles aggregate parameters by passing around pointers to + * stuff in memory, so if we have compound parameters we are never const */ + for (size_t i = 0; i < n_params; ++i) { + ir_type *param = get_method_param_type(type, i); + if (is_compound_type(param)) { + prop &= ~mtp_property_const; + may_be_const = mtp_no_property; + } + } if (prop & mtp_property_const) { /* already marked as a const function */ @@ -538,34 +460,32 @@ static unsigned check_const_or_pure_function(ir_graph *irg, int top) { return mtp_no_property; } if (IS_IRG_BUSY(irg)) { - /* we are still evaluate this method. Be optimistic, - return the best possible so far but mark the result as temporary. */ - return mtp_temporary | mtp_property_const; + /* We are still evaluate this method. + * The function (indirectly) calls itself and thus may not terminate. */ + return mtp_no_property; } SET_IRG_BUSY(irg); - end = get_irg_end(irg); - endbl = get_nodes_block(end); - prop = mtp_property_const; - - current_ir_graph = irg; + ir_node *end = get_irg_end(irg); + ir_node *endbl = get_nodes_block(end); + prop = may_be_const; + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); - /* mark the initial mem: recursion of follow_mem stops here */ + /* mark the initial mem: recursion of follow_mem() stops here */ mark_irn_visited(get_irg_initial_mem(irg)); /* visit every Return */ - for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) { - ir_node *node = get_Block_cfgpred(endbl, j); - ir_opcode code = get_irn_opcode(node); - ir_node *mem; + for (int j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) { + ir_node *node = get_Block_cfgpred(endbl, j); + unsigned code = get_irn_opcode(node); /* Bad nodes usually do NOT produce anything, so it's ok */ if (code == iro_Bad) continue; if (code == iro_Return) { - mem = get_Return_mem(node); + ir_node *mem = get_Return_mem(node); /* Bad nodes usually do NOT produce anything, so it's ok */ if (is_Bad(mem)) @@ -584,7 +504,7 @@ static unsigned check_const_or_pure_function(ir_graph *irg, int top) { if (prop != mtp_no_property) { /* check, if a keep-alive exists */ - for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) { + for (int j = get_End_n_keepalives(end) - 1; j >= 0; --j) { ir_node *kept = get_End_keepalive(end, j); if (is_Block(kept)) { @@ -601,79 +521,68 @@ static unsigned check_const_or_pure_function(ir_graph *irg, int top) { } } - if (prop != mtp_no_property) { - if (top || (prop & mtp_temporary) == 0) { - /* We use the temporary flag here to mark optimistic result. - Set the property only if we are sure that it does NOT base on - temporary results OR if we are at top-level. */ - set_irg_additional_property(irg, prop & ~mtp_temporary); - SET_IRG_READY(irg); + if (top) { + /* Set the property only if we are at top-level. */ + if (prop != mtp_no_property) { + add_entity_additional_properties(entity, prop); } - } - if (top) SET_IRG_READY(irg); + } CLEAR_IRG_BUSY(irg); - current_ir_graph = rem; + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); return prop; -} /* check_const_or_pure_function */ +} /** * Handle calls to const functions. * * @param ctx context */ -static void handle_const_Calls(env_t *ctx) { - int i; - - ctx->n_calls_SymConst = 0; - ctx->n_calls_Sel = 0; - +static void handle_const_Calls(env_t *ctx) +{ /* all calls of const functions can be transformed */ - for (i = get_irp_n_irgs() - 1; i >= 0; --i) { - ir_graph *irg = get_irp_irg(i); + size_t n = get_irp_n_irgs(); + for (size_t i = 0; i < n; ++i) { + ir_graph *irg = get_irp_irg(i); ctx->float_const_call_list = NULL; ctx->nonfloat_const_call_list = NULL; ctx->pure_call_list = NULL; ctx->proj_list = NULL; - irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx); - if (ctx->float_const_call_list != NULL) { - fix_const_call_lists(irg, ctx); + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); + irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx); + fix_const_call_lists(irg, ctx); + ir_free_resources(irg, IR_RESOURCE_IRN_LINK); - /* this graph was changed, invalidate analysis info */ - set_irg_outs_inconsistent(irg); - set_irg_doms_inconsistent(irg); - } + confirm_irg_properties(irg, + IR_GRAPH_PROPERTIES_CONTROL_FLOW + | IR_GRAPH_PROPERTY_ONE_RETURN + | IR_GRAPH_PROPERTY_MANY_RETURNS); } -} /* handle_const_Calls */ +} /** * Handle calls to nothrow functions. * * @param ctx context */ -static void handle_nothrow_Calls(env_t *ctx) { - int i; - - ctx->n_calls_SymConst = 0; - ctx->n_calls_Sel = 0; - +static void handle_nothrow_Calls(env_t *ctx) +{ /* all calls of const functions can be transformed */ - for (i = get_irp_n_irgs() - 1; i >= 0; --i) { + size_t n = get_irp_n_irgs(); + for (size_t i = 0; i < n; ++i) { ir_graph *irg = get_irp_irg(i); ctx->nothrow_call_list = NULL; ctx->proj_list = NULL; + + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx); - if (ctx->nothrow_call_list) { + if (ctx->nothrow_call_list) fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list); - - /* this graph was changed, invalidate analysis info */ - set_irg_outs_inconsistent(irg); - set_irg_doms_inconsistent(irg); - } + ir_free_resources(irg, IR_RESOURCE_IRN_LINK); } } @@ -683,37 +592,32 @@ static void handle_nothrow_Calls(env_t *ctx) { * * @param node the node to check */ -static int is_malloc_call_result(const ir_node *node) { +static bool is_malloc_call_result(const ir_node *node) +{ if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) { /* Firm style high-level allocation */ - return 1; + return true; } - if (is_alloc_entity != NULL && is_Call(node)) { - ir_node *ptr = get_Call_ptr(node); - - if (is_Global(ptr)) { - ir_entity *ent = get_Global_entity(ptr); - return is_alloc_entity(ent); - } - } - return 0; -} /* is_malloc_call_result */ + /* TODO: check mtp_malloc */ + return false; +} /** * Update a property depending on a call property. */ -static unsigned update_property(unsigned orig_prop, unsigned call_prop) { - unsigned t = (orig_prop | call_prop) & mtp_temporary; - unsigned r = orig_prop & call_prop; +static mtp_additional_properties update_property(mtp_additional_properties orig_prop, mtp_additional_properties call_prop) +{ + mtp_additional_properties t = (orig_prop | call_prop) & mtp_temporary; + mtp_additional_properties r = orig_prop & call_prop; return r | t; -} /** update_property */ +} /** * Check if a node is stored. */ -static int is_stored(const ir_node *n) { - const ir_edge_t *edge; - const ir_node *ptr; +static bool is_stored(const ir_node *n) +{ + const ir_node *ptr; foreach_out_edge(n, edge) { const ir_node *succ = get_edge_src_irn(edge); @@ -726,62 +630,63 @@ static int is_stored(const ir_node *n) { break; case iro_Store: if (get_Store_value(succ) == n) - return 1; + return true; /* ok if its only the address input */ break; case iro_Sel: case iro_Cast: case iro_Confirm: if (is_stored(succ)) - return 1; + return true; break; case iro_Call: ptr = get_Call_ptr(succ); - if (is_Global(ptr)) { - ir_entity *ent = get_Global_entity(ptr); - int i; + if (is_SymConst_addr_ent(ptr)) { + ir_entity *ent = get_SymConst_entity(ptr); + size_t i; /* we know the called entity */ - for (i = get_Call_n_params(succ) - 1; i >= 0; --i) { - if (get_Call_param(succ, i) == n) { + for (i = get_Call_n_params(succ); i > 0;) { + if (get_Call_param(succ, --i) == n) { /* n is the i'th param of the call */ if (get_method_param_access(ent, i) & ptr_access_store) { /* n is store in ent */ - return 1; + return true; } } } } else { /* unknown call address */ - return 1; + return true; } break; default: /* bad, potential alias */ - return 1; + return true; } } - return 0; -} /* is_stored */ + return false; +} /** * Check that the return value of an irg is not stored anywhere. * * return ~mtp_property_malloc if return values are stored, ~0 else */ -static unsigned check_stored_result(ir_graph *irg) { - ir_node *end_blk = get_irg_end_block(irg); - int i, j; - unsigned res = ~0; - int old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL); +static mtp_additional_properties check_stored_result(ir_graph *irg) +{ + ir_node *end_blk = get_irg_end_block(irg); + mtp_additional_properties res = ~mtp_no_property; + + assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES); - for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) { + for (int i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred(end_blk, i); if (! is_Return(pred)) continue; - for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) { - const ir_node *irn = get_Return_res(pred, j); + for (size_t j = get_Return_n_ress(pred); j > 0;) { + const ir_node *irn = get_Return_res(pred, --j); if (is_stored(irn)) { /* bad, might create an alias */ @@ -791,10 +696,9 @@ static unsigned check_stored_result(ir_graph *irg) { } } finish: - if (! old_edges) - edges_deactivate_kind(irg, EDGE_KIND_NORMAL); + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL); return res; -} /* check_stored_result */ +} /** * Check if a graph represents a nothrow or a malloc function. @@ -802,16 +706,15 @@ finish: * @param irg the graph to check * @param top if set, this is the top call */ -static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) { - ir_node *end_blk = get_irg_end_block(irg); - ir_entity *ent; - ir_type *mtp; - int i, j; - unsigned curr_prop = mtp_property_malloc | mtp_property_nothrow; +static mtp_additional_properties check_nothrow_or_malloc(ir_graph *irg, bool top) +{ + mtp_additional_properties curr_prop + = mtp_property_malloc | mtp_property_nothrow; + ir_entity *ent = get_irg_entity(irg); if (IS_IRG_READY(irg)) { /* already checked */ - return get_irg_additional_properties(irg); + return get_entity_additional_properties(ent); } if (IS_IRG_BUSY(irg)) { /* we are still evaluate this method. Be optimistic, @@ -820,20 +723,19 @@ static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) { } SET_IRG_BUSY(irg); - ent = get_irg_entity(irg); - mtp = get_entity_type(ent); - + ir_type *mtp = get_entity_type(ent); if (get_method_n_ress(mtp) <= 0) curr_prop &= ~mtp_property_malloc; - for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) { + ir_node *end_blk = get_irg_end_block(irg); + for (int i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred(end_blk, i); if (is_Return(pred)) { if (curr_prop & mtp_property_malloc) { /* check, if malloc is called here */ - for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) { - ir_node *res = get_Return_res(pred, j); + for (size_t j = get_Return_n_ress(pred); j > 0;) { + ir_node *res = get_Return_res(pred, --j); /* skip Confirms and Casts */ res = skip_HighLevel_ops(res); @@ -845,45 +747,19 @@ static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) { } else if (is_Call(res)) { ir_node *ptr = get_Call_ptr(res); - if (is_Global(ptr)) { + if (is_SymConst_addr_ent(ptr)) { /* a direct call */ - ir_entity *ent = get_Global_entity(ptr); + ir_entity *ent = get_SymConst_entity(ptr); ir_graph *callee = get_entity_irg(ent); if (callee == irg) { /* A self-recursive call. The property did not depend on this call. */ } else if (callee != NULL) { - unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0); + mtp_additional_properties prop = check_nothrow_or_malloc(callee, false); curr_prop = update_property(curr_prop, prop); } else { curr_prop = update_property(curr_prop, get_entity_additional_properties(ent)); } - } else if (get_opt_closed_world() && - is_Sel(ptr) && - get_irg_callee_info_state(irg) == irg_callee_info_consistent) { - /* check if all possible callees are malloc functions. */ - int i, n_callees = get_Call_n_callees(res); - if (n_callees == 0) { - /* This is kind of strange: dying code or a Call that will raise an exception - when executed as there is no implementation to call. So better not - optimize. */ - curr_prop &= ~mtp_property_malloc; - continue; - } - - for (i = 0; i < n_callees; ++i) { - ir_entity *ent = get_Call_callee(res, i); - if (ent == unknown_entity) { - /* we don't know which entity is called here */ - curr_prop &= ~mtp_property_malloc; - break; - } - if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) { - curr_prop &= ~mtp_property_malloc; - break; - } - } - /* if we pass the for cycle, malloc is still ok */ } else { /* unknown call */ curr_prop &= ~mtp_property_malloc; @@ -901,47 +777,21 @@ static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) { if (is_Call(pred)) { ir_node *ptr = get_Call_ptr(pred); - if (is_Global(ptr)) { + if (is_SymConst_addr_ent(ptr)) { /* a direct call */ - ir_entity *ent = get_Global_entity(ptr); + ir_entity *ent = get_SymConst_entity(ptr); ir_graph *callee = get_entity_irg(ent); if (callee == irg) { /* A self-recursive call. The property did not depend on this call. */ } else if (callee != NULL) { /* Note: we check here for nothrow only, so do NOT reset the malloc property */ - unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc; + mtp_additional_properties prop = check_nothrow_or_malloc(callee, false) | mtp_property_malloc; curr_prop = update_property(curr_prop, prop); } else { if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) curr_prop &= ~mtp_property_nothrow; } - } else if (get_opt_closed_world() && - is_Sel(ptr) && - get_irg_callee_info_state(irg) == irg_callee_info_consistent) { - /* check if all possible callees are nothrow functions. */ - int i, n_callees = get_Call_n_callees(pred); - if (n_callees == 0) { - /* This is kind of strange: dying code or a Call that will raise an exception - when executed as there is no implementation to call. So better not - optimize. */ - curr_prop &= ~mtp_property_nothrow; - continue; - } - - for (i = 0; i < n_callees; ++i) { - ir_entity *ent = get_Call_callee(pred, i); - if (ent == unknown_entity) { - /* we don't know which entity is called here */ - curr_prop &= ~mtp_property_nothrow; - break; - } - if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) { - curr_prop &= ~mtp_property_nothrow; - break; - } - } - /* if we pass the for cycle, nothrow is still ok */ } else { /* unknown call */ curr_prop &= ~mtp_property_nothrow; @@ -958,124 +808,98 @@ static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) { } if (curr_prop & mtp_property_malloc) { - /* - * Note that the malloc property means not only return newly allocated + /* Note that the malloc property means not only return newly allocated * memory, but also that this memory is ALIAS FREE. * To ensure that, we do NOT allow that the returned memory is somewhere - * stored. - */ + * stored. */ curr_prop &= check_stored_result(irg); } - if (curr_prop != mtp_no_property) { - if (top || (curr_prop & mtp_temporary) == 0) { - /* We use the temporary flag here to mark an optimistic result. - Set the property only if we are sure that it does NOT base on - temporary results OR if we are at top-level. */ - set_irg_additional_property(irg, curr_prop & ~mtp_temporary); - SET_IRG_READY(irg); - } + if (curr_prop != mtp_no_property + && (top || (curr_prop & mtp_temporary) == 0)) { + /* We use the temporary flag here to mark an optimistic result. + * Set the property only if we are sure that it does NOT base on + * temporary results OR if we are at top-level. */ + add_entity_additional_properties(ent, curr_prop & ~mtp_temporary); + SET_IRG_READY(irg); } if (top) SET_IRG_READY(irg); CLEAR_IRG_BUSY(irg); return curr_prop; -} /* check_nothrow_or_malloc */ +} /** * When a function was detected as "const", it might be moved out of loops. - * This might be dangerous if the graph might contain endless loops. + * This might be dangerous if the graph can contain endless loops. */ -static void check_for_possible_endless_loops(ir_graph *irg) { - ir_loop *root_loop; - assure_cf_loop(irg); +static void check_for_possible_endless_loops(ir_graph *irg) +{ + assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO); + + ir_loop *root_loop = get_irg_loop(irg); + if (root_loop->flags & loop_outer_loop) { + ir_entity *ent = get_irg_entity(irg); + add_entity_additional_properties(ent, mtp_property_has_loop); + } - root_loop = get_irg_loop(irg); - if (root_loop->flags & loop_outer_loop) - set_irg_additional_property(irg, mtp_property_has_loop); + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL); } -/* - * optimize function calls by handling const functions - */ -void optimize_funccalls(int force_run, check_alloc_entity_func callback) +void optimize_funccalls(void) { - int i, last_idx; - unsigned num_const = 0; - unsigned num_pure = 0; - unsigned num_nothrow = 0; - unsigned num_malloc = 0; - - is_alloc_entity = callback; - /* prepare: mark all graphs as not analyzed */ - last_idx = get_irp_last_idx(); + size_t last_idx = get_irp_last_idx(); ready_set = rbitset_malloc(last_idx); busy_set = rbitset_malloc(last_idx); /* first step: detect, which functions are nothrow or malloc */ DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n")); - for (i = get_irp_n_irgs() - 1; i >= 0; --i) { - ir_graph *irg = get_irp_irg(i); - unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1); + for (size_t i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *irg = get_irp_irg(i); + unsigned prop = check_nothrow_or_malloc(irg, true); if (prop & mtp_property_nothrow) { - ++num_nothrow; DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg)); } else if (prop & mtp_property_malloc) { - ++num_malloc; DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg)); } } /* second step: remove exception edges: this must be done before the detection of const and pure functions take place. */ - if (force_run || num_nothrow > 0) { - env_t ctx; - - handle_nothrow_Calls(&ctx); - DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc)); - DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n", - ctx.n_calls_SymConst, ctx.n_calls_Sel)); - } else { - DB((dbg, LEVEL_1, "No graphs without side effects detected\n")); - } + env_t ctx; + handle_nothrow_Calls(&ctx); rbitset_clear_all(ready_set, last_idx); rbitset_clear_all(busy_set, last_idx); /* third step: detect, which functions are const or pure */ DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n")); - for (i = get_irp_n_irgs() - 1; i >= 0; --i) { - ir_graph *irg = get_irp_irg(i); - unsigned prop = check_const_or_pure_function(irg, /*top=*/1); + for (size_t i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *irg = get_irp_irg(i); + unsigned prop = check_const_or_pure_function(irg, true); if (prop & mtp_property_const) { - ++num_const; DB((dbg, LEVEL_2, "%+F has the const property\n", irg)); check_for_possible_endless_loops(irg); } else if (prop & mtp_property_pure) { - ++num_pure; DB((dbg, LEVEL_2, "%+F has the pure property\n", irg)); } } - if (force_run || num_const > 0) { - env_t ctx; + handle_const_Calls(&ctx); - handle_const_Calls(&ctx); - DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure)); - DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n", - ctx.n_calls_SymConst, ctx.n_calls_Sel)); - } else { - DB((dbg, LEVEL_1, "No graphs without side effects detected\n")); - } xfree(busy_set); xfree(ready_set); -} /* optimize_funccalls */ +} -/* initialize the funccall optimization */ -void firm_init_funccalls(void) { +void firm_init_funccalls(void) +{ FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls"); -// firm_dbg_set_mask(dbg, -1); -} /* firm_init_funccalls */ +} + +ir_prog_pass_t *optimize_funccalls_pass(const char *name) +{ + return def_prog_pass(name ? name : "funccall", optimize_funccalls); +}