gcc/tree-inline.c

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