gcc/tree-inline.c

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