irouts.c 19.1 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
 *
 * This file is part of libFirm.
Michael Beck's avatar
Michael Beck committed
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
Michael Beck's avatar
Michael Beck committed
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
14
15
16
17
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Michael Beck's avatar
Michael Beck committed
18
 */
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
26
/**
 * @file
 * @brief    Compute and access out edges (also called def-use edges).
 * @author   Goetz Lindenmaier, Michael Beck
 * @date     1.2002
 * @version  $Id$
 */
Michael Beck's avatar
Michael Beck committed
27
28
#ifdef HAVE_CONFIG_H
#include "config.h"
Michael Beck's avatar
Michael Beck committed
29
#endif
30

Michael Beck's avatar
Michael Beck committed
31
32
33
34
35
#ifdef HAVE_STRING_H
#include <string.h>
#endif

#include "xmalloc.h"
36
37
#include "irouts.h"
#include "irnode_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
38
#include "irgraph_t.h"
39
#include "irprog_t.h"
40
#include "irgwalk.h"
41
#include "irtools.h"
42
43
#include "irprintf.h"
#include "error.h"
44

45
46
47
48
49
50
#ifdef DEBUG_libfirm
/* Note:  ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
/* Accesses to out_valid and n_outs are fenced out to avoid breakage
   when compiling with neither DEBUG_libfirm or NDEBUG defined */
#endif /* defined DEBUG_libfirm */

Michael Beck's avatar
Michael Beck committed
51
/*--------------------------------------------------------------------*/
52
/** Accessing the out datastructures                                 **/
Michael Beck's avatar
Michael Beck committed
53
/*--------------------------------------------------------------------*/
54

Matthias Braun's avatar
Matthias Braun committed
55
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
56
/** Clear the outs of a node */
Michael Beck's avatar
Michael Beck committed
57
static void reset_outs(ir_node *node, void *unused) {
Matthias Braun's avatar
Matthias Braun committed
58
	(void) unused;
Michael Beck's avatar
Michael Beck committed
59
60
	node->out       = NULL;
	node->out_valid = 0;
61
}
Matthias Braun's avatar
Matthias Braun committed
62
#endif
63

64
65
66
67
68
int get_irn_outs_computed(const ir_node *node)
{
	return node->out != NULL;
}

69
/* returns the number of successors of the node: */
Matthias Braun's avatar
Matthias Braun committed
70
int get_irn_n_outs(const ir_node *node) {
Michael Beck's avatar
Michael Beck committed
71
	assert(node && node->kind == k_ir_node);
72
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
73
	/* assert(node->out_valid); */
74
#endif /* defined DEBUG_libfirm */
75
76
	/* we misuse the first for the size info of the out array */
	return node->out[0].pos;
77
78
79
}

/* Access successor n */
Matthias Braun's avatar
Matthias Braun committed
80
ir_node *get_irn_out(const ir_node *def, int pos) {
81
	assert(pos >= 0 && pos < get_irn_n_outs(def));
82
#ifdef DEBUG_libfirm
83
84
85
86
87
88
	/* assert(def->out_valid); */
#endif /* defined DEBUG_libfirm */
	return def->out[pos+1].use;
}

/* Access successor n */
Matthias Braun's avatar
Matthias Braun committed
89
ir_node *get_irn_out_ex(const ir_node *def, int pos, int *in_pos) {
90
91
92
	assert(pos >= 0 && pos < get_irn_n_outs(def));
#ifdef DEBUG_libfirm
	/* assert(def->out_valid); */
93
#endif /* defined DEBUG_libfirm */
94
95
	*in_pos = def->out[pos+1].pos;
	return def->out[pos+1].use;
96
97
}

98
99
100
void set_irn_out(ir_node *def, int pos, ir_node *use, int in_pos) {
	assert(def && use);
	assert(pos >= 0 && pos < get_irn_n_outs(def));
101
#ifdef DEBUG_libfirm
102
	def->out_valid = 1;          /* assume that this function is used correctly */
103
#endif /* defined DEBUG_libfirm */
104
105
	def->out[pos+1].use = use;
	def->out[pos+1].pos = in_pos;
106
107
}

