2 * Regpressure node selector.
3 * Originally implemented by Sebastian Hack.
4 * @author Christian Wuerdig
14 #include "iredges_t.h"
17 #include "besched_t.h"
18 #include "belistsched.h"
22 typedef struct _usage_stats_t {
24 struct _usage_stats_t *next;
26 int uses_in_block; /**< Number of uses inside the current block. */
27 int already_consumed; /**< Number of insns using this value already
32 const list_sched_selector_t *vtab;
33 const arch_env_t *arch_env;
34 } reg_pressure_main_env_t;
38 const reg_pressure_main_env_t *main_env;
40 nodeset *already_scheduled;
41 } reg_pressure_selector_env_t;
46 * Ugly global variable for the compare function
47 * since qsort(3) does not pass an extra pointer.
49 static ir_node *curr_bl = NULL;
51 static int cmp_usage(const void *a, const void *b)
53 struct trivial_sched_env *env;
58 res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
61 * One of them is live at the end of the block.
62 * Then, that one shall be scheduled at after the other
72 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
74 usage_stats_t *us = get_irn_link(irn);
77 us = obstack_alloc(&env->obst, sizeof(us[0]));
79 us->already_consumed = 0;
80 us->max_hops = INT_MAX;
83 set_irn_link(irn, us);
89 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
91 usage_stats_t *us = get_irn_link(irn);
92 assert(us && "This node must have usage stats");
96 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
98 ir_node *bl = get_nodes_block(irn);
100 * If the reached node is not in the block desired,
101 * return the value passed for this situation.
103 if(get_nodes_block(irn) != bl)
104 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
107 * If the node is in the current block but not
108 * yet scheduled, we keep on searching from that node.
110 if(!nodeset_find(env->already_scheduled, irn)) {
113 for(i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
114 ir_node *operand = get_irn_in_or_dep(irn, i);
116 if(get_irn_visited(operand) < visited_nr) {
119 set_irn_visited(operand, visited_nr);
120 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
129 * If the node is in the current block and scheduled, return
130 * the depth which indicates the number of steps to the
131 * region of scheduled nodes.
136 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
138 ir_node *bl = get_nodes_block(irn);
139 ir_graph *irg = get_irn_irg(bl);
142 const ir_edge_t *edge;
144 foreach_out_edge(irn, edge) {
145 ir_node *user = get_edge_src_irn(edge);
146 unsigned visited_nr = get_irg_visited(irg) + 1;
149 set_irg_visited(irg, visited_nr);
150 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
151 res = MAX(res, max_hops);
157 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
159 reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
161 main_env->arch_env = arch_env;
162 main_env->vtab = vtab;
163 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
168 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
172 if(sel->to_appear_in_schedule)
173 res = sel->to_appear_in_schedule(block_env, irn);
175 return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn));
178 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
181 reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0]));
183 obstack_init(&env->obst);
184 env->already_scheduled = new_nodeset(32);
186 env->main_env = graph_env;
189 * Collect usage statistics.
191 sched_foreach(bl, irn) {
192 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
195 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
196 //ir_node *op = get_irn_n(irn, i);
197 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
198 usage_stats_t *us = get_or_set_usage_stats(env, irn);
199 #if 0 /* Liveness is not computed here! */
200 if(is_live_end(bl, op))
201 us->uses_in_block = 99999;
213 static void reg_pressure_block_free(void *block_env)
215 reg_pressure_selector_env_t *env = block_env;
218 for(us = env->root; us; us = us->next)
219 set_irn_link(us->irn, NULL);
221 obstack_free(&env->obst, NULL);
222 del_nodeset(env->already_scheduled);
226 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
229 if(get_irn_mode(irn) == mode_T) {
230 const ir_edge_t *edge;
232 foreach_out_edge(irn, edge)
233 res += get_result_hops_sum(env, get_edge_src_irn(edge));
236 else if(mode_is_data(get_irn_mode(irn)))
237 res = compute_max_hops(env, irn);
243 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
248 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
249 ir_node *op = get_irn_n(irn, i);
251 if(must_appear_in_schedule(env->main_env->vtab, env, op))
252 sum += compute_max_hops(env, op);
255 sum += get_result_hops_sum(env, irn);
260 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set, nodeset *live_set)
262 reg_pressure_selector_env_t *env = block_env;
263 ir_node *irn, *res = NULL;
264 int curr_cost = INT_MAX;
266 assert(nodeset_count(ready_set) > 0);
268 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
270 Ignore branch instructions for the time being.
271 They should only be scheduled if there is nothing else.
273 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
274 int costs = reg_pr_costs(env, irn);
275 if (costs <= curr_cost) {
283 There was no result so we only saw a branch.
288 res = nodeset_first(ready_set);
289 nodeset_break(ready_set);
291 assert(res && "There must be a node scheduled.");
294 nodeset_insert(env->already_scheduled, res);
298 static const list_sched_selector_t reg_pressure_selector_struct = {
299 reg_pressure_graph_init,
300 reg_pressure_block_init,
302 NULL, /* to_appear_in_schedule */
303 NULL, /* node_ready */
304 NULL, /* node_selected */
307 reg_pressure_block_free,
311 const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct;