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