irdom.c 24.2 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
 *
 * 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.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
26
/**
 * @file
 * @brief     Construct and access dominator / post dominator tree.
 * @author    Goetz Lindenmaier, Michael Beck, Rubino Geiss
 * @date      2.2002
 * @version   $Id$
 */
Michael Beck's avatar
Michael Beck committed
27
28
#include "config.h"

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
31
32
#include "irouts.h"

Michael Beck's avatar
Michael Beck committed
33
#include "xmalloc.h"
34
#include "irgwalk.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
36
37
#include "irdom_t.h"
#include "irgraph_t.h"   /* To access state field. */
#include "irnode_t.h"
38
#include "ircons_t.h"
39
#include "array_t.h"
Christian Würdig's avatar
Christian Würdig committed
40
#include "iredges.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
41

Sebastian Hack's avatar
Sebastian Hack committed
42

43
44
#define get_dom_info(bl)  (&(bl)->attr.block.dom)
#define get_pdom_info(bl) (&(bl)->attr.block.pdom)
Sebastian Hack's avatar
Sebastian Hack committed
45

46
/*--------------------------------------------------------------------*/
47
/** Accessing the dominator and post dominator data structures       **/
48
/*--------------------------------------------------------------------*/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
49

Sebastian Hack's avatar
Sebastian Hack committed
50
ir_node *get_Block_idom(const ir_node *bl) {
51
52
53
54
55
56
	assert(is_Block(bl));
	if (get_Block_dom_depth(bl) == -1) {
		/* This block is not reachable from Start */
		return new_Bad();
	}
	return get_dom_info(bl)->idom;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
57
58
59
}

void set_Block_idom(ir_node *bl, ir_node *n) {
60
	ir_dom_info *bli = get_dom_info(bl);
Sebastian Hack's avatar
Sebastian Hack committed
61

62
	assert(is_Block(bl));
Sebastian Hack's avatar
Sebastian Hack committed
63
64
65
66
67
68
69
70
71

	/* Set the immediate dominator of bl to n */
	bli->idom = n;

	/*
	 * If we don't set the root of the dominator tree
	 * Append bl to the dominates queue of n.
	 */
	if(n != NULL) {
72
		ir_dom_info *ni = get_dom_info(n);
Sebastian Hack's avatar
Sebastian Hack committed
73
74
75
76

		bli->next = ni->first;
		ni->first = bl;
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
77
78
}

79
ir_node *get_Block_ipostdom(const ir_node *bl) {
80
81
82
83
84
85
	assert(is_Block(bl));
	if (get_Block_postdom_depth(bl) == -1) {
		/* This block is not reachable from Start */
		return new_Bad();
	}
	return get_pdom_info(bl)->idom;
86
87
88
}

void set_Block_ipostdom(ir_node *bl, ir_node *n) {
89
	ir_dom_info *bli = get_pdom_info(bl);
90

91
	assert(is_Block(bl));
92
93
94
95
96
97
98
99
100

	/* Set the immediate post dominator of bl to n */
	bli->idom = n;

	/*
	 * If we don't set the root of the post dominator tree
	 * Append bl to the post dominates queue of n.
	 */
	if(n != NULL) {
101
		ir_dom_info *ni = get_pdom_info(n);
102
103
104
105

		bli->next = ni->first;
		ni->first = bl;
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
106
107
}

108
int get_Block_dom_pre_num(const ir_node *bl) {
109
	assert(is_Block(bl));
110
	return get_dom_info(bl)->pre_num;
111
112
113
}

void set_Block_dom_pre_num(ir_node *bl, int num) {
114
	assert(is_Block(bl));
115
	get_dom_info(bl)->pre_num = num;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
116
117
}

Sebastian Hack's avatar
Sebastian Hack committed
118
int get_Block_dom_depth(const ir_node *bl) {
119
	assert(is_Block(bl));
120
	return get_dom_info(bl)->dom_depth;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
121
122
123
}

void set_Block_dom_depth(ir_node *bl, int depth) {
124
	assert(is_Block(bl));
125
	get_dom_info(bl)->dom_depth = depth;
126
127
128
129
}


int get_Block_postdom_pre_num(const ir_node *bl) {
130
	assert(is_Block(bl));
131
	return get_pdom_info(bl)->pre_num;
132
133
134
}

void set_Block_postdom_pre_num(ir_node *bl, int num) {
135
	assert(is_Block(bl));
136
	get_pdom_info(bl)->pre_num = num;
137
138
139
}

int get_Block_postdom_depth(const ir_node *bl) {
140
	assert(is_Block(bl));
141
	return get_pdom_info(bl)->dom_depth;
142
143
144
}

void set_Block_postdom_depth(ir_node *bl, int depth) {
145
	assert(is_Block(bl));
146
	get_pdom_info(bl)->dom_depth = depth;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
147
148
}

149
unsigned get_Block_dom_tree_pre_num(const ir_node *bl) {
Sebastian Hack's avatar
Sebastian Hack committed
150
151
152
153
	assert(is_Block(bl));
	return get_dom_info(bl)->tree_pre_num;
}

154
unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl) {
Sebastian Hack's avatar
Sebastian Hack committed
155
156
157
158
	assert(is_Block(bl));
	return get_dom_info(bl)->max_subtree_pre_num;
}

159
unsigned get_Block_pdom_tree_pre_num(const ir_node *bl) {
160
161
162
163
	assert(is_Block(bl));
	return get_pdom_info(bl)->tree_pre_num;
}

164
unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl) {
165
166
167
168
169
	assert(is_Block(bl));
	return get_pdom_info(bl)->max_subtree_pre_num;
}

