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