irsimpletype.c 11.4 KB
Newer Older
Michael Beck's avatar
Michael Beck committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
 *
 * This file is part of libFirm.
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * 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.
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
14
 *
Matthias Braun's avatar
Matthias Braun committed
15
16
17
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
18
19
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
/**
 * @file
 * @brief     Run most simple type analyses.
 * @author    Goetz Lindenmaier
 * @date      22.8.2003
 * @version   $Id$
yb9976's avatar
yb9976 committed
26
 * @brief
Matthias Braun's avatar
Matthias Braun committed
27
28
29
30
31
32
33
 *  Runs most simple type analyses.
 *
 *  We compute type information for each node.  It is derived from the
 *  types of the origines of values, e.g. parameter types can be derived
 *  from the method type.
 *  The type information so far is saved in the link field.
 */
Matthias Braun's avatar
Matthias Braun committed
34
#include "config.h"
35

Matthias Braun's avatar
Matthias Braun committed
36
37
#include "irtypeinfo.h"
#include "irsimpletype.h"
38

Matthias Braun's avatar
Matthias Braun committed
39
40
41
42
43
#include "irnode_t.h"
#include "irprog_t.h"
#include "irgwalk.h"
#include "ident.h"
#include "trouts.h"
44
#include "debug.h"
45
#include "error.h"
46

47
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
48

49
static ir_type *phi_cycle_type = NULL;
50
51
52
53
54


/* ------------ Building and Removing the type information  ----------- */


Michael Beck's avatar
Michael Beck committed
55
56
57
/**
 * init type link field so that types point to their pointers.
 */
58
59
static void precompute_pointer_types(void)
{
60
#if 0
61
62
63
64
65
66
67
68
69
70
71
72
	int i;
	set_type_link(firm_unknown_type, firm_unknown_type);
	set_type_link(firm_none_type,    firm_unknown_type);

	for (i = get_irp_n_types() - 1; i >= 0; --i)
		set_type_link(get_irp_type(i), (void *)firm_unknown_type);

	for (i = get_irp_n_types() - 1; i >= 0; --i) {
		ir_type *tp = get_irp_type(i);
		if (is_Pointer_type(tp))
			set_type_link(get_pointer_points_to_type(tp), (void *)tp);
	}
73
#else
74
	compute_trouts();
75
#endif
76
77
}

Michael Beck's avatar
Michael Beck committed
78
79
80
81
/**
 * Returns a pointer to type which was stored in the link field
 * to speed up search.
 */
82
83
static ir_type *find_pointer_type_to (ir_type *tp)
{
84
#if 0
85
	return (ir_type *)get_type_link(tp);
86
#else
87
88
89
90
	if (get_type_n_pointertypes_to(tp) > 0)
		return get_type_pointertype_to(tp, 0);
	else
		return firm_unknown_type;
91
#endif
92
93
}

94
static ir_type *compute_irn_type(ir_node *n);
95

96
97
98
99
/**
 * Try to determine a type for a Proj node.
 * If a type cannot be determined, return @p firm_none_type.
 */
