2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Scheduling utilities for nodes in Blocks and Blocks.
9 * @author Sebastian Hack
15 #include "firm_types.h"
16 #include "iredges_t.h"
25 #include "belistsched.h"
29 #include "lc_opts_enum.h"
32 #define SCHED_INITIAL_GRANULARITY (1 << 14)
34 static void sched_renumber(ir_node *const block)
37 sched_timestep_t step = SCHED_INITIAL_GRANULARITY;
39 sched_foreach(block, irn) {
40 inf = get_irn_sched_info(irn);
41 inf->time_step = step;
42 step += SCHED_INITIAL_GRANULARITY;
46 static inline void sched_set_time_stamp(const ir_node *irn)
48 sched_info_t *info = get_irn_sched_info(irn);
49 const sched_info_t *prev_info = get_irn_sched_info(info->prev);
50 const sched_info_t *next_info = get_irn_sched_info(info->next);
51 sched_timestep_t before_ts = prev_info->time_step;
52 sched_timestep_t after_ts = next_info->time_step;
55 * If we are the last, we can give us a big time step,
56 * else we have to compute our time step from our
59 if(before_ts >= after_ts) {
60 info->time_step = before_ts + SCHED_INITIAL_GRANULARITY;
62 if (info->time_step <= before_ts) {
63 sched_renumber(get_nodes_block(irn));
66 sched_timestep_t ts = (before_ts + after_ts) / 2;
69 * If the resolution went out, we have to renumber
72 if(ts == before_ts || ts == after_ts)
73 sched_renumber(get_nodes_block(irn));
79 void sched_add_before(ir_node *before, ir_node *irn)
81 sched_info_t *info = get_irn_sched_info(irn);
82 ir_node *next = before;
83 sched_info_t *next_info = get_irn_sched_info(next);
84 ir_node *prev = next_info->prev;
85 sched_info_t *prev_info = get_irn_sched_info(prev);
86 assert(sched_is_scheduled(before));
87 assert(!sched_is_scheduled(irn));
88 assert(!is_Proj(before));
89 assert(!is_Proj(irn));
93 prev_info->next = irn;
94 next_info->prev = irn;
95 sched_set_time_stamp(irn);
98 void sched_add_after(ir_node *after, ir_node *irn)
100 sched_info_t *info = get_irn_sched_info(irn);
101 ir_node *prev = after;
102 sched_info_t *prev_info = get_irn_sched_info(prev);
103 ir_node *next = prev_info->next;
104 sched_info_t *next_info = get_irn_sched_info(next);
105 assert(sched_is_scheduled(after));
106 assert(!sched_is_scheduled(irn));
107 assert(!is_Proj(after));
108 assert(!is_Proj(irn));
112 prev_info->next = irn;
113 next_info->prev = irn;
114 sched_set_time_stamp(irn);
117 void sched_remove(ir_node *irn)
119 sched_info_t *info = get_irn_sched_info(irn);
120 ir_node *prev = info->prev;
121 ir_node *next = info->next;
122 sched_info_t *prev_info = get_irn_sched_info(prev);
123 sched_info_t *next_info = get_irn_sched_info(next);
124 assert(sched_is_scheduled(irn));
126 prev_info->next = next;
127 next_info->prev = prev;
132 void sched_replace(ir_node *const old, ir_node *const irn)
134 assert(sched_is_scheduled(old));
135 assert(!sched_is_scheduled(irn));
137 sched_info_t *const old_info = get_irn_sched_info(old);
138 sched_info_t *const irn_info = get_irn_sched_info(irn);
139 *irn_info = *old_info;
141 old_info->prev = NULL;
142 old_info->next = NULL;
144 ir_node *const prev = irn_info->prev;
145 ir_node *const next = irn_info->next;
146 get_irn_sched_info(prev)->next = irn;
147 get_irn_sched_info(next)->prev = irn;
150 static be_module_list_entry_t *schedulers;
151 static schedule_func scheduler;
153 void be_register_scheduler(const char *name, schedule_func func)
155 if (scheduler == NULL)
157 be_add_module_to_list(&schedulers, name, (void*)func);
160 void be_schedule_graph(ir_graph *irg)
165 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched)
166 void be_init_sched(void)
168 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
169 be_add_module_list_opt(be_grp, "scheduler", "scheduling algorithm",
170 &schedulers, (void**)&scheduler);