gcc/tree-inline.c

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