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