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