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