2 * Scheduling algorithms.
3 * An ILP scheduler based on
4 * "ILP-based Instruction Scheduling for IA-64"
5 * by Daniel Kaestner and Sebastian Winkel
8 * @author Christian Wuerdig
18 #include "irphase_t.h"
26 typedef struct _ilpsched_node_attr_t {
29 unsigned visit_idx : 31;
30 unsigned enqueued : 1;
31 bitset_t *transitive_block_nodes;
32 } ilpsched_node_attr_t;
34 typedef struct _ilpsched_block_attr_t {
35 unsigned n_interesting_nodes;
36 ir_node *head_root_nodes;
37 } ilpsched_block_attr_t;
39 typedef union _ilpsched_attr_ {
40 ilpsched_node_attr_t node_attr;
41 ilpsched_block_attr_t block_attr;
53 DEBUG_ONLY(firm_dbg_module_t *dbg);
56 #define get_ilpsched_irn(ilpsched_env, irn) (phase_get_or_set_irn_data(&(ilpsched_env)->ph, (irn)))
57 #define is_ilpsched_block(node) (is_Block((node)->irn))
58 #define get_ilpsched_block_attr(block) (&(block)->attr.block_attr)
59 #define get_ilpsched_node_attr(node) (&(node)->attr.node_attr)
61 #define foreach_linked_irns(head, iter) for ((iter) = (head); (iter); (iter) = get_irn_link((iter)))
63 #define consider_for_sched(irn) \
64 (! (is_Block(irn) || is_Proj(irn) || is_Phi(irn) || be_is_Keep(irn) || is_NoMem(irn) || is_Jmp(irn)))
67 * In case there is no phase information for irn, initialize it.
69 static void *init_ilpsched_irn(phase_t *ph, ir_node *irn, void *old) {
70 be_ilpsched_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
73 /* if node has phase data and it's not a block: clear the bitset */
74 if (! is_Block(res->irn)) {
75 ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
76 bitset_clear_all(na->transitive_block_nodes);
85 ilpsched_block_attr_t *ba = get_ilpsched_block_attr(res);
87 ba->n_interesting_nodes = 0;
88 ba->head_root_nodes = NULL;
91 ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
97 na->transitive_block_nodes = bitset_irg_obstack_alloc(phase_obst(ph), phase_get_irg(ph));
104 * Add all nodes having no user in current block to last_nodes list.
106 static void collect_alap_root_nodes(ir_node *irn, void *walk_env) {
108 const ir_edge_t *edge;
109 be_ilpsched_env_t *env;
110 be_ilpsched_irn_t *block_node;
111 ilpsched_block_attr_t *ba;
112 int has_block_user = 0;
114 if (! consider_for_sched(irn))
117 block = get_nodes_block(irn);
119 foreach_out_edge(irn, edge) {
120 ir_node *user = get_edge_src_irn(edge);
123 const ir_edge_t *user_edge;
125 if (get_irn_mode(user) == mode_X)
128 /* The ABI ensures, that there will be no ProjT nodes in the graph. */
129 foreach_out_edge(user, user_edge) {
130 ir_node *real_user = get_edge_src_irn(user_edge);
132 if (! is_Phi(real_user) && get_nodes_block(real_user) == block) {
141 else if (is_Block(user)) {
144 else if (! is_Phi(user) && get_nodes_block(user) == block) {
151 block_node = get_ilpsched_irn(env, block);
152 ba = get_ilpsched_block_attr(block_node);
154 ba->n_interesting_nodes++;
156 /* current irn has no user inside this block */
157 if (! has_block_user) {
158 set_irn_link(irn, ba->head_root_nodes);
159 ba->head_root_nodes = irn;
164 * Calculate the ASAP scheduling step for current irn.
166 static void calculate_irn_asap(ir_node *irn, void *walk_env) {
167 be_ilpsched_irn_t *node;
168 be_ilpsched_env_t *env = walk_env;
172 ilpsched_node_attr_t *na;
174 /* These nodes are handled separate */
175 if (! consider_for_sched(irn))
178 DBG((env->dbg, LEVEL_1, "Calculating ASAP of node %+F\n", irn));
180 node = get_ilpsched_irn(env, irn);
181 block = get_nodes_block(irn);
182 idx = get_irn_idx(irn);
183 na = get_ilpsched_node_attr(node);
185 /* accumulate all transitive predecessors of current node */
186 for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
187 ir_node *pred = skip_Proj(get_irn_in_or_dep(irn, i));
188 be_ilpsched_irn_t *pred_node;
189 ilpsched_node_attr_t *pna;
191 if (be_is_Keep(pred))
192 pred = skip_Proj(get_irn_n(pred, 0));
194 if (is_Phi(pred) || block != get_nodes_block(pred) || is_NoMem(pred))
197 pred_node = get_ilpsched_irn(env, pred);
198 pna = get_ilpsched_node_attr(pred_node);
200 assert(pna->asap && "missing ASAP of predecessor");
203 We have not already visited this predecessor
204 -> accumulate it's predecessors
206 if (pna->visit_idx != idx) {
207 pna->visit_idx = idx;
208 na->transitive_block_nodes = bitset_or(na->transitive_block_nodes, pna->transitive_block_nodes);
209 DBG((env->dbg, LEVEL_1, "\taccumulating preds of %+F\n", pred));
213 /* every node is it's own transitive predecessor in block */
214 bitset_set(na->transitive_block_nodes, idx);
216 /* asap = number of transitive predecessors in this block */
217 na->asap = bitset_popcnt(na->transitive_block_nodes);
219 DBG((env->dbg, LEVEL_1, "\tcalculated ASAP is %u\n", na->asap));
223 * Accumulate the successors of all nodes from irn on upwards.
225 static void accumulate_succs(be_ilpsched_env_t *env, ir_node *irn) {
227 unsigned idx = get_irn_idx(irn);
228 be_ilpsched_irn_t *node = get_ilpsched_irn(env, irn);
229 ilpsched_node_attr_t *na = get_ilpsched_node_attr(node);
230 ir_node *block = get_nodes_block(irn);
231 waitq *wq = new_waitq();
233 DBG((env->dbg, LEVEL_1, "\taccumulating succs of %+F\n", irn));
235 /* enqueue node for final alap calculation */
236 if (! na->enqueued) {
237 be_ilpsched_irn_t *block_node = get_ilpsched_irn(env, block);
238 ilpsched_block_attr_t *ba = get_ilpsched_block_attr(block_node);
241 na->alap = ba->n_interesting_nodes;
242 waitq_put(env->alap_queue, node);
243 DBG((env->dbg, LEVEL_2, "\t\tenqueueing %+F for final ALAP calculation\n", irn));
246 for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
247 ir_node *pred = skip_Proj(get_irn_in_or_dep(irn, i));
248 be_ilpsched_irn_t *pred_node;
249 ilpsched_node_attr_t *pna;
251 if (be_is_Keep(pred))
252 pred = skip_Proj(get_irn_n(pred, 0));
254 if (is_Phi(pred) || block != get_nodes_block(pred) || is_NoMem(pred))
257 pred_node = get_ilpsched_irn(env, pred);
258 pna = get_ilpsched_node_attr(pred_node);
260 /* accumulate the successors */
261 if (pna->visit_idx != idx) {
262 pna->visit_idx = idx;
263 pna->transitive_block_nodes = bitset_or(pna->transitive_block_nodes, na->transitive_block_nodes);
265 /* set current node as successor */
266 bitset_set(pna->transitive_block_nodes, idx);
269 DBG((env->dbg, LEVEL_1, "\taccumulating succs of %+F to %+F\n", irn, pred));
273 /* process all predecessors */
274 while (! waitq_empty(wq)) {
275 accumulate_succs(env, waitq_get(wq));
280 * Calculate the ALAP scheduling step of all irns in current block.
281 * Depends on ASAP beeing calculated.
283 static void calculate_block_alap(ir_node *block, void *walk_env) {
284 be_ilpsched_env_t *env = walk_env;
285 be_ilpsched_irn_t *block_node = get_ilpsched_irn(env, block);
286 ilpsched_block_attr_t *ba = get_ilpsched_block_attr(block_node);
287 bitset_t *alap_bs = bitset_irg_alloca(env->irg);
290 assert(is_Block(block));
292 DBG((env->dbg, LEVEL_1, "Calculating ALAP for nodes in %+F (%u nodes)\n", block, ba->n_interesting_nodes));
294 phase_reinit_block_irn_data(&env->ph, block);
296 /* calculate the alap of all nodes, starting at collected roots upwards */
297 foreach_linked_irns(ba->head_root_nodes, root) {
298 accumulate_succs(env, root);
301 /* all interesting nodes should have their successors accumulated now */
302 while (! waitq_empty(env->alap_queue)) {
303 be_ilpsched_irn_t *node = waitq_get(env->alap_queue);
304 ilpsched_node_attr_t *na = get_ilpsched_node_attr(node);
306 na->alap -= bitset_popcnt(na->transitive_block_nodes);
307 DBG((env->dbg, LEVEL_1, "\tALAP of %+F is %u (%u succs)\n", node->irn, na->alap, bitset_popcnt(na->transitive_block_nodes)));
311 void be_ilp_sched(const be_irg_t *birg) {
312 be_ilpsched_env_t env;
314 FIRM_DBG_REGISTER(env.dbg, "firm.be.sched.ilp");
316 //firm_dbg_set_mask(env.dbg, 31);
319 env.alap_queue = new_waitq();
320 phase_init(&env.ph, "be ilp scheduling", env.irg, PHASE_DEFAULT_GROWTH, init_ilpsched_irn);
322 irg_walk_graph(env.irg, collect_alap_root_nodes, calculate_irn_asap, &env);
323 irg_block_walk_graph(env.irg, NULL, calculate_block_alap, &env);
325 del_waitq(env.alap_queue);