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