tree-inline.c revision 132718
1/* Control and data flow functions for trees.
2   Copyright 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3   Contributed by Alexandre Oliva <aoliva@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to
19the Free Software Foundation, 59 Temple Place - Suite 330,
20Boston, MA 02111-1307, USA.  */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "toplev.h"
27#include "tree.h"
28#include "tree-inline.h"
29#include "rtl.h"
30#include "expr.h"
31#include "flags.h"
32#include "params.h"
33#include "input.h"
34#include "insn-config.h"
35#include "integrate.h"
36#include "varray.h"
37#include "hashtab.h"
38#include "splay-tree.h"
39#include "langhooks.h"
40#include "cgraph.h"
41#include "intl.h"
42#include "diagnostic.h"
43
44/* This should be eventually be generalized to other languages, but
45   this would require a shared function-as-trees infrastructure.  */
46#ifndef INLINER_FOR_JAVA
47#include "c-common.h"
48#else /* INLINER_FOR_JAVA */
49#include "parse.h"
50#include "java-tree.h"
51#endif /* INLINER_FOR_JAVA */
52
53/* 0 if we should not perform inlining.
54   1 if we should expand functions calls inline at the tree level.
55   2 if we should consider *all* functions to be inline
56   candidates.  */
57
58int flag_inline_trees = 0;
59
60/* To Do:
61
62   o In order to make inlining-on-trees work, we pessimized
63     function-local static constants.  In particular, they are now
64     always output, even when not addressed.  Fix this by treating
65     function-local static constants just like global static
66     constants; the back-end already knows not to output them if they
67     are not needed.
68
69   o Provide heuristics to clamp inlining of recursive template
70     calls?  */
71
72/* Data required for function inlining.  */
73
74typedef struct inline_data
75{
76  /* A stack of the functions we are inlining.  For example, if we are
77     compiling `f', which calls `g', which calls `h', and we are
78     inlining the body of `h', the stack will contain, `h', followed
79     by `g', followed by `f'.  The first few elements of the stack may
80     contain other functions that we know we should not recurse into,
81     even though they are not directly being inlined.  */
82  varray_type fns;
83  /* The index of the first element of FNS that really represents an
84     inlined function.  */
85  unsigned first_inlined_fn;
86  /* The label to jump to when a return statement is encountered.  If
87     this value is NULL, then return statements will simply be
88     remapped as return statements, rather than as jumps.  */
89  tree ret_label;
90  /* The map from local declarations in the inlined function to
91     equivalents in the function into which it is being inlined.  */
92  splay_tree decl_map;
93  /* Nonzero if we are currently within the cleanup for a
94     TARGET_EXPR.  */
95  int in_target_cleanup_p;
96  /* A list of the functions current function has inlined.  */
97  varray_type inlined_fns;
98  /* We use the same mechanism to build clones that we do to perform
99     inlining.  However, there are a few places where we need to
100     distinguish between those two situations.  This flag is true if
101     we are cloning, rather than inlining.  */
102  bool cloning_p;
103  /* Hash table used to prevent walk_tree from visiting the same node
104     umpteen million times.  */
105  htab_t tree_pruner;
106  /* Decl of function we are inlining into.  */
107  tree decl;
108  tree current_decl;
109} inline_data;
110
111/* Prototypes.  */
112
113static tree declare_return_variable (inline_data *, tree, tree *);
114static tree copy_body_r (tree *, int *, void *);
115static tree copy_body (inline_data *);
116static tree expand_call_inline (tree *, int *, void *);
117static void expand_calls_inline (tree *, inline_data *);
118static bool inlinable_function_p (tree);
119static tree remap_decl (tree, inline_data *);
120static tree remap_type (tree, inline_data *);
121#ifndef INLINER_FOR_JAVA
122static tree initialize_inlined_parameters (inline_data *, tree, tree);
123static void remap_block (tree, tree, inline_data *);
124static void copy_scope_stmt (tree *, int *, inline_data *);
125#else /* INLINER_FOR_JAVA */
126static tree initialize_inlined_parameters (inline_data *, tree, tree, tree);
127static void remap_block (tree *, tree, inline_data *);
128static tree add_stmt_to_compound (tree, tree, tree);
129#endif /* INLINER_FOR_JAVA */
130
131/* Remap DECL during the copying of the BLOCK tree for the function.  */
132
133static tree
134remap_decl (tree decl, inline_data *id)
135{
136  splay_tree_node n;
137  tree fn;
138
139  /* We only remap local variables in the current function.  */
140  fn = VARRAY_TOP_TREE (id->fns);
141  if (! (*lang_hooks.tree_inlining.auto_var_in_fn_p) (decl, fn))
142    return NULL_TREE;
143
144  /* See if we have remapped this declaration.  */
145  n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
146
147  /* If we didn't already have an equivalent for this declaration,
148     create one now.  */
149  if (!n)
150    {
151      tree t;
152
153      /* Make a copy of the variable or label.  */
154      t = copy_decl_for_inlining (decl, fn, VARRAY_TREE (id->fns, 0));
155
156      /* Remap types, if necessary.  */
157      TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
158      if (TREE_CODE (t) == TYPE_DECL)
159        DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
160      else if (TREE_CODE (t) == PARM_DECL)
161        DECL_ARG_TYPE_AS_WRITTEN (t)
162	  = remap_type (DECL_ARG_TYPE_AS_WRITTEN (t), id);
163
164      /* Remap sizes as necessary.  */
165      walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
166      walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
167
168#ifndef INLINER_FOR_JAVA
169      if (! DECL_NAME (t) && TREE_TYPE (t)
170	  && (*lang_hooks.tree_inlining.anon_aggr_type_p) (TREE_TYPE (t)))
171	{
172	  /* For a VAR_DECL of anonymous type, we must also copy the
173	     member VAR_DECLS here and rechain the DECL_ANON_UNION_ELEMS.  */
174	  tree members = NULL;
175	  tree src;
176
177	  for (src = DECL_ANON_UNION_ELEMS (t); src;
178	       src = TREE_CHAIN (src))
179	    {
180	      tree member = remap_decl (TREE_VALUE (src), id);
181
182	      if (TREE_PURPOSE (src))
183		abort ();
184	      members = tree_cons (NULL, member, members);
185	    }
186	  DECL_ANON_UNION_ELEMS (t) = nreverse (members);
187	}
188#endif /* not INLINER_FOR_JAVA */
189
190      /* Remember it, so that if we encounter this local entity
191	 again we can reuse this copy.  */
192      n = splay_tree_insert (id->decl_map,
193			     (splay_tree_key) decl,
194			     (splay_tree_value) t);
195    }
196
197  return (tree) n->value;
198}
199
200static tree
201remap_type (tree type, inline_data *id)
202{
203  splay_tree_node node;
204  tree new, t;
205
206  if (type == NULL)
207    return type;
208
209  /* See if we have remapped this type.  */
210  node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
211  if (node)
212    return (tree) node->value;
213
214  /* The type only needs remapping if it's variably modified.  */
215  if (! variably_modified_type_p (type))
216    {
217      splay_tree_insert (id->decl_map, (splay_tree_key) type,
218			 (splay_tree_value) type);
219      return type;
220    }
221
222  /* We do need a copy.  build and register it now.  */
223  new = copy_node (type);
224  splay_tree_insert (id->decl_map, (splay_tree_key) type,
225		     (splay_tree_value) new);
226
227  /* This is a new type, not a copy of an old type.  Need to reassociate
228     variants.  We can handle everything except the main variant lazily.  */
229  t = TYPE_MAIN_VARIANT (type);
230  if (type != t)
231    {
232      t = remap_type (t, id);
233      TYPE_MAIN_VARIANT (new) = t;
234      TYPE_NEXT_VARIANT (new) = TYPE_MAIN_VARIANT (t);
235      TYPE_NEXT_VARIANT (t) = new;
236    }
237  else
238    {
239      TYPE_MAIN_VARIANT (new) = new;
240      TYPE_NEXT_VARIANT (new) = NULL;
241    }
242
243  /* Lazily create pointer and reference types.  */
244  TYPE_POINTER_TO (new) = NULL;
245  TYPE_REFERENCE_TO (new) = NULL;
246
247  switch (TREE_CODE (new))
248    {
249    case INTEGER_TYPE:
250    case REAL_TYPE:
251    case ENUMERAL_TYPE:
252    case BOOLEAN_TYPE:
253    case CHAR_TYPE:
254      t = TYPE_MIN_VALUE (new);
255      if (t && TREE_CODE (t) != INTEGER_CST)
256        walk_tree (&TYPE_MIN_VALUE (new), copy_body_r, id, NULL);
257      t = TYPE_MAX_VALUE (new);
258      if (t && TREE_CODE (t) != INTEGER_CST)
259        walk_tree (&TYPE_MAX_VALUE (new), copy_body_r, id, NULL);
260      return new;
261
262    case POINTER_TYPE:
263      TREE_TYPE (new) = t = remap_type (TREE_TYPE (new), id);
264      if (TYPE_MODE (new) == ptr_mode)
265        TYPE_POINTER_TO (t) = new;
266      return new;
267
268    case REFERENCE_TYPE:
269      TREE_TYPE (new) = t = remap_type (TREE_TYPE (new), id);
270      if (TYPE_MODE (new) == ptr_mode)
271        TYPE_REFERENCE_TO (t) = new;
272      return new;
273
274    case METHOD_TYPE:
275    case FUNCTION_TYPE:
276      TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
277      walk_tree (&TYPE_ARG_TYPES (new), copy_body_r, id, NULL);
278      return new;
279
280    case ARRAY_TYPE:
281      TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
282      TYPE_DOMAIN (new) = remap_type (TYPE_DOMAIN (new), id);
283      break;
284
285    case RECORD_TYPE:
286    case UNION_TYPE:
287    case QUAL_UNION_TYPE:
288      walk_tree (&TYPE_FIELDS (new), copy_body_r, id, NULL);
289      break;
290
291    case FILE_TYPE:
292    case SET_TYPE:
293    case OFFSET_TYPE:
294    default:
295      /* Shouldn't have been thought variable sized.  */
296      abort ();
297    }
298
299  walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
300  walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
301
302  return new;
303}
304
305#ifndef INLINER_FOR_JAVA
306/* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain
307   remapped versions of the variables therein.  And hook the new block
308   into the block-tree.  If non-NULL, the DECLS are declarations to
309   add to use instead of the BLOCK_VARS in the old block.  */
310#else /* INLINER_FOR_JAVA */
311/* Copy the BLOCK to contain remapped versions of the variables
312   therein.  And hook the new block into the block-tree.  */
313#endif /* INLINER_FOR_JAVA */
314
315static void
316#ifndef INLINER_FOR_JAVA
317remap_block (tree scope_stmt, tree decls, inline_data *id)
318#else /* INLINER_FOR_JAVA */
319remap_block (tree *block, tree decls, inline_data *id)
320#endif /* INLINER_FOR_JAVA */
321{
322#ifndef INLINER_FOR_JAVA
323  /* We cannot do this in the cleanup for a TARGET_EXPR since we do
324     not know whether or not expand_expr will actually write out the
325     code we put there.  If it does not, then we'll have more BLOCKs
326     than block-notes, and things will go awry.  At some point, we
327     should make the back-end handle BLOCK notes in a tidier way,
328     without requiring a strict correspondence to the block-tree; then
329     this check can go.  */
330  if (id->in_target_cleanup_p)
331    {
332      SCOPE_STMT_BLOCK (scope_stmt) = NULL_TREE;
333      return;
334    }
335
336  /* If this is the beginning of a scope, remap the associated BLOCK.  */
337  if (SCOPE_BEGIN_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
338    {
339      tree old_block;
340      tree new_block;
341      tree old_var;
342      tree fn;
343
344      /* Make the new block.  */
345      old_block = SCOPE_STMT_BLOCK (scope_stmt);
346      new_block = make_node (BLOCK);
347      TREE_USED (new_block) = TREE_USED (old_block);
348      BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
349      SCOPE_STMT_BLOCK (scope_stmt) = new_block;
350
351      /* Remap its variables.  */
352      for (old_var = decls ? decls : BLOCK_VARS (old_block);
353	   old_var;
354	   old_var = TREE_CHAIN (old_var))
355	{
356	  tree new_var;
357
358	  /* Remap the variable.  */
359	  new_var = remap_decl (old_var, id);
360	  /* If we didn't remap this variable, so we can't mess with
361	     its TREE_CHAIN.  If we remapped this variable to
362	     something other than a declaration (say, if we mapped it
363	     to a constant), then we must similarly omit any mention
364	     of it here.  */
365	  if (!new_var || !DECL_P (new_var))
366	    ;
367	  else
368	    {
369	      TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
370	      BLOCK_VARS (new_block) = new_var;
371	    }
372	}
373      /* We put the BLOCK_VARS in reverse order; fix that now.  */
374      BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
375      fn = VARRAY_TREE (id->fns, 0);
376      if (id->cloning_p)
377	/* We're building a clone; DECL_INITIAL is still
378	   error_mark_node, and current_binding_level is the parm
379	   binding level.  */
380	(*lang_hooks.decls.insert_block) (new_block);
381      else
382	{
383	  /* Attach this new block after the DECL_INITIAL block for the
384	     function into which this block is being inlined.  In
385	     rest_of_compilation we will straighten out the BLOCK tree.  */
386	  tree *first_block;
387	  if (DECL_INITIAL (fn))
388	    first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
389	  else
390	    first_block = &DECL_INITIAL (fn);
391	  BLOCK_CHAIN (new_block) = *first_block;
392	  *first_block = new_block;
393	}
394      /* Remember the remapped block.  */
395      splay_tree_insert (id->decl_map,
396			 (splay_tree_key) old_block,
397			 (splay_tree_value) new_block);
398    }
399  /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the
400     remapped block.  */
401  else if (SCOPE_END_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
402    {
403      splay_tree_node n;
404
405      /* Find this block in the table of remapped things.  */
406      n = splay_tree_lookup (id->decl_map,
407			     (splay_tree_key) SCOPE_STMT_BLOCK (scope_stmt));
408      if (! n)
409	abort ();
410      SCOPE_STMT_BLOCK (scope_stmt) = (tree) n->value;
411    }
412#else /* INLINER_FOR_JAVA */
413  tree old_block;
414  tree new_block;
415  tree old_var;
416  tree fn;
417
418  /* Make the new block.  */
419  old_block = *block;
420  new_block = make_node (BLOCK);
421  TREE_USED (new_block) = TREE_USED (old_block);
422  BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
423  BLOCK_SUBBLOCKS (new_block) = BLOCK_SUBBLOCKS (old_block);
424  TREE_SIDE_EFFECTS (new_block) = TREE_SIDE_EFFECTS (old_block);
425  TREE_TYPE (new_block) = TREE_TYPE (old_block);
426  *block = new_block;
427
428  /* Remap its variables.  */
429  for (old_var = decls ? decls : BLOCK_VARS (old_block);
430       old_var;
431       old_var = TREE_CHAIN (old_var))
432    {
433      tree new_var;
434
435      /* All local class initialization flags go in the outermost
436	 scope.  */
437      if (LOCAL_CLASS_INITIALIZATION_FLAG_P (old_var))
438	{
439	  /* We may already have one.  */
440	  if (! splay_tree_lookup (id->decl_map, (splay_tree_key) old_var))
441	    {
442	      tree outermost_block;
443	      new_var = remap_decl (old_var, id);
444	      DECL_ABSTRACT_ORIGIN (new_var) = NULL;
445	      outermost_block = DECL_SAVED_TREE (current_function_decl);
446	      TREE_CHAIN (new_var) = BLOCK_VARS (outermost_block);
447	      BLOCK_VARS (outermost_block) = new_var;
448	    }
449	  continue;
450	}
451
452      /* Remap the variable.  */
453      new_var = remap_decl (old_var, id);
454      /* If we didn't remap this variable, so we can't mess with
455	 its TREE_CHAIN.  If we remapped this variable to
456	 something other than a declaration (say, if we mapped it
457	 to a constant), then we must similarly omit any mention
458	 of it here.  */
459      if (!new_var || !DECL_P (new_var))
460	;
461      else
462	{
463	  TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
464	  BLOCK_VARS (new_block) = new_var;
465	}
466    }
467  /* We put the BLOCK_VARS in reverse order; fix that now.  */
468  BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
469  fn = VARRAY_TREE (id->fns, 0);
470  /* Remember the remapped block.  */
471  splay_tree_insert (id->decl_map,
472		     (splay_tree_key) old_block,
473		     (splay_tree_value) new_block);
474#endif /* INLINER_FOR_JAVA */
475}
476
477#ifndef INLINER_FOR_JAVA
478/* Copy the SCOPE_STMT pointed to by TP.  */
479
480static void
481copy_scope_stmt (tree *tp, int *walk_subtrees, inline_data *id)
482{
483  tree block;
484
485  /* Remember whether or not this statement was nullified.  When
486     making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and
487     doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to
488     deal with copying BLOCKs if they do not wish to do so.  */
489  block = SCOPE_STMT_BLOCK (*tp);
490  /* Copy (and replace) the statement.  */
491  copy_tree_r (tp, walk_subtrees, NULL);
492  /* Restore the SCOPE_STMT_BLOCK.  */
493  SCOPE_STMT_BLOCK (*tp) = block;
494
495  /* Remap the associated block.  */
496  remap_block (*tp, NULL_TREE, id);
497}
498#endif /* not INLINER_FOR_JAVA */
499
500/* Called from copy_body via walk_tree.  DATA is really an
501   `inline_data *'.  */
502static tree
503copy_body_r (tree *tp, int *walk_subtrees, void *data)
504{
505  inline_data* id;
506  tree fn;
507
508  /* Set up.  */
509  id = (inline_data *) data;
510  fn = VARRAY_TOP_TREE (id->fns);
511
512#if 0
513  /* All automatic variables should have a DECL_CONTEXT indicating
514     what function they come from.  */
515  if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
516      && DECL_NAMESPACE_SCOPE_P (*tp))
517    if (! DECL_EXTERNAL (*tp) && ! TREE_STATIC (*tp))
518      abort ();
519#endif
520
521#ifdef INLINER_FOR_JAVA
522  if (TREE_CODE (*tp) == BLOCK)
523    remap_block (tp, NULL_TREE, id);
524#endif
525
526  /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
527     GOTO_STMT with the RET_LABEL as its target.  */
528#ifndef INLINER_FOR_JAVA
529  if (TREE_CODE (*tp) == RETURN_STMT && id->ret_label)
530#else /* INLINER_FOR_JAVA */
531  if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
532#endif /* INLINER_FOR_JAVA */
533    {
534      tree return_stmt = *tp;
535      tree goto_stmt;
536
537      /* Build the GOTO_STMT.  */
538#ifndef INLINER_FOR_JAVA
539      goto_stmt = build_stmt (GOTO_STMT, id->ret_label);
540      TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt);
541      GOTO_FAKE_P (goto_stmt) = 1;
542#else /* INLINER_FOR_JAVA */
543      tree assignment = TREE_OPERAND (return_stmt, 0);
544      goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
545      TREE_SIDE_EFFECTS (goto_stmt) = 1;
546#endif /* INLINER_FOR_JAVA */
547
548      /* If we're returning something, just turn that into an
549	 assignment into the equivalent of the original
550	 RESULT_DECL.  */
551#ifndef INLINER_FOR_JAVA
552      if (RETURN_STMT_EXPR (return_stmt))
553	{
554	  *tp = build_stmt (EXPR_STMT,
555			    RETURN_STMT_EXPR (return_stmt));
556	  STMT_IS_FULL_EXPR_P (*tp) = 1;
557	  /* And then jump to the end of the function.  */
558	  TREE_CHAIN (*tp) = goto_stmt;
559	}
560#else /* INLINER_FOR_JAVA */
561      if (assignment)
562	{
563	  copy_body_r (&assignment, walk_subtrees, data);
564	  *tp = build (COMPOUND_EXPR, void_type_node, assignment, goto_stmt);
565	  TREE_SIDE_EFFECTS (*tp) = 1;
566	}
567#endif /* INLINER_FOR_JAVA */
568      /* If we're not returning anything just do the jump.  */
569      else
570	*tp = goto_stmt;
571    }
572  /* Local variables and labels need to be replaced by equivalent
573     variables.  We don't want to copy static variables; there's only
574     one of those, no matter how many times we inline the containing
575     function.
576     We do not also want to copy the label which we put into
577     GOTO_STMT which replaced RETURN_STMT.  */
578  else if (*tp != id->ret_label
579	   && (*lang_hooks.tree_inlining.auto_var_in_fn_p) (*tp, fn))
580    {
581      tree new_decl;
582
583      /* Remap the declaration.  */
584      new_decl = remap_decl (*tp, id);
585      if (! new_decl)
586	abort ();
587      /* Replace this variable with the copy.  */
588      STRIP_TYPE_NOPS (new_decl);
589      *tp = new_decl;
590    }
591#if 0
592  else if (nonstatic_local_decl_p (*tp)
593	   && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
594    abort ();
595#endif
596  else if (TREE_CODE (*tp) == SAVE_EXPR)
597    remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0),
598		     walk_subtrees);
599  else if (TREE_CODE (*tp) == UNSAVE_EXPR)
600    /* UNSAVE_EXPRs should not be generated until expansion time.  */
601    abort ();
602#ifndef INLINER_FOR_JAVA
603  /* For a SCOPE_STMT, we must copy the associated block so that we
604     can write out debugging information for the inlined variables.  */
605  else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p)
606    copy_scope_stmt (tp, walk_subtrees, id);
607#else /* INLINER_FOR_JAVA */
608  else if (TREE_CODE (*tp) == LABELED_BLOCK_EXPR)
609    {
610      /* We need a new copy of this labeled block; the EXIT_BLOCK_EXPR
611         will refer to it, so save a copy ready for remapping.  We
612         save it in the decl_map, although it isn't a decl.  */
613      tree new_block = copy_node (*tp);
614      splay_tree_insert (id->decl_map,
615			 (splay_tree_key) *tp,
616			 (splay_tree_value) new_block);
617      *tp = new_block;
618    }
619  else if (TREE_CODE (*tp) == EXIT_BLOCK_EXPR)
620    {
621      splay_tree_node n
622	= splay_tree_lookup (id->decl_map,
623			     (splay_tree_key) TREE_OPERAND (*tp, 0));
624      /* We _must_ have seen the enclosing LABELED_BLOCK_EXPR.  */
625      if (! n)
626	abort ();
627      *tp = copy_node (*tp);
628      TREE_OPERAND (*tp, 0) = (tree) n->value;
629    }
630#endif /* INLINER_FOR_JAVA */
631  /* Types may need remapping as well.  */
632  else if (TYPE_P (*tp))
633    *tp = remap_type (*tp, id);
634
635  /* Otherwise, just copy the node.  Note that copy_tree_r already
636     knows not to copy VAR_DECLs, etc., so this is safe.  */
637  else
638    {
639      if (TREE_CODE (*tp) == MODIFY_EXPR
640	  && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
641	  && ((*lang_hooks.tree_inlining.auto_var_in_fn_p)
642	      (TREE_OPERAND (*tp, 0), fn)))
643	{
644	  /* Some assignments VAR = VAR; don't generate any rtl code
645	     and thus don't count as variable modification.  Avoid
646	     keeping bogosities like 0 = 0.  */
647	  tree decl = TREE_OPERAND (*tp, 0), value;
648	  splay_tree_node n;
649
650	  n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
651	  if (n)
652	    {
653	      value = (tree) n->value;
654	      STRIP_TYPE_NOPS (value);
655	      if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
656		{
657		  *tp = value;
658		  return copy_body_r (tp, walk_subtrees, data);
659		}
660	    }
661	}
662      else if (TREE_CODE (*tp) == ADDR_EXPR
663	       && ((*lang_hooks.tree_inlining.auto_var_in_fn_p)
664		   (TREE_OPERAND (*tp, 0), fn)))
665	{
666	  /* Get rid of &* from inline substitutions.  It can occur when
667	     someone takes the address of a parm or return slot passed by
668	     invisible reference.  */
669	  tree decl = TREE_OPERAND (*tp, 0), value;
670	  splay_tree_node n;
671
672	  n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
673	  if (n)
674	    {
675	      value = (tree) n->value;
676	      if (TREE_CODE (value) == INDIRECT_REF)
677		{
678		  *tp = convert (TREE_TYPE (*tp), TREE_OPERAND (value, 0));
679		  return copy_body_r (tp, walk_subtrees, data);
680		}
681	    }
682	}
683
684      copy_tree_r (tp, walk_subtrees, NULL);
685
686      TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
687
688      /* The copied TARGET_EXPR has never been expanded, even if the
689	 original node was expanded already.  */
690      if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
691	{
692	  TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
693	  TREE_OPERAND (*tp, 3) = NULL_TREE;
694	}
695    }
696
697  /* Keep iterating.  */
698  return NULL_TREE;
699}
700
701/* Make a copy of the body of FN so that it can be inserted inline in
702   another function.  */
703
704static tree
705copy_body (inline_data *id)
706{
707  tree body;
708
709  body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
710  walk_tree (&body, copy_body_r, id, NULL);
711
712  return body;
713}
714
715/* Generate code to initialize the parameters of the function at the
716   top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
717
718static tree
719#ifndef INLINER_FOR_JAVA
720initialize_inlined_parameters (inline_data *id, tree args, tree fn)
721#else /* INLINER_FOR_JAVA */
722initialize_inlined_parameters (inline_data *id, tree args, tree fn, tree block)
723#endif /* INLINER_FOR_JAVA */
724{
725  tree init_stmts;
726  tree parms;
727  tree a;
728  tree p;
729#ifdef INLINER_FOR_JAVA
730  tree vars = NULL_TREE;
731#endif /* INLINER_FOR_JAVA */
732  int argnum = 0;
733
734  /* Figure out what the parameters are.  */
735  parms =
736DECL_ARGUMENTS (fn);
737
738  /* Start with no initializations whatsoever.  */
739  init_stmts = NULL_TREE;
740
741  /* Loop through the parameter declarations, replacing each with an
742     equivalent VAR_DECL, appropriately initialized.  */
743  for (p = parms, a = args; p;
744       a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
745    {
746#ifndef INLINER_FOR_JAVA
747      tree init_stmt;
748      tree cleanup;
749#endif /* not INLINER_FOR_JAVA */
750      tree var;
751      tree value;
752      tree var_sub;
753
754      ++argnum;
755
756      /* Find the initializer.  */
757      value = (*lang_hooks.tree_inlining.convert_parm_for_inlining)
758	      (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
759
760      /* If the parameter is never assigned to, we may not need to
761	 create a new variable here at all.  Instead, we may be able
762	 to just use the argument value.  */
763      if (TREE_READONLY (p)
764	  && !TREE_ADDRESSABLE (p)
765	  && value && !TREE_SIDE_EFFECTS (value))
766	{
767	  /* Simplify the value, if possible.  */
768	  value = fold (DECL_P (value) ? decl_constant_value (value) : value);
769
770	  /* We can't risk substituting complex expressions.  They
771	     might contain variables that will be assigned to later.
772	     Theoretically, we could check the expression to see if
773	     all of the variables that determine its value are
774	     read-only, but we don't bother.  */
775	  if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
776	    {
777	      /* If this is a declaration, wrap it a NOP_EXPR so that
778		 we don't try to put the VALUE on the list of
779		 BLOCK_VARS.  */
780	      if (DECL_P (value))
781		value = build1 (NOP_EXPR, TREE_TYPE (value), value);
782
783	      /* If this is a constant, make sure it has the right type.  */
784	      else if (TREE_TYPE (value) != TREE_TYPE (p))
785		value = fold (build1 (NOP_EXPR, TREE_TYPE (p), value));
786
787	      splay_tree_insert (id->decl_map,
788				 (splay_tree_key) p,
789				 (splay_tree_value) value);
790	      continue;
791	    }
792	}
793
794      /* Make an equivalent VAR_DECL.  */
795      var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
796
797      /* See if the frontend wants to pass this by invisible reference.  If
798	 so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
799	 replace uses of the PARM_DECL with dereferences.  */
800      if (TREE_TYPE (var) != TREE_TYPE (p)
801	  && POINTER_TYPE_P (TREE_TYPE (var))
802	  && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
803	var_sub = build1 (INDIRECT_REF, TREE_TYPE (p), var);
804      else
805	var_sub = var;
806
807      /* Register the VAR_DECL as the equivalent for the PARM_DECL;
808	 that way, when the PARM_DECL is encountered, it will be
809	 automatically replaced by the VAR_DECL.  */
810      splay_tree_insert (id->decl_map,
811			 (splay_tree_key) p,
812			 (splay_tree_value) var_sub);
813
814      /* Declare this new variable.  */
815#ifndef INLINER_FOR_JAVA
816      init_stmt = build_stmt (DECL_STMT, var);
817      TREE_CHAIN (init_stmt) = init_stmts;
818      init_stmts = init_stmt;
819#else /* INLINER_FOR_JAVA */
820      TREE_CHAIN (var) = vars;
821      vars = var;
822#endif /* INLINER_FOR_JAVA */
823
824      /* Initialize this VAR_DECL from the equivalent argument.  If
825	 the argument is an object, created via a constructor or copy,
826	 this will not result in an extra copy: the TARGET_EXPR
827	 representing the argument will be bound to VAR, and the
828	 object will be constructed in VAR.  */
829      if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
830#ifndef INLINER_FOR_JAVA
831	DECL_INITIAL (var) = value;
832      else
833	{
834	  /* Even if P was TREE_READONLY, the new VAR should not be.
835	     In the original code, we would have constructed a
836	     temporary, and then the function body would have never
837	     changed the value of P.  However, now, we will be
838	     constructing VAR directly.  The constructor body may
839	     change its value multiple times as it is being
840	     constructed.  Therefore, it must not be TREE_READONLY;
841	     the back-end assumes that TREE_READONLY variable is
842	     assigned to only once.  */
843	  TREE_READONLY (var) = 0;
844
845	  /* Build a run-time initialization.  */
846	  init_stmt = build_stmt (EXPR_STMT,
847				  build (INIT_EXPR, TREE_TYPE (p),
848					 var, value));
849	  /* Add this initialization to the list.  Note that we want the
850	     declaration *after* the initialization because we are going
851	     to reverse all the initialization statements below.  */
852	  TREE_CHAIN (init_stmt) = init_stmts;
853	  init_stmts = init_stmt;
854	}
855
856      /* See if we need to clean up the declaration.  */
857      cleanup = (*lang_hooks.maybe_build_cleanup) (var);
858      if (cleanup)
859	{
860	  tree cleanup_stmt;
861	  /* Build the cleanup statement.  */
862	  cleanup_stmt = build_stmt (CLEANUP_STMT, var, cleanup);
863	  /* Add it to the *front* of the list; the list will be
864	     reversed below.  */
865	  TREE_CHAIN (cleanup_stmt) = init_stmts;
866	  init_stmts = cleanup_stmt;
867	}
868#else /* INLINER_FOR_JAVA */
869	{
870	  tree assignment = build (MODIFY_EXPR, TREE_TYPE (p), var, value);
871	  init_stmts = add_stmt_to_compound (init_stmts, TREE_TYPE (p),
872					     assignment);
873	}
874      else
875	{
876	  /* Java objects don't ever need constructing when being
877             passed as arguments because only call by reference is
878             supported.  */
879	  abort ();
880	}
881#endif /* INLINER_FOR_JAVA */
882    }
883
884#ifndef INLINER_FOR_JAVA
885  /* Evaluate trailing arguments.  */
886  for (; a; a = TREE_CHAIN (a))
887    {
888      tree init_stmt;
889      tree value = TREE_VALUE (a);
890
891      if (! value || ! TREE_SIDE_EFFECTS (value))
892	continue;
893
894      init_stmt = build_stmt (EXPR_STMT, value);
895      TREE_CHAIN (init_stmt) = init_stmts;
896      init_stmts = init_stmt;
897    }
898
899  /* The initialization statements have been built up in reverse
900     order.  Straighten them out now.  */
901  return nreverse (init_stmts);
902#else /* INLINER_FOR_JAVA */
903  BLOCK_VARS (block) = nreverse (vars);
904  return init_stmts;
905#endif /* INLINER_FOR_JAVA */
906}
907
908/* Declare a return variable to replace the RESULT_DECL for the
909   function we are calling.  An appropriate DECL_STMT is returned.
910   The USE_STMT is filled in to contain a use of the declaration to
911   indicate the return value of the function.  */
912
913#ifndef INLINER_FOR_JAVA
914static tree
915declare_return_variable (struct inline_data *id, tree return_slot_addr,
916			 tree *use_stmt)
917#else /* INLINER_FOR_JAVA */
918static tree
919declare_return_variable (struct inline_data *id, tree return_slot_addr,
920			 tree *var)
921#endif /* INLINER_FOR_JAVA */
922{
923  tree fn = VARRAY_TOP_TREE (id->fns);
924  tree result = DECL_RESULT (fn);
925#ifndef INLINER_FOR_JAVA
926  tree var;
927#endif /* not INLINER_FOR_JAVA */
928  int need_return_decl = 1;
929
930  /* We don't need to do anything for functions that don't return
931     anything.  */
932  if (!result || VOID_TYPE_P (TREE_TYPE (result)))
933    {
934#ifndef INLINER_FOR_JAVA
935      *use_stmt = NULL_TREE;
936#else /* INLINER_FOR_JAVA */
937      *var = NULL_TREE;
938#endif /* INLINER_FOR_JAVA */
939      return NULL_TREE;
940    }
941
942#ifndef INLINER_FOR_JAVA
943  var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
944	 (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
945	  &need_return_decl, return_slot_addr));
946
947  /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
948     way, when the RESULT_DECL is encountered, it will be
949     automatically replaced by the VAR_DECL.  */
950  splay_tree_insert (id->decl_map,
951		     (splay_tree_key) result,
952		     (splay_tree_value) var);
953
954  /* Build the USE_STMT.  If the return type of the function was
955     promoted, convert it back to the expected type.  */
956  if (TREE_TYPE (var) == TREE_TYPE (TREE_TYPE (fn)))
957    *use_stmt = build_stmt (EXPR_STMT, var);
958  else
959    *use_stmt = build_stmt (EXPR_STMT,
960			    build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)),
961				    var));
962  TREE_ADDRESSABLE (*use_stmt) = 1;
963
964  /* Build the declaration statement if FN does not return an
965     aggregate.  */
966  if (need_return_decl)
967    return build_stmt (DECL_STMT, var);
968#else /* INLINER_FOR_JAVA */
969  *var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
970	 (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
971	  &need_return_decl, return_slot_addr));
972
973  splay_tree_insert (id->decl_map,
974		     (splay_tree_key) result,
975		     (splay_tree_value) *var);
976  DECL_IGNORED_P (*var) = 1;
977  if (need_return_decl)
978    return *var;
979#endif /* INLINER_FOR_JAVA */
980  /* If FN does return an aggregate, there's no need to declare the
981     return variable; we're using a variable in our caller's frame.  */
982  else
983    return NULL_TREE;
984}
985
986/* Returns nonzero if a function can be inlined as a tree.  */
987
988bool
989tree_inlinable_function_p (tree fn)
990{
991  return inlinable_function_p (fn);
992}
993
994static const char *inline_forbidden_reason;
995
996static tree
997inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
998		      void *fnp)
999{
1000  tree node = *nodep;
1001  tree fn = (tree) fnp;
1002  tree t;
1003
1004  switch (TREE_CODE (node))
1005    {
1006    case CALL_EXPR:
1007      /* Refuse to inline alloca call unless user explicitly forced so as
1008	 this may change program's memory overhead drastically when the
1009	 function using alloca is called in loop.  In GCC present in
1010	 SPEC2000 inlining into schedule_block cause it to require 2GB of
1011	 RAM instead of 256MB.  */
1012      if (alloca_call_p (node)
1013	  && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1014	{
1015	  inline_forbidden_reason
1016	    = N_("%Jfunction '%F' can never be inlined because it uses "
1017		 "alloca (override using the always_inline attribute)");
1018	  return node;
1019	}
1020      t = get_callee_fndecl (node);
1021      if (! t)
1022	break;
1023
1024
1025      /* We cannot inline functions that call setjmp.  */
1026      if (setjmp_call_p (t))
1027	{
1028	  inline_forbidden_reason
1029	    = N_("%Jfunction '%F' can never be inlined because it uses setjmp");
1030	  return node;
1031	}
1032
1033      if (DECL_BUILT_IN (t))
1034	switch (DECL_FUNCTION_CODE (t))
1035	  {
1036	    /* We cannot inline functions that take a variable number of
1037	       arguments.  */
1038	  case BUILT_IN_VA_START:
1039	  case BUILT_IN_STDARG_START:
1040	  case BUILT_IN_NEXT_ARG:
1041	  case BUILT_IN_VA_END:
1042	    {
1043	      inline_forbidden_reason
1044		= N_("%Jfunction '%F' can never be inlined because it "
1045		     "uses variable argument lists");
1046	      return node;
1047	    }
1048	  case BUILT_IN_LONGJMP:
1049	    {
1050	      /* We can't inline functions that call __builtin_longjmp at
1051		 all.  The non-local goto machinery really requires the
1052		 destination be in a different function.  If we allow the
1053		 function calling __builtin_longjmp to be inlined into the
1054		 function calling __builtin_setjmp, Things will Go Awry.  */
1055	      /* ??? Need front end help to identify "regular" non-local
1056		 goto.  */
1057	      if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
1058		{
1059		  inline_forbidden_reason
1060		    = N_("%Jfunction '%F' can never be inlined because "
1061			 "it uses setjmp-longjmp exception handling");
1062		  return node;
1063		}
1064	    }
1065
1066	  default:
1067	    break;
1068	  }
1069      break;
1070
1071#ifndef INLINER_FOR_JAVA
1072    case DECL_STMT:
1073      /* We cannot inline functions that contain other functions.  */
1074      if (TREE_CODE (TREE_OPERAND (node, 0)) == FUNCTION_DECL
1075	  && DECL_INITIAL (TREE_OPERAND (node, 0)))
1076	{
1077	  inline_forbidden_reason
1078	    = N_("%Jfunction '%F' can never be inlined "
1079		 "because it contains a nested function");
1080	  return node;
1081	}
1082      break;
1083
1084    case GOTO_STMT:
1085    case GOTO_EXPR:
1086      t = TREE_OPERAND (node, 0);
1087
1088      /* We will not inline a function which uses computed goto.  The
1089	 addresses of its local labels, which may be tucked into
1090	 global storage, are of course not constant across
1091	 instantiations, which causes unexpected behavior.  */
1092      if (TREE_CODE (t) != LABEL_DECL)
1093	{
1094	  inline_forbidden_reason
1095	    = N_("%Jfunction '%F' can never be inlined "
1096		 "because it contains a computed goto");
1097	  return node;
1098	}
1099
1100      /* We cannot inline a nested function that jumps to a nonlocal
1101         label.  */
1102      if (TREE_CODE (t) == LABEL_DECL && DECL_CONTEXT (t) != fn)
1103	{
1104	  inline_forbidden_reason
1105	    = N_("%Jfunction '%F' can never be inlined "
1106		 "because it contains a nonlocal goto");
1107	  return node;
1108	}
1109
1110      break;
1111
1112    case RECORD_TYPE:
1113    case UNION_TYPE:
1114      /* We cannot inline a function of the form
1115
1116	   void F (int i) { struct S { int ar[i]; } s; }
1117
1118	 Attempting to do so produces a catch-22.
1119	 If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1120	 UNION_TYPE nodes, then it goes into infinite recursion on a
1121	 structure containing a pointer to its own type.  If it doesn't,
1122	 then the type node for S doesn't get adjusted properly when
1123	 F is inlined, and we abort in find_function_data.  */
1124      for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1125	if (variably_modified_type_p (TREE_TYPE (t)))
1126	  {
1127	    inline_forbidden_reason
1128	      = N_("%Jfunction '%F' can never be inlined "
1129		   "because it uses variable sized variables");
1130	    return node;
1131	  }
1132#endif
1133    default:
1134      break;
1135    }
1136
1137  return NULL_TREE;
1138}
1139
1140/* Return subexpression representing possible alloca call, if any.  */
1141static tree
1142inline_forbidden_p (tree fndecl)
1143{
1144  location_t saved_loc = input_location;
1145  tree ret = walk_tree_without_duplicates
1146		(&DECL_SAVED_TREE (fndecl), inline_forbidden_p_1, fndecl);
1147  input_location = saved_loc;
1148  return ret;
1149}
1150
1151/* Returns nonzero if FN is a function that does not have any
1152   fundamental inline blocking properties.  */
1153
1154static bool
1155inlinable_function_p (tree fn)
1156{
1157  bool inlinable = true;
1158
1159  /* If we've already decided this function shouldn't be inlined,
1160     there's no need to check again.  */
1161  if (DECL_UNINLINABLE (fn))
1162    return false;
1163
1164  /* See if there is any language-specific reason it cannot be
1165     inlined.  (It is important that this hook be called early because
1166     in C++ it may result in template instantiation.)
1167     If the function is not inlinable for language-specific reasons,
1168     it is left up to the langhook to explain why.  */
1169  inlinable = !(*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn);
1170
1171  /* If we don't have the function body available, we can't inline it.
1172     However, this should not be recorded since we also get here for
1173     forward declared inline functions.  Therefore, return at once.  */
1174  if (!DECL_SAVED_TREE (fn))
1175    return false;
1176
1177  /* If we're not inlining at all, then we cannot inline this function.  */
1178  else if (!flag_inline_trees)
1179    inlinable = false;
1180
1181  /* Only try to inline functions if DECL_INLINE is set.  This should be
1182     true for all functions declared `inline', and for all other functions
1183     as well with -finline-functions.
1184
1185     Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1186     it's the front-end that must set DECL_INLINE in this case, because
1187     dwarf2out loses if a function that does not have DECL_INLINE set is
1188     inlined anyway.  That is why we have both DECL_INLINE and
1189     DECL_DECLARED_INLINE_P.  */
1190  /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1191	    here should be redundant.  */
1192  else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1193    inlinable = false;
1194
1195#ifdef INLINER_FOR_JAVA
1196  /* Synchronized methods can't be inlined.  This is a bug.  */
1197  else if (METHOD_SYNCHRONIZED (fn))
1198    inlinable = false;
1199#endif /* INLINER_FOR_JAVA */
1200
1201  else if (inline_forbidden_p (fn))
1202    {
1203      /* See if we should warn about uninlinable functions.  Previously,
1204	 some of these warnings would be issued while trying to expand
1205	 the function inline, but that would cause multiple warnings
1206	 about functions that would for example call alloca.  But since
1207	 this a property of the function, just one warning is enough.
1208	 As a bonus we can now give more details about the reason why a
1209	 function is not inlinable.
1210	 We only warn for functions declared `inline' by the user.  */
1211      bool do_warning = (warn_inline
1212			 && DECL_INLINE (fn)
1213			 && DECL_DECLARED_INLINE_P (fn)
1214			 && !DECL_IN_SYSTEM_HEADER (fn));
1215
1216      if (lookup_attribute ("always_inline",
1217			    DECL_ATTRIBUTES (fn)))
1218	sorry (inline_forbidden_reason, fn, fn);
1219      else if (do_warning)
1220	warning (inline_forbidden_reason, fn, fn);
1221
1222      inlinable = false;
1223    }
1224
1225  /* Squirrel away the result so that we don't have to check again.  */
1226  DECL_UNINLINABLE (fn) = !inlinable;
1227
1228  return inlinable;
1229}
1230
1231/* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1232
1233static tree
1234expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1235{
1236  inline_data *id;
1237  tree t;
1238  tree expr;
1239  tree stmt;
1240#ifndef INLINER_FOR_JAVA
1241  tree chain;
1242  tree scope_stmt;
1243  tree use_stmt;
1244#else /* INLINER_FOR_JAVA */
1245  tree retvar;
1246#endif /* INLINER_FOR_JAVA */
1247  tree fn;
1248  tree arg_inits;
1249  tree *inlined_body;
1250  splay_tree st;
1251  tree args;
1252  tree return_slot_addr;
1253  const char *reason;
1254
1255  /* See what we've got.  */
1256  id = (inline_data *) data;
1257  t = *tp;
1258
1259  /* Recurse, but letting recursive invocations know that we are
1260     inside the body of a TARGET_EXPR.  */
1261  if (TREE_CODE (*tp) == TARGET_EXPR)
1262    {
1263#ifndef INLINER_FOR_JAVA
1264      int i, len = first_rtl_op (TARGET_EXPR);
1265
1266      /* We're walking our own subtrees.  */
1267      *walk_subtrees = 0;
1268
1269      /* Actually walk over them.  This loop is the body of
1270	 walk_trees, omitting the case where the TARGET_EXPR
1271	 itself is handled.  */
1272      for (i = 0; i < len; ++i)
1273	{
1274	  if (i == 2)
1275	    ++id->in_target_cleanup_p;
1276	  walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1277		     id->tree_pruner);
1278	  if (i == 2)
1279	    --id->in_target_cleanup_p;
1280	}
1281
1282      return NULL_TREE;
1283#else /* INLINER_FOR_JAVA */
1284      abort ();
1285#endif /* INLINER_FOR_JAVA */
1286    }
1287  else if (TREE_CODE (t) == EXPR_WITH_FILE_LOCATION)
1288    {
1289      /* We're walking the subtree directly.  */
1290      *walk_subtrees = 0;
1291      /* Update the source position.  */
1292      push_srcloc (EXPR_WFL_FILENAME (t), EXPR_WFL_LINENO (t));
1293      walk_tree (&EXPR_WFL_NODE (t), expand_call_inline, data,
1294		 id->tree_pruner);
1295      /* Restore the original source position.  */
1296      pop_srcloc ();
1297
1298      return NULL_TREE;
1299    }
1300
1301  if (TYPE_P (t))
1302    /* Because types were not copied in copy_body, CALL_EXPRs beneath
1303       them should not be expanded.  This can happen if the type is a
1304       dynamic array type, for example.  */
1305    *walk_subtrees = 0;
1306
1307  /* From here on, we're only interested in CALL_EXPRs.  */
1308  if (TREE_CODE (t) != CALL_EXPR)
1309    return NULL_TREE;
1310
1311  /* First, see if we can figure out what function is being called.
1312     If we cannot, then there is no hope of inlining the function.  */
1313  fn = get_callee_fndecl (t);
1314  if (!fn)
1315    return NULL_TREE;
1316
1317  /* Turn forward declarations into real ones.  */
1318  fn = cgraph_node (fn)->decl;
1319
1320  /* If fn is a declaration of a function in a nested scope that was
1321     globally declared inline, we don't set its DECL_INITIAL.
1322     However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1323     C++ front-end uses it for cdtors to refer to their internal
1324     declarations, that are not real functions.  Fortunately those
1325     don't have trees to be saved, so we can tell by checking their
1326     DECL_SAVED_TREE.  */
1327  if (! DECL_INITIAL (fn)
1328      && DECL_ABSTRACT_ORIGIN (fn)
1329      && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1330    fn = DECL_ABSTRACT_ORIGIN (fn);
1331
1332  /* Don't try to inline functions that are not well-suited to
1333     inlining.  */
1334  if (!cgraph_inline_p (id->current_decl, fn, &reason))
1335    {
1336      if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1337	{
1338	  sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1339	  sorry ("called from here");
1340	}
1341      else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1342	       && !DECL_IN_SYSTEM_HEADER (fn)
1343	       && strlen (reason))
1344	{
1345	  warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1346	  warning ("called from here");
1347	}
1348      return NULL_TREE;
1349    }
1350
1351  if (! (*lang_hooks.tree_inlining.start_inlining) (fn))
1352    return NULL_TREE;
1353
1354  /* Set the current filename and line number to the function we are
1355     inlining so that when we create new _STMT nodes here they get
1356     line numbers corresponding to the function we are calling.  We
1357     wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
1358     because individual statements don't record the filename.  */
1359  push_srcloc (DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn));
1360
1361#ifndef INLINER_FOR_JAVA
1362  /* Build a statement-expression containing code to initialize the
1363     arguments, the actual inline expansion of the body, and a label
1364     for the return statements within the function to jump to.  The
1365     type of the statement expression is the return type of the
1366     function call.  */
1367  expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), make_node (COMPOUND_STMT));
1368  /* There is no scope associated with the statement-expression.  */
1369  STMT_EXPR_NO_SCOPE (expr) = 1;
1370  if (lookup_attribute ("warn_unused_result",
1371			TYPE_ATTRIBUTES (TREE_TYPE (fn))))
1372    STMT_EXPR_WARN_UNUSED_RESULT (expr) = 1;
1373  stmt = STMT_EXPR_STMT (expr);
1374#else /* INLINER_FOR_JAVA */
1375  /* Build a block containing code to initialize the arguments, the
1376     actual inline expansion of the body, and a label for the return
1377     statements within the function to jump to.  The type of the
1378     statement expression is the return type of the function call.  */
1379  stmt = NULL;
1380  expr = build (BLOCK, TREE_TYPE (TREE_TYPE (fn)), stmt);
1381#endif /* INLINER_FOR_JAVA */
1382
1383  /* Local declarations will be replaced by their equivalents in this
1384     map.  */
1385  st = id->decl_map;
1386  id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1387				 NULL, NULL);
1388
1389  /* Initialize the parameters.  */
1390  args = TREE_OPERAND (t, 1);
1391  return_slot_addr = NULL_TREE;
1392  if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1393    {
1394      return_slot_addr = TREE_VALUE (args);
1395      args = TREE_CHAIN (args);
1396    }
1397
1398#ifndef INLINER_FOR_JAVA
1399  arg_inits = initialize_inlined_parameters (id, args, fn);
1400  /* Expand any inlined calls in the initializers.  Do this before we
1401     push FN on the stack of functions we are inlining; we want to
1402     inline calls to FN that appear in the initializers for the
1403     parameters.  */
1404  expand_calls_inline (&arg_inits, id);
1405  /* And add them to the tree.  */
1406  COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), arg_inits);
1407#else /* INLINER_FOR_JAVA */
1408  arg_inits = initialize_inlined_parameters (id, args, fn, expr);
1409  if (arg_inits)
1410    {
1411      /* Expand any inlined calls in the initializers.  Do this before we
1412	 push FN on the stack of functions we are inlining; we want to
1413	 inline calls to FN that appear in the initializers for the
1414	 parameters.  */
1415      expand_calls_inline (&arg_inits, id);
1416
1417      /* And add them to the tree.  */
1418      BLOCK_EXPR_BODY (expr) = add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1419						     TREE_TYPE (arg_inits),
1420						     arg_inits);
1421    }
1422#endif /* INLINER_FOR_JAVA */
1423
1424  /* Record the function we are about to inline so that we can avoid
1425     recursing into it.  */
1426  VARRAY_PUSH_TREE (id->fns, fn);
1427
1428  /* Record the function we are about to inline if optimize_function
1429     has not been called on it yet and we don't have it in the list.  */
1430  if (! DECL_INLINED_FNS (fn))
1431    {
1432      int i;
1433
1434      for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1435	if (VARRAY_TREE (id->inlined_fns, i) == fn)
1436	  break;
1437      if (i < 0)
1438	VARRAY_PUSH_TREE (id->inlined_fns, fn);
1439    }
1440
1441  /* Return statements in the function body will be replaced by jumps
1442     to the RET_LABEL.  */
1443  id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1444  DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1445
1446  if (! DECL_INITIAL (fn)
1447      || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
1448    abort ();
1449
1450#ifndef INLINER_FOR_JAVA
1451  /* Create a block to put the parameters in.  We have to do this
1452     after the parameters have been remapped because remapping
1453     parameters is different from remapping ordinary variables.  */
1454  scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
1455  SCOPE_BEGIN_P (scope_stmt) = 1;
1456  SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
1457  remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
1458  TREE_CHAIN (scope_stmt) = COMPOUND_BODY (stmt);
1459  COMPOUND_BODY (stmt) = scope_stmt;
1460
1461  /* Tell the debugging backends that this block represents the
1462     outermost scope of the inlined function.  */
1463  if (SCOPE_STMT_BLOCK (scope_stmt))
1464    BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
1465
1466  /* Declare the return variable for the function.  */
1467  COMPOUND_BODY (stmt)
1468    = chainon (COMPOUND_BODY (stmt),
1469	       declare_return_variable (id, return_slot_addr, &use_stmt));
1470#else /* INLINER_FOR_JAVA */
1471  {
1472    /* Declare the return variable for the function.  */
1473    tree decl = declare_return_variable (id, return_slot_addr, &retvar);
1474    if (retvar)
1475      {
1476	tree *next = &BLOCK_VARS (expr);
1477	while (*next)
1478	  next = &TREE_CHAIN (*next);
1479	*next = decl;
1480      }
1481  }
1482#endif /* INLINER_FOR_JAVA */
1483
1484  /* After we've initialized the parameters, we insert the body of the
1485     function itself.  */
1486#ifndef INLINER_FOR_JAVA
1487  inlined_body = &COMPOUND_BODY (stmt);
1488  while (*inlined_body)
1489    inlined_body = &TREE_CHAIN (*inlined_body);
1490  *inlined_body = copy_body (id);
1491#else /* INLINER_FOR_JAVA */
1492  {
1493    tree new_body;
1494    java_inlining_map_static_initializers (fn, id->decl_map);
1495    new_body = copy_body (id);
1496    TREE_TYPE (new_body) = TREE_TYPE (TREE_TYPE (fn));
1497    BLOCK_EXPR_BODY (expr)
1498      = add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1499			      TREE_TYPE (new_body), new_body);
1500    inlined_body = &BLOCK_EXPR_BODY (expr);
1501  }
1502#endif /* INLINER_FOR_JAVA */
1503
1504  /* After the body of the function comes the RET_LABEL.  This must come
1505     before we evaluate the returned value below, because that evaluation
1506     may cause RTL to be generated.  */
1507#ifndef INLINER_FOR_JAVA
1508  COMPOUND_BODY (stmt)
1509    = chainon (COMPOUND_BODY (stmt),
1510	       build_stmt (LABEL_STMT, id->ret_label));
1511#else /* INLINER_FOR_JAVA */
1512  {
1513    tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1514    BLOCK_EXPR_BODY (expr)
1515      = add_stmt_to_compound (BLOCK_EXPR_BODY (expr), void_type_node, label);
1516    TREE_SIDE_EFFECTS (label) = TREE_SIDE_EFFECTS (t);
1517  }
1518#endif /* INLINER_FOR_JAVA */
1519
1520  /* Finally, mention the returned value so that the value of the
1521     statement-expression is the returned value of the function.  */
1522#ifndef INLINER_FOR_JAVA
1523  COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), use_stmt);
1524
1525  /* Close the block for the parameters.  */
1526  scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
1527  SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
1528  remap_block (scope_stmt, NULL_TREE, id);
1529  COMPOUND_BODY (stmt)
1530    = chainon (COMPOUND_BODY (stmt), scope_stmt);
1531#else /* INLINER_FOR_JAVA */
1532  if (retvar)
1533    {
1534      /* Mention the retvar.  If the return type of the function was
1535	 promoted, convert it back to the expected type.  */
1536      if (TREE_TYPE (TREE_TYPE (fn)) != TREE_TYPE (retvar))
1537	retvar = build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)), retvar);
1538      BLOCK_EXPR_BODY (expr)
1539	= add_stmt_to_compound (BLOCK_EXPR_BODY (expr),
1540				TREE_TYPE (retvar), retvar);
1541    }
1542
1543  java_inlining_merge_static_initializers (fn, id->decl_map);
1544#endif /* INLINER_FOR_JAVA */
1545
1546  /* Clean up.  */
1547  splay_tree_delete (id->decl_map);
1548  id->decl_map = st;
1549
1550  /* The new expression has side-effects if the old one did.  */
1551  TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1552
1553  /* Replace the call by the inlined body.  Wrap it in an
1554     EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
1555     pointing to the right place.  */
1556#ifndef INLINER_FOR_JAVA
1557  chain = TREE_CHAIN (*tp);
1558#endif /* INLINER_FOR_JAVA */
1559  *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
1560			/*col=*/0);
1561  EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
1562#ifndef INLINER_FOR_JAVA
1563  TREE_CHAIN (*tp) = chain;
1564#endif /* not INLINER_FOR_JAVA */
1565  pop_srcloc ();
1566
1567  /* If the value of the new expression is ignored, that's OK.  We
1568     don't warn about this for CALL_EXPRs, so we shouldn't warn about
1569     the equivalent inlined version either.  */
1570  TREE_USED (*tp) = 1;
1571
1572  /* Update callgraph if needed.  */
1573  if (id->decl)
1574    {
1575      cgraph_remove_call (id->decl, fn);
1576      cgraph_create_edges (id->decl, *inlined_body);
1577    }
1578
1579  /* Recurse into the body of the just inlined function.  */
1580  {
1581    tree old_decl = id->current_decl;
1582    id->current_decl = fn;
1583    expand_calls_inline (inlined_body, id);
1584    id->current_decl = old_decl;
1585  }
1586  VARRAY_POP (id->fns);
1587
1588  /* Don't walk into subtrees.  We've already handled them above.  */
1589  *walk_subtrees = 0;
1590
1591  (*lang_hooks.tree_inlining.end_inlining) (fn);
1592
1593  /* Keep iterating.  */
1594  return NULL_TREE;
1595}
1596/* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
1597   expansions as appropriate.  */
1598
1599static void
1600expand_calls_inline (tree *tp, inline_data *id)
1601{
1602  /* Search through *TP, replacing all calls to inline functions by
1603     appropriate equivalents.  Use walk_tree in no-duplicates mode
1604     to avoid exponential time complexity.  (We can't just use
1605     walk_tree_without_duplicates, because of the special TARGET_EXPR
1606     handling in expand_calls.  The hash table is set up in
1607     optimize_function.  */
1608  walk_tree (tp, expand_call_inline, id, id->tree_pruner);
1609}
1610
1611/* Expand calls to inline functions in the body of FN.  */
1612
1613void
1614optimize_inline_calls (tree fn)
1615{
1616  inline_data id;
1617  tree prev_fn;
1618
1619  /* There is no point in performing inlining if errors have already
1620     occurred -- and we might crash if we try to inline invalid
1621     code.  */
1622  if (errorcount || sorrycount)
1623    return;
1624
1625  /* Clear out ID.  */
1626  memset (&id, 0, sizeof (id));
1627
1628  id.decl = fn;
1629  id.current_decl = fn;
1630  /* Don't allow recursion into FN.  */
1631  VARRAY_TREE_INIT (id.fns, 32, "fns");
1632  VARRAY_PUSH_TREE (id.fns, fn);
1633  /* Or any functions that aren't finished yet.  */
1634  prev_fn = NULL_TREE;
1635  if (current_function_decl)
1636    {
1637      VARRAY_PUSH_TREE (id.fns, current_function_decl);
1638      prev_fn = current_function_decl;
1639    }
1640
1641  prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls)
1642	     (&id.fns, prev_fn));
1643
1644  /* Create the list of functions this call will inline.  */
1645  VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1646
1647  /* Keep track of the low-water mark, i.e., the point where the first
1648     real inlining is represented in ID.FNS.  */
1649  id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1650
1651  /* Replace all calls to inline functions with the bodies of those
1652     functions.  */
1653  id.tree_pruner = htab_create (37, htab_hash_pointer,
1654				htab_eq_pointer, NULL);
1655  expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1656
1657  /* Clean up.  */
1658  htab_delete (id.tree_pruner);
1659  if (DECL_LANG_SPECIFIC (fn))
1660    {
1661      tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1662
1663      if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1664	memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1665		VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1666      DECL_INLINED_FNS (fn) = ifn;
1667    }
1668}
1669
1670/* FN is a function that has a complete body, and CLONE is a function
1671   whose body is to be set to a copy of FN, mapping argument
1672   declarations according to the ARG_MAP splay_tree.  */
1673
1674void
1675clone_body (tree clone, tree fn, void *arg_map)
1676{
1677  inline_data id;
1678
1679  /* Clone the body, as if we were making an inline call.  But, remap
1680     the parameters in the callee to the parameters of caller.  If
1681     there's an in-charge parameter, map it to an appropriate
1682     constant.  */
1683  memset (&id, 0, sizeof (id));
1684  VARRAY_TREE_INIT (id.fns, 2, "fns");
1685  VARRAY_PUSH_TREE (id.fns, clone);
1686  VARRAY_PUSH_TREE (id.fns, fn);
1687  id.decl_map = (splay_tree)arg_map;
1688
1689  /* Cloning is treated slightly differently from inlining.  Set
1690     CLONING_P so that it's clear which operation we're performing.  */
1691  id.cloning_p = true;
1692
1693  /* Actually copy the body.  */
1694  TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1695}
1696
1697/* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1698   FUNC is called with the DATA and the address of each sub-tree.  If
1699   FUNC returns a non-NULL value, the traversal is aborted, and the
1700   value returned by FUNC is returned.  If HTAB is non-NULL it is used
1701   to record the nodes visited, and to avoid visiting a node more than
1702   once.  */
1703
1704tree
1705walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
1706{
1707  htab_t htab = (htab_t) htab_;
1708  enum tree_code code;
1709  int walk_subtrees;
1710  tree result;
1711
1712#define WALK_SUBTREE(NODE)				\
1713  do							\
1714    {							\
1715      result = walk_tree (&(NODE), func, data, htab);	\
1716      if (result)					\
1717	return result;					\
1718    }							\
1719  while (0)
1720
1721#define WALK_SUBTREE_TAIL(NODE)				\
1722  do							\
1723    {							\
1724       tp = & (NODE);					\
1725       goto tail_recurse;				\
1726    }							\
1727  while (0)
1728
1729 tail_recurse:
1730  /* Skip empty subtrees.  */
1731  if (!*tp)
1732    return NULL_TREE;
1733
1734  if (htab)
1735    {
1736      void **slot;
1737
1738      /* Don't walk the same tree twice, if the user has requested
1739         that we avoid doing so.  */
1740      slot = htab_find_slot (htab, *tp, INSERT);
1741      if (*slot)
1742	return NULL_TREE;
1743      *slot = *tp;
1744    }
1745
1746  /* Call the function.  */
1747  walk_subtrees = 1;
1748  result = (*func) (tp, &walk_subtrees, data);
1749
1750  /* If we found something, return it.  */
1751  if (result)
1752    return result;
1753
1754  code = TREE_CODE (*tp);
1755
1756#ifndef INLINER_FOR_JAVA
1757  /* Even if we didn't, FUNC may have decided that there was nothing
1758     interesting below this point in the tree.  */
1759  if (!walk_subtrees)
1760    {
1761      if (STATEMENT_CODE_P (code) || code == TREE_LIST
1762	  || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1763	/* But we still need to check our siblings.  */
1764	WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1765      else
1766	return NULL_TREE;
1767    }
1768
1769  /* Handle common cases up front.  */
1770  if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1771#else /* INLINER_FOR_JAVA */
1772  if (code != EXIT_BLOCK_EXPR
1773      && code != SAVE_EXPR
1774      && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1775#endif /* INLINER_FOR_JAVA */
1776    {
1777      int i, len;
1778
1779#ifndef INLINER_FOR_JAVA
1780      /* Set lineno here so we get the right instantiation context
1781	 if we call instantiate_decl from inlinable_function_p.  */
1782      if (STATEMENT_CODE_P (code) && !STMT_LINENO_FOR_FN_P (*tp))
1783	input_line = STMT_LINENO (*tp);
1784#endif /* not INLINER_FOR_JAVA */
1785
1786      /* Walk over all the sub-trees of this operand.  */
1787      len = first_rtl_op (code);
1788      /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
1789	 But, we only want to walk once.  */
1790      if (code == TARGET_EXPR
1791	  && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
1792	--len;
1793      /* Go through the subtrees.  We need to do this in forward order so
1794         that the scope of a FOR_EXPR is handled properly.  */
1795      for (i = 0; i < len; ++i)
1796	WALK_SUBTREE (TREE_OPERAND (*tp, i));
1797
1798#ifndef INLINER_FOR_JAVA
1799      /* For statements, we also walk the chain so that we cover the
1800	 entire statement tree.  */
1801      if (STATEMENT_CODE_P (code))
1802	{
1803	  if (code == DECL_STMT
1804	      && DECL_STMT_DECL (*tp)
1805	      && DECL_P (DECL_STMT_DECL (*tp)))
1806	    {
1807	      /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
1808		 into declarations that are just mentioned, rather than
1809		 declared; they don't really belong to this part of the tree.
1810		 And, we can see cycles: the initializer for a declaration can
1811		 refer to the declaration itself.  */
1812	      WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
1813	      WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
1814	      WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
1815	      WALK_SUBTREE (TREE_TYPE (*tp));
1816	    }
1817
1818	  /* This can be tail-recursion optimized if we write it this way.  */
1819	  WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1820	}
1821
1822#endif /* not INLINER_FOR_JAVA */
1823      /* We didn't find what we were looking for.  */
1824      return NULL_TREE;
1825    }
1826  else if (TREE_CODE_CLASS (code) == 'd')
1827    {
1828      WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1829    }
1830  else if (TREE_CODE_CLASS (code) == 't')
1831    {
1832      WALK_SUBTREE (TYPE_SIZE (*tp));
1833      WALK_SUBTREE (TYPE_SIZE_UNIT (*tp));
1834      /* Also examine various special fields, below.  */
1835    }
1836
1837  result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
1838						      data, htab);
1839  if (result || ! walk_subtrees)
1840    return result;
1841
1842  /* Not one of the easy cases.  We must explicitly go through the
1843     children.  */
1844  switch (code)
1845    {
1846    case ERROR_MARK:
1847    case IDENTIFIER_NODE:
1848    case INTEGER_CST:
1849    case REAL_CST:
1850    case VECTOR_CST:
1851    case STRING_CST:
1852    case REAL_TYPE:
1853    case COMPLEX_TYPE:
1854    case VECTOR_TYPE:
1855    case VOID_TYPE:
1856    case BOOLEAN_TYPE:
1857    case UNION_TYPE:
1858    case ENUMERAL_TYPE:
1859    case BLOCK:
1860    case RECORD_TYPE:
1861    case CHAR_TYPE:
1862    case PLACEHOLDER_EXPR:
1863      /* None of these have subtrees other than those already walked
1864         above.  */
1865      break;
1866
1867    case POINTER_TYPE:
1868    case REFERENCE_TYPE:
1869      WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1870      break;
1871
1872    case TREE_LIST:
1873      WALK_SUBTREE (TREE_VALUE (*tp));
1874      WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1875      break;
1876
1877    case TREE_VEC:
1878      {
1879	int len = TREE_VEC_LENGTH (*tp);
1880
1881	if (len == 0)
1882	  break;
1883
1884	/* Walk all elements but the first.  */
1885	while (--len)
1886	  WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
1887
1888	/* Now walk the first one as a tail call.  */
1889	WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
1890      }
1891
1892    case COMPLEX_CST:
1893      WALK_SUBTREE (TREE_REALPART (*tp));
1894      WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
1895
1896    case CONSTRUCTOR:
1897      WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
1898
1899    case METHOD_TYPE:
1900      WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
1901      /* Fall through.  */
1902
1903    case FUNCTION_TYPE:
1904      WALK_SUBTREE (TREE_TYPE (*tp));
1905      {
1906	tree arg = TYPE_ARG_TYPES (*tp);
1907
1908	/* We never want to walk into default arguments.  */
1909	for (; arg; arg = TREE_CHAIN (arg))
1910	  WALK_SUBTREE (TREE_VALUE (arg));
1911      }
1912      break;
1913
1914    case ARRAY_TYPE:
1915      WALK_SUBTREE (TREE_TYPE (*tp));
1916      WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp));
1917
1918    case INTEGER_TYPE:
1919      WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
1920      WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp));
1921
1922    case OFFSET_TYPE:
1923      WALK_SUBTREE (TREE_TYPE (*tp));
1924      WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp));
1925
1926#ifdef INLINER_FOR_JAVA
1927    case EXIT_BLOCK_EXPR:
1928      WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
1929
1930    case SAVE_EXPR:
1931      WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
1932#endif /* INLINER_FOR_JAVA */
1933
1934    default:
1935      abort ();
1936    }
1937
1938  /* We didn't find what we were looking for.  */
1939  return NULL_TREE;
1940
1941#undef WALK_SUBTREE
1942#undef WALK_SUBTREE_TAIL
1943}
1944
1945/* Like walk_tree, but does not walk duplicate nodes more than
1946   once.  */
1947
1948tree
1949walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
1950{
1951  tree result;
1952  htab_t htab;
1953
1954  htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1955  result = walk_tree (tp, func, data, htab);
1956  htab_delete (htab);
1957  return result;
1958}
1959
1960/* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
1961
1962tree
1963copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
1964{
1965  enum tree_code code = TREE_CODE (*tp);
1966
1967  /* We make copies of most nodes.  */
1968  if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1969      || TREE_CODE_CLASS (code) == 'c'
1970      || code == TREE_LIST
1971      || code == TREE_VEC
1972      || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1973    {
1974      /* Because the chain gets clobbered when we make a copy, we save it
1975	 here.  */
1976      tree chain = TREE_CHAIN (*tp);
1977
1978      /* Copy the node.  */
1979      *tp = copy_node (*tp);
1980
1981      /* Now, restore the chain, if appropriate.  That will cause
1982	 walk_tree to walk into the chain as well.  */
1983      if (code == PARM_DECL || code == TREE_LIST
1984#ifndef INLINER_FOR_JAVA
1985	  || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)
1986	  || STATEMENT_CODE_P (code))
1987	TREE_CHAIN (*tp) = chain;
1988
1989      /* For now, we don't update BLOCKs when we make copies.  So, we
1990	 have to nullify all scope-statements.  */
1991      if (TREE_CODE (*tp) == SCOPE_STMT)
1992	SCOPE_STMT_BLOCK (*tp) = NULL_TREE;
1993#else /* INLINER_FOR_JAVA */
1994	  || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1995	TREE_CHAIN (*tp) = chain;
1996#endif /* INLINER_FOR_JAVA */
1997    }
1998  else if (TREE_CODE_CLASS (code) == 't')
1999    *walk_subtrees = 0;
2000
2001  return NULL_TREE;
2002}
2003
2004/* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2005   information indicating to what new SAVE_EXPR this one should be
2006   mapped, use that one.  Otherwise, create a new node and enter it in
2007   ST.  FN is the function into which the copy will be placed.  */
2008
2009void
2010remap_save_expr (tree *tp, void *st_, tree fn, int *walk_subtrees)
2011{
2012  splay_tree st = (splay_tree) st_;
2013  splay_tree_node n;
2014
2015  /* See if we already encountered this SAVE_EXPR.  */
2016  n = splay_tree_lookup (st, (splay_tree_key) *tp);
2017
2018  /* If we didn't already remap this SAVE_EXPR, do so now.  */
2019  if (!n)
2020    {
2021      tree t = copy_node (*tp);
2022
2023      /* The SAVE_EXPR is now part of the function into which we
2024	 are inlining this body.  */
2025      SAVE_EXPR_CONTEXT (t) = fn;
2026      /* And we haven't evaluated it yet.  */
2027      SAVE_EXPR_RTL (t) = NULL_RTX;
2028      /* Remember this SAVE_EXPR.  */
2029      n = splay_tree_insert (st,
2030			     (splay_tree_key) *tp,
2031			     (splay_tree_value) t);
2032      /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2033      splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2034    }
2035  else
2036    /* We've already walked into this SAVE_EXPR, so we needn't do it
2037       again.  */
2038    *walk_subtrees = 0;
2039
2040  /* Replace this SAVE_EXPR with the copy.  */
2041  *tp = (tree) n->value;
2042}
2043
2044#ifdef INLINER_FOR_JAVA
2045/* Add STMT to EXISTING if possible, otherwise create a new
2046   COMPOUND_EXPR and add STMT to it.  */
2047
2048static tree
2049add_stmt_to_compound (tree existing, tree type, tree stmt)
2050{
2051  if (!stmt)
2052    return existing;
2053  else if (existing)
2054    return build (COMPOUND_EXPR, type, existing, stmt);
2055  else
2056    return stmt;
2057}
2058
2059#endif /* INLINER_FOR_JAVA */
2060