structure.c 26.4 KB
Newer Older
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    Structure Analysis
 * @author   Michael Beck
 * @date     5.4.2007
 * @version  $Id$
26
27
28
29
30
31
32
33
34
35
36
 */
#include "config.h"

#include "firm_common.h"
#include "irnode_t.h"
#include "structure.h"
#include "irdom.h"
#include "irouts.h"
#include "irtools.h"
#include "irgwalk.h"
#include "array.h"
37
#include "irdump.h"
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include "debug.h"

typedef union ir_reg_or_blk ir_reg_or_blk;

/* The structure tree. */
struct ir_reg_tree {
	struct obstack obst;   /**< The obstack where the data is allocated. */
	ir_region *top;        /**< The top region. */
	ir_graph *irg;         /**< Associated graph. */
};

/* A region. */
struct ir_region {
Michael Beck's avatar
Michael Beck committed
52
53
54
55
56
57
58
59
60
61
62
63
64
	firm_kind      kind;      /**< Must be k_ir_region. */
	ir_region_kind type;      /**< The type of this region. */
	ir_region      *parent;   /**< points to the parent. */
	ir_reg_or_blk  *parts;    /**< The list of all region parts. */
	ir_region      **pred;    /**< The predecessor (control flow) regions of this region. */
	ir_region      **succ;    /**< The successor (control flow) regions of this region. */
	unsigned       prenum;    /**< DFS pre-oder number */
	unsigned       postnum;   /**< DFS post-oder number */
	void           *link;     /**< A link field. */
	unsigned long  nr;        /**< for debugging */
	unsigned       visited:1; /**< The visited flag. */
	unsigned       exit:1;    /**< If set, the parent region can be left by this node. */
	unsigned       enter:1;   /**< If set, the parent region can be entered by this node. */
65
66
67
68
69
70
71
72
73
74
};

/* A helper type for unioning blocks and regions. */
union ir_reg_or_blk {
	firm_kind *kind;    /**< For easier check. */
	ir_node   *blk;     /**< A node */
	ir_region *region;  /**< A region. */
};

/* The debug handle. */
Michael Beck's avatar
Michael Beck committed
75
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
76
77
78
79

/**
 * Returns the link of a region.
 */
80
81
void *get_region_link(const ir_region *reg)
{
82
83
84
85
86
87
	return reg->link;
}

/**
 * Sets the link of a region.
 */
88
89
void set_region_link(ir_region *reg, void *data)
{
90
91
92
93
94
95
	reg->link = data;
}

/**
 * Get the immediate region of a block.
 */
96
97
ir_region *get_block_region(const ir_node *block)
{
98
	assert(is_Block(block));
Michael Beck's avatar
Michael Beck committed
99
	return block->attr.block.region;
100
101
102
103
104
}

/**
 * Sets the immediate region of a block.
 */
105
106
void set_block_region(ir_node *block, ir_region *reg)
{
107
	assert(is_Block(block));
Michael Beck's avatar
Michael Beck committed
108
	block->attr.block.region = reg;
109
110
111
112
113
}

/**
 * Get the immediate region of a node.
 */
114
115
ir_region *get_irn_region(ir_node *n)
{
116
117
118
119
120
121
	if (is_no_Block(n))
		n = get_nodes_block(n);
	return get_block_region(n);
}

/**
122
 * Return non-zero if a given firm thing is a region.
123
 */
124
125
int is_region(const void *thing)
{
126
127
128
129
130
	const firm_kind *kind = thing;
	return *kind == k_ir_region;
}

/**
131
 * Return the number of predecessors of a region.
132
 */
133
134
int get_region_n_preds(const ir_region *reg)
{
135
136
137
138
139
140
	return ARR_LEN(reg->pred);
}

/**
 * Return the predecessor region at position pos.
 */
141
142
ir_region *get_region_pred(const ir_region *reg, int pos)
{
143
144
145
146
147
148
149
	assert(0 <= pos && pos <= get_region_n_preds(reg));
	return reg->pred[pos];
}

/**
 * Set the predecessor region at position pos.
 */
150
151
void set_region_pred(ir_region *reg, int pos, ir_region *n)
{
152
153
154
155
156
157
158
	assert(0 <= pos && pos <= get_region_n_preds(reg));
	reg->pred[pos] = n;
}

/**
 * Return the number of successors in a region.
 */
159
160
int get_region_n_succs(const ir_region *reg)
{
161
162
163
164
165
166
	return ARR_LEN(reg->succ);
}

/**
 * Return the successor region at position pos.
 */
