irscc.c 31.9 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
 *
 * 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    Compute the strongly connected regions and build
Götz Lindenmaier's avatar
Götz Lindenmaier committed
23
 *              backedge/loop datastructures.
24
25
 *              A variation on the Tarjan algorithm. See also [Trapp:99],
 *              Chapter 5.2.1.2.
Matthias Braun's avatar
Matthias Braun committed
26
27
28
 * @author   Goetz Lindenmaier
 * @date     7.2002
 * @version  $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
29
 */
Matthias Braun's avatar
Matthias Braun committed
30
#include "config.h"
Michael Beck's avatar
Michael Beck committed
31

32
#include <string.h>
33
#include <stdlib.h>
34

35
#include "irloop_t.h"
36
37

#include "irprog_t.h"
38
#include "irgraph_t.h"
39
40
#include "irnode_t.h"
#include "irgwalk.h"
41
#include "irdump.h"
42
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
43
#include "pmap.h"
44

Götz Lindenmaier's avatar
Götz Lindenmaier committed
45
46
47
48
/* A variant of the loop tree that avoids loops without head.
   This reduces the depth of the loop tree. */
#define NO_LOOPS_WITHOUT_HEAD 1

49
50
51
52
53
54
55
56
57
58
59
/** The outermost graph the scc is computed for. */
static ir_graph *outermost_ir_graph;
/** Current loop construction is working on. */
static ir_loop *current_loop;
/** Counts the number of allocated loop nodes.
 *  Each loop node gets a unique number.
 *  @todo What for? ev. remove.
 */
static int loop_node_cnt = 0;
/** Counter to generate depth first numbering of visited nodes. */
static int current_dfn = 1;
60
61

static int max_loop_depth = 0;
62

63
void link_to_reg_end(ir_node *n, void *env);
Andreas Schösser's avatar
Andreas Schösser committed
64
65
66
void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
ir_node *get_projx_link(ir_node *cb_projx);

Götz Lindenmaier's avatar
Götz Lindenmaier committed
67
68
69
70
/**********************************************************************/
/* Node attributes                                                   **/
/**********************************************************************/

71
72
73
74
75
/**********************************************************************/
/* Node attributes needed for the construction.                      **/
/**********************************************************************/

typedef struct scc_info {
76
77
78
79
80
81
82
83
84
	int in_stack;          /**< Marks whether node is on the stack. */
	int dfn;               /**< Depth first search number. */
	int uplink;            /**< dfn number of ancestor. */
	/*  ir_loop *loop;         *//* Refers to the containing loop. */
	/*
	    struct section *section;
	    xset def;
	    xset use;
	*/
85
86
} scc_info;

87
88
89
/**
 * Allocates a new SCC info on the given obstack.
 */
90
91
static inline scc_info *new_scc_info(struct obstack *obst)
{
92
	return OALLOCZ(obst, scc_info);
93
94
}

95
96
97
/**
 * Mark node n being on the SCC stack.
 */
98
99
static inline void mark_irn_in_stack(ir_node *n)
{
100
101
102
	scc_info *scc = get_irn_link(n);
	assert(scc);
	scc->in_stack = 1;
103
104
}

105
106
107
/**
* Mark node n NOT being on the SCC stack.
*/
108
109
static inline void mark_irn_not_in_stack(ir_node *n)
{
110
111
112
	scc_info *scc = get_irn_link(n);
	assert(scc);
	scc->in_stack = 0;
113
114
}

115
116
117
/**
 * Checks if a node is on the SCC stack.
 */
118
119
static inline int irn_is_in_stack(ir_node *n)
{
120
121
122
	scc_info *scc = get_irn_link(n);
	assert(scc);
	return scc->in_stack;
123
124
}

125
126
127
/**
 * Sets the uplink number for a node.
 */
128
129
static inline void set_irn_uplink(ir_node *n, int uplink)
{
130
131
132
	scc_info *scc = get_irn_link(n);
	assert(scc);
	scc->uplink = uplink;
133
134
}

135
136
137
/**
 * Returns the uplink number for a node.
 */
138
139
static int get_irn_uplink(ir_node *n)
{
140
141
142
	scc_info *scc = get_irn_link(n);
	assert(scc);
	return scc->uplink;
143
144
}