/* Check, if a block dominates another block. */
170
int block_dominates(const ir_node *a, const ir_node *b) {
171
	const ir_dom_info *ai, *bi;
Sebastian Hack's avatar
Sebastian Hack committed
172

173
	if (is_Block(a) && is_Block(b)) {
Sebastian Hack's avatar
Sebastian Hack committed
174
175
176
177
178
179
180
		ai = get_dom_info(a);
		bi = get_dom_info(b);
		return bi->tree_pre_num - ai->tree_pre_num
			<= ai->max_subtree_pre_num - ai->tree_pre_num;
	}

	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
181
182
}

183
184
185
186
187
/* Check, if a block strictly dominates another block. */
int block_strictly_dominates(const ir_node *a, const ir_node *b) {
	return (a != b) && block_dominates(a, b);
}

Christian Würdig's avatar
Christian Würdig committed
188
/* Returns the smallest common dominator block of two nodes. */
189
ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b) {
Christian Würdig's avatar
Christian Würdig committed
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
	ir_node *bl_a   = is_Block(a) ? a : get_nodes_block(a);
	ir_node *bl_b   = is_Block(b) ? b : get_nodes_block(b);
	ir_node *dom_bl = NULL;

	/* Check if block of a dominates block of b */
	if (block_dominates(bl_a, bl_b))
		dom_bl = bl_a;
	/* Check if block of b dominates block of a */
	else if (block_dominates(bl_b, bl_a))
		dom_bl = bl_b;
	else {
		/* walk up dominator tree and search for first block dominating a and b */
		while (! dom_bl) {
			bl_a = get_Block_idom(bl_a);

			assert(! is_Bad(bl_a) && "block is dead?");

			if (block_dominates(bl_a, bl_b))
				dom_bl = bl_a;
		}
	}

	return dom_bl;
}

