X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschedtrace.c;h=7362abba2b0d7e4ef82be064c05b584d5abd94dd;hb=d0d5cc041a1bdc5a62aab757dbf7d3069796c63a;hp=8ccfdebbd3025aec9aae2e0a4a62b0090e8cf121;hpb=2adf84106c02caf097c2d6cf1764706bdc437bcc;p=libfirm diff --git a/ir/be/beschedtrace.c b/ir/be/beschedtrace.c index 8ccfdebbd..7362abba2 100644 --- a/ir/be/beschedtrace.c +++ b/ir/be/beschedtrace.c @@ -1,21 +1,39 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** - * Implements a trace scheduler as presented in Muchnik[TM]. - * Originally implemented by Michael Beck. - * @author Christian Wuerdig - * @date 28.08.2006 - * @cvs-id $Id$ + * @file + * @brief Implements a trace scheduler as presented in Muchnik[TM]. + * @author Michael Beck + * @date 28.08.2006 + * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include #include "iredges_t.h" -#include "besched_t.h" +#include "besched.h" #include "belistsched.h" -#include "benode_t.h" +#include "benode.h" +#include "belive.h" /* we need a special mark */ static char _mark; @@ -33,7 +51,6 @@ typedef struct _trace_irn { typedef struct _trace_env { trace_irn_t *sched_info; /**< trace scheduling information about the nodes */ - const arch_env_t *arch_env; /**< the arch environment */ sched_timestep_t curr_time; /**< current time of the scheduler */ void *selector_env; /**< the backend selector environment */ const list_sched_selector_t *selector; /**< the actual backend selector */ @@ -55,7 +72,7 @@ static ir_node *get_nodeset_node(const ir_nodeset_t *nodeset) /** * Returns non-zero if the node is a root node */ -static INLINE unsigned is_root_node(trace_env_t *env, ir_node *n) +static inline unsigned is_root_node(trace_env_t *env, ir_node *n) { int idx = get_irn_idx(n); @@ -66,7 +83,7 @@ static INLINE unsigned is_root_node(trace_env_t *env, ir_node *n) /** * Mark a node as root node */ -static INLINE void mark_root_node(trace_env_t *env, ir_node *n) +static inline void mark_root_node(trace_env_t *env, ir_node *n) { int idx = get_irn_idx(n); @@ -77,7 +94,8 @@ static INLINE void mark_root_node(trace_env_t *env, ir_node *n) /** * Get the current delay. */ -static INLINE sched_timestep_t get_irn_delay(trace_env_t *env, ir_node *n) { +static inline sched_timestep_t get_irn_delay(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -87,7 +105,8 @@ static INLINE sched_timestep_t get_irn_delay(trace_env_t *env, ir_node *n) { /** * Set the current delay. */ -static INLINE void set_irn_delay(trace_env_t *env, ir_node *n, sched_timestep_t delay) { +static inline void set_irn_delay(trace_env_t *env, ir_node *n, sched_timestep_t delay) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -97,7 +116,8 @@ static INLINE void set_irn_delay(trace_env_t *env, ir_node *n, sched_timestep_t /** * Get the current etime. */ -static INLINE sched_timestep_t get_irn_etime(trace_env_t *env, ir_node *n) { +static inline sched_timestep_t get_irn_etime(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -107,7 +127,8 @@ static INLINE sched_timestep_t get_irn_etime(trace_env_t *env, ir_node *n) { /** * Set the current etime. */ -static INLINE void set_irn_etime(trace_env_t *env, ir_node *n, sched_timestep_t etime) { +static inline void set_irn_etime(trace_env_t *env, ir_node *n, sched_timestep_t etime) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -117,7 +138,8 @@ static INLINE void set_irn_etime(trace_env_t *env, ir_node *n, sched_timestep_t /** * Get the number of users. */ -static INLINE unsigned get_irn_num_user(trace_env_t *env, ir_node *n) { +static inline unsigned get_irn_num_user(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -127,7 +149,8 @@ static INLINE unsigned get_irn_num_user(trace_env_t *env, ir_node *n) { /** * Set the number of users. */ -static INLINE void set_irn_num_user(trace_env_t *env, ir_node *n, unsigned num_user) { +static inline void set_irn_num_user(trace_env_t *env, ir_node *n, unsigned num_user) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -137,7 +160,8 @@ static INLINE void set_irn_num_user(trace_env_t *env, ir_node *n, unsigned num_u /** * Get the register difference. */ -static INLINE int get_irn_reg_diff(trace_env_t *env, ir_node *n) { +static inline int get_irn_reg_diff(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -147,7 +171,8 @@ static INLINE int get_irn_reg_diff(trace_env_t *env, ir_node *n) { /** * Set the register difference. */ -static INLINE void set_irn_reg_diff(trace_env_t *env, ir_node *n, int reg_diff) { +static inline void set_irn_reg_diff(trace_env_t *env, ir_node *n, int reg_diff) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -157,7 +182,8 @@ static INLINE void set_irn_reg_diff(trace_env_t *env, ir_node *n, int reg_diff) /** * Get the pre-order position. */ -static INLINE int get_irn_preorder(trace_env_t *env, ir_node *n) { +static inline int get_irn_preorder(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -167,7 +193,8 @@ static INLINE int get_irn_preorder(trace_env_t *env, ir_node *n) { /** * Set the pre-order position. */ -static INLINE void set_irn_preorder(trace_env_t *env, ir_node *n, int pos) { +static inline void set_irn_preorder(trace_env_t *env, ir_node *n, int pos) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -177,7 +204,8 @@ static INLINE void set_irn_preorder(trace_env_t *env, ir_node *n, int pos) { /** * Get the pre-order position. */ -static INLINE unsigned get_irn_critical_path_len(trace_env_t *env, ir_node *n) { +static inline unsigned get_irn_critical_path_len(trace_env_t *env, ir_node *n) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -187,7 +215,8 @@ static INLINE unsigned get_irn_critical_path_len(trace_env_t *env, ir_node *n) { /** * Set the pre-order position. */ -static INLINE void set_irn_critical_path_len(trace_env_t *env, ir_node *n, unsigned len) { +static inline void set_irn_critical_path_len(trace_env_t *env, ir_node *n, unsigned len) +{ int idx = get_irn_idx(n); assert(idx < ARR_LEN(env->sched_info)); @@ -197,7 +226,8 @@ static INLINE void set_irn_critical_path_len(trace_env_t *env, ir_node *n, unsig /** * returns the exec-time for node n. */ -static sched_timestep_t exectime(trace_env_t *env, ir_node *n) { +static sched_timestep_t exectime(trace_env_t *env, ir_node *n) +{ if (be_is_Keep(n) || is_Proj(n)) return 0; if (env->selector->exectime) @@ -208,7 +238,8 @@ static sched_timestep_t exectime(trace_env_t *env, ir_node *n) { /** * Calculates the latency for between two ops */ -static sched_timestep_t latency(trace_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) { +static sched_timestep_t latency(trace_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) +{ /* a Keep hides a root */ if (be_is_Keep(curr)) return exectime(env, pred); @@ -229,7 +260,8 @@ static sched_timestep_t latency(trace_env_t *env, ir_node *pred, int pred_cycle, /** * Returns the number of users of a node having mode datab. */ -static int get_num_successors(ir_node *irn) { +static int get_num_successors(ir_node *irn) +{ int sum = 0; const ir_edge_t *edge; @@ -259,14 +291,15 @@ static int get_num_successors(ir_node *irn) { /** * Returns the difference of regs_output - regs_input; */ -static int get_reg_difference(trace_env_t *env, ir_node *irn) { +static int get_reg_difference(trace_env_t *env, ir_node *irn) +{ int num_out = 0; int num_in = 0; int i; ir_node *block = get_nodes_block(irn); if (be_is_Call(irn)) { - /* we want calls prefered */ + /* we want calls preferred */ return -5; } @@ -286,10 +319,16 @@ static int get_reg_difference(trace_env_t *env, ir_node *irn) { for (i = get_irn_arity(irn) - 1; i >= 0; i--) { ir_node *in = get_irn_n(irn, i); - if (! be_is_live_end(env->liveness, block, in) && /* if the value lives outside of block: do not count */ - mode_is_datab(get_irn_mode(in)) && /* must be data node */ - ! arch_irn_is(env->arch_env, in, ignore)) /* ignore "ignore" nodes :) */ - num_in++; + if (!mode_is_datab(get_irn_mode(in))) + continue; + + if (arch_irn_is_ignore(in)) + continue; + + if (be_is_live_end(env->liveness, block, in)) + continue; + + num_in++; } return num_out - num_in; @@ -298,7 +337,8 @@ static int get_reg_difference(trace_env_t *env, ir_node *irn) { /** * descent into a dag and create a pre-order list. */ -static void descent(ir_node *root, ir_node *block, ir_node **list, trace_env_t *env, unsigned path_len) { +static void descent(ir_node *root, ir_node *block, ir_node **list, trace_env_t *env, unsigned path_len) +{ int i; if (! is_Phi(root)) { @@ -342,7 +382,8 @@ static void descent(ir_node *root, ir_node *block, ir_node **list, trace_env_t * /** * Returns non-zero if root is a root in the block block. */ -static int is_root(ir_node *root, ir_node *block) { +static int is_root(ir_node *root, ir_node *block) +{ const ir_edge_t *edge; foreach_out_edge(root, edge) { @@ -362,7 +403,8 @@ static int is_root(ir_node *root, ir_node *block) { /** * Performs initial block calculations for trace scheduling. */ -static void trace_preprocess_block(trace_env_t *env, ir_node *block) { +static void trace_preprocess_block(trace_env_t *env, ir_node *block) +{ ir_node *root = NULL, *preord = NULL; ir_node *curr, *irn; int cur_pos; @@ -372,6 +414,16 @@ static void trace_preprocess_block(trace_env_t *env, ir_node *block) { foreach_out_edge(block, edge) { ir_node *succ = get_edge_src_irn(edge); + if (is_Block(succ)) { + /* A Block-Block edge. This should be the MacroBlock + * edge, ignore it. */ + assert(get_Block_MacroBlock(succ) == block && "Block-Block edge found"); + continue; + } + if (is_Anchor(succ)) { + /* ignore a keep alive edge */ + continue; + } if (is_root(succ, block)) { mark_root_node(env, succ); set_irn_link(succ, root); @@ -396,7 +448,7 @@ static void trace_preprocess_block(trace_env_t *env, ir_node *block) { for (cur_pos = 0, curr = root; curr; curr = get_irn_link(curr), cur_pos++) { sched_timestep_t d; - if (arch_irn_class_is(env->arch_env, curr, branch)) { + if (is_cfop(curr)) { /* assure, that branches can be executed last */ d = 0; } @@ -430,7 +482,8 @@ static void trace_preprocess_block(trace_env_t *env, ir_node *block) { /** * This functions gets called after a node finally has been made ready. */ -static void trace_node_ready(void *data, ir_node *irn, ir_node *pred) { +static void trace_node_ready(void *data, ir_node *irn, ir_node *pred) +{ trace_env_t *env = data; sched_timestep_t etime_p, etime; @@ -448,9 +501,10 @@ static void trace_node_ready(void *data, ir_node *irn, ir_node *pred) { /** * Update the current time after irn has been selected. */ -static void trace_update_time(void *data, ir_node *irn) { +static void trace_update_time(void *data, ir_node *irn) +{ trace_env_t *env = data; - if (is_Phi(irn) || get_irn_opcode(irn) == iro_Start) { + if (is_Phi(irn) || get_irn_opcode(irn) == beo_Start) { env->curr_time += get_irn_etime(env, irn); } else { @@ -463,16 +517,18 @@ static void trace_update_time(void *data, ir_node *irn) { * @param birg The backend irg object * @return The environment */ -static trace_env_t *trace_init(const arch_env_t *arch_env, ir_graph *irg) { - trace_env_t *env = xcalloc(1, sizeof(*env)); +static trace_env_t *trace_init(const be_irg_t *birg) +{ + trace_env_t *env = XMALLOCZ(trace_env_t); + ir_graph *irg = be_get_birg_irg(birg); int nn = get_irg_last_idx(irg); - env->arch_env = arch_env; env->curr_time = 0; env->sched_info = NEW_ARR_F(trace_irn_t, nn); env->liveness = be_liveness(irg); FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.trace"); + be_liveness_assure_chk(env->liveness); memset(env->sched_info, 0, nn * sizeof(*(env->sched_info))); return env; @@ -482,7 +538,8 @@ static trace_env_t *trace_init(const arch_env_t *arch_env, ir_graph *irg) { * Frees all memory allocated for trace scheduling environment. * @param env The environment */ -static void trace_free(void *data) { +static void trace_free(void *data) +{ trace_env_t *env = data; be_liveness_free(env->liveness); DEL_ARR_F(env->sched_info); @@ -492,13 +549,14 @@ static void trace_free(void *data) { /** * Simple selector. Just assure that jumps are scheduled last. */ -static ir_node *basic_selection(const arch_env_t *arch_env, ir_nodeset_t *ready_set) { +static ir_node *basic_selection(ir_nodeset_t *ready_set) +{ ir_node *irn = NULL; ir_nodeset_iterator_t iter; /* assure that branches and constants are executed last */ foreach_ir_nodeset(ready_set, irn, iter) { - if (! arch_irn_class_is(arch_env, irn, branch)) { + if (!is_cfop(irn)) { return irn; } } @@ -519,6 +577,7 @@ static ir_node *muchnik_select(void *block_env, ir_nodeset_t *ready_set, ir_node ir_nodeset_iterator_t iter; sched_timestep_t max_delay = 0; ir_node *irn; + (void) live_set; /* calculate the max delay of all candidates */ foreach_ir_nodeset(ready_set, irn, iter) { @@ -549,7 +608,7 @@ static ir_node *muchnik_select(void *block_env, ir_nodeset_t *ready_set, ir_node if (cnt == 1) { irn = get_nodeset_node(&ecands); - if (arch_irn_class_is(env->arch_env, irn, branch)) { + if (is_cfop(irn)) { /* BEWARE: don't select a JUMP if others are still possible */ goto force_mcands; } @@ -557,23 +616,23 @@ static ir_node *muchnik_select(void *block_env, ir_nodeset_t *ready_set, ir_node } else if (cnt > 1) { DB((env->dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay)); - irn = basic_selection(env->arch_env, &ecands); + irn = basic_selection(&ecands); } else { force_mcands: DB((env->dbg, LEVEL_3, "\tmcand = %d\n", ir_nodeset_size(&mcands))); - irn = basic_selection(env->arch_env, &mcands); + irn = basic_selection(&mcands); } } return irn; } -static void *muchnik_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg) +static void *muchnik_init_graph(const list_sched_selector_t *vtab, const be_irg_t *birg) { - trace_env_t *env = trace_init(arch_env, irg); + trace_env_t *env = trace_init(birg); env->selector = vtab; - env->selector_env = (void*) arch_env; + env->selector_env = (void*) be_get_birg_arch_env(birg); return (void *)env; } @@ -583,7 +642,7 @@ static void *muchnik_init_block(void *graph_env, ir_node *bl) return graph_env; } -static const list_sched_selector_t muchnik_selector_struct = { +const list_sched_selector_t muchnik_selector = { muchnik_init_graph, muchnik_init_block, muchnik_select, @@ -596,8 +655,6 @@ static const list_sched_selector_t muchnik_selector_struct = { trace_free /* finish_graph */ }; -const list_sched_selector_t *muchnik_selector = &muchnik_selector_struct; - /** * Execute the heuristic function. */ @@ -627,12 +684,12 @@ static ir_node *heuristic_select(void *block_env, ir_nodeset_t *ns, ir_nodeset_t /* priority based selection, heuristic inspired by mueller diss */ foreach_ir_nodeset(ns, irn, iter) { /* make sure that branches are scheduled last */ - if (! arch_irn_class_is(trace_env->arch_env, irn, branch)) { + if (!is_cfop(irn)) { int rdiff = get_irn_reg_diff(trace_env, irn); int sign = rdiff < 0; int chg = (rdiff < 0 ? -rdiff : rdiff) << PRIO_CHG_PRESS; - //reg_fact = chg << cur_pressure; + /* reg_fact = chg << cur_pressure; */ reg_fact = chg * cur_pressure; if (reg_fact < chg) reg_fact = INT_MAX - 2; @@ -667,13 +724,13 @@ static ir_node *heuristic_select(void *block_env, ir_nodeset_t *ns, ir_nodeset_t DBG((trace_env->dbg, LEVEL_4, "heuristic selected %+F:\n", cand)); } else { - cand = basic_selection(trace_env->arch_env, ns); + cand = basic_selection(ns); } return cand; } -static const list_sched_selector_t heuristic_selector_struct = { +const list_sched_selector_t heuristic_selector = { muchnik_init_graph, muchnik_init_block, heuristic_select, @@ -685,5 +742,3 @@ static const list_sched_selector_t heuristic_selector_struct = { NULL, /* finish_block */ trace_free /* finish_graph */ }; - -const list_sched_selector_t *heuristic_selector = &heuristic_selector_struct;