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