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  * Returns true if an address represents a global variable.
 327  */
 328 static INLINE int is_global_var(ir_node *irn) {
 329         return is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent;
 330 }  /* is_global_var */
 331
 332 /**
 333  * Determine the alias relation between two addresses.
 334  */
 335 static ir_alias_relation _get_alias_relation(
 336         ir_graph *irg,
 337         ir_node *adr1, ir_mode *mode1,
 338         ir_node *adr2, ir_mode *mode2)
 339 {
 340         ir_opcode op1, op2;
 341         ir_entity *ent1, *ent2;
 342         unsigned options;
 343
 344         if (! get_opt_alias_analysis())
 345                 return may_alias;
 346
 347         if (adr1 == adr2)
 348                 return sure_alias;
 349
 350         options = get_irg_memory_disambiguator_options(irg);
 351
 352         /* The Armageddon switch */
 353         if (options & aa_opt_no_alias)
 354                 return no_alias;
 355
 356         /* Two save some code, sort the addresses by its id's. Beware, this
 357            might break some things, so better check here. */
 358         assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence breaked");
 359         op1 = get_irn_opcode(adr1);
 360         op2 = get_irn_opcode(adr2);
 361
 362         if (op1 > op2) {
 363                 ir_node *t = adr1;
 364                 ir_mode *m = mode1;
 365                 adr1  = adr2;
 366                 mode1 = mode2;
 367                 adr2  = t;
 368                 mode2 = m;
 369         }
 370
 371         if (is_global_var(adr1)) {
 372                 /* first address is a global variable */
 373
 374                 if (is_global_var(adr2)) {
 375                         /* both addresses are global variables and we know
 376                            they are different (R1 a) */
 377                         if (get_SymConst_entity(adr1) != get_SymConst_entity(adr2))
 378                                 return no_alias;
 379                         else {
 380                                 /* equal addresses */
 381                                 return sure_alias;
 382                         }
 383                 }
 384                 if (is_Sel(adr2)) {
 385                         ir_node *base2 = find_base_adr(adr2, &ent2);
 386
 387                         if (is_global_var(base2)) {
 388                                 /* base2 address is a global var (R1 a) */
 389                                 if (adr1 != base2)
 390                                         return no_alias;
 391                                 else
 392                                         return different_offsets(adr1, adr2);
 393                         } else if (base2 == get_irg_frame(irg)) {
 394                                 /* the second one is a local variable so they are always
 395                                    different (R1 b) */
 396                                 return no_alias;
 397                         } else if (base2 == get_irg_tls(irg)) {
 398                                 /* the second one is a TLS variable so they are always
 399                                    different (R1 c) */
 400                                 return no_alias;
 401                         }
 402                 }
 403
 404                 /* Here we are: the first is a global var, the second some pointer. */
 405                 ent1 = get_SymConst_entity(adr1);
 406                 if (get_entity_address_taken(ent1) == ir_address_not_taken) {
 407                         /* The address of the global variable was never taken, so
 408                            the pointer cannot match (R2). */
 409                         return no_alias;
 410                 }
 411         } else if (is_Sel(adr1)) {
 412                 /* the first address is a Sel */
 413                 ir_node *base1 = find_base_adr(adr1, &ent1);
 414
 415                 if (base1 == get_irg_frame(irg)) {
 416                         /* the first is a local variable */
 417                         if (is_Sel(adr2)) {
 418                                 /* the second address is a Sel */
 419                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 420
 421                                 if (base1 == base2)
 422                                         return different_sel_offsets(adr1, adr2);
 423                                 else if (base2 == get_irg_frame(irg)) {
 424                                         /* both addresses are local variables and we know
 425                                            they are different (R1 a) */
 426                                         if (ent1 != ent2)
 427                                                 return no_alias;
 428                                 } else if (base2 == get_irg_tls(irg)) {
 429                                         /* the second one is a TLS variable so they are always
 430                                        different (R1 d) */
 431                                         return no_alias;
 432                                 } else if (is_arg_Proj(base2)) {
 433                                         /* the second one is an offset from a parameter so they are
 434                                            always different (R1 e) */
 435                                         return no_alias;
 436                                 }
 437                         } else if (is_arg_Proj(adr2)) {
 438                                 /* a local variable and a parameter are always different (R1 e) */
 439                                 return no_alias;
 440                         }
 441                 } else if (base1 == get_irg_tls(irg)) {
 442                         /* the first is a TLS variable */
 443                         if (is_Sel(adr2)) {
 444                                 /* the second address is a Sel */
 445                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 446
 447                                 if (base1 == base2)
 448                                         return different_sel_offsets(adr1, adr2);
 449                                 else if (base2 == get_irg_frame(irg)) {
 450                                         /* the second one is a local variable so they are always
 451                                        different (R1 d) */
 452                                         return no_alias;
 453                                 } else if (base2 == get_irg_tls(irg)) {
 454                                         /* both addresses are TLS variables and we know
 455                                            they are different (R1 a) */
 456                                         if (ent1 != ent2)
 457                                                 return no_alias;
 458                                 }
 459                         }
 460                 } else if (is_arg_Proj(base1)) {
 461                         /* the first one is an offset from a parameter */
 462                         if (is_Sel(adr2)) {
 463                                 /* the second address is a Sel */
 464                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 465
 466                                 if (base2 == get_irg_frame(irg)) {
 467                                         /* the second one is a local variable so they are always
 468                                        different (R1 e) */
 469                                         return no_alias;
 470                                 }
 471                         }
 472                 } else if (is_global_var(base1)) {
 473                         /* the first one is a global variable */
 474                         ent1 = get_SymConst_entity(base1);
 475                         if (is_Sel(adr2)) {
 476                                 /* the second address is a Sel */
 477                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 478
 479                                 if (base1 == base2)
 480                                         return different_sel_offsets(adr1, adr2);
 481                                 else if (base2 == get_irg_frame(irg)) {
 482                                         /* the second one is a local variable so they are always
 483                                        different (R1 a) */
 484                                         return no_alias;
 485                                 } else if (base2 == get_irg_tls(irg)) {
 486                                         /* the second one is a TLS variable so they are always
 487                                        different (R1 a) */
 488                                         return no_alias;
 489                                 } else if (is_arg_Proj(base2)) {
 490                                         if (get_entity_address_taken(ent1) == ir_address_not_taken) {
 491                                                 /* The address of the global variable was never taken, so
 492                                                    the pointer cannot match (R2). */
 493                                                 return no_alias;
 494                                         }
 495                                 } else if (is_global_var(base2)) {
 496                                         ent2 = get_SymConst_entity(base2);
 497                                         /* both addresses are global variables and we know
 498                                            they are different (R1 a) */
 499                                         if (ent1 != ent2)
 500                                                 return no_alias;
 501                                 }
 502                         }
 503                 }
 504         }
 505
 506         if (options & aa_opt_type_based) { /* Type based alias analysis */
 507                 ir_alias_relation rel;
 508
 509                 if (options & aa_opt_byte_type_may_alias) {
 510                         if (get_mode_size_bits(mode1) == 8 || get_mode_size_bits(mode2) == 8) {
 511                                 /* One of the modes address a byte. Assume a may_alias and leave
 512                                    the type based check. */
 513                                 goto leave_type_based_alias;
 514                         }
 515                 }
 516                 /* cheap check: If the mode sizes did not match, the types MUST be different */
 517                 if (get_mode_size_bits(mode1) != get_mode_size_bits(mode2))
 518                         return no_alias;
 519
 520                 /* try rule R5 */
 521                 rel = different_types(adr1, adr2);
 522                 if (rel != may_alias)
 523                         return rel;
 524 leave_type_based_alias:;
 525         }
 526
 527         /* do we have a language specific memory disambiguator? */
 528         if (language_disambuigator) {
 529                 ir_alias_relation rel = (*language_disambuigator)(irg, adr1, mode1, adr2, mode2);
 530                 if (rel != may_alias)
 531                         return rel;
 532         }
 533
 534         /* access points-to information here */
 535         return may_alias;
 536 }  /* _get_alias_relation */
 537
 538 /*
 539  * Determine the alias relation between two addresses.
 540  */
 541 ir_alias_relation get_alias_relation(
 542         ir_graph *irg,
 543         ir_node *adr1, ir_mode *mode1,
 544         ir_node *adr2, ir_mode *mode2)
 545 {
 546         ir_alias_relation rel = _get_alias_relation(irg, adr1, mode1, adr2, mode2);
 547         return rel;
 548 }  /* get_alias_relation */
 549
 550 /* Set a source language specific memory disambiguator function. */
 551 void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func) {
 552         language_disambuigator = func;
 553 }  /* set_language_memory_disambiguator */
 554
 555 /** The result cache for the memory disambiguator. */
 556 static set *result_cache = NULL;
 557
 558 /** An entry in the relation cache. */
 559 typedef struct mem_disambig_entry {
 560         ir_node           *adr1;    /**< The first address. */
 561         ir_node           *adr2;    /**< The second address. */
 562         ir_alias_relation result;   /**< The alias relation result. */
 563 } mem_disambig_entry;
 564
 565 #define HASH_ENTRY(adr1, adr2)  (HASH_PTR(adr1) ^ HASH_PTR(adr2))
 566
 567 /**
 568  * Compare two relation cache entries.
 569  */
 570 static int cmp_mem_disambig_entry(const void *elt, const void *key, size_t size) {
 571         const mem_disambig_entry *p1 = elt;
 572         const mem_disambig_entry *p2 = key;
 573
 574         return p1->adr1 == p2->adr1 && p1->adr2 == p2->adr2;
 575 }  /* cmp_mem_disambig_entry */
 576
 577 /**
 578  * Initialize the relation cache.
 579  */
 580 void mem_disambig_init(void) {
 581         result_cache = new_set(cmp_mem_disambig_entry, 8);
 582 }  /* mem_disambig_init */
 583
 584 /*
 585  * Determine the alias relation between two addresses.
 586  */
 587 ir_alias_relation get_alias_relation_ex(
 588         ir_graph *irg,
 589         ir_node *adr1, ir_mode *mode1,
 590         ir_node *adr2, ir_mode *mode2)
 591 {
 592         mem_disambig_entry key, *entry;
 593
 594         if (! get_opt_alias_analysis())
 595                 return may_alias;
 596
 597         if (get_irn_opcode(adr1) > get_irn_opcode(adr2)) {
 598                 ir_node *t = adr1;
 599                 adr1 = adr2;
 600                 adr2 = t;
 601         }
 602
 603         key.adr1 = adr1;
 604         key.adr2 = adr2;
 605         entry = set_find(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 606         if (entry)
 607                 return entry->result;
 608
 609         key.result = get_alias_relation(irg, adr1, mode1, adr2, mode2);
 610
 611         set_insert(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 612         return key.result;
 613 }  /* get_alias_relation_ex */
 614
 615 /* Free the relation cache. */
 616 void mem_disambig_term(void) {
 617         if (result_cache) {
 618                 del_set(result_cache);
 619                 result_cache = NULL;
 620         }
 621 }  /* mem_disambig_term */
 622
 623 /**
 624  * Check the mode of a Load/Store with the mode of the entity
 625  * that is accessed.
 626  * If the mode of the entity and the Load/Store mode do not match, we
 627  * have the bad reinterpret case:
 628  *
 629  * int i;
 630  * char b = *(char *)&i;
 631  *
 632  * We do NOT count this as one value and return address_taken
 633  * in that case.
 634  * However, we support an often used case. If the mode is two-complement
 635  * we allow casts between signed/unsigned.
 636  *
 637  * @param mode     the mode of the Load/Store
 638  * @param ent_mode the mode of the accessed entity
 639  *
 640  * @return non-zero if the Load/Store is a hidden cast, zero else
 641  */
 642 static int is_hidden_cast(ir_mode *mode, ir_mode *ent_mode) {
 643         if (ent_mode != mode) {
 644                 if (ent_mode == NULL ||
 645                         get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
 646                         get_mode_sort(ent_mode) != get_mode_sort(mode) ||
 647                         get_mode_arithmetic(ent_mode) != irma_twos_complement ||
 648                         get_mode_arithmetic(mode) != irma_twos_complement)
 649                         return 1;
 650         }
 651         return 0;
 652 }  /* is_hidden_cast */
 653
 654 /**
 655  * Determine the address_taken state of a node (or it's successor Sels).
 656  *
 657  * @param irn  the node
 658  */
 659 static ir_address_taken_state find_address_taken_state(ir_node *irn) {
 660         int     i;
 661         ir_mode *emode, *mode;
 662         ir_node *value;
 663         ir_entity *ent;
 664
 665         for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 666                 ir_node *succ = get_irn_out(irn, i);
 667
 668                 switch (get_irn_opcode(succ)) {
 669                 case iro_Load:
 670                         /* check if this load is not a hidden conversion */
 671                         mode = get_Load_mode(succ);
 672                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 673                         emode = get_type_mode(get_entity_type(ent));
 674                         if (is_hidden_cast(mode, emode))
 675                                 return ir_address_taken;
 676                         break;
 677
 678                 case iro_Store:
 679                         /* check that the node is not the Store's value */
 680                         value = get_Store_value(succ);
 681                         if (value == irn)
 682                                 return ir_address_taken;
 683                         /* check if this Store is not a hidden conversion */
 684                         mode = get_irn_mode(value);
 685                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 686                         emode = get_type_mode(get_entity_type(ent));
 687                         if (is_hidden_cast(mode, emode))
 688                                 return ir_address_taken;
 689                         break;
 690
 691                 case iro_Sel: {
 692                         /* Check the successor of irn. */
 693                         ir_address_taken_state res = find_address_taken_state(succ);
 694                         if (res != ir_address_not_taken)
 695                                 return res;
 696                         break;
 697                 }
 698
 699                 case iro_Call:
 700                         /* Only the call address is not an address taker but
 701                            this is an uninteresting case, so we ignore it here. */
 702                         return ir_address_taken;
 703
 704                 default:
 705                         /* another op, the address may be taken */
 706                         return ir_address_taken_unknown;
 707                 }
 708         }
 709         /* All successors finished, the address is not taken. */
 710         return ir_address_not_taken;
 711 }  /* find_address_taken_state */
 712
 713 /**
 714  * Update the "address taken" flag of all frame entities.
 715  */
 716 static void analyse_irg_address_taken(ir_graph *irg) {
 717         ir_type *ft = get_irg_frame_type(irg);
 718         ir_node *irg_frame;
 719         int i;
 720
 721         /* set initial state to not_taken, as this is the "smallest" state */
 722         for (i = get_class_n_members(ft) - 1; i >= 0; --i) {
 723                 ir_entity *ent = get_class_member(ft, i);
 724
 725                 set_entity_address_taken(ent, ir_address_not_taken);
 726         }
 727
 728         assure_irg_outs(irg);
 729
 730         irg_frame = get_irg_frame(irg);
 731
 732         for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
 733                 ir_node *succ = get_irn_out(irg_frame, i);
 734                 ir_address_taken_state state;
 735
 736             if (is_Sel(succ)) {
 737                         ir_entity *ent = get_Sel_entity(succ);
 738
 739                         if (get_entity_address_taken(ent) == ir_address_taken)
 740                                 continue;
 741
 742                         state = find_address_taken_state(succ);
 743                         if (state > get_entity_address_taken(ent))
 744                                 set_entity_address_taken(ent, state);
 745                 }
 746         }
 747         /* now computed */
 748         irg->adr_taken_state = ir_address_taken_computed;
 749 }  /* analyse_address_taken */
 750
 751 /* Returns the current address taken state of the graph. */
 752 ir_address_taken_computed_state get_irg_address_taken_state(const ir_graph *irg) {
 753         return irg->adr_taken_state;
 754 }  /* get_irg_address_taken_state */
 755
 756 /* Sets the current address taken state of the graph. */
 757 void set_irg_address_taken_state(ir_graph *irg, ir_address_taken_computed_state state) {
 758         irg->adr_taken_state = state;
 759 }  /* set_irg_address_taken_state */
 760
 761 /* Assure that the address taken flag is computed for the given graph. */
 762 void assure_irg_address_taken_computed(ir_graph *irg) {
 763         if (irg->adr_taken_state == ir_address_taken_not_computed)
 764                 analyse_irg_address_taken(irg);
 765 }  /* assure_irg_address_taken_computed */
 766
 767 /**
 768  * Initialize the address_taken flag for a global type like type.
 769  */
 770 static void init_taken_flag(ir_type * tp) {
 771         int i;
 772
 773         /* All external visible entities are at least
 774            ir_address_taken_unknown. This is very conservative. */
 775         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 776                 ir_entity *ent = get_compound_member(tp, i);
 777                 ir_address_taken_state state;
 778
 779                 state = get_entity_visibility(ent) == visibility_external_visible ?
 780                                 ir_address_taken_unknown : ir_address_not_taken ;
 781                 set_entity_address_taken(ent, state);
 782         }
 783 }  /* init_taken_flag */
 784
 785 #if 0
 786 /**
 787  * Print the address taken state of all entities of a given type for debugging.
 788  */
 789 static void print_address_taken_state(ir_type *tp) {
 790         int i;
 791         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 792                 ir_entity *ent = get_compound_member(tp, i);
 793                 ir_address_taken_state state = get_entity_address_taken(ent);
 794
 795                 if (state != ir_address_not_taken) {
 796                         assert(ir_address_not_taken <= state && state <= ir_address_taken);
 797                         ir_printf("%+F: %s\n", ent, get_address_taken_state_name(state));
 798                 }
 799         }
 800 }  /* print_address_taken_state */
 801 #endif
 802
 803 /**
 804  * Post-walker: check for global entity address
 805  */
 806 static void check_global_address(ir_node *irn, void *env) {
 807         ir_node *tls = env;
 808         ir_entity *ent;
 809         ir_address_taken_state state;
 810
 811         if (is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent) {
 812                 /* A global. */
 813                 ent = get_SymConst_entity(irn);
 814         } else if (is_Sel(irn) && get_Sel_ptr(irn) == tls) {
 815                 /* A TLS variable. */
 816                 ent = get_Sel_entity(irn);
 817         } else
 818                 return;
 819
 820         if (get_entity_address_taken(ent) >= ir_address_taken) {
 821                 /* Already at the maximum. */
 822                 return;
 823         }
 824         state = find_address_taken_state(irn);
 825         if (state > get_entity_address_taken(ent))
 826                 set_entity_address_taken(ent, state);
 827 }  /* check_global_address */
 828
 829 /**
 830  * Update the "address taken" flag of all global entities.
 831  */
 832 static void analyse_irp_globals_address_taken(void) {
 833         int i;
 834
 835         init_taken_flag(get_glob_type());
 836         init_taken_flag(get_tls_type());
 837
 838         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 839                 ir_graph *irg = get_irp_irg(i);
 840
 841                 assure_irg_outs(irg);
 842                 irg_walk_graph(irg, NULL, check_global_address, get_irg_tls(irg));
 843         }
 844         //print_address_taken_state(get_glob_type());
 845         //print_address_taken_state(get_tls_type());
 846
 847         /* now computed */
 848         irp->globals_adr_taken_state = ir_address_taken_computed;
 849 }  /* analyse_irp_globals_address_taken */
 850
 851 /* Returns the current address taken state of the globals. */
 852 ir_address_taken_computed_state get_irp_globals_address_taken_state(void) {
 853         return irp->globals_adr_taken_state;
 854 }  /* get_irp_globals_address_taken_state */
 855
 856 /* Sets the current address taken state of the graph. */
 857 void set_irp_globals_address_taken_state(ir_address_taken_computed_state state) {
 858         irp->globals_adr_taken_state = state;
 859 }  /* set_irg_address_taken_state */
 860
 861 /* Assure that the address taken flag is computed for the globals. */
 862 void assure_irp_globals_address_taken_computed(void) {
 863         if (irp->globals_adr_taken_state == ir_address_taken_not_computed)
 864                 analyse_irp_globals_address_taken();
 865 }  /* assure_irp_globals_address_taken_computed */