gcc/tree-inline.c

   1 /* Tree inlining.
   2    Copyright 2001, 2002, 2003, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, 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 "varray.h"
  36 #include "hashtab.h"
  37 #include "langhooks.h"
  38 #include "basic-block.h"
  39 #include "tree-iterator.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 "ggc.h"
  46 #include "tree-flow.h"
  47 #include "diagnostic.h"
  48 #include "except.h"
  49 #include "debug.h"
  50 #include "pointer-set.h"
  51 #include "ipa-prop.h"
  52
  53 /* I'm not real happy about this, but we need to handle gimple and
  54    non-gimple trees.  */
  55 #include "tree-gimple.h"
  56
  57 /* Inlining, Cloning, Versioning, Parallelization
  58
  59    Inlining: a function body is duplicated, but the PARM_DECLs are
  60    remapped into VAR_DECLs, and non-void RETURN_EXPRs become
  61    MODIFY_EXPRs that store to a dedicated returned-value variable.
  62    The duplicated eh_region info of the copy will later be appended
  63    to the info for the caller; the eh_region info in copied throwing
  64    statements and RESX_EXPRs is adjusted accordingly.
  65
  66    Cloning: (only in C++) We have one body for a con/de/structor, and
  67    multiple function decls, each with a unique parameter list.
  68    Duplicate the body, using the given splay tree; some parameters
  69    will become constants (like 0 or 1).
  70
  71    Versioning: a function body is duplicated and the result is a new
  72    function rather than into blocks of an existing function as with
  73    inlining.  Some parameters will become constants.
  74
  75    Parallelization: a region of a function is duplicated resulting in
  76    a new function.  Variables may be replaced with complex expressions
  77    to enable shared variable semantics.
  78
  79    All of these will simultaneously lookup any callgraph edges.  If
  80    we're going to inline the duplicated function body, and the given
  81    function has some cloned callgraph nodes (one for each place this
  82    function will be inlined) those callgraph edges will be duplicated.
  83    If we're cloning the body, those callgraph edges will be
  84    updated to point into the new body.  (Note that the original
  85    callgraph node and edge list will not be altered.)
  86
  87    See the CALL_EXPR handling case in copy_body_r ().  */
  88
  89 /* 0 if we should not perform inlining.
  90    1 if we should expand functions calls inline at the tree level.
  91    2 if we should consider *all* functions to be inline
  92    candidates.  */
  93
  94 int flag_inline_trees = 0;
  95
  96 /* To Do:
  97
  98    o In order to make inlining-on-trees work, we pessimized
  99      function-local static constants.  In particular, they are now
 100      always output, even when not addressed.  Fix this by treating
 101      function-local static constants just like global static
 102      constants; the back-end already knows not to output them if they
 103      are not needed.
 104
 105    o Provide heuristics to clamp inlining of recursive template
 106      calls?  */
 107
 108 /* Prototypes.  */
 109
 110 static tree declare_return_variable (copy_body_data *, tree, tree, tree *);
 111 static tree copy_generic_body (copy_body_data *);
 112 static bool inlinable_function_p (tree);
 113 static void remap_block (tree *, copy_body_data *);
 114 static tree remap_decls (tree, copy_body_data *);
 115 static void copy_bind_expr (tree *, int *, copy_body_data *);
 116 static tree mark_local_for_remap_r (tree *, int *, void *);
 117 static void unsave_expr_1 (tree);
 118 static tree unsave_r (tree *, int *, void *);
 119 static void declare_inline_vars (tree, tree);
 120 static void remap_save_expr (tree *, void *, int *);
 121 static void add_lexical_block (tree current_block, tree new_block);
 122 static tree copy_decl_to_var (tree, copy_body_data *);
 123 static tree copy_decl_no_change (tree, copy_body_data *);
 124 static tree copy_decl_maybe_to_var (tree, copy_body_data *);
 125
 126 /* Insert a tree->tree mapping for ID.  Despite the name suggests
 127    that the trees should be variables, it is used for more than that.  */
 128
 129 void
 130 insert_decl_map (copy_body_data *id, tree key, tree value)
 131 {
 132   splay_tree_insert (id->decl_map, (splay_tree_key) key,
 133                      (splay_tree_value) value);
 134
 135   /* Always insert an identity map as well.  If we see this same new
 136      node again, we won't want to duplicate it a second time.  */
 137   if (key != value)
 138     splay_tree_insert (id->decl_map, (splay_tree_key) value,
 139                        (splay_tree_value) value);
 140 }
 141
 142 /* Remap DECL during the copying of the BLOCK tree for the function.  */
 143
 144 tree
 145 remap_decl (tree decl, copy_body_data *id)
 146 {
 147   splay_tree_node n;
 148   tree fn;
 149
 150   /* We only remap local variables in the current function.  */
 151   fn = id->src_fn;
 152
 153   /* See if we have remapped this declaration.  */
 154
 155   n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 156
 157   /* If we didn't already have an equivalent for this declaration,
 158      create one now.  */
 159   if (!n)
 160     {
 161       /* Make a copy of the variable or label.  */
 162       tree t = id->copy_decl (decl, id);
 163
 164       /* Remember it, so that if we encounter this local entity again
 165          we can reuse this copy.  Do this early because remap_type may
 166          need this decl for TYPE_STUB_DECL.  */
 167       insert_decl_map (id, decl, t);
 168
 169       if (!DECL_P (t))
 170         return t;
 171
 172       /* Remap types, if necessary.  */
 173       TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
 174       if (TREE_CODE (t) == TYPE_DECL)
 175         DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
 176
 177       /* Remap sizes as necessary.  */
 178       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 179       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 180
 181       /* If fields, do likewise for offset and qualifier.  */
 182       if (TREE_CODE (t) == FIELD_DECL)
 183         {
 184           walk_tree (&DECL_FIELD_OFFSET (t), copy_body_r, id, NULL);
 185           if (TREE_CODE (DECL_CONTEXT (t)) == QUAL_UNION_TYPE)
 186             walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
 187         }
 188
 189       return t;
 190     }
 191
 192   return unshare_expr ((tree) n->value);
 193 }
 194
 195 static tree
 196 remap_type_1 (tree type, copy_body_data *id)
 197 {
 198   splay_tree_node node;
 199   tree new, t;
 200
 201   if (type == NULL)
 202     return type;
 203
 204   /* See if we have remapped this type.  */
 205   node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
 206   if (node)
 207     return (tree) node->value;
 208
 209   /* The type only needs remapping if it's variably modified.  */
 210   if (! variably_modified_type_p (type, id->src_fn))
 211     {
 212       insert_decl_map (id, type, type);
 213       return type;
 214     }
 215
 216   /* We do need a copy.  build and register it now.  If this is a pointer or
 217      reference type, remap the designated type and make a new pointer or
 218      reference type.  */
 219   if (TREE_CODE (type) == POINTER_TYPE)
 220     {
 221       new = build_pointer_type_for_mode (remap_type (TREE_TYPE (type), id),
 222                                          TYPE_MODE (type),
 223                                          TYPE_REF_CAN_ALIAS_ALL (type));
 224       insert_decl_map (id, type, new);
 225       return new;
 226     }
 227   else if (TREE_CODE (type) == REFERENCE_TYPE)
 228     {
 229       new = build_reference_type_for_mode (remap_type (TREE_TYPE (type), id),
 230                                             TYPE_MODE (type),
 231                                             TYPE_REF_CAN_ALIAS_ALL (type));
 232       insert_decl_map (id, type, new);
 233       return new;
 234     }
 235   else
 236     new = copy_node (type);
 237
 238   insert_decl_map (id, type, new);
 239
 240   /* This is a new type, not a copy of an old type.  Need to reassociate
 241      variants.  We can handle everything except the main variant lazily.  */
 242   t = TYPE_MAIN_VARIANT (type);
 243   if (type != t)
 244     {
 245       t = remap_type (t, id);
 246       TYPE_MAIN_VARIANT (new) = t;
 247       TYPE_NEXT_VARIANT (new) = TYPE_MAIN_VARIANT (t);
 248       TYPE_NEXT_VARIANT (t) = new;
 249     }
 250   else
 251     {
 252       TYPE_MAIN_VARIANT (new) = new;
 253       TYPE_NEXT_VARIANT (new) = NULL;
 254     }
 255
 256   if (TYPE_STUB_DECL (type))
 257     TYPE_STUB_DECL (new) = remap_decl (TYPE_STUB_DECL (type), id);
 258
 259   /* Lazily create pointer and reference types.  */
 260   TYPE_POINTER_TO (new) = NULL;
 261   TYPE_REFERENCE_TO (new) = NULL;
 262
 263   switch (TREE_CODE (new))
 264     {
 265     case INTEGER_TYPE:
 266     case REAL_TYPE:
 267     case ENUMERAL_TYPE:
 268     case BOOLEAN_TYPE:
 269       t = TYPE_MIN_VALUE (new);
 270       if (t && TREE_CODE (t) != INTEGER_CST)
 271         walk_tree (&TYPE_MIN_VALUE (new), copy_body_r, id, NULL);
 272
 273       t = TYPE_MAX_VALUE (new);
 274       if (t && TREE_CODE (t) != INTEGER_CST)
 275         walk_tree (&TYPE_MAX_VALUE (new), copy_body_r, id, NULL);
 276       return new;
 277
 278     case FUNCTION_TYPE:
 279       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 280       walk_tree (&TYPE_ARG_TYPES (new), copy_body_r, id, NULL);
 281       return new;
 282
 283     case ARRAY_TYPE:
 284       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 285       TYPE_DOMAIN (new) = remap_type (TYPE_DOMAIN (new), id);
 286       break;
 287
 288     case RECORD_TYPE:
 289     case UNION_TYPE:
 290     case QUAL_UNION_TYPE:
 291       {
 292         tree f, nf = NULL;
 293
 294         for (f = TYPE_FIELDS (new); f ; f = TREE_CHAIN (f))
 295           {
 296             t = remap_decl (f, id);
 297             DECL_CONTEXT (t) = new;
 298             TREE_CHAIN (t) = nf;
 299             nf = t;
 300           }
 301         TYPE_FIELDS (new) = nreverse (nf);
 302       }
 303       break;
 304
 305     case OFFSET_TYPE:
 306     default:
 307       /* Shouldn't have been thought variable sized.  */
 308       gcc_unreachable ();
 309     }
 310
 311   walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
 312   walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
 313
 314   return new;
 315 }
 316
 317 tree
 318 remap_type (tree type, copy_body_data *id)
 319 {
 320   splay_tree_node node;
 321
 322   if (type == NULL)
 323     return type;
 324
 325   /* See if we have remapped this type.  */
 326   node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
 327   if (node)
 328     return (tree) node->value;
 329
 330   /* The type only needs remapping if it's variably modified.  */
 331   if (! variably_modified_type_p (type, id->src_fn))
 332     {
 333       insert_decl_map (id, type, type);
 334       return type;
 335     }
 336
 337   return remap_type_1 (type, id);
 338 }
 339
 340 static tree
 341 remap_decls (tree decls, copy_body_data *id)
 342 {
 343   tree old_var;
 344   tree new_decls = NULL_TREE;
 345
 346   /* Remap its variables.  */
 347   for (old_var = decls; old_var; old_var = TREE_CHAIN (old_var))
 348     {
 349       tree new_var;
 350
 351       /* We can not chain the local static declarations into the unexpanded_var_list
 352          as we can't duplicate them or break one decl rule.  Go ahead and link
 353          them into unexpanded_var_list.  */
 354       if (!lang_hooks.tree_inlining.auto_var_in_fn_p (old_var, id->src_fn)
 355           && !DECL_EXTERNAL (old_var))
 356         {
 357           cfun->unexpanded_var_list = tree_cons (NULL_TREE, old_var,
 358                                                  cfun->unexpanded_var_list);
 359           continue;
 360         }
 361
 362       /* Remap the variable.  */
 363       new_var = remap_decl (old_var, id);
 364
 365       /* If we didn't remap this variable, so we can't mess with its
 366          TREE_CHAIN.  If we remapped this variable to the return slot, it's
 367          already declared somewhere else, so don't declare it here.  */
 368       if (!new_var || new_var == id->retvar)
 369         ;
 370       else
 371         {
 372           gcc_assert (DECL_P (new_var));
 373           TREE_CHAIN (new_var) = new_decls;
 374           new_decls = new_var;
 375         }
 376     }
 377
 378   return nreverse (new_decls);
 379 }
 380
 381 /* Copy the BLOCK to contain remapped versions of the variables
 382    therein.  And hook the new block into the block-tree.  */
 383
 384 static void
 385 remap_block (tree *block, copy_body_data *id)
 386 {
 387   tree old_block;
 388   tree new_block;
 389   tree fn;
 390
 391   /* Make the new block.  */
 392   old_block = *block;
 393   new_block = make_node (BLOCK);
 394   TREE_USED (new_block) = TREE_USED (old_block);
 395   BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 396   BLOCK_SOURCE_LOCATION (new_block) = BLOCK_SOURCE_LOCATION (old_block);
 397   *block = new_block;
 398
 399   /* Remap its variables.  */
 400   BLOCK_VARS (new_block) = remap_decls (BLOCK_VARS (old_block), id);
 401
 402   fn = id->dst_fn;
 403
 404   if (id->transform_lang_insert_block)
 405     lang_hooks.decls.insert_block (new_block);
 406
 407   /* Remember the remapped block.  */
 408   insert_decl_map (id, old_block, new_block);
 409 }
 410
 411 /* Copy the whole block tree and root it in id->block.  */
 412 static tree
 413 remap_blocks (tree block, copy_body_data *id)
 414 {
 415   tree t;
 416   tree new = block;
 417
 418   if (!block)
 419     return NULL;
 420
 421   remap_block (&new, id);
 422   gcc_assert (new != block);
 423   for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
 424     add_lexical_block (new, remap_blocks (t, id));
 425   return new;
 426 }
 427
 428 static void
 429 copy_statement_list (tree *tp)
 430 {
 431   tree_stmt_iterator oi, ni;
 432   tree new;
 433
 434   new = alloc_stmt_list ();
 435   ni = tsi_start (new);
 436   oi = tsi_start (*tp);
 437   *tp = new;
 438
 439   for (; !tsi_end_p (oi); tsi_next (&oi))
 440     tsi_link_after (&ni, tsi_stmt (oi), TSI_NEW_STMT);
 441 }
 442
 443 static void
 444 copy_bind_expr (tree *tp, int *walk_subtrees, copy_body_data *id)
 445 {
 446   tree block = BIND_EXPR_BLOCK (*tp);
 447   /* Copy (and replace) the statement.  */
 448   copy_tree_r (tp, walk_subtrees, NULL);
 449   if (block)
 450     {
 451       remap_block (&block, id);
 452       BIND_EXPR_BLOCK (*tp) = block;
 453     }
 454
 455   if (BIND_EXPR_VARS (*tp))
 456     /* This will remap a lot of the same decls again, but this should be
 457        harmless.  */
 458     BIND_EXPR_VARS (*tp) = remap_decls (BIND_EXPR_VARS (*tp), id);
 459 }
 460
 461 /* Called from copy_body_id via walk_tree.  DATA is really an
 462    `copy_body_data *'.  */
 463
 464 tree
 465 copy_body_r (tree *tp, int *walk_subtrees, void *data)
 466 {
 467   copy_body_data *id = (copy_body_data *) data;
 468   tree fn = id->src_fn;
 469   tree new_block;
 470
 471   /* Begin by recognizing trees that we'll completely rewrite for the
 472      inlining context.  Our output for these trees is completely
 473      different from out input (e.g. RETURN_EXPR is deleted, and morphs
 474      into an edge).  Further down, we'll handle trees that get
 475      duplicated and/or tweaked.  */
 476
 477   /* When requested, RETURN_EXPRs should be transformed to just the
 478      contained MODIFY_EXPR.  The branch semantics of the return will
 479      be handled elsewhere by manipulating the CFG rather than a statement.  */
 480   if (TREE_CODE (*tp) == RETURN_EXPR && id->transform_return_to_modify)
 481     {
 482       tree assignment = TREE_OPERAND (*tp, 0);
 483
 484       /* If we're returning something, just turn that into an
 485          assignment into the equivalent of the original RESULT_DECL.
 486          If the "assignment" is just the result decl, the result
 487          decl has already been set (e.g. a recent "foo (&result_decl,
 488          ...)"); just toss the entire RETURN_EXPR.  */
 489       if (assignment && TREE_CODE (assignment) == MODIFY_EXPR)
 490         {
 491           /* Replace the RETURN_EXPR with (a copy of) the
 492              MODIFY_EXPR hanging underneath.  */
 493           *tp = copy_node (assignment);
 494         }
 495       else /* Else the RETURN_EXPR returns no value.  */
 496         {
 497           *tp = NULL;
 498           return (tree) (void *)1;
 499         }
 500     }
 501
 502   /* Local variables and labels need to be replaced by equivalent
 503      variables.  We don't want to copy static variables; there's only
 504      one of those, no matter how many times we inline the containing
 505      function.  Similarly for globals from an outer function.  */
 506   else if (lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
 507     {
 508       tree new_decl;
 509
 510       /* Remap the declaration.  */
 511       new_decl = remap_decl (*tp, id);
 512       gcc_assert (new_decl);
 513       /* Replace this variable with the copy.  */
 514       STRIP_TYPE_NOPS (new_decl);
 515       *tp = new_decl;
 516       *walk_subtrees = 0;
 517     }
 518   else if (TREE_CODE (*tp) == STATEMENT_LIST)
 519     copy_statement_list (tp);
 520   else if (TREE_CODE (*tp) == SAVE_EXPR)
 521     remap_save_expr (tp, id->decl_map, walk_subtrees);
 522   else if (TREE_CODE (*tp) == LABEL_DECL
 523            && (! DECL_CONTEXT (*tp)
 524                || decl_function_context (*tp) == id->src_fn))
 525     /* These may need to be remapped for EH handling.  */
 526     *tp = remap_decl (*tp, id);
 527   else if (TREE_CODE (*tp) == BIND_EXPR)
 528     copy_bind_expr (tp, walk_subtrees, id);
 529   /* Types may need remapping as well.  */
 530   else if (TYPE_P (*tp))
 531     *tp = remap_type (*tp, id);
 532
 533   /* If this is a constant, we have to copy the node iff the type will be
 534      remapped.  copy_tree_r will not copy a constant.  */
 535   else if (CONSTANT_CLASS_P (*tp))
 536     {
 537       tree new_type = remap_type (TREE_TYPE (*tp), id);
 538
 539       if (new_type == TREE_TYPE (*tp))
 540         *walk_subtrees = 0;
 541
 542       else if (TREE_CODE (*tp) == INTEGER_CST)
 543         *tp = build_int_cst_wide (new_type, TREE_INT_CST_LOW (*tp),
 544                                   TREE_INT_CST_HIGH (*tp));
 545       else
 546         {
 547           *tp = copy_node (*tp);
 548           TREE_TYPE (*tp) = new_type;
 549         }
 550     }
 551
 552   /* Otherwise, just copy the node.  Note that copy_tree_r already
 553      knows not to copy VAR_DECLs, etc., so this is safe.  */
 554   else
 555     {
 556       /* Here we handle trees that are not completely rewritten.
 557          First we detect some inlining-induced bogosities for
 558          discarding.  */
 559       if (TREE_CODE (*tp) == MODIFY_EXPR
 560           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 561           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 562               (TREE_OPERAND (*tp, 0), fn)))
 563         {
 564           /* Some assignments VAR = VAR; don't generate any rtl code
 565              and thus don't count as variable modification.  Avoid
 566              keeping bogosities like 0 = 0.  */
 567           tree decl = TREE_OPERAND (*tp, 0), value;
 568           splay_tree_node n;
 569
 570           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 571           if (n)
 572             {
 573               value = (tree) n->value;
 574               STRIP_TYPE_NOPS (value);
 575               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 576                 {
 577                   *tp = build_empty_stmt ();
 578                   return copy_body_r (tp, walk_subtrees, data);
 579                 }
 580             }
 581         }
 582       else if (TREE_CODE (*tp) == INDIRECT_REF)
 583         {
 584           /* Get rid of *& from inline substitutions that can happen when a
 585              pointer argument is an ADDR_EXPR.  */
 586           tree decl = TREE_OPERAND (*tp, 0);
 587           splay_tree_node n;
 588
 589           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 590           if (n)
 591             {
 592               tree new;
 593               tree old;
 594               /* If we happen to get an ADDR_EXPR in n->value, strip
 595                  it manually here as we'll eventually get ADDR_EXPRs
 596                  which lie about their types pointed to.  In this case
 597                  build_fold_indirect_ref wouldn't strip the INDIRECT_REF,
 598                  but we absolutely rely on that.  As fold_indirect_ref
 599                  does other useful transformations, try that first, though.  */
 600               tree type = TREE_TYPE (TREE_TYPE ((tree)n->value));
 601               new = unshare_expr ((tree)n->value);
 602               old = *tp;
 603               *tp = fold_indirect_ref_1 (type, new);
 604               if (! *tp)
 605                 {
 606                   if (TREE_CODE (new) == ADDR_EXPR)
 607                     *tp = TREE_OPERAND (new, 0);
 608                   else
 609                     {
 610                       *tp = build1 (INDIRECT_REF, type, new);
 611                       TREE_THIS_VOLATILE (*tp) = TREE_THIS_VOLATILE (old);
 612                     }
 613                 }
 614               *walk_subtrees = 0;
 615               return NULL;
 616             }
 617         }
 618
 619       /* Here is the "usual case".  Copy this tree node, and then
 620          tweak some special cases.  */
 621       copy_tree_r (tp, walk_subtrees, NULL);
 622
 623       /* If EXPR has block defined, map it to newly constructed block.
 624          When inlining we want EXPRs without block appear in the block
 625          of function call.  */
 626       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (*tp))))
 627         {
 628           new_block = id->block;
 629           if (TREE_BLOCK (*tp))
 630             {
 631               splay_tree_node n;
 632               n = splay_tree_lookup (id->decl_map,
 633                                      (splay_tree_key) TREE_BLOCK (*tp));
 634               gcc_assert (n);
 635               new_block = (tree) n->value;
 636             }
 637           TREE_BLOCK (*tp) = new_block;
 638         }
 639
 640       if (TREE_CODE (*tp) == RESX_EXPR && id->eh_region_offset)
 641         TREE_OPERAND (*tp, 0) =
 642           build_int_cst
 643             (NULL_TREE,
 644              id->eh_region_offset + TREE_INT_CST_LOW (TREE_OPERAND (*tp, 0)));
 645
 646       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 647
 648       /* The copied TARGET_EXPR has never been expanded, even if the
 649          original node was expanded already.  */
 650       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 651         {
 652           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 653           TREE_OPERAND (*tp, 3) = NULL_TREE;
 654         }
 655
 656       /* Variable substitution need not be simple.  In particular, the
 657          INDIRECT_REF substitution above.  Make sure that TREE_CONSTANT
 658          and friends are up-to-date.  */
 659       else if (TREE_CODE (*tp) == ADDR_EXPR)
 660         {
 661           walk_tree (&TREE_OPERAND (*tp, 0), copy_body_r, id, NULL);
 662           /* Handle the case where we substituted an INDIRECT_REF
 663              into the operand of the ADDR_EXPR.  */
 664           if (TREE_CODE (TREE_OPERAND (*tp, 0)) == INDIRECT_REF)
 665             *tp = TREE_OPERAND (TREE_OPERAND (*tp, 0), 0);
 666           else
 667             recompute_tree_invariant_for_addr_expr (*tp);
 668           *walk_subtrees = 0;
 669         }
 670     }
 671
 672   /* Keep iterating.  */
 673   return NULL_TREE;
 674 }
 675
 676 /* Copy basic block, scale profile accordingly.  Edges will be taken care of
 677    later  */
 678
 679 static basic_block
 680 copy_bb (copy_body_data *id, basic_block bb, int frequency_scale, int count_scale)
 681 {
 682   block_stmt_iterator bsi, copy_bsi;
 683   basic_block copy_basic_block;
 684
 685   /* create_basic_block() will append every new block to
 686      basic_block_info automatically.  */
 687   copy_basic_block = create_basic_block (NULL, (void *) 0,
 688                                          (basic_block) bb->prev_bb->aux);
 689   copy_basic_block->count = bb->count * count_scale / REG_BR_PROB_BASE;
 690   copy_basic_block->frequency = (bb->frequency
 691                                      * frequency_scale / REG_BR_PROB_BASE);
 692   copy_bsi = bsi_start (copy_basic_block);
 693
 694   for (bsi = bsi_start (bb);
 695        !bsi_end_p (bsi); bsi_next (&bsi))
 696     {
 697       tree stmt = bsi_stmt (bsi);
 698       tree orig_stmt = stmt;
 699
 700       walk_tree (&stmt, copy_body_r, id, NULL);
 701
 702       /* RETURN_EXPR might be removed,
 703          this is signalled by making stmt pointer NULL.  */
 704       if (stmt)
 705         {
 706           tree call, decl;
 707
 708           /* With return slot optimization we can end up with
 709              non-gimple (foo *)&this->m, fix that here.  */
 710           if (TREE_CODE (stmt) == MODIFY_EXPR
 711               && TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR
 712               && !is_gimple_val (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0)))
 713             gimplify_stmt (&stmt);
 714
 715           bsi_insert_after (&copy_bsi, stmt, BSI_NEW_STMT);
 716           call = get_call_expr_in (stmt);
 717           /* We're duplicating a CALL_EXPR.  Find any corresponding
 718              callgraph edges and update or duplicate them.  */
 719           if (call && (decl = get_callee_fndecl (call)))
 720             {
 721               struct cgraph_node *node;
 722               struct cgraph_edge *edge;
 723
 724               switch (id->transform_call_graph_edges)
 725                 {
 726                 case CB_CGE_DUPLICATE:
 727                   edge = cgraph_edge (id->src_node, orig_stmt);
 728                   if (edge)
 729                     cgraph_clone_edge (edge, id->dst_node, stmt,
 730                                        REG_BR_PROB_BASE, 1, true);
 731                   break;
 732
 733                 case CB_CGE_MOVE_CLONES:
 734                   for (node = id->dst_node->next_clone;
 735                        node;
 736                        node = node->next_clone)
 737                     {
 738                       edge = cgraph_edge (node, orig_stmt);
 739                       gcc_assert (edge);
 740                       cgraph_set_call_stmt (edge, stmt);
 741                     }
 742                   /* FALLTHRU */
 743
 744                 case CB_CGE_MOVE:
 745                   edge = cgraph_edge (id->dst_node, orig_stmt);
 746                   if (edge)
 747                     cgraph_set_call_stmt (edge, stmt);
 748                   break;
 749
 750                 default:
 751                   gcc_unreachable ();
 752                 }
 753             }
 754           /* If you think we can abort here, you are wrong.
 755              There is no region 0 in tree land.  */
 756           gcc_assert (lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt)
 757                       != 0);
 758
 759           if (tree_could_throw_p (stmt))
 760             {
 761               int region = lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt);
 762               /* Add an entry for the copied tree in the EH hashtable.
 763                  When cloning or versioning, use the hashtable in
 764                  cfun, and just copy the EH number.  When inlining, use the
 765                  hashtable in the caller, and adjust the region number.  */
 766               if (region > 0)
 767                 add_stmt_to_eh_region (stmt, region + id->eh_region_offset);
 768
 769               /* If this tree doesn't have a region associated with it,
 770                  and there is a "current region,"
 771                  then associate this tree with the current region
 772                  and add edges associated with this region.  */
 773               if ((lookup_stmt_eh_region_fn (id->src_cfun,
 774                                              orig_stmt) <= 0
 775                    && id->eh_region > 0)
 776                   && tree_could_throw_p (stmt))
 777                 add_stmt_to_eh_region (stmt, id->eh_region);
 778             }
 779         }
 780     }
 781   return copy_basic_block;
 782 }
 783
 784 /* Copy edges from BB into its copy constructed earlier, scale profile
 785    accordingly.  Edges will be taken care of later.  Assume aux
 786    pointers to point to the copies of each BB.  */
 787 static void
 788 copy_edges_for_bb (basic_block bb, int count_scale)
 789 {
 790   basic_block new_bb = (basic_block) bb->aux;
 791   edge_iterator ei;
 792   edge old_edge;
 793   block_stmt_iterator bsi;
 794   int flags;
 795
 796   /* Use the indices from the original blocks to create edges for the
 797      new ones.  */
 798   FOR_EACH_EDGE (old_edge, ei, bb->succs)
 799     if (!(old_edge->flags & EDGE_EH))
 800       {
 801         edge new;
 802
 803         flags = old_edge->flags;
 804
 805         /* Return edges do get a FALLTHRU flag when the get inlined.  */
 806         if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags
 807             && old_edge->dest->aux != EXIT_BLOCK_PTR)
 808           flags |= EDGE_FALLTHRU;
 809         new = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
 810         new->count = old_edge->count * count_scale / REG_BR_PROB_BASE;
 811         new->probability = old_edge->probability;
 812       }
 813
 814   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
 815     return;
 816
 817   for (bsi = bsi_start (new_bb); !bsi_end_p (bsi);)
 818     {
 819       tree copy_stmt;
 820
 821       copy_stmt = bsi_stmt (bsi);
 822       update_stmt (copy_stmt);
 823       /* Do this before the possible split_block.  */
 824       bsi_next (&bsi);
 825
 826       /* If this tree could throw an exception, there are two
 827          cases where we need to add abnormal edge(s): the
 828          tree wasn't in a region and there is a "current
 829          region" in the caller; or the original tree had
 830          EH edges.  In both cases split the block after the tree,
 831          and add abnormal edge(s) as needed; we need both
 832          those from the callee and the caller.
 833          We check whether the copy can throw, because the const
 834          propagation can change an INDIRECT_REF which throws
 835          into a COMPONENT_REF which doesn't.  If the copy
 836          can throw, the original could also throw.  */
 837
 838       if (tree_can_throw_internal (copy_stmt))
 839         {
 840           if (!bsi_end_p (bsi))
 841             /* Note that bb's predecessor edges aren't necessarily
 842                right at this point; split_block doesn't care.  */
 843             {
 844               edge e = split_block (new_bb, copy_stmt);
 845               new_bb = e->dest;
 846               bsi = bsi_start (new_bb);
 847             }
 848
 849            make_eh_edges (copy_stmt);
 850         }
 851     }
 852 }
 853
 854 /* Wrapper for remap_decl so it can be used as a callback.  */
 855 static tree
 856 remap_decl_1 (tree decl, void *data)
 857 {
 858   return remap_decl (decl, (copy_body_data *) data);
 859 }
 860
 861 /* Make a copy of the body of FN so that it can be inserted inline in
 862    another function.  Walks FN via CFG, returns new fndecl.  */
 863
 864 static tree
 865 copy_cfg_body (copy_body_data * id, gcov_type count, int frequency,
 866                basic_block entry_block_map, basic_block exit_block_map)
 867 {
 868   tree callee_fndecl = id->src_fn;
 869   /* Original cfun for the callee, doesn't change.  */
 870   struct function *src_cfun = DECL_STRUCT_FUNCTION (callee_fndecl);
 871   /* Copy, built by this function.  */
 872   struct function *new_cfun;
 873   /* Place to copy from; when a copy of the function was saved off earlier,
 874      use that instead of the main copy.  */
 875   struct function *cfun_to_copy =
 876     (struct function *) ggc_alloc_cleared (sizeof (struct function));
 877   basic_block bb;
 878   tree new_fndecl = NULL;
 879   int count_scale, frequency_scale;
 880
 881   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count)
 882     count_scale = (REG_BR_PROB_BASE * count
 883                    / ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count);
 884   else
 885     count_scale = 1;
 886
 887   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency)
 888     frequency_scale = (REG_BR_PROB_BASE * frequency
 889                        /
 890                        ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency);
 891   else
 892     frequency_scale = count_scale;
 893
 894   /* Register specific tree functions.  */
 895   tree_register_cfg_hooks ();
 896
 897   /* Must have a CFG here at this point.  */
 898   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION
 899               (DECL_STRUCT_FUNCTION (callee_fndecl)));
 900
 901   *cfun_to_copy = *DECL_STRUCT_FUNCTION (callee_fndecl);
 902
 903   id->src_cfun = cfun_to_copy;
 904
 905   /* If requested, create new basic_block_info and label_to_block_maps.
 906      Otherwise, insert our new blocks and labels into the existing cfg.  */
 907   if (id->transform_new_cfg)
 908     {
 909       new_cfun =
 910         (struct function *) ggc_alloc_cleared (sizeof (struct function));
 911       *new_cfun = *DECL_STRUCT_FUNCTION (callee_fndecl);
 912       new_cfun->cfg = NULL;
 913       new_cfun->decl = new_fndecl = copy_node (callee_fndecl);
 914       new_cfun->ib_boundaries_block = NULL;
 915       DECL_STRUCT_FUNCTION (new_fndecl) = new_cfun;
 916       push_cfun (new_cfun);
 917       init_empty_tree_cfg ();
 918
 919       ENTRY_BLOCK_PTR->count =
 920         (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
 921          REG_BR_PROB_BASE);
 922       ENTRY_BLOCK_PTR->frequency =
 923         (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
 924          frequency_scale / REG_BR_PROB_BASE);
 925       EXIT_BLOCK_PTR->count =
 926         (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
 927          REG_BR_PROB_BASE);
 928       EXIT_BLOCK_PTR->frequency =
 929         (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
 930          frequency_scale / REG_BR_PROB_BASE);
 931
 932       entry_block_map = ENTRY_BLOCK_PTR;
 933       exit_block_map = EXIT_BLOCK_PTR;
 934     }
 935
 936   ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = entry_block_map;
 937   EXIT_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = exit_block_map;
 938
 939   /* Duplicate any exception-handling regions.  */
 940   if (cfun->eh)
 941     {
 942       if (id->transform_new_cfg)
 943         init_eh_for_function ();
 944       id->eh_region_offset
 945         = duplicate_eh_regions (cfun_to_copy, remap_decl_1, id,
 946                                 0, id->eh_region);
 947     }
 948   /* Use aux pointers to map the original blocks to copy.  */
 949   FOR_EACH_BB_FN (bb, cfun_to_copy)
 950     bb->aux = copy_bb (id, bb, frequency_scale, count_scale);
 951   /* Now that we've duplicated the blocks, duplicate their edges.  */
 952   FOR_ALL_BB_FN (bb, cfun_to_copy)
 953     copy_edges_for_bb (bb, count_scale);
 954   FOR_ALL_BB_FN (bb, cfun_to_copy)
 955     bb->aux = NULL;
 956
 957   if (id->transform_new_cfg)
 958     pop_cfun ();
 959
 960   return new_fndecl;
 961 }
 962
 963 /* Make a copy of the body of FN so that it can be inserted inline in
 964    another function.  */
 965
 966 static tree
 967 copy_generic_body (copy_body_data *id)
 968 {
 969   tree body;
 970   tree fndecl = id->src_fn;
 971
 972   body = DECL_SAVED_TREE (fndecl);
 973   walk_tree (&body, copy_body_r, id, NULL);
 974
 975   return body;
 976 }
 977
 978 static tree
 979 copy_body (copy_body_data *id, gcov_type count, int frequency,
 980            basic_block entry_block_map, basic_block exit_block_map)
 981 {
 982   tree fndecl = id->src_fn;
 983   tree body;
 984
 985   /* If this body has a CFG, walk CFG and copy.  */
 986   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (fndecl)));
 987   body = copy_cfg_body (id, count, frequency, entry_block_map, exit_block_map);
 988
 989   return body;
 990 }
 991
 992 /* Return true if VALUE is an ADDR_EXPR of an automatic variable
 993    defined in function FN, or of a data member thereof.  */
 994
 995 static bool
 996 self_inlining_addr_expr (tree value, tree fn)
 997 {
 998   tree var;
 999
1000   if (TREE_CODE (value) != ADDR_EXPR)
1001     return false;
1002
1003   var = get_base_address (TREE_OPERAND (value, 0));
1004
1005   return var && lang_hooks.tree_inlining.auto_var_in_fn_p (var, fn);
1006 }
1007
1008 static void
1009 setup_one_parameter (copy_body_data *id, tree p, tree value, tree fn,
1010                      basic_block bb, tree *vars)
1011 {
1012   tree init_stmt;
1013   tree var;
1014   tree var_sub;
1015
1016   /* If the parameter is never assigned to, we may not need to
1017      create a new variable here at all.  Instead, we may be able
1018      to just use the argument value.  */
1019   if (TREE_READONLY (p)
1020       && !TREE_ADDRESSABLE (p)
1021       && value && !TREE_SIDE_EFFECTS (value))
1022     {
1023       /* We may produce non-gimple trees by adding NOPs or introduce
1024          invalid sharing when operand is not really constant.
1025          It is not big deal to prohibit constant propagation here as
1026          we will constant propagate in DOM1 pass anyway.  */
1027       if (is_gimple_min_invariant (value)
1028           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p))
1029           /* We have to be very careful about ADDR_EXPR.  Make sure
1030              the base variable isn't a local variable of the inlined
1031              function, e.g., when doing recursive inlining, direct or
1032              mutually-recursive or whatever, which is why we don't
1033              just test whether fn == current_function_decl.  */
1034           && ! self_inlining_addr_expr (value, fn))
1035         {
1036           insert_decl_map (id, p, value);
1037           return;
1038         }
1039     }
1040
1041   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
1042      here since the type of this decl must be visible to the calling
1043      function.  */
1044   var = copy_decl_to_var (p, id);
1045
1046   /* See if the frontend wants to pass this by invisible reference.  If
1047      so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
1048      replace uses of the PARM_DECL with dereferences.  */
1049   if (TREE_TYPE (var) != TREE_TYPE (p)
1050       && POINTER_TYPE_P (TREE_TYPE (var))
1051       && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
1052     {
1053       insert_decl_map (id, var, var);
1054       var_sub = build_fold_indirect_ref (var);
1055     }
1056   else
1057     var_sub = var;
1058
1059   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
1060      that way, when the PARM_DECL is encountered, it will be
1061      automatically replaced by the VAR_DECL.  */
1062   insert_decl_map (id, p, var_sub);
1063
1064   /* Declare this new variable.  */
1065   TREE_CHAIN (var) = *vars;
1066   *vars = var;
1067
1068   /* Make gimplifier happy about this variable.  */
1069   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1070
1071   /* Even if P was TREE_READONLY, the new VAR should not be.
1072      In the original code, we would have constructed a
1073      temporary, and then the function body would have never
1074      changed the value of P.  However, now, we will be
1075      constructing VAR directly.  The constructor body may
1076      change its value multiple times as it is being
1077      constructed.  Therefore, it must not be TREE_READONLY;
1078      the back-end assumes that TREE_READONLY variable is
1079      assigned to only once.  */
1080   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
1081     TREE_READONLY (var) = 0;
1082
1083   /* Initialize this VAR_DECL from the equivalent argument.  Convert
1084      the argument to the proper type in case it was promoted.  */
1085   if (value)
1086     {
1087       tree rhs = fold_convert (TREE_TYPE (var), value);
1088       block_stmt_iterator bsi = bsi_last (bb);
1089
1090       if (rhs == error_mark_node)
1091         return;
1092
1093       STRIP_USELESS_TYPE_CONVERSION (rhs);
1094
1095       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
1096          keep our trees in gimple form.  */
1097       init_stmt = build2 (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
1098
1099       /* If we did not create a gimple value and we did not create a gimple
1100          cast of a gimple value, then we will need to gimplify INIT_STMTS
1101          at the end.  Note that is_gimple_cast only checks the outer
1102          tree code, not its operand.  Thus the explicit check that its
1103          operand is a gimple value.  */
1104       if (!is_gimple_val (rhs)
1105           && (!is_gimple_cast (rhs)
1106               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
1107         gimplify_stmt (&init_stmt);
1108
1109       /* If VAR represents a zero-sized variable, it's possible that the
1110          assignment statment may result in no gimple statements.  */
1111       if (init_stmt)
1112         bsi_insert_after (&bsi, init_stmt, BSI_NEW_STMT);
1113     }
1114 }
1115
1116 /* Generate code to initialize the parameters of the function at the
1117    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
1118
1119 static void
1120 initialize_inlined_parameters (copy_body_data *id, tree args, tree static_chain,
1121                                tree fn, basic_block bb)
1122 {
1123   tree parms;
1124   tree a;
1125   tree p;
1126   tree vars = NULL_TREE;
1127   int argnum = 0;
1128
1129   /* Figure out what the parameters are.  */
1130   parms = DECL_ARGUMENTS (fn);
1131
1132   /* Loop through the parameter declarations, replacing each with an
1133      equivalent VAR_DECL, appropriately initialized.  */
1134   for (p = parms, a = args; p;
1135        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
1136     {
1137       tree value;
1138
1139       ++argnum;
1140
1141       /* Find the initializer.  */
1142       value = lang_hooks.tree_inlining.convert_parm_for_inlining
1143               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
1144
1145       setup_one_parameter (id, p, value, fn, bb, &vars);
1146     }
1147
1148   /* Initialize the static chain.  */
1149   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1150   gcc_assert (fn != current_function_decl);
1151   if (p)
1152     {
1153       /* No static chain?  Seems like a bug in tree-nested.c.  */
1154       gcc_assert (static_chain);
1155
1156       setup_one_parameter (id, p, static_chain, fn, bb, &vars);
1157     }
1158
1159   declare_inline_vars (id->block, vars);
1160 }
1161
1162 /* Declare a return variable to replace the RESULT_DECL for the
1163    function we are calling.  An appropriate DECL_STMT is returned.
1164    The USE_STMT is filled to contain a use of the declaration to
1165    indicate the return value of the function.
1166
1167    RETURN_SLOT_ADDR, if non-null, was a fake parameter that
1168    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
1169    the MODIFY_EXPR to which this call is the RHS.
1170
1171    The return value is a (possibly null) value that is the result of the
1172    function as seen by the callee.  *USE_P is a (possibly null) value that
1173    holds the result as seen by the caller.  */
1174
1175 static tree
1176 declare_return_variable (copy_body_data *id, tree return_slot_addr,
1177                          tree modify_dest, tree *use_p)
1178 {
1179   tree callee = id->src_fn;
1180   tree caller = id->dst_fn;
1181   tree result = DECL_RESULT (callee);
1182   tree callee_type = TREE_TYPE (result);
1183   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
1184   tree var, use;
1185
1186   /* We don't need to do anything for functions that don't return
1187      anything.  */
1188   if (!result || VOID_TYPE_P (callee_type))
1189     {
1190       *use_p = NULL_TREE;
1191       return NULL_TREE;
1192     }
1193
1194   /* If there was a return slot, then the return value is the
1195      dereferenced address of that object.  */
1196   if (return_slot_addr)
1197     {
1198       /* The front end shouldn't have used both return_slot_addr and
1199          a modify expression.  */
1200       gcc_assert (!modify_dest);
1201       if (DECL_BY_REFERENCE (result))
1202         var = return_slot_addr;
1203       else
1204         var = build_fold_indirect_ref (return_slot_addr);
1205       if (TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1206           && !DECL_COMPLEX_GIMPLE_REG_P (result)
1207           && DECL_P (var))
1208         DECL_COMPLEX_GIMPLE_REG_P (var) = 0;
1209       use = NULL;
1210       goto done;
1211     }
1212
1213   /* All types requiring non-trivial constructors should have been handled.  */
1214   gcc_assert (!TREE_ADDRESSABLE (callee_type));
1215
1216   /* Attempt to avoid creating a new temporary variable.  */
1217   if (modify_dest)
1218     {
1219       bool use_it = false;
1220
1221       /* We can't use MODIFY_DEST if there's type promotion involved.  */
1222       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
1223         use_it = false;
1224
1225       /* ??? If we're assigning to a variable sized type, then we must
1226          reuse the destination variable, because we've no good way to
1227          create variable sized temporaries at this point.  */
1228       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
1229         use_it = true;
1230
1231       /* If the callee cannot possibly modify MODIFY_DEST, then we can
1232          reuse it as the result of the call directly.  Don't do this if
1233          it would promote MODIFY_DEST to addressable.  */
1234       else if (TREE_ADDRESSABLE (result))
1235         use_it = false;
1236       else
1237         {
1238           tree base_m = get_base_address (modify_dest);
1239
1240           /* If the base isn't a decl, then it's a pointer, and we don't
1241              know where that's going to go.  */
1242           if (!DECL_P (base_m))
1243             use_it = false;
1244           else if (is_global_var (base_m))
1245             use_it = false;
1246           else if (TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1247                    && !DECL_COMPLEX_GIMPLE_REG_P (result)
1248                    && DECL_COMPLEX_GIMPLE_REG_P (base_m))
1249             use_it = false;
1250           else if (!TREE_ADDRESSABLE (base_m))
1251             use_it = true;
1252         }
1253
1254       if (use_it)
1255         {
1256           var = modify_dest;
1257           use = NULL;
1258           goto done;
1259         }
1260     }
1261
1262   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
1263
1264   var = copy_decl_to_var (result, id);
1265
1266   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1267   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
1268     = tree_cons (NULL_TREE, var,
1269                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
1270
1271   /* Do not have the rest of GCC warn about this variable as it should
1272      not be visible to the user.  */
1273   TREE_NO_WARNING (var) = 1;
1274
1275   /* Build the use expr.  If the return type of the function was
1276      promoted, convert it back to the expected type.  */
1277   use = var;
1278   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
1279     use = fold_convert (caller_type, var);
1280
1281   STRIP_USELESS_TYPE_CONVERSION (use);
1282
1283  done:
1284   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
1285      way, when the RESULT_DECL is encountered, it will be
1286      automatically replaced by the VAR_DECL.  */
1287   insert_decl_map (id, result, var);
1288
1289   /* Remember this so we can ignore it in remap_decls.  */
1290   id->retvar = var;
1291
1292   *use_p = use;
1293   return var;
1294 }
1295
1296 /* Returns nonzero if a function can be inlined as a tree.  */
1297
1298 bool
1299 tree_inlinable_function_p (tree fn)
1300 {
1301   return inlinable_function_p (fn);
1302 }
1303
1304 static const char *inline_forbidden_reason;
1305
1306 static tree
1307 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
1308                       void *fnp)
1309 {
1310   tree node = *nodep;
1311   tree fn = (tree) fnp;
1312   tree t;
1313
1314   switch (TREE_CODE (node))
1315     {
1316     case CALL_EXPR:
1317       /* Refuse to inline alloca call unless user explicitly forced so as
1318          this may change program's memory overhead drastically when the
1319          function using alloca is called in loop.  In GCC present in
1320          SPEC2000 inlining into schedule_block cause it to require 2GB of
1321          RAM instead of 256MB.  */
1322       if (alloca_call_p (node)
1323           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1324         {
1325           inline_forbidden_reason
1326             = G_("function %q+F can never be inlined because it uses "
1327                  "alloca (override using the always_inline attribute)");
1328           return node;
1329         }
1330       t = get_callee_fndecl (node);
1331       if (! t)
1332         break;
1333
1334       /* We cannot inline functions that call setjmp.  */
1335       if (setjmp_call_p (t))
1336         {
1337           inline_forbidden_reason
1338             = G_("function %q+F can never be inlined because it uses setjmp");
1339           return node;
1340         }
1341
1342       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
1343         switch (DECL_FUNCTION_CODE (t))
1344           {
1345             /* We cannot inline functions that take a variable number of
1346                arguments.  */
1347           case BUILT_IN_VA_START:
1348           case BUILT_IN_STDARG_START:
1349           case BUILT_IN_NEXT_ARG:
1350           case BUILT_IN_VA_END:
1351             inline_forbidden_reason
1352               = G_("function %q+F can never be inlined because it "
1353                    "uses variable argument lists");
1354             return node;
1355
1356           case BUILT_IN_LONGJMP:
1357             /* We can't inline functions that call __builtin_longjmp at
1358                all.  The non-local goto machinery really requires the
1359                destination be in a different function.  If we allow the
1360                function calling __builtin_longjmp to be inlined into the
1361                function calling __builtin_setjmp, Things will Go Awry.  */
1362             inline_forbidden_reason
1363               = G_("function %q+F can never be inlined because "
1364                    "it uses setjmp-longjmp exception handling");
1365             return node;
1366
1367           case BUILT_IN_NONLOCAL_GOTO:
1368             /* Similarly.  */
1369             inline_forbidden_reason
1370               = G_("function %q+F can never be inlined because "
1371                    "it uses non-local goto");
1372             return node;
1373
1374           case BUILT_IN_RETURN:
1375           case BUILT_IN_APPLY_ARGS:
1376             /* If a __builtin_apply_args caller would be inlined,
1377                it would be saving arguments of the function it has
1378                been inlined into.  Similarly __builtin_return would
1379                return from the function the inline has been inlined into.  */
1380             inline_forbidden_reason
1381               = G_("function %q+F can never be inlined because "
1382                    "it uses __builtin_return or __builtin_apply_args");
1383             return node;
1384
1385           default:
1386             break;
1387           }
1388       break;
1389
1390     case GOTO_EXPR:
1391       t = TREE_OPERAND (node, 0);
1392
1393       /* We will not inline a function which uses computed goto.  The
1394          addresses of its local labels, which may be tucked into
1395          global storage, are of course not constant across
1396          instantiations, which causes unexpected behavior.  */
1397       if (TREE_CODE (t) != LABEL_DECL)
1398         {
1399           inline_forbidden_reason
1400             = G_("function %q+F can never be inlined "
1401                  "because it contains a computed goto");
1402           return node;
1403         }
1404       break;
1405
1406     case LABEL_EXPR:
1407       t = TREE_OPERAND (node, 0);
1408       if (DECL_NONLOCAL (t))
1409         {
1410           /* We cannot inline a function that receives a non-local goto
1411              because we cannot remap the destination label used in the
1412              function that is performing the non-local goto.  */
1413           inline_forbidden_reason
1414             = G_("function %q+F can never be inlined "
1415                  "because it receives a non-local goto");
1416           return node;
1417         }
1418       break;
1419
1420     case RECORD_TYPE:
1421     case UNION_TYPE:
1422       /* We cannot inline a function of the form
1423
1424            void F (int i) { struct S { int ar[i]; } s; }
1425
1426          Attempting to do so produces a catch-22.
1427          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1428          UNION_TYPE nodes, then it goes into infinite recursion on a
1429          structure containing a pointer to its own type.  If it doesn't,
1430          then the type node for S doesn't get adjusted properly when
1431          F is inlined.
1432
1433          ??? This is likely no longer true, but it's too late in the 4.0
1434          cycle to try to find out.  This should be checked for 4.1.  */
1435       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1436         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1437           {
1438             inline_forbidden_reason
1439               = G_("function %q+F can never be inlined "
1440                    "because it uses variable sized variables");
1441             return node;
1442           }
1443
1444     default:
1445       break;
1446     }
1447
1448   return NULL_TREE;
1449 }
1450
1451 /* Return subexpression representing possible alloca call, if any.  */
1452 static tree
1453 inline_forbidden_p (tree fndecl)
1454 {
1455   location_t saved_loc = input_location;
1456   block_stmt_iterator bsi;
1457   basic_block bb;
1458   tree ret = NULL_TREE;
1459
1460   FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fndecl))
1461     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1462       {
1463         ret = walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
1464                                     inline_forbidden_p_1, fndecl);
1465         if (ret)
1466           goto egress;
1467       }
1468
1469 egress:
1470   input_location = saved_loc;
1471   return ret;
1472 }
1473
1474 /* Returns nonzero if FN is a function that does not have any
1475    fundamental inline blocking properties.  */
1476
1477 static bool
1478 inlinable_function_p (tree fn)
1479 {
1480   bool inlinable = true;
1481
1482   /* If we've already decided this function shouldn't be inlined,
1483      there's no need to check again.  */
1484   if (DECL_UNINLINABLE (fn))
1485     return false;
1486
1487   /* See if there is any language-specific reason it cannot be
1488      inlined.  (It is important that this hook be called early because
1489      in C++ it may result in template instantiation.)
1490      If the function is not inlinable for language-specific reasons,
1491      it is left up to the langhook to explain why.  */
1492   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1493
1494   /* If we don't have the function body available, we can't inline it.
1495      However, this should not be recorded since we also get here for
1496      forward declared inline functions.  Therefore, return at once.  */
1497   if (!DECL_SAVED_TREE (fn))
1498     return false;
1499
1500   /* If we're not inlining at all, then we cannot inline this function.  */
1501   else if (!flag_inline_trees)
1502     inlinable = false;
1503
1504   /* Only try to inline functions if DECL_INLINE is set.  This should be
1505      true for all functions declared `inline', and for all other functions
1506      as well with -finline-functions.
1507
1508      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1509      it's the front-end that must set DECL_INLINE in this case, because
1510      dwarf2out loses if a function that does not have DECL_INLINE set is
1511      inlined anyway.  That is why we have both DECL_INLINE and
1512      DECL_DECLARED_INLINE_P.  */
1513   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1514             here should be redundant.  */
1515   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1516     inlinable = false;
1517
1518   else if (inline_forbidden_p (fn))
1519     {
1520       /* See if we should warn about uninlinable functions.  Previously,
1521          some of these warnings would be issued while trying to expand
1522          the function inline, but that would cause multiple warnings
1523          about functions that would for example call alloca.  But since
1524          this a property of the function, just one warning is enough.
1525          As a bonus we can now give more details about the reason why a
1526          function is not inlinable.
1527          We only warn for functions declared `inline' by the user.  */
1528       bool do_warning = (warn_inline
1529                          && DECL_INLINE (fn)
1530                          && DECL_DECLARED_INLINE_P (fn)
1531                          && !DECL_IN_SYSTEM_HEADER (fn));
1532
1533       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1534         sorry (inline_forbidden_reason, fn);
1535       else if (do_warning)
1536         warning (OPT_Winline, inline_forbidden_reason, fn);
1537
1538       inlinable = false;
1539     }
1540
1541   /* Squirrel away the result so that we don't have to check again.  */
1542   DECL_UNINLINABLE (fn) = !inlinable;
1543
1544   return inlinable;
1545 }
1546
1547 /* Estimate the cost of a memory move.  Use machine dependent
1548    word size and take possible memcpy call into account.  */
1549
1550 int
1551 estimate_move_cost (tree type)
1552 {
1553   HOST_WIDE_INT size;
1554
1555   size = int_size_in_bytes (type);
1556
1557   if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1558     /* Cost of a memcpy call, 3 arguments and the call.  */
1559     return 4;
1560   else
1561     return ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1562 }
1563
1564 /* Used by estimate_num_insns.  Estimate number of instructions seen
1565    by given statement.  */
1566
1567 static tree
1568 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1569 {
1570   int *count = (int *) data;
1571   tree x = *tp;
1572
1573   if (IS_TYPE_OR_DECL_P (x))
1574     {
1575       *walk_subtrees = 0;
1576       return NULL;
1577     }
1578   /* Assume that constants and references counts nothing.  These should
1579      be majorized by amount of operations among them we count later
1580      and are common target of CSE and similar optimizations.  */
1581   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1582     return NULL;
1583
1584   switch (TREE_CODE (x))
1585     {
1586     /* Containers have no cost.  */
1587     case TREE_LIST:
1588     case TREE_VEC:
1589     case BLOCK:
1590     case COMPONENT_REF:
1591     case BIT_FIELD_REF:
1592     case INDIRECT_REF:
1593     case ALIGN_INDIRECT_REF:
1594     case MISALIGNED_INDIRECT_REF:
1595     case ARRAY_REF:
1596     case ARRAY_RANGE_REF:
1597     case OBJ_TYPE_REF:
1598     case EXC_PTR_EXPR: /* ??? */
1599     case FILTER_EXPR: /* ??? */
1600     case COMPOUND_EXPR:
1601     case BIND_EXPR:
1602     case WITH_CLEANUP_EXPR:
1603     case NOP_EXPR:
1604     case VIEW_CONVERT_EXPR:
1605     case SAVE_EXPR:
1606     case ADDR_EXPR:
1607     case COMPLEX_EXPR:
1608     case RANGE_EXPR:
1609     case CASE_LABEL_EXPR:
1610     case SSA_NAME:
1611     case CATCH_EXPR:
1612     case EH_FILTER_EXPR:
1613     case STATEMENT_LIST:
1614     case ERROR_MARK:
1615     case NON_LVALUE_EXPR:
1616     case FDESC_EXPR:
1617     case VA_ARG_EXPR:
1618     case TRY_CATCH_EXPR:
1619     case TRY_FINALLY_EXPR:
1620     case LABEL_EXPR:
1621     case GOTO_EXPR:
1622     case RETURN_EXPR:
1623     case EXIT_EXPR:
1624     case LOOP_EXPR:
1625     case PHI_NODE:
1626     case WITH_SIZE_EXPR:
1627     case OMP_CLAUSE:
1628     case OMP_RETURN:
1629     case OMP_CONTINUE:
1630       break;
1631
1632     /* We don't account constants for now.  Assume that the cost is amortized
1633        by operations that do use them.  We may re-consider this decision once
1634        we are able to optimize the tree before estimating its size and break
1635        out static initializers.  */
1636     case IDENTIFIER_NODE:
1637     case INTEGER_CST:
1638     case REAL_CST:
1639     case COMPLEX_CST:
1640     case VECTOR_CST:
1641     case STRING_CST:
1642       *walk_subtrees = 0;
1643       return NULL;
1644
1645     /* Try to estimate the cost of assignments.  We have three cases to
1646        deal with:
1647         1) Simple assignments to registers;
1648         2) Stores to things that must live in memory.  This includes
1649            "normal" stores to scalars, but also assignments of large
1650            structures, or constructors of big arrays;
1651         3) TARGET_EXPRs.
1652
1653        Let us look at the first two cases, assuming we have "a = b + C":
1654        <modify_expr <var_decl "a"> <plus_expr <var_decl "b"> <constant C>>
1655        If "a" is a GIMPLE register, the assignment to it is free on almost
1656        any target, because "a" usually ends up in a real register.  Hence
1657        the only cost of this expression comes from the PLUS_EXPR, and we
1658        can ignore the MODIFY_EXPR.
1659        If "a" is not a GIMPLE register, the assignment to "a" will most
1660        likely be a real store, so the cost of the MODIFY_EXPR is the cost
1661        of moving something into "a", which we compute using the function
1662        estimate_move_cost.
1663
1664        The third case deals with TARGET_EXPRs, for which the semantics are
1665        that a temporary is assigned, unless the TARGET_EXPR itself is being
1666        assigned to something else.  In the latter case we do not need the
1667        temporary.  E.g. in <modify_expr <var_decl "a"> <target_expr>>, the
1668        MODIFY_EXPR is free.  */
1669     case INIT_EXPR:
1670     case MODIFY_EXPR:
1671       /* Is the right and side a TARGET_EXPR?  */
1672       if (TREE_CODE (TREE_OPERAND (x, 1)) == TARGET_EXPR)
1673         break;
1674       /* ... fall through ...  */
1675
1676     case TARGET_EXPR:
1677       x = TREE_OPERAND (x, 0);
1678       /* Is this an assignments to a register?  */
1679       if (is_gimple_reg (x))
1680         break;
1681       /* Otherwise it's a store, so fall through to compute the move cost.  */
1682
1683     case CONSTRUCTOR:
1684       *count += estimate_move_cost (TREE_TYPE (x));
1685       break;
1686
1687     /* Assign cost of 1 to usual operations.
1688        ??? We may consider mapping RTL costs to this.  */
1689     case COND_EXPR:
1690     case VEC_COND_EXPR:
1691
1692     case PLUS_EXPR:
1693     case MINUS_EXPR:
1694     case MULT_EXPR:
1695
1696     case FIX_TRUNC_EXPR:
1697     case FIX_CEIL_EXPR:
1698     case FIX_FLOOR_EXPR:
1699     case FIX_ROUND_EXPR:
1700
1701     case NEGATE_EXPR:
1702     case FLOAT_EXPR:
1703     case MIN_EXPR:
1704     case MAX_EXPR:
1705     case ABS_EXPR:
1706
1707     case LSHIFT_EXPR:
1708     case RSHIFT_EXPR:
1709     case LROTATE_EXPR:
1710     case RROTATE_EXPR:
1711     case VEC_LSHIFT_EXPR:
1712     case VEC_RSHIFT_EXPR:
1713
1714     case BIT_IOR_EXPR:
1715     case BIT_XOR_EXPR:
1716     case BIT_AND_EXPR:
1717     case BIT_NOT_EXPR:
1718
1719     case TRUTH_ANDIF_EXPR:
1720     case TRUTH_ORIF_EXPR:
1721     case TRUTH_AND_EXPR:
1722     case TRUTH_OR_EXPR:
1723     case TRUTH_XOR_EXPR:
1724     case TRUTH_NOT_EXPR:
1725
1726     case LT_EXPR:
1727     case LE_EXPR:
1728     case GT_EXPR:
1729     case GE_EXPR:
1730     case EQ_EXPR:
1731     case NE_EXPR:
1732     case ORDERED_EXPR:
1733     case UNORDERED_EXPR:
1734
1735     case UNLT_EXPR:
1736     case UNLE_EXPR:
1737     case UNGT_EXPR:
1738     case UNGE_EXPR:
1739     case UNEQ_EXPR:
1740     case LTGT_EXPR:
1741
1742     case CONVERT_EXPR:
1743
1744     case CONJ_EXPR:
1745
1746     case PREDECREMENT_EXPR:
1747     case PREINCREMENT_EXPR:
1748     case POSTDECREMENT_EXPR:
1749     case POSTINCREMENT_EXPR:
1750
1751     case SWITCH_EXPR:
1752
1753     case ASM_EXPR:
1754
1755     case REALIGN_LOAD_EXPR:
1756
1757     case REDUC_MAX_EXPR:
1758     case REDUC_MIN_EXPR:
1759     case REDUC_PLUS_EXPR:
1760     case WIDEN_SUM_EXPR:
1761     case DOT_PROD_EXPR:
1762
1763     case WIDEN_MULT_EXPR:
1764
1765     case RESX_EXPR:
1766       *count += 1;
1767       break;
1768
1769     /* Few special cases of expensive operations.  This is useful
1770        to avoid inlining on functions having too many of these.  */
1771     case TRUNC_DIV_EXPR:
1772     case CEIL_DIV_EXPR:
1773     case FLOOR_DIV_EXPR:
1774     case ROUND_DIV_EXPR:
1775     case EXACT_DIV_EXPR:
1776     case TRUNC_MOD_EXPR:
1777     case CEIL_MOD_EXPR:
1778     case FLOOR_MOD_EXPR:
1779     case ROUND_MOD_EXPR:
1780     case RDIV_EXPR:
1781       *count += 10;
1782       break;
1783     case CALL_EXPR:
1784       {
1785         tree decl = get_callee_fndecl (x);
1786         tree arg;
1787
1788         if (decl && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1789           switch (DECL_FUNCTION_CODE (decl))
1790             {
1791             case BUILT_IN_CONSTANT_P:
1792               *walk_subtrees = 0;
1793               return NULL_TREE;
1794             case BUILT_IN_EXPECT:
1795               return NULL_TREE;
1796             default:
1797               break;
1798             }
1799
1800         /* Our cost must be kept in sync with cgraph_estimate_size_after_inlining
1801            that does use function declaration to figure out the arguments.  */
1802         if (!decl)
1803           {
1804             for (arg = TREE_OPERAND (x, 1); arg; arg = TREE_CHAIN (arg))
1805               *count += estimate_move_cost (TREE_TYPE (TREE_VALUE (arg)));
1806           }
1807         else
1808           {
1809             for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
1810               *count += estimate_move_cost (TREE_TYPE (arg));
1811           }
1812
1813         *count += PARAM_VALUE (PARAM_INLINE_CALL_COST);
1814         break;
1815       }
1816
1817     case OMP_PARALLEL:
1818     case OMP_FOR:
1819     case OMP_SECTIONS:
1820     case OMP_SINGLE:
1821     case OMP_SECTION:
1822     case OMP_MASTER:
1823     case OMP_ORDERED:
1824     case OMP_CRITICAL:
1825     case OMP_ATOMIC:
1826       /* OpenMP directives are generally very expensive.  */
1827       *count += 40;
1828       break;
1829
1830     default:
1831       gcc_unreachable ();
1832     }
1833   return NULL;
1834 }
1835
1836 /* Estimate number of instructions that will be created by expanding EXPR.  */
1837
1838 int
1839 estimate_num_insns (tree expr)
1840 {
1841   int num = 0;
1842   struct pointer_set_t *visited_nodes;
1843   basic_block bb;
1844   block_stmt_iterator bsi;
1845   struct function *my_function;
1846
1847   /* If we're given an entire function, walk the CFG.  */
1848   if (TREE_CODE (expr) == FUNCTION_DECL)
1849     {
1850       my_function = DECL_STRUCT_FUNCTION (expr);
1851       gcc_assert (my_function && my_function->cfg);
1852       visited_nodes = pointer_set_create ();
1853       FOR_EACH_BB_FN (bb, my_function)
1854         {
1855           for (bsi = bsi_start (bb);
1856                !bsi_end_p (bsi);
1857                bsi_next (&bsi))
1858             {
1859               walk_tree (bsi_stmt_ptr (bsi), estimate_num_insns_1,
1860                          &num, visited_nodes);
1861             }
1862         }
1863       pointer_set_destroy (visited_nodes);
1864     }
1865   else
1866     walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1867
1868   return num;
1869 }
1870
1871 typedef struct function *function_p;
1872
1873 DEF_VEC_P(function_p);
1874 DEF_VEC_ALLOC_P(function_p,heap);
1875
1876 /* Initialized with NOGC, making this poisonous to the garbage collector.  */
1877 static VEC(function_p,heap) *cfun_stack;
1878
1879 void
1880 push_cfun (struct function *new_cfun)
1881 {
1882   VEC_safe_push (function_p, heap, cfun_stack, cfun);
1883   cfun = new_cfun;
1884 }
1885
1886 void
1887 pop_cfun (void)
1888 {
1889   cfun = VEC_pop (function_p, cfun_stack);
1890 }
1891
1892 /* Install new lexical TREE_BLOCK underneath 'current_block'.  */
1893 static void
1894 add_lexical_block (tree current_block, tree new_block)
1895 {
1896   tree *blk_p;
1897
1898   /* Walk to the last sub-block.  */
1899   for (blk_p = &BLOCK_SUBBLOCKS (current_block);
1900        *blk_p;
1901        blk_p = &TREE_CHAIN (*blk_p))
1902     ;
1903   *blk_p = new_block;
1904   BLOCK_SUPERCONTEXT (new_block) = current_block;
1905 }
1906
1907 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1908
1909 static bool
1910 expand_call_inline (basic_block bb, tree stmt, tree *tp, void *data)
1911 {
1912   copy_body_data *id;
1913   tree t;
1914   tree use_retvar;
1915   tree fn;
1916   splay_tree st;
1917   tree args;
1918   tree return_slot_addr;
1919   tree modify_dest;
1920   location_t saved_location;
1921   struct cgraph_edge *cg_edge;
1922   const char *reason;
1923   basic_block return_block;
1924   edge e;
1925   block_stmt_iterator bsi, stmt_bsi;
1926   bool successfully_inlined = FALSE;
1927   tree t_step;
1928   tree var;
1929   tree decl;
1930
1931   /* See what we've got.  */
1932   id = (copy_body_data *) data;
1933   t = *tp;
1934
1935   /* Set input_location here so we get the right instantiation context
1936      if we call instantiate_decl from inlinable_function_p.  */
1937   saved_location = input_location;
1938   if (EXPR_HAS_LOCATION (t))
1939     input_location = EXPR_LOCATION (t);
1940
1941   /* From here on, we're only interested in CALL_EXPRs.  */
1942   if (TREE_CODE (t) != CALL_EXPR)
1943     goto egress;
1944
1945   /* First, see if we can figure out what function is being called.
1946      If we cannot, then there is no hope of inlining the function.  */
1947   fn = get_callee_fndecl (t);
1948   if (!fn)
1949     goto egress;
1950
1951   /* Turn forward declarations into real ones.  */
1952   fn = cgraph_node (fn)->decl;
1953
1954   /* If fn is a declaration of a function in a nested scope that was
1955      globally declared inline, we don't set its DECL_INITIAL.
1956      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1957      C++ front-end uses it for cdtors to refer to their internal
1958      declarations, that are not real functions.  Fortunately those
1959      don't have trees to be saved, so we can tell by checking their
1960      DECL_SAVED_TREE.  */
1961   if (! DECL_INITIAL (fn)
1962       && DECL_ABSTRACT_ORIGIN (fn)
1963       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1964     fn = DECL_ABSTRACT_ORIGIN (fn);
1965
1966   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1967      Kill this check once this is fixed.  */
1968   if (!id->dst_node->analyzed)
1969     goto egress;
1970
1971   cg_edge = cgraph_edge (id->dst_node, stmt);
1972
1973   /* Constant propagation on argument done during previous inlining
1974      may create new direct call.  Produce an edge for it.  */
1975   if (!cg_edge)
1976     {
1977       struct cgraph_node *dest = cgraph_node (fn);
1978
1979       /* We have missing edge in the callgraph.  This can happen in one case
1980          where previous inlining turned indirect call into direct call by
1981          constant propagating arguments.  In all other cases we hit a bug
1982          (incorrect node sharing is most common reason for missing edges.  */
1983       gcc_assert (dest->needed || !flag_unit_at_a_time);
1984       cgraph_create_edge (id->dst_node, dest, stmt,
1985                           bb->count, bb->loop_depth)->inline_failed
1986         = N_("originally indirect function call not considered for inlining");
1987       goto egress;
1988     }
1989
1990   /* Don't try to inline functions that are not well-suited to
1991      inlining.  */
1992   if (!cgraph_inline_p (cg_edge, &reason))
1993     {
1994       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
1995           /* Avoid warnings during early inline pass. */
1996           && (!flag_unit_at_a_time || cgraph_global_info_ready))
1997         {
1998           sorry ("inlining failed in call to %q+F: %s", fn, reason);
1999           sorry ("called from here");
2000         }
2001       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
2002                && !DECL_IN_SYSTEM_HEADER (fn)
2003                && strlen (reason)
2004                && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn))
2005                /* Avoid warnings during early inline pass. */
2006                && (!flag_unit_at_a_time || cgraph_global_info_ready))
2007         {
2008           warning (OPT_Winline, "inlining failed in call to %q+F: %s",
2009                    fn, reason);
2010           warning (OPT_Winline, "called from here");
2011         }
2012       goto egress;
2013     }
2014   fn = cg_edge->callee->decl;
2015
2016 #ifdef ENABLE_CHECKING
2017   if (cg_edge->callee->decl != id->dst_node->decl)
2018     verify_cgraph_node (cg_edge->callee);
2019 #endif
2020
2021   /* We will be inlining this callee.  */
2022
2023   id->eh_region = lookup_stmt_eh_region (stmt);
2024
2025   /* Split the block holding the CALL_EXPR.  */
2026
2027   e = split_block (bb, stmt);
2028   bb = e->src;
2029   return_block = e->dest;
2030   remove_edge (e);
2031
2032   /* split_block splits before the statement, work around this by moving
2033      the call into the first half_bb.  Not pretty, but seems easier than
2034      doing the CFG manipulation by hand when the CALL_EXPR is in the last
2035      statement in BB.  */
2036   stmt_bsi = bsi_last (bb);
2037   bsi = bsi_start (return_block);
2038   if (!bsi_end_p (bsi))
2039     bsi_move_before (&stmt_bsi, &bsi);
2040   else
2041     {
2042       tree stmt = bsi_stmt (stmt_bsi);
2043       bsi_remove (&stmt_bsi, false);
2044       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2045     }
2046   stmt_bsi = bsi_start (return_block);
2047
2048   /* Build a block containing code to initialize the arguments, the
2049      actual inline expansion of the body, and a label for the return
2050      statements within the function to jump to.  The type of the
2051      statement expression is the return type of the function call.  */
2052   id->block = make_node (BLOCK);
2053   BLOCK_ABSTRACT_ORIGIN (id->block) = fn;
2054   BLOCK_SOURCE_LOCATION (id->block) = input_location;
2055   add_lexical_block (TREE_BLOCK (stmt), id->block);
2056
2057   /* Local declarations will be replaced by their equivalents in this
2058      map.  */
2059   st = id->decl_map;
2060   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
2061                                  NULL, NULL);
2062
2063   /* Initialize the parameters.  */
2064   args = TREE_OPERAND (t, 1);
2065
2066   /* Record the function we are about to inline.  */
2067   id->src_fn = fn;
2068   id->src_node = cg_edge->callee;
2069
2070   initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2), fn, bb);
2071
2072   if (DECL_INITIAL (fn))
2073     add_lexical_block (id->block, remap_blocks (DECL_INITIAL (fn), id));
2074
2075   /* Return statements in the function body will be replaced by jumps
2076      to the RET_LABEL.  */
2077
2078   gcc_assert (DECL_INITIAL (fn));
2079   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
2080
2081   /* Find the lhs to which the result of this call is assigned.  */
2082   return_slot_addr = NULL;
2083   if (TREE_CODE (stmt) == MODIFY_EXPR)
2084     {
2085       modify_dest = TREE_OPERAND (stmt, 0);
2086
2087       /* The function which we are inlining might not return a value,
2088          in which case we should issue a warning that the function
2089          does not return a value.  In that case the optimizers will
2090          see that the variable to which the value is assigned was not
2091          initialized.  We do not want to issue a warning about that
2092          uninitialized variable.  */
2093       if (DECL_P (modify_dest))
2094         TREE_NO_WARNING (modify_dest) = 1;
2095       if (CALL_EXPR_RETURN_SLOT_OPT (t))
2096         {
2097           return_slot_addr = build_fold_addr_expr (modify_dest);
2098           STRIP_USELESS_TYPE_CONVERSION (return_slot_addr);
2099           modify_dest = NULL;
2100         }
2101     }
2102   else
2103     modify_dest = NULL;
2104
2105   /* Declare the return variable for the function.  */
2106   decl = declare_return_variable (id, return_slot_addr,
2107                                   modify_dest, &use_retvar);
2108   /* Do this only if declare_return_variable created a new one.  */
2109   if (decl && !return_slot_addr && decl != modify_dest)
2110     declare_inline_vars (id->block, decl);
2111
2112   /* This is it.  Duplicate the callee body.  Assume callee is
2113      pre-gimplified.  Note that we must not alter the caller
2114      function in any way before this point, as this CALL_EXPR may be
2115      a self-referential call; if we're calling ourselves, we need to
2116      duplicate our body before altering anything.  */
2117   copy_body (id, bb->count, bb->frequency, bb, return_block);
2118
2119   /* Add local vars in this inlined callee to caller.  */
2120   t_step = id->src_cfun->unexpanded_var_list;
2121   for (; t_step; t_step = TREE_CHAIN (t_step))
2122     {
2123       var = TREE_VALUE (t_step);
2124       if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
2125         cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
2126                                                cfun->unexpanded_var_list);
2127       else
2128         cfun->unexpanded_var_list = tree_cons (NULL_TREE, remap_decl (var, id),
2129                                                cfun->unexpanded_var_list);
2130     }
2131
2132   /* Clean up.  */
2133   splay_tree_delete (id->decl_map);
2134   id->decl_map = st;
2135
2136   /* If the inlined function returns a result that we care about,
2137      clobber the CALL_EXPR with a reference to the return variable.  */
2138   if (use_retvar && (TREE_CODE (bsi_stmt (stmt_bsi)) != CALL_EXPR))
2139     {
2140       *tp = use_retvar;
2141       maybe_clean_or_replace_eh_stmt (stmt, stmt);
2142     }
2143   else
2144     /* We're modifying a TSI owned by gimple_expand_calls_inline();
2145        tsi_delink() will leave the iterator in a sane state.  */
2146     bsi_remove (&stmt_bsi, true);
2147
2148   bsi_next (&bsi);
2149   if (bsi_end_p (bsi))
2150     tree_purge_dead_eh_edges (return_block);
2151
2152   /* If the value of the new expression is ignored, that's OK.  We
2153      don't warn about this for CALL_EXPRs, so we shouldn't warn about
2154      the equivalent inlined version either.  */
2155   TREE_USED (*tp) = 1;
2156
2157   /* Output the inlining info for this abstract function, since it has been
2158      inlined.  If we don't do this now, we can lose the information about the
2159      variables in the function when the blocks get blown away as soon as we
2160      remove the cgraph node.  */
2161   (*debug_hooks->outlining_inline_function) (cg_edge->callee->decl);
2162
2163   /* Update callgraph if needed.  */
2164   cgraph_remove_node (cg_edge->callee);
2165
2166   id->block = NULL_TREE;
2167   successfully_inlined = TRUE;
2168
2169  egress:
2170   input_location = saved_location;
2171   return successfully_inlined;
2172 }
2173
2174 /* Expand call statements reachable from STMT_P.
2175    We can only have CALL_EXPRs as the "toplevel" tree code or nested
2176    in a MODIFY_EXPR.  See tree-gimple.c:get_call_expr_in().  We can
2177    unfortunately not use that function here because we need a pointer
2178    to the CALL_EXPR, not the tree itself.  */
2179
2180 static bool
2181 gimple_expand_calls_inline (basic_block bb, copy_body_data *id)
2182 {
2183   block_stmt_iterator bsi;
2184
2185   /* Register specific tree functions.  */
2186   tree_register_cfg_hooks ();
2187   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2188     {
2189       tree *expr_p = bsi_stmt_ptr (bsi);
2190       tree stmt = *expr_p;
2191
2192       if (TREE_CODE (*expr_p) == MODIFY_EXPR)
2193         expr_p = &TREE_OPERAND (*expr_p, 1);
2194       if (TREE_CODE (*expr_p) == WITH_SIZE_EXPR)
2195         expr_p = &TREE_OPERAND (*expr_p, 0);
2196       if (TREE_CODE (*expr_p) == CALL_EXPR)
2197         if (expand_call_inline (bb, stmt, expr_p, id))
2198           return true;
2199     }
2200   return false;
2201 }
2202
2203 /* Expand calls to inline functions in the body of FN.  */
2204
2205 void
2206 optimize_inline_calls (tree fn)
2207 {
2208   copy_body_data id;
2209   tree prev_fn;
2210   basic_block bb;
2211   /* There is no point in performing inlining if errors have already
2212      occurred -- and we might crash if we try to inline invalid
2213      code.  */
2214   if (errorcount || sorrycount)
2215     return;
2216
2217   /* Clear out ID.  */
2218   memset (&id, 0, sizeof (id));
2219
2220   id.src_node = id.dst_node = cgraph_node (fn);
2221   id.dst_fn = fn;
2222   /* Or any functions that aren't finished yet.  */
2223   prev_fn = NULL_TREE;
2224   if (current_function_decl)
2225     {
2226       id.dst_fn = current_function_decl;
2227       prev_fn = current_function_decl;
2228     }
2229
2230   id.copy_decl = copy_decl_maybe_to_var;
2231   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2232   id.transform_new_cfg = false;
2233   id.transform_return_to_modify = true;
2234   id.transform_lang_insert_block = false;
2235
2236   push_gimplify_context ();
2237
2238   /* Reach the trees by walking over the CFG, and note the
2239      enclosing basic-blocks in the call edges.  */
2240   /* We walk the blocks going forward, because inlined function bodies
2241      will split id->current_basic_block, and the new blocks will
2242      follow it; we'll trudge through them, processing their CALL_EXPRs
2243      along the way.  */
2244   FOR_EACH_BB (bb)
2245     gimple_expand_calls_inline (bb, &id);
2246
2247   pop_gimplify_context (NULL);
2248   /* Renumber the (code) basic_blocks consecutively.  */
2249   compact_blocks ();
2250   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2251   number_blocks (fn);
2252
2253 #ifdef ENABLE_CHECKING
2254     {
2255       struct cgraph_edge *e;
2256
2257       verify_cgraph_node (id.dst_node);
2258
2259       /* Double check that we inlined everything we are supposed to inline.  */
2260       for (e = id.dst_node->callees; e; e = e->next_callee)
2261         gcc_assert (e->inline_failed);
2262     }
2263 #endif
2264   /* We need to rescale frequencies again to peak at REG_BR_PROB_BASE
2265      as inlining loops might increase the maximum.  */
2266   if (ENTRY_BLOCK_PTR->count)
2267     counts_to_freqs ();
2268   fold_cond_expr_cond ();
2269 }
2270
2271 /* FN is a function that has a complete body, and CLONE is a function whose
2272    body is to be set to a copy of FN, mapping argument declarations according
2273    to the ARG_MAP splay_tree.  */
2274
2275 void
2276 clone_body (tree clone, tree fn, void *arg_map)
2277 {
2278   copy_body_data id;
2279
2280   /* Clone the body, as if we were making an inline call.  But, remap the
2281      parameters in the callee to the parameters of caller.  */
2282   memset (&id, 0, sizeof (id));
2283   id.src_fn = fn;
2284   id.dst_fn = clone;
2285   id.src_cfun = DECL_STRUCT_FUNCTION (fn);
2286   id.decl_map = (splay_tree)arg_map;
2287
2288   id.copy_decl = copy_decl_no_change;
2289   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2290   id.transform_new_cfg = true;
2291   id.transform_return_to_modify = false;
2292   id.transform_lang_insert_block = true;
2293
2294   /* We're not inside any EH region.  */
2295   id.eh_region = -1;
2296
2297   /* Actually copy the body.  */
2298   append_to_statement_list_force (copy_generic_body (&id), &DECL_SAVED_TREE (clone));
2299 }
2300
2301 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2302
2303 tree
2304 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2305 {
2306   enum tree_code code = TREE_CODE (*tp);
2307
2308   /* We make copies of most nodes.  */
2309   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2310       || code == TREE_LIST
2311       || code == TREE_VEC
2312       || code == TYPE_DECL
2313       || code == OMP_CLAUSE)
2314     {
2315       /* Because the chain gets clobbered when we make a copy, we save it
2316          here.  */
2317       tree chain = TREE_CHAIN (*tp);
2318       tree new;
2319
2320       /* Copy the node.  */
2321       new = copy_node (*tp);
2322
2323       /* Propagate mudflap marked-ness.  */
2324       if (flag_mudflap && mf_marked_p (*tp))
2325         mf_mark (new);
2326
2327       *tp = new;
2328
2329       /* Now, restore the chain, if appropriate.  That will cause
2330          walk_tree to walk into the chain as well.  */
2331       if (code == PARM_DECL
2332           || code == TREE_LIST
2333           || code == OMP_CLAUSE)
2334         TREE_CHAIN (*tp) = chain;
2335
2336       /* For now, we don't update BLOCKs when we make copies.  So, we
2337          have to nullify all BIND_EXPRs.  */
2338       if (TREE_CODE (*tp) == BIND_EXPR)
2339         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2340     }
2341   else if (code == CONSTRUCTOR)
2342     {
2343       /* CONSTRUCTOR nodes need special handling because
2344          we need to duplicate the vector of elements.  */
2345       tree new;
2346
2347       new = copy_node (*tp);
2348
2349       /* Propagate mudflap marked-ness.  */
2350       if (flag_mudflap && mf_marked_p (*tp))
2351         mf_mark (new);
2352
2353       CONSTRUCTOR_ELTS (new) = VEC_copy (constructor_elt, gc,
2354                                          CONSTRUCTOR_ELTS (*tp));
2355       *tp = new;
2356     }
2357   else if (TREE_CODE_CLASS (code) == tcc_type)
2358     *walk_subtrees = 0;
2359   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2360     *walk_subtrees = 0;
2361   else if (TREE_CODE_CLASS (code) == tcc_constant)
2362     *walk_subtrees = 0;
2363   else
2364     gcc_assert (code != STATEMENT_LIST);
2365   return NULL_TREE;
2366 }
2367
2368 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2369    information indicating to what new SAVE_EXPR this one should be mapped,
2370    use that one.  Otherwise, create a new node and enter it in ST.  FN is
2371    the function into which the copy will be placed.  */
2372
2373 static void
2374 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2375 {
2376   splay_tree st = (splay_tree) st_;
2377   splay_tree_node n;
2378   tree t;
2379
2380   /* See if we already encountered this SAVE_EXPR.  */
2381   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2382
2383   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2384   if (!n)
2385     {
2386       t = copy_node (*tp);
2387
2388       /* Remember this SAVE_EXPR.  */
2389       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2390       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2391       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2392     }
2393   else
2394     {
2395       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2396       *walk_subtrees = 0;
2397       t = (tree) n->value;
2398     }
2399
2400   /* Replace this SAVE_EXPR with the copy.  */
2401   *tp = t;
2402 }
2403
2404 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2405    copies the declaration and enters it in the splay_tree in DATA (which is
2406    really an `copy_body_data *').  */
2407
2408 static tree
2409 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2410                         void *data)
2411 {
2412   copy_body_data *id = (copy_body_data *) data;
2413
2414   /* Don't walk into types.  */
2415   if (TYPE_P (*tp))
2416     *walk_subtrees = 0;
2417
2418   else if (TREE_CODE (*tp) == LABEL_EXPR)
2419     {
2420       tree decl = TREE_OPERAND (*tp, 0);
2421
2422       /* Copy the decl and remember the copy.  */
2423       insert_decl_map (id, decl, id->copy_decl (decl, id));
2424     }
2425
2426   return NULL_TREE;
2427 }
2428
2429 /* Perform any modifications to EXPR required when it is unsaved.  Does
2430    not recurse into EXPR's subtrees.  */
2431
2432 static void
2433 unsave_expr_1 (tree expr)
2434 {
2435   switch (TREE_CODE (expr))
2436     {
2437     case TARGET_EXPR:
2438       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2439          It's OK for this to happen if it was part of a subtree that
2440          isn't immediately expanded, such as operand 2 of another
2441          TARGET_EXPR.  */
2442       if (TREE_OPERAND (expr, 1))
2443         break;
2444
2445       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2446       TREE_OPERAND (expr, 3) = NULL_TREE;
2447       break;
2448
2449     default:
2450       break;
2451     }
2452 }
2453
2454 /* Called via walk_tree when an expression is unsaved.  Using the
2455    splay_tree pointed to by ST (which is really a `splay_tree'),
2456    remaps all local declarations to appropriate replacements.  */
2457
2458 static tree
2459 unsave_r (tree *tp, int *walk_subtrees, void *data)
2460 {
2461   copy_body_data *id = (copy_body_data *) data;
2462   splay_tree st = id->decl_map;
2463   splay_tree_node n;
2464
2465   /* Only a local declaration (variable or label).  */
2466   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2467       || TREE_CODE (*tp) == LABEL_DECL)
2468     {
2469       /* Lookup the declaration.  */
2470       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2471
2472       /* If it's there, remap it.  */
2473       if (n)
2474         *tp = (tree) n->value;
2475     }
2476
2477   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2478     copy_statement_list (tp);
2479   else if (TREE_CODE (*tp) == BIND_EXPR)
2480     copy_bind_expr (tp, walk_subtrees, id);
2481   else if (TREE_CODE (*tp) == SAVE_EXPR)
2482     remap_save_expr (tp, st, walk_subtrees);
2483   else
2484     {
2485       copy_tree_r (tp, walk_subtrees, NULL);
2486
2487       /* Do whatever unsaving is required.  */
2488       unsave_expr_1 (*tp);
2489     }
2490
2491   /* Keep iterating.  */
2492   return NULL_TREE;
2493 }
2494
2495 /* Copies everything in EXPR and replaces variables, labels
2496    and SAVE_EXPRs local to EXPR.  */
2497
2498 tree
2499 unsave_expr_now (tree expr)
2500 {
2501   copy_body_data id;
2502
2503   /* There's nothing to do for NULL_TREE.  */
2504   if (expr == 0)
2505     return expr;
2506
2507   /* Set up ID.  */
2508   memset (&id, 0, sizeof (id));
2509   id.src_fn = current_function_decl;
2510   id.dst_fn = current_function_decl;
2511   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2512
2513   id.copy_decl = copy_decl_no_change;
2514   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2515   id.transform_new_cfg = false;
2516   id.transform_return_to_modify = false;
2517   id.transform_lang_insert_block = false;
2518
2519   /* Walk the tree once to find local labels.  */
2520   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2521
2522   /* Walk the tree again, copying, remapping, and unsaving.  */
2523   walk_tree (&expr, unsave_r, &id, NULL);
2524
2525   /* Clean up.  */
2526   splay_tree_delete (id.decl_map);
2527
2528   return expr;
2529 }
2530
2531 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2532
2533 static tree
2534 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2535 {
2536   if (*tp == data)
2537     return (tree) data;
2538   else
2539     return NULL;
2540 }
2541
2542 bool
2543 debug_find_tree (tree top, tree search)
2544 {
2545   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2546 }
2547
2548
2549 /* Declare the variables created by the inliner.  Add all the variables in
2550    VARS to BIND_EXPR.  */
2551
2552 static void
2553 declare_inline_vars (tree block, tree vars)
2554 {
2555   tree t;
2556   for (t = vars; t; t = TREE_CHAIN (t))
2557     {
2558       DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2559       gcc_assert (!TREE_STATIC (t) && !TREE_ASM_WRITTEN (t));
2560       cfun->unexpanded_var_list =
2561         tree_cons (NULL_TREE, t,
2562                    cfun->unexpanded_var_list);
2563     }
2564
2565   if (block)
2566     BLOCK_VARS (block) = chainon (BLOCK_VARS (block), vars);
2567 }
2568
2569
2570 /* Copy NODE (which must be a DECL).  The DECL originally was in the FROM_FN,
2571    but now it will be in the TO_FN.  PARM_TO_VAR means enable PARM_DECL to
2572    VAR_DECL translation.  */
2573
2574 static tree
2575 copy_decl_for_dup_finish (copy_body_data *id, tree decl, tree copy)
2576 {
2577   /* Don't generate debug information for the copy if we wouldn't have
2578      generated it for the copy either.  */
2579   DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (decl);
2580   DECL_IGNORED_P (copy) = DECL_IGNORED_P (decl);
2581
2582   /* Set the DECL_ABSTRACT_ORIGIN so the debugging routines know what
2583      declaration inspired this copy.  */
2584   DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (decl);
2585
2586   /* The new variable/label has no RTL, yet.  */
2587   if (CODE_CONTAINS_STRUCT (TREE_CODE (copy), TS_DECL_WRTL)
2588       && !TREE_STATIC (copy) && !DECL_EXTERNAL (copy))
2589     SET_DECL_RTL (copy, NULL_RTX);
2590
2591   /* These args would always appear unused, if not for this.  */
2592   TREE_USED (copy) = 1;
2593
2594   /* Set the context for the new declaration.  */
2595   if (!DECL_CONTEXT (decl))
2596     /* Globals stay global.  */
2597     ;
2598   else if (DECL_CONTEXT (decl) != id->src_fn)
2599     /* Things that weren't in the scope of the function we're inlining
2600        from aren't in the scope we're inlining to, either.  */
2601     ;
2602   else if (TREE_STATIC (decl))
2603     /* Function-scoped static variables should stay in the original
2604        function.  */
2605     ;
2606   else
2607     /* Ordinary automatic local variables are now in the scope of the
2608        new function.  */
2609     DECL_CONTEXT (copy) = id->dst_fn;
2610
2611   return copy;
2612 }
2613
2614 static tree
2615 copy_decl_to_var (tree decl, copy_body_data *id)
2616 {
2617   tree copy, type;
2618
2619   gcc_assert (TREE_CODE (decl) == PARM_DECL
2620               || TREE_CODE (decl) == RESULT_DECL);
2621
2622   type = TREE_TYPE (decl);
2623
2624   copy = build_decl (VAR_DECL, DECL_NAME (decl), type);
2625   TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (decl);
2626   TREE_READONLY (copy) = TREE_READONLY (decl);
2627   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (decl);
2628   DECL_COMPLEX_GIMPLE_REG_P (copy) = DECL_COMPLEX_GIMPLE_REG_P (decl);
2629
2630   return copy_decl_for_dup_finish (id, decl, copy);
2631 }
2632
2633 static tree
2634 copy_decl_no_change (tree decl, copy_body_data *id)
2635 {
2636   tree copy;
2637
2638   copy = copy_node (decl);
2639
2640   /* The COPY is not abstract; it will be generated in DST_FN.  */
2641   DECL_ABSTRACT (copy) = 0;
2642   lang_hooks.dup_lang_specific_decl (copy);
2643
2644   /* TREE_ADDRESSABLE isn't used to indicate that a label's address has
2645      been taken; it's for internal bookkeeping in expand_goto_internal.  */
2646   if (TREE_CODE (copy) == LABEL_DECL)
2647     {
2648       TREE_ADDRESSABLE (copy) = 0;
2649       LABEL_DECL_UID (copy) = -1;
2650     }
2651
2652   return copy_decl_for_dup_finish (id, decl, copy);
2653 }
2654
2655 static tree
2656 copy_decl_maybe_to_var (tree decl, copy_body_data *id)
2657 {
2658   if (TREE_CODE (decl) == PARM_DECL || TREE_CODE (decl) == RESULT_DECL)
2659     return copy_decl_to_var (decl, id);
2660   else
2661     return copy_decl_no_change (decl, id);
2662 }
2663
2664 /* Return a copy of the function's argument tree.  */
2665 static tree
2666 copy_arguments_for_versioning (tree orig_parm, copy_body_data * id)
2667 {
2668   tree *arg_copy, *parg;
2669
2670   arg_copy = &orig_parm;
2671   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
2672     {
2673       tree new = remap_decl (*parg, id);
2674       lang_hooks.dup_lang_specific_decl (new);
2675       TREE_CHAIN (new) = TREE_CHAIN (*parg);
2676       *parg = new;
2677     }
2678   return orig_parm;
2679 }
2680
2681 /* Return a copy of the function's static chain.  */
2682 static tree
2683 copy_static_chain (tree static_chain, copy_body_data * id)
2684 {
2685   tree *chain_copy, *pvar;
2686
2687   chain_copy = &static_chain;
2688   for (pvar = chain_copy; *pvar; pvar = &TREE_CHAIN (*pvar))
2689     {
2690       tree new = remap_decl (*pvar, id);
2691       lang_hooks.dup_lang_specific_decl (new);
2692       TREE_CHAIN (new) = TREE_CHAIN (*pvar);
2693       *pvar = new;
2694     }
2695   return static_chain;
2696 }
2697
2698 /* Return true if the function is allowed to be versioned.
2699    This is a guard for the versioning functionality.  */
2700 bool
2701 tree_versionable_function_p (tree fndecl)
2702 {
2703   if (fndecl == NULL_TREE)
2704     return false;
2705   /* ??? There are cases where a function is
2706      uninlinable but can be versioned.  */
2707   if (!tree_inlinable_function_p (fndecl))
2708     return false;
2709
2710   return true;
2711 }
2712
2713 /* Create a copy of a function's tree.
2714    OLD_DECL and NEW_DECL are FUNCTION_DECL tree nodes
2715    of the original function and the new copied function
2716    respectively.  In case we want to replace a DECL
2717    tree with another tree while duplicating the function's
2718    body, TREE_MAP represents the mapping between these
2719    trees. If UPDATE_CLONES is set, the call_stmt fields
2720    of edges of clones of the function will be updated.  */
2721 void
2722 tree_function_versioning (tree old_decl, tree new_decl, varray_type tree_map,
2723                           bool update_clones)
2724 {
2725   struct cgraph_node *old_version_node;
2726   struct cgraph_node *new_version_node;
2727   copy_body_data id;
2728   tree p, new_fndecl;
2729   unsigned i;
2730   struct ipa_replace_map *replace_info;
2731   basic_block old_entry_block;
2732   tree t_step;
2733
2734   gcc_assert (TREE_CODE (old_decl) == FUNCTION_DECL
2735               && TREE_CODE (new_decl) == FUNCTION_DECL);
2736   DECL_POSSIBLY_INLINED (old_decl) = 1;
2737
2738   old_version_node = cgraph_node (old_decl);
2739   new_version_node = cgraph_node (new_decl);
2740
2741   allocate_struct_function (new_decl);
2742   /* Cfun points to the new allocated function struct at this point.  */
2743   cfun->function_end_locus = DECL_SOURCE_LOCATION (new_decl);
2744
2745   DECL_ARTIFICIAL (new_decl) = 1;
2746   DECL_ABSTRACT_ORIGIN (new_decl) = DECL_ORIGIN (old_decl);
2747
2748   /* Generate a new name for the new version. */
2749   if (!update_clones)
2750     DECL_NAME (new_decl) = create_tmp_var_name (NULL);
2751   /* Create a new SYMBOL_REF rtx for the new name. */
2752   if (DECL_RTL (old_decl) != NULL)
2753     {
2754       SET_DECL_RTL (new_decl, copy_rtx (DECL_RTL (old_decl)));
2755       XEXP (DECL_RTL (new_decl), 0) =
2756         gen_rtx_SYMBOL_REF (GET_MODE (XEXP (DECL_RTL (old_decl), 0)),
2757                             IDENTIFIER_POINTER (DECL_NAME (new_decl)));
2758     }
2759
2760   /* Prepare the data structures for the tree copy.  */
2761   memset (&id, 0, sizeof (id));
2762
2763   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2764   id.src_fn = old_decl;
2765   id.dst_fn = new_decl;
2766   id.src_node = old_version_node;
2767   id.dst_node = new_version_node;
2768   id.src_cfun = DECL_STRUCT_FUNCTION (old_decl);
2769
2770   id.copy_decl = copy_decl_no_change;
2771   id.transform_call_graph_edges
2772     = update_clones ? CB_CGE_MOVE_CLONES : CB_CGE_MOVE;
2773   id.transform_new_cfg = true;
2774   id.transform_return_to_modify = false;
2775   id.transform_lang_insert_block = false;
2776
2777   current_function_decl = new_decl;
2778
2779   /* Copy the function's static chain.  */
2780   p = DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl;
2781   if (p)
2782     DECL_STRUCT_FUNCTION (new_decl)->static_chain_decl =
2783       copy_static_chain (DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl,
2784                          &id);
2785   /* Copy the function's arguments.  */
2786   if (DECL_ARGUMENTS (old_decl) != NULL_TREE)
2787     DECL_ARGUMENTS (new_decl) =
2788       copy_arguments_for_versioning (DECL_ARGUMENTS (old_decl), &id);
2789
2790   /* If there's a tree_map, prepare for substitution.  */
2791   if (tree_map)
2792     for (i = 0; i < VARRAY_ACTIVE_SIZE (tree_map); i++)
2793       {
2794         replace_info = VARRAY_GENERIC_PTR (tree_map, i);
2795         if (replace_info->replace_p)
2796           insert_decl_map (&id, replace_info->old_tree,
2797                            replace_info->new_tree);
2798       }
2799
2800   DECL_INITIAL (new_decl) = remap_blocks (DECL_INITIAL (id.src_fn), &id);
2801
2802   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2803   number_blocks (id.dst_fn);
2804
2805   if (DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list != NULL_TREE)
2806     /* Add local vars.  */
2807     for (t_step = DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list;
2808          t_step; t_step = TREE_CHAIN (t_step))
2809       {
2810         tree var = TREE_VALUE (t_step);
2811         if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
2812           cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
2813                                                  cfun->unexpanded_var_list);
2814         else
2815           cfun->unexpanded_var_list =
2816             tree_cons (NULL_TREE, remap_decl (var, &id),
2817                        cfun->unexpanded_var_list);
2818       }
2819
2820   /* Copy the Function's body.  */
2821   old_entry_block = ENTRY_BLOCK_PTR_FOR_FUNCTION
2822     (DECL_STRUCT_FUNCTION (old_decl));
2823   new_fndecl = copy_body (&id,
2824                           old_entry_block->count,
2825                           old_entry_block->frequency, NULL, NULL);
2826
2827   DECL_SAVED_TREE (new_decl) = DECL_SAVED_TREE (new_fndecl);
2828
2829   DECL_STRUCT_FUNCTION (new_decl)->cfg =
2830     DECL_STRUCT_FUNCTION (new_fndecl)->cfg;
2831   DECL_STRUCT_FUNCTION (new_decl)->eh = DECL_STRUCT_FUNCTION (new_fndecl)->eh;
2832   DECL_STRUCT_FUNCTION (new_decl)->ib_boundaries_block =
2833     DECL_STRUCT_FUNCTION (new_fndecl)->ib_boundaries_block;
2834   DECL_STRUCT_FUNCTION (new_decl)->last_label_uid =
2835     DECL_STRUCT_FUNCTION (new_fndecl)->last_label_uid;
2836
2837   if (DECL_RESULT (old_decl) != NULL_TREE)
2838     {
2839       tree *res_decl = &DECL_RESULT (old_decl);
2840       DECL_RESULT (new_decl) = remap_decl (*res_decl, &id);
2841       lang_hooks.dup_lang_specific_decl (DECL_RESULT (new_decl));
2842     }
2843
2844   current_function_decl = NULL;
2845   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2846   number_blocks (new_decl);
2847
2848   /* Clean up.  */
2849   splay_tree_delete (id.decl_map);
2850   fold_cond_expr_cond ();
2851   return;
2852 }
2853
2854 /* Duplicate a type, fields and all.  */
2855
2856 tree
2857 build_duplicate_type (tree type)
2858 {
2859   struct copy_body_data id;
2860
2861   memset (&id, 0, sizeof (id));
2862   id.src_fn = current_function_decl;
2863   id.dst_fn = current_function_decl;
2864   id.src_cfun = cfun;
2865   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2866
2867   type = remap_type_1 (type, &id);
2868
2869   splay_tree_delete (id.decl_map);
2870
2871   return type;
2872 }