nsz Git - libfirm/blob - ir/ana/trouts.c

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