100
101
static ir_type *find_type_for_Proj(ir_node *n)
{
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
	ir_type *tp;

	/* Avoid nested Tuples. */
	ir_node *pred = skip_Tuple(get_Proj_pred(n));
	ir_mode *m = get_irn_mode(n);

	if (m == mode_T  ||
	    m == mode_BB ||
	    m == mode_X  ||
	    m == mode_M  ||
	    m == mode_b    )
		return firm_none_type;

	switch (get_irn_opcode(pred)) {
	case iro_Proj: {
		ir_node *pred_pred;
		/* Deal with Start / Call here: we need to know the Proj Nr. */
		assert(get_irn_mode(pred) == mode_T);
		pred_pred = get_Proj_pred(pred);
121
		if (is_Start(pred_pred))  {
122
123
			ir_type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
			tp = get_method_param_type(mtp, get_Proj_proj(n));
124
		} else if (is_Call(pred_pred)) {
125
126
			ir_type *mtp = get_Call_type(pred_pred);
			tp = get_method_res_type(mtp, get_Proj_proj(n));
127
		} else if (is_Tuple(pred_pred)) {
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
			panic("Encountered nested Tuple");
		} else {
			DB((dbg, SET_LEVEL_1, "Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
			tp = firm_unknown_type;
		}
		break;
	}
	case iro_Start:
		/* frame pointer, globals and tls */
		switch (get_Proj_proj(n)) {
		case pn_Start_P_frame_base:
			tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
			break;
		case pn_Start_P_tls:
			tp = find_pointer_type_to(get_tls_type());
			break;
		default:
			DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
			tp = firm_unknown_type;
		}
		break;
	case iro_Call:
		/* value args pointer */
		if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
			DB((dbg, SET_LEVEL_1, "Value res base Proj %ld from Call: unknown type\n", get_irn_node_nr(n)));
			tp = firm_unknown_type; /* find_pointer_type_to(get....get_Call_type(pred)); */
		} else {
			DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
			tp = firm_unknown_type;
		}
		break;
	case iro_Tuple:
		tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
		break;
	default:
		tp = compute_irn_type(pred);
	}

	return tp;
167
168
}

Michael Beck's avatar
Michael Beck committed
169
170
171
172
/**
 * Try to determine the type of a node.
 * If a type cannot be determined, return @p firm_none_type.
 */
173
174
static ir_type *find_type_for_node(ir_node *n)
{
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
	ir_type *tp = firm_unknown_type;
	ir_type *tp1 = NULL, *tp2 = NULL;
	ir_node *a = NULL, *b = NULL;

	if (is_unop(n)) {
		a = get_unop_op(n);
		tp1 = compute_irn_type(a);
	}
	if (is_binop(n)) {
		a = get_binop_left(n);
		b = get_binop_right(n);
		tp1 = compute_irn_type(a);
		tp2 = compute_irn_type(b);
	}

	switch (get_irn_opcode(n)) {

192
	case iro_InstOf:
193
		assert(0 && "op_InstOf not supported");
194
		break;
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

		/* has no type */
	case iro_Return: {
		/* Check returned type. */
		/*
		int i;
		ir_type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
		for (i = 0; i < get_method_n_ress(meth_type); i++) {
		ir_type *res_type = get_method_res_type(meth_type, i);
		ir_type *ana_res_type = get_irn_type(get_Return_res(n, i));
		if (ana_res_type == firm_unknown_type) continue;
		if (res_type != ana_res_type && "return value has wrong type") {
		DDMN(n);
		assert(res_type == ana_res_type && "return value has wrong type");
		}
		}
		*/
	}
	case iro_Block:
	case iro_Start:
	case iro_End:
	case iro_Jmp:
	case iro_Cond:
	case iro_Raise:
	case iro_Call:
	case iro_Cmp:
	case iro_Store:
	case iro_Free:
	case iro_Sync:
	case iro_Tuple:
	case iro_Bad:
	case iro_NoMem:
	case iro_Break:
	case iro_CallBegin:
	case iro_EndReg:
	case iro_EndExcept:
		break;

		/* compute the type */
234
235
236
	case iro_Const:
	     	tp = get_Const_type(n);
		break;
237
	case iro_SymConst:
238
239
		tp = get_SymConst_value_type(n);
		break;
240
	case iro_Sel:
241
242
243
		tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n)));
		break;

244
245
246
247
		/* asymmetric binops */
	case iro_Shl:
	case iro_Shr:
	case iro_Shrs:
248
	case iro_Rotl:
249
250
		tp = tp1;
		break;
251
	case iro_Cast:
252
253
		tp = get_Cast_type(n);
		break;
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
	case iro_Phi: {
		int i;
		int n_preds = get_Phi_n_preds(n);

		if (n_preds == 0)
			break;

		/* initialize this Phi */
		set_irn_typeinfo_type(n, phi_cycle_type);

		/* find a first real type */
		for (i = 0; i < n_preds; ++i) {
			tp1 = compute_irn_type(get_Phi_pred(n, i));
			assert(tp1 != initial_type);
			if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
				break;
		}

		/* find a second real type */
		tp2 = tp1;
		for (; (i < n_preds); ++i) {
			tp2 = compute_irn_type(get_Phi_pred(n, i));
			if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
				tp2 = tp1;
				continue;
			}
			if (tp2 != tp1) break;
		}

		/* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */

		if (tp1 == tp2) { tp = tp1; break; }

287
		DB((dbg, SET_LEVEL_2, "Phi %ld with two different types: %+F, %+F: unknown type.\n", get_irn_node_nr(n), tp1, tp2));
288
		tp = firm_unknown_type;   /* Test for supertypes? */
289
290
		break;
	}
