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