gcc/tree-inline.c

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