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