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.
46 /*static*/ dtree_t *trees = 0;
48 static dtree_t *last = 0;
51 /* --------------------------------------------------------------------
53 * -------------------------------------------------------------------- */
55 Helper function for get_n_blocks
57 static void count_block (ir_node *block, void *env)
62 assert (block && "no block");
63 assert (env && "no env");
64 # endif /* def DEBUG_libfirm */
66 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
67 __FILE__ ":count_block", (void *)block, *n);
73 Count the number of blocks in the given graph
75 static int get_n_blocks (ir_graph *graph)
79 ir_node *end_block = get_irg_end (graph);
82 assert (graph && "no graph");
83 assert (end_block && "no end block");
84 # endif /* def DEBUG_libfirm */
86 irg_block_walk (end_block, count_block, NULL, &n);
88 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
89 __FILE__ ":get_n_blocks", (void *)graph, n);
95 Build an empty dominator relation entry
97 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
99 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
101 # ifdef DEBUG_libfirm
102 assert (res && "no memory for dtree");
103 # endif /* def DEBUG_libfirm */
113 Build an empty dominator relation
115 static dt_t *new_dt (ir_graph *graph)
117 int n_blocks = get_n_blocks (graph);
119 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
121 # ifdef DEBUG_libfirm
122 assert (n_blocks && "no blocks for dt");
123 assert (res && "no memory for dt");
124 # endif /* def DEBUG_libfirm */
126 res->n_blocks = n_blocks;
128 res->blocks = xcalloc(n_blocks, sizeof(res->blocks[0]));
129 res->idoms = xcalloc(n_blocks, sizeof(res->idoms[0]));
130 res->masks = xcalloc(n_blocks, sizeof(res->masks[0]));
132 assert (res && "no dt");
137 static void free_dt (dt_t *dt)
139 free (dt->blocks); dt->blocks = 0;
140 free (dt->masks); dt->masks = 0;
145 /* --------------------------------------------------------------------
147 * -------------------------------------------------------------------- */
150 Given a graph, find its dominator tree in the global list:
152 @return The tree, if it exists, and 0 else
154 static dt_t *get_dominator_tree (ir_graph *graph)
156 dtree_t *iter = trees;
158 # ifdef DEBUG_libfirm
159 assert (graph && "no graph");
160 # endif /* def DEBUG_libfirm */
162 while ((0 != iter) && (graph != iter->graph))
167 # ifdef DEBUG_libfirm
168 assert ((graph == iter->tree->graph) && "wrong graph");
169 # endif /* def DEBUG_libfirm */
180 Given a dominator tree and a graph, enter the tree into the global list.
182 static void add_dominator_tree (dt_t *tree)
185 ir_graph *graph = tree->graph;
187 # ifdef DEBUG_libfirm
188 assert (tree && "no tree" );
189 assert (graph && "no graph");
190 # endif /* def DEBUG_libfirm */
192 dtree = new_dtree (tree, graph);
194 # ifdef VERBOSE_libfirm
195 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
196 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
197 # endif /* def VERBOSE_libfirm */
199 /* enter in global list: */
205 Get (or create) the index for a given block
207 static int get_index (dt_t *dt, ir_node *block)
211 # ifdef DEBUG_libfirm
212 assert (dt && "no dt");
213 assert (block && "no block");
214 # endif /* def DEBUG_libfirm */
216 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
217 if (block == dt->blocks [i])
220 /* not found . . . enter new one: */
221 dt->blocks [i] = block;
222 if (block == get_irg_start_block (dt->graph))
224 dt->masks [i] = 0x00000001 << i;
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 */
233 dt->masks [i] = ~0x00000000;
235 # ifdef VERBOSE_libfirm
236 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
237 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
238 # endif /* def VERBOSE_libfirm */
245 Get the bit mask for a block
247 static bs_t _get_mask (dt_t*, int);
248 static bs_t get_mask (dt_t *dt, ir_node *block)
250 int index = get_index (dt, block);
252 # ifdef DEBUG_libfirm
253 assert (dt && "no dt");
254 assert (block && "no block");
255 # endif /* def DEBUG_libfirm */
257 return (_get_mask (dt, index));
261 Get the bit mask for a block index
263 static bs_t _get_mask (dt_t *dt, int index)
265 # ifdef DEBUG_libfirm
266 assert (dt && "no dt");
267 # endif /* def DEBUG_libfirm */
269 return (dt->masks [index]);
273 Set the bit mask for a block
276 static void _set_mask (dt_t*, int, bs_t);
277 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
279 int index = get_index (dt, block);
281 # ifdef DEBUG_libfirm
282 assert (dt && "no dt");
283 assert (block && "no block");
284 # endif /* def DEBUG_libfirm */
286 _set_mask (dt, index, mask);
290 Set the bit mask for a block index
292 static void _set_mask (dt_t *dt, int index, bs_t mask)
294 # ifdef DEBUG_libfirm
295 assert (dt && "no dt");
296 # endif /* def DEBUG_libfirm */
298 dt->masks [index] = mask;
302 Update the list of dominators of a given block
304 typedef struct dt_walk_env_t
306 dt_t *dt; /* the dominator relation we're building */
307 ir_node *start_block; /* need to know the start block of this graph */
308 bool changed; /* wether the relation has changed recently */
313 Helper function for build_dominator_tree
315 static void update_dominators (ir_node *block, void *env)
318 dt_walk_env_t *w = (dt_walk_env_t*) env;
321 int block_index = get_index (dt, block);
322 int n_ins = get_irn_arity (block);
324 bs_t old_mask = _get_mask (dt, block_index);
325 bs_t new_mask = ~0x00000000;
327 /* Special handling of Start Block: */
328 if (block == w->start_block)
332 for (i = 0; i < n_ins; i ++)
334 ir_node *in = get_nodes_block (get_irn_n (block, i));
335 bs_t in_mask = get_mask (dt, in);
340 /* and remember ourselves: */
341 new_mask |= (0x00000001 << block_index);
343 if (new_mask != old_mask)
346 _set_mask (dt, block_index, new_mask);
348 # ifdef VERBOSE_libfirm
349 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
350 __FILE__ ":" __PRETTY_FUNCTION__,
351 block, block_index, old_mask, new_mask);
352 # endif /* def VERBOSE_libfirm */
357 Say wether a dominates b
360 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
362 int index_a = get_index (dt, a);
363 bs_t b_mask = get_mask (dt, b);
365 return (0 != (b_mask & (0x00000001 << index_a)));
369 Return the immediate dominator of block a
371 static ir_node *_get_idom (dt_t *dt, ir_node *block)
374 int block_index = get_index (dt, block);
376 if (0 != (idom = dt->idoms [block_index]))
379 /* check all CFG preds:
380 Question: Shouldn't it be good enough to just ask our first CFG
384 int n = get_irn_arity (block);
387 idom = block; /* prime the loop: */
389 for (i = 0; i < n; i ++)
393 pred = get_nodes_block (get_irn_n (block, i));
394 ndom = _get_idom (dt, pred);
397 if (_dominates (dt, idom, ndom))
402 assert (idom && "Something terribly wrong in _get_idom");
404 # ifdef VERBOSE_libfirm
405 fprintf (stdout, "%s: idom(%p) = %p\n",
406 __FILE__ ":" __PRETTY_FUNCTION__,
408 # endif /* def VERBOSE_libfirm */
411 dt->idoms [block_index] = idom;
416 /* --------------------------------------------------------------------
418 * -------------------------------------------------------------------- */
421 Say wether a dominates b
423 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
425 dt_t *dt = get_dominator_tree (g);
427 return (_dominates (dt, a, b));
431 Return the immediate dominator of block a
433 ir_node *get_idom (ir_graph *g, ir_node *a)
435 dt_t *dt = get_dominator_tree (g);
437 return (_get_idom (dt, a));
441 Allow for precomputation of necessary data
442 This will allow for a slightly faster lookup of the dominator
443 relation if one node is checked for dominance against many other nodes.
445 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
447 dom_env_t *env = xcalloc(1, sizeof(*env));
450 env->dt = get_dominator_tree (graph);
452 env->index_a = get_index (env->dt, a);
457 Dispose a dominator environment
459 void delete_dom_env (dom_env_t *env)
470 Say wether the node in env dominates b
474 bool dominates_l (dom_env_t *env, ir_node *b)
476 int index_a = env->index_a;
478 bs_t b_mask = get_mask (dt, b);
480 return (0 != (b_mask & (0x00000001 << index_a)));
484 Build a new dominator tree for the given graph
486 void build_dominator_tree (ir_graph *graph)
489 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
491 ir_node *end_block = get_irg_end_block (graph);
492 ir_node *start_block = get_irg_start_block (graph);
493 int n_blocks = get_n_blocks (graph);
494 dt_t *dt = get_dominator_tree (graph);
497 dt_walk_env_t *w = 0;
498 ir_node *end_block = 0;
499 ir_node *start_block = 0;
503 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
504 end_block = get_irg_end_block (graph);
505 start_block = get_irg_start_block (graph);
506 n_blocks = get_n_blocks (graph);
507 dt = get_dominator_tree (graph);
509 # ifdef DEBUG_libfirm
510 assert (graph && "no graph");
511 # endif /* def DEBUG_libfirm */
513 # ifdef VERBOSE_libfirm
514 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
515 # endif /* def VERBOSE_libfirm */
523 w->start_block = start_block;
524 w->changed = true; /* at least one walk */
533 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
537 # ifdef VERBOSE_libfirm
538 fprintf (stdout, "%s: for graph(%p): %i passes\n",
539 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
540 # endif /* def VERBOSE_libfirm */
543 /* ok, now remember it: */
544 add_dominator_tree (dt);