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 /* we misuse the first for the size info of the out array */
74 return node->out[0].pos;
77 /* Access successor n */
78 ir_node *get_irn_out(ir_node *def, int pos) {
79 assert(pos >= 0 && pos < get_irn_n_outs(def));
81 /* assert(def->out_valid); */
82 #endif /* defined DEBUG_libfirm */
83 return def->out[pos+1].use;
86 /* Access successor n */
87 ir_node *get_irn_out_ex(ir_node *def, int pos, int *in_pos) {
88 assert(pos >= 0 && pos < get_irn_n_outs(def));
90 /* assert(def->out_valid); */
91 #endif /* defined DEBUG_libfirm */
92 *in_pos = def->out[pos+1].pos;
93 return def->out[pos+1].use;
96 void set_irn_out(ir_node *def, int pos, ir_node *use, int in_pos) {
98 assert(pos >= 0 && pos < get_irn_n_outs(def));
100 def->out_valid = 1; /* assume that this function is used correctly */
101 #endif /* defined DEBUG_libfirm */
102 def->out[pos+1].use = use;
103 def->out[pos+1].pos = in_pos;
106 /* Return the number of control flow successors, ignore keep-alives. */
107 int get_Block_n_cfg_outs(ir_node *bl) {
108 int i, n_cfg_outs = 0;
109 assert(bl && is_Block(bl));
111 assert(bl->out_valid);
112 #endif /* defined DEBUG_libfirm */
113 for (i = 1; i <= bl->out[0].pos; ++i) {
114 ir_node *succ = bl->out[i].use;
115 if (get_irn_mode(succ) == mode_X && !is_End(succ))
116 n_cfg_outs += succ->out[0].pos;
121 /* Return the number of control flow successors, honor keep-alives. */
122 int get_Block_n_cfg_outs_ka(ir_node *bl) {
123 int i, n_cfg_outs = 0;
124 assert(bl && is_Block(bl));
126 assert(bl->out_valid);
127 #endif /* defined DEBUG_libfirm */
128 for (i = 1; i <= bl->out[0].pos; ++i) {
129 ir_node *succ = bl->out[i].use;
130 if (get_irn_mode(succ) == mode_X) {
133 /* ignore End if we are in the Endblock */
134 if (get_nodes_block(succ) == bl)
136 else /* count Keep-alive as one */
139 n_cfg_outs += succ->out[0].pos;
145 /* Access predecessor n, ignore keep-alives. */
146 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
148 assert(bl && is_Block(bl));
150 assert(bl->out_valid);
151 #endif /* defined DEBUG_libfirm */
152 for (i = 1; i <= bl->out[0].pos; ++i) {
153 ir_node *succ = bl->out[i].use;
154 if (get_irn_mode(succ) == mode_X && !is_End(succ)) {
155 int n_outs = succ->out[0].pos;
157 return succ->out[pos + 1].use;
165 /* Access predecessor n, honor keep-alives. */
166 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
168 assert(bl && is_Block(bl));
170 assert (bl->out_valid);
171 #endif /* defined DEBUG_libfirm */
172 for (i = 1; i <= bl->out[0].pos; ++i) {
173 ir_node *succ = bl->out[i].use;
174 if (get_irn_mode(succ) == mode_X) {
176 ir_node *end_bl = get_nodes_block(succ);
178 /* ignore End if we are in the Endblock */
182 /* handle keep-alive here: return the Endblock instead of the End node */
187 n_outs = succ->out[0].pos;
189 return succ->out[pos + 1].use;
198 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
199 irg_walk_func *post, void *env) {
204 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
206 set_irn_visited(node, get_irg_visited(current_ir_graph));
208 if (pre) pre(node, env);
210 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
211 succ = get_irn_out(node, i);
212 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
213 irg_out_walk_2(succ, pre, post, env);
216 if (post) post(node, env);
219 void irg_out_walk(ir_node *node,
220 irg_walk_func *pre, irg_walk_func *post,
223 if (get_irg_outs_state(current_ir_graph) != outs_none) {
224 inc_irg_visited (current_ir_graph);
225 irg_out_walk_2(node, pre, post, env);
229 static void irg_out_block_walk2(ir_node *bl,
230 irg_walk_func *pre, irg_walk_func *post,
234 if (Block_not_block_visited(bl)) {
235 mark_Block_block_visited(bl);
240 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
241 /* find the corresponding predecessor block. */
242 ir_node *pred = get_Block_cfg_out(bl, i);
244 irg_out_block_walk2(pred, pre, post, env);
252 /* Walks only over Block nodes in the graph. Has it's own visited
253 flag, so that it can be interleaved with the other walker. */
254 void irg_out_block_walk(ir_node *node,
255 irg_walk_func *pre, irg_walk_func *post,
258 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
260 inc_irg_block_visited(current_ir_graph);
262 if (get_irn_mode(node) == mode_X) {
265 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
266 ir_node *succ = get_irn_out(node, i);
267 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
268 irg_out_walk_2(succ, pre, post, env);
272 irg_out_block_walk2(node, pre, post, env);
276 /*--------------------------------------------------------------------*/
277 /** Building and Removing the out datastructure **/
279 /** The outs of a graph are allocated in a single, large array. **/
280 /** This allows to allocate and deallocate the memory for the outs **/
281 /** on demand. The large array is separated into many small ones **/
282 /** for each node. Only a single field to reference the out array **/
283 /** is stored in each node and a field referencing the large out **/
284 /** array in irgraph. The 0 field of each out array contains the **/
285 /** size of this array. This saves memory in the irnodes themselves.**/
286 /** The construction does two passes over the graph. The first pass **/
287 /** counts the overall number of outs and the outs of each node. It **/
288 /** stores the outs of each node in the out reference of the node. **/
289 /** Then the large array is allocated. The second iteration chops **/
290 /** the large array into smaller parts, sets the out edges and **/
291 /** recounts the out edges. **/
292 /** Removes Tuple nodes! **/
293 /*--------------------------------------------------------------------*/
296 /** Returns the amount of out edges for not yet visited successors. */
297 static int _count_outs(ir_node *n) {
298 int start, i, res, irn_arity;
301 n->out = INT_TO_PTR(1); /* Space for array size. */
303 start = is_Block(n) ? 0 : -1;
304 irn_arity = get_irn_arity(n);
305 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
307 for (i = start; i < irn_arity; ++i) {
308 /* Optimize Tuples. They annoy if walking the cfg. */
309 ir_node *pred = get_irn_n(n, i);
310 ir_node *skipped_pred = skip_Tuple(pred);
312 if (skipped_pred != pred) {
313 set_irn_n(n, i, skipped_pred);
316 /* count Def-Use edges for predecessors */
317 if (irn_not_visited(skipped_pred))
318 res += _count_outs(skipped_pred);
320 /*count my Def-Use edges */
321 skipped_pred->out = INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1);
327 /** Returns the amount of out edges for not yet visited successors.
328 * This version handles some special nodes like irg_frame, irg_args etc.
330 static int count_outs(ir_graph *irg) {
334 inc_irg_visited(irg);
335 res = _count_outs(get_irg_end(irg));
337 /* Now handle anchored nodes. We need the out count of those
338 even if they are not visible. */
339 for (i = anchor_last - 1; i >= 0; --i) {
340 n = get_irg_anchor(irg, i);
341 if (irn_not_visited(n)) {
344 n->out = INT_TO_PTR(1);
352 * Enter memory for the outs to a node.
354 * @param use current node
355 * @param free current free address in the chunk allocated for the outs
357 * @return The next free address
359 static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) {
360 int n_outs, start, i, irn_arity, pos;
362 mark_irn_visited(use);
364 /* Allocate my array */
365 n_outs = PTR_TO_INT(use->out);
369 #endif /* defined DEBUG_libfirm */
371 /* We count the successors again, the space will be sufficient.
372 We use this counter to remember the position for the next back
376 start = is_Block(use) ? 0 : -1;
377 irn_arity = get_irn_arity(use);
379 for (i = start; i < irn_arity; ++i) {
380 ir_node *def = get_irn_n(use, i);
383 if (irn_not_visited(def))
384 free = _set_out_edges(def, free);
386 /* Remember this Def-Use edge */
387 pos = def->out[0].pos + 1;
388 def->out[pos].use = use;
389 def->out[pos].pos = i;
391 /* increase the number of Def-Use edges so far */
392 def->out[0].pos = pos;
398 * Enter memory for the outs to a node. Handles special nodes
400 * @param irg the graph
401 * @param free current free address in the chunk allocated for the outs
403 * @return The next free address
405 static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) {
409 inc_irg_visited(irg);
410 free = _set_out_edges(get_irg_end(irg), free);
412 /* handle anchored nodes */
413 for (i = anchor_last - 1; i >= 0; --i) {
414 n = get_irg_anchor(irg, i);
415 if (irn_not_visited(n)) {
418 n_outs = PTR_TO_INT(n->out);
422 #endif /* defined DEBUG_libfirm */
432 * We want that the out of ProjX from Start contains the next block at
433 * position 1, the Start block at position 2. This is necessary for
434 * the out block walker.
436 static INLINE void fix_start_proj(ir_graph *irg) {
437 ir_node *proj = NULL;
439 ir_node *startbl = get_irg_start_block(irg);
440 int i, block_pos, other_pos;
442 if (get_Block_n_cfg_outs(startbl)) {
443 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
444 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
445 proj = get_irn_out(startbl, i);
449 if (get_irn_out_ex(proj, 0, &block_pos) == startbl) {
450 assert(get_irn_n_outs(proj) == 2);
451 irn = get_irn_out_ex(proj, 1, &other_pos);
452 set_irn_out(proj, 0, irn, other_pos);
453 set_irn_out(proj, 1, startbl, block_pos);
458 /* compute the outs for a given graph */
459 void compute_irg_outs(ir_graph *irg) {
460 ir_graph *rem = current_ir_graph;
462 ir_def_use_edge *end = NULL; /* Only for debugging */
464 current_ir_graph = irg;
466 /* Update graph state */
467 assert(get_irg_phase_state(current_ir_graph) != phase_building);
469 if (current_ir_graph->outs_state != outs_none)
470 free_irg_outs(current_ir_graph);
472 /* This first iteration counts the overall number of out edges and the
473 number of out edges for each node. */
474 n_out_edges = count_outs(irg);
476 /* allocate memory for all out edges. */
477 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
479 irg->n_outs = n_out_edges;
480 #endif /* defined DEBUG_libfirm */
482 /* The second iteration splits the irg->outs array into smaller arrays
483 for each node and writes the back edges into this array. */
484 end = set_out_edges(irg, irg->outs);
486 /* Check how much memory we have used */
487 assert (end == (irg->outs + n_out_edges));
489 /* We want that the out of ProjX from Start contains the next block at
490 position 1, the Start block at position 2. This is necessary for
491 the out block walker. */
494 current_ir_graph->outs_state = outs_consistent;
495 current_ir_graph = rem;
498 void assure_irg_outs(ir_graph *irg) {
499 if (get_irg_outs_state(irg) != outs_consistent)
500 compute_irg_outs(irg);
503 void compute_irp_outs(void) {
505 for (i = get_irp_n_irgs() -1; i >= 0; --i)
506 compute_irg_outs(get_irp_irg(i));
509 void free_irp_outs(void) {
511 for (i = get_irp_n_irgs() -1; i >= 0; --i)
512 free_irg_outs(get_irp_irg(i));
516 /*------------------------------------------------------------*
517 * This computes the outedges for in interprocedural graph. *
518 * There is one quirk: *
519 * The number of the outedges for each node is saved in *
520 * the first member of the ir_node** array. Maybe we should *
521 * change this to make it more portable... *
522 *------------------------------------------------------------*/
525 #ifdef INTERPROCEDURAL_VIEW
527 * Inits the number of outedges for each node
530 static void init_count(ir_node * node, void *env) {
532 node->out = (ir_node **) 1; /* 1 for the array size */
537 * Adjusts the out edge count for its predecessors
538 * and adds the current arity to the overall count,
539 * which is saved in "env"
541 static void node_arity_count(ir_node * node, void * env) {
542 int *anz = (int *) env, arity, n_outs, i, start;
545 arity = get_irn_arity(node);
546 start = (is_Block(node)) ? 0 : -1;
548 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
551 for(i = start; i < arity; i++) {
552 succ = get_irn_n(node, i);
553 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
558 * Inits all nodes for setting the outedges
559 * Returns the overall count of edges
561 int count_ip_outs(void) {
564 cg_walk(init_count, node_arity_count, &res);
569 static int dummy_count = 0, global_count; /* Only for debugging */
572 * For each node: Sets the pointer to array
573 * in which the outedges are written later.
574 * The current array start is transported in env
576 static void set_array_pointer(ir_node *node, void *env) {
578 ir_node ***free = (ir_node ***) env;
580 /* Allocate my array */
581 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
582 dummy_count += n_outs;
583 assert(dummy_count <= global_count && "More outedges than initially counted!");
585 *free = &((*free)[n_outs]);
586 /* We count the successors again, the space will be sufficient.
587 We use this counter to remember the position for the next back
589 node -> out[0] = (ir_node *) 0;
594 * Adds an outedge from the predecessor to the
597 static void set_out_pointer(ir_node * node, void *env) {
598 int i, arity = get_irn_arity(node);
600 int start = (!is_Block(node)) ? -1 : 0;
603 for (i = start; i < arity; ++i) {
604 succ = get_irn_n(node, i);
605 succ->out[get_irn_n_outs(succ)+1] = node;
606 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
612 * Sets the outedges for all nodes.
614 void set_ip_outs(void) {
615 ir_node **outedge_array = get_irp_ip_outedges();
616 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
622 * Counts the outedges, allocates memory to save the
623 * outedges and fills this outedge array in interprocedural
626 void compute_ip_outs(void) {
630 assert(get_irp_ip_view_state() == ip_view_valid &&
631 "Cannot construct outs for invalid ip view.");
633 if (irp->outs_state != outs_none) {
637 global_count = n_out_edges = count_ip_outs();
638 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
639 set_irp_ip_outedges(out_edges);
643 void free_ip_outs(void) {
644 ir_node **out_edges = get_irp_ip_outedges();
645 if (out_edges != NULL) {
647 set_irp_ip_outedges(NULL);
649 irp->outs_state = outs_none;
654 void free_irg_outs(ir_graph *irg) {
655 /* current_ir_graph->outs_state = outs_none; */
656 irg->outs_state = outs_none;
660 memset(irg->outs, 0, irg->n_outs);
661 #endif /* defined DEBUG_libfirm */
666 #endif /* defined DEBUG_libfirm */
670 /* when debugging, *always* reset all nodes' outs! irg->outs might
671 have been lying to us */
672 irg_walk_graph (irg, reset_outs, NULL, NULL);
673 #endif /* defined DEBUG_libfirm */