gcc/tree-inline.c

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