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