vrp.c 17.3 KB
Newer Older
Jonas Fietz's avatar
Jonas Fietz committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Jonas Fietz's avatar
Jonas Fietz committed
4
5
6
7
 */

/**
 * @file
8
9
 * @brief   analyze graph to provide value range information
 * @author  Jonas Fietz
Jonas Fietz's avatar
Jonas Fietz committed
10
11
12
 */
#include "irtypes.h"
#include "vrp.h"
Matthias Braun's avatar
Matthias Braun committed
13
#include "iroptimize.h"
Jonas Fietz's avatar
Jonas Fietz committed
14
15
#include "irouts.h"
#include "irgraph_t.h"
16
#include "irgopt.h"
Jonas Fietz's avatar
Jonas Fietz committed
17
18
19
#include "irgwalk.h"
#include "iredges.h"
#include "tv.h"
20
#include "irop.h"
21
#include "pdeq.h"
22
#include "irnodemap.h"
23
#include "irhooks.h"
24
#include "bitset.h"
25
#include "debug.h"
Jonas Fietz's avatar
Jonas Fietz committed
26

27
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
Jonas Fietz's avatar
Jonas Fietz committed
28

Matthias Braun's avatar
Matthias Braun committed
29
typedef struct vrp_env_t {
30
31
32
	waitq       *workqueue;
	bitset_t    *visited;
	ir_vrp_info *info;
Matthias Braun's avatar
Matthias Braun committed
33
} vrp_env_t;
Jonas Fietz's avatar
Jonas Fietz committed
34

35
static vrp_attr *vrp_get_or_set_info(ir_vrp_info *info, const ir_node *node)
36
{
37
	vrp_attr *attr = ir_nodemap_get(vrp_attr, &info->infos, node);
38
39
40
41
	if (attr == NULL) {
		ir_mode *mode = get_irn_mode(node);
		assert(mode_is_int(mode));

42
		attr = OALLOCZ(&info->obst, vrp_attr);
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
		attr->range_type   = VRP_UNDEFINED;
		attr->bits_set     = get_mode_null(mode);
		attr->bits_not_set = get_mode_all_one(mode);
		attr->range_bottom = get_tarval_top();
		attr->range_top    = get_tarval_top();

		ir_nodemap_insert(&info->infos, node, attr);
	}
	return attr;
}

vrp_attr *vrp_get_info(const ir_node *node)
{
	ir_graph *irg = get_irn_irg(node);
	if (irg->vrp.infos.data == NULL)
		return NULL;
59
	return ir_nodemap_get(vrp_attr, &irg->vrp.infos, node);
60
61
}

