]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Functions to analyze and validate GIMPLE trees. |
bc7ffd06 | 2 | Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | Rewritten by Jason Merrill <jason@redhat.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 2, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING. If not, write to | |
366ccddb KC |
20 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
21 | Boston, MA 02110-1301, USA. */ | |
6de9cd9a DN |
22 | |
23 | #include "config.h" | |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "ggc.h" | |
27 | #include "tm.h" | |
28 | #include "tree.h" | |
eadf906f | 29 | #include "tree-gimple.h" |
0c322af3 | 30 | #include "tree-flow.h" |
6de9cd9a DN |
31 | #include "output.h" |
32 | #include "rtl.h" | |
33 | #include "expr.h" | |
34 | #include "bitmap.h" | |
35 | ||
bfe0d06b | 36 | /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi. */ |
6de9cd9a | 37 | |
6de9cd9a DN |
38 | /* Validation of GIMPLE expressions. */ |
39 | ||
0c322af3 | 40 | /* Return true if T is a GIMPLE RHS for an assignment to a temporary. */ |
6de9cd9a DN |
41 | |
42 | bool | |
17ad5b5e | 43 | is_gimple_formal_tmp_rhs (tree t) |
6de9cd9a DN |
44 | { |
45 | enum tree_code code = TREE_CODE (t); | |
46 | ||
47 | switch (TREE_CODE_CLASS (code)) | |
48 | { | |
6615c446 JO |
49 | case tcc_unary: |
50 | case tcc_binary: | |
51 | case tcc_comparison: | |
90051e16 | 52 | return true; |
6de9cd9a DN |
53 | |
54 | default: | |
55 | break; | |
56 | } | |
57 | ||
58 | switch (code) | |
59 | { | |
60 | case TRUTH_NOT_EXPR: | |
61 | case TRUTH_AND_EXPR: | |
62 | case TRUTH_OR_EXPR: | |
63 | case TRUTH_XOR_EXPR: | |
64 | case ADDR_EXPR: | |
65 | case CALL_EXPR: | |
66 | case CONSTRUCTOR: | |
67 | case COMPLEX_EXPR: | |
6de9cd9a DN |
68 | case INTEGER_CST: |
69 | case REAL_CST: | |
70 | case STRING_CST: | |
71 | case COMPLEX_CST: | |
72 | case VECTOR_CST: | |
0f59171d | 73 | case OBJ_TYPE_REF: |
0bca51f0 | 74 | case ASSERT_EXPR: |
90051e16 | 75 | return true; |
6de9cd9a DN |
76 | |
77 | default: | |
78 | break; | |
79 | } | |
80 | ||
90051e16 | 81 | return is_gimple_lvalue (t) || is_gimple_val (t); |
6de9cd9a DN |
82 | } |
83 | ||
17ad5b5e RH |
84 | /* Returns true iff T is a valid RHS for an assignment to a renamed |
85 | user -- or front-end generated artificial -- variable. */ | |
0c322af3 JM |
86 | |
87 | bool | |
88 | is_gimple_reg_rhs (tree t) | |
89 | { | |
17ad5b5e RH |
90 | /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto |
91 | and the LHS is a user variable, then we need to introduce a formal | |
92 | temporary. This way the optimizers can determine that the user | |
93 | variable is only modified if evaluation of the RHS does not throw. | |
94 | ||
95 | Don't force a temp of a non-renamable type; the copy could be | |
96 | arbitrarily expensive. Instead we will generate a V_MAY_DEF for | |
97 | the assignment. */ | |
0c322af3 | 98 | |
0c322af3 | 99 | if (is_gimple_reg_type (TREE_TYPE (t)) |
17ad5b5e RH |
100 | && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t)) |
101 | || tree_could_throw_p (t))) | |
102 | return false; | |
103 | ||
104 | return is_gimple_formal_tmp_rhs (t); | |
0c322af3 JM |
105 | } |
106 | ||
107 | /* Returns true iff T is a valid RHS for an assignment to an un-renamed | |
108 | LHS, or for a call argument. */ | |
109 | ||
110 | bool | |
111 | is_gimple_mem_rhs (tree t) | |
112 | { | |
49382b6c JM |
113 | /* If we're dealing with a renamable type, either source or dest must be |
114 | a renamed variable. Also force a temporary if the type doesn't need | |
115 | to be stored in memory, since it's cheap and prevents erroneous | |
116 | tailcalls (PR 17526). */ | |
117 | if (is_gimple_reg_type (TREE_TYPE (t)) | |
118 | || TYPE_MODE (TREE_TYPE (t)) != BLKmode) | |
0c322af3 JM |
119 | return is_gimple_val (t); |
120 | else | |
17ad5b5e | 121 | return is_gimple_formal_tmp_rhs (t); |
0c322af3 JM |
122 | } |
123 | ||
124 | /* Returns the appropriate RHS predicate for this LHS. */ | |
125 | ||
126 | gimple_predicate | |
127 | rhs_predicate_for (tree lhs) | |
128 | { | |
17ad5b5e RH |
129 | if (is_gimple_formal_tmp_var (lhs)) |
130 | return is_gimple_formal_tmp_rhs; | |
0c322af3 JM |
131 | else if (is_gimple_reg (lhs)) |
132 | return is_gimple_reg_rhs; | |
133 | else | |
134 | return is_gimple_mem_rhs; | |
135 | } | |
136 | ||
90051e16 | 137 | /* Return true if T is a valid LHS for a GIMPLE assignment expression. */ |
6de9cd9a DN |
138 | |
139 | bool | |
140 | is_gimple_lvalue (tree t) | |
141 | { | |
e847cc68 | 142 | return (is_gimple_addressable (t) |
d25cee4d | 143 | || TREE_CODE (t) == WITH_SIZE_EXPR |
6de9cd9a DN |
144 | /* These are complex lvalues, but don't have addresses, so they |
145 | go here. */ | |
146 | || TREE_CODE (t) == BIT_FIELD_REF); | |
147 | } | |
148 | ||
90051e16 | 149 | /* Return true if T is a GIMPLE condition. */ |
6de9cd9a DN |
150 | |
151 | bool | |
152 | is_gimple_condexpr (tree t) | |
153 | { | |
6615c446 | 154 | return (is_gimple_val (t) || COMPARISON_CLASS_P (t)); |
6de9cd9a DN |
155 | } |
156 | ||
e847cc68 | 157 | /* Return true if T is something whose address can be taken. */ |
6de9cd9a DN |
158 | |
159 | bool | |
e847cc68 | 160 | is_gimple_addressable (tree t) |
6de9cd9a | 161 | { |
9e51aaf5 | 162 | return (is_gimple_id (t) || handled_component_p (t) |
1b096a0a | 163 | || INDIRECT_REF_P (t)); |
6de9cd9a DN |
164 | } |
165 | ||
90051e16 | 166 | /* Return true if T is function invariant. Or rather a restricted |
6de9cd9a DN |
167 | form of function invariant. */ |
168 | ||
169 | bool | |
170 | is_gimple_min_invariant (tree t) | |
171 | { | |
172 | switch (TREE_CODE (t)) | |
173 | { | |
174 | case ADDR_EXPR: | |
175 | return TREE_INVARIANT (t); | |
176 | ||
177 | case INTEGER_CST: | |
178 | case REAL_CST: | |
179 | case STRING_CST: | |
180 | case COMPLEX_CST: | |
181 | case VECTOR_CST: | |
f1b19062 | 182 | return true; |
6de9cd9a DN |
183 | |
184 | default: | |
185 | return false; | |
186 | } | |
187 | } | |
188 | ||
90051e16 | 189 | /* Return true if T looks like a valid GIMPLE statement. */ |
6de9cd9a DN |
190 | |
191 | bool | |
192 | is_gimple_stmt (tree t) | |
193 | { | |
194 | enum tree_code code = TREE_CODE (t); | |
195 | ||
196 | if (IS_EMPTY_STMT (t)) | |
197 | return 1; | |
198 | ||
199 | switch (code) | |
200 | { | |
201 | case BIND_EXPR: | |
202 | case COND_EXPR: | |
203 | /* These are only valid if they're void. */ | |
506e2710 | 204 | return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t)); |
6de9cd9a DN |
205 | |
206 | case SWITCH_EXPR: | |
207 | case GOTO_EXPR: | |
208 | case RETURN_EXPR: | |
209 | case LABEL_EXPR: | |
210 | case CASE_LABEL_EXPR: | |
211 | case TRY_CATCH_EXPR: | |
212 | case TRY_FINALLY_EXPR: | |
213 | case EH_FILTER_EXPR: | |
214 | case CATCH_EXPR: | |
215 | case ASM_EXPR: | |
216 | case RESX_EXPR: | |
217 | case PHI_NODE: | |
218 | case STATEMENT_LIST: | |
953ff289 DN |
219 | case OMP_PARALLEL: |
220 | case OMP_FOR: | |
221 | case OMP_SECTIONS: | |
222 | case OMP_SECTION: | |
223 | case OMP_SINGLE: | |
224 | case OMP_MASTER: | |
225 | case OMP_ORDERED: | |
226 | case OMP_CRITICAL: | |
6de9cd9a | 227 | /* These are always void. */ |
90051e16 | 228 | return true; |
6de9cd9a | 229 | |
6de9cd9a DN |
230 | case CALL_EXPR: |
231 | case MODIFY_EXPR: | |
232 | /* These are valid regardless of their type. */ | |
90051e16 | 233 | return true; |
6de9cd9a DN |
234 | |
235 | default: | |
90051e16 | 236 | return false; |
6de9cd9a DN |
237 | } |
238 | } | |
239 | ||
90051e16 | 240 | /* Return true if T is a variable. */ |
6de9cd9a DN |
241 | |
242 | bool | |
243 | is_gimple_variable (tree t) | |
244 | { | |
245 | return (TREE_CODE (t) == VAR_DECL | |
246 | || TREE_CODE (t) == PARM_DECL | |
247 | || TREE_CODE (t) == RESULT_DECL | |
248 | || TREE_CODE (t) == SSA_NAME); | |
249 | } | |
250 | ||
90051e16 | 251 | /* Return true if T is a GIMPLE identifier (something with an address). */ |
6de9cd9a | 252 | |
688e936d | 253 | bool |
6de9cd9a DN |
254 | is_gimple_id (tree t) |
255 | { | |
256 | return (is_gimple_variable (t) | |
257 | || TREE_CODE (t) == FUNCTION_DECL | |
258 | || TREE_CODE (t) == LABEL_DECL | |
0534fa56 | 259 | || TREE_CODE (t) == CONST_DECL |
6de9cd9a DN |
260 | /* Allow string constants, since they are addressable. */ |
261 | || TREE_CODE (t) == STRING_CST); | |
262 | } | |
263 | ||
90051e16 | 264 | /* Return true if TYPE is a suitable type for a scalar register variable. */ |
6de9cd9a DN |
265 | |
266 | bool | |
267 | is_gimple_reg_type (tree type) | |
268 | { | |
e41d82f5 | 269 | return !AGGREGATE_TYPE_P (type); |
6de9cd9a DN |
270 | } |
271 | ||
e41d82f5 | 272 | /* Return true if T is a non-aggregate register variable. */ |
6de9cd9a DN |
273 | |
274 | bool | |
275 | is_gimple_reg (tree t) | |
276 | { | |
277 | if (TREE_CODE (t) == SSA_NAME) | |
278 | t = SSA_NAME_VAR (t); | |
279 | ||
326eda4b DB |
280 | if (MTAG_P (t)) |
281 | return false; | |
282 | ||
e670d9e4 RH |
283 | if (!is_gimple_variable (t)) |
284 | return false; | |
e41d82f5 | 285 | |
e670d9e4 RH |
286 | if (!is_gimple_reg_type (TREE_TYPE (t))) |
287 | return false; | |
288 | ||
289 | /* A volatile decl is not acceptable because we can't reuse it as | |
290 | needed. We need to copy it into a temp first. */ | |
291 | if (TREE_THIS_VOLATILE (t)) | |
292 | return false; | |
293 | ||
294 | /* We define "registers" as things that can be renamed as needed, | |
295 | which with our infrastructure does not apply to memory. */ | |
296 | if (needs_to_live_in_memory (t)) | |
297 | return false; | |
298 | ||
299 | /* Hard register variables are an interesting case. For those that | |
300 | are call-clobbered, we don't know where all the calls are, since | |
301 | we don't (want to) take into account which operations will turn | |
302 | into libcalls at the rtl level. For those that are call-saved, | |
303 | we don't currently model the fact that calls may in fact change | |
304 | global hard registers, nor do we examine ASM_CLOBBERS at the tree | |
305 | level, and so miss variable changes that might imply. All around, | |
306 | it seems safest to not do too much optimization with these at the | |
307 | tree level at all. We'll have to rely on the rtl optimizers to | |
308 | clean this up, as there we've got all the appropriate bits exposed. */ | |
309 | if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) | |
310 | return false; | |
311 | ||
e41d82f5 RH |
312 | /* Complex values must have been put into ssa form. That is, no |
313 | assignments to the individual components. */ | |
314 | if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE) | |
315 | return DECL_COMPLEX_GIMPLE_REG_P (t); | |
316 | ||
e670d9e4 | 317 | return true; |
6de9cd9a DN |
318 | } |
319 | ||
e8ca4159 | 320 | |
17ad5b5e | 321 | /* Returns true if T is a GIMPLE formal temporary variable. */ |
14797075 RH |
322 | |
323 | bool | |
17ad5b5e | 324 | is_gimple_formal_tmp_var (tree t) |
14797075 | 325 | { |
8b11a64c ZD |
326 | if (TREE_CODE (t) == SSA_NAME) |
327 | return true; | |
328 | ||
17ad5b5e | 329 | return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t); |
14797075 RH |
330 | } |
331 | ||
17ad5b5e | 332 | /* Returns true if T is a GIMPLE formal temporary register variable. */ |
14797075 RH |
333 | |
334 | bool | |
17ad5b5e | 335 | is_gimple_formal_tmp_reg (tree t) |
14797075 RH |
336 | { |
337 | /* The intent of this is to get hold of a value that won't change. | |
338 | An SSA_NAME qualifies no matter if its of a user variable or not. */ | |
339 | if (TREE_CODE (t) == SSA_NAME) | |
340 | return true; | |
341 | ||
342 | /* We don't know the lifetime characteristics of user variables. */ | |
17ad5b5e | 343 | if (!is_gimple_formal_tmp_var (t)) |
14797075 RH |
344 | return false; |
345 | ||
346 | /* Finally, it must be capable of being placed in a register. */ | |
347 | return is_gimple_reg (t); | |
348 | } | |
349 | ||
90051e16 | 350 | /* Return true if T is a GIMPLE variable whose address is not needed. */ |
6de9cd9a DN |
351 | |
352 | bool | |
353 | is_gimple_non_addressable (tree t) | |
354 | { | |
355 | if (TREE_CODE (t) == SSA_NAME) | |
356 | t = SSA_NAME_VAR (t); | |
357 | ||
c597ef4e | 358 | return (is_gimple_variable (t) && ! needs_to_live_in_memory (t)); |
6de9cd9a DN |
359 | } |
360 | ||
90051e16 | 361 | /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant. */ |
6de9cd9a DN |
362 | |
363 | bool | |
364 | is_gimple_val (tree t) | |
365 | { | |
366 | /* Make loads from volatiles and memory vars explicit. */ | |
367 | if (is_gimple_variable (t) | |
368 | && is_gimple_reg_type (TREE_TYPE (t)) | |
369 | && !is_gimple_reg (t)) | |
90051e16 | 370 | return false; |
6de9cd9a DN |
371 | |
372 | /* FIXME make these decls. That can happen only when we expose the | |
373 | entire landing-pad construct at the tree level. */ | |
374 | if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR) | |
375 | return 1; | |
376 | ||
377 | return (is_gimple_variable (t) || is_gimple_min_invariant (t)); | |
378 | } | |
379 | ||
e670d9e4 RH |
380 | /* Similarly, but accept hard registers as inputs to asm statements. */ |
381 | ||
382 | bool | |
383 | is_gimple_asm_val (tree t) | |
384 | { | |
385 | if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) | |
386 | return true; | |
387 | ||
388 | return is_gimple_val (t); | |
389 | } | |
6de9cd9a | 390 | |
90051e16 | 391 | /* Return true if T is a GIMPLE minimal lvalue. */ |
6de9cd9a DN |
392 | |
393 | bool | |
394 | is_gimple_min_lval (tree t) | |
395 | { | |
396 | return (is_gimple_id (t) | |
397 | || TREE_CODE (t) == INDIRECT_REF); | |
398 | } | |
399 | ||
90051e16 | 400 | /* Return true if T is a typecast operation. */ |
6de9cd9a DN |
401 | |
402 | bool | |
403 | is_gimple_cast (tree t) | |
404 | { | |
405 | return (TREE_CODE (t) == NOP_EXPR | |
406 | || TREE_CODE (t) == CONVERT_EXPR | |
407 | || TREE_CODE (t) == FIX_TRUNC_EXPR | |
408 | || TREE_CODE (t) == FIX_CEIL_EXPR | |
409 | || TREE_CODE (t) == FIX_FLOOR_EXPR | |
410 | || TREE_CODE (t) == FIX_ROUND_EXPR); | |
411 | } | |
412 | ||
0f59171d RH |
413 | /* Return true if T is a valid op0 of a CALL_EXPR. */ |
414 | ||
415 | bool | |
416 | is_gimple_call_addr (tree t) | |
417 | { | |
418 | return (TREE_CODE (t) == OBJ_TYPE_REF | |
419 | || is_gimple_val (t)); | |
420 | } | |
6de9cd9a DN |
421 | |
422 | /* If T makes a function call, return the corresponding CALL_EXPR operand. | |
423 | Otherwise, return NULL_TREE. */ | |
424 | ||
425 | tree | |
426 | get_call_expr_in (tree t) | |
427 | { | |
90051e16 RH |
428 | if (TREE_CODE (t) == MODIFY_EXPR) |
429 | t = TREE_OPERAND (t, 1); | |
d25cee4d RH |
430 | if (TREE_CODE (t) == WITH_SIZE_EXPR) |
431 | t = TREE_OPERAND (t, 0); | |
6de9cd9a DN |
432 | if (TREE_CODE (t) == CALL_EXPR) |
433 | return t; | |
6de9cd9a DN |
434 | return NULL_TREE; |
435 | } | |
436 | ||
370d199d DN |
437 | /* Given a memory reference expression T, return its base address. |
438 | The base address of a memory reference expression is the main | |
439 | object being referenced. For instance, the base address for | |
440 | 'array[i].fld[j]' is 'array'. You can think of this as stripping | |
441 | away the offset part from a memory address. | |
442 | ||
443 | This function calls handled_component_p to strip away all the inner | |
444 | parts of the memory reference until it reaches the base object. */ | |
6de9cd9a DN |
445 | |
446 | tree | |
447 | get_base_address (tree t) | |
448 | { | |
afe84921 | 449 | while (handled_component_p (t)) |
75822272 RK |
450 | t = TREE_OPERAND (t, 0); |
451 | ||
452 | if (SSA_VAR_P (t) | |
453 | || TREE_CODE (t) == STRING_CST | |
454 | || TREE_CODE (t) == CONSTRUCTOR | |
1b096a0a | 455 | || INDIRECT_REF_P (t)) |
75822272 RK |
456 | return t; |
457 | else | |
458 | return NULL_TREE; | |
6de9cd9a DN |
459 | } |
460 | ||
6de9cd9a DN |
461 | void |
462 | recalculate_side_effects (tree t) | |
463 | { | |
464 | enum tree_code code = TREE_CODE (t); | |
ac1b13f4 | 465 | int len = TREE_CODE_LENGTH (code); |
6de9cd9a DN |
466 | int i; |
467 | ||
468 | switch (TREE_CODE_CLASS (code)) | |
469 | { | |
6615c446 | 470 | case tcc_expression: |
6de9cd9a DN |
471 | switch (code) |
472 | { | |
473 | case INIT_EXPR: | |
474 | case MODIFY_EXPR: | |
475 | case VA_ARG_EXPR: | |
6de9cd9a DN |
476 | case PREDECREMENT_EXPR: |
477 | case PREINCREMENT_EXPR: | |
478 | case POSTDECREMENT_EXPR: | |
479 | case POSTINCREMENT_EXPR: | |
480 | /* All of these have side-effects, no matter what their | |
481 | operands are. */ | |
482 | return; | |
483 | ||
484 | default: | |
485 | break; | |
486 | } | |
487 | /* Fall through. */ | |
488 | ||
6615c446 JO |
489 | case tcc_comparison: /* a comparison expression */ |
490 | case tcc_unary: /* a unary arithmetic expression */ | |
491 | case tcc_binary: /* a binary arithmetic expression */ | |
492 | case tcc_reference: /* a reference */ | |
6de9cd9a | 493 | TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t); |
ac1b13f4 | 494 | for (i = 0; i < len; ++i) |
6de9cd9a DN |
495 | { |
496 | tree op = TREE_OPERAND (t, i); | |
497 | if (op && TREE_SIDE_EFFECTS (op)) | |
498 | TREE_SIDE_EFFECTS (t) = 1; | |
499 | } | |
500 | break; | |
6615c446 JO |
501 | |
502 | default: | |
503 | /* Can never be used with non-expressions. */ | |
504 | gcc_unreachable (); | |
6de9cd9a DN |
505 | } |
506 | } |