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