1/* Functions to analyze and validate GIMPLE trees.
2   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Diego Novillo <dnovillo@redhat.com>
4   Rewritten by Jason Merrill <jason@redhat.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 2, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING.  If not, write to
20the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21Boston, MA 02110-1301, 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"
29#include "tree-gimple.h"
30#include "tree-flow.h"
31#include "output.h"
32#include "rtl.h"
33#include "expr.h"
34#include "bitmap.h"
35
36/* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
37
38/* Validation of GIMPLE expressions.  */
39
40/* Return true if T is a GIMPLE RHS for an assignment to a temporary.  */
41
42bool
43is_gimple_formal_tmp_rhs (tree t)
44{
45  enum tree_code code = TREE_CODE (t);
46
47  switch (TREE_CODE_CLASS (code))
48    {
49    case tcc_unary:
50    case tcc_binary:
51    case tcc_comparison:
52      return true;
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:
68    case INTEGER_CST:
69    case REAL_CST:
70    case STRING_CST:
71    case COMPLEX_CST:
72    case VECTOR_CST:
73    case OBJ_TYPE_REF:
74    case ASSERT_EXPR:
75      return true;
76
77    default:
78      break;
79    }
80
81  return is_gimple_lvalue (t) || is_gimple_val (t);
82}
83
84/* Returns true iff T is a valid RHS for an assignment to a renamed
85   user -- or front-end generated artificial -- variable.  */
86
87bool
88is_gimple_reg_rhs (tree t)
89{
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.  */
98
99  if (is_gimple_reg_type (TREE_TYPE (t))
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);
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
110bool
111is_gimple_mem_rhs (tree t)
112{
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)
119    return is_gimple_val (t);
120  else
121    return is_gimple_formal_tmp_rhs (t);
122}
123
124/* Returns the appropriate RHS predicate for this LHS.  */
125
126gimple_predicate
127rhs_predicate_for (tree lhs)
128{
129  if (is_gimple_formal_tmp_var (lhs))
130    return is_gimple_formal_tmp_rhs;
131  else if (is_gimple_reg (lhs))
132    return is_gimple_reg_rhs;
133  else
134    return is_gimple_mem_rhs;
135}
136
137/*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
138
139bool
140is_gimple_lvalue (tree t)
141{
142  return (is_gimple_addressable (t)
143	  || TREE_CODE (t) == WITH_SIZE_EXPR
144	  /* These are complex lvalues, but don't have addresses, so they
145	     go here.  */
146	  || TREE_CODE (t) == BIT_FIELD_REF);
147}
148
149/*  Return true if T is a GIMPLE condition.  */
150
151bool
152is_gimple_condexpr (tree t)
153{
154  return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
155}
156
157/*  Return true if T is something whose address can be taken.  */
158
159bool
160is_gimple_addressable (tree t)
161{
162  return (is_gimple_id (t) || handled_component_p (t)
163	  || INDIRECT_REF_P (t));
164}
165
166/* Return true if T is function invariant.  Or rather a restricted
167   form of function invariant.  */
168
169bool
170is_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:
182      return true;
183
184    default:
185      return false;
186    }
187}
188
189/* Return true if T looks like a valid GIMPLE statement.  */
190
191bool
192is_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.  */
204      return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
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:
219      /* These are always void.  */
220      return true;
221
222    case CALL_EXPR:
223    case MODIFY_EXPR:
224      /* These are valid regardless of their type.  */
225      return true;
226
227    default:
228      return false;
229    }
230}
231
232/* Return true if T is a variable.  */
233
234bool
235is_gimple_variable (tree t)
236{
237  return (TREE_CODE (t) == VAR_DECL
238	  || TREE_CODE (t) == PARM_DECL
239	  || TREE_CODE (t) == RESULT_DECL
240	  || TREE_CODE (t) == SSA_NAME);
241}
242
243/*  Return true if T is a GIMPLE identifier (something with an address).  */
244
245bool
246is_gimple_id (tree t)
247{
248  return (is_gimple_variable (t)
249	  || TREE_CODE (t) == FUNCTION_DECL
250	  || TREE_CODE (t) == LABEL_DECL
251	  || TREE_CODE (t) == CONST_DECL
252	  /* Allow string constants, since they are addressable.  */
253	  || TREE_CODE (t) == STRING_CST);
254}
255
256/* Return true if TYPE is a suitable type for a scalar register variable.  */
257
258bool
259is_gimple_reg_type (tree type)
260{
261  return !AGGREGATE_TYPE_P (type);
262}
263
264/* Return true if T is a non-aggregate register variable.  */
265
266bool
267is_gimple_reg (tree t)
268{
269  var_ann_t ann;
270
271  if (TREE_CODE (t) == SSA_NAME)
272    t = SSA_NAME_VAR (t);
273
274  if (!is_gimple_variable (t))
275    return false;
276
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  /* Complex values must have been put into ssa form.  That is, no
304     assignments to the individual components.  */
305  if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE)
306    return DECL_COMPLEX_GIMPLE_REG_P (t);
307
308  /* Some compiler temporaries are created to be used exclusively in
309     virtual operands (currently memory tags and sub-variables).
310     These variables should never be considered GIMPLE registers.  */
311  if (DECL_ARTIFICIAL (t) && (ann = var_ann (t)) != NULL)
312    return ann->mem_tag_kind == NOT_A_TAG;
313
314  return true;
315}
316
317
318/* Returns true if T is a GIMPLE formal temporary variable.  */
319
320bool
321is_gimple_formal_tmp_var (tree t)
322{
323  if (TREE_CODE (t) == SSA_NAME)
324    return true;
325
326  return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
327}
328
329/* Returns true if T is a GIMPLE formal temporary register variable.  */
330
331bool
332is_gimple_formal_tmp_reg (tree t)
333{
334  /* The intent of this is to get hold of a value that won't change.
335     An SSA_NAME qualifies no matter if its of a user variable or not.  */
336  if (TREE_CODE (t) == SSA_NAME)
337    return true;
338
339  /* We don't know the lifetime characteristics of user variables.  */
340  if (!is_gimple_formal_tmp_var (t))
341    return false;
342
343  /* Finally, it must be capable of being placed in a register.  */
344  return is_gimple_reg (t);
345}
346
347/* Return true if T is a GIMPLE variable whose address is not needed.  */
348
349bool
350is_gimple_non_addressable (tree t)
351{
352  if (TREE_CODE (t) == SSA_NAME)
353    t = SSA_NAME_VAR (t);
354
355  return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
356}
357
358/* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
359
360bool
361is_gimple_val (tree t)
362{
363  /* Make loads from volatiles and memory vars explicit.  */
364  if (is_gimple_variable (t)
365      && is_gimple_reg_type (TREE_TYPE (t))
366      && !is_gimple_reg (t))
367    return false;
368
369  /* FIXME make these decls.  That can happen only when we expose the
370     entire landing-pad construct at the tree level.  */
371  if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
372    return 1;
373
374  return (is_gimple_variable (t) || is_gimple_min_invariant (t));
375}
376
377/* Similarly, but accept hard registers as inputs to asm statements.  */
378
379bool
380is_gimple_asm_val (tree t)
381{
382  if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
383    return true;
384
385  return is_gimple_val (t);
386}
387
388/* Return true if T is a GIMPLE minimal lvalue.  */
389
390bool
391is_gimple_min_lval (tree t)
392{
393  return (is_gimple_id (t)
394	  || TREE_CODE (t) == INDIRECT_REF);
395}
396
397/* Return true if T is a typecast operation.  */
398
399bool
400is_gimple_cast (tree t)
401{
402  return (TREE_CODE (t) == NOP_EXPR
403	  || TREE_CODE (t) == CONVERT_EXPR
404          || TREE_CODE (t) == FIX_TRUNC_EXPR
405          || TREE_CODE (t) == FIX_CEIL_EXPR
406          || TREE_CODE (t) == FIX_FLOOR_EXPR
407          || TREE_CODE (t) == FIX_ROUND_EXPR);
408}
409
410/* Return true if T is a valid op0 of a CALL_EXPR.  */
411
412bool
413is_gimple_call_addr (tree t)
414{
415  return (TREE_CODE (t) == OBJ_TYPE_REF
416	  || is_gimple_val (t));
417}
418
419/* If T makes a function call, return the corresponding CALL_EXPR operand.
420   Otherwise, return NULL_TREE.  */
421
422tree
423get_call_expr_in (tree t)
424{
425  if (TREE_CODE (t) == MODIFY_EXPR)
426    t = TREE_OPERAND (t, 1);
427  if (TREE_CODE (t) == WITH_SIZE_EXPR)
428    t = TREE_OPERAND (t, 0);
429  if (TREE_CODE (t) == CALL_EXPR)
430    return t;
431  return NULL_TREE;
432}
433
434/* Given a memory reference expression T, return its base address.
435   The base address of a memory reference expression is the main
436   object being referenced.  For instance, the base address for
437   'array[i].fld[j]' is 'array'.  You can think of this as stripping
438   away the offset part from a memory address.
439
440   This function calls handled_component_p to strip away all the inner
441   parts of the memory reference until it reaches the base object.  */
442
443tree
444get_base_address (tree t)
445{
446  while (handled_component_p (t))
447    t = TREE_OPERAND (t, 0);
448
449  if (SSA_VAR_P (t)
450      || TREE_CODE (t) == STRING_CST
451      || TREE_CODE (t) == CONSTRUCTOR
452      || INDIRECT_REF_P (t))
453    return t;
454  else
455    return NULL_TREE;
456}
457
458void
459recalculate_side_effects (tree t)
460{
461  enum tree_code code = TREE_CODE (t);
462  int len = TREE_CODE_LENGTH (code);
463  int i;
464
465  switch (TREE_CODE_CLASS (code))
466    {
467    case tcc_expression:
468      switch (code)
469	{
470	case INIT_EXPR:
471	case MODIFY_EXPR:
472	case VA_ARG_EXPR:
473	case PREDECREMENT_EXPR:
474	case PREINCREMENT_EXPR:
475	case POSTDECREMENT_EXPR:
476	case POSTINCREMENT_EXPR:
477	  /* All of these have side-effects, no matter what their
478	     operands are.  */
479	  return;
480
481	default:
482	  break;
483	}
484      /* Fall through.  */
485
486    case tcc_comparison:  /* a comparison expression */
487    case tcc_unary:       /* a unary arithmetic expression */
488    case tcc_binary:      /* a binary arithmetic expression */
489    case tcc_reference:   /* a reference */
490      TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
491      for (i = 0; i < len; ++i)
492	{
493	  tree op = TREE_OPERAND (t, i);
494	  if (op && TREE_SIDE_EFFECTS (op))
495	    TREE_SIDE_EFFECTS (t) = 1;
496	}
497      break;
498
499    default:
500      /* Can never be used with non-expressions.  */
501      gcc_unreachable ();
502   }
503}
504