gcc/tree-inline.c

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