gcc/tree-inline.c

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