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