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  * @summary
  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 #ifdef HAVE_CONFIG_H
  33 # include "config.h"
  34 #endif
  35
  36 #ifdef HAVE_STDLIB_H
  37 # include <stdlib.h>
  38 #endif
  39
  40 #include <stdio.h>
  41
  42 #include "entity_t.h"
  43 #include "type_t.h"
  44
  45 #include "irprog_t.h"
  46 #include "irgraph_t.h"
  47 #include "irnode_t.h"
  48 #include "irgwalk.h"
  49 #include "error.h"
  50
  51 /**
  52  * The walker environment
  53  */
  54 typedef struct type_walk_env {
  55         type_walk_func *pre;    /**< Pre-walker function */
  56         type_walk_func *post;   /**< Post-walker function */
  57         void *env;              /**< environment for walker functions */
  58 } type_walk_env;
  59
  60 /* a walker for irn's */
  61 static void irn_type_walker(
  62         ir_node *node, type_walk_func *pre, type_walk_func *post, void *env);
  63
  64 static void walk_initializer(ir_initializer_t *initializer,
  65                              type_walk_func *pre, type_walk_func *post,
  66                              void *env)
  67 {
  68         switch(initializer->kind) {
  69         case IR_INITIALIZER_CONST:
  70                 irn_type_walker(initializer->consti.value, pre, post, env);
  71                 return;
  72         case IR_INITIALIZER_TARVAL:
  73         case IR_INITIALIZER_NULL:
  74                 return;
  75
  76         case IR_INITIALIZER_COMPOUND: {
  77                 size_t i;
  78                 for(i = 0; i < initializer->compound.n_initializers; ++i) {
  79                         ir_initializer_t *subinitializer
  80                                 = initializer->compound.initializers[i];
  81                         walk_initializer(subinitializer, pre, post, env);
  82                 }
  83                 return;
  84         }
  85         }
  86         panic("invalid initializer found");
  87 }
  88
  89 /**
  90  * Main walker: walks over all used types/entities of a
  91  * type entity.
  92  */
  93 static void do_type_walk(type_or_ent tore,
  94                          type_walk_func *pre,
  95                          type_walk_func *post,
  96                          void *env)
  97 {
  98         int         i, n_types, n_mem;
  99         ir_entity   *ent = NULL;
 100         ir_type     *tp = NULL;
 101         ir_node     *n;
 102         type_or_ent cont;
 103
 104         /* marked? */
 105         switch (get_kind(tore.ent)) {
 106         case k_entity:
 107                 ent = tore.ent;
 108                 if (entity_visited(ent))
 109                         return;
 110                 break;
 111         case k_type:
 112                 tp = skip_tid(tore.typ);
 113                 if (type_visited(tp))
 114                         return;
 115                 break;
 116         default:
 117                 break;
 118         }
 119
 120         /* execute pre method */
 121         if (pre)
 122                 pre(tore, env);
 123
 124         /* iterate */
 125         switch (get_kind(tore.ent)) {
 126         case k_entity:
 127                 mark_entity_visited(ent);
 128                 cont.typ = get_entity_owner(ent);
 129                 do_type_walk(cont, pre, post, env);
 130                 cont.typ = get_entity_type(ent);
 131                 do_type_walk(cont, pre, post, env);
 132
 133                 if (get_entity_variability(ent) != variability_uninitialized) {
 134                         /* walk over the value types */
 135                         if (ent->has_initializer) {
 136                                 walk_initializer(ent->attr.initializer, pre, post, env);
 137                         } else if (is_atomic_entity(ent)) {
 138                                 n = get_atomic_ent_value(ent);
 139                                 irn_type_walker(n, pre, post, env);
 140                         } else {
 141                                 n_mem = get_compound_ent_n_values(ent);
 142                                 for (i = 0; i < n_mem; ++i) {
 143                                         n = get_compound_ent_value(ent, i);
 144                                         irn_type_walker(n, pre, post, env);
 145                                 }
 146                         }
 147                 }
 148                 break;
 149         case k_type:
 150                 mark_type_visited(tp);
 151                 switch (get_type_tpop_code(tp)) {
 152
 153                 case tpo_class:
 154                         n_types = get_class_n_supertypes(tp);
 155                         for (i = 0; i < n_types; ++i) {
 156                                 cont.typ = get_class_supertype(tp, i);
 157                                 do_type_walk(cont, pre, post, env);
 158                         }
 159                         n_mem = get_class_n_members(tp);
 160                         for (i = 0; i < n_mem; ++i) {
 161                                 cont.ent = get_class_member(tp, i);
 162                                 do_type_walk(cont, pre, post, env);
 163                         }
 164                         n_types = get_class_n_subtypes(tp);
 165                         for (i = 0; i < n_types; ++i) {
 166                                 cont.typ = get_class_subtype(tp, i);
 167                                 do_type_walk(cont, pre, post, env);
 168                         }
 169                         break;
 170
 171                 case tpo_struct:
 172                         n_mem = get_struct_n_members(tp);
 173                         for (i = 0; i < n_mem; ++i) {
 174                                 cont.ent = get_struct_member(tp, i);
 175                                 do_type_walk(cont, pre, post, env);
 176                         }
 177                         break;
 178
 179                 case tpo_method:
 180                         n_mem = get_method_n_params(tp);
 181                         for (i = 0; i < n_mem; ++i) {
 182                                 cont.typ = get_method_param_type(tp, i);
 183                                 do_type_walk(cont, pre, post, env);
 184                         }
 185                         n_mem = get_method_n_ress(tp);
 186                         for (i = 0; i < n_mem; ++i) {
 187                                 cont.typ = get_method_res_type(tp, i);
 188                                 do_type_walk(cont, pre, post, env);
 189                         }
 190                         break;
 191
 192                 case tpo_union:
 193                         n_mem = get_union_n_members(tp);
 194                         for (i = 0; i < n_mem; ++i) {
 195                                 cont.ent = get_union_member(tp, i);
 196                                 do_type_walk(cont, pre, post, env);
 197                         }
 198                         break;
 199
 200                 case tpo_array:
 201                         cont.typ = get_array_element_type(tp);
 202                         do_type_walk(cont, pre, post, env);
 203                         cont.ent = get_array_element_entity(tp);
 204                         do_type_walk(cont, pre, post, env);
 205                         break;
 206
 207                 case tpo_enumeration:
 208                         /* a leave */
 209                         break;
 210
 211                 case tpo_pointer:
 212                         cont.typ = get_pointer_points_to_type(tp);
 213                         do_type_walk(cont, pre, post, env);
 214                         break;
 215
 216                 case tpo_primitive:
 217                 case tpo_id:
 218                 case tpo_none:
 219                 case tpo_unknown:
 220                         /* a leave. */
 221                         break;
 222                 default:
 223                         assert(0 && "Faulty type");
 224                         break;
 225                 }
 226                 break; /* end case k_type */
 227
 228         default:
 229                 printf(" *** Faulty type or entity! \n");
 230                 break;
 231         }
 232
 233         /* execute post method */
 234         if (post)
 235                 post(tore, env);
 236 }
 237
 238 /**  Check whether node contains types or entities as an attribute.
 239      If so start a walk over that information. */
 240 static void irn_type_walker(
 241   ir_node *node, type_walk_func *pre, type_walk_func *post, void *env)
 242 {
 243         type_or_ent cont;
 244
 245         assert(node);
 246
 247         cont.ent = get_irn_entity_attr(node);
 248         if (cont.ent)
 249                 do_type_walk(cont, pre, post, env);
 250         cont.typ = get_irn_type_attr(node);
 251         if (cont.typ)
 252                 do_type_walk(cont, pre, post, env);
 253 }
 254
 255 /**  Check whether node contains types or entities as an attribute.
 256      If so start a walk over that information. */
 257 static void start_type_walk(ir_node *node, void *ctx) {
 258         type_walk_env *env = ctx;
 259         type_walk_func *pre;
 260         type_walk_func *post;
 261         void *envi;
 262
 263         pre  = env->pre;
 264         post = env->post;
 265         envi = env->env;
 266
 267         irn_type_walker(node, pre, post, envi);
 268 }
 269
 270 /* walker: walks over all types */
 271 void type_walk(type_walk_func *pre, type_walk_func *post, void *env) {
 272         int         i, n_types = get_irp_n_types();
 273         type_or_ent cont;
 274
 275         inc_master_type_visited();
 276         for (i = 0; i < n_types; ++i) {
 277                 cont.typ = get_irp_type(i);
 278                 do_type_walk(cont, pre, post, env);
 279         }
 280         cont.typ = get_glob_type();
 281         do_type_walk(cont, pre, post, env);
 282 }
 283
 284 void type_walk_irg(ir_graph *irg,
 285                    type_walk_func *pre,
 286                    type_walk_func *post,
 287                    void *env)
 288 {
 289         ir_graph *rem = current_ir_graph;
 290         /* this is needed to pass the parameters to the walker that actually
 291            walks the type information */
 292         type_walk_env type_env;
 293         type_or_ent   cont;
 294
 295         type_env.pre  = pre;
 296         type_env.post = post;
 297         type_env.env  = env;
 298
 299         current_ir_graph = irg;
 300
 301         /* We walk over the irg to find all IR-nodes that contain an attribute
 302            with type information.  If we find one we call a type walker to
 303            touch the reachable type information.
 304            The same type can be referenced by several IR-nodes.  To avoid
 305            repeated visits of the same type node we must decrease the
 306            type visited flag for each walk.  This is done in start_type_walk().
 307            Here we initially increase the flag.  We only call do_type_walk that does
 308            not increase the flag.
 309         */
 310         inc_master_type_visited();
 311         irg_walk(get_irg_end(irg), start_type_walk, NULL, &type_env);
 312
 313         cont.ent = get_irg_entity(irg);
 314         do_type_walk(cont, pre, post, env);
 315
 316         cont.typ = get_irg_frame_type(irg);
 317         do_type_walk(cont, pre, post, env);
 318
 319         current_ir_graph = rem;
 320 }
 321
 322 static void type_walk_s2s_2(type_or_ent tore,
 323                             type_walk_func *pre,
 324                             type_walk_func *post,
 325                             void *env)
 326 {
 327         type_or_ent cont;
 328         int         i, n;
 329
 330         /* marked? */
 331         switch (get_kind(tore.ent)) {
 332         case k_entity:
 333                 if (entity_visited(tore.ent)) return;
 334                 break;
 335         case k_type:
 336                 if (type_id == get_type_tpop(tore.typ)) {
 337                         cont.typ = skip_tid(tore.typ);
 338                         type_walk_s2s_2(cont, pre, post, env);
 339                         return;
 340                 }
 341                 if (type_visited(tore.typ)) return;
 342                 break;
 343         default:
 344                 break;
 345         }
 346
 347         /* iterate */
 348         switch (get_kind(tore.typ)) {
 349         case k_type:
 350                 {
 351                         ir_type *tp = tore.typ;
 352                         mark_type_visited(tp);
 353                         switch (get_type_tpop_code(tp)) {
 354                         case tpo_class:
 355                                 {
 356                                         n = get_class_n_supertypes(tp);
 357                                         for (i = 0; i < n; ++i) {
 358                                                 cont.typ = get_class_supertype(tp, i);
 359                                                 type_walk_s2s_2(cont, pre, post, env);
 360                                         }
 361                                         /* execute pre method */
 362                                         if (pre)
 363                                                 pre(tore, env);
 364                                         tp = skip_tid(tp);
 365
 366                                         n = get_class_n_subtypes(tp);
 367                                         for (i = 0; i < n; ++i) {
 368                                                 cont.typ = get_class_subtype(tp, i);
 369                                                 type_walk_s2s_2(cont, pre, post, env);
 370                                         }
 371
 372                                         /* execute post method */
 373                                         if (post)
 374                                                 post(tore, env);
 375                                 }
 376                                 break;
 377                         case tpo_struct:
 378                         case tpo_method:
 379                         case tpo_union:
 380                         case tpo_array:
 381                         case tpo_enumeration:
 382                         case tpo_pointer:
 383                         case tpo_primitive:
 384                         case tpo_id:
 385                                 /* dont care */
 386                                 break;
 387                         default:
 388                                 printf(" *** Faulty type! \n");
 389                                 break;
 390                         }
 391                 } break; /* end case k_type */
 392         case k_entity:
 393                 /* don't care */
 394                 break;
 395         default:
 396                 printf(" *** Faulty type or entity! \n");
 397                 break;
 398         }
 399 }
 400
 401 void type_walk_super2sub(type_walk_func *pre,
 402                          type_walk_func *post,
 403                          void *env)
 404 {
 405         type_or_ent cont;
 406         int         i, n_types = get_irp_n_types();
 407
 408         inc_master_type_visited();
 409         cont.typ = get_glob_type();
 410         type_walk_s2s_2(cont, pre, post, env);
 411         for (i = 0; i < n_types; ++i) {
 412                 cont.typ = get_irp_type(i);
 413                 type_walk_s2s_2(cont, pre, post, env);
 414         }
 415 }
 416
 417 /*****************************************************************************/
 418
 419 static void
 420 type_walk_super_2(type_or_ent tore,
 421                   type_walk_func *pre,
 422                   type_walk_func *post,
 423                   void *env) {
 424         type_or_ent cont;
 425         int         i, n;
 426
 427         /* marked? */
 428         switch (get_kind(tore.ent)) {
 429         case k_entity:
 430                 if (entity_visited(tore.ent))
 431                         return;
 432                 break;
 433         case k_type:
 434                 if (type_id == get_type_tpop(tore.typ)) {
 435                         cont.typ = skip_tid(tore.typ);
 436                         type_walk_super_2(cont, pre, post, env);
 437                         return;
 438                 }
 439                 if (type_visited(tore.typ))
 440                         return;
 441                 break;
 442         default:
 443                 break;
 444         }
 445
 446         /* iterate */
 447         switch (get_kind(tore.typ)) {
 448         case k_type:
 449                 {
 450                         ir_type *tp = tore.typ;
 451                         mark_type_visited(tp);
 452                         switch (get_type_tpop_code(tp)) {
 453                         case tpo_class:
 454                                 {
 455                                         /* execute pre method */
 456                                         if (pre)
 457                                                 pre(tore, env);
 458                                         tp = skip_tid(tp);
 459
 460                                         n = get_class_n_supertypes(tp);
 461                                         for (i = 0; i < n; ++i) {
 462                                                 cont.typ = get_class_supertype(tp, i);
 463                                                 type_walk_super_2(cont, pre, post, env);
 464                                         }
 465
 466                                         /* execute post method */
 467                                         if (post)
 468                                                 post(tore, env);
 469                                 }
 470                                 break;
 471                         case tpo_struct:
 472                         case tpo_method:
 473                         case tpo_union:
 474                         case tpo_array:
 475                         case tpo_enumeration:
 476                         case tpo_pointer:
 477                         case tpo_primitive:
 478                         case tpo_id:
 479                                 /* don't care */
 480                                 break;
 481                         default:
 482                                 printf(" *** Faulty type! \n");
 483                                 break;
 484                         }
 485                 } break; /* end case k_type */
 486         case k_entity:
 487                 /* don't care */
 488                 break;
 489         default:
 490                 printf(" *** Faulty type or entity! \n");
 491                 break;
 492         }
 493 }
 494
 495 void type_walk_super(type_walk_func *pre,
 496                      type_walk_func *post,
 497                      void *env) {
 498         int         i, n_types = get_irp_n_types();
 499         type_or_ent cont;
 500
 501         inc_master_type_visited();
 502         cont.typ = get_glob_type();
 503         type_walk_super_2(cont, pre, post, env);
 504         for (i = 0; i < n_types; ++i) {
 505                 cont.typ = get_irp_type(i);
 506                 type_walk_super_2(cont, pre, post, env);
 507         }
 508 }
 509
 510 /*****************************************************************************/
 511
 512
 513 static void
 514 class_walk_s2s_2(ir_type *tp,
 515                  class_walk_func *pre,
 516                  class_walk_func *post,
 517                  void *env)
 518 {
 519         int i, n;
 520
 521         /* marked? */
 522         if (type_visited(tp)) return;
 523
 524         assert(is_Class_type(tp));
 525         /* Assure all supertypes are visited before */
 526         n = get_class_n_supertypes(tp);
 527         for (i = 0; i < n; ++i) {
 528                 if (type_not_visited(get_class_supertype(tp, i)))
 529                         return;
 530         }
 531
 532         mark_type_visited(tp);
 533
 534         /* execute pre method */
 535         if (pre)
 536                 pre(tp, env);
 537
 538         tp = skip_tid(tp);
 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         int i, n_types = get_irp_n_types();
 553         ir_type *tp;
 554
 555         inc_master_type_visited();
 556         for (i = 0; i < n_types; i++) {
 557                 tp = get_irp_type(i);
 558                 if (is_Class_type(tp) &&
 559                     (get_class_n_supertypes(tp) == 0) &&
 560                     type_not_visited(tp)) {
 561                         assert(! is_frame_type(tp));
 562                         assert(tp != get_glob_type());
 563                         class_walk_s2s_2(tp, pre, post, env);
 564                 }
 565         }
 566 }
 567
 568
 569 /* Walks over all entities in the type */
 570 void walk_types_entities(ir_type *tp,
 571                          entity_walk_func *doit,
 572                          void *env)
 573 {
 574         int i, n;
 575
 576         switch (get_type_tpop_code(tp)) {
 577         case tpo_class:
 578                 n = get_class_n_members(tp);
 579                 for (i = 0; i < n; ++i)
 580                         doit(get_class_member(tp, i), env);
 581                 break;
 582         case tpo_struct:
 583                 n = get_struct_n_members(tp);
 584                 for (i = 0; i < n; ++i)
 585                         doit(get_struct_member(tp, i), env);
 586                 break;
 587         case tpo_union:
 588                 n = get_union_n_members(tp);
 589                 for (i = 0; i < n; ++i)
 590                         doit(get_union_member(tp, i), env);
 591                 break;
 592         case tpo_array:
 593                 doit(get_array_element_entity(tp), env);
 594                 break;
 595         case tpo_method:
 596         case tpo_enumeration:
 597         case tpo_pointer:
 598         case tpo_primitive:
 599         case tpo_id:
 600         default:
 601                 break;
 602         }
 603 }