gcc/tree-inline.c

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