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 SET_TYPE:
 327     case OFFSET_TYPE:
 328     default:
 329       /* Shouldn't have been thought variable sized.  */
 330       gcc_unreachable ();
 331     }
 332
 333   walk_tree (&TYPE_SIZE (new), copy_body_r, id, NULL);
 334   walk_tree (&TYPE_SIZE_UNIT (new), copy_body_r, id, NULL);
 335
 336   return new;
 337 }
 338
 339 static tree
 340 remap_decls (tree decls, inline_data *id)
 341 {
 342   tree old_var;
 343   tree new_decls = NULL_TREE;
 344
 345   /* Remap its variables.  */
 346   for (old_var = decls; old_var; old_var = TREE_CHAIN (old_var))
 347     {
 348       tree new_var;
 349
 350       /* Remap the variable.  */
 351       new_var = remap_decl (old_var, id);
 352
 353       /* If we didn't remap this variable, so we can't mess with its
 354          TREE_CHAIN.  If we remapped this variable to the return slot, it's
 355          already declared somewhere else, so don't declare it here.  */
 356       if (!new_var || new_var == id->retvar)
 357         ;
 358       else
 359         {
 360           gcc_assert (DECL_P (new_var));
 361           TREE_CHAIN (new_var) = new_decls;
 362           new_decls = new_var;
 363         }
 364     }
 365
 366   return nreverse (new_decls);
 367 }
 368
 369 /* Copy the BLOCK to contain remapped versions of the variables
 370    therein.  And hook the new block into the block-tree.  */
 371
 372 static void
 373 remap_block (tree *block, inline_data *id)
 374 {
 375   tree old_block;
 376   tree new_block;
 377   tree fn;
 378
 379   /* Make the new block.  */
 380   old_block = *block;
 381   new_block = make_node (BLOCK);
 382   TREE_USED (new_block) = TREE_USED (old_block);
 383   BLOCK_ABSTRACT_ORIGIN (new_block) = old_block;
 384   *block = new_block;
 385
 386   /* Remap its variables.  */
 387   BLOCK_VARS (new_block) = remap_decls (BLOCK_VARS (old_block), id);
 388
 389   fn = VARRAY_TREE (id->fns, 0);
 390 #if 1
 391   /* FIXME!  It shouldn't be so hard to manage blocks.  Rebuilding them in
 392      rest_of_compilation is a good start.  */
 393   if (id->cloning_p)
 394     /* We're building a clone; DECL_INITIAL is still
 395        error_mark_node, and current_binding_level is the parm
 396        binding level.  */
 397     lang_hooks.decls.insert_block (new_block);
 398   else
 399     {
 400       /* Attach this new block after the DECL_INITIAL block for the
 401          function into which this block is being inlined.  In
 402          rest_of_compilation we will straighten out the BLOCK tree.  */
 403       tree *first_block;
 404       if (DECL_INITIAL (fn))
 405         first_block = &BLOCK_CHAIN (DECL_INITIAL (fn));
 406       else
 407         first_block = &DECL_INITIAL (fn);
 408       BLOCK_CHAIN (new_block) = *first_block;
 409       *first_block = new_block;
 410     }
 411 #endif
 412   /* Remember the remapped block.  */
 413   insert_decl_map (id, old_block, new_block);
 414 }
 415
 416 static void
 417 copy_statement_list (tree *tp)
 418 {
 419   tree_stmt_iterator oi, ni;
 420   tree new;
 421
 422   new = alloc_stmt_list ();
 423   ni = tsi_start (new);
 424   oi = tsi_start (*tp);
 425   *tp = new;
 426
 427   for (; !tsi_end_p (oi); tsi_next (&oi))
 428     tsi_link_after (&ni, tsi_stmt (oi), TSI_NEW_STMT);
 429 }
 430
 431 static void
 432 copy_bind_expr (tree *tp, int *walk_subtrees, inline_data *id)
 433 {
 434   tree block = BIND_EXPR_BLOCK (*tp);
 435   /* Copy (and replace) the statement.  */
 436   copy_tree_r (tp, walk_subtrees, NULL);
 437   if (block)
 438     {
 439       remap_block (&block, id);
 440       BIND_EXPR_BLOCK (*tp) = block;
 441     }
 442
 443   if (BIND_EXPR_VARS (*tp))
 444     /* This will remap a lot of the same decls again, but this should be
 445        harmless.  */
 446     BIND_EXPR_VARS (*tp) = remap_decls (BIND_EXPR_VARS (*tp), id);
 447 }
 448
 449 /* Called from copy_body via walk_tree.  DATA is really an `inline_data *'.  */
 450
 451 static tree
 452 copy_body_r (tree *tp, int *walk_subtrees, void *data)
 453 {
 454   inline_data *id = (inline_data *) data;
 455   tree fn = VARRAY_TOP_TREE (id->fns);
 456
 457 #if 0
 458   /* All automatic variables should have a DECL_CONTEXT indicating
 459      what function they come from.  */
 460   if ((TREE_CODE (*tp) == VAR_DECL || TREE_CODE (*tp) == LABEL_DECL)
 461       && DECL_NAMESPACE_SCOPE_P (*tp))
 462     gcc_assert (DECL_EXTERNAL (*tp) || TREE_STATIC (*tp));
 463 #endif
 464
 465   /* If this is a RETURN_EXPR, change it into a MODIFY_EXPR and a
 466      GOTO_EXPR with the RET_LABEL as its target.  */
 467   if (TREE_CODE (*tp) == RETURN_EXPR && id->ret_label)
 468     {
 469       tree return_stmt = *tp;
 470       tree goto_stmt;
 471
 472       /* Build the GOTO_EXPR.  */
 473       tree assignment = TREE_OPERAND (return_stmt, 0);
 474       goto_stmt = build1 (GOTO_EXPR, void_type_node, id->ret_label);
 475       TREE_USED (id->ret_label) = 1;
 476
 477       /* If we're returning something, just turn that into an
 478          assignment into the equivalent of the original
 479          RESULT_DECL.  */
 480       if (assignment)
 481         {
 482           /* Do not create a statement containing a naked RESULT_DECL.  */
 483           if (TREE_CODE (assignment) == RESULT_DECL)
 484             gimplify_stmt (&assignment);
 485
 486           *tp = build (BIND_EXPR, void_type_node, NULL, NULL, NULL);
 487           append_to_statement_list (assignment, &BIND_EXPR_BODY (*tp));
 488           append_to_statement_list (goto_stmt, &BIND_EXPR_BODY (*tp));
 489         }
 490       /* If we're not returning anything just do the jump.  */
 491       else
 492         *tp = goto_stmt;
 493     }
 494   /* Local variables and labels need to be replaced by equivalent
 495      variables.  We don't want to copy static variables; there's only
 496      one of those, no matter how many times we inline the containing
 497      function.  Similarly for globals from an outer function.  */
 498   else if (lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
 499     {
 500       tree new_decl;
 501
 502       /* Remap the declaration.  */
 503       new_decl = remap_decl (*tp, id);
 504       gcc_assert (new_decl);
 505       /* Replace this variable with the copy.  */
 506       STRIP_TYPE_NOPS (new_decl);
 507       *tp = new_decl;
 508     }
 509   else if (TREE_CODE (*tp) == STATEMENT_LIST)
 510     copy_statement_list (tp);
 511   else if (TREE_CODE (*tp) == SAVE_EXPR)
 512     remap_save_expr (tp, id->decl_map, walk_subtrees);
 513   else if (TREE_CODE (*tp) == BIND_EXPR)
 514     copy_bind_expr (tp, walk_subtrees, id);
 515   /* Types may need remapping as well.  */
 516   else if (TYPE_P (*tp))
 517     *tp = remap_type (*tp, id);
 518
 519   /* If this is a constant, we have to copy the node iff the type will be
 520      remapped.  copy_tree_r will not copy a constant.  */
 521   else if (TREE_CODE_CLASS (TREE_CODE (*tp)) == tcc_constant)
 522     {
 523       tree new_type = remap_type (TREE_TYPE (*tp), id);
 524
 525       if (new_type == TREE_TYPE (*tp))
 526         *walk_subtrees = 0;
 527
 528       else if (TREE_CODE (*tp) == INTEGER_CST)
 529         *tp = build_int_cst_wide (new_type, TREE_INT_CST_LOW (*tp),
 530                                   TREE_INT_CST_HIGH (*tp));
 531       else
 532         {
 533           *tp = copy_node (*tp);
 534           TREE_TYPE (*tp) = new_type;
 535         }
 536     }
 537
 538   /* Otherwise, just copy the node.  Note that copy_tree_r already
 539      knows not to copy VAR_DECLs, etc., so this is safe.  */
 540   else
 541     {
 542       tree old_node = *tp;
 543
 544       if (TREE_CODE (*tp) == MODIFY_EXPR
 545           && TREE_OPERAND (*tp, 0) == TREE_OPERAND (*tp, 1)
 546           && (lang_hooks.tree_inlining.auto_var_in_fn_p
 547               (TREE_OPERAND (*tp, 0), fn)))
 548         {
 549           /* Some assignments VAR = VAR; don't generate any rtl code
 550              and thus don't count as variable modification.  Avoid
 551              keeping bogosities like 0 = 0.  */
 552           tree decl = TREE_OPERAND (*tp, 0), value;
 553           splay_tree_node n;
 554
 555           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 556           if (n)
 557             {
 558               value = (tree) n->value;
 559               STRIP_TYPE_NOPS (value);
 560               if (TREE_CONSTANT (value) || TREE_READONLY_DECL_P (value))
 561                 {
 562                   *tp = build_empty_stmt ();
 563                   return copy_body_r (tp, walk_subtrees, data);
 564                 }
 565             }
 566         }
 567       else if (TREE_CODE (*tp) == INDIRECT_REF)
 568         {
 569           /* Get rid of *& from inline substitutions that can happen when a
 570              pointer argument is an ADDR_EXPR.  */
 571           tree decl = TREE_OPERAND (*tp, 0), value;
 572           splay_tree_node n;
 573
 574           n = splay_tree_lookup (id->decl_map, (splay_tree_key) decl);
 575           if (n)
 576             {
 577               value = (tree) n->value;
 578               STRIP_NOPS (value);
 579               if (TREE_CODE (value) == ADDR_EXPR
 580                   && (lang_hooks.types_compatible_p
 581                       (TREE_TYPE (*tp), TREE_TYPE (TREE_OPERAND (value, 0)))))
 582                 {
 583                   *tp = TREE_OPERAND (value, 0);
 584                   return copy_body_r (tp, walk_subtrees, data);
 585                 }
 586             }
 587         }
 588
 589       copy_tree_r (tp, walk_subtrees, NULL);
 590
 591       if (TREE_CODE (*tp) == CALL_EXPR && id->node && get_callee_fndecl (*tp))
 592         {
 593           if (id->saving_p)
 594             {
 595               struct cgraph_node *node;
 596               struct cgraph_edge *edge;
 597
 598               for (node = id->node->next_clone; node; node = node->next_clone)
 599                 {
 600                   edge = cgraph_edge (node, old_node);
 601                   gcc_assert (edge);
 602                   edge->call_expr = *tp;
 603                 }
 604             }
 605           else
 606             {
 607               struct cgraph_edge *edge
 608                 = cgraph_edge (id->current_node, old_node);
 609
 610               if (edge)
 611                 cgraph_clone_edge (edge, id->node, *tp);
 612             }
 613         }
 614
 615       TREE_TYPE (*tp) = remap_type (TREE_TYPE (*tp), id);
 616
 617       /* The copied TARGET_EXPR has never been expanded, even if the
 618          original node was expanded already.  */
 619       if (TREE_CODE (*tp) == TARGET_EXPR && TREE_OPERAND (*tp, 3))
 620         {
 621           TREE_OPERAND (*tp, 1) = TREE_OPERAND (*tp, 3);
 622           TREE_OPERAND (*tp, 3) = NULL_TREE;
 623         }
 624
 625       /* Variable substitution need not be simple.  In particular, the
 626          INDIRECT_REF substitution above.  Make sure that TREE_CONSTANT
 627          and friends are up-to-date.  */
 628       else if (TREE_CODE (*tp) == ADDR_EXPR)
 629         {
 630           walk_tree (&TREE_OPERAND (*tp, 0), copy_body_r, id, NULL);
 631           recompute_tree_invarant_for_addr_expr (*tp);
 632           *walk_subtrees = 0;
 633         }
 634     }
 635
 636   /* Keep iterating.  */
 637   return NULL_TREE;
 638 }
 639
 640 /* Make a copy of the body of FN so that it can be inserted inline in
 641    another function.  */
 642
 643 static tree
 644 copy_body (inline_data *id)
 645 {
 646   tree body;
 647   tree fndecl = VARRAY_TOP_TREE (id->fns);
 648
 649   if (fndecl == current_function_decl
 650       && cfun->saved_tree)
 651     body = cfun->saved_tree;
 652   else
 653     body = DECL_SAVED_TREE (fndecl);
 654   walk_tree (&body, copy_body_r, id, NULL);
 655
 656   return body;
 657 }
 658
 659 static void
 660 setup_one_parameter (inline_data *id, tree p, tree value, tree fn,
 661                      tree *init_stmts, tree *vars, bool *gimplify_init_stmts_p)
 662 {
 663   tree init_stmt;
 664   tree var;
 665
 666   /* If the parameter is never assigned to, we may not need to
 667      create a new variable here at all.  Instead, we may be able
 668      to just use the argument value.  */
 669   if (TREE_READONLY (p)
 670       && !TREE_ADDRESSABLE (p)
 671       && value && !TREE_SIDE_EFFECTS (value))
 672     {
 673       /* We can't risk substituting complex expressions.  They
 674          might contain variables that will be assigned to later.
 675          Theoretically, we could check the expression to see if
 676          all of the variables that determine its value are
 677          read-only, but we don't bother.  */
 678       /* We may produce non-gimple trees by adding NOPs or introduce
 679          invalid sharing when operand is not really constant.
 680          It is not big deal to prohibit constant propagation here as
 681          we will constant propagate in DOM1 pass anyway.  */
 682       if (is_gimple_min_invariant (value)
 683           && lang_hooks.types_compatible_p (TREE_TYPE (value), TREE_TYPE (p)))
 684         {
 685           insert_decl_map (id, p, value);
 686           return;
 687         }
 688     }
 689
 690   /* Make an equivalent VAR_DECL.  Note that we must NOT remap the type
 691      here since the type of this decl must be visible to the calling
 692      function.  */
 693   var = copy_decl_for_inlining (p, fn, VARRAY_TREE (id->fns, 0));
 694
 695   /* Register the VAR_DECL as the equivalent for the PARM_DECL;
 696      that way, when the PARM_DECL is encountered, it will be
 697      automatically replaced by the VAR_DECL.  */
 698   insert_decl_map (id, p, var);
 699
 700   /* Declare this new variable.  */
 701   TREE_CHAIN (var) = *vars;
 702   *vars = var;
 703
 704   /* Make gimplifier happy about this variable.  */
 705   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 706
 707   /* Even if P was TREE_READONLY, the new VAR should not be.
 708      In the original code, we would have constructed a
 709      temporary, and then the function body would have never
 710      changed the value of P.  However, now, we will be
 711      constructing VAR directly.  The constructor body may
 712      change its value multiple times as it is being
 713      constructed.  Therefore, it must not be TREE_READONLY;
 714      the back-end assumes that TREE_READONLY variable is
 715      assigned to only once.  */
 716   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (p)))
 717     TREE_READONLY (var) = 0;
 718
 719   /* Initialize this VAR_DECL from the equivalent argument.  Convert
 720      the argument to the proper type in case it was promoted.  */
 721   if (value)
 722     {
 723       tree rhs = fold_convert (TREE_TYPE (var), value);
 724
 725       if (rhs == error_mark_node)
 726         return;
 727
 728       /* We want to use MODIFY_EXPR, not INIT_EXPR here so that we
 729          keep our trees in gimple form.  */
 730       init_stmt = build (MODIFY_EXPR, TREE_TYPE (var), var, rhs);
 731       append_to_statement_list (init_stmt, init_stmts);
 732
 733       /* If we did not create a gimple value and we did not create a gimple
 734          cast of a gimple value, then we will need to gimplify INIT_STMTS
 735          at the end.  Note that is_gimple_cast only checks the outer
 736          tree code, not its operand.  Thus the explicit check that it's
 737          operand is a gimple value.  */
 738       if (!is_gimple_val (rhs)
 739           && (!is_gimple_cast (rhs)
 740               || !is_gimple_val (TREE_OPERAND (rhs, 0))))
 741         *gimplify_init_stmts_p = true;
 742     }
 743 }
 744
 745 /* Generate code to initialize the parameters of the function at the
 746    top of the stack in ID from the ARGS (presented as a TREE_LIST).  */
 747
 748 static tree
 749 initialize_inlined_parameters (inline_data *id, tree args, tree static_chain,
 750                                tree fn, tree bind_expr)
 751 {
 752   tree init_stmts = NULL_TREE;
 753   tree parms;
 754   tree a;
 755   tree p;
 756   tree vars = NULL_TREE;
 757   bool gimplify_init_stmts_p = false;
 758   int argnum = 0;
 759
 760   /* Figure out what the parameters are.  */
 761   parms = DECL_ARGUMENTS (fn);
 762   if (fn == current_function_decl)
 763     parms = cfun->saved_args;
 764
 765   /* Loop through the parameter declarations, replacing each with an
 766      equivalent VAR_DECL, appropriately initialized.  */
 767   for (p = parms, a = args; p;
 768        a = a ? TREE_CHAIN (a) : a, p = TREE_CHAIN (p))
 769     {
 770       tree value;
 771
 772       ++argnum;
 773
 774       /* Find the initializer.  */
 775       value = lang_hooks.tree_inlining.convert_parm_for_inlining
 776               (p, a ? TREE_VALUE (a) : NULL_TREE, fn, argnum);
 777
 778       setup_one_parameter (id, p, value, fn, &init_stmts, &vars,
 779                            &gimplify_init_stmts_p);
 780     }
 781
 782   /* Evaluate trailing arguments.  */
 783   for (; a; a = TREE_CHAIN (a))
 784     {
 785       tree value = TREE_VALUE (a);
 786       append_to_statement_list (value, &init_stmts);
 787     }
 788
 789   /* Initialize the static chain.  */
 790   p = DECL_STRUCT_FUNCTION (fn)->static_chain_decl;
 791   if (p)
 792     {
 793       /* No static chain?  Seems like a bug in tree-nested.c.  */
 794       gcc_assert (static_chain);
 795
 796       setup_one_parameter (id, p, static_chain, fn, &init_stmts, &vars,
 797                            &gimplify_init_stmts_p);
 798     }
 799
 800   if (gimplify_init_stmts_p)
 801     gimplify_body (&init_stmts, current_function_decl);
 802
 803   declare_inline_vars (bind_expr, vars);
 804   return init_stmts;
 805 }
 806
 807 /* Declare a return variable to replace the RESULT_DECL for the function we
 808    are calling.  RETURN_SLOT_ADDR, if non-null, was a fake parameter that
 809    took the address of the result.  MODIFY_DEST, if non-null, was the LHS of
 810    the MODIFY_EXPR to which this call is the RHS.
 811
 812    The return value is a (possibly null) value that is the result of the
 813    function as seen by the callee.  *USE_P is a (possibly null) value that
 814    holds the result as seen by the caller.  */
 815
 816 static tree
 817 declare_return_variable (inline_data *id, tree return_slot_addr,
 818                          tree modify_dest, tree *use_p)
 819 {
 820   tree callee = VARRAY_TOP_TREE (id->fns);
 821   tree caller = VARRAY_TREE (id->fns, 0);
 822   tree result = DECL_RESULT (callee);
 823   tree callee_type = TREE_TYPE (result);
 824   tree caller_type = TREE_TYPE (TREE_TYPE (callee));
 825   tree var, use;
 826
 827   /* We don't need to do anything for functions that don't return
 828      anything.  */
 829   if (!result || VOID_TYPE_P (callee_type))
 830     {
 831       *use_p = NULL_TREE;
 832       return NULL_TREE;
 833     }
 834
 835   /* If there was a return slot, then the return value is the
 836      dereferenced address of that object.  */
 837   if (return_slot_addr)
 838     {
 839       /* The front end shouldn't have used both return_slot_addr and
 840          a modify expression.  */
 841       gcc_assert (!modify_dest);
 842       if (DECL_BY_REFERENCE (result))
 843         var = return_slot_addr;
 844       else
 845         var = build_fold_indirect_ref (return_slot_addr);
 846       use = NULL;
 847       goto done;
 848     }
 849
 850   /* All types requiring non-trivial constructors should have been handled.  */
 851   gcc_assert (!TREE_ADDRESSABLE (callee_type));
 852
 853   /* Attempt to avoid creating a new temporary variable.  */
 854   if (modify_dest)
 855     {
 856       bool use_it = false;
 857
 858       /* We can't use MODIFY_DEST if there's type promotion involved.  */
 859       if (!lang_hooks.types_compatible_p (caller_type, callee_type))
 860         use_it = false;
 861
 862       /* ??? If we're assigning to a variable sized type, then we must
 863          reuse the destination variable, because we've no good way to
 864          create variable sized temporaries at this point.  */
 865       else if (TREE_CODE (TYPE_SIZE_UNIT (caller_type)) != INTEGER_CST)
 866         use_it = true;
 867
 868       /* If the callee cannot possibly modify MODIFY_DEST, then we can
 869          reuse it as the result of the call directly.  Don't do this if
 870          it would promote MODIFY_DEST to addressable.  */
 871       else if (!TREE_STATIC (modify_dest)
 872                && !TREE_ADDRESSABLE (modify_dest)
 873                && !TREE_ADDRESSABLE (result))
 874         use_it = true;
 875
 876       if (use_it)
 877         {
 878           var = modify_dest;
 879           use = NULL;
 880           goto done;
 881         }
 882     }
 883
 884   gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (callee_type)) == INTEGER_CST);
 885
 886   var = copy_decl_for_inlining (result, callee, caller);
 887   DECL_SEEN_IN_BIND_EXPR_P (var) = 1;
 888   DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list
 889     = tree_cons (NULL_TREE, var,
 890                  DECL_STRUCT_FUNCTION (caller)->unexpanded_var_list);
 891
 892   /* Do not have the rest of GCC warn about this variable as it should
 893      not be visible to the user.  */
 894   TREE_NO_WARNING (var) = 1;
 895
 896   /* Build the use expr.  If the return type of the function was
 897      promoted, convert it back to the expected type.  */
 898   use = var;
 899   if (!lang_hooks.types_compatible_p (TREE_TYPE (var), caller_type))
 900     use = fold_convert (caller_type, var);
 901
 902  done:
 903   /* Register the VAR_DECL as the equivalent for the RESULT_DECL; that
 904      way, when the RESULT_DECL is encountered, it will be
 905      automatically replaced by the VAR_DECL.  */
 906   insert_decl_map (id, result, var);
 907
 908   /* Remember this so we can ignore it in remap_decls.  */
 909   id->retvar = var;
 910
 911   *use_p = use;
 912   return var;
 913 }
 914
 915 /* Returns nonzero if a function can be inlined as a tree.  */
 916
 917 bool
 918 tree_inlinable_function_p (tree fn)
 919 {
 920   return inlinable_function_p (fn);
 921 }
 922
 923 static const char *inline_forbidden_reason;
 924
 925 static tree
 926 inline_forbidden_p_1 (tree *nodep, int *walk_subtrees ATTRIBUTE_UNUSED,
 927                       void *fnp)
 928 {
 929   tree node = *nodep;
 930   tree fn = (tree) fnp;
 931   tree t;
 932
 933   switch (TREE_CODE (node))
 934     {
 935     case CALL_EXPR:
 936       /* Refuse to inline alloca call unless user explicitly forced so as
 937          this may change program's memory overhead drastically when the
 938          function using alloca is called in loop.  In GCC present in
 939          SPEC2000 inlining into schedule_block cause it to require 2GB of
 940          RAM instead of 256MB.  */
 941       if (alloca_call_p (node)
 942           && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
 943         {
 944           inline_forbidden_reason
 945             = N_("%Jfunction %qF can never be inlined because it uses "
 946                  "alloca (override using the always_inline attribute)");
 947           return node;
 948         }
 949       t = get_callee_fndecl (node);
 950       if (! t)
 951         break;
 952
 953       /* We cannot inline functions that call setjmp.  */
 954       if (setjmp_call_p (t))
 955         {
 956           inline_forbidden_reason
 957             = N_("%Jfunction %qF can never be inlined because it uses setjmp");
 958           return node;
 959         }
 960
 961       if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL)
 962         switch (DECL_FUNCTION_CODE (t))
 963           {
 964             /* We cannot inline functions that take a variable number of
 965                arguments.  */
 966           case BUILT_IN_VA_START:
 967           case BUILT_IN_STDARG_START:
 968           case BUILT_IN_NEXT_ARG:
 969           case BUILT_IN_VA_END:
 970             inline_forbidden_reason
 971               = N_("%Jfunction %qF can never be inlined because it "
 972                    "uses variable argument lists");
 973             return node;
 974
 975           case BUILT_IN_LONGJMP:
 976             /* We can't inline functions that call __builtin_longjmp at
 977                all.  The non-local goto machinery really requires the
 978                destination be in a different function.  If we allow the
 979                function calling __builtin_longjmp to be inlined into the
 980                function calling __builtin_setjmp, Things will Go Awry.  */
 981             inline_forbidden_reason
 982               = N_("%Jfunction %qF can never be inlined because "
 983                    "it uses setjmp-longjmp exception handling");
 984             return node;
 985
 986           case BUILT_IN_NONLOCAL_GOTO:
 987             /* Similarly.  */
 988             inline_forbidden_reason
 989               = N_("%Jfunction %qF can never be inlined because "
 990                    "it uses non-local goto");
 991             return node;
 992
 993           default:
 994             break;
 995           }
 996       break;
 997
 998     case GOTO_EXPR:
 999       t = TREE_OPERAND (node, 0);
1000
1001       /* We will not inline a function which uses computed goto.  The
1002          addresses of its local labels, which may be tucked into
1003          global storage, are of course not constant across
1004          instantiations, which causes unexpected behavior.  */
1005       if (TREE_CODE (t) != LABEL_DECL)
1006         {
1007           inline_forbidden_reason
1008             = N_("%Jfunction %qF can never be inlined "
1009                  "because it contains a computed goto");
1010           return node;
1011         }
1012       break;
1013
1014     case LABEL_EXPR:
1015       t = TREE_OPERAND (node, 0);
1016       if (DECL_NONLOCAL (t))
1017         {
1018           /* We cannot inline a function that receives a non-local goto
1019              because we cannot remap the destination label used in the
1020              function that is performing the non-local goto.  */
1021           inline_forbidden_reason
1022             = N_("%Jfunction %qF can never be inlined "
1023                  "because it receives a non-local goto");
1024           return node;
1025         }
1026       break;
1027
1028     case RECORD_TYPE:
1029     case UNION_TYPE:
1030       /* We cannot inline a function of the form
1031
1032            void F (int i) { struct S { int ar[i]; } s; }
1033
1034          Attempting to do so produces a catch-22.
1035          If walk_tree examines the TYPE_FIELDS chain of RECORD_TYPE/
1036          UNION_TYPE nodes, then it goes into infinite recursion on a
1037          structure containing a pointer to its own type.  If it doesn't,
1038          then the type node for S doesn't get adjusted properly when
1039          F is inlined, and we abort in find_function_data.
1040
1041          ??? This is likely no longer true, but it's too late in the 4.0
1042          cycle to try to find out.  This should be checked for 4.1.  */
1043       for (t = TYPE_FIELDS (node); t; t = TREE_CHAIN (t))
1044         if (variably_modified_type_p (TREE_TYPE (t), NULL))
1045           {
1046             inline_forbidden_reason
1047               = N_("%Jfunction %qF can never be inlined "
1048                    "because it uses variable sized variables");
1049             return node;
1050           }
1051
1052     default:
1053       break;
1054     }
1055
1056   return NULL_TREE;
1057 }
1058
1059 /* Return subexpression representing possible alloca call, if any.  */
1060 static tree
1061 inline_forbidden_p (tree fndecl)
1062 {
1063   location_t saved_loc = input_location;
1064   tree ret = walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
1065                                            inline_forbidden_p_1, fndecl);
1066
1067   input_location = saved_loc;
1068   return ret;
1069 }
1070
1071 /* Returns nonzero if FN is a function that does not have any
1072    fundamental inline blocking properties.  */
1073
1074 static bool
1075 inlinable_function_p (tree fn)
1076 {
1077   bool inlinable = true;
1078
1079   /* If we've already decided this function shouldn't be inlined,
1080      there's no need to check again.  */
1081   if (DECL_UNINLINABLE (fn))
1082     return false;
1083
1084   /* See if there is any language-specific reason it cannot be
1085      inlined.  (It is important that this hook be called early because
1086      in C++ it may result in template instantiation.)
1087      If the function is not inlinable for language-specific reasons,
1088      it is left up to the langhook to explain why.  */
1089   inlinable = !lang_hooks.tree_inlining.cannot_inline_tree_fn (&fn);
1090
1091   /* If we don't have the function body available, we can't inline it.
1092      However, this should not be recorded since we also get here for
1093      forward declared inline functions.  Therefore, return at once.  */
1094   if (!DECL_SAVED_TREE (fn))
1095     return false;
1096
1097   /* If we're not inlining at all, then we cannot inline this function.  */
1098   else if (!flag_inline_trees)
1099     inlinable = false;
1100
1101   /* Only try to inline functions if DECL_INLINE is set.  This should be
1102      true for all functions declared `inline', and for all other functions
1103      as well with -finline-functions.
1104
1105      Don't think of disregarding DECL_INLINE when flag_inline_trees == 2;
1106      it's the front-end that must set DECL_INLINE in this case, because
1107      dwarf2out loses if a function that does not have DECL_INLINE set is
1108      inlined anyway.  That is why we have both DECL_INLINE and
1109      DECL_DECLARED_INLINE_P.  */
1110   /* FIXME: When flag_inline_trees dies, the check for flag_unit_at_a_time
1111             here should be redundant.  */
1112   else if (!DECL_INLINE (fn) && !flag_unit_at_a_time)
1113     inlinable = false;
1114
1115   else if (inline_forbidden_p (fn))
1116     {
1117       /* See if we should warn about uninlinable functions.  Previously,
1118          some of these warnings would be issued while trying to expand
1119          the function inline, but that would cause multiple warnings
1120          about functions that would for example call alloca.  But since
1121          this a property of the function, just one warning is enough.
1122          As a bonus we can now give more details about the reason why a
1123          function is not inlinable.
1124          We only warn for functions declared `inline' by the user.  */
1125       bool do_warning = (warn_inline
1126                          && DECL_INLINE (fn)
1127                          && DECL_DECLARED_INLINE_P (fn)
1128                          && !DECL_IN_SYSTEM_HEADER (fn));
1129
1130       if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)))
1131         sorry (inline_forbidden_reason, fn, fn);
1132       else if (do_warning)
1133         warning (inline_forbidden_reason, fn, fn);
1134
1135       inlinable = false;
1136     }
1137
1138   /* Squirrel away the result so that we don't have to check again.  */
1139   DECL_UNINLINABLE (fn) = !inlinable;
1140
1141   return inlinable;
1142 }
1143
1144 /* Used by estimate_num_insns.  Estimate number of instructions seen
1145    by given statement.  */
1146
1147 static tree
1148 estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
1149 {
1150   int *count = data;
1151   tree x = *tp;
1152
1153   if (IS_TYPE_OR_DECL_P (x))
1154     {
1155       *walk_subtrees = 0;
1156       return NULL;
1157     }
1158   /* Assume that constants and references counts nothing.  These should
1159      be majorized by amount of operations among them we count later
1160      and are common target of CSE and similar optimizations.  */
1161   else if (CONSTANT_CLASS_P (x) || REFERENCE_CLASS_P (x))
1162     return NULL;
1163
1164   switch (TREE_CODE (x))
1165     {
1166     /* Containers have no cost.  */
1167     case TREE_LIST:
1168     case TREE_VEC:
1169     case BLOCK:
1170     case COMPONENT_REF:
1171     case BIT_FIELD_REF:
1172     case INDIRECT_REF:
1173     case ARRAY_REF:
1174     case ARRAY_RANGE_REF:
1175     case OBJ_TYPE_REF:
1176     case EXC_PTR_EXPR: /* ??? */
1177     case FILTER_EXPR: /* ??? */
1178     case COMPOUND_EXPR:
1179     case BIND_EXPR:
1180     case WITH_CLEANUP_EXPR:
1181     case NOP_EXPR:
1182     case VIEW_CONVERT_EXPR:
1183     case SAVE_EXPR:
1184     case ADDR_EXPR:
1185     case COMPLEX_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 = first_rtl_op (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 = first_rtl_op (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 }