108
/* Return the number of control flow successors, ignore keep-alives. */
Matthias Braun's avatar
Matthias Braun committed
109
int get_Block_n_cfg_outs(const ir_node *bl) {
Michael Beck's avatar
Michael Beck committed
110
111
	int i, n_cfg_outs = 0;
	assert(bl && is_Block(bl));
112
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
113
	assert(bl->out_valid);
114
#endif /* defined DEBUG_libfirm */
115
116
117
118
	for (i = 1; i <= bl->out[0].pos; ++i) {
		ir_node *succ = bl->out[i].use;
		if (get_irn_mode(succ) == mode_X && !is_End(succ))
			n_cfg_outs += succ->out[0].pos;
119
	}
Michael Beck's avatar
Michael Beck committed
120
	return n_cfg_outs;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
121
122
}

123
/* Return the number of control flow successors, honor keep-alives. */
Matthias Braun's avatar
Matthias Braun committed
124
int get_Block_n_cfg_outs_ka(const ir_node *bl) {
Michael Beck's avatar
Michael Beck committed
125
126
	int i, n_cfg_outs = 0;
	assert(bl && is_Block(bl));
127
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
128
	assert(bl->out_valid);
129
#endif /* defined DEBUG_libfirm */
130
131
	for (i = 1; i <= bl->out[0].pos; ++i) {
		ir_node *succ = bl->out[i].use;
132
		if (get_irn_mode(succ) == mode_X) {
133

134
			if (is_End(succ)) {
135
				/* ignore End if we are in the Endblock */
136
				if (get_nodes_block(succ) == bl)
137
138
139
140
					continue;
				else /* count Keep-alive as one */
					n_cfg_outs += 1;
			} else
141
				n_cfg_outs += succ->out[0].pos;
Michael Beck's avatar
Michael Beck committed
142
		}
143
	}
Michael Beck's avatar
Michael Beck committed
144
	return n_cfg_outs;
145
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
146

147
/* Access predecessor n, ignore keep-alives. */
Matthias Braun's avatar
Matthias Braun committed
148
ir_node *get_Block_cfg_out(const ir_node *bl, int pos) {
149
	int i;
Michael Beck's avatar
Michael Beck committed
150
	assert(bl && is_Block(bl));
151
#ifdef DEBUG_libfirm
152
	assert(bl->out_valid);
153
#endif /* defined DEBUG_libfirm */
154
155
156
157
	for (i = 1; i <= bl->out[0].pos; ++i) {
		ir_node *succ = bl->out[i].use;
		if (get_irn_mode(succ) == mode_X && !is_End(succ)) {
			int n_outs = succ->out[0].pos;
158
			if (pos < n_outs)
159
				return succ->out[pos + 1].use;
160
161
			else
				pos -= n_outs;
Michael Beck's avatar
Michael Beck committed
162
		}
163
	}
Michael Beck's avatar
Michael Beck committed
164
	return NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
165
166
}

167
/* Access predecessor n, honor keep-alives. */
Matthias Braun's avatar
Matthias Braun committed
168
ir_node *get_Block_cfg_out_ka(const ir_node *bl, int pos) {
169
	int i, n_outs;
Michael Beck's avatar
Michael Beck committed
170
	assert(bl && is_Block(bl));
171
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
172
	assert (bl->out_valid);
173
#endif /* defined DEBUG_libfirm */
174
175
	for (i = 1; i <= bl->out[0].pos; ++i) {
		ir_node *succ = bl->out[i].use;
176
		if (get_irn_mode(succ) == mode_X) {
177
178
179
			if (is_End(succ)) {
				ir_node *end_bl = get_nodes_block(succ);
				if (end_bl == bl) {
180
181
182
183
184
					/* ignore End if we are in the Endblock */
					continue;
				}
				if (pos == 0) {
					/* handle keep-alive here: return the Endblock instead of the End node */
185
					return end_bl;
186
187
188
				} else
					--pos;
			} else {
189
				n_outs = succ->out[0].pos;
190
				if (pos < n_outs)
191
					return succ->out[pos + 1].use;
192
193
194
				else
					pos -= n_outs;
			}
Michael Beck's avatar
Michael Beck committed
195
		}
196
	}
Michael Beck's avatar
Michael Beck committed
197
	return NULL;
198
199
}

Michael Beck's avatar
Michael Beck committed
200
static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
201
            irg_walk_func *post, void *env) {
Michael Beck's avatar
Michael Beck committed
202
203
	int     i, n;
	ir_node *succ;
204

Michael Beck's avatar
Michael Beck committed
205
206
	assert(node);
	assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
207

Michael Beck's avatar
Michael Beck committed
208
	set_irn_visited(node, get_irg_visited(current_ir_graph));
209

Michael Beck's avatar
Michael Beck committed
210
	if (pre) pre(node, env);
211

Michael Beck's avatar
Michael Beck committed
212
213
214
215
216
	for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
		succ = get_irn_out(node, i);
		if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
			irg_out_walk_2(succ, pre, post, env);
	}
