structure.c 26.7 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2011 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
	if (!is_Block(n))
117
118
119
120
121
		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
	const firm_kind *kind = (const firm_kind*) thing;
127
128
129
130
	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
	ir_graph *rem = current_ir_graph;
	ir_region *reg;

	current_ir_graph = irg;
228
	reg              = (ir_region*) get_irn_link(get_irg_start_block(irg));
229
230
231
232
233
234
235
236

	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
	walk_env *env = (walk_env*) ctx;
243
244
245
	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
	walk_env *env = (walk_env*) ctx;
	ir_region *reg = (ir_region*) get_irn_link(blk);
273
274
275
	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
		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);
283
			reg->pred[j++] = (ir_region*) get_irn_link(pred);
284
285
286
287
288
289
290
291
		}
		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);
292
		reg->succ[j++] = (ir_region*) get_irn_link(succ);
293
294
	}
	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;
330
		next = (ir_region*) nset->link;
Michael Beck's avatar
Michael Beck committed
331
		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
	int add = 1;

	/* check, if the exit block is in the list */
406
	for (c = cases; c != NULL; c = (ir_region*) c->link) {
407
408
409
410
411
		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
	i = 1;
	for (c = cases; c != NULL; c = n) {
421
		n = (ir_region*) c->link;
422
423
424
425
426
		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
	DEBUG_ONLY({
		size_t i;
435
436
437
438
439
		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
446
	return reg;
}  /* new_SwitchCase */

/**
 * Create a new SelfLoop region.
 */
447
448
static ir_region *new_SelfLoop(struct obstack *obst, ir_region *head)
{
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
484
	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.
 */
485
486
static ir_region *new_RepeatLoop(struct obstack *obst, ir_region *head, ir_region *body)
{
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
514
	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.
 */
515
516
static ir_region *new_WhileLoop(struct obstack *obst, ir_region *head)
{
517
	ir_region *reg, *succ;
518
	ir_region *body = (ir_region*) head->link;
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
553
	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
554
555
556
/**
 * Create a new new_NaturalLoop region.
 */
557
558
static ir_region *new_NaturalLoop(struct obstack *obst, ir_region *head)
{
Michael Beck's avatar
Michael Beck committed
559
560
561
562
	ir_region *reg, *c, *n;
	int i, j, k, len, n_pred, n_succ;

	/* count number of parts */
563
	for (len = 0, c = head; c != NULL; c = (ir_region*) c->link)
Michael Beck's avatar
Michael Beck committed
564
565
566
567
568
569
570
571
572
573
574
		++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;
575
		n = (ir_region*) c->link;
Michael Beck's avatar
Michael Beck committed
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
		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) {
596
597
598
		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
599
600
601
602
603
604
605
			if (succ->parent != reg)
				++n_succ;
		}
	}
	reg->succ = NEW_ARR_D(ir_region *, obst, n_succ);
	k = 0;
	for (j = 0; j < len; ++j) {
606
607
608
		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
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
			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 */

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

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

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

/**
659
 * Reverse a linked list of regions.
660
 */
661
662
static struct ir_region *reverse_list(ir_region *n)
{
663
664
665
	ir_region *prev = NULL, *next;

	for (; n; n = next) {
666
		next = (ir_region*) n->link;
667
668
669
670
671
672
673
674
675
		n->link = prev;
		prev = n;
	}
	return prev;
}

/**
 * Find the cyclic region in the subgraph entered by node.
 */
676
677
static ir_region *find_cyclic_region(ir_region *node)
{
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
	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. */
707
708
			last = (ir_region*) rem->link;
			rem->link = reverse_list((ir_region*) rem->link);
709
710
711
712
		}
	}

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

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

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

/**
 * Detect a cyclic region.
 */
724
725
static ir_region *cyclic_region_type(struct obstack *obst, ir_region *node)
{
726
727
728
729
730
731
732
733
734
735
736
737
738
739
	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
740
	if (list->link) {
741
		if (!LINK(list)->link && get_region_n_succs((ir_region*) list->link) == 1) {
Michael Beck's avatar
Michael Beck committed
742
743
744
745
746
			/* 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);
747
748
749
750
751
	}

	return NULL;
}

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

	for (next = list; next; list = next) {
760
		next = (ir_region*) list->link;
761
762
763
764
		list->link = NULL;
	}
}

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

767
768
769
/**
 * Detect an acyclic region.
 */
770
771
static ir_region *acyclic_region_type(struct obstack *obst, ir_region *node)
{
772
773
	ir_region *n, *m;
	int p, s, i, k;
774
775
	ir_region *nset = NULL;
	int nset_len = 0;
776
777
778
779
780
781
782
783
784
785
786
787
788
789
	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) {
790
		ADD_LIST(nset, n);
791
792
793
794
795
		n = get_region_succ(n, 0);
		p = get_region_n_preds(n) == 1;
		s = get_region_n_succs(n) == 1;
	}
	if (p) {
796
		ADD_LIST(nset, n);
797
	}
798
	if (nset_len > 1) {
799
		/* node --> .. --> .. */
800
		res = new_Sequence(obst, nset, nset_len);
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
		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
826
		if (n_succs == 1 &&
827
		    get_region_succ(n, 0) == m &&
Michael Beck's avatar
Michael Beck committed
828
		    pred_of(node, m)) {
829
830
831
832
833
834
			/*
			 * node -->n-->m
			 *    \-------/
			 */
			return new_IfThen(obst, node, n);
		}
Michael Beck's avatar
Michael Beck committed
835
		if (m_succs == 1 &&
836
		    get_region_succ(m, 0) == m &&
Michael Beck's avatar
Michael Beck committed
837
		    pred_of(node, n)) {
838
839
840
841
842
843
844
845
			/*
			 * node -->m-->n
			 *    \-------/
			 */
			return new_IfThen(obst, node, m);
		}
	}
	/* check for Switch, case */
846
	if (k > 0) {
847
		ir_region *rexit = NULL;
848
849
850
851
852
853
854
		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 */
855
				rexit = n;
856
857
				++p;
				if (p > 1)
858
859
860
					break;
			}
		}
861
862
863
864
865
866
		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 */
867
			for (m = (ir_region*) nset; m != NULL; m = (ir_region*) m->link) {
868
869
				if (get_region_n_succs(m) != 1) {
					/* must be the exit block */
870
871
872
					if (rexit == NULL) {
						rexit = m;
					} else if (rexit != m) {
873
						/* two exits */
874
						rexit = NULL;
875
876
877
878
879
880
						break;
					}
				} else {
					ir_region *succ = get_region_succ(m, 0);

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

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

/**
 * replace all pred edges from region pred that points to any of the set set
 * to ONE edge to reg.
 */
939
940
static void replace_pred(ir_region *succ, ir_region *reg)
{
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
	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
959
960
961
		} else {
			/* the current region can be entered by this node */
			pred->enter = 1;
962
963
964
965
966
967
968
969
970
		}
	}
	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.
 */
971
972
static void replace_succ(ir_region *pred, ir_region *reg)
{
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
	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
991
992
993
		} else {
			/* current region can be left by this node */
			succ->exit = 1;
994
995
996
997
998
999
1000
		}
	}
	ARR_SHRINKLEN(pred->succ, len);
}

/**
 * Reduce the graph by the node reg.
For faster browsing, not all history is shown. View entire blame