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