167
168
ir_region *get_region_succ(const ir_region *reg, int pos)
{
169
170
171
172
173
174
175
	assert(0 <= pos && pos <= get_region_n_succs(reg));
	return reg->succ[pos];
}

/**
 * Set the successor region at position pos.
 */
176
177
void set_region_succ(ir_region *reg, int pos, ir_region *n)
{
178
179
180
181
182
183
184
185
	assert(0 <= pos && pos <= get_region_n_succs(reg));
	reg->succ[pos] = n;
}

/* ----------------------- construction -------------------------- */

/** Walker environment. */
typedef struct walk_env {
186
	struct obstack *obst;  /**< An obstack to allocate from. */
187
	ir_region **post;      /**< The list of all currently existent top regions. */
188
	unsigned l_post;       /**< The length of the allocated regions array. */
189
190
	unsigned premax;       /**< maximum pre counter */
	unsigned postmax;      /**< maximum post counter */
191
192
	ir_node *start_block;  /**< The start block of the graph. */
	ir_node *end_block;    /**< The end block of the graph. */
193
194
195
196
197
198
} walk_env;

/**
 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
 * node and store the region nodes into the post array.
 */
199
200
static void dfs_walk2(ir_region *reg, walk_env *env)
{
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
	int i, n;

	if (reg->visited == 0) {
		reg->visited = 1;

		reg->prenum = env->premax++;
		for (i = 0, n = get_region_n_succs(reg); i < n; ++i) {
			/* recursion */
			ir_region *succ = get_region_succ(reg, i);
			dfs_walk2(succ, env);
		}

		env->post[env->postmax] = reg;
		reg->postnum = env->postmax++;
	}
}

/**
 * Do a DFS search on the initial regions, assign a prenum and a postnum to every
 * node and store the region nodes into the post array.
 */
222
223
static void dfs_walk(ir_graph *irg, walk_env *env)
{
224
225
226
227
228
229
230
231
232
233
234
235
236
	ir_graph *rem = current_ir_graph;
	ir_region *reg;

	current_ir_graph = irg;
	reg              = get_irn_link(get_irg_start_block(irg));

	env->premax  = 0;
	env->postmax = 0;
	dfs_walk2(reg, env);
	current_ir_graph = rem;
}

/**
Michael Beck's avatar
Michael Beck committed
237
 * Post-walker: wrap all blocks with a BasicBlock region
238
239
 * and count them
 */
240
241
static void wrap_BasicBlocks(ir_node *block, void *ctx)
{
242
243
244
245
	walk_env *env = ctx;
	ir_region *reg;

	/* Allocate a Block wrapper */
246
	reg          = OALLOC(env->obst, ir_region);
247
	reg->kind    = k_ir_region;
Michael Beck's avatar
Michael Beck committed
248
	reg->type    = ir_rk_BasicBlock;
249
250
251
252
	reg->parent  = NULL;
	reg->prenum  = 0;
	reg->postnum = 0;
	reg->visited = 0;
Michael Beck's avatar
Michael Beck committed
253
254
	reg->exit    = 0;
	reg->enter   = 0;
255
256
257
258
259
260
261
262
	reg->link    = NULL;
	reg->nr      = get_irn_node_nr(block);
	reg->parts   = NEW_ARR_D(ir_reg_or_blk, env->obst, 1);

	reg->parts[0].blk = block;
	set_irn_link(block, reg);

	++env->l_post;
Michael Beck's avatar
Michael Beck committed
263
}  /* wrap_BasicBlocks */
264
265

/**
266
 * Post-walker: Create the pred and succ edges for Block wrapper.
267
268
 * Kill edges to the Start and End blocks.
 */
269
270
static void update_BasicBlock_regions(ir_node *blk, void *ctx)
{
271
272
273
274
275
	walk_env *env = ctx;
	ir_region *reg = get_irn_link(blk);
	int i, j, len;

	if (blk == env->start_block) {
276
		/* handle Firm's self loop: Start block has no predecessors */
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
		reg->pred = NEW_ARR_D(ir_region *, env->obst, 0);
	} else {
		len = get_Block_n_cfgpreds(blk);
		reg->pred = NEW_ARR_D(ir_region *, env->obst, len);
		for (i = j = 0; i < len; ++i) {
			ir_node *pred = get_Block_cfgpred_block(blk, i);
			reg->pred[j++] = get_irn_link(pred);
		}
		ARR_SHRINKLEN(reg->pred, j);
	}

	len = get_Block_n_cfg_outs(blk);
	reg->succ = NEW_ARR_D(ir_region *, env->obst, len);
	for (i = j = 0; i < len; ++i) {
		ir_node *succ = get_Block_cfg_out(blk, i);
		reg->succ[j++] = get_irn_link(succ);
	}
	ARR_SHRINKLEN(reg->succ, j);
Michael Beck's avatar
Michael Beck committed
295
}  /* update_BasicBlock_regions */
296

