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 int get_irn_outs_computed(const ir_node *node)
64 return node->out != NULL;
67 /* returns the number of successors of the node: */
68 int get_irn_n_outs(ir_node *node) {
69 assert(node && node->kind == k_ir_node);
71 /* assert(node->out_valid); */
72 #endif /* defined DEBUG_libfirm */
73 return PTR_TO_INT(node->out[0]);
76 /* Access successor n */
77 ir_node *get_irn_out(ir_node *node, int pos) {
78 assert(pos >= 0 && pos < get_irn_n_outs(node));
80 /* assert(node->out_valid); */
81 #endif /* defined DEBUG_libfirm */
82 return node->out[pos+1];
85 void set_irn_out(ir_node *node, int pos, ir_node *out) {
87 assert(pos >= 0 && pos < get_irn_n_outs(node));
89 node->out_valid = 1; /* assume that this function is used correctly */
90 #endif /* defined DEBUG_libfirm */
91 node->out[pos+1] = out;
94 /* Return the number of control flow successors, ignore keep-alives. */
95 int get_Block_n_cfg_outs(ir_node *bl) {
96 int i, n_cfg_outs = 0;
97 assert(bl && is_Block(bl));
99 assert(bl->out_valid);
100 #endif /* defined DEBUG_libfirm */
101 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
102 ir_node *succ = bl->out[i];
103 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End)
104 n_cfg_outs += PTR_TO_INT(succ->out[0]);
109 /* Return the number of control flow successors, honor keep-alives. */
110 int get_Block_n_cfg_outs_ka(ir_node *bl) {
111 int i, n_cfg_outs = 0;
112 assert(bl && is_Block(bl));
114 assert(bl->out_valid);
115 #endif /* defined DEBUG_libfirm */
116 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
117 ir_node *succ = bl->out[i];
118 if (get_irn_mode(succ) == mode_X) {
120 if (get_irn_op(succ) == op_End) {
121 /* ignore End if we are in the Endblock */
122 if (get_irn_n(succ, -1) == bl)
124 else /* count Keep-alive as one */
127 n_cfg_outs += PTR_TO_INT(succ->out[0]);
133 /* Access predecessor n, ignore keep-alives. */
134 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
136 assert(bl && is_Block(bl));
138 assert (bl->out_valid);
139 #endif /* defined DEBUG_libfirm */
140 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
141 ir_node *succ = bl->out[i];
142 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End) {
143 int n_outs = PTR_TO_INT(succ->out[0]);
145 return succ->out[pos + 1];
153 /* Access predecessor n, honor keep-alives. */
154 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
156 assert(bl && is_Block(bl));
158 assert (bl->out_valid);
159 #endif /* defined DEBUG_libfirm */
160 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
161 ir_node *succ = bl->out[i];
162 if (get_irn_mode(succ) == mode_X) {
163 if (get_irn_op(succ) == op_End) {
164 if (get_irn_n(succ, -1) == bl) {
165 /* ignore End if we are in the Endblock */
169 /* handle keep-alive here: return the Endblock instead of the End node */
170 return get_irn_n(succ, -1);
174 n_outs = PTR_TO_INT(succ->out[0]);
176 return succ->out[pos + 1];
185 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
186 irg_walk_func *post, void *env) {
191 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
193 set_irn_visited(node, get_irg_visited(current_ir_graph));
195 if (pre) pre(node, env);
197 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
198 succ = get_irn_out(node, i);
199 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
200 irg_out_walk_2(succ, pre, post, env);
203 if (post) post(node, env);
208 void irg_out_walk(ir_node *node,
209 irg_walk_func *pre, irg_walk_func *post,
212 if (get_irg_outs_state(current_ir_graph) != outs_none) {
213 inc_irg_visited (current_ir_graph);
214 irg_out_walk_2(node, pre, post, env);
219 static void irg_out_block_walk2(ir_node *bl,
220 irg_walk_func *pre, irg_walk_func *post,
224 if (Block_not_block_visited(bl)) {
225 mark_Block_block_visited(bl);
230 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
231 /* find the corresponding predecessor block. */
232 ir_node *pred = get_Block_cfg_out(bl, i);
234 irg_out_block_walk2(pred, pre, post, env);
242 /* Walks only over Block nodes in the graph. Has it's own visited
243 flag, so that it can be interleaved with the other walker. */
244 void irg_out_block_walk(ir_node *node,
245 irg_walk_func *pre, irg_walk_func *post,
248 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
250 inc_irg_block_visited(current_ir_graph);
252 if (get_irn_mode(node) == mode_X) {
255 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
256 ir_node *succ = get_irn_out(node, i);
257 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
258 irg_out_walk_2(succ, pre, post, env);
262 irg_out_block_walk2(node, pre, post, env);
266 /*--------------------------------------------------------------------*/
267 /** Building and Removing the out datastructure **/
269 /** The outs of a graph are allocated in a single, large array. **/
270 /** This allows to allocate and deallocate the memory for the outs **/
271 /** on demand. The large array is separated into many small ones **/
272 /** for each node. Only a single field to reference the out array **/
273 /** is stored in each node and a field referencing the large out **/
274 /** array in irgraph. The 0 field of each out array contains the **/
275 /** size of this array. This saves memory in the irnodes themselves.**/
276 /** The construction does two passes over the graph. The first pass **/
277 /** counts the overall number of outs and the outs of each node. It **/
278 /** stores the outs of each node in the out reference of the node. **/
279 /** Then the large array is allocated. The second iteration chops **/
280 /** the large array into smaller parts, sets the out edges and **/
281 /** recounts the out edges. **/
282 /** Removes Tuple nodes! **/
283 /*--------------------------------------------------------------------*/
286 /** Returns the amount of out edges for not yet visited successors. */
287 static int _count_outs(ir_node *n) {
288 int start, i, res, irn_arity;
291 n->out = (ir_node **) 1; /* Space for array size. */
293 start = is_Block(n) ? 0 : -1;
294 irn_arity = get_irn_arity(n);
295 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
297 for (i = start; i < irn_arity; ++i) {
298 /* Optimize Tuples. They annoy if walking the cfg. */
299 ir_node *pred = skip_Tuple(get_irn_n(n, i));
300 set_irn_n(n, i, pred);
302 /* count outs for successors */
303 if (irn_not_visited(pred))
304 res += _count_outs(pred);
307 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
313 /** Returns the amount of out edges for not yet visited successors.
314 * This version handles some special nodes like irg_frame, irg_args etc.
316 static int count_outs(ir_graph *irg) {
320 inc_irg_visited(irg);
321 res = _count_outs(get_irg_end(irg));
323 /* Now handle special nodes. We need the out count of those
324 even if they are not visible. */
325 n = get_irg_frame(irg);
326 if (! is_Bad(n) && irn_not_visited(n)) {
327 n->out = (ir_node **)1;
331 n = get_irg_args(irg);
332 if (! is_Bad(n) && irn_not_visited(n)) {
333 n->out = (ir_node **)1;
337 n = get_irg_value_param_base(irg);
338 if (! is_Bad(n) && irn_not_visited(n)) {
339 n->out = (ir_node **)1;
347 * Enter memory for the outs to a node.
349 * @param n current node
350 * @param free current free address in the chunk allocated for the outs
352 * @return The next free address
354 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
355 int n_outs, start, i, irn_arity;
358 set_irn_visited(n, get_irg_visited(current_ir_graph));
360 /* Allocate my array */
361 n_outs = PTR_TO_INT(n->out);
365 #endif /* defined DEBUG_libfirm */
367 /* We count the successors again, the space will be sufficient.
368 We use this counter to remember the position for the next back
370 n->out[0] = (ir_node *)0;
372 start = is_Block(n) ? 0 : -1;
373 irn_arity = get_irn_arity(n);
375 for (i = start; i < irn_arity; ++i) {
376 pred = get_irn_n(n, i);
378 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
379 free = _set_out_edges(pred, free);
380 /* Remember our back edge */
381 pred->out[get_irn_n_outs(pred)+1] = n;
382 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
388 * Enter memory for the outs to a node. Handles special nodes
390 * @param irg the graph
391 * @param free current free address in the chunk allocated for the outs
393 * @return The next free address
395 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
396 ir_node *n, *special[3];
399 inc_irg_visited(irg);
400 free = _set_out_edges(get_irg_end(irg), free);
402 /* handle special nodes */
403 special[0] = get_irg_frame(irg);
404 special[1] = get_irg_args(irg);
405 special[2] = get_irg_value_param_base(irg);
407 for (i = 2; i >= 0; --i) {
412 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
413 n_outs = PTR_TO_INT(n->out);
417 #endif /* defined DEBUG_libfirm */
427 * We want that the out of ProjX from Start contains the next block at
428 * position 1, the Start block at position 2. This is necessary for
429 * the out block walker.
431 static INLINE void fix_start_proj(ir_graph *irg) {
432 ir_node *proj = NULL;
433 ir_node *startbl = get_irg_start_block(irg);
436 if (get_Block_n_cfg_outs(startbl)) {
437 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
438 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
439 proj = get_irn_out(startbl, i);
443 if (get_irn_out(proj, 0) == startbl) {
444 assert(get_irn_n_outs(proj) == 2);
445 set_irn_out(proj, 0, get_irn_out(proj, 1));
446 set_irn_out(proj, 1, startbl);
451 /* compute the outs for a given graph */
452 void compute_irg_outs(ir_graph *irg) {
453 ir_graph *rem = current_ir_graph;
455 ir_node **end = NULL; /* Only for debugging */
457 current_ir_graph = irg;
459 /* Update graph state */
460 assert(get_irg_phase_state(current_ir_graph) != phase_building);
462 if (current_ir_graph->outs_state != outs_none)
463 free_irg_outs(current_ir_graph);
465 /* This first iteration counts the overall number of out edges and the
466 number of out edges for each node. */
467 n_out_edges = count_outs(irg);
469 /* allocate memory for all out edges. */
470 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
472 irg->n_outs = n_out_edges;
473 #endif /* defined DEBUG_libfirm */
475 /* The second iteration splits the irg->outs array into smaller arrays
476 for each node and writes the back edges into this array. */
477 end = set_out_edges(irg, irg->outs);
479 /* Check how much memory we have used */
480 assert (end == (irg->outs + n_out_edges));
482 /* We want that the out of ProjX from Start contains the next block at
483 position 1, the Start block at position 2. This is necessary for
484 the out block walker. */
487 current_ir_graph->outs_state = outs_consistent;
488 current_ir_graph = rem;
491 void assure_irg_outs(ir_graph *irg) {
492 if (get_irg_outs_state(irg) != outs_consistent)
493 compute_irg_outs(irg);
496 void compute_irp_outs(void) {
498 for (i = get_irp_n_irgs() -1; i >= 0; --i)
499 compute_irg_outs(get_irp_irg(i));
502 void free_irp_outs(void) {
504 for (i = get_irp_n_irgs() -1; i >= 0; --i)
505 free_irg_outs(get_irp_irg(i));
509 /*------------------------------------------------------------*
510 * This computes the outedges for in interprocedural graph. *
511 * There is one quirk: *
512 * The number of the outedges for each node is saved in *
513 * the first member of the ir_node** array. Maybe we should *
514 * change this to make it more portable... *
515 *------------------------------------------------------------*/
518 #ifdef INTERPROCEDURAL_VIEW
520 * Inits the number of outedges for each node
523 static void init_count(ir_node * node, void *env) {
525 node->out = (ir_node **) 1; /* 1 for the array size */
530 * Adjusts the out edge count for its predecessors
531 * and adds the current arity to the overall count,
532 * which is saved in "env"
534 static void node_arity_count(ir_node * node, void * env) {
535 int *anz = (int *) env, arity, n_outs, i, start;
538 arity = get_irn_arity(node);
539 start = (is_Block(node)) ? 0 : -1;
541 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
544 for(i = start; i < arity; i++) {
545 succ = get_irn_n(node, i);
546 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
551 * Inits all nodes for setting the outedges
552 * Returns the overall count of edges
554 int count_ip_outs(void) {
557 cg_walk(init_count, node_arity_count, &res);
562 static int dummy_count = 0, global_count; /* Only for debugging */
565 * For each node: Sets the pointer to array
566 * in which the outedges are written later.
567 * The current array start is transported in env
569 static void set_array_pointer(ir_node *node, void *env) {
571 ir_node ***free = (ir_node ***) env;
573 /* Allocate my array */
574 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
575 dummy_count += n_outs;
576 assert(dummy_count <= global_count && "More outedges than initially counted!");
578 *free = &((*free)[n_outs]);
579 /* We count the successors again, the space will be sufficient.
580 We use this counter to remember the position for the next back
582 node -> out[0] = (ir_node *) 0;
587 * Adds an outedge from the predecessor to the
590 static void set_out_pointer(ir_node * node, void *env) {
591 int i, arity = get_irn_arity(node);
593 int start = (!is_Block(node)) ? -1 : 0;
596 for (i = start; i < arity; ++i) {
597 succ = get_irn_n(node, i);
598 succ->out[get_irn_n_outs(succ)+1] = node;
599 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
605 * Sets the outedges for all nodes.
607 void set_ip_outs(void) {
608 ir_node **outedge_array = get_irp_ip_outedges();
609 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
615 * Counts the outedges, allocates memory to save the
616 * outedges and fills this outedge array in interprocedural
619 void compute_ip_outs(void) {
623 assert(get_irp_ip_view_state() == ip_view_valid &&
624 "Cannot construct outs for invalid ip view.");
626 if (irp->outs_state != outs_none) {
630 global_count = n_out_edges = count_ip_outs();
631 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
632 set_irp_ip_outedges(out_edges);
636 void free_ip_outs(void) {
637 ir_node **out_edges = get_irp_ip_outedges();
638 if (out_edges != NULL) {
640 set_irp_ip_outedges(NULL);
642 irp->outs_state = outs_none;
647 void free_irg_outs(ir_graph *irg) {
648 /* current_ir_graph->outs_state = outs_none; */
649 irg->outs_state = outs_none;
653 memset(irg->outs, 0, irg->n_outs);
654 #endif /* defined DEBUG_libfirm */
659 #endif /* defined DEBUG_libfirm */
663 /* when debugging, *always* reset all nodes' outs! irg->outs might
664 have been lying to us */
665 irg_walk_graph (irg, reset_outs, NULL, NULL);
666 #endif /* defined DEBUG_libfirm */