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 /* 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(adr1) && get_SymConst_kind(adr1) == symconst_addr_ent)
 339                 ent1 = get_SymConst_entity(adr1);
 340         else if (is_Sel(adr1))
 341                 ent1 = get_Sel_entity(adr1);
 342
 343         if (is_SymConst(adr2) && get_SymConst_kind(adr2) == symconst_addr_ent)
 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 static INLINE int is_global_var(ir_node *irn) {
 473         return is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent;
 474 }  /* is_global_var */
 475
 476 /**
 477  * Determine the alias relation between two addresses.
 478  */
 479 static ir_alias_relation _get_alias_relation(
 480         ir_graph *irg,
 481         ir_node *adr1, ir_mode *mode1,
 482         ir_node *adr2, ir_mode *mode2)
 483 {
 484         ir_opcode op1, op2;
 485         ir_entity *ent1, *ent2;
 486         unsigned options;
 487
 488         if (! get_opt_alias_analysis())
 489                 return may_alias;
 490
 491         if (adr1 == adr2)
 492                 return sure_alias;
 493
 494         options = get_irg_memory_disambiguator_options(irg);
 495
 496         /* The Armageddon switch */
 497         if (options & aa_opt_no_alias)
 498                 return no_alias;
 499
 500         /* Two save some code, sort the addresses by its id's. Beware, this
 501            might break some things, so better check here. */
 502         assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence broken");
 503         op1 = get_irn_opcode(adr1);
 504         op2 = get_irn_opcode(adr2);
 505
 506         if (op1 > op2) {
 507                 ir_node *t = adr1;
 508                 ir_mode *m = mode1;
 509                 adr1  = adr2;
 510                 mode1 = mode2;
 511                 adr2  = t;
 512                 mode2 = m;
 513         }
 514
 515         if (is_global_var(adr1)) {
 516                 /* first address is a global variable */
 517
 518                 if (is_global_var(adr2)) {
 519                         /* both addresses are global variables and we know
 520                            they are different (R1 a) */
 521                         if (get_SymConst_entity(adr1) != get_SymConst_entity(adr2))
 522                                 return no_alias;
 523                         else {
 524                                 /* equal entity addresses */
 525                                 return sure_alias;
 526                         }
 527                 }
 528                 if (is_Sel(adr2)) {
 529                         ir_node *base2 = find_base_adr(adr2, &ent2);
 530
 531                         if (is_global_var(base2)) {
 532                                 /* base2 address is a global var (R1 a) */
 533                                 if (adr1 != base2)
 534                                         return no_alias;
 535                         } else if (base2 == get_irg_frame(irg)) {
 536                                 /* the second one is a local variable so they are always
 537                                    different (R1 b) */
 538                                 return no_alias;
 539                         } else if (base2 == get_irg_tls(irg)) {
 540                                 /* the second one is a TLS variable so they are always
 541                                    different (R1 c) */
 542                                 return no_alias;
 543                         }
 544                 }
 545
 546                 /* Here we are: the first is a global var, the second some pointer. */
 547                 ent1 = get_SymConst_entity(adr1);
 548                 if (get_entity_address_taken(ent1) == ir_address_not_taken) {
 549                         /* The address of the global variable was never taken, so
 550                            the pointer cannot match (R2). */
 551                         return no_alias;
 552                 }
 553         } else if (is_Sel(adr1)) {
 554                 /* the first address is a Sel */
 555                 ir_node *base1 = find_base_adr(adr1, &ent1);
 556
 557                 if (base1 == get_irg_frame(irg)) {
 558                         /* first is a local variable ent1 */
 559                         if (is_Sel(adr2)) {
 560                                 /* the second address is a Sel */
 561                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 562
 563                                 if (base1 == base2) {
 564                                         /* identical bases: both are local variables */
 565                                         if (ent1 != ent2) {
 566                                                 /* both addresses are local variables and we know
 567                                                they are different (R1 a) */
 568                                                 return no_alias;
 569                                         } else {
 570                                                 /* same local var */
 571                                                 return different_sel_offsets(adr1, adr2);
 572                                         }
 573                                 } else if (base2 == get_irg_tls(irg)) {
 574                                         /* the second one is a TLS variable so they are always
 575                                        different (R1 d) */
 576                                         return no_alias;
 577                                 } else if (is_arg_Proj(base2)) {
 578                                         /* the second one is an offset from a parameter so they are
 579                                            always different (R1 e) */
 580                                         return no_alias;
 581                                 }
 582                         } else if (is_arg_Proj(adr2)) {
 583                                 /* a local variable and a parameter are always different (R1 e) */
 584                                 return no_alias;
 585                         }
 586                 } else if (base1 == get_irg_tls(irg)) {
 587                         /* the first is a TLS variable */
 588                         if (is_Sel(adr2)) {
 589                                 /* the second address is a Sel */
 590                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 591
 592                                 if (base1 == base2)
 593                                         if (ent1 != ent2) {
 594                                                 /* both addresses are tls variables and we know
 595                                                they are different (R1 a) */
 596                                         } else {
 597                                                 /* same tls var */
 598                                                 return different_sel_offsets(adr1, adr2);
 599                                         }
 600                                 else if (base2 == get_irg_frame(irg)) {
 601                                         /* the first one is a tls variable, the second a local one,
 602                                            they are different (R1 d) */
 603                                         return no_alias;
 604                                 }
 605                         }
 606                 } else if (is_arg_Proj(base1)) {
 607                         /* the first one is an offset from a parameter */
 608                         if (is_Sel(adr2)) {
 609                                 /* the second address is a Sel */
 610                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 611
 612                                 if (base2 == get_irg_frame(irg)) {
 613                                         /* the second one is a local variable so they are always
 614                                        different (R1 e) */
 615                                         return no_alias;
 616                                 }
 617                         }
 618                 } else if (is_global_var(base1)) {
 619                         /* the first one is a global variable */
 620                         ent1 = get_SymConst_entity(base1);
 621                         if (is_Sel(adr2)) {
 622                                 /* the second address is a Sel */
 623                                 ir_node *base2 = find_base_adr(adr2, &ent2);
 624
 625                                 if (base1 == base2) {
 626                                         /* same global var */
 627                                         return different_sel_offsets(adr1, adr2);
 628                                 }
 629                                 else if (base2 == get_irg_frame(irg)) {
 630                                         /* the second one is a local variable so they are always
 631                                        different (R1 a) */
 632                                         return no_alias;
 633                                 } else if (base2 == get_irg_tls(irg)) {
 634                                         /* the second one is a TLS variable so they are always
 635                                        different (R1 a) */
 636                                         return no_alias;
 637                                 } else if (is_arg_Proj(base2)) {
 638                                         if (get_entity_address_taken(ent1) == ir_address_not_taken) {
 639                                                 /* The address of the global variable was never taken, so
 640                                                    the pointer cannot match (R2). */
 641                                                 return no_alias;
 642                                         }
 643                                 } else if (is_global_var(base2)) {
 644                                         ent2 = get_SymConst_entity(base2);
 645                                         /* both addresses are global variables and we know
 646                                            they are different (R1 a) */
 647                                         if (ent1 != ent2)
 648                                                 return no_alias;
 649                                 }
 650                         }
 651                 }
 652         } else {
 653                 /* some pointers, check if they have the same base buf constant offset */
 654                 ir_alias_relation rel = different_pointer(adr1, mode1, adr2, mode2);
 655                 if (rel != may_alias)
 656                         return rel;
 657         }
 658
 659
 660         if (options & aa_opt_type_based) { /* Type based alias analysis */
 661                 ir_alias_relation rel;
 662
 663                 if (options & aa_opt_byte_type_may_alias) {
 664                         if (get_mode_size_bits(mode1) == 8 || get_mode_size_bits(mode2) == 8) {
 665                                 /* One of the modes address a byte. Assume a may_alias and leave
 666                                    the type based check. */
 667                                 goto leave_type_based_alias;
 668                         }
 669                 }
 670                 /* cheap check: If the mode sizes did not match, the types MUST be different */
 671                 if (get_mode_size_bits(mode1) != get_mode_size_bits(mode2))
 672                         return no_alias;
 673
 674                 /* cheap test: if only one is a reference mode, no alias */
 675                 if (mode_is_reference(mode1) != mode_is_reference(mode2))
 676                         return no_alias;
 677
 678                 /* try rule R5 */
 679                 rel = different_types(adr1, adr2);
 680                 if (rel != may_alias)
 681                         return rel;
 682 leave_type_based_alias:;
 683         }
 684
 685         /* do we have a language specific memory disambiguator? */
 686         if (language_disambuigator) {
 687                 ir_alias_relation rel = (*language_disambuigator)(irg, adr1, mode1, adr2, mode2);
 688                 if (rel != may_alias)
 689                         return rel;
 690         }
 691
 692         /* access points-to information here */
 693         return may_alias;
 694 }  /* _get_alias_relation */
 695
 696 /*
 697  * Determine the alias relation between two addresses.
 698  */
 699 ir_alias_relation get_alias_relation(
 700         ir_graph *irg,
 701         ir_node *adr1, ir_mode *mode1,
 702         ir_node *adr2, ir_mode *mode2)
 703 {
 704         ir_alias_relation rel = _get_alias_relation(irg, adr1, mode1, adr2, mode2);
 705         DB((dbg, LEVEL_1, "alias(%+F, %+f) = %s\n", adr1, adr2, get_ir_alias_relation_name(rel)));
 706         return rel;
 707 }  /* get_alias_relation */
 708
 709 /* Set a source language specific memory disambiguator function. */
 710 void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func) {
 711         language_disambuigator = func;
 712 }  /* set_language_memory_disambiguator */
 713
 714 /** The result cache for the memory disambiguator. */
 715 static set *result_cache = NULL;
 716
 717 /** An entry in the relation cache. */
 718 typedef struct mem_disambig_entry {
 719         ir_node           *adr1;    /**< The first address. */
 720         ir_node           *adr2;    /**< The second address. */
 721         ir_alias_relation result;   /**< The alias relation result. */
 722 } mem_disambig_entry;
 723
 724 #define HASH_ENTRY(adr1, adr2)  (HASH_PTR(adr1) ^ HASH_PTR(adr2))
 725
 726 /**
 727  * Compare two relation cache entries.
 728  */
 729 static int cmp_mem_disambig_entry(const void *elt, const void *key, size_t size) {
 730         const mem_disambig_entry *p1 = elt;
 731         const mem_disambig_entry *p2 = key;
 732         (void) size;
 733
 734         return p1->adr1 == p2->adr1 && p1->adr2 == p2->adr2;
 735 }  /* cmp_mem_disambig_entry */
 736
 737 /**
 738  * Initialize the relation cache.
 739  */
 740 void mem_disambig_init(void) {
 741         result_cache = new_set(cmp_mem_disambig_entry, 8);
 742 }  /* mem_disambig_init */
 743
 744 /*
 745  * Determine the alias relation between two addresses.
 746  */
 747 ir_alias_relation get_alias_relation_ex(
 748         ir_graph *irg,
 749         ir_node *adr1, ir_mode *mode1,
 750         ir_node *adr2, ir_mode *mode2)
 751 {
 752         mem_disambig_entry key, *entry;
 753
 754         if (! get_opt_alias_analysis())
 755                 return may_alias;
 756
 757         if (get_irn_opcode(adr1) > get_irn_opcode(adr2)) {
 758                 ir_node *t = adr1;
 759                 adr1 = adr2;
 760                 adr2 = t;
 761         }
 762
 763         key.adr1 = adr1;
 764         key.adr2 = adr2;
 765         entry = set_find(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 766         if (entry)
 767                 return entry->result;
 768
 769         key.result = get_alias_relation(irg, adr1, mode1, adr2, mode2);
 770
 771         set_insert(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
 772         return key.result;
 773 }  /* get_alias_relation_ex */
 774
 775 /* Free the relation cache. */
 776 void mem_disambig_term(void) {
 777         if (result_cache) {
 778                 del_set(result_cache);
 779                 result_cache = NULL;
 780         }
 781 }  /* mem_disambig_term */
 782
 783 /**
 784  * Check the mode of a Load/Store with the mode of the entity
 785  * that is accessed.
 786  * If the mode of the entity and the Load/Store mode do not match, we
 787  * have the bad reinterpret case:
 788  *
 789  * int i;
 790  * char b = *(char *)&i;
 791  *
 792  * We do NOT count this as one value and return address_taken
 793  * in that case.
 794  * However, we support an often used case. If the mode is two-complement
 795  * we allow casts between signed/unsigned.
 796  *
 797  * @param mode     the mode of the Load/Store
 798  * @param ent_mode the mode of the accessed entity
 799  *
 800  * @return non-zero if the Load/Store is a hidden cast, zero else
 801  */
 802 static int is_hidden_cast(ir_mode *mode, ir_mode *ent_mode) {
 803         if (ent_mode != mode) {
 804                 if (ent_mode == NULL ||
 805                         get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
 806                         get_mode_sort(ent_mode) != get_mode_sort(mode) ||
 807                         get_mode_arithmetic(ent_mode) != irma_twos_complement ||
 808                         get_mode_arithmetic(mode) != irma_twos_complement)
 809                         return 1;
 810         }
 811         return 0;
 812 }  /* is_hidden_cast */
 813
 814 /**
 815  * Determine the address_taken state of a node (or it's successor Sels).
 816  *
 817  * @param irn  the node
 818  */
 819 static ir_address_taken_state find_address_taken_state(ir_node *irn) {
 820         int     i, j;
 821         ir_mode *emode, *mode;
 822         ir_node *value;
 823         ir_entity *ent;
 824
 825         for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 826                 ir_node *succ = get_irn_out(irn, i);
 827
 828                 switch (get_irn_opcode(succ)) {
 829                 case iro_Load:
 830                         /* check if this load is not a hidden conversion */
 831                         mode = get_Load_mode(succ);
 832                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 833                         emode = get_type_mode(get_entity_type(ent));
 834                         if (is_hidden_cast(mode, emode))
 835                                 return ir_address_taken;
 836                         break;
 837
 838                 case iro_Store:
 839                         /* check that the node is not the Store's value */
 840                         value = get_Store_value(succ);
 841                         if (value == irn)
 842                                 return ir_address_taken;
 843                         /* check if this Store is not a hidden conversion */
 844                         mode = get_irn_mode(value);
 845                         ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
 846                         emode = get_type_mode(get_entity_type(ent));
 847                         if (is_hidden_cast(mode, emode))
 848                                 return ir_address_taken;
 849                         break;
 850
 851                 case iro_Sel: {
 852                         /* Check the successor of irn. */
 853                         ir_address_taken_state res = find_address_taken_state(succ);
 854                         if (res != ir_address_not_taken)
 855                                 return res;
 856                         break;
 857                 }
 858
 859                 case iro_Call:
 860                         /* Only the call address is not an address taker but
 861                            this is an uninteresting case, so we ignore it here. */
 862                         for (j = get_Call_n_params(succ) - 1; j >= 0; --j) {
 863                                 ir_node *param = get_Call_param(succ, j);
 864                                 if (param == irn)
 865                                         return ir_address_taken;
 866                         }
 867                         break;
 868
 869                 default:
 870                         /* another op, the address may be taken */
 871                         return ir_address_taken_unknown;
 872                 }
 873         }
 874         /* All successors finished, the address is not taken. */
 875         return ir_address_not_taken;
 876 }  /* find_address_taken_state */
 877
 878 /**
 879  * Update the "address taken" flag of all frame entities.
 880  */
 881 static void analyse_irg_address_taken(ir_graph *irg) {
 882         ir_type *ft = get_irg_frame_type(irg);
 883         ir_node *irg_frame;
 884         int i;
 885
 886         /* set initial state to not_taken, as this is the "smallest" state */
 887         for (i = get_class_n_members(ft) - 1; i >= 0; --i) {
 888                 ir_entity *ent = get_class_member(ft, i);
 889
 890                 set_entity_address_taken(ent, ir_address_not_taken);
 891         }
 892
 893         assure_irg_outs(irg);
 894
 895         irg_frame = get_irg_frame(irg);
 896
 897         for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
 898                 ir_node *succ = get_irn_out(irg_frame, i);
 899                 ir_address_taken_state state;
 900
 901             if (is_Sel(succ)) {
 902                         ir_entity *ent = get_Sel_entity(succ);
 903
 904                         if (get_entity_address_taken(ent) == ir_address_taken)
 905                                 continue;
 906
 907                         state = find_address_taken_state(succ);
 908                         if (state > get_entity_address_taken(ent))
 909                                 set_entity_address_taken(ent, state);
 910                 }
 911         }
 912         /* now computed */
 913         irg->adr_taken_state = ir_address_taken_computed;
 914 }  /* analyse_address_taken */
 915
 916 /* Returns the current address taken state of the graph. */
 917 ir_address_taken_computed_state get_irg_address_taken_state(const ir_graph *irg) {
 918         return irg->adr_taken_state;
 919 }  /* get_irg_address_taken_state */
 920
 921 /* Sets the current address taken state of the graph. */
 922 void set_irg_address_taken_state(ir_graph *irg, ir_address_taken_computed_state state) {
 923         irg->adr_taken_state = state;
 924 }  /* set_irg_address_taken_state */
 925
 926 /* Assure that the address taken flag is computed for the given graph. */
 927 void assure_irg_address_taken_computed(ir_graph *irg) {
 928         if (irg->adr_taken_state == ir_address_taken_not_computed)
 929                 analyse_irg_address_taken(irg);
 930 }  /* assure_irg_address_taken_computed */
 931
 932
 933 /**
 934  * Initialize the address_taken flag for a global type like type.
 935  */
 936 static void init_taken_flag(ir_type * tp) {
 937         int i;
 938
 939         /* All external visible entities are at least
 940            ir_address_taken_unknown. This is very conservative. */
 941         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 942                 ir_entity *ent = get_compound_member(tp, i);
 943                 ir_address_taken_state state;
 944
 945                 state = get_entity_visibility(ent) == visibility_external_visible ?
 946                                 ir_address_taken_unknown : ir_address_not_taken ;
 947                 set_entity_address_taken(ent, state);
 948         }
 949 }  /* init_taken_flag */
 950
 951 /**
 952  * Mark all entities used in the initializer for the given entity as address taken
 953  */
 954 static void check_initializer(ir_entity *ent) {
 955         ir_node *n;
 956         int i;
 957
 958         /* do not check uninitialized values */
 959         if (get_entity_variability(ent) == variability_uninitialized)
 960                 return;
 961
 962         /* Beware: Methods initialized with "themself". This does not count as a taken
 963            address. */
 964         if (is_Method_type(get_entity_type(ent)))
 965                 return;
 966
 967         if (is_atomic_entity(ent)) {
 968                 /* let's check if it's an address */
 969                 n = get_atomic_ent_value(ent);
 970                 if (is_SymConst(n) && get_SymConst_kind(n) == symconst_addr_ent) {
 971                         ir_entity *ent = get_SymConst_entity(n);
 972                         set_entity_address_taken(ent, ir_address_taken);
 973                 }
 974         } else {
 975                 for (i = get_compound_ent_n_values(ent) - 1; i >= 0; --i) {
 976                         n = get_compound_ent_value(ent, i);
 977
 978                         /* let's check if it's an address */
 979                         if (is_SymConst(n) && get_SymConst_kind(n) == symconst_addr_ent) {
 980                                 ir_entity *ent = get_SymConst_entity(n);
 981                                 set_entity_address_taken(ent, ir_address_taken);
 982                         }
 983                 }
 984         }
 985 }  /* check_initializer */
 986
 987
 988 /**
 989  * Mark all entities used in initializers as address taken
 990  */
 991 static void check_initializers(ir_type *tp) {
 992         int i;
 993
 994         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
 995                 ir_entity *ent = get_compound_member(tp, i);
 996
 997                 check_initializer(ent);
 998         }
 999 }  /* check_initializers */
