cdep.c 4.65 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
26
#include <assert.h>
#include <stdlib.h>
27
#include "irdom_t.h"
28
29
30
31
#include "irgraph.h"
#include "irgwalk.h"
#include "irnode.h"
#include "pmap.h"
Michael Beck's avatar
Michael Beck committed
32
#include "obst.h"
Michael Beck's avatar
Michael Beck committed
33
#include "xmalloc.h"
34
#include "cdep_t.h"
35
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
36
37
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
38
39
40
41
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;
42

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

45
46
47
48
49
50
51
52
53
54
ir_node *(get_cdep_node)(const ir_cdep *cdep)
{
	return _get_cdep_node(cdep);
}

ir_cdep *(get_cdep_next)(const ir_cdep *cdep)
{
	return _get_cdep_next(cdep);
}

55
56
ir_cdep *find_cdep(const ir_node *block)
{
57
	assert(is_Block(block));
58
	return pmap_get(ir_cdep, cdep_data->cdep_map, block);
59
60
}

61
62
void exchange_cdep(ir_node *old, const ir_node *nw)
{
63
	ir_cdep *cdep = find_cdep(nw);
64
	assert(is_Block(old));
Michael Beck's avatar
Michael Beck committed
65
	pmap_insert(cdep_data->cdep_map, old, cdep);
Christoph Mallon's avatar
Christoph Mallon committed
66
67
}

Michael Beck's avatar
Michael Beck committed
68
69
70
/**
 * Adds a control dependence from node to dep_on.
 */
71
72
static void add_cdep(ir_node *node, ir_node *dep_on)
{
73
	ir_cdep *dep = find_cdep(node);
74

75
	assert(is_Block(dep_on));
76
	if (dep == NULL) {
77
		ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
78
79
80

		newdep->node = dep_on;
		newdep->next = NULL;
Michael Beck's avatar
Michael Beck committed
81
		pmap_insert(cdep_data->cdep_map, node, newdep);
82
	} else {
83
		ir_cdep *newdep;
84
85

		for (;;) {
86
			if (get_cdep_node(dep) == dep_on) return;
87
88
89
			if (dep->next == NULL) break;
			dep = dep->next;
		}
90
		newdep = OALLOC(&cdep_data->obst, ir_cdep);
91
92
93
94
		newdep->node = dep_on;
		newdep->next = NULL;
		dep->next = newdep;
	}
95
96
}

97
98
99
/**
 * Pre-block-walker: calculate the control dependence
 */
100
101
static void cdep_pre(ir_node *node, void *ctx)
{
102
	ir_node *const end_block = (ir_node*)ctx;
Michael Beck's avatar
Michael Beck committed
103
	int i;
104

105
106
	/* Special case: The end block has no control dependency. */
	if (node == end_block) return;
107

Michael Beck's avatar
Michael Beck committed
108
	for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
109
110
111
112
113
114
115
116
117
118
119
120
		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);
		}
	}
121
122
123
}


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

131
132
133
	for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
		fprintf(
			F,
134
135
136
137
			"edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
			"linestyle:dashed color:gold}\n",
			get_irn_node_nr(block), get_irn_node_nr(cd->node)
		);
138
	}
139
140
141
142

	return 0;
}

143
144
void compute_cdep(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
145
	free_cdep(irg);
146
	cdep_data = XMALLOC(cdep_info);
Michael Beck's avatar
Michael Beck committed
147
148
149
	obstack_init(&cdep_data->obst);

	cdep_data->cdep_map = pmap_create();
150

151
	assure_postdoms(irg);
152

Michael Beck's avatar
Michael Beck committed
153
154
155
156
	/* 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.
	 */
157
158
159
160
	ir_node *const start_block = get_irg_start_block(irg);
	ir_node *const end_block   = get_irg_end_block(irg);
	ir_node *const rem         = get_Block_ipostdom(start_block);
	set_Block_ipostdom(start_block, end_block);
Michael Beck's avatar
Michael Beck committed
161

162
	irg_block_walk_graph(irg, cdep_pre, NULL, end_block);
163

Matthias Braun's avatar
Matthias Braun committed
164
	(void) cdep_edge_hook;
165

166
	/* restore the post dominator relation */
167
	set_Block_ipostdom(start_block, rem);
168
169
}

170
171
void free_cdep(ir_graph *irg)
{
Matthias Braun's avatar
Matthias Braun committed
172
	(void) irg;
Michael Beck's avatar
Michael Beck committed
173
174
175
176
177
178
	if (cdep_data != NULL) {
		pmap_destroy(cdep_data->cdep_map);
		obstack_free(&cdep_data->obst, NULL);
		xfree(cdep_data);
		cdep_data = NULL;
	}
179
180
}

181
182
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
{
183
	const ir_cdep *dep;
Christoph Mallon's avatar
Christoph Mallon committed
184
185

	for (dep = find_cdep(dependee); dep != NULL; dep = dep->next) {
186
		if (get_cdep_node(dep) == candidate) return 1;
Christoph Mallon's avatar
Christoph Mallon committed
187
188
189
190
	}
	return 0;
}

191
192
ir_node *get_unique_cdep(const ir_node *block)
{
193
	ir_cdep *cdep = find_cdep(block);
194

195
	return cdep != NULL && cdep->next == NULL ? get_cdep_node(cdep) : NULL;
196
197
}

198
199
int has_multiple_cdep(const ir_node *block)
{
200
	ir_cdep *cdep = find_cdep(block);
201
202
203

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