217

Michael Beck's avatar
Michael Beck committed
218
	if (post) post(node, env);
219
220
221
}

void irg_out_walk(ir_node *node,
Michael Beck's avatar
Michael Beck committed
222
223
224
225
226
227
228
                  irg_walk_func *pre, irg_walk_func *post,
                  void *env) {
	assert(node);
	if (get_irg_outs_state(current_ir_graph) != outs_none) {
		inc_irg_visited (current_ir_graph);
		irg_out_walk_2(node, pre, post, env);
	}
229
230
}

Michael Beck's avatar
Michael Beck committed
231
static void irg_out_block_walk2(ir_node *bl,
Michael Beck's avatar
Michael Beck committed
232
233
234
235
                                irg_walk_func *pre, irg_walk_func *post,
                                void *env) {
	int i, n;

236
	if (!Block_block_visited(bl)) {
Michael Beck's avatar
Michael Beck committed
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
		mark_Block_block_visited(bl);

		if (pre)
			pre(bl, env);

		for (i = 0, n =  get_Block_n_cfg_outs(bl); i < n; ++i) {
			/* find the corresponding predecessor block. */
			ir_node *pred = get_Block_cfg_out(bl, i);
			/* recursion */
			irg_out_block_walk2(pred, pre, post, env);
		}

		if (post)
			post(bl, env);
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
252
253
}

254
255
256
/* Walks only over Block nodes in the graph.  Has it's own visited
   flag, so that it can be interleaved with the other walker.         */
void irg_out_block_walk(ir_node *node,
Michael Beck's avatar
Michael Beck committed
257
258
                        irg_walk_func *pre, irg_walk_func *post,
                        void *env) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
259

Michael Beck's avatar
Michael Beck committed
260
	assert(is_Block(node) || (get_irn_mode(node) == mode_X));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
261

Michael Beck's avatar
Michael Beck committed
262
	inc_irg_block_visited(current_ir_graph);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
263

Michael Beck's avatar
Michael Beck committed
264
265
266
267
268
269
270
271
272
273
274
275
	if (get_irn_mode(node) == mode_X) {
		int i, n;

		for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
			ir_node *succ = get_irn_out(node, i);
			if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
				irg_out_walk_2(succ, pre, post, env);
		}
	}
	else {
		irg_out_block_walk2(node, pre, post, env);
	}
276
277
}

Michael Beck's avatar
Michael Beck committed
278
/*--------------------------------------------------------------------*/
279
/** Building and Removing the out datastructure                      **/
280
281
282
283
284
285
286
287
288
289
290
291
292
293
/**                                                                  **/
/** The outs of a graph are allocated in a single, large array.      **/
/** This allows to allocate and deallocate the memory for the outs   **/
/** on demand.  The large array is separated into many small ones    **/
/** for each node.  Only a single field to reference the out array   **/
/** is stored in each node and a field referencing the large out     **/
/** array in irgraph.  The 0 field of each out array contains the    **/
/** size of this array.  This saves memory in the irnodes themselves.**/
/** The construction does two passes over the graph.  The first pass **/
/** counts the overall number of outs and the outs of each node.  It **/
/** stores the outs of each node in the out reference of the node.   **/
/** Then the large array is allocated.  The second iteration chops   **/
/** the large array into smaller parts, sets the out edges and       **/
/** recounts the out edges.                                          **/
294
/** Removes Tuple nodes!                                             **/
Michael Beck's avatar
Michael Beck committed
295
/*--------------------------------------------------------------------*/
296
297


