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_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1573   insert_decl_map (id, id->ret_label, id->ret_label);
1574
1575   gcc_assert (DECL_INITIAL (fn));
1576   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
1577
1578   /* Find the lhs to which the result of this call is assigned.  */
1579   modify_dest = tsi_stmt (id->tsi);
1580   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1581     modify_dest = TREE_OPERAND (modify_dest, 0);
1582   else
1583     modify_dest = NULL;
1584
1585   /* Declare the return variable for the function.  */
1586   decl = declare_return_variable (id, return_slot_addr,
1587                                   modify_dest, &use_retvar);
1588
1589   /* After we've initialized the parameters, we insert the body of the
1590      function itself.  */
1591   {
1592     struct cgraph_node *old_node = id->current_node;
1593
1594     id->current_node = edge->callee;
1595     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1596     id->current_node = old_node;
1597   }
1598   inlined_body = &BIND_EXPR_BODY (expr);
1599
1600   /* After the body of the function comes the RET_LABEL.  This must come
1601      before we evaluate the returned value below, because that evaluation
1602      may cause RTL to be generated.  */
1603   if (TREE_USED (id->ret_label))
1604     {
1605       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1606       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1607     }
1608
1609   /* Clean up.  */
1610   splay_tree_delete (id->decl_map);
1611   id->decl_map = st;
1612
1613   /* Although, from the semantic viewpoint, the new expression has
1614      side-effects only if the old one did, it is not possible, from
1615      the technical viewpoint, to evaluate the body of a function
1616      multiple times without serious havoc.  */
1617   TREE_SIDE_EFFECTS (expr) = 1;
1618
1619   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1620
1621   /* If the inlined function returns a result that we care about,
1622      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1623      the call was a standalone statement and we can just replace it
1624      with the BIND_EXPR inline representation of the called function.  */
1625   if (!use_retvar || !modify_dest)
1626     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1627   else
1628     *tp = use_retvar;
1629
1630   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1631      the call if it is to a "const" function.  Thus the copy of
1632      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1633      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1634      "const" function.
1635
1636      Unfortunately, that is wrong as inlining the function can create/expose
1637      interesting side effects (such as setting of a return value).
1638
1639      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1640      the toplevel expression.  */
1641   recalculate_side_effects (expr);
1642
1643   /* Update callgraph if needed.  */
1644   cgraph_remove_node (edge->callee);
1645
1646   /* Recurse into the body of the just inlined function.  */
1647   expand_calls_inline (inlined_body, id);
1648   VARRAY_POP (id->fns);
1649
1650   /* Don't walk into subtrees.  We've already handled them above.  */
1651   *walk_subtrees = 0;
1652
1653   lang_hooks.tree_inlining.end_inlining (fn);
1654
1655   /* Keep iterating.  */
1656  egress:
1657   input_location = saved_location;
1658   return NULL_TREE;
1659 }
1660
1661 static void
1662 expand_calls_inline (tree *stmt_p, inline_data *id)
1663 {
1664   tree stmt = *stmt_p;
1665   enum tree_code code = TREE_CODE (stmt);
1666   int dummy;
1667
1668   switch (code)
1669     {
1670     case STATEMENT_LIST:
1671       {
1672         tree_stmt_iterator i;
1673         tree new;
1674
1675         for (i = tsi_start (stmt); !tsi_end_p (i); )
1676           {
1677             id->tsi = i;
1678             expand_calls_inline (tsi_stmt_ptr (i), id);
1679
1680             new = tsi_stmt (i);
1681             if (TREE_CODE (new) == STATEMENT_LIST)
1682               {
1683                 tsi_link_before (&i, new, TSI_SAME_STMT);
1684                 tsi_delink (&i);
1685               }
1686             else
1687               tsi_next (&i);
1688           }
1689       }
1690       break;
1691
1692     case COND_EXPR:
1693       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1694       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1695       break;
1696
1697     case CATCH_EXPR:
1698       expand_calls_inline (&CATCH_BODY (stmt), id);
1699       break;
1700
1701     case EH_FILTER_EXPR:
1702       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1703       break;
1704
1705     case TRY_CATCH_EXPR:
1706     case TRY_FINALLY_EXPR:
1707       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1708       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1709       break;
1710
1711     case BIND_EXPR:
1712       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1713       break;
1714
1715     case COMPOUND_EXPR:
1716       /* We're gimple.  We should have gotten rid of all these.  */
1717       gcc_unreachable ();
1718
1719     case RETURN_EXPR:
1720       stmt_p = &TREE_OPERAND (stmt, 0);
1721       stmt = *stmt_p;
1722       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1723         break;
1724
1725       /* FALLTHRU */
1726
1727     case MODIFY_EXPR:
1728       stmt_p = &TREE_OPERAND (stmt, 1);
1729       stmt = *stmt_p;
1730       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1731         {
1732           stmt_p = &TREE_OPERAND (stmt, 0);
1733           stmt = *stmt_p;
1734         }
1735       if (TREE_CODE (stmt) != CALL_EXPR)
1736         break;
1737
1738       /* FALLTHRU */
1739
1740     case CALL_EXPR:
1741       expand_call_inline (stmt_p, &dummy, id);
1742       break;
1743
1744     default:
1745       break;
1746     }
1747 }
1748
1749 /* Expand calls to inline functions in the body of FN.  */
1750
1751 void
1752 optimize_inline_calls (tree fn)
1753 {
1754   inline_data id;
1755   tree prev_fn;
1756
1757   /* There is no point in performing inlining if errors have already
1758      occurred -- and we might crash if we try to inline invalid
1759      code.  */
1760   if (errorcount || sorrycount)
1761     return;
1762
1763   /* Clear out ID.  */
1764   memset (&id, 0, sizeof (id));
1765
1766   id.current_node = id.node = cgraph_node (fn);
1767   /* Don't allow recursion into FN.  */
1768   VARRAY_TREE_INIT (id.fns, 32, "fns");
1769   VARRAY_PUSH_TREE (id.fns, fn);
1770   /* Or any functions that aren't finished yet.  */
1771   prev_fn = NULL_TREE;
1772   if (current_function_decl)
1773     {
1774       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1775       prev_fn = current_function_decl;
1776     }
1777
1778   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1779
1780   /* Keep track of the low-water mark, i.e., the point where the first
1781      real inlining is represented in ID.FNS.  */
1782   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1783
1784   /* Replace all calls to inline functions with the bodies of those
1785      functions.  */
1786   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1787   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1788
1789   /* Clean up.  */
1790   htab_delete (id.tree_pruner);
1791
1792 #ifdef ENABLE_CHECKING
1793     {
1794       struct cgraph_edge *e;
1795
1796       verify_cgraph_node (id.node);
1797
1798       /* Double check that we inlined everything we are supposed to inline.  */
1799       for (e = id.node->callees; e; e = e->next_callee)
1800         gcc_assert (e->inline_failed);
1801     }
1802 #endif
1803 }
1804
1805 /* FN is a function that has a complete body, and CLONE is a function whose
1806    body is to be set to a copy of FN, mapping argument declarations according
1807    to the ARG_MAP splay_tree.  */
1808
1809 void
1810 clone_body (tree clone, tree fn, void *arg_map)
1811 {
1812   inline_data id;
1813
1814   /* Clone the body, as if we were making an inline call.  But, remap the
1815      parameters in the callee to the parameters of caller.  If there's an
1816      in-charge parameter, map it to an appropriate constant.  */
1817   memset (&id, 0, sizeof (id));
1818   VARRAY_TREE_INIT (id.fns, 2, "fns");
1819   VARRAY_PUSH_TREE (id.fns, clone);
1820   VARRAY_PUSH_TREE (id.fns, fn);
1821   id.decl_map = (splay_tree)arg_map;
1822
1823   /* Cloning is treated slightly differently from inlining.  Set
1824      CLONING_P so that it's clear which operation we're performing.  */
1825   id.cloning_p = true;
1826
1827   /* Actually copy the body.  */
1828   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1829 }
1830
1831 /* Make and return duplicate of body in FN.  Put copies of DECL_ARGUMENTS
1832    in *arg_copy and of the static chain, if any, in *sc_copy.  */
1833
1834 tree
1835 save_body (tree fn, tree *arg_copy, tree *sc_copy)
1836 {
1837   inline_data id;
1838   tree body, *parg;
1839
1840   memset (&id, 0, sizeof (id));
1841   VARRAY_TREE_INIT (id.fns, 1, "fns");
1842   VARRAY_PUSH_TREE (id.fns, fn);
1843   id.node = cgraph_node (fn);
1844   id.saving_p = true;
1845   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1846   *arg_copy = DECL_ARGUMENTS (fn);
1847
1848   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1849     {
1850       tree new = copy_node (*parg);
1851
1852       lang_hooks.dup_lang_specific_decl (new);
1853       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1854       insert_decl_map (&id, *parg, new);
1855       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1856       *parg = new;
1857     }
1858
1859   *sc_copy = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1860   if (*sc_copy)
1861     {
1862       tree new = copy_node (*sc_copy);
1863
1864       lang_hooks.dup_lang_specific_decl (new);
1865       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*sc_copy);
1866       insert_decl_map (&id, *sc_copy, new);
1867       TREE_CHAIN (new) = TREE_CHAIN (*sc_copy);
1868       *sc_copy = new;
1869     }
1870
1871   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1872
1873   /* Actually copy the body.  */
1874   body = copy_body (&id);
1875
1876   /* Clean up.  */
1877   splay_tree_delete (id.decl_map);
1878   return body;
1879 }
1880
1881 #define WALK_SUBTREE(NODE)                              \
1882   do                                                    \
1883     {                                                   \
1884       result = walk_tree (&(NODE), func, data, pset);   \
1885       if (result)                                       \
1886         return result;                                  \
1887     }                                                   \
1888   while (0)
1889
1890 /* This is a subroutine of walk_tree that walks field of TYPE that are to
1891    be walked whenever a type is seen in the tree.  Rest of operands and return
1892    value are as for walk_tree.  */
1893
1894 static tree
1895 walk_type_fields (tree type, walk_tree_fn func, void *data,
1896                   struct pointer_set_t *pset)
1897 {
1898   tree result = NULL_TREE;
1899
1900   switch (TREE_CODE (type))
1901     {
1902     case POINTER_TYPE:
1903     case REFERENCE_TYPE:
1904       /* We have to worry about mutually recursive pointers.  These can't
1905          be written in C.  They can in Ada.  It's pathological, but
1906          there's an ACATS test (c38102a) that checks it.  Deal with this
1907          by checking if we're pointing to another pointer, that one
1908          points to another pointer, that one does too, and we have no htab.
1909          If so, get a hash table.  We check three levels deep to avoid
1910          the cost of the hash table if we don't need one.  */
1911       if (POINTER_TYPE_P (TREE_TYPE (type))
1912           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
1913           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
1914           && !pset)
1915         {
1916           result = walk_tree_without_duplicates (&TREE_TYPE (type),
1917                                                  func, data);
1918           if (result)
1919             return result;
1920
1921           break;
1922         }
1923
1924       /* ... fall through ... */
1925
1926     case COMPLEX_TYPE:
1927       WALK_SUBTREE (TREE_TYPE (type));
1928       break;
1929
1930     case METHOD_TYPE:
1931       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
1932
1933       /* Fall through.  */
1934
1935     case FUNCTION_TYPE:
1936       WALK_SUBTREE (TREE_TYPE (type));
1937       {
1938         tree arg;
1939
1940         /* We never want to walk into default arguments.  */
1941         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
1942           WALK_SUBTREE (TREE_VALUE (arg));
1943       }
1944       break;
1945
1946     case ARRAY_TYPE:
1947       /* Don't follow this nodes's type if a pointer for fear that we'll
1948          have infinite recursion.  Those types are uninteresting anyway.  */
1949       if (!POINTER_TYPE_P (TREE_TYPE (type))
1950           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
1951         WALK_SUBTREE (TREE_TYPE (type));
1952       WALK_SUBTREE (TYPE_DOMAIN (type));
1953       break;
1954
1955     case BOOLEAN_TYPE:
1956     case ENUMERAL_TYPE:
1957     case INTEGER_TYPE:
1958     case CHAR_TYPE:
1959     case REAL_TYPE:
1960       WALK_SUBTREE (TYPE_MIN_VALUE (type));
1961       WALK_SUBTREE (TYPE_MAX_VALUE (type));
1962       break;
1963
1964     case OFFSET_TYPE:
1965       WALK_SUBTREE (TREE_TYPE (type));
1966       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
1967       break;
1968
1969     default:
1970       break;
1971     }
1972
1973   return NULL_TREE;
1974 }
1975
1976 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
1977    called with the DATA and the address of each sub-tree.  If FUNC returns a
1978    non-NULL value, the traversal is aborted, and the value returned by FUNC
1979    is returned.  If PSET is non-NULL it is used to record the nodes visited,
1980    and to avoid visiting a node more than once.  */
1981
1982 tree
1983 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
1984 {
1985   enum tree_code code;
1986   int walk_subtrees;
1987   tree result;
1988
1989 #define WALK_SUBTREE_TAIL(NODE)                         \
1990   do                                                    \
1991     {                                                   \
1992        tp = & (NODE);                                   \
1993        goto tail_recurse;                               \
1994     }                                                   \
1995   while (0)
1996
1997  tail_recurse:
1998   /* Skip empty subtrees.  */
1999   if (!*tp)
2000     return NULL_TREE;
2001
2002   /* Don't walk the same tree twice, if the user has requested
2003      that we avoid doing so.  */
2004   if (pset && pointer_set_insert (pset, *tp))
2005     return NULL_TREE;
2006
2007   /* Call the function.  */
2008   walk_subtrees = 1;
2009   result = (*func) (tp, &walk_subtrees, data);
2010
2011   /* If we found something, return it.  */
2012   if (result)
2013     return result;
2014
2015   code = TREE_CODE (*tp);
2016
2017   /* Even if we didn't, FUNC may have decided that there was nothing
2018      interesting below this point in the tree.  */
2019   if (!walk_subtrees)
2020     {
2021       if (code == TREE_LIST)
2022         /* But we still need to check our siblings.  */
2023         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2024       else
2025         return NULL_TREE;
2026     }
2027
2028   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2029                                                    data, pset);
2030   if (result || ! walk_subtrees)
2031     return result;
2032
2033   /* If this is a DECL_EXPR, walk into various fields of the type that it's
2034      defining.  We only want to walk into these fields of a type in this
2035      case.  Note that decls get walked as part of the processing of a
2036      BIND_EXPR.
2037
2038      ??? Precisely which fields of types that we are supposed to walk in
2039      this case vs. the normal case aren't well defined.  */
2040   if (code == DECL_EXPR
2041       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
2042       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
2043     {
2044       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
2045
2046       /* Call the function for the type.  See if it returns anything or
2047          doesn't want us to continue.  If we are to continue, walk both
2048          the normal fields and those for the declaration case.  */
2049       result = (*func) (type_p, &walk_subtrees, data);
2050       if (result || !walk_subtrees)
2051         return NULL_TREE;
2052
2053       result = walk_type_fields (*type_p, func, data, pset);
2054       if (result)
2055         return result;
2056
2057       WALK_SUBTREE (TYPE_SIZE (*type_p));
2058       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
2059
2060       /* If this is a record type, also walk the fields.  */
2061       if (TREE_CODE (*type_p) == RECORD_TYPE
2062           || TREE_CODE (*type_p) == UNION_TYPE
2063           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2064         {
2065           tree field;
2066
2067           for (field = TYPE_FIELDS (*type_p); field;
2068                field = TREE_CHAIN (field))
2069             {
2070               /* We'd like to look at the type of the field, but we can easily
2071                  get infinite recursion.  So assume it's pointed to elsewhere
2072                  in the tree.  Also, ignore things that aren't fields.  */
2073               if (TREE_CODE (field) != FIELD_DECL)
2074                 continue;
2075
2076               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
2077               WALK_SUBTREE (DECL_SIZE (field));
2078               WALK_SUBTREE (DECL_SIZE_UNIT (field));
2079               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2080                 WALK_SUBTREE (DECL_QUALIFIER (field));
2081             }
2082         }
2083     }
2084
2085   else if (code != SAVE_EXPR
2086            && code != BIND_EXPR
2087            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2088     {
2089       int i, len;
2090
2091       /* Walk over all the sub-trees of this operand.  */
2092       len = TREE_CODE_LENGTH (code);
2093       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2094          But, we only want to walk once.  */
2095       if (code == TARGET_EXPR
2096           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2097         --len;
2098
2099       /* Go through the subtrees.  We need to do this in forward order so
2100          that the scope of a FOR_EXPR is handled properly.  */
2101 #ifdef DEBUG_WALK_TREE
2102       for (i = 0; i < len; ++i)
2103         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2104 #else
2105       for (i = 0; i < len - 1; ++i)
2106         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2107
2108       if (len)
2109         {
2110           /* The common case is that we may tail recurse here.  */
2111           if (code != BIND_EXPR
2112               && !TREE_CHAIN (*tp))
2113             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
2114           else
2115             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
2116         }
2117 #endif
2118     }
2119
2120   /* If this is a type, walk the needed fields in the type.  */
2121   else if (TYPE_P (*tp))
2122     {
2123       result = walk_type_fields (*tp, func, data, pset);
2124       if (result)
2125         return result;
2126     }
2127   else
2128     {
2129       /* Not one of the easy cases.  We must explicitly go through the
2130          children.  */
2131       switch (code)
2132         {
2133         case ERROR_MARK:
2134         case IDENTIFIER_NODE:
2135         case INTEGER_CST:
2136         case REAL_CST:
2137         case VECTOR_CST:
2138         case STRING_CST:
2139         case BLOCK:
2140         case PLACEHOLDER_EXPR:
2141         case SSA_NAME:
2142         case FIELD_DECL:
2143         case RESULT_DECL:
2144           /* None of thse have subtrees other than those already walked
2145              above.  */
2146           break;
2147
2148         case TREE_LIST:
2149           WALK_SUBTREE (TREE_VALUE (*tp));
2150           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2151           break;
2152
2153         case TREE_VEC:
2154           {
2155             int len = TREE_VEC_LENGTH (*tp);
2156
2157             if (len == 0)
2158               break;
2159
2160             /* Walk all elements but the first.  */
2161             while (--len)
2162               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2163
2164             /* Now walk the first one as a tail call.  */
2165             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2166           }
2167
2168         case COMPLEX_CST:
2169           WALK_SUBTREE (TREE_REALPART (*tp));
2170           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2171
2172         case CONSTRUCTOR:
2173           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2174
2175         case SAVE_EXPR:
2176           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2177
2178         case BIND_EXPR:
2179           {
2180             tree decl;
2181             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2182               {
2183                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2184                    into declarations that are just mentioned, rather than
2185                    declared; they don't really belong to this part of the tree.
2186                    And, we can see cycles: the initializer for a declaration
2187                    can refer to the declaration itself.  */
2188                 WALK_SUBTREE (DECL_INITIAL (decl));
2189                 WALK_SUBTREE (DECL_SIZE (decl));
2190                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2191               }
2192             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2193           }
2194
2195         case STATEMENT_LIST:
2196           {
2197             tree_stmt_iterator i;
2198             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2199               WALK_SUBTREE (*tsi_stmt_ptr (i));
2200           }
2201           break;
2202
2203         default:
2204           /* ??? This could be a language-defined node.  We really should make
2205              a hook for it, but right now just ignore it.  */
2206           break;
2207         }
2208     }
2209
2210   /* We didn't find what we were looking for.  */
2211   return NULL_TREE;
2212
2213 #undef WALK_SUBTREE
2214 #undef WALK_SUBTREE_TAIL
2215 }
2216
2217 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
2218
2219 tree
2220 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2221 {
2222   tree result;
2223   struct pointer_set_t *pset;
2224
2225   pset = pointer_set_create ();
2226   result = walk_tree (tp, func, data, pset);
2227   pointer_set_destroy (pset);
2228   return result;
2229 }
2230
2231 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2232
2233 tree
2234 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2235 {
2236   enum tree_code code = TREE_CODE (*tp);
2237
2238   /* We make copies of most nodes.  */
2239   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2240       || code == TREE_LIST
2241       || code == TREE_VEC
2242       || code == TYPE_DECL)
2243     {
2244       /* Because the chain gets clobbered when we make a copy, we save it
2245          here.  */
2246       tree chain = TREE_CHAIN (*tp);
2247       tree new;
2248
2249       /* Copy the node.  */
2250       new = copy_node (*tp);
2251
2252       /* Propagate mudflap marked-ness.  */
2253       if (flag_mudflap && mf_marked_p (*tp))
2254         mf_mark (new);
2255
2256       *tp = new;
2257
2258       /* Now, restore the chain, if appropriate.  That will cause
2259          walk_tree to walk into the chain as well.  */
2260       if (code == PARM_DECL || code == TREE_LIST)
2261         TREE_CHAIN (*tp) = chain;
2262
2263       /* For now, we don't update BLOCKs when we make copies.  So, we
2264          have to nullify all BIND_EXPRs.  */
2265       if (TREE_CODE (*tp) == BIND_EXPR)
2266         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2267     }
2268
2269   else if (TREE_CODE_CLASS (code) == tcc_type)
2270     *walk_subtrees = 0;
2271   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2272     *walk_subtrees = 0;
2273   else if (TREE_CODE_CLASS (code) == tcc_constant)
2274     *walk_subtrees = 0;
2275   else
2276     gcc_assert (code != STATEMENT_LIST);
2277   return NULL_TREE;
2278 }
2279
2280 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2281    information indicating to what new SAVE_EXPR this one should be mapped,
2282    use that one.  Otherwise, create a new node and enter it in ST.  */
2283
2284 static void
2285 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2286 {
2287   splay_tree st = (splay_tree) st_;
2288   splay_tree_node n;
2289   tree t;
2290
2291   /* See if we already encountered this SAVE_EXPR.  */
2292   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2293
2294   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2295   if (!n)
2296     {
2297       t = copy_node (*tp);
2298
2299       /* Remember this SAVE_EXPR.  */
2300       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2301       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2302       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2303     }
2304   else
2305     {
2306       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2307       *walk_subtrees = 0;
2308       t = (tree) n->value;
2309     }
2310
2311   /* Replace this SAVE_EXPR with the copy.  */
2312   *tp = t;
2313 }
2314
2315 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2316    copies the declaration and enters it in the splay_tree in DATA (which is
2317    really an `inline_data *').  */
2318
2319 static tree
2320 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2321                         void *data)
2322 {
2323   inline_data *id = (inline_data *) data;
2324
2325   /* Don't walk into types.  */
2326   if (TYPE_P (*tp))
2327     *walk_subtrees = 0;
2328
2329   else if (TREE_CODE (*tp) == LABEL_EXPR)
2330     {
2331       tree decl = TREE_OPERAND (*tp, 0);
2332
2333       /* Copy the decl and remember the copy.  */
2334       insert_decl_map (id, decl,
2335                        copy_decl_for_inlining (decl, DECL_CONTEXT (decl),
2336                                                DECL_CONTEXT (decl)));
2337     }
2338
2339   return NULL_TREE;
2340 }
2341
2342 /* Perform any modifications to EXPR required when it is unsaved.  Does
2343    not recurse into EXPR's subtrees.  */
2344
2345 static void
2346 unsave_expr_1 (tree expr)
2347 {
2348   switch (TREE_CODE (expr))
2349     {
2350     case TARGET_EXPR:
2351       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2352          It's OK for this to happen if it was part of a subtree that
2353          isn't immediately expanded, such as operand 2 of another
2354          TARGET_EXPR.  */
2355       if (TREE_OPERAND (expr, 1))
2356         break;
2357
2358       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2359       TREE_OPERAND (expr, 3) = NULL_TREE;
2360       break;
2361
2362     default:
2363       break;
2364     }
2365 }
2366
2367 /* Called via walk_tree when an expression is unsaved.  Using the
2368    splay_tree pointed to by ST (which is really a `splay_tree'),
2369    remaps all local declarations to appropriate replacements.  */
2370
2371 static tree
2372 unsave_r (tree *tp, int *walk_subtrees, void *data)
2373 {
2374   inline_data *id = (inline_data *) data;
2375   splay_tree st = id->decl_map;
2376   splay_tree_node n;
2377
2378   /* Only a local declaration (variable or label).  */
2379   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2380       || TREE_CODE (*tp) == LABEL_DECL)
2381     {
2382       /* Lookup the declaration.  */
2383       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2384
2385       /* If it's there, remap it.  */
2386       if (n)
2387         *tp = (tree) n->value;
2388     }
2389
2390   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2391     copy_statement_list (tp);
2392   else if (TREE_CODE (*tp) == BIND_EXPR)
2393     copy_bind_expr (tp, walk_subtrees, id);
2394   else if (TREE_CODE (*tp) == SAVE_EXPR)
2395     remap_save_expr (tp, st, walk_subtrees);
2396   else
2397     {
2398       copy_tree_r (tp, walk_subtrees, NULL);
2399
2400       /* Do whatever unsaving is required.  */
2401       unsave_expr_1 (*tp);
2402     }
2403
2404   /* Keep iterating.  */
2405   return NULL_TREE;
2406 }
2407
2408 /* Copies everything in EXPR and replaces variables, labels
2409    and SAVE_EXPRs local to EXPR.  */
2410
2411 tree
2412 unsave_expr_now (tree expr)
2413 {
2414   inline_data id;
2415
2416   /* There's nothing to do for NULL_TREE.  */
2417   if (expr == 0)
2418     return expr;
2419
2420   /* Set up ID.  */
2421   memset (&id, 0, sizeof (id));
2422   VARRAY_TREE_INIT (id.fns, 1, "fns");
2423   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2424   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2425
2426   /* Walk the tree once to find local labels.  */
2427   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2428
2429   /* Walk the tree again, copying, remapping, and unsaving.  */
2430   walk_tree (&expr, unsave_r, &id, NULL);
2431
2432   /* Clean up.  */
2433   splay_tree_delete (id.decl_map);
2434
2435   return expr;
2436 }
2437
2438 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2439
2440 static tree
2441 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2442 {
2443   if (*tp == data)
2444     return (tree) data;
2445   else
2446     return NULL;
2447 }
2448
2449 bool
2450 debug_find_tree (tree top, tree search)
2451 {
2452   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2453 }
2454
2455 /* Declare the variables created by the inliner.  Add all the variables in
2456    VARS to BIND_EXPR.  */
2457
2458 static void
2459 declare_inline_vars (tree bind_expr, tree vars)
2460 {
2461   tree t;
2462   for (t = vars; t; t = TREE_CHAIN (t))
2463     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2464
2465   add_var_to_bind_expr (bind_expr, vars);
2466 }