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