2 * Scheduling algorithms.
3 * Just a simple list scheduling algorithm is here.
5 * @author Sebastian Hack
25 #include "iredges_t.h"
30 #include "irprintf_t.h"
35 #include "besched_t.h"
38 #include "belistsched.h"
39 #include "beschedmris.h"
44 * All scheduling info needed per node.
46 typedef struct _sched_irn_t {
47 sched_timestep_t delay; /**< The delay for this node if already calculated, else 0. */
48 sched_timestep_t etime; /**< The earliest time of this node. */
49 unsigned num_user; /**< The number real users (mode datab) of this node */
50 unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
51 int reg_diff; /**< The difference of num(out registers) - num(in registers) */
52 int preorder; /**< The pre-order position */
53 unsigned already_sched : 1; /**< Set if this node is already scheduled */
54 unsigned is_root : 1; /**< is a root node of a block */
58 * Scheduling environment for the whole graph.
60 typedef struct _sched_env_t {
61 sched_irn_t *sched_info; /**< scheduling info per node */
62 const list_sched_selector_t *selector; /**< The node selector. */
63 const arch_env_t *arch_env; /**< The architecture environment. */
64 const ir_graph *irg; /**< The graph to schedule. */
65 void *selector_env; /**< A pointer to give to the selector. */
66 unsigned use_heuristic : 1; /**< Use internal heuristic or backend selector */
71 * Ugly global variable for the compare function
72 * since qsort(3) does not pass an extra pointer.
74 static ir_node *curr_bl = NULL;
76 static int cmp_usage(const void *a, const void *b)
78 struct trivial_sched_env *env;
83 res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
86 * One of them is live at the end of the block.
87 * Then, that one shall be scheduled at after the other
98 * The trivial selector:
99 * Just assure that branches are executed last, otherwise select
100 * the first node ready.
102 static ir_node *trivial_select(void *block_env, nodeset *ready_set)
104 const arch_env_t *arch_env = block_env;
107 /* assure that branches and constants are executed last */
108 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
109 if (! arch_irn_class_is(arch_env, irn, branch)) {
110 nodeset_break(ready_set);
116 /* at last: schedule branches */
117 irn = nodeset_first(ready_set);
118 nodeset_break(ready_set);
123 static void *trivial_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
125 return (void *) arch_env;
128 static void *trivial_init_block(void *graph_env, ir_node *bl)
133 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
137 if(sel->to_appear_in_schedule)
138 res = sel->to_appear_in_schedule(block_env, irn);
140 return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_RegParams(irn));
143 static const list_sched_selector_t trivial_selector_struct = {
147 NULL, /* to_appear_in_schedule */
150 NULL, /* finish_block */
151 NULL /* finish_graph */
154 const list_sched_selector_t *trivial_selector = &trivial_selector_struct;
156 typedef struct _usage_stats_t {
158 struct _usage_stats_t *next;
160 int uses_in_block; /**< Number of uses inside the current block. */
161 int already_consumed; /**< Number of insns using this value already
166 const list_sched_selector_t *vtab;
167 const arch_env_t *arch_env;
168 } reg_pressure_main_env_t;
172 const reg_pressure_main_env_t *main_env;
174 nodeset *already_scheduled;
175 } reg_pressure_selector_env_t;
177 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
179 usage_stats_t *us = get_irn_link(irn);
182 us = obstack_alloc(&env->obst, sizeof(us[0]));
184 us->already_consumed = 0;
185 us->max_hops = INT_MAX;
186 us->next = env->root;
188 set_irn_link(irn, us);
194 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
196 usage_stats_t *us = get_irn_link(irn);
197 assert(us && "This node must have usage stats");
201 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
203 ir_node *bl = get_nodes_block(irn);
205 * If the reached node is not in the block desired,
206 * return the value passed for this situation.
208 if(get_nodes_block(irn) != bl)
209 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
212 * If the node is in the current block but not
213 * yet scheduled, we keep on searching from that node.
215 if(!nodeset_find(env->already_scheduled, irn)) {
218 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
219 ir_node *operand = get_irn_n(irn, i);
221 if(get_irn_visited(operand) < visited_nr) {
224 set_irn_visited(operand, visited_nr);
225 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
234 * If the node is in the current block and scheduled, return
235 * the depth which indicates the number of steps to the
236 * region of scheduled nodes.
241 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
243 ir_node *bl = get_nodes_block(irn);
244 ir_graph *irg = get_irn_irg(bl);
247 const ir_edge_t *edge;
249 foreach_out_edge(irn, edge) {
250 ir_node *user = get_edge_src_irn(edge);
251 unsigned visited_nr = get_irg_visited(irg) + 1;
254 set_irg_visited(irg, visited_nr);
255 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
256 res = MAX(res, max_hops);
262 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
264 reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
266 main_env->arch_env = arch_env;
267 main_env->vtab = vtab;
268 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
273 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
276 reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0]));
278 obstack_init(&env->obst);
279 env->already_scheduled = new_nodeset(32);
281 env->main_env = graph_env;
284 * Collect usage statistics.
286 sched_foreach(bl, irn) {
287 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
290 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
291 //ir_node *op = get_irn_n(irn, i);
292 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
293 usage_stats_t *us = get_or_set_usage_stats(env, irn);
294 #if 0 /* Liveness is not computed here! */
295 if(is_live_end(bl, op))
296 us->uses_in_block = 99999;
308 static void reg_pressure_block_free(void *block_env)
310 reg_pressure_selector_env_t *env = block_env;
313 for(us = env->root; us; us = us->next)
314 set_irn_link(us->irn, NULL);
316 obstack_free(&env->obst, NULL);
317 del_nodeset(env->already_scheduled);
321 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
324 if(get_irn_mode(irn) == mode_T) {
325 const ir_edge_t *edge;
327 foreach_out_edge(irn, edge)
328 res += get_result_hops_sum(env, get_edge_src_irn(edge));
331 else if(mode_is_data(get_irn_mode(irn)))
332 res = compute_max_hops(env, irn);
338 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
343 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
344 ir_node *op = get_irn_n(irn, i);
346 if(must_appear_in_schedule(env->main_env->vtab, env, op))
347 sum += compute_max_hops(env, op);
350 sum += get_result_hops_sum(env, irn);
355 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set)
357 reg_pressure_selector_env_t *env = block_env;
358 ir_node *irn, *res = NULL;
359 int curr_cost = INT_MAX;
361 assert(nodeset_count(ready_set) > 0);
363 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
365 Ignore branch instructions for the time being.
366 They should only be scheduled if there is nothing else.
368 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
369 int costs = reg_pr_costs(env, irn);
370 if (costs <= curr_cost) {
378 There was no result so we only saw a branch.
383 res = nodeset_first(ready_set);
384 nodeset_break(ready_set);
386 assert(res && "There must be a node scheduled.");
389 nodeset_insert(env->already_scheduled, res);
394 * Environment for a block scheduler.
396 typedef struct _block_sched_env_t {
397 sched_irn_t *sched_info; /**< scheduling info per node, copied from the global scheduler object */
398 sched_timestep_t curr_time; /**< current time of the scheduler */
399 nodeset *cands; /**< the set of candidates */
400 ir_node *block; /**< the current block */
401 sched_env_t *sched_env; /**< the scheduler environment */
402 nodeset *live; /**< simple liveness during scheduling */
403 const list_sched_selector_t *selector;
404 void *selector_block_env;
405 DEBUG_ONLY(firm_dbg_module_t *dbg;)
409 * Returns non-zero if the node is already scheduled
411 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
413 int idx = get_irn_idx(n);
415 assert(idx < ARR_LEN(env->sched_info));
416 return env->sched_info[idx].already_sched;
420 * Mark a node as already scheduled
422 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
424 int idx = get_irn_idx(n);
426 assert(idx < ARR_LEN(env->sched_info));
427 env->sched_info[idx].already_sched = 1;
431 * Returns non-zero if the node is a root node
433 static INLINE unsigned is_root_node(block_sched_env_t *env, ir_node *n)
435 int idx = get_irn_idx(n);
437 assert(idx < ARR_LEN(env->sched_info));
438 return env->sched_info[idx].is_root;
442 * Mark a node as roto node
444 static INLINE void mark_root_node(block_sched_env_t *env, ir_node *n)
446 int idx = get_irn_idx(n);
448 assert(idx < ARR_LEN(env->sched_info));
449 env->sched_info[idx].is_root = 1;
453 * Get the current delay.
455 static INLINE sched_timestep_t get_irn_delay(block_sched_env_t *env, ir_node *n) {
456 int idx = get_irn_idx(n);
458 assert(idx < ARR_LEN(env->sched_info));
459 return env->sched_info[idx].delay;
463 * Set the current delay.
465 static INLINE void set_irn_delay(block_sched_env_t *env, ir_node *n, sched_timestep_t delay) {
466 int idx = get_irn_idx(n);
468 assert(idx < ARR_LEN(env->sched_info));
469 env->sched_info[idx].delay = delay;
473 * Get the current etime.
475 static INLINE sched_timestep_t get_irn_etime(block_sched_env_t *env, ir_node *n) {
476 int idx = get_irn_idx(n);
478 assert(idx < ARR_LEN(env->sched_info));
479 return env->sched_info[idx].etime;
483 * Set the current etime.
485 static INLINE void set_irn_etime(block_sched_env_t *env, ir_node *n, sched_timestep_t etime) {
486 int idx = get_irn_idx(n);
488 assert(idx < ARR_LEN(env->sched_info));
489 env->sched_info[idx].etime = etime;
493 * Get the number of users.
495 static INLINE unsigned get_irn_num_user(block_sched_env_t *env, ir_node *n) {
496 int idx = get_irn_idx(n);
498 assert(idx < ARR_LEN(env->sched_info));
499 return env->sched_info[idx].num_user;
503 * Set the number of users.
505 static INLINE void set_irn_num_user(block_sched_env_t *env, ir_node *n, unsigned num_user) {
506 int idx = get_irn_idx(n);
508 assert(idx < ARR_LEN(env->sched_info));
509 env->sched_info[idx].num_user = num_user;
513 * Get the register difference.
515 static INLINE int get_irn_reg_diff(block_sched_env_t *env, ir_node *n) {
516 int idx = get_irn_idx(n);
518 assert(idx < ARR_LEN(env->sched_info));
519 return env->sched_info[idx].reg_diff;
523 * Set the register difference.
525 static INLINE void set_irn_reg_diff(block_sched_env_t *env, ir_node *n, int reg_diff) {
526 int idx = get_irn_idx(n);
528 assert(idx < ARR_LEN(env->sched_info));
529 env->sched_info[idx].reg_diff = reg_diff;
533 * Get the pre-order position.
535 static INLINE int get_irn_preorder(block_sched_env_t *env, ir_node *n) {
536 int idx = get_irn_idx(n);
538 assert(idx < ARR_LEN(env->sched_info));
539 return env->sched_info[idx].preorder;
543 * Set the pre-order position.
545 static INLINE void set_irn_preorder(block_sched_env_t *env, ir_node *n, int pos) {
546 int idx = get_irn_idx(n);
548 assert(idx < ARR_LEN(env->sched_info));
549 env->sched_info[idx].preorder = pos;
553 * returns the exec-time for node n.
555 static sched_timestep_t exectime(sched_env_t *env, ir_node *n) {
556 if (be_is_Keep(n) || is_Proj(n))
558 if (env->selector->exectime)
559 return env->selector->exectime(env->selector_env, n);
564 * Calculates the latency for between two ops
566 static sched_timestep_t latency(sched_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
567 /* a Keep hides a root */
568 if (be_is_Keep(curr))
569 return exectime(env, pred);
571 /* Proj's are executed immediately */
575 /* predecessors Proj's must be skipped */
577 pred = get_Proj_pred(pred);
579 if (env->selector->latency)
580 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
585 * Try to put a node in the ready set.
586 * @param env The block scheduler environment.
587 * @param pred The previous scheduled node.
588 * @param irn The node to make ready.
589 * @return 1, if the node could be made ready, 0 else.
591 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
594 sched_timestep_t etime_p, etime;
596 /* Blocks cannot be scheduled. */
601 * Check, if the given ir node is in a different block as the
602 * currently scheduled one. If that is so, don't make the node ready.
604 if (env->block != get_nodes_block(irn))
607 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
608 ir_node *op = get_irn_n(irn, i);
610 /* if irn is an End we have keep-alives and op might be a block, skip that */
612 assert(get_irn_op(irn) == op_End);
616 /* If the operand is local to the scheduled block and not yet
617 * scheduled, this nodes cannot be made ready, so exit. */
618 if (!is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
622 nodeset_insert(env->cands, irn);
624 /* calculate the etime of this node */
625 etime = env->curr_time;
627 etime_p = get_irn_etime(env, pred);
628 etime += latency(env->sched_env, pred, 1, irn, 0);
630 etime = etime_p > etime ? etime_p : etime;
633 set_irn_etime(env, irn, etime);
635 DB((env->dbg, LEVEL_2, "\tmaking ready: %+F etime %u\n", irn, etime));
641 * Try, to make all users of a node ready.
642 * In fact, a usage node can only be made ready, if all its operands
643 * have already been scheduled yet. This is checked my make_ready().
644 * @param env The block schedule environment.
645 * @param irn The node, which usages (successors) are to be made ready.
647 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
649 const ir_edge_t *edge;
651 foreach_out_edge(irn, edge) {
652 ir_node *user = edge->src;
654 make_ready(env, irn, user);
659 * Returns the number of not yet schedules users.
661 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
662 int idx = get_irn_idx(n);
664 assert(idx < ARR_LEN(env->sched_info));
665 return env->sched_info[idx].num_not_sched_user;
669 * Sets the number of not yet schedules users.
671 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
672 int idx = get_irn_idx(n);
674 assert(idx < ARR_LEN(env->sched_info));
675 env->sched_info[idx].num_not_sched_user = num;
679 * Add @p num to the number of not yet schedules users and returns the result.
681 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
682 int idx = get_irn_idx(n);
684 assert(idx < ARR_LEN(env->sched_info));
685 env->sched_info[idx].num_not_sched_user += num;
686 return env->sched_info[idx].num_not_sched_user;
690 * Returns the number of users of a node having mode datab.
692 static int get_num_successors(ir_node *irn) {
694 const ir_edge_t *edge;
696 if (get_irn_mode(irn) == mode_T) {
697 /* for mode_T nodes: count the users of all Projs */
698 foreach_out_edge(irn, edge) {
699 ir_node *proj = get_edge_src_irn(edge);
700 ir_mode *mode = get_irn_mode(proj);
703 sum += get_num_successors(proj);
704 else if (mode_is_datab(mode))
705 sum += get_irn_n_edges(proj);
709 /* do not count keep-alive edges */
710 foreach_out_edge(irn, edge) {
711 if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
720 * Adds irn to @p live, updates all inputs that this user is scheduled
721 * and counts all of it's non scheduled users.
723 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
730 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
731 ir_node *in = get_irn_n(irn, i);
733 /* if in is a proj: update predecessor */
735 in = get_Proj_pred(in);
737 /* if in is still in the live set: reduce number of users by one */
738 if (nodeset_find(env->live, in)) {
739 if (add_irn_not_sched_user(env, in, -1) <= 0)
740 nodeset_remove(env->live, in);
745 get_num_successors returns the number of all users. This includes
746 users in different blocks as well. As the each block is scheduled separately
747 the liveness info of those users will not be updated and so these
748 users will keep up the register pressure as it is desired.
750 i = get_num_successors(irn);
752 set_irn_not_sched_user(env, irn, i);
753 nodeset_insert(env->live, irn);
758 * Returns the current register pressure for the current block
760 * This is the number of already scheduled nodes having not yet
763 static INLINE int get_cur_reg_pressure(block_sched_env_t *env) {
765 Nodes with all users scheduled are removed from live set,
766 so the number of nodes in this set represent the current
767 register pressure in this block.
769 return nodeset_count(env->live);
773 * Append an instruction to a schedule.
774 * @param env The block scheduling environment.
775 * @param irn The node to add to the schedule.
776 * @return The given node.
778 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
780 /* If the node consumes/produces data, it is appended to the schedule
781 * list, otherwise, it is not put into the list */
782 if(must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
783 sched_info_t *info = get_irn_sched_info(irn);
784 INIT_LIST_HEAD(&info->list);
786 update_sched_liveness(env, irn);
787 sched_add_before(env->block, irn);
789 DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
792 /* Insert the node in the set of all already scheduled nodes. */
793 mark_already_scheduled(env, irn);
795 /* Remove the node from the ready set */
796 if(nodeset_find(env->cands, irn))
797 nodeset_remove(env->cands, irn);
803 * Add the proj nodes of a tuple-mode irn to the schedule immediately
804 * after the tuple-moded irn. By pinning the projs after the irn, no
805 * other nodes can create a new lifetime between the tuple-moded irn and
806 * one of its projs. This should render a realistic image of a
807 * tuple-moded irn, which in fact models a node which defines multiple
810 * @param irn The tuple-moded irn.
812 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
814 const ir_edge_t *edge;
816 assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
821 foreach_out_edge(irn, edge) {
822 ir_node *out = edge->src;
824 assert(is_Proj(out) && "successor of a modeT node must be a proj");
826 if (get_irn_mode(out) == mode_T)
827 add_tuple_projs(env, out);
829 add_to_sched(env, out);
830 make_users_ready(env, out);
836 * Returns the difference of regs_output - regs_input;
838 static int get_reg_difference(block_sched_env_t *be, ir_node *irn) {
843 if (get_irn_mode(irn) == mode_T) {
844 /* mode_T nodes: num out regs == num Projs with mode datab */
845 const ir_edge_t *edge;
846 foreach_out_edge(irn, edge) {
847 ir_node *proj = get_edge_src_irn(edge);
848 if (mode_is_datab(get_irn_mode(proj)))
855 /* num in regs: number of ins with mode datab and not ignore */
856 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
857 ir_node *in = get_irn_n(irn, i);
858 if (mode_is_datab(get_irn_mode(in)) && ! arch_irn_is(be->sched_env->arch_env, irn, ignore))
862 return num_out - num_in;
866 * Execute the heuristic function,
868 static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
870 ir_node *irn, *cand = NULL;
872 /* prefer instructions which can be scheduled early */
874 /* prefer instructions with lots of successors */
875 #define PRIO_NUMSUCCS 4
876 /* prefer instructions with long critical path */
877 #define PRIO_LEVEL 12
878 /* prefer instructions coming early in preorder */
879 #define PRIO_PREORD 8
880 /* weight of current register pressure */
881 #define PRIO_CUR_PRESS 20
882 /* weight of register pressure difference */
883 #define PRIO_CHG_PRESS 14
885 /* schedule keeps as early as possible */
886 foreach_nodeset(ns, irn) {
887 if (be_is_Keep(irn)) {
893 if (be->sched_env->use_heuristic) {
894 int max_prio = INT_MIN;
895 int cur_prio = INT_MIN;
896 int cur_pressure = get_cur_reg_pressure(be);
898 /* priority based selection, heuristic inspired by mueller diss */
899 foreach_nodeset(ns, irn) {
900 /* make sure that branches are scheduled last */
901 if (! arch_irn_class_is(be->sched_env->arch_env, irn, branch)) {
902 cur_prio = (get_irn_delay(be, irn) << PRIO_LEVEL)
903 + (get_irn_num_user(be, irn) << PRIO_NUMSUCCS)
904 - (get_irn_etime(be, irn) << PRIO_TIME)
905 - ((get_irn_reg_diff(be, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
906 + (get_irn_preorder(be, irn) << PRIO_PREORD); /* high preorder means: early scheduled in pre-order list */
907 if (cur_prio > max_prio) {
915 DBG((be->dbg, LEVEL_4, "heuristic selected %+F:\n", cand));
916 DBG((be->dbg, LEVEL_4, "\tpriority: %d\n", cand));
917 DBG((be->dbg, LEVEL_4, "\tdelay: %d (%d)\n", get_irn_delay(be, cand), get_irn_delay(be, cand) << PRIO_LEVEL));
918 DBG((be->dbg, LEVEL_4, "\t#user: %d (%d)\n", get_irn_num_user(be, cand), get_irn_num_user(be, cand) << PRIO_NUMSUCCS));
919 DBG((be->dbg, LEVEL_4, "\tetime: %d (%d)\n", get_irn_etime(be, cand), -(get_irn_etime(be, cand) << PRIO_TIME)));
920 DBG((be->dbg, LEVEL_4, "\tpreorder: %d (%d)\n", get_irn_preorder(be, cand), get_irn_preorder(be, cand) << PRIO_PREORD));
921 DBG((be->dbg, LEVEL_4, "\treg diff: %d (%d)\n", get_irn_reg_diff(be, cand), -(((get_irn_reg_diff(be, cand) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3)))));
922 DBG((be->dbg, LEVEL_4, "\tpressure: %d\n", cur_pressure));
925 cand = nodeset_first(ns);
929 /* use backend selector */
930 cand = be->selector->select(be->selector_block_env, ns);
937 * Returns non-zero if root is a root in the block block.
939 static int is_root(ir_node *root, ir_node *block) {
940 const ir_edge_t *edge;
942 foreach_out_edge(root, edge) {
943 ir_node *succ = get_edge_src_irn(edge);
947 /* Phi nodes are always in "another block */
950 if (get_nodes_block(succ) == block)
956 /* we need a special mark */
960 static firm_dbg_module_t *xxxdbg;
963 * descent into a dag and create a pre-order list.
965 static void descent(ir_node *root, ir_node *block, ir_node **list, block_sched_env_t *env, int cur_depth) {
970 if (! is_Phi(root)) {
971 /* Phi nodes always leave the block */
972 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
973 ir_node *pred = get_irn_n(root, i);
975 DBG((xxxdbg, LEVEL_3, " node %+F\n", pred));
976 /* Blocks may happen as predecessors of End nodes */
980 /* already seen nodes are not marked */
981 if (get_irn_link(pred) != MARK)
984 /* don't leave our block */
985 if (get_nodes_block(pred) != block)
988 set_irn_link(pred, NULL);
989 set_irn_preorder(env, pred, cur_depth);
991 descent(pred, block, list, env, cur_depth);
994 set_irn_link(root, *list);
1001 * Perform list scheduling on a block.
1003 * Note, that the caller must compute a linked list of nodes in the block
1004 * using the link field before calling this function.
1006 * Also the outs must have been computed.
1008 * @param block The block node.
1009 * @param env Scheduling environment.
1011 static void list_sched_block(ir_node *block, void *env_ptr)
1013 sched_env_t *env = env_ptr;
1014 const list_sched_selector_t *selector = env->selector;
1015 ir_node *start_node = get_irg_start(get_irn_irg(block));
1016 sched_info_t *info = get_irn_sched_info(block);
1018 block_sched_env_t be;
1019 const ir_edge_t *edge;
1023 ir_node *root = NULL, *preord = NULL;
1026 /* Initialize the block's list head that will hold the schedule. */
1027 INIT_LIST_HEAD(&info->list);
1029 /* Initialize the block scheduling environment */
1030 be.sched_info = env->sched_info;
1033 be.cands = new_nodeset(get_irn_n_edges(block));
1034 be.live = new_nodeset(get_irn_n_edges(block));
1035 be.selector = selector;
1037 FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
1038 FIRM_DBG_REGISTER(xxxdbg, "firm.be.sched");
1040 // firm_dbg_set_mask(be.dbg, SET_LEVEL_3);
1042 if (selector->init_block)
1043 be.selector_block_env = selector->init_block(env->selector_env, block);
1045 DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
1047 /* First step: Find the root set. */
1048 foreach_out_edge(block, edge) {
1049 ir_node *succ = get_edge_src_irn(edge);
1051 if (is_root(succ, block)) {
1052 mark_root_node(&be, succ);
1053 set_irn_link(succ, root);
1057 set_irn_link(succ, MARK);
1060 /* Second step: calculate the pre-order list. */
1062 for (curr = root; curr; curr = irn) {
1063 irn = get_irn_link(curr);
1064 DBG((be.dbg, LEVEL_2, " DAG root %+F\n", curr));
1065 descent(curr, block, &preord, &be, 0);
1069 /* Third step: calculate the Delay. Note that our
1070 * list is now in pre-order, starting at root
1072 for (curr = root; curr; curr = get_irn_link(curr)) {
1075 if (arch_irn_class_is(env->arch_env, curr, branch)) {
1076 /* assure, that branches can be executed last */
1080 if (is_root_node(&be, curr))
1081 d = exectime(env, curr);
1084 foreach_out_edge(curr, edge) {
1085 ir_node *n = get_edge_src_irn(edge);
1087 if (get_nodes_block(n) == block) {
1088 sched_timestep_t ld;
1090 ld = latency(env, curr, 1, n, 0) + get_irn_delay(&be, n);
1091 d = ld > d ? ld : d;
1096 set_irn_delay(&be, curr, d);
1097 DB((be.dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
1099 /* set the etime of all nodes to 0 */
1100 set_irn_etime(&be, curr, 0);
1104 /* Then one can add all nodes are ready to the set. */
1105 foreach_out_edge(block, edge) {
1106 ir_node *irn = get_edge_src_irn(edge);
1108 /* Skip the end node because of keepalive edges. */
1109 if (get_irn_opcode(irn) == iro_End)
1113 /* Phi functions are scheduled immediately, since they only transfer
1114 * data flow from the predecessors to this block. */
1116 /* Increase the time step. */
1117 be.curr_time += get_irn_etime(&be, irn);
1118 add_to_sched(&be, irn);
1119 make_users_ready(&be, irn);
1121 else if (irn == start_node) {
1122 /* The start block will be scheduled as the first node */
1123 be.curr_time += get_irn_etime(&be, irn);
1125 add_to_sched(&be, irn);
1126 add_tuple_projs(&be, irn);
1129 /* Other nodes must have all operands in other blocks to be made
1133 /* Check, if the operands of a node are not local to this block */
1134 for (j = 0, m = get_irn_arity(irn); j < m; ++j) {
1135 ir_node *operand = get_irn_n(irn, j);
1137 if (get_nodes_block(operand) == block) {
1142 /* live in values increase register pressure */
1143 update_sched_liveness(&be, operand);
1147 /* Make the node ready, if all operands live in a foreign block */
1149 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
1150 make_ready(&be, NULL, irn);
1153 /* calculate number of users (needed for heuristic) */
1154 set_irn_num_user(&be, irn, get_num_successors(irn));
1156 /* calculate register difference (needed for heuristic) */
1157 set_irn_reg_diff(&be, irn, get_reg_difference(&be, irn));
1161 while (nodeset_count(be.cands) > 0) {
1162 nodeset *mcands; /**< the set of candidates with maximum delay time */
1163 nodeset *ecands; /**< the set of nodes in mcands whose etime <= curr_time */
1164 sched_timestep_t max_delay = 0;
1166 /* collect statistics about amount of ready nodes */
1167 be_do_stat_sched_ready(block, be.cands);
1169 /* calculate the max delay of all candidates */
1170 foreach_nodeset(be.cands, irn) {
1171 sched_timestep_t d = get_irn_delay(&be, irn);
1173 max_delay = d > max_delay ? d : max_delay;
1175 mcands = new_nodeset(8);
1176 ecands = new_nodeset(8);
1178 /* calculate mcands and ecands */
1179 foreach_nodeset(be.cands, irn) {
1180 if (be_is_Keep(irn)) {
1181 nodeset_break(be.cands);
1184 if (get_irn_delay(&be, irn) == max_delay) {
1185 nodeset_insert(mcands, irn);
1186 if (get_irn_etime(&be, irn) <= be.curr_time)
1187 nodeset_insert(ecands, irn);
1192 /* Keeps must be immediately scheduled */
1195 DB((be.dbg, LEVEL_2, "\tbe.curr_time = %u\n", be.curr_time));
1197 /* select a node to be scheduled and check if it was ready */
1198 if (nodeset_count(mcands) == 1) {
1199 irn = nodeset_first(mcands);
1200 DB((be.dbg, LEVEL_3, "\tirn = %+F, mcand = 1, max_delay = %u\n", irn, max_delay));
1203 int cnt = nodeset_count(ecands);
1205 irn = nodeset_first(ecands);
1207 if (arch_irn_class_is(env->arch_env, irn, branch)) {
1208 /* BEWARE: don't select a JUMP if others are still possible */
1211 DB((be.dbg, LEVEL_3, "\tirn = %+F, ecand = 1, max_delay = %u\n", irn, max_delay));
1214 DB((be.dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
1215 irn = select_node_heuristic(&be, ecands);
1219 DB((be.dbg, LEVEL_3, "\tmcand = %d\n", nodeset_count(mcands)));
1220 irn = select_node_heuristic(&be, mcands);
1224 del_nodeset(mcands);
1225 del_nodeset(ecands);
1227 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
1229 /* Increase the time step. */
1230 be.curr_time += exectime(env, irn);
1232 /* Add the node to the schedule. */
1233 add_to_sched(&be, irn);
1235 if (get_irn_mode(irn) == mode_T)
1236 add_tuple_projs(&be, irn);
1238 make_users_ready(&be, irn);
1240 /* remove the scheduled node from the ready list. */
1241 if (nodeset_find(be.cands, irn))
1242 nodeset_remove(be.cands, irn);
1245 if (selector->finish_block)
1246 selector->finish_block(be.selector_block_env);
1248 del_nodeset(be.cands);
1249 del_nodeset(be.live);
1252 static const list_sched_selector_t reg_pressure_selector_struct = {
1253 reg_pressure_graph_init,
1254 reg_pressure_block_init,
1255 reg_pressure_select,
1256 NULL, /* to_appear_in_schedule */
1257 NULL, /* exectime */
1259 reg_pressure_block_free,
1263 const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct;
1265 /* List schedule a graph. */
1266 void list_sched(const be_irg_t *birg, be_options_t *be_opts)
1268 const arch_env_t *arch_env = birg->main_env->arch_env;
1269 ir_graph *irg = birg->irg;
1275 /* Assure, that the out edges are computed */
1279 mris = be_sched_mris_preprocess(birg);
1281 num_nodes = get_irg_last_idx(irg);
1283 memset(&env, 0, sizeof(env));
1284 env.selector = arch_env->isa->impl->get_list_sched_selector(arch_env->isa);
1285 env.arch_env = arch_env;
1287 env.use_heuristic = be_opts->sched_select == BE_SCHED_SELECT_HEUR ? 1 : 0;
1288 env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
1290 memset(env.sched_info, 0, num_nodes * sizeof(*env.sched_info));
1292 if (env.selector->init_graph)
1293 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
1295 /* Schedule each single block. */
1296 irg_block_walk_graph(irg, list_sched_block, NULL, &env);
1298 if (env.selector->finish_graph)
1299 env.selector->finish_graph(env.selector_env);
1302 be_sched_mris_free(mris);
1304 DEL_ARR_F(env.sched_info);