297
/** Allocate a new region on an obstack */
298
299
#define ALLOC_REG(obst, reg, tp) \
	do { \
300
		(reg)          = OALLOC((obst), ir_region); \
301
302
303
304
305
306
		(reg)->kind    = k_ir_region; \
		(reg)->type    = tp; \
		(reg)->parent  = NULL; \
		(reg)->prenum  = 0; \
		(reg)->postnum = 0; \
		(reg)->visited = 0; \
Michael Beck's avatar
Michael Beck committed
307
308
		(reg)->exit    = 0; \
		(reg)->enter   = 0; \
309
310
311
312
313
314
		(reg)->link    = NULL; \
	} while (0)

/**
 * Creates a new Sequence region.
 */
315
316
static ir_region *new_Sequence(struct obstack *obst, ir_region *nset, int nset_len)
{
Michael Beck's avatar
Michael Beck committed
317
	ir_region *reg, *next;
318
	int i;
319
320
321

	ALLOC_REG(obst, reg, ir_rk_Sequence);

322
	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, nset_len);
323

324
	/* beware: list is in reverse order, reverse */
Michael Beck's avatar
Michael Beck committed
325
	next = nset;
326
	for (i = nset_len - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
327
		nset = next;
328
329
		reg->parts[i].region = nset;
		nset->parent = reg;
Michael Beck's avatar
Michael Beck committed
330
331
		next = nset->link;
		nset->link = NULL;
332
333
	}

334
335
336
337
	reg->nr   = reg->parts[0].region->nr;
	reg->pred = DUP_ARR_D(ir_region *, obst, reg->parts[0].region->pred);
	reg->succ = DUP_ARR_D(ir_region *, obst, reg->parts[nset_len - 1].region->succ);

338
339
	DEBUG_ONLY(
		DB((dbg, LEVEL_2, " Created Sequence "));
340
		for (i = 0; i < nset_len; ++i) {
341
342
343
344
345
346
347
348
349
350
			DB((dbg, LEVEL_2, "(%u)", reg->parts[i].region->nr));
		}
		DB((dbg, LEVEL_2, "\n"));
	)
	return reg;
}  /* new_Sequence */

/**
 * Create a new IfThenElse region.
 */
351
352
static ir_region *new_IfThenElse(struct obstack *obst, ir_region *if_b, ir_region *then_b, ir_region *else_b)
{
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
	ir_region *reg;

	ALLOC_REG(obst, reg, ir_rk_IfThenElse);

	reg->nr    = if_b->nr;
	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 3);

	reg->parts[0].region = if_b;   if_b->parent   = reg;
	reg->parts[1].region = then_b; then_b->parent = reg;
	reg->parts[2].region = else_b; else_b->parent = reg;

	reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
	reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);

	DB((dbg, LEVEL_2, " Created If(%u)Then(%u)Else(%u)\n", reg->nr, then_b->nr, else_b->nr));

	return reg;
}  /* new_IfThenElse */

/**
 * Create a new IfThen region.
 */
375
376
static ir_region *new_IfThen(struct obstack *obst, ir_region *if_b, ir_region *then_b)
{
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
	ir_region *reg;

	ALLOC_REG(obst, reg, ir_rk_IfThen);

	reg->nr    = if_b->nr;
	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, 2);

	reg->parts[0].region = if_b;   if_b->parent   = reg;
	reg->parts[1].region = then_b; then_b->parent = reg;

	reg->pred = DUP_ARR_D(ir_region *, obst, if_b->pred);
	reg->succ = DUP_ARR_D(ir_region *, obst, then_b->succ);

	DB((dbg, LEVEL_2, " Created If(%u)Then(%u)\n", reg->nr, then_b->nr));

	return reg;
}  /* new_IfThenElse */

/**
 * Create a new Switch/case region.
 */
