beintlive_t.h 7.27 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @file   beintlive_t.h
 * @date   10.05.2007
 * @author Sebastian Hack
 *
 * Principal routines for liveness and interference checks.
 *
 * Copyright (C) 2007 Universitaet Karlsruhe
 * Released under the GPL
 */

#ifndef _BELIVECHK_T_H
#define _BELIVECHK_T_H

#include "irgraph_t.h"
#include "irphase_t.h"
#include "iredges_t.h"

Sebastian Hack's avatar
Sebastian Hack committed
19
20
#include "statev.h"

21
22
#include "beirg_t.h"
#include "besched_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
23
#include "belive_t.h"
24
25
26
27
28
29
30

/**
 * Check dominance of two nodes in the same block.
 * @param a The first node.
 * @param b The second node.
 * @return 1 if a comes before b in the same block or if a == b, 0 else.
 */
31
static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
32
33
{
	/* TODO: ? :  can be removed?! */
34
35
	sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
	sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
36
37
38
	return as <= bs;
}

39
40
41
42
43
44
/**
 * Check strict dominance of two nodes in the same block.
 * @param a The first node.
 * @param b The second node.
 * @return 1 if a comes before b in the same block, 0 else.
 */
45
static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
46
47
{
	/* TODO: ? :  can be removed?! */
48
49
	sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
	sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
50
51
52
	return as < bs;
}

53
54
55
56
57
58
59
/**
 * Check, if one value dominates the other.
 * The dominance is not strict here.
 * @param a The first node.
 * @param b The second node.
 * @return 1 if a dominates b or if a == b, 0 else.
 */
60
static inline int _value_dominates(const ir_node *a, const ir_node *b)
61
{
62
63
	const ir_node *block_a = get_block_const(a);
	const ir_node *block_b = get_block_const(b);
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

	/*
	 * a and b are not in the same block,
	 * so dominance is determined by the dominance of the blocks.
	 */
	if(block_a != block_b) {
		return block_dominates(block_a, block_b);
	}

	/*
	 * Dominance is determined by the time steps of the schedule.
	 */
	return _value_dominates_intrablock(a, b);
}

79
80
81
82
83
84
85
/**
 * Check, if one value dominates the other.
 * The dominance is strict here.
 * @param a The first node.
 * @param b The second node.
 * @return 1 if a dominates b, 0 else.
 */
86
static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
87
{
88
89
	const ir_node *block_a = get_block_const(a);
	const ir_node *block_b = get_block_const(b);
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

	/*
	 * a and b are not in the same block,
	 * so dominance is determined by the dominance of the blocks.
	 */
	if(block_a != block_b) {
		return block_dominates(block_a, block_b);
	}

	/*
	 * Dominance is determined by the time steps of the schedule.
	 */
	return _value_strictly_dominates_intrablock(a, b);
}

105
106
107
108
109
110
111
/**
 * Check, if two values interfere.
 * @param lv Liveness information (in the future we should use a be_irg_t here).
 * @param a The first value.
 * @param b The second value.
 * @return 1, if a and b interfere, 0 if not.
 */
112
static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
113
114
115
{
	int a2b = _value_dominates(a, b);
	int b2a = _value_dominates(b, a);
Sebastian Hack's avatar
Sebastian Hack committed
116
117
118
119
120
121
122
123
124
125
126
127
	int res = 0;

	/*
	 * Adjust a and b so, that a dominates b if
	 * a dominates b or vice versa.
	 */
	if(b2a) {
		const ir_node *t = a;
		a = b;
		b = t;
		a2b = 1;
	}
128
129

	/* If there is no dominance relation, they do not interfere. */
Sebastian Hack's avatar
Sebastian Hack committed
130
	if(a2b) {
131
		const ir_edge_t *edge;
Sebastian Hack's avatar
Sebastian Hack committed
132
		ir_node *bb = get_nodes_block(b);
133

134
		//stat_ev_dbl("beintlive_ignore", arch_irn_is(lv->birg->main_env->arch_env, a, ignore));
135
136
137
138
139

		/*
		 * If a is live end in b's block it is
		 * live at b's definition (a dominates b)
		 */
Sebastian Hack's avatar
Sebastian Hack committed
140
141
142
143
		if(be_is_live_end(lv, bb, a)) {
			res = 1;
			goto end;
		}
144
145
146
147
148
149
150
151
152
153
154
155
156
157

		/*
		 * Look at all usages of a.
		 * If there's one usage of a in the block of b, then
		 * we check, if this use is dominated by b, if that's true
		 * a and b interfere. Note that b must strictly dominate the user,
		 * since if b is the last user of in the block, b and a do not
		 * interfere.
		 * Uses of a not in b's block can be disobeyed, because the
		 * check for a being live at the end of b's block is already
		 * performed.
		 */
		foreach_out_edge(a, edge) {
			const ir_node *user = get_edge_src_irn(edge);
Sebastian Hack's avatar
Sebastian Hack committed
158
159
160
161
			if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
				res = 1;
				goto end;
			}
162
163
164
		}
  	}