145
146
147
/**
 * Sets the depth-first-search number for a node.
 */
148
149
static inline void set_irn_dfn(ir_node *n, int dfn)
{
150
151
152
	scc_info *scc = get_irn_link(n);
	assert(scc);
	scc->dfn = dfn;
153
154
}

155
156
157
/**
 * Returns the depth-first-search number of a node.
 */
158
159
static int get_irn_dfn(ir_node *n)
{
160
161
162
	scc_info *scc = get_irn_link(n);
	assert(scc);
	return scc->dfn;
163
164
}

165
#if 0
166
167
static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l)
{
168
169
	int i;
	ir_loop *res = NULL;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
170

171
172
173
	/* Test whether n is contained in this loop. */
	for (i = 0; i < get_loop_n_nodes(l); i++)
		if (n == get_loop_node(l, i)) return l;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
174

175
176
	/* Is this a leave in the loop tree? If so loop not found. */
	if (get_loop_n_sons(l) == 0) return NULL;
177

178
179
180
181
182
183
	/* Else descend in the loop tree. */
	for (i = 0; i < get_loop_n_sons(l); i++) {
		res = find_nodes_loop(n, get_loop_son(l, i));
		if (res) break;
	}
	return res;
184
185
186
}

/* @@@ temporary implementation, costly!!! */
187
188
ir_loop * get_irn_loop(ir_node *n)
{
189
190
191
	ir_loop *l = get_irg_loop(current_ir_graph);
	l = find_nodes_loop(n, l);
	return l;
192
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
193
#endif
194
195
196
197
198
199
200
201

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

static ir_node **stack = NULL;
static int tos = 0;                /* top of stack */

Michael Beck's avatar
Michael Beck committed
202
203
204
/**
 * initializes the stack
 */
205
206
static inline void init_stack(void)
{
207
208
209
210
211
212
	if (stack) {
		ARR_RESIZE(ir_node *, stack, 1000);
	} else {
		stack = NEW_ARR_F(ir_node *, 1000);
	}
	tos = 0;
213
214
}

215
216
217
/**
 * Frees the stack.
 */
218
219
static void finish_stack(void)
{
220
221
	DEL_ARR_F(stack);
	stack = NULL;
222
223
}

Michael Beck's avatar
Michael Beck committed
224
225
226
227
228
/**
 * push a node onto the stack
 *
 * @param n  The node to push
 */
229
230
static inline void push(ir_node *n)
{
231
232
233
234
235
236
	if (tos == ARR_LEN(stack)) {
		int nlen = ARR_LEN(stack) * 2;
		ARR_RESIZE(ir_node *, stack, nlen);
	}
	stack [tos++] = n;
	mark_irn_in_stack(n);
237
238
}

Michael Beck's avatar
Michael Beck committed
239
240
241
242
243
/**
 * pop a node from the stack
 *
 * @return  The topmost node
 */
244
245
static inline ir_node *pop(void)
{
246
247
248
	ir_node *n = stack[--tos];
	mark_irn_not_in_stack(n);
	return n;
249
250
}

Michael Beck's avatar
Michael Beck committed
251
252
253
254
/**
 * The nodes up to n belong to the current loop.
 * Removes them from the stack and adds them to the current loop.
 */
255
256
static inline void pop_scc_to_loop(ir_node *n)
{
257
258
259
260
261
262
263
264
265
266
	ir_node *m;

	do {
		m = pop();

		loop_node_cnt++;
		set_irn_dfn(m, loop_node_cnt);
		add_loop_node(current_loop, m);
		set_irn_loop(m, current_loop);
	} while (m != n);
267
268
269
270
271
}

/* GL ??? my last son is my grandson???  Removes loops 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? ) */
272
273
static void close_loop(ir_loop *l)
{
274
275
276
	int last = get_loop_n_elements(l) - 1;
	loop_element lelement = get_loop_element(l, last);
	ir_loop *last_son = lelement.son;
277

278
279
280
	if (get_kind(last_son) == k_ir_loop &&
		get_loop_n_elements(last_son) == 1) {
			ir_loop *gson;
Michael Beck's avatar
Michael Beck committed
281

282
283
			lelement = get_loop_element(last_son, 0);
			gson = lelement.son;
Michael Beck's avatar
Michael Beck committed
284

285
286
			if (get_kind(gson) == k_ir_loop) {
				loop_element new_last_son;
Michael Beck's avatar
Michael Beck committed
287

288
289
290
291
292
				gson->outer_loop = l;
				new_last_son.son = gson;
				l->children[last] = new_last_son;
			}
	}
293

294
	current_loop = l;
295
296
297
298
}

/* Removes and unmarks all nodes up to n from the stack.
   The nodes must be visited once more to assign them to a scc. */
299
300
static inline void pop_scc_unmark_visit(ir_node *n)
{
301
302
303
304
305
306
	ir_node *m = NULL;

	while (m != n) {
		m = pop();
		set_irn_visited(m, 0);
	}
307
308
309
310
311
312
313
314
}

/**********************************************************************/
/* The loop datastructure.                                           **/
/**********************************************************************/

/* Allocates a new loop as son of current_loop.  Sets current_loop
   to the new loop and returns the father. */
315
316
static ir_loop *new_loop(void)
{
317
318
	ir_loop *father = current_loop;
	ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
319

320
321
322
	if (son->depth > max_loop_depth) max_loop_depth = son->depth;
	current_loop = son;
	return father;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
323
}
324

325
326
327
328
329
330
/**********************************************************************/
/* Constructing and destructing the loop/backedge information.       **/
/**********************************************************************/

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

331
332
static inline void init_node(ir_node *n, void *env)
{
333
334
335
	struct obstack *obst = env;
	set_irn_link(n, new_scc_info(obst));
	clear_backedges(n);
336
337
}

338
339
static inline void init_scc_common(void)
{
340
341
342
	current_dfn = 1;
	loop_node_cnt = 0;
	init_stack();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
343
344
}

345
346
static inline void init_scc(ir_graph *irg, struct obstack *obst)
{
347
348
349
350
351
	init_scc_common();
	irg_walk_graph(irg, init_node, NULL, obst);
	/*
	irg_walk (irg, link_to_reg_end, NULL, NULL);
	*/
352
353
}

354
static inline void finish_scc(void)
yb9976's avatar
yb9976 committed
355
356
357
358
{
	finish_stack();
}

359
#ifdef INTERPROCEDURAL_VIEW
360
361
static inline void init_ip_scc(struct obstack *obst)
{
362
363
	init_scc_common();
	cg_walk(init_node, NULL, obst);
Andreas Schösser's avatar
Andreas Schösser committed
364
365

#if EXPERIMENTAL_LOOP_TREE
366
	cg_walk(link_to_reg_end, NULL, NULL);
Andreas Schösser's avatar
Andreas Schösser committed
367
#endif
368
}
369
#endif
370

Michael Beck's avatar
Michael Beck committed
371
372
373
374
375
376
377
378
379
380
/**
 * Check weather a given node represents the outer most Start
 * block. In intra-procedural view this is the start block of the
 * current graph, in interprocedural view it is the start block
 * of the outer most graph.
 *
 * @param n  the node to check
 *
 * This is the condition for breaking the scc recursion.
 */
381
382
static int is_outermost_Start(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
383
384
385
386
	/* Test whether this is the outermost Start node. */
	if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
		ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
	    if (is_Start(pred) && get_nodes_block(pred) == n)
387
388
389
			return 1;
	}
	return 0;
390
391
}

