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"
55 #include "belistsched.h"
59 ir_heights_t *heights;
63 struct list_head lineage_head;
65 DEBUG_ONLY(firm_dbg_module_t *dbg;)
68 typedef struct mris_irn_t {
70 ir_node *lineage_start;
71 ir_node *lineage_next;
73 struct list_head lineage_list;
76 #define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)
78 #define get_mris_irn(env, irn) ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
79 #define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)
81 static void *mris_irn_data_init(ir_phase *ph, const ir_node *irn)
83 mris_irn_t *mi = (mris_irn_t*)phase_alloc(ph, sizeof(mi[0]));
85 memset(mi, 0, sizeof(mi[0]));
86 INIT_LIST_HEAD(&mi->lineage_list);
90 #define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
92 static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
94 const ir_edge_t *edge;
96 // assert(get_irn_mode(irn) != mode_T);
98 foreach_out_edge(irn, edge) {
99 ir_node *desc = get_edge_src_irn(edge);
100 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
101 obstack_ptr_grow(&env->obst, desc);
102 bitset_add_irn(visited, desc);
106 foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
107 ir_node *desc = get_edge_src_irn(edge);
108 if (valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
109 obstack_ptr_grow(&env->obst, desc);
110 bitset_add_irn(visited, desc);
115 static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
117 bitset_t *visited = bitset_irg_malloc(env->irg);
119 grow_all_descendands(env, irn, visited);
122 if (get_irn_mode(irn) == mode_T) {
123 const ir_edge_t *edge;
124 foreach_out_edge(irn, edge) {
125 ir_node *desc = get_edge_src_irn(edge);
126 assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
127 grow_all_descendands(env, desc, visited);
132 grow_all_descendands(env, irn, visited);
134 bitset_free(visited);
135 obstack_ptr_grow(&env->obst, NULL);
136 return (ir_node**)obstack_finish(&env->obst);
139 static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
141 int lowest_index = 0;
142 unsigned lowest_height = INT_MAX;
145 for (i = 0; in[i]; ++i) {
146 unsigned height = get_irn_height(env->heights, in[i]);
147 if (height < lowest_height) {
148 lowest_height = height;
154 ir_node *tmp = in[0];
155 in[0] = in[lowest_index];
156 in[lowest_index] = tmp;
162 static inline ir_node *skip_Projs(ir_node *irn)
164 return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
167 static void lineage_formation(mris_env_t *env)
169 DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
171 const ir_edge_t *edge;
173 ir_nodeset_init(&nodes);
175 foreach_out_edge(env->bl, edge) {
176 ir_node *irn = get_edge_src_irn(edge);
177 if (to_appear(env, irn))
178 ir_nodeset_insert(&nodes, irn);
181 while (ir_nodeset_size(&nodes) > 0) {
184 ir_node *highest_node = NULL;
185 ir_node *lowest_desc = NULL;
187 mris_irn_t *start_mi;
188 ir_nodeset_iterator_t iter;
191 int recompute_height = 0;
192 unsigned curr_height = 0;
194 /* search the highest node which is not yet in a lineage. */
195 foreach_ir_nodeset(&nodes, irn, iter) {
196 unsigned height = get_irn_height(env->heights, irn);
197 if (height > curr_height) {
199 curr_height = height;
203 assert(highest_node);
204 DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
206 start = highest_node;
207 mi = start_mi = get_mris_irn(env, highest_node);
209 /* start a lineage beginning with highest_node. */
210 mi->lineage_start = highest_node;
211 mi->lineage_next = NULL;
212 mi->lineage_end = NULL;
213 list_add(&mi->lineage_list, &env->lineage_head);
214 ir_nodeset_remove(&nodes, highest_node);
217 put all descendants in an array.
218 we also move the lowest descendant in front, so that the other nodes
219 are easily accessible as an array, too.
221 in = all_descendants(env, highest_node);
222 lowest_desc = put_lowest_in_front(env, in);
224 /* as long as the current highest node has still descendants */
225 while (lowest_desc) {
226 mris_irn_t *lowest_mi = get_mris_irn(env, lowest_desc);
227 mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
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) {
238 we insert a CopyKeep node to express the artificial dependencies from the lowest
239 descendant to all other descendants.
241 if (n_desc > 1 && !be_is_Keep(lowest_desc)) {
245 for (i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
246 op = get_irn_in_or_dep(lowest_desc, i);
247 if (op == highest_node)
251 assert(i < n && "could not find operand");
253 //replace_tuple_by_repr_proj(env, &in[1]);
254 if (!is_Proj(lowest_desc))
255 add_irn_dep(lowest_desc, in[1]);
257 obstack_free(&env->obst, in);
259 /* if the current lowest node is not yet in a lineage, add it to the current one. */
260 if (!lowest_mi->lineage_start) {
261 /* mark the current lowest node as the last one in the lineage. */
262 highest_mi->lineage_next = lowest_desc;
263 start_mi->lineage_end = lowest_desc;
265 lowest_mi->lineage_start = start;
266 ir_nodeset_remove(&nodes, lowest_desc);
269 /* else we cannot extend this lineage, so break. */
273 highest_node = lowest_desc;
274 highest_mi = lowest_mi;
276 /* recompute the descendants array and the new lowest descendant. */
277 in = all_descendants(env, highest_node);
278 lowest_desc = put_lowest_in_front(env, in);
281 /* recompute the heights if desired. */
282 if (recompute_height)
283 heights_recompute(env->heights);
286 ir_nodeset_destroy(&nodes);
289 static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
293 ir_node *u_end = u->lineage_end;
294 ir_node *v_start = v->lineage_start;
295 ir_node *start = skip_Projs(v_start);
297 if (be_is_Keep(start))
300 /* set lineage end of nodes in u to end of v. */
301 irn = last = u->lineage_start;
302 mi = get_mris_irn(env, irn);
303 while (irn && irn != u_end) {
304 mi = get_mris_irn(env, irn);
305 mi->lineage_end = v->lineage_end;
307 irn = mi->lineage_next;
310 /* insert a CopyKeep to make lineage v dependent on u. */
311 if (get_irn_ins_or_deps(start) == 0)
314 if (get_irn_mode(last) == mode_T) {
315 const ir_edge_t *edge = get_irn_out_edge_first(last);
316 last = get_edge_src_irn(edge);
319 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
320 mi->lineage_next = v_start;
322 /* add a dependency from the first node in v's lineage to the last in u's */
323 add_irn_dep(u_end, v_start);
325 /* set lineage start of nodes in v to start of u. */
326 irn = v->lineage_start;
327 while (irn && irn != v->lineage_end) {
328 mris_irn_t *mi = get_mris_irn(env, irn);
329 mi->lineage_start = u->lineage_start;
330 irn = mi->lineage_next;
333 heights_recompute(env->heights);
335 mi = get_mris_irn(env, v_start);
336 list_del(&mi->lineage_list);
341 static void fuse_lineages(mris_env_t *env)
343 mris_irn_t *u, *v, *tmp1, *tmp2;
346 foreach_lineage(env, u, tmp1) {
347 foreach_lineage(env, v, tmp2) {
348 if (u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
349 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
350 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
351 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
354 if (fuse_two_lineages(env, u, v))
362 static mris_env_t *dump_env = NULL;
364 static void block_walker(ir_node *bl, void *data)
366 mris_env_t *env = (mris_env_t*)data;
368 lineage_formation(env);
372 static void mris_edge_hook(FILE *F, ir_node *irn)
374 mris_irn_t *mi = get_mris_irn(dump_env, irn);
376 if (mi->lineage_next) {
377 fprintf(F, "edge:{sourcename:\"");
378 PRINT_NODEID(mi->lineage_next);
379 fprintf(F, "\" targetname:\"");
381 fprintf(F, "\" color:lilac}\n");
385 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix)
387 dump_node_edge_func old = get_dump_node_edge_hook();
389 set_dump_node_edge_hook(mris_edge_hook);
391 dump_ir_graph(env->irg, suffix);
392 set_dump_node_edge_hook(old);
395 mris_env_t *be_sched_mris_preprocess(ir_graph *irg)
397 mris_env_t *env = XMALLOC(mris_env_t);
399 phase_init(&env->ph, irg, mris_irn_data_init);
402 env->heights = heights_new(irg);
403 INIT_LIST_HEAD(&env->lineage_head);
404 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
405 obstack_init(&env->obst);
406 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
407 irg_block_walk_graph(irg, block_walker, NULL, env);
408 obstack_free(&env->obst, NULL);
409 // dump_ir_block_graph_mris(env, "-mris");
413 void be_sched_mris_free(mris_env_t *env)
415 phase_deinit(&env->ph);
416 heights_free(env->heights);