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