From c19953ed6384686c23fb9d720a7cfdda3d443d19 Mon Sep 17 00:00:00 2001 From: =?utf8?q?G=C3=B6tz=20Lindenmaier?= Date: Fri, 4 Mar 2005 14:16:47 +0000 Subject: [PATCH] improvements, interessing insight about scc algorithm documented [r5295] --- ir/ana/callgraph.c | 2 +- ir/ana/execution_frequency.c | 200 +++++++++++++++++++++++++++++++++-- ir/ana/execution_frequency.h | 25 ++++- ir/ana/field_temperature.c | 13 ++- ir/ana/interval_analysis.c | 22 ++-- ir/ana/interval_analysis.h | 18 ++-- ir/ana/irloop.h | 12 ++- 7 files changed, 262 insertions(+), 30 deletions(-) diff --git a/ir/ana/callgraph.c b/ir/ana/callgraph.c index b0156344a..3caa23ff2 100644 --- a/ir/ana/callgraph.c +++ b/ir/ana/callgraph.c @@ -1118,7 +1118,7 @@ static void compute_rec_depth (ir_graph *irg, void *env) { /* ----------------------------------------------------------------------------------- */ -/* Another algorithm to compute recursion nesting depth */ +/* Another algorithm to compute the execution freqency of methods ignoring recursions. */ /* Walk the callgraph. Ignore backedges. Use sum of execution freqencies of Call */ /* nodes to evaluate a callgraph edge. */ /* ----------------------------------------------------------------------------------- */ diff --git a/ir/ana/execution_frequency.c b/ir/ana/execution_frequency.c index bacf73e3e..e740c0bf0 100644 --- a/ir/ana/execution_frequency.c +++ b/ir/ana/execution_frequency.c @@ -20,7 +20,9 @@ #include "pdeq.h" #include "irprog.h" +#include "irnode_t.h" #include "irloop.h" +#include "irgwalk.h" #include "interval_analysis.h" @@ -32,6 +34,7 @@ typedef struct { void *reg; double freq; + int prob; } reg_exec_freq; /* We use this set for all nodes in all irgraphs. */ @@ -58,6 +61,7 @@ static INLINE void set_region_exec_freq(void *reg, double freq) { INLINE double get_region_exec_freq(void *reg) { reg_exec_freq ef, *found; ef.reg = reg; + assert(exec_freq_set); found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef)); @@ -79,6 +83,183 @@ double get_irn_exec_freq(ir_node *n) { } +/*------------------------------------------------------------------*/ +/* A algorithm that precomputes whether Conds lead to an exception. + * Computes a field for all Projs from Conds that says the following: + * - The Proj projs from a normal dual Cond with probability 50:50 + * - This Proj of the Cond leads to an exception, i.e., a raise node. + * It is taken with exception probability. + * - The Proj of the Cond avoids an exception. It is taken with + * 1 - exception probability. */ +/*------------------------------------------------------------------*/ + +#include "irouts.h" + +typedef enum { + Cond_prob_none, + Cond_prob_normal, + Cond_prob_avoid_exception, + Cond_prob_exception_taken, + Cond_prob_was_exception_taken, +} Cond_prob; + +static int just_passed_a_Raise = 0; +static ir_node *Cond_list = NULL; + +/* We do not use an extra set, as Projs are not yet in the existing one. */ +void set_ProjX_probability(ir_node *n, Cond_prob prob) { + reg_exec_freq ef; + ef.reg = n; + ef.prob = prob; + set_insert(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef)); +} + +Cond_prob get_ProjX_probability(ir_node *n) { + reg_exec_freq ef, *found; + ef.reg = n; + + found = set_find(exec_freq_set, &ef, sizeof(ef), exec_freq_hash(&ef)); + + if (found) + return (Cond_prob)found->prob; + else + return Cond_prob_none; +} + +/* A walker that only visits the nodes we want to see. */ + +static void +my_irg_walk_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env) { + int i; + set_irn_visited(node, current_ir_graph->visited); + + pre(node, env); + + if (node->op != op_Block) { + ir_node *pred; + if (node->op == op_Proj) + pred = get_irn_n(node, 0); + else + pred = get_irn_n(node, -1); + if (pred->visited < current_ir_graph->visited) + my_irg_walk_2_both(pred, pre, post, env); + } + + else { /* a Block */ + for (i = get_irn_arity(node) - 1; i >= 0; --i) { + ir_node *pred = get_irn_n(node, i); + if (pred->visited < current_ir_graph->visited) + my_irg_walk_2_both(pred, pre, post, env); + } + } + + if (node->op == op_End) { + for (i = get_irn_arity(node) - 1; i >= 0; --i) { + ir_node *pred = get_irn_n(node, i); + if ((pred->op == op_Block) && (pred->visited < current_ir_graph->visited)) + my_irg_walk_2_both(pred, pre, post, env); + } + } + + post(node, env); +} +static void my_irg_walk_current_graph(irg_walk_func *pre, irg_walk_func *post, void *env) { + inc_irg_visited(current_ir_graph); + my_irg_walk_2_both(get_irg_end(current_ir_graph), pre, post, env); +} + + +static void walk_pre(ir_node *n, void *env) { + + if (get_irn_op(n) == op_Raise) + just_passed_a_Raise = 1; + + if ( (get_irn_op(n) == op_Proj) + && (get_irn_op(get_Proj_pred(n)) == op_Cond) + && (just_passed_a_Raise)) { + ir_node *c = get_Proj_pred(n); + + /* If we already visited the other Proj, and it also leads to a Raise, + we are in the middle of something. Continue searching. */ + assert(get_irn_n_outs(c) == 2 && "encountered a switch cond"); + ir_node *other_proj = get_irn_out(c, 0); + if (other_proj == n) other_proj = get_irn_out(c, 1); + if (get_ProjX_probability(other_proj) == Cond_prob_exception_taken) { + set_ProjX_probability(other_proj, Cond_prob_was_exception_taken); + /* Keep searching for the Proj, so keep just_passed_a_Raise. */ + } else { + set_ProjX_probability(n, Cond_prob_exception_taken); + just_passed_a_Raise = 0; + } + } + + if (get_irn_op(n) == op_Cond) { + set_irn_link(n, Cond_list); + Cond_list = n; + } +} + +static void walk_post(ir_node *n, void *env) { + + if (get_irn_op(n) == op_Raise) + just_passed_a_Raise = 0; + + if ( (get_irn_op(n) == op_Proj) + && (get_irn_op(get_Proj_pred(n)) == op_Cond) + && ((get_ProjX_probability(n) == Cond_prob_exception_taken) || + (get_ProjX_probability(n) == Cond_prob_was_exception_taken) )) { + just_passed_a_Raise = 1; + } +} + +/** Precompute which Conds test for an exception. + * + * Operates on current_ir_graph. */ +void precompute_cond_evaluation(void) { + ir_node *c; + + compute_outs(current_ir_graph); + + just_passed_a_Raise = 0; + Cond_list = NULL; + my_irg_walk_current_graph(walk_pre, walk_post, NULL); + + for (c = Cond_list; c; c = get_irn_link(c)) { + assert(get_irn_n_outs(c) == 2 && "encountered a switch cond"); + ir_node *p0 = get_irn_out(c, 0); + ir_node *p1 = get_irn_out(c, 1); + + /* both are exceptions */ + if ((get_ProjX_probability(p0) == Cond_prob_exception_taken) && + (get_ProjX_probability(p1) == Cond_prob_exception_taken) ) { + assert(0 && "I tried to avoid these!"); + /* It's a */ + set_ProjX_probability(p0, Cond_prob_normal); + set_ProjX_probability(p1, Cond_prob_normal); + } + + /* p0 is exception */ + else if (get_ProjX_probability(p0) == Cond_prob_exception_taken) { + set_ProjX_probability(p1, Cond_prob_avoid_exception); + } + + /* p1 is exception */ + else if (get_ProjX_probability(p1) == Cond_prob_exception_taken) { + set_ProjX_probability(p0, Cond_prob_avoid_exception); + } + + /* none is exception */ + else { + set_ProjX_probability(p0, Cond_prob_normal); + set_ProjX_probability(p1, Cond_prob_normal); + } + } +} + +int is_fragile_Proj(ir_node *n) { + return is_Proj(n) && (get_ProjX_probability(n) == Cond_prob_exception_taken); +} + /*------------------------------------------------------------------*/ /* The algorithm to compute the execution freqencies. * @@ -94,21 +275,27 @@ static INLINE int is_loop_head(ir_node *cond) { return false; } +/** Weight a single region in edge. + * + * Given all outs of the predecessor region, we can compute the weight of + * this single edge. */ static INLINE double get_weighted_region_exec_freq(void *reg, int pos) { - void *pred_reg = get_region_in(reg, pos); - double res, full_freq = get_region_exec_freq(pred_reg); - int n_outs = get_region_n_outs (pred_reg); - int n_exc_outs = get_region_n_exc_outs(pred_reg); + void *pred_reg = get_region_in(reg, pos); + double res, full_freq = get_region_exec_freq (pred_reg); + int n_outs = get_region_n_outs (pred_reg); + int n_exc_outs = get_region_n_exc_outs(pred_reg); ir_node *cfop; if (is_ir_node(reg)) { - cfop = skip_Proj(get_Block_cfgpred((ir_node *)reg, pos)); + cfop = get_Block_cfgpred((ir_node *)reg, pos); + if (is_Proj(cfop) && (get_irn_op(get_Proj_pred(cfop)) != op_Cond)) + cfop = skip_Proj(cfop); } else { assert(is_ir_loop(reg)); cfop = get_loop_cfop(reg, pos); } - if (is_fragile_op(cfop)) { + if (is_fragile_op(cfop) || is_fragile_Proj(cfop)) { res = full_freq * exception_prob; } else { @@ -183,6 +370,7 @@ void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_prob = exception_probability; if (!exec_freq_set) exec_freq_set = new_set(exec_freq_cmp, 256); + precompute_cond_evaluation(); construct_intervals(current_ir_graph); compute_frequency(default_loop_weight); diff --git a/ir/ana/execution_frequency.h b/ir/ana/execution_frequency.h index 5d88e37e6..d20b433d0 100644 --- a/ir/ana/execution_frequency.h +++ b/ir/ana/execution_frequency.h @@ -22,26 +22,41 @@ * We assume the start block of a procedure is executed once. Based on this we * compute the execution freqency of all blocks. * - * + * The computation of the freqencies depends on the count of exception control + * flow computed during the interval analysis. The interval analysis again + * depends on stuff computed here. */ #include "irnode.h" #include "irgraph.h" +/* A proj from a Cond that goes to an exception handler. */ +int is_fragile_Proj(ir_node *n); /** Returns the number of times the block/region is executed according to - * our estimate. */ -double get_irn_exec_freq(ir_node *n); + * our estimate. Gives a number relative to the Start node of the procedure + * the block is in, which is weighted with 1. */ +double get_irn_exec_freq (ir_node *n); double get_Block_exec_freq (ir_node *b); double get_region_exec_freq(void *reg); /** Compute the execution frequency for all blocks in the given * graph. * - * @param irg The graph to be analyzed. - * @param default_loop_weight The default number of executions of a loop. + * @param irg The graph to be analyzed. + * @param default_loop_weight The default number of executions of a loop. + * @param exception_probability The probability that a fragile operation causes an exception. + * + * Uses link field. */ void compute_execution_frequency(ir_graph *irg, int default_loop_weight, double exception_probability); + +/** Compute the execution frequency for all graphs. + * + * @param default_loop_weight The default number of executions of a loop. + * @param exception_probability The probability that a fragile operation causes an exception. + * + */ void compute_execution_frequencies(int default_loop_weight, double exception_probability); /** Free occupied memory, reset. */ diff --git a/ir/ana/field_temperature.c b/ir/ana/field_temperature.c index 53d526bf2..86ab93cb1 100644 --- a/ir/ana/field_temperature.c +++ b/ir/ana/field_temperature.c @@ -68,6 +68,7 @@ int get_irn_recursion_depth(ir_node *n) { } +/** @@@ the second version of the heuristic. */ int get_weighted_loop_depth(ir_node *n) { int loop_call_depth = get_irn_loop_call_depth(n); int loop_depth = get_irn_loop_depth(n); @@ -86,12 +87,14 @@ static int default_recursion_weight = 5; /* The final evaluation of a node. In this function we can adapt the heuristic. Combine execution freqency with - recursion depth. */ + recursion depth. + @@@ the second version of the heuristic. */ double get_irn_final_cost(ir_node *n) { - double cost_loop = get_irn_exec_freq(n); - int rec_depth = get_irn_recursion_depth(n); - double cost_rec = pow(default_recursion_weight, rec_depth); - return cost_loop + cost_rec; + double cost_loop = get_irn_exec_freq(n); + double cost_method = get_irg_method_execution_frequency(get_irn_irg(n)); + int rec_depth = get_irn_recursion_depth(n); + double cost_rec = pow(default_recursion_weight, rec_depth); + return cost_loop*(cost_method + cost_rec); } double get_type_estimated_n_instances(type *tp) { diff --git a/ir/ana/interval_analysis.c b/ir/ana/interval_analysis.c index 930e814c2..41edaa04a 100644 --- a/ir/ana/interval_analysis.c +++ b/ir/ana/interval_analysis.c @@ -1,3 +1,4 @@ + #ifdef HAVE_CONFIG_H #include "config.h" #endif @@ -7,7 +8,7 @@ #endif #include "interval_analysis.h" - +#include "execution_frequency.h" #include "firm_common_t.h" #include "set.h" #include "array.h" @@ -71,7 +72,7 @@ int get_region_n_ins(void *region) { void *get_region_in(void *region, int pos) { assert(0 <= pos && pos < get_region_n_ins(region)); - return (get_region_attr(region)->in_array)[pos]; + return ((get_region_attr(region)->in_array)[pos]); } void add_region_in (void *region, void *in) { @@ -93,7 +94,7 @@ void inc_region_n_exc_outs(void *region) { void *get_loop_cfop(void *region, int pos) { assert(0 <= pos && pos < get_region_n_ins(region)); - return (get_region_attr(region)->op_array)[pos]; + return ((get_region_attr(region)->op_array)[pos]); } void add_loop_cfop (void *region, void *cfop) { @@ -102,7 +103,8 @@ void add_loop_cfop (void *region, void *cfop) { } static INLINE void exc_outs(void *reg, ir_node *cfop) { - if (is_fragile_op(cfop)) inc_region_n_exc_outs(reg); + if (is_fragile_op(cfop) || (is_fragile_Proj(cfop))) + inc_region_n_exc_outs(reg); } /*------------------------------------------------------------------*/ @@ -235,8 +237,16 @@ static void construct_interval_block(ir_node *b, ir_loop *l) { continue; } - cfop = skip_Proj(get_Block_cfgpred(b, i)); - pred = get_nodes_block(cfop); + cfop = get_Block_cfgpred(b, i); + if (is_Proj(cfop)) { + if (get_irn_op(get_Proj_pred(cfop)) != op_Cond) { + cfop = skip_Proj(cfop); + } else { + assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop))); + } + } + + pred = skip_Proj(get_nodes_block(cfop)); /* We want nice blocks. */ assert( get_irn_op(pred) != op_Bad && get_irn_op(skip_Proj(get_Block_cfgpred(b, i))) != op_Bad); diff --git a/ir/ana/interval_analysis.h b/ir/ana/interval_analysis.h index 1562e5e44..bac1a9c4b 100644 --- a/ir/ana/interval_analysis.h +++ b/ir/ana/interval_analysis.h @@ -17,13 +17,14 @@ * * @author Goetz Lindenmaier * - * The analysis is based on the control flow looptree. An intervall are basically - * all nodes in a single ir_loop entry, i.e., basic blocks and inner loop nodes. - * The analysis computes a new set of edges that link all nodes of a loop to an - * acyclic graph. - * - * + * The analysis is based on the control flow looptree. An intervall + * are basically all nodes in a single ir_loop entry, i.e., basic + * blocks and inner loop nodes. The analysis computes a new set of + * edges that link all nodes of a loop to an acyclic graph. * + * The interval analysis counts the number of exception control flow + * operations leaving a block. This depends on stuff computed in + * execution_freqencies. */ #ifndef _INTERVAL_ANALYSIS_H_ @@ -47,6 +48,11 @@ void add_region_in (void *region, void *in); * This number is useful for evaluation of execution frequencies. */ int get_region_n_outs(void *region); + +/** The number of exception out edges of a region. + * + * This number is useful for evaluation of execution frequencies. + */ int get_region_n_exc_outs(void *region); /** The control flow operation corresponding to the loop-region in at diff --git a/ir/ana/irloop.h b/ir/ana/irloop.h index ce552013c..f84547dc7 100644 --- a/ir/ana/irloop.h +++ b/ir/ana/irloop.h @@ -126,7 +126,17 @@ void *get_loop_link (const ir_loop *loop); /* ------------------------------------------------------------------- */ /** Constructs backedge information for irg in intraprocedural view. - * @returns Maximal depth of loop tree. */ + * @returns Maximal depth of loop tree. + * + * ATTENTION: + * One assumes, the Phi nodes in a block with a backedge have backedges + * at the same positions as the block. This is not the case, as + * the scc algorithms does not respect the program semantics in this case. + * Take a swap in a loop (t = i; i = j; j = t;) This results in two Phi + * nodes. They form a cycle. Once the scc algorithm deleted one of the + * edges, the cycle is removed. The second Phi node does not get a + * backedge! + */ /* @@@ Well, maybe construct_loop_information or analyze_loops ? */ int construct_backedges(ir_graph *irg); -- 2.20.1