heights.c 6.61 KB
Newer Older
Christian Würdig's avatar
Christian Würdig 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.
Christian Würdig's avatar
Christian Würdig committed
18
 */
Sebastian Hack's avatar
Sebastian Hack committed
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
26
/**
 * @file
 * @brief    Compute heights of nodes inside basic blocks
 * @author   Sebastian Hack
 * @date     19.04.2006
 * @version  $Id$
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
28

29
#include "heights.h"
30

Sebastian Hack's avatar
Sebastian Hack committed
31
32
#include <stdlib.h>
#include <stdio.h>
33
#include <stdbool.h>
Sebastian Hack's avatar
Sebastian Hack committed
34
35
36

#include "irdump.h"
#include "irgwalk.h"
37
#include "irnodemap.h"
Sebastian Hack's avatar
Sebastian Hack committed
38
#include "iredges_t.h"
39
40
#include "list.h"
#include "util.h"
Sebastian Hack's avatar
Sebastian Hack committed
41

42
struct ir_heights_t {
43
44
45
46
	ir_nodemap      data;
	unsigned        visited;
	void           *dump_handle;
	struct obstack  obst;
Sebastian Hack's avatar
Sebastian Hack committed
47
48
49
50
51
52
53
};

typedef struct {
	unsigned height;
	unsigned visited;
} irn_height_t;

54
55
static irn_height_t *maybe_get_height_data(const ir_heights_t *heights,
                                           const ir_node *node)
Sebastian Hack's avatar
Sebastian Hack committed
56
{
57
58
	irn_height_t *height = (irn_height_t*)ir_nodemap_get(&heights->data, node);
	return height;
59
60
}

61
static irn_height_t *get_height_data(ir_heights_t *heights, const ir_node *node)
62
{
63
64
	irn_height_t *height = (irn_height_t*)ir_nodemap_get(&heights->data, node);
	if (height == NULL) {
65
		height = OALLOCZ(&heights->obst, irn_height_t);
66
67
68
		ir_nodemap_insert(&heights->data, node, height);
	}
	return height;
Sebastian Hack's avatar
Sebastian Hack committed
69
70
71
72
}

static void height_dump_cb(void *data, FILE *f, const ir_node *irn)
{
73
74
75
	const ir_heights_t *heights = (const ir_heights_t*) data;
	const irn_height_t *h       = maybe_get_height_data(heights, irn);
	if (h != NULL)
Sebastian Hack's avatar
Sebastian Hack committed
76
77
78
79
80
81
82
83
84
85
		fprintf(f, "height: %u\n", h->height);
}

/**
 * Check, if we can reach a target node from a given node inside one basic block.
 * @param h    The heights object.
 * @param curr The current node from which we tried to reach the other one.
 * @param tgt  The node we try to reach.
 * @return     1, one of tgt can be reached from curr, 0 else.
 */
86
static bool search(ir_heights_t *h, const ir_node *curr, const ir_node *tgt)
Sebastian Hack's avatar
Sebastian Hack committed
87
88
89
90
91
92
{
	irn_height_t *h_curr;
	irn_height_t *h_tgt;
	int i, n;

	/* if the current node is the one we were looking for, we're done. */
93
	if (curr == tgt)
94
		return true;
Sebastian Hack's avatar
Sebastian Hack committed
95

96
	/* If we are in another block or at a phi we won't find our target. */
97
	if (get_nodes_block(curr) != get_nodes_block(tgt))
98
		return false;
99
	if (is_Phi(curr))
100
		return false;
Sebastian Hack's avatar
Sebastian Hack committed
101
102

	/* Check, if we have already been here. Coming more often won't help :-) */
103
	h_curr = maybe_get_height_data(h, curr);
104
	if (h_curr->visited >= h->visited)
105
		return false;
Sebastian Hack's avatar
Sebastian Hack committed
106
107

	/* If we are too deep into the DAG we won't find the target either. */
108
	h_tgt = maybe_get_height_data(h, tgt);
109
	if (h_curr->height > h_tgt->height)
110
		return false;
Sebastian Hack's avatar
Sebastian Hack committed
111
112
113
114
115

	/* Mark this place as visited. */
	h_curr->visited = h->visited;

	/* Start a search from this node. */
116
	for (i = 0, n = get_irn_ins_or_deps(curr); i < n; ++i) {
117
		ir_node *op = get_irn_in_or_dep(curr, i);
118
		if (search(h, op, tgt))
119
			return true;
Sebastian Hack's avatar
Sebastian Hack committed
120
121
	}

122
	return false;
Sebastian Hack's avatar
Sebastian Hack committed
123
124
125
}

/**
126
127
 * Check, if one node can be reached from another one, according to data
 * dependence.
Sebastian Hack's avatar
Sebastian Hack committed
128
 */
129
int heights_reachable_in_block(ir_heights_t *h, const ir_node *n,
130
                               const ir_node *m)
Sebastian Hack's avatar
Sebastian Hack committed
131
132
{
	int res          = 0;
133
134
	irn_height_t *hn = maybe_get_height_data(h, n);
	irn_height_t *hm = maybe_get_height_data(h, m);
Sebastian Hack's avatar
Sebastian Hack committed
135
136
137
138

	assert(get_nodes_block(n) == get_nodes_block(m));
	assert(hn != NULL && hm != NULL);

139
	if (hn->height <= hm->height) {
Sebastian Hack's avatar
Sebastian Hack committed
140
141
142
143
144
145
146
147
148
149
150
151
152
		h->visited++;
		res = search(h, n, m);
	}

	return res;
}

