vrp.c 18.5 KB
Newer Older
Jonas Fietz's avatar
Jonas Fietz committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
Jonas Fietz's avatar
Jonas Fietz committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * 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.
 */

/**
 * @file
 * @brief	analyze graph to provide value range information
 * @author 	Jonas Fietz
 * @version	$Id$
 */
Michael Beck's avatar
Michael Beck committed
26
#include "config.h"
Jonas Fietz's avatar
Jonas Fietz committed
27
28
29
30
31

#include "irtypes.h"
#include "vrp.h"
#include "irouts.h"
#include "irgraph_t.h"
32
#include "irgopt.h"
Jonas Fietz's avatar
Jonas Fietz committed
33
34
35
36
#include "irpass.h"
#include "irgwalk.h"
#include "iredges.h"
#include "tv.h"
37
#include "irop.h"
38
#include "pdeq.h"
39
#include "irphase_t.h"
Matthias Braun's avatar
Matthias Braun committed
40
#include "irprintf.h"
Jonas Fietz's avatar
Jonas Fietz committed
41
42
43
44
45

static char v;
static void *VISITED = &v;

struct vrp_env_t {
46
	waitq *workqueue;
Jonas Fietz's avatar
Jonas Fietz committed
47
48
};

49
50
51
52
53
static vrp_attr *get_vrp_attr(const ir_node *node)
{
	return (vrp_attr*) get_or_set_irn_phase_info(node, PHASE_VRP);
}

