gcc/tree-inline.c

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