392
393
394
395
396
397
398
399
400
401
static inline int is_ip_Filter(ir_node *n)
{
#ifdef INTERPROCEDURAL_VIEW
	return is_Filter(n) && get_interprocedural_view();
#else
	(void) n;
	return 0;
#endif
}

Andreas Schösser's avatar
Andreas Schösser committed
402
/* When to walk from nodes to blocks. Only for Control flow operations? */
403
404
static inline int get_start_index(ir_node *n)
{
Andreas Schösser's avatar
Andreas Schösser committed
405
406
407
408
409
#undef BLOCK_BEFORE_NODE
#define BLOCK_BEFORE_NODE 1

#if BLOCK_BEFORE_NODE

410
	/* This version assures, that all nodes are ordered absolutely.  This allows
411
412
413
414
415
416
417
	   to undef all nodes in the heap analysis if the block is false, which
	   means not reachable.
	   I.e., with this code, the order on the loop tree is correct. But a
	   (single) test showed the loop tree is deeper. */
	if (get_irn_op(n) == op_Phi  ||
	    is_Block(n)              ||
	    (is_ip_Filter(n))        || (
418
419
420
	      get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
	      get_irn_pinned(n)              == op_pin_state_floats
	    ))
421
422
423
424
		// Here we could test for backedge at -1 which is illegal
		return 0;
	else
		return -1;
Andreas Schösser's avatar
Andreas Schösser committed
425
426
427

#else

428
429
430
431
432
	/* This version causes deeper loop trees (at least we verified this
	   for Polymor).
	   But it guarantees that Blocks are analysed before nodes contained in the
	   block.  If so, we can set the value to undef if the block is not \
	   executed. */
433
	if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
434
435
436
		return -1;
	else
		return 0;
Andreas Schösser's avatar
Andreas Schösser committed
437

438
#endif
439
}
Andreas Schösser's avatar
Andreas Schösser committed
440

