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

   1 /*
   2  * File name:   ir/ana/irsimpletype.c
   3  * Purpose:     Run most simple type analyses.
   4  * Author:      Goetz Lindenmaier
   5  * Modified by:
   6  * Created:     22.8.2003
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 2003 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 /**
  13  * @file irsimpletype.c
  14  *
  15  * Runs most simple type analyses.
  16  *
  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.
  21  *
  22  * @author Goetz Lindenmaier
  23  */
  24
  25 #ifdef HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 # include "irtypeinfo.h"
  30 # include "irsimpletype.h"
  31
  32 # include "irnode_t.h"
  33 # include "irprog_t.h"
  34 # include "irgwalk.h"
  35 # include "ident.h"
  36 # include "trouts.h"
  37
  38 #define VERBOSE_UNKNOWN_TYPE(s) printf s
  39
  40 static ir_type *phi_cycle_type = NULL;
  41
  42
  43 /* ------------ Building and Removing the type information  ----------- */
  44
  45
  46 /**
  47  * init type link field so that types point to their pointers.
  48  */
  49 static void precompute_pointer_types(void) {
  50 #if 0
  51   int i;
  52   set_type_link(firm_unknown_type, firm_unknown_type);
  53   set_type_link(firm_none_type,    firm_unknown_type);
  54
  55   for (i = get_irp_n_types() - 1; i >= 0; --i)
  56     set_type_link(get_irp_type(i), (void *)firm_unknown_type);
  57
  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);
  62   }
  63 #else
  64   compute_trouts();
  65 #endif
  66 }
  67
  68 /**
  69  * Returns a pointer to type which was stored in the link field
  70  * to speed up search.
  71  */
  72 static ir_type *find_pointer_type_to (ir_type *tp) {
  73 #if 0
  74   return (ir_type *)get_type_link(tp);
  75 #else
  76   if (get_type_n_pointertypes_to(tp) > 0)
  77     return get_type_pointertype_to(tp, 0);
  78   else
  79     return firm_unknown_type;
  80 #endif
  81 }
  82
  83 static ir_type *compute_irn_type(ir_node *n);
  84
  85 /**
  86  * Try to determine a type for a Proj node.
  87  * If a type cannot be determined, return @p firm_none_type.
  88  */
  89 static ir_type *find_type_for_Proj(ir_node *n) {
  90   ir_type *tp;
  91
  92   /* Avoid nested Tuples. */
  93   ir_node *pred = skip_Tuple(get_Proj_pred(n));
  94   ir_mode *m = get_irn_mode(n);
  95
  96   if (m == mode_T  ||
  97       m == mode_BB ||
  98       m == mode_X  ||
  99       m == mode_M  ||
 100       m == mode_b    )
 101     return firm_none_type;
 102
 103   switch (get_irn_opcode(pred)) {
 104   case iro_Proj: {
 105     ir_node *pred_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");
 117     } else {
 118       VERBOSE_UNKNOWN_TYPE(("Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
 119       tp = firm_unknown_type;
 120     }
 121   } break;
 122   case iro_Start: {
 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)));
 127       break;
 128     case pn_Start_P_globals:
 129       tp = find_pointer_type_to(get_glob_type());
 130       break;
 131     case pn_Start_P_tls:
 132       tp = find_pointer_type_to(get_tls_type());
 133       break;
 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))))); */
 137       break;
 138     default:
 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;
 141     }
 142   } break;
 143   case iro_Call: {
 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)); */
 148     } else {
 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;
 151     }
 152   } break;
 153   case iro_Tuple: {
 154     tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
 155   } break;
 156   default:
 157     tp = compute_irn_type(pred);
 158   }
 159
 160   return tp;
 161 }
 162
 163 /**
 164  * Try to determine the type of a node.
 165  * If a type cannot be determined, return @p firm_none_type.
 166  */
 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;
 171
 172   /* DDMN(n); */
 173
 174   if (is_unop(n)) {
 175     a = get_unop_op(n);
 176     tp1 = compute_irn_type(a);
 177   }
 178   if (is_binop(n)) {
 179     a = get_binop_left(n);
 180     b = get_binop_right(n);
 181     tp1 = compute_irn_type(a);
 182     tp2 = compute_irn_type(b);
 183   }
 184
 185   switch (get_irn_opcode(n)) {
 186
 187   case iro_InstOf: {
 188     assert(0 && "op_InstOf not supported");
 189   } break;
 190
 191   /* has no type */
 192   case iro_Return: {
 193     /* Check returned type. */
 194     /*
 195     int i;
 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") {
 202         DDMN(n);
 203         assert(res_type == ana_res_type && "return value has wrong type");
 204       }
 205     }
 206     */
 207   }
 208   case iro_Block:
 209   case iro_Start:
 210   case iro_End:
 211   case iro_Jmp:
 212   case iro_Cond:
 213   case iro_Raise:
 214   case iro_Call:
 215   case iro_Cmp:
 216   case iro_Store:
 217   case iro_Free:
 218   case iro_Sync:
 219   case iro_Tuple:
 220   case iro_Bad:
 221   case iro_NoMem:
 222   case iro_Break:
 223   case iro_CallBegin:
 224   case iro_EndReg:
 225   case iro_EndExcept:
 226     break;
 227
 228   /* compute the type */
 229   case iro_Const:  tp = get_Const_type(n); break;
 230   case iro_SymConst:
 231     tp = get_SymConst_value_type(n); break;
 232   case iro_Sel:
 233     tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
 234   /* asymmetric binops */
 235   case iro_Shl:
 236   case iro_Shr:
 237   case iro_Shrs:
 238   case iro_Rot:
 239     tp = tp1;  break;
 240   case iro_Cast:
 241     tp = get_Cast_type(n);  break;
 242   case iro_Phi: {
 243     int i;
 244     int n_preds = get_Phi_n_preds(n);
 245
 246     if (n_preds == 0)
 247       break;
 248
 249     /* initialize this Phi */
 250     set_irn_typeinfo_type(n, phi_cycle_type);
 251
 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))
 257         break;
 258     }
 259
 260     /* find a second real type */
 261     tp2 = tp1;
 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)) {
 265         tp2 = tp1;
 266         continue;
 267       }
 268       if (tp2 != tp1) break;
 269     }
 270
 271     /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
 272
 273     if (tp1 == tp2) { tp = tp1; break; }
 274
 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)));
 278     }
 279     tp = firm_unknown_type;   /* Test for supertypes? */
 280   } break;
 281   case iro_Load: {
 282     ir_node *a = get_Load_ptr(n);
 283     if (is_Sel(a))
 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);
 289     } else {
 290       VERBOSE_UNKNOWN_TYPE(("Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
 291     }
 292   } break;
 293   case iro_Alloc:
 294     tp = find_pointer_type_to(get_Alloc_type(n));  break;
 295   case iro_Proj:
 296     tp = find_type_for_Proj(n); break;
 297   case iro_Id:
 298     tp = compute_irn_type(get_Id_pred(n)); break;
 299  case iro_Unknown:
 300     tp = firm_unknown_type;  break;
 301  case iro_Filter:
 302     assert(0 && "Filter not implemented"); break;
 303
 304   /* catch special cases with fallthrough to binop/unop cases in default. */
 305   case iro_Sub: {
 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;
 311     }
 312   } /* fall through to Add. */
 313   case iro_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))         ) {
 317       tp = tp1; break;
 318     }
 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))    ) {
 322       tp = tp2; break;
 323     }
 324     goto default_code;
 325   } break;
 326   case iro_Mul: {
 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;
 330     }
 331     goto default_code;
 332   } break;
 333   case iro_Mux: {
 334     a = get_Mux_true(n);
 335     b = get_Mux_false(n);
 336     tp1 = compute_irn_type(a);
 337     tp2 = compute_irn_type(b);
 338     if (tp1 == tp2)
 339       tp = tp1;
 340   } break;
 341   case iro_Psi: {
 342     int i, n_conds = get_Psi_n_conds(n);
 343     tp1 = compute_irn_type(get_Psi_default(n));
 344
 345     for (i = 0; i < n_conds; ++i) {
 346       tp2 = compute_irn_type(get_Psi_val(n, i));
 347       if (tp2 != tp1)
 348         break;
 349     }
 350     if (tp1 == tp2)
 351       tp = tp1;
 352   } break;
 353   case iro_Bound:
 354     tp = compute_irn_type(get_Bound_index(n));
 355     break;
 356   case iro_Confirm:
 357     tp = compute_irn_type(get_Confirm_value(n));
 358     break;
 359   case iro_Conv:
 360     /* Conv is a unop, but changing the mode implies
 361        changing the type. */
 362     break;
 363
 364   default:
 365 default_code: {
 366
 367     if (is_unop(n)) {
 368       /* It's not proper to walk past a Conv, so this case is handled above. */
 369       tp = tp1;
 370       break;
 371     }
 372
 373     if (is_binop(n)) {
 374       if (tp1 == tp2) {
 375               tp = tp1;
 376               break;
 377       }
 378       if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
 379               tp = phi_cycle_type;
 380               break;
 381       }
 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)));
 385       }
 386       tp = firm_unknown_type;
 387       break;
 388     }
 389
 390     printf(" not implemented: "); DDMN(n);
 391   } break; /* default */
 392   } /* end switch */
 393
 394   /* printf (" found %s ", get_type_name(tp)); DDM; */
 395
 396   return tp;
 397 }
 398
 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);
 402
 403   if (tp == initial_type) {
 404     tp = find_type_for_node(n);
 405     set_irn_typeinfo_type(n, tp);
 406   }
 407
 408   /* printf (" found %s ", get_type_name(tp)); DDM; */
 409
 410   return tp;
 411 }
 412
 413 /**
 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.
 418  */
 419 static void compute_type(ir_node *n, void *env) {
 420
 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);
 425   }
 426   compute_irn_type(n);
 427 }
 428
 429 /**
 430  * Compute the types for all nodes of a graph.
 431  */
 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);
 435 }
 436
 437 /**
 438  * Initialize the analysis by creating a phi_cycle_type and
 439  * computing pointer types for all class and struct types.
 440  */
 441 static void init_irsimpletype(void) {
 442   init_irtypeinfo();
 443   if (!phi_cycle_type)
 444     phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
 445   precompute_pointer_types();
 446 }
 447
 448 /* Computes type information for each node in all ir graphs. */
 449 void simple_analyse_types(void) {
 450   int i;
 451   init_irsimpletype();
 452   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 453     ir_graph *irg = get_irp_irg(i);
 454     analyse_irg(irg);
 455   }
 456   set_irp_typeinfo_state(ir_typeinfo_consistent);
 457 }
 458
 459 void free_simple_type_information(void) {
 460   free_irtypeinfo();
 461
 462   if (phi_cycle_type) {
 463     free_type(phi_cycle_type);
 464     phi_cycle_type = NULL;
 465   }
 466   set_irp_typeinfo_state(ir_typeinfo_none);
 467 }