nsz Git - libfirm/blob - ir/ana/trouts.c

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