62
static int vrp_update_node(ir_vrp_info *info, ir_node *node)
63
{
Matthias Braun's avatar
Matthias Braun committed
64
65
66
67
68
69
	ir_tarval       *new_bits_set      = get_tarval_bad();
	ir_tarval       *new_bits_not_set  = get_tarval_bad();
	ir_tarval       *new_range_bottom  = get_tarval_bad();
	ir_tarval       *new_range_top     = get_tarval_bad();
	enum range_types new_range_type    = VRP_UNDEFINED;
	bool             something_changed = false;
70
71
72
	if (!mode_is_int(get_irn_mode(node))) {
		return 0; /* we don't optimize for non-int-nodes*/
	}
73

Matthias Braun's avatar
Matthias Braun committed
74
	vrp_attr *vrp = vrp_get_or_set_info(info, node);
Jonas Fietz's avatar
Jonas Fietz committed
75

Jonas Fietz's avatar
Jonas Fietz committed
76
	/* TODO: Check if all predecessors have valid VRP information*/
Jonas Fietz's avatar
Jonas Fietz committed
77

78
	switch (get_irn_opcode(node)) {
Jonas Fietz's avatar
Jonas Fietz committed
79
	case iro_Const: {
Matthias Braun's avatar
Matthias Braun committed
80
		ir_tarval *tv = get_Const_tarval(node);
Jonas Fietz's avatar
Jonas Fietz committed
81
		new_bits_set = tv;
82
		new_bits_not_set = tv;
Jonas Fietz's avatar
Jonas Fietz committed
83
84
85
		new_range_bottom = tv;
		new_range_top = tv;
		new_range_type = VRP_RANGE;
86
		break;
Jonas Fietz's avatar
Jonas Fietz committed
87
88
	}
	case iro_And: {
89
90
		const vrp_attr *vrp_left, *vrp_right;
		const ir_node *left, *right;
91
92
93

		left = get_And_left(node);
		right = get_And_right(node);
94
95
		vrp_left = vrp_get_or_set_info(info, left);
		vrp_right = vrp_get_or_set_info(info, right);
96
		new_bits_set = tarval_and(vrp_left->bits_set, vrp_right->bits_set);
97
		new_bits_not_set = tarval_and(vrp_left->bits_not_set, vrp_right->bits_not_set);
98

99
		break;
Jonas Fietz's avatar
Jonas Fietz committed
100
	}
101

Jonas Fietz's avatar
Jonas Fietz committed
102
	case iro_Add: {
Matthias Braun's avatar
Matthias Braun committed
103
104
		const vrp_attr *vrp_left  = vrp_get_or_set_info(info, get_Add_left(node));
		const vrp_attr *vrp_right = vrp_get_or_set_info(info, get_Add_right(node));
105

Matthias Braun's avatar
Matthias Braun committed
106
107
108
109
		if (vrp_left->range_type == VRP_UNDEFINED
		 || vrp_right->range_type == VRP_UNDEFINED
		 || vrp_left->range_type == VRP_VARYING
		 || vrp_right->range_type == VRP_VARYING) {
Jonas Fietz's avatar
Jonas Fietz committed
110
111
112
			return 0;
		}

Matthias Braun's avatar
Matthias Braun committed
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
		if (vrp_left->range_type == VRP_RANGE
		 && vrp_right->range_type == VRP_RANGE) {
			tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();
			tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
			ir_tarval *new_top
				= tarval_add(vrp_left->range_top, vrp_right->range_top);
			ir_tarval *new_bottom
				= tarval_add(vrp_left->range_bottom, vrp_right->range_bottom);
			tarval_set_integer_overflow_mode(rem);

			if (new_top != tarval_bad && new_bottom != tarval_bad) {
				new_range_bottom = new_bottom;
				new_range_top    = new_top;
				new_range_type   = VRP_RANGE;
			} else {
				/* TODO Implement overflow handling*/
				new_range_type = VRP_UNDEFINED;
			}
Jonas Fietz's avatar
Jonas Fietz committed
131
		}
132
		break;
Jonas Fietz's avatar
Jonas Fietz committed
133
	}
Jonas Fietz's avatar
Jonas Fietz committed
134

Jonas Fietz's avatar
Jonas Fietz committed
135
	case iro_Sub: {
136
137
138
139
140
141
		ir_node *left  = get_Sub_left(node);
		ir_node *right = get_Sub_right(node);

		if (!mode_is_int(get_irn_mode(left)))
			return 0;

Matthias Braun's avatar
Matthias Braun committed
142
143
		const vrp_attr *vrp_left  = vrp_get_or_set_info(info, left);
		const vrp_attr *vrp_right = vrp_get_or_set_info(info, right);
144

Matthias Braun's avatar
Matthias Braun committed
145
146
147
148
		if (vrp_left->range_type == VRP_UNDEFINED
		 || vrp_right->range_type == VRP_UNDEFINED
		 || vrp_left->range_type == VRP_VARYING
		 || vrp_right->range_type == VRP_VARYING) {
Jonas Fietz's avatar
Jonas Fietz committed
149
150
151
			return 0;
		}

Matthias Braun's avatar
Matthias Braun committed
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
		if (vrp_left->range_type == VRP_RANGE
		 && vrp_right->range_type == VRP_RANGE) {
			tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode();
			tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
			ir_tarval *new_top = tarval_sub(vrp_left->range_top, vrp_right->range_top, NULL);
			ir_tarval *new_bottom = tarval_sub(vrp_left->range_bottom, vrp_right->range_bottom, NULL);
			tarval_set_integer_overflow_mode(rem);

			if (new_top != tarval_bad && new_bottom != tarval_bad) {
				new_range_bottom = new_bottom;
				new_range_top = new_top;
				new_range_type = VRP_RANGE;
			} else {
				/* TODO Implement overflow handling*/
				new_range_type = VRP_UNDEFINED;
			}
Jonas Fietz's avatar
Jonas Fietz committed
168
		}
169
		break;
Jonas Fietz's avatar
Jonas Fietz committed
170
171
172
	}

	case iro_Or: {
173
		const vrp_attr *vrp_left, *vrp_right;
Jonas Fietz's avatar
Jonas Fietz committed
174

175
176
		vrp_left = vrp_get_or_set_info(info, get_Or_left(node));
		vrp_right = vrp_get_or_set_info(info, get_Or_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
177

178
		new_bits_set = tarval_or(vrp_left->bits_set, vrp_right->bits_set);
179
		new_bits_not_set = tarval_or(vrp_left->bits_not_set, vrp_right->bits_not_set);
180

181
		break;
Jonas Fietz's avatar
Jonas Fietz committed
182
183
184
	}

	case iro_Shl: {
185
		const vrp_attr *vrp_left;
186
		const ir_node *right = get_Shl_right(node);
187
		vrp_left = vrp_get_or_set_info(info, get_Shl_left(node));
Jonas Fietz's avatar
Jonas Fietz committed
188

Jonas Fietz's avatar
Jonas Fietz committed
189
		/* We can only compute this if the right value is a constant*/
190
		if (is_Const(right)) {
191
192
			new_bits_set = tarval_shl(vrp_left->bits_set, get_Const_tarval(right));
			new_bits_not_set = tarval_shl(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
193
		}
194
		break;
Jonas Fietz's avatar
Jonas Fietz committed
195
196
197
	}

	case iro_Shr: {
198
		const vrp_attr *vrp_left;
199
		const ir_node *right = get_Shr_right(node);
Jonas Fietz's avatar
Jonas Fietz committed
200

201
		vrp_left = vrp_get_or_set_info(info, get_Shr_left(node));
Jonas Fietz's avatar
Jonas Fietz committed
202

Jonas Fietz's avatar
Jonas Fietz committed
203
		/* We can only compute this if the right value is a constant*/
204
		if (is_Const(right)) {
205
206
			new_bits_set = tarval_shr(vrp_left->bits_set, get_Const_tarval(right));
			new_bits_not_set = tarval_shr(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
207
		}
208
		break;
Jonas Fietz's avatar
Jonas Fietz committed
209
210
211
	}

	case iro_Shrs: {
212
		const vrp_attr *vrp_left;
213
		const ir_node *right = get_Shrs_right(node);
Jonas Fietz's avatar
Jonas Fietz committed
214

215
		vrp_left = vrp_get_or_set_info(info, get_Shrs_left(node));
Jonas Fietz's avatar
Jonas Fietz committed
216

Jonas Fietz's avatar
Jonas Fietz committed
217
		/* We can only compute this if the right value is a constant*/
218
		if (is_Const(right)) {
219
220
			new_bits_set = tarval_shrs(vrp_left->bits_set, get_Const_tarval(right));
			new_bits_not_set = tarval_shrs(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
221
		}
222
		break;
Jonas Fietz's avatar
Jonas Fietz committed
223
224
225
	}

	case iro_Eor: {
226
		const vrp_attr *vrp_left, *vrp_right;
Jonas Fietz's avatar
Jonas Fietz committed
227

228
229
		vrp_left = vrp_get_or_set_info(info, get_Eor_left(node));
		vrp_right = vrp_get_or_set_info(info, get_Eor_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
230

231
232
233
		new_bits_set = tarval_or(
						tarval_and(vrp_left->bits_set, tarval_not(vrp_right->bits_not_set)),
						tarval_and(tarval_not(vrp_left->bits_not_set), vrp_right->bits_set));
Jonas Fietz's avatar
Jonas Fietz committed
234

235
236
237
238
		new_bits_not_set = tarval_not(tarval_or(
				tarval_and(vrp_left->bits_set,vrp_right->bits_set),
							tarval_and(tarval_not(vrp_left->bits_not_set),
								tarval_not(vrp_right->bits_not_set))));
Jonas Fietz's avatar
Jonas Fietz committed
239

240
		break;
Jonas Fietz's avatar
Jonas Fietz committed
241
	}
Jonas Fietz's avatar
Jonas Fietz committed
242

Jonas Fietz's avatar
Jonas Fietz committed
243
	case iro_Id: {
244
		const vrp_attr *vrp_pred = vrp_get_or_set_info(info, get_Id_pred(node));
245
246
247
248
249
		new_bits_set = vrp_pred->bits_set;
		new_bits_not_set = vrp_pred->bits_not_set;
		new_range_top = vrp_pred->range_top;
		new_range_bottom = vrp_pred->range_bottom;
		new_range_type = vrp_pred->range_type;
250
		break;
Jonas Fietz's avatar
Jonas Fietz committed
251
	}
Jonas Fietz's avatar
Jonas Fietz committed
252

Jonas Fietz's avatar
Jonas Fietz committed
253
	case iro_Not: {
254
		const vrp_attr *vrp_pred = vrp_get_or_set_info(info, get_Not_op(node));
255
256
		new_bits_set = tarval_not(vrp_pred->bits_not_set);
		new_bits_not_set = tarval_not(vrp_pred->bits_set);
257
		break;
Jonas Fietz's avatar
Jonas Fietz committed
258
	}
Jonas Fietz's avatar
Jonas Fietz committed
259

Jonas Fietz's avatar
Jonas Fietz committed
260
	case iro_Conv: {
261
		const ir_node *pred = get_Conv_op(node);
262
		ir_mode *old_mode = get_irn_mode(pred);
263
		const vrp_attr *vrp_pred;
Jonas Fietz's avatar
Jonas Fietz committed
264

265
266
267
		ir_mode *new_mode;

		if (!mode_is_int(old_mode))
Jonas Fietz's avatar
Jonas Fietz committed
268
269
			return 0;

270
		vrp_pred = vrp_get_or_set_info(info, pred);
271
		new_mode = get_irn_mode(node);
Jonas Fietz's avatar
Jonas Fietz committed
272

Jonas Fietz's avatar
Jonas Fietz committed
273
		/* The second and is needed if target type is smaller*/
274
275
		new_bits_not_set = tarval_convert_to(get_mode_all_one(old_mode), new_mode);
		new_bits_not_set = tarval_and(new_bits_not_set, tarval_convert_to(vrp_pred->bits_not_set, new_mode));
Jonas Fietz's avatar
Jonas Fietz committed
276
		new_bits_set = tarval_and(
277
				new_bits_not_set, tarval_convert_to(vrp_pred->bits_set, new_mode));
Jonas Fietz's avatar
Jonas Fietz committed
278

279
280
		/* Matze: TODO, BUGGY, tarval_cmp never returns ir_relation_less_equal */
		if (tarval_cmp(vrp_pred->range_top, get_mode_max(new_mode)) == ir_relation_less_equal) {
281
			vrp->range_top = vrp_pred->range_top;
Jonas Fietz's avatar
Jonas Fietz committed
282
283
		}

284
285
		/* Matze: TODO, BUGGY, tarval_cmp never returns ir_relation_greater_equal */
		if (tarval_cmp(vrp_pred->range_bottom, get_mode_min(new_mode)) == ir_relation_greater_equal) {
286
			vrp->range_bottom = vrp_pred->range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
287
		}
288
		break;
Jonas Fietz's avatar
Jonas Fietz committed
289
	}
Jonas Fietz's avatar
Jonas Fietz committed
290

Jonas Fietz's avatar
Jonas Fietz committed
291
	case iro_Confirm: {
292
293
		const ir_relation relation = get_Confirm_relation(node);
		const ir_node    *bound    = get_Confirm_bound(node);
Jonas Fietz's avatar
Jonas Fietz committed
294
295


296
		if (relation == ir_relation_less_greater) {
297
			/** @todo: Handle non-Const bounds */
Jonas Fietz's avatar
Jonas Fietz committed
298
			if (is_Const(bound)) {
299
				new_range_type = VRP_ANTIRANGE;
Jonas Fietz's avatar
Jonas Fietz committed
300
301
302
				new_range_top = get_Const_tarval(bound);
				new_range_bottom = get_Const_tarval(bound);
			}
303
		} else if (relation == ir_relation_less_equal) {
304
			if (is_Const(bound)) {
Jonas Fietz's avatar
Jonas Fietz committed
305
				new_range_type = VRP_RANGE;
306
				new_range_top = get_Const_tarval(bound);
Jonas Fietz's avatar
Jonas Fietz committed
307
308
309
				new_range_bottom = get_tarval_min(get_irn_mode(node));
			}
		}
310
		break;
Jonas Fietz's avatar
Jonas Fietz committed
311
	}
Jonas Fietz's avatar
Jonas Fietz committed
312

Jonas Fietz's avatar
Jonas Fietz committed
313
	case iro_Phi: {
Jonas Fietz's avatar
Jonas Fietz committed
314
		/* combine all ranges*/
315
		const ir_node *pred = get_Phi_pred(node,0);
316
		const vrp_attr *vrp_pred = vrp_get_or_set_info(info, pred);
Matthias Braun's avatar
Matthias Braun committed
317
		new_range_top    = vrp_pred->range_top;
318
		new_range_bottom = vrp_pred->range_bottom;
Matthias Braun's avatar
Matthias Braun committed
319
320
		new_range_type   = vrp_pred->range_type;
		new_bits_set     = vrp_pred->bits_set;
321
		new_bits_not_set = vrp_pred->bits_not_set;
322

Matthias Braun's avatar
Matthias Braun committed
323
		for (int i = 1, num = get_Phi_n_preds(node); i < num; i++) {
Jonas Fietz's avatar
Jonas Fietz committed
324
			pred = get_Phi_pred(node, i);
325
			vrp_pred = vrp_get_or_set_info(info, pred);
326
			if (new_range_type == VRP_RANGE && vrp_pred->range_type ==
Jonas Fietz's avatar
Jonas Fietz committed
327
					VRP_RANGE) {
Matthias Braun's avatar
Matthias Braun committed
328
				ir_relation relation = tarval_cmp(new_range_top, vrp_pred->range_top);
329
				if (relation == ir_relation_less) {
330
					new_range_top = vrp_pred->range_top;
Jonas Fietz's avatar
Jonas Fietz committed
331
				}
332
333
				relation = tarval_cmp(new_range_bottom, vrp_pred->range_bottom);
				if (relation == ir_relation_greater) {
334
					new_range_bottom = vrp_pred->range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
335
336
				}
			} else {
337
				new_range_type = VRP_VARYING;
Jonas Fietz's avatar
Jonas Fietz committed
338
			}
339
340
341
			new_bits_set = tarval_and(new_bits_set, vrp_pred->bits_set);
			new_bits_not_set = tarval_or(new_bits_not_set,
					vrp_pred->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
342
343
		}

344
		break;
Jonas Fietz's avatar
Jonas Fietz committed
345
	}
346
347
348
	default:
		/* unhandled, therefore never updated */
		break;
Jonas Fietz's avatar
Jonas Fietz committed
349
350
351
352
353
	}



	/* TODO: Check, if there can be information derived from any of these:
354
	is_Abs(node) is_Alloc(node) is_Anchor(node) is_Borrow(node) is_Bound(node)
355
	is_Break(node) is_Builtin(node) is_Call(node)
Matthias Braun's avatar
Matthias Braun committed
356
	is_Carry(node) is_Cmp(node) is_Cond(node)
Matthias Braun's avatar
Matthias Braun committed
357
	is_CopyB(node) is_Div(node) is_Dummy(node)
358
	is_End(node) is_Free(node)
Jonas Fietz's avatar
Jonas Fietz committed
359
360
	is_IJmp(node) is_InstOf(node) is_Jmp(node) is_Load(node) is_Minus(node)
	is_Mod(node) is_Mul(node) is_Mulh(node) is_Mux(node) is_NoMem(node)
361
	is_Pin(node) is_Proj(node)
Jonas Fietz's avatar
Jonas Fietz committed
362
363
364
365
	is_Raise(node) is_Return(node) is_Sel(node) is_Start(node) is_Store(node)
	is_SymConst(node) is_Sync(node) is_Tuple(node)
	*/

366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
	/* @todo: At this place, we check if the mode of the variable changed. A
	 * better place for this might be in the convopt.c file
	 */

	if (new_bits_set != tarval_bad && get_tarval_mode(new_bits_set) != get_tarval_mode(vrp->bits_set)) {
		vrp->bits_set = tarval_convert_to(vrp->bits_set, get_irn_mode(node));
	}
	if (new_bits_not_set != tarval_bad && get_tarval_mode(new_bits_not_set) != get_tarval_mode(vrp->bits_not_set)) {
		vrp->bits_not_set = tarval_convert_to(vrp->bits_not_set, get_irn_mode(node));
	}

	if (vrp->range_type != VRP_UNDEFINED && new_range_type != VRP_UNDEFINED && get_tarval_mode(new_range_top) != get_tarval_mode(vrp->range_top)) {
		/* @todo: We might be able to preserve this range information if it
		 * fits in */
		vrp->range_type = VRP_VARYING;
	}

Jonas Fietz's avatar
Jonas Fietz committed
383
	/* Merge the newly calculated values with those that might already exist*/
Jonas Fietz's avatar
Jonas Fietz committed
384
	if (new_bits_set != tarval_bad) {
385
		new_bits_set = tarval_or(new_bits_set, vrp->bits_set);
386
		if (new_bits_set != vrp->bits_set) {
Matthias Braun's avatar
Matthias Braun committed
387
388
			something_changed = true;
			vrp->bits_set     = new_bits_set;
Jonas Fietz's avatar
Jonas Fietz committed
389
390
391
		}
	}
	if (new_bits_not_set != tarval_bad) {
392
		new_bits_not_set = tarval_and(new_bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
393

394
		if (new_bits_not_set != vrp->bits_not_set) {
Matthias Braun's avatar
Matthias Braun committed
395
			something_changed = true;
396
			vrp->bits_not_set = new_bits_not_set;
Jonas Fietz's avatar
Jonas Fietz committed
397
398
399
		}
	}

400
	if (vrp->range_type == VRP_UNDEFINED &&
Jonas Fietz's avatar
Jonas Fietz committed
401
			new_range_type != VRP_UNDEFINED) {
Matthias Braun's avatar
Matthias Braun committed
402
		something_changed = true;
403
404
405
		vrp->range_type = new_range_type;
		vrp->range_bottom = new_range_bottom;
		vrp->range_top = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
406

407
	} else if (vrp->range_type == VRP_RANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
408
		if (new_range_type == VRP_RANGE) {
409
			if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_less) {
Matthias Braun's avatar
Matthias Braun committed
410
				something_changed = true;
411
				vrp->range_bottom = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
412
			}
413
			if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_greater) {
Matthias Braun's avatar
Matthias Braun committed
414
415
				something_changed = true;
				vrp->range_top    = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
416
417
418
419
			}
		}

		if (new_range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
420
421
			/* if they are overlapping, cut the range.*/
			/* TODO: Maybe we can preserve more information here*/
422
423
			if (tarval_cmp(vrp->range_bottom, new_range_top) == ir_relation_greater &&
					tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_greater) {
Matthias Braun's avatar
Matthias Braun committed
424
				something_changed = true;
425
				vrp->range_bottom = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
426

427
428
			} else if (tarval_cmp(vrp->range_top, new_range_bottom) == ir_relation_greater &&
					tarval_cmp(vrp->range_top, new_range_top) == ir_relation_less) {
Matthias Braun's avatar
Matthias Braun committed
429
430
				something_changed = true;
				vrp->range_top    = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
431
			}
432
433
434
435

			/* We can not handle the case where the anti range is in the*/
			/* range*/

Jonas Fietz's avatar
Jonas Fietz committed
436
		}
437
	} else if (vrp->range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
438
		if (new_range_type == VRP_ANTIRANGE) {
439
			if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_greater) {
Matthias Braun's avatar
Matthias Braun committed
440
				something_changed = true;
441
				vrp->range_bottom = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
442
			}
443
			if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_less) {
Matthias Braun's avatar
Matthias Braun committed
444
445
				something_changed = true;
				vrp->range_top    = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
446
447
448
449
			}
		}

		if (new_range_type == VRP_RANGE) {
450
			if (tarval_cmp(vrp->range_bottom, new_range_top) == ir_relation_greater) {
Matthias Braun's avatar
Matthias Braun committed
451
				something_changed = true;
452
				vrp->range_bottom = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
453
			}
454
			if (tarval_cmp(vrp->range_top, new_range_bottom) == ir_relation_less) {
Matthias Braun's avatar
Matthias Braun committed
455
456
				something_changed = true;
				vrp->range_top    = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
457
458
459
460
			}
		}
	}

Matthias Braun's avatar
Matthias Braun committed
461
	assert(tarval_is_null(tarval_and(vrp->bits_set, tarval_not(vrp->bits_not_set))));
Jonas Fietz's avatar
Jonas Fietz committed
462
463
464
	return something_changed;
}

465
static void vrp_first_pass(ir_node *n, void *e)
466
{
Jonas Fietz's avatar
Jonas Fietz committed
467
468
469
	if (is_Block(n))
		return;

Matthias Braun's avatar
Matthias Braun committed
470
	vrp_env_t *env = (vrp_env_t*) e;
471
	bitset_set(env->visited, get_irn_idx(n));
Jonas Fietz's avatar
Jonas Fietz committed
472

473
	vrp_update_node(env->info, n);
Jonas Fietz's avatar
Jonas Fietz committed
474

Matthias Braun's avatar
Matthias Braun committed
475
	for (int i = get_irn_n_outs(n); i-- > 0; ) {
476
477
		ir_node *succ = get_irn_out(n, i);
		if (bitset_is_set(env->visited, get_irn_idx(succ))) {
Jonas Fietz's avatar
Jonas Fietz committed
478
			/* we found a loop*/
Jonas Fietz's avatar
Jonas Fietz committed
479
			waitq_put(env->workqueue, succ);
Jonas Fietz's avatar
Jonas Fietz committed
480
481
482
483
		}
	}
}

484
485
486
487
488
489
static void dump_vrp_info(void *ctx, FILE *F, const ir_node *node)
{
	(void) ctx;
	if (!mode_is_int(get_irn_mode(node)))
		return;

Matthias Braun's avatar
Matthias Braun committed
490
	vrp_attr *vrp = vrp_get_info(node);
491
492
493
494
495
496
497
498
499
500
501
502
503
504
	if (vrp == NULL)
		return;

	fprintf(F, "vrp range type: %d\n", (int) vrp->range_type);
	if (vrp->range_type == VRP_RANGE || vrp->range_type == VRP_ANTIRANGE) {
		ir_fprintf(F, "vrp range bottom: %T\n",vrp->range_bottom);
		ir_fprintf(F, "vrp range top: %T\n", vrp->range_top);
	}
	ir_fprintf(F, "vrp bits set: %T\n", vrp->bits_set);
	ir_fprintf(F, "vrp bits not set: %T\n", vrp->bits_not_set);
}

static hook_entry_t dump_hook;

505
506
void set_vrp_data(ir_graph *irg)
{
507
508
	if (irg->vrp.infos.data != NULL)
		free_vrp_data(irg);
Jonas Fietz's avatar
Jonas Fietz committed
509

510
511
	FIRM_DBG_REGISTER(dbg, "ir.ana.vrp");

Jonas Fietz's avatar
Jonas Fietz committed
512
	assure_irg_outs(irg); /* ensure that out edges are consistent*/
513
514
	ir_nodemap_init(&irg->vrp.infos, irg);
	obstack_init(&irg->vrp.obst);
Matthias Braun's avatar
Matthias Braun committed
515
	ir_vrp_info *info = &irg->vrp;
516

517
518
519
520
521
	if (dump_hook.hook._hook_node_info == NULL) {
		dump_hook.hook._hook_node_info = dump_vrp_info;
		register_hook(hook_node_info, &dump_hook);
	}

Matthias Braun's avatar
Matthias Braun committed
522
	vrp_env_t *env = OALLOCZ(&irg->vrp.obst, vrp_env_t);
523
	env->workqueue = new_waitq();
524
	env->info      = info;
Jonas Fietz's avatar
Jonas Fietz committed
525

526
	env->visited = bitset_malloc(get_irg_last_idx(irg));
527
	irg_walk_graph(irg, NULL, vrp_first_pass, env);
528
	free(env->visited);
Jonas Fietz's avatar
Jonas Fietz committed
529

Jonas Fietz's avatar
Jonas Fietz committed
530
	/* while there are entries in the worklist, continue*/
531
	while (!waitq_empty(env->workqueue)) {
Matthias Braun's avatar
Matthias Braun committed
532
		ir_node *node = (ir_node*) waitq_get(env->workqueue);
533

534
		if (vrp_update_node(info, node)) {
535
			/* if something changed, add successors to worklist*/
Matthias Braun's avatar
Matthias Braun committed
536
537
			for (int i = get_irn_n_outs(node); i-- > 0; ) {
				ir_node *succ =  get_irn_out(node, i);
538
				waitq_put(env->workqueue, succ);
Jonas Fietz's avatar
Jonas Fietz committed
539
540
541
			}
		}
	}
542
	del_waitq(env->workqueue);
Jonas Fietz's avatar
Jonas Fietz committed
543
544
}

545
546
547
548
549
550
551
552
void free_vrp_data(ir_graph *irg)
{
	if (irg->vrp.infos.data == NULL)
		return;
	obstack_free(&irg->vrp.obst, NULL);
	ir_nodemap_destroy(&irg->vrp.infos);
}

553
ir_relation vrp_cmp(const ir_node *left, const ir_node *right)
554
{
555
556
557
	if (!mode_is_int(get_irn_mode(left)))
		return ir_relation_true;

Matthias Braun's avatar
Matthias Braun committed
558
559
560
	vrp_attr *vrp_left  = vrp_get_info(left);
	vrp_attr *vrp_right = vrp_get_info(right);
	if (vrp_left == NULL || vrp_right == NULL)
561
		return ir_relation_true;
yb9976's avatar
yb9976 committed
562

563
	if (vrp_left->range_type == VRP_RANGE && vrp_right->range_type == VRP_RANGE) {
564
565
		if (tarval_cmp(vrp_left->range_top, vrp_right->range_bottom) == ir_relation_less) {
			return ir_relation_less;
566
		}
567
568
		if (tarval_cmp(vrp_left->range_bottom, vrp_right->range_top) == ir_relation_greater) {
			return ir_relation_greater;
Jonas Fietz's avatar
Jonas Fietz committed
569
		}
570
	}
Jonas Fietz's avatar
Jonas Fietz committed
571

572
573
	if (!tarval_is_null(tarval_and(vrp_left->bits_set, tarval_not(vrp_right->bits_not_set))) ||
			!tarval_is_null(tarval_and(tarval_not(vrp_left->bits_not_set), vrp_right->bits_set))) {
574
		return ir_relation_less_greater;
Jonas Fietz's avatar
Jonas Fietz committed
575
576
	}

577
578
	/* TODO: We can get way more information here*/
	return ir_relation_true;
Jonas Fietz's avatar
Jonas Fietz committed
579
}