Michael Beck's avatar
Michael Beck committed
441
442
443
444
445
446
/**
 * Return non-zero if the given node is a legal loop header:
 * Block, Phi, Filter.
 *
 * @param n  the node to check
 */
447
448
static inline int is_possible_loop_head(ir_node *n)
{
449
450
451
	ir_op *op = get_irn_op(n);
	return ((op == op_Block) ||
	        (op == op_Phi) ||
452
	        (is_ip_Filter(n)));
453
454
}

455
456
457
458
/**
 * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
 * or Filter node and has predecessors within the loop and out
 * of the loop.
Michael Beck's avatar
Michael Beck committed
459
460
461
 *
 * @param n    the node to check
 * @param root only needed for assertion.
462
 */
463
464
static int is_head(ir_node *n, ir_node *root)
{
465
466
467
468
469
470
471
472
	int i, arity;
	int some_outof_loop = 0, some_in_loop = 0;

	/* Test for legal loop header: Block, Phi, ... */
	if (!is_possible_loop_head(n))
		return 0;

	if (!is_outermost_Start(n)) {
Michael Beck's avatar
Michael Beck committed
473
474
#ifndef NDEBUG
		int uplink = get_irn_uplink(root);
475
476
#else
		(void) root;
Michael Beck's avatar
Michael Beck committed
477
#endif
478
479
		arity = get_irn_arity(n);
		for (i = get_start_index(n); i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
480
			ir_node *pred;
481
482
			if (is_backedge(n, i))
				continue;
Michael Beck's avatar
Michael Beck committed
483
484
			pred = get_irn_n(n, i);
			if (! irn_is_in_stack(pred)) {
485
486
				some_outof_loop = 1;
			} else {
Michael Beck's avatar
Michael Beck committed
487
				assert(get_irn_uplink(pred) >= uplink);
488
489
490
491
				some_in_loop = 1;
			}
		}
	}
Michael Beck's avatar
Michael Beck committed
492
	return some_outof_loop & some_in_loop;
493
494
}

495
496
497
498
/**
 * Returns non-zero if n is possible loop head of an endless loop.
 * I.e., it is a Block, Phi or Filter node and has only predecessors
 * within the loop.
Michael Beck's avatar
Michael Beck committed
499
500
501
 *
 * @param n    the node to check
 * @param root only needed for assertion.
502
 */
503
504
static int is_endless_head(ir_node *n, ir_node *root)
{
505
	int i, arity;
Michael Beck's avatar
Michael Beck committed
506
	int none_outof_loop = 1, some_in_loop = 0;
507
508
509
510
511
512

	/* Test for legal loop header: Block, Phi, ... */
	if (!is_possible_loop_head(n))
		return 0;

	if (!is_outermost_Start(n)) {
Michael Beck's avatar
Michael Beck committed
513
514
#ifndef NDEBUG
		int uplink = get_irn_uplink(root);
515
516
#else
		(void) root;
Michael Beck's avatar
Michael Beck committed
517
#endif
518
519
		arity = get_irn_arity(n);
		for (i = get_start_index(n); i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
520
521
522
523
			ir_node *pred;
			if (is_backedge(n, i))
				continue;
			pred = get_irn_n(n, i);
524
			if (!irn_is_in_stack(pred)) {
Michael Beck's avatar
Michael Beck committed
525
				none_outof_loop = 0;
526
			} else {
Michael Beck's avatar
Michael Beck committed
527
				assert(get_irn_uplink(pred) >= uplink);
528
529
530
531
				some_in_loop = 1;
			}
		}
	}
Michael Beck's avatar
Michael Beck committed
532
	return none_outof_loop & some_in_loop;
533
534
535
536
}

