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.
32 # endif /* def DEBUG_libfirm */
37 /*static*/ dtree_t *trees = 0;
39 static dtree_t *last = 0;
42 /* --------------------------------------------------------------------
44 * -------------------------------------------------------------------- */
46 Helper function for get_n_blocks
48 static void count_block (ir_node *block, void *env)
53 assert (block && "no block");
54 assert (env && "no env");
55 # endif /* def DEBUG_libfirm */
57 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
58 __FILE__ ":count_block", (void *)block, *n);
64 Count the number of blocks in the given graph
66 static int get_n_blocks (ir_graph *graph)
70 ir_node *end_block = get_irg_end (graph);
73 assert (graph && "no graph");
74 assert (end_block && "no end block");
75 # endif /* def DEBUG_libfirm */
77 irg_block_walk (end_block, count_block, NULL, &n);
79 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
80 __FILE__ ":get_n_blocks", (void *)graph, n);
86 Build an empty dominator relation entry
88 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
90 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
93 assert (res && "no memory for dtree");
94 # endif /* def DEBUG_libfirm */
104 Build an empty dominator relation
106 static dt_t *new_dt (ir_graph *graph)
108 int n_blocks = get_n_blocks (graph);
110 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
112 # ifdef DEBUG_libfirm
113 assert (n_blocks && "no blocks for dt");
114 assert (res && "no memory for dt");
115 # endif /* def DEBUG_libfirm */
117 res->n_blocks = n_blocks;
119 res->blocks = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
120 res->idoms = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
121 res->masks = (bs_t*) calloc (n_blocks, sizeof (bs_t));
123 assert (res && "no dt");
128 static void free_dt (dt_t *dt)
130 free (dt->blocks); dt->blocks = 0;
131 free (dt->masks); dt->masks = 0;
136 /* --------------------------------------------------------------------
138 * -------------------------------------------------------------------- */
141 Given a graph, find its dominator tree in the global list:
143 @return The tree, if it exists, and 0 else
145 static dt_t *get_dominator_tree (ir_graph *graph)
147 dtree_t *iter = trees;
149 # ifdef DEBUG_libfirm
150 assert (graph && "no graph");
151 # endif /* def DEBUG_libfirm */
153 while ((0 != iter) && (graph != iter->graph))
158 # ifdef DEBUG_libfirm
159 assert ((graph == iter->tree->graph) && "wrong graph");
160 # endif /* def DEBUG_libfirm */
171 Given a dominator tree and a graph, enter the tree into the global list.
173 static void add_dominator_tree (dt_t *tree)
176 ir_graph *graph = tree->graph;
178 # ifdef DEBUG_libfirm
179 assert (tree && "no tree" );
180 assert (graph && "no graph");
181 # endif /* def DEBUG_libfirm */
183 dtree = new_dtree (tree, graph);
185 # ifdef VERBOSE_libfirm
186 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
187 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
188 # endif /* def VERBOSE_libfirm */
190 /* enter in global list: */
196 Get (or create) the index for a given block
198 static int get_index (dt_t *dt, ir_node *block)
202 # ifdef DEBUG_libfirm
203 assert (dt && "no dt");
204 assert (block && "no block");
205 # endif /* def DEBUG_libfirm */
207 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
208 if (block == dt->blocks [i])
211 /* not found . . . enter new one: */
212 dt->blocks [i] = block;
213 if (block == get_irg_start_block (dt->graph))
215 dt->masks [i] = 0x00000001 << i;
217 # ifdef VERBOSE_libfirm
218 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
219 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
220 # endif /* def VERBOSE_libfirm */
224 dt->masks [i] = ~0x00000000;
226 # ifdef VERBOSE_libfirm
227 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
228 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
229 # endif /* def VERBOSE_libfirm */
236 Get the bit mask for a block
238 static bs_t _get_mask (dt_t*, int);
239 static bs_t get_mask (dt_t *dt, ir_node *block)
241 int index = get_index (dt, block);
243 # ifdef DEBUG_libfirm
244 assert (dt && "no dt");
245 assert (block && "no block");
246 # endif /* def DEBUG_libfirm */
248 return (_get_mask (dt, index));
252 Get the bit mask for a block index
254 static bs_t _get_mask (dt_t *dt, int index)
256 # ifdef DEBUG_libfirm
257 assert (dt && "no dt");
258 # endif /* def DEBUG_libfirm */
260 return (dt->masks [index]);
264 Set the bit mask for a block
267 static void _set_mask (dt_t*, int, bs_t);
268 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
270 int index = get_index (dt, block);
272 # ifdef DEBUG_libfirm
273 assert (dt && "no dt");
274 assert (block && "no block");
275 # endif /* def DEBUG_libfirm */
277 _set_mask (dt, index, mask);
281 Set the bit mask for a block index
283 static void _set_mask (dt_t *dt, int index, bs_t mask)
285 # ifdef DEBUG_libfirm
286 assert (dt && "no dt");
287 # endif /* def DEBUG_libfirm */
289 dt->masks [index] = mask;
293 Update the list of dominators of a given block
295 typedef struct dt_walk_env_t
297 dt_t *dt; /* the dominator relation we're building */
298 ir_node *start_block; /* need to know the start block of this graph */
299 bool changed; /* wether the relation has changed recently */
304 Helper function for build_dominator_tree
306 static void update_dominators (ir_node *block, void *env)
309 dt_walk_env_t *w = (dt_walk_env_t*) env;
312 int block_index = get_index (dt, block);
313 int n_ins = get_irn_arity (block);
315 bs_t old_mask = _get_mask (dt, block_index);
316 bs_t new_mask = ~0x00000000;
318 /* Special handling of Start Block: */
319 if (block == w->start_block)
323 for (i = 0; i < n_ins; i ++)
325 ir_node *in = get_nodes_Block (get_irn_n (block, i));
326 bs_t in_mask = get_mask (dt, in);
331 /* and remember ourselves: */
332 new_mask |= (0x00000001 << block_index);
334 if (new_mask != old_mask)
337 _set_mask (dt, block_index, new_mask);
339 # ifdef VERBOSE_libfirm
340 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
341 __FILE__ ":" __PRETTY_FUNCTION__,
342 block, block_index, old_mask, new_mask);
343 # endif /* def VERBOSE_libfirm */
348 Say wether a dominates b
351 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
353 int index_a = get_index (dt, a);
354 bs_t b_mask = get_mask (dt, b);
356 return (0 != (b_mask & (0x00000001 << index_a)));
360 Return the immediate dominator of block a
362 static ir_node *_get_idom (dt_t *dt, ir_node *block)
365 int block_index = get_index (dt, block);
367 if (0 != (idom = dt->idoms [block_index]))
370 /* check all CFG preds:
371 Question: Shouldn't it be good enough to just ask our first CFG
375 int n = get_irn_arity (block);
378 idom = block; /* prime the loop: */
380 for (i = 0; i < n; i ++)
384 pred = get_nodes_Block (get_irn_n (block, i));
385 ndom = _get_idom (dt, pred);
388 if (_dominates (dt, idom, ndom))
393 assert (idom && "Something terribly wrong in _get_idom");
395 # ifdef VERBOSE_libfirm
396 fprintf (stdout, "%s: idom(%p) = %p\n",
397 __FILE__ ":" __PRETTY_FUNCTION__,
399 # endif /* def VERBOSE_libfirm */
402 dt->idoms [block_index] = idom;
407 /* --------------------------------------------------------------------
409 * -------------------------------------------------------------------- */
412 Say wether a dominates b
414 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
416 dt_t *dt = get_dominator_tree (g);
418 return (_dominates (dt, a, b));
422 Return the immediate dominator of block a
424 ir_node *get_idom (ir_graph *g, ir_node *a)
426 dt_t *dt = get_dominator_tree (g);
428 return (_get_idom (dt, a));
432 Allow for precomputation of necessary data
433 This will allow for a slightly faster lookup of the dominator
434 relation if one node is checked for dominance against many other nodes.
436 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
438 dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t));
441 env->dt = get_dominator_tree (graph);
443 env->index_a = get_index (env->dt, a);
448 Dispose a dominator environment
450 void delete_dom_env (dom_env_t *env)
461 Say wether the node in env dominates b
465 bool dominates_l (dom_env_t *env, ir_node *b)
467 int index_a = env->index_a;
469 bs_t b_mask = get_mask (dt, b);
471 return (0 != (b_mask & (0x00000001 << index_a)));
475 Build a new dominator tree for the given graph
477 void build_dominator_tree (ir_graph *graph)
480 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
482 ir_node *end_block = get_irg_end_block (graph);
483 ir_node *start_block = get_irg_start_block (graph);
484 int n_blocks = get_n_blocks (graph);
485 dt_t *dt = get_dominator_tree (graph);
488 dt_walk_env_t *w = 0;
489 ir_node *end_block = 0;
490 ir_node *start_block = 0;
494 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
495 end_block = get_irg_end_block (graph);
496 start_block = get_irg_start_block (graph);
497 n_blocks = get_n_blocks (graph);
498 dt = get_dominator_tree (graph);
500 # ifdef DEBUG_libfirm
501 assert (graph && "no graph");
502 # endif /* def DEBUG_libfirm */
504 # ifdef VERBOSE_libfirm
505 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
506 # endif /* def VERBOSE_libfirm */
514 w->start_block = start_block;
515 w->changed = true; /* at least one walk */
524 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
528 # ifdef VERBOSE_libfirm
529 fprintf (stdout, "%s: for graph(%p): %i passes\n",
530 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
531 # endif /* def VERBOSE_libfirm */
534 /* ok, now remember it: */
535 add_dominator_tree (dt);