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(void (pre)(type_or_ent*, void*),
 287                          void (post)(type_or_ent*, void*),
 288                          void *env) {
 289   int i;
 290   type *tp;
 291   ++type_visited;
 292   type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
 293   for (i = 0; i < get_irp_n_types(); i++) {
 294     tp = get_irp_type(i);
 295     type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
 296   }
 297 }
 298
 299 /*****************************************************************************/
 300
 301 static void
 302 type_walk_super_2(type_or_ent *tore,
 303                   void (pre)(type_or_ent*, void*),
 304                   void (post)(type_or_ent*, void*),
 305                   void *env)
 306 {
 307   int i;
 308
 309   /* marked? */
 310   switch (get_kind(tore)) {
 311   case k_entity:
 312     if (((entity *)tore)->visit >= type_visited) return;
 313     break;
 314   case k_type:
 315     if(type_id == get_type_tpop((type*)tore)) {
 316       type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 317       return;
 318     }
 319     if (((type *)tore)->visit >= type_visited) return;
 320     break;
 321   default:
 322     break;
 323   }
 324
 325   /* iterate */
 326   switch (get_kind(tore)) {
 327   case k_type:
 328     {
 329       type *tp = (type *)tore;
 330       mark_type_visited(tp);
 331       switch (get_type_tpop_code(tp)) {
 332       case tpo_class:
 333         {
 334           /* execute pre method */
 335           if(pre)
 336             pre(tore, env);
 337           tp = skip_tid((type*)tore);
 338
 339           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 340             type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
 341                               post, env);
 342           }
 343
 344           /* execute post method */
 345           if(post)
 346             post(tore, env);
 347         }
 348         break;
 349       case tpo_struct:
 350       case tpo_method:
 351       case tpo_union:
 352       case tpo_array:
 353       case tpo_enumeration:
 354       case tpo_pointer:
 355       case tpo_primitive:
 356       case tpo_id:
 357         /* dont care */
 358         break;
 359       default:
 360         printf(" *** Faulty type! \n");
 361         break;
 362       }
 363     } break; /* end case k_type */
 364   case k_entity:
 365     /* dont care */
 366     break;
 367   default:
 368     printf(" *** Faulty type or entity! \n");
 369     break;
 370   }
 371   return;
 372 }
 373
 374 void type_walk_super(void (pre)(type_or_ent*, void*),
 375                      void (post)(type_or_ent*, void*),
 376                      void *env) {
 377   int i;
 378   type *tp;
 379   ++type_visited;
 380   type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
 381   for (i = 0; i < get_irp_n_types(); i++) {
 382     tp = get_irp_type(i);
 383     type_walk_super_2((type_or_ent *)tp, pre, post, env);
 384   }
 385 }
 386
 387 /*****************************************************************************/
 388
 389
 390 static void
 391 class_walk_s2s_2(type *tp,
 392                  void (pre)(type*, void*),
 393                  void (post)(type*, void*),
 394                  void *env)
 395 {
 396   int i;
 397
 398   /* marked? */
 399   if (tp->visit >= type_visited) return;
 400
 401   assert(is_class_type(tp));
 402   /* Assure all supertypes are visited before */
 403   for (i=0; i < get_class_n_supertypes(tp); i++) {
 404     if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
 405       return;
 406   }
 407
 408   mark_type_visited(tp);
 409
 410   /* execute pre method */
 411   if(pre)
 412     pre(tp, env);
 413
 414   tp = skip_tid((type*)tp);
 415   for (i=0; i<get_class_n_subtypes(tp); i++) {
 416     class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 417   }
 418   /* execute post method */
 419   if(post)
 420     post(tp, env);
 421
 422   return;
 423 }
 424
 425 #if 0
 426 void class_walk_super2sub(void (pre)(type*, void*),
 427                           void (post)(type*, void*),
 428                           void *env) {
 429   int i;
 430   type *tp;
 431
 432   ++type_visited;
 433   for (i = 0; i < get_irp_n_types(); i++) {
 434     tp = get_irp_type(i);
 435     if (is_class_type(tp) &&
 436         (get_class_n_supertypes(tp) == 0) &&
 437         (tp->visit < type_visited) &&
 438         (!is_frame_type(tp)) &&
 439         (tp != get_glob_type())) {
 440       class_walk_s2s_2(tp, pre, post, env);
 441     }
 442   }
 443 }
 444 #endif
 445 void class_walk_super2sub(void (pre)(type*, void*),
 446                           void (post)(type*, void*),
 447                           void *env) {
 448   int i;
 449   type *tp;
 450
 451   ++type_visited;
 452   for (i = 0; i < get_irp_n_types(); i++) {
 453     tp = get_irp_type(i);
 454     if (is_class_type(tp) &&
 455         (get_class_n_supertypes(tp) == 0) &&
 456         (tp->visit < type_visited))  {
 457       assert(!is_frame_type(tp));
 458       assert(tp != get_glob_type());
 459       class_walk_s2s_2(tp, pre, post, env);
 460     }
 461   }
 462 }
 463
 464
 465 /* Walks over all entities in the type */
 466 void walk_types_entities(type *tp,
 467                          void (doit)(entity*, void*),
 468                          void *env) {
 469   int i;
 470   switch(get_type_tpop_code(tp)) {
 471   case tpo_class: {
 472     for (i=0; i<get_class_n_members(tp); i++)
 473       doit(get_class_member(tp, i), env);
 474   } break;
 475   case tpo_struct: {
 476     for (i=0; i<get_struct_n_members(tp); i++)
 477       doit(get_struct_member(tp, i), env);
 478   } break;
 479   case tpo_union: {
 480     for (i = 0; i < get_union_n_members(tp); i++)
 481       doit(get_union_member(tp, i), env);
 482   } break;
 483   case tpo_array: {
 484       doit(get_array_element_entity(tp), env);
 485   } break;
 486   case tpo_method:
 487   case tpo_enumeration:
 488   case tpo_pointer:
 489   case tpo_primitive:
 490   case tpo_id:
 491   default:
 492     break;
 493   }
 494 }