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.  Don't think of
 671      disregarding DECL_INLINE when flag_inline_trees == 2; it's the
 672      front-end that must set DECL_INLINE in this case, because
 673      dwarf2out loses if a function is inlined that doesn't have
 674      DECL_INLINE set.  */
 675   else if (! DECL_INLINE (fn))
 676     ;
 677   /* We can't inline functions that are too big.  Only allow a single
 678      function to eat up half of our budget.  Make special allowance
 679      for extern inline functions, though.  */
 680   else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 681            && DECL_NUM_STMTS (fn) * INSNS_PER_STMT > MAX_INLINE_INSNS / 2)
 682     ;
 683   /* All is well.  We can inline this function.  Traditionally, GCC
 684      has refused to inline functions using alloca, or functions whose
 685      values are returned in a PARALLEL, and a few other such obscure
 686      conditions.  We are not equally constrained at the tree level.  */
 687   else
 688     inlinable = 1;
 689
 690   /* Squirrel away the result so that we don't have to check again.  */
 691   DECL_UNINLINABLE (fn) = ! inlinable;
 692
 693   /* Even if this function is not itself too big to inline, it might
 694      be that we've done so much inlining already that we don't want to
 695      risk too much inlining any more and thus halve the acceptable
 696      size.  */
 697   if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 698       && ((DECL_NUM_STMTS (fn) + (id ? id->inlined_stmts : 0)) * INSNS_PER_STMT
 699           > MAX_INLINE_INSNS)
 700       && DECL_NUM_STMTS (fn) * INSNS_PER_STMT > MAX_INLINE_INSNS / 4)
 701     inlinable = 0;
 702
 703   if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn))
 704     inlinable = 0;
 705
 706   /* If we don't have the function body available, we can't inline
 707      it.  */
 708   if (! DECL_SAVED_TREE (fn))
 709     inlinable = 0;
 710
 711   /* Check again, language hooks may have modified it.  */
 712   if (! inlinable || DECL_UNINLINABLE (fn))
 713     return 0;
 714
 715   /* Don't do recursive inlining, either.  We don't record this in
 716      DECL_UNINLINABLE; we may be able to inline this function later.  */
 717   if (id)
 718     {
 719       size_t i;
 720
 721       for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i)
 722         if (VARRAY_TREE (id->fns, i) == fn)
 723           return 0;
 724
 725       if (DECL_INLINED_FNS (fn))
 726         {
 727           int j;
 728           tree inlined_fns = DECL_INLINED_FNS (fn);
 729
 730           for (j = 0; j < TREE_VEC_LENGTH (inlined_fns); ++j)
 731             if (TREE_VEC_ELT (inlined_fns, j) == VARRAY_TREE (id->fns, 0))
 732               return 0;
 733         }
 734     }
 735
 736   /* Return the result.  */
 737   return inlinable;
 738 }
 739
 740 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 741
 742 static tree
 743 expand_call_inline (tp, walk_subtrees, data)
 744      tree *tp;
 745      int *walk_subtrees;
 746      void *data;
 747 {
 748   inline_data *id;
 749   tree t;
 750   tree expr;
 751   tree chain;
 752   tree fn;
 753   tree scope_stmt;
 754   tree use_stmt;
 755   tree arg_inits;
 756   tree *inlined_body;
 757   splay_tree st;
 758
 759   /* See what we've got.  */
 760   id = (inline_data *) data;
 761   t = *tp;
 762
 763   /* Recurse, but letting recursive invocations know that we are
 764      inside the body of a TARGET_EXPR.  */
 765   if (TREE_CODE (*tp) == TARGET_EXPR)
 766     {
 767       int i, len = first_rtl_op (TARGET_EXPR);
 768
 769       /* We're walking our own subtrees.  */
 770       *walk_subtrees = 0;
 771
 772       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 773       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 774
 775       /* Actually walk over them.  This loop is the body of
 776          walk_trees, omitting the case where the TARGET_EXPR
 777          itself is handled.  */
 778       for (i = 0; i < len; ++i)
 779         {
 780           if (i == 2)
 781             ++id->in_target_cleanup_p;
 782           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
 783                      id->tree_pruner);
 784           if (i == 2)
 785             --id->in_target_cleanup_p;
 786         }
 787
 788       /* We're done with this TARGET_EXPR now.  */
 789       VARRAY_POP (id->target_exprs);
 790
 791       return NULL_TREE;
 792     }
 793
 794   if (TYPE_P (t))
 795     /* Because types were not copied in copy_body, CALL_EXPRs beneath
 796        them should not be expanded.  This can happen if the type is a
 797        dynamic array type, for example.  */
 798     *walk_subtrees = 0;
 799
 800   /* From here on, we're only interested in CALL_EXPRs.  */
 801   if (TREE_CODE (t) != CALL_EXPR)
 802     return NULL_TREE;
 803
 804   /* First, see if we can figure out what function is being called.
 805      If we cannot, then there is no hope of inlining the function.  */
 806   fn = get_callee_fndecl (t);
 807   if (!fn)
 808     return NULL_TREE;
 809
 810   /* Don't try to inline functions that are not well-suited to
 811      inlining.  */
 812   if (!inlinable_function_p (fn, id))
 813     return NULL_TREE;
 814
 815   /* Set the current filename and line number to the function we are
 816      inlining so that when we create new _STMT nodes here they get
 817      line numbers corresponding to the function we are calling.  We
 818      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 819      because individual statements don't record the filename.  */
 820   push_srcloc (fn->decl.filename, fn->decl.linenum);
 821
 822   /* Build a statement-expression containing code to initialize the
 823      arguments, the actual inline expansion of the body, and a label
 824      for the return statements within the function to jump to.  The
 825      type of the statement expression is the return type of the
 826      function call.  */
 827   expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 828
 829   /* Local declarations will be replaced by their equivalents in this
 830      map.  */
 831   st = id->decl_map;
 832   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 833                                  NULL, NULL);
 834
 835   /* Initialize the parameters.  */
 836   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 837   /* Expand any inlined calls in the initializers.  Do this before we
 838      push FN on the stack of functions we are inlining; we want to
 839      inline calls to FN that appear in the initializers for the
 840      parameters.  */
 841   expand_calls_inline (&arg_inits, id);
 842   /* And add them to the tree.  */
 843   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits);
 844
 845   /* Record the function we are about to inline so that we can avoid
 846      recursing into it.  */
 847   VARRAY_PUSH_TREE (id->fns, fn);
 848
 849   /* Record the function we are about to inline if optimize_function
 850      has not been called on it yet and we don't have it in the list.  */
 851   if (! DECL_INLINED_FNS (fn))
 852     {
 853       int i;
 854
 855       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
 856         if (VARRAY_TREE (id->inlined_fns, i) == fn)
 857           break;
 858       if (i < 0)
 859         VARRAY_PUSH_TREE (id->inlined_fns, fn);
 860     }
 861
 862   /* Return statements in the function body will be replaced by jumps
 863      to the RET_LABEL.  */
 864   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 865   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 866
 867   /* Create a block to put the parameters in.  We have to do this
 868      after the parameters have been remapped because remapping
 869      parameters is different from remapping ordinary variables.  */
 870   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 871   SCOPE_BEGIN_P (scope_stmt) = 1;
 872   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 873   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 874   TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr);
 875   STMT_EXPR_STMT (expr) = scope_stmt;
 876
 877   /* Tell the debugging backends that this block represents the
 878      outermost scope of the inlined function.  */
 879   if (SCOPE_STMT_BLOCK (scope_stmt))
 880     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 881
 882   /* Declare the return variable for the function.  */
 883   STMT_EXPR_STMT (expr)
 884     = chainon (STMT_EXPR_STMT (expr),
 885                declare_return_variable (id, &use_stmt));
 886
 887   /* After we've initialized the parameters, we insert the body of the
 888      function itself.  */
 889   inlined_body = &STMT_EXPR_STMT (expr);
 890   while (*inlined_body)
 891     inlined_body = &TREE_CHAIN (*inlined_body);
 892   *inlined_body = copy_body (id);
 893
 894   /* Close the block for the parameters.  */
 895   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 896   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 897   if (! DECL_INITIAL (fn)
 898       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
 899     abort ();
 900   remap_block (scope_stmt, NULL_TREE, id);
 901   STMT_EXPR_STMT (expr)
 902     = chainon (STMT_EXPR_STMT (expr), scope_stmt);
 903
 904   /* After the body of the function comes the RET_LABEL.  This must come
 905      before we evaluate the returned value below, because that evalulation
 906      may cause RTL to be generated.  */
 907   STMT_EXPR_STMT (expr)
 908     = chainon (STMT_EXPR_STMT (expr),
 909                build_stmt (LABEL_STMT, id->ret_label));
 910
 911   /* Finally, mention the returned value so that the value of the
 912      statement-expression is the returned value of the function.  */
 913   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 914
 915   /* Clean up.  */
 916   splay_tree_delete (id->decl_map);
 917   id->decl_map = st;
 918
 919   /* The new expression has side-effects if the old one did.  */
 920   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 921
 922   /* Replace the call by the inlined body.  Wrap it in an
 923      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 924      pointing to the right place.  */
 925   chain = TREE_CHAIN (*tp);
 926   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 927                         /*col=*/0);
 928   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 929   TREE_CHAIN (*tp) = chain;
 930   pop_srcloc ();
 931
 932   /* If the value of the new expression is ignored, that's OK.  We
 933      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 934      the equivalent inlined version either.  */
 935   TREE_USED (*tp) = 1;
 936
 937   /* Our function now has more statements than it did before.  */
 938   DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn);
 939   id->inlined_stmts += DECL_NUM_STMTS (fn);
 940
 941   /* Recurse into the body of the just inlined function.  */
 942   expand_calls_inline (inlined_body, id);
 943   VARRAY_POP (id->fns);
 944
 945   /* If we've returned to the top level, clear out the record of how
 946      much inlining has been done.  */
 947   if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn)
 948     id->inlined_stmts = 0;
 949
 950   /* Don't walk into subtrees.  We've already handled them above.  */
 951   *walk_subtrees = 0;
 952
 953   /* Keep iterating.  */
 954   return NULL_TREE;
 955 }
 956
 957 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 958    expansions as appropriate.  */
 959
 960 static void
 961 expand_calls_inline (tp, id)
 962      tree *tp;
 963      inline_data *id;
 964 {
 965   /* Search through *TP, replacing all calls to inline functions by
 966      appropriate equivalents.  Use walk_tree in no-duplicates mode
 967      to avoid exponential time complexity.  (We can't just use
 968      walk_tree_without_duplicates, because of the special TARGET_EXPR
 969      handling in expand_calls.  The hash table is set up in
 970      optimize_function.  */
 971   walk_tree (tp, expand_call_inline, id, id->tree_pruner);
 972 }
 973
 974 /* Expand calls to inline functions in the body of FN.  */
 975
 976 void
 977 optimize_inline_calls (fn)
 978      tree fn;
 979 {
 980   inline_data id;
 981   tree prev_fn;
 982
 983   /* Clear out ID.  */
 984   memset (&id, 0, sizeof (id));
 985
 986   /* Don't allow recursion into FN.  */
 987   VARRAY_TREE_INIT (id.fns, 32, "fns");
 988   VARRAY_PUSH_TREE (id.fns, fn);
 989   /* Or any functions that aren't finished yet.  */
 990   prev_fn = NULL_TREE;
 991   if (current_function_decl)
 992     {
 993       VARRAY_PUSH_TREE (id.fns, current_function_decl);
 994       prev_fn = current_function_decl;
 995     }
 996
 997   prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls)
 998              (&id.fns, prev_fn));
 999