/* Returns the smallest common dominator block of all users of a node. */
216
ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi) {
Christian Würdig's avatar
Christian Würdig committed
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
	int n, j, i = 0, success;
	ir_node **user_blocks, *dom_bl;
	const ir_edge_t *edge;

	assert(! is_Block(irn) && "WRONG USAGE of node_users_smallest_common_dominator");
	assert(edges_activated(get_irn_irg(irn)) && "need edges activated");

	n = get_irn_n_edges(irn);

	/* get array to hold all block of the node users */
	NEW_ARR_A(ir_node *, user_blocks, n);
	foreach_out_edge(irn, edge) {
		ir_node *src = get_edge_src_irn(edge);

		if (is_Phi(src) && handle_phi) {
			/* get the corresponding cfg predecessor block if phi handling requested */
233
			j  = get_edge_src_pos(edge);
Christian Würdig's avatar
Christian Würdig committed
234
			assert(j >= 0 && "kaputt");
235
			user_blocks[i++] = get_Block_cfgpred_block(get_nodes_block(src), j);
Christian Würdig's avatar
Christian Würdig committed
236
237
238
239
240
		}
		else
			user_blocks[i++] = is_Block(src) ? src : get_nodes_block(src);
	}

241
242
	assert(i == n && "get_irn_n_edges probably broken");

Christian Würdig's avatar
Christian Würdig committed
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
	/* in case of only one user: return the block of the user */
	if (n == 1)
		return user_blocks[0];

	i = 0;
	/* search the smallest block dominating all user blocks */
	do {
		dom_bl  = node_smallest_common_dominator(user_blocks[i], user_blocks[i + 1]);
		success = 1;

		/* check if this block dominates all remaining blocks as well */
		for (j = i + 2; j < n; j++) {
			if (! block_dominates(dom_bl, user_blocks[j]))
				success = 0;
		}

		if (success)
			break;

		/* inherit the dominator block of the first (i + 1) users */
		user_blocks[++i] = dom_bl;
	} while (i < n - 1);

	assert(success && "no block found dominating all users");

	return dom_bl;
}


272
/* Get the first node in the list of nodes dominated by a given block. */
273
ir_node *get_Block_dominated_first(const ir_node *bl) {
Sebastian Hack's avatar
Sebastian Hack committed
274
275
276
277
	assert(is_Block(bl));
	return get_dom_info(bl)->first;
}

278
279
/* Get the next node in a list of nodes which are dominated by some
 * other node. */
280
ir_node *get_Block_dominated_next(const ir_node *bl) {
Sebastian Hack's avatar
Sebastian Hack committed
281
282
283
284
	assert(is_Block(bl));
	return get_dom_info(bl)->next;
}

285
/* Check, if a block post dominates another block. */
286
int block_postdominates(const ir_node *a, const ir_node *b) {
287
	const ir_dom_info *ai, *bi;
288
289
290
291
292
293
294
295
296
297
298

	if (is_Block(a) && is_Block(b)) {
		ai = get_pdom_info(a);
		bi = get_pdom_info(b);
		return bi->tree_pre_num - ai->tree_pre_num
			<= ai->max_subtree_pre_num - ai->tree_pre_num;
	}

	return 0;
}

299
300
301
302
303
304
/* Check, if a block strictly dominates another block. */
int block_strictly_postdominates(const ir_node *a, const ir_node *b) {
	return (a != b) && block_postdominates(a, b);
}


305
/* Get the first node in the list of nodes post dominated by a given block. */
306
ir_node *get_Block_postdominated_first(const ir_node *bl) {
307
308
309
310
311
312
	assert(is_Block(bl));
	return get_pdom_info(bl)->first;
}

/* Get the next node in a list of nodes which are post dominated by some
 * other node. */
313
ir_node *get_Block_postdominated_next(const ir_node *bl) {
314
315
316
317
318
	assert(is_Block(bl));
	return get_pdom_info(bl)->next;
}

/* Visit all nodes in the dominator subtree of a given node. */
Sebastian Hack's avatar
Sebastian Hack committed
319
void dom_tree_walk(ir_node *bl, irg_walk_func *pre,
Sebastian Hack's avatar
Sebastian Hack committed
320
321
322
323
		irg_walk_func *post, void *env)
{
	ir_node *p;

Sebastian Hack's avatar
Sebastian Hack committed
324
325
	if(pre)
		pre(bl, env);
Sebastian Hack's avatar
Sebastian Hack committed
326

Sebastian Hack's avatar
Sebastian Hack committed
327
	dominates_for_each(bl, p) {
Sebastian Hack's avatar
Sebastian Hack committed
328
329
		dom_tree_walk(p, pre, post, env);
	}
Sebastian Hack's avatar
Sebastian Hack committed
330
331
332

	if(post)
		post(bl, env);
Sebastian Hack's avatar
Sebastian Hack committed
333
334
}

