2 * Scheduling algorithms.
3 * Just a simple list scheduling algorithm is here.
5 * @author Sebastian Hack
24 #include "iredges_t.h"
29 #include "irprintf_t.h"
34 #include "besched_t.h"
37 #include "belistsched.h"
38 #include "beschedmris.h"
43 * All scheduling info needed per node.
45 typedef struct _sched_irn_t {
46 sched_timestep_t delay; /**< The delay for this node if already calculated, else 0. */
47 sched_timestep_t etime; /**< The earliest time of this node. */
48 unsigned num_user; /**< The number real users (mode datab) of this node */
49 unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
50 int reg_diff; /**< The difference of num(out registers) - num(in registers) */
51 int preorder; /**< The pre-order position */
52 unsigned already_sched : 1; /**< Set if this node is already scheduled */
53 unsigned is_root : 1; /**< is a root node of a block */
57 * Scheduling environment for the whole graph.
59 typedef struct _sched_env_t {
60 sched_irn_t *sched_info; /**< scheduling info per node */
61 const list_sched_selector_t *selector; /**< The node selector. */
62 const arch_env_t *arch_env; /**< The architecture environment. */
63 const ir_graph *irg; /**< The graph to schedule. */
64 void *selector_env; /**< A pointer to give to the selector. */
69 * Ugly global variable for the compare function
70 * since qsort(3) does not pass an extra pointer.
72 static ir_node *curr_bl = NULL;
74 static int cmp_usage(const void *a, const void *b)
76 struct trivial_sched_env *env;
81 res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
84 * One of them is live at the end of the block.
85 * Then, that one shall be scheduled at after the other
96 * The trivial selector:
97 * Just assure that branches are executed last, otherwise select
98 * the first node ready.
100 static ir_node *trivial_select(void *block_env, nodeset *ready_set)
102 const arch_env_t *arch_env = block_env;
105 /* assure that branches and constants are executed last */
106 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
107 if (! arch_irn_class_is(arch_env, irn, branch)) {
108 nodeset_break(ready_set);
114 /* at last: schedule branches */
115 irn = nodeset_first(ready_set);
116 nodeset_break(ready_set);
121 static void *trivial_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
123 return (void *) arch_env;
126 static void *trivial_init_block(void *graph_env, ir_node *bl)
131 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
135 if(sel->to_appear_in_schedule)
136 res = sel->to_appear_in_schedule(block_env, irn);
138 return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_RegParams(irn));
141 static const list_sched_selector_t trivial_selector_struct = {
145 NULL, /* to_appear_in_schedule */
148 NULL, /* finish_block */
149 NULL /* finish_graph */
152 const list_sched_selector_t *trivial_selector = &trivial_selector_struct;
154 typedef struct _usage_stats_t {
156 struct _usage_stats_t *next;
158 int uses_in_block; /**< Number of uses inside the current block. */
159 int already_consumed; /**< Number of insns using this value already
164 const list_sched_selector_t *vtab;
165 const arch_env_t *arch_env;
166 } reg_pressure_main_env_t;
170 const reg_pressure_main_env_t *main_env;
172 nodeset *already_scheduled;
173 } reg_pressure_selector_env_t;
175 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
177 usage_stats_t *us = get_irn_link(irn);
180 us = obstack_alloc(&env->obst, sizeof(us[0]));
182 us->already_consumed = 0;
183 us->max_hops = INT_MAX;
184 us->next = env->root;
186 set_irn_link(irn, us);
192 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
194 usage_stats_t *us = get_irn_link(irn);
195 assert(us && "This node must have usage stats");
199 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
201 ir_node *bl = get_nodes_block(irn);
203 * If the reached node is not in the block desired,
204 * return the value passed for this situation.
206 if(get_nodes_block(irn) != bl)
207 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
210 * If the node is in the current block but not
211 * yet scheduled, we keep on searching from that node.
213 if(!nodeset_find(env->already_scheduled, irn)) {
216 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
217 ir_node *operand = get_irn_n(irn, i);
219 if(get_irn_visited(operand) < visited_nr) {
222 set_irn_visited(operand, visited_nr);
223 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
232 * If the node is in the current block and scheduled, return
233 * the depth which indicates the number of steps to the
234 * region of scheduled nodes.
239 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
241 ir_node *bl = get_nodes_block(irn);
242 ir_graph *irg = get_irn_irg(bl);
245 const ir_edge_t *edge;
247 foreach_out_edge(irn, edge) {
248 ir_node *user = get_edge_src_irn(edge);
249 unsigned visited_nr = get_irg_visited(irg) + 1;
252 set_irg_visited(irg, visited_nr);
253 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
254 res = MAX(res, max_hops);
260 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
262 reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
264 main_env->arch_env = arch_env;
265 main_env->vtab = vtab;
266 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
271 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
274 reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0]));
276 obstack_init(&env->obst);
277 env->already_scheduled = new_nodeset(32);
279 env->main_env = graph_env;
282 * Collect usage statistics.
284 sched_foreach(bl, irn) {
285 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
288 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
289 //ir_node *op = get_irn_n(irn, i);
290 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
291 usage_stats_t *us = get_or_set_usage_stats(env, irn);
292 #if 0 /* Liveness is not computed here! */
293 if(is_live_end(bl, op))
294 us->uses_in_block = 99999;
306 static void reg_pressure_block_free(void *block_env)
308 reg_pressure_selector_env_t *env = block_env;
311 for(us = env->root; us; us = us->next)
312 set_irn_link(us->irn, NULL);
314 obstack_free(&env->obst, NULL);
315 del_nodeset(env->already_scheduled);
319 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
322 if(get_irn_mode(irn) == mode_T) {
323 const ir_edge_t *edge;
325 foreach_out_edge(irn, edge)
326 res += get_result_hops_sum(env, get_edge_src_irn(edge));
329 else if(mode_is_data(get_irn_mode(irn)))
330 res = compute_max_hops(env, irn);
336 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
341 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
342 ir_node *op = get_irn_n(irn, i);
344 if(must_appear_in_schedule(env->main_env->vtab, env, op))
345 sum += compute_max_hops(env, op);
348 sum += get_result_hops_sum(env, irn);
353 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set)
355 reg_pressure_selector_env_t *env = block_env;
356 ir_node *irn, *res = NULL;
357 int curr_cost = INT_MAX;
359 assert(nodeset_count(ready_set) > 0);
361 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
363 Ignore branch instructions for the time being.
364 They should only be scheduled if there is nothing else.
366 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
367 int costs = reg_pr_costs(env, irn);
368 if (costs <= curr_cost) {
376 There was no result so we only saw a branch.
381 res = nodeset_first(ready_set);
382 nodeset_break(ready_set);
384 assert(res && "There must be a node scheduled.");
387 nodeset_insert(env->already_scheduled, res);
392 * Environment for a block scheduler.
394 typedef struct _block_sched_env_t {
395 sched_irn_t *sched_info; /**< scheduling info per node, copied from the global scheduler object */
396 sched_timestep_t curr_time; /**< current time of the scheduler */
397 nodeset *cands; /**< the set of candidates */
398 ir_node *block; /**< the current block */
399 sched_env_t *sched_env; /**< the scheduler environment */
400 nodeset *live; /**< simple liveness during scheduling */
401 const list_sched_selector_t *selector;
402 void *selector_block_env;
403 DEBUG_ONLY(firm_dbg_module_t *dbg;)
407 * Returns non-zero if the node is already scheduled
409 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
411 int idx = get_irn_idx(n);
413 assert(idx < ARR_LEN(env->sched_info));
414 return env->sched_info[idx].already_sched;
418 * Mark a node as already scheduled
420 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
422 int idx = get_irn_idx(n);
424 assert(idx < ARR_LEN(env->sched_info));
425 env->sched_info[idx].already_sched = 1;
429 * Returns non-zero if the node is a root node
431 static INLINE unsigned is_root_node(block_sched_env_t *env, ir_node *n)
433 int idx = get_irn_idx(n);
435 assert(idx < ARR_LEN(env->sched_info));
436 return env->sched_info[idx].is_root;
440 * Mark a node as roto node
442 static INLINE void mark_root_node(block_sched_env_t *env, ir_node *n)
444 int idx = get_irn_idx(n);
446 assert(idx < ARR_LEN(env->sched_info));
447 env->sched_info[idx].is_root = 1;
451 * Get the current delay.
453 static INLINE sched_timestep_t get_irn_delay(block_sched_env_t *env, ir_node *n) {
454 int idx = get_irn_idx(n);
456 assert(idx < ARR_LEN(env->sched_info));
457 return env->sched_info[idx].delay;
461 * Set the current delay.
463 static INLINE void set_irn_delay(block_sched_env_t *env, ir_node *n, sched_timestep_t delay) {
464 int idx = get_irn_idx(n);
466 assert(idx < ARR_LEN(env->sched_info));
467 env->sched_info[idx].delay = delay;
471 * Get the current etime.
473 static INLINE sched_timestep_t get_irn_etime(block_sched_env_t *env, ir_node *n) {
474 int idx = get_irn_idx(n);
476 assert(idx < ARR_LEN(env->sched_info));
477 return env->sched_info[idx].etime;
481 * Set the current etime.
483 static INLINE void set_irn_etime(block_sched_env_t *env, ir_node *n, sched_timestep_t etime) {
484 int idx = get_irn_idx(n);
486 assert(idx < ARR_LEN(env->sched_info));
487 env->sched_info[idx].etime = etime;
491 * Get the number of users.
493 static INLINE unsigned get_irn_num_user(block_sched_env_t *env, ir_node *n) {
494 int idx = get_irn_idx(n);
496 assert(idx < ARR_LEN(env->sched_info));
497 return env->sched_info[idx].num_user;
501 * Set the number of users.
503 static INLINE void set_irn_num_user(block_sched_env_t *env, ir_node *n, unsigned num_user) {
504 int idx = get_irn_idx(n);
506 assert(idx < ARR_LEN(env->sched_info));
507 env->sched_info[idx].num_user = num_user;
511 * Get the register difference.
513 static INLINE int get_irn_reg_diff(block_sched_env_t *env, ir_node *n) {
514 int idx = get_irn_idx(n);
516 assert(idx < ARR_LEN(env->sched_info));
517 return env->sched_info[idx].reg_diff;
521 * Set the register difference.
523 static INLINE void set_irn_reg_diff(block_sched_env_t *env, ir_node *n, int reg_diff) {
524 int idx = get_irn_idx(n);
526 assert(idx < ARR_LEN(env->sched_info));
527 env->sched_info[idx].reg_diff = reg_diff;
531 * Get the pre-order position.
533 static INLINE int get_irn_preorder(block_sched_env_t *env, ir_node *n) {
534 int idx = get_irn_idx(n);
536 assert(idx < ARR_LEN(env->sched_info));
537 return env->sched_info[idx].preorder;
541 * Set the pre-order position.
543 static INLINE void set_irn_preorder(block_sched_env_t *env, ir_node *n, int pos) {
544 int idx = get_irn_idx(n);
546 assert(idx < ARR_LEN(env->sched_info));
547 env->sched_info[idx].preorder = pos;
551 * returns the exec-time for node n.
553 static sched_timestep_t exectime(sched_env_t *env, ir_node *n) {
554 if (be_is_Keep(n) || is_Proj(n))
556 if (env->selector->exectime)
557 return env->selector->exectime(env->selector_env, n);
562 * Calculates the latency for between two ops
564 static sched_timestep_t latency(sched_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
565 /* a Keep hides a root */
566 if (be_is_Keep(curr))
567 return exectime(env, pred);
569 /* Proj's are executed immediately */
573 /* predecessors Proj's must be skipped */
575 pred = get_Proj_pred(pred);
577 if (env->selector->latency)
578 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
583 * Try to put a node in the ready set.
584 * @param env The block scheduler environment.
585 * @param pred The previous scheduled node.
586 * @param irn The node to make ready.
587 * @return 1, if the node could be made ready, 0 else.
589 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
592 sched_timestep_t etime_p, etime;
594 /* Blocks cannot be scheduled. */
599 * Check, if the given ir node is in a different block as the
600 * currently scheduled one. If that is so, don't make the node ready.
602 if (env->block != get_nodes_block(irn))
605 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
606 ir_node *op = get_irn_n(irn, i);
608 /* if irn is an End we have keep-alives and op might be a block, skip that */
610 assert(get_irn_op(irn) == op_End);
614 /* If the operand is local to the scheduled block and not yet
615 * scheduled, this nodes cannot be made ready, so exit. */
616 if (!is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
620 nodeset_insert(env->cands, irn);
622 /* calculate the etime of this node */
623 etime = env->curr_time;
625 etime_p = get_irn_etime(env, pred);
626 etime += latency(env->sched_env, pred, 1, irn, 0);
628 etime = etime_p > etime ? etime_p : etime;
631 set_irn_etime(env, irn, etime);
633 DB((env->dbg, LEVEL_2, "\tmaking ready: %+F etime %u\n", irn, etime));
639 * Try, to make all users of a node ready.
640 * In fact, a usage node can only be made ready, if all its operands
641 * have already been scheduled yet. This is checked my make_ready().
642 * @param env The block schedule environment.
643 * @param irn The node, which usages (successors) are to be made ready.
645 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
647 const ir_edge_t *edge;
649 foreach_out_edge(irn, edge) {
650 ir_node *user = edge->src;
652 make_ready(env, irn, user);
657 * Returns the number of not yet schedules users.
659 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
660 int idx = get_irn_idx(n);
662 assert(idx < ARR_LEN(env->sched_info));
663 return env->sched_info[idx].num_not_sched_user;
667 * Sets the number of not yet schedules users.
669 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
670 int idx = get_irn_idx(n);
672 assert(idx < ARR_LEN(env->sched_info));
673 env->sched_info[idx].num_not_sched_user = num;
677 * Add @p num to the number of not yet schedules users and returns the result.
679 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
680 int idx = get_irn_idx(n);
682 assert(idx < ARR_LEN(env->sched_info));
683 env->sched_info[idx].num_not_sched_user += num;
684 return env->sched_info[idx].num_not_sched_user;
688 * Returns the number of users of a node having mode datab.
690 static int get_num_successors(ir_node *irn) {
692 const ir_edge_t *edge;
694 if (get_irn_mode(irn) == mode_T) {
695 /* for mode_T nodes: count the users of all Projs */
696 foreach_out_edge(irn, edge) {
697 ir_node *proj = get_edge_src_irn(edge);
698 ir_mode *mode = get_irn_mode(proj);
701 sum += get_num_successors(proj);
702 else if (mode_is_datab(mode))
703 sum += get_irn_n_edges(proj);
707 /* do not count keep-alive edges */
708 foreach_out_edge(irn, edge) {
709 if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
718 * Adds irn to @p live, updates all inputs that this user is scheduled
719 * and counts all of it's non scheduled users.
721 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
728 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
729 ir_node *in = get_irn_n(irn, i);
731 /* if in is a proj: update predecessor */
733 in = get_Proj_pred(in);
735 /* if in is still in the live set: reduce number of users by one */
736 if (nodeset_find(env->live, in)) {
737 if (add_irn_not_sched_user(env, in, -1) <= 0)
738 nodeset_remove(env->live, in);
743 get_num_successors returns the number of all users. This includes
744 users in different blocks as well. As the each block is scheduled separately
745 the liveness info of those users will not be updated and so these
746 users will keep up the register pressure as it is desired.
748 i = get_num_successors(irn);
750 set_irn_not_sched_user(env, irn, i);
751 nodeset_insert(env->live, irn);
756 * Returns the current register pressure for the current block
758 * This is the number of already scheduled nodes having not yet
761 static INLINE int get_cur_reg_pressure(block_sched_env_t *env) {
763 Nodes with all users scheduled are removed from live set,
764 so the number of nodes in this set represent the current
765 register pressure in this block.
767 return nodeset_count(env->live);
771 * Append an instruction to a schedule.
772 * @param env The block scheduling environment.
773 * @param irn The node to add to the schedule.
774 * @return The given node.
776 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
778 /* If the node consumes/produces data, it is appended to the schedule
779 * list, otherwise, it is not put into the list */
780 if(must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
781 sched_info_t *info = get_irn_sched_info(irn);
782 INIT_LIST_HEAD(&info->list);
784 update_sched_liveness(env, irn);
785 sched_add_before(env->block, irn);
787 DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
790 /* Insert the node in the set of all already scheduled nodes. */
791 mark_already_scheduled(env, irn);
793 /* Remove the node from the ready set */
794 if(nodeset_find(env->cands, irn))
795 nodeset_remove(env->cands, irn);
801 * Add the proj nodes of a tuple-mode irn to the schedule immediately
802 * after the tuple-moded irn. By pinning the projs after the irn, no
803 * other nodes can create a new lifetime between the tuple-moded irn and
804 * one of its projs. This should render a realistic image of a
805 * tuple-moded irn, which in fact models a node which defines multiple
808 * @param irn The tuple-moded irn.
810 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
812 const ir_edge_t *edge;
814 assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
819 foreach_out_edge(irn, edge) {
820 ir_node *out = edge->src;
822 assert(is_Proj(out) && "successor of a modeT node must be a proj");
824 if (get_irn_mode(out) == mode_T)
825 add_tuple_projs(env, out);
827 add_to_sched(env, out);
828 make_users_ready(env, out);
834 * Returns the difference of regs_output - regs_input;
836 static int get_reg_difference(block_sched_env_t *be, ir_node *irn) {
841 if (get_irn_mode(irn) == mode_T) {
842 /* mode_T nodes: num out regs == num Projs with mode datab */
843 const ir_edge_t *edge;
844 foreach_out_edge(irn, edge) {
845 ir_node *proj = get_edge_src_irn(edge);
846 if (mode_is_datab(get_irn_mode(proj)))
853 /* num in regs: number of ins with mode datab and not ignore */
854 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
855 ir_node *in = get_irn_n(irn, i);
856 if (mode_is_datab(get_irn_mode(in)) && ! arch_irn_is(be->sched_env->arch_env, irn, ignore))
860 return num_out - num_in;
864 * Execute the heuristic function,
866 static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
868 ir_node *irn, *cand = NULL;
869 int max_prio = INT_MIN;
870 int cur_prio = INT_MIN;
871 int cur_pressure = get_cur_reg_pressure(be);
873 /* prefer instructions which can be scheduled early */
875 /* prefer instructions with lots of successors */
876 #define PRIO_NUMSUCCS 4
877 /* prefer instructions with long critical path */
878 #define PRIO_LEVEL 12
879 /* prefer instructions coming early in preorder */
880 #define PRIO_PREORD 8
881 /* weight of current register pressure */
882 #define PRIO_CUR_PRESS 20
883 /* weight of register pressure difference */
884 #define PRIO_CHG_PRESS 14
886 /* schedule keeps as early as possible */
887 foreach_nodeset(ns, irn) {
888 if (be_is_Keep(irn)) {
894 /* priority based selection, heuristic inspired by mueller diss */
895 foreach_nodeset(ns, irn) {
896 if (! arch_irn_class_is(be->sched_env->arch_env, irn, branch)) {
897 cur_prio = (get_irn_delay(be, irn) << PRIO_LEVEL)
898 + (get_irn_num_user(be, irn) << PRIO_NUMSUCCS)
899 - (get_irn_etime(be, irn) << PRIO_TIME)
900 - ((get_irn_reg_diff(be, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
901 + (get_irn_preorder(be, irn) << PRIO_PREORD); /* high preorder means: early scheduled in pre-order list */
902 if (cur_prio > max_prio) {
910 // ir_printf("scheduling %+F with priority %d, delay %d, #user %d, etime %d, reg diff %d, preorder %d, cur pressure %d\n", cand, cur_prio,
911 // get_irn_delay(be, cand), get_irn_num_user(be, cand), get_irn_etime(be, cand), get_irn_reg_diff(be, cand), get_irn_preorder(be, cand), cur_pressure);
916 return be->selector->select(be->selector_block_env, ns);
920 * Returns non-zero if root is a root in the block block.
922 static int is_root(ir_node *root, ir_node *block) {
923 const ir_edge_t *edge;
925 foreach_out_edge(root, edge) {
926 ir_node *succ = get_edge_src_irn(edge);
930 /* Phi nodes are always in "another block */
933 if (get_nodes_block(succ) == block)
939 /* we need a special mark */
943 static firm_dbg_module_t *xxxdbg;
946 * descent into a dag and create a pre-order list.
948 static void descent(ir_node *root, ir_node *block, ir_node **list, block_sched_env_t *env, int cur_depth) {
953 if (! is_Phi(root)) {
954 /* Phi nodes always leave the block */
955 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
956 ir_node *pred = get_irn_n(root, i);
958 DBG((xxxdbg, LEVEL_3, " node %+F\n", pred));
959 /* Blocks may happen as predecessors of End nodes */
963 /* already seen nodes are not marked */
964 if (get_irn_link(pred) != MARK)
967 /* don't leave our block */
968 if (get_nodes_block(pred) != block)
971 set_irn_link(pred, NULL);
972 set_irn_preorder(env, pred, cur_depth);
974 descent(pred, block, list, env, cur_depth);
977 set_irn_link(root, *list);
984 * Perform list scheduling on a block.
986 * Note, that the caller must compute a linked list of nodes in the block
987 * using the link field before calling this function.
989 * Also the outs must have been computed.
991 * @param block The block node.
992 * @param env Scheduling environment.
994 static void list_sched_block(ir_node *block, void *env_ptr)
996 sched_env_t *env = env_ptr;
997 const list_sched_selector_t *selector = env->selector;
998 ir_node *start_node = get_irg_start(get_irn_irg(block));
999 sched_info_t *info = get_irn_sched_info(block);
1001 block_sched_env_t be;
1002 const ir_edge_t *edge;
1006 ir_node *root = NULL, *preord = NULL;
1009 /* Initialize the block's list head that will hold the schedule. */
1010 INIT_LIST_HEAD(&info->list);
1012 /* Initialize the block scheduling environment */
1013 be.sched_info = env->sched_info;
1016 be.cands = new_nodeset(get_irn_n_edges(block));
1017 be.live = new_nodeset(get_irn_n_edges(block));
1018 be.selector = selector;
1020 FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
1021 FIRM_DBG_REGISTER(xxxdbg, "firm.be.sched");
1023 // firm_dbg_set_mask(be.dbg, SET_LEVEL_3);
1025 if (selector->init_block)
1026 be.selector_block_env = selector->init_block(env->selector_env, block);
1028 DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
1030 /* First step: Find the root set. */
1031 foreach_out_edge(block, edge) {
1032 ir_node *succ = get_edge_src_irn(edge);
1034 if (is_root(succ, block)) {
1035 mark_root_node(&be, succ);
1036 set_irn_link(succ, root);
1040 set_irn_link(succ, MARK);
1043 /* Second step: calculate the pre-order list. */
1045 for (curr = root; curr; curr = irn) {
1046 irn = get_irn_link(curr);
1047 DBG((be.dbg, LEVEL_2, " DAG root %+F\n", curr));
1048 descent(curr, block, &preord, &be, 0);
1052 /* Third step: calculate the Delay. Note that our
1053 * list is now in pre-order, starting at root
1055 for (curr = root; curr; curr = get_irn_link(curr)) {
1058 if (arch_irn_class_is(env->arch_env, curr, branch)) {
1059 /* assure, that branches can be executed last */
1063 if (is_root_node(&be, curr))
1064 d = exectime(env, curr);
1067 foreach_out_edge(curr, edge) {
1068 ir_node *n = get_edge_src_irn(edge);
1070 if (get_nodes_block(n) == block) {
1071 sched_timestep_t ld;
1073 ld = latency(env, curr, 1, n, 0) + get_irn_delay(&be, n);
1074 d = ld > d ? ld : d;
1079 set_irn_delay(&be, curr, d);
1080 DB((be.dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
1082 /* set the etime of all nodes to 0 */
1083 set_irn_etime(&be, curr, 0);
1087 /* Then one can add all nodes are ready to the set. */
1088 foreach_out_edge(block, edge) {
1089 ir_node *irn = get_edge_src_irn(edge);
1091 /* Skip the end node because of keepalive edges. */
1092 if (get_irn_opcode(irn) == iro_End)
1096 /* Phi functions are scheduled immediately, since they only transfer
1097 * data flow from the predecessors to this block. */
1099 /* Increase the time step. */
1100 be.curr_time += get_irn_etime(&be, irn);
1101 add_to_sched(&be, irn);
1102 make_users_ready(&be, irn);
1104 else if (irn == start_node) {
1105 /* The start block will be scheduled as the first node */
1106 be.curr_time += get_irn_etime(&be, irn);
1108 add_to_sched(&be, irn);
1109 add_tuple_projs(&be, irn);
1112 /* Other nodes must have all operands in other blocks to be made
1116 /* Check, if the operands of a node are not local to this block */
1117 for (j = 0, m = get_irn_arity(irn); j < m; ++j) {
1118 ir_node *operand = get_irn_n(irn, j);
1120 if (get_nodes_block(operand) == block) {
1125 /* live in values increase register pressure */
1126 update_sched_liveness(&be, operand);
1130 /* Make the node ready, if all operands live in a foreign block */
1132 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
1133 make_ready(&be, NULL, irn);
1136 /* calculate number of users (needed for heuristic) */
1137 set_irn_num_user(&be, irn, get_num_successors(irn));
1139 /* calculate register difference (needed for heuristic) */
1140 set_irn_reg_diff(&be, irn, get_reg_difference(&be, irn));
1144 while (nodeset_count(be.cands) > 0) {
1145 nodeset *mcands; /**< the set of candidates with maximum delay time */
1146 nodeset *ecands; /**< the set of nodes in mcands whose etime <= curr_time */
1147 sched_timestep_t max_delay = 0;
1149 /* collect statistics about amount of ready nodes */
1150 be_do_stat_sched_ready(block, be.cands);
1152 /* calculate the max delay of all candidates */
1153 foreach_nodeset(be.cands, irn) {
1154 sched_timestep_t d = get_irn_delay(&be, irn);
1156 max_delay = d > max_delay ? d : max_delay;
1158 mcands = new_nodeset(8);
1159 ecands = new_nodeset(8);
1161 /* calculate mcands and ecands */
1162 foreach_nodeset(be.cands, irn) {
1163 if (be_is_Keep(irn)) {
1164 nodeset_break(be.cands);
1167 if (get_irn_delay(&be, irn) == max_delay) {
1168 nodeset_insert(mcands, irn);
1169 if (get_irn_etime(&be, irn) <= be.curr_time)
1170 nodeset_insert(ecands, irn);
1175 /* Keeps must be immediately scheduled */
1178 DB((be.dbg, LEVEL_2, "\tbe.curr_time = %u\n", be.curr_time));
1180 /* select a node to be scheduled and check if it was ready */
1181 if (nodeset_count(mcands) == 1) {
1182 irn = nodeset_first(mcands);
1183 DB((be.dbg, LEVEL_3, "\tirn = %+F, mcand = 1, max_delay = %u\n", irn, max_delay));
1186 int cnt = nodeset_count(ecands);
1188 irn = nodeset_first(ecands);
1190 if (arch_irn_class_is(env->arch_env, irn, branch)) {
1191 /* BEWARE: don't select a JUMP if others are still possible */
1194 DB((be.dbg, LEVEL_3, "\tirn = %+F, ecand = 1, max_delay = %u\n", irn, max_delay));
1197 DB((be.dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
1198 irn = select_node_heuristic(&be, ecands);
1202 DB((be.dbg, LEVEL_3, "\tmcand = %d\n", nodeset_count(mcands)));
1203 irn = select_node_heuristic(&be, mcands);
1207 del_nodeset(mcands);
1208 del_nodeset(ecands);
1210 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
1212 /* Increase the time step. */
1213 be.curr_time += exectime(env, irn);
1215 /* Add the node to the schedule. */
1216 add_to_sched(&be, irn);
1218 if (get_irn_mode(irn) == mode_T)
1219 add_tuple_projs(&be, irn);
1221 make_users_ready(&be, irn);
1223 /* remove the scheduled node from the ready list. */
1224 if (nodeset_find(be.cands, irn))
1225 nodeset_remove(be.cands, irn);
1228 if (selector->finish_block)
1229 selector->finish_block(be.selector_block_env);
1231 del_nodeset(be.cands);
1232 del_nodeset(be.live);
1235 static const list_sched_selector_t reg_pressure_selector_struct = {
1236 reg_pressure_graph_init,
1237 reg_pressure_block_init,
1238 reg_pressure_select,
1239 NULL, /* to_appear_in_schedule */
1240 NULL, /* exectime */
1242 reg_pressure_block_free,
1246 const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct;
1248 /* List schedule a graph. */
1249 void list_sched(const be_irg_t *birg, int enable_mris)
1251 const arch_env_t *arch_env = birg->main_env->arch_env;
1252 ir_graph *irg = birg->irg;
1258 /* Assure, that the out edges are computed */
1262 mris = be_sched_mris_preprocess(birg);
1264 num_nodes = get_irg_last_idx(irg);
1266 memset(&env, 0, sizeof(env));
1267 env.selector = arch_env->isa->impl->get_list_sched_selector(arch_env->isa);
1268 env.arch_env = arch_env;
1270 env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
1272 memset(env.sched_info, 0, num_nodes * sizeof(*env.sched_info));
1274 if (env.selector->init_graph)
1275 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
1277 /* Schedule each single block. */
1278 irg_block_walk_graph(irg, list_sched_block, NULL, &env);
1280 if (env.selector->finish_graph)
1281 env.selector->finish_graph(env.selector_env);
1284 be_sched_mris_free(mris);
1286 DEL_ARR_F(env.sched_info);