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