nsz Git - libfirm/blob - ir/tr/typewalk.c

   1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 * All rights reserved.
   3 *
   4 * Author: Goetz Lindenmaier
   5 *
   6 * traverse the type information.  The walker walks the whole ir graph
   7 * to find the distinct type trees in the type graph forest.
   8 * - execute the pre function before recursion
   9 * - execute the post function after recursion
  10 */
  11
  12 /* $Id$ */
  13
  14 #ifdef HAVE_CONFIG_H
  15 # include <config.h>
  16 #endif
  17
  18 #include <stdlib.h>
  19 #include <stdio.h>
  20 #include "irgwalk.h"
  21 #include "irgraph_t.h"
  22 #include "irnode.h"
  23 #include "irprog.h"
  24 #include "type_or_entity.h"
  25 #include "typegmod.h"
  26 #include "typewalk.h"
  27
  28 /* Make types visible to allow most efficient access */
  29 #include "entity_t.h"
  30 #include "type_t.h"
  31
  32 typedef struct type_walk_env {
  33   type_walk_func *pre;
  34   type_walk_func *post;
  35   void *env;
  36 } type_walk_env;
  37
  38
  39 static void type_walk_2(type_or_ent *tore,
  40                void (*pre)(type_or_ent*, void*),
  41                void (*post)(type_or_ent*, void*),
  42                void *env)
  43 {
  44   int i;
  45
  46   /* marked? */
  47   switch (get_kind(tore)) {
  48   case k_entity:
  49     if (((entity *)tore)->visit >= type_visited) return;
  50     break;
  51   case k_type:
  52     if(type_id == get_type_tpop((type*)tore)) {
  53       type_walk_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
  54       return;
  55     }
  56     if (((type *)tore)->visit >= type_visited) return;
  57     break;
  58   default:
  59     break;
  60   }
  61
  62   /* execute pre method */
  63   if(pre)
  64     pre(tore, env);
  65
  66   /* iterate */
  67   switch (get_kind(tore)) {
  68   case k_entity:
  69     {
  70
  71       entity *ent = (entity *)tore;
  72       ent->visit = type_visited;
  73       type_walk_2((type_or_ent *)get_entity_owner(ent), pre, post, env);
  74       type_walk_2((type_or_ent *)get_entity_type(ent), pre, post, env);
  75     }
  76     break;
  77   case k_type:
  78     {
  79       type *tp = (type *)tore;
  80       mark_type_visited(tp);
  81       switch (get_type_tpop_code(tp)) {
  82       case tpo_class:
  83         {
  84           for (i=0; i<get_class_n_supertypes(tp); i++)
  85             type_walk_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
  86           for (i=0; i<get_class_n_members(tp); i++)
  87             type_walk_2((type_or_ent *)get_class_member(tp, i), pre, post, env);
  88           for (i=0; i<get_class_n_subtypes(tp); i++)
  89             type_walk_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
  90         }
  91         break;
  92       case tpo_struct:
  93         {
  94           for (i=0; i<get_struct_n_members(tp); i++)
  95             type_walk_2((type_or_ent *)get_struct_member(tp, i), pre, post, env);
  96         }
  97         break;
  98       case tpo_method:
  99         {
 100           for (i = 0; i < get_method_n_params(tp); i++)
 101             type_walk_2((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
 102           for (i = 0; i < get_method_n_ress(tp); i++)
 103             type_walk_2((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
 104         }
 105         break;
 106       case tpo_union:
 107         {
 108           for (i = 0; i < get_union_n_members(tp); i++)
 109             type_walk_2((type_or_ent *)get_union_member(tp, i), pre, post, env);
 110         }
 111         break;
 112       case tpo_array:
 113         type_walk_2((type_or_ent *)get_array_element_type(tp),
 114                     pre, post, env);
 115         type_walk_2((type_or_ent *)get_array_element_entity(tp),
 116                     pre, post, env);
 117         break;
 118       case tpo_enumeration:
 119         /* a leave */
 120         break;
 121       case tpo_pointer:
 122         type_walk_2((type_or_ent *)get_pointer_points_to_type(tp),
 123                     pre, post, env);
 124         break;
 125       case tpo_primitive:
 126       case tpo_id:
 127         /* a leave. */
 128         break;
 129       default:
 130         printf(" *** Faulty type! \n");
 131         break;
 132       }
 133     } break; /* end case k_type */
 134   default:
 135     printf(" *** Faulty type or entity! \n");
 136     break;
 137   }
 138
 139   /* execute post method */
 140   if(post)
 141     post(tore, env);
 142
 143   return;
 144 }
 145
 146 /**  Check wether node contains types or entities as an attribute.
 147      If so start a walk over that information. */
 148 static void start_type_walk(ir_node *node, void *env) {
 149  type_walk_func *pre;
 150  type_walk_func *post;
 151  void *envi;
 152
 153   pre  = ((type_walk_env *)env)->pre;
 154   post = ((type_walk_env *)env)->post;
 155   envi = ((type_walk_env *)env)->env;
 156
 157   assert(node);
 158
 159   switch (get_irn_opcode(node)) {  /* node label */
 160   case iro_SymConst:
 161     if (   (get_SymConst_kind(node) == type_tag)
 162            || (get_SymConst_kind(node) == size))
 163       type_walk_2((type_or_ent *)get_SymConst_type(node), pre, post, envi);
 164     break;
 165   case iro_Sel:
 166     type_walk_2((type_or_ent *)get_Sel_entity(node), pre, post, envi);
 167     break;
 168   case iro_Call:
 169     type_walk_2((type_or_ent *)get_Call_type(node), pre, post, envi);
 170     break;
 171   case iro_Alloc:
 172     type_walk_2((type_or_ent *)get_Alloc_type(node), pre, post, envi);
 173     break;
 174   case iro_Free:
 175     type_walk_2((type_or_ent *)get_Free_type(node), pre, post, envi);
 176     break;
 177   case iro_Cast:
 178     type_walk_2((type_or_ent *)get_Cast_type(node), pre, post, envi);
 179     break;
 180   default:
 181     break;
 182   }
 183 }
 184
 185 void type_walk(void (pre)(type_or_ent*, void*),
 186                void (post)(type_or_ent*, void*),
 187                void *env) {
 188   int i;
 189   ++type_visited;
 190   /*type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 191    global type is on the list visited below, too. */
 192   for (i = 0; i < get_irp_n_types(); i++) {
 193     type_walk_2((type_or_ent *)get_irp_type(i), pre, post, env);
 194   }
 195   type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 196 }
 197
 198 void type_walk_irg (ir_graph *irg,
 199                     void (*pre)(type_or_ent*, void*),
 200                     void (*post)(type_or_ent*, void*),
 201                     void *env)
 202 {
 203   ir_graph *rem = current_ir_graph;
 204   /* this is needed to pass the parameters to the walker that actually
 205      walks the type information */
 206   type_walk_env type_env;
 207
 208   type_env.pre  = pre;
 209   type_env.post = post;
 210   type_env.env  = env;
 211
 212   current_ir_graph = irg;
 213
 214   /* We walk over the irg to find all irnodes that contain an attribute
 215      with type information.  If we find one we call a type walker to
 216      touch the reachable type information.
 217      The same type can be referenced by several irnodes.  To avoid
 218      repeated visits of the same type node we must decrease the
 219      type visited flag for each walk.  This is done in start_type_walk().
 220      Here we initially increase the flag.  We only call type_walk_2 that does
 221      not increase the flag.
 222   */
 223   ++type_visited;
 224   irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 225
 226   type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
 227
 228   type_walk_2((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
 229
 230   current_ir_graph = rem;
 231   return;
 232 }
 233
 234 static void type_walk_s2s_2(type_or_ent *tore,
 235                             void (*pre)(type_or_ent*, void*),
 236                             void (*post)(type_or_ent*, void*),
 237                             void *env)
 238 {
 239   int i;
 240
 241   /* marked? */
 242   switch (get_kind(tore)) {
 243   case k_entity:
 244     if (((entity *)tore)->visit >= type_visited) return;
 245     break;
 246   case k_type:
 247     if(type_id == get_type_tpop((type*)tore)) {
 248       type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 249       return;
 250     }
 251     if (((type *)tore)->visit >= type_visited) return;
 252     break;
 253   default:
 254     break;
 255   }
 256
 257   /* iterate */
 258   switch (get_kind(tore)) {
 259   case k_type:
 260     {
 261       type *tp = (type *)tore;
 262       mark_type_visited(tp);
 263       switch (get_type_tpop_code(tp)) {
 264       case tpo_class:
 265         {
 266           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 267             type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
 268                             post, env);
 269           }
 270           /* execute pre method */
 271           if(pre)
 272             pre(tore, env);
 273           tp = skip_tid((type*)tore);
 274
 275           for (i = 0; i < get_class_n_subtypes(tp); i++) {
 276             type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
 277                             post, env);
 278           }
 279
 280           /* execute post method */
 281           if(post)
 282             post(tore, env);
 283         }
 284         break;
 285       case tpo_struct:
 286       case tpo_method:
 287       case tpo_union:
 288       case tpo_array:
 289       case tpo_enumeration:
 290       case tpo_pointer:
 291       case tpo_primitive:
 292       case tpo_id:
 293         /* dont care */
 294         break;
 295       default:
 296         printf(" *** Faulty type! \n");
 297         break;
 298       }
 299     } break; /* end case k_type */
 300   case k_entity:
 301     /* dont care */
 302     break;
 303   default:
 304     printf(" *** Faulty type or entity! \n");
 305     break;
 306   }
 307   return;
 308 }
 309
 310 void type_walk_super2sub(
 311                   void (*pre)(type_or_ent*, void*),
 312                   void (*post)(type_or_ent*, void*),
 313                   void *env)
 314 {
 315   int i;
 316   type *tp;
 317   ++type_visited;
 318   type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
 319   for (i = 0; i < get_irp_n_types(); i++) {
 320     tp = get_irp_type(i);
 321     type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
 322   }
 323 }
 324
 325 /*****************************************************************************/
 326
 327 static void
 328 type_walk_super_2(type_or_ent *tore,
 329                   void (*pre)(type_or_ent*, void*),
 330                   void (*post)(type_or_ent*, void*),
 331                   void *env)
 332 {
 333   int i;
 334
 335   /* marked? */
 336   switch (get_kind(tore)) {
 337   case k_entity:
 338     if (((entity *)tore)->visit >= type_visited) return;
 339     break;
 340   case k_type:
 341     if(type_id == get_type_tpop((type*)tore)) {
 342       type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 343       return;
 344     }
 345     if (((type *)tore)->visit >= type_visited) return;
 346     break;
 347   default:
 348     break;
 349   }
 350
 351   /* iterate */
 352   switch (get_kind(tore)) {
 353   case k_type:
 354     {
 355       type *tp = (type *)tore;
 356       mark_type_visited(tp);
 357       switch (get_type_tpop_code(tp)) {
 358       case tpo_class:
 359         {
 360           /* execute pre method */
 361           if(pre)
 362             pre(tore, env);
 363           tp = skip_tid((type*)tore);
 364
 365           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 366             type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
 367                               post, env);
 368           }
 369
 370           /* execute post method */
 371           if(post)
 372             post(tore, env);
 373         }
 374         break;
 375       case tpo_struct:
 376       case tpo_method:
 377       case tpo_union:
 378       case tpo_array:
 379       case tpo_enumeration:
 380       case tpo_pointer:
 381       case tpo_primitive:
 382       case tpo_id:
 383         /* dont care */
 384         break;
 385       default:
 386         printf(" *** Faulty type! \n");
 387         break;
 388       }
 389     } break; /* end case k_type */
 390   case k_entity:
 391     /* dont care */
 392     break;
 393   default:
 394     printf(" *** Faulty type or entity! \n");
 395     break;
 396   }
 397   return;
 398 }
 399
 400 void type_walk_super(
 401                   void (*pre)(type_or_ent*, void*),
 402                   void (*post)(type_or_ent*, void*),
 403                   void *env) {
 404   int i;
 405   type *tp;
 406   ++type_visited;
 407   type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
 408   for (i = 0; i < get_irp_n_types(); i++) {
 409     tp = get_irp_type(i);
 410     type_walk_super_2((type_or_ent *)tp, pre, post, env);
 411   }
 412 }
 413
 414 /*****************************************************************************/
 415
 416
 417 static void
 418 class_walk_s2s_2(type *tp,
 419                  void (*pre)(type*, void*),
 420                  void (*post)(type*, void*),
 421                  void *env)
 422 {
 423   int i;
 424
 425   /* marked? */
 426   if (tp->visit >= type_visited) return;
 427
 428   assert(is_class_type(tp));
 429   /* Assure all supertypes are visited before */
 430   for (i=0; i < get_class_n_supertypes(tp); i++) {
 431     if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
 432       return;
 433   }
 434
 435   mark_type_visited(tp);
 436
 437   /* execute pre method */
 438   if(pre)
 439     pre(tp, env);
 440
 441   tp = skip_tid((type*)tp);
 442   for (i=0; i<get_class_n_subtypes(tp); i++) {
 443     class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 444   }
 445   /* execute post method */
 446   if(post)
 447     post(tp, env);
 448
 449   return;
 450 }
 451
 452 #if 0
 453 void class_walk_super2sub(
 454                   void (*pre)(type*, void*),
 455                   void (*post)(type*, void*),
 456                   void *env)
 457 {
 458   int i;
 459   type *tp;
 460
 461   ++type_visited;
 462   for (i = 0; i < get_irp_n_types(); i++) {
 463     tp = get_irp_type(i);
 464     if (is_class_type(tp) &&
 465         (get_class_n_supertypes(tp) == 0) &&
 466         (tp->visit < type_visited) &&
 467         (!is_frame_type(tp)) &&
 468         (tp != get_glob_type())) {
 469       class_walk_s2s_2(tp, pre, post, env);
 470     }
 471   }
 472 }
 473 #endif
 474 void class_walk_super2sub(
 475                   void (*pre)(type*, void*),
 476                   void (post)(type*, void*),
 477                   void *env)
 478 {
 479   int i;
 480   type *tp;
 481
 482   ++type_visited;
 483   for (i = 0; i < get_irp_n_types(); i++) {
 484     tp = get_irp_type(i);
 485     if (is_class_type(tp) &&
 486         (get_class_n_supertypes(tp) == 0) &&
 487         (tp->visit < type_visited))  {
 488       assert(!is_frame_type(tp));
 489       assert(tp != get_glob_type());
 490       class_walk_s2s_2(tp, pre, post, env);
 491     }
 492   }
 493 }
 494
 495
 496 /* Walks over all entities in the type */
 497 void walk_types_entities(
 498                   type *tp,
 499                   void (*doit)(entity*, void*),
 500                   void *env)
 501 {
 502   int i;
 503   switch(get_type_tpop_code(tp)) {
 504   case tpo_class: {
 505     for (i=0; i<get_class_n_members(tp); i++)
 506       doit(get_class_member(tp, i), env);
 507   } break;
 508   case tpo_struct: {
 509     for (i=0; i<get_struct_n_members(tp); i++)
 510       doit(get_struct_member(tp, i), env);
 511   } break;
 512   case tpo_union: {
 513     for (i = 0; i < get_union_n_members(tp); i++)
 514       doit(get_union_member(tp, i), env);
 515   } break;
 516   case tpo_array: {
 517       doit(get_array_element_entity(tp), env);
 518   } break;
 519   case tpo_method:
 520   case tpo_enumeration:
 521   case tpo_pointer:
 522   case tpo_primitive:
 523   case tpo_id:
 524   default:
 525     break;
 526   }
 527 }