gcc/cp/optimize.c

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