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