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