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 critical_path_len; /**< The weighted length of the longest critical path */
54 unsigned already_sched : 1; /**< Set if this node is already scheduled */
55 unsigned is_root : 1; /**< is a root node of a block */
59 * Scheduling environment for the whole graph.
61 typedef struct _sched_env_t {
62 sched_irn_t *sched_info; /**< scheduling info per node */
63 const list_sched_selector_t *selector; /**< The node selector. */
64 const arch_env_t *arch_env; /**< The architecture environment. */
65 const ir_graph *irg; /**< The graph to schedule. */
66 void *selector_env; /**< A pointer to give to the selector. */
67 int sel_strategy; /**< Node selection strategy (muchnik, mueller, isa) */
72 * Ugly global variable for the compare function
73 * since qsort(3) does not pass an extra pointer.
75 static ir_node *curr_bl = NULL;
77 static int cmp_usage(const void *a, const void *b)
79 struct trivial_sched_env *env;
84 res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
87 * One of them is live at the end of the block.
88 * Then, that one shall be scheduled at after the other
99 * The trivial selector:
100 * Just assure that branches are executed last, otherwise select
101 * the first node ready.
103 static ir_node *trivial_select(void *block_env, nodeset *ready_set)
105 const arch_env_t *arch_env = block_env;
108 /* assure that branches and constants are executed last */
109 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
110 if (! arch_irn_class_is(arch_env, irn, branch)) {
111 nodeset_break(ready_set);
117 /* at last: schedule branches */
118 irn = nodeset_first(ready_set);
119 nodeset_break(ready_set);
124 static void *trivial_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
126 return (void *) arch_env;
129 static void *trivial_init_block(void *graph_env, ir_node *bl)
134 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
138 if(sel->to_appear_in_schedule)
139 res = sel->to_appear_in_schedule(block_env, irn);
141 return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_RegParams(irn));
144 static const list_sched_selector_t trivial_selector_struct = {
148 NULL, /* to_appear_in_schedule */
151 NULL, /* finish_block */
152 NULL /* finish_graph */
155 const list_sched_selector_t *trivial_selector = &trivial_selector_struct;
157 typedef struct _usage_stats_t {
159 struct _usage_stats_t *next;
161 int uses_in_block; /**< Number of uses inside the current block. */
162 int already_consumed; /**< Number of insns using this value already
167 const list_sched_selector_t *vtab;
168 const arch_env_t *arch_env;
169 } reg_pressure_main_env_t;
173 const reg_pressure_main_env_t *main_env;
175 nodeset *already_scheduled;
176 } reg_pressure_selector_env_t;
178 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
180 usage_stats_t *us = get_irn_link(irn);
183 us = obstack_alloc(&env->obst, sizeof(us[0]));
185 us->already_consumed = 0;
186 us->max_hops = INT_MAX;
187 us->next = env->root;
189 set_irn_link(irn, us);
195 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
197 usage_stats_t *us = get_irn_link(irn);
198 assert(us && "This node must have usage stats");
202 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
204 ir_node *bl = get_nodes_block(irn);
206 * If the reached node is not in the block desired,
207 * return the value passed for this situation.
209 if(get_nodes_block(irn) != bl)
210 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
213 * If the node is in the current block but not
214 * yet scheduled, we keep on searching from that node.
216 if(!nodeset_find(env->already_scheduled, irn)) {
219 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
220 ir_node *operand = get_irn_n(irn, i);
222 if(get_irn_visited(operand) < visited_nr) {
225 set_irn_visited(operand, visited_nr);
226 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
235 * If the node is in the current block and scheduled, return
236 * the depth which indicates the number of steps to the
237 * region of scheduled nodes.
242 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
244 ir_node *bl = get_nodes_block(irn);
245 ir_graph *irg = get_irn_irg(bl);
248 const ir_edge_t *edge;
250 foreach_out_edge(irn, edge) {
251 ir_node *user = get_edge_src_irn(edge);
252 unsigned visited_nr = get_irg_visited(irg) + 1;
255 set_irg_visited(irg, visited_nr);
256 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
257 res = MAX(res, max_hops);
263 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
265 reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
267 main_env->arch_env = arch_env;
268 main_env->vtab = vtab;
269 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
274 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
277 reg_pressure_selector_env_t *env = xmalloc(sizeof(env[0]));
279 obstack_init(&env->obst);
280 env->already_scheduled = new_nodeset(32);
282 env->main_env = graph_env;
285 * Collect usage statistics.
287 sched_foreach(bl, irn) {
288 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
291 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
292 //ir_node *op = get_irn_n(irn, i);
293 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
294 usage_stats_t *us = get_or_set_usage_stats(env, irn);
295 #if 0 /* Liveness is not computed here! */
296 if(is_live_end(bl, op))
297 us->uses_in_block = 99999;
309 static void reg_pressure_block_free(void *block_env)
311 reg_pressure_selector_env_t *env = block_env;
314 for(us = env->root; us; us = us->next)
315 set_irn_link(us->irn, NULL);
317 obstack_free(&env->obst, NULL);
318 del_nodeset(env->already_scheduled);
322 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
325 if(get_irn_mode(irn) == mode_T) {
326 const ir_edge_t *edge;
328 foreach_out_edge(irn, edge)
329 res += get_result_hops_sum(env, get_edge_src_irn(edge));
332 else if(mode_is_data(get_irn_mode(irn)))
333 res = compute_max_hops(env, irn);
339 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
344 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
345 ir_node *op = get_irn_n(irn, i);
347 if(must_appear_in_schedule(env->main_env->vtab, env, op))
348 sum += compute_max_hops(env, op);
351 sum += get_result_hops_sum(env, irn);
356 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set)
358 reg_pressure_selector_env_t *env = block_env;
359 ir_node *irn, *res = NULL;
360 int curr_cost = INT_MAX;
362 assert(nodeset_count(ready_set) > 0);
364 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
366 Ignore branch instructions for the time being.
367 They should only be scheduled if there is nothing else.
369 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
370 int costs = reg_pr_costs(env, irn);
371 if (costs <= curr_cost) {
379 There was no result so we only saw a branch.
384 res = nodeset_first(ready_set);
385 nodeset_break(ready_set);
387 assert(res && "There must be a node scheduled.");
390 nodeset_insert(env->already_scheduled, res);
395 * Environment for a block scheduler.
397 typedef struct _block_sched_env_t {
398 sched_irn_t *sched_info; /**< scheduling info per node, copied from the global scheduler object */
399 sched_timestep_t curr_time; /**< current time of the scheduler */
400 nodeset *cands; /**< the set of candidates */
401 ir_node *block; /**< the current block */
402 sched_env_t *sched_env; /**< the scheduler environment */
403 nodeset *live; /**< simple liveness during scheduling */
404 const list_sched_selector_t *selector;
405 void *selector_block_env;
406 DEBUG_ONLY(firm_dbg_module_t *dbg;)
410 * Returns non-zero if the node is already scheduled
412 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
414 int idx = get_irn_idx(n);
416 assert(idx < ARR_LEN(env->sched_info));
417 return env->sched_info[idx].already_sched;
421 * Mark a node as already scheduled
423 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
425 int idx = get_irn_idx(n);
427 assert(idx < ARR_LEN(env->sched_info));
428 env->sched_info[idx].already_sched = 1;
432 * Returns non-zero if the node is a root node
434 static INLINE unsigned is_root_node(block_sched_env_t *env, ir_node *n)
436 int idx = get_irn_idx(n);
438 assert(idx < ARR_LEN(env->sched_info));
439 return env->sched_info[idx].is_root;
443 * Mark a node as roto node
445 static INLINE void mark_root_node(block_sched_env_t *env, ir_node *n)
447 int idx = get_irn_idx(n);
449 assert(idx < ARR_LEN(env->sched_info));
450 env->sched_info[idx].is_root = 1;
454 * Get the current delay.
456 static INLINE sched_timestep_t get_irn_delay(block_sched_env_t *env, ir_node *n) {
457 int idx = get_irn_idx(n);
459 assert(idx < ARR_LEN(env->sched_info));
460 return env->sched_info[idx].delay;
464 * Set the current delay.
466 static INLINE void set_irn_delay(block_sched_env_t *env, ir_node *n, sched_timestep_t delay) {
467 int idx = get_irn_idx(n);
469 assert(idx < ARR_LEN(env->sched_info));
470 env->sched_info[idx].delay = delay;
474 * Get the current etime.
476 static INLINE sched_timestep_t get_irn_etime(block_sched_env_t *env, ir_node *n) {
477 int idx = get_irn_idx(n);
479 assert(idx < ARR_LEN(env->sched_info));
480 return env->sched_info[idx].etime;
484 * Set the current etime.
486 static INLINE void set_irn_etime(block_sched_env_t *env, ir_node *n, sched_timestep_t etime) {
487 int idx = get_irn_idx(n);
489 assert(idx < ARR_LEN(env->sched_info));
490 env->sched_info[idx].etime = etime;
494 * Get the number of users.
496 static INLINE unsigned get_irn_num_user(block_sched_env_t *env, ir_node *n) {
497 int idx = get_irn_idx(n);
499 assert(idx < ARR_LEN(env->sched_info));
500 return env->sched_info[idx].num_user;
504 * Set the number of users.
506 static INLINE void set_irn_num_user(block_sched_env_t *env, ir_node *n, unsigned num_user) {
507 int idx = get_irn_idx(n);
509 assert(idx < ARR_LEN(env->sched_info));
510 env->sched_info[idx].num_user = num_user;
514 * Get the register difference.
516 static INLINE int get_irn_reg_diff(block_sched_env_t *env, ir_node *n) {
517 int idx = get_irn_idx(n);
519 assert(idx < ARR_LEN(env->sched_info));
520 return env->sched_info[idx].reg_diff;
524 * Set the register difference.
526 static INLINE void set_irn_reg_diff(block_sched_env_t *env, ir_node *n, int reg_diff) {
527 int idx = get_irn_idx(n);
529 assert(idx < ARR_LEN(env->sched_info));
530 env->sched_info[idx].reg_diff = reg_diff;
534 * Get the pre-order position.
536 static INLINE int get_irn_preorder(block_sched_env_t *env, ir_node *n) {
537 int idx = get_irn_idx(n);
539 assert(idx < ARR_LEN(env->sched_info));
540 return env->sched_info[idx].preorder;
544 * Set the pre-order position.
546 static INLINE void set_irn_preorder(block_sched_env_t *env, ir_node *n, int pos) {
547 int idx = get_irn_idx(n);
549 assert(idx < ARR_LEN(env->sched_info));
550 env->sched_info[idx].preorder = pos;
554 * Get the pre-order position.
556 static INLINE unsigned get_irn_critical_path_len(block_sched_env_t *env, ir_node *n) {
557 int idx = get_irn_idx(n);
559 assert(idx < ARR_LEN(env->sched_info));
560 return env->sched_info[idx].critical_path_len;
564 * Set the pre-order position.
566 static INLINE void set_irn_critical_path_len(block_sched_env_t *env, ir_node *n, unsigned len) {
567 int idx = get_irn_idx(n);
569 assert(idx < ARR_LEN(env->sched_info));
570 env->sched_info[idx].critical_path_len = len;
574 * returns the exec-time for node n.
576 static sched_timestep_t exectime(sched_env_t *env, ir_node *n) {
577 if (be_is_Keep(n) || is_Proj(n))
579 if (env->selector->exectime)
580 return env->selector->exectime(env->selector_env, n);
585 * Calculates the latency for between two ops
587 static sched_timestep_t latency(sched_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
588 /* a Keep hides a root */
589 if (be_is_Keep(curr))
590 return exectime(env, pred);
592 /* Proj's are executed immediately */
596 /* predecessors Proj's must be skipped */
598 pred = get_Proj_pred(pred);
600 if (env->selector->latency)
601 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
606 * Try to put a node in the ready set.
607 * @param env The block scheduler environment.
608 * @param pred The previous scheduled node.
609 * @param irn The node to make ready.
610 * @return 1, if the node could be made ready, 0 else.
612 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
615 sched_timestep_t etime_p, etime;
617 /* Blocks cannot be scheduled. */
622 * Check, if the given ir node is in a different block as the
623 * currently scheduled one. If that is so, don't make the node ready.
625 if (env->block != get_nodes_block(irn))
628 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
629 ir_node *op = get_irn_n(irn, i);
631 /* if irn is an End we have keep-alives and op might be a block, skip that */
633 assert(get_irn_op(irn) == op_End);
637 /* If the operand is local to the scheduled block and not yet
638 * scheduled, this nodes cannot be made ready, so exit. */
639 if (!is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
643 nodeset_insert(env->cands, irn);
645 /* calculate the etime of this node */
646 etime = env->curr_time;
648 etime_p = get_irn_etime(env, pred);
649 etime += latency(env->sched_env, pred, 1, irn, 0);
651 etime = etime_p > etime ? etime_p : etime;
654 set_irn_etime(env, irn, etime);
656 DB((env->dbg, LEVEL_2, "\tmaking ready: %+F etime %u\n", irn, etime));
662 * Try, to make all users of a node ready.
663 * In fact, a usage node can only be made ready, if all its operands
664 * have already been scheduled yet. This is checked my make_ready().
665 * @param env The block schedule environment.
666 * @param irn The node, which usages (successors) are to be made ready.
668 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
670 const ir_edge_t *edge;
672 foreach_out_edge(irn, edge) {
673 ir_node *user = edge->src;
675 make_ready(env, irn, user);
680 * Returns the number of not yet schedules users.
682 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
683 int idx = get_irn_idx(n);
685 assert(idx < ARR_LEN(env->sched_info));
686 return env->sched_info[idx].num_not_sched_user;
690 * Sets the number of not yet schedules users.
692 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
693 int idx = get_irn_idx(n);
695 assert(idx < ARR_LEN(env->sched_info));
696 env->sched_info[idx].num_not_sched_user = num;
700 * Add @p num to the number of not yet schedules users and returns the result.
702 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
703 int idx = get_irn_idx(n);
705 assert(idx < ARR_LEN(env->sched_info));
706 env->sched_info[idx].num_not_sched_user += num;
707 return env->sched_info[idx].num_not_sched_user;
711 * Returns the number of users of a node having mode datab.
713 static int get_num_successors(ir_node *irn) {
715 const ir_edge_t *edge;
717 if (get_irn_mode(irn) == mode_T) {
718 /* for mode_T nodes: count the users of all Projs */
719 foreach_out_edge(irn, edge) {
720 ir_node *proj = get_edge_src_irn(edge);
721 ir_mode *mode = get_irn_mode(proj);
724 sum += get_num_successors(proj);
725 else if (mode_is_datab(mode))
726 sum += get_irn_n_edges(proj);
730 /* do not count keep-alive edges */
731 foreach_out_edge(irn, edge) {
732 if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
741 * Adds irn to @p live, updates all inputs that this user is scheduled
742 * and counts all of it's non scheduled users.
744 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
751 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
752 ir_node *in = get_irn_n(irn, i);
754 /* if in is a proj: update predecessor */
756 in = get_Proj_pred(in);
758 /* if in is still in the live set: reduce number of users by one */
759 if (nodeset_find(env->live, in)) {
760 if (add_irn_not_sched_user(env, in, -1) <= 0)
761 nodeset_remove(env->live, in);
766 get_num_successors returns the number of all users. This includes
767 users in different blocks as well. As the each block is scheduled separately
768 the liveness info of those users will not be updated and so these
769 users will keep up the register pressure as it is desired.
771 i = get_num_successors(irn);
773 set_irn_not_sched_user(env, irn, i);
774 nodeset_insert(env->live, irn);
779 * Returns the current register pressure for the current block
781 * This is the number of already scheduled nodes having not yet
784 static INLINE int get_cur_reg_pressure(block_sched_env_t *env) {
786 Nodes with all users scheduled are removed from live set,
787 so the number of nodes in this set represent the current
788 register pressure in this block.
790 return nodeset_count(env->live);
794 * Append an instruction to a schedule.
795 * @param env The block scheduling environment.
796 * @param irn The node to add to the schedule.
797 * @return The given node.
799 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
801 /* If the node consumes/produces data, it is appended to the schedule
802 * list, otherwise, it is not put into the list */
803 if(must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
804 sched_info_t *info = get_irn_sched_info(irn);
805 INIT_LIST_HEAD(&info->list);
807 update_sched_liveness(env, irn);
808 sched_add_before(env->block, irn);
810 DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
813 /* Insert the node in the set of all already scheduled nodes. */
814 mark_already_scheduled(env, irn);
816 /* Remove the node from the ready set */
817 if(nodeset_find(env->cands, irn))
818 nodeset_remove(env->cands, irn);
824 * Add the proj nodes of a tuple-mode irn to the schedule immediately
825 * after the tuple-moded irn. By pinning the projs after the irn, no
826 * other nodes can create a new lifetime between the tuple-moded irn and
827 * one of its projs. This should render a realistic image of a
828 * tuple-moded irn, which in fact models a node which defines multiple
831 * @param irn The tuple-moded irn.
833 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
835 const ir_edge_t *edge;
837 assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
842 foreach_out_edge(irn, edge) {
843 ir_node *out = edge->src;
845 assert(is_Proj(out) && "successor of a modeT node must be a proj");
847 if (get_irn_mode(out) == mode_T)
848 add_tuple_projs(env, out);
850 add_to_sched(env, out);
851 make_users_ready(env, out);
857 * Returns the difference of regs_output - regs_input;
859 static int get_reg_difference(block_sched_env_t *be, ir_node *irn) {
864 if (get_irn_mode(irn) == mode_T) {
865 /* mode_T nodes: num out regs == num Projs with mode datab */
866 const ir_edge_t *edge;
867 foreach_out_edge(irn, edge) {
868 ir_node *proj = get_edge_src_irn(edge);
869 if (mode_is_datab(get_irn_mode(proj)))
876 /* num in regs: number of ins with mode datab and not ignore */
877 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
878 ir_node *in = get_irn_n(irn, i);
879 if (mode_is_datab(get_irn_mode(in)) && ! arch_irn_is(be->sched_env->arch_env, in, ignore))
883 return num_out - num_in;
887 * Execute the heuristic function,
889 static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
891 ir_node *irn, *cand = NULL;
893 /* prefer instructions which can be scheduled early */
895 /* prefer instructions with lots of successors */
896 #define PRIO_NUMSUCCS 8
897 /* prefer instructions with long critical path */
898 #define PRIO_LEVEL 12
899 /* prefer instructions coming early in preorder */
900 #define PRIO_PREORD 8
901 /* weight of current register pressure */
902 #define PRIO_CUR_PRESS 20
903 /* weight of register pressure difference */
904 #define PRIO_CHG_PRESS 8
906 /* schedule keeps as early as possible */
907 foreach_nodeset(ns, irn) {
908 if (be_is_Keep(irn)) {
914 if (be->sched_env->sel_strategy & BE_SCHED_SELECT_HEUR) {
915 int max_prio = INT_MIN;
916 int cur_prio = INT_MIN;
917 int cur_pressure = get_cur_reg_pressure(be);
918 int reg_fact, cand_reg_fact;
920 /* priority based selection, heuristic inspired by mueller diss */
921 foreach_nodeset(ns, irn) {
922 /* make sure that branches are scheduled last */
923 if (! arch_irn_class_is(be->sched_env->arch_env, irn, branch)) {
924 int rdiff = get_irn_reg_diff(be, irn);
925 int sign = rdiff < 0;
926 int chg = (rdiff < 0 ? -rdiff : rdiff) << PRIO_CHG_PRESS;
928 reg_fact = chg << cur_pressure;
930 reg_fact = INT_MAX - 2;
931 reg_fact = sign ? -reg_fact : reg_fact;
933 cur_prio = (get_irn_critical_path_len(be, irn) << PRIO_LEVEL)
934 //- (get_irn_delay(be, irn) << PRIO_LEVEL)
935 + (get_irn_num_user(be, irn) << PRIO_NUMSUCCS)
936 - (get_irn_etime(be, irn) << PRIO_TIME)
937 // - ((get_irn_reg_diff(be, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
939 + (get_irn_preorder(be, irn) << PRIO_PREORD); /* high preorder means early schedule */
940 if (cur_prio > max_prio) {
943 cand_reg_fact = reg_fact;
946 DBG((be->dbg, LEVEL_4, "checked NODE %+F\n", irn));
947 DBG((be->dbg, LEVEL_4, "\tpriority: %d\n", cur_prio));
948 DBG((be->dbg, LEVEL_4, "\tpath len: %d (%d)\n", get_irn_critical_path_len(be, irn), get_irn_critical_path_len(be, irn) << PRIO_LEVEL));
949 DBG((be->dbg, LEVEL_4, "\tdelay: %d (%d)\n", get_irn_delay(be, irn), get_irn_delay(be, irn) << PRIO_LEVEL));
950 DBG((be->dbg, LEVEL_4, "\t#user: %d (%d)\n", get_irn_num_user(be, irn), get_irn_num_user(be, irn) << PRIO_NUMSUCCS));
951 DBG((be->dbg, LEVEL_4, "\tetime: %d (%d)\n", get_irn_etime(be, irn), -(get_irn_etime(be, irn) << PRIO_TIME)));
952 DBG((be->dbg, LEVEL_4, "\tpreorder: %d (%d)\n", get_irn_preorder(be, irn), get_irn_preorder(be, irn) << PRIO_PREORD));
953 DBG((be->dbg, LEVEL_4, "\treg diff: %d (%d)\n", get_irn_reg_diff(be, irn), -cand_reg_fact));
954 DBG((be->dbg, LEVEL_4, "\tpressure: %d\n", cur_pressure));
959 DBG((be->dbg, LEVEL_4, "heuristic selected %+F:\n", cand));
962 cand = nodeset_first(ns);
966 /* use backend selector */
967 cand = be->selector->select(be->selector_block_env, ns);
974 * Returns non-zero if root is a root in the block block.
976 static int is_root(ir_node *root, ir_node *block) {
977 const ir_edge_t *edge;
979 foreach_out_edge(root, edge) {
980 ir_node *succ = get_edge_src_irn(edge);
984 /* Phi nodes are always in "another block */
987 if (get_nodes_block(succ) == block)
993 /* we need a special mark */
997 static firm_dbg_module_t *xxxdbg;
1000 * descent into a dag and create a pre-order list.
1002 static void descent(ir_node *root, ir_node *block, ir_node **list, block_sched_env_t *env, unsigned path_len) {
1005 if (! is_Phi(root)) {
1006 path_len += exectime(env->sched_env, root);
1007 if (get_irn_critical_path_len(env, root) < path_len) {
1008 set_irn_critical_path_len(env, root, path_len);
1011 /* Phi nodes always leave the block */
1012 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
1013 ir_node *pred = get_irn_n(root, i);
1015 DBG((xxxdbg, LEVEL_3, " node %+F\n", pred));
1016 /* Blocks may happen as predecessors of End nodes */
1020 /* already seen nodes are not marked */
1021 if (get_irn_link(pred) != MARK)
1024 /* don't leave our block */
1025 if (get_nodes_block(pred) != block)
1028 set_irn_link(pred, NULL);
1030 descent(pred, block, list, env, path_len);
1033 set_irn_link(root, *list);
1038 * Perform list scheduling on a block.
1040 * Note, that the caller must compute a linked list of nodes in the block
1041 * using the link field before calling this function.
1043 * Also the outs must have been computed.
1045 * @param block The block node.
1046 * @param env Scheduling environment.
1048 static void list_sched_block(ir_node *block, void *env_ptr)
1050 sched_env_t *env = env_ptr;
1051 const list_sched_selector_t *selector = env->selector;
1052 ir_node *start_node = get_irg_start(get_irn_irg(block));
1053 sched_info_t *info = get_irn_sched_info(block);
1055 block_sched_env_t be;
1056 const ir_edge_t *edge;
1060 ir_node *root = NULL, *preord = NULL;
1063 /* Initialize the block's list head that will hold the schedule. */
1064 INIT_LIST_HEAD(&info->list);
1066 /* Initialize the block scheduling environment */
1067 be.sched_info = env->sched_info;
1070 be.cands = new_nodeset(get_irn_n_edges(block));
1071 be.live = new_nodeset(get_irn_n_edges(block));
1072 be.selector = selector;
1074 FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
1075 FIRM_DBG_REGISTER(xxxdbg, "firm.be.sched");
1077 // firm_dbg_set_mask(be.dbg, SET_LEVEL_3);
1079 if (selector->init_block)
1080 be.selector_block_env = selector->init_block(env->selector_env, block);
1082 DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
1084 /* First step: Find the root set. */
1085 foreach_out_edge(block, edge) {
1086 ir_node *succ = get_edge_src_irn(edge);
1088 if (is_root(succ, block)) {
1089 mark_root_node(&be, succ);
1090 set_irn_link(succ, root);
1094 set_irn_link(succ, MARK);
1097 /* Second step: calculate the pre-order list. */
1099 for (curr = root; curr; curr = irn) {
1100 irn = get_irn_link(curr);
1101 DBG((be.dbg, LEVEL_2, " DAG root %+F\n", curr));
1102 descent(curr, block, &preord, &be, 0);
1106 /* Third step: calculate the Delay. Note that our
1107 * list is now in pre-order, starting at root
1109 for (cur_pos = 0, curr = root; curr; curr = get_irn_link(curr), cur_pos++) {
1112 if (arch_irn_class_is(env->arch_env, curr, branch)) {
1113 /* assure, that branches can be executed last */
1117 if (is_root_node(&be, curr))
1118 d = exectime(env, curr);
1121 foreach_out_edge(curr, edge) {
1122 ir_node *n = get_edge_src_irn(edge);
1124 if (get_nodes_block(n) == block) {
1125 sched_timestep_t ld;
1127 ld = latency(env, curr, 1, n, 0) + get_irn_delay(&be, n);
1128 d = ld > d ? ld : d;
1133 set_irn_delay(&be, curr, d);
1134 DB((be.dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
1136 /* set the etime of all nodes to 0 */
1137 set_irn_etime(&be, curr, 0);
1139 set_irn_preorder(&be, curr, cur_pos);
1143 /* Then one can add all nodes are ready to the set. */
1144 foreach_out_edge(block, edge) {
1145 ir_node *irn = get_edge_src_irn(edge);
1147 /* Skip the end node because of keepalive edges. */
1148 if (get_irn_opcode(irn) == iro_End)
1152 /* Phi functions are scheduled immediately, since they only transfer
1153 * data flow from the predecessors to this block. */
1155 /* Increase the time step. */
1156 be.curr_time += get_irn_etime(&be, irn);
1157 add_to_sched(&be, irn);
1158 make_users_ready(&be, irn);
1160 else if (irn == start_node) {
1161 /* The start block will be scheduled as the first node */
1162 be.curr_time += get_irn_etime(&be, irn);
1164 add_to_sched(&be, irn);
1165 add_tuple_projs(&be, irn);
1168 /* Other nodes must have all operands in other blocks to be made
1172 /* Check, if the operands of a node are not local to this block */
1173 for (j = 0, m = get_irn_arity(irn); j < m; ++j) {
1174 ir_node *operand = get_irn_n(irn, j);
1176 if (get_nodes_block(operand) == block) {
1181 /* live in values increase register pressure */
1182 update_sched_liveness(&be, operand);
1186 /* Make the node ready, if all operands live in a foreign block */
1188 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
1189 make_ready(&be, NULL, irn);
1192 /* calculate number of users (needed for heuristic) */
1193 set_irn_num_user(&be, irn, get_num_successors(irn));
1195 /* calculate register difference (needed for heuristic) */
1196 set_irn_reg_diff(&be, irn, get_reg_difference(&be, irn));
1200 while (nodeset_count(be.cands) > 0) {
1201 nodeset *mcands; /**< the set of candidates with maximum delay time */
1202 nodeset *ecands; /**< the set of nodes in mcands whose etime <= curr_time */
1203 nodeset *local_cands;
1204 sched_timestep_t max_delay = 0;
1206 /* collect statistics about amount of ready nodes */
1207 be_do_stat_sched_ready(block, be.cands);
1209 /* calculate the max delay of all candidates */
1210 foreach_nodeset(be.cands, irn) {
1211 sched_timestep_t d = get_irn_delay(&be, irn);
1213 max_delay = d > max_delay ? d : max_delay;
1216 if (be.sched_env->sel_strategy & BE_SCHED_SELECT_MUCHNIK) {
1217 mcands = new_nodeset(8);
1218 ecands = new_nodeset(8);
1221 local_cands = new_nodeset(8);
1224 /* calculate mcands and ecands */
1225 foreach_nodeset(be.cands, irn) {
1226 if (be_is_Keep(irn)) {
1227 nodeset_break(be.cands);
1230 if (be.sched_env->sel_strategy & BE_SCHED_SELECT_MUCHNIK) {
1231 if (get_irn_delay(&be, irn) == max_delay) {
1232 nodeset_insert(mcands, irn);
1233 if (get_irn_etime(&be, irn) <= be.curr_time)
1234 nodeset_insert(ecands, irn);
1238 nodeset_insert(local_cands, irn);
1243 /* Keeps must be immediately scheduled */
1246 DB((be.dbg, LEVEL_2, "\tbe.curr_time = %u\n", be.curr_time));
1248 /* select a node to be scheduled and check if it was ready */
1249 if (! (be.sched_env->sel_strategy & BE_SCHED_SELECT_MUCHNIK)) {
1250 DB((be.dbg, LEVEL_3, "\tlocal_cands = %d\n", nodeset_count(local_cands)));
1251 irn = select_node_heuristic(&be, local_cands);
1253 else if (nodeset_count(mcands) == 1) {
1254 irn = nodeset_first(mcands);
1255 DB((be.dbg, LEVEL_3, "\tirn = %+F, mcand = 1, max_delay = %u\n", irn, max_delay));
1258 int cnt = nodeset_count(ecands);
1260 irn = nodeset_first(ecands);
1262 if (arch_irn_class_is(env->arch_env, irn, branch)) {
1263 /* BEWARE: don't select a JUMP if others are still possible */
1266 DB((be.dbg, LEVEL_3, "\tirn = %+F, ecand = 1, max_delay = %u\n", irn, max_delay));
1269 DB((be.dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
1270 irn = select_node_heuristic(&be, ecands);
1274 DB((be.dbg, LEVEL_3, "\tmcand = %d\n", nodeset_count(mcands)));
1275 irn = select_node_heuristic(&be, mcands);
1280 if (be.sched_env->sel_strategy & BE_SCHED_SELECT_MUCHNIK) {
1281 del_nodeset(mcands);
1282 del_nodeset(ecands);
1285 del_nodeset(local_cands);
1288 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
1290 /* Increase the time step. */
1291 be.curr_time += exectime(env, irn);
1293 /* Add the node to the schedule. */
1294 add_to_sched(&be, irn);
1296 if (get_irn_mode(irn) == mode_T)
1297 add_tuple_projs(&be, irn);
1299 make_users_ready(&be, irn);
1301 /* remove the scheduled node from the ready list. */
1302 if (nodeset_find(be.cands, irn))
1303 nodeset_remove(be.cands, irn);
1306 if (selector->finish_block)
1307 selector->finish_block(be.selector_block_env);
1309 del_nodeset(be.cands);
1310 del_nodeset(be.live);
1313 static const list_sched_selector_t reg_pressure_selector_struct = {
1314 reg_pressure_graph_init,
1315 reg_pressure_block_init,
1316 reg_pressure_select,
1317 NULL, /* to_appear_in_schedule */
1318 NULL, /* exectime */
1320 reg_pressure_block_free,
1324 const list_sched_selector_t *reg_pressure_selector = ®_pressure_selector_struct;
1326 /* List schedule a graph. */
1327 void list_sched(const be_irg_t *birg, be_options_t *be_opts)
1329 const arch_env_t *arch_env = birg->main_env->arch_env;
1330 ir_graph *irg = birg->irg;
1336 /* Assure, that the out edges are computed */
1340 mris = be_sched_mris_preprocess(birg);
1342 num_nodes = get_irg_last_idx(irg);
1344 memset(&env, 0, sizeof(env));
1345 env.selector = arch_env->isa->impl->get_list_sched_selector(arch_env->isa);
1346 env.arch_env = arch_env;
1348 env.sel_strategy = be_opts->sched_select;
1349 env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
1351 memset(env.sched_info, 0, num_nodes * sizeof(*env.sched_info));
1353 if (env.selector->init_graph)
1354 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
1356 /* Schedule each single block. */
1357 irg_block_walk_graph(irg, list_sched_block, NULL, &env);
1359 if (env.selector->finish_graph)
1360 env.selector->finish_graph(env.selector_env);
1363 be_sched_mris_free(mris);
1365 DEL_ARR_F(env.sched_info);