nsz Git - libfirm/blob - ir/ana/irsimpletype.c

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief     Run most simple type analyses.
  23  * @author    Goetz Lindenmaier
  24  * @date      22.8.2003
  25  * @version   $Id$
  26  * @summary
  27  *  Runs most simple type analyses.
  28  *
  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.
  33  */
  34 #ifdef HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include "irtypeinfo.h"
  39 #include "irsimpletype.h"
  40
  41 #include "irnode_t.h"
  42 #include "irprog_t.h"
  43 #include "irgwalk.h"
  44 #include "ident.h"
  45 #include "trouts.h"
  46
  47 #define VERBOSE_UNKNOWN_TYPE(s) printf s
  48
  49 static ir_type *phi_cycle_type = NULL;
  50
  51
  52 /* ------------ Building and Removing the type information  ----------- */
  53
  54
  55 /**
  56  * init type link field so that types point to their pointers.
  57  */
  58 static void precompute_pointer_types(void) {
  59 #if 0
  60   int i;
  61   set_type_link(firm_unknown_type, firm_unknown_type);
  62   set_type_link(firm_none_type,    firm_unknown_type);
  63
  64   for (i = get_irp_n_types() - 1; i >= 0; --i)
  65     set_type_link(get_irp_type(i), (void *)firm_unknown_type);
  66
  67   for (i = get_irp_n_types() - 1; i >= 0; --i) {
  68     ir_type *tp = get_irp_type(i);
  69     if (is_Pointer_type(tp))
  70       set_type_link(get_pointer_points_to_type(tp), (void *)tp);
  71   }
  72 #else
  73   compute_trouts();
  74 #endif
  75 }
  76
  77 /**
  78  * Returns a pointer to type which was stored in the link field
  79  * to speed up search.
  80  */
  81 static ir_type *find_pointer_type_to (ir_type *tp) {
  82 #if 0
  83   return (ir_type *)get_type_link(tp);
  84 #else
  85   if (get_type_n_pointertypes_to(tp) > 0)
  86     return get_type_pointertype_to(tp, 0);
  87   else
  88     return firm_unknown_type;
  89 #endif
  90 }
  91
  92 static ir_type *compute_irn_type(ir_node *n);
  93
  94 /**
  95  * Try to determine a type for a Proj node.
  96  * If a type cannot be determined, return @p firm_none_type.
  97  */
  98 static ir_type *find_type_for_Proj(ir_node *n) {
  99   ir_type *tp;
 100
 101   /* Avoid nested Tuples. */
 102   ir_node *pred = skip_Tuple(get_Proj_pred(n));
 103   ir_mode *m = get_irn_mode(n);
 104
 105   if (m == mode_T  ||
 106       m == mode_BB ||
 107       m == mode_X  ||
 108       m == mode_M  ||
 109       m == mode_b    )
 110     return firm_none_type;
 111
 112   switch (get_irn_opcode(pred)) {
 113   case iro_Proj: {
 114     ir_node *pred_pred;
 115     /* Deal with Start / Call here: we need to know the Proj Nr. */
 116     assert(get_irn_mode(pred) == mode_T);
 117     pred_pred = get_Proj_pred(pred);
 118     if (get_irn_op(pred_pred) == op_Start)  {
 119       ir_type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
 120       tp = get_method_param_type(mtp, get_Proj_proj(n));
 121     } else if (get_irn_op(pred_pred) == op_Call) {
 122       ir_type *mtp = get_Call_type(pred_pred);
 123       tp = get_method_res_type(mtp, get_Proj_proj(n));
 124     } else if (get_irn_op(pred_pred) == op_Tuple) {
 125       assert(0 && "Encountered nested Tuple");
 126     } else {
 127       VERBOSE_UNKNOWN_TYPE(("Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
 128       tp = firm_unknown_type;
 129     }
 130   } break;
 131   case iro_Start: {
 132     /* frame pointer, globals and tls */
 133     switch (get_Proj_proj(n)) {
 134     case pn_Start_P_frame_base:
 135       tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
 136       break;
 137     case pn_Start_P_globals:
 138       tp = find_pointer_type_to(get_glob_type());
 139       break;
 140     case pn_Start_P_tls:
 141       tp = find_pointer_type_to(get_tls_type());
 142       break;
 143     case pn_Start_P_value_arg_base:
 144       VERBOSE_UNKNOWN_TYPE(("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))))); */
 146       break;
 147     default:
 148       VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 149       tp = firm_unknown_type;
 150     }
 151   } break;
 152   case iro_Call: {
 153     /* value args pointer */
 154     if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
 155       VERBOSE_UNKNOWN_TYPE(("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)); */
 157     } else {
 158       VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 159       tp = firm_unknown_type;
 160     }
 161   } break;
 162   case iro_Tuple: {
 163     tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
 164   } break;
 165   default:
 166     tp = compute_irn_type(pred);
 167   }
 168
 169   return tp;
 170 }
 171
 172 /**
 173  * Try to determine the type of a node.
 174  * If a type cannot be determined, return @p firm_none_type.
 175  */
 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;
 180
 181   /* DDMN(n); */
 182
 183   if (is_unop(n)) {
 184     a = get_unop_op(n);
 185     tp1 = compute_irn_type(a);
 186   }
 187   if (is_binop(n)) {
 188     a = get_binop_left(n);
 189     b = get_binop_right(n);
 190     tp1 = compute_irn_type(a);
 191     tp2 = compute_irn_type(b);
 192   }
 193
 194   switch (get_irn_opcode(n)) {
 195
 196   case iro_InstOf: {
 197     assert(0 && "op_InstOf not supported");
 198   } break;
 199
 200   /* has no type */
 201   case iro_Return: {
 202     /* Check returned type. */
 203     /*
 204     int i;
 205     ir_type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
 206     for (i = 0; i < get_method_n_ress(meth_type); i++) {
 207       ir_type *res_type = get_method_res_type(meth_type, i);
 208       ir_type *ana_res_type = get_irn_type(get_Return_res(n, i));
 209       if (ana_res_type == firm_unknown_type) continue;
 210       if (res_type != ana_res_type && "return value has wrong type") {
 211         DDMN(n);
 212         assert(res_type == ana_res_type && "return value has wrong type");
 213       }
 214     }
 215     */
 216   }
 217   case iro_Block:
 218   case iro_Start:
 219   case iro_End:
 220   case iro_Jmp:
 221   case iro_Cond:
 222   case iro_Raise:
 223   case iro_Call:
 224   case iro_Cmp:
 225   case iro_Store:
 226   case iro_Free:
 227   case iro_Sync:
 228   case iro_Tuple:
 229   case iro_Bad:
 230   case iro_NoMem:
 231   case iro_Break:
 232   case iro_CallBegin:
 233   case iro_EndReg:
 234   case iro_EndExcept:
 235     break;
 236
 237   /* compute the type */
 238   case iro_Const:  tp = get_Const_type(n); break;
 239   case iro_SymConst:
 240     tp = get_SymConst_value_type(n); break;
 241   case iro_Sel:
 242     tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
 243   /* asymmetric binops */
 244   case iro_Shl:
 245   case iro_Shr:
 246   case iro_Shrs:
 247   case iro_Rot:
 248     tp = tp1;  break;
 249   case iro_Cast:
 250     tp = get_Cast_type(n);  break;
 251   case iro_Phi: {
 252     int i;
 253     int n_preds = get_Phi_n_preds(n);
 254
 255     if (n_preds == 0)
 256       break;
 257
 258     /* initialize this Phi */
 259     set_irn_typeinfo_type(n, phi_cycle_type);
 260
 261     /* find a first real type */
 262     for (i = 0; i < n_preds; ++i) {
 263       tp1 = compute_irn_type(get_Phi_pred(n, i));
 264       assert(tp1 != initial_type);
 265       if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
 266         break;
 267     }
 268
 269     /* find a second real type */
 270     tp2 = tp1;
 271     for (; (i < n_preds); ++i) {
 272       tp2 = compute_irn_type(get_Phi_pred(n, i));
 273       if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
 274         tp2 = tp1;
 275         continue;
 276       }
 277       if (tp2 != tp1) break;
 278     }
 279
 280     /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
 281
 282     if (tp1 == tp2) { tp = tp1; break; }
 283
 284     if (get_firm_verbosity() > 55) {  // Do not commit 55! should be 1.
 285       VERBOSE_UNKNOWN_TYPE(("Phi %ld with two different types: %s, %s: unknown type.\n", get_irn_node_nr(n),
 286                             get_type_name(tp1), get_type_name(tp2)));
 287     }
 288     tp = firm_unknown_type;   /* Test for supertypes? */
 289   } break;
 290   case iro_Load: {
 291     ir_node *a = get_Load_ptr(n);
 292     if (is_Sel(a))
 293       tp = get_entity_type(get_Sel_entity(a));
 294     else if (is_Pointer_type(compute_irn_type(a))) {
 295       tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
 296       if (is_Array_type(tp))
 297         tp = get_array_element_type(tp);
 298     } else {
 299       VERBOSE_UNKNOWN_TYPE(("Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
 300     }
 301   } break;
 302   case iro_Alloc:
 303     tp = find_pointer_type_to(get_Alloc_type(n));  break;
 304   case iro_Proj:
 305     tp = find_type_for_Proj(n); break;
 306   case iro_Id:
 307     tp = compute_irn_type(get_Id_pred(n)); break;
 308  case iro_Unknown:
 309     tp = firm_unknown_type;  break;
 310  case iro_Filter:
 311     assert(0 && "Filter not implemented"); break;
 312
 313   /* catch special cases with fallthrough to binop/unop cases in default. */
 314   case iro_Sub: {
 315     if (mode_is_int(get_irn_mode(n))       &&
 316       mode_is_reference(get_irn_mode(a)) &&
 317       mode_is_reference(get_irn_mode(b))   ) {
 318       VERBOSE_UNKNOWN_TYPE(("Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
 319       tp =  firm_unknown_type; break;
 320     }
 321   } /* fall through to Add. */
 322   case iro_Add: {
 323     if (mode_is_reference(get_irn_mode(n)) &&
 324         mode_is_reference(get_irn_mode(a)) &&
 325         mode_is_int(get_irn_mode(b))         ) {
 326       tp = tp1; break;
 327     }
 328     if (mode_is_reference(get_irn_mode(n)) &&
 329         mode_is_int(get_irn_mode(a))       &&
 330         mode_is_reference(get_irn_mode(b))    ) {
 331       tp = tp2; break;
 332     }
 333     goto default_code;
 334   } break;
 335   case iro_Mul: {
 336     if (get_irn_mode(n) != get_irn_mode(a)) {
 337       VERBOSE_UNKNOWN_TYPE(("Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
 338       tp = firm_unknown_type; break;
 339     }
 340     goto default_code;
 341   } break;
 342   case iro_Mux: {
 343     a = get_Mux_true(n);
 344     b = get_Mux_false(n);
 345     tp1 = compute_irn_type(a);
 346     tp2 = compute_irn_type(b);
 347     if (tp1 == tp2)
 348       tp = tp1;
 349   } break;
 350   case iro_Psi: {
 351     int i, n_conds = get_Psi_n_conds(n);
 352     tp1 = compute_irn_type(get_Psi_default(n));
 353
 354     for (i = 0; i < n_conds; ++i) {
 355       tp2 = compute_irn_type(get_Psi_val(n, i));
 356       if (tp2 != tp1)
 357         break;
 358     }
 359     if (tp1 == tp2)
 360       tp = tp1;
 361   } break;
 362   case iro_Bound:
 363     tp = compute_irn_type(get_Bound_index(n));
 364     break;
 365   case iro_Confirm:
 366     tp = compute_irn_type(get_Confirm_value(n));
 367     break;
 368   case iro_Conv:
 369     /* Conv is a unop, but changing the mode implies
 370        changing the type. */
 371     break;
 372
 373   default:
 374 default_code: {
 375
 376     if (is_unop(n)) {
 377       /* It's not proper to walk past a Conv, so this case is handled above. */
 378       tp = tp1;
 379       break;
 380     }
 381
 382     if (is_binop(n)) {
 383       if (tp1 == tp2) {
 384               tp = tp1;
 385               break;
 386       }
 387       if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
 388               tp = phi_cycle_type;
 389               break;
 390       }
 391       if (get_firm_verbosity() > 55) {
 392         VERBOSE_UNKNOWN_TYPE(("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       }
 395       tp = firm_unknown_type;
 396       break;
 397     }
 398
 399     printf(" not implemented: "); DDMN(n);
 400   } break; /* default */
 401   } /* end switch */
 402
 403   /* printf (" found %s ", get_type_name(tp)); DDM; */
 404
 405   return tp;
 406 }
 407
 408 /** Compute the type of an IR node. */
 409 static ir_type *compute_irn_type(ir_node *n) {
 410   ir_type *tp = get_irn_typeinfo_type(n);
 411
 412   if (tp == initial_type) {
 413     tp = find_type_for_node(n);
 414     set_irn_typeinfo_type(n, tp);
 415   }
 416
 417   /* printf (" found %s ", get_type_name(tp)); DDM; */
 418
 419   return tp;
 420 }
 421
 422 /**
 423  * Post-Walker: computes the type for every node
 424  * and store it into a map.
 425  * Post-walking ensures that the types for all predecessor
 426  * nodes are already computed.
 427  */
 428 static void compute_type(ir_node *n, void *env) {
 429
 430   ir_type *tp = get_irn_typeinfo_type(n);
 431   if (tp ==  phi_cycle_type) {
 432     /* printf(" recomputing for phi_cycle_type "); DDMN(n); */
 433     set_irn_typeinfo_type(n, initial_type);
 434   }
 435   compute_irn_type(n);
 436 }
 437
 438 /**
 439  * Compute the types for all nodes of a graph.
 440  */
 441 static void analyse_irg (ir_graph *irg) {
 442   set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
 443   irg_walk_graph(irg, NULL, compute_type, NULL);
 444 }
 445
 446 /**
 447  * Initialize the analysis by creating a phi_cycle_type and
 448  * computing pointer types for all class and struct types.
 449  */
 450 static void init_irsimpletype(void) {
 451   init_irtypeinfo();
 452   if (!phi_cycle_type)
 453     phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
 454   precompute_pointer_types();
 455 }
 456
 457 /* Computes type information for each node in all ir graphs. */
 458 void simple_analyse_types(void) {
 459   int i;
 460   init_irsimpletype();
 461   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 462     ir_graph *irg = get_irp_irg(i);
 463     analyse_irg(irg);
 464   }
 465   set_irp_typeinfo_state(ir_typeinfo_consistent);
 466 }
 467
 468 void free_simple_type_information(void) {
 469   free_irtypeinfo();
 470
 471   if (phi_cycle_type) {
 472     free_type(phi_cycle_type);
 473     phi_cycle_type = NULL;
 474   }
 475   set_irp_typeinfo_state(ir_typeinfo_none);
 476 }