gcc/tree-ssa-alias-warnings.c

   1 /* Strict aliasing checks.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3    Contributed by Silvius Rus <rus@google.com>.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "alloc-pool.h"
  26 #include "tree.h"
  27 #include "tree-dump.h"
  28 #include "tree-flow.h"
  29 #include "params.h"
  30 #include "function.h"
  31 #include "expr.h"
  32 #include "toplev.h"
  33 #include "diagnostic.h"
  34 #include "tree-ssa-structalias.h"
  35 #include "tree-ssa-propagate.h"
  36 #include "langhooks.h"
  37
  38 /* Module to issue a warning when a program uses data through a type
  39    different from the type through which the data were defined.
  40    Implements -Wstrict-aliasing and -Wstrict-aliasing=n.
  41    These checks only happen when -fstrict-aliasing is present.
  42
  43    The idea is to use the compiler to identify occurrences of nonstandard
  44    aliasing, and report them to programmers.  Programs free of such aliasing
  45    are more portable, maintainable, and can usually be optimized better.
  46
  47    The current, as of April 2007, C and C++ language standards forbid
  48    accessing data of type A through an lvalue of another type B,
  49    with certain exceptions. See the C Standard ISO/IEC 9899:1999,
  50    section 6.5, paragraph 7, and the C++ Standard ISO/IEC 14882:1998,
  51    section 3.10, paragraph 15.
  52
  53    Example 1:*a is used as int but was defined as a float, *b.
  54         int* a = ...;
  55         float* b = reinterpret_cast<float*> (a);
  56         *b = 2.0;
  57         return *a
  58
  59    Unfortunately, the problem is in general undecidable if we take into
  60    account arithmetic expressions such as array indices or pointer arithmetic.
  61    (It is at least as hard as Peano arithmetic decidability.)
  62    Even ignoring arithmetic, the problem is still NP-hard, because it is
  63    at least as hard as flow-insensitive may-alias analysis, which was proved
  64    NP-hard by Horwitz et al, TOPLAS 1997.
  65
  66    It is clear that we need to choose some heuristics.
  67    Unfortunately, various users have different goals which correspond to
  68    different time budgets so a common approach will not suit all.
  69    We present the user with three effort/accuracy levels.  By accuracy, we mean
  70    a common-sense mix of low count of false positives with a
  71    reasonably low number of false negatives.  We are heavily biased
  72    towards a low count of false positives.
  73    The effort (compilation time) is likely to increase with the level.
  74
  75    -Wstrict-aliasing=1
  76    ===================
  77    Most aggressive, least accurate.  Possibly useful when higher levels
  78    do not warn but -fstrict-aliasing still breaks the code, as
  79    it has very few false negatives.
  80    Warn for all bad pointer conversions, even if never dereferenced.
  81    Implemented in the front end (c-common.c).
  82    Uses alias_sets_might_conflict to compare types.
  83
  84    -Wstrict-aliasing=2
  85    ===================
  86    Aggressive, not too precise.
  87    May still have many false positives (not as many as level 1 though),
  88    and few false negatives (but possibly more than level 1).
  89    Runs only in the front end. Uses alias_sets_might_conflict to
  90    compare types. Does not check for pointer dereferences.
  91    Only warns when an address is taken. Warns about incomplete type punning.
  92
  93    -Wstrict-aliasing=3 (default)
  94    ===================
  95    Should have very few false positives and few false negatives.
  96    Takes care of the common punn+dereference pattern in the front end:
  97    *(int*)&some_float.
  98    Takes care of multiple statement cases in the back end,
  99    using flow-sensitive points-to information (-O required).
 100    Uses alias_sets_conflict_p to compare types and only warns
 101    when the converted pointer is dereferenced.
 102    Does not warn about incomplete type punning.
 103
 104    Future improvements can be included by adding higher levels.
 105
 106    In summary, expression level analysis is performed in the front-end,
 107    and multiple-statement analysis is performed in the backend.
 108    The remainder of this discussion is only about the backend analysis.
 109
 110    This implementation uses flow-sensitive points-to information.
 111    Flow-sensitivity refers to accesses to the pointer, and not the object
 112    pointed.  For instance, we do not warn about the following case.
 113
 114    Example 2.
 115         int* a = (int*)malloc (...);
 116         float* b = reinterpret_cast<float*> (a);
 117         *b = 2.0;
 118         a = (int*)malloc (...);
 119         return *a;
 120
 121    In SSA, it becomes clear that the INT value *A_2 referenced in the
 122    return statement is not aliased to the FLOAT defined through *B_1.
 123         int* a_1 = (int*)malloc (...);
 124         float* b_1 = reinterpret_cast<float*> (a_1);
 125         *b_1 = 2.0;
 126         a_2 = (int*)malloc (...);
 127         return *a_2;
 128
 129
 130    Algorithm Outline
 131    =================
 132
 133    ForEach (ptr, object) in the points-to table
 134      If (incompatible_types (*ptr, object))
 135        If (referenced (ptr, current function)
 136            and referenced (object, current function))
 137          Issue warning (ptr, object, reference locations)
 138
 139    The complexity is:
 140    O (sizeof (points-to table)
 141       + sizeof (function body) * lookup_time (points-to table))
 142
 143    Pointer dereference locations are looked up on demand.  The search is
 144    a single scan of the function body, in which all references to pointers
 145    and objects in the points-to table are recorded.  However, this dominant
 146    time factor occurs rarely, only when cross-type aliasing was detected.
 147
 148
 149    Limitations of the Proposed Implementation
 150    ==========================================
 151
 152    1. We do not catch the following case, because -fstrict-aliasing will
 153       associate different tags with MEM while building points-to information,
 154       thus before we get to analyze it.
 155       XXX: this could be solved by either running with -fno-strict-aliasing
 156       or by recording the points-to information before splitting the original
 157       tag based on type.
 158
 159    Example 3.
 160         void* mem = malloc (...);
 161         int* pi = reinterpret_cast<int*> (mem);
 162         float* b = reinterpret_cast<float*> (mem);
 163         *b = 2.0;
 164         return *pi+1;
 165
 166    2. We do not check whether the two conflicting (de)references can
 167       reach each other in the control flow sense.  If we fixed limitation
 168       1, we would wrongly issue a warning in the following case.
 169
 170    Example 4.
 171         void* raw = malloc (...);
 172         if (...) {
 173          float* b = reinterpret_cast<float*> (raw);
 174          *b = 2.0;
 175          return (int)*b;
 176         } else {
 177          int* a = reinterpret_cast<int*> (raw);
 178          *a = 1;
 179          return *a;
 180
 181    3. Only simple types are compared, thus no structures, unions or classes
 182       are analyzed.  A first attempt to deal with structures introduced much
 183       complication and has not showed much improvement in preliminary tests,
 184       so it was left out.
 185
 186    4. All analysis is intraprocedural.  */
 187
 188
 189 /* Local declarations.  */
 190 static void find_references_in_function (void);
 191 \f
 192
 193
 194 /* Get main type of tree TYPE, stripping array dimensions and qualifiers.  */
 195
 196 static tree
 197 get_main_type (tree type)
 198 {
 199   while (TREE_CODE (type) == ARRAY_TYPE)
 200     type = TREE_TYPE (type);
 201   return TYPE_MAIN_VARIANT (type);
 202 }
 203
 204
 205 /* Get the type of the given object.  If IS_PTR is true, get the type of the
 206    object pointed to or referenced by OBJECT instead.
 207    For arrays, return the element type.  Ignore all qualifiers.  */
 208
 209 static tree
 210 get_otype (tree object, bool is_ptr)
 211 {
 212   tree otype = TREE_TYPE (object);
 213
 214   if (is_ptr)
 215     {
 216       gcc_assert (POINTER_TYPE_P (otype));
 217       otype = TREE_TYPE (otype);
 218     }
 219   return get_main_type (otype);
 220 }
 221
 222
 223 /* Return true if tree TYPE is struct, class or union.  */
 224
 225 static bool
 226 struct_class_union_p (tree type)
 227 {
 228   return (TREE_CODE (type) == RECORD_TYPE
 229           || TREE_CODE (type) == UNION_TYPE
 230           || TREE_CODE (type) == QUAL_UNION_TYPE);
 231 }
 232 \f
 233
 234
 235 /* Keep data during a search for an aliasing site.
 236    RHS = object or pointer aliased.  No LHS is specified because we are only
 237    looking in the UseDef paths of a given variable, so LHS will always be
 238    an SSA name of the same variable.
 239    When IS_RHS_POINTER = true, we are looking for ... = RHS.  Otherwise,
 240    we are looking for ... = &RHS.
 241    SITE is the output of a search, non-NULL if the search succeeded.  */
 242
 243 struct alias_match
 244 {
 245   tree rhs;
 246   bool is_rhs_pointer;
 247   tree site;
 248 };
 249
 250
 251 /* Callback for find_alias_site.  Return true if the right hand site
 252    of STMT matches DATA.  */
 253
 254 static bool
 255 find_alias_site_helper (tree var ATTRIBUTE_UNUSED, tree stmt, void *data)
 256 {
 257   struct alias_match *match = (struct alias_match *) data;
 258   tree rhs_pointer = get_rhs (stmt);
 259   tree to_match = NULL_TREE;
 260
 261   while (TREE_CODE (rhs_pointer) == NOP_EXPR
 262          || TREE_CODE (rhs_pointer) == CONVERT_EXPR
 263          || TREE_CODE (rhs_pointer) == VIEW_CONVERT_EXPR)
 264     rhs_pointer = TREE_OPERAND (rhs_pointer, 0);
 265
 266   if (!rhs_pointer)
 267     /* Not a type conversion.  */
 268     return false;
 269
 270   if (TREE_CODE (rhs_pointer) == ADDR_EXPR && !match->is_rhs_pointer)
 271     to_match = TREE_OPERAND (rhs_pointer, 0);
 272   else if (POINTER_TYPE_P (rhs_pointer) && match->is_rhs_pointer)
 273     to_match = rhs_pointer;
 274
 275   if (to_match != match->rhs)
 276     /* Type conversion, but not a name match.  */
 277     return false;
 278
 279   /* Found it.  */
 280   match->site = stmt;
 281   return true;
 282 }
 283
 284
 285 /* Find the statement where OBJECT1 gets aliased to OBJECT2.
 286    If IS_PTR2 is true, consider OBJECT2 to be the name of a pointer or
 287    reference rather than the actual aliased object.
 288    For now, just implement the case where OBJECT1 is an SSA name defined
 289    by a PHI statement.  */
 290
 291 static tree
 292 find_alias_site (tree object1, bool is_ptr1 ATTRIBUTE_UNUSED,
 293                  tree object2, bool is_ptr2)
 294 {
 295   struct alias_match match;
 296
 297   match.rhs = object2;
 298   match.is_rhs_pointer = is_ptr2;
 299   match.site = NULL_TREE;
 300
 301   if (TREE_CODE (object1) != SSA_NAME)
 302     return NULL_TREE;
 303
 304   walk_use_def_chains (object1, find_alias_site_helper, &match, false);
 305   return match.site;
 306 }
 307
 308
 309 /* Structure to store temporary results when trying to figure out whether
 310    an object is referenced.  Just its presence in the text is not enough,
 311    as we may just be taking its address.  */
 312
 313 struct match_info
 314 {
 315   tree object;
 316   bool is_ptr;
 317   /* The difference between the number of references to OBJECT
 318      and the number of occurrences of &OBJECT.  */
 319   int found;
 320 };
 321
 322
 323 /* Return the base if EXPR is an SSA name.  Return EXPR otherwise.  */
 324
 325 static tree
 326 get_ssa_base (tree expr)
 327 {
 328   if (TREE_CODE (expr) == SSA_NAME)
 329     return SSA_NAME_VAR (expr);
 330   else
 331     return expr;
 332 }
 333
 334
 335 /* Record references to objects and pointer dereferences across some piece of
 336    code.  The number of references is recorded for each item.
 337    References to an object just to take its address are not counted.
 338    For instance, if PTR is a pointer and OBJ is an object:
 339    1. Expression &obj + *ptr will have the following reference match structure:
 340    ptrs: <ptr, 1>
 341    objs: <ptr, 1>
 342    OBJ does not appear as referenced because we just take its address.
 343    2. Expression ptr + *ptr will have the following reference match structure:
 344    ptrs: <ptr, 1>
 345    objs: <ptr, 2>
 346    PTR shows up twice as an object, but is dereferenced only once.
 347
 348    The elements of the hash tables are tree_map objects.  */
 349 struct reference_matches
 350 {
 351   htab_t ptrs;
 352   htab_t objs;
 353 };
 354
 355
 356 /* Return the match, if any.  Otherwise, return NULL_TREE.  It will
 357    return NULL_TREE even when a match was found, if the value associated
 358    to KEY is NULL_TREE.  */
 359
 360 static inline tree
 361 match (htab_t ref_map, tree key)
 362 {
 363   struct tree_map *found;
 364   void **slot = NULL;
 365   slot = htab_find_slot (ref_map, &key, NO_INSERT);
 366
 367   if (!slot)
 368     return NULL_TREE;
 369
 370   found = (struct tree_map *) *slot;
 371   return found->to;
 372 }
 373
 374
 375 /* Set the entry corresponding to KEY, but only if the entry
 376    already exists and its value is NULL_TREE.  Otherwise, do nothing.  */
 377
 378 static inline void
 379 maybe_add_match (htab_t ref_map, struct tree_map *key)
 380 {
 381   struct tree_map *found = (struct tree_map *) htab_find (ref_map, key);
 382
 383   if (found && !found->to)
 384     found->to = key->to;
 385 }
 386
 387
 388 /* Add an entry to HT, with key T and value NULL_TREE.  */
 389
 390 static void
 391 add_key (htab_t ht, tree t, alloc_pool references_pool)
 392 {
 393   void **slot;
 394   struct tree_map *tp = (struct tree_map *) pool_alloc (references_pool);
 395
 396   tp->base.from = t;
 397   tp->to = NULL_TREE;
 398   slot = htab_find_slot (ht, &t, INSERT);
 399   *slot = (void *) tp;
 400 }
 401
 402
 403 /* Some memory to keep the objects in the reference table.  */
 404
 405 static alloc_pool ref_table_alloc_pool = NULL;
 406
 407
 408 /* Get some memory to keep the objects in the reference table.  */
 409
 410 static inline alloc_pool
 411 reference_table_alloc_pool (bool build)
 412 {
 413   if (ref_table_alloc_pool || !build)
 414     return ref_table_alloc_pool;
 415
 416   ref_table_alloc_pool =
 417     create_alloc_pool ("ref_table_alloc_pool", sizeof (struct tree_map), 20);
 418
 419   return ref_table_alloc_pool;
 420 }
 421
 422
 423 /* Initialize the reference table by adding all pointers in the points-to
 424    table as keys, and NULL_TREE as associated values.  */
 425
 426 static struct reference_matches *
 427 build_reference_table (void)
 428 {
 429   unsigned int i;
 430   struct reference_matches *ref_table = NULL;
 431   alloc_pool references_pool = reference_table_alloc_pool (true);
 432
 433   ref_table = XNEW (struct reference_matches);
 434   ref_table->objs = htab_create (10, tree_map_base_hash, tree_map_eq, NULL);
 435   ref_table->ptrs = htab_create (10, tree_map_base_hash, tree_map_eq, NULL);
 436
 437   for (i = 1; i < num_ssa_names; i++)
 438     {
 439       tree ptr = ssa_name (i);
 440       struct ptr_info_def *pi;
 441
 442       if (ptr == NULL_TREE)
 443         continue;
 444
 445       pi = SSA_NAME_PTR_INFO (ptr);
 446
 447       if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag)
 448         {
 449           /* Add pointer to the interesting dereference list.  */
 450           add_key (ref_table->ptrs, ptr, references_pool);
 451
 452           /* Add all aliased names to the interesting reference list.  */
 453           if (pi->pt_vars)
 454             {
 455               unsigned ix;
 456               bitmap_iterator bi;
 457
 458               EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi)
 459                 {
 460                   tree alias = referenced_var (ix);
 461                   add_key (ref_table->objs, alias, references_pool);
 462                 }
 463             }
 464         }
 465     }
 466
 467   return ref_table;
 468 }
 469
 470
 471 /*  Reference table.  */
 472
 473 static struct reference_matches *ref_table = NULL;
 474
 475
 476 /* Clean up the reference table if allocated.  */
 477
 478 static void
 479 maybe_free_reference_table (void)
 480 {
 481   if (ref_table)
 482     {
 483       htab_delete (ref_table->ptrs);
 484       htab_delete (ref_table->objs);
 485       free (ref_table);
 486       ref_table = NULL;
 487     }
 488
 489   if (ref_table_alloc_pool)
 490     {
 491       free_alloc_pool (ref_table_alloc_pool);
 492       ref_table_alloc_pool = NULL;
 493     }
 494 }
 495
 496
 497 /* Get the reference table.  Initialize it if needed.  */
 498
 499 static inline struct reference_matches *
 500 reference_table (bool build)
 501 {
 502   if (ref_table || !build)
 503     return ref_table;
 504
 505   ref_table = build_reference_table ();
 506   find_references_in_function ();
 507   return ref_table;
 508 }
 509
 510
 511 /* Callback for find_references_in_function.
 512    Check whether *TP is an object reference or pointer dereference for the
 513    variables given in ((struct match_info*)DATA)->OBJS or
 514    ((struct match_info*)DATA)->PTRS.  The total number of references
 515    is stored in the same structures.  */
 516
 517 static tree
 518 find_references_in_tree_helper (tree *tp,
 519                                 int *walk_subtrees ATTRIBUTE_UNUSED,
 520                                 void *data)
 521 {
 522   struct tree_map match;
 523   static int parent_tree_code = ERROR_MARK;
 524
 525   /* Do not report references just for the purpose of taking an address.
 526      XXX: we rely on the fact that the tree walk is in preorder
 527      and that ADDR_EXPR is not a leaf, thus cannot be carried over across
 528      walks.  */
 529   if (parent_tree_code == ADDR_EXPR)
 530     goto finish;
 531
 532   match.to = (tree) data;
 533
 534   if (TREE_CODE (*tp) == INDIRECT_REF)
 535     {
 536       match.base.from = TREE_OPERAND (*tp, 0);
 537       maybe_add_match (reference_table (true)->ptrs, &match);
 538     }
 539   else
 540     {
 541       match.base.from = *tp;
 542       maybe_add_match (reference_table (true)->objs, &match);
 543     }
 544
 545 finish:
 546   parent_tree_code = TREE_CODE (*tp);
 547   return NULL_TREE;
 548 }
 549
 550
 551 /* Find all the references to aliased variables in the current function.  */
 552
 553 static void
 554 find_references_in_function (void)
 555 {
 556   basic_block bb;
 557   block_stmt_iterator i;
 558
 559   FOR_EACH_BB (bb)
 560     for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 561       walk_tree (bsi_stmt_ptr (i), find_references_in_tree_helper,
 562                  (void *) *bsi_stmt_ptr (i), NULL);
 563 }
 564
 565
 566 /* Find the reference site for OBJECT.
 567    If IS_PTR is true, look for dereferences of OBJECT instead.
 568    XXX: only the first site is returned in the current
 569    implementation.  If there are no matching sites, return NULL_TREE.  */
 570
 571 static tree
 572 reference_site (tree object, bool is_ptr)
 573 {
 574   if (is_ptr)
 575     return match (reference_table (true)->ptrs, object);
 576   else
 577     return match (reference_table (true)->objs, object);
 578 }
 579
 580
 581 /* Try to get more location info when something is missing.
 582    OBJECT1 and OBJECT2 are aliased names.  If IS_PTR1 or IS_PTR2, the alias
 583    is on the memory referenced or pointed to by OBJECT1 and OBJECT2.
 584    ALIAS_SITE, DEREF_SITE1 and DEREF_SITE2 are the statements where the
 585    alias takes place (some pointer assignment usually) and where the
 586    alias is referenced through OBJECT1 and OBJECT2 respectively.
 587    REF_TYPE1 and REF_TYPE2 will return the type of the reference at the
 588    respective sites.  Only the first matching reference is returned for
 589    each name.  If no statement is found, the function header is returned.  */
 590
 591 static void
 592 maybe_find_missing_stmts (tree object1, bool is_ptr1,
 593                           tree object2, bool is_ptr2,
 594                           tree *alias_site,
 595                           tree *deref_site1,
 596                           tree *deref_site2)
 597 {
 598   if (object1 && object2)
 599     {
 600       if (!*alias_site || !EXPR_HAS_LOCATION (*alias_site))
 601         *alias_site = find_alias_site (object1, is_ptr1, object2, is_ptr2);
 602
 603       if (!*deref_site1 || !EXPR_HAS_LOCATION (*deref_site1))
 604         *deref_site1 = reference_site (object1, is_ptr1);
 605
 606       if (!*deref_site2 || !EXPR_HAS_LOCATION (*deref_site2))
 607         *deref_site2 = reference_site (object2, is_ptr2);
 608     }
 609
 610   /* If we could not find the alias site, set it to one of the dereference
 611      sites, if available.  */
 612   if (!*alias_site)
 613     {
 614       if (*deref_site1)
 615         *alias_site = *deref_site1;
 616       else if (*deref_site2)
 617         *alias_site = *deref_site2;
 618     }
 619
 620   /* If we could not find the dereference sites, set them to the alias site,
 621      if known.  */
 622   if (!*deref_site1 && *alias_site)
 623     *deref_site1 = *alias_site;
 624   if (!*deref_site2 && *alias_site)
 625     *deref_site2 = *alias_site;
 626 }
 627
 628
 629 /* Callback for find_first_artificial_name.
 630    Find out if there are no artificial names at tree node *T.  */
 631
 632 static tree
 633 ffan_walker (tree *t,
 634              int *go_below ATTRIBUTE_UNUSED,
 635              void *data ATTRIBUTE_UNUSED)
 636 {
 637   if (DECL_P (*t) && !MTAG_P (*t) && DECL_ARTIFICIAL (*t))
 638     return *t;
 639   else
 640     return NULL_TREE;
 641 }
 642
 643 /* Return the first artificial name within EXPR, or NULL_TREE if
 644    none exists.  */
 645
 646 static tree
 647 find_first_artificial_name (tree expr)
 648 {
 649   return walk_tree_without_duplicates (&expr, ffan_walker, NULL);
 650 }
 651
 652
 653 /* Get a name from the original program for VAR.  */
 654
 655 static const char *
 656 get_var_name (tree var)
 657 {
 658   if (TREE_CODE (var) == SSA_NAME)
 659     return get_var_name (get_ssa_base (var));
 660
 661   if (find_first_artificial_name (var))
 662     return "{unknown}";
 663
 664   if (TREE_CODE (var) == VAR_DECL || TREE_CODE (var) == PARM_DECL)
 665     if (DECL_NAME (var))
 666       return IDENTIFIER_POINTER (DECL_NAME (var));
 667
 668   return "{unknown}";
 669 }
 670
 671
 672 /* Return "*" if OBJECT is not the actual alias but a pointer to it, or
 673    "" otherwise.
 674    IS_PTR is true when OBJECT is not the actual alias.
 675    In addition to checking IS_PTR, we also make sure that OBJECT is a pointer
 676    since IS_PTR would also be true for C++ references, but we should only
 677    print a * before a pointer and not before a reference.  */
 678
 679 static const char *
 680 get_maybe_star_prefix (tree object, bool is_ptr)
 681 {
 682   gcc_assert (object);
 683   return (is_ptr
 684           && TREE_CODE (TREE_TYPE (object)) == POINTER_TYPE) ? "*" : "";
 685 }
 686
 687
 688 /* Callback for contains_node_type_p.
 689    Returns true if *T has tree code *(int*)DATA.  */
 690
 691 static tree
 692 contains_node_type_p_callback (tree *t,
 693                                int *go_below ATTRIBUTE_UNUSED,
 694                                void *data)
 695 {
 696   return ((int) TREE_CODE (*t) == *((int *) data)) ? *t : NULL_TREE;
 697 }
 698
 699
 700 /* Return true if T contains a node with tree code TYPE.  */
 701
 702 static bool
 703 contains_node_type_p (tree t, int type)
 704 {
 705   return (walk_tree_without_duplicates (&t, contains_node_type_p_callback,
 706                                         (void *) &type)
 707           != NULL_TREE);
 708 }
 709
 710
 711 /* Return true if a warning was issued in the front end at STMT.  */
 712
 713 static bool
 714 already_warned_in_frontend_p (tree stmt)
 715 {
 716   tree rhs_pointer;
 717
 718   if (stmt == NULL_TREE)
 719     return false;
 720
 721   rhs_pointer = get_rhs (stmt);
 722
 723   if ((TREE_CODE (rhs_pointer) == NOP_EXPR
 724        || TREE_CODE (rhs_pointer) == CONVERT_EXPR
 725        || TREE_CODE (rhs_pointer) == VIEW_CONVERT_EXPR)
 726       && TREE_NO_WARNING (rhs_pointer))
 727     return true;
 728   else
 729     return false;
 730 }
 731
 732
 733 /* Return true if and only if TYPE is a function or method pointer type,
 734    or pointer to a pointer to ... to a function or method.  */
 735
 736 static bool
 737 is_method_pointer (tree type)
 738 {
 739   while (TREE_CODE (type) == POINTER_TYPE)
 740     type = TREE_TYPE (type);
 741   return TREE_CODE (type) == METHOD_TYPE || TREE_CODE (type) == FUNCTION_TYPE;
 742 }
 743
 744
 745 /* Issue a -Wstrict-aliasing warning.
 746    OBJECT1 and OBJECT2 are aliased names.
 747    If IS_PTR1 and/or IS_PTR2 is true, then the corresponding name
 748    OBJECT1/OBJECT2 is a pointer or reference to the aliased memory,
 749    rather than actual storage.
 750    ALIAS_SITE is a statement where the alias took place.  In the most common
 751    case, that is where a pointer was assigned to the address of an object.  */
 752
 753 static bool
 754 strict_aliasing_warn (tree alias_site,
 755                       tree object1, bool is_ptr1,
 756                       tree object2, bool is_ptr2,
 757                       bool filter_artificials)
 758 {
 759   tree ref_site1 = NULL_TREE;
 760   tree ref_site2 = NULL_TREE;
 761   const char *name1;
 762   const char *name2;
 763   location_t alias_loc;
 764   location_t ref1_loc;
 765   location_t ref2_loc;
 766   gcc_assert (object1);
 767   gcc_assert (object2);
 768   name1 = get_var_name (object1);
 769   name2 = get_var_name (object2);
 770
 771
 772   if (is_method_pointer (get_main_type (TREE_TYPE (object2))))
 773     return false;
 774
 775   maybe_find_missing_stmts (object1, is_ptr1, object2, is_ptr2, &alias_site,
 776                             &ref_site1, &ref_site2);
 777
 778   if (EXPR_HAS_LOCATION (alias_site))
 779     alias_loc = EXPR_LOCATION (alias_site);
 780   else
 781     return false;
 782
 783   if (EXPR_HAS_LOCATION (ref_site1))
 784     ref1_loc = EXPR_LOCATION (ref_site1);
 785   else
 786     ref1_loc = alias_loc;
 787
 788   if (EXPR_HAS_LOCATION (ref_site2))
 789     ref2_loc = EXPR_LOCATION (ref_site2);
 790   else
 791     ref2_loc = alias_loc;
 792
 793   if (already_warned_in_frontend_p (alias_site))
 794     return false;
 795
 796   /* If they are not SSA names, but contain SSA names, drop the warning
 797      because it cannot be displayed well.
 798      Also drop it if they both contain artificials.
 799      XXX: this is a hack, must figure out a better way to display them.  */
 800   if (filter_artificials)
 801     if ((find_first_artificial_name (get_ssa_base (object1))
 802          && find_first_artificial_name (get_ssa_base (object2)))
 803         || (TREE_CODE (object1) != SSA_NAME
 804             && contains_node_type_p (object1, SSA_NAME))
 805         || (TREE_CODE (object2) != SSA_NAME
 806             && contains_node_type_p (object2, SSA_NAME)))
 807       return false;
 808
 809
 810   /* XXX: In the following format string, %s:%d should be replaced by %H.
 811      However, in my tests only the first %H printed ok, while the
 812      second and third were printed as blanks.  */
 813   warning (OPT_Wstrict_aliasing,
 814            "%Hlikely type-punning may break strict-aliasing rules: "
 815            "object %<%s%s%> of main type %qT is referenced at or around "
 816            "%s:%d and may be "
 817            "aliased to object %<%s%s%> of main type %qT which is referenced "
 818            "at or around %s:%d.",
 819            &alias_loc,
 820            get_maybe_star_prefix (object1, is_ptr1),
 821            name1, get_otype (object1, is_ptr1),
 822            LOCATION_FILE (ref1_loc), LOCATION_LINE (ref1_loc),
 823            get_maybe_star_prefix (object2, is_ptr2),
 824            name2, get_otype (object2, is_ptr2),
 825            LOCATION_FILE (ref2_loc), LOCATION_LINE (ref2_loc));
 826
 827   return true;
 828 }
 829 \f
 830
 831
 832 /* Return true when any objects of TYPE1 and TYPE2 respectively
 833    may not be aliased according to the language standard.  */
 834
 835 static bool
 836 nonstandard_alias_types_p (tree type1, tree type2)
 837 {
 838   alias_set_type set1;
 839   alias_set_type set2;
 840
 841   if (VOID_TYPE_P (type1) || VOID_TYPE_P (type2))
 842     return false;
 843
 844   set1 = get_alias_set (type1);
 845   set2 = get_alias_set (type2);
 846   return !alias_sets_conflict_p (set1, set2);
 847 }
 848 \f
 849
 850
 851 /* Returns true when *PTR may not be aliased to ALIAS.
 852    See C standard 6.5p7 and C++ standard 3.10p15.
 853    If PTR_PTR is true, ALIAS represents a pointer or reference to the
 854    aliased storage rather than its actual name.  */
 855
 856 static bool
 857 nonstandard_alias_p (tree ptr, tree alias, bool ptr_ptr)
 858 {
 859   /* Find the types to compare.  */
 860   tree ptr_type = get_otype (ptr, true);
 861   tree alias_type = get_otype (alias, ptr_ptr);
 862
 863   /* XXX: for now, say it's OK if the alias escapes.
 864      Not sure this is needed in general, but otherwise GCC will not
 865      bootstrap.  */
 866   if (var_ann (get_ssa_base (alias))->escape_mask != NO_ESCAPE)
 867     return false;
 868
 869   /* XXX: don't get into structures for now.  It brings much complication
 870      and little benefit.  */
 871   if (struct_class_union_p (ptr_type) || struct_class_union_p (alias_type))
 872     return false;
 873
 874   /* If they are both SSA names of artificials, let it go, the warning
 875      is too confusing.  */
 876   if (find_first_artificial_name (ptr) && find_first_artificial_name (alias))
 877     return false;
 878
 879   /* Compare the types.  */
 880   return nonstandard_alias_types_p (ptr_type, alias_type);
 881 }
 882
 883
 884 /* Return true when we should skip analysis for pointer PTR based on the
 885    fact that their alias information *PI is not considered relevant.  */
 886
 887 static bool
 888 skip_this_pointer (tree ptr ATTRIBUTE_UNUSED, struct ptr_info_def *pi)
 889 {
 890   /* If it is not dereferenced, it is not a problem (locally).  */
 891   if (!pi->is_dereferenced)
 892     return true;
 893
 894   /* This would probably cause too many false positives.  */
 895   if (pi->value_escapes_p || pi->pt_anything)
 896     return true;
 897
 898   return false;
 899 }
 900
 901
 902 /* Find aliasing to named objects for pointer PTR.  */
 903
 904 static void
 905 dsa_named_for (tree ptr)
 906 {
 907   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 908
 909   if (pi)
 910     {
 911       if (skip_this_pointer (ptr, pi))
 912         return;
 913
 914       /* For all the variables it could be aliased to.  */
 915       if (pi->pt_vars)
 916         {
 917           unsigned ix;
 918           bitmap_iterator bi;
 919
 920           EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi)
 921             {
 922               tree alias = referenced_var (ix);
 923
 924               if (nonstandard_alias_p (ptr, alias, false))
 925                 strict_aliasing_warn (SSA_NAME_DEF_STMT (ptr),
 926                                       ptr, true, alias, false, true);
 927             }
 928         }
 929     }
 930 }
 931
 932
 933 /* Detect and report strict aliasing violation of named objects.  */
 934
 935 static void
 936 detect_strict_aliasing_named (void)
 937 {
 938   unsigned int i;
 939
 940   for (i = 1; i < num_ssa_names; i++)
 941     {
 942       tree ptr = ssa_name (i);
 943       struct ptr_info_def *pi;
 944
 945       if (ptr == NULL_TREE)
 946         continue;
 947
 948       pi = SSA_NAME_PTR_INFO (ptr);
 949
 950       if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag)
 951         dsa_named_for (ptr);
 952     }
 953 }
 954
 955
 956 /* Return false only the first time I see each instance of FUNC.  */
 957
 958 static bool
 959 processed_func_p (tree func)
 960 {
 961   static htab_t seen = NULL;
 962   void **slot = NULL;
 963
 964   if (!seen)
 965     seen = htab_create (10, tree_map_base_hash, tree_map_eq, NULL);
 966
 967   slot = htab_find_slot (seen, &func, INSERT);
 968   gcc_assert (slot);
 969
 970   if (*slot)
 971     return true;
 972
 973   gcc_assert (slot);
 974   *slot = &func;
 975   return false;
 976 }
 977
 978
 979 /* Detect and warn about type-punning using points-to information.  */
 980
 981 void
 982 strict_aliasing_warning_backend (void)
 983 {
 984   if (flag_strict_aliasing && warn_strict_aliasing == 3
 985       && !processed_func_p (current_function_decl))
 986     {
 987       detect_strict_aliasing_named ();
 988       maybe_free_reference_table ();
 989     }
 990 }