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 #ifdef HAVE_STDLIB_H
  26 # include <stdlib.h>
  27 #endif
  28
  29 #include <stdio.h>
  30
  31 #include "typewalk.h"
  32 #include "entity_t.h"
  33 #include "type_t.h"
  34 #include "type_or_entity.h"
  35 #include "typegmod.h"
  36
  37 #include "irprog_t.h"
  38 #include "irgraph_t.h"
  39 #include "irnode_t.h"
  40 #include "irgwalk.h"
  41
  42 typedef struct type_walk_env {
  43   type_walk_func *pre;
  44   type_walk_func *post;
  45   void *env;
  46 } type_walk_env;
  47
  48
  49 static void type_walk_2(type_or_ent *tore,
  50                         void (*pre) (type_or_ent*, void*),
  51                         void (*post)(type_or_ent*, void*),
  52                         void *env)
  53 {
  54   int i;
  55
  56   /* marked? */
  57   switch (get_kind(tore)) {
  58   case k_entity:
  59     if (((entity *)tore)->visit >= type_visited) return;
  60     break;
  61   case k_type:
  62     if(type_id == get_type_tpop((type*)tore)) {
  63       type_walk_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
  64       return;
  65     }
  66     if (((type *)tore)->visit >= type_visited) return;
  67     break;
  68   default:
  69     break;
  70   }
  71
  72   /* execute pre method */
  73   if(pre)
  74     pre(tore, env);
  75
  76   /* iterate */
  77   switch (get_kind(tore)) {
  78   case k_entity:
  79     {
  80
  81       entity *ent = (entity *)tore;
  82       ent->visit = type_visited;
  83       type_walk_2((type_or_ent *)get_entity_owner(ent), pre, post, env);
  84       type_walk_2((type_or_ent *)get_entity_type(ent), pre, post, env);
  85     }
  86     break;
  87   case k_type:
  88     {
  89       type *tp = (type *)tore;
  90       mark_type_visited(tp);
  91       switch (get_type_tpop_code(tp)) {
  92       case tpo_class:
  93         {
  94           for (i=0; i<get_class_n_supertypes(tp); i++)
  95             type_walk_2((type_or_ent *)get_class_supertype(tp, i), pre, post, env);
  96           for (i=0; i<get_class_n_members(tp); i++)
  97             type_walk_2((type_or_ent *)get_class_member(tp, i), pre, post, env);
  98           for (i=0; i<get_class_n_subtypes(tp); i++)
  99             type_walk_2((type_or_ent *)get_class_subtype(tp, i), pre, post, env);
 100         }
 101         break;
 102       case tpo_struct:
 103         {
 104           for (i=0; i<get_struct_n_members(tp); i++)
 105             type_walk_2((type_or_ent *)get_struct_member(tp, i), pre, post, env);
 106         }
 107         break;
 108       case tpo_method:
 109         {
 110           for (i = 0; i < get_method_n_params(tp); i++)
 111             type_walk_2((type_or_ent *)get_method_param_type(tp, i), pre, post, env);
 112           for (i = 0; i < get_method_n_ress(tp); i++)
 113             type_walk_2((type_or_ent *)get_method_res_type(tp, i), pre, post, env);
 114         }
 115         break;
 116       case tpo_union:
 117         {
 118           for (i = 0; i < get_union_n_members(tp); i++)
 119             type_walk_2((type_or_ent *)get_union_member(tp, i), pre, post, env);
 120         }
 121         break;
 122       case tpo_array:
 123         type_walk_2((type_or_ent *)get_array_element_type(tp),
 124                     pre, post, env);
 125         type_walk_2((type_or_ent *)get_array_element_entity(tp),
 126                     pre, post, env);
 127         break;
 128       case tpo_enumeration:
 129         /* a leave */
 130         break;
 131       case tpo_pointer:
 132         type_walk_2((type_or_ent *)get_pointer_points_to_type(tp),
 133                     pre, post, env);
 134         break;
 135       case tpo_primitive:
 136       case tpo_id:
 137       case tpo_none:
 138       case tpo_unknown:
 139         /* a leave. */
 140         break;
 141       default:
 142         assert(0 && "Faulty type");
 143         break;
 144       }
 145     } break; /* end case k_type */
 146   default:
 147     printf(" *** Faulty type or entity! \n");
 148     break;
 149   }
 150
 151   /* execute post method */
 152   if(post)
 153     post(tore, env);
 154
 155   return;
 156 }
 157
 158 /**  Check wether node contains types or entities as an attribute.
 159      If so start a walk over that information. */
 160 static void start_type_walk(ir_node *node, void *env) {
 161  type_walk_func *pre;
 162  type_walk_func *post;
 163  void *envi;
 164
 165   pre  = ((type_walk_env *)env)->pre;
 166   post = ((type_walk_env *)env)->post;
 167   envi = ((type_walk_env *)env)->env;
 168
 169   assert(node);
 170
 171   switch (get_irn_opcode(node)) {  /* node label */
 172   case iro_SymConst:
 173     if (   (get_SymConst_kind(node) ==symconst_type_tag)
 174            || (get_SymConst_kind(node) ==symconst_size))
 175       type_walk_2((type_or_ent *)get_SymConst_type(node), pre, post, envi);
 176     break;
 177   case iro_Sel:
 178     type_walk_2((type_or_ent *)get_Sel_entity(node), pre, post, envi);
 179     break;
 180   case iro_Call:
 181     type_walk_2((type_or_ent *)get_Call_type(node), pre, post, envi);
 182     break;
 183   case iro_Alloc:
 184     type_walk_2((type_or_ent *)get_Alloc_type(node), pre, post, envi);
 185     break;
 186   case iro_Free:
 187     type_walk_2((type_or_ent *)get_Free_type(node), pre, post, envi);
 188     break;
 189   case iro_Cast:
 190     type_walk_2((type_or_ent *)get_Cast_type(node), pre, post, envi);
 191     break;
 192   default:
 193     break;
 194   }
 195 }
 196
 197 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
 198   int i, n_types = get_irp_n_types();
 199
 200   ++type_visited;
 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_entity(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 }