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 */
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. */
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;
320 foreach_out_edge(last, edge) {
321 last = get_edge_src_irn(edge);
326 /* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
327 mi->lineage_next = v_start;
329 /* add a dependency from the first node in v's lineage to the last in u's */
330 add_irn_dep(u_end, v_start);
332 /* set lineage start of nodes in v to start of u. */
333 irn = v->lineage_start;
334 while(irn && irn != v->lineage_end) {
335 mris_irn_t *mi = get_mris_irn(env, irn);
336 mi->lineage_start = u->lineage_start;
337 irn = mi->lineage_next;
340 heights_recompute(env->heights);
342 mi = get_mris_irn(env, v_start);
343 list_del(&mi->lineage_list);
348 static void fuse_lineages(mris_env_t *env)
350 mris_irn_t *u, *v, *tmp1, *tmp2;
353 foreach_lineage(env, u, tmp1) {
354 foreach_lineage(env, v, tmp2) {
355 if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
356 && get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
357 int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
358 int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);
361 if(fuse_two_lineages(env, u, v))
369 static mris_env_t *dump_env = NULL;
371 static void block_walker(ir_node *bl, void *data)
373 mris_env_t *env = data;
375 lineage_formation(env);
379 static int mris_edge_hook(FILE *F, ir_node *irn)
381 mris_irn_t *mi = get_mris_irn(dump_env, irn);
383 if(mi->lineage_next) {
384 fprintf(F, "edge:{sourcename:\"");
385 PRINT_NODEID(mi->lineage_next);
386 fprintf(F, "\" targetname:\"");
388 fprintf(F, "\" color:lilac}\n");
393 void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
394 DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();
396 dump_consts_local(0);
397 set_dump_node_edge_hook(mris_edge_hook);
399 dump_ir_block_graph(env->irg, suffix);
400 set_dump_node_edge_hook(old);
403 mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
405 mris_env_t *env = XMALLOC(mris_env_t);
406 ir_graph *irg = be_get_birg_irg(birg);
408 phase_init(&env->ph, "mris", irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init, NULL);
411 env->heights = heights_new(irg);
412 INIT_LIST_HEAD(&env->lineage_head);
413 FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
414 obstack_init(&env->obst);
415 irg_walk_graph(irg, firm_clear_link, NULL, NULL);
416 irg_block_walk_graph(irg, block_walker, NULL, env);
417 obstack_free(&env->obst, NULL);
418 // dump_ir_block_graph_mris(env, "-mris");
422 void be_sched_mris_free(mris_env_t *env)
424 phase_free(&env->ph);
425 heights_free(env->heights);