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