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 ir_node *get_type_cast(const ir_type *tp, size_t pos)
 394 {
 395         ir_node **casts;
 396         assert(pos < get_type_n_casts(tp));
 397
 398         casts = get_type_cast_array(tp);
 399         return casts[pos];
 400 }
 401
 402 void add_type_cast(const ir_type *tp, ir_node *n)
 403 {
 404         ir_node **casts;
 405
 406         assert(tp && is_type(tp));
 407         assert(n && is_ir_node(n));
 408
 409         casts = get_type_cast_array(tp);
 410         ARR_APP1(ir_node *, casts, n);
 411         set_type_cast_array(tp, casts);
 412 }
 413
 414 #if 0
 415 void set_type_cast(const ir_type *tp, size_t pos, ir_node *n)
 416 {
 417         ir_node **casts;
 418
 419         assert(pos < get_type_n_casts(tp));
 420         assert(n && is_ir_node(n));
 421
 422         casts = get_type_cast_array(tp);
 423         casts[pos] = n;
 424 }
 425 #endif
 426
 427 /*------------------------------------------------------------------*/
 428
 429 size_t get_type_n_pointertypes_to(const ir_type *tp)
 430 {
 431         ir_type ** pts;
 432
 433         assert(tp && is_type(tp));
 434
 435         pts = get_type_pointertype_array(tp);
 436         return ARR_LEN(pts);
 437 }
 438
 439 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
 440 {
 441         ir_type ** pts;
 442
 443         assert(pos < get_type_n_pointertypes_to(tp));
 444
 445         pts = get_type_pointertype_array(tp);
 446         return pts[pos];
 447 }
 448
 449 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
 450 {
 451         ir_type ** pts;
 452
 453         assert(tp && is_type(tp));
 454         assert(ptp && is_Pointer_type(ptp));
 455
 456         pts = get_type_pointertype_array(tp);
 457         ARR_APP1(ir_type*, pts, ptp);
 458         set_type_pointertype_array(tp, pts);
 459 }
 460
 461 #if 0
 462 void set_type_pointertype_to(const ir_type *tp, int pos, ir_type *ptp)
 463 {
 464         ir_type ** pts;
 465
 466         assert(0 <= pos && pos < get_type_n_pointertypes_to(tp));
 467         assert(ptp && is_Pointer_type(ptp));
 468
 469         pts = get_type_pointertype_array(tp);
 470         pts[pos] = ptp;
 471 }
 472 #endif
 473
 474 /*------------------------------------------------------------------*/
 475
 476 size_t get_type_n_arraytypes_of(const ir_type *tp)
 477 {
 478         ir_type ** pts;
 479
 480         assert(tp && is_type(tp));
 481
 482         pts = get_type_arraytype_array(tp);
 483         return ARR_LEN(pts);
 484 }
 485
 486 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
 487 {
 488         ir_type ** pts;
 489
 490         assert(pos < get_type_n_arraytypes_of(tp));
 491
 492         pts = get_type_arraytype_array(tp);
 493         return pts[pos];
 494 }
 495
 496 void  add_type_arraytype_of(const ir_type *tp, ir_type *atp)
 497 {
 498         ir_type ** pts;
 499
 500         assert(tp && is_type(tp));
 501         assert(atp && is_Array_type(atp));
 502
 503         pts = get_type_arraytype_array(tp);
 504         ARR_APP1(ir_type*, pts, atp);
 505         set_type_arraytype_array(tp, pts);
 506 }
 507
 508 #if 0
 509 void  set_type_arraytype_of(const ir_type *tp, int pos, ir_type *atp)
 510 {
 511         ir_type ** pts;
 512
 513         assert(0 <= pos && pos < get_type_n_arraytypes_of(tp));
 514         assert(atp && is_Array_type(atp));
 515
 516         pts = get_type_arraytype_array(tp);
 517         pts[pos] = atp;
 518 }
 519 #endif
 520
 521 /*------------------------------------------------------------------*/
 522 /* Building and Removing the out datastructure                      */
 523 /*------------------------------------------------------------------*/
 524
 525 /** Initialize the trouts handling. */
 526 static void init_trouts(void)
 527 {
 528 }
 529
 530 /** The number of entities that can be accessed by this Sel node. */
 531 static int get_Sel_n_accessed_entities(const ir_node *sel)
 532 {
 533         (void) sel;
 534         return 1;
 535 }
 536
 537 /** The entity that cat be accessed by this Sel node. */
 538 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
 539 {
 540         return get_Sel_entity(sel);
 541 }
 542
 543 /** An addr node is a SymConst or a Sel. */
 544 static int get_addr_n_entities(const ir_node *addr)
 545 {
 546         switch (get_irn_opcode(addr)) {
 547         case iro_Sel:
 548                 /* Treat jack array sels? */
 549                 return get_Sel_n_accessed_entities(addr);
 550         case iro_SymConst:
 551                 if (get_SymConst_kind(addr) == symconst_addr_ent)
 552                         return 1;
 553                 return 0;
 554         default:
 555                 return 0;
 556         }
 557 }
 558
 559 /** An addr node is a SymConst or a Sel.
 560     If Sel follow to outermost of compound. */
 561 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
 562 {
 563         ir_node *ptr;
 564         (void) pos;
 565
 566         switch (get_irn_opcode(addr)) {
 567         case iro_Sel:
 568                 /* Treat jack array sels? They are compounds!  Follow to outermost entity.  */
 569                 ptr = get_Sel_ptr(addr);
 570                 while (is_Sel(ptr)) {
 571                         addr = ptr;
 572                         ptr  = get_Sel_ptr(addr);
 573                 }
 574                 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
 575                 return get_Sel_accessed_entity(addr);
 576         case iro_SymConst:
 577                 if (get_SymConst_kind(addr) == symconst_addr_ent) {
 578                         assert(pos == 0);
 579                         return get_SymConst_entity(addr);
 580                 }
 581                 return NULL;
 582         default:
 583                 return NULL;
 584         }
 585 }
 586
 587 static void chain_accesses(ir_node *n, void *env)
 588 {
 589         int i, n_ents;
 590         ir_node *addr;
 591
 592         (void) env;
 593         if (is_Alloc(n)) {
 594                 add_type_alloc(get_Alloc_type(n), n);
 595                 return;
 596         } else if (is_Cast(n)) {
 597                 add_type_cast(get_Cast_type(n), n);
 598                 return;
 599         } else if (is_Sel(n)) {
 600                 add_entity_reference(get_Sel_entity(n), n);
 601                 return;
 602         } else if (is_SymConst_addr_ent(n)) {
 603                 add_entity_reference(get_SymConst_entity(n), n);
 604                 return;
 605         } else if (is_Store(n)) {
 606                 addr = get_Store_ptr(n);
 607         } else if (is_Load(n)) {
 608                 addr = get_Load_ptr(n);
 609         } else if (is_Call(n)) {
 610                 addr = get_Call_ptr(n);
 611                 if (! is_Sel(addr)) return;  /* Sels before Calls mean a Load / polymorphic Call. */
 612         } else {
 613                 return;
 614         }
 615
 616         n_ents = get_addr_n_entities(addr);  /* == 1 */
 617         for (i = 0; i < n_ents; ++i) {
 618                 ir_entity *ent = get_addr_entity(addr, i);
 619                 if (ent)
 620                         add_entity_access(ent, n);
 621                 //else
 622                 //add_unrecognized_access(n);
 623         }
 624 }
 625
 626 /**
 627  * Handle chain types (pointer, array) by adding them to
 628  * its "inner" type.
 629  */
 630 static void chain_types(ir_type *tp)
 631 {
 632         if (is_Pointer_type(tp)) {
 633                 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
 634         } else if (is_Array_type(tp)) {
 635                 add_type_arraytype_of(get_array_element_type(tp), tp);
 636         }
 637 }
 638
 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 }