1 /* Copyright (c) 2002 by Universität Karlsruhe (TH). All Rights Reserved */
3 // Time-stamp: <Monday, 13.05.2002, 13:27:22 goetz@i44pc2.info.uni-karlsruhe.de>
10 provide some auxilliary structures for firm graphs.
14 liekweg - Feb 26, 2002: Created.
25 # endif /* def DEBUG_libfirm */
29 static dtree_t *trees = 0;
30 static dtree_t *last = 0;
32 // --------------------------------------------------------------------
34 // --------------------------------------------------------------------
36 Helper function for get_n_blocks
38 static void count_block (ir_node *block, void *env)
43 assert (block && "no block");
44 assert (env && "no env");
45 # endif /* def DEBUG_libfirm */
47 fprintf (stdout, "%s: Block(%p) has # (%i)\n",
48 __FILE__ ":" __PRETTY_FUNCTION__, block, *n);
54 Count the number of blocks in the given graph
56 static int get_n_blocks (ir_graph *graph)
60 ir_node *end_block = get_irg_end (graph);
63 assert (graph && "no graph");
64 assert (end_block && "no end block");
65 # endif /* def DEBUG_libfirm */
67 irg_block_walk (end_block, count_block, NULL, &n);
68 // irg_block_walk (end_block, NULL, NULL, NULL);
72 fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
73 __FILE__ ":" __PRETTY_FUNCTION__, graph, n);
79 Build an empty dominator relation entry
81 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
83 dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
86 assert (res && "no memory for dtree");
87 # endif /* def DEBUG_libfirm */
97 Build an empty dominator relation
99 static dt_t *new_dt (ir_graph *graph)
102 int n_blocks = get_n_blocks (graph);
104 dt_t *res = (dt_t*) malloc (sizeof (dt_t));
106 # ifdef DEBUG_libfirm
107 assert (n_blocks && "no blocks for dt");
108 assert (res && "no memory for dt");
109 # endif /* def DEBUG_libfirm */
111 res->n_blocks = n_blocks;
113 res->blocks = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
114 res->idoms = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
115 res->masks = (bs_t*) calloc (n_blocks, sizeof (bs_t));
117 assert (res && "no dt");
122 static void free_dt (dt_t *dt)
124 free (dt->blocks); dt->blocks = 0;
125 free (dt->masks); dt->masks = 0;
130 // --------------------------------------------------------------------
132 // --------------------------------------------------------------------
135 Given a graph, find its dominator tree in the global list:
137 @return The tree, if it exists, and 0 else
139 static dt_t *get_dominator_tree (ir_graph *graph)
141 dtree_t *iter = trees;
143 # ifdef DEBUG_libfirm
144 assert (graph && "no graph");
145 // assert (iter && "no trees");
146 # endif /* def DEBUG_libfirm */
148 while ((0 != iter) && (graph != iter->graph))
153 # ifdef DEBUG_libfirm
154 assert ((graph == iter->tree->graph) && "wrong graph");
155 # endif /* def DEBUG_libfirm */
166 Given a dominator tree and a graph, enter the tree into the global list.
168 static void add_dominator_tree (dt_t *tree)
171 ir_graph *graph = tree->graph;
173 # ifdef DEBUG_libfirm
174 assert (tree && "no tree" );
175 assert (graph && "no graph");
176 # endif /* def DEBUG_libfirm */
178 dtree = new_dtree (tree, graph);
180 # ifdef VERBOSE_libfirm
181 fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
182 __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
183 # endif /* def VERBOSE_libfirm */
185 //enter in global list:
191 Get (or create) the index for a given block
193 static int get_index (dt_t *dt, ir_node *block)
197 # ifdef DEBUG_libfirm
198 assert (dt && "no dt");
199 assert (block && "no block");
200 # endif /* def DEBUG_libfirm */
202 for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
203 if (block == dt->blocks [i])
206 /* not found . . . enter new one: */
207 dt->blocks [i] = block;
208 if (block == get_irg_start_block (dt->graph))
210 dt->masks [i] = 0x00000001 << i;
212 # ifdef VERBOSE_libfirm
213 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
214 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
215 # endif /* def VERBOSE_libfirm */
219 dt->masks [i] = ~0x00000000;
221 # ifdef VERBOSE_libfirm
222 fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
223 __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
224 # endif /* def VERBOSE_libfirm */
231 Get the bit mask for a block
233 static bs_t _get_mask (dt_t*, int);
234 static bs_t get_mask (dt_t *dt, ir_node *block)
236 int index = get_index (dt, block);
238 # ifdef DEBUG_libfirm
239 assert (dt && "no dt");
240 assert (block && "no block");
241 # endif /* def DEBUG_libfirm */
243 return (_get_mask (dt, index));
247 Get the bit mask for a block index
249 static bs_t _get_mask (dt_t *dt, int index)
251 # ifdef DEBUG_libfirm
252 assert (dt && "no dt");
253 # endif /* def DEBUG_libfirm */
255 return (dt->masks [index]);
259 Set the bit mask for a block
261 static void _set_mask (dt_t*, int, bs_t);
262 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
264 int index = get_index (dt, block);
266 # ifdef DEBUG_libfirm
267 assert (dt && "no dt");
268 assert (block && "no block");
269 # endif /* def DEBUG_libfirm */
271 _set_mask (dt, index, mask);
275 Set the bit mask for a block index
277 static void _set_mask (dt_t *dt, int index, bs_t mask)
279 # ifdef DEBUG_libfirm
280 assert (dt && "no dt");
281 # endif /* def DEBUG_libfirm */
283 dt->masks [index] = mask;
287 Update the list of dominators of a given block
289 typedef struct dt_walk_env_t // grrr
291 dt_t *dt; // the dominator relation we're building
292 ir_node *start_block; // need to know the start block of this graph
293 bool changed; // wether the relation has changed recently
298 Helper function for build_dominator_tree
300 static void update_dominators (ir_node *block, void *env)
303 dt_walk_env_t *w = (dt_walk_env_t*) env;
306 int block_index = get_index (dt, block);
307 int n_ins = get_irn_arity (block);
309 bs_t old_mask = _get_mask (dt, block_index);
310 bs_t new_mask = ~0x00000000;
312 // Special handling of Start Block:
313 if (block == w->start_block)
317 for (i = 0; i < n_ins; i ++)
319 ir_node *in = get_nodes_Block (get_irn_n (block, i)); // hope that's the block
320 bs_t in_mask = get_mask (dt, in);
325 // and remember ourselves:
326 new_mask |= (0x00000001 << block_index);
328 if (new_mask != old_mask)
331 _set_mask (dt, block_index, new_mask);
333 # ifdef VERBOSE_libfirm
334 fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
335 __FILE__ ":" __PRETTY_FUNCTION__,
336 block, block_index, old_mask, new_mask);
337 # endif /* def VERBOSE_libfirm */
342 Say wether a dominates b
345 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
347 int index_a = get_index (dt, a);
348 bs_t b_mask = get_mask (dt, b);
350 return (0 != (b_mask & (0x00000001 << index_a)));
354 Return the immediate dominator of block a
356 static ir_node *_get_idom (dt_t *dt, ir_node *block)
359 int block_index = get_index (dt, block);
361 if (0 != (idom = dt->idoms [block_index]))
364 // check all CFG preds:
365 // Question: Shouldn't it be good enough to just ask our first CFG predecessor?
368 int n = get_irn_arity (block);
371 idom = block; // prime the loop:
373 for (i = 0; i < n; i ++)
377 pred = get_nodes_Block (get_irn_n (block, i));
378 ndom = _get_idom (dt, pred);
381 if (_dominates (dt, idom, ndom))
386 assert (idom && "Something terribly wrong in _get_idom");
388 # ifdef VERBOSE_libfirm
389 fprintf (stdout, "%s: idom(%p) = %p\n",
390 __FILE__ ":" __PRETTY_FUNCTION__,
392 # endif /* def VERBOSE_libfirm */
395 dt->idoms [block_index] = idom;
400 // --------------------------------------------------------------------
402 // --------------------------------------------------------------------
405 Say wether a dominates b
407 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
409 dt_t *dt = get_dominator_tree (g);
411 return (_dominates (dt, a, b));
415 Return the immediate dominator of block a
417 ir_node *get_idom (ir_graph *g, ir_node *a)
419 dt_t *dt = get_dominator_tree (g);
421 return (_get_idom (dt, a));
425 Allow for precomputation of necessary data
426 This will allow for a slightly faster lookup of the dominator
427 relation if one node is checked for dominance against many other nodes.
429 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
431 dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t));
434 env->dt = get_dominator_tree (graph);
436 env->index_a = get_index (env->dt, a);
441 Dispose a dominator environment
443 void delete_dom_env (dom_env_t *env)
454 Say wether the node in env dominates b
458 bool dominates_l (dom_env_t *env, ir_node *b)
460 int index_a = env->index_a;
462 bs_t b_mask = get_mask (dt, b);
464 return (0 != (b_mask & (0x00000001 << index_a)));
468 Build a new dominator tree for the given graph
470 void build_dominator_tree (ir_graph *graph)
473 dt_walk_env_t *w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
475 ir_node *end_block = get_irg_end_block (graph);
476 ir_node *start_block = get_irg_start_block (graph);
477 int n_blocks = get_n_blocks (graph);
478 dt_t *dt = get_dominator_tree (graph);
481 dt_walk_env_t *w = 0;
482 ir_node *end_block = 0;
483 ir_node *start_block = 0;
487 w = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
488 end_block = get_irg_end_block (graph);
489 start_block = get_irg_start_block (graph);
490 n_blocks = get_n_blocks (graph);
491 dt = get_dominator_tree (graph);
493 # ifdef DEBUG_libfirm
494 assert (graph && "no graph");
495 # endif /* def DEBUG_libfirm */
497 # ifdef VERBOSE_libfirm
498 fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
499 # endif /* def VERBOSE_libfirm */
507 w->start_block = start_block; // grrr
508 w->changed = TRUE; // at least one walk
517 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
521 # ifdef VERBOSE_libfirm
522 fprintf (stdout, "%s: for graph(%p): %i passes\n",
523 __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
524 # endif /* def VERBOSE_libfirm */
527 /* ok, now remember it: */
528 add_dominator_tree (dt);