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 = 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
1328     case CONVERT_EXPR:
1329
1330     case CONJ_EXPR:
1331
1332     case PREDECREMENT_EXPR:
1333     case PREINCREMENT_EXPR:
1334     case POSTDECREMENT_EXPR:
1335     case POSTINCREMENT_EXPR:
1336
1337     case SWITCH_EXPR:
1338
1339     case ASM_EXPR:
1340
1341     case RESX_EXPR:
1342       *count++;
1343       break;
1344
1345     /* Few special cases of expensive operations.  This is usefull
1346        to avoid inlining on functions having too many of these.  */
1347     case TRUNC_DIV_EXPR:
1348     case CEIL_DIV_EXPR:
1349     case FLOOR_DIV_EXPR:
1350     case ROUND_DIV_EXPR:
1351     case EXACT_DIV_EXPR:
1352     case TRUNC_MOD_EXPR:
1353     case CEIL_MOD_EXPR:
1354     case FLOOR_MOD_EXPR:
1355     case ROUND_MOD_EXPR:
1356     case RDIV_EXPR:
1357       *count += 10;
1358       break;
1359     case CALL_EXPR:
1360       {
1361         tree decl = get_callee_fndecl (x);
1362
1363         if (decl && DECL_BUILT_IN (decl))
1364           switch (DECL_FUNCTION_CODE (decl))
1365             {
1366             case BUILT_IN_CONSTANT_P:
1367               *walk_subtrees = 0;
1368               return NULL_TREE;
1369             case BUILT_IN_EXPECT:
1370               return NULL_TREE;
1371             default:
1372               break;
1373             }
1374         *count += 10;
1375         break;
1376       }
1377     default:
1378       /* Abort here se we know we don't miss any nodes.  */
1379       abort ();
1380     }
1381   return NULL;
1382 }
1383
1384 /* Estimate number of instructions that will be created by expanding EXPR.  */
1385 int
1386 estimate_num_insns (tree expr)
1387 {
1388   int num = 0;
1389   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1390   return num;
1391 }
1392
1393 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1394
1395 static tree
1396 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1397 {
1398   inline_data *id;
1399   tree t;
1400   tree expr;
1401   tree stmt;
1402   tree use_retvar;
1403   tree decl;
1404   tree fn;
1405   tree arg_inits;
1406   tree *inlined_body;
1407   tree inline_result;
1408   splay_tree st;
1409   tree args;
1410   tree return_slot_addr;
1411   location_t saved_location;
1412   struct cgraph_edge *edge;
1413   const char *reason;
1414
1415   /* See what we've got.  */
1416   id = (inline_data *) data;
1417   t = *tp;
1418
1419   /* Set input_location here so we get the right instantiation context
1420      if we call instantiate_decl from inlinable_function_p.  */
1421   saved_location = input_location;
1422   if (EXPR_HAS_LOCATION (t))
1423     input_location = EXPR_LOCATION (t);
1424
1425   /* Recurse, but letting recursive invocations know that we are
1426      inside the body of a TARGET_EXPR.  */
1427   if (TREE_CODE (*tp) == TARGET_EXPR)
1428     {
1429 #if 0
1430       int i, len = first_rtl_op (TARGET_EXPR);
1431
1432       /* We're walking our own subtrees.  */
1433       *walk_subtrees = 0;
1434
1435       /* Actually walk over them.  This loop is the body of
1436          walk_trees, omitting the case where the TARGET_EXPR
1437          itself is handled.  */
1438       for (i = 0; i < len; ++i)
1439         {
1440           if (i == 2)
1441             ++id->in_target_cleanup_p;
1442           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1443                      id->tree_pruner);
1444           if (i == 2)
1445             --id->in_target_cleanup_p;
1446         }
1447
1448       goto egress;
1449 #endif
1450     }
1451
1452   if (TYPE_P (t))
1453     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1454        them should not be expanded.  This can happen if the type is a
1455        dynamic array type, for example.  */
1456     *walk_subtrees = 0;
1457
1458   /* From here on, we're only interested in CALL_EXPRs.  */
1459   if (TREE_CODE (t) != CALL_EXPR)
1460     goto egress;
1461
1462   /* First, see if we can figure out what function is being called.
1463      If we cannot, then there is no hope of inlining the function.  */
1464   fn = get_callee_fndecl (t);
1465   if (!fn)
1466     goto egress;
1467
1468   /* Turn forward declarations into real ones.  */
1469   fn = cgraph_node (fn)->decl;
1470
1471   /* If fn is a declaration of a function in a nested scope that was
1472      globally declared inline, we don't set its DECL_INITIAL.
1473      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1474      C++ front-end uses it for cdtors to refer to their internal
1475      declarations, that are not real functions.  Fortunately those
1476      don't have trees to be saved, so we can tell by checking their
1477      DECL_SAVED_TREE.  */
1478   if (! DECL_INITIAL (fn)
1479       && DECL_ABSTRACT_ORIGIN (fn)
1480       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1481     fn = DECL_ABSTRACT_ORIGIN (fn);
1482
1483   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1484      Kill this check once this is fixed.  */
1485   if (!id->current_node->analyzed)
1486     goto egress;
1487
1488   edge = cgraph_edge (id->current_node, t);
1489
1490   /* Constant propagation on argument done during previous inlining
1491      may create new direct call.  Produce an edge for it.  */
1492   if (!edge)
1493     {
1494       struct cgraph_node *dest = cgraph_node (fn);
1495
1496       /* We have missing edge in the callgraph.  This can happen in one case
1497          where previous inlining turned indirect call into direct call by
1498          constant propagating arguments.  In all other cases we hit a bug
1499          (incorrect node sharing is most common reason for missing edges.  */
1500       if (!dest->needed)
1501         abort ();
1502       cgraph_create_edge (id->node, dest, t)->inline_failed
1503         = N_("originally indirect function call not considered for inlining");
1504       goto egress;
1505     }
1506
1507   /* Don't try to inline functions that are not well-suited to
1508      inlining.  */
1509   if (!cgraph_inline_p (edge, &reason))
1510     {
1511       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1512         {
1513           sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1514           sorry ("called from here");
1515         }
1516       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1517                && !DECL_IN_SYSTEM_HEADER (fn)
1518                && strlen (reason))
1519         {
1520           warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1521           warning ("called from here");
1522         }
1523       goto egress;
1524     }
1525
1526 #ifdef ENABLE_CHECKING
1527   if (edge->callee->decl != id->node->decl)
1528     verify_cgraph_node (edge->callee);
1529 #endif
1530
1531   if (! lang_hooks.tree_inlining.start_inlining (fn))
1532     goto egress;
1533
1534   /* Build a block containing code to initialize the arguments, the
1535      actual inline expansion of the body, and a label for the return
1536      statements within the function to jump to.  The type of the
1537      statement expression is the return type of the function call.  */
1538   stmt = NULL;
1539   expr = build (BIND_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE,
1540                 stmt, make_node (BLOCK));
1541   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1542
1543   /* Local declarations will be replaced by their equivalents in this
1544      map.  */
1545   st = id->decl_map;
1546   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1547                                  NULL, NULL);
1548
1549   /* Initialize the parameters.  */
1550   args = TREE_OPERAND (t, 1);
1551   return_slot_addr = NULL_TREE;
1552   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1553     {
1554       return_slot_addr = TREE_VALUE (args);
1555       args = TREE_CHAIN (args);
1556       TREE_TYPE (expr) = void_type_node;
1557     }
1558
1559   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1560                                              fn, expr);
1561   if (arg_inits)
1562     {
1563       /* Expand any inlined calls in the initializers.  Do this before we
1564          push FN on the stack of functions we are inlining; we want to
1565          inline calls to FN that appear in the initializers for the
1566          parameters.
1567
1568          Note we need to save and restore the saved tree statement iterator
1569          to avoid having it clobbered by expand_calls_inline.  */
1570       tree_stmt_iterator save_tsi;
1571
1572       save_tsi = id->tsi;
1573       expand_calls_inline (&arg_inits, id);
1574       id->tsi = save_tsi;
1575
1576       /* And add them to the tree.  */
1577       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1578     }
1579
1580   /* Record the function we are about to inline so that we can avoid
1581      recursing into it.  */
1582   VARRAY_PUSH_TREE (id->fns, fn);
1583
1584   /* Record the function we are about to inline if optimize_function
1585      has not been called on it yet and we don't have it in the list.  */
1586   if (! DECL_INLINED_FNS (fn))
1587     {
1588       int i;
1589
1590       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1591         if (VARRAY_TREE (id->inlined_fns, i) == fn)
1592           break;
1593       if (i < 0)
1594         VARRAY_PUSH_TREE (id->inlined_fns, fn);
1595     }
1596
1597   /* Return statements in the function body will be replaced by jumps
1598      to the RET_LABEL.  */
1599   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1600   DECL_ARTIFICIAL (id->ret_label) = 1;
1601   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1602   insert_decl_map (id, id->ret_label, id->ret_label);
1603
1604   if (! DECL_INITIAL (fn)
1605       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
1606     abort ();
1607
1608   /* Declare the return variable for the function.  */
1609   decl = declare_return_variable (id, return_slot_addr, &use_retvar);
1610   if (decl)
1611     declare_inline_vars (expr, decl);
1612
1613   /* After we've initialized the parameters, we insert the body of the
1614      function itself.  */
1615   {
1616     struct cgraph_node *old_node = id->current_node;
1617
1618     id->current_node = edge->callee;
1619     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1620     id->current_node = old_node;
1621   }
1622   inlined_body = &BIND_EXPR_BODY (expr);
1623
1624   /* After the body of the function comes the RET_LABEL.  This must come
1625      before we evaluate the returned value below, because that evaluation
1626      may cause RTL to be generated.  */
1627   if (TREE_USED (id->ret_label))
1628     {
1629       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1630       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1631     }
1632
1633   /* Finally, mention the returned value so that the value of the
1634      statement-expression is the returned value of the function.  */
1635   if (use_retvar)
1636     /* Set TREE_TYPE on BIND_EXPR?  */
1637     append_to_statement_list_force (use_retvar, &BIND_EXPR_BODY (expr));
1638
1639   /* Clean up.  */
1640   splay_tree_delete (id->decl_map);
1641   id->decl_map = st;
1642
1643   /* The new expression has side-effects if the old one did.  */
1644   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1645
1646   /* If we are working with gimple form, then we need to keep the tree
1647      in gimple form.  If we are not in gimple form, we can just replace
1648      *tp with the new BIND_EXPR.  */
1649   if (lang_hooks.gimple_before_inlining)
1650     {
1651       tree save_decl;
1652
1653       /* Keep the new trees in gimple form.  */
1654       BIND_EXPR_BODY (expr)
1655         = rationalize_compound_expr (BIND_EXPR_BODY (expr));
1656
1657       /* We want to create a new variable to hold the result of the
1658          inlined body.  This new variable needs to be added to the
1659          function which we are inlining into, thus the saving and
1660          restoring of current_function_decl.  */
1661       save_decl = current_function_decl;
1662       current_function_decl = id->node->decl;
1663       inline_result = voidify_wrapper_expr (expr);
1664       current_function_decl = save_decl;
1665
1666       /* If the inlined function returns a result that we care about,
1667          then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1668          the call was a standalone statement and we can just replace it
1669          with the BIND_EXPR inline representation of the called function.  */
1670       if (TREE_CODE (tsi_stmt (id->tsi)) != CALL_EXPR)
1671         {
1672           tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1673           *tp = inline_result;
1674         }
1675       else
1676         *tp = expr;
1677
1678       /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS
1679          on the call if it is to a "const" function.  Thus the copy of
1680          TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above
1681          with result in TREE_SIDE_EFFECTS not being set for the inlined
1682          copy of a "const" function.
1683
1684          Unfortunately, that is wrong as inlining the function
1685          can create/expose interesting side effects (such as setting
1686          of a return value).
1687
1688          The easiest solution is to simply recalculate TREE_SIDE_EFFECTS
1689          for the toplevel expression.  */
1690       recalculate_side_effects (expr);
1691     }
1692   else
1693     *tp = expr;
1694
1695   /* If the value of the new expression is ignored, that's OK.  We
1696      don't warn about this for CALL_EXPRs, so we shouldn't warn about
1697      the equivalent inlined version either.  */
1698   TREE_USED (*tp) = 1;
1699
1700   /* Update callgraph if needed.  */
1701   cgraph_remove_node (edge->callee);
1702
1703   /* Recurse into the body of the just inlined function.  */
1704   expand_calls_inline (inlined_body, id);
1705   VARRAY_POP (id->fns);
1706
1707   /* Don't walk into subtrees.  We've already handled them above.  */
1708   *walk_subtrees = 0;
1709
1710   lang_hooks.tree_inlining.end_inlining (fn);
1711
1712   /* Keep iterating.  */
1713  egress:
1714   input_location = saved_location;
1715   return NULL_TREE;
1716 }
1717
1718 static void
1719 gimple_expand_calls_inline (tree *stmt_p, inline_data *id)
1720 {
1721   tree stmt = *stmt_p;
1722   enum tree_code code = TREE_CODE (stmt);
1723   int dummy;
1724
1725   switch (code)
1726     {
1727     case STATEMENT_LIST:
1728       {
1729         tree_stmt_iterator i;
1730         tree new;
1731
1732         for (i = tsi_start (stmt); !tsi_end_p (i); )
1733           {
1734             id->tsi = i;
1735             gimple_expand_calls_inline (tsi_stmt_ptr (i), id);
1736
1737             new = tsi_stmt (i);
1738             if (TREE_CODE (new) == STATEMENT_LIST)
1739               {
1740                 tsi_link_before (&i, new, TSI_SAME_STMT);
1741                 tsi_delink (&i);
1742               }
1743             else
1744               tsi_next (&i);
1745           }
1746       }
1747       break;
1748
1749     case COND_EXPR:
1750       gimple_expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1751       gimple_expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1752       break;
1753     case CATCH_EXPR:
1754       gimple_expand_calls_inline (&CATCH_BODY (stmt), id);
1755       break;
1756     case EH_FILTER_EXPR:
1757       gimple_expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1758       break;
1759     case TRY_CATCH_EXPR:
1760     case TRY_FINALLY_EXPR:
1761       gimple_expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1762       gimple_expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1763       break;
1764     case BIND_EXPR:
1765       gimple_expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1766       break;
1767
1768     case COMPOUND_EXPR:
1769       /* We're gimple.  We should have gotten rid of all these.  */
1770       abort ();
1771
1772     case RETURN_EXPR:
1773       stmt_p = &TREE_OPERAND (stmt, 0);
1774       stmt = *stmt_p;
1775       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1776         break;
1777       /* FALLTHRU */
1778     case MODIFY_EXPR:
1779       stmt_p = &TREE_OPERAND (stmt, 1);
1780       stmt = *stmt_p;
1781       if (TREE_CODE (stmt) != CALL_EXPR)
1782         break;
1783       /* FALLTHRU */
1784     case CALL_EXPR:
1785       expand_call_inline (stmt_p, &dummy, id);
1786       break;
1787
1788     default:
1789       break;
1790     }
1791 }
1792
1793 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
1794    expansions as appropriate.  */
1795
1796 static void
1797 expand_calls_inline (tree *tp, inline_data *id)
1798 {
1799   /* If we are not in gimple form, then we want to walk the tree
1800      recursively as we do not know anything about the structure
1801      of the tree.  */
1802
1803   if (!lang_hooks.gimple_before_inlining)
1804     {
1805       walk_tree (tp, expand_call_inline, id, id->tree_pruner);
1806       return;
1807     }
1808
1809   /* We are in gimple form.  We want to stay in gimple form.  Walk
1810      the statements, inlining calls in each statement.  By walking
1811      the statements, we have enough information to keep the tree
1812      in gimple form as we insert inline bodies.  */
1813
1814   gimple_expand_calls_inline (tp, id);
1815 }
1816
1817 /* Expand calls to inline functions in the body of FN.  */
1818
1819 void
1820 optimize_inline_calls (tree fn)
1821 {
1822   inline_data id;
1823   tree prev_fn;
1824
1825   /* There is no point in performing inlining if errors have already
1826      occurred -- and we might crash if we try to inline invalid
1827      code.  */
1828   if (errorcount || sorrycount)
1829     return;
1830
1831   /* Clear out ID.  */
1832   memset (&id, 0, sizeof (id));
1833
1834   id.current_node = id.node = cgraph_node (fn);
1835   /* Don't allow recursion into FN.  */
1836   VARRAY_TREE_INIT (id.fns, 32, "fns");
1837   VARRAY_PUSH_TREE (id.fns, fn);
1838   /* Or any functions that aren't finished yet.  */
1839   prev_fn = NULL_TREE;
1840   if (current_function_decl)
1841     {
1842       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1843       prev_fn = current_function_decl;
1844     }
1845
1846   prev_fn = (lang_hooks.tree_inlining.add_pending_fn_decls
1847              (&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,
1859                                 htab_eq_pointer, NULL);
1860   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1861
1862   /* Clean up.  */
1863   htab_delete (id.tree_pruner);
1864   if (DECL_LANG_SPECIFIC (fn))
1865     {
1866       tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1867
1868       if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1869         memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1870                 VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1871       DECL_INLINED_FNS (fn) = ifn;
1872     }
1873
1874 #ifdef ENABLE_CHECKING
1875     {
1876       struct cgraph_edge *e;
1877
1878       verify_cgraph_node (id.node);
1879
1880       /* Double check that we inlined everything we are supposed to inline.  */
1881       for (e = id.node->callees; e; e = e->next_callee)
1882         if (!e->inline_failed)
1883           abort ();
1884     }
1885 #endif
1886 }
1887
1888 /* FN is a function that has a complete body, and CLONE is a function
1889    whose body is to be set to a copy of FN, mapping argument
1890    declarations according to the ARG_MAP splay_tree.  */
1891
1892 void
1893 clone_body (tree clone, tree fn, void *arg_map)
1894 {
1895   inline_data id;
1896
1897   /* Clone the body, as if we were making an inline call.  But, remap
1898      the parameters in the callee to the parameters of caller.  If
1899      there's an in-charge parameter, map it to an appropriate
1900      constant.  */
1901   memset (&id, 0, sizeof (id));
1902   VARRAY_TREE_INIT (id.fns, 2, "fns");
1903   VARRAY_PUSH_TREE (id.fns, clone);
1904   VARRAY_PUSH_TREE (id.fns, fn);
1905   id.decl_map = (splay_tree)arg_map;
1906
1907   /* Cloning is treated slightly differently from inlining.  Set
1908      CLONING_P so that it's clear which operation we're performing.  */
1909   id.cloning_p = true;
1910
1911   /* Actually copy the body.  */
1912   TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1913 }
1914
1915 /* Save duplicate of body in FN.  MAP is used to pass around splay tree
1916    used to update arguments in restore_body.  */
1917 tree
1918 save_body (tree fn, tree *arg_copy)
1919 {
1920   inline_data id;
1921   tree body, *parg;
1922
1923   memset (&id, 0, sizeof (id));
1924   VARRAY_TREE_INIT (id.fns, 1, "fns");
1925   VARRAY_PUSH_TREE (id.fns, fn);
1926   id.node = cgraph_node (fn);
1927   id.saving_p = true;
1928   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1929   *arg_copy = DECL_ARGUMENTS (fn);
1930   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1931     {
1932       tree new = copy_node (*parg);
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   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1940
1941   /* Actually copy the body.  */
1942   body = copy_body (&id);
1943
1944   /* Clean up.  */
1945   splay_tree_delete (id.decl_map);
1946   return body;
1947 }
1948
1949 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1950    FUNC is called with the DATA and the address of each sub-tree.  If
1951    FUNC returns a non-NULL value, the traversal is aborted, and the
1952    value returned by FUNC is returned.  If HTAB is non-NULL it is used
1953    to record the nodes visited, and to avoid visiting a node more than
1954    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           || lang_hooks.tree_inlining.tree_chain_matters_p (*tp))
2014         /* But we still need to check our siblings.  */
2015         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2016       else
2017         return NULL_TREE;
2018     }
2019
2020   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2021                                                    data, htab);
2022   if (result || ! walk_subtrees)
2023     return result;
2024
2025   if (code != EXIT_BLOCK_EXPR
2026       && code != SAVE_EXPR
2027       && code != BIND_EXPR
2028       && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2029     {
2030       int i, len;
2031
2032       /* Walk over all the sub-trees of this operand.  */
2033       len = first_rtl_op (code);
2034       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2035          But, we only want to walk once.  */
2036       if (code == TARGET_EXPR
2037           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2038         --len;
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       if (lang_hooks.tree_inlining.tree_chain_matters_p (*tp))
2060         /* Check our siblings.  */
2061         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2062     }
2063   else if (TREE_CODE_CLASS (code) == 'd')
2064     {
2065       WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
2066     }
2067   else
2068     {
2069       if (TREE_CODE_CLASS (code) == 't')
2070         {
2071           WALK_SUBTREE (TYPE_SIZE (*tp));
2072           WALK_SUBTREE (TYPE_SIZE_UNIT (*tp));
2073           /* Also examine various special fields, below.  */
2074         }
2075
2076       /* Not one of the easy cases.  We must explicitly go through the
2077          children.  */
2078       switch (code)
2079         {
2080         case ERROR_MARK:
2081         case IDENTIFIER_NODE:
2082         case INTEGER_CST:
2083         case REAL_CST:
2084         case VECTOR_CST:
2085         case STRING_CST:
2086         case REAL_TYPE:
2087         case COMPLEX_TYPE:
2088         case VECTOR_TYPE:
2089         case VOID_TYPE:
2090         case BOOLEAN_TYPE:
2091         case UNION_TYPE:
2092         case ENUMERAL_TYPE:
2093         case BLOCK:
2094         case RECORD_TYPE:
2095         case PLACEHOLDER_EXPR:
2096         case SSA_NAME:
2097           /* None of thse have subtrees other than those already walked
2098              above.  */
2099           break;
2100
2101         case POINTER_TYPE:
2102         case REFERENCE_TYPE:
2103           WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
2104           break;
2105
2106         case TREE_LIST:
2107           WALK_SUBTREE (TREE_VALUE (*tp));
2108           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2109           break;
2110
2111         case TREE_VEC:
2112           {
2113             int len = TREE_VEC_LENGTH (*tp);
2114
2115             if (len == 0)
2116               break;
2117
2118             /* Walk all elements but the first.  */
2119             while (--len)
2120               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2121
2122             /* Now walk the first one as a tail call.  */
2123             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2124           }
2125
2126         case COMPLEX_CST:
2127           WALK_SUBTREE (TREE_REALPART (*tp));
2128           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2129
2130         case CONSTRUCTOR:
2131           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2132
2133         case METHOD_TYPE:
2134           WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
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 ARRAY_TYPE:
2149           WALK_SUBTREE (TREE_TYPE (*tp));
2150           WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp));
2151
2152         case INTEGER_TYPE:
2153         case CHAR_TYPE:
2154           WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
2155           WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp));
2156
2157         case OFFSET_TYPE:
2158           WALK_SUBTREE (TREE_TYPE (*tp));
2159           WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp));
2160
2161         case EXIT_BLOCK_EXPR:
2162           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
2163
2164         case SAVE_EXPR:
2165           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2166
2167         case BIND_EXPR:
2168           {
2169             tree decl;
2170             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2171               {
2172                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2173                    into declarations that are just mentioned, rather than
2174                    declared; they don't really belong to this part of the tree.
2175                    And, we can see cycles: the initializer for a declaration can
2176                    refer to the declaration itself.  */
2177                 WALK_SUBTREE (DECL_INITIAL (decl));
2178                 WALK_SUBTREE (DECL_SIZE (decl));
2179                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2180                 WALK_SUBTREE (TREE_TYPE (decl));
2181               }
2182             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2183           }
2184
2185         case STATEMENT_LIST:
2186           {
2187             tree_stmt_iterator i;
2188             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2189               WALK_SUBTREE (*tsi_stmt_ptr (i));
2190           }
2191           break;
2192
2193         default:
2194           abort ();
2195         }
2196     }
2197
2198   /* We didn't find what we were looking for.  */
2199   return NULL_TREE;
2200
2201 #undef WALK_SUBTREE
2202 #undef WALK_SUBTREE_TAIL
2203 }
2204
2205 /* Like walk_tree, but does not walk duplicate nodes more than
2206    once.  */
2207
2208 tree
2209 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2210 {
2211   tree result;
2212   htab_t htab;
2213
2214   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
2215   result = walk_tree (tp, func, data, htab);
2216   htab_delete (htab);
2217   return result;
2218 }
2219
2220 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2221
2222 tree
2223 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2224 {
2225   enum tree_code code = TREE_CODE (*tp);
2226
2227   /* We make copies of most nodes.  */
2228   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2229       || TREE_CODE_CLASS (code) == 'c'
2230       || code == TREE_LIST
2231       || code == TREE_VEC
2232       || code == TYPE_DECL
2233       || lang_hooks.tree_inlining.tree_chain_matters_p (*tp))
2234     {
2235       /* Because the chain gets clobbered when we make a copy, we save it
2236          here.  */
2237       tree chain = TREE_CHAIN (*tp);
2238       tree new;
2239
2240       /* Copy the node.  */
2241       new = copy_node (*tp);
2242
2243       /* Propagate mudflap marked-ness.  */
2244       if (flag_mudflap && mf_marked_p (*tp))
2245         mf_mark (new);
2246
2247       *tp = new;
2248
2249       /* Now, restore the chain, if appropriate.  That will cause
2250          walk_tree to walk into the chain as well.  */
2251       if (code == PARM_DECL || code == TREE_LIST
2252           || lang_hooks.tree_inlining.tree_chain_matters_p (*tp))
2253         TREE_CHAIN (*tp) = chain;
2254
2255       /* For now, we don't update BLOCKs when we make copies.  So, we
2256          have to nullify all BIND_EXPRs.  */
2257       if (TREE_CODE (*tp) == BIND_EXPR)
2258         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2259     }
2260   else if (TREE_CODE_CLASS (code) == 't')
2261     *walk_subtrees = 0;
2262   else if (TREE_CODE_CLASS (code) == 'd')
2263     *walk_subtrees = 0;
2264   else if (code == STATEMENT_LIST)
2265     abort ();
2266
2267   return NULL_TREE;
2268 }
2269
2270 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2271    information indicating to what new SAVE_EXPR this one should be
2272    mapped, use that one.  Otherwise, create a new node and enter it in
2273    ST.  FN is the function into which the copy will be placed.  */
2274
2275 void
2276 remap_save_expr (tree *tp, void *st_, tree fn, int *walk_subtrees)
2277 {
2278   splay_tree st = (splay_tree) st_;
2279   splay_tree_node n;
2280   tree t;
2281
2282   /* See if we already encountered this SAVE_EXPR.  */
2283   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2284
2285   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2286   if (!n)
2287     {
2288       t = copy_node (*tp);
2289
2290       /* The SAVE_EXPR is now part of the function into which we
2291          are inlining this body.  */
2292       SAVE_EXPR_CONTEXT (t) = fn;
2293       /* And we haven't evaluated it yet.  */
2294       SAVE_EXPR_RTL (t) = NULL_RTX;
2295       /* Remember this SAVE_EXPR.  */
2296       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2297       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2298       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2299     }
2300   else
2301     {
2302       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2303       *walk_subtrees = 0;
2304       t = (tree) n->value;
2305     }
2306
2307   /* Replace this SAVE_EXPR with the copy.  */
2308   *tp = t;
2309 }
2310
2311 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local
2312    declaration, copies the declaration and enters it in the splay_tree
2313    in DATA (which is really an `inline_data *').  */
2314
2315 static tree
2316 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2317                         void *data)
2318 {
2319   tree t = *tp;
2320   inline_data *id = (inline_data *) data;
2321   tree decl;
2322
2323   /* Don't walk into types.  */
2324   if (TYPE_P (t))
2325     {
2326       *walk_subtrees = 0;
2327       return NULL_TREE;
2328     }
2329
2330   if (TREE_CODE (t) == LABEL_EXPR)
2331     decl = TREE_OPERAND (t, 0);
2332   else
2333     /* We don't need to handle anything else ahead of time.  */
2334     decl = NULL_TREE;
2335
2336   if (decl)
2337     {
2338       tree copy;
2339
2340       /* Make a copy.  */
2341       copy = copy_decl_for_inlining (decl,
2342                                      DECL_CONTEXT (decl),
2343                                      DECL_CONTEXT (decl));
2344
2345       /* Remember the copy.  */
2346       insert_decl_map (id, decl, copy);
2347     }
2348
2349   return NULL_TREE;
2350 }
2351
2352 /* Called via walk_tree when an expression is unsaved.  Using the
2353    splay_tree pointed to by ST (which is really a `splay_tree'),
2354    remaps all local declarations to appropriate replacements.  */
2355
2356 static tree
2357 unsave_r (tree *tp, int *walk_subtrees, void *data)
2358 {
2359   inline_data *id = (inline_data *) data;
2360   splay_tree st = id->decl_map;
2361   splay_tree_node n;
2362
2363   /* Only a local declaration (variable or label).  */
2364   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2365       || TREE_CODE (*tp) == LABEL_DECL)
2366     {
2367       /* Lookup the declaration.  */
2368       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2369
2370       /* If it's there, remap it.  */
2371       if (n)
2372         *tp = (tree) n->value;
2373     }
2374   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2375     copy_statement_list (tp);
2376   else if (TREE_CODE (*tp) == BIND_EXPR)
2377     copy_bind_expr (tp, walk_subtrees, id);
2378   else if (TREE_CODE (*tp) == SAVE_EXPR)
2379     remap_save_expr (tp, st, current_function_decl, walk_subtrees);
2380   else
2381     {
2382       copy_tree_r (tp, walk_subtrees, NULL);
2383
2384       /* Do whatever unsaving is required.  */
2385       unsave_expr_1 (*tp);
2386     }
2387
2388   /* Keep iterating.  */
2389   return NULL_TREE;
2390 }
2391
2392 /* Default lang hook for "unsave_expr_now".  Copies everything in EXPR and
2393    replaces variables, labels and SAVE_EXPRs local to EXPR.  */
2394
2395 tree
2396 lhd_unsave_expr_now (tree expr)
2397 {
2398   inline_data id;
2399
2400   /* There's nothing to do for NULL_TREE.  */
2401   if (expr == 0)
2402     return expr;
2403
2404   /* Set up ID.  */
2405   memset (&id, 0, sizeof (id));
2406   VARRAY_TREE_INIT (id.fns, 1, "fns");
2407   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2408   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2409
2410   /* Walk the tree once to find local labels.  */
2411   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2412
2413   /* Walk the tree again, copying, remapping, and unsaving.  */
2414   walk_tree (&expr, unsave_r, &id, NULL);
2415
2416   /* Clean up.  */
2417   splay_tree_delete (id.decl_map);
2418
2419   return expr;
2420 }
2421
2422 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2423 static tree
2424 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2425 {
2426   if (*tp == data)
2427     return (tree) data;
2428   else
2429     return NULL;
2430 }
2431
2432 extern bool debug_find_tree (tree top, tree search);
2433
2434 bool
2435 debug_find_tree (tree top, tree search)
2436 {
2437   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2438 }
2439
2440
2441 /* Declare the variables created by the inliner.  Add all the variables in
2442    VARS to BIND_EXPR.  */
2443
2444 static void
2445 declare_inline_vars (tree bind_expr, tree vars)
2446 {
2447   if (lang_hooks.gimple_before_inlining)
2448     {
2449       tree t;
2450       for (t = vars; t; t = TREE_CHAIN (t))
2451         vars->decl.seen_in_bind_expr = 1;
2452     }
2453
2454   add_var_to_bind_expr (bind_expr, vars);
2455 }