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