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