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 if ((get_irn_mode(bl->out[i]) == mode_X) &&
98 (get_irn_op(bl->out[i]) != op_End))
103 /* Return the number of control flow successors, honor keep-alives. */
104 int get_Block_n_cfg_outs_ka(ir_node *bl) {
105 int i, n_cfg_outs = 0;
106 assert(bl && is_Block(bl));
108 assert(bl->out_valid);
109 #endif /* defined DEBUG_libfirm */
110 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
111 if (get_irn_mode(bl->out[i]) == mode_X) {
112 /* ignore End if we are in the Endblock */
113 if (get_irn_op(bl->out[i]) == op_End &&
114 get_irn_n(bl->out[i], -1) == bl)
122 /* Access predecessor n, ignore keep-alives. */
123 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
125 assert(bl && is_Block(bl));
127 assert (bl->out_valid);
128 #endif /* defined DEBUG_libfirm */
129 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
130 if ((get_irn_mode(bl->out[i]) == mode_X) &&
131 (get_irn_op(bl->out[i]) != op_End)) {
132 if (out_pos == pos) {
133 ir_node *cfop = bl->out[i];
141 /* Access predecessor n, honor keep-alives. */
142 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
144 assert(bl && is_Block(bl));
146 assert (bl->out_valid);
147 #endif /* defined DEBUG_libfirm */
148 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
149 if (get_irn_mode(bl->out[i]) == mode_X) {
150 /* ignore End if we are in the Endblock */
151 if (get_irn_op(bl->out[i]) == op_End &&
152 get_irn_n(bl->out[i], -1) == bl)
154 if (out_pos == pos) {
155 ir_node *cfop = bl->out[i];
156 /* handle keep-alive here */
157 if (get_irn_op(cfop) == op_End)
158 return get_irn_n(cfop, -1);
166 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
167 irg_walk_func *post, void *env) {
172 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
174 set_irn_visited(node, get_irg_visited(current_ir_graph));
176 if (pre) pre(node, env);
178 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
179 succ = get_irn_out(node, i);
180 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
181 irg_out_walk_2(succ, pre, post, env);
184 if (post) post(node, env);
189 void irg_out_walk(ir_node *node,
190 irg_walk_func *pre, irg_walk_func *post,
193 if (get_irg_outs_state(current_ir_graph) != outs_none) {
194 inc_irg_visited (current_ir_graph);
195 irg_out_walk_2(node, pre, post, env);
200 static void irg_out_block_walk2(ir_node *bl,
201 irg_walk_func *pre, irg_walk_func *post,
205 if (Block_not_block_visited(bl)) {
206 mark_Block_block_visited(bl);
211 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
212 /* find the corresponding predecessor block. */
213 ir_node *pred = get_Block_cfg_out(bl, i);
215 irg_out_block_walk2(pred, pre, post, env);
223 /* Walks only over Block nodes in the graph. Has it's own visited
224 flag, so that it can be interleaved with the other walker. */
225 void irg_out_block_walk(ir_node *node,
226 irg_walk_func *pre, irg_walk_func *post,
229 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
231 inc_irg_block_visited(current_ir_graph);
233 if (get_irn_mode(node) == mode_X)
236 irg_out_block_walk2(node, pre, post, env);
239 /*--------------------------------------------------------------------*/
240 /** Building and Removing the out datasturcture **/
242 /** The outs of a graph are allocated in a single, large array. **/
243 /** This allows to allocate and deallocate the memory for the outs **/
244 /** on demand. The large array is separated into many small ones **/
245 /** for each node. Only a single field to reference the out array **/
246 /** is stored in each node and a field referencing the large out **/
247 /** array in irgraph. The 0 field of each out array contains the **/
248 /** size of this array. This saves memory in the irnodes themselves.**/
249 /** The construction does two passes over the graph. The first pass **/
250 /** counts the overall number of outs and the outs of each node. It **/
251 /** stores the outs of each node in the out reference of the node. **/
252 /** Then the large array is allocated. The second iteration chops **/
253 /** the large array into smaller parts, sets the out edges and **/
254 /** recounts the out edges. **/
255 /** Removes Tuple nodes! **/
256 /*--------------------------------------------------------------------*/
259 /** Returns the amount of out edges for not yet visited successors. */
260 static int _count_outs(ir_node *n) {
261 int start, i, res, irn_arity;
264 n->out = (ir_node **) 1; /* Space for array size. */
266 start = is_Block(n) ? 0 : -1;
267 irn_arity = get_irn_arity(n);
268 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
270 for (i = start; i < irn_arity; ++i) {
271 /* Optimize Tuples. They annoy if walking the cfg. */
272 ir_node *pred = skip_Tuple(get_irn_n(n, i));
273 set_irn_n(n, i, pred);
275 /* count outs for successors */
276 if (irn_not_visited(pred))
277 res += _count_outs(pred);
280 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
286 /** Returns the amount of out edges for not yet visited successors.
287 * This version handles some special nodes like irg_frame, irg_args etc.
289 static int count_outs(ir_graph *irg) {
293 inc_irg_visited(irg);
294 res = _count_outs(get_irg_end(irg));
296 /* now handle special nodes */
297 n = get_irg_frame(irg);
298 if (irn_not_visited(n)) {
299 n->out = (ir_node **)1;
303 n = get_irg_args(irg);
304 if (irn_not_visited(n)) {
305 n->out = (ir_node **)1;
313 * Enter memory for the outs to a node.
315 * @param n current node
316 * @param free current free address in the chunk allocated for the outs
318 * @return The next free address
320 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
321 int n_outs, start, i, irn_arity;
324 set_irn_visited(n, get_irg_visited(current_ir_graph));
326 /* Allocate my array */
327 n_outs = PTR_TO_INT(n->out);
331 #endif /* defined DEBUG_libfirm */
333 /* We count the successors again, the space will be sufficient.
334 We use this counter to remember the position for the next back
336 n->out[0] = (ir_node *)0;
338 start = is_Block(n) ? 0 : -1;
339 irn_arity = get_irn_arity(n);
341 for (i = start; i < irn_arity; ++i) {
342 pred = get_irn_n(n, i);
344 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
345 free = _set_out_edges(pred, free);
346 /* Remember our back edge */
347 pred->out[get_irn_n_outs(pred)+1] = n;
348 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
354 * Enter memory for the outs to a node. Handles special nodes
356 * @param irg the graph
357 * @param free current free address in the chunk allocated for the outs
359 * @return The next free address
361 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
362 ir_node *n, *special[2];
365 inc_irg_visited(irg);
366 free = _set_out_edges(get_irg_end(irg), free);
368 /* handle special nodes */
369 special[0] = get_irg_frame(irg);
370 special[1] = get_irg_args(irg);
372 for (i = 1; i >= 0; --i) {
375 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
376 n_outs = PTR_TO_INT(n->out);
380 #endif /* defined DEBUG_libfirm */
390 * We want that the out of ProjX from Start contains the next block at
391 * position 1, the Start block at position 2. This is necessary for
392 * the out block walker.
394 static INLINE void fix_start_proj(ir_graph *irg) {
395 ir_node *proj = NULL;
396 ir_node *startbl = get_irg_start_block(irg);
399 if (get_Block_n_cfg_outs(startbl)) {
400 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
401 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
402 proj = get_irn_out(startbl, i);
406 if (get_irn_out(proj, 0) == startbl) {
407 assert(get_irn_n_outs(proj) == 2);
408 set_irn_out(proj, 0, get_irn_out(proj, 1));
409 set_irn_out(proj, 1, startbl);
414 /* compute the outs for a given graph */
415 void compute_irg_outs(ir_graph *irg) {
416 ir_graph *rem = current_ir_graph;
418 ir_node **end = NULL; /* Only for debugging */
420 current_ir_graph = irg;
422 /* Update graph state */
423 assert(get_irg_phase_state(current_ir_graph) != phase_building);
425 if (current_ir_graph->outs_state != outs_none)
426 free_irg_outs(current_ir_graph);
428 /* This first iteration counts the overall number of out edges and the
429 number of out edges for each node. */
430 n_out_edges = count_outs(irg);
432 /* allocate memory for all out edges. */
433 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
435 irg->n_outs = n_out_edges;
436 #endif /* defined DEBUG_libfirm */
438 /* The second iteration splits the irg->outs array into smaller arrays
439 for each node and writes the back edges into this array. */
440 end = set_out_edges(irg, irg->outs);
442 /* Check how much memory we have used */
443 assert (end == (irg->outs + n_out_edges));
445 /* We want that the out of ProjX from Start contains the next block at
446 position 1, the Start block at position 2. This is necessary for
447 the out block walker. */
450 current_ir_graph->outs_state = outs_consistent;
451 current_ir_graph = rem;
454 void assure_irg_outs(ir_graph *irg) {
455 if (get_irg_outs_state(irg) != outs_consistent)
456 compute_irg_outs(irg);
459 void compute_irp_outs(void) {
461 for (i = get_irp_n_irgs() -1; i >= 0; --i)
462 compute_irg_outs(get_irp_irg(i));
465 void free_irp_outs(void) {
467 for (i = get_irp_n_irgs() -1; i >= 0; --i)
468 free_irg_outs(get_irp_irg(i));
472 /*------------------------------------------------------------*
473 * This computes the outedges for in interprocedural graph. *
474 * There is one quirk: *
475 * The number of the outedges for each node is saved in *
476 * the first member of the ir_node** array. Maybe we should *
477 * change this to make it more portable... *
478 *------------------------------------------------------------*/
482 * Inits the number of outedges for each node
485 static void init_count(ir_node * node, void *env) {
487 node->out = (ir_node **) 1; /* 1 for the array size */
492 * Adjusts the out edge count for its predecessors
493 * and adds the current arity to the overall count,
494 * which is saved in "env"
496 static void node_arity_count(ir_node * node, void * env) {
497 int *anz = (int *) env, arity, n_outs, i, start;
500 arity = get_irn_arity(node);
501 start = (is_Block(node)) ? 0 : -1;
503 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
506 for(i = start; i < arity; i++) {
507 succ = get_irn_n(node, i);
508 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
514 * Inits all nodes for setting the outedges
515 * Returns the overall count of edges
517 int count_ip_outs(void) {
520 cg_walk(init_count, node_arity_count, &res);
525 static int dummy_count = 0, global_count; /* Only for debugging */
528 * For each node: Sets the pointer to array
529 * in which the outedges are written later.
530 * The current array start is transported in env
532 static void set_array_pointer(ir_node *node, void *env) {
534 ir_node ***free = (ir_node ***) env;
536 /* Allocate my array */
537 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
538 dummy_count += n_outs;
539 assert(dummy_count <= global_count && "More outedges than initially counted!");
541 *free = &((*free)[n_outs]);
542 /* We count the successors again, the space will be sufficient.
543 We use this counter to remember the position for the next back
545 node -> out[0] = (ir_node *) 0;
550 * Adds an outedge from the predecessor to the
553 static void set_out_pointer(ir_node * node, void *env) {
554 int i, arity = get_irn_arity(node);
556 int start = (!is_Block(node)) ? -1 : 0;
559 for (i = start; i < arity; ++i) {
560 succ = get_irn_n(node, i);
561 succ->out[get_irn_n_outs(succ)+1] = node;
562 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
568 * Sets the outedges for all nodes.
570 void set_ip_outs(void) {
571 ir_node **outedge_array = get_irp_ip_outedges();
572 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
578 * Counts the outedges, allocates memory to save the
579 * outedges and fills this outedge array in interprocedural
582 void compute_ip_outs(void) {
586 assert(get_irp_ip_view_state() == ip_view_valid &&
587 "Cannot construct outs for invalid ip view.");
589 if (irp->outs_state != outs_none) {
593 global_count = n_out_edges = count_ip_outs();
594 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
595 set_irp_ip_outedges(out_edges);
599 void free_ip_outs(void) {
600 ir_node **out_edges = get_irp_ip_outedges();
601 if (out_edges != NULL) {
603 set_irp_ip_outedges(NULL);
605 irp->outs_state = outs_none;
609 void free_irg_outs(ir_graph *irg) {
610 /* current_ir_graph->outs_state = outs_none; */
611 irg->outs_state = outs_none;
615 memset(irg->outs, 0, irg->n_outs);
616 #endif /* defined DEBUG_libfirm */
621 #endif /* defined DEBUG_libfirm */
625 /* when debugging, *always* reset all nodes' outs! irg->outs might
626 have been lying to us */
627 irg_walk_graph (irg, reset_outs, NULL, NULL);
628 #endif /* defined DEBUG_libfirm */