- fixed a stupid Bug: the marks are not cleared at the beginning,
[libfirm] / ir / ana / irouts.c
1 /*
2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
3  *
4  * This file is part of libFirm.
5  *
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.
10  *
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.
14  *
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
17  * PURPOSE.
18  */
19
20 /**
21  * @file
22  * @brief    Compute and access out edges (also called def-use edges).
23  * @author   Goetz Lindenmaier, Michael Beck
24  * @date     1.2002
25  * @version  $Id$
26  */
27 #ifdef HAVE_CONFIG_H
28 #include "config.h"
29 #endif
30
31 #ifdef HAVE_STRING_H
32 #include <string.h>
33 #endif
34
35 #include "xmalloc.h"
36 #include "irouts.h"
37 #include "irnode_t.h"
38 #include "irgraph_t.h"
39 #include "irprog_t.h"
40 #include "irgwalk.h"
41 #include "irtools.h"
42
43 #ifdef DEBUG_libfirm
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 */
48
49 /*--------------------------------------------------------------------*/
50 /** Accessing the out datastructures                                 **/
51 /*--------------------------------------------------------------------*/
52
53 #ifdef DEBUG_libfirm
54 /** Clear the outs of a node */
55 static void reset_outs(ir_node *node, void *unused) {
56         (void) unused;
57         node->out       = NULL;
58         node->out_valid = 0;
59 }
60 #endif
61
62 int get_irn_outs_computed(const ir_node *node)
63 {
64         return node->out != NULL;
65 }
66
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);
70 #ifdef DEBUG_libfirm
71         /* assert(node->out_valid); */
72 #endif /* defined DEBUG_libfirm */
73         return PTR_TO_INT(node->out[0]);
74 }
75
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));
79 #ifdef DEBUG_libfirm
80         /* assert(node->out_valid); */
81 #endif /* defined DEBUG_libfirm */
82 return node->out[pos+1];
83 }
84
85 void set_irn_out(ir_node *node, int pos, ir_node *out) {
86         assert(node && out);
87         assert(pos >= 0 && pos < get_irn_n_outs(node));
88 #ifdef DEBUG_libfirm
89         node->out_valid = 1;          /* assume that this function is used correctly */
90 #endif /* defined DEBUG_libfirm */
91         node->out[pos+1] = out;
92 }
93
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));
98 #ifdef DEBUG_libfirm
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]);
105         }
106         return n_cfg_outs;
107 }
108
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));
113 #ifdef DEBUG_libfirm
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) {
119
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)
123                                         continue;
124                                 else /* count Keep-alive as one */
125                                         n_cfg_outs += 1;
126                         } else
127                                 n_cfg_outs += PTR_TO_INT(succ->out[0]);
128                 }
129         }
130         return n_cfg_outs;
131 }
132
133 /* Access predecessor n, ignore keep-alives. */
134 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
135         int i;
136         assert(bl && is_Block(bl));
137 #ifdef DEBUG_libfirm
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]);
144                         if (pos < n_outs)
145                                 return succ->out[pos + 1];
146                         else
147                                 pos -= n_outs;
148                 }
149         }
150         return NULL;
151 }
152
153 /* Access predecessor n, honor keep-alives. */
154 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
155         int i, n_outs;
156         assert(bl && is_Block(bl));
157 #ifdef DEBUG_libfirm
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 */
166                                         continue;
167                                 }
168                                 if (pos == 0) {
169                                         /* handle keep-alive here: return the Endblock instead of the End node */
170                                         return get_irn_n(succ, -1);
171                                 } else
172                                         --pos;
173                         } else {
174                                 n_outs = PTR_TO_INT(succ->out[0]);
175                                 if (pos < n_outs)
176                                         return succ->out[pos + 1];
177                                 else
178                                         pos -= n_outs;
179                         }
180                 }
181         }
182         return NULL;
183 }
184
185 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
186             irg_walk_func *post, void *env) {
187         int     i, n;
188         ir_node *succ;
189
190         assert(node);
191         assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
192
193         set_irn_visited(node, get_irg_visited(current_ir_graph));
194
195         if (pre) pre(node, env);
196
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);
201         }
202
203         if (post) post(node, env);
204
205         return;
206 }
207
208 void irg_out_walk(ir_node *node,
209                   irg_walk_func *pre, irg_walk_func *post,
210                   void *env) {
211         assert(node);
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);
215         }
216         return;
217 }
218
219 static void irg_out_block_walk2(ir_node *bl,
220                                 irg_walk_func *pre, irg_walk_func *post,
221                                 void *env) {
222         int i, n;
223
224         if (Block_not_block_visited(bl)) {
225                 mark_Block_block_visited(bl);
226
227                 if (pre)
228                         pre(bl, env);
229
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);
233                         /* recursion */
234                         irg_out_block_walk2(pred, pre, post, env);
235                 }
236
237                 if (post)
238                         post(bl, env);
239         }
240 }
241
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,
246                         void *env) {
247
248         assert(is_Block(node) || (get_irn_mode(node) == mode_X));
249
250         inc_irg_block_visited(current_ir_graph);
251
252         if (get_irn_mode(node) == mode_X) {
253                 int i, n;
254
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);
259                 }
260         }
261         else {
262                 irg_out_block_walk2(node, pre, post, env);
263         }
264 }
265
266 /*--------------------------------------------------------------------*/
267 /** Building and Removing the out datastructure                      **/
268 /**                                                                  **/
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 /*--------------------------------------------------------------------*/
284
285
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;
289
290         mark_irn_visited(n);
291         n->out = (ir_node **) 1;     /* Space for array size. */
292
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. */
296
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);
301
302                 /* count outs for successors */
303                 if (irn_not_visited(pred))
304                         res += _count_outs(pred);
305
306                 /* Count my outs */
307                 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
308         }
309         return res;
310 }
311
312
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.
315  */
316 static int count_outs(ir_graph *irg) {
317         ir_node *n;
318         int res;
319
320         inc_irg_visited(irg);
321         res = _count_outs(get_irg_end(irg));
322
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;
328                 ++res;
329         }
330
331         n = get_irg_args(irg);
332         if (! is_Bad(n) && irn_not_visited(n)) {
333                 n->out = (ir_node **)1;
334                 ++res;
335         }
336
337         n = get_irg_value_param_base(irg);
338         if (! is_Bad(n) && irn_not_visited(n)) {
339                 n->out = (ir_node **)1;
340                 ++res;
341         }
342
343         return res;
344 }
345
346 /**
347  * Enter memory for the outs to a node.
348  *
349  * @param n      current node
350  * @param free   current free address in the chunk allocated for the outs
351  *
352  * @return The next free address
353  */
354 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
355         int n_outs, start, i, irn_arity;
356         ir_node *pred;
357
358         set_irn_visited(n, get_irg_visited(current_ir_graph));
359
360         /* Allocate my array */
361         n_outs = PTR_TO_INT(n->out);
362         n->out = free;
363 #ifdef DEBUG_libfirm
364         n->out_valid = 1;
365 #endif /* defined DEBUG_libfirm */
366         free += n_outs;
367         /* We count the successors again, the space will be sufficient.
368            We use this counter to remember the position for the next back
369            edge. */
370         n->out[0] = (ir_node *)0;
371
372         start = is_Block(n) ? 0 : -1;
373         irn_arity = get_irn_arity(n);
374
375         for (i = start; i < irn_arity; ++i) {
376                 pred = get_irn_n(n, i);
377                 /* Recursion */
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);
383         }
384         return free;
385 }
386
387 /**
388  * Enter memory for the outs to a node. Handles special nodes
389  *
390  * @param irg    the graph
391  * @param free   current free address in the chunk allocated for the outs
392  *
393  * @return The next free address
394  */
395 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
396         ir_node *n, *special[3];
397         int i, n_outs;
398
399         inc_irg_visited(irg);
400         free = _set_out_edges(get_irg_end(irg), free);
401
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);
406
407         for (i = 2; i >= 0; --i) {
408                 n = special[i];
409                 if (is_Bad(n))
410                         continue;
411
412                 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
413                         n_outs = PTR_TO_INT(n->out);
414                         n->out = free;
415 #ifdef DEBUG_libfirm
416                         n->out_valid = 1;
417 #endif /* defined DEBUG_libfirm */
418                         free += n_outs;
419                 }
420         }
421
422         return free;
423 }
424
425
426 /**
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.
430  */
431 static INLINE void fix_start_proj(ir_graph *irg) {
432         ir_node *proj    = NULL;
433         ir_node *startbl = get_irg_start_block(irg);
434         int i;
435
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);
440                                 break;
441                         }
442
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);
447                 }
448         }
449 }
450
451 /* compute the outs for a given graph */
452 void compute_irg_outs(ir_graph *irg) {
453         ir_graph *rem = current_ir_graph;
454         int n_out_edges = 0;
455         ir_node **end = NULL;         /* Only for debugging */
456
457         current_ir_graph = irg;
458
459         /* Update graph state */
460         assert(get_irg_phase_state(current_ir_graph) != phase_building);
461
462         if (current_ir_graph->outs_state != outs_none)
463                 free_irg_outs(current_ir_graph);
464
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);
468
469         /* allocate memory for all out edges. */
470         irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
471 #ifdef DEBUG_libfirm
472         irg->n_outs = n_out_edges;
473 #endif /* defined DEBUG_libfirm */
474
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);
478
479         /* Check how much memory we have used */
480         assert (end == (irg->outs + n_out_edges));
481
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. */
485         fix_start_proj(irg);
486
487         current_ir_graph->outs_state = outs_consistent;
488         current_ir_graph = rem;
489 }
490
491 void assure_irg_outs(ir_graph *irg) {
492         if (get_irg_outs_state(irg) != outs_consistent)
493                 compute_irg_outs(irg);
494 }
495
496 void compute_irp_outs(void) {
497         int i;
498         for (i = get_irp_n_irgs() -1; i >= 0; --i)
499                 compute_irg_outs(get_irp_irg(i));
500 }
501
502 void free_irp_outs(void) {
503         int i;
504         for (i = get_irp_n_irgs() -1; i >= 0; --i)
505                 free_irg_outs(get_irp_irg(i));
506 }
507
508
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  *------------------------------------------------------------*/
516
517
518 #ifdef INTERPROCEDURAL_VIEW
519 /**
520  * Inits the number of outedges for each node
521  * before counting.
522  */
523 static void init_count(ir_node * node, void *env) {
524         (void) env;
525         node->out = (ir_node **) 1; /* 1 for the array size */
526 }
527
528
529 /**
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"
533  */
534 static void node_arity_count(ir_node * node, void * env) {
535         int *anz = (int *) env, arity, n_outs, i, start;
536         ir_node *succ;
537
538         arity = get_irn_arity(node);
539         start = (is_Block(node)) ? 0 : -1;
540
541         n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
542         *anz += n_outs;
543
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);
547         }
548 }
549
550 /*
551  * Inits all nodes for setting the outedges
552  * Returns the overall count of edges
553  */
554 int count_ip_outs(void) {
555         int res = 0;
556
557         cg_walk(init_count, node_arity_count, &res);
558
559         return(res);
560 }
561
562 static int dummy_count = 0, global_count; /* Only for debugging */
563
564 /**
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
568  */
569 static void set_array_pointer(ir_node *node, void *env) {
570         int n_outs;
571         ir_node ***free = (ir_node ***) env;
572
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!");
577         node -> out = *free;
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
581            edge. */
582         node -> out[0] = (ir_node *) 0;
583 }
584
585
586 /**
587  * Adds an outedge from the predecessor to the
588  * current node.
589  */
590 static void set_out_pointer(ir_node * node, void *env) {
591         int i, arity = get_irn_arity(node);
592         ir_node *succ;
593         int start = (!is_Block(node)) ? -1 : 0;
594         (void) env;
595
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);
600         }
601 }
602
603
604 /*
605  * Sets the outedges for all nodes.
606  */
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);
610 }
611
612
613
614 /*
615  * Counts the outedges, allocates memory to save the
616  * outedges and fills this outedge array in interprocedural
617  * view!
618  */
619 void compute_ip_outs(void) {
620         int n_out_edges;
621         ir_node **out_edges;
622
623         assert(get_irp_ip_view_state() == ip_view_valid &&
624          "Cannot construct outs for invalid ip view.");
625
626         if (irp->outs_state != outs_none) {
627                 free_ip_outs();
628         }
629
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);
633         set_ip_outs();
634 }
635
636 void free_ip_outs(void) {
637         ir_node **out_edges = get_irp_ip_outedges();
638         if (out_edges != NULL) {
639                 free(out_edges);
640                 set_irp_ip_outedges(NULL);
641         }
642         irp->outs_state = outs_none;
643 }
644 #endif
645
646
647 void free_irg_outs(ir_graph *irg) {
648         /*   current_ir_graph->outs_state = outs_none; */
649         irg->outs_state = outs_none;
650
651         if (irg->outs) {
652 #ifdef DEBUG_libfirm
653                 memset(irg->outs, 0, irg->n_outs);
654 #endif /* defined DEBUG_libfirm */
655                 free(irg->outs);
656                 irg->outs = NULL;
657 #ifdef DEBUG_libfirm
658                 irg->n_outs = 0;
659 #endif /* defined DEBUG_libfirm */
660         }
661
662 #ifdef 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 */
667 }