cdep.c 5.81 KB
Newer Older
Matthias Braun's avatar
Matthias Braun committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief   Implementation of cdep
Matthias Braun's avatar
Matthias Braun committed
23
 * @author  Christoph Mallon
Matthias Braun's avatar
Matthias Braun committed
24
25
 * @version $Id$
 */
26
27
28
29
30
31
32
#include <assert.h>
#include <stdlib.h>
#include "irdom.h"
#include "irgraph.h"
#include "irgwalk.h"
#include "irnode.h"
#include "pmap.h"
Michael Beck's avatar
Michael Beck committed
33
#include "obst.h"
Michael Beck's avatar
Michael Beck committed
34
#include "xmalloc.h"
35
36
#include "cdep.h"
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
37
38
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
39
40
41
42
typedef struct cdep_info {
	pmap   *cdep_map;     /**< A map to find the list of all control dependence nodes for a block. */
	struct obstack obst;  /**< An obstack where all cdep data lives on. */
} cdep_info;
43

Michael Beck's avatar
Michael Beck committed
44
static cdep_info *cdep_data;
45

Michael Beck's avatar
Michael Beck committed
46
47
48
/* Return a list of all control dependences of a block. */
ir_cdep *find_cdep(const ir_node *block) {
	return pmap_get(cdep_data->cdep_map, (void *)block);
49
50
}

Michael Beck's avatar
Michael Beck committed
51
52
/* Replace the control dependence info of old by the info of nw. */
void exchange_cdep(ir_node *old, const ir_node *nw) {
53
	ir_cdep *cdep = find_cdep(nw);
Michael Beck's avatar
Michael Beck committed
54
	pmap_insert(cdep_data->cdep_map, old, cdep);
Christoph Mallon's avatar
Christoph Mallon committed
55
56
}

Michael Beck's avatar
Michael Beck committed
57
58
59
60
/**
 * Adds a control dependence from node to dep_on.
 */
static void add_cdep(ir_node *node, ir_node *dep_on) {
61
	ir_cdep *dep = find_cdep(node);
62
63
64
65
#if 0
	ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
#endif

66
	if (dep == NULL) {
Michael Beck's avatar
Michael Beck committed
67
		ir_cdep *newdep = obstack_alloc(&cdep_data->obst, sizeof(*newdep));
68
69
70

		newdep->node = dep_on;
		newdep->next = NULL;
Michael Beck's avatar
Michael Beck committed
71
		pmap_insert(cdep_data->cdep_map, node, newdep);
72
	} else {
73
		ir_cdep *newdep;
74
75
76
77
78
79

		for (;;) {
			if (dep->node == dep_on) return;
			if (dep->next == NULL) break;
			dep = dep->next;
		}
Michael Beck's avatar
Michael Beck committed
80
		newdep = obstack_alloc(&cdep_data->obst, sizeof(*newdep));
81
82
83
84
		newdep->node = dep_on;
		newdep->next = NULL;
		dep->next = newdep;
	}
85
86
}

87
88
89
90
typedef struct cdep_env {
	ir_node *start_block;
	ir_node *end_block;
} cdep_env;
91

92
93
94
/**
 * Pre-block-walker: calculate the control dependence
 */
Michael Beck's avatar
Michael Beck committed
95
static void cdep_pre(ir_node *node, void *ctx) {
96
	cdep_env *env = ctx;
Matthias Braun's avatar
Matthias Braun committed
97
98
	unsigned int n;
	unsigned int i;
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

	/* special case:
	 * start and end block have no control dependency
	 */
	if (node == env->start_block) return;
	if (node == env->end_block) return;

	n = get_Block_n_cfgpreds(node);
	for (i = 0; i < n; i++) {
		ir_node *pred = get_Block_cfgpred_block(node, i);
		ir_node *pdom;
		ir_node *dependee;

		if (is_Bad(pred)) continue;

		pdom = get_Block_ipostdom(pred);
		for (dependee = node; dependee != pdom; dependee = get_Block_ipostdom(dependee)) {
			assert(!is_Bad(pdom));
			add_cdep(dependee, pred);
		}
	}
120
121
122
}


123
124
125
126
/**
 * A block edge hook: add all cdep edges of block.
 */