291
292
293
294
295
296
297
298
299
300
301
302

	case iro_Load: {
		ir_node *a = get_Load_ptr(n);
		if (is_Sel(a))
			tp = get_entity_type(get_Sel_entity(a));
		else if (is_Pointer_type(compute_irn_type(a))) {
			tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
			if (is_Array_type(tp))
				tp = get_array_element_type(tp);
		} else {
			DB((dbg, SET_LEVEL_1, "Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
		}
303
304
		break;
	}
305
	case iro_Alloc:
306
307
		tp = find_pointer_type_to(get_Alloc_type(n));
		break;
308
	case iro_Proj:
309
310
		tp = find_type_for_Proj(n);
		break;
311
	case iro_Id:
312
313
		tp = compute_irn_type(get_Id_pred(n));
		break;
314
	case iro_Unknown:
315
316
		tp = firm_unknown_type;
		break;
317
	case iro_Filter:
318
319
		assert(0 && "Filter not implemented");
		break;
320
321

		/* catch special cases with fallthrough to binop/unop cases in default. */
322
	case iro_Sub:
323
324
325
326
327
328
		if (mode_is_int(get_irn_mode(n))       &&
		    mode_is_reference(get_irn_mode(a)) &&
		    mode_is_reference(get_irn_mode(b))   ) {
			DB((dbg, SET_LEVEL_1, "Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
			tp =  firm_unknown_type; break;
		}
329
330
		/* fall through to Add. */
	case iro_Add:
331
332
333
334
335
336
337
338
339
340
341
342
		if (mode_is_reference(get_irn_mode(n)) &&
		    mode_is_reference(get_irn_mode(a)) &&
		    mode_is_int(get_irn_mode(b))         ) {
			tp = tp1; break;
		}
		if (mode_is_reference(get_irn_mode(n)) &&
		    mode_is_int(get_irn_mode(a))       &&
		    mode_is_reference(get_irn_mode(b))    ) {
			tp = tp2; break;
		}
		goto default_code;

343
	case iro_Mul:
344
345
346
347
348
349
		if (get_irn_mode(n) != get_irn_mode(a)) {
			DB((dbg, SET_LEVEL_1, "Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
			tp = firm_unknown_type; break;
		}
		goto default_code;

350
	case iro_Mux:
351
352
353
354
355
356
		a = get_Mux_true(n);
		b = get_Mux_false(n);
		tp1 = compute_irn_type(a);
		tp2 = compute_irn_type(b);
		if (tp1 == tp2)
			tp = tp1;
357
		break;
358
359
360
361
362
363
364
365
366
367
368
369
370

	case iro_Bound:
		tp = compute_irn_type(get_Bound_index(n));
		break;
	case iro_Confirm:
		tp = compute_irn_type(get_Confirm_value(n));
		break;
	case iro_Conv:
		/* Conv is a unop, but changing the mode implies
		changing the type. */
		break;

	default:
371
default_code:
372
373
374
375
376
377
378
379
380
381
382
		if (is_unop(n)) {
			/* It's not proper to walk past a Conv, so this case is handled above. */
			tp = tp1;
			break;
		}

		if (is_binop(n)) {
			if (tp1 == tp2) {
				tp = tp1;
				break;
			}
383
			if ((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
384
385
386
				tp = phi_cycle_type;
				break;
			}
387
			DB((dbg, SET_LEVEL_2, "Binop %ld with two different types: %+F, %+F: unknown type\n", get_irn_node_nr(n), tp1, tp2));
388
389
390
391
392
393
394
395
			tp = firm_unknown_type;
			break;
		}

		panic(" not implemented: %+F", n);
	} /* end switch */

	return tp;
396
397
}

398
/** Compute the type of an IR node. */
399
400
static ir_type *compute_irn_type(ir_node *n)
{
401
	ir_type *tp = get_irn_typeinfo_type(n);
402

403
404
405
406
407
	if (tp == initial_type) {
		tp = find_type_for_node(n);
		set_irn_typeinfo_type(n, tp);
	}
	return tp;
408
409
}

410
411
412
413
414
415
/**
 * Post-Walker: computes the type for every node
 * and store it into a map.
 * Post-walking ensures that the types for all predecessor
 * nodes are already computed.
 */
416
417
static void compute_type(ir_node *n, void *env)
{
418
419
420
421
422
423
424
	ir_type *tp = get_irn_typeinfo_type(n);
	(void) env;
	if (tp ==  phi_cycle_type) {
		/* printf(" recomputing for phi_cycle_type "); DDMN(n); */
		set_irn_typeinfo_type(n, initial_type);
	}
	compute_irn_type(n);
425
426
}

427
428
429
/**
 * Compute the types for all nodes of a graph.
 */
430
431
static void analyse_irg (ir_graph *irg)
{
432
433
	set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
	irg_walk_graph(irg, NULL, compute_type, NULL);
434
435
}

436
437
438
439
/**
 * Initialize the analysis by creating a phi_cycle_type and
 * computing pointer types for all class and struct types.
 */
440
441
static void init_irsimpletype(void)
{
442
443
444
445
	init_irtypeinfo();
	if (!phi_cycle_type)
		phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
	precompute_pointer_types();
446
447
}

448
/* Computes type information for each node in all ir graphs. */
449
450
void simple_analyse_types(void)
{
451
452
453
454
455
456
457
458
459
	int i;
	FIRM_DBG_REGISTER(dbg, "firm.ana.simpletype");

	init_irsimpletype();
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		ir_graph *irg = get_irp_irg(i);
		analyse_irg(irg);
	}
	set_irp_typeinfo_state(ir_typeinfo_consistent);
460
461
}

462
463
void free_simple_type_information(void)
{
464
	free_irtypeinfo();
465

466
467
468
469
470
	if (phi_cycle_type) {
		free_type(phi_cycle_type);
		phi_cycle_type = NULL;
	}
	set_irp_typeinfo_state(ir_typeinfo_none);
471
}