Michael Beck's avatar
Michael Beck committed
298
/** Returns the amount of out edges for not yet visited successors. */
299
static int _count_outs(ir_node *n) {
300
	int start, i, res, irn_arity;
301

Michael Beck's avatar
Michael Beck committed
302
	mark_irn_visited(n);
303
	n->out = INT_TO_PTR(1);     /* Space for array size. */
304

305
	start = is_Block(n) ? 0 : -1;
Michael Beck's avatar
Michael Beck committed
306
	irn_arity = get_irn_arity(n);
307
	res = irn_arity - start + 1;  /* --1 or --0; 1 for array size. */
Michael Beck's avatar
Michael Beck committed
308

309
	for (i = start; i < irn_arity; ++i) {
Michael Beck's avatar
Michael Beck committed
310
		/* Optimize Tuples.  They annoy if walking the cfg. */
311
312
313
314
315
316
		ir_node *pred         = get_irn_n(n, i);
		ir_node *skipped_pred = skip_Tuple(pred);

		if (skipped_pred != pred) {
			set_irn_n(n, i, skipped_pred);
		}
Michael Beck's avatar
Michael Beck committed
317

318
		/* count Def-Use edges for predecessors */
319
320
		if (irn_not_visited(skipped_pred))
			res += _count_outs(skipped_pred);
321

322
		/*count my Def-Use edges */
323
		skipped_pred->out = INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1);
Michael Beck's avatar
Michael Beck committed
324
325
	}
	return res;
326
327
}

328
329

/** Returns the amount of out edges for not yet visited successors.
330
 *  This version handles some special nodes like irg_frame, irg_args etc.
331
332
 */
static int count_outs(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
333
	ir_node *n;
334
	int     i, res;
Michael Beck's avatar
Michael Beck committed
335
336
337
338

	inc_irg_visited(irg);
	res = _count_outs(get_irg_end(irg));

339
	/* Now handle anchored nodes. We need the out count of those
340
	   even if they are not visible. */
341
342
343
344
	for (i = anchor_last - 1; i >= 0; --i) {
		n = get_irg_anchor(irg, i);
		if (irn_not_visited(n)) {
			mark_irn_visited(n);
345

346
347
348
			n->out = INT_TO_PTR(1);
			++res;
		}
Michael Beck's avatar
Michael Beck committed
349
350
	}
	return res;
351
352
}

Michael Beck's avatar
Michael Beck committed
353
354
355
/**
 * Enter memory for the outs to a node.
 *
356
 * @param use    current node
Michael Beck's avatar
Michael Beck committed
357
358
359
360
 * @param free   current free address in the chunk allocated for the outs
 *
 * @return The next free address
 */
361
362
static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) {
	int     n_outs, start, i, irn_arity, pos;
363

364
	mark_irn_visited(use);
365

Michael Beck's avatar
Michael Beck committed
366
	/* Allocate my array */
367
368
	n_outs = PTR_TO_INT(use->out);
	use->out = free;
369
#ifdef DEBUG_libfirm
370
	use->out_valid = 1;
371
#endif /* defined DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
372
373
374
375
	free += n_outs;
	/* We count the successors again, the space will be sufficient.
	   We use this counter to remember the position for the next back
	   edge. */
376
	use->out[0].pos = 0;
Michael Beck's avatar
Michael Beck committed
377

378
379
	start = is_Block(use) ? 0 : -1;
	irn_arity = get_irn_arity(use);
380
381

	for (i = start; i < irn_arity; ++i) {
382
383
		ir_node *def = get_irn_n(use, i);

Michael Beck's avatar
Michael Beck committed
384
		/* Recursion */
385
386
387
388
389
390
391
392
393
394
		if (irn_not_visited(def))
			free = _set_out_edges(def, free);

		/* Remember this Def-Use edge */
		pos = def->out[0].pos + 1;
		def->out[pos].use = use;
		def->out[pos].pos = i;

		/* increase the number of Def-Use edges so far */
		def->out[0].pos = pos;
Michael Beck's avatar
Michael Beck committed
395
396
	}
	return free;
397
398
}

399
400
401
402
403
404
405
406
/**
 * Enter memory for the outs to a node. Handles special nodes
 *
 * @param irg    the graph
 * @param free   current free address in the chunk allocated for the outs
 *
 * @return The next free address
 */
