gcc/tree-inline.c

   1 /* Tree inlining.
   2    Copyright 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Alexandre Oliva <aoliva@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "toplev.h"
  27 #include "tree.h"
  28 #include "tree-inline.h"
  29 #include "rtl.h"
  30 #include "expr.h"
  31 #include "flags.h"
  32 #include "params.h"
  33 #include "input.h"
  34 #include "insn-config.h"
  35 #include "integrate.h"
  36 #include "varray.h"
  37 #include "hashtab.h"
  38 #include "splay-tree.h"
  39 #include "langhooks.h"
  40 #include "cgraph.h"
  41 #include "intl.h"
  42 #include "tree-mudflap.h"
  43 #include "function.h"
  44 #include "diagnostic.h"
  45
  46 /* I'm not real happy about this, but we need to handle gimple and
  47    non-gimple trees.  */
  48 #include "tree-iterator.h"
  49 #include "tree-gimple.h"
  50
  51 /* 0 if we should not perform inlining.
  52    1 if we should expand functions calls inline at the tree level.
  53    2 if we should consider *all* functions to be inline
  54    candidates.  */
  55
  56 int flag_inline_trees = 0;
  57
  58 /* To Do:
  59
  60    o In order to make inlining-on-trees work, we pessimized
  61      function-local static constants.  In particular, they are now
  62      always output, even when not addressed.  Fix this by treating
  63      function-local static constants just like global static
  64      constants; the back-end already knows not to output them if they
  65      are not needed.
  66
  67    o Provide heuristics to clamp inlining of recursive template
  68      calls?  */
  69
  70 /* Data required for function inlining.  */
  71
  72 typedef struct inline_data
  73 {
  74   /* A stack of the functions we are inlining.  For example, if we are
  75      compiling `f', which calls `g', which calls `h', and we are
  76      inlining the body of `h', the stack will contain, `h', followed
  77      by `g', followed by `f'.  The first few elements of the stack may
  78      contain other functions that we know we should not recurse into,
  79      even though they are not directly being inlined.  */
  80   varray_type fns;
  81   /* The index of the first element of FNS that really represents an
  82      inlined function.  */
  83   unsigned first_inlined_fn;
  84   /* The label to jump to when a return statement is encountered.  If
  85      this value is NULL, then return statements will simply be
  86      remapped as return statements, rather than as jumps.  */
  87   tree ret_label;
  88   /* The VAR_DECL for the return value.  */
  89   tree retvar;
  90   /* The map from local declarations in the inlined function to
  91      equivalents in the function into which it is being inlined.  */
  92   splay_tree decl_map;
  93   /* Nonzero if we are currently within the cleanup for a
  94      TARGET_EXPR.  */
  95   int in_target_cleanup_p;
  96   /* A list of the functions current function has inlined.  */
  97   varray_type inlined_fns;
  98   /* We use the same mechanism to build clones that we do to perform
  99      inlining.  However, there are a few places where we need to
 100      distinguish between those two situations.  This flag is true if
 101      we are cloning, rather than inlining.  */
 102   bool cloning_p;
 103   /* Similarly for saving function body.  */
 104   bool saving_p;
 105   /* Hash table used to prevent walk_tree from visiting the same node
 106      umpteen million times.  */
 107   htab_t tree_pruner;
 108   /* Callgraph node of function we are inlining into.  */
 109   struct cgraph_node *node;
 110   /* Callgraph node of currently inlined function.  */
 111   struct cgraph_node *current_node;
 112   /* Statement iterator.  We need this so we can keep the tree in
 113      gimple form when we insert the inlined function.   It is not
 114      used when we are not dealing with gimple trees.  */
 115   tree_stmt_iterator tsi;
 116 } inline_data;
 117
 118 /* Prototypes.  */
 119
 120 /* The approximate number of instructions per statement.  This number
 121    need not be particularly accurate; it is used only to make
 122    decisions about when a function is too big to inline.  */
 123 #define INSNS_PER_STMT (10)
 124
 125 static tree copy_body_r (tree *, int *, void *);
 126 static tree copy_body (inline_data *);
 127 static tree expand_call_inline (tree *, int *, void *);
 128 static void expand_calls_inline (tree *, inline_data *);
 129 static bool inlinable_function_p (tree);
 130 static tree remap_decl (tree, inline_data *);
 131 static tree remap_type (tree, inline_data *);
 132 static tree initialize_inlined_parameters (inline_data *, tree,
 133                                            tree, tree, tree);
 134 static void remap_block (tree *, inline_data *);
 135 static tree remap_decls (tree, inline_data *);
 136 static void copy_bind_expr (tree *, int *, inline_data *);
 137 static tree mark_local_for_remap_r (tree *, int *, void *);
 138 static void unsave_expr_1 (tree);
 139 static tree unsave_r (tree *, int *, void *);
 140 static void declare_inline_vars (tree bind_expr, tree vars);
 141
 142 /* Insert a tree->tree mapping for ID.  Despite the name suggests
 143    that the trees should be variables, it is used for more than that.  */
 144
 145 static void
 146 insert_decl_map (inline_data *id, tree key, tree value)
 147 {
 148   splay_tree_insert (id->decl_map, (splay_tree_key) key,
 149                      (splay_tree_value) value);
 150
 151   /* Always insert an identity map as well.  If we see this same new
 152      node again, we won't want to duplicate it a second time.  */
 153   if (key != value)
 154     splay_tree_insert (id->decl_map, (splay_tree_key) value,
 155                        (splay_tree_value) value);
 156 }
 157
 158 /* Remap DECL during the copying of the BLOCK tree for the function.
 159    We are only called to remap local variables in the current function.  */
 160
 161 static tree
 162 remap_decl (tree decl, inline_data *id)
 163 {
 164   splay_tree_node n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 165   tree fn = VARRAY_TOP_TREE (id->fns);
 166
 167   /* See if we have remapped this declaration.  If we didn't already have an
 168      equivalent for this declaration, create one now.  */
 169   if (!n)
 170     {
 171       /* Make a copy of the variable or label.  */
 172       tree t = copy_decl_for_inlining (decl, fn, VARRAY_TREE (id->fns, 0));
 173
 174       /* Remap types, if necessary.  */
 175       TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
 176       if (TREE_CODE (t) == TYPE_DECL)
 177         DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
 178       else if (TREE_CODE (t) == PARM_DECL)
 179         DECL_ARG_TYPE_AS_WRITTEN (t)
 180           = remap_type (DECL_ARG_TYPE_AS_WRITTEN (t), id);
 181
 182       /* Remap sizes as necessary.  */
 183       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 184       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 185
 186       /* If fields, do likewise for offset and qualifier. */
 187       if (TREE_CODE (t) == FIELD_DECL)
 188         {
 189           walk_tree (&DECL_FIELD_OFFSET (t), copy_body_r, id, NULL);
 190           if (TREE_CODE (DECL_CONTEXT (t)) == QUAL_UNION_TYPE)
 191             walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
 192         }
 193
 194 #if 0
 195       /* FIXME handle anon aggrs.  */
 196       if (! DECL_NAME (t) && TREE_TYPE (t)
 197           && lang_hooks.tree_inlining.anon_aggr_type_p (TREE_TYPE (t)))
 198         {
 199           /* For a VAR_DECL of anonymous type, we must also copy the
 200              member VAR_DECLS here and rechain the DECL_ANON_UNION_ELEMS.  */
 201           tree members = NULL;
 202           tree src;
 203
 204           for (src = DECL_ANON_UNION_ELEMS (t); src;
 205                src = TREE_CHAIN (src))
 206             {
 207               tree member = remap_decl (TREE_VALUE (src), id);
 208
 209               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) == BIND_EXPR)
 523     copy_bind_expr (tp, walk_subtrees, id);
 524   else if (TREE_CODE (*tp) == LABELED_BLOCK_EXPR)
 525     {
 526       /* We need a new copy of this labeled block; the EXIT_BLOCK_EXPR
 527          will refer to it, so save a copy ready for remapping.  We
 528          save it in the decl_map, although it isn't a decl.  */
 529       tree new_block = copy_node (*tp);
 530       insert_decl_map (id, *tp, new_block);
 531       *tp = new_block;
 532     }
 533   else if (TREE_CODE (*tp) == EXIT_BLOCK_EXPR)
 534     {
 535       splay_tree_node n
 536         = splay_tree_lookup (id->decl_map,
 537                              (splay_tree_key) TREE_OPERAND (*tp, 0));
 538       /* We _must_ have seen the enclosing LABELED_BLOCK_EXPR.  */
 539       if (! n)
 540         abort ();
 541       *tp = copy_node (*tp);
 542       TREE_OPERAND (*tp, 0) = (tree) n->value;
 543     }
 544   /* Types may need remapping as well.  */
 545   else if (TYPE_P (*tp))
 546     *tp = remap_type (*tp, id);
 547
 548   /* Otherwise, just copy the node.  Note that copy_tree_r already
 549      knows not to copy VAR_DECLs, etc., so this is safe.  */
 550   else
 551     {
 552       tree old_node = *tp;
 553
 554       if (TREE_CODE (*tp) == MODIFY_EXPR
 555           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 556           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 557               (TREE_OPERAND (*tp, 0), fn)))
 558         {
 559           /* Some assignments VAR = VAR; don't generate any rtl code
 560              and thus don't count as variable modification.  Avoid
 561              keeping bogosities like 0 = 0.  */
 562           tree decl = TREE_OPERAND (*tp, 0), value;
 563           splay_tree_node n;
 564
 565           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 566           if (n)
 567             {
 568               value = (tree) n->value;
 569               STRIP_TYPE_NOPS (value);
 570               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 571                 {
 572                   *tp = value;
 573                   return copy_body_r (tp, walk_subtrees, data);
 574                 }
 575             }
 576         }
 577       else if (TREE_CODE (*tp) == INDIRECT_REF)
 578         {
 579           /* Get rid of *& from inline substitutions that can happen when a
 580              pointer argument is an ADDR_EXPR.  */
 581           tree decl = TREE_OPERAND (*tp, 0), value;
 582           splay_tree_node n;
 583
 584           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 585           if (n)
 586             {
 587               value = (tree) n->value;
 588               STRIP_NOPS (value);
 589               if (TREE_CODE (value) == ADDR_EXPR
 590                   && (lang_hooks.types_compatible_p
 591                       (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0)))))
 592                 {
 593                   *tp = TREE_OPERAND (value, 0);
 594                   return copy_body_r (tp, walk_subtrees, data);
 595                 }
 596             }
 597         }
 598
 599       copy_tree_r (tp, walk_subtrees, NULL);
 600
 601       if (TREE_CODE (*tp) == CALL_EXPR && id->node && get_callee_fndecl (*tp))
 602         {
 603           if (id->saving_p)
 604             {
 605               struct cgraph_node *node;
 606               struct cgraph_edge *edge;
 607
 608               for (node = id->node->next_clone; node; node = node->next_clone)
 609                 {
 610                   edge = cgraph_edge (node, old_node);
 611                   if (edge)
 612                     edge->call_expr = *tp;
 613                   else
 614                     abort ();
 615                 }
 616             }
 617           else
 618             {
 619               struct cgraph_edge *edge
 620                 = cgraph_edge (id->current_node, old_node);
 621
 622               if (edge)
 623                 cgraph_clone_edge (edge, id->node, *tp);
 624             }
 625         }
 626
 627       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 628
 629       /* The copied TARGET_EXPR has never been expanded, even if the
 630          original node was expanded already.  */
 631       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 632         {
 633           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 634           TREE_OPERAND (*tp, 3) = NULL_TREE;
 635         }
 636     }
 637
 638   /* Keep iterating.  */
 639   return NULL_TREE;
 640 }
 641
 642 /* Make a copy of the body of FN so that it can be inserted inline in
 643    another function.  */
 644
 645 static tree
 646 copy_body (inline_data *id)
 647 {
 648   tree body;
 649   tree fndecl = VARRAY_TOP_TREE (id->fns);
 650
 651   if (fndecl == current_function_decl
 652       && cfun->saved_tree)
 653     body = cfun->saved_tree;
 654   else
 655     body = DECL_SAVED_TREE (fndecl);
 656   walk_tree (&body, copy_body_r, id, NULL);
 657
 658   return body;
 659 }
 660
 661 static void
 662 setup_one_parameter (inline_data *id, tree p, tree value, tree fn,
 663                      tree *init_stmts, tree *vars, bool *gimplify_init_stmts_p)
 664 {
 665   tree init_stmt;
 666   tree var;
 667
 668   /* If the parameter is never assigned to, we may not need to
 669      create a new variable here at all.  Instead, we may be able
 670      to just use the argument value.  */
 671   if (TREE_READONLY (p)
 672       && !TREE_ADDRESSABLE (p)
 673       && value && !TREE_SIDE_EFFECTS (value))
 674     {
 675       /* We can't risk substituting complex expressions.  They
 676          might contain variables that will be assigned to later.
 677          Theoretically, we could check the expression to see if
 678          all of the variables that determine its value are
 679          read-only, but we don't bother.  */
 680       /* We may produce non-gimple trees by adding NOPs or introduce
 681          invalid sharing when operand is not really constant.
 682          It is not big deal to prohibit constant propagation here as
 683          we will constant propagate in DOM1 pass anyway.  */
 684       if (is_gimple_min_invariant (value)
 685           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p)))
 686         {
 687           insert_decl_map (id, p, value);
 688           return;
 689         }
 690     }
 691
 692   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
 693      here since the type of this decl must be visible to the calling
 694      function. */
 695   var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 696
 697   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 698      that way, when the PARM_DECL is encountered, it will be
 699      automatically replaced by the VAR_DECL.  */
 700   insert_decl_map (id, p, var);
 701
 702   /* Declare this new variable.  */
 703   TREE_CHAIN (var) = *vars;
 704   *vars = var;
 705
 706   /* Make gimplifier happy about this variable.  */
 707   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 708
 709   /* Even if P was TREE_READONLY, the new VAR should not be.
 710      In the original code, we would have constructed a
 711      temporary, and then the function body would have never
 712      changed the value of P.  However, now, we will be
 713      constructing VAR directly.  The constructor body may
 714      change its value multiple times as it is being
 715      constructed.  Therefore, it must not be TREE_READONLY;
 716      the back-end assumes that TREE_READONLY variable is
 717      assigned to only once.  */
 718   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 719     TREE_READONLY (var) = 0;
 720
 721   /* Initialize this VAR_DECL from the equivalent argument.  Convert
 722      the argument to the proper type in case it was promoted.  */
 723   if (value)
 724     {
 725       tree rhs = fold_convert (TREE_TYPE (var), value);
 726
 727       if (rhs == error_mark_node)
 728         return;
 729
 730       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
 731          keep our trees in gimple form.  */
 732       init_stmt = build (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
 733       append_to_statement_list (init_stmt, init_stmts);
 734
 735       /* If we did not create a gimple value and we did not create a gimple
 736          cast of a gimple value, then we will need to gimplify INIT_STMTS
 737          at the end.  Note that is_gimple_cast only checks the outer
 738          tree code, not its operand.  Thus the explicit check that it's
 739          operand is a gimple value.  */
 740       if (!is_gimple_val (rhs)
 741           && (!is_gimple_cast (rhs)
 742               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
 743         *gimplify_init_stmts_p = true;
 744     }
 745 }
 746
 747 /* Generate code to initialize the parameters of the function at the
 748    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 749
 750 static tree
 751 initialize_inlined_parameters (inline_data *id, tree args, tree static_chain,
 752                                tree fn, tree bind_expr)
 753 {
 754   tree init_stmts = NULL_TREE;
 755   tree parms;
 756   tree a;
 757   tree p;
 758   tree vars = NULL_TREE;
 759   bool gimplify_init_stmts_p = false;
 760   int argnum = 0;
 761
 762   /* Figure out what the parameters are.  */
 763   parms = DECL_ARGUMENTS (fn);
 764   if (fn == current_function_decl)
 765     parms = cfun->saved_args;
 766
 767   /* Loop through the parameter declarations, replacing each with an
 768      equivalent VAR_DECL, appropriately initialized.  */
 769   for (p = parms, a = args; p;
 770        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 771     {
 772       tree value;
 773
 774       ++argnum;
 775
 776       /* Find the initializer.  */
 777       value = lang_hooks.tree_inlining.convert_parm_for_inlining
 778               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
 779
 780       setup_one_parameter (id, p, value, fn, &init_stmts, &vars,
 781                            &gimplify_init_stmts_p);
 782     }
 783
 784   /* Evaluate trailing arguments.  */
 785   for (; a; a = TREE_CHAIN (a))
 786     {
 787       tree value = TREE_VALUE (a);
 788       append_to_statement_list (value, &init_stmts);
 789     }
 790
 791   /* Initialize the static chain.  */
 792   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
 793   if (p)
 794     {
 795       /* No static chain?  Seems like a bug in tree-nested.c.  */
 796       if (!static_chain)
 797         abort ();
 798
 799        setup_one_parameter (id, p, static_chain, fn, &init_stmts, &vars,
 800                             &gimplify_init_stmts_p);
 801     }
 802
 803   if (gimplify_init_stmts_p)
 804     gimplify_body (&init_stmts, current_function_decl);
 805
 806   declare_inline_vars (bind_expr, vars);
 807   return init_stmts;
 808 }
 809
 810 /* Declare a return variable to replace the RESULT_DECL for the function we
 811    are calling.  RETURN_SLOT_ADDR, if non-null, was a fake parameter that
 812    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
 813    the MODIFY_EXPR to which this call is the RHS.
 814
 815    The return value is a (possibly null) value that is the result of the
 816    function as seen by the callee.  *USE_P is a (possibly null) value that
 817    holds the result as seen by the caller.  */
 818
 819 static tree
 820 declare_return_variable (inline_data *id, tree return_slot_addr,
 821                          tree modify_dest, tree *use_p)
 822 {
 823   tree callee = VARRAY_TOP_TREE (id->fns);
 824   tree caller = VARRAY_TREE (id->fns, 0);
 825   tree result = DECL_RESULT (callee);
 826   tree callee_type = TREE_TYPE (result);
 827   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
 828   tree var, use;
 829
 830   /* We don't need to do anything for functions that don't return
 831      anything.  */
 832   if (!result || VOID_TYPE_P (callee_type))
 833     {
 834       *use_p = NULL_TREE;
 835       return NULL_TREE;
 836     }
 837
 838   /* If there was a return slot, then the return value is the
 839      dereferenced address of that object.  */
 840   if (return_slot_addr)
 841     {
 842       /* The front end shouldn't have used both return_slot_addr and
 843          a modify expression.  */
 844       if (modify_dest)
 845         abort ();
 846       if (DECL_BY_REFERENCE (result))
 847         var = return_slot_addr;
 848       else
 849         var = build_fold_indirect_ref (return_slot_addr);
 850       use = NULL;
 851       goto done;
 852     }
 853
 854   /* All types requiring non-trivial constructors should have been handled.  */
 855   if (TREE_ADDRESSABLE (callee_type))
 856     abort ();
 857
 858   /* Attempt to avoid creating a new temporary variable.  */
 859   if (modify_dest)
 860     {
 861       bool use_it = false;
 862
 863       /* We can't use MODIFY_DEST if there's type promotion involved.  */
 864       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
 865         use_it = false;
 866
 867       /* ??? If we're assigning to a variable sized type, then we must
 868          reuse the destination variable, because we've no good way to
 869          create variable sized temporaries at this point.  */
 870       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
 871         use_it = true;
 872
 873       /* If the callee cannot possibly modify MODIFY_DEST, then we can
 874          reuse it as the result of the call directly.  Don't do this if
 875          it would promote MODIFY_DEST to addressable.  */
 876       else if (!TREE_STATIC (modify_dest)
 877                && !TREE_ADDRESSABLE (modify_dest)
 878                && !TREE_ADDRESSABLE (result))
 879         use_it = true;
 880
 881       if (use_it)
 882         {
 883           var = modify_dest;
 884           use = NULL;
 885           goto done;
 886         }
 887     }
 888
 889   if (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) != INTEGER_CST)
 890     abort ();
 891
 892   var = copy_decl_for_inlining (result, callee, caller);
 893   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 894   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
 895     = tree_cons (NULL_TREE, var,
 896                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
 897
 898   /* Do not have the rest of GCC warn about this variable as it should
 899      not be visible to the user.   */
 900   TREE_NO_WARNING (var) = 1;
 901
 902   /* Build the use expr.  If the return type of the function was
 903      promoted, convert it back to the expected type.  */
 904   use = var;
 905   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
 906     use = fold_convert (caller_type, var);
 907
 908  done:
 909   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 910      way, when the RESULT_DECL is encountered, it will be
 911      automatically replaced by the VAR_DECL.  */
 912   insert_decl_map (id, result, var);
 913
 914   /* Remember this so we can ignore it in remap_decls.  */
 915   id->retvar = var;
 916
 917   *use_p = use;
 918   return var;
 919 }
 920
 921 /* Returns nonzero if a function can be inlined as a tree.  */
 922
 923 bool
 924 tree_inlinable_function_p (tree fn)
 925 {
 926   return inlinable_function_p (fn);
 927 }
 928
 929 static const char *inline_forbidden_reason;
 930
 931 static tree
 932 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
 933                       void *fnp)
 934 {
 935   tree node = *nodep;
 936   tree fn = (tree) fnp;
 937   tree t;
 938
 939   switch (TREE_CODE (node))
 940     {
 941     case CALL_EXPR:
 942       /* Refuse to inline alloca call unless user explicitly forced so as
 943          this may change program's memory overhead drastically when the
 944          function using alloca is called in loop.  In GCC present in
 945          SPEC2000 inlining into schedule_block cause it to require 2GB of
 946          RAM instead of 256MB.  */
 947       if (alloca_call_p (node)
 948           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
 949         {
 950           inline_forbidden_reason
 951             = N_("%Jfunction '%F' can never be inlined because it uses "
 952                  "alloca (override using the always_inline attribute)");
 953           return node;
 954         }
 955       t = get_callee_fndecl (node);
 956       if (! t)
 957         break;
 958
 959       /* We cannot inline functions that call setjmp.  */
 960       if (setjmp_call_p (t))
 961         {
 962           inline_forbidden_reason
 963             = N_("%Jfunction '%F' can never be inlined because it uses setjmp");
 964           return node;
 965         }
 966
 967       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
 968         switch (DECL_FUNCTION_CODE (t))
 969           {
 970             /* We cannot inline functions that take a variable number of
 971                arguments.  */
 972           case BUILT_IN_VA_START:
 973           case BUILT_IN_STDARG_START:
 974           case BUILT_IN_NEXT_ARG:
 975           case BUILT_IN_VA_END:
 976             inline_forbidden_reason
 977               = N_("%Jfunction '%F' can never be inlined because it "
 978                    "uses variable argument lists");
 979             return node;
 980
 981           case BUILT_IN_LONGJMP:
 982             /* We can't inline functions that call __builtin_longjmp at
 983                all.  The non-local goto machinery really requires the
 984                destination be in a different function.  If we allow the
 985                function calling __builtin_longjmp to be inlined into the
 986                function calling __builtin_setjmp, Things will Go Awry.  */
 987             inline_forbidden_reason
 988               = N_("%Jfunction '%F' can never be inlined because "
 989                    "it uses setjmp-longjmp exception handling");
 990             return node;
 991
 992           case BUILT_IN_NONLOCAL_GOTO:
 993             /* Similarly.  */
 994             inline_forbidden_reason
 995               = N_("%Jfunction '%F' can never be inlined because "
 996                    "it uses non-local goto");
 997             return node;
 998
 999           default:
1000             break;
1001           }
1002       break;
1003
1004     case BIND_EXPR:
1005       for (t = BIND_EXPR_VARS (node); t ; t = TREE_CHAIN (t))
1006         {
1007           /* We cannot inline functions that contain other functions.  */
1008           if (TREE_CODE (t) == FUNCTION_DECL && DECL_INITIAL (t))
1009             {
1010               inline_forbidden_reason
1011                 = N_("%Jfunction '%F' can never be inlined "
1012                      "because it contains a nested function");
1013               return node;
1014             }
1015         }
1016       break;
1017
1018     case GOTO_EXPR:
1019       t = TREE_OPERAND (node, 0);
1020
1021       /* We will not inline a function which uses computed goto.  The
1022          addresses of its local labels, which may be tucked into
1023          global storage, are of course not constant across
1024          instantiations, which causes unexpected behavior.  */
1025       if (TREE_CODE (t) != LABEL_DECL)
1026         {
1027           inline_forbidden_reason
1028             = N_("%Jfunction '%F' can never be inlined "
1029                  "because it contains a computed goto");
1030           return node;
1031         }
1032       break;
1033
1034     case LABEL_EXPR:
1035       t = TREE_OPERAND (node, 0);
1036       if (DECL_NONLOCAL (t))
1037         {
1038           /* We cannot inline a function that receives a non-local goto
1039              because we cannot remap the destination label used in the
1040              function that is performing the non-local goto.  */
1041           inline_forbidden_reason
1042             = N_("%Jfunction '%F' can never be inlined "
1043                  "because it receives a non-local goto");
1044           return node;
1045         }
1046       break;
1047
1048     case RECORD_TYPE:
1049     case UNION_TYPE:
1050       /* We cannot inline a function of the form
1051
1052            void F (int i) { struct S { int ar[i]; } s; }
1053
1054          Attempting to do so produces a catch-22.
1055          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1056          UNION_TYPE nodes, then it goes into infinite recursion on a
1057          structure containing a pointer to its own type.  If it doesn't,
1058          then the type node for S doesn't get adjusted properly when
1059          F is inlined, and we abort in find_function_data.  */
1060       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1061         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1062           {
1063             inline_forbidden_reason
1064               = N_("%Jfunction '%F' can never be inlined "
1065                    "because it uses variable sized variables");
1066             return node;
1067           }
1068
1069     default:
1070       break;
1071     }
1072
1073   return NULL_TREE;
1074 }
1075
1076 /* Return subexpression representing possible alloca call, if any.  */
1077 static tree
1078 inline_forbidden_p (tree fndecl)
1079 {
1080   location_t saved_loc = input_location;
1081   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1082                                            inline_forbidden_p_1, fndecl);
1083
1084   input_location = saved_loc;
1085   return ret;
1086 }
1087
1088 /* Returns nonzero if FN is a function that does not have any
1089    fundamental inline blocking properties.  */
1090
1091 static bool
1092 inlinable_function_p (tree fn)
1093 {
1094   bool inlinable = true;
1095
1096   /* If we've already decided this function shouldn't be inlined,
1097      there's no need to check again.  */
1098   if (DECL_UNINLINABLE (fn))
1099     return false;
1100
1101   /* See if there is any language-specific reason it cannot be
1102      inlined.  (It is important that this hook be called early because
1103      in C++ it may result in template instantiation.)
1104      If the function is not inlinable for language-specific reasons,
1105      it is left up to the langhook to explain why.  */
1106   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1107
1108   /* If we don't have the function body available, we can't inline it.
1109      However, this should not be recorded since we also get here for
1110      forward declared inline functions.  Therefore, return at once.  */
1111   if (!DECL_SAVED_TREE (fn))
1112     return false;
1113
1114   /* If we're not inlining at all, then we cannot inline this function.  */
1115   else if (!flag_inline_trees)
1116     inlinable = false;
1117
1118   /* Only try to inline functions if DECL_INLINE is set.  This should be
1119      true for all functions declared `inline', and for all other functions
1120      as well with -finline-functions.
1121
1122      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1123      it's the front-end that must set DECL_INLINE in this case, because
1124      dwarf2out loses if a function that does not have DECL_INLINE set is
1125      inlined anyway.  That is why we have both DECL_INLINE and
1126      DECL_DECLARED_INLINE_P.  */
1127   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1128             here should be redundant.  */
1129   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1130     inlinable = false;
1131
1132   else if (inline_forbidden_p (fn))
1133     {
1134       /* See if we should warn about uninlinable functions.  Previously,
1135          some of these warnings would be issued while trying to expand
1136          the function inline, but that would cause multiple warnings
1137          about functions that would for example call alloca.  But since
1138          this a property of the function, just one warning is enough.
1139          As a bonus we can now give more details about the reason why a
1140          function is not inlinable.
1141          We only warn for functions declared `inline' by the user.  */
1142       bool do_warning = (warn_inline
1143                          && DECL_INLINE (fn)
1144                          && DECL_DECLARED_INLINE_P (fn)
1145                          && !DECL_IN_SYSTEM_HEADER (fn));
1146
1147       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1148         sorry (inline_forbidden_reason, fn, fn);
1149       else if (do_warning)
1150         warning (inline_forbidden_reason, fn, fn);
1151
1152       inlinable = false;
1153     }
1154
1155   /* Squirrel away the result so that we don't have to check again.  */
1156   DECL_UNINLINABLE (fn) = !inlinable;
1157
1158   return inlinable;
1159 }
1160
1161 /* Used by estimate_num_insns.  Estimate number of instructions seen
1162    by given statement.  */
1163
1164 static tree
1165 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1166 {
1167   int *count = data;
1168   tree x = *tp;
1169
1170   if (TYPE_P (x) || DECL_P (x))
1171     {
1172       *walk_subtrees = 0;
1173       return NULL;
1174     }
1175   /* Assume that constants and references counts nothing.  These should
1176      be majorized by amount of operations among them we count later
1177      and are common target of CSE and similar optimizations.  */
1178   else if (TREE_CODE_CLASS (TREE_CODE (x)) == 'c'
1179            || TREE_CODE_CLASS (TREE_CODE (x)) == 'r')
1180     return NULL;
1181
1182   switch (TREE_CODE (x))
1183     {
1184     /* Containers have no cost.  */
1185     case TREE_LIST:
1186     case TREE_VEC:
1187     case BLOCK:
1188     case COMPONENT_REF:
1189     case BIT_FIELD_REF:
1190     case INDIRECT_REF:
1191     case ARRAY_REF:
1192     case ARRAY_RANGE_REF:
1193     case OBJ_TYPE_REF:
1194     case EXC_PTR_EXPR: /* ??? */
1195     case FILTER_EXPR: /* ??? */
1196     case COMPOUND_EXPR:
1197     case BIND_EXPR:
1198     case LABELED_BLOCK_EXPR:
1199     case WITH_CLEANUP_EXPR:
1200     case NOP_EXPR:
1201     case VIEW_CONVERT_EXPR:
1202     case SAVE_EXPR:
1203     case ADDR_EXPR:
1204     case COMPLEX_EXPR:
1205     case EXIT_BLOCK_EXPR:
1206     case CASE_LABEL_EXPR:
1207     case SSA_NAME:
1208     case CATCH_EXPR:
1209     case EH_FILTER_EXPR:
1210     case STATEMENT_LIST:
1211     case ERROR_MARK:
1212     case NON_LVALUE_EXPR:
1213     case FDESC_EXPR:
1214     case VA_ARG_EXPR:
1215     case TRY_CATCH_EXPR:
1216     case TRY_FINALLY_EXPR:
1217     case LABEL_EXPR:
1218     case GOTO_EXPR:
1219     case RETURN_EXPR:
1220     case EXIT_EXPR:
1221     case LOOP_EXPR:
1222     case PHI_NODE:
1223     case WITH_SIZE_EXPR:
1224       break;
1225
1226     /* We don't account constants for now.  Assume that the cost is amortized
1227        by operations that do use them.  We may re-consider this decision once
1228        we are able to optimize the tree before estimating it's size and break
1229        out static initializers.  */
1230     case IDENTIFIER_NODE:
1231     case INTEGER_CST:
1232     case REAL_CST:
1233     case COMPLEX_CST:
1234     case VECTOR_CST:
1235     case STRING_CST:
1236       *walk_subtrees = 0;
1237       return NULL;
1238
1239     /* Recognize assignments of large structures and constructors of
1240        big arrays.  */
1241     case INIT_EXPR:
1242     case MODIFY_EXPR:
1243       x = TREE_OPERAND (x, 0);
1244       /* FALLTHRU */
1245     case TARGET_EXPR:
1246     case CONSTRUCTOR:
1247       {
1248         HOST_WIDE_INT size;
1249
1250         size = int_size_in_bytes (TREE_TYPE (x));
1251
1252         if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1253           *count += 10;
1254         else
1255           *count += ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1256       }
1257       break;
1258
1259       /* Assign cost of 1 to usual operations.
1260          ??? We may consider mapping RTL costs to this.  */
1261     case COND_EXPR:
1262
1263     case PLUS_EXPR:
1264     case MINUS_EXPR:
1265     case MULT_EXPR:
1266
1267     case FIX_TRUNC_EXPR:
1268     case FIX_CEIL_EXPR:
1269     case FIX_FLOOR_EXPR:
1270     case FIX_ROUND_EXPR:
1271
1272     case NEGATE_EXPR:
1273     case FLOAT_EXPR:
1274     case MIN_EXPR:
1275     case MAX_EXPR:
1276     case ABS_EXPR:
1277
1278     case LSHIFT_EXPR:
1279     case RSHIFT_EXPR:
1280     case LROTATE_EXPR:
1281     case RROTATE_EXPR:
1282
1283     case BIT_IOR_EXPR:
1284     case BIT_XOR_EXPR:
1285     case BIT_AND_EXPR:
1286     case BIT_NOT_EXPR:
1287
1288     case TRUTH_ANDIF_EXPR:
1289     case TRUTH_ORIF_EXPR:
1290     case TRUTH_AND_EXPR:
1291     case TRUTH_OR_EXPR:
1292     case TRUTH_XOR_EXPR:
1293     case TRUTH_NOT_EXPR:
1294
1295     case LT_EXPR:
1296     case LE_EXPR:
1297     case GT_EXPR:
1298     case GE_EXPR:
1299     case EQ_EXPR:
1300     case NE_EXPR:
1301     case ORDERED_EXPR:
1302     case UNORDERED_EXPR:
1303
1304     case UNLT_EXPR:
1305     case UNLE_EXPR:
1306     case UNGT_EXPR:
1307     case UNGE_EXPR:
1308     case UNEQ_EXPR:
1309     case LTGT_EXPR:
1310
1311     case CONVERT_EXPR:
1312
1313     case CONJ_EXPR:
1314
1315     case PREDECREMENT_EXPR:
1316     case PREINCREMENT_EXPR:
1317     case POSTDECREMENT_EXPR:
1318     case POSTINCREMENT_EXPR:
1319
1320     case SWITCH_EXPR:
1321
1322     case ASM_EXPR:
1323
1324     case RESX_EXPR:
1325       *count += 1;
1326       break;
1327
1328     /* Few special cases of expensive operations.  This is useful
1329        to avoid inlining on functions having too many of these.  */
1330     case TRUNC_DIV_EXPR:
1331     case CEIL_DIV_EXPR:
1332     case FLOOR_DIV_EXPR:
1333     case ROUND_DIV_EXPR:
1334     case EXACT_DIV_EXPR:
1335     case TRUNC_MOD_EXPR:
1336     case CEIL_MOD_EXPR:
1337     case FLOOR_MOD_EXPR:
1338     case ROUND_MOD_EXPR:
1339     case RDIV_EXPR:
1340       *count += 10;
1341       break;
1342     case CALL_EXPR:
1343       {
1344         tree decl = get_callee_fndecl (x);
1345
1346         if (decl && DECL_BUILT_IN (decl))
1347           switch (DECL_FUNCTION_CODE (decl))
1348             {
1349             case BUILT_IN_CONSTANT_P:
1350               *walk_subtrees = 0;
1351               return NULL_TREE;
1352             case BUILT_IN_EXPECT:
1353               return NULL_TREE;
1354             default:
1355               break;
1356             }
1357         *count += 10;
1358         break;
1359       }
1360     default:
1361       /* Abort here se we know we don't miss any nodes.  */
1362       abort ();
1363     }
1364   return NULL;
1365 }
1366
1367 /* Estimate number of instructions that will be created by expanding EXPR.  */
1368
1369 int
1370 estimate_num_insns (tree expr)
1371 {
1372   int num = 0;
1373   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1374   return num;
1375 }
1376
1377 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1378
1379 static tree
1380 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1381 {
1382   inline_data *id;
1383   tree t;
1384   tree expr;
1385   tree stmt;
1386   tree use_retvar;
1387   tree decl;
1388   tree fn;
1389   tree arg_inits;
1390   tree *inlined_body;
1391   splay_tree st;
1392   tree args;
1393   tree return_slot_addr;
1394   tree modify_dest;
1395   location_t saved_location;
1396   struct cgraph_edge *edge;
1397   const char *reason;
1398
1399   /* See what we've got.  */
1400   id = (inline_data *) data;
1401   t = *tp;
1402
1403   /* Set input_location here so we get the right instantiation context
1404      if we call instantiate_decl from inlinable_function_p.  */
1405   saved_location = input_location;
1406   if (EXPR_HAS_LOCATION (t))
1407     input_location = EXPR_LOCATION (t);
1408
1409   /* Recurse, but letting recursive invocations know that we are
1410      inside the body of a TARGET_EXPR.  */
1411   if (TREE_CODE (*tp) == TARGET_EXPR)
1412     {
1413 #if 0
1414       int i, len = first_rtl_op (TARGET_EXPR);
1415
1416       /* We're walking our own subtrees.  */
1417       *walk_subtrees = 0;
1418
1419       /* Actually walk over them.  This loop is the body of
1420          walk_trees, omitting the case where the TARGET_EXPR
1421          itself is handled.  */
1422       for (i = 0; i < len; ++i)
1423         {
1424           if (i == 2)
1425             ++id->in_target_cleanup_p;
1426           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1427                      id->tree_pruner);
1428           if (i == 2)
1429             --id->in_target_cleanup_p;
1430         }
1431
1432       goto egress;
1433 #endif
1434     }
1435
1436   if (TYPE_P (t))
1437     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1438        them should not be expanded.  This can happen if the type is a
1439        dynamic array type, for example.  */
1440     *walk_subtrees = 0;
1441
1442   /* From here on, we're only interested in CALL_EXPRs.  */
1443   if (TREE_CODE (t) != CALL_EXPR)
1444     goto egress;
1445
1446   /* First, see if we can figure out what function is being called.
1447      If we cannot, then there is no hope of inlining the function.  */
1448   fn = get_callee_fndecl (t);
1449   if (!fn)
1450     goto egress;
1451
1452   /* Turn forward declarations into real ones.  */
1453   fn = cgraph_node (fn)->decl;
1454
1455   /* If fn is a declaration of a function in a nested scope that was
1456      globally declared inline, we don't set its DECL_INITIAL.
1457      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1458      C++ front-end uses it for cdtors to refer to their internal
1459      declarations, that are not real functions.  Fortunately those
1460      don't have trees to be saved, so we can tell by checking their
1461      DECL_SAVED_TREE.  */
1462   if (! DECL_INITIAL (fn)
1463       && DECL_ABSTRACT_ORIGIN (fn)
1464       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1465     fn = DECL_ABSTRACT_ORIGIN (fn);
1466
1467   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1468      Kill this check once this is fixed.  */
1469   if (!id->current_node->analyzed)
1470     goto egress;
1471
1472   edge = cgraph_edge (id->current_node, t);
1473
1474   /* Constant propagation on argument done during previous inlining
1475      may create new direct call.  Produce an edge for it.  */
1476   if (!edge)
1477     {
1478       struct cgraph_node *dest = cgraph_node (fn);
1479
1480       /* We have missing edge in the callgraph.  This can happen in one case
1481          where previous inlining turned indirect call into direct call by
1482          constant propagating arguments.  In all other cases we hit a bug
1483          (incorrect node sharing is most common reason for missing edges.  */
1484       if (!dest->needed)
1485         abort ();
1486       cgraph_create_edge (id->node, dest, t)->inline_failed
1487         = N_("originally indirect function call not considered for inlining");
1488       goto egress;
1489     }
1490
1491   /* Don't try to inline functions that are not well-suited to
1492      inlining.  */
1493   if (!cgraph_inline_p (edge, &reason))
1494     {
1495       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1496         {
1497           sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1498           sorry ("called from here");
1499         }
1500       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1501                && !DECL_IN_SYSTEM_HEADER (fn)
1502                && strlen (reason))
1503         {
1504           warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1505           warning ("called from here");
1506         }
1507       goto egress;
1508     }
1509
1510 #ifdef ENABLE_CHECKING
1511   if (edge->callee->decl != id->node->decl)
1512     verify_cgraph_node (edge->callee);
1513 #endif
1514
1515   if (! lang_hooks.tree_inlining.start_inlining (fn))
1516     goto egress;
1517
1518   /* Build a block containing code to initialize the arguments, the
1519      actual inline expansion of the body, and a label for the return
1520      statements within the function to jump to.  The type of the
1521      statement expression is the return type of the function call.  */
1522   stmt = NULL;
1523   expr = build (BIND_EXPR, void_type_node, NULL_TREE,
1524                 stmt, make_node (BLOCK));
1525   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1526
1527   /* Local declarations will be replaced by their equivalents in this
1528      map.  */
1529   st = id->decl_map;
1530   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1531                                  NULL, NULL);
1532
1533   /* Initialize the parameters.  */
1534   args = TREE_OPERAND (t, 1);
1535   return_slot_addr = NULL_TREE;
1536   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1537     {
1538       return_slot_addr = TREE_VALUE (args);
1539       args = TREE_CHAIN (args);
1540       TREE_TYPE (expr) = void_type_node;
1541     }
1542
1543   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1544                                              fn, expr);
1545   if (arg_inits)
1546     {
1547       /* Expand any inlined calls in the initializers.  Do this before we
1548          push FN on the stack of functions we are inlining; we want to
1549          inline calls to FN that appear in the initializers for the
1550          parameters.
1551
1552          Note we need to save and restore the saved tree statement iterator
1553          to avoid having it clobbered by expand_calls_inline.  */
1554       tree_stmt_iterator save_tsi;
1555
1556       save_tsi = id->tsi;
1557       expand_calls_inline (&arg_inits, id);
1558       id->tsi = save_tsi;
1559
1560       /* And add them to the tree.  */
1561       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1562     }
1563
1564   /* Record the function we are about to inline so that we can avoid
1565      recursing into it.  */
1566   VARRAY_PUSH_TREE (id->fns, fn);
1567
1568   /* Record the function we are about to inline if optimize_function
1569      has not been called on it yet and we don't have it in the list.  */
1570   if (! DECL_INLINED_FNS (fn))
1571     {
1572       int i;
1573
1574       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1575         if (VARRAY_TREE (id->inlined_fns, i) == fn)
1576           break;
1577       if (i < 0)
1578         VARRAY_PUSH_TREE (id->inlined_fns, fn);
1579     }
1580
1581   /* Return statements in the function body will be replaced by jumps
1582      to the RET_LABEL.  */
1583   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1584   DECL_ARTIFICIAL (id->ret_label) = 1;
1585   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1586   insert_decl_map (id, id->ret_label, id->ret_label);
1587
1588   if (! DECL_INITIAL (fn)
1589       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
1590     abort ();
1591
1592   /* Find the lhs to which the result of this call is assigned.  */
1593   modify_dest = tsi_stmt (id->tsi);
1594   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1595     modify_dest = TREE_OPERAND (modify_dest, 0);
1596   else
1597     modify_dest = NULL;
1598
1599   /* Declare the return variable for the function.  */
1600   decl = declare_return_variable (id, return_slot_addr,
1601                                   modify_dest, &use_retvar);
1602
1603   /* After we've initialized the parameters, we insert the body of the
1604      function itself.  */
1605   {
1606     struct cgraph_node *old_node = id->current_node;
1607
1608     id->current_node = edge->callee;
1609     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1610     id->current_node = old_node;
1611   }
1612   inlined_body = &BIND_EXPR_BODY (expr);
1613
1614   /* After the body of the function comes the RET_LABEL.  This must come
1615      before we evaluate the returned value below, because that evaluation
1616      may cause RTL to be generated.  */
1617   if (TREE_USED (id->ret_label))
1618     {
1619       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1620       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1621     }
1622
1623   /* Clean up.  */
1624   splay_tree_delete (id->decl_map);
1625   id->decl_map = st;
1626
1627   /* The new expression has side-effects if the old one did.  */
1628   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1629
1630   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1631
1632   /* If the inlined function returns a result that we care about,
1633      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1634      the call was a standalone statement and we can just replace it
1635      with the BIND_EXPR inline representation of the called function.  */
1636   if (!use_retvar || !modify_dest)
1637     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1638   else
1639     *tp = use_retvar;
1640
1641   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1642      the call if it is to a "const" function.  Thus the copy of
1643      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1644      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1645      "const" function.
1646
1647      Unfortunately, that is wrong as inlining the function can create/expose
1648      interesting side effects (such as setting of a return value).
1649
1650      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1651      the toplevel expression.  */
1652   recalculate_side_effects (expr);
1653
1654   /* Update callgraph if needed.  */
1655   cgraph_remove_node (edge->callee);
1656
1657   /* Recurse into the body of the just inlined function.  */
1658   expand_calls_inline (inlined_body, id);
1659   VARRAY_POP (id->fns);
1660
1661   /* Don't walk into subtrees.  We've already handled them above.  */
1662   *walk_subtrees = 0;
1663
1664   lang_hooks.tree_inlining.end_inlining (fn);
1665
1666   /* Keep iterating.  */
1667  egress:
1668   input_location = saved_location;
1669   return NULL_TREE;
1670 }
1671
1672 static void
1673 expand_calls_inline (tree *stmt_p, inline_data *id)
1674 {
1675   tree stmt = *stmt_p;
1676   enum tree_code code = TREE_CODE (stmt);
1677   int dummy;
1678
1679   switch (code)
1680     {
1681     case STATEMENT_LIST:
1682       {
1683         tree_stmt_iterator i;
1684         tree new;
1685
1686         for (i = tsi_start (stmt); !tsi_end_p (i); )
1687           {
1688             id->tsi = i;
1689             expand_calls_inline (tsi_stmt_ptr (i), id);
1690
1691             new = tsi_stmt (i);
1692             if (TREE_CODE (new) == STATEMENT_LIST)
1693               {
1694                 tsi_link_before (&i, new, TSI_SAME_STMT);
1695                 tsi_delink (&i);
1696               }
1697             else
1698               tsi_next (&i);
1699           }
1700       }
1701       break;
1702
1703     case COND_EXPR:
1704       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1705       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1706       break;
1707
1708     case CATCH_EXPR:
1709       expand_calls_inline (&CATCH_BODY (stmt), id);
1710       break;
1711
1712     case EH_FILTER_EXPR:
1713       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1714       break;
1715
1716     case TRY_CATCH_EXPR:
1717     case TRY_FINALLY_EXPR:
1718       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1719       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1720       break;
1721
1722     case BIND_EXPR:
1723       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1724       break;
1725
1726     case COMPOUND_EXPR:
1727       /* We're gimple.  We should have gotten rid of all these.  */
1728       abort ();
1729
1730     case RETURN_EXPR:
1731       stmt_p = &TREE_OPERAND (stmt, 0);
1732       stmt = *stmt_p;
1733       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1734         break;
1735
1736       /* FALLTHRU */
1737
1738     case MODIFY_EXPR:
1739       stmt_p = &TREE_OPERAND (stmt, 1);
1740       stmt = *stmt_p;
1741       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1742         {
1743           stmt_p = &TREE_OPERAND (stmt, 0);
1744           stmt = *stmt_p;
1745         }
1746       if (TREE_CODE (stmt) != CALL_EXPR)
1747         break;
1748
1749       /* FALLTHRU */
1750
1751     case CALL_EXPR:
1752       expand_call_inline (stmt_p, &dummy, id);
1753       break;
1754
1755     default:
1756       break;
1757     }
1758 }
1759
1760 /* Expand calls to inline functions in the body of FN.  */
1761
1762 void
1763 optimize_inline_calls (tree fn)
1764 {
1765   inline_data id;
1766   tree prev_fn;
1767   tree ifn;
1768
1769   /* There is no point in performing inlining if errors have already
1770      occurred -- and we might crash if we try to inline invalid
1771      code.  */
1772   if (errorcount || sorrycount)
1773     return;
1774
1775   /* Clear out ID.  */
1776   memset (&id, 0, sizeof (id));
1777
1778   id.current_node = id.node = cgraph_node (fn);
1779   /* Don't allow recursion into FN.  */
1780   VARRAY_TREE_INIT (id.fns, 32, "fns");
1781   VARRAY_PUSH_TREE (id.fns, fn);
1782   /* Or any functions that aren't finished yet.  */
1783   prev_fn = NULL_TREE;
1784   if (current_function_decl)
1785     {
1786       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1787       prev_fn = current_function_decl;
1788     }
1789
1790   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1791
1792   /* Create the list of functions this call will inline.  */
1793   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1794
1795   /* Keep track of the low-water mark, i.e., the point where the first
1796      real inlining is represented in ID.FNS.  */
1797   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1798
1799   /* Replace all calls to inline functions with the bodies of those
1800      functions.  */
1801   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1802   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1803
1804   /* Clean up.  */
1805   htab_delete (id.tree_pruner);
1806   ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1807   if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1808     memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1809             VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1810   DECL_INLINED_FNS (fn) = ifn;
1811
1812 #ifdef ENABLE_CHECKING
1813     {
1814       struct cgraph_edge *e;
1815
1816       verify_cgraph_node (id.node);
1817
1818       /* Double check that we inlined everything we are supposed to inline.  */
1819       for (e = id.node->callees; e; e = e->next_callee)
1820         if (!e->inline_failed)
1821           abort ();
1822     }
1823 #endif
1824 }
1825
1826 /* FN is a function that has a complete body, and CLONE is a function whose
1827    body is to be set to a copy of FN, mapping argument declarations according
1828    to the ARG_MAP splay_tree.  */
1829
1830 void
1831 clone_body (tree clone, tree fn, void *arg_map)
1832 {
1833   inline_data id;
1834
1835   /* Clone the body, as if we were making an inline call.  But, remap the
1836      parameters in the callee to the parameters of caller.  If there's an
1837      in-charge parameter, map it to an appropriate constant.  */
1838   memset (&id, 0, sizeof (id));
1839   VARRAY_TREE_INIT (id.fns, 2, "fns");
1840   VARRAY_PUSH_TREE (id.fns, clone);
1841   VARRAY_PUSH_TREE (id.fns, fn);
1842   id.decl_map = (splay_tree)arg_map;
1843
1844   /* Cloning is treated slightly differently from inlining.  Set
1845      CLONING_P so that it's clear which operation we're performing.  */
1846   id.cloning_p = true;
1847
1848   /* Actually copy the body.  */
1849   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1850 }
1851
1852 /* Make and return duplicate of body in FN.  Put copies of DECL_ARGUMENTS
1853    in *arg_copy and of the static chain, if any, in *sc_copy.  */
1854
1855 tree
1856 save_body (tree fn, tree *arg_copy, tree *sc_copy)
1857 {
1858   inline_data id;
1859   tree body, *parg;
1860
1861   memset (&id, 0, sizeof (id));
1862   VARRAY_TREE_INIT (id.fns, 1, "fns");
1863   VARRAY_PUSH_TREE (id.fns, fn);
1864   id.node = cgraph_node (fn);
1865   id.saving_p = true;
1866   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1867   *arg_copy = DECL_ARGUMENTS (fn);
1868
1869   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1870     {
1871       tree new = copy_node (*parg);
1872
1873       lang_hooks.dup_lang_specific_decl (new);
1874       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1875       insert_decl_map (&id, *parg, new);
1876       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1877       *parg = new;
1878     }
1879
1880   *sc_copy = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1881   if (*sc_copy)
1882     {
1883       tree new = copy_node (*sc_copy);
1884
1885       lang_hooks.dup_lang_specific_decl (new);
1886       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*sc_copy);
1887       insert_decl_map (&id, *sc_copy, new);
1888       TREE_CHAIN (new) = TREE_CHAIN (*sc_copy);
1889       *sc_copy = 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 /* Perform any modifications to EXPR required when it is unsaved.  Does
2375    not recurse into EXPR's subtrees.  */
2376
2377 static void
2378 unsave_expr_1 (tree expr)
2379 {
2380   switch (TREE_CODE (expr))
2381     {
2382     case TARGET_EXPR:
2383       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2384          It's OK for this to happen if it was part of a subtree that
2385          isn't immediately expanded, such as operand 2 of another
2386          TARGET_EXPR.  */
2387       if (TREE_OPERAND (expr, 1))
2388         break;
2389
2390       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2391       TREE_OPERAND (expr, 3) = NULL_TREE;
2392       break;
2393
2394     default:
2395       break;
2396     }
2397 }
2398
2399 /* Called via walk_tree when an expression is unsaved.  Using the
2400    splay_tree pointed to by ST (which is really a `splay_tree'),
2401    remaps all local declarations to appropriate replacements.  */
2402
2403 static tree
2404 unsave_r (tree *tp, int *walk_subtrees, void *data)
2405 {
2406   inline_data *id = (inline_data *) data;
2407   splay_tree st = id->decl_map;
2408   splay_tree_node n;
2409
2410   /* Only a local declaration (variable or label).  */
2411   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2412       || TREE_CODE (*tp) == LABEL_DECL)
2413     {
2414       /* Lookup the declaration.  */
2415       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2416
2417       /* If it's there, remap it.  */
2418       if (n)
2419         *tp = (tree) n->value;
2420     }
2421
2422   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2423     copy_statement_list (tp);
2424   else if (TREE_CODE (*tp) == BIND_EXPR)
2425     copy_bind_expr (tp, walk_subtrees, id);
2426   else if (TREE_CODE (*tp) == SAVE_EXPR)
2427     remap_save_expr (tp, st, walk_subtrees);
2428   else
2429     {
2430       copy_tree_r (tp, walk_subtrees, NULL);
2431
2432       /* Do whatever unsaving is required.  */
2433       unsave_expr_1 (*tp);
2434     }
2435
2436   /* Keep iterating.  */
2437   return NULL_TREE;
2438 }
2439
2440 /* Copies everything in EXPR and replaces variables, labels
2441    and SAVE_EXPRs local to EXPR.  */
2442
2443 tree
2444 unsave_expr_now (tree expr)
2445 {
2446   inline_data id;
2447
2448   /* There's nothing to do for NULL_TREE.  */
2449   if (expr == 0)
2450     return expr;
2451
2452   /* Set up ID.  */
2453   memset (&id, 0, sizeof (id));
2454   VARRAY_TREE_INIT (id.fns, 1, "fns");
2455   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2456   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2457
2458   /* Walk the tree once to find local labels.  */
2459   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2460
2461   /* Walk the tree again, copying, remapping, and unsaving.  */
2462   walk_tree (&expr, unsave_r, &id, NULL);
2463
2464   /* Clean up.  */
2465   splay_tree_delete (id.decl_map);
2466
2467   return expr;
2468 }
2469
2470 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2471
2472 static tree
2473 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2474 {
2475   if (*tp == data)
2476     return (tree) data;
2477   else
2478     return NULL;
2479 }
2480
2481 bool
2482 debug_find_tree (tree top, tree search)
2483 {
2484   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2485 }
2486
2487 /* Declare the variables created by the inliner.  Add all the variables in
2488    VARS to BIND_EXPR.  */
2489
2490 static void
2491 declare_inline_vars (tree bind_expr, tree vars)
2492 {
2493   tree t;
2494   for (t = vars; t; t = TREE_CHAIN (t))
2495     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2496
2497   add_var_to_bind_expr (bind_expr, vars);
2498 }