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 /*------------------------------------------------------------------*/
 224
 225 size_t get_entity_n_references(const ir_entity *ent)
 226 {
 227         ir_node ** refs;
 228
 229         assert(ent && is_entity(ent));
 230
 231         refs = get_entity_reference_array(ent);
 232         return ARR_LEN(refs);
 233 }
 234
 235 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
 236 {
 237         ir_node ** refs;
 238
 239         assert( pos < get_entity_n_references(ent));
 240
 241         refs = get_entity_reference_array(ent);
 242         return refs[pos];
 243 }
 244
 245 static void add_entity_reference(const ir_entity *ent, ir_node *n)
 246 {
 247         ir_node ** refs;
 248
 249         assert(ent && is_entity(ent));
 250         assert(n && is_ir_node(n));
 251
 252         refs = get_entity_reference_array(ent);
 253         ARR_APP1(ir_node *, refs, n);
 254         set_entity_reference_array(ent, refs);
 255 }
 256
 257 /**------------------------------------------------------------------*/
 258 /*   Access routines for types                                       */
 259 /**------------------------------------------------------------------*/
 260
 261 /* Number of Alloc nodes that create an instance of this type */
 262 size_t get_type_n_allocs(const ir_type *tp)
 263 {
 264         ir_node **allocs;
 265
 266         assert(tp && is_type(tp));
 267
 268         allocs = get_type_alloc_array(tp);
 269         return ARR_LEN(allocs);
 270 }
 271
 272 /* Alloc node that creates an instance of this type */
 273 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
 274 {
 275         ir_node **allocs;
 276         assert( pos < get_type_n_allocs(tp));
 277
 278         allocs = get_type_alloc_array(tp);
 279         return allocs[pos];
 280 }
 281
 282 static void add_type_alloc(const ir_type *tp, ir_node *n)
 283 {
 284         ir_node **allocs;
 285
 286         assert(tp && is_type(tp));
 287         assert(n && is_ir_node(n));
 288
 289         allocs = get_type_alloc_array(tp);
 290         ARR_APP1(ir_node *, allocs, n);
 291         set_type_alloc_array(tp, allocs);
 292 }
 293
 294 /* Number of Cast nodes that create an instance of this type */
 295 size_t get_type_n_casts(const ir_type *tp)
 296 {
 297         ir_node **casts;
 298
 299         assert(tp && is_type(tp));
 300
 301         casts = get_type_cast_array(tp);
 302         return ARR_LEN(casts);
 303 }
 304
 305
 306 size_t get_class_n_upcasts(const ir_type *clss)
 307 {
 308         size_t i, n_casts = get_type_n_casts(clss);
 309         size_t n_instances = 0;
 310         for (i = 0; i < n_casts; ++i) {
 311                 ir_node *cast = get_type_cast(clss, i);
 312                 if (is_Cast_upcast(cast))
 313                         ++n_instances;
 314         }
 315         return n_instances;
 316 }
 317
 318 size_t get_class_n_downcasts(const ir_type *clss)
 319 {
 320         size_t i, n_casts = get_type_n_casts(clss);
 321         size_t n_instances = 0;
 322         for (i = 0; i < n_casts; ++i) {
 323                 ir_node *cast = get_type_cast(clss, i);
 324                 if (is_Cast_downcast(cast))
 325                         ++n_instances;
 326         }
 327         return n_instances;
 328 }
 329
 330 ir_node *get_type_cast(const ir_type *tp, size_t pos)
 331 {
 332         ir_node **casts;
 333         assert(pos < get_type_n_casts(tp));
 334
 335         casts = get_type_cast_array(tp);
 336         return casts[pos];
 337 }
 338
 339 void add_type_cast(const ir_type *tp, ir_node *n)
 340 {
 341         ir_node **casts;
 342
 343         assert(tp && is_type(tp));
 344         assert(n && is_ir_node(n));
 345
 346         casts = get_type_cast_array(tp);
 347         ARR_APP1(ir_node *, casts, n);
 348         set_type_cast_array(tp, casts);
 349 }
 350
 351 /*------------------------------------------------------------------*/
 352
 353 size_t get_type_n_pointertypes_to(const ir_type *tp)
 354 {
 355         ir_type ** pts;
 356
 357         assert(tp && is_type(tp));
 358
 359         pts = get_type_pointertype_array(tp);
 360         return ARR_LEN(pts);
 361 }
 362
 363 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
 364 {
 365         ir_type ** pts;
 366
 367         assert(pos < get_type_n_pointertypes_to(tp));
 368
 369         pts = get_type_pointertype_array(tp);
 370         return pts[pos];
 371 }
 372
 373 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
 374 {
 375         ir_type ** pts;
 376
 377         assert(tp && is_type(tp));
 378         assert(ptp && is_Pointer_type(ptp));
 379
 380         pts = get_type_pointertype_array(tp);
 381         ARR_APP1(ir_type*, pts, ptp);
 382         set_type_pointertype_array(tp, pts);
 383 }
 384
 385 /*------------------------------------------------------------------*/
 386
 387 size_t get_type_n_arraytypes_of(const ir_type *tp)
 388 {
 389         ir_type ** pts;
 390
 391         assert(tp && is_type(tp));
 392
 393         pts = get_type_arraytype_array(tp);
 394         return ARR_LEN(pts);
 395 }
 396
 397 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
 398 {
 399         ir_type ** pts;
 400
 401         assert(pos < get_type_n_arraytypes_of(tp));
 402
 403         pts = get_type_arraytype_array(tp);
 404         return pts[pos];
 405 }
 406
 407 void  add_type_arraytype_of(const ir_type *tp, ir_type *atp)
 408 {
 409         ir_type ** pts;
 410
 411         assert(tp && is_type(tp));
 412         assert(atp && is_Array_type(atp));
 413
 414         pts = get_type_arraytype_array(tp);
 415         ARR_APP1(ir_type*, pts, atp);
 416         set_type_arraytype_array(tp, pts);
 417 }
 418
 419 /*------------------------------------------------------------------*/
 420 /* Building and Removing the out datastructure                      */
 421 /*------------------------------------------------------------------*/
 422
 423 /** Initialize the trouts handling. */
 424 static void init_trouts(void)
 425 {
 426 }
 427
 428 /** The number of entities that can be accessed by this Sel node. */
 429 static int get_Sel_n_accessed_entities(const ir_node *sel)
 430 {
 431         (void) sel;
 432         return 1;
 433 }
 434
 435 /** The entity that cat be accessed by this Sel node. */
 436 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
 437 {
 438         return get_Sel_entity(sel);
 439 }
 440
 441 /** An addr node is a SymConst or a Sel. */
 442 static int get_addr_n_entities(const ir_node *addr)
 443 {
 444         switch (get_irn_opcode(addr)) {
 445         case iro_Sel:
 446                 /* Treat jack array sels? */
 447                 return get_Sel_n_accessed_entities(addr);
 448         case iro_SymConst:
 449                 if (get_SymConst_kind(addr) == symconst_addr_ent)
 450                         return 1;
 451                 return 0;
 452         default:
 453                 return 0;
 454         }
 455 }
 456
 457 /** An addr node is a SymConst or a Sel.
 458     If Sel follow to outermost of compound. */
 459 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
 460 {
 461         ir_node *ptr;
 462         (void) pos;
 463
 464         switch (get_irn_opcode(addr)) {
 465         case iro_Sel:
 466                 /* Treat jack array sels? They are compounds!  Follow to outermost entity.  */
 467                 ptr = get_Sel_ptr(addr);
 468                 while (is_Sel(ptr)) {
 469                         addr = ptr;
 470                         ptr  = get_Sel_ptr(addr);
 471                 }
 472                 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
 473                 return get_Sel_accessed_entity(addr);
 474         case iro_SymConst:
 475                 if (get_SymConst_kind(addr) == symconst_addr_ent) {
 476                         assert(pos == 0);
 477                         return get_SymConst_entity(addr);
 478                 }
 479                 return NULL;
 480         default:
 481                 return NULL;
 482         }
 483 }
 484
 485 static void chain_accesses(ir_node *n, void *env)
 486 {
 487         int i, n_ents;
 488         ir_node *addr;
 489
 490         (void) env;
 491         if (is_Alloc(n)) {
 492                 add_type_alloc(get_Alloc_type(n), n);
 493                 return;
 494         } else if (is_Cast(n)) {
 495                 add_type_cast(get_Cast_type(n), n);
 496                 return;
 497         } else if (is_Sel(n)) {
 498                 add_entity_reference(get_Sel_entity(n), n);
 499                 return;
 500         } else if (is_SymConst_addr_ent(n)) {
 501                 add_entity_reference(get_SymConst_entity(n), n);
 502                 return;
 503         } else if (is_Store(n)) {
 504                 addr = get_Store_ptr(n);
 505         } else if (is_Load(n)) {
 506                 addr = get_Load_ptr(n);
 507         } else if (is_Call(n)) {
 508                 addr = get_Call_ptr(n);
 509                 if (! is_Sel(addr)) return;  /* Sels before Calls mean a Load / polymorphic Call. */
 510         } else {
 511                 return;
 512         }
 513
 514         n_ents = get_addr_n_entities(addr);  /* == 1 */
 515         for (i = 0; i < n_ents; ++i) {
 516                 ir_entity *ent = get_addr_entity(addr, i);
 517                 if (ent)
 518                         add_entity_access(ent, n);
 519                 //else
 520                 //add_unrecognized_access(n);
 521         }
 522 }
 523
 524 /**
 525  * Handle chain types (pointer, array) by adding them to
 526  * its "inner" type.
 527  */
 528 static void chain_types(ir_type *tp)
 529 {
 530         if (is_Pointer_type(tp)) {
 531                 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
 532         } else if (is_Array_type(tp)) {
 533                 add_type_arraytype_of(get_array_element_type(tp), tp);
 534         }
 535 }
 536
 537 void compute_trouts(void)
 538 {
 539         size_t i;
 540
 541         free_trouts();
 542         init_trouts();
 543
 544         /* Compute outs for IR nodes. */
 545         for (i = get_irp_n_irgs(); i > 0;) {
 546                 ir_graph *irg = get_irp_irg(--i);
 547                 irg_walk_graph(irg, NULL, chain_accesses, NULL);
 548         }
 549         walk_const_code(NULL, chain_accesses, NULL);
 550
 551         /* Compute outs for types */
 552         for (i = get_irp_n_types(); i > 0;) {
 553                 ir_type *type = get_irp_type(--i);
 554                 chain_types(type);
 555         }
 556 }
 557
 558 void free_trouts(void)
 559 {
 560         if (entity_access_map) {
 561                 ir_node **accs;
 562                 for (accs = (ir_node **)pmap_first(entity_access_map);
 563                         accs;
 564                         accs = (ir_node **)pmap_next(entity_access_map)) {
 565                         /* DEL_ARR_F(accs); */
 566                 }
 567                 pmap_destroy(entity_access_map);
 568                 entity_access_map = NULL;
 569         }
 570
 571         if (entity_reference_map) {
 572                 ir_node **refs;
 573                 for (refs = (ir_node **)pmap_first(entity_reference_map);
 574                         refs;
 575                         refs = (ir_node **)pmap_next(entity_reference_map)) {
 576                         /* DEL_ARR_F(refs); */
 577                 }
 578                 pmap_destroy(entity_reference_map);
 579                 entity_reference_map = NULL;
 580         }
 581
 582         if (type_alloc_map) {
 583                 ir_node **alls;
 584                 for (alls = (ir_node **)pmap_first(type_alloc_map);
 585                         alls;
 586                         alls = (ir_node **)pmap_next(type_alloc_map)) {
 587                         /* DEL_ARR_F(alls); */
 588                 }
 589                 pmap_destroy(type_alloc_map);
 590                 type_alloc_map = NULL;
 591         }
 592
 593         if (type_cast_map) {
 594                 ir_node **casts;
 595                 for (casts = (ir_node **)pmap_first(type_cast_map);
 596                         casts;
 597                         casts = (ir_node **)pmap_next(type_cast_map)) {
 598                         /* DEL_ARR_F(alls); */
 599                 }
 600                 pmap_destroy(type_cast_map);
 601                 type_cast_map = NULL;
 602         }
 603
 604         if (type_pointertype_map) {
 605                 ir_node **pts;
 606                 for (pts = (ir_node **)pmap_first(type_pointertype_map);
 607                         pts;
 608                         pts = (ir_node **)pmap_next(type_pointertype_map)) {
 609                         /* DEL_ARR_F(pts); */
 610                 }
 611                 pmap_destroy(type_pointertype_map);
 612                 type_pointertype_map = NULL;
 613         }
 614
 615         if (type_arraytype_map) {
 616                 ir_node **pts;
 617                 for (pts = (ir_node **)pmap_first(type_arraytype_map);
 618                         pts;
 619                         pts = (ir_node **)pmap_next(type_arraytype_map)) {
 620                         /* DEL_ARR_F(pts); */
 621                 }
 622                 pmap_destroy(type_arraytype_map);
 623                 type_arraytype_map = NULL;
 624         }
 625 }