gcc/tree-inline.c

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