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

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