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 GOTO_EXPR:
 997       t = TREE_OPERAND (node, 0);
 998
 999       /* We will not inline a function which uses computed goto.  The
1000          addresses of its local labels, which may be tucked into
1001          global storage, are of course not constant across
1002          instantiations, which causes unexpected behavior.  */
1003       if (TREE_CODE (t) != LABEL_DECL)
1004         {
1005           inline_forbidden_reason
1006             = N_("%Jfunction '%F' can never be inlined "
1007                  "because it contains a computed goto");
1008           return node;
1009         }
1010       break;
1011
1012     case LABEL_EXPR:
1013       t = TREE_OPERAND (node, 0);
1014       if (DECL_NONLOCAL (t))
1015         {
1016           /* We cannot inline a function that receives a non-local goto
1017              because we cannot remap the destination label used in the
1018              function that is performing the non-local goto.  */
1019           inline_forbidden_reason
1020             = N_("%Jfunction '%F' can never be inlined "
1021                  "because it receives a non-local goto");
1022           return node;
1023         }
1024       break;
1025
1026     case RECORD_TYPE:
1027     case UNION_TYPE:
1028       /* We cannot inline a function of the form
1029
1030            void F (int i) { struct S { int ar[i]; } s; }
1031
1032          Attempting to do so produces a catch-22.
1033          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1034          UNION_TYPE nodes, then it goes into infinite recursion on a
1035          structure containing a pointer to its own type.  If it doesn't,
1036          then the type node for S doesn't get adjusted properly when
1037          F is inlined, and we abort in find_function_data.  */
1038       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1039         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1040           {
1041             inline_forbidden_reason
1042               = N_("%Jfunction '%F' can never be inlined "
1043                    "because it uses variable sized variables");
1044             return node;
1045           }
1046
1047     default:
1048       break;
1049     }
1050
1051   return NULL_TREE;
1052 }
1053
1054 /* Return subexpression representing possible alloca call, if any.  */
1055 static tree
1056 inline_forbidden_p (tree fndecl)
1057 {
1058   location_t saved_loc = input_location;
1059   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1060                                            inline_forbidden_p_1, fndecl);
1061
1062   input_location = saved_loc;
1063   return ret;
1064 }
1065
1066 /* Returns nonzero if FN is a function that does not have any
1067    fundamental inline blocking properties.  */
1068
1069 static bool
1070 inlinable_function_p (tree fn)
1071 {
1072   bool inlinable = true;
1073
1074   /* If we've already decided this function shouldn't be inlined,
1075      there's no need to check again.  */
1076   if (DECL_UNINLINABLE (fn))
1077     return false;
1078
1079   /* See if there is any language-specific reason it cannot be
1080      inlined.  (It is important that this hook be called early because
1081      in C++ it may result in template instantiation.)
1082      If the function is not inlinable for language-specific reasons,
1083      it is left up to the langhook to explain why.  */
1084   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1085
1086   /* If we don't have the function body available, we can't inline it.
1087      However, this should not be recorded since we also get here for
1088      forward declared inline functions.  Therefore, return at once.  */
1089   if (!DECL_SAVED_TREE (fn))
1090     return false;
1091
1092   /* If we're not inlining at all, then we cannot inline this function.  */
1093   else if (!flag_inline_trees)
1094     inlinable = false;
1095
1096   /* Only try to inline functions if DECL_INLINE is set.  This should be
1097      true for all functions declared `inline', and for all other functions
1098      as well with -finline-functions.
1099
1100      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1101      it's the front-end that must set DECL_INLINE in this case, because
1102      dwarf2out loses if a function that does not have DECL_INLINE set is
1103      inlined anyway.  That is why we have both DECL_INLINE and
1104      DECL_DECLARED_INLINE_P.  */
1105   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1106             here should be redundant.  */
1107   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1108     inlinable = false;
1109
1110   else if (inline_forbidden_p (fn))
1111     {
1112       /* See if we should warn about uninlinable functions.  Previously,
1113          some of these warnings would be issued while trying to expand
1114          the function inline, but that would cause multiple warnings
1115          about functions that would for example call alloca.  But since
1116          this a property of the function, just one warning is enough.
1117          As a bonus we can now give more details about the reason why a
1118          function is not inlinable.
1119          We only warn for functions declared `inline' by the user.  */
1120       bool do_warning = (warn_inline
1121                          && DECL_INLINE (fn)
1122                          && DECL_DECLARED_INLINE_P (fn)
1123                          && !DECL_IN_SYSTEM_HEADER (fn));
1124
1125       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1126         sorry (inline_forbidden_reason, fn, fn);
1127       else if (do_warning)
1128         warning (inline_forbidden_reason, fn, fn);
1129
1130       inlinable = false;
1131     }
1132
1133   /* Squirrel away the result so that we don't have to check again.  */
1134   DECL_UNINLINABLE (fn) = !inlinable;
1135
1136   return inlinable;
1137 }
1138
1139 /* Used by estimate_num_insns.  Estimate number of instructions seen
1140    by given statement.  */
1141
1142 static tree
1143 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1144 {
1145   int *count = data;
1146   tree x = *tp;
1147
1148   if (IS_TYPE_OR_DECL_P (x))
1149     {
1150       *walk_subtrees = 0;
1151       return NULL;
1152     }
1153   /* Assume that constants and references counts nothing.  These should
1154      be majorized by amount of operations among them we count later
1155      and are common target of CSE and similar optimizations.  */
1156   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1157     return NULL;
1158
1159   switch (TREE_CODE (x))
1160     {
1161     /* Containers have no cost.  */
1162     case TREE_LIST:
1163     case TREE_VEC:
1164     case BLOCK:
1165     case COMPONENT_REF:
1166     case BIT_FIELD_REF:
1167     case INDIRECT_REF:
1168     case ARRAY_REF:
1169     case ARRAY_RANGE_REF:
1170     case OBJ_TYPE_REF:
1171     case EXC_PTR_EXPR: /* ??? */
1172     case FILTER_EXPR: /* ??? */
1173     case COMPOUND_EXPR:
1174     case BIND_EXPR:
1175     case LABELED_BLOCK_EXPR:
1176     case WITH_CLEANUP_EXPR:
1177     case NOP_EXPR:
1178     case VIEW_CONVERT_EXPR:
1179     case SAVE_EXPR:
1180     case ADDR_EXPR:
1181     case COMPLEX_EXPR:
1182     case EXIT_BLOCK_EXPR:
1183     case CASE_LABEL_EXPR:
1184     case SSA_NAME:
1185     case CATCH_EXPR:
1186     case EH_FILTER_EXPR:
1187     case STATEMENT_LIST:
1188     case ERROR_MARK:
1189     case NON_LVALUE_EXPR:
1190     case FDESC_EXPR:
1191     case VA_ARG_EXPR:
1192     case TRY_CATCH_EXPR:
1193     case TRY_FINALLY_EXPR:
1194     case LABEL_EXPR:
1195     case GOTO_EXPR:
1196     case RETURN_EXPR:
1197     case EXIT_EXPR:
1198     case LOOP_EXPR:
1199     case PHI_NODE:
1200     case WITH_SIZE_EXPR:
1201       break;
1202
1203     /* We don't account constants for now.  Assume that the cost is amortized
1204        by operations that do use them.  We may re-consider this decision once
1205        we are able to optimize the tree before estimating it's size and break
1206        out static initializers.  */
1207     case IDENTIFIER_NODE:
1208     case INTEGER_CST:
1209     case REAL_CST:
1210     case COMPLEX_CST:
1211     case VECTOR_CST:
1212     case STRING_CST:
1213       *walk_subtrees = 0;
1214       return NULL;
1215
1216     /* Recognize assignments of large structures and constructors of
1217        big arrays.  */
1218     case INIT_EXPR:
1219     case MODIFY_EXPR:
1220       x = TREE_OPERAND (x, 0);
1221       /* FALLTHRU */
1222     case TARGET_EXPR:
1223     case CONSTRUCTOR:
1224       {
1225         HOST_WIDE_INT size;
1226
1227         size = int_size_in_bytes (TREE_TYPE (x));
1228
1229         if (size < 0 || size > MOVE_MAX_PIECES * MOVE_RATIO)
1230           *count += 10;
1231         else
1232           *count += ((size + MOVE_MAX_PIECES - 1) / MOVE_MAX_PIECES);
1233       }
1234       break;
1235
1236       /* Assign cost of 1 to usual operations.
1237          ??? We may consider mapping RTL costs to this.  */
1238     case COND_EXPR:
1239
1240     case PLUS_EXPR:
1241     case MINUS_EXPR:
1242     case MULT_EXPR:
1243
1244     case FIX_TRUNC_EXPR:
1245     case FIX_CEIL_EXPR:
1246     case FIX_FLOOR_EXPR:
1247     case FIX_ROUND_EXPR:
1248
1249     case NEGATE_EXPR:
1250     case FLOAT_EXPR:
1251     case MIN_EXPR:
1252     case MAX_EXPR:
1253     case ABS_EXPR:
1254
1255     case LSHIFT_EXPR:
1256     case RSHIFT_EXPR:
1257     case LROTATE_EXPR:
1258     case RROTATE_EXPR:
1259
1260     case BIT_IOR_EXPR:
1261     case BIT_XOR_EXPR:
1262     case BIT_AND_EXPR:
1263     case BIT_NOT_EXPR:
1264
1265     case TRUTH_ANDIF_EXPR:
1266     case TRUTH_ORIF_EXPR:
1267     case TRUTH_AND_EXPR:
1268     case TRUTH_OR_EXPR:
1269     case TRUTH_XOR_EXPR:
1270     case TRUTH_NOT_EXPR:
1271
1272     case LT_EXPR:
1273     case LE_EXPR:
1274     case GT_EXPR:
1275     case GE_EXPR:
1276     case EQ_EXPR:
1277     case NE_EXPR:
1278     case ORDERED_EXPR:
1279     case UNORDERED_EXPR:
1280
1281     case UNLT_EXPR:
1282     case UNLE_EXPR:
1283     case UNGT_EXPR:
1284     case UNGE_EXPR:
1285     case UNEQ_EXPR:
1286     case LTGT_EXPR:
1287
1288     case CONVERT_EXPR:
1289
1290     case CONJ_EXPR:
1291
1292     case PREDECREMENT_EXPR:
1293     case PREINCREMENT_EXPR:
1294     case POSTDECREMENT_EXPR:
1295     case POSTINCREMENT_EXPR:
1296
1297     case SWITCH_EXPR:
1298
1299     case ASM_EXPR:
1300
1301     case RESX_EXPR:
1302       *count += 1;
1303       break;
1304
1305     /* Few special cases of expensive operations.  This is useful
1306        to avoid inlining on functions having too many of these.  */
1307     case TRUNC_DIV_EXPR:
1308     case CEIL_DIV_EXPR:
1309     case FLOOR_DIV_EXPR:
1310     case ROUND_DIV_EXPR:
1311     case EXACT_DIV_EXPR:
1312     case TRUNC_MOD_EXPR:
1313     case CEIL_MOD_EXPR:
1314     case FLOOR_MOD_EXPR:
1315     case ROUND_MOD_EXPR:
1316     case RDIV_EXPR:
1317       *count += 10;
1318       break;
1319     case CALL_EXPR:
1320       {
1321         tree decl = get_callee_fndecl (x);
1322
1323         if (decl && DECL_BUILT_IN (decl))
1324           switch (DECL_FUNCTION_CODE (decl))
1325             {
1326             case BUILT_IN_CONSTANT_P:
1327               *walk_subtrees = 0;
1328               return NULL_TREE;
1329             case BUILT_IN_EXPECT:
1330               return NULL_TREE;
1331             default:
1332               break;
1333             }
1334         *count += 10;
1335         break;
1336       }
1337     default:
1338       /* Abort here se we know we don't miss any nodes.  */
1339       gcc_unreachable ();
1340     }
1341   return NULL;
1342 }
1343
1344 /* Estimate number of instructions that will be created by expanding EXPR.  */
1345
1346 int
1347 estimate_num_insns (tree expr)
1348 {
1349   int num = 0;
1350   walk_tree_without_duplicates (&expr, estimate_num_insns_1, &num);
1351   return num;
1352 }
1353
1354 /* If *TP is a CALL_EXPR, replace it with its inline expansion.  */
1355
1356 static tree
1357 expand_call_inline (tree *tp, int *walk_subtrees, void *data)
1358 {
1359   inline_data *id;
1360   tree t;
1361   tree expr;
1362   tree stmt;
1363   tree use_retvar;
1364   tree decl;
1365   tree fn;
1366   tree arg_inits;
1367   tree *inlined_body;
1368   splay_tree st;
1369   tree args;
1370   tree return_slot_addr;
1371   tree modify_dest;
1372   location_t saved_location;
1373   struct cgraph_edge *edge;
1374   const char *reason;
1375
1376   /* See what we've got.  */
1377   id = (inline_data *) data;
1378   t = *tp;
1379
1380   /* Set input_location here so we get the right instantiation context
1381      if we call instantiate_decl from inlinable_function_p.  */
1382   saved_location = input_location;
1383   if (EXPR_HAS_LOCATION (t))
1384     input_location = EXPR_LOCATION (t);
1385
1386   /* Recurse, but letting recursive invocations know that we are
1387      inside the body of a TARGET_EXPR.  */
1388   if (TREE_CODE (*tp) == TARGET_EXPR)
1389     {
1390 #if 0
1391       int i, len = first_rtl_op (TARGET_EXPR);
1392
1393       /* We're walking our own subtrees.  */
1394       *walk_subtrees = 0;
1395
1396       /* Actually walk over them.  This loop is the body of
1397          walk_trees, omitting the case where the TARGET_EXPR
1398          itself is handled.  */
1399       for (i = 0; i < len; ++i)
1400         {
1401           if (i == 2)
1402             ++id->in_target_cleanup_p;
1403           walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
1404                      id->tree_pruner);
1405           if (i == 2)
1406             --id->in_target_cleanup_p;
1407         }
1408
1409       goto egress;
1410 #endif
1411     }
1412
1413   if (TYPE_P (t))
1414     /* Because types were not copied in copy_body, CALL_EXPRs beneath
1415        them should not be expanded.  This can happen if the type is a
1416        dynamic array type, for example.  */
1417     *walk_subtrees = 0;
1418
1419   /* From here on, we're only interested in CALL_EXPRs.  */
1420   if (TREE_CODE (t) != CALL_EXPR)
1421     goto egress;
1422
1423   /* First, see if we can figure out what function is being called.
1424      If we cannot, then there is no hope of inlining the function.  */
1425   fn = get_callee_fndecl (t);
1426   if (!fn)
1427     goto egress;
1428
1429   /* Turn forward declarations into real ones.  */
1430   fn = cgraph_node (fn)->decl;
1431
1432   /* If fn is a declaration of a function in a nested scope that was
1433      globally declared inline, we don't set its DECL_INITIAL.
1434      However, we can't blindly follow DECL_ABSTRACT_ORIGIN because the
1435      C++ front-end uses it for cdtors to refer to their internal
1436      declarations, that are not real functions.  Fortunately those
1437      don't have trees to be saved, so we can tell by checking their
1438      DECL_SAVED_TREE.  */
1439   if (! DECL_INITIAL (fn)
1440       && DECL_ABSTRACT_ORIGIN (fn)
1441       && DECL_SAVED_TREE (DECL_ABSTRACT_ORIGIN (fn)))
1442     fn = DECL_ABSTRACT_ORIGIN (fn);
1443
1444   /* Objective C and fortran still calls tree_rest_of_compilation directly.
1445      Kill this check once this is fixed.  */
1446   if (!id->current_node->analyzed)
1447     goto egress;
1448
1449   edge = cgraph_edge (id->current_node, t);
1450
1451   /* Constant propagation on argument done during previous inlining
1452      may create new direct call.  Produce an edge for it.  */
1453   if (!edge)
1454     {
1455       struct cgraph_node *dest = cgraph_node (fn);
1456
1457       /* We have missing edge in the callgraph.  This can happen in one case
1458          where previous inlining turned indirect call into direct call by
1459          constant propagating arguments.  In all other cases we hit a bug
1460          (incorrect node sharing is most common reason for missing edges.  */
1461       gcc_assert (dest->needed || !flag_unit_at_a_time);
1462       cgraph_create_edge (id->node, dest, t)->inline_failed
1463         = N_("originally indirect function call not considered for inlining");
1464       goto egress;
1465     }
1466
1467   /* Don't try to inline functions that are not well-suited to
1468      inlining.  */
1469   if (!cgraph_inline_p (edge, &reason))
1470     {
1471       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1472         {
1473           sorry ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1474           sorry ("called from here");
1475         }
1476       else if (warn_inline && DECL_DECLARED_INLINE_P (fn)
1477                && !DECL_IN_SYSTEM_HEADER (fn)
1478                && strlen (reason)
1479                && !lookup_attribute ("noinline", DECL_ATTRIBUTES (fn)))
1480         {
1481           warning ("%Jinlining failed in call to '%F': %s", fn, fn, reason);
1482           warning ("called from here");
1483         }
1484       goto egress;
1485     }
1486
1487 #ifdef ENABLE_CHECKING
1488   if (edge->callee->decl != id->node->decl)
1489     verify_cgraph_node (edge->callee);
1490 #endif
1491
1492   if (! lang_hooks.tree_inlining.start_inlining (fn))
1493     goto egress;
1494
1495   /* Build a block containing code to initialize the arguments, the
1496      actual inline expansion of the body, and a label for the return
1497      statements within the function to jump to.  The type of the
1498      statement expression is the return type of the function call.  */
1499   stmt = NULL;
1500   expr = build (BIND_EXPR, void_type_node, NULL_TREE,
1501                 stmt, make_node (BLOCK));
1502   BLOCK_ABSTRACT_ORIGIN (BIND_EXPR_BLOCK (expr)) = fn;
1503
1504   /* Local declarations will be replaced by their equivalents in this
1505      map.  */
1506   st = id->decl_map;
1507   id->decl_map = splay_tree_new (splay_tree_compare_pointers,
1508                                  NULL, NULL);
1509
1510   /* Initialize the parameters.  */
1511   args = TREE_OPERAND (t, 1);
1512   return_slot_addr = NULL_TREE;
1513   if (CALL_EXPR_HAS_RETURN_SLOT_ADDR (t))
1514     {
1515       return_slot_addr = TREE_VALUE (args);
1516       args = TREE_CHAIN (args);
1517       TREE_TYPE (expr) = void_type_node;
1518     }
1519
1520   arg_inits = initialize_inlined_parameters (id, args, TREE_OPERAND (t, 2),
1521                                              fn, expr);
1522   if (arg_inits)
1523     {
1524       /* Expand any inlined calls in the initializers.  Do this before we
1525          push FN on the stack of functions we are inlining; we want to
1526          inline calls to FN that appear in the initializers for the
1527          parameters.
1528
1529          Note we need to save and restore the saved tree statement iterator
1530          to avoid having it clobbered by expand_calls_inline.  */
1531       tree_stmt_iterator save_tsi;
1532
1533       save_tsi = id->tsi;
1534       expand_calls_inline (&arg_inits, id);
1535       id->tsi = save_tsi;
1536
1537       /* And add them to the tree.  */
1538       append_to_statement_list (arg_inits, &BIND_EXPR_BODY (expr));
1539     }
1540
1541   /* Record the function we are about to inline so that we can avoid
1542      recursing into it.  */
1543   VARRAY_PUSH_TREE (id->fns, fn);
1544
1545   /* Record the function we are about to inline if optimize_function
1546      has not been called on it yet and we don't have it in the list.  */
1547   if (! DECL_INLINED_FNS (fn))
1548     {
1549       int i;
1550
1551       for (i = VARRAY_ACTIVE_SIZE (id->inlined_fns) - 1; i >= 0; i--)
1552         if (VARRAY_TREE (id->inlined_fns, i) == fn)
1553           break;
1554       if (i < 0)
1555         VARRAY_PUSH_TREE (id->inlined_fns, fn);
1556     }
1557
1558   /* Return statements in the function body will be replaced by jumps
1559      to the RET_LABEL.  */
1560   id->ret_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
1561   DECL_ARTIFICIAL (id->ret_label) = 1;
1562   DECL_CONTEXT (id->ret_label) = VARRAY_TREE (id->fns, 0);
1563   insert_decl_map (id, id->ret_label, id->ret_label);
1564
1565   gcc_assert (DECL_INITIAL (fn));
1566   gcc_assert (TREE_CODE (DECL_INITIAL (fn)) == BLOCK);
1567
1568   /* Find the lhs to which the result of this call is assigned.  */
1569   modify_dest = tsi_stmt (id->tsi);
1570   if (TREE_CODE (modify_dest) == MODIFY_EXPR)
1571     modify_dest = TREE_OPERAND (modify_dest, 0);
1572   else
1573     modify_dest = NULL;
1574
1575   /* Declare the return variable for the function.  */
1576   decl = declare_return_variable (id, return_slot_addr,
1577                                   modify_dest, &use_retvar);
1578
1579   /* After we've initialized the parameters, we insert the body of the
1580      function itself.  */
1581   {
1582     struct cgraph_node *old_node = id->current_node;
1583
1584     id->current_node = edge->callee;
1585     append_to_statement_list (copy_body (id), &BIND_EXPR_BODY (expr));
1586     id->current_node = old_node;
1587   }
1588   inlined_body = &BIND_EXPR_BODY (expr);
1589
1590   /* After the body of the function comes the RET_LABEL.  This must come
1591      before we evaluate the returned value below, because that evaluation
1592      may cause RTL to be generated.  */
1593   if (TREE_USED (id->ret_label))
1594     {
1595       tree label = build1 (LABEL_EXPR, void_type_node, id->ret_label);
1596       append_to_statement_list (label, &BIND_EXPR_BODY (expr));
1597     }
1598
1599   /* Clean up.  */
1600   splay_tree_delete (id->decl_map);
1601   id->decl_map = st;
1602
1603   /* The new expression has side-effects if the old one did.  */
1604   TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (t);
1605
1606   tsi_link_before (&id->tsi, expr, TSI_SAME_STMT);
1607
1608   /* If the inlined function returns a result that we care about,
1609      then we're going to need to splice in a MODIFY_EXPR.  Otherwise
1610      the call was a standalone statement and we can just replace it
1611      with the BIND_EXPR inline representation of the called function.  */
1612   if (!use_retvar || !modify_dest)
1613     *tsi_stmt_ptr (id->tsi) = build_empty_stmt ();
1614   else
1615     *tp = use_retvar;
1616
1617   /* When we gimplify a function call, we may clear TREE_SIDE_EFFECTS on
1618      the call if it is to a "const" function.  Thus the copy of
1619      TREE_SIDE_EFFECTS from the CALL_EXPR to the BIND_EXPR above with
1620      result in TREE_SIDE_EFFECTS not being set for the inlined copy of a
1621      "const" function.
1622
1623      Unfortunately, that is wrong as inlining the function can create/expose
1624      interesting side effects (such as setting of a return value).
1625
1626      The easiest solution is to simply recalculate TREE_SIDE_EFFECTS for
1627      the toplevel expression.  */
1628   recalculate_side_effects (expr);
1629
1630   /* Update callgraph if needed.  */
1631   cgraph_remove_node (edge->callee);
1632
1633   /* Recurse into the body of the just inlined function.  */
1634   expand_calls_inline (inlined_body, id);
1635   VARRAY_POP (id->fns);
1636
1637   /* Don't walk into subtrees.  We've already handled them above.  */
1638   *walk_subtrees = 0;
1639
1640   lang_hooks.tree_inlining.end_inlining (fn);
1641
1642   /* Keep iterating.  */
1643  egress:
1644   input_location = saved_location;
1645   return NULL_TREE;
1646 }
1647
1648 static void
1649 expand_calls_inline (tree *stmt_p, inline_data *id)
1650 {
1651   tree stmt = *stmt_p;
1652   enum tree_code code = TREE_CODE (stmt);
1653   int dummy;
1654
1655   switch (code)
1656     {
1657     case STATEMENT_LIST:
1658       {
1659         tree_stmt_iterator i;
1660         tree new;
1661
1662         for (i = tsi_start (stmt); !tsi_end_p (i); )
1663           {
1664             id->tsi = i;
1665             expand_calls_inline (tsi_stmt_ptr (i), id);
1666
1667             new = tsi_stmt (i);
1668             if (TREE_CODE (new) == STATEMENT_LIST)
1669               {
1670                 tsi_link_before (&i, new, TSI_SAME_STMT);
1671                 tsi_delink (&i);
1672               }
1673             else
1674               tsi_next (&i);
1675           }
1676       }
1677       break;
1678
1679     case COND_EXPR:
1680       expand_calls_inline (&COND_EXPR_THEN (stmt), id);
1681       expand_calls_inline (&COND_EXPR_ELSE (stmt), id);
1682       break;
1683
1684     case CATCH_EXPR:
1685       expand_calls_inline (&CATCH_BODY (stmt), id);
1686       break;
1687
1688     case EH_FILTER_EXPR:
1689       expand_calls_inline (&EH_FILTER_FAILURE (stmt), id);
1690       break;
1691
1692     case TRY_CATCH_EXPR:
1693     case TRY_FINALLY_EXPR:
1694       expand_calls_inline (&TREE_OPERAND (stmt, 0), id);
1695       expand_calls_inline (&TREE_OPERAND (stmt, 1), id);
1696       break;
1697
1698     case BIND_EXPR:
1699       expand_calls_inline (&BIND_EXPR_BODY (stmt), id);
1700       break;
1701
1702     case COMPOUND_EXPR:
1703       /* We're gimple.  We should have gotten rid of all these.  */
1704       gcc_unreachable ();
1705
1706     case RETURN_EXPR:
1707       stmt_p = &TREE_OPERAND (stmt, 0);
1708       stmt = *stmt_p;
1709       if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
1710         break;
1711
1712       /* FALLTHRU */
1713
1714     case MODIFY_EXPR:
1715       stmt_p = &TREE_OPERAND (stmt, 1);
1716       stmt = *stmt_p;
1717       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
1718         {
1719           stmt_p = &TREE_OPERAND (stmt, 0);
1720           stmt = *stmt_p;
1721         }
1722       if (TREE_CODE (stmt) != CALL_EXPR)
1723         break;
1724
1725       /* FALLTHRU */
1726
1727     case CALL_EXPR:
1728       expand_call_inline (stmt_p, &dummy, id);
1729       break;
1730
1731     default:
1732       break;
1733     }
1734 }
1735
1736 /* Expand calls to inline functions in the body of FN.  */
1737
1738 void
1739 optimize_inline_calls (tree fn)
1740 {
1741   inline_data id;
1742   tree prev_fn;
1743   tree ifn;
1744
1745   /* There is no point in performing inlining if errors have already
1746      occurred -- and we might crash if we try to inline invalid
1747      code.  */
1748   if (errorcount || sorrycount)
1749     return;
1750
1751   /* Clear out ID.  */
1752   memset (&id, 0, sizeof (id));
1753
1754   id.current_node = id.node = cgraph_node (fn);
1755   /* Don't allow recursion into FN.  */
1756   VARRAY_TREE_INIT (id.fns, 32, "fns");
1757   VARRAY_PUSH_TREE (id.fns, fn);
1758   /* Or any functions that aren't finished yet.  */
1759   prev_fn = NULL_TREE;
1760   if (current_function_decl)
1761     {
1762       VARRAY_PUSH_TREE (id.fns, current_function_decl);
1763       prev_fn = current_function_decl;
1764     }
1765
1766   prev_fn = lang_hooks.tree_inlining.add_pending_fn_decls (&id.fns, prev_fn);
1767
1768   /* Create the list of functions this call will inline.  */
1769   VARRAY_TREE_INIT (id.inlined_fns, 32, "inlined_fns");
1770
1771   /* Keep track of the low-water mark, i.e., the point where the first
1772      real inlining is represented in ID.FNS.  */
1773   id.first_inlined_fn = VARRAY_ACTIVE_SIZE (id.fns);
1774
1775   /* Replace all calls to inline functions with the bodies of those
1776      functions.  */
1777   id.tree_pruner = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1778   expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
1779
1780   /* Clean up.  */
1781   htab_delete (id.tree_pruner);
1782   ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (id.inlined_fns));
1783   if (VARRAY_ACTIVE_SIZE (id.inlined_fns))
1784     memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (id.inlined_fns, 0),
1785             VARRAY_ACTIVE_SIZE (id.inlined_fns) * sizeof (tree));
1786   DECL_INLINED_FNS (fn) = ifn;
1787
1788 #ifdef ENABLE_CHECKING
1789     {
1790       struct cgraph_edge *e;
1791
1792       verify_cgraph_node (id.node);
1793
1794       /* Double check that we inlined everything we are supposed to inline.  */
1795       for (e = id.node->callees; e; e = e->next_callee)
1796         gcc_assert (e->inline_failed);
1797     }
1798 #endif
1799 }
1800
1801 /* FN is a function that has a complete body, and CLONE is a function whose
1802    body is to be set to a copy of FN, mapping argument declarations according
1803    to the ARG_MAP splay_tree.  */
1804
1805 void
1806 clone_body (tree clone, tree fn, void *arg_map)
1807 {
1808   inline_data id;
1809
1810   /* Clone the body, as if we were making an inline call.  But, remap the
1811      parameters in the callee to the parameters of caller.  If there's an
1812      in-charge parameter, map it to an appropriate constant.  */
1813   memset (&id, 0, sizeof (id));
1814   VARRAY_TREE_INIT (id.fns, 2, "fns");
1815   VARRAY_PUSH_TREE (id.fns, clone);
1816   VARRAY_PUSH_TREE (id.fns, fn);
1817   id.decl_map = (splay_tree)arg_map;
1818
1819   /* Cloning is treated slightly differently from inlining.  Set
1820      CLONING_P so that it's clear which operation we're performing.  */
1821   id.cloning_p = true;
1822
1823   /* Actually copy the body.  */
1824   append_to_statement_list_force (copy_body (&id), &DECL_SAVED_TREE (clone));
1825 }
1826
1827 /* Make and return duplicate of body in FN.  Put copies of DECL_ARGUMENTS
1828    in *arg_copy and of the static chain, if any, in *sc_copy.  */
1829
1830 tree
1831 save_body (tree fn, tree *arg_copy, tree *sc_copy)
1832 {
1833   inline_data id;
1834   tree body, *parg;
1835
1836   memset (&id, 0, sizeof (id));
1837   VARRAY_TREE_INIT (id.fns, 1, "fns");
1838   VARRAY_PUSH_TREE (id.fns, fn);
1839   id.node = cgraph_node (fn);
1840   id.saving_p = true;
1841   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
1842   *arg_copy = DECL_ARGUMENTS (fn);
1843
1844   for (parg = arg_copy; *parg; parg = &TREE_CHAIN (*parg))
1845     {
1846       tree new = copy_node (*parg);
1847
1848       lang_hooks.dup_lang_specific_decl (new);
1849       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*parg);
1850       insert_decl_map (&id, *parg, new);
1851       TREE_CHAIN (new) = TREE_CHAIN (*parg);
1852       *parg = new;
1853     }
1854
1855   *sc_copy = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
1856   if (*sc_copy)
1857     {
1858       tree new = copy_node (*sc_copy);
1859
1860       lang_hooks.dup_lang_specific_decl (new);
1861       DECL_ABSTRACT_ORIGIN (new) = DECL_ORIGIN (*sc_copy);
1862       insert_decl_map (&id, *sc_copy, new);
1863       TREE_CHAIN (new) = TREE_CHAIN (*sc_copy);
1864       *sc_copy = new;
1865     }
1866
1867   insert_decl_map (&id, DECL_RESULT (fn), DECL_RESULT (fn));
1868
1869   /* Actually copy the body.  */
1870   body = copy_body (&id);
1871
1872   /* Clean up.  */
1873   splay_tree_delete (id.decl_map);
1874   return body;
1875 }
1876
1877 #define WALK_SUBTREE(NODE)                              \
1878   do                                                    \
1879     {                                                   \
1880       result = walk_tree (&(NODE), func, data, htab);   \
1881       if (result)                                       \
1882         return result;                                  \
1883     }                                                   \
1884   while (0)
1885
1886 /* This is a subroutine of walk_tree that walks field of TYPE that are to
1887    be walked whenever a type is seen in the tree.  Rest of operands and return
1888    value are as for walk_tree.  */
1889
1890 static tree
1891 walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
1892 {
1893   tree result = NULL_TREE;
1894
1895   switch (TREE_CODE (type))
1896     {
1897     case POINTER_TYPE:
1898     case REFERENCE_TYPE:
1899       /* We have to worry about mutually recursive pointers.  These can't
1900          be written in C.  They can in Ada.  It's pathological, but
1901          there's an ACATS test (c38102a) that checks it.  Deal with this
1902          by checking if we're pointing to another pointer, that one
1903          points to another pointer, that one does too, and we have no htab.
1904          If so, get a hash table.  We check three levels deep to avoid
1905          the cost of the hash table if we don't need one.  */
1906       if (POINTER_TYPE_P (TREE_TYPE (type))
1907           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
1908           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
1909           && !htab)
1910         {
1911           result = walk_tree_without_duplicates (&TREE_TYPE (type),
1912                                                  func, data);
1913           if (result)
1914             return result;
1915
1916           break;
1917         }
1918
1919       /* ... fall through ... */
1920
1921     case COMPLEX_TYPE:
1922       WALK_SUBTREE (TREE_TYPE (type));
1923       break;
1924
1925     case METHOD_TYPE:
1926       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
1927
1928       /* Fall through.  */
1929
1930     case FUNCTION_TYPE:
1931       WALK_SUBTREE (TREE_TYPE (type));
1932       {
1933         tree arg;
1934
1935         /* We never want to walk into default arguments.  */
1936         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
1937           WALK_SUBTREE (TREE_VALUE (arg));
1938       }
1939       break;
1940
1941     case ARRAY_TYPE:
1942       /* Don't follow this nodes's type if a pointer for fear that we'll
1943          have infinite recursion.  Those types are uninteresting anyway.  */
1944       if (!POINTER_TYPE_P (TREE_TYPE (type))
1945           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
1946         WALK_SUBTREE (TREE_TYPE (type));
1947       WALK_SUBTREE (TYPE_DOMAIN (type));
1948       break;
1949
1950     case BOOLEAN_TYPE:
1951     case ENUMERAL_TYPE:
1952     case INTEGER_TYPE:
1953     case CHAR_TYPE:
1954     case REAL_TYPE:
1955       WALK_SUBTREE (TYPE_MIN_VALUE (type));
1956       WALK_SUBTREE (TYPE_MAX_VALUE (type));
1957       break;
1958
1959     case OFFSET_TYPE:
1960       WALK_SUBTREE (TREE_TYPE (type));
1961       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
1962       break;
1963
1964     default:
1965       break;
1966     }
1967
1968   return NULL_TREE;
1969 }
1970
1971 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
1972    called with the DATA and the address of each sub-tree.  If FUNC returns a
1973    non-NULL value, the traversal is aborted, and the value returned by FUNC
1974    is returned.  If HTAB is non-NULL it is used to record the nodes visited,
1975    and to avoid visiting a node more than once.  */
1976
1977 tree
1978 walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
1979 {
1980   htab_t htab = (htab_t) htab_;
1981   enum tree_code code;
1982   int walk_subtrees;
1983   tree result;
1984
1985 #define WALK_SUBTREE_TAIL(NODE)                         \
1986   do                                                    \
1987     {                                                   \
1988        tp = & (NODE);                                   \
1989        goto tail_recurse;                               \
1990     }                                                   \
1991   while (0)
1992
1993  tail_recurse:
1994   /* Skip empty subtrees.  */
1995   if (!*tp)
1996     return NULL_TREE;
1997
1998   if (htab)
1999     {
2000       void **slot;
2001
2002       /* Don't walk the same tree twice, if the user has requested
2003          that we avoid doing so.  */
2004       slot = htab_find_slot (htab, *tp, INSERT);
2005       if (*slot)
2006         return NULL_TREE;
2007       *slot = *tp;
2008     }
2009
2010   /* Call the function.  */
2011   walk_subtrees = 1;
2012   result = (*func) (tp, &walk_subtrees, data);
2013
2014   /* If we found something, return it.  */
2015   if (result)
2016     return result;
2017
2018   code = TREE_CODE (*tp);
2019
2020   /* Even if we didn't, FUNC may have decided that there was nothing
2021      interesting below this point in the tree.  */
2022   if (!walk_subtrees)
2023     {
2024       if (code == TREE_LIST)
2025         /* But we still need to check our siblings.  */
2026         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2027       else
2028         return NULL_TREE;
2029     }
2030
2031   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
2032                                                    data, htab);
2033   if (result || ! walk_subtrees)
2034     return result;
2035
2036   /* If this is a DECL_EXPR, walk into various fields of the type that it's
2037      defining.  We only want to walk into these fields of a type in this
2038      case.  Note that decls get walked as part of the processing of a
2039      BIND_EXPR.
2040
2041      ??? Precisely which fields of types that we are supposed to walk in
2042      this case vs. the normal case aren't well defined.  */
2043   if (code == DECL_EXPR
2044       && TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
2045       && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
2046     {
2047       tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
2048
2049       /* Call the function for the type.  See if it returns anything or
2050          doesn't want us to continue.  If we are to continue, walk both
2051          the normal fields and those for the declaration case.  */
2052       result = (*func) (type_p, &walk_subtrees, data);
2053       if (result || !walk_subtrees)
2054         return NULL_TREE;
2055
2056       result = walk_type_fields (*type_p, func, data, htab_);
2057       if (result)
2058         return result;
2059
2060       WALK_SUBTREE (TYPE_SIZE (*type_p));
2061       WALK_SUBTREE (TYPE_SIZE_UNIT (*type_p));
2062
2063       /* If this is a record type, also walk the fields.  */
2064       if (TREE_CODE (*type_p) == RECORD_TYPE
2065           || TREE_CODE (*type_p) == UNION_TYPE
2066           || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2067         {
2068           tree field;
2069
2070           for (field = TYPE_FIELDS (*type_p); field;
2071                field = TREE_CHAIN (field))
2072             {
2073               /* We'd like to look at the type of the field, but we can easily
2074                  get infinite recursion.  So assume it's pointed to elsewhere
2075                  in the tree.  Also, ignore things that aren't fields.  */
2076               if (TREE_CODE (field) != FIELD_DECL)
2077                 continue;
2078
2079               WALK_SUBTREE (DECL_FIELD_OFFSET (field));
2080               WALK_SUBTREE (DECL_SIZE (field));
2081               WALK_SUBTREE (DECL_SIZE_UNIT (field));
2082               if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
2083                 WALK_SUBTREE (DECL_QUALIFIER (field));
2084             }
2085         }
2086     }
2087
2088   else if (code != EXIT_BLOCK_EXPR
2089            && code != SAVE_EXPR
2090            && code != BIND_EXPR
2091            && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2092     {
2093       int i, len;
2094
2095       /* Walk over all the sub-trees of this operand.  */
2096       len = first_rtl_op (code);
2097       /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
2098          But, we only want to walk once.  */
2099       if (code == TARGET_EXPR
2100           && TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1))
2101         --len;
2102
2103       /* Go through the subtrees.  We need to do this in forward order so
2104          that the scope of a FOR_EXPR is handled properly.  */
2105 #ifdef DEBUG_WALK_TREE
2106       for (i = 0; i < len; ++i)
2107         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2108 #else
2109       for (i = 0; i < len - 1; ++i)
2110         WALK_SUBTREE (TREE_OPERAND (*tp, i));
2111
2112       if (len)
2113         {
2114           /* The common case is that we may tail recurse here.  */
2115           if (code != BIND_EXPR
2116               && !TREE_CHAIN (*tp))
2117             WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
2118           else
2119             WALK_SUBTREE (TREE_OPERAND (*tp, len - 1));
2120         }
2121 #endif
2122     }
2123
2124   /* If this is a type, walk the needed fields in the type.  */
2125   else if (TYPE_P (*tp))
2126     {
2127       result = walk_type_fields (*tp, func, data, htab_);
2128       if (result)
2129         return result;
2130     }
2131   else
2132     {
2133       /* Not one of the easy cases.  We must explicitly go through the
2134          children.  */
2135       switch (code)
2136         {
2137         case ERROR_MARK:
2138         case IDENTIFIER_NODE:
2139         case INTEGER_CST:
2140         case REAL_CST:
2141         case VECTOR_CST:
2142         case STRING_CST:
2143         case BLOCK:
2144         case PLACEHOLDER_EXPR:
2145         case SSA_NAME:
2146         case FIELD_DECL:
2147         case RESULT_DECL:
2148           /* None of thse have subtrees other than those already walked
2149              above.  */
2150           break;
2151
2152         case TREE_LIST:
2153           WALK_SUBTREE (TREE_VALUE (*tp));
2154           WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
2155           break;
2156
2157         case TREE_VEC:
2158           {
2159             int len = TREE_VEC_LENGTH (*tp);
2160
2161             if (len == 0)
2162               break;
2163
2164             /* Walk all elements but the first.  */
2165             while (--len)
2166               WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
2167
2168             /* Now walk the first one as a tail call.  */
2169             WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
2170           }
2171
2172         case COMPLEX_CST:
2173           WALK_SUBTREE (TREE_REALPART (*tp));
2174           WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
2175
2176         case CONSTRUCTOR:
2177           WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
2178
2179         case EXIT_BLOCK_EXPR:
2180           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 1));
2181
2182         case SAVE_EXPR:
2183           WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
2184
2185         case BIND_EXPR:
2186           {
2187             tree decl;
2188             for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
2189               {
2190                 /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
2191                    into declarations that are just mentioned, rather than
2192                    declared; they don't really belong to this part of the tree.
2193                    And, we can see cycles: the initializer for a declaration
2194                    can refer to the declaration itself.  */
2195                 WALK_SUBTREE (DECL_INITIAL (decl));
2196                 WALK_SUBTREE (DECL_SIZE (decl));
2197                 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
2198               }
2199             WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
2200           }
2201
2202         case STATEMENT_LIST:
2203           {
2204             tree_stmt_iterator i;
2205             for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
2206               WALK_SUBTREE (*tsi_stmt_ptr (i));
2207           }
2208           break;
2209
2210         default:
2211           /* ??? This could be a language-defined node.  We really should make
2212              a hook for it, but right now just ignore it.  */
2213           break;
2214         }
2215     }
2216
2217   /* We didn't find what we were looking for.  */
2218   return NULL_TREE;
2219
2220 #undef WALK_SUBTREE
2221 #undef WALK_SUBTREE_TAIL
2222 }
2223
2224 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
2225
2226 tree
2227 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
2228 {
2229   tree result;
2230   htab_t htab;
2231
2232   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
2233   result = walk_tree (tp, func, data, htab);
2234   htab_delete (htab);
2235   return result;
2236 }
2237
2238 /* Passed to walk_tree.  Copies the node pointed to, if appropriate.  */
2239
2240 tree
2241 copy_tree_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2242 {
2243   enum tree_code code = TREE_CODE (*tp);
2244
2245   /* We make copies of most nodes.  */
2246   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
2247       || code == TREE_LIST
2248       || code == TREE_VEC
2249       || code == TYPE_DECL)
2250     {
2251       /* Because the chain gets clobbered when we make a copy, we save it
2252          here.  */
2253       tree chain = TREE_CHAIN (*tp);
2254       tree new;
2255
2256       /* Copy the node.  */
2257       new = copy_node (*tp);
2258
2259       /* Propagate mudflap marked-ness.  */
2260       if (flag_mudflap && mf_marked_p (*tp))
2261         mf_mark (new);
2262
2263       *tp = new;
2264
2265       /* Now, restore the chain, if appropriate.  That will cause
2266          walk_tree to walk into the chain as well.  */
2267       if (code == PARM_DECL || code == TREE_LIST)
2268         TREE_CHAIN (*tp) = chain;
2269
2270       /* For now, we don't update BLOCKs when we make copies.  So, we
2271          have to nullify all BIND_EXPRs.  */
2272       if (TREE_CODE (*tp) == BIND_EXPR)
2273         BIND_EXPR_BLOCK (*tp) = NULL_TREE;
2274     }
2275
2276   else if (TREE_CODE_CLASS (code) == tcc_type)
2277     *walk_subtrees = 0;
2278   else if (TREE_CODE_CLASS (code) == tcc_declaration)
2279     *walk_subtrees = 0;
2280   else if (TREE_CODE_CLASS (code) == tcc_constant)
2281     *walk_subtrees = 0;
2282   else
2283     gcc_assert (code != STATEMENT_LIST);
2284   return NULL_TREE;
2285 }
2286
2287 /* The SAVE_EXPR pointed to by TP is being copied.  If ST contains
2288    information indicating to what new SAVE_EXPR this one should be mapped,
2289    use that one.  Otherwise, create a new node and enter it in ST.  */
2290
2291 void
2292 remap_save_expr (tree *tp, void *st_, int *walk_subtrees)
2293 {
2294   splay_tree st = (splay_tree) st_;
2295   splay_tree_node n;
2296   tree t;
2297
2298   /* See if we already encountered this SAVE_EXPR.  */
2299   n = splay_tree_lookup (st, (splay_tree_key) *tp);
2300
2301   /* If we didn't already remap this SAVE_EXPR, do so now.  */
2302   if (!n)
2303     {
2304       t = copy_node (*tp);
2305
2306       /* Remember this SAVE_EXPR.  */
2307       splay_tree_insert (st, (splay_tree_key) *tp, (splay_tree_value) t);
2308       /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
2309       splay_tree_insert (st, (splay_tree_key) t, (splay_tree_value) t);
2310     }
2311   else
2312     {
2313       /* We've already walked into this SAVE_EXPR; don't do it again.  */
2314       *walk_subtrees = 0;
2315       t = (tree) n->value;
2316     }
2317
2318   /* Replace this SAVE_EXPR with the copy.  */
2319   *tp = t;
2320 }
2321
2322 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local label,
2323    copies the declaration and enters it in the splay_tree in DATA (which is
2324    really an `inline_data *').  */
2325
2326 static tree
2327 mark_local_for_remap_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
2328                         void *data)
2329 {
2330   inline_data *id = (inline_data *) data;
2331
2332   /* Don't walk into types.  */
2333   if (TYPE_P (*tp))
2334     *walk_subtrees = 0;
2335
2336   else if (TREE_CODE (*tp) == LABEL_EXPR)
2337     {
2338       tree decl = TREE_OPERAND (*tp, 0);
2339
2340       /* Copy the decl and remember the copy.  */
2341       insert_decl_map (id, decl,
2342                        copy_decl_for_inlining (decl, DECL_CONTEXT (decl),
2343                                                DECL_CONTEXT (decl)));
2344     }
2345
2346   return NULL_TREE;
2347 }
2348
2349 /* Perform any modifications to EXPR required when it is unsaved.  Does
2350    not recurse into EXPR's subtrees.  */
2351
2352 static void
2353 unsave_expr_1 (tree expr)
2354 {
2355   switch (TREE_CODE (expr))
2356     {
2357     case TARGET_EXPR:
2358       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
2359          It's OK for this to happen if it was part of a subtree that
2360          isn't immediately expanded, such as operand 2 of another
2361          TARGET_EXPR.  */
2362       if (TREE_OPERAND (expr, 1))
2363         break;
2364
2365       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
2366       TREE_OPERAND (expr, 3) = NULL_TREE;
2367       break;
2368
2369     default:
2370       break;
2371     }
2372 }
2373
2374 /* Called via walk_tree when an expression is unsaved.  Using the
2375    splay_tree pointed to by ST (which is really a `splay_tree'),
2376    remaps all local declarations to appropriate replacements.  */
2377
2378 static tree
2379 unsave_r (tree *tp, int *walk_subtrees, void *data)
2380 {
2381   inline_data *id = (inline_data *) data;
2382   splay_tree st = id->decl_map;
2383   splay_tree_node n;
2384
2385   /* Only a local declaration (variable or label).  */
2386   if ((TREE_CODE (*tp) == VAR_DECL && !TREE_STATIC (*tp))
2387       || TREE_CODE (*tp) == LABEL_DECL)
2388     {
2389       /* Lookup the declaration.  */
2390       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2391
2392       /* If it's there, remap it.  */
2393       if (n)
2394         *tp = (tree) n->value;
2395     }
2396
2397   else if (TREE_CODE (*tp) == STATEMENT_LIST)
2398     copy_statement_list (tp);
2399   else if (TREE_CODE (*tp) == BIND_EXPR)
2400     copy_bind_expr (tp, walk_subtrees, id);
2401   else if (TREE_CODE (*tp) == SAVE_EXPR)
2402     remap_save_expr (tp, st, walk_subtrees);
2403   else
2404     {
2405       copy_tree_r (tp, walk_subtrees, NULL);
2406
2407       /* Do whatever unsaving is required.  */
2408       unsave_expr_1 (*tp);
2409     }
2410
2411   /* Keep iterating.  */
2412   return NULL_TREE;
2413 }
2414
2415 /* Copies everything in EXPR and replaces variables, labels
2416    and SAVE_EXPRs local to EXPR.  */
2417
2418 tree
2419 unsave_expr_now (tree expr)
2420 {
2421   inline_data id;
2422
2423   /* There's nothing to do for NULL_TREE.  */
2424   if (expr == 0)
2425     return expr;
2426
2427   /* Set up ID.  */
2428   memset (&id, 0, sizeof (id));
2429   VARRAY_TREE_INIT (id.fns, 1, "fns");
2430   VARRAY_PUSH_TREE (id.fns, current_function_decl);
2431   id.decl_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2432
2433   /* Walk the tree once to find local labels.  */
2434   walk_tree_without_duplicates (&expr, mark_local_for_remap_r, &id);
2435
2436   /* Walk the tree again, copying, remapping, and unsaving.  */
2437   walk_tree (&expr, unsave_r, &id, NULL);
2438
2439   /* Clean up.  */
2440   splay_tree_delete (id.decl_map);
2441
2442   return expr;
2443 }
2444
2445 /* Allow someone to determine if SEARCH is a child of TOP from gdb.  */
2446
2447 static tree
2448 debug_find_tree_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
2449 {
2450   if (*tp == data)
2451     return (tree) data;
2452   else
2453     return NULL;
2454 }
2455
2456 bool
2457 debug_find_tree (tree top, tree search)
2458 {
2459   return walk_tree_without_duplicates (&top, debug_find_tree_1, search) != 0;
2460 }
2461
2462 /* Declare the variables created by the inliner.  Add all the variables in
2463    VARS to BIND_EXPR.  */
2464
2465 static void
2466 declare_inline_vars (tree bind_expr, tree vars)
2467 {
2468   tree t;
2469   for (t = vars; t; t = TREE_CHAIN (t))
2470     DECL_SEEN_IN_BIND_EXPR_P (t) = 1;
2471
2472   add_var_to_bind_expr (bind_expr, vars);
2473 }