335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
/* Visit all nodes in the post dominator subtree of a given node. */
void postdom_tree_walk(ir_node *bl, irg_walk_func *pre,
		irg_walk_func *post, void *env)
{
	ir_node *p;

	if(pre)
		pre(bl, env);

	postdominates_for_each(bl, p) {
		postdom_tree_walk(p, pre, post, env);
	}

	if(post)
		post(bl, env);
}

/* Walk over the dominator tree of an irg starting at the root. */
Sebastian Hack's avatar
Sebastian Hack committed
353
354
355
void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
		irg_walk_func *post, void *env)
{
356
	/* The root of the dominator tree should be the Start block. */
Sebastian Hack's avatar
Sebastian Hack committed
357
358
359
360
361
362
363
364
365
366
	ir_node *root = get_irg_start_block(irg);

  assert(irg->dom_state == dom_consistent
			&& "The dominators of the irg must be consistent");
	assert(root && "The start block of the graph is NULL?");
	assert(get_dom_info(root)->idom == NULL
			&& "The start node in the graph must be the root of the dominator tree");
	dom_tree_walk(root, pre, post, env);
}

367
368
369
370
371
372
373
/* Walk over the post dominator tree of an irg starting at the root. */
void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
		irg_walk_func *post, void *env)
{
	/* The root of the dominator tree should be the End block. */
	ir_node *root = get_irg_end_block(irg);

374
	assert(irg->pdom_state == dom_consistent
375
376
377
378
379
380
381
382
383
			&& "The dominators of the irg must be consistent");
	assert(root && "The end block of the graph is NULL?");
	assert(get_pdom_info(root)->idom == NULL
			&& "The End block node in the graph must be the root of the post dominator tree");
	postdom_tree_walk(root, pre, post, env);
}


static void assign_tree_dom_pre_order(ir_node *bl, void *data)
Sebastian Hack's avatar
Sebastian Hack committed
384
385
{
	unsigned *num = data;
386
	ir_dom_info *bi = get_dom_info(bl);
387

Sebastian Hack's avatar
Sebastian Hack committed
388
389
	bi->tree_pre_num = (*num)++;
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
390

391
static void assign_tree_dom_pre_order_max(ir_node *bl, void *data)
Sebastian Hack's avatar
Sebastian Hack committed
392
{
393
	ir_dom_info *bi = get_dom_info(bl);
Sebastian Hack's avatar
Sebastian Hack committed
394
395
	ir_node *p;
	unsigned max = 0;
396
	unsigned children = 0;
Matthias Braun's avatar
Matthias Braun committed
397
	(void) data;
Sebastian Hack's avatar
Sebastian Hack committed
398
399
400
401

	for(p = bi->first; p; p = get_dom_info(p)->next) {
		unsigned max_p = get_dom_info(p)->max_subtree_pre_num;
		max = max > max_p ? max : max_p;
402
		children++;
Sebastian Hack's avatar
Sebastian Hack committed
403
404
	}

405
406
	bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
	assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
Sebastian Hack's avatar
Sebastian Hack committed
407
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
408

409
410
411
static void assign_tree_postdom_pre_order(ir_node *bl, void *data)
{
	unsigned *num = data;
412
	ir_dom_info *bi = get_pdom_info(bl);
413
414
415
416
417
418

	bi->tree_pre_num = (*num)++;
}

static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data)
{
419
	ir_dom_info *bi = get_pdom_info(bl);
420
421
422
	ir_node *p;
	unsigned max = 0;
	unsigned children = 0;
Matthias Braun's avatar
Matthias Braun committed
423
	(void) data;
424
425
426
427
428
429
430
431
432
433
434

	for(p = bi->first; p; p = get_pdom_info(p)->next) {
		unsigned max_p = get_pdom_info(p)->max_subtree_pre_num;
		max = max > max_p ? max : max_p;
		children++;
	}

	bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
	assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
}

435
/*--------------------------------------------------------------------*/
Michael Beck's avatar
Michael Beck committed
436
/*  Building and Removing the dominator data structure                */
437
/*--------------------------------------------------------------------*/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
438

439
440
441
442
/**
 * count the number of blocks and clears the post dominance info
 */
static void count_and_init_blocks_pdom(ir_node *bl, void *env) {
443
444
445
446
447
448
449
	int *n_blocks = (int *) env;
	(*n_blocks) ++;

	memset(get_pdom_info(bl), 0, sizeof(ir_dom_info));
	set_Block_ipostdom(bl, NULL);
	set_Block_postdom_pre_num(bl, -1);
	set_Block_postdom_depth(bl, -1);
450
451
452
}

/** temporary type used while constructing the dominator / post dominator tree. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
453
typedef struct tmp_dom_info {
454
455
456
457
458
459
460
461
462
463
464
465
466
467
	ir_node *block;               /**< backlink */

	struct tmp_dom_info *semi;    /**< semidominator */
	struct tmp_dom_info *parent;
	struct tmp_dom_info *label;   /**< used for LINK and EVAL */
	struct tmp_dom_info *ancestor;/**< used for LINK and EVAL */
	struct tmp_dom_info *dom;     /**< After step 3, if the semidominator of w is
	                                   its immediate dominator, then w->dom is the
	                                   immediate dominator of w.  Otherwise w->dom
	                                   is a vertex v whose number is smaller than
	                                   w and whose immediate dominator is also w's
	                                   immediate dominator. After step 4, w->dom
	                                   is the immediate dominator of w.  */
	struct tmp_dom_info *bucket;  /**< set of vertices with same semidominator */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
468
469
} tmp_dom_info;

