]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Miscellaneous SSA utility functions. |
ad616de1 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
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" | |
27 | #include "rtl.h" | |
28 | #include "tm_p.h" | |
29 | #include "ggc.h" | |
30 | #include "langhooks.h" | |
31 | #include "hard-reg-set.h" | |
32 | #include "basic-block.h" | |
33 | #include "output.h" | |
34 | #include "errors.h" | |
35 | #include "expr.h" | |
36 | #include "function.h" | |
37 | #include "diagnostic.h" | |
38 | #include "bitmap.h" | |
d0ce8e4c | 39 | #include "pointer-set.h" |
6de9cd9a | 40 | #include "tree-flow.h" |
eadf906f | 41 | #include "tree-gimple.h" |
6de9cd9a DN |
42 | #include "tree-inline.h" |
43 | #include "varray.h" | |
44 | #include "timevar.h" | |
6de9cd9a DN |
45 | #include "hashtab.h" |
46 | #include "tree-dump.h" | |
47 | #include "tree-pass.h" | |
48 | ||
f6144c34 BE |
49 | /* Remove the corresponding arguments from the PHI nodes in E's |
50 | destination block and redirect it to DEST. Return redirected edge. | |
6de9cd9a DN |
51 | The list of removed arguments is stored in PENDING_STMT (e). */ |
52 | ||
53 | edge | |
54 | ssa_redirect_edge (edge e, basic_block dest) | |
55 | { | |
52c3e649 | 56 | tree phi; |
6de9cd9a DN |
57 | tree list = NULL, *last = &list; |
58 | tree src, dst, node; | |
6de9cd9a DN |
59 | |
60 | /* Remove the appropriate PHI arguments in E's destination block. */ | |
52c3e649 | 61 | for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a | 62 | { |
3a2f1f06 | 63 | if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE) |
6de9cd9a DN |
64 | continue; |
65 | ||
3a2f1f06 | 66 | src = PHI_ARG_DEF (phi, e->dest_idx); |
6de9cd9a DN |
67 | dst = PHI_RESULT (phi); |
68 | node = build_tree_list (dst, src); | |
69 | *last = node; | |
70 | last = &TREE_CHAIN (node); | |
6de9cd9a DN |
71 | } |
72 | ||
73 | e = redirect_edge_succ_nodup (e, dest); | |
74 | PENDING_STMT (e) = list; | |
75 | ||
76 | return e; | |
77 | } | |
78 | ||
71882046 KH |
79 | /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge |
80 | E->dest. */ | |
81 | ||
82 | void | |
83 | flush_pending_stmts (edge e) | |
84 | { | |
85 | tree phi, arg; | |
86 | ||
87 | if (!PENDING_STMT (e)) | |
88 | return; | |
89 | ||
90 | for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e); | |
91 | phi; | |
bb29d951 | 92 | phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg)) |
71882046 KH |
93 | { |
94 | tree def = TREE_VALUE (arg); | |
d2e398df | 95 | add_phi_arg (phi, def, e); |
71882046 KH |
96 | } |
97 | ||
98 | PENDING_STMT (e) = NULL; | |
99 | } | |
6de9cd9a | 100 | |
53b4bf74 | 101 | /* Return true if SSA_NAME is malformed and mark it visited. |
6de9cd9a | 102 | |
53b4bf74 DN |
103 | IS_VIRTUAL is true if this SSA_NAME was found inside a virtual |
104 | operand. */ | |
6de9cd9a DN |
105 | |
106 | static bool | |
53b4bf74 | 107 | verify_ssa_name (tree ssa_name, bool is_virtual) |
6de9cd9a | 108 | { |
6de9cd9a DN |
109 | if (TREE_CODE (ssa_name) != SSA_NAME) |
110 | { | |
111 | error ("Expected an SSA_NAME object"); | |
53b4bf74 | 112 | return true; |
6de9cd9a DN |
113 | } |
114 | ||
bbc630f5 DN |
115 | if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name))) |
116 | { | |
117 | error ("Type mismatch between an SSA_NAME and its symbol."); | |
118 | return true; | |
119 | } | |
120 | ||
53b4bf74 DN |
121 | if (SSA_NAME_IN_FREE_LIST (ssa_name)) |
122 | { | |
123 | error ("Found an SSA_NAME that had been released into the free pool"); | |
124 | return true; | |
125 | } | |
126 | ||
127 | if (is_virtual && is_gimple_reg (ssa_name)) | |
128 | { | |
129 | error ("Found a virtual definition for a GIMPLE register"); | |
130 | return true; | |
131 | } | |
132 | ||
133 | if (!is_virtual && !is_gimple_reg (ssa_name)) | |
134 | { | |
135 | error ("Found a real definition for a non-register"); | |
136 | return true; | |
137 | } | |
138 | ||
d19e9499 DB |
139 | if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name)) |
140 | && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL) | |
141 | { | |
142 | error ("Found real variable when subvariables should have appeared"); | |
143 | return true; | |
144 | } | |
145 | ||
53b4bf74 DN |
146 | return false; |
147 | } | |
148 | ||
149 | ||
150 | /* Return true if the definition of SSA_NAME at block BB is malformed. | |
151 | ||
152 | STMT is the statement where SSA_NAME is created. | |
153 | ||
154 | DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME | |
155 | version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, | |
156 | it means that the block in that array slot contains the | |
157 | definition of SSA_NAME. | |
158 | ||
159 | IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a | |
160 | V_MUST_DEF. */ | |
161 | ||
162 | static bool | |
163 | verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, | |
164 | tree stmt, bool is_virtual) | |
165 | { | |
166 | if (verify_ssa_name (ssa_name, is_virtual)) | |
167 | goto err; | |
168 | ||
6de9cd9a DN |
169 | if (definition_block[SSA_NAME_VERSION (ssa_name)]) |
170 | { | |
171 | error ("SSA_NAME created in two different blocks %i and %i", | |
172 | definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index); | |
53b4bf74 | 173 | goto err; |
6de9cd9a DN |
174 | } |
175 | ||
176 | definition_block[SSA_NAME_VERSION (ssa_name)] = bb; | |
177 | ||
178 | if (SSA_NAME_DEF_STMT (ssa_name) != stmt) | |
179 | { | |
180 | error ("SSA_NAME_DEF_STMT is wrong"); | |
6de9cd9a | 181 | fprintf (stderr, "Expected definition statement:\n"); |
7bab95ba | 182 | print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS); |
6de9cd9a | 183 | fprintf (stderr, "\nActual definition statement:\n"); |
7bab95ba | 184 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
53b4bf74 | 185 | goto err; |
6de9cd9a DN |
186 | } |
187 | ||
53b4bf74 DN |
188 | return false; |
189 | ||
190 | err: | |
191 | fprintf (stderr, "while verifying SSA_NAME "); | |
192 | print_generic_expr (stderr, ssa_name, 0); | |
193 | fprintf (stderr, " in statement\n"); | |
7bab95ba | 194 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
53b4bf74 DN |
195 | |
196 | return true; | |
6de9cd9a DN |
197 | } |
198 | ||
199 | ||
200 | /* Return true if the use of SSA_NAME at statement STMT in block BB is | |
201 | malformed. | |
202 | ||
203 | DEF_BB is the block where SSA_NAME was found to be created. | |
204 | ||
205 | IDOM contains immediate dominator information for the flowgraph. | |
206 | ||
207 | CHECK_ABNORMAL is true if the caller wants to check whether this use | |
208 | is flowing through an abnormal edge (only used when checking PHI | |
53b4bf74 DN |
209 | arguments). |
210 | ||
211 | IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a | |
b1d16eff ZD |
212 | V_MUST_DEF. |
213 | ||
214 | If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names | |
215 | that are defined before STMT in basic block BB. */ | |
6de9cd9a DN |
216 | |
217 | static bool | |
f430bae8 | 218 | verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p, |
b1d16eff ZD |
219 | tree stmt, bool check_abnormal, bool is_virtual, |
220 | bitmap names_defined_in_bb) | |
6de9cd9a DN |
221 | { |
222 | bool err = false; | |
f430bae8 | 223 | tree ssa_name = USE_FROM_PTR (use_p); |
6de9cd9a | 224 | |
53b4bf74 | 225 | err = verify_ssa_name (ssa_name, is_virtual); |
f430bae8 AM |
226 | |
227 | if (!TREE_VISITED (ssa_name)) | |
228 | if (verify_imm_links (stderr, ssa_name)) | |
229 | err = true; | |
230 | ||
28a3618f | 231 | TREE_VISITED (ssa_name) = 1; |
53b4bf74 DN |
232 | |
233 | if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)) | |
234 | && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name) | |
235 | ; /* Default definitions have empty statements. Nothing to do. */ | |
6de9cd9a DN |
236 | else if (!def_bb) |
237 | { | |
238 | error ("Missing definition"); | |
239 | err = true; | |
240 | } | |
241 | else if (bb != def_bb | |
242 | && !dominated_by_p (CDI_DOMINATORS, bb, def_bb)) | |
243 | { | |
244 | error ("Definition in block %i does not dominate use in block %i", | |
245 | def_bb->index, bb->index); | |
246 | err = true; | |
247 | } | |
b1d16eff ZD |
248 | else if (bb == def_bb |
249 | && names_defined_in_bb != NULL | |
250 | && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name))) | |
251 | { | |
252 | error ("Definition in block %i follows the use", def_bb->index); | |
253 | err = true; | |
254 | } | |
6de9cd9a DN |
255 | |
256 | if (check_abnormal | |
257 | && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name)) | |
258 | { | |
259 | error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set"); | |
260 | err = true; | |
261 | } | |
262 | ||
f430bae8 | 263 | /* Make sure the use is in an appropriate list by checking the previous |
f3b569ca | 264 | element to make sure it's the same. */ |
f430bae8 AM |
265 | if (use_p->prev == NULL) |
266 | { | |
267 | error ("No immediate_use list"); | |
268 | err = true; | |
269 | } | |
270 | else | |
271 | { | |
272 | tree listvar ; | |
273 | if (use_p->prev->use == NULL) | |
274 | listvar = use_p->prev->stmt; | |
275 | else | |
276 | listvar = USE_FROM_PTR (use_p->prev); | |
277 | if (listvar != ssa_name) | |
278 | { | |
279 | error ("Wrong immediate use list"); | |
280 | err = true; | |
281 | } | |
282 | } | |
283 | ||
6de9cd9a DN |
284 | if (err) |
285 | { | |
286 | fprintf (stderr, "for SSA_NAME: "); | |
7bab95ba | 287 | print_generic_expr (stderr, ssa_name, TDF_VOPS); |
0bca51f0 | 288 | fprintf (stderr, " in statement:\n"); |
7bab95ba | 289 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
6de9cd9a DN |
290 | } |
291 | ||
292 | return err; | |
293 | } | |
294 | ||
295 | ||
296 | /* Return true if any of the arguments for PHI node PHI at block BB is | |
297 | malformed. | |
298 | ||
6de9cd9a DN |
299 | DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version |
300 | numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the | |
301 | block in that array slot contains the definition of SSA_NAME. */ | |
302 | ||
303 | static bool | |
304 | verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) | |
305 | { | |
306 | edge e; | |
307 | bool err = false; | |
609d9bed | 308 | unsigned i, phi_num_args = PHI_NUM_ARGS (phi); |
6de9cd9a | 309 | |
609d9bed JL |
310 | if (EDGE_COUNT (bb->preds) != phi_num_args) |
311 | { | |
312 | error ("Incoming edge count does not match number of PHI arguments\n"); | |
313 | err = true; | |
314 | goto error; | |
315 | } | |
316 | ||
6de9cd9a DN |
317 | for (i = 0; i < phi_num_args; i++) |
318 | { | |
f430bae8 AM |
319 | use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i); |
320 | tree op = USE_FROM_PTR (op_p); | |
321 | ||
6de9cd9a | 322 | |
62112e35 | 323 | e = EDGE_PRED (bb, i); |
6b66c718 KH |
324 | |
325 | if (op == NULL_TREE) | |
326 | { | |
327 | error ("PHI argument is missing for edge %d->%d\n", | |
328 | e->src->index, | |
329 | e->dest->index); | |
330 | err = true; | |
331 | goto error; | |
332 | } | |
333 | ||
609d9bed JL |
334 | if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op)) |
335 | { | |
336 | error ("PHI argument is not SSA_NAME, or invariant"); | |
337 | err = true; | |
338 | } | |
339 | ||
6de9cd9a | 340 | if (TREE_CODE (op) == SSA_NAME) |
f430bae8 | 341 | err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p, |
53b4bf74 | 342 | phi, e->flags & EDGE_ABNORMAL, |
b1d16eff ZD |
343 | !is_gimple_reg (PHI_RESULT (phi)), |
344 | NULL); | |
6de9cd9a DN |
345 | |
346 | if (e->dest != bb) | |
347 | { | |
348 | error ("Wrong edge %d->%d for PHI argument\n", | |
349 | e->src->index, e->dest->index, bb->index); | |
350 | err = true; | |
351 | } | |
352 | ||
6de9cd9a DN |
353 | if (err) |
354 | { | |
355 | fprintf (stderr, "PHI argument\n"); | |
7bab95ba | 356 | print_generic_stmt (stderr, op, TDF_VOPS); |
53b4bf74 | 357 | goto error; |
6de9cd9a | 358 | } |
6de9cd9a DN |
359 | } |
360 | ||
53b4bf74 | 361 | error: |
6de9cd9a DN |
362 | if (err) |
363 | { | |
364 | fprintf (stderr, "for PHI node\n"); | |
7bab95ba | 365 | print_generic_stmt (stderr, phi, TDF_VOPS); |
6de9cd9a DN |
366 | } |
367 | ||
368 | ||
369 | return err; | |
370 | } | |
371 | ||
372 | ||
53b4bf74 DN |
373 | static void |
374 | verify_flow_insensitive_alias_info (void) | |
375 | { | |
376 | size_t i; | |
377 | tree var; | |
8bdbfff5 | 378 | bitmap visited = BITMAP_ALLOC (NULL); |
53b4bf74 DN |
379 | |
380 | for (i = 0; i < num_referenced_vars; i++) | |
381 | { | |
852c7b12 | 382 | size_t j; |
53b4bf74 | 383 | var_ann_t ann; |
852c7b12 | 384 | varray_type may_aliases; |
53b4bf74 DN |
385 | |
386 | var = referenced_var (i); | |
387 | ann = var_ann (var); | |
852c7b12 | 388 | may_aliases = ann->may_aliases; |
53b4bf74 | 389 | |
852c7b12 | 390 | for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++) |
53b4bf74 | 391 | { |
852c7b12 | 392 | tree alias = VARRAY_TREE (may_aliases, j); |
53b4bf74 | 393 | |
852c7b12 | 394 | bitmap_set_bit (visited, var_ann (alias)->uid); |
53b4bf74 | 395 | |
852c7b12 DN |
396 | if (!may_be_aliased (alias)) |
397 | { | |
398 | error ("Non-addressable variable inside an alias set."); | |
399 | debug_variable (alias); | |
400 | goto err; | |
53b4bf74 DN |
401 | } |
402 | } | |
403 | } | |
404 | ||
405 | for (i = 0; i < num_referenced_vars; i++) | |
406 | { | |
407 | var_ann_t ann; | |
408 | ||
409 | var = referenced_var (i); | |
410 | ann = var_ann (var); | |
411 | ||
412 | if (ann->mem_tag_kind == NOT_A_TAG | |
413 | && ann->is_alias_tag | |
414 | && !bitmap_bit_p (visited, ann->uid)) | |
415 | { | |
416 | error ("Addressable variable that is an alias tag but is not in any alias set."); | |
417 | goto err; | |
418 | } | |
419 | } | |
420 | ||
8bdbfff5 | 421 | BITMAP_FREE (visited); |
53b4bf74 DN |
422 | return; |
423 | ||
424 | err: | |
425 | debug_variable (var); | |
426 | internal_error ("verify_flow_insensitive_alias_info failed."); | |
427 | } | |
428 | ||
429 | ||
430 | static void | |
431 | verify_flow_sensitive_alias_info (void) | |
432 | { | |
433 | size_t i; | |
434 | tree ptr; | |
435 | ||
436 | for (i = 1; i < num_ssa_names; i++) | |
437 | { | |
b5c3569b | 438 | tree var; |
53b4bf74 DN |
439 | var_ann_t ann; |
440 | struct ptr_info_def *pi; | |
b5c3569b | 441 | |
53b4bf74 DN |
442 | |
443 | ptr = ssa_name (i); | |
8b547e44 JH |
444 | if (!ptr) |
445 | continue; | |
53b4bf74 DN |
446 | |
447 | /* We only care for pointers that are actually referenced in the | |
448 | program. */ | |
b5c3569b | 449 | if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) |
53b4bf74 DN |
450 | continue; |
451 | ||
452 | /* RESULT_DECL is special. If it's a GIMPLE register, then it | |
453 | is only written-to only once in the return statement. | |
454 | Otherwise, aggregate RESULT_DECLs may be written-to more than | |
455 | once in virtual operands. */ | |
b5c3569b JL |
456 | var = SSA_NAME_VAR (ptr); |
457 | if (TREE_CODE (var) == RESULT_DECL | |
53b4bf74 DN |
458 | && is_gimple_reg (ptr)) |
459 | continue; | |
460 | ||
b5c3569b | 461 | pi = SSA_NAME_PTR_INFO (ptr); |
53b4bf74 DN |
462 | if (pi == NULL) |
463 | continue; | |
464 | ||
b5c3569b | 465 | ann = var_ann (var); |
53b4bf74 DN |
466 | if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag) |
467 | { | |
468 | error ("Dereferenced pointers should have a name or a type tag"); | |
469 | goto err; | |
470 | } | |
471 | ||
53b4bf74 DN |
472 | if (pi->name_mem_tag |
473 | && !pi->pt_malloc | |
eb59b8de | 474 | && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) |
53b4bf74 DN |
475 | { |
476 | error ("Pointers with a memory tag, should have points-to sets or point to malloc"); | |
477 | goto err; | |
478 | } | |
479 | ||
480 | if (pi->value_escapes_p | |
481 | && pi->name_mem_tag | |
482 | && !is_call_clobbered (pi->name_mem_tag)) | |
483 | { | |
484 | error ("Pointer escapes but its name tag is not call-clobbered."); | |
485 | goto err; | |
486 | } | |
53b4bf74 DN |
487 | } |
488 | ||
489 | return; | |
490 | ||
491 | err: | |
492 | debug_variable (ptr); | |
493 | internal_error ("verify_flow_sensitive_alias_info failed."); | |
494 | } | |
495 | ||
7dcdacad DB |
496 | DEF_VEC_MALLOC_P (bitmap); |
497 | ||
498 | /* Verify that all name tags have different points to sets. | |
499 | This algorithm takes advantage of the fact that every variable with the | |
500 | same name tag must have the same points-to set. | |
3d4818fd | 501 | So we check a single variable for each name tag, and verify that its |
7dcdacad | 502 | points-to set is different from every other points-to set for other name |
e03a46f5 DN |
503 | tags. |
504 | ||
505 | Additionally, given a pointer P_i with name tag NMT and type tag | |
506 | TMT, this function verified the alias set of TMT is a superset of | |
507 | the alias set of NMT. */ | |
7dcdacad DB |
508 | |
509 | static void | |
510 | verify_name_tags (void) | |
511 | { | |
512 | size_t i; | |
513 | size_t j; | |
514 | bitmap first, second; | |
515 | VEC (tree) *name_tag_reps = NULL; | |
516 | VEC (bitmap) *pt_vars_for_reps = NULL; | |
8bdbfff5 | 517 | bitmap type_aliases = BITMAP_ALLOC (NULL); |
7dcdacad DB |
518 | |
519 | /* First we compute the name tag representatives and their points-to sets. */ | |
520 | for (i = 0; i < num_ssa_names; i++) | |
521 | { | |
e03a46f5 DN |
522 | struct ptr_info_def *pi; |
523 | tree tmt, ptr = ssa_name (i); | |
524 | ||
525 | if (ptr == NULL_TREE) | |
526 | continue; | |
527 | ||
528 | pi = SSA_NAME_PTR_INFO (ptr); | |
529 | ||
530 | if (!TREE_VISITED (ptr) | |
531 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
532 | || !pi | |
533 | || !pi->name_mem_tag | |
534 | || TREE_VISITED (pi->name_mem_tag)) | |
535 | continue; | |
536 | ||
537 | TREE_VISITED (pi->name_mem_tag) = 1; | |
538 | ||
539 | if (pi->pt_vars == NULL) | |
540 | continue; | |
541 | ||
542 | VEC_safe_push (tree, name_tag_reps, ptr); | |
543 | VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars); | |
544 | ||
545 | /* Verify that alias set of PTR's type tag is a superset of the | |
546 | alias set of PTR's name tag. */ | |
547 | tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; | |
548 | if (tmt) | |
7dcdacad | 549 | { |
e03a46f5 DN |
550 | size_t i; |
551 | varray_type aliases = var_ann (tmt)->may_aliases; | |
552 | bitmap_clear (type_aliases); | |
553 | for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
554 | { | |
555 | tree alias = VARRAY_TREE (aliases, i); | |
556 | bitmap_set_bit (type_aliases, var_ann (alias)->uid); | |
557 | } | |
558 | ||
559 | /* When grouping, we may have added PTR's type tag into the | |
560 | alias set of PTR's name tag. To prevent a false | |
561 | positive, pretend that TMT is in its own alias set. */ | |
562 | bitmap_set_bit (type_aliases, var_ann (tmt)->uid); | |
563 | ||
564 | if (bitmap_equal_p (type_aliases, pi->pt_vars)) | |
7dcdacad | 565 | continue; |
e03a46f5 DN |
566 | |
567 | if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) | |
568 | { | |
569 | error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag"); | |
570 | debug_variable (tmt); | |
571 | debug_variable (pi->name_mem_tag); | |
572 | goto err; | |
7dcdacad DB |
573 | } |
574 | } | |
575 | } | |
576 | ||
577 | /* Now compare all the representative bitmaps with all other representative | |
578 | bitmaps, to verify that they are all different. */ | |
579 | for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) | |
580 | { | |
581 | for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) | |
582 | { | |
583 | if (bitmap_equal_p (first, second)) | |
584 | { | |
585 | error ("Two different pointers with identical points-to sets but different name tags"); | |
586 | debug_variable (VEC_index (tree, name_tag_reps, j)); | |
587 | goto err; | |
588 | } | |
589 | } | |
590 | } | |
53b4bf74 | 591 | |
7dcdacad DB |
592 | /* Lastly, clear out the visited flags. */ |
593 | for (i = 0; i < num_ssa_names; i++) | |
594 | { | |
595 | if (ssa_name (i)) | |
596 | { | |
597 | tree ptr = ssa_name (i); | |
598 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
599 | if (!TREE_VISITED (ptr) | |
600 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
601 | || !pi | |
602 | || !pi->name_mem_tag) | |
603 | continue; | |
604 | TREE_VISITED (pi->name_mem_tag) = 0; | |
605 | } | |
606 | } | |
e03a46f5 | 607 | |
7dcdacad | 608 | VEC_free (bitmap, pt_vars_for_reps); |
e03a46f5 | 609 | BITMAP_FREE (type_aliases); |
7dcdacad DB |
610 | return; |
611 | ||
612 | err: | |
613 | debug_variable (VEC_index (tree, name_tag_reps, i)); | |
614 | internal_error ("verify_name_tags failed"); | |
615 | } | |
e03a46f5 DN |
616 | |
617 | ||
53b4bf74 DN |
618 | /* Verify the consistency of aliasing information. */ |
619 | ||
620 | static void | |
621 | verify_alias_info (void) | |
622 | { | |
c1b763fa | 623 | verify_flow_sensitive_alias_info (); |
7dcdacad | 624 | verify_name_tags (); |
c1b763fa | 625 | verify_flow_insensitive_alias_info (); |
53b4bf74 DN |
626 | } |
627 | ||
628 | ||
6de9cd9a DN |
629 | /* Verify common invariants in the SSA web. |
630 | TODO: verify the variable annotations. */ | |
631 | ||
632 | void | |
f430bae8 | 633 | verify_ssa (bool check_modified_stmt) |
6de9cd9a | 634 | { |
53b4bf74 | 635 | size_t i; |
6de9cd9a | 636 | basic_block bb; |
95a3742c | 637 | basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block)); |
4c124b4c AM |
638 | ssa_op_iter iter; |
639 | tree op; | |
03261822 | 640 | enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; |
8bdbfff5 | 641 | bitmap names_defined_in_bb = BITMAP_ALLOC (NULL); |
6de9cd9a DN |
642 | |
643 | timevar_push (TV_TREE_SSA_VERIFY); | |
644 | ||
53b4bf74 DN |
645 | /* Keep track of SSA names present in the IL. */ |
646 | for (i = 1; i < num_ssa_names; i++) | |
6de9cd9a | 647 | { |
609d9bed JL |
648 | tree name = ssa_name (i); |
649 | if (name) | |
6de9cd9a DN |
650 | { |
651 | tree stmt; | |
609d9bed | 652 | TREE_VISITED (name) = 0; |
6de9cd9a | 653 | |
609d9bed JL |
654 | stmt = SSA_NAME_DEF_STMT (name); |
655 | if (!IS_EMPTY_STMT (stmt)) | |
53b4bf74 | 656 | { |
609d9bed JL |
657 | basic_block bb = bb_for_stmt (stmt); |
658 | verify_def (bb, definition_block, | |
659 | name, stmt, !is_gimple_reg (name)); | |
660 | ||
6de9cd9a DN |
661 | } |
662 | } | |
663 | } | |
664 | ||
609d9bed | 665 | calculate_dominance_info (CDI_DOMINATORS); |
6de9cd9a DN |
666 | |
667 | /* Now verify all the uses and make sure they agree with the definitions | |
668 | found in the previous pass. */ | |
669 | FOR_EACH_BB (bb) | |
670 | { | |
671 | edge e; | |
672 | tree phi; | |
628f6a4e | 673 | edge_iterator ei; |
6de9cd9a DN |
674 | block_stmt_iterator bsi; |
675 | ||
676 | /* Make sure that all edges have a clear 'aux' field. */ | |
628f6a4e | 677 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
678 | { |
679 | if (e->aux) | |
680 | { | |
681 | error ("AUX pointer initialized for edge %d->%d\n", e->src->index, | |
682 | e->dest->index); | |
53b4bf74 | 683 | goto err; |
6de9cd9a DN |
684 | } |
685 | } | |
686 | ||
687 | /* Verify the arguments for every PHI node in the block. */ | |
17192884 | 688 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
b1d16eff ZD |
689 | { |
690 | if (verify_phi_args (phi, bb, definition_block)) | |
691 | goto err; | |
692 | bitmap_set_bit (names_defined_in_bb, | |
693 | SSA_NAME_VERSION (PHI_RESULT (phi))); | |
694 | } | |
6de9cd9a | 695 | |
53b4bf74 | 696 | /* Now verify all the uses and vuses in every statement of the block. */ |
6de9cd9a DN |
697 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
698 | { | |
699 | tree stmt = bsi_stmt (bsi); | |
f430bae8 AM |
700 | use_operand_p use_p; |
701 | ||
702 | if (check_modified_stmt && stmt_modified_p (stmt)) | |
703 | { | |
704 | error ("Stmt (0x%x) marked modified after optimization pass : ", | |
705 | (unsigned long)stmt); | |
706 | print_generic_stmt (stderr, stmt, TDF_VOPS); | |
707 | goto err; | |
708 | } | |
6de9cd9a | 709 | |
f8d66d34 DN |
710 | if (TREE_CODE (stmt) == MODIFY_EXPR |
711 | && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) | |
712 | { | |
713 | tree lhs, base_address; | |
714 | ||
715 | lhs = TREE_OPERAND (stmt, 0); | |
716 | base_address = get_base_address (lhs); | |
609d9bed | 717 | |
f8d66d34 DN |
718 | if (base_address |
719 | && SSA_VAR_P (base_address) | |
720 | && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0 | |
721 | && NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) == 0) | |
609d9bed | 722 | { |
f8d66d34 DN |
723 | error ("Statement makes a memory store, but has no " |
724 | "V_MAY_DEFS nor V_MUST_DEFS"); | |
609d9bed JL |
725 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
726 | goto err; | |
727 | } | |
f8d66d34 DN |
728 | } |
729 | ||
730 | ||
731 | if (stmt_ann (stmt)->makes_aliased_stores | |
732 | && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0) | |
733 | { | |
734 | error ("Statement makes aliased stores, but has no V_MAY_DEFS"); | |
735 | print_generic_stmt (stderr, stmt, TDF_VOPS); | |
736 | goto err; | |
737 | } | |
6de9cd9a | 738 | |
f8d66d34 DN |
739 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, |
740 | SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) | |
6de9cd9a | 741 | { |
f430bae8 | 742 | op = USE_FROM_PTR (use_p); |
53b4bf74 | 743 | if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], |
f430bae8 | 744 | use_p, stmt, false, !is_gimple_reg (op), |
b1d16eff ZD |
745 | names_defined_in_bb)) |
746 | goto err; | |
747 | } | |
748 | ||
749 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) | |
750 | { | |
751 | bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); | |
752 | } | |
753 | } | |
754 | ||
b1d16eff | 755 | bitmap_clear (names_defined_in_bb); |
6de9cd9a DN |
756 | } |
757 | ||
53b4bf74 DN |
758 | /* Finally, verify alias information. */ |
759 | verify_alias_info (); | |
6de9cd9a | 760 | |
53b4bf74 | 761 | free (definition_block); |
b01d837f KH |
762 | /* Restore the dominance information to its prior known state, so |
763 | that we do not perturb the compiler's subsequent behavior. */ | |
03261822 NS |
764 | if (orig_dom_state == DOM_NONE) |
765 | free_dominance_info (CDI_DOMINATORS); | |
766 | else | |
767 | dom_computed[CDI_DOMINATORS] = orig_dom_state; | |
768 | ||
8bdbfff5 | 769 | BITMAP_FREE (names_defined_in_bb); |
6de9cd9a | 770 | timevar_pop (TV_TREE_SSA_VERIFY); |
53b4bf74 | 771 | return; |
6de9cd9a | 772 | |
53b4bf74 DN |
773 | err: |
774 | internal_error ("verify_ssa failed."); | |
6de9cd9a DN |
775 | } |
776 | ||
777 | ||
6de9cd9a DN |
778 | /* Initialize global DFA and SSA structures. */ |
779 | ||
780 | void | |
781 | init_tree_ssa (void) | |
782 | { | |
783 | VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars"); | |
8bdbfff5 NS |
784 | call_clobbered_vars = BITMAP_ALLOC (NULL); |
785 | addressable_vars = BITMAP_ALLOC (NULL); | |
6de9cd9a DN |
786 | init_ssanames (); |
787 | init_phinodes (); | |
788 | global_var = NULL_TREE; | |
90c1d75a | 789 | aliases_computed_p = false; |
6de9cd9a DN |
790 | } |
791 | ||
792 | ||
793 | /* Deallocate memory associated with SSA data structures for FNDECL. */ | |
794 | ||
795 | void | |
796 | delete_tree_ssa (void) | |
797 | { | |
798 | size_t i; | |
799 | basic_block bb; | |
800 | block_stmt_iterator bsi; | |
801 | ||
802 | /* Remove annotations from every tree in the function. */ | |
803 | FOR_EACH_BB (bb) | |
804 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
80d8221e JH |
805 | { |
806 | tree stmt = bsi_stmt (bsi); | |
807 | release_defs (stmt); | |
808 | ggc_free (stmt->common.ann); | |
809 | stmt->common.ann = NULL; | |
810 | } | |
6de9cd9a DN |
811 | |
812 | /* Remove annotations from every referenced variable. */ | |
813 | if (referenced_vars) | |
814 | { | |
815 | for (i = 0; i < num_referenced_vars; i++) | |
80d8221e JH |
816 | { |
817 | tree var = referenced_var (i); | |
818 | ggc_free (var->common.ann); | |
819 | var->common.ann = NULL; | |
820 | } | |
6de9cd9a DN |
821 | referenced_vars = NULL; |
822 | } | |
823 | ||
824 | fini_ssanames (); | |
825 | fini_phinodes (); | |
6de9cd9a DN |
826 | |
827 | global_var = NULL_TREE; | |
8bdbfff5 | 828 | BITMAP_FREE (call_clobbered_vars); |
6de9cd9a | 829 | call_clobbered_vars = NULL; |
8bdbfff5 | 830 | BITMAP_FREE (addressable_vars); |
a6d02559 | 831 | addressable_vars = NULL; |
7ded35b4 | 832 | modified_noreturn_calls = NULL; |
90c1d75a | 833 | aliases_computed_p = false; |
6de9cd9a DN |
834 | } |
835 | ||
836 | ||
837 | /* Return true if EXPR is a useless type conversion, otherwise return | |
838 | false. */ | |
839 | ||
840 | bool | |
841 | tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) | |
842 | { | |
4f380bf8 RS |
843 | if (inner_type == outer_type) |
844 | return true; | |
845 | ||
846 | /* Changes in machine mode are never useless conversions. */ | |
847 | if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type)) | |
848 | return false; | |
849 | ||
6de9cd9a DN |
850 | /* If the inner and outer types are effectively the same, then |
851 | strip the type conversion and enter the equivalence into | |
852 | the table. */ | |
4f380bf8 | 853 | if (lang_hooks.types_compatible_p (inner_type, outer_type)) |
6de9cd9a DN |
854 | return true; |
855 | ||
856 | /* If both types are pointers and the outer type is a (void *), then | |
857 | the conversion is not necessary. The opposite is not true since | |
858 | that conversion would result in a loss of information if the | |
859 | equivalence was used. Consider an indirect function call where | |
860 | we need to know the exact type of the function to correctly | |
861 | implement the ABI. */ | |
862 | else if (POINTER_TYPE_P (inner_type) | |
863 | && POINTER_TYPE_P (outer_type) | |
106f5de5 UW |
864 | && TYPE_REF_CAN_ALIAS_ALL (inner_type) |
865 | == TYPE_REF_CAN_ALIAS_ALL (outer_type) | |
6de9cd9a DN |
866 | && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) |
867 | return true; | |
868 | ||
869 | /* Pointers and references are equivalent once we get to GENERIC, | |
870 | so strip conversions that just switch between them. */ | |
871 | else if (POINTER_TYPE_P (inner_type) | |
872 | && POINTER_TYPE_P (outer_type) | |
106f5de5 UW |
873 | && TYPE_REF_CAN_ALIAS_ALL (inner_type) |
874 | == TYPE_REF_CAN_ALIAS_ALL (outer_type) | |
3facc4b6 AP |
875 | && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), |
876 | TREE_TYPE (outer_type))) | |
6de9cd9a DN |
877 | return true; |
878 | ||
879 | /* If both the inner and outer types are integral types, then the | |
880 | conversion is not necessary if they have the same mode and | |
bc15d0ef JM |
881 | signedness and precision, and both or neither are boolean. Some |
882 | code assumes an invariant that boolean types stay boolean and do | |
883 | not become 1-bit bit-field types. Note that types with precision | |
884 | not using all bits of the mode (such as bit-field types in C) | |
885 | mean that testing of precision is necessary. */ | |
6de9cd9a DN |
886 | else if (INTEGRAL_TYPE_P (inner_type) |
887 | && INTEGRAL_TYPE_P (outer_type) | |
6de9cd9a DN |
888 | && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type) |
889 | && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)) | |
bc15d0ef JM |
890 | { |
891 | bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE); | |
892 | bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE); | |
893 | if (first_boolean == second_boolean) | |
894 | return true; | |
895 | } | |
6de9cd9a DN |
896 | |
897 | /* Recurse for complex types. */ | |
898 | else if (TREE_CODE (inner_type) == COMPLEX_TYPE | |
899 | && TREE_CODE (outer_type) == COMPLEX_TYPE | |
900 | && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type), | |
901 | TREE_TYPE (inner_type))) | |
902 | return true; | |
903 | ||
904 | return false; | |
905 | } | |
906 | ||
907 | /* Return true if EXPR is a useless type conversion, otherwise return | |
908 | false. */ | |
909 | ||
910 | bool | |
911 | tree_ssa_useless_type_conversion (tree expr) | |
912 | { | |
913 | /* If we have an assignment that merely uses a NOP_EXPR to change | |
914 | the top of the RHS to the type of the LHS and the type conversion | |
915 | is "safe", then strip away the type conversion so that we can | |
916 | enter LHS = RHS into the const_and_copies table. */ | |
580d124f RK |
917 | if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR |
918 | || TREE_CODE (expr) == VIEW_CONVERT_EXPR | |
919 | || TREE_CODE (expr) == NON_LVALUE_EXPR) | |
6de9cd9a DN |
920 | return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr), |
921 | TREE_TYPE (TREE_OPERAND (expr, | |
922 | 0))); | |
923 | ||
924 | ||
925 | return false; | |
926 | } | |
927 | ||
9beeb4ee ZD |
928 | /* Returns true if statement STMT may read memory. */ |
929 | ||
930 | bool | |
931 | stmt_references_memory_p (tree stmt) | |
932 | { | |
1e6a5d3c | 933 | stmt_ann_t ann = stmt_ann (stmt); |
9beeb4ee ZD |
934 | |
935 | if (ann->has_volatile_ops) | |
936 | return true; | |
937 | ||
938 | return (NUM_VUSES (VUSE_OPS (ann)) > 0 | |
939 | || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0 | |
940 | || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0); | |
941 | } | |
6de9cd9a DN |
942 | |
943 | /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as | |
53b4bf74 DN |
944 | described in walk_use_def_chains. |
945 | ||
d0ce8e4c SB |
946 | VISITED is a pointer set used to mark visited SSA_NAMEs to avoid |
947 | infinite loops. We used to have a bitmap for this to just mark | |
948 | SSA versions we had visited. But non-sparse bitmaps are way too | |
949 | expensive, while sparse bitmaps may cause quadratic behavior. | |
53b4bf74 DN |
950 | |
951 | IS_DFS is true if the caller wants to perform a depth-first search | |
952 | when visiting PHI nodes. A DFS will visit each PHI argument and | |
953 | call FN after each one. Otherwise, all the arguments are | |
954 | visited first and then FN is called with each of the visited | |
955 | arguments in a separate pass. */ | |
6de9cd9a DN |
956 | |
957 | static bool | |
958 | walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, | |
d0ce8e4c | 959 | struct pointer_set_t *visited, bool is_dfs) |
6de9cd9a DN |
960 | { |
961 | tree def_stmt; | |
962 | ||
d0ce8e4c | 963 | if (pointer_set_insert (visited, var)) |
6de9cd9a DN |
964 | return false; |
965 | ||
6de9cd9a DN |
966 | def_stmt = SSA_NAME_DEF_STMT (var); |
967 | ||
968 | if (TREE_CODE (def_stmt) != PHI_NODE) | |
969 | { | |
970 | /* If we reached the end of the use-def chain, call FN. */ | |
53b4bf74 | 971 | return fn (var, def_stmt, data); |
6de9cd9a DN |
972 | } |
973 | else | |
974 | { | |
975 | int i; | |
976 | ||
53b4bf74 DN |
977 | /* When doing a breadth-first search, call FN before following the |
978 | use-def links for each argument. */ | |
979 | if (!is_dfs) | |
980 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) | |
981 | if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) | |
982 | return true; | |
983 | ||
984 | /* Follow use-def links out of each PHI argument. */ | |
6de9cd9a DN |
985 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) |
986 | { | |
987 | tree arg = PHI_ARG_DEF (def_stmt, i); | |
988 | if (TREE_CODE (arg) == SSA_NAME | |
53b4bf74 | 989 | && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) |
6de9cd9a DN |
990 | return true; |
991 | } | |
53b4bf74 DN |
992 | |
993 | /* When doing a depth-first search, call FN after following the | |
994 | use-def links for each argument. */ | |
995 | if (is_dfs) | |
996 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) | |
997 | if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) | |
998 | return true; | |
6de9cd9a | 999 | } |
53b4bf74 | 1000 | |
6de9cd9a DN |
1001 | return false; |
1002 | } | |
1003 | ||
1004 | ||
1005 | ||
53b4bf74 DN |
1006 | /* Walk use-def chains starting at the SSA variable VAR. Call |
1007 | function FN at each reaching definition found. FN takes three | |
1008 | arguments: VAR, its defining statement (DEF_STMT) and a generic | |
1009 | pointer to whatever state information that FN may want to maintain | |
1010 | (DATA). FN is able to stop the walk by returning true, otherwise | |
1011 | in order to continue the walk, FN should return false. | |
6de9cd9a DN |
1012 | |
1013 | Note, that if DEF_STMT is a PHI node, the semantics are slightly | |
53b4bf74 DN |
1014 | different. The first argument to FN is no longer the original |
1015 | variable VAR, but the PHI argument currently being examined. If FN | |
1016 | wants to get at VAR, it should call PHI_RESULT (PHI). | |
1017 | ||
1018 | If IS_DFS is true, this function will: | |
6de9cd9a | 1019 | |
53b4bf74 DN |
1020 | 1- walk the use-def chains for all the PHI arguments, and, |
1021 | 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. | |
1022 | ||
1023 | If IS_DFS is false, the two steps above are done in reverse order | |
1024 | (i.e., a breadth-first search). */ | |
6de9cd9a | 1025 | |
6de9cd9a DN |
1026 | |
1027 | void | |
53b4bf74 DN |
1028 | walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, |
1029 | bool is_dfs) | |
6de9cd9a DN |
1030 | { |
1031 | tree def_stmt; | |
1032 | ||
1e128c5f | 1033 | gcc_assert (TREE_CODE (var) == SSA_NAME); |
6de9cd9a DN |
1034 | |
1035 | def_stmt = SSA_NAME_DEF_STMT (var); | |
1036 | ||
1037 | /* We only need to recurse if the reaching definition comes from a PHI | |
1038 | node. */ | |
1039 | if (TREE_CODE (def_stmt) != PHI_NODE) | |
1040 | (*fn) (var, def_stmt, data); | |
1041 | else | |
1042 | { | |
d0ce8e4c | 1043 | struct pointer_set_t *visited = pointer_set_create (); |
53b4bf74 | 1044 | walk_use_def_chains_1 (var, fn, data, visited, is_dfs); |
d0ce8e4c | 1045 | pointer_set_destroy (visited); |
6de9cd9a DN |
1046 | } |
1047 | } | |
1048 | ||
6de9cd9a DN |
1049 | \f |
1050 | /* Emit warnings for uninitialized variables. This is done in two passes. | |
1051 | ||
1052 | The first pass notices real uses of SSA names with default definitions. | |
1053 | Such uses are unconditionally uninitialized, and we can be certain that | |
1054 | such a use is a mistake. This pass is run before most optimizations, | |
1055 | so that we catch as many as we can. | |
1056 | ||
1057 | The second pass follows PHI nodes to find uses that are potentially | |
1058 | uninitialized. In this case we can't necessarily prove that the use | |
1059 | is really uninitialized. This pass is run after most optimizations, | |
1060 | so that we thread as many jumps and possible, and delete as much dead | |
1061 | code as possible, in order to reduce false positives. We also look | |
1062 | again for plain uninitialized variables, since optimization may have | |
1063 | changed conditionally uninitialized to unconditionally uninitialized. */ | |
1064 | ||
1065 | /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact | |
1066 | warning text is in MSGID and LOCUS may contain a location or be null. */ | |
1067 | ||
1068 | static void | |
bb0a4525 | 1069 | warn_uninit (tree t, const char *msgid, void *data) |
6de9cd9a DN |
1070 | { |
1071 | tree var = SSA_NAME_VAR (t); | |
1072 | tree def = SSA_NAME_DEF_STMT (t); | |
bb0a4525 PB |
1073 | tree context = (tree) data; |
1074 | location_t * locus; | |
6de9cd9a DN |
1075 | |
1076 | /* Default uses (indicated by an empty definition statement), | |
1077 | are uninitialized. */ | |
1078 | if (!IS_EMPTY_STMT (def)) | |
1079 | return; | |
1080 | ||
1081 | /* Except for PARMs of course, which are always initialized. */ | |
1082 | if (TREE_CODE (var) == PARM_DECL) | |
1083 | return; | |
1084 | ||
1085 | /* Hard register variables get their initial value from the ether. */ | |
e670d9e4 | 1086 | if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) |
6de9cd9a DN |
1087 | return; |
1088 | ||
1089 | /* TREE_NO_WARNING either means we already warned, or the front end | |
1090 | wishes to suppress the warning. */ | |
1091 | if (TREE_NO_WARNING (var)) | |
1092 | return; | |
1093 | ||
bb0a4525 PB |
1094 | locus = (context != NULL && EXPR_HAS_LOCATION (context) |
1095 | ? EXPR_LOCUS (context) | |
1096 | : &DECL_SOURCE_LOCATION (var)); | |
6de9cd9a DN |
1097 | warning (msgid, locus, var); |
1098 | TREE_NO_WARNING (var) = 1; | |
1099 | } | |
1100 | ||
1101 | /* Called via walk_tree, look for SSA_NAMEs that have empty definitions | |
1102 | and warn about them. */ | |
1103 | ||
1104 | static tree | |
1105 | warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) | |
1106 | { | |
6de9cd9a DN |
1107 | tree t = *tp; |
1108 | ||
1109 | /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */ | |
1110 | if (TREE_CODE (t) == SSA_NAME) | |
1111 | { | |
bb0a4525 | 1112 | warn_uninit (t, "%H%qD is used uninitialized in this function", data); |
6de9cd9a DN |
1113 | *walk_subtrees = 0; |
1114 | } | |
6615c446 | 1115 | else if (IS_TYPE_OR_DECL_P (t)) |
6de9cd9a DN |
1116 | *walk_subtrees = 0; |
1117 | ||
1118 | return NULL_TREE; | |
1119 | } | |
1120 | ||
1121 | /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions | |
1122 | and warn about them. */ | |
1123 | ||
1124 | static void | |
1125 | warn_uninitialized_phi (tree phi) | |
1126 | { | |
1127 | int i, n = PHI_NUM_ARGS (phi); | |
1128 | ||
1129 | /* Don't look at memory tags. */ | |
1130 | if (!is_gimple_reg (PHI_RESULT (phi))) | |
1131 | return; | |
1132 | ||
1133 | for (i = 0; i < n; ++i) | |
1134 | { | |
1135 | tree op = PHI_ARG_DEF (phi, i); | |
1136 | if (TREE_CODE (op) == SSA_NAME) | |
7a6336aa | 1137 | warn_uninit (op, "%H%qD may be used uninitialized in this function", |
6de9cd9a DN |
1138 | NULL); |
1139 | } | |
1140 | } | |
1141 | ||
1142 | static void | |
1143 | execute_early_warn_uninitialized (void) | |
1144 | { | |
1145 | block_stmt_iterator bsi; | |
1146 | basic_block bb; | |
1147 | ||
1148 | FOR_EACH_BB (bb) | |
1149 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
bb0a4525 PB |
1150 | { |
1151 | tree context = bsi_stmt (bsi); | |
1152 | walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var, | |
1153 | context, NULL); | |
1154 | } | |
6de9cd9a DN |
1155 | } |
1156 | ||
1157 | static void | |
1158 | execute_late_warn_uninitialized (void) | |
1159 | { | |
1160 | basic_block bb; | |
1161 | tree phi; | |
1162 | ||
1163 | /* Re-do the plain uninitialized variable check, as optimization may have | |
1164 | straightened control flow. Do this first so that we don't accidentally | |
1165 | get a "may be" warning when we'd have seen an "is" warning later. */ | |
1166 | execute_early_warn_uninitialized (); | |
1167 | ||
1168 | FOR_EACH_BB (bb) | |
17192884 | 1169 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
1170 | warn_uninitialized_phi (phi); |
1171 | } | |
1172 | ||
1173 | static bool | |
1174 | gate_warn_uninitialized (void) | |
1175 | { | |
1176 | return warn_uninitialized != 0; | |
1177 | } | |
1178 | ||
1179 | struct tree_opt_pass pass_early_warn_uninitialized = | |
1180 | { | |
1181 | NULL, /* name */ | |
1182 | gate_warn_uninitialized, /* gate */ | |
1183 | execute_early_warn_uninitialized, /* execute */ | |
1184 | NULL, /* sub */ | |
1185 | NULL, /* next */ | |
1186 | 0, /* static_pass_number */ | |
1187 | 0, /* tv_id */ | |
1188 | PROP_ssa, /* properties_required */ | |
1189 | 0, /* properties_provided */ | |
1190 | 0, /* properties_destroyed */ | |
1191 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1192 | 0, /* todo_flags_finish */ |
1193 | 0 /* letter */ | |
6de9cd9a DN |
1194 | }; |
1195 | ||
1196 | struct tree_opt_pass pass_late_warn_uninitialized = | |
1197 | { | |
1198 | NULL, /* name */ | |
1199 | gate_warn_uninitialized, /* gate */ | |
1200 | execute_late_warn_uninitialized, /* execute */ | |
1201 | NULL, /* sub */ | |
1202 | NULL, /* next */ | |
1203 | 0, /* static_pass_number */ | |
1204 | 0, /* tv_id */ | |
1205 | PROP_ssa, /* properties_required */ | |
1206 | 0, /* properties_provided */ | |
1207 | 0, /* properties_destroyed */ | |
1208 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1209 | 0, /* todo_flags_finish */ |
1210 | 0 /* letter */ | |
6de9cd9a | 1211 | }; |
52328bf6 | 1212 |