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