1000
1001 #ifdef DEBUG_libfirm
1002 /**
1003  * Print the address taken state of all entities of a given type for debugging.
1004  */
1005 static void print_address_taken_state(ir_type *tp) {
1006         int i;
1007         for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
1008                 ir_entity *ent = get_compound_member(tp, i);
1009                 ir_address_taken_state state = get_entity_address_taken(ent);
1010
1011                 if (state != ir_address_not_taken) {
1012                         assert(ir_address_not_taken <= (int) state && state <= ir_address_taken);
1013                         ir_printf("%+F: %s\n", ent, get_address_taken_state_name(state));
1014                 }
1015         }
1016 }  /* print_address_taken_state */
1017 #endif /* DEBUG_libfirm */
1018
1019 /**
1020  * Post-walker: check for global entity address
1021  */
1022 static void check_global_address(ir_node *irn, void *env) {
1023         ir_node *tls = env;
1024         ir_entity *ent;
1025         ir_address_taken_state state;
1026
1027         if (is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent) {
1028                 /* A global. */
1029                 ent = get_SymConst_entity(irn);
1030         } else if (is_Sel(irn) && get_Sel_ptr(irn) == tls) {
1031                 /* A TLS variable. */
1032                 ent = get_Sel_entity(irn);
1033         } else
1034                 return;
1035
1036         if (get_entity_address_taken(ent) >= ir_address_taken) {
1037                 /* Already at the maximum. */
1038                 return;
1039         }
1040         state = find_address_taken_state(irn);
1041         if (state > get_entity_address_taken(ent))
1042                 set_entity_address_taken(ent, state);
1043 }  /* check_global_address */
1044
1045 /**
1046  * Update the "address taken" flag of all global entities.
1047  */
1048 static void analyse_irp_globals_address_taken(void) {
1049         int i;
1050
1051         FIRM_DBG_REGISTER(dbg, "firm.ana.irmemory");
1052
1053         init_taken_flag(get_glob_type());
1054         init_taken_flag(get_tls_type());
1055
1056         check_initializers(get_glob_type());
1057         check_initializers(get_tls_type());
1058
1059         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1060                 ir_graph *irg = get_irp_irg(i);
1061
1062                 assure_irg_outs(irg);
1063                 irg_walk_graph(irg, NULL, check_global_address, get_irg_tls(irg));
1064         }
1065
1066 #ifdef DEBUG_libfirm
1067         if (firm_dbg_get_mask(dbg) & LEVEL_1) {
1068                 print_address_taken_state(get_glob_type());
1069                 print_address_taken_state(get_tls_type());
1070         }
1071 #endif /* DEBUG_libfirm */
1072
1073         /* now computed */
1074         irp->globals_adr_taken_state = ir_address_taken_computed;
1075 }  /* analyse_irp_globals_address_taken */
1076
1077 /* Returns the current address taken state of the globals. */
1078 ir_address_taken_computed_state get_irp_globals_address_taken_state(void) {
1079         return irp->globals_adr_taken_state;
1080 }  /* get_irp_globals_address_taken_state */
1081
1082 /* Sets the current address taken state of the graph. */
1083 void set_irp_globals_address_taken_state(ir_address_taken_computed_state state) {
1084         irp->globals_adr_taken_state = state;
1085 }  /* set_irg_address_taken_state */
1086
1087 /* Assure that the address taken flag is computed for the globals. */
1088 void assure_irp_globals_address_taken_computed(void) {
1089         if (irp->globals_adr_taken_state == ir_address_taken_not_computed)
1090                 analyse_irp_globals_address_taken();
1091 }  /* assure_irp_globals_address_taken_computed */
1092
1093
1094 #include <adt/pmap.h>
1095 #include "typerep.h"
1096
1097 DEBUG_ONLY(static firm_dbg_module_t *dbgcall = NULL;)
1098
1099 /** Maps method types to cloned method types. */
1100 static pmap *mtp_map;
1101
1102 /**
1103  * Clone a method type if not already cloned.
1104  */
1105 static ir_type *clone_type_and_cache(ir_type *tp) {
1106         ir_type *res;
1107         pmap_entry *e = pmap_find(mtp_map, tp);
1108
1109         if (e)
1110                 return e->value;
1111
1112         res = clone_type_method(tp);
1113         pmap_insert(mtp_map, tp, res);
1114
1115         return res;
1116 }  /* clone_type_and_cache */
1117
1118 /**
1119  * Copy the calling conventions from the entities to the call type.
1120  */
1121 static void update_calls_to_private(ir_node *call, void *env) {
1122         (void) env;
1123         if (is_Call(call)) {
1124                 ir_node *ptr = get_Call_ptr(call);
1125
1126                 if (is_SymConst(ptr)) {
1127                         ir_entity *ent = get_SymConst_entity(ptr);
1128                         ir_type *mtp = get_entity_type(ent);
1129                         ir_type *ctp = get_Call_type(call);
1130
1131                         if ((get_method_additional_properties(ctp) & mtp_property_private) == 0) {
1132                                 ctp = clone_type_and_cache(ctp);
1133                                 set_method_additional_property(ctp, mtp_property_private);
1134                                 set_Call_type(call, ctp);
1135                                 DB((dbgcall, LEVEL_1, "changed call to private method %+F\n", ent));
1136                         }
1137                 }
1138         }
1139 }  /* update_calls_to_private */
1140
1141 /* Mark all private methods, i.e. those of which all call sites are known. */
1142 void mark_private_methods(void) {
1143         int i;
1144         int changed = 0;
1145
1146         FIRM_DBG_REGISTER(dbgcall, "firm.opt.cc");
1147
1148         assure_irp_globals_address_taken_computed();
1149
1150         mtp_map = pmap_create();
1151
1152         /* first step: change the calling conventions of the local non-escaped entities */
1153         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1154                 ir_graph               *irg = get_irp_irg(i);
1155                 ir_entity              *ent = get_irg_entity(irg);
1156                 ir_address_taken_state state = get_entity_address_taken(ent);
1157
1158                 if (get_entity_visibility(ent) == visibility_local &&
1159                     state == ir_address_not_taken) {
1160                         ir_type *mtp = get_entity_type(ent);
1161
1162                         set_entity_additional_property(ent, mtp_property_private);
1163                         if ((get_method_additional_properties(mtp) & mtp_property_private) == 0) {
1164                                 /* need a new type */
1165                                 mtp = clone_type_and_cache(mtp);
1166                                 set_entity_type(ent, mtp);
1167                                 set_method_additional_property(mtp, mtp_property_private);
1168                                 changed = 1;
1169                         }
1170                         DB((dbgcall, LEVEL_1, "found private method %+F\n", ent));
1171                 }
1172         }
1173
1174         if (changed)
1175                 all_irg_walk(NULL, update_calls_to_private, NULL);
1176
1177         pmap_destroy(mtp_map);
1178 }  /* mark_private_methods */