/**
 * Compute the height of a node in a block.
 * @param h   The heights object.
 * @param irn The node.
 * @param bl  The block.
 */
153
static unsigned compute_height(ir_heights_t *h, ir_node *irn, const ir_node *bl)
Sebastian Hack's avatar
Sebastian Hack committed
154
{
155
	irn_height_t *ih = get_height_data(h, irn);
Sebastian Hack's avatar
Sebastian Hack committed
156
157
158
159

	const ir_edge_t *edge;

	/* bail out if we already visited that node. */
160
	if (ih->visited >= h->visited)
Sebastian Hack's avatar
Sebastian Hack committed
161
162
163
164
165
166
167
168
		return ih->height;

	ih->visited = h->visited;
	ih->height  = 0;

	foreach_out_edge(irn, edge) {
		ir_node *dep = get_edge_src_irn(edge);

169
		if (!is_Block(dep) && !is_Phi(dep) && get_nodes_block(dep) == bl) {
Sebastian Hack's avatar
Sebastian Hack committed
170
171
172
173
174
175
176
			unsigned dep_height = compute_height(h, dep, bl);
			ih->height          = MAX(ih->height, dep_height);
		}

		ih->height++;
	}

177
178
179
	foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
		ir_node *dep = get_edge_src_irn(edge);

180
		assert(!is_Phi(dep));
181
		if (!is_Block(dep) && get_nodes_block(dep) == bl) {
182
183
184
185
186
187
188
			unsigned dep_height = compute_height(h, dep, bl);
			ih->height          = MAX(ih->height, dep_height);
		}

		ih->height++;
	}

Sebastian Hack's avatar
Sebastian Hack committed
189
190
191
	return ih->height;
}

192
static unsigned compute_heights_in_block(ir_node *bl, ir_heights_t *h)
Sebastian Hack's avatar
Sebastian Hack committed
193
{
Christian Würdig's avatar
Christian Würdig committed
194
	int             max_height = -1;
Sebastian Hack's avatar
Sebastian Hack committed
195
196
197
198
199
200
	const ir_edge_t *edge;

	h->visited++;

	foreach_out_edge(bl, edge) {
		ir_node *dep = get_edge_src_irn(edge);
Christian Würdig's avatar
Christian Würdig committed
201
202
203
		int     curh = compute_height(h, dep, bl);

		max_height = MAX(curh, max_height);
Sebastian Hack's avatar
Sebastian Hack committed
204
	}
205
206
207

	foreach_out_edge_kind(bl, edge, EDGE_KIND_DEP) {
		ir_node *dep = get_edge_src_irn(edge);
Christian Würdig's avatar
Christian Würdig committed
208
209
210
		int     curh = compute_height(h, dep, bl);

		max_height = MAX(curh, max_height);
211
	}
Christian Würdig's avatar
Christian Würdig committed
212
213

	return max_height;
Sebastian Hack's avatar
Sebastian Hack committed
214
215
}

Matthias Braun's avatar
Matthias Braun committed
216
217
static void compute_heights_in_block_walker(ir_node *block, void *data)
{
218
	ir_heights_t *h = (ir_heights_t*) data;
Matthias Braun's avatar
Matthias Braun committed
219
220
221
	compute_heights_in_block(block, h);
}

222
unsigned get_irn_height(const ir_heights_t *heights, const ir_node *irn)
Sebastian Hack's avatar
Sebastian Hack committed
223
{
224
225
226
	const irn_height_t *height = maybe_get_height_data(heights, irn);
	assert(height != NULL && "No height information for node");
	return height->height;
Sebastian Hack's avatar
Sebastian Hack committed
227
228
}

229
unsigned heights_recompute_block(ir_heights_t *h, ir_node *block)
Christian Würdig's avatar
Christian Würdig committed
230
{
231
	ir_graph *irg = get_irn_irg(block);
Christian Würdig's avatar
Christian Würdig committed
232
233
	const ir_edge_t *edge;

234
	edges_assure(irg);
Christian Würdig's avatar
Christian Würdig committed
235
236
237
238

	/* reset phase data for all nodes in the block */
	foreach_out_edge(block, edge) {
		ir_node      *irn = get_edge_src_irn(edge);
239
		irn_height_t *ih  = get_height_data(h, irn);
240
		memset(ih, 0, sizeof(*ih));
Christian Würdig's avatar
Christian Würdig committed
241
242
243
244
245
246
	}

	h->visited = 0;
	return compute_heights_in_block(block, h);
}

247
ir_heights_t *heights_new(ir_graph *irg)
Sebastian Hack's avatar
Sebastian Hack committed
248
{
249
	ir_heights_t *res = XMALLOCZ(ir_heights_t);
250
251
	ir_nodemap_init(&res->data, irg);
	obstack_init(&res->obst);
Sebastian Hack's avatar
Sebastian Hack committed
252
	res->dump_handle = dump_add_node_info_callback(height_dump_cb, res);
253
254
255

	edges_assure(irg);
	irg_block_walk_graph(irg, compute_heights_in_block_walker, NULL, res);
Sebastian Hack's avatar
Sebastian Hack committed
256
257
258
259

	return res;
}

260
void heights_free(ir_heights_t *h)
Sebastian Hack's avatar
Sebastian Hack committed
261
{
262
	dump_remove_node_info_callback(h->dump_handle);
263
264
	obstack_free(&h->obst, NULL);
	ir_nodemap_destroy(&h->data);
Sebastian Hack's avatar
Sebastian Hack committed
265
266
	xfree(h);
}