gcc/tree-inline.c

   1 /* Control and data flow functions for trees.
   2    Copyright 2001 Free Software Foundation, Inc.
   3    Contributed by Alexandre Oliva <aoliva@redhat.com>
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC 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 GNU CC 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 GNU CC; 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 "toplev.h"
  25 #include "tree.h"
  26 #include "tree-inline.h"
  27 #include "rtl.h"
  28 #include "expr.h"
  29 #include "flags.h"
  30 #include "params.h"
  31 #include "input.h"
  32 #include "insn-config.h"
  33 #include "integrate.h"
  34 #include "varray.h"
  35 #include "hashtab.h"
  36 #include "splay-tree.h"
  37
  38 /* This should be eventually be generalized to other languages, but
  39    this would require a shared function-as-trees infrastructure.  */
  40 #include "c-common.h"
  41
  42 /* 0 if we should not perform inlining.
  43    1 if we should expand functions calls inline at the tree level.
  44    2 if we should consider *all* functions to be inline
  45    candidates.  */
  46
  47 int flag_inline_trees = 0;
  48
  49 /* To Do:
  50
  51    o In order to make inlining-on-trees work, we pessimized
  52      function-local static constants.  In particular, they are now
  53      always output, even when not addressed.  Fix this by treating
  54      function-local static constants just like global static
  55      constants; the back-end already knows not to output them if they
  56      are not needed.
  57
  58    o Provide heuristics to clamp inlining of recursive template
  59      calls?  */
  60
  61 /* Data required for function inlining.  */
  62
  63 typedef struct inline_data
  64 {
  65   /* A stack of the functions we are inlining.  For example, if we are
  66      compiling `f', which calls `g', which calls `h', and we are
  67      inlining the body of `h', the stack will contain, `h', followed
  68      by `g', followed by `f'.  The first few elements of the stack may
  69      contain other functions that we know we should not recurse into,
  70      even though they are not directly being inlined.  */
  71   varray_type fns;
  72   /* The index of the first element of FNS that really represents an
  73      inlined function.  */
  74   unsigned first_inlined_fn;
  75   /* The label to jump to when a return statement is encountered.  If
  76      this value is NULL, then return statements will simply be
  77      remapped as return statements, rather than as jumps.  */
  78   tree ret_label;
  79   /* The map from local declarations in the inlined function to
  80      equivalents in the function into which it is being inlined.  */
  81   splay_tree decl_map;
  82   /* Nonzero if we are currently within the cleanup for a
  83      TARGET_EXPR.  */
  84   int in_target_cleanup_p;
  85   /* A stack of the TARGET_EXPRs that we are currently processing.  */
  86   varray_type target_exprs;
  87   /* A list of the functions current function has inlined.  */
  88   varray_type inlined_fns;
  89   /* The approximate number of statements we have inlined in the
  90      current call stack.  */
  91   int inlined_stmts;
  92   /* We use the same mechanism to build clones that we do to perform
  93      inlining.  However, there are a few places where we need to
  94      distinguish between those two situations.  This flag is true if
  95      we are cloning, rather than inlining.  */
  96   bool cloning_p;
  97   /* Hash table used to prevent walk_tree from visiting the same node
  98      umpteen million times.  */
  99   htab_t tree_pruner;
 100 } inline_data;
 101
 102 /* Prototypes.  */
 103
 104 static tree initialize_inlined_parameters PARAMS ((inline_data *, tree, tree));
 105 static tree declare_return_variable PARAMS ((inline_data *, tree *));
 106 static tree copy_body_r PARAMS ((tree *, int *, void *));
 107 static tree copy_body PARAMS ((inline_data *));
 108 static tree expand_call_inline PARAMS ((tree *, int *, void *));
 109 static void expand_calls_inline PARAMS ((tree *, inline_data *));
 110 static int inlinable_function_p PARAMS ((tree, inline_data *));
 111 static tree remap_decl PARAMS ((tree, inline_data *));
 112 static void remap_block PARAMS ((tree, tree, inline_data *));
 113 static void copy_scope_stmt PARAMS ((tree *, int *, inline_data *));
 114
 115 /* The approximate number of instructions per statement.  This number
 116    need not be particularly accurate; it is used only to make
 117    decisions about when a function is too big to inline.  */
 118 #define INSNS_PER_STMT (10)
 119
 120 /* Remap DECL during the copying of the BLOCK tree for the function.  */
 121
 122 static tree
 123 remap_decl (decl, id)
 124      tree decl;
 125      inline_data *id;
 126 {
 127   splay_tree_node n;
 128   tree fn;
 129
 130   /* We only remap local variables in the current function.  */
 131   fn = VARRAY_TOP_TREE (id->fns);
 132   if (! (*lang_hooks.tree_inlining.auto_var_in_fn_p) (decl, fn))
 133     return NULL_TREE;
 134
 135   /* See if we have remapped this declaration.  */
 136   n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 137   /* If we didn't already have an equivalent for this declaration,
 138      create one now.  */
 139   if (!n)
 140     {
 141       tree t;
 142
 143       /* Make a copy of the variable or label.  */
 144       t = copy_decl_for_inlining (decl, fn,
 145                                   VARRAY_TREE (id->fns, 0));
 146
 147       /* The decl T could be a dynamic array or other variable size type,
 148          in which case some fields need to be remapped because they may
 149          contain SAVE_EXPRs.  */
 150       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 151       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 152       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
 153           && TYPE_DOMAIN (TREE_TYPE (t)))
 154         {
 155           TREE_TYPE (t) = copy_node (TREE_TYPE (t));
 156           TYPE_DOMAIN (TREE_TYPE (t))
 157             = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
 158           walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
 159                      copy_body_r, id, NULL);
 160         }
 161
 162       if (! DECL_NAME (t) && TREE_TYPE (t)
 163           && (*lang_hooks.tree_inlining.anon_aggr_type_p) (TREE_TYPE (t)))
 164         {
 165           /* For a VAR_DECL of anonymous type, we must also copy the
 166              member VAR_DECLS here and rechain the
 167              DECL_ANON_UNION_ELEMS.  */
 168           tree members = NULL;
 169           tree src;
 170
 171           for (src = DECL_ANON_UNION_ELEMS (t); src;
 172                src = TREE_CHAIN (src))
 173             {
 174               tree member = remap_decl (TREE_VALUE (src), id);
 175
 176               if (TREE_PURPOSE (src))
 177                 abort ();
 178               members = tree_cons (NULL, member, members);
 179             }
 180           DECL_ANON_UNION_ELEMS (t) = nreverse (members);
 181         }
 182
 183       /* Remember it, so that if we encounter this local entity
 184          again we can reuse this copy.  */
 185       n = splay_tree_insert (id->decl_map,
 186                              (splay_tree_key) decl,
 187                              (splay_tree_value) t);
 188     }
 189
 190   return (tree) n->value;
 191 }
 192
 193 /* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain
 194    remapped versions of the variables therein.  And hook the new block
 195    into the block-tree.  If non-NULL, the DECLS are declarations to
 196    add to use instead of the BLOCK_VARS in the old block.  */
 197
 198 static void
 199 remap_block (scope_stmt, decls, id)
 200      tree scope_stmt;
 201      tree decls;
 202      inline_data *id;
 203 {
 204   /* We cannot do this in the cleanup for a TARGET_EXPR since we do
 205      not know whether or not expand_expr will actually write out the
 206      code we put there.  If it does not, then we'll have more BLOCKs
 207      than block-notes, and things will go awry.  At some point, we
 208      should make the back-end handle BLOCK notes in a tidier way,
 209      without requiring a strict correspondence to the block-tree; then
 210      this check can go.  */
 211   if (id->in_target_cleanup_p)
 212     {
 213       SCOPE_STMT_BLOCK (scope_stmt) = NULL_TREE;
 214       return;
 215     }
 216
 217   /* If this is the beginning of a scope, remap the associated BLOCK.  */
 218   if (SCOPE_BEGIN_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
 219     {
 220       tree old_block;
 221       tree new_block;
 222       tree old_var;
 223       tree fn;
 224
 225       /* Make the new block.  */
 226       old_block = SCOPE_STMT_BLOCK (scope_stmt);
 227       new_block = make_node (BLOCK);
 228       TREE_USED (new_block) = TREE_USED (old_block);
 229       BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 230       SCOPE_STMT_BLOCK (scope_stmt) = new_block;
 231
 232       /* Remap its variables.  */
 233       for (old_var = decls ? decls : BLOCK_VARS (old_block);
 234            old_var;
 235            old_var = TREE_CHAIN (old_var))
 236         {
 237           tree new_var;
 238
 239           /* Remap the variable.  */
 240           new_var = remap_decl (old_var, id);
 241           /* If we didn't remap this variable, so we can't mess with
 242              its TREE_CHAIN.  If we remapped this variable to
 243              something other than a declaration (say, if we mapped it
 244              to a constant), then we must similarly omit any mention
 245              of it here.  */
 246           if (!new_var || !DECL_P (new_var))
 247             ;
 248           else
 249             {
 250               TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
 251               BLOCK_VARS (new_block) = new_var;
 252             }
 253         }
 254       /* We put the BLOCK_VARS in reverse order; fix that now.  */
 255       BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
 256       fn = VARRAY_TREE (id->fns, 0);
 257       if (id->cloning_p)
 258         /* We're building a clone; DECL_INITIAL is still
 259            error_mark_node, and current_binding_level is the parm
 260            binding level.  */
 261         insert_block (new_block);
 262       else
 263         {
 264           /* Attach this new block after the DECL_INITIAL block for the
 265              function into which this block is being inlined.  In
 266              rest_of_compilation we will straighten out the BLOCK tree.  */
 267           tree *first_block;
 268           if (DECL_INITIAL (fn))
 269             first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
 270           else
 271             first_block = &DECL_INITIAL (fn);
 272           BLOCK_CHAIN (new_block) = *first_block;
 273           *first_block = new_block;
 274         }
 275       /* Remember the remapped block.  */
 276       splay_tree_insert (id->decl_map,
 277                          (splay_tree_key) old_block,
 278                          (splay_tree_value) new_block);
 279     }
 280   /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the
 281      remapped block.  */
 282   else if (SCOPE_END_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
 283     {
 284       splay_tree_node n;
 285
 286       /* Find this block in the table of remapped things.  */
 287       n = splay_tree_lookup (id->decl_map,
 288                              (splay_tree_key) SCOPE_STMT_BLOCK (scope_stmt));
 289       if (! n)
 290         abort ();
 291       SCOPE_STMT_BLOCK (scope_stmt) = (tree) n->value;
 292     }
 293 }
 294
 295 /* Copy the SCOPE_STMT pointed to by TP.  */
 296
 297 static void
 298 copy_scope_stmt (tp, walk_subtrees, id)
 299      tree *tp;
 300      int *walk_subtrees;
 301      inline_data *id;
 302 {
 303   tree block;
 304
 305   /* Remember whether or not this statement was nullified.  When
 306      making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and
 307      doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to
 308      deal with copying BLOCKs if they do not wish to do so.  */
 309   block = SCOPE_STMT_BLOCK (*tp);
 310   /* Copy (and replace) the statement.  */
 311   copy_tree_r (tp, walk_subtrees, NULL);
 312   /* Restore the SCOPE_STMT_BLOCK.  */
 313   SCOPE_STMT_BLOCK (*tp) = block;
 314
 315   /* Remap the associated block.  */
 316   remap_block (*tp, NULL_TREE, id);
 317 }
 318
 319 /* Called from copy_body via walk_tree.  DATA is really an
 320    `inline_data *'.  */
 321
 322 static tree
 323 copy_body_r (tp, walk_subtrees, data)
 324      tree *tp;
 325      int *walk_subtrees;
 326      void *data;
 327 {
 328   inline_data* id;
 329   tree fn;
 330
 331   /* Set up.  */
 332   id = (inline_data *) data;
 333   fn = VARRAY_TOP_TREE (id->fns);
 334
 335 #if 0
 336   /* All automatic variables should have a DECL_CONTEXT indicating
 337      what function they come from.  */
 338   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 339       && DECL_NAMESPACE_SCOPE_P (*tp))
 340     if (! DECL_EXTERNAL (*tp) && ! TREE_STATIC (*tp))
 341       abort ();
 342 #endif
 343
 344   /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
 345      GOTO_STMT with the RET_LABEL as its target.  */
 346   if (TREE_CODE (*tp) == RETURN_STMT && id->ret_label)
 347     {
 348       tree return_stmt = *tp;
 349       tree goto_stmt;
 350
 351       /* Build the GOTO_STMT.  */
 352       goto_stmt = build_stmt (GOTO_STMT, id->ret_label);
 353       TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt);
 354
 355       /* If we're returning something, just turn that into an
 356          assignment into the equivalent of the original
 357          RESULT_DECL.  */
 358       if (RETURN_EXPR (return_stmt))
 359         {
 360           *tp = build_stmt (EXPR_STMT,
 361                             RETURN_EXPR (return_stmt));
 362           STMT_IS_FULL_EXPR_P (*tp) = 1;
 363           /* And then jump to the end of the function.  */
 364           TREE_CHAIN (*tp) = goto_stmt;
 365         }
 366       /* If we're not returning anything just do the jump.  */
 367       else
 368         *tp = goto_stmt;
 369     }
 370   /* Local variables and labels need to be replaced by equivalent
 371      variables.  We don't want to copy static variables; there's only
 372      one of those, no matter how many times we inline the containing
 373      function.  */
 374   else if ((*lang_hooks.tree_inlining.auto_var_in_fn_p) (*tp, fn))
 375     {
 376       tree new_decl;
 377
 378       /* Remap the declaration.  */
 379       new_decl = remap_decl (*tp, id);
 380       if (! new_decl)
 381         abort ();
 382       /* Replace this variable with the copy.  */
 383       STRIP_TYPE_NOPS (new_decl);
 384       *tp = new_decl;
 385     }
 386 #if 0
 387   else if (nonstatic_local_decl_p (*tp)
 388            && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
 389     abort ();
 390 #endif
 391   else if (TREE_CODE (*tp) == SAVE_EXPR)
 392     remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0),
 393                      walk_subtrees);
 394   else if (TREE_CODE (*tp) == UNSAVE_EXPR)
 395     /* UNSAVE_EXPRs should not be generated until expansion time.  */
 396     abort ();
 397   /* For a SCOPE_STMT, we must copy the associated block so that we
 398      can write out debugging information for the inlined variables.  */
 399   else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p)
 400     copy_scope_stmt (tp, walk_subtrees, id);
 401   /* Otherwise, just copy the node.  Note that copy_tree_r already
 402      knows not to copy VAR_DECLs, etc., so this is safe.  */
 403   else
 404     {
 405       copy_tree_r (tp, walk_subtrees, NULL);
 406
 407       /* The copied TARGET_EXPR has never been expanded, even if the
 408          original node was expanded already.  */
 409       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 410         {
 411           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 412           TREE_OPERAND (*tp, 3) = NULL_TREE;
 413         }
 414       else if (TREE_CODE (*tp) == MODIFY_EXPR
 415                && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 416                && ((*lang_hooks.tree_inlining.auto_var_in_fn_p)
 417                    (TREE_OPERAND (*tp, 0), fn)))
 418         {
 419           /* Some assignments VAR = VAR; don't generate any rtl code
 420              and thus don't count as variable modification.  Avoid
 421              keeping bogosities like 0 = 0.  */
 422           tree decl = TREE_OPERAND (*tp, 0), value;
 423           splay_tree_node n;
 424
 425           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 426           if (n)
 427             {
 428               value = (tree) n->value;
 429               STRIP_TYPE_NOPS (value);
 430               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 431                 *tp = value;
 432             }
 433         }
 434     }
 435
 436   /* Keep iterating.  */
 437   return NULL_TREE;
 438 }
 439
 440 /* Make a copy of the body of FN so that it can be inserted inline in
 441    another function.  */
 442
 443 static tree
 444 copy_body (id)
 445      inline_data *id;
 446 {
 447   tree body;
 448
 449   body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
 450   walk_tree (&body, copy_body_r, id, NULL);
 451
 452   return body;
 453 }
 454
 455 /* Generate code to initialize the parameters of the function at the
 456    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 457
 458 static tree
 459 initialize_inlined_parameters (id, args, fn)
 460      inline_data *id;
 461      tree args;
 462      tree fn;
 463 {
 464   tree init_stmts;
 465   tree parms;
 466   tree a;
 467   tree p;
 468
 469   /* Figure out what the parameters are.  */
 470   parms = DECL_ARGUMENTS (fn);
 471
 472   /* Start with no initializations whatsoever.  */
 473   init_stmts = NULL_TREE;
 474
 475   /* Loop through the parameter declarations, replacing each with an
 476      equivalent VAR_DECL, appropriately initialized.  */
 477   for (p = parms, a = args; p;
 478        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 479     {
 480       tree init_stmt;
 481       tree var;
 482       tree value;
 483
 484       /* Find the initializer.  */
 485       value = a ? TREE_VALUE (a) : NULL_TREE;
 486
 487       /* If the parameter is never assigned to, we may not need to
 488          create a new variable here at all.  Instead, we may be able
 489          to just use the argument value.  */
 490       if (TREE_READONLY (p)
 491           && !TREE_ADDRESSABLE (p)
 492           && value && !TREE_SIDE_EFFECTS (value))
 493         {
 494           /* Simplify the value, if possible.  */
 495           value = fold (DECL_P (value) ? decl_constant_value (value) : value);
 496
 497           /* We can't risk substituting complex expressions.  They
 498              might contain variables that will be assigned to later.
 499              Theoretically, we could check the expression to see if
 500              all of the variables that determine its value are
 501              read-only, but we don't bother.  */
 502           if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 503             {
 504               /* If this is a declaration, wrap it a NOP_EXPR so that
 505                  we don't try to put the VALUE on the list of
 506                  BLOCK_VARS.  */
 507               if (DECL_P (value))
 508                 value = build1 (NOP_EXPR, TREE_TYPE (value), value);
 509
 510               splay_tree_insert (id->decl_map,
 511                                  (splay_tree_key) p,
 512                                  (splay_tree_value) value);
 513               continue;
 514             }
 515         }
 516
 517       /* Make an equivalent VAR_DECL.  */
 518       var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 519       /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 520          that way, when the PARM_DECL is encountered, it will be
 521          automatically replaced by the VAR_DECL.  */
 522       splay_tree_insert (id->decl_map,
 523                          (splay_tree_key) p,
 524                          (splay_tree_value) var);
 525
 526       /* Declare this new variable.  */
 527       init_stmt = build_stmt (DECL_STMT, var);
 528       TREE_CHAIN (init_stmt) = init_stmts;
 529       init_stmts = init_stmt;
 530
 531       /* Initialize this VAR_DECL from the equivalent argument.  If
 532          the argument is an object, created via a constructor or copy,
 533          this will not result in an extra copy: the TARGET_EXPR
 534          representing the argument will be bound to VAR, and the
 535          object will be constructed in VAR.  */
 536       if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 537         DECL_INITIAL (var) = value;
 538       else
 539         {
 540           /* Even if P was TREE_READONLY, the new VAR should not be.
 541              In the original code, we would have constructed a
 542              temporary, and then the function body would have never
 543              changed the value of P.  However, now, we will be
 544              constructing VAR directly.  The constructor body may
 545              change its value multiple times as it is being
 546              constructed.  Therefore, it must not be TREE_READONLY;
 547              the back-end assumes that TREE_READONLY variable is
 548              assigned to only once.  */
 549           TREE_READONLY (var) = 0;
 550
 551           /* Build a run-time initialization.  */
 552           init_stmt = build_stmt (EXPR_STMT,
 553                                   build (INIT_EXPR, TREE_TYPE (p),
 554                                          var, value));
 555           /* Add this initialization to the list.  Note that we want the
 556              declaration *after* the initialization because we are going
 557              to reverse all the initialization statements below.  */
 558           TREE_CHAIN (init_stmt) = init_stmts;
 559           init_stmts = init_stmt;
 560         }
 561     }
 562
 563   /* Evaluate trailing arguments.  */
 564   for (; a; a = TREE_CHAIN (a))
 565     {
 566       tree init_stmt;
 567       tree value;
 568
 569       /* Find the initializer.  */
 570       value = a ? TREE_VALUE (a) : NULL_TREE;
 571
 572       if (! value || ! TREE_SIDE_EFFECTS (value))
 573         continue;
 574
 575       init_stmt = build_stmt (EXPR_STMT, value);
 576       TREE_CHAIN (init_stmt) = init_stmts;
 577       init_stmts = init_stmt;
 578     }
 579
 580   /* The initialization statements have been built up in reverse
 581      order.  Straighten them out now.  */
 582   return nreverse (init_stmts);
 583 }
 584
 585 /* Declare a return variable to replace the RESULT_DECL for the
 586    function we are calling.  An appropriate DECL_STMT is returned.
 587    The USE_STMT is filled in to contain a use of the declaration to
 588    indicate the return value of the function.  */
 589
 590 static tree
 591 declare_return_variable (id, use_stmt)
 592      struct inline_data *id;
 593      tree *use_stmt;
 594 {
 595   tree fn = VARRAY_TOP_TREE (id->fns);
 596   tree result = DECL_RESULT (fn);
 597   tree var;
 598   int need_return_decl = 1;
 599
 600   /* We don't need to do anything for functions that don't return
 601      anything.  */
 602   if (!result || VOID_TYPE_P (TREE_TYPE (result)))
 603     {
 604       *use_stmt = NULL_TREE;
 605       return NULL_TREE;
 606     }
 607
 608   var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
 609          (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
 610           &need_return_decl, &id->target_exprs));
 611
 612   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 613      way, when the RESULT_DECL is encountered, it will be
 614      automatically replaced by the VAR_DECL.  */
 615   splay_tree_insert (id->decl_map,
 616                      (splay_tree_key) result,
 617                      (splay_tree_value) var);
 618
 619   /* Build the USE_STMT.  If the return type of the function was
 620      promoted, convert it back to the expected type.  */
 621   if (TREE_TYPE (var) == TREE_TYPE (TREE_TYPE (fn)))
 622     *use_stmt = build_stmt (EXPR_STMT, var);
 623   else
 624     *use_stmt = build_stmt (EXPR_STMT,
 625                             build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)),
 626                                     var));
 627
 628   /* Build the declaration statement if FN does not return an
 629      aggregate.  */
 630   if (need_return_decl)
 631     return build_stmt (DECL_STMT, var);
 632   /* If FN does return an aggregate, there's no need to declare the
 633      return variable; we're using a variable in our caller's frame.  */
 634   else
 635     return NULL_TREE;
 636 }
 637
 638 /* Returns non-zero if a function can be inlined as a tree.  */
 639
 640 int
 641 tree_inlinable_function_p (fn)
 642      tree fn;
 643 {
 644   return inlinable_function_p (fn, NULL);
 645 }
 646
 647 /* Returns non-zero if FN is a function that can be inlined into the
 648    inlining context ID_.  If ID_ is NULL, check whether the function
 649    can be inlined at all.  */
 650
 651 static int
 652 inlinable_function_p (fn, id)
 653      tree fn;
 654      inline_data *id;
 655 {
 656   int inlinable;
 657
 658   /* If we've already decided this function shouldn't be inlined,
 659      there's no need to check again.  */
 660   if (DECL_UNINLINABLE (fn))
 661     return 0;
 662
 663   /* Assume it is not inlinable.  */
 664   inlinable = 0;
 665
 666   /* If we're not inlining things, then nothing is inlinable.  */
 667   if (! flag_inline_trees)
 668     ;
 669   /* If we're not inlining all functions and the function was not
 670      declared `inline', we don't inline it.  */
 671   else if (flag_inline_trees < 2 && ! DECL_INLINE (fn))
 672     ;
 673   /* We can't inline functions that are too big.  Only allow a single
 674      function to eat up half of our budget.  Make special allowance
 675      for extern inline functions, though.  */
 676   else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 677            && DECL_NUM_STMTS (fn) * INSNS_PER_STMT > MAX_INLINE_INSNS / 2)
 678     ;
 679   /* All is well.  We can inline this function.  Traditionally, GCC
 680      has refused to inline functions using alloca, or functions whose
 681      values are returned in a PARALLEL, and a few other such obscure
 682      conditions.  We are not equally constrained at the tree level.  */
 683   else
 684     inlinable = 1;
 685
 686   /* Squirrel away the result so that we don't have to check again.  */
 687   DECL_UNINLINABLE (fn) = ! inlinable;
 688
 689   /* Even if this function is not itself too big to inline, it might
 690      be that we've done so much inlining already that we don't want to
 691      risk too much inlining any more and thus halve the acceptable
 692      size.  */
 693   if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 694       && ((DECL_NUM_STMTS (fn) + (id ? id->inlined_stmts : 0)) * INSNS_PER_STMT
 695           > MAX_INLINE_INSNS)
 696       && DECL_NUM_STMTS (fn) * INSNS_PER_STMT > MAX_INLINE_INSNS / 4)
 697     inlinable = 0;
 698
 699   if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn))
 700     inlinable = 0;
 701
 702   /* If we don't have the function body available, we can't inline
 703      it.  */
 704   if (! DECL_SAVED_TREE (fn))
 705     inlinable = 0;
 706
 707   /* Check again, language hooks may have modified it.  */
 708   if (! inlinable || DECL_UNINLINABLE (fn))
 709     return 0;
 710
 711   /* Don't do recursive inlining, either.  We don't record this in
 712      DECL_UNINLINABLE; we may be able to inline this function later.  */
 713   if (id)
 714     {
 715       size_t i;
 716
 717       for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i)
 718         if (VARRAY_TREE (id->fns, i) == fn)
 719           return 0;
 720
 721       if (DECL_INLINED_FNS (fn))
 722         {
 723           int j;
 724           tree inlined_fns = DECL_INLINED_FNS (fn);
 725
 726           for (j = 0; j < TREE_VEC_LENGTH (inlined_fns); ++j)
 727             if (TREE_VEC_ELT (inlined_fns, j) == VARRAY_TREE (id->fns, 0))
 728               return 0;
 729         }
 730     }
 731
 732   /* Return the result.  */
 733   return inlinable;
 734 }
 735
 736 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 737
 738 static tree
 739 expand_call_inline (tp, walk_subtrees, data)
 740      tree *tp;
 741      int *walk_subtrees;
 742      void *data;
 743 {
 744   inline_data *id;
 745   tree t;
 746   tree expr;
 747   tree chain;
 748   tree fn;
 749   tree scope_stmt;
 750   tree use_stmt;
 751   tree arg_inits;
 752   tree *inlined_body;
 753   splay_tree st;
 754
 755   /* See what we've got.  */
 756   id = (inline_data *) data;
 757   t = *tp;
 758
 759   /* Recurse, but letting recursive invocations know that we are
 760      inside the body of a TARGET_EXPR.  */
 761   if (TREE_CODE (*tp) == TARGET_EXPR)
 762     {
 763       int i, len = first_rtl_op (TARGET_EXPR);
 764
 765       /* We're walking our own subtrees.  */
 766       *walk_subtrees = 0;
 767
 768       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 769       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 770
 771       /* Actually walk over them.  This loop is the body of
 772          walk_trees, omitting the case where the TARGET_EXPR
 773          itself is handled.  */
 774       for (i = 0; i < len; ++i)
 775         {
 776           if (i == 2)
 777             ++id->in_target_cleanup_p;
 778           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
 779                      id->tree_pruner);
 780           if (i == 2)
 781             --id->in_target_cleanup_p;
 782         }
 783
 784       /* We're done with this TARGET_EXPR now.  */
 785       VARRAY_POP (id->target_exprs);
 786
 787       return NULL_TREE;
 788     }
 789
 790   if (TYPE_P (t))
 791     /* Because types were not copied in copy_body, CALL_EXPRs beneath
 792        them should not be expanded.  This can happen if the type is a
 793        dynamic array type, for example.  */
 794     *walk_subtrees = 0;
 795
 796   /* From here on, we're only interested in CALL_EXPRs.  */
 797   if (TREE_CODE (t) != CALL_EXPR)
 798     return NULL_TREE;
 799
 800   /* First, see if we can figure out what function is being called.
 801      If we cannot, then there is no hope of inlining the function.  */
 802   fn = get_callee_fndecl (t);
 803   if (!fn)
 804     return NULL_TREE;
 805
 806   /* Don't try to inline functions that are not well-suited to
 807      inlining.  */
 808   if (!inlinable_function_p (fn, id))
 809     return NULL_TREE;
 810
 811   /* Set the current filename and line number to the function we are
 812      inlining so that when we create new _STMT nodes here they get
 813      line numbers corresponding to the function we are calling.  We
 814      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 815      because individual statements don't record the filename.  */
 816   push_srcloc (fn->decl.filename, fn->decl.linenum);
 817
 818   /* Build a statement-expression containing code to initialize the
 819      arguments, the actual inline expansion of the body, and a label
 820      for the return statements within the function to jump to.  The
 821      type of the statement expression is the return type of the
 822      function call.  */
 823   expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 824
 825   /* Local declarations will be replaced by their equivalents in this
 826      map.  */
 827   st = id->decl_map;
 828   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 829                                  NULL, NULL);
 830
 831   /* Initialize the parameters.  */
 832   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 833   /* Expand any inlined calls in the initializers.  Do this before we
 834      push FN on the stack of functions we are inlining; we want to
 835      inline calls to FN that appear in the initializers for the
 836      parameters.  */
 837   expand_calls_inline (&arg_inits, id);
 838   /* And add them to the tree.  */
 839   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits);
 840
 841   /* Record the function we are about to inline so that we can avoid
 842      recursing into it.  */
 843   VARRAY_PUSH_TREE (id->fns, fn);
 844
 845   /* Record the function we are about to inline if optimize_function
 846      has not been called on it yet and we don't have it in the list.  */
 847   if (! DECL_INLINED_FNS (fn))
 848     {
 849       int i;
 850
 851       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
 852         if (VARRAY_TREE (id->inlined_fns, i) == fn)
 853           break;
 854       if (i < 0)
 855         VARRAY_PUSH_TREE (id->inlined_fns, fn);
 856     }
 857
 858   /* Return statements in the function body will be replaced by jumps
 859      to the RET_LABEL.  */
 860   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 861   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 862
 863   /* Create a block to put the parameters in.  We have to do this
 864      after the parameters have been remapped because remapping
 865      parameters is different from remapping ordinary variables.  */
 866   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 867   SCOPE_BEGIN_P (scope_stmt) = 1;
 868   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 869   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 870   TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr);
 871   STMT_EXPR_STMT (expr) = scope_stmt;
 872
 873   /* Tell the debugging backends that this block represents the
 874      outermost scope of the inlined function.  */
 875   if (SCOPE_STMT_BLOCK (scope_stmt))
 876     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 877
 878   /* Declare the return variable for the function.  */
 879   STMT_EXPR_STMT (expr)
 880     = chainon (STMT_EXPR_STMT (expr),
 881                declare_return_variable (id, &use_stmt));
 882
 883   /* After we've initialized the parameters, we insert the body of the
 884      function itself.  */
 885   inlined_body = &STMT_EXPR_STMT (expr);
 886   while (*inlined_body)
 887     inlined_body = &TREE_CHAIN (*inlined_body);
 888   *inlined_body = copy_body (id);
 889
 890   /* Close the block for the parameters.  */
 891   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 892   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 893   if (! DECL_INITIAL (fn)
 894       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
 895     abort ();
 896   remap_block (scope_stmt, NULL_TREE, id);
 897   STMT_EXPR_STMT (expr)
 898     = chainon (STMT_EXPR_STMT (expr), scope_stmt);
 899
 900   /* After the body of the function comes the RET_LABEL.  This must come
 901      before we evaluate the returned value below, because that evalulation
 902      may cause RTL to be generated.  */
 903   STMT_EXPR_STMT (expr)
 904     = chainon (STMT_EXPR_STMT (expr),
 905                build_stmt (LABEL_STMT, id->ret_label));
 906
 907   /* Finally, mention the returned value so that the value of the
 908      statement-expression is the returned value of the function.  */
 909   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 910
 911   /* Clean up.  */
 912   splay_tree_delete (id->decl_map);
 913   id->decl_map = st;
 914
 915   /* The new expression has side-effects if the old one did.  */
 916   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 917
 918   /* Replace the call by the inlined body.  Wrap it in an
 919      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 920      pointing to the right place.  */
 921   chain = TREE_CHAIN (*tp);
 922   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 923                         /*col=*/0);
 924   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 925   TREE_CHAIN (*tp) = chain;
 926   pop_srcloc ();
 927
 928   /* If the value of the new expression is ignored, that's OK.  We
 929      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 930      the equivalent inlined version either.  */
 931   TREE_USED (*tp) = 1;
 932
 933   /* Our function now has more statements than it did before.  */
 934   DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn);
 935   id->inlined_stmts += DECL_NUM_STMTS (fn);
 936
 937   /* Recurse into the body of the just inlined function.  */
 938   expand_calls_inline (inlined_body, id);
 939   VARRAY_POP (id->fns);
 940
 941   /* If we've returned to the top level, clear out the record of how
 942      much inlining has been done.  */
 943   if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn)
 944     id->inlined_stmts = 0;
 945
 946   /* Don't walk into subtrees.  We've already handled them above.  */
 947   *walk_subtrees = 0;
 948
 949   /* Keep iterating.  */
 950   return NULL_TREE;
 951 }
 952
 953 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 954    expansions as appropriate.  */
 955
 956 static void
 957 expand_calls_inline (tp, id)
 958      tree *tp;
 959      inline_data *id;
 960 {
 961   /* Search through *TP, replacing all calls to inline functions by
 962      appropriate equivalents.  Use walk_tree in no-duplicates mode
 963      to avoid exponential time complexity.  (We can't just use
 964      walk_tree_without_duplicates, because of the special TARGET_EXPR
 965      handling in expand_calls.  The hash table is set up in
 966      optimize_function.  */
 967   walk_tree (tp, expand_call_inline, id, id->tree_pruner);
 968 }
 969
 970 /* Expand calls to inline functions in the body of FN.  */
 971
 972 void
 973 optimize_inline_calls (fn)
 974      tree fn;
 975 {
 976   inline_data id;
 977   tree prev_fn;
 978
 979   /* Clear out ID.  */
 980   memset (&id, 0, sizeof (id));
 981
 982   /* Don't allow recursion into FN.  */
 983   VARRAY_TREE_INIT (id.fns, 32, "fns");
 984   VARRAY_PUSH_TREE (id.fns, fn);
 985   /* Or any functions that aren't finished yet.  */
 986   prev_fn = NULL_TREE;
 987   if (current_function_decl)
 988     {
 989       VARRAY_PUSH_TREE (id.fns, current_function_decl);
 990       prev_fn = current_function_decl;
 991     }
 992
 993   prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls)
 994              (&id.fns, prev_fn));
 995
 996   /* Create the stack of TARGET_EXPRs.  */
 997   VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
 998
 999   /* Create the list of functions this call will inline.  */
