]>
Commit | Line | Data |
---|---|---|
34f97b94 | 1 | /* Predicate aware uninitialized variable warning. |
d1e082c2 | 2 | Copyright (C) 2001-2013 Free Software Foundation, Inc. |
34f97b94 XDL |
3 | Contributed by Xinliang David Li <davidxl@google.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "flags.h" | |
34f97b94 | 27 | #include "tm_p.h" |
34f97b94 | 28 | #include "basic-block.h" |
34f97b94 | 29 | #include "function.h" |
cf835838 | 30 | #include "gimple-pretty-print.h" |
34f97b94 XDL |
31 | #include "bitmap.h" |
32 | #include "pointer-set.h" | |
33 | #include "tree-flow.h" | |
34 | #include "gimple.h" | |
35 | #include "tree-inline.h" | |
34f97b94 | 36 | #include "hashtab.h" |
34f97b94 | 37 | #include "tree-pass.h" |
718f9c0f | 38 | #include "diagnostic-core.h" |
34f97b94 XDL |
39 | |
40 | /* This implements the pass that does predicate aware warning on uses of | |
41 | possibly uninitialized variables. The pass first collects the set of | |
42 | possibly uninitialized SSA names. For each such name, it walks through | |
43 | all its immediate uses. For each immediate use, it rebuilds the condition | |
44 | expression (the predicate) that guards the use. The predicate is then | |
45 | examined to see if the variable is always defined under that same condition. | |
46 | This is done either by pruning the unrealizable paths that lead to the | |
47 | default definitions or by checking if the predicate set that guards the | |
48 | defining paths is a superset of the use predicate. */ | |
49 | ||
50 | ||
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. */ | |
54 | static struct pointer_set_t *possibly_undefined_names = 0; | |
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) | |
62 | in mask that is non zero. Returns -1 if the mask is empty. */ | |
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 | ||
77 | ||
78 | /* Return true if T, an SSA_NAME, has an undefined value. */ | |
79 | ||
80 | bool | |
81 | ssa_undefined_value_p (tree t) | |
82 | { | |
83 | tree var = SSA_NAME_VAR (t); | |
84 | ||
70b5e7dc RG |
85 | if (!var) |
86 | ; | |
34f97b94 | 87 | /* Parameters get their initial value from the function entry. */ |
70b5e7dc | 88 | else if (TREE_CODE (var) == PARM_DECL) |
34f97b94 | 89 | return false; |
6938f93f JH |
90 | /* When returning by reference the return address is actually a hidden |
91 | parameter. */ | |
70b5e7dc | 92 | else if (TREE_CODE (var) == RESULT_DECL && DECL_BY_REFERENCE (var)) |
6938f93f | 93 | return false; |
34f97b94 | 94 | /* Hard register variables get their initial value from the ether. */ |
70b5e7dc | 95 | else if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) |
34f97b94 XDL |
96 | return false; |
97 | ||
98 | /* The value is undefined iff its definition statement is empty. */ | |
99 | return (gimple_nop_p (SSA_NAME_DEF_STMT (t)) | |
100 | || (possibly_undefined_names | |
101 | && pointer_set_contains (possibly_undefined_names, t))); | |
102 | } | |
103 | ||
ba7e83f8 JJ |
104 | /* Like ssa_undefined_value_p, but don't return true if TREE_NO_WARNING |
105 | is set on SSA_NAME_VAR. */ | |
106 | ||
107 | static inline bool | |
108 | uninit_undefined_value_p (tree t) | |
109 | { | |
110 | if (!ssa_undefined_value_p (t)) | |
111 | return false; | |
112 | if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t))) | |
113 | return false; | |
114 | return true; | |
115 | } | |
116 | ||
34f97b94 XDL |
117 | /* Checks if the operand OPND of PHI is defined by |
118 | another phi with one operand defined by this PHI, | |
119 | but the rest operands are all defined. If yes, | |
120 | returns true to skip this this operand as being | |
121 | redundant. Can be enhanced to be more general. */ | |
122 | ||
123 | static bool | |
124 | can_skip_redundant_opnd (tree opnd, gimple phi) | |
125 | { | |
126 | gimple op_def; | |
127 | tree phi_def; | |
128 | int i, n; | |
129 | ||
130 | phi_def = gimple_phi_result (phi); | |
131 | op_def = SSA_NAME_DEF_STMT (opnd); | |
132 | if (gimple_code (op_def) != GIMPLE_PHI) | |
133 | return false; | |
134 | n = gimple_phi_num_args (op_def); | |
135 | for (i = 0; i < n; ++i) | |
136 | { | |
137 | tree op = gimple_phi_arg_def (op_def, i); | |
138 | if (TREE_CODE (op) != SSA_NAME) | |
139 | continue; | |
ba7e83f8 | 140 | if (op != phi_def && uninit_undefined_value_p (op)) |
34f97b94 XDL |
141 | return false; |
142 | } | |
143 | ||
144 | return true; | |
145 | } | |
146 | ||
147 | /* Returns a bit mask holding the positions of arguments in PHI | |
148 | that have empty (or possibly empty) definitions. */ | |
149 | ||
150 | static unsigned | |
151 | compute_uninit_opnds_pos (gimple phi) | |
152 | { | |
153 | size_t i, n; | |
154 | unsigned uninit_opnds = 0; | |
155 | ||
156 | n = gimple_phi_num_args (phi); | |
98d30e4f XDL |
157 | /* Bail out for phi with too many args. */ |
158 | if (n > 32) | |
159 | return 0; | |
34f97b94 XDL |
160 | |
161 | for (i = 0; i < n; ++i) | |
162 | { | |
163 | tree op = gimple_phi_arg_def (phi, i); | |
164 | if (TREE_CODE (op) == SSA_NAME | |
ba7e83f8 | 165 | && uninit_undefined_value_p (op) |
34f97b94 | 166 | && !can_skip_redundant_opnd (op, phi)) |
e7d764f3 | 167 | { |
e7d764f3 JJ |
168 | if (cfun->has_nonlocal_label || cfun->calls_setjmp) |
169 | { | |
aea0101d RB |
170 | /* Ignore SSA_NAMEs that appear on abnormal edges |
171 | somewhere. */ | |
172 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) | |
173 | continue; | |
e7d764f3 JJ |
174 | } |
175 | MASK_SET_BIT (uninit_opnds, i); | |
176 | } | |
34f97b94 XDL |
177 | } |
178 | return uninit_opnds; | |
179 | } | |
180 | ||
181 | /* Find the immediate postdominator PDOM of the specified | |
182 | basic block BLOCK. */ | |
183 | ||
184 | static inline basic_block | |
185 | find_pdom (basic_block block) | |
186 | { | |
187 | if (block == EXIT_BLOCK_PTR) | |
188 | return EXIT_BLOCK_PTR; | |
189 | else | |
190 | { | |
191 | basic_block bb | |
192 | = get_immediate_dominator (CDI_POST_DOMINATORS, block); | |
193 | if (! bb) | |
194 | return EXIT_BLOCK_PTR; | |
195 | return bb; | |
196 | } | |
197 | } | |
198 | ||
199 | /* Find the immediate DOM of the specified | |
200 | basic block BLOCK. */ | |
201 | ||
202 | static inline basic_block | |
203 | find_dom (basic_block block) | |
204 | { | |
205 | if (block == ENTRY_BLOCK_PTR) | |
206 | return ENTRY_BLOCK_PTR; | |
207 | else | |
208 | { | |
209 | basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block); | |
210 | if (! bb) | |
211 | return ENTRY_BLOCK_PTR; | |
212 | return bb; | |
213 | } | |
214 | } | |
215 | ||
216 | /* Returns true if BB1 is postdominating BB2 and BB1 is | |
217 | not a loop exit bb. The loop exit bb check is simple and does | |
218 | not cover all cases. */ | |
219 | ||
220 | static bool | |
221 | is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2) | |
222 | { | |
223 | if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)) | |
224 | return false; | |
225 | ||
226 | if (single_pred_p (bb1) && !single_succ_p (bb2)) | |
227 | return false; | |
228 | ||
229 | return true; | |
230 | } | |
231 | ||
232 | /* Find the closest postdominator of a specified BB, which is control | |
233 | equivalent to BB. */ | |
234 | ||
235 | static inline basic_block | |
236 | find_control_equiv_block (basic_block bb) | |
237 | { | |
238 | basic_block pdom; | |
239 | ||
240 | pdom = find_pdom (bb); | |
241 | ||
242 | /* Skip the postdominating bb that is also loop exit. */ | |
243 | if (!is_non_loop_exit_postdominating (pdom, bb)) | |
244 | return NULL; | |
245 | ||
246 | if (dominated_by_p (CDI_DOMINATORS, pdom, bb)) | |
247 | return pdom; | |
248 | ||
249 | return NULL; | |
250 | } | |
251 | ||
252 | #define MAX_NUM_CHAINS 8 | |
253 | #define MAX_CHAIN_LEN 5 | |
4dc1d68c | 254 | #define MAX_POSTDOM_CHECK 8 |
34f97b94 XDL |
255 | |
256 | /* Computes the control dependence chains (paths of edges) | |
257 | for DEP_BB up to the dominating basic block BB (the head node of a | |
258 | chain should be dominated by it). CD_CHAINS is pointer to a | |
259 | dynamic array holding the result chains. CUR_CD_CHAIN is the current | |
260 | chain being computed. *NUM_CHAINS is total number of chains. The | |
261 | function returns true if the information is successfully computed, | |
262 | return false if there is no control dependence or not computed. */ | |
263 | ||
264 | static bool | |
265 | compute_control_dep_chain (basic_block bb, basic_block dep_bb, | |
9771b263 | 266 | vec<edge> *cd_chains, |
34f97b94 | 267 | size_t *num_chains, |
9771b263 | 268 | vec<edge> *cur_cd_chain) |
34f97b94 XDL |
269 | { |
270 | edge_iterator ei; | |
271 | edge e; | |
272 | size_t i; | |
273 | bool found_cd_chain = false; | |
274 | size_t cur_chain_len = 0; | |
275 | ||
276 | if (EDGE_COUNT (bb->succs) < 2) | |
277 | return false; | |
278 | ||
279 | /* Could use a set instead. */ | |
9771b263 | 280 | cur_chain_len = cur_cd_chain->length (); |
34f97b94 XDL |
281 | if (cur_chain_len > MAX_CHAIN_LEN) |
282 | return false; | |
283 | ||
284 | for (i = 0; i < cur_chain_len; i++) | |
285 | { | |
9771b263 | 286 | edge e = (*cur_cd_chain)[i]; |
34f97b94 XDL |
287 | /* cycle detected. */ |
288 | if (e->src == bb) | |
289 | return false; | |
290 | } | |
291 | ||
292 | FOR_EACH_EDGE (e, ei, bb->succs) | |
293 | { | |
294 | basic_block cd_bb; | |
4dc1d68c | 295 | int post_dom_check = 0; |
34f97b94 XDL |
296 | if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL)) |
297 | continue; | |
298 | ||
299 | cd_bb = e->dest; | |
9771b263 | 300 | cur_cd_chain->safe_push (e); |
34f97b94 XDL |
301 | while (!is_non_loop_exit_postdominating (cd_bb, bb)) |
302 | { | |
303 | if (cd_bb == dep_bb) | |
304 | { | |
305 | /* Found a direct control dependence. */ | |
306 | if (*num_chains < MAX_NUM_CHAINS) | |
307 | { | |
9771b263 | 308 | cd_chains[*num_chains] = cur_cd_chain->copy (); |
34f97b94 XDL |
309 | (*num_chains)++; |
310 | } | |
311 | found_cd_chain = true; | |
312 | /* check path from next edge. */ | |
313 | break; | |
314 | } | |
315 | ||
316 | /* Now check if DEP_BB is indirectly control dependent on BB. */ | |
317 | if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, | |
318 | num_chains, cur_cd_chain)) | |
319 | { | |
320 | found_cd_chain = true; | |
321 | break; | |
322 | } | |
323 | ||
324 | cd_bb = find_pdom (cd_bb); | |
4dc1d68c XDL |
325 | post_dom_check++; |
326 | if (cd_bb == EXIT_BLOCK_PTR || post_dom_check > MAX_POSTDOM_CHECK) | |
34f97b94 XDL |
327 | break; |
328 | } | |
9771b263 DN |
329 | cur_cd_chain->pop (); |
330 | gcc_assert (cur_cd_chain->length () == cur_chain_len); | |
34f97b94 | 331 | } |
9771b263 | 332 | gcc_assert (cur_cd_chain->length () == cur_chain_len); |
34f97b94 XDL |
333 | |
334 | return found_cd_chain; | |
335 | } | |
336 | ||
337 | typedef struct use_pred_info | |
338 | { | |
339 | gimple cond; | |
340 | bool invert; | |
341 | } *use_pred_info_t; | |
342 | ||
34f97b94 XDL |
343 | |
344 | ||
345 | /* Converts the chains of control dependence edges into a set of | |
346 | predicates. A control dependence chain is represented by a vector | |
347 | edges. DEP_CHAINS points to an array of dependence chains. | |
348 | NUM_CHAINS is the size of the chain array. One edge in a dependence | |
349 | chain is mapped to predicate expression represented by use_pred_info_t | |
350 | type. One dependence chain is converted to a composite predicate that | |
351 | is the result of AND operation of use_pred_info_t mapped to each edge. | |
352 | A composite predicate is presented by a vector of use_pred_info_t. On | |
353 | return, *PREDS points to the resulting array of composite predicates. | |
354 | *NUM_PREDS is the number of composite predictes. */ | |
355 | ||
356 | static bool | |
9771b263 | 357 | convert_control_dep_chain_into_preds (vec<edge> *dep_chains, |
34f97b94 | 358 | size_t num_chains, |
9771b263 | 359 | vec<use_pred_info_t> **preds, |
34f97b94 XDL |
360 | size_t *num_preds) |
361 | { | |
362 | bool has_valid_pred = false; | |
363 | size_t i, j; | |
364 | if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS) | |
365 | return false; | |
366 | ||
34f97b94 XDL |
367 | /* Now convert the control dep chain into a set |
368 | of predicates. */ | |
9771b263 DN |
369 | typedef vec<use_pred_info_t> vec_use_pred_info_t_heap; |
370 | *preds = XCNEWVEC (vec_use_pred_info_t_heap, num_chains); | |
34f97b94 XDL |
371 | *num_preds = num_chains; |
372 | ||
373 | for (i = 0; i < num_chains; i++) | |
374 | { | |
9771b263 | 375 | vec<edge> one_cd_chain = dep_chains[i]; |
c375a3a4 DL |
376 | |
377 | has_valid_pred = false; | |
9771b263 | 378 | for (j = 0; j < one_cd_chain.length (); j++) |
34f97b94 XDL |
379 | { |
380 | gimple cond_stmt; | |
381 | gimple_stmt_iterator gsi; | |
382 | basic_block guard_bb; | |
383 | use_pred_info_t one_pred; | |
384 | edge e; | |
385 | ||
9771b263 | 386 | e = one_cd_chain[j]; |
34f97b94 XDL |
387 | guard_bb = e->src; |
388 | gsi = gsi_last_bb (guard_bb); | |
389 | if (gsi_end_p (gsi)) | |
390 | { | |
391 | has_valid_pred = false; | |
392 | break; | |
393 | } | |
394 | cond_stmt = gsi_stmt (gsi); | |
395 | if (gimple_code (cond_stmt) == GIMPLE_CALL | |
396 | && EDGE_COUNT (e->src->succs) >= 2) | |
397 | { | |
398 | /* Ignore EH edge. Can add assertion | |
399 | on the other edge's flag. */ | |
400 | continue; | |
401 | } | |
402 | /* Skip if there is essentially one succesor. */ | |
403 | if (EDGE_COUNT (e->src->succs) == 2) | |
404 | { | |
405 | edge e1; | |
406 | edge_iterator ei1; | |
407 | bool skip = false; | |
408 | ||
409 | FOR_EACH_EDGE (e1, ei1, e->src->succs) | |
410 | { | |
411 | if (EDGE_COUNT (e1->dest->succs) == 0) | |
412 | { | |
413 | skip = true; | |
414 | break; | |
415 | } | |
416 | } | |
417 | if (skip) | |
418 | continue; | |
419 | } | |
420 | if (gimple_code (cond_stmt) != GIMPLE_COND) | |
421 | { | |
422 | has_valid_pred = false; | |
423 | break; | |
424 | } | |
425 | one_pred = XNEW (struct use_pred_info); | |
426 | one_pred->cond = cond_stmt; | |
427 | one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE); | |
9771b263 | 428 | (*preds)[i].safe_push (one_pred); |
3411bc59 | 429 | has_valid_pred = true; |
34f97b94 XDL |
430 | } |
431 | ||
432 | if (!has_valid_pred) | |
433 | break; | |
434 | } | |
435 | return has_valid_pred; | |
436 | } | |
437 | ||
438 | /* Computes all control dependence chains for USE_BB. The control | |
439 | dependence chains are then converted to an array of composite | |
440 | predicates pointed to by PREDS. PHI_BB is the basic block of | |
441 | the phi whose result is used in USE_BB. */ | |
442 | ||
443 | static bool | |
9771b263 | 444 | find_predicates (vec<use_pred_info_t> **preds, |
34f97b94 XDL |
445 | size_t *num_preds, |
446 | basic_block phi_bb, | |
447 | basic_block use_bb) | |
448 | { | |
449 | size_t num_chains = 0, i; | |
9771b263 | 450 | vec<edge> *dep_chains = 0; |
6e1aa848 | 451 | vec<edge> cur_chain = vNULL; |
34f97b94 XDL |
452 | bool has_valid_pred = false; |
453 | basic_block cd_root = 0; | |
454 | ||
9771b263 DN |
455 | typedef vec<edge> vec_edge_heap; |
456 | dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS); | |
34f97b94 XDL |
457 | |
458 | /* First find the closest bb that is control equivalent to PHI_BB | |
459 | that also dominates USE_BB. */ | |
460 | cd_root = phi_bb; | |
461 | while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) | |
462 | { | |
463 | basic_block ctrl_eq_bb = find_control_equiv_block (cd_root); | |
464 | if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb)) | |
465 | cd_root = ctrl_eq_bb; | |
466 | else | |
467 | break; | |
468 | } | |
469 | ||
470 | compute_control_dep_chain (cd_root, use_bb, | |
471 | dep_chains, &num_chains, | |
472 | &cur_chain); | |
473 | ||
474 | has_valid_pred | |
475 | = convert_control_dep_chain_into_preds (dep_chains, | |
476 | num_chains, | |
477 | preds, | |
478 | num_preds); | |
479 | /* Free individual chain */ | |
9771b263 | 480 | cur_chain.release (); |
34f97b94 | 481 | for (i = 0; i < num_chains; i++) |
9771b263 | 482 | dep_chains[i].release (); |
34f97b94 XDL |
483 | free (dep_chains); |
484 | return has_valid_pred; | |
485 | } | |
486 | ||
487 | /* Computes the set of incoming edges of PHI that have non empty | |
488 | definitions of a phi chain. The collection will be done | |
489 | recursively on operands that are defined by phis. CD_ROOT | |
490 | is the control dependence root. *EDGES holds the result, and | |
491 | VISITED_PHIS is a pointer set for detecting cycles. */ | |
492 | ||
493 | static void | |
494 | collect_phi_def_edges (gimple phi, basic_block cd_root, | |
9771b263 | 495 | vec<edge> *edges, |
34f97b94 XDL |
496 | struct pointer_set_t *visited_phis) |
497 | { | |
498 | size_t i, n; | |
499 | edge opnd_edge; | |
500 | tree opnd; | |
501 | ||
502 | if (pointer_set_insert (visited_phis, phi)) | |
503 | return; | |
504 | ||
505 | n = gimple_phi_num_args (phi); | |
506 | for (i = 0; i < n; i++) | |
507 | { | |
508 | opnd_edge = gimple_phi_arg_edge (phi, i); | |
509 | opnd = gimple_phi_arg_def (phi, i); | |
510 | ||
e74780a3 XDL |
511 | if (TREE_CODE (opnd) != SSA_NAME) |
512 | { | |
513 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
514 | { | |
515 | fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); | |
516 | print_gimple_stmt (dump_file, phi, 0, 0); | |
517 | } | |
9771b263 | 518 | edges->safe_push (opnd_edge); |
e74780a3 | 519 | } |
34f97b94 XDL |
520 | else |
521 | { | |
522 | gimple def = SSA_NAME_DEF_STMT (opnd); | |
e74780a3 | 523 | |
34f97b94 XDL |
524 | if (gimple_code (def) == GIMPLE_PHI |
525 | && dominated_by_p (CDI_DOMINATORS, | |
526 | gimple_bb (def), cd_root)) | |
527 | collect_phi_def_edges (def, cd_root, edges, | |
528 | visited_phis); | |
ba7e83f8 | 529 | else if (!uninit_undefined_value_p (opnd)) |
e74780a3 XDL |
530 | { |
531 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
532 | { | |
533 | fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); | |
534 | print_gimple_stmt (dump_file, phi, 0, 0); | |
535 | } | |
9771b263 | 536 | edges->safe_push (opnd_edge); |
e74780a3 | 537 | } |
34f97b94 XDL |
538 | } |
539 | } | |
540 | } | |
541 | ||
542 | /* For each use edge of PHI, computes all control dependence chains. | |
543 | The control dependence chains are then converted to an array of | |
544 | composite predicates pointed to by PREDS. */ | |
545 | ||
546 | static bool | |
9771b263 | 547 | find_def_preds (vec<use_pred_info_t> **preds, |
34f97b94 XDL |
548 | size_t *num_preds, gimple phi) |
549 | { | |
550 | size_t num_chains = 0, i, n; | |
9771b263 | 551 | vec<edge> *dep_chains = 0; |
6e1aa848 DN |
552 | vec<edge> cur_chain = vNULL; |
553 | vec<edge> def_edges = vNULL; | |
34f97b94 XDL |
554 | bool has_valid_pred = false; |
555 | basic_block phi_bb, cd_root = 0; | |
556 | struct pointer_set_t *visited_phis; | |
557 | ||
9771b263 DN |
558 | typedef vec<edge> vec_edge_heap; |
559 | dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS); | |
34f97b94 XDL |
560 | |
561 | phi_bb = gimple_bb (phi); | |
562 | /* First find the closest dominating bb to be | |
563 | the control dependence root */ | |
564 | cd_root = find_dom (phi_bb); | |
565 | if (!cd_root) | |
566 | return false; | |
567 | ||
568 | visited_phis = pointer_set_create (); | |
569 | collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis); | |
570 | pointer_set_destroy (visited_phis); | |
571 | ||
9771b263 | 572 | n = def_edges.length (); |
34f97b94 XDL |
573 | if (n == 0) |
574 | return false; | |
575 | ||
576 | for (i = 0; i < n; i++) | |
577 | { | |
578 | size_t prev_nc, j; | |
579 | edge opnd_edge; | |
580 | ||
9771b263 | 581 | opnd_edge = def_edges[i]; |
34f97b94 XDL |
582 | prev_nc = num_chains; |
583 | compute_control_dep_chain (cd_root, opnd_edge->src, | |
584 | dep_chains, &num_chains, | |
585 | &cur_chain); | |
586 | /* Free individual chain */ | |
9771b263 | 587 | cur_chain.release (); |
34f97b94 XDL |
588 | |
589 | /* Now update the newly added chains with | |
590 | the phi operand edge: */ | |
591 | if (EDGE_COUNT (opnd_edge->src->succs) > 1) | |
592 | { | |
593 | if (prev_nc == num_chains | |
594 | && num_chains < MAX_NUM_CHAINS) | |
595 | num_chains++; | |
596 | for (j = prev_nc; j < num_chains; j++) | |
597 | { | |
9771b263 | 598 | dep_chains[j].safe_push (opnd_edge); |
34f97b94 XDL |
599 | } |
600 | } | |
601 | } | |
602 | ||
603 | has_valid_pred | |
604 | = convert_control_dep_chain_into_preds (dep_chains, | |
605 | num_chains, | |
606 | preds, | |
607 | num_preds); | |
608 | for (i = 0; i < num_chains; i++) | |
9771b263 | 609 | dep_chains[i].release (); |
34f97b94 XDL |
610 | free (dep_chains); |
611 | return has_valid_pred; | |
612 | } | |
613 | ||
614 | /* Dumps the predicates (PREDS) for USESTMT. */ | |
615 | ||
616 | static void | |
617 | dump_predicates (gimple usestmt, size_t num_preds, | |
9771b263 | 618 | vec<use_pred_info_t> *preds, |
34f97b94 XDL |
619 | const char* msg) |
620 | { | |
621 | size_t i, j; | |
9771b263 | 622 | vec<use_pred_info_t> one_pred_chain; |
34f97b94 XDL |
623 | fprintf (dump_file, msg); |
624 | print_gimple_stmt (dump_file, usestmt, 0, 0); | |
625 | fprintf (dump_file, "is guarded by :\n"); | |
626 | /* do some dumping here: */ | |
627 | for (i = 0; i < num_preds; i++) | |
628 | { | |
629 | size_t np; | |
630 | ||
631 | one_pred_chain = preds[i]; | |
9771b263 | 632 | np = one_pred_chain.length (); |
34f97b94 XDL |
633 | |
634 | for (j = 0; j < np; j++) | |
635 | { | |
636 | use_pred_info_t one_pred | |
9771b263 | 637 | = one_pred_chain[j]; |
34f97b94 XDL |
638 | if (one_pred->invert) |
639 | fprintf (dump_file, " (.NOT.) "); | |
640 | print_gimple_stmt (dump_file, one_pred->cond, 0, 0); | |
641 | if (j < np - 1) | |
642 | fprintf (dump_file, "(.AND.)\n"); | |
643 | } | |
644 | if (i < num_preds - 1) | |
645 | fprintf (dump_file, "(.OR.)\n"); | |
646 | } | |
647 | } | |
648 | ||
649 | /* Destroys the predicate set *PREDS. */ | |
650 | ||
651 | static void | |
652 | destroy_predicate_vecs (size_t n, | |
9771b263 | 653 | vec<use_pred_info_t> * preds) |
34f97b94 XDL |
654 | { |
655 | size_t i, j; | |
656 | for (i = 0; i < n; i++) | |
657 | { | |
9771b263 DN |
658 | for (j = 0; j < preds[i].length (); j++) |
659 | free (preds[i][j]); | |
660 | preds[i].release (); | |
34f97b94 XDL |
661 | } |
662 | free (preds); | |
663 | } | |
664 | ||
665 | ||
666 | /* Computes the 'normalized' conditional code with operand | |
667 | swapping and condition inversion. */ | |
668 | ||
669 | static enum tree_code | |
670 | get_cmp_code (enum tree_code orig_cmp_code, | |
671 | bool swap_cond, bool invert) | |
672 | { | |
673 | enum tree_code tc = orig_cmp_code; | |
674 | ||
675 | if (swap_cond) | |
676 | tc = swap_tree_comparison (orig_cmp_code); | |
677 | if (invert) | |
678 | tc = invert_tree_comparison (tc, false); | |
679 | ||
680 | switch (tc) | |
681 | { | |
682 | case LT_EXPR: | |
683 | case LE_EXPR: | |
684 | case GT_EXPR: | |
685 | case GE_EXPR: | |
686 | case EQ_EXPR: | |
687 | case NE_EXPR: | |
688 | break; | |
689 | default: | |
690 | return ERROR_MARK; | |
691 | } | |
692 | return tc; | |
693 | } | |
694 | ||
695 | /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e. | |
696 | all values in the range satisfies (x CMPC BOUNDARY) == true. */ | |
697 | ||
698 | static bool | |
699 | is_value_included_in (tree val, tree boundary, enum tree_code cmpc) | |
700 | { | |
701 | bool inverted = false; | |
702 | bool is_unsigned; | |
703 | bool result; | |
704 | ||
705 | /* Only handle integer constant here. */ | |
706 | if (TREE_CODE (val) != INTEGER_CST | |
707 | || TREE_CODE (boundary) != INTEGER_CST) | |
708 | return true; | |
709 | ||
710 | is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val)); | |
711 | ||
712 | if (cmpc == GE_EXPR || cmpc == GT_EXPR | |
713 | || cmpc == NE_EXPR) | |
714 | { | |
715 | cmpc = invert_tree_comparison (cmpc, false); | |
716 | inverted = true; | |
717 | } | |
718 | ||
719 | if (is_unsigned) | |
720 | { | |
721 | if (cmpc == EQ_EXPR) | |
722 | result = tree_int_cst_equal (val, boundary); | |
723 | else if (cmpc == LT_EXPR) | |
724 | result = INT_CST_LT_UNSIGNED (val, boundary); | |
725 | else | |
726 | { | |
727 | gcc_assert (cmpc == LE_EXPR); | |
728 | result = (tree_int_cst_equal (val, boundary) | |
729 | || INT_CST_LT_UNSIGNED (val, boundary)); | |
730 | } | |
731 | } | |
732 | else | |
733 | { | |
734 | if (cmpc == EQ_EXPR) | |
735 | result = tree_int_cst_equal (val, boundary); | |
736 | else if (cmpc == LT_EXPR) | |
737 | result = INT_CST_LT (val, boundary); | |
738 | else | |
739 | { | |
740 | gcc_assert (cmpc == LE_EXPR); | |
741 | result = (tree_int_cst_equal (val, boundary) | |
742 | || INT_CST_LT (val, boundary)); | |
743 | } | |
744 | } | |
745 | ||
746 | if (inverted) | |
747 | result ^= 1; | |
748 | ||
749 | return result; | |
750 | } | |
751 | ||
752 | /* Returns true if PRED is common among all the predicate | |
753 | chains (PREDS) (and therefore can be factored out). | |
754 | NUM_PRED_CHAIN is the size of array PREDS. */ | |
755 | ||
756 | static bool | |
757 | find_matching_predicate_in_rest_chains (use_pred_info_t pred, | |
9771b263 | 758 | vec<use_pred_info_t> *preds, |
34f97b94 XDL |
759 | size_t num_pred_chains) |
760 | { | |
761 | size_t i, j, n; | |
762 | ||
763 | /* trival case */ | |
764 | if (num_pred_chains == 1) | |
765 | return true; | |
766 | ||
767 | for (i = 1; i < num_pred_chains; i++) | |
768 | { | |
769 | bool found = false; | |
9771b263 DN |
770 | vec<use_pred_info_t> one_chain = preds[i]; |
771 | n = one_chain.length (); | |
34f97b94 XDL |
772 | for (j = 0; j < n; j++) |
773 | { | |
774 | use_pred_info_t pred2 | |
9771b263 | 775 | = one_chain[j]; |
34f97b94 XDL |
776 | /* can relax the condition comparison to not |
777 | use address comparison. However, the most common | |
778 | case is that multiple control dependent paths share | |
779 | a common path prefix, so address comparison should | |
780 | be ok. */ | |
781 | ||
782 | if (pred2->cond == pred->cond | |
783 | && pred2->invert == pred->invert) | |
784 | { | |
785 | found = true; | |
786 | break; | |
787 | } | |
788 | } | |
789 | if (!found) | |
790 | return false; | |
791 | } | |
792 | return true; | |
793 | } | |
794 | ||
795 | /* Forward declaration. */ | |
796 | static bool | |
797 | is_use_properly_guarded (gimple use_stmt, | |
798 | basic_block use_bb, | |
799 | gimple phi, | |
800 | unsigned uninit_opnds, | |
801 | struct pointer_set_t *visited_phis); | |
802 | ||
2edb37a6 XDL |
803 | /* Returns true if all uninitialized opnds are pruned. Returns false |
804 | otherwise. PHI is the phi node with uninitialized operands, | |
805 | UNINIT_OPNDS is the bitmap of the uninitialize operand positions, | |
806 | FLAG_DEF is the statement defining the flag guarding the use of the | |
807 | PHI output, BOUNDARY_CST is the const value used in the predicate | |
808 | associated with the flag, CMP_CODE is the comparison code used in | |
809 | the predicate, VISITED_PHIS is the pointer set of phis visited, and | |
810 | VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions | |
811 | that are also phis. | |
812 | ||
813 | Example scenario: | |
814 | ||
815 | BB1: | |
816 | flag_1 = phi <0, 1> // (1) | |
817 | var_1 = phi <undef, some_val> | |
818 | ||
819 | ||
820 | BB2: | |
821 | flag_2 = phi <0, flag_1, flag_1> // (2) | |
822 | var_2 = phi <undef, var_1, var_1> | |
823 | if (flag_2 == 1) | |
824 | goto BB3; | |
825 | ||
826 | BB3: | |
827 | use of var_2 // (3) | |
828 | ||
829 | Because some flag arg in (1) is not constant, if we do not look into the | |
830 | flag phis recursively, it is conservatively treated as unknown and var_1 | |
831 | is thought to be flowed into use at (3). Since var_1 is potentially uninitialized | |
832 | a false warning will be emitted. Checking recursively into (1), the compiler can | |
833 | find out that only some_val (which is defined) can flow into (3) which is OK. | |
834 | ||
835 | */ | |
836 | ||
837 | static bool | |
838 | prune_uninit_phi_opnds_in_unrealizable_paths ( | |
839 | gimple phi, unsigned uninit_opnds, | |
840 | gimple flag_def, tree boundary_cst, | |
841 | enum tree_code cmp_code, | |
842 | struct pointer_set_t *visited_phis, | |
843 | bitmap *visited_flag_phis) | |
844 | { | |
845 | unsigned i; | |
846 | ||
847 | for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++) | |
848 | { | |
849 | tree flag_arg; | |
850 | ||
851 | if (!MASK_TEST_BIT (uninit_opnds, i)) | |
852 | continue; | |
853 | ||
854 | flag_arg = gimple_phi_arg_def (flag_def, i); | |
855 | if (!is_gimple_constant (flag_arg)) | |
856 | { | |
857 | gimple flag_arg_def, phi_arg_def; | |
858 | tree phi_arg; | |
859 | unsigned uninit_opnds_arg_phi; | |
860 | ||
861 | if (TREE_CODE (flag_arg) != SSA_NAME) | |
862 | return false; | |
863 | flag_arg_def = SSA_NAME_DEF_STMT (flag_arg); | |
864 | if (gimple_code (flag_arg_def) != GIMPLE_PHI) | |
865 | return false; | |
866 | ||
867 | phi_arg = gimple_phi_arg_def (phi, i); | |
868 | if (TREE_CODE (phi_arg) != SSA_NAME) | |
869 | return false; | |
870 | ||
871 | phi_arg_def = SSA_NAME_DEF_STMT (phi_arg); | |
872 | if (gimple_code (phi_arg_def) != GIMPLE_PHI) | |
873 | return false; | |
874 | ||
875 | if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def)) | |
876 | return false; | |
877 | ||
878 | if (!*visited_flag_phis) | |
879 | *visited_flag_phis = BITMAP_ALLOC (NULL); | |
880 | ||
881 | if (bitmap_bit_p (*visited_flag_phis, | |
882 | SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)))) | |
883 | return false; | |
884 | ||
885 | bitmap_set_bit (*visited_flag_phis, | |
886 | SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); | |
887 | ||
888 | /* Now recursively prune the uninitialized phi args. */ | |
889 | uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def); | |
890 | if (!prune_uninit_phi_opnds_in_unrealizable_paths ( | |
891 | phi_arg_def, uninit_opnds_arg_phi, | |
892 | flag_arg_def, boundary_cst, cmp_code, | |
893 | visited_phis, visited_flag_phis)) | |
894 | return false; | |
895 | ||
896 | bitmap_clear_bit (*visited_flag_phis, | |
897 | SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); | |
898 | continue; | |
899 | } | |
900 | ||
901 | /* Now check if the constant is in the guarded range. */ | |
902 | if (is_value_included_in (flag_arg, boundary_cst, cmp_code)) | |
903 | { | |
904 | tree opnd; | |
905 | gimple opnd_def; | |
906 | ||
907 | /* Now that we know that this undefined edge is not | |
908 | pruned. If the operand is defined by another phi, | |
909 | we can further prune the incoming edges of that | |
910 | phi by checking the predicates of this operands. */ | |
911 | ||
912 | opnd = gimple_phi_arg_def (phi, i); | |
913 | opnd_def = SSA_NAME_DEF_STMT (opnd); | |
914 | if (gimple_code (opnd_def) == GIMPLE_PHI) | |
915 | { | |
916 | edge opnd_edge; | |
917 | unsigned uninit_opnds2 | |
918 | = compute_uninit_opnds_pos (opnd_def); | |
919 | gcc_assert (!MASK_EMPTY (uninit_opnds2)); | |
920 | opnd_edge = gimple_phi_arg_edge (phi, i); | |
921 | if (!is_use_properly_guarded (phi, | |
922 | opnd_edge->src, | |
923 | opnd_def, | |
924 | uninit_opnds2, | |
925 | visited_phis)) | |
926 | return false; | |
927 | } | |
928 | else | |
929 | return false; | |
930 | } | |
931 | } | |
932 | ||
933 | return true; | |
934 | } | |
935 | ||
34f97b94 XDL |
936 | /* A helper function that determines if the predicate set |
937 | of the use is not overlapping with that of the uninit paths. | |
938 | The most common senario of guarded use is in Example 1: | |
939 | Example 1: | |
940 | if (some_cond) | |
941 | { | |
942 | x = ...; | |
943 | flag = true; | |
944 | } | |
945 | ||
946 | ... some code ... | |
947 | ||
948 | if (flag) | |
949 | use (x); | |
950 | ||
951 | The real world examples are usually more complicated, but similar | |
952 | and usually result from inlining: | |
953 | ||
954 | bool init_func (int * x) | |
955 | { | |
956 | if (some_cond) | |
957 | return false; | |
958 | *x = .. | |
959 | return true; | |
960 | } | |
961 | ||
962 | void foo(..) | |
963 | { | |
964 | int x; | |
965 | ||
966 | if (!init_func(&x)) | |
967 | return; | |
968 | ||
969 | .. some_code ... | |
970 | use (x); | |
971 | } | |
972 | ||
973 | Another possible use scenario is in the following trivial example: | |
974 | ||
975 | Example 2: | |
976 | if (n > 0) | |
977 | x = 1; | |
978 | ... | |
979 | if (n > 0) | |
980 | { | |
981 | if (m < 2) | |
982 | .. = x; | |
983 | } | |
984 | ||
985 | Predicate analysis needs to compute the composite predicate: | |
986 | ||
987 | 1) 'x' use predicate: (n > 0) .AND. (m < 2) | |
988 | 2) 'x' default value (non-def) predicate: .NOT. (n > 0) | |
989 | (the predicate chain for phi operand defs can be computed | |
990 | starting from a bb that is control equivalent to the phi's | |
991 | bb and is dominating the operand def.) | |
992 | ||
993 | and check overlapping: | |
994 | (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0)) | |
995 | <==> false | |
996 | ||
997 | This implementation provides framework that can handle | |
998 | scenarios. (Note that many simple cases are handled properly | |
999 | without the predicate analysis -- this is due to jump threading | |
1000 | transformation which eliminates the merge point thus makes | |
1001 | path sensitive analysis unnecessary.) | |
1002 | ||
1003 | NUM_PREDS is the number is the number predicate chains, PREDS is | |
1004 | the array of chains, PHI is the phi node whose incoming (undefined) | |
1005 | paths need to be pruned, and UNINIT_OPNDS is the bitmap holding | |
1006 | uninit operand positions. VISITED_PHIS is the pointer set of phi | |
1007 | stmts being checked. */ | |
1008 | ||
1009 | ||
1010 | static bool | |
1011 | use_pred_not_overlap_with_undef_path_pred ( | |
1012 | size_t num_preds, | |
9771b263 | 1013 | vec<use_pred_info_t> *preds, |
34f97b94 XDL |
1014 | gimple phi, unsigned uninit_opnds, |
1015 | struct pointer_set_t *visited_phis) | |
1016 | { | |
1017 | unsigned int i, n; | |
1018 | gimple flag_def = 0; | |
1019 | tree boundary_cst = 0; | |
1020 | enum tree_code cmp_code; | |
1021 | bool swap_cond = false; | |
1022 | bool invert = false; | |
9771b263 | 1023 | vec<use_pred_info_t> the_pred_chain; |
2edb37a6 XDL |
1024 | bitmap visited_flag_phis = NULL; |
1025 | bool all_pruned = false; | |
34f97b94 XDL |
1026 | |
1027 | gcc_assert (num_preds > 0); | |
1028 | /* Find within the common prefix of multiple predicate chains | |
1029 | a predicate that is a comparison of a flag variable against | |
1030 | a constant. */ | |
1031 | the_pred_chain = preds[0]; | |
9771b263 | 1032 | n = the_pred_chain.length (); |
34f97b94 XDL |
1033 | for (i = 0; i < n; i++) |
1034 | { | |
1035 | gimple cond; | |
1036 | tree cond_lhs, cond_rhs, flag = 0; | |
1037 | ||
1038 | use_pred_info_t the_pred | |
9771b263 | 1039 | = the_pred_chain[i]; |
34f97b94 XDL |
1040 | |
1041 | cond = the_pred->cond; | |
1042 | invert = the_pred->invert; | |
1043 | cond_lhs = gimple_cond_lhs (cond); | |
1044 | cond_rhs = gimple_cond_rhs (cond); | |
1045 | cmp_code = gimple_cond_code (cond); | |
1046 | ||
1047 | if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME | |
1048 | && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs)) | |
1049 | { | |
1050 | boundary_cst = cond_rhs; | |
1051 | flag = cond_lhs; | |
1052 | } | |
1053 | else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME | |
1054 | && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs)) | |
1055 | { | |
1056 | boundary_cst = cond_lhs; | |
1057 | flag = cond_rhs; | |
1058 | swap_cond = true; | |
1059 | } | |
1060 | ||
1061 | if (!flag) | |
1062 | continue; | |
1063 | ||
1064 | flag_def = SSA_NAME_DEF_STMT (flag); | |
1065 | ||
1066 | if (!flag_def) | |
1067 | continue; | |
1068 | ||
1069 | if ((gimple_code (flag_def) == GIMPLE_PHI) | |
1070 | && (gimple_bb (flag_def) == gimple_bb (phi)) | |
1071 | && find_matching_predicate_in_rest_chains ( | |
1072 | the_pred, preds, num_preds)) | |
1073 | break; | |
1074 | ||
1075 | flag_def = 0; | |
1076 | } | |
1077 | ||
1078 | if (!flag_def) | |
1079 | return false; | |
1080 | ||
1081 | /* Now check all the uninit incoming edge has a constant flag value | |
1082 | that is in conflict with the use guard/predicate. */ | |
1083 | cmp_code = get_cmp_code (cmp_code, swap_cond, invert); | |
1084 | ||
1085 | if (cmp_code == ERROR_MARK) | |
1086 | return false; | |
1087 | ||
2edb37a6 XDL |
1088 | all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi, |
1089 | uninit_opnds, | |
1090 | flag_def, | |
1091 | boundary_cst, | |
1092 | cmp_code, | |
1093 | visited_phis, | |
1094 | &visited_flag_phis); | |
34f97b94 | 1095 | |
2edb37a6 XDL |
1096 | if (visited_flag_phis) |
1097 | BITMAP_FREE (visited_flag_phis); | |
34f97b94 | 1098 | |
2edb37a6 | 1099 | return all_pruned; |
34f97b94 XDL |
1100 | } |
1101 | ||
1102 | /* Returns true if TC is AND or OR */ | |
1103 | ||
1104 | static inline bool | |
1105 | is_and_or_or (enum tree_code tc, tree typ) | |
1106 | { | |
3046b1a9 | 1107 | return (tc == BIT_IOR_EXPR |
34f97b94 XDL |
1108 | || (tc == BIT_AND_EXPR |
1109 | && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE))); | |
1110 | } | |
1111 | ||
1112 | typedef struct norm_cond | |
1113 | { | |
9771b263 | 1114 | vec<gimple> conds; |
34f97b94 XDL |
1115 | enum tree_code cond_code; |
1116 | bool invert; | |
1117 | } *norm_cond_t; | |
1118 | ||
1119 | ||
1120 | /* Normalizes gimple condition COND. The normalization follows | |
1121 | UD chains to form larger condition expression trees. NORM_COND | |
1122 | holds the normalized result. COND_CODE is the logical opcode | |
1123 | (AND or OR) of the normalized tree. */ | |
1124 | ||
1125 | static void | |
1126 | normalize_cond_1 (gimple cond, | |
1127 | norm_cond_t norm_cond, | |
1128 | enum tree_code cond_code) | |
1129 | { | |
1130 | enum gimple_code gc; | |
1131 | enum tree_code cur_cond_code; | |
1132 | tree rhs1, rhs2; | |
1133 | ||
1134 | gc = gimple_code (cond); | |
1135 | if (gc != GIMPLE_ASSIGN) | |
1136 | { | |
9771b263 | 1137 | norm_cond->conds.safe_push (cond); |
34f97b94 XDL |
1138 | return; |
1139 | } | |
1140 | ||
1141 | cur_cond_code = gimple_assign_rhs_code (cond); | |
1142 | rhs1 = gimple_assign_rhs1 (cond); | |
1143 | rhs2 = gimple_assign_rhs2 (cond); | |
1144 | if (cur_cond_code == NE_EXPR) | |
1145 | { | |
1146 | if (integer_zerop (rhs2) | |
1147 | && (TREE_CODE (rhs1) == SSA_NAME)) | |
1148 | normalize_cond_1 ( | |
1149 | SSA_NAME_DEF_STMT (rhs1), | |
1150 | norm_cond, cond_code); | |
1151 | else if (integer_zerop (rhs1) | |
1152 | && (TREE_CODE (rhs2) == SSA_NAME)) | |
1153 | normalize_cond_1 ( | |
1154 | SSA_NAME_DEF_STMT (rhs2), | |
1155 | norm_cond, cond_code); | |
1156 | else | |
9771b263 | 1157 | norm_cond->conds.safe_push (cond); |
34f97b94 XDL |
1158 | |
1159 | return; | |
1160 | } | |
1161 | ||
1162 | if (is_and_or_or (cur_cond_code, TREE_TYPE (rhs1)) | |
1163 | && (cond_code == cur_cond_code || cond_code == ERROR_MARK) | |
1164 | && (TREE_CODE (rhs1) == SSA_NAME && TREE_CODE (rhs2) == SSA_NAME)) | |
1165 | { | |
1166 | normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1), | |
1167 | norm_cond, cur_cond_code); | |
1168 | normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2), | |
1169 | norm_cond, cur_cond_code); | |
1170 | norm_cond->cond_code = cur_cond_code; | |
1171 | } | |
1172 | else | |
9771b263 | 1173 | norm_cond->conds.safe_push (cond); |
34f97b94 XDL |
1174 | } |
1175 | ||
1176 | /* See normalize_cond_1 for details. INVERT is a flag to indicate | |
1177 | if COND needs to be inverted or not. */ | |
1178 | ||
1179 | static void | |
1180 | normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert) | |
1181 | { | |
1182 | enum tree_code cond_code; | |
1183 | ||
1184 | norm_cond->cond_code = ERROR_MARK; | |
1185 | norm_cond->invert = false; | |
9771b263 | 1186 | norm_cond->conds.create (0); |
34f97b94 XDL |
1187 | gcc_assert (gimple_code (cond) == GIMPLE_COND); |
1188 | cond_code = gimple_cond_code (cond); | |
1189 | if (invert) | |
1190 | cond_code = invert_tree_comparison (cond_code, false); | |
1191 | ||
1192 | if (cond_code == NE_EXPR) | |
1193 | { | |
1194 | if (integer_zerop (gimple_cond_rhs (cond)) | |
1195 | && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME)) | |
1196 | normalize_cond_1 ( | |
1197 | SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)), | |
1198 | norm_cond, ERROR_MARK); | |
1199 | else if (integer_zerop (gimple_cond_lhs (cond)) | |
1200 | && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME)) | |
1201 | normalize_cond_1 ( | |
1202 | SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)), | |
1203 | norm_cond, ERROR_MARK); | |
1204 | else | |
1205 | { | |
9771b263 | 1206 | norm_cond->conds.safe_push (cond); |
34f97b94 XDL |
1207 | norm_cond->invert = invert; |
1208 | } | |
1209 | } | |
1210 | else | |
1211 | { | |
9771b263 | 1212 | norm_cond->conds.safe_push (cond); |
34f97b94 XDL |
1213 | norm_cond->invert = invert; |
1214 | } | |
1215 | ||
9771b263 | 1216 | gcc_assert (norm_cond->conds.length () == 1 |
34f97b94 XDL |
1217 | || is_and_or_or (norm_cond->cond_code, NULL)); |
1218 | } | |
1219 | ||
1220 | /* Returns true if the domain for condition COND1 is a subset of | |
1221 | COND2. REVERSE is a flag. when it is true the function checks | |
1222 | if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags | |
1223 | to indicate if COND1 and COND2 need to be inverted or not. */ | |
1224 | ||
1225 | static bool | |
1226 | is_gcond_subset_of (gimple cond1, bool invert1, | |
1227 | gimple cond2, bool invert2, | |
1228 | bool reverse) | |
1229 | { | |
1230 | enum gimple_code gc1, gc2; | |
1231 | enum tree_code cond1_code, cond2_code; | |
1232 | gimple tmp; | |
1233 | tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs; | |
1234 | ||
1235 | /* Take the short cut. */ | |
1236 | if (cond1 == cond2) | |
1237 | return true; | |
1238 | ||
1239 | if (reverse) | |
1240 | { | |
1241 | tmp = cond1; | |
1242 | cond1 = cond2; | |
1243 | cond2 = tmp; | |
1244 | } | |
1245 | ||
1246 | gc1 = gimple_code (cond1); | |
1247 | gc2 = gimple_code (cond2); | |
1248 | ||
1249 | if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND) | |
1250 | || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND)) | |
1251 | return cond1 == cond2; | |
1252 | ||
1253 | cond1_code = ((gc1 == GIMPLE_ASSIGN) | |
1254 | ? gimple_assign_rhs_code (cond1) | |
1255 | : gimple_cond_code (cond1)); | |
1256 | ||
1257 | cond2_code = ((gc2 == GIMPLE_ASSIGN) | |
1258 | ? gimple_assign_rhs_code (cond2) | |
1259 | : gimple_cond_code (cond2)); | |
1260 | ||
1261 | if (TREE_CODE_CLASS (cond1_code) != tcc_comparison | |
1262 | || TREE_CODE_CLASS (cond2_code) != tcc_comparison) | |
1263 | return false; | |
1264 | ||
1265 | if (invert1) | |
1266 | cond1_code = invert_tree_comparison (cond1_code, false); | |
1267 | if (invert2) | |
1268 | cond2_code = invert_tree_comparison (cond2_code, false); | |
1269 | ||
1270 | cond1_lhs = ((gc1 == GIMPLE_ASSIGN) | |
1271 | ? gimple_assign_rhs1 (cond1) | |
1272 | : gimple_cond_lhs (cond1)); | |
1273 | cond1_rhs = ((gc1 == GIMPLE_ASSIGN) | |
1274 | ? gimple_assign_rhs2 (cond1) | |
1275 | : gimple_cond_rhs (cond1)); | |
1276 | cond2_lhs = ((gc2 == GIMPLE_ASSIGN) | |
1277 | ? gimple_assign_rhs1 (cond2) | |
1278 | : gimple_cond_lhs (cond2)); | |
1279 | cond2_rhs = ((gc2 == GIMPLE_ASSIGN) | |
1280 | ? gimple_assign_rhs2 (cond2) | |
1281 | : gimple_cond_rhs (cond2)); | |
1282 | ||
1283 | /* Assuming const operands have been swapped to the | |
1284 | rhs at this point of the analysis. */ | |
1285 | ||
1286 | if (cond1_lhs != cond2_lhs) | |
1287 | return false; | |
1288 | ||
1289 | if (!is_gimple_constant (cond1_rhs) | |
1290 | || TREE_CODE (cond1_rhs) != INTEGER_CST) | |
1291 | return (cond1_rhs == cond2_rhs); | |
1292 | ||
1293 | if (!is_gimple_constant (cond2_rhs) | |
1294 | || TREE_CODE (cond2_rhs) != INTEGER_CST) | |
1295 | return (cond1_rhs == cond2_rhs); | |
1296 | ||
1297 | if (cond1_code == EQ_EXPR) | |
1298 | return is_value_included_in (cond1_rhs, | |
1299 | cond2_rhs, cond2_code); | |
1300 | if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR) | |
1301 | return ((cond2_code == cond1_code) | |
1302 | && tree_int_cst_equal (cond1_rhs, cond2_rhs)); | |
1303 | ||
1304 | if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR) | |
1305 | && (cond2_code == LE_EXPR || cond2_code == LT_EXPR)) | |
1306 | || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR) | |
1307 | && (cond2_code == GE_EXPR || cond2_code == GT_EXPR))) | |
1308 | return false; | |
1309 | ||
1310 | if (cond1_code != GE_EXPR && cond1_code != GT_EXPR | |
1311 | && cond1_code != LE_EXPR && cond1_code != LT_EXPR) | |
1312 | return false; | |
1313 | ||
1314 | if (cond1_code == GT_EXPR) | |
1315 | { | |
1316 | cond1_code = GE_EXPR; | |
1317 | cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs), | |
1318 | cond1_rhs, | |
1319 | fold_convert (TREE_TYPE (cond1_rhs), | |
1320 | integer_one_node)); | |
1321 | } | |
1322 | else if (cond1_code == LT_EXPR) | |
1323 | { | |
1324 | cond1_code = LE_EXPR; | |
1325 | cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs), | |
1326 | cond1_rhs, | |
1327 | fold_convert (TREE_TYPE (cond1_rhs), | |
1328 | integer_one_node)); | |
1329 | } | |
1330 | ||
1331 | if (!cond1_rhs) | |
1332 | return false; | |
1333 | ||
1334 | gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR); | |
1335 | ||
1336 | if (cond2_code == GE_EXPR || cond2_code == GT_EXPR || | |
1337 | cond2_code == LE_EXPR || cond2_code == LT_EXPR) | |
1338 | return is_value_included_in (cond1_rhs, | |
1339 | cond2_rhs, cond2_code); | |
1340 | else if (cond2_code == NE_EXPR) | |
1341 | return | |
1342 | (is_value_included_in (cond1_rhs, | |
1343 | cond2_rhs, cond2_code) | |
1344 | && !is_value_included_in (cond2_rhs, | |
1345 | cond1_rhs, cond1_code)); | |
1346 | return false; | |
1347 | } | |
1348 | ||
1349 | /* Returns true if the domain of the condition expression | |
1350 | in COND is a subset of any of the sub-conditions | |
1351 | of the normalized condtion NORM_COND. INVERT is a flag | |
1352 | to indicate of the COND needs to be inverted. | |
1353 | REVERSE is a flag. When it is true, the check is reversed -- | |
1354 | it returns true if COND is a superset of any of the subconditions | |
1355 | of NORM_COND. */ | |
1356 | ||
1357 | static bool | |
1358 | is_subset_of_any (gimple cond, bool invert, | |
1359 | norm_cond_t norm_cond, bool reverse) | |
1360 | { | |
1361 | size_t i; | |
9771b263 | 1362 | size_t len = norm_cond->conds.length (); |
34f97b94 XDL |
1363 | |
1364 | for (i = 0; i < len; i++) | |
1365 | { | |
1366 | if (is_gcond_subset_of (cond, invert, | |
9771b263 | 1367 | norm_cond->conds[i], |
34f97b94 XDL |
1368 | false, reverse)) |
1369 | return true; | |
1370 | } | |
1371 | return false; | |
1372 | } | |
1373 | ||
1374 | /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR | |
1375 | expressions (formed by following UD chains not control | |
1376 | dependence chains). The function returns true of domain | |
1377 | of and expression NORM_COND1 is a subset of NORM_COND2's. | |
1378 | The implementation is conservative, and it returns false if | |
1379 | it the inclusion relationship may not hold. */ | |
1380 | ||
1381 | static bool | |
1382 | is_or_set_subset_of (norm_cond_t norm_cond1, | |
1383 | norm_cond_t norm_cond2) | |
1384 | { | |
1385 | size_t i; | |
9771b263 | 1386 | size_t len = norm_cond1->conds.length (); |
34f97b94 XDL |
1387 | |
1388 | for (i = 0; i < len; i++) | |
1389 | { | |
9771b263 | 1390 | if (!is_subset_of_any (norm_cond1->conds[i], |
34f97b94 XDL |
1391 | false, norm_cond2, false)) |
1392 | return false; | |
1393 | } | |
1394 | return true; | |
1395 | } | |
1396 | ||
1397 | /* NORM_COND1 and NORM_COND2 are normalized logical AND | |
1398 | expressions (formed by following UD chains not control | |
1399 | dependence chains). The function returns true of domain | |
1400 | of and expression NORM_COND1 is a subset of NORM_COND2's. */ | |
1401 | ||
1402 | static bool | |
1403 | is_and_set_subset_of (norm_cond_t norm_cond1, | |
1404 | norm_cond_t norm_cond2) | |
1405 | { | |
1406 | size_t i; | |
9771b263 | 1407 | size_t len = norm_cond2->conds.length (); |
34f97b94 XDL |
1408 | |
1409 | for (i = 0; i < len; i++) | |
1410 | { | |
9771b263 | 1411 | if (!is_subset_of_any (norm_cond2->conds[i], |
34f97b94 XDL |
1412 | false, norm_cond1, true)) |
1413 | return false; | |
1414 | } | |
1415 | return true; | |
1416 | } | |
1417 | ||
1418 | /* Returns true of the domain if NORM_COND1 is a subset | |
1419 | of that of NORM_COND2. Returns false if it can not be | |
1420 | proved to be so. */ | |
1421 | ||
1422 | static bool | |
1423 | is_norm_cond_subset_of (norm_cond_t norm_cond1, | |
1424 | norm_cond_t norm_cond2) | |
1425 | { | |
1426 | size_t i; | |
1427 | enum tree_code code1, code2; | |
1428 | ||
1429 | code1 = norm_cond1->cond_code; | |
1430 | code2 = norm_cond2->cond_code; | |
1431 | ||
3046b1a9 | 1432 | if (code1 == BIT_AND_EXPR) |
34f97b94 XDL |
1433 | { |
1434 | /* Both conditions are AND expressions. */ | |
3046b1a9 | 1435 | if (code2 == BIT_AND_EXPR) |
34f97b94 XDL |
1436 | return is_and_set_subset_of (norm_cond1, norm_cond2); |
1437 | /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR | |
1438 | expression. In this case, returns true if any subexpression | |
1439 | of NORM_COND1 is a subset of any subexpression of NORM_COND2. */ | |
3046b1a9 | 1440 | else if (code2 == BIT_IOR_EXPR) |
34f97b94 XDL |
1441 | { |
1442 | size_t len1; | |
9771b263 | 1443 | len1 = norm_cond1->conds.length (); |
34f97b94 XDL |
1444 | for (i = 0; i < len1; i++) |
1445 | { | |
9771b263 | 1446 | gimple cond1 = norm_cond1->conds[i]; |
34f97b94 XDL |
1447 | if (is_subset_of_any (cond1, false, norm_cond2, false)) |
1448 | return true; | |
1449 | } | |
1450 | return false; | |
1451 | } | |
1452 | else | |
1453 | { | |
1454 | gcc_assert (code2 == ERROR_MARK); | |
9771b263 DN |
1455 | gcc_assert (norm_cond2->conds.length () == 1); |
1456 | return is_subset_of_any (norm_cond2->conds[0], | |
34f97b94 XDL |
1457 | norm_cond2->invert, norm_cond1, true); |
1458 | } | |
1459 | } | |
1460 | /* NORM_COND1 is an OR expression */ | |
3046b1a9 | 1461 | else if (code1 == BIT_IOR_EXPR) |
34f97b94 XDL |
1462 | { |
1463 | if (code2 != code1) | |
1464 | return false; | |
1465 | ||
1466 | return is_or_set_subset_of (norm_cond1, norm_cond2); | |
1467 | } | |
1468 | else | |
1469 | { | |
1470 | gcc_assert (code1 == ERROR_MARK); | |
9771b263 | 1471 | gcc_assert (norm_cond1->conds.length () == 1); |
34f97b94 XDL |
1472 | /* Conservatively returns false if NORM_COND1 is non-decomposible |
1473 | and NORM_COND2 is an AND expression. */ | |
3046b1a9 | 1474 | if (code2 == BIT_AND_EXPR) |
34f97b94 XDL |
1475 | return false; |
1476 | ||
3046b1a9 | 1477 | if (code2 == BIT_IOR_EXPR) |
9771b263 | 1478 | return is_subset_of_any (norm_cond1->conds[0], |
34f97b94 XDL |
1479 | norm_cond1->invert, norm_cond2, false); |
1480 | ||
1481 | gcc_assert (code2 == ERROR_MARK); | |
9771b263 DN |
1482 | gcc_assert (norm_cond2->conds.length () == 1); |
1483 | return is_gcond_subset_of (norm_cond1->conds[0], | |
34f97b94 | 1484 | norm_cond1->invert, |
9771b263 | 1485 | norm_cond2->conds[0], |
34f97b94 XDL |
1486 | norm_cond2->invert, false); |
1487 | } | |
1488 | } | |
1489 | ||
1490 | /* Returns true of the domain of single predicate expression | |
1491 | EXPR1 is a subset of that of EXPR2. Returns false if it | |
1492 | can not be proved. */ | |
1493 | ||
1494 | static bool | |
1495 | is_pred_expr_subset_of (use_pred_info_t expr1, | |
1496 | use_pred_info_t expr2) | |
1497 | { | |
1498 | gimple cond1, cond2; | |
1499 | enum tree_code code1, code2; | |
1500 | struct norm_cond norm_cond1, norm_cond2; | |
1501 | bool is_subset = false; | |
1502 | ||
1503 | cond1 = expr1->cond; | |
1504 | cond2 = expr2->cond; | |
1505 | code1 = gimple_cond_code (cond1); | |
1506 | code2 = gimple_cond_code (cond2); | |
1507 | ||
1508 | if (expr1->invert) | |
1509 | code1 = invert_tree_comparison (code1, false); | |
1510 | if (expr2->invert) | |
1511 | code2 = invert_tree_comparison (code2, false); | |
1512 | ||
1513 | /* Fast path -- match exactly */ | |
1514 | if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2)) | |
1515 | && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2)) | |
1516 | && (code1 == code2)) | |
1517 | return true; | |
1518 | ||
1519 | /* Normalize conditions. To keep NE_EXPR, do not invert | |
1520 | with both need inversion. */ | |
1521 | normalize_cond (cond1, &norm_cond1, (expr1->invert)); | |
1522 | normalize_cond (cond2, &norm_cond2, (expr2->invert)); | |
1523 | ||
1524 | is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2); | |
1525 | ||
1526 | /* Free memory */ | |
9771b263 DN |
1527 | norm_cond1.conds.release (); |
1528 | norm_cond2.conds.release (); | |
34f97b94 XDL |
1529 | return is_subset ; |
1530 | } | |
1531 | ||
1532 | /* Returns true if the domain of PRED1 is a subset | |
1533 | of that of PRED2. Returns false if it can not be proved so. */ | |
1534 | ||
1535 | static bool | |
9771b263 DN |
1536 | is_pred_chain_subset_of (vec<use_pred_info_t> pred1, |
1537 | vec<use_pred_info_t> pred2) | |
34f97b94 XDL |
1538 | { |
1539 | size_t np1, np2, i1, i2; | |
1540 | ||
9771b263 DN |
1541 | np1 = pred1.length (); |
1542 | np2 = pred2.length (); | |
34f97b94 XDL |
1543 | |
1544 | for (i2 = 0; i2 < np2; i2++) | |
1545 | { | |
1546 | bool found = false; | |
1547 | use_pred_info_t info2 | |
9771b263 | 1548 | = pred2[i2]; |
34f97b94 XDL |
1549 | for (i1 = 0; i1 < np1; i1++) |
1550 | { | |
1551 | use_pred_info_t info1 | |
9771b263 | 1552 | = pred1[i1]; |
34f97b94 XDL |
1553 | if (is_pred_expr_subset_of (info1, info2)) |
1554 | { | |
1555 | found = true; | |
1556 | break; | |
1557 | } | |
1558 | } | |
1559 | if (!found) | |
1560 | return false; | |
1561 | } | |
1562 | return true; | |
1563 | } | |
1564 | ||
1565 | /* Returns true if the domain defined by | |
1566 | one pred chain ONE_PRED is a subset of the domain | |
1567 | of *PREDS. It returns false if ONE_PRED's domain is | |
1568 | not a subset of any of the sub-domains of PREDS ( | |
1569 | corresponding to each individual chains in it), even | |
1570 | though it may be still be a subset of whole domain | |
1571 | of PREDS which is the union (ORed) of all its subdomains. | |
1572 | In other words, the result is conservative. */ | |
1573 | ||
1574 | static bool | |
9771b263 DN |
1575 | is_included_in (vec<use_pred_info_t> one_pred, |
1576 | vec<use_pred_info_t> *preds, | |
34f97b94 XDL |
1577 | size_t n) |
1578 | { | |
1579 | size_t i; | |
1580 | ||
1581 | for (i = 0; i < n; i++) | |
1582 | { | |
1583 | if (is_pred_chain_subset_of (one_pred, preds[i])) | |
1584 | return true; | |
1585 | } | |
1586 | ||
1587 | return false; | |
1588 | } | |
1589 | ||
1590 | /* compares two predicate sets PREDS1 and PREDS2 and returns | |
1591 | true if the domain defined by PREDS1 is a superset | |
1592 | of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and | |
1593 | PREDS2 respectively. The implementation chooses not to build | |
1594 | generic trees (and relying on the folding capability of the | |
1595 | compiler), but instead performs brute force comparison of | |
1596 | individual predicate chains (won't be a compile time problem | |
1597 | as the chains are pretty short). When the function returns | |
1598 | false, it does not necessarily mean *PREDS1 is not a superset | |
1599 | of *PREDS2, but mean it may not be so since the analysis can | |
1600 | not prove it. In such cases, false warnings may still be | |
1601 | emitted. */ | |
1602 | ||
1603 | static bool | |
9771b263 | 1604 | is_superset_of (vec<use_pred_info_t> *preds1, |
34f97b94 | 1605 | size_t n1, |
9771b263 | 1606 | vec<use_pred_info_t> *preds2, |
34f97b94 XDL |
1607 | size_t n2) |
1608 | { | |
1609 | size_t i; | |
9771b263 | 1610 | vec<use_pred_info_t> one_pred_chain; |
34f97b94 XDL |
1611 | |
1612 | for (i = 0; i < n2; i++) | |
1613 | { | |
1614 | one_pred_chain = preds2[i]; | |
1615 | if (!is_included_in (one_pred_chain, preds1, n1)) | |
1616 | return false; | |
1617 | } | |
1618 | ||
1619 | return true; | |
1620 | } | |
1621 | ||
56b67510 XDL |
1622 | /* Comparison function used by qsort. It is used to |
1623 | sort predicate chains to allow predicate | |
1624 | simplification. */ | |
1625 | ||
1626 | static int | |
1627 | pred_chain_length_cmp (const void *p1, const void *p2) | |
1628 | { | |
1629 | use_pred_info_t i1, i2; | |
9771b263 DN |
1630 | vec<use_pred_info_t> const *chain1 |
1631 | = (vec<use_pred_info_t> const *)p1; | |
1632 | vec<use_pred_info_t> const *chain2 | |
1633 | = (vec<use_pred_info_t> const *)p2; | |
56b67510 | 1634 | |
9771b263 DN |
1635 | if (chain1->length () != chain2->length ()) |
1636 | return (chain1->length () - chain2->length ()); | |
56b67510 | 1637 | |
9771b263 DN |
1638 | i1 = (*chain1)[0]; |
1639 | i2 = (*chain2)[0]; | |
56b67510 XDL |
1640 | |
1641 | /* Allow predicates with similar prefix come together. */ | |
1642 | if (!i1->invert && i2->invert) | |
1643 | return -1; | |
1644 | else if (i1->invert && !i2->invert) | |
1645 | return 1; | |
1646 | ||
1647 | return gimple_uid (i1->cond) - gimple_uid (i2->cond); | |
1648 | } | |
1649 | ||
1650 | /* x OR (!x AND y) is equivalent to x OR y. | |
1651 | This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) | |
1652 | into x1 OR x2 OR x3. PREDS is the predicate chains, and N is | |
1653 | the number of chains. Returns true if normalization happens. */ | |
1654 | ||
1655 | static bool | |
9771b263 | 1656 | normalize_preds (vec<use_pred_info_t> *preds, size_t *n) |
56b67510 XDL |
1657 | { |
1658 | size_t i, j, ll; | |
9771b263 | 1659 | vec<use_pred_info_t> pred_chain; |
6e1aa848 | 1660 | vec<use_pred_info_t> x = vNULL; |
56b67510 XDL |
1661 | use_pred_info_t xj = 0, nxj = 0; |
1662 | ||
1663 | if (*n < 2) | |
1664 | return false; | |
1665 | ||
1666 | /* First sort the chains in ascending order of lengths. */ | |
1667 | qsort (preds, *n, sizeof (void *), pred_chain_length_cmp); | |
1668 | pred_chain = preds[0]; | |
9771b263 | 1669 | ll = pred_chain.length (); |
56b67510 XDL |
1670 | if (ll != 1) |
1671 | { | |
1672 | if (ll == 2) | |
1673 | { | |
1674 | use_pred_info_t xx, yy, xx2, nyy; | |
9771b263 DN |
1675 | vec<use_pred_info_t> pred_chain2 = preds[1]; |
1676 | if (pred_chain2.length () != 2) | |
56b67510 XDL |
1677 | return false; |
1678 | ||
1679 | /* See if simplification x AND y OR x AND !y is possible. */ | |
9771b263 DN |
1680 | xx = pred_chain[0]; |
1681 | yy = pred_chain[1]; | |
1682 | xx2 = pred_chain2[0]; | |
1683 | nyy = pred_chain2[1]; | |
56b67510 XDL |
1684 | if (gimple_cond_lhs (xx->cond) != gimple_cond_lhs (xx2->cond) |
1685 | || gimple_cond_rhs (xx->cond) != gimple_cond_rhs (xx2->cond) | |
1686 | || gimple_cond_code (xx->cond) != gimple_cond_code (xx2->cond) | |
1687 | || (xx->invert != xx2->invert)) | |
1688 | return false; | |
1689 | if (gimple_cond_lhs (yy->cond) != gimple_cond_lhs (nyy->cond) | |
1690 | || gimple_cond_rhs (yy->cond) != gimple_cond_rhs (nyy->cond) | |
1691 | || gimple_cond_code (yy->cond) != gimple_cond_code (nyy->cond) | |
1692 | || (yy->invert == nyy->invert)) | |
1693 | return false; | |
1694 | ||
1695 | /* Now merge the first two chains. */ | |
1696 | free (yy); | |
1697 | free (nyy); | |
1698 | free (xx2); | |
9771b263 DN |
1699 | pred_chain.release (); |
1700 | pred_chain2.release (); | |
1701 | pred_chain.safe_push (xx); | |
56b67510 XDL |
1702 | preds[0] = pred_chain; |
1703 | for (i = 1; i < *n - 1; i++) | |
1704 | preds[i] = preds[i + 1]; | |
1705 | ||
9771b263 | 1706 | preds[*n - 1].create (0); |
56b67510 XDL |
1707 | *n = *n - 1; |
1708 | } | |
1709 | else | |
1710 | return false; | |
1711 | } | |
1712 | ||
9771b263 | 1713 | x.safe_push (pred_chain[0]); |
56b67510 XDL |
1714 | |
1715 | /* The loop extracts x1, x2, x3, etc from chains | |
1716 | x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */ | |
1717 | for (i = 1; i < *n; i++) | |
1718 | { | |
1719 | pred_chain = preds[i]; | |
9771b263 | 1720 | if (pred_chain.length () != i + 1) |
56b67510 XDL |
1721 | return false; |
1722 | ||
1723 | for (j = 0; j < i; j++) | |
1724 | { | |
9771b263 DN |
1725 | xj = x[j]; |
1726 | nxj = pred_chain[j]; | |
56b67510 XDL |
1727 | |
1728 | /* Check if nxj is !xj */ | |
1729 | if (gimple_cond_lhs (xj->cond) != gimple_cond_lhs (nxj->cond) | |
1730 | || gimple_cond_rhs (xj->cond) != gimple_cond_rhs (nxj->cond) | |
1731 | || gimple_cond_code (xj->cond) != gimple_cond_code (nxj->cond) | |
1732 | || (xj->invert == nxj->invert)) | |
1733 | return false; | |
1734 | } | |
1735 | ||
9771b263 | 1736 | x.safe_push (pred_chain[i]); |
56b67510 XDL |
1737 | } |
1738 | ||
1739 | /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */ | |
1740 | for (j = 0; j < *n; j++) | |
1741 | { | |
1742 | use_pred_info_t t; | |
9771b263 | 1743 | xj = x[j]; |
56b67510 XDL |
1744 | |
1745 | t = XNEW (struct use_pred_info); | |
1746 | *t = *xj; | |
1747 | ||
9771b263 | 1748 | x[j] = t; |
56b67510 XDL |
1749 | } |
1750 | ||
1751 | for (i = 0; i < *n; i++) | |
1752 | { | |
1753 | pred_chain = preds[i]; | |
9771b263 DN |
1754 | for (j = 0; j < pred_chain.length (); j++) |
1755 | free (pred_chain[j]); | |
1756 | pred_chain.release (); | |
56b67510 | 1757 | /* A new chain. */ |
9771b263 | 1758 | pred_chain.safe_push (x[i]); |
56b67510 XDL |
1759 | preds[i] = pred_chain; |
1760 | } | |
1761 | return true; | |
1762 | } | |
1763 | ||
1764 | ||
1765 | ||
34f97b94 XDL |
1766 | /* Computes the predicates that guard the use and checks |
1767 | if the incoming paths that have empty (or possibly | |
073a8998 | 1768 | empty) definition can be pruned/filtered. The function returns |
34f97b94 XDL |
1769 | true if it can be determined that the use of PHI's def in |
1770 | USE_STMT is guarded with a predicate set not overlapping with | |
1771 | predicate sets of all runtime paths that do not have a definition. | |
1772 | Returns false if it is not or it can not be determined. USE_BB is | |
1773 | the bb of the use (for phi operand use, the bb is not the bb of | |
1774 | the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS | |
1775 | is a bit vector. If an operand of PHI is uninitialized, the | |
073a8998 | 1776 | corresponding bit in the vector is 1. VISIED_PHIS is a pointer |
34f97b94 XDL |
1777 | set of phis being visted. */ |
1778 | ||
1779 | static bool | |
1780 | is_use_properly_guarded (gimple use_stmt, | |
1781 | basic_block use_bb, | |
1782 | gimple phi, | |
1783 | unsigned uninit_opnds, | |
1784 | struct pointer_set_t *visited_phis) | |
1785 | { | |
1786 | basic_block phi_bb; | |
9771b263 DN |
1787 | vec<use_pred_info_t> *preds = 0; |
1788 | vec<use_pred_info_t> *def_preds = 0; | |
34f97b94 XDL |
1789 | size_t num_preds = 0, num_def_preds = 0; |
1790 | bool has_valid_preds = false; | |
1791 | bool is_properly_guarded = false; | |
1792 | ||
1793 | if (pointer_set_insert (visited_phis, phi)) | |
1794 | return false; | |
1795 | ||
1796 | phi_bb = gimple_bb (phi); | |
1797 | ||
1798 | if (is_non_loop_exit_postdominating (use_bb, phi_bb)) | |
1799 | return false; | |
1800 | ||
1801 | has_valid_preds = find_predicates (&preds, &num_preds, | |
1802 | phi_bb, use_bb); | |
1803 | ||
1804 | if (!has_valid_preds) | |
1805 | { | |
1806 | destroy_predicate_vecs (num_preds, preds); | |
1807 | return false; | |
1808 | } | |
1809 | ||
1810 | if (dump_file) | |
1811 | dump_predicates (use_stmt, num_preds, preds, | |
e74780a3 | 1812 | "\nUse in stmt "); |
34f97b94 XDL |
1813 | |
1814 | has_valid_preds = find_def_preds (&def_preds, | |
1815 | &num_def_preds, phi); | |
1816 | ||
1817 | if (has_valid_preds) | |
1818 | { | |
56b67510 | 1819 | bool normed; |
34f97b94 XDL |
1820 | if (dump_file) |
1821 | dump_predicates (phi, num_def_preds, def_preds, | |
1822 | "Operand defs of phi "); | |
56b67510 XDL |
1823 | |
1824 | normed = normalize_preds (def_preds, &num_def_preds); | |
1825 | if (normed && dump_file) | |
1826 | { | |
1827 | fprintf (dump_file, "\nNormalized to\n"); | |
1828 | dump_predicates (phi, num_def_preds, def_preds, | |
1829 | "Operand defs of phi "); | |
1830 | } | |
34f97b94 XDL |
1831 | is_properly_guarded = |
1832 | is_superset_of (def_preds, num_def_preds, | |
1833 | preds, num_preds); | |
1834 | } | |
1835 | ||
1836 | /* further prune the dead incoming phi edges. */ | |
1837 | if (!is_properly_guarded) | |
1838 | is_properly_guarded | |
1839 | = use_pred_not_overlap_with_undef_path_pred ( | |
1840 | num_preds, preds, phi, uninit_opnds, visited_phis); | |
1841 | ||
1842 | destroy_predicate_vecs (num_preds, preds); | |
1843 | destroy_predicate_vecs (num_def_preds, def_preds); | |
1844 | return is_properly_guarded; | |
1845 | } | |
1846 | ||
1847 | /* Searches through all uses of a potentially | |
1848 | uninitialized variable defined by PHI and returns a use | |
1849 | statement if the use is not properly guarded. It returns | |
1850 | NULL if all uses are guarded. UNINIT_OPNDS is a bitvector | |
1851 | holding the position(s) of uninit PHI operands. WORKLIST | |
1852 | is the vector of candidate phis that may be updated by this | |
1853 | function. ADDED_TO_WORKLIST is the pointer set tracking | |
1854 | if the new phi is already in the worklist. */ | |
1855 | ||
1856 | static gimple | |
1857 | find_uninit_use (gimple phi, unsigned uninit_opnds, | |
9771b263 | 1858 | vec<gimple> *worklist, |
34f97b94 XDL |
1859 | struct pointer_set_t *added_to_worklist) |
1860 | { | |
1861 | tree phi_result; | |
1862 | use_operand_p use_p; | |
1863 | gimple use_stmt; | |
1864 | imm_use_iterator iter; | |
1865 | ||
1866 | phi_result = gimple_phi_result (phi); | |
1867 | ||
1868 | FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result) | |
1869 | { | |
1870 | struct pointer_set_t *visited_phis; | |
1871 | basic_block use_bb; | |
1872 | ||
480161b5 RG |
1873 | use_stmt = USE_STMT (use_p); |
1874 | if (is_gimple_debug (use_stmt)) | |
1875 | continue; | |
34f97b94 XDL |
1876 | |
1877 | visited_phis = pointer_set_create (); | |
1878 | ||
34f97b94 | 1879 | if (gimple_code (use_stmt) == GIMPLE_PHI) |
480161b5 RG |
1880 | use_bb = gimple_phi_arg_edge (use_stmt, |
1881 | PHI_ARG_INDEX_FROM_USE (use_p))->src; | |
1882 | else | |
1883 | use_bb = gimple_bb (use_stmt); | |
34f97b94 XDL |
1884 | |
1885 | if (is_use_properly_guarded (use_stmt, | |
1886 | use_bb, | |
1887 | phi, | |
1888 | uninit_opnds, | |
1889 | visited_phis)) | |
1890 | { | |
1891 | pointer_set_destroy (visited_phis); | |
1892 | continue; | |
1893 | } | |
1894 | pointer_set_destroy (visited_phis); | |
1895 | ||
e74780a3 XDL |
1896 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1897 | { | |
1898 | fprintf (dump_file, "[CHECK]: Found unguarded use: "); | |
1899 | print_gimple_stmt (dump_file, use_stmt, 0, 0); | |
1900 | } | |
34f97b94 XDL |
1901 | /* Found one real use, return. */ |
1902 | if (gimple_code (use_stmt) != GIMPLE_PHI) | |
e74780a3 | 1903 | return use_stmt; |
34f97b94 XDL |
1904 | |
1905 | /* Found a phi use that is not guarded, | |
1906 | add the phi to the worklist. */ | |
1907 | if (!pointer_set_insert (added_to_worklist, | |
1908 | use_stmt)) | |
1909 | { | |
e74780a3 XDL |
1910 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1911 | { | |
1912 | fprintf (dump_file, "[WORKLIST]: Update worklist with phi: "); | |
1913 | print_gimple_stmt (dump_file, use_stmt, 0, 0); | |
1914 | } | |
1915 | ||
9771b263 DN |
1916 | worklist->safe_push (use_stmt); |
1917 | pointer_set_insert (possibly_undefined_names, phi_result); | |
34f97b94 XDL |
1918 | } |
1919 | } | |
1920 | ||
1921 | return NULL; | |
1922 | } | |
1923 | ||
1924 | /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions | |
1925 | and gives warning if there exists a runtime path from the entry to a | |
1926 | use of the PHI def that does not contain a definition. In other words, | |
1927 | the warning is on the real use. The more dead paths that can be pruned | |
1928 | by the compiler, the fewer false positives the warning is. WORKLIST | |
1929 | is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is | |
1930 | a pointer set tracking if the new phi is added to the worklist or not. */ | |
1931 | ||
1932 | static void | |
9771b263 | 1933 | warn_uninitialized_phi (gimple phi, vec<gimple> *worklist, |
34f97b94 XDL |
1934 | struct pointer_set_t *added_to_worklist) |
1935 | { | |
1936 | unsigned uninit_opnds; | |
1937 | gimple uninit_use_stmt = 0; | |
1938 | tree uninit_op; | |
1939 | ||
ea057359 RG |
1940 | /* Don't look at virtual operands. */ |
1941 | if (virtual_operand_p (gimple_phi_result (phi))) | |
34f97b94 XDL |
1942 | return; |
1943 | ||
1944 | uninit_opnds = compute_uninit_opnds_pos (phi); | |
1945 | ||
1946 | if (MASK_EMPTY (uninit_opnds)) | |
1947 | return; | |
1948 | ||
e74780a3 XDL |
1949 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1950 | { | |
1951 | fprintf (dump_file, "[CHECK]: examining phi: "); | |
1952 | print_gimple_stmt (dump_file, phi, 0, 0); | |
1953 | } | |
1954 | ||
34f97b94 XDL |
1955 | /* Now check if we have any use of the value without proper guard. */ |
1956 | uninit_use_stmt = find_uninit_use (phi, uninit_opnds, | |
1957 | worklist, added_to_worklist); | |
1958 | ||
1959 | /* All uses are properly guarded. */ | |
1960 | if (!uninit_use_stmt) | |
1961 | return; | |
1962 | ||
1963 | uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds)); | |
70b5e7dc RG |
1964 | if (SSA_NAME_VAR (uninit_op) == NULL_TREE) |
1965 | return; | |
8d2b0410 RG |
1966 | warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op), |
1967 | SSA_NAME_VAR (uninit_op), | |
34f97b94 XDL |
1968 | "%qD may be used uninitialized in this function", |
1969 | uninit_use_stmt); | |
1970 | ||
1971 | } | |
1972 | ||
1973 | ||
1974 | /* Entry point to the late uninitialized warning pass. */ | |
1975 | ||
1976 | static unsigned int | |
1977 | execute_late_warn_uninitialized (void) | |
1978 | { | |
1979 | basic_block bb; | |
1980 | gimple_stmt_iterator gsi; | |
6e1aa848 | 1981 | vec<gimple> worklist = vNULL; |
34f97b94 XDL |
1982 | struct pointer_set_t *added_to_worklist; |
1983 | ||
1984 | calculate_dominance_info (CDI_DOMINATORS); | |
1985 | calculate_dominance_info (CDI_POST_DOMINATORS); | |
1986 | /* Re-do the plain uninitialized variable check, as optimization may have | |
1987 | straightened control flow. Do this first so that we don't accidentally | |
1988 | get a "may be" warning when we'd have seen an "is" warning later. */ | |
1989 | warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1); | |
1990 | ||
1991 | timevar_push (TV_TREE_UNINIT); | |
1992 | ||
1993 | possibly_undefined_names = pointer_set_create (); | |
1994 | added_to_worklist = pointer_set_create (); | |
1995 | ||
1996 | /* Initialize worklist */ | |
1997 | FOR_EACH_BB (bb) | |
1998 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1999 | { | |
2000 | gimple phi = gsi_stmt (gsi); | |
2001 | size_t n, i; | |
2002 | ||
2003 | n = gimple_phi_num_args (phi); | |
2004 | ||
ea057359 RG |
2005 | /* Don't look at virtual operands. */ |
2006 | if (virtual_operand_p (gimple_phi_result (phi))) | |
34f97b94 XDL |
2007 | continue; |
2008 | ||
2009 | for (i = 0; i < n; ++i) | |
2010 | { | |
2011 | tree op = gimple_phi_arg_def (phi, i); | |
2012 | if (TREE_CODE (op) == SSA_NAME | |
ba7e83f8 | 2013 | && uninit_undefined_value_p (op)) |
34f97b94 | 2014 | { |
9771b263 | 2015 | worklist.safe_push (phi); |
34f97b94 | 2016 | pointer_set_insert (added_to_worklist, phi); |
e74780a3 XDL |
2017 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2018 | { | |
2019 | fprintf (dump_file, "[WORKLIST]: add to initial list: "); | |
2020 | print_gimple_stmt (dump_file, phi, 0, 0); | |
2021 | } | |
34f97b94 XDL |
2022 | break; |
2023 | } | |
2024 | } | |
2025 | } | |
2026 | ||
9771b263 | 2027 | while (worklist.length () != 0) |
34f97b94 XDL |
2028 | { |
2029 | gimple cur_phi = 0; | |
9771b263 | 2030 | cur_phi = worklist.pop (); |
34f97b94 XDL |
2031 | warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist); |
2032 | } | |
e74780a3 | 2033 | |
9771b263 | 2034 | worklist.release (); |
34f97b94 XDL |
2035 | pointer_set_destroy (added_to_worklist); |
2036 | pointer_set_destroy (possibly_undefined_names); | |
2037 | possibly_undefined_names = NULL; | |
2038 | free_dominance_info (CDI_POST_DOMINATORS); | |
2039 | timevar_pop (TV_TREE_UNINIT); | |
2040 | return 0; | |
2041 | } | |
2042 | ||
2043 | static bool | |
2044 | gate_warn_uninitialized (void) | |
2045 | { | |
2046 | return warn_uninitialized != 0; | |
2047 | } | |
2048 | ||
2049 | struct gimple_opt_pass pass_late_warn_uninitialized = | |
2050 | { | |
2051 | { | |
2052 | GIMPLE_PASS, | |
2053 | "uninit", /* name */ | |
2b4e6bf1 | 2054 | OPTGROUP_NONE, /* optinfo_flags */ |
34f97b94 XDL |
2055 | gate_warn_uninitialized, /* gate */ |
2056 | execute_late_warn_uninitialized, /* execute */ | |
2057 | NULL, /* sub */ | |
2058 | NULL, /* next */ | |
2059 | 0, /* static_pass_number */ | |
2060 | TV_NONE, /* tv_id */ | |
2061 | PROP_ssa, /* properties_required */ | |
2062 | 0, /* properties_provided */ | |
2063 | 0, /* properties_destroyed */ | |
2064 | 0, /* todo_flags_start */ | |
2065 | 0 /* todo_flags_finish */ | |
2066 | } | |
2067 | }; |