470
/** Struct to pass info through walker. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
471
typedef struct {
472
473
	tmp_dom_info *d;
	int used;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
474
475
} dom_env;

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

477
/**
Michael Beck's avatar
Michael Beck committed
478
 * Walks Blocks along the out data structure.  If recursion started with
479
480
 * Start block misses control dead blocks.
 */
481
static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
482
                              tmp_dom_info *tdi_list, int *used, int n_blocks) {
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
	tmp_dom_info *tdi;
	int i;

	assert(is_Block(bl));
	if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
	  return;
	mark_Block_block_visited(bl);
	set_Block_dom_pre_num(bl, *used);

	assert(*used < n_blocks);
	tdi = &tdi_list[*used];
	++(*used);

	tdi->semi     = tdi;
	tdi->label    = tdi;
	tdi->ancestor = NULL;
	tdi->bucket   = NULL;
	tdi->parent   = parent;
	tdi->block    = bl;

	/* Iterate */
	for (i = get_Block_n_cfg_outs_ka(bl) - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfg_out_ka(bl, i);
506
507
508
509
510
		/* can happen for half-optimized dead code (I've seen this in student
		   projects */
		if (!is_Block(pred))
			continue;

511
512
		init_tmp_dom_info(pred, tdi, tdi_list, used, n_blocks);
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
513
514
}

515
516
517
518
519
/**
 * Walks Blocks along the control flow.  If recursion started with
 * End block misses blocks in endless loops.
 */
static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent,
520
                               tmp_dom_info *tdi_list, int* used, int n_blocks) {
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
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
	tmp_dom_info *tdi;
	int i;

	assert(is_Block(bl));
	if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
	  return;
	mark_Block_block_visited(bl);
	set_Block_postdom_pre_num(bl, *used);

	assert(*used < n_blocks);
	tdi = &tdi_list[*used];
	++(*used);

	tdi->semi = tdi;
	tdi->label = tdi;
	tdi->ancestor = NULL;
	tdi->bucket = NULL;
	tdi->parent = parent;
	tdi->block = bl;

	/* Iterate */
	for (i = get_Block_n_cfgpreds(bl) - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfgpred_block(bl, i);
		if (is_Bad(pred))
			continue;
		assert(is_Block(pred));
		init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
	}

	/* Handle keep-alives. Note that the preprocessing
	   in init_construction() had already killed all
	   phantom keep-alive edges. All remaining block keep-alives
	   are really edges to endless loops.
	 */
	if (bl == get_irg_end_block(current_ir_graph)) {
		ir_node *end = get_irg_end(current_ir_graph);

		for (i = get_irn_arity(end) - 1; i >= 0; --i) {
			ir_node *pred = get_irn_n(end, i);

			if (is_Block(pred))
				init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
		}
	}
}

