gcc/tree-inline.c

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