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