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