cdep.c 3.81 KB
Newer Older
1
2
3
4
5
6
7
#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
8
#include "xmalloc.h"
9
10
11
12
13
#include "cdep.h"
#include "irprintf.h"

typedef unsigned int uint;

14
static pmap *cdep_map;
15

16
cdep *find_cdep(const ir_node *block)
17
{
18
	return pmap_get(cdep_map, (void *)block);
19
20
21
}


22
void exchange_cdep(ir_node *old, const ir_node *nw)
Christoph Mallon's avatar
Christoph Mallon committed
23
{
24
	cdep *cdep = find_cdep(nw);
Christoph Mallon's avatar
Christoph Mallon committed
25
26
27
28
29

	pmap_insert(cdep_map, old, cdep);
}


30
31
static void add_cdep(ir_node* node, ir_node* dep_on)
{
32
	cdep *dep = find_cdep(node);
33
34
35
36
#if 0
	ir_fprintf(stderr, "Adding cdep of %+F on %+F\n", node, dep_on);
#endif

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
	if (dep == NULL) {
		cdep *newdep = xmalloc(sizeof(*newdep));

		newdep->node = dep_on;
		newdep->next = NULL;
		pmap_insert(cdep_map, node, newdep);
	} else {
		cdep *newdep;

		for (;;) {
			if (dep->node == dep_on) return;
			if (dep->next == NULL) break;
			dep = dep->next;
		}
		newdep = xmalloc(sizeof(*newdep));
		newdep->node = dep_on;
		newdep->next = NULL;
		dep->next = newdep;
	}
56
57
}

58
59
60
61
typedef struct cdep_env {
	ir_node *start_block;
	ir_node *end_block;
} cdep_env;
62

63
64
65
66
/**
 * Pre-block-walker: calculate the control dependence
 */
static void cdep_pre(ir_node *node, void *ctx)
67
{
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
	cdep_env *env = ctx;
	uint n;
	uint i;

	/* 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);
		}
	}
92
93
94
95
96
}


#include "irdump.h"

97
98
99
100
/**
 * A block edge hook: add all cdep edges of block.
 */
static int cdep_edge_hook(FILE *F, ir_node *block)
101
{
102
	cdep *cd;
103
104

#if 0
105
	ir_node *pdom = get_Block_ipostdom(block);
106
107
108
109
110
111
112
113
114
	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

115
116
117
	for (cd = find_cdep(block); cd != NULL; cd = cd->next) {
		fprintf(
			F,
118
119
120
121
			"edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
			"linestyle:dashed color:gold}\n",
			get_irn_node_nr(block), get_irn_node_nr(cd->node)
		);
122
	}
123
124
125
126
127

	return 0;
}


128
void compute_cdep(ir_graph *irg)
129
{
130
131
132
133
	ir_node *start_block, *rem;
	cdep_env env;

	cdep_map = pmap_create();
134

135
	assure_postdoms(irg);
136

137
138
139
140
	/* we must temporary change the post dominator relation */
	start_block = get_irg_start_block(irg);
	rem = get_Block_ipostdom(start_block);
	set_Block_ipostdom(start_block, get_irg_end_block(irg));
141

142
143
144
145
146
	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
147
	set_dump_block_edge_hook(cdep_edge_hook);
148
	dump_ir_block_graph(irg, "_cdep");
149
150
151
	set_dump_block_edge_hook(NULL);
#endif

152
153
	/* restore the post dominator relation */
	set_Block_ipostdom(start_block, rem);
154
155
156
}


157
void free_cdep(ir_graph *irg)
158
{
159
	// TODO atm leaking more memory than a small memory leaking animal
160
161
162
}


163
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
Christoph Mallon's avatar
Christoph Mallon committed
164
{
165
	const cdep *dep;
Christoph Mallon's avatar
Christoph Mallon committed
166
167
168
169
170
171
172
173

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


174
int is_iterated_cdep_on(ir_node *dependee, ir_node *candidate)
175
{
176
	const cdep *dep;
177
178
179
180
181
182
183
184
185
186

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


187
ir_node *get_unique_cdep(const ir_node *block)
188
{
189
	cdep *cdep = find_cdep(block);
190
191
192
193
194

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


195
int has_multiple_cdep(const ir_node *block)
196
{
197
	cdep *cdep = find_cdep(block);
198
199
200

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