gcc/tree-inline.c

   1 /* Tree inlining.
   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 "tree-mudflap.h"
  43 #include "function.h"
  44 #include "diagnostic.h"
  45
  46 /* I'm not real happy about this, but we need to handle gimple and
  47    non-gimple trees.  */
  48 #include "tree-iterator.h"
  49 #include "tree-gimple.h"
  50
  51 /* 0 if we should not perform inlining.
  52    1 if we should expand functions calls inline at the tree level.
  53    2 if we should consider *all* functions to be inline
  54    candidates.  */
  55
  56 int flag_inline_trees = 0;
  57
  58 /* To Do:
  59
  60    o In order to make inlining-on-trees work, we pessimized
  61      function-local static constants.  In particular, they are now
  62      always output, even when not addressed.  Fix this by treating
  63      function-local static constants just like global static
  64      constants; the back-end already knows not to output them if they
  65      are not needed.
  66
  67    o Provide heuristics to clamp inlining of recursive template
  68      calls?  */
  69
  70 /* Data required for function inlining.  */
  71
  72 typedef struct inline_data
  73 {
  74   /* A stack of the functions we are inlining.  For example, if we are
  75      compiling `f', which calls `g', which calls `h', and we are
  76      inlining the body of `h', the stack will contain, `h', followed
  77      by `g', followed by `f'.  The first few elements of the stack may
  78      contain other functions that we know we should not recurse into,
  79      even though they are not directly being inlined.  */
  80   varray_type fns;
  81   /* The index of the first element of FNS that really represents an
  82      inlined function.  */
  83   unsigned first_inlined_fn;
  84   /* The label to jump to when a return statement is encountered.  If
  85      this value is NULL, then return statements will simply be
  86      remapped as return statements, rather than as jumps.  */
  87   tree ret_label;
  88   /* The VAR_DECL for the return value.  */
  89   tree retvar;
  90   /* The map from local declarations in the inlined function to
  91      equivalents in the function into which it is being inlined.  */
  92   splay_tree decl_map;
  93   /* Nonzero if we are currently within the cleanup for a
  94      TARGET_EXPR.  */
  95   int in_target_cleanup_p;
  96   /* A list of the functions current function has inlined.  */
  97   varray_type inlined_fns;
  98   /* We use the same mechanism to build clones that we do to perform
  99      inlining.  However, there are a few places where we need to
 100      distinguish between those two situations.  This flag is true if
 101      we are cloning, rather than inlining.  */
 102   bool cloning_p;
 103   /* Similarly for saving function body.  */
 104   bool saving_p;
 105   /* Hash table used to prevent walk_tree from visiting the same node
 106      umpteen million times.  */
 107   htab_t tree_pruner;
 108   /* Callgraph node of function we are inlining into.  */
 109   struct cgraph_node *node;
 110   /* Callgraph node of currently inlined function.  */
 111   struct cgraph_node *current_node;
 112   /* Statement iterator.  We need this so we can keep the tree in
 113      gimple form when we insert the inlined function.   It is not
 114      used when we are not dealing with gimple trees.  */
 115   tree_stmt_iterator tsi;
 116 } inline_data;
 117
 118 /* Prototypes.  */
 119
 120 /* The approximate number of instructions per statement.  This number
 121    need not be particularly accurate; it is used only to make
 122    decisions about when a function is too big to inline.  */
 123 #define INSNS_PER_STMT (10)
 124
 125 static tree copy_body_r (tree *, int *, void *);
 126 static tree copy_body (inline_data *);
 127 static tree expand_call_inline (tree *, int *, void *);
 128 static void expand_calls_inline (tree *, inline_data *);
 129 static bool inlinable_function_p (tree);
 130 static tree remap_decl (tree, inline_data *);
 131 static tree remap_type (tree, inline_data *);
 132 static tree initialize_inlined_parameters (inline_data *, tree,
 133                                            tree, tree, tree);
 134 static void remap_block (tree *, inline_data *);
 135 static tree remap_decls (tree, inline_data *);
 136 static void copy_bind_expr (tree *, int *, inline_data *);
 137 static tree mark_local_for_remap_r (tree *, int *, void *);
 138 static tree unsave_r (tree *, int *, void *);
 139 static void declare_inline_vars (tree bind_expr, tree vars);
 140
 141 /* Insert a tree->tree mapping for ID.  Despite the name suggests
 142    that the trees should be variables, it is used for more than that.  */
 143
 144 static void
 145 insert_decl_map (inline_data *id, tree key, tree value)
 146 {
 147   splay_tree_insert (id->decl_map, (splay_tree_key) key,
 148                      (splay_tree_value) value);
 149
 150   /* Always insert an identity map as well.  If we see this same new
 151      node again, we won't want to duplicate it a second time.  */
 152   if (key != value)
 153     splay_tree_insert (id->decl_map, (splay_tree_key) value,
 154                        (splay_tree_value) value);
 155 }
 156
 157 /* Remap DECL during the copying of the BLOCK tree for the function.
 158    We are only called to remap local variables in the current function.  */
 159
 160 static tree
 161 remap_decl (tree decl, inline_data *id)
 162 {
 163   splay_tree_node n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 164   tree fn = VARRAY_TOP_TREE (id->fns);
 165
 166   /* See if we have remapped this declaration.  If we didn't already have an
 167      equivalent for this declaration, create one now.  */
 168   if (!n)
 169     {
 170       /* Make a copy of the variable or label.  */
 171       tree t = copy_decl_for_inlining (decl, fn, VARRAY_TREE (id->fns, 0));
 172
 173       /* Remap types, if necessary.  */
 174       TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
 175       if (TREE_CODE (t) == TYPE_DECL)
 176         DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
 177       else if (TREE_CODE (t) == PARM_DECL)
 178         DECL_ARG_TYPE_AS_WRITTEN (t)
 179           = remap_type (DECL_ARG_TYPE_AS_WRITTEN (t), id);
 180
 181       /* Remap sizes as necessary.  */
 182       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 183       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 184
 185       /* If fields, do likewise for offset and qualifier. */
 186       if (TREE_CODE (t) == FIELD_DECL)
 187         {
 188           walk_tree (&DECL_FIELD_OFFSET (t), copy_body_r, id, NULL);
 189           if (TREE_CODE (DECL_CONTEXT (t)) == QUAL_UNION_TYPE)
 190             walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
 191         }
 192
 193 #if 0
 194       /* FIXME handle anon aggrs.  */
 195       if (! DECL_NAME (t) && TREE_TYPE (t)
 196           && lang_hooks.tree_inlining.anon_aggr_type_p (TREE_TYPE (t)))
 197         {
 198           /* For a VAR_DECL of anonymous type, we must also copy the
 199              member VAR_DECLS here and rechain the DECL_ANON_UNION_ELEMS.  */
 200           tree members = NULL;
 201           tree src;
 202
 203           for (src = DECL_ANON_UNION_ELEMS (t); src;
 204                src = TREE_CHAIN (src))
 205             {
 206               tree member = remap_decl (TREE_VALUE (src), id);
 207
 208               if (TREE_PURPOSE (src))
 209                 abort ();
 210               members = tree_cons (NULL, member, members);
 211             }
 212           DECL_ANON_UNION_ELEMS (t) = nreverse (members);
 213         }
 214 #endif
 215
 216       /* Remember it, so that if we encounter this local entity
 217          again we can reuse this copy.  */
 218       insert_decl_map (id, decl, t);
 219       return t;
 220     }
 221
 222   return unshare_expr ((tree) n->value);
 223 }
 224
 225 static tree
 226 remap_type (tree type, inline_data *id)
 227 {
 228   splay_tree_node node;
 229   tree new, t;
 230
 231   if (type == NULL)
 232     return type;
 233
 234   /* See if we have remapped this type.  */
 235   node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
 236   if (node)
 237     return (tree) node->value;
 238
 239   /* The type only needs remapping if it's variably modified by a variable
 240      in the function we are inlining.  */
 241   if (! variably_modified_type_p (type, VARRAY_TOP_TREE (id->fns)))
 242     {
 243       insert_decl_map (id, type, type);
 244       return type;
 245     }
 246
 247   /* We do need a copy.  build and register it now.  If this is a pointer or
 248      reference type, remap the designated type and make a new pointer or
 249      reference type.  */
 250   if (TREE_CODE (type) == POINTER_TYPE)
 251     {
 252       new = build_pointer_type_for_mode (remap_type (TREE_TYPE (type), id),
 253                                          TYPE_MODE (type),
 254                                          TYPE_REF_CAN_ALIAS_ALL (type));
 255       insert_decl_map (id, type, new);
 256       return new;
 257     }
 258   else if (TREE_CODE (type) == REFERENCE_TYPE)
 259     {
 260       new = build_reference_type_for_mode (remap_type (TREE_TYPE (type), id),
 261                                             TYPE_MODE (type),
 262                                             TYPE_REF_CAN_ALIAS_ALL (type));
 263       insert_decl_map (id, type, new);
 264       return new;
 265     }
 266   else
 267     new = copy_node (type);
 268
 269   insert_decl_map (id, type, new);
 270
 271   /* This is a new type, not a copy of an old type.  Need to reassociate
 272      variants.  We can handle everything except the main variant lazily.  */
 273   t = TYPE_MAIN_VARIANT (type);
 274   if (type != t)
 275     {
 276       t = remap_type (t, id);
 277       TYPE_MAIN_VARIANT (new) = t;
 278       TYPE_NEXT_VARIANT (new) = TYPE_MAIN_VARIANT (t);
 279       TYPE_NEXT_VARIANT (t) = new;
 280     }
 281   else
 282     {
 283       TYPE_MAIN_VARIANT (new) = new;
 284       TYPE_NEXT_VARIANT (new) = NULL;
 285     }
 286
 287   /* Lazily create pointer and reference types.  */
 288   TYPE_POINTER_TO (new) = NULL;
 289   TYPE_REFERENCE_TO (new) = NULL;
 290
 291   switch (TREE_CODE (new))
 292     {
 293     case INTEGER_TYPE:
 294     case REAL_TYPE:
 295     case ENUMERAL_TYPE:
 296     case BOOLEAN_TYPE:
 297     case CHAR_TYPE:
 298       t = TYPE_MIN_VALUE (new);
 299       if (t && TREE_CODE (t) != INTEGER_CST)
 300         walk_tree (&TYPE_MIN_VALUE (new), copy_body_r, id, NULL);
 301
 302       t = TYPE_MAX_VALUE (new);
 303       if (t && TREE_CODE (t) != INTEGER_CST)
 304         walk_tree (&TYPE_MAX_VALUE (new), copy_body_r, id, NULL);
 305       return new;
 306
 307     case FUNCTION_TYPE:
 308       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 309       walk_tree (&TYPE_ARG_TYPES (new), copy_body_r, id, NULL);
 310       return new;
 311
 312     case ARRAY_TYPE:
 313       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 314       TYPE_DOMAIN (new) = remap_type (TYPE_DOMAIN (new), id);
 315       break;
 316
 317     case RECORD_TYPE:
 318     case UNION_TYPE:
 319     case QUAL_UNION_TYPE:
 320       walk_tree (&TYPE_FIELDS (new), copy_body_r, id, NULL);
 321       break;
 322
 323     case FILE_TYPE:
 324     case SET_TYPE:
 325     case OFFSET_TYPE:
 326     default:
 327       /* Shouldn't have been thought variable sized.  */
 328       abort ();
 329     }
 330
 331   walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
 332   walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
 333
 334   return new;
 335 }
 336
 337 static tree
 338 remap_decls (tree decls, inline_data *id)
 339 {
 340   tree old_var;
 341   tree new_decls = NULL_TREE;
 342
 343   /* Remap its variables.  */
 344   for (old_var = decls; old_var; old_var = TREE_CHAIN (old_var))
 345     {
 346       tree new_var;
 347
 348       /* Remap the variable.  */
 349       new_var = remap_decl (old_var, id);
 350
 351       /* If we didn't remap this variable, so we can't mess with its
 352          TREE_CHAIN.  If we remapped this variable to the return slot, it's
 353          already declared somewhere else, so don't declare it here.  */
 354       if (!new_var || new_var == id->retvar)
 355         ;
 356 #ifdef ENABLE_CHECKING
 357       else if (!DECL_P (new_var))
 358         abort ();
 359 #endif
 360       else
 361         {
 362           TREE_CHAIN (new_var) = new_decls;
 363           new_decls = new_var;
 364         }
 365     }
 366
 367   return nreverse (new_decls);
 368 }
 369
 370 /* Copy the BLOCK to contain remapped versions of the variables
 371    therein.  And hook the new block into the block-tree.  */
 372
 373 static void
 374 remap_block (tree *block, inline_data *id)
 375 {
 376   tree old_block;
 377   tree new_block;
 378   tree fn;
 379
 380   /* Make the new block.  */
 381   old_block = *block;
 382   new_block = make_node (BLOCK);
 383   TREE_USED (new_block) = TREE_USED (old_block);
 384   BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 385   *block = new_block;
 386
 387   /* Remap its variables.  */
 388   BLOCK_VARS (new_block) = remap_decls (BLOCK_VARS (old_block), id);
 389
 390   fn = VARRAY_TREE (id->fns, 0);
 391 #if 1
 392   /* FIXME!  It shouldn't be so hard to manage blocks.  Rebuilding them in
 393      rest_of_compilation is a good start.  */
 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 #endif
 413   /* Remember the remapped block.  */
 414   insert_decl_map (id, old_block, new_block);
 415 }
 416
 417 static void
 418 copy_statement_list (tree *tp)
 419 {
 420   tree_stmt_iterator oi, ni;
 421   tree new;
 422
 423   new = alloc_stmt_list ();
 424   ni = tsi_start (new);
 425   oi = tsi_start (*tp);
 426   *tp = new;
 427
 428   for (; !tsi_end_p (oi); tsi_next (&oi))
 429     tsi_link_after (&ni, tsi_stmt (oi), TSI_NEW_STMT);
 430 }
 431
 432 static void
 433 copy_bind_expr (tree *tp, int *walk_subtrees, inline_data *id)
 434 {
 435   tree block = BIND_EXPR_BLOCK (*tp);
 436   /* Copy (and replace) the statement.  */
 437   copy_tree_r (tp, walk_subtrees, NULL);
 438   if (block)
 439     {
 440       remap_block (&block, id);
 441       BIND_EXPR_BLOCK (*tp) = block;
 442     }
 443
 444   if (BIND_EXPR_VARS (*tp))
 445     /* This will remap a lot of the same decls again, but this should be
 446        harmless.  */
 447     BIND_EXPR_VARS (*tp) = remap_decls (BIND_EXPR_VARS (*tp), id);
 448 }
 449
 450 /* Called from copy_body via walk_tree.  DATA is really an `inline_data *'.  */
 451
 452 static tree
 453 copy_body_r (tree *tp, int *walk_subtrees, void *data)
 454 {
 455   inline_data *id = (inline_data *) data;
 456   tree fn = VARRAY_TOP_TREE (id->fns);
 457
 458 #if 0
 459   /* All automatic variables should have a DECL_CONTEXT indicating
 460      what function they come from.  */
 461   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 462       && DECL_NAMESPACE_SCOPE_P (*tp))
 463     if (! DECL_EXTERNAL (*tp) && ! TREE_STATIC (*tp))
 464       abort ();
 465 #endif
 466
 467   /* If this is a RETURN_EXPR, change it into a MODIFY_EXPR and a
 468      GOTO_EXPR with the RET_LABEL as its target.  */
 469   if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
 470     {
 471       tree return_stmt = *tp;
 472       tree goto_stmt;
 473
 474       /* Build the GOTO_EXPR.  */
 475       tree assignment = TREE_OPERAND (return_stmt, 0);
 476       goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
 477       TREE_USED (id->ret_label) = 1;
 478
 479       /* If we're returning something, just turn that into an
 480          assignment into the equivalent of the original
 481          RESULT_DECL.  */
 482       if (assignment)
 483         {
 484           /* Do not create a statement containing a naked RESULT_DECL.  */
 485           if (TREE_CODE (assignment) == RESULT_DECL)
 486             gimplify_stmt (&assignment);
 487
 488           *tp = build (BIND_EXPR, void_type_node, NULL, NULL, NULL);
 489           append_to_statement_list (assignment, &BIND_EXPR_BODY (*tp));
 490           append_to_statement_list (goto_stmt, &BIND_EXPR_BODY (*tp));
 491         }
 492       /* If we're not returning anything just do the jump.  */
 493       else
 494         *tp = goto_stmt;
 495     }
 496   /* Local variables and labels need to be replaced by equivalent
 497      variables.  We don't want to copy static variables; there's only
 498      one of those, no matter how many times we inline the containing
 499      function.  Similarly for globals from an outer function.  */
 500   else if (lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
 501     {
 502       tree new_decl;
 503
 504       /* Remap the declaration.  */
 505       new_decl = remap_decl (*tp, id);
 506       if (! new_decl)
 507         abort ();
 508       /* Replace this variable with the copy.  */
 509       STRIP_TYPE_NOPS (new_decl);
 510       *tp = new_decl;
 511     }
 512 #if 0
 513   else if (nonstatic_local_decl_p (*tp)
 514            && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
 515     abort ();
 516 #endif
 517   else if (TREE_CODE (*tp) == STATEMENT_LIST)
 518     copy_statement_list (tp);
 519   else if (TREE_CODE (*tp) == SAVE_EXPR)
 520     remap_save_expr (tp, id->decl_map, walk_subtrees);
 521   else if (TREE_CODE (*tp) == UNSAVE_EXPR)
 522     /* UNSAVE_EXPRs should not be generated until expansion time.  */
 523     abort ();
 524   else if (TREE_CODE (*tp) == BIND_EXPR)
 525     copy_bind_expr (tp, walk_subtrees, id);
 526   else if (TREE_CODE (*tp) == LABELED_BLOCK_EXPR)
 527     {
 528       /* We need a new copy of this labeled block; the EXIT_BLOCK_EXPR
 529          will refer to it, so save a copy ready for remapping.  We
 530          save it in the decl_map, although it isn't a decl.  */
 531       tree new_block = copy_node (*tp);
 532       insert_decl_map (id, *tp, new_block);
 533       *tp = new_block;
 534     }
 535   else if (TREE_CODE (*tp) == EXIT_BLOCK_EXPR)
 536     {
 537       splay_tree_node n
 538         = splay_tree_lookup (id->decl_map,
 539                              (splay_tree_key) TREE_OPERAND (*tp, 0));
 540       /* We _must_ have seen the enclosing LABELED_BLOCK_EXPR.  */
 541       if (! n)
 542         abort ();
 543       *tp = copy_node (*tp);
 544       TREE_OPERAND (*tp, 0) = (tree) n->value;
 545     }
 546   /* Types may need remapping as well.  */
 547   else if (TYPE_P (*tp))
 548     *tp = remap_type (*tp, id);
 549
 550   /* Otherwise, just copy the node.  Note that copy_tree_r already
 551      knows not to copy VAR_DECLs, etc., so this is safe.  */
 552   else
 553     {
 554       tree old_node = *tp;
 555
 556       if (TREE_CODE (*tp) == MODIFY_EXPR
 557           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 558           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 559               (TREE_OPERAND (*tp, 0), fn)))
 560         {
 561           /* Some assignments VAR = VAR; don't generate any rtl code
 562              and thus don't count as variable modification.  Avoid
 563              keeping bogosities like 0 = 0.  */
 564           tree decl = TREE_OPERAND (*tp, 0), value;
 565           splay_tree_node n;
 566
 567           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 568           if (n)
 569             {
 570               value = (tree) n->value;
 571               STRIP_TYPE_NOPS (value);
 572               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 573                 {
 574                   *tp = value;
 575                   return copy_body_r (tp, walk_subtrees, data);
 576                 }
 577             }
 578         }
 579       else if (TREE_CODE (*tp) == ADDR_EXPR
 580                && (lang_hooks.tree_inlining.auto_var_in_fn_p
 581                    (TREE_OPERAND (*tp, 0), fn)))
 582         {
 583           /* Get rid of &* from inline substitutions.  It can occur when
 584              someone takes the address of a parm or return slot passed by
 585              invisible reference.  */
 586           tree decl = TREE_OPERAND (*tp, 0), value;
 587           splay_tree_node n;
 588
 589           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 590           if (n)
 591             {
 592               value = (tree) n->value;
 593               if (TREE_CODE (value) == INDIRECT_REF)
 594                 {
 595                   if  (!lang_hooks.types_compatible_p
 596                        (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0))))
 597                     *tp = fold_convert (TREE_TYPE (*tp),
 598                                         TREE_OPERAND (value, 0));
 599                   else
 600                     *tp = TREE_OPERAND (value, 0);
 601
 602                   return copy_body_r (tp, walk_subtrees, data);
 603                 }
 604             }
 605         }
 606       else if (TREE_CODE (*tp) == INDIRECT_REF)
 607         {
 608           /* Get rid of *& from inline substitutions that can happen when a
 609              pointer argument is an ADDR_EXPR.  */
 610           tree decl = TREE_OPERAND (*tp, 0), value;
 611           splay_tree_node n;
 612
 613           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 614           if (n)
 615             {
 616               value = (tree) n->value;
 617               STRIP_NOPS (value);
 618               if (TREE_CODE (value) == ADDR_EXPR
 619                   && (lang_hooks.types_compatible_p
 620                       (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0)))))
 621                 {
 622                   *tp = TREE_OPERAND (value, 0);
 623                   return copy_body_r (tp, walk_subtrees, data);
 624                 }
 625             }
 626         }
 627
 628       copy_tree_r (tp, walk_subtrees, NULL);
 629
 630       if (TREE_CODE (*tp) == CALL_EXPR && id->node && get_callee_fndecl (*tp))
 631         {
 632           if (id->saving_p)
 633             {
 634               struct cgraph_node *node;
 635               struct cgraph_edge *edge;
 636
 637               for (node = id->node->next_clone; node; node = node->next_clone)
 638                 {
 639                   edge = cgraph_edge (node, old_node);
 640                   if (edge)
 641                     edge->call_expr = *tp;
 642                   else
 643                     abort ();
 644                 }
 645             }
 646           else
 647             {
 648               struct cgraph_edge *edge
 649                 = cgraph_edge (id->current_node, old_node);
 650
 651               if (edge)
 652                 cgraph_clone_edge (edge, id->node, *tp);
 653             }
 654         }
 655
 656       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 657
 658       /* The copied TARGET_EXPR has never been expanded, even if the
 659          original node was expanded already.  */
 660       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 661         {
 662           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 663           TREE_OPERAND (*tp, 3) = NULL_TREE;
 664         }
 665     }
 666
 667   /* Keep iterating.  */
 668   return NULL_TREE;
 669 }
 670
 671 /* Make a copy of the body of FN so that it can be inserted inline in
 672    another function.  */
 673
 674 static tree
 675 copy_body (inline_data *id)
 676 {
 677   tree body;
 678   tree fndecl = VARRAY_TOP_TREE (id->fns);
 679
 680   if (fndecl == current_function_decl
 681       && cfun->saved_tree)
 682     body = cfun->saved_tree;
 683   else
 684     body = DECL_SAVED_TREE (fndecl);
 685   walk_tree (&body, copy_body_r, id, NULL);
 686
 687   return body;
 688 }
 689
 690 static void
 691 setup_one_parameter (inline_data *id, tree p, tree value, tree fn,
 692                      tree *init_stmts, tree *vars, bool *gimplify_init_stmts_p)
 693 {
 694   tree init_stmt;
 695   tree var;
 696   tree var_sub;
 697
 698   /* If the parameter is never assigned to, we may not need to
 699      create a new variable here at all.  Instead, we may be able
 700      to just use the argument value.  */
 701   if (TREE_READONLY (p)
 702       && !TREE_ADDRESSABLE (p)
 703       && value && !TREE_SIDE_EFFECTS (value))
 704     {
 705       /* We can't risk substituting complex expressions.  They
 706          might contain variables that will be assigned to later.
 707          Theoretically, we could check the expression to see if
 708          all of the variables that determine its value are
 709          read-only, but we don't bother.  */
 710       /* We may produce non-gimple trees by adding NOPs or introduce
 711          invalid sharing when operand is not really constant.
 712          It is not big deal to prohibit constant propagation here as
 713          we will constant propagate in DOM1 pass anyway.  */
 714       if (is_gimple_min_invariant (value)
 715           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p)))
 716         {
 717           insert_decl_map (id, p, value);
 718           return;
 719         }
 720     }
 721
 722   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
 723      here since the type of this decl must be visible to the calling
 724      function. */
 725   var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 726
 727   /* See if the frontend wants to pass this by invisible reference.  If
 728      so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
 729      replace uses of the PARM_DECL with dereferences.  */
 730   if (TREE_TYPE (var) != TREE_TYPE (p)
 731       && POINTER_TYPE_P (TREE_TYPE (var))
 732       && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
 733     {
 734       insert_decl_map (id, var, var);
 735       var_sub = build1 (INDIRECT_REF, TREE_TYPE (p), var);
 736     }
 737   else
 738     var_sub = var;
 739
 740   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 741      that way, when the PARM_DECL is encountered, it will be
 742      automatically replaced by the VAR_DECL.  */
 743   insert_decl_map (id, p, var_sub);
 744
 745   /* Declare this new variable.  */
 746   TREE_CHAIN (var) = *vars;
 747   *vars = var;
 748
 749   /* Make gimplifier happy about this variable.  */
 750   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 751
 752   /* Even if P was TREE_READONLY, the new VAR should not be.
 753      In the original code, we would have constructed a
 754      temporary, and then the function body would have never
 755      changed the value of P.  However, now, we will be
 756      constructing VAR directly.  The constructor body may
 757      change its value multiple times as it is being
 758      constructed.  Therefore, it must not be TREE_READONLY;
 759      the back-end assumes that TREE_READONLY variable is
 760      assigned to only once.  */
 761   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 762     TREE_READONLY (var) = 0;
 763
 764   /* Initialize this VAR_DECL from the equivalent argument.  Convert
 765      the argument to the proper type in case it was promoted.  */
 766   if (value)
 767     {
 768       tree rhs = fold_convert (TREE_TYPE (var), value);
 769
 770       if (rhs == error_mark_node)
 771         return;
 772
 773       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
 774          keep our trees in gimple form.  */
 775       init_stmt = build (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
 776       append_to_statement_list (init_stmt, init_stmts);
 777
 778       /* If we did not create a gimple value and we did not create a gimple
 779          cast of a gimple value, then we will need to gimplify INIT_STMTS
 780          at the end.  Note that is_gimple_cast only checks the outer
 781          tree code, not its operand.  Thus the explicit check that it's
 782          operand is a gimple value.  */
 783       if (!is_gimple_val (rhs)
 784           && (!is_gimple_cast (rhs)
 785               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
 786         *gimplify_init_stmts_p = true;
 787     }
 788 }
 789
 790 /* Generate code to initialize the parameters of the function at the
 791    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 792
 793 static tree
 794 initialize_inlined_parameters (inline_data *id, tree args, tree static_chain,
 795                                tree fn, tree bind_expr)
 796 {
 797   tree init_stmts = NULL_TREE;
 798   tree parms;
 799   tree a;
 800   tree p;
 801   tree vars = NULL_TREE;
 802   bool gimplify_init_stmts_p = false;
 803   int argnum = 0;
 804
 805   /* Figure out what the parameters are.  */
 806   parms = DECL_ARGUMENTS (fn);
 807   if (fn == current_function_decl)
 808     parms = cfun->saved_args;
 809
 810   /* Loop through the parameter declarations, replacing each with an
 811      equivalent VAR_DECL, appropriately initialized.  */
 812   for (p = parms, a = args; p;
 813        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 814     {
 815       tree value;
 816
 817       ++argnum;
 818
 819       /* Find the initializer.  */
 820       value = lang_hooks.tree_inlining.convert_parm_for_inlining
 821               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
 822
 823       setup_one_parameter (id, p, value, fn, &init_stmts, &vars,
 824                            &gimplify_init_stmts_p);
 825     }
 826
 827   /* Evaluate trailing arguments.  */
 828   for (; a; a = TREE_CHAIN (a))
 829     {
 830       tree value = TREE_VALUE (a);
 831       append_to_statement_list (value, &init_stmts);
 832     }
 833
 834   /* Initialize the static chain.  */
 835   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
 836   if (p)
 837     {
 838       /* No static chain?  Seems like a bug in tree-nested.c.  */
 839       if (!static_chain)
 840         abort ();
 841
 842        setup_one_parameter (id, p, static_chain, fn, &init_stmts, &vars,
 843                             &gimplify_init_stmts_p);
 844     }
 845
 846   if (gimplify_init_stmts_p)
 847     gimplify_body (&init_stmts, current_function_decl);
 848
 849   declare_inline_vars (bind_expr, vars);
 850   return init_stmts;
 851 }
 852
 853 /* Declare a return variable to replace the RESULT_DECL for the function we
 854    are calling.  RETURN_SLOT_ADDR, if non-null, was a fake parameter that
 855    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
 856    the MODIFY_EXPR to which this call is the RHS.
 857
 858    The return value is a (possibly null) value that is the result of the
 859    function as seen by the callee.  *USE_P is a (possibly null) value that
 860    holds the result as seen by the caller.  */
 861
 862 static tree
 863 declare_return_variable (inline_data *id, tree return_slot_addr,
 864                          tree modify_dest, tree *use_p)
 865 {
 866   tree callee = VARRAY_TOP_TREE (id->fns);
 867   tree caller = VARRAY_TREE (id->fns, 0);
 868   tree result = DECL_RESULT (callee);
 869   tree callee_type = TREE_TYPE (result);
 870   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
 871   tree var, use;
 872
 873   /* We don't need to do anything for functions that don't return
 874      anything.  */
 875   if (!result || VOID_TYPE_P (callee_type))
 876     {
 877       *use_p = NULL_TREE;
 878       return NULL_TREE;
 879     }
 880
 881   /* If there was a return slot, then the return value the the
 882      dereferenced address of that object.  */
 883   if (return_slot_addr)
 884     {
 885       /* The front end shouldn't have used both return_slot_addr and
 886          a modify expression.  */
 887       if (modify_dest)
 888         abort ();
 889       var = build_fold_indirect_ref (return_slot_addr);
 890       use = NULL;
 891       goto done;
 892     }
 893
 894   /* All types requiring non-trivial constructors should have been handled.  */
 895   if (TREE_ADDRESSABLE (callee_type))
 896     abort ();
 897
 898   /* Attempt to avoid creating a new temporary variable.  */
 899   if (modify_dest)
 900     {
 901       bool use_it = false;
 902
 903       /* We can't use MODIFY_DEST if there's type promotion involved.  */
 904       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
 905         use_it = false;
 906
 907       /* ??? If we're assigning to a variable sized type, then we must
 908          reuse the destination variable, because we've no good way to
 909          create variable sized temporaries at this point.  */
 910       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
 911         use_it = true;
 912
 913       /* If the callee cannot possibly modify MODIFY_DEST, then we can
 914          reuse it as the result of the call directly.  Don't do this if
 915          it would promote MODIFY_DEST to addressable.  */
 916       else if (!TREE_STATIC (modify_dest)
 917                && !TREE_ADDRESSABLE (modify_dest)
 918                && !TREE_ADDRESSABLE (result))
 919         use_it = true;
 920
 921       if (use_it)
 922         {
 923           var = modify_dest;
 924           use = NULL;
 925           goto done;
 926         }
 927     }
 928
 929   if (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) != INTEGER_CST)
 930     abort ();
 931
 932   var = copy_decl_for_inlining (result, callee, caller);
 933   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 934   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
 935     = tree_cons (NULL_TREE, var,
 936                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
 937
 938   /* Do not have the rest of GCC warn about this variable as it should
 939      not be visible to the user.   */
 940   TREE_NO_WARNING (var) = 1;
 941
 942   /* Build the use expr.  If the return type of the function was
 943      promoted, convert it back to the expected type.  */
 944   use = var;
 945   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
 946     use = fold_convert (caller_type, var);
 947
 948  done:
 949   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 950      way, when the RESULT_DECL is encountered, it will be
 951      automatically replaced by the VAR_DECL.  */
 952   insert_decl_map (id, result, var);
 953
 954   /* Remember this so we can ignore it in remap_decls.  */
 955   id->retvar = var;
 956
 957   *use_p = use;
 958   return var;
 959 }
 960
 961 /* Returns nonzero if a function can be inlined as a tree.  */
 962
 963 bool
 964 tree_inlinable_function_p (tree fn)
 965 {
 966   return inlinable_function_p (fn);
 967 }
 968
 969 static const char *inline_forbidden_reason;
 970
 971 static tree
 972 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
 973                       void *fnp)
 974 {
 975   tree node = *nodep;
 976   tree fn = (tree) fnp;
 977   tree t;
 978
 979   switch (TREE_CODE (node))
 980     {
 981     case CALL_EXPR:
 982       /* Refuse to inline alloca call unless user explicitly forced so as
 983          this may change program's memory overhead drastically when the
 984          function using alloca is called in loop.  In GCC present in
 985          SPEC2000 inlining into schedule_block cause it to require 2GB of
 986          RAM instead of 256MB.  */
 987       if (alloca_call_p (node)
 988           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
 989         {
 990           inline_forbidden_reason
 991             = N_("%Jfunction '%F' can never be inlined because it uses "
 992                  "alloca (override using the always_inline attribute)");
 993           return node;
 994         }
 995       t = get_callee_fndecl (node);
 996       if (! t)
 997         break;
 998
 999       /* We cannot inline functions that call setjmp.  */
1000       if (setjmp_call_p (t))
1001         {
1002           inline_forbidden_reason
1003             = N_("%Jfunction '%F' can never be inlined because it uses setjmp");
1004           return node;
1005         }
1006
1007       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
1008         switch (DECL_FUNCTION_CODE (t))
1009           {
1010             /* We cannot inline functions that take a variable number of
1011                arguments.  */
1012           case BUILT_IN_VA_START:
1013           case BUILT_IN_STDARG_START:
1014           case BUILT_IN_NEXT_ARG:
1015           case BUILT_IN_VA_END:
1016             inline_forbidden_reason
1017               = N_("%Jfunction '%F' can never be inlined because it "
1018                    "uses variable argument lists");
1019             return node;
1020
1021           case BUILT_IN_LONGJMP:
1022             /* We can't inline functions that call __builtin_longjmp at
1023                all.  The non-local goto machinery really requires the
1024                destination be in a different function.  If we allow the
1025                function calling __builtin_longjmp to be inlined into the
1026                function calling __builtin_setjmp, Things will Go Awry.  */
1027             inline_forbidden_reason
1028               = N_("%Jfunction '%F' can never be inlined because "
1029                    "it uses setjmp-longjmp exception handling");
1030             return node;
1031
1032           case BUILT_IN_NONLOCAL_GOTO:
1033             /* Similarly.  */
1034             inline_forbidden_reason
1035               = N_("%Jfunction '%F' can never be inlined because "
1036                    "it uses non-local goto");
1037             return node;
1038
1039           default:
1040             break;
1041           }
1042       break;
1043
1044     case BIND_EXPR:
1045       for (t = BIND_EXPR_VARS (node); t ; t = TREE_CHAIN (t))
1046         {
1047           /* We cannot inline functions that contain other functions.  */
1048           if (TREE_CODE (t) == FUNCTION_DECL && DECL_INITIAL (t))
1049             {
1050               inline_forbidden_reason
1051                 = N_("%Jfunction '%F' can never be inlined "
1052                      "because it contains a nested function");
1053               return node;
1054             }
1055         }
1056       break;
1057
1058     case GOTO_EXPR:
1059       t = TREE_OPERAND (node, 0);
1060
1061       /* We will not inline a function which uses computed goto.  The
1062          addresses of its local labels, which may be tucked into
1063          global storage, are of course not constant across
1064          instantiations, which causes unexpected behavior.  */
1065       if (TREE_CODE (t) != LABEL_DECL)
1066         {
1067           inline_forbidden_reason
1068             = N_("%Jfunction '%F' can never be inlined "
1069                  "because it contains a computed goto");
1070           return node;
1071         }
1072       break;
1073
1074     case LABEL_EXPR:
1075       t = TREE_OPERAND (node, 0);
1076       if (DECL_NONLOCAL (t))
1077         {
1078           /* We cannot inline a function that receives a non-local goto
1079              because we cannot remap the destination label used in the
1080              function that is performing the non-local goto.  */
1081           inline_forbidden_reason
1082             = N_("%Jfunction '%F' can never be inlined "
1083                  "because it receives a non-local goto");
1084           return node;
1085         }
1086       break;
1087
1088     case RECORD_TYPE:
1089     case UNION_TYPE:
1090       /* We cannot inline a function of the form
1091
1092            void F (int i) { struct S { int ar[i]; } s; }
1093
1094          Attempting to do so produces a catch-22.
1095          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1096          UNION_TYPE nodes, then it goes into infinite recursion on a
1097          structure containing a pointer to its own type.  If it doesn't,
1098          then the type node for S doesn't get adjusted properly when
1099          F is inlined, and we abort in find_function_data.  */
1100       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1101         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1102           {
1103             inline_forbidden_reason
1104               = N_("%Jfunction '%F' can never be inlined "
1105                    "because it uses variable sized variables");
1106             return node;
1107           }
1108
1109     default:
1110       break;
1111     }
1112
1113   return NULL_TREE;
1114 }
1115
1116 /* Return subexpression representing possible alloca call, if any.  */
1117 static tree
1118 inline_forbidden_p (tree fndecl)
1119 {
1120   location_t saved_loc = input_location;
1121   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1122                                            inline_forbidden_p_1, fndecl);
1123
1124   input_location = saved_loc;
1125   return ret;
1126 }
1127
1128 /* Returns nonzero if FN is a function that does not have any
1129    fundamental inline blocking properties.  */
1130
1131 static bool
1132 inlinable_function_p (tree fn)
1133 {
1134   bool inlinable = true;
1135
1136   /* If we've already decided this function shouldn't be inlined,
1137      there's no need to check again.  */
1138   if (DECL_UNINLINABLE (fn))
1139     return false;
1140
1141   /* See if there is any language-specific reason it cannot be
1142      inlined.  (It is important that this hook be called early because
1143      in C++ it may result in template instantiation.)
1144      If the function is not inlinable for language-specific reasons,
1145      it is left up to the langhook to explain why.  */
1146   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1147
1148   /* If we don't have the function body available, we can't inline it.
1149      However, this should not be recorded since we also get here for
1150      forward declared inline functions.  Therefore, return at once.  */
1151   if (!DECL_SAVED_TREE (fn))
1152     return false;
1153
1154   /* If we're not inlining at all, then we cannot inline this function.  */
1155   else if (!flag_inline_trees)
1156     inlinable = false;
1157
1158   /* Only try to inline functions if DECL_INLINE is set.  This should be
1159      true for all functions declared `inline', and for all other functions
1160      as well with -finline-functions.
1161
1162      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1163      it's the front-end that must set DECL_INLINE in this case, because
1164      dwarf2out loses if a function that does not have DECL_INLINE set is
1165      inlined anyway.  That is why we have both DECL_INLINE and
1166      DECL_DECLARED_INLINE_P.  */
1167   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1168             here should be redundant.  */
1169   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1170     inlinable = false;
1171
1172   else if (inline_forbidden_p (fn))
1173     {
1174       /* See if we should warn about uninlinable functions.  Previously,
1175          some of these warnings would be issued while trying to expand
1176          the function inline, but that would cause multiple warnings
1177          about functions that would for example call alloca.  But since
1178          this a property of the function, just one warning is enough.
1179          As a bonus we can now give more details about the reason why a
1180          function is not inlinable.
1181          We only warn for functions declared `inline' by the user.  */
1182       bool do_warning = (warn_inline
1183                          && DECL_INLINE (fn)
1184                          && DECL_DECLARED_INLINE_P (fn)
1185                          && !DECL_IN_SYSTEM_HEADER (fn));
1186
1187       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1188         sorry (inline_forbidden_reason, fn, fn);
1189       else if (do_warning)
1190         warning (inline_forbidden_reason, fn, fn);
1191
1192       inlinable = false;
1193     }
1194
1195   /* Squirrel away the result so that we don't have to check again.  */
1196   DECL_UNINLINABLE (fn) = !inlinable;
1197
1198   return inlinable;
1199 }
1200
1201 /* Used by estimate_num_insns.  Estimate number of instructions seen
1202    by given statement.  */
1203
1204 static tree
1205 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1206 {
1207   int *count = data;
1208   tree x = *tp;
1209
1210   if (TYPE_P (x) || DECL_P (x))
1211     {
1212       *walk_subtrees = 0;
1213       return NULL;
1214     }
1215   /* Assume that constants and references counts nothing.  These should
1216      be majorized by amount of operations among them we count later
1217      and are common target of CSE and similar optimizations.  */
1218   else if (TREE_CODE_CLASS (TREE_CODE (x)) == 'c'
1219            || TREE_CODE_CLASS (TREE_CODE (x)) == 'r')
1220     return NULL;
1221
1222   switch (TREE_CODE (x))
1223     {
1224     /* Containers have no cost.  */
1225     case TREE_LIST:
1226     case TREE_VEC:
1227     case BLOCK:
1228     case COMPONENT_REF:
1229     case BIT_FIELD_REF:
1230     case INDIRECT_REF:
1231     case ARRAY_REF:
1232     case ARRAY_RANGE_REF:
1233     case OBJ_TYPE_REF:
1234     case EXC_PTR_EXPR: /* ??? */
1235     case FILTER_EXPR: /* ??? */
1236     case COMPOUND_EXPR:
1237     case BIND_EXPR:
1238     case LABELED_BLOCK_EXPR:
1239     case WITH_CLEANUP_EXPR:
1240     case NOP_EXPR:
1241     case VIEW_CONVERT_EXPR:
1242     case SAVE_EXPR:
1243     case UNSAVE_EXPR:
1244     case ADDR_EXPR:
1245     case COMPLEX_EXPR:
1246     case EXIT_BLOCK_EXPR:
1247     case CASE_LABEL_EXPR:
1248     case SSA_NAME:
1249     case CATCH_EXPR:
1250     case EH_FILTER_EXPR:
1251     case STATEMENT_LIST:
1252     case ERROR_MARK:
1253     case NON_LVALUE_EXPR:
1254     case ENTRY_VALUE_EXPR:
1255     case FDESC_EXPR:
1256     case VA_ARG_EXPR:
1257     case TRY_CATCH_EXPR:
1258     case TRY_FINALLY_EXPR:
1259     case LABEL_EXPR:
1260     case GOTO_EXPR:
1261     case RETURN_EXPR:
1262     case EXIT_EXPR:
1263     case LOOP_EXPR:
1264     case PHI_NODE:
1265     case WITH_SIZE_EXPR:
1266       break;
1267
1268     /* We don't account constants for now.  Assume that the cost is amortized
1269        by operations that do use them.  We may re-consider this decision once
1270        we are able to optimize the tree before estimating it's size and break
1271        out static initializers.  */
1272     case IDENTIFIER_NODE:
1273     case INTEGER_CST:
1274     case REAL_CST:
1275     case COMPLEX_CST:
1276     case VECTOR_CST:
1277     case STRING_CST:
1278       *walk_subtrees = 0;
1279       return NULL;
1280
1281     /* Recognize assignments of large structures and constructors of
1282        big arrays.  */
1283     case INIT_EXPR:
1284     case MODIFY_EXPR:
1285       x = TREE_OPERAND (x, 0);
1286       /* FALLTHRU */
1287     case TARGET_EXPR:
1288     case CONSTRUCTOR:
1289       {
1290         HOST_WIDE_INT size;
1291
1292         size = int_size_in_bytes (TREE_TYPE (x));
1293
1294         if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1295           *count += 10;
1296         else
1297           *count += ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1298       }
1299       break;
1300
1301       /* Assign cost of 1 to usual operations.
1302          ??? We may consider mapping RTL costs to this.  */
1303     case COND_EXPR:
1304
1305     case PLUS_EXPR:
1306     case MINUS_EXPR:
1307     case MULT_EXPR:
1308
1309     case FIX_TRUNC_EXPR:
1310     case FIX_CEIL_EXPR:
1311     case FIX_FLOOR_EXPR:
1312     case FIX_ROUND_EXPR:
1313
1314     case NEGATE_EXPR:
1315     case FLOAT_EXPR:
1316     case MIN_EXPR:
1317     case MAX_EXPR:
1318     case ABS_EXPR:
1319
1320     case LSHIFT_EXPR:
1321     case RSHIFT_EXPR:
1322     case LROTATE_EXPR:
1323     case RROTATE_EXPR:
1324
1325     case BIT_IOR_EXPR:
1326     case BIT_XOR_EXPR:
1327     case BIT_AND_EXPR:
1328     case BIT_NOT_EXPR:
1329
1330     case TRUTH_ANDIF_EXPR:
1331     case TRUTH_ORIF_EXPR:
1332     case TRUTH_AND_EXPR:
1333     case TRUTH_OR_EXPR:
1334     case TRUTH_XOR_EXPR:
1335     case TRUTH_NOT_EXPR:
1336
1337     case LT_EXPR:
1338     case LE_EXPR:
1339     case GT_EXPR:
1340     case GE_EXPR:
1341     case EQ_EXPR:
1342     case NE_EXPR:
1343     case ORDERED_EXPR:
1344     case UNORDERED_EXPR:
1345
1346     case UNLT_EXPR:
1347     case UNLE_EXPR:
1348     case UNGT_EXPR:
1349     case UNGE_EXPR:
1350     case UNEQ_EXPR:
1351     case LTGT_EXPR:
1352
1353     case CONVERT_EXPR:
1354
1355     case CONJ_EXPR:
1356
1357     case PREDECREMENT_EXPR:
1358     case PREINCREMENT_EXPR:
1359     case POSTDECREMENT_EXPR:
1360     case POSTINCREMENT_EXPR:
1361
1362     case SWITCH_EXPR:
1363
1364     case ASM_EXPR:
1365
1366     case RESX_EXPR:
1367       *count += 1;
1368       break;
1369
1370     /* Few special cases of expensive operations.  This is useful
1371        to avoid inlining on functions having too many of these.  */
1372     case TRUNC_DIV_EXPR:
1373     case CEIL_DIV_EXPR:
1374     case FLOOR_DIV_EXPR:
1375     case ROUND_DIV_EXPR:
1376     case EXACT_DIV_EXPR:
1377     case TRUNC_MOD_EXPR:
1378     case CEIL_MOD_EXPR:
1379     case FLOOR_MOD_EXPR:
1380     case ROUND_MOD_EXPR:
1381     case RDIV_EXPR:
1382       *count += 10;
1383       break;
1384     case CALL_EXPR:
1385       {
1386         tree decl = get_callee_fndecl (x);
1387
1388         if (decl && DECL_BUILT_IN (decl))
1389           switch (DECL_FUNCTION_CODE (decl))
1390             {
1391             case BUILT_IN_CONSTANT_P:
1392               *walk_subtrees = 0;
1393               return NULL_TREE;
1394             case BUILT_IN_EXPECT:
1395               return NULL_TREE;
1396             default:
1397               break;
1398             }
1399         *count += 10;
1400         break;
1401       }
1402     default:
1403       /* Abort here se we know we don't miss any nodes.  */
1404       abort ();
1405     }
1406   return NULL;
1407 }
1408
1409 /* Estimate number of instructions that will be created by expanding EXPR.  */
1410
1411 int
1412 estimate_num_insns (tree expr)
1413 {
1414   int num = 0;
1415   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1416   return num;
1417 }
1418
1419 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1420
1421 static tree
1422 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1423 {
1424   inline_data *id;
1425   tree t;
1426   tree expr;
1427   tree stmt;
1428   tree use_retvar;
1429   tree decl;
1430   tree fn;
1431   tree arg_inits;
1432   tree *inlined_body;
1433   splay_tree st;
1434   tree args;
1435   tree return_slot_addr;
1436   tree modify_dest;
1437   location_t saved_location;
1438   struct cgraph_edge *edge;
1439   const char *reason;
1440
1441   /* See what we've got.  */
1442   id = (inline_data *) data;
1443   t = *tp;
1444
1445   /* Set input_location here so we get the right instantiation context
1446      if we call instantiate_decl from inlinable_function_p.  */
1447   saved_location = input_location;
1448   if (EXPR_HAS_LOCATION (t))
1449     input_location = EXPR_LOCATION (t);
1450
1451   /* Recurse, but letting recursive invocations know that we are
1452      inside the body of a TARGET_EXPR.  */
1453   if (TREE_CODE (*tp) == TARGET_EXPR)
1454     {
1455 #if 0
1456       int i, len = first_rtl_op (TARGET_EXPR);
1457
1458       /* We're walking our own subtrees.  */
1459       *walk_subtrees = 0;
1460
1461       /* Actually walk over them.  This loop is the body of
1462          walk_trees, omitting the case where the TARGET_EXPR
1463          itself is handled.  */
1464       for (i = 0; i < len; ++i)
1465         {
1466           if (i == 2)
1467             ++id->in_target_cleanup_p;
1468           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1469                      id->tree_pruner);
1470           if (i == 2)
1471             --id->in_target_cleanup_p;
1472         }
1473
1474       goto egress;
1475 #endif
1476     }
1477
1478   if (TYPE_P (t))
1479     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1480        them should not be expanded.  This can happen if the type is a
1481        dynamic array type, for example.  */
1482     *walk_subtrees = 0;
1483
1484   /* From here on, we're only interested in CALL_EXPRs.  */
1485   if (TREE_CODE (t) != CALL_EXPR)
1486     goto egress;
1487
1488   /* First, see if we can figure out what function is being called.
1489      If we cannot, then there is no hope of inlining the function.  */
1490   fn = get_callee_fndecl (t);
1491   if (!fn)
1492     goto egress;
1493
1494   /* Turn forward declarations into real ones.  */
1495   fn = cgraph_node (fn)->decl;
1496
1497   /* If fn is a declaration of a function in a nested scope that was
1498      globally declared inline, we don't set its DECL_INITIAL.
1499      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1500      C++ front-end uses it for cdtors to refer to their internal
1501      declarations, that are not real functions.  Fortunately those
1502      don't have trees to be saved, so we can tell by checking their
1503      DECL_SAVED_TREE.  */
1504   if (! DECL_INITIAL (fn)
1505       && DECL_ABSTRACT_ORIGIN (fn)
1506       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1507     fn = DECL_ABSTRACT_ORIGIN (fn);
1508
1509   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1510      Kill this check once this is fixed.  */
1511   if (!id->current_node->analyzed)
1512     goto egress;
1513
1514   edge = cgraph_edge (id->current_node, t);
1515
1516   /* Constant propagation on argument done during previous inlining
1517      may create new direct call.  Produce an edge for it.  */
1518   if (!edge)
1519     {
1520       struct cgraph_node *dest = cgraph_node (fn);
1521
1522       /* We have missing edge in the callgraph.  This can happen in one case
1523          where previous inlining turned indirect call into direct call by
1524          constant propagating arguments.  In all other cases we hit a bug
1525          (incorrect node sharing is most common reason for missing edges.  */
1526       if (!dest->needed)
1527         abort ();
1528       cgraph_create_edge (id->node, dest, t)->inline_failed
1529         = N_("originally indirect function call not considered for inlining");
1530       goto egress;
1531     }
1532
1533   /* Don't try to inline functions that are not well-suited to
1534      inlining.  */
1535   if (!cgraph_inline_p (edge, &reason))
1536     {
1537       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1538         {
1539           sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1540           sorry ("called from here");
1541         }
1542       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1543                && !DECL_IN_SYSTEM_HEADER (fn)
1544                && strlen (reason))
1545         {
1546           warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1547           warning ("called from here");
1548         }
1549       goto egress;
1550     }
1551
1552 #ifdef ENABLE_CHECKING
1553   if (edge->callee->decl != id->node->decl)
1554     verify_cgraph_node (edge->callee);
1555 #endif
1556
1557   if (! lang_hooks.tree_inlining.start_inlining (fn))
1558     goto egress;
1559
1560   /* Build a block containing code to initialize the arguments, the
1561      actual inline expansion of the body, and a label for the return
1562      statements within the function to jump to.  The type of the
1563      statement expression is the return type of the function call.  */
1564   stmt = NULL;
1565   expr = build (BIND_EXPR, void_type_node, NULL_TREE,
1566                 stmt, make_node (BLOCK));
1567   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1568
1569   /* Local declarations will be replaced by their equivalents in this
1570      map.  */
1571   st = id->decl_map;
1572   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1573                                  NULL, NULL);
1574
1575   /* Initialize the parameters.  */
1576   args = TREE_OPERAND (t, 1);
1577   return_slot_addr = NULL_TREE;
1578   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1579     {
1580       return_slot_addr = TREE_VALUE (args);
1581       args = TREE_CHAIN (args);
1582       TREE_TYPE (expr) = void_type_node;
1583     }
1584
1585   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1586                                              fn, expr);
1587   if (arg_inits)
1588     {
1589       /* Expand any inlined calls in the initializers.  Do this before we
1590          push FN on the stack of functions we are inlining; we want to
1591          inline calls to FN that appear in the initializers for the
1592          parameters.
1593
1594          Note we need to save and restore the saved tree statement iterator
1595          to avoid having it clobbered by expand_calls_inline.  */
1596       tree_stmt_iterator save_tsi;
1597
1598       save_tsi = id->tsi;
1599       expand_calls_inline (&arg_inits, id);
1600       id->tsi = save_tsi;
1601
1602       /* And add them to the tree.  */
1603       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1604     }
1605
1606   /* Record the function we are about to inline so that we can avoid
1607      recursing into it.  */
1608   VARRAY_PUSH_TREE (id->fns, fn);
1609
1610   /* Record the function we are about to inline if optimize_function
1611      has not been called on it yet and we don't have it in the list.  */
1612   if (! DECL_INLINED_FNS (fn))
1613     {
1614       int i;
1615
1616       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1617         if (VARRAY_TREE (id->inlined_fns, i) == fn)
1618           break;
1619       if (i < 0)
1620         VARRAY_PUSH_TREE (id->inlined_fns, fn);
1621     }
1622
1623   /* Return statements in the function body will be replaced by jumps
1624      to the RET_LABEL.  */
1625   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1626   DECL_ARTIFICIAL (id->ret_label) = 1;
1627   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1628   insert_decl_map (id, id->ret_label, id->ret_label);
1629
1630   if (! DECL_INITIAL (fn)
1631       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
1632     abort ();
1633
1634   /* Find the lhs to which the result of this call is assigned.  */
1635   modify_dest = tsi_stmt (id->tsi);
1636   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1637     modify_dest = TREE_OPERAND (modify_dest, 0);
1638   else
1639     modify_dest = NULL;
1640
1641   /* Declare the return variable for the function.  */
1642   decl = declare_return_variable (id, return_slot_addr,
1643                                   modify_dest, &use_retvar);
1644
1645   /* After we've initialized the parameters, we insert the body of the
1646      function itself.  */
1647   {
1648     struct cgraph_node *old_node = id->current_node;
1649
1650     id->current_node = edge->callee;
1651     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1652     id->current_node = old_node;
1653   }
1654   inlined_body = &BIND_EXPR_BODY (expr);
1655
1656   /* After the body of the function comes the RET_LABEL.  This must come
1657      before we evaluate the returned value below, because that evaluation
1658      may cause RTL to be generated.  */
1659   if (TREE_USED (id->ret_label))
1660     {
1661       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1662       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1663     }
1664
1665   /* Clean up.  */
1666   splay_tree_delete (id->decl_map);
1667   id->decl_map = st;
1668
1669   /* The new expression has side-effects if the old one did.  */
1670   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1671
1672   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1673
1674   /* If the inlined function returns a result that we care about,
1675      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1676      the call was a standalone statement and we can just replace it
1677      with the BIND_EXPR inline representation of the called function.  */
1678   if (!use_retvar || !modify_dest)
1679     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1680   else
1681     *tp = use_retvar;
1682
1683   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1684      the call if it is to a "const" function.  Thus the copy of
1685      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1686      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1687      "const" function.
1688
1689      Unfortunately, that is wrong as inlining the function can create/expose
1690      interesting side effects (such as setting of a return value).
1691
1692      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1693      the toplevel expression.  */
1694   recalculate_side_effects (expr);
1695
1696   /* Update callgraph if needed.  */
1697   cgraph_remove_node (edge->callee);
1698
1699   /* Recurse into the body of the just inlined function.  */
1700   expand_calls_inline (inlined_body, id);
1701   VARRAY_POP (id->fns);
1702
1703   /* Don't walk into subtrees.  We've already handled them above.  */
1704   *walk_subtrees = 0;
1705
1706   lang_hooks.tree_inlining.end_inlining (fn);
1707
1708   /* Keep iterating.  */
1709  egress:
1710   input_location = saved_location;
1711   return NULL_TREE;
1712 }
1713
1714 static void
1715 expand_calls_inline (tree *stmt_p, inline_data *id)
1716 {
1717   tree stmt = *stmt_p;
1718   enum tree_code code = TREE_CODE (stmt);
1719   int dummy;
1720
1721   switch (code)
1722     {
1723     case STATEMENT_LIST:
1724       {
1725         tree_stmt_iterator i;
1726         tree new;
1727
1728         for (i = tsi_start (stmt); !tsi_end_p (i); )
1729           {
1730             id->tsi = i;
1731             expand_calls_inline (tsi_stmt_ptr (i), id);
1732
1733             new = tsi_stmt (i);
1734             if (TREE_CODE (new) == STATEMENT_LIST)
1735               {
1736                 tsi_link_before (&i, new, TSI_SAME_STMT);
1737                 tsi_delink (&i);
1738               }
1739             else
1740               tsi_next (&i);
1741           }
1742       }
1743       break;
1744
1745     case COND_EXPR:
1746       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1747       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1748       break;
1749
1750     case CATCH_EXPR:
1751       expand_calls_inline (&CATCH_BODY (stmt), id);
1752       break;
1753
1754     case EH_FILTER_EXPR:
1755       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1756       break;
1757
1758     case TRY_CATCH_EXPR:
1759     case TRY_FINALLY_EXPR:
1760       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1761       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1762       break;
1763
1764     case BIND_EXPR:
1765       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1766       break;
1767
1768     case COMPOUND_EXPR:
1769       /* We're gimple.  We should have gotten rid of all these.  */
1770       abort ();
1771
1772     case RETURN_EXPR:
1773       stmt_p = &TREE_OPERAND (stmt, 0);
1774       stmt = *stmt_p;
1775       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1776         break;
1777
1778       /* FALLTHRU */
1779
1780     case MODIFY_EXPR:
1781       stmt_p = &TREE_OPERAND (stmt, 1);
1782       stmt = *stmt_p;
1783       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1784         {
1785           stmt_p = &TREE_OPERAND (stmt, 0);
1786           stmt = *stmt_p;
1787         }
1788       if (TREE_CODE (stmt) != CALL_EXPR)
1789         break;
1790
1791       /* FALLTHRU */
1792
1793     case CALL_EXPR:
1794       expand_call_inline (stmt_p, &dummy, id);
1795       break;
1796
1797     default:
1798       break;
1799     }
1800 }
1801
1802 /* Expand calls to inline functions in the body of FN.  */
1803
1804 void
1805 optimize_inline_calls (tree fn)
1806 {
1807   inline_data id;
1808   tree prev_fn;
1809   tree ifn;
1810
1811   /* There is no point in performing inlining if errors have already
1812      occurred -- and we might crash if we try to inline invalid
1813      code.  */
1814   if (errorcount || sorrycount)
1815     return;
1816
1817   /* Clear out ID.  */
1818   memset (&id, 0, sizeof (id));
1819
1820   id.current_node = id.node = cgraph_node (fn);
1821   /* Don't allow recursion into FN.  */
1822   VARRAY_TREE_INIT (id.fns, 32, "fns");
1823   VARRAY_PUSH_TREE (id.fns, fn);
1824   /* Or any functions that aren't finished yet.  */
1825   prev_fn = NULL_TREE;
1826   if (current_function_decl)
1827     {
1828       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1829       prev_fn = current_function_decl;
1830     }
1831
1832   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1833
1834   /* Create the list of functions this call will inline.  */
1835   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1836
1837   /* Keep track of the low-water mark, i.e., the point where the first
1838      real inlining is represented in ID.FNS.  */
1839   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1840
1841   /* Replace all calls to inline functions with the bodies of those
1842      functions.  */
1843   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1844   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1845
1846   /* Clean up.  */
1847   htab_delete (id.tree_pruner);
1848   ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1849   if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1850     memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1851             VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1852   DECL_INLINED_FNS (fn) = ifn;
1853
1854 #ifdef ENABLE_CHECKING
1855     {
1856       struct cgraph_edge *e;
1857
1858       verify_cgraph_node (id.node);
1859
1860       /* Double check that we inlined everything we are supposed to inline.  */
1861       for (e = id.node->callees; e; e = e->next_callee)
1862         if (!e->inline_failed)
1863           abort ();
1864     }
1865 #endif
1866 }
1867
1868 /* FN is a function that has a complete body, and CLONE is a function whose
1869    body is to be set to a copy of FN, mapping argument declarations according
1870    to the ARG_MAP splay_tree.  */
1871
1872 void
1873 clone_body (tree clone, tree fn, void *arg_map)
1874 {
1875   inline_data id;
1876
1877   /* Clone the body, as if we were making an inline call.  But, remap the
1878      parameters in the callee to the parameters of caller.  If there's an
1879      in-charge parameter, map it to an appropriate constant.  */
1880   memset (&id, 0, sizeof (id));
1881   VARRAY_TREE_INIT (id.fns, 2, "fns");
1882   VARRAY_PUSH_TREE (id.fns, clone);
1883   VARRAY_PUSH_TREE (id.fns, fn);
1884   id.decl_map = (splay_tree)arg_map;
1885
1886   /* Cloning is treated slightly differently from inlining.  Set
1887      CLONING_P so that it's clear which operation we're performing.  */
1888   id.cloning_p = true;
1889
1890   /* Actually copy the body.  */
1891   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1892 }
1893
1894 /* Save duplicate of body in FN.  MAP is used to pass around splay tree
1895    used to update arguments in restore_body.  */
1896 tree
1897 save_body (tree fn, tree *arg_copy)
1898 {
1899   inline_data id;
1900   tree body, *parg;
1901
1902   memset (&id, 0, sizeof (id));
1903   VARRAY_TREE_INIT (id.fns, 1, "fns");
1904   VARRAY_PUSH_TREE (id.fns, fn);
1905   id.node = cgraph_node (fn);
1906   id.saving_p = true;
1907   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1908   *arg_copy = DECL_ARGUMENTS (fn);
1909
1910   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1911     {
1912       tree new = copy_node (*parg);
1913
1914       lang_hooks.dup_lang_specific_decl (new);
1915       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1916       insert_decl_map (&id, *parg, new);
1917       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1918       *parg = new;
1919     }
1920
1921   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1922
1923   /* Actually copy the body.  */
1924   body = copy_body (&id);
1925
1926   /* Clean up.  */
1927   splay_tree_delete (id.decl_map);
1928   return body;
1929 }
1930
1931 #define WALK_SUBTREE(NODE)                              \
1932   do                                                    \
1933     {                                                   \
1934       result = walk_tree (&(NODE), func, data, htab);   \
1935       if (result)                                       \
1936         return result;                                  \
1937     }                                                   \
1938   while (0)
1939
1940 /* This is a subroutine of walk_tree that walks field of TYPE that are to
1941    be walked whenever a type is seen in the tree.  Rest of operands and return
1942    value are as for walk_tree.  */
1943
1944 static tree
1945 walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
1946 {
1947   tree result = NULL_TREE;
1948
1949   switch (TREE_CODE (type))
1950     {
1951     case POINTER_TYPE:
1952     case REFERENCE_TYPE:
1953       /* We have to worry about mutually recursive pointers.  These can't
1954          be written in C.  They can in Ada.  It's pathlogical, but
1955          there's an ACATS test (c38102a) that checks it.  Deal with this
1956          by checking if we're pointing to another pointer, that one
1957          points to another pointer, that one does too, and we have no htab.
1958          If so, get a hash table.  We check three levels deep to avoid
1959          the cost of the hash table if we don't need one.  */
1960       if (POINTER_TYPE_P (TREE_TYPE (type))
1961           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
1962           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
1963           && !htab)
1964         {
1965           result = walk_tree_without_duplicates (&TREE_TYPE (type),
1966                                                  func, data);
1967           if (result)
1968             return result;
1969
1970           break;
1971         }
1972
1973       /* ... fall through ... */
1974
1975     case COMPLEX_TYPE:
1976       WALK_SUBTREE (TREE_TYPE (type));
1977       break;
1978
1979     case METHOD_TYPE:
1980       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
1981
1982       /* Fall through.  */
1983
1984     case FUNCTION_TYPE:
1985       WALK_SUBTREE (TREE_TYPE (type));
1986       {
1987         tree arg;
1988
1989         /* We never want to walk into default arguments.  */
1990         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
1991           WALK_SUBTREE (TREE_VALUE (arg));
1992       }
1993       break;
1994
1995     case ARRAY_TYPE:
1996       /* Don't follow this nodes's type if a pointer for fear that we'll
1997          have infinite recursion.  Those types are uninteresting anyway. */
1998       if (!POINTER_TYPE_P (TREE_TYPE (type))
1999           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
2000         WALK_SUBTREE (TREE_TYPE (type));
2001       WALK_SUBTREE (TYPE_DOMAIN (type));
2002       break;
2003
2004     case BOOLEAN_TYPE:
2005     case ENUMERAL_TYPE:
2006     case INTEGER_TYPE:
2007     case CHAR_TYPE:
2008     case REAL_TYPE:
2009       WALK_SUBTREE (TYPE_MIN_VALUE (type));
2010       WALK_SUBTREE (TYPE_MAX_VALUE (type));
2011       break;
2012
2013     case OFFSET_TYPE:
2014       WALK_SUBTREE (TREE_TYPE (type));
2015       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
2016       break;
2017
2018     default:
2019       break;
2020     }
2021
2022   return NULL_TREE;
2023 }
2024
2025 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
2026    called with the DATA and the address of each sub-tree.  If FUNC returns a
2027    non-NULL value, the traversal is aborted, and the value returned by FUNC
2028    is returned.  If HTAB is non-NULL it is used to record the nodes visited,
2029    and to avoid visiting a node more than once.  */
2030
2031 tree
2032 walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
2033 {
2034   htab_t htab = (htab_t) htab_;
2035   enum tree_code code;
2036   int walk_subtrees;
2037   tree result;
2038
2039 #define WALK_SUBTREE_TAIL(NODE)                         \
2040   do                                                    \
2041     {                                                   \
2042        tp = & (NODE);                                   \
2043        goto tail_recurse;                               \
2044     }                                                   \
2045   while (0)
2046
2047  tail_recurse:
2048   /* Skip empty subtrees.  */
2049   if (!*tp)
2050     return NULL_TREE;
2051
2052   if (htab)
2053     {
2054       void **slot;
2055
2056       /* Don't walk the same tree twice, if the user has requested
2057          that we avoid doing so.  */
2058       slot = htab_find_slot (htab, *tp, INSERT);
2059       if (*slot)
2060         return NULL_TREE;
2061       *slot = *tp;
2062     }
2063
2064   /* Call the function.  */
2065   walk_subtrees = 1;
2066   result = (*func) (tp, &walk_subtrees, data);
2067
2068   /* If we found something, return it.  */
2069   if (result)
2070     return result;
2071
2072   code = TREE_CODE (*tp);
2073
2074   /* Even if we didn't, FUNC may have decided that there was nothing
2075      interesting below this point in the tree.  */
2076   if (!walk_subtrees)
2077     {
2078       if (code == TREE_LIST)
2079         /* But we still need to check our siblings.  */
2080         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2081       else
2082         return NULL_TREE;
2083     }
2084
2085   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2086                                                    data, htab);
2087   if (result || ! walk_subtrees)
2088     return result;
2089
2090   /* If this is a DECL_EXPR, walk into various fields of the type that it's
2091      defining.  We only want to walk into these fields of a type in this
2092      case.  Note that decls get walked as part of the processing of a
2093      BIND_EXPR.
2094
2095      ??? Precisely which fields of types that we are supposed to walk in
2096      this case vs. the normal case aren't well defined.  */
2097   if (code == DECL_EXPR
2098       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
2099       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
2100     {
2101       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
2102
2103       /* Call the function for the type.  See if it returns anything or
2104          doesn't want us to continue.  If we are to continue, walk both
2105          the normal fields and those for the declaration case.  */
2106       result = (*func) (type_p, &walk_subtrees, data);
2107       if (result || !walk_subtrees)
2108         return NULL_TREE;
2109
2110       result = walk_type_fields (*type_p, func, data, htab_);
2111       if (result)
2112         return result;
2113
2114       WALK_SUBTREE (TYPE_SIZE (*type_p));
2115       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
2116
2117       /* If this is a record type, also walk the fields.  */
2118       if (TREE_CODE (*type_p) == RECORD_TYPE
2119           || TREE_CODE (*type_p) == UNION_TYPE
2120           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2121         {
2122           tree field;
2123
2124           for (field = TYPE_FIELDS (*type_p); field;
2125                field = TREE_CHAIN (field))
2126             {
2127               /* We'd like to look at the type of the field, but we can easily
2128                  get infinite recursion.  So assume it's pointed to elsewhere
2129                  in the tree.  Also, ignore things that aren't fields.  */
2130               if (TREE_CODE (field) != FIELD_DECL)
2131                 continue;
2132
2133               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
2134               WALK_SUBTREE (DECL_SIZE (field));
2135               WALK_SUBTREE (DECL_SIZE_UNIT (field));
2136               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2137                 WALK_SUBTREE (DECL_QUALIFIER (field));
2138             }
2139         }
2140     }
2141
2142   else if (code != EXIT_BLOCK_EXPR
2143            && code != SAVE_EXPR
2144            && code != BIND_EXPR
2145            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2146     {
2147       int i, len;
2148
2149       /* Walk over all the sub-trees of this operand.  */
2150       len = first_rtl_op (code);
2151       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2152          But, we only want to walk once.  */
2153       if (code == TARGET_EXPR
2154           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2155         --len;
2156
2157       /* Go through the subtrees.  We need to do this in forward order so
2158          that the scope of a FOR_EXPR is handled properly.  */
2159 #ifdef DEBUG_WALK_TREE
2160       for (i = 0; i < len; ++i)
2161         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2162 #else
2163       for (i = 0; i < len - 1; ++i)
2164         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2165
2166       if (len)
2167         {
2168           /* The common case is that we may tail recurse here.  */
2169           if (code != BIND_EXPR
2170               && !TREE_CHAIN (*tp))
2171             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
2172           else
2173             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
2174         }
2175 #endif
2176     }
2177
2178   /* If this is a type, walk the needed fields in the type.  */
2179   else if (TYPE_P (*tp))
2180     {
2181       result = walk_type_fields (*tp, func, data, htab_);
2182       if (result)
2183         return result;
2184     }
2185   else
2186     {
2187       /* Not one of the easy cases.  We must explicitly go through the
2188          children.  */
2189       switch (code)
2190         {
2191         case ERROR_MARK:
2192         case IDENTIFIER_NODE:
2193         case INTEGER_CST:
2194         case REAL_CST:
2195         case VECTOR_CST:
2196         case STRING_CST:
2197         case BLOCK:
2198         case PLACEHOLDER_EXPR:
2199         case SSA_NAME:
2200         case FIELD_DECL:
2201         case RESULT_DECL:
2202           /* None of thse have subtrees other than those already walked
2203              above.  */
2204           break;
2205
2206         case TREE_LIST:
2207           WALK_SUBTREE (TREE_VALUE (*tp));
2208           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2209           break;
2210
2211         case TREE_VEC:
2212           {
2213             int len = TREE_VEC_LENGTH (*tp);
2214
2215             if (len == 0)
2216               break;
2217
2218             /* Walk all elements but the first.  */
2219             while (--len)
2220               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2221
2222             /* Now walk the first one as a tail call.  */
2223             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2224           }
2225
2226         case COMPLEX_CST:
2227           WALK_SUBTREE (TREE_REALPART (*tp));
2228           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2229
2230         case CONSTRUCTOR:
2231           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2232
2233         case EXIT_BLOCK_EXPR:
2234           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
2235
2236         case SAVE_EXPR:
2237           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2238
2239         case BIND_EXPR:
2240           {
2241             tree decl;
2242             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2243               {
2244                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2245                    into declarations that are just mentioned, rather than
2246                    declared; they don't really belong to this part of the tree.
2247                    And, we can see cycles: the initializer for a declaration
2248                    can refer to the declaration itself.  */
2249                 WALK_SUBTREE (DECL_INITIAL (decl));
2250                 WALK_SUBTREE (DECL_SIZE (decl));
2251                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2252               }
2253             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2254           }
2255
2256         case STATEMENT_LIST:
2257           {
2258             tree_stmt_iterator i;
2259             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2260               WALK_SUBTREE (*tsi_stmt_ptr (i));
2261           }
2262           break;
2263
2264         default:
2265           /* ??? This could be a language-defined node.  We really should make
2266              a hook for it, but right now just ignore it.  */
2267           break;
2268         }
2269     }
2270
2271   /* We didn't find what we were looking for.  */
2272   return NULL_TREE;
2273
2274 #undef WALK_SUBTREE
2275 #undef WALK_SUBTREE_TAIL
2276 }
2277
2278 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
2279
2280 tree
2281 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2282 {
2283   tree result;
2284   htab_t htab;
2285
2286   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
2287   result = walk_tree (tp, func, data, htab);
2288   htab_delete (htab);
2289   return result;
2290 }
2291
2292 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2293
2294 tree
2295 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2296 {
2297   enum tree_code code = TREE_CODE (*tp);
2298
2299   /* We make copies of most nodes.  */
2300   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2301       || TREE_CODE_CLASS (code) == 'c'
2302       || code == TREE_LIST
2303       || code == TREE_VEC
2304       || code == TYPE_DECL)
2305     {
2306       /* Because the chain gets clobbered when we make a copy, we save it
2307          here.  */
2308       tree chain = TREE_CHAIN (*tp);
2309       tree new;
2310
2311       /* Copy the node.  */
2312       new = copy_node (*tp);
2313
2314       /* Propagate mudflap marked-ness.  */
2315       if (flag_mudflap && mf_marked_p (*tp))
2316         mf_mark (new);
2317
2318       *tp = new;
2319
2320       /* Now, restore the chain, if appropriate.  That will cause
2321          walk_tree to walk into the chain as well.  */
2322       if (code == PARM_DECL || code == TREE_LIST)
2323         TREE_CHAIN (*tp) = chain;
2324
2325       /* For now, we don't update BLOCKs when we make copies.  So, we
2326          have to nullify all BIND_EXPRs.  */
2327       if (TREE_CODE (*tp) == BIND_EXPR)
2328         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2329     }
2330
2331   else if (TREE_CODE_CLASS (code) == 't')
2332     *walk_subtrees = 0;
2333   else if (TREE_CODE_CLASS (code) == 'd')
2334     *walk_subtrees = 0;
2335  else if (code == STATEMENT_LIST)
2336     abort ();
2337
2338   return NULL_TREE;
2339 }
2340
2341 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2342    information indicating to what new SAVE_EXPR this one should be mapped,
2343    use that one.  Otherwise, create a new node and enter it in ST.  */
2344
2345 void
2346 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2347 {
2348   splay_tree st = (splay_tree) st_;
2349   splay_tree_node n;
2350   tree t;
2351
2352   /* See if we already encountered this SAVE_EXPR.  */
2353   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2354
2355   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2356   if (!n)
2357     {
2358       t = copy_node (*tp);
2359
2360       /* Remember this SAVE_EXPR.  */
2361       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2362       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2363       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2364     }
2365   else
2366     {
2367       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2368       *walk_subtrees = 0;
2369       t = (tree) n->value;
2370     }
2371
2372   /* Replace this SAVE_EXPR with the copy.  */
2373   *tp = t;
2374 }
2375
2376 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2377    copies the declaration and enters it in the splay_tree in DATA (which is
2378    really an `inline_data *').  */
2379
2380 static tree
2381 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2382                         void *data)
2383 {
2384   inline_data *id = (inline_data *) data;
2385
2386   /* Don't walk into types.  */
2387   if (TYPE_P (*tp))
2388     *walk_subtrees = 0;
2389
2390   else if (TREE_CODE (*tp) == LABEL_EXPR)
2391     {
2392       tree decl = TREE_OPERAND (*tp, 0);
2393
2394       /* Copy the decl and remember the copy.  */
2395       insert_decl_map (id, decl,
2396                        copy_decl_for_inlining (decl, DECL_CONTEXT (decl),
2397                                                DECL_CONTEXT (decl)));
2398     }
2399
2400   return NULL_TREE;
2401 }
2402
2403 /* Called via walk_tree when an expression is unsaved.  Using the
2404    splay_tree pointed to by ST (which is really a `splay_tree'),
2405    remaps all local declarations to appropriate replacements.  */
2406
2407 static tree
2408 unsave_r (tree *tp, int *walk_subtrees, void *data)
2409 {
2410   inline_data *id = (inline_data *) data;
2411   splay_tree st = id->decl_map;
2412   splay_tree_node n;
2413
2414   /* Only a local declaration (variable or label).  */
2415   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2416       || TREE_CODE (*tp) == LABEL_DECL)
2417     {
2418       /* Lookup the declaration.  */
2419       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2420
2421       /* If it's there, remap it.  */
2422       if (n)
2423         *tp = (tree) n->value;
2424     }
2425
2426   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2427     copy_statement_list (tp);
2428   else if (TREE_CODE (*tp) == BIND_EXPR)
2429     copy_bind_expr (tp, walk_subtrees, id);
2430   else if (TREE_CODE (*tp) == SAVE_EXPR)
2431     remap_save_expr (tp, st, walk_subtrees);
2432   else
2433     {
2434       copy_tree_r (tp, walk_subtrees, NULL);
2435
2436       /* Do whatever unsaving is required.  */
2437       unsave_expr_1 (*tp);
2438     }
2439
2440   /* Keep iterating.  */
2441   return NULL_TREE;
2442 }
2443
2444 /* Default lang hook for "unsave_expr_now".  Copies everything in EXPR and
2445    replaces variables, labels and SAVE_EXPRs local to EXPR.  */
2446
2447 tree
2448 lhd_unsave_expr_now (tree expr)
2449 {
2450   inline_data id;
2451
2452   /* There's nothing to do for NULL_TREE.  */
2453   if (expr == 0)
2454     return expr;
2455
2456   /* Set up ID.  */
2457   memset (&id, 0, sizeof (id));
2458   VARRAY_TREE_INIT (id.fns, 1, "fns");
2459   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2460   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2461
2462   /* Walk the tree once to find local labels.  */
2463   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2464
2465   /* Walk the tree again, copying, remapping, and unsaving.  */
2466   walk_tree (&expr, unsave_r, &id, NULL);
2467
2468   /* Clean up.  */
2469   splay_tree_delete (id.decl_map);
2470
2471   return expr;
2472 }
2473
2474 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2475
2476 static tree
2477 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2478 {
2479   if (*tp == data)
2480     return (tree) data;
2481   else
2482     return NULL;
2483 }
2484
2485 bool
2486 debug_find_tree (tree top, tree search)
2487 {
2488   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2489 }
2490
2491 /* Declare the variables created by the inliner.  Add all the variables in
2492    VARS to BIND_EXPR.  */
2493
2494 static void
2495 declare_inline_vars (tree bind_expr, tree vars)
2496 {
2497   tree t;
2498   for (t = vars; t; t = TREE_CHAIN (t))
2499     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2500
2501   add_var_to_bind_expr (bind_expr, vars);
2502 }