1 /* Functions to analyze and validate GIMPLE trees.
2 Copyright (C) 2002, 2003, 2004 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
114 op0 -> ID | '&' ID | OBJ_TYPE_REF
117 addr-expr-arg : compref | ID
118 lhs: addr-expr-arg | '*' ID | bitfieldref
119 min-lval: ID | '*' ID
143 inner_compref : compref | min_lval
151 condition : val | val relop val
154 rhs : varname | CONST
163 (cast here stands for all valid C typecasts)
193 static inline bool is_gimple_id (tree
);
195 /* Validation of GIMPLE expressions. */
197 /* Return nonzero if T is a GIMPLE RHS:
199 rhs : varname | CONST
201 | '&' varname_or_temp
206 | <CONSTRUCTOR <gimple_val ...>>
208 The last option is only valid GIMPLE for vector and complex types;
209 aggregate types should have their constructors decomposed. */
212 is_gimple_rhs (tree t
)
214 enum tree_code code
= TREE_CODE (t
);
216 switch (TREE_CODE_CLASS (code
))
237 /* FIXME lower VA_ARG_EXPR. */
251 if (is_gimple_lvalue (t
) || is_gimple_val (t
))
257 /* Returns nonzero if T is a valid CONSTRUCTOR component in GIMPLE, either
258 a val or another CONSTRUCTOR. */
261 is_gimple_constructor_elt (tree t
)
263 return (is_gimple_val (t
)
264 || TREE_CODE (t
) == CONSTRUCTOR
);
267 /* Return nonzero if T is a valid LHS for a GIMPLE assignment expression. */
270 is_gimple_lvalue (tree t
)
272 return (is_gimple_addr_expr_arg (t
)
273 || TREE_CODE (t
) == INDIRECT_REF
274 /* These are complex lvalues, but don't have addresses, so they
276 || TREE_CODE (t
) == BIT_FIELD_REF
);
280 /* Return nonzero if T is a GIMPLE condition:
287 is_gimple_condexpr (tree t
)
289 return (is_gimple_val (t
)
290 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<');
294 /* Return nonzero if T is a valid operand for '&':
302 is_gimple_addr_expr_arg (tree t
)
304 return (is_gimple_id (t
)
305 || TREE_CODE (t
) == ARRAY_REF
306 || TREE_CODE (t
) == ARRAY_RANGE_REF
307 || TREE_CODE (t
) == COMPONENT_REF
308 || TREE_CODE (t
) == REALPART_EXPR
309 || TREE_CODE (t
) == IMAGPART_EXPR
310 || TREE_CODE (t
) == INDIRECT_REF
);
313 /* Return nonzero if T is function invariant. Or rather a restricted
314 form of function invariant. */
317 is_gimple_min_invariant (tree t
)
319 switch (TREE_CODE (t
))
322 return TREE_INVARIANT (t
);
329 return !TREE_OVERFLOW (t
);
336 /* Return nonzero if T looks like a valid GIMPLE statement. */
339 is_gimple_stmt (tree t
)
341 enum tree_code code
= TREE_CODE (t
);
343 if (IS_EMPTY_STMT (t
))
350 /* These are only valid if they're void. */
351 return TREE_TYPE (t
) == NULL
|| VOID_TYPE_P (TREE_TYPE (t
));
357 case CASE_LABEL_EXPR
:
359 case TRY_FINALLY_EXPR
:
366 /* These are always void. */
370 /* FIXME this should be lowered. */
374 /* FIXME should we work harder to make COMPOUND_EXPRs void? */
377 /* These are valid regardless of their type. */
385 /* Return nonzero if T is a variable. */
388 is_gimple_variable (tree t
)
390 return (TREE_CODE (t
) == VAR_DECL
391 || TREE_CODE (t
) == PARM_DECL
392 || TREE_CODE (t
) == RESULT_DECL
393 || TREE_CODE (t
) == SSA_NAME
);
396 /* Return nonzero if T is a GIMPLE identifier (something with an address). */
399 is_gimple_id (tree t
)
401 return (is_gimple_variable (t
)
402 || TREE_CODE (t
) == FUNCTION_DECL
403 || TREE_CODE (t
) == LABEL_DECL
404 /* Allow string constants, since they are addressable. */
405 || TREE_CODE (t
) == STRING_CST
);
408 /* Return nonzero if TYPE is a suitable type for a scalar register
412 is_gimple_reg_type (tree type
)
414 return (!AGGREGATE_TYPE_P (type
)
415 && TREE_CODE (type
) != COMPLEX_TYPE
);
419 /* Return nonzero if T is a scalar register variable. */
422 is_gimple_reg (tree t
)
424 if (TREE_CODE (t
) == SSA_NAME
)
425 t
= SSA_NAME_VAR (t
);
427 return (is_gimple_variable (t
)
428 && is_gimple_reg_type (TREE_TYPE (t
))
429 /* A volatile decl is not acceptable because we can't reuse it as
430 needed. We need to copy it into a temp first. */
431 && ! TREE_THIS_VOLATILE (t
)
432 && ! TREE_ADDRESSABLE (t
)
433 && ! needs_to_live_in_memory (t
));
436 /* Return nonzero if T is a GIMPLE variable whose address is not needed. */
439 is_gimple_non_addressable (tree t
)
441 if (TREE_CODE (t
) == SSA_NAME
)
442 t
= SSA_NAME_VAR (t
);
444 return (is_gimple_variable (t
)
445 && ! TREE_ADDRESSABLE (t
)
446 && ! needs_to_live_in_memory (t
));
449 /* Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
453 is_gimple_val (tree t
)
455 /* Make loads from volatiles and memory vars explicit. */
456 if (is_gimple_variable (t
)
457 && is_gimple_reg_type (TREE_TYPE (t
))
458 && !is_gimple_reg (t
))
461 /* FIXME make these decls. That can happen only when we expose the
462 entire landing-pad construct at the tree level. */
463 if (TREE_CODE (t
) == EXC_PTR_EXPR
|| TREE_CODE (t
) == FILTER_EXPR
)
466 return (is_gimple_variable (t
) || is_gimple_min_invariant (t
));
470 /* Return true if T is a GIMPLE minimal lvalue, of the form
472 min_lval: ID | '(' '*' ID ')'
474 This never actually appears in the original SIMPLE grammar, but is
475 repeated in several places. */
478 is_gimple_min_lval (tree t
)
480 return (is_gimple_id (t
)
481 || TREE_CODE (t
) == INDIRECT_REF
);
484 /* Return nonzero if T is a typecast operation of the form
488 is_gimple_cast (tree t
)
490 return (TREE_CODE (t
) == NOP_EXPR
491 || TREE_CODE (t
) == CONVERT_EXPR
492 || TREE_CODE (t
) == FIX_TRUNC_EXPR
493 || TREE_CODE (t
) == FIX_CEIL_EXPR
494 || TREE_CODE (t
) == FIX_FLOOR_EXPR
495 || TREE_CODE (t
) == FIX_ROUND_EXPR
);
498 /* Return true if T is a valid op0 of a CALL_EXPR. */
501 is_gimple_call_addr (tree t
)
503 return (TREE_CODE (t
) == OBJ_TYPE_REF
504 || is_gimple_val (t
));
507 /* If T makes a function call, return the corresponding CALL_EXPR operand.
508 Otherwise, return NULL_TREE. */
511 get_call_expr_in (tree t
)
513 if (TREE_CODE (t
) == CALL_EXPR
)
515 else if (TREE_CODE (t
) == MODIFY_EXPR
516 && TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
)
517 return TREE_OPERAND (t
, 1);
518 else if (TREE_CODE (t
) == RETURN_EXPR
519 && TREE_OPERAND (t
, 0)
520 && TREE_CODE (TREE_OPERAND (t
, 0)) == MODIFY_EXPR
521 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t
, 0), 1)) == CALL_EXPR
)
522 return TREE_OPERAND (TREE_OPERAND (t
, 0), 1);
528 /* Given an _EXPR TOP, reorganize all of the nested _EXPRs with the same
529 code so that they only appear as the second operand. This should only
530 be used for tree codes which are truly associative, such as
531 COMPOUND_EXPR and TRUTH_ANDIF_EXPR. Arithmetic is not associative
532 enough, due to the limited precision of arithmetic data types.
534 This transformation is conservative; the operand 0 of a matching tree
535 node will only change if it is also a matching node. */
538 right_assocify_expr (tree top
)
541 enum tree_code code
= TREE_CODE (*p
);
542 while (TREE_CODE (*p
) == code
)
545 tree lhs
= TREE_OPERAND (cur
, 0);
546 if (TREE_CODE (lhs
) == code
)
548 /* There's a left-recursion. If we have ((a, (b, c)), d), we
549 want to rearrange to (a, (b, (c, d))). */
552 /* Replace cur with the lhs; move (a, *) up. */
555 if (code
== COMPOUND_EXPR
)
557 /* We need to give (b, c) the type of c; previously lhs had
559 TREE_TYPE (lhs
) = TREE_TYPE (cur
);
560 if (TREE_SIDE_EFFECTS (cur
))
561 TREE_SIDE_EFFECTS (lhs
) = 1;
564 /* Walk through the op1 chain from there until we find something
565 with a different code. In this case, c. */
566 for (q
= &TREE_OPERAND (lhs
, 1); TREE_CODE (*q
) == code
;
567 q
= &TREE_OPERAND (*q
, 1))
568 TREE_TYPE (*q
) = TREE_TYPE (cur
);
570 /* Change (*, d) into (c, d). */
571 TREE_OPERAND (cur
, 0) = *q
;
573 /* And plug it in where c used to be. */
577 p
= &TREE_OPERAND (cur
, 1);
582 /* Normalize the statement TOP. If it is a COMPOUND_EXPR, reorganize it so
583 that we can traverse it without recursion. If it is null, replace it
587 rationalize_compound_expr (tree top
)
589 if (top
== NULL_TREE
)
590 top
= build_empty_stmt ();
591 else if (TREE_CODE (top
) == COMPOUND_EXPR
)
592 top
= right_assocify_expr (top
);
597 /* Given a memory reference expression, return the base address. Note that,
598 in contrast with get_base_var, this will not recurse inside INDIRECT_REF
599 expressions. Therefore, given the reference PTR->FIELD, this function
600 will return *PTR. Whereas get_base_var would've returned PTR. */
603 get_base_address (tree t
)
605 while (TREE_CODE (t
) == REALPART_EXPR
|| TREE_CODE (t
) == IMAGPART_EXPR
606 || handled_component_p (t
))
607 t
= TREE_OPERAND (t
, 0);
610 || TREE_CODE (t
) == STRING_CST
611 || TREE_CODE (t
) == CONSTRUCTOR
612 || TREE_CODE (t
) == INDIRECT_REF
)
619 recalculate_side_effects (tree t
)
621 enum tree_code code
= TREE_CODE (t
);
622 int fro
= first_rtl_op (code
);
625 switch (TREE_CODE_CLASS (code
))
634 case PREDECREMENT_EXPR
:
635 case PREINCREMENT_EXPR
:
636 case POSTDECREMENT_EXPR
:
637 case POSTINCREMENT_EXPR
:
638 /* All of these have side-effects, no matter what their
647 case '<': /* a comparison expression */
648 case '1': /* a unary arithmetic expression */
649 case '2': /* a binary arithmetic expression */
650 case 'r': /* a reference */
651 TREE_SIDE_EFFECTS (t
) = TREE_THIS_VOLATILE (t
);
652 for (i
= 0; i
< fro
; ++i
)
654 tree op
= TREE_OPERAND (t
, i
);
655 if (op
&& TREE_SIDE_EFFECTS (op
))
656 TREE_SIDE_EFFECTS (t
) = 1;