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"
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, void *data)
82 mris_irn_t *mi = data ? data : 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);
227 int highest_is_tuple = get_irn_mode(highest_node) == mode_T;
231 DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
233 /* count the number of all descendants which are not the lowest descendant */
234 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) {
247 op = get_irn_in_or_dep(lowest_desc, i);
248 cmp = highest_is_tuple ? skip_Projs(op) : op;
250 // if (cmp == highest_node)
251 if (op == highest_node)
255 assert(i < n && "could not find operand");
257 //replace_tuple_by_repr_proj(env, &in[1]);
258 if (!is_Proj(lowest_desc))
259 add_irn_dep(lowest_desc, in[1]);
261 obstack_free(&env->obst, in);
263 /* if the current lowest node is not yet in a lineage, add it to the current one. */
264 if (!lowest_mi->lineage_start) {
265 /* mark the current lowest node as the last one in the lineage. */
266 highest_mi->lineage_next = lowest_desc;
267 start_mi->lineage_end = lowest_desc;
269 lowest_mi->lineage_start = start;
270 ir_nodeset_remove(&nodes, lowest_desc);
273 /* else we cannot extend this lineage, so break. */
277 highest_node = lowest_desc;
278 highest_mi = lowest_mi;
280 /* recompute the descendants array and the new lowest descendant. */
281 in = all_descendants(env, highest_node);
282 lowest_desc = put_lowest_in_front(env, in);
285 /* recompute the heights if desired. */
286 if (recompute_height)
287 heights_recompute(env->heights);
290 ir_nodeset_destroy(&nodes);
293 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
297 ir_node *u_end = u->lineage_end;
298 ir_node *v_start = v->lineage_start;
299 ir_node *start = skip_Projs(v_start);
301 if (be_is_Keep(start))
304 /* set lineage end of nodes in u to end of v. */
305 irn = last = u->lineage_start;
306 mi = get_mris_irn(env, irn);
307 while (irn && irn != u_end) {
308 mi = get_mris_irn(env, irn);
309 mi->lineage_end = v->lineage_end;
311 irn = mi->lineage_next;
314 /* insert a CopyKeep to make lineage v dependent on u. */
315 if (get_irn_ins_or_deps(start) == 0)
318 if (get_irn_mode(last) == mode_T) {
319 const ir_edge_t *edge = get_irn_out_edge_first(last);
320 last = get_edge_src_irn(edge);
323 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
324 mi->lineage_next = v_start;
326 /* add a dependency from the first node in v's lineage to the last in u's */
327 add_irn_dep(u_end, v_start);
329 /* set lineage start of nodes in v to start of u. */
330 irn = v->lineage_start;
331 while (irn && irn != v->lineage_end) {
332 mris_irn_t *mi = get_mris_irn(env, irn);
333 mi->lineage_start = u->lineage_start;
334 irn = mi->lineage_next;
337 heights_recompute(env->heights);
339 mi = get_mris_irn(env, v_start);
340 list_del(&mi->lineage_list);
345 static void fuse_lineages(mris_env_t *env)
347 mris_irn_t *u, *v, *tmp1, *tmp2;
350 foreach_lineage(env, u, tmp1) {
351 foreach_lineage(env, v, tmp2) {
352 if (u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
353 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
354 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
355 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
358 if (fuse_two_lineages(env, u, v))
366 static mris_env_t *dump_env = NULL;
368 static void block_walker(ir_node *bl, void *data)
370 mris_env_t *env = data;
372 lineage_formation(env);
376 static int mris_edge_hook(FILE *F, ir_node *irn)
378 mris_irn_t *mi = get_mris_irn(dump_env, irn);
380 if (mi->lineage_next) {
381 fprintf(F, "edge:{sourcename:\"");
382 PRINT_NODEID(mi->lineage_next);
383 fprintf(F, "\" targetname:\"");
385 fprintf(F, "\" color:lilac}\n");
390 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix)
392 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
394 dump_consts_local(0);
395 set_dump_node_edge_hook(mris_edge_hook);
397 dump_ir_block_graph(env->irg, suffix);
398 set_dump_node_edge_hook(old);
401 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
403 mris_env_t *env = XMALLOC(mris_env_t);
404 ir_graph *irg = be_get_birg_irg(birg);
406 phase_init(&env->ph, irg, mris_irn_data_init);
409 env->heights = heights_new(irg);
410 INIT_LIST_HEAD(&env->lineage_head);
411 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
412 obstack_init(&env->obst);
413 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
414 irg_block_walk_graph(irg, block_walker, NULL, env);
415 obstack_free(&env->obst, NULL);
416 // dump_ir_block_graph_mris(env, "-mris");
420 void be_sched_mris_free(mris_env_t *env)
422 phase_deinit(&env->ph);
423 heights_free(env->heights);