gcc/tree-inline.c

   1 /* Tree inlining.
   2    Copyright 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Alexandre Oliva <aoliva@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, 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 "integrate.h"
  36 #include "varray.h"
  37 #include "hashtab.h"
  38 #include "pointer-set.h"
  39 #include "splay-tree.h"
  40 #include "langhooks.h"
  41 #include "cgraph.h"
  42 #include "intl.h"
  43 #include "tree-mudflap.h"
  44 #include "tree-flow.h"
  45 #include "function.h"
  46 #include "diagnostic.h"
  47 #include "debug.h"
  48
  49 /* I'm not real happy about this, but we need to handle gimple and
  50    non-gimple trees.  */
  51 #include "tree-iterator.h"
  52 #include "tree-gimple.h"
  53
  54 /* 0 if we should not perform inlining.
  55    1 if we should expand functions calls inline at the tree level.
  56    2 if we should consider *all* functions to be inline
  57    candidates.  */
  58
  59 int flag_inline_trees = 0;
  60
  61 /* To Do:
  62
  63    o In order to make inlining-on-trees work, we pessimized
  64      function-local static constants.  In particular, they are now
  65      always output, even when not addressed.  Fix this by treating
  66      function-local static constants just like global static
  67      constants; the back-end already knows not to output them if they
  68      are not needed.
  69
  70    o Provide heuristics to clamp inlining of recursive template
  71      calls?  */
  72
  73 /* Data required for function inlining.  */
  74
  75 typedef struct inline_data
  76 {
  77   /* A stack of the functions we are inlining.  For example, if we are
  78      compiling `f', which calls `g', which calls `h', and we are
  79      inlining the body of `h', the stack will contain, `h', followed
  80      by `g', followed by `f'.  The first few elements of the stack may
  81      contain other functions that we know we should not recurse into,
  82      even though they are not directly being inlined.  */
  83   varray_type fns;
  84   /* The index of the first element of FNS that really represents an
  85      inlined function.  */
  86   unsigned first_inlined_fn;
  87   /* The label to jump to when a return statement is encountered.  If
  88      this value is NULL, then return statements will simply be
  89      remapped as return statements, rather than as jumps.  */
  90   tree ret_label;
  91   /* The VAR_DECL for the return value.  */
  92   tree retvar;
  93   /* The map from local declarations in the inlined function to
  94      equivalents in the function into which it is being inlined.  */
  95   splay_tree decl_map;
  96   /* Nonzero if we are currently within the cleanup for a
  97      TARGET_EXPR.  */
  98   int in_target_cleanup_p;
  99   /* We use the same mechanism to build clones that we do to perform
 100      inlining.  However, there are a few places where we need to
 101      distinguish between those two situations.  This flag is true if
 102      we are cloning, rather than inlining.  */
 103   bool cloning_p;
 104   /* Similarly for saving function body.  */
 105   bool saving_p;
 106   /* Hash table used to prevent walk_tree from visiting the same node
 107      umpteen million times.  */
 108   htab_t tree_pruner;
 109   /* Callgraph node of function we are inlining into.  */
 110   struct cgraph_node *node;
 111   /* Callgraph node of currently inlined function.  */
 112   struct cgraph_node *current_node;
 113   /* Statement iterator.  We need this so we can keep the tree in
 114      gimple form when we insert the inlined function.   It is not
 115      used when we are not dealing with gimple trees.  */
 116   tree_stmt_iterator tsi;
 117 } inline_data;
 118
 119 /* Prototypes.  */
 120
 121 /* The approximate number of instructions per statement.  This number
 122    need not be particularly accurate; it is used only to make
 123    decisions about when a function is too big to inline.  */
 124 #define INSNS_PER_STMT (10)
 125
 126 static tree copy_body_r (tree *, int *, void *);
 127 static tree copy_body (inline_data *);
 128 static tree expand_call_inline (tree *, int *, void *);
 129 static void expand_calls_inline (tree *, inline_data *);
 130 static bool inlinable_function_p (tree);
 131 static tree remap_decl (tree, inline_data *);
 132 static tree remap_type (tree, inline_data *);
 133 static tree initialize_inlined_parameters (inline_data *, tree,
 134                                            tree, tree, tree);
 135 static void remap_block (tree *, inline_data *);
 136 static tree remap_decls (tree, inline_data *);
 137 static void copy_bind_expr (tree *, int *, inline_data *);
 138 static tree mark_local_for_remap_r (tree *, int *, void *);
 139 static void unsave_expr_1 (tree);
 140 static tree unsave_r (tree *, int *, void *);
 141 static void declare_inline_vars (tree bind_expr, tree vars);
 142 static void remap_save_expr (tree *, void *, int *);
 143
 144 /* Insert a tree->tree mapping for ID.  Despite the name suggests
 145    that the trees should be variables, it is used for more than that.  */
 146
 147 static void
 148 insert_decl_map (inline_data *id, tree key, tree value)
 149 {
 150   splay_tree_insert (id->decl_map, (splay_tree_key) key,
 151                      (splay_tree_value) value);
 152
 153   /* Always insert an identity map as well.  If we see this same new
 154      node again, we won't want to duplicate it a second time.  */
 155   if (key != value)
 156     splay_tree_insert (id->decl_map, (splay_tree_key) value,
 157                        (splay_tree_value) value);
 158 }
 159
 160 /* Remap DECL during the copying of the BLOCK tree for the function.
 161    We are only called to remap local variables in the current function.  */
 162
 163 static tree
 164 remap_decl (tree decl, inline_data *id)
 165 {
 166   splay_tree_node n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 167   tree fn = VARRAY_TOP_TREE (id->fns);
 168
 169   /* See if we have remapped this declaration.  If we didn't already have an
 170      equivalent for this declaration, create one now.  */
 171   if (!n)
 172     {
 173       /* Make a copy of the variable or label.  */
 174       tree t = copy_decl_for_inlining (decl, fn, VARRAY_TREE (id->fns, 0));
 175
 176       /* Remap types, if necessary.  */
 177       TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
 178       if (TREE_CODE (t) == TYPE_DECL)
 179         DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
 180       else if (TREE_CODE (t) == PARM_DECL)
 181         DECL_ARG_TYPE_AS_WRITTEN (t)
 182           = remap_type (DECL_ARG_TYPE_AS_WRITTEN (t), id);
 183
 184       /* Remap sizes as necessary.  */
 185       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 186       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 187
 188       /* If fields, do likewise for offset and qualifier.  */
 189       if (TREE_CODE (t) == FIELD_DECL)
 190         {
 191           walk_tree (&DECL_FIELD_OFFSET (t), copy_body_r, id, NULL);
 192           if (TREE_CODE (DECL_CONTEXT (t)) == QUAL_UNION_TYPE)
 193             walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
 194         }
 195
 196 #if 0
 197       /* FIXME handle anon aggrs.  */
 198       if (! DECL_NAME (t) && TREE_TYPE (t)
 199           && lang_hooks.tree_inlining.anon_aggr_type_p (TREE_TYPE (t)))
 200         {
 201           /* For a VAR_DECL of anonymous type, we must also copy the
 202              member VAR_DECLS here and rechain the DECL_ANON_UNION_ELEMS.  */
 203           tree members = NULL;
 204           tree src;
 205
 206           for (src = DECL_ANON_UNION_ELEMS (t); src;
 207                src = TREE_CHAIN (src))
 208             {
 209               tree member = remap_decl (TREE_VALUE (src), id);
 210
 211               gcc_assert (!TREE_PURPOSE (src));
 212               members = tree_cons (NULL, member, members);
 213             }
 214           DECL_ANON_UNION_ELEMS (t) = nreverse (members);
 215         }
 216 #endif
 217
 218       /* Remember it, so that if we encounter this local entity
 219          again we can reuse this copy.  */
 220       insert_decl_map (id, decl, t);
 221       return t;
 222     }
 223
 224   return unshare_expr ((tree) n->value);
 225 }
 226
 227 static tree
 228 remap_type (tree type, inline_data *id)
 229 {
 230   splay_tree_node node;
 231   tree new, t;
 232
 233   if (type == NULL)
 234     return type;
 235
 236   /* See if we have remapped this type.  */
 237   node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
 238   if (node)
 239     return (tree) node->value;
 240
 241   /* The type only needs remapping if it's variably modified by a variable
 242      in the function we are inlining.  */
 243   if (! variably_modified_type_p (type, VARRAY_TOP_TREE (id->fns)))
 244     {
 245       insert_decl_map (id, type, type);
 246       return type;
 247     }
 248
 249   /* We do need a copy.  build and register it now.  If this is a pointer or
 250      reference type, remap the designated type and make a new pointer or
 251      reference type.  */
 252   if (TREE_CODE (type) == POINTER_TYPE)
 253     {
 254       new = build_pointer_type_for_mode (remap_type (TREE_TYPE (type), id),
 255                                          TYPE_MODE (type),
 256                                          TYPE_REF_CAN_ALIAS_ALL (type));
 257       insert_decl_map (id, type, new);
 258       return new;
 259     }
 260   else if (TREE_CODE (type) == REFERENCE_TYPE)
 261     {
 262       new = build_reference_type_for_mode (remap_type (TREE_TYPE (type), id),
 263                                             TYPE_MODE (type),
 264                                             TYPE_REF_CAN_ALIAS_ALL (type));
 265       insert_decl_map (id, type, new);
 266       return new;
 267     }
 268   else
 269     new = copy_node (type);
 270
 271   insert_decl_map (id, type, new);
 272
 273   /* This is a new type, not a copy of an old type.  Need to reassociate
 274      variants.  We can handle everything except the main variant lazily.  */
 275   t = TYPE_MAIN_VARIANT (type);
 276   if (type != t)
 277     {
 278       t = remap_type (t, id);
 279       TYPE_MAIN_VARIANT (new) = t;
 280       TYPE_NEXT_VARIANT (new) = TYPE_MAIN_VARIANT (t);
 281       TYPE_NEXT_VARIANT (t) = new;
 282     }
 283   else
 284     {
 285       TYPE_MAIN_VARIANT (new) = new;
 286       TYPE_NEXT_VARIANT (new) = NULL;
 287     }
 288
 289   /* Lazily create pointer and reference types.  */
 290   TYPE_POINTER_TO (new) = NULL;
 291   TYPE_REFERENCE_TO (new) = NULL;
 292
 293   switch (TREE_CODE (new))
 294     {
 295     case INTEGER_TYPE:
 296     case REAL_TYPE:
 297     case ENUMERAL_TYPE:
 298     case BOOLEAN_TYPE:
 299     case CHAR_TYPE:
 300       t = TYPE_MIN_VALUE (new);
 301       if (t && TREE_CODE (t) != INTEGER_CST)
 302         walk_tree (&TYPE_MIN_VALUE (new), copy_body_r, id, NULL);
 303
 304       t = TYPE_MAX_VALUE (new);
 305       if (t && TREE_CODE (t) != INTEGER_CST)
 306         walk_tree (&TYPE_MAX_VALUE (new), copy_body_r, id, NULL);
 307       return new;
 308
 309     case FUNCTION_TYPE:
 310       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 311       walk_tree (&TYPE_ARG_TYPES (new), copy_body_r, id, NULL);
 312       return new;
 313
 314     case ARRAY_TYPE:
 315       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 316       TYPE_DOMAIN (new) = remap_type (TYPE_DOMAIN (new), id);
 317       break;
 318
 319     case RECORD_TYPE:
 320     case UNION_TYPE:
 321     case QUAL_UNION_TYPE:
 322       walk_tree (&TYPE_FIELDS (new), copy_body_r, id, NULL);
 323       break;
 324
 325     case FILE_TYPE:
 326     case OFFSET_TYPE:
 327     default:
 328       /* Shouldn't have been thought variable sized.  */
 329       gcc_unreachable ();
 330     }
 331
 332   walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
 333   walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
 334
 335   return new;
 336 }
 337
 338 static tree
 339 remap_decls (tree decls, inline_data *id)
 340 {
 341   tree old_var;
 342   tree new_decls = NULL_TREE;
 343
 344   /* Remap its variables.  */
 345   for (old_var = decls; old_var; old_var = TREE_CHAIN (old_var))
 346     {
 347       tree new_var;
 348
 349       /* Remap the variable.  */
 350       new_var = remap_decl (old_var, id);
 351
 352       /* If we didn't remap this variable, so we can't mess with its
 353          TREE_CHAIN.  If we remapped this variable to the return slot, it's
 354          already declared somewhere else, so don't declare it here.  */
 355       if (!new_var || new_var == id->retvar)
 356         ;
 357       else
 358         {
 359           gcc_assert (DECL_P (new_var));
 360           TREE_CHAIN (new_var) = new_decls;
 361           new_decls = new_var;
 362         }
 363     }
 364
 365   return nreverse (new_decls);
 366 }
 367
 368 /* Copy the BLOCK to contain remapped versions of the variables
 369    therein.  And hook the new block into the block-tree.  */
 370
 371 static void
 372 remap_block (tree *block, inline_data *id)
 373 {
 374   tree old_block;
 375   tree new_block;
 376   tree fn;
 377
 378   /* Make the new block.  */
 379   old_block = *block;
 380   new_block = make_node (BLOCK);
 381   TREE_USED (new_block) = TREE_USED (old_block);
 382   BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 383   *block = new_block;
 384
 385   /* Remap its variables.  */
 386   BLOCK_VARS (new_block) = remap_decls (BLOCK_VARS (old_block), id);
 387
 388   fn = VARRAY_TREE (id->fns, 0);
 389 #if 1
 390   /* FIXME!  It shouldn't be so hard to manage blocks.  Rebuilding them in
 391      rest_of_compilation is a good start.  */
 392   if (id->cloning_p)
 393     /* We're building a clone; DECL_INITIAL is still
 394        error_mark_node, and current_binding_level is the parm
 395        binding level.  */
 396     lang_hooks.decls.insert_block (new_block);
 397   else
 398     {
 399       /* Attach this new block after the DECL_INITIAL block for the
 400          function into which this block is being inlined.  In
 401          rest_of_compilation we will straighten out the BLOCK tree.  */
 402       tree *first_block;
 403       if (DECL_INITIAL (fn))
 404         first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
 405       else
 406         first_block = &DECL_INITIAL (fn);
 407       BLOCK_CHAIN (new_block) = *first_block;
 408       *first_block = new_block;
 409     }
 410 #endif
 411   /* Remember the remapped block.  */
 412   insert_decl_map (id, old_block, new_block);
 413 }
 414
 415 static void
 416 copy_statement_list (tree *tp)
 417 {
 418   tree_stmt_iterator oi, ni;
 419   tree new;
 420
 421   new = alloc_stmt_list ();
 422   ni = tsi_start (new);
 423   oi = tsi_start (*tp);
 424   *tp = new;
 425
 426   for (; !tsi_end_p (oi); tsi_next (&oi))
 427     tsi_link_after (&ni, tsi_stmt (oi), TSI_NEW_STMT);
 428 }
 429
 430 static void
 431 copy_bind_expr (tree *tp, int *walk_subtrees, inline_data *id)
 432 {
 433   tree block = BIND_EXPR_BLOCK (*tp);
 434   /* Copy (and replace) the statement.  */
 435   copy_tree_r (tp, walk_subtrees, NULL);
 436   if (block)
 437     {
 438       remap_block (&block, id);
 439       BIND_EXPR_BLOCK (*tp) = block;
 440     }
 441
 442   if (BIND_EXPR_VARS (*tp))
 443     /* This will remap a lot of the same decls again, but this should be
 444        harmless.  */
 445     BIND_EXPR_VARS (*tp) = remap_decls (BIND_EXPR_VARS (*tp), id);
 446 }
 447
 448 /* Called from copy_body via walk_tree.  DATA is really an `inline_data *'.  */
 449
 450 static tree
 451 copy_body_r (tree *tp, int *walk_subtrees, void *data)
 452 {
 453   inline_data *id = (inline_data *) data;
 454   tree fn = VARRAY_TOP_TREE (id->fns);
 455
 456 #if 0
 457   /* All automatic variables should have a DECL_CONTEXT indicating
 458      what function they come from.  */
 459   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 460       && DECL_NAMESPACE_SCOPE_P (*tp))
 461     gcc_assert (DECL_EXTERNAL (*tp) || TREE_STATIC (*tp));
 462 #endif
 463
 464   /* If this is a RETURN_EXPR, change it into a MODIFY_EXPR and a
 465      GOTO_EXPR with the RET_LABEL as its target.  */
 466   if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
 467     {
 468       tree return_stmt = *tp;
 469       tree goto_stmt;
 470
 471       /* Build the GOTO_EXPR.  */
 472       tree assignment = TREE_OPERAND (return_stmt, 0);
 473       goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
 474       TREE_USED (id->ret_label) = 1;
 475
 476       /* If we're returning something, just turn that into an
 477          assignment into the equivalent of the original
 478          RESULT_DECL.  */
 479       if (assignment)
 480         {
 481           /* Do not create a statement containing a naked RESULT_DECL.  */
 482           if (TREE_CODE (assignment) == RESULT_DECL)
 483             gimplify_stmt (&assignment);
 484
 485           *tp = build (BIND_EXPR, void_type_node, NULL, NULL, NULL);
 486           append_to_statement_list (assignment, &BIND_EXPR_BODY (*tp));
 487           append_to_statement_list (goto_stmt, &BIND_EXPR_BODY (*tp));
 488         }
 489       /* If we're not returning anything just do the jump.  */
 490       else
 491         *tp = goto_stmt;
 492     }
 493   /* Local variables and labels need to be replaced by equivalent
 494      variables.  We don't want to copy static variables; there's only
 495      one of those, no matter how many times we inline the containing
 496      function.  Similarly for globals from an outer function.  */
 497   else if (lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
 498     {
 499       tree new_decl;
 500
 501       /* Remap the declaration.  */
 502       new_decl = remap_decl (*tp, id);
 503       gcc_assert (new_decl);
 504       /* Replace this variable with the copy.  */
 505       STRIP_TYPE_NOPS (new_decl);
 506       *tp = new_decl;
 507       *walk_subtrees = 0;
 508     }
 509   else if (TREE_CODE (*tp) == STATEMENT_LIST)
 510     copy_statement_list (tp);
 511   else if (TREE_CODE (*tp) == SAVE_EXPR)
 512     remap_save_expr (tp, id->decl_map, walk_subtrees);
 513   else if (TREE_CODE (*tp) == BIND_EXPR)
 514     copy_bind_expr (tp, walk_subtrees, id);
 515   /* Types may need remapping as well.  */
 516   else if (TYPE_P (*tp))
 517     *tp = remap_type (*tp, id);
 518
 519   /* If this is a constant, we have to copy the node iff the type will be
 520      remapped.  copy_tree_r will not copy a constant.  */
 521   else if (TREE_CODE_CLASS (TREE_CODE (*tp)) == tcc_constant)
 522     {
 523       tree new_type = remap_type (TREE_TYPE (*tp), id);
 524
 525       if (new_type == TREE_TYPE (*tp))
 526         *walk_subtrees = 0;
 527
 528       else if (TREE_CODE (*tp) == INTEGER_CST)
 529         *tp = build_int_cst_wide (new_type, TREE_INT_CST_LOW (*tp),
 530                                   TREE_INT_CST_HIGH (*tp));
 531       else
 532         {
 533           *tp = copy_node (*tp);
 534           TREE_TYPE (*tp) = new_type;
 535         }
 536     }
 537
 538   /* Otherwise, just copy the node.  Note that copy_tree_r already
 539      knows not to copy VAR_DECLs, etc., so this is safe.  */
 540   else
 541     {
 542       tree old_node = *tp;
 543
 544       if (TREE_CODE (*tp) == MODIFY_EXPR
 545           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 546           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 547               (TREE_OPERAND (*tp, 0), fn)))
 548         {
 549           /* Some assignments VAR = VAR; don't generate any rtl code
 550              and thus don't count as variable modification.  Avoid
 551              keeping bogosities like 0 = 0.  */
 552           tree decl = TREE_OPERAND (*tp, 0), value;
 553           splay_tree_node n;
 554
 555           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 556           if (n)
 557             {
 558               value = (tree) n->value;
 559               STRIP_TYPE_NOPS (value);
 560               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 561                 {
 562                   *tp = build_empty_stmt ();
 563                   return copy_body_r (tp, walk_subtrees, data);
 564                 }
 565             }
 566         }
 567       else if (TREE_CODE (*tp) == INDIRECT_REF)
 568         {
 569           /* Get rid of *& from inline substitutions that can happen when a
 570              pointer argument is an ADDR_EXPR.  */
 571           tree decl = TREE_OPERAND (*tp, 0), value;
 572           splay_tree_node n;
 573
 574           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 575           if (n)
 576             {
 577               value = (tree) n->value;
 578               STRIP_NOPS (value);
 579               if (TREE_CODE (value) == ADDR_EXPR
 580                   && (lang_hooks.types_compatible_p
 581                       (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0)))))
 582                 {
 583                   *tp = TREE_OPERAND (value, 0);
 584                   return copy_body_r (tp, walk_subtrees, data);
 585                 }
 586             }
 587         }
 588
 589       copy_tree_r (tp, walk_subtrees, NULL);
 590
 591       if (TREE_CODE (*tp) == CALL_EXPR && id->node && get_callee_fndecl (*tp))
 592         {
 593           if (id->saving_p)
 594             {
 595               struct cgraph_node *node;
 596               struct cgraph_edge *edge;
 597
 598               for (node = id->node->next_clone; node; node = node->next_clone)
 599                 {
 600                   edge = cgraph_edge (node, old_node);
 601                   gcc_assert (edge);
 602                   edge->call_expr = *tp;
 603                 }
 604             }
 605           else
 606             {
 607               struct cgraph_edge *edge
 608                 = cgraph_edge (id->current_node, old_node);
 609
 610               if (edge)
 611                 cgraph_clone_edge (edge, id->node, *tp);
 612             }
 613         }
 614
 615       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 616
 617       /* The copied TARGET_EXPR has never been expanded, even if the
 618          original node was expanded already.  */
 619       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 620         {
 621           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 622           TREE_OPERAND (*tp, 3) = NULL_TREE;
 623         }
 624
 625       /* Variable substitution need not be simple.  In particular, the
 626          INDIRECT_REF substitution above.  Make sure that TREE_CONSTANT
 627          and friends are up-to-date.  */
 628       else if (TREE_CODE (*tp) == ADDR_EXPR)
 629         {
 630           walk_tree (&TREE_OPERAND (*tp, 0), copy_body_r, id, NULL);
 631           recompute_tree_invarant_for_addr_expr (*tp);
 632           *walk_subtrees = 0;
 633         }
 634     }
 635
 636   /* Keep iterating.  */
 637   return NULL_TREE;
 638 }
 639
 640 /* Make a copy of the body of FN so that it can be inserted inline in
 641    another function.  */
 642
 643 static tree
 644 copy_body (inline_data *id)
 645 {
 646   tree body;
 647   tree fndecl = VARRAY_TOP_TREE (id->fns);
 648
 649   if (fndecl == current_function_decl
 650       && cfun->saved_tree)
 651     body = cfun->saved_tree;
 652   else
 653     body = DECL_SAVED_TREE (fndecl);
 654   walk_tree (&body, copy_body_r, id, NULL);
 655
 656   return body;
 657 }
 658
 659 /* Return true if VALUE is an ADDR_EXPR of an automatic variable
 660    defined in function FN, or of a data member thereof.  */
 661
 662 static bool
 663 self_inlining_addr_expr (tree value, tree fn)
 664 {
 665   tree var;
 666
 667   if (TREE_CODE (value) != ADDR_EXPR)
 668     return false;
 669
 670   var = get_base_address (TREE_OPERAND (value, 0));
 671
 672   return var && lang_hooks.tree_inlining.auto_var_in_fn_p (var, fn);
 673 }
 674
 675 static void
 676 setup_one_parameter (inline_data *id, tree p, tree value, tree fn,
 677                      tree *init_stmts, tree *vars, bool *gimplify_init_stmts_p)
 678 {
 679   tree init_stmt;
 680   tree var;
 681
 682   /* If the parameter is never assigned to, we may not need to
 683      create a new variable here at all.  Instead, we may be able
 684      to just use the argument value.  */
 685   if (TREE_READONLY (p)
 686       && !TREE_ADDRESSABLE (p)
 687       && value && !TREE_SIDE_EFFECTS (value))
 688     {
 689       /* We can't risk substituting complex expressions.  They
 690          might contain variables that will be assigned to later.
 691          Theoretically, we could check the expression to see if
 692          all of the variables that determine its value are
 693          read-only, but we don't bother.  */
 694       /* We may produce non-gimple trees by adding NOPs or introduce
 695          invalid sharing when operand is not really constant.
 696          It is not big deal to prohibit constant propagation here as
 697          we will constant propagate in DOM1 pass anyway.  */
 698       if (is_gimple_min_invariant (value)
 699           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p))
 700           /* We have to be very careful about ADDR_EXPR.  Make sure
 701              the base variable isn't a local variable of the inlined
 702              function, e.g., when doing recursive inlining, direct or
 703              mutually-recursive or whatever, which is why we don't
 704              just test whether fn == current_function_decl.  */
 705           && ! self_inlining_addr_expr (value, fn))
 706         {
 707           insert_decl_map (id, p, value);
 708           return;
 709         }
 710     }
 711
 712   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
 713      here since the type of this decl must be visible to the calling
 714      function.  */
 715   var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 716
 717   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 718      that way, when the PARM_DECL is encountered, it will be
 719      automatically replaced by the VAR_DECL.  */
 720   insert_decl_map (id, p, var);
 721
 722   /* Declare this new variable.  */
 723   TREE_CHAIN (var) = *vars;
 724   *vars = var;
 725
 726   /* Make gimplifier happy about this variable.  */
 727   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 728
 729   /* Even if P was TREE_READONLY, the new VAR should not be.
 730      In the original code, we would have constructed a
 731      temporary, and then the function body would have never
 732      changed the value of P.  However, now, we will be
 733      constructing VAR directly.  The constructor body may
 734      change its value multiple times as it is being
 735      constructed.  Therefore, it must not be TREE_READONLY;
 736      the back-end assumes that TREE_READONLY variable is
 737      assigned to only once.  */
 738   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 739     TREE_READONLY (var) = 0;
 740
 741   /* Initialize this VAR_DECL from the equivalent argument.  Convert
 742      the argument to the proper type in case it was promoted.  */
 743   if (value)
 744     {
 745       tree rhs = fold_convert (TREE_TYPE (var), value);
 746
 747       if (rhs == error_mark_node)
 748         return;
 749
 750       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
 751          keep our trees in gimple form.  */
 752       init_stmt = build (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
 753       append_to_statement_list (init_stmt, init_stmts);
 754
 755       /* If we did not create a gimple value and we did not create a gimple
 756          cast of a gimple value, then we will need to gimplify INIT_STMTS
 757          at the end.  Note that is_gimple_cast only checks the outer
 758          tree code, not its operand.  Thus the explicit check that it's
 759          operand is a gimple value.  */
 760       if (!is_gimple_val (rhs)
 761           && (!is_gimple_cast (rhs)
 762               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
 763         *gimplify_init_stmts_p = true;
 764     }
 765 }
 766
 767 /* Generate code to initialize the parameters of the function at the
 768    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 769
 770 static tree
 771 initialize_inlined_parameters (inline_data *id, tree args, tree static_chain,
 772                                tree fn, tree bind_expr)
 773 {
 774   tree init_stmts = NULL_TREE;
 775   tree parms;
 776   tree a;
 777   tree p;
 778   tree vars = NULL_TREE;
 779   bool gimplify_init_stmts_p = false;
 780   int argnum = 0;
 781
 782   /* Figure out what the parameters are.  */
 783   parms = DECL_ARGUMENTS (fn);
 784   if (fn == current_function_decl)
 785     parms = cfun->saved_args;
 786
 787   /* Loop through the parameter declarations, replacing each with an
 788      equivalent VAR_DECL, appropriately initialized.  */
 789   for (p = parms, a = args; p;
 790        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 791     {
 792       tree value;
 793
 794       ++argnum;
 795
 796       /* Find the initializer.  */
 797       value = lang_hooks.tree_inlining.convert_parm_for_inlining
 798               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
 799
 800       setup_one_parameter (id, p, value, fn, &init_stmts, &vars,
 801                            &gimplify_init_stmts_p);
 802     }
 803
 804   /* Evaluate trailing arguments.  */
 805   for (; a; a = TREE_CHAIN (a))
 806     {
 807       tree value = TREE_VALUE (a);
 808       append_to_statement_list (value, &init_stmts);
 809     }
 810
 811   /* Initialize the static chain.  */
 812   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
 813   if (fn == current_function_decl)
 814     p = DECL_STRUCT_FUNCTION (fn)->saved_static_chain_decl;
 815   if (p)
 816     {
 817       /* No static chain?  Seems like a bug in tree-nested.c.  */
 818       gcc_assert (static_chain);
 819
 820       setup_one_parameter (id, p, static_chain, fn, &init_stmts, &vars,
 821                            &gimplify_init_stmts_p);
 822     }
 823
 824   if (gimplify_init_stmts_p)
 825     gimplify_body (&init_stmts, current_function_decl, false);
 826
 827   declare_inline_vars (bind_expr, vars);
 828   return init_stmts;
 829 }
 830
 831 /* Declare a return variable to replace the RESULT_DECL for the function we
 832    are calling.  RETURN_SLOT_ADDR, if non-null, was a fake parameter that
 833    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
 834    the MODIFY_EXPR to which this call is the RHS.
 835
 836    The return value is a (possibly null) value that is the result of the
 837    function as seen by the callee.  *USE_P is a (possibly null) value that
 838    holds the result as seen by the caller.  */
 839
 840 static tree
 841 declare_return_variable (inline_data *id, tree return_slot_addr,
 842                          tree modify_dest, tree *use_p)
 843 {
 844   tree callee = VARRAY_TOP_TREE (id->fns);
 845   tree caller = VARRAY_TREE (id->fns, 0);
 846   tree result = DECL_RESULT (callee);
 847   tree callee_type = TREE_TYPE (result);
 848   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
 849   tree var, use;
 850
 851   /* We don't need to do anything for functions that don't return
 852      anything.  */
 853   if (!result || VOID_TYPE_P (callee_type))
 854     {
 855       *use_p = NULL_TREE;
 856       return NULL_TREE;
 857     }
 858
 859   /* If there was a return slot, then the return value is the
 860      dereferenced address of that object.  */
 861   if (return_slot_addr)
 862     {
 863       /* The front end shouldn't have used both return_slot_addr and
 864          a modify expression.  */
 865       gcc_assert (!modify_dest);
 866       if (DECL_BY_REFERENCE (result))
 867         var = return_slot_addr;
 868       else
 869         var = build_fold_indirect_ref (return_slot_addr);
 870       use = NULL;
 871       goto done;
 872     }
 873
 874   /* All types requiring non-trivial constructors should have been handled.  */
 875   gcc_assert (!TREE_ADDRESSABLE (callee_type));
 876
 877   /* Attempt to avoid creating a new temporary variable.  */
 878   if (modify_dest)
 879     {
 880       bool use_it = false;
 881
 882       /* We can't use MODIFY_DEST if there's type promotion involved.  */
 883       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
 884         use_it = false;
 885
 886       /* ??? If we're assigning to a variable sized type, then we must
 887          reuse the destination variable, because we've no good way to
 888          create variable sized temporaries at this point.  */
 889       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
 890         use_it = true;
 891
 892       /* If the callee cannot possibly modify MODIFY_DEST, then we can
 893          reuse it as the result of the call directly.  Don't do this if
 894          it would promote MODIFY_DEST to addressable.  */
 895       else if (!TREE_STATIC (modify_dest)
 896                && !TREE_ADDRESSABLE (modify_dest)
 897                && !TREE_ADDRESSABLE (result))
 898         use_it = true;
 899
 900       if (use_it)
 901         {
 902           var = modify_dest;
 903           use = NULL;
 904           goto done;
 905         }
 906     }
 907
 908   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
 909
 910   var = copy_decl_for_inlining (result, callee, caller);
 911   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 912   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
 913     = tree_cons (NULL_TREE, var,
 914                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
 915
 916   /* Do not have the rest of GCC warn about this variable as it should
 917      not be visible to the user.  */
 918   TREE_NO_WARNING (var) = 1;
 919
 920   /* Build the use expr.  If the return type of the function was
 921      promoted, convert it back to the expected type.  */
 922   use = var;
 923   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
 924     use = fold_convert (caller_type, var);
 925
 926  done:
 927   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 928      way, when the RESULT_DECL is encountered, it will be
 929      automatically replaced by the VAR_DECL.  */
 930   insert_decl_map (id, result, var);
 931
 932   /* Remember this so we can ignore it in remap_decls.  */
 933   id->retvar = var;
 934
 935   *use_p = use;
 936   return var;
 937 }
 938
 939 /* Returns nonzero if a function can be inlined as a tree.  */
 940
 941 bool
 942 tree_inlinable_function_p (tree fn)
 943 {
 944   return inlinable_function_p (fn);
 945 }
 946
 947 static const char *inline_forbidden_reason;
 948
 949 static tree
 950 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
 951                       void *fnp)
 952 {
 953   tree node = *nodep;
 954   tree fn = (tree) fnp;
 955   tree t;
 956
 957   switch (TREE_CODE (node))
 958     {
 959     case CALL_EXPR:
 960       /* Refuse to inline alloca call unless user explicitly forced so as
 961          this may change program's memory overhead drastically when the
 962          function using alloca is called in loop.  In GCC present in
 963          SPEC2000 inlining into schedule_block cause it to require 2GB of
 964          RAM instead of 256MB.  */
 965       if (alloca_call_p (node)
 966           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
 967         {
 968           inline_forbidden_reason
 969             = N_("%Jfunction %qF can never be inlined because it uses "
 970                  "alloca (override using the always_inline attribute)");
 971           return node;
 972         }
 973       t = get_callee_fndecl (node);
 974       if (! t)
 975         break;
 976
 977       /* We cannot inline functions that call setjmp.  */
 978       if (setjmp_call_p (t))
 979         {
 980           inline_forbidden_reason
 981             = N_("%Jfunction %qF can never be inlined because it uses setjmp");
 982           return node;
 983         }
 984
 985       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
 986         switch (DECL_FUNCTION_CODE (t))
 987           {
 988             /* We cannot inline functions that take a variable number of
 989                arguments.  */
 990           case BUILT_IN_VA_START:
 991           case BUILT_IN_STDARG_START:
 992           case BUILT_IN_NEXT_ARG:
 993           case BUILT_IN_VA_END:
 994             inline_forbidden_reason
 995               = N_("%Jfunction %qF can never be inlined because it "
 996                    "uses variable argument lists");
 997             return node;
 998
 999           case BUILT_IN_LONGJMP:
1000             /* We can't inline functions that call __builtin_longjmp at
1001                all.  The non-local goto machinery really requires the
1002                destination be in a different function.  If we allow the
1003                function calling __builtin_longjmp to be inlined into the
1004                function calling __builtin_setjmp, Things will Go Awry.  */
1005             inline_forbidden_reason
1006               = N_("%Jfunction %qF can never be inlined because "
1007                    "it uses setjmp-longjmp exception handling");
1008             return node;
1009
1010           case BUILT_IN_NONLOCAL_GOTO:
1011             /* Similarly.  */
1012             inline_forbidden_reason
1013               = N_("%Jfunction %qF can never be inlined because "
1014                    "it uses non-local goto");
1015             return node;
1016
1017           default:
1018             break;
1019           }
1020       break;
1021
1022     case GOTO_EXPR:
1023       t = TREE_OPERAND (node, 0);
1024
1025       /* We will not inline a function which uses computed goto.  The
1026          addresses of its local labels, which may be tucked into
1027          global storage, are of course not constant across
1028          instantiations, which causes unexpected behavior.  */
1029       if (TREE_CODE (t) != LABEL_DECL)
1030         {
1031           inline_forbidden_reason
1032             = N_("%Jfunction %qF can never be inlined "
1033                  "because it contains a computed goto");
1034           return node;
1035         }
1036       break;
1037
1038     case LABEL_EXPR:
1039       t = TREE_OPERAND (node, 0);
1040       if (DECL_NONLOCAL (t))
1041         {
1042           /* We cannot inline a function that receives a non-local goto
1043              because we cannot remap the destination label used in the
1044              function that is performing the non-local goto.  */
1045           inline_forbidden_reason
1046             = N_("%Jfunction %qF can never be inlined "
1047                  "because it receives a non-local goto");
1048           return node;
1049         }
1050       break;
1051
1052     case RECORD_TYPE:
1053     case UNION_TYPE:
1054       /* We cannot inline a function of the form
1055
1056            void F (int i) { struct S { int ar[i]; } s; }
1057
1058          Attempting to do so produces a catch-22.
1059          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1060          UNION_TYPE nodes, then it goes into infinite recursion on a
1061          structure containing a pointer to its own type.  If it doesn't,
1062          then the type node for S doesn't get adjusted properly when
1063          F is inlined, and we abort in find_function_data.
1064
1065          ??? This is likely no longer true, but it's too late in the 4.0
1066          cycle to try to find out.  This should be checked for 4.1.  */
1067       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1068         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1069           {
1070             inline_forbidden_reason
1071               = N_("%Jfunction %qF can never be inlined "
1072                    "because it uses variable sized variables");
1073             return node;
1074           }
1075
1076     default:
1077       break;
1078     }
1079
1080   return NULL_TREE;
1081 }
1082
1083 /* Return subexpression representing possible alloca call, if any.  */
1084 static tree
1085 inline_forbidden_p (tree fndecl)
1086 {
1087   location_t saved_loc = input_location;
1088   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1089                                            inline_forbidden_p_1, fndecl);
1090
1091   input_location = saved_loc;
1092   return ret;
1093 }
1094
1095 /* Returns nonzero if FN is a function that does not have any
1096    fundamental inline blocking properties.  */
1097
1098 static bool
1099 inlinable_function_p (tree fn)
1100 {
1101   bool inlinable = true;
1102
1103   /* If we've already decided this function shouldn't be inlined,
1104      there's no need to check again.  */
1105   if (DECL_UNINLINABLE (fn))
1106     return false;
1107
1108   /* See if there is any language-specific reason it cannot be
1109      inlined.  (It is important that this hook be called early because
1110      in C++ it may result in template instantiation.)
1111      If the function is not inlinable for language-specific reasons,
1112      it is left up to the langhook to explain why.  */
1113   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1114
1115   /* If we don't have the function body available, we can't inline it.
1116      However, this should not be recorded since we also get here for
1117      forward declared inline functions.  Therefore, return at once.  */
1118   if (!DECL_SAVED_TREE (fn))
1119     return false;
1120
1121   /* If we're not inlining at all, then we cannot inline this function.  */
1122   else if (!flag_inline_trees)
1123     inlinable = false;
1124
1125   /* Only try to inline functions if DECL_INLINE is set.  This should be
1126      true for all functions declared `inline', and for all other functions
1127      as well with -finline-functions.
1128
1129      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1130      it's the front-end that must set DECL_INLINE in this case, because
1131      dwarf2out loses if a function that does not have DECL_INLINE set is
1132      inlined anyway.  That is why we have both DECL_INLINE and
1133      DECL_DECLARED_INLINE_P.  */
1134   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1135             here should be redundant.  */
1136   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1137     inlinable = false;
1138
1139   else if (inline_forbidden_p (fn))
1140     {
1141       /* See if we should warn about uninlinable functions.  Previously,
1142          some of these warnings would be issued while trying to expand
1143          the function inline, but that would cause multiple warnings
1144          about functions that would for example call alloca.  But since
1145          this a property of the function, just one warning is enough.
1146          As a bonus we can now give more details about the reason why a
1147          function is not inlinable.
1148          We only warn for functions declared `inline' by the user.  */
1149       bool do_warning = (warn_inline
1150                          && DECL_INLINE (fn)
1151                          && DECL_DECLARED_INLINE_P (fn)
1152                          && !DECL_IN_SYSTEM_HEADER (fn));
1153
1154       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1155         sorry (inline_forbidden_reason, fn, fn);
1156       else if (do_warning)
1157         warning (inline_forbidden_reason, fn, fn);
1158
1159       inlinable = false;
1160     }
1161
1162   /* Squirrel away the result so that we don't have to check again.  */
1163   DECL_UNINLINABLE (fn) = !inlinable;
1164
1165   return inlinable;
1166 }
1167
1168 /* Used by estimate_num_insns.  Estimate number of instructions seen
1169    by given statement.  */
1170
1171 static tree
1172 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1173 {
1174   int *count = data;
1175   tree x = *tp;
1176
1177   if (IS_TYPE_OR_DECL_P (x))
1178     {
1179       *walk_subtrees = 0;
1180       return NULL;
1181     }
1182   /* Assume that constants and references counts nothing.  These should
1183      be majorized by amount of operations among them we count later
1184      and are common target of CSE and similar optimizations.  */
1185   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1186     return NULL;
1187
1188   switch (TREE_CODE (x))
1189     {
1190     /* Containers have no cost.  */
1191     case TREE_LIST:
1192     case TREE_VEC:
1193     case BLOCK:
1194     case COMPONENT_REF:
1195     case BIT_FIELD_REF:
1196     case INDIRECT_REF:
1197     case ALIGN_INDIRECT_REF:
1198     case MISALIGNED_INDIRECT_REF:
1199     case ARRAY_REF:
1200     case ARRAY_RANGE_REF:
1201     case OBJ_TYPE_REF:
1202     case EXC_PTR_EXPR: /* ??? */
1203     case FILTER_EXPR: /* ??? */
1204     case COMPOUND_EXPR:
1205     case BIND_EXPR:
1206     case WITH_CLEANUP_EXPR:
1207     case NOP_EXPR:
1208     case VIEW_CONVERT_EXPR:
1209     case SAVE_EXPR:
1210     case ADDR_EXPR:
1211     case COMPLEX_EXPR:
1212     case RANGE_EXPR:
1213     case CASE_LABEL_EXPR:
1214     case SSA_NAME:
1215     case CATCH_EXPR:
1216     case EH_FILTER_EXPR:
1217     case STATEMENT_LIST:
1218     case ERROR_MARK:
1219     case NON_LVALUE_EXPR:
1220     case FDESC_EXPR:
1221     case VA_ARG_EXPR:
1222     case TRY_CATCH_EXPR:
1223     case TRY_FINALLY_EXPR:
1224     case LABEL_EXPR:
1225     case GOTO_EXPR:
1226     case RETURN_EXPR:
1227     case EXIT_EXPR:
1228     case LOOP_EXPR:
1229     case PHI_NODE:
1230     case WITH_SIZE_EXPR:
1231       break;
1232
1233     /* We don't account constants for now.  Assume that the cost is amortized
1234        by operations that do use them.  We may re-consider this decision once
1235        we are able to optimize the tree before estimating it's size and break
1236        out static initializers.  */
1237     case IDENTIFIER_NODE:
1238     case INTEGER_CST:
1239     case REAL_CST:
1240     case COMPLEX_CST:
1241     case VECTOR_CST:
1242     case STRING_CST:
1243       *walk_subtrees = 0;
1244       return NULL;
1245
1246     /* Recognize assignments of large structures and constructors of
1247        big arrays.  */
1248     case INIT_EXPR:
1249     case MODIFY_EXPR:
1250       x = TREE_OPERAND (x, 0);
1251       /* FALLTHRU */
1252     case TARGET_EXPR:
1253     case CONSTRUCTOR:
1254       {
1255         HOST_WIDE_INT size;
1256
1257         size = int_size_in_bytes (TREE_TYPE (x));
1258
1259         if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1260           *count += 10;
1261         else
1262           *count += ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1263       }
1264       break;
1265
1266       /* Assign cost of 1 to usual operations.
1267          ??? We may consider mapping RTL costs to this.  */
1268     case COND_EXPR:
1269
1270     case PLUS_EXPR:
1271     case MINUS_EXPR:
1272     case MULT_EXPR:
1273
1274     case FIX_TRUNC_EXPR:
1275     case FIX_CEIL_EXPR:
1276     case FIX_FLOOR_EXPR:
1277     case FIX_ROUND_EXPR:
1278
1279     case NEGATE_EXPR:
1280     case FLOAT_EXPR:
1281     case MIN_EXPR:
1282     case MAX_EXPR:
1283     case ABS_EXPR:
1284
1285     case LSHIFT_EXPR:
1286     case RSHIFT_EXPR:
1287     case LROTATE_EXPR:
1288     case RROTATE_EXPR:
1289
1290     case BIT_IOR_EXPR:
1291     case BIT_XOR_EXPR:
1292     case BIT_AND_EXPR:
1293     case BIT_NOT_EXPR:
1294
1295     case TRUTH_ANDIF_EXPR:
1296     case TRUTH_ORIF_EXPR:
1297     case TRUTH_AND_EXPR:
1298     case TRUTH_OR_EXPR:
1299     case TRUTH_XOR_EXPR:
1300     case TRUTH_NOT_EXPR:
1301
1302     case LT_EXPR:
1303     case LE_EXPR:
1304     case GT_EXPR:
1305     case GE_EXPR:
1306     case EQ_EXPR:
1307     case NE_EXPR:
1308     case ORDERED_EXPR:
1309     case UNORDERED_EXPR:
1310
1311     case UNLT_EXPR:
1312     case UNLE_EXPR:
1313     case UNGT_EXPR:
1314     case UNGE_EXPR:
1315     case UNEQ_EXPR:
1316     case LTGT_EXPR:
1317
1318     case CONVERT_EXPR:
1319
1320     case CONJ_EXPR:
1321
1322     case PREDECREMENT_EXPR:
1323     case PREINCREMENT_EXPR:
1324     case POSTDECREMENT_EXPR:
1325     case POSTINCREMENT_EXPR:
1326
1327     case SWITCH_EXPR:
1328
1329     case ASM_EXPR:
1330
1331     case REALIGN_LOAD_EXPR:
1332
1333     case RESX_EXPR:
1334       *count += 1;
1335       break;
1336
1337     /* Few special cases of expensive operations.  This is useful
1338        to avoid inlining on functions having too many of these.  */
1339     case TRUNC_DIV_EXPR:
1340     case CEIL_DIV_EXPR:
1341     case FLOOR_DIV_EXPR:
1342     case ROUND_DIV_EXPR:
1343     case EXACT_DIV_EXPR:
1344     case TRUNC_MOD_EXPR:
1345     case CEIL_MOD_EXPR:
1346     case FLOOR_MOD_EXPR:
1347     case ROUND_MOD_EXPR:
1348     case RDIV_EXPR:
1349       *count += 10;
1350       break;
1351     case CALL_EXPR:
1352       {
1353         tree decl = get_callee_fndecl (x);
1354
1355         if (decl && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1356           switch (DECL_FUNCTION_CODE (decl))
1357             {
1358             case BUILT_IN_CONSTANT_P:
1359               *walk_subtrees = 0;
1360               return NULL_TREE;
1361             case BUILT_IN_EXPECT:
1362               return NULL_TREE;
1363             default:
1364               break;
1365             }
1366         *count += 10;
1367         break;
1368       }
1369     default:
1370       /* Abort here se we know we don't miss any nodes.  */
1371       gcc_unreachable ();
1372     }
1373   return NULL;
1374 }
1375
1376 /* Estimate number of instructions that will be created by expanding EXPR.  */
1377
1378 int
1379 estimate_num_insns (tree expr)
1380 {
1381   int num = 0;
1382   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1383   return num;
1384 }
1385
1386 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1387
1388 static tree
1389 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1390 {
1391   inline_data *id;
1392   tree t;
1393   tree expr;
1394   tree stmt;
1395   tree use_retvar;
1396   tree decl;
1397   tree fn;
1398   tree arg_inits;
1399   tree *inlined_body;
1400   splay_tree st;
1401   tree args;
1402   tree return_slot_addr;
1403   tree modify_dest;
1404   location_t saved_location;
1405   struct cgraph_edge *edge;
1406   const char *reason;
1407
1408   /* See what we've got.  */
1409   id = (inline_data *) data;
1410   t = *tp;
1411
1412   /* Set input_location here so we get the right instantiation context
1413      if we call instantiate_decl from inlinable_function_p.  */
1414   saved_location = input_location;
1415   if (EXPR_HAS_LOCATION (t))
1416     input_location = EXPR_LOCATION (t);
1417
1418   /* Recurse, but letting recursive invocations know that we are
1419      inside the body of a TARGET_EXPR.  */
1420   if (TREE_CODE (*tp) == TARGET_EXPR)
1421     {
1422 #if 0
1423       int i, len = TREE_CODE_LENGTH (TARGET_EXPR);
1424
1425       /* We're walking our own subtrees.  */
1426       *walk_subtrees = 0;
1427
1428       /* Actually walk over them.  This loop is the body of
1429          walk_trees, omitting the case where the TARGET_EXPR
1430          itself is handled.  */
1431       for (i = 0; i < len; ++i)
1432         {
1433           if (i == 2)
1434             ++id->in_target_cleanup_p;
1435           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1436                      id->tree_pruner);
1437           if (i == 2)
1438             --id->in_target_cleanup_p;
1439         }
1440
1441       goto egress;
1442 #endif
1443     }
1444
1445   if (TYPE_P (t))
1446     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1447        them should not be expanded.  This can happen if the type is a
1448        dynamic array type, for example.  */
1449     *walk_subtrees = 0;
1450
1451   /* From here on, we're only interested in CALL_EXPRs.  */
1452   if (TREE_CODE (t) != CALL_EXPR)
1453     goto egress;
1454
1455   /* First, see if we can figure out what function is being called.
1456      If we cannot, then there is no hope of inlining the function.  */
1457   fn = get_callee_fndecl (t);
1458   if (!fn)
1459     goto egress;
1460
1461   /* Turn forward declarations into real ones.  */
1462   fn = cgraph_node (fn)->decl;
1463
1464   /* If fn is a declaration of a function in a nested scope that was
1465      globally declared inline, we don't set its DECL_INITIAL.
1466      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1467      C++ front-end uses it for cdtors to refer to their internal
1468      declarations, that are not real functions.  Fortunately those
1469      don't have trees to be saved, so we can tell by checking their
1470      DECL_SAVED_TREE.  */
1471   if (! DECL_INITIAL (fn)
1472       && DECL_ABSTRACT_ORIGIN (fn)
1473       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1474     fn = DECL_ABSTRACT_ORIGIN (fn);
1475
1476   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1477      Kill this check once this is fixed.  */
1478   if (!id->current_node->analyzed)
1479     goto egress;
1480
1481   edge = cgraph_edge (id->current_node, t);
1482
1483   /* Constant propagation on argument done during previous inlining
1484      may create new direct call.  Produce an edge for it.  */
1485   if (!edge)
1486     {
1487       struct cgraph_node *dest = cgraph_node (fn);
1488
1489       /* We have missing edge in the callgraph.  This can happen in one case
1490          where previous inlining turned indirect call into direct call by
1491          constant propagating arguments.  In all other cases we hit a bug
1492          (incorrect node sharing is most common reason for missing edges.  */
1493       gcc_assert (dest->needed || !flag_unit_at_a_time);
1494       cgraph_create_edge (id->node, dest, t)->inline_failed
1495         = N_("originally indirect function call not considered for inlining");
1496       goto egress;
1497     }
1498
1499   /* Don't try to inline functions that are not well-suited to
1500      inlining.  */
1501   if (!cgraph_inline_p (edge, &reason))
1502     {
1503       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1504         {
1505           sorry ("%Jinlining failed in call to %qF: %s", fn, fn, reason);
1506           sorry ("called from here");
1507         }
1508       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1509                && !DECL_IN_SYSTEM_HEADER (fn)
1510                && strlen (reason)
1511                && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn)))
1512         {
1513           warning ("%Jinlining failed in call to %qF: %s", fn, fn, reason);
1514           warning ("called from here");
1515         }
1516       goto egress;
1517     }
1518
1519 #ifdef ENABLE_CHECKING
1520   if (edge->callee->decl != id->node->decl)
1521     verify_cgraph_node (edge->callee);
1522 #endif
1523
1524   if (! lang_hooks.tree_inlining.start_inlining (fn))
1525     goto egress;
1526
1527   /* Build a block containing code to initialize the arguments, the
1528      actual inline expansion of the body, and a label for the return
1529      statements within the function to jump to.  The type of the
1530      statement expression is the return type of the function call.  */
1531   stmt = NULL;
1532   expr = build (BIND_EXPR, void_type_node, NULL_TREE,
1533                 stmt, make_node (BLOCK));
1534   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1535
1536   /* Local declarations will be replaced by their equivalents in this
1537      map.  */
1538   st = id->decl_map;
1539   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1540                                  NULL, NULL);
1541
1542   /* Initialize the parameters.  */
1543   args = TREE_OPERAND (t, 1);
1544   return_slot_addr = NULL_TREE;
1545   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1546     {
1547       return_slot_addr = TREE_VALUE (args);
1548       args = TREE_CHAIN (args);
1549       TREE_TYPE (expr) = void_type_node;
1550     }
1551
1552   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1553                                              fn, expr);
1554   if (arg_inits)
1555     {
1556       /* Expand any inlined calls in the initializers.  Do this before we
1557          push FN on the stack of functions we are inlining; we want to
1558          inline calls to FN that appear in the initializers for the
1559          parameters.
1560
1561          Note we need to save and restore the saved tree statement iterator
1562          to avoid having it clobbered by expand_calls_inline.  */
1563       tree_stmt_iterator save_tsi;
1564
1565       save_tsi = id->tsi;
1566       expand_calls_inline (&arg_inits, id);
1567       id->tsi = save_tsi;
1568
1569       /* And add them to the tree.  */
1570       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1571     }
1572
1573   /* Record the function we are about to inline so that we can avoid
1574      recursing into it.  */
1575   VARRAY_PUSH_TREE (id->fns, fn);
1576
1577   /* Return statements in the function body will be replaced by jumps
1578      to the RET_LABEL.  */
1579   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1580   DECL_ARTIFICIAL (id->ret_label) = 1;
1581   DECL_IGNORED_P (id->ret_label) = 1;
1582   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1583   insert_decl_map (id, id->ret_label, id->ret_label);
1584
1585   gcc_assert (DECL_INITIAL (fn));
1586   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
1587
1588   /* Find the lhs to which the result of this call is assigned.  */
1589   modify_dest = tsi_stmt (id->tsi);
1590   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1591     {
1592       modify_dest = TREE_OPERAND (modify_dest, 0);
1593
1594       /* The function which we are inlining might not return a value,
1595          in which case we should issue a warning that the function
1596          does not return a value.  In that case the optimizers will
1597          see that the variable to which the value is assigned was not
1598          initialized.  We do not want to issue a warning about that
1599          uninitialized variable.  */
1600       if (DECL_P (modify_dest))
1601         TREE_NO_WARNING (modify_dest) = 1;
1602     }
1603   else
1604     modify_dest = NULL;
1605
1606   /* Declare the return variable for the function.  */
1607   decl = declare_return_variable (id, return_slot_addr,
1608                                   modify_dest, &use_retvar);
1609
1610   /* After we've initialized the parameters, we insert the body of the
1611      function itself.  */
1612   {
1613     struct cgraph_node *old_node = id->current_node;
1614     tree copy;
1615
1616     id->current_node = edge->callee;
1617     copy = copy_body (id);
1618
1619     if (warn_return_type
1620         && !TREE_NO_WARNING (fn)
1621         && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn)))
1622         && block_may_fallthru (copy))
1623       {
1624         warning ("control may reach end of non-void function %qD being inlined",
1625                  fn);
1626         TREE_NO_WARNING (fn) = 1;
1627       }
1628
1629     append_to_statement_list (copy, &BIND_EXPR_BODY (expr));
1630     id->current_node = old_node;
1631   }
1632   inlined_body = &BIND_EXPR_BODY (expr);
1633
1634   /* After the body of the function comes the RET_LABEL.  This must come
1635      before we evaluate the returned value below, because that evaluation
1636      may cause RTL to be generated.  */
1637   if (TREE_USED (id->ret_label))
1638     {
1639       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1640       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1641     }
1642
1643   /* Clean up.  */
1644   splay_tree_delete (id->decl_map);
1645   id->decl_map = st;
1646
1647   /* Although, from the semantic viewpoint, the new expression has
1648      side-effects only if the old one did, it is not possible, from
1649      the technical viewpoint, to evaluate the body of a function
1650      multiple times without serious havoc.  */
1651   TREE_SIDE_EFFECTS (expr) = 1;
1652
1653   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1654
1655   /* If the inlined function returns a result that we care about,
1656      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1657      the call was a standalone statement and we can just replace it
1658      with the BIND_EXPR inline representation of the called function.  */
1659   if (!use_retvar || !modify_dest)
1660     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1661   else
1662     *tp = use_retvar;
1663
1664   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1665      the call if it is to a "const" function.  Thus the copy of
1666      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1667      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1668      "const" function.
1669
1670      Unfortunately, that is wrong as inlining the function can create/expose
1671      interesting side effects (such as setting of a return value).
1672
1673      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1674      the toplevel expression.  */
1675   recalculate_side_effects (expr);
1676
1677   /* Output the inlining info for this abstract function, since it has been
1678      inlined.  If we don't do this now, we can lose the information about the
1679      variables in the function when the blocks get blown away as soon as we
1680      remove the cgraph node.  */
1681   (*debug_hooks->outlining_inline_function) (edge->callee->decl);
1682
1683   /* Update callgraph if needed.  */
1684   cgraph_remove_node (edge->callee);
1685
1686   /* Recurse into the body of the just inlined function.  */
1687   expand_calls_inline (inlined_body, id);
1688   VARRAY_POP (id->fns);
1689
1690   /* Don't walk into subtrees.  We've already handled them above.  */
1691   *walk_subtrees = 0;
1692
1693   lang_hooks.tree_inlining.end_inlining (fn);
1694
1695   /* Keep iterating.  */
1696  egress:
1697   input_location = saved_location;
1698   return NULL_TREE;
1699 }
1700
1701 static void
1702 expand_calls_inline (tree *stmt_p, inline_data *id)
1703 {
1704   tree stmt = *stmt_p;
1705   enum tree_code code = TREE_CODE (stmt);
1706   int dummy;
1707
1708   switch (code)
1709     {
1710     case STATEMENT_LIST:
1711       {
1712         tree_stmt_iterator i;
1713         tree new;
1714
1715         for (i = tsi_start (stmt); !tsi_end_p (i); )
1716           {
1717             id->tsi = i;
1718             expand_calls_inline (tsi_stmt_ptr (i), id);
1719
1720             new = tsi_stmt (i);
1721             if (TREE_CODE (new) == STATEMENT_LIST)
1722               {
1723                 tsi_link_before (&i, new, TSI_SAME_STMT);
1724                 tsi_delink (&i);
1725               }
1726             else
1727               tsi_next (&i);
1728           }
1729       }
1730       break;
1731
1732     case COND_EXPR:
1733       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1734       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1735       break;
1736
1737     case CATCH_EXPR:
1738       expand_calls_inline (&CATCH_BODY (stmt), id);
1739       break;
1740
1741     case EH_FILTER_EXPR:
1742       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1743       break;
1744
1745     case TRY_CATCH_EXPR:
1746     case TRY_FINALLY_EXPR:
1747       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1748       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1749       break;
1750
1751     case BIND_EXPR:
1752       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1753       break;
1754
1755     case COMPOUND_EXPR:
1756       /* We're gimple.  We should have gotten rid of all these.  */
1757       gcc_unreachable ();
1758
1759     case RETURN_EXPR:
1760       stmt_p = &TREE_OPERAND (stmt, 0);
1761       stmt = *stmt_p;
1762       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1763         break;
1764
1765       /* FALLTHRU */
1766
1767     case MODIFY_EXPR:
1768       stmt_p = &TREE_OPERAND (stmt, 1);
1769       stmt = *stmt_p;
1770       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1771         {
1772           stmt_p = &TREE_OPERAND (stmt, 0);
1773           stmt = *stmt_p;
1774         }
1775       if (TREE_CODE (stmt) != CALL_EXPR)
1776         break;
1777
1778       /* FALLTHRU */
1779
1780     case CALL_EXPR:
1781       expand_call_inline (stmt_p, &dummy, id);
1782       break;
1783
1784     default:
1785       break;
1786     }
1787 }
1788
1789 /* Expand calls to inline functions in the body of FN.  */
1790
1791 void
1792 optimize_inline_calls (tree fn)
1793 {
1794   inline_data id;
1795   tree prev_fn;
1796
1797   /* There is no point in performing inlining if errors have already
1798      occurred -- and we might crash if we try to inline invalid
1799      code.  */
1800   if (errorcount || sorrycount)
1801     return;
1802
1803   /* Clear out ID.  */
1804   memset (&id, 0, sizeof (id));
1805
1806   id.current_node = id.node = cgraph_node (fn);
1807   /* Don't allow recursion into FN.  */
1808   VARRAY_TREE_INIT (id.fns, 32, "fns");
1809   VARRAY_PUSH_TREE (id.fns, fn);
1810   /* Or any functions that aren't finished yet.  */
1811   prev_fn = NULL_TREE;
1812   if (current_function_decl)
1813     {
1814       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1815       prev_fn = current_function_decl;
1816     }
1817
1818   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1819
1820   /* Keep track of the low-water mark, i.e., the point where the first
1821      real inlining is represented in ID.FNS.  */
1822   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1823
1824   /* Replace all calls to inline functions with the bodies of those
1825      functions.  */
1826   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1827   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1828
1829   /* Clean up.  */
1830   htab_delete (id.tree_pruner);
1831
1832 #ifdef ENABLE_CHECKING
1833     {
1834       struct cgraph_edge *e;
1835
1836       verify_cgraph_node (id.node);
1837
1838       /* Double check that we inlined everything we are supposed to inline.  */
1839       for (e = id.node->callees; e; e = e->next_callee)
1840         gcc_assert (e->inline_failed);
1841     }
1842 #endif
1843 }
1844
1845 /* FN is a function that has a complete body, and CLONE is a function whose
1846    body is to be set to a copy of FN, mapping argument declarations according
1847    to the ARG_MAP splay_tree.  */
1848
1849 void
1850 clone_body (tree clone, tree fn, void *arg_map)
1851 {
1852   inline_data id;
1853
1854   /* Clone the body, as if we were making an inline call.  But, remap the
1855      parameters in the callee to the parameters of caller.  If there's an
1856      in-charge parameter, map it to an appropriate constant.  */
1857   memset (&id, 0, sizeof (id));
1858   VARRAY_TREE_INIT (id.fns, 2, "fns");
1859   VARRAY_PUSH_TREE (id.fns, clone);
1860   VARRAY_PUSH_TREE (id.fns, fn);
1861   id.decl_map = (splay_tree)arg_map;
1862
1863   /* Cloning is treated slightly differently from inlining.  Set
1864      CLONING_P so that it's clear which operation we're performing.  */
1865   id.cloning_p = true;
1866
1867   /* Actually copy the body.  */
1868   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1869 }
1870
1871 /* Make and return duplicate of body in FN.  Put copies of DECL_ARGUMENTS
1872    in *arg_copy and of the static chain, if any, in *sc_copy.  */
1873
1874 tree
1875 save_body (tree fn, tree *arg_copy, tree *sc_copy)
1876 {
1877   inline_data id;
1878   tree body, *parg;
1879
1880   memset (&id, 0, sizeof (id));
1881   VARRAY_TREE_INIT (id.fns, 1, "fns");
1882   VARRAY_PUSH_TREE (id.fns, fn);
1883   id.node = cgraph_node (fn);
1884   id.saving_p = true;
1885   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1886   *arg_copy = DECL_ARGUMENTS (fn);
1887
1888   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1889     {
1890       tree new = copy_node (*parg);
1891
1892       lang_hooks.dup_lang_specific_decl (new);
1893       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1894       insert_decl_map (&id, *parg, new);
1895       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1896       *parg = new;
1897     }
1898
1899   *sc_copy = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1900   if (*sc_copy)
1901     {
1902       tree new = copy_node (*sc_copy);
1903
1904       lang_hooks.dup_lang_specific_decl (new);
1905       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*sc_copy);
1906       insert_decl_map (&id, *sc_copy, new);
1907       TREE_CHAIN (new) = TREE_CHAIN (*sc_copy);
1908       *sc_copy = new;
1909     }
1910
1911   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1912
1913   /* Actually copy the body.  */
1914   body = copy_body (&id);
1915
1916   /* Clean up.  */
1917   splay_tree_delete (id.decl_map);
1918   return body;
1919 }
1920
1921 #define WALK_SUBTREE(NODE)                              \
1922   do                                                    \
1923     {                                                   \
1924       result = walk_tree (&(NODE), func, data, pset);   \
1925       if (result)                                       \
1926         return result;                                  \
1927     }                                                   \
1928   while (0)
1929
1930 /* This is a subroutine of walk_tree that walks field of TYPE that are to
1931    be walked whenever a type is seen in the tree.  Rest of operands and return
1932    value are as for walk_tree.  */
1933
1934 static tree
1935 walk_type_fields (tree type, walk_tree_fn func, void *data,
1936                   struct pointer_set_t *pset)
1937 {
1938   tree result = NULL_TREE;
1939
1940   switch (TREE_CODE (type))
1941     {
1942     case POINTER_TYPE:
1943     case REFERENCE_TYPE:
1944       /* We have to worry about mutually recursive pointers.  These can't
1945          be written in C.  They can in Ada.  It's pathological, but
1946          there's an ACATS test (c38102a) that checks it.  Deal with this
1947          by checking if we're pointing to another pointer, that one
1948          points to another pointer, that one does too, and we have no htab.
1949          If so, get a hash table.  We check three levels deep to avoid
1950          the cost of the hash table if we don't need one.  */
1951       if (POINTER_TYPE_P (TREE_TYPE (type))
1952           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
1953           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
1954           && !pset)
1955         {
1956           result = walk_tree_without_duplicates (&TREE_TYPE (type),
1957                                                  func, data);
1958           if (result)
1959             return result;
1960
1961           break;
1962         }
1963
1964       /* ... fall through ... */
1965
1966     case COMPLEX_TYPE:
1967       WALK_SUBTREE (TREE_TYPE (type));
1968       break;
1969
1970     case METHOD_TYPE:
1971       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
1972
1973       /* Fall through.  */
1974
1975     case FUNCTION_TYPE:
1976       WALK_SUBTREE (TREE_TYPE (type));
1977       {
1978         tree arg;
1979
1980         /* We never want to walk into default arguments.  */
1981         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
1982           WALK_SUBTREE (TREE_VALUE (arg));
1983       }
1984       break;
1985
1986     case ARRAY_TYPE:
1987       /* Don't follow this nodes's type if a pointer for fear that we'll
1988          have infinite recursion.  Those types are uninteresting anyway.  */
1989       if (!POINTER_TYPE_P (TREE_TYPE (type))
1990           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
1991         WALK_SUBTREE (TREE_TYPE (type));
1992       WALK_SUBTREE (TYPE_DOMAIN (type));
1993       break;
1994
1995     case BOOLEAN_TYPE:
1996     case ENUMERAL_TYPE:
1997     case INTEGER_TYPE:
1998     case CHAR_TYPE:
1999     case REAL_TYPE:
2000       WALK_SUBTREE (TYPE_MIN_VALUE (type));
2001       WALK_SUBTREE (TYPE_MAX_VALUE (type));
2002       break;
2003
2004     case OFFSET_TYPE:
2005       WALK_SUBTREE (TREE_TYPE (type));
2006       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
2007       break;
2008
2009     default:
2010       break;
2011     }
2012
2013   return NULL_TREE;
2014 }
2015
2016 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
2017    called with the DATA and the address of each sub-tree.  If FUNC returns a
2018    non-NULL value, the traversal is aborted, and the value returned by FUNC
2019    is returned.  If PSET is non-NULL it is used to record the nodes visited,
2020    and to avoid visiting a node more than once.  */
2021
2022 tree
2023 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
2024 {
2025   enum tree_code code;
2026   int walk_subtrees;
2027   tree result;
2028
2029 #define WALK_SUBTREE_TAIL(NODE)                         \
2030   do                                                    \
2031     {                                                   \
2032        tp = & (NODE);                                   \
2033        goto tail_recurse;                               \
2034     }                                                   \
2035   while (0)
2036
2037  tail_recurse:
2038   /* Skip empty subtrees.  */
2039   if (!*tp)
2040     return NULL_TREE;
2041
2042   /* Don't walk the same tree twice, if the user has requested
2043      that we avoid doing so.  */
2044   if (pset && pointer_set_insert (pset, *tp))
2045     return NULL_TREE;
2046
2047   /* Call the function.  */
2048   walk_subtrees = 1;
2049   result = (*func) (tp, &walk_subtrees, data);
2050
2051   /* If we found something, return it.  */
2052   if (result)
2053     return result;
2054
2055   code = TREE_CODE (*tp);
2056
2057   /* Even if we didn't, FUNC may have decided that there was nothing
2058      interesting below this point in the tree.  */
2059   if (!walk_subtrees)
2060     {
2061       if (code == TREE_LIST)
2062         /* But we still need to check our siblings.  */
2063         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2064       else
2065         return NULL_TREE;
2066     }
2067
2068   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2069                                                    data, pset);
2070   if (result || ! walk_subtrees)
2071     return result;
2072
2073   /* If this is a DECL_EXPR, walk into various fields of the type that it's
2074      defining.  We only want to walk into these fields of a type in this
2075      case.  Note that decls get walked as part of the processing of a
2076      BIND_EXPR.
2077
2078      ??? Precisely which fields of types that we are supposed to walk in
2079      this case vs. the normal case aren't well defined.  */
2080   if (code == DECL_EXPR
2081       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
2082       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
2083     {
2084       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
2085
2086       /* Call the function for the type.  See if it returns anything or
2087          doesn't want us to continue.  If we are to continue, walk both
2088          the normal fields and those for the declaration case.  */
2089       result = (*func) (type_p, &walk_subtrees, data);
2090       if (result || !walk_subtrees)
2091         return NULL_TREE;
2092
2093       result = walk_type_fields (*type_p, func, data, pset);
2094       if (result)
2095         return result;
2096
2097       WALK_SUBTREE (TYPE_SIZE (*type_p));
2098       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
2099
2100       /* If this is a record type, also walk the fields.  */
2101       if (TREE_CODE (*type_p) == RECORD_TYPE
2102           || TREE_CODE (*type_p) == UNION_TYPE
2103           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2104         {
2105           tree field;
2106
2107           for (field = TYPE_FIELDS (*type_p); field;
2108                field = TREE_CHAIN (field))
2109             {
2110               /* We'd like to look at the type of the field, but we can easily
2111                  get infinite recursion.  So assume it's pointed to elsewhere
2112                  in the tree.  Also, ignore things that aren't fields.  */
2113               if (TREE_CODE (field) != FIELD_DECL)
2114                 continue;
2115
2116               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
2117               WALK_SUBTREE (DECL_SIZE (field));
2118               WALK_SUBTREE (DECL_SIZE_UNIT (field));
2119               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2120                 WALK_SUBTREE (DECL_QUALIFIER (field));
2121             }
2122         }
2123     }
2124
2125   else if (code != SAVE_EXPR
2126            && code != BIND_EXPR
2127            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2128     {
2129       int i, len;
2130
2131       /* Walk over all the sub-trees of this operand.  */
2132       len = TREE_CODE_LENGTH (code);
2133       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2134          But, we only want to walk once.  */
2135       if (code == TARGET_EXPR
2136           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2137         --len;
2138
2139       /* Go through the subtrees.  We need to do this in forward order so
2140          that the scope of a FOR_EXPR is handled properly.  */
2141 #ifdef DEBUG_WALK_TREE
2142       for (i = 0; i < len; ++i)
2143         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2144 #else
2145       for (i = 0; i < len - 1; ++i)
2146         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2147
2148       if (len)
2149         {
2150           /* The common case is that we may tail recurse here.  */
2151           if (code != BIND_EXPR
2152               && !TREE_CHAIN (*tp))
2153             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
2154           else
2155             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
2156         }
2157 #endif
2158     }
2159
2160   /* If this is a type, walk the needed fields in the type.  */
2161   else if (TYPE_P (*tp))
2162     {
2163       result = walk_type_fields (*tp, func, data, pset);
2164       if (result)
2165         return result;
2166     }
2167   else
2168     {
2169       /* Not one of the easy cases.  We must explicitly go through the
2170          children.  */
2171       switch (code)
2172         {
2173         case ERROR_MARK:
2174         case IDENTIFIER_NODE:
2175         case INTEGER_CST:
2176         case REAL_CST:
2177         case VECTOR_CST:
2178         case STRING_CST:
2179         case BLOCK:
2180         case PLACEHOLDER_EXPR:
2181         case SSA_NAME:
2182         case FIELD_DECL:
2183         case RESULT_DECL:
2184           /* None of thse have subtrees other than those already walked
2185              above.  */
2186           break;
2187
2188         case TREE_LIST:
2189           WALK_SUBTREE (TREE_VALUE (*tp));
2190           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2191           break;
2192
2193         case TREE_VEC:
2194           {
2195             int len = TREE_VEC_LENGTH (*tp);
2196
2197             if (len == 0)
2198               break;
2199
2200             /* Walk all elements but the first.  */
2201             while (--len)
2202               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2203
2204             /* Now walk the first one as a tail call.  */
2205             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2206           }
2207
2208         case COMPLEX_CST:
2209           WALK_SUBTREE (TREE_REALPART (*tp));
2210           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2211
2212         case CONSTRUCTOR:
2213           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2214
2215         case SAVE_EXPR:
2216           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2217
2218         case BIND_EXPR:
2219           {
2220             tree decl;
2221             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2222               {
2223                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2224                    into declarations that are just mentioned, rather than
2225                    declared; they don't really belong to this part of the tree.
2226                    And, we can see cycles: the initializer for a declaration
2227                    can refer to the declaration itself.  */
2228                 WALK_SUBTREE (DECL_INITIAL (decl));
2229                 WALK_SUBTREE (DECL_SIZE (decl));
2230                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2231               }
2232             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2233           }
2234
2235         case STATEMENT_LIST:
2236           {
2237             tree_stmt_iterator i;
2238             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2239               WALK_SUBTREE (*tsi_stmt_ptr (i));
2240           }
2241           break;
2242
2243         default:
2244           /* ??? This could be a language-defined node.  We really should make
2245              a hook for it, but right now just ignore it.  */
2246           break;
2247         }
2248     }
2249
2250   /* We didn't find what we were looking for.  */
2251   return NULL_TREE;
2252
2253 #undef WALK_SUBTREE
2254 #undef WALK_SUBTREE_TAIL
2255 }
2256
2257 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
2258
2259 tree
2260 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2261 {
2262   tree result;
2263   struct pointer_set_t *pset;
2264
2265   pset = pointer_set_create ();
2266   result = walk_tree (tp, func, data, pset);
2267   pointer_set_destroy (pset);
2268   return result;
2269 }
2270
2271 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2272
2273 tree
2274 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2275 {
2276   enum tree_code code = TREE_CODE (*tp);
2277
2278   /* We make copies of most nodes.  */
2279   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2280       || code == TREE_LIST
2281       || code == TREE_VEC
2282       || code == TYPE_DECL)
2283     {
2284       /* Because the chain gets clobbered when we make a copy, we save it
2285          here.  */
2286       tree chain = TREE_CHAIN (*tp);
2287       tree new;
2288
2289       /* Copy the node.  */
2290       new = copy_node (*tp);
2291
2292       /* Propagate mudflap marked-ness.  */
2293       if (flag_mudflap && mf_marked_p (*tp))
2294         mf_mark (new);
2295
2296       *tp = new;
2297
2298       /* Now, restore the chain, if appropriate.  That will cause
2299          walk_tree to walk into the chain as well.  */
2300       if (code == PARM_DECL || code == TREE_LIST)
2301         TREE_CHAIN (*tp) = chain;
2302
2303       /* For now, we don't update BLOCKs when we make copies.  So, we
2304          have to nullify all BIND_EXPRs.  */
2305       if (TREE_CODE (*tp) == BIND_EXPR)
2306         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2307     }
2308
2309   else if (TREE_CODE_CLASS (code) == tcc_type)
2310     *walk_subtrees = 0;
2311   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2312     *walk_subtrees = 0;
2313   else if (TREE_CODE_CLASS (code) == tcc_constant)
2314     *walk_subtrees = 0;
2315   else
2316     gcc_assert (code != STATEMENT_LIST);
2317   return NULL_TREE;
2318 }
2319
2320 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2321    information indicating to what new SAVE_EXPR this one should be mapped,
2322    use that one.  Otherwise, create a new node and enter it in ST.  */
2323
2324 static void
2325 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2326 {
2327   splay_tree st = (splay_tree) st_;
2328   splay_tree_node n;
2329   tree t;
2330
2331   /* See if we already encountered this SAVE_EXPR.  */
2332   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2333
2334   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2335   if (!n)
2336     {
2337       t = copy_node (*tp);
2338
2339       /* Remember this SAVE_EXPR.  */
2340       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2341       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2342       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2343     }
2344   else
2345     {
2346       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2347       *walk_subtrees = 0;
2348       t = (tree) n->value;
2349     }
2350
2351   /* Replace this SAVE_EXPR with the copy.  */
2352   *tp = t;
2353 }
2354
2355 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2356    copies the declaration and enters it in the splay_tree in DATA (which is
2357    really an `inline_data *').  */
2358
2359 static tree
2360 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2361                         void *data)
2362 {
2363   inline_data *id = (inline_data *) data;
2364
2365   /* Don't walk into types.  */
2366   if (TYPE_P (*tp))
2367     *walk_subtrees = 0;
2368
2369   else if (TREE_CODE (*tp) == LABEL_EXPR)
2370     {
2371       tree decl = TREE_OPERAND (*tp, 0);
2372
2373       /* Copy the decl and remember the copy.  */
2374       insert_decl_map (id, decl,
2375                        copy_decl_for_inlining (decl, DECL_CONTEXT (decl),
2376                                                DECL_CONTEXT (decl)));
2377     }
2378
2379   return NULL_TREE;
2380 }
2381
2382 /* Perform any modifications to EXPR required when it is unsaved.  Does
2383    not recurse into EXPR's subtrees.  */
2384
2385 static void
2386 unsave_expr_1 (tree expr)
2387 {
2388   switch (TREE_CODE (expr))
2389     {
2390     case TARGET_EXPR:
2391       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2392          It's OK for this to happen if it was part of a subtree that
2393          isn't immediately expanded, such as operand 2 of another
2394          TARGET_EXPR.  */
2395       if (TREE_OPERAND (expr, 1))
2396         break;
2397
2398       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2399       TREE_OPERAND (expr, 3) = NULL_TREE;
2400       break;
2401
2402     default:
2403       break;
2404     }
2405 }
2406
2407 /* Called via walk_tree when an expression is unsaved.  Using the
2408    splay_tree pointed to by ST (which is really a `splay_tree'),
2409    remaps all local declarations to appropriate replacements.  */
2410
2411 static tree
2412 unsave_r (tree *tp, int *walk_subtrees, void *data)
2413 {
2414   inline_data *id = (inline_data *) data;
2415   splay_tree st = id->decl_map;
2416   splay_tree_node n;
2417
2418   /* Only a local declaration (variable or label).  */
2419   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2420       || TREE_CODE (*tp) == LABEL_DECL)
2421     {
2422       /* Lookup the declaration.  */
2423       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2424
2425       /* If it's there, remap it.  */
2426       if (n)
2427         *tp = (tree) n->value;
2428     }
2429
2430   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2431     copy_statement_list (tp);
2432   else if (TREE_CODE (*tp) == BIND_EXPR)
2433     copy_bind_expr (tp, walk_subtrees, id);
2434   else if (TREE_CODE (*tp) == SAVE_EXPR)
2435     remap_save_expr (tp, st, walk_subtrees);
2436   else
2437     {
2438       copy_tree_r (tp, walk_subtrees, NULL);
2439
2440       /* Do whatever unsaving is required.  */
2441       unsave_expr_1 (*tp);
2442     }
2443
2444   /* Keep iterating.  */
2445   return NULL_TREE;
2446 }
2447
2448 /* Copies everything in EXPR and replaces variables, labels
2449    and SAVE_EXPRs local to EXPR.  */
2450
2451 tree
2452 unsave_expr_now (tree expr)
2453 {
2454   inline_data id;
2455
2456   /* There's nothing to do for NULL_TREE.  */
2457   if (expr == 0)
2458     return expr;
2459
2460   /* Set up ID.  */
2461   memset (&id, 0, sizeof (id));
2462   VARRAY_TREE_INIT (id.fns, 1, "fns");
2463   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2464   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2465
2466   /* Walk the tree once to find local labels.  */
2467   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2468
2469   /* Walk the tree again, copying, remapping, and unsaving.  */
2470   walk_tree (&expr, unsave_r, &id, NULL);
2471
2472   /* Clean up.  */
2473   splay_tree_delete (id.decl_map);
2474
2475   return expr;
2476 }
2477
2478 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2479
2480 static tree
2481 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2482 {
2483   if (*tp == data)
2484     return (tree) data;
2485   else
2486     return NULL;
2487 }
2488
2489 bool
2490 debug_find_tree (tree top, tree search)
2491 {
2492   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2493 }
2494
2495 /* Declare the variables created by the inliner.  Add all the variables in
2496    VARS to BIND_EXPR.  */
2497
2498 static void
2499 declare_inline_vars (tree bind_expr, tree vars)
2500 {
2501   tree t;
2502   for (t = vars; t; t = TREE_CHAIN (t))
2503     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2504
2505   add_var_to_bind_expr (bind_expr, vars);
2506 }