2 * Copyright (C) 1995-2007 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 Regpressure node selector.
23 * @author Sebastian Hack
33 #include "iredges_t.h"
36 #include "besched_t.h"
37 #include "belistsched.h"
41 typedef struct _usage_stats_t {
43 struct _usage_stats_t *next;
45 int uses_in_block; /**< Number of uses inside the current block. */
46 int already_consumed; /**< Number of insns using this value already
51 const list_sched_selector_t *vtab;
52 const arch_env_t *arch_env;
53 } reg_pressure_main_env_t;
57 const reg_pressure_main_env_t *main_env;
59 ir_nodeset_t already_scheduled;
60 } reg_pressure_selector_env_t;
65 * Ugly global variable for the compare function
66 * since qsort(3) does not pass an extra pointer.
68 static ir_node *curr_bl = NULL;
70 static int cmp_usage(const void *a, const void *b)
72 struct trivial_sched_env *env;
77 res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
80 * One of them is live at the end of the block.
81 * Then, that one shall be scheduled at after the other
91 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
93 usage_stats_t *us = get_irn_link(irn);
96 us = obstack_alloc(&env->obst, sizeof(us[0]));
98 us->already_consumed = 0;
99 us->max_hops = INT_MAX;
100 us->next = env->root;
102 set_irn_link(irn, us);
108 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
110 usage_stats_t *us = get_irn_link(irn);
111 assert(us && "This node must have usage stats");
115 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
117 ir_node *bl = get_nodes_block(irn);
119 * If the reached node is not in the block desired,
120 * return the value passed for this situation.
122 if(get_nodes_block(irn) != bl)
123 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
126 * If the node is in the current block but not
127 * yet scheduled, we keep on searching from that node.
129 if(!ir_nodeset_contains(&env->already_scheduled, irn)) {
132 for(i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
133 ir_node *operand = get_irn_in_or_dep(irn, i);
135 if(get_irn_visited(operand) < visited_nr) {
138 set_irn_visited(operand, visited_nr);
139 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
148 * If the node is in the current block and scheduled, return
149 * the depth which indicates the number of steps to the
150 * region of scheduled nodes.
155 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
157 ir_node *bl = get_nodes_block(irn);
158 ir_graph *irg = get_irn_irg(bl);
161 const ir_edge_t *edge;
163 foreach_out_edge(irn, edge) {
164 ir_node *user = get_edge_src_irn(edge);
165 unsigned visited_nr = get_irg_visited(irg) + 1;
168 set_irg_visited(irg, visited_nr);
169 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
170 res = MAX(res, max_hops);
176 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
178 reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
180 main_env->arch_env = arch_env;
181 main_env->vtab = vtab;
182 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
187 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
191 if(sel->to_appear_in_schedule)
192 res = sel->to_appear_in_schedule(block_env, irn);
194 return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn));
197 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
200 reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0]));
202 obstack_init(&env->obst);
203 ir_nodeset_init(&env->already_scheduled);
205 env->main_env = graph_env;
208 * Collect usage statistics.
210 sched_foreach(bl, irn) {
211 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
214 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
215 //ir_node *op = get_irn_n(irn, i);
216 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
217 usage_stats_t *us = get_or_set_usage_stats(env, irn);
218 #if 0 /* Liveness is not computed here! */
219 if(is_live_end(bl, op))
220 us->uses_in_block = 99999;
232 static void reg_pressure_block_free(void *block_env)
234 reg_pressure_selector_env_t *env = block_env;
237 for(us = env->root; us; us = us->next)
238 set_irn_link(us->irn, NULL);
240 obstack_free(&env->obst, NULL);
241 ir_nodeset_destroy(&env->already_scheduled);
245 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
248 if(get_irn_mode(irn) == mode_T) {
249 const ir_edge_t *edge;
251 foreach_out_edge(irn, edge)
252 res += get_result_hops_sum(env, get_edge_src_irn(edge));
255 else if(mode_is_data(get_irn_mode(irn)))
256 res = compute_max_hops(env, irn);
262 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
267 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
268 ir_node *op = get_irn_n(irn, i);
270 if(must_appear_in_schedule(env->main_env->vtab, env, op))
271 sum += compute_max_hops(env, op);
274 sum += get_result_hops_sum(env, irn);
279 static ir_node *reg_pressure_select(void *block_env, ir_nodeset_t *ready_set,
280 ir_nodeset_t *live_set)
282 ir_nodeset_iterator_t iter;
283 reg_pressure_selector_env_t *env = block_env;
284 ir_node *irn, *res = NULL;
285 int curr_cost = INT_MAX;
287 assert(ir_nodeset_size(ready_set) > 0);
289 ir_nodeset_iterator_init(&iter, ready_set);
290 while( (irn = ir_nodeset_iterator_next(&iter)) != NULL) {
292 Ignore branch instructions for the time being.
293 They should only be scheduled if there is nothing else.
295 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
296 int costs = reg_pr_costs(env, irn);
297 if (costs <= curr_cost) {
305 There was no result so we only saw a branch.
310 ir_nodeset_iterator_init(&iter, ready_set);
311 res = ir_nodeset_iterator_next(&iter);
313 assert(res && "There must be a node scheduled.");
316 ir_nodeset_insert(&env->already_scheduled, res);
320 static const list_sched_selector_t reg_pressure_selector_struct = {
321 reg_pressure_graph_init,
322 reg_pressure_block_init,
324 NULL, /* to_appear_in_schedule */
325 NULL, /* node_ready */
326 NULL, /* node_selected */
329 reg_pressure_block_free,
333 const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct;