]>
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 | |
366ccddb KC |
18 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
19 | Boston, MA 02110-1301, USA. */ | |
6de9cd9a DN |
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" | |
6de9cd9a DN |
34 | #include "expr.h" |
35 | #include "function.h" | |
36 | #include "diagnostic.h" | |
37 | #include "bitmap.h" | |
d0ce8e4c | 38 | #include "pointer-set.h" |
6de9cd9a | 39 | #include "tree-flow.h" |
eadf906f | 40 | #include "tree-gimple.h" |
6de9cd9a DN |
41 | #include "tree-inline.h" |
42 | #include "varray.h" | |
43 | #include "timevar.h" | |
6de9cd9a DN |
44 | #include "hashtab.h" |
45 | #include "tree-dump.h" | |
46 | #include "tree-pass.h" | |
4c714dd4 | 47 | #include "toplev.h" |
6de9cd9a | 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 | { | |
ab532386 | 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 | { | |
ab532386 | 117 | error ("type mismatch between an SSA_NAME and its symbol"); |
bbc630f5 DN |
118 | return true; |
119 | } | |
120 | ||
53b4bf74 DN |
121 | if (SSA_NAME_IN_FREE_LIST (ssa_name)) |
122 | { | |
ab532386 | 123 | error ("found an SSA_NAME that had been released into the free pool"); |
53b4bf74 DN |
124 | return true; |
125 | } | |
126 | ||
127 | if (is_virtual && is_gimple_reg (ssa_name)) | |
128 | { | |
ab532386 | 129 | error ("found a virtual definition for a GIMPLE register"); |
53b4bf74 DN |
130 | return true; |
131 | } | |
132 | ||
133 | if (!is_virtual && !is_gimple_reg (ssa_name)) | |
134 | { | |
ab532386 | 135 | error ("found a real definition for a non-register"); |
53b4bf74 DN |
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 | { | |
ab532386 | 142 | error ("found real variable when subvariables should have appeared"); |
d19e9499 DB |
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)) | |
df1f6f31 | 234 | && default_def (SSA_NAME_VAR (ssa_name)) == ssa_name) |
53b4bf74 | 235 | ; /* Default definitions have empty statements. Nothing to do. */ |
6de9cd9a DN |
236 | else if (!def_bb) |
237 | { | |
ab532386 | 238 | error ("missing definition"); |
6de9cd9a DN |
239 | err = true; |
240 | } | |
241 | else if (bb != def_bb | |
242 | && !dominated_by_p (CDI_DOMINATORS, bb, def_bb)) | |
243 | { | |
ab532386 | 244 | error ("definition in block %i does not dominate use in block %i", |
6de9cd9a DN |
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 | { | |
ab532386 | 252 | error ("definition in block %i follows the use", def_bb->index); |
b1d16eff ZD |
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 | { | |
ab532386 | 267 | error ("no immediate_use list"); |
f430bae8 AM |
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 | { | |
ab532386 | 279 | error ("wrong immediate use list"); |
f430bae8 AM |
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 | { | |
ab532386 | 312 | error ("incoming edge count does not match number of PHI arguments"); |
609d9bed JL |
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 | { | |
ab532386 | 327 | error ("PHI argument is missing for edge %d->%d", |
6b66c718 KH |
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 | { | |
ab532386 | 348 | error ("wrong edge %d->%d for PHI argument", |
ea40ba9c | 349 | e->src->index, e->dest->index); |
6de9cd9a DN |
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 | { | |
53b4bf74 | 376 | tree var; |
8bdbfff5 | 377 | bitmap visited = BITMAP_ALLOC (NULL); |
a3648cfc | 378 | referenced_var_iterator rvi; |
53b4bf74 | 379 | |
a3648cfc | 380 | FOR_EACH_REFERENCED_VAR (var, rvi) |
53b4bf74 | 381 | { |
852c7b12 | 382 | size_t j; |
53b4bf74 | 383 | var_ann_t ann; |
780e37d3 ZD |
384 | VEC(tree,gc) *may_aliases; |
385 | tree alias; | |
53b4bf74 | 386 | |
53b4bf74 | 387 | ann = var_ann (var); |
852c7b12 | 388 | may_aliases = ann->may_aliases; |
53b4bf74 | 389 | |
780e37d3 | 390 | for (j = 0; VEC_iterate (tree, may_aliases, j, alias); j++) |
53b4bf74 | 391 | { |
a3648cfc | 392 | bitmap_set_bit (visited, DECL_UID (alias)); |
53b4bf74 | 393 | |
852c7b12 DN |
394 | if (!may_be_aliased (alias)) |
395 | { | |
ab532386 | 396 | error ("non-addressable variable inside an alias set"); |
852c7b12 DN |
397 | debug_variable (alias); |
398 | goto err; | |
53b4bf74 DN |
399 | } |
400 | } | |
401 | } | |
402 | ||
a3648cfc | 403 | FOR_EACH_REFERENCED_VAR (var, rvi) |
53b4bf74 DN |
404 | { |
405 | var_ann_t ann; | |
53b4bf74 DN |
406 | ann = var_ann (var); |
407 | ||
326eda4b | 408 | if (!MTAG_P (var) |
faf7c678 | 409 | && ann->is_aliased |
a3648cfc | 410 | && !bitmap_bit_p (visited, DECL_UID (var))) |
53b4bf74 | 411 | { |
faf7c678 | 412 | error ("addressable variable that is aliased but is not in any alias set"); |
53b4bf74 DN |
413 | goto err; |
414 | } | |
415 | } | |
416 | ||
8bdbfff5 | 417 | BITMAP_FREE (visited); |
53b4bf74 DN |
418 | return; |
419 | ||
420 | err: | |
421 | debug_variable (var); | |
ab532386 | 422 | internal_error ("verify_flow_insensitive_alias_info failed"); |
53b4bf74 DN |
423 | } |
424 | ||
425 | ||
426 | static void | |
427 | verify_flow_sensitive_alias_info (void) | |
428 | { | |
429 | size_t i; | |
430 | tree ptr; | |
431 | ||
432 | for (i = 1; i < num_ssa_names; i++) | |
433 | { | |
b5c3569b | 434 | tree var; |
53b4bf74 DN |
435 | var_ann_t ann; |
436 | struct ptr_info_def *pi; | |
b5c3569b | 437 | |
53b4bf74 DN |
438 | |
439 | ptr = ssa_name (i); | |
8b547e44 JH |
440 | if (!ptr) |
441 | continue; | |
53b4bf74 DN |
442 | |
443 | /* We only care for pointers that are actually referenced in the | |
444 | program. */ | |
b5c3569b | 445 | if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) |
53b4bf74 DN |
446 | continue; |
447 | ||
448 | /* RESULT_DECL is special. If it's a GIMPLE register, then it | |
449 | is only written-to only once in the return statement. | |
450 | Otherwise, aggregate RESULT_DECLs may be written-to more than | |
451 | once in virtual operands. */ | |
b5c3569b JL |
452 | var = SSA_NAME_VAR (ptr); |
453 | if (TREE_CODE (var) == RESULT_DECL | |
53b4bf74 DN |
454 | && is_gimple_reg (ptr)) |
455 | continue; | |
456 | ||
b5c3569b | 457 | pi = SSA_NAME_PTR_INFO (ptr); |
53b4bf74 DN |
458 | if (pi == NULL) |
459 | continue; | |
460 | ||
b5c3569b | 461 | ann = var_ann (var); |
18cd8a03 | 462 | if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag) |
53b4bf74 | 463 | { |
18cd8a03 | 464 | error ("dereferenced pointers should have a name or a symbol tag"); |
53b4bf74 DN |
465 | goto err; |
466 | } | |
467 | ||
53b4bf74 | 468 | if (pi->name_mem_tag |
eb59b8de | 469 | && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) |
53b4bf74 | 470 | { |
e8ca4159 | 471 | error ("pointers with a memory tag, should have points-to sets"); |
53b4bf74 DN |
472 | goto err; |
473 | } | |
474 | ||
475 | if (pi->value_escapes_p | |
476 | && pi->name_mem_tag | |
477 | && !is_call_clobbered (pi->name_mem_tag)) | |
478 | { | |
ab532386 | 479 | error ("pointer escapes but its name tag is not call-clobbered"); |
53b4bf74 DN |
480 | goto err; |
481 | } | |
53b4bf74 DN |
482 | } |
483 | ||
484 | return; | |
485 | ||
486 | err: | |
487 | debug_variable (ptr); | |
ab532386 | 488 | internal_error ("verify_flow_sensitive_alias_info failed"); |
53b4bf74 DN |
489 | } |
490 | ||
d4e6fecb NS |
491 | DEF_VEC_P (bitmap); |
492 | DEF_VEC_ALLOC_P (bitmap,heap); | |
7dcdacad DB |
493 | |
494 | /* Verify that all name tags have different points to sets. | |
495 | This algorithm takes advantage of the fact that every variable with the | |
496 | same name tag must have the same points-to set. | |
3d4818fd | 497 | So we check a single variable for each name tag, and verify that its |
7dcdacad | 498 | points-to set is different from every other points-to set for other name |
e03a46f5 DN |
499 | tags. |
500 | ||
18cd8a03 DN |
501 | Additionally, given a pointer P_i with name tag NMT and symbol tag |
502 | SMT, this function verified the alias set of SMT is a superset of | |
e03a46f5 | 503 | the alias set of NMT. */ |
7dcdacad DB |
504 | |
505 | static void | |
506 | verify_name_tags (void) | |
507 | { | |
508 | size_t i; | |
509 | size_t j; | |
510 | bitmap first, second; | |
d4e6fecb NS |
511 | VEC(tree,heap) *name_tag_reps = NULL; |
512 | VEC(bitmap,heap) *pt_vars_for_reps = NULL; | |
8bdbfff5 | 513 | bitmap type_aliases = BITMAP_ALLOC (NULL); |
7dcdacad DB |
514 | |
515 | /* First we compute the name tag representatives and their points-to sets. */ | |
516 | for (i = 0; i < num_ssa_names; i++) | |
517 | { | |
e03a46f5 | 518 | struct ptr_info_def *pi; |
18cd8a03 | 519 | tree smt, ptr = ssa_name (i); |
e03a46f5 DN |
520 | |
521 | if (ptr == NULL_TREE) | |
522 | continue; | |
523 | ||
524 | pi = SSA_NAME_PTR_INFO (ptr); | |
525 | ||
526 | if (!TREE_VISITED (ptr) | |
527 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
528 | || !pi | |
529 | || !pi->name_mem_tag | |
530 | || TREE_VISITED (pi->name_mem_tag)) | |
531 | continue; | |
532 | ||
533 | TREE_VISITED (pi->name_mem_tag) = 1; | |
534 | ||
535 | if (pi->pt_vars == NULL) | |
536 | continue; | |
537 | ||
d4e6fecb NS |
538 | VEC_safe_push (tree, heap, name_tag_reps, ptr); |
539 | VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars); | |
e03a46f5 | 540 | |
18cd8a03 | 541 | /* Verify that alias set of PTR's symbol tag is a superset of the |
e03a46f5 | 542 | alias set of PTR's name tag. */ |
18cd8a03 DN |
543 | smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; |
544 | if (smt) | |
7dcdacad | 545 | { |
e03a46f5 | 546 | size_t i; |
18cd8a03 | 547 | VEC(tree,gc) *aliases = var_ann (smt)->may_aliases; |
780e37d3 ZD |
548 | tree alias; |
549 | ||
e03a46f5 | 550 | bitmap_clear (type_aliases); |
780e37d3 ZD |
551 | for (i = 0; VEC_iterate (tree, aliases, i, alias); i++) |
552 | bitmap_set_bit (type_aliases, DECL_UID (alias)); | |
e03a46f5 | 553 | |
18cd8a03 | 554 | /* When grouping, we may have added PTR's symbol tag into the |
e03a46f5 | 555 | alias set of PTR's name tag. To prevent a false |
18cd8a03 DN |
556 | positive, pretend that SMT is in its own alias set. */ |
557 | bitmap_set_bit (type_aliases, DECL_UID (smt)); | |
e03a46f5 DN |
558 | |
559 | if (bitmap_equal_p (type_aliases, pi->pt_vars)) | |
7dcdacad | 560 | continue; |
e03a46f5 DN |
561 | |
562 | if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) | |
563 | { | |
18cd8a03 DN |
564 | error ("alias set of a pointer's symbol tag should be a superset of the corresponding name tag"); |
565 | debug_variable (smt); | |
e03a46f5 DN |
566 | debug_variable (pi->name_mem_tag); |
567 | goto err; | |
7dcdacad DB |
568 | } |
569 | } | |
570 | } | |
571 | ||
572 | /* Now compare all the representative bitmaps with all other representative | |
573 | bitmaps, to verify that they are all different. */ | |
574 | for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) | |
575 | { | |
576 | for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) | |
577 | { | |
578 | if (bitmap_equal_p (first, second)) | |
579 | { | |
ab532386 | 580 | error ("two different pointers with identical points-to sets but different name tags"); |
7dcdacad DB |
581 | debug_variable (VEC_index (tree, name_tag_reps, j)); |
582 | goto err; | |
583 | } | |
584 | } | |
585 | } | |
53b4bf74 | 586 | |
7dcdacad DB |
587 | /* Lastly, clear out the visited flags. */ |
588 | for (i = 0; i < num_ssa_names; i++) | |
589 | { | |
590 | if (ssa_name (i)) | |
591 | { | |
592 | tree ptr = ssa_name (i); | |
593 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
594 | if (!TREE_VISITED (ptr) | |
595 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
596 | || !pi | |
597 | || !pi->name_mem_tag) | |
598 | continue; | |
599 | TREE_VISITED (pi->name_mem_tag) = 0; | |
600 | } | |
601 | } | |
e03a46f5 | 602 | |
d4e6fecb NS |
603 | /* We do not have to free the bitmaps or trees in the vectors, as |
604 | they are not owned by us. */ | |
605 | VEC_free (bitmap, heap, pt_vars_for_reps); | |
606 | VEC_free (tree, heap, name_tag_reps); | |
e03a46f5 | 607 | BITMAP_FREE (type_aliases); |
7dcdacad DB |
608 | return; |
609 | ||
610 | err: | |
611 | debug_variable (VEC_index (tree, name_tag_reps, i)); | |
612 | internal_error ("verify_name_tags failed"); | |
613 | } | |
e03a46f5 DN |
614 | |
615 | ||
fe1f8f44 DB |
616 | /* Verify the consistency of call clobbering information. */ |
617 | static void | |
618 | verify_call_clobbering (void) | |
619 | { | |
620 | unsigned int i; | |
621 | bitmap_iterator bi; | |
622 | tree var; | |
623 | referenced_var_iterator rvi; | |
624 | ||
625 | /* At all times, the result of the DECL_CALL_CLOBBERED flag should | |
626 | match the result of the call_clobbered_vars bitmap. Verify both | |
627 | that everything in call_clobbered_vars is marked | |
628 | DECL_CALL_CLOBBERED, and that everything marked | |
629 | DECL_CALL_CLOBBERED is in call_clobbered_vars. */ | |
630 | EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) | |
631 | { | |
632 | var = referenced_var (i); | |
633 | if (!MTAG_P (var) && !DECL_CALL_CLOBBERED (var)) | |
634 | { | |
635 | error ("variable in call_clobbered_vars but not marked DECL_CALL_CLOBBERED"); | |
636 | debug_variable (var); | |
637 | goto err; | |
638 | } | |
639 | } | |
640 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
641 | { | |
642 | if (!MTAG_P (var) && DECL_CALL_CLOBBERED (var) | |
643 | && !bitmap_bit_p (call_clobbered_vars, DECL_UID (var))) | |
644 | { | |
645 | error ("variable marked DECL_CALL_CLOBBERED but not in call_clobbered_vars bitmap."); | |
646 | debug_variable (var); | |
647 | goto err; | |
648 | } | |
649 | } | |
650 | return; | |
651 | ||
652 | err: | |
653 | internal_error ("verify_call_clobbering failed"); | |
654 | } | |
655 | ||
53b4bf74 DN |
656 | /* Verify the consistency of aliasing information. */ |
657 | ||
658 | static void | |
659 | verify_alias_info (void) | |
660 | { | |
c1b763fa | 661 | verify_flow_sensitive_alias_info (); |
7dcdacad | 662 | verify_name_tags (); |
fe1f8f44 | 663 | verify_call_clobbering (); |
c1b763fa | 664 | verify_flow_insensitive_alias_info (); |
53b4bf74 DN |
665 | } |
666 | ||
667 | ||
6de9cd9a DN |
668 | /* Verify common invariants in the SSA web. |
669 | TODO: verify the variable annotations. */ | |
670 | ||
671 | void | |
f430bae8 | 672 | verify_ssa (bool check_modified_stmt) |
6de9cd9a | 673 | { |
53b4bf74 | 674 | size_t i; |
6de9cd9a | 675 | basic_block bb; |
858904db | 676 | basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names); |
4c124b4c AM |
677 | ssa_op_iter iter; |
678 | tree op; | |
03261822 | 679 | enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; |
8bdbfff5 | 680 | bitmap names_defined_in_bb = BITMAP_ALLOC (NULL); |
6de9cd9a | 681 | |
84d65814 DN |
682 | gcc_assert (!need_ssa_update_p ()); |
683 | ||
684 | verify_stmts (); | |
685 | ||
6de9cd9a DN |
686 | timevar_push (TV_TREE_SSA_VERIFY); |
687 | ||
53b4bf74 DN |
688 | /* Keep track of SSA names present in the IL. */ |
689 | for (i = 1; i < num_ssa_names; i++) | |
6de9cd9a | 690 | { |
609d9bed JL |
691 | tree name = ssa_name (i); |
692 | if (name) | |
6de9cd9a DN |
693 | { |
694 | tree stmt; | |
609d9bed | 695 | TREE_VISITED (name) = 0; |
6de9cd9a | 696 | |
609d9bed JL |
697 | stmt = SSA_NAME_DEF_STMT (name); |
698 | if (!IS_EMPTY_STMT (stmt)) | |
53b4bf74 | 699 | { |
609d9bed JL |
700 | basic_block bb = bb_for_stmt (stmt); |
701 | verify_def (bb, definition_block, | |
702 | name, stmt, !is_gimple_reg (name)); | |
703 | ||
6de9cd9a DN |
704 | } |
705 | } | |
706 | } | |
707 | ||
609d9bed | 708 | calculate_dominance_info (CDI_DOMINATORS); |
6de9cd9a DN |
709 | |
710 | /* Now verify all the uses and make sure they agree with the definitions | |
711 | found in the previous pass. */ | |
712 | FOR_EACH_BB (bb) | |
713 | { | |
714 | edge e; | |
715 | tree phi; | |
628f6a4e | 716 | edge_iterator ei; |
6de9cd9a DN |
717 | block_stmt_iterator bsi; |
718 | ||
719 | /* Make sure that all edges have a clear 'aux' field. */ | |
628f6a4e | 720 | FOR_EACH_EDGE (e, ei, bb->preds) |
6de9cd9a DN |
721 | { |
722 | if (e->aux) | |
723 | { | |
ab532386 | 724 | error ("AUX pointer initialized for edge %d->%d", e->src->index, |
6de9cd9a | 725 | e->dest->index); |
53b4bf74 | 726 | goto err; |
6de9cd9a DN |
727 | } |
728 | } | |
729 | ||
730 | /* Verify the arguments for every PHI node in the block. */ | |
17192884 | 731 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
b1d16eff ZD |
732 | { |
733 | if (verify_phi_args (phi, bb, definition_block)) | |
734 | goto err; | |
735 | bitmap_set_bit (names_defined_in_bb, | |
736 | SSA_NAME_VERSION (PHI_RESULT (phi))); | |
737 | } | |
6de9cd9a | 738 | |
53b4bf74 | 739 | /* Now verify all the uses and vuses in every statement of the block. */ |
6de9cd9a DN |
740 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
741 | { | |
742 | tree stmt = bsi_stmt (bsi); | |
f430bae8 AM |
743 | use_operand_p use_p; |
744 | ||
745 | if (check_modified_stmt && stmt_modified_p (stmt)) | |
746 | { | |
ab532386 | 747 | error ("stmt (%p) marked modified after optimization pass : ", |
f47c96aa | 748 | (void *)stmt); |
f430bae8 AM |
749 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
750 | goto err; | |
751 | } | |
6de9cd9a | 752 | |
f8d66d34 DN |
753 | if (TREE_CODE (stmt) == MODIFY_EXPR |
754 | && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) | |
755 | { | |
756 | tree lhs, base_address; | |
757 | ||
758 | lhs = TREE_OPERAND (stmt, 0); | |
759 | base_address = get_base_address (lhs); | |
609d9bed | 760 | |
f8d66d34 DN |
761 | if (base_address |
762 | && SSA_VAR_P (base_address) | |
f47c96aa | 763 | && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) |
609d9bed | 764 | { |
ab532386 | 765 | error ("statement makes a memory store, but has no " |
f8d66d34 | 766 | "V_MAY_DEFS nor V_MUST_DEFS"); |
609d9bed JL |
767 | print_generic_stmt (stderr, stmt, TDF_VOPS); |
768 | goto err; | |
769 | } | |
f8d66d34 DN |
770 | } |
771 | ||
f8d66d34 DN |
772 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, |
773 | SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) | |
6de9cd9a | 774 | { |
f430bae8 | 775 | op = USE_FROM_PTR (use_p); |
53b4bf74 | 776 | if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], |
f430bae8 | 777 | use_p, stmt, false, !is_gimple_reg (op), |
b1d16eff ZD |
778 | names_defined_in_bb)) |
779 | goto err; | |
780 | } | |
781 | ||
782 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) | |
84d65814 | 783 | bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); |
b1d16eff ZD |
784 | } |
785 | ||
b1d16eff | 786 | bitmap_clear (names_defined_in_bb); |
6de9cd9a DN |
787 | } |
788 | ||
53b4bf74 DN |
789 | /* Finally, verify alias information. */ |
790 | verify_alias_info (); | |
6de9cd9a | 791 | |
53b4bf74 | 792 | free (definition_block); |
84d65814 | 793 | |
b01d837f KH |
794 | /* Restore the dominance information to its prior known state, so |
795 | that we do not perturb the compiler's subsequent behavior. */ | |
03261822 NS |
796 | if (orig_dom_state == DOM_NONE) |
797 | free_dominance_info (CDI_DOMINATORS); | |
798 | else | |
799 | dom_computed[CDI_DOMINATORS] = orig_dom_state; | |
800 | ||
8bdbfff5 | 801 | BITMAP_FREE (names_defined_in_bb); |
6de9cd9a | 802 | timevar_pop (TV_TREE_SSA_VERIFY); |
53b4bf74 | 803 | return; |
6de9cd9a | 804 | |
53b4bf74 | 805 | err: |
ab532386 | 806 | internal_error ("verify_ssa failed"); |
6de9cd9a DN |
807 | } |
808 | ||
a3648cfc DB |
809 | /* Return true if the uid in both int tree maps are equal. */ |
810 | ||
811 | int | |
812 | int_tree_map_eq (const void *va, const void *vb) | |
813 | { | |
858904db GDR |
814 | const struct int_tree_map *a = (const struct int_tree_map *) va; |
815 | const struct int_tree_map *b = (const struct int_tree_map *) vb; | |
a3648cfc DB |
816 | return (a->uid == b->uid); |
817 | } | |
818 | ||
819 | /* Hash a UID in a int_tree_map. */ | |
820 | ||
821 | unsigned int | |
822 | int_tree_map_hash (const void *item) | |
823 | { | |
824 | return ((const struct int_tree_map *)item)->uid; | |
825 | } | |
826 | ||
6de9cd9a | 827 | |
6de9cd9a DN |
828 | /* Initialize global DFA and SSA structures. */ |
829 | ||
830 | void | |
831 | init_tree_ssa (void) | |
832 | { | |
a3648cfc DB |
833 | referenced_vars = htab_create_ggc (20, int_tree_map_hash, |
834 | int_tree_map_eq, NULL); | |
86051306 | 835 | default_defs = htab_create_ggc (20, int_tree_map_hash, int_tree_map_eq, NULL); |
8bdbfff5 NS |
836 | call_clobbered_vars = BITMAP_ALLOC (NULL); |
837 | addressable_vars = BITMAP_ALLOC (NULL); | |
c900f6aa | 838 | init_alias_heapvars (); |
6de9cd9a DN |
839 | init_ssanames (); |
840 | init_phinodes (); | |
841 | global_var = NULL_TREE; | |
90c1d75a | 842 | aliases_computed_p = false; |
6de9cd9a DN |
843 | } |
844 | ||
845 | ||
846 | /* Deallocate memory associated with SSA data structures for FNDECL. */ | |
847 | ||
848 | void | |
849 | delete_tree_ssa (void) | |
850 | { | |
851 | size_t i; | |
852 | basic_block bb; | |
853 | block_stmt_iterator bsi; | |
a3648cfc DB |
854 | referenced_var_iterator rvi; |
855 | tree var; | |
6de9cd9a | 856 | |
f47c96aa AM |
857 | /* Release any ssa_names still in use. */ |
858 | for (i = 0; i < num_ssa_names; i++) | |
859 | { | |
860 | tree var = ssa_name (i); | |
861 | if (var && TREE_CODE (var) == SSA_NAME) | |
862 | { | |
863 | SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var)); | |
864 | SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var)); | |
865 | } | |
866 | release_ssa_name (var); | |
867 | } | |
868 | ||
6de9cd9a DN |
869 | /* Remove annotations from every tree in the function. */ |
870 | FOR_EACH_BB (bb) | |
6844185d JH |
871 | { |
872 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
873 | { | |
874 | tree stmt = bsi_stmt (bsi); | |
875 | stmt_ann_t ann = get_stmt_ann (stmt); | |
876 | ||
877 | free_ssa_operands (&ann->operands); | |
878 | ann->addresses_taken = 0; | |
879 | mark_stmt_modified (stmt); | |
880 | } | |
881 | set_phi_nodes (bb, NULL); | |
882 | } | |
6de9cd9a DN |
883 | |
884 | /* Remove annotations from every referenced variable. */ | |
a3648cfc | 885 | FOR_EACH_REFERENCED_VAR (var, rvi) |
6de9cd9a | 886 | { |
2d4d14ac KH |
887 | ggc_free (var->common.ann); |
888 | var->common.ann = NULL; | |
6de9cd9a | 889 | } |
a3648cfc DB |
890 | htab_delete (referenced_vars); |
891 | referenced_vars = NULL; | |
6de9cd9a DN |
892 | |
893 | fini_ssanames (); | |
894 | fini_phinodes (); | |
6de9cd9a DN |
895 | |
896 | global_var = NULL_TREE; | |
86051306 JH |
897 | |
898 | htab_delete (default_defs); | |
8bdbfff5 | 899 | BITMAP_FREE (call_clobbered_vars); |
6de9cd9a | 900 | call_clobbered_vars = NULL; |
8bdbfff5 | 901 | BITMAP_FREE (addressable_vars); |
a6d02559 | 902 | addressable_vars = NULL; |
7ded35b4 | 903 | modified_noreturn_calls = NULL; |
90c1d75a | 904 | aliases_computed_p = false; |
c900f6aa | 905 | delete_alias_heapvars (); |
84d65814 | 906 | gcc_assert (!need_ssa_update_p ()); |
6de9cd9a DN |
907 | } |
908 | ||
909 | ||
e0004427 RG |
910 | /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a |
911 | useless type conversion, otherwise return false. */ | |
6de9cd9a DN |
912 | |
913 | bool | |
914 | tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) | |
915 | { | |
4f380bf8 RS |
916 | if (inner_type == outer_type) |
917 | return true; | |
918 | ||
919 | /* Changes in machine mode are never useless conversions. */ | |
920 | if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type)) | |
921 | return false; | |
922 | ||
6de9cd9a DN |
923 | /* If the inner and outer types are effectively the same, then |
924 | strip the type conversion and enter the equivalence into | |
925 | the table. */ | |
4f380bf8 | 926 | if (lang_hooks.types_compatible_p (inner_type, outer_type)) |
6de9cd9a DN |
927 | return true; |
928 | ||
929 | /* If both types are pointers and the outer type is a (void *), then | |
930 | the conversion is not necessary. The opposite is not true since | |
931 | that conversion would result in a loss of information if the | |
932 | equivalence was used. Consider an indirect function call where | |
933 | we need to know the exact type of the function to correctly | |
934 | implement the ABI. */ | |
935 | else if (POINTER_TYPE_P (inner_type) | |
936 | && POINTER_TYPE_P (outer_type) | |
106f5de5 UW |
937 | && TYPE_REF_CAN_ALIAS_ALL (inner_type) |
938 | == TYPE_REF_CAN_ALIAS_ALL (outer_type) | |
6de9cd9a DN |
939 | && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) |
940 | return true; | |
941 | ||
af62f6f9 RH |
942 | /* Don't lose casts between pointers to volatile and non-volatile |
943 | qualified types. Doing so would result in changing the semantics | |
944 | of later accesses. */ | |
945 | else if (POINTER_TYPE_P (inner_type) | |
946 | && POINTER_TYPE_P (outer_type) | |
947 | && TYPE_VOLATILE (TREE_TYPE (outer_type)) | |
948 | != TYPE_VOLATILE (TREE_TYPE (inner_type))) | |
949 | return false; | |
950 | ||
e0004427 RG |
951 | /* Pointers/references are equivalent if their pointed to types |
952 | are effectively the same. This allows to strip conversions between | |
953 | pointer types with different type qualifiers. */ | |
6de9cd9a DN |
954 | else if (POINTER_TYPE_P (inner_type) |
955 | && POINTER_TYPE_P (outer_type) | |
106f5de5 UW |
956 | && TYPE_REF_CAN_ALIAS_ALL (inner_type) |
957 | == TYPE_REF_CAN_ALIAS_ALL (outer_type) | |
3facc4b6 AP |
958 | && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), |
959 | TREE_TYPE (outer_type))) | |
6de9cd9a DN |
960 | return true; |
961 | ||
962 | /* If both the inner and outer types are integral types, then the | |
963 | conversion is not necessary if they have the same mode and | |
bc15d0ef JM |
964 | signedness and precision, and both or neither are boolean. Some |
965 | code assumes an invariant that boolean types stay boolean and do | |
966 | not become 1-bit bit-field types. Note that types with precision | |
967 | not using all bits of the mode (such as bit-field types in C) | |
968 | mean that testing of precision is necessary. */ | |
6de9cd9a DN |
969 | else if (INTEGRAL_TYPE_P (inner_type) |
970 | && INTEGRAL_TYPE_P (outer_type) | |
6de9cd9a | 971 | && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type) |
2decfada AP |
972 | && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type) |
973 | && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type)) | |
974 | && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type))) | |
bc15d0ef JM |
975 | { |
976 | bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE); | |
977 | bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE); | |
978 | if (first_boolean == second_boolean) | |
979 | return true; | |
980 | } | |
6de9cd9a DN |
981 | |
982 | /* Recurse for complex types. */ | |
983 | else if (TREE_CODE (inner_type) == COMPLEX_TYPE | |
984 | && TREE_CODE (outer_type) == COMPLEX_TYPE | |
985 | && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type), | |
986 | TREE_TYPE (inner_type))) | |
987 | return true; | |
988 | ||
989 | return false; | |
990 | } | |
991 | ||
992 | /* Return true if EXPR is a useless type conversion, otherwise return | |
993 | false. */ | |
994 | ||
995 | bool | |
996 | tree_ssa_useless_type_conversion (tree expr) | |
997 | { | |
998 | /* If we have an assignment that merely uses a NOP_EXPR to change | |
999 | the top of the RHS to the type of the LHS and the type conversion | |
1000 | is "safe", then strip away the type conversion so that we can | |
1001 | enter LHS = RHS into the const_and_copies table. */ | |
580d124f RK |
1002 | if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR |
1003 | || TREE_CODE (expr) == VIEW_CONVERT_EXPR | |
1004 | || TREE_CODE (expr) == NON_LVALUE_EXPR) | |
6de9cd9a DN |
1005 | return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr), |
1006 | TREE_TYPE (TREE_OPERAND (expr, | |
1007 | 0))); | |
1008 | ||
1009 | ||
1010 | return false; | |
1011 | } | |
1012 | ||
9beeb4ee ZD |
1013 | /* Returns true if statement STMT may read memory. */ |
1014 | ||
1015 | bool | |
1016 | stmt_references_memory_p (tree stmt) | |
1017 | { | |
1e6a5d3c | 1018 | stmt_ann_t ann = stmt_ann (stmt); |
9beeb4ee ZD |
1019 | |
1020 | if (ann->has_volatile_ops) | |
1021 | return true; | |
1022 | ||
f47c96aa | 1023 | return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)); |
9beeb4ee | 1024 | } |
6de9cd9a DN |
1025 | |
1026 | /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as | |
53b4bf74 DN |
1027 | described in walk_use_def_chains. |
1028 | ||
d0ce8e4c SB |
1029 | VISITED is a pointer set used to mark visited SSA_NAMEs to avoid |
1030 | infinite loops. We used to have a bitmap for this to just mark | |
1031 | SSA versions we had visited. But non-sparse bitmaps are way too | |
1032 | expensive, while sparse bitmaps may cause quadratic behavior. | |
53b4bf74 DN |
1033 | |
1034 | IS_DFS is true if the caller wants to perform a depth-first search | |
1035 | when visiting PHI nodes. A DFS will visit each PHI argument and | |
1036 | call FN after each one. Otherwise, all the arguments are | |
1037 | visited first and then FN is called with each of the visited | |
1038 | arguments in a separate pass. */ | |
6de9cd9a DN |
1039 | |
1040 | static bool | |
1041 | walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, | |
d0ce8e4c | 1042 | struct pointer_set_t *visited, bool is_dfs) |
6de9cd9a DN |
1043 | { |
1044 | tree def_stmt; | |
1045 | ||
d0ce8e4c | 1046 | if (pointer_set_insert (visited, var)) |
6de9cd9a DN |
1047 | return false; |
1048 | ||
6de9cd9a DN |
1049 | def_stmt = SSA_NAME_DEF_STMT (var); |
1050 | ||
1051 | if (TREE_CODE (def_stmt) != PHI_NODE) | |
1052 | { | |
1053 | /* If we reached the end of the use-def chain, call FN. */ | |
53b4bf74 | 1054 | return fn (var, def_stmt, data); |
6de9cd9a DN |
1055 | } |
1056 | else | |
1057 | { | |
1058 | int i; | |
1059 | ||
53b4bf74 DN |
1060 | /* When doing a breadth-first search, call FN before following the |
1061 | use-def links for each argument. */ | |
1062 | if (!is_dfs) | |
1063 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) | |
1064 | if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) | |
1065 | return true; | |
1066 | ||
1067 | /* Follow use-def links out of each PHI argument. */ | |
6de9cd9a DN |
1068 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) |
1069 | { | |
1070 | tree arg = PHI_ARG_DEF (def_stmt, i); | |
1071 | if (TREE_CODE (arg) == SSA_NAME | |
53b4bf74 | 1072 | && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) |
6de9cd9a DN |
1073 | return true; |
1074 | } | |
53b4bf74 DN |
1075 | |
1076 | /* When doing a depth-first search, call FN after following the | |
1077 | use-def links for each argument. */ | |
1078 | if (is_dfs) | |
1079 | for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) | |
1080 | if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) | |
1081 | return true; | |
6de9cd9a | 1082 | } |
53b4bf74 | 1083 | |
6de9cd9a DN |
1084 | return false; |
1085 | } | |
1086 | ||
1087 | ||
1088 | ||
53b4bf74 DN |
1089 | /* Walk use-def chains starting at the SSA variable VAR. Call |
1090 | function FN at each reaching definition found. FN takes three | |
1091 | arguments: VAR, its defining statement (DEF_STMT) and a generic | |
1092 | pointer to whatever state information that FN may want to maintain | |
1093 | (DATA). FN is able to stop the walk by returning true, otherwise | |
1094 | in order to continue the walk, FN should return false. | |
6de9cd9a DN |
1095 | |
1096 | Note, that if DEF_STMT is a PHI node, the semantics are slightly | |
53b4bf74 DN |
1097 | different. The first argument to FN is no longer the original |
1098 | variable VAR, but the PHI argument currently being examined. If FN | |
1099 | wants to get at VAR, it should call PHI_RESULT (PHI). | |
1100 | ||
1101 | If IS_DFS is true, this function will: | |
6de9cd9a | 1102 | |
53b4bf74 DN |
1103 | 1- walk the use-def chains for all the PHI arguments, and, |
1104 | 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. | |
1105 | ||
1106 | If IS_DFS is false, the two steps above are done in reverse order | |
1107 | (i.e., a breadth-first search). */ | |
6de9cd9a | 1108 | |
6de9cd9a DN |
1109 | |
1110 | void | |
53b4bf74 DN |
1111 | walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, |
1112 | bool is_dfs) | |
6de9cd9a DN |
1113 | { |
1114 | tree def_stmt; | |
1115 | ||
1e128c5f | 1116 | gcc_assert (TREE_CODE (var) == SSA_NAME); |
6de9cd9a DN |
1117 | |
1118 | def_stmt = SSA_NAME_DEF_STMT (var); | |
1119 | ||
1120 | /* We only need to recurse if the reaching definition comes from a PHI | |
1121 | node. */ | |
1122 | if (TREE_CODE (def_stmt) != PHI_NODE) | |
1123 | (*fn) (var, def_stmt, data); | |
1124 | else | |
1125 | { | |
d0ce8e4c | 1126 | struct pointer_set_t *visited = pointer_set_create (); |
53b4bf74 | 1127 | walk_use_def_chains_1 (var, fn, data, visited, is_dfs); |
d0ce8e4c | 1128 | pointer_set_destroy (visited); |
6de9cd9a DN |
1129 | } |
1130 | } | |
1131 | ||
6de9cd9a DN |
1132 | \f |
1133 | /* Emit warnings for uninitialized variables. This is done in two passes. | |
1134 | ||
1135 | The first pass notices real uses of SSA names with default definitions. | |
1136 | Such uses are unconditionally uninitialized, and we can be certain that | |
1137 | such a use is a mistake. This pass is run before most optimizations, | |
1138 | so that we catch as many as we can. | |
1139 | ||
1140 | The second pass follows PHI nodes to find uses that are potentially | |
1141 | uninitialized. In this case we can't necessarily prove that the use | |
1142 | is really uninitialized. This pass is run after most optimizations, | |
1143 | so that we thread as many jumps and possible, and delete as much dead | |
1144 | code as possible, in order to reduce false positives. We also look | |
1145 | again for plain uninitialized variables, since optimization may have | |
1146 | changed conditionally uninitialized to unconditionally uninitialized. */ | |
1147 | ||
1148 | /* Emit a warning for T, an SSA_NAME, being uninitialized. The exact | |
1149 | warning text is in MSGID and LOCUS may contain a location or be null. */ | |
1150 | ||
1151 | static void | |
4b794eaf | 1152 | warn_uninit (tree t, const char *gmsgid, void *data) |
6de9cd9a DN |
1153 | { |
1154 | tree var = SSA_NAME_VAR (t); | |
1155 | tree def = SSA_NAME_DEF_STMT (t); | |
bb0a4525 PB |
1156 | tree context = (tree) data; |
1157 | location_t * locus; | |
6de9cd9a DN |
1158 | |
1159 | /* Default uses (indicated by an empty definition statement), | |
1160 | are uninitialized. */ | |
1161 | if (!IS_EMPTY_STMT (def)) | |
1162 | return; | |
1163 | ||
1164 | /* Except for PARMs of course, which are always initialized. */ | |
1165 | if (TREE_CODE (var) == PARM_DECL) | |
1166 | return; | |
1167 | ||
1168 | /* Hard register variables get their initial value from the ether. */ | |
e670d9e4 | 1169 | if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) |
6de9cd9a DN |
1170 | return; |
1171 | ||
1172 | /* TREE_NO_WARNING either means we already warned, or the front end | |
1173 | wishes to suppress the warning. */ | |
1174 | if (TREE_NO_WARNING (var)) | |
1175 | return; | |
1176 | ||
bb0a4525 PB |
1177 | locus = (context != NULL && EXPR_HAS_LOCATION (context) |
1178 | ? EXPR_LOCUS (context) | |
1179 | : &DECL_SOURCE_LOCATION (var)); | |
4b794eaf | 1180 | warning (0, gmsgid, locus, var); |
6de9cd9a DN |
1181 | TREE_NO_WARNING (var) = 1; |
1182 | } | |
1183 | ||
1184 | /* Called via walk_tree, look for SSA_NAMEs that have empty definitions | |
1185 | and warn about them. */ | |
1186 | ||
1187 | static tree | |
1188 | warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) | |
1189 | { | |
6de9cd9a DN |
1190 | tree t = *tp; |
1191 | ||
978dee9a | 1192 | switch (TREE_CODE (t)) |
6de9cd9a | 1193 | { |
978dee9a RH |
1194 | case SSA_NAME: |
1195 | /* We only do data flow with SSA_NAMEs, so that's all we | |
1196 | can warn about. */ | |
bb0a4525 | 1197 | warn_uninit (t, "%H%qD is used uninitialized in this function", data); |
6de9cd9a | 1198 | *walk_subtrees = 0; |
978dee9a RH |
1199 | break; |
1200 | ||
1201 | case REALPART_EXPR: | |
1202 | case IMAGPART_EXPR: | |
1203 | /* The total store transformation performed during gimplification | |
1204 | creates uninitialized variable uses. If all is well, these will | |
1205 | be optimized away, so don't warn now. */ | |
1206 | if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME) | |
1207 | *walk_subtrees = 0; | |
1208 | break; | |
1209 | ||
1210 | default: | |
1211 | if (IS_TYPE_OR_DECL_P (t)) | |
1212 | *walk_subtrees = 0; | |
1213 | break; | |
6de9cd9a | 1214 | } |
6de9cd9a DN |
1215 | |
1216 | return NULL_TREE; | |
1217 | } | |
1218 | ||
1219 | /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions | |
1220 | and warn about them. */ | |
1221 | ||
1222 | static void | |
1223 | warn_uninitialized_phi (tree phi) | |
1224 | { | |
1225 | int i, n = PHI_NUM_ARGS (phi); | |
1226 | ||
1227 | /* Don't look at memory tags. */ | |
1228 | if (!is_gimple_reg (PHI_RESULT (phi))) | |
1229 | return; | |
1230 | ||
1231 | for (i = 0; i < n; ++i) | |
1232 | { | |
1233 | tree op = PHI_ARG_DEF (phi, i); | |
1234 | if (TREE_CODE (op) == SSA_NAME) | |
7a6336aa | 1235 | warn_uninit (op, "%H%qD may be used uninitialized in this function", |
6de9cd9a DN |
1236 | NULL); |
1237 | } | |
1238 | } | |
1239 | ||
c2924966 | 1240 | static unsigned int |
6de9cd9a DN |
1241 | execute_early_warn_uninitialized (void) |
1242 | { | |
1243 | block_stmt_iterator bsi; | |
1244 | basic_block bb; | |
1245 | ||
1246 | FOR_EACH_BB (bb) | |
1247 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
bb0a4525 PB |
1248 | { |
1249 | tree context = bsi_stmt (bsi); | |
1250 | walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var, | |
1251 | context, NULL); | |
1252 | } | |
c2924966 | 1253 | return 0; |
6de9cd9a DN |
1254 | } |
1255 | ||
c2924966 | 1256 | static unsigned int |
6de9cd9a DN |
1257 | execute_late_warn_uninitialized (void) |
1258 | { | |
1259 | basic_block bb; | |
1260 | tree phi; | |
1261 | ||
1262 | /* Re-do the plain uninitialized variable check, as optimization may have | |
1263 | straightened control flow. Do this first so that we don't accidentally | |
1264 | get a "may be" warning when we'd have seen an "is" warning later. */ | |
1265 | execute_early_warn_uninitialized (); | |
1266 | ||
1267 | FOR_EACH_BB (bb) | |
17192884 | 1268 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a | 1269 | warn_uninitialized_phi (phi); |
c2924966 | 1270 | return 0; |
6de9cd9a DN |
1271 | } |
1272 | ||
1273 | static bool | |
1274 | gate_warn_uninitialized (void) | |
1275 | { | |
1276 | return warn_uninitialized != 0; | |
1277 | } | |
1278 | ||
1279 | struct tree_opt_pass pass_early_warn_uninitialized = | |
1280 | { | |
1281 | NULL, /* name */ | |
1282 | gate_warn_uninitialized, /* gate */ | |
1283 | execute_early_warn_uninitialized, /* execute */ | |
1284 | NULL, /* sub */ | |
1285 | NULL, /* next */ | |
1286 | 0, /* static_pass_number */ | |
1287 | 0, /* tv_id */ | |
1288 | PROP_ssa, /* properties_required */ | |
1289 | 0, /* properties_provided */ | |
1290 | 0, /* properties_destroyed */ | |
1291 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1292 | 0, /* todo_flags_finish */ |
1293 | 0 /* letter */ | |
6de9cd9a DN |
1294 | }; |
1295 | ||
1296 | struct tree_opt_pass pass_late_warn_uninitialized = | |
1297 | { | |
1298 | NULL, /* name */ | |
1299 | gate_warn_uninitialized, /* gate */ | |
1300 | execute_late_warn_uninitialized, /* execute */ | |
1301 | NULL, /* sub */ | |
1302 | NULL, /* next */ | |
1303 | 0, /* static_pass_number */ | |
1304 | 0, /* tv_id */ | |
1305 | PROP_ssa, /* properties_required */ | |
1306 | 0, /* properties_provided */ | |
1307 | 0, /* properties_destroyed */ | |
1308 | 0, /* todo_flags_start */ | |
9f8628ba PB |
1309 | 0, /* todo_flags_finish */ |
1310 | 0 /* letter */ | |
6de9cd9a | 1311 | }; |
52328bf6 | 1312 |