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