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.
40 /*static*/ dtree_t *trees = 0;
42 static dtree_t *last = 0;
45 /* --------------------------------------------------------------------
47 * -------------------------------------------------------------------- */
49 Helper function for get_n_blocks
51 static void count_block (ir_node *block, void *env)
56 assert (block && "no block");
57 assert (env && "no env");
58 # endif /* def DEBUG_libfirm */
60 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
61 __FILE__ ":count_block", (void *)block, *n);
67 Count the number of blocks in the given graph
69 static int get_n_blocks (ir_graph *graph)
73 ir_node *end_block = get_irg_end (graph);
76 assert (graph && "no graph");
77 assert (end_block && "no end block");
78 # endif /* def DEBUG_libfirm */
80 irg_block_walk (end_block, count_block, NULL, &n);
82 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
83 __FILE__ ":get_n_blocks", (void *)graph, n);
89 Build an empty dominator relation entry
91 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
93 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
96 assert (res && "no memory for dtree");
97 # endif /* def DEBUG_libfirm */
107 Build an empty dominator relation
109 static dt_t *new_dt (ir_graph *graph)
111 int n_blocks = get_n_blocks (graph);
113 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
115 # ifdef DEBUG_libfirm
116 assert (n_blocks && "no blocks for dt");
117 assert (res && "no memory for dt");
118 # endif /* def DEBUG_libfirm */
120 res->n_blocks = n_blocks;
122 res->blocks = xcalloc(n_blocks, sizeof(res->blocks[0]));
123 res->idoms = xcalloc(n_blocks, sizeof(res->idoms[0]));
124 res->masks = xcalloc(n_blocks, sizeof(res->masks[0]));
126 assert (res && "no dt");
131 static void free_dt (dt_t *dt)
133 free (dt->blocks); dt->blocks = 0;
134 free (dt->masks); dt->masks = 0;
139 /* --------------------------------------------------------------------
141 * -------------------------------------------------------------------- */
144 Given a graph, find its dominator tree in the global list:
146 @return The tree, if it exists, and 0 else
148 static dt_t *get_dominator_tree (ir_graph *graph)
150 dtree_t *iter = trees;
152 # ifdef DEBUG_libfirm
153 assert (graph && "no graph");
154 # endif /* def DEBUG_libfirm */
156 while ((0 != iter) && (graph != iter->graph))
161 # ifdef DEBUG_libfirm
162 assert ((graph == iter->tree->graph) && "wrong graph");
163 # endif /* def DEBUG_libfirm */
174 Given a dominator tree and a graph, enter the tree into the global list.
176 static void add_dominator_tree (dt_t *tree)
179 ir_graph *graph = tree->graph;
181 # ifdef DEBUG_libfirm
182 assert (tree && "no tree" );
183 assert (graph && "no graph");
184 # endif /* def DEBUG_libfirm */
186 dtree = new_dtree (tree, graph);
188 # ifdef VERBOSE_libfirm
189 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
190 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
191 # endif /* def VERBOSE_libfirm */
193 /* enter in global list: */
199 Get (or create) the index for a given block
201 static int get_index (dt_t *dt, ir_node *block)
205 # ifdef DEBUG_libfirm
206 assert (dt && "no dt");
207 assert (block && "no block");
208 # endif /* def DEBUG_libfirm */
210 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
211 if (block == dt->blocks [i])
214 /* not found . . . enter new one: */
215 dt->blocks [i] = block;
216 if (block == get_irg_start_block (dt->graph))
218 dt->masks [i] = 0x00000001 << i;
220 # ifdef VERBOSE_libfirm
221 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
222 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
223 # endif /* def VERBOSE_libfirm */
227 dt->masks [i] = ~0x00000000;
229 # ifdef VERBOSE_libfirm
230 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
231 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
232 # endif /* def VERBOSE_libfirm */
239 Get the bit mask for a block
241 static bs_t _get_mask (dt_t*, int);
242 static bs_t get_mask (dt_t *dt, ir_node *block)
244 int index = get_index (dt, block);
246 # ifdef DEBUG_libfirm
247 assert (dt && "no dt");
248 assert (block && "no block");
249 # endif /* def DEBUG_libfirm */
251 return (_get_mask (dt, index));
255 Get the bit mask for a block index
257 static bs_t _get_mask (dt_t *dt, int index)
259 # ifdef DEBUG_libfirm
260 assert (dt && "no dt");
261 # endif /* def DEBUG_libfirm */
263 return (dt->masks [index]);
267 Set the bit mask for a block
270 static void _set_mask (dt_t*, int, bs_t);
271 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
273 int index = get_index (dt, block);
275 # ifdef DEBUG_libfirm
276 assert (dt && "no dt");
277 assert (block && "no block");
278 # endif /* def DEBUG_libfirm */
280 _set_mask (dt, index, mask);
284 Set the bit mask for a block index
286 static void _set_mask (dt_t *dt, int index, bs_t mask)
288 # ifdef DEBUG_libfirm
289 assert (dt && "no dt");
290 # endif /* def DEBUG_libfirm */
292 dt->masks [index] = mask;
296 Update the list of dominators of a given block
298 typedef struct dt_walk_env_t
300 dt_t *dt; /* the dominator relation we're building */
301 ir_node *start_block; /* need to know the start block of this graph */
302 bool changed; /* wether the relation has changed recently */
307 Helper function for build_dominator_tree
309 static void update_dominators (ir_node *block, void *env)
312 dt_walk_env_t *w = (dt_walk_env_t*) env;
315 int block_index = get_index (dt, block);
316 int n_ins = get_irn_arity (block);
318 bs_t old_mask = _get_mask (dt, block_index);
319 bs_t new_mask = ~0x00000000;
321 /* Special handling of Start Block: */
322 if (block == w->start_block)
326 for (i = 0; i < n_ins; i ++)
328 ir_node *in = get_nodes_block (get_irn_n (block, i));
329 bs_t in_mask = get_mask (dt, in);
334 /* and remember ourselves: */
335 new_mask |= (0x00000001 << block_index);
337 if (new_mask != old_mask)
340 _set_mask (dt, block_index, new_mask);
342 # ifdef VERBOSE_libfirm
343 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
344 __FILE__ ":" __PRETTY_FUNCTION__,
345 block, block_index, old_mask, new_mask);
346 # endif /* def VERBOSE_libfirm */
351 Say wether a dominates b
354 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
356 int index_a = get_index (dt, a);
357 bs_t b_mask = get_mask (dt, b);
359 return (0 != (b_mask & (0x00000001 << index_a)));
363 Return the immediate dominator of block a
365 static ir_node *_get_idom (dt_t *dt, ir_node *block)
368 int block_index = get_index (dt, block);
370 if (0 != (idom = dt->idoms [block_index]))
373 /* check all CFG preds:
374 Question: Shouldn't it be good enough to just ask our first CFG
378 int n = get_irn_arity (block);
381 idom = block; /* prime the loop: */
383 for (i = 0; i < n; i ++)
387 pred = get_nodes_block (get_irn_n (block, i));
388 ndom = _get_idom (dt, pred);
391 if (_dominates (dt, idom, ndom))
396 assert (idom && "Something terribly wrong in _get_idom");
398 # ifdef VERBOSE_libfirm
399 fprintf (stdout, "%s: idom(%p) = %p\n",
400 __FILE__ ":" __PRETTY_FUNCTION__,
402 # endif /* def VERBOSE_libfirm */
405 dt->idoms [block_index] = idom;
410 /* --------------------------------------------------------------------
412 * -------------------------------------------------------------------- */
415 Say wether a dominates b
417 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
419 dt_t *dt = get_dominator_tree (g);
421 return (_dominates (dt, a, b));
425 Return the immediate dominator of block a
427 ir_node *get_idom (ir_graph *g, ir_node *a)
429 dt_t *dt = get_dominator_tree (g);
431 return (_get_idom (dt, a));
435 Allow for precomputation of necessary data
436 This will allow for a slightly faster lookup of the dominator
437 relation if one node is checked for dominance against many other nodes.
439 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
441 dom_env_t *env = xcalloc(1, sizeof(*env));
444 env->dt = get_dominator_tree (graph);
446 env->index_a = get_index (env->dt, a);
451 Dispose a dominator environment
453 void delete_dom_env (dom_env_t *env)
464 Say wether the node in env dominates b
468 bool dominates_l (dom_env_t *env, ir_node *b)
470 int index_a = env->index_a;
472 bs_t b_mask = get_mask (dt, b);
474 return (0 != (b_mask & (0x00000001 << index_a)));
478 Build a new dominator tree for the given graph
480 void build_dominator_tree (ir_graph *graph)
483 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
485 ir_node *end_block = get_irg_end_block (graph);
486 ir_node *start_block = get_irg_start_block (graph);
487 int n_blocks = get_n_blocks (graph);
488 dt_t *dt = get_dominator_tree (graph);
491 dt_walk_env_t *w = 0;
492 ir_node *end_block = 0;
493 ir_node *start_block = 0;
497 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
498 end_block = get_irg_end_block (graph);
499 start_block = get_irg_start_block (graph);
500 n_blocks = get_n_blocks (graph);
501 dt = get_dominator_tree (graph);
503 # ifdef DEBUG_libfirm
504 assert (graph && "no graph");
505 # endif /* def DEBUG_libfirm */
507 # ifdef VERBOSE_libfirm
508 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
509 # endif /* def VERBOSE_libfirm */
517 w->start_block = start_block;
518 w->changed = true; /* at least one walk */
527 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
531 # ifdef VERBOSE_libfirm
532 fprintf (stdout, "%s: for graph(%p): %i passes\n",
533 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
534 # endif /* def VERBOSE_libfirm */
537 /* ok, now remember it: */
538 add_dominator_tree (dt);