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   default:
 178     break;
 179   }
 180 }
 181
 182 void type_walk(void (pre)(type_or_ent*, void*),
 183                void (post)(type_or_ent*, void*),
 184                void *env) {
 185   int i;
 186   ++type_visited;
 187   /*type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 188    global type is on the list visited below, too. */
 189   for (i = 0; i < get_irp_n_types(); i++) {
 190     type_walk_2((type_or_ent *)get_irp_type(i), pre, post, env);
 191   }
 192   type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 193 }
 194
 195 void type_walk_irg (ir_graph *irg,
 196                     void (*pre)(type_or_ent*, void*),
 197                     void (*post)(type_or_ent*, void*),
 198                     void *env)
 199 {
 200   ir_graph *rem = current_ir_graph;
 201   /* this is needed to pass the parameters to the walker that actually
 202      walks the type information */
 203   type_walk_env type_env;
 204
 205   type_env.pre  = pre;
 206   type_env.post = post;
 207   type_env.env  = env;
 208
 209   current_ir_graph = irg;
 210
 211   /* We walk over the irg to find all irnodes that contain an attribute
 212      with type information.  If we find one we call a type walker to
 213      touch the reachable type information.
 214      The same type can be referenced by several irnodes.  To avoid
 215      repeated visits of the same type node we must decrease the
 216      type visited flag for each walk.  This is done in start_type_walk().
 217      Here we initially increase the flag.  We only call type_walk_2 that does
 218      not increase the flag.
 219   */
 220   ++type_visited;
 221   irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 222
 223   type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
 224
 225   type_walk_2((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
 226
 227   current_ir_graph = rem;
 228   return;
 229 }
 230
 231 static void type_walk_s2s_2(type_or_ent *tore,
 232                             void (*pre)(type_or_ent*, void*),
 233                             void (*post)(type_or_ent*, void*),
 234                             void *env)
 235 {
 236   int i;
 237
 238   /* marked? */
 239   switch (get_kind(tore)) {
 240   case k_entity:
 241     if (((entity *)tore)->visit >= type_visited) return;
 242     break;
 243   case k_type:
 244     if(type_id == get_type_tpop((type*)tore)) {
 245       type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 246       return;
 247     }
 248     if (((type *)tore)->visit >= type_visited) return;
 249     break;
 250   default:
 251     break;
 252   }
 253
 254   /* iterate */
 255   switch (get_kind(tore)) {
 256   case k_type:
 257     {
 258       type *tp = (type *)tore;
 259       mark_type_visited(tp);
 260       switch (get_type_tpop_code(tp)) {
 261       case tpo_class:
 262         {
 263           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 264             type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
 265                             post, env);
 266           }
 267           /* execute pre method */
 268           if(pre)
 269             pre(tore, env);
 270           tp = skip_tid((type*)tore);
 271
 272           for (i = 0; i < get_class_n_subtypes(tp); i++) {
 273             type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
 274                             post, env);
 275           }
 276
 277           /* execute post method */
 278           if(post)
 279             post(tore, env);
 280         }
 281         break;
 282       case tpo_struct:
 283       case tpo_method:
 284       case tpo_union:
 285       case tpo_array:
 286       case tpo_enumeration:
 287       case tpo_pointer:
 288       case tpo_primitive:
 289       case tpo_id:
 290         /* dont care */
 291         break;
 292       default:
 293         printf(" *** Faulty type! \n");
 294         break;
 295       }
 296     } break; /* end case k_type */
 297   case k_entity:
 298     /* dont care */
 299     break;
 300   default:
 301     printf(" *** Faulty type or entity! \n");
 302     break;
 303   }
 304   return;
 305 }
 306
 307 void type_walk_super2sub(
 308                   void (*pre)(type_or_ent*, void*),
 309                   void (*post)(type_or_ent*, void*),
 310                   void *env)
 311 {
 312   int i;
 313   type *tp;
 314   ++type_visited;
 315   type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
 316   for (i = 0; i < get_irp_n_types(); i++) {
 317     tp = get_irp_type(i);
 318     type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
 319   }
 320 }
 321
 322 /*****************************************************************************/
 323
 324 static void
 325 type_walk_super_2(type_or_ent *tore,
 326                   void (*pre)(type_or_ent*, void*),
 327                   void (*post)(type_or_ent*, void*),
 328                   void *env)
 329 {
 330   int i;
 331
 332   /* marked? */
 333   switch (get_kind(tore)) {
 334   case k_entity:
 335     if (((entity *)tore)->visit >= type_visited) return;
 336     break;
 337   case k_type:
 338     if(type_id == get_type_tpop((type*)tore)) {
 339       type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 340       return;
 341     }
 342     if (((type *)tore)->visit >= type_visited) return;
 343     break;
 344   default:
 345     break;
 346   }
 347
 348   /* iterate */
 349   switch (get_kind(tore)) {
 350   case k_type:
 351     {
 352       type *tp = (type *)tore;
 353       mark_type_visited(tp);
 354       switch (get_type_tpop_code(tp)) {
 355       case tpo_class:
 356         {
 357           /* execute pre method */
 358           if(pre)
 359             pre(tore, env);
 360           tp = skip_tid((type*)tore);
 361
 362           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 363             type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
 364                               post, env);
 365           }
 366
 367           /* execute post method */
 368           if(post)
 369             post(tore, env);
 370         }
 371         break;
 372       case tpo_struct:
 373       case tpo_method:
 374       case tpo_union:
 375       case tpo_array:
 376       case tpo_enumeration:
 377       case tpo_pointer:
 378       case tpo_primitive:
 379       case tpo_id:
 380         /* dont care */
 381         break;
 382       default:
 383         printf(" *** Faulty type! \n");
 384         break;
 385       }
 386     } break; /* end case k_type */
 387   case k_entity:
 388     /* dont care */
 389     break;
 390   default:
 391     printf(" *** Faulty type or entity! \n");
 392     break;
 393   }
 394   return;
 395 }
 396
 397 void type_walk_super(
 398                   void (*pre)(type_or_ent*, void*),
 399                   void (*post)(type_or_ent*, void*),
 400                   void *env) {
 401   int i;
 402   type *tp;
 403   ++type_visited;
 404   type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
 405   for (i = 0; i < get_irp_n_types(); i++) {
 406     tp = get_irp_type(i);
 407     type_walk_super_2((type_or_ent *)tp, pre, post, env);
 408   }
 409 }
 410
 411 /*****************************************************************************/
 412
 413
 414 static void
 415 class_walk_s2s_2(type *tp,
 416                  void (*pre)(type*, void*),
 417                  void (*post)(type*, void*),
 418                  void *env)
 419 {
 420   int i;
 421
 422   /* marked? */
 423   if (tp->visit >= type_visited) return;
 424
 425   assert(is_class_type(tp));
 426   /* Assure all supertypes are visited before */
 427   for (i=0; i < get_class_n_supertypes(tp); i++) {
 428     if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
 429       return;
 430   }
 431
 432   mark_type_visited(tp);
 433
 434   /* execute pre method */
 435   if(pre)
 436     pre(tp, env);
 437
 438   tp = skip_tid((type*)tp);
 439   for (i=0; i<get_class_n_subtypes(tp); i++) {
 440     class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 441   }
 442   /* execute post method */
 443   if(post)
 444     post(tp, env);
 445
 446   return;
 447 }
 448
 449 #if 0
 450 void class_walk_super2sub(
 451                   void (*pre)(type*, void*),
 452                   void (*post)(type*, void*),
 453                   void *env)
 454 {
 455   int i;
 456   type *tp;
 457
 458   ++type_visited;
 459   for (i = 0; i < get_irp_n_types(); i++) {
 460     tp = get_irp_type(i);
 461     if (is_class_type(tp) &&
 462         (get_class_n_supertypes(tp) == 0) &&
 463         (tp->visit < type_visited) &&
 464         (!is_frame_type(tp)) &&
 465         (tp != get_glob_type())) {
 466       class_walk_s2s_2(tp, pre, post, env);
 467     }
 468   }
 469 }
 470 #endif
 471 void class_walk_super2sub(
 472                   void (*pre)(type*, void*),
 473                   void (post)(type*, void*),
 474                   void *env)
 475 {
 476   int i;
 477   type *tp;
 478
 479   ++type_visited;
 480   for (i = 0; i < get_irp_n_types(); i++) {
 481     tp = get_irp_type(i);
 482     if (is_class_type(tp) &&
 483         (get_class_n_supertypes(tp) == 0) &&
 484         (tp->visit < type_visited))  {
 485       assert(!is_frame_type(tp));
 486       assert(tp != get_glob_type());
 487       class_walk_s2s_2(tp, pre, post, env);
 488     }
 489   }
 490 }
 491
 492
 493 /* Walks over all entities in the type */
 494 void walk_types_entities(
 495                   type *tp,
 496                   void (*doit)(entity*, void*),
 497                   void *env)
 498 {
 499   int i;
 500   switch(get_type_tpop_code(tp)) {
 501   case tpo_class: {
 502     for (i=0; i<get_class_n_members(tp); i++)
 503       doit(get_class_member(tp, i), env);
 504   } break;
 505   case tpo_struct: {
 506     for (i=0; i<get_struct_n_members(tp); i++)
 507       doit(get_struct_member(tp, i), env);
 508   } break;
 509   case tpo_union: {
 510     for (i = 0; i < get_union_n_members(tp); i++)
 511       doit(get_union_member(tp, i), env);
 512   } break;
 513   case tpo_array: {
 514       doit(get_array_element_entity(tp), env);
 515   } break;
 516   case tpo_method:
 517   case tpo_enumeration:
 518   case tpo_pointer:
 519   case tpo_primitive:
 520   case tpo_id:
 521   default:
 522     break;
 523   }
 524 }