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