3 * File name: ir/st/st.c
4 * Purpose: Provide some auxilliary structures for firm graphs.
5 * Author: Florian Liekweg
9 * Copyright: (c) 2002-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 provide some auxilliary structures for firm graphs.
34 /*static*/ dtree_t *trees = 0;
36 static dtree_t *last = 0;
39 /* --------------------------------------------------------------------
41 * -------------------------------------------------------------------- */
43 Helper function for get_n_blocks
45 static void count_block (ir_node *block, void *env)
50 assert (block && "no block");
51 assert (env && "no env");
52 # endif /* def DEBUG_libfirm */
54 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
55 __FILE__ ":count_block", (void *)block, *n);
61 Count the number of blocks in the given graph
63 static int get_n_blocks (ir_graph *graph)
67 ir_node *end_block = get_irg_end (graph);
70 assert (graph && "no graph");
71 assert (end_block && "no end block");
72 # endif /* def DEBUG_libfirm */
74 irg_block_walk (end_block, count_block, NULL, &n);
76 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
77 __FILE__ ":get_n_blocks", (void *)graph, n);
83 Build an empty dominator relation entry
85 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
87 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
90 assert (res && "no memory for dtree");
91 # endif /* def DEBUG_libfirm */
101 Build an empty dominator relation
103 static dt_t *new_dt (ir_graph *graph)
105 int n_blocks = get_n_blocks (graph);
107 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
109 # ifdef DEBUG_libfirm
110 assert (n_blocks && "no blocks for dt");
111 assert (res && "no memory for dt");
112 # endif /* def DEBUG_libfirm */
114 res->n_blocks = n_blocks;
116 res->blocks = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
117 res->idoms = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
118 res->masks = (bs_t*) calloc (n_blocks, sizeof (bs_t));
120 assert (res && "no dt");
125 static void free_dt (dt_t *dt)
127 free (dt->blocks); dt->blocks = 0;
128 free (dt->masks); dt->masks = 0;
133 /* --------------------------------------------------------------------
135 * -------------------------------------------------------------------- */
138 Given a graph, find its dominator tree in the global list:
140 @return The tree, if it exists, and 0 else
142 static dt_t *get_dominator_tree (ir_graph *graph)
144 dtree_t *iter = trees;
146 # ifdef DEBUG_libfirm
147 assert (graph && "no graph");
148 # endif /* def DEBUG_libfirm */
150 while ((0 != iter) && (graph != iter->graph))
155 # ifdef DEBUG_libfirm
156 assert ((graph == iter->tree->graph) && "wrong graph");
157 # endif /* def DEBUG_libfirm */
168 Given a dominator tree and a graph, enter the tree into the global list.
170 static void add_dominator_tree (dt_t *tree)
173 ir_graph *graph = tree->graph;
175 # ifdef DEBUG_libfirm
176 assert (tree && "no tree" );
177 assert (graph && "no graph");
178 # endif /* def DEBUG_libfirm */
180 dtree = new_dtree (tree, graph);
182 # ifdef VERBOSE_libfirm
183 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
184 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
185 # endif /* def VERBOSE_libfirm */
187 /* enter in global list: */
193 Get (or create) the index for a given block
195 static int get_index (dt_t *dt, ir_node *block)
199 # ifdef DEBUG_libfirm
200 assert (dt && "no dt");
201 assert (block && "no block");
202 # endif /* def DEBUG_libfirm */
204 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
205 if (block == dt->blocks [i])
208 /* not found . . . enter new one: */
209 dt->blocks [i] = block;
210 if (block == get_irg_start_block (dt->graph))
212 dt->masks [i] = 0x00000001 << i;
214 # ifdef VERBOSE_libfirm
215 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
216 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
217 # endif /* def VERBOSE_libfirm */
221 dt->masks [i] = ~0x00000000;
223 # ifdef VERBOSE_libfirm
224 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
225 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
226 # endif /* def VERBOSE_libfirm */
233 Get the bit mask for a block
235 static bs_t _get_mask (dt_t*, int);
236 static bs_t get_mask (dt_t *dt, ir_node *block)
238 int index = get_index (dt, block);
240 # ifdef DEBUG_libfirm
241 assert (dt && "no dt");
242 assert (block && "no block");
243 # endif /* def DEBUG_libfirm */
245 return (_get_mask (dt, index));
249 Get the bit mask for a block index
251 static bs_t _get_mask (dt_t *dt, int index)
253 # ifdef DEBUG_libfirm
254 assert (dt && "no dt");
255 # endif /* def DEBUG_libfirm */
257 return (dt->masks [index]);
261 Set the bit mask for a block
264 static void _set_mask (dt_t*, int, bs_t);
265 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
267 int index = get_index (dt, block);
269 # ifdef DEBUG_libfirm
270 assert (dt && "no dt");
271 assert (block && "no block");
272 # endif /* def DEBUG_libfirm */
274 _set_mask (dt, index, mask);
278 Set the bit mask for a block index
280 static void _set_mask (dt_t *dt, int index, bs_t mask)
282 # ifdef DEBUG_libfirm
283 assert (dt && "no dt");
284 # endif /* def DEBUG_libfirm */
286 dt->masks [index] = mask;
290 Update the list of dominators of a given block
292 typedef struct dt_walk_env_t
294 dt_t *dt; /* the dominator relation we're building */
295 ir_node *start_block; /* need to know the start block of this graph */
296 bool changed; /* wether the relation has changed recently */
301 Helper function for build_dominator_tree
303 static void update_dominators (ir_node *block, void *env)
306 dt_walk_env_t *w = (dt_walk_env_t*) env;
309 int block_index = get_index (dt, block);
310 int n_ins = get_irn_arity (block);
312 bs_t old_mask = _get_mask (dt, block_index);
313 bs_t new_mask = ~0x00000000;
315 /* Special handling of Start Block: */
316 if (block == w->start_block)
320 for (i = 0; i < n_ins; i ++)
322 ir_node *in = get_nodes_block (get_irn_n (block, i));
323 bs_t in_mask = get_mask (dt, in);
328 /* and remember ourselves: */
329 new_mask |= (0x00000001 << block_index);
331 if (new_mask != old_mask)
334 _set_mask (dt, block_index, new_mask);
336 # ifdef VERBOSE_libfirm
337 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
338 __FILE__ ":" __PRETTY_FUNCTION__,
339 block, block_index, old_mask, new_mask);
340 # endif /* def VERBOSE_libfirm */
345 Say wether a dominates b
348 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
350 int index_a = get_index (dt, a);
351 bs_t b_mask = get_mask (dt, b);
353 return (0 != (b_mask & (0x00000001 << index_a)));
357 Return the immediate dominator of block a
359 static ir_node *_get_idom (dt_t *dt, ir_node *block)
362 int block_index = get_index (dt, block);
364 if (0 != (idom = dt->idoms [block_index]))
367 /* check all CFG preds:
368 Question: Shouldn't it be good enough to just ask our first CFG
372 int n = get_irn_arity (block);
375 idom = block; /* prime the loop: */
377 for (i = 0; i < n; i ++)
381 pred = get_nodes_block (get_irn_n (block, i));
382 ndom = _get_idom (dt, pred);
385 if (_dominates (dt, idom, ndom))
390 assert (idom && "Something terribly wrong in _get_idom");
392 # ifdef VERBOSE_libfirm
393 fprintf (stdout, "%s: idom(%p) = %p\n",
394 __FILE__ ":" __PRETTY_FUNCTION__,
396 # endif /* def VERBOSE_libfirm */
399 dt->idoms [block_index] = idom;
404 /* --------------------------------------------------------------------
406 * -------------------------------------------------------------------- */
409 Say wether a dominates b
411 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
413 dt_t *dt = get_dominator_tree (g);
415 return (_dominates (dt, a, b));
419 Return the immediate dominator of block a
421 ir_node *get_idom (ir_graph *g, ir_node *a)
423 dt_t *dt = get_dominator_tree (g);
425 return (_get_idom (dt, a));
429 Allow for precomputation of necessary data
430 This will allow for a slightly faster lookup of the dominator
431 relation if one node is checked for dominance against many other nodes.
433 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
435 dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t));
438 env->dt = get_dominator_tree (graph);
440 env->index_a = get_index (env->dt, a);
445 Dispose a dominator environment
447 void delete_dom_env (dom_env_t *env)
458 Say wether the node in env dominates b
462 bool dominates_l (dom_env_t *env, ir_node *b)
464 int index_a = env->index_a;
466 bs_t b_mask = get_mask (dt, b);
468 return (0 != (b_mask & (0x00000001 << index_a)));
472 Build a new dominator tree for the given graph
474 void build_dominator_tree (ir_graph *graph)
477 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
479 ir_node *end_block = get_irg_end_block (graph);
480 ir_node *start_block = get_irg_start_block (graph);
481 int n_blocks = get_n_blocks (graph);
482 dt_t *dt = get_dominator_tree (graph);
485 dt_walk_env_t *w = 0;
486 ir_node *end_block = 0;
487 ir_node *start_block = 0;
491 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
492 end_block = get_irg_end_block (graph);
493 start_block = get_irg_start_block (graph);
494 n_blocks = get_n_blocks (graph);
495 dt = get_dominator_tree (graph);
497 # ifdef DEBUG_libfirm
498 assert (graph && "no graph");
499 # endif /* def DEBUG_libfirm */
501 # ifdef VERBOSE_libfirm
502 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
503 # endif /* def VERBOSE_libfirm */
511 w->start_block = start_block;
512 w->changed = true; /* at least one walk */
521 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
525 # ifdef VERBOSE_libfirm
526 fprintf (stdout, "%s: for graph(%p): %i passes\n",
527 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
528 # endif /* def VERBOSE_libfirm */
531 /* ok, now remember it: */
532 add_dominator_tree (dt);