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) {
114 /* ignore End if we are in the Endblock */
115 if (get_irn_op(succ) == op_End &&
116 get_irn_n(succ, -1) == bl)
119 n_cfg_outs += PTR_TO_INT(succ->out[0]);
125 /* Access predecessor n, ignore keep-alives. */
126 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
128 assert(bl && is_Block(bl));
130 assert (bl->out_valid);
131 #endif /* defined DEBUG_libfirm */
132 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
133 ir_node *succ = bl->out[i];
134 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End) {
135 int n_outs = PTR_TO_INT(succ->out[0]);
137 return succ->out[pos + 1];
145 /* Access predecessor n, honor keep-alives. */
146 ir_node *get_Block_cfg_out_ka(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 <= PTR_TO_INT(bl->out[0]); ++i) {
153 ir_node *succ = bl->out[i];
154 if (get_irn_mode(succ) == mode_X) {
155 /* ignore End if we are in the Endblock */
156 if (get_irn_op(succ) == op_End && get_irn_n(succ, -1) == bl)
158 n_outs = PTR_TO_INT(succ->out[0]);
160 /* handle keep-alive here: return the Endblock instead of the End node */
161 if (get_irn_op(succ) == op_End)
162 return get_irn_n(succ, -1);
163 return succ->out[pos + 1];
171 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
172 irg_walk_func *post, void *env) {
177 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
179 set_irn_visited(node, get_irg_visited(current_ir_graph));
181 if (pre) pre(node, env);
183 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
184 succ = get_irn_out(node, i);
185 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
186 irg_out_walk_2(succ, pre, post, env);
189 if (post) post(node, env);
194 void irg_out_walk(ir_node *node,
195 irg_walk_func *pre, irg_walk_func *post,
198 if (get_irg_outs_state(current_ir_graph) != outs_none) {
199 inc_irg_visited (current_ir_graph);
200 irg_out_walk_2(node, pre, post, env);
205 static void irg_out_block_walk2(ir_node *bl,
206 irg_walk_func *pre, irg_walk_func *post,
210 if (Block_not_block_visited(bl)) {
211 mark_Block_block_visited(bl);
216 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
217 /* find the corresponding predecessor block. */
218 ir_node *pred = get_Block_cfg_out(bl, i);
220 irg_out_block_walk2(pred, pre, post, env);
228 /* Walks only over Block nodes in the graph. Has it's own visited
229 flag, so that it can be interleaved with the other walker. */
230 void irg_out_block_walk(ir_node *node,
231 irg_walk_func *pre, irg_walk_func *post,
234 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
236 inc_irg_block_visited(current_ir_graph);
238 if (get_irn_mode(node) == mode_X) {
241 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
242 ir_node *succ = get_irn_out(node, i);
243 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
244 irg_out_walk_2(succ, pre, post, env);
248 irg_out_block_walk2(node, pre, post, env);
252 /*--------------------------------------------------------------------*/
253 /** Building and Removing the out datastructure **/
255 /** The outs of a graph are allocated in a single, large array. **/
256 /** This allows to allocate and deallocate the memory for the outs **/
257 /** on demand. The large array is separated into many small ones **/
258 /** for each node. Only a single field to reference the out array **/
259 /** is stored in each node and a field referencing the large out **/
260 /** array in irgraph. The 0 field of each out array contains the **/
261 /** size of this array. This saves memory in the irnodes themselves.**/
262 /** The construction does two passes over the graph. The first pass **/
263 /** counts the overall number of outs and the outs of each node. It **/
264 /** stores the outs of each node in the out reference of the node. **/
265 /** Then the large array is allocated. The second iteration chops **/
266 /** the large array into smaller parts, sets the out edges and **/
267 /** recounts the out edges. **/
268 /** Removes Tuple nodes! **/
269 /*--------------------------------------------------------------------*/
272 /** Returns the amount of out edges for not yet visited successors. */
273 static int _count_outs(ir_node *n) {
274 int start, i, res, irn_arity;
277 n->out = (ir_node **) 1; /* Space for array size. */
279 start = is_Block(n) ? 0 : -1;
280 irn_arity = get_irn_arity(n);
281 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
283 for (i = start; i < irn_arity; ++i) {
284 /* Optimize Tuples. They annoy if walking the cfg. */
285 ir_node *pred = skip_Tuple(get_irn_n(n, i));
286 set_irn_n(n, i, pred);
288 /* count outs for successors */
289 if (irn_not_visited(pred))
290 res += _count_outs(pred);
293 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
299 /** Returns the amount of out edges for not yet visited successors.
300 * This version handles some special nodes like irg_frame, irg_args etc.
302 static int count_outs(ir_graph *irg) {
306 inc_irg_visited(irg);
307 res = _count_outs(get_irg_end(irg));
309 /* now handle special nodes */
310 n = get_irg_frame(irg);
311 if (irn_not_visited(n)) {
312 n->out = (ir_node **)1;
316 n = get_irg_args(irg);
317 if (irn_not_visited(n)) {
318 n->out = (ir_node **)1;
326 * Enter memory for the outs to a node.
328 * @param n current node
329 * @param free current free address in the chunk allocated for the outs
331 * @return The next free address
333 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
334 int n_outs, start, i, irn_arity;
337 set_irn_visited(n, get_irg_visited(current_ir_graph));
339 /* Allocate my array */
340 n_outs = PTR_TO_INT(n->out);
344 #endif /* defined DEBUG_libfirm */
346 /* We count the successors again, the space will be sufficient.
347 We use this counter to remember the position for the next back
349 n->out[0] = (ir_node *)0;
351 start = is_Block(n) ? 0 : -1;
352 irn_arity = get_irn_arity(n);
354 for (i = start; i < irn_arity; ++i) {
355 pred = get_irn_n(n, i);
357 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
358 free = _set_out_edges(pred, free);
359 /* Remember our back edge */
360 pred->out[get_irn_n_outs(pred)+1] = n;
361 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
367 * Enter memory for the outs to a node. Handles special nodes
369 * @param irg the graph
370 * @param free current free address in the chunk allocated for the outs
372 * @return The next free address
374 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
375 ir_node *n, *special[2];
378 inc_irg_visited(irg);
379 free = _set_out_edges(get_irg_end(irg), free);
381 /* handle special nodes */
382 special[0] = get_irg_frame(irg);
383 special[1] = get_irg_args(irg);
385 for (i = 1; i >= 0; --i) {
388 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
389 n_outs = PTR_TO_INT(n->out);
393 #endif /* defined DEBUG_libfirm */
403 * We want that the out of ProjX from Start contains the next block at
404 * position 1, the Start block at position 2. This is necessary for
405 * the out block walker.
407 static INLINE void fix_start_proj(ir_graph *irg) {
408 ir_node *proj = NULL;
409 ir_node *startbl = get_irg_start_block(irg);
412 if (get_Block_n_cfg_outs(startbl)) {
413 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
414 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
415 proj = get_irn_out(startbl, i);
419 if (get_irn_out(proj, 0) == startbl) {
420 assert(get_irn_n_outs(proj) == 2);
421 set_irn_out(proj, 0, get_irn_out(proj, 1));
422 set_irn_out(proj, 1, startbl);
427 /* compute the outs for a given graph */
428 void compute_irg_outs(ir_graph *irg) {
429 ir_graph *rem = current_ir_graph;
431 ir_node **end = NULL; /* Only for debugging */
433 current_ir_graph = irg;
435 /* Update graph state */
436 assert(get_irg_phase_state(current_ir_graph) != phase_building);
438 if (current_ir_graph->outs_state != outs_none)
439 free_irg_outs(current_ir_graph);
441 /* This first iteration counts the overall number of out edges and the
442 number of out edges for each node. */
443 n_out_edges = count_outs(irg);
445 /* allocate memory for all out edges. */
446 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
448 irg->n_outs = n_out_edges;
449 #endif /* defined DEBUG_libfirm */
451 /* The second iteration splits the irg->outs array into smaller arrays
452 for each node and writes the back edges into this array. */
453 end = set_out_edges(irg, irg->outs);
455 /* Check how much memory we have used */
456 assert (end == (irg->outs + n_out_edges));
458 /* We want that the out of ProjX from Start contains the next block at
459 position 1, the Start block at position 2. This is necessary for
460 the out block walker. */
463 current_ir_graph->outs_state = outs_consistent;
464 current_ir_graph = rem;
467 void assure_irg_outs(ir_graph *irg) {
468 if (get_irg_outs_state(irg) != outs_consistent)
469 compute_irg_outs(irg);
472 void compute_irp_outs(void) {
474 for (i = get_irp_n_irgs() -1; i >= 0; --i)
475 compute_irg_outs(get_irp_irg(i));
478 void free_irp_outs(void) {
480 for (i = get_irp_n_irgs() -1; i >= 0; --i)
481 free_irg_outs(get_irp_irg(i));
485 /*------------------------------------------------------------*
486 * This computes the outedges for in interprocedural graph. *
487 * There is one quirk: *
488 * The number of the outedges for each node is saved in *
489 * the first member of the ir_node** array. Maybe we should *
490 * change this to make it more portable... *
491 *------------------------------------------------------------*/
495 * Inits the number of outedges for each node
498 static void init_count(ir_node * node, void *env) {
500 node->out = (ir_node **) 1; /* 1 for the array size */
505 * Adjusts the out edge count for its predecessors
506 * and adds the current arity to the overall count,
507 * which is saved in "env"
509 static void node_arity_count(ir_node * node, void * env) {
510 int *anz = (int *) env, arity, n_outs, i, start;
513 arity = get_irn_arity(node);
514 start = (is_Block(node)) ? 0 : -1;
516 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
519 for(i = start; i < arity; i++) {
520 succ = get_irn_n(node, i);
521 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
527 * Inits all nodes for setting the outedges
528 * Returns the overall count of edges
530 int count_ip_outs(void) {
533 cg_walk(init_count, node_arity_count, &res);
538 static int dummy_count = 0, global_count; /* Only for debugging */
541 * For each node: Sets the pointer to array
542 * in which the outedges are written later.
543 * The current array start is transported in env
545 static void set_array_pointer(ir_node *node, void *env) {
547 ir_node ***free = (ir_node ***) env;
549 /* Allocate my array */
550 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
551 dummy_count += n_outs;
552 assert(dummy_count <= global_count && "More outedges than initially counted!");
554 *free = &((*free)[n_outs]);
555 /* We count the successors again, the space will be sufficient.
556 We use this counter to remember the position for the next back
558 node -> out[0] = (ir_node *) 0;
563 * Adds an outedge from the predecessor to the
566 static void set_out_pointer(ir_node * node, void *env) {
567 int i, arity = get_irn_arity(node);
569 int start = (!is_Block(node)) ? -1 : 0;
572 for (i = start; i < arity; ++i) {
573 succ = get_irn_n(node, i);
574 succ->out[get_irn_n_outs(succ)+1] = node;
575 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
581 * Sets the outedges for all nodes.
583 void set_ip_outs(void) {
584 ir_node **outedge_array = get_irp_ip_outedges();
585 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
591 * Counts the outedges, allocates memory to save the
592 * outedges and fills this outedge array in interprocedural
595 void compute_ip_outs(void) {
599 assert(get_irp_ip_view_state() == ip_view_valid &&
600 "Cannot construct outs for invalid ip view.");
602 if (irp->outs_state != outs_none) {
606 global_count = n_out_edges = count_ip_outs();
607 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
608 set_irp_ip_outedges(out_edges);
612 void free_ip_outs(void) {
613 ir_node **out_edges = get_irp_ip_outedges();
614 if (out_edges != NULL) {
616 set_irp_ip_outedges(NULL);
618 irp->outs_state = outs_none;
622 void free_irg_outs(ir_graph *irg) {
623 /* current_ir_graph->outs_state = outs_none; */
624 irg->outs_state = outs_none;
628 memset(irg->outs, 0, irg->n_outs);
629 #endif /* defined DEBUG_libfirm */
634 #endif /* defined DEBUG_libfirm */
638 /* when debugging, *always* reset all nodes' outs! irg->outs might
639 have been lying to us */
640 irg_walk_graph (irg, reset_outs, NULL, NULL);
641 #endif /* defined DEBUG_libfirm */