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