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_pointertype_map = NULL;
  47 static pmap *type_arraytype_map = NULL;
  48
  49 /**
  50  * Return a flexible array containing all IR-nodes
  51  * that access a given entity.
  52  */
  53 static ir_node **get_entity_access_array(const ir_entity *ent)
  54 {
  55         if (!entity_access_map) entity_access_map = pmap_create();
  56
  57         ir_node **res = pmap_get(ir_node*, entity_access_map, ent);
  58         if (!res) {
  59                 res = NEW_ARR_F(ir_node *, 0);
  60                 pmap_insert(entity_access_map, ent, (void *)res);
  61         }
  62
  63         return res;
  64 }
  65
  66 static void set_entity_access_array(const ir_entity *ent, ir_node **accs)
  67 {
  68         pmap_insert(entity_access_map, ent, (void *)accs);
  69 }
  70
  71 /**
  72  * Return a flexible array containing all IR-nodes
  73  * that reference a given entity.
  74  */
  75 static ir_node **get_entity_reference_array(const ir_entity *ent)
  76 {
  77         if (!entity_reference_map) entity_reference_map = pmap_create();
  78
  79         ir_node **res = pmap_get(ir_node*, entity_reference_map, ent);
  80         if (!res) {
  81                 res = NEW_ARR_F(ir_node *, 0);
  82                 pmap_insert(entity_reference_map, ent, (void *)res);
  83         }
  84
  85         return res;
  86 }
  87
  88 static void set_entity_reference_array(const ir_entity *ent, ir_node **refs)
  89 {
  90         pmap_insert(entity_reference_map, ent, (void *)refs);
  91 }
  92
  93 /**
  94  * Return a flexible array containing all IR-nodes
  95  * that allocate a given type.
  96  */
  97 static ir_node **get_type_alloc_array(const ir_type *tp)
  98 {
  99         if (!type_alloc_map) type_alloc_map = pmap_create();
 100
 101         ir_node **res = pmap_get(ir_node*, type_alloc_map, tp);
 102         if (!res) {
 103                 res = NEW_ARR_F(ir_node *, 0);
 104                 pmap_insert(type_alloc_map, tp, (void *)res);
 105         }
 106
 107         return res;
 108 }
 109
 110 static void set_type_alloc_array(const ir_type *tp, ir_node **alls)
 111 {
 112         pmap_insert(type_alloc_map, tp, (void *)alls);
 113 }
 114
 115 /**
 116  * Return a flexible array containing all pointer
 117  * types that points-to a given type.
 118  */
 119 static ir_type **get_type_pointertype_array(const ir_type *tp)
 120 {
 121         if (!type_pointertype_map) type_pointertype_map = pmap_create();
 122
 123         ir_type **res = pmap_get(ir_type*, type_pointertype_map, tp);
 124         if (!res) {
 125                 res = NEW_ARR_F(ir_type *, 0);
 126                 pmap_insert(type_pointertype_map, tp, (void *)res);
 127         }
 128
 129         return res;
 130 }
 131
 132 static void set_type_pointertype_array(const ir_type *tp, ir_type **pts)
 133 {
 134         pmap_insert(type_pointertype_map, tp, (void *)pts);
 135 }
 136
 137 /**
 138  * Return a flexible array containing all array
 139  * types that have a given type as element type.
 140  */
 141 static ir_type **get_type_arraytype_array(const ir_type *tp)
 142 {
 143         if (!type_arraytype_map) type_arraytype_map = pmap_create();
 144
 145         ir_type **res = pmap_get(ir_type*, type_arraytype_map, tp);
 146         if (!res) {
 147                 res = NEW_ARR_F(ir_type *, 0);
 148                 pmap_insert(type_arraytype_map, tp, (void *)res);
 149         }
 150
 151         return res;
 152 }
 153
 154 static void set_type_arraytype_array(const ir_type *tp, ir_type **pts)
 155 {
 156         pmap_insert(type_arraytype_map, tp, (void *)pts);
 157 }
 158
 159 /*------------------------------------------------------------------*/
 160 /* Accessing the out data structures.                               */
 161 /* These routines only work properly if firm is in state            */
 162 /* trouts_consistent or trouts_inconsistent.                        */
 163 /*------------------------------------------------------------------*/
 164
 165 /**------------------------------------------------------------------*/
 166 /*   Access routines for entities                                    */
 167 /**------------------------------------------------------------------*/
 168
 169 size_t get_entity_n_accesses(const ir_entity *ent)
 170 {
 171         ir_node ** accs;
 172
 173         assert(ent && is_entity(ent));
 174
 175         accs = get_entity_access_array(ent);
 176         return ARR_LEN(accs);
 177 }
 178
 179 ir_node *get_entity_access(const ir_entity *ent, size_t pos)
 180 {
 181         ir_node ** accs;
 182
 183         assert(pos < get_entity_n_accesses(ent));
 184
 185         accs = get_entity_access_array(ent);
 186         return accs[pos];
 187 }
 188
 189 static void add_entity_access(const ir_entity *ent, ir_node *n)
 190 {
 191         ir_node ** accs;
 192
 193         assert(ent && is_entity(ent));
 194         assert(n && is_ir_node(n));
 195
 196         accs = get_entity_access_array(ent);
 197         ARR_APP1(ir_node *, accs, n);
 198         set_entity_access_array(ent, accs);
 199 }
 200
 201 /*------------------------------------------------------------------*/
 202
 203 size_t get_entity_n_references(const ir_entity *ent)
 204 {
 205         ir_node ** refs;
 206
 207         assert(ent && is_entity(ent));
 208
 209         refs = get_entity_reference_array(ent);
 210         return ARR_LEN(refs);
 211 }
 212
 213 ir_node *get_entity_reference(const ir_entity *ent, size_t pos)
 214 {
 215         ir_node ** refs;
 216
 217         assert( pos < get_entity_n_references(ent));
 218
 219         refs = get_entity_reference_array(ent);
 220         return refs[pos];
 221 }
 222
 223 static void add_entity_reference(const ir_entity *ent, ir_node *n)
 224 {
 225         ir_node ** refs;
 226
 227         assert(ent && is_entity(ent));
 228         assert(n && is_ir_node(n));
 229
 230         refs = get_entity_reference_array(ent);
 231         ARR_APP1(ir_node *, refs, n);
 232         set_entity_reference_array(ent, refs);
 233 }
 234
 235 /**------------------------------------------------------------------*/
 236 /*   Access routines for types                                       */
 237 /**------------------------------------------------------------------*/
 238
 239 /* Number of Alloc nodes that create an instance of this type */
 240 size_t get_type_n_allocs(const ir_type *tp)
 241 {
 242         ir_node **allocs;
 243
 244         assert(tp && is_type(tp));
 245
 246         allocs = get_type_alloc_array(tp);
 247         return ARR_LEN(allocs);
 248 }
 249
 250 /* Alloc node that creates an instance of this type */
 251 ir_node *get_type_alloc(const ir_type *tp, size_t pos)
 252 {
 253         ir_node **allocs;
 254         assert( pos < get_type_n_allocs(tp));
 255
 256         allocs = get_type_alloc_array(tp);
 257         return allocs[pos];
 258 }
 259
 260 static void add_type_alloc(const ir_type *tp, ir_node *n)
 261 {
 262         ir_node **allocs;
 263
 264         assert(tp && is_type(tp));
 265         assert(n && is_ir_node(n));
 266
 267         allocs = get_type_alloc_array(tp);
 268         ARR_APP1(ir_node *, allocs, n);
 269         set_type_alloc_array(tp, allocs);
 270 }
 271
 272 /*------------------------------------------------------------------*/
 273
 274 size_t get_type_n_pointertypes_to(const ir_type *tp)
 275 {
 276         ir_type ** pts;
 277
 278         assert(tp && is_type(tp));
 279
 280         pts = get_type_pointertype_array(tp);
 281         return ARR_LEN(pts);
 282 }
 283
 284 ir_type *get_type_pointertype_to(const ir_type *tp, size_t pos)
 285 {
 286         ir_type ** pts;
 287
 288         assert(pos < get_type_n_pointertypes_to(tp));
 289
 290         pts = get_type_pointertype_array(tp);
 291         return pts[pos];
 292 }
 293
 294 void add_type_pointertype_to(const ir_type *tp, ir_type *ptp)
 295 {
 296         ir_type ** pts;
 297
 298         assert(tp && is_type(tp));
 299         assert(ptp && is_Pointer_type(ptp));
 300
 301         pts = get_type_pointertype_array(tp);
 302         ARR_APP1(ir_type*, pts, ptp);
 303         set_type_pointertype_array(tp, pts);
 304 }
 305
 306 /*------------------------------------------------------------------*/
 307
 308 size_t get_type_n_arraytypes_of(const ir_type *tp)
 309 {
 310         ir_type ** pts;
 311
 312         assert(tp && is_type(tp));
 313
 314         pts = get_type_arraytype_array(tp);
 315         return ARR_LEN(pts);
 316 }
 317
 318 ir_type *get_type_arraytype_of(const ir_type *tp, size_t pos)
 319 {
 320         ir_type ** pts;
 321
 322         assert(pos < get_type_n_arraytypes_of(tp));
 323
 324         pts = get_type_arraytype_array(tp);
 325         return pts[pos];
 326 }
 327
 328 void  add_type_arraytype_of(const ir_type *tp, ir_type *atp)
 329 {
 330         ir_type ** pts;
 331
 332         assert(tp && is_type(tp));
 333         assert(atp && is_Array_type(atp));
 334
 335         pts = get_type_arraytype_array(tp);
 336         ARR_APP1(ir_type*, pts, atp);
 337         set_type_arraytype_array(tp, pts);
 338 }
 339
 340 /*------------------------------------------------------------------*/
 341 /* Building and Removing the out datastructure                      */
 342 /*------------------------------------------------------------------*/
 343
 344 /** Initialize the trouts handling. */
 345 static void init_trouts(void)
 346 {
 347 }
 348
 349 /** The number of entities that can be accessed by this Sel node. */
 350 static int get_Sel_n_accessed_entities(const ir_node *sel)
 351 {
 352         (void) sel;
 353         return 1;
 354 }
 355
 356 /** The entity that cat be accessed by this Sel node. */
 357 static ir_entity *get_Sel_accessed_entity(const ir_node *sel)
 358 {
 359         return get_Sel_entity(sel);
 360 }
 361
 362 /** An addr node is a SymConst or a Sel. */
 363 static int get_addr_n_entities(const ir_node *addr)
 364 {
 365         switch (get_irn_opcode(addr)) {
 366         case iro_Sel:
 367                 /* Treat jack array sels? */
 368                 return get_Sel_n_accessed_entities(addr);
 369         case iro_SymConst:
 370                 if (get_SymConst_kind(addr) == symconst_addr_ent)
 371                         return 1;
 372                 return 0;
 373         default:
 374                 return 0;
 375         }
 376 }
 377
 378 /** An addr node is a SymConst or a Sel.
 379     If Sel follow to outermost of compound. */
 380 static ir_entity *get_addr_entity(const ir_node *addr, int pos)
 381 {
 382         ir_node *ptr;
 383         (void) pos;
 384
 385         switch (get_irn_opcode(addr)) {
 386         case iro_Sel:
 387                 /* Treat jack array sels? They are compounds!  Follow to outermost entity.  */
 388                 ptr = get_Sel_ptr(addr);
 389                 while (is_Sel(ptr)) {
 390                         addr = ptr;
 391                         ptr  = get_Sel_ptr(addr);
 392                 }
 393                 assert(0 <= pos && pos < get_Sel_n_accessed_entities(addr));
 394                 return get_Sel_accessed_entity(addr);
 395         case iro_SymConst:
 396                 if (get_SymConst_kind(addr) == symconst_addr_ent) {
 397                         assert(pos == 0);
 398                         return get_SymConst_entity(addr);
 399                 }
 400                 return NULL;
 401         default:
 402                 return NULL;
 403         }
 404 }
 405
 406 static void chain_accesses(ir_node *n, void *env)
 407 {
 408         int i, n_ents;
 409         ir_node *addr;
 410
 411         (void) env;
 412         if (is_Alloc(n)) {
 413                 add_type_alloc(get_Alloc_type(n), n);
 414                 return;
 415         } else if (is_Sel(n)) {
 416                 add_entity_reference(get_Sel_entity(n), n);
 417                 return;
 418         } else if (is_SymConst_addr_ent(n)) {
 419                 add_entity_reference(get_SymConst_entity(n), n);
 420                 return;
 421         } else if (is_Store(n)) {
 422                 addr = get_Store_ptr(n);
 423         } else if (is_Load(n)) {
 424                 addr = get_Load_ptr(n);
 425         } else if (is_Call(n)) {
 426                 addr = get_Call_ptr(n);
 427                 if (! is_Sel(addr)) return;  /* Sels before Calls mean a Load / polymorphic Call. */
 428         } else {
 429                 return;
 430         }
 431
 432         n_ents = get_addr_n_entities(addr);  /* == 1 */
 433         for (i = 0; i < n_ents; ++i) {
 434                 ir_entity *ent = get_addr_entity(addr, i);
 435                 if (ent)
 436                         add_entity_access(ent, n);
 437                 //else
 438                 //add_unrecognized_access(n);
 439         }
 440 }
 441
 442 /**
 443  * Handle chain types (pointer, array) by adding them to
 444  * its "inner" type.
 445  */
 446 static void chain_types(ir_type *tp)
 447 {
 448         if (is_Pointer_type(tp)) {
 449                 add_type_pointertype_to(get_pointer_points_to_type(tp), tp);
 450         } else if (is_Array_type(tp)) {
 451                 add_type_arraytype_of(get_array_element_type(tp), tp);
 452         }
 453 }
 454
 455 void compute_trouts(void)
 456 {
 457         size_t i;
 458
 459         free_trouts();
 460         init_trouts();
 461
 462         /* Compute outs for IR nodes. */
 463         for (i = get_irp_n_irgs(); i > 0;) {
 464                 ir_graph *irg = get_irp_irg(--i);
 465                 irg_walk_graph(irg, NULL, chain_accesses, NULL);
 466         }
 467         walk_const_code(NULL, chain_accesses, NULL);
 468
 469         /* Compute outs for types */
 470         for (i = get_irp_n_types(); i > 0;) {
 471                 ir_type *type = get_irp_type(--i);
 472                 chain_types(type);
 473         }
 474 }
 475
 476 void free_trouts(void)
 477 {
 478         if (entity_access_map) {
 479                 ir_node **accs;
 480                 for (accs = (ir_node **)pmap_first(entity_access_map);
 481                         accs;
 482                         accs = (ir_node **)pmap_next(entity_access_map)) {
 483                         /* DEL_ARR_F(accs); */
 484                 }
 485                 pmap_destroy(entity_access_map);
 486                 entity_access_map = NULL;
 487         }
 488
 489         if (entity_reference_map) {
 490                 ir_node **refs;
 491                 for (refs = (ir_node **)pmap_first(entity_reference_map);
 492                         refs;
 493                         refs = (ir_node **)pmap_next(entity_reference_map)) {
 494                         /* DEL_ARR_F(refs); */
 495                 }
 496                 pmap_destroy(entity_reference_map);
 497                 entity_reference_map = NULL;
 498         }
 499
 500         if (type_alloc_map) {
 501                 ir_node **alls;
 502                 for (alls = (ir_node **)pmap_first(type_alloc_map);
 503                         alls;
 504                         alls = (ir_node **)pmap_next(type_alloc_map)) {
 505                         /* DEL_ARR_F(alls); */
 506                 }
 507                 pmap_destroy(type_alloc_map);
 508                 type_alloc_map = NULL;
 509         }
 510
 511         if (type_pointertype_map) {
 512                 ir_node **pts;
 513                 for (pts = (ir_node **)pmap_first(type_pointertype_map);
 514                         pts;
 515                         pts = (ir_node **)pmap_next(type_pointertype_map)) {
 516                         /* DEL_ARR_F(pts); */
 517                 }
 518                 pmap_destroy(type_pointertype_map);
 519                 type_pointertype_map = NULL;
 520         }
 521
 522         if (type_arraytype_map) {
 523                 ir_node **pts;
 524                 for (pts = (ir_node **)pmap_first(type_arraytype_map);
 525                         pts;
 526                         pts = (ir_node **)pmap_next(type_arraytype_map)) {
 527                         /* DEL_ARR_F(pts); */
 528                 }
 529                 pmap_destroy(type_arraytype_map);
 530                 type_arraytype_map = NULL;
 531         }
 532 }