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) {
61 /* returns the number of successors of the node: */
62 int get_irn_n_outs(ir_node *node) {
63 assert(node && node->kind == k_ir_node);
65 /* assert(node->out_valid); */
66 #endif /* defined DEBUG_libfirm */
67 return PTR_TO_INT(node->out[0]);
70 /* Access successor n */
71 ir_node *get_irn_out(ir_node *node, int pos) {
72 assert(pos >= 0 && pos < get_irn_n_outs(node));
74 /* assert(node->out_valid); */
75 #endif /* defined DEBUG_libfirm */
76 return node->out[pos+1];
79 void set_irn_out(ir_node *node, int pos, ir_node *out) {
81 assert(pos >= 0 && pos < get_irn_n_outs(node));
83 node->out_valid = 1; /* assume that this function is used correctly */
84 #endif /* defined DEBUG_libfirm */
85 node->out[pos+1] = out;
88 /* Return the number of control flow successors, ignore keep-alives. */
89 int get_Block_n_cfg_outs(ir_node *bl) {
90 int i, n_cfg_outs = 0;
91 assert(bl && is_Block(bl));
93 assert(bl->out_valid);
94 #endif /* defined DEBUG_libfirm */
95 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
96 if ((get_irn_mode(bl->out[i]) == mode_X) &&
97 (get_irn_op(bl->out[i]) != op_End))
102 /* Return the number of control flow successors, honor keep-alives. */
103 int get_Block_n_cfg_outs_ka(ir_node *bl) {
104 int i, n_cfg_outs = 0;
105 assert(bl && is_Block(bl));
107 assert(bl->out_valid);
108 #endif /* defined DEBUG_libfirm */
109 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
110 if (get_irn_mode(bl->out[i]) == mode_X) {
111 /* ignore End if we are in the Endblock */
112 if (get_irn_op(bl->out[i]) == op_End &&
113 get_irn_n(bl->out[i], -1) == bl)
121 /* Access predecessor n, ignore keep-alives. */
122 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
124 assert(bl && is_Block(bl));
126 assert (bl->out_valid);
127 #endif /* defined DEBUG_libfirm */
128 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
129 if ((get_irn_mode(bl->out[i]) == mode_X) &&
130 (get_irn_op(bl->out[i]) != op_End)) {
131 if (out_pos == pos) {
132 ir_node *cfop = bl->out[i];
140 /* Access predecessor n, honor keep-alives. */
141 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
143 assert(bl && is_Block(bl));
145 assert (bl->out_valid);
146 #endif /* defined DEBUG_libfirm */
147 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
148 if (get_irn_mode(bl->out[i]) == mode_X) {
149 /* ignore End if we are in the Endblock */
150 if (get_irn_op(bl->out[i]) == op_End &&
151 get_irn_n(bl->out[i], -1) == bl)
153 if (out_pos == pos) {
154 ir_node *cfop = bl->out[i];
155 /* handle keep-alive here */
156 if (get_irn_op(cfop) == op_End)
157 return get_irn_n(cfop, -1);
165 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
166 irg_walk_func *post, void *env) {
171 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
173 set_irn_visited(node, get_irg_visited(current_ir_graph));
175 if (pre) pre(node, env);
177 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
178 succ = get_irn_out(node, i);
179 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
180 irg_out_walk_2(succ, pre, post, env);
183 if (post) post(node, env);
188 void irg_out_walk(ir_node *node,
189 irg_walk_func *pre, irg_walk_func *post,
192 if (get_irg_outs_state(current_ir_graph) != outs_none) {
193 inc_irg_visited (current_ir_graph);
194 irg_out_walk_2(node, pre, post, env);
199 static void irg_out_block_walk2(ir_node *bl,
200 irg_walk_func *pre, irg_walk_func *post,
204 if (Block_not_block_visited(bl)) {
205 mark_Block_block_visited(bl);
210 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
211 /* find the corresponding predecessor block. */
212 ir_node *pred = get_Block_cfg_out(bl, i);
214 irg_out_block_walk2(pred, pre, post, env);
222 /* Walks only over Block nodes in the graph. Has it's own visited
223 flag, so that it can be interleaved with the other walker. */
224 void irg_out_block_walk(ir_node *node,
225 irg_walk_func *pre, irg_walk_func *post,
228 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
230 inc_irg_block_visited(current_ir_graph);
232 if (get_irn_mode(node) == mode_X)
235 irg_out_block_walk2(node, pre, post, env);
238 /*--------------------------------------------------------------------*/
239 /** Building and Removing the out datasturcture **/
241 /** The outs of a graph are allocated in a single, large array. **/
242 /** This allows to allocate and deallocate the memory for the outs **/
243 /** on demand. The large array is separated into many small ones **/
244 /** for each node. Only a single field to reference the out array **/
245 /** is stored in each node and a field referencing the large out **/
246 /** array in irgraph. The 0 field of each out array contains the **/
247 /** size of this array. This saves memory in the irnodes themselves.**/
248 /** The construction does two passes over the graph. The first pass **/
249 /** counts the overall number of outs and the outs of each node. It **/
250 /** stores the outs of each node in the out reference of the node. **/
251 /** Then the large array is allocated. The second iteration chops **/
252 /** the large array into smaller parts, sets the out edges and **/
253 /** recounts the out edges. **/
254 /** Removes Tuple nodes! **/
255 /*--------------------------------------------------------------------*/
258 /** Returns the amount of out edges for not yet visited successors. */
259 static int _count_outs(ir_node *n) {
260 int start, i, res, irn_arity;
263 n->out = (ir_node **) 1; /* Space for array size. */
265 start = is_Block(n) ? 0 : -1;
266 irn_arity = get_irn_arity(n);
267 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
269 for (i = start; i < irn_arity; ++i) {
270 /* Optimize Tuples. They annoy if walking the cfg. */
271 ir_node *pred = skip_Tuple(get_irn_n(n, i));
272 set_irn_n(n, i, pred);
274 /* count outs for successors */
275 if (irn_not_visited(pred))
276 res += _count_outs(pred);
279 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
285 /** Returns the amount of out edges for not yet visited successors.
286 * This version handles some special nodes like irg_frame, irg_args etc.
288 static int count_outs(ir_graph *irg) {
292 inc_irg_visited(irg);
293 res = _count_outs(get_irg_end(irg));
295 /* now handle special nodes */
296 n = get_irg_frame(irg);
297 if (irn_not_visited(n)) {
298 n->out = (ir_node **)1;
302 n = get_irg_args(irg);
303 if (irn_not_visited(n)) {
304 n->out = (ir_node **)1;
312 * Enter memory for the outs to a node.
314 * @param n current node
315 * @param free current free address in the chunk allocated for the outs
317 * @return The next free address
319 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
320 int n_outs, start, i, irn_arity;
323 set_irn_visited(n, get_irg_visited(current_ir_graph));
325 /* Allocate my array */
326 n_outs = PTR_TO_INT(n->out);
330 #endif /* defined DEBUG_libfirm */
332 /* We count the successors again, the space will be sufficient.
333 We use this counter to remember the position for the next back
335 n->out[0] = (ir_node *)0;
337 start = is_Block(n) ? 0 : -1;
338 irn_arity = get_irn_arity(n);
340 for (i = start; i < irn_arity; ++i) {
341 pred = get_irn_n(n, i);
343 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
344 free = _set_out_edges(pred, free);
345 /* Remember our back edge */
346 pred->out[get_irn_n_outs(pred)+1] = n;
347 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
353 * Enter memory for the outs to a node. Handles special nodes
355 * @param irg the graph
356 * @param free current free address in the chunk allocated for the outs
358 * @return The next free address
360 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
361 ir_node *n, *special[2];
364 inc_irg_visited(irg);
365 free = _set_out_edges(get_irg_end(irg), free);
367 /* handle special nodes */
368 special[0] = get_irg_frame(irg);
369 special[1] = get_irg_args(irg);
371 for (i = 1; i >= 0; --i) {
374 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
375 n_outs = PTR_TO_INT(n->out);
379 #endif /* defined DEBUG_libfirm */
389 * We want that the out of ProjX from Start contains the next block at
390 * position 1, the Start block at position 2. This is necessary for
391 * the out block walker.
393 static INLINE void fix_start_proj(ir_graph *irg) {
394 ir_node *proj = NULL;
395 ir_node *startbl = get_irg_start_block(irg);
398 if (get_Block_n_cfg_outs(startbl)) {
399 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
400 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
401 proj = get_irn_out(startbl, i);
405 if (get_irn_out(proj, 0) == startbl) {
406 assert(get_irn_n_outs(proj) == 2);
407 set_irn_out(proj, 0, get_irn_out(proj, 1));
408 set_irn_out(proj, 1, startbl);
413 /* compute the outs for a given graph */
414 void compute_irg_outs(ir_graph *irg) {
415 ir_graph *rem = current_ir_graph;
417 ir_node **end = NULL; /* Only for debugging */
419 current_ir_graph = irg;
421 /* Update graph state */
422 assert(get_irg_phase_state(current_ir_graph) != phase_building);
424 if (current_ir_graph->outs_state != outs_none)
425 free_irg_outs(current_ir_graph);
427 /* This first iteration counts the overall number of out edges and the
428 number of out edges for each node. */
429 n_out_edges = count_outs(irg);
431 /* allocate memory for all out edges. */
432 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
434 irg->n_outs = n_out_edges;
435 #endif /* defined DEBUG_libfirm */
437 /* The second iteration splits the irg->outs array into smaller arrays
438 for each node and writes the back edges into this array. */
439 end = set_out_edges(irg, irg->outs);
441 /* Check how much memory we have used */
442 assert (end == (irg->outs + n_out_edges));
444 /* We want that the out of ProjX from Start contains the next block at
445 position 1, the Start block at position 2. This is necessary for
446 the out block walker. */
449 current_ir_graph->outs_state = outs_consistent;
450 current_ir_graph = rem;
453 void assure_irg_outs(ir_graph *irg) {
454 if (get_irg_outs_state(irg) != outs_consistent)
455 compute_irg_outs(irg);
458 void compute_irp_outs(void) {
460 for (i = get_irp_n_irgs() -1; i >= 0; --i)
461 compute_irg_outs(get_irp_irg(i));
464 void free_irp_outs(void) {
466 for (i = get_irp_n_irgs() -1; i >= 0; --i)
467 free_irg_outs(get_irp_irg(i));
471 /*------------------------------------------------------------*
472 * This computes the outedges for in interprocedural graph. *
473 * There is one quirk: *
474 * The number of the outedges for each node is saved in *
475 * the first member of the ir_node** array. Maybe we should *
476 * change this to make it more portable... *
477 *------------------------------------------------------------*/
481 * Inits the number of outedges for each node
484 static void init_count(ir_node * node, void *env) {
485 node->out = (ir_node **) 1; /* 1 for the array size */
490 * Adjusts the out edge count for its predecessors
491 * and adds the current arity to the overall count,
492 * which is saved in "env"
494 static void node_arity_count(ir_node * node, void * env) {
495 int *anz = (int *) env, arity, n_outs, i, start;
498 arity = get_irn_arity(node);
499 start = (is_Block(node)) ? 0 : -1;
501 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
504 for(i = start; i < arity; i++) {
505 succ = get_irn_n(node, i);
506 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
512 * Inits all nodes for setting the outedges
513 * Returns the overall count of edges
515 int count_ip_outs(void) {
518 cg_walk(init_count, node_arity_count, &res);
523 static int dummy_count = 0, global_count; /* Only for debugging */
526 * For each node: Sets the pointer to array
527 * in which the outedges are written later.
528 * The current array start is transported in env
530 static void set_array_pointer(ir_node *node, void *env) {
532 ir_node ***free = (ir_node ***) env;
534 /* Allocate my array */
535 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
536 dummy_count += n_outs;
537 assert(dummy_count <= global_count && "More outedges than initially counted!");
539 *free = &((*free)[n_outs]);
540 /* We count the successors again, the space will be sufficient.
541 We use this counter to remember the position for the next back
543 node -> out[0] = (ir_node *) 0;
548 * Adds an outedge from the predecessor to the
551 static void set_out_pointer(ir_node * node, void * env) {
552 int i, arity = get_irn_arity(node);
554 int start = (!is_Block(node)) ? -1 : 0;
556 for (i = start; i < arity; ++i) {
557 succ = get_irn_n(node, i);
558 succ->out[get_irn_n_outs(succ)+1] = node;
559 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
565 * Sets the outedges for all nodes.
567 void set_ip_outs(void) {
568 ir_node **outedge_array = get_irp_ip_outedges();
569 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
575 * Counts the outedges, allocates memory to save the
576 * outedges and fills this outedge array in interprocedural
579 void compute_ip_outs(void) {
583 assert(get_irp_ip_view_state() == ip_view_valid &&
584 "Cannot construct outs for invalid ip view.");
586 if (irp->outs_state != outs_none) {
590 global_count = n_out_edges = count_ip_outs();
591 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
592 set_irp_ip_outedges(out_edges);
596 void free_ip_outs(void) {
597 ir_node **out_edges = get_irp_ip_outedges();
598 if (out_edges != NULL) {
600 set_irp_ip_outedges(NULL);
602 irp->outs_state = outs_none;
606 void free_irg_outs(ir_graph *irg) {
607 /* current_ir_graph->outs_state = outs_none; */
608 irg->outs_state = outs_none;
612 memset(irg->outs, 0, irg->n_outs);
613 #endif /* defined DEBUG_libfirm */
618 #endif /* defined DEBUG_libfirm */
622 /* when debugging, *always* reset all nodes' outs! irg->outs might
623 have been lying to us */
624 irg_walk_graph (irg, reset_outs, NULL, NULL);
625 #endif /* defined DEBUG_libfirm */