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