/** Returns index of the predecessor with the smallest dfn number
    greater-equal than limit. */
537
538
static int smallest_dfn_pred(ir_node *n, int limit)
{
539
540
541
542
543
544
	int i, index = -2, min = -1;

	if (!is_outermost_Start(n)) {
		int arity = get_irn_arity(n);
		for (i = get_start_index(n); i < arity; i++) {
			ir_node *pred = get_irn_n(n, i);
Michael Beck's avatar
Michael Beck committed
545
546
			if (is_backedge(n, i) || !irn_is_in_stack(pred))
				continue;
547
548
549
550
551
552
553
			if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
				index = i;
				min = get_irn_dfn(pred);
			}
		}
	}
	return index;
554
555
}

Michael Beck's avatar
Michael Beck committed
556
557
558
/**
 * Returns index of the predecessor with the largest dfn number.
 */
559
560
static int largest_dfn_pred(ir_node *n)
{
561
562
563
564
565
566
	int i, index = -2, max = -1;

	if (!is_outermost_Start(n)) {
		int arity = get_irn_arity(n);
		for (i = get_start_index(n); i < arity; i++) {
			ir_node *pred = get_irn_n(n, i);
Michael Beck's avatar
Michael Beck committed
567
568
			if (is_backedge (n, i) || !irn_is_in_stack(pred))
				continue;
569
570
571
572
573
574
575
			if (get_irn_dfn(pred) > max) {
				index = i;
				max = get_irn_dfn(pred);
			}
		}
	}
	return index;
576
577
}

578
579
580
581
582
583
584
/**
 * Searches the stack for possible loop heads.  Tests these for backedges.
 * If it finds a head with an unmarked backedge it marks this edge and
 * returns the tail of the loop.
 * If it finds no backedge returns NULL.
 * ("disable_backedge" in fiasco)
 *
Michael Beck's avatar
Michael Beck committed
585
 * @param n  A node where uplink == dfn.
586
 */
587
588
static ir_node *find_tail(ir_node *n)
{
589
590
591
592
593
594
595
	ir_node *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 */
Michael Beck's avatar
Michael Beck committed
596
	if (is_head(m, n)) {
597
598
599
600
601
602
603
604
605
		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
606
607
			if (is_head(m, n)) {
				res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
608
				if (res_index == -2)  /* no smallest dfn pred found. */
Michael Beck's avatar
Michael Beck committed
609
					res_index = largest_dfn_pred(m);
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628

				if ((m == n) && (res_index == -2)) {  /* don't walk past loop head. */
					i = -1;
				}
				break;
			}

			/* We should not walk past our selves on the stack:  The upcoming nodes
			   are not in this loop. We assume a loop not reachable from Start. */
			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
629
630
				if (is_endless_head(m, n)) {
					res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
					if (res_index == -2)  /* no smallest dfn pred found. */
						res_index = largest_dfn_pred (m);
					break;
				}
				if (m == n) { break; }  /* It's not an unreachable loop, either. */
			}
			//assert(0 && "no head found on stack");
		}

	}
	if (res_index <= -2) {
		/* It's a completely bad loop: without Phi/Block nodes that can
		   be a head. I.e., the code is "dying".  We break the loop by
		   setting Bad nodes. */
		int arity = get_irn_arity(n);
Michael Beck's avatar
Michael Beck committed
646
		ir_node *bad = get_irg_bad(get_irn_irg(n));
647
		for (i = -1; i < arity; ++i) {
Michael Beck's avatar
Michael Beck committed
648
			set_irn_n(n, i, bad);
649
650
651
		}
		return NULL;
	}
