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