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