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               tree *stmtp = bsi_stmt_ptr (copy_bsi);
 819               tree stmt = *stmtp;
 820               call = get_call_expr_in (stmt);
 821
 822               if (call && CALL_EXPR_VA_ARG_PACK (call) && id->call_expr)
 823                 {
 824                   /* __builtin_va_arg_pack () should be replaced by
 825                      all arguments corresponding to ... in the caller.  */
 826                   tree p, *argarray, new_call, *call_ptr;
 827                   int nargs = call_expr_nargs (id->call_expr);
 828
 829                   for (p = DECL_ARGUMENTS (id->src_fn); p; p = TREE_CHAIN (p))
 830                     nargs--;
 831
 832                   argarray = (tree *) alloca ((nargs + call_expr_nargs (call))
 833                                               * sizeof (tree));
 834
 835                   memcpy (argarray, CALL_EXPR_ARGP (call),
 836                           call_expr_nargs (call) * sizeof (*argarray));
 837                   memcpy (argarray + call_expr_nargs (call),
 838                           CALL_EXPR_ARGP (id->call_expr)
 839                           + (call_expr_nargs (id->call_expr) - nargs),
 840                           nargs * sizeof (*argarray));
 841
 842                   new_call = build_call_array (TREE_TYPE (call),
 843                                                CALL_EXPR_FN (call),
 844                                                nargs + call_expr_nargs (call),
 845                                                argarray);
 846                   /* Copy all CALL_EXPR flags, locus and block, except
 847                      CALL_EXPR_VA_ARG_PACK flag.  */
 848                   CALL_EXPR_STATIC_CHAIN (new_call)
 849                     = CALL_EXPR_STATIC_CHAIN (call);
 850                   CALL_EXPR_TAILCALL (new_call) = CALL_EXPR_TAILCALL (call);
 851                   CALL_EXPR_RETURN_SLOT_OPT (new_call)
 852                     = CALL_EXPR_RETURN_SLOT_OPT (call);
 853                   CALL_FROM_THUNK_P (new_call) = CALL_FROM_THUNK_P (call);
 854                   CALL_CANNOT_INLINE_P (new_call)
 855                     = CALL_CANNOT_INLINE_P (call);
 856                   TREE_NOTHROW (new_call) = TREE_NOTHROW (call);
 857                   SET_EXPR_LOCUS (new_call, EXPR_LOCUS (call));
 858                   TREE_BLOCK (new_call) = TREE_BLOCK (call);
 859
 860                   call_ptr = stmtp;
 861                   if (TREE_CODE (*call_ptr) == GIMPLE_MODIFY_STMT)
 862                     call_ptr = &GIMPLE_STMT_OPERAND (*call_ptr, 1);
 863                   if (TREE_CODE (*call_ptr) == WITH_SIZE_EXPR)
 864                     call_ptr = &TREE_OPERAND (*call_ptr, 0);
 865                   gcc_assert (*call_ptr == call);
 866                   *call_ptr = new_call;
 867                   stmt = *stmtp;
 868                   update_stmt (stmt);
 869                 }
 870
 871               /* Statements produced by inlining can be unfolded, especially
 872                  when we constant propagated some operands.  We can't fold
 873                  them right now for two reasons:
 874                  1) folding require SSA_NAME_DEF_STMTs to be correct
 875                  2) we can't change function calls to builtins.
 876                  So we just mark statement for later folding.  We mark
 877                  all new statements, instead just statements that has changed
 878                  by some nontrivial substitution so even statements made
 879                  foldable indirectly are updated.  If this turns out to be
 880                  expensive, copy_body can be told to watch for nontrivial
 881                  changes.  */
 882               if (id->statements_to_fold)
 883                 pointer_set_insert (id->statements_to_fold, stmt);
 884               /* We're duplicating a CALL_EXPR.  Find any corresponding
 885                  callgraph edges and update or duplicate them.  */
 886               if (call && (decl = get_callee_fndecl (call)))
 887                 {
 888                   struct cgraph_node *node;
 889                   struct cgraph_edge *edge;
 890
 891                   switch (id->transform_call_graph_edges)
 892                     {
 893                     case CB_CGE_DUPLICATE:
 894                       edge = cgraph_edge (id->src_node, orig_stmt);
 895                       if (edge)
 896                         cgraph_clone_edge (edge, id->dst_node, stmt,
 897                                            REG_BR_PROB_BASE, 1, edge->frequency, true);
 898                       break;
 899
 900                     case CB_CGE_MOVE_CLONES:
 901                       for (node = id->dst_node->next_clone;
 902                            node;
 903                            node = node->next_clone)
 904                         {
 905                           edge = cgraph_edge (node, orig_stmt);
 906                           gcc_assert (edge);
 907                           cgraph_set_call_stmt (edge, stmt);
 908                         }
 909                       /* FALLTHRU */
 910
 911                     case CB_CGE_MOVE:
 912                       edge = cgraph_edge (id->dst_node, orig_stmt);
 913                       if (edge)
 914                         cgraph_set_call_stmt (edge, stmt);
 915                       break;
 916
 917                     default:
 918                       gcc_unreachable ();
 919                     }
 920                 }
 921               /* If you think we can abort here, you are wrong.
 922                  There is no region 0 in tree land.  */
 923               gcc_assert (lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt)
 924                           != 0);
 925
 926               if (tree_could_throw_p (stmt)
 927                   /* When we are cloning for inlining, we are supposed to
 928                      construct a clone that calls precisely the same functions
 929                      as original.  However IPA optimizers might've proved
 930                      earlier some function calls as non-trapping that might
 931                      render some basic blocks dead that might become
 932                      unreachable.
 933
 934                      We can't update SSA with unreachable blocks in CFG and thus
 935                      we prevent the scenario by preserving even the "dead" eh
 936                      edges until the point they are later removed by
 937                      fixup_cfg pass.  */
 938                   || (id->transform_call_graph_edges == CB_CGE_MOVE_CLONES
 939                       && lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt) > 0))
 940                 {
 941                   int region = lookup_stmt_eh_region_fn (id->src_cfun, orig_stmt);
 942                   /* Add an entry for the copied tree in the EH hashtable.
 943                      When cloning or versioning, use the hashtable in
 944                      cfun, and just copy the EH number.  When inlining, use the
 945                      hashtable in the caller, and adjust the region number.  */
 946                   if (region > 0)
 947                     add_stmt_to_eh_region (stmt, region + id->eh_region_offset);
 948
 949                   /* If this tree doesn't have a region associated with it,
 950                      and there is a "current region,"
 951                      then associate this tree with the current region
 952                      and add edges associated with this region.  */
 953                   if ((lookup_stmt_eh_region_fn (id->src_cfun,
 954                                                  orig_stmt) <= 0
 955                        && id->eh_region > 0)
 956                       && tree_could_throw_p (stmt))
 957                     add_stmt_to_eh_region (stmt, id->eh_region);
 958                 }
 959               if (gimple_in_ssa_p (cfun))
 960                 {
 961                    ssa_op_iter i;
 962                    tree def;
 963
 964                    find_new_referenced_vars (bsi_stmt_ptr (copy_bsi));
 965                    FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
 966                     if (TREE_CODE (def) == SSA_NAME)
 967                       SSA_NAME_DEF_STMT (def) = stmt;
 968                 }
 969               bsi_next (&copy_bsi);
 970             }
 971           copy_bsi = bsi_last (copy_basic_block);
 972         }
 973     }
 974   return copy_basic_block;
 975 }
 976
 977 /* Inserting Single Entry Multiple Exit region in SSA form into code in SSA
 978    form is quite easy, since dominator relationship for old basic blocks does
 979    not change.
 980
 981    There is however exception where inlining might change dominator relation
 982    across EH edges from basic block within inlined functions destinating
 983    to landing pads in function we inline into.
 984
 985    The function mark PHI_RESULT of such PHI nodes for renaming; it is
 986    safe the EH edges are abnormal and SSA_NAME_OCCURS_IN_ABNORMAL_PHI
 987    must be set.  This means, that there will be no overlapping live ranges
 988    for the underlying symbol.
 989
 990    This might change in future if we allow redirecting of EH edges and
 991    we might want to change way build CFG pre-inlining to include
 992    all the possible edges then.  */
 993 static void
 994 update_ssa_across_eh_edges (basic_block bb)
 995 {
 996   edge e;
 997   edge_iterator ei;
 998
 999   FOR_EACH_EDGE (e, ei, bb->succs)
1000     if (!e->dest->aux
1001         || ((basic_block)e->dest->aux)->index == ENTRY_BLOCK)
1002       {
1003         tree phi;
1004
1005         gcc_assert (e->flags & EDGE_EH);
1006         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1007           {
1008             gcc_assert (SSA_NAME_OCCURS_IN_ABNORMAL_PHI
1009                         (PHI_RESULT (phi)));
1010             mark_sym_for_renaming
1011               (SSA_NAME_VAR (PHI_RESULT (phi)));
1012           }
1013       }
1014 }
1015
1016 /* Copy edges from BB into its copy constructed earlier, scale profile
1017    accordingly.  Edges will be taken care of later.  Assume aux
1018    pointers to point to the copies of each BB.  */
1019 static void
1020 copy_edges_for_bb (basic_block bb, int count_scale)
1021 {
1022   basic_block new_bb = (basic_block) bb->aux;
1023   edge_iterator ei;
1024   edge old_edge;
1025   block_stmt_iterator bsi;
1026   int flags;
1027
1028   /* Use the indices from the original blocks to create edges for the
1029      new ones.  */
1030   FOR_EACH_EDGE (old_edge, ei, bb->succs)
1031     if (!(old_edge->flags & EDGE_EH))
1032       {
1033         edge new;
1034
1035         flags = old_edge->flags;
1036
1037         /* Return edges do get a FALLTHRU flag when the get inlined.  */
1038         if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags
1039             && old_edge->dest->aux != EXIT_BLOCK_PTR)
1040           flags |= EDGE_FALLTHRU;
1041         new = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
1042         new->count = old_edge->count * count_scale / REG_BR_PROB_BASE;
1043         new->probability = old_edge->probability;
1044       }
1045
1046   if (bb->index == ENTRY_BLOCK || bb->index == EXIT_BLOCK)
1047     return;
1048
1049   for (bsi = bsi_start (new_bb); !bsi_end_p (bsi);)
1050     {
1051       tree copy_stmt;
1052
1053       copy_stmt = bsi_stmt (bsi);
1054       update_stmt (copy_stmt);
1055       if (gimple_in_ssa_p (cfun))
1056         mark_symbols_for_renaming (copy_stmt);
1057       /* Do this before the possible split_block.  */
1058       bsi_next (&bsi);
1059
1060       /* If this tree could throw an exception, there are two
1061          cases where we need to add abnormal edge(s): the
1062          tree wasn't in a region and there is a "current
1063          region" in the caller; or the original tree had
1064          EH edges.  In both cases split the block after the tree,
1065          and add abnormal edge(s) as needed; we need both
1066          those from the callee and the caller.
1067          We check whether the copy can throw, because the const
1068          propagation can change an INDIRECT_REF which throws
1069          into a COMPONENT_REF which doesn't.  If the copy
1070          can throw, the original could also throw.  */
1071
1072       if (tree_can_throw_internal (copy_stmt))
1073         {
1074           if (!bsi_end_p (bsi))
1075             /* Note that bb's predecessor edges aren't necessarily
1076                right at this point; split_block doesn't care.  */
1077             {
1078               edge e = split_block (new_bb, copy_stmt);
1079
1080               new_bb = e->dest;
1081               new_bb->aux = e->src->aux;
1082               bsi = bsi_start (new_bb);
1083             }
1084
1085            make_eh_edges (copy_stmt);
1086
1087            if (gimple_in_ssa_p (cfun))
1088              update_ssa_across_eh_edges (bb_for_stmt (copy_stmt));
1089         }
1090     }
1091 }
1092
1093 /* Copy the PHIs.  All blocks and edges are copied, some blocks
1094    was possibly split and new outgoing EH edges inserted.
1095    BB points to the block of original function and AUX pointers links
1096    the original and newly copied blocks.  */
1097
1098 static void
1099 copy_phis_for_bb (basic_block bb, copy_body_data *id)
1100 {
1101   basic_block new_bb = bb->aux;
1102   edge_iterator ei;
1103   tree phi;
1104
1105   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1106     {
1107       tree res = PHI_RESULT (phi);
1108       tree new_res = res;
1109       tree new_phi;
1110       edge new_edge;
1111
1112       if (is_gimple_reg (res))
1113         {
1114           walk_tree (&new_res, copy_body_r, id, NULL);
1115           SSA_NAME_DEF_STMT (new_res)
1116             = new_phi = create_phi_node (new_res, new_bb);
1117           FOR_EACH_EDGE (new_edge, ei, new_bb->preds)
1118             {
1119               edge old_edge = find_edge (new_edge->src->aux, bb);
1120               tree arg = PHI_ARG_DEF_FROM_EDGE (phi, old_edge);
1121               tree new_arg = arg;
1122
1123               walk_tree (&new_arg, copy_body_r, id, NULL);
1124               gcc_assert (new_arg);
1125               add_phi_arg (new_phi, new_arg, new_edge);
1126             }
1127         }
1128     }
1129 }
1130
1131 /* Wrapper for remap_decl so it can be used as a callback.  */
1132 static tree
1133 remap_decl_1 (tree decl, void *data)
1134 {
1135   return remap_decl (decl, (copy_body_data *) data);
1136 }
1137
1138 /* Build struct function and associated datastructures for the new clone
1139    NEW_FNDECL to be build.  CALLEE_FNDECL is the original */
1140
1141 static void
1142 initialize_cfun (tree new_fndecl, tree callee_fndecl, gcov_type count,
1143                  int frequency)
1144 {
1145   struct function *new_cfun
1146      = (struct function *) ggc_alloc_cleared (sizeof (struct function));
1147   struct function *src_cfun = DECL_STRUCT_FUNCTION (callee_fndecl);
1148   int count_scale, frequency_scale;
1149
1150   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count)
1151     count_scale = (REG_BR_PROB_BASE * count
1152                    / ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count);
1153   else
1154     count_scale = 1;
1155
1156   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency)
1157     frequency_scale = (REG_BR_PROB_BASE * frequency
1158                        /
1159                        ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency);
1160   else
1161     frequency_scale = count_scale;
1162
1163   /* Register specific tree functions.  */
1164   tree_register_cfg_hooks ();
1165   *new_cfun = *DECL_STRUCT_FUNCTION (callee_fndecl);
1166   new_cfun->funcdef_no = get_next_funcdef_no ();
1167   VALUE_HISTOGRAMS (new_cfun) = NULL;
1168   new_cfun->unexpanded_var_list = NULL;
1169   new_cfun->cfg = NULL;
1170   new_cfun->decl = new_fndecl /*= copy_node (callee_fndecl)*/;
1171   DECL_STRUCT_FUNCTION (new_fndecl) = new_cfun;
1172   push_cfun (new_cfun);
1173   init_empty_tree_cfg ();
1174
1175   ENTRY_BLOCK_PTR->count =
1176     (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
1177      REG_BR_PROB_BASE);
1178   ENTRY_BLOCK_PTR->frequency =
1179     (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
1180      frequency_scale / REG_BR_PROB_BASE);
1181   EXIT_BLOCK_PTR->count =
1182     (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count * count_scale /
1183      REG_BR_PROB_BASE);
1184   EXIT_BLOCK_PTR->frequency =
1185     (EXIT_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency *
1186      frequency_scale / REG_BR_PROB_BASE);
1187   if (src_cfun->eh)
1188     init_eh_for_function ();
1189
1190   if (src_cfun->gimple_df)
1191     {
1192       init_tree_ssa ();
1193       cfun->gimple_df->in_ssa_p = true;
1194       init_ssa_operands ();
1195     }
1196   pop_cfun ();
1197 }
1198
1199 /* Make a copy of the body of FN so that it can be inserted inline in
1200    another function.  Walks FN via CFG, returns new fndecl.  */
1201
1202 static tree
1203 copy_cfg_body (copy_body_data * id, gcov_type count, int frequency,
1204                basic_block entry_block_map, basic_block exit_block_map)
1205 {
1206   tree callee_fndecl = id->src_fn;
1207   /* Original cfun for the callee, doesn't change.  */
1208   struct function *src_cfun = DECL_STRUCT_FUNCTION (callee_fndecl);
1209   struct function *cfun_to_copy;
1210   basic_block bb;
1211   tree new_fndecl = NULL;
1212   int count_scale, frequency_scale;
1213   int last;
1214
1215   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count)
1216     count_scale = (REG_BR_PROB_BASE * count
1217                    / ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->count);
1218   else
1219     count_scale = 1;
1220
1221   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency)
1222     frequency_scale = (REG_BR_PROB_BASE * frequency
1223                        /
1224                        ENTRY_BLOCK_PTR_FOR_FUNCTION (src_cfun)->frequency);
1225   else
1226     frequency_scale = count_scale;
1227
1228   /* Register specific tree functions.  */
1229   tree_register_cfg_hooks ();
1230
1231   /* Must have a CFG here at this point.  */
1232   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION
1233               (DECL_STRUCT_FUNCTION (callee_fndecl)));
1234
1235   cfun_to_copy = id->src_cfun = DECL_STRUCT_FUNCTION (callee_fndecl);
1236
1237
1238   ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = entry_block_map;
1239   EXIT_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy)->aux = exit_block_map;
1240   entry_block_map->aux = ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy);
1241   exit_block_map->aux = EXIT_BLOCK_PTR_FOR_FUNCTION (cfun_to_copy);
1242
1243   /* Duplicate any exception-handling regions.  */
1244   if (cfun->eh)
1245     {
1246       id->eh_region_offset
1247         = duplicate_eh_regions (cfun_to_copy, remap_decl_1, id,
1248                                 0, id->eh_region);
1249     }
1250   /* Use aux pointers to map the original blocks to copy.  */
1251   FOR_EACH_BB_FN (bb, cfun_to_copy)
1252     {
1253       basic_block new = copy_bb (id, bb, frequency_scale, count_scale);
1254       bb->aux = new;
1255       new->aux = bb;
1256     }
1257
1258   last = last_basic_block;
1259   /* Now that we've duplicated the blocks, duplicate their edges.  */
1260   FOR_ALL_BB_FN (bb, cfun_to_copy)
1261     copy_edges_for_bb (bb, count_scale);
1262   if (gimple_in_ssa_p (cfun))
1263     FOR_ALL_BB_FN (bb, cfun_to_copy)
1264       copy_phis_for_bb (bb, id);
1265   FOR_ALL_BB_FN (bb, cfun_to_copy)
1266     {
1267       ((basic_block)bb->aux)->aux = NULL;
1268       bb->aux = NULL;
1269     }
1270   /* Zero out AUX fields of newly created block during EH edge
1271      insertion. */
1272   for (; last < last_basic_block; last++)
1273     BASIC_BLOCK (last)->aux = NULL;
1274   entry_block_map->aux = NULL;
1275   exit_block_map->aux = NULL;
1276
1277   return new_fndecl;
1278 }
1279
1280 /* Make a copy of the body of FN so that it can be inserted inline in
1281    another function.  */
1282
1283 static tree
1284 copy_generic_body (copy_body_data *id)
1285 {
1286   tree body;
1287   tree fndecl = id->src_fn;
1288
1289   body = DECL_SAVED_TREE (fndecl);
1290   walk_tree (&body, copy_body_r, id, NULL);
1291
1292   return body;
1293 }
1294
1295 static tree
1296 copy_body (copy_body_data *id, gcov_type count, int frequency,
1297            basic_block entry_block_map, basic_block exit_block_map)
1298 {
1299   tree fndecl = id->src_fn;
1300   tree body;
1301
1302   /* If this body has a CFG, walk CFG and copy.  */
1303   gcc_assert (ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (fndecl)));
1304   body = copy_cfg_body (id, count, frequency, entry_block_map, exit_block_map);
1305
1306   return body;
1307 }
1308
1309 /* Return true if VALUE is an ADDR_EXPR of an automatic variable
1310    defined in function FN, or of a data member thereof.  */
1311
1312 static bool
1313 self_inlining_addr_expr (tree value, tree fn)
1314 {
1315   tree var;
1316
1317   if (TREE_CODE (value) != ADDR_EXPR)
1318     return false;
1319
1320   var = get_base_address (TREE_OPERAND (value, 0));
1321
1322   return var && auto_var_in_fn_p (var, fn);
1323 }
1324
1325 static void
1326 setup_one_parameter (copy_body_data *id, tree p, tree value, tree fn,
1327                      basic_block bb, tree *vars)
1328 {
1329   tree init_stmt;
1330   tree var;
1331   tree var_sub;
1332   tree rhs = value;
1333   tree def = (gimple_in_ssa_p (cfun)
1334               ? gimple_default_def (id->src_cfun, p) : NULL);
1335
1336   if (value
1337       && value != error_mark_node
1338       && !useless_type_conversion_p (TREE_TYPE (p), TREE_TYPE (value)))
1339     rhs = fold_build1 (NOP_EXPR, TREE_TYPE (p), value);
1340
1341   /* If the parameter is never assigned to, has no SSA_NAMEs created,
1342      we may not need to create a new variable here at all.  Instead, we may
1343      be able to just use the argument value.  */
1344   if (TREE_READONLY (p)
1345       && !TREE_ADDRESSABLE (p)
1346       && value && !TREE_SIDE_EFFECTS (value)
1347       && !def)
1348     {
1349       /* We may produce non-gimple trees by adding NOPs or introduce
1350          invalid sharing when operand is not really constant.
1351          It is not big deal to prohibit constant propagation here as
1352          we will constant propagate in DOM1 pass anyway.  */
1353       if (is_gimple_min_invariant (value)
1354           && useless_type_conversion_p (TREE_TYPE (p),
1355                                                  TREE_TYPE (value))
1356           /* We have to be very careful about ADDR_EXPR.  Make sure
1357              the base variable isn't a local variable of the inlined
1358              function, e.g., when doing recursive inlining, direct or
1359              mutually-recursive or whatever, which is why we don't
1360              just test whether fn == current_function_decl.  */
1361           && ! self_inlining_addr_expr (value, fn))
1362         {
1363           insert_decl_map (id, p, value);
1364           return;
1365         }
1366     }
1367
1368   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
1369      here since the type of this decl must be visible to the calling
1370      function.  */
1371   var = copy_decl_to_var (p, id);
1372   if (gimple_in_ssa_p (cfun) && TREE_CODE (var) == VAR_DECL)
1373     {
1374       get_var_ann (var);
1375       add_referenced_var (var);
1376     }
1377
1378   /* See if the frontend wants to pass this by invisible reference.  If
1379      so, our new VAR_DECL will have REFERENCE_TYPE, and we need to
1380      replace uses of the PARM_DECL with dereferences.  */
1381   if (TREE_TYPE (var) != TREE_TYPE (p)
1382       && POINTER_TYPE_P (TREE_TYPE (var))
1383       && TREE_TYPE (TREE_TYPE (var)) == TREE_TYPE (p))
1384     {
1385       insert_decl_map (id, var, var);
1386       var_sub = build_fold_indirect_ref (var);
1387     }
1388   else
1389     var_sub = var;
1390
1391   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
1392      that way, when the PARM_DECL is encountered, it will be
1393      automatically replaced by the VAR_DECL.  */
1394   insert_decl_map (id, p, var_sub);
1395
1396   /* Declare this new variable.  */
1397   TREE_CHAIN (var) = *vars;
1398   *vars = var;
1399
1400   /* Make gimplifier happy about this variable.  */
1401   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1402
1403   /* Even if P was TREE_READONLY, the new VAR should not be.
1404      In the original code, we would have constructed a
1405      temporary, and then the function body would have never
1406      changed the value of P.  However, now, we will be
1407      constructing VAR directly.  The constructor body may
1408      change its value multiple times as it is being
1409      constructed.  Therefore, it must not be TREE_READONLY;
1410      the back-end assumes that TREE_READONLY variable is
1411      assigned to only once.  */
1412   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
1413     TREE_READONLY (var) = 0;
1414
1415   /* If there is no setup required and we are in SSA, take the easy route
1416      replacing all SSA names representing the function parameter by the
1417      SSA name passed to function.
1418
1419      We need to construct map for the variable anyway as it might be used
1420      in different SSA names when parameter is set in function.
1421
1422      FIXME: This usually kills the last connection in between inlined
1423      function parameter and the actual value in debug info.  Can we do
1424      better here?  If we just inserted the statement, copy propagation
1425      would kill it anyway as it always did in older versions of GCC.
1426
1427      We might want to introduce a notion that single SSA_NAME might
1428      represent multiple variables for purposes of debugging. */
1429   if (gimple_in_ssa_p (cfun) && rhs && def && is_gimple_reg (p)
1430       && (TREE_CODE (rhs) == SSA_NAME
1431           || is_gimple_min_invariant (rhs))
1432       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1433     {
1434       insert_decl_map (id, def, rhs);
1435       return;
1436     }
1437
1438   /* Initialize this VAR_DECL from the equivalent argument.  Convert
1439      the argument to the proper type in case it was promoted.  */
1440   if (value)
1441     {
1442       block_stmt_iterator bsi = bsi_last (bb);
1443
1444       if (rhs == error_mark_node)
1445         {
1446           insert_decl_map (id, p, var_sub);
1447           return;
1448         }
1449
1450       STRIP_USELESS_TYPE_CONVERSION (rhs);
1451
1452       /* We want to use GIMPLE_MODIFY_STMT, not INIT_EXPR here so that we
1453          keep our trees in gimple form.  */
1454       if (def && gimple_in_ssa_p (cfun) && is_gimple_reg (p))
1455         {
1456           def = remap_ssa_name (def, id);
1457           init_stmt = build_gimple_modify_stmt (def, rhs);
1458           SSA_NAME_DEF_STMT (def) = init_stmt;
1459           SSA_NAME_IS_DEFAULT_DEF (def) = 0;
1460           set_default_def (var, NULL);
1461         }
1462       else
1463         init_stmt = build_gimple_modify_stmt (var, rhs);
1464
1465       /* If we did not create a gimple value and we did not create a gimple
1466          cast of a gimple value, then we will need to gimplify INIT_STMTS
1467          at the end.  Note that is_gimple_cast only checks the outer
1468          tree code, not its operand.  Thus the explicit check that its
1469          operand is a gimple value.  */
1470       if ((!is_gimple_val (rhs)
1471           && (!is_gimple_cast (rhs)
1472               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
1473           || !is_gimple_reg (var))
1474         {
1475           tree_stmt_iterator i;
1476
1477           push_gimplify_context ();
1478           gimplify_stmt (&init_stmt);
1479           if (gimple_in_ssa_p (cfun)
1480               && init_stmt && TREE_CODE (init_stmt) == STATEMENT_LIST)
1481             {
1482               /* The replacement can expose previously unreferenced
1483                  variables.  */
1484               for (i = tsi_start (init_stmt); !tsi_end_p (i); tsi_next (&i))
1485                 find_new_referenced_vars (tsi_stmt_ptr (i));
1486              }
1487           pop_gimplify_context (NULL);
1488         }
1489
1490       /* If VAR represents a zero-sized variable, it's possible that the
1491          assignment statment may result in no gimple statements.  */
1492       if (init_stmt)
1493         bsi_insert_after (&bsi, init_stmt, BSI_NEW_STMT);
1494       if (gimple_in_ssa_p (cfun))
1495         for (;!bsi_end_p (bsi); bsi_next (&bsi))
1496           mark_symbols_for_renaming (bsi_stmt (bsi));
1497     }
1498 }
1499
1500 /* Generate code to initialize the parameters of the function at the
1501    top of the stack in ID from the CALL_EXPR EXP.  */
1502
1503 static void
1504 initialize_inlined_parameters (copy_body_data *id, tree exp,
1505                                tree fn, basic_block bb)
1506 {
1507   tree parms;
1508   tree a;
1509   tree p;
1510   tree vars = NULL_TREE;
1511   call_expr_arg_iterator iter;
1512   tree static_chain = CALL_EXPR_STATIC_CHAIN (exp);
1513
1514   /* Figure out what the parameters are.  */
1515   parms = DECL_ARGUMENTS (fn);
1516
1517   /* Loop through the parameter declarations, replacing each with an
1518      equivalent VAR_DECL, appropriately initialized.  */
1519   for (p = parms, a = first_call_expr_arg (exp, &iter); p;
1520        a = next_call_expr_arg (&iter), p = TREE_CHAIN (p))
1521     setup_one_parameter (id, p, a, fn, bb, &vars);
1522
1523   /* Initialize the static chain.  */
1524   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1525   gcc_assert (fn != current_function_decl);
1526   if (p)
1527     {
1528       /* No static chain?  Seems like a bug in tree-nested.c.  */
1529       gcc_assert (static_chain);
1530
1531       setup_one_parameter (id, p, static_chain, fn, bb, &vars);
1532     }
1533
1534   declare_inline_vars (id->block, vars);
1535 }
1536
1537 /* Declare a return variable to replace the RESULT_DECL for the
1538    function we are calling.  An appropriate DECL_STMT is returned.
1539    The USE_STMT is filled to contain a use of the declaration to
1540    indicate the return value of the function.
1541
1542    RETURN_SLOT, if non-null is place where to store the result.  It
1543    is set only for CALL_EXPR_RETURN_SLOT_OPT.  MODIFY_DEST, if non-null,
1544    was the LHS of the GIMPLE_MODIFY_STMT to which this call is the RHS.
1545
1546    The return value is a (possibly null) value that is the result of the
1547    function as seen by the callee.  *USE_P is a (possibly null) value that
1548    holds the result as seen by the caller.  */
1549
1550 static tree
1551 declare_return_variable (copy_body_data *id, tree return_slot, tree modify_dest,
1552                          tree *use_p)
1553 {
1554   tree callee = id->src_fn;
1555   tree caller = id->dst_fn;
1556   tree result = DECL_RESULT (callee);
1557   tree callee_type = TREE_TYPE (result);
1558   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
1559   tree var, use;
1560
1561   /* We don't need to do anything for functions that don't return
1562      anything.  */
1563   if (!result || VOID_TYPE_P (callee_type))
1564     {
1565       *use_p = NULL_TREE;
1566       return NULL_TREE;
1567     }
1568
1569   /* If there was a return slot, then the return value is the
1570      dereferenced address of that object.  */
1571   if (return_slot)
1572     {
1573       /* The front end shouldn't have used both return_slot and
1574          a modify expression.  */
1575       gcc_assert (!modify_dest);
1576       if (DECL_BY_REFERENCE (result))
1577         {
1578           tree return_slot_addr = build_fold_addr_expr (return_slot);
1579           STRIP_USELESS_TYPE_CONVERSION (return_slot_addr);
1580
1581           /* We are going to construct *&return_slot and we can't do that
1582              for variables believed to be not addressable.
1583
1584              FIXME: This check possibly can match, because values returned
1585              via return slot optimization are not believed to have address
1586              taken by alias analysis.  */
1587           gcc_assert (TREE_CODE (return_slot) != SSA_NAME);
1588           if (gimple_in_ssa_p (cfun))
1589             {
1590               HOST_WIDE_INT bitsize;
1591               HOST_WIDE_INT bitpos;
1592               tree offset;
1593               enum machine_mode mode;
1594               int unsignedp;
1595               int volatilep;
1596               tree base;
1597               base = get_inner_reference (return_slot, &bitsize, &bitpos,
1598                                           &offset,
1599                                           &mode, &unsignedp, &volatilep,
1600                                           false);
1601               if (TREE_CODE (base) == INDIRECT_REF)
1602                 base = TREE_OPERAND (base, 0);
1603               if (TREE_CODE (base) == SSA_NAME)
1604                 base = SSA_NAME_VAR (base);
1605               mark_sym_for_renaming (base);
1606             }
1607           var = return_slot_addr;
1608         }
1609       else
1610         {
1611           var = return_slot;
1612           gcc_assert (TREE_CODE (var) != SSA_NAME);
1613         }
1614       if ((TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1615            || TREE_CODE (TREE_TYPE (result)) == VECTOR_TYPE)
1616           && !DECL_GIMPLE_REG_P (result)
1617           && DECL_P (var))
1618         DECL_GIMPLE_REG_P (var) = 0;
1619       use = NULL;
1620       goto done;
1621     }
1622
1623   /* All types requiring non-trivial constructors should have been handled.  */
1624   gcc_assert (!TREE_ADDRESSABLE (callee_type));
1625
1626   /* Attempt to avoid creating a new temporary variable.  */
1627   if (modify_dest
1628       && TREE_CODE (modify_dest) != SSA_NAME)
1629     {
1630       bool use_it = false;
1631
1632       /* We can't use MODIFY_DEST if there's type promotion involved.  */
1633       if (!useless_type_conversion_p (callee_type, caller_type))
1634         use_it = false;
1635
1636       /* ??? If we're assigning to a variable sized type, then we must
1637          reuse the destination variable, because we've no good way to
1638          create variable sized temporaries at this point.  */
1639       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
1640         use_it = true;
1641
1642       /* If the callee cannot possibly modify MODIFY_DEST, then we can
1643          reuse it as the result of the call directly.  Don't do this if
1644          it would promote MODIFY_DEST to addressable.  */
1645       else if (TREE_ADDRESSABLE (result))
1646         use_it = false;
1647       else
1648         {
1649           tree base_m = get_base_address (modify_dest);
1650
1651           /* If the base isn't a decl, then it's a pointer, and we don't
1652              know where that's going to go.  */
1653           if (!DECL_P (base_m))
1654             use_it = false;
1655           else if (is_global_var (base_m))
1656             use_it = false;
1657           else if ((TREE_CODE (TREE_TYPE (result)) == COMPLEX_TYPE
1658                     || TREE_CODE (TREE_TYPE (result)) == VECTOR_TYPE)
1659                    && !DECL_GIMPLE_REG_P (result)
1660                    && DECL_GIMPLE_REG_P (base_m))
1661             use_it = false;
1662           else if (!TREE_ADDRESSABLE (base_m))
1663             use_it = true;
1664         }
1665
1666       if (use_it)
1667         {
1668           var = modify_dest;
1669           use = NULL;
1670           goto done;
1671         }
1672     }
1673
1674   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
1675
1676   var = copy_result_decl_to_var (result, id);
1677   if (gimple_in_ssa_p (cfun))
1678     {
1679       get_var_ann (var);
1680       add_referenced_var (var);
1681     }
1682
1683   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
1684   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
1685     = tree_cons (NULL_TREE, var,
1686                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
1687
1688   /* Do not have the rest of GCC warn about this variable as it should
1689      not be visible to the user.  */
1690   TREE_NO_WARNING (var) = 1;
1691
1692   declare_inline_vars (id->block, var);
1693
1694   /* Build the use expr.  If the return type of the function was
1695      promoted, convert it back to the expected type.  */
1696   use = var;
1697   if (!useless_type_conversion_p (caller_type, TREE_TYPE (var)))
1698     use = fold_convert (caller_type, var);
1699
1700   STRIP_USELESS_TYPE_CONVERSION (use);
1701
1702   if (DECL_BY_REFERENCE (result))
1703     var = build_fold_addr_expr (var);
1704
1705  done:
1706   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
1707      way, when the RESULT_DECL is encountered, it will be
1708      automatically replaced by the VAR_DECL.  */
1709   insert_decl_map (id, result, var);
1710
1711   /* Remember this so we can ignore it in remap_decls.  */
1712   id->retvar = var;
1713
1714   *use_p = use;
1715   return var;
1716 }
1717
1718 /* Returns nonzero if a function can be inlined as a tree.  */
1719
1720 bool
1721 tree_inlinable_function_p (tree fn)
1722 {
1723   return inlinable_function_p (fn);
1724 }
1725
1726 static const char *inline_forbidden_reason;
1727
1728 static tree
1729 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
1730                       void *fnp)
1731 {
1732   tree node = *nodep;
1733   tree fn = (tree) fnp;
1734   tree t;
1735
1736   switch (TREE_CODE (node))
1737     {
1738     case CALL_EXPR:
1739       /* Refuse to inline alloca call unless user explicitly forced so as
1740          this may change program's memory overhead drastically when the
1741          function using alloca is called in loop.  In GCC present in
1742          SPEC2000 inlining into schedule_block cause it to require 2GB of
1743          RAM instead of 256MB.  */
1744       if (alloca_call_p (node)
1745           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1746         {
1747           inline_forbidden_reason
1748             = G_("function %q+F can never be inlined because it uses "
1749                  "alloca (override using the always_inline attribute)");
1750           return node;
1751         }
1752       t = get_callee_fndecl (node);
1753       if (! t)
1754         break;
1755
1756       /* We cannot inline functions that call setjmp.  */
1757       if (setjmp_call_p (t))
1758         {
1759           inline_forbidden_reason
1760             = G_("function %q+F can never be inlined because it uses setjmp");
1761           return node;
1762         }
1763
1764       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
1765         switch (DECL_FUNCTION_CODE (t))
1766           {
1767             /* We cannot inline functions that take a variable number of
1768                arguments.  */
1769           case BUILT_IN_VA_START:
1770           case BUILT_IN_STDARG_START:
1771           case BUILT_IN_NEXT_ARG:
1772           case BUILT_IN_VA_END:
1773             inline_forbidden_reason
1774               = G_("function %q+F can never be inlined because it "
1775                    "uses variable argument lists");
1776             return node;
1777
1778           case BUILT_IN_LONGJMP:
1779             /* We can't inline functions that call __builtin_longjmp at
1780                all.  The non-local goto machinery really requires the
1781                destination be in a different function.  If we allow the
1782                function calling __builtin_longjmp to be inlined into the
1783                function calling __builtin_setjmp, Things will Go Awry.  */
1784             inline_forbidden_reason
1785               = G_("function %q+F can never be inlined because "
1786                    "it uses setjmp-longjmp exception handling");
1787             return node;
1788
1789           case BUILT_IN_NONLOCAL_GOTO:
1790             /* Similarly.  */
1791             inline_forbidden_reason
1792               = G_("function %q+F can never be inlined because "
1793                    "it uses non-local goto");
1794             return node;
1795
1796           case BUILT_IN_RETURN:
1797           case BUILT_IN_APPLY_ARGS:
1798             /* If a __builtin_apply_args caller would be inlined,
1799                it would be saving arguments of the function it has
1800                been inlined into.  Similarly __builtin_return would
1801                return from the function the inline has been inlined into.  */
1802             inline_forbidden_reason
1803               = G_("function %q+F can never be inlined because "
1804                    "it uses __builtin_return or __builtin_apply_args");
1805             return node;
1806
1807           default:
1808             break;
1809           }
1810       break;
1811
1812     case GOTO_EXPR:
1813       t = TREE_OPERAND (node, 0);
1814
1815       /* We will not inline a function which uses computed goto.  The
1816          addresses of its local labels, which may be tucked into
1817          global storage, are of course not constant across
1818          instantiations, which causes unexpected behavior.  */
1819       if (TREE_CODE (t) != LABEL_DECL)
1820         {
1821           inline_forbidden_reason
1822             = G_("function %q+F can never be inlined "
1823                  "because it contains a computed goto");
1824           return node;
1825         }
1826       break;
1827
1828     case LABEL_EXPR:
1829       t = TREE_OPERAND (node, 0);
1830       if (DECL_NONLOCAL (t))
1831         {
1832           /* We cannot inline a function that receives a non-local goto
1833              because we cannot remap the destination label used in the
1834              function that is performing the non-local goto.  */
1835           inline_forbidden_reason
1836             = G_("function %q+F can never be inlined "
1837                  "because it receives a non-local goto");
1838           return node;
1839         }
1840       break;
1841
1842     case RECORD_TYPE:
1843     case UNION_TYPE:
1844       /* We cannot inline a function of the form
1845
1846            void F (int i) { struct S { int ar[i]; } s; }
1847
1848          Attempting to do so produces a catch-22.
1849          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1850          UNION_TYPE nodes, then it goes into infinite recursion on a
1851          structure containing a pointer to its own type.  If it doesn't,
1852          then the type node for S doesn't get adjusted properly when
1853          F is inlined.
1854
1855          ??? This is likely no longer true, but it's too late in the 4.0
1856          cycle to try to find out.  This should be checked for 4.1.  */
1857       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1858         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1859           {
1860             inline_forbidden_reason
1861               = G_("function %q+F can never be inlined "
1862                    "because it uses variable sized variables");
1863             return node;
1864           }
1865
1866     default:
1867       break;
1868     }
1869
1870   return NULL_TREE;
1871 }
1872
1873 /* Return subexpression representing possible alloca call, if any.  */
1874 static tree
1875 inline_forbidden_p (tree fndecl)
1876 {
1877   location_t saved_loc = input_location;
1878   block_stmt_iterator bsi;
1879   basic_block bb;
1880   tree ret = NULL_TREE;
1881
1882   FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (fndecl))
1883     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1884       {
1885         ret = walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
1886                                     inline_forbidden_p_1, fndecl);
1887         if (ret)
1888           goto egress;
1889       }
1890
1891 egress:
1892   input_location = saved_loc;
1893   return ret;
1894 }
1895
1896 /* Returns nonzero if FN is a function that does not have any
1897    fundamental inline blocking properties.  */
1898
1899 static bool
1900 inlinable_function_p (tree fn)
1901 {
1902   bool inlinable = true;
1903   bool do_warning;
1904   tree always_inline;
1905
1906   /* If we've already decided this function shouldn't be inlined,
1907      there's no need to check again.  */
1908   if (DECL_UNINLINABLE (fn))
1909     return false;
1910
1911   /* We only warn for functions declared `inline' by the user.  */
1912   do_warning = (warn_inline
1913                 && DECL_INLINE (fn)
1914                 && DECL_DECLARED_INLINE_P (fn)
1915                 && !DECL_IN_SYSTEM_HEADER (fn));
1916
1917   always_inline = lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn));
1918
1919   if (flag_really_no_inline
1920       && always_inline == NULL)
1921     {
1922       if (do_warning)
1923         warning (OPT_Winline, "function %q+F can never be inlined because it "
1924                  "is suppressed using -fno-inline", fn);
1925       inlinable = false;
1926     }
1927
1928   /* Don't auto-inline anything that might not be bound within
1929      this unit of translation.  */
1930   else if (!DECL_DECLARED_INLINE_P (fn)
1931            && DECL_REPLACEABLE_P (fn))
1932     inlinable = false;
1933
1934   else if (!function_attribute_inlinable_p (fn))
1935     {
1936       if (do_warning)
1937         warning (OPT_Winline, "function %q+F can never be inlined because it "
1938                  "uses attributes conflicting with inlining", fn);
1939       inlinable = false;
1940     }
1941
1942   /* If we don't have the function body available, we can't inline it.
1943      However, this should not be recorded since we also get here for
1944      forward declared inline functions.  Therefore, return at once.  */
1945   if (!DECL_SAVED_TREE (fn))
1946     return false;
1947
1948   /* If we're not inlining at all, then we cannot inline this function.  */
1949   else if (!flag_inline_trees)
1950     inlinable = false;
1951
1952   /* Only try to inline functions if DECL_INLINE is set.  This should be
1953      true for all functions declared `inline', and for all other functions
1954      as well with -finline-functions.
1955
1956      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1957      it's the front-end that must set DECL_INLINE in this case, because
1958      dwarf2out loses if a function that does not have DECL_INLINE set is
1959      inlined anyway.  That is why we have both DECL_INLINE and
1960      DECL_DECLARED_INLINE_P.  */
1961   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1962             here should be redundant.  */
1963   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1964     inlinable = false;
1965
1966   else if (inline_forbidden_p (fn))
1967     {
1968       /* See if we should warn about uninlinable functions.  Previously,
1969          some of these warnings would be issued while trying to expand
1970          the function inline, but that would cause multiple warnings
1971          about functions that would for example call alloca.  But since
1972          this a property of the function, just one warning is enough.
1973          As a bonus we can now give more details about the reason why a
1974          function is not inlinable.  */
1975       if (always_inline)
1976         sorry (inline_forbidden_reason, fn);
1977       else if (do_warning)
1978         warning (OPT_Winline, inline_forbidden_reason, fn);
1979
1980       inlinable = false;
1981     }
1982
1983   /* Squirrel away the result so that we don't have to check again.  */
1984   DECL_UNINLINABLE (fn) = !inlinable;
1985
1986   return inlinable;
1987 }
1988
1989 /* Estimate the cost of a memory move.  Use machine dependent
1990    word size and take possible memcpy call into account.  */
1991
1992 int
1993 estimate_move_cost (tree type)
1994 {
1995   HOST_WIDE_INT size;
1996
1997   size = int_size_in_bytes (type);
1998
1999   if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
2000     /* Cost of a memcpy call, 3 arguments and the call.  */
2001     return 4;
2002   else
2003     return ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
2004 }
2005
2006 /* Arguments for estimate_num_insns_1.  */
2007
2008 struct eni_data
2009 {
2010   /* Used to return the number of insns.  */
2011   int count;
2012
2013   /* Weights of various constructs.  */
2014   eni_weights *weights;
2015 };
2016
2017 /* Used by estimate_num_insns.  Estimate number of instructions seen
2018    by given statement.  */
2019
2020 static tree
2021 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
2022 {
2023   struct eni_data *d = data;
2024   tree x = *tp;
2025   unsigned cost;
2026
2027   if (IS_TYPE_OR_DECL_P (x))
2028     {
2029       *walk_subtrees = 0;
2030       return NULL;
2031     }
2032   /* Assume that constants and references counts nothing.  These should
2033      be majorized by amount of operations among them we count later
2034      and are common target of CSE and similar optimizations.  */
2035   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
2036     return NULL;
2037
2038   switch (TREE_CODE (x))
2039     {
2040     /* Containers have no cost.  */
2041     case TREE_LIST:
2042     case TREE_VEC:
2043     case BLOCK:
2044     case COMPONENT_REF:
2045     case BIT_FIELD_REF:
2046     case INDIRECT_REF:
2047     case ALIGN_INDIRECT_REF:
2048     case MISALIGNED_INDIRECT_REF:
2049     case ARRAY_REF:
2050     case ARRAY_RANGE_REF:
2051     case OBJ_TYPE_REF:
2052     case EXC_PTR_EXPR: /* ??? */
2053     case FILTER_EXPR: /* ??? */
2054     case COMPOUND_EXPR:
2055     case BIND_EXPR:
2056     case WITH_CLEANUP_EXPR:
2057     case NOP_EXPR:
2058     case CONVERT_EXPR:
2059     case VIEW_CONVERT_EXPR:
2060     case SAVE_EXPR:
2061     case ADDR_EXPR:
2062     case COMPLEX_EXPR:
2063     case RANGE_EXPR:
2064     case CASE_LABEL_EXPR:
2065     case SSA_NAME:
2066     case CATCH_EXPR:
2067     case EH_FILTER_EXPR:
2068     case STATEMENT_LIST:
2069     case ERROR_MARK:
2070     case NON_LVALUE_EXPR:
2071     case FDESC_EXPR:
2072     case VA_ARG_EXPR:
2073     case TRY_CATCH_EXPR:
2074     case TRY_FINALLY_EXPR:
2075     case LABEL_EXPR:
2076     case GOTO_EXPR:
2077     case RETURN_EXPR:
2078     case EXIT_EXPR:
2079     case LOOP_EXPR:
2080     case PHI_NODE:
2081     case WITH_SIZE_EXPR:
2082     case OMP_CLAUSE:
2083     case OMP_RETURN:
2084     case OMP_CONTINUE:
2085     case OMP_SECTIONS_SWITCH:
2086       break;
2087
2088     /* We don't account constants for now.  Assume that the cost is amortized
2089        by operations that do use them.  We may re-consider this decision once
2090        we are able to optimize the tree before estimating its size and break
2091        out static initializers.  */
2092     case IDENTIFIER_NODE:
2093     case INTEGER_CST:
2094     case REAL_CST:
2095     case FIXED_CST:
2096     case COMPLEX_CST:
2097     case VECTOR_CST:
2098     case STRING_CST:
2099       *walk_subtrees = 0;
2100       return NULL;
2101
2102       /* CHANGE_DYNAMIC_TYPE_EXPR explicitly expands to nothing.  */
2103     case CHANGE_DYNAMIC_TYPE_EXPR:
2104       *walk_subtrees = 0;
2105       return NULL;
2106
2107     /* Try to estimate the cost of assignments.  We have three cases to
2108        deal with:
2109         1) Simple assignments to registers;
2110         2) Stores to things that must live in memory.  This includes
2111            "normal" stores to scalars, but also assignments of large
2112            structures, or constructors of big arrays;
2113         3) TARGET_EXPRs.
2114
2115        Let us look at the first two cases, assuming we have "a = b + C":
2116        <GIMPLE_MODIFY_STMT <var_decl "a">
2117                            <plus_expr <var_decl "b"> <constant C>>
2118        If "a" is a GIMPLE register, the assignment to it is free on almost
2119        any target, because "a" usually ends up in a real register.  Hence
2120        the only cost of this expression comes from the PLUS_EXPR, and we
2121        can ignore the GIMPLE_MODIFY_STMT.
2122        If "a" is not a GIMPLE register, the assignment to "a" will most
2123        likely be a real store, so the cost of the GIMPLE_MODIFY_STMT is the cost
2124        of moving something into "a", which we compute using the function
2125        estimate_move_cost.
2126
2127        The third case deals with TARGET_EXPRs, for which the semantics are
2128        that a temporary is assigned, unless the TARGET_EXPR itself is being
2129        assigned to something else.  In the latter case we do not need the
2130        temporary.  E.g. in:
2131                 <GIMPLE_MODIFY_STMT <var_decl "a"> <target_expr>>, the
2132        GIMPLE_MODIFY_STMT is free.  */
2133     case INIT_EXPR:
2134     case GIMPLE_MODIFY_STMT:
2135       /* Is the right and side a TARGET_EXPR?  */
2136       if (TREE_CODE (GENERIC_TREE_OPERAND (x, 1)) == TARGET_EXPR)
2137         break;
2138       /* ... fall through ...  */
2139
2140     case TARGET_EXPR:
2141       x = GENERIC_TREE_OPERAND (x, 0);
2142       /* Is this an assignments to a register?  */
2143       if (is_gimple_reg (x))
2144         break;
2145       /* Otherwise it's a store, so fall through to compute the move cost.  */
2146
2147     case CONSTRUCTOR:
2148       d->count += estimate_move_cost (TREE_TYPE (x));
2149       break;
2150
2151     /* Assign cost of 1 to usual operations.
2152        ??? We may consider mapping RTL costs to this.  */
2153     case COND_EXPR:
2154     case VEC_COND_EXPR:
2155
2156     case PLUS_EXPR:
2157     case POINTER_PLUS_EXPR:
2158     case MINUS_EXPR:
2159     case MULT_EXPR:
2160
2161     case FIXED_CONVERT_EXPR:
2162     case FIX_TRUNC_EXPR:
2163
2164     case NEGATE_EXPR:
2165     case FLOAT_EXPR:
2166     case MIN_EXPR:
2167     case MAX_EXPR:
2168     case ABS_EXPR:
2169
2170     case LSHIFT_EXPR:
2171     case RSHIFT_EXPR:
2172     case LROTATE_EXPR:
2173     case RROTATE_EXPR:
2174     case VEC_LSHIFT_EXPR:
2175     case VEC_RSHIFT_EXPR:
2176
2177     case BIT_IOR_EXPR:
2178     case BIT_XOR_EXPR:
2179     case BIT_AND_EXPR:
2180     case BIT_NOT_EXPR:
2181
2182     case TRUTH_ANDIF_EXPR:
2183     case TRUTH_ORIF_EXPR:
2184     case TRUTH_AND_EXPR:
2185     case TRUTH_OR_EXPR:
2186     case TRUTH_XOR_EXPR:
2187     case TRUTH_NOT_EXPR:
2188
2189     case LT_EXPR:
2190     case LE_EXPR:
2191     case GT_EXPR:
2192     case GE_EXPR:
2193     case EQ_EXPR:
2194     case NE_EXPR:
2195     case ORDERED_EXPR:
2196     case UNORDERED_EXPR:
2197
2198     case UNLT_EXPR:
2199     case UNLE_EXPR:
2200     case UNGT_EXPR:
2201     case UNGE_EXPR:
2202     case UNEQ_EXPR:
2203     case LTGT_EXPR:
2204
2205     case CONJ_EXPR:
2206
2207     case PREDECREMENT_EXPR:
2208     case PREINCREMENT_EXPR:
2209     case POSTDECREMENT_EXPR:
2210     case POSTINCREMENT_EXPR:
2211
2212     case ASM_EXPR:
2213
2214     case REALIGN_LOAD_EXPR:
2215
2216     case REDUC_MAX_EXPR:
2217     case REDUC_MIN_EXPR:
2218     case REDUC_PLUS_EXPR:
2219     case WIDEN_SUM_EXPR:
2220     case DOT_PROD_EXPR:
2221     case VEC_WIDEN_MULT_HI_EXPR:
2222     case VEC_WIDEN_MULT_LO_EXPR:
2223     case VEC_UNPACK_HI_EXPR:
2224     case VEC_UNPACK_LO_EXPR:
2225     case VEC_UNPACK_FLOAT_HI_EXPR:
2226     case VEC_UNPACK_FLOAT_LO_EXPR:
2227     case VEC_PACK_TRUNC_EXPR:
2228     case VEC_PACK_SAT_EXPR:
2229     case VEC_PACK_FIX_TRUNC_EXPR:
2230
2231     case WIDEN_MULT_EXPR:
2232
2233     case VEC_EXTRACT_EVEN_EXPR:
2234     case VEC_EXTRACT_ODD_EXPR:
2235     case VEC_INTERLEAVE_HIGH_EXPR:
2236     case VEC_INTERLEAVE_LOW_EXPR:
2237
2238     case RESX_EXPR:
2239       d->count += 1;
2240       break;
2241
2242     case SWITCH_EXPR:
2243       /* TODO: Cost of a switch should be derived from the number of
2244          branches.  */
2245       d->count += d->weights->switch_cost;
2246       break;
2247
2248     /* Few special cases of expensive operations.  This is useful
2249        to avoid inlining on functions having too many of these.  */
2250     case TRUNC_DIV_EXPR:
2251     case CEIL_DIV_EXPR:
2252     case FLOOR_DIV_EXPR:
2253     case ROUND_DIV_EXPR:
2254     case EXACT_DIV_EXPR:
2255     case TRUNC_MOD_EXPR:
2256     case CEIL_MOD_EXPR:
2257     case FLOOR_MOD_EXPR:
2258     case ROUND_MOD_EXPR:
2259     case RDIV_EXPR:
2260       d->count += d->weights->div_mod_cost;
2261       break;
2262     case CALL_EXPR:
2263       {
2264         tree decl = get_callee_fndecl (x);
2265
2266         cost = d->weights->call_cost;
2267         if (decl && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2268           switch (DECL_FUNCTION_CODE (decl))
2269             {
2270             case BUILT_IN_CONSTANT_P:
2271               *walk_subtrees = 0;
2272               return NULL_TREE;
2273             case BUILT_IN_EXPECT:
2274               return NULL_TREE;
2275             /* Prefetch instruction is not expensive.  */
2276             case BUILT_IN_PREFETCH:
2277               cost = 1;
2278               break;
2279             default:
2280               break;
2281             }
2282
2283         /* Our cost must be kept in sync with cgraph_estimate_size_after_inlining
2284            that does use function declaration to figure out the arguments.  */
2285         if (!decl)
2286           {
2287             tree a;
2288             call_expr_arg_iterator iter;
2289             FOR_EACH_CALL_EXPR_ARG (a, iter, x)
2290               d->count += estimate_move_cost (TREE_TYPE (a));
2291           }
2292         else
2293           {
2294             tree arg;
2295             for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
2296               d->count += estimate_move_cost (TREE_TYPE (arg));
2297           }
2298
2299         d->count += cost;
2300         break;
2301       }
2302
2303     case OMP_PARALLEL:
2304     case OMP_FOR:
2305     case OMP_SECTIONS:
2306     case OMP_SINGLE:
2307     case OMP_SECTION:
2308     case OMP_MASTER:
2309     case OMP_ORDERED:
2310     case OMP_CRITICAL:
2311     case OMP_ATOMIC:
2312       /* OpenMP directives are generally very expensive.  */
2313       d->count += d->weights->omp_cost;
2314       break;
2315
2316     default:
2317       gcc_unreachable ();
2318     }
2319   return NULL;
2320 }
2321
2322 /* Estimate number of instructions that will be created by expanding EXPR.
2323    WEIGHTS contains weights attributed to various constructs.  */
2324
2325 int
2326 estimate_num_insns (tree expr, eni_weights *weights)
2327 {
2328   struct pointer_set_t *visited_nodes;
2329   basic_block bb;
2330   block_stmt_iterator bsi;
2331   struct function *my_function;
2332   struct eni_data data;
2333
2334   data.count = 0;
2335   data.weights = weights;
2336
2337   /* If we're given an entire function, walk the CFG.  */
2338   if (TREE_CODE (expr) == FUNCTION_DECL)
2339     {
2340       my_function = DECL_STRUCT_FUNCTION (expr);
2341       gcc_assert (my_function && my_function->cfg);
2342       visited_nodes = pointer_set_create ();
2343       FOR_EACH_BB_FN (bb, my_function)
2344         {
2345           for (bsi = bsi_start (bb);
2346                !bsi_end_p (bsi);
2347                bsi_next (&bsi))
2348             {
2349               walk_tree (bsi_stmt_ptr (bsi), estimate_num_insns_1,
2350                          &data, visited_nodes);
2351             }
2352         }
2353       pointer_set_destroy (visited_nodes);
2354     }
2355   else
2356     walk_tree_without_duplicates (&expr, estimate_num_insns_1, &data);
2357
2358   return data.count;
2359 }
2360
2361 /* Initializes weights used by estimate_num_insns.  */
2362
2363 void
2364 init_inline_once (void)
2365 {
2366   eni_inlining_weights.call_cost = PARAM_VALUE (PARAM_INLINE_CALL_COST);
2367   eni_inlining_weights.div_mod_cost = 10;
2368   eni_inlining_weights.switch_cost = 1;
2369   eni_inlining_weights.omp_cost = 40;
2370
2371   eni_size_weights.call_cost = 1;
2372   eni_size_weights.div_mod_cost = 1;
2373   eni_size_weights.switch_cost = 10;
2374   eni_size_weights.omp_cost = 40;
2375
2376   /* Estimating time for call is difficult, since we have no idea what the
2377      called function does.  In the current uses of eni_time_weights,
2378      underestimating the cost does less harm than overestimating it, so
2379      we choose a rather small value here.  */
2380   eni_time_weights.call_cost = 10;
2381   eni_time_weights.div_mod_cost = 10;
2382   eni_time_weights.switch_cost = 4;
2383   eni_time_weights.omp_cost = 40;
2384 }
2385
2386 /* Install new lexical TREE_BLOCK underneath 'current_block'.  */
2387 static void
2388 add_lexical_block (tree current_block, tree new_block)
2389 {
2390   tree *blk_p;
2391
2392   /* Walk to the last sub-block.  */
2393   for (blk_p = &BLOCK_SUBBLOCKS (current_block);
2394        *blk_p;
2395        blk_p = &TREE_CHAIN (*blk_p))
2396     ;
2397   *blk_p = new_block;
2398   BLOCK_SUPERCONTEXT (new_block) = current_block;
2399 }
2400
2401 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
2402
2403 static bool
2404 expand_call_inline (basic_block bb, tree stmt, tree *tp, void *data)
2405 {
2406   copy_body_data *id;
2407   tree t;
2408   tree use_retvar;
2409   tree fn;
2410   struct pointer_map_t *st;
2411   tree return_slot;
2412   tree modify_dest;
2413   location_t saved_location;
2414   struct cgraph_edge *cg_edge;
2415   const char *reason;
2416   basic_block return_block;
2417   edge e;
2418   block_stmt_iterator bsi, stmt_bsi;
2419   bool successfully_inlined = FALSE;
2420   bool purge_dead_abnormal_edges;
2421   tree t_step;
2422   tree var;
2423
2424   /* See what we've got.  */
2425   id = (copy_body_data *) data;
2426   t = *tp;
2427
2428   /* Set input_location here so we get the right instantiation context
2429      if we call instantiate_decl from inlinable_function_p.  */
2430   saved_location = input_location;
2431   if (EXPR_HAS_LOCATION (t))
2432     input_location = EXPR_LOCATION (t);
2433
2434   /* From here on, we're only interested in CALL_EXPRs.  */
2435   if (TREE_CODE (t) != CALL_EXPR)
2436     goto egress;
2437
2438   /* First, see if we can figure out what function is being called.
2439      If we cannot, then there is no hope of inlining the function.  */
2440   fn = get_callee_fndecl (t);
2441   if (!fn)
2442     goto egress;
2443
2444   /* Turn forward declarations into real ones.  */
2445   fn = cgraph_node (fn)->decl;
2446
2447   /* If fn is a declaration of a function in a nested scope that was
2448      globally declared inline, we don't set its DECL_INITIAL.
2449      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
2450      C++ front-end uses it for cdtors to refer to their internal
2451      declarations, that are not real functions.  Fortunately those
2452      don't have trees to be saved, so we can tell by checking their
2453      DECL_SAVED_TREE.  */
2454   if (! DECL_INITIAL (fn)
2455       && DECL_ABSTRACT_ORIGIN (fn)
2456       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
2457     fn = DECL_ABSTRACT_ORIGIN (fn);
2458
2459   /* Objective C and fortran still calls tree_rest_of_compilation directly.
2460      Kill this check once this is fixed.  */
2461   if (!id->dst_node->analyzed)
2462     goto egress;
2463
2464   cg_edge = cgraph_edge (id->dst_node, stmt);
2465
2466   /* Constant propagation on argument done during previous inlining
2467      may create new direct call.  Produce an edge for it.  */
2468   if (!cg_edge)
2469     {
2470       struct cgraph_node *dest = cgraph_node (fn);
2471
2472       /* We have missing edge in the callgraph.  This can happen in one case
2473          where previous inlining turned indirect call into direct call by
2474          constant propagating arguments.  In all other cases we hit a bug
2475          (incorrect node sharing is most common reason for missing edges.  */
2476       gcc_assert (dest->needed || !flag_unit_at_a_time);
2477       cgraph_create_edge (id->dst_node, dest, stmt,
2478                           bb->count, CGRAPH_FREQ_BASE,
2479                           bb->loop_depth)->inline_failed
2480         = N_("originally indirect function call not considered for inlining");
2481       if (dump_file)
2482         {
2483            fprintf (dump_file, "Created new direct edge to %s",
2484                     cgraph_node_name (dest));
2485         }
2486       goto egress;
2487     }
2488
2489   /* Don't try to inline functions that are not well-suited to
2490      inlining.  */
2491   if (!cgraph_inline_p (cg_edge, &reason))
2492     {
2493       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
2494           /* Avoid warnings during early inline pass. */
2495           && (!flag_unit_at_a_time || cgraph_global_info_ready))
2496         {
2497           sorry ("inlining failed in call to %q+F: %s", fn, reason);
2498           sorry ("called from here");
2499         }
2500       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
2501                && !DECL_IN_SYSTEM_HEADER (fn)
2502                && strlen (reason)
2503                && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn))
2504                /* Avoid warnings during early inline pass. */
2505                && (!flag_unit_at_a_time || cgraph_global_info_ready))
2506         {
2507           warning (OPT_Winline, "inlining failed in call to %q+F: %s",
2508                    fn, reason);
2509           warning (OPT_Winline, "called from here");
2510         }
2511       goto egress;
2512     }
2513   fn = cg_edge->callee->decl;
2514
2515 #ifdef ENABLE_CHECKING
2516   if (cg_edge->callee->decl != id->dst_node->decl)
2517     verify_cgraph_node (cg_edge->callee);
2518 #endif
2519
2520   /* We will be inlining this callee.  */
2521   id->eh_region = lookup_stmt_eh_region (stmt);
2522
2523   /* Split the block holding the CALL_EXPR.  */
2524   e = split_block (bb, stmt);
2525   bb = e->src;
2526   return_block = e->dest;
2527   remove_edge (e);
2528
2529   /* split_block splits after the statement; work around this by
2530      moving the call into the second block manually.  Not pretty,
2531      but seems easier than doing the CFG manipulation by hand
2532      when the CALL_EXPR is in the last statement of BB.  */
2533   stmt_bsi = bsi_last (bb);
2534   bsi_remove (&stmt_bsi, false);
2535
2536   /* If the CALL_EXPR was in the last statement of BB, it may have
2537      been the source of abnormal edges.  In this case, schedule
2538      the removal of dead abnormal edges.  */
2539   bsi = bsi_start (return_block);
2540   if (bsi_end_p (bsi))
2541     {
2542       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2543       purge_dead_abnormal_edges = true;
2544     }
2545   else
2546     {
2547       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2548       purge_dead_abnormal_edges = false;
2549     }
2550
2551   stmt_bsi = bsi_start (return_block);
2552
2553   /* Build a block containing code to initialize the arguments, the
2554      actual inline expansion of the body, and a label for the return
2555      statements within the function to jump to.  The type of the
2556      statement expression is the return type of the function call.  */
2557   id->block = make_node (BLOCK);
2558   BLOCK_ABSTRACT_ORIGIN (id->block) = fn;
2559   BLOCK_SOURCE_LOCATION (id->block) = input_location;
2560   add_lexical_block (TREE_BLOCK (stmt), id->block);
2561
2562   /* Local declarations will be replaced by their equivalents in this
2563      map.  */
2564   st = id->decl_map;
2565   id->decl_map = pointer_map_create ();
2566
2567   /* Record the function we are about to inline.  */
2568   id->src_fn = fn;
2569   id->src_node = cg_edge->callee;
2570   id->src_cfun = DECL_STRUCT_FUNCTION (fn);
2571   id->call_expr = t;
2572
2573   initialize_inlined_parameters (id, t, fn, bb);
2574
2575   if (DECL_INITIAL (fn))
2576     add_lexical_block (id->block, remap_blocks (DECL_INITIAL (fn), id));
2577
2578   /* Return statements in the function body will be replaced by jumps
2579      to the RET_LABEL.  */
2580
2581   gcc_assert (DECL_INITIAL (fn));
2582   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
2583
2584   /* Find the lhs to which the result of this call is assigned.  */
2585   return_slot = NULL;
2586   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2587     {
2588       modify_dest = GIMPLE_STMT_OPERAND (stmt, 0);
2589
2590       /* The function which we are inlining might not return a value,
2591          in which case we should issue a warning that the function
2592          does not return a value.  In that case the optimizers will
2593          see that the variable to which the value is assigned was not
2594          initialized.  We do not want to issue a warning about that
2595          uninitialized variable.  */
2596       if (DECL_P (modify_dest))
2597         TREE_NO_WARNING (modify_dest) = 1;
2598       if (CALL_EXPR_RETURN_SLOT_OPT (t))
2599         {
2600           return_slot = modify_dest;
2601           modify_dest = NULL;
2602         }
2603     }
2604   else
2605     modify_dest = NULL;
2606
2607   /* Declare the return variable for the function.  */
2608   declare_return_variable (id, return_slot,
2609                            modify_dest, &use_retvar);
2610
2611   /* This is it.  Duplicate the callee body.  Assume callee is
2612      pre-gimplified.  Note that we must not alter the caller
2613      function in any way before this point, as this CALL_EXPR may be
2614      a self-referential call; if we're calling ourselves, we need to
2615      duplicate our body before altering anything.  */
2616   copy_body (id, bb->count, bb->frequency, bb, return_block);
2617
2618   /* Add local vars in this inlined callee to caller.  */
2619   t_step = id->src_cfun->unexpanded_var_list;
2620   for (; t_step; t_step = TREE_CHAIN (t_step))
2621     {
2622       var = TREE_VALUE (t_step);
2623       if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
2624         cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
2625                                                cfun->unexpanded_var_list);
2626       else
2627         cfun->unexpanded_var_list = tree_cons (NULL_TREE, remap_decl (var, id),
2628                                                cfun->unexpanded_var_list);
2629     }
2630
2631   /* Clean up.  */
2632   pointer_map_destroy (id->decl_map);
2633   id->decl_map = st;
2634
2635   /* If the inlined function returns a result that we care about,
2636      clobber the CALL_EXPR with a reference to the return variable.  */
2637   if (use_retvar && (TREE_CODE (bsi_stmt (stmt_bsi)) != CALL_EXPR))
2638     {
2639       *tp = use_retvar;
2640       if (gimple_in_ssa_p (cfun))
2641         {
2642           update_stmt (stmt);
2643           mark_symbols_for_renaming (stmt);
2644         }
2645       maybe_clean_or_replace_eh_stmt (stmt, stmt);
2646     }
2647   else
2648     /* We're modifying a TSI owned by gimple_expand_calls_inline();
2649        tsi_delink() will leave the iterator in a sane state.  */
2650     {
2651       /* Handle case of inlining function that miss return statement so
2652          return value becomes undefined.  */
2653       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
2654           && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME)
2655         {
2656           tree name = TREE_OPERAND (stmt, 0);
2657           tree var = SSA_NAME_VAR (TREE_OPERAND (stmt, 0));
2658           tree def = gimple_default_def (cfun, var);
2659
2660           /* If the variable is used undefined, make this name undefined via
2661              move.  */
2662           if (def)
2663             {
2664               TREE_OPERAND (stmt, 1) = def;
2665               update_stmt (stmt);
2666             }
2667           /* Otherwise make this variable undefined.  */
2668           else
2669             {
2670               bsi_remove (&stmt_bsi, true);
2671               set_default_def (var, name);
2672               SSA_NAME_DEF_STMT (name) = build_empty_stmt ();
2673             }
2674         }
2675       else
2676         bsi_remove (&stmt_bsi, true);
2677     }
2678
2679   if (purge_dead_abnormal_edges)
2680     tree_purge_dead_abnormal_call_edges (return_block);
2681
2682   /* If the value of the new expression is ignored, that's OK.  We
2683      don't warn about this for CALL_EXPRs, so we shouldn't warn about
2684      the equivalent inlined version either.  */
2685   TREE_USED (*tp) = 1;
2686
2687   /* Output the inlining info for this abstract function, since it has been
2688      inlined.  If we don't do this now, we can lose the information about the
2689      variables in the function when the blocks get blown away as soon as we
2690      remove the cgraph node.  */
2691   (*debug_hooks->outlining_inline_function) (cg_edge->callee->decl);
2692
2693   /* Update callgraph if needed.  */
2694   cgraph_remove_node (cg_edge->callee);
2695
2696   id->block = NULL_TREE;
2697   successfully_inlined = TRUE;
2698
2699  egress:
2700   input_location = saved_location;
2701   return successfully_inlined;
2702 }
2703
2704 /* Expand call statements reachable from STMT_P.
2705    We can only have CALL_EXPRs as the "toplevel" tree code or nested
2706    in a GIMPLE_MODIFY_STMT.  See tree-gimple.c:get_call_expr_in().  We can
2707    unfortunately not use that function here because we need a pointer
2708    to the CALL_EXPR, not the tree itself.  */
2709
2710 static bool
2711 gimple_expand_calls_inline (basic_block bb, copy_body_data *id)
2712 {
2713   block_stmt_iterator bsi;
2714
2715   /* Register specific tree functions.  */
2716   tree_register_cfg_hooks ();
2717   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2718     {
2719       tree *expr_p = bsi_stmt_ptr (bsi);
2720       tree stmt = *expr_p;
2721
2722       if (TREE_CODE (*expr_p) == GIMPLE_MODIFY_STMT)
2723         expr_p = &GIMPLE_STMT_OPERAND (*expr_p, 1);
2724       if (TREE_CODE (*expr_p) == WITH_SIZE_EXPR)
2725         expr_p = &TREE_OPERAND (*expr_p, 0);
2726       if (TREE_CODE (*expr_p) == CALL_EXPR)
2727         if (expand_call_inline (bb, stmt, expr_p, id))
2728           return true;
2729     }
2730   return false;
2731 }
2732
2733 /* Walk all basic blocks created after FIRST and try to fold every statement
2734    in the STATEMENTS pointer set.  */
2735 static void
2736 fold_marked_statements (int first, struct pointer_set_t *statements)
2737 {
2738   for (;first < n_basic_blocks;first++)
2739     if (BASIC_BLOCK (first))
2740       {
2741         block_stmt_iterator bsi;
2742         for (bsi = bsi_start (BASIC_BLOCK (first));
2743              !bsi_end_p (bsi); bsi_next (&bsi))
2744           if (pointer_set_contains (statements, bsi_stmt (bsi)))
2745             {
2746               tree old_stmt = bsi_stmt (bsi);
2747               if (fold_stmt (bsi_stmt_ptr (bsi)))
2748                 {
2749                   update_stmt (bsi_stmt (bsi));
2750                   if (maybe_clean_or_replace_eh_stmt (old_stmt, bsi_stmt (bsi)))
2751                      tree_purge_dead_eh_edges (BASIC_BLOCK (first));
2752                 }
2753             }
2754       }
2755 }
2756
2757 /* Return true if BB has at least one abnormal outgoing edge.  */
2758
2759 static inline bool
2760 has_abnormal_outgoing_edge_p (basic_block bb)
2761 {
2762   edge e;
2763   edge_iterator ei;
2764
2765   FOR_EACH_EDGE (e, ei, bb->succs)
2766     if (e->flags & EDGE_ABNORMAL)
2767       return true;
2768
2769   return false;
2770 }
2771
2772 /* When a block from the inlined function contains a call with side-effects
2773    in the middle gets inlined in a function with non-locals labels, the call
2774    becomes a potential non-local goto so we need to add appropriate edge.  */
2775
2776 static void
2777 make_nonlocal_label_edges (void)
2778 {
2779   block_stmt_iterator bsi;
2780   basic_block bb;
2781
2782   FOR_EACH_BB (bb)
2783     {
2784       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2785         {
2786           tree stmt = bsi_stmt (bsi);
2787           if (tree_can_make_abnormal_goto (stmt))
2788             {
2789               if (stmt == bsi_stmt (bsi_last (bb)))
2790                 {
2791                   if (!has_abnormal_outgoing_edge_p (bb))
2792                     make_abnormal_goto_edges (bb, true);
2793                 }
2794               else
2795                 {
2796                   edge e = split_block (bb, stmt);
2797                   bb = e->src;
2798                   make_abnormal_goto_edges (bb, true);
2799                 }
2800               break;
2801             }
2802
2803           /* Update PHIs on nonlocal goto receivers we (possibly)
2804              just created new edges into.  */
2805           if (TREE_CODE (stmt) == LABEL_EXPR
2806               && gimple_in_ssa_p (cfun))
2807             {
2808               tree target = LABEL_EXPR_LABEL (stmt);
2809               if (DECL_NONLOCAL (target))
2810                 {
2811                   tree phi;
2812
2813                   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2814                     {
2815                       gcc_assert (SSA_NAME_OCCURS_IN_ABNORMAL_PHI
2816                                   (PHI_RESULT (phi)));
2817                       mark_sym_for_renaming
2818                         (SSA_NAME_VAR (PHI_RESULT (phi)));
2819                     }
2820                 }
2821             }
2822         }
2823     }
2824 }
2825
2826 /* Expand calls to inline functions in the body of FN.  */
2827
2828 unsigned int
2829 optimize_inline_calls (tree fn)
2830 {
2831   copy_body_data id;
2832   tree prev_fn;
2833   basic_block bb;
2834   int last = n_basic_blocks;
2835   /* There is no point in performing inlining if errors have already
2836      occurred -- and we might crash if we try to inline invalid
2837      code.  */
2838   if (errorcount || sorrycount)
2839     return 0;
2840
2841   /* Clear out ID.  */
2842   memset (&id, 0, sizeof (id));
2843
2844   id.src_node = id.dst_node = cgraph_node (fn);
2845   id.dst_fn = fn;
2846   /* Or any functions that aren't finished yet.  */
2847   prev_fn = NULL_TREE;
2848   if (current_function_decl)
2849     {
2850       id.dst_fn = current_function_decl;
2851       prev_fn = current_function_decl;
2852     }
2853
2854   id.copy_decl = copy_decl_maybe_to_var;
2855   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2856   id.transform_new_cfg = false;
2857   id.transform_return_to_modify = true;
2858   id.transform_lang_insert_block = false;
2859   id.statements_to_fold = pointer_set_create ();
2860
2861   push_gimplify_context ();
2862
2863   /* We make no attempts to keep dominance info up-to-date.  */
2864   free_dominance_info (CDI_DOMINATORS);
2865   free_dominance_info (CDI_POST_DOMINATORS);
2866
2867   /* Reach the trees by walking over the CFG, and note the
2868      enclosing basic-blocks in the call edges.  */
2869   /* We walk the blocks going forward, because inlined function bodies
2870      will split id->current_basic_block, and the new blocks will
2871      follow it; we'll trudge through them, processing their CALL_EXPRs
2872      along the way.  */
2873   FOR_EACH_BB (bb)
2874     gimple_expand_calls_inline (bb, &id);
2875
2876   pop_gimplify_context (NULL);
2877
2878 #ifdef ENABLE_CHECKING
2879     {
2880       struct cgraph_edge *e;
2881
2882       verify_cgraph_node (id.dst_node);
2883
2884       /* Double check that we inlined everything we are supposed to inline.  */
2885       for (e = id.dst_node->callees; e; e = e->next_callee)
2886         gcc_assert (e->inline_failed);
2887     }
2888 #endif
2889
2890   /* Fold the statements before compacting/renumbering the basic blocks.  */
2891   fold_marked_statements (last, id.statements_to_fold);
2892   pointer_set_destroy (id.statements_to_fold);
2893
2894   /* Renumber the (code) basic_blocks consecutively.  */
2895   compact_blocks ();
2896   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
2897   number_blocks (fn);
2898
2899   /* We are not going to maintain the cgraph edges up to date.
2900      Kill it so it won't confuse us.  */
2901   cgraph_node_remove_callees (id.dst_node);
2902
2903   fold_cond_expr_cond ();
2904   if (current_function_has_nonlocal_label)
2905     make_nonlocal_label_edges ();
2906   /* It would be nice to check SSA/CFG/statement consistency here, but it is
2907      not possible yet - the IPA passes might make various functions to not
2908      throw and they don't care to proactively update local EH info.  This is
2909      done later in fixup_cfg pass that also execute the verification.  */
2910   return (TODO_update_ssa | TODO_cleanup_cfg
2911           | (gimple_in_ssa_p (cfun) ? TODO_remove_unused_locals : 0)
2912           | (profile_status != PROFILE_ABSENT ? TODO_rebuild_frequencies : 0));
2913 }
2914
2915 /* FN is a function that has a complete body, and CLONE is a function whose
2916    body is to be set to a copy of FN, mapping argument declarations according
2917    to the ARG_MAP splay_tree.  */
2918
2919 void
2920 clone_body (tree clone, tree fn, void *arg_map)
2921 {
2922   copy_body_data id;
2923
2924   /* Clone the body, as if we were making an inline call.  But, remap the
2925      parameters in the callee to the parameters of caller.  */
2926   memset (&id, 0, sizeof (id));
2927   id.src_fn = fn;
2928   id.dst_fn = clone;
2929   id.src_cfun = DECL_STRUCT_FUNCTION (fn);
2930   id.decl_map = (struct pointer_map_t *)arg_map;
2931
2932   id.copy_decl = copy_decl_no_change;
2933   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
2934   id.transform_new_cfg = true;
2935   id.transform_return_to_modify = false;
2936   id.transform_lang_insert_block = true;
2937
2938   /* We're not inside any EH region.  */
2939   id.eh_region = -1;
2940
2941   /* Actually copy the body.  */
2942   append_to_statement_list_force (copy_generic_body (&id), &DECL_SAVED_TREE (clone));
2943 }
2944
2945 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2946
2947 tree
2948 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2949 {
2950   enum tree_code code = TREE_CODE (*tp);
2951   enum tree_code_class cl = TREE_CODE_CLASS (code);
2952
2953   /* We make copies of most nodes.  */
2954   if (IS_EXPR_CODE_CLASS (cl)
2955       || IS_GIMPLE_STMT_CODE_CLASS (cl)
2956       || code == TREE_LIST
2957       || code == TREE_VEC
2958       || code == TYPE_DECL
2959       || code == OMP_CLAUSE)
2960     {
2961       /* Because the chain gets clobbered when we make a copy, we save it
2962          here.  */
2963       tree chain = NULL_TREE, new;
2964
2965       if (!GIMPLE_TUPLE_P (*tp))
2966         chain = TREE_CHAIN (*tp);
2967
2968       /* Copy the node.  */
2969       new = copy_node (*tp);
2970
2971       /* Propagate mudflap marked-ness.  */
2972       if (flag_mudflap && mf_marked_p (*tp))
2973         mf_mark (new);
2974
2975       *tp = new;
2976
2977       /* Now, restore the chain, if appropriate.  That will cause
2978          walk_tree to walk into the chain as well.  */
2979       if (code == PARM_DECL
2980           || code == TREE_LIST
2981           || code == OMP_CLAUSE)
2982         TREE_CHAIN (*tp) = chain;
2983
2984       /* For now, we don't update BLOCKs when we make copies.  So, we
2985          have to nullify all BIND_EXPRs.  */
2986       if (TREE_CODE (*tp) == BIND_EXPR)
2987         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2988     }
2989   else if (code == CONSTRUCTOR)
2990     {
2991       /* CONSTRUCTOR nodes need special handling because
2992          we need to duplicate the vector of elements.  */
2993       tree new;
2994
2995       new = copy_node (*tp);
2996
2997       /* Propagate mudflap marked-ness.  */
2998       if (flag_mudflap && mf_marked_p (*tp))
2999         mf_mark (new);
3000
3001       CONSTRUCTOR_ELTS (new) = VEC_copy (constructor_elt, gc,
3002                                          CONSTRUCTOR_ELTS (*tp));
3003       *tp = new;
3004     }
3005   else if (TREE_CODE_CLASS (code) == tcc_type)
3006     *walk_subtrees = 0;
3007   else if (TREE_CODE_CLASS (code) == tcc_declaration)
3008     *walk_subtrees = 0;
3009   else if (TREE_CODE_CLASS (code) == tcc_constant)
3010     *walk_subtrees = 0;
3011   else
3012     gcc_assert (code != STATEMENT_LIST);
3013   return NULL_TREE;
3014 }
3015
3016 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
3017    information indicating to what new SAVE_EXPR this one should be mapped,
3018    use that one.  Otherwise, create a new node and enter it in ST.  FN is
3019    the function into which the copy will be placed.  */
3020
3021 static void
3022 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
3023 {
3024   struct pointer_map_t *st = (struct pointer_map_t *) st_;
3025   tree *n;
3026   tree t;
3027
3028   /* See if we already encountered this SAVE_EXPR.  */
3029   n = (tree *) pointer_map_contains (st, *tp);
3030
3031   /* If we didn't already remap this SAVE_EXPR, do so now.  */
3032   if (!n)
3033     {
3034       t = copy_node (*tp);
3035
3036       /* Remember this SAVE_EXPR.  */
3037       *pointer_map_insert (st, *tp) = t;
3038       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
3039       *pointer_map_insert (st, t) = t;
3040     }
3041   else
3042     {
3043       /* We've already walked into this SAVE_EXPR; don't do it again.  */
3044       *walk_subtrees = 0;
3045       t = *n;
3046     }
3047
3048   /* Replace this SAVE_EXPR with the copy.  */
3049   *tp = t;
3050 }
3051
3052 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
3053    copies the declaration and enters it in the splay_tree in DATA (which is
3054    really an `copy_body_data *').  */
3055
3056 static tree
3057 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
3058                         void *data)
3059 {
3060   copy_body_data *id = (copy_body_data *) data;
3061
3062   /* Don't walk into types.  */
3063   if (TYPE_P (*tp))
3064     *walk_subtrees = 0;
3065
3066   else if (TREE_CODE (*tp) == LABEL_EXPR)
3067     {
3068       tree decl = TREE_OPERAND (*tp, 0);
3069
3070       /* Copy the decl and remember the copy.  */
3071       insert_decl_map (id, decl, id->copy_decl (decl, id));
3072     }
3073
3074   return NULL_TREE;
3075 }
3076
3077 /* Perform any modifications to EXPR required when it is unsaved.  Does
3078    not recurse into EXPR's subtrees.  */
3079
3080 static void
3081 unsave_expr_1 (tree expr)
3082 {
3083   switch (TREE_CODE (expr))
3084     {
3085     case TARGET_EXPR:
3086       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
3087          It's OK for this to happen if it was part of a subtree that
3088          isn't immediately expanded, such as operand 2 of another
3089          TARGET_EXPR.  */
3090       if (TREE_OPERAND (expr, 1))
3091         break;
3092
3093       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
3094       TREE_OPERAND (expr, 3) = NULL_TREE;
3095       break;
3096
3097     default:
3098       break;
3099     }
3100 }
3101
3102 /* Called via walk_tree when an expression is unsaved.  Using the
3103    splay_tree pointed to by ST (which is really a `splay_tree'),
3104    remaps all local declarations to appropriate replacements.  */
3105
3106 static tree
3107 unsave_r (tree *tp, int *walk_subtrees, void *data)
3108 {
3109   copy_body_data *id = (copy_body_data *) data;
3110   struct pointer_map_t *st = id->decl_map;
3111   tree *n;
3112
3113   /* Only a local declaration (variable or label).  */
3114   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
3115       || TREE_CODE (*tp) == LABEL_DECL)
3116     {
3117       /* Lookup the declaration.  */
3118       n = (tree *) pointer_map_contains (st, *tp);
3119
3120       /* If it's there, remap it.  */
3121       if (n)
3122         *tp = *n;
3123     }
3124
3125   else if (TREE_CODE (*tp) == STATEMENT_LIST)
3126     copy_statement_list (tp);
3127   else if (TREE_CODE (*tp) == BIND_EXPR)
3128     copy_bind_expr (tp, walk_subtrees, id);
3129   else if (TREE_CODE (*tp) == SAVE_EXPR)
3130     remap_save_expr (tp, st, walk_subtrees);
3131   else
3132     {
3133       copy_tree_r (tp, walk_subtrees, NULL);
3134
3135       /* Do whatever unsaving is required.  */
3136       unsave_expr_1 (*tp);
3137     }
3138
3139   /* Keep iterating.  */
3140   return NULL_TREE;
3141 }
3142
3143 /* Copies everything in EXPR and replaces variables, labels
3144    and SAVE_EXPRs local to EXPR.  */
3145
3146 tree
3147 unsave_expr_now (tree expr)
3148 {
3149   copy_body_data id;
3150
3151   /* There's nothing to do for NULL_TREE.  */
3152   if (expr == 0)
3153     return expr;
3154
3155   /* Set up ID.  */
3156   memset (&id, 0, sizeof (id));
3157   id.src_fn = current_function_decl;
3158   id.dst_fn = current_function_decl;
3159   id.decl_map = pointer_map_create ();
3160
3161   id.copy_decl = copy_decl_no_change;
3162   id.transform_call_graph_edges = CB_CGE_DUPLICATE;
3163   id.transform_new_cfg = false;
3164   id.transform_return_to_modify = false;
3165   id.transform_lang_insert_block = false;
3166
3167   /* Walk the tree once to find local labels.  */
3168   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
3169
3170   /* Walk the tree again, copying, remapping, and unsaving.  */
3171   walk_tree (&expr, unsave_r, &id, NULL);
3172
3173   /* Clean up.  */
3174   pointer_map_destroy (id.decl_map);
3175
3176   return expr;
3177 }
3178
3179 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
3180
3181 static tree
3182 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
3183 {
3184   if (*tp == data)
3185     return (tree) data;
3186   else
3187     return NULL;
3188 }
3189
3190 bool
3191 debug_find_tree (tree top, tree search)
3192 {
3193   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
3194 }
3195
3196
3197 /* Declare the variables created by the inliner.  Add all the variables in
3198    VARS to BIND_EXPR.  */
3199
3200 static void
3201 declare_inline_vars (tree block, tree vars)
3202 {
3203   tree t;
3204   for (t = vars; t; t = TREE_CHAIN (t))
3205     {
3206       DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
3207       gcc_assert (!TREE_STATIC (t) && !TREE_ASM_WRITTEN (t));
3208       cfun->unexpanded_var_list =
3209         tree_cons (NULL_TREE, t,
3210                    cfun->unexpanded_var_list);
3211     }
3212
3213   if (block)
3214     BLOCK_VARS (block) = chainon (BLOCK_VARS (block), vars);
3215 }
3216
3217
3218 /* Copy NODE (which must be a DECL).  The DECL originally was in the FROM_FN,
3219    but now it will be in the TO_FN.  PARM_TO_VAR means enable PARM_DECL to
3220    VAR_DECL translation.  */
3221
3222 static tree
3223 copy_decl_for_dup_finish (copy_body_data *id, tree decl, tree copy)
3224 {
3225   /* Don't generate debug information for the copy if we wouldn't have
3226      generated it for the copy either.  */
3227   DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (decl);
3228   DECL_IGNORED_P (copy) = DECL_IGNORED_P (decl);
3229
3230   /* Set the DECL_ABSTRACT_ORIGIN so the debugging routines know what
3231      declaration inspired this copy.  */
3232   DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (decl);
3233
3234   /* The new variable/label has no RTL, yet.  */
3235   if (CODE_CONTAINS_STRUCT (TREE_CODE (copy), TS_DECL_WRTL)
3236       && !TREE_STATIC (copy) && !DECL_EXTERNAL (copy))
3237     SET_DECL_RTL (copy, NULL_RTX);
3238
3239   /* These args would always appear unused, if not for this.  */
3240   TREE_USED (copy) = 1;
3241
3242   /* Set the context for the new declaration.  */
3243   if (!DECL_CONTEXT (decl))
3244     /* Globals stay global.  */
3245     ;
3246   else if (DECL_CONTEXT (decl) != id->src_fn)
3247     /* Things that weren't in the scope of the function we're inlining
3248        from aren't in the scope we're inlining to, either.  */
3249     ;
3250   else if (TREE_STATIC (decl))
3251     /* Function-scoped static variables should stay in the original
3252        function.  */
3253     ;
3254   else
3255     /* Ordinary automatic local variables are now in the scope of the
3256        new function.  */
3257     DECL_CONTEXT (copy) = id->dst_fn;
3258
3259   return copy;
3260 }
3261
3262 static tree
3263 copy_decl_to_var (tree decl, copy_body_data *id)
3264 {
3265   tree copy, type;
3266
3267   gcc_assert (TREE_CODE (decl) == PARM_DECL
3268               || TREE_CODE (decl) == RESULT_DECL);
3269
3270   type = TREE_TYPE (decl);
3271
3272   copy = build_decl (VAR_DECL, DECL_NAME (decl), type);
3273   TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (decl);
3274   TREE_READONLY (copy) = TREE_READONLY (decl);
3275   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (decl);
3276   DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (decl);
3277   DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (decl);
3278
3279   return copy_decl_for_dup_finish (id, decl, copy);
3280 }
3281
3282 /* Like copy_decl_to_var, but create a return slot object instead of a
3283    pointer variable for return by invisible reference.  */
3284
3285 static tree
3286 copy_result_decl_to_var (tree decl, copy_body_data *id)
3287 {
3288   tree copy, type;
3289
3290   gcc_assert (TREE_CODE (decl) == PARM_DECL
3291               || TREE_CODE (decl) == RESULT_DECL);
3292
3293   type = TREE_TYPE (decl);
3294   if (DECL_BY_REFERENCE (decl))
3295     type = TREE_TYPE (type);
3296
3297   copy = build_decl (VAR_DECL, DECL_NAME (decl), type);
3298   TREE_READONLY (copy) = TREE_READONLY (decl);
3299   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (decl);
3300   if (!DECL_BY_REFERENCE (decl))
3301     {
3302       TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (decl);
3303       DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (decl);
3304       DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (decl);
3305     }
3306
3307   return copy_decl_for_dup_finish (id, decl, copy);
3308 }
3309
3310
3311 static tree
3312 copy_decl_no_change (tree decl, copy_body_data *id)
3313 {
3314   tree copy;
3315
3316   copy = copy_node (decl);
3317
3318   /* The COPY is not abstract; it will be generated in DST_FN.  */
3319   DECL_ABSTRACT (copy) = 0;
3320   lang_hooks.dup_lang_specific_decl (copy);
3321
3322   /* TREE_ADDRESSABLE isn't used to indicate that a label's address has
3323      been taken; it's for internal bookkeeping in expand_goto_internal.  */
3324   if (TREE_CODE (copy) == LABEL_DECL)
3325     {
3326       TREE_ADDRESSABLE (copy) = 0;
3327       LABEL_DECL_UID (copy) = -1;
3328     }
3329
3330   return copy_decl_for_dup_finish (id, decl, copy);
3331 }
3332
3333 static tree
3334 copy_decl_maybe_to_var (tree decl, copy_body_data *id)
3335 {
3336   if (TREE_CODE (decl) == PARM_DECL || TREE_CODE (decl) == RESULT_DECL)
3337     return copy_decl_to_var (decl, id);
3338   else
3339     return copy_decl_no_change (decl, id);
3340 }
3341
3342 /* Return a copy of the function's argument tree.  */
3343 static tree
3344 copy_arguments_for_versioning (tree orig_parm, copy_body_data * id)
3345 {
3346   tree *arg_copy, *parg;
3347
3348   arg_copy = &orig_parm;
3349   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
3350     {
3351       tree new = remap_decl (*parg, id);
3352       lang_hooks.dup_lang_specific_decl (new);
3353       TREE_CHAIN (new) = TREE_CHAIN (*parg);
3354       *parg = new;
3355     }
3356   return orig_parm;
3357 }
3358
3359 /* Return a copy of the function's static chain.  */
3360 static tree
3361 copy_static_chain (tree static_chain, copy_body_data * id)
3362 {
3363   tree *chain_copy, *pvar;
3364
3365   chain_copy = &static_chain;
3366   for (pvar = chain_copy; *pvar; pvar = &TREE_CHAIN (*pvar))
3367     {
3368       tree new = remap_decl (*pvar, id);
3369       lang_hooks.dup_lang_specific_decl (new);
3370       TREE_CHAIN (new) = TREE_CHAIN (*pvar);
3371       *pvar = new;
3372     }
3373   return static_chain;
3374 }
3375
3376 /* Return true if the function is allowed to be versioned.
3377    This is a guard for the versioning functionality.  */
3378 bool
3379 tree_versionable_function_p (tree fndecl)
3380 {
3381   if (fndecl == NULL_TREE)
3382     return false;
3383   /* ??? There are cases where a function is
3384      uninlinable but can be versioned.  */
3385   if (!tree_inlinable_function_p (fndecl))
3386     return false;
3387
3388   return true;
3389 }
3390
3391 /* Create a copy of a function's tree.
3392    OLD_DECL and NEW_DECL are FUNCTION_DECL tree nodes
3393    of the original function and the new copied function
3394    respectively.  In case we want to replace a DECL
3395    tree with another tree while duplicating the function's
3396    body, TREE_MAP represents the mapping between these
3397    trees. If UPDATE_CLONES is set, the call_stmt fields
3398    of edges of clones of the function will be updated.  */
3399 void
3400 tree_function_versioning (tree old_decl, tree new_decl, varray_type tree_map,
3401                           bool update_clones)
3402 {
3403   struct cgraph_node *old_version_node;
3404   struct cgraph_node *new_version_node;
3405   copy_body_data id;
3406   tree p;
3407   unsigned i;
3408   struct ipa_replace_map *replace_info;
3409   basic_block old_entry_block;
3410   tree t_step;
3411   tree old_current_function_decl = current_function_decl;
3412
3413   gcc_assert (TREE_CODE (old_decl) == FUNCTION_DECL
3414               && TREE_CODE (new_decl) == FUNCTION_DECL);
3415   DECL_POSSIBLY_INLINED (old_decl) = 1;
3416
3417   old_version_node = cgraph_node (old_decl);
3418   new_version_node = cgraph_node (new_decl);
3419
3420   DECL_ARTIFICIAL (new_decl) = 1;
3421   DECL_ABSTRACT_ORIGIN (new_decl) = DECL_ORIGIN (old_decl);
3422
3423   /* Prepare the data structures for the tree copy.  */
3424   memset (&id, 0, sizeof (id));
3425
3426   /* Generate a new name for the new version. */
3427   if (!update_clones)
3428     {
3429       DECL_NAME (new_decl) =  create_tmp_var_name (NULL);
3430       SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
3431       SET_DECL_RTL (new_decl, NULL_RTX);
3432       id.statements_to_fold = pointer_set_create ();
3433     }
3434
3435   id.decl_map = pointer_map_create ();
3436   id.src_fn = old_decl;
3437   id.dst_fn = new_decl;
3438   id.src_node = old_version_node;
3439   id.dst_node = new_version_node;
3440   id.src_cfun = DECL_STRUCT_FUNCTION (old_decl);
3441
3442   id.copy_decl = copy_decl_no_change;
3443   id.transform_call_graph_edges
3444     = update_clones ? CB_CGE_MOVE_CLONES : CB_CGE_MOVE;
3445   id.transform_new_cfg = true;
3446   id.transform_return_to_modify = false;
3447   id.transform_lang_insert_block = false;
3448
3449   current_function_decl = new_decl;
3450   old_entry_block = ENTRY_BLOCK_PTR_FOR_FUNCTION
3451     (DECL_STRUCT_FUNCTION (old_decl));
3452   initialize_cfun (new_decl, old_decl,
3453                    old_entry_block->count,
3454                    old_entry_block->frequency);
3455   push_cfun (DECL_STRUCT_FUNCTION (new_decl));
3456
3457   /* Copy the function's static chain.  */
3458   p = DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl;
3459   if (p)
3460     DECL_STRUCT_FUNCTION (new_decl)->static_chain_decl =
3461       copy_static_chain (DECL_STRUCT_FUNCTION (old_decl)->static_chain_decl,
3462                          &id);
3463   /* Copy the function's arguments.  */
3464   if (DECL_ARGUMENTS (old_decl) != NULL_TREE)
3465     DECL_ARGUMENTS (new_decl) =
3466       copy_arguments_for_versioning (DECL_ARGUMENTS (old_decl), &id);
3467
3468   /* If there's a tree_map, prepare for substitution.  */
3469   if (tree_map)
3470     for (i = 0; i < VARRAY_ACTIVE_SIZE (tree_map); i++)
3471       {
3472         replace_info = VARRAY_GENERIC_PTR (tree_map, i);
3473         if (replace_info->replace_p)
3474           insert_decl_map (&id, replace_info->old_tree,
3475                            replace_info->new_tree);
3476       }
3477
3478   DECL_INITIAL (new_decl) = remap_blocks (DECL_INITIAL (id.src_fn), &id);
3479
3480   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
3481   number_blocks (id.dst_fn);
3482
3483   if (DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list != NULL_TREE)
3484     /* Add local vars.  */
3485     for (t_step = DECL_STRUCT_FUNCTION (old_decl)->unexpanded_var_list;
3486          t_step; t_step = TREE_CHAIN (t_step))
3487       {
3488         tree var = TREE_VALUE (t_step);
3489         if (TREE_STATIC (var) && !TREE_ASM_WRITTEN (var))
3490           cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
3491                                                  cfun->unexpanded_var_list);
3492         else
3493           cfun->unexpanded_var_list =
3494             tree_cons (NULL_TREE, remap_decl (var, &id),
3495                        cfun->unexpanded_var_list);
3496       }
3497
3498   /* Copy the Function's body.  */
3499   copy_body (&id, old_entry_block->count, old_entry_block->frequency, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR);
3500
3501   if (DECL_RESULT (old_decl) != NULL_TREE)
3502     {
3503       tree *res_decl = &DECL_RESULT (old_decl);
3504       DECL_RESULT (new_decl) = remap_decl (*res_decl, &id);
3505       lang_hooks.dup_lang_specific_decl (DECL_RESULT (new_decl));
3506     }
3507
3508   /* Renumber the lexical scoping (non-code) blocks consecutively.  */
3509   number_blocks (new_decl);
3510
3511   /* Clean up.  */
3512   pointer_map_destroy (id.decl_map);
3513   if (!update_clones)
3514     {
3515       fold_marked_statements (0, id.statements_to_fold);
3516       pointer_set_destroy (id.statements_to_fold);
3517       fold_cond_expr_cond ();
3518     }
3519   if (gimple_in_ssa_p (cfun))
3520     {
3521       free_dominance_info (CDI_DOMINATORS);
3522       free_dominance_info (CDI_POST_DOMINATORS);
3523       if (!update_clones)
3524         delete_unreachable_blocks ();
3525       update_ssa (TODO_update_ssa);
3526       if (!update_clones)
3527         {
3528           fold_cond_expr_cond ();
3529           if (need_ssa_update_p ())
3530             update_ssa (TODO_update_ssa);
3531         }
3532     }
3533   free_dominance_info (CDI_DOMINATORS);
3534   free_dominance_info (CDI_POST_DOMINATORS);
3535   pop_cfun ();
3536   current_function_decl = old_current_function_decl;
3537   gcc_assert (!current_function_decl
3538               || DECL_STRUCT_FUNCTION (current_function_decl) == cfun);
3539   return;
3540 }
3541
3542 /* Duplicate a type, fields and all.  */
3543
3544 tree
3545 build_duplicate_type (tree type)
3546 {
3547   struct copy_body_data id;
3548
3549   memset (&id, 0, sizeof (id));
3550   id.src_fn = current_function_decl;
3551   id.dst_fn = current_function_decl;
3552   id.src_cfun = cfun;
3553   id.decl_map = pointer_map_create ();
3554
3555   type = remap_type_1 (type, &id);
3556
3557   pointer_map_destroy (id.decl_map);
3558
3559   return type;
3560 }