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