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