Michael Beck's avatar
Michael Beck committed
652
	assert(res_index > -2);
653
654
655

	set_backedge(m, res_index);
	return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
656
657
658
}


Andreas Schösser's avatar
Andreas Schösser committed
659
660
661
#if EXPERIMENTAL_LOOP_TREE

/*  ----------------------------------------------------------------
Michael Beck's avatar
Michael Beck committed
662
    AS:  This is experimental code to build loop trees suitable for
Andreas Schösser's avatar
Andreas Schösser committed
663
664
665
666
667
668
669
670
671
672
673
    the heap analysis. Does not work correctly right now... :-(


    Search in stack for the corresponding first Call-End-ProjX that
    corresponds to one of the control flow predecessors of the given
    block, that is the possible callers.
    returns: the control predecessor to chose\
    or       -1 if no corresponding Call-End-Node could be found
             on the stack.
    - -------------------------------------------------------------- */

674
675
int search_endproj_in_stack(ir_node *start_block)
{
676
677
	int i, j;
	assert(is_Block(start_block));
678
	for (i = tos - 1; i >= 0; --i)
679
	{
680
		if (get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
681
682
683
684
685
686
			get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
		{
			printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
			ir_node *end_projx = stack[i];

			int arity = get_irn_arity(start_block);
687
			for (j = 0; j < arity; j++)
688
689
690
			{
				ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
					get_Proj_proj(end_projx));
691
				if (get_irn_n(start_block, j) == begin_projx)
692
693
694
695
696
697
698
699
				{
					printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
					return(j);
				}
			}
		}
	}
	return(-1);
Andreas Schösser's avatar
Andreas Schösser committed
700
701
702
703
704
}


static pmap *projx_link = NULL;

705
706
void link_to_reg_end (ir_node *n, void *env)
{
707
	if (get_irn_op(n) == op_Proj &&
708
709
710
711
712
713
714
715
		get_irn_mode(n) == mode_X &&
		get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
			/* Reg End Projx -> Find the CallBegin Projx and hash it */
			ir_node *end_projx = n;
			ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
				get_Proj_proj(end_projx));
			set_projx_link(begin_projx, end_projx);
	}
Andreas Schösser's avatar
Andreas Schösser committed
716
717
}

718
719
void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
{
720
	if (projx_link == NULL)
721
722
		projx_link = pmap_create();
	pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
Andreas Schösser's avatar
Andreas Schösser committed
723
724
}

725
726
ir_node *get_projx_link(ir_node *cb_projx)
{
727
	return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
Andreas Schösser's avatar
Andreas Schösser committed
728
729
730
731
}

#endif

732
733
static inline int is_outermost_loop(ir_loop *l)
{
734
	return l == get_loop_outer_loop(l);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
735
}
Andreas Schösser's avatar
Andreas Schösser committed
736
737


738
/*-----------------------------------------------------------*
Andreas Schösser's avatar
Andreas Schösser committed
739
 *                   The core algorithm.                     *
740
 *-----------------------------------------------------------*/
Andreas Schösser's avatar
Andreas Schösser committed
741

Michael Beck's avatar
Michael Beck committed
742
743
744
745
746
/**
 * The core algorithm: Find strongly coupled components.
 *
 * @param n  node to start
 */
