2 * Copyright (C) 1995-2008 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 Primitive list scheduling with different node selectors.
23 * @author Sebastian Hack
42 #include "iredges_t.h"
47 #include "irprintf_t.h"
56 #include "belistsched.h"
62 #include "lc_opts_enum.h"
64 /* we have prolog, "normal" and epilog */
65 #define N_PRIORITY_CLASSES 3
67 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
70 * Scheduling environment for the whole graph.
72 typedef struct sched_env_t {
73 unsigned *scheduled; /**< bitset of already scheduled nodes */
74 const list_sched_selector_t *selector; /**< The node selector. */
75 void *selector_env; /**< A pointer to give to the selector. */
79 * Environment for a block scheduler.
81 typedef struct block_sched_env_t {
82 /** scheduling info per node, copied from the global scheduler object */
84 /** the set of candidates */
85 ir_nodeset_t cands[N_PRIORITY_CLASSES];
86 ir_node *block; /**< the current block */
87 sched_env_t *sched_env; /**< the scheduler environment */
88 const list_sched_selector_t *selector;
89 void *selector_block_env;
93 * map prolog/normal/epilog into 3 priority levels
95 static unsigned get_priority(const ir_node *node)
97 arch_irn_flags_t flags = arch_irn_get_flags(node);
98 if (flags & arch_irn_flags_prolog) {
99 assert(! (flags & arch_irn_flags_epilog));
101 } else if (flags & arch_irn_flags_epilog) {
108 * Returns non-zero if the node is already scheduled
110 static bool is_already_scheduled(const sched_env_t *env, ir_node *n)
112 unsigned idx = get_irn_idx(n);
113 return rbitset_is_set(env->scheduled, idx);
117 * Mark a node as already scheduled
119 static void set_already_scheduled(sched_env_t *env, ir_node *n)
121 unsigned idx = get_irn_idx(n);
122 rbitset_set(env->scheduled, idx);
125 static void selected(block_sched_env_t *env, ir_node *irn);
126 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
129 * Put a node in the ready set, or make it available immediately if it doesn't
130 * need to be scheduled
132 static void node_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
135 || (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled)) {
137 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
138 } else if (be_is_Keep(irn) || be_is_CopyKeep(irn)) {
139 /* Keeps must be scheduled immediately */
140 add_to_sched(env, irn);
142 unsigned priority = get_priority(irn);
143 ir_nodeset_insert(&env->cands[priority], irn);
145 /* Notify selector about the ready node. */
146 if (env->selector->node_ready)
147 env->selector->node_ready(env->selector_block_env, irn, pred);
149 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
154 * Try to put a node in the ready set.
155 * @param env The block scheduler environment.
156 * @param pred The previous scheduled node.
157 * @param irn The node to make ready.
158 * @return 1, if the node could be made ready, 0 else.
160 static void try_make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
164 /* we schedule one block at a time, so no need to consider users in other
166 if (is_Block(irn) || get_nodes_block(irn) != env->block)
168 if (is_Phi(irn) || is_End(irn))
170 /* check if all operands are already available */
171 n = get_irn_ins_or_deps(irn);
172 for (i = 0; i < n; ++i) {
173 ir_node *op = get_irn_in_or_dep(irn, i);
175 /* If the operand is local to the scheduled block and not yet
176 * scheduled, this nodes cannot be made ready, so exit. */
177 if (get_nodes_block(op) == env->block
178 && !is_already_scheduled(env->sched_env, op))
182 node_ready(env, pred, irn);
185 static void selected(block_sched_env_t *env, ir_node *node)
187 const ir_edge_t *edge;
189 /* notify the selector about the finally selected node. */
190 if (env->selector->node_selected)
191 env->selector->node_selected(env->selector_block_env, node);
193 /* Insert the node in the set of all available scheduled nodes. */
194 set_already_scheduled(env->sched_env, node);
196 /* check users, they might be ready now */
197 foreach_out_edge(node, edge) {
198 ir_node *user = get_edge_src_irn(edge);
199 try_make_ready(env, node, user);
201 foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) {
202 ir_node *user = get_edge_src_irn(edge);
203 try_make_ready(env, node, user);
208 * Append an instruction to a schedule.
209 * @param env The block scheduling environment.
210 * @param irn The node to add to the schedule.
211 * @return The given node.
213 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
215 unsigned priority = get_priority(irn);
217 assert(! (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled));
219 sched_add_before(env->block, irn);
221 DB((dbg, LEVEL_2, "\tschedule %+F\n", irn));
223 /* Remove the node from the ready set */
224 ir_nodeset_remove(&env->cands[priority], irn);
230 * Perform list scheduling on a block.
232 * Note, that the caller must compute a linked list of nodes in the block
233 * using the link field before calling this function.
235 * Also the outs must have been computed.
237 * @param block The block node.
238 * @param env Scheduling environment.
240 static void list_sched_block(ir_node *block, void *env_ptr)
242 sched_env_t *env = (sched_env_t*)env_ptr;
243 const list_sched_selector_t *selector = env->selector;
245 block_sched_env_t be;
246 const ir_edge_t *edge;
249 /* Initialize the block's list head that will hold the schedule. */
250 sched_init_block(block);
252 /* Initialize the block scheduling environment */
254 be.selector = selector;
256 for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
257 ir_nodeset_init_size(&be.cands[p], get_irn_n_edges(block));
260 DB((dbg, LEVEL_1, "scheduling %+F\n", block));
262 if (selector->init_block)
263 be.selector_block_env = selector->init_block(env->selector_env, block);
265 /* Then one can add all nodes are ready to the set. */
266 foreach_out_edge(block, edge) {
267 ir_node *irn = get_edge_src_irn(edge);
270 /* Phi functions are scheduled immediately, since they only
271 * transfer data flow from the predecessors to this block. */
272 add_to_sched(&be, irn);
273 } else if (be_is_Start(irn)) {
274 /* The start block will be scheduled as the first node */
275 add_to_sched(&be, irn);
277 try_make_ready(&be, NULL, irn);
281 /* Iterate over all remaining nodes */
282 for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
283 ir_nodeset_t *p_cands = &be.cands[p];
284 while (ir_nodeset_size(p_cands) > 0) {
285 ir_node *irn = be.selector->select(be.selector_block_env, p_cands);
286 DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
288 /* remove the scheduled node from the ready list. */
289 ir_nodeset_remove(p_cands, irn);
290 /* Add the node to the schedule. */
291 add_to_sched(&be, irn);
295 if (selector->finish_block)
296 selector->finish_block(be.selector_block_env);
298 for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
299 /** all cand lists should be empty. Otherwise there was some invalid
300 * dependencies between priority classes (ie. priority 0 value depending
301 * on a priority 1 value) */
302 assert(ir_nodeset_size(&be.cands[p]) == 0);
303 ir_nodeset_init_size(&be.cands[p], get_irn_n_edges(block));
307 /* List schedule a graph. */
308 void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector)
313 /* Matze: This is very slow, we should avoid it to improve backend speed,
314 * we just have to make sure that we have no dangling out-edges at this
317 edges_deactivate(irg);
320 num_nodes = get_irg_last_idx(irg);
322 /* initialize environment for list scheduler */
323 memset(&env, 0, sizeof(env));
324 env.selector = selector;
325 env.scheduled = rbitset_malloc(num_nodes);
327 if (selector->init_graph != NULL)
328 env.selector_env = selector->init_graph(irg);
330 /* Schedule each single block. */
331 irg_block_walk_graph(irg, list_sched_block, NULL, &env);
333 if (selector->finish_graph != NULL)
334 selector->finish_graph(env.selector_env);
339 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched);
340 void be_init_listsched(void)
342 FIRM_DBG_REGISTER(dbg, "firm.be.sched");