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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief     Run most simple type analyses.
  23  * @author    Goetz Lindenmaier
  24  * @date      22.8.2003
  25  * @version   $Id$
  26  * @summary
  27  *  Runs most simple type analyses.
  28  *
  29  *  We compute type information for each node.  It is derived from the
  30  *  types of the origines of values, e.g. parameter types can be derived
  31  *  from the method type.
  32  *  The type information so far is saved in the link field.
  33  */
  34 #ifdef HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include "irtypeinfo.h"
  39 #include "irsimpletype.h"
  40
  41 #include "irnode_t.h"
  42 #include "irprog_t.h"
  43 #include "irgwalk.h"
  44 #include "ident.h"
  45 #include "trouts.h"
  46 #include "debug.h"
  47 #include "error.h"
  48
  49 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
  50
  51 static ir_type *phi_cycle_type = NULL;
  52
  53
  54 /* ------------ Building and Removing the type information  ----------- */
  55
  56
  57 /**
  58  * init type link field so that types point to their pointers.
  59  */
  60 static void precompute_pointer_types(void) {
  61 #if 0
  62         int i;
  63         set_type_link(firm_unknown_type, firm_unknown_type);
  64         set_type_link(firm_none_type,    firm_unknown_type);
  65
  66         for (i = get_irp_n_types() - 1; i >= 0; --i)
  67                 set_type_link(get_irp_type(i), (void *)firm_unknown_type);
  68
  69         for (i = get_irp_n_types() - 1; i >= 0; --i) {
  70                 ir_type *tp = get_irp_type(i);
  71                 if (is_Pointer_type(tp))
  72                         set_type_link(get_pointer_points_to_type(tp), (void *)tp);
  73         }
  74 #else
  75         compute_trouts();
  76 #endif
  77 }
  78
  79 /**
  80  * Returns a pointer to type which was stored in the link field
  81  * to speed up search.
  82  */
  83 static ir_type *find_pointer_type_to (ir_type *tp) {
  84 #if 0
  85         return (ir_type *)get_type_link(tp);
  86 #else
  87         if (get_type_n_pointertypes_to(tp) > 0)
  88                 return get_type_pointertype_to(tp, 0);
  89         else
  90                 return firm_unknown_type;
  91 #endif
  92 }
  93
  94 static ir_type *compute_irn_type(ir_node *n);
  95
  96 /**
  97  * Try to determine a type for a Proj node.
  98  * If a type cannot be determined, return @p firm_none_type.
  99  */
 100 static ir_type *find_type_for_Proj(ir_node *n) {
 101         ir_type *tp;
 102
 103         /* Avoid nested Tuples. */
 104         ir_node *pred = skip_Tuple(get_Proj_pred(n));
 105         ir_mode *m = get_irn_mode(n);
 106
 107         if (m == mode_T  ||
 108             m == mode_BB ||
 109             m == mode_X  ||
 110             m == mode_M  ||
 111             m == mode_b    )
 112                 return firm_none_type;
 113
 114         switch (get_irn_opcode(pred)) {
 115         case iro_Proj: {
 116                 ir_node *pred_pred;
 117                 /* Deal with Start / Call here: we need to know the Proj Nr. */
 118                 assert(get_irn_mode(pred) == mode_T);
 119                 pred_pred = get_Proj_pred(pred);
 120                 if (get_irn_op(pred_pred) == op_Start)  {
 121                         ir_type *mtp = get_entity_type(get_irg_entity(get_irn_irg(pred_pred)));
 122                         tp = get_method_param_type(mtp, get_Proj_proj(n));
 123                 } else if (get_irn_op(pred_pred) == op_Call) {
 124                         ir_type *mtp = get_Call_type(pred_pred);
 125                         tp = get_method_res_type(mtp, get_Proj_proj(n));
 126                 } else if (get_irn_op(pred_pred) == op_Tuple) {
 127                         panic("Encountered nested Tuple");
 128                 } else {
 129                         DB((dbg, SET_LEVEL_1, "Proj %ld from Proj from ??: unknown type\n", get_irn_node_nr(n)));
 130                         tp = firm_unknown_type;
 131                 }
 132                 break;
 133         }
 134         case iro_Start:
 135                 /* frame pointer, globals and tls */
 136                 switch (get_Proj_proj(n)) {
 137                 case pn_Start_P_frame_base:
 138                         tp = find_pointer_type_to(get_irg_frame_type(get_irn_irg(pred)));
 139                         break;
 140                 case pn_Start_P_globals:
 141                         tp = find_pointer_type_to(get_glob_type());
 142                         break;
 143                 case pn_Start_P_tls:
 144                         tp = find_pointer_type_to(get_tls_type());
 145                         break;
 146                 case pn_Start_P_value_arg_base:
 147                         DB((dbg, SET_LEVEL_1, "Value arg base proj %ld from Start: unknown type\n", get_irn_node_nr(n)));
 148                         tp =  firm_unknown_type; /* find_pointer_type_to(get....(get_entity_type(get_irg_entity(get_irn_irg(pred))))); */
 149                         break;
 150                 default:
 151                         DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Start: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 152                         tp = firm_unknown_type;
 153                 }
 154                 break;
 155         case iro_Call:
 156                 /* value args pointer */
 157                 if (get_Proj_proj(n) == pn_Call_P_value_res_base) {
 158                         DB((dbg, SET_LEVEL_1, "Value res base Proj %ld from Call: unknown type\n", get_irn_node_nr(n)));
 159                         tp = firm_unknown_type; /* find_pointer_type_to(get....get_Call_type(pred)); */
 160                 } else {
 161                         DB((dbg, SET_LEVEL_1, "Proj %ld %ld from Call: unknown type\n", get_Proj_proj(n), get_irn_node_nr(n)));
 162                         tp = firm_unknown_type;
 163                 }
 164                 break;
 165         case iro_Tuple:
 166                 tp = compute_irn_type(get_Tuple_pred(pred, get_Proj_proj(n)));
 167                 break;
 168         default:
 169                 tp = compute_irn_type(pred);
 170         }
 171
 172         return tp;
 173 }
 174
 175 /**
 176  * Try to determine the type of a node.
 177  * If a type cannot be determined, return @p firm_none_type.
 178  */
 179 static ir_type *find_type_for_node(ir_node *n) {
 180         ir_type *tp = firm_unknown_type;
 181         ir_type *tp1 = NULL, *tp2 = NULL;
 182         ir_node *a = NULL, *b = NULL;
 183
 184         if (is_unop(n)) {
 185                 a = get_unop_op(n);
 186                 tp1 = compute_irn_type(a);
 187         }
 188         if (is_binop(n)) {
 189                 a = get_binop_left(n);
 190                 b = get_binop_right(n);
 191                 tp1 = compute_irn_type(a);
 192                 tp2 = compute_irn_type(b);
 193         }
 194
 195         switch (get_irn_opcode(n)) {
 196
 197         case iro_InstOf: {
 198                 assert(0 && "op_InstOf not supported");
 199         } break;
 200
 201                 /* has no type */
 202         case iro_Return: {
 203                 /* Check returned type. */
 204                 /*
 205                 int i;
 206                 ir_type *meth_type = get_entity_type(get_irg_entity(current_ir_graph));
 207                 for (i = 0; i < get_method_n_ress(meth_type); i++) {
 208                 ir_type *res_type = get_method_res_type(meth_type, i);
 209                 ir_type *ana_res_type = get_irn_type(get_Return_res(n, i));
 210                 if (ana_res_type == firm_unknown_type) continue;
 211                 if (res_type != ana_res_type && "return value has wrong type") {
 212                 DDMN(n);
 213                 assert(res_type == ana_res_type && "return value has wrong type");
 214                 }
 215                 }
 216                 */
 217         }
 218         case iro_Block:
 219         case iro_Start:
 220         case iro_End:
 221         case iro_Jmp:
 222         case iro_Cond:
 223         case iro_Raise:
 224         case iro_Call:
 225         case iro_Cmp:
 226         case iro_Store:
 227         case iro_Free:
 228         case iro_Sync:
 229         case iro_Tuple:
 230         case iro_Bad:
 231         case iro_NoMem:
 232         case iro_Break:
 233         case iro_CallBegin:
 234         case iro_EndReg:
 235         case iro_EndExcept:
 236                 break;
 237
 238                 /* compute the type */
 239         case iro_Const:  tp = get_Const_type(n); break;
 240         case iro_SymConst:
 241                 tp = get_SymConst_value_type(n); break;
 242         case iro_Sel:
 243                 tp = find_pointer_type_to(get_entity_type(get_Sel_entity(n))); break;
 244                 /* asymmetric binops */
 245         case iro_Shl:
 246         case iro_Shr:
 247         case iro_Shrs:
 248         case iro_Rot:
 249                 tp = tp1;  break;
 250         case iro_Cast:
 251                 tp = get_Cast_type(n);  break;
 252         case iro_Phi: {
 253                 int i;
 254                 int n_preds = get_Phi_n_preds(n);
 255
 256                 if (n_preds == 0)
 257                         break;
 258
 259                 /* initialize this Phi */
 260                 set_irn_typeinfo_type(n, phi_cycle_type);
 261
 262                 /* find a first real type */
 263                 for (i = 0; i < n_preds; ++i) {
 264                         tp1 = compute_irn_type(get_Phi_pred(n, i));
 265                         assert(tp1 != initial_type);
 266                         if ((tp1 != phi_cycle_type) && (tp1 != firm_none_type))
 267                                 break;
 268                 }
 269
 270                 /* find a second real type */
 271                 tp2 = tp1;
 272                 for (; (i < n_preds); ++i) {
 273                         tp2 = compute_irn_type(get_Phi_pred(n, i));
 274                         if ((tp2 == phi_cycle_type) || (tp2 == firm_none_type)) {
 275                                 tp2 = tp1;
 276                                 continue;
 277                         }
 278                         if (tp2 != tp1) break;
 279                 }
 280
 281                 /* printf("Types in Phi %s and %s \n", get_type_name(tp1), get_type_name(tp2)); */
 282
 283                 if (tp1 == tp2) { tp = tp1; break; }
 284
 285                 DB((dbg, SET_LEVEL_2, "Phi %ld with two different types: %s, %s: unknown type.\n", get_irn_node_nr(n),
 286                         get_type_name(tp1), get_type_name(tp2)));
 287                 tp = firm_unknown_type;   /* Test for supertypes? */
 288         } break;
 289
 290         case iro_Load: {
 291                 ir_node *a = get_Load_ptr(n);
 292                 if (is_Sel(a))
 293                         tp = get_entity_type(get_Sel_entity(a));
 294                 else if (is_Pointer_type(compute_irn_type(a))) {
 295                         tp = get_pointer_points_to_type(get_irn_typeinfo_type(a));
 296                         if (is_Array_type(tp))
 297                                 tp = get_array_element_type(tp);
 298                 } else {
 299                         DB((dbg, SET_LEVEL_1, "Load %ld with typeless address. result: unknown type\n", get_irn_node_nr(n)));
 300                 }
 301         } break;
 302         case iro_Alloc:
 303                 tp = find_pointer_type_to(get_Alloc_type(n));  break;
 304         case iro_Proj:
 305                 tp = find_type_for_Proj(n); break;
 306         case iro_Id:
 307                 tp = compute_irn_type(get_Id_pred(n)); break;
 308         case iro_Unknown:
 309                 tp = firm_unknown_type;  break;
 310         case iro_Filter:
 311                 assert(0 && "Filter not implemented"); break;
 312
 313                 /* catch special cases with fallthrough to binop/unop cases in default. */
 314         case iro_Sub: {
 315                 if (mode_is_int(get_irn_mode(n))       &&
 316                     mode_is_reference(get_irn_mode(a)) &&
 317                     mode_is_reference(get_irn_mode(b))   ) {
 318                         DB((dbg, SET_LEVEL_1, "Sub %ld ptr - ptr = int: unknown type\n", get_irn_node_nr(n)));
 319                         tp =  firm_unknown_type; break;
 320                 }
 321         } /* fall through to Add. */
 322         case iro_Add: {
 323                 if (mode_is_reference(get_irn_mode(n)) &&
 324                     mode_is_reference(get_irn_mode(a)) &&
 325                     mode_is_int(get_irn_mode(b))         ) {
 326                         tp = tp1; break;
 327                 }
 328                 if (mode_is_reference(get_irn_mode(n)) &&
 329                     mode_is_int(get_irn_mode(a))       &&
 330                     mode_is_reference(get_irn_mode(b))    ) {
 331                         tp = tp2; break;
 332                 }
 333                 goto default_code;
 334         } break;
 335
 336         case iro_Mul: {
 337                 if (get_irn_mode(n) != get_irn_mode(a)) {
 338                         DB((dbg, SET_LEVEL_1, "Mul %ld int1 * int1 = int2: unknown type\n", get_irn_node_nr(n)));
 339                         tp = firm_unknown_type; break;
 340                 }
 341                 goto default_code;
 342         } break;
 343
 344         case iro_Mux: {
 345                 a = get_Mux_true(n);
 346                 b = get_Mux_false(n);
 347                 tp1 = compute_irn_type(a);
 348                 tp2 = compute_irn_type(b);
 349                 if (tp1 == tp2)
 350                         tp = tp1;
 351         } break;
 352
 353         case iro_Psi: {
 354                 int i, n_conds = get_Psi_n_conds(n);
 355                 tp1 = compute_irn_type(get_Psi_default(n));
 356
 357                 for (i = 0; i < n_conds; ++i) {
 358                         tp2 = compute_irn_type(get_Psi_val(n, i));
 359                         if (tp2 != tp1)
 360                                 break;
 361                 }
 362                 if (tp1 == tp2)
 363                         tp = tp1;
 364         } break;
 365
 366         case iro_Bound:
 367                 tp = compute_irn_type(get_Bound_index(n));
 368                 break;
 369         case iro_Confirm:
 370                 tp = compute_irn_type(get_Confirm_value(n));
 371                 break;
 372         case iro_Conv:
 373                 /* Conv is a unop, but changing the mode implies
 374                 changing the type. */
 375                 break;
 376
 377         default:
 378 default_code: {
 379
 380                 if (is_unop(n)) {
 381                         /* It's not proper to walk past a Conv, so this case is handled above. */
 382                         tp = tp1;
 383                         break;
 384                 }
 385
 386                 if (is_binop(n)) {
 387                         if (tp1 == tp2) {
 388                                 tp = tp1;
 389                                 break;
 390                         }
 391                         if((tp1 == phi_cycle_type) || (tp2 == phi_cycle_type)) {
 392                                 tp = phi_cycle_type;
 393                                 break;
 394                         }
 395                         DB((dbg, SET_LEVEL_2, "Binop %ld with two different types: %s, %s: unknown type \n", get_irn_node_nr(n),
 396                                 get_type_name(tp1), get_type_name(tp2)));
 397                         tp = firm_unknown_type;
 398                         break;
 399                 }
 400
 401                 panic(" not implemented: %+F", n);
 402         } break; /* default */
 403         } /* end switch */
 404
 405         return tp;
 406 }
 407
 408 /** Compute the type of an IR node. */
 409 static ir_type *compute_irn_type(ir_node *n) {
 410         ir_type *tp = get_irn_typeinfo_type(n);
 411
 412         if (tp == initial_type) {
 413                 tp = find_type_for_node(n);
 414                 set_irn_typeinfo_type(n, tp);
 415         }
 416         return tp;
 417 }
 418
 419 /**
 420  * Post-Walker: computes the type for every node
 421  * and store it into a map.
 422  * Post-walking ensures that the types for all predecessor
 423  * nodes are already computed.
 424  */
 425 static void compute_type(ir_node *n, void *env) {
 426         ir_type *tp = get_irn_typeinfo_type(n);
 427         (void) env;
 428         if (tp ==  phi_cycle_type) {
 429                 /* printf(" recomputing for phi_cycle_type "); DDMN(n); */
 430                 set_irn_typeinfo_type(n, initial_type);
 431         }
 432         compute_irn_type(n);
 433 }
 434
 435 /**
 436  * Compute the types for all nodes of a graph.
 437  */
 438 static void analyse_irg (ir_graph *irg) {
 439         set_irg_typeinfo_state(irg, ir_typeinfo_consistent);
 440         irg_walk_graph(irg, NULL, compute_type, NULL);
 441 }
 442
 443 /**
 444  * Initialize the analysis by creating a phi_cycle_type and
 445  * computing pointer types for all class and struct types.
 446  */
 447 static void init_irsimpletype(void) {
 448         init_irtypeinfo();
 449         if (!phi_cycle_type)
 450                 phi_cycle_type = new_type_class(new_id_from_str("phi_cycle_type"));
 451         precompute_pointer_types();
 452 }
 453
 454 /* Computes type information for each node in all ir graphs. */
 455 void simple_analyse_types(void) {
 456         int i;
 457         FIRM_DBG_REGISTER(dbg, "firm.ana.simpletype");
 458
 459         init_irsimpletype();
 460         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 461                 ir_graph *irg = get_irp_irg(i);
 462                 analyse_irg(irg);
 463         }
 464         set_irp_typeinfo_state(ir_typeinfo_consistent);
 465 }
 466
 467 void free_simple_type_information(void) {
 468         free_irtypeinfo();
 469
 470         if (phi_cycle_type) {
 471                 free_type(phi_cycle_type);
 472                 phi_cycle_type = NULL;
 473         }
 474         set_irp_typeinfo_state(ir_typeinfo_none);
 475 }