1000   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1001
1002   /* Keep track of the low-water mark, i.e., the point where the first
1003      real inlining is represented in ID.FNS.  */
1004   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1005
1006   /* Replace all calls to inline functions with the bodies of those
1007      functions.  */
1008   id.tree_pruner = htab_create (37, htab_hash_pointer,
1009                                 htab_eq_pointer, NULL);
1010   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1011
1012   /* Clean up.  */
1013   htab_delete (id.tree_pruner);
1014   VARRAY_FREE (id.fns);
1015   VARRAY_FREE (id.target_exprs);
1016   if (DECL_LANG_SPECIFIC (fn))
1017     {
1018       tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1019
1020       memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1021               VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1022       DECL_INLINED_FNS (fn) = ifn;
1023     }
1024   VARRAY_FREE (id.inlined_fns);
1025 }
1026
1027 /* FN is a function that has a complete body, and CLONE is a function
1028    whose body is to be set to a copy of FN, mapping argument
1029    declarations according to the ARG_MAP splay_tree.  */
1030
1031 void
1032 clone_body (clone, fn, arg_map)
1033      tree clone, fn;
1034      void *arg_map;
1035 {
1036   inline_data id;
1037
1038   /* Clone the body, as if we were making an inline call.  But, remap
1039      the parameters in the callee to the parameters of caller.  If
1040      there's an in-charge parameter, map it to an appropriate
1041      constant.  */
1042   memset (&id, 0, sizeof (id));
1043   VARRAY_TREE_INIT (id.fns, 2, "fns");
1044   VARRAY_PUSH_TREE (id.fns, clone);
1045   VARRAY_PUSH_TREE (id.fns, fn);
1046   id.decl_map = (splay_tree)arg_map;
1047
1048   /* Cloning is treated slightly differently from inlining.  Set
1049      CLONING_P so that it's clear which operation we're performing.  */
1050   id.cloning_p = true;
1051
1052   /* Actually copy the body.  */
1053   TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1054
1055   /* Clean up.  */
1056   VARRAY_FREE (id.fns);
1057 }
1058
1059 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1060    FUNC is called with the DATA and the address of each sub-tree.  If
1061    FUNC returns a non-NULL value, the traversal is aborted, and the
1062    value returned by FUNC is returned.  If HTAB is non-NULL it is used
1063    to record the nodes visited, and to avoid visiting a node more than
1064    once.  */
1065
1066 tree
1067 walk_tree (tp, func, data, htab_)
1068      tree *tp;
1069      walk_tree_fn func;
1070      void *data;
1071      void *htab_;
1072 {
1073   htab_t htab = (htab_t) htab_;
1074   enum tree_code code;
1075   int walk_subtrees;
1076   tree result;
1077
1078 #define WALK_SUBTREE(NODE)                              \
1079   do                                                    \
1080     {                                                   \
1081       result = walk_tree (&(NODE), func, data, htab);   \
1082       if (result)                                       \
1083         return result;                                  \
1084     }                                                   \
1085   while (0)
1086
1087   /* Skip empty subtrees.  */
1088   if (!*tp)
1089     return NULL_TREE;
1090
1091   if (htab)
1092     {
1093       void **slot;
1094
1095       /* Don't walk the same tree twice, if the user has requested
1096          that we avoid doing so.  */
1097       if (htab_find (htab, *tp))
1098         return NULL_TREE;
1099       /* If we haven't already seen this node, add it to the table.  */
1100       slot = htab_find_slot (htab, *tp, INSERT);
1101       *slot = *tp;
1102     }
1103
1104   /* Call the function.  */
1105   walk_subtrees = 1;
1106   result = (*func) (tp, &walk_subtrees, data);
1107
1108   /* If we found something, return it.  */
1109   if (result)
1110     return result;
1111
1112   code = TREE_CODE (*tp);
1113
1114   /* Even if we didn't, FUNC may have decided that there was nothing
1115      interesting below this point in the tree.  */
1116   if (!walk_subtrees)
1117     {
1118       if (statement_code_p (code) || code == TREE_LIST
1119           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1120         /* But we still need to check our siblings.  */
1121         return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
1122       else
1123         return NULL_TREE;
1124     }
1125
1126   /* Handle common cases up front.  */
1127   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1128       || TREE_CODE_CLASS (code) == 'r'
1129       || TREE_CODE_CLASS (code) == 's')
1130     {
1131       int i, len;
1132
1133       /* Set lineno here so we get the right instantiation context
1134          if we call instantiate_decl from inlinable_function_p.  */
1135       if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp))
1136         lineno = STMT_LINENO (*tp);
1137
1138       /* Walk over all the sub-trees of this operand.  */
1139       len = first_rtl_op (code);
1140       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
1141          But, we only want to walk once.  */
1142       if (code == TARGET_EXPR
1143           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
1144         --len;
1145       /* Go through the subtrees.  We need to do this in forward order so
1146          that the scope of a FOR_EXPR is handled properly.  */
1147       for (i = 0; i < len; ++i)
1148         WALK_SUBTREE (TREE_OPERAND (*tp, i));
1149
1150       /* For statements, we also walk the chain so that we cover the
1151          entire statement tree.  */
1152       if (statement_code_p (code))
1153         {
1154           if (code == DECL_STMT
1155               && DECL_STMT_DECL (*tp)
1156               && DECL_P (DECL_STMT_DECL (*tp)))
1157             {
1158               /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
1159                  into declarations that are just mentioned, rather than
1160                  declared; they don't really belong to this part of the tree.
1161                  And, we can see cycles: the initializer for a declaration can
1162                  refer to the declaration itself.  */
1163               WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
1164               WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
1165               WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
1166             }
1167
1168           /* This can be tail-recursion optimized if we write it this way.  */
1169           return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
1170         }
1171
1172       /* We didn't find what we were looking for.  */
1173       return NULL_TREE;
1174     }
1175   else if (TREE_CODE_CLASS (code) == 'd')
1176     {
1177       WALK_SUBTREE (TREE_TYPE (*tp));
1178
1179       /* We didn't find what we were looking for.  */
1180       return NULL_TREE;
1181     }
1182
1183   result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
1184                                                       data, htab);
1185   if (result || ! walk_subtrees)
1186     return result;
1187
1188   /* Not one of the easy cases.  We must explicitly go through the
1189      children.  */
1190   switch (code)
1191     {
1192     case ERROR_MARK:
1193     case IDENTIFIER_NODE:
1194     case INTEGER_CST:
1195     case REAL_CST:
1196     case STRING_CST:
1197     case REAL_TYPE:
1198     case COMPLEX_TYPE:
1199     case VECTOR_TYPE:
1200     case VOID_TYPE:
1201     case BOOLEAN_TYPE:
1202     case UNION_TYPE:
1203     case ENUMERAL_TYPE:
1204     case BLOCK:
1205     case RECORD_TYPE:
1206       /* None of thse have subtrees other than those already walked
1207          above.  */
1208       break;
1209
1210     case POINTER_TYPE:
1211     case REFERENCE_TYPE:
1212       WALK_SUBTREE (TREE_TYPE (*tp));
1213       break;
1214
1215     case TREE_LIST:
1216       WALK_SUBTREE (TREE_VALUE (*tp));
1217       WALK_SUBTREE (TREE_CHAIN (*tp));
1218       break;
1219
1220     case TREE_VEC:
1221       {
1222         int len = TREE_VEC_LENGTH (*tp);
1223         while (len--)
1224           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
1225       }
1226       break;
1227
1228     case COMPLEX_CST:
1229       WALK_SUBTREE (TREE_REALPART (*tp));
1230       WALK_SUBTREE (TREE_IMAGPART (*tp));
1231       break;
1232
1233     case CONSTRUCTOR:
1234       WALK_SUBTREE (CONSTRUCTOR_ELTS (*tp));
1235       break;
1236
1237     case METHOD_TYPE:
1238       WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
1239       /* Fall through.  */
1240
1241     case FUNCTION_TYPE:
1242       WALK_SUBTREE (TREE_TYPE (*tp));
1243       {
1244         tree arg = TYPE_ARG_TYPES (*tp);
1245
1246         /* We never want to walk into default arguments.  */
1247         for (; arg; arg = TREE_CHAIN (arg))
1248           WALK_SUBTREE (TREE_VALUE (arg));
1249       }
1250       break;
1251
1252     case ARRAY_TYPE:
1253       WALK_SUBTREE (TREE_TYPE (*tp));
1254       WALK_SUBTREE (TYPE_DOMAIN (*tp));
1255       break;
1256
1257     case INTEGER_TYPE:
1258       WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
1259       WALK_SUBTREE (TYPE_MAX_VALUE (*tp));
1260       break;
1261
1262     case OFFSET_TYPE:
1263       WALK_SUBTREE (TREE_TYPE (*tp));
1264       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (*tp));
1265       break;
1266
1267     default:
1268       abort ();
1269     }
1270
1271   /* We didn't find what we were looking for.  */
1272   return NULL_TREE;
1273
1274 #undef WALK_SUBTREE
1275 }
1276
1277 /* Like walk_tree, but does not walk duplicate nodes more than
1278    once.  */
1279
1280 tree
1281 walk_tree_without_duplicates (tp, func, data)
1282      tree *tp;
1283      walk_tree_fn func;
1284      void *data;
1285 {
1286   tree result;
1287   htab_t htab;
1288
1289   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1290   result = walk_tree (tp, func, data, htab);
1291   htab_delete (htab);
1292   return result;
1293 }
1294
1295 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
1296
1297 tree
1298 copy_tree_r (tp, walk_subtrees, data)
1299      tree *tp;
1300      int *walk_subtrees;
1301      void *data ATTRIBUTE_UNUSED;
1302 {
1303   enum tree_code code = TREE_CODE (*tp);
1304
1305   /* We make copies of most nodes.  */
1306   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1307       || TREE_CODE_CLASS (code) == 'r'
1308       || TREE_CODE_CLASS (code) == 'c'
1309       || TREE_CODE_CLASS (code) == 's'
1310       || code == TREE_LIST
1311       || code == TREE_VEC
1312       || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1313     {
1314       /* Because the chain gets clobbered when we make a copy, we save it
1315          here.  */
1316       tree chain = TREE_CHAIN (*tp);
1317
1318       /* Copy the node.  */
1319       *tp = copy_node (*tp);
1320
1321       /* Now, restore the chain, if appropriate.  That will cause
1322          walk_tree to walk into the chain as well.  */
1323       if (code == PARM_DECL || code == TREE_LIST
1324           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)
1325           || statement_code_p (code))
1326         TREE_CHAIN (*tp) = chain;
1327
1328       /* For now, we don't update BLOCKs when we make copies.  So, we
1329          have to nullify all scope-statements.  */
1330       if (TREE_CODE (*tp) == SCOPE_STMT)
1331         SCOPE_STMT_BLOCK (*tp) = NULL_TREE;
1332     }
1333   else if (TREE_CODE_CLASS (code) == 't')
1334     /* There's no need to copy types, or anything beneath them.  */
1335     *walk_subtrees = 0;
1336
1337   return NULL_TREE;
1338 }
1339
1340 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
1341    information indicating to what new SAVE_EXPR this one should be
1342    mapped, use that one.  Otherwise, create a new node and enter it in
1343    ST.  FN is the function into which the copy will be placed.  */
1344
1345 void
1346 remap_save_expr (tp, st_, fn, walk_subtrees)
1347      tree *tp;
1348      void *st_;
1349      tree fn;
1350      int *walk_subtrees;
1351 {
1352   splay_tree st = (splay_tree) st_;
1353   splay_tree_node n;
1354
1355   /* See if we already encountered this SAVE_EXPR.  */
1356   n = splay_tree_lookup (st, (splay_tree_key) *tp);
1357
1358   /* If we didn't already remap this SAVE_EXPR, do so now.  */
1359   if (!n)
1360     {
1361       tree t = copy_node (*tp);
1362
1363       /* The SAVE_EXPR is now part of the function into which we
1364          are inlining this body.  */
1365       SAVE_EXPR_CONTEXT (t) = fn;
1366       /* And we haven't evaluated it yet.  */
1367       SAVE_EXPR_RTL (t) = NULL_RTX;
1368       /* Remember this SAVE_EXPR.  */
1369       n = splay_tree_insert (st,
1370                              (splay_tree_key) *tp,
1371                              (splay_tree_value) t);
1372     }
1373   else
1374     /* We've already walked into this SAVE_EXPR, so we needn't do it
1375        again.  */
1376     *walk_subtrees = 0;
1377
1378   /* Replace this SAVE_EXPR with the copy.  */
1379   *tp = (tree) n->value;
1380 }