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 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_supertype(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_member(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_subtype(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_member(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_res(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 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 }
 186
 187 void type_walk_irg (ir_graph *irg,
 188                     void (pre)(type_or_ent*, void*),
 189                     void (post)(type_or_ent*, void*),
 190                     void *env)
 191 {
 192   /* this is needed to pass the parameters to the walker that actually
 193      walks the type information */
 194   type_walk_env* type_env;
 195   type_env = (type_walk_env *) malloc (sizeof(type_walk_env));
 196   type_env->pre = pre;
 197   type_env->post = post;
 198   type_env->env = env;
 199
 200   ++type_visited;
 201   irg_walk(get_irg_end(irg), start_type_walk, NULL, type_env);
 202
 203   type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
 204
 205   free(type_env);
 206   return;
 207 }
 208
 209 void type_walk_s2s_2(type_or_ent *tore,
 210                      void (pre)(type_or_ent*, void*),
 211                      void (post)(type_or_ent*, void*),
 212                      void *env)
 213 {
 214   int i;
 215
 216   /* marked? */
 217   switch (get_kind(tore)) {
 218   case k_entity:
 219     if (((entity *)tore)->visit >= type_visited) return;
 220     break;
 221   case k_type:
 222     if(type_id == get_type_tpop((type*)tore)) {
 223       type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 224       return;
 225     }
 226     if (((type *)tore)->visit >= type_visited) return;
 227     break;
 228   default:
 229     break;
 230   }
 231
 232   /* iterate */
 233   switch (get_kind(tore)) {
 234   case k_type:
 235     {
 236       type *tp = (type *)tore;
 237       mark_type_visited(tp);
 238       switch (get_type_tpop_code(tp)) {
 239       case tpo_class:
 240         {
 241           for (i = 0; i < get_class_n_supertype(tp); i++) {
 242             type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
 243                             post, env);
 244           }
 245           /* execute pre method */
 246           if(pre)
 247             pre(tore, env);
 248           tp = skip_tid((type*)tore);
 249
 250           for (i = 0; i < get_class_n_subtype(tp); i++) {
 251             type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
 252                             post, env);
 253           }
 254
 255           /* execute post method */
 256           if(post)
 257             post(tore, env);
 258         }
 259         break;
 260       case tpo_struct:
 261       case tpo_method:
 262       case tpo_union:
 263       case tpo_array:
 264       case tpo_enumeration:
 265       case tpo_pointer:
 266       case tpo_primitive:
 267       case tpo_id:
 268         /* dont care */
 269         break;
 270       default:
 271         printf(" *** Faulty type! \n");
 272         break;
 273       }
 274     } break; /* end case k_type */
 275   case k_entity:
 276     /* dont care */
 277     break;
 278   default:
 279     printf(" *** Faulty type or entity! \n");
 280     break;
 281   }
 282   return;
 283 }
 284
 285 void type_walk_super2sub(void (pre)(type_or_ent*, void*),
 286                          void (post)(type_or_ent*, void*),
 287                          void *env) {
 288   int i;
 289   type *tp;
 290   ++type_visited;
 291   type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
 292   for (i = 0; i < get_irp_n_types(); i++) {
 293     tp = get_irp_type(i);
 294     type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
 295   }
 296 }
 297
 298 /*****************************************************************************/
 299
 300 static
 301 void type_walk_super_2(type_or_ent *tore,
 302                        void (pre)(type_or_ent*, void*),
 303                        void (post)(type_or_ent*, void*),
 304                        void *env)
 305 {
 306   int i;
 307
 308   /* marked? */
 309   switch (get_kind(tore)) {
 310   case k_entity:
 311     if (((entity *)tore)->visit >= type_visited) return;
 312     break;
 313   case k_type:
 314     if(type_id == get_type_tpop((type*)tore)) {
 315       type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 316       return;
 317     }
 318     if (((type *)tore)->visit >= type_visited) return;
 319     break;
 320   default:
 321     break;
 322   }
 323
 324   /* iterate */
 325   switch (get_kind(tore)) {
 326   case k_type:
 327     {
 328       type *tp = (type *)tore;
 329       mark_type_visited(tp);
 330       switch (get_type_tpop_code(tp)) {
 331       case tpo_class:
 332         {
 333           /* execute pre method */
 334           if(pre)
 335             pre(tore, env);
 336           tp = skip_tid((type*)tore);
 337
 338           for (i = 0; i < get_class_n_supertype(tp); i++) {
 339             type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
 340                               post, env);
 341           }
 342
 343           /* execute post method */
 344           if(post)
 345             post(tore, env);
 346         }
 347         break;
 348       case tpo_struct:
 349       case tpo_method:
 350       case tpo_union:
 351       case tpo_array:
 352       case tpo_enumeration:
 353       case tpo_pointer:
 354       case tpo_primitive:
 355       case tpo_id:
 356         /* dont care */
 357         break;
 358       default:
 359         printf(" *** Faulty type! \n");
 360         break;
 361       }
 362     } break; /* end case k_type */
 363   case k_entity:
 364     /* dont care */
 365     break;
 366   default:
 367     printf(" *** Faulty type or entity! \n");
 368     break;
 369   }
 370   return;
 371 }
 372
 373 void type_walk_super(void (pre)(type_or_ent*, void*),
 374                      void (post)(type_or_ent*, void*),
 375                      void *env) {
 376   int i;
 377   type *tp;
 378   ++type_visited;
 379   type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
 380   for (i = 0; i < get_irp_n_types(); i++) {
 381     tp = get_irp_type(i);
 382     type_walk_super_2((type_or_ent *)tp, pre, post, env);
 383   }
 384 }
 385
 386 /*****************************************************************************/
 387
 388
 389 void class_walk_s2s_2(type *tp,
 390                      void (pre)(type*, void*),
 391                      void (post)(type*, void*),
 392                      void *env)
 393 {
 394   int i;
 395
 396   /* marked? */
 397   if (tp->visit >= type_visited) return;
 398
 399   assert(is_class_type(tp));
 400   /* Assure all supertypes are visited before */
 401   for (i=0; i < get_class_n_supertype(tp); i++) {
 402     if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
 403       return;
 404   }
 405
 406   mark_type_visited(tp);
 407
 408   /* execute pre method */
 409   if(pre)
 410     pre(tp, env);
 411
 412   tp = skip_tid((type*)tp);
 413   for (i=0; i<get_class_n_subtype(tp); i++) {
 414     class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 415   }
 416   /* execute post method */
 417   if(post)
 418     post(tp, env);
 419
 420   return;
 421 }
 422
 423
 424 void class_walk_super2sub(void (pre)(type*, void*),
 425                           void (post)(type*, void*),
 426                           void *env) {
 427   int i;
 428   type *tp;
 429
 430   ++type_visited;
 431   for (i = 0; i < get_irp_n_types(); i++) {
 432     tp = get_irp_type(i);
 433     if (is_class_type(tp) &&
 434         (get_class_n_supertype(tp) == 0) &&
 435         (tp->visit < type_visited) &&
 436         (!is_frame_type(tp)) &&
 437         (tp != get_glob_type())) {
 438       class_walk_s2s_2(tp, pre, post, env);
 439     }
 440   }
 441 }