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