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

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