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

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