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           bsi_insert_after (&copy_bsi, stmt, BSI_NEW_STMT);
 708           call = get_call_expr_in (stmt);
 709           /* We're duplicating a CALL_EXPR.  Find any corresponding
 710              callgraph edges and update or duplicate them.  */
 711           if (call && (decl = get_callee_fndecl (call)))
 712             {
 713               struct cgraph_node *node;
 714               struct cgraph_edge *edge;
 715
 716               switch (id->transform_call_graph_edges)
 717                 {
 718                 case CB_CGE_DUPLICATE:
 719                   edge = cgraph_edge (id->src_node, orig_stmt);
 720                   if (edge)
 721                     cgraph_clone_edge (edge, id->dst_node, stmt,
 722                                        REG_BR_PROB_BASE, 1, true);
 723                   break;
 724
 725                 case CB_CGE_MOVE_CLONES:
 726                   for (node = id->dst_node->next_clone;
 727                        node;
 728                        node = node->next_clone)
 729                     {
 730                       edge = cgraph_edge (node, orig_stmt);
 731                       gcc_assert (edge);
 732                       edge->call_stmt = stmt;
 733                     }
 734                   /* FALLTHRU */
 735
 736                 case CB_CGE_MOVE:
 737                   edge = cgraph_edge (id->dst_node, orig_stmt);
 738                   if (edge)
 739                     edge->call_stmt = stmt;
 740                   break;
 741
 742                 default:
 743                   gcc_unreachable ();
 744                 }
 745             }
 746           /* If you think we can abort here, you are wrong.
 747              There is no region 0 in tree land.  */
 748           gcc_assert (lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt)
 749                       != 0);
 750
 751           if (tree_could_throw_p (stmt))
 752             {
 753               int region = lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt);
 754               /* Add an entry for the copied tree in the EH hashtable.
 755                  When cloning or versioning, use the hashtable in
 756                  cfun, and just copy the EH number.  When inlining, use the
 757                  hashtable in the caller, and adjust the region number.  */
 758               if (region > 0)
 759                 add_stmt_to_eh_region (stmt, region + id->eh_region_offset);
 760
 761               /* If this tree doesn't have a region associated with it,
 762                  and there is a "current region,"
 763                  then associate this tree with the current region
 764                  and add edges associated with this region.  */
 765               if ((lookup_stmt_eh_region_fn (id->src_cfun,
 766                                              orig_stmt) <= 0
 767                    && id->eh_region > 0)
 768                   && tree_could_throw_p (stmt))
 769                 add_stmt_to_eh_region (stmt, id->eh_region);
 770             }
 771         }
 772     }
 773   return copy_basic_block;
 774 }
 775
 776 /* Copy edges from BB into its copy constructed earlier, scale profile
 777    accordingly.  Edges will be taken care of later.  Assume aux
 778    pointers to point to the copies of each BB.  */
 779 static void
 780 copy_edges_for_bb (basic_block bb, int count_scale)
 781 {
 782   basic_block new_bb = (basic_block) bb->aux;
 783   edge_iterator ei;
 784   edge old_edge;
 785   block_stmt_iterator bsi;
 786   int flags;
 787
 788   /* Use the indices from the original blocks to create edges for the
 789      new ones.  */
 790   FOR_EACH_EDGE (old_edge, ei, bb->succs)
 791     if (!(old_edge->flags & EDGE_EH))
 792       {
 793         edge new;
 794
 795         flags = old_edge->flags;
 796
 797         /* Return edges do get a FALLTHRU flag when the get inlined.  */
 798         if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags
 799             && old_edge->dest->aux != EXIT_BLOCK_PTR)
 800           flags |= EDGE_FALLTHRU;
 801         new = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
 802         new->count = old_edge->count * count_scale / REG_BR_PROB_BASE;
 803         new->probability = old_edge->probability;
 804       }
 805
 806   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
 807     return;
 808
 809   for (bsi = bsi_start (new_bb); !bsi_end_p (bsi);)
 810     {
 811       tree copy_stmt;
 812
 813       copy_stmt = bsi_stmt (bsi);
 814       update_stmt (copy_stmt);
 815       /* Do this before the possible split_block.  */
 816       bsi_next (&bsi);
 817
 818       /* If this tree could throw an exception, there are two
 819          cases where we need to add abnormal edge(s): the
 820          tree wasn't in a region and there is a "current
 821          region" in the caller; or the original tree had
 822          EH edges.  In both cases split the block after the tree,
 823          and add abnormal edge(s) as needed; we need both
 824          those from the callee and the caller.
 825          We check whether the copy can throw, because the const
 826          propagation can change an INDIRECT_REF which throws
 827          into a COMPONENT_REF which doesn't.  If the copy
 828          can throw, the original could also throw.  */
 829
 830       if (tree_can_throw_internal (copy_stmt))
 831         {
 832           if (!bsi_end_p (bsi))
 833             /* Note that bb's predecessor edges aren't necessarily
 834                right at this point; split_block doesn't care.  */
 835             {
 836               edge e = split_block (new_bb, copy_stmt);
 837               new_bb = e->dest;
 838               bsi = bsi_start (new_bb);
 839             }
 840
 841            make_eh_edges (copy_stmt);
 842         }
 843     }
 844 }
 845
 846 /* Wrapper for remap_decl so it can be used as a callback.  */
 847 static tree
 848 remap_decl_1 (tree decl, void *data)
 849 {
 850   return remap_decl (decl, (copy_body_data *) data);
 851 }
 852
 853 /* Make a copy of the body of FN so that it can be inserted inline in
 854    another function.  Walks FN via CFG, returns new fndecl.  */
 855
 856 static tree
 857 copy_cfg_body (copy_body_data * id, gcov_type count, int frequency,
 858                basic_block entry_block_map, basic_block exit_block_map)
 859 {
 860   tree callee_fndecl = id->src_fn;
 861   /* Original cfun for the callee, doesn't change.  */
 862   struct function *src_cfun = DECL_STRUCT_FUNCTION (callee_fndecl);
 863   /* Copy, built by this function.  */
 864   struct function *new_cfun;
 865   /* Place to copy from; when a copy of the function was saved off earlier,
 866      use that instead of the main copy.  */
 867   struct function *cfun_to_copy =
 868     (struct function *) ggc_alloc_cleared (sizeof (struct function));
 869   basic_block bb;
 870   tree new_fndecl = NULL;
 871   int count_scale, frequency_scale;
 872
 873   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count)
 874     count_scale = (REG_BR_PROB_BASE * count
 875                    / ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count);
 876   else
 877     count_scale = 1;
 878
 879   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency)
 880     frequency_scale = (REG_BR_PROB_BASE * frequency
 881                        /
 882                        ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency);
 883   else
 884     frequency_scale = count_scale;
 885
 886   /* Register specific tree functions.  */
 887   tree_register_cfg_hooks ();
 888
 889   /* Must have a CFG here at this point.  */
 890   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION
 891               (DECL_STRUCT_FUNCTION (callee_fndecl)));
 892
 893   *cfun_to_copy = *DECL_STRUCT_FUNCTION (callee_fndecl);
 894
 895   id->src_cfun = cfun_to_copy;
 896
 897   /* If requested, create new basic_block_info and label_to_block_maps.
 898      Otherwise, insert our new blocks and labels into the existing cfg.  */
 899   if (id->transform_new_cfg)
 900     {
 901       new_cfun =
 902         (struct function *) ggc_alloc_cleared (sizeof (struct function));
 903       *new_cfun = *DECL_STRUCT_FUNCTION (callee_fndecl);
 904       new_cfun->cfg = NULL;
 905       new_cfun->decl = new_fndecl = copy_node (callee_fndecl);
 906       new_cfun->ib_boundaries_block = NULL;
 907       DECL_STRUCT_FUNCTION (new_fndecl) = new_cfun;
 908       push_cfun (new_cfun);
 909       init_empty_tree_cfg ();
 910
 911       ENTRY_BLOCK_PTR->count =
 912         (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
 913          REG_BR_PROB_BASE);
 914       ENTRY_BLOCK_PTR->frequency =
 915         (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
 916          frequency_scale / REG_BR_PROB_BASE);
 917       EXIT_BLOCK_PTR->count =
 918         (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
 919          REG_BR_PROB_BASE);
 920       EXIT_BLOCK_PTR->frequency =
 921         (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
 922          frequency_scale / REG_BR_PROB_BASE);
 923
 924       entry_block_map = ENTRY_BLOCK_PTR;
 925       exit_block_map = EXIT_BLOCK_PTR;
 926     }
 927
 928   ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = entry_block_map;
 929   EXIT_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = exit_block_map;
 930
 931   /* Duplicate any exception-handling regions.  */
 932   if (cfun->eh)
 933     {
 934       if (id->transform_new_cfg)
 935         init_eh_for_function ();
 936       id->eh_region_offset
 937         = duplicate_eh_regions (cfun_to_copy, remap_decl_1, id,
 938                                 0, id->eh_region);
 939     }
 940   /* Use aux pointers to map the original blocks to copy.  */
 941   FOR_EACH_BB_FN (bb, cfun_to_copy)
 942     bb->aux = copy_bb (id, bb, frequency_scale, count_scale);
 943   /* Now that we've duplicated the blocks, duplicate their edges.  */
 944   FOR_ALL_BB_FN (bb, cfun_to_copy)
 945     copy_edges_for_bb (bb, count_scale);
 946   FOR_ALL_BB_FN (bb, cfun_to_copy)
 947     bb->aux = NULL;
 948
 949   if (id->transform_new_cfg)
 950     pop_cfun ();
 951
 952   return new_fndecl;
 953 }
 954
 955 /* Make a copy of the body of FN so that it can be inserted inline in
 956    another function.  */
 957
 958 static tree
 959 copy_generic_body (copy_body_data *id)
 960 {
 961   tree body;
 962   tree fndecl = id->src_fn;
 963
 964   body = DECL_SAVED_TREE (fndecl);
 965   walk_tree (&body, copy_body_r, id, NULL);
 966
 967   return body;
 968 }
 969
 970 static tree
 971 copy_body (copy_body_data *id, gcov_type count, int frequency,
 972            basic_block entry_block_map, basic_block exit_block_map)
 973 {
 974   tree fndecl = id->src_fn;
 975   tree body;
 976
 977   /* If this body has a CFG, walk CFG and copy.  */
 978   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (fndecl)));
 979   body = copy_cfg_body (id, count, frequency, entry_block_map, exit_block_map);
 980
 981   return body;
 982 }
 983
 984 /* Return true if VALUE is an ADDR_EXPR of an automatic variable
 985    defined in function FN, or of a data member thereof.  */
 986
 987 static bool
 988 self_inlining_addr_expr (tree value, tree fn)
 989 {
 990   tree var;
 991
 992   if (TREE_CODE (value) != ADDR_EXPR)
 993     return false;
 994
 995   var = get_base_address (TREE_OPERAND (value, 0));
 996
 997   return var && lang_hooks.tree_inlining.auto_var_in_fn_p (var, fn);
 998 }
 999
