2 * Copyright (C) 1995-2008 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 Compute and access out edges (also called def-use edges).
23 * @author Goetz Lindenmaier, Michael Beck
38 #include "irgraph_t.h"
44 /* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
45 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
46 when compiling with neither DEBUG_libfirm or NDEBUG defined */
47 #endif /* defined DEBUG_libfirm */
49 /*--------------------------------------------------------------------*/
50 /** Accessing the out datastructures **/
51 /*--------------------------------------------------------------------*/
54 /** Clear the outs of a node */
55 static void reset_outs(ir_node *node, void *unused) {
62 /* returns the number of successors of the node: */
63 int get_irn_n_outs(ir_node *node) {
64 assert(node && node->kind == k_ir_node);
66 /* assert(node->out_valid); */
67 #endif /* defined DEBUG_libfirm */
68 return PTR_TO_INT(node->out[0]);
71 /* Access successor n */
72 ir_node *get_irn_out(ir_node *node, int pos) {
73 assert(pos >= 0 && pos < get_irn_n_outs(node));
75 /* assert(node->out_valid); */
76 #endif /* defined DEBUG_libfirm */
77 return node->out[pos+1];
80 void set_irn_out(ir_node *node, int pos, ir_node *out) {
82 assert(pos >= 0 && pos < get_irn_n_outs(node));
84 node->out_valid = 1; /* assume that this function is used correctly */
85 #endif /* defined DEBUG_libfirm */
86 node->out[pos+1] = out;
89 /* Return the number of control flow successors, ignore keep-alives. */
90 int get_Block_n_cfg_outs(ir_node *bl) {
91 int i, n_cfg_outs = 0;
92 assert(bl && is_Block(bl));
94 assert(bl->out_valid);
95 #endif /* defined DEBUG_libfirm */
96 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
97 ir_node *succ = bl->out[i];
98 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End)
99 n_cfg_outs += PTR_TO_INT(succ->out[0]);
104 /* Return the number of control flow successors, honor keep-alives. */
105 int get_Block_n_cfg_outs_ka(ir_node *bl) {
106 int i, n_cfg_outs = 0;
107 assert(bl && is_Block(bl));
109 assert(bl->out_valid);
110 #endif /* defined DEBUG_libfirm */
111 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
112 ir_node *succ = bl->out[i];
113 if (get_irn_mode(succ) == mode_X) {
115 if (get_irn_op(succ) == op_End) {
116 /* ignore End if we are in the Endblock */
117 if (get_irn_n(succ, -1) == bl)
119 else /* count Keep-alive as one */
122 n_cfg_outs += PTR_TO_INT(succ->out[0]);
128 /* Access predecessor n, ignore keep-alives. */
129 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
131 assert(bl && is_Block(bl));
133 assert (bl->out_valid);
134 #endif /* defined DEBUG_libfirm */
135 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
136 ir_node *succ = bl->out[i];
137 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End) {
138 int n_outs = PTR_TO_INT(succ->out[0]);
140 return succ->out[pos + 1];
148 /* Access predecessor n, honor keep-alives. */
149 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
151 assert(bl && is_Block(bl));
153 assert (bl->out_valid);
154 #endif /* defined DEBUG_libfirm */
155 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
156 ir_node *succ = bl->out[i];
157 if (get_irn_mode(succ) == mode_X) {
158 if (get_irn_op(succ) == op_End) {
159 if (get_irn_n(succ, -1) == bl) {
160 /* ignore End if we are in the Endblock */
164 /* handle keep-alive here: return the Endblock instead of the End node */
165 return get_irn_n(succ, -1);
169 n_outs = PTR_TO_INT(succ->out[0]);
171 return succ->out[pos + 1];
180 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
181 irg_walk_func *post, void *env) {
186 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
188 set_irn_visited(node, get_irg_visited(current_ir_graph));
190 if (pre) pre(node, env);
192 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
193 succ = get_irn_out(node, i);
194 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
195 irg_out_walk_2(succ, pre, post, env);
198 if (post) post(node, env);
203 void irg_out_walk(ir_node *node,
204 irg_walk_func *pre, irg_walk_func *post,
207 if (get_irg_outs_state(current_ir_graph) != outs_none) {
208 inc_irg_visited (current_ir_graph);
209 irg_out_walk_2(node, pre, post, env);
214 static void irg_out_block_walk2(ir_node *bl,
215 irg_walk_func *pre, irg_walk_func *post,
219 if (Block_not_block_visited(bl)) {
220 mark_Block_block_visited(bl);
225 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
226 /* find the corresponding predecessor block. */
227 ir_node *pred = get_Block_cfg_out(bl, i);
229 irg_out_block_walk2(pred, pre, post, env);
237 /* Walks only over Block nodes in the graph. Has it's own visited
238 flag, so that it can be interleaved with the other walker. */
239 void irg_out_block_walk(ir_node *node,
240 irg_walk_func *pre, irg_walk_func *post,
243 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
245 inc_irg_block_visited(current_ir_graph);
247 if (get_irn_mode(node) == mode_X) {
250 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
251 ir_node *succ = get_irn_out(node, i);
252 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
253 irg_out_walk_2(succ, pre, post, env);
257 irg_out_block_walk2(node, pre, post, env);
261 /*--------------------------------------------------------------------*/
262 /** Building and Removing the out datastructure **/
264 /** The outs of a graph are allocated in a single, large array. **/
265 /** This allows to allocate and deallocate the memory for the outs **/
266 /** on demand. The large array is separated into many small ones **/
267 /** for each node. Only a single field to reference the out array **/
268 /** is stored in each node and a field referencing the large out **/
269 /** array in irgraph. The 0 field of each out array contains the **/
270 /** size of this array. This saves memory in the irnodes themselves.**/
271 /** The construction does two passes over the graph. The first pass **/
272 /** counts the overall number of outs and the outs of each node. It **/
273 /** stores the outs of each node in the out reference of the node. **/
274 /** Then the large array is allocated. The second iteration chops **/
275 /** the large array into smaller parts, sets the out edges and **/
276 /** recounts the out edges. **/
277 /** Removes Tuple nodes! **/
278 /*--------------------------------------------------------------------*/
281 /** Returns the amount of out edges for not yet visited successors. */
282 static int _count_outs(ir_node *n) {
283 int start, i, res, irn_arity;
286 n->out = (ir_node **) 1; /* Space for array size. */
288 start = is_Block(n) ? 0 : -1;
289 irn_arity = get_irn_arity(n);
290 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
292 for (i = start; i < irn_arity; ++i) {
293 /* Optimize Tuples. They annoy if walking the cfg. */
294 ir_node *pred = skip_Tuple(get_irn_n(n, i));
295 set_irn_n(n, i, pred);
297 /* count outs for successors */
298 if (irn_not_visited(pred))
299 res += _count_outs(pred);
302 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
308 /** Returns the amount of out edges for not yet visited successors.
309 * This version handles some special nodes like irg_frame, irg_args etc.
311 static int count_outs(ir_graph *irg) {
315 inc_irg_visited(irg);
316 res = _count_outs(get_irg_end(irg));
318 /* Now handle special nodes. We need the out count of those
319 even if they are not visible. */
320 n = get_irg_frame(irg);
321 if (! is_Bad(n) && irn_not_visited(n)) {
322 n->out = (ir_node **)1;
326 n = get_irg_args(irg);
327 if (! is_Bad(n) && irn_not_visited(n)) {
328 n->out = (ir_node **)1;
332 n = get_irg_value_param_base(irg);
333 if (! is_Bad(n) && irn_not_visited(n)) {
334 n->out = (ir_node **)1;
342 * Enter memory for the outs to a node.
344 * @param n current node
345 * @param free current free address in the chunk allocated for the outs
347 * @return The next free address
349 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
350 int n_outs, start, i, irn_arity;
353 set_irn_visited(n, get_irg_visited(current_ir_graph));
355 /* Allocate my array */
356 n_outs = PTR_TO_INT(n->out);
360 #endif /* defined DEBUG_libfirm */
362 /* We count the successors again, the space will be sufficient.
363 We use this counter to remember the position for the next back
365 n->out[0] = (ir_node *)0;
367 start = is_Block(n) ? 0 : -1;
368 irn_arity = get_irn_arity(n);
370 for (i = start; i < irn_arity; ++i) {
371 pred = get_irn_n(n, i);
373 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
374 free = _set_out_edges(pred, free);
375 /* Remember our back edge */
376 pred->out[get_irn_n_outs(pred)+1] = n;
377 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
383 * Enter memory for the outs to a node. Handles special nodes
385 * @param irg the graph
386 * @param free current free address in the chunk allocated for the outs
388 * @return The next free address
390 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
391 ir_node *n, *special[3];
394 inc_irg_visited(irg);
395 free = _set_out_edges(get_irg_end(irg), free);
397 /* handle special nodes */
398 special[0] = get_irg_frame(irg);
399 special[1] = get_irg_args(irg);
400 special[2] = get_irg_value_param_base(irg);
402 for (i = 2; i >= 0; --i) {
407 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
408 n_outs = PTR_TO_INT(n->out);
412 #endif /* defined DEBUG_libfirm */
422 * We want that the out of ProjX from Start contains the next block at
423 * position 1, the Start block at position 2. This is necessary for
424 * the out block walker.
426 static INLINE void fix_start_proj(ir_graph *irg) {
427 ir_node *proj = NULL;
428 ir_node *startbl = get_irg_start_block(irg);
431 if (get_Block_n_cfg_outs(startbl)) {
432 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
433 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
434 proj = get_irn_out(startbl, i);
438 if (get_irn_out(proj, 0) == startbl) {
439 assert(get_irn_n_outs(proj) == 2);
440 set_irn_out(proj, 0, get_irn_out(proj, 1));
441 set_irn_out(proj, 1, startbl);
446 /* compute the outs for a given graph */
447 void compute_irg_outs(ir_graph *irg) {
448 ir_graph *rem = current_ir_graph;
450 ir_node **end = NULL; /* Only for debugging */
452 current_ir_graph = irg;
454 /* Update graph state */
455 assert(get_irg_phase_state(current_ir_graph) != phase_building);
457 if (current_ir_graph->outs_state != outs_none)
458 free_irg_outs(current_ir_graph);
460 /* This first iteration counts the overall number of out edges and the
461 number of out edges for each node. */
462 n_out_edges = count_outs(irg);
464 /* allocate memory for all out edges. */
465 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
467 irg->n_outs = n_out_edges;
468 #endif /* defined DEBUG_libfirm */
470 /* The second iteration splits the irg->outs array into smaller arrays
471 for each node and writes the back edges into this array. */
472 end = set_out_edges(irg, irg->outs);
474 /* Check how much memory we have used */
475 assert (end == (irg->outs + n_out_edges));
477 /* We want that the out of ProjX from Start contains the next block at
478 position 1, the Start block at position 2. This is necessary for
479 the out block walker. */
482 current_ir_graph->outs_state = outs_consistent;
483 current_ir_graph = rem;
486 void assure_irg_outs(ir_graph *irg) {
487 if (get_irg_outs_state(irg) != outs_consistent)
488 compute_irg_outs(irg);
491 void compute_irp_outs(void) {
493 for (i = get_irp_n_irgs() -1; i >= 0; --i)
494 compute_irg_outs(get_irp_irg(i));
497 void free_irp_outs(void) {
499 for (i = get_irp_n_irgs() -1; i >= 0; --i)
500 free_irg_outs(get_irp_irg(i));
504 /*------------------------------------------------------------*
505 * This computes the outedges for in interprocedural graph. *
506 * There is one quirk: *
507 * The number of the outedges for each node is saved in *
508 * the first member of the ir_node** array. Maybe we should *
509 * change this to make it more portable... *
510 *------------------------------------------------------------*/
513 #ifdef INTERPROCEDURAL_VIEW
515 * Inits the number of outedges for each node
518 static void init_count(ir_node * node, void *env) {
520 node->out = (ir_node **) 1; /* 1 for the array size */
525 * Adjusts the out edge count for its predecessors
526 * and adds the current arity to the overall count,
527 * which is saved in "env"
529 static void node_arity_count(ir_node * node, void * env) {
530 int *anz = (int *) env, arity, n_outs, i, start;
533 arity = get_irn_arity(node);
534 start = (is_Block(node)) ? 0 : -1;
536 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
539 for(i = start; i < arity; i++) {
540 succ = get_irn_n(node, i);
541 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
546 * Inits all nodes for setting the outedges
547 * Returns the overall count of edges
549 int count_ip_outs(void) {
552 cg_walk(init_count, node_arity_count, &res);
557 static int dummy_count = 0, global_count; /* Only for debugging */
560 * For each node: Sets the pointer to array
561 * in which the outedges are written later.
562 * The current array start is transported in env
564 static void set_array_pointer(ir_node *node, void *env) {
566 ir_node ***free = (ir_node ***) env;
568 /* Allocate my array */
569 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
570 dummy_count += n_outs;
571 assert(dummy_count <= global_count && "More outedges than initially counted!");
573 *free = &((*free)[n_outs]);
574 /* We count the successors again, the space will be sufficient.
575 We use this counter to remember the position for the next back
577 node -> out[0] = (ir_node *) 0;
582 * Adds an outedge from the predecessor to the
585 static void set_out_pointer(ir_node * node, void *env) {
586 int i, arity = get_irn_arity(node);
588 int start = (!is_Block(node)) ? -1 : 0;
591 for (i = start; i < arity; ++i) {
592 succ = get_irn_n(node, i);
593 succ->out[get_irn_n_outs(succ)+1] = node;
594 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
600 * Sets the outedges for all nodes.
602 void set_ip_outs(void) {
603 ir_node **outedge_array = get_irp_ip_outedges();
604 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
610 * Counts the outedges, allocates memory to save the
611 * outedges and fills this outedge array in interprocedural
614 void compute_ip_outs(void) {
618 assert(get_irp_ip_view_state() == ip_view_valid &&
619 "Cannot construct outs for invalid ip view.");
621 if (irp->outs_state != outs_none) {
625 global_count = n_out_edges = count_ip_outs();
626 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
627 set_irp_ip_outedges(out_edges);
631 void free_ip_outs(void) {
632 ir_node **out_edges = get_irp_ip_outedges();
633 if (out_edges != NULL) {
635 set_irp_ip_outedges(NULL);
637 irp->outs_state = outs_none;
642 void free_irg_outs(ir_graph *irg) {
643 /* current_ir_graph->outs_state = outs_none; */
644 irg->outs_state = outs_none;
648 memset(irg->outs, 0, irg->n_outs);
649 #endif /* defined DEBUG_libfirm */
654 #endif /* defined DEBUG_libfirm */
658 /* when debugging, *always* reset all nodes' outs! irg->outs might
659 have been lying to us */
660 irg_walk_graph (irg, reset_outs, NULL, NULL);
661 #endif /* defined DEBUG_libfirm */