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