gcc/tree-inline.c

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