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