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

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