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         (*lang_hooks.decls.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       tree cleanup;
 484
 485       /* Find the initializer.  */
 486       value = (*lang_hooks.tree_inlining.convert_parm_for_inlining)
 487               (p, a ? TREE_VALUE (a) : NULL_TREE, fn);
 488
 489       /* If the parameter is never assigned to, we may not need to
 490          create a new variable here at all.  Instead, we may be able
 491          to just use the argument value.  */
 492       if (TREE_READONLY (p)
 493           && !TREE_ADDRESSABLE (p)
 494           && value && !TREE_SIDE_EFFECTS (value))
 495         {
 496           /* Simplify the value, if possible.  */
 497           value = fold (DECL_P (value) ? decl_constant_value (value) : value);
 498
 499           /* We can't risk substituting complex expressions.  They
 500              might contain variables that will be assigned to later.
 501              Theoretically, we could check the expression to see if
 502              all of the variables that determine its value are
 503              read-only, but we don't bother.  */
 504           if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 505             {
 506               /* If this is a declaration, wrap it a NOP_EXPR so that
 507                  we don't try to put the VALUE on the list of
 508                  BLOCK_VARS.  */
 509               if (DECL_P (value))
 510                 value = build1 (NOP_EXPR, TREE_TYPE (value), value);
 511
 512               splay_tree_insert (id->decl_map,
 513                                  (splay_tree_key) p,
 514                                  (splay_tree_value) value);
 515               continue;
 516             }
 517         }
 518
 519       /* Make an equivalent VAR_DECL.  */
 520       var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 521       /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 522          that way, when the PARM_DECL is encountered, it will be
 523          automatically replaced by the VAR_DECL.  */
 524       splay_tree_insert (id->decl_map,
 525                          (splay_tree_key) p,
 526                          (splay_tree_value) var);
 527
 528       /* Declare this new variable.  */
 529       init_stmt = build_stmt (DECL_STMT, var);
 530       TREE_CHAIN (init_stmt) = init_stmts;
 531       init_stmts = init_stmt;
 532
 533       /* Initialize this VAR_DECL from the equivalent argument.  If
 534          the argument is an object, created via a constructor or copy,
 535          this will not result in an extra copy: the TARGET_EXPR
 536          representing the argument will be bound to VAR, and the
 537          object will be constructed in VAR.  */
 538       if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 539         DECL_INITIAL (var) = value;
 540       else
 541         {
 542           /* Even if P was TREE_READONLY, the new VAR should not be.
 543              In the original code, we would have constructed a
 544              temporary, and then the function body would have never
 545              changed the value of P.  However, now, we will be
 546              constructing VAR directly.  The constructor body may
 547              change its value multiple times as it is being
 548              constructed.  Therefore, it must not be TREE_READONLY;
 549              the back-end assumes that TREE_READONLY variable is
 550              assigned to only once.  */
 551           TREE_READONLY (var) = 0;
 552
 553           /* Build a run-time initialization.  */
 554           init_stmt = build_stmt (EXPR_STMT,
 555                                   build (INIT_EXPR, TREE_TYPE (p),
 556                                          var, value));
 557           /* Add this initialization to the list.  Note that we want the
 558              declaration *after* the initialization because we are going
 559              to reverse all the initialization statements below.  */
 560           TREE_CHAIN (init_stmt) = init_stmts;
 561           init_stmts = init_stmt;
 562         }
 563
 564       /* See if we need to clean up the declaration.  */
 565       cleanup = (*lang_hooks.maybe_build_cleanup) (var);
 566       if (cleanup)
 567         {
 568           tree cleanup_stmt;
 569           /* Build the cleanup statement.  */
 570           cleanup_stmt = build_stmt (CLEANUP_STMT, var, cleanup);
 571           /* Add it to the *front* of the list; the list will be
 572              reversed below.  */
 573           TREE_CHAIN (cleanup_stmt) = init_stmts;
 574           init_stmts = cleanup_stmt;
 575         }
 576     }
 577
 578   /* Evaluate trailing arguments.  */
 579   for (; a; a = TREE_CHAIN (a))
 580     {
 581       tree init_stmt;
 582       tree value = TREE_VALUE (a);
 583
 584       if (! value || ! TREE_SIDE_EFFECTS (value))
 585         continue;
 586
 587       init_stmt = build_stmt (EXPR_STMT, value);
 588       TREE_CHAIN (init_stmt) = init_stmts;
 589       init_stmts = init_stmt;
 590     }
 591
 592   /* The initialization statements have been built up in reverse
 593      order.  Straighten them out now.  */
 594   return nreverse (init_stmts);
 595 }
 596
 597 /* Declare a return variable to replace the RESULT_DECL for the
 598    function we are calling.  An appropriate DECL_STMT is returned.
 599    The USE_STMT is filled in to contain a use of the declaration to
 600    indicate the return value of the function.  */
 601
 602 static tree
 603 declare_return_variable (id, use_stmt)
 604      struct inline_data *id;
 605      tree *use_stmt;
 606 {
 607   tree fn = VARRAY_TOP_TREE (id->fns);
 608   tree result = DECL_RESULT (fn);
 609   tree var;
 610   int need_return_decl = 1;
 611
 612   /* We don't need to do anything for functions that don't return
 613      anything.  */
 614   if (!result || VOID_TYPE_P (TREE_TYPE (result)))
 615     {
 616       *use_stmt = NULL_TREE;
 617       return NULL_TREE;
 618     }
 619
 620   var = ((*lang_hooks.tree_inlining.copy_res_decl_for_inlining)
 621          (result, fn, VARRAY_TREE (id->fns, 0), id->decl_map,
 622           &need_return_decl, &id->target_exprs));
 623
 624   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 625      way, when the RESULT_DECL is encountered, it will be
 626      automatically replaced by the VAR_DECL.  */
 627   splay_tree_insert (id->decl_map,
 628                      (splay_tree_key) result,
 629                      (splay_tree_value) var);
 630
 631   /* Build the USE_STMT.  If the return type of the function was
 632      promoted, convert it back to the expected type.  */
 633   if (TREE_TYPE (var) == TREE_TYPE (TREE_TYPE (fn)))
 634     *use_stmt = build_stmt (EXPR_STMT, var);
 635   else
 636     *use_stmt = build_stmt (EXPR_STMT,
 637                             build1 (NOP_EXPR, TREE_TYPE (TREE_TYPE (fn)),
 638                                     var));
 639
 640   TREE_ADDRESSABLE (*use_stmt) = 1;
 641
 642   /* Build the declaration statement if FN does not return an
 643      aggregate.  */
 644   if (need_return_decl)
 645     return build_stmt (DECL_STMT, var);
 646   /* If FN does return an aggregate, there's no need to declare the
 647      return variable; we're using a variable in our caller's frame.  */
 648   else
 649     return NULL_TREE;
 650 }
 651
 652 /* Returns non-zero if a function can be inlined as a tree.  */
 653
 654 int
 655 tree_inlinable_function_p (fn)
 656      tree fn;
 657 {
 658   return inlinable_function_p (fn, NULL);
 659 }
 660
 661 /* Returns non-zero if FN is a function that can be inlined into the
 662    inlining context ID_.  If ID_ is NULL, check whether the function
 663    can be inlined at all.  */
 664
 665 static int
 666 inlinable_function_p (fn, id)
 667      tree fn;
 668      inline_data *id;
 669 {
 670   int inlinable;
 671   int currfn_insns;
 672
 673   /* If we've already decided this function shouldn't be inlined,
 674      there's no need to check again.  */
 675   if (DECL_UNINLINABLE (fn))
 676     return 0;
 677
 678   /* Assume it is not inlinable.  */
 679   inlinable = 0;
 680
 681   /* The number of instructions (estimated) of current function.  */
 682   currfn_insns = DECL_NUM_STMTS (fn) * INSNS_PER_STMT;
 683
 684   /* If we're not inlining things, then nothing is inlinable.  */
 685   if (! flag_inline_trees)
 686     ;
 687   /* If we're not inlining all functions and the function was not
 688      declared `inline', we don't inline it.  Don't think of
 689      disregarding DECL_INLINE when flag_inline_trees == 2; it's the
 690      front-end that must set DECL_INLINE in this case, because
 691      dwarf2out loses if a function is inlined that doesn't have
 692      DECL_INLINE set.  */
 693   else if (! DECL_INLINE (fn))
 694     ;
 695   /* We can't inline functions that are too big.  Only allow a single
 696      function to be of MAX_INLINE_INSNS_SINGLE size.  Make special
 697      allowance for extern inline functions, though.  */
 698   else if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 699            && currfn_insns > MAX_INLINE_INSNS_SINGLE)
 700     ;
 701   /* All is well.  We can inline this function.  Traditionally, GCC
 702      has refused to inline functions using alloca, or functions whose
 703      values are returned in a PARALLEL, and a few other such obscure
 704      conditions.  We are not equally constrained at the tree level.  */
 705   else
 706     inlinable = 1;
 707
 708   /* Squirrel away the result so that we don't have to check again.  */
 709   DECL_UNINLINABLE (fn) = ! inlinable;
 710
 711   /* In case we don't disregard the inlining limits and we basically
 712      can inline this function, investigate further.  */
 713   if (! (*lang_hooks.tree_inlining.disregard_inline_limits) (fn)
 714       && inlinable)
 715     {
 716       int sum_insns = (id ? id->inlined_stmts : 0) * INSNS_PER_STMT
 717                      + currfn_insns;
 718       /* In the extreme case that we have exceeded the recursive inlining
 719          limit by a huge factor (128), we just say no. Should not happen
 720          in real life.  */
 721       if (sum_insns > MAX_INLINE_INSNS * 128)
 722          inlinable = 0;
 723       /* If we did not hit the extreme limit, we use a linear function
 724          with slope -1/MAX_INLINE_SLOPE to exceedingly decrease the
 725          allowable size. We always allow a size of MIN_INLINE_INSNS
 726          though.  */
 727       else if ((sum_insns > MAX_INLINE_INSNS)
 728                && (currfn_insns > MIN_INLINE_INSNS))
 729         {
 730           int max_curr = MAX_INLINE_INSNS_SINGLE
 731                         - (sum_insns - MAX_INLINE_INSNS) / MAX_INLINE_SLOPE;
 732           if (currfn_insns > max_curr)
 733             inlinable = 0;
 734         }
 735     }
 736
 737   if (inlinable && (*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn))
 738     inlinable = 0;
 739
 740   /* If we don't have the function body available, we can't inline
 741      it.  */
 742   if (! DECL_SAVED_TREE (fn))
 743     inlinable = 0;
 744
 745   /* Check again, language hooks may have modified it.  */
 746   if (! inlinable || DECL_UNINLINABLE (fn))
 747     return 0;
 748
 749   /* Don't do recursive inlining, either.  We don't record this in
 750      DECL_UNINLINABLE; we may be able to inline this function later.  */
 751   if (id)
 752     {
 753       size_t i;
 754
 755       for (i = 0; i < VARRAY_ACTIVE_SIZE (id->fns); ++i)
 756         if (VARRAY_TREE (id->fns, i) == fn)
 757           return 0;
 758
 759       if (DECL_INLINED_FNS (fn))
 760         {
 761           int j;
 762           tree inlined_fns = DECL_INLINED_FNS (fn);
 763
 764           for (j = 0; j < TREE_VEC_LENGTH (inlined_fns); ++j)
 765             if (TREE_VEC_ELT (inlined_fns, j) == VARRAY_TREE (id->fns, 0))
 766               return 0;
 767         }
 768     }
 769
 770   /* Return the result.  */
 771   return inlinable;
 772 }
 773
 774 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 775
 776 static tree
 777 expand_call_inline (tp, walk_subtrees, data)
 778      tree *tp;
 779      int *walk_subtrees;
 780      void *data;
 781 {
 782   inline_data *id;
 783   tree t;
 784   tree expr;
 785   tree stmt;
 786   tree chain;
 787   tree fn;
 788   tree scope_stmt;
 789   tree use_stmt;
 790   tree arg_inits;
 791   tree *inlined_body;
 792   splay_tree st;
 793
 794   /* See what we've got.  */
 795   id = (inline_data *) data;
 796   t = *tp;
 797
 798   /* Recurse, but letting recursive invocations know that we are
 799      inside the body of a TARGET_EXPR.  */
 800   if (TREE_CODE (*tp) == TARGET_EXPR)
 801     {
 802       int i, len = first_rtl_op (TARGET_EXPR);
 803
 804       /* We're walking our own subtrees.  */
 805       *walk_subtrees = 0;
 806
 807       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 808       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 809
 810       /* Actually walk over them.  This loop is the body of
 811          walk_trees, omitting the case where the TARGET_EXPR
 812          itself is handled.  */
 813       for (i = 0; i < len; ++i)
 814         {
 815           if (i == 2)
 816             ++id->in_target_cleanup_p;
 817           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
 818                      id->tree_pruner);
 819           if (i == 2)
 820             --id->in_target_cleanup_p;
 821         }
 822
 823       /* We're done with this TARGET_EXPR now.  */
 824       VARRAY_POP (id->target_exprs);
 825
 826       return NULL_TREE;
 827     }
 828
 829   if (TYPE_P (t))
 830     /* Because types were not copied in copy_body, CALL_EXPRs beneath
 831        them should not be expanded.  This can happen if the type is a
 832        dynamic array type, for example.  */
 833     *walk_subtrees = 0;
 834
 835   /* From here on, we're only interested in CALL_EXPRs.  */
 836   if (TREE_CODE (t) != CALL_EXPR)
 837     return NULL_TREE;
 838
 839   /* First, see if we can figure out what function is being called.
 840      If we cannot, then there is no hope of inlining the function.  */
 841   fn = get_callee_fndecl (t);
 842   if (!fn)
 843     return NULL_TREE;
 844
 845   /* If fn is a declaration of a function in a nested scope that was
 846      globally declared inline, we don't set its DECL_INITIAL.
 847      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
 848      C++ front-end uses it for cdtors to refer to their internal
 849      declarations, that are not real functions.  Fortunately those
 850      don't have trees to be saved, so we can tell by checking their
 851      DECL_SAVED_TREE.  */
 852   if (! DECL_INITIAL (fn)
 853       && DECL_ABSTRACT_ORIGIN (fn)
 854       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
 855     fn = DECL_ABSTRACT_ORIGIN (fn);
 856
 857   /* Don't try to inline functions that are not well-suited to
 858      inlining.  */
 859   if (!inlinable_function_p (fn, id))
 860     return NULL_TREE;
 861
 862   if (! (*lang_hooks.tree_inlining.start_inlining) (fn))
 863     return NULL_TREE;
 864
 865   /* Set the current filename and line number to the function we are
 866      inlining so that when we create new _STMT nodes here they get
 867      line numbers corresponding to the function we are calling.  We
 868      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 869      because individual statements don't record the filename.  */
 870   push_srcloc (fn->decl.filename, fn->decl.linenum);
 871
 872   /* Build a statement-expression containing code to initialize the
 873      arguments, the actual inline expansion of the body, and a label
 874      for the return statements within the function to jump to.  The
 875      type of the statement expression is the return type of the
 876      function call.  */
 877   expr = build1 (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), make_node (COMPOUND_STMT));
 878   /* There is no scope associated with the statement-expression.  */
 879   STMT_EXPR_NO_SCOPE (expr) = 1;
 880   stmt = STMT_EXPR_STMT (expr);
 881   /* Local declarations will be replaced by their equivalents in this
 882      map.  */
 883   st = id->decl_map;
 884   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 885                                  NULL, NULL);
 886
 887   /* Initialize the parameters.  */
 888   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 889   /* Expand any inlined calls in the initializers.  Do this before we
 890      push FN on the stack of functions we are inlining; we want to
 891      inline calls to FN that appear in the initializers for the
 892      parameters.  */
 893   expand_calls_inline (&arg_inits, id);
 894   /* And add them to the tree.  */
 895   COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), arg_inits);
 896
 897   /* Record the function we are about to inline so that we can avoid
 898      recursing into it.  */
 899   VARRAY_PUSH_TREE (id->fns, fn);
 900
 901   /* Record the function we are about to inline if optimize_function
 902      has not been called on it yet and we don't have it in the list.  */
 903   if (! DECL_INLINED_FNS (fn))
 904     {
 905       int i;
 906
 907       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
 908         if (VARRAY_TREE (id->inlined_fns, i) == fn)
 909           break;
 910       if (i < 0)
 911         VARRAY_PUSH_TREE (id->inlined_fns, fn);
 912     }
 913
 914   /* Return statements in the function body will be replaced by jumps
 915      to the RET_LABEL.  */
 916   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 917   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 918
 919   if (! DECL_INITIAL (fn)
 920       || TREE_CODE (DECL_INITIAL (fn)) != BLOCK)
 921     abort ();
 922
 923   /* Create a block to put the parameters in.  We have to do this
 924      after the parameters have been remapped because remapping
 925      parameters is different from remapping ordinary variables.  */
 926   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 927   SCOPE_BEGIN_P (scope_stmt) = 1;
 928   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 929   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 930   TREE_CHAIN (scope_stmt) = COMPOUND_BODY (stmt);
 931   COMPOUND_BODY (stmt) = scope_stmt;
 932
 933   /* Tell the debugging backends that this block represents the
 934      outermost scope of the inlined function.  */
 935   if (SCOPE_STMT_BLOCK (scope_stmt))
 936     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 937
 938   /* Declare the return variable for the function.  */
 939   COMPOUND_BODY (stmt)
 940     = chainon (COMPOUND_BODY (stmt),
 941                declare_return_variable (id, &use_stmt));
 942
 943   /* After we've initialized the parameters, we insert the body of the
 944      function itself.  */
 945   inlined_body = &COMPOUND_BODY (stmt);
 946   while (*inlined_body)
 947     inlined_body = &TREE_CHAIN (*inlined_body);
 948   *inlined_body = copy_body (id);
 949
 950   /* After the body of the function comes the RET_LABEL.  This must come
 951      before we evaluate the returned value below, because that evalulation
 952      may cause RTL to be generated.  */
 953   COMPOUND_BODY (stmt)
 954     = chainon (COMPOUND_BODY (stmt),
 955                build_stmt (LABEL_STMT, id->ret_label));
 956
 957   /* Finally, mention the returned value so that the value of the
 958      statement-expression is the returned value of the function.  */
 959   COMPOUND_BODY (stmt) = chainon (COMPOUND_BODY (stmt), use_stmt);
 960
 961   /* Close the block for the parameters.  */
 962   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 963   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 964   remap_block (scope_stmt, NULL_TREE, id);
 965   COMPOUND_BODY (stmt)
 966     = chainon (COMPOUND_BODY (stmt), scope_stmt);
 967
 968   /* Clean up.  */
 969   splay_tree_delete (id->decl_map);
 970   id->decl_map = st;
 971
 972   /* The new expression has side-effects if the old one did.  */
 973   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 974
 975   /* Replace the call by the inlined body.  Wrap it in an
 976      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 977      pointing to the right place.  */
 978   chain = TREE_CHAIN (*tp);
 979   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 980                         /*col=*/0);
 981   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 982   TREE_CHAIN (*tp) = chain;
 983   pop_srcloc ();
 984
 985   /* If the value of the new expression is ignored, that's OK.  We
 986      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 987      the equivalent inlined version either.  */
 988   TREE_USED (*tp) = 1;
 989
 990   /* Our function now has more statements than it did before.  */
 991   DECL_NUM_STMTS (VARRAY_TREE (id->fns, 0)) += DECL_NUM_STMTS (fn);
 992   /* For accounting, subtract one for the saved call/ret.  */
 993   id->inlined_stmts += DECL_NUM_STMTS (fn) - 1;
 994
 995   /* Recurse into the body of the just inlined function.  */
 996   expand_calls_inline (inlined_body, id);
 997   VARRAY_POP (id->fns);
 998
 999   /* If we've returned to the top level, clear out the record of how
1000      much inlining has been done.  */
1001   if (VARRAY_ACTIVE_SIZE (id->fns) == id->first_inlined_fn)
1002     id->inlined_stmts = 0;
1003
1004   /* Don't walk into subtrees.  We've already handled them above.  */
1005   *walk_subtrees = 0;
1006
1007   (*lang_hooks.tree_inlining.end_inlining) (fn);
1008
1009   /* Keep iterating.  */
1010   return NULL_TREE;
1011 }
1012
1013 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
1014    expansions as appropriate.  */
1015
1016 static void
1017 expand_calls_inline (tp, id)
1018      tree *tp;
1019      inline_data *id;
1020 {
1021   /* Search through *TP, replacing all calls to inline functions by
1022      appropriate equivalents.  Use walk_tree in no-duplicates mode
1023      to avoid exponential time complexity.  (We can't just use
1024      walk_tree_without_duplicates, because of the special TARGET_EXPR
1025      handling in expand_calls.  The hash table is set up in
1026      optimize_function.  */
1027   walk_tree (tp, expand_call_inline, id, id->tree_pruner);
1028 }
1029
1030 /* Expand calls to inline functions in the body of FN.  */
1031
1032 void
1033 optimize_inline_calls (fn)
1034      tree fn;
1035 {
1036   inline_data id;
1037   tree prev_fn;
1038
1039   /* Clear out ID.  */
1040   memset (&id, 0, sizeof (id));
1041
1042   /* Don't allow recursion into FN.  */
1043   VARRAY_TREE_INIT (id.fns, 32, "fns");
1044   VARRAY_PUSH_TREE (id.fns, fn);
1045   /* Or any functions that aren't finished yet.  */
1046   prev_fn = NULL_TREE;
1047   if (current_function_decl)
1048     {
1049       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1050       prev_fn = current_function_decl;
1051     }
1052
1053   prev_fn = ((*lang_hooks.tree_inlining.add_pending_fn_decls)
1054              (&id.fns, prev_fn));
1055
1056   /* Create the stack of TARGET_EXPRs.  */
1057   VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
1058
1059   /* Create the list of functions this call will inline.  */
1060   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1061
1062   /* Keep track of the low-water mark, i.e., the point where the first
1063      real inlining is represented in ID.FNS.  */
1064   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1065
1066   /* Replace all calls to inline functions with the bodies of those
1067      functions.  */
1068   id.tree_pruner = htab_create (37, htab_hash_pointer,
1069                                 htab_eq_pointer, NULL);
1070   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1071
1072   /* Clean up.  */
1073   htab_delete (id.tree_pruner);
1074   if (DECL_LANG_SPECIFIC (fn))
1075     {
1076       tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1077
1078       memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1079               VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1080       DECL_INLINED_FNS (fn) = ifn;
1081     }
1082 }
1083
1084 /* FN is a function that has a complete body, and CLONE is a function
1085    whose body is to be set to a copy of FN, mapping argument
1086    declarations according to the ARG_MAP splay_tree.  */
1087
1088 void
1089 clone_body (clone, fn, arg_map)
1090      tree clone, fn;
1091      void *arg_map;
1092 {
1093   inline_data id;
1094
1095   /* Clone the body, as if we were making an inline call.  But, remap
1096      the parameters in the callee to the parameters of caller.  If
1097      there's an in-charge parameter, map it to an appropriate
1098      constant.  */
1099   memset (&id, 0, sizeof (id));
1100   VARRAY_TREE_INIT (id.fns, 2, "fns");
1101   VARRAY_PUSH_TREE (id.fns, clone);
1102   VARRAY_PUSH_TREE (id.fns, fn);
1103   id.decl_map = (splay_tree)arg_map;
1104
1105   /* Cloning is treated slightly differently from inlining.  Set
1106      CLONING_P so that it's clear which operation we're performing.  */
1107   id.cloning_p = true;
1108
1109   /* Actually copy the body.  */
1110   TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
1111 }
1112
1113 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.
1114    FUNC is called with the DATA and the address of each sub-tree.  If
1115    FUNC returns a non-NULL value, the traversal is aborted, and the
1116    value returned by FUNC is returned.  If HTAB is non-NULL it is used
1117    to record the nodes visited, and to avoid visiting a node more than
1118    once.  */
1119
1120 tree
1121 walk_tree (tp, func, data, htab_)
1122      tree *tp;
1123      walk_tree_fn func;
1124      void *data;
1125      void *htab_;
1126 {
1127   htab_t htab = (htab_t) htab_;
1128   enum tree_code code;
1129   int walk_subtrees;
1130   tree result;
1131
1132 #define WALK_SUBTREE(NODE)                              \
1133   do                                                    \
1134     {                                                   \
1135       result = walk_tree (&(NODE), func, data, htab);   \
1136       if (result)                                       \
1137         return result;                                  \
1138     }                                                   \
1139   while (0)
1140
1141 #define WALK_SUBTREE_TAIL(NODE)                         \
1142   do                                                    \
1143     {                                                   \
1144        tp = & (NODE);                                   \
1145        goto tail_recurse;                               \
1146     }                                                   \
1147   while (0)
1148
1149  tail_recurse:
1150   /* Skip empty subtrees.  */
1151   if (!*tp)
1152     return NULL_TREE;
1153
1154   if (htab)
1155     {
1156       void **slot;
1157
1158       /* Don't walk the same tree twice, if the user has requested
1159          that we avoid doing so.  */
1160       if (htab_find (htab, *tp))
1161         return NULL_TREE;
1162       /* If we haven't already seen this node, add it to the table.  */
1163       slot = htab_find_slot (htab, *tp, INSERT);
1164       *slot = *tp;
1165     }
1166
1167   /* Call the function.  */
1168   walk_subtrees = 1;
1169   result = (*func) (tp, &walk_subtrees, data);
1170
1171   /* If we found something, return it.  */
1172   if (result)
1173     return result;
1174
1175   code = TREE_CODE (*tp);
1176
1177   /* Even if we didn't, FUNC may have decided that there was nothing
1178      interesting below this point in the tree.  */
1179   if (!walk_subtrees)
1180     {
1181       if (statement_code_p (code) || code == TREE_LIST
1182           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1183         /* But we still need to check our siblings.  */
1184         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1185       else
1186         return NULL_TREE;
1187     }
1188
1189   /* Handle common cases up front.  */
1190   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1191       || TREE_CODE_CLASS (code) == 'r'
1192       || TREE_CODE_CLASS (code) == 's')
1193     {
1194       int i, len;
1195
1196       /* Set lineno here so we get the right instantiation context
1197          if we call instantiate_decl from inlinable_function_p.  */
1198       if (statement_code_p (code) && !STMT_LINENO_FOR_FN_P (*tp))
1199         lineno = STMT_LINENO (*tp);
1200
1201       /* Walk over all the sub-trees of this operand.  */
1202       len = first_rtl_op (code);
1203       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
1204          But, we only want to walk once.  */
1205       if (code == TARGET_EXPR
1206           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
1207         --len;
1208       /* Go through the subtrees.  We need to do this in forward order so
1209          that the scope of a FOR_EXPR is handled properly.  */
1210       for (i = 0; i < len; ++i)
1211         WALK_SUBTREE (TREE_OPERAND (*tp, i));
1212
1213       /* For statements, we also walk the chain so that we cover the
1214          entire statement tree.  */
1215       if (statement_code_p (code))
1216         {
1217           if (code == DECL_STMT
1218               && DECL_STMT_DECL (*tp)
1219               && DECL_P (DECL_STMT_DECL (*tp)))
1220             {
1221               /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
1222                  into declarations that are just mentioned, rather than
1223                  declared; they don't really belong to this part of the tree.
1224                  And, we can see cycles: the initializer for a declaration can
1225                  refer to the declaration itself.  */
1226               WALK_SUBTREE (DECL_INITIAL (DECL_STMT_DECL (*tp)));
1227               WALK_SUBTREE (DECL_SIZE (DECL_STMT_DECL (*tp)));
1228               WALK_SUBTREE (DECL_SIZE_UNIT (DECL_STMT_DECL (*tp)));
1229             }
1230
1231           /* This can be tail-recursion optimized if we write it this way.  */
1232           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1233         }
1234
1235       /* We didn't find what we were looking for.  */
1236       return NULL_TREE;
1237     }
1238   else if (TREE_CODE_CLASS (code) == 'd')
1239     {
1240       WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1241     }
1242
1243   result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
1244                                                       data, htab);
1245   if (result || ! walk_subtrees)
1246     return result;
1247
1248   /* Not one of the easy cases.  We must explicitly go through the
1249      children.  */
1250   switch (code)
1251     {
1252     case ERROR_MARK:
1253     case IDENTIFIER_NODE:
1254     case INTEGER_CST:
1255     case REAL_CST:
1256     case VECTOR_CST:
1257     case STRING_CST:
1258     case REAL_TYPE:
1259     case COMPLEX_TYPE:
1260     case VECTOR_TYPE:
1261     case VOID_TYPE:
1262     case BOOLEAN_TYPE:
1263     case UNION_TYPE:
1264     case ENUMERAL_TYPE:
1265     case BLOCK:
1266     case RECORD_TYPE:
1267       /* None of thse have subtrees other than those already walked
1268          above.  */
1269       break;
1270
1271     case POINTER_TYPE:
1272     case REFERENCE_TYPE:
1273       WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
1274       break;
1275
1276     case TREE_LIST:
1277       WALK_SUBTREE (TREE_VALUE (*tp));
1278       WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
1279       break;
1280
1281     case TREE_VEC:
1282       {
1283         int len = TREE_VEC_LENGTH (*tp);
1284
1285         if (len == 0)
1286           break;
1287
1288         /* Walk all elements but the first.  */
1289         while (--len)
1290           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
1291
1292         /* Now walk the first one as a tail call.  */
1293         WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
1294       }
1295
1296     case COMPLEX_CST:
1297       WALK_SUBTREE (TREE_REALPART (*tp));
1298       WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
1299
1300     case CONSTRUCTOR:
1301       WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
1302
1303     case METHOD_TYPE:
1304       WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
1305       /* Fall through.  */
1306
1307     case FUNCTION_TYPE:
1308       WALK_SUBTREE (TREE_TYPE (*tp));
1309       {
1310         tree arg = TYPE_ARG_TYPES (*tp);
1311
1312         /* We never want to walk into default arguments.  */
1313         for (; arg; arg = TREE_CHAIN (arg))
1314           WALK_SUBTREE (TREE_VALUE (arg));
1315       }
1316       break;
1317
1318     case ARRAY_TYPE:
1319       WALK_SUBTREE (TREE_TYPE (*tp));
1320       WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp));
1321
1322     case INTEGER_TYPE:
1323       WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
1324       WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp));
1325
1326     case OFFSET_TYPE:
1327       WALK_SUBTREE (TREE_TYPE (*tp));
1328       WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp));
1329
1330     default:
1331       abort ();
1332     }
1333
1334   /* We didn't find what we were looking for.  */
1335   return NULL_TREE;
1336
1337 #undef WALK_SUBTREE
1338 }
1339
1340 /* Like walk_tree, but does not walk duplicate nodes more than
1341    once.  */
1342
1343 tree
1344 walk_tree_without_duplicates (tp, func, data)
1345      tree *tp;
1346      walk_tree_fn func;
1347      void *data;
1348 {
1349   tree result;
1350   htab_t htab;
1351
1352   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1353   result = walk_tree (tp, func, data, htab);
1354   htab_delete (htab);
1355   return result;
1356 }
1357
1358 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
1359
1360 tree
1361 copy_tree_r (tp, walk_subtrees, data)
1362      tree *tp;
1363      int *walk_subtrees;
1364      void *data ATTRIBUTE_UNUSED;
1365 {
1366   enum tree_code code = TREE_CODE (*tp);
1367
1368   /* We make copies of most nodes.  */
1369   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
1370       || TREE_CODE_CLASS (code) == 'r'
1371       || TREE_CODE_CLASS (code) == 'c'
1372       || TREE_CODE_CLASS (code) == 's'
1373       || code == TREE_LIST
1374       || code == TREE_VEC
1375       || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
1376     {
1377       /* Because the chain gets clobbered when we make a copy, we save it
1378          here.  */
1379       tree chain = TREE_CHAIN (*tp);
1380
1381       /* Copy the node.  */
1382       *tp = copy_node (*tp);
1383
1384       /* Now, restore the chain, if appropriate.  That will cause
1385          walk_tree to walk into the chain as well.  */
1386       if (code == PARM_DECL || code == TREE_LIST
1387           || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp)
1388           || statement_code_p (code))
1389         TREE_CHAIN (*tp) = chain;
1390
1391       /* For now, we don't update BLOCKs when we make copies.  So, we
1392          have to nullify all scope-statements.  */
1393       if (TREE_CODE (*tp) == SCOPE_STMT)
1394         SCOPE_STMT_BLOCK (*tp) = NULL_TREE;
1395     }
1396   else if (TREE_CODE_CLASS (code) == 't')
1397     /* There's no need to copy types, or anything beneath them.  */
1398     *walk_subtrees = 0;
1399
1400   return NULL_TREE;
1401 }
1402
1403 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
1404    information indicating to what new SAVE_EXPR this one should be
1405    mapped, use that one.  Otherwise, create a new node and enter it in
1406    ST.  FN is the function into which the copy will be placed.  */
1407
1408 void
1409 remap_save_expr (tp, st_, fn, walk_subtrees)
1410      tree *tp;
1411      void *st_;
1412      tree fn;
1413      int *walk_subtrees;
1414 {
1415   splay_tree st = (splay_tree) st_;
1416   splay_tree_node n;
1417
1418   /* See if we already encountered this SAVE_EXPR.  */
1419   n = splay_tree_lookup (st, (splay_tree_key) *tp);
1420
1421   /* If we didn't already remap this SAVE_EXPR, do so now.  */
1422   if (!n)
1423     {
1424       tree t = copy_node (*tp);
1425
1426       /* The SAVE_EXPR is now part of the function into which we
1427          are inlining this body.  */
1428       SAVE_EXPR_CONTEXT (t) = fn;
1429       /* And we haven't evaluated it yet.  */
1430       SAVE_EXPR_RTL (t) = NULL_RTX;
1431       /* Remember this SAVE_EXPR.  */
1432       n = splay_tree_insert (st,
1433                              (splay_tree_key) *tp,
1434                              (splay_tree_value) t);
1435       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
1436       splay_tree_insert (st, (splay_tree_key) t,
1437                          (splay_tree_value) error_mark_node);
1438     }
1439   else
1440     /* We've already walked into this SAVE_EXPR, so we needn't do it
1441        again.  */
1442     *walk_subtrees = 0;
1443
1444   /* Replace this SAVE_EXPR with the copy.  */
1445   *tp = (tree) n->value;
1446 }