1000 static void
1001 setup_one_parameter (copy_body_data *id, tree p, tree value, tree fn,
1002                      basic_block bb, tree *vars)
1003 {
1004   tree init_stmt;
1005   tree var;
1006   tree var_sub;
1007
1008   /* If the parameter is never assigned to, we may not need to
1009      create a new variable here at all.  Instead, we may be able
1010      to just use the argument value.  */
1011   if (TREE_READONLY (p)
1012       && !TREE_ADDRESSABLE (p)
1013       && value && !TREE_SIDE_EFFECTS (value))
1014     {
1015       /* We may produce non-gimple trees by adding NOPs or introduce
1016          invalid sharing when operand is not really constant.
1017          It is not big deal to prohibit constant propagation here as
1018          we will constant propagate in DOM1 pass anyway.  */
1019       if (is_gimple_min_invariant (value)
1020           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p))
1021           /* We have to be very careful about ADDR_EXPR.  Make sure
1022              the base variable isn't a local variable of the inlined
1023              function, e.g., when doing recursive inlining, direct or
1024              mutually-recursive or whatever, which is why we don't
1025              just test whether fn == current_function_decl.  */
1026           && ! self_inlining_addr_expr (value, fn))
1027         {
1028           insert_decl_map (id, p, value);
1029           return;
1030         }
1031     }
1032
1033   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
1034      here since the type of this decl must be visible to the calling
1035      function.  */
1036   var = copy_decl_to_var (p, id);
1037
1038   /* See if the frontend wants to pass this by invisible reference.  If
1039      so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
1040      replace uses of the PARM_DECL with dereferences.  */
1041   if (TREE_TYPE (var) != TREE_TYPE (p)
1042       && POINTER_TYPE_P (TREE_TYPE (var))
1043       && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
1044     {
1045       insert_decl_map (id, var, var);
1046       var_sub = build_fold_indirect_ref (var);
1047     }
1048   else
1049     var_sub = var;
1050
1051   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
1052      that way, when the PARM_DECL is encountered, it will be
1053      automatically replaced by the VAR_DECL.  */
1054   insert_decl_map (id, p, var_sub);
1055
1056   /* Declare this new variable.  */
1057   TREE_CHAIN (var) = *vars;
1058   *vars = var;
1059
1060   /* Make gimplifier happy about this variable.  */
1061   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1062
1063   /* Even if P was TREE_READONLY, the new VAR should not be.
1064      In the original code, we would have constructed a
1065      temporary, and then the function body would have never
1066      changed the value of P.  However, now, we will be
1067      constructing VAR directly.  The constructor body may
1068      change its value multiple times as it is being
1069      constructed.  Therefore, it must not be TREE_READONLY;
1070      the back-end assumes that TREE_READONLY variable is
1071      assigned to only once.  */
1072   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
1073     TREE_READONLY (var) = 0;
1074
1075   /* Initialize this VAR_DECL from the equivalent argument.  Convert
1076      the argument to the proper type in case it was promoted.  */
1077   if (value)
1078     {
1079       tree rhs = fold_convert (TREE_TYPE (var), value);
1080       block_stmt_iterator bsi = bsi_last (bb);
1081
1082       if (rhs == error_mark_node)
1083         return;
1084
1085       STRIP_USELESS_TYPE_CONVERSION (rhs);
1086
1087       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
1088          keep our trees in gimple form.  */
1089       init_stmt = build2 (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
1090
1091       /* If we did not create a gimple value and we did not create a gimple
1092          cast of a gimple value, then we will need to gimplify INIT_STMTS
1093          at the end.  Note that is_gimple_cast only checks the outer
1094          tree code, not its operand.  Thus the explicit check that its
1095          operand is a gimple value.  */
1096       if (!is_gimple_val (rhs)
1097           && (!is_gimple_cast (rhs)
1098               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
1099         gimplify_stmt (&init_stmt);
1100
1101       /* If VAR represents a zero-sized variable, it's possible that the
1102          assignment statment may result in no gimple statements.  */
1103       if (init_stmt)
1104         bsi_insert_after (&bsi, init_stmt, BSI_NEW_STMT);
1105     }
1106 }
1107
1108 /* Generate code to initialize the parameters of the function at the
1109    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
1110
1111 static void
1112 initialize_inlined_parameters (copy_body_data *id, tree args, tree static_chain,
1113                                tree fn, basic_block bb)
1114 {
1115   tree parms;
1116   tree a;
1117   tree p;
1118   tree vars = NULL_TREE;
1119   int argnum = 0;
1120
1121   /* Figure out what the parameters are.  */
1122   parms = DECL_ARGUMENTS (fn);
1123
1124   /* Loop through the parameter declarations, replacing each with an
1125      equivalent VAR_DECL, appropriately initialized.  */
1126   for (p = parms, a = args; p;
1127        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
1128     {
1129       tree value;
1130
1131       ++argnum;
1132
1133       /* Find the initializer.  */
1134       value = lang_hooks.tree_inlining.convert_parm_for_inlining
1135               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
1136
1137       setup_one_parameter (id, p, value, fn, bb, &vars);
1138     }
1139
1140   /* Initialize the static chain.  */
1141   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1142   gcc_assert (fn != current_function_decl);
1143   if (p)
1144     {
1145       /* No static chain?  Seems like a bug in tree-nested.c.  */
1146       gcc_assert (static_chain);
1147
1148       setup_one_parameter (id, p, static_chain, fn, bb, &vars);
1149     }
1150
1151   declare_inline_vars (id->block, vars);
1152 }
1153
1154 /* Declare a return variable to replace the RESULT_DECL for the
1155    function we are calling.  An appropriate DECL_STMT is returned.
1156    The USE_STMT is filled to contain a use of the declaration to
1157    indicate the return value of the function.
1158
1159    RETURN_SLOT_ADDR, if non-null, was a fake parameter that
1160    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
1161    the MODIFY_EXPR to which this call is the RHS.
1162
1163    The return value is a (possibly null) value that is the result of the
1164    function as seen by the callee.  *USE_P is a (possibly null) value that
1165    holds the result as seen by the caller.  */
1166
1167 static tree
1168 declare_return_variable (copy_body_data *id, tree return_slot_addr,
1169                          tree modify_dest, tree *use_p)
1170 {
1171   tree callee = id->src_fn;
1172   tree caller = id->dst_fn;
1173   tree result = DECL_RESULT (callee);
1174   tree callee_type = TREE_TYPE (result);
1175   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
1176   tree var, use;
1177
1178   /* We don't need to do anything for functions that don't return
1179      anything.  */
1180   if (!result || VOID_TYPE_P (callee_type))
1181     {
1182       *use_p = NULL_TREE;
1183       return NULL_TREE;
1184     }
1185
1186   /* If there was a return slot, then the return value is the
1187      dereferenced address of that object.  */
1188   if (return_slot_addr)
1189     {
1190       /* The front end shouldn't have used both return_slot_addr and
1191          a modify expression.  */
1192       gcc_assert (!modify_dest);
1193       if (DECL_BY_REFERENCE (result))
1194         var = return_slot_addr;
1195       else
1196         var = build_fold_indirect_ref (return_slot_addr);
1197       if (TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1198           && !DECL_COMPLEX_GIMPLE_REG_P (result)
1199           && DECL_P (var))
1200         DECL_COMPLEX_GIMPLE_REG_P (var) = 0;
1201       use = NULL;
1202       goto done;
1203     }
1204
1205   /* All types requiring non-trivial constructors should have been handled.  */
1206   gcc_assert (!TREE_ADDRESSABLE (callee_type));
1207
1208   /* Attempt to avoid creating a new temporary variable.  */
1209   if (modify_dest)
1210     {
1211       bool use_it = false;
1212
1213       /* We can't use MODIFY_DEST if there's type promotion involved.  */
1214       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
1215         use_it = false;
1216
1217       /* ??? If we're assigning to a variable sized type, then we must
1218          reuse the destination variable, because we've no good way to
1219          create variable sized temporaries at this point.  */
1220       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
1221         use_it = true;
1222
1223       /* If the callee cannot possibly modify MODIFY_DEST, then we can
1224          reuse it as the result of the call directly.  Don't do this if
1225          it would promote MODIFY_DEST to addressable.  */
1226       else if (TREE_ADDRESSABLE (result))
1227         use_it = false;
1228       else
1229         {
1230           tree base_m = get_base_address (modify_dest);
1231
1232           /* If the base isn't a decl, then it's a pointer, and we don't
1233              know where that's going to go.  */
1234           if (!DECL_P (base_m))
1235             use_it = false;
1236           else if (is_global_var (base_m))
1237             use_it = false;
1238           else if (TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1239                    && !DECL_COMPLEX_GIMPLE_REG_P (result)
1240                    && DECL_COMPLEX_GIMPLE_REG_P (base_m))
1241             use_it = false;
1242           else if (!TREE_ADDRESSABLE (base_m))
1243             use_it = true;
1244         }
1245
1246       if (use_it)
1247         {
1248           var = modify_dest;
1249           use = NULL;
1250           goto done;
1251         }
1252     }
1253
1254   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
1255
1256   var = copy_decl_to_var (result, id);
1257
1258   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1259   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
1260     = tree_cons (NULL_TREE, var,
1261                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
1262
1263   /* Do not have the rest of GCC warn about this variable as it should
1264      not be visible to the user.  */
1265   TREE_NO_WARNING (var) = 1;
1266
1267   /* Build the use expr.  If the return type of the function was
1268      promoted, convert it back to the expected type.  */
1269   use = var;
1270   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
1271     use = fold_convert (caller_type, var);
1272
1273   STRIP_USELESS_TYPE_CONVERSION (use);
1274
1275  done:
1276   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
1277      way, when the RESULT_DECL is encountered, it will be
1278      automatically replaced by the VAR_DECL.  */
1279   insert_decl_map (id, result, var);
1280
1281   /* Remember this so we can ignore it in remap_decls.  */
1282   id->retvar = var;
1283
1284   *use_p = use;
1285   return var;
1286 }
1287
1288 /* Returns nonzero if a function can be inlined as a tree.  */
1289
1290 bool
1291 tree_inlinable_function_p (tree fn)
1292 {
1293   return inlinable_function_p (fn);
1294 }
1295
1296 static const char *inline_forbidden_reason;
1297
1298 static tree
1299 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
1300                       void *fnp)
1301 {
1302   tree node = *nodep;
1303   tree fn = (tree) fnp;
1304   tree t;
1305
1306   switch (TREE_CODE (node))
1307     {
1308     case CALL_EXPR:
1309       /* Refuse to inline alloca call unless user explicitly forced so as
1310          this may change program's memory overhead drastically when the
1311          function using alloca is called in loop.  In GCC present in
1312          SPEC2000 inlining into schedule_block cause it to require 2GB of
1313          RAM instead of 256MB.  */
1314       if (alloca_call_p (node)
1315           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1316         {
1317           inline_forbidden_reason
1318             = G_("function %q+F can never be inlined because it uses "
1319                  "alloca (override using the always_inline attribute)");
1320           return node;
1321         }
1322       t = get_callee_fndecl (node);
1323       if (! t)
1324         break;
1325
1326       /* We cannot inline functions that call setjmp.  */
1327       if (setjmp_call_p (t))
1328         {
1329           inline_forbidden_reason
1330             = G_("function %q+F can never be inlined because it uses setjmp");
1331           return node;
1332         }
1333
1334       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
1335         switch (DECL_FUNCTION_CODE (t))
1336           {
1337             /* We cannot inline functions that take a variable number of
1338                arguments.  */
1339           case BUILT_IN_VA_START:
1340           case BUILT_IN_STDARG_START:
1341           case BUILT_IN_NEXT_ARG:
1342           case BUILT_IN_VA_END:
1343             inline_forbidden_reason
1344               = G_("function %q+F can never be inlined because it "
1345                    "uses variable argument lists");
1346             return node;
1347
1348           case BUILT_IN_LONGJMP:
1349             /* We can't inline functions that call __builtin_longjmp at
1350                all.  The non-local goto machinery really requires the
1351                destination be in a different function.  If we allow the
1352                function calling __builtin_longjmp to be inlined into the
1353                function calling __builtin_setjmp, Things will Go Awry.  */
1354             inline_forbidden_reason
1355               = G_("function %q+F can never be inlined because "
1356                    "it uses setjmp-longjmp exception handling");
1357             return node;
1358
1359           case BUILT_IN_NONLOCAL_GOTO:
1360             /* Similarly.  */
1361             inline_forbidden_reason
1362               = G_("function %q+F can never be inlined because "
1363                    "it uses non-local goto");
1364             return node;
1365
1366           case BUILT_IN_RETURN:
1367           case BUILT_IN_APPLY_ARGS:
1368             /* If a __builtin_apply_args caller would be inlined,
1369                it would be saving arguments of the function it has
1370                been inlined into.  Similarly __builtin_return would
1371                return from the function the inline has been inlined into.  */
1372             inline_forbidden_reason
1373               = G_("function %q+F can never be inlined because "
1374                    "it uses __builtin_return or __builtin_apply_args");
1375             return node;
1376
1377           default:
1378             break;
1379           }
1380       break;
1381
1382     case GOTO_EXPR:
1383       t = TREE_OPERAND (node, 0);
1384
1385       /* We will not inline a function which uses computed goto.  The
1386          addresses of its local labels, which may be tucked into
1387          global storage, are of course not constant across
1388          instantiations, which causes unexpected behavior.  */
1389       if (TREE_CODE (t) != LABEL_DECL)
1390         {
1391           inline_forbidden_reason
1392             = G_("function %q+F can never be inlined "
1393                  "because it contains a computed goto");
1394           return node;
1395         }
1396       break;
1397
1398     case LABEL_EXPR:
1399       t = TREE_OPERAND (node, 0);
1400       if (DECL_NONLOCAL (t))
1401         {
1402           /* We cannot inline a function that receives a non-local goto
1403              because we cannot remap the destination label used in the
1404              function that is performing the non-local goto.  */
1405           inline_forbidden_reason
1406             = G_("function %q+F can never be inlined "
1407                  "because it receives a non-local goto");
1408           return node;
1409         }
1410       break;
1411
1412     case RECORD_TYPE:
1413     case UNION_TYPE:
1414       /* We cannot inline a function of the form
1415
1416            void F (int i) { struct S { int ar[i]; } s; }
1417
1418          Attempting to do so produces a catch-22.
1419          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1420          UNION_TYPE nodes, then it goes into infinite recursion on a
1421          structure containing a pointer to its own type.  If it doesn't,
1422          then the type node for S doesn't get adjusted properly when
1423          F is inlined.
1424
1425          ??? This is likely no longer true, but it's too late in the 4.0
1426          cycle to try to find out.  This should be checked for 4.1.  */
1427       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1428         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1429           {
1430             inline_forbidden_reason
1431               = G_("function %q+F can never be inlined "
1432                    "because it uses variable sized variables");
1433             return node;
1434           }
1435
1436     default:
1437       break;
1438     }
1439
1440   return NULL_TREE;
1441 }
1442
1443 /* Return subexpression representing possible alloca call, if any.  */
1444 static tree
1445 inline_forbidden_p (tree fndecl)
1446 {
1447   location_t saved_loc = input_location;
1448   block_stmt_iterator bsi;
1449   basic_block bb;
1450   tree ret = NULL_TREE;
1451
1452   FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fndecl))
1453     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1454       {
1455         ret = walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
1456                                     inline_forbidden_p_1, fndecl);
1457         if (ret)
1458           goto egress;
1459       }
1460
1461 egress:
1462   input_location = saved_loc;
1463   return ret;
1464 }
1465
1466 /* Returns nonzero if FN is a function that does not have any
1467    fundamental inline blocking properties.  */
1468
1469 static bool
1470 inlinable_function_p (tree fn)
1471 {
1472   bool inlinable = true;
1473
1474   /* If we've already decided this function shouldn't be inlined,
1475      there's no need to check again.  */
1476   if (DECL_UNINLINABLE (fn))
1477     return false;
1478
1479   /* See if there is any language-specific reason it cannot be
1480      inlined.  (It is important that this hook be called early because
1481      in C++ it may result in template instantiation.)
1482      If the function is not inlinable for language-specific reasons,
1483      it is left up to the langhook to explain why.  */
1484   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1485
1486   /* If we don't have the function body available, we can't inline it.
1487      However, this should not be recorded since we also get here for
1488      forward declared inline functions.  Therefore, return at once.  */
1489   if (!DECL_SAVED_TREE (fn))
1490     return false;
1491
1492   /* If we're not inlining at all, then we cannot inline this function.  */
1493   else if (!flag_inline_trees)
1494     inlinable = false;
1495
1496   /* Only try to inline functions if DECL_INLINE is set.  This should be
1497      true for all functions declared `inline', and for all other functions
1498      as well with -finline-functions.
1499
1500      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1501      it's the front-end that must set DECL_INLINE in this case, because
1502      dwarf2out loses if a function that does not have DECL_INLINE set is
1503      inlined anyway.  That is why we have both DECL_INLINE and
1504      DECL_DECLARED_INLINE_P.  */
1505   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1506             here should be redundant.  */
1507   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1508     inlinable = false;
1509
1510   else if (inline_forbidden_p (fn))
1511     {
1512       /* See if we should warn about uninlinable functions.  Previously,
1513          some of these warnings would be issued while trying to expand
1514          the function inline, but that would cause multiple warnings
1515          about functions that would for example call alloca.  But since
1516          this a property of the function, just one warning is enough.
1517          As a bonus we can now give more details about the reason why a
1518          function is not inlinable.
1519          We only warn for functions declared `inline' by the user.  */
1520       bool do_warning = (warn_inline
1521                          && DECL_INLINE (fn)
1522                          && DECL_DECLARED_INLINE_P (fn)
1523                          && !DECL_IN_SYSTEM_HEADER (fn));
1524
1525       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1526         sorry (inline_forbidden_reason, fn);
1527       else if (do_warning)
1528         warning (OPT_Winline, inline_forbidden_reason, fn);
1529
1530       inlinable = false;
1531     }
1532
1533   /* Squirrel away the result so that we don't have to check again.  */
1534   DECL_UNINLINABLE (fn) = !inlinable;
1535
1536   return inlinable;
1537 }
1538
1539 /* Estimate the cost of a memory move.  Use machine dependent
1540    word size and take possible memcpy call into account.  */
1541
1542 int
1543 estimate_move_cost (tree type)
1544 {
1545   HOST_WIDE_INT size;
1546
1547   size = int_size_in_bytes (type);
1548
1549   if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1550     /* Cost of a memcpy call, 3 arguments and the call.  */
1551     return 4;
1552   else
1553     return ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1554 }
1555
1556 /* Used by estimate_num_insns.  Estimate number of instructions seen
1557    by given statement.  */
1558
1559 static tree
1560 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1561 {
1562   int *count = (int *) data;
1563   tree x = *tp;
1564
1565   if (IS_TYPE_OR_DECL_P (x))
1566     {
1567       *walk_subtrees = 0;
1568       return NULL;
1569     }
1570   /* Assume that constants and references counts nothing.  These should
1571      be majorized by amount of operations among them we count later
1572      and are common target of CSE and similar optimizations.  */
1573   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1574     return NULL;
1575
1576   switch (TREE_CODE (x))
1577     {
1578     /* Containers have no cost.  */
1579     case TREE_LIST:
1580     case TREE_VEC:
1581     case BLOCK:
1582     case COMPONENT_REF:
1583     case BIT_FIELD_REF:
1584     case INDIRECT_REF:
1585     case ALIGN_INDIRECT_REF:
1586     case MISALIGNED_INDIRECT_REF:
1587     case ARRAY_REF:
1588     case ARRAY_RANGE_REF:
1589     case OBJ_TYPE_REF:
1590     case EXC_PTR_EXPR: /* ??? */
1591     case FILTER_EXPR: /* ??? */
1592     case COMPOUND_EXPR:
1593     case BIND_EXPR:
1594     case WITH_CLEANUP_EXPR:
1595     case NOP_EXPR:
1596     case VIEW_CONVERT_EXPR:
1597     case SAVE_EXPR:
1598     case ADDR_EXPR:
1599     case COMPLEX_EXPR:
1600     case RANGE_EXPR:
1601     case CASE_LABEL_EXPR:
1602     case SSA_NAME:
1603     case CATCH_EXPR:
1604     case EH_FILTER_EXPR:
1605     case STATEMENT_LIST:
1606     case ERROR_MARK:
1607     case NON_LVALUE_EXPR:
1608     case FDESC_EXPR:
1609     case VA_ARG_EXPR:
1610     case TRY_CATCH_EXPR:
1611     case TRY_FINALLY_EXPR:
1612     case LABEL_EXPR:
1613     case GOTO_EXPR:
1614     case RETURN_EXPR:
1615     case EXIT_EXPR:
1616     case LOOP_EXPR:
1617     case PHI_NODE:
1618     case WITH_SIZE_EXPR:
1619     case OMP_CLAUSE:
1620     case OMP_RETURN:
1621     case OMP_CONTINUE:
1622       break;
1623
1624     /* We don't account constants for now.  Assume that the cost is amortized
1625        by operations that do use them.  We may re-consider this decision once
1626        we are able to optimize the tree before estimating its size and break
1627        out static initializers.  */
1628     case IDENTIFIER_NODE:
1629     case INTEGER_CST:
1630     case REAL_CST:
1631     case COMPLEX_CST:
1632     case VECTOR_CST:
1633     case STRING_CST:
1634       *walk_subtrees = 0;
1635       return NULL;
1636
1637     /* Try to estimate the cost of assignments.  We have three cases to
1638        deal with:
1639         1) Simple assignments to registers;
1640         2) Stores to things that must live in memory.  This includes
1641            "normal" stores to scalars, but also assignments of large
1642            structures, or constructors of big arrays;
1643         3) TARGET_EXPRs.
1644
1645        Let us look at the first two cases, assuming we have "a = b + C":
1646        <modify_expr <var_decl "a"> <plus_expr <var_decl "b"> <constant C>>
1647        If "a" is a GIMPLE register, the assignment to it is free on almost
1648        any target, because "a" usually ends up in a real register.  Hence
1649        the only cost of this expression comes from the PLUS_EXPR, and we
1650        can ignore the MODIFY_EXPR.
1651        If "a" is not a GIMPLE register, the assignment to "a" will most
1652        likely be a real store, so the cost of the MODIFY_EXPR is the cost
1653        of moving something into "a", which we compute using the function
1654        estimate_move_cost.
1655
1656        The third case deals with TARGET_EXPRs, for which the semantics are
1657        that a temporary is assigned, unless the TARGET_EXPR itself is being
1658        assigned to something else.  In the latter case we do not need the
1659        temporary.  E.g. in <modify_expr <var_decl "a"> <target_expr>>, the
1660        MODIFY_EXPR is free.  */
1661     case INIT_EXPR:
1662     case MODIFY_EXPR:
1663       /* Is the right and side a TARGET_EXPR?  */
1664       if (TREE_CODE (TREE_OPERAND (x, 1)) == TARGET_EXPR)
1665         break;
1666       /* ... fall through ...  */
1667
1668     case TARGET_EXPR:
1669       x = TREE_OPERAND (x, 0);
1670       /* Is this an assignments to a register?  */
1671       if (is_gimple_reg (x))
1672         break;
1673       /* Otherwise it's a store, so fall through to compute the move cost.  */
1674
1675     case CONSTRUCTOR:
1676       *count += estimate_move_cost (TREE_TYPE (x));
1677       break;
1678
1679     /* Assign cost of 1 to usual operations.
1680        ??? We may consider mapping RTL costs to this.  */
1681     case COND_EXPR:
1682     case VEC_COND_EXPR:
1683
1684     case PLUS_EXPR:
1685     case MINUS_EXPR:
1686     case MULT_EXPR:
1687
1688     case FIX_TRUNC_EXPR:
1689     case FIX_CEIL_EXPR:
1690     case FIX_FLOOR_EXPR:
1691     case FIX_ROUND_EXPR:
1692
1693     case NEGATE_EXPR:
1694     case FLOAT_EXPR:
1695     case MIN_EXPR:
1696     case MAX_EXPR:
1697     case ABS_EXPR:
1698
1699     case LSHIFT_EXPR:
1700     case RSHIFT_EXPR:
1701     case LROTATE_EXPR:
1702     case RROTATE_EXPR:
1703     case VEC_LSHIFT_EXPR:
1704     case VEC_RSHIFT_EXPR:
1705
1706     case BIT_IOR_EXPR:
1707     case BIT_XOR_EXPR:
1708     case BIT_AND_EXPR:
1709     case BIT_NOT_EXPR:
1710
1711     case TRUTH_ANDIF_EXPR:
1712     case TRUTH_ORIF_EXPR:
1713     case TRUTH_AND_EXPR:
1714     case TRUTH_OR_EXPR:
1715     case TRUTH_XOR_EXPR:
1716     case TRUTH_NOT_EXPR:
1717
1718     case LT_EXPR:
1719     case LE_EXPR:
1720     case GT_EXPR:
1721     case GE_EXPR:
1722     case EQ_EXPR:
1723     case NE_EXPR:
1724     case ORDERED_EXPR:
1725     case UNORDERED_EXPR:
1726
1727     case UNLT_EXPR:
1728     case UNLE_EXPR:
1729     case UNGT_EXPR:
1730     case UNGE_EXPR:
1731     case UNEQ_EXPR:
1732     case LTGT_EXPR:
1733
1734     case CONVERT_EXPR:
1735
1736     case CONJ_EXPR:
1737
1738     case PREDECREMENT_EXPR:
1739     case PREINCREMENT_EXPR:
1740     case POSTDECREMENT_EXPR:
1741     case POSTINCREMENT_EXPR:
1742
1743     case SWITCH_EXPR:
1744
1745     case ASM_EXPR:
1746
1747     case REALIGN_LOAD_EXPR:
1748
1749     case REDUC_MAX_EXPR:
1750     case REDUC_MIN_EXPR:
1751     case REDUC_PLUS_EXPR:
1752     case WIDEN_SUM_EXPR:
1753     case DOT_PROD_EXPR:
1754
1755     case WIDEN_MULT_EXPR:
1756
1757     case RESX_EXPR:
1758       *count += 1;
1759       break;
1760
1761     /* Few special cases of expensive operations.  This is useful
1762        to avoid inlining on functions having too many of these.  */
1763     case TRUNC_DIV_EXPR:
1764     case CEIL_DIV_EXPR:
1765     case FLOOR_DIV_EXPR:
1766     case ROUND_DIV_EXPR:
1767     case EXACT_DIV_EXPR:
1768     case TRUNC_MOD_EXPR:
1769     case CEIL_MOD_EXPR:
1770     case FLOOR_MOD_EXPR:
1771     case ROUND_MOD_EXPR:
1772     case RDIV_EXPR:
1773       *count += 10;
1774       break;
1775     case CALL_EXPR:
1776       {
1777         tree decl = get_callee_fndecl (x);
1778         tree arg;
1779
1780         if (decl && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1781           switch (DECL_FUNCTION_CODE (decl))
1782             {
1783             case BUILT_IN_CONSTANT_P:
1784               *walk_subtrees = 0;
1785               return NULL_TREE;
1786             case BUILT_IN_EXPECT:
1787               return NULL_TREE;
1788             default:
1789               break;
1790             }
1791
1792         /* Our cost must be kept in sync with cgraph_estimate_size_after_inlining
1793            that does use function declaration to figure out the arguments.  */
1794         if (!decl)
1795           {
1796             for (arg = TREE_OPERAND (x, 1); arg; arg = TREE_CHAIN (arg))
1797               *count += estimate_move_cost (TREE_TYPE (TREE_VALUE (arg)));
1798           }
1799         else
1800           {
1801             for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
1802               *count += estimate_move_cost (TREE_TYPE (arg));
1803           }
1804
1805         *count += PARAM_VALUE (PARAM_INLINE_CALL_COST);
1806         break;
1807       }
1808
1809     case OMP_PARALLEL:
1810     case OMP_FOR:
1811     case OMP_SECTIONS:
1812     case OMP_SINGLE:
1813     case OMP_SECTION:
1814     case OMP_MASTER:
1815     case OMP_ORDERED:
1816     case OMP_CRITICAL:
1817     case OMP_ATOMIC:
1818       /* OpenMP directives are generally very expensive.  */
1819       *count += 40;
1820       break;
1821
1822     default:
1823       gcc_unreachable ();
1824     }
1825   return NULL;
1826 }
1827
1828 /* Estimate number of instructions that will be created by expanding EXPR.  */
1829
1830 int
1831 estimate_num_insns (tree expr)
1832 {
1833   int num = 0;
1834   struct pointer_set_t *visited_nodes;
1835   basic_block bb;
1836   block_stmt_iterator bsi;
1837   struct function *my_function;
1838
1839   /* If we're given an entire function, walk the CFG.  */
1840   if (TREE_CODE (expr) == FUNCTION_DECL)
1841     {
1842       my_function = DECL_STRUCT_FUNCTION (expr);
1843       gcc_assert (my_function && my_function->cfg);
1844       visited_nodes = pointer_set_create ();
1845       FOR_EACH_BB_FN (bb, my_function)
1846         {
1847           for (bsi = bsi_start (bb);
1848                !bsi_end_p (bsi);
1849                bsi_next (&bsi))
1850             {
1851               walk_tree (bsi_stmt_ptr (bsi), estimate_num_insns_1,
1852                          &num, visited_nodes);
1853             }
1854         }
1855       pointer_set_destroy (visited_nodes);
1856     }
1857   else
1858     walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1859
1860   return num;
1861 }
1862
1863 typedef struct function *function_p;
1864
1865 DEF_VEC_P(function_p);
1866 DEF_VEC_ALLOC_P(function_p,heap);
1867
1868 /* Initialized with NOGC, making this poisonous to the garbage collector.  */
1869 static VEC(function_p,heap) *cfun_stack;
1870
1871 void
1872 push_cfun (struct function *new_cfun)
1873 {
1874   VEC_safe_push (function_p, heap, cfun_stack, cfun);
1875   cfun = new_cfun;
1876 }
1877
1878 void
1879 pop_cfun (void)
1880 {
1881   cfun = VEC_pop (function_p, cfun_stack);
1882 }
1883
1884 /* Install new lexical TREE_BLOCK underneath 'current_block'.  */
1885 static void
1886 add_lexical_block (tree current_block, tree new_block)
1887 {
1888   tree *blk_p;
1889
1890   /* Walk to the last sub-block.  */
1891   for (blk_p = &BLOCK_SUBBLOCKS (current_block);
1892        *blk_p;
1893        blk_p = &TREE_CHAIN (*blk_p))
1894     ;
1895   *blk_p = new_block;
1896   BLOCK_SUPERCONTEXT (new_block) = current_block;
1897 }
1898
1899 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1900
1901 static bool
1902 expand_call_inline (basic_block bb, tree stmt, tree *tp, void *data)
1903 {
1904   copy_body_data *id;
1905   tree t;
1906   tree use_retvar;
1907   tree fn;
1908   splay_tree st;
1909   tree args;
1910   tree return_slot_addr;
1911   tree modify_dest;
1912   location_t saved_location;
1913   struct cgraph_edge *cg_edge;
1914   const char *reason;
1915   basic_block return_block;
1916   edge e;
1917   block_stmt_iterator bsi, stmt_bsi;
1918   bool successfully_inlined = FALSE;
1919   tree t_step;
1920   tree var;
1921   tree decl;
1922
1923   /* See what we've got.  */
1924   id = (copy_body_data *) data;
1925   t = *tp;
1926
1927   /* Set input_location here so we get the right instantiation context
1928      if we call instantiate_decl from inlinable_function_p.  */
1929   saved_location = input_location;
1930   if (EXPR_HAS_LOCATION (t))
1931     input_location = EXPR_LOCATION (t);
1932
1933   /* From here on, we're only interested in CALL_EXPRs.  */
1934   if (TREE_CODE (t) != CALL_EXPR)
1935     goto egress;
1936
1937   /* First, see if we can figure out what function is being called.
1938      If we cannot, then there is no hope of inlining the function.  */
1939   fn = get_callee_fndecl (t);
1940   if (!fn)
1941     goto egress;
1942
1943   /* Turn forward declarations into real ones.  */
1944   fn = cgraph_node (fn)->decl;
1945
1946   /* If fn is a declaration of a function in a nested scope that was
1947      globally declared inline, we don't set its DECL_INITIAL.
1948      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1949      C++ front-end uses it for cdtors to refer to their internal
1950      declarations, that are not real functions.  Fortunately those
1951      don't have trees to be saved, so we can tell by checking their
1952      DECL_SAVED_TREE.  */
1953   if (! DECL_INITIAL (fn)
1954       && DECL_ABSTRACT_ORIGIN (fn)
1955       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1956     fn = DECL_ABSTRACT_ORIGIN (fn);
1957
1958   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1959      Kill this check once this is fixed.  */
1960   if (!id->dst_node->analyzed)
1961     goto egress;
1962
1963   cg_edge = cgraph_edge (id->dst_node, stmt);
1964
1965   /* Constant propagation on argument done during previous inlining
1966      may create new direct call.  Produce an edge for it.  */
1967   if (!cg_edge)
1968     {
1969       struct cgraph_node *dest = cgraph_node (fn);
1970
1971       /* We have missing edge in the callgraph.  This can happen in one case
1972          where previous inlining turned indirect call into direct call by
1973          constant propagating arguments.  In all other cases we hit a bug
1974          (incorrect node sharing is most common reason for missing edges.  */
1975       gcc_assert (dest->needed || !flag_unit_at_a_time);
1976       cgraph_create_edge (id->dst_node, dest, stmt,
1977                           bb->count, bb->loop_depth)->inline_failed
1978         = N_("originally indirect function call not considered for inlining");
1979       goto egress;
1980     }
1981
1982   /* Don't try to inline functions that are not well-suited to
1983      inlining.  */
1984   if (!cgraph_inline_p (cg_edge, &reason))
1985     {
1986       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
1987           /* Avoid warnings during early inline pass. */
1988           && (!flag_unit_at_a_time || cgraph_global_info_ready))
1989         {
1990           sorry ("inlining failed in call to %q+F: %s", fn, reason);
1991           sorry ("called from here");
1992         }
1993       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1994                && !DECL_IN_SYSTEM_HEADER (fn)
1995                && strlen (reason)
1996                && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn))
1997                /* Avoid warnings during early inline pass. */
1998                && (!flag_unit_at_a_time || cgraph_global_info_ready))
1999         {
2000           warning (OPT_Winline, "inlining failed in call to %q+F: %s",
2001                    fn, reason);
2002           warning (OPT_Winline, "called from here");
2003         }
2004       goto egress;
2005     }
2006   fn = cg_edge->callee->decl;
2007
2008 #ifdef ENABLE_CHECKING
2009   if (cg_edge->callee->decl != id->dst_node->decl)
2010     verify_cgraph_node (cg_edge->callee);
2011 #endif
2012
2013   /* We will be inlining this callee.  */
2014
2015   id->eh_region = lookup_stmt_eh_region (stmt);
2016
2017   /* Split the block holding the CALL_EXPR.  */
2018
2019   e = split_block (bb, stmt);
2020   bb = e->src;
2021   return_block = e->dest;
2022   remove_edge (e);
2023
2024   /* split_block splits before the statement, work around this by moving
2025      the call into the first half_bb.  Not pretty, but seems easier than
2026      doing the CFG manipulation by hand when the CALL_EXPR is in the last
2027      statement in BB.  */
2028   stmt_bsi = bsi_last (bb);
2029   bsi = bsi_start (return_block);
2030   if (!bsi_end_p (bsi))
2031     bsi_move_before (&stmt_bsi, &bsi);
2032   else
2033     {
2034       tree stmt = bsi_stmt (stmt_bsi);
2035       bsi_remove (&stmt_bsi, false);
2036       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2037     }
2038   stmt_bsi = bsi_start (return_block);
2039
2040   /* Build a block containing code to initialize the arguments, the
2041      actual inline expansion of the body, and a label for the return
2042      statements within the function to jump to.  The type of the
2043      statement expression is the return type of the function call.  */
2044   id->block = make_node (BLOCK);
2045   BLOCK_ABSTRACT_ORIGIN (id->block) = fn;
2046   BLOCK_SOURCE_LOCATION (id->block) = input_location;
2047   add_lexical_block (TREE_BLOCK (stmt), id->block);
2048
2049   /* Local declarations will be replaced by their equivalents in this
2050      map.  */
2051   st = id->decl_map;
2052   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
2053                                  NULL, NULL);
2054
2055   /* Initialize the parameters.  */
2056   args = TREE_OPERAND (t, 1);
2057
2058   /* Record the function we are about to inline.  */
2059   id->src_fn = fn;
2060   id->src_node = cg_edge->callee;
2061
2062   initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2), fn, bb);
2063
2064   if (DECL_INITIAL (fn))
2065     add_lexical_block (id->block, remap_blocks (DECL_INITIAL (fn), id));
2066
2067   /* Return statements in the function body will be replaced by jumps
2068      to the RET_LABEL.  */
2069
2070   gcc_assert (DECL_INITIAL (fn));
2071   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
2072
2073   /* Find the lhs to which the result of this call is assigned.  */
2074   return_slot_addr = NULL;
2075   if (TREE_CODE (stmt) == MODIFY_EXPR)
2076     {
2077       modify_dest = TREE_OPERAND (stmt, 0);
2078
2079       /* The function which we are inlining might not return a value,
2080          in which case we should issue a warning that the function
2081          does not return a value.  In that case the optimizers will
2082          see that the variable to which the value is assigned was not
2083          initialized.  We do not want to issue a warning about that
2084          uninitialized variable.  */
2085       if (DECL_P (modify_dest))
2086         TREE_NO_WARNING (modify_dest) = 1;
2087       if (CALL_EXPR_RETURN_SLOT_OPT (t))
2088         {
2089           return_slot_addr = build_fold_addr_expr (modify_dest);
2090           STRIP_USELESS_TYPE_CONVERSION (return_slot_addr);
2091           modify_dest = NULL;
2092         }
2093     }
2094   else
2095     modify_dest = NULL;
2096
2097   /* Declare the return variable for the function.  */
2098   decl = declare_return_variable (id, return_slot_addr,
2099                                   modify_dest, &use_retvar);
2100   /* Do this only if declare_return_variable created a new one.  */
2101   if (decl && !return_slot_addr && decl != modify_dest)
2102     declare_inline_vars (id->block, decl);
2103
2104   /* This is it.  Duplicate the callee body.  Assume callee is
2105      pre-gimplified.  Note that we must not alter the caller
2106      function in any way before this point, as this CALL_EXPR may be
2107      a self-referential call; if we're calling ourselves, we need to
2108      duplicate our body before altering anything.  */
2109   copy_body (id, bb->count, bb->frequency, bb, return_block);
2110
2111   /* Add local vars in this inlined callee to caller.  */
2112   t_step = id->src_cfun->unexpanded_var_list;
2113   for (; t_step; t_step = TREE_CHAIN (t_step))
2114     {
2115       var = TREE_VALUE (t_step);
2116       if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
2117         cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
2118                                                cfun->unexpanded_var_list);
2119       else
2120         cfun->unexpanded_var_list = tree_cons (NULL_TREE, remap_decl (var, id),
2121                                                cfun->unexpanded_var_list);
2122     }
2123
2124   /* Clean up.  */
2125   splay_tree_delete (id->decl_map);
2126   id->decl_map = st;
2127
2128   /* If the inlined function returns a result that we care about,
2129      clobber the CALL_EXPR with a reference to the return variable.  */
2130   if (use_retvar && (TREE_CODE (bsi_stmt (stmt_bsi)) != CALL_EXPR))
2131     {
2132       *tp = use_retvar;
2133       maybe_clean_or_replace_eh_stmt (stmt, stmt);
2134     }
2135   else
2136     /* We're modifying a TSI owned by gimple_expand_calls_inline();
2137        tsi_delink() will leave the iterator in a sane state.  */
2138     bsi_remove (&stmt_bsi, true);
2139
2140   bsi_next (&bsi);
2141   if (bsi_end_p (bsi))
2142     tree_purge_dead_eh_edges (return_block);
2143
2144   /* If the value of the new expression is ignored, that's OK.  We
2145      don't warn about this for CALL_EXPRs, so we shouldn't warn about
2146      the equivalent inlined version either.  */
2147   TREE_USED (*tp) = 1;
2148
2149   /* Output the inlining info for this abstract function, since it has been
2150      inlined.  If we don't do this now, we can lose the information about the
2151      variables in the function when the blocks get blown away as soon as we
2152      remove the cgraph node.  */
2153   (*debug_hooks->outlining_inline_function) (cg_edge->callee->decl);
2154
2155   /* Update callgraph if needed.  */
2156   cgraph_remove_node (cg_edge->callee);
2157
2158   /* Declare the 'auto' variables added with this inlined body.  */
2159   record_vars (BLOCK_VARS (id->block));
2160   id->block = NULL_TREE;
2161   successfully_inlined = TRUE;
2162
2163  egress:
2164   input_location = saved_location;
2165   return successfully_inlined;
2166 }
2167
2168 /* Expand call statements reachable from STMT_P.
2169    We can only have CALL_EXPRs as the "toplevel" tree code or nested
2170    in a MODIFY_EXPR.  See tree-gimple.c:get_call_expr_in().  We can
2171    unfortunately not use that function here because we need a pointer
2172    to the CALL_EXPR, not the tree itself.  */
2173
2174 static bool
2175 gimple_expand_calls_inline (basic_block bb, copy_body_data *id)
2176 {
2177   block_stmt_iterator bsi;
2178
2179   /* Register specific tree functions.  */
2180   tree_register_cfg_hooks ();
2181   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2182     {
2183       tree *expr_p = bsi_stmt_ptr (bsi);
2184       tree stmt = *expr_p;
2185
2186       if (TREE_CODE (*expr_p) == MODIFY_EXPR)
2187         expr_p = &TREE_OPERAND (*expr_p, 1);
2188       if (TREE_CODE (*expr_p) == WITH_SIZE_EXPR)
2189         expr_p = &TREE_OPERAND (*expr_p, 0);
2190       if (TREE_CODE (*expr_p) == CALL_EXPR)
2191         if (expand_call_inline (bb, stmt, expr_p, id))
2192           return true;
2193     }
2194   return false;
2195 }
2196
2197 /* Expand calls to inline functions in the body of FN.  */
2198
2199 void
2200 optimize_inline_calls (tree fn)
2201 {
2202   copy_body_data id;
2203   tree prev_fn;
2204   basic_block bb;
2205   /* There is no point in performing inlining if errors have already
2206      occurred -- and we might crash if we try to inline invalid
2207      code.  */
2208   if (errorcount || sorrycount)
2209     return;
2210
2211   /* Clear out ID.  */
2212   memset (&id, 0, sizeof (id));
2213
2214   id.src_node = id.dst_node = cgraph_node (fn);
2215   id.dst_fn = fn;
2216   /* Or any functions that aren't finished yet.  */
2217   prev_fn = NULL_TREE;
2218   if (current_function_decl)
2219     {
2220       id.dst_fn = current_function_decl;
2221       prev_fn = current_function_decl;
2222     }
2223
2224   id.copy_decl = copy_decl_maybe_to_var;
2225   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2226   id.transform_new_cfg = false;
2227   id.transform_return_to_modify = true;
2228   id.transform_lang_insert_block = false;
2229
2230   push_gimplify_context ();
2231
2232   /* Reach the trees by walking over the CFG, and note the
2233      enclosing basic-blocks in the call edges.  */
2234   /* We walk the blocks going forward, because inlined function bodies
2235      will split id->current_basic_block, and the new blocks will
2236      follow it; we'll trudge through them, processing their CALL_EXPRs
2237      along the way.  */
2238   FOR_EACH_BB (bb)
2239     gimple_expand_calls_inline (bb, &id);
2240
2241   pop_gimplify_context (NULL);
2242   /* Renumber the (code) basic_blocks consecutively.  */
2243   compact_blocks ();
2244   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2245   number_blocks (fn);
2246
2247 #ifdef ENABLE_CHECKING
2248     {
2249       struct cgraph_edge *e;
2250
2251       verify_cgraph_node (id.dst_node);
2252
2253       /* Double check that we inlined everything we are supposed to inline.  */
2254       for (e = id.dst_node->callees; e; e = e->next_callee)
2255         gcc_assert (e->inline_failed);
2256     }
2257 #endif
2258   /* We need to rescale frequencies again to peak at REG_BR_PROB_BASE
2259      as inlining loops might increase the maximum.  */
2260   if (ENTRY_BLOCK_PTR->count)
2261     counts_to_freqs ();
2262   fold_cond_expr_cond ();
2263 }
2264
2265 /* FN is a function that has a complete body, and CLONE is a function whose
2266    body is to be set to a copy of FN, mapping argument declarations according
2267    to the ARG_MAP splay_tree.  */
2268
2269 void
2270 clone_body (tree clone, tree fn, void *arg_map)
2271 {
2272   copy_body_data id;
2273
2274   /* Clone the body, as if we were making an inline call.  But, remap the
2275      parameters in the callee to the parameters of caller.  */
2276   memset (&id, 0, sizeof (id));
2277   id.src_fn = fn;
2278   id.dst_fn = clone;
2279   id.src_cfun = DECL_STRUCT_FUNCTION (fn);
2280   id.decl_map = (splay_tree)arg_map;
2281
2282   id.copy_decl = copy_decl_no_change;
2283   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2284   id.transform_new_cfg = true;
2285   id.transform_return_to_modify = false;
2286   id.transform_lang_insert_block = true;
2287
2288   /* We're not inside any EH region.  */
2289   id.eh_region = -1;
2290
2291   /* Actually copy the body.  */
2292   append_to_statement_list_force (copy_generic_body (&id), &DECL_SAVED_TREE (clone));
2293 }
2294
2295 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2296
2297 tree
2298 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2299 {
2300   enum tree_code code = TREE_CODE (*tp);
2301
2302   /* We make copies of most nodes.  */
2303   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2304       || code == TREE_LIST
2305       || code == TREE_VEC
2306       || code == TYPE_DECL
2307       || code == OMP_CLAUSE)
2308     {
2309       /* Because the chain gets clobbered when we make a copy, we save it
2310          here.  */
2311       tree chain = TREE_CHAIN (*tp);
2312       tree new;
2313
2314       /* Copy the node.  */
2315       new = copy_node (*tp);
2316
2317       /* Propagate mudflap marked-ness.  */
2318       if (flag_mudflap && mf_marked_p (*tp))
2319         mf_mark (new);
2320
2321       *tp = new;
2322
2323       /* Now, restore the chain, if appropriate.  That will cause
2324          walk_tree to walk into the chain as well.  */
2325       if (code == PARM_DECL
2326           || code == TREE_LIST
2327           || code == OMP_CLAUSE)
2328         TREE_CHAIN (*tp) = chain;
2329
2330       /* For now, we don't update BLOCKs when we make copies.  So, we
2331          have to nullify all BIND_EXPRs.  */
2332       if (TREE_CODE (*tp) == BIND_EXPR)
2333         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2334     }
2335   else if (code == CONSTRUCTOR)
2336     {
2337       /* CONSTRUCTOR nodes need special handling because
2338          we need to duplicate the vector of elements.  */
2339       tree new;
2340
2341       new = copy_node (*tp);
2342
2343       /* Propagate mudflap marked-ness.  */
2344       if (flag_mudflap && mf_marked_p (*tp))
2345         mf_mark (new);
2346
2347       CONSTRUCTOR_ELTS (new) = VEC_copy (constructor_elt, gc,
2348                                          CONSTRUCTOR_ELTS (*tp));
2349       *tp = new;
2350     }
2351   else if (TREE_CODE_CLASS (code) == tcc_type)
2352     *walk_subtrees = 0;
2353   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2354     *walk_subtrees = 0;
2355   else if (TREE_CODE_CLASS (code) == tcc_constant)
2356     *walk_subtrees = 0;
2357   else
2358     gcc_assert (code != STATEMENT_LIST);
2359   return NULL_TREE;
2360 }
2361
2362 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2363    information indicating to what new SAVE_EXPR this one should be mapped,
2364    use that one.  Otherwise, create a new node and enter it in ST.  FN is
2365    the function into which the copy will be placed.  */
2366
2367 static void
2368 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2369 {
2370   splay_tree st = (splay_tree) st_;
2371   splay_tree_node n;
2372   tree t;
2373
2374   /* See if we already encountered this SAVE_EXPR.  */
2375   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2376
2377   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2378   if (!n)
2379     {
2380       t = copy_node (*tp);
2381
2382       /* Remember this SAVE_EXPR.  */
2383       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2384       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2385       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2386     }
2387   else
2388     {
2389       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2390       *walk_subtrees = 0;
2391       t = (tree) n->value;
2392     }
2393
2394   /* Replace this SAVE_EXPR with the copy.  */
2395   *tp = t;
2396 }
2397
2398 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2399    copies the declaration and enters it in the splay_tree in DATA (which is
2400    really an `copy_body_data *').  */
2401
2402 static tree
2403 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2404                         void *data)
2405 {
2406   copy_body_data *id = (copy_body_data *) data;
2407
2408   /* Don't walk into types.  */
2409   if (TYPE_P (*tp))
2410     *walk_subtrees = 0;
2411
2412   else if (TREE_CODE (*tp) == LABEL_EXPR)
2413     {
2414       tree decl = TREE_OPERAND (*tp, 0);
2415
2416       /* Copy the decl and remember the copy.  */
2417       insert_decl_map (id, decl, id->copy_decl (decl, id));
2418     }
2419
2420   return NULL_TREE;
2421 }
2422
2423 /* Perform any modifications to EXPR required when it is unsaved.  Does
2424    not recurse into EXPR's subtrees.  */
2425
2426 static void
2427 unsave_expr_1 (tree expr)
2428 {
2429   switch (TREE_CODE (expr))
2430     {
2431     case TARGET_EXPR:
2432       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2433          It's OK for this to happen if it was part of a subtree that
2434          isn't immediately expanded, such as operand 2 of another
2435          TARGET_EXPR.  */
2436       if (TREE_OPERAND (expr, 1))
2437         break;
2438
2439       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2440       TREE_OPERAND (expr, 3) = NULL_TREE;
2441       break;
2442
2443     default:
2444       break;
2445     }
2446 }
2447
2448 /* Called via walk_tree when an expression is unsaved.  Using the
2449    splay_tree pointed to by ST (which is really a `splay_tree'),
2450    remaps all local declarations to appropriate replacements.  */
2451
2452 static tree
2453 unsave_r (tree *tp, int *walk_subtrees, void *data)
2454 {
2455   copy_body_data *id = (copy_body_data *) data;
2456   splay_tree st = id->decl_map;
2457   splay_tree_node n;
2458
2459   /* Only a local declaration (variable or label).  */
2460   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2461       || TREE_CODE (*tp) == LABEL_DECL)
2462     {
2463       /* Lookup the declaration.  */
2464       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2465
2466       /* If it's there, remap it.  */
2467       if (n)
2468         *tp = (tree) n->value;
2469     }
2470
2471   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2472     copy_statement_list (tp);
2473   else if (TREE_CODE (*tp) == BIND_EXPR)
2474     copy_bind_expr (tp, walk_subtrees, id);
2475   else if (TREE_CODE (*tp) == SAVE_EXPR)
2476     remap_save_expr (tp, st, walk_subtrees);
2477   else
2478     {
2479       copy_tree_r (tp, walk_subtrees, NULL);
2480
2481       /* Do whatever unsaving is required.  */
2482       unsave_expr_1 (*tp);
2483     }
2484
2485   /* Keep iterating.  */
2486   return NULL_TREE;
2487 }
2488
2489 /* Copies everything in EXPR and replaces variables, labels
2490    and SAVE_EXPRs local to EXPR.  */
2491
2492 tree
2493 unsave_expr_now (tree expr)
2494 {
2495   copy_body_data id;
2496
2497   /* There's nothing to do for NULL_TREE.  */
2498   if (expr == 0)
2499     return expr;
2500
2501   /* Set up ID.  */
2502   memset (&id, 0, sizeof (id));
2503   id.src_fn = current_function_decl;
2504   id.dst_fn = current_function_decl;
2505   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2506
2507   id.copy_decl = copy_decl_no_change;
2508   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2509   id.transform_new_cfg = false;
2510   id.transform_return_to_modify = false;
2511   id.transform_lang_insert_block = false;
2512
2513   /* Walk the tree once to find local labels.  */
2514   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2515
2516   /* Walk the tree again, copying, remapping, and unsaving.  */
2517   walk_tree (&expr, unsave_r, &id, NULL);
2518
2519   /* Clean up.  */
2520   splay_tree_delete (id.decl_map);
2521
2522   return expr;
2523 }
2524
2525 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2526
2527 static tree
2528 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2529 {
2530   if (*tp == data)
2531     return (tree) data;
2532   else
2533     return NULL;
2534 }
2535
2536 bool
2537 debug_find_tree (tree top, tree search)
2538 {
2539   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2540 }
2541
2542
2543 /* Declare the variables created by the inliner.  Add all the variables in
2544    VARS to BIND_EXPR.  */
2545
2546 static void
2547 declare_inline_vars (tree block, tree vars)
2548 {
2549   tree t;
2550   for (t = vars; t; t = TREE_CHAIN (t))
2551     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2552
2553   if (block)
2554     BLOCK_VARS (block) = chainon (BLOCK_VARS (block), vars);
2555 }
2556
2557
2558 /* Copy NODE (which must be a DECL).  The DECL originally was in the FROM_FN,
2559    but now it will be in the TO_FN.  PARM_TO_VAR means enable PARM_DECL to
2560    VAR_DECL translation.  */
2561
2562 static tree
2563 copy_decl_for_dup_finish (copy_body_data *id, tree decl, tree copy)
2564 {
2565   /* Don't generate debug information for the copy if we wouldn't have
2566      generated it for the copy either.  */
2567   DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (decl);
2568   DECL_IGNORED_P (copy) = DECL_IGNORED_P (decl);
2569
2570   /* Set the DECL_ABSTRACT_ORIGIN so the debugging routines know what
2571      declaration inspired this copy.  */
2572   DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (decl);
2573
2574   /* The new variable/label has no RTL, yet.  */
2575   if (CODE_CONTAINS_STRUCT (TREE_CODE (copy), TS_DECL_WRTL)
2576       && !TREE_STATIC (copy) && !DECL_EXTERNAL (copy))
2577     SET_DECL_RTL (copy, NULL_RTX);
2578
2579   /* These args would always appear unused, if not for this.  */
2580   TREE_USED (copy) = 1;
2581
2582   /* Set the context for the new declaration.  */
2583   if (!DECL_CONTEXT (decl))
2584     /* Globals stay global.  */
2585     ;
2586   else if (DECL_CONTEXT (decl) != id->src_fn)
2587     /* Things that weren't in the scope of the function we're inlining
2588        from aren't in the scope we're inlining to, either.  */
2589     ;
2590   else if (TREE_STATIC (decl))
2591     /* Function-scoped static variables should stay in the original
2592        function.  */
2593     ;
2594   else
2595     /* Ordinary automatic local variables are now in the scope of the
2596        new function.  */
2597     DECL_CONTEXT (copy) = id->dst_fn;
2598
2599   return copy;
2600 }
2601
2602 static tree
2603 copy_decl_to_var (tree decl, copy_body_data *id)
2604 {
2605   tree copy, type;
2606
2607   gcc_assert (TREE_CODE (decl) == PARM_DECL
2608               || TREE_CODE (decl) == RESULT_DECL);
2609
2610   type = TREE_TYPE (decl);
2611
2612   copy = build_decl (VAR_DECL, DECL_NAME (decl), type);
2613   TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (decl);
2614   TREE_READONLY (copy) = TREE_READONLY (decl);
2615   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (decl);
2616   DECL_COMPLEX_GIMPLE_REG_P (copy) = DECL_COMPLEX_GIMPLE_REG_P (decl);
2617
2618   return copy_decl_for_dup_finish (id, decl, copy);
2619 }
2620
2621 static tree
2622 copy_decl_no_change (tree decl, copy_body_data *id)
2623 {
2624   tree copy;
2625
2626   copy = copy_node (decl);
2627
2628   /* The COPY is not abstract; it will be generated in DST_FN.  */
2629   DECL_ABSTRACT (copy) = 0;
2630   lang_hooks.dup_lang_specific_decl (copy);
2631
2632   /* TREE_ADDRESSABLE isn't used to indicate that a label's address has
2633      been taken; it's for internal bookkeeping in expand_goto_internal.  */
2634   if (TREE_CODE (copy) == LABEL_DECL)
2635     {
2636       TREE_ADDRESSABLE (copy) = 0;
2637       LABEL_DECL_UID (copy) = -1;
2638     }
2639
2640   return copy_decl_for_dup_finish (id, decl, copy);
2641 }
2642
2643 static tree
2644 copy_decl_maybe_to_var (tree decl, copy_body_data *id)
2645 {
2646   if (TREE_CODE (decl) == PARM_DECL || TREE_CODE (decl) == RESULT_DECL)
2647     return copy_decl_to_var (decl, id);
2648   else
2649     return copy_decl_no_change (decl, id);
2650 }
2651
2652 /* Return a copy of the function's argument tree.  */
2653 static tree
2654 copy_arguments_for_versioning (tree orig_parm, copy_body_data * id)
2655 {
2656   tree *arg_copy, *parg;
2657
2658   arg_copy = &orig_parm;
2659   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
2660     {
2661       tree new = remap_decl (*parg, id);
2662       lang_hooks.dup_lang_specific_decl (new);
2663       TREE_CHAIN (new) = TREE_CHAIN (*parg);
2664       *parg = new;
2665     }
2666   return orig_parm;
2667 }
2668
2669 /* Return a copy of the function's static chain.  */
2670 static tree
2671 copy_static_chain (tree static_chain, copy_body_data * id)
2672 {
2673   tree *chain_copy, *pvar;
2674
2675   chain_copy = &static_chain;
2676   for (pvar = chain_copy; *pvar; pvar = &TREE_CHAIN (*pvar))
2677     {
2678       tree new = remap_decl (*pvar, id);
2679       lang_hooks.dup_lang_specific_decl (new);
2680       TREE_CHAIN (new) = TREE_CHAIN (*pvar);
2681       *pvar = new;
2682     }
2683   return static_chain;
2684 }
2685
2686 /* Return true if the function is allowed to be versioned.
2687    This is a guard for the versioning functionality.  */
2688 bool
2689 tree_versionable_function_p (tree fndecl)
2690 {
2691   if (fndecl == NULL_TREE)
2692     return false;
2693   /* ??? There are cases where a function is
2694      uninlinable but can be versioned.  */
2695   if (!tree_inlinable_function_p (fndecl))
2696     return false;
2697
2698   return true;
2699 }
2700
2701 /* Create a copy of a function's tree.
2702    OLD_DECL and NEW_DECL are FUNCTION_DECL tree nodes
2703    of the original function and the new copied function
2704    respectively.  In case we want to replace a DECL
2705    tree with another tree while duplicating the function's
2706    body, TREE_MAP represents the mapping between these
2707    trees. If UPDATE_CLONES is set, the call_stmt fields
2708    of edges of clones of the function will be updated.  */
2709 void
2710 tree_function_versioning (tree old_decl, tree new_decl, varray_type tree_map,
2711                           bool update_clones)
2712 {
2713   struct cgraph_node *old_version_node;
2714   struct cgraph_node *new_version_node;
2715   copy_body_data id;
2716   tree p, new_fndecl;
2717   unsigned i;
2718   struct ipa_replace_map *replace_info;
2719   basic_block old_entry_block;
2720   tree t_step;
2721
2722   gcc_assert (TREE_CODE (old_decl) == FUNCTION_DECL
2723               && TREE_CODE (new_decl) == FUNCTION_DECL);
2724   DECL_POSSIBLY_INLINED (old_decl) = 1;
2725
2726   old_version_node = cgraph_node (old_decl);
2727   new_version_node = cgraph_node (new_decl);
2728
2729   allocate_struct_function (new_decl);
2730   /* Cfun points to the new allocated function struct at this point.  */
2731   cfun->function_end_locus = DECL_SOURCE_LOCATION (new_decl);
2732
2733   DECL_ARTIFICIAL (new_decl) = 1;
2734   DECL_ABSTRACT_ORIGIN (new_decl) = DECL_ORIGIN (old_decl);
2735
2736   /* Generate a new name for the new version. */
2737   if (!update_clones)
2738     DECL_NAME (new_decl) = create_tmp_var_name (NULL);
2739   /* Create a new SYMBOL_REF rtx for the new name. */
2740   if (DECL_RTL (old_decl) != NULL)
2741     {
2742       SET_DECL_RTL (new_decl, copy_rtx (DECL_RTL (old_decl)));
2743       XEXP (DECL_RTL (new_decl), 0) =
2744         gen_rtx_SYMBOL_REF (GET_MODE (XEXP (DECL_RTL (old_decl), 0)),
2745                             IDENTIFIER_POINTER (DECL_NAME (new_decl)));
2746     }
2747
2748   /* Prepare the data structures for the tree copy.  */
2749   memset (&id, 0, sizeof (id));
2750
2751   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2752   id.src_fn = old_decl;
2753   id.dst_fn = new_decl;
2754   id.src_node = old_version_node;
2755   id.dst_node = new_version_node;
2756   id.src_cfun = DECL_STRUCT_FUNCTION (old_decl);
2757
2758   id.copy_decl = copy_decl_no_change;
2759   id.transform_call_graph_edges
2760     = update_clones ? CB_CGE_MOVE_CLONES : CB_CGE_MOVE;
2761   id.transform_new_cfg = true;
2762   id.transform_return_to_modify = false;
2763   id.transform_lang_insert_block = false;
2764
2765   current_function_decl = new_decl;
2766
2767   /* Copy the function's static chain.  */
2768   p = DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl;
2769   if (p)
2770     DECL_STRUCT_FUNCTION (new_decl)->static_chain_decl =
2771       copy_static_chain (DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl,
2772                          &id);
2773   /* Copy the function's arguments.  */
2774   if (DECL_ARGUMENTS (old_decl) != NULL_TREE)
2775     DECL_ARGUMENTS (new_decl) =
2776       copy_arguments_for_versioning (DECL_ARGUMENTS (old_decl), &id);
2777
2778   /* If there's a tree_map, prepare for substitution.  */
2779   if (tree_map)
2780     for (i = 0; i < VARRAY_ACTIVE_SIZE (tree_map); i++)
2781       {
2782         replace_info = VARRAY_GENERIC_PTR (tree_map, i);
2783         if (replace_info->replace_p)
2784           insert_decl_map (&id, replace_info->old_tree,
2785                            replace_info->new_tree);
2786       }
2787
2788   DECL_INITIAL (new_decl) = remap_blocks (DECL_INITIAL (id.src_fn), &id);
2789
2790   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2791   number_blocks (id.dst_fn);
2792
2793   if (DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list != NULL_TREE)
2794     /* Add local vars.  */
2795     for (t_step = DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list;
2796          t_step; t_step = TREE_CHAIN (t_step))
2797       {
2798         tree var = TREE_VALUE (t_step);
2799         if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
2800           cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
2801                                                  cfun->unexpanded_var_list);
2802         else
2803           cfun->unexpanded_var_list =
2804             tree_cons (NULL_TREE, remap_decl (var, &id),
2805                        cfun->unexpanded_var_list);
2806       }
2807
2808   /* Copy the Function's body.  */
2809   old_entry_block = ENTRY_BLOCK_PTR_FOR_FUNCTION
2810     (DECL_STRUCT_FUNCTION (old_decl));
2811   new_fndecl = copy_body (&id,
2812                           old_entry_block->count,
2813                           old_entry_block->frequency, NULL, NULL);
2814
2815   DECL_SAVED_TREE (new_decl) = DECL_SAVED_TREE (new_fndecl);
2816
2817   DECL_STRUCT_FUNCTION (new_decl)->cfg =
2818     DECL_STRUCT_FUNCTION (new_fndecl)->cfg;
2819   DECL_STRUCT_FUNCTION (new_decl)->eh = DECL_STRUCT_FUNCTION (new_fndecl)->eh;
2820   DECL_STRUCT_FUNCTION (new_decl)->ib_boundaries_block =
2821     DECL_STRUCT_FUNCTION (new_fndecl)->ib_boundaries_block;
2822   DECL_STRUCT_FUNCTION (new_decl)->last_label_uid =
2823     DECL_STRUCT_FUNCTION (new_fndecl)->last_label_uid;
2824
2825   if (DECL_RESULT (old_decl) != NULL_TREE)
2826     {
2827       tree *res_decl = &DECL_RESULT (old_decl);
2828       DECL_RESULT (new_decl) = remap_decl (*res_decl, &id);
2829       lang_hooks.dup_lang_specific_decl (DECL_RESULT (new_decl));
2830     }
2831
2832   current_function_decl = NULL;
2833   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2834   number_blocks (new_decl);
2835
2836   /* Clean up.  */
2837   splay_tree_delete (id.decl_map);
2838   fold_cond_expr_cond ();
2839   return;
2840 }
2841
2842 /* Duplicate a type, fields and all.  */
2843
2844 tree
2845 build_duplicate_type (tree type)
2846 {
2847   struct copy_body_data id;
2848
2849   memset (&id, 0, sizeof (id));
2850   id.src_fn = current_function_decl;
2851   id.dst_fn = current_function_decl;
2852   id.src_cfun = cfun;
2853   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2854
2855   type = remap_type_1 (type, &id);
2856
2857   splay_tree_delete (id.decl_map);
2858
2859   return type;
2860 }