nsz Git - libfirm/blob - ir/ana/irmemory.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    Memory disambiguator
  23  * @author   Michael Beck
  24  * @date     27.12.2006
  25  * @version  $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <stdlib.h>
  32
  33 #include "irnode_t.h"
  34 #include "irgraph_t.h"
  35 #include "irprog_t.h"
  36 #include "irmemory.h"
  37 #include "irflag.h"
  38 #include "hashptr.h"
  39 #include "irflag.h"
  40 #include "irouts.h"
  41 #include "irgwalk.h"
  42 #include "irprintf.h"
  43
  44 /** The source language specific language disambiguator function. */
  45 static DISAMBIGUATOR_FUNC language_disambuigator = NULL;
  46
  47 /** The global memory disambiguator options. */
  48 static unsigned global_mem_disamgig_opt = aa_opt_no_opt;
  49
  50 /* Get the memory disambiguator options for a graph. */
  51 unsigned get_irg_memory_disambiguator_options(ir_graph *irg) {
  52         unsigned opt = irg->mem_disambig_opt;
  53         if (opt & aa_opt_inherited)
  54                 return global_mem_disamgig_opt;
  55         return opt;
  56 }  /* get_irg_memory_disambiguator_options */
  57
  58 /*  Set the memory disambiguator options for a graph. */
  59 void set_irg_memory_disambiguator_options(ir_graph *irg, unsigned options) {
  60         irg->mem_disambig_opt = options & ~aa_opt_inherited;
  61 }  /* set_irg_memory_disambiguator_options */
  62
  63 /* Set the global disambiguator options for all graphs not having local options. */
  64 void set_irp_memory_disambiguator_options(unsigned options) {
  65         global_mem_disamgig_opt = options;
  66 }  /* set_irp_memory_disambiguator_options */
  67
  68 /**
  69  * Find the base address and entity of an Sel node.
  70  *
  71  * @param sel  the node
  72  * @param pEnt after return points to the base entity.
  73  *
  74  * @return the base address.
  75  */
  76 static ir_node *find_base_adr(ir_node *sel, ir_entity **pEnt) {
  77         ir_node *ptr = get_Sel_ptr(sel);
  78
  79         while (is_Sel(ptr)) {
  80                 sel = ptr;
  81                 ptr = get_Sel_ptr(sel);
  82         }
  83         *pEnt = get_Sel_entity(sel);
  84         return ptr;
  85 }  /* find_base_adr */
  86
  87 /**
  88  * Check if the address can be decomposed into base PLUS offset.
  89  */
  90 static int has_offset(ir_node *adr, int *offset) {
  91         if (is_SymConst(adr)) {
  92                 *offset = 0;
  93                 return 1;
  94         }
  95         if (is_Sel(adr)) {
  96                 ir_entity *ent = get_Sel_entity(adr);
  97                 ir_type   *owner = get_entity_owner(ent);
  98
  99                 if (get_type_state(owner) != layout_fixed) {
 100                         /* The layout is NOT fixed yet, symbolic evaluation needed */
 101                 }
 102         }
 103         return 0;
 104 }  /* has_offset */
 105
 106 /**
 107  * Two address expressions have the same base address,
 108  * check if there offsets are different.
 109  *
 110  * @param adr1  The first address.
 111  * @param adr2  The second address.
 112  */
 113 static ir_alias_relation different_offsets(ir_node *adr1, ir_node *adr2) {
 114         int offset1, offset2;
 115         if (has_offset(adr1, &offset1) && has_offset(adr2, &offset2)) {
 116                 /* */
 117         }
 118         return may_alias;
 119 }  /* different_offsets */
 120
 121 /**
 122  * idx1 and idx2 represent two integer indexes. Check if they could be classified
 123  */
 124 static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2) {
 125         ir_alias_relation res = may_alias;
 126
 127         if (idx1 == idx2)
 128                 return sure_alias;
 129         if (is_Const(idx1) && is_Const(idx2)) {
 130                 /* both are const, we can compare them */
 131                 return get_Const_tarval(idx1) == get_Const_tarval(idx2) ? sure_alias : no_alias;
 132         }
 133
 134         /* Note: we rely here on the fact that normalization puts constants on the RIGHT side */
 135         if (is_Add(idx1)) {
 136                 ir_node *l1 = get_Add_left(idx1);
 137                 ir_node *r1 = get_Add_right(idx1);
 138
 139                 if (l1 == idx2) {
 140                         /* x + c == y */
 141                         if (is_Const(r1)) {
 142                                 return classify_Const(r1) == CNST_NULL ? sure_alias : no_alias;
 143                         }
 144                 }
 145                 if (is_Add(idx2)) {
 146                         /* both are Adds, check if they are of x + c kind */
 147                         ir_node *l2 = get_Add_left(idx2);
 148                         ir_node *r2 = get_Add_right(idx2);
 149
 150                         if (l1 == l2)
 151                                 res = different_index(r1, r2);
 152                         else if (l1 == r2)
 153                                 res = different_index(r1, l2);
 154                         else if (r1 == r2)
 155                                 res = different_index(l1, l2);
 156                         else if (r1 == l2)
 157                                 res = different_index(l1, r2);
 158                         if (res != may_alias)
 159                                 return res;
 160                 }
 161         }
 162         if (is_Add(idx2)) {
 163                 ir_node *l2 = get_Add_left(idx2);
 164                 ir_node *r2 = get_Add_right(idx2);
 165
 166                 if (l2 == idx1) {
 167                         /* x + c == y */
 168                         if (is_Const(r2)) {
 169                                 return classify_Const(r2) == CNST_NULL ? sure_alias : no_alias;
 170                         }
 171                 }
 172         }
 173
 174         if (is_Sub(idx1)) {
 175                 ir_node *l1 = get_Sub_left(idx1);
 176                 ir_node *r1 = get_Sub_right(idx1);
 177
 178                 if (l1 == idx2) {
 179                         /* x - c == y */
 180                         if (is_Const(r1)) {
 181                                 return classify_Const(r1) == CNST_NULL ? sure_alias : no_alias;
 182                         }
 183                 }
 184
 185                 if (is_Sub(idx2)) {
 186                         /* both are Subs, check if they are of x - c kind */
 187                         ir_node *l2 = get_Sub_left(idx2);
 188
 189                         if (l1 == l2) {
 190                                 ir_node *r2 = get_Sub_right(idx2);
 191                                 res = different_index(r1, r2);
 192                         }
 193                 }
 194                 if (res != may_alias)
 195                         return res;
 196         }
 197         if (is_Sub(idx2)) {
 198                 ir_node *l2 = get_Sub_left(idx2);
 199                 ir_node *r2 = get_Sub_right(idx2);
 200
 201                 if (l2 == idx1) {
 202                         /* x - c == y */
 203                         if (is_Const(r2)) {
 204                                 return classify_Const(r2) == CNST_NULL ? sure_alias : no_alias;
 205                         }
 206                 }
 207
 208         }
 209         return may_alias;
 210 }  /* different_index */
 211
 212 /**
 213  * Two Sel addresses have the same base address, check if there offsets are different.
 214  *
 215  * @param adr1  The first address.
 216  * @param adr2  The second address.
 217  */
 218 static ir_alias_relation different_sel_offsets(ir_node *sel1, ir_node *sel2) {
 219         ir_entity *ent1 = get_Sel_entity(sel1);
 220         ir_entity *ent2 = get_Sel_entity(sel2);
 221         int i, check_arr = 0;
 222
 223         if (ent1 == ent2)
 224                 check_arr = 1;
 225         else {
 226                 ir_type *tp1 = get_entity_type(ent1);
 227                 ir_type *tp2 = get_entity_type(ent2);
 228
 229                 if (tp1 == tp2)
 230                         check_arr = 1;
 231                 else if (get_type_state(tp1) == layout_fixed && get_type_state(tp2) == layout_fixed &&
 232                          get_type_size_bytes(tp1) == get_type_size_bytes(tp2))
 233                         check_arr = 1;
 234         }
 235         if (check_arr) {
 236                 /* we select an entity of same size, check for indexes */
 237                 int n = get_Sel_n_indexs(sel1);
 238                 int have_no = 0;
 239
 240                 if (n > 0 && n == get_Sel_n_indexs(sel2)) {
 241                         /* same non-zero number of indexes, an array access, check */
 242                         for (i = 0; i < n; ++i) {
 243                                 ir_node *idx1 = get_Sel_index(sel1, i);
 244                                 ir_node *idx2 = get_Sel_index(sel2, i);
 245                                 ir_alias_relation res = different_index(idx1, idx2);
 246
 247                                 if (res == may_alias)
 248                                         return may_alias;
 249                                 else if (res == no_alias)
 250                                         have_no = 1;
 251                         }
 252                         /* if we have at least one no_alias, there is no alias relation, else we have sure */
 253                         return have_no > 0 ? no_alias : sure_alias;
 254                 }
 255         }
 256         return may_alias;
 257 }  /* different_sel_offsets */
 258
 259 /**
 260  * Determine the alias relation by checking if adr1 and adr2 are pointer
 261  * to different type.
 262  *
 263  * @param adr1    The first address.
 264  * @param adr2    The second address.
 265  */
 266 static ir_alias_relation different_types(ir_node *adr1, ir_node *adr2)
 267 {
 268         ir_entity *ent1 = NULL, *ent2 = NULL;
 269
 270         if (is_SymConst(adr1) && get_SymConst_kind(adr1) == symconst_addr_ent)
 271                 ent1 = get_SymConst_entity(adr1);
 272         else if (is_Sel(adr1))
 273                 ent1 = get_Sel_entity(adr1);
 274
 275         if (is_SymConst(adr2) && get_SymConst_kind(adr2) == symconst_addr_ent)
 276                 ent2 = get_SymConst_entity(adr2);
 277         else if (is_Sel(adr2))
 278                 ent2 = get_Sel_entity(adr2);
 279
 280         if (ent1 != NULL && ent2 != NULL) {
 281                 ir_type *tp1 = get_entity_type(ent1);
 282                 ir_type *tp2 = get_entity_type(ent2);
 283
 284                 if (tp1 != tp2) {
 285                         if (is_Pointer_type(tp1) && is_Pointer_type(tp2)) {
 286                                 /* do deref until no pointer types are found */
 287                                 do {
 288                                         tp1 = get_pointer_points_to_type(tp1);
 289                                         tp2 = get_pointer_points_to_type(tp2);
 290                                 } while (is_Pointer_type(tp1) && is_Pointer_type(tp2));
 291                         }
 292
 293                         if (get_type_tpop(tp1) != get_type_tpop(tp2)) {
 294                                 /* different type structure */
 295                                 return no_alias;
 296                         }
 297                         if (is_Class_type(tp1)) {
 298                                 /* check class hierarchy */
 299                                 if (! is_SubClass_of(tp1, tp2) &&
 300                                         ! is_SubClass_of(tp2, tp1))
 301                                         return no_alias;
 302                         } else {
 303                                 /* different types */
 304                                 return no_alias;
 305                         }
 306                 }
 307         }
 308         return may_alias;
 309 }  /* different_types */
 310
 311 /**
 312  * Returns non-zero if a node is a routine parameter.
 313  *
 314  * @param node  the node to test
 315  */
 316 static int is_arg_Proj(ir_node *node) {
 317         if (! is_Proj(node))
 318                 return 0;
 319         node = get_Proj_pred(node);
 320         if (! is_Proj(node))
 321                 return 0;
 322         return pn_Start_T_args == get_Proj_proj(node) && is_Start(get_Proj_pred(node));
 323 }  /* is_arg_Proj */
 324
 325 /**
 326  * Determine the alias relation between two addresses.
 327  */
 328 static ir_alias_relation _get_alias_relation(
 329         ir_graph *irg,
 330         ir_node *adr1, ir_mode *mode1,
 331         ir_node *adr2, ir_mode *mode2)
 332 {
 333         ir_opcode op1, op2;
 334         ir_entity *ent1, *ent2;
 335         unsigned options;
 336
 337         if (! get_opt_alias_analysis())
 338                 return may_alias;
 339
 340         if (adr1 == adr2)
 341                 return sure_alias;
 342
 343         options = get_irg_memory_disambiguator_options(irg);
 344
 345         /* The Armageddon switch */
 346         if (options & aa_opt_no_alias)
 347                 return no_alias;
 348
 349         /* Two save some code, sort the addresses by its id's. Beware, this
 350            might break some things, so better check here. */
 351         assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence breaked");
 352         op1 = get_irn_opcode(adr1);
 353         op2 = get_irn_opcode(adr2);
 354
 355         if (op1 > op2) {
 356                 ir_node *t = adr1;
 357                 ir_mode *m = mode1;
 358                 adr1  = adr2;
 359                 mode1 = mode2;
 360                 adr2  = t;
 361                 mode2 = m;
 362         }
 363
 364         if (is_SymConst(adr1) && get_SymConst_kind(adr1) == symconst_addr_ent) {
 365                 /* first address is a global variable */
 366
 367                 if (is_SymConst(adr2) && get_SymConst_kind(adr2) == symconst_addr_ent) {
 368                         /* both addresses are global variables and we know
 369                            they are different (R1 a) */
 370                         if (get_SymConst_entity(adr1) != get_SymConst_entity(adr2))
 371                                 return no_alias;
 372                         else {
 373                                 /* equal addresses */
 374                                 return sure_alias;
 375                         }
 376                 }
 377                 if (is_Sel(adr2)) {
 378                         ir_node *base = find_base_adr(adr2, &ent2);
 379
 380                         if (is_SymConst(base) && get_SymConst_kind(base) == symconst_addr_ent) {
 381                                 /* base address is a global var (R1 a) */
 382                                 if (adr1 != base)
 383                                         return no_alias;
 384                                 if (base == adr1)
 385                                         return different_offsets(adr1, adr2);
 386                         } else if (base == get_irg_frame(irg)) {
 387                                 /* the second one is a local variable so they are always
 388                                    different (R1 b) */
 389                                 return no_alias;
 390                         } else if (base == get_irg_tls(irg)) {
 391                                 /* the second one is a TLS variable so they are always
 392                                    different (R1 c) */
 393                                 return no_alias;
 394                         }
 395                 }
 396
 397                 /* Here we are: the first is a global var, the second some pointer. */
 398                 ent1 = get_SymConst_entity(adr1);
 399                 if (get_entity_address_taken(ent1) == ir_address_not_taken) {
 400                         /* The address of the global variable was never taken, so
 401                            the pointer cannot match (R2). */
 402                         return no_alias;
 403                 }
 404         } else if (is_Sel(adr1)) {
 405                 /* the first address is a Sel */
 406                 ir_node *base1 = find_base_adr(adr1, &ent1);
 407
 408                 if (base1 == get_irg_frame(irg)) {
 409                         /* the first is a local variable */
 410                         if (is_Sel(adr2)) {
 411                                 /* the second address is a Sel */
 412                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 413
 414                                 if (base2 == get_irg_frame(irg)) {
 415                                         /* both addresses are local variables and we know
 416                                            they are different (R1 a) */
 417                                         if (ent1 != ent2)
 418                                                 return no_alias;
 419                                         else
 420                                                 return different_sel_offsets(adr1, adr2);
 421                                 } else if (base2 == get_irg_tls(irg)) {
 422                                         /* the second one is a TLS variable so they are always
 423                                        different (R1 d) */
 424                                         return no_alias;
 425                                 } else if (is_arg_Proj(base2)) {
 426                                         /* the second one is an offset from a parameter so they are
 427                                            always different (R1 e) */
 428                                         return no_alias;
 429                                 }
 430                         } else if (is_arg_Proj(adr2)) {
 431                                 /* a local variable and a parameter are always different (R1 e) */
 432                                 return no_alias;
 433                         }
 434                 } else if (base1 == get_irg_tls(irg)) {
 435                         /* the first is a TLS variable */
 436                         if (is_Sel(adr2)) {
 437                                 /* the second address is a Sel */
 438                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 439
 440                                 if (base2 == get_irg_frame(irg)) {
 441                                         /* the second one is a local variable so they are always
 442                                        different (R1 d) */
 443                                         return no_alias;
 444                                 } else if (base2 == get_irg_tls(irg)) {
 445                                         /* both addresses are TLS variables and we know
 446                                            they are different (R1 a) */
 447                                         if (ent1 != ent2)
 448                                                 return no_alias;
 449                                         else
 450                                                 return different_sel_offsets(adr1, adr2);
 451                                 }
 452                         }
 453                 } else if (is_arg_Proj(base1)) {
 454                         /* the first one is an offset from a parameter */
 455                         if (is_Sel(adr2)) {
 456                                 /* the second address is a Sel */
 457                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 458
 459                                 if (base2 == get_irg_frame(irg)) {
 460                                         /* the second one is a local variable so they are always
 461                                        different (R1 e) */
 462                                         return no_alias;
 463                                 }
 464                         }
 465                 }
 466         }
 467
 468         if (options & aa_opt_type_based) { /* Type based alias analysis */
 469                 ir_alias_relation rel;
 470
 471                 if (options & aa_opt_byte_type_may_alias) {
 472                         if (get_mode_size_bits(mode1) == 8 || get_mode_size_bits(mode2) == 8) {
 473                                 /* One of the modes address a byte. Assume a may_alias and leave
 474                                    the type based check. */
 475                                 goto leave_type_based_alias;
 476                         }
 477                 }
 478                 /* cheap check: If the mode sizes did not match, the types MUST be different */
 479                 if (get_mode_size_bits(mode1) != get_mode_size_bits(mode2))
 480                         return no_alias;
 481
 482                 /* try rule R5 */
 483                 rel = different_types(adr1, adr2);
 484                 if (rel != may_alias)
 485                         return rel;
 486 leave_type_based_alias:;
 487         }
 488
 489         /* do we have a language specific memory disambiguator? */
 490         if (language_disambuigator) {
 491                 ir_alias_relation rel = (*language_disambuigator)(irg, adr1, mode1, adr2, mode2);
 492                 if (rel != may_alias)
 493                         return rel;
 494         }
 495
 496         /* access points-to information here */
 497         return may_alias;
 498 }  /* _get_alias_relation */
 499
 500 /*
 501  * Determine the alias relation between two addresses.
 502  */
 503 ir_alias_relation get_alias_relation(
 504         ir_graph *irg,
 505         ir_node *adr1, ir_mode *mode1,
 506         ir_node *adr2, ir_mode *mode2)
 507 {
 508         ir_alias_relation rel = _get_alias_relation(irg, adr1, mode1, adr2, mode2);
 509         return rel;
 510 }  /* get_alias_relation */
 511
 512 /* Set a source language specific memory disambiguator function. */
 513 void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func) {
 514         language_disambuigator = func;
 515 }  /* set_language_memory_disambiguator */
 516
 517 /** The result cache for the memory disambiguator. */
 518 static set *result_cache = NULL;
 519
 520 /** An entry in the relation cache. */
 521 typedef struct mem_disambig_entry {
 522         ir_node           *adr1;    /**< The first address. */
 523         ir_node           *adr2;    /**< The second address. */
 524         ir_alias_relation result;   /**< The alias relation result. */
 525 } mem_disambig_entry;
 526
 527 #define HASH_ENTRY(adr1, adr2)  (HASH_PTR(adr1) ^ HASH_PTR(adr2))
 528
 529 /**
 530  * Compare two relation cache entries.
 531  */
 532 static int cmp_mem_disambig_entry(const void *elt, const void *key, size_t size) {
 533         const mem_disambig_entry *p1 = elt;
 534         const mem_disambig_entry *p2 = key;
 535
 536         return p1->adr1 == p2->adr1 && p1->adr2 == p2->adr2;
 537 }  /* cmp_mem_disambig_entry */
 538
 539 /**
 540  * Initialize the relation cache.
 541  */
 542 void mem_disambig_init(void) {
 543         result_cache = new_set(cmp_mem_disambig_entry, 8);
 544 }  /* mem_disambig_init */
 545
 546 /*
 547  * Determine the alias relation between two addresses.
 548  */
 549 ir_alias_relation get_alias_relation_ex(
 550         ir_graph *irg,
 551         ir_node *adr1, ir_mode *mode1,
 552         ir_node *adr2, ir_mode *mode2)
 553 {
 554         mem_disambig_entry key, *entry;
 555
 556         if (! get_opt_alias_analysis())
 557                 return may_alias;
 558
 559         if (get_irn_opcode(adr1) > get_irn_opcode(adr2)) {
 560                 ir_node *t = adr1;
 561                 adr1 = adr2;
 562                 adr2 = t;
 563         }
 564
 565         key.adr1 = adr1;
 566         key.adr2 = adr2;
 567         entry = set_find(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 568         if (entry)
 569                 return entry->result;
 570
 571         key.result = get_alias_relation(irg, adr1, mode1, adr2, mode2);
 572
 573         set_insert(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 574         return key.result;
 575 }  /* get_alias_relation_ex */
 576
 577 /* Free the relation cache. */
 578 void mem_disambig_term(void) {
 579         if (result_cache) {
 580                 del_set(result_cache);
 581                 result_cache = NULL;
 582         }
 583 }  /* mem_disambig_term */
 584
 585 /**
 586  * Check the mode of a Load/Store with the mode of the entity
 587  * that is accessed.
 588  * If the mode of the entity and the Load/Store mode do not match, we
 589  * have the bad reinterpret case:
 590  *
 591  * int i;
 592  * char b = *(char *)&i;
 593  *
 594  * We do NOT count this as one value and return address_taken
 595  * in that case.
 596  * However, we support an often used case. If the mode is two-complement
 597  * we allow casts between signed/unsigned.
 598  *
 599  * @param mode     the mode of the Load/Store
 600  * @param ent_mode the mode of the accessed entity
 601  *
 602  * @return non-zero if the Load/Store is a hidden cast, zero else
 603  */
 604 static int is_hidden_cast(ir_mode *mode, ir_mode *ent_mode) {
 605         if (ent_mode != mode) {
 606                 if (ent_mode == NULL ||
 607                         get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
 608                         get_mode_sort(ent_mode) != get_mode_sort(mode) ||
 609                         get_mode_arithmetic(ent_mode) != irma_twos_complement ||
 610                         get_mode_arithmetic(mode) != irma_twos_complement)
 611                         return 1;
 612         }
 613         return 0;
 614 }  /* is_hidden_cast */
 615
 616 /**
 617  * Determine the address_taken state of a node (or it's successor Sels).
 618  *
 619  * @param irn  the node
 620  */
 621 static ir_address_taken_state find_address_taken_state(ir_node *irn) {
 622         int     i;
 623         ir_mode *emode, *mode;
 624         ir_node *value;
 625         ir_entity *ent;
 626
 627         for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 628                 ir_node *succ = get_irn_out(irn, i);
 629
 630                 switch (get_irn_opcode(succ)) {
 631                 case iro_Load:
 632                         /* check if this load is not a hidden conversion */
 633                         mode = get_Load_mode(succ);
 634                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 635                         emode = get_type_mode(get_entity_type(ent));
 636                         if (is_hidden_cast(mode, emode))
 637                                 return ir_address_taken;
 638                         break;
 639
 640                 case iro_Store:
 641                         /* check that the node is not the Store's value */
 642                         value = get_Store_value(succ);
 643                         if (value == irn)
 644                                 return ir_address_taken;
 645                         /* check if this Store is not a hidden conversion */
 646                         mode = get_irn_mode(value);
 647                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 648                         emode = get_type_mode(get_entity_type(ent));
 649                         if (is_hidden_cast(mode, emode))
 650                                 return ir_address_taken;
 651                         break;
 652
 653                 case iro_Sel: {
 654                         /* Check the successor of irn. */
 655                         ir_address_taken_state res = find_address_taken_state(succ);
 656                         if (res != ir_address_not_taken)
 657                                 return res;
 658                         break;
 659                 }
 660
 661                 case iro_Call:
 662                         /* Only the call address is not an address taker but
 663                            this is an uninteresting case, so we ignore it here. */
 664                         return ir_address_taken;
 665
 666                 default:
 667                         /* another op, the address may be taken */
 668                         return ir_address_taken_unknown;
 669                 }
 670         }
 671         /* All successors finished, the address is not taken. */
 672         return ir_address_not_taken;
 673 }  /* find_address_taken_state */
 674
 675 /**
 676  * Update the "address taken" flag of all frame entities.
 677  */
 678 static void analyse_irg_address_taken(ir_graph *irg) {
 679         ir_type *ft = get_irg_frame_type(irg);
 680         ir_node *irg_frame;
 681         int i;
 682
 683         /* set initial state to not_taken, as this is the "smallest" state */
 684         for (i = get_class_n_members(ft) - 1; i >= 0; --i) {
 685                 ir_entity *ent = get_class_member(ft, i);
 686
 687                 set_entity_address_taken(ent, ir_address_not_taken);
 688         }
 689
 690         assure_irg_outs(irg);
 691
 692         irg_frame = get_irg_frame(irg);
 693
 694         for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
 695                 ir_node *succ = get_irn_out(irg_frame, i);
 696                 ir_address_taken_state state;
 697
 698             if (is_Sel(succ)) {
 699                         ir_entity *ent = get_Sel_entity(succ);
 700
 701                         if (get_entity_address_taken(ent) == ir_address_taken)
 702                                 continue;
 703
 704                         state = find_address_taken_state(succ);
 705                         if (state > get_entity_address_taken(ent))
 706                                 set_entity_address_taken(ent, state);
 707                 }
 708         }
 709         /* now computed */
 710         irg->adr_taken_state = ir_address_taken_computed;
 711 }  /* analyse_address_taken */
 712
 713 /* Returns the current address taken state of the graph. */
 714 ir_address_taken_computed_state get_irg_address_taken_state(const ir_graph *irg) {
 715         return irg->adr_taken_state;
 716 }  /* get_irg_address_taken_state */
 717
 718 /* Sets the current address taken state of the graph. */
 719 void set_irg_address_taken_state(ir_graph *irg, ir_address_taken_computed_state state) {
 720         irg->adr_taken_state = state;
 721 }  /* set_irg_address_taken_state */
 722
 723 /* Assure that the address taken flag is computed for the given graph. */
 724 void assure_irg_address_taken_computed(ir_graph *irg) {
 725         if (irg->adr_taken_state == ir_address_taken_not_computed)
 726                 analyse_irg_address_taken(irg);
 727 }  /* assure_irg_address_taken_computed */
 728
 729 /**
 730  * Initialize the address_taken flag for a global type like type.
 731  */
 732 static void init_taken_flag(ir_type * tp) {
 733         int i;
 734
 735         /* All external visible entities are at least
 736            ir_address_taken_unknown. This is very conservative. */
 737         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 738                 ir_entity *ent = get_compound_member(tp, i);
 739                 ir_address_taken_state state;
 740
 741                 state = get_entity_visibility(ent) == visibility_external_visible ?
 742                                 ir_address_taken_unknown : ir_address_not_taken ;
 743                 set_entity_address_taken(ent, state);
 744         }
 745 }  /* init_taken_flag */
 746
 747 #if 0
 748 /**
 749  * Print the address taken state of all entities of a given type for debugging.
 750  */
 751 static void print_address_taken_state(ir_type *tp) {
 752         int i;
 753         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 754                 ir_entity *ent = get_compound_member(tp, i);
 755                 ir_address_taken_state state = get_entity_address_taken(ent);
 756
 757                 if (state != ir_address_not_taken) {
 758                         assert(ir_address_not_taken <= state && state <= ir_address_taken);
 759                         ir_printf("%+F: %s\n", ent, get_address_taken_state_name(state));
 760                 }
 761         }
 762 }  /* print_address_taken_state */
 763 #endif
 764
 765 /**
 766  * Post-walker: check for global entity address
 767  */
 768 static void check_global_address(ir_node *irn, void *env) {
 769         ir_node *tls = env;
 770         ir_entity *ent;
 771         ir_address_taken_state state;
 772
 773         if (is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent) {
 774                 /* A global. */
 775                 ent = get_SymConst_entity(irn);
 776         } else if (is_Sel(irn) && get_Sel_ptr(irn) == tls) {
 777                 /* A TLS variable. */
 778                 ent = get_Sel_entity(irn);
 779         } else
 780                 return;
 781
 782         if (get_entity_address_taken(ent) >= ir_address_taken) {
 783                 /* Already at the maximum. */
 784                 return;
 785         }
 786         state = find_address_taken_state(irn);
 787         if (state > get_entity_address_taken(ent))
 788                 set_entity_address_taken(ent, state);
 789 }  /* check_global_address */
 790
 791 /**
 792  * Update the "address taken" flag of all global entities.
 793  */
 794 static void analyse_irp_globals_address_taken(void) {
 795         int i;
 796
 797         init_taken_flag(get_glob_type());
 798         init_taken_flag(get_tls_type());
 799
 800         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 801                 ir_graph *irg = get_irp_irg(i);
 802
 803                 assure_irg_outs(irg);
 804                 irg_walk_graph(irg, NULL, check_global_address, get_irg_tls(irg));
 805         }
 806         //print_address_taken_state(get_glob_type());
 807         //print_address_taken_state(get_tls_type());
 808
 809         /* now computed */
 810         irp->globals_adr_taken_state = ir_address_taken_computed;
 811 }  /* analyse_irp_globals_address_taken */
 812
 813 /* Returns the current address taken state of the globals. */
 814 ir_address_taken_computed_state get_irp_globals_address_taken_state(void) {
 815         return irp->globals_adr_taken_state;
 816 }  /* get_irp_globals_address_taken_state */
 817
 818 /* Sets the current address taken state of the graph. */
 819 void set_irp_globals_address_taken_state(ir_address_taken_computed_state state) {
 820         irp->globals_adr_taken_state = state;
 821 }  /* set_irg_address_taken_state */
 822
 823 /* Assure that the address taken flag is computed for the globals. */
 824 void assure_irp_globals_address_taken_computed(void) {
 825         if (irp->globals_adr_taken_state == ir_address_taken_not_computed)
 826                 analyse_irp_globals_address_taken();
 827 }  /* assure_irp_globals_address_taken_computed */