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  * @brief
  25  *
  26  * Traverse the type information.  The walker walks the whole ir graph
  27  * to find the distinct type trees in the type graph forest.
  28  * - execute the pre function before recursion
  29  * - execute the post function after recursion
  30  */
  31 #include "config.h"
  32
  33 #include <stdlib.h>
  34 #include <stdio.h>
  35
  36 #include "entity_t.h"
  37 #include "type_t.h"
  38
  39 #include "irprog_t.h"
  40 #include "irgraph_t.h"
  41 #include "irnode_t.h"
  42 #include "irgwalk.h"
  43 #include "error.h"
  44 #include "ircons.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 void type_walk(type_walk_func *pre, type_walk_func *post, void *env)
 261 {
 262         size_t      i, n_types = get_irp_n_types();
 263         type_or_ent cont;
 264
 265         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 266         inc_master_type_visited();
 267         for (i = 0; i < n_types; ++i) {
 268                 cont.typ = get_irp_type(i);
 269                 do_type_walk(cont, pre, post, env);
 270         }
 271         cont.typ = get_glob_type();
 272         do_type_walk(cont, pre, post, env);
 273         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 274 }
 275
 276 void type_walk_irg(ir_graph *irg,
 277                    type_walk_func *pre,
 278                    type_walk_func *post,
 279                    void *env)
 280 {
 281         ir_graph *rem = current_ir_graph;
 282         /* this is needed to pass the parameters to the walker that actually
 283            walks the type information */
 284         type_walk_env type_env;
 285         type_or_ent   cont;
 286
 287         type_env.pre  = pre;
 288         type_env.post = post;
 289         type_env.env  = env;
 290
 291         current_ir_graph = irg;
 292
 293         /* We walk over the irg to find all IR-nodes that contain an attribute
 294            with type information.  If we find one we call a type walker to
 295            touch the reachable type information.
 296            The same type can be referenced by several IR-nodes.  To avoid
 297            repeated visits of the same type node we must decrease the
 298            type visited flag for each walk.  This is done in start_type_walk().
 299            Here we initially increase the flag.  We only call do_type_walk that does
 300            not increase the flag.
 301         */
 302         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 303         inc_master_type_visited();
 304         irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 305
 306         cont.ent = get_irg_entity(irg);
 307         do_type_walk(cont, pre, post, env);
 308
 309         cont.typ = get_irg_frame_type(irg);
 310         do_type_walk(cont, pre, post, env);
 311
 312         current_ir_graph = rem;
 313         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 314 }
 315
 316 static void type_walk_s2s_2(type_or_ent tore,
 317                             type_walk_func *pre,
 318                             type_walk_func *post,
 319                             void *env)
 320 {
 321         type_or_ent cont;
 322
 323         /* marked? */
 324         switch (get_kind(tore.ent)) {
 325         case k_entity:
 326                 if (entity_visited(tore.ent)) return;
 327                 break;
 328         case k_type:
 329                 if (type_visited(tore.typ)) return;
 330                 break;
 331         default:
 332                 break;
 333         }
 334
 335         /* iterate */
 336         switch (get_kind(tore.typ)) {
 337         case k_type:
 338                 {
 339                         ir_type *tp = tore.typ;
 340                         mark_type_visited(tp);
 341                         switch (get_type_tpop_code(tp)) {
 342                         case tpo_class:
 343                                 {
 344                                         size_t i, n;
 345
 346                                         n = get_class_n_supertypes(tp);
 347                                         for (i = 0; i < n; ++i) {
 348                                                 cont.typ = get_class_supertype(tp, i);
 349                                                 type_walk_s2s_2(cont, pre, post, env);
 350                                         }
 351                                         /* execute pre method */
 352                                         if (pre)
 353                                                 pre(tore, env);
 354
 355                                         n = get_class_n_subtypes(tp);
 356                                         for (i = 0; i < n; ++i) {
 357                                                 cont.typ = get_class_subtype(tp, i);
 358                                                 type_walk_s2s_2(cont, pre, post, env);
 359                                         }
 360
 361                                         /* execute post method */
 362                                         if (post)
 363                                                 post(tore, env);
 364                                 }
 365                                 break;
 366                         case tpo_struct:
 367                         case tpo_method:
 368                         case tpo_union:
 369                         case tpo_array:
 370                         case tpo_enumeration:
 371                         case tpo_pointer:
 372                         case tpo_primitive:
 373                                 /* dont care */
 374                                 break;
 375                         default:
 376                                 printf(" *** Faulty type! \n");
 377                                 break;
 378                         }
 379                 } break; /* end case k_type */
 380         case k_entity:
 381                 /* don't care */
 382                 break;
 383         default:
 384                 printf(" *** Faulty type or entity! \n");
 385                 break;
 386         }
 387 }
 388
 389 void type_walk_super2sub(type_walk_func *pre,
 390                          type_walk_func *post,
 391                          void *env)
 392 {
 393         type_or_ent cont;
 394         size_t      i, n_types = get_irp_n_types();
 395
 396         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 397         inc_master_type_visited();
 398         cont.typ = get_glob_type();
 399         type_walk_s2s_2(cont, pre, post, env);
 400         for (i = 0; i < n_types; ++i) {
 401                 cont.typ = get_irp_type(i);
 402                 type_walk_s2s_2(cont, pre, post, env);
 403         }
 404         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 405 }
 406
 407 /*****************************************************************************/
 408
 409 static void type_walk_super_2(type_or_ent tore, type_walk_func *pre,
 410                               type_walk_func *post, void *env)
 411 {
 412         type_or_ent cont;
 413
 414         /* marked? */
 415         switch (get_kind(tore.ent)) {
 416         case k_entity:
 417                 if (entity_visited(tore.ent))
 418                         return;
 419                 break;
 420         case k_type:
 421                 if (type_visited(tore.typ))
 422                         return;
 423                 break;
 424         default:
 425                 break;
 426         }
 427
 428         /* iterate */
 429         switch (get_kind(tore.typ)) {
 430         case k_type:
 431                 {
 432                         ir_type *tp = tore.typ;
 433                         mark_type_visited(tp);
 434                         switch (get_type_tpop_code(tp)) {
 435                         case tpo_class:
 436                                 {
 437                                         size_t i, n;
 438
 439                                         /* execute pre method */
 440                                         if (pre)
 441                                                 pre(tore, env);
 442
 443                                         n = get_class_n_supertypes(tp);
 444                                         for (i = 0; i < n; ++i) {
 445                                                 cont.typ = get_class_supertype(tp, i);
 446                                                 type_walk_super_2(cont, pre, post, env);
 447                                         }
 448
 449                                         /* execute post method */
 450                                         if (post)
 451                                                 post(tore, env);
 452                                 }
 453                                 break;
 454                         case tpo_struct:
 455                         case tpo_method:
 456                         case tpo_union:
 457                         case tpo_array:
 458                         case tpo_enumeration:
 459                         case tpo_pointer:
 460                         case tpo_primitive:
 461                                 /* don't care */
 462                                 break;
 463                         default:
 464                                 printf(" *** Faulty type! \n");
 465                                 break;
 466                         }
 467                 } break; /* end case k_type */
 468         case k_entity:
 469                 /* don't care */
 470                 break;
 471         default:
 472                 printf(" *** Faulty type or entity! \n");
 473                 break;
 474         }
 475 }
 476
 477 void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
 478 {
 479         size_t      i, n_types = get_irp_n_types();
 480         type_or_ent cont;
 481
 482         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 483         inc_master_type_visited();
 484         cont.typ = get_glob_type();
 485         type_walk_super_2(cont, pre, post, env);
 486         for (i = 0; i < n_types; ++i) {
 487                 cont.typ = get_irp_type(i);
 488                 type_walk_super_2(cont, pre, post, env);
 489         }
 490         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 491 }
 492
 493 /*****************************************************************************/
 494
 495
 496 static void class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
 497                              class_walk_func *post, void *env)
 498 {
 499         size_t i, n;
 500
 501         /* marked? */
 502         if (type_visited(tp)) return;
 503
 504         assert(is_Class_type(tp));
 505         /* Assure all supertypes are visited before */
 506         n = get_class_n_supertypes(tp);
 507         for (i = 0; i < n; ++i) {
 508                 if (type_not_visited(get_class_supertype(tp, i)))
 509                         return;
 510         }
 511
 512         mark_type_visited(tp);
 513
 514         /* execute pre method */
 515         if (pre)
 516                 pre(tp, env);
 517
 518         n = get_class_n_subtypes(tp);
 519         for (i = 0; i < n; ++i) {
 520                 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 521         }
 522         /* execute post method */
 523         if (post)
 524                 post(tp, env);
 525 }
 526
 527 void class_walk_super2sub(class_walk_func *pre,
 528                           class_walk_func *post,
 529                           void *env)
 530 {
 531         size_t i, n_types = get_irp_n_types();
 532         ir_type *tp;
 533
 534         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 535         inc_master_type_visited();
 536         for (i = 0; i < n_types; i++) {
 537                 tp = get_irp_type(i);
 538                 if (is_Class_type(tp) &&
 539                     (get_class_n_supertypes(tp) == 0) &&
 540                     type_not_visited(tp)) {
 541                         assert(! is_frame_type(tp));
 542                         assert(tp != get_glob_type());
 543                         class_walk_s2s_2(tp, pre, post, env);
 544                 }
 545         }
 546         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 547 }
 548
 549
 550 void walk_types_entities(ir_type *tp,
 551                          entity_walk_func *doit,
 552                          void *env)
 553 {
 554         size_t i, n;
 555
 556         switch (get_type_tpop_code(tp)) {
 557         case tpo_class:
 558                 n = get_class_n_members(tp);
 559                 for (i = 0; i < n; ++i)
 560                         doit(get_class_member(tp, i), env);
 561                 break;
 562         case tpo_struct:
 563                 n = get_struct_n_members(tp);
 564                 for (i = 0; i < n; ++i)
 565                         doit(get_struct_member(tp, i), env);
 566                 break;
 567         case tpo_union:
 568                 n = get_union_n_members(tp);
 569                 for (i = 0; i < n; ++i)
 570                         doit(get_union_member(tp, i), env);
 571                 break;
 572         case tpo_array:
 573                 doit(get_array_element_entity(tp), env);
 574                 break;
 575         case tpo_method:
 576         case tpo_enumeration:
 577         case tpo_pointer:
 578         case tpo_primitive:
 579         default:
 580                 break;
 581         }
 582 }