54
static int vrp_update_node(ir_node *node)
55
{
Jonas Fietz's avatar
Jonas Fietz committed
56
57
58
59
60
	tarval *new_bits_set = get_tarval_bad();
	tarval *new_bits_not_set = get_tarval_bad();
	tarval *new_range_bottom = get_tarval_bad();
	tarval *new_range_top = get_tarval_bad();
	enum range_types new_range_type = VRP_UNDEFINED;
61
	int something_changed = 0;
62
63
64
65
66
	vrp_attr *vrp;

	if (!mode_is_int(get_irn_mode(node))) {
		return 0; /* we don't optimize for non-int-nodes*/
	}
67

68
	ir_printf("update_vrp for %d called\n", get_irn_node_nr(node));
69
	vrp = get_vrp_attr(node);
Jonas Fietz's avatar
Jonas Fietz committed
70

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

73
	switch (get_irn_opcode(node)) {
Jonas Fietz's avatar
Jonas Fietz committed
74
75
	case iro_Const: {
		tarval *tv = get_Const_tarval(node);
Jonas Fietz's avatar
Jonas Fietz committed
76
77
78
79
80
		new_bits_set = tv;
		new_bits_not_set = tarval_not(tv);
		new_range_bottom = tv;
		new_range_top = tv;
		new_range_type = VRP_RANGE;
81
		break;
Jonas Fietz's avatar
Jonas Fietz committed
82
83
84
	}

	case iro_And: {
85
		vrp_attr *vrp_left, *vrp_right;
Jonas Fietz's avatar
Jonas Fietz committed
86
		ir_node *left, *right;
87
88
89

		left = get_And_left(node);
		right = get_And_right(node);
90
91
		vrp_left = get_vrp_attr(left);
		vrp_right = get_vrp_attr(right);
92
93
94
		new_bits_set = tarval_and(vrp_left->bits_set, vrp_right->bits_set);
		new_bits_not_set = tarval_or(vrp_left->bits_not_set, vrp_right->bits_not_set);

95
		break;
Jonas Fietz's avatar
Jonas Fietz committed
96
	}
97

Jonas Fietz's avatar
Jonas Fietz committed
98
	case iro_Add: {
Michael Beck's avatar
Michael Beck committed
99
100
		int overflow_top, overflow_bottom;
		tarval *new_top, *new_bottom;
101
		vrp_attr *vrp_left, *vrp_right;
102
103
		vrp_left = get_vrp_attr(get_Add_left(node));
		vrp_right = get_vrp_attr(get_Add_right(node));
104

105
106
107
		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
108
109
110
			return 0;
		}

111
		new_top = tarval_add(vrp_left->range_top, vrp_right->range_top);
Jonas Fietz's avatar
Jonas Fietz committed
112
		overflow_top = tarval_carry();
113
		new_bottom = tarval_add(vrp_left->range_bottom, vrp_right->range_bottom);
Jonas Fietz's avatar
Jonas Fietz committed
114
115
		overflow_bottom = tarval_carry();

116
117
		if (!overflow_top && !overflow_bottom && vrp_left->range_type == VRP_RANGE
				&&vrp_right->range_type == VRP_RANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
118
119
120
121
122
123
			new_range_bottom = new_bottom;
			new_range_top = new_top;
			new_range_type = VRP_RANGE;
		}

		if (overflow_top || overflow_bottom) {
Jonas Fietz's avatar
Jonas Fietz committed
124
			/* TODO Implement overflow handling*/
Jonas Fietz's avatar
Jonas Fietz committed
125
126
			new_range_type = VRP_UNDEFINED;
		}
127
		break;
Jonas Fietz's avatar
Jonas Fietz committed
128
	}
Jonas Fietz's avatar
Jonas Fietz committed
129

Jonas Fietz's avatar
Jonas Fietz committed
130
	case iro_Sub: {
Michael Beck's avatar
Michael Beck committed
131
132
		int overflow_top, overflow_bottom;
		tarval *new_top, *new_bottom;
133
		vrp_attr *vrp_left, *vrp_right;
134
135
		vrp_left = get_vrp_attr(get_Sub_left(node));
		vrp_right = get_vrp_attr(get_Sub_right(node));
136

137
		if (vrp_left->range_type == VRP_UNDEFINED || vrp_right->range_type ==
Jonas Fietz's avatar
Jonas Fietz committed
138
139
140
141
				VRP_UNDEFINED) {
			return 0;
		}

142
		new_top = tarval_sub(vrp_left->range_top, vrp_right->range_top, NULL);
Jonas Fietz's avatar
Jonas Fietz committed
143
		overflow_top = tarval_carry();
144
		new_bottom = tarval_sub(vrp_left->range_bottom, vrp_right->range_bottom, NULL);
Jonas Fietz's avatar
Jonas Fietz committed
145
146
		overflow_bottom = tarval_carry();

147
148
		if (!overflow_top && !overflow_bottom && vrp_left->range_type == VRP_RANGE
				&&vrp_right->range_type == VRP_RANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
149
150
151
152
153
154
			new_range_bottom = new_bottom;
			new_range_top = new_top;
			new_range_type = VRP_RANGE;
		}

		if (overflow_top || overflow_bottom) {
Jonas Fietz's avatar
Jonas Fietz committed
155
			/* TODO Implement overflow handling*/
Jonas Fietz's avatar
Jonas Fietz committed
156
		}
157
		break;
Jonas Fietz's avatar
Jonas Fietz committed
158
159
160
	}

	case iro_Or: {
161
		vrp_attr *vrp_left, *vrp_right;
Jonas Fietz's avatar
Jonas Fietz committed
162

163
164
		vrp_left = get_vrp_attr(get_Or_left(node));
		vrp_right = get_vrp_attr(get_Or_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
165

166
167
168
		new_bits_set = tarval_or(vrp_left->bits_set, vrp_right->bits_set);
		new_bits_not_set = tarval_and(vrp_left->bits_not_set, vrp_right->bits_not_set);

169
		break;
Jonas Fietz's avatar
Jonas Fietz committed
170
171
172
	}

	case iro_Rotl: {
173
174
		vrp_attr *vrp_left, *vrp_right;
		ir_node *right = get_Rotl_right(node);
Jonas Fietz's avatar
Jonas Fietz committed
175

176
177
		vrp_left = get_vrp_attr(get_Rotl_left(node));
		vrp_right = get_vrp_attr(get_Rotl_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
178

Jonas Fietz's avatar
Jonas Fietz committed
179
		/* We can only compute this if the right value is a constant*/
180
		if (is_Const(right)) {
Jonas Fietz's avatar
Jonas Fietz committed
181
			tarval *bits_set, *bits_not_set;
182
183
			bits_set = tarval_rotl(vrp_left->bits_set, get_Const_tarval(right));
			bits_not_set = tarval_rotl(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
184

185
186
			new_bits_set = tarval_or(bits_set, vrp->bits_set);
			new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
187
		}
188
		break;
Jonas Fietz's avatar
Jonas Fietz committed
189
	}
Jonas Fietz's avatar
Jonas Fietz committed
190

Jonas Fietz's avatar
Jonas Fietz committed
191
	case iro_Shl: {
192
193
		vrp_attr *vrp_left, *vrp_right;
		ir_node *right = get_Shl_right(node);
194
195
		vrp_left = get_vrp_attr(get_Shl_left(node));
		vrp_right = get_vrp_attr(get_Shl_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
196

Jonas Fietz's avatar
Jonas Fietz committed
197
		/* We can only compute this if the right value is a constant*/
198
		if (is_Const(right)) {
Jonas Fietz's avatar
Jonas Fietz committed
199
			tarval *bits_set, *bits_not_set;
200
201
202
			ir_mode *m = get_tarval_mode(vrp->bits_not_set);
			bits_set = tarval_shl(vrp_left->bits_set, get_Const_tarval(right));
			bits_not_set = tarval_shl(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
203

204
205
			new_bits_set = tarval_or(bits_set, vrp->bits_set);
			new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
206
207

			bits_not_set = tarval_not( tarval_shl(
208
										get_mode_all_one(m),
209
										get_Const_tarval(right)));
Jonas Fietz's avatar
Jonas Fietz committed
210
211
212
			new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);

		}
213
		break;
Jonas Fietz's avatar
Jonas Fietz committed
214
215
216
	}

	case iro_Shr: {
217
218
		vrp_attr *vrp_left, *vrp_right;
		ir_node *right = get_Shr_right(node);
Jonas Fietz's avatar
Jonas Fietz committed
219

220
221
		vrp_left = get_vrp_attr(get_Shr_left(node));
		vrp_right = get_vrp_attr(get_Shr_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
222

Jonas Fietz's avatar
Jonas Fietz committed
223
		/* We can only compute this if the right value is a constant*/
224
		if (is_Const(right)) {
Jonas Fietz's avatar
Jonas Fietz committed
225
			tarval *bits_set, *bits_not_set;
226
227
228
			ir_mode *m = get_tarval_mode(vrp->bits_not_set);
			bits_set = tarval_shr(vrp_left->bits_set, get_Const_tarval(right));
			bits_not_set = tarval_shr(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
229

230
231
			new_bits_set = tarval_or(bits_set, vrp->bits_set);
			new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
232
233

			bits_not_set = tarval_not( tarval_shr(
234
										get_mode_all_one(m),
235
										get_Const_tarval(right)));
Jonas Fietz's avatar
Jonas Fietz committed
236
237
			new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
		}
238
		break;
Jonas Fietz's avatar
Jonas Fietz committed
239
240
241
	}

	case iro_Shrs: {
242
243
		vrp_attr *vrp_left, *vrp_right;
		ir_node *right = get_Shrs_right(node);
Jonas Fietz's avatar
Jonas Fietz committed
244

245
246
		vrp_left = get_vrp_attr(get_Shrs_left(node));
		vrp_right = get_vrp_attr(get_Shrs_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
247

Jonas Fietz's avatar
Jonas Fietz committed
248
		/* We can only compute this if the right value is a constant*/
249
		if (is_Const(right)) {
Jonas Fietz's avatar
Jonas Fietz committed
250
			tarval *bits_set, *bits_not_set;
251
252
253
			ir_mode *m = get_tarval_mode(vrp->bits_not_set);
			bits_set = tarval_shrs(vrp_left->bits_set, get_Const_tarval(right));
			bits_not_set = tarval_shrs(vrp_left->bits_not_set, get_Const_tarval(right));
Jonas Fietz's avatar
Jonas Fietz committed
254

255
256
			new_bits_set = tarval_or(bits_set, vrp->bits_set);
			new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
257
258

			bits_not_set = tarval_not( tarval_shrs(
259
										get_mode_all_one(m),
260
										get_Const_tarval(right)));
Jonas Fietz's avatar
Jonas Fietz committed
261
262
			new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set);
		}
263
		break;
Jonas Fietz's avatar
Jonas Fietz committed
264
265
266
	}

	case iro_Eor: {
Michael Beck's avatar
Michael Beck committed
267
		tarval *bits_set, *bits_not_set;
268
		vrp_attr *vrp_left, *vrp_right;
Jonas Fietz's avatar
Jonas Fietz committed
269

270
271
		vrp_left = get_vrp_attr(get_Eor_left(node));
		vrp_right = get_vrp_attr(get_Eor_right(node));
Jonas Fietz's avatar
Jonas Fietz committed
272
273

		bits_not_set = tarval_or(
274
275
276
							tarval_and(vrp_left->bits_set, vrp_right->bits_set),
							tarval_and(vrp_left->bits_not_set,
								vrp_right->bits_not_set));
Jonas Fietz's avatar
Jonas Fietz committed
277
278

		bits_set = tarval_or(
279
280
						tarval_and(vrp_left->bits_set, vrp_right->bits_not_set),
						tarval_and(vrp_left->bits_not_set, vrp_right->bits_set));
Jonas Fietz's avatar
Jonas Fietz committed
281

282
283
		new_bits_set = tarval_or(bits_set, vrp->bits_set);
		new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
284
		break;
Jonas Fietz's avatar
Jonas Fietz committed
285
	}
Jonas Fietz's avatar
Jonas Fietz committed
286

Jonas Fietz's avatar
Jonas Fietz committed
287
	case iro_Id: {
288
		vrp_attr *vrp_pred = get_vrp_attr(get_Id_pred(node));
289
290
291
292
293
		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;
294
		break;
Jonas Fietz's avatar
Jonas Fietz committed
295
	}
Jonas Fietz's avatar
Jonas Fietz committed
296

Jonas Fietz's avatar
Jonas Fietz committed
297
	case iro_Not: {
298
		vrp_attr *vrp_pred = get_vrp_attr(get_Not_op(node));
299
300
		new_bits_set = tarval_or(vrp_pred->bits_not_set, vrp->bits_set);
		new_bits_not_set = tarval_or(vrp_pred->bits_set, vrp->bits_not_set);
301
		break;
Jonas Fietz's avatar
Jonas Fietz committed
302
	}
Jonas Fietz's avatar
Jonas Fietz committed
303

Jonas Fietz's avatar
Jonas Fietz committed
304
305
	case iro_Conv: {
		ir_node *pred = get_Conv_op(node);
306
		ir_mode *old_mode = get_irn_mode(pred);
307
		vrp_attr *vrp_pred = get_vrp_attr(pred);
Jonas Fietz's avatar
Jonas Fietz committed
308

309
		ir_mode *new_mode;
Jonas Fietz's avatar
Jonas Fietz committed
310
		tarval *bits_not_set;
311
312

		if (!mode_is_int(old_mode))
Jonas Fietz's avatar
Jonas Fietz committed
313
314
			return 0;

315
		new_mode = get_irn_mode(node);
Jonas Fietz's avatar
Jonas Fietz committed
316

Jonas Fietz's avatar
Jonas Fietz committed
317
		/* The second and is needed if target type is smaller*/
318
		bits_not_set = tarval_not(
319
							tarval_convert_to(get_mode_all_one(old_mode),
320
321
								new_mode
								));
322
323
		bits_not_set = tarval_or(bits_not_set, tarval_convert_to(vrp_pred->bits_not_set, new_mode));
		new_bits_not_set = tarval_or(bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
324
		new_bits_set = tarval_and(
325
				tarval_not(bits_not_set), tarval_convert_to(vrp_pred->bits_set, new_mode));
Jonas Fietz's avatar
Jonas Fietz committed
326

327
328
		if (tarval_cmp(vrp_pred->range_top, get_mode_max(new_mode)) == pn_Cmp_Le) {
			vrp->range_top = vrp_pred->range_top;
Jonas Fietz's avatar
Jonas Fietz committed
329
330
		}

331
332
		if (tarval_cmp(vrp_pred->range_bottom, get_mode_min(new_mode)) == pn_Cmp_Ge) {
			vrp->range_bottom = vrp_pred->range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
333
		}
334
		break;
Jonas Fietz's avatar
Jonas Fietz committed
335
	}
Jonas Fietz's avatar
Jonas Fietz committed
336

Jonas Fietz's avatar
Jonas Fietz committed
337
338
339
	case iro_Confirm: {
		pn_Cmp cmp = get_Confirm_cmp(node);
		ir_node *bound = get_Confirm_bound(node);
Jonas Fietz's avatar
Jonas Fietz committed
340
341
342
343
344
345
346
347
348
349
350

		/** @todo: Handle non-Const bounds */

		if (cmp == pn_Cmp_Lg) {
			/** @todo: Is there some way to preserve the information? */
			new_range_type = VRP_ANTIRANGE;
			if (is_Const(bound)) {
				new_range_top = get_Const_tarval(bound);
				new_range_bottom = get_Const_tarval(bound);
			}
		} else if (cmp == pn_Cmp_Le) {
351
			if (vrp->range_type == VRP_UNDEFINED) {
Jonas Fietz's avatar
Jonas Fietz committed
352
353
354
355
356
				new_range_type = VRP_RANGE;
				if (is_Const(bound)) {
					new_range_top = get_Const_tarval(bound);
				}
				new_range_bottom = get_tarval_min(get_irn_mode(node));
357
			} else if (vrp->range_type == VRP_RANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
358
				if (is_Const(bound)) {
359
					if (tarval_cmp(vrp->range_top,
Jonas Fietz's avatar
Jonas Fietz committed
360
361
362
363
364
								get_Const_tarval(bound)) == pn_Cmp_Le) {
						new_range_top = get_Const_tarval(bound);
					}
					new_range_bottom = get_tarval_min(get_irn_mode(node));

365
				} else if (vrp->range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
366
367
368
369
					/** @todo: How do we manage not to get a never ending loop? */
				}
			}
		}
370
		break;
Jonas Fietz's avatar
Jonas Fietz committed
371
	}
Jonas Fietz's avatar
Jonas Fietz committed
372

Jonas Fietz's avatar
Jonas Fietz committed
373
	case iro_Phi: {
Jonas Fietz's avatar
Jonas Fietz committed
374
		/* combine all ranges*/
375

Michael Beck's avatar
Michael Beck committed
376
377
378
379
		int num = get_Phi_n_preds(node);
		pn_Cmp cmp;
		int i;

Jonas Fietz's avatar
Jonas Fietz committed
380
		ir_node *pred = get_Phi_pred(node,0);
381
		vrp_attr *vrp_pred = get_vrp_attr(pred);
382
383
384
385
386
		new_range_top = vrp_pred->range_top;
		new_range_bottom = vrp_pred->range_bottom;
		new_range_type = vrp_pred->range_type;
		new_bits_set = vrp_pred->bits_set;
		new_bits_not_set = vrp_pred->bits_not_set;
387

Jonas Fietz's avatar
Jonas Fietz committed
388
389
390
		assert(num > 0);


391
		for (i = 1; i < num; i++) {
Jonas Fietz's avatar
Jonas Fietz committed
392
			pred = get_Phi_pred(node, i);
393
			vrp_pred = get_vrp_attr(pred);
394
			if (new_range_type == VRP_RANGE && vrp_pred->range_type ==
Jonas Fietz's avatar
Jonas Fietz committed
395
					VRP_RANGE) {
396
				cmp = tarval_cmp(new_range_top, vrp_pred->range_top);
Jonas Fietz's avatar
Jonas Fietz committed
397
				if (cmp == pn_Cmp_Lt) {
398
					new_range_top = vrp_pred->range_top;
Jonas Fietz's avatar
Jonas Fietz committed
399
				}
400
				cmp = tarval_cmp(new_range_bottom, vrp_pred->range_bottom);
Jonas Fietz's avatar
Jonas Fietz committed
401
				if (cmp == pn_Cmp_Gt) {
402
					new_range_bottom = vrp_pred->range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
403
404
				}
			} else {
405
				new_range_type = VRP_VARYING;
Jonas Fietz's avatar
Jonas Fietz committed
406
407
408
409
				break;
			}
		}

410
		break;
Jonas Fietz's avatar
Jonas Fietz committed
411
	}
412
413
414
	default:
		/* unhandled, therefore never updated */
		break;
Jonas Fietz's avatar
Jonas Fietz committed
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
	}



	/* TODO: Check, if there can be information derived from any of these:
	is_Abs(node) is_Alloc(node) is_Anchor(node) is_Borrow(node) is_Bound(node)
	is_Break(node) is_Builtin(node) is_Call(node) is_CallBegin(node)
	is_Carry(node) is_Cast(node) is_Cmp(node) is_Cond(node)
	is_CopyB(node) is_Div(node) is_DivMod(node) is_Dummy(node)
	is_End(node) is_EndExcept(node) is_EndReg(node) is_Filter(node) is_Free(node)
	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)
	is_Pin(node) is_Proj(node) is_Quot(node)
	is_Raise(node) is_Return(node) is_Sel(node) is_Start(node) is_Store(node)
	is_SymConst(node) is_Sync(node) is_Tuple(node)
	*/

Jonas Fietz's avatar
Jonas Fietz committed
432
	/* Merge the newly calculated values with those that might already exist*/
Jonas Fietz's avatar
Jonas Fietz committed
433
	if (new_bits_set != tarval_bad) {
434
435
		new_bits_set = tarval_or(new_bits_set, vrp->bits_set);
		if (tarval_cmp(new_bits_set, vrp->bits_set) != pn_Cmp_Eq) {
Jonas Fietz's avatar
Jonas Fietz committed
436
			something_changed = 1;
437
			vrp->bits_set = new_bits_set;
Jonas Fietz's avatar
Jonas Fietz committed
438
439
440
441
		}
	}

	if (new_bits_not_set != tarval_bad) {
442
		new_bits_not_set = tarval_or(new_bits_not_set, vrp->bits_not_set);
Jonas Fietz's avatar
Jonas Fietz committed
443

444
		if (tarval_cmp(new_bits_not_set, vrp->bits_not_set) != pn_Cmp_Eq) {
Jonas Fietz's avatar
Jonas Fietz committed
445
			something_changed = 1;
446
			vrp->bits_not_set = new_bits_not_set;
Jonas Fietz's avatar
Jonas Fietz committed
447
448
449
		}
	}

450
	if (vrp->range_type == VRP_UNDEFINED &&
Jonas Fietz's avatar
Jonas Fietz committed
451
452
			new_range_type != VRP_UNDEFINED) {
		something_changed = 1;
453
454
455
		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
456

457
	} else if (vrp->range_type == VRP_RANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
458
		if (new_range_type == VRP_RANGE) {
459
460
461
			if (tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Lt) {
				something_changed = 1;
				vrp->range_bottom = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
462
			}
463
			if (tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Gt) {
Jonas Fietz's avatar
Jonas Fietz committed
464
				something_changed = 1;
465
				vrp->range_top = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
466
467
468
469
			}
		}

		if (new_range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
470
471
			/* if they are overlapping, cut the range.*/
			/* TODO: Maybe we can preserve more information here*/
472
473
474
475
			if (tarval_cmp(vrp->range_bottom, new_range_top) == pn_Cmp_Gt &&
					tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Gt) {
				something_changed = 1;
				vrp->range_bottom = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
476

477
478
			} else if (tarval_cmp(vrp->range_top, new_range_bottom) == pn_Cmp_Gt &&
					tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Lt) {
Jonas Fietz's avatar
Jonas Fietz committed
479
				something_changed = 1;
480
				vrp->range_top = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
481
			}
482
483
484
485

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

Jonas Fietz's avatar
Jonas Fietz committed
486
		}
487
	} else if (vrp->range_type == VRP_ANTIRANGE) {
Jonas Fietz's avatar
Jonas Fietz committed
488
		if (new_range_type == VRP_ANTIRANGE) {
489
490
491
			if (tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Gt) {
				something_changed = 1;
				vrp->range_bottom = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
492
			}
493
			if (tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Lt) {
Jonas Fietz's avatar
Jonas Fietz committed
494
				something_changed = 1;
495
				vrp->range_top = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
496
497
498
499
			}
		}

		if (new_range_type == VRP_RANGE) {
500
501
502
			if (tarval_cmp(vrp->range_bottom, new_range_top) == pn_Cmp_Gt) {
				something_changed = 1;
				vrp->range_bottom = new_range_top;
Jonas Fietz's avatar
Jonas Fietz committed
503
			}
504
			if (tarval_cmp(vrp->range_top, new_range_bottom) == pn_Cmp_Lt) {
Jonas Fietz's avatar
Jonas Fietz committed
505
				something_changed = 1;
506
				vrp->range_top = new_range_bottom;
Jonas Fietz's avatar
Jonas Fietz committed
507
508
509
510
511
			}
		}
	}

	assert(tarval_is_null(
512
				tarval_and(vrp->bits_set, vrp->bits_not_set)));
Jonas Fietz's avatar
Jonas Fietz committed
513
514
515
	return something_changed;
}

516
static void vrp_first_pass(ir_node *n, void *e)
517
{
Jonas Fietz's avatar
Jonas Fietz committed
518
519
	ir_node *succ;
	int i;
520
	struct vrp_env_t *env = e;
Jonas Fietz's avatar
Jonas Fietz committed
521
522
523
524
525
526

	if (is_Block(n))
		return;

	set_irn_link(n, VISITED);

527
	vrp_update_node(n);
Jonas Fietz's avatar
Jonas Fietz committed
528
529
530
531

	for (i = get_irn_n_outs(n) - 1; i >=0; --i) {
		succ =  get_irn_out(n, i);
		if (get_irn_link(succ) == VISITED) {
Jonas Fietz's avatar
Jonas Fietz committed
532
			/* we found a loop*/
533
			waitq_put(env->workqueue, n);
Jonas Fietz's avatar
Jonas Fietz committed
534
535
536
537
		}
	}
}

538
539
540
static void *vrp_init_node(ir_phase *phase, const ir_node *n, void *old)
{
	ir_mode *mode;
Michael Beck's avatar
Michael Beck committed
541
542
543
	vrp_attr *vrp;

	ir_printf("initialized node nr: %d\n", get_irn_node_nr(n));
544
545
546
	if (old) {
		assert(1==0 && "init called for node already initialized");
	}
Michael Beck's avatar
Michael Beck committed
547
	vrp = phase_alloc(phase, sizeof(vrp_attr));
548
549
550
551
552
553
554
555
556
557
558
559

	memset(vrp, 0, sizeof(vrp_attr));
	/* Initialize the vrp information to default */

	mode = get_irn_mode(n);

	vrp->range_type = VRP_UNDEFINED;

	/* TODO: We might be able to optimize space usage if we do not allocate
	 * vrp space for non-int nodes. (currently caught by vrp_update_node)
	 */
	if (mode_is_int(mode)) {
Michael Beck's avatar
Michael Beck committed
560
		/* We are assuming that 0 is always represented as this modes null */
561
		vrp->valid = 1;
Michael Beck's avatar
Michael Beck committed
562
563
564
		vrp->bits_set =
		vrp->bits_not_set = get_mode_null(mode);
		vrp->range_bottom =
565
566
567
		vrp->range_top = get_tarval_top();
	} else {
		vrp->valid = 0;
Michael Beck's avatar
Michael Beck committed
568
569
570
		vrp->bits_set =
		vrp->bits_not_set =
		vrp->range_bottom =
571
572
573
574
		vrp->range_top = get_tarval_bad();
	}

	/* TODO: We might be able to set better vrp info at this time, if this is
Michael Beck's avatar
Michael Beck committed
575
	 * a node which is newly created in an already initialized irg
576
577
578
579
580
581
	 *
	 * maybe just call vrp_update_node and if it returns one, iterate over
	 * successors
	 */
	return vrp;
}
Jonas Fietz's avatar
Jonas Fietz committed
582

583
584
void set_vrp_data(ir_graph *irg)
{
585
	ir_node *succ, *node;
Jonas Fietz's avatar
Jonas Fietz committed
586
	int i;
587
588
	struct vrp_env_t *env;
	ir_phase *phase;
Jonas Fietz's avatar
Jonas Fietz committed
589

Jonas Fietz's avatar
Jonas Fietz committed
590
	assure_irg_outs(irg); /* ensure that out edges are consistent*/
591
592
593
594
595
596
	phase = irg_get_phase(irg, PHASE_VRP);
	if (phase == NULL) {
		/* this is our first run */
		phase = new_phase(irg, vrp_init_node);
		irg_register_phase(irg, PHASE_VRP, phase);
		env = phase_alloc(phase, sizeof(*env));
597
598
599
600
601
602
		phase->priv = env;
	} else {
		env = phase->priv;
	}

	env->workqueue = new_waitq();
Jonas Fietz's avatar
Jonas Fietz committed
603

604
	irg_walk_graph(irg, NULL, vrp_first_pass, env);
Jonas Fietz's avatar
Jonas Fietz committed
605

Jonas Fietz's avatar
Jonas Fietz committed
606
	/* while there are entries in the worklist, continue*/
607
608
	while (!waitq_empty(env->workqueue)) {
		node = waitq_get(env->workqueue);
609

610
		if (vrp_update_node(node)) {
611
612
613
			/* if something changed, add successors to worklist*/
			for (i = get_irn_n_outs(node) - 1; i >=0; --i) {
				succ =  get_irn_out(node, i);
614
				waitq_put(env->workqueue, node);
Jonas Fietz's avatar
Jonas Fietz committed
615
616
617
			}
		}
	}
618
	del_waitq(env->workqueue);
Jonas Fietz's avatar
Jonas Fietz committed
619
620
621
}


622
623
ir_graph_pass_t *set_vrp_pass(const char *name)
{
Jonas Fietz's avatar
Jonas Fietz committed
624
625
626
	return def_graph_pass(name ? name : "set_vrp", set_vrp_data);
}

627
pn_Cmp vrp_cmp(const ir_node *left, const ir_node *right)
628
{
629
630
631
632
633
634
	vrp_attr *vrp_left, *vrp_right;

	vrp_left = vrp_get_info(left);
	vrp_right = vrp_get_info(right);

	if (!vrp_left || !vrp_right) {
yb9976's avatar
yb9976 committed
635
636
637
		return pn_Cmp_False;
	}

638
639
	if (vrp_left->range_type == VRP_RANGE && vrp_right->range_type == VRP_RANGE) {
		if (tarval_cmp(vrp_left->range_top, vrp_right->range_bottom) == pn_Cmp_Lt) {
640
641
			return pn_Cmp_Lt;
		}
642
		if (tarval_cmp(vrp_left->range_bottom, vrp_right->range_top) == pn_Cmp_Gt) {
643
			return pn_Cmp_Gt;
Jonas Fietz's avatar
Jonas Fietz committed
644
		}
645
	}
Jonas Fietz's avatar
Jonas Fietz committed
646

647
648
	if (!tarval_is_null(tarval_and(vrp_left->bits_set, vrp_right->bits_not_set)) ||
			!tarval_is_null(tarval_and(vrp_left->bits_not_set, vrp_right->bits_set))) {
649
		return pn_Cmp_Lg;
Jonas Fietz's avatar
Jonas Fietz committed
650
	}
Jonas Fietz's avatar
Jonas Fietz committed
651
	/* TODO: We can get way more information here*/
Jonas Fietz's avatar
Jonas Fietz committed
652
653
654

	return pn_Cmp_False;
}
655

656
657
658
659
vrp_attr *vrp_get_info(const ir_node *node)
{
	const ir_graph *irg   = get_irn_irg(node);
	const ir_phase *phase = irg_get_phase(irg, PHASE_VRP);
660

661
	if (phase == NULL) {
662
663
664
665
		/* phase has not yet been initialized */
		return NULL;
	}

666
	return phase_get_irn_data(phase, node);
667
}