static int cdep_edge_hook(FILE *F, ir_node *block)
127
{
128
	ir_cdep *cd;
129
130

#if 0
131
	ir_node *pdom = get_Block_ipostdom(block);
132
133
134
135
136
137
138
139
140
	if (pdom != NULL) {
		fprintf(
			F,
			"edge:{sourcename:\"n%ld\" targetname:\"n%ld\" color:gold}\n",
			get_irn_node_nr(pdom), get_irn_node_nr(block)
		);
	}
#endif

141
142
143
	for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
		fprintf(
			F,
144
145
146
147
			"edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
			"linestyle:dashed color:gold}\n",
			get_irn_node_nr(block), get_irn_node_nr(cd->node)
		);
148
	}
149
150
151
152

	return 0;
}

Michael Beck's avatar
Michael Beck committed
153
154
/* Compute the control dependence graph for a graph. */
void compute_cdep(ir_graph *irg) {
155
156
157
	ir_node *start_block, *rem;
	cdep_env env;

Michael Beck's avatar
Michael Beck committed
158
	free_cdep(irg);
159
	cdep_data = XMALLOC(cdep_info);
Michael Beck's avatar
Michael Beck committed
160
161
162
	obstack_init(&cdep_data->obst);

	cdep_data->cdep_map = pmap_create();
163

164
	assure_postdoms(irg);
165

Michael Beck's avatar
Michael Beck committed
166
167
168
169
	/* we must temporary change the post dominator relation:
	   the ipdom of the startblock is the end block.
	   Firm does NOT add the phantom edge from Start to End.
	 */
170
171
172
	start_block = get_irg_start_block(irg);
	rem = get_Block_ipostdom(start_block);
	set_Block_ipostdom(start_block, get_irg_end_block(irg));
173

174
175
176
177
178
	env.start_block = get_irg_start_block(irg);
	env.end_block   = get_irg_end_block(irg);
	irg_block_walk_graph(irg, cdep_pre, NULL, &env);

#if 0
179
	set_dump_block_edge_hook(cdep_edge_hook);
180
	dump_ir_block_graph(irg, "_cdep");
181
	set_dump_block_edge_hook(NULL);
Matthias Braun's avatar
Matthias Braun committed
182
183
#else
	(void) cdep_edge_hook;
184
185
#endif

186
187
	/* restore the post dominator relation */
	set_Block_ipostdom(start_block, rem);
188
189
}

Michael Beck's avatar
Michael Beck committed
190
191
/* Free the control dependence info. */
void free_cdep(ir_graph *irg) {
Matthias Braun's avatar
Matthias Braun committed
192
	(void) irg;
Michael Beck's avatar
Michael Beck committed
193
194
195
196
197
198
	if (cdep_data != NULL) {
		pmap_destroy(cdep_data->cdep_map);
		obstack_free(&cdep_data->obst, NULL);
		xfree(cdep_data);
		cdep_data = NULL;
	}
199
200
}

Michael Beck's avatar
Michael Beck committed
201
202
/* Check whether dependee is (directly) control dependent on candidate. */
int is_cdep_on(const ir_node *dependee, const ir_node *candidate) {
203
	const ir_cdep *dep;
Christoph Mallon's avatar
Christoph Mallon committed
204
205
206
207
208
209
210

	for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
		if (dep->node == candidate) return 1;
	}
	return 0;
}

Michael Beck's avatar
Michael Beck committed
211
212
/* Check whether dependee is (possible iterated) control dependent on candidate. */
int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate) {
213
	const ir_cdep *dep;
214
215
216
217
218
219
220
221
222

	while ((dep = find_cdep(dependee)) != NULL) {
		if (dep->next != NULL) return 0;
		if (dep->node == candidate) return 1;
		dependee = dep->node;
	}
	return 0;
}

Michael Beck's avatar
Michael Beck committed
223
224
/* If block is control dependent on exactly one node, return this node, else NULL. */
ir_node *get_unique_cdep(const ir_node *block) {
225
	ir_cdep *cdep = find_cdep(block);
226
227
228
229

	return cdep != NULL && cdep->next == NULL ? cdep->node : NULL;
}

Michael Beck's avatar
Michael Beck committed
230
231
/* Check if the given block is control dependent of more than one node. */
int has_multiple_cdep(const ir_node *block) {
232
	ir_cdep *cdep = find_cdep(block);
233
234
235

	return cdep != NULL && cdep->next != NULL;
}