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 #include "irgwalk.h"
  28 #include "irgraph_t.h"
  29 #include "irnode.h"
  30 #include "irprog.h"
  31 #include "type_or_entity.h"
  32 #include "typegmod.h"
  33 #include "typewalk.h"
  34
  35 /* Make types visible to allow most efficient access */
  36 #include "entity_t.h"
  37 #include "type_t.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         /* a leave. */
 135         break;
 136       default:
 137         printf(" *** Faulty type! \n");
 138         break;
 139       }
 140     } break; /* end case k_type */
 141   default:
 142     printf(" *** Faulty type or entity! \n");
 143     break;
 144   }
 145
 146   /* execute post method */
 147   if(post)
 148     post(tore, env);
 149
 150   return;
 151 }
 152
 153 /**  Check wether node contains types or entities as an attribute.
 154      If so start a walk over that information. */
 155 static void start_type_walk(ir_node *node, void *env) {
 156  type_walk_func *pre;
 157  type_walk_func *post;
 158  void *envi;
 159
 160   pre  = ((type_walk_env *)env)->pre;
 161   post = ((type_walk_env *)env)->post;
 162   envi = ((type_walk_env *)env)->env;
 163
 164   assert(node);
 165
 166   switch (get_irn_opcode(node)) {  /* node label */
 167   case iro_SymConst:
 168     if (   (get_SymConst_kind(node) == type_tag)
 169            || (get_SymConst_kind(node) == size))
 170       type_walk_2((type_or_ent *)get_SymConst_type(node), pre, post, envi);
 171     break;
 172   case iro_Sel:
 173     type_walk_2((type_or_ent *)get_Sel_entity(node), pre, post, envi);
 174     break;
 175   case iro_Call:
 176     type_walk_2((type_or_ent *)get_Call_type(node), pre, post, envi);
 177     break;
 178   case iro_Alloc:
 179     type_walk_2((type_or_ent *)get_Alloc_type(node), pre, post, envi);
 180     break;
 181   case iro_Free:
 182     type_walk_2((type_or_ent *)get_Free_type(node), pre, post, envi);
 183     break;
 184   case iro_Cast:
 185     type_walk_2((type_or_ent *)get_Cast_type(node), pre, post, envi);
 186     break;
 187   default:
 188     break;
 189   }
 190 }
 191
 192 void type_walk(type_walk_func pre,
 193                type_walk_func post,
 194                void *env) {
 195   int i;
 196   ++type_visited;
 197   /*type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 198    global type is on the list visited below, too. */
 199   for (i = 0; i < get_irp_n_types(); i++) {
 200     type_walk_2((type_or_ent *)get_irp_type(i), pre, post, env);
 201   }
 202   type_walk_2((type_or_ent *)get_glob_type(), pre, post, env);
 203 }
 204
 205 void type_walk_irg (ir_graph *irg,
 206                     void (*pre)(type_or_ent*, void*),
 207                     void (*post)(type_or_ent*, void*),
 208                     void *env)
 209 {
 210   ir_graph *rem = current_ir_graph;
 211   /* this is needed to pass the parameters to the walker that actually
 212      walks the type information */
 213   type_walk_env type_env;
 214
 215   type_env.pre  = pre;
 216   type_env.post = post;
 217   type_env.env  = env;
 218
 219   current_ir_graph = irg;
 220
 221   /* We walk over the irg to find all irnodes that contain an attribute
 222      with type information.  If we find one we call a type walker to
 223      touch the reachable type information.
 224      The same type can be referenced by several irnodes.  To avoid
 225      repeated visits of the same type node we must decrease the
 226      type visited flag for each walk.  This is done in start_type_walk().
 227      Here we initially increase the flag.  We only call type_walk_2 that does
 228      not increase the flag.
 229   */
 230   ++type_visited;
 231   irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 232
 233   type_walk_2((type_or_ent *)get_irg_ent(irg), pre, post, env);
 234
 235   type_walk_2((type_or_ent *)get_irg_frame_type(irg), pre, post, env);
 236
 237   current_ir_graph = rem;
 238   return;
 239 }
 240
 241 static void type_walk_s2s_2(type_or_ent *tore,
 242                             void (*pre)(type_or_ent*, void*),
 243                             void (*post)(type_or_ent*, void*),
 244                             void *env)
 245 {
 246   int i;
 247
 248   /* marked? */
 249   switch (get_kind(tore)) {
 250   case k_entity:
 251     if (((entity *)tore)->visit >= type_visited) return;
 252     break;
 253   case k_type:
 254     if(type_id == get_type_tpop((type*)tore)) {
 255       type_walk_s2s_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 256       return;
 257     }
 258     if (((type *)tore)->visit >= type_visited) return;
 259     break;
 260   default:
 261     break;
 262   }
 263
 264   /* iterate */
 265   switch (get_kind(tore)) {
 266   case k_type:
 267     {
 268       type *tp = (type *)tore;
 269       mark_type_visited(tp);
 270       switch (get_type_tpop_code(tp)) {
 271       case tpo_class:
 272         {
 273           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 274             type_walk_s2s_2((type_or_ent *)get_class_supertype(tp, i), pre,
 275                             post, env);
 276           }
 277           /* execute pre method */
 278           if(pre)
 279             pre(tore, env);
 280           tp = skip_tid((type*)tore);
 281
 282           for (i = 0; i < get_class_n_subtypes(tp); i++) {
 283             type_walk_s2s_2((type_or_ent *)get_class_subtype(tp, i), pre,
 284                             post, env);
 285           }
 286
 287           /* execute post method */
 288           if(post)
 289             post(tore, env);
 290         }
 291         break;
 292       case tpo_struct:
 293       case tpo_method:
 294       case tpo_union:
 295       case tpo_array:
 296       case tpo_enumeration:
 297       case tpo_pointer:
 298       case tpo_primitive:
 299       case tpo_id:
 300         /* dont care */
 301         break;
 302       default:
 303         printf(" *** Faulty type! \n");
 304         break;
 305       }
 306     } break; /* end case k_type */
 307   case k_entity:
 308     /* dont care */
 309     break;
 310   default:
 311     printf(" *** Faulty type or entity! \n");
 312     break;
 313   }
 314   return;
 315 }
 316
 317 void type_walk_super2sub(
 318                   void (*pre)(type_or_ent*, void*),
 319                   void (*post)(type_or_ent*, void*),
 320                   void *env)
 321 {
 322   int i;
 323   type *tp;
 324   ++type_visited;
 325   type_walk_s2s_2((type_or_ent *)get_glob_type(), pre, post, env);
 326   for (i = 0; i < get_irp_n_types(); i++) {
 327     tp = get_irp_type(i);
 328     type_walk_s2s_2((type_or_ent *)tp, pre, post, env);
 329   }
 330 }
 331
 332 /*****************************************************************************/
 333
 334 static void
 335 type_walk_super_2(type_or_ent *tore,
 336                   void (*pre)(type_or_ent*, void*),
 337                   void (*post)(type_or_ent*, void*),
 338                   void *env)
 339 {
 340   int i;
 341
 342   /* marked? */
 343   switch (get_kind(tore)) {
 344   case k_entity:
 345     if (((entity *)tore)->visit >= type_visited) return;
 346     break;
 347   case k_type:
 348     if(type_id == get_type_tpop((type*)tore)) {
 349       type_walk_super_2((type_or_ent *)skip_tid((type *)tore), pre, post, env);
 350       return;
 351     }
 352     if (((type *)tore)->visit >= type_visited) return;
 353     break;
 354   default:
 355     break;
 356   }
 357
 358   /* iterate */
 359   switch (get_kind(tore)) {
 360   case k_type:
 361     {
 362       type *tp = (type *)tore;
 363       mark_type_visited(tp);
 364       switch (get_type_tpop_code(tp)) {
 365       case tpo_class:
 366         {
 367           /* execute pre method */
 368           if(pre)
 369             pre(tore, env);
 370           tp = skip_tid((type*)tore);
 371
 372           for (i = 0; i < get_class_n_supertypes(tp); i++) {
 373             type_walk_super_2((type_or_ent *)get_class_supertype(tp, i), pre,
 374                               post, env);
 375           }
 376
 377           /* execute post method */
 378           if(post)
 379             post(tore, env);
 380         }
 381         break;
 382       case tpo_struct:
 383       case tpo_method:
 384       case tpo_union:
 385       case tpo_array:
 386       case tpo_enumeration:
 387       case tpo_pointer:
 388       case tpo_primitive:
 389       case tpo_id:
 390         /* dont care */
 391         break;
 392       default:
 393         printf(" *** Faulty type! \n");
 394         break;
 395       }
 396     } break; /* end case k_type */
 397   case k_entity:
 398     /* dont care */
 399     break;
 400   default:
 401     printf(" *** Faulty type or entity! \n");
 402     break;
 403   }
 404   return;
 405 }
 406
 407 void type_walk_super(
 408                   void (*pre)(type_or_ent*, void*),
 409                   void (*post)(type_or_ent*, void*),
 410                   void *env) {
 411   int i;
 412   type *tp;
 413   ++type_visited;
 414   type_walk_super_2((type_or_ent *)get_glob_type(), pre, post, env);
 415   for (i = 0; i < get_irp_n_types(); i++) {
 416     tp = get_irp_type(i);
 417     type_walk_super_2((type_or_ent *)tp, pre, post, env);
 418   }
 419 }
 420
 421 /*****************************************************************************/
 422
 423
 424 static void
 425 class_walk_s2s_2(type *tp,
 426                  void (*pre)(type*, void*),
 427                  void (*post)(type*, void*),
 428                  void *env)
 429 {
 430   int i;
 431
 432   /* marked? */
 433   if (tp->visit >= type_visited) return;
 434
 435   assert(is_class_type(tp));
 436   /* Assure all supertypes are visited before */
 437   for (i=0; i < get_class_n_supertypes(tp); i++) {
 438     if (get_type_visited(get_class_supertype(tp, i)) < type_visited)
 439       return;
 440   }
 441
 442   mark_type_visited(tp);
 443
 444   /* execute pre method */
 445   if(pre)
 446     pre(tp, env);
 447
 448   tp = skip_tid((type*)tp);
 449   for (i=0; i<get_class_n_subtypes(tp); i++) {
 450     class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 451   }
 452   /* execute post method */
 453   if(post)
 454     post(tp, env);
 455
 456   return;
 457 }
 458
 459 #if 0
 460 void class_walk_super2sub(
 461                   void (*pre)(type*, void*),
 462                   void (*post)(type*, void*),
 463                   void *env)
 464 {
 465   int i;
 466   type *tp;
 467
 468   ++type_visited;
 469   for (i = 0; i < get_irp_n_types(); i++) {
 470     tp = get_irp_type(i);
 471     if (is_class_type(tp) &&
 472         (get_class_n_supertypes(tp) == 0) &&
 473         (tp->visit < type_visited) &&
 474         (!is_frame_type(tp)) &&
 475         (tp != get_glob_type())) {
 476       class_walk_s2s_2(tp, pre, post, env);
 477     }
 478   }
 479 }
 480 #endif
 481 void class_walk_super2sub(
 482                   void (*pre)(type*, void*),
 483                   void (post)(type*, void*),
 484                   void *env)
 485 {
 486   int i;
 487   type *tp;
 488
 489   ++type_visited;
 490   for (i = 0; i < get_irp_n_types(); i++) {
 491     tp = get_irp_type(i);
 492     if (is_class_type(tp) &&
 493         (get_class_n_supertypes(tp) == 0) &&
 494         (tp->visit < type_visited))  {
 495       assert(!is_frame_type(tp));
 496       assert(tp != get_glob_type());
 497       class_walk_s2s_2(tp, pre, post, env);
 498     }
 499   }
 500 }
 501
 502
 503 /* Walks over all entities in the type */
 504 void walk_types_entities(
 505                   type *tp,
 506                   void (*doit)(entity*, void*),
 507                   void *env)
 508 {
 509   int i;
 510   switch(get_type_tpop_code(tp)) {
 511   case tpo_class: {
 512     for (i=0; i<get_class_n_members(tp); i++)
 513       doit(get_class_member(tp, i), env);
 514   } break;
 515   case tpo_struct: {
 516     for (i=0; i<get_struct_n_members(tp); i++)
 517       doit(get_struct_member(tp, i), env);
 518   } break;
 519   case tpo_union: {
 520     for (i = 0; i < get_union_n_members(tp); i++)
 521       doit(get_union_member(tp, i), env);
 522   } break;
 523   case tpo_array: {
 524       doit(get_array_element_entity(tp), env);
 525   } break;
 526   case tpo_method:
 527   case tpo_enumeration:
 528   case tpo_pointer:
 529   case tpo_primitive:
 530   case tpo_id:
 531   default:
 532     break;
 533   }
 534 }