vrp.c 17.2 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"
14
#include "irouts_t.h"
Jonas Fietz's avatar
Jonas Fietz committed
15
#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 "irprintf.h"
22
#include "pdeq.h"
23
#include "irnodemap.h"
24
#include "irhooks.h"
25
#include "bitset.h"
26
#include "debug.h"
Jonas Fietz's avatar
Jonas Fietz committed
27

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

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

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

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

		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;
60
	return ir_nodemap_get(vrp_attr, &irg->vrp.infos, node);
61
62
}

63
static int vrp_update_node(ir_vrp_info *info, ir_node *node)
64
{
Matthias Braun's avatar
Matthias Braun committed
65
66
67
68
69
70
	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;
71
72
73
	if (!mode_is_int(get_irn_mode(node))) {
		return 0; /* we don't optimize for non-int-nodes*/
	}
74

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

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

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

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

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

Jonas Fietz's avatar
Jonas Fietz committed
103
	case iro_Add: {
Matthias Braun's avatar
Matthias Braun committed
104
105
		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));
106

Matthias Braun's avatar
Matthias Braun committed
107
108
109
110
		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
111
112
113
			return 0;
		}

Matthias Braun's avatar
Matthias Braun committed
114
115
		if (vrp_left->range_type == VRP_RANGE
		 && vrp_right->range_type == VRP_RANGE) {
Matthias Braun's avatar
Matthias Braun committed
116
117
			int old_wrap_on_overflow = tarval_get_wrap_on_overflow();
			tarval_set_wrap_on_overflow(false);
Matthias Braun's avatar
Matthias Braun committed
118
119
120
121
			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);
Matthias Braun's avatar
Matthias Braun committed
122
			tarval_set_wrap_on_overflow(old_wrap_on_overflow);
Matthias Braun's avatar
Matthias Braun committed
123
124
125
126
127
128
129
130
131

			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
132
		}
133
		break;
Jonas Fietz's avatar
Jonas Fietz committed
134
	}
Jonas Fietz's avatar
Jonas Fietz committed
135

Jonas Fietz's avatar
Jonas Fietz committed
136
	case iro_Sub: {
137
138
139
140
141
142
		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
143
144
		const vrp_attr *vrp_left  = vrp_get_or_set_info(info, left);
		const vrp_attr *vrp_right = vrp_get_or_set_info(info, right);
145

Matthias Braun's avatar
Matthias Braun committed
146
147
148
149
		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
150
151
152
			return 0;
		}

Matthias Braun's avatar
Matthias Braun committed
153
154
		if (vrp_left->range_type == VRP_RANGE
		 && vrp_right->range_type == VRP_RANGE) {
Matthias Braun's avatar
Matthias Braun committed
155
156
			int old_wrap_on_overflow = tarval_get_wrap_on_overflow();
			tarval_set_wrap_on_overflow(false);
157
158
			ir_tarval *new_top = tarval_sub(vrp_left->range_top, vrp_right->range_bottom, NULL);
			ir_tarval *new_bottom = tarval_sub(vrp_left->range_bottom, vrp_right->range_top, NULL);
Matthias Braun's avatar
Matthias Braun committed
159
			tarval_set_wrap_on_overflow(old_wrap_on_overflow);
Matthias Braun's avatar
Matthias Braun committed
160
161
162
163
164
165
166
167
168

			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
169
		}
170
		break;
Jonas Fietz's avatar
Jonas Fietz committed
171
172
173
	}

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

176
177
		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
178

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

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

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

Jonas Fietz's avatar
Jonas Fietz committed
190
		/* We can only compute this if the right value is a constant*/
191
		if (is_Const(right)) {
192
193
			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
194
		}
195
		break;
Jonas Fietz's avatar
Jonas Fietz committed
196
197
198
	}

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

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

Jonas Fietz's avatar
Jonas Fietz committed
204
		/* We can only compute this if the right value is a constant*/
205
		if (is_Const(right)) {
206
207
			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
208
		}
209
		break;
Jonas Fietz's avatar
Jonas Fietz committed
210
211
212
	}

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

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

