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

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