1258501Spfg/* Strict aliasing checks. 2258501Spfg Copyright (C) 2007 Free Software Foundation, Inc. 3258501Spfg Contributed by Silvius Rus <rus@google.com>. 4258501Spfg 5258501Spfg This file is part of GCC. 6258501Spfg 7258501Spfg GCC is free software; you can redistribute it and/or modify 8258501Spfg it under the terms of the GNU General Public License as published by 9258501Spfg the Free Software Foundation; either version 2, or (at your option) 10258501Spfg any later version. 11258501Spfg 12258501Spfg GCC is distributed in the hope that it will be useful, 13258501Spfg but WITHOUT ANY WARRANTY; without even the implied warranty of 14258501Spfg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15258501Spfg GNU General Public License for more details. 16258501Spfg 17258501Spfg You should have received a copy of the GNU General Public License 18258501Spfg along with GCC; see the file COPYING. If not, write to 19258501Spfg the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20258501Spfg Boston, MA 02110-1301, USA. */ 21258501Spfg 22258501Spfg#include "config.h" 23258501Spfg#include "system.h" 24258501Spfg#include "coretypes.h" 25258501Spfg#include "tm.h" 26258501Spfg#include "alloc-pool.h" 27258501Spfg#include "tree.h" 28258501Spfg#include "tree-dump.h" 29258501Spfg#include "tree-flow.h" 30258501Spfg#include "params.h" 31258501Spfg#include "function.h" 32258501Spfg#include "expr.h" 33258501Spfg#include "toplev.h" 34258501Spfg#include "diagnostic.h" 35258501Spfg#include "tree-ssa-structalias.h" 36258501Spfg#include "tree-ssa-propagate.h" 37258501Spfg#include "langhooks.h" 38258501Spfg 39258501Spfg/* Module to issue a warning when a program uses data through a type 40258501Spfg different from the type through which the data were defined. 41258501Spfg Implements -Wstrict-aliasing and -Wstrict-aliasing=n. 42258501Spfg These checks only happen when -fstrict-aliasing is present. 43258501Spfg 44258501Spfg The idea is to use the compiler to identify occurrences of nonstandard 45258501Spfg aliasing, and report them to programmers. Programs free of such aliasing 46258501Spfg are more portable, maintainable, and can usually be optimized better. 47258501Spfg 48258501Spfg The current, as of April 2007, C and C++ language standards forbid 49258501Spfg accessing data of type A through an lvalue of another type B, 50258501Spfg with certain exceptions. See the C Standard ISO/IEC 9899:1999, 51258501Spfg section 6.5, paragraph 7, and the C++ Standard ISO/IEC 14882:1998, 52258501Spfg section 3.10, paragraph 15. 53258501Spfg 54258501Spfg Example 1:*a is used as int but was defined as a float, *b. 55258501Spfg int* a = ...; 56258501Spfg float* b = reinterpret_cast<float*> (a); 57258501Spfg *b = 2.0; 58258501Spfg return *a 59258501Spfg 60258501Spfg Unfortunately, the problem is in general undecidable if we take into 61258501Spfg account arithmetic expressions such as array indices or pointer arithmetic. 62258501Spfg (It is at least as hard as Peano arithmetic decidability.) 63258501Spfg Even ignoring arithmetic, the problem is still NP-hard, because it is 64258501Spfg at least as hard as flow-insensitive may-alias analysis, which was proved 65258501Spfg NP-hard by Horwitz et al, TOPLAS 1997. 66258501Spfg 67258501Spfg It is clear that we need to choose some heuristics. 68258501Spfg Unfortunately, various users have different goals which correspond to 69258501Spfg different time budgets so a common approach will not suit all. 70258501Spfg We present the user with three effort/accuracy levels. By accuracy, we mean 71258501Spfg a common-sense mix of low count of false positives with a 72258501Spfg reasonably low number of false negatives. We are heavily biased 73258501Spfg towards a low count of false positives. 74258501Spfg The effort (compilation time) is likely to increase with the level. 75258501Spfg 76258501Spfg -Wstrict-aliasing=1 77258501Spfg =================== 78258501Spfg Most aggressive, least accurate. Possibly useful when higher levels 79258501Spfg do not warn but -fstrict-aliasing still breaks the code, as 80258501Spfg it has very few false negatives. 81258501Spfg Warn for all bad pointer conversions, even if never dereferenced. 82258501Spfg Implemented in the front end (c-common.c). 83258501Spfg Uses alias_sets_might_conflict to compare types. 84258501Spfg 85258501Spfg -Wstrict-aliasing=2 86258501Spfg =================== 87258501Spfg Aggressive, not too precise. 88258501Spfg May still have many false positives (not as many as level 1 though), 89258501Spfg and few false negatives (but possibly more than level 1). 90258501Spfg Runs only in the front end. Uses alias_sets_might_conflict to 91258501Spfg compare types. Does not check for pointer dereferences. 92258501Spfg Only warns when an address is taken. Warns about incomplete type punning. 93258501Spfg 94258501Spfg -Wstrict-aliasing=3 (default) 95258501Spfg =================== 96258501Spfg Should have very few false positives and few false negatives. 97258501Spfg Takes care of the common punn+dereference pattern in the front end: 98258501Spfg *(int*)&some_float. 99258501Spfg Takes care of multiple statement cases in the back end, 100258501Spfg using flow-sensitive points-to information (-O required). 101258501Spfg Uses alias_sets_conflict_p to compare types and only warns 102258501Spfg when the converted pointer is dereferenced. 103258501Spfg Does not warn about incomplete type punning. 104258501Spfg 105258501Spfg Future improvements can be included by adding higher levels. 106258501Spfg 107258501Spfg In summary, expression level analysis is performed in the front-end, 108258501Spfg and multiple-statement analysis is performed in the backend. 109258501Spfg The remainder of this discussion is only about the backend analysis. 110258501Spfg 111258501Spfg This implementation uses flow-sensitive points-to information. 112258501Spfg Flow-sensitivity refers to accesses to the pointer, and not the object 113258501Spfg pointed. For instance, we do not warn about the following case. 114258501Spfg 115258501Spfg Example 2. 116258501Spfg int* a = (int*)malloc (...); 117258501Spfg float* b = reinterpret_cast<float*> (a); 118258501Spfg *b = 2.0; 119258501Spfg a = (int*)malloc (...); 120258501Spfg return *a; 121258501Spfg 122258501Spfg In SSA, it becomes clear that the INT value *A_2 referenced in the 123258501Spfg return statement is not aliased to the FLOAT defined through *B_1. 124258501Spfg int* a_1 = (int*)malloc (...); 125258501Spfg float* b_1 = reinterpret_cast<float*> (a_1); 126258501Spfg *b_1 = 2.0; 127258501Spfg a_2 = (int*)malloc (...); 128258501Spfg return *a_2; 129258501Spfg 130258501Spfg 131258501Spfg Algorithm Outline 132258501Spfg ================= 133258501Spfg 134258501Spfg ForEach (ptr, object) in the points-to table 135258501Spfg If (incompatible_types (*ptr, object)) 136258501Spfg If (referenced (ptr, current function) 137258501Spfg and referenced (object, current function)) 138258501Spfg Issue warning (ptr, object, reference locations) 139258501Spfg 140258501Spfg The complexity is: 141258501Spfg O (sizeof (points-to table) 142258501Spfg + sizeof (function body) * lookup_time (points-to table)) 143258501Spfg 144258501Spfg Pointer dereference locations are looked up on demand. The search is 145258501Spfg a single scan of the function body, in which all references to pointers 146258501Spfg and objects in the points-to table are recorded. However, this dominant 147258501Spfg time factor occurs rarely, only when cross-type aliasing was detected. 148258501Spfg 149258501Spfg 150258501Spfg Limitations of the Proposed Implementation 151258501Spfg ========================================== 152258501Spfg 153258501Spfg 1. We do not catch the following case, because -fstrict-aliasing will 154258501Spfg associate different tags with MEM while building points-to information, 155258501Spfg thus before we get to analyze it. 156258501Spfg XXX: this could be solved by either running with -fno-strict-aliasing 157258501Spfg or by recording the points-to information before splitting the orignal 158258501Spfg tag based on type. 159258501Spfg 160258501Spfg Example 3. 161258501Spfg void* mem = malloc (...); 162258501Spfg int* pi = reinterpret_cast<int*> (mem); 163258501Spfg float* b = reinterpret_cast<float*> (mem); 164258501Spfg *b = 2.0; 165258501Spfg return *pi+1; 166258501Spfg 167258501Spfg 2. We do not check whether the two conflicting (de)references can 168258501Spfg reach each other in the control flow sense. If we fixed limitation 169258501Spfg 1, we would wrongly issue a warning in the following case. 170258501Spfg 171258501Spfg Example 4. 172258501Spfg void* raw = malloc (...); 173258501Spfg if (...) { 174258501Spfg float* b = reinterpret_cast<float*> (raw); 175258501Spfg *b = 2.0; 176258501Spfg return (int)*b; 177258501Spfg } else { 178258501Spfg int* a = reinterpret_cast<int*> (raw); 179258501Spfg *a = 1; 180258501Spfg return *a; 181258501Spfg 182258501Spfg 3. Only simple types are compared, thus no structures, unions or classes 183258501Spfg are analyzed. A first attempt to deal with structures introduced much 184258501Spfg complication and has not showed much improvement in preliminary tests, 185258501Spfg so it was left out. 186258501Spfg 187258501Spfg 4. All analysis is intraprocedural. */ 188258501Spfg 189258501Spfg 190258501Spfg/* Local declarations. */ 191258501Spfgstatic void find_references_in_function (void); 192258501Spfg 193258501Spfg 194258501Spfg 195258501Spfg/* Get main type of tree TYPE, stripping array dimensions and qualifiers. */ 196258501Spfg 197258501Spfgstatic tree 198258501Spfgget_main_type (tree type) 199258501Spfg{ 200258501Spfg while (TREE_CODE (type) == ARRAY_TYPE) 201258501Spfg type = TREE_TYPE (type); 202258501Spfg return TYPE_MAIN_VARIANT (type); 203258501Spfg} 204258501Spfg 205258501Spfg 206258501Spfg/* Get the type of the given object. If IS_PTR is true, get the type of the 207258501Spfg object pointed to or referenced by OBJECT instead. 208258501Spfg For arrays, return the element type. Ignore all qualifiers. */ 209258501Spfg 210258501Spfgstatic tree 211258501Spfgget_otype (tree object, bool is_ptr) 212258501Spfg{ 213258501Spfg tree otype = TREE_TYPE (object); 214258501Spfg 215258501Spfg if (is_ptr) 216258501Spfg { 217258501Spfg gcc_assert (POINTER_TYPE_P (otype)); 218258501Spfg otype = TREE_TYPE (otype); 219258501Spfg } 220258501Spfg return get_main_type (otype); 221258501Spfg} 222258501Spfg 223258501Spfg 224258501Spfg/* Return true if tree TYPE is struct, class or union. */ 225258501Spfg 226258501Spfgstatic bool 227258501Spfgstruct_class_union_p (tree type) 228258501Spfg{ 229258501Spfg return (TREE_CODE (type) == RECORD_TYPE 230258501Spfg || TREE_CODE (type) == UNION_TYPE 231258501Spfg || TREE_CODE (type) == QUAL_UNION_TYPE); 232258501Spfg} 233258501Spfg 234258501Spfg 235258501Spfg 236258501Spfg/* Keep data during a search for an aliasing site. 237258501Spfg RHS = object or pointer aliased. No LHS is specified because we are only 238258501Spfg looking in the UseDef paths of a given variable, so LHS will always be 239258501Spfg an SSA name of the same variable. 240258501Spfg When IS_RHS_POINTER = true, we are looking for ... = RHS. Otherwise, 241258501Spfg we are looking for ... = &RHS. 242258501Spfg SITE is the output of a search, non-NULL if the search succeeded. */ 243258501Spfg 244258501Spfgstruct alias_match 245258501Spfg{ 246258501Spfg tree rhs; 247258501Spfg bool is_rhs_pointer; 248258501Spfg tree site; 249258501Spfg}; 250258501Spfg 251258501Spfg 252258501Spfg/* Callback for find_alias_site. Return true if the right hand site 253258501Spfg of STMT matches DATA. */ 254258501Spfg 255258501Spfgstatic bool 256258501Spfgfind_alias_site_helper (tree var ATTRIBUTE_UNUSED, tree stmt, void *data) 257258501Spfg{ 258258501Spfg struct alias_match *match = (struct alias_match *) data; 259258501Spfg tree rhs_pointer = get_rhs (stmt); 260258501Spfg tree to_match = NULL_TREE; 261258501Spfg 262258501Spfg while (TREE_CODE (rhs_pointer) == NOP_EXPR 263258501Spfg || TREE_CODE (rhs_pointer) == CONVERT_EXPR 264258501Spfg || TREE_CODE (rhs_pointer) == VIEW_CONVERT_EXPR) 265258501Spfg rhs_pointer = TREE_OPERAND (rhs_pointer, 0); 266258501Spfg 267258501Spfg if (!rhs_pointer) 268258501Spfg /* Not a type conversion. */ 269258501Spfg return false; 270258501Spfg 271258501Spfg if (TREE_CODE (rhs_pointer) == ADDR_EXPR && !match->is_rhs_pointer) 272258501Spfg to_match = TREE_OPERAND (rhs_pointer, 0); 273258501Spfg else if (POINTER_TYPE_P (rhs_pointer) && match->is_rhs_pointer) 274258501Spfg to_match = rhs_pointer; 275258501Spfg 276258501Spfg if (to_match != match->rhs) 277258501Spfg /* Type conversion, but not a name match. */ 278258501Spfg return false; 279258501Spfg 280258501Spfg /* Found it. */ 281258501Spfg match->site = stmt; 282258501Spfg return true; 283258501Spfg} 284258501Spfg 285258501Spfg 286258501Spfg/* Find the statement where OBJECT1 gets aliased to OBJECT2. 287258501Spfg If IS_PTR2 is true, consider OBJECT2 to be the name of a pointer or 288258501Spfg reference rather than the actual aliased object. 289258501Spfg For now, just implement the case where OBJECT1 is an SSA name defined 290258501Spfg by a PHI statement. */ 291258501Spfg 292258501Spfgstatic tree 293258501Spfgfind_alias_site (tree object1, bool is_ptr1 ATTRIBUTE_UNUSED, 294258501Spfg tree object2, bool is_ptr2) 295258501Spfg{ 296258501Spfg struct alias_match match; 297258501Spfg 298258501Spfg match.rhs = object2; 299258501Spfg match.is_rhs_pointer = is_ptr2; 300258501Spfg match.site = NULL_TREE; 301258501Spfg 302258501Spfg if (TREE_CODE (object1) != SSA_NAME) 303258501Spfg return NULL_TREE; 304258501Spfg 305258501Spfg walk_use_def_chains (object1, find_alias_site_helper, &match, false); 306258501Spfg return match.site; 307258501Spfg} 308258501Spfg 309258501Spfg 310258501Spfg/* Structure to store temporary results when trying to figure out whether 311258501Spfg an object is referenced. Just its presence in the text is not enough, 312258501Spfg as we may just be taking its address. */ 313258501Spfg 314258501Spfgstruct match_info 315258501Spfg{ 316258501Spfg tree object; 317258501Spfg bool is_ptr; 318258501Spfg /* The difference between the number of references to OBJECT 319258501Spfg and the number of occurences of &OBJECT. */ 320258501Spfg int found; 321258501Spfg}; 322258501Spfg 323258501Spfg 324258501Spfg/* Return the base if EXPR is an SSA name. Return EXPR otherwise. */ 325258501Spfg 326258501Spfgstatic tree 327258501Spfgget_ssa_base (tree expr) 328258501Spfg{ 329258501Spfg if (TREE_CODE (expr) == SSA_NAME) 330258501Spfg return SSA_NAME_VAR (expr); 331258501Spfg else 332258501Spfg return expr; 333258501Spfg} 334258501Spfg 335258501Spfg 336258501Spfg/* Record references to objects and pointer dereferences across some piece of 337258501Spfg code. The number of references is recorded for each item. 338258501Spfg References to an object just to take its address are not counted. 339258501Spfg For instance, if PTR is a pointer and OBJ is an object: 340258501Spfg 1. Expression &obj + *ptr will have the following reference match structure: 341258501Spfg ptrs: <ptr, 1> 342258501Spfg objs: <ptr, 1> 343258501Spfg OBJ does not appear as referenced because we just take its address. 344258501Spfg 2. Expression ptr + *ptr will have the following reference match structure: 345258501Spfg ptrs: <ptr, 1> 346258501Spfg objs: <ptr, 2> 347258501Spfg PTR shows up twice as an object, but is dereferenced only once. 348258501Spfg 349258501Spfg The elements of the hash tables are tree_map objects. */ 350258501Spfgstruct reference_matches 351258501Spfg{ 352258501Spfg htab_t ptrs; 353258501Spfg htab_t objs; 354258501Spfg}; 355258501Spfg 356258501Spfg 357258501Spfg/* Return the match, if any. Otherwise, return NULL_TREE. It will 358258501Spfg return NULL_TREE even when a match was found, if the value associated 359258501Spfg to KEY is NULL_TREE. */ 360258501Spfg 361258501Spfgstatic inline tree 362258501Spfgmatch (htab_t ref_map, tree key) 363258501Spfg{ 364258501Spfg struct tree_map to_find; 365258501Spfg struct tree_map *found; 366258501Spfg void **slot = NULL; 367258501Spfg 368258501Spfg to_find.from = key; 369258501Spfg to_find.hash = htab_hash_pointer (key); 370258501Spfg slot = htab_find_slot (ref_map, &to_find, NO_INSERT); 371258501Spfg 372258501Spfg if (!slot) 373258501Spfg return NULL_TREE; 374258501Spfg 375258501Spfg found = (struct tree_map *) *slot; 376258501Spfg return found->to; 377258501Spfg} 378258501Spfg 379258501Spfg 380258501Spfg/* Set the entry corresponding to KEY, but only if the entry 381258501Spfg already exists and its value is NULL_TREE. Otherwise, do nothing. */ 382258501Spfg 383258501Spfgstatic inline void 384258501Spfgmaybe_add_match (htab_t ref_map, struct tree_map *key) 385258501Spfg{ 386258501Spfg struct tree_map *found = htab_find (ref_map, key); 387258501Spfg 388258501Spfg if (found && !found->to) 389258501Spfg found->to = key->to; 390258501Spfg} 391258501Spfg 392258501Spfg 393258501Spfg/* Add an entry to HT, with key T and value NULL_TREE. */ 394258501Spfg 395258501Spfgstatic void 396258501Spfgadd_key (htab_t ht, tree t, alloc_pool references_pool) 397258501Spfg{ 398258501Spfg void **slot; 399258501Spfg struct tree_map *tp = pool_alloc (references_pool); 400258501Spfg 401258501Spfg tp->from = t; 402258501Spfg tp->to = NULL_TREE; 403258501Spfg tp->hash = htab_hash_pointer(tp->from); 404258501Spfg 405258501Spfg slot = htab_find_slot (ht, tp, INSERT); 406258501Spfg *slot = (void *) tp; 407258501Spfg} 408258501Spfg 409258501Spfg 410258501Spfg/* Some memory to keep the objects in the reference table. */ 411258501Spfg 412258501Spfgstatic alloc_pool ref_table_alloc_pool = NULL; 413258501Spfg 414258501Spfg 415258501Spfg/* Get some memory to keep the objects in the reference table. */ 416258501Spfg 417258501Spfgstatic inline alloc_pool 418258501Spfgreference_table_alloc_pool (bool build) 419258501Spfg{ 420258501Spfg if (ref_table_alloc_pool || !build) 421258501Spfg return ref_table_alloc_pool; 422258501Spfg 423258501Spfg ref_table_alloc_pool = 424258501Spfg create_alloc_pool ("ref_table_alloc_pool", sizeof (struct tree_map), 20); 425258501Spfg 426258501Spfg return ref_table_alloc_pool; 427258501Spfg} 428258501Spfg 429258501Spfg 430258501Spfg/* Initialize the reference table by adding all pointers in the points-to 431258501Spfg table as keys, and NULL_TREE as associated values. */ 432258501Spfg 433258501Spfgstatic struct reference_matches * 434258501Spfgbuild_reference_table (void) 435258501Spfg{ 436258501Spfg unsigned int i; 437258501Spfg struct reference_matches *ref_table = NULL; 438258501Spfg alloc_pool references_pool = reference_table_alloc_pool (true); 439258501Spfg 440258501Spfg ref_table = XNEW (struct reference_matches); 441258501Spfg ref_table->objs = htab_create (10, tree_map_hash, tree_map_eq, NULL); 442258501Spfg ref_table->ptrs = htab_create (10, tree_map_hash, tree_map_eq, NULL); 443258501Spfg 444258501Spfg for (i = 1; i < num_ssa_names; i++) 445258501Spfg { 446258501Spfg tree ptr = ssa_name (i); 447258501Spfg struct ptr_info_def *pi; 448258501Spfg 449258501Spfg if (ptr == NULL_TREE) 450258501Spfg continue; 451258501Spfg 452258501Spfg pi = SSA_NAME_PTR_INFO (ptr); 453258501Spfg 454258501Spfg if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag) 455258501Spfg { 456258501Spfg /* Add pointer to the interesting dereference list. */ 457258501Spfg add_key (ref_table->ptrs, ptr, references_pool); 458258501Spfg 459258501Spfg /* Add all aliased names to the interesting reference list. */ 460258501Spfg if (pi->pt_vars) 461258501Spfg { 462258501Spfg unsigned ix; 463258501Spfg bitmap_iterator bi; 464258501Spfg 465258501Spfg EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) 466258501Spfg { 467258501Spfg tree alias = referenced_var (ix); 468258501Spfg add_key (ref_table->objs, alias, references_pool); 469258501Spfg } 470258501Spfg } 471258501Spfg } 472258501Spfg } 473258501Spfg 474258501Spfg return ref_table; 475258501Spfg} 476258501Spfg 477258501Spfg 478258501Spfg/* Reference table. */ 479258501Spfg 480258501Spfgstatic struct reference_matches *ref_table = NULL; 481258501Spfg 482258501Spfg 483258501Spfg/* Clean up the reference table if allocated. */ 484258501Spfg 485258501Spfgstatic void 486258501Spfgmaybe_free_reference_table (void) 487258501Spfg{ 488258501Spfg if (ref_table) 489258501Spfg { 490258501Spfg htab_delete (ref_table->ptrs); 491258501Spfg htab_delete (ref_table->objs); 492258501Spfg free (ref_table); 493258501Spfg ref_table = NULL; 494258501Spfg } 495258501Spfg 496258501Spfg if (ref_table_alloc_pool) 497258501Spfg { 498258501Spfg free_alloc_pool (ref_table_alloc_pool); 499258501Spfg ref_table_alloc_pool = NULL; 500258501Spfg } 501258501Spfg} 502258501Spfg 503258501Spfg 504258501Spfg/* Get the reference table. Initialize it if needed. */ 505258501Spfg 506258501Spfgstatic inline struct reference_matches * 507258501Spfgreference_table (bool build) 508258501Spfg{ 509258501Spfg if (ref_table || !build) 510258501Spfg return ref_table; 511258501Spfg 512258501Spfg ref_table = build_reference_table (); 513258501Spfg find_references_in_function (); 514258501Spfg return ref_table; 515258501Spfg} 516258501Spfg 517258501Spfg 518258501Spfg/* Callback for find_references_in_function. 519258501Spfg Check whether *TP is an object reference or pointer dereference for the 520258501Spfg variables given in ((struct match_info*)DATA)->OBJS or 521258501Spfg ((struct match_info*)DATA)->PTRS. The total number of references 522258501Spfg is stored in the same structures. */ 523258501Spfg 524258501Spfgstatic tree 525258501Spfgfind_references_in_tree_helper (tree *tp, 526258501Spfg int *walk_subtrees ATTRIBUTE_UNUSED, 527258501Spfg void *data) 528258501Spfg{ 529258501Spfg struct tree_map match; 530258501Spfg static int parent_tree_code = ERROR_MARK; 531258501Spfg 532258501Spfg /* Do not report references just for the purpose of taking an address. 533258501Spfg XXX: we rely on the fact that the tree walk is in preorder 534258501Spfg and that ADDR_EXPR is not a leaf, thus cannot be carried over across 535258501Spfg walks. */ 536258501Spfg if (parent_tree_code == ADDR_EXPR) 537258501Spfg goto finish; 538258501Spfg 539258501Spfg match.to = (tree) data; 540258501Spfg 541258501Spfg if (TREE_CODE (*tp) == INDIRECT_REF) 542258501Spfg { 543258501Spfg match.from = TREE_OPERAND (*tp, 0); 544258501Spfg match.hash = htab_hash_pointer (match.from); 545258501Spfg maybe_add_match (reference_table (true)->ptrs, &match); 546258501Spfg } 547258501Spfg else 548258501Spfg { 549258501Spfg match.from = *tp; 550258501Spfg match.hash = htab_hash_pointer (match.from); 551258501Spfg maybe_add_match (reference_table (true)->objs, &match); 552258501Spfg } 553258501Spfg 554258501Spfgfinish: 555258501Spfg parent_tree_code = TREE_CODE (*tp); 556258501Spfg return NULL_TREE; 557258501Spfg} 558258501Spfg 559258501Spfg 560258501Spfg/* Find all the references to aliased variables in the current function. */ 561258501Spfg 562258501Spfgstatic void 563258501Spfgfind_references_in_function (void) 564258501Spfg{ 565258501Spfg basic_block bb; 566258501Spfg block_stmt_iterator i; 567258501Spfg 568258501Spfg FOR_EACH_BB (bb) 569258501Spfg for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) 570258501Spfg walk_tree (bsi_stmt_ptr (i), find_references_in_tree_helper, 571258501Spfg (void *) *bsi_stmt_ptr (i), NULL); 572258501Spfg} 573258501Spfg 574258501Spfg 575258501Spfg/* Find the reference site for OBJECT. 576258501Spfg If IS_PTR is true, look for derferences of OBJECT instead. 577258501Spfg XXX: only the first site is returned in the current 578258501Spfg implementation. If there are no matching sites, return NULL_TREE. */ 579258501Spfg 580258501Spfgstatic tree 581258501Spfgreference_site (tree object, bool is_ptr) 582258501Spfg{ 583258501Spfg if (is_ptr) 584258501Spfg return match (reference_table (true)->ptrs, object); 585258501Spfg else 586258501Spfg return match (reference_table (true)->objs, object); 587258501Spfg} 588258501Spfg 589258501Spfg 590258501Spfg/* Try to get more location info when something is missing. 591258501Spfg OBJECT1 and OBJECT2 are aliased names. If IS_PTR1 or IS_PTR2, the alias 592258501Spfg is on the memory referenced or pointed to by OBJECT1 and OBJECT2. 593258501Spfg ALIAS_SITE, DEREF_SITE1 and DEREF_SITE2 are the statements where the 594258501Spfg alias takes place (some pointer assignment usually) and where the 595258501Spfg alias is referenced through OBJECT1 and OBJECT2 respectively. 596258501Spfg REF_TYPE1 and REF_TYPE2 will return the type of the reference at the 597258501Spfg respective sites. Only the first matching reference is returned for 598258501Spfg each name. If no statement is found, the function header is returned. */ 599258501Spfg 600258501Spfgstatic void 601258501Spfgmaybe_find_missing_stmts (tree object1, bool is_ptr1, 602258501Spfg tree object2, bool is_ptr2, 603258501Spfg tree *alias_site, 604258501Spfg tree *deref_site1, 605258501Spfg tree *deref_site2) 606258501Spfg{ 607258501Spfg if (object1 && object2) 608258501Spfg { 609258501Spfg if (!*alias_site || !EXPR_HAS_LOCATION (*alias_site)) 610258501Spfg *alias_site = find_alias_site (object1, is_ptr1, object2, is_ptr2); 611258501Spfg 612258501Spfg if (!*deref_site1 || !EXPR_HAS_LOCATION (*deref_site1)) 613258501Spfg *deref_site1 = reference_site (object1, is_ptr1); 614258501Spfg 615258501Spfg if (!*deref_site2 || !EXPR_HAS_LOCATION (*deref_site2)) 616258501Spfg *deref_site2 = reference_site (object2, is_ptr2); 617258501Spfg } 618258501Spfg 619258501Spfg /* If we could not find the alias site, set it to one of the dereference 620258501Spfg sites, if available. */ 621258501Spfg if (!*alias_site) 622258501Spfg { 623258501Spfg if (*deref_site1) 624258501Spfg *alias_site = *deref_site1; 625258501Spfg else if (*deref_site2) 626258501Spfg *alias_site = *deref_site2; 627258501Spfg } 628258501Spfg 629258501Spfg /* If we could not find the dereference sites, set them to the alias site, 630258501Spfg if known. */ 631258501Spfg if (!*deref_site1 && *alias_site) 632258501Spfg *deref_site1 = *alias_site; 633258501Spfg if (!*deref_site2 && *alias_site) 634258501Spfg *deref_site2 = *alias_site; 635258501Spfg} 636258501Spfg 637258501Spfg 638258501Spfg/* Callback for find_first_artificial_name. 639258501Spfg Find out if there are no artificial names at tree node *T. */ 640258501Spfg 641258501Spfgstatic tree 642258501Spfgffan_walker (tree *t, 643258501Spfg int *go_below ATTRIBUTE_UNUSED, 644258501Spfg void *data ATTRIBUTE_UNUSED) 645258501Spfg{ 646258501Spfg if (TREE_CODE (*t) == VAR_DECL || TREE_CODE (*t) == PARM_DECL) 647258501Spfg if (DECL_ARTIFICIAL (*t)) 648258501Spfg return *t; 649258501Spfg 650258501Spfg return NULL_TREE; 651258501Spfg} 652258501Spfg 653258501Spfg/* Return the first artificial name within EXPR, or NULL_TREE if 654258501Spfg none exists. */ 655258501Spfg 656258501Spfgstatic tree 657258501Spfgfind_first_artificial_name (tree expr) 658258501Spfg{ 659258501Spfg return walk_tree_without_duplicates (&expr, ffan_walker, NULL); 660258501Spfg} 661258501Spfg 662258501Spfg 663258501Spfg/* Get a name from the original program for VAR. */ 664258501Spfg 665258501Spfgstatic const char * 666258501Spfgget_var_name (tree var) 667258501Spfg{ 668258501Spfg if (TREE_CODE (var) == SSA_NAME) 669258501Spfg return get_var_name (get_ssa_base (var)); 670258501Spfg 671258501Spfg if (find_first_artificial_name (var)) 672258501Spfg return "{unknown}"; 673258501Spfg 674258501Spfg if (TREE_CODE (var) == VAR_DECL || TREE_CODE (var) == PARM_DECL) 675258501Spfg if (DECL_NAME (var)) 676258501Spfg return IDENTIFIER_POINTER (DECL_NAME (var)); 677258501Spfg 678258501Spfg return "{unknown}"; 679258501Spfg} 680258501Spfg 681258501Spfg 682258501Spfg/* Return true if VAR contains an artificial name. */ 683258501Spfg 684258501Spfgstatic bool 685258501Spfgcontains_artificial_name_p (tree var) 686258501Spfg{ 687258501Spfg if (TREE_CODE (var) == SSA_NAME) 688258501Spfg return contains_artificial_name_p (get_ssa_base (var)); 689258501Spfg 690258501Spfg return find_first_artificial_name (var) != NULL_TREE; 691258501Spfg} 692258501Spfg 693258501Spfg 694258501Spfg/* Return "*" if OBJECT is not the actual alias but a pointer to it, or 695258501Spfg "" otherwise. 696258501Spfg IS_PTR is true when OBJECT is not the actual alias. 697258501Spfg In addition to checking IS_PTR, we also make sure that OBJECT is a pointer 698258501Spfg since IS_PTR would also be true for C++ references, but we should only 699258501Spfg print a * before a pointer and not before a reference. */ 700258501Spfg 701258501Spfgstatic const char * 702258501Spfgget_maybe_star_prefix (tree object, bool is_ptr) 703258501Spfg{ 704258501Spfg gcc_assert (object); 705258501Spfg return (is_ptr 706258501Spfg && TREE_CODE (TREE_TYPE (object)) == POINTER_TYPE) ? "*" : ""; 707258501Spfg} 708258501Spfg 709258501Spfg 710258501Spfg/* Callback for contains_node_type_p. 711258501Spfg Returns true if *T has tree code *(int*)DATA. */ 712258501Spfg 713258501Spfgstatic tree 714258501Spfgcontains_node_type_p_callback (tree *t, 715258501Spfg int *go_below ATTRIBUTE_UNUSED, 716258501Spfg void *data) 717258501Spfg{ 718258501Spfg return ((int) TREE_CODE (*t) == *((int *) data)) ? *t : NULL_TREE; 719258501Spfg} 720258501Spfg 721258501Spfg 722258501Spfg/* Return true if T contains a node with tree code TYPE. */ 723258501Spfg 724258501Spfgstatic bool 725258501Spfgcontains_node_type_p (tree t, int type) 726258501Spfg{ 727258501Spfg return (walk_tree_without_duplicates (&t, contains_node_type_p_callback, 728258501Spfg (void *) &type) 729258501Spfg != NULL_TREE); 730258501Spfg} 731258501Spfg 732258501Spfg 733258501Spfg/* Return true if a warning was issued in the front end at STMT. */ 734258501Spfg 735258501Spfgstatic bool 736258501Spfgalready_warned_in_frontend_p (tree stmt) 737258501Spfg{ 738258501Spfg tree rhs_pointer; 739258501Spfg 740258501Spfg if (stmt == NULL_TREE) 741258501Spfg return false; 742258501Spfg 743258501Spfg rhs_pointer = get_rhs (stmt); 744258501Spfg 745258501Spfg if ((TREE_CODE (rhs_pointer) == NOP_EXPR 746258501Spfg || TREE_CODE (rhs_pointer) == CONVERT_EXPR 747258501Spfg || TREE_CODE (rhs_pointer) == VIEW_CONVERT_EXPR) 748258501Spfg && TREE_NO_WARNING (rhs_pointer)) 749258501Spfg return true; 750258501Spfg else 751258501Spfg return false; 752258501Spfg} 753258501Spfg 754258501Spfg 755258501Spfg/* Return true if and only if TYPE is a function or method pointer type, 756258501Spfg or pointer to a pointer to ... to a function or method. */ 757258501Spfg 758258501Spfgstatic bool 759258501Spfgis_method_pointer (tree type) 760258501Spfg{ 761258501Spfg while (TREE_CODE (type) == POINTER_TYPE) 762258501Spfg type = TREE_TYPE (type); 763258501Spfg return TREE_CODE (type) == METHOD_TYPE || TREE_CODE (type) == FUNCTION_TYPE; 764258501Spfg} 765258501Spfg 766258501Spfg 767258501Spfg/* Issue a -Wstrict-aliasing warning. 768258501Spfg OBJECT1 and OBJECT2 are aliased names. 769258501Spfg If IS_PTR1 and/or IS_PTR2 is true, then the corresponding name 770258501Spfg OBJECT1/OBJECT2 is a pointer or reference to the aliased memory, 771258501Spfg rather than actual storage. 772258501Spfg ALIAS_SITE is a statement where the alias took place. In the most common 773258501Spfg case, that is where a pointer was assigned to the address of an object. */ 774258501Spfg 775258501Spfgstatic bool 776258501Spfgstrict_aliasing_warn (tree alias_site, 777258501Spfg tree object1, bool is_ptr1, 778258501Spfg tree object2, bool is_ptr2, 779258501Spfg bool filter_artificials) 780258501Spfg{ 781258501Spfg tree ref_site1 = NULL_TREE; 782258501Spfg tree ref_site2 = NULL_TREE; 783258501Spfg const char *name1; 784258501Spfg const char *name2; 785258501Spfg location_t alias_loc; 786258501Spfg location_t ref1_loc; 787258501Spfg location_t ref2_loc; 788258501Spfg gcc_assert (object1); 789258501Spfg gcc_assert (object2); 790258501Spfg 791258501Spfg if (contains_artificial_name_p (object1) 792258501Spfg || contains_artificial_name_p (object2)) 793258501Spfg return false; 794258501Spfg 795258501Spfg name1 = get_var_name (object1); 796258501Spfg name2 = get_var_name (object2); 797258501Spfg 798258501Spfg if (is_method_pointer (get_main_type (TREE_TYPE (object2)))) 799258501Spfg return false; 800258501Spfg 801258501Spfg maybe_find_missing_stmts (object1, is_ptr1, object2, is_ptr2, &alias_site, 802258501Spfg &ref_site1, &ref_site2); 803258501Spfg 804258501Spfg if (!alias_site) 805258501Spfg return false; 806258501Spfg 807258501Spfg if (EXPR_HAS_LOCATION (alias_site)) 808258501Spfg alias_loc = EXPR_LOCATION (alias_site); 809258501Spfg else 810258501Spfg return false; 811258501Spfg 812258501Spfg if (EXPR_HAS_LOCATION (ref_site1)) 813258501Spfg ref1_loc = EXPR_LOCATION (ref_site1); 814258501Spfg else 815258501Spfg ref1_loc = alias_loc; 816258501Spfg 817258501Spfg if (EXPR_HAS_LOCATION (ref_site2)) 818258501Spfg ref2_loc = EXPR_LOCATION (ref_site2); 819258501Spfg else 820258501Spfg ref2_loc = alias_loc; 821258501Spfg 822258501Spfg if (already_warned_in_frontend_p (alias_site)) 823258501Spfg return false; 824258501Spfg 825258501Spfg /* If they are not SSA names, but contain SSA names, drop the warning 826258501Spfg because it cannot be displayed well. 827258501Spfg Also drop it if they both contain artificials. 828258501Spfg XXX: this is a hack, must figure out a better way to display them. */ 829258501Spfg if (filter_artificials) 830258501Spfg if ((find_first_artificial_name (get_ssa_base (object1)) 831258501Spfg && find_first_artificial_name (get_ssa_base (object2))) 832258501Spfg || (TREE_CODE (object1) != SSA_NAME 833258501Spfg && contains_node_type_p (object1, SSA_NAME)) 834258501Spfg || (TREE_CODE (object2) != SSA_NAME 835258501Spfg && contains_node_type_p (object2, SSA_NAME))) 836258501Spfg return false; 837258501Spfg 838258501Spfg /* XXX: In the following format string, %s:%d should be replaced by %H. 839258501Spfg However, in my tests only the first %H printed ok, while the 840258501Spfg second and third were printed as blanks. */ 841258501Spfg warning (OPT_Wstrict_aliasing, 842258501Spfg "%Hlikely type-punning may break strict-aliasing rules: " 843258501Spfg "object %<%s%s%> of main type %qT is referenced at or around " 844258501Spfg "%s:%d and may be " 845258501Spfg "aliased to object %<%s%s%> of main type %qT which is referenced " 846258501Spfg "at or around %s:%d.", 847258501Spfg &alias_loc, 848258501Spfg get_maybe_star_prefix (object1, is_ptr1), 849258501Spfg name1, get_otype (object1, is_ptr1), 850258501Spfg LOCATION_FILE (ref1_loc), LOCATION_LINE (ref1_loc), 851258501Spfg get_maybe_star_prefix (object2, is_ptr2), 852258501Spfg name2, get_otype (object2, is_ptr2), 853258501Spfg LOCATION_FILE (ref2_loc), LOCATION_LINE (ref2_loc)); 854258501Spfg 855258501Spfg return true; 856258501Spfg} 857258501Spfg 858258501Spfg 859258501Spfg 860258501Spfg/* Return true when any objects of TYPE1 and TYPE2 respectively 861258501Spfg may not be aliased according to the language standard. */ 862258501Spfg 863258501Spfgstatic bool 864258501Spfgnonstandard_alias_types_p (tree type1, tree type2) 865258501Spfg{ 866258501Spfg HOST_WIDE_INT set1; 867258501Spfg HOST_WIDE_INT set2; 868258501Spfg 869258501Spfg if (VOID_TYPE_P (type1) || VOID_TYPE_P (type2)) 870258501Spfg return false; 871258501Spfg 872258501Spfg set1 = get_alias_set (type1); 873258501Spfg set2 = get_alias_set (type2); 874258501Spfg return !alias_sets_conflict_p (set1, set2); 875258501Spfg} 876258501Spfg 877258501Spfg 878258501Spfg 879258501Spfg/* Returns true if the given name is a struct field tag (SFT). */ 880258501Spfg 881258501Spfgstatic bool 882258501Spfgstruct_field_tag_p (tree var) 883258501Spfg{ 884258501Spfg return TREE_CODE (var) == STRUCT_FIELD_TAG; 885258501Spfg} 886258501Spfg 887258501Spfg 888258501Spfg/* Returns true when *PTR may not be aliased to ALIAS. 889258501Spfg See C standard 6.5p7 and C++ standard 3.10p15. 890258501Spfg If PTR_PTR is true, ALIAS represents a pointer or reference to the 891258501Spfg aliased storage rather than its actual name. */ 892258501Spfg 893258501Spfgstatic bool 894258501Spfgnonstandard_alias_p (tree ptr, tree alias, bool ptr_ptr) 895258501Spfg{ 896258501Spfg /* Find the types to compare. */ 897258501Spfg tree ptr_type = get_otype (ptr, true); 898258501Spfg tree alias_type = get_otype (alias, ptr_ptr); 899258501Spfg 900258501Spfg /* XXX: for now, say it's OK if the alias escapes. 901258501Spfg Not sure this is needed in general, but otherwise GCC will not 902258501Spfg bootstrap. */ 903258501Spfg if (var_ann (get_ssa_base (alias))->escape_mask != NO_ESCAPE) 904258501Spfg return false; 905258501Spfg 906258501Spfg /* XXX: don't get into structures for now. It brings much complication 907258501Spfg and little benefit. */ 908258501Spfg if (struct_class_union_p (ptr_type) || struct_class_union_p (alias_type)) 909258501Spfg return false; 910258501Spfg 911258501Spfg /* XXX: In 4.2.1, field resolution in alias is not as good as in pre-4.3 912258501Spfg This fixes problems found during the backport, where a pointer to the 913258501Spfg first field of a struct appears to be aliased to the whole struct. */ 914258501Spfg if (struct_field_tag_p (alias)) 915258501Spfg return false; 916258501Spfg 917258501Spfg /* If they are both SSA names of artificials, let it go, the warning 918258501Spfg is too confusing. */ 919258501Spfg if (find_first_artificial_name (ptr) && find_first_artificial_name (alias)) 920258501Spfg return false; 921258501Spfg 922258501Spfg /* Compare the types. */ 923258501Spfg return nonstandard_alias_types_p (ptr_type, alias_type); 924258501Spfg} 925258501Spfg 926258501Spfg 927258501Spfg/* Return true when we should skip analysis for pointer PTR based on the 928258501Spfg fact that their alias information *PI is not considered relevant. */ 929258501Spfg 930258501Spfgstatic bool 931258501Spfgskip_this_pointer (tree ptr ATTRIBUTE_UNUSED, struct ptr_info_def *pi) 932258501Spfg{ 933258501Spfg /* If it is not dereferenced, it is not a problem (locally). */ 934258501Spfg if (!pi->is_dereferenced) 935258501Spfg return true; 936258501Spfg 937258501Spfg /* This would probably cause too many false positives. */ 938258501Spfg if (pi->value_escapes_p || pi->pt_anything) 939258501Spfg return true; 940258501Spfg 941258501Spfg return false; 942258501Spfg} 943258501Spfg 944258501Spfg 945258501Spfg/* Find aliasing to named objects for pointer PTR. */ 946258501Spfg 947258501Spfgstatic void 948258501Spfgdsa_named_for (tree ptr) 949258501Spfg{ 950258501Spfg struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 951258501Spfg 952258501Spfg if (pi) 953258501Spfg { 954258501Spfg if (skip_this_pointer (ptr, pi)) 955258501Spfg return; 956258501Spfg 957258501Spfg /* For all the variables it could be aliased to. */ 958258501Spfg if (pi->pt_vars) 959258501Spfg { 960258501Spfg unsigned ix; 961258501Spfg bitmap_iterator bi; 962258501Spfg 963258501Spfg EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) 964258501Spfg { 965258501Spfg tree alias = referenced_var (ix); 966258501Spfg 967258501Spfg if (is_global_var (alias)) 968258501Spfg continue; 969258501Spfg 970258501Spfg if (nonstandard_alias_p (ptr, alias, false)) 971258501Spfg strict_aliasing_warn (SSA_NAME_DEF_STMT (ptr), 972258501Spfg ptr, true, alias, false, true); 973258501Spfg } 974258501Spfg } 975258501Spfg } 976258501Spfg} 977258501Spfg 978258501Spfg 979258501Spfg/* Detect and report strict aliasing violation of named objects. */ 980258501Spfg 981258501Spfgstatic void 982258501Spfgdetect_strict_aliasing_named (void) 983258501Spfg{ 984258501Spfg unsigned int i; 985258501Spfg 986258501Spfg for (i = 1; i < num_ssa_names; i++) 987258501Spfg { 988258501Spfg tree ptr = ssa_name (i); 989258501Spfg struct ptr_info_def *pi; 990258501Spfg 991258501Spfg if (ptr == NULL_TREE) 992258501Spfg continue; 993258501Spfg 994258501Spfg pi = SSA_NAME_PTR_INFO (ptr); 995258501Spfg 996258501Spfg if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag) 997258501Spfg dsa_named_for (ptr); 998258501Spfg } 999258501Spfg} 1000258501Spfg 1001258501Spfg 1002258501Spfg/* Return false only the first time I see each instance of FUNC. */ 1003258501Spfg 1004258501Spfgstatic bool 1005258501Spfgprocessed_func_p (tree func) 1006258501Spfg{ 1007258501Spfg static htab_t seen = NULL; 1008258501Spfg void **slot; 1009258501Spfg 1010258501Spfg if (!seen) 1011258501Spfg seen = htab_create (100, htab_hash_pointer, htab_eq_pointer, NULL); 1012258501Spfg 1013258501Spfg slot = htab_find_slot (seen, func, INSERT); 1014258501Spfg gcc_assert (slot); 1015258501Spfg 1016258501Spfg if (*slot) 1017258501Spfg return true; 1018258501Spfg 1019258501Spfg *slot = func; 1020258501Spfg return false; 1021258501Spfg} 1022258501Spfg 1023258501Spfg 1024258501Spfg/* Detect and warn about type-punning using points-to information. */ 1025258501Spfg 1026258501Spfgvoid 1027258501Spfgstrict_aliasing_warning_backend (void) 1028258501Spfg{ 1029258501Spfg if (!(flag_strict_aliasing 1030258501Spfg && warn_strict_aliasing == 3 1031258501Spfg && !processed_func_p (current_function_decl))) 1032258501Spfg return; 1033258501Spfg 1034258501Spfg detect_strict_aliasing_named (); 1035258501Spfg maybe_free_reference_table (); 1036258501Spfg} 1037