2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Implements a list scheduler for the MRIS algorithm.
23 * @author Sebastian Hack
27 * Implements a list scheduler for the MRIS algorithm in:
28 * Govindarajan, Yang, Amaral, Zhang, Gao
29 * Minimum Register Instruction Sequencing to Reduce Register Spills
30 * in out-of-order issue superscalar architectures
39 #include "irgraph_t.h"
41 #include "iredges_t.h"
43 #include "irphase_t.h"
48 #include "irnodeset.h"
53 #include "beschedmris.h"
58 ir_heights_t *heights;
62 struct list_head lineage_head;
64 DEBUG_ONLY(firm_dbg_module_t *dbg;)
67 typedef struct mris_irn_t {
69 ir_node *lineage_start;
70 ir_node *lineage_next;
72 struct list_head lineage_list;
75 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
77 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
78 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
80 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn)
82 mris_irn_t *mi = phase_alloc(ph, sizeof(mi[0]));
84 memset(mi, 0, sizeof(mi[0]));
85 INIT_LIST_HEAD(&mi->lineage_list);
89 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
91 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
93 const ir_edge_t *edge;
95 // assert(get_irn_mode(irn) != mode_T);
97 foreach_out_edge(irn, edge) {
98 ir_node *desc = get_edge_src_irn(edge);
99 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
100 obstack_ptr_grow(&env->obst, desc);
101 bitset_add_irn(visited, desc);
105 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
106 ir_node *desc = get_edge_src_irn(edge);
107 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
108 obstack_ptr_grow(&env->obst, desc);
109 bitset_add_irn(visited, desc);
114 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
116 bitset_t *visited = bitset_irg_malloc(env->irg);
118 grow_all_descendands(env, irn, visited);
121 if (get_irn_mode(irn) == mode_T) {
122 const ir_edge_t *edge;
123 foreach_out_edge(irn, edge) {
124 ir_node *desc = get_edge_src_irn(edge);
125 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
126 grow_all_descendands(env, desc, visited);
131 grow_all_descendands(env, irn, visited);
133 bitset_free(visited);
134 obstack_ptr_grow(&env->obst, NULL);
135 return obstack_finish(&env->obst);
138 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
140 int lowest_index = 0;
141 unsigned lowest_height = INT_MAX;
144 for (i = 0; in[i]; ++i) {
145 unsigned height = get_irn_height(env->heights, in[i]);
146 if (height < lowest_height) {
147 lowest_height = height;
153 ir_node *tmp = in[0];
154 in[0] = in[lowest_index];
155 in[lowest_index] = tmp;
161 static inline ir_node *skip_Projs(ir_node *irn)
163 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
166 static void lineage_formation(mris_env_t *env)
168 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
170 const ir_edge_t *edge;
172 ir_nodeset_init(&nodes);
174 foreach_out_edge(env->bl, edge) {
175 ir_node *irn = get_edge_src_irn(edge);
176 if (to_appear(env, irn))
177 ir_nodeset_insert(&nodes, irn);
180 while (ir_nodeset_size(&nodes) > 0) {
183 ir_node *highest_node = NULL;
184 ir_node *lowest_desc = NULL;
186 mris_irn_t *start_mi;
187 ir_nodeset_iterator_t iter;
190 int recompute_height = 0;
191 unsigned curr_height = 0;
193 /* search the highest node which is not yet in a lineage. */
194 foreach_ir_nodeset(&nodes, irn, iter) {
195 unsigned height = get_irn_height(env->heights, irn);
196 if (height > curr_height) {
198 curr_height = height;
202 assert(highest_node);
203 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
205 start = highest_node;
206 mi = start_mi = get_mris_irn(env, highest_node);
208 /* start a lineage beginning with highest_node. */
209 mi->lineage_start = highest_node;
210 mi->lineage_next = NULL;
211 mi->lineage_end = NULL;
212 list_add(&mi->lineage_list, &env->lineage_head);
213 ir_nodeset_remove(&nodes, highest_node);
216 put all descendants in an array.
217 we also move the lowest descendant in front, so that the other nodes
218 are easily accessible as an array, too.
220 in = all_descendants(env, highest_node);
221 lowest_desc = put_lowest_in_front(env, in);
223 /* as long as the current highest node has still descendants */
224 while (lowest_desc) {
225 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
226 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
230 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
232 /* count the number of all descendants which are not the lowest descendant */
233 for (n_desc = 0; in[n_desc]; ++n_desc) {
237 we insert a CopyKeep node to express the artificial dependencies from the lowest
238 descendant to all other descendants.
240 if (n_desc > 1 && !be_is_Keep(lowest_desc)) {
244 for (i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
245 op = get_irn_in_or_dep(lowest_desc, i);
246 if (op == highest_node)
250 assert(i < n && "could not find operand");
252 //replace_tuple_by_repr_proj(env, &in[1]);
253 if (!is_Proj(lowest_desc))
254 add_irn_dep(lowest_desc, in[1]);
256 obstack_free(&env->obst, in);
258 /* if the current lowest node is not yet in a lineage, add it to the current one. */
259 if (!lowest_mi->lineage_start) {
260 /* mark the current lowest node as the last one in the lineage. */
261 highest_mi->lineage_next = lowest_desc;
262 start_mi->lineage_end = lowest_desc;
264 lowest_mi->lineage_start = start;
265 ir_nodeset_remove(&nodes, lowest_desc);
268 /* else we cannot extend this lineage, so break. */
272 highest_node = lowest_desc;
273 highest_mi = lowest_mi;
275 /* recompute the descendants array and the new lowest descendant. */
276 in = all_descendants(env, highest_node);
277 lowest_desc = put_lowest_in_front(env, in);
280 /* recompute the heights if desired. */
281 if (recompute_height)
282 heights_recompute(env->heights);
285 ir_nodeset_destroy(&nodes);
288 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
292 ir_node *u_end = u->lineage_end;
293 ir_node *v_start = v->lineage_start;
294 ir_node *start = skip_Projs(v_start);
296 if (be_is_Keep(start))
299 /* set lineage end of nodes in u to end of v. */
300 irn = last = u->lineage_start;
301 mi = get_mris_irn(env, irn);
302 while (irn && irn != u_end) {
303 mi = get_mris_irn(env, irn);
304 mi->lineage_end = v->lineage_end;
306 irn = mi->lineage_next;
309 /* insert a CopyKeep to make lineage v dependent on u. */
310 if (get_irn_ins_or_deps(start) == 0)
313 if (get_irn_mode(last) == mode_T) {
314 const ir_edge_t *edge = get_irn_out_edge_first(last);
315 last = get_edge_src_irn(edge);
318 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
319 mi->lineage_next = v_start;
321 /* add a dependency from the first node in v's lineage to the last in u's */
322 add_irn_dep(u_end, v_start);
324 /* set lineage start of nodes in v to start of u. */
325 irn = v->lineage_start;
326 while (irn && irn != v->lineage_end) {
327 mris_irn_t *mi = get_mris_irn(env, irn);
328 mi->lineage_start = u->lineage_start;
329 irn = mi->lineage_next;
332 heights_recompute(env->heights);
334 mi = get_mris_irn(env, v_start);
335 list_del(&mi->lineage_list);
340 static void fuse_lineages(mris_env_t *env)
342 mris_irn_t *u, *v, *tmp1, *tmp2;
345 foreach_lineage(env, u, tmp1) {
346 foreach_lineage(env, v, tmp2) {
347 if (u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
348 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
349 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
350 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
353 if (fuse_two_lineages(env, u, v))
361 static mris_env_t *dump_env = NULL;
363 static void block_walker(ir_node *bl, void *data)
365 mris_env_t *env = data;
367 lineage_formation(env);
371 static void mris_edge_hook(FILE *F, ir_node *irn)
373 mris_irn_t *mi = get_mris_irn(dump_env, irn);
375 if (mi->lineage_next) {
376 fprintf(F, "edge:{sourcename:\"");
377 PRINT_NODEID(mi->lineage_next);
378 fprintf(F, "\" targetname:\"");
380 fprintf(F, "\" color:lilac}\n");
384 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix)
386 dump_node_edge_func old = get_dump_node_edge_hook();
388 set_dump_node_edge_hook(mris_edge_hook);
390 dump_ir_graph(env->irg, suffix);
391 set_dump_node_edge_hook(old);
394 mris_env_t *be_sched_mris_preprocess(ir_graph *irg)
396 mris_env_t *env = XMALLOC(mris_env_t);
398 phase_init(&env->ph, irg, mris_irn_data_init);
401 env->heights = heights_new(irg);
402 INIT_LIST_HEAD(&env->lineage_head);
403 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
404 obstack_init(&env->obst);
405 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
406 irg_block_walk_graph(irg, block_walker, NULL, env);
407 obstack_free(&env->obst, NULL);
408 // dump_ir_block_graph_mris(env, "-mris");
412 void be_sched_mris_free(mris_env_t *env)
414 phase_deinit(&env->ph);
415 heights_free(env->heights);