747
748
static void scc(ir_node *n)
{
749
	if (irn_visited_else_mark(n))
Michael Beck's avatar
Michael Beck committed
750
		return;
751
752
753
754
755

	/* Initialize the node */
	set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
	set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
	set_irn_loop(n, NULL);
Michael Beck's avatar
Michael Beck committed
756
	++current_dfn;
757
758
759
760
761
762
763
	push(n);

	/* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
	   array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
	   so is_backedge does not access array[-1] but correctly returns false! */

	if (!is_outermost_Start(n)) {
Michael Beck's avatar
Michael Beck committed
764
		int i, arity = get_irn_arity(n);
765

Michael Beck's avatar
Michael Beck committed
766
		for (i = get_start_index(n); i < arity; ++i) {
767
			ir_node *m;
Michael Beck's avatar
Michael Beck committed
768
769
770
			if (is_backedge(n, i))
				continue;
			m = get_irn_n(n, i);
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
			scc(m);
			if (irn_is_in_stack(m)) {
				/* Uplink of m is smaller if n->m is a backedge.
				   Propagate the uplink to mark the loop. */
				if (get_irn_uplink(m) < get_irn_uplink(n))
					set_irn_uplink(n, get_irn_uplink(m));
			}
		}
	}

	if (get_irn_dfn(n) == get_irn_uplink(n)) {
		/* This condition holds for
		   1) the node with the incoming backedge.
		      That is: We found a loop!
		   2) Straight line code, because no uplink has been propagated, so the
		      uplink still is the same as the dfn.

		   But n might not be a proper loop head for the analysis. Proper loop
Michael Beck's avatar
Michael Beck committed
789
		   heads are Block and Phi nodes. find_tail() searches the stack for
790
791
792
793
		   Block's and Phi's and takes those nodes as loop heads for the current
		   loop instead and marks the incoming edge as backedge. */

		ir_node *tail = find_tail(n);
Michael Beck's avatar
Michael Beck committed
794
		if (tail != NULL) {
795
796
797
798
			/* We have a loop, that is no straight line code,
			   because we found a loop head!
			   Next actions: Open a new loop on the loop tree and
			                 try to find inner loops */
Andreas Schösser's avatar
Andreas Schösser committed
799
800

#if NO_LOOPS_WITHOUT_HEAD
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
			/* This is an adaption of the algorithm from fiasco / optscc to
			 * avoid loops without Block or Phi as first node.  This should
			 * severely reduce the number of evaluations of nodes to detect
			 * a fixpoint in the heap analysis.
			 * Further it avoids loops without firm nodes that cause errors
			 * in the heap analyses.
			 * But attention:  don't do it for the outermost loop:  This loop
			 * is not iterated.  A first block can be a loop head in case of
			 * an endless recursion. */

			ir_loop *l;
			int close;
			if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
				l = new_loop();
				close = 1;
			} else {
				l = current_loop;
				close = 0;
			}
820
#else
821
			ir_loop *l = new_loop();
822
#endif
823

824
825
			/* Remove the loop from the stack ... */
			pop_scc_unmark_visit(n);
Andreas Schösser's avatar
Andreas Schösser committed
826

827
828
			/* The current backedge has been marked, that is temporarily eliminated,
			   by find tail. Start the scc algorithm
Michael Beck's avatar
Michael Beck committed
829
			   again on the subgraph that is left (the current loop without the backedge)
830
831
			   in order to find more inner loops. */
			scc(tail);
Andreas Schösser's avatar
Andreas Schösser committed
832

833
			assert(irn_visited(n));
834
#if NO_LOOPS_WITHOUT_HEAD
835
			if (close)
836
#endif
837
838
839
840
841
842
843
844
845
				close_loop(l);
		} else {
			/* No loop head was found, that is we have straight line code.
			   Pop all nodes from the stack to the current loop. */
			pop_scc_to_loop(n);
		}
	}
}

