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