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