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 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 */
319 n = get_irg_frame(irg);
320 if (irn_not_visited(n)) {
321 n->out = (ir_node **)1;
325 n = get_irg_args(irg);
326 if (irn_not_visited(n)) {
327 n->out = (ir_node **)1;
335 * Enter memory for the outs to a node.
337 * @param n current node
338 * @param free current free address in the chunk allocated for the outs
340 * @return The next free address
342 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
343 int n_outs, start, i, irn_arity;
346 set_irn_visited(n, get_irg_visited(current_ir_graph));
348 /* Allocate my array */
349 n_outs = PTR_TO_INT(n->out);
353 #endif /* defined DEBUG_libfirm */
355 /* We count the successors again, the space will be sufficient.
356 We use this counter to remember the position for the next back
358 n->out[0] = (ir_node *)0;
360 start = is_Block(n) ? 0 : -1;
361 irn_arity = get_irn_arity(n);
363 for (i = start; i < irn_arity; ++i) {
364 pred = get_irn_n(n, i);
366 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
367 free = _set_out_edges(pred, free);
368 /* Remember our back edge */
369 pred->out[get_irn_n_outs(pred)+1] = n;
370 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
376 * Enter memory for the outs to a node. Handles special nodes
378 * @param irg the graph
379 * @param free current free address in the chunk allocated for the outs
381 * @return The next free address
383 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
384 ir_node *n, *special[2];
387 inc_irg_visited(irg);
388 free = _set_out_edges(get_irg_end(irg), free);
390 /* handle special nodes */
391 special[0] = get_irg_frame(irg);
392 special[1] = get_irg_args(irg);
394 for (i = 1; i >= 0; --i) {
397 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
398 n_outs = PTR_TO_INT(n->out);
402 #endif /* defined DEBUG_libfirm */
412 * We want that the out of ProjX from Start contains the next block at
413 * position 1, the Start block at position 2. This is necessary for
414 * the out block walker.
416 static INLINE void fix_start_proj(ir_graph *irg) {
417 ir_node *proj = NULL;
418 ir_node *startbl = get_irg_start_block(irg);
421 if (get_Block_n_cfg_outs(startbl)) {
422 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
423 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
424 proj = get_irn_out(startbl, i);
428 if (get_irn_out(proj, 0) == startbl) {
429 assert(get_irn_n_outs(proj) == 2);
430 set_irn_out(proj, 0, get_irn_out(proj, 1));
431 set_irn_out(proj, 1, startbl);
436 /* compute the outs for a given graph */
437 void compute_irg_outs(ir_graph *irg) {
438 ir_graph *rem = current_ir_graph;
440 ir_node **end = NULL; /* Only for debugging */
442 current_ir_graph = irg;
444 /* Update graph state */
445 assert(get_irg_phase_state(current_ir_graph) != phase_building);
447 if (current_ir_graph->outs_state != outs_none)
448 free_irg_outs(current_ir_graph);
450 /* This first iteration counts the overall number of out edges and the
451 number of out edges for each node. */
452 n_out_edges = count_outs(irg);
454 /* allocate memory for all out edges. */
455 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
457 irg->n_outs = n_out_edges;
458 #endif /* defined DEBUG_libfirm */
460 /* The second iteration splits the irg->outs array into smaller arrays
461 for each node and writes the back edges into this array. */
462 end = set_out_edges(irg, irg->outs);
464 /* Check how much memory we have used */
465 assert (end == (irg->outs + n_out_edges));
467 /* We want that the out of ProjX from Start contains the next block at
468 position 1, the Start block at position 2. This is necessary for
469 the out block walker. */
472 current_ir_graph->outs_state = outs_consistent;
473 current_ir_graph = rem;
476 void assure_irg_outs(ir_graph *irg) {
477 if (get_irg_outs_state(irg) != outs_consistent)
478 compute_irg_outs(irg);
481 void compute_irp_outs(void) {
483 for (i = get_irp_n_irgs() -1; i >= 0; --i)
484 compute_irg_outs(get_irp_irg(i));
487 void free_irp_outs(void) {
489 for (i = get_irp_n_irgs() -1; i >= 0; --i)
490 free_irg_outs(get_irp_irg(i));
494 /*------------------------------------------------------------*
495 * This computes the outedges for in interprocedural graph. *
496 * There is one quirk: *
497 * The number of the outedges for each node is saved in *
498 * the first member of the ir_node** array. Maybe we should *
499 * change this to make it more portable... *
500 *------------------------------------------------------------*/
503 #ifdef INTERPROCEDURAL_VIEW
505 * Inits the number of outedges for each node
508 static void init_count(ir_node * node, void *env) {
510 node->out = (ir_node **) 1; /* 1 for the array size */
515 * Adjusts the out edge count for its predecessors
516 * and adds the current arity to the overall count,
517 * which is saved in "env"
519 static void node_arity_count(ir_node * node, void * env) {
520 int *anz = (int *) env, arity, n_outs, i, start;
523 arity = get_irn_arity(node);
524 start = (is_Block(node)) ? 0 : -1;
526 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
529 for(i = start; i < arity; i++) {
530 succ = get_irn_n(node, i);
531 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
536 * Inits all nodes for setting the outedges
537 * Returns the overall count of edges
539 int count_ip_outs(void) {
542 cg_walk(init_count, node_arity_count, &res);
547 static int dummy_count = 0, global_count; /* Only for debugging */
550 * For each node: Sets the pointer to array
551 * in which the outedges are written later.
552 * The current array start is transported in env
554 static void set_array_pointer(ir_node *node, void *env) {
556 ir_node ***free = (ir_node ***) env;
558 /* Allocate my array */
559 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
560 dummy_count += n_outs;
561 assert(dummy_count <= global_count && "More outedges than initially counted!");
563 *free = &((*free)[n_outs]);
564 /* We count the successors again, the space will be sufficient.
565 We use this counter to remember the position for the next back
567 node -> out[0] = (ir_node *) 0;
572 * Adds an outedge from the predecessor to the
575 static void set_out_pointer(ir_node * node, void *env) {
576 int i, arity = get_irn_arity(node);
578 int start = (!is_Block(node)) ? -1 : 0;
581 for (i = start; i < arity; ++i) {
582 succ = get_irn_n(node, i);
583 succ->out[get_irn_n_outs(succ)+1] = node;
584 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
590 * Sets the outedges for all nodes.
592 void set_ip_outs(void) {
593 ir_node **outedge_array = get_irp_ip_outedges();
594 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
600 * Counts the outedges, allocates memory to save the
601 * outedges and fills this outedge array in interprocedural
604 void compute_ip_outs(void) {
608 assert(get_irp_ip_view_state() == ip_view_valid &&
609 "Cannot construct outs for invalid ip view.");
611 if (irp->outs_state != outs_none) {
615 global_count = n_out_edges = count_ip_outs();
616 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
617 set_irp_ip_outedges(out_edges);
621 void free_ip_outs(void) {
622 ir_node **out_edges = get_irp_ip_outedges();
623 if (out_edges != NULL) {
625 set_irp_ip_outedges(NULL);
627 irp->outs_state = outs_none;
632 void free_irg_outs(ir_graph *irg) {
633 /* current_ir_graph->outs_state = outs_none; */
634 irg->outs_state = outs_none;
638 memset(irg->outs, 0, irg->n_outs);
639 #endif /* defined DEBUG_libfirm */
644 #endif /* defined DEBUG_libfirm */
648 /* when debugging, *always* reset all nodes' outs! irg->outs might
649 have been lying to us */
650 irg_walk_graph (irg, reset_outs, NULL, NULL);
651 #endif /* defined DEBUG_libfirm */