407
408
409
static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) {
	ir_node *n;
	int     i, n_outs;
410

Michael Beck's avatar
Michael Beck committed
411
412
	inc_irg_visited(irg);
	free = _set_out_edges(get_irg_end(irg), free);
413

414
415
416
417
418
	/* handle anchored nodes */
	for (i = anchor_last - 1; i >= 0; --i) {
		n = get_irg_anchor(irg, i);
		if (irn_not_visited(n)) {
			mark_irn_visited(n);
419

Michael Beck's avatar
Michael Beck committed
420
421
			n_outs = PTR_TO_INT(n->out);
			n->out = free;
422
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
423
			n->out_valid = 1;
424
#endif /* defined DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
425
426
427
			free += n_outs;
		}
	}
428

Michael Beck's avatar
Michael Beck committed
429
	return free;
430
431
432
}


Michael Beck's avatar
Michael Beck committed
433
434
/**
 * We want that the out of ProjX from Start contains the next block at
435
 * position 0, the Start block at position 1.  This is necessary for
Michael Beck's avatar
Michael Beck committed
436
437
 * the out block walker.
 */
438
static INLINE void fix_start_proj(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
439
440
441
	ir_node *startbl = get_irg_start_block(irg);

	if (get_Block_n_cfg_outs(startbl)) {
442
443
444
445
446
447
448
449
450
		ir_node *proj = get_irg_initial_exec(irg);
		ir_node *irn;
		int     block_pos, other_pos;

		if (get_irn_n_outs(proj) == 2) {
			if (get_irn_out_ex(proj, 0, &block_pos) == startbl) {
				irn = get_irn_out_ex(proj, 1, &other_pos);
				set_irn_out(proj, 0, irn, other_pos);
				set_irn_out(proj, 1, startbl, block_pos);
Michael Beck's avatar
Michael Beck committed
451
			}
452
453
		} else {
			assert(get_irg_phase_state(irg) == phase_backend);
Michael Beck's avatar
Michael Beck committed
454
455
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
456
457
}

Michael Beck's avatar
Michael Beck committed
458
/* compute the outs for a given graph */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
459
void compute_irg_outs(ir_graph *irg) {
460
461
462
	ir_graph        *rem = current_ir_graph;
	int             n_out_edges = 0;
	ir_def_use_edge *end = NULL;         /* Only for debugging */
463

Michael Beck's avatar
Michael Beck committed
464
	current_ir_graph = irg;
465

Michael Beck's avatar
Michael Beck committed
466
467
	/* Update graph state */
	assert(get_irg_phase_state(current_ir_graph) != phase_building);
Michael Beck's avatar
Michael Beck committed
468

Michael Beck's avatar
Michael Beck committed
469
470
	if (current_ir_graph->outs_state != outs_none)
		free_irg_outs(current_ir_graph);
471

Michael Beck's avatar
Michael Beck committed
472
473
474
	/* This first iteration counts the overall number of out edges and the
	   number of out edges for each node. */
	n_out_edges = count_outs(irg);
475

Michael Beck's avatar
Michael Beck committed
476
477
	/* allocate memory for all out edges. */
	irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
478
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
479
	irg->n_outs = n_out_edges;
480
#endif /* defined DEBUG_libfirm */
481

Michael Beck's avatar
Michael Beck committed
482
483
484
	/* The second iteration splits the irg->outs array into smaller arrays
	   for each node and writes the back edges into this array. */
	end = set_out_edges(irg, irg->outs);
485

Michael Beck's avatar
Michael Beck committed
486
487
	/* Check how much memory we have used */
	assert (end == (irg->outs + n_out_edges));
488

Michael Beck's avatar
Michael Beck committed
489
	/* We want that the out of ProjX from Start contains the next block at
490
491
	   position 0, the Start block at position 1.  This is necessary for
	   code placement (place_early() ONLY if started GCSE on graphs with dead blocks) */
Michael Beck's avatar
Michael Beck committed
492
	fix_start_proj(irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
493

Michael Beck's avatar
Michael Beck committed
494
495
	current_ir_graph->outs_state = outs_consistent;
	current_ir_graph = rem;
496
497
}

Michael Beck's avatar
Michael Beck committed
498
void assure_irg_outs(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
499
500
	if (get_irg_outs_state(irg) != outs_consistent)
		compute_irg_outs(irg);
Michael Beck's avatar
Michael Beck committed
501
502
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
503
void compute_irp_outs(void) {
Michael Beck's avatar
Michael Beck committed
504
505
506
	int i;
	for (i = get_irp_n_irgs() -1; i >= 0; --i)
		compute_irg_outs(get_irp_irg(i));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
507
}
Michael Beck's avatar
Michael Beck committed
508

Götz Lindenmaier's avatar
Götz Lindenmaier committed
509
void free_irp_outs(void) {
Michael Beck's avatar
Michael Beck committed
510
511
512
	int i;
	for (i = get_irp_n_irgs() -1; i >= 0; --i)
		free_irg_outs(get_irp_irg(i));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
513
}
514
515


Michael Beck's avatar
Michael Beck committed
516
517
518
519
520
521
522
/*------------------------------------------------------------*
 *  This computes the outedges for in interprocedural graph.  *
 *  There is one quirk:                                       *
 *  The number of the outedges for each node is saved in      *
 *  the first member of the ir_node** array. Maybe we should  *
 *  change this to make it more portable...                   *
 *------------------------------------------------------------*/
523
524


525
#ifdef INTERPROCEDURAL_VIEW
Michael Beck's avatar
Michael Beck committed
526
527
528
529
530
/**
 * Inits the number of outedges for each node
 * before counting.
 */
static void init_count(ir_node * node, void *env) {
Matthias Braun's avatar
Matthias Braun committed
531
	(void) env;
Michael Beck's avatar
Michael Beck committed
532
	node->out = (ir_node **) 1; /* 1 for the array size */
533
}
534
535


Michael Beck's avatar
Michael Beck committed
536
537
538
539
540
/**
 * Adjusts the out edge count for its predecessors
 * and adds the current arity to the overall count,
 * which is saved in "env"
 */
Michael Beck's avatar
Michael Beck committed
541
static void node_arity_count(ir_node * node, void * env) {
542
	int *anz = (int *) env, arity, n_outs, i, start;
Michael Beck's avatar
Michael Beck committed
543
	ir_node *succ;
544

Michael Beck's avatar
Michael Beck committed
545
	arity = get_irn_arity(node);
546
	start = (is_Block(node)) ? 0 : -1;
547

548
	n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
549
	*anz += n_outs;
550
551

	for(i = start; i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
552
553
554
		succ = get_irn_n(node, i);
		succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
	}
555
}
556

Michael Beck's avatar
Michael Beck committed
557
558
559
560
/*
 * Inits all nodes for setting the outedges
 * Returns the overall count of edges
 */
561
int count_ip_outs(void) {
Michael Beck's avatar
Michael Beck committed
562
	int res = 0;
563

Michael Beck's avatar
Michael Beck committed
564
	cg_walk(init_count, node_arity_count, &res);
565

Michael Beck's avatar
Michael Beck committed
566
	return(res);
567
568
}

Michael Beck's avatar
Michael Beck committed
569
static int dummy_count = 0, global_count; /* Only for debugging */
570

Michael Beck's avatar
Michael Beck committed
571
572
573
574
575
/**
 * For each node: Sets the pointer to array
 * in which the outedges are written later.
 * The current array start is transported in env
 */
576
static void set_array_pointer(ir_node *node, void *env) {
Michael Beck's avatar
Michael Beck committed
577
578
579
580
581
582
583
584
585
586
587
588
589
	int n_outs;
	ir_node ***free = (ir_node ***) env;

	/* Allocate my array */
	n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
	dummy_count += n_outs;
	assert(dummy_count <= global_count && "More outedges than initially counted!");
	node -> out = *free;
	*free = &((*free)[n_outs]);
	/* We count the successors again, the space will be sufficient.
	   We use this counter to remember the position for the next back
	   edge. */
	node -> out[0] = (ir_node *) 0;
590
591
592
}


Michael Beck's avatar
Michael Beck committed
593
594
595
596
/**
 * Adds an outedge from the predecessor to the
 * current node.
 */
Matthias Braun's avatar
Matthias Braun committed
597
static void set_out_pointer(ir_node * node, void *env) {
Michael Beck's avatar
Michael Beck committed
598
599
	int i, arity = get_irn_arity(node);
	ir_node *succ;
600
	int start = (!is_Block(node)) ? -1 : 0;
Matthias Braun's avatar
Matthias Braun committed
601
	(void) env;
Michael Beck's avatar
Michael Beck committed
602

603
	for (i = start; i < arity; ++i) {
Michael Beck's avatar
Michael Beck committed
604
605
606
607
		succ = get_irn_n(node, i);
		succ->out[get_irn_n_outs(succ)+1] = node;
		succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
	}
608
}
609

610

Michael Beck's avatar
Michael Beck committed
611
612
613
/*
 * Sets the outedges for all nodes.
 */
Michael Beck's avatar
Michael Beck committed
614
615
616
void set_ip_outs(void) {
	ir_node **outedge_array = get_irp_ip_outedges();
	cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
617
618
619
620
}



Michael Beck's avatar
Michael Beck committed
621
622
623
624
625
/*
 * Counts the outedges, allocates memory to save the
 * outedges and fills this outedge array in interprocedural
 * view!
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
626
void compute_ip_outs(void) {
Michael Beck's avatar
Michael Beck committed
627
628
	int n_out_edges;
	ir_node **out_edges;
629

Michael Beck's avatar
Michael Beck committed
630
631
	assert(get_irp_ip_view_state() == ip_view_valid &&
	 "Cannot construct outs for invalid ip view.");
632

Michael Beck's avatar
Michael Beck committed
633
634
635
	if (irp->outs_state != outs_none) {
		free_ip_outs();
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
636

Michael Beck's avatar
Michael Beck committed
637
638
639
640
	global_count = n_out_edges = count_ip_outs();
	out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
	set_irp_ip_outedges(out_edges);
	set_ip_outs();
641
642
}

Michael Beck's avatar
Michael Beck committed
643
644
645
646
647
648
649
void free_ip_outs(void) {
	ir_node **out_edges = get_irp_ip_outedges();
	if (out_edges != NULL) {
		free(out_edges);
		set_irp_ip_outedges(NULL);
	}
	irp->outs_state = outs_none;
650
}
651
#endif
652

653

Götz Lindenmaier's avatar
Götz Lindenmaier committed
654
void free_irg_outs(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
655
656
	/*   current_ir_graph->outs_state = outs_none; */
	irg->outs_state = outs_none;
657

Michael Beck's avatar
Michael Beck committed
658
	if (irg->outs) {
659
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
660
		memset(irg->outs, 0, irg->n_outs);
661
#endif /* defined DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
662
663
		free(irg->outs);
		irg->outs = NULL;
664
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
665
		irg->n_outs = 0;
666
#endif /* defined DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
667
	}
668

669
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
670
671
672
	/* when debugging, *always* reset all nodes' outs!  irg->outs might
	   have been lying to us */
	irg_walk_graph (irg, reset_outs, NULL, NULL);
673
#endif /* defined DEBUG_libfirm */
674
}
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717

static void check_out_edges(ir_node *irn, void *env) {
	int i, j, pos;
	int *pError = env;
	int error = *pError;
	int last = is_Block(irn) ? 0 : -1;

	/* check forward: every input must have an out edge */
	for (i = get_irn_arity(irn) - 1; i >= last; --i) {
		ir_node *pred = get_irn_n(irn, i);

		for (j = get_irn_n_outs(pred) - 1; j >= 0; --j) {
			ir_node *user = get_irn_out_ex(pred, j, &pos);

			if (user == irn && pos == i) {
				break;
			}
		}
		if (j < 0) {
			ir_fprintf(stderr, "Missing out edge from %+F input %d to %+F", irn, i, pred);
			++error;
		}
	}

	/* checking backward */
	for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
		ir_node *user = get_irn_out_ex(irn, i, &pos);

		if (get_irn_n(user, pos) != irn) {
			ir_fprintf(stderr, "Spurious out edge from %+F output %d to %+F", irn, i, user);
			++error;
		}
	}
	*pError = error;
}

/* verify outs edges. */
void verify_outs(ir_graph *irg) {
	int errors = 0;
	irg_walk_graph(irg, NULL, check_out_edges, &errors);
	if (errors > 0)
		panic("Out edges are corrupt");
}