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 {
 248         type_walk_env *env = ctx;
 249         type_walk_func *pre;
 250         type_walk_func *post;
 251         void *envi;
 252
 253         pre  = env->pre;
 254         post = env->post;
 255         envi = env->env;
 256
 257         irn_type_walker(node, pre, post, envi);
 258 }
 259
 260 /* walker: walks over all types */
 261 void type_walk(type_walk_func *pre, type_walk_func *post, void *env)
 262 {
 263         int         i, n_types = get_irp_n_types();
 264         type_or_ent cont;
 265
 266         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 267         inc_master_type_visited();
 268         for (i = 0; i < n_types; ++i) {
 269                 cont.typ = get_irp_type(i);
 270                 do_type_walk(cont, pre, post, env);
 271         }
 272         cont.typ = get_glob_type();
 273         do_type_walk(cont, pre, post, env);
 274         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 275 }
 276
 277 void type_walk_prog(type_walk_func *pre, type_walk_func *post, void *env)
 278 {
 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 = IR_SEGMENT_FIRST; i <= IR_SEGMENT_LAST; ++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         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 328         inc_master_type_visited();
 329         irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 330
 331         cont.ent = get_irg_entity(irg);
 332         do_type_walk(cont, pre, post, env);
 333
 334         cont.typ = get_irg_frame_type(irg);
 335         do_type_walk(cont, pre, post, env);
 336
 337         current_ir_graph = rem;
 338         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 339 }
 340
 341 static void type_walk_s2s_2(type_or_ent tore,
 342                             type_walk_func *pre,
 343                             type_walk_func *post,
 344                             void *env)
 345 {
 346         type_or_ent cont;
 347         int         i, n;
 348
 349         /* marked? */
 350         switch (get_kind(tore.ent)) {
 351         case k_entity:
 352                 if (entity_visited(tore.ent)) return;
 353                 break;
 354         case k_type:
 355                 if (type_visited(tore.typ)) return;
 356                 break;
 357         default:
 358                 break;
 359         }
 360
 361         /* iterate */
 362         switch (get_kind(tore.typ)) {
 363         case k_type:
 364                 {
 365                         ir_type *tp = tore.typ;
 366                         mark_type_visited(tp);
 367                         switch (get_type_tpop_code(tp)) {
 368                         case tpo_class:
 369                                 {
 370                                         n = get_class_n_supertypes(tp);
 371                                         for (i = 0; i < n; ++i) {
 372                                                 cont.typ = get_class_supertype(tp, i);
 373                                                 type_walk_s2s_2(cont, pre, post, env);
 374                                         }
 375                                         /* execute pre method */
 376                                         if (pre)
 377                                                 pre(tore, env);
 378
 379                                         n = get_class_n_subtypes(tp);
 380                                         for (i = 0; i < n; ++i) {
 381                                                 cont.typ = get_class_subtype(tp, i);
 382                                                 type_walk_s2s_2(cont, pre, post, env);
 383                                         }
 384
 385                                         /* execute post method */
 386                                         if (post)
 387                                                 post(tore, env);
 388                                 }
 389                                 break;
 390                         case tpo_struct:
 391                         case tpo_method:
 392                         case tpo_union:
 393                         case tpo_array:
 394                         case tpo_enumeration:
 395                         case tpo_pointer:
 396                         case tpo_primitive:
 397                                 /* dont care */
 398                                 break;
 399                         default:
 400                                 printf(" *** Faulty type! \n");
 401                                 break;
 402                         }
 403                 } break; /* end case k_type */
 404         case k_entity:
 405                 /* don't care */
 406                 break;
 407         default:
 408                 printf(" *** Faulty type or entity! \n");
 409                 break;
 410         }
 411 }
 412
 413 void type_walk_super2sub(type_walk_func *pre,
 414                          type_walk_func *post,
 415                          void *env)
 416 {
 417         type_or_ent cont;
 418         int         i, n_types = get_irp_n_types();
 419
 420         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 421         inc_master_type_visited();
 422         cont.typ = get_glob_type();
 423         type_walk_s2s_2(cont, pre, post, env);
 424         for (i = 0; i < n_types; ++i) {
 425                 cont.typ = get_irp_type(i);
 426                 type_walk_s2s_2(cont, pre, post, env);
 427         }
 428         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 429 }
 430
 431 /*****************************************************************************/
 432
 433 static void type_walk_super_2(type_or_ent tore, type_walk_func *pre,
 434                               type_walk_func *post, void *env)
 435 {
 436         type_or_ent cont;
 437         int         i, n;
 438
 439         /* marked? */
 440         switch (get_kind(tore.ent)) {
 441         case k_entity:
 442                 if (entity_visited(tore.ent))
 443                         return;
 444                 break;
 445         case k_type:
 446                 if (type_visited(tore.typ))
 447                         return;
 448                 break;
 449         default:
 450                 break;
 451         }
 452
 453         /* iterate */
 454         switch (get_kind(tore.typ)) {
 455         case k_type:
 456                 {
 457                         ir_type *tp = tore.typ;
 458                         mark_type_visited(tp);
 459                         switch (get_type_tpop_code(tp)) {
 460                         case tpo_class:
 461                                 {
 462                                         /* execute pre method */
 463                                         if (pre)
 464                                                 pre(tore, env);
 465
 466                                         n = get_class_n_supertypes(tp);
 467                                         for (i = 0; i < n; ++i) {
 468                                                 cont.typ = get_class_supertype(tp, i);
 469                                                 type_walk_super_2(cont, pre, post, env);
 470                                         }
 471
 472                                         /* execute post method */
 473                                         if (post)
 474                                                 post(tore, env);
 475                                 }
 476                                 break;
 477                         case tpo_struct:
 478                         case tpo_method:
 479                         case tpo_union:
 480                         case tpo_array:
 481                         case tpo_enumeration:
 482                         case tpo_pointer:
 483                         case tpo_primitive:
 484                                 /* don't care */
 485                                 break;
 486                         default:
 487                                 printf(" *** Faulty type! \n");
 488                                 break;
 489                         }
 490                 } break; /* end case k_type */
 491         case k_entity:
 492                 /* don't care */
 493                 break;
 494         default:
 495                 printf(" *** Faulty type or entity! \n");
 496                 break;
 497         }
 498 }
 499
 500 void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
 501 {
 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 class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
 520                              class_walk_func *post, void *env)
 521 {
 522         int i, n;
 523
 524         /* marked? */
 525         if (type_visited(tp)) return;
 526
 527         assert(is_Class_type(tp));
 528         /* Assure all supertypes are visited before */
 529         n = get_class_n_supertypes(tp);
 530         for (i = 0; i < n; ++i) {
 531                 if (type_not_visited(get_class_supertype(tp, i)))
 532                         return;
 533         }
 534
 535         mark_type_visited(tp);
 536
 537         /* execute pre method */
 538         if (pre)
 539                 pre(tp, env);
 540
 541         n = get_class_n_subtypes(tp);
 542         for (i = 0; i < n; ++i) {
 543                 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 544         }
 545         /* execute post method */
 546         if (post)
 547                 post(tp, env);
 548 }
 549
 550 void class_walk_super2sub(class_walk_func *pre,
 551                           class_walk_func *post,
 552                           void *env)
 553 {
 554         int i, n_types = get_irp_n_types();
 555         ir_type *tp;
 556
 557         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 558         inc_master_type_visited();
 559         for (i = 0; i < n_types; i++) {
 560                 tp = get_irp_type(i);
 561                 if (is_Class_type(tp) &&
 562                     (get_class_n_supertypes(tp) == 0) &&
 563                     type_not_visited(tp)) {
 564                         assert(! is_frame_type(tp));
 565                         assert(tp != get_glob_type());
 566                         class_walk_s2s_2(tp, pre, post, env);
 567                 }
 568         }
 569         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 570 }
 571
 572
 573 /* Walks over all entities in the type */
 574 void walk_types_entities(ir_type *tp,
 575                          entity_walk_func *doit,
 576                          void *env)
 577 {
 578         int i, n;
 579
 580         switch (get_type_tpop_code(tp)) {
 581         case tpo_class:
 582                 n = get_class_n_members(tp);
 583                 for (i = 0; i < n; ++i)
 584                         doit(get_class_member(tp, i), env);
 585                 break;
 586         case tpo_struct:
 587                 n = get_struct_n_members(tp);
 588                 for (i = 0; i < n; ++i)
 589                         doit(get_struct_member(tp, i), env);
 590                 break;
 591         case tpo_union:
 592                 n = get_union_n_members(tp);
 593                 for (i = 0; i < n; ++i)
 594                         doit(get_union_member(tp, i), env);
 595                 break;
 596         case tpo_array:
 597                 doit(get_array_element_entity(tp), env);
 598                 break;
 599         case tpo_method:
 600         case tpo_enumeration:
 601         case tpo_pointer:
 602         case tpo_primitive:
 603         default:
 604                 break;
 605         }
 606 }