Jonas Fietz's avatar
Jonas Fietz committed
218
		/* We can only compute this if the right value is a constant*/
219
		if (is_Const(right)) {
220
221
			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
222
		}
223
		break;
Jonas Fietz's avatar
Jonas Fietz committed
224
225
226
	}

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

229
230
		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
231

232
233
234
		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
235

236
237
238
239
		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
240

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

Jonas Fietz's avatar
Jonas Fietz committed
244
	case iro_Id: {
245
		const vrp_attr *vrp_pred = vrp_get_or_set_info(info, get_Id_pred(node));
246
247
248
249
250
		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;
251
		break;
Jonas Fietz's avatar
Jonas Fietz committed
252
	}
Jonas Fietz's avatar
Jonas Fietz committed
253

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

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

266
267
268
		ir_mode *new_mode;

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

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

Jonas Fietz's avatar
Jonas Fietz committed
274
		/* The second and is needed if target type is smaller*/
275
276
		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
277
		new_bits_set = tarval_and(
278
				new_bits_not_set, tarval_convert_to(vrp_pred->bits_set, new_mode));
Jonas Fietz's avatar
Jonas Fietz committed
279

280
281
		/* 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) {
282
			vrp->range_top = vrp_pred->range_top;
Jonas Fietz's avatar
Jonas Fietz committed
283
284
		}

285
286
		/* 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) {
287
			vrp->range_bottom = vrp_pred->range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
288
		}
289
		break;
Jonas Fietz's avatar
Jonas Fietz committed
290
	}
Jonas Fietz's avatar
Jonas Fietz committed
291

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


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

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

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

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



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

367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
	/* @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
384
	/* Merge the newly calculated values with those that might already exist*/
Jonas Fietz's avatar
Jonas Fietz committed
385
	if (new_bits_set != tarval_bad) {
386
		new_bits_set = tarval_or(new_bits_set, vrp->bits_set);
387
		if (new_bits_set != vrp->bits_set) {
Matthias Braun's avatar
Matthias Braun committed
388
389
			something_changed = true;
			vrp->bits_set     = new_bits_set;
Jonas Fietz's avatar
Jonas Fietz committed
390
391
392
		}
	}
	if (new_bits_not_set != tarval_bad) {
393
		new_bits_not_set = tarval_and(new_bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
394

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

401
	if (vrp->range_type == VRP_UNDEFINED &&
Jonas Fietz's avatar
Jonas Fietz committed
402
			new_range_type != VRP_UNDEFINED) {
Matthias Braun's avatar
Matthias Braun committed
403
		something_changed = true;
404
405
406
		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
407

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

		if (new_range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
421
422
			/* if they are overlapping, cut the range.*/
			/* TODO: Maybe we can preserve more information here*/
423
424
			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
425
				something_changed = true;
426
				vrp->range_bottom = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
427

428
429
			} 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
430
431
				something_changed = true;
				vrp->range_top    = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
432
			}
433
434
435
436

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

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

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

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

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

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

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

476
	foreach_irn_out_r(n, i, succ) {
477
		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
static void dump_vrp_info(void *ctx, FILE *F, const ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
486
	(void)ctx;
487
488
489
	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*/
536
			foreach_irn_out_r(node, i, succ) {
537
				waitq_put(env->workqueue, succ);
Jonas Fietz's avatar
Jonas Fietz committed
538
539
540
			}
		}
	}
541
	del_waitq(env->workqueue);
Jonas Fietz's avatar
Jonas Fietz committed
542
543
}

544
545
546
547
548
549
550
551
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);
}

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

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

562
	if (vrp_left->range_type == VRP_RANGE && vrp_right->range_type == VRP_RANGE) {
563
564
		if (tarval_cmp(vrp_left->range_top, vrp_right->range_bottom) == ir_relation_less) {
			return ir_relation_less;
565
		}
566
567
		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
568
		}
569
	}
Jonas Fietz's avatar
Jonas Fietz committed
570

571
572
	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))) {
573
		return ir_relation_less_greater;
Jonas Fietz's avatar
Jonas Fietz committed
574
575
	}

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