nsz Git - libfirm/blob - ir/tr/typewalk.c

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