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, IRP_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, IRP_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
 290         for (i = IR_SEGMENT_FIRST; i <= IR_SEGMENT_LAST; ++i) {
 291                 cont.typ = get_segment_type((ir_segment_t) i);
 292                 if (cont.typ)
 293                         do_type_walk(cont, pre, post, env);
 294         }
 295 }
 296
 297 void type_walk_irg(ir_graph *irg,
 298                    type_walk_func *pre,
 299                    type_walk_func *post,
 300                    void *env)
 301 {
 302         ir_graph *rem = current_ir_graph;
 303         /* this is needed to pass the parameters to the walker that actually
 304            walks the type information */
 305         type_walk_env type_env;
 306         type_or_ent   cont;
 307
 308         type_env.pre  = pre;
 309         type_env.post = post;
 310         type_env.env  = env;
 311
 312         current_ir_graph = irg;
 313
 314         /* We walk over the irg to find all IR-nodes that contain an attribute
 315            with type information.  If we find one we call a type walker to
 316            touch the reachable type information.
 317            The same type can be referenced by several IR-nodes.  To avoid
 318            repeated visits of the same type node we must decrease the
 319            type visited flag for each walk.  This is done in start_type_walk().
 320            Here we initially increase the flag.  We only call do_type_walk that does
 321            not increase the flag.
 322         */
 323         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 324         inc_master_type_visited();
 325         irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 326
 327         cont.ent = get_irg_entity(irg);
 328         do_type_walk(cont, pre, post, env);
 329
 330         cont.typ = get_irg_frame_type(irg);
 331         do_type_walk(cont, pre, post, env);
 332
 333         current_ir_graph = rem;
 334         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 335 }
 336
 337 static void type_walk_s2s_2(type_or_ent tore,
 338                             type_walk_func *pre,
 339                             type_walk_func *post,
 340                             void *env)
 341 {
 342         type_or_ent cont;
 343
 344         /* marked? */
 345         switch (get_kind(tore.ent)) {
 346         case k_entity:
 347                 if (entity_visited(tore.ent)) return;
 348                 break;
 349         case k_type:
 350                 if (type_visited(tore.typ)) return;
 351                 break;
 352         default:
 353                 break;
 354         }
 355
 356         /* iterate */
 357         switch (get_kind(tore.typ)) {
 358         case k_type:
 359                 {
 360                         ir_type *tp = tore.typ;
 361                         mark_type_visited(tp);
 362                         switch (get_type_tpop_code(tp)) {
 363                         case tpo_class:
 364                                 {
 365                                         size_t i, n;
 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         size_t      i, n_types = get_irp_n_types();
 416
 417         irp_reserve_resources(irp, IRP_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, IRP_RESOURCE_TYPE_VISITED);
 426 }
 427
 428 /*****************************************************************************/
 429
 430 static void type_walk_super_2(type_or_ent tore, type_walk_func *pre,
 431                               type_walk_func *post, void *env)
 432 {
 433         type_or_ent cont;
 434
 435         /* marked? */
 436         switch (get_kind(tore.ent)) {
 437         case k_entity:
 438                 if (entity_visited(tore.ent))
 439                         return;
 440                 break;
 441         case k_type:
 442                 if (type_visited(tore.typ))
 443                         return;
 444                 break;
 445         default:
 446                 break;
 447         }
 448
 449         /* iterate */
 450         switch (get_kind(tore.typ)) {
 451         case k_type:
 452                 {
 453                         ir_type *tp = tore.typ;
 454                         mark_type_visited(tp);
 455                         switch (get_type_tpop_code(tp)) {
 456                         case tpo_class:
 457                                 {
 458                                         size_t i, n;
 459
 460                                         /* execute pre method */
 461                                         if (pre)
 462                                                 pre(tore, env);
 463
 464                                         n = get_class_n_supertypes(tp);
 465                                         for (i = 0; i < n; ++i) {
 466                                                 cont.typ = get_class_supertype(tp, i);
 467                                                 type_walk_super_2(cont, pre, post, env);
 468                                         }
 469
 470                                         /* execute post method */
 471                                         if (post)
 472                                                 post(tore, env);
 473                                 }
 474                                 break;
 475                         case tpo_struct:
 476                         case tpo_method:
 477                         case tpo_union:
 478                         case tpo_array:
 479                         case tpo_enumeration:
 480                         case tpo_pointer:
 481                         case tpo_primitive:
 482                                 /* don't care */
 483                                 break;
 484                         default:
 485                                 printf(" *** Faulty type! \n");
 486                                 break;
 487                         }
 488                 } break; /* end case k_type */
 489         case k_entity:
 490                 /* don't care */
 491                 break;
 492         default:
 493                 printf(" *** Faulty type or entity! \n");
 494                 break;
 495         }
 496 }
 497
 498 void type_walk_super(type_walk_func *pre, type_walk_func *post, void *env)
 499 {
 500         size_t      i, n_types = get_irp_n_types();
 501         type_or_ent cont;
 502
 503         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 504         inc_master_type_visited();
 505         cont.typ = get_glob_type();
 506         type_walk_super_2(cont, pre, post, env);
 507         for (i = 0; i < n_types; ++i) {
 508                 cont.typ = get_irp_type(i);
 509                 type_walk_super_2(cont, pre, post, env);
 510         }
 511         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 512 }
 513
 514 /*****************************************************************************/
 515
 516
 517 static void class_walk_s2s_2(ir_type *tp, class_walk_func *pre,
 518                              class_walk_func *post, void *env)
 519 {
 520         size_t i, n;
 521
 522         /* marked? */
 523         if (type_visited(tp)) return;
 524
 525         assert(is_Class_type(tp));
 526         /* Assure all supertypes are visited before */
 527         n = get_class_n_supertypes(tp);
 528         for (i = 0; i < n; ++i) {
 529                 if (type_not_visited(get_class_supertype(tp, i)))
 530                         return;
 531         }
 532
 533         mark_type_visited(tp);
 534
 535         /* execute pre method */
 536         if (pre)
 537                 pre(tp, env);
 538
 539         n = get_class_n_subtypes(tp);
 540         for (i = 0; i < n; ++i) {
 541                 class_walk_s2s_2(get_class_subtype(tp, i), pre, post, env);
 542         }
 543         /* execute post method */
 544         if (post)
 545                 post(tp, env);
 546 }
 547
 548 void class_walk_super2sub(class_walk_func *pre,
 549                           class_walk_func *post,
 550                           void *env)
 551 {
 552         size_t i, n_types = get_irp_n_types();
 553         ir_type *tp;
 554
 555         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 556         inc_master_type_visited();
 557         for (i = 0; i < n_types; i++) {
 558                 tp = get_irp_type(i);
 559                 if (is_Class_type(tp) &&
 560                     (get_class_n_supertypes(tp) == 0) &&
 561                     type_not_visited(tp)) {
 562                         assert(! is_frame_type(tp));
 563                         assert(tp != get_glob_type());
 564                         class_walk_s2s_2(tp, pre, post, env);
 565                 }
 566         }
 567         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 568 }
 569
 570
 571 /* Walks over all entities in the type */
 572 void walk_types_entities(ir_type *tp,
 573                          entity_walk_func *doit,
 574                          void *env)
 575 {
 576         size_t i, n;
 577
 578         switch (get_type_tpop_code(tp)) {
 579         case tpo_class:
 580                 n = get_class_n_members(tp);
 581                 for (i = 0; i < n; ++i)
 582                         doit(get_class_member(tp, i), env);
 583                 break;
 584         case tpo_struct:
 585                 n = get_struct_n_members(tp);
 586                 for (i = 0; i < n; ++i)
 587                         doit(get_struct_member(tp, i), env);
 588                 break;
 589         case tpo_union:
 590                 n = get_union_n_members(tp);
 591                 for (i = 0; i < n; ++i)
 592                         doit(get_union_member(tp, i), env);
 593                 break;
 594         case tpo_array:
 595                 doit(get_array_element_entity(tp), env);
 596                 break;
 597         case tpo_method:
 598         case tpo_enumeration:
 599         case tpo_pointer:
 600         case tpo_primitive:
 601         default:
 602                 break;
 603         }
 604 }