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