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 # include "irtypeinfo.h"
  26 # include "irsimpletype.h"
  27
  28 # include "irnode_t.h"
  29 # include "irprog_t.h"
  30 # include "irgwalk.h"
  31 # include "ident.h"
  32
  33 #define VERBOSE_UNKNOWN_TYPE(s) printf s
  34
  35 static type *phi_cycle_type = NULL;
  36
  37
  38 /* ------------ Building and Removing the type information  ----------- */
  39
  40
  41 /* init type link field so that types point to their pointers. */
  42 void precompute_pointer_types(void) {
  43   int i;
  44   set_type_link(firm_unknown_type, firm_unknown_type);
  45   set_type_link(firm_none_type,    firm_unknown_type);
  46   for (i = 0; i < get_irp_n_types(); ++i)
  47     set_type_link(get_irp_type(i), (void *)firm_unknown_type);
  48   for (i = get_irp_n_types()-1; i>=0; --i) {
  49     type *tp = get_irp_type(i);
  50     if (is_Pointer_type(tp))
  51       set_type_link(get_pointer_points_to_type(tp), (void *)tp);
  52   }
  53 }
  54
  55 /* Store pointer in link to speed up search of pointer type. */
  56 static type *find_pointer_type_to (type *tp) {
  57   return (type *)get_type_link(tp);
  58 }
  59
  60 static type* compute_irn_type(ir_node *n);
  61
  62 static type *find_type_for_Proj(ir_node *n) {
  63   type *tp;
  64
  65   /* Avoid nested Tuples. */
  66   ir_node *pred = skip_Tuple(get_Proj_pred(n));
  67   ir_mode *m = get_irn_mode(n);
  68
  69   if (m == mode_T  ||
  70       m == mode_BB ||
  71       m == mode_X  ||
  72       m == mode_M  ||
  73       m == mode_b    )
  74     return firm_none_type;
  75
  76   switch (get_irn_opcode(pred)) {
  77   case iro_Proj: {
  78     ir_node *pred_pred;
  79     /* Deal with Start / Call here: we need to know the Proj Nr. */
  80     assert(get_irn_mode(pred) == mode_T);
  81     pred_pred = get_Proj_pred(pred);
  82     if (get_irn_op(pred_pred) == op_Start)  {
  83       type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
  84       tp = get_method_param_type(mtp, get_Proj_proj(n));
  85     } else if (get_irn_op(pred_pred) == op_Call) {
  86       type *mtp = get_Call_type(pred_pred);
  87       tp = get_method_res_type(mtp, get_Proj_proj(n));
  88     } else if (get_irn_op(pred_pred) == op_Tuple) {
  89       assert(0 && "Encountered nested Tuple");
  90     } else {
  91       VERBOSE_UNKNOWN_TYPE(("Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
  92       tp = firm_unknown_type;
  93     }
  94   } break;
  95   case iro_Start: {
  96     /* globals and frame pointer */
  97     if (get_Proj_proj(n) ==  pn_Start_P_frame_base)
  98       tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
  99     else if (get_Proj_proj(n) == pn_Start_P_globals)
 100       tp = find_pointer_type_to(get_glob_type());
 101     else  if (get_Proj_proj(n) == pn_Start_P_value_arg_base) {
 102       VERBOSE_UNKNOWN_TYPE(("Value arg base proj %ld from Start: unknown type\n", get_irn_node_nr(n)));
 103       tp =  firm_unknown_type; /* find_pointer_type_to(get....(get_entity_type(get_irg_entity(get_irn_irg(pred))))); */
 104     } else {
 105       VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 106       tp = firm_unknown_type;
 107     }
 108   } break;
 109   case iro_Call: {
 110     /* value args pointer */
 111     if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
 112       VERBOSE_UNKNOWN_TYPE(("Value res base Proj %ld from Call: unknown type\n", get_irn_node_nr(n)));
 113       tp = firm_unknown_type; /* find_pointer_type_to(get....get_Call_type(pred)); */
 114     } else {
 115       VERBOSE_UNKNOWN_TYPE(("Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 116       tp = firm_unknown_type;
 117     }
 118   } break;
 119   case iro_Tuple: {
 120     tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
 121   } break;
 122   default:
 123     tp = compute_irn_type(pred);
 124   }
 125
 126   return tp;
 127 }
 128
 129 static type *find_type_for_node(ir_node *n) {
 130   type *tp = NULL;
 131   type *tp1 = NULL, *tp2 = NULL;
 132   ir_node *a = NULL, *b = NULL;
 133
 134   /* DDMN(n); */
 135
 136   if (is_unop(n)) {
 137     a = get_unop_op(n);
 138     tp1 = compute_irn_type(a);
 139   }
 140   if (is_binop(n)) {
 141     a = get_binop_left(n);
 142     b = get_binop_right(n);
 143     tp1 = compute_irn_type(a);
 144     tp2 = compute_irn_type(b);
 145   }
 146
 147   switch(get_irn_opcode(n)) {
 148
 149   case iro_InstOf: {
 150     assert(0 && "op_InstOf not supported");
 151   } break;
 152
 153   /* has no type */
 154   case iro_Return: {
 155     /* Check returned type. */
 156     /*
 157     int i;
 158     type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
 159     for (i = 0; i < get_method_n_ress(meth_type); i++) {
 160       type *res_type = get_method_res_type(meth_type, i);
 161       type *ana_res_type = get_irn_type(get_Return_res(n, i));
 162       if (ana_res_type == firm_unknown_type) continue;
 163       if (res_type != ana_res_type && "return value has wrong type") {
 164         DDMN(n);
 165         assert(res_type == ana_res_type && "return value has wrong type");
 166       }
 167     }
 168     */
 169   }
 170   case iro_Block:
 171   case iro_Start:
 172   case iro_End:
 173   case iro_Jmp:
 174   case iro_Cond:
 175   case iro_Raise:
 176   case iro_Call:
 177   case iro_Cmp:
 178   case iro_Store:
 179   case iro_Free:
 180   case iro_Sync:
 181   case iro_Tuple:
 182   case iro_Bad:
 183   case iro_NoMem:
 184   case iro_Break:
 185   case iro_CallBegin:
 186   case iro_EndReg:
 187   case iro_EndExcept:
 188     tp = firm_none_type; break;
 189
 190   /* compute the type */
 191   case iro_Const:  tp = get_Const_type(n); break;
 192   case iro_SymConst:
 193     tp = get_SymConst_value_type(n); break;
 194   case iro_Sel:
 195     tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
 196   /* asymmetric binops */
 197   case iro_Shl:
 198   case iro_Shr:
 199   case iro_Shrs:
 200   case iro_Rot:
 201     tp = tp1;  break;
 202   case iro_Cast:
 203     tp = get_Cast_type(n);  break;
 204   case iro_Phi: {
 205     int i;
 206     int n_preds = get_Phi_n_preds(n);
 207
 208     if (n_preds == 0)  {tp = firm_none_type; break; }
 209
 210     /* initialize this Phi */
 211     set_irn_typeinfo_type(n, phi_cycle_type);
 212
 213     /* find a first real type */
 214     for (i = 0; i < n_preds; ++i) {
 215       tp1 = compute_irn_type(get_Phi_pred(n, i));
 216       assert(tp1 != initial_type);
 217       if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
 218         break;
 219     }
 220
 221     /* find a second real type */
 222     tp2 = tp1;
 223     for (; (i < n_preds); ++i) {
 224       tp2 = compute_irn_type(get_Phi_pred(n, i));
 225       if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
 226         tp2 = tp1;
 227         continue;
 228       }
 229       if (tp2 != tp1) break;
 230     }
 231
 232     /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
 233
 234     if (tp1 == tp2) { tp = tp1; break; }
 235
 236     if (get_firm_verbosity() > 55) {  // Do not commit 55! should be 1.
 237       VERBOSE_UNKNOWN_TYPE(("Phi %ld with two different types: %s, %s: unknown type.\n", get_irn_node_nr(n),
 238                             get_type_name(tp1), get_type_name(tp2)));
 239     }
 240     tp = firm_unknown_type;   /* Test for supertypes? */
 241   } break;
 242   case iro_Load: {
 243     ir_node *a = get_Load_ptr(n);
 244     if (get_irn_op(a) == op_Sel)
 245       tp = get_entity_type(get_Sel_entity(a));
 246     else if (is_Pointer_type(compute_irn_type(a))) {
 247       tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
 248       if (is_Array_type(tp)) tp = get_array_element_type(tp);
 249     } else {
 250       VERBOSE_UNKNOWN_TYPE(("Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
 251       tp = firm_unknown_type;
 252     }
 253   } break;
 254   case iro_Alloc:
 255     tp = find_pointer_type_to(get_Alloc_type(n));  break;
 256   case iro_Proj:
 257     tp = find_type_for_Proj(n); break;
 258   case iro_Id:
 259     tp = compute_irn_type(get_Id_pred(n)); break;
 260  case iro_Unknown:
 261     tp = firm_unknown_type;  break;
 262  case iro_Filter:
 263     assert(0 && "Filter not implemented"); break;
 264
 265   /* catch special cases with fallthrough to binop/unop cases in default. */
 266   case iro_Sub: {
 267     if (mode_is_int(get_irn_mode(n))       &&
 268         mode_is_reference(get_irn_mode(a)) &&
 269         mode_is_reference(get_irn_mode(b))   ) {
 270       VERBOSE_UNKNOWN_TYPE(("Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
 271       tp =  firm_unknown_type; break;
 272     }
 273   } /* fall through to Add. */
 274   case iro_Add: {
 275     if (mode_is_reference(get_irn_mode(n)) &&
 276         mode_is_reference(get_irn_mode(a)) &&
 277         mode_is_int(get_irn_mode(b))         ) {
 278       tp = tp1; break;
 279     }
 280     if (mode_is_reference(get_irn_mode(n)) &&
 281         mode_is_int(get_irn_mode(a))       &&
 282         mode_is_reference(get_irn_mode(b))    ) {
 283       tp = tp2; break;
 284     }
 285     goto default_code;
 286   } break;
 287   case iro_Mul: {
 288     if (get_irn_mode(n) != get_irn_mode(a)) {
 289       VERBOSE_UNKNOWN_TYPE(("Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
 290       tp = firm_unknown_type; break;
 291     }
 292     goto default_code;
 293   } break;
 294   case iro_Mux: {
 295     a = get_Mux_true(n);
 296     b = get_Mux_false(n);
 297     tp1 = compute_irn_type(a);
 298     tp2 = compute_irn_type(b);
 299     if (tp1 == tp2)
 300       tp = tp1;
 301     else
 302       tp = firm_unknown_type;
 303   } break;
 304
 305   default:
 306   default_code: {
 307
 308     if (is_unop(n)) {
 309       /* Is is proper to walk past a Conv??? */
 310       tp = tp1;
 311       break;
 312     }
 313
 314     if (is_binop(n)) {
 315       if (tp1 == tp2) {
 316               tp = tp1;
 317               break;
 318       }
 319       if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
 320               tp = phi_cycle_type;
 321               break;
 322       }
 323       if (get_firm_verbosity() > 55) {
 324         VERBOSE_UNKNOWN_TYPE(("Binop %ld with two different types: %s, %s: unknown type \n", get_irn_node_nr(n),
 325                               get_type_name(tp1), get_type_name(tp2)));
 326       }
 327       tp = firm_unknown_type;
 328       break;
 329     }
 330
 331     printf(" not implemented: "); DDMN(n);
 332   } break; /* default */
 333   } /* end switch */
 334
 335   /* printf (" found %s ", get_type_name(tp)); DDM; */
 336
 337   return tp;
 338 }
 339
 340
 341 static type* compute_irn_type(ir_node *n) {
 342   type *tp = get_irn_typeinfo_type(n);
 343
 344   if (tp == initial_type) {
 345     tp = find_type_for_node(n);
 346     set_irn_typeinfo_type(n, tp);
 347   }
 348
 349   /* printf (" found %s ", get_type_name(tp)); DDM; */
 350
 351   return tp;
 352 }
 353
 354 static void compute_type(ir_node *n, void *env) {
 355
 356   type *tp = get_irn_typeinfo_type(n);
 357   if (tp ==  phi_cycle_type) {
 358     /* printf(" recomputing for phi_cycle_type "); DDMN(n); */
 359     set_irn_typeinfo_type(n, initial_type);
 360   }
 361
 362   compute_irn_type(n);
 363 }
 364
 365 static void analyse_irg (ir_graph *irg) {
 366   set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
 367   irg_walk_graph(irg, NULL, compute_type, NULL);
 368 }
 369
 370 static void init_irsimpletype(void) {
 371   init_irtypeinfo();
 372   if (!phi_cycle_type)
 373     phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
 374   precompute_pointer_types();
 375 }
 376
 377 void simple_analyse_types(void) {
 378   int i;
 379   init_irsimpletype();
 380   for (i = 0; i < get_irp_n_irgs(); i++) {
 381     current_ir_graph = get_irp_irg(i);
 382     analyse_irg(current_ir_graph);
 383   }
 384   set_irp_typeinfo_state(ir_typeinfo_consistent);
 385 }
 386
 387 void free_simple_type_information(void) {
 388   free_irtypeinfo();
 389
 390   if (phi_cycle_type) {
 391     free_type(phi_cycle_type);
 392     phi_cycle_type = NULL;
 393   }
 394   set_irp_typeinfo_state(ir_typeinfo_none);
 395 }