2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Primitive list scheduling with different node selectors.
9 * @author Sebastian Hack
26 #include "iredges_t.h"
40 #include "belistsched.h"
45 #include "lc_opts_enum.h"
47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
50 * Scheduling environment for the whole graph.
52 typedef struct sched_env_t {
53 unsigned *scheduled; /**< bitset of already scheduled nodes */
54 const list_sched_selector_t *selector; /**< The node selector. */
55 void *selector_env; /**< A pointer to give to the selector. */
59 * Environment for a block scheduler.
61 typedef struct block_sched_env_t {
62 /** scheduling info per node, copied from the global scheduler object */
64 /** the set of candidates */
66 ir_node *block; /**< the current block */
67 sched_env_t *sched_env; /**< the scheduler environment */
68 const list_sched_selector_t *selector;
69 void *selector_block_env;
73 * Returns non-zero if the node is already scheduled
75 static bool is_already_scheduled(const sched_env_t *env, ir_node *n)
77 unsigned idx = get_irn_idx(n);
78 return rbitset_is_set(env->scheduled, idx);
82 * Mark a node as already scheduled
84 static void set_already_scheduled(sched_env_t *env, ir_node *n)
86 unsigned idx = get_irn_idx(n);
87 rbitset_set(env->scheduled, idx);
90 static void selected(block_sched_env_t *env, ir_node *irn);
91 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
94 * Put a node in the ready set, or make it available immediately if it doesn't
95 * need to be scheduled
97 static void node_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
100 || (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled)) {
102 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
103 } else if (be_is_Keep(irn) || be_is_CopyKeep(irn)) {
104 /* Keeps must be scheduled immediately */
105 add_to_sched(env, irn);
107 ir_nodeset_insert(&env->cands, irn);
109 /* Notify selector about the ready node. */
110 if (env->selector->node_ready)
111 env->selector->node_ready(env->selector_block_env, irn, pred);
113 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
118 * Try to put a node in the ready set.
119 * @param env The block scheduler environment.
120 * @param pred The previous scheduled node.
121 * @param irn The node to make ready.
122 * @return 1, if the node could be made ready, 0 else.
124 static void try_make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
128 /* we schedule one block at a time, so no need to consider users in other
130 if (is_Block(irn) || get_nodes_block(irn) != env->block)
132 if (is_Phi(irn) || is_End(irn))
134 /* check if all operands are already available */
135 n = get_irn_ins_or_deps(irn);
136 for (i = 0; i < n; ++i) {
137 ir_node *op = get_irn_in_or_dep(irn, i);
139 /* If the operand is local to the scheduled block and not yet
140 * scheduled, this nodes cannot be made ready, so exit. */
141 if (get_nodes_block(op) == env->block
142 && !is_already_scheduled(env->sched_env, op))
146 node_ready(env, pred, irn);
149 static void selected(block_sched_env_t *env, ir_node *node)
151 /* notify the selector about the finally selected node. */
152 if (env->selector->node_selected)
153 env->selector->node_selected(env->selector_block_env, node);
155 /* Insert the node in the set of all available scheduled nodes. */
156 set_already_scheduled(env->sched_env, node);
158 /* check users, they might be ready now */
159 foreach_out_edge(node, edge) {
160 ir_node *user = get_edge_src_irn(edge);
161 try_make_ready(env, node, user);
163 foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) {
164 ir_node *user = get_edge_src_irn(edge);
165 try_make_ready(env, node, user);
170 * Append an instruction to a schedule.
171 * @param env The block scheduling environment.
172 * @param irn The node to add to the schedule.
173 * @return The given node.
175 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
177 assert(! (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled));
179 sched_add_before(env->block, irn);
181 DB((dbg, LEVEL_2, "\tschedule %+F\n", irn));
183 /* Remove the node from the ready set */
184 ir_nodeset_remove(&env->cands, irn);
190 * Perform list scheduling on a block.
192 * Note, that the caller must compute a linked list of nodes in the block
193 * using the link field before calling this function.
195 * Also the outs must have been computed.
197 * @param block The block node.
198 * @param env Scheduling environment.
200 static void list_sched_block(ir_node *block, void *env_ptr)
202 sched_env_t *env = (sched_env_t*)env_ptr;
203 const list_sched_selector_t *selector = env->selector;
205 block_sched_env_t be;
206 ir_nodeset_t *cands = &be.cands;
208 /* Initialize the block's list head that will hold the schedule. */
209 sched_init_block(block);
211 /* Initialize the block scheduling environment */
213 be.selector = selector;
215 ir_nodeset_init_size(cands, get_irn_n_edges(block));
217 DB((dbg, LEVEL_1, "scheduling %+F\n", block));
219 if (selector->init_block)
220 be.selector_block_env = selector->init_block(env->selector_env, block);
222 /* Then one can add all nodes are ready to the set. */
223 foreach_out_edge(block, edge) {
224 ir_node *irn = get_edge_src_irn(edge);
227 /* Phi functions are scheduled immediately, since they only
228 * transfer data flow from the predecessors to this block. */
229 add_to_sched(&be, irn);
230 } else if (be_is_Start(irn)) {
231 /* The start block will be scheduled as the first node */
232 add_to_sched(&be, irn);
234 try_make_ready(&be, NULL, irn);
238 /* Iterate over all remaining nodes */
239 while (ir_nodeset_size(cands) > 0) {
240 ir_node *irn = be.selector->select(be.selector_block_env, cands);
241 DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
243 /* remove the scheduled node from the ready list. */
244 ir_nodeset_remove(cands, irn);
245 /* Add the node to the schedule. */
246 add_to_sched(&be, irn);
249 ir_nodeset_destroy(cands);
251 if (selector->finish_block)
252 selector->finish_block(be.selector_block_env);
255 /* List schedule a graph. */
256 void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector)
261 /* Matze: This is very slow, we should avoid it to improve backend speed,
262 * we just have to make sure that we have no dangling out-edges at this
265 edges_deactivate(irg);
268 num_nodes = get_irg_last_idx(irg);
270 /* initialize environment for list scheduler */
271 memset(&env, 0, sizeof(env));
272 env.selector = selector;
273 env.scheduled = rbitset_malloc(num_nodes);
275 if (selector->init_graph != NULL)
276 env.selector_env = selector->init_graph(irg);
278 /* Schedule each single block. */
279 irg_block_walk_graph(irg, list_sched_block, NULL, &env);
281 if (selector->finish_graph != NULL)
282 selector->finish_graph(env.selector_env);
287 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched)
288 void be_init_listsched(void)
290 FIRM_DBG_REGISTER(dbg, "firm.be.sched");