]>
Commit | Line | Data |
---|---|---|
34f97b94 | 1 | /* Predicate aware uninitialized variable warning. |
99dee823 | 2 | Copyright (C) 2001-2021 Free Software Foundation, Inc. |
34f97b94 XDL |
3 | Contributed by Xinliang David Li <davidxl@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 | ||
72be80e4 | 21 | #define INCLUDE_STRING |
34f97b94 XDL |
22 | #include "config.h" |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
c7131fb2 | 25 | #include "backend.h" |
34f97b94 | 26 | #include "tree.h" |
c7131fb2 | 27 | #include "gimple.h" |
957060b5 | 28 | #include "tree-pass.h" |
c7131fb2 | 29 | #include "ssa.h" |
957060b5 AM |
30 | #include "gimple-pretty-print.h" |
31 | #include "diagnostic-core.h" | |
40e23961 | 32 | #include "fold-const.h" |
5be5c238 | 33 | #include "gimple-iterator.h" |
442b4905 | 34 | #include "tree-ssa.h" |
666e8e06 | 35 | #include "tree-cfg.h" |
11ef0b22 | 36 | #include "cfghooks.h" |
b825a228 MS |
37 | #include "attribs.h" |
38 | #include "builtins.h" | |
39 | #include "calls.h" | |
45f4e2b0 | 40 | #include "gimple-range.h" |
34f97b94 XDL |
41 | |
42 | /* This implements the pass that does predicate aware warning on uses of | |
ac0e4fde ML |
43 | possibly uninitialized variables. The pass first collects the set of |
44 | possibly uninitialized SSA names. For each such name, it walks through | |
45 | all its immediate uses. For each immediate use, it rebuilds the condition | |
46 | expression (the predicate) that guards the use. The predicate is then | |
34f97b94 XDL |
47 | examined to see if the variable is always defined under that same condition. |
48 | This is done either by pruning the unrealizable paths that lead to the | |
49 | default definitions or by checking if the predicate set that guards the | |
50 | defining paths is a superset of the use predicate. */ | |
51 | ||
358a95e4 AH |
52 | /* Max PHI args we can handle in pass. */ |
53 | const unsigned max_phi_args = 32; | |
54 | ||
34f97b94 XDL |
55 | /* Pointer set of potentially undefined ssa names, i.e., |
56 | ssa names that are defined by phi with operands that | |
57 | are not defined or potentially undefined. */ | |
6e2830c3 | 58 | static hash_set<tree> *possibly_undefined_names = 0; |
34f97b94 XDL |
59 | |
60 | /* Bit mask handling macros. */ | |
61 | #define MASK_SET_BIT(mask, pos) mask |= (1 << pos) | |
62 | #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos)) | |
63 | #define MASK_EMPTY(mask) (mask == 0) | |
64 | ||
65 | /* Returns the first bit position (starting from LSB) | |
ac0e4fde | 66 | in mask that is non zero. Returns -1 if the mask is empty. */ |
34f97b94 XDL |
67 | static int |
68 | get_mask_first_set_bit (unsigned mask) | |
69 | { | |
70 | int pos = 0; | |
71 | if (mask == 0) | |
72 | return -1; | |
73 | ||
74 | while ((mask & (1 << pos)) == 0) | |
75 | pos++; | |
76 | ||
77 | return pos; | |
78 | } | |
79 | #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask) | |
80 | ||
34f97b94 | 81 | /* Return true if T, an SSA_NAME, has an undefined value. */ |
c152901f AM |
82 | static bool |
83 | has_undefined_value_p (tree t) | |
34f97b94 | 84 | { |
c152901f | 85 | return (ssa_undefined_value_p (t) |
5e48d8a0 ML |
86 | || (possibly_undefined_names |
87 | && possibly_undefined_names->contains (t))); | |
34f97b94 XDL |
88 | } |
89 | ||
e9e2bad7 MS |
90 | /* Return true if EXPR should suppress either uninitialized warning. */ |
91 | ||
92 | static inline bool | |
93 | get_no_uninit_warning (tree expr) | |
94 | { | |
95 | return warning_suppressed_p (expr, OPT_Wuninitialized); | |
96 | } | |
97 | ||
98 | /* Suppress both uninitialized warnings for EXPR. */ | |
99 | ||
100 | static inline void | |
101 | set_no_uninit_warning (tree expr) | |
102 | { | |
103 | suppress_warning (expr, OPT_Wuninitialized); | |
104 | } | |
105 | ||
106 | /* Like has_undefined_value_p, but don't return true if the no-warning | |
107 | bit is set on SSA_NAME_VAR for either uninit warning. */ | |
ba7e83f8 JJ |
108 | |
109 | static inline bool | |
ac0e4fde ML |
110 | uninit_undefined_value_p (tree t) |
111 | { | |
c152901f | 112 | if (!has_undefined_value_p (t)) |
ba7e83f8 | 113 | return false; |
e9e2bad7 MS |
114 | if (!SSA_NAME_VAR (t)) |
115 | return true; | |
116 | return !get_no_uninit_warning (SSA_NAME_VAR (t)); | |
ba7e83f8 JJ |
117 | } |
118 | ||
c152901f AM |
119 | /* Emit warnings for uninitialized variables. This is done in two passes. |
120 | ||
121 | The first pass notices real uses of SSA names with undefined values. | |
122 | Such uses are unconditionally uninitialized, and we can be certain that | |
123 | such a use is a mistake. This pass is run before most optimizations, | |
124 | so that we catch as many as we can. | |
125 | ||
126 | The second pass follows PHI nodes to find uses that are potentially | |
127 | uninitialized. In this case we can't necessarily prove that the use | |
128 | is really uninitialized. This pass is run after most optimizations, | |
129 | so that we thread as many jumps and possible, and delete as much dead | |
130 | code as possible, in order to reduce false positives. We also look | |
131 | again for plain uninitialized variables, since optimization may have | |
132 | changed conditionally uninitialized to unconditionally uninitialized. */ | |
133 | ||
4e84e381 MS |
134 | /* Emit warning OPT for variable VAR at the point in the program where |
135 | the SSA_NAME T is being used uninitialized. The warning text is in | |
136 | MSGID and STMT is the statement that does the uninitialized read. | |
137 | PHI_ARG_LOC is the location of the PHI argument if T and VAR are one, | |
138 | or UNKNOWN_LOCATION otherwise. */ | |
c152901f AM |
139 | |
140 | static void | |
4e84e381 MS |
141 | warn_uninit (opt_code opt, tree t, tree var, const char *gmsgid, |
142 | gimple *context, location_t phi_arg_loc = UNKNOWN_LOCATION) | |
c152901f | 143 | { |
4e84e381 MS |
144 | /* Bail if the value isn't provably uninitialized. */ |
145 | if (!has_undefined_value_p (t)) | |
146 | return; | |
c152901f | 147 | |
e1ec47c4 TP |
148 | /* Ignore COMPLEX_EXPR as initializing only a part of a complex |
149 | turns in a COMPLEX_EXPR with the not initialized part being | |
150 | set to its previous (undefined) value. */ | |
151 | if (is_gimple_assign (context) | |
152 | && gimple_assign_rhs_code (context) == COMPLEX_EXPR) | |
153 | return; | |
50aa64d5 | 154 | /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p |
4e84e381 | 155 | can return true if the def stmt of an anonymous SSA_NAME is COMPLEX_EXPR |
50aa64d5 JJ |
156 | created for conversion from scalar to complex. Use the underlying var of |
157 | the COMPLEX_EXPRs real part in that case. See PR71581. */ | |
4e84e381 MS |
158 | if (!var && !SSA_NAME_VAR (t)) |
159 | { | |
160 | gimple *def_stmt = SSA_NAME_DEF_STMT (t); | |
161 | if (is_gimple_assign (def_stmt) | |
162 | && gimple_assign_rhs_code (def_stmt) == COMPLEX_EXPR) | |
50aa64d5 | 163 | { |
4e84e381 MS |
164 | tree v = gimple_assign_rhs1 (def_stmt); |
165 | if (TREE_CODE (v) == SSA_NAME | |
166 | && has_undefined_value_p (v) | |
167 | && zerop (gimple_assign_rhs2 (def_stmt))) | |
168 | var = SSA_NAME_VAR (v); | |
50aa64d5 JJ |
169 | } |
170 | } | |
171 | ||
4e84e381 | 172 | if (var == NULL_TREE) |
50aa64d5 JJ |
173 | return; |
174 | ||
4e84e381 MS |
175 | /* Avoid warning if we've already done so or if the warning has been |
176 | suppressed. */ | |
177 | if (((warning_suppressed_p (context, OPT_Wuninitialized) | |
178 | || (gimple_assign_single_p (context) | |
179 | && get_no_uninit_warning (gimple_assign_rhs1 (context))))) | |
180 | || get_no_uninit_warning (var)) | |
c152901f AM |
181 | return; |
182 | ||
4e84e381 MS |
183 | /* Use either the location of the read statement or that of the PHI |
184 | argument, or that of the uninitialized variable, in that order, | |
185 | whichever is valid. */ | |
186 | location_t location; | |
187 | if (gimple_has_location (context)) | |
e1ec47c4 | 188 | location = gimple_location (context); |
4e84e381 MS |
189 | else if (phi_arg_loc != UNKNOWN_LOCATION) |
190 | location = phi_arg_loc; | |
e1ec47c4 TP |
191 | else |
192 | location = DECL_SOURCE_LOCATION (var); | |
c152901f | 193 | location = linemap_resolve_location (line_table, location, |
ac0e4fde | 194 | LRK_SPELLING_LOCATION, NULL); |
4e84e381 | 195 | |
097f82ec | 196 | auto_diagnostic_group d; |
4e84e381 MS |
197 | if (!warning_at (location, opt, gmsgid, var)) |
198 | return; | |
199 | ||
200 | /* Avoid subsequent warnings for reads of the same variable again. */ | |
201 | suppress_warning (var, opt); | |
202 | ||
203 | /* Issue a note pointing to the read variable unless the warning | |
204 | is at the same location. */ | |
205 | location_t var_loc = DECL_SOURCE_LOCATION (var); | |
206 | if (location == var_loc) | |
207 | return; | |
c152901f | 208 | |
4e84e381 MS |
209 | location_t cfun_loc = DECL_SOURCE_LOCATION (cfun->decl); |
210 | expanded_location xloc = expand_location (location); | |
211 | expanded_location floc = expand_location (cfun_loc); | |
212 | if (xloc.file != floc.file | |
213 | || linemap_location_before_p (line_table, location, cfun_loc) | |
214 | || linemap_location_before_p (line_table, cfun->function_end_locus, | |
c152901f | 215 | location)) |
4e84e381 | 216 | inform (var_loc, "%qD was declared here", var); |
c152901f AM |
217 | } |
218 | ||
e80facb4 RB |
219 | struct check_defs_data |
220 | { | |
221 | /* If we found any may-defs besides must-def clobbers. */ | |
222 | bool found_may_defs; | |
223 | }; | |
224 | ||
6aacd901 MS |
225 | /* Return true if STMT is a call to built-in function all of whose |
226 | by-reference arguments are const-qualified (i.e., the function can | |
227 | be assumed not to modify them). */ | |
228 | ||
229 | static bool | |
230 | builtin_call_nomodifying_p (gimple *stmt) | |
231 | { | |
232 | if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) | |
233 | return false; | |
234 | ||
235 | tree fndecl = gimple_call_fndecl (stmt); | |
236 | if (!fndecl) | |
237 | return false; | |
238 | ||
239 | tree fntype = TREE_TYPE (fndecl); | |
240 | if (!fntype) | |
241 | return false; | |
242 | ||
243 | /* Check the called function's signature for non-constc pointers. | |
244 | If one is found, return false. */ | |
245 | unsigned argno = 0; | |
246 | tree argtype; | |
247 | function_args_iterator it; | |
248 | FOREACH_FUNCTION_ARGS (fntype, argtype, it) | |
249 | { | |
250 | if (VOID_TYPE_P (argtype)) | |
251 | return true; | |
252 | ||
253 | ++argno; | |
254 | ||
255 | if (!POINTER_TYPE_P (argtype)) | |
256 | continue; | |
257 | ||
258 | if (TYPE_READONLY (TREE_TYPE (argtype))) | |
259 | continue; | |
260 | ||
261 | return false; | |
262 | } | |
263 | ||
264 | /* If the number of actual arguments to the call is less than or | |
265 | equal to the number of parameters, return false. */ | |
266 | unsigned nargs = gimple_call_num_args (stmt); | |
267 | if (nargs <= argno) | |
268 | return false; | |
269 | ||
270 | /* Check arguments passed through the ellipsis in calls to variadic | |
271 | functions for pointers. If one is found that's a non-constant | |
272 | pointer, return false. */ | |
273 | for (; argno < nargs; ++argno) | |
274 | { | |
275 | tree arg = gimple_call_arg (stmt, argno); | |
276 | argtype = TREE_TYPE (arg); | |
277 | if (!POINTER_TYPE_P (argtype)) | |
278 | continue; | |
279 | ||
280 | if (TYPE_READONLY (TREE_TYPE (argtype))) | |
281 | continue; | |
282 | ||
283 | return false; | |
284 | } | |
285 | ||
286 | return true; | |
287 | } | |
288 | ||
fb85d6eb MS |
289 | /* If ARG is a FNDECL parameter declared with attribute access none or |
290 | write_only issue a warning for its read access via PTR. */ | |
291 | ||
292 | static void | |
293 | maybe_warn_read_write_only (tree fndecl, gimple *stmt, tree arg, tree ptr) | |
294 | { | |
295 | if (!fndecl) | |
296 | return; | |
297 | ||
298 | if (get_no_uninit_warning (arg)) | |
299 | return; | |
300 | ||
301 | tree fntype = TREE_TYPE (fndecl); | |
302 | if (!fntype) | |
303 | return; | |
304 | ||
305 | /* Initialize a map of attribute access specifications for arguments | |
306 | to the function function call. */ | |
307 | rdwr_map rdwr_idx; | |
308 | init_attr_rdwr_indices (&rdwr_idx, TYPE_ATTRIBUTES (fntype)); | |
309 | ||
310 | unsigned argno = 0; | |
311 | tree parms = DECL_ARGUMENTS (fndecl); | |
312 | for (tree parm = parms; parm; parm = TREE_CHAIN (parm), ++argno) | |
313 | { | |
314 | if (parm != arg) | |
315 | continue; | |
316 | ||
317 | const attr_access* access = rdwr_idx.get (argno); | |
318 | if (!access) | |
319 | break; | |
320 | ||
321 | if (access->mode != access_none | |
322 | && access->mode != access_write_only) | |
323 | continue; | |
324 | ||
325 | location_t stmtloc | |
326 | = linemap_resolve_location (line_table, gimple_location (stmt), | |
327 | LRK_SPELLING_LOCATION, NULL); | |
328 | ||
329 | if (!warning_at (stmtloc, OPT_Wmaybe_uninitialized, | |
330 | "%qE may be used uninitialized", ptr)) | |
331 | break; | |
332 | ||
333 | suppress_warning (arg, OPT_Wmaybe_uninitialized); | |
334 | ||
335 | const char* const access_str = | |
336 | TREE_STRING_POINTER (access->to_external_string ()); | |
337 | ||
338 | location_t parmloc = DECL_SOURCE_LOCATION (parm); | |
339 | inform (parmloc, "accessing argument %u of a function declared with " | |
340 | "attribute %<%s%>", | |
341 | argno + 1, access_str); | |
342 | ||
343 | break; | |
344 | } | |
345 | } | |
346 | ||
e80facb4 RB |
347 | /* Callback for walk_aliased_vdefs. */ |
348 | ||
349 | static bool | |
350 | check_defs (ao_ref *ref, tree vdef, void *data_) | |
351 | { | |
352 | check_defs_data *data = (check_defs_data *)data_; | |
353 | gimple *def_stmt = SSA_NAME_DEF_STMT (vdef); | |
2efe245b MS |
354 | |
355 | /* The ASAN_MARK intrinsic doesn't modify the variable. */ | |
e07d30fd MS |
356 | if (is_gimple_call (def_stmt)) |
357 | { | |
358 | if (gimple_call_internal_p (def_stmt) | |
359 | && gimple_call_internal_fn (def_stmt) == IFN_ASAN_MARK) | |
360 | return false; | |
361 | ||
362 | if (tree fndecl = gimple_call_fndecl (def_stmt)) | |
363 | { | |
364 | /* Some sanitizer calls pass integer arguments to built-ins | |
365 | that expect pointers. Avoid using gimple_call_builtin_p() | |
366 | which fails for such calls. */ | |
367 | if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) | |
368 | { | |
369 | built_in_function fncode = DECL_FUNCTION_CODE (fndecl); | |
370 | if (fncode > BEGIN_SANITIZER_BUILTINS | |
371 | && fncode < END_SANITIZER_BUILTINS) | |
372 | return false; | |
373 | } | |
374 | } | |
375 | } | |
2efe245b MS |
376 | |
377 | /* End of VLA scope is not a kill. */ | |
378 | if (gimple_call_builtin_p (def_stmt, BUILT_IN_STACK_RESTORE)) | |
379 | return false; | |
380 | ||
e80facb4 RB |
381 | /* If this is a clobber then if it is not a kill walk past it. */ |
382 | if (gimple_clobber_p (def_stmt)) | |
383 | { | |
384 | if (stmt_kills_ref_p (def_stmt, ref)) | |
385 | return true; | |
386 | return false; | |
387 | } | |
2efe245b | 388 | |
6aacd901 MS |
389 | if (builtin_call_nomodifying_p (def_stmt)) |
390 | return false; | |
391 | ||
e80facb4 RB |
392 | /* Found a may-def on this path. */ |
393 | data->found_may_defs = true; | |
394 | return true; | |
395 | } | |
396 | ||
b825a228 MS |
397 | /* Counters and limits controlling the the depth of analysis and |
398 | strictness of the warning. */ | |
399 | struct wlimits | |
400 | { | |
401 | /* Number of VDEFs encountered. */ | |
402 | unsigned int vdef_cnt; | |
403 | /* Number of statements examined by walk_aliased_vdefs. */ | |
404 | unsigned int oracle_cnt; | |
405 | /* Limit on the number of statements visited by walk_aliased_vdefs. */ | |
406 | unsigned limit; | |
407 | /* Set when basic block with statement is executed unconditionally. */ | |
408 | bool always_executed; | |
409 | /* Set to issue -Wmaybe-uninitialized. */ | |
410 | bool wmaybe_uninit; | |
411 | }; | |
412 | ||
413 | /* Determine if REF references an uninitialized operand and diagnose | |
fb85d6eb MS |
414 | it if so. STMS is the referencing statement. LHS is the result |
415 | of the access and may be null. RHS is the variable referenced by | |
416 | the access; it may not be null. */ | |
b825a228 MS |
417 | |
418 | static tree | |
419 | maybe_warn_operand (ao_ref &ref, gimple *stmt, tree lhs, tree rhs, | |
420 | wlimits &wlims) | |
421 | { | |
422 | bool has_bit_insert = false; | |
423 | use_operand_p luse_p; | |
424 | imm_use_iterator liter; | |
425 | ||
e9e2bad7 | 426 | if (get_no_uninit_warning (rhs)) |
b825a228 MS |
427 | return NULL_TREE; |
428 | ||
429 | /* Do not warn if the base was marked so or this is a | |
430 | hard register var. */ | |
431 | tree base = ao_ref_base (&ref); | |
432 | if ((VAR_P (base) | |
433 | && DECL_HARD_REGISTER (base)) | |
e9e2bad7 | 434 | || get_no_uninit_warning (base)) |
b825a228 MS |
435 | return NULL_TREE; |
436 | ||
1121e495 MS |
437 | /* Do not warn if the access is zero size or if it's fully outside |
438 | the object. */ | |
b825a228 | 439 | poly_int64 decl_size; |
1121e495 MS |
440 | if (known_size_p (ref.size) |
441 | && known_eq (ref.max_size, ref.size) | |
442 | && (known_eq (ref.size, 0) | |
443 | || known_le (ref.offset + ref.size, 0))) | |
444 | return NULL_TREE; | |
445 | ||
b825a228 | 446 | if (DECL_P (base) |
1121e495 MS |
447 | && known_ge (ref.offset, 0) |
448 | && DECL_SIZE (base) | |
449 | && poly_int_tree_p (DECL_SIZE (base), &decl_size) | |
450 | && known_le (decl_size, ref.offset)) | |
b825a228 MS |
451 | return NULL_TREE; |
452 | ||
453 | /* Do not warn if the result of the access is then used for | |
454 | a BIT_INSERT_EXPR. */ | |
455 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
456 | FOR_EACH_IMM_USE_FAST (luse_p, liter, lhs) | |
457 | { | |
458 | gimple *use_stmt = USE_STMT (luse_p); | |
459 | /* BIT_INSERT_EXPR first operand should not be considered | |
460 | a use for the purpose of uninit warnings. */ | |
461 | if (gassign *ass = dyn_cast <gassign *> (use_stmt)) | |
462 | { | |
463 | if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR | |
464 | && luse_p->use == gimple_assign_rhs1_ptr (ass)) | |
465 | { | |
466 | has_bit_insert = true; | |
467 | break; | |
468 | } | |
469 | } | |
470 | } | |
471 | ||
472 | if (has_bit_insert) | |
473 | return NULL_TREE; | |
474 | ||
475 | /* Limit the walking to a constant number of stmts after | |
476 | we overcommit quadratic behavior for small functions | |
477 | and O(n) behavior. */ | |
478 | if (wlims.oracle_cnt > 128 * 128 | |
479 | && wlims.oracle_cnt > wlims.vdef_cnt * 2) | |
480 | wlims.limit = 32; | |
481 | ||
482 | check_defs_data data; | |
483 | bool fentry_reached = false; | |
484 | data.found_may_defs = false; | |
485 | tree use = gimple_vuse (stmt); | |
486 | if (!use) | |
487 | return NULL_TREE; | |
488 | int res = walk_aliased_vdefs (&ref, use, | |
489 | check_defs, &data, NULL, | |
490 | &fentry_reached, wlims.limit); | |
491 | if (res == -1) | |
492 | { | |
493 | wlims.oracle_cnt += wlims.limit; | |
494 | return NULL_TREE; | |
495 | } | |
496 | ||
497 | wlims.oracle_cnt += res; | |
498 | if (data.found_may_defs) | |
499 | return NULL_TREE; | |
500 | ||
501 | bool found_alloc = false; | |
502 | ||
503 | if (fentry_reached) | |
504 | { | |
505 | if (TREE_CODE (base) == MEM_REF) | |
506 | base = TREE_OPERAND (base, 0); | |
507 | ||
508 | /* Follow the chain of SSA_NAME assignments looking for an alloca | |
509 | call (or VLA) or malloc/realloc, or for decls. If any is found | |
510 | (and in the latter case, the operand is a local variable) issue | |
511 | a warning. */ | |
512 | while (TREE_CODE (base) == SSA_NAME) | |
513 | { | |
514 | gimple *def_stmt = SSA_NAME_DEF_STMT (base); | |
515 | ||
516 | if (is_gimple_call (def_stmt) | |
517 | && gimple_call_builtin_p (def_stmt)) | |
518 | { | |
519 | /* Detect uses of uninitialized alloca/VLAs. */ | |
520 | tree fndecl = gimple_call_fndecl (def_stmt); | |
521 | const built_in_function fncode = DECL_FUNCTION_CODE (fndecl); | |
522 | if (fncode == BUILT_IN_ALLOCA | |
523 | || fncode == BUILT_IN_ALLOCA_WITH_ALIGN | |
524 | || fncode == BUILT_IN_MALLOC) | |
525 | found_alloc = true; | |
526 | break; | |
527 | } | |
528 | ||
529 | if (!is_gimple_assign (def_stmt)) | |
530 | break; | |
531 | ||
532 | tree_code code = gimple_assign_rhs_code (def_stmt); | |
533 | if (code != ADDR_EXPR && code != POINTER_PLUS_EXPR) | |
534 | break; | |
535 | ||
536 | base = gimple_assign_rhs1 (def_stmt); | |
537 | if (TREE_CODE (base) == ADDR_EXPR) | |
538 | base = TREE_OPERAND (base, 0); | |
539 | ||
540 | if (DECL_P (base) | |
541 | || TREE_CODE (base) == COMPONENT_REF) | |
542 | rhs = base; | |
543 | ||
544 | if (TREE_CODE (base) == MEM_REF) | |
545 | base = TREE_OPERAND (base, 0); | |
546 | ||
547 | if (tree ba = get_base_address (base)) | |
548 | base = ba; | |
549 | } | |
550 | ||
551 | /* Replace the RHS expression with BASE so that it | |
552 | refers to it in the diagnostic (instead of to | |
553 | '<unknown>'). */ | |
554 | if (DECL_P (base) | |
555 | && EXPR_P (rhs) | |
556 | && TREE_CODE (rhs) != COMPONENT_REF) | |
557 | rhs = base; | |
558 | } | |
559 | ||
560 | /* Do not warn if it can be initialized outside this function. | |
561 | If we did not reach function entry then we found killing | |
562 | clobbers on all paths to entry. */ | |
fb85d6eb MS |
563 | if (!found_alloc && fentry_reached) |
564 | { | |
565 | if (TREE_CODE (base) == SSA_NAME) | |
566 | { | |
567 | tree var = SSA_NAME_VAR (base); | |
568 | if (var && TREE_CODE (var) == PARM_DECL) | |
569 | { | |
570 | maybe_warn_read_write_only (cfun->decl, stmt, var, rhs); | |
571 | return NULL_TREE; | |
572 | } | |
573 | } | |
574 | ||
575 | if (!VAR_P (base) | |
576 | || is_global_var (base)) | |
577 | /* ??? We'd like to use ref_may_alias_global_p but that | |
578 | excludes global readonly memory and thus we get bogus | |
579 | warnings from p = cond ? "a" : "b" for example. */ | |
580 | return NULL_TREE; | |
581 | } | |
b825a228 MS |
582 | |
583 | /* Strip the address-of expression from arrays passed to functions. */ | |
584 | if (TREE_CODE (rhs) == ADDR_EXPR) | |
585 | rhs = TREE_OPERAND (rhs, 0); | |
586 | ||
587 | /* Check again since RHS may have changed above. */ | |
e9e2bad7 | 588 | if (get_no_uninit_warning (rhs)) |
b825a228 MS |
589 | return NULL_TREE; |
590 | ||
591 | /* Avoid warning about empty types such as structs with no members. | |
592 | The first_field() test is important for C++ where the predicate | |
593 | alone isn't always sufficient. */ | |
594 | tree rhstype = TREE_TYPE (rhs); | |
8b75204b MS |
595 | if (POINTER_TYPE_P (rhstype)) |
596 | rhstype = TREE_TYPE (rhstype); | |
3072125a | 597 | if (is_empty_type (rhstype)) |
b825a228 MS |
598 | return NULL_TREE; |
599 | ||
600 | bool warned = false; | |
601 | /* We didn't find any may-defs so on all paths either | |
602 | reached function entry or a killing clobber. */ | |
603 | location_t location | |
604 | = linemap_resolve_location (line_table, gimple_location (stmt), | |
605 | LRK_SPELLING_LOCATION, NULL); | |
606 | if (wlims.always_executed) | |
607 | { | |
608 | if (warning_at (location, OPT_Wuninitialized, | |
6d3bab5d | 609 | "%qE is used uninitialized", rhs)) |
b825a228 MS |
610 | { |
611 | /* ??? This is only effective for decls as in | |
612 | gcc.dg/uninit-B-O0.c. Avoid doing this for maybe-uninit | |
613 | uses or accesses by functions as it may hide important | |
614 | locations. */ | |
615 | if (lhs) | |
e9e2bad7 | 616 | set_no_uninit_warning (rhs); |
b825a228 MS |
617 | warned = true; |
618 | } | |
619 | } | |
620 | else if (wlims.wmaybe_uninit) | |
621 | warned = warning_at (location, OPT_Wmaybe_uninitialized, | |
6d3bab5d | 622 | "%qE may be used uninitialized", rhs); |
b825a228 MS |
623 | |
624 | return warned ? base : NULL_TREE; | |
625 | } | |
626 | ||
627 | ||
628 | /* Diagnose passing addresses of uninitialized objects to either const | |
629 | pointer arguments to functions, or to functions declared with attribute | |
630 | access implying read access to those objects. */ | |
631 | ||
632 | static void | |
0c9687d0 | 633 | maybe_warn_pass_by_reference (gcall *stmt, wlimits &wlims) |
b825a228 MS |
634 | { |
635 | if (!wlims.wmaybe_uninit) | |
636 | return; | |
637 | ||
638 | unsigned nargs = gimple_call_num_args (stmt); | |
639 | if (!nargs) | |
640 | return; | |
641 | ||
642 | tree fndecl = gimple_call_fndecl (stmt); | |
643 | tree fntype = gimple_call_fntype (stmt); | |
644 | if (!fntype) | |
645 | return; | |
646 | ||
0c9687d0 JH |
647 | /* Const function do not read their arguments. */ |
648 | if (gimple_call_flags (stmt) & ECF_CONST) | |
649 | return; | |
650 | ||
b825a228 MS |
651 | const built_in_function fncode |
652 | = (fndecl && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL) | |
653 | ? DECL_FUNCTION_CODE (fndecl) : (built_in_function)BUILT_IN_LAST); | |
654 | ||
655 | if (fncode == BUILT_IN_MEMCPY || fncode == BUILT_IN_MEMMOVE) | |
656 | /* Avoid diagnosing calls to raw memory functions (this is overly | |
657 | permissive; consider tightening it up). */ | |
658 | return; | |
659 | ||
660 | /* Save the current warning setting and replace it either a "maybe" | |
661 | when passing addresses of uninitialized variables to const-qualified | |
662 | pointers or arguments declared with attribute read_write, or with | |
663 | a "certain" when passing them to arguments declared with attribute | |
664 | read_only. */ | |
665 | const bool save_always_executed = wlims.always_executed; | |
666 | ||
72be80e4 MS |
667 | /* Initialize a map of attribute access specifications for arguments |
668 | to the function function call. */ | |
b825a228 | 669 | rdwr_map rdwr_idx; |
6450f073 | 670 | init_attr_rdwr_indices (&rdwr_idx, TYPE_ATTRIBUTES (fntype)); |
b825a228 MS |
671 | |
672 | tree argtype; | |
673 | unsigned argno = 0; | |
674 | function_args_iterator it; | |
675 | ||
676 | FOREACH_FUNCTION_ARGS (fntype, argtype, it) | |
677 | { | |
678 | ++argno; | |
679 | ||
680 | if (!POINTER_TYPE_P (argtype)) | |
681 | continue; | |
682 | ||
683 | tree access_size = NULL_TREE; | |
72be80e4 | 684 | const attr_access* access = rdwr_idx.get (argno - 1); |
b825a228 MS |
685 | if (access) |
686 | { | |
d14c547a MS |
687 | if (access->mode == access_none |
688 | || access->mode == access_write_only) | |
b825a228 | 689 | continue; |
72be80e4 MS |
690 | |
691 | if (access->mode == access_deferred | |
692 | && !TYPE_READONLY (TREE_TYPE (argtype))) | |
693 | continue; | |
694 | ||
d14c547a | 695 | if (save_always_executed && access->mode == access_read_only) |
b825a228 MS |
696 | /* Attribute read_only arguments imply read access. */ |
697 | wlims.always_executed = true; | |
698 | else | |
699 | /* Attribute read_write arguments are documented as requiring | |
700 | initialized objects but it's expected that aggregates may | |
701 | be only partially initialized regardless. */ | |
702 | wlims.always_executed = false; | |
703 | ||
704 | if (access->sizarg < nargs) | |
705 | access_size = gimple_call_arg (stmt, access->sizarg); | |
706 | } | |
707 | else if (!TYPE_READONLY (TREE_TYPE (argtype))) | |
708 | continue; | |
709 | else if (save_always_executed && fncode != BUILT_IN_LAST) | |
710 | /* Const-qualified arguments to built-ins imply read access. */ | |
711 | wlims.always_executed = true; | |
712 | else | |
713 | /* Const-qualified arguments to ordinary functions imply a likely | |
714 | (but not definitive) read access. */ | |
715 | wlims.always_executed = false; | |
716 | ||
0c9687d0 | 717 | /* Ignore args we are not going to read from. */ |
e12946df | 718 | if (gimple_call_arg_flags (stmt, argno - 1) & (EAF_UNUSED | EAF_NOREAD)) |
0c9687d0 JH |
719 | continue; |
720 | ||
b825a228 | 721 | tree arg = gimple_call_arg (stmt, argno - 1); |
9816f509 MS |
722 | if (!POINTER_TYPE_P (TREE_TYPE (arg))) |
723 | /* Avoid actual arguments with invalid types. */ | |
724 | continue; | |
b825a228 MS |
725 | |
726 | ao_ref ref; | |
727 | ao_ref_init_from_ptr_and_size (&ref, arg, access_size); | |
728 | tree argbase = maybe_warn_operand (ref, stmt, NULL_TREE, arg, wlims); | |
729 | if (!argbase) | |
730 | continue; | |
731 | ||
72be80e4 | 732 | if (access && access->mode != access_deferred) |
b825a228 | 733 | { |
72be80e4 MS |
734 | const char* const access_str = |
735 | TREE_STRING_POINTER (access->to_external_string ()); | |
b825a228 MS |
736 | |
737 | if (fndecl) | |
738 | { | |
739 | location_t loc = DECL_SOURCE_LOCATION (fndecl); | |
72be80e4 MS |
740 | inform (loc, "in a call to %qD declared with " |
741 | "attribute %<%s%> here", fndecl, access_str); | |
b825a228 MS |
742 | } |
743 | else | |
744 | { | |
745 | /* Handle calls through function pointers. */ | |
746 | location_t loc = gimple_location (stmt); | |
747 | inform (loc, "in a call to %qT declared with " | |
72be80e4 | 748 | "attribute %<%s%>", fntype, access_str); |
b825a228 MS |
749 | } |
750 | } | |
b825a228 MS |
751 | else |
752 | { | |
72be80e4 MS |
753 | /* For a declaration with no relevant attribute access create |
754 | a dummy object and use the formatting function to avoid | |
755 | having to complicate things here. */ | |
756 | attr_access ptr_access = { }; | |
757 | if (!access) | |
758 | access = &ptr_access; | |
759 | const std::string argtypestr = access->array_as_string (argtype); | |
760 | if (fndecl) | |
761 | { | |
762 | location_t loc (DECL_SOURCE_LOCATION (fndecl)); | |
baad4c48 | 763 | inform (loc, "by argument %u of type %s to %qD " |
72be80e4 MS |
764 | "declared here", |
765 | argno, argtypestr.c_str (), fndecl); | |
766 | } | |
767 | else | |
768 | { | |
769 | /* Handle calls through function pointers. */ | |
770 | location_t loc (gimple_location (stmt)); | |
baad4c48 | 771 | inform (loc, "by argument %u of type %s to %qT", |
72be80e4 MS |
772 | argno, argtypestr.c_str (), fntype); |
773 | } | |
b825a228 MS |
774 | } |
775 | ||
776 | if (DECL_P (argbase)) | |
777 | { | |
778 | location_t loc = DECL_SOURCE_LOCATION (argbase); | |
779 | inform (loc, "%qD declared here", argbase); | |
780 | } | |
781 | } | |
782 | ||
783 | wlims.always_executed = save_always_executed; | |
784 | } | |
785 | ||
66030d68 RB |
786 | /* Warn about an uninitialized PHI argument on the fallthru path to |
787 | an always executed block BB. */ | |
788 | ||
789 | static void | |
790 | warn_uninit_phi_uses (basic_block bb) | |
791 | { | |
792 | edge_iterator ei; | |
793 | edge e, found = NULL, found_back = NULL; | |
794 | /* Look for a fallthru and possibly a single backedge. */ | |
795 | FOR_EACH_EDGE (e, ei, bb->preds) | |
796 | { | |
797 | /* Ignore backedges. */ | |
798 | if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) | |
799 | { | |
800 | if (found_back) | |
801 | { | |
802 | found = NULL; | |
803 | break; | |
804 | } | |
805 | found_back = e; | |
806 | continue; | |
807 | } | |
808 | if (found) | |
809 | { | |
810 | found = NULL; | |
811 | break; | |
812 | } | |
813 | found = e; | |
814 | } | |
815 | if (!found) | |
816 | return; | |
817 | ||
818 | basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |
819 | for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); | |
820 | gsi_next (&si)) | |
821 | { | |
822 | gphi *phi = si.phi (); | |
823 | tree def = PHI_ARG_DEF_FROM_EDGE (phi, found); | |
824 | if (TREE_CODE (def) != SSA_NAME | |
825 | || !SSA_NAME_IS_DEFAULT_DEF (def) | |
826 | || virtual_operand_p (def)) | |
827 | continue; | |
828 | /* If there's a default def on the fallthru edge PHI | |
829 | value and there's a use that post-dominates entry | |
830 | then that use is uninitialized and we can warn. */ | |
831 | imm_use_iterator iter; | |
832 | use_operand_p use_p; | |
833 | gimple *use_stmt = NULL; | |
834 | FOR_EACH_IMM_USE_FAST (use_p, iter, gimple_phi_result (phi)) | |
835 | { | |
836 | use_stmt = USE_STMT (use_p); | |
837 | if (gimple_location (use_stmt) != UNKNOWN_LOCATION | |
838 | && dominated_by_p (CDI_POST_DOMINATORS, succ, | |
839 | gimple_bb (use_stmt)) | |
840 | /* If we found a non-fallthru edge make sure the | |
841 | use is inside the loop, otherwise the backedge | |
842 | can serve as initialization. */ | |
843 | && (!found_back | |
844 | || dominated_by_p (CDI_DOMINATORS, found_back->src, | |
845 | gimple_bb (use_stmt)))) | |
846 | break; | |
847 | use_stmt = NULL; | |
848 | } | |
849 | if (use_stmt) | |
850 | warn_uninit (OPT_Wuninitialized, def, SSA_NAME_VAR (def), | |
4e84e381 | 851 | "%qD is used uninitialized", use_stmt); |
66030d68 RB |
852 | } |
853 | } | |
b825a228 | 854 | |
4e84e381 MS |
855 | /* Issue warnings about reads of uninitialized variables. WMAYBE_UNINIT |
856 | is true to issue -Wmaybe-uninitialized, otherwise -Wuninitialized. */ | |
857 | ||
858 | static void | |
b825a228 | 859 | warn_uninitialized_vars (bool wmaybe_uninit) |
c152901f | 860 | { |
b825a228 MS |
861 | /* Counters and limits controlling the the depth of the warning. */ |
862 | wlimits wlims = { }; | |
863 | wlims.wmaybe_uninit = wmaybe_uninit; | |
864 | ||
c152901f AM |
865 | gimple_stmt_iterator gsi; |
866 | basic_block bb; | |
11cd3bed | 867 | FOR_EACH_BB_FN (bb, cfun) |
c152901f | 868 | { |
ac0e4fde | 869 | basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
b825a228 | 870 | wlims.always_executed = dominated_by_p (CDI_POST_DOMINATORS, succ, bb); |
66030d68 RB |
871 | |
872 | if (wlims.always_executed) | |
873 | warn_uninit_phi_uses (bb); | |
874 | ||
c152901f AM |
875 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
876 | { | |
355fe088 | 877 | gimple *stmt = gsi_stmt (gsi); |
c152901f AM |
878 | if (is_gimple_debug (stmt)) |
879 | continue; | |
880 | ||
881 | /* We only do data flow with SSA_NAMEs, so that's all we | |
882 | can warn about. */ | |
4e84e381 MS |
883 | use_operand_p use_p; |
884 | ssa_op_iter op_iter; | |
c152901f AM |
885 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE) |
886 | { | |
d07f8c59 RB |
887 | /* BIT_INSERT_EXPR first operand should not be considered |
888 | a use for the purpose of uninit warnings. */ | |
889 | if (gassign *ass = dyn_cast <gassign *> (stmt)) | |
890 | { | |
891 | if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR | |
892 | && use_p->use == gimple_assign_rhs1_ptr (ass)) | |
893 | continue; | |
894 | } | |
4e84e381 | 895 | tree use = USE_FROM_PTR (use_p); |
b825a228 | 896 | if (wlims.always_executed) |
ac0e4fde | 897 | warn_uninit (OPT_Wuninitialized, use, SSA_NAME_VAR (use), |
4e84e381 | 898 | "%qD is used uninitialized", stmt); |
b825a228 | 899 | else if (wmaybe_uninit) |
ac0e4fde | 900 | warn_uninit (OPT_Wmaybe_uninitialized, use, SSA_NAME_VAR (use), |
4e84e381 | 901 | "%qD may be used uninitialized", stmt); |
c152901f AM |
902 | } |
903 | ||
e80facb4 RB |
904 | /* For limiting the alias walk below we count all |
905 | vdefs in the function. */ | |
906 | if (gimple_vdef (stmt)) | |
b825a228 | 907 | wlims.vdef_cnt++; |
e80facb4 | 908 | |
0c9687d0 JH |
909 | if (gcall *call = dyn_cast <gcall *> (stmt)) |
910 | maybe_warn_pass_by_reference (call, wlims); | |
b825a228 MS |
911 | else if (gimple_assign_load_p (stmt) |
912 | && gimple_has_location (stmt)) | |
c152901f AM |
913 | { |
914 | tree rhs = gimple_assign_rhs1 (stmt); | |
6d20bf18 | 915 | tree lhs = gimple_assign_lhs (stmt); |
e80facb4 RB |
916 | |
917 | ao_ref ref; | |
918 | ao_ref_init (&ref, rhs); | |
b825a228 MS |
919 | tree var = maybe_warn_operand (ref, stmt, lhs, rhs, wlims); |
920 | if (!var) | |
d21a8e3b | 921 | continue; |
c152901f | 922 | |
b825a228 | 923 | if (DECL_P (var)) |
e80facb4 | 924 | { |
b825a228 MS |
925 | location_t loc = DECL_SOURCE_LOCATION (var); |
926 | inform (loc, "%qD declared here", var); | |
e80facb4 | 927 | } |
c152901f AM |
928 | } |
929 | } | |
930 | } | |
c152901f AM |
931 | } |
932 | ||
927734cf XDL |
933 | /* Checks if the operand OPND of PHI is defined by |
934 | another phi with one operand defined by this PHI, | |
ac0e4fde | 935 | but the rest operands are all defined. If yes, |
026c3cfd | 936 | returns true to skip this operand as being |
ac0e4fde | 937 | redundant. Can be enhanced to be more general. */ |
34f97b94 XDL |
938 | |
939 | static bool | |
355fe088 | 940 | can_skip_redundant_opnd (tree opnd, gimple *phi) |
34f97b94 | 941 | { |
4e84e381 MS |
942 | tree phi_def = gimple_phi_result (phi); |
943 | gimple *op_def = SSA_NAME_DEF_STMT (opnd); | |
34f97b94 XDL |
944 | if (gimple_code (op_def) != GIMPLE_PHI) |
945 | return false; | |
4e84e381 MS |
946 | |
947 | unsigned n = gimple_phi_num_args (op_def); | |
948 | for (unsigned i = 0; i < n; ++i) | |
34f97b94 XDL |
949 | { |
950 | tree op = gimple_phi_arg_def (op_def, i); | |
951 | if (TREE_CODE (op) != SSA_NAME) | |
5e48d8a0 | 952 | continue; |
ba7e83f8 | 953 | if (op != phi_def && uninit_undefined_value_p (op)) |
5e48d8a0 | 954 | return false; |
34f97b94 XDL |
955 | } |
956 | ||
957 | return true; | |
958 | } | |
959 | ||
960 | /* Returns a bit mask holding the positions of arguments in PHI | |
961 | that have empty (or possibly empty) definitions. */ | |
962 | ||
963 | static unsigned | |
538dd0b7 | 964 | compute_uninit_opnds_pos (gphi *phi) |
34f97b94 | 965 | { |
34f97b94 XDL |
966 | unsigned uninit_opnds = 0; |
967 | ||
4e84e381 | 968 | unsigned n = gimple_phi_num_args (phi); |
98d30e4f | 969 | /* Bail out for phi with too many args. */ |
358a95e4 | 970 | if (n > max_phi_args) |
98d30e4f | 971 | return 0; |
34f97b94 | 972 | |
4e84e381 | 973 | for (unsigned i = 0; i < n; ++i) |
34f97b94 XDL |
974 | { |
975 | tree op = gimple_phi_arg_def (phi, i); | |
976 | if (TREE_CODE (op) == SSA_NAME | |
5e48d8a0 ML |
977 | && uninit_undefined_value_p (op) |
978 | && !can_skip_redundant_opnd (op, phi)) | |
e7d764f3 | 979 | { |
5e48d8a0 | 980 | if (cfun->has_nonlocal_label || cfun->calls_setjmp) |
e7d764f3 | 981 | { |
aea0101d RB |
982 | /* Ignore SSA_NAMEs that appear on abnormal edges |
983 | somewhere. */ | |
984 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) | |
985 | continue; | |
e7d764f3 JJ |
986 | } |
987 | MASK_SET_BIT (uninit_opnds, i); | |
988 | } | |
34f97b94 XDL |
989 | } |
990 | return uninit_opnds; | |
991 | } | |
992 | ||
4e84e381 | 993 | /* Find the immediate postdominator of the specified basic block BLOCK. */ |
34f97b94 XDL |
994 | |
995 | static inline basic_block | |
996 | find_pdom (basic_block block) | |
997 | { | |
ac0e4fde ML |
998 | if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
999 | return EXIT_BLOCK_PTR_FOR_FN (cfun); | |
1000 | else | |
1001 | { | |
1002 | basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); | |
1003 | if (!bb) | |
1004 | return EXIT_BLOCK_PTR_FOR_FN (cfun); | |
1005 | return bb; | |
1006 | } | |
34f97b94 XDL |
1007 | } |
1008 | ||
4e84e381 | 1009 | /* Find the immediate dominator of the specified basic block BLOCK. */ |
34f97b94 XDL |
1010 | |
1011 | static inline basic_block | |
1012 | find_dom (basic_block block) | |
1013 | { | |
ac0e4fde ML |
1014 | if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
1015 | return ENTRY_BLOCK_PTR_FOR_FN (cfun); | |
1016 | else | |
1017 | { | |
1018 | basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block); | |
1019 | if (!bb) | |
1020 | return ENTRY_BLOCK_PTR_FOR_FN (cfun); | |
1021 | return bb; | |
1022 | } | |
34f97b94 XDL |
1023 | } |
1024 | ||
1025 | /* Returns true if BB1 is postdominating BB2 and BB1 is | |
ac0e4fde | 1026 | not a loop exit bb. The loop exit bb check is simple and does |
34f97b94 XDL |
1027 | not cover all cases. */ |
1028 | ||
1029 | static bool | |
1030 | is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2) | |
1031 | { | |
1032 | if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)) | |
1033 | return false; | |
1034 | ||
1035 | if (single_pred_p (bb1) && !single_succ_p (bb2)) | |
1036 | return false; | |
1037 | ||
1038 | return true; | |
1039 | } | |
1040 | ||
1041 | /* Find the closest postdominator of a specified BB, which is control | |
1042 | equivalent to BB. */ | |
1043 | ||
ac0e4fde | 1044 | static inline basic_block |
34f97b94 XDL |
1045 | find_control_equiv_block (basic_block bb) |
1046 | { | |
4e84e381 | 1047 | basic_block pdom = find_pdom (bb); |
34f97b94 XDL |
1048 | |
1049 | /* Skip the postdominating bb that is also loop exit. */ | |
1050 | if (!is_non_loop_exit_postdominating (pdom, bb)) | |
1051 | return NULL; | |
1052 | ||
1053 | if (dominated_by_p (CDI_DOMINATORS, pdom, bb)) | |
1054 | return pdom; | |
1055 | ||
1056 | return NULL; | |
1057 | } | |
1058 | ||
1059 | #define MAX_NUM_CHAINS 8 | |
1060 | #define MAX_CHAIN_LEN 5 | |
4dc1d68c | 1061 | #define MAX_POSTDOM_CHECK 8 |
666e8e06 | 1062 | #define MAX_SWITCH_CASES 40 |
34f97b94 XDL |
1063 | |
1064 | /* Computes the control dependence chains (paths of edges) | |
1065 | for DEP_BB up to the dominating basic block BB (the head node of a | |
92261ce0 JJ |
1066 | chain should be dominated by it). CD_CHAINS is pointer to an |
1067 | array holding the result chains. CUR_CD_CHAIN is the current | |
34f97b94 XDL |
1068 | chain being computed. *NUM_CHAINS is total number of chains. The |
1069 | function returns true if the information is successfully computed, | |
1070 | return false if there is no control dependence or not computed. */ | |
1071 | ||
1072 | static bool | |
1073 | compute_control_dep_chain (basic_block bb, basic_block dep_bb, | |
5e48d8a0 ML |
1074 | vec<edge> *cd_chains, |
1075 | size_t *num_chains, | |
92261ce0 JJ |
1076 | vec<edge> *cur_cd_chain, |
1077 | int *num_calls) | |
34f97b94 XDL |
1078 | { |
1079 | edge_iterator ei; | |
1080 | edge e; | |
1081 | size_t i; | |
1082 | bool found_cd_chain = false; | |
1083 | size_t cur_chain_len = 0; | |
1084 | ||
028d4092 | 1085 | if (*num_calls > param_uninit_control_dep_attempts) |
92261ce0 JJ |
1086 | return false; |
1087 | ++*num_calls; | |
1088 | ||
927734cf | 1089 | /* Could use a set instead. */ |
9771b263 | 1090 | cur_chain_len = cur_cd_chain->length (); |
34f97b94 XDL |
1091 | if (cur_chain_len > MAX_CHAIN_LEN) |
1092 | return false; | |
1093 | ||
1094 | for (i = 0; i < cur_chain_len; i++) | |
1095 | { | |
9771b263 | 1096 | edge e = (*cur_cd_chain)[i]; |
ac0e4fde | 1097 | /* Cycle detected. */ |
34f97b94 | 1098 | if (e->src == bb) |
5e48d8a0 | 1099 | return false; |
34f97b94 XDL |
1100 | } |
1101 | ||
1102 | FOR_EACH_EDGE (e, ei, bb->succs) | |
1103 | { | |
1104 | basic_block cd_bb; | |
4dc1d68c | 1105 | int post_dom_check = 0; |
34f97b94 | 1106 | if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL)) |
5e48d8a0 | 1107 | continue; |
34f97b94 XDL |
1108 | |
1109 | cd_bb = e->dest; | |
9771b263 | 1110 | cur_cd_chain->safe_push (e); |
34f97b94 | 1111 | while (!is_non_loop_exit_postdominating (cd_bb, bb)) |
5e48d8a0 ML |
1112 | { |
1113 | if (cd_bb == dep_bb) | |
1114 | { | |
1115 | /* Found a direct control dependence. */ | |
1116 | if (*num_chains < MAX_NUM_CHAINS) | |
1117 | { | |
1118 | cd_chains[*num_chains] = cur_cd_chain->copy (); | |
1119 | (*num_chains)++; | |
1120 | } | |
1121 | found_cd_chain = true; | |
1122 | /* Check path from next edge. */ | |
1123 | break; | |
1124 | } | |
1125 | ||
1126 | /* Now check if DEP_BB is indirectly control dependent on BB. */ | |
ac0e4fde ML |
1127 | if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains, |
1128 | cur_cd_chain, num_calls)) | |
5e48d8a0 ML |
1129 | { |
1130 | found_cd_chain = true; | |
1131 | break; | |
1132 | } | |
34f97b94 | 1133 | |
5e48d8a0 ML |
1134 | cd_bb = find_pdom (cd_bb); |
1135 | post_dom_check++; | |
ac0e4fde ML |
1136 | if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) |
1137 | || post_dom_check > MAX_POSTDOM_CHECK) | |
5e48d8a0 ML |
1138 | break; |
1139 | } | |
9771b263 DN |
1140 | cur_cd_chain->pop (); |
1141 | gcc_assert (cur_cd_chain->length () == cur_chain_len); | |
34f97b94 | 1142 | } |
9771b263 | 1143 | gcc_assert (cur_cd_chain->length () == cur_chain_len); |
34f97b94 XDL |
1144 | |
1145 | return found_cd_chain; | |
1146 | } | |
1147 | ||
ac0e4fde | 1148 | /* The type to represent a simple predicate. */ |
927734cf | 1149 | |
a79683d5 | 1150 | struct pred_info |
34f97b94 | 1151 | { |
927734cf XDL |
1152 | tree pred_lhs; |
1153 | tree pred_rhs; | |
1154 | enum tree_code cond_code; | |
34f97b94 | 1155 | bool invert; |
a79683d5 | 1156 | }; |
927734cf XDL |
1157 | |
1158 | /* The type to represent a sequence of predicates grouped | |
1159 | with .AND. operation. */ | |
34f97b94 | 1160 | |
927734cf | 1161 | typedef vec<pred_info, va_heap, vl_ptr> pred_chain; |
34f97b94 | 1162 | |
927734cf XDL |
1163 | /* The type to represent a sequence of pred_chains grouped |
1164 | with .OR. operation. */ | |
1165 | ||
1166 | typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union; | |
34f97b94 XDL |
1167 | |
1168 | /* Converts the chains of control dependence edges into a set of | |
ac0e4fde ML |
1169 | predicates. A control dependence chain is represented by a vector |
1170 | edges. DEP_CHAINS points to an array of dependence chains. | |
1171 | NUM_CHAINS is the size of the chain array. One edge in a dependence | |
927734cf | 1172 | chain is mapped to predicate expression represented by pred_info |
ac0e4fde | 1173 | type. One dependence chain is converted to a composite predicate that |
927734cf | 1174 | is the result of AND operation of pred_info mapped to each edge. |
ac0e4fde | 1175 | A composite predicate is presented by a vector of pred_info. On |
34f97b94 XDL |
1176 | return, *PREDS points to the resulting array of composite predicates. |
1177 | *NUM_PREDS is the number of composite predictes. */ | |
1178 | ||
1179 | static bool | |
9771b263 | 1180 | convert_control_dep_chain_into_preds (vec<edge> *dep_chains, |
5e48d8a0 ML |
1181 | size_t num_chains, |
1182 | pred_chain_union *preds) | |
34f97b94 XDL |
1183 | { |
1184 | bool has_valid_pred = false; | |
1185 | size_t i, j; | |
1186 | if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS) | |
1187 | return false; | |
1188 | ||
34f97b94 XDL |
1189 | /* Now convert the control dep chain into a set |
1190 | of predicates. */ | |
927734cf | 1191 | preds->reserve (num_chains); |
34f97b94 XDL |
1192 | |
1193 | for (i = 0; i < num_chains; i++) | |
1194 | { | |
9771b263 | 1195 | vec<edge> one_cd_chain = dep_chains[i]; |
c375a3a4 DL |
1196 | |
1197 | has_valid_pred = false; | |
927734cf | 1198 | pred_chain t_chain = vNULL; |
9771b263 | 1199 | for (j = 0; j < one_cd_chain.length (); j++) |
5e48d8a0 | 1200 | { |
355fe088 | 1201 | gimple *cond_stmt; |
5e48d8a0 ML |
1202 | gimple_stmt_iterator gsi; |
1203 | basic_block guard_bb; | |
1204 | pred_info one_pred; | |
1205 | edge e; | |
1206 | ||
1207 | e = one_cd_chain[j]; | |
1208 | guard_bb = e->src; | |
1209 | gsi = gsi_last_bb (guard_bb); | |
e7c6abad | 1210 | /* Ignore empty forwarder blocks. */ |
11ef0b22 AH |
1211 | if (empty_block_p (guard_bb) && single_succ_p (guard_bb)) |
1212 | continue; | |
e7c6abad AH |
1213 | /* An empty basic block here is likely a PHI, and is not one |
1214 | of the cases we handle below. */ | |
1215 | if (gsi_end_p (gsi)) | |
1216 | { | |
1217 | has_valid_pred = false; | |
1218 | break; | |
1219 | } | |
5e48d8a0 | 1220 | cond_stmt = gsi_stmt (gsi); |
ac0e4fde ML |
1221 | if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2) |
1222 | /* Ignore EH edge. Can add assertion on the other edge's flag. */ | |
1223 | continue; | |
5e48d8a0 ML |
1224 | /* Skip if there is essentially one succesor. */ |
1225 | if (EDGE_COUNT (e->src->succs) == 2) | |
1226 | { | |
1227 | edge e1; | |
1228 | edge_iterator ei1; | |
1229 | bool skip = false; | |
1230 | ||
1231 | FOR_EACH_EDGE (e1, ei1, e->src->succs) | |
1232 | { | |
1233 | if (EDGE_COUNT (e1->dest->succs) == 0) | |
1234 | { | |
1235 | skip = true; | |
1236 | break; | |
1237 | } | |
1238 | } | |
1239 | if (skip) | |
1240 | continue; | |
1241 | } | |
1242 | if (gimple_code (cond_stmt) == GIMPLE_COND) | |
666e8e06 RB |
1243 | { |
1244 | one_pred.pred_lhs = gimple_cond_lhs (cond_stmt); | |
1245 | one_pred.pred_rhs = gimple_cond_rhs (cond_stmt); | |
1246 | one_pred.cond_code = gimple_cond_code (cond_stmt); | |
1247 | one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE); | |
1248 | t_chain.safe_push (one_pred); | |
1249 | has_valid_pred = true; | |
1250 | } | |
ac0e4fde | 1251 | else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt)) |
666e8e06 RB |
1252 | { |
1253 | /* Avoid quadratic behavior. */ | |
1254 | if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES) | |
1255 | { | |
1256 | has_valid_pred = false; | |
1257 | break; | |
1258 | } | |
1259 | /* Find the case label. */ | |
1260 | tree l = NULL_TREE; | |
1261 | unsigned idx; | |
1262 | for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx) | |
1263 | { | |
1264 | tree tl = gimple_switch_label (gs, idx); | |
61ff5d6f | 1265 | if (e->dest == label_to_block (cfun, CASE_LABEL (tl))) |
666e8e06 RB |
1266 | { |
1267 | if (!l) | |
1268 | l = tl; | |
1269 | else | |
1270 | { | |
1271 | l = NULL_TREE; | |
1272 | break; | |
1273 | } | |
1274 | } | |
1275 | } | |
1276 | /* If more than one label reaches this block or the case | |
5e48d8a0 | 1277 | label doesn't have a single value (like the default one) |
666e8e06 RB |
1278 | fail. */ |
1279 | if (!l | |
1280 | || !CASE_LOW (l) | |
ac0e4fde ML |
1281 | || (CASE_HIGH (l) |
1282 | && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0))) | |
666e8e06 RB |
1283 | { |
1284 | has_valid_pred = false; | |
1285 | break; | |
1286 | } | |
1287 | one_pred.pred_lhs = gimple_switch_index (gs); | |
1288 | one_pred.pred_rhs = CASE_LOW (l); | |
1289 | one_pred.cond_code = EQ_EXPR; | |
1290 | one_pred.invert = false; | |
1291 | t_chain.safe_push (one_pred); | |
1292 | has_valid_pred = true; | |
1293 | } | |
1294 | else | |
5e48d8a0 ML |
1295 | { |
1296 | has_valid_pred = false; | |
1297 | break; | |
1298 | } | |
1299 | } | |
34f97b94 XDL |
1300 | |
1301 | if (!has_valid_pred) | |
a4f0c29d | 1302 | break; |
927734cf | 1303 | else |
a4f0c29d | 1304 | preds->safe_push (t_chain); |
34f97b94 XDL |
1305 | } |
1306 | return has_valid_pred; | |
1307 | } | |
1308 | ||
ac0e4fde | 1309 | /* Computes all control dependence chains for USE_BB. The control |
34f97b94 XDL |
1310 | dependence chains are then converted to an array of composite |
1311 | predicates pointed to by PREDS. PHI_BB is the basic block of | |
1312 | the phi whose result is used in USE_BB. */ | |
1313 | ||
1314 | static bool | |
927734cf | 1315 | find_predicates (pred_chain_union *preds, |
5e48d8a0 ML |
1316 | basic_block phi_bb, |
1317 | basic_block use_bb) | |
34f97b94 XDL |
1318 | { |
1319 | size_t num_chains = 0, i; | |
92261ce0 JJ |
1320 | int num_calls = 0; |
1321 | vec<edge> dep_chains[MAX_NUM_CHAINS]; | |
1322 | auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; | |
34f97b94 XDL |
1323 | bool has_valid_pred = false; |
1324 | basic_block cd_root = 0; | |
1325 | ||
34f97b94 XDL |
1326 | /* First find the closest bb that is control equivalent to PHI_BB |
1327 | that also dominates USE_BB. */ | |
1328 | cd_root = phi_bb; | |
1329 | while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) | |
1330 | { | |
1331 | basic_block ctrl_eq_bb = find_control_equiv_block (cd_root); | |
1332 | if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb)) | |
5e48d8a0 | 1333 | cd_root = ctrl_eq_bb; |
34f97b94 | 1334 | else |
5e48d8a0 | 1335 | break; |
34f97b94 XDL |
1336 | } |
1337 | ||
92261ce0 JJ |
1338 | compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains, |
1339 | &cur_chain, &num_calls); | |
34f97b94 XDL |
1340 | |
1341 | has_valid_pred | |
92261ce0 | 1342 | = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds); |
34f97b94 | 1343 | for (i = 0; i < num_chains; i++) |
9771b263 | 1344 | dep_chains[i].release (); |
34f97b94 XDL |
1345 | return has_valid_pred; |
1346 | } | |
1347 | ||
1348 | /* Computes the set of incoming edges of PHI that have non empty | |
1349 | definitions of a phi chain. The collection will be done | |
ac0e4fde ML |
1350 | recursively on operands that are defined by phis. CD_ROOT |
1351 | is the control dependence root. *EDGES holds the result, and | |
34f97b94 XDL |
1352 | VISITED_PHIS is a pointer set for detecting cycles. */ |
1353 | ||
1354 | static void | |
538dd0b7 | 1355 | collect_phi_def_edges (gphi *phi, basic_block cd_root, |
a4f0c29d | 1356 | auto_vec<edge> *edges, |
355fe088 | 1357 | hash_set<gimple *> *visited_phis) |
34f97b94 XDL |
1358 | { |
1359 | size_t i, n; | |
1360 | edge opnd_edge; | |
1361 | tree opnd; | |
1362 | ||
6e2830c3 | 1363 | if (visited_phis->add (phi)) |
34f97b94 XDL |
1364 | return; |
1365 | ||
1366 | n = gimple_phi_num_args (phi); | |
1367 | for (i = 0; i < n; i++) | |
1368 | { | |
1369 | opnd_edge = gimple_phi_arg_edge (phi, i); | |
1370 | opnd = gimple_phi_arg_def (phi, i); | |
1371 | ||
e74780a3 | 1372 | if (TREE_CODE (opnd) != SSA_NAME) |
5e48d8a0 ML |
1373 | { |
1374 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1375 | { | |
ac0e4fde | 1376 | fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i); |
ef6cb4c7 | 1377 | print_gimple_stmt (dump_file, phi, 0); |
5e48d8a0 ML |
1378 | } |
1379 | edges->safe_push (opnd_edge); | |
1380 | } | |
34f97b94 | 1381 | else |
5e48d8a0 | 1382 | { |
355fe088 | 1383 | gimple *def = SSA_NAME_DEF_STMT (opnd); |
e74780a3 | 1384 | |
5e48d8a0 | 1385 | if (gimple_code (def) == GIMPLE_PHI |
ac0e4fde ML |
1386 | && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root)) |
1387 | collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges, | |
5e48d8a0 ML |
1388 | visited_phis); |
1389 | else if (!uninit_undefined_value_p (opnd)) | |
1390 | { | |
1391 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1392 | { | |
ac0e4fde ML |
1393 | fprintf (dump_file, "\n[CHECK] Found def edge %d in ", |
1394 | (int) i); | |
ef6cb4c7 | 1395 | print_gimple_stmt (dump_file, phi, 0); |
5e48d8a0 ML |
1396 | } |
1397 | edges->safe_push (opnd_edge); | |
1398 | } | |
1399 | } | |
34f97b94 XDL |
1400 | } |
1401 | } | |
1402 | ||
1403 | /* For each use edge of PHI, computes all control dependence chains. | |
1404 | The control dependence chains are then converted to an array of | |
1405 | composite predicates pointed to by PREDS. */ | |
1406 | ||
1407 | static bool | |
538dd0b7 | 1408 | find_def_preds (pred_chain_union *preds, gphi *phi) |
34f97b94 XDL |
1409 | { |
1410 | size_t num_chains = 0, i, n; | |
92261ce0 JJ |
1411 | vec<edge> dep_chains[MAX_NUM_CHAINS]; |
1412 | auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; | |
a4f0c29d | 1413 | auto_vec<edge> def_edges; |
34f97b94 XDL |
1414 | bool has_valid_pred = false; |
1415 | basic_block phi_bb, cd_root = 0; | |
34f97b94 | 1416 | |
34f97b94 XDL |
1417 | phi_bb = gimple_bb (phi); |
1418 | /* First find the closest dominating bb to be | |
ac0e4fde | 1419 | the control dependence root. */ |
34f97b94 XDL |
1420 | cd_root = find_dom (phi_bb); |
1421 | if (!cd_root) | |
1422 | return false; | |
1423 | ||
355fe088 | 1424 | hash_set<gimple *> visited_phis; |
6e2830c3 | 1425 | collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis); |
34f97b94 | 1426 | |
9771b263 | 1427 | n = def_edges.length (); |
34f97b94 XDL |
1428 | if (n == 0) |
1429 | return false; | |
1430 | ||
1431 | for (i = 0; i < n; i++) | |
1432 | { | |
1433 | size_t prev_nc, j; | |
92261ce0 | 1434 | int num_calls = 0; |
34f97b94 XDL |
1435 | edge opnd_edge; |
1436 | ||
9771b263 | 1437 | opnd_edge = def_edges[i]; |
34f97b94 | 1438 | prev_nc = num_chains; |
92261ce0 JJ |
1439 | compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains, |
1440 | &num_chains, &cur_chain, &num_calls); | |
34f97b94 XDL |
1441 | |
1442 | /* Now update the newly added chains with | |
5e48d8a0 | 1443 | the phi operand edge: */ |
34f97b94 | 1444 | if (EDGE_COUNT (opnd_edge->src->succs) > 1) |
5e48d8a0 | 1445 | { |
92261ce0 JJ |
1446 | if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS) |
1447 | dep_chains[num_chains++] = vNULL; | |
5e48d8a0 | 1448 | for (j = prev_nc; j < num_chains; j++) |
92261ce0 | 1449 | dep_chains[j].safe_push (opnd_edge); |
5e48d8a0 | 1450 | } |
34f97b94 XDL |
1451 | } |
1452 | ||
1453 | has_valid_pred | |
92261ce0 | 1454 | = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds); |
34f97b94 | 1455 | for (i = 0; i < num_chains; i++) |
9771b263 | 1456 | dep_chains[i].release (); |
34f97b94 XDL |
1457 | return has_valid_pred; |
1458 | } | |
1459 | ||
11ef0b22 AH |
1460 | /* Dump a pred_info. */ |
1461 | ||
1462 | static void | |
1463 | dump_pred_info (pred_info one_pred) | |
1464 | { | |
1465 | if (one_pred.invert) | |
1466 | fprintf (dump_file, " (.NOT.) "); | |
1467 | print_generic_expr (dump_file, one_pred.pred_lhs); | |
1468 | fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code)); | |
1469 | print_generic_expr (dump_file, one_pred.pred_rhs); | |
1470 | } | |
1471 | ||
1472 | /* Dump a pred_chain. */ | |
1473 | ||
1474 | static void | |
1475 | dump_pred_chain (pred_chain one_pred_chain) | |
1476 | { | |
1477 | size_t np = one_pred_chain.length (); | |
1478 | for (size_t j = 0; j < np; j++) | |
1479 | { | |
1480 | dump_pred_info (one_pred_chain[j]); | |
1481 | if (j < np - 1) | |
1482 | fprintf (dump_file, " (.AND.) "); | |
1483 | else | |
1484 | fprintf (dump_file, "\n"); | |
1485 | } | |
1486 | } | |
1487 | ||
34f97b94 XDL |
1488 | /* Dumps the predicates (PREDS) for USESTMT. */ |
1489 | ||
1490 | static void | |
ac0e4fde | 1491 | dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg) |
34f97b94 | 1492 | { |
81018dcf | 1493 | fprintf (dump_file, "%s", msg); |
11ef0b22 AH |
1494 | if (usestmt) |
1495 | { | |
1496 | print_gimple_stmt (dump_file, usestmt, 0); | |
1497 | fprintf (dump_file, "is guarded by :\n\n"); | |
1498 | } | |
927734cf | 1499 | size_t num_preds = preds.length (); |
11ef0b22 | 1500 | for (size_t i = 0; i < num_preds; i++) |
34f97b94 | 1501 | { |
11ef0b22 | 1502 | dump_pred_chain (preds[i]); |
34f97b94 | 1503 | if (i < num_preds - 1) |
5e48d8a0 | 1504 | fprintf (dump_file, "(.OR.)\n"); |
927734cf | 1505 | else |
5e48d8a0 | 1506 | fprintf (dump_file, "\n\n"); |
34f97b94 XDL |
1507 | } |
1508 | } | |
1509 | ||
1510 | /* Destroys the predicate set *PREDS. */ | |
1511 | ||
1512 | static void | |
a4f0c29d | 1513 | destroy_predicate_vecs (pred_chain_union *preds) |
34f97b94 | 1514 | { |
927734cf XDL |
1515 | size_t i; |
1516 | ||
a4f0c29d | 1517 | size_t n = preds->length (); |
34f97b94 | 1518 | for (i = 0; i < n; i++) |
a4f0c29d ML |
1519 | (*preds)[i].release (); |
1520 | preds->release (); | |
34f97b94 XDL |
1521 | } |
1522 | ||
927734cf | 1523 | /* Computes the 'normalized' conditional code with operand |
34f97b94 XDL |
1524 | swapping and condition inversion. */ |
1525 | ||
1526 | static enum tree_code | |
ac0e4fde | 1527 | get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert) |
34f97b94 XDL |
1528 | { |
1529 | enum tree_code tc = orig_cmp_code; | |
1530 | ||
1531 | if (swap_cond) | |
1532 | tc = swap_tree_comparison (orig_cmp_code); | |
1533 | if (invert) | |
1534 | tc = invert_tree_comparison (tc, false); | |
1535 | ||
1536 | switch (tc) | |
1537 | { | |
1538 | case LT_EXPR: | |
1539 | case LE_EXPR: | |
1540 | case GT_EXPR: | |
1541 | case GE_EXPR: | |
1542 | case EQ_EXPR: | |
1543 | case NE_EXPR: | |
1544 | break; | |
1545 | default: | |
1546 | return ERROR_MARK; | |
1547 | } | |
1548 | return tc; | |
1549 | } | |
1550 | ||
5c1b3334 | 1551 | /* Returns whether VAL CMPC BOUNDARY is true. */ |
34f97b94 XDL |
1552 | |
1553 | static bool | |
1554 | is_value_included_in (tree val, tree boundary, enum tree_code cmpc) | |
1555 | { | |
1556 | bool inverted = false; | |
34f97b94 XDL |
1557 | bool result; |
1558 | ||
1559 | /* Only handle integer constant here. */ | |
ac0e4fde | 1560 | if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST) |
34f97b94 XDL |
1561 | return true; |
1562 | ||
ac0e4fde | 1563 | if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR) |
34f97b94 XDL |
1564 | { |
1565 | cmpc = invert_tree_comparison (cmpc, false); | |
1566 | inverted = true; | |
1567 | } | |
1568 | ||
fb4b60c6 VI |
1569 | if (cmpc == EQ_EXPR) |
1570 | result = tree_int_cst_equal (val, boundary); | |
1571 | else if (cmpc == LT_EXPR) | |
1572 | result = tree_int_cst_lt (val, boundary); | |
34f97b94 XDL |
1573 | else |
1574 | { | |
fb4b60c6 VI |
1575 | gcc_assert (cmpc == LE_EXPR); |
1576 | result = tree_int_cst_le (val, boundary); | |
34f97b94 XDL |
1577 | } |
1578 | ||
1579 | if (inverted) | |
1580 | result ^= 1; | |
1581 | ||
1582 | return result; | |
1583 | } | |
1584 | ||
0f8e84c6 VI |
1585 | /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can be |
1586 | either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like), | |
1587 | or BIT_AND_EXPR. EXACT_P is only meaningful for the latter. It modifies the | |
1588 | question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL. | |
1589 | For other values of CMPC, EXACT_P is ignored. */ | |
1590 | ||
1591 | static bool | |
1592 | value_sat_pred_p (tree val, tree boundary, enum tree_code cmpc, | |
1593 | bool exact_p = false) | |
1594 | { | |
1595 | if (cmpc != BIT_AND_EXPR) | |
1596 | return is_value_included_in (val, boundary, cmpc); | |
1597 | ||
56a4e074 | 1598 | wide_int andw = wi::to_wide (val) & wi::to_wide (boundary); |
0f8e84c6 VI |
1599 | if (exact_p) |
1600 | return andw == wi::to_wide (val); | |
1601 | else | |
1602 | return andw.to_uhwi (); | |
1603 | } | |
1604 | ||
34f97b94 | 1605 | /* Returns true if PRED is common among all the predicate |
7987a8d2 | 1606 | chains (PREDS) (and therefore can be factored out). */ |
34f97b94 XDL |
1607 | |
1608 | static bool | |
7987a8d2 | 1609 | find_matching_predicate_in_rest_chains (pred_info pred, pred_chain_union preds) |
34f97b94 XDL |
1610 | { |
1611 | size_t i, j, n; | |
1612 | ||
927734cf | 1613 | /* Trival case. */ |
7987a8d2 | 1614 | if (preds.length () == 1) |
34f97b94 XDL |
1615 | return true; |
1616 | ||
7987a8d2 | 1617 | for (i = 1; i < preds.length (); i++) |
34f97b94 XDL |
1618 | { |
1619 | bool found = false; | |
927734cf | 1620 | pred_chain one_chain = preds[i]; |
9771b263 | 1621 | n = one_chain.length (); |
34f97b94 | 1622 | for (j = 0; j < n; j++) |
5e48d8a0 ML |
1623 | { |
1624 | pred_info pred2 = one_chain[j]; | |
1625 | /* Can relax the condition comparison to not | |
ac0e4fde | 1626 | use address comparison. However, the most common |
5e48d8a0 ML |
1627 | case is that multiple control dependent paths share |
1628 | a common path prefix, so address comparison should | |
1629 | be ok. */ | |
1630 | ||
1631 | if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0) | |
1632 | && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0) | |
1633 | && pred2.invert == pred.invert) | |
1634 | { | |
1635 | found = true; | |
1636 | break; | |
1637 | } | |
1638 | } | |
34f97b94 | 1639 | if (!found) |
5e48d8a0 | 1640 | return false; |
34f97b94 XDL |
1641 | } |
1642 | return true; | |
1643 | } | |
1644 | ||
1645 | /* Forward declaration. */ | |
ac0e4fde ML |
1646 | static bool is_use_properly_guarded (gimple *use_stmt, |
1647 | basic_block use_bb, | |
1648 | gphi *phi, | |
1649 | unsigned uninit_opnds, | |
1650 | pred_chain_union *def_preds, | |
1651 | hash_set<gphi *> *visited_phis); | |
1652 | ||
1653 | /* Returns true if all uninitialized opnds are pruned. Returns false | |
1654 | otherwise. PHI is the phi node with uninitialized operands, | |
2edb37a6 XDL |
1655 | UNINIT_OPNDS is the bitmap of the uninitialize operand positions, |
1656 | FLAG_DEF is the statement defining the flag guarding the use of the | |
1657 | PHI output, BOUNDARY_CST is the const value used in the predicate | |
1658 | associated with the flag, CMP_CODE is the comparison code used in | |
1659 | the predicate, VISITED_PHIS is the pointer set of phis visited, and | |
1660 | VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions | |
1661 | that are also phis. | |
1662 | ||
1663 | Example scenario: | |
1664 | ||
1665 | BB1: | |
ac0e4fde | 1666 | flag_1 = phi <0, 1> // (1) |
2edb37a6 XDL |
1667 | var_1 = phi <undef, some_val> |
1668 | ||
1669 | ||
1670 | BB2: | |
1671 | flag_2 = phi <0, flag_1, flag_1> // (2) | |
1672 | var_2 = phi <undef, var_1, var_1> | |
1673 | if (flag_2 == 1) | |
1674 | goto BB3; | |
1675 | ||
1676 | BB3: | |
ac0e4fde | 1677 | use of var_2 // (3) |
2edb37a6 XDL |
1678 | |
1679 | Because some flag arg in (1) is not constant, if we do not look into the | |
1680 | flag phis recursively, it is conservatively treated as unknown and var_1 | |
ac0e4fde ML |
1681 | is thought to be flowed into use at (3). Since var_1 is potentially |
1682 | uninitialized a false warning will be emitted. | |
1683 | Checking recursively into (1), the compiler can find out that only some_val | |
1684 | (which is defined) can flow into (3) which is OK. */ | |
2edb37a6 XDL |
1685 | |
1686 | static bool | |
ac0e4fde ML |
1687 | prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def, |
1688 | tree boundary_cst, enum tree_code cmp_code, | |
1689 | hash_set<gphi *> *visited_phis, | |
1690 | bitmap *visited_flag_phis) | |
2edb37a6 XDL |
1691 | { |
1692 | unsigned i; | |
1693 | ||
358a95e4 | 1694 | for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++) |
2edb37a6 XDL |
1695 | { |
1696 | tree flag_arg; | |
1697 | ||
1698 | if (!MASK_TEST_BIT (uninit_opnds, i)) | |
5e48d8a0 | 1699 | continue; |
2edb37a6 XDL |
1700 | |
1701 | flag_arg = gimple_phi_arg_def (flag_def, i); | |
1702 | if (!is_gimple_constant (flag_arg)) | |
5e48d8a0 ML |
1703 | { |
1704 | gphi *flag_arg_def, *phi_arg_def; | |
1705 | tree phi_arg; | |
1706 | unsigned uninit_opnds_arg_phi; | |
1707 | ||
1708 | if (TREE_CODE (flag_arg) != SSA_NAME) | |
1709 | return false; | |
ac0e4fde | 1710 | flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg)); |
538dd0b7 | 1711 | if (!flag_arg_def) |
5e48d8a0 | 1712 | return false; |
2edb37a6 | 1713 | |
5e48d8a0 ML |
1714 | phi_arg = gimple_phi_arg_def (phi, i); |
1715 | if (TREE_CODE (phi_arg) != SSA_NAME) | |
1716 | return false; | |
2edb37a6 | 1717 | |
ac0e4fde | 1718 | phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg)); |
538dd0b7 | 1719 | if (!phi_arg_def) |
5e48d8a0 | 1720 | return false; |
2edb37a6 | 1721 | |
5e48d8a0 ML |
1722 | if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def)) |
1723 | return false; | |
2edb37a6 | 1724 | |
5e48d8a0 ML |
1725 | if (!*visited_flag_phis) |
1726 | *visited_flag_phis = BITMAP_ALLOC (NULL); | |
2edb37a6 | 1727 | |
ac0e4fde ML |
1728 | tree phi_result = gimple_phi_result (flag_arg_def); |
1729 | if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result))) | |
5e48d8a0 | 1730 | return false; |
2edb37a6 | 1731 | |
5e48d8a0 ML |
1732 | bitmap_set_bit (*visited_flag_phis, |
1733 | SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); | |
2edb37a6 | 1734 | |
5e48d8a0 ML |
1735 | /* Now recursively prune the uninitialized phi args. */ |
1736 | uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def); | |
ac0e4fde ML |
1737 | if (!prune_uninit_phi_opnds |
1738 | (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, boundary_cst, | |
1739 | cmp_code, visited_phis, visited_flag_phis)) | |
5e48d8a0 | 1740 | return false; |
2edb37a6 | 1741 | |
ac0e4fde ML |
1742 | phi_result = gimple_phi_result (flag_arg_def); |
1743 | bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result)); | |
5e48d8a0 ML |
1744 | continue; |
1745 | } | |
2edb37a6 XDL |
1746 | |
1747 | /* Now check if the constant is in the guarded range. */ | |
1748 | if (is_value_included_in (flag_arg, boundary_cst, cmp_code)) | |
5e48d8a0 ML |
1749 | { |
1750 | tree opnd; | |
355fe088 | 1751 | gimple *opnd_def; |
2edb37a6 | 1752 | |
5e48d8a0 | 1753 | /* Now that we know that this undefined edge is not |
ac0e4fde | 1754 | pruned. If the operand is defined by another phi, |
5e48d8a0 ML |
1755 | we can further prune the incoming edges of that |
1756 | phi by checking the predicates of this operands. */ | |
1757 | ||
1758 | opnd = gimple_phi_arg_def (phi, i); | |
1759 | opnd_def = SSA_NAME_DEF_STMT (opnd); | |
1760 | if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def)) | |
1761 | { | |
1762 | edge opnd_edge; | |
ac0e4fde | 1763 | unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi); |
8bc47ae2 RB |
1764 | if (!MASK_EMPTY (uninit_opnds2)) |
1765 | { | |
1766 | pred_chain_union def_preds = vNULL; | |
1767 | bool ok; | |
1768 | opnd_edge = gimple_phi_arg_edge (phi, i); | |
1769 | ok = is_use_properly_guarded (phi, | |
1770 | opnd_edge->src, | |
1771 | opnd_def_phi, | |
1772 | uninit_opnds2, | |
1773 | &def_preds, | |
1774 | visited_phis); | |
1775 | destroy_predicate_vecs (&def_preds); | |
1776 | if (!ok) | |
1777 | return false; | |
1778 | } | |
5e48d8a0 ML |
1779 | } |
1780 | else | |
1781 | return false; | |
1782 | } | |
2edb37a6 XDL |
1783 | } |
1784 | ||
1785 | return true; | |
1786 | } | |
1787 | ||
7987a8d2 BC |
1788 | /* A helper function finds predicate which will be examined against uninit |
1789 | paths. If there is no "flag_var cmp const" form predicate, the function | |
1790 | tries to find predicate of form like "flag_var cmp flag_var" with value | |
1791 | range info. PHI is the phi node whose incoming (undefined) paths need to | |
1792 | be examined. On success, the function returns the comparsion code, sets | |
1793 | defintion gimple of the flag_var to FLAG_DEF, sets boundary_cst to | |
1794 | BOUNDARY_CST. On fail, the function returns ERROR_MARK. */ | |
1795 | ||
1796 | static enum tree_code | |
1797 | find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def, | |
1798 | tree *boundary_cst) | |
1799 | { | |
1800 | enum tree_code vrinfo_code = ERROR_MARK, code; | |
1801 | gimple *vrinfo_def = NULL; | |
1802 | tree vrinfo_cst = NULL, cond_lhs, cond_rhs; | |
1803 | ||
1804 | gcc_assert (preds.length () > 0); | |
1805 | pred_chain the_pred_chain = preds[0]; | |
1806 | for (unsigned i = 0; i < the_pred_chain.length (); i++) | |
1807 | { | |
1808 | bool use_vrinfo_p = false; | |
1809 | pred_info the_pred = the_pred_chain[i]; | |
1810 | cond_lhs = the_pred.pred_lhs; | |
1811 | cond_rhs = the_pred.pred_rhs; | |
1812 | if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE) | |
1813 | continue; | |
1814 | ||
1815 | code = get_cmp_code (the_pred.cond_code, false, the_pred.invert); | |
1816 | if (code == ERROR_MARK) | |
1817 | continue; | |
1818 | ||
1819 | if (TREE_CODE (cond_lhs) == SSA_NAME && is_gimple_constant (cond_rhs)) | |
1820 | ; | |
1821 | else if (TREE_CODE (cond_rhs) == SSA_NAME | |
1822 | && is_gimple_constant (cond_lhs)) | |
1823 | { | |
1824 | std::swap (cond_lhs, cond_rhs); | |
1825 | if ((code = get_cmp_code (code, true, false)) == ERROR_MARK) | |
1826 | continue; | |
1827 | } | |
1828 | /* Check if we can take advantage of "flag_var comp flag_var" predicate | |
1829 | with value range info. Note only first of such case is handled. */ | |
1830 | else if (vrinfo_code == ERROR_MARK | |
1831 | && TREE_CODE (cond_lhs) == SSA_NAME | |
1832 | && TREE_CODE (cond_rhs) == SSA_NAME) | |
1833 | { | |
1834 | gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs); | |
1835 | if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI | |
1836 | || gimple_bb (lhs_def) != gimple_bb (phi)) | |
1837 | { | |
1838 | std::swap (cond_lhs, cond_rhs); | |
1839 | if ((code = get_cmp_code (code, true, false)) == ERROR_MARK) | |
1840 | continue; | |
1841 | } | |
1842 | ||
1843 | /* Check value range info of rhs, do following transforms: | |
1844 | flag_var < [min, max] -> flag_var < max | |
1845 | flag_var > [min, max] -> flag_var > min | |
1846 | ||
1847 | We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR: | |
1848 | flag_var <= [min, max] -> flag_var < [min, max+1] | |
1849 | flag_var >= [min, max] -> flag_var > [min-1, max] | |
1850 | if no overflow/wrap. */ | |
7987a8d2 | 1851 | tree type = TREE_TYPE (cond_lhs); |
45f4e2b0 | 1852 | value_range r; |
7987a8d2 | 1853 | if (!INTEGRAL_TYPE_P (type) |
45f4e2b0 AH |
1854 | || !get_range_query (cfun)->range_of_expr (r, cond_rhs) |
1855 | || r.kind () != VR_RANGE) | |
7987a8d2 | 1856 | continue; |
45f4e2b0 AH |
1857 | wide_int min = r.lower_bound (); |
1858 | wide_int max = r.upper_bound (); | |
7987a8d2 BC |
1859 | if (code == LE_EXPR |
1860 | && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type))) | |
1861 | { | |
1862 | code = LT_EXPR; | |
1863 | max = max + 1; | |
1864 | } | |
1865 | if (code == GE_EXPR | |
1866 | && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))) | |
1867 | { | |
1868 | code = GT_EXPR; | |
1869 | min = min - 1; | |
1870 | } | |
1871 | if (code == LT_EXPR) | |
1872 | cond_rhs = wide_int_to_tree (type, max); | |
1873 | else if (code == GT_EXPR) | |
1874 | cond_rhs = wide_int_to_tree (type, min); | |
1875 | else | |
1876 | continue; | |
1877 | ||
1878 | use_vrinfo_p = true; | |
1879 | } | |
1880 | else | |
1881 | continue; | |
1882 | ||
1883 | if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL) | |
1884 | continue; | |
1885 | ||
1886 | if (gimple_code (*flag_def) != GIMPLE_PHI | |
1887 | || gimple_bb (*flag_def) != gimple_bb (phi) | |
1888 | || !find_matching_predicate_in_rest_chains (the_pred, preds)) | |
1889 | continue; | |
1890 | ||
1891 | /* Return if any "flag_var comp const" predicate is found. */ | |
1892 | if (!use_vrinfo_p) | |
1893 | { | |
1894 | *boundary_cst = cond_rhs; | |
1895 | return code; | |
1896 | } | |
1897 | /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */ | |
1898 | else if (vrinfo_code == ERROR_MARK) | |
1899 | { | |
1900 | vrinfo_code = code; | |
1901 | vrinfo_def = *flag_def; | |
1902 | vrinfo_cst = cond_rhs; | |
1903 | } | |
1904 | } | |
1905 | /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */ | |
1906 | if (vrinfo_code != ERROR_MARK) | |
1907 | { | |
1908 | *flag_def = vrinfo_def; | |
1909 | *boundary_cst = vrinfo_cst; | |
1910 | } | |
1911 | return vrinfo_code; | |
1912 | } | |
1913 | ||
34f97b94 XDL |
1914 | /* A helper function that determines if the predicate set |
1915 | of the use is not overlapping with that of the uninit paths. | |
1916 | The most common senario of guarded use is in Example 1: | |
1917 | Example 1: | |
5e48d8a0 ML |
1918 | if (some_cond) |
1919 | { | |
1920 | x = ...; | |
1921 | flag = true; | |
1922 | } | |
34f97b94 | 1923 | |
5e48d8a0 | 1924 | ... some code ... |
34f97b94 | 1925 | |
5e48d8a0 ML |
1926 | if (flag) |
1927 | use (x); | |
34f97b94 XDL |
1928 | |
1929 | The real world examples are usually more complicated, but similar | |
1930 | and usually result from inlining: | |
1931 | ||
5e48d8a0 ML |
1932 | bool init_func (int * x) |
1933 | { | |
1934 | if (some_cond) | |
1935 | return false; | |
1936 | *x = .. | |
1937 | return true; | |
1938 | } | |
34f97b94 | 1939 | |
ac0e4fde | 1940 | void foo (..) |
5e48d8a0 ML |
1941 | { |
1942 | int x; | |
34f97b94 | 1943 | |
ac0e4fde | 1944 | if (!init_func (&x)) |
5e48d8a0 | 1945 | return; |
34f97b94 | 1946 | |
5e48d8a0 ML |
1947 | .. some_code ... |
1948 | use (x); | |
1949 | } | |
34f97b94 XDL |
1950 | |
1951 | Another possible use scenario is in the following trivial example: | |
1952 | ||
1953 | Example 2: | |
5e48d8a0 ML |
1954 | if (n > 0) |
1955 | x = 1; | |
1956 | ... | |
1957 | if (n > 0) | |
1958 | { | |
1959 | if (m < 2) | |
1960 | .. = x; | |
1961 | } | |
34f97b94 XDL |
1962 | |
1963 | Predicate analysis needs to compute the composite predicate: | |
1964 | ||
1965 | 1) 'x' use predicate: (n > 0) .AND. (m < 2) | |
1966 | 2) 'x' default value (non-def) predicate: .NOT. (n > 0) | |
1967 | (the predicate chain for phi operand defs can be computed | |
1968 | starting from a bb that is control equivalent to the phi's | |
1969 | bb and is dominating the operand def.) | |
1970 | ||
1971 | and check overlapping: | |
5e48d8a0 ML |
1972 | (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0)) |
1973 | <==> false | |
34f97b94 XDL |
1974 | |
1975 | This implementation provides framework that can handle | |
ac0e4fde | 1976 | scenarios. (Note that many simple cases are handled properly |
34f97b94 XDL |
1977 | without the predicate analysis -- this is due to jump threading |
1978 | transformation which eliminates the merge point thus makes | |
1979 | path sensitive analysis unnecessary.) | |
1980 | ||
358a95e4 AH |
1981 | PHI is the phi node whose incoming (undefined) paths need to be |
1982 | pruned, and UNINIT_OPNDS is the bitmap holding uninit operand | |
1983 | positions. VISITED_PHIS is the pointer set of phi stmts being | |
1984 | checked. */ | |
34f97b94 | 1985 | |
34f97b94 | 1986 | static bool |
927734cf | 1987 | use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds, |
5e48d8a0 | 1988 | gphi *phi, unsigned uninit_opnds, |
538dd0b7 | 1989 | hash_set<gphi *> *visited_phis) |
34f97b94 | 1990 | { |
355fe088 | 1991 | gimple *flag_def = 0; |
ac0e4fde | 1992 | tree boundary_cst = 0; |
34f97b94 | 1993 | enum tree_code cmp_code; |
2edb37a6 XDL |
1994 | bitmap visited_flag_phis = NULL; |
1995 | bool all_pruned = false; | |
34f97b94 | 1996 | |
34f97b94 XDL |
1997 | /* Find within the common prefix of multiple predicate chains |
1998 | a predicate that is a comparison of a flag variable against | |
1999 | a constant. */ | |
7987a8d2 BC |
2000 | cmp_code = find_var_cmp_const (preds, phi, &flag_def, &boundary_cst); |
2001 | if (cmp_code == ERROR_MARK) | |
34f97b94 XDL |
2002 | return false; |
2003 | ||
2004 | /* Now check all the uninit incoming edge has a constant flag value | |
2005 | that is in conflict with the use guard/predicate. */ | |
ac0e4fde ML |
2006 | all_pruned = prune_uninit_phi_opnds |
2007 | (phi, uninit_opnds, as_a<gphi *> (flag_def), boundary_cst, cmp_code, | |
2008 | visited_phis, &visited_flag_phis); | |
34f97b94 | 2009 | |
2edb37a6 XDL |
2010 | if (visited_flag_phis) |
2011 | BITMAP_FREE (visited_flag_phis); | |
34f97b94 | 2012 | |
2edb37a6 | 2013 | return all_pruned; |
34f97b94 XDL |
2014 | } |
2015 | ||
927734cf | 2016 | /* The helper function returns true if two predicates X1 and X2 |
ac0e4fde | 2017 | are equivalent. It assumes the expressions have already |
927734cf | 2018 | properly re-associated. */ |
34f97b94 XDL |
2019 | |
2020 | static inline bool | |
927734cf | 2021 | pred_equal_p (pred_info x1, pred_info x2) |
34f97b94 | 2022 | { |
927734cf XDL |
2023 | enum tree_code c1, c2; |
2024 | if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0) | |
2025 | || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0)) | |
2026 | return false; | |
34f97b94 | 2027 | |
927734cf | 2028 | c1 = x1.cond_code; |
c27348aa MP |
2029 | if (x1.invert != x2.invert |
2030 | && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison) | |
927734cf XDL |
2031 | c2 = invert_tree_comparison (x2.cond_code, false); |
2032 | else | |
2033 | c2 = x2.cond_code; | |
34f97b94 | 2034 | |
927734cf XDL |
2035 | return c1 == c2; |
2036 | } | |
34f97b94 | 2037 | |
927734cf | 2038 | /* Returns true if the predication is testing !=. */ |
34f97b94 | 2039 | |
927734cf XDL |
2040 | static inline bool |
2041 | is_neq_relop_p (pred_info pred) | |
34f97b94 | 2042 | { |
34f97b94 | 2043 | |
ac0e4fde ML |
2044 | return ((pred.cond_code == NE_EXPR && !pred.invert) |
2045 | || (pred.cond_code == EQ_EXPR && pred.invert)); | |
34f97b94 XDL |
2046 | } |
2047 | ||
927734cf | 2048 | /* Returns true if pred is of the form X != 0. */ |
34f97b94 | 2049 | |
5e48d8a0 | 2050 | static inline bool |
927734cf | 2051 | is_neq_zero_form_p (pred_info pred) |
34f97b94 | 2052 | { |
927734cf XDL |
2053 | if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs) |
2054 | || TREE_CODE (pred.pred_lhs) != SSA_NAME) | |
2055 | return false; | |
2056 | return true; | |
2057 | } | |
34f97b94 | 2058 | |
927734cf XDL |
2059 | /* The helper function returns true if two predicates X1 |
2060 | is equivalent to X2 != 0. */ | |
34f97b94 | 2061 | |
927734cf XDL |
2062 | static inline bool |
2063 | pred_expr_equal_p (pred_info x1, tree x2) | |
2064 | { | |
2065 | if (!is_neq_zero_form_p (x1)) | |
2066 | return false; | |
34f97b94 | 2067 | |
927734cf | 2068 | return operand_equal_p (x1.pred_lhs, x2, 0); |
34f97b94 XDL |
2069 | } |
2070 | ||
927734cf | 2071 | /* Returns true of the domain of single predicate expression |
ac0e4fde | 2072 | EXPR1 is a subset of that of EXPR2. Returns false if it |
67914693 | 2073 | cannot be proved. */ |
34f97b94 XDL |
2074 | |
2075 | static bool | |
927734cf | 2076 | is_pred_expr_subset_of (pred_info expr1, pred_info expr2) |
34f97b94 | 2077 | { |
927734cf | 2078 | enum tree_code code1, code2; |
34f97b94 | 2079 | |
927734cf | 2080 | if (pred_equal_p (expr1, expr2)) |
34f97b94 XDL |
2081 | return true; |
2082 | ||
927734cf XDL |
2083 | if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST) |
2084 | || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST)) | |
2085 | return false; | |
34f97b94 | 2086 | |
927734cf XDL |
2087 | if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0)) |
2088 | return false; | |
34f97b94 | 2089 | |
927734cf XDL |
2090 | code1 = expr1.cond_code; |
2091 | if (expr1.invert) | |
2092 | code1 = invert_tree_comparison (code1, false); | |
2093 | code2 = expr2.cond_code; | |
2094 | if (expr2.invert) | |
2095 | code2 = invert_tree_comparison (code2, false); | |
34f97b94 | 2096 | |
5c1b3334 VI |
2097 | if (code2 == NE_EXPR && code1 == NE_EXPR) |
2098 | return false; | |
2099 | ||
0f8e84c6 VI |
2100 | if (code2 == NE_EXPR) |
2101 | return !value_sat_pred_p (expr2.pred_rhs, expr1.pred_rhs, code1); | |
5c1b3334 | 2102 | |
0f8e84c6 VI |
2103 | if (code1 == EQ_EXPR) |
2104 | return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2); | |
666e8e06 | 2105 | |
0f8e84c6 VI |
2106 | if (code1 == code2) |
2107 | return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2, | |
2108 | code1 == BIT_AND_EXPR); | |
34f97b94 | 2109 | |
927734cf XDL |
2110 | return false; |
2111 | } | |
34f97b94 | 2112 | |
927734cf | 2113 | /* Returns true if the domain of PRED1 is a subset |
67914693 | 2114 | of that of PRED2. Returns false if it cannot be proved so. */ |
34f97b94 | 2115 | |
927734cf | 2116 | static bool |
ac0e4fde | 2117 | is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2) |
927734cf XDL |
2118 | { |
2119 | size_t np1, np2, i1, i2; | |
34f97b94 | 2120 | |
927734cf XDL |
2121 | np1 = pred1.length (); |
2122 | np2 = pred2.length (); | |
34f97b94 | 2123 | |
927734cf | 2124 | for (i2 = 0; i2 < np2; i2++) |
34f97b94 | 2125 | { |
927734cf XDL |
2126 | bool found = false; |
2127 | pred_info info2 = pred2[i2]; | |
2128 | for (i1 = 0; i1 < np1; i1++) | |
5e48d8a0 ML |
2129 | { |
2130 | pred_info info1 = pred1[i1]; | |
2131 | if (is_pred_expr_subset_of (info1, info2)) | |
2132 | { | |
2133 | found = true; | |
2134 | break; | |
2135 | } | |
2136 | } | |
927734cf | 2137 | if (!found) |
5e48d8a0 | 2138 | return false; |
34f97b94 | 2139 | } |
927734cf | 2140 | return true; |
34f97b94 XDL |
2141 | } |
2142 | ||
927734cf XDL |
2143 | /* Returns true if the domain defined by |
2144 | one pred chain ONE_PRED is a subset of the domain | |
ac0e4fde | 2145 | of *PREDS. It returns false if ONE_PRED's domain is |
927734cf XDL |
2146 | not a subset of any of the sub-domains of PREDS |
2147 | (corresponding to each individual chains in it), even | |
2148 | though it may be still be a subset of whole domain | |
2149 | of PREDS which is the union (ORed) of all its subdomains. | |
2150 | In other words, the result is conservative. */ | |
34f97b94 XDL |
2151 | |
2152 | static bool | |
927734cf | 2153 | is_included_in (pred_chain one_pred, pred_chain_union preds) |
34f97b94 XDL |
2154 | { |
2155 | size_t i; | |
927734cf | 2156 | size_t n = preds.length (); |
34f97b94 | 2157 | |
927734cf | 2158 | for (i = 0; i < n; i++) |
34f97b94 | 2159 | { |
927734cf | 2160 | if (is_pred_chain_subset_of (one_pred, preds[i])) |
5e48d8a0 | 2161 | return true; |
34f97b94 | 2162 | } |
927734cf | 2163 | |
34f97b94 XDL |
2164 | return false; |
2165 | } | |
2166 | ||
927734cf XDL |
2167 | /* Compares two predicate sets PREDS1 and PREDS2 and returns |
2168 | true if the domain defined by PREDS1 is a superset | |
ac0e4fde ML |
2169 | of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and |
2170 | PREDS2 respectively. The implementation chooses not to build | |
927734cf XDL |
2171 | generic trees (and relying on the folding capability of the |
2172 | compiler), but instead performs brute force comparison of | |
2173 | individual predicate chains (won't be a compile time problem | |
ac0e4fde | 2174 | as the chains are pretty short). When the function returns |
927734cf | 2175 | false, it does not necessarily mean *PREDS1 is not a superset |
155ed511 SL |
2176 | of *PREDS2, but mean it may not be so since the analysis cannot |
2177 | prove it. In such cases, false warnings may still be | |
927734cf | 2178 | emitted. */ |
34f97b94 XDL |
2179 | |
2180 | static bool | |
927734cf | 2181 | is_superset_of (pred_chain_union preds1, pred_chain_union preds2) |
34f97b94 | 2182 | { |
927734cf XDL |
2183 | size_t i, n2; |
2184 | pred_chain one_pred_chain = vNULL; | |
34f97b94 | 2185 | |
927734cf XDL |
2186 | n2 = preds2.length (); |
2187 | ||
2188 | for (i = 0; i < n2; i++) | |
34f97b94 | 2189 | { |
927734cf XDL |
2190 | one_pred_chain = preds2[i]; |
2191 | if (!is_included_in (one_pred_chain, preds1)) | |
5e48d8a0 | 2192 | return false; |
34f97b94 | 2193 | } |
927734cf | 2194 | |
34f97b94 XDL |
2195 | return true; |
2196 | } | |
2197 | ||
927734cf XDL |
2198 | /* Returns true if X1 is the negate of X2. */ |
2199 | ||
2200 | static inline bool | |
2201 | pred_neg_p (pred_info x1, pred_info x2) | |
2202 | { | |
2203 | enum tree_code c1, c2; | |
2204 | if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0) | |
2205 | || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0)) | |
2206 | return false; | |
5e48d8a0 | 2207 | |
927734cf XDL |
2208 | c1 = x1.cond_code; |
2209 | if (x1.invert == x2.invert) | |
2210 | c2 = invert_tree_comparison (x2.cond_code, false); | |
2211 | else | |
2212 | c2 = x2.cond_code; | |
2213 | ||
2214 | return c1 == c2; | |
34f97b94 XDL |
2215 | } |
2216 | ||
927734cf XDL |
2217 | /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0); |
2218 | 2) (X AND Y) OR (!X AND Y) is equivalent to Y; | |
2219 | 3) X OR (!X AND Y) is equivalent to (X OR Y); | |
2220 | 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to | |
2221 | (x != 0 AND y != 0) | |
2222 | 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to | |
5e48d8a0 | 2223 | (X AND Y) OR Z |
34f97b94 | 2224 | |
927734cf XDL |
2225 | PREDS is the predicate chains, and N is the number of chains. */ |
2226 | ||
2227 | /* Helper function to implement rule 1 above. ONE_CHAIN is | |
2228 | the AND predication to be simplified. */ | |
2229 | ||
2230 | static void | |
2231 | simplify_pred (pred_chain *one_chain) | |
34f97b94 | 2232 | { |
927734cf XDL |
2233 | size_t i, j, n; |
2234 | bool simplified = false; | |
2235 | pred_chain s_chain = vNULL; | |
34f97b94 | 2236 | |
927734cf | 2237 | n = one_chain->length (); |
34f97b94 | 2238 | |
927734cf | 2239 | for (i = 0; i < n; i++) |
34f97b94 | 2240 | { |
927734cf XDL |
2241 | pred_info *a_pred = &(*one_chain)[i]; |
2242 | ||
2243 | if (!a_pred->pred_lhs) | |
5e48d8a0 | 2244 | continue; |
927734cf | 2245 | if (!is_neq_zero_form_p (*a_pred)) |
5e48d8a0 | 2246 | continue; |
927734cf | 2247 | |
355fe088 | 2248 | gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs); |
927734cf | 2249 | if (gimple_code (def_stmt) != GIMPLE_ASSIGN) |
5e48d8a0 | 2250 | continue; |
927734cf | 2251 | if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR) |
5e48d8a0 ML |
2252 | { |
2253 | for (j = 0; j < n; j++) | |
2254 | { | |
2255 | pred_info *b_pred = &(*one_chain)[j]; | |
2256 | ||
2257 | if (!b_pred->pred_lhs) | |
2258 | continue; | |
2259 | if (!is_neq_zero_form_p (*b_pred)) | |
2260 | continue; | |
2261 | ||
2262 | if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt)) | |
2263 | || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt))) | |
ac0e4fde ML |
2264 | { |
2265 | /* Mark a_pred for removal. */ | |
2266 | a_pred->pred_lhs = NULL; | |
2267 | a_pred->pred_rhs = NULL; | |
2268 | simplified = true; | |
2269 | break; | |
2270 | } | |
5e48d8a0 ML |
2271 | } |
2272 | } | |
34f97b94 | 2273 | } |
34f97b94 | 2274 | |
927734cf | 2275 | if (!simplified) |
ac0e4fde | 2276 | return; |
34f97b94 | 2277 | |
927734cf XDL |
2278 | for (i = 0; i < n; i++) |
2279 | { | |
2280 | pred_info *a_pred = &(*one_chain)[i]; | |
2281 | if (!a_pred->pred_lhs) | |
5e48d8a0 | 2282 | continue; |
927734cf | 2283 | s_chain.safe_push (*a_pred); |
34f97b94 | 2284 | } |
927734cf | 2285 | |
ac0e4fde ML |
2286 | one_chain->release (); |
2287 | *one_chain = s_chain; | |
34f97b94 XDL |
2288 | } |
2289 | ||
927734cf XDL |
2290 | /* The helper function implements the rule 2 for the |
2291 | OR predicate PREDS. | |
2292 | ||
2293 | 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */ | |
34f97b94 XDL |
2294 | |
2295 | static bool | |
927734cf | 2296 | simplify_preds_2 (pred_chain_union *preds) |
34f97b94 | 2297 | { |
927734cf XDL |
2298 | size_t i, j, n; |
2299 | bool simplified = false; | |
2300 | pred_chain_union s_preds = vNULL; | |
34f97b94 | 2301 | |
5e48d8a0 | 2302 | /* (X AND Y) OR (!X AND Y) is equivalent to Y. |
927734cf | 2303 | (X AND Y) OR (X AND !Y) is equivalent to X. */ |
34f97b94 | 2304 | |
927734cf XDL |
2305 | n = preds->length (); |
2306 | for (i = 0; i < n; i++) | |
2307 | { | |
2308 | pred_info x, y; | |
2309 | pred_chain *a_chain = &(*preds)[i]; | |
34f97b94 | 2310 | |
927734cf | 2311 | if (a_chain->length () != 2) |
5e48d8a0 | 2312 | continue; |
927734cf XDL |
2313 | |
2314 | x = (*a_chain)[0]; | |
2315 | y = (*a_chain)[1]; | |
2316 | ||
2317 | for (j = 0; j < n; j++) | |
5e48d8a0 ML |
2318 | { |
2319 | pred_chain *b_chain; | |
2320 | pred_info x2, y2; | |
2321 | ||
2322 | if (j == i) | |
2323 | continue; | |
2324 | ||
2325 | b_chain = &(*preds)[j]; | |
2326 | if (b_chain->length () != 2) | |
2327 | continue; | |
2328 | ||
2329 | x2 = (*b_chain)[0]; | |
2330 | y2 = (*b_chain)[1]; | |
2331 | ||
2332 | if (pred_equal_p (x, x2) && pred_neg_p (y, y2)) | |
2333 | { | |
2334 | /* Kill a_chain. */ | |
2335 | a_chain->release (); | |
2336 | b_chain->release (); | |
2337 | b_chain->safe_push (x); | |
2338 | simplified = true; | |
2339 | break; | |
2340 | } | |
2341 | if (pred_neg_p (x, x2) && pred_equal_p (y, y2)) | |
2342 | { | |
2343 | /* Kill a_chain. */ | |
2344 | a_chain->release (); | |
2345 | b_chain->release (); | |
2346 | b_chain->safe_push (y); | |
2347 | simplified = true; | |
2348 | break; | |
2349 | } | |
2350 | } | |
927734cf XDL |
2351 | } |
2352 | /* Now clean up the chain. */ | |
2353 | if (simplified) | |
2354 | { | |
2355 | for (i = 0; i < n; i++) | |
5e48d8a0 ML |
2356 | { |
2357 | if ((*preds)[i].is_empty ()) | |
2358 | continue; | |
2359 | s_preds.safe_push ((*preds)[i]); | |
2360 | } | |
927734cf XDL |
2361 | preds->release (); |
2362 | (*preds) = s_preds; | |
2363 | s_preds = vNULL; | |
2364 | } | |
34f97b94 | 2365 | |
927734cf | 2366 | return simplified; |
34f97b94 XDL |
2367 | } |
2368 | ||
927734cf XDL |
2369 | /* The helper function implements the rule 2 for the |
2370 | OR predicate PREDS. | |
2371 | ||
2372 | 3) x OR (!x AND y) is equivalent to x OR y. */ | |
34f97b94 XDL |
2373 | |
2374 | static bool | |
927734cf | 2375 | simplify_preds_3 (pred_chain_union *preds) |
34f97b94 | 2376 | { |
927734cf XDL |
2377 | size_t i, j, n; |
2378 | bool simplified = false; | |
34f97b94 | 2379 | |
927734cf XDL |
2380 | /* Now iteratively simplify X OR (!X AND Z ..) |
2381 | into X OR (Z ...). */ | |
34f97b94 | 2382 | |
927734cf XDL |
2383 | n = preds->length (); |
2384 | if (n < 2) | |
2385 | return false; | |
2386 | ||
2387 | for (i = 0; i < n; i++) | |
34f97b94 | 2388 | { |
927734cf XDL |
2389 | pred_info x; |
2390 | pred_chain *a_chain = &(*preds)[i]; | |
2391 | ||
2392 | if (a_chain->length () != 1) | |
5e48d8a0 | 2393 | continue; |
927734cf XDL |
2394 | |
2395 | x = (*a_chain)[0]; | |
2396 | ||
2397 | for (j = 0; j < n; j++) | |
5e48d8a0 ML |
2398 | { |
2399 | pred_chain *b_chain; | |
2400 | pred_info x2; | |
2401 | size_t k; | |
2402 | ||
2403 | if (j == i) | |
2404 | continue; | |
2405 | ||
2406 | b_chain = &(*preds)[j]; | |
2407 | if (b_chain->length () < 2) | |
2408 | continue; | |
2409 | ||
2410 | for (k = 0; k < b_chain->length (); k++) | |
2411 | { | |
2412 | x2 = (*b_chain)[k]; | |
2413 | if (pred_neg_p (x, x2)) | |
2414 | { | |
2415 | b_chain->unordered_remove (k); | |
2416 | simplified = true; | |
2417 | break; | |
2418 | } | |
2419 | } | |
2420 | } | |
34f97b94 | 2421 | } |
927734cf | 2422 | return simplified; |
34f97b94 XDL |
2423 | } |
2424 | ||
927734cf XDL |
2425 | /* The helper function implements the rule 4 for the |
2426 | OR predicate PREDS. | |
2427 | ||
2428 | 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to | |
2429 | (x != 0 ANd y != 0). */ | |
34f97b94 XDL |
2430 | |
2431 | static bool | |
927734cf | 2432 | simplify_preds_4 (pred_chain_union *preds) |
34f97b94 | 2433 | { |
927734cf XDL |
2434 | size_t i, j, n; |
2435 | bool simplified = false; | |
2436 | pred_chain_union s_preds = vNULL; | |
355fe088 | 2437 | gimple *def_stmt; |
34f97b94 | 2438 | |
927734cf | 2439 | n = preds->length (); |
34f97b94 XDL |
2440 | for (i = 0; i < n; i++) |
2441 | { | |
927734cf XDL |
2442 | pred_info z; |
2443 | pred_chain *a_chain = &(*preds)[i]; | |
2444 | ||
2445 | if (a_chain->length () != 1) | |
5e48d8a0 | 2446 | continue; |
927734cf XDL |
2447 | |
2448 | z = (*a_chain)[0]; | |
2449 | ||
2450 | if (!is_neq_zero_form_p (z)) | |
5e48d8a0 | 2451 | continue; |
927734cf XDL |
2452 | |
2453 | def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs); | |
2454 | if (gimple_code (def_stmt) != GIMPLE_ASSIGN) | |
5e48d8a0 | 2455 | continue; |
927734cf XDL |
2456 | |
2457 | if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR) | |
5e48d8a0 | 2458 | continue; |
927734cf XDL |
2459 | |
2460 | for (j = 0; j < n; j++) | |
5e48d8a0 ML |
2461 | { |
2462 | pred_chain *b_chain; | |
2463 | pred_info x2, y2; | |
2464 | ||
2465 | if (j == i) | |
2466 | continue; | |
2467 | ||
2468 | b_chain = &(*preds)[j]; | |
2469 | if (b_chain->length () != 2) | |
2470 | continue; | |
2471 | ||
2472 | x2 = (*b_chain)[0]; | |
2473 | y2 = (*b_chain)[1]; | |
ac0e4fde | 2474 | if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2)) |
5e48d8a0 ML |
2475 | continue; |
2476 | ||
2477 | if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt)) | |
2478 | && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt))) | |
2479 | || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt)) | |
2480 | && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt)))) | |
2481 | { | |
2482 | /* Kill a_chain. */ | |
2483 | a_chain->release (); | |
2484 | simplified = true; | |
2485 | break; | |
2486 | } | |
2487 | } | |
927734cf XDL |
2488 | } |
2489 | /* Now clean up the chain. */ | |
2490 | if (simplified) | |
2491 | { | |
2492 | for (i = 0; i < n; i++) | |
5e48d8a0 ML |
2493 | { |
2494 | if ((*preds)[i].is_empty ()) | |
2495 | continue; | |
2496 | s_preds.safe_push ((*preds)[i]); | |
2497 | } | |
a4f0c29d | 2498 | |
3703d095 | 2499 | preds->release (); |
927734cf XDL |
2500 | (*preds) = s_preds; |
2501 | s_preds = vNULL; | |
34f97b94 XDL |
2502 | } |
2503 | ||
927734cf | 2504 | return simplified; |
34f97b94 XDL |
2505 | } |
2506 | ||
927734cf XDL |
2507 | /* This function simplifies predicates in PREDS. */ |
2508 | ||
2509 | static void | |
355fe088 | 2510 | simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use) |
34f97b94 | 2511 | { |
927734cf XDL |
2512 | size_t i, n; |
2513 | bool changed = false; | |
34f97b94 | 2514 | |
927734cf | 2515 | if (dump_file && dump_flags & TDF_DETAILS) |
34f97b94 | 2516 | { |
927734cf XDL |
2517 | fprintf (dump_file, "[BEFORE SIMPLICATION -- "); |
2518 | dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n"); | |
34f97b94 XDL |
2519 | } |
2520 | ||
927734cf XDL |
2521 | for (i = 0; i < preds->length (); i++) |
2522 | simplify_pred (&(*preds)[i]); | |
2523 | ||
2524 | n = preds->length (); | |
2525 | if (n < 2) | |
2526 | return; | |
2527 | ||
2528 | do | |
2529 | { | |
2530 | changed = false; | |
2531 | if (simplify_preds_2 (preds)) | |
5e48d8a0 | 2532 | changed = true; |
927734cf XDL |
2533 | |
2534 | /* Now iteratively simplify X OR (!X AND Z ..) | |
2535 | into X OR (Z ...). */ | |
2536 | if (simplify_preds_3 (preds)) | |
5e48d8a0 | 2537 | changed = true; |
927734cf XDL |
2538 | |
2539 | if (simplify_preds_4 (preds)) | |
5e48d8a0 | 2540 | changed = true; |
ac0e4fde ML |
2541 | } |
2542 | while (changed); | |
927734cf XDL |
2543 | |
2544 | return; | |
34f97b94 XDL |
2545 | } |
2546 | ||
927734cf | 2547 | /* This is a helper function which attempts to normalize predicate chains |
ac0e4fde | 2548 | by following UD chains. It basically builds up a big tree of either IOR |
5e48d8a0 | 2549 | operations or AND operations, and convert the IOR tree into a |
927734cf XDL |
2550 | pred_chain_union or BIT_AND tree into a pred_chain. |
2551 | Example: | |
56b67510 | 2552 | |
927734cf XDL |
2553 | _3 = _2 RELOP1 _1; |
2554 | _6 = _5 RELOP2 _4; | |
2555 | _9 = _8 RELOP3 _7; | |
2556 | _10 = _3 | _6; | |
2557 | _12 = _9 | _0; | |
2558 | _t = _10 | _12; | |
2559 | ||
2560 | then _t != 0 will be normalized into a pred_chain_union | |
2561 | ||
2562 | (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0) | |
2563 | ||
2564 | Similarly given, | |
2565 | ||
2566 | _3 = _2 RELOP1 _1; | |
2567 | _6 = _5 RELOP2 _4; | |
2568 | _9 = _8 RELOP3 _7; | |
2569 | _10 = _3 & _6; | |
2570 | _12 = _9 & _0; | |
2571 | ||
2572 | then _t != 0 will be normalized into a pred_chain: | |
2573 | (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0) | |
5e48d8a0 | 2574 | |
927734cf XDL |
2575 | */ |
2576 | ||
2577 | /* This is a helper function that stores a PRED into NORM_PREDS. */ | |
2578 | ||
2579 | inline static void | |
2580 | push_pred (pred_chain_union *norm_preds, pred_info pred) | |
56b67510 | 2581 | { |
927734cf XDL |
2582 | pred_chain pred_chain = vNULL; |
2583 | pred_chain.safe_push (pred); | |
2584 | norm_preds->safe_push (pred_chain); | |
2585 | } | |
56b67510 | 2586 | |
927734cf XDL |
2587 | /* A helper function that creates a predicate of the form |
2588 | OP != 0 and push it WORK_LIST. */ | |
56b67510 | 2589 | |
927734cf | 2590 | inline static void |
ade3ff24 | 2591 | push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list, |
5e48d8a0 | 2592 | hash_set<tree> *mark_set) |
927734cf | 2593 | { |
6e2830c3 | 2594 | if (mark_set->contains (op)) |
ade3ff24 | 2595 | return; |
6e2830c3 | 2596 | mark_set->add (op); |
ade3ff24 | 2597 | |
927734cf XDL |
2598 | pred_info arg_pred; |
2599 | arg_pred.pred_lhs = op; | |
2600 | arg_pred.pred_rhs = integer_zero_node; | |
2601 | arg_pred.cond_code = NE_EXPR; | |
2602 | arg_pred.invert = false; | |
2603 | work_list->safe_push (arg_pred); | |
2604 | } | |
56b67510 | 2605 | |
927734cf XDL |
2606 | /* A helper that generates a pred_info from a gimple assignment |
2607 | CMP_ASSIGN with comparison rhs. */ | |
56b67510 | 2608 | |
927734cf | 2609 | static pred_info |
355fe088 | 2610 | get_pred_info_from_cmp (gimple *cmp_assign) |
927734cf XDL |
2611 | { |
2612 | pred_info n_pred; | |
2613 | n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign); | |
2614 | n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign); | |
2615 | n_pred.cond_code = gimple_assign_rhs_code (cmp_assign); | |
2616 | n_pred.invert = false; | |
2617 | return n_pred; | |
56b67510 XDL |
2618 | } |
2619 | ||
927734cf | 2620 | /* Returns true if the PHI is a degenerated phi with |
ac0e4fde | 2621 | all args with the same value (relop). In that case, *PRED |
927734cf | 2622 | will be updated to that value. */ |
56b67510 XDL |
2623 | |
2624 | static bool | |
355fe088 | 2625 | is_degenerated_phi (gimple *phi, pred_info *pred_p) |
56b67510 | 2626 | { |
927734cf XDL |
2627 | int i, n; |
2628 | tree op0; | |
355fe088 | 2629 | gimple *def0; |
927734cf | 2630 | pred_info pred0; |
56b67510 | 2631 | |
927734cf XDL |
2632 | n = gimple_phi_num_args (phi); |
2633 | op0 = gimple_phi_arg_def (phi, 0); | |
2634 | ||
2635 | if (TREE_CODE (op0) != SSA_NAME) | |
56b67510 XDL |
2636 | return false; |
2637 | ||
927734cf XDL |
2638 | def0 = SSA_NAME_DEF_STMT (op0); |
2639 | if (gimple_code (def0) != GIMPLE_ASSIGN) | |
2640 | return false; | |
ac0e4fde | 2641 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison) |
927734cf XDL |
2642 | return false; |
2643 | pred0 = get_pred_info_from_cmp (def0); | |
2644 | ||
2645 | for (i = 1; i < n; ++i) | |
56b67510 | 2646 | { |
355fe088 | 2647 | gimple *def; |
927734cf XDL |
2648 | pred_info pred; |
2649 | tree op = gimple_phi_arg_def (phi, i); | |
2650 | ||
2651 | if (TREE_CODE (op) != SSA_NAME) | |
5e48d8a0 | 2652 | return false; |
56b67510 | 2653 | |
927734cf XDL |
2654 | def = SSA_NAME_DEF_STMT (op); |
2655 | if (gimple_code (def) != GIMPLE_ASSIGN) | |
5e48d8a0 | 2656 | return false; |
ac0e4fde | 2657 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison) |
5e48d8a0 | 2658 | return false; |
927734cf XDL |
2659 | pred = get_pred_info_from_cmp (def); |
2660 | if (!pred_equal_p (pred, pred0)) | |
5e48d8a0 | 2661 | return false; |
927734cf XDL |
2662 | } |
2663 | ||
2664 | *pred_p = pred0; | |
2665 | return true; | |
2666 | } | |
2667 | ||
5e48d8a0 | 2668 | /* Normalize one predicate PRED |
927734cf XDL |
2669 | 1) if PRED can no longer be normlized, put it into NORM_PREDS. |
2670 | 2) otherwise if PRED is of the form x != 0, follow x's definition | |
2671 | and put normalized predicates into WORK_LIST. */ | |
5e48d8a0 | 2672 | |
927734cf | 2673 | static void |
5e48d8a0 ML |
2674 | normalize_one_pred_1 (pred_chain_union *norm_preds, |
2675 | pred_chain *norm_chain, | |
2676 | pred_info pred, | |
2677 | enum tree_code and_or_code, | |
2678 | vec<pred_info, va_heap, vl_ptr> *work_list, | |
6e2830c3 | 2679 | hash_set<tree> *mark_set) |
927734cf XDL |
2680 | { |
2681 | if (!is_neq_zero_form_p (pred)) | |
2682 | { | |
2683 | if (and_or_code == BIT_IOR_EXPR) | |
5e48d8a0 | 2684 | push_pred (norm_preds, pred); |
927734cf | 2685 | else |
5e48d8a0 | 2686 | norm_chain->safe_push (pred); |
927734cf XDL |
2687 | return; |
2688 | } | |
2689 | ||
355fe088 | 2690 | gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); |
5e48d8a0 | 2691 | |
927734cf XDL |
2692 | if (gimple_code (def_stmt) == GIMPLE_PHI |
2693 | && is_degenerated_phi (def_stmt, &pred)) | |
2694 | work_list->safe_push (pred); | |
ac0e4fde | 2695 | else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR) |
927734cf XDL |
2696 | { |
2697 | int i, n; | |
2698 | n = gimple_phi_num_args (def_stmt); | |
2699 | ||
ac0e4fde | 2700 | /* If we see non zero constant, we should punt. The predicate |
927734cf XDL |
2701 | * should be one guarding the phi edge. */ |
2702 | for (i = 0; i < n; ++i) | |
5e48d8a0 ML |
2703 | { |
2704 | tree op = gimple_phi_arg_def (def_stmt, i); | |
2705 | if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op)) | |
2706 | { | |
2707 | push_pred (norm_preds, pred); | |
2708 | return; | |
2709 | } | |
2710 | } | |
56b67510 | 2711 | |
927734cf | 2712 | for (i = 0; i < n; ++i) |
5e48d8a0 ML |
2713 | { |
2714 | tree op = gimple_phi_arg_def (def_stmt, i); | |
2715 | if (integer_zerop (op)) | |
2716 | continue; | |
927734cf | 2717 | |
5e48d8a0 ML |
2718 | push_to_worklist (op, work_list, mark_set); |
2719 | } | |
ade3ff24 RH |
2720 | } |
2721 | else if (gimple_code (def_stmt) != GIMPLE_ASSIGN) | |
2722 | { | |
2723 | if (and_or_code == BIT_IOR_EXPR) | |
2724 | push_pred (norm_preds, pred); | |
2725 | else | |
2726 | norm_chain->safe_push (pred); | |
2727 | } | |
2728 | else if (gimple_assign_rhs_code (def_stmt) == and_or_code) | |
2729 | { | |
666e8e06 RB |
2730 | /* Avoid splitting up bit manipulations like x & 3 or y | 1. */ |
2731 | if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt))) | |
2732 | { | |
2733 | /* But treat x & 3 as condition. */ | |
2734 | if (and_or_code == BIT_AND_EXPR) | |
2735 | { | |
2736 | pred_info n_pred; | |
2737 | n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt); | |
2738 | n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt); | |
2739 | n_pred.cond_code = and_or_code; | |
2740 | n_pred.invert = false; | |
2741 | norm_chain->safe_push (n_pred); | |
2742 | } | |
2743 | } | |
2744 | else | |
2745 | { | |
2746 | push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set); | |
2747 | push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set); | |
2748 | } | |
ade3ff24 RH |
2749 | } |
2750 | else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) | |
2751 | == tcc_comparison) | |
2752 | { | |
2753 | pred_info n_pred = get_pred_info_from_cmp (def_stmt); | |
2754 | if (and_or_code == BIT_IOR_EXPR) | |
2755 | push_pred (norm_preds, n_pred); | |
2756 | else | |
2757 | norm_chain->safe_push (n_pred); | |
2758 | } | |
2759 | else | |
2760 | { | |
2761 | if (and_or_code == BIT_IOR_EXPR) | |
2762 | push_pred (norm_preds, pred); | |
2763 | else | |
2764 | norm_chain->safe_push (pred); | |
2765 | } | |
927734cf XDL |
2766 | } |
2767 | ||
2768 | /* Normalize PRED and store the normalized predicates into NORM_PREDS. */ | |
2769 | ||
2770 | static void | |
ac0e4fde | 2771 | normalize_one_pred (pred_chain_union *norm_preds, pred_info pred) |
927734cf XDL |
2772 | { |
2773 | vec<pred_info, va_heap, vl_ptr> work_list = vNULL; | |
2774 | enum tree_code and_or_code = ERROR_MARK; | |
2775 | pred_chain norm_chain = vNULL; | |
56b67510 | 2776 | |
927734cf | 2777 | if (!is_neq_zero_form_p (pred)) |
56b67510 | 2778 | { |
927734cf XDL |
2779 | push_pred (norm_preds, pred); |
2780 | return; | |
2781 | } | |
56b67510 | 2782 | |
355fe088 | 2783 | gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); |
927734cf XDL |
2784 | if (gimple_code (def_stmt) == GIMPLE_ASSIGN) |
2785 | and_or_code = gimple_assign_rhs_code (def_stmt); | |
ac0e4fde | 2786 | if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR) |
927734cf | 2787 | { |
ac0e4fde | 2788 | if (TREE_CODE_CLASS (and_or_code) == tcc_comparison) |
5e48d8a0 ML |
2789 | { |
2790 | pred_info n_pred = get_pred_info_from_cmp (def_stmt); | |
2791 | push_pred (norm_preds, n_pred); | |
2792 | } | |
ac0e4fde ML |
2793 | else |
2794 | push_pred (norm_preds, pred); | |
927734cf XDL |
2795 | return; |
2796 | } | |
56b67510 | 2797 | |
927734cf | 2798 | work_list.safe_push (pred); |
6e2830c3 | 2799 | hash_set<tree> mark_set; |
ade3ff24 | 2800 | |
927734cf XDL |
2801 | while (!work_list.is_empty ()) |
2802 | { | |
2803 | pred_info a_pred = work_list.pop (); | |
ac0e4fde ML |
2804 | normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code, |
2805 | &work_list, &mark_set); | |
56b67510 | 2806 | } |
927734cf XDL |
2807 | if (and_or_code == BIT_AND_EXPR) |
2808 | norm_preds->safe_push (norm_chain); | |
2809 | ||
2810 | work_list.release (); | |
2811 | } | |
56b67510 | 2812 | |
927734cf | 2813 | static void |
ac0e4fde | 2814 | normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain) |
927734cf XDL |
2815 | { |
2816 | vec<pred_info, va_heap, vl_ptr> work_list = vNULL; | |
6e2830c3 | 2817 | hash_set<tree> mark_set; |
927734cf XDL |
2818 | pred_chain norm_chain = vNULL; |
2819 | size_t i; | |
2820 | ||
2821 | for (i = 0; i < one_chain.length (); i++) | |
ade3ff24 RH |
2822 | { |
2823 | work_list.safe_push (one_chain[i]); | |
6e2830c3 | 2824 | mark_set.add (one_chain[i].pred_lhs); |
ade3ff24 | 2825 | } |
927734cf XDL |
2826 | |
2827 | while (!work_list.is_empty ()) | |
56b67510 | 2828 | { |
927734cf | 2829 | pred_info a_pred = work_list.pop (); |
ac0e4fde ML |
2830 | normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list, |
2831 | &mark_set); | |
56b67510 | 2832 | } |
927734cf XDL |
2833 | |
2834 | norm_preds->safe_push (norm_chain); | |
2835 | work_list.release (); | |
56b67510 XDL |
2836 | } |
2837 | ||
927734cf XDL |
2838 | /* Normalize predicate chains PREDS and returns the normalized one. */ |
2839 | ||
2840 | static pred_chain_union | |
355fe088 | 2841 | normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use) |
927734cf XDL |
2842 | { |
2843 | pred_chain_union norm_preds = vNULL; | |
2844 | size_t n = preds.length (); | |
2845 | size_t i; | |
2846 | ||
2847 | if (dump_file && dump_flags & TDF_DETAILS) | |
2848 | { | |
2849 | fprintf (dump_file, "[BEFORE NORMALIZATION --"); | |
2850 | dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n"); | |
2851 | } | |
2852 | ||
2853 | for (i = 0; i < n; i++) | |
2854 | { | |
2855 | if (preds[i].length () != 1) | |
5e48d8a0 | 2856 | normalize_one_pred_chain (&norm_preds, preds[i]); |
927734cf | 2857 | else |
5e48d8a0 ML |
2858 | { |
2859 | normalize_one_pred (&norm_preds, preds[i][0]); | |
2860 | preds[i].release (); | |
2861 | } | |
927734cf XDL |
2862 | } |
2863 | ||
2864 | if (dump_file) | |
2865 | { | |
2866 | fprintf (dump_file, "[AFTER NORMALIZATION -- "); | |
ac0e4fde ML |
2867 | dump_predicates (use_or_def, norm_preds, |
2868 | is_use ? "[USE]:\n" : "[DEF]:\n"); | |
927734cf XDL |
2869 | } |
2870 | ||
a4f0c29d | 2871 | destroy_predicate_vecs (&preds); |
927734cf XDL |
2872 | return norm_preds; |
2873 | } | |
56b67510 | 2874 | |
358a95e4 | 2875 | /* Return TRUE if PREDICATE can be invalidated by any individual |
11ef0b22 | 2876 | predicate in USE_GUARD. */ |
358a95e4 AH |
2877 | |
2878 | static bool | |
2879 | can_one_predicate_be_invalidated_p (pred_info predicate, | |
95ac78ce | 2880 | pred_chain use_guard) |
358a95e4 | 2881 | { |
11ef0b22 AH |
2882 | if (dump_file && dump_flags & TDF_DETAILS) |
2883 | { | |
2884 | fprintf (dump_file, "Testing if this predicate: "); | |
2885 | dump_pred_info (predicate); | |
2886 | fprintf (dump_file, "\n...can be invalidated by a USE guard of: "); | |
2887 | dump_pred_chain (use_guard); | |
2888 | } | |
95ac78ce | 2889 | for (size_t i = 0; i < use_guard.length (); ++i) |
358a95e4 | 2890 | { |
358a95e4 AH |
2891 | /* NOTE: This is a very simple check, and only understands an |
2892 | exact opposite. So, [i == 0] is currently only invalidated | |
2893 | by [.NOT. i == 0] or [i != 0]. Ideally we should also | |
2894 | invalidate with say [i > 5] or [i == 8]. There is certainly | |
2895 | room for improvement here. */ | |
95ac78ce | 2896 | if (pred_neg_p (predicate, use_guard[i])) |
11ef0b22 AH |
2897 | { |
2898 | if (dump_file && dump_flags & TDF_DETAILS) | |
2899 | { | |
2900 | fprintf (dump_file, " Predicate was invalidated by: "); | |
2901 | dump_pred_info (use_guard[i]); | |
2902 | fputc ('\n', dump_file); | |
2903 | } | |
2904 | return true; | |
2905 | } | |
358a95e4 AH |
2906 | } |
2907 | return false; | |
2908 | } | |
2909 | ||
95ac78ce AH |
2910 | /* Return TRUE if all predicates in UNINIT_PRED are invalidated by |
2911 | USE_GUARD being true. */ | |
358a95e4 AH |
2912 | |
2913 | static bool | |
95ac78ce AH |
2914 | can_chain_union_be_invalidated_p (pred_chain_union uninit_pred, |
2915 | pred_chain use_guard) | |
358a95e4 | 2916 | { |
95ac78ce AH |
2917 | if (uninit_pred.is_empty ()) |
2918 | return false; | |
11ef0b22 AH |
2919 | if (dump_file && dump_flags & TDF_DETAILS) |
2920 | dump_predicates (NULL, uninit_pred, | |
2921 | "Testing if anything here can be invalidated: "); | |
95ac78ce | 2922 | for (size_t i = 0; i < uninit_pred.length (); ++i) |
358a95e4 | 2923 | { |
95ac78ce | 2924 | pred_chain c = uninit_pred[i]; |
11ef0b22 AH |
2925 | size_t j; |
2926 | for (j = 0; j < c.length (); ++j) | |
2927 | if (can_one_predicate_be_invalidated_p (c[j], use_guard)) | |
2928 | break; | |
2929 | ||
2930 | /* If we were unable to invalidate any predicate in C, then there | |
2931 | is a viable path from entry to the PHI where the PHI takes | |
2932 | an uninitialized value and continues to a use of the PHI. */ | |
2933 | if (j == c.length ()) | |
2934 | return false; | |
358a95e4 AH |
2935 | } |
2936 | return true; | |
2937 | } | |
2938 | ||
95ac78ce AH |
2939 | /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS |
2940 | can actually happen if we arrived at a use for PHI. | |
358a95e4 | 2941 | |
95ac78ce | 2942 | PHI_USE_GUARDS are the guard conditions for the use of the PHI. */ |
358a95e4 | 2943 | |
95ac78ce AH |
2944 | static bool |
2945 | uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds, | |
2946 | pred_chain_union phi_use_guards) | |
358a95e4 | 2947 | { |
95ac78ce AH |
2948 | unsigned phi_args = gimple_phi_num_args (phi); |
2949 | if (phi_args > max_phi_args) | |
2950 | return false; | |
358a95e4 | 2951 | |
95ac78ce AH |
2952 | /* PHI_USE_GUARDS are OR'ed together. If we have more than one |
2953 | possible guard, there's no way of knowing which guard was true. | |
2954 | Since we need to be absolutely sure that the uninitialized | |
2955 | operands will be invalidated, bail. */ | |
2956 | if (phi_use_guards.length () != 1) | |
2957 | return false; | |
358a95e4 | 2958 | |
358a95e4 | 2959 | /* Look for the control dependencies of all the uninitialized |
95ac78ce | 2960 | operands and build guard predicates describing them. */ |
3703d095 AH |
2961 | pred_chain_union uninit_preds; |
2962 | bool ret = true; | |
2963 | for (unsigned i = 0; i < phi_args; ++i) | |
358a95e4 AH |
2964 | { |
2965 | if (!MASK_TEST_BIT (uninit_opnds, i)) | |
2966 | continue; | |
2967 | ||
2968 | edge e = gimple_phi_arg_edge (phi, i); | |
2969 | vec<edge> dep_chains[MAX_NUM_CHAINS]; | |
2970 | auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; | |
2971 | size_t num_chains = 0; | |
2972 | int num_calls = 0; | |
2973 | ||
95ac78ce | 2974 | /* Build the control dependency chain for uninit operand `i'... */ |
3703d095 | 2975 | uninit_preds = vNULL; |
11ef0b22 | 2976 | if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun), |
95ac78ce AH |
2977 | e->src, dep_chains, &num_chains, |
2978 | &cur_chain, &num_calls)) | |
3703d095 AH |
2979 | { |
2980 | ret = false; | |
2981 | break; | |
2982 | } | |
95ac78ce | 2983 | /* ...and convert it into a set of predicates. */ |
11ef0b22 AH |
2984 | bool has_valid_preds |
2985 | = convert_control_dep_chain_into_preds (dep_chains, num_chains, | |
2986 | &uninit_preds); | |
95ac78ce AH |
2987 | for (size_t j = 0; j < num_chains; ++j) |
2988 | dep_chains[j].release (); | |
11ef0b22 AH |
2989 | if (!has_valid_preds) |
2990 | { | |
2991 | ret = false; | |
2992 | break; | |
2993 | } | |
3703d095 AH |
2994 | simplify_preds (&uninit_preds, NULL, false); |
2995 | uninit_preds = normalize_preds (uninit_preds, NULL, false); | |
95ac78ce AH |
2996 | |
2997 | /* Can the guard for this uninitialized operand be invalidated | |
2998 | by the PHI use? */ | |
3703d095 AH |
2999 | if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0])) |
3000 | { | |
3001 | ret = false; | |
3002 | break; | |
3003 | } | |
358a95e4 | 3004 | } |
3703d095 AH |
3005 | destroy_predicate_vecs (&uninit_preds); |
3006 | return ret; | |
358a95e4 AH |
3007 | } |
3008 | ||
34f97b94 XDL |
3009 | /* Computes the predicates that guard the use and checks |
3010 | if the incoming paths that have empty (or possibly | |
ac0e4fde | 3011 | empty) definition can be pruned/filtered. The function returns |
34f97b94 XDL |
3012 | true if it can be determined that the use of PHI's def in |
3013 | USE_STMT is guarded with a predicate set not overlapping with | |
3014 | predicate sets of all runtime paths that do not have a definition. | |
c0503346 | 3015 | |
67914693 | 3016 | Returns false if it is not or it cannot be determined. USE_BB is |
34f97b94 | 3017 | the bb of the use (for phi operand use, the bb is not the bb of |
c0503346 PP |
3018 | the phi stmt, but the src bb of the operand edge). |
3019 | ||
ac0e4fde | 3020 | UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the |
c0503346 PP |
3021 | corresponding bit in the vector is 1. VISITED_PHIS is a pointer |
3022 | set of phis being visited. | |
3023 | ||
3024 | *DEF_PREDS contains the (memoized) defining predicate chains of PHI. | |
3025 | If *DEF_PREDS is the empty vector, the defining predicate chains of | |
3026 | PHI will be computed and stored into *DEF_PREDS as needed. | |
3027 | ||
3028 | VISITED_PHIS is a pointer set of phis being visited. */ | |
34f97b94 XDL |
3029 | |
3030 | static bool | |
355fe088 | 3031 | is_use_properly_guarded (gimple *use_stmt, |
5e48d8a0 ML |
3032 | basic_block use_bb, |
3033 | gphi *phi, | |
3034 | unsigned uninit_opnds, | |
c0503346 | 3035 | pred_chain_union *def_preds, |
5e48d8a0 | 3036 | hash_set<gphi *> *visited_phis) |
34f97b94 XDL |
3037 | { |
3038 | basic_block phi_bb; | |
927734cf | 3039 | pred_chain_union preds = vNULL; |
34f97b94 XDL |
3040 | bool has_valid_preds = false; |
3041 | bool is_properly_guarded = false; | |
3042 | ||
6e2830c3 | 3043 | if (visited_phis->add (phi)) |
34f97b94 XDL |
3044 | return false; |
3045 | ||
3046 | phi_bb = gimple_bb (phi); | |
3047 | ||
3048 | if (is_non_loop_exit_postdominating (use_bb, phi_bb)) | |
3049 | return false; | |
3050 | ||
927734cf | 3051 | has_valid_preds = find_predicates (&preds, phi_bb, use_bb); |
34f97b94 XDL |
3052 | |
3053 | if (!has_valid_preds) | |
3054 | { | |
a4f0c29d | 3055 | destroy_predicate_vecs (&preds); |
34f97b94 XDL |
3056 | return false; |
3057 | } | |
3058 | ||
ac0e4fde | 3059 | /* Try to prune the dead incoming phi edges. */ |
927734cf XDL |
3060 | is_properly_guarded |
3061 | = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds, | |
3062 | visited_phis); | |
34f97b94 | 3063 | |
358a95e4 AH |
3064 | /* We might be able to prove that if the control dependencies |
3065 | for UNINIT_OPNDS are true, that the control dependencies for | |
3066 | USE_STMT can never be true. */ | |
3067 | if (!is_properly_guarded) | |
95ac78ce AH |
3068 | is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds, |
3069 | preds); | |
358a95e4 | 3070 | |
927734cf | 3071 | if (is_properly_guarded) |
34f97b94 | 3072 | { |
a4f0c29d | 3073 | destroy_predicate_vecs (&preds); |
927734cf XDL |
3074 | return true; |
3075 | } | |
56b67510 | 3076 | |
c0503346 | 3077 | if (def_preds->is_empty ()) |
927734cf | 3078 | { |
c0503346 PP |
3079 | has_valid_preds = find_def_preds (def_preds, phi); |
3080 | ||
3081 | if (!has_valid_preds) | |
3082 | { | |
a4f0c29d | 3083 | destroy_predicate_vecs (&preds); |
c0503346 PP |
3084 | return false; |
3085 | } | |
3086 | ||
3087 | simplify_preds (def_preds, phi, false); | |
3088 | *def_preds = normalize_preds (*def_preds, phi, false); | |
34f97b94 XDL |
3089 | } |
3090 | ||
927734cf XDL |
3091 | simplify_preds (&preds, use_stmt, true); |
3092 | preds = normalize_preds (preds, use_stmt, true); | |
3093 | ||
c0503346 | 3094 | is_properly_guarded = is_superset_of (*def_preds, preds); |
34f97b94 | 3095 | |
a4f0c29d | 3096 | destroy_predicate_vecs (&preds); |
34f97b94 XDL |
3097 | return is_properly_guarded; |
3098 | } | |
3099 | ||
3100 | /* Searches through all uses of a potentially | |
3101 | uninitialized variable defined by PHI and returns a use | |
ac0e4fde ML |
3102 | statement if the use is not properly guarded. It returns |
3103 | NULL if all uses are guarded. UNINIT_OPNDS is a bitvector | |
3104 | holding the position(s) of uninit PHI operands. WORKLIST | |
34f97b94 | 3105 | is the vector of candidate phis that may be updated by this |
ac0e4fde | 3106 | function. ADDED_TO_WORKLIST is the pointer set tracking |
34f97b94 XDL |
3107 | if the new phi is already in the worklist. */ |
3108 | ||
355fe088 | 3109 | static gimple * |
538dd0b7 | 3110 | find_uninit_use (gphi *phi, unsigned uninit_opnds, |
5e48d8a0 | 3111 | vec<gphi *> *worklist, |
538dd0b7 | 3112 | hash_set<gphi *> *added_to_worklist) |
34f97b94 XDL |
3113 | { |
3114 | tree phi_result; | |
3115 | use_operand_p use_p; | |
355fe088 | 3116 | gimple *use_stmt; |
34f97b94 | 3117 | imm_use_iterator iter; |
c0503346 | 3118 | pred_chain_union def_preds = vNULL; |
355fe088 | 3119 | gimple *ret = NULL; |
34f97b94 XDL |
3120 | |
3121 | phi_result = gimple_phi_result (phi); | |
3122 | ||
3123 | FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result) | |
3124 | { | |
34f97b94 XDL |
3125 | basic_block use_bb; |
3126 | ||
480161b5 RG |
3127 | use_stmt = USE_STMT (use_p); |
3128 | if (is_gimple_debug (use_stmt)) | |
3129 | continue; | |
34f97b94 | 3130 | |
ac0e4fde | 3131 | if (gphi *use_phi = dyn_cast<gphi *> (use_stmt)) |
538dd0b7 | 3132 | use_bb = gimple_phi_arg_edge (use_phi, |
480161b5 RG |
3133 | PHI_ARG_INDEX_FROM_USE (use_p))->src; |
3134 | else | |
3135 | use_bb = gimple_bb (use_stmt); | |
34f97b94 | 3136 | |
538dd0b7 | 3137 | hash_set<gphi *> visited_phis; |
927734cf | 3138 | if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds, |
c0503346 | 3139 | &def_preds, &visited_phis)) |
6e2830c3 | 3140 | continue; |
34f97b94 | 3141 | |
e74780a3 | 3142 | if (dump_file && (dump_flags & TDF_DETAILS)) |
5e48d8a0 ML |
3143 | { |
3144 | fprintf (dump_file, "[CHECK]: Found unguarded use: "); | |
ef6cb4c7 | 3145 | print_gimple_stmt (dump_file, use_stmt, 0); |
5e48d8a0 | 3146 | } |
34f97b94 XDL |
3147 | /* Found one real use, return. */ |
3148 | if (gimple_code (use_stmt) != GIMPLE_PHI) | |
c0503346 PP |
3149 | { |
3150 | ret = use_stmt; | |
3151 | break; | |
3152 | } | |
34f97b94 XDL |
3153 | |
3154 | /* Found a phi use that is not guarded, | |
5e48d8a0 | 3155 | add the phi to the worklist. */ |
ac0e4fde | 3156 | if (!added_to_worklist->add (as_a<gphi *> (use_stmt))) |
5e48d8a0 ML |
3157 | { |
3158 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3159 | { | |
3160 | fprintf (dump_file, "[WORKLIST]: Update worklist with phi: "); | |
ef6cb4c7 | 3161 | print_gimple_stmt (dump_file, use_stmt, 0); |
5e48d8a0 ML |
3162 | } |
3163 | ||
ac0e4fde | 3164 | worklist->safe_push (as_a<gphi *> (use_stmt)); |
5e48d8a0 ML |
3165 | possibly_undefined_names->add (phi_result); |
3166 | } | |
34f97b94 XDL |
3167 | } |
3168 | ||
a4f0c29d | 3169 | destroy_predicate_vecs (&def_preds); |
c0503346 | 3170 | return ret; |
34f97b94 XDL |
3171 | } |
3172 | ||
3173 | /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions | |
3174 | and gives warning if there exists a runtime path from the entry to a | |
ac0e4fde ML |
3175 | use of the PHI def that does not contain a definition. In other words, |
3176 | the warning is on the real use. The more dead paths that can be pruned | |
3177 | by the compiler, the fewer false positives the warning is. WORKLIST | |
3178 | is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is | |
34f97b94 XDL |
3179 | a pointer set tracking if the new phi is added to the worklist or not. */ |
3180 | ||
3181 | static void | |
538dd0b7 | 3182 | warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist, |
5e48d8a0 | 3183 | hash_set<gphi *> *added_to_worklist) |
34f97b94 | 3184 | { |
ea057359 RG |
3185 | /* Don't look at virtual operands. */ |
3186 | if (virtual_operand_p (gimple_phi_result (phi))) | |
34f97b94 XDL |
3187 | return; |
3188 | ||
4e84e381 | 3189 | unsigned uninit_opnds = compute_uninit_opnds_pos (phi); |
ac0e4fde | 3190 | if (MASK_EMPTY (uninit_opnds)) |
34f97b94 XDL |
3191 | return; |
3192 | ||
e74780a3 XDL |
3193 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3194 | { | |
3195 | fprintf (dump_file, "[CHECK]: examining phi: "); | |
ef6cb4c7 | 3196 | print_gimple_stmt (dump_file, phi, 0); |
e74780a3 XDL |
3197 | } |
3198 | ||
34f97b94 | 3199 | /* Now check if we have any use of the value without proper guard. */ |
4e84e381 MS |
3200 | gimple *uninit_use_stmt = find_uninit_use (phi, uninit_opnds, |
3201 | worklist, added_to_worklist); | |
34f97b94 XDL |
3202 | |
3203 | /* All uses are properly guarded. */ | |
3204 | if (!uninit_use_stmt) | |
3205 | return; | |
3206 | ||
4e84e381 MS |
3207 | int phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds); |
3208 | tree uninit_op = gimple_phi_arg_def (phi, phiarg_index); | |
70b5e7dc RG |
3209 | if (SSA_NAME_VAR (uninit_op) == NULL_TREE) |
3210 | return; | |
4e84e381 MS |
3211 | |
3212 | location_t phi_arg_loc = gimple_phi_arg_location (phi, phiarg_index); | |
3213 | warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, | |
8d2b0410 | 3214 | SSA_NAME_VAR (uninit_op), |
5e48d8a0 | 3215 | "%qD may be used uninitialized in this function", |
4e84e381 | 3216 | uninit_use_stmt, phi_arg_loc); |
34f97b94 XDL |
3217 | } |
3218 | ||
be55bfe6 TS |
3219 | static bool |
3220 | gate_warn_uninitialized (void) | |
3221 | { | |
3222 | return warn_uninitialized || warn_maybe_uninitialized; | |
3223 | } | |
34f97b94 | 3224 | |
be55bfe6 | 3225 | namespace { |
34f97b94 | 3226 | |
be55bfe6 TS |
3227 | const pass_data pass_data_late_warn_uninitialized = |
3228 | { | |
3229 | GIMPLE_PASS, /* type */ | |
3230 | "uninit", /* name */ | |
3231 | OPTGROUP_NONE, /* optinfo_flags */ | |
be55bfe6 TS |
3232 | TV_NONE, /* tv_id */ |
3233 | PROP_ssa, /* properties_required */ | |
3234 | 0, /* properties_provided */ | |
3235 | 0, /* properties_destroyed */ | |
3236 | 0, /* todo_flags_start */ | |
3237 | 0, /* todo_flags_finish */ | |
3238 | }; | |
3239 | ||
3240 | class pass_late_warn_uninitialized : public gimple_opt_pass | |
3241 | { | |
3242 | public: | |
3243 | pass_late_warn_uninitialized (gcc::context *ctxt) | |
3244 | : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt) | |
3245 | {} | |
3246 | ||
3247 | /* opt_pass methods: */ | |
ac0e4fde | 3248 | opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); } |
be55bfe6 TS |
3249 | virtual bool gate (function *) { return gate_warn_uninitialized (); } |
3250 | virtual unsigned int execute (function *); | |
3251 | ||
3252 | }; // class pass_late_warn_uninitialized | |
3253 | ||
3254 | unsigned int | |
3255 | pass_late_warn_uninitialized::execute (function *fun) | |
34f97b94 XDL |
3256 | { |
3257 | basic_block bb; | |
538dd0b7 DM |
3258 | gphi_iterator gsi; |
3259 | vec<gphi *> worklist = vNULL; | |
34f97b94 XDL |
3260 | |
3261 | calculate_dominance_info (CDI_DOMINATORS); | |
3262 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
3263 | /* Re-do the plain uninitialized variable check, as optimization may have | |
3264 | straightened control flow. Do this first so that we don't accidentally | |
3265 | get a "may be" warning when we'd have seen an "is" warning later. */ | |
b825a228 | 3266 | warn_uninitialized_vars (/*warn_maybe_uninitialized=*/1); |
34f97b94 XDL |
3267 | |
3268 | timevar_push (TV_TREE_UNINIT); | |
3269 | ||
6e2830c3 | 3270 | possibly_undefined_names = new hash_set<tree>; |
538dd0b7 | 3271 | hash_set<gphi *> added_to_worklist; |
34f97b94 XDL |
3272 | |
3273 | /* Initialize worklist */ | |
be55bfe6 | 3274 | FOR_EACH_BB_FN (bb, fun) |
34f97b94 XDL |
3275 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
3276 | { | |
538dd0b7 | 3277 | gphi *phi = gsi.phi (); |
be55bfe6 TS |
3278 | size_t n, i; |
3279 | ||
3280 | n = gimple_phi_num_args (phi); | |
3281 | ||
3282 | /* Don't look at virtual operands. */ | |
3283 | if (virtual_operand_p (gimple_phi_result (phi))) | |
3284 | continue; | |
3285 | ||
3286 | for (i = 0; i < n; ++i) | |
3287 | { | |
3288 | tree op = gimple_phi_arg_def (phi, i); | |
ac0e4fde | 3289 | if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op)) |
be55bfe6 TS |
3290 | { |
3291 | worklist.safe_push (phi); | |
6e2830c3 | 3292 | added_to_worklist.add (phi); |
be55bfe6 TS |
3293 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3294 | { | |
3295 | fprintf (dump_file, "[WORKLIST]: add to initial list: "); | |
ef6cb4c7 | 3296 | print_gimple_stmt (dump_file, phi, 0); |
be55bfe6 TS |
3297 | } |
3298 | break; | |
3299 | } | |
3300 | } | |
34f97b94 XDL |
3301 | } |
3302 | ||
9771b263 | 3303 | while (worklist.length () != 0) |
34f97b94 | 3304 | { |
538dd0b7 | 3305 | gphi *cur_phi = 0; |
9771b263 | 3306 | cur_phi = worklist.pop (); |
6e2830c3 | 3307 | warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist); |
34f97b94 | 3308 | } |
e74780a3 | 3309 | |
9771b263 | 3310 | worklist.release (); |
6e2830c3 | 3311 | delete possibly_undefined_names; |
34f97b94 XDL |
3312 | possibly_undefined_names = NULL; |
3313 | free_dominance_info (CDI_POST_DOMINATORS); | |
3314 | timevar_pop (TV_TREE_UNINIT); | |
3315 | return 0; | |
3316 | } | |
3317 | ||
27a4cd48 DM |
3318 | } // anon namespace |
3319 | ||
3320 | gimple_opt_pass * | |
3321 | make_pass_late_warn_uninitialized (gcc::context *ctxt) | |
3322 | { | |
3323 | return new pass_late_warn_uninitialized (ctxt); | |
3324 | } | |
c152901f | 3325 | |
c152901f AM |
3326 | static unsigned int |
3327 | execute_early_warn_uninitialized (void) | |
3328 | { | |
3329 | /* Currently, this pass runs always but | |
ac0e4fde | 3330 | execute_late_warn_uninitialized only runs with optimization. With |
c152901f AM |
3331 | optimization we want to warn about possible uninitialized as late |
3332 | as possible, thus don't do it here. However, without | |
927734cf | 3333 | optimization we need to warn here about "may be uninitialized". */ |
66030d68 | 3334 | calculate_dominance_info (CDI_DOMINATORS); |
c152901f AM |
3335 | calculate_dominance_info (CDI_POST_DOMINATORS); |
3336 | ||
b825a228 | 3337 | warn_uninitialized_vars (/*warn_maybe_uninitialized=*/!optimize); |
c152901f | 3338 | |
67914693 | 3339 | /* Post-dominator information cannot be reliably updated. Free it |
c152901f AM |
3340 | after the use. */ |
3341 | ||
3342 | free_dominance_info (CDI_POST_DOMINATORS); | |
3343 | return 0; | |
3344 | } | |
3345 | ||
c152901f AM |
3346 | namespace { |
3347 | ||
3348 | const pass_data pass_data_early_warn_uninitialized = | |
3349 | { | |
3350 | GIMPLE_PASS, /* type */ | |
3351 | "*early_warn_uninitialized", /* name */ | |
3352 | OPTGROUP_NONE, /* optinfo_flags */ | |
c152901f AM |
3353 | TV_TREE_UNINIT, /* tv_id */ |
3354 | PROP_ssa, /* properties_required */ | |
3355 | 0, /* properties_provided */ | |
3356 | 0, /* properties_destroyed */ | |
3357 | 0, /* todo_flags_start */ | |
3358 | 0, /* todo_flags_finish */ | |
3359 | }; | |
3360 | ||
3361 | class pass_early_warn_uninitialized : public gimple_opt_pass | |
3362 | { | |
3363 | public: | |
c3284718 RS |
3364 | pass_early_warn_uninitialized (gcc::context *ctxt) |
3365 | : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt) | |
c152901f AM |
3366 | {} |
3367 | ||
3368 | /* opt_pass methods: */ | |
1a3d085c | 3369 | virtual bool gate (function *) { return gate_warn_uninitialized (); } |
be55bfe6 | 3370 | virtual unsigned int execute (function *) |
ac0e4fde ML |
3371 | { |
3372 | return execute_early_warn_uninitialized (); | |
3373 | } | |
c152901f AM |
3374 | |
3375 | }; // class pass_early_warn_uninitialized | |
3376 | ||
3377 | } // anon namespace | |
3378 | ||
3379 | gimple_opt_pass * | |
3380 | make_pass_early_warn_uninitialized (gcc::context *ctxt) | |
3381 | { | |
3382 | return new pass_early_warn_uninitialized (ctxt); | |
3383 | } |