Michael Beck's avatar
Michael Beck committed
846
#ifdef INTERPROCEDURAL_VIEW
847
848
static void my_scc(ir_node *n)
{
849
	int i;
850
	if (irn_visited_else_mark(n))
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
		return;

	/* Initialize the node */
	set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
	set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
	set_irn_loop(n, NULL);
	current_dfn ++;
	push(n);

	/* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
	   array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
	   so is_backedge does not access array[-1] but correctly returns false! */

	if (!is_outermost_Start(n)) {
		int arity = get_irn_arity(n);

		for (i = get_start_index(n); i < arity; i++) {
			ir_node *m;
			if (is_backedge(n, i)) continue;
			m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
871
			/* if (!m || is_Unknown(m)) continue; */
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
			my_scc(m);
			if (irn_is_in_stack(m)) {
				/* Uplink of m is smaller if n->m is a backedge.
				   Propagate the uplink to mark the loop. */
				if (get_irn_uplink(m) < get_irn_uplink(n))
					set_irn_uplink(n, get_irn_uplink(m));
			}
		}
	}

	if (get_irn_dfn(n) == get_irn_uplink(n)) {
		/* This condition holds for
		   1) the node with the incoming backedge.
		      That is: We found a loop!
		   2) Straight line code, because no uplink has been propagated, so the
		      uplink still is the same as the dfn.

		   But n might not be a proper loop head for the analysis. Proper loop
		   heads are Block and Phi nodes. find_tail searches the stack for
		   Block's and Phi's and takes those nodes as loop heads for the current
		   loop instead and marks the incoming edge as backedge. */

		ir_node *tail = find_tail(n);
		if (tail) {
			/* We have a loop, that is no straight line code,
			   because we found a loop head!
			   Next actions: Open a new loop on the loop tree and
			                 try to find inner loops */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
900
901

#if NO_LOOPS_WITHOUT_HEAD
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
			/* This is an adaption of the algorithm from fiasco / optscc to
			 * avoid loops without Block or Phi as first node.  This should
			 * severely reduce the number of evaluations of nodes to detect
			 * a fixpoint in the heap analysis.
			 * Further it avoids loops without firm nodes that cause errors
			 * in the heap analyses. */

			ir_loop *l;
			int close;
			if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
				l = new_loop();
				close = 1;
			} else {
				l = current_loop;
				close = 0;
			}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
918
#else
919
			ir_loop *l = new_loop();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
920
921
#endif

922
923
			/* Remove the loop from the stack ... */
			pop_scc_unmark_visit(n);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
924

925
926
927
928
929
			/* The current backedge has been marked, that is temporarily eliminated,
			   by find tail. Start the scc algorithm
			   anew on the subgraph that is left (the current loop without the backedge)
			   in order to find more inner loops. */
			my_scc(tail);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
930

931
			assert(irn_visited(n));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
932
#if NO_LOOPS_WITHOUT_HEAD
933
			if (close)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
934
#endif
935
936
937
938
939
940
941
				close_loop(l);
		} else {
			/* No loop head was found, that is we have straightline code.
			   Pop all nodes from the stack to the current loop. */
			pop_scc_to_loop(n);
		}
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
942
}
Michael Beck's avatar
Michael Beck committed
943
#endif /* INTERPROCEDURAL_VIEW */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
944

945
946
/* Constructs backedge information for irg. In interprocedural view constructs
   backedges for all methods called by irg, too. */
947
948
int construct_backedges(ir_graph *irg)
{
949
950
951
	ir_graph *rem = current_ir_graph;
	ir_loop *head_rem;
	struct obstack temp;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
952

953
#ifdef INTERPROCEDURAL_VIEW
954
955
	assert(!get_interprocedural_view() &&
	       "not implemented, use construct_ip_backedges()");
956
#endif
Götz Lindenmaier's avatar
Götz Lindenmaier committed
957

958
959
960
	max_loop_depth = 0;
	current_ir_graph   = irg;
	outermost_ir_graph = irg;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
961

962
963
	obstack_init(&temp);
	init_scc(irg, &temp);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
964

965
966
967
	current_loop = NULL;
	new_loop();  /* sets current_loop */
	head_rem = current_loop; /* Just for assertion */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
968

969
	inc_irg_visited(irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
970

971
	scc(get_irg_end(irg));
yb9976's avatar
yb9976 committed
972
973

	finish_scc();
Michael Beck's avatar
Michael Beck committed
974
	obstack_free(&temp, NULL);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
975

976
977
978
979
980
981
982
983
	assert(head_rem == current_loop);
	mature_loops(current_loop, irg->obst);
	set_irg_loop(irg, current_loop);
	set_irg_loopinfo_state(irg, loopinfo_consistent);
	assert(get_irg_loop(irg)->kind == k_ir_loop);
	current_ir_graph = rem;
	return max_loop_depth;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
984
985


986
#ifdef INTERPROCEDURAL_VIEW
987
988
int construct_ip_backedges(void)
{
989
990
991
992
	ir_graph *rem = current_ir_graph;
	int rem_ipv = get_interprocedural_view();
	int i;
	strcut obstack temp;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
993

994
995
	max_loop_depth = 0;
	assert(get_irp_ip_view_state() == ip_view_valid);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
996

997
	outermost_ir_graph = get_irp_main_irg();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
998

999
1000
	obstack_init(&temp);
	init_ip_scc(&temp);