gcc/tree-inline.c

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