398
static ir_region *new_SwitchCase(struct obstack *obst, ir_region_kind type, ir_region *head, ir_region *exit,
399
400
                                 ir_region *cases, int cases_len)
{
401
	ir_region *reg, *c, *n;
402
	int i;
403
404
405
406
407
408
409
410
411
	int add = 1;

	/* check, if the exit block is in the list */
	for (c = cases; c != NULL; c = c->link) {
		if (c == exit) {
			add = 0;
			break;
		}
	}
412
413
414
415

	ALLOC_REG(obst, reg, type);

	reg->nr    = head->nr;
416
	reg->parts = NEW_ARR_D(ir_reg_or_blk, obst, cases_len + add);
417
418

	reg->parts[0].region = head; head->parent = reg;
419
420
421
422
423
424
425
426
	i = 1;
	for (c = cases; c != NULL; c = n) {
		n = c->link;
		if (c != exit) {
			reg->parts[i++].region = c;
			c->parent = reg;
		}
		c->link = NULL;
427
428
429
430
	}

	reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
	reg->succ = NEW_ARR_D(ir_region *, obst, 1);
431
	reg->succ[0] = exit;
432

433
434
435
436
437
438
439
	DEBUG_ONLY(
		DB((dbg, LEVEL_2, " Created %s(%u)\n", reg->type == ir_rk_Switch ? "Switch" : "Case", reg->nr));
		for (i = 1; i < ARR_LEN(reg->parts); ++i) {
			DB((dbg, LEVEL_2, "  Case(%u)\n", reg->parts[i].region->nr));
		}
		DB((dbg, LEVEL_2, "  Exit(%u)\n", exit->nr));
	)
440
441
442
443
444
445
	return reg;
}  /* new_SwitchCase */

/**
 * Create a new SelfLoop region.
 */
446
447
static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
{
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
	ir_region *reg, *succ;
	int i, j, len;

	ALLOC_REG(obst, reg, ir_rk_SelfLoop);

	reg->nr      = head->nr;
	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 1);

	reg->parts[0].region = head; head->parent = reg;

	len = ARR_LEN(head->pred);
	reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
	for (i = j = 0; i < len; ++i) {
		ir_region *pred = get_region_pred(head, i);
		if (pred != head)
			reg->pred[j++] = pred;
	}
	assert(j == len - 1);

	reg->succ = NEW_ARR_D(ir_region *, obst, 1);
	assert(ARR_LEN(head->succ) == 2);

	succ = get_region_succ(head, 0);
	if (succ != head)
		reg->succ[0] = succ;
	else
		reg->succ[0] = get_region_succ(head, 1);

	DB((dbg, LEVEL_2, " Created SelfLoop(%u)\n", reg->nr));

	return reg;
}  /* new_SelfLoop */

/**
 * Create a new RepeatLoop region.
 */
484
485
static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
{
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
	ir_region *reg, *succ;

	ALLOC_REG(obst, reg, ir_rk_RepeatLoop);

	reg->nr      = head->nr;
	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);

	reg->parts[0].region = head; head->parent = reg;
	reg->parts[1].region = body; body->parent = reg;

	reg->pred = DUP_ARR_D(ir_region *, obst, head->pred);
	reg->succ = NEW_ARR_D(ir_region *, obst, 1);
	assert(ARR_LEN(body->succ) == 2);

	succ = get_region_succ(body, 0);
	if (succ != head)
		reg->succ[0] = succ;
	else
		reg->succ[0] = get_region_succ(body, 1);

	DB((dbg, LEVEL_2, " Created RepeatLoop(%u)Body(%u)\n", reg->nr, body->nr));

	return reg;
}  /* new_RepeatLoop */

/**
 * Create a new WhileLoop region.
 */
514
515
static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
{
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
	ir_region *reg, *succ;
	ir_region *body = head->link;
	int i, j, len;

	head->link = NULL;

	ALLOC_REG(obst, reg, ir_rk_WhileLoop);

	reg->nr      = head->nr;
	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, 2);

	reg->parts[0].region = head; head->parent = reg;
	reg->parts[1].region = body; body->parent = reg;

	len = ARR_LEN(head->pred);
	reg->pred = NEW_ARR_D(ir_region *, obst, len - 1);
	for (i = j = 0; i < len; ++i) {
		ir_region *pred = get_region_pred(head, i);
		if (pred != body)
			reg->pred[j++] = pred;
	}
	assert(j == len - 1);

	reg->succ = NEW_ARR_D(ir_region *, obst, 1);
	assert(ARR_LEN(head->succ) == 2);

	succ = get_region_succ(head, 0);
	if (succ != body)
		reg->succ[0] = succ;
	else
		reg->succ[0] = get_region_succ(head, 1);

	DB((dbg, LEVEL_2, " Created WhileLoop(%u)Body(%u)\n", reg->nr, body->nr));

	return reg;
}  /* new_WhileLoop */

Michael Beck's avatar
Michael Beck committed
553
554
555
/**
 * Create a new new_NaturalLoop region.
 */
