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