1 /* Functions to analyze and validate GIMPLE trees.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
5 Rewritten by Jason Merrill <jason@redhat.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "tree-gimple.h"
30 #include "tree-flow.h"
36 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi. */
38 /* Validation of GIMPLE expressions. */
40 /* Return true if T is a GIMPLE RHS for an assignment to a temporary. */
43 is_gimple_formal_tmp_rhs (tree t
)
45 enum tree_code code
= TREE_CODE (t
);
47 switch (TREE_CODE_CLASS (code
))
83 return is_gimple_lvalue (t
) || is_gimple_val (t
);
86 /* Returns true iff T is a valid RHS for an assignment to a renamed
87 user -- or front-end generated artificial -- variable. */
90 is_gimple_reg_rhs (tree t
)
92 /* If the RHS of the GIMPLE_MODIFY_STMT may throw or make a nonlocal goto
93 and the LHS is a user variable, then we need to introduce a formal
94 temporary. This way the optimizers can determine that the user
95 variable is only modified if evaluation of the RHS does not throw.
97 Don't force a temp of a non-renamable type; the copy could be
98 arbitrarily expensive. Instead we will generate a VDEF for
101 if (is_gimple_reg_type (TREE_TYPE (t
))
102 && ((TREE_CODE (t
) == CALL_EXPR
&& TREE_SIDE_EFFECTS (t
))
103 || tree_could_throw_p (t
)))
106 return is_gimple_formal_tmp_rhs (t
);
109 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
110 LHS, or for a call argument. */
113 is_gimple_mem_rhs (tree t
)
115 /* If we're dealing with a renamable type, either source or dest must be
116 a renamed variable. */
117 if (is_gimple_reg_type (TREE_TYPE (t
)))
118 return is_gimple_val (t
);
120 return is_gimple_formal_tmp_rhs (t
);
123 /* Returns the appropriate RHS predicate for this LHS. */
126 rhs_predicate_for (tree lhs
)
128 if (is_gimple_formal_tmp_var (lhs
))
129 return is_gimple_formal_tmp_rhs
;
130 else if (is_gimple_reg (lhs
))
131 return is_gimple_reg_rhs
;
133 return is_gimple_mem_rhs
;
136 /* Return true if T is a valid LHS for a GIMPLE assignment expression. */
139 is_gimple_lvalue (tree t
)
141 return (is_gimple_addressable (t
)
142 || TREE_CODE (t
) == WITH_SIZE_EXPR
143 /* These are complex lvalues, but don't have addresses, so they
145 || TREE_CODE (t
) == BIT_FIELD_REF
);
148 /* Return true if T is a GIMPLE condition. */
151 is_gimple_condexpr (tree t
)
153 return (is_gimple_val (t
) || (COMPARISON_CLASS_P (t
)
154 && !tree_could_trap_p (t
)
155 && is_gimple_val (TREE_OPERAND (t
, 0))
156 && is_gimple_val (TREE_OPERAND (t
, 1))));
159 /* Return true if T is something whose address can be taken. */
162 is_gimple_addressable (tree t
)
164 return (is_gimple_id (t
) || handled_component_p (t
)
165 || INDIRECT_REF_P (t
));
168 /* Return true if T is a valid gimple constant. */
171 is_gimple_constant (const_tree t
)
173 switch (TREE_CODE (t
))
183 /* Vector constant constructors are gimple invariant. */
185 if (TREE_TYPE (t
) && TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
186 return TREE_CONSTANT (t
);
195 /* Return true if T is a gimple address. */
198 is_gimple_address (const_tree t
)
202 if (TREE_CODE (t
) != ADDR_EXPR
)
205 op
= TREE_OPERAND (t
, 0);
206 while (handled_component_p (op
))
208 if ((TREE_CODE (op
) == ARRAY_REF
209 || TREE_CODE (op
) == ARRAY_RANGE_REF
)
210 && !is_gimple_val (TREE_OPERAND (op
, 1)))
213 op
= TREE_OPERAND (op
, 0);
216 if (CONSTANT_CLASS_P (op
) || INDIRECT_REF_P (op
))
219 switch (TREE_CODE (op
))
234 /* Return true if T is a gimple invariant address. */
237 is_gimple_invariant_address (const_tree t
)
241 if (TREE_CODE (t
) != ADDR_EXPR
)
244 op
= TREE_OPERAND (t
, 0);
245 while (handled_component_p (op
))
247 switch (TREE_CODE (op
))
250 case ARRAY_RANGE_REF
:
251 if (!is_gimple_constant (TREE_OPERAND (op
, 1))
252 || TREE_OPERAND (op
, 2) != NULL_TREE
253 || TREE_OPERAND (op
, 3) != NULL_TREE
)
258 if (TREE_OPERAND (op
, 2) != NULL_TREE
)
264 op
= TREE_OPERAND (op
, 0);
267 return CONSTANT_CLASS_P (op
) || decl_address_invariant_p (op
);
270 /* Return true if T is a GIMPLE minimal invariant. It's a restricted
271 form of function invariant. */
274 is_gimple_min_invariant (const_tree t
)
276 if (TREE_CODE (t
) == ADDR_EXPR
)
277 return is_gimple_invariant_address (t
);
279 return is_gimple_constant (t
);
282 /* Return true if T looks like a valid GIMPLE statement. */
285 is_gimple_stmt (tree t
)
287 const enum tree_code code
= TREE_CODE (t
);
292 /* The only valid NOP_EXPR is the empty statement. */
293 return IS_EMPTY_STMT (t
);
297 /* These are only valid if they're void. */
298 return TREE_TYPE (t
) == NULL
|| VOID_TYPE_P (TREE_TYPE (t
));
304 case CASE_LABEL_EXPR
:
306 case TRY_FINALLY_EXPR
:
309 case CHANGE_DYNAMIC_TYPE_EXPR
:
317 case OMP_SECTIONS_SWITCH
:
326 case OMP_ATOMIC_LOAD
:
327 case OMP_ATOMIC_STORE
:
328 /* These are always void. */
332 case GIMPLE_MODIFY_STMT
:
334 /* These are valid regardless of their type. */
342 /* Return true if T is a variable. */
345 is_gimple_variable (tree t
)
347 return (TREE_CODE (t
) == VAR_DECL
348 || TREE_CODE (t
) == PARM_DECL
349 || TREE_CODE (t
) == RESULT_DECL
350 || TREE_CODE (t
) == SSA_NAME
);
353 /* Return true if T is a GIMPLE identifier (something with an address). */
356 is_gimple_id (tree t
)
358 return (is_gimple_variable (t
)
359 || TREE_CODE (t
) == FUNCTION_DECL
360 || TREE_CODE (t
) == LABEL_DECL
361 || TREE_CODE (t
) == CONST_DECL
362 /* Allow string constants, since they are addressable. */
363 || TREE_CODE (t
) == STRING_CST
);
366 /* Return true if TYPE is a suitable type for a scalar register variable. */
369 is_gimple_reg_type (tree type
)
371 /* In addition to aggregate types, we also exclude complex types if not
372 optimizing because they can be subject to partial stores in GNU C by
373 means of the __real__ and __imag__ operators and we cannot promote
374 them to total stores (see gimplify_modify_expr_complex_part). */
375 return !(AGGREGATE_TYPE_P (type
)
376 || (TREE_CODE (type
) == COMPLEX_TYPE
&& !optimize
));
380 /* Return true if T is a non-aggregate register variable. */
383 is_gimple_reg (tree t
)
385 if (TREE_CODE (t
) == SSA_NAME
)
386 t
= SSA_NAME_VAR (t
);
391 if (!is_gimple_variable (t
))
394 if (!is_gimple_reg_type (TREE_TYPE (t
)))
397 /* A volatile decl is not acceptable because we can't reuse it as
398 needed. We need to copy it into a temp first. */
399 if (TREE_THIS_VOLATILE (t
))
402 /* We define "registers" as things that can be renamed as needed,
403 which with our infrastructure does not apply to memory. */
404 if (needs_to_live_in_memory (t
))
407 /* Hard register variables are an interesting case. For those that
408 are call-clobbered, we don't know where all the calls are, since
409 we don't (want to) take into account which operations will turn
410 into libcalls at the rtl level. For those that are call-saved,
411 we don't currently model the fact that calls may in fact change
412 global hard registers, nor do we examine ASM_CLOBBERS at the tree
413 level, and so miss variable changes that might imply. All around,
414 it seems safest to not do too much optimization with these at the
415 tree level at all. We'll have to rely on the rtl optimizers to
416 clean this up, as there we've got all the appropriate bits exposed. */
417 if (TREE_CODE (t
) == VAR_DECL
&& DECL_HARD_REGISTER (t
))
420 /* Complex and vector values must have been put into SSA-like form.
421 That is, no assignments to the individual components. */
422 if (TREE_CODE (TREE_TYPE (t
)) == COMPLEX_TYPE
423 || TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
424 return DECL_GIMPLE_REG_P (t
);
430 /* Returns true if T is a GIMPLE formal temporary variable. */
433 is_gimple_formal_tmp_var (tree t
)
435 if (TREE_CODE (t
) == SSA_NAME
)
438 return TREE_CODE (t
) == VAR_DECL
&& DECL_GIMPLE_FORMAL_TEMP_P (t
);
441 /* Returns true if T is a GIMPLE formal temporary register variable. */
444 is_gimple_formal_tmp_reg (tree t
)
446 /* The intent of this is to get hold of a value that won't change.
447 An SSA_NAME qualifies no matter if its of a user variable or not. */
448 if (TREE_CODE (t
) == SSA_NAME
)
451 /* We don't know the lifetime characteristics of user variables. */
452 if (!is_gimple_formal_tmp_var (t
))
455 /* Finally, it must be capable of being placed in a register. */
456 return is_gimple_reg (t
);
459 /* Return true if T is a GIMPLE variable whose address is not needed. */
462 is_gimple_non_addressable (tree t
)
464 if (TREE_CODE (t
) == SSA_NAME
)
465 t
= SSA_NAME_VAR (t
);
467 return (is_gimple_variable (t
) && ! needs_to_live_in_memory (t
));
470 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant. */
473 is_gimple_val (tree t
)
475 /* Make loads from volatiles and memory vars explicit. */
476 if (is_gimple_variable (t
)
477 && is_gimple_reg_type (TREE_TYPE (t
))
478 && !is_gimple_reg (t
))
481 /* FIXME make these decls. That can happen only when we expose the
482 entire landing-pad construct at the tree level. */
483 if (TREE_CODE (t
) == EXC_PTR_EXPR
|| TREE_CODE (t
) == FILTER_EXPR
)
486 return (is_gimple_variable (t
) || is_gimple_min_invariant (t
));
489 /* Similarly, but accept hard registers as inputs to asm statements. */
492 is_gimple_asm_val (tree t
)
494 if (TREE_CODE (t
) == VAR_DECL
&& DECL_HARD_REGISTER (t
))
497 return is_gimple_val (t
);
500 /* Return true if T is a GIMPLE minimal lvalue. */
503 is_gimple_min_lval (tree t
)
505 return (is_gimple_id (t
)
506 || TREE_CODE (t
) == INDIRECT_REF
);
509 /* Return true if T is a typecast operation. */
512 is_gimple_cast (tree t
)
514 return (CONVERT_EXPR_P (t
)
515 || TREE_CODE (t
) == FIX_TRUNC_EXPR
);
518 /* Return true if T is a valid function operand of a CALL_EXPR. */
521 is_gimple_call_addr (tree t
)
523 return (TREE_CODE (t
) == OBJ_TYPE_REF
524 || is_gimple_val (t
));
527 /* If T makes a function call, return the corresponding CALL_EXPR operand.
528 Otherwise, return NULL_TREE. */
531 get_call_expr_in (tree t
)
533 /* FIXME tuples: delete the assertion below when conversion complete. */
534 gcc_assert (TREE_CODE (t
) != MODIFY_EXPR
);
535 if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
536 t
= GIMPLE_STMT_OPERAND (t
, 1);
537 if (TREE_CODE (t
) == WITH_SIZE_EXPR
)
538 t
= TREE_OPERAND (t
, 0);
539 if (TREE_CODE (t
) == CALL_EXPR
)
544 /* Given a memory reference expression T, return its base address.
545 The base address of a memory reference expression is the main
546 object being referenced. For instance, the base address for
547 'array[i].fld[j]' is 'array'. You can think of this as stripping
548 away the offset part from a memory address.
550 This function calls handled_component_p to strip away all the inner
551 parts of the memory reference until it reaches the base object. */
554 get_base_address (tree t
)
556 while (handled_component_p (t
))
557 t
= TREE_OPERAND (t
, 0);
560 || TREE_CODE (t
) == STRING_CST
561 || TREE_CODE (t
) == CONSTRUCTOR
562 || INDIRECT_REF_P (t
))
569 recalculate_side_effects (tree t
)
571 enum tree_code code
= TREE_CODE (t
);
572 int len
= TREE_OPERAND_LENGTH (t
);
575 switch (TREE_CODE_CLASS (code
))
581 case GIMPLE_MODIFY_STMT
:
583 case PREDECREMENT_EXPR
:
584 case PREINCREMENT_EXPR
:
585 case POSTDECREMENT_EXPR
:
586 case POSTINCREMENT_EXPR
:
587 /* All of these have side-effects, no matter what their
596 case tcc_comparison
: /* a comparison expression */
597 case tcc_unary
: /* a unary arithmetic expression */
598 case tcc_binary
: /* a binary arithmetic expression */
599 case tcc_reference
: /* a reference */
600 case tcc_vl_exp
: /* a function call */
601 TREE_SIDE_EFFECTS (t
) = TREE_THIS_VOLATILE (t
);
602 for (i
= 0; i
< len
; ++i
)
604 tree op
= TREE_OPERAND (t
, i
);
605 if (op
&& TREE_SIDE_EFFECTS (op
))
606 TREE_SIDE_EFFECTS (t
) = 1;
611 /* Can never be used with non-expressions. */
616 /* Canonicalize a tree T for use in a COND_EXPR as conditional. Returns
617 a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
618 we failed to create one. */
621 canonicalize_cond_expr_cond (tree t
)
623 /* For (bool)x use x != 0. */
624 if (TREE_CODE (t
) == NOP_EXPR
625 && TREE_TYPE (t
) == boolean_type_node
)
627 tree top0
= TREE_OPERAND (t
, 0);
628 t
= build2 (NE_EXPR
, TREE_TYPE (t
),
629 top0
, build_int_cst (TREE_TYPE (top0
), 0));
631 /* For !x use x == 0. */
632 else if (TREE_CODE (t
) == TRUTH_NOT_EXPR
)
634 tree top0
= TREE_OPERAND (t
, 0);
635 t
= build2 (EQ_EXPR
, TREE_TYPE (t
),
636 top0
, build_int_cst (TREE_TYPE (top0
), 0));
638 /* For cmp ? 1 : 0 use cmp. */
639 else if (TREE_CODE (t
) == COND_EXPR
640 && COMPARISON_CLASS_P (TREE_OPERAND (t
, 0))
641 && integer_onep (TREE_OPERAND (t
, 1))
642 && integer_zerop (TREE_OPERAND (t
, 2)))
644 tree top0
= TREE_OPERAND (t
, 0);
645 t
= build2 (TREE_CODE (top0
), TREE_TYPE (t
),
646 TREE_OPERAND (top0
, 0), TREE_OPERAND (top0
, 1));
649 if (is_gimple_condexpr (t
))