nsz Git - libfirm/blob - ir/ana/trouts.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
  22  * @brief    Reverse edges that reference types/entities.
  23  * @author   Goetz Lindenmaier
  24  * @date     29.10.2004
  25  */
  26 #include "config.h"
  27
  28 #include "trouts_t.h"
  29
  30 #include "array.h"
  31 #include "pmap.h"
  32
  33 #include "irnode_t.h"
  34 #include "irprog_t.h"
  35 #include "irgwalk.h"
  36 #include "irnode.h"
  37
  38
  39 /*------------------------------------------------------------------*/
  40 /* We represent the fields in entities/types by hashmaps.           */
  41 /*------------------------------------------------------------------*/
  42
  43 static pmap *entity_access_map = NULL;
  44 static pmap *entity_reference_map = NULL;
  45 static pmap *type_alloc_map = NULL;
  46 static pmap *type_cast_map = NULL;
  47 static pmap *type_pointertype_map = NULL;
  48 static pmap *type_arraytype_map = NULL;
  49
  50 /**
  51  * Return a flexible array containing all IR-nodes
  52  * that access a given entity.
  53  */
  54 static ir_node **get_entity_access_array(const ir_entity *ent)
  55 {
  56         ir_node **res;
  57         if (!entity_access_map) entity_access_map = pmap_create();
  58
  59         if (pmap_contains(entity_access_map, ent)) {
  60                 res = (ir_node **) pmap_get(entity_access_map, ent);
  61         } else {
  62                 res = NEW_ARR_F(ir_node *, 0);
  63                 pmap_insert(entity_access_map, ent, (void *)res);
  64         }
  65
  66         return res;
  67 }
  68
  69 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
  70 {
  71         pmap_insert(entity_access_map, ent, (void *)accs);
  72 }
  73
  74 /**
  75  * Return a flexible array containing all IR-nodes
  76  * that reference a given entity.
  77  */
  78 static ir_node **get_entity_reference_array(const ir_entity *ent)
  79 {
  80         ir_node **res;
  81         if (!entity_reference_map) entity_reference_map = pmap_create();
  82
  83         if (pmap_contains(entity_reference_map, ent)) {
  84                 res = (ir_node **) pmap_get(entity_reference_map, ent);
  85         } else {
  86                 res = NEW_ARR_F(ir_node *, 0);
  87                 pmap_insert(entity_reference_map, ent, (void *)res);
  88         }
  89
  90         return res;
  91 }
  92
  93 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
  94 {
  95         pmap_insert(entity_reference_map, ent, (void *)refs);
  96 }
  97
  98 /**
  99  * Return a flexible array containing all IR-nodes
 100  * that allocate a given type.
 101  */
 102 static ir_node **get_type_alloc_array(const ir_type *tp)
 103 {
 104         ir_node **res;
 105         if (!type_alloc_map) type_alloc_map = pmap_create();
 106
 107         if (pmap_contains(type_alloc_map, tp)) {
 108                 res = (ir_node **) pmap_get(type_alloc_map, tp);
 109         } else {
 110                 res = NEW_ARR_F(ir_node *, 0);
 111                 pmap_insert(type_alloc_map, tp, (void *)res);
 112         }
 113
 114         return res;
 115 }
 116
 117 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
 118 {
 119         pmap_insert(type_alloc_map, tp, (void *)alls);
 120 }
 121
 122 /**
 123  * Return a flexible array containing all Cast-nodes
 124  * that "create" a given type.
 125  */
 126 static ir_node **get_type_cast_array(const ir_type *tp)
 127 {
 128         ir_node **res;
 129         if (!type_cast_map) type_cast_map = pmap_create();
 130
 131         if (pmap_contains(type_cast_map, tp)) {
 132                 res = (ir_node **) pmap_get(type_cast_map, tp);
 133         } else {
 134                 res = NEW_ARR_F(ir_node *, 0);
 135                 pmap_insert(type_cast_map, tp, (void *)res);
 136         }
 137         return res;
 138 }
 139
 140 static void set_type_cast_array(const ir_type *tp, ir_node **alls)
 141 {
 142         pmap_insert(type_cast_map, tp, (void *)alls);
 143 }
 144
 145 /**
 146  * Return a flexible array containing all pointer
 147  * types that points-to a given type.
 148  */
 149 static ir_type **get_type_pointertype_array(const ir_type *tp)
 150 {
 151         ir_type **res;
 152         if (!type_pointertype_map) type_pointertype_map = pmap_create();
 153
 154         if (pmap_contains(type_pointertype_map, tp)) {
 155                 res = (ir_type **) pmap_get(type_pointertype_map, tp);
 156         } else {
 157                 res = NEW_ARR_F(ir_type *, 0);
 158                 pmap_insert(type_pointertype_map, tp, (void *)res);
 159         }
 160
 161         return res;
 162 }
 163
 164 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
 165 {
 166         pmap_insert(type_pointertype_map, tp, (void *)pts);
 167 }
 168
 169 /**
 170  * Return a flexible array containing all array
 171  * types that have a given type as element type.
 172  */
 173 static ir_type **get_type_arraytype_array(const ir_type *tp)
 174 {
 175         ir_type **res;
 176         if (!type_arraytype_map) type_arraytype_map = pmap_create();
 177
 178         if (pmap_contains(type_arraytype_map, tp)) {
 179                 res = (ir_type **) pmap_get(type_arraytype_map, tp);
 180         } else {
 181                 res = NEW_ARR_F(ir_type *, 0);
 182                 pmap_insert(type_arraytype_map, tp, (void *)res);
 183         }
 184
 185         return res;
 186 }
 187
 188 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
 189 {
 190         pmap_insert(type_arraytype_map, tp, (void *)pts);
 191 }
 192
 193 /*------------------------------------------------------------------*/
 194 /* Accessing the out data structures.                               */
 195 /* These routines only work properly if firm is in state            */
 196 /* trouts_consistent or trouts_inconsistent.                        */
 197 /*------------------------------------------------------------------*/
 198
 199 /**------------------------------------------------------------------*/
 200 /*   Access routines for entities                                    */
 201 /**------------------------------------------------------------------*/
 202
 203 size_t get_entity_n_accesses(const ir_entity *ent)
 204 {
 205         ir_node ** accs;
 206
 207         assert(ent && is_entity(ent));
 208
 209         accs = get_entity_access_array(ent);
 210         return ARR_LEN(accs);
 211 }
 212
 213 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
 214 {
 215         ir_node ** accs;
 216
 217         assert(pos < get_entity_n_accesses(ent));
 218
 219         accs = get_entity_access_array(ent);
 220         return accs[pos];
 221 }
 222
 223 static void add_entity_access(const ir_entity *ent, ir_node *n)
 224 {
 225         ir_node ** accs;
 226
 227         assert(ent && is_entity(ent));
 228         assert(n && is_ir_node(n));
 229
 230         accs = get_entity_access_array(ent);
 231         ARR_APP1(ir_node *, accs, n);
 232         set_entity_access_array(ent, accs);
 233 }
 234
 235 #if 0
 236 void set_entity_access(const ir_entity *ent, int pos, ir_node *n)
 237 {
 238         ir_node ** accs;
 239
 240         assert(0 <= pos && pos < get_entity_n_accesses(ent));
 241         assert(n && is_ir_node(n));
 242
 243         accs = get_entity_access_array(ent);
 244         accs[pos] = n;
 245 }
 246 #endif
 247
 248 /*------------------------------------------------------------------*/
 249
 250 size_t get_entity_n_references(const ir_entity *ent)
 251 {
 252         ir_node ** refs;
 253
 254         assert(ent && is_entity(ent));
 255
 256         refs = get_entity_reference_array(ent);
 257         return ARR_LEN(refs);
 258 }
 259
 260 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
 261 {
 262         ir_node ** refs;
 263
 264         assert( pos < get_entity_n_references(ent));
 265
 266         refs = get_entity_reference_array(ent);
 267         return refs[pos];
 268 }
 269
 270 static void add_entity_reference(const ir_entity *ent, ir_node *n)
 271 {
 272         ir_node ** refs;
 273
 274         assert(ent && is_entity(ent));
 275         assert(n && is_ir_node(n));
 276
 277         refs = get_entity_reference_array(ent);
 278         ARR_APP1(ir_node *, refs, n);
 279         set_entity_reference_array(ent, refs);
 280 }
 281
 282 #if 0
 283 void set_entity_reference(const ir_entity *ent, int pos, ir_node *n)
 284 {
 285         ir_node ** refs;
 286
 287         assert(0 <= pos && pos < get_entity_n_references(ent));
 288         assert(n && is_ir_node(n));
 289
 290         refs = get_entity_reference_array(ent);
 291         refs[pos] = n;
 292 }
 293 #endif
 294
 295 /**------------------------------------------------------------------*/
 296 /*   Access routines for types                                       */
 297 /**------------------------------------------------------------------*/
 298
 299 /* Number of Alloc nodes that create an instance of this type */
 300 size_t get_type_n_allocs(const ir_type *tp)
 301 {
 302         ir_node **allocs;
 303
 304         assert(tp && is_type(tp));
 305
 306         allocs = get_type_alloc_array(tp);
 307         return ARR_LEN(allocs);
 308 }
 309
 310 /* Alloc node that creates an instance of this type */
 311 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
 312 {
 313         ir_node **allocs;
 314         assert( pos < get_type_n_allocs(tp));
 315
 316         allocs = get_type_alloc_array(tp);
 317         return allocs[pos];
 318 }
 319
 320 static void add_type_alloc(const ir_type *tp, ir_node *n)
 321 {
 322         ir_node **allocs;
 323
 324         assert(tp && is_type(tp));
 325         assert(n && is_ir_node(n));
 326
 327         allocs = get_type_alloc_array(tp);
 328         ARR_APP1(ir_node *, allocs, n);
 329         set_type_alloc_array(tp, allocs);
 330 }
 331
 332 #if 0
 333 void set_type_alloc(const ir_type *tp, int pos, ir_node *n)
 334 {
 335         ir_node **allocs;
 336
 337         assert(0 <= pos && pos < get_type_n_allocs(tp));
 338         assert(n && is_ir_node(n));
 339
 340         allocs = get_type_alloc_array(tp);
 341         allocs[pos] = n;
 342 }
 343 #endif
 344
 345 /* Number of Cast nodes that create an instance of this type */
 346 size_t get_type_n_casts(const ir_type *tp)
 347 {
 348         ir_node **casts;
 349
 350         assert(tp && is_type(tp));
 351
 352         casts = get_type_cast_array(tp);
 353         return ARR_LEN(casts);
 354 }
 355
 356
 357 size_t get_class_n_upcasts(const ir_type *clss)
 358 {
 359         size_t i, n_casts = get_type_n_casts(clss);
 360         size_t n_instances = 0;
 361         for (i = 0; i < n_casts; ++i) {
 362                 ir_node *cast = get_type_cast(clss, i);
 363                 if (is_Cast_upcast(cast))
 364                         ++n_instances;
 365         }
 366         return n_instances;
 367 }
 368
 369 size_t get_class_n_downcasts(const ir_type *clss)
 370 {
 371         size_t i, n_casts = get_type_n_casts(clss);
 372         size_t n_instances = 0;
 373         for (i = 0; i < n_casts; ++i) {
 374                 ir_node *cast = get_type_cast(clss, i);
 375                 if (is_Cast_downcast(cast))
 376                         ++n_instances;
 377         }
 378         return n_instances;
 379 }
 380
 381 ir_node *get_type_cast(const ir_type *tp, size_t pos)
 382 {
 383         ir_node **casts;
 384         assert(pos < get_type_n_casts(tp));
 385
 386         casts = get_type_cast_array(tp);
 387         return casts[pos];
 388 }
 389
 390 void add_type_cast(const ir_type *tp, ir_node *n)
 391 {
 392         ir_node **casts;
 393
 394         assert(tp && is_type(tp));
 395         assert(n && is_ir_node(n));
 396
 397         casts = get_type_cast_array(tp);
 398         ARR_APP1(ir_node *, casts, n);
 399         set_type_cast_array(tp, casts);
 400 }
 401
 402 #if 0
 403 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
 404 {
 405         ir_node **casts;
 406
 407         assert(pos < get_type_n_casts(tp));
 408         assert(n && is_ir_node(n));
 409
 410         casts = get_type_cast_array(tp);
 411         casts[pos] = n;
 412 }
 413 #endif
 414
 415 /*------------------------------------------------------------------*/
 416
 417 size_t get_type_n_pointertypes_to(const ir_type *tp)
 418 {
 419         ir_type ** pts;
 420
 421         assert(tp && is_type(tp));
 422
 423         pts = get_type_pointertype_array(tp);
 424         return ARR_LEN(pts);
 425 }
 426
 427 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
 428 {
 429         ir_type ** pts;
 430
 431         assert(pos < get_type_n_pointertypes_to(tp));
 432
 433         pts = get_type_pointertype_array(tp);
 434         return pts[pos];
 435 }
 436
 437 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
 438 {
 439         ir_type ** pts;
 440
 441         assert(tp && is_type(tp));
 442         assert(ptp && is_Pointer_type(ptp));
 443
 444         pts = get_type_pointertype_array(tp);
 445         ARR_APP1(ir_type*, pts, ptp);
 446         set_type_pointertype_array(tp, pts);
 447 }
 448
 449 #if 0
 450 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
 451 {
 452         ir_type ** pts;
 453
 454         assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
 455         assert(ptp && is_Pointer_type(ptp));
 456
 457         pts = get_type_pointertype_array(tp);
 458         pts[pos] = ptp;
 459 }
 460 #endif
 461
 462 /*------------------------------------------------------------------*/
 463
 464 size_t get_type_n_arraytypes_of(const ir_type *tp)
 465 {
 466         ir_type ** pts;
 467
 468         assert(tp && is_type(tp));
 469
 470         pts = get_type_arraytype_array(tp);
 471         return ARR_LEN(pts);
 472 }
 473
 474 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
 475 {
 476         ir_type ** pts;
 477
 478         assert(pos < get_type_n_arraytypes_of(tp));
 479
 480         pts = get_type_arraytype_array(tp);
 481         return pts[pos];
 482 }
 483
 484 void  add_type_arraytype_of(const ir_type *tp, ir_type *atp)
 485 {
 486         ir_type ** pts;
 487
 488         assert(tp && is_type(tp));
 489         assert(atp && is_Array_type(atp));
 490
 491         pts = get_type_arraytype_array(tp);
 492         ARR_APP1(ir_type*, pts, atp);
 493         set_type_arraytype_array(tp, pts);
 494 }
 495
 496 #if 0
 497 void  set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
 498 {
 499         ir_type ** pts;
 500
 501         assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
 502         assert(atp && is_Array_type(atp));
 503
 504         pts = get_type_arraytype_array(tp);
 505         pts[pos] = atp;
 506 }
 507 #endif
 508
 509 /*------------------------------------------------------------------*/
 510 /* Building and Removing the out datastructure                      */
 511 /*------------------------------------------------------------------*/
 512
 513 /** Initialize the trouts handling. */
 514 static void init_trouts(void)
 515 {
 516 }
 517
 518 /** The number of entities that can be accessed by this Sel node. */
 519 static int get_Sel_n_accessed_entities(const ir_node *sel)
 520 {
 521         (void) sel;
 522         return 1;
 523 }
 524
 525 /** The entity that cat be accessed by this Sel node. */
 526 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
 527 {
 528         return get_Sel_entity(sel);
 529 }
 530
 531 /** An addr node is a SymConst or a Sel. */
 532 static int get_addr_n_entities(const ir_node *addr)
 533 {
 534         switch (get_irn_opcode(addr)) {
 535         case iro_Sel:
 536                 /* Treat jack array sels? */
 537                 return get_Sel_n_accessed_entities(addr);
 538         case iro_SymConst:
 539                 if (get_SymConst_kind(addr) == symconst_addr_ent)
 540                         return 1;
 541                 return 0;
 542         default:
 543                 return 0;
 544         }
 545 }
 546
 547 /** An addr node is a SymConst or a Sel.
 548     If Sel follow to outermost of compound. */
 549 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
 550 {
 551         ir_node *ptr;
 552         (void) pos;
 553
 554         switch (get_irn_opcode(addr)) {
 555         case iro_Sel:
 556                 /* Treat jack array sels? They are compounds!  Follow to outermost entity.  */
 557                 ptr = get_Sel_ptr(addr);
 558                 while (is_Sel(ptr)) {
 559                         addr = ptr;
 560                         ptr  = get_Sel_ptr(addr);
 561                 }
 562                 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
 563                 return get_Sel_accessed_entity(addr);
 564         case iro_SymConst:
 565                 if (get_SymConst_kind(addr) == symconst_addr_ent) {
 566                         assert(pos == 0);
 567                         return get_SymConst_entity(addr);
 568                 }
 569                 return NULL;
 570         default:
 571                 return NULL;
 572         }
 573 }
 574
 575 static void chain_accesses(ir_node *n, void *env)
 576 {
 577         int i, n_ents;
 578         ir_node *addr;
 579
 580         (void) env;
 581         if (is_Alloc(n)) {
 582                 add_type_alloc(get_Alloc_type(n), n);
 583                 return;
 584         } else if (is_Cast(n)) {
 585                 add_type_cast(get_Cast_type(n), n);
 586                 return;
 587         } else if (is_Sel(n)) {
 588                 add_entity_reference(get_Sel_entity(n), n);
 589                 return;
 590         } else if (is_SymConst_addr_ent(n)) {
 591                 add_entity_reference(get_SymConst_entity(n), n);
 592                 return;
 593         } else if (is_Store(n)) {
 594                 addr = get_Store_ptr(n);
 595         } else if (is_Load(n)) {
 596                 addr = get_Load_ptr(n);
 597         } else if (is_Call(n)) {
 598                 addr = get_Call_ptr(n);
 599                 if (! is_Sel(addr)) return;  /* Sels before Calls mean a Load / polymorphic Call. */
 600         } else {
 601                 return;
 602         }
 603
 604         n_ents = get_addr_n_entities(addr);  /* == 1 */
 605         for (i = 0; i < n_ents; ++i) {
 606                 ir_entity *ent = get_addr_entity(addr, i);
 607                 if (ent)
 608                         add_entity_access(ent, n);
 609                 //else
 610                 //add_unrecognized_access(n);
 611         }
 612 }
 613
 614 /**
 615  * Handle chain types (pointer, array) by adding them to
 616  * its "inner" type.
 617  */
 618 static void chain_types(ir_type *tp)
 619 {
 620         if (is_Pointer_type(tp)) {
 621                 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
 622         } else if (is_Array_type(tp)) {
 623                 add_type_arraytype_of(get_array_element_type(tp), tp);
 624         }
 625 }
 626
 627 void compute_trouts(void)
 628 {
 629         size_t i;
 630
 631         free_trouts();
 632         init_trouts();
 633
 634         /* Compute outs for IR nodes. */
 635         for (i = get_irp_n_irgs(); i > 0;) {
 636                 ir_graph *irg = get_irp_irg(--i);
 637                 irg_walk_graph(irg, NULL, chain_accesses, NULL);
 638         }
 639         walk_const_code(NULL, chain_accesses, NULL);
 640
 641         /* Compute outs for types */
 642         for (i = get_irp_n_types(); i > 0;) {
 643                 ir_type *type = get_irp_type(--i);
 644                 chain_types(type);
 645         }
 646 }
 647
 648 void free_trouts(void)
 649 {
 650         if (entity_access_map) {
 651                 ir_node **accs;
 652                 for (accs = (ir_node **)pmap_first(entity_access_map);
 653                         accs;
 654                         accs = (ir_node **)pmap_next(entity_access_map)) {
 655                         /* DEL_ARR_F(accs); */
 656                 }
 657                 pmap_destroy(entity_access_map);
 658                 entity_access_map = NULL;
 659         }
 660
 661         if (entity_reference_map) {
 662                 ir_node **refs;
 663                 for (refs = (ir_node **)pmap_first(entity_reference_map);
 664                         refs;
 665                         refs = (ir_node **)pmap_next(entity_reference_map)) {
 666                         /* DEL_ARR_F(refs); */
 667                 }
 668                 pmap_destroy(entity_reference_map);
 669                 entity_reference_map = NULL;
 670         }
 671
 672         if (type_alloc_map) {
 673                 ir_node **alls;
 674                 for (alls = (ir_node **)pmap_first(type_alloc_map);
 675                         alls;
 676                         alls = (ir_node **)pmap_next(type_alloc_map)) {
 677                         /* DEL_ARR_F(alls); */
 678                 }
 679                 pmap_destroy(type_alloc_map);
 680                 type_alloc_map = NULL;
 681         }
 682
 683         if (type_cast_map) {
 684                 ir_node **casts;
 685                 for (casts = (ir_node **)pmap_first(type_cast_map);
 686                         casts;
 687                         casts = (ir_node **)pmap_next(type_cast_map)) {
 688                         /* DEL_ARR_F(alls); */
 689                 }
 690                 pmap_destroy(type_cast_map);
 691                 type_cast_map = NULL;
 692         }
 693
 694         if (type_pointertype_map) {
 695                 ir_node **pts;
 696                 for (pts = (ir_node **)pmap_first(type_pointertype_map);
 697                         pts;
 698                         pts = (ir_node **)pmap_next(type_pointertype_map)) {
 699                         /* DEL_ARR_F(pts); */
 700                 }
 701                 pmap_destroy(type_pointertype_map);
 702                 type_pointertype_map = NULL;
 703         }
 704
 705         if (type_arraytype_map) {
 706                 ir_node **pts;
 707                 for (pts = (ir_node **)pmap_first(type_arraytype_map);
 708                         pts;
 709                         pts = (ir_node **)pmap_next(type_arraytype_map)) {
 710                         /* DEL_ARR_F(pts); */
 711                 }
 712                 pmap_destroy(type_arraytype_map);
 713                 type_arraytype_map = NULL;
 714         }
 715 }