2 * Copyright (C) 1995-2007 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 Provide some auxilliary structures for firm graphs.
23 * @author Florian Liekweg
32 provide some auxilliary structures for firm graphs.
55 /*static*/ dtree_t *trees = 0;
57 static dtree_t *last = 0;
60 /* --------------------------------------------------------------------
62 * -------------------------------------------------------------------- */
64 Helper function for get_n_blocks
66 static void count_block (ir_node *block, void *env)
71 assert (block && "no block");
72 assert (env && "no env");
73 # endif /* def DEBUG_libfirm */
75 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
76 __FILE__ ":count_block", (void *)block, *n);
82 Count the number of blocks in the given graph
84 static int get_n_blocks (ir_graph *graph)
88 ir_node *end_block = get_irg_end (graph);
91 assert (graph && "no graph");
92 assert (end_block && "no end block");
93 # endif /* def DEBUG_libfirm */
95 irg_block_walk (end_block, count_block, NULL, &n);
97 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
98 __FILE__ ":get_n_blocks", (void *)graph, n);
104 Build an empty dominator relation entry
106 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
108 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
110 # ifdef DEBUG_libfirm
111 assert (res && "no memory for dtree");
112 # endif /* def DEBUG_libfirm */
122 Build an empty dominator relation
124 static dt_t *new_dt (ir_graph *graph)
126 int n_blocks = get_n_blocks (graph);
128 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
130 # ifdef DEBUG_libfirm
131 assert (n_blocks && "no blocks for dt");
132 assert (res && "no memory for dt");
133 # endif /* def DEBUG_libfirm */
135 res->n_blocks = n_blocks;
137 res->blocks = xcalloc(n_blocks, sizeof(res->blocks[0]));
138 res->idoms = xcalloc(n_blocks, sizeof(res->idoms[0]));
139 res->masks = xcalloc(n_blocks, sizeof(res->masks[0]));
141 assert (res && "no dt");
146 static void free_dt (dt_t *dt)
148 free (dt->blocks); dt->blocks = 0;
149 free (dt->masks); dt->masks = 0;
154 /* --------------------------------------------------------------------
156 * -------------------------------------------------------------------- */
159 Given a graph, find its dominator tree in the global list:
161 @return The tree, if it exists, and 0 else
163 static dt_t *get_dominator_tree (ir_graph *graph)
165 dtree_t *iter = trees;
167 # ifdef DEBUG_libfirm
168 assert (graph && "no graph");
169 # endif /* def DEBUG_libfirm */
171 while ((0 != iter) && (graph != iter->graph))
176 # ifdef DEBUG_libfirm
177 assert ((graph == iter->tree->graph) && "wrong graph");
178 # endif /* def DEBUG_libfirm */
189 Given a dominator tree and a graph, enter the tree into the global list.
191 static void add_dominator_tree (dt_t *tree)
194 ir_graph *graph = tree->graph;
196 # ifdef DEBUG_libfirm
197 assert (tree && "no tree" );
198 assert (graph && "no graph");
199 # endif /* def DEBUG_libfirm */
201 dtree = new_dtree (tree, graph);
203 # ifdef VERBOSE_libfirm
204 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
205 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
206 # endif /* def VERBOSE_libfirm */
208 /* enter in global list: */
214 Get (or create) the index for a given block
216 static int get_index (dt_t *dt, ir_node *block)
220 # ifdef DEBUG_libfirm
221 assert (dt && "no dt");
222 assert (block && "no block");
223 # endif /* def DEBUG_libfirm */
225 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
226 if (block == dt->blocks [i])
229 /* not found . . . enter new one: */
230 dt->blocks [i] = block;
231 if (block == get_irg_start_block (dt->graph))
233 dt->masks [i] = 0x00000001 << i;
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 */
242 dt->masks [i] = ~0x00000000;
244 # ifdef VERBOSE_libfirm
245 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
246 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
247 # endif /* def VERBOSE_libfirm */
254 Get the bit mask for a block
256 static bs_t _get_mask (dt_t*, int);
257 static bs_t get_mask (dt_t *dt, ir_node *block)
259 int index = get_index (dt, block);
261 # ifdef DEBUG_libfirm
262 assert (dt && "no dt");
263 assert (block && "no block");
264 # endif /* def DEBUG_libfirm */
266 return (_get_mask (dt, index));
270 Get the bit mask for a block index
272 static bs_t _get_mask (dt_t *dt, int index)
274 # ifdef DEBUG_libfirm
275 assert (dt && "no dt");
276 # endif /* def DEBUG_libfirm */
278 return (dt->masks [index]);
282 Set the bit mask for a block
285 static void _set_mask (dt_t*, int, bs_t);
286 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
288 int index = get_index (dt, block);
290 # ifdef DEBUG_libfirm
291 assert (dt && "no dt");
292 assert (block && "no block");
293 # endif /* def DEBUG_libfirm */
295 _set_mask (dt, index, mask);
299 Set the bit mask for a block index
301 static void _set_mask (dt_t *dt, int index, bs_t mask)
303 # ifdef DEBUG_libfirm
304 assert (dt && "no dt");
305 # endif /* def DEBUG_libfirm */
307 dt->masks [index] = mask;
311 Update the list of dominators of a given block
313 typedef struct dt_walk_env_t
315 dt_t *dt; /* the dominator relation we're building */
316 ir_node *start_block; /* need to know the start block of this graph */
317 bool changed; /* wether the relation has changed recently */
322 Helper function for build_dominator_tree
324 static void update_dominators (ir_node *block, void *env)
327 dt_walk_env_t *w = (dt_walk_env_t*) env;
330 int block_index = get_index (dt, block);
331 int n_ins = get_irn_arity (block);
333 bs_t old_mask = _get_mask (dt, block_index);
334 bs_t new_mask = ~0x00000000;
336 /* Special handling of Start Block: */
337 if (block == w->start_block)
341 for (i = 0; i < n_ins; i ++)
343 ir_node *in = get_nodes_block (get_irn_n (block, i));
344 bs_t in_mask = get_mask (dt, in);
349 /* and remember ourselves: */
350 new_mask |= (0x00000001 << block_index);
352 if (new_mask != old_mask)
355 _set_mask (dt, block_index, new_mask);
357 # ifdef VERBOSE_libfirm
358 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
359 __FILE__ ":" __PRETTY_FUNCTION__,
360 block, block_index, old_mask, new_mask);
361 # endif /* def VERBOSE_libfirm */
366 Say wether a dominates b
369 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
371 int index_a = get_index (dt, a);
372 bs_t b_mask = get_mask (dt, b);
374 return (0 != (b_mask & (0x00000001 << index_a)));
378 Return the immediate dominator of block a
380 static ir_node *_get_idom (dt_t *dt, ir_node *block)
383 int block_index = get_index (dt, block);
385 if (0 != (idom = dt->idoms [block_index]))
388 /* check all CFG preds:
389 Question: Shouldn't it be good enough to just ask our first CFG
393 int n = get_irn_arity (block);
396 idom = block; /* prime the loop: */
398 for (i = 0; i < n; i ++)
402 pred = get_nodes_block (get_irn_n (block, i));
403 ndom = _get_idom (dt, pred);
406 if (_dominates (dt, idom, ndom))
411 assert (idom && "Something terribly wrong in _get_idom");
413 # ifdef VERBOSE_libfirm
414 fprintf (stdout, "%s: idom(%p) = %p\n",
415 __FILE__ ":" __PRETTY_FUNCTION__,
417 # endif /* def VERBOSE_libfirm */
420 dt->idoms [block_index] = idom;
425 /* --------------------------------------------------------------------
427 * -------------------------------------------------------------------- */
430 Say wether a dominates b
432 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
434 dt_t *dt = get_dominator_tree (g);
436 return (_dominates (dt, a, b));
440 Return the immediate dominator of block a
442 ir_node *get_idom (ir_graph *g, ir_node *a)
444 dt_t *dt = get_dominator_tree (g);
446 return (_get_idom (dt, a));
450 Allow for precomputation of necessary data
451 This will allow for a slightly faster lookup of the dominator
452 relation if one node is checked for dominance against many other nodes.
454 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
456 dom_env_t *env = xcalloc(1, sizeof(*env));
459 env->dt = get_dominator_tree (graph);
461 env->index_a = get_index (env->dt, a);
466 Dispose a dominator environment
468 void delete_dom_env (dom_env_t *env)
479 Say wether the node in env dominates b
483 bool dominates_l (dom_env_t *env, ir_node *b)
485 int index_a = env->index_a;
487 bs_t b_mask = get_mask (dt, b);
489 return (0 != (b_mask & (0x00000001 << index_a)));
493 Build a new dominator tree for the given graph
495 void build_dominator_tree (ir_graph *graph)
498 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
500 ir_node *end_block = get_irg_end_block (graph);
501 ir_node *start_block = get_irg_start_block (graph);
502 int n_blocks = get_n_blocks (graph);
503 dt_t *dt = get_dominator_tree (graph);
506 dt_walk_env_t *w = 0;
507 ir_node *end_block = 0;
508 ir_node *start_block = 0;
512 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
513 end_block = get_irg_end_block (graph);
514 start_block = get_irg_start_block (graph);
515 n_blocks = get_n_blocks (graph);
516 dt = get_dominator_tree (graph);
518 # ifdef DEBUG_libfirm
519 assert (graph && "no graph");
520 # endif /* def DEBUG_libfirm */
522 # ifdef VERBOSE_libfirm
523 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
524 # endif /* def VERBOSE_libfirm */
532 w->start_block = start_block;
533 w->changed = true; /* at least one walk */
542 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
546 # ifdef VERBOSE_libfirm
547 fprintf (stdout, "%s: for graph(%p): %i passes\n",
548 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
549 # endif /* def VERBOSE_libfirm */
552 /* ok, now remember it: */
553 add_dominator_tree (dt);