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