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

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