gcc/cp/optimize.c

   1 /* Perform optimizations on tree structure.
   2    Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
   3    Written by Mark Michell (mark@codesourcery.com).
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify it
   8 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, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 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 the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "tree.h"
  25 #include "cp-tree.h"
  26 #include "rtl.h"
  27 #include "insn-config.h"
  28 #include "input.h"
  29 #include "integrate.h"
  30 #include "varray.h"
  31
  32 /* To Do:
  33
  34    o In order to make inlining-on-trees work, we pessimized
  35      function-local static constants.  In particular, they are now
  36      always output, even when not addressed.  Fix this by treating
  37      function-local static constants just like global static
  38      constants; the back-end already knows not to output them if they
  39      are not needed.
  40
  41    o Provide heuristics to clamp inlining of recursive template
  42      calls?  */
  43
  44 /* Data required for function inlining.  */
  45
  46 typedef struct inline_data
  47 {
  48   /* A stack of the functions we are inlining.  For example, if we are
  49      compiling `f', which calls `g', which calls `h', and we are
  50      inlining the body of `h', the stack will contain, `h', followed
  51      by `g', followed by `f'.  */
  52   varray_type fns;
  53   /* The label to jump to when a return statement is encountered.  If
  54      this value is NULL, then return statements will simply be
  55      remapped as return statements, rather than as jumps.  */
  56   tree ret_label;
  57   /* The map from local declarations in the inlined function to
  58      equivalents in the function into which it is being inlined.  */
  59   splay_tree decl_map;
  60   /* Nonzero if we are currently within the cleanup for a
  61      TARGET_EXPR.  */
  62   int in_target_cleanup_p;
  63   /* A stack of the TARGET_EXPRs that we are currently processing.  */
  64   varray_type target_exprs;
  65 } inline_data;
  66
  67 /* Prototypes.  */
  68
  69 static tree initialize_inlined_parameters PARAMS ((inline_data *, tree, tree));
  70 static tree declare_return_variable PARAMS ((inline_data *, tree *));
  71 static tree copy_body_r PARAMS ((tree *, int *, void *));
  72 static tree copy_body PARAMS ((inline_data *));
  73 static tree expand_call_inline PARAMS ((tree *, int *, void *));
  74 static void expand_calls_inline PARAMS ((tree *, inline_data *));
  75 static int inlinable_function_p PARAMS ((tree, inline_data *));
  76 static tree remap_decl PARAMS ((tree, inline_data *));
  77 static void remap_block PARAMS ((tree, tree, inline_data *));
  78 static void copy_scope_stmt PARAMS ((tree *, int *, inline_data *));
  79 static tree calls_setjmp_r PARAMS ((tree *, int *, void *));
  80
  81 /* Remap DECL during the copying of the BLOCK tree for the function.
  82    DATA is really an `inline_data *'.  */
  83
  84 static tree
  85 remap_decl (decl, id)
  86      tree decl;
  87      inline_data *id;
  88 {
  89   splay_tree_node n;
  90   tree fn;
  91
  92   /* We only remap local variables in the current function.  */
  93   fn = VARRAY_TOP_TREE (id->fns);
  94   if (!nonstatic_local_decl_p (decl) || DECL_CONTEXT (decl) != fn)
  95     return NULL_TREE;
  96
  97   /* See if we have remapped this declaration.  */
  98   n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
  99   /* If we didn't already have an equivalent for this declaration,
 100      create one now.  */
 101   if (!n)
 102     {
 103       tree t;
 104
 105       /* Make a copy of the variable or label.  */
 106       t = copy_decl_for_inlining (decl, fn,
 107                                   VARRAY_TREE (id->fns, 0));
 108
 109       /* The decl T could be a dynamic array or other variable size type,
 110          in which case some fields need to be remapped because they may
 111          contain SAVE_EXPRs.  */
 112       walk_tree (&DECL_SIZE (t), copy_body_r, id);
 113       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id);
 114       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
 115           && TYPE_DOMAIN (TREE_TYPE (t)))
 116         {
 117           TREE_TYPE (t) = copy_node (TREE_TYPE (t));
 118           TYPE_DOMAIN (TREE_TYPE (t))
 119             = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
 120           walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
 121                      copy_body_r, id);
 122         }
 123
 124       /* Remember it, so that if we encounter this local entity
 125          again we can reuse this copy.  */
 126       n = splay_tree_insert (id->decl_map,
 127                              (splay_tree_key) decl,
 128                              (splay_tree_value) t);
 129     }
 130
 131   return (tree) n->value;
 132 }
 133
 134 /* Copy the SCOPE_STMT_BLOCK associated with SCOPE_STMT to contain
 135    remapped versions of the variables therein.  And hook the new block
 136    into the block-tree.  If non-NULL, the DECLS are declarations to
 137    add to use instead of the BLOCK_VARS in the old block.  */
 138
 139 static void
 140 remap_block (scope_stmt, decls, id)
 141      tree scope_stmt;
 142      tree decls;
 143      inline_data *id;
 144 {
 145   /* We cannot do this in the cleanup for a TARGET_EXPR since we do
 146      not know whether or not expand_expr will actually write out the
 147      code we put there.  If it does not, then we'll have more BLOCKs
 148      than block-notes, and things will go awry.  At some point, we
 149      should make the back-end handle BLOCK notes in a tidier way,
 150      without requiring a strict correspondence to the block-tree; then
 151      this check can go.  */
 152   if (id->in_target_cleanup_p)
 153     {
 154       SCOPE_STMT_BLOCK (scope_stmt) = NULL_TREE;
 155       return;
 156     }
 157
 158   /* If this is the beginning of a scope, remap the associated BLOCK.  */
 159   if (SCOPE_BEGIN_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
 160     {
 161       tree old_block;
 162       tree new_block;
 163       tree old_var;
 164       tree *first_block;
 165       tree fn;
 166
 167       /* Make the new block.  */
 168       old_block = SCOPE_STMT_BLOCK (scope_stmt);
 169       new_block = make_node (BLOCK);
 170       TREE_USED (new_block) = TREE_USED (old_block);
 171       BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 172       SCOPE_STMT_BLOCK (scope_stmt) = new_block;
 173
 174       /* Remap its variables.  */
 175       for (old_var = decls ? decls : BLOCK_VARS (old_block);
 176            old_var;
 177            old_var = TREE_CHAIN (old_var))
 178         {
 179           tree new_var;
 180
 181           /* Remap the variable.  */
 182           new_var = remap_decl (old_var, id);
 183           /* If we didn't remap this variable, so we can't mess with
 184              its TREE_CHAIN.  If we remapped this variable to
 185              something other than a declaration (say, if we mapped it
 186              to a constant), then we must similarly omit any mention
 187              of it here.  */
 188           if (!new_var || !DECL_P (new_var))
 189             ;
 190           else
 191             {
 192               TREE_CHAIN (new_var) = BLOCK_VARS (new_block);
 193               BLOCK_VARS (new_block) = new_var;
 194             }
 195         }
 196       /* We put the BLOCK_VARS in reverse order; fix that now.  */
 197       BLOCK_VARS (new_block) = nreverse (BLOCK_VARS (new_block));
 198       /* Attach this new block after the DECL_INITIAL block for the
 199          function into which this block is being inlined.  In
 200          rest_of_compilation we will straighten out the BLOCK tree.  */
 201       fn = VARRAY_TREE (id->fns, 0);
 202       if (DECL_INITIAL (fn))
 203         first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
 204       else
 205         first_block = &DECL_INITIAL (fn);
 206       BLOCK_CHAIN (new_block) = *first_block;
 207       *first_block = new_block;
 208       /* Remember the remapped block.  */
 209       splay_tree_insert (id->decl_map,
 210                          (splay_tree_key) old_block,
 211                          (splay_tree_value) new_block);
 212     }
 213   /* If this is the end of a scope, set the SCOPE_STMT_BLOCK to be the
 214      remapped block.  */
 215   else if (SCOPE_END_P (scope_stmt) && SCOPE_STMT_BLOCK (scope_stmt))
 216     {
 217       splay_tree_node n;
 218
 219       /* Find this block in the table of remapped things.  */
 220       n = splay_tree_lookup (id->decl_map,
 221                              (splay_tree_key) SCOPE_STMT_BLOCK (scope_stmt));
 222       my_friendly_assert (n != NULL, 19991203);
 223       SCOPE_STMT_BLOCK (scope_stmt) = (tree) n->value;
 224     }
 225 }
 226
 227 /* Copy the SCOPE_STMT pointed to by TP.  */
 228
 229 static void
 230 copy_scope_stmt (tp, walk_subtrees, id)
 231      tree *tp;
 232      int *walk_subtrees;
 233      inline_data *id;
 234 {
 235   tree block;
 236
 237   /* Remember whether or not this statement was nullified.  When
 238      making a copy, copy_tree_r always sets SCOPE_NULLIFIED_P (and
 239      doesn't copy the SCOPE_STMT_BLOCK) to free callers from having to
 240      deal with copying BLOCKs if they do not wish to do so.  */
 241   block = SCOPE_STMT_BLOCK (*tp);
 242   /* Copy (and replace) the statement.  */
 243   copy_tree_r (tp, walk_subtrees, NULL);
 244   /* Restore the SCOPE_STMT_BLOCK.  */
 245   SCOPE_STMT_BLOCK (*tp) = block;
 246
 247   /* Remap the associated block.  */
 248   remap_block (*tp, NULL_TREE, id);
 249 }
 250
 251 /* Called from copy_body via walk_tree.  DATA is really an
 252    `inline_data *'.  */
 253
 254 static tree
 255 copy_body_r (tp, walk_subtrees, data)
 256      tree *tp;
 257      int *walk_subtrees;
 258      void *data;
 259 {
 260   inline_data* id;
 261   tree fn;
 262
 263   /* Set up.  */
 264   id = (inline_data *) data;
 265   fn = VARRAY_TOP_TREE (id->fns);
 266
 267   /* All automatic variables should have a DECL_CONTEXT indicating
 268      what function they come from.  */
 269   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 270       && DECL_NAMESPACE_SCOPE_P (*tp))
 271     my_friendly_assert (DECL_EXTERNAL (*tp) || TREE_STATIC (*tp),
 272                         19991113);
 273
 274   /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
 275      GOTO_STMT with the RET_LABEL as its target.  */
 276   if (TREE_CODE (*tp) == RETURN_STMT && id->ret_label)
 277     {
 278       tree return_stmt = *tp;
 279       tree goto_stmt;
 280
 281       /* Build the GOTO_STMT.  */
 282       goto_stmt = build_min_nt (GOTO_STMT, id->ret_label);
 283       TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt);
 284
 285       /* If we're returning something, just turn that into an
 286          assignment into the equivalent of the original
 287          RESULT_DECL.  */
 288       if (RETURN_EXPR (return_stmt))
 289         {
 290           *tp = build_min_nt (EXPR_STMT,
 291                               RETURN_EXPR (return_stmt));
 292           /* And then jump to the end of the function.  */
 293           TREE_CHAIN (*tp) = goto_stmt;
 294         }
 295       /* If we're not returning anything just do the jump.  */
 296       else
 297         *tp = goto_stmt;
 298     }
 299   /* Local variables and labels need to be replaced by equivalent
 300      variables.  We don't want to copy static variables; there's only
 301      one of those, no matter how many times we inline the containing
 302      function.  */
 303   else if (nonstatic_local_decl_p (*tp) && DECL_CONTEXT (*tp) == fn)
 304     {
 305       tree new_decl;
 306
 307       /* Remap the declaration.  */
 308       new_decl = remap_decl (*tp, id);
 309       my_friendly_assert (new_decl != NULL_TREE, 19991203);
 310       /* Replace this variable with the copy.  */
 311       STRIP_TYPE_NOPS (new_decl);
 312       *tp = new_decl;
 313     }
 314   else if (nonstatic_local_decl_p (*tp)
 315            && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
 316     my_friendly_abort (0);
 317   else if (TREE_CODE (*tp) == SAVE_EXPR)
 318     remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0),
 319                      walk_subtrees);
 320   else if (TREE_CODE (*tp) == UNSAVE_EXPR)
 321     my_friendly_abort (19991113);
 322   /* For a SCOPE_STMT, we must copy the associated block so that we
 323      can write out debugging information for the inlined variables.  */
 324   else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p)
 325     copy_scope_stmt (tp, walk_subtrees, id);
 326   /* Otherwise, just copy the node.  Note that copy_tree_r already
 327      knows not to copy VAR_DECLs, etc., so this is safe.  */
 328   else
 329     {
 330       copy_tree_r (tp, walk_subtrees, NULL);
 331
 332       /* The copied TARGET_EXPR has never been expanded, even if the
 333          original node was expanded already.  */
 334       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 335         {
 336           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 337           TREE_OPERAND (*tp, 3) = NULL_TREE;
 338         }
 339       /* Similarly, if we're copying a CALL_EXPR, the RTL for the
 340          result is no longer valid.  */
 341       else if (TREE_CODE (*tp) == CALL_EXPR)
 342         CALL_EXPR_RTL (*tp) = NULL_RTX;
 343     }
 344
 345   /* Keep iterating.  */
 346   return NULL_TREE;
 347 }
 348
 349 /* Make a copy of the body of FN so that it can be inserted inline in
 350    another function.  */
 351
 352 static tree
 353 copy_body (id)
 354      inline_data *id;
 355 {
 356   tree body;
 357
 358   body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
 359   walk_tree (&body, copy_body_r, id);
 360
 361   return body;
 362 }
 363
 364 /* Generate code to initialize the parameters of the function at the
 365    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 366
 367 static tree
 368 initialize_inlined_parameters (id, args, fn)
 369      inline_data *id;
 370      tree args;
 371      tree fn;
 372 {
 373   tree init_stmts;
 374   tree parms;
 375   tree a;
 376   tree p;
 377
 378   /* Figure out what the parameters are.  */
 379   parms = DECL_ARGUMENTS (fn);
 380
 381   /* Start with no initializations whatsoever.  */
 382   init_stmts = NULL_TREE;
 383
 384   /* Loop through the parameter declarations, replacing each with an
 385      equivalent VAR_DECL, appropriately initialized.  */
 386   for (p = parms, a = args; p; a = TREE_CHAIN (a), p = TREE_CHAIN (p))
 387     {
 388       tree init_stmt;
 389       tree var;
 390       tree value;
 391
 392       /* Find the initializer.  */
 393       value = TREE_VALUE (a);
 394       /* If the parameter is never assigned to, we may not need to
 395          create a new variable here at all.  Instead, we may be able
 396          to just use the argument value.  */
 397       if (TREE_READONLY (p)
 398           && !TREE_ADDRESSABLE (p)
 399           && !TREE_SIDE_EFFECTS (value))
 400         {
 401           /* Simplify the value, if possible.  */
 402           value = fold (decl_constant_value (value));
 403
 404           /* We can't risk substituting complex expressions.  They
 405              might contain variables that will be assigned to later.
 406              Theoretically, we could check the expression to see if
 407              all of the variables that determine its value are
 408              read-only, but we don't bother.  */
 409           if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 410             {
 411               /* If this is a declaration, wrap it a NOP_EXPR so that
 412                  we don't try to put the VALUE on the list of
 413                  BLOCK_VARS.  */
 414               if (DECL_P (value))
 415                 value = build1 (NOP_EXPR, TREE_TYPE (value), value);
 416
 417               splay_tree_insert (id->decl_map,
 418                                  (splay_tree_key) p,
 419                                  (splay_tree_value) value);
 420               continue;
 421             }
 422         }
 423
 424       /* Make an equivalent VAR_DECL.  */
 425       var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 426       /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 427          that way, when the PARM_DECL is encountered, it will be
 428          automatically replaced by the VAR_DECL.  */
 429       splay_tree_insert (id->decl_map,
 430                          (splay_tree_key) p,
 431                          (splay_tree_value) var);
 432
 433       /* Declare this new variable.  */
 434       init_stmt = build_min_nt (DECL_STMT, var);
 435       TREE_CHAIN (init_stmt) = init_stmts;
 436       init_stmts = init_stmt;
 437
 438       /* Initialize this VAR_DECL from the equivalent argument.  If
 439          the argument is an object, created via a constructor or copy,
 440          this will not result in an extra copy: the TARGET_EXPR
 441          representing the argument will be bound to VAR, and the
 442          object will be constructed in VAR.  */
 443       if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 444         DECL_INITIAL (var) = value;
 445       else
 446         {
 447           init_stmt = build_min_nt (EXPR_STMT,
 448                                     build (INIT_EXPR, TREE_TYPE (p),
 449                                            var, value));
 450           /* Add this initialization to the list.  Note that we want the
 451              declaration *after* the initialization because we are going
 452              to reverse all the initialization statements below.  */
 453           TREE_CHAIN (init_stmt) = init_stmts;
 454           init_stmts = init_stmt;
 455         }
 456     }
 457
 458   /* The initialization statements have been built up in reverse
 459      order.  Straighten them out now.  */
 460   return nreverse (init_stmts);
 461 }
 462
 463 /* Declare a return variable to replace the RESULT_DECL for the
 464    function we are calling.  An appropriate DECL_STMT is returned.
 465    The USE_STMT is filled in to contain a use of the declaration to
 466    indicate the return value of the function.  */
 467
 468 static tree
 469 declare_return_variable (id, use_stmt)
 470      struct inline_data *id;
 471      tree *use_stmt;
 472 {
 473   tree fn = VARRAY_TOP_TREE (id->fns);
 474   tree result = DECL_RESULT (fn);
 475   tree var;
 476   int aggregate_return_p;
 477
 478   /* We don't need to do anything for functions that don't return
 479      anything.  */
 480   if (!result || VOID_TYPE_P (TREE_TYPE (result)))
 481     {
 482       *use_stmt = NULL_TREE;
 483       return NULL_TREE;
 484     }
 485
 486   /* Figure out whether or not FN returns an aggregate.  */
 487   aggregate_return_p = IS_AGGR_TYPE (TREE_TYPE (result));
 488
 489   /* If FN returns an aggregate then the caller will always create the
 490      temporary (using a TARGET_EXPR) and the call will be the
 491      initializing expression for the TARGET_EXPR.  If we were just to
 492      create a new VAR_DECL here, then the result of this function
 493      would be copied (bitwise) into the variable initialized by the
 494      TARGET_EXPR.  That's incorrect, so we must transform any
 495      references to the RESULT into references to the target.  */
 496   if (aggregate_return_p)
 497     {
 498       my_friendly_assert (id->target_exprs->elements_used != 0,
 499                           20000430);
 500       var = TREE_OPERAND (VARRAY_TOP_TREE (id->target_exprs), 0);
 501       my_friendly_assert
 502         (same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (var),
 503                                                     TREE_TYPE (result)),
 504          20000430);
 505     }
 506   /* Otherwise, make an appropriate copy.  */
 507   else
 508     var = copy_decl_for_inlining (result, fn, VARRAY_TREE (id->fns, 0));
 509
 510   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 511      way, when the RESULT_DECL is encountered, it will be
 512      automatically replaced by the VAR_DECL.  */
 513   splay_tree_insert (id->decl_map,
 514                      (splay_tree_key) result,
 515                      (splay_tree_value) var);
 516
 517   /* Build the USE_STMT.  */
 518   *use_stmt = build_min_nt (EXPR_STMT, var);
 519
 520   /* Build the declaration statement if FN does not return an
 521      aggregate.  */
 522   if (!aggregate_return_p)
 523     return build_min_nt (DECL_STMT, var);
 524   /* If FN does return an aggregate, there's no need to declare the
 525      return variable; we're using a variable in our caller's frame.  */
 526   else
 527     return NULL_TREE;
 528 }
 529
 530 /* Returns non-zero if FN is a function that can be inlined.  */
 531
 532 static int
 533 inlinable_function_p (fn, id)
 534      tree fn;
 535      inline_data *id;
 536 {
 537   int inlinable;
 538
 539   /* If we've already decided this function shouldn't be inlined,
 540      there's no need to check again.  */
 541   if (DECL_UNINLINABLE (fn))
 542     return 0;
 543
 544   /* Assume it is not inlinable.  */
 545   inlinable = 0;
 546
 547   /* If we're not inlining things, then nothing is inlinable.  */
 548   if (!flag_inline_trees)
 549     ;
 550   /* If the function was not declared `inline', then we don't inline
 551      it.  */
 552   else if (!DECL_INLINE (fn))
 553     ;
 554   /* We can't inline varargs functions.  */
 555   else if (varargs_function_p (fn))
 556     ;
 557   /* All is well.  We can inline this function.  Traditionally, GCC
 558      has refused to inline functions using alloca, or functions whose
 559      values are returned in a PARALLEL, and a few other such obscure
 560      conditions.  We are not equally constrained at the tree level.  */
 561   else
 562     inlinable = 1;
 563
 564   /* Squirrel away the result so that we don't have to check again.  */
 565   DECL_UNINLINABLE (fn) = !inlinable;
 566
 567   /* We can inline a template instantiation only if it's fully
 568      instantiated.  */
 569   if (inlinable
 570       && DECL_TEMPLATE_INFO (fn)
 571       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
 572     {
 573       fn = instantiate_decl (fn, /*defer_ok=*/0);
 574       inlinable = !TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn));
 575     }
 576
 577   /* If we don't have the function body available, we can't inline
 578      it.  */
 579   if (!DECL_SAVED_TREE (fn))
 580     inlinable = 0;
 581
 582   /* Don't do recursive inlining, either.  We don't record this in
 583      DECL_UNLINABLE; we may be able to inline this function later.  */
 584   if (inlinable)
 585     {
 586       size_t i;
 587
 588       for (i = 0; i < id->fns->elements_used; ++i)
 589         if (VARRAY_TREE (id->fns, i) == fn)
 590           inlinable = 0;
 591     }
 592
 593   /* Return the result.  */
 594   return inlinable;
 595 }
 596
 597 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 598
 599 static tree
 600 expand_call_inline (tp, walk_subtrees, data)
 601      tree *tp;
 602      int *walk_subtrees;
 603      void *data;
 604 {
 605   inline_data *id;
 606   tree t;
 607   tree expr;
 608   tree chain;
 609   tree fn;
 610   tree scope_stmt;
 611   tree use_stmt;
 612   tree arg_inits;
 613   tree *inlined_body;
 614   splay_tree st;
 615
 616   /* See what we've got.  */
 617   id = (inline_data *) data;
 618   t = *tp;
 619
 620   /* Recurse, but letting recursive invocations know that we are
 621      inside the body of a TARGET_EXPR.  */
 622   if (TREE_CODE (*tp) == TARGET_EXPR)
 623     {
 624       int i, len = first_rtl_op (TARGET_EXPR);
 625
 626       /* We're walking our own subtrees.  */
 627       *walk_subtrees = 0;
 628
 629       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 630       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 631
 632       /* Actually walk over them.  This loop is the body of
 633          walk_trees, omitting the case where the TARGET_EXPR
 634          itself is handled.  */
 635       for (i = 0; i < len; ++i)
 636         {
 637           if (i == 2)
 638             ++id->in_target_cleanup_p;
 639           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data);
 640           if (i == 2)
 641             --id->in_target_cleanup_p;
 642         }
 643
 644       /* We're done with this TARGET_EXPR now.  */
 645       VARRAY_POP (id->target_exprs);
 646
 647       return NULL_TREE;
 648     }
 649
 650   /* From here on, we're only interested in CALL_EXPRs.  */
 651   if (TREE_CODE (t) != CALL_EXPR)
 652     return NULL_TREE;
 653
 654   /* First, see if we can figure out what function is being called.
 655      If we cannot, then there is no hope of inlining the function.  */
 656   fn = get_callee_fndecl (t);
 657   if (!fn)
 658     return NULL_TREE;
 659
 660   /* Don't try to inline functions that are not well-suited to
 661      inlining.  */
 662   if (!inlinable_function_p (fn, id))
 663     return NULL_TREE;
 664
 665   /* Set the current filename and line number to the function we are
 666      inlining so that when we create new _STMT nodes here they get
 667      line numbers corresponding to the function we are calling.  We
 668      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 669      because individual statements don't record the filename.  */
 670   push_srcloc (fn->decl.filename, fn->decl.linenum);
 671
 672   /* Build a statement-expression containing code to initialize the
 673      arguments, the actual inline expansion of the body, and a label
 674      for the return statements within the function to jump to.  The
 675      type of the statement expression is the return type of the
 676      function call.  */
 677   expr = build_min (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 678
 679   /* Local declarations will be replaced by their equivalents in this
 680      map.  */
 681   st = id->decl_map;
 682   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 683                                  NULL, NULL);
 684
 685   /* Initialize the parameters.  */
 686   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 687   /* Expand any inlined calls in the initializers.  Do this before we
 688      push FN on the stack of functions we are inlining; we want to
 689      inline calls to FN that appear in the initializers for the
 690      parameters.  */
 691   expand_calls_inline (&arg_inits, id);
 692   /* And add them to the tree.  */
 693   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits);
 694
 695   /* Record the function we are about to inline so that we can avoid
 696      recursing into it.  */
 697   VARRAY_PUSH_TREE (id->fns, fn);
 698
 699   /* Return statements in the function body will be replaced by jumps
 700      to the RET_LABEL.  */
 701   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 702   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 703
 704   /* Create a block to put the parameters in.  We have to do this
 705      after the parameters have been remapped because remapping
 706      parameters is different from remapping ordinary variables.  */
 707   scope_stmt = build_min_nt (SCOPE_STMT, DECL_INITIAL (fn));
 708   SCOPE_BEGIN_P (scope_stmt) = 1;
 709   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 710   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 711   TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr);
 712   STMT_EXPR_STMT (expr) = scope_stmt;
 713
 714   /* Tell the debugging backends that this block represents the
 715      outermost scope of the inlined function.  */
 716   if (SCOPE_STMT_BLOCK (scope_stmt))
 717     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 718
 719   /* Declare the return variable for the function.  */
 720   STMT_EXPR_STMT (expr)
 721     = chainon (STMT_EXPR_STMT (expr),
 722                declare_return_variable (id, &use_stmt));
 723
 724   /* After we've initialized the parameters, we insert the body of the
 725      function itself.  */
 726   inlined_body = &STMT_EXPR_STMT (expr);
 727   while (*inlined_body)
 728     inlined_body = &TREE_CHAIN (*inlined_body);
 729   *inlined_body = copy_body (id);
 730
 731   /* Close the block for the parameters.  */
 732   scope_stmt = build_min_nt (SCOPE_STMT, DECL_INITIAL (fn));
 733   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 734   my_friendly_assert (DECL_INITIAL (fn)
 735                       && TREE_CODE (DECL_INITIAL (fn)) == BLOCK,
 736                       19991203);
 737   remap_block (scope_stmt, NULL_TREE, id);
 738   STMT_EXPR_STMT (expr)
 739     = chainon (STMT_EXPR_STMT (expr), scope_stmt);
 740
 741   /* After the body of the function comes the RET_LABEL.  This must come
 742      before we evaluate the returned value below, because that evalulation
 743      may cause RTL to be generated.  */
 744   STMT_EXPR_STMT (expr)
 745     = chainon (STMT_EXPR_STMT (expr),
 746                build_min_nt (LABEL_STMT, id->ret_label));
 747
 748   /* Finally, mention the returned value so that the value of the
 749      statement-expression is the returned value of the function.  */
 750   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 751
 752   /* Clean up.  */
 753   splay_tree_delete (id->decl_map);
 754   id->decl_map = st;
 755
 756   /* The new expression has side-effects if the old one did.  */
 757   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 758
 759   /* Replace the call by the inlined body.  Wrap it in an
 760      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 761      pointing to the right place.  */
 762   chain = TREE_CHAIN (*tp);
 763   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 764                         /*col=*/0);
 765   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 766   TREE_CHAIN (*tp) = chain;
 767   pop_srcloc ();
 768
 769   /* If the value of the new expression is ignored, that's OK.  We
 770      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 771      the equivalent inlined version either.  */
 772   TREE_USED (*tp) = 1;
 773
 774   /* Recurse into the body of the just inlined function.  */
 775   expand_calls_inline (inlined_body, id);
 776   VARRAY_POP (id->fns);
 777
 778   /* Don't walk into subtrees.  We've already handled them above.  */
 779   *walk_subtrees = 0;
 780
 781   /* Keep iterating.  */
 782   return NULL_TREE;
 783 }
 784
 785 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 786    expansions as appropriate.  */
 787
 788 static void
 789 expand_calls_inline (tp, id)
 790      tree *tp;
 791      inline_data *id;
 792 {
 793   /* Search through *TP, replacing all calls to inline functions by
 794      appropriate equivalents.  */
 795   walk_tree (tp, expand_call_inline, id);
 796 }
 797
 798 /* Optimize the body of FN.  */
 799
 800 void
 801 optimize_function (fn)
 802      tree fn;
 803 {
 804   /* Expand calls to inline functions.  */
 805   if (flag_inline_trees)
 806     {
 807       inline_data id;
 808       tree prev_fn;
 809       struct saved_scope *s;
 810
 811       /* Clear out ID.  */
 812       memset (&id, 0, sizeof (id));
 813
 814       /* Don't allow recursion into FN.  */
 815       VARRAY_TREE_INIT (id.fns, 32, "fns");
 816       VARRAY_PUSH_TREE (id.fns, fn);
 817       /* Or any functions that aren't finished yet.  */
 818       prev_fn = NULL_TREE;
 819       if (current_function_decl)
 820         {
 821           VARRAY_PUSH_TREE (id.fns, current_function_decl);
 822           prev_fn = current_function_decl;
 823         }
 824       for (s = scope_chain; s; s = s->prev)
 825         if (s->function_decl && s->function_decl != prev_fn)
 826           {
 827             VARRAY_PUSH_TREE (id.fns, s->function_decl);
 828             prev_fn = s->function_decl;
 829           }
 830
 831       /* Create the stack of TARGET_EXPRs.  */
 832       VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
 833
 834       /* Replace all calls to inline functions with the bodies of those
 835          functions.  */
 836       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
 837
 838       /* Clean up.  */
 839       VARRAY_FREE (id.fns);
 840       VARRAY_FREE (id.target_exprs);
 841     }
 842 }
 843
 844 /* Called from calls_setjmp_p via walk_tree.  */
 845
 846 static tree
 847 calls_setjmp_r (tp, walk_subtrees, data)
 848      tree *tp;
 849      int *walk_subtrees ATTRIBUTE_UNUSED;
 850      void *data ATTRIBUTE_UNUSED;
 851 {
 852   /* We're only interested in FUNCTION_DECLS.  */
 853   if (TREE_CODE (*tp) != FUNCTION_DECL)
 854     return NULL_TREE;
 855
 856   return setjmp_call_p (*tp) ? *tp : NULL_TREE;
 857 }
 858
 859 /* Returns non-zero if FN calls `setjmp' or some other function that
 860    can return more than once.  This function is conservative; it may
 861    occasionally return a non-zero value even when FN does not actually
 862    call `setjmp'.  */
 863
 864 int
 865 calls_setjmp_p (fn)
 866      tree fn;
 867 {
 868   return (walk_tree (&DECL_SAVED_TREE (fn), calls_setjmp_r, NULL)
 869           != NULL_TREE);
 870 }
 871
 872 /* FN is a function that has a complete body.  Clone the body as
 873    necessary.  Returns non-zero if there's no longer any need to
 874    process the main body.  */
 875
 876 int
 877 maybe_clone_body (fn)
 878      tree fn;
 879 {
 880   inline_data id;
 881   tree clone;
 882
 883   /* We don't clone constructors and destructors under the old ABI.  */
 884   if (!flag_new_abi)
 885     return 0;
 886
 887   /* We only clone constructors and destructors.  */
 888   if (!DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (fn)
 889       && !DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fn))
 890     return 0;
 891
 892   /* We know that any clones immediately follow FN in the TYPE_METHODS
 893      list.  */
 894   for (clone = TREE_CHAIN (fn);
 895        clone && DECL_CLONED_FUNCTION_P (clone);
 896        clone = TREE_CHAIN (clone))
 897     {
 898       tree parm;
 899       tree clone_parm;
 900       int parmno;
 901
 902       /* Update CLONE's source position information to match FN's.  */
 903       DECL_SOURCE_FILE (clone) = DECL_SOURCE_FILE (fn);
 904       DECL_SOURCE_LINE (clone) = DECL_SOURCE_LINE (fn);
 905       DECL_INLINE (clone) = DECL_INLINE (fn);
 906       DECL_THIS_INLINE (clone) = DECL_THIS_INLINE (fn);
 907       DECL_COMDAT (clone) = DECL_COMDAT (fn);
 908       DECL_WEAK (clone) = DECL_WEAK (fn);
 909       DECL_ONE_ONLY (clone) = DECL_ONE_ONLY (fn);
 910       DECL_SECTION_NAME (clone) = DECL_SECTION_NAME (fn);
 911       DECL_USE_TEMPLATE (clone) = DECL_USE_TEMPLATE (fn);
 912       DECL_EXTERNAL (clone) = DECL_EXTERNAL (fn);
 913       DECL_INTERFACE_KNOWN (clone) = DECL_INTERFACE_KNOWN (fn);
 914       DECL_NOT_REALLY_EXTERN (clone) = DECL_NOT_REALLY_EXTERN (fn);
 915
 916       /* Start processing the function.  */
 917       push_to_top_level ();
 918       start_function (NULL_TREE, clone, NULL_TREE, SF_PRE_PARSED);
 919       store_parm_decls ();
 920
 921       /* Just clone the body, as if we were making an inline call.
 922          But, remap the parameters in the callee to the parameters of
 923          caller.  If there's an in-charge parameter, map it to an
 924          appropriate constant.  */
 925       memset (&id, 0, sizeof (id));
 926       VARRAY_TREE_INIT (id.fns, 2, "fns");
 927       VARRAY_PUSH_TREE (id.fns, clone);
 928       VARRAY_PUSH_TREE (id.fns, fn);
 929
 930       /* Remap the parameters.  */
 931       id.decl_map = splay_tree_new (splay_tree_compare_pointers,
 932                                     NULL, NULL);
 933       for (parmno = 0,
 934              parm = DECL_ARGUMENTS (fn),
 935              clone_parm = DECL_ARGUMENTS (clone);
 936            parm;
 937            ++parmno,
 938              parm = TREE_CHAIN (parm))
 939         {
 940           /* Map the in-charge parameter to an appropriate constant.  */
 941           if (DECL_HAS_IN_CHARGE_PARM_P (fn) && parmno == 1)
 942             {
 943               tree in_charge;
 944               in_charge = in_charge_arg_for_name (DECL_NAME (clone));
 945               splay_tree_insert (id.decl_map,
 946                                  (splay_tree_key) parm,
 947                                  (splay_tree_value) in_charge);
 948
 949               /* For a subobject constructor or destructor, the next
 950                  argument is the VTT parameter.  Remap the VTT_PARM
 951                  from the CLONE to this parameter.  */
 952               if (DECL_NEEDS_VTT_PARM_P (clone))
 953                 {
 954                   splay_tree_insert (id.decl_map,
 955                                      (splay_tree_key) DECL_VTT_PARM (fn),
 956                                      (splay_tree_value) clone_parm);
 957                   splay_tree_insert (id.decl_map,
 958                                      (splay_tree_key) DECL_USE_VTT_PARM (fn),
 959                                      (splay_tree_value) boolean_true_node);
 960                   clone_parm = TREE_CHAIN (clone_parm);
 961                 }
 962               /* Otherwise, map the VTT parameter to `NULL'.  */
 963               else if (DECL_VTT_PARM (fn))
 964                 {
 965                   splay_tree_insert (id.decl_map,
 966                                      (splay_tree_key) DECL_VTT_PARM (fn),
 967                                      (splay_tree_value) null_pointer_node);
 968                   splay_tree_insert (id.decl_map,
 969                                      (splay_tree_key) DECL_USE_VTT_PARM (fn),
 970                                      (splay_tree_value) boolean_false_node);
 971                 }
 972             }
 973           /* Map other parameters to their equivalents in the cloned
 974              function.  */
 975           else
 976             {
 977               splay_tree_insert (id.decl_map,
 978                                  (splay_tree_key) parm,
 979                                  (splay_tree_value) clone_parm);
 980               clone_parm = TREE_CHAIN (clone_parm);
 981             }
 982         }
 983
 984       /* Actually copy the body.  */
 985       TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
 986
 987       /* Clean up.  */
 988       splay_tree_delete (id.decl_map);
 989       VARRAY_FREE (id.fns);
 990
 991       /* Now, expand this function into RTL, if appropriate.  */
 992       current_function_name_declared = 1;
 993       expand_body (finish_function (0));
 994       pop_from_top_level ();
 995     }
 996
 997   /* We don't need to process the original function any further.  */
 998   return 1;
 999 }