Sebastian Hack's avatar
Sebastian Hack committed
165
166
end:
	return res;
167
168
169
170
171
172
173
174
175
176
177
}



/**
 * Check if a node dominates a use.
 * Note that the use of a phi is in its corresponding predecessor.
 * @param irn  The node.
 * @param edge The use.
 * @return     1, if @p irn dominates the use @p edge.
 */
178
static inline int _dominates_use(const ir_node *irn, const ir_edge_t *edge)
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
{
	ir_node *use = get_edge_src_irn(edge);

	if (is_Phi(use)) {
		int pos         = get_edge_src_pos(edge);
		ir_node *phi_bl = get_nodes_block(use);
		ir_node *use_bl = get_Block_cfgpred_block(phi_bl, pos);
		ir_node *irn_bl = get_nodes_block(irn);
		return block_dominates(irn_bl, use_bl);
	}

	return _value_dominates(irn, use);
}

/**
 * Check if a node strictly dominates a use.
 * Note that the use of a phi is in its corresponding predecessor.
 * @param irn  The node.
 * @param edge The use.
 * @return     1, if @p irn strictly dominates the use @p edge.
 */
200
static inline int _strictly_dominates_use(const ir_node *irn, const ir_edge_t *edge)
201
202
203
204
205
206
207
208
209
210
211
{
	return get_edge_src_irn(edge) != irn && _dominates_use(irn, edge);
}

/**
 * Check, if a node is live in front of another.
 * @param birg  The backend irg.
 * @param irn   The node.
 * @param where The location to check for.
 * @return      1, if @p irn is live in front of @p where.
 */
212
static inline int _be_lv_chk_before_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
213
{
Sebastian Hack's avatar
Sebastian Hack committed
214
	const be_lv_t *lv = be_get_birg_liveness(birg);
215
216
217
218
219
220
221
222
223
224
	const ir_edge_t *edge;

	/* the node must strictly dominate the location, else it cannot be live there. */
	if (!_value_dominates(irn, where) || irn == where)
		return 0;

	/*
	 * now that it is clear that it strictly dominates the location it is surely live
	 * if it is also live end at the block.
	 */
Sebastian Hack's avatar
Sebastian Hack committed
225
	if (be_is_live_end(lv, get_nodes_block(where), irn))
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
		return 1;

	/*
	 * If the node is not live out, we have to check if there
	 * is a use which is dominated by the location.
	 */
	foreach_out_edge (irn, edge) {
		if (_dominates_use(where, edge))
			return 1;
	}

	return 0;
}

/**
 * Check, if a node is live after another node.
 * @param birg  The backend irg.
 * @param irn   The node.
 * @param where The location to check for.
 * @return      1, if @p irn is live after @p where.
 */
247
static inline int _be_lv_chk_after_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
248
{
Sebastian Hack's avatar
Sebastian Hack committed
249
	const be_lv_t *lv = be_get_birg_liveness(birg);
250
251
252
253
254
	const ir_edge_t *edge;

	if (!_value_dominates(irn, where))
		return 0;

Sebastian Hack's avatar
Sebastian Hack committed
255
	if (be_is_live_end(lv, get_nodes_block(where), irn))
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
		return 1;

	foreach_out_edge (irn, edge) {
		if (_strictly_dominates_use(where, edge))
			return 1;
	}

	return 0;
}

#define value_dominates_intrablock(a, b)         _value_dominates_intrablock(a, b)
#define value_dominates(a, b)                    _value_dominates(a, b)
#define dominates_use(a, e)                      _dominates_use(a, e)
#define strictly_dominates_use(a, e)             _strictly_dominates_use(a, e)
#define be_lv_chk_before_irn(birg, a, b)         _be_lv_chk_before_irn(birg, a, b)
#define be_lv_chk_after_irn(birg, a, b)          _be_lv_chk_after_irn(birg, a, b)

#endif /* _BELIVECHK_T_H */