2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Run most simple type analyses.
23 * @author Goetz Lindenmaier
27 * Runs most simple type analyses.
29 * We compute type information for each node. It is derived from the
30 * types of the origines of values, e.g. parameter types can be derived
31 * from the method type.
32 * The type information so far is saved in the link field.
38 #include "irtypeinfo.h"
39 #include "irsimpletype.h"
49 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
51 static ir_type *phi_cycle_type = NULL;
54 /* ------------ Building and Removing the type information ----------- */
58 * init type link field so that types point to their pointers.
60 static void precompute_pointer_types(void) {
63 set_type_link(firm_unknown_type, firm_unknown_type);
64 set_type_link(firm_none_type, firm_unknown_type);
66 for (i = get_irp_n_types() - 1; i >= 0; --i)
67 set_type_link(get_irp_type(i), (void *)firm_unknown_type);
69 for (i = get_irp_n_types() - 1; i >= 0; --i) {
70 ir_type *tp = get_irp_type(i);
71 if (is_Pointer_type(tp))
72 set_type_link(get_pointer_points_to_type(tp), (void *)tp);
80 * Returns a pointer to type which was stored in the link field
83 static ir_type *find_pointer_type_to (ir_type *tp) {
85 return (ir_type *)get_type_link(tp);
87 if (get_type_n_pointertypes_to(tp) > 0)
88 return get_type_pointertype_to(tp, 0);
90 return firm_unknown_type;
94 static ir_type *compute_irn_type(ir_node *n);
97 * Try to determine a type for a Proj node.
98 * If a type cannot be determined, return @p firm_none_type.
100 static ir_type *find_type_for_Proj(ir_node *n) {
103 /* Avoid nested Tuples. */
104 ir_node *pred = skip_Tuple(get_Proj_pred(n));
105 ir_mode *m = get_irn_mode(n);
112 return firm_none_type;
114 switch (get_irn_opcode(pred)) {
117 /* Deal with Start / Call here: we need to know the Proj Nr. */
118 assert(get_irn_mode(pred) == mode_T);
119 pred_pred = get_Proj_pred(pred);
120 if (get_irn_op(pred_pred) == op_Start) {
121 ir_type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
122 tp = get_method_param_type(mtp, get_Proj_proj(n));
123 } else if (get_irn_op(pred_pred) == op_Call) {
124 ir_type *mtp = get_Call_type(pred_pred);
125 tp = get_method_res_type(mtp, get_Proj_proj(n));
126 } else if (get_irn_op(pred_pred) == op_Tuple) {
127 panic("Encountered nested Tuple");
129 DB((dbg, SET_LEVEL_1, "Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
130 tp = firm_unknown_type;
135 /* frame pointer, globals and tls */
136 switch (get_Proj_proj(n)) {
137 case pn_Start_P_frame_base:
138 tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
141 tp = find_pointer_type_to(get_tls_type());
143 case pn_Start_P_value_arg_base:
144 DB((dbg, SET_LEVEL_1, "Value arg base proj %ld from Start: unknown type\n", get_irn_node_nr(n)));
145 tp = firm_unknown_type; /* find_pointer_type_to(get....(get_entity_type(get_irg_entity(get_irn_irg(pred))))); */
148 DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
149 tp = firm_unknown_type;
153 /* value args pointer */
154 if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
155 DB((dbg, SET_LEVEL_1, "Value res base Proj %ld from Call: unknown type\n", get_irn_node_nr(n)));
156 tp = firm_unknown_type; /* find_pointer_type_to(get....get_Call_type(pred)); */
158 DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
159 tp = firm_unknown_type;
163 tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
166 tp = compute_irn_type(pred);
173 * Try to determine the type of a node.
174 * If a type cannot be determined, return @p firm_none_type.
176 static ir_type *find_type_for_node(ir_node *n) {
177 ir_type *tp = firm_unknown_type;
178 ir_type *tp1 = NULL, *tp2 = NULL;
179 ir_node *a = NULL, *b = NULL;
183 tp1 = compute_irn_type(a);
186 a = get_binop_left(n);
187 b = get_binop_right(n);
188 tp1 = compute_irn_type(a);
189 tp2 = compute_irn_type(b);
192 switch (get_irn_opcode(n)) {
195 assert(0 && "op_InstOf not supported");
200 /* Check returned type. */
203 ir_type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
204 for (i = 0; i < get_method_n_ress(meth_type); i++) {
205 ir_type *res_type = get_method_res_type(meth_type, i);
206 ir_type *ana_res_type = get_irn_type(get_Return_res(n, i));
207 if (ana_res_type == firm_unknown_type) continue;
208 if (res_type != ana_res_type && "return value has wrong type") {
210 assert(res_type == ana_res_type && "return value has wrong type");
235 /* compute the type */
236 case iro_Const: tp = get_Const_type(n); break;
238 tp = get_SymConst_value_type(n); break;
240 tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
241 /* asymmetric binops */
248 tp = get_Cast_type(n); break;
251 int n_preds = get_Phi_n_preds(n);
256 /* initialize this Phi */
257 set_irn_typeinfo_type(n, phi_cycle_type);
259 /* find a first real type */
260 for (i = 0; i < n_preds; ++i) {
261 tp1 = compute_irn_type(get_Phi_pred(n, i));
262 assert(tp1 != initial_type);
263 if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
267 /* find a second real type */
269 for (; (i < n_preds); ++i) {
270 tp2 = compute_irn_type(get_Phi_pred(n, i));
271 if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
275 if (tp2 != tp1) break;
278 /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
280 if (tp1 == tp2) { tp = tp1; break; }
282 DB((dbg, SET_LEVEL_2, "Phi %ld with two different types: %s, %s: unknown type.\n", get_irn_node_nr(n),
283 get_type_name(tp1), get_type_name(tp2)));
284 tp = firm_unknown_type; /* Test for supertypes? */
288 ir_node *a = get_Load_ptr(n);
290 tp = get_entity_type(get_Sel_entity(a));
291 else if (is_Pointer_type(compute_irn_type(a))) {
292 tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
293 if (is_Array_type(tp))
294 tp = get_array_element_type(tp);
296 DB((dbg, SET_LEVEL_1, "Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
300 tp = find_pointer_type_to(get_Alloc_type(n)); break;
302 tp = find_type_for_Proj(n); break;
304 tp = compute_irn_type(get_Id_pred(n)); break;
306 tp = firm_unknown_type; break;
308 assert(0 && "Filter not implemented"); break;
310 /* catch special cases with fallthrough to binop/unop cases in default. */
312 if (mode_is_int(get_irn_mode(n)) &&
313 mode_is_reference(get_irn_mode(a)) &&
314 mode_is_reference(get_irn_mode(b)) ) {
315 DB((dbg, SET_LEVEL_1, "Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
316 tp = firm_unknown_type; break;
318 } /* fall through to Add. */
320 if (mode_is_reference(get_irn_mode(n)) &&
321 mode_is_reference(get_irn_mode(a)) &&
322 mode_is_int(get_irn_mode(b)) ) {
325 if (mode_is_reference(get_irn_mode(n)) &&
326 mode_is_int(get_irn_mode(a)) &&
327 mode_is_reference(get_irn_mode(b)) ) {
334 if (get_irn_mode(n) != get_irn_mode(a)) {
335 DB((dbg, SET_LEVEL_1, "Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
336 tp = firm_unknown_type; break;
343 b = get_Mux_false(n);
344 tp1 = compute_irn_type(a);
345 tp2 = compute_irn_type(b);
351 int i, n_conds = get_Psi_n_conds(n);
352 tp1 = compute_irn_type(get_Psi_default(n));
354 for (i = 0; i < n_conds; ++i) {
355 tp2 = compute_irn_type(get_Psi_val(n, i));
364 tp = compute_irn_type(get_Bound_index(n));
367 tp = compute_irn_type(get_Confirm_value(n));
370 /* Conv is a unop, but changing the mode implies
371 changing the type. */
378 /* It's not proper to walk past a Conv, so this case is handled above. */
388 if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
392 DB((dbg, SET_LEVEL_2, "Binop %ld with two different types: %s, %s: unknown type \n", get_irn_node_nr(n),
393 get_type_name(tp1), get_type_name(tp2)));
394 tp = firm_unknown_type;
398 panic(" not implemented: %+F", n);
399 } break; /* default */
405 /** Compute the type of an IR node. */
406 static ir_type *compute_irn_type(ir_node *n) {
407 ir_type *tp = get_irn_typeinfo_type(n);
409 if (tp == initial_type) {
410 tp = find_type_for_node(n);
411 set_irn_typeinfo_type(n, tp);
417 * Post-Walker: computes the type for every node
418 * and store it into a map.
419 * Post-walking ensures that the types for all predecessor
420 * nodes are already computed.
422 static void compute_type(ir_node *n, void *env) {
423 ir_type *tp = get_irn_typeinfo_type(n);
425 if (tp == phi_cycle_type) {
426 /* printf(" recomputing for phi_cycle_type "); DDMN(n); */
427 set_irn_typeinfo_type(n, initial_type);
433 * Compute the types for all nodes of a graph.
435 static void analyse_irg (ir_graph *irg) {
436 set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
437 irg_walk_graph(irg, NULL, compute_type, NULL);
441 * Initialize the analysis by creating a phi_cycle_type and
442 * computing pointer types for all class and struct types.
444 static void init_irsimpletype(void) {
447 phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
448 precompute_pointer_types();
451 /* Computes type information for each node in all ir graphs. */
452 void simple_analyse_types(void) {
454 FIRM_DBG_REGISTER(dbg, "firm.ana.simpletype");
457 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
458 ir_graph *irg = get_irp_irg(i);
461 set_irp_typeinfo_state(ir_typeinfo_consistent);
464 void free_simple_type_information(void) {
467 if (phi_cycle_type) {
468 free_type(phi_cycle_type);
469 phi_cycle_type = NULL;
471 set_irp_typeinfo_state(ir_typeinfo_none);