556
557
static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
{
Michael Beck's avatar
Michael Beck committed
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
	ir_region *reg, *c, *n;
	int i, j, k, len, n_pred, n_succ;

	/* count number of parts */
	for (len = 0, c = head; c != NULL; c = c->link)
		++len;

	ALLOC_REG(obst, reg, ir_rk_WhileLoop);

	reg->nr      = head->nr;
	reg->parts   = NEW_ARR_D(ir_reg_or_blk, obst, len);

	/* enter all parts */
	for (i = 0, c = head; c != NULL; c = n) {
		reg->parts[i++].region = c;
		c->parent = reg;
		n = c->link;
		c->link = NULL;
	}

	/* count number of preds */
	n_pred = 0;
	for (i = get_region_n_preds(head) - 1; i >= 0; --i) {
		ir_region *pred = get_region_pred(head, i);
		if (pred->parent != reg)
			++n_pred;
	}
	reg->pred = NEW_ARR_D(ir_region *, obst, n_pred);
	for (j = 0, i = get_region_n_preds(head) - 1; i >= 0; --i) {
		ir_region *pred = get_region_pred(head, i);
		if (pred->parent != reg)
			reg->pred[j++] = pred;
	}

	/* count number of succs */
	n_succ = 0;
	for (j = 0; j < len; ++j) {
595
596
597
		ir_region *pc = reg->parts[j].region;
		for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
			ir_region *succ = get_region_succ(pc, i);
Michael Beck's avatar
Michael Beck committed
598
599
600
601
602
603
604
			if (succ->parent != reg)
				++n_succ;
		}
	}
	reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
	k = 0;
	for (j = 0; j < len; ++j) {
605
606
607
		ir_region *pc = reg->parts[j].region;
		for (i = get_region_n_succs(pc) - 1; i >= 0; --i) {
			ir_region *succ = get_region_succ(pc, i);
Michael Beck's avatar
Michael Beck committed
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
			if (succ->parent != reg)
				reg->succ[k++] = succ;
		}
	}

	DEBUG_ONLY(
		DB((dbg, LEVEL_2, " Created NaturalLoop(%u)Head(%u)\n", reg->nr, head->nr));
		for (i = 1; i < len; ++i) {
			ir_region *p = reg->parts[i].region;
			DB((dbg, LEVEL_2, "  Body(%u)\n", p->nr));
		}
	)
	return reg;
}  /* new_NaturalLoop */

623
/**
624
 * Return true if region a is an ancestor of region b in DFS search.
625
 */
626
627
static int is_ancestor(const ir_region *a, const ir_region *b)
{
628
629
630
	return (a->prenum <= b->prenum && a->postnum > b->postnum);
}

Michael Beck's avatar
Michael Beck committed
631
/**
632
 * Return true if region pred is a predecessor of region n.
Michael Beck's avatar
Michael Beck committed
633
 */
634
635
static int pred_of(const ir_region *pred, const ir_region *n)
{
Michael Beck's avatar
Michael Beck committed
636
637
638
639
640
641
642
643
	int i;
	for (i = get_region_n_preds(n) - 1; i >= 0; --i) {
		if (get_region_pred(n, i) == pred)
			return 1;
	}
	return 0;
}

644
/**
645
 * Return true if region succ is a successor of region n.
646
 */
647
648
static int succ_of(const ir_region *succ, const ir_region *n)
{
649
650
651
652
653
654
655
656
657
	int i;
	for (i = get_region_n_succs(n) - 1; i >= 0; --i) {
		if (get_region_succ(n, i) == succ)
			return 1;
	}
	return 0;
}

/**
658
 * Reverse a linked list of regions.
659
 */
660
661
static struct ir_region *reverse_list(ir_region *n)
{
662
663
664
665
666
667
668
669
670
671
672
673
674
	ir_region *prev = NULL, *next;

	for (; n; n = next) {
		next = n->link;
		n->link = prev;
		prev = n;
	}
	return prev;
}

/**
 * Find the cyclic region in the subgraph entered by node.
 */