static void dom_compress(tmp_dom_info *v) {
	assert (v->ancestor);
	if (v->ancestor->ancestor) {
		dom_compress (v->ancestor);
		if (v->ancestor->label->semi < v->label->semi) {
			v->label = v->ancestor->label;
		}
		v->ancestor = v->ancestor->ancestor;
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
576
577
}

578
579
580
581
/**
 * if V is a root, return v, else return the vertex u, not being the
 * root, with minimum u->semi on the path from v to its root.
 */
582
inline static tmp_dom_info *dom_eval(tmp_dom_info *v) {
583
584
585
	if (!v->ancestor) return v;
	dom_compress (v);
	return v->label;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
586
587
}

588
/** make V W's ancestor */
589
inline static void dom_link(tmp_dom_info *v, tmp_dom_info *w) {
590
	w->ancestor = v;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
591
592
}

593
594
595
596
/**
 * Walker: count the number of blocks and clears the dominance info
 */
static void count_and_init_blocks_dom(ir_node *bl, void *env) {
597
598
599
600
601
602
603
	int *n_blocks = (int *) env;
	(*n_blocks) ++;

	memset(get_dom_info(bl), 0, sizeof(ir_dom_info));
	set_Block_idom(bl, NULL);
	set_Block_dom_pre_num(bl, -1);
	set_Block_dom_depth(bl, -1);
604
605
606
607
608
609
610
}

/**
 * Initialize the dominance/postdominance construction:
 *
 * - count the number of blocks
 * - clear the dominance info
611
612
 * - remove Block-keepalives of live blocks to reduce
 *   the number of "phantom" block edges
613
614
615
616
617
 *
 * @param irg  the graph
 * @param pre  a walker function that will be called for every block in the graph
 */
static int init_construction(ir_graph *irg, irg_walk_func *pre) {
618
619
620
	ir_graph *rem = current_ir_graph;
	ir_node *end;
	int arity;
621
622
	int n_blocks = 0;

623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
	current_ir_graph = irg;

	/* this visits only the reachable blocks */
	irg_block_walk(get_irg_end_block(irg), pre, NULL, &n_blocks);

	/* now visit the unreachable (from End) Blocks and remove unnecessary keep-alives */
	end   = get_irg_end(irg);
	arity = get_End_n_keepalives(end);
	if (arity) {    /* we have keep-alives */
		ir_node **in;
		int i, j;

		NEW_ARR_A(ir_node *, in, arity);
		for (i = j = 0; i < arity; i++) {
			ir_node *pred = get_End_keepalive(end, i);

639
640
641
642
			if (!is_Block(pred)) {
				pred = get_nodes_block(pred);
				if (!is_Block(pred)) {
					/* a node which has a bad block input: kill it */
643
					continue;
644
				}
645
			}
646
647
			dec_irg_block_visited(irg);
			irg_block_walk(pred, pre, NULL, &n_blocks);
648
649
650
			in[j++] = pred;
		}
		if (j != arity) {
651
			/* we kill some keep-alives */
652
653
654
655
656
657
			set_End_keepalives(end, j, in);
			set_irg_outs_inconsistent(irg);
		}
	}

	current_ir_graph = rem;
658
	return n_blocks;
659
660
661
}


Götz Lindenmaier's avatar
Götz Lindenmaier committed
662
663
664
665
/* Computes the dominator trees.  Sets a flag in irg to "dom_consistent".
   If the control flow of the graph is changed this flag must be set to
   "dom_inconsistent".  */
void compute_doms(ir_graph *irg) {
666
667
668
669
670
671
672
673
674
675
676
677
678
679
	ir_graph *rem = current_ir_graph;
	int n_blocks, used, i, j;
	tmp_dom_info *tdi_list;   /* Ein Golf? */

	current_ir_graph = irg;

	/* Update graph state */
	assert(get_irg_phase_state(irg) != phase_building);
	irg->dom_state = dom_consistent;

	/* Count the number of blocks in the graph. */
	n_blocks = init_construction(irg, count_and_init_blocks_dom);

	/* Memory for temporary information. */
680
	tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784

	/* We need the out data structure. */
	assure_irg_outs(irg);

	/* this with a standard walker as passing the parent to the sons isn't
	   simple. */
	used = 0;
	inc_irg_block_visited(irg);
	init_tmp_dom_info(get_irg_start_block(irg), NULL, tdi_list, &used, n_blocks);
	/* If not all blocks are reachable from Start by out edges this assertion
	   fails.
	   assert(used == n_blocks && "Precondition for dom construction violated"); */
	assert(used <= n_blocks && "Precondition for dom construction violated");
	n_blocks = used;


	for (i = n_blocks-1; i > 0; i--) {  /* Don't iterate the root, it's done. */
		int irn_arity;
		tmp_dom_info *w = &tdi_list[i];
		tmp_dom_info *v;

		/* Step 2 */
		irn_arity = get_irn_arity(w->block);
		for (j = 0; j < irn_arity;  j++) {
			ir_node *pred = get_Block_cfgpred_block(w->block, j);
			tmp_dom_info *u;

			if (is_Bad(pred) || (get_Block_dom_pre_num (pred) == -1))
				continue;	/* control-dead */

			u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
			if (u->semi < w->semi) w->semi = u->semi;
		}

		/* handle keep-alives if we are at the end block */
		if (w->block == get_irg_end_block(irg)) {
			ir_node *end = get_irg_end(irg);

			irn_arity = get_irn_arity(end);
			for (j = 0; j < irn_arity;  j++) {
				ir_node *pred = get_irn_n(end, j);
				tmp_dom_info *u;

				if (is_no_Block(pred) || get_Block_dom_pre_num(pred) == -1)
					continue;	/* control-dead */

				u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
				if (u->semi < w->semi) w->semi = u->semi;
			}
		}

		/* Add w to w->semi's bucket.  w is in exactly one bucket, so
		   buckets can been implemented as linked lists. */
		w->bucket = w->semi->bucket;
		w->semi->bucket = w;

		dom_link (w->parent, w);

		/* Step 3 */
		while (w->parent->bucket) {
			tmp_dom_info *u;
			v = w->parent->bucket;
			/* remove v from w->parent->bucket */
			w->parent->bucket = v->bucket;
			v->bucket = NULL;

			u = dom_eval (v);
			if (u->semi < v->semi)
				v->dom = u;
			else
				v->dom = w->parent;
		}
	}
	/* Step 4 */
	tdi_list[0].dom = NULL;
	set_Block_idom(tdi_list[0].block, NULL);
	set_Block_dom_depth(tdi_list[0].block, 1);
	for (i = 1; i < n_blocks;  i++) {
		tmp_dom_info *w = &tdi_list[i];
		int depth;

		if (! w->dom)
			continue; /* control dead */

		if (w->dom != w->semi) w->dom = w->dom->dom;
		set_Block_idom(w->block, w->dom->block);

		/* blocks dominated by dead one's are still dead */
		depth = get_Block_dom_depth(w->dom->block);
		if (depth > 0)
			++depth;
		set_Block_dom_depth(w->block, depth);
	}

	/* clean up */
	free(tdi_list);

	/* Do a walk over the tree and assign the tree pre orders. */
	{
		unsigned tree_pre_order = 0;
		dom_tree_walk_irg(irg, assign_tree_dom_pre_order,
			assign_tree_dom_pre_order_max, &tree_pre_order);
	}
	current_ir_graph = rem;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
785
786
}

787
void assure_doms(ir_graph *irg) {
788
789
	if (get_irg_dom_state(irg) != dom_consistent)
		compute_doms(irg);
790
791
}

792
void free_dom(ir_graph *irg) {
793
	/* Update graph state */
Matthias Braun's avatar
Matthias Braun committed
794
795
	assert(get_irg_phase_state(irg) != phase_building);
	irg->dom_state = dom_none;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
796

797
798
	/* With the implementation right now there is nothing to free,
	   but better call it anyways... */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
799
}
800
801
802
803
804

/* Computes the post dominator trees.  Sets a flag in irg to "dom_consistent".
   If the control flow of the graph is changed this flag must be set to
   "dom_inconsistent".  */
void compute_postdoms(ir_graph *irg) {
805
806
807
808
809
810
811
812
813
814
815
816
817
818
	ir_graph *rem = current_ir_graph;
	int n_blocks, used, i, j;
	tmp_dom_info *tdi_list;

	current_ir_graph = irg;

	/* Update graph state */
	assert(get_irg_phase_state(irg) != phase_building);
	irg->pdom_state = dom_consistent;

	/* Count the number of blocks in the graph. */
	n_blocks = init_construction(irg, count_and_init_blocks_pdom);

	/* Memory for temporary information. */
819
	tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895

	/* We need the out data structure. */
	assure_irg_outs(irg);

	/* this with a standard walker as passing the parent to the sons isn't
	   simple. */
	used = 0;
	inc_irg_block_visited(irg);
	init_tmp_pdom_info(get_irg_end_block(irg), NULL, tdi_list, &used, n_blocks);
	/* If not all blocks are reachable from End by cfg edges this assertion
	   fails.
	   assert(used == n_blocks && "Precondition for dom construction violated"); */
	n_blocks = used;


	for (i = n_blocks-1; i > 0; i--) {  /* Don't iterate the root, it's done. */
		int irn_arity;
		tmp_dom_info *w = &tdi_list[i];
		tmp_dom_info *v;

		/* Step 2 */
		irn_arity = get_Block_n_cfg_outs_ka(w->block);
		for (j = 0;  j < irn_arity;  j++) {
			ir_node *succ = get_Block_cfg_out_ka(w->block, j);
			tmp_dom_info *u;

			if (get_Block_postdom_pre_num (succ) == -1)
				continue;	/* endless-loop */

			u = dom_eval (&tdi_list[get_Block_postdom_pre_num(succ)]);
			if (u->semi < w->semi) w->semi = u->semi;
		}
		/* Add w to w->semi's bucket.  w is in exactly one bucket, so
		   buckets can be implemented as linked lists. */
		w->bucket = w->semi->bucket;
		w->semi->bucket = w;

		dom_link (w->parent, w);

		/* Step 3 */
		while (w->parent->bucket) {
			tmp_dom_info *u;
			v = w->parent->bucket;
			/* remove v from w->parent->bucket */
			w->parent->bucket = v->bucket;
			v->bucket = NULL;

			u = dom_eval(v);
			if (u->semi < v->semi)
				v->dom = u;
			else
				v->dom = w->parent;
		}
	}
	/* Step 4 */
	tdi_list[0].dom = NULL;
	set_Block_ipostdom(tdi_list[0].block, NULL);
	set_Block_postdom_depth(tdi_list[0].block, 1);
	for (i = 1;  i < n_blocks;  i++) {
		tmp_dom_info *w = &tdi_list[i];

		if (w->dom != w->semi) w->dom = w->dom->dom;
		set_Block_ipostdom(w->block, w->dom->block);
		set_Block_postdom_depth(w->block, get_Block_postdom_depth(w->dom->block) + 1);
	}

	/* clean up */
	free(tdi_list);

	/* Do a walk over the tree and assign the tree pre orders. */
	{
		unsigned tree_pre_order = 0;
		postdom_tree_walk_irg(irg, assign_tree_postdom_pre_order,
			assign_tree_postdom_pre_order_max, &tree_pre_order);
	}
	current_ir_graph = rem;
896
897
}

898
void assure_postdoms(ir_graph *irg) {
899
900
	if (get_irg_postdom_state(irg) != dom_consistent)
		compute_postdoms(irg);
901
902
}

903
void free_postdom(ir_graph *irg) {
904
	/* Update graph state */
Matthias Braun's avatar
Matthias Braun committed
905
906
	assert(get_irg_phase_state(irg) != phase_building);
	irg->pdom_state = dom_none;
907

908
909
	/* With the implementation right now there is nothing to free,
	   but better call it anyways... */
910
}