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