gcc/cp/optimize.c

   1 /* Perform optimizations on tree structure.
   2
   3    Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   4    Written by Mark Michell (mark@codesourcery.com).
   5
   6    This file is part of GNU CC.
   7
   8    GNU CC is free software; you can redistribute it and/or modify it
   9    under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    GNU CC is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GNU CC; see the file COPYING.  If not, write to the Free
  20    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21    02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "tree.h"
  26 #include "cp-tree.h"
  27 #include "rtl.h"
  28 #include "insn-config.h"
  29 #include "integrate.h"
  30 #include "varray.h"
  31
  32 /* To Do:
  33
  34    o Provide debugging information for inlined function bodies.
  35
  36    o In order to make inlining-on-trees work, we pessimized
  37      function-local static constants.  In particular, they are now
  38      always output, even when not addressed.  Fix this by treating
  39      function-local static constants just like global static
  40      constants; the back-end already knows not to output them if they
  41      are not needed.
  42
  43    o Provide heuristics to clamp inlining of recursive template
  44      calls?  */
  45
  46 /* Data required for function inlining.  */
  47
  48 typedef struct inline_data
  49 {
  50   /* A stack of the functions we are inlining.  For example, if we are
  51      compiling `f', which calls `g', which calls `h', and we are
  52      inlining the body of `h', the stack will contain, `h', followed
  53      by `g', followed by `f'.  */
  54   varray_type fns;
  55   /* The top of the FNS stack.  */
  56   size_t fns_top;
  57   /* The label to jump to when a return statement is encountered.  */
  58   tree ret_label;
  59   /* The map from local declarations in the inlined function to
  60      equivalents in the function into which it is being inlined.  */
  61   splay_tree decl_map;
  62 } inline_data;
  63
  64 /* Prototypes.  */
  65
  66 static tree initialize_inlined_parameters PROTO((inline_data *, tree));
  67 static tree declare_return_variable PROTO((inline_data *, tree *));
  68 static tree copy_body_r PROTO((tree *, int *, void *));
  69 static tree copy_body PROTO((inline_data *));
  70 static tree expand_call_inline PROTO((tree *, int *, void *));
  71 static void expand_calls_inline PROTO((tree *, inline_data *));
  72 static int inlinable_function_p PROTO((tree, inline_data *));
  73
  74 /* Called from copy_body via walk_tree.  DATA is really an
  75    `inline_data *'.  */
  76
  77 static tree
  78 copy_body_r (tp, walk_subtrees, data)
  79      tree *tp;
  80      int *walk_subtrees;
  81      void *data;
  82 {
  83   inline_data* id;
  84   tree fn;
  85
  86   /* Set up.  */
  87   id = (inline_data *) data;
  88   fn = VARRAY_TREE (id->fns, id->fns_top - 1);
  89
  90   /* All automatic variables should have a DECL_CONTEXT indicating
  91      what function they come from.  */
  92   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
  93       && DECL_NAMESPACE_SCOPE_P (*tp))
  94     my_friendly_assert (DECL_EXTERNAL (*tp) || TREE_STATIC (*tp),
  95                         19991113);
  96
  97   /* If this is a RETURN_STMT, change it into an EXPR_STMT and a
  98      GOTO_STMT with the RET_LABEL as its target.  */
  99   if (TREE_CODE (*tp) == RETURN_STMT)
 100     {
 101       tree return_stmt = *tp;
 102       tree goto_stmt;
 103
 104       /* Build the GOTO_STMT.  */
 105       goto_stmt = build_min_nt (GOTO_STMT, id->ret_label);
 106       TREE_CHAIN (goto_stmt) = TREE_CHAIN (return_stmt);
 107
 108       /* If we're returning something, just turn that into an
 109          assignment into the equivalent of the original
 110          RESULT_DECL.  */
 111       if (RETURN_EXPR (return_stmt))
 112         {
 113           *tp = build_min_nt (EXPR_STMT,
 114                               RETURN_EXPR (return_stmt));
 115           /* And then jump to the end of the function.  */
 116           TREE_CHAIN (*tp) = goto_stmt;
 117         }
 118       /* If we're not returning anything just do the jump.  */
 119       else
 120         *tp = goto_stmt;
 121     }
 122   /* Local variables and labels need to be replaced by equivalent
 123      variables.  We don't want to copy static variables; there's only
 124      one of those, no matter how many times we inline the containing
 125      function.  */
 126   else if (nonstatic_local_decl_p (*tp) && DECL_CONTEXT (*tp) == fn)
 127     {
 128       splay_tree_node n;
 129
 130       /* Look up the declaration.  */
 131       n = splay_tree_lookup (id->decl_map, (splay_tree_key) *tp);
 132
 133       /* If we didn't already have an equivalent for this declaration,
 134          create one now.  */
 135       if (!n)
 136         {
 137           tree t;
 138
 139           /* Make a copy of the variable or label.  */
 140           t = copy_decl_for_inlining (*tp, fn,
 141                                       VARRAY_TREE (id->fns, 0));
 142           /* Remember it, so that if we encounter this local entity
 143              again we can reuse this copy.  */
 144           n = splay_tree_insert (id->decl_map,
 145                                  (splay_tree_key) *tp,
 146                                  (splay_tree_value) t);
 147         }
 148
 149       /* Replace this variable with the copy.  */
 150       *tp = (tree) n->value;
 151     }
 152   else if (TREE_CODE (*tp) == SAVE_EXPR)
 153     remap_save_expr (tp, id->decl_map, VARRAY_TREE (id->fns, 0));
 154   else if (TREE_CODE (*tp) == UNSAVE_EXPR)
 155     my_friendly_abort (19991113);
 156   /* Otherwise, just copy the node.  Note that copy_tree_r already
 157      knows not to copy VAR_DECLs, etc., so this is safe.  */
 158   else
 159     {
 160       copy_tree_r (tp, walk_subtrees, NULL);
 161
 162       /* The copied TARGET_EXPR has never been expanded, even if the
 163          original node was expanded already.  */
 164       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 165         TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 166       /* Similarly, if we're copying a CALL_EXPR, the RTL for the
 167          result is no longer valid.  */
 168       else if (TREE_CODE (*tp) == CALL_EXPR)
 169         CALL_EXPR_RTL (*tp) = NULL_RTX;
 170     }
 171
 172   /* Keep iterating.  */
 173   return NULL_TREE;
 174 }
 175
 176 /* Make a copy of the body of FN so that it can be inserted inline in
 177    another function.  */
 178
 179 static tree
 180 copy_body (id)
 181      inline_data *id;
 182 {
 183   tree body;
 184
 185   body = DECL_SAVED_TREE (VARRAY_TREE (id->fns, id->fns_top - 1));
 186   walk_tree (&body, copy_body_r, id);
 187
 188   return body;
 189 }
 190
 191 /* Generate code to initialize the parameters of the function at the
 192    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 193
 194 static tree
 195 initialize_inlined_parameters (id, args)
 196      inline_data *id;
 197      tree args;
 198 {
 199   tree fn;
 200   tree init_stmts;
 201   tree parms;
 202   tree a;
 203   tree p;
 204
 205   /* Figure out what the parameters are.  */
 206   fn = VARRAY_TREE (id->fns, id->fns_top - 1);
 207   parms = DECL_ARGUMENTS (fn);
 208
 209   /* Start with no initializations whatsoever.  */
 210   init_stmts = NULL_TREE;
 211
 212   /* Loop through the parameter declarations, replacing each with an
 213      equivalent VAR_DECL, appropriately initialized.  */
 214   for (p = parms, a = args; p; a = TREE_CHAIN (a), p = TREE_CHAIN (p))
 215     {
 216       tree init_stmt;
 217       tree var;
 218
 219       /* Make an equivalent VAR_DECL.  */
 220       var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 221       /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 222          that way, when the PARM_DECL is encountered, it will be
 223          automatically replaced by the VAR_DECL.  */
 224       splay_tree_insert (id->decl_map,
 225                          (splay_tree_key) p,
 226                          (splay_tree_value) var);
 227       /* Initialize this VAR_DECL from the equivalent argument.  If
 228          the argument is an object, created via a constructor or copy,
 229          this will not result in an extra copy: the TARGET_EXPR
 230          representing the argument will be bound to VAR, and the
 231          object will be constructed in VAR.  */
 232       init_stmt = build_min_nt (EXPR_STMT,
 233                                 build (INIT_EXPR, TREE_TYPE (p),
 234                                        var, TREE_VALUE (a)));
 235       /* Declare this new variable.  Note that we do this *after* the
 236          initialization because we are going to reverse all the
 237          initialization statements below.  */
 238       TREE_CHAIN (init_stmt) = build_min_nt (DECL_STMT, var);
 239       /* Add this initialization to the list.  */
 240       TREE_CHAIN (TREE_CHAIN (init_stmt)) = init_stmts;
 241       init_stmts = init_stmt;
 242     }
 243
 244   /* The initialization statements have been built up in reverse
 245      order.  Straighten them out now.  */
 246   return nreverse (init_stmts);
 247 }
 248
 249 /* Declare a return variable to replace the RESULT_DECL for the
 250    function we are calling.  An appropriate DECL_STMT is returned.
 251    The USE_STMT is filled in to contain a use of the declaration to
 252    indicate the return value of the function.  */
 253
 254 static tree
 255 declare_return_variable (id, use_stmt)
 256      struct inline_data *id;
 257      tree *use_stmt;
 258 {
 259   tree fn = VARRAY_TREE (id->fns, id->fns_top - 1);
 260   tree result = DECL_RESULT (fn);
 261   tree var;
 262
 263   /* We don't need to do anything for functions that don't return
 264      anything.  */
 265   if (!result || same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (result)),
 266                               void_type_node))
 267     {
 268       *use_stmt = NULL_TREE;
 269       return NULL_TREE;
 270     }
 271
 272   /* Make an appropriate copy.  */
 273   var = copy_decl_for_inlining (result, fn, VARRAY_TREE (id->fns, 0));
 274   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 275      way, when the RESULT_DECL is encountered, it will be
 276      automatically replaced by the VAR_DECL.  */
 277   splay_tree_insert (id->decl_map,
 278                      (splay_tree_key) result,
 279                      (splay_tree_value) var);
 280
 281   /* Build the USE_STMT.  */
 282   *use_stmt = build_min_nt (EXPR_STMT, var);
 283
 284   /* Build the declaration statement.  */
 285   return build_min_nt (DECL_STMT, var);
 286 }
 287
 288 /* Returns non-zero if FN is a function that can be inlined.  */
 289
 290 static int
 291 inlinable_function_p (fn, id)
 292      tree fn;
 293      inline_data *id;
 294 {
 295   int inlinable;
 296
 297   /* If we've already decided this function shouldn't be inlined,
 298      there's no need to check again.  */
 299   if (DECL_UNINLINABLE (fn))
 300     return 0;
 301
 302   /* Assume it is not inlinable.  */
 303   inlinable = 0;
 304
 305   /* If the function was not declared `inline', then we don't inline
 306      it.  */
 307   if (!DECL_INLINE (fn))
 308     ;
 309   /* If we don't have the function body available, we can't inline
 310      it.  */
 311   else if (!DECL_SAVED_TREE (fn))
 312     ;
 313   /* We can't inline varargs functions.  */
 314   else if (varargs_function_p (fn))
 315     ;
 316   /* All is well.  We can inline this function.  Traditionally, GCC
 317      has refused to inline functions using setjmp or alloca, or
 318      functions whose values are returned in a PARALLEL, and a few
 319      other such obscure conditions.  We are not equally constrained at
 320      the tree level.  */
 321   else
 322     inlinable = 1;
 323
 324   /* Squirrel away the result so that we don't have to check again.  */
 325   DECL_UNINLINABLE (fn) = !inlinable;
 326
 327   /* Don't do recursive inlining, either.  We don't record this in
 328      DECL_UNLINABLE; we may be able to inline this function later.  */
 329   if (inlinable)
 330     {
 331       size_t i;
 332
 333       for (i = 0; i < id->fns_top; ++i)
 334         if (VARRAY_TREE (id->fns, i) == fn)
 335           inlinable = 0;
 336     }
 337
 338   /* We can inline a template instantiation only if its fully
 339      instantiated.  */
 340   if (inlinable
 341       && DECL_TEMPLATE_INFO (fn)
 342       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
 343     {
 344       fn = instantiate_decl (fn);
 345       inlinable = !TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn));
 346     }
 347
 348   /* Return the result.  */
 349   return inlinable;
 350 }
 351
 352 /* If *TP is CALL_EXPR, replace it with its inline expansion.  */
 353
 354 static tree
 355 expand_call_inline (tp, walk_subtrees, data)
 356      tree *tp;
 357      int *walk_subtrees;
 358      void *data;
 359 {
 360   inline_data *id;
 361   tree t;
 362   tree expr;
 363   tree chain;
 364   tree fn;
 365   tree use_stmt;
 366   splay_tree st;
 367
 368   /* We're only interested in CALL_EXPRs.  */
 369   t = *tp;
 370   if (TREE_CODE (t) != CALL_EXPR)
 371     return NULL_TREE;
 372
 373   /* First, see if we can figure out what function is being called.
 374      If we cannot, then there is no hope of inlining the function.  */
 375   fn = get_callee_fndecl (t);
 376   if (!fn)
 377     return NULL_TREE;
 378
 379   /* Don't try to inline functions that are not well-suited to
 380      inlining.  */
 381   id = (inline_data *) data;
 382   if (!inlinable_function_p (fn, id))
 383     return NULL_TREE;
 384
 385   /* Return statements in the function body will be replaced by jumps
 386      to the RET_LABEL.  */
 387   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 388   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
 389
 390   /* Build a statement-expression containing code to initialize the
 391      arguments, the actual inline expansion of the body, and a label
 392      for the return statements within the function to jump to.  The
 393      type of the statement expression is the return type of the
 394      function call.  */
 395   expr = build_min (STMT_EXPR, TREE_TYPE (TREE_TYPE (fn)), NULL_TREE);
 396
 397   /* Record the function we are about to inline so that we can avoid
 398      recursing into it.  */
 399   if (id->fns_top > id->fns->num_elements)
 400     VARRAY_GROW (id->fns, 2 * id->fns->num_elements);
 401   VARRAY_TREE (id->fns, id->fns_top++) = fn;
 402
 403   /* Local declarations will be replaced by their equivalents in this
 404      map.  */
 405   st = id->decl_map;
 406   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
 407                                  NULL, NULL);
 408
 409   /* Initialize the parameters.  */
 410   STMT_EXPR_STMT (expr)
 411     = initialize_inlined_parameters (id, TREE_OPERAND (t, 1));
 412
 413   /* Declare the return variable for the function.  */
 414   STMT_EXPR_STMT (expr)
 415     = chainon (STMT_EXPR_STMT (expr),
 416                declare_return_variable (id, &use_stmt));
 417
 418   /* After we've initialized the parameters, we insert the body of the
 419      function itself.  */
 420   STMT_EXPR_STMT (expr)
 421     = chainon (STMT_EXPR_STMT (expr), copy_body (id));
 422
 423   /* Finally, mention the returned value so that the value of the
 424      statement-expression is the returned value of the function.  */
 425   STMT_EXPR_STMT (expr) = chainon (STMT_EXPR_STMT (expr), use_stmt);
 426
 427   /* Clean up.  */
 428   splay_tree_delete (id->decl_map);
 429   id->decl_map = st;
 430
 431   /* After the body of the function comes the RET_LABEL.  */
 432   STMT_EXPR_STMT (expr)
 433     = chainon (STMT_EXPR_STMT (expr),
 434                build_min_nt (LABEL_STMT, id->ret_label));
 435
 436   /* The new expression has side-effects if the old one did.  */
 437   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
 438   /* If the value of the new expression is ignored, that's OK.  We
 439      don't warn about this for CALL_EXPRs, so we shouldn't warn about
 440      the equivalent inlined version either.  */
 441   TREE_USED (expr) = 1;
 442
 443   /* Replace the call by the inlined body.  */
 444   chain = TREE_CHAIN (*tp);
 445   *tp = expr;
 446   TREE_CHAIN (expr) = chain;
 447
 448   /* Recurse into the body of the just inlined function.  */
 449   expand_calls_inline (tp, id);
 450   --id->fns_top;
 451
 452   /* Don't walk into subtrees.  We've already handled them above.  */
 453   *walk_subtrees = 0;
 454
 455   /* Keep iterating.  */
 456   return NULL_TREE;
 457 }
 458
 459 /* Walk over the entire tree *TP, replacing CALL_EXPRs with inline
 460    expansions as appropriate.  */
 461
 462 static void
 463 expand_calls_inline (tp, id)
 464      tree *tp;
 465      inline_data *id;
 466 {
 467   /* Search through *TP, replacing all calls to inline functions by
 468      appropriate equivalents.  */
 469   walk_tree (tp, expand_call_inline, id);
 470 }
 471
 472 /* Optimize the body of FN.  */
 473
 474 void
 475 optimize_function (fn)
 476      tree fn;
 477 {
 478   /* Expand calls to inline functions.  */
 479   if (flag_inline_trees)
 480     {
 481       inline_data id;
 482
 483       /* Clear out ID.  */
 484       bzero (&id, sizeof (id));
 485
 486       /* Don't allow recursion into FN.  */
 487       VARRAY_TREE_INIT (id.fns, 32, "fns");
 488       VARRAY_TREE (id.fns, id.fns_top++) = fn;
 489
 490       /* Replace all calls to inline functions with the bodies of those
 491          functions.  */
 492       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
 493
 494       /* Clean up.  */
 495       VARRAY_FREE (id.fns);
 496     }
 497 }