2 * File name: ir/ana/irsimpletype.c
3 * Purpose: Run most simple type analyses.
4 * Author: Goetz Lindenmaier
8 * Copyright: (c) 2003 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
13 * @file irsimpletype.c
15 * Runs most simple type analyses.
17 * We compute type information for each node. It is derived from the
18 * types of the origines of values, e.g. parameter types can be derived
19 * from the method type.
20 * The type information so far is saved in the link field.
22 * @author Goetz Lindenmaier
29 # include "irtypeinfo.h"
30 # include "irsimpletype.h"
32 # include "irnode_t.h"
33 # include "irprog_t.h"
38 #define VERBOSE_UNKNOWN_TYPE(s) printf s
40 static ir_type *phi_cycle_type = NULL;
43 /* ------------ Building and Removing the type information ----------- */
47 * init type link field so that types point to their pointers.
49 static void precompute_pointer_types(void) {
52 set_type_link(firm_unknown_type, firm_unknown_type);
53 set_type_link(firm_none_type, firm_unknown_type);
55 for (i = get_irp_n_types() - 1; i >= 0; --i)
56 set_type_link(get_irp_type(i), (void *)firm_unknown_type);
58 for (i = get_irp_n_types() - 1; i >= 0; --i) {
59 ir_type *tp = get_irp_type(i);
60 if (is_Pointer_type(tp))
61 set_type_link(get_pointer_points_to_type(tp), (void *)tp);
69 * Returns a pointer to type which was stored in the link field
72 static ir_type *find_pointer_type_to (ir_type *tp) {
74 return (ir_type *)get_type_link(tp);
76 if (get_type_n_pointertypes_to(tp) > 0)
77 return get_type_pointertype_to(tp, 0);
79 return firm_unknown_type;
83 static ir_type *compute_irn_type(ir_node *n);
86 * Try to determine a type for a Proj node.
87 * If a type cannot be determined, return @p firm_none_type.
89 static ir_type *find_type_for_Proj(ir_node *n) {
92 /* Avoid nested Tuples. */
93 ir_node *pred = skip_Tuple(get_Proj_pred(n));
94 ir_mode *m = get_irn_mode(n);
101 return firm_none_type;
103 switch (get_irn_opcode(pred)) {
106 /* Deal with Start / Call here: we need to know the Proj Nr. */
107 assert(get_irn_mode(pred) == mode_T);
108 pred_pred = get_Proj_pred(pred);
109 if (get_irn_op(pred_pred) == op_Start) {
110 ir_type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
111 tp = get_method_param_type(mtp, get_Proj_proj(n));
112 } else if (get_irn_op(pred_pred) == op_Call) {
113 ir_type *mtp = get_Call_type(pred_pred);
114 tp = get_method_res_type(mtp, get_Proj_proj(n));
115 } else if (get_irn_op(pred_pred) == op_Tuple) {
116 assert(0 && "Encountered nested Tuple");
118 VERBOSE_UNKNOWN_TYPE(("Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
119 tp = firm_unknown_type;
123 /* frame pointer, globals and tls */
124 switch (get_Proj_proj(n)) {
125 case pn_Start_P_frame_base:
126 tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
128 case pn_Start_P_globals:
129 tp = find_pointer_type_to(get_glob_type());
132 tp = find_pointer_type_to(get_tls_type());
134 case pn_Start_P_value_arg_base:
135 VERBOSE_UNKNOWN_TYPE(("Value arg base proj %ld from Start: unknown type\n", get_irn_node_nr(n)));
136 tp = firm_unknown_type; /* find_pointer_type_to(get....(get_entity_type(get_irg_entity(get_irn_irg(pred))))); */
139 VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
140 tp = firm_unknown_type;
144 /* value args pointer */
145 if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
146 VERBOSE_UNKNOWN_TYPE(("Value res base Proj %ld from Call: unknown type\n", get_irn_node_nr(n)));
147 tp = firm_unknown_type; /* find_pointer_type_to(get....get_Call_type(pred)); */
149 VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
150 tp = firm_unknown_type;
154 tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
157 tp = compute_irn_type(pred);
164 * Try to determine the type of a node.
165 * If a type cannot be determined, return @p firm_none_type.
167 static ir_type *find_type_for_node(ir_node *n) {
168 ir_type *tp = firm_unknown_type;
169 ir_type *tp1 = NULL, *tp2 = NULL;
170 ir_node *a = NULL, *b = NULL;
176 tp1 = compute_irn_type(a);
179 a = get_binop_left(n);
180 b = get_binop_right(n);
181 tp1 = compute_irn_type(a);
182 tp2 = compute_irn_type(b);
185 switch (get_irn_opcode(n)) {
188 assert(0 && "op_InstOf not supported");
193 /* Check returned type. */
196 ir_type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
197 for (i = 0; i < get_method_n_ress(meth_type); i++) {
198 ir_type *res_type = get_method_res_type(meth_type, i);
199 ir_type *ana_res_type = get_irn_type(get_Return_res(n, i));
200 if (ana_res_type == firm_unknown_type) continue;
201 if (res_type != ana_res_type && "return value has wrong type") {
203 assert(res_type == ana_res_type && "return value has wrong type");
228 /* compute the type */
229 case iro_Const: tp = get_Const_type(n); break;
231 tp = get_SymConst_value_type(n); break;
233 tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
234 /* asymmetric binops */
241 tp = get_Cast_type(n); break;
244 int n_preds = get_Phi_n_preds(n);
249 /* initialize this Phi */
250 set_irn_typeinfo_type(n, phi_cycle_type);
252 /* find a first real type */
253 for (i = 0; i < n_preds; ++i) {
254 tp1 = compute_irn_type(get_Phi_pred(n, i));
255 assert(tp1 != initial_type);
256 if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
260 /* find a second real type */
262 for (; (i < n_preds); ++i) {
263 tp2 = compute_irn_type(get_Phi_pred(n, i));
264 if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
268 if (tp2 != tp1) break;
271 /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
273 if (tp1 == tp2) { tp = tp1; break; }
275 if (get_firm_verbosity() > 55) { // Do not commit 55! should be 1.
276 VERBOSE_UNKNOWN_TYPE(("Phi %ld with two different types: %s, %s: unknown type.\n", get_irn_node_nr(n),
277 get_type_name(tp1), get_type_name(tp2)));
279 tp = firm_unknown_type; /* Test for supertypes? */
282 ir_node *a = get_Load_ptr(n);
284 tp = get_entity_type(get_Sel_entity(a));
285 else if (is_Pointer_type(compute_irn_type(a))) {
286 tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
287 if (is_Array_type(tp))
288 tp = get_array_element_type(tp);
290 VERBOSE_UNKNOWN_TYPE(("Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
294 tp = find_pointer_type_to(get_Alloc_type(n)); break;
296 tp = find_type_for_Proj(n); break;
298 tp = compute_irn_type(get_Id_pred(n)); break;
300 tp = firm_unknown_type; break;
302 assert(0 && "Filter not implemented"); break;
304 /* catch special cases with fallthrough to binop/unop cases in default. */
306 if (mode_is_int(get_irn_mode(n)) &&
307 mode_is_reference(get_irn_mode(a)) &&
308 mode_is_reference(get_irn_mode(b)) ) {
309 VERBOSE_UNKNOWN_TYPE(("Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
310 tp = firm_unknown_type; break;
312 } /* fall through to Add. */
314 if (mode_is_reference(get_irn_mode(n)) &&
315 mode_is_reference(get_irn_mode(a)) &&
316 mode_is_int(get_irn_mode(b)) ) {
319 if (mode_is_reference(get_irn_mode(n)) &&
320 mode_is_int(get_irn_mode(a)) &&
321 mode_is_reference(get_irn_mode(b)) ) {
327 if (get_irn_mode(n) != get_irn_mode(a)) {
328 VERBOSE_UNKNOWN_TYPE(("Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
329 tp = firm_unknown_type; break;
335 b = get_Mux_false(n);
336 tp1 = compute_irn_type(a);
337 tp2 = compute_irn_type(b);
342 int i, n_conds = get_Psi_n_conds(n);
343 tp1 = compute_irn_type(get_Psi_default(n));
345 for (i = 0; i < n_conds; ++i) {
346 tp2 = compute_irn_type(get_Psi_val(n, i));
354 tp = compute_irn_type(get_Bound_index(n));
357 tp = compute_irn_type(get_Confirm_value(n));
360 /* Conv is a unop, but changing the mode implies
361 changing the type. */
368 /* It's not proper to walk past a Conv, so this case is handled above. */
378 if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
382 if (get_firm_verbosity() > 55) {
383 VERBOSE_UNKNOWN_TYPE(("Binop %ld with two different types: %s, %s: unknown type \n", get_irn_node_nr(n),
384 get_type_name(tp1), get_type_name(tp2)));
386 tp = firm_unknown_type;
390 printf(" not implemented: "); DDMN(n);
391 } break; /* default */
394 /* printf (" found %s ", get_type_name(tp)); DDM; */
399 /** Compute the type of an IR node. */
400 static ir_type *compute_irn_type(ir_node *n) {
401 ir_type *tp = get_irn_typeinfo_type(n);
403 if (tp == initial_type) {
404 tp = find_type_for_node(n);
405 set_irn_typeinfo_type(n, tp);
408 /* printf (" found %s ", get_type_name(tp)); DDM; */
414 * Post-Walker: computes the type for every node
415 * and store it into a map.
416 * Post-walking ensures that the types for all predecessor
417 * nodes are already computed.
419 static void compute_type(ir_node *n, void *env) {
421 ir_type *tp = get_irn_typeinfo_type(n);
422 if (tp == phi_cycle_type) {
423 /* printf(" recomputing for phi_cycle_type "); DDMN(n); */
424 set_irn_typeinfo_type(n, initial_type);
430 * Compute the types for all nodes of a graph.
432 static void analyse_irg (ir_graph *irg) {
433 set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
434 irg_walk_graph(irg, NULL, compute_type, NULL);
438 * Initialize the analysis by creating a phi_cycle_type and
439 * computing pointer types for all class and struct types.
441 static void init_irsimpletype(void) {
444 phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
445 precompute_pointer_types();
448 /* Computes type information for each node in all ir graphs. */
449 void simple_analyse_types(void) {
452 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
453 ir_graph *irg = get_irp_irg(i);
456 set_irp_typeinfo_state(ir_typeinfo_consistent);
459 void free_simple_type_information(void) {
462 if (phi_cycle_type) {
463 free_type(phi_cycle_type);
464 phi_cycle_type = NULL;
466 set_irp_typeinfo_state(ir_typeinfo_none);