]>
Commit | Line | Data |
---|---|---|
79bedddc | 1 | /* Strict aliasing checks. |
fa10beec | 2 | Copyright (C) 2007, 2008 Free Software Foundation, Inc. |
79bedddc SR |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
79bedddc SR |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
79bedddc SR |
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. | |
fa10beec | 96 | Takes care of the common pun+dereference pattern in the front end: |
79bedddc SR |
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 | |
c80b4100 | 156 | or by recording the points-to information before splitting the original |
79bedddc SR |
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; | |
726a989a | 247 | gimple site; |
79bedddc SR |
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 | |
726a989a | 255 | find_alias_site_helper (tree var ATTRIBUTE_UNUSED, gimple stmt, void *data) |
79bedddc SR |
256 | { |
257 | struct alias_match *match = (struct alias_match *) data; | |
726a989a | 258 | tree rhs_pointer = NULL_TREE; |
79bedddc SR |
259 | tree to_match = NULL_TREE; |
260 | ||
726a989a RB |
261 | if (gimple_assign_cast_p (stmt)) |
262 | rhs_pointer = gimple_assign_rhs1 (stmt); | |
79bedddc SR |
263 | |
264 | if (!rhs_pointer) | |
265 | /* Not a type conversion. */ | |
266 | return false; | |
267 | ||
268 | if (TREE_CODE (rhs_pointer) == ADDR_EXPR && !match->is_rhs_pointer) | |
269 | to_match = TREE_OPERAND (rhs_pointer, 0); | |
270 | else if (POINTER_TYPE_P (rhs_pointer) && match->is_rhs_pointer) | |
271 | to_match = rhs_pointer; | |
272 | ||
273 | if (to_match != match->rhs) | |
274 | /* Type conversion, but not a name match. */ | |
275 | return false; | |
276 | ||
277 | /* Found it. */ | |
278 | match->site = stmt; | |
279 | return true; | |
280 | } | |
281 | ||
282 | ||
283 | /* Find the statement where OBJECT1 gets aliased to OBJECT2. | |
284 | If IS_PTR2 is true, consider OBJECT2 to be the name of a pointer or | |
285 | reference rather than the actual aliased object. | |
286 | For now, just implement the case where OBJECT1 is an SSA name defined | |
287 | by a PHI statement. */ | |
288 | ||
726a989a | 289 | static gimple |
79bedddc SR |
290 | find_alias_site (tree object1, bool is_ptr1 ATTRIBUTE_UNUSED, |
291 | tree object2, bool is_ptr2) | |
292 | { | |
293 | struct alias_match match; | |
294 | ||
295 | match.rhs = object2; | |
296 | match.is_rhs_pointer = is_ptr2; | |
726a989a | 297 | match.site = NULL; |
79bedddc SR |
298 | |
299 | if (TREE_CODE (object1) != SSA_NAME) | |
726a989a | 300 | return NULL; |
79bedddc SR |
301 | |
302 | walk_use_def_chains (object1, find_alias_site_helper, &match, false); | |
303 | return match.site; | |
304 | } | |
305 | ||
306 | ||
307 | /* Structure to store temporary results when trying to figure out whether | |
308 | an object is referenced. Just its presence in the text is not enough, | |
309 | as we may just be taking its address. */ | |
310 | ||
311 | struct match_info | |
312 | { | |
313 | tree object; | |
314 | bool is_ptr; | |
315 | /* The difference between the number of references to OBJECT | |
c80b4100 | 316 | and the number of occurrences of &OBJECT. */ |
79bedddc SR |
317 | int found; |
318 | }; | |
319 | ||
320 | ||
321 | /* Return the base if EXPR is an SSA name. Return EXPR otherwise. */ | |
322 | ||
323 | static tree | |
324 | get_ssa_base (tree expr) | |
325 | { | |
326 | if (TREE_CODE (expr) == SSA_NAME) | |
327 | return SSA_NAME_VAR (expr); | |
328 | else | |
329 | return expr; | |
330 | } | |
331 | ||
332 | ||
333 | /* Record references to objects and pointer dereferences across some piece of | |
334 | code. The number of references is recorded for each item. | |
335 | References to an object just to take its address are not counted. | |
336 | For instance, if PTR is a pointer and OBJ is an object: | |
337 | 1. Expression &obj + *ptr will have the following reference match structure: | |
338 | ptrs: <ptr, 1> | |
339 | objs: <ptr, 1> | |
340 | OBJ does not appear as referenced because we just take its address. | |
341 | 2. Expression ptr + *ptr will have the following reference match structure: | |
342 | ptrs: <ptr, 1> | |
343 | objs: <ptr, 2> | |
344 | PTR shows up twice as an object, but is dereferenced only once. | |
345 | ||
726a989a | 346 | The elements of the hash tables are gimple_map objects. */ |
79bedddc SR |
347 | struct reference_matches |
348 | { | |
349 | htab_t ptrs; | |
350 | htab_t objs; | |
351 | }; | |
352 | ||
726a989a RB |
353 | struct gimple_tree_map |
354 | { | |
355 | tree from; | |
356 | gimple to; | |
357 | }; | |
358 | ||
359 | /* Return true if the from tree in both gimple-tree maps are equal. | |
360 | VA and VB are really instances of struct gimple_tree_map. */ | |
361 | ||
362 | static int | |
363 | gimple_tree_map_eq (const void *va, const void *vb) | |
364 | { | |
365 | const struct gimple_tree_map *const a = (const struct gimple_tree_map *) va; | |
366 | const struct gimple_tree_map *const b = (const struct gimple_tree_map *) vb; | |
367 | return (a->from == b->from); | |
368 | } | |
369 | ||
370 | /* Hash a from tree in a gimple_tree_map. ITEM is really an instance | |
371 | of struct gimple_tree_map. */ | |
79bedddc | 372 | |
726a989a RB |
373 | static unsigned int |
374 | gimple_tree_map_hash (const void *item) | |
375 | { | |
376 | return htab_hash_pointer (((const struct gimple_tree_map *)item)->from); | |
377 | } | |
378 | ||
379 | /* Return the match, if any. Otherwise, return NULL. It will return | |
380 | NULL even when a match was found, if the value associated to KEY is | |
381 | NULL. */ | |
79bedddc | 382 | |
726a989a | 383 | static inline gimple |
79bedddc SR |
384 | match (htab_t ref_map, tree key) |
385 | { | |
726a989a | 386 | struct gimple_tree_map *found; |
79bedddc SR |
387 | void **slot = NULL; |
388 | slot = htab_find_slot (ref_map, &key, NO_INSERT); | |
389 | ||
390 | if (!slot) | |
726a989a RB |
391 | return NULL; |
392 | ||
393 | found = (struct gimple_tree_map *) *slot; | |
79bedddc | 394 | |
79bedddc SR |
395 | return found->to; |
396 | } | |
397 | ||
398 | ||
399 | /* Set the entry corresponding to KEY, but only if the entry | |
400 | already exists and its value is NULL_TREE. Otherwise, do nothing. */ | |
401 | ||
402 | static inline void | |
726a989a | 403 | maybe_add_match (htab_t ref_map, struct gimple_tree_map *key) |
79bedddc | 404 | { |
726a989a RB |
405 | struct gimple_tree_map *found; |
406 | ||
407 | found = (struct gimple_tree_map *) htab_find (ref_map, key); | |
79bedddc SR |
408 | |
409 | if (found && !found->to) | |
410 | found->to = key->to; | |
411 | } | |
412 | ||
413 | ||
414 | /* Add an entry to HT, with key T and value NULL_TREE. */ | |
415 | ||
416 | static void | |
417 | add_key (htab_t ht, tree t, alloc_pool references_pool) | |
418 | { | |
419 | void **slot; | |
726a989a RB |
420 | struct gimple_tree_map *tp; |
421 | ||
422 | tp = (struct gimple_tree_map *) pool_alloc (references_pool); | |
79bedddc | 423 | |
726a989a RB |
424 | tp->from = t; |
425 | tp->to = NULL; | |
79bedddc SR |
426 | slot = htab_find_slot (ht, &t, INSERT); |
427 | *slot = (void *) tp; | |
428 | } | |
429 | ||
430 | ||
431 | /* Some memory to keep the objects in the reference table. */ | |
432 | ||
433 | static alloc_pool ref_table_alloc_pool = NULL; | |
434 | ||
435 | ||
436 | /* Get some memory to keep the objects in the reference table. */ | |
437 | ||
438 | static inline alloc_pool | |
439 | reference_table_alloc_pool (bool build) | |
440 | { | |
441 | if (ref_table_alloc_pool || !build) | |
442 | return ref_table_alloc_pool; | |
443 | ||
726a989a RB |
444 | ref_table_alloc_pool = create_alloc_pool ("ref_table_alloc_pool", |
445 | sizeof (struct gimple_tree_map), | |
446 | 20); | |
79bedddc SR |
447 | |
448 | return ref_table_alloc_pool; | |
449 | } | |
450 | ||
451 | ||
452 | /* Initialize the reference table by adding all pointers in the points-to | |
453 | table as keys, and NULL_TREE as associated values. */ | |
454 | ||
455 | static struct reference_matches * | |
456 | build_reference_table (void) | |
457 | { | |
458 | unsigned int i; | |
459 | struct reference_matches *ref_table = NULL; | |
460 | alloc_pool references_pool = reference_table_alloc_pool (true); | |
461 | ||
462 | ref_table = XNEW (struct reference_matches); | |
726a989a RB |
463 | ref_table->objs = htab_create (10, gimple_tree_map_hash, gimple_tree_map_eq, |
464 | NULL); | |
465 | ref_table->ptrs = htab_create (10, gimple_tree_map_hash, gimple_tree_map_eq, | |
466 | NULL); | |
79bedddc SR |
467 | |
468 | for (i = 1; i < num_ssa_names; i++) | |
469 | { | |
470 | tree ptr = ssa_name (i); | |
471 | struct ptr_info_def *pi; | |
472 | ||
473 | if (ptr == NULL_TREE) | |
474 | continue; | |
475 | ||
476 | pi = SSA_NAME_PTR_INFO (ptr); | |
477 | ||
478 | if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag) | |
479 | { | |
480 | /* Add pointer to the interesting dereference list. */ | |
481 | add_key (ref_table->ptrs, ptr, references_pool); | |
482 | ||
483 | /* Add all aliased names to the interesting reference list. */ | |
484 | if (pi->pt_vars) | |
485 | { | |
3b302421 RG |
486 | unsigned ix; |
487 | bitmap_iterator bi; | |
488 | ||
489 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) | |
490 | { | |
491 | tree alias = referenced_var (ix); | |
492 | add_key (ref_table->objs, alias, references_pool); | |
493 | } | |
79bedddc SR |
494 | } |
495 | } | |
496 | } | |
497 | ||
498 | return ref_table; | |
499 | } | |
500 | ||
501 | ||
502 | /* Reference table. */ | |
503 | ||
504 | static struct reference_matches *ref_table = NULL; | |
505 | ||
506 | ||
507 | /* Clean up the reference table if allocated. */ | |
508 | ||
509 | static void | |
510 | maybe_free_reference_table (void) | |
511 | { | |
512 | if (ref_table) | |
513 | { | |
514 | htab_delete (ref_table->ptrs); | |
515 | htab_delete (ref_table->objs); | |
516 | free (ref_table); | |
517 | ref_table = NULL; | |
518 | } | |
519 | ||
520 | if (ref_table_alloc_pool) | |
521 | { | |
522 | free_alloc_pool (ref_table_alloc_pool); | |
523 | ref_table_alloc_pool = NULL; | |
524 | } | |
525 | } | |
526 | ||
527 | ||
528 | /* Get the reference table. Initialize it if needed. */ | |
529 | ||
530 | static inline struct reference_matches * | |
531 | reference_table (bool build) | |
532 | { | |
533 | if (ref_table || !build) | |
534 | return ref_table; | |
535 | ||
536 | ref_table = build_reference_table (); | |
537 | find_references_in_function (); | |
538 | return ref_table; | |
539 | } | |
540 | ||
541 | ||
542 | /* Callback for find_references_in_function. | |
543 | Check whether *TP is an object reference or pointer dereference for the | |
544 | variables given in ((struct match_info*)DATA)->OBJS or | |
545 | ((struct match_info*)DATA)->PTRS. The total number of references | |
546 | is stored in the same structures. */ | |
547 | ||
548 | static tree | |
549 | find_references_in_tree_helper (tree *tp, | |
550 | int *walk_subtrees ATTRIBUTE_UNUSED, | |
551 | void *data) | |
552 | { | |
726a989a | 553 | struct gimple_tree_map match; |
79bedddc | 554 | static int parent_tree_code = ERROR_MARK; |
726a989a | 555 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; |
79bedddc SR |
556 | |
557 | /* Do not report references just for the purpose of taking an address. | |
558 | XXX: we rely on the fact that the tree walk is in preorder | |
559 | and that ADDR_EXPR is not a leaf, thus cannot be carried over across | |
560 | walks. */ | |
561 | if (parent_tree_code == ADDR_EXPR) | |
562 | goto finish; | |
563 | ||
726a989a | 564 | match.to = (gimple) wi->info; |
79bedddc SR |
565 | |
566 | if (TREE_CODE (*tp) == INDIRECT_REF) | |
567 | { | |
726a989a | 568 | match.from = TREE_OPERAND (*tp, 0); |
79bedddc SR |
569 | maybe_add_match (reference_table (true)->ptrs, &match); |
570 | } | |
571 | else | |
572 | { | |
726a989a | 573 | match.from = *tp; |
79bedddc SR |
574 | maybe_add_match (reference_table (true)->objs, &match); |
575 | } | |
576 | ||
577 | finish: | |
578 | parent_tree_code = TREE_CODE (*tp); | |
579 | return NULL_TREE; | |
580 | } | |
581 | ||
582 | ||
583 | /* Find all the references to aliased variables in the current function. */ | |
584 | ||
585 | static void | |
586 | find_references_in_function (void) | |
587 | { | |
588 | basic_block bb; | |
726a989a | 589 | gimple_stmt_iterator i; |
79bedddc SR |
590 | |
591 | FOR_EACH_BB (bb) | |
726a989a RB |
592 | for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) |
593 | { | |
594 | struct walk_stmt_info wi; | |
595 | memset (&wi, 0, sizeof (wi)); | |
596 | wi.info = (void *) gsi_stmt (i); | |
597 | walk_gimple_op (gsi_stmt (i), find_references_in_tree_helper, &wi); | |
598 | } | |
79bedddc SR |
599 | } |
600 | ||
601 | ||
602 | /* Find the reference site for OBJECT. | |
c80b4100 | 603 | If IS_PTR is true, look for dereferences of OBJECT instead. |
79bedddc SR |
604 | XXX: only the first site is returned in the current |
605 | implementation. If there are no matching sites, return NULL_TREE. */ | |
606 | ||
726a989a | 607 | static gimple |
79bedddc SR |
608 | reference_site (tree object, bool is_ptr) |
609 | { | |
610 | if (is_ptr) | |
611 | return match (reference_table (true)->ptrs, object); | |
612 | else | |
613 | return match (reference_table (true)->objs, object); | |
614 | } | |
615 | ||
616 | ||
617 | /* Try to get more location info when something is missing. | |
618 | OBJECT1 and OBJECT2 are aliased names. If IS_PTR1 or IS_PTR2, the alias | |
619 | is on the memory referenced or pointed to by OBJECT1 and OBJECT2. | |
620 | ALIAS_SITE, DEREF_SITE1 and DEREF_SITE2 are the statements where the | |
621 | alias takes place (some pointer assignment usually) and where the | |
622 | alias is referenced through OBJECT1 and OBJECT2 respectively. | |
623 | REF_TYPE1 and REF_TYPE2 will return the type of the reference at the | |
624 | respective sites. Only the first matching reference is returned for | |
625 | each name. If no statement is found, the function header is returned. */ | |
626 | ||
627 | static void | |
628 | maybe_find_missing_stmts (tree object1, bool is_ptr1, | |
629 | tree object2, bool is_ptr2, | |
726a989a RB |
630 | gimple *alias_site, |
631 | gimple *deref_site1, | |
632 | gimple *deref_site2) | |
79bedddc SR |
633 | { |
634 | if (object1 && object2) | |
635 | { | |
726a989a | 636 | if (!*alias_site || !gimple_has_location (*alias_site)) |
79bedddc SR |
637 | *alias_site = find_alias_site (object1, is_ptr1, object2, is_ptr2); |
638 | ||
726a989a | 639 | if (!*deref_site1 || !gimple_has_location (*deref_site1)) |
79bedddc SR |
640 | *deref_site1 = reference_site (object1, is_ptr1); |
641 | ||
726a989a | 642 | if (!*deref_site2 || !gimple_has_location (*deref_site2)) |
79bedddc SR |
643 | *deref_site2 = reference_site (object2, is_ptr2); |
644 | } | |
645 | ||
646 | /* If we could not find the alias site, set it to one of the dereference | |
647 | sites, if available. */ | |
648 | if (!*alias_site) | |
649 | { | |
650 | if (*deref_site1) | |
651 | *alias_site = *deref_site1; | |
652 | else if (*deref_site2) | |
653 | *alias_site = *deref_site2; | |
654 | } | |
655 | ||
656 | /* If we could not find the dereference sites, set them to the alias site, | |
657 | if known. */ | |
658 | if (!*deref_site1 && *alias_site) | |
659 | *deref_site1 = *alias_site; | |
660 | if (!*deref_site2 && *alias_site) | |
661 | *deref_site2 = *alias_site; | |
662 | } | |
663 | ||
664 | ||
665 | /* Callback for find_first_artificial_name. | |
666 | Find out if there are no artificial names at tree node *T. */ | |
667 | ||
668 | static tree | |
669 | ffan_walker (tree *t, | |
670 | int *go_below ATTRIBUTE_UNUSED, | |
671 | void *data ATTRIBUTE_UNUSED) | |
672 | { | |
7ffc27a6 | 673 | if (DECL_P (*t) && !MTAG_P (*t) && DECL_ARTIFICIAL (*t)) |
79bedddc SR |
674 | return *t; |
675 | else | |
676 | return NULL_TREE; | |
677 | } | |
678 | ||
679 | /* Return the first artificial name within EXPR, or NULL_TREE if | |
680 | none exists. */ | |
681 | ||
682 | static tree | |
683 | find_first_artificial_name (tree expr) | |
684 | { | |
685 | return walk_tree_without_duplicates (&expr, ffan_walker, NULL); | |
686 | } | |
687 | ||
688 | ||
689 | /* Get a name from the original program for VAR. */ | |
690 | ||
691 | static const char * | |
692 | get_var_name (tree var) | |
693 | { | |
694 | if (TREE_CODE (var) == SSA_NAME) | |
695 | return get_var_name (get_ssa_base (var)); | |
696 | ||
697 | if (find_first_artificial_name (var)) | |
698 | return "{unknown}"; | |
699 | ||
700 | if (TREE_CODE (var) == VAR_DECL || TREE_CODE (var) == PARM_DECL) | |
701 | if (DECL_NAME (var)) | |
702 | return IDENTIFIER_POINTER (DECL_NAME (var)); | |
703 | ||
704 | return "{unknown}"; | |
705 | } | |
706 | ||
707 | ||
708 | /* Return "*" if OBJECT is not the actual alias but a pointer to it, or | |
709 | "" otherwise. | |
710 | IS_PTR is true when OBJECT is not the actual alias. | |
711 | In addition to checking IS_PTR, we also make sure that OBJECT is a pointer | |
712 | since IS_PTR would also be true for C++ references, but we should only | |
713 | print a * before a pointer and not before a reference. */ | |
714 | ||
715 | static const char * | |
716 | get_maybe_star_prefix (tree object, bool is_ptr) | |
717 | { | |
718 | gcc_assert (object); | |
719 | return (is_ptr | |
720 | && TREE_CODE (TREE_TYPE (object)) == POINTER_TYPE) ? "*" : ""; | |
721 | } | |
722 | ||
79bedddc SR |
723 | /* Callback for contains_node_type_p. |
724 | Returns true if *T has tree code *(int*)DATA. */ | |
725 | ||
726 | static tree | |
727 | contains_node_type_p_callback (tree *t, | |
728 | int *go_below ATTRIBUTE_UNUSED, | |
729 | void *data) | |
730 | { | |
731 | return ((int) TREE_CODE (*t) == *((int *) data)) ? *t : NULL_TREE; | |
732 | } | |
733 | ||
734 | ||
735 | /* Return true if T contains a node with tree code TYPE. */ | |
736 | ||
737 | static bool | |
738 | contains_node_type_p (tree t, int type) | |
739 | { | |
740 | return (walk_tree_without_duplicates (&t, contains_node_type_p_callback, | |
741 | (void *) &type) | |
742 | != NULL_TREE); | |
743 | } | |
744 | ||
745 | ||
746 | /* Return true if a warning was issued in the front end at STMT. */ | |
747 | ||
748 | static bool | |
726a989a | 749 | already_warned_in_frontend_p (gimple stmt) |
79bedddc | 750 | { |
726a989a | 751 | if (stmt == NULL) |
79bedddc SR |
752 | return false; |
753 | ||
726a989a RB |
754 | if (gimple_assign_cast_p (stmt) |
755 | && TREE_NO_WARNING (gimple_assign_rhs1 (stmt))) | |
79bedddc SR |
756 | return true; |
757 | else | |
758 | return false; | |
759 | } | |
760 | ||
761 | ||
762 | /* Return true if and only if TYPE is a function or method pointer type, | |
763 | or pointer to a pointer to ... to a function or method. */ | |
764 | ||
765 | static bool | |
766 | is_method_pointer (tree type) | |
767 | { | |
768 | while (TREE_CODE (type) == POINTER_TYPE) | |
769 | type = TREE_TYPE (type); | |
770 | return TREE_CODE (type) == METHOD_TYPE || TREE_CODE (type) == FUNCTION_TYPE; | |
771 | } | |
772 | ||
773 | ||
774 | /* Issue a -Wstrict-aliasing warning. | |
775 | OBJECT1 and OBJECT2 are aliased names. | |
776 | If IS_PTR1 and/or IS_PTR2 is true, then the corresponding name | |
777 | OBJECT1/OBJECT2 is a pointer or reference to the aliased memory, | |
778 | rather than actual storage. | |
779 | ALIAS_SITE is a statement where the alias took place. In the most common | |
780 | case, that is where a pointer was assigned to the address of an object. */ | |
781 | ||
782 | static bool | |
726a989a | 783 | strict_aliasing_warn (gimple alias_site, |
79bedddc SR |
784 | tree object1, bool is_ptr1, |
785 | tree object2, bool is_ptr2, | |
786 | bool filter_artificials) | |
787 | { | |
726a989a RB |
788 | gimple ref_site1 = NULL; |
789 | gimple ref_site2 = NULL; | |
79bedddc SR |
790 | const char *name1; |
791 | const char *name2; | |
792 | location_t alias_loc; | |
793 | location_t ref1_loc; | |
794 | location_t ref2_loc; | |
795 | gcc_assert (object1); | |
796 | gcc_assert (object2); | |
797 | name1 = get_var_name (object1); | |
798 | name2 = get_var_name (object2); | |
799 | ||
800 | ||
801 | if (is_method_pointer (get_main_type (TREE_TYPE (object2)))) | |
802 | return false; | |
803 | ||
804 | maybe_find_missing_stmts (object1, is_ptr1, object2, is_ptr2, &alias_site, | |
805 | &ref_site1, &ref_site2); | |
806 | ||
726a989a RB |
807 | if (gimple_has_location (alias_site)) |
808 | alias_loc = gimple_location (alias_site); | |
79bedddc SR |
809 | else |
810 | return false; | |
811 | ||
726a989a RB |
812 | if (gimple_has_location (ref_site1)) |
813 | ref1_loc = gimple_location (ref_site1); | |
79bedddc SR |
814 | else |
815 | ref1_loc = alias_loc; | |
816 | ||
726a989a RB |
817 | if (gimple_has_location (ref_site2)) |
818 | ref2_loc = gimple_location (ref_site2); | |
79bedddc SR |
819 | else |
820 | ref2_loc = alias_loc; | |
821 | ||
822 | if (already_warned_in_frontend_p (alias_site)) | |
823 | return false; | |
824 | ||
825 | /* If they are not SSA names, but contain SSA names, drop the warning | |
826 | because it cannot be displayed well. | |
827 | Also drop it if they both contain artificials. | |
828 | XXX: this is a hack, must figure out a better way to display them. */ | |
829 | if (filter_artificials) | |
830 | if ((find_first_artificial_name (get_ssa_base (object1)) | |
831 | && find_first_artificial_name (get_ssa_base (object2))) | |
832 | || (TREE_CODE (object1) != SSA_NAME | |
833 | && contains_node_type_p (object1, SSA_NAME)) | |
834 | || (TREE_CODE (object2) != SSA_NAME | |
835 | && contains_node_type_p (object2, SSA_NAME))) | |
836 | return false; | |
837 | ||
838 | ||
839 | /* XXX: In the following format string, %s:%d should be replaced by %H. | |
840 | However, in my tests only the first %H printed ok, while the | |
841 | second and third were printed as blanks. */ | |
842 | warning (OPT_Wstrict_aliasing, | |
843 | "%Hlikely type-punning may break strict-aliasing rules: " | |
844 | "object %<%s%s%> of main type %qT is referenced at or around " | |
845 | "%s:%d and may be " | |
846 | "aliased to object %<%s%s%> of main type %qT which is referenced " | |
847 | "at or around %s:%d.", | |
848 | &alias_loc, | |
849 | get_maybe_star_prefix (object1, is_ptr1), | |
850 | name1, get_otype (object1, is_ptr1), | |
851 | LOCATION_FILE (ref1_loc), LOCATION_LINE (ref1_loc), | |
852 | get_maybe_star_prefix (object2, is_ptr2), | |
853 | name2, get_otype (object2, is_ptr2), | |
854 | LOCATION_FILE (ref2_loc), LOCATION_LINE (ref2_loc)); | |
855 | ||
856 | return true; | |
857 | } | |
858 | \f | |
859 | ||
860 | ||
861 | /* Return true when any objects of TYPE1 and TYPE2 respectively | |
862 | may not be aliased according to the language standard. */ | |
863 | ||
864 | static bool | |
865 | nonstandard_alias_types_p (tree type1, tree type2) | |
866 | { | |
4862826d ILT |
867 | alias_set_type set1; |
868 | alias_set_type set2; | |
79bedddc SR |
869 | |
870 | if (VOID_TYPE_P (type1) || VOID_TYPE_P (type2)) | |
871 | return false; | |
872 | ||
873 | set1 = get_alias_set (type1); | |
874 | set2 = get_alias_set (type2); | |
875 | return !alias_sets_conflict_p (set1, set2); | |
876 | } | |
877 | \f | |
878 | ||
879 | ||
880 | /* Returns true when *PTR may not be aliased to ALIAS. | |
881 | See C standard 6.5p7 and C++ standard 3.10p15. | |
882 | If PTR_PTR is true, ALIAS represents a pointer or reference to the | |
883 | aliased storage rather than its actual name. */ | |
884 | ||
885 | static bool | |
886 | nonstandard_alias_p (tree ptr, tree alias, bool ptr_ptr) | |
887 | { | |
888 | /* Find the types to compare. */ | |
889 | tree ptr_type = get_otype (ptr, true); | |
890 | tree alias_type = get_otype (alias, ptr_ptr); | |
891 | ||
892 | /* XXX: for now, say it's OK if the alias escapes. | |
893 | Not sure this is needed in general, but otherwise GCC will not | |
894 | bootstrap. */ | |
895 | if (var_ann (get_ssa_base (alias))->escape_mask != NO_ESCAPE) | |
896 | return false; | |
897 | ||
898 | /* XXX: don't get into structures for now. It brings much complication | |
899 | and little benefit. */ | |
900 | if (struct_class_union_p (ptr_type) || struct_class_union_p (alias_type)) | |
901 | return false; | |
902 | ||
903 | /* If they are both SSA names of artificials, let it go, the warning | |
904 | is too confusing. */ | |
905 | if (find_first_artificial_name (ptr) && find_first_artificial_name (alias)) | |
906 | return false; | |
907 | ||
908 | /* Compare the types. */ | |
909 | return nonstandard_alias_types_p (ptr_type, alias_type); | |
910 | } | |
911 | ||
912 | ||
913 | /* Return true when we should skip analysis for pointer PTR based on the | |
914 | fact that their alias information *PI is not considered relevant. */ | |
915 | ||
916 | static bool | |
917 | skip_this_pointer (tree ptr ATTRIBUTE_UNUSED, struct ptr_info_def *pi) | |
918 | { | |
919 | /* If it is not dereferenced, it is not a problem (locally). */ | |
920 | if (!pi->is_dereferenced) | |
921 | return true; | |
922 | ||
923 | /* This would probably cause too many false positives. */ | |
924 | if (pi->value_escapes_p || pi->pt_anything) | |
925 | return true; | |
926 | ||
927 | return false; | |
928 | } | |
929 | ||
930 | ||
931 | /* Find aliasing to named objects for pointer PTR. */ | |
932 | ||
933 | static void | |
726a989a | 934 | dsa_named_for (tree ptr ATTRIBUTE_UNUSED) |
79bedddc SR |
935 | { |
936 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
937 | ||
938 | if (pi) | |
939 | { | |
940 | if (skip_this_pointer (ptr, pi)) | |
941 | return; | |
942 | ||
943 | /* For all the variables it could be aliased to. */ | |
944 | if (pi->pt_vars) | |
945 | { | |
3b302421 RG |
946 | unsigned ix; |
947 | bitmap_iterator bi; | |
b3778556 | 948 | bool any = false; |
3b302421 RG |
949 | |
950 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) | |
951 | { | |
952 | tree alias = referenced_var (ix); | |
79bedddc | 953 | |
3b302421 RG |
954 | if (nonstandard_alias_p (ptr, alias, false)) |
955 | strict_aliasing_warn (SSA_NAME_DEF_STMT (ptr), | |
956 | ptr, true, alias, false, true); | |
b3778556 RG |
957 | else |
958 | any = true; | |
3b302421 | 959 | } |
b3778556 RG |
960 | |
961 | /* If there was no object in the points-to set that the pointer | |
962 | may alias, unconditionally warn. */ | |
963 | if (!any) | |
964 | warning (OPT_Wstrict_aliasing, | |
965 | "dereferencing type-punned pointer %D will " | |
966 | "break strict-aliasing rules", SSA_NAME_VAR (ptr)); | |
79bedddc SR |
967 | } |
968 | } | |
969 | } | |
970 | ||
971 | ||
972 | /* Detect and report strict aliasing violation of named objects. */ | |
973 | ||
974 | static void | |
975 | detect_strict_aliasing_named (void) | |
976 | { | |
977 | unsigned int i; | |
978 | ||
979 | for (i = 1; i < num_ssa_names; i++) | |
980 | { | |
981 | tree ptr = ssa_name (i); | |
982 | struct ptr_info_def *pi; | |
983 | ||
984 | if (ptr == NULL_TREE) | |
985 | continue; | |
986 | ||
987 | pi = SSA_NAME_PTR_INFO (ptr); | |
988 | ||
989 | if (!SSA_NAME_IN_FREE_LIST (ptr) && pi && pi->name_mem_tag) | |
990 | dsa_named_for (ptr); | |
991 | } | |
992 | } | |
993 | ||
994 | ||
995 | /* Return false only the first time I see each instance of FUNC. */ | |
996 | ||
997 | static bool | |
998 | processed_func_p (tree func) | |
999 | { | |
1000 | static htab_t seen = NULL; | |
1001 | void **slot = NULL; | |
1002 | ||
1003 | if (!seen) | |
726a989a | 1004 | seen = htab_create (10, gimple_tree_map_hash, gimple_tree_map_eq, NULL); |
79bedddc SR |
1005 | |
1006 | slot = htab_find_slot (seen, &func, INSERT); | |
1007 | gcc_assert (slot); | |
1008 | ||
1009 | if (*slot) | |
1010 | return true; | |
1011 | ||
1012 | gcc_assert (slot); | |
1013 | *slot = &func; | |
1014 | return false; | |
1015 | } | |
1016 | ||
1017 | ||
1018 | /* Detect and warn about type-punning using points-to information. */ | |
1019 | ||
1020 | void | |
1021 | strict_aliasing_warning_backend (void) | |
1022 | { | |
1023 | if (flag_strict_aliasing && warn_strict_aliasing == 3 | |
1024 | && !processed_func_p (current_function_decl)) | |
1025 | { | |
1026 | detect_strict_aliasing_named (); | |
1027 | maybe_free_reference_table (); | |
1028 | } | |
1029 | } |