gcc/tree-inline.c

   1 /* Tree inlining.
   2    Copyright 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Alexandre Oliva <aoliva@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it 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 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "toplev.h"
  27 #include "tree.h"
  28 #include "tree-inline.h"
  29 #include "rtl.h"
  30 #include "expr.h"
  31 #include "flags.h"
  32 #include "params.h"
  33 #include "input.h"
  34 #include "insn-config.h"
  35 #include "integrate.h"
  36 #include "varray.h"
  37 #include "hashtab.h"
  38 #include "splay-tree.h"
  39 #include "langhooks.h"
  40 #include "cgraph.h"
  41 #include "intl.h"
  42 #include "tree-mudflap.h"
  43 #include "function.h"
  44 #include "diagnostic.h"
  45
  46 /* I'm not real happy about this, but we need to handle gimple and
  47    non-gimple trees.  */
  48 #include "tree-iterator.h"
  49 #include "tree-gimple.h"
  50
  51 /* 0 if we should not perform inlining.
  52    1 if we should expand functions calls inline at the tree level.
  53    2 if we should consider *all* functions to be inline
  54    candidates.  */
  55
  56 int flag_inline_trees = 0;
  57
  58 /* To Do:
  59
  60    o In order to make inlining-on-trees work, we pessimized
  61      function-local static constants.  In particular, they are now
  62      always output, even when not addressed.  Fix this by treating
  63      function-local static constants just like global static
  64      constants; the back-end already knows not to output them if they
  65      are not needed.
  66
  67    o Provide heuristics to clamp inlining of recursive template
  68      calls?  */
  69
  70 /* Data required for function inlining.  */
  71
  72 typedef struct inline_data
  73 {
  74   /* A stack of the functions we are inlining.  For example, if we are
  75      compiling `f', which calls `g', which calls `h', and we are
  76      inlining the body of `h', the stack will contain, `h', followed
  77      by `g', followed by `f'.  The first few elements of the stack may
  78      contain other functions that we know we should not recurse into,
  79      even though they are not directly being inlined.  */
  80   varray_type fns;
  81   /* The index of the first element of FNS that really represents an
  82      inlined function.  */
  83   unsigned first_inlined_fn;
  84   /* The label to jump to when a return statement is encountered.  If
  85      this value is NULL, then return statements will simply be
  86      remapped as return statements, rather than as jumps.  */
  87   tree ret_label;
  88   /* The VAR_DECL for the return value.  */
  89   tree retvar;
  90   /* The map from local declarations in the inlined function to
  91      equivalents in the function into which it is being inlined.  */
  92   splay_tree decl_map;
  93   /* Nonzero if we are currently within the cleanup for a
  94      TARGET_EXPR.  */
  95   int in_target_cleanup_p;
  96   /* A list of the functions current function has inlined.  */
  97   varray_type inlined_fns;
  98   /* We use the same mechanism to build clones that we do to perform
  99      inlining.  However, there are a few places where we need to
 100      distinguish between those two situations.  This flag is true if
 101      we are cloning, rather than inlining.  */
 102   bool cloning_p;
 103   /* Similarly for saving function body.  */
 104   bool saving_p;
 105   /* Hash table used to prevent walk_tree from visiting the same node
 106      umpteen million times.  */
 107   htab_t tree_pruner;
 108   /* Callgraph node of function we are inlining into.  */
 109   struct cgraph_node *node;
 110   /* Callgraph node of currently inlined function.  */
 111   struct cgraph_node *current_node;
 112   /* Statement iterator.  We need this so we can keep the tree in
 113      gimple form when we insert the inlined function.   It is not
 114      used when we are not dealing with gimple trees.  */
 115   tree_stmt_iterator tsi;
 116 } inline_data;
 117
 118 /* Prototypes.  */
 119
 120 /* The approximate number of instructions per statement.  This number
 121    need not be particularly accurate; it is used only to make
 122    decisions about when a function is too big to inline.  */
 123 #define INSNS_PER_STMT (10)
 124
 125 static tree copy_body_r (tree *, int *, void *);
 126 static tree copy_body (inline_data *);
 127 static tree expand_call_inline (tree *, int *, void *);
 128 static void expand_calls_inline (tree *, inline_data *);
 129 static bool inlinable_function_p (tree);
 130 static tree remap_decl (tree, inline_data *);
 131 static tree remap_type (tree, inline_data *);
 132 static tree initialize_inlined_parameters (inline_data *, tree,
 133                                            tree, tree, tree);
 134 static void remap_block (tree *, inline_data *);
 135 static tree remap_decls (tree, inline_data *);
 136 static void copy_bind_expr (tree *, int *, inline_data *);
 137 static tree mark_local_for_remap_r (tree *, int *, void *);
 138 static void unsave_expr_1 (tree);
 139 static tree unsave_r (tree *, int *, void *);
 140 static void declare_inline_vars (tree bind_expr, tree vars);
 141
 142 /* Insert a tree->tree mapping for ID.  Despite the name suggests
 143    that the trees should be variables, it is used for more than that.  */
 144
 145 static void
 146 insert_decl_map (inline_data *id, tree key, tree value)
 147 {
 148   splay_tree_insert (id->decl_map, (splay_tree_key) key,
 149                      (splay_tree_value) value);
 150
 151   /* Always insert an identity map as well.  If we see this same new
 152      node again, we won't want to duplicate it a second time.  */
 153   if (key != value)
 154     splay_tree_insert (id->decl_map, (splay_tree_key) value,
 155                        (splay_tree_value) value);
 156 }
 157
 158 /* Remap DECL during the copying of the BLOCK tree for the function.
 159    We are only called to remap local variables in the current function.  */
 160
 161 static tree
 162 remap_decl (tree decl, inline_data *id)
 163 {
 164   splay_tree_node n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 165   tree fn = VARRAY_TOP_TREE (id->fns);
 166
 167   /* See if we have remapped this declaration.  If we didn't already have an
 168      equivalent for this declaration, create one now.  */
 169   if (!n)
 170     {
 171       /* Make a copy of the variable or label.  */
 172       tree t = copy_decl_for_inlining (decl, fn, VARRAY_TREE (id->fns, 0));
 173
 174       /* Remap types, if necessary.  */
 175       TREE_TYPE (t) = remap_type (TREE_TYPE (t), id);
 176       if (TREE_CODE (t) == TYPE_DECL)
 177         DECL_ORIGINAL_TYPE (t) = remap_type (DECL_ORIGINAL_TYPE (t), id);
 178       else if (TREE_CODE (t) == PARM_DECL)
 179         DECL_ARG_TYPE_AS_WRITTEN (t)
 180           = remap_type (DECL_ARG_TYPE_AS_WRITTEN (t), id);
 181
 182       /* Remap sizes as necessary.  */
 183       walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
 184       walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
 185
 186       /* If fields, do likewise for offset and qualifier.  */
 187       if (TREE_CODE (t) == FIELD_DECL)
 188         {
 189           walk_tree (&DECL_FIELD_OFFSET (t), copy_body_r, id, NULL);
 190           if (TREE_CODE (DECL_CONTEXT (t)) == QUAL_UNION_TYPE)
 191             walk_tree (&DECL_QUALIFIER (t), copy_body_r, id, NULL);
 192         }
 193
 194 #if 0
 195       /* FIXME handle anon aggrs.  */
 196       if (! DECL_NAME (t) && TREE_TYPE (t)
 197           && lang_hooks.tree_inlining.anon_aggr_type_p (TREE_TYPE (t)))
 198         {
 199           /* For a VAR_DECL of anonymous type, we must also copy the
 200              member VAR_DECLS here and rechain the DECL_ANON_UNION_ELEMS.  */
 201           tree members = NULL;
 202           tree src;
 203
 204           for (src = DECL_ANON_UNION_ELEMS (t); src;
 205                src = TREE_CHAIN (src))
 206             {
 207               tree member = remap_decl (TREE_VALUE (src), id);
 208
 209               gcc_assert (!TREE_PURPOSE (src));
 210               members = tree_cons (NULL, member, members);
 211             }
 212           DECL_ANON_UNION_ELEMS (t) = nreverse (members);
 213         }
 214 #endif
 215
 216       /* Remember it, so that if we encounter this local entity
 217          again we can reuse this copy.  */
 218       insert_decl_map (id, decl, t);
 219       return t;
 220     }
 221
 222   return unshare_expr ((tree) n->value);
 223 }
 224
 225 static tree
 226 remap_type (tree type, inline_data *id)
 227 {
 228   splay_tree_node node;
 229   tree new, t;
 230
 231   if (type == NULL)
 232     return type;
 233
 234   /* See if we have remapped this type.  */
 235   node = splay_tree_lookup (id->decl_map, (splay_tree_key) type);
 236   if (node)
 237     return (tree) node->value;
 238
 239   /* The type only needs remapping if it's variably modified by a variable
 240      in the function we are inlining.  */
 241   if (! variably_modified_type_p (type, VARRAY_TOP_TREE (id->fns)))
 242     {
 243       insert_decl_map (id, type, type);
 244       return type;
 245     }
 246
 247   /* We do need a copy.  build and register it now.  If this is a pointer or
 248      reference type, remap the designated type and make a new pointer or
 249      reference type.  */
 250   if (TREE_CODE (type) == POINTER_TYPE)
 251     {
 252       new = build_pointer_type_for_mode (remap_type (TREE_TYPE (type), id),
 253                                          TYPE_MODE (type),
 254                                          TYPE_REF_CAN_ALIAS_ALL (type));
 255       insert_decl_map (id, type, new);
 256       return new;
 257     }
 258   else if (TREE_CODE (type) == REFERENCE_TYPE)
 259     {
 260       new = build_reference_type_for_mode (remap_type (TREE_TYPE (type), id),
 261                                             TYPE_MODE (type),
 262                                             TYPE_REF_CAN_ALIAS_ALL (type));
 263       insert_decl_map (id, type, new);
 264       return new;
 265     }
 266   else
 267     new = copy_node (type);
 268
 269   insert_decl_map (id, type, new);
 270
 271   /* This is a new type, not a copy of an old type.  Need to reassociate
 272      variants.  We can handle everything except the main variant lazily.  */
 273   t = TYPE_MAIN_VARIANT (type);
 274   if (type != t)
 275     {
 276       t = remap_type (t, id);
 277       TYPE_MAIN_VARIANT (new) = t;
 278       TYPE_NEXT_VARIANT (new) = TYPE_MAIN_VARIANT (t);
 279       TYPE_NEXT_VARIANT (t) = new;
 280     }
 281   else
 282     {
 283       TYPE_MAIN_VARIANT (new) = new;
 284       TYPE_NEXT_VARIANT (new) = NULL;
 285     }
 286
 287   /* Lazily create pointer and reference types.  */
 288   TYPE_POINTER_TO (new) = NULL;
 289   TYPE_REFERENCE_TO (new) = NULL;
 290
 291   switch (TREE_CODE (new))
 292     {
 293     case INTEGER_TYPE:
 294     case REAL_TYPE:
 295     case ENUMERAL_TYPE:
 296     case BOOLEAN_TYPE:
 297     case CHAR_TYPE:
 298       t = TYPE_MIN_VALUE (new);
 299       if (t && TREE_CODE (t) != INTEGER_CST)
 300         walk_tree (&TYPE_MIN_VALUE (new), copy_body_r, id, NULL);
 301
 302       t = TYPE_MAX_VALUE (new);
 303       if (t && TREE_CODE (t) != INTEGER_CST)
 304         walk_tree (&TYPE_MAX_VALUE (new), copy_body_r, id, NULL);
 305       return new;
 306
 307     case FUNCTION_TYPE:
 308       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 309       walk_tree (&TYPE_ARG_TYPES (new), copy_body_r, id, NULL);
 310       return new;
 311
 312     case ARRAY_TYPE:
 313       TREE_TYPE (new) = remap_type (TREE_TYPE (new), id);
 314       TYPE_DOMAIN (new) = remap_type (TYPE_DOMAIN (new), id);
 315       break;
 316
 317     case RECORD_TYPE:
 318     case UNION_TYPE:
 319     case QUAL_UNION_TYPE:
 320       walk_tree (&TYPE_FIELDS (new), copy_body_r, id, NULL);
 321       break;
 322
 323     case FILE_TYPE:
 324     case SET_TYPE:
 325     case OFFSET_TYPE:
 326     default:
 327       /* Shouldn't have been thought variable sized.  */
 328       gcc_unreachable ();
 329     }
 330
 331   walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
 332   walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
 333
 334   return new;
 335 }
 336
 337 static tree
 338 remap_decls (tree decls, inline_data *id)
 339 {
 340   tree old_var;
 341   tree new_decls = NULL_TREE;
 342
 343   /* Remap its variables.  */
 344   for (old_var = decls; old_var; old_var = TREE_CHAIN (old_var))
 345     {
 346       tree new_var;
 347
 348       /* Remap the variable.  */
 349       new_var = remap_decl (old_var, id);
 350
 351       /* If we didn't remap this variable, so we can't mess with its
 352          TREE_CHAIN.  If we remapped this variable to the return slot, it's
 353          already declared somewhere else, so don't declare it here.  */
 354       if (!new_var || new_var == id->retvar)
 355         ;
 356       else
 357         {
 358           gcc_assert (DECL_P (new_var));
 359           TREE_CHAIN (new_var) = new_decls;
 360           new_decls = new_var;
 361         }
 362     }
 363
 364   return nreverse (new_decls);
 365 }
 366
 367 /* Copy the BLOCK to contain remapped versions of the variables
 368    therein.  And hook the new block into the block-tree.  */
 369
 370 static void
 371 remap_block (tree *block, inline_data *id)
 372 {
 373   tree old_block;
 374   tree new_block;
 375   tree fn;
 376
 377   /* Make the new block.  */
 378   old_block = *block;
 379   new_block = make_node (BLOCK);
 380   TREE_USED (new_block) = TREE_USED (old_block);
 381   BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 382   *block = new_block;
 383
 384   /* Remap its variables.  */
 385   BLOCK_VARS (new_block) = remap_decls (BLOCK_VARS (old_block), id);
 386
 387   fn = VARRAY_TREE (id->fns, 0);
 388 #if 1
 389   /* FIXME!  It shouldn't be so hard to manage blocks.  Rebuilding them in
 390      rest_of_compilation is a good start.  */
 391   if (id->cloning_p)
 392     /* We're building a clone; DECL_INITIAL is still
 393        error_mark_node, and current_binding_level is the parm
 394        binding level.  */
 395     lang_hooks.decls.insert_block (new_block);
 396   else
 397     {
 398       /* Attach this new block after the DECL_INITIAL block for the
 399          function into which this block is being inlined.  In
 400          rest_of_compilation we will straighten out the BLOCK tree.  */
 401       tree *first_block;
 402       if (DECL_INITIAL (fn))
 403         first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
 404       else
 405         first_block = &DECL_INITIAL (fn);
 406       BLOCK_CHAIN (new_block) = *first_block;
 407       *first_block = new_block;
 408     }
 409 #endif
 410   /* Remember the remapped block.  */
 411   insert_decl_map (id, old_block, new_block);
 412 }
 413
 414 static void
 415 copy_statement_list (tree *tp)
 416 {
 417   tree_stmt_iterator oi, ni;
 418   tree new;
 419
 420   new = alloc_stmt_list ();
 421   ni = tsi_start (new);
 422   oi = tsi_start (*tp);
 423   *tp = new;
 424
 425   for (; !tsi_end_p (oi); tsi_next (&oi))
 426     tsi_link_after (&ni, tsi_stmt (oi), TSI_NEW_STMT);
 427 }
 428
 429 static void
 430 copy_bind_expr (tree *tp, int *walk_subtrees, inline_data *id)
 431 {
 432   tree block = BIND_EXPR_BLOCK (*tp);
 433   /* Copy (and replace) the statement.  */
 434   copy_tree_r (tp, walk_subtrees, NULL);
 435   if (block)
 436     {
 437       remap_block (&block, id);
 438       BIND_EXPR_BLOCK (*tp) = block;
 439     }
 440
 441   if (BIND_EXPR_VARS (*tp))
 442     /* This will remap a lot of the same decls again, but this should be
 443        harmless.  */
 444     BIND_EXPR_VARS (*tp) = remap_decls (BIND_EXPR_VARS (*tp), id);
 445 }
 446
 447 /* Called from copy_body via walk_tree.  DATA is really an `inline_data *'.  */
 448
 449 static tree
 450 copy_body_r (tree *tp, int *walk_subtrees, void *data)
 451 {
 452   inline_data *id = (inline_data *) data;
 453   tree fn = VARRAY_TOP_TREE (id->fns);
 454
 455 #if 0
 456   /* All automatic variables should have a DECL_CONTEXT indicating
 457      what function they come from.  */
 458   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 459       && DECL_NAMESPACE_SCOPE_P (*tp))
 460     gcc_assert (DECL_EXTERNAL (*tp) || TREE_STATIC (*tp));
 461 #endif
 462
 463   /* If this is a RETURN_EXPR, change it into a MODIFY_EXPR and a
 464      GOTO_EXPR with the RET_LABEL as its target.  */
 465   if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
 466     {
 467       tree return_stmt = *tp;
 468       tree goto_stmt;
 469
 470       /* Build the GOTO_EXPR.  */
 471       tree assignment = TREE_OPERAND (return_stmt, 0);
 472       goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
 473       TREE_USED (id->ret_label) = 1;
 474
 475       /* If we're returning something, just turn that into an
 476          assignment into the equivalent of the original
 477          RESULT_DECL.  */
 478       if (assignment)
 479         {
 480           /* Do not create a statement containing a naked RESULT_DECL.  */
 481           if (TREE_CODE (assignment) == RESULT_DECL)
 482             gimplify_stmt (&assignment);
 483
 484           *tp = build (BIND_EXPR, void_type_node, NULL, NULL, NULL);
 485           append_to_statement_list (assignment, &BIND_EXPR_BODY (*tp));
 486           append_to_statement_list (goto_stmt, &BIND_EXPR_BODY (*tp));
 487         }
 488       /* If we're not returning anything just do the jump.  */
 489       else
 490         *tp = goto_stmt;
 491     }
 492   /* Local variables and labels need to be replaced by equivalent
 493      variables.  We don't want to copy static variables; there's only
 494      one of those, no matter how many times we inline the containing
 495      function.  Similarly for globals from an outer function.  */
 496   else if (lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
 497     {
 498       tree new_decl;
 499
 500       /* Remap the declaration.  */
 501       new_decl = remap_decl (*tp, id);
 502       gcc_assert (new_decl);
 503       /* Replace this variable with the copy.  */
 504       STRIP_TYPE_NOPS (new_decl);
 505       *tp = new_decl;
 506     }
 507   else if (TREE_CODE (*tp) == STATEMENT_LIST)
 508     copy_statement_list (tp);
 509   else if (TREE_CODE (*tp) == SAVE_EXPR)
 510     remap_save_expr (tp, id->decl_map, walk_subtrees);
 511   else if (TREE_CODE (*tp) == BIND_EXPR)
 512     copy_bind_expr (tp, walk_subtrees, id);
 513   else if (TREE_CODE (*tp) == LABELED_BLOCK_EXPR)
 514     {
 515       /* We need a new copy of this labeled block; the EXIT_BLOCK_EXPR
 516          will refer to it, so save a copy ready for remapping.  We
 517          save it in the decl_map, although it isn't a decl.  */
 518       tree new_block = copy_node (*tp);
 519       insert_decl_map (id, *tp, new_block);
 520       *tp = new_block;
 521     }
 522   else if (TREE_CODE (*tp) == EXIT_BLOCK_EXPR)
 523     {
 524       splay_tree_node n
 525         = splay_tree_lookup (id->decl_map,
 526                              (splay_tree_key) TREE_OPERAND (*tp, 0));
 527       /* We _must_ have seen the enclosing LABELED_BLOCK_EXPR.  */
 528       gcc_assert (n);
 529       *tp = copy_node (*tp);
 530       TREE_OPERAND (*tp, 0) = (tree) n->value;
 531     }
 532   /* Types may need remapping as well.  */
 533   else if (TYPE_P (*tp))
 534     *tp = remap_type (*tp, id);
 535
 536   /* Otherwise, just copy the node.  Note that copy_tree_r already
 537      knows not to copy VAR_DECLs, etc., so this is safe.  */
 538   else
 539     {
 540       tree old_node = *tp;
 541
 542       if (TREE_CODE (*tp) == MODIFY_EXPR
 543           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 544           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 545               (TREE_OPERAND (*tp, 0), fn)))
 546         {
 547           /* Some assignments VAR = VAR; don't generate any rtl code
 548              and thus don't count as variable modification.  Avoid
 549              keeping bogosities like 0 = 0.  */
 550           tree decl = TREE_OPERAND (*tp, 0), value;
 551           splay_tree_node n;
 552
 553           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 554           if (n)
 555             {
 556               value = (tree) n->value;
 557               STRIP_TYPE_NOPS (value);
 558               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 559                 {
 560                   *tp = value;
 561                   return copy_body_r (tp, walk_subtrees, data);
 562                 }
 563             }
 564         }
 565       else if (TREE_CODE (*tp) == INDIRECT_REF)
 566         {
 567           /* Get rid of *& from inline substitutions that can happen when a
 568              pointer argument is an ADDR_EXPR.  */
 569           tree decl = TREE_OPERAND (*tp, 0), value;
 570           splay_tree_node n;
 571
 572           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 573           if (n)
 574             {
 575               value = (tree) n->value;
 576               STRIP_NOPS (value);
 577               if (TREE_CODE (value) == ADDR_EXPR
 578                   && (lang_hooks.types_compatible_p
 579                       (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0)))))
 580                 {
 581                   *tp = TREE_OPERAND (value, 0);
 582                   return copy_body_r (tp, walk_subtrees, data);
 583                 }
 584             }
 585         }
 586
 587       copy_tree_r (tp, walk_subtrees, NULL);
 588
 589       if (TREE_CODE (*tp) == CALL_EXPR && id->node && get_callee_fndecl (*tp))
 590         {
 591           if (id->saving_p)
 592             {
 593               struct cgraph_node *node;
 594               struct cgraph_edge *edge;
 595
 596               for (node = id->node->next_clone; node; node = node->next_clone)
 597                 {
 598                   edge = cgraph_edge (node, old_node);
 599                   gcc_assert (edge);
 600                   edge->call_expr = *tp;
 601                 }
 602             }
 603           else
 604             {
 605               struct cgraph_edge *edge
 606                 = cgraph_edge (id->current_node, old_node);
 607
 608               if (edge)
 609                 cgraph_clone_edge (edge, id->node, *tp);
 610             }
 611         }
 612
 613       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 614
 615       /* The copied TARGET_EXPR has never been expanded, even if the
 616          original node was expanded already.  */
 617       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 618         {
 619           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 620           TREE_OPERAND (*tp, 3) = NULL_TREE;
 621         }
 622
 623       /* Variable substitution need not be simple.  In particular, the
 624          INDIRECT_REF substitution above.  Make sure that TREE_CONSTANT
 625          and friends are up-to-date.  */
 626       else if (TREE_CODE (*tp) == ADDR_EXPR)
 627         {
 628           walk_tree (&TREE_OPERAND (*tp, 0), copy_body_r, id, NULL);
 629           recompute_tree_invarant_for_addr_expr (*tp);
 630           *walk_subtrees = 0;
 631         }
 632     }
 633
 634   /* Keep iterating.  */
 635   return NULL_TREE;
 636 }
 637
 638 /* Make a copy of the body of FN so that it can be inserted inline in
 639    another function.  */
 640
 641 static tree
 642 copy_body (inline_data *id)
 643 {
 644   tree body;
 645   tree fndecl = VARRAY_TOP_TREE (id->fns);
 646
 647   if (fndecl == current_function_decl
 648       && cfun->saved_tree)
 649     body = cfun->saved_tree;
 650   else
 651     body = DECL_SAVED_TREE (fndecl);
 652   walk_tree (&body, copy_body_r, id, NULL);
 653
 654   return body;
 655 }
 656
 657 static void
 658 setup_one_parameter (inline_data *id, tree p, tree value, tree fn,
 659                      tree *init_stmts, tree *vars, bool *gimplify_init_stmts_p)
 660 {
 661   tree init_stmt;
 662   tree var;
 663
 664   /* If the parameter is never assigned to, we may not need to
 665      create a new variable here at all.  Instead, we may be able
 666      to just use the argument value.  */
 667   if (TREE_READONLY (p)
 668       && !TREE_ADDRESSABLE (p)
 669       && value && !TREE_SIDE_EFFECTS (value))
 670     {
 671       /* We can't risk substituting complex expressions.  They
 672          might contain variables that will be assigned to later.
 673          Theoretically, we could check the expression to see if
 674          all of the variables that determine its value are
 675          read-only, but we don't bother.  */
 676       /* We may produce non-gimple trees by adding NOPs or introduce
 677          invalid sharing when operand is not really constant.
 678          It is not big deal to prohibit constant propagation here as
 679          we will constant propagate in DOM1 pass anyway.  */
 680       if (is_gimple_min_invariant (value)
 681           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p)))
 682         {
 683           insert_decl_map (id, p, value);
 684           return;
 685         }
 686     }
 687
 688   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
 689      here since the type of this decl must be visible to the calling
 690      function.  */
 691   var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 692
 693   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 694      that way, when the PARM_DECL is encountered, it will be
 695      automatically replaced by the VAR_DECL.  */
 696   insert_decl_map (id, p, var);
 697
 698   /* Declare this new variable.  */
 699   TREE_CHAIN (var) = *vars;
 700   *vars = var;
 701
 702   /* Make gimplifier happy about this variable.  */
 703   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 704
 705   /* Even if P was TREE_READONLY, the new VAR should not be.
 706      In the original code, we would have constructed a
 707      temporary, and then the function body would have never
 708      changed the value of P.  However, now, we will be
 709      constructing VAR directly.  The constructor body may
 710      change its value multiple times as it is being
 711      constructed.  Therefore, it must not be TREE_READONLY;
 712      the back-end assumes that TREE_READONLY variable is
 713      assigned to only once.  */
 714   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 715     TREE_READONLY (var) = 0;
 716
 717   /* Initialize this VAR_DECL from the equivalent argument.  Convert
 718      the argument to the proper type in case it was promoted.  */
 719   if (value)
 720     {
 721       tree rhs = fold_convert (TREE_TYPE (var), value);
 722
 723       if (rhs == error_mark_node)
 724         return;
 725
 726       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
 727          keep our trees in gimple form.  */
 728       init_stmt = build (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
 729       append_to_statement_list (init_stmt, init_stmts);
 730
 731       /* If we did not create a gimple value and we did not create a gimple
 732          cast of a gimple value, then we will need to gimplify INIT_STMTS
 733          at the end.  Note that is_gimple_cast only checks the outer
 734          tree code, not its operand.  Thus the explicit check that it's
 735          operand is a gimple value.  */
 736       if (!is_gimple_val (rhs)
 737           && (!is_gimple_cast (rhs)
 738               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
 739         *gimplify_init_stmts_p = true;
 740     }
 741 }
 742
 743 /* Generate code to initialize the parameters of the function at the
 744    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 745
 746 static tree
 747 initialize_inlined_parameters (inline_data *id, tree args, tree static_chain,
 748                                tree fn, tree bind_expr)
 749 {
 750   tree init_stmts = NULL_TREE;
 751   tree parms;
 752   tree a;
 753   tree p;
 754   tree vars = NULL_TREE;
 755   bool gimplify_init_stmts_p = false;
 756   int argnum = 0;
 757
 758   /* Figure out what the parameters are.  */
 759   parms = DECL_ARGUMENTS (fn);
 760   if (fn == current_function_decl)
 761     parms = cfun->saved_args;
 762
 763   /* Loop through the parameter declarations, replacing each with an
 764      equivalent VAR_DECL, appropriately initialized.  */
 765   for (p = parms, a = args; p;
 766        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 767     {
 768       tree value;
 769
 770       ++argnum;
 771
 772       /* Find the initializer.  */
 773       value = lang_hooks.tree_inlining.convert_parm_for_inlining
 774               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
 775
 776       setup_one_parameter (id, p, value, fn, &init_stmts, &vars,
 777                            &gimplify_init_stmts_p);
 778     }
 779
 780   /* Evaluate trailing arguments.  */
 781   for (; a; a = TREE_CHAIN (a))
 782     {
 783       tree value = TREE_VALUE (a);
 784       append_to_statement_list (value, &init_stmts);
 785     }
 786
 787   /* Initialize the static chain.  */
 788   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
 789   if (p)
 790     {
 791       /* No static chain?  Seems like a bug in tree-nested.c.  */
 792       gcc_assert (static_chain);
 793
 794       setup_one_parameter (id, p, static_chain, fn, &init_stmts, &vars,
 795                            &gimplify_init_stmts_p);
 796     }
 797
 798   if (gimplify_init_stmts_p)
 799     gimplify_body (&init_stmts, current_function_decl);
 800
 801   declare_inline_vars (bind_expr, vars);
 802   return init_stmts;
 803 }
 804
 805 /* Declare a return variable to replace the RESULT_DECL for the function we
 806    are calling.  RETURN_SLOT_ADDR, if non-null, was a fake parameter that
 807    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
 808    the MODIFY_EXPR to which this call is the RHS.
 809
 810    The return value is a (possibly null) value that is the result of the
 811    function as seen by the callee.  *USE_P is a (possibly null) value that
 812    holds the result as seen by the caller.  */
 813
 814 static tree
 815 declare_return_variable (inline_data *id, tree return_slot_addr,
 816                          tree modify_dest, tree *use_p)
 817 {
 818   tree callee = VARRAY_TOP_TREE (id->fns);
 819   tree caller = VARRAY_TREE (id->fns, 0);
 820   tree result = DECL_RESULT (callee);
 821   tree callee_type = TREE_TYPE (result);
 822   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
 823   tree var, use;
 824
 825   /* We don't need to do anything for functions that don't return
 826      anything.  */
 827   if (!result || VOID_TYPE_P (callee_type))
 828     {
 829       *use_p = NULL_TREE;
 830       return NULL_TREE;
 831     }
 832
 833   /* If there was a return slot, then the return value is the
 834      dereferenced address of that object.  */
 835   if (return_slot_addr)
 836     {
 837       /* The front end shouldn't have used both return_slot_addr and
 838          a modify expression.  */
 839       gcc_assert (!modify_dest);
 840       if (DECL_BY_REFERENCE (result))
 841         var = return_slot_addr;
 842       else
 843         var = build_fold_indirect_ref (return_slot_addr);
 844       use = NULL;
 845       goto done;
 846     }
 847
 848   /* All types requiring non-trivial constructors should have been handled.  */
 849   gcc_assert (!TREE_ADDRESSABLE (callee_type));
 850
 851   /* Attempt to avoid creating a new temporary variable.  */
 852   if (modify_dest)
 853     {
 854       bool use_it = false;
 855
 856       /* We can't use MODIFY_DEST if there's type promotion involved.  */
 857       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
 858         use_it = false;
 859
 860       /* ??? If we're assigning to a variable sized type, then we must
 861          reuse the destination variable, because we've no good way to
 862          create variable sized temporaries at this point.  */
 863       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
 864         use_it = true;
 865
 866       /* If the callee cannot possibly modify MODIFY_DEST, then we can
 867          reuse it as the result of the call directly.  Don't do this if
 868          it would promote MODIFY_DEST to addressable.  */
 869       else if (!TREE_STATIC (modify_dest)
 870                && !TREE_ADDRESSABLE (modify_dest)
 871                && !TREE_ADDRESSABLE (result))
 872         use_it = true;
 873
 874       if (use_it)
 875         {
 876           var = modify_dest;
 877           use = NULL;
 878           goto done;
 879         }
 880     }
 881
 882   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
 883
 884   var = copy_decl_for_inlining (result, callee, caller);
 885   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 886   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
 887     = tree_cons (NULL_TREE, var,
 888                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
 889
 890   /* Do not have the rest of GCC warn about this variable as it should
 891      not be visible to the user.   */
 892   TREE_NO_WARNING (var) = 1;
 893
 894   /* Build the use expr.  If the return type of the function was
 895      promoted, convert it back to the expected type.  */
 896   use = var;
 897   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
 898     use = fold_convert (caller_type, var);
 899
 900  done:
 901   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 902      way, when the RESULT_DECL is encountered, it will be
 903      automatically replaced by the VAR_DECL.  */
 904   insert_decl_map (id, result, var);
 905
 906   /* Remember this so we can ignore it in remap_decls.  */
 907   id->retvar = var;
 908
 909   *use_p = use;
 910   return var;
 911 }
 912
 913 /* Returns nonzero if a function can be inlined as a tree.  */
 914
 915 bool
 916 tree_inlinable_function_p (tree fn)
 917 {
 918   return inlinable_function_p (fn);
 919 }
 920
 921 static const char *inline_forbidden_reason;
 922
 923 static tree
 924 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
 925                       void *fnp)
 926 {
 927   tree node = *nodep;
 928   tree fn = (tree) fnp;
 929   tree t;
 930
 931   switch (TREE_CODE (node))
 932     {
 933     case CALL_EXPR:
 934       /* Refuse to inline alloca call unless user explicitly forced so as
 935          this may change program's memory overhead drastically when the
 936          function using alloca is called in loop.  In GCC present in
 937          SPEC2000 inlining into schedule_block cause it to require 2GB of
 938          RAM instead of 256MB.  */
 939       if (alloca_call_p (node)
 940           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
 941         {
 942           inline_forbidden_reason
 943             = N_("%Jfunction '%F' can never be inlined because it uses "
 944                  "alloca (override using the always_inline attribute)");
 945           return node;
 946         }
 947       t = get_callee_fndecl (node);
 948       if (! t)
 949         break;
 950
 951       /* We cannot inline functions that call setjmp.  */
 952       if (setjmp_call_p (t))
 953         {
 954           inline_forbidden_reason
 955             = N_("%Jfunction '%F' can never be inlined because it uses setjmp");
 956           return node;
 957         }
 958
 959       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
 960         switch (DECL_FUNCTION_CODE (t))
 961           {
 962             /* We cannot inline functions that take a variable number of
 963                arguments.  */
 964           case BUILT_IN_VA_START:
 965           case BUILT_IN_STDARG_START:
 966           case BUILT_IN_NEXT_ARG:
 967           case BUILT_IN_VA_END:
 968             inline_forbidden_reason
 969               = N_("%Jfunction '%F' can never be inlined because it "
 970                    "uses variable argument lists");
 971             return node;
 972
 973           case BUILT_IN_LONGJMP:
 974             /* We can't inline functions that call __builtin_longjmp at
 975                all.  The non-local goto machinery really requires the
 976                destination be in a different function.  If we allow the
 977                function calling __builtin_longjmp to be inlined into the
 978                function calling __builtin_setjmp, Things will Go Awry.  */
 979             inline_forbidden_reason
 980               = N_("%Jfunction '%F' can never be inlined because "
 981                    "it uses setjmp-longjmp exception handling");
 982             return node;
 983
 984           case BUILT_IN_NONLOCAL_GOTO:
 985             /* Similarly.  */
 986             inline_forbidden_reason
 987               = N_("%Jfunction '%F' can never be inlined because "
 988                    "it uses non-local goto");
 989             return node;
 990
 991           default:
 992             break;
 993           }
 994       break;
 995
 996     case BIND_EXPR:
 997       for (t = BIND_EXPR_VARS (node); t ; t = TREE_CHAIN (t))
 998         {
 999           /* We cannot inline functions that contain other functions.  */
1000           if (TREE_CODE (t) == FUNCTION_DECL && DECL_INITIAL (t))
1001             {
1002               inline_forbidden_reason
1003                 = N_("%Jfunction '%F' can never be inlined "
1004                      "because it contains a nested function");
1005               return node;
1006             }
1007         }
1008       break;
1009
1010     case GOTO_EXPR:
1011       t = TREE_OPERAND (node, 0);
1012
1013       /* We will not inline a function which uses computed goto.  The
1014          addresses of its local labels, which may be tucked into
1015          global storage, are of course not constant across
1016          instantiations, which causes unexpected behavior.  */
1017       if (TREE_CODE (t) != LABEL_DECL)
1018         {
1019           inline_forbidden_reason
1020             = N_("%Jfunction '%F' can never be inlined "
1021                  "because it contains a computed goto");
1022           return node;
1023         }
1024       break;
1025
1026     case LABEL_EXPR:
1027       t = TREE_OPERAND (node, 0);
1028       if (DECL_NONLOCAL (t))
1029         {
1030           /* We cannot inline a function that receives a non-local goto
1031              because we cannot remap the destination label used in the
1032              function that is performing the non-local goto.  */
1033           inline_forbidden_reason
1034             = N_("%Jfunction '%F' can never be inlined "
1035                  "because it receives a non-local goto");
1036           return node;
1037         }
1038       break;
1039
1040     case RECORD_TYPE:
1041     case UNION_TYPE:
1042       /* We cannot inline a function of the form
1043
1044            void F (int i) { struct S { int ar[i]; } s; }
1045
1046          Attempting to do so produces a catch-22.
1047          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1048          UNION_TYPE nodes, then it goes into infinite recursion on a
1049          structure containing a pointer to its own type.  If it doesn't,
1050          then the type node for S doesn't get adjusted properly when
1051          F is inlined, and we abort in find_function_data.  */
1052       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1053         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1054           {
1055             inline_forbidden_reason
1056               = N_("%Jfunction '%F' can never be inlined "
1057                    "because it uses variable sized variables");
1058             return node;
1059           }
1060
1061     default:
1062       break;
1063     }
1064
1065   return NULL_TREE;
1066 }
1067
1068 /* Return subexpression representing possible alloca call, if any.  */
1069 static tree
1070 inline_forbidden_p (tree fndecl)
1071 {
1072   location_t saved_loc = input_location;
1073   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1074                                            inline_forbidden_p_1, fndecl);
1075
1076   input_location = saved_loc;
1077   return ret;
1078 }
1079
1080 /* Returns nonzero if FN is a function that does not have any
1081    fundamental inline blocking properties.  */
1082
1083 static bool
1084 inlinable_function_p (tree fn)
1085 {
1086   bool inlinable = true;
1087
1088   /* If we've already decided this function shouldn't be inlined,
1089      there's no need to check again.  */
1090   if (DECL_UNINLINABLE (fn))
1091     return false;
1092
1093   /* See if there is any language-specific reason it cannot be
1094      inlined.  (It is important that this hook be called early because
1095      in C++ it may result in template instantiation.)
1096      If the function is not inlinable for language-specific reasons,
1097      it is left up to the langhook to explain why.  */
1098   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1099
1100   /* If we don't have the function body available, we can't inline it.
1101      However, this should not be recorded since we also get here for
1102      forward declared inline functions.  Therefore, return at once.  */
1103   if (!DECL_SAVED_TREE (fn))
1104     return false;
1105
1106   /* If we're not inlining at all, then we cannot inline this function.  */
1107   else if (!flag_inline_trees)
1108     inlinable = false;
1109
1110   /* Only try to inline functions if DECL_INLINE is set.  This should be
1111      true for all functions declared `inline', and for all other functions
1112      as well with -finline-functions.
1113
1114      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1115      it's the front-end that must set DECL_INLINE in this case, because
1116      dwarf2out loses if a function that does not have DECL_INLINE set is
1117      inlined anyway.  That is why we have both DECL_INLINE and
1118      DECL_DECLARED_INLINE_P.  */
1119   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1120             here should be redundant.  */
1121   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1122     inlinable = false;
1123
1124   else if (inline_forbidden_p (fn))
1125     {
1126       /* See if we should warn about uninlinable functions.  Previously,
1127          some of these warnings would be issued while trying to expand
1128          the function inline, but that would cause multiple warnings
1129          about functions that would for example call alloca.  But since
1130          this a property of the function, just one warning is enough.
1131          As a bonus we can now give more details about the reason why a
1132          function is not inlinable.
1133          We only warn for functions declared `inline' by the user.  */
1134       bool do_warning = (warn_inline
1135                          && DECL_INLINE (fn)
1136                          && DECL_DECLARED_INLINE_P (fn)
1137                          && !DECL_IN_SYSTEM_HEADER (fn));
1138
1139       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1140         sorry (inline_forbidden_reason, fn, fn);
1141       else if (do_warning)
1142         warning (inline_forbidden_reason, fn, fn);
1143
1144       inlinable = false;
1145     }
1146
1147   /* Squirrel away the result so that we don't have to check again.  */
1148   DECL_UNINLINABLE (fn) = !inlinable;
1149
1150   return inlinable;
1151 }
1152
1153 /* Used by estimate_num_insns.  Estimate number of instructions seen
1154    by given statement.  */
1155
1156 static tree
1157 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1158 {
1159   int *count = data;
1160   tree x = *tp;
1161
1162   if (IS_TYPE_OR_DECL_P (x))
1163     {
1164       *walk_subtrees = 0;
1165       return NULL;
1166     }
1167   /* Assume that constants and references counts nothing.  These should
1168      be majorized by amount of operations among them we count later
1169      and are common target of CSE and similar optimizations.  */
1170   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1171     return NULL;
1172
1173   switch (TREE_CODE (x))
1174     {
1175     /* Containers have no cost.  */
1176     case TREE_LIST:
1177     case TREE_VEC:
1178     case BLOCK:
1179     case COMPONENT_REF:
1180     case BIT_FIELD_REF:
1181     case INDIRECT_REF:
1182     case ARRAY_REF:
1183     case ARRAY_RANGE_REF:
1184     case OBJ_TYPE_REF:
1185     case EXC_PTR_EXPR: /* ??? */
1186     case FILTER_EXPR: /* ??? */
1187     case COMPOUND_EXPR:
1188     case BIND_EXPR:
1189     case LABELED_BLOCK_EXPR:
1190     case WITH_CLEANUP_EXPR:
1191     case NOP_EXPR:
1192     case VIEW_CONVERT_EXPR:
1193     case SAVE_EXPR:
1194     case ADDR_EXPR:
1195     case COMPLEX_EXPR:
1196     case EXIT_BLOCK_EXPR:
1197     case CASE_LABEL_EXPR:
1198     case SSA_NAME:
1199     case CATCH_EXPR:
1200     case EH_FILTER_EXPR:
1201     case STATEMENT_LIST:
1202     case ERROR_MARK:
1203     case NON_LVALUE_EXPR:
1204     case FDESC_EXPR:
1205     case VA_ARG_EXPR:
1206     case TRY_CATCH_EXPR:
1207     case TRY_FINALLY_EXPR:
1208     case LABEL_EXPR:
1209     case GOTO_EXPR:
1210     case RETURN_EXPR:
1211     case EXIT_EXPR:
1212     case LOOP_EXPR:
1213     case PHI_NODE:
1214     case WITH_SIZE_EXPR:
1215       break;
1216
1217     /* We don't account constants for now.  Assume that the cost is amortized
1218        by operations that do use them.  We may re-consider this decision once
1219        we are able to optimize the tree before estimating it's size and break
1220        out static initializers.  */
1221     case IDENTIFIER_NODE:
1222     case INTEGER_CST:
1223     case REAL_CST:
1224     case COMPLEX_CST:
1225     case VECTOR_CST:
1226     case STRING_CST:
1227       *walk_subtrees = 0;
1228       return NULL;
1229
1230     /* Recognize assignments of large structures and constructors of
1231        big arrays.  */
1232     case INIT_EXPR:
1233     case MODIFY_EXPR:
1234       x = TREE_OPERAND (x, 0);
1235       /* FALLTHRU */
1236     case TARGET_EXPR:
1237     case CONSTRUCTOR:
1238       {
1239         HOST_WIDE_INT size;
1240
1241         size = int_size_in_bytes (TREE_TYPE (x));
1242
1243         if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1244           *count += 10;
1245         else
1246           *count += ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1247       }
1248       break;
1249
1250       /* Assign cost of 1 to usual operations.
1251          ??? We may consider mapping RTL costs to this.  */
1252     case COND_EXPR:
1253
1254     case PLUS_EXPR:
1255     case MINUS_EXPR:
1256     case MULT_EXPR:
1257
1258     case FIX_TRUNC_EXPR:
1259     case FIX_CEIL_EXPR:
1260     case FIX_FLOOR_EXPR:
1261     case FIX_ROUND_EXPR:
1262
1263     case NEGATE_EXPR:
1264     case FLOAT_EXPR:
1265     case MIN_EXPR:
1266     case MAX_EXPR:
1267     case ABS_EXPR:
1268
1269     case LSHIFT_EXPR:
1270     case RSHIFT_EXPR:
1271     case LROTATE_EXPR:
1272     case RROTATE_EXPR:
1273
1274     case BIT_IOR_EXPR:
1275     case BIT_XOR_EXPR:
1276     case BIT_AND_EXPR:
1277     case BIT_NOT_EXPR:
1278
1279     case TRUTH_ANDIF_EXPR:
1280     case TRUTH_ORIF_EXPR:
1281     case TRUTH_AND_EXPR:
1282     case TRUTH_OR_EXPR:
1283     case TRUTH_XOR_EXPR:
1284     case TRUTH_NOT_EXPR:
1285
1286     case LT_EXPR:
1287     case LE_EXPR:
1288     case GT_EXPR:
1289     case GE_EXPR:
1290     case EQ_EXPR:
1291     case NE_EXPR:
1292     case ORDERED_EXPR:
1293     case UNORDERED_EXPR:
1294
1295     case UNLT_EXPR:
1296     case UNLE_EXPR:
1297     case UNGT_EXPR:
1298     case UNGE_EXPR:
1299     case UNEQ_EXPR:
1300     case LTGT_EXPR:
1301
1302     case CONVERT_EXPR:
1303
1304     case CONJ_EXPR:
1305
1306     case PREDECREMENT_EXPR:
1307     case PREINCREMENT_EXPR:
1308     case POSTDECREMENT_EXPR:
1309     case POSTINCREMENT_EXPR:
1310
1311     case SWITCH_EXPR:
1312
1313     case ASM_EXPR:
1314
1315     case RESX_EXPR:
1316       *count += 1;
1317       break;
1318
1319     /* Few special cases of expensive operations.  This is useful
1320        to avoid inlining on functions having too many of these.  */
1321     case TRUNC_DIV_EXPR:
1322     case CEIL_DIV_EXPR:
1323     case FLOOR_DIV_EXPR:
1324     case ROUND_DIV_EXPR:
1325     case EXACT_DIV_EXPR:
1326     case TRUNC_MOD_EXPR:
1327     case CEIL_MOD_EXPR:
1328     case FLOOR_MOD_EXPR:
1329     case ROUND_MOD_EXPR:
1330     case RDIV_EXPR:
1331       *count += 10;
1332       break;
1333     case CALL_EXPR:
1334       {
1335         tree decl = get_callee_fndecl (x);
1336
1337         if (decl && DECL_BUILT_IN (decl))
1338           switch (DECL_FUNCTION_CODE (decl))
1339             {
1340             case BUILT_IN_CONSTANT_P:
1341               *walk_subtrees = 0;
1342               return NULL_TREE;
1343             case BUILT_IN_EXPECT:
1344               return NULL_TREE;
1345             default:
1346               break;
1347             }
1348         *count += 10;
1349         break;
1350       }
1351     default:
1352       /* Abort here se we know we don't miss any nodes.  */
1353       gcc_unreachable ();
1354     }
1355   return NULL;
1356 }
1357
1358 /* Estimate number of instructions that will be created by expanding EXPR.  */
1359
1360 int
1361 estimate_num_insns (tree expr)
1362 {
1363   int num = 0;
1364   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1365   return num;
1366 }
1367
1368 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1369
1370 static tree
1371 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1372 {
1373   inline_data *id;
1374   tree t;
1375   tree expr;
1376   tree stmt;
1377   tree use_retvar;
1378   tree decl;
1379   tree fn;
1380   tree arg_inits;
1381   tree *inlined_body;
1382   splay_tree st;
1383   tree args;
1384   tree return_slot_addr;
1385   tree modify_dest;
1386   location_t saved_location;
1387   struct cgraph_edge *edge;
1388   const char *reason;
1389
1390   /* See what we've got.  */
1391   id = (inline_data *) data;
1392   t = *tp;
1393
1394   /* Set input_location here so we get the right instantiation context
1395      if we call instantiate_decl from inlinable_function_p.  */
1396   saved_location = input_location;
1397   if (EXPR_HAS_LOCATION (t))
1398     input_location = EXPR_LOCATION (t);
1399
1400   /* Recurse, but letting recursive invocations know that we are
1401      inside the body of a TARGET_EXPR.  */
1402   if (TREE_CODE (*tp) == TARGET_EXPR)
1403     {
1404 #if 0
1405       int i, len = first_rtl_op (TARGET_EXPR);
1406
1407       /* We're walking our own subtrees.  */
1408       *walk_subtrees = 0;
1409
1410       /* Actually walk over them.  This loop is the body of
1411          walk_trees, omitting the case where the TARGET_EXPR
1412          itself is handled.  */
1413       for (i = 0; i < len; ++i)
1414         {
1415           if (i == 2)
1416             ++id->in_target_cleanup_p;
1417           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1418                      id->tree_pruner);
1419           if (i == 2)
1420             --id->in_target_cleanup_p;
1421         }
1422
1423       goto egress;
1424 #endif
1425     }
1426
1427   if (TYPE_P (t))
1428     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1429        them should not be expanded.  This can happen if the type is a
1430        dynamic array type, for example.  */
1431     *walk_subtrees = 0;
1432
1433   /* From here on, we're only interested in CALL_EXPRs.  */
1434   if (TREE_CODE (t) != CALL_EXPR)
1435     goto egress;
1436
1437   /* First, see if we can figure out what function is being called.
1438      If we cannot, then there is no hope of inlining the function.  */
1439   fn = get_callee_fndecl (t);
1440   if (!fn)
1441     goto egress;
1442
1443   /* Turn forward declarations into real ones.  */
1444   fn = cgraph_node (fn)->decl;
1445
1446   /* If fn is a declaration of a function in a nested scope that was
1447      globally declared inline, we don't set its DECL_INITIAL.
1448      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1449      C++ front-end uses it for cdtors to refer to their internal
1450      declarations, that are not real functions.  Fortunately those
1451      don't have trees to be saved, so we can tell by checking their
1452      DECL_SAVED_TREE.  */
1453   if (! DECL_INITIAL (fn)
1454       && DECL_ABSTRACT_ORIGIN (fn)
1455       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1456     fn = DECL_ABSTRACT_ORIGIN (fn);
1457
1458   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1459      Kill this check once this is fixed.  */
1460   if (!id->current_node->analyzed)
1461     goto egress;
1462
1463   edge = cgraph_edge (id->current_node, t);
1464
1465   /* Constant propagation on argument done during previous inlining
1466      may create new direct call.  Produce an edge for it.  */
1467   if (!edge)
1468     {
1469       struct cgraph_node *dest = cgraph_node (fn);
1470
1471       /* We have missing edge in the callgraph.  This can happen in one case
1472          where previous inlining turned indirect call into direct call by
1473          constant propagating arguments.  In all other cases we hit a bug
1474          (incorrect node sharing is most common reason for missing edges.  */
1475       gcc_assert (dest->needed || flag_unit_at_a_time);
1476       cgraph_create_edge (id->node, dest, t)->inline_failed
1477         = N_("originally indirect function call not considered for inlining");
1478       goto egress;
1479     }
1480
1481   /* Don't try to inline functions that are not well-suited to
1482      inlining.  */
1483   if (!cgraph_inline_p (edge, &reason))
1484     {
1485       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1486         {
1487           sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1488           sorry ("called from here");
1489         }
1490       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1491                && !DECL_IN_SYSTEM_HEADER (fn)
1492                && strlen (reason))
1493         {
1494           warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1495           warning ("called from here");
1496         }
1497       goto egress;
1498     }
1499
1500 #ifdef ENABLE_CHECKING
1501   if (edge->callee->decl != id->node->decl)
1502     verify_cgraph_node (edge->callee);
1503 #endif
1504
1505   if (! lang_hooks.tree_inlining.start_inlining (fn))
1506     goto egress;
1507
1508   /* Build a block containing code to initialize the arguments, the
1509      actual inline expansion of the body, and a label for the return
1510      statements within the function to jump to.  The type of the
1511      statement expression is the return type of the function call.  */
1512   stmt = NULL;
1513   expr = build (BIND_EXPR, void_type_node, NULL_TREE,
1514                 stmt, make_node (BLOCK));
1515   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1516
1517   /* Local declarations will be replaced by their equivalents in this
1518      map.  */
1519   st = id->decl_map;
1520   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1521                                  NULL, NULL);
1522
1523   /* Initialize the parameters.  */
1524   args = TREE_OPERAND (t, 1);
1525   return_slot_addr = NULL_TREE;
1526   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1527     {
1528       return_slot_addr = TREE_VALUE (args);
1529       args = TREE_CHAIN (args);
1530       TREE_TYPE (expr) = void_type_node;
1531     }
1532
1533   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1534                                              fn, expr);
1535   if (arg_inits)
1536     {
1537       /* Expand any inlined calls in the initializers.  Do this before we
1538          push FN on the stack of functions we are inlining; we want to
1539          inline calls to FN that appear in the initializers for the
1540          parameters.
1541
1542          Note we need to save and restore the saved tree statement iterator
1543          to avoid having it clobbered by expand_calls_inline.  */
1544       tree_stmt_iterator save_tsi;
1545
1546       save_tsi = id->tsi;
1547       expand_calls_inline (&arg_inits, id);
1548       id->tsi = save_tsi;
1549
1550       /* And add them to the tree.  */
1551       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1552     }
1553
1554   /* Record the function we are about to inline so that we can avoid
1555      recursing into it.  */
1556   VARRAY_PUSH_TREE (id->fns, fn);
1557
1558   /* Record the function we are about to inline if optimize_function
1559      has not been called on it yet and we don't have it in the list.  */
1560   if (! DECL_INLINED_FNS (fn))
1561     {
1562       int i;
1563
1564       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1565         if (VARRAY_TREE (id->inlined_fns, i) == fn)
1566           break;
1567       if (i < 0)
1568         VARRAY_PUSH_TREE (id->inlined_fns, fn);
1569     }
1570
1571   /* Return statements in the function body will be replaced by jumps
1572      to the RET_LABEL.  */
1573   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1574   DECL_ARTIFICIAL (id->ret_label) = 1;
1575   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1576   insert_decl_map (id, id->ret_label, id->ret_label);
1577
1578   gcc_assert (DECL_INITIAL (fn));
1579   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
1580
1581   /* Find the lhs to which the result of this call is assigned.  */
1582   modify_dest = tsi_stmt (id->tsi);
1583   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1584     modify_dest = TREE_OPERAND (modify_dest, 0);
1585   else
1586     modify_dest = NULL;
1587
1588   /* Declare the return variable for the function.  */
1589   decl = declare_return_variable (id, return_slot_addr,
1590                                   modify_dest, &use_retvar);
1591
1592   /* After we've initialized the parameters, we insert the body of the
1593      function itself.  */
1594   {
1595     struct cgraph_node *old_node = id->current_node;
1596
1597     id->current_node = edge->callee;
1598     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1599     id->current_node = old_node;
1600   }
1601   inlined_body = &BIND_EXPR_BODY (expr);
1602
1603   /* After the body of the function comes the RET_LABEL.  This must come
1604      before we evaluate the returned value below, because that evaluation
1605      may cause RTL to be generated.  */
1606   if (TREE_USED (id->ret_label))
1607     {
1608       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1609       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1610     }
1611
1612   /* Clean up.  */
1613   splay_tree_delete (id->decl_map);
1614   id->decl_map = st;
1615
1616   /* The new expression has side-effects if the old one did.  */
1617   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1618
1619   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1620
1621   /* If the inlined function returns a result that we care about,
1622      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1623      the call was a standalone statement and we can just replace it
1624      with the BIND_EXPR inline representation of the called function.  */
1625   if (!use_retvar || !modify_dest)
1626     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1627   else
1628     *tp = use_retvar;
1629
1630   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1631      the call if it is to a "const" function.  Thus the copy of
1632      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1633      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1634      "const" function.
1635
1636      Unfortunately, that is wrong as inlining the function can create/expose
1637      interesting side effects (such as setting of a return value).
1638
1639      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1640      the toplevel expression.  */
1641   recalculate_side_effects (expr);
1642
1643   /* Update callgraph if needed.  */
1644   cgraph_remove_node (edge->callee);
1645
1646   /* Recurse into the body of the just inlined function.  */
1647   expand_calls_inline (inlined_body, id);
1648   VARRAY_POP (id->fns);
1649
1650   /* Don't walk into subtrees.  We've already handled them above.  */
1651   *walk_subtrees = 0;
1652
1653   lang_hooks.tree_inlining.end_inlining (fn);
1654
1655   /* Keep iterating.  */
1656  egress:
1657   input_location = saved_location;
1658   return NULL_TREE;
1659 }
1660
1661 static void
1662 expand_calls_inline (tree *stmt_p, inline_data *id)
1663 {
1664   tree stmt = *stmt_p;
1665   enum tree_code code = TREE_CODE (stmt);
1666   int dummy;
1667
1668   switch (code)
1669     {
1670     case STATEMENT_LIST:
1671       {
1672         tree_stmt_iterator i;
1673         tree new;
1674
1675         for (i = tsi_start (stmt); !tsi_end_p (i); )
1676           {
1677             id->tsi = i;
1678             expand_calls_inline (tsi_stmt_ptr (i), id);
1679
1680             new = tsi_stmt (i);
1681             if (TREE_CODE (new) == STATEMENT_LIST)
1682               {
1683                 tsi_link_before (&i, new, TSI_SAME_STMT);
1684                 tsi_delink (&i);
1685               }
1686             else
1687               tsi_next (&i);
1688           }
1689       }
1690       break;
1691
1692     case COND_EXPR:
1693       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1694       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1695       break;
1696
1697     case CATCH_EXPR:
1698       expand_calls_inline (&CATCH_BODY (stmt), id);
1699       break;
1700
1701     case EH_FILTER_EXPR:
1702       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1703       break;
1704
1705     case TRY_CATCH_EXPR:
1706     case TRY_FINALLY_EXPR:
1707       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1708       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1709       break;
1710
1711     case BIND_EXPR:
1712       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1713       break;
1714
1715     case COMPOUND_EXPR:
1716       /* We're gimple.  We should have gotten rid of all these.  */
1717       gcc_unreachable ();
1718
1719     case RETURN_EXPR:
1720       stmt_p = &TREE_OPERAND (stmt, 0);
1721       stmt = *stmt_p;
1722       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1723         break;
1724
1725       /* FALLTHRU */
1726
1727     case MODIFY_EXPR:
1728       stmt_p = &TREE_OPERAND (stmt, 1);
1729       stmt = *stmt_p;
1730       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1731         {
1732           stmt_p = &TREE_OPERAND (stmt, 0);
1733           stmt = *stmt_p;
1734         }
1735       if (TREE_CODE (stmt) != CALL_EXPR)
1736         break;
1737
1738       /* FALLTHRU */
1739
1740     case CALL_EXPR:
1741       expand_call_inline (stmt_p, &dummy, id);
1742       break;
1743
1744     default:
1745       break;
1746     }
1747 }
1748
1749 /* Expand calls to inline functions in the body of FN.  */
1750
1751 void
1752 optimize_inline_calls (tree fn)
1753 {
1754   inline_data id;
1755   tree prev_fn;
1756   tree ifn;
1757
1758   /* There is no point in performing inlining if errors have already
1759      occurred -- and we might crash if we try to inline invalid
1760      code.  */
1761   if (errorcount || sorrycount)
1762     return;
1763
1764   /* Clear out ID.  */
1765   memset (&id, 0, sizeof (id));
1766
1767   id.current_node = id.node = cgraph_node (fn);
1768   /* Don't allow recursion into FN.  */
1769   VARRAY_TREE_INIT (id.fns, 32, "fns");
1770   VARRAY_PUSH_TREE (id.fns, fn);
1771   /* Or any functions that aren't finished yet.  */
1772   prev_fn = NULL_TREE;
1773   if (current_function_decl)
1774     {
1775       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1776       prev_fn = current_function_decl;
1777     }
1778
1779   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1780
1781   /* Create the list of functions this call will inline.  */
1782   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1783
1784   /* Keep track of the low-water mark, i.e., the point where the first
1785      real inlining is represented in ID.FNS.  */
1786   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1787
1788   /* Replace all calls to inline functions with the bodies of those
1789      functions.  */
1790   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1791   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1792
1793   /* Clean up.  */
1794   htab_delete (id.tree_pruner);
1795   ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1796   if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1797     memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1798             VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1799   DECL_INLINED_FNS (fn) = ifn;
1800
1801 #ifdef ENABLE_CHECKING
1802     {
1803       struct cgraph_edge *e;
1804
1805       verify_cgraph_node (id.node);
1806
1807       /* Double check that we inlined everything we are supposed to inline.  */
1808       for (e = id.node->callees; e; e = e->next_callee)
1809         gcc_assert (e->inline_failed);
1810     }
1811 #endif
1812 }
1813
1814 /* FN is a function that has a complete body, and CLONE is a function whose
1815    body is to be set to a copy of FN, mapping argument declarations according
1816    to the ARG_MAP splay_tree.  */
1817
1818 void
1819 clone_body (tree clone, tree fn, void *arg_map)
1820 {
1821   inline_data id;
1822
1823   /* Clone the body, as if we were making an inline call.  But, remap the
1824      parameters in the callee to the parameters of caller.  If there's an
1825      in-charge parameter, map it to an appropriate constant.  */
1826   memset (&id, 0, sizeof (id));
1827   VARRAY_TREE_INIT (id.fns, 2, "fns");
1828   VARRAY_PUSH_TREE (id.fns, clone);
1829   VARRAY_PUSH_TREE (id.fns, fn);
1830   id.decl_map = (splay_tree)arg_map;
1831
1832   /* Cloning is treated slightly differently from inlining.  Set
1833      CLONING_P so that it's clear which operation we're performing.  */
1834   id.cloning_p = true;
1835
1836   /* Actually copy the body.  */
1837   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1838 }
1839
1840 /* Make and return duplicate of body in FN.  Put copies of DECL_ARGUMENTS
1841    in *arg_copy and of the static chain, if any, in *sc_copy.  */
1842
1843 tree
1844 save_body (tree fn, tree *arg_copy, tree *sc_copy)
1845 {
1846   inline_data id;
1847   tree body, *parg;
1848
1849   memset (&id, 0, sizeof (id));
1850   VARRAY_TREE_INIT (id.fns, 1, "fns");
1851   VARRAY_PUSH_TREE (id.fns, fn);
1852   id.node = cgraph_node (fn);
1853   id.saving_p = true;
1854   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1855   *arg_copy = DECL_ARGUMENTS (fn);
1856
1857   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1858     {
1859       tree new = copy_node (*parg);
1860
1861       lang_hooks.dup_lang_specific_decl (new);
1862       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1863       insert_decl_map (&id, *parg, new);
1864       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1865       *parg = new;
1866     }
1867
1868   *sc_copy = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1869   if (*sc_copy)
1870     {
1871       tree new = copy_node (*sc_copy);
1872
1873       lang_hooks.dup_lang_specific_decl (new);
1874       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*sc_copy);
1875       insert_decl_map (&id, *sc_copy, new);
1876       TREE_CHAIN (new) = TREE_CHAIN (*sc_copy);
1877       *sc_copy = new;
1878     }
1879
1880   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1881
1882   /* Actually copy the body.  */
1883   body = copy_body (&id);
1884
1885   /* Clean up.  */
1886   splay_tree_delete (id.decl_map);
1887   return body;
1888 }
1889
1890 #define WALK_SUBTREE(NODE)                              \
1891   do                                                    \
1892     {                                                   \
1893       result = walk_tree (&(NODE), func, data, htab);   \
1894       if (result)                                       \
1895         return result;                                  \
1896     }                                                   \
1897   while (0)
1898
1899 /* This is a subroutine of walk_tree that walks field of TYPE that are to
1900    be walked whenever a type is seen in the tree.  Rest of operands and return
1901    value are as for walk_tree.  */
1902
1903 static tree
1904 walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
1905 {
1906   tree result = NULL_TREE;
1907
1908   switch (TREE_CODE (type))
1909     {
1910     case POINTER_TYPE:
1911     case REFERENCE_TYPE:
1912       /* We have to worry about mutually recursive pointers.  These can't
1913          be written in C.  They can in Ada.  It's pathological, but
1914          there's an ACATS test (c38102a) that checks it.  Deal with this
1915          by checking if we're pointing to another pointer, that one
1916          points to another pointer, that one does too, and we have no htab.
1917          If so, get a hash table.  We check three levels deep to avoid
1918          the cost of the hash table if we don't need one.  */
1919       if (POINTER_TYPE_P (TREE_TYPE (type))
1920           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
1921           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
1922           && !htab)
1923         {
1924           result = walk_tree_without_duplicates (&TREE_TYPE (type),
1925                                                  func, data);
1926           if (result)
1927             return result;
1928
1929           break;
1930         }
1931
1932       /* ... fall through ... */
1933
1934     case COMPLEX_TYPE:
1935       WALK_SUBTREE (TREE_TYPE (type));
1936       break;
1937
1938     case METHOD_TYPE:
1939       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
1940
1941       /* Fall through.  */
1942
1943     case FUNCTION_TYPE:
1944       WALK_SUBTREE (TREE_TYPE (type));
1945       {
1946         tree arg;
1947
1948         /* We never want to walk into default arguments.  */
1949         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
1950           WALK_SUBTREE (TREE_VALUE (arg));
1951       }
1952       break;
1953
1954     case ARRAY_TYPE:
1955       /* Don't follow this nodes's type if a pointer for fear that we'll
1956          have infinite recursion.  Those types are uninteresting anyway.  */
1957       if (!POINTER_TYPE_P (TREE_TYPE (type))
1958           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
1959         WALK_SUBTREE (TREE_TYPE (type));
1960       WALK_SUBTREE (TYPE_DOMAIN (type));
1961       break;
1962
1963     case BOOLEAN_TYPE:
1964     case ENUMERAL_TYPE:
1965     case INTEGER_TYPE:
1966     case CHAR_TYPE:
1967     case REAL_TYPE:
1968       WALK_SUBTREE (TYPE_MIN_VALUE (type));
1969       WALK_SUBTREE (TYPE_MAX_VALUE (type));
1970       break;
1971
1972     case OFFSET_TYPE:
1973       WALK_SUBTREE (TREE_TYPE (type));
1974       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
1975       break;
1976
1977     default:
1978       break;
1979     }
1980
1981   return NULL_TREE;
1982 }
1983
1984 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
1985    called with the DATA and the address of each sub-tree.  If FUNC returns a
1986    non-NULL value, the traversal is aborted, and the value returned by FUNC
1987    is returned.  If HTAB is non-NULL it is used to record the nodes visited,
1988    and to avoid visiting a node more than once.  */
1989
1990 tree
1991 walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
1992 {
1993   htab_t htab = (htab_t) htab_;
1994   enum tree_code code;
1995   int walk_subtrees;
1996   tree result;
1997
1998 #define WALK_SUBTREE_TAIL(NODE)                         \
1999   do                                                    \
2000     {                                                   \
2001        tp = & (NODE);                                   \
2002        goto tail_recurse;                               \
2003     }                                                   \
2004   while (0)
2005
2006  tail_recurse:
2007   /* Skip empty subtrees.  */
2008   if (!*tp)
2009     return NULL_TREE;
2010
2011   if (htab)
2012     {
2013       void **slot;
2014
2015       /* Don't walk the same tree twice, if the user has requested
2016          that we avoid doing so.  */
2017       slot = htab_find_slot (htab, *tp, INSERT);
2018       if (*slot)
2019         return NULL_TREE;
2020       *slot = *tp;
2021     }
2022
2023   /* Call the function.  */
2024   walk_subtrees = 1;
2025   result = (*func) (tp, &walk_subtrees, data);
2026
2027   /* If we found something, return it.  */
2028   if (result)
2029     return result;
2030
2031   code = TREE_CODE (*tp);
2032
2033   /* Even if we didn't, FUNC may have decided that there was nothing
2034      interesting below this point in the tree.  */
2035   if (!walk_subtrees)
2036     {
2037       if (code == TREE_LIST)
2038         /* But we still need to check our siblings.  */
2039         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2040       else
2041         return NULL_TREE;
2042     }
2043
2044   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2045                                                    data, htab);
2046   if (result || ! walk_subtrees)
2047     return result;
2048
2049   /* If this is a DECL_EXPR, walk into various fields of the type that it's
2050      defining.  We only want to walk into these fields of a type in this
2051      case.  Note that decls get walked as part of the processing of a
2052      BIND_EXPR.
2053
2054      ??? Precisely which fields of types that we are supposed to walk in
2055      this case vs. the normal case aren't well defined.  */
2056   if (code == DECL_EXPR
2057       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
2058       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
2059     {
2060       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
2061
2062       /* Call the function for the type.  See if it returns anything or
2063          doesn't want us to continue.  If we are to continue, walk both
2064          the normal fields and those for the declaration case.  */
2065       result = (*func) (type_p, &walk_subtrees, data);
2066       if (result || !walk_subtrees)
2067         return NULL_TREE;
2068
2069       result = walk_type_fields (*type_p, func, data, htab_);
2070       if (result)
2071         return result;
2072
2073       WALK_SUBTREE (TYPE_SIZE (*type_p));
2074       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
2075
2076       /* If this is a record type, also walk the fields.  */
2077       if (TREE_CODE (*type_p) == RECORD_TYPE
2078           || TREE_CODE (*type_p) == UNION_TYPE
2079           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2080         {
2081           tree field;
2082
2083           for (field = TYPE_FIELDS (*type_p); field;
2084                field = TREE_CHAIN (field))
2085             {
2086               /* We'd like to look at the type of the field, but we can easily
2087                  get infinite recursion.  So assume it's pointed to elsewhere
2088                  in the tree.  Also, ignore things that aren't fields.  */
2089               if (TREE_CODE (field) != FIELD_DECL)
2090                 continue;
2091
2092               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
2093               WALK_SUBTREE (DECL_SIZE (field));
2094               WALK_SUBTREE (DECL_SIZE_UNIT (field));
2095               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2096                 WALK_SUBTREE (DECL_QUALIFIER (field));
2097             }
2098         }
2099     }
2100
2101   else if (code != EXIT_BLOCK_EXPR
2102            && code != SAVE_EXPR
2103            && code != BIND_EXPR
2104            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2105     {
2106       int i, len;
2107
2108       /* Walk over all the sub-trees of this operand.  */
2109       len = first_rtl_op (code);
2110       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2111          But, we only want to walk once.  */
2112       if (code == TARGET_EXPR
2113           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2114         --len;
2115
2116       /* Go through the subtrees.  We need to do this in forward order so
2117          that the scope of a FOR_EXPR is handled properly.  */
2118 #ifdef DEBUG_WALK_TREE
2119       for (i = 0; i < len; ++i)
2120         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2121 #else
2122       for (i = 0; i < len - 1; ++i)
2123         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2124
2125       if (len)
2126         {
2127           /* The common case is that we may tail recurse here.  */
2128           if (code != BIND_EXPR
2129               && !TREE_CHAIN (*tp))
2130             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
2131           else
2132             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
2133         }
2134 #endif
2135     }
2136
2137   /* If this is a type, walk the needed fields in the type.  */
2138   else if (TYPE_P (*tp))
2139     {
2140       result = walk_type_fields (*tp, func, data, htab_);
2141       if (result)
2142         return result;
2143     }
2144   else
2145     {
2146       /* Not one of the easy cases.  We must explicitly go through the
2147          children.  */
2148       switch (code)
2149         {
2150         case ERROR_MARK:
2151         case IDENTIFIER_NODE:
2152         case INTEGER_CST:
2153         case REAL_CST:
2154         case VECTOR_CST:
2155         case STRING_CST:
2156         case BLOCK:
2157         case PLACEHOLDER_EXPR:
2158         case SSA_NAME:
2159         case FIELD_DECL:
2160         case RESULT_DECL:
2161           /* None of thse have subtrees other than those already walked
2162              above.  */
2163           break;
2164
2165         case TREE_LIST:
2166           WALK_SUBTREE (TREE_VALUE (*tp));
2167           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2168           break;
2169
2170         case TREE_VEC:
2171           {
2172             int len = TREE_VEC_LENGTH (*tp);
2173
2174             if (len == 0)
2175               break;
2176
2177             /* Walk all elements but the first.  */
2178             while (--len)
2179               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2180
2181             /* Now walk the first one as a tail call.  */
2182             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2183           }
2184
2185         case COMPLEX_CST:
2186           WALK_SUBTREE (TREE_REALPART (*tp));
2187           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2188
2189         case CONSTRUCTOR:
2190           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2191
2192         case EXIT_BLOCK_EXPR:
2193           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
2194
2195         case SAVE_EXPR:
2196           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2197
2198         case BIND_EXPR:
2199           {
2200             tree decl;
2201             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2202               {
2203                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2204                    into declarations that are just mentioned, rather than
2205                    declared; they don't really belong to this part of the tree.
2206                    And, we can see cycles: the initializer for a declaration
2207                    can refer to the declaration itself.  */
2208                 WALK_SUBTREE (DECL_INITIAL (decl));
2209                 WALK_SUBTREE (DECL_SIZE (decl));
2210                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2211               }
2212             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2213           }
2214
2215         case STATEMENT_LIST:
2216           {
2217             tree_stmt_iterator i;
2218             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2219               WALK_SUBTREE (*tsi_stmt_ptr (i));
2220           }
2221           break;
2222
2223         default:
2224           /* ??? This could be a language-defined node.  We really should make
2225              a hook for it, but right now just ignore it.  */
2226           break;
2227         }
2228     }
2229
2230   /* We didn't find what we were looking for.  */
2231   return NULL_TREE;
2232
2233 #undef WALK_SUBTREE
2234 #undef WALK_SUBTREE_TAIL
2235 }
2236
2237 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
2238
2239 tree
2240 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2241 {
2242   tree result;
2243   htab_t htab;
2244
2245   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
2246   result = walk_tree (tp, func, data, htab);
2247   htab_delete (htab);
2248   return result;
2249 }
2250
2251 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2252
2253 tree
2254 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2255 {
2256   enum tree_code code = TREE_CODE (*tp);
2257
2258   /* We make copies of most nodes.  */
2259   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2260       || code == TREE_LIST
2261       || code == TREE_VEC
2262       || code == TYPE_DECL)
2263     {
2264       /* Because the chain gets clobbered when we make a copy, we save it
2265          here.  */
2266       tree chain = TREE_CHAIN (*tp);
2267       tree new;
2268
2269       /* Copy the node.  */
2270       new = copy_node (*tp);
2271
2272       /* Propagate mudflap marked-ness.  */
2273       if (flag_mudflap && mf_marked_p (*tp))
2274         mf_mark (new);
2275
2276       *tp = new;
2277
2278       /* Now, restore the chain, if appropriate.  That will cause
2279          walk_tree to walk into the chain as well.  */
2280       if (code == PARM_DECL || code == TREE_LIST)
2281         TREE_CHAIN (*tp) = chain;
2282
2283       /* For now, we don't update BLOCKs when we make copies.  So, we
2284          have to nullify all BIND_EXPRs.  */
2285       if (TREE_CODE (*tp) == BIND_EXPR)
2286         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2287     }
2288
2289   else if (TREE_CODE_CLASS (code) == tcc_type)
2290     *walk_subtrees = 0;
2291   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2292     *walk_subtrees = 0;
2293   else if (TREE_CODE_CLASS (code) == tcc_constant)
2294     *walk_subtrees = 0;
2295   else
2296     gcc_assert (code != STATEMENT_LIST);
2297   return NULL_TREE;
2298 }
2299
2300 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2301    information indicating to what new SAVE_EXPR this one should be mapped,
2302    use that one.  Otherwise, create a new node and enter it in ST.  */
2303
2304 void
2305 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2306 {
2307   splay_tree st = (splay_tree) st_;
2308   splay_tree_node n;
2309   tree t;
2310
2311   /* See if we already encountered this SAVE_EXPR.  */
2312   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2313
2314   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2315   if (!n)
2316     {
2317       t = copy_node (*tp);
2318
2319       /* Remember this SAVE_EXPR.  */
2320       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2321       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2322       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2323     }
2324   else
2325     {
2326       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2327       *walk_subtrees = 0;
2328       t = (tree) n->value;
2329     }
2330
2331   /* Replace this SAVE_EXPR with the copy.  */
2332   *tp = t;
2333 }
2334
2335 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2336    copies the declaration and enters it in the splay_tree in DATA (which is
2337    really an `inline_data *').  */
2338
2339 static tree
2340 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2341                         void *data)
2342 {
2343   inline_data *id = (inline_data *) data;
2344
2345   /* Don't walk into types.  */
2346   if (TYPE_P (*tp))
2347     *walk_subtrees = 0;
2348
2349   else if (TREE_CODE (*tp) == LABEL_EXPR)
2350     {
2351       tree decl = TREE_OPERAND (*tp, 0);
2352
2353       /* Copy the decl and remember the copy.  */
2354       insert_decl_map (id, decl,
2355                        copy_decl_for_inlining (decl, DECL_CONTEXT (decl),
2356                                                DECL_CONTEXT (decl)));
2357     }
2358
2359   return NULL_TREE;
2360 }
2361
2362 /* Perform any modifications to EXPR required when it is unsaved.  Does
2363    not recurse into EXPR's subtrees.  */
2364
2365 static void
2366 unsave_expr_1 (tree expr)
2367 {
2368   switch (TREE_CODE (expr))
2369     {
2370     case TARGET_EXPR:
2371       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2372          It's OK for this to happen if it was part of a subtree that
2373          isn't immediately expanded, such as operand 2 of another
2374          TARGET_EXPR.  */
2375       if (TREE_OPERAND (expr, 1))
2376         break;
2377
2378       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2379       TREE_OPERAND (expr, 3) = NULL_TREE;
2380       break;
2381
2382     default:
2383       break;
2384     }
2385 }
2386
2387 /* Called via walk_tree when an expression is unsaved.  Using the
2388    splay_tree pointed to by ST (which is really a `splay_tree'),
2389    remaps all local declarations to appropriate replacements.  */
2390
2391 static tree
2392 unsave_r (tree *tp, int *walk_subtrees, void *data)
2393 {
2394   inline_data *id = (inline_data *) data;
2395   splay_tree st = id->decl_map;
2396   splay_tree_node n;
2397
2398   /* Only a local declaration (variable or label).  */
2399   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2400       || TREE_CODE (*tp) == LABEL_DECL)
2401     {
2402       /* Lookup the declaration.  */
2403       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2404
2405       /* If it's there, remap it.  */
2406       if (n)
2407         *tp = (tree) n->value;
2408     }
2409
2410   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2411     copy_statement_list (tp);
2412   else if (TREE_CODE (*tp) == BIND_EXPR)
2413     copy_bind_expr (tp, walk_subtrees, id);
2414   else if (TREE_CODE (*tp) == SAVE_EXPR)
2415     remap_save_expr (tp, st, walk_subtrees);
2416   else
2417     {
2418       copy_tree_r (tp, walk_subtrees, NULL);
2419
2420       /* Do whatever unsaving is required.  */
2421       unsave_expr_1 (*tp);
2422     }
2423
2424   /* Keep iterating.  */
2425   return NULL_TREE;
2426 }
2427
2428 /* Copies everything in EXPR and replaces variables, labels
2429    and SAVE_EXPRs local to EXPR.  */
2430
2431 tree
2432 unsave_expr_now (tree expr)
2433 {
2434   inline_data id;
2435
2436   /* There's nothing to do for NULL_TREE.  */
2437   if (expr == 0)
2438     return expr;
2439
2440   /* Set up ID.  */
2441   memset (&id, 0, sizeof (id));
2442   VARRAY_TREE_INIT (id.fns, 1, "fns");
2443   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2444   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2445
2446   /* Walk the tree once to find local labels.  */
2447   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2448
2449   /* Walk the tree again, copying, remapping, and unsaving.  */
2450   walk_tree (&expr, unsave_r, &id, NULL);
2451
2452   /* Clean up.  */
2453   splay_tree_delete (id.decl_map);
2454
2455   return expr;
2456 }
2457
2458 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2459
2460 static tree
2461 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2462 {
2463   if (*tp == data)
2464     return (tree) data;
2465   else
2466     return NULL;
2467 }
2468
2469 bool
2470 debug_find_tree (tree top, tree search)
2471 {
2472   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2473 }
2474
2475 /* Declare the variables created by the inliner.  Add all the variables in
2476    VARS to BIND_EXPR.  */
2477
2478 static void
2479 declare_inline_vars (tree bind_expr, tree vars)
2480 {
2481   tree t;
2482   for (t = vars; t; t = TREE_CHAIN (t))
2483     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2484
2485   add_var_to_bind_expr (bind_expr, vars);
2486 }