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

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