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, NULL);
 113       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 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, NULL);
 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_stmt (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_stmt (EXPR_STMT,
 291                             RETURN_EXPR (return_stmt));
 292           STMT_IS_FULL_EXPR_P (*tp) = 1;
 293           /* And then jump to the end of the function.  */
 294           TREE_CHAIN (*tp) = goto_stmt;
 295         }
 296       /* If we're not returning anything just do the jump.  */
 297       else
 298         *tp = goto_stmt;
 299     }
 300   /* Local variables and labels need to be replaced by equivalent
 301      variables.  We don't want to copy static variables; there's only
 302      one of those, no matter how many times we inline the containing
 303      function.  */
 304   else if (nonstatic_local_decl_p (*tp) && DECL_CONTEXT (*tp) == fn)
 305     {
 306       tree new_decl;
 307
 308       /* Remap the declaration.  */
 309       new_decl = remap_decl (*tp, id);
 310       my_friendly_assert (new_decl != NULL_TREE, 19991203);
 311       /* Replace this variable with the copy.  */
 312       STRIP_TYPE_NOPS (new_decl);
 313       *tp = new_decl;
 314     }
 315   else if (nonstatic_local_decl_p (*tp)
 316            && DECL_CONTEXT (*tp) != VARRAY_TREE (id->fns, 0))
 317     my_friendly_abort (0);
 318   else if (TREE_CODE (*tp) == SAVE_EXPR)
 319     remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0),
 320                      walk_subtrees);
 321   else if (TREE_CODE (*tp) == UNSAVE_EXPR)
 322     my_friendly_abort (19991113);
 323   /* For a SCOPE_STMT, we must copy the associated block so that we
 324      can write out debugging information for the inlined variables.  */
 325   else if (TREE_CODE (*tp) == SCOPE_STMT && !id->in_target_cleanup_p)
 326     copy_scope_stmt (tp, walk_subtrees, id);
 327   /* Otherwise, just copy the node.  Note that copy_tree_r already
 328      knows not to copy VAR_DECLs, etc., so this is safe.  */
 329   else
 330     {
 331       copy_tree_r (tp, walk_subtrees, NULL);
 332
 333       /* The copied TARGET_EXPR has never been expanded, even if the
 334          original node was expanded already.  */
 335       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 336         {
 337           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 338           TREE_OPERAND (*tp, 3) = NULL_TREE;
 339         }
 340     }
 341
 342   /* Keep iterating.  */
 343   return NULL_TREE;
 344 }
 345
 346 /* Make a copy of the body of FN so that it can be inserted inline in
 347    another function.  */
 348
 349 static tree
 350 copy_body (id)
 351      inline_data *id;
 352 {
 353   tree body;
 354
 355   body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
 356   walk_tree (&body, copy_body_r, id, NULL);
 357
 358   return body;
 359 }
 360
 361 /* Generate code to initialize the parameters of the function at the
 362    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 363
 364 static tree
 365 initialize_inlined_parameters (id, args, fn)
 366      inline_data *id;
 367      tree args;
 368      tree fn;
 369 {
 370   tree init_stmts;
 371   tree parms;
 372   tree a;
 373   tree p;
 374
 375   /* Figure out what the parameters are.  */
 376   parms = DECL_ARGUMENTS (fn);
 377
 378   /* Start with no initializations whatsoever.  */
 379   init_stmts = NULL_TREE;
 380
 381   /* Loop through the parameter declarations, replacing each with an
 382      equivalent VAR_DECL, appropriately initialized.  */
 383   for (p = parms, a = args; p; a = TREE_CHAIN (a), p = TREE_CHAIN (p))
 384     {
 385       tree init_stmt;
 386       tree var;
 387       tree value;
 388
 389       /* Find the initializer.  */
 390       value = TREE_VALUE (a);
 391       /* If the parameter is never assigned to, we may not need to
 392          create a new variable here at all.  Instead, we may be able
 393          to just use the argument value.  */
 394       if (TREE_READONLY (p)
 395           && !TREE_ADDRESSABLE (p)
 396           && !TREE_SIDE_EFFECTS (value))
 397         {
 398           /* Simplify the value, if possible.  */
 399           value = fold (decl_constant_value (value));
 400
 401           /* We can't risk substituting complex expressions.  They
 402              might contain variables that will be assigned to later.
 403              Theoretically, we could check the expression to see if
 404              all of the variables that determine its value are
 405              read-only, but we don't bother.  */
 406           if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 407             {
 408               /* If this is a declaration, wrap it a NOP_EXPR so that
 409                  we don't try to put the VALUE on the list of
 410                  BLOCK_VARS.  */
 411               if (DECL_P (value))
 412                 value = build1 (NOP_EXPR, TREE_TYPE (value), value);
 413
 414               splay_tree_insert (id->decl_map,
 415                                  (splay_tree_key) p,
 416                                  (splay_tree_value) value);
 417               continue;
 418             }
 419         }
 420
 421       /* Make an equivalent VAR_DECL.  */
 422       var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 423       /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 424          that way, when the PARM_DECL is encountered, it will be
 425          automatically replaced by the VAR_DECL.  */
 426       splay_tree_insert (id->decl_map,
 427                          (splay_tree_key) p,
 428                          (splay_tree_value) var);
 429
 430       /* Declare this new variable.  */
 431       init_stmt = build_stmt (DECL_STMT, var);
 432       TREE_CHAIN (init_stmt) = init_stmts;
 433       init_stmts = init_stmt;
 434
 435       /* Initialize this VAR_DECL from the equivalent argument.  If
 436          the argument is an object, created via a constructor or copy,
 437          this will not result in an extra copy: the TARGET_EXPR
 438          representing the argument will be bound to VAR, and the
 439          object will be constructed in VAR.  */
 440       if (! TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 441         DECL_INITIAL (var) = value;
 442       else
 443         {
 444           init_stmt = build_stmt (EXPR_STMT,
 445                                   build (INIT_EXPR, TREE_TYPE (p),
 446                                          var, value));
 447           /* Add this initialization to the list.  Note that we want the
 448              declaration *after* the initialization because we are going
 449              to reverse all the initialization statements below.  */
 450           TREE_CHAIN (init_stmt) = init_stmts;
 451           init_stmts = init_stmt;
 452         }
 453     }
 454
 455   /* The initialization statements have been built up in reverse
 456      order.  Straighten them out now.  */
 457   return nreverse (init_stmts);
 458 }
 459
 460 /* Declare a return variable to replace the RESULT_DECL for the
 461    function we are calling.  An appropriate DECL_STMT is returned.
 462    The USE_STMT is filled in to contain a use of the declaration to
 463    indicate the return value of the function.  */
 464
 465 static tree
 466 declare_return_variable (id, use_stmt)
 467      struct inline_data *id;
 468      tree *use_stmt;
 469 {
 470   tree fn = VARRAY_TOP_TREE (id->fns);
 471   tree result = DECL_RESULT (fn);
 472   tree var;
 473   int aggregate_return_p;
 474
 475   /* We don't need to do anything for functions that don't return
 476      anything.  */
 477   if (!result || VOID_TYPE_P (TREE_TYPE (result)))
 478     {
 479       *use_stmt = NULL_TREE;
 480       return NULL_TREE;
 481     }
 482
 483   /* Figure out whether or not FN returns an aggregate.  */
 484   aggregate_return_p = IS_AGGR_TYPE (TREE_TYPE (result));
 485
 486   /* If FN returns an aggregate then the caller will always create the
 487      temporary (using a TARGET_EXPR) and the call will be the
 488      initializing expression for the TARGET_EXPR.  If we were just to
 489      create a new VAR_DECL here, then the result of this function
 490      would be copied (bitwise) into the variable initialized by the
 491      TARGET_EXPR.  That's incorrect, so we must transform any
 492      references to the RESULT into references to the target.  */
 493   if (aggregate_return_p)
 494     {
 495       my_friendly_assert (id->target_exprs->elements_used != 0,
 496                           20000430);
 497       var = TREE_OPERAND (VARRAY_TOP_TREE (id->target_exprs), 0);
 498       my_friendly_assert
 499         (same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (var),
 500                                                     TREE_TYPE (result)),
 501          20000430);
 502     }
 503   /* Otherwise, make an appropriate copy.  */
 504   else
 505     var = copy_decl_for_inlining (result, fn, VARRAY_TREE (id->fns, 0));
 506
 507   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 508      way, when the RESULT_DECL is encountered, it will be
 509      automatically replaced by the VAR_DECL.  */
 510   splay_tree_insert (id->decl_map,
 511                      (splay_tree_key) result,
 512                      (splay_tree_value) var);
 513
 514   /* Build the USE_STMT.  */
 515   *use_stmt = build_stmt (EXPR_STMT, var);
 516
 517   /* Build the declaration statement if FN does not return an
 518      aggregate.  */
 519   if (!aggregate_return_p)
 520     return build_stmt (DECL_STMT, var);
 521   /* If FN does return an aggregate, there's no need to declare the
 522      return variable; we're using a variable in our caller's frame.  */
 523   else
 524     return NULL_TREE;
 525 }
 526
 527 /* Returns non-zero if FN is a function that can be inlined.  */
 528
 529 static int
 530 inlinable_function_p (fn, id)
 531      tree fn;
 532      inline_data *id;
 533 {
 534   int inlinable;
 535
 536   /* If we've already decided this function shouldn't be inlined,
 537      there's no need to check again.  */
 538   if (DECL_UNINLINABLE (fn))
 539     return 0;
 540
 541   /* Assume it is not inlinable.  */
 542   inlinable = 0;
 543
 544   /* If we're not inlining things, then nothing is inlinable.  */
 545   if (!flag_inline_trees)
 546     ;
 547   /* If the function was not declared `inline', then we don't inline
 548      it.  */
 549   else if (!DECL_INLINE (fn))
 550     ;
 551   /* We can't inline varargs functions.  */
 552   else if (varargs_function_p (fn))
 553     ;
 554   /* All is well.  We can inline this function.  Traditionally, GCC
 555      has refused to inline functions using alloca, or functions whose
 556      values are returned in a PARALLEL, and a few other such obscure
 557      conditions.  We are not equally constrained at the tree level.  */
 558   else
 559     inlinable = 1;
 560
 561   /* Squirrel away the result so that we don't have to check again.  */
 562   DECL_UNINLINABLE (fn) = !inlinable;
 563
 564   /* We can inline a template instantiation only if it's fully
 565      instantiated.  */
 566   if (inlinable
 567       && DECL_TEMPLATE_INFO (fn)
 568       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
 569     {
 570       fn = instantiate_decl (fn, /*defer_ok=*/0);
 571       inlinable = !TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn));
 572     }
 573
 574   /* If we don't have the function body available, we can't inline
 575      it.  */
 576   if (!DECL_SAVED_TREE (fn))
 577     inlinable = 0;
 578
 579   /* Don't do recursive inlining, either.  We don't record this in
 580      DECL_UNLINABLE; we may be able to inline this function later.  */
 581   if (inlinable)
 582     {
 583       size_t i;
 584
 585       for (i = 0; i < id->fns->elements_used; ++i)
 586         if (VARRAY_TREE (id->fns, i) == fn)
 587           inlinable = 0;
 588     }
 589
 590   /* Return the result.  */
 591   return inlinable;
 592 }
 593
 594 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 595
 596 static tree
 597 expand_call_inline (tp, walk_subtrees, data)
 598      tree *tp;
 599      int *walk_subtrees;
 600      void *data;
 601 {
 602   inline_data *id;
 603   tree t;
 604   tree expr;
 605   tree chain;
 606   tree fn;
 607   tree scope_stmt;
 608   tree use_stmt;
 609   tree arg_inits;
 610   tree *inlined_body;
 611   splay_tree st;
 612
 613   /* See what we've got.  */
 614   id = (inline_data *) data;
 615   t = *tp;
 616
 617   /* Recurse, but letting recursive invocations know that we are
 618      inside the body of a TARGET_EXPR.  */
 619   if (TREE_CODE (*tp) == TARGET_EXPR)
 620     {
 621       int i, len = first_rtl_op (TARGET_EXPR);
 622
 623       /* We're walking our own subtrees.  */
 624       *walk_subtrees = 0;
 625
 626       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 627       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 628
 629       /* Actually walk over them.  This loop is the body of
 630          walk_trees, omitting the case where the TARGET_EXPR
 631          itself is handled.  */
 632       for (i = 0; i < len; ++i)
 633         {
 634           if (i == 2)
 635             ++id->in_target_cleanup_p;
 636           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
 637                      NULL);
 638           if (i == 2)
 639             --id->in_target_cleanup_p;
 640         }
 641
 642       /* We're done with this TARGET_EXPR now.  */
 643       VARRAY_POP (id->target_exprs);
 644
 645       return NULL_TREE;
 646     }
 647
 648   /* From here on, we're only interested in CALL_EXPRs.  */
 649   if (TREE_CODE (t) != CALL_EXPR)
 650     return NULL_TREE;
 651
 652   /* First, see if we can figure out what function is being called.
 653      If we cannot, then there is no hope of inlining the function.  */
 654   fn = get_callee_fndecl (t);
 655   if (!fn)
 656     return NULL_TREE;
 657
 658   /* Don't try to inline functions that are not well-suited to
 659      inlining.  */
 660   if (!inlinable_function_p (fn, id))
 661     return NULL_TREE;
 662
 663   /* Set the current filename and line number to the function we are
 664      inlining so that when we create new _STMT nodes here they get
 665      line numbers corresponding to the function we are calling.  We
 666      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 667      because individual statements don't record the filename.  */
 668   push_srcloc (fn->decl.filename, fn->decl.linenum);
 669
 670   /* Build a statement-expression containing code to initialize the
 671      arguments, the actual inline expansion of the body, and a label
 672      for the return statements within the function to jump to.  The
 673      type of the statement expression is the return type of the
 674      function call.  */
 675   expr = build_min (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 676
 677   /* Local declarations will be replaced by their equivalents in this
 678      map.  */
 679   st = id->decl_map;
 680   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 681                                  NULL, NULL);
 682
 683   /* Initialize the parameters.  */
 684   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 685   /* Expand any inlined calls in the initializers.  Do this before we
 686      push FN on the stack of functions we are inlining; we want to
 687      inline calls to FN that appear in the initializers for the
 688      parameters.  */
 689   expand_calls_inline (&arg_inits, id);
 690   /* And add them to the tree.  */
 691   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits);
 692
 693   /* Record the function we are about to inline so that we can avoid
 694      recursing into it.  */
 695   VARRAY_PUSH_TREE (id->fns, fn);
 696
 697   /* Return statements in the function body will be replaced by jumps
 698      to the RET_LABEL.  */
 699   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 700   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 701
 702   /* Create a block to put the parameters in.  We have to do this
 703      after the parameters have been remapped because remapping
 704      parameters is different from remapping ordinary variables.  */
 705   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 706   SCOPE_BEGIN_P (scope_stmt) = 1;
 707   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 708   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 709   TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr);
 710   STMT_EXPR_STMT (expr) = scope_stmt;
 711
 712   /* Tell the debugging backends that this block represents the
 713      outermost scope of the inlined function.  */
 714   if (SCOPE_STMT_BLOCK (scope_stmt))
 715     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 716
 717   /* Declare the return variable for the function.  */
 718   STMT_EXPR_STMT (expr)
 719     = chainon (STMT_EXPR_STMT (expr),
 720                declare_return_variable (id, &use_stmt));
 721
 722   /* After we've initialized the parameters, we insert the body of the
 723      function itself.  */
 724   inlined_body = &STMT_EXPR_STMT (expr);
 725   while (*inlined_body)
 726     inlined_body = &TREE_CHAIN (*inlined_body);
 727   *inlined_body = copy_body (id);
 728
 729   /* Close the block for the parameters.  */
 730   scope_stmt = build_stmt (SCOPE_STMT, DECL_INITIAL (fn));
 731   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 732   my_friendly_assert (DECL_INITIAL (fn)
 733                       && TREE_CODE (DECL_INITIAL (fn)) == BLOCK,
 734                       19991203);
 735   remap_block (scope_stmt, NULL_TREE, id);
 736   STMT_EXPR_STMT (expr)
 737     = chainon (STMT_EXPR_STMT (expr), scope_stmt);
 738
 739   /* After the body of the function comes the RET_LABEL.  This must come
 740      before we evaluate the returned value below, because that evalulation
 741      may cause RTL to be generated.  */
 742   STMT_EXPR_STMT (expr)
 743     = chainon (STMT_EXPR_STMT (expr),
 744                build_stmt (LABEL_STMT, id->ret_label));
 745
 746   /* Finally, mention the returned value so that the value of the
 747      statement-expression is the returned value of the function.  */
 748   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 749
 750   /* Clean up.  */
 751   splay_tree_delete (id->decl_map);
 752   id->decl_map = st;
 753
 754   /* The new expression has side-effects if the old one did.  */
 755   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 756
 757   /* Replace the call by the inlined body.  Wrap it in an
 758      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 759      pointing to the right place.  */
 760   chain = TREE_CHAIN (*tp);
 761   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 762                         /*col=*/0);
 763   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 764   TREE_CHAIN (*tp) = chain;
 765   pop_srcloc ();
 766
 767   /* If the value of the new expression is ignored, that's OK.  We
 768      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 769      the equivalent inlined version either.  */
 770   TREE_USED (*tp) = 1;
 771
 772   /* Recurse into the body of the just inlined function.  */
 773   expand_calls_inline (inlined_body, id);
 774   VARRAY_POP (id->fns);
 775
 776   /* Don't walk into subtrees.  We've already handled them above.  */
 777   *walk_subtrees = 0;
 778
 779   /* Keep iterating.  */
 780   return NULL_TREE;
 781 }
 782
 783 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 784    expansions as appropriate.  */
 785
 786 static void
 787 expand_calls_inline (tp, id)
 788      tree *tp;
 789      inline_data *id;
 790 {
 791   /* Search through *TP, replacing all calls to inline functions by
 792      appropriate equivalents.  */
 793   walk_tree (tp, expand_call_inline, id, NULL);
 794 }
 795
 796 /* Optimize the body of FN.  */
 797
 798 void
 799 optimize_function (fn)
 800      tree fn;
 801 {
 802   /* While in this function, we may choose to go off and compile
 803      another function.  For example, we might instantiate a function
 804      in the hopes of inlining it.  Normally, that wouldn't trigger any
 805      actual RTL code-generation -- but it will if the template is
 806      actually needed.  (For example, if it's address is taken, or if
 807      some other function already refers to the template.)  If
 808      code-generation occurs, then garbage collection will occur, so we
 809      must protect ourselves, just as we do while building up the body
 810      of the function.  */
 811   ++function_depth;
 812
 813   /* Expand calls to inline functions.  */
 814   if (flag_inline_trees)
 815     {
 816       inline_data id;
 817       tree prev_fn;
 818       struct saved_scope *s;
 819
 820       /* Clear out ID.  */
 821       memset (&id, 0, sizeof (id));
 822
 823       /* Don't allow recursion into FN.  */
 824       VARRAY_TREE_INIT (id.fns, 32, "fns");
 825       VARRAY_PUSH_TREE (id.fns, fn);
 826       /* Or any functions that aren't finished yet.  */
 827       prev_fn = NULL_TREE;
 828       if (current_function_decl)
 829         {
 830           VARRAY_PUSH_TREE (id.fns, current_function_decl);
 831           prev_fn = current_function_decl;
 832         }
 833       for (s = scope_chain; s; s = s->prev)
 834         if (s->function_decl && s->function_decl != prev_fn)
 835           {
 836             VARRAY_PUSH_TREE (id.fns, s->function_decl);
 837             prev_fn = s->function_decl;
 838           }
 839
 840       /* Create the stack of TARGET_EXPRs.  */
 841       VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
 842
 843       /* Replace all calls to inline functions with the bodies of those
 844          functions.  */
 845       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
 846
 847       /* Clean up.  */
 848       VARRAY_FREE (id.fns);
 849       VARRAY_FREE (id.target_exprs);
 850     }
 851
 852   /* Undo the call to ggc_push_context above.  */
 853   --function_depth;
 854 }
 855
 856 /* Called from calls_setjmp_p via walk_tree.  */
 857
 858 static tree
 859 calls_setjmp_r (tp, walk_subtrees, data)
 860      tree *tp;
 861      int *walk_subtrees ATTRIBUTE_UNUSED;
 862      void *data ATTRIBUTE_UNUSED;
 863 {
 864   /* We're only interested in FUNCTION_DECLS.  */
 865   if (TREE_CODE (*tp) != FUNCTION_DECL)
 866     return NULL_TREE;
 867
 868   return setjmp_call_p (*tp) ? *tp : NULL_TREE;
 869 }
 870
 871 /* Returns non-zero if FN calls `setjmp' or some other function that
 872    can return more than once.  This function is conservative; it may
 873    occasionally return a non-zero value even when FN does not actually
 874    call `setjmp'.  */
 875
 876 int
 877 calls_setjmp_p (fn)
 878      tree fn;
 879 {
 880   return walk_tree_without_duplicates (&DECL_SAVED_TREE (fn),
 881                                        calls_setjmp_r,
 882                                        NULL) != NULL_TREE;
 883 }
 884
 885 /* FN is a function that has a complete body.  Clone the body as
 886    necessary.  Returns non-zero if there's no longer any need to
 887    process the main body.  */
 888
 889 int
 890 maybe_clone_body (fn)
 891      tree fn;
 892 {
 893   inline_data id;
 894   tree clone;
 895
 896   /* We don't clone constructors and destructors under the old ABI.  */
 897   if (!flag_new_abi)
 898     return 0;
 899
 900   /* We only clone constructors and destructors.  */
 901   if (!DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (fn)
 902       && !DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fn))
 903     return 0;
 904
 905   /* We know that any clones immediately follow FN in the TYPE_METHODS
 906      list.  */
 907   for (clone = TREE_CHAIN (fn);
 908        clone && DECL_CLONED_FUNCTION_P (clone);
 909        clone = TREE_CHAIN (clone))
 910     {
 911       tree parm;
 912       tree clone_parm;
 913       int parmno;
 914
 915       /* Update CLONE's source position information to match FN's.  */
 916       DECL_SOURCE_FILE (clone) = DECL_SOURCE_FILE (fn);
 917       DECL_SOURCE_LINE (clone) = DECL_SOURCE_LINE (fn);
 918       DECL_INLINE (clone) = DECL_INLINE (fn);
 919       DECL_THIS_INLINE (clone) = DECL_THIS_INLINE (fn);
 920       DECL_COMDAT (clone) = DECL_COMDAT (fn);
 921       DECL_WEAK (clone) = DECL_WEAK (fn);
 922       DECL_ONE_ONLY (clone) = DECL_ONE_ONLY (fn);
 923       DECL_SECTION_NAME (clone) = DECL_SECTION_NAME (fn);
 924       DECL_USE_TEMPLATE (clone) = DECL_USE_TEMPLATE (fn);
 925       DECL_EXTERNAL (clone) = DECL_EXTERNAL (fn);
 926       DECL_INTERFACE_KNOWN (clone) = DECL_INTERFACE_KNOWN (fn);
 927       DECL_NOT_REALLY_EXTERN (clone) = DECL_NOT_REALLY_EXTERN (fn);
 928
 929       /* Start processing the function.  */
 930       push_to_top_level ();
 931       start_function (NULL_TREE, clone, NULL_TREE, SF_PRE_PARSED);
 932
 933       /* Just clone the body, as if we were making an inline call.
 934          But, remap the parameters in the callee to the parameters of
 935          caller.  If there's an in-charge parameter, map it to an
 936          appropriate constant.  */
 937       memset (&id, 0, sizeof (id));
 938       VARRAY_TREE_INIT (id.fns, 2, "fns");
 939       VARRAY_PUSH_TREE (id.fns, clone);
 940       VARRAY_PUSH_TREE (id.fns, fn);
 941
 942       /* Remap the parameters.  */
 943       id.decl_map = splay_tree_new (splay_tree_compare_pointers,
 944                                     NULL, NULL);
 945       for (parmno = 0,
 946              parm = DECL_ARGUMENTS (fn),
 947              clone_parm = DECL_ARGUMENTS (clone);
 948            parm;
 949            ++parmno,
 950              parm = TREE_CHAIN (parm))
 951         {
 952           /* Map the in-charge parameter to an appropriate constant.  */
 953           if (DECL_HAS_IN_CHARGE_PARM_P (fn) && parmno == 1)
 954             {
 955               tree in_charge;
 956               in_charge = in_charge_arg_for_name (DECL_NAME (clone));
 957               splay_tree_insert (id.decl_map,
 958                                  (splay_tree_key) parm,
 959                                  (splay_tree_value) in_charge);
 960
 961               /* For a subobject constructor or destructor, the next
 962                  argument is the VTT parameter.  Remap the VTT_PARM
 963                  from the CLONE to this parameter.  */
 964               if (DECL_NEEDS_VTT_PARM_P (clone))
 965                 {
 966                   splay_tree_insert (id.decl_map,
 967                                      (splay_tree_key) DECL_VTT_PARM (fn),
 968                                      (splay_tree_value) clone_parm);
 969                   splay_tree_insert (id.decl_map,
 970                                      (splay_tree_key) DECL_USE_VTT_PARM (fn),
 971                                      (splay_tree_value) boolean_true_node);
 972                   clone_parm = TREE_CHAIN (clone_parm);
 973                 }
 974               /* Otherwise, map the VTT parameter to `NULL'.  */
 975               else if (DECL_VTT_PARM (fn))
 976                 {
 977                   splay_tree_insert (id.decl_map,
 978                                      (splay_tree_key) DECL_VTT_PARM (fn),
 979                                      (splay_tree_value) null_pointer_node);
 980                   splay_tree_insert (id.decl_map,
 981                                      (splay_tree_key) DECL_USE_VTT_PARM (fn),
 982                                      (splay_tree_value) boolean_false_node);
 983                 }
 984             }
 985           /* Map other parameters to their equivalents in the cloned
 986              function.  */
 987           else
 988             {
 989               splay_tree_insert (id.decl_map,
 990                                  (splay_tree_key) parm,
 991                                  (splay_tree_value) clone_parm);
 992               clone_parm = TREE_CHAIN (clone_parm);
 993             }
 994         }
 995
 996       /* Actually copy the body.  */
 997       TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
 998
 999       /* Clean up.  */
1000       splay_tree_delete (id.decl_map);
1001       VARRAY_FREE (id.fns);
1002
1003       /* Now, expand this function into RTL, if appropriate.  */
1004       function_name_declared_p = 1;
1005       expand_body (finish_function (0));
1006       pop_from_top_level ();
1007     }
1008
1009   /* We don't need to process the original function any further.  */
1010   return 1;
1011 }