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