gcc/tree-inline.c

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