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       /* Initialize this VAR_DECL from the equivalent argument.  If
 433          the argument is an object, created via a constructor or copy,
 434          this will not result in an extra copy: the TARGET_EXPR
 435          representing the argument will be bound to VAR, and the
 436          object will be constructed in VAR.  */
 437       init_stmt = build_min_nt (EXPR_STMT,
 438                                 build (INIT_EXPR, TREE_TYPE (p),
 439                                        var, value));
 440       /* Declare this new variable.  Note that we do this *after* the
 441          initialization because we are going to reverse all the
 442          initialization statements below.  */
 443       TREE_CHAIN (init_stmt) = build_min_nt (DECL_STMT, var);
 444       /* Add this initialization to the list.  */
 445       TREE_CHAIN (TREE_CHAIN (init_stmt)) = init_stmts;
 446       init_stmts = init_stmt;
 447     }
 448
 449   /* The initialization statements have been built up in reverse
 450      order.  Straighten them out now.  */
 451   return nreverse (init_stmts);
 452 }
 453
 454 /* Declare a return variable to replace the RESULT_DECL for the
 455    function we are calling.  An appropriate DECL_STMT is returned.
 456    The USE_STMT is filled in to contain a use of the declaration to
 457    indicate the return value of the function.  */
 458
 459 static tree
 460 declare_return_variable (id, use_stmt)
 461      struct inline_data *id;
 462      tree *use_stmt;
 463 {
 464   tree fn = VARRAY_TOP_TREE (id->fns);
 465   tree result = DECL_RESULT (fn);
 466   tree var;
 467   int aggregate_return_p;
 468
 469   /* We don't need to do anything for functions that don't return
 470      anything.  */
 471   if (!result || same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (result)),
 472                               void_type_node))
 473     {
 474       *use_stmt = NULL_TREE;
 475       return NULL_TREE;
 476     }
 477
 478   /* Figure out whether or not FN returns an aggregate.  */
 479   aggregate_return_p = IS_AGGR_TYPE (TREE_TYPE (result));
 480
 481   /* If FN returns an aggregate then the caller will always create the
 482      temporary (using a TARGET_EXPR) and the call will be the
 483      initializing expression for the TARGET_EXPR.  If we were just to
 484      create a new VAR_DECL here, then the result of this function
 485      would be copied (bitwise) into the variable initialized by the
 486      TARGET_EXPR.  That's incorrect, so we must transform any
 487      references to the RESULT into references to the target.  */
 488   if (aggregate_return_p)
 489     {
 490       my_friendly_assert (id->target_exprs->elements_used != 0,
 491                           20000430);
 492       var = TREE_OPERAND (VARRAY_TOP_TREE (id->target_exprs), 0);
 493       my_friendly_assert (same_type_p (TREE_TYPE (var),
 494                                        TREE_TYPE (result)),
 495                           20000430);
 496     }
 497   /* Otherwise, make an appropriate copy.  */
 498   else
 499     var = copy_decl_for_inlining (result, fn, VARRAY_TREE (id->fns, 0));
 500
 501   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 502      way, when the RESULT_DECL is encountered, it will be
 503      automatically replaced by the VAR_DECL.  */
 504   splay_tree_insert (id->decl_map,
 505                      (splay_tree_key) result,
 506                      (splay_tree_value) var);
 507
 508   /* Build the USE_STMT.  */
 509   *use_stmt = build_min_nt (EXPR_STMT, var);
 510
 511   /* Build the declaration statement if FN does not return an
 512      aggregate.  */
 513   if (!aggregate_return_p)
 514     return build_min_nt (DECL_STMT, var);
 515   /* If FN does return an aggregate, there's no need to declare the
 516      return variable; we're using a variable in our caller's frame.  */
 517   else
 518     return NULL_TREE;
 519 }
 520
 521 /* Returns non-zero if FN is a function that can be inlined.  */
 522
 523 static int
 524 inlinable_function_p (fn, id)
 525      tree fn;
 526      inline_data *id;
 527 {
 528   int inlinable;
 529
 530   /* If we've already decided this function shouldn't be inlined,
 531      there's no need to check again.  */
 532   if (DECL_UNINLINABLE (fn))
 533     return 0;
 534
 535   /* Assume it is not inlinable.  */
 536   inlinable = 0;
 537
 538   /* If we're not inlining things, then nothing is inlinable.  */
 539   if (!flag_inline_trees)
 540     ;
 541   /* If the function was not declared `inline', then we don't inline
 542      it.  */
 543   else if (!DECL_INLINE (fn))
 544     ;
 545   /* We can't inline varargs functions.  */
 546   else if (varargs_function_p (fn))
 547     ;
 548   /* All is well.  We can inline this function.  Traditionally, GCC
 549      has refused to inline functions using alloca, or functions whose
 550      values are returned in a PARALLEL, and a few other such obscure
 551      conditions.  We are not equally constrained at the tree level.  */
 552   else
 553     inlinable = 1;
 554
 555   /* Squirrel away the result so that we don't have to check again.  */
 556   DECL_UNINLINABLE (fn) = !inlinable;
 557
 558   /* We can inline a template instantiation only if it's fully
 559      instantiated.  */
 560   if (inlinable
 561       && DECL_TEMPLATE_INFO (fn)
 562       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
 563     {
 564       fn = instantiate_decl (fn, /*defer_ok=*/0);
 565       inlinable = !TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn));
 566     }
 567
 568   /* If we don't have the function body available, we can't inline
 569      it.  */
 570   if (!DECL_SAVED_TREE (fn))
 571     inlinable = 0;
 572
 573   /* Don't do recursive inlining, either.  We don't record this in
 574      DECL_UNLINABLE; we may be able to inline this function later.  */
 575   if (inlinable)
 576     {
 577       size_t i;
 578
 579       for (i = 0; i < id->fns->elements_used; ++i)
 580         if (VARRAY_TREE (id->fns, i) == fn)
 581           inlinable = 0;
 582     }
 583
 584   /* Return the result.  */
 585   return inlinable;
 586 }
 587
 588 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
 589
 590 static tree
 591 expand_call_inline (tp, walk_subtrees, data)
 592      tree *tp;
 593      int *walk_subtrees;
 594      void *data;
 595 {
 596   inline_data *id;
 597   tree t;
 598   tree expr;
 599   tree chain;
 600   tree fn;
 601   tree scope_stmt;
 602   tree use_stmt;
 603   tree arg_inits;
 604   splay_tree st;
 605
 606   /* See what we've got.  */
 607   id = (inline_data *) data;
 608   t = *tp;
 609
 610   /* Recurse, but letting recursive invocations know that we are
 611      inside the body of a TARGET_EXPR.  */
 612   if (TREE_CODE (*tp) == TARGET_EXPR)
 613     {
 614       int i, len = first_rtl_op (TARGET_EXPR);
 615
 616       /* We're walking our own subtrees.  */
 617       *walk_subtrees = 0;
 618
 619       /* Push *TP on the stack of pending TARGET_EXPRs.  */
 620       VARRAY_PUSH_TREE (id->target_exprs, *tp);
 621
 622       /* Actually walk over them.  This loop is the body of
 623          walk_trees, omitting the case where the TARGET_EXPR
 624          itself is handled.  */
 625       for (i = 0; i < len; ++i)
 626         {
 627           if (i == 2)
 628             ++id->in_target_cleanup_p;
 629           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data);
 630           if (i == 2)
 631             --id->in_target_cleanup_p;
 632         }
 633
 634       /* We're done with this TARGET_EXPR now.  */
 635       VARRAY_POP (id->target_exprs);
 636
 637       return NULL_TREE;
 638     }
 639
 640   /* From here on, we're only interested in CALL_EXPRs.  */
 641   if (TREE_CODE (t) != CALL_EXPR)
 642     return NULL_TREE;
 643
 644   /* First, see if we can figure out what function is being called.
 645      If we cannot, then there is no hope of inlining the function.  */
 646   fn = get_callee_fndecl (t);
 647   if (!fn)
 648     return NULL_TREE;
 649
 650   /* Don't try to inline functions that are not well-suited to
 651      inlining.  */
 652   if (!inlinable_function_p (fn, id))
 653     return NULL_TREE;
 654
 655   /* Set the current filename and line number to the function we are
 656      inlining so that when we create new _STMT nodes here they get
 657      line numbers corresponding to the function we are calling.  We
 658      wrap the whole inlined body in an EXPR_WITH_FILE_AND_LINE as well
 659      because individual statements don't record the filename.  */
 660   push_srcloc (fn->decl.filename, fn->decl.linenum);
 661
 662   /* Build a statement-expression containing code to initialize the
 663      arguments, the actual inline expansion of the body, and a label
 664      for the return statements within the function to jump to.  The
 665      type of the statement expression is the return type of the
 666      function call.  */
 667   expr = build_min (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 668
 669   /* Local declarations will be replaced by their equivalents in this
 670      map.  */
 671   st = id->decl_map;
 672   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 673                                  NULL, NULL);
 674
 675   /* Initialize the parameters.  */
 676   arg_inits = initialize_inlined_parameters (id, TREE_OPERAND (t, 1), fn);
 677   /* Expand any inlined calls in the initializers.  Do this before we
 678      push FN on the stack of functions we are inlining; we want to
 679      inline calls to FN that appear in the initializers for the
 680      parameters.  */
 681   expand_calls_inline (&arg_inits, id);
 682   /* And add them to the tree.  */
 683   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), arg_inits);
 684
 685   /* Record the function we are about to inline so that we can avoid
 686      recursing into it.  */
 687   VARRAY_PUSH_TREE (id->fns, fn);
 688
 689   /* Return statements in the function body will be replaced by jumps
 690      to the RET_LABEL.  */
 691   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 692   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 693
 694   /* Create a block to put the parameters in.  We have to do this
 695      after the parameters have been remapped because remapping
 696      parameters is different from remapping ordinary variables.  */
 697   scope_stmt = build_min_nt (SCOPE_STMT, DECL_INITIAL (fn));
 698   SCOPE_BEGIN_P (scope_stmt) = 1;
 699   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 700   remap_block (scope_stmt, DECL_ARGUMENTS (fn), id);
 701   TREE_CHAIN (scope_stmt) = STMT_EXPR_STMT (expr);
 702   STMT_EXPR_STMT (expr) = scope_stmt;
 703
 704   /* Tell the debugging backends that this block represents the
 705      outermost scope of the inlined function.  */
 706   if (SCOPE_STMT_BLOCK (scope_stmt))
 707     BLOCK_ABSTRACT_ORIGIN (SCOPE_STMT_BLOCK (scope_stmt)) = DECL_ORIGIN (fn);
 708
 709   /* Declare the return variable for the function.  */
 710   STMT_EXPR_STMT (expr)
 711     = chainon (STMT_EXPR_STMT (expr),
 712                declare_return_variable (id, &use_stmt));
 713
 714   /* After we've initialized the parameters, we insert the body of the
 715      function itself.  */
 716   STMT_EXPR_STMT (expr)
 717     = chainon (STMT_EXPR_STMT (expr), copy_body (id));
 718
 719   /* Close the block for the parameters.  */
 720   scope_stmt = build_min_nt (SCOPE_STMT, DECL_INITIAL (fn));
 721   SCOPE_NO_CLEANUPS_P (scope_stmt) = 1;
 722   my_friendly_assert (DECL_INITIAL (fn)
 723                       && TREE_CODE (DECL_INITIAL (fn)) == BLOCK,
 724                       19991203);
 725   remap_block (scope_stmt, NULL_TREE, id);
 726   STMT_EXPR_STMT (expr)
 727     = chainon (STMT_EXPR_STMT (expr), scope_stmt);
 728
 729   /* After the body of the function comes the RET_LABEL.  This must come
 730      before we evaluate the returned value below, because that evalulation
 731      may cause RTL to be generated.  */
 732   STMT_EXPR_STMT (expr)
 733     = chainon (STMT_EXPR_STMT (expr),
 734                build_min_nt (LABEL_STMT, id->ret_label));
 735
 736   /* Finally, mention the returned value so that the value of the
 737      statement-expression is the returned value of the function.  */
 738   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 739
 740   /* Clean up.  */
 741   splay_tree_delete (id->decl_map);
 742   id->decl_map = st;
 743
 744   /* The new expression has side-effects if the old one did.  */
 745   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 746
 747   /* Replace the call by the inlined body.  Wrap it in an
 748      EXPR_WITH_FILE_LOCATION so that we'll get debugging line notes
 749      pointing to the right place.  */
 750   chain = TREE_CHAIN (*tp);
 751   *tp = build_expr_wfl (expr, DECL_SOURCE_FILE (fn), DECL_SOURCE_LINE (fn),
 752                         /*col=*/0);
 753   EXPR_WFL_EMIT_LINE_NOTE (*tp) = 1;
 754   TREE_CHAIN (*tp) = chain;
 755   pop_srcloc ();
 756
 757   /* If the value of the new expression is ignored, that's OK.  We
 758      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 759      the equivalent inlined version either.  */
 760   TREE_USED (*tp) = 1;
 761
 762   /* Recurse into the body of the just inlined function.  */
 763   expand_calls_inline (tp, id);
 764   VARRAY_POP (id->fns);
 765
 766   /* Don't walk into subtrees.  We've already handled them above.  */
 767   *walk_subtrees = 0;
 768
 769   /* Keep iterating.  */
 770   return NULL_TREE;
 771 }
 772
 773 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 774    expansions as appropriate.  */
 775
 776 static void
 777 expand_calls_inline (tp, id)
 778      tree *tp;
 779      inline_data *id;
 780 {
 781   /* Search through *TP, replacing all calls to inline functions by
 782      appropriate equivalents.  */
 783   walk_tree (tp, expand_call_inline, id);
 784 }
 785
 786 /* Optimize the body of FN.  */
 787
 788 void
 789 optimize_function (fn)
 790      tree fn;
 791 {
 792   /* Expand calls to inline functions.  */
 793   if (flag_inline_trees)
 794     {
 795       inline_data id;
 796       tree prev_fn;
 797       struct saved_scope *s;
 798
 799       /* Clear out ID.  */
 800       memset (&id, 0, sizeof (id));
 801
 802       /* Don't allow recursion into FN.  */
 803       VARRAY_TREE_INIT (id.fns, 32, "fns");
 804       VARRAY_PUSH_TREE (id.fns, fn);
 805       /* Or any functions that aren't finished yet.  */
 806       prev_fn = NULL_TREE;
 807       if (current_function_decl)
 808         {
 809           VARRAY_PUSH_TREE (id.fns, current_function_decl);
 810           prev_fn = current_function_decl;
 811         }
 812       for (s = scope_chain; s; s = s->prev)
 813         if (s->function_decl && s->function_decl != prev_fn)
 814           {
 815             VARRAY_PUSH_TREE (id.fns, s->function_decl);
 816             prev_fn = s->function_decl;
 817           }
 818
 819       /* Create the stack of TARGET_EXPRs.  */
 820       VARRAY_TREE_INIT (id.target_exprs, 32, "target_exprs");
 821
 822       /* Replace all calls to inline functions with the bodies of those
 823          functions.  */
 824       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
 825
 826       /* Clean up.  */
 827       VARRAY_FREE (id.fns);
 828       VARRAY_FREE (id.target_exprs);
 829     }
 830 }
 831
 832 /* Called from calls_setjmp_p via walk_tree.  */
 833
 834 static tree
 835 calls_setjmp_r (tp, walk_subtrees, data)
 836      tree *tp;
 837      int *walk_subtrees ATTRIBUTE_UNUSED;
 838      void *data ATTRIBUTE_UNUSED;
 839 {
 840   /* We're only interested in FUNCTION_DECLS.  */
 841   if (TREE_CODE (*tp) != FUNCTION_DECL)
 842     return NULL_TREE;
 843
 844   return setjmp_call_p (*tp) ? *tp : NULL_TREE;
 845 }
 846
 847 /* Returns non-zero if FN calls `setjmp' or some other function that
 848    can return more than once.  This function is conservative; it may
 849    occasionally return a non-zero value even when FN does not actually
 850    call `setjmp'.  */
 851
 852 int
 853 calls_setjmp_p (fn)
 854      tree fn;
 855 {
 856   return (walk_tree (&DECL_SAVED_TREE (fn), calls_setjmp_r, NULL)
 857           != NULL_TREE);
 858 }
 859
 860 /* FN is a function that has a complete body.  Clone the body as
 861    necessary.  Returns non-zero if there's no longer any need to
 862    process the main body.  */
 863
 864 int
 865 maybe_clone_body (fn)
 866      tree fn;
 867 {
 868   inline_data id;
 869   tree clone;
 870
 871   /* We don't clone constructors and destructors under the old ABI.  */
 872   if (!flag_new_abi)
 873     return 0;
 874
 875   /* We only clone constructors and destructors.  */
 876   if (!DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (fn)
 877       && !DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fn))
 878     return 0;
 879
 880   /* We know that any clones immediately follow FN in the TYPE_METHODS
 881      list.  */
 882   for (clone = TREE_CHAIN (fn);
 883        clone && DECL_CLONED_FUNCTION_P (clone);
 884        clone = TREE_CHAIN (clone))
 885     {
 886       tree parm;
 887       tree clone_parm;
 888       int parmno;
 889
 890       /* Update CLONE's source position information to match FN's.  */
 891       DECL_SOURCE_FILE (clone) = DECL_SOURCE_FILE (fn);
 892       DECL_SOURCE_LINE (clone) = DECL_SOURCE_LINE (fn);
 893
 894       /* Start processing the function.  */
 895       push_to_top_level ();
 896       start_function (NULL_TREE, clone, NULL_TREE, SF_PRE_PARSED);
 897       store_parm_decls ();
 898
 899       /* Just clone the body, as if we were making an inline call.
 900          But, remap the parameters in the callee to the parameters of
 901          caller.  If there's an in-charge parameter, map it to an
 902          appropriate constant.  */
 903       memset (&id, 0, sizeof (id));
 904       VARRAY_TREE_INIT (id.fns, 2, "fns");
 905       VARRAY_PUSH_TREE (id.fns, clone);
 906       VARRAY_PUSH_TREE (id.fns, fn);
 907
 908       /* Remap the parameters.  */
 909       id.decl_map = splay_tree_new (splay_tree_compare_pointers,
 910                                     NULL, NULL);
 911       for (parmno = 0,
 912              parm = DECL_ARGUMENTS (fn),
 913              clone_parm = DECL_ARGUMENTS (clone);
 914            parm;
 915            ++parmno,
 916              parm = TREE_CHAIN (parm))
 917         {
 918           /* Map the in-charge parameter to an appropriate constant.  */
 919           if (DECL_HAS_IN_CHARGE_PARM_P (fn) && parmno == 1)
 920             {
 921               tree in_charge;
 922               in_charge = in_charge_arg_for_name (DECL_NAME (clone));
 923               splay_tree_insert (id.decl_map,
 924                                  (splay_tree_key) parm,
 925                                  (splay_tree_key) in_charge);
 926             }
 927           /* Map other parameters to their equivalents in the cloned
 928              function.  */
 929           else
 930             {
 931               splay_tree_insert (id.decl_map,
 932                                  (splay_tree_key) parm,
 933                                  (splay_tree_value) clone_parm);
 934               clone_parm = TREE_CHAIN (clone_parm);
 935             }
 936         }
 937
 938       /* Actually copy the body.  */
 939       TREE_CHAIN (DECL_SAVED_TREE (clone)) = copy_body (&id);
 940
 941       /* Clean up.  */
 942       splay_tree_delete (id.decl_map);
 943       VARRAY_FREE (id.fns);
 944
 945       /* Now, expand this function into RTL, if appropriate.  */
 946       current_function_name_declared = 1;
 947       expand_body (finish_function (0));
 948       pop_from_top_level ();
 949     }
 950
 951   /* We don't need to process the original function any further.  */
 952   return 1;
 953 }