675
676
static ir_region *find_cyclic_region(ir_region *node)
{
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
	int i;
	ir_region *last = node;
	int improper = 0;

	for (i = get_region_n_preds(node) - 1; i >= 0; --i) {
		ir_region *pred = get_region_pred(node, i);

		/* search backedges */
		if (!pred->link && pred != last && is_ancestor(node, pred)) {
			ir_region *rem = last;
			int j;

			last->link = pred;
			last       = pred;
			for (j = get_region_n_preds(pred) - 1; j >= 0; --j) {
				ir_region *p = get_region_pred(pred, j);

				/* Search regions we didn't visited yet and
				   link them into the list. */
				if (!p->link && p != last) {
					if (is_ancestor(node, p)) {
						last->link = p;
						last       = p;
					} else {
						improper = 1;
					}
				}
			}
			/* reverse the list. */
			last = rem->link;
			rem->link = reverse_list(rem->link);
		}
	}

	if (node->link && improper) {
Michael Beck's avatar
Michael Beck committed
712
713
		/* found an improper region, do minimization */

714
715
716
717
718
719
720
721
722
	}
	return node;
}

#define LINK(list) ((ir_region *)list->link)

/**
 * Detect a cyclic region.
 */
723
724
static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
{
725
726
727
728
729
730
731
732
733
734
735
736
737
738
	ir_region *list;

	/* simple cases first */
	if (succ_of(node, node)) {
		return new_SelfLoop(obst, node);
	}
	if (get_region_n_succs(node) == 1) {
		ir_region *succ = get_region_succ(node, 0);
		if (get_region_n_preds(succ) == 1 && succ_of(node, succ)) {
			return new_RepeatLoop(obst, node, succ);
		}
	}
	list = find_cyclic_region(node);

Michael Beck's avatar
Michael Beck committed
739
740
741
742
743
744
745
	if (list->link) {
		if (!LINK(list)->link && get_region_n_succs(list->link) == 1) {
			/* only one body block with only one successor (the head) */
			return new_WhileLoop(obst, list);
		}
		/* A Loop with one head */
		return new_NaturalLoop(obst, list);
746
747
748
749
750
	}

	return NULL;
}

751
/**
752
 * Clear all links on a list. Needed, because we expect cleared links.
753
 */
754
755
static void clear_list(ir_region *list)
{
756
757
758
759
760
761
762
763
	ir_region *next;

	for (next = list; next; list = next) {
		next = list->link;
		list->link = NULL;
	}
}

764
#define ADD_LIST(list, n) do { n->link = list; list = n; ++list##_len; } while (0)
765

766
767
768
/**
 * Detect an acyclic region.
 */
