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