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

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