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

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