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