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 * File name: ir/st/st.c
23 * Purpose: Provide some auxilliary structures for firm graphs.
24 * Author: Florian Liekweg
28 * Copyright: (c) 2002-2003 Universität Karlsruhe
35 provide some auxilliary structures for firm graphs.
58 /*static*/ dtree_t *trees = 0;
60 static dtree_t *last = 0;
63 /* --------------------------------------------------------------------
65 * -------------------------------------------------------------------- */
67 Helper function for get_n_blocks
69 static void count_block (ir_node *block, void *env)
74 assert (block && "no block");
75 assert (env && "no env");
76 # endif /* def DEBUG_libfirm */
78 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
79 __FILE__ ":count_block", (void *)block, *n);
85 Count the number of blocks in the given graph
87 static int get_n_blocks (ir_graph *graph)
91 ir_node *end_block = get_irg_end (graph);
94 assert (graph && "no graph");
95 assert (end_block && "no end block");
96 # endif /* def DEBUG_libfirm */
98 irg_block_walk (end_block, count_block, NULL, &n);
100 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
101 __FILE__ ":get_n_blocks", (void *)graph, n);
107 Build an empty dominator relation entry
109 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
111 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
113 # ifdef DEBUG_libfirm
114 assert (res && "no memory for dtree");
115 # endif /* def DEBUG_libfirm */
125 Build an empty dominator relation
127 static dt_t *new_dt (ir_graph *graph)
129 int n_blocks = get_n_blocks (graph);
131 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
133 # ifdef DEBUG_libfirm
134 assert (n_blocks && "no blocks for dt");
135 assert (res && "no memory for dt");
136 # endif /* def DEBUG_libfirm */
138 res->n_blocks = n_blocks;
140 res->blocks = xcalloc(n_blocks, sizeof(res->blocks[0]));
141 res->idoms = xcalloc(n_blocks, sizeof(res->idoms[0]));
142 res->masks = xcalloc(n_blocks, sizeof(res->masks[0]));
144 assert (res && "no dt");
149 static void free_dt (dt_t *dt)
151 free (dt->blocks); dt->blocks = 0;
152 free (dt->masks); dt->masks = 0;
157 /* --------------------------------------------------------------------
159 * -------------------------------------------------------------------- */
162 Given a graph, find its dominator tree in the global list:
164 @return The tree, if it exists, and 0 else
166 static dt_t *get_dominator_tree (ir_graph *graph)
168 dtree_t *iter = trees;
170 # ifdef DEBUG_libfirm
171 assert (graph && "no graph");
172 # endif /* def DEBUG_libfirm */
174 while ((0 != iter) && (graph != iter->graph))
179 # ifdef DEBUG_libfirm
180 assert ((graph == iter->tree->graph) && "wrong graph");
181 # endif /* def DEBUG_libfirm */
192 Given a dominator tree and a graph, enter the tree into the global list.
194 static void add_dominator_tree (dt_t *tree)
197 ir_graph *graph = tree->graph;
199 # ifdef DEBUG_libfirm
200 assert (tree && "no tree" );
201 assert (graph && "no graph");
202 # endif /* def DEBUG_libfirm */
204 dtree = new_dtree (tree, graph);
206 # ifdef VERBOSE_libfirm
207 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
208 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
209 # endif /* def VERBOSE_libfirm */
211 /* enter in global list: */
217 Get (or create) the index for a given block
219 static int get_index (dt_t *dt, ir_node *block)
223 # ifdef DEBUG_libfirm
224 assert (dt && "no dt");
225 assert (block && "no block");
226 # endif /* def DEBUG_libfirm */
228 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
229 if (block == dt->blocks [i])
232 /* not found . . . enter new one: */
233 dt->blocks [i] = block;
234 if (block == get_irg_start_block (dt->graph))
236 dt->masks [i] = 0x00000001 << i;
238 # ifdef VERBOSE_libfirm
239 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
240 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
241 # endif /* def VERBOSE_libfirm */
245 dt->masks [i] = ~0x00000000;
247 # ifdef VERBOSE_libfirm
248 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
249 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
250 # endif /* def VERBOSE_libfirm */
257 Get the bit mask for a block
259 static bs_t _get_mask (dt_t*, int);
260 static bs_t get_mask (dt_t *dt, ir_node *block)
262 int index = get_index (dt, block);
264 # ifdef DEBUG_libfirm
265 assert (dt && "no dt");
266 assert (block && "no block");
267 # endif /* def DEBUG_libfirm */
269 return (_get_mask (dt, index));
273 Get the bit mask for a block index
275 static bs_t _get_mask (dt_t *dt, int index)
277 # ifdef DEBUG_libfirm
278 assert (dt && "no dt");
279 # endif /* def DEBUG_libfirm */
281 return (dt->masks [index]);
285 Set the bit mask for a block
288 static void _set_mask (dt_t*, int, bs_t);
289 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
291 int index = get_index (dt, block);
293 # ifdef DEBUG_libfirm
294 assert (dt && "no dt");
295 assert (block && "no block");
296 # endif /* def DEBUG_libfirm */
298 _set_mask (dt, index, mask);
302 Set the bit mask for a block index
304 static void _set_mask (dt_t *dt, int index, bs_t mask)
306 # ifdef DEBUG_libfirm
307 assert (dt && "no dt");
308 # endif /* def DEBUG_libfirm */
310 dt->masks [index] = mask;
314 Update the list of dominators of a given block
316 typedef struct dt_walk_env_t
318 dt_t *dt; /* the dominator relation we're building */
319 ir_node *start_block; /* need to know the start block of this graph */
320 bool changed; /* wether the relation has changed recently */
325 Helper function for build_dominator_tree
327 static void update_dominators (ir_node *block, void *env)
330 dt_walk_env_t *w = (dt_walk_env_t*) env;
333 int block_index = get_index (dt, block);
334 int n_ins = get_irn_arity (block);
336 bs_t old_mask = _get_mask (dt, block_index);
337 bs_t new_mask = ~0x00000000;
339 /* Special handling of Start Block: */
340 if (block == w->start_block)
344 for (i = 0; i < n_ins; i ++)
346 ir_node *in = get_nodes_block (get_irn_n (block, i));
347 bs_t in_mask = get_mask (dt, in);
352 /* and remember ourselves: */
353 new_mask |= (0x00000001 << block_index);
355 if (new_mask != old_mask)
358 _set_mask (dt, block_index, new_mask);
360 # ifdef VERBOSE_libfirm
361 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
362 __FILE__ ":" __PRETTY_FUNCTION__,
363 block, block_index, old_mask, new_mask);
364 # endif /* def VERBOSE_libfirm */
369 Say wether a dominates b
372 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
374 int index_a = get_index (dt, a);
375 bs_t b_mask = get_mask (dt, b);
377 return (0 != (b_mask & (0x00000001 << index_a)));
381 Return the immediate dominator of block a
383 static ir_node *_get_idom (dt_t *dt, ir_node *block)
386 int block_index = get_index (dt, block);
388 if (0 != (idom = dt->idoms [block_index]))
391 /* check all CFG preds:
392 Question: Shouldn't it be good enough to just ask our first CFG
396 int n = get_irn_arity (block);
399 idom = block; /* prime the loop: */
401 for (i = 0; i < n; i ++)
405 pred = get_nodes_block (get_irn_n (block, i));
406 ndom = _get_idom (dt, pred);
409 if (_dominates (dt, idom, ndom))
414 assert (idom && "Something terribly wrong in _get_idom");
416 # ifdef VERBOSE_libfirm
417 fprintf (stdout, "%s: idom(%p) = %p\n",
418 __FILE__ ":" __PRETTY_FUNCTION__,
420 # endif /* def VERBOSE_libfirm */
423 dt->idoms [block_index] = idom;
428 /* --------------------------------------------------------------------
430 * -------------------------------------------------------------------- */
433 Say wether a dominates b
435 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
437 dt_t *dt = get_dominator_tree (g);
439 return (_dominates (dt, a, b));
443 Return the immediate dominator of block a
445 ir_node *get_idom (ir_graph *g, ir_node *a)
447 dt_t *dt = get_dominator_tree (g);
449 return (_get_idom (dt, a));
453 Allow for precomputation of necessary data
454 This will allow for a slightly faster lookup of the dominator
455 relation if one node is checked for dominance against many other nodes.
457 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
459 dom_env_t *env = xcalloc(1, sizeof(*env));
462 env->dt = get_dominator_tree (graph);
464 env->index_a = get_index (env->dt, a);
469 Dispose a dominator environment
471 void delete_dom_env (dom_env_t *env)
482 Say wether the node in env dominates b
486 bool dominates_l (dom_env_t *env, ir_node *b)
488 int index_a = env->index_a;
490 bs_t b_mask = get_mask (dt, b);
492 return (0 != (b_mask & (0x00000001 << index_a)));
496 Build a new dominator tree for the given graph
498 void build_dominator_tree (ir_graph *graph)
501 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
503 ir_node *end_block = get_irg_end_block (graph);
504 ir_node *start_block = get_irg_start_block (graph);
505 int n_blocks = get_n_blocks (graph);
506 dt_t *dt = get_dominator_tree (graph);
509 dt_walk_env_t *w = 0;
510 ir_node *end_block = 0;
511 ir_node *start_block = 0;
515 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
516 end_block = get_irg_end_block (graph);
517 start_block = get_irg_start_block (graph);
518 n_blocks = get_n_blocks (graph);
519 dt = get_dominator_tree (graph);
521 # ifdef DEBUG_libfirm
522 assert (graph && "no graph");
523 # endif /* def DEBUG_libfirm */
525 # ifdef VERBOSE_libfirm
526 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
527 # endif /* def VERBOSE_libfirm */
535 w->start_block = start_block;
536 w->changed = true; /* at least one walk */
545 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
549 # ifdef VERBOSE_libfirm
550 fprintf (stdout, "%s: for graph(%p): %i passes\n",
551 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
552 # endif /* def VERBOSE_libfirm */
555 /* ok, now remember it: */
556 add_dominator_tree (dt);