1 /* Functions to analyze and validate GIMPLE trees.
2 Copyright (C) 2002, 2003 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
4 Rewritten by Jason Merrill <jason@redhat.com>
6 This file is part of GCC.
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)
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.
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. */
25 #include "coretypes.h"
29 #include "tree-gimple.h"
35 /* GCC GIMPLE structure
37 Inspired by the SIMPLE C grammar at
39 http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
43 DECL_SAVED_TREE -> block
46 BIND_EXPR_VARS -> DECL chain
47 BIND_EXPR_BLOCK -> BLOCK
48 BIND_EXPR_BODY -> compound-stmt
51 op0 -> non-compound-stmt
54 (or other alternate solution)
55 stmt: compound-stmt | non-compound-stmt
74 op2 -> array of case labels (as LABEL_DECLs?)
75 FIXME: add case value info
76 The SWITCH_LABELS (op2) are sorted in ascending order, and the
77 last label in the vector is always the default case.
80 op0 -> LABEL_DECL | '*' ID
84 | MODIFY_EXPR -> RESULT_DECL, varname
85 | THROW_EXPR? do we need/want such a thing for opts, perhaps
86 to generate an ERT_THROW region? I think so.
87 Hmm...this would only work at the GIMPLE level, where we know that
88 the call args don't have any EH impact. Perhaps
89 annotation of the CALL_EXPR would work better.
95 CASE_LOW -> val | NULL_TREE
96 CASE_HIGH -> val | NULL_TREE
97 CASE_LABEL -> LABEL_DECL FIXME
117 addr-expr-arg : compref | ID
118 lhs: addr-expr-arg | '*' ID | bitfieldref
119 min-lval: ID | '*' ID
122 op0 -> compref | min-lval
127 op0 -> compref | min-lval
129 op0 -> compref | min-lval
134 condition : val | val relop val
137 rhs : varname | CONST
145 (cast here stands for all valid C typecasts)
175 static inline bool is_gimple_id (tree
);
177 /* Validation of GIMPLE expressions. */
179 /* Return nonzero if T is a GIMPLE RHS:
181 rhs : varname | CONST
183 | '&' varname_or_temp
188 | <CONSTRUCTOR <gimple_val ...>>
190 The last option is only valid GIMPLE for vector and complex types;
191 aggregate types should have their constructors decomposed. */
194 is_gimple_rhs (tree t
)
196 enum tree_code code
= TREE_CODE (t
);
198 switch (TREE_CODE_CLASS (code
))
219 /* FIXME lower VA_ARG_EXPR. */
232 if (is_gimple_lvalue (t
) || is_gimple_val (t
))
238 /* Returns nonzero if T is a valid CONSTRUCTOR component in GIMPLE, either
239 a val or another CONSTRUCTOR. */
242 is_gimple_constructor_elt (tree t
)
244 return (is_gimple_val (t
)
245 || TREE_CODE (t
) == CONSTRUCTOR
);
248 /* Return nonzero if T is a valid LHS for a GIMPLE assignment expression. */
251 is_gimple_lvalue (tree t
)
253 return (is_gimple_addr_expr_arg (t
)
254 || TREE_CODE (t
) == INDIRECT_REF
255 /* These are complex lvalues, but don't have addresses, so they
257 || TREE_CODE (t
) == BIT_FIELD_REF
);
261 /* Return nonzero if T is a GIMPLE condition:
268 is_gimple_condexpr (tree t
)
270 return (is_gimple_val (t
)
271 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<');
275 /* Return nonzero if T is a valid operand for '&':
283 is_gimple_addr_expr_arg (tree t
)
285 return (is_gimple_id (t
)
286 || TREE_CODE (t
) == ARRAY_REF
287 || TREE_CODE (t
) == COMPONENT_REF
288 || TREE_CODE (t
) == REALPART_EXPR
289 || TREE_CODE (t
) == IMAGPART_EXPR
);
292 /* Return nonzero if T is function invariant. Or rather a restricted
293 form of function invariant. */
296 is_gimple_min_invariant (tree t
)
298 switch (TREE_CODE (t
))
301 return TREE_INVARIANT (t
);
308 return !TREE_OVERFLOW (t
);
315 /* Return nonzero if T looks like a valid GIMPLE statement. */
318 is_gimple_stmt (tree t
)
320 enum tree_code code
= TREE_CODE (t
);
322 if (IS_EMPTY_STMT (t
))
329 /* These are only valid if they're void. */
330 return VOID_TYPE_P (TREE_TYPE (t
));
336 case CASE_LABEL_EXPR
:
338 case TRY_FINALLY_EXPR
:
345 /* These are always void. */
349 /* FIXME this should be lowered. */
353 /* FIXME should we work harder to make COMPOUND_EXPRs void? */
356 /* These are valid regardless of their type. */
364 /* Return nonzero if T is a variable. */
367 is_gimple_variable (tree t
)
369 return (TREE_CODE (t
) == VAR_DECL
370 || TREE_CODE (t
) == PARM_DECL
371 || TREE_CODE (t
) == RESULT_DECL
372 || TREE_CODE (t
) == SSA_NAME
);
375 /* Return nonzero if T is a GIMPLE identifier (something with an address). */
378 is_gimple_id (tree t
)
380 return (is_gimple_variable (t
)
381 || TREE_CODE (t
) == FUNCTION_DECL
382 || TREE_CODE (t
) == LABEL_DECL
383 /* Allow string constants, since they are addressable. */
384 || TREE_CODE (t
) == STRING_CST
);
387 /* Return nonzero if TYPE is a suitable type for a scalar register
391 is_gimple_reg_type (tree type
)
393 return (!AGGREGATE_TYPE_P (type
)
394 && TREE_CODE (type
) != COMPLEX_TYPE
);
398 /* Return nonzero if T is a scalar register variable. */
401 is_gimple_reg (tree t
)
403 if (TREE_CODE (t
) == SSA_NAME
)
404 t
= SSA_NAME_VAR (t
);
406 return (is_gimple_variable (t
)
407 && is_gimple_reg_type (TREE_TYPE (t
))
408 /* A volatile decl is not acceptable because we can't reuse it as
409 needed. We need to copy it into a temp first. */
410 && ! TREE_THIS_VOLATILE (t
)
411 && ! TREE_ADDRESSABLE (t
)
412 && ! needs_to_live_in_memory (t
));
415 /* Return nonzero if T is a GIMPLE variable whose address is not needed. */
418 is_gimple_non_addressable (tree t
)
420 if (TREE_CODE (t
) == SSA_NAME
)
421 t
= SSA_NAME_VAR (t
);
423 return (is_gimple_variable (t
)
424 && ! TREE_ADDRESSABLE (t
)
425 && ! needs_to_live_in_memory (t
));
428 /* Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
432 is_gimple_val (tree t
)
434 /* Make loads from volatiles and memory vars explicit. */
435 if (is_gimple_variable (t
)
436 && is_gimple_reg_type (TREE_TYPE (t
))
437 && !is_gimple_reg (t
))
440 /* FIXME make these decls. That can happen only when we expose the
441 entire landing-pad construct at the tree level. */
442 if (TREE_CODE (t
) == EXC_PTR_EXPR
|| TREE_CODE (t
) == FILTER_EXPR
)
445 return (is_gimple_variable (t
) || is_gimple_min_invariant (t
));
449 /* Return true if T is a GIMPLE minimal lvalue, of the form
451 min_lval: ID | '(' '*' ID ')'
453 This never actually appears in the original SIMPLE grammar, but is
454 repeated in several places. */
457 is_gimple_min_lval (tree t
)
459 return (is_gimple_id (t
)
460 || TREE_CODE (t
) == INDIRECT_REF
);
463 /* Return nonzero if T is a typecast operation of the form
467 is_gimple_cast (tree t
)
469 return (TREE_CODE (t
) == NOP_EXPR
470 || TREE_CODE (t
) == CONVERT_EXPR
471 || TREE_CODE (t
) == FIX_TRUNC_EXPR
472 || TREE_CODE (t
) == FIX_CEIL_EXPR
473 || TREE_CODE (t
) == FIX_FLOOR_EXPR
474 || TREE_CODE (t
) == FIX_ROUND_EXPR
);
478 /* If T makes a function call, return the corresponding CALL_EXPR operand.
479 Otherwise, return NULL_TREE. */
482 get_call_expr_in (tree t
)
484 if (TREE_CODE (t
) == CALL_EXPR
)
486 else if (TREE_CODE (t
) == MODIFY_EXPR
487 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
)
488 return TREE_OPERAND (t
, 1);
489 else if (TREE_CODE (t
) == RETURN_EXPR
490 && TREE_OPERAND (t
, 0)
491 && TREE_CODE (TREE_OPERAND (t
, 0)) == MODIFY_EXPR
492 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t
, 0), 1)) == CALL_EXPR
)
493 return TREE_OPERAND (TREE_OPERAND (t
, 0), 1);
499 /* Given an _EXPR TOP, reorganize all of the nested _EXPRs with the same
500 code so that they only appear as the second operand. This should only
501 be used for tree codes which are truly associative, such as
502 COMPOUND_EXPR and TRUTH_ANDIF_EXPR. Arithmetic is not associative
503 enough, due to the limited precision of arithmetic data types.
505 This transformation is conservative; the operand 0 of a matching tree
506 node will only change if it is also a matching node. */
509 right_assocify_expr (tree top
)
512 enum tree_code code
= TREE_CODE (*p
);
513 while (TREE_CODE (*p
) == code
)
516 tree lhs
= TREE_OPERAND (cur
, 0);
517 if (TREE_CODE (lhs
) == code
)
519 /* There's a left-recursion. If we have ((a, (b, c)), d), we
520 want to rearrange to (a, (b, (c, d))). */
523 /* Replace cur with the lhs; move (a, *) up. */
526 if (code
== COMPOUND_EXPR
)
528 /* We need to give (b, c) the type of c; previously lhs had
530 TREE_TYPE (lhs
) = TREE_TYPE (cur
);
531 if (TREE_SIDE_EFFECTS (cur
))
532 TREE_SIDE_EFFECTS (lhs
) = 1;
535 /* Walk through the op1 chain from there until we find something
536 with a different code. In this case, c. */
537 for (q
= &TREE_OPERAND (lhs
, 1); TREE_CODE (*q
) == code
;
538 q
= &TREE_OPERAND (*q
, 1))
539 TREE_TYPE (*q
) = TREE_TYPE (cur
);
541 /* Change (*, d) into (c, d). */
542 TREE_OPERAND (cur
, 0) = *q
;
544 /* And plug it in where c used to be. */
548 p
= &TREE_OPERAND (cur
, 1);
553 /* Normalize the statement TOP. If it is a COMPOUND_EXPR, reorganize it so
554 that we can traverse it without recursion. If it is null, replace it
558 rationalize_compound_expr (tree top
)
560 if (top
== NULL_TREE
)
561 top
= build_empty_stmt ();
562 else if (TREE_CODE (top
) == COMPOUND_EXPR
)
563 top
= right_assocify_expr (top
);
568 /* Given a memory reference expression, return the base address. Note that,
569 in contrast with get_base_var, this will not recurse inside INDIRECT_REF
570 expressions. Therefore, given the reference PTR->FIELD, this function
571 will return *PTR. Whereas get_base_var would've returned PTR. */
574 get_base_address (tree t
)
579 || TREE_CODE (t
) == STRING_CST
580 || TREE_CODE (t
) == CONSTRUCTOR
581 || TREE_CODE (t
) == INDIRECT_REF
)
584 switch (TREE_CODE (t
))
591 t
= TREE_OPERAND (t
, 0);
605 recalculate_side_effects (tree t
)
607 enum tree_code code
= TREE_CODE (t
);
608 int fro
= first_rtl_op (code
);
611 switch (TREE_CODE_CLASS (code
))
620 case PREDECREMENT_EXPR
:
621 case PREINCREMENT_EXPR
:
622 case POSTDECREMENT_EXPR
:
623 case POSTINCREMENT_EXPR
:
624 /* All of these have side-effects, no matter what their
633 case '<': /* a comparison expression */
634 case '1': /* a unary arithmetic expression */
635 case '2': /* a binary arithmetic expression */
636 case 'r': /* a reference */
637 TREE_SIDE_EFFECTS (t
) = TREE_THIS_VOLATILE (t
);
638 for (i
= 0; i
< fro
; ++i
)
640 tree op
= TREE_OPERAND (t
, i
);
641 if (op
&& TREE_SIDE_EFFECTS (op
))
642 TREE_SIDE_EFFECTS (t
) = 1;