769
770
static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
{
771
772
	ir_region *n, *m;
	int p, s, i, k;
773
774
	ir_region *nset = NULL;
	int nset_len = 0;
775
776
777
778
779
780
781
782
783
784
785
786
787
788
	ir_region *res;

	/* check for a block containing node */
	n = node;
	p = get_region_n_preds(n) == 1;
	s = 1;
	while (p & s) {
		n = get_region_pred(n, 0);
		p = get_region_n_preds(n) == 1;
		s = get_region_n_succs(n) == 1;
	}
	p = 1;
	s = get_region_n_succs(n) == 1;
	while (p & s) {
789
		ADD_LIST(nset, n);
790
791
792
793
794
		n = get_region_succ(n, 0);
		p = get_region_n_preds(n) == 1;
		s = get_region_n_succs(n) == 1;
	}
	if (p) {
795
		ADD_LIST(nset, n);
796
	}
797
	if (nset_len > 1) {
798
		/* node --> .. --> .. */
799
		res = new_Sequence(obst, nset, nset_len);
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
		return res;
	}
	node = n;

	/* check for IfThenElse */
	k = get_region_n_succs(node);
	if (k == 2) {
		int n_succs, m_succs, n_preds, m_preds;

		n = get_region_succ(node, 0);
		m = get_region_succ(node, 1);

		n_succs = get_region_n_succs(n);
		m_succs = get_region_n_succs(m);
		n_preds = get_region_n_preds(n);
		m_preds = get_region_n_preds(m);
		if (n_succs == 1 && n_succs == m_succs && n_preds == m_preds &&
		    get_region_succ(n, 0) == get_region_succ(m, 0)) {
			/*
			 *    /-->n---\
			 * node      ...
			 *    \-->m---/
			 */
			return new_IfThenElse(obst, node, n, m);
		}
Michael Beck's avatar
Michael Beck committed
825
		if (n_succs == 1 &&
826
		    get_region_succ(n, 0) == m &&
Michael Beck's avatar
Michael Beck committed
827
		    pred_of(node, m)) {
828
829
830
831
832
833
			/*
			 * node -->n-->m
			 *    \-------/
			 */
			return new_IfThen(obst, node, n);
		}
Michael Beck's avatar
Michael Beck committed
834
		if (m_succs == 1 &&
835
		    get_region_succ(m, 0) == m &&
Michael Beck's avatar
Michael Beck committed
836
		    pred_of(node, n)) {
837
838
839
840
841
842
843
844
			/*
			 * node -->m-->n
			 *    \-------/
			 */
			return new_IfThen(obst, node, m);
		}
	}
	/* check for Switch, case */
845
	if (k > 0) {
846
		ir_region *rexit = NULL;
847
848
849
850
851
852
853
		nset = NULL; nset_len = 0;
		p = 0;
		for (i = k - 1; i >= 0; --i) {
			n = get_region_succ(node, i);
			ADD_LIST(nset, n);
			if (get_region_n_succs(n) != 1) {
				/* must be the exit */
854
				rexit = n;
855
856
				++p;
				if (p > 1)
857
858
859
					break;
			}
		}
860
861
862
863
864
865
866
867
868
		if (p <= 1) {
			ir_region_kind kind = ir_rk_Case;
			ir_region *pos_exit_1 = NULL;
			ir_region *pos_exit_2 = NULL;

			/* find the exit */
			for (m = nset; m != NULL; m = m->link) {
				if (get_region_n_succs(m) != 1) {
					/* must be the exit block */
869
870
871
					if (rexit == NULL) {
						rexit = m;
					} else if (rexit != m) {
872
						/* two exits */
873
						rexit = NULL;
874
875
876
877
878
879
						break;
					}
				} else {
					ir_region *succ = get_region_succ(m, 0);

					if (succ->link == NULL) {
880
						if (rexit == NULL) {
881
							if (succ == pos_exit_1)
882
								rexit = succ;
883
							else if (succ == pos_exit_2)
884
								rexit = succ;
885
886
887
888
889
890
891
892
							else if (pos_exit_1 == NULL)
								pos_exit_1 = succ;
							else if (pos_exit_2 == NULL)
								pos_exit_2 = succ;
							else {
								/* more than two possible exits */
								break;
							}
893
						} else if (rexit != succ) {
894
							/* two exits */
895
							rexit = NULL;
896
897
898
							break;
						}
					}
899
900
				}
			}
901
			if (rexit != NULL) {
902
903
904
				/* do the checks */
				for (n = nset; n != NULL; n = n->link) {
					ir_region *succ;
905
					if (n == rexit) {
906
907
908
909
						/* good, default fall through */
						continue;
					}
					succ = get_region_succ(n, 0);
910
					if (succ == rexit) {
911
912
913
914
915
916
917
918
919
920
921
						/* good, switch to exit */
						continue;
					}
					if (succ->link == NULL) {
						/* another exit */
						break;
					} else {
						/* a fall through */
						kind = ir_rk_Switch;
					}
				}
922

923
924
				if (n == NULL) {
					/* detected */
925
					return new_SwitchCase(obst, kind, node, rexit, nset, nset_len);
926
				}
927
928
			}
		}
929
		clear_list(nset);
930
931
932
933
934
935
936
937
	}
	return NULL;
}

/**
 * replace all pred edges from region pred that points to any of the set set
 * to ONE edge to reg.
 */
938
939
static void replace_pred(ir_region *succ, ir_region *reg)
{
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
	int i, len = get_region_n_preds(succ);
	int have_one = 0;

	for (i = 0; i < len; ++i) {
		ir_region *pred = get_region_pred(succ, i);

		if (pred->parent == reg) {
			ir_region *r;

			if (have_one) {
				/* kill it */
				r = get_region_pred(succ, --len);
			} else {
				/* replace it */
				have_one = 1;
				r = reg;
			}
			set_region_pred(succ, i, r);
Michael Beck's avatar
Michael Beck committed
958
959
960
		} else {
			/* the current region can be entered by this node */
			pred->enter = 1;
961
962
963
964
965
966
967
968
969
		}
	}
	ARR_SHRINKLEN(succ->pred, len);
}

/**
 * replace all succ edges from region pred that points to any of the set set
 * to ONE edge to reg.
 */
970
971
static void replace_succ(ir_region *pred, ir_region *reg)
{
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
	int i, len = get_region_n_succs(pred);
	int have_one = 0;

	for (i = 0; i < len; ++i) {
		ir_region *succ = get_region_succ(pred, i);

		if (succ->parent == reg) {
			ir_region *r;

			if (have_one) {
				/* kill it */
				r = get_region_succ(pred, --len);
			} else {
				/* replace it */
				have_one = 1;
				r = reg;
			}
			set_region_succ(pred, i, r);
Michael Beck's avatar
Michael Beck committed
990
991
992
		} else {
			/* current region can be left by this node */
			succ->exit = 1;
993
994
995
996
997
998
999
1000
		}
	}
	ARR_SHRINKLEN(pred->succ, len);
}

