callgraph.c 38.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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * This file is part of libFirm.
 *
 * 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.
 *
 * 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.
 */

/**
 * @file
 * @brief       Representation and computation of the callgraph.
 * @author      Goetz Lindenmaier
 * @date        21.7.2004
 * @version     $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
26
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
Michael Beck's avatar
Michael Beck committed
28

29
#include <string.h>
Michael Beck's avatar
Michael Beck committed
30
31
#include <stdlib.h>

Götz Lindenmaier's avatar
Götz Lindenmaier committed
32
33
34
35
36
37
38
#include "callgraph.h"

#include "irloop_t.h"
#include "irprog_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"

39
#include "cgana.h"
40
#include "execution_frequency.h"
41

Götz Lindenmaier's avatar
Götz Lindenmaier committed
42
43
#include "array.h"
#include "pmap.h"
Michael Beck's avatar
Michael Beck committed
44
#include "hashptr.h"
Michael Beck's avatar
Michael Beck committed
45
#include "raw_bitset.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
46
47
48

#include "irgwalk.h"

49
static ir_visited_t master_cg_visited = 0;
50
51
static inline int cg_irg_visited      (ir_graph *n);
static inline void mark_cg_irg_visited(ir_graph *n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
52

53
/** Returns the callgraph state of the program representation. */
54
55
irp_callgraph_state get_irp_callgraph_state(void)
{
Christian Würdig's avatar
Christian Würdig committed
56
	return irp->callgraph_state;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
57
}
58
59

/* Sets the callgraph state of the program representation. */
60
61
void set_irp_callgraph_state(irp_callgraph_state s)
{
Christian Würdig's avatar
Christian Würdig committed
62
	irp->callgraph_state = s;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
63
64
}

65
/* Returns the number of procedures that call the given irg. */
66
67
int get_irg_n_callers(const ir_graph *irg)
{
Christian Würdig's avatar
Christian Würdig committed
68
69
	if (irg->callers) return ARR_LEN(irg->callers);
	return -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
70
}
71
72

/* Returns the caller at position pos. */
73
74
ir_graph *get_irg_caller(const ir_graph *irg, int pos)
{
Michael Beck's avatar
Michael Beck committed
75
	assert(pos >= 0 && pos < get_irg_n_callers(irg));
Christian Würdig's avatar
Christian Würdig committed
76
77
	if (irg->callers) return irg->callers[pos];
	return NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
78
}
79
80

/* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
81
82
int is_irg_caller_backedge(const ir_graph *irg, int pos)
{
Michael Beck's avatar
Michael Beck committed
83
	assert(pos >= 0 && pos < get_irg_n_callers(irg));
84
	return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
85
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
86

87
/** Search the caller in the list of all callers and set it's backedge property. */
88
89
static void set_irg_caller_backedge(ir_graph *irg, ir_graph *caller)
{
Christian Würdig's avatar
Christian Würdig committed
90
	int i, n_callers = get_irg_n_callers(irg);
91
92
93

	/* allocate a new array on demand */
	if (irg->caller_isbe == NULL)
94
		irg->caller_isbe = rbitset_malloc(n_callers);
Christian Würdig's avatar
Christian Würdig committed
95
96
	for (i = 0; i < n_callers; ++i) {
		if (get_irg_caller(irg, i) == caller) {
97
			rbitset_set(irg->caller_isbe, i);
Christian Würdig's avatar
Christian Würdig committed
98
99
100
			break;
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
101
102
}

103
/* Returns non-zero if the irg has a backedge caller. */
104
105
int has_irg_caller_backedge(const ir_graph *irg)
{
Christian Würdig's avatar
Christian Würdig committed
106
	int i, n_callers = get_irg_n_callers(irg);
107
108
109

	if (irg->caller_isbe != NULL) {
		for (i = 0; i < n_callers; ++i)
110
111
			if (rbitset_is_set(irg->caller_isbe, i))
				return 1;
112
	}
Christian Würdig's avatar
Christian Würdig committed
113
	return 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
114
115
}

116
117
118
119
120
/**
 * Find the reversion position of a caller.
 * Given the position pos_caller of an caller of irg, return
 * irg's callee position on that caller.
 */
121
122
static int reverse_pos(const ir_graph *callee, int pos_caller)
{
Christian Würdig's avatar
Christian Würdig committed
123
124
125
126
127
128
129
130
131
132
	ir_graph *caller = get_irg_caller(callee, pos_caller);
	/* search the other relation for the corresponding edge. */
	int pos_callee = -1;
	int i, n_callees = get_irg_n_callees(caller);
	for (i = 0; i < n_callees; ++i) {
		if (get_irg_callee(caller, i) == callee) {
			pos_callee = i;
			break;
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
133

Christian Würdig's avatar
Christian Würdig committed
134
	assert(pos_callee >= 0);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
135

Christian Würdig's avatar
Christian Würdig committed
136
	return pos_callee;
137
138
}

139
/* Returns the maximal loop depth of call nodes that call along this edge. */
140
141
int get_irg_caller_loop_depth(const ir_graph *irg, int pos)
{
Christian Würdig's avatar
Christian Würdig committed
142
143
	ir_graph *caller     = get_irg_caller(irg, pos);
	int       pos_callee = reverse_pos(irg, pos);
144

Christian Würdig's avatar
Christian Würdig committed
145
	return get_irg_callee_loop_depth(caller, pos_callee);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
146
147
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
148

149
/* Returns the number of procedures that are called by the given irg. */
150
151
int get_irg_n_callees(const ir_graph *irg)
{
Christian Würdig's avatar
Christian Würdig committed
152
153
	if (irg->callees) return ARR_LEN(irg->callees);
	return -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
154
}
155
156

/* Returns the callee at position pos. */
157
158
ir_graph *get_irg_callee(const ir_graph *irg, int pos)
{
Michael Beck's avatar
Michael Beck committed
159
	assert(pos >= 0 && pos < get_irg_n_callees(irg));
160
	if (irg->callees) return irg->callees[pos]->irg;
Christian Würdig's avatar
Christian Würdig committed
161
	return NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
162
}
163
164

/* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
165
166
int is_irg_callee_backedge(const ir_graph *irg, int pos)
{
Michael Beck's avatar
Michael Beck committed
167
168
	assert(pos >= 0 && pos < get_irg_n_callees(irg));
	return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
169
}
170
171

/* Returns non-zero if the irg has a backedge callee. */
172
173
int has_irg_callee_backedge(const ir_graph *irg)
{
Christian Würdig's avatar
Christian Würdig committed
174
	int i, n_callees = get_irg_n_callees(irg);
175
176
177

	if (irg->callee_isbe != NULL) {
		for (i = 0; i < n_callees; ++i)
Michael Beck's avatar
Michael Beck committed
178
179
			if (rbitset_is_set(irg->callee_isbe, i))
				return 1;
180
	}
Christian Würdig's avatar
Christian Würdig committed
181
	return 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
182
}
183
184
185
186

/**
 * Mark the callee at position pos as a backedge.
 */
187
188
static void set_irg_callee_backedge(ir_graph *irg, int pos)
{
189
190
191
192
	int n = get_irg_n_callees(irg);

	/* allocate a new array on demand */
	if (irg->callee_isbe == NULL)
Michael Beck's avatar
Michael Beck committed
193
194
195
		irg->callee_isbe = rbitset_malloc(n);
	assert(pos >= 0 && pos < n);
	rbitset_set(irg->callee_isbe, pos);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
196
197
}

198
/* Returns the maximal loop depth of call nodes that call along this edge. */
199
200
int get_irg_callee_loop_depth(const ir_graph *irg, int pos)
{
Michael Beck's avatar
Michael Beck committed
201
	assert(pos >= 0 && pos < get_irg_n_callees(irg));
202
	if (irg->callees) return irg->callees[pos]->max_depth;
Christian Würdig's avatar
Christian Würdig committed
203
	return -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
204
205
}

206
static double get_irg_callee_execution_frequency(const ir_graph *irg, int pos)
207
{
208
	ir_node **arr = irg->callees[pos]->call_list;
Christian Würdig's avatar
Christian Würdig committed
209
	int i, n_Calls = ARR_LEN(arr);
210
	double freq = 0.0;
211

Christian Würdig's avatar
Christian Würdig committed
212
213
214
215
	for (i = 0; i < n_Calls; ++i) {
		freq += get_irn_exec_freq(arr[i]);
	}
	return freq;
216
217
}

218
219
static double get_irg_callee_method_execution_frequency(const ir_graph *irg,
                                                        int pos)
220
{
Christian Würdig's avatar
Christian Würdig committed
221
222
223
	double call_freq = get_irg_callee_execution_frequency(irg, pos);
	double meth_freq = get_irg_method_execution_frequency(irg);
	return call_freq * meth_freq;
224
225
}

226
227
static double get_irg_caller_method_execution_frequency(const ir_graph *irg,
                                                        int pos)
228
{
Christian Würdig's avatar
Christian Würdig committed
229
230
	ir_graph *caller     = get_irg_caller(irg, pos);
	int       pos_callee = reverse_pos(irg, pos);
231

Christian Würdig's avatar
Christian Würdig committed
232
	return get_irg_callee_method_execution_frequency(caller, pos_callee);
233
234
235
}


Götz Lindenmaier's avatar
Götz Lindenmaier committed
236
237
/* --------------------- Compute the callgraph ------------------------ */

238
/**
239
240
 * Walker called by compute_callgraph(), analyses all Call nodes.
 */
241
242
static void ana_Call(ir_node *n, void *env)
{
Christian Würdig's avatar
Christian Würdig committed
243
244
	int i, n_callees;
	ir_graph *irg;
Matthias Braun's avatar
Matthias Braun committed
245
	(void) env;
Christian Würdig's avatar
Christian Würdig committed
246
247
248
249
250
251
252
253
254
255

	if (! is_Call(n)) return;

	irg = get_irn_irg(n);
	n_callees = get_Call_n_callees(n);
	for (i = 0; i < n_callees; ++i) {
		ir_entity *callee_e = get_Call_callee(n, i);
		ir_graph *callee = get_entity_irg(callee_e);

		if (callee) {
256
257
			cg_callee_entry buf;
			cg_callee_entry *found;
Christian Würdig's avatar
Christian Würdig committed
258
259
260
261
262
263
264
265
266
267
268
			int depth;

			buf.irg = callee;

			pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
			found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
			if (found) {  /* add Call node to list, compute new nesting. */
				ir_node **arr = found->call_list;
				ARR_APP1(ir_node *, arr, n);
				found->call_list = arr;
			} else { /* New node, add Call node and init nesting. */
269
				found = OALLOC(irg->obst, cg_callee_entry);
Christian Würdig's avatar
Christian Würdig committed
270
271
272
273
274
275
276
277
278
279
				found->irg = callee;
				found->call_list = NEW_ARR_F(ir_node *, 1);
				found->call_list[0] = n;
				found->max_depth = 0;
				pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
			}
			depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
			found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
280
281
}

282
/** compare two ir graphs in a cg_callee_entry */
283
284
static int cg_callee_entry_cmp(const void *elt, const void *key)
{
285
286
	const cg_callee_entry *e1 = elt;
	const cg_callee_entry *e2 = key;
Christian Würdig's avatar
Christian Würdig committed
287
	return e1->irg != e2->irg;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
288
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
289

290
/** compare two ir graphs for pointer identity */
291
292
static int graph_cmp(const void *elt, const void *key)
{
293
294
295
	const ir_graph *e1 = elt;
	const ir_graph *e2 = key;
	return e1 != e2;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
296
297
298
299
}


/* Construct and destruct the callgraph. */
300
301
void compute_callgraph(void)
{
302
	int i, n_irgs;
Christian Würdig's avatar
Christian Würdig committed
303

Michael Beck's avatar
Michael Beck committed
304
#ifdef INTERPROCEDURAL_VIEW
Christian Würdig's avatar
Christian Würdig committed
305
	assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
Michael Beck's avatar
Michael Beck committed
306
#endif
Christian Würdig's avatar
Christian Würdig committed
307
308
309

	/* initialize */
	free_callgraph();
310
311

	n_irgs = get_irp_n_irgs();
Christian Würdig's avatar
Christian Würdig committed
312
313
314
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
		assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
315
		irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
Christian Würdig's avatar
Christian Würdig committed
316
317
318
319
320
321
322
323
324
325
326
327
328
329
		irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
		//construct_cf_backedges(irg);
	}

	/* Compute the call graph */
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
		construct_cf_backedges(irg);   // We also find the maximal loop depth of a call.
		irg_walk_graph(irg, ana_Call, NULL, NULL);
	}

	/* Change the sets to arrays. */
	for (i = 0; i < n_irgs; ++i) {
		int j, count;
330
		cg_callee_entry *callee;
Christian Würdig's avatar
Christian Würdig committed
331
332
333
334
335
		ir_graph *c, *irg = get_irp_irg(i);
		pset *callee_set, *caller_set;

		callee_set = (pset *)irg->callees;
		count = pset_count(callee_set);
336
337
338
		irg->callees = NEW_ARR_F(cg_callee_entry *, count);
		irg->callee_isbe = NULL;
		callee = pset_first(callee_set);
Christian Würdig's avatar
Christian Würdig committed
339
		for (j = 0; j < count; ++j) {
340
341
			irg->callees[j] = callee;
			callee = pset_next(callee_set);
Christian Würdig's avatar
Christian Würdig committed
342
343
		}
		del_pset(callee_set);
344
		assert(callee == NULL);
Christian Würdig's avatar
Christian Würdig committed
345
346
347
348

		caller_set = (pset *)irg->callers;
		count = pset_count(caller_set);
		irg->callers = NEW_ARR_F(ir_graph *, count);
349
		irg->caller_isbe =  NULL;
Christian Würdig's avatar
Christian Würdig committed
350
351
352
353
354
355
356
357
358
		c = pset_first(caller_set);
		for (j = 0; j < count; ++j) {
			irg->callers[j] = c;
			c = pset_next(caller_set);
		}
		del_pset(caller_set);
		assert(c == NULL);
	}
	set_irp_callgraph_state(irp_callgraph_consistent);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
359
360
}

361
/* Destruct the callgraph. */
362
363
void free_callgraph(void)
{
Christian Würdig's avatar
Christian Würdig committed
364
365
366
367
368
369
370
371
372
373
374
375
376
	int i, n_irgs = get_irp_n_irgs();
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
		if (irg->callees) DEL_ARR_F(irg->callees);
		if (irg->callers) DEL_ARR_F(irg->callers);
		if (irg->callee_isbe) free(irg->callee_isbe);
		if (irg->caller_isbe) free(irg->caller_isbe);
		irg->callees = NULL;
		irg->callers = NULL;
		irg->callee_isbe = NULL;
		irg->caller_isbe = NULL;
	}
	set_irp_callgraph_state(irp_callgraph_none);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
377
378
379
380
381
382
383
}

/* ----------------------------------------------------------------------------------- */
/* A walker for the callgraph                                                          */
/* ----------------------------------------------------------------------------------- */


384
385
static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
{
Christian Würdig's avatar
Christian Würdig committed
386
	int i, n_callees;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
387

388
389
	if (cg_irg_visited(irg))
		return;
Christian Würdig's avatar
Christian Würdig committed
390
	mark_cg_irg_visited(irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
391

Christian Würdig's avatar
Christian Würdig committed
392
393
	if (pre)
		pre(irg, env);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
394

Christian Würdig's avatar
Christian Würdig committed
395
396
397
398
399
	n_callees = get_irg_n_callees(irg);
	for (i = 0; i < n_callees; i++) {
		ir_graph *m = get_irg_callee(irg, i);
		do_walk(m, pre, post, env);
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
400

Christian Würdig's avatar
Christian Würdig committed
401
402
	if (post)
		post(irg, env);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
403
404
}

405
406
void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
{
407
	int i, n_irgs = get_irp_n_irgs();
408
	++master_cg_visited;
Christian Würdig's avatar
Christian Würdig committed
409

410
411
412
	/* roots are methods which have no callers in the current program */
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
413

414
415
		if (get_irg_n_callers(irg) == 0)
			do_walk(irg, pre, post, env);
416
417
	}

418
	/* in case of unreachable call loops we haven't visited some irgs yet */
Christian Würdig's avatar
Christian Würdig committed
419
420
	for (i = 0; i < n_irgs; i++) {
		ir_graph *irg = get_irp_irg(i);
421
		do_walk(irg, pre, post, env);
Christian Würdig's avatar
Christian Würdig committed
422
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
423
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
424
425
426
427
428

/* ----------------------------------------------------------------------------------- */
/* loop construction algorithm                                                         */
/* ----------------------------------------------------------------------------------- */

429
430
static ir_graph *outermost_ir_graph;   /**< The outermost graph the scc is computed
                                            for */
Michael Beck's avatar
Michael Beck committed
431
static ir_loop *current_loop;      /**< Current cfloop construction is working
432
                                        on. */
Michael Beck's avatar
Michael Beck committed
433
static int loop_node_cnt = 0;      /**< Counts the number of allocated cfloop nodes.
434
435
                                        Each cfloop node gets a unique number.
                                        What for? ev. remove. @@@ */
Michael Beck's avatar
Michael Beck committed
436
static int current_dfn = 1;        /**< Counter to generate depth first numbering
437
                                        of visited nodes.  */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
438

439
440
441
/*-----------------*/
/* Node attributes */
/*-----------------*/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
442
443

typedef struct scc_info {
Christian Würdig's avatar
Christian Würdig committed
444
445
446
447
	int in_stack;          /**< Marks whether node is on the stack. */
	int dfn;               /**< Depth first search number. */
	int uplink;            /**< dfn number of ancestor. */
	int visited;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
448
449
} scc_info;

Michael Beck's avatar
Michael Beck committed
450
/**
451
 * allocates a new scc_info on the obstack
Michael Beck's avatar
Michael Beck committed
452
 */
453
454
static inline scc_info *new_scc_info(struct obstack *obst)
{
455
	return OALLOCZ(obst, scc_info);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
456
457
}

458
459
460
/**
 * Returns non-zero if a graph was already visited.
 */
461
462
static inline int cg_irg_visited(ir_graph *irg)
{
463
	return irg->self_visited >= master_cg_visited;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
464
465
}

466
467
468
/**
 * Marks a graph as visited.
 */
469
470
static inline void mark_cg_irg_visited(ir_graph *irg)
{
471
	irg->self_visited = master_cg_visited;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
472
473
}

474
475
476
/**
 * Set a graphs visited flag to i.
 */
477
478
static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
{
479
	irg->self_visited = i;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
480
481
}

482
483
484
/**
 * Returns the visited flag of a graph.
 */
485
486
static inline ir_visited_t get_cg_irg_visited(ir_graph *irg)
{
487
	return irg->self_visited;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
488
489
}

490
491
static inline void mark_irg_in_stack(ir_graph *irg)
{
492
	scc_info *info = get_irg_link(irg);
493
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
494
	info->in_stack = 1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
495
496
}

497
498
static inline void mark_irg_not_in_stack(ir_graph *irg)
{
499
	scc_info *info = get_irg_link(irg);
500
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
501
	info->in_stack = 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
502
503
}

504
505
static inline int irg_is_in_stack(ir_graph *irg)
{
506
	scc_info *info = get_irg_link(irg);
507
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
508
	return info->in_stack;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
509
510
}

511
512
static inline void set_irg_uplink(ir_graph *irg, int uplink)
{
513
	scc_info *info = get_irg_link(irg);
514
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
515
	info->uplink = uplink;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
516
517
}

518
519
static inline int get_irg_uplink(ir_graph *irg)
{
520
	scc_info *info = get_irg_link(irg);
521
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
522
	return info->uplink;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
523
524
}

525
526
static inline void set_irg_dfn(ir_graph *irg, int dfn)
{
527
	scc_info *info = get_irg_link(irg);
528
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
529
	info->dfn = dfn;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
530
531
}

532
533
static inline int get_irg_dfn(ir_graph *irg)
{
534
	scc_info *info = get_irg_link(irg);
535
	assert(info && "missing call to init_scc()");
Christian Würdig's avatar
Christian Würdig committed
536
	return info->dfn;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
537
538
539
540
541
542
543
}

/**********************************************************************/
/* A stack.                                                          **/
/**********************************************************************/

static ir_graph **stack = NULL;
Michael Beck's avatar
Michael Beck committed
544
static int tos = 0;                /**< top of stack */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
545

Michael Beck's avatar
Michael Beck committed
546
/**
547
 * Initialize the irg stack.
Michael Beck's avatar
Michael Beck committed
548
 */
549
550
static inline void init_stack(void)
{
Christian Würdig's avatar
Christian Würdig committed
551
	if (stack) {
Michael Beck's avatar
Michael Beck committed
552
		ARR_RESIZE(ir_graph *, stack, 1000);
Christian Würdig's avatar
Christian Würdig committed
553
	} else {
Michael Beck's avatar
Michael Beck committed
554
		stack = NEW_ARR_F(ir_graph *, 1000);
Christian Würdig's avatar
Christian Würdig committed
555
556
	}
	tos = 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
557
558
}

Michael Beck's avatar
Michael Beck committed
559
560
561
562
/**
 * push a graph on the irg stack
 * @param n the graph to be pushed
 */
563
564
static inline void push(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
565
566
567
	if (tos == ARR_LEN(stack)) {
		int nlen = ARR_LEN(stack) * 2;
		ARR_RESIZE(ir_node *, stack, nlen);
Christian Würdig's avatar
Christian Würdig committed
568
	}
569
570
	stack [tos++] = irg;
	mark_irg_in_stack(irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
571
572
}

Michael Beck's avatar
Michael Beck committed
573
574
575
/**
 * return the topmost graph on the stack and pop it
 */
576
577
static inline ir_graph *pop(void)
{
578
579
580
	ir_graph *irg = stack[--tos];
	mark_irg_not_in_stack(irg);
	return irg;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
581
582
}

Michael Beck's avatar
Michael Beck committed
583
/**
584
 * The nodes up to irg belong to the current loop.
Michael Beck's avatar
Michael Beck committed
585
586
 * Removes them from the stack and adds them to the current loop.
 */
587
588
static inline void pop_scc_to_loop(ir_graph *irg)
{
Christian Würdig's avatar
Christian Würdig committed
589
	ir_graph *m;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
590

Christian Würdig's avatar
Christian Würdig committed
591
592
593
594
	do {
		m = pop();
		loop_node_cnt++;
		set_irg_dfn(m, loop_node_cnt);
595
		add_loop_irg(current_loop, m);
Christian Würdig's avatar
Christian Würdig committed
596
597
		m->l = current_loop;
		//m->callgraph_loop_depth = current_loop->depth;
598
	} while (m != irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
599
600
601
602
603
}

/* GL ??? my last son is my grandson???  Removes cfloops with no
   ir_nodes in them.  Such loops have only another loop as son. (Why
   can't they have two loops as sons? Does it never get that far? ) */
604
605
static void close_loop(ir_loop *l)
{
Christian Würdig's avatar
Christian Würdig committed
606
607
608
	int last = get_loop_n_elements(l) - 1;
	loop_element lelement = get_loop_element(l, last);
	ir_loop *last_son = lelement.son;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
609

Christian Würdig's avatar
Christian Würdig committed
610
	if (get_kind(last_son) == k_ir_loop &&
611
612
	    get_loop_n_elements(last_son) == 1) {
		ir_loop *gson;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
613

614
615
616
617
		lelement = get_loop_element(last_son, 0);
		gson = lelement.son;
		if (get_kind(gson) == k_ir_loop) {
			loop_element new_last_son;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
618

619
620
621
622
			gson->outer_loop = l;
			new_last_son.son = gson;
			l->children[last] = new_last_son;
		}
Christian Würdig's avatar
Christian Würdig committed
623
624
	}
	current_loop = l;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
625
626
}

Michael Beck's avatar
Michael Beck committed
627
628
629
630
/**
 * Removes and unmarks all nodes up to n from the stack.
 * The nodes must be visited once more to assign them to a scc.
 */
631
632
static inline void pop_scc_unmark_visit(ir_graph *n)
{
Christian Würdig's avatar
Christian Würdig committed
633
	ir_graph *m = NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
634

Christian Würdig's avatar
Christian Würdig committed
635
636
637
638
	while (m != n) {
		m = pop();
		set_cg_irg_visited(m, 0);
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
639
640
641
}

/**********************************************************************/
Michael Beck's avatar
Michael Beck committed
642
/* The loop data structure.                                          **/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
643
644
/**********************************************************************/

Michael Beck's avatar
Michael Beck committed
645
646
647
648
/**
 * Allocates a new loop as son of current_loop.  Sets current_loop
 * to the new loop and returns the father.
 */
649
650
static ir_loop *new_loop(void)
{
651
652
	ir_loop *father = current_loop;
	ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
653

Christian Würdig's avatar
Christian Würdig committed
654
655
	current_loop = son;
	return father;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
656
657
}

658

Götz Lindenmaier's avatar
Götz Lindenmaier committed
659
660
661
662
663
664
/**********************************************************************/
/* Constructing and destructing the loop/backedge information.       **/
/**********************************************************************/

/* Initialization steps. **********************************************/

665
666
static void init_scc(struct obstack *obst)
{
Christian Würdig's avatar
Christian Würdig committed
667
668
	int i;
	int n_irgs;
Michael Beck's avatar
Michael Beck committed
669

Christian Würdig's avatar
Christian Würdig committed
670
671
672
	current_dfn   = 1;
	loop_node_cnt = 0;
	init_stack();
Michael Beck's avatar
Michael Beck committed
673

Christian Würdig's avatar
Christian Würdig committed
674
675
676
	n_irgs = get_irp_n_irgs();
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);
677
		set_irg_link(irg, new_scc_info(obst));
Christian Würdig's avatar
Christian Würdig committed
678
679
680
		irg->callgraph_recursion_depth = 0;
		irg->callgraph_loop_depth      = 0;
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
681
682
}

683
/** Returns non-zero if n is a loop header, i.e., it is a Block node
Götz Lindenmaier's avatar
Götz Lindenmaier committed
684
685
686
687
 *  and has predecessors within the cfloop and out of the cfloop.
 *
 *  @param root: only needed for assertion.
 */
688
689
static int is_head(ir_graph *n, ir_graph *root)
{
Christian Würdig's avatar
Christian Würdig committed
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
	int i, arity;
	int some_outof_loop = 0, some_in_loop = 0;

	arity = get_irg_n_callees(n);
	for (i = 0; i < arity; i++) {
		ir_graph *pred = get_irg_callee(n, i);
		if (is_irg_callee_backedge(n, i)) continue;
		if (!irg_is_in_stack(pred)) {
			some_outof_loop = 1;
		} else {
			if (get_irg_uplink(pred) < get_irg_uplink(root))  {
				assert(get_irg_uplink(pred) >= get_irg_uplink(root));
			}
			some_in_loop = 1;
		}
	}

Matthias Braun's avatar
Matthias Braun committed
707
	return some_outof_loop && some_in_loop;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
708
}
Michael Beck's avatar
Michael Beck committed
709
710

/**
711
 * Returns non-zero if n is possible loop head of an endless loop.
Michael Beck's avatar
Michael Beck committed
712
713
714
715
 * I.e., it is a Block, Phi or Filter node and has only predecessors
 * within the loop.
 * @arg root: only needed for assertion.
 */
716
static int is_endless_head(ir_graph *n, ir_graph *root)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
717
{
Christian Würdig's avatar
Christian Würdig committed
718
719
	int i, arity;
	int some_outof_loop = 0, some_in_loop = 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
720

Christian Würdig's avatar
Christian Würdig committed
721
722
723
724
	arity = get_irg_n_callees(n);
	for (i = 0; i < arity; i++) {
		ir_graph *pred = get_irg_callee(n, i);
		assert(pred);
Michael Beck's avatar
Michael Beck committed
725
726
		if (is_irg_callee_backedge(n, i))
			continue;
Christian Würdig's avatar
Christian Würdig committed
727
728
729
		if (!irg_is_in_stack(pred)) {
			some_outof_loop = 1;
		} else {
Michael Beck's avatar
Michael Beck committed
730
			if (get_irg_uplink(pred) < get_irg_uplink(root)) {
Christian Würdig's avatar
Christian Würdig committed
731
732
733
734
735
				assert(get_irg_uplink(pred) >= get_irg_uplink(root));
			}
			some_in_loop = 1;
		}
	}
Matthias Braun's avatar
Matthias Braun committed
736
	return !some_outof_loop && some_in_loop;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
737
738
}

Michael Beck's avatar
Michael Beck committed
739
#ifdef INTERPROCEDURAL_VIEW
Michael Beck's avatar
Michael Beck committed
740
741
742
743
/**
 * Check whether there is a parallel edge in the ip control flow.
 * Only
 */
744
static int is_ip_head(ir_graph *n, ir_graph *pred)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
745
{
Christian Würdig's avatar
Christian Würdig committed
746
	int is_be = 0;
Michael Beck's avatar
Michael Beck committed
747

Christian Würdig's avatar
Christian Würdig committed
748
749
750
751
752
753
754
755
756
757
758
759
760
	int iv_rem = get_interprocedural_view();
	set_interprocedural_view(1);
	{
		ir_node *sblock = get_irg_start_block(n);
		int i, arity = get_Block_n_cfgpreds(sblock);

		//printf(" edge from "); DDMG(n);
		//printf(" to pred   "); DDMG(pred);
		//printf(" sblock    "); DDMN(sblock);

		for (i = 0; i < arity; i++) {
			ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
			//printf("  "); DDMN(pred_cfop);
761
			if (is_CallBegin(pred_cfop)) { /* could be Unknown */
Christian Würdig's avatar
Christian Würdig committed
762
763
764
765
766
767
768
769
770
771
772
				ir_graph *ip_pred = get_irn_irg(pred_cfop);
				//printf("   "); DDMG(ip_pred);
				if ((ip_pred == pred) && is_backedge(sblock, i)) {
					//printf("   found\n");
					is_be = 1;
				}
			}
		}
	}
	set_interprocedural_view(iv_rem);
	return is_be;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
773
}
Michael Beck's avatar
Michael Beck committed
774
#endif /* INTERPROCEDURAL_VIEW */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
775

Michael Beck's avatar
Michael Beck committed
776
777
778
779
/**
 * Returns index of the predecessor with the smallest dfn number
 * greater-equal than limit.
 */
780
static int smallest_dfn_pred(ir_graph *n, int limit)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
781
{
Christian Würdig's avatar
Christian Würdig committed
782
	int i, index = -2, min = -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
783

Christian Würdig's avatar
Christian Würdig committed
784
785
786
	int arity = get_irg_n_callees(n);
	for (i = 0; i < arity; i++) {
		ir_graph *pred = get_irg_callee(n, i);
Michael Beck's avatar
Michael Beck committed
787
788
		if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
			continue;
Christian Würdig's avatar
Christian Würdig committed
789
790
791
792
793
		if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
			index = i;
			min = get_irg_dfn(pred);
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
794

Christian Würdig's avatar
Christian Würdig committed
795
	return index;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
796
797
}

Michael Beck's avatar
Michael Beck committed
798
/** Returns index of the predecessor with the largest dfn number. */
799
800
static int largest_dfn_pred(ir_graph *n)
{
Christian Würdig's avatar
Christian Würdig committed
801
	int i, index = -2, max = -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
802

Christian Würdig's avatar
Christian Würdig committed
803
	int arity = get_irg_n_callees(n);
Michael Beck's avatar
Michael Beck committed
804
	for (i = 0; i < arity; ++i) {
Christian Würdig's avatar
Christian Würdig committed
805
806
807
808
809
810
811
		ir_graph *pred = get_irg_callee(n, i);
		if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
		if (get_irg_dfn(pred) > max) {
			index = i;
			max = get_irg_dfn(pred);
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
812

Christian Würdig's avatar
Christian Würdig committed
813
	return index;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
814
815
}

Michael Beck's avatar
Michael Beck committed
816
#ifndef INTERPROCEDURAL_VIEW
817
818
static ir_graph *find_tail(ir_graph *n)
{
Christian Würdig's avatar
Christian Würdig committed
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
	ir_graph *m;
	int i, res_index = -2;

	/*
	if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
	*/
	m = stack[tos-1];  /* tos = top of stack */
	if (is_head (m, n)) {
		res_index = smallest_dfn_pred(m, 0);
		if ((res_index == -2) &&  /* no smallest dfn pred found. */
			(n == m))
			return NULL;
	} else {
		if (m == n) return NULL;    // Is this to catch Phi - self loops?
		for (i = tos-2; i >= 0; --i) {
			m = stack[i];

Michael Beck's avatar
Michael Beck committed
836
837
			if (is_head(m, n)) {
				res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
Christian Würdig's avatar
Christian Würdig committed
838
				if (res_index == -2)  /* no smallest dfn pred found. */
Michael Beck's avatar
Michael Beck committed
839
					res_index = largest_dfn_pred(m);
Christian Würdig's avatar
Christian Würdig committed
840
841
842
843
844
845
846
847

				if ((m == n) && (res_index == -2)) {
					i = -1;
				}
				break;
			}

			/* We should not walk past our selves on the stack:  The upcoming nodes
848
			   are not in this loop. We assume a loop not reachable from Start. */
Christian Würdig's avatar
Christian Würdig committed
849
850
851
852
853
854
855
856
857
858
859
			if (m == n) {
				i = -1;
				break;
			}

		}

		if (i < 0) {
			/* A dead loop not reachable from Start. */
			for (i = tos-2; i >= 0; --i) {
				m = stack[i];
Michael Beck's avatar
Michael Beck committed
860
861
				if (is_endless_head(m, n)) {
					res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
Christian Würdig's avatar
Christian Würdig committed
862
					if (res_index == -2)  /* no smallest dfn pred found. */
Michael Beck's avatar
Michael Beck committed
863
						res_index = largest_dfn_pred(m);
Christian Würdig's avatar
Christian Würdig committed
864
865
866
867
868
869
870
871
872
873
					break;
				}
				if (m == n) { break; }  /* It's not an unreachable loop, either. */
			}
			//assert(0 && "no head found on stack");
		}

	}
	assert (res_index > -2);

Michael Beck's avatar
Michael Beck committed
874
	set_irg_callee_backedge(m, res_index);
Christian Würdig's avatar
Christian Würdig committed
875
	return get_irg_callee(m, res_index);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
876
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
877
#else
878
879
static ir_graph *find_tail(ir_graph *n)
{
Christian Würdig's avatar
Christian Würdig committed
880
881
	ir_graph *m;
	int i, res_index = -2;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
882

Christian Würdig's avatar
Christian Würdig committed
883
884
885
886
887
	ir_graph *res;
	ir_graph *in_and_out    = NULL;
	ir_graph *only_in       = NULL;
	ir_graph *ip_in_and_out = NULL;
	ir_graph *ip_only_in    = NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
888

Christian Würdig's avatar
Christian Würdig committed
889
	//printf("find tail for "); DDMG(n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
890

Christian Würdig's avatar
Christian Würdig committed
891
892
893
	for (i = tos-1; i >= 0; --i) {
		ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
		m = stack[i];
Götz Lindenmaier's avatar
Götz Lindenmaier committed
894

Michael Beck's avatar
Michael Beck committed
895
		if (is_head(m, n)) {
Christian Würdig's avatar
Christian Würdig committed
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
			//printf(" found 1a! "); DDM;
			in_and_out = m;
			if (is_ip_head(pred, m)) {
				//printf(" found 1b! "); DDM;
				ip_in_and_out = m;
			}
		} else if (!ip_only_in && is_endless_head(m, n)) {
			only_in = m;
			//printf(" found 2a! "); DDM;
			if (is_ip_head(pred, m)) {
				//printf(" found 2b! "); DDM;
				ip_only_in = m;
			}
		} else if (is_ip_head(pred, m)) {
			//printf(" found 3! "); DDM;   This happens for self recursions in the second
			//assert(0);                   scc iteration (the one to flip the loop.)
		}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
913

Christian Würdig's avatar
Christian Würdig committed
914
		if (ip_in_and_out) break;    /* That's what we really want. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
915

Christian Würdig's avatar
Christian Würdig committed
916
917
		if (m == n) break;   /* Don't walk past n on the stack! */
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
918
919


Christian Würdig's avatar
Christian Würdig committed
920
921
922
	if (!in_and_out && !only_in)
		/* There is no loop */
		return NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
923
924


Christian Würdig's avatar
Christian Würdig committed
925
926
927
	/* Is there a head in the callgraph without a head in the
	   ip cf graph? */
	assert(in_and_out || only_in);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
928

Christian Würdig's avatar
Christian Würdig committed
929
	m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
930

Christian Würdig's avatar
Christian Würdig committed
931
932
	if (!m)
		m = (in_and_out) ? in_and_out : only_in;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
933

Christian Würdig's avatar
Christian Würdig committed
934
	//printf("*** head is "); DDMG(m);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
935

Michael Beck's avatar
Michael Beck committed
936
	res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
Christian Würdig's avatar
Christian Würdig committed
937
	if (res_index == -2)  /* no smallest dfn pred found. */
Michael Beck's avatar
Michael Beck committed
938
		res_index = largest_dfn_pred(m);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
939

Michael Beck's avatar
Michael Beck committed
940
	set_irg_callee_backedge(m, res_index);
Christian Würdig's avatar
Christian Würdig committed
941
942
943
	res = get_irg_callee(m, res_index);
	//printf("*** tail is "); DDMG(res);
	return res;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
944
}
Michael Beck's avatar
Michael Beck committed
945
#endif /* INTERPROCEDURAL_VIEW */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
946
947

/*-----------------------------------------------------------*
948
949
 *                   The core algorithm.                     *
 *-----------------------------------------------------------*/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
950
951


952
953
static void cgscc(ir_graph *n)
{
Christian Würdig's avatar
Christian Würdig committed
954
	int i, arity;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
955

Christian Würdig's avatar
Christian Würdig committed
956
957
	if (cg_irg_visited(n)) return;
	mark_cg_irg_visited(n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
958

Christian Würdig's avatar
Christian Würdig committed
959
960
961
962
963
	/* Initialize the node */
	set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
	set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
	current_dfn ++;
	push(n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
964

Christian Würdig's avatar
Christian Würdig committed
965
966
967
968
969
	arity = get_irg_n_callees(n);
	for (i = 0; i < arity; i++) {
		ir_graph *m;
		if (is_irg_callee_backedge(n, i)) continue;
		m = get_irg_callee(n, i);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
970

Christian Würdig's avatar
Christian Würdig committed
971
972
		/** This marks the backedge, but does it guarantee a correct loop tree? */
		//if (m == n) { set_irg_callee_backedge(n, i); continue; }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
973