1000   /* Create the stack of TARGET_EXPRs.  */
1001   VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
1002
1003   /* Create the list of functions this call will inline.  */
1004   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1005
1006   /* Keep track of the low-water mark, i.e., the point where the first
1007      real inlining is represented in ID.FNS.  */
1008   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1009
1010   /* Replace all calls to inline functions with the bodies of those
1011      functions.  */
1012   id.tree_pruner = htab_create (37, htab_hash_pointer,
1013                                 htab_eq_pointer, NULL);
1014   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1015
1016   /* Clean up.  */
1017   htab_delete (id.tree_pruner);
1018   VARRAY_FREE (id.fns);
1019   VARRAY_FREE (id.target_exprs);
1020   if (DECL_LANG_SPECIFIC (fn))
1021     {
1022       tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1023
1024       memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1025               VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1026       DECL_INLINED_FNS (fn) = ifn;
1027     }
1028   VARRAY_FREE (id.inlined_fns);
1029 }
1030
1031 /* FN is a function that has a complete body, and CLONE is a function
1032    whose body is to be set to a copy of FN, mapping argument
1033    declarations according to the ARG_MAP splay_tree.  */
1034
1035 void
1036 clone_body (clone, fn, arg_map)
1037      tree clone, fn;
1038      void *arg_map;
1039 {
1040   inline_data id;
1041
1042   /* Clone the body, as if we were making an inline call.  But, remap
1043      the parameters in the callee to the parameters of caller.  If
1044      there's an in-charge parameter, map it to an appropriate
1045      constant.  */
1046   memset (&id, 0, sizeof (id));
1047   VARRAY_TREE_INIT (id.fns, 2, "fns");
1048   VARRAY_PUSH_TREE (id.fns, clone);
1049   VARRAY_PUSH_TREE (id.fns, fn);
1050   id.decl_map = (splay_tree)arg_map;
1051
1052   /* Cloning is treated slightly differently from inlining.  Set
1053      CLONING_P so that it's clear which operation we're performing.  */
1054   id.cloning_p = true;
1055
1056   /* Actually copy the body.  */
1057   TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1058
1059   /* Clean up.  */
1060   VARRAY_FREE (id.fns);
1061 }
1062
1063 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1064    FUNC is called with the DATA and the address of each sub-tree.  If
1065    FUNC returns a non-NULL value, the traversal is aborted, and the
1066    value returned by FUNC is returned.  If HTAB is non-NULL it is used
1067    to record the nodes visited, and to avoid visiting a node more than
1068    once.  */
1069
1070 tree
1071 walk_tree (tp, func, data, htab_)
1072      tree *tp;
1073      walk_tree_fn func;
1074      void *data;
1075      void *htab_;
1076 {
1077   htab_t htab = (htab_t) htab_;
1078   enum tree_code code;
1079   int walk_subtrees;
1080   tree result;
1081
1082 #define WALK_SUBTREE(NODE)                              \
1083   do                                                    \
1084     {                                                   \
1085       result = walk_tree (&(NODE), func, data, htab);   \
1086       if (result)                                       \
1087         return result;                                  \
1088     }                                                   \
1089   while (0)
1090
1091   /* Skip empty subtrees.  */
1092   if (!*tp)
1093     return NULL_TREE;
1094
1095   if (htab)
1096     {
1097       void **slot;
1098
1099       /* Don't walk the same tree twice, if the user has requested
1100          that we avoid doing so.  */
1101       if (htab_find (htab, *tp))
1102         return NULL_TREE;
1103       /* If we haven't already seen this node, add it to the table.  */
1104       slot = htab_find_slot (htab, *tp, INSERT);
1105       *slot = *tp;
1106     }
1107
1108   /* Call the function.  */
1109   walk_subtrees = 1;
1110   result = (*func) (tp, &walk_subtrees, data);
1111
1112   /* If we found something, return it.  */
1113   if (result)
1114     return result;
1115
1116   code = TREE_CODE (*tp);
1117
1118   /* Even if we didn't, FUNC may have decided that there was nothing
1119      interesting below this point in the tree.  */
1120   if (!walk_subtrees)
1121     {
1122       if (statement_code_p (code) || code == TREE_LIST
1123           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1124         /* But we still need to check our siblings.  */
1125         return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
1126       else
1127         return NULL_TREE;
1128     }
1129
1130   /* Handle common cases up front.  */
1131   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1132       || TREE_CODE_CLASS (code) == 'r'
1133       || TREE_CODE_CLASS (code) == 's')
1134     {
1135       int i, len;
1136
1137       /* Set lineno here so we get the right instantiation context
1138          if we call instantiate_decl from inlinable_function_p.  */
1139       if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp))
1140         lineno = STMT_LINENO (*tp);
1141
1142       /* Walk over all the sub-trees of this operand.  */
1143       len = first_rtl_op (code);
1144       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
1145          But, we only want to walk once.  */
1146       if (code == TARGET_EXPR
1147           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
1148         --len;
1149       /* Go through the subtrees.  We need to do this in forward order so
1150          that the scope of a FOR_EXPR is handled properly.  */
1151       for (i = 0; i < len; ++i)
1152         WALK_SUBTREE (TREE_OPERAND (*tp, i));
1153
1154       /* For statements, we also walk the chain so that we cover the
1155          entire statement tree.  */
1156       if (statement_code_p (code))
1157         {
1158           if (code == DECL_STMT
1159               && DECL_STMT_DECL (*tp)
1160               && DECL_P (DECL_STMT_DECL (*tp)))
1161             {
1162               /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
1163                  into declarations that are just mentioned, rather than
1164                  declared; they don't really belong to this part of the tree.
1165                  And, we can see cycles: the initializer for a declaration can
1166                  refer to the declaration itself.  */
1167               WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
1168               WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
1169               WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
1170             }
1171
1172           /* This can be tail-recursion optimized if we write it this way.  */
1173           return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
1174         }
1175
1176       /* We didn't find what we were looking for.  */
1177       return NULL_TREE;
1178     }
1179   else if (TREE_CODE_CLASS (code) == 'd')
1180     {
1181       WALK_SUBTREE (TREE_TYPE (*tp));
1182
1183       /* We didn't find what we were looking for.  */
1184       return NULL_TREE;
1185     }
1186
1187   result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
1188                                                       data, htab);
1189   if (result || ! walk_subtrees)
1190     return result;
1191
1192   /* Not one of the easy cases.  We must explicitly go through the
1193      children.  */
1194   switch (code)
1195     {
1196     case ERROR_MARK:
1197     case IDENTIFIER_NODE:
1198     case INTEGER_CST:
1199     case REAL_CST:
1200     case STRING_CST:
1201     case REAL_TYPE:
1202     case COMPLEX_TYPE:
1203     case VECTOR_TYPE:
1204     case VOID_TYPE:
1205     case BOOLEAN_TYPE:
1206     case UNION_TYPE:
1207     case ENUMERAL_TYPE:
1208     case BLOCK:
1209     case RECORD_TYPE:
1210       /* None of thse have subtrees other than those already walked
1211          above.  */
1212       break;
1213
1214     case POINTER_TYPE:
1215     case REFERENCE_TYPE:
1216       WALK_SUBTREE (TREE_TYPE (*tp));
1217       break;
1218
1219     case TREE_LIST:
1220       WALK_SUBTREE (TREE_VALUE (*tp));
1221       WALK_SUBTREE (TREE_CHAIN (*tp));
1222       break;
1223
1224     case TREE_VEC:
1225       {
1226         int len = TREE_VEC_LENGTH (*tp);
1227         while (len--)
1228           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
1229       }
1230       break;
1231
1232     case COMPLEX_CST:
1233       WALK_SUBTREE (TREE_REALPART (*tp));
1234       WALK_SUBTREE (TREE_IMAGPART (*tp));
1235       break;
1236
1237     case CONSTRUCTOR:
1238       WALK_SUBTREE (CONSTRUCTOR_ELTS (*tp));
1239       break;
1240
1241     case METHOD_TYPE:
1242       WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
1243       /* Fall through.  */
1244
1245     case FUNCTION_TYPE:
1246       WALK_SUBTREE (TREE_TYPE (*tp));
1247       {
1248         tree arg = TYPE_ARG_TYPES (*tp);
1249
1250         /* We never want to walk into default arguments.  */
1251         for (; arg; arg = TREE_CHAIN (arg))
1252           WALK_SUBTREE (TREE_VALUE (arg));
1253       }
1254       break;
1255
1256     case ARRAY_TYPE:
1257       WALK_SUBTREE (TREE_TYPE (*tp));
1258       WALK_SUBTREE (TYPE_DOMAIN (*tp));
1259       break;
1260
1261     case INTEGER_TYPE:
1262       WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
1263       WALK_SUBTREE (TYPE_MAX_VALUE (*tp));
1264       break;
1265
1266     case OFFSET_TYPE:
1267       WALK_SUBTREE (TREE_TYPE (*tp));
1268       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (*tp));
1269       break;
1270
1271     default:
1272       abort ();
1273     }
1274
1275   /* We didn't find what we were looking for.  */
1276   return NULL_TREE;
1277
1278 #undef WALK_SUBTREE
1279 }
1280
1281 /* Like walk_tree, but does not walk duplicate nodes more than
1282    once.  */
1283
1284 tree
1285 walk_tree_without_duplicates (tp, func, data)
1286      tree *tp;
1287      walk_tree_fn func;
1288      void *data;
1289 {
1290   tree result;
1291   htab_t htab;
1292
1293   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1294   result = walk_tree (tp, func, data, htab);
1295   htab_delete (htab);
1296   return result;
1297 }
1298
1299 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
1300
1301 tree
1302 copy_tree_r (tp, walk_subtrees, data)
1303      tree *tp;
1304      int *walk_subtrees;
1305      void *data ATTRIBUTE_UNUSED;
1306 {
1307   enum tree_code code = TREE_CODE (*tp);
1308
1309   /* We make copies of most nodes.  */
1310   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1311       || TREE_CODE_CLASS (code) == 'r'
1312       || TREE_CODE_CLASS (code) == 'c'
1313       || TREE_CODE_CLASS (code) == 's'
1314       || code == TREE_LIST
1315       || code == TREE_VEC
1316       || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1317     {
1318       /* Because the chain gets clobbered when we make a copy, we save it
1319          here.  */
1320       tree chain = TREE_CHAIN (*tp);
1321
1322       /* Copy the node.  */
1323       *tp = copy_node (*tp);
1324
1325       /* Now, restore the chain, if appropriate.  That will cause
1326          walk_tree to walk into the chain as well.  */
1327       if (code == PARM_DECL || code == TREE_LIST
1328           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)
1329           || statement_code_p (code))
1330         TREE_CHAIN (*tp) = chain;
1331
1332       /* For now, we don't update BLOCKs when we make copies.  So, we
1333          have to nullify all scope-statements.  */
1334       if (TREE_CODE (*tp) == SCOPE_STMT)
1335         SCOPE_STMT_BLOCK (*tp) = NULL_TREE;
1336     }
1337   else if (TREE_CODE_CLASS (code) == 't')
1338     /* There's no need to copy types, or anything beneath them.  */
1339     *walk_subtrees = 0;
1340
1341   return NULL_TREE;
1342 }
1343
1344 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
1345    information indicating to what new SAVE_EXPR this one should be
1346    mapped, use that one.  Otherwise, create a new node and enter it in
1347    ST.  FN is the function into which the copy will be placed.  */
1348
1349 void
1350 remap_save_expr (tp, st_, fn, walk_subtrees)
1351      tree *tp;
1352      void *st_;
1353      tree fn;
1354      int *walk_subtrees;
1355 {
1356   splay_tree st = (splay_tree) st_;
1357   splay_tree_node n;
1358
1359   /* See if we already encountered this SAVE_EXPR.  */
1360   n = splay_tree_lookup (st, (splay_tree_key) *tp);
1361
1362   /* If we didn't already remap this SAVE_EXPR, do so now.  */
1363   if (!n)
1364     {
1365       tree t = copy_node (*tp);
1366
1367       /* The SAVE_EXPR is now part of the function into which we
1368          are inlining this body.  */
1369       SAVE_EXPR_CONTEXT (t) = fn;
1370       /* And we haven't evaluated it yet.  */
1371       SAVE_EXPR_RTL (t) = NULL_RTX;
1372       /* Remember this SAVE_EXPR.  */
1373       n = splay_tree_insert (st,
1374                              (splay_tree_key) *tp,
1375                              (splay_tree_value) t);
1376     }
1377   else
1378     /* We've already walked into this SAVE_EXPR, so we needn't do it
1379        again.  */
1380     *walk_subtrees = 0;
1381
1382   /* Replace this SAVE_EXPR with the copy.  */
1383   *tp = (tree) n->value;
1384 }