/**
 * Reduce the graph by the node reg.
 */
1001
1002
static void reduce(walk_env *env, ir_region *reg)
{
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
	int i;
	ir_region *head = reg->parts[0].region;
	unsigned maxorder = head->postnum;
	unsigned minorder = head->prenum;

	/* second step: replace all preds in successors */
	for (i = get_region_n_succs(reg) - 1; i >= 0; --i) {
		ir_region *succ = get_region_succ(reg, i);

		replace_pred(succ, reg);
	}

1015
	/* third step: replace all succs in predessors */
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
	for (i = get_region_n_preds(reg) - 1; i >= 0; --i) {
		ir_region *pred = get_region_pred(reg, i);

		replace_succ(pred, reg);
	}

	reg->prenum  = minorder;
	reg->postnum = maxorder;
	env->post[maxorder] = reg;
}

/**
 * Construct the region tree of a graph by doing
 * structural analysis.
 *
 * Uses link fields of nodes.
 *
 * @param irg  the graph
 */
1035
1036
ir_reg_tree *construct_region_tree(ir_graph *irg)
{
1037
1038
	walk_env env;
	ir_graph *rem = current_ir_graph;
1039
	ir_reg_tree *res = XMALLOC(ir_reg_tree);
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062

	obstack_init(&res->obst);

	current_ir_graph = irg;

	FIRM_DBG_REGISTER(dbg, "firm.ana.structure");
	firm_dbg_set_mask(dbg, SET_LEVEL_5);

	DB((dbg, LEVEL_1, "Structural analysis on %+F starts...\n", irg));

	dump_ir_block_graph(irg, "-structure_start");

	/* we need dominance info */
	assure_doms(irg);
	/* and out edges */
	assure_irg_outs(irg);

	env.start_block = get_irg_start_block(irg);
	env.end_block   = get_irg_end_block(irg);

	/* create the Block wrapper and count them */
	env.l_post = 0;
	env.obst   = &res->obst;
Michael Beck's avatar
Michael Beck committed
1063
1064
	irg_block_walk_graph(irg, NULL, wrap_BasicBlocks, &env);
	irg_block_walk_graph(irg, NULL, update_BasicBlock_regions, &env);
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076

	env.post = NEW_ARR_F(ir_region *, env.l_post);

	/* do the DFS walk */
	dfs_walk(irg, &env);

	DB((dbg, LEVEL_1, "%d regions left\n", env.postmax));
	if (env.postmax > 1) {
		unsigned postctr = 0;
		do {
			ir_region *reg, *n = env.post[postctr];
			do {
1077
				if (n->parent != NULL) {
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
					/* already folded */
					break;
				}
				/* locate an acyclic region if present */
				reg = acyclic_region_type(env.obst, n);
				if (reg == NULL) {
					/* locate a cyclic region */
					reg = cyclic_region_type(env.obst, n);
				}
				if (reg != NULL) {
					/* found a new region */
					reduce(&env, reg);
					n = reg;
				}
			} while (reg != NULL);
			++postctr;
		} while (postctr < env.postmax);
	}
	DB((dbg, LEVEL_1, "Structural analysis finished.\n"));

	DEL_ARR_F(env.post);
	current_ir_graph = rem;

	res->top = env.post[0];
	res->irg = irg;
	return res;
}

/**
 * Walk over the region tree.
 *
 * @param reg   a region node
 * @param pre   walker function, executed before the children of a tree node are visited
 * @param post  walker function, executed after the children of a tree node are visited
 * @param env   environment, passed to pre and post
 */
1114
1115
static void region_tree_walk2(ir_region *reg, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
{
1116
1117
1118
1119
	int i, n;

	if (pre)
		pre(reg, env);
Michael Beck's avatar
Michael Beck committed
1120
	if (reg->type != ir_rk_BasicBlock) {
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
		for (i = 0, n = ARR_LEN(reg->parts); i < n; ++i)
			region_tree_walk2(reg->parts[i].region, pre, post, env);
	}
	if (post)
		post(reg, env);
}

/**
 * Walk over the region tree.
 *
 * @param tree  the tree
 * @param pre   walker function, executed before the children of a tree node are visited
 * @param post  walker function, executed after the children of a tree node are visited
 * @param env   environment, passed to pre and post
 */
1136
1137
void region_tree_walk(ir_reg_tree *tree, irg_reg_walk_func *pre, irg_reg_walk_func *post, void *env)
{
1138
1139
	region_tree_walk2(tree->top, pre, post, env);
}