gcc/tree-inline.c

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