gcc/tree-inline.c

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