nsz Git - libfirm/blob - ir/tr/typewalk.c

   1 /*
   2  * Copyright (C) 1995-2011 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         size_t      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                         size_t i, 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 = (type_walk_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         size_t      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         size_t 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
 348         /* marked? */
 349         switch (get_kind(tore.ent)) {
 350         case k_entity:
 351                 if (entity_visited(tore.ent)) return;
 352                 break;
 353         case k_type:
 354                 if (type_visited(tore.typ)) return;
 355                 break;
 356         default:
 357                 break;
 358         }
 359
 360         /* iterate */
 361         switch (get_kind(tore.typ)) {
 362         case k_type:
 363                 {
 364                         ir_type *tp = tore.typ;
 365                         mark_type_visited(tp);
 366                         switch (get_type_tpop_code(tp)) {
 367                         case tpo_class:
 368                                 {
 369                                         size_t i, n;
 370
 371                                         n = get_class_n_supertypes(tp);
 372                                         for (i = 0; i < n; ++i) {
 373                                                 cont.typ = get_class_supertype(tp, i);
 374                                                 type_walk_s2s_2(cont, pre, post, env);
 375                                         }
 376                                         /* execute pre method */
 377                                         if (pre)
 378                                                 pre(tore, env);
 379
 380                                         n = get_class_n_subtypes(tp);
 381                                         for (i = 0; i < n; ++i) {
 382                                                 cont.typ = get_class_subtype(tp, i);
 383                                                 type_walk_s2s_2(cont, pre, post, env);
 384                                         }
 385
 386                                         /* execute post method */
 387                                         if (post)
 388                                                 post(tore, env);
 389                                 }
 390                                 break;
 391                         case tpo_struct:
 392                         case tpo_method:
 393                         case tpo_union:
 394                         case tpo_array:
 395                         case tpo_enumeration:
 396                         case tpo_pointer:
 397                         case tpo_primitive:
 398                                 /* dont care */
 399                                 break;
 400                         default:
 401                                 printf(" *** Faulty type! \n");
 402                                 break;
 403                         }
 404                 } break; /* end case k_type */
 405         case k_entity:
 406                 /* don't care */
 407                 break;
 408         default:
 409                 printf(" *** Faulty type or entity! \n");
 410                 break;
 411         }
 412 }
 413
 414 void type_walk_super2sub(type_walk_func *pre,
 415                          type_walk_func *post,
 416                          void *env)
 417 {
 418         type_or_ent cont;
 419         size_t      i, n_types = get_irp_n_types();
 420
 421         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 422         inc_master_type_visited();
 423         cont.typ = get_glob_type();
 424         type_walk_s2s_2(cont, pre, post, env);
 425         for (i = 0; i < n_types; ++i) {
 426                 cont.typ = get_irp_type(i);
 427                 type_walk_s2s_2(cont, pre, post, env);
 428         }
 429         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 430 }
 431
 432 /*****************************************************************************/
 433
 434 static void type_walk_super_2(type_or_ent tore, type_walk_func *pre,
 435                               type_walk_func *post, void *env)
 436 {
 437         type_or_ent cont;
 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                                         size_t i, n;
 463
 464                                         /* execute pre method */
 465                                         if (pre)
 466                                                 pre(tore, env);
 467
 468                                         n = get_class_n_supertypes(tp);
 469                                         for (i = 0; i < n; ++i) {
 470                                                 cont.typ = get_class_supertype(tp, i);
 471                                                 type_walk_super_2(cont, pre, post, env);
 472                                         }
 473
 474                                         /* execute post method */
 475                                         if (post)
 476                                                 post(tore, env);
 477                                 }
 478                                 break;
 479                         case tpo_struct:
 480                         case tpo_method:
 481                         case tpo_union:
 482                         case tpo_array:
 483                         case tpo_enumeration:
 484                         case tpo_pointer:
 485                         case tpo_primitive:
 486                                 /* don't care */
 487                                 break;
 488                         default:
 489                                 printf(" *** Faulty type! \n");
 490                                 break;
 491                         }
 492                 } break; /* end case k_type */
 493         case k_entity:
 494                 /* don't care */
 495                 break;
 496         default:
 497                 printf(" *** Faulty type or entity! \n");
 498                 break;
 499         }
 500 }
 501
 502 void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
 503 {
 504         size_t      i, n_types = get_irp_n_types();
 505         type_or_ent cont;
 506
 507         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 508         inc_master_type_visited();
 509         cont.typ = get_glob_type();
 510         type_walk_super_2(cont, pre, post, env);
 511         for (i = 0; i < n_types; ++i) {
 512                 cont.typ = get_irp_type(i);
 513                 type_walk_super_2(cont, pre, post, env);
 514         }
 515         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 516 }
 517
 518 /*****************************************************************************/
 519
 520
 521 static void class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
 522                              class_walk_func *post, void *env)
 523 {
 524         size_t 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         n = get_class_n_subtypes(tp);
 544         for (i = 0; i < n; ++i) {
 545                 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 546         }
 547         /* execute post method */
 548         if (post)
 549                 post(tp, env);
 550 }
 551
 552 void class_walk_super2sub(class_walk_func *pre,
 553                           class_walk_func *post,
 554                           void *env)
 555 {
 556         size_t i, n_types = get_irp_n_types();
 557         ir_type *tp;
 558
 559         irp_reserve_resources(irp, IR_RESOURCE_TYPE_VISITED);
 560         inc_master_type_visited();
 561         for (i = 0; i < n_types; i++) {
 562                 tp = get_irp_type(i);
 563                 if (is_Class_type(tp) &&
 564                     (get_class_n_supertypes(tp) == 0) &&
 565                     type_not_visited(tp)) {
 566                         assert(! is_frame_type(tp));
 567                         assert(tp != get_glob_type());
 568                         class_walk_s2s_2(tp, pre, post, env);
 569                 }
 570         }
 571         irp_free_resources(irp, IR_RESOURCE_TYPE_VISITED);
 572 }
 573
 574
 575 /* Walks over all entities in the type */
 576 void walk_types_entities(ir_type *tp,
 577                          entity_walk_func *doit,
 578                          void *env)
 579 {
 580         size_t i, n;
 581
 582         switch (get_type_tpop_code(tp)) {
 583         case tpo_class:
 584                 n = get_class_n_members(tp);
 585                 for (i = 0; i < n; ++i)
 586                         doit(get_class_member(tp, i), env);
 587                 break;
 588         case tpo_struct:
 589                 n = get_struct_n_members(tp);
 590                 for (i = 0; i < n; ++i)
 591                         doit(get_struct_member(tp, i), env);
 592                 break;
 593         case tpo_union:
 594                 n = get_union_n_members(tp);
 595                 for (i = 0; i < n; ++i)
 596                         doit(get_union_member(tp, i), env);
 597                 break;
 598         case tpo_array:
 599                 doit(get_array_element_entity(tp), env);
 600                 break;
 601         case tpo_method:
 602         case tpo_enumeration:
 603         case tpo_pointer:
 604         case tpo_primitive:
 605         default:
 606                 break;
 607         }
 608 }