gcc/tree-nested.c

   1 /* Nested function decomposition for trees.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING.  If not, write to
  18    the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19    Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "function.h"
  29 #include "tree-dump.h"
  30 #include "tree-inline.h"
  31 #include "tree-gimple.h"
  32 #include "tree-iterator.h"
  33 #include "tree-flow.h"
  34 #include "cgraph.h"
  35 #include "expr.h"
  36 #include "langhooks.h"
  37 #include "ggc.h"
  38
  39
  40 /* The object of this pass is to lower the representation of a set of nested
  41    functions in order to expose all of the gory details of the various
  42    nonlocal references.  We want to do this sooner rather than later, in
  43    order to give us more freedom in emitting all of the functions in question.
  44
  45    Back in olden times, when gcc was young, we developed an insanely
  46    complicated scheme whereby variables which were referenced nonlocally
  47    were forced to live in the stack of the declaring function, and then
  48    the nested functions magically discovered where these variables were
  49    placed.  In order for this scheme to function properly, it required
  50    that the outer function be partially expanded, then we switch to
  51    compiling the inner function, and once done with those we switch back
  52    to compiling the outer function.  Such delicate ordering requirements
  53    makes it difficult to do whole translation unit optimizations
  54    involving such functions.
  55
  56    The implementation here is much more direct.  Everything that can be
  57    referenced by an inner function is a member of an explicitly created
  58    structure herein called the "nonlocal frame struct".  The incoming
  59    static chain for a nested function is a pointer to this struct in
  60    the parent.  In this way, we settle on known offsets from a known
  61    base, and so are decoupled from the logic that places objects in the
  62    function's stack frame.  More importantly, we don't have to wait for
  63    that to happen -- since the compilation of the inner function is no
  64    longer tied to a real stack frame, the nonlocal frame struct can be
  65    allocated anywhere.  Which means that the outer function is now
  66    inlinable.
  67
  68    Theory of operation here is very simple.  Iterate over all the
  69    statements in all the functions (depth first) several times,
  70    allocating structures and fields on demand.  In general we want to
  71    examine inner functions first, so that we can avoid making changes
  72    to outer functions which are unnecessary.
  73
  74    The order of the passes matters a bit, in that later passes will be
  75    skipped if it is discovered that the functions don't actually interact
  76    at all.  That is, they're nested in the lexical sense but could have
  77    been written as independent functions without change.  */
  78
  79
  80 struct var_map_elt GTY(())
  81 {
  82   tree old;
  83   tree new;
  84 };
  85
  86 struct nesting_info GTY ((chain_next ("%h.next")))
  87 {
  88   struct nesting_info *outer;
  89   struct nesting_info *inner;
  90   struct nesting_info *next;
  91
  92   htab_t GTY ((param_is (struct var_map_elt))) field_map;
  93   htab_t GTY ((param_is (struct var_map_elt))) var_map;
  94   bitmap suppress_expansion;
  95
  96   tree context;
  97   tree new_local_var_chain;
  98   tree debug_var_chain;
  99   tree frame_type;
 100   tree frame_decl;
 101   tree chain_field;
 102   tree chain_decl;
 103   tree nl_goto_field;
 104
 105   bool any_parm_remapped;
 106   bool any_tramp_created;
 107 };
 108
 109
 110 /* Hashing and equality functions for nesting_info->var_map.  */
 111
 112 static hashval_t
 113 var_map_hash (const void *x)
 114 {
 115   const struct var_map_elt *a = (const struct var_map_elt *) x;
 116   return htab_hash_pointer (a->old);
 117 }
 118
 119 static int
 120 var_map_eq (const void *x, const void *y)
 121 {
 122   const struct var_map_elt *a = (const struct var_map_elt *) x;
 123   const struct var_map_elt *b = (const struct var_map_elt *) y;
 124   return a->old == b->old;
 125 }
 126
 127 /* We're working in so many different function contexts simultaneously,
 128    that create_tmp_var is dangerous.  Prevent mishap.  */
 129 #define create_tmp_var cant_use_create_tmp_var_here_dummy
 130
 131 /* Like create_tmp_var, except record the variable for registration at
 132    the given nesting level.  */
 133
 134 static tree
 135 create_tmp_var_for (struct nesting_info *info, tree type, const char *prefix)
 136 {
 137   tree tmp_var;
 138
 139   /* If the type is of variable size or a type which must be created by the
 140      frontend, something is wrong.  Note that we explicitly allow
 141      incomplete types here, since we create them ourselves here.  */
 142   gcc_assert (!TREE_ADDRESSABLE (type));
 143   gcc_assert (!TYPE_SIZE_UNIT (type)
 144               || TREE_CODE (TYPE_SIZE_UNIT (type)) == INTEGER_CST);
 145
 146   tmp_var = create_tmp_var_raw (type, prefix);
 147   DECL_CONTEXT (tmp_var) = info->context;
 148   TREE_CHAIN (tmp_var) = info->new_local_var_chain;
 149   DECL_SEEN_IN_BIND_EXPR_P (tmp_var) = 1;
 150   if (TREE_CODE (type) == COMPLEX_TYPE)
 151     DECL_COMPLEX_GIMPLE_REG_P (tmp_var) = 1;
 152
 153   info->new_local_var_chain = tmp_var;
 154
 155   return tmp_var;
 156 }
 157
 158 /* Take the address of EXP to be used within function CONTEXT.
 159    Mark it for addressability as necessary.  */
 160
 161 tree
 162 build_addr (tree exp, tree context)
 163 {
 164   tree base = exp;
 165   tree save_context;
 166   tree retval;
 167
 168   while (handled_component_p (base))
 169     base = TREE_OPERAND (base, 0);
 170
 171   if (DECL_P (base))
 172     TREE_ADDRESSABLE (base) = 1;
 173
 174   /* Building the ADDR_EXPR will compute a set of properties for
 175      that ADDR_EXPR.  Those properties are unfortunately context
 176      specific.  ie, they are dependent on CURRENT_FUNCTION_DECL.
 177
 178      Temporarily set CURRENT_FUNCTION_DECL to the desired context,
 179      build the ADDR_EXPR, then restore CURRENT_FUNCTION_DECL.  That
 180      way the properties are for the ADDR_EXPR are computed properly.  */
 181   save_context = current_function_decl;
 182   current_function_decl = context;
 183   retval = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (exp)), exp);
 184   current_function_decl = save_context;;
 185   return retval;
 186 }
 187
 188 /* Insert FIELD into TYPE, sorted by alignment requirements.  */
 189
 190 void
 191 insert_field_into_struct (tree type, tree field)
 192 {
 193   tree *p;
 194
 195   DECL_CONTEXT (field) = type;
 196
 197   for (p = &TYPE_FIELDS (type); *p ; p = &TREE_CHAIN (*p))
 198     if (DECL_ALIGN (field) >= DECL_ALIGN (*p))
 199       break;
 200
 201   TREE_CHAIN (field) = *p;
 202   *p = field;
 203 }
 204
 205 /* Build or return the RECORD_TYPE that describes the frame state that is
 206    shared between INFO->CONTEXT and its nested functions.  This record will
 207    not be complete until finalize_nesting_tree; up until that point we'll
 208    be adding fields as necessary.
 209
 210    We also build the DECL that represents this frame in the function.  */
 211
 212 static tree
 213 get_frame_type (struct nesting_info *info)
 214 {
 215   tree type = info->frame_type;
 216   if (!type)
 217     {
 218       char *name;
 219
 220       type = make_node (RECORD_TYPE);
 221
 222       name = concat ("FRAME.",
 223                      IDENTIFIER_POINTER (DECL_NAME (info->context)),
 224                      NULL);
 225       TYPE_NAME (type) = get_identifier (name);
 226       free (name);
 227
 228       info->frame_type = type;
 229       info->frame_decl = create_tmp_var_for (info, type, "FRAME");
 230
 231       /* ??? Always make it addressable for now, since it is meant to
 232          be pointed to by the static chain pointer.  This pessimizes
 233          when it turns out that no static chains are needed because
 234          the nested functions referencing non-local variables are not
 235          reachable, but the true pessimization is to create the non-
 236          local frame structure in the first place.  */
 237       TREE_ADDRESSABLE (info->frame_decl) = 1;
 238     }
 239   return type;
 240 }
 241
 242 /* Return true if DECL should be referenced by pointer in the non-local
 243    frame structure.  */
 244
 245 static bool
 246 use_pointer_in_frame (tree decl)
 247 {
 248   if (TREE_CODE (decl) == PARM_DECL)
 249     {
 250       /* It's illegal to copy TREE_ADDRESSABLE, impossible to copy variable
 251          sized decls, and inefficient to copy large aggregates.  Don't bother
 252          moving anything but scalar variables.  */
 253       return AGGREGATE_TYPE_P (TREE_TYPE (decl));
 254     }
 255   else
 256     {
 257       /* Variable sized types make things "interesting" in the frame.  */
 258       return DECL_SIZE (decl) == NULL || !TREE_CONSTANT (DECL_SIZE (decl));
 259     }
 260 }
 261
 262 /* Given DECL, a non-locally accessed variable, find or create a field
 263    in the non-local frame structure for the given nesting context.  */
 264
 265 static tree
 266 lookup_field_for_decl (struct nesting_info *info, tree decl,
 267                        enum insert_option insert)
 268 {
 269   struct var_map_elt *elt, dummy;
 270   void **slot;
 271   tree field;
 272
 273   dummy.old = decl;
 274   slot = htab_find_slot (info->field_map, &dummy, insert);
 275   if (!slot)
 276     {
 277       gcc_assert (insert != INSERT);
 278       return NULL;
 279     }
 280   elt = (struct var_map_elt *) *slot;
 281
 282   if (!elt && insert == INSERT)
 283     {
 284       field = make_node (FIELD_DECL);
 285       DECL_NAME (field) = DECL_NAME (decl);
 286
 287       if (use_pointer_in_frame (decl))
 288         {
 289           TREE_TYPE (field) = build_pointer_type (TREE_TYPE (decl));
 290           DECL_ALIGN (field) = TYPE_ALIGN (TREE_TYPE (field));
 291           DECL_NONADDRESSABLE_P (field) = 1;
 292         }
 293       else
 294         {
 295           TREE_TYPE (field) = TREE_TYPE (decl);
 296           DECL_SOURCE_LOCATION (field) = DECL_SOURCE_LOCATION (decl);
 297           DECL_ALIGN (field) = DECL_ALIGN (decl);
 298           DECL_USER_ALIGN (field) = DECL_USER_ALIGN (decl);
 299           TREE_ADDRESSABLE (field) = TREE_ADDRESSABLE (decl);
 300           DECL_NONADDRESSABLE_P (field) = !TREE_ADDRESSABLE (decl);
 301           TREE_THIS_VOLATILE (field) = TREE_THIS_VOLATILE (decl);
 302         }
 303
 304       insert_field_into_struct (get_frame_type (info), field);
 305
 306       elt = GGC_NEW (struct var_map_elt);
 307       elt->old = decl;
 308       elt->new = field;
 309       *slot = elt;
 310
 311       if (TREE_CODE (decl) == PARM_DECL)
 312         info->any_parm_remapped = true;
 313     }
 314   else
 315     field = elt ? elt->new : NULL;
 316
 317   return field;
 318 }
 319
 320 /* Build or return the variable that holds the static chain within
 321    INFO->CONTEXT.  This variable may only be used within INFO->CONTEXT.  */
 322
 323 static tree
 324 get_chain_decl (struct nesting_info *info)
 325 {
 326   tree decl = info->chain_decl;
 327   if (!decl)
 328     {
 329       tree type;
 330
 331       type = get_frame_type (info->outer);
 332       type = build_pointer_type (type);
 333
 334       /* Note that this variable is *not* entered into any BIND_EXPR;
 335          the construction of this variable is handled specially in
 336          expand_function_start and initialize_inlined_parameters.
 337          Note also that it's represented as a parameter.  This is more
 338          close to the truth, since the initial value does come from
 339          the caller.  */
 340       decl = build_decl (PARM_DECL, create_tmp_var_name ("CHAIN"), type);
 341       DECL_ARTIFICIAL (decl) = 1;
 342       DECL_IGNORED_P (decl) = 1;
 343       TREE_USED (decl) = 1;
 344       DECL_CONTEXT (decl) = info->context;
 345       DECL_ARG_TYPE (decl) = type;
 346
 347       /* Tell tree-inline.c that we never write to this variable, so
 348          it can copy-prop the replacement value immediately.  */
 349       TREE_READONLY (decl) = 1;
 350
 351       info->chain_decl = decl;
 352     }
 353   return decl;
 354 }
 355
 356 /* Build or return the field within the non-local frame state that holds
 357    the static chain for INFO->CONTEXT.  This is the way to walk back up
 358    multiple nesting levels.  */
 359
 360 static tree
 361 get_chain_field (struct nesting_info *info)
 362 {
 363   tree field = info->chain_field;
 364   if (!field)
 365     {
 366       tree type = build_pointer_type (get_frame_type (info->outer));
 367
 368       field = make_node (FIELD_DECL);
 369       DECL_NAME (field) = get_identifier ("__chain");
 370       TREE_TYPE (field) = type;
 371       DECL_ALIGN (field) = TYPE_ALIGN (type);
 372       DECL_NONADDRESSABLE_P (field) = 1;
 373
 374       insert_field_into_struct (get_frame_type (info), field);
 375
 376       info->chain_field = field;
 377     }
 378   return field;
 379 }
 380
 381 /* Copy EXP into a temporary.  Allocate the temporary in the context of
 382    INFO and insert the initialization statement before TSI.  */
 383
 384 static tree
 385 init_tmp_var (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
 386 {
 387   tree t, stmt;
 388
 389   t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
 390   stmt = build2 (MODIFY_EXPR, TREE_TYPE (t), t, exp);
 391   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
 392   tsi_link_before (tsi, stmt, TSI_SAME_STMT);
 393
 394   return t;
 395 }
 396
 397 /* Similarly, but only do so to force EXP to satisfy is_gimple_val.  */
 398
 399 static tree
 400 tsi_gimplify_val (struct nesting_info *info, tree exp, tree_stmt_iterator *tsi)
 401 {
 402   if (is_gimple_val (exp))
 403     return exp;
 404   else
 405     return init_tmp_var (info, exp, tsi);
 406 }
 407
 408 /* Similarly, but copy from the temporary and insert the statement
 409    after the iterator.  */
 410
 411 static tree
 412 save_tmp_var (struct nesting_info *info, tree exp,
 413               tree_stmt_iterator *tsi)
 414 {
 415   tree t, stmt;
 416
 417   t = create_tmp_var_for (info, TREE_TYPE (exp), NULL);
 418   stmt = build2 (MODIFY_EXPR, TREE_TYPE (t), exp, t);
 419   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (tsi_stmt (*tsi)));
 420   tsi_link_after (tsi, stmt, TSI_SAME_STMT);
 421
 422   return t;
 423 }
 424
 425 /* Build or return the type used to represent a nested function trampoline.  */
 426
 427 static GTY(()) tree trampoline_type;
 428
 429 static tree
 430 get_trampoline_type (void)
 431 {
 432   tree record, t;
 433   unsigned align, size;
 434
 435   if (trampoline_type)
 436     return trampoline_type;
 437
 438   align = TRAMPOLINE_ALIGNMENT;
 439   size = TRAMPOLINE_SIZE;
 440
 441   /* If we won't be able to guarantee alignment simply via TYPE_ALIGN,
 442      then allocate extra space so that we can do dynamic alignment.  */
 443   if (align > STACK_BOUNDARY)
 444     {
 445       size += ((align/BITS_PER_UNIT) - 1) & -(STACK_BOUNDARY/BITS_PER_UNIT);
 446       align = STACK_BOUNDARY;
 447     }
 448
 449   t = build_index_type (build_int_cst (NULL_TREE, size - 1));
 450   t = build_array_type (char_type_node, t);
 451   t = build_decl (FIELD_DECL, get_identifier ("__data"), t);
 452   DECL_ALIGN (t) = align;
 453   DECL_USER_ALIGN (t) = 1;
 454
 455   record = make_node (RECORD_TYPE);
 456   TYPE_NAME (record) = get_identifier ("__builtin_trampoline");
 457   TYPE_FIELDS (record) = t;
 458   layout_type (record);
 459
 460   return record;
 461 }
 462
 463 /* Given DECL, a nested function, find or create a field in the non-local
 464    frame structure for a trampoline for this function.  */
 465
 466 static tree
 467 lookup_tramp_for_decl (struct nesting_info *info, tree decl,
 468                        enum insert_option insert)
 469 {
 470   struct var_map_elt *elt, dummy;
 471   void **slot;
 472   tree field;
 473
 474   dummy.old = decl;
 475   slot = htab_find_slot (info->var_map, &dummy, insert);
 476   if (!slot)
 477     {
 478       gcc_assert (insert != INSERT);
 479       return NULL;
 480     }
 481   elt = (struct var_map_elt *) *slot;
 482
 483   if (!elt && insert == INSERT)
 484     {
 485       field = make_node (FIELD_DECL);
 486       DECL_NAME (field) = DECL_NAME (decl);
 487       TREE_TYPE (field) = get_trampoline_type ();
 488       TREE_ADDRESSABLE (field) = 1;
 489
 490       insert_field_into_struct (get_frame_type (info), field);
 491
 492       elt = GGC_NEW (struct var_map_elt);
 493       elt->old = decl;
 494       elt->new = field;
 495       *slot = elt;
 496
 497       info->any_tramp_created = true;
 498     }
 499   else
 500     field = elt ? elt->new : NULL;
 501
 502   return field;
 503 }
 504
 505 /* Build or return the field within the non-local frame state that holds
 506    the non-local goto "jmp_buf".  The buffer itself is maintained by the
 507    rtl middle-end as dynamic stack space is allocated.  */
 508
 509 static tree
 510 get_nl_goto_field (struct nesting_info *info)
 511 {
 512   tree field = info->nl_goto_field;
 513   if (!field)
 514     {
 515       unsigned size;
 516       tree type;
 517
 518       /* For __builtin_nonlocal_goto, we need N words.  The first is the
 519          frame pointer, the rest is for the target's stack pointer save
 520          area.  The number of words is controlled by STACK_SAVEAREA_MODE;
 521          not the best interface, but it'll do for now.  */
 522       if (Pmode == ptr_mode)
 523         type = ptr_type_node;
 524       else
 525         type = lang_hooks.types.type_for_mode (Pmode, 1);
 526
 527       size = GET_MODE_SIZE (STACK_SAVEAREA_MODE (SAVE_NONLOCAL));
 528       size = size / GET_MODE_SIZE (Pmode);
 529       size = size + 1;
 530
 531       type = build_array_type
 532         (type, build_index_type (build_int_cst (NULL_TREE, size)));
 533
 534       field = make_node (FIELD_DECL);
 535       DECL_NAME (field) = get_identifier ("__nl_goto_buf");
 536       TREE_TYPE (field) = type;
 537       DECL_ALIGN (field) = TYPE_ALIGN (type);
 538       TREE_ADDRESSABLE (field) = 1;
 539
 540       insert_field_into_struct (get_frame_type (info), field);
 541
 542       info->nl_goto_field = field;
 543     }
 544
 545   return field;
 546 }
 547 \f
 548 /* Iterate over all sub-statements of *TP calling walk_tree with
 549    WI->CALLBACK for every sub-expression in each statement found.  */
 550
 551 void
 552 walk_stmts (struct walk_stmt_info *wi, tree *tp)
 553 {
 554   tree t = *tp;
 555   int walk_subtrees;
 556
 557   if (!t)
 558     return;
 559
 560   if (wi->want_locations && EXPR_HAS_LOCATION (t))
 561     input_location = EXPR_LOCATION (t);
 562
 563   switch (TREE_CODE (t))
 564     {
 565     case STATEMENT_LIST:
 566       {
 567         tree_stmt_iterator i;
 568         for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
 569           {
 570             wi->tsi = i;
 571             walk_stmts (wi, tsi_stmt_ptr (i));
 572           }
 573       }
 574       break;
 575
 576     case COND_EXPR:
 577       walk_tree (&COND_EXPR_COND (t), wi->callback, wi, NULL);
 578       walk_stmts (wi, &COND_EXPR_THEN (t));
 579       walk_stmts (wi, &COND_EXPR_ELSE (t));
 580       break;
 581     case CATCH_EXPR:
 582       walk_stmts (wi, &CATCH_BODY (t));
 583       break;
 584     case EH_FILTER_EXPR:
 585       walk_stmts (wi, &EH_FILTER_FAILURE (t));
 586       break;
 587     case TRY_CATCH_EXPR:
 588     case TRY_FINALLY_EXPR:
 589       walk_stmts (wi, &TREE_OPERAND (t, 0));
 590       walk_stmts (wi, &TREE_OPERAND (t, 1));
 591       break;
 592
 593     case BIND_EXPR:
 594       if (wi->want_bind_expr)
 595         {
 596           walk_subtrees = 1;
 597           wi->callback (tp, &walk_subtrees, wi);
 598           if (!walk_subtrees)
 599             break;
 600         }
 601       walk_stmts (wi, &BIND_EXPR_BODY (t));
 602       break;
 603
 604     case RETURN_EXPR:
 605       if (wi->want_return_expr)
 606         {
 607           walk_subtrees = 1;
 608           wi->callback (tp, &walk_subtrees, wi);
 609           if (!walk_subtrees)
 610             break;
 611         }
 612       walk_stmts (wi, &TREE_OPERAND (t, 0));
 613       break;
 614
 615     case MODIFY_EXPR:
 616       /* A formal temporary lhs may use a COMPONENT_REF rhs.  */
 617       wi->val_only = !is_gimple_formal_tmp_var (TREE_OPERAND (t, 0));
 618       walk_tree (&TREE_OPERAND (t, 1), wi->callback, wi, NULL);
 619
 620       /* If the rhs is appropriate for a memory, we may use a
 621          COMPONENT_REF on the lhs.  */
 622       wi->val_only = !is_gimple_mem_rhs (TREE_OPERAND (t, 1));
 623       wi->is_lhs = true;
 624       walk_tree (&TREE_OPERAND (t, 0), wi->callback, wi, NULL);
 625
 626       wi->val_only = true;
 627       wi->is_lhs = false;
 628       break;
 629
 630     default:
 631       wi->val_only = true;
 632       walk_tree (tp, wi->callback, wi, NULL);
 633       break;
 634     }
 635 }
 636
 637 /* Invoke CALLBACK on all statements of *STMT_P.  */
 638
 639 static void
 640 walk_body (walk_tree_fn callback, struct nesting_info *info, tree *stmt_p)
 641 {
 642   struct walk_stmt_info wi;
 643
 644   memset (&wi, 0, sizeof (wi));
 645   wi.callback = callback;
 646   wi.info = info;
 647   wi.val_only = true;
 648
 649   walk_stmts (&wi, stmt_p);
 650 }
 651
 652 /* Invoke CALLBACK on all statements of INFO->CONTEXT.  */
 653
 654 static inline void
 655 walk_function (walk_tree_fn callback, struct nesting_info *info)
 656 {
 657   walk_body (callback, info, &DECL_SAVED_TREE (info->context));
 658 }
 659
 660 /* Similarly for ROOT and all functions nested underneath, depth first.  */
 661
 662 static void
 663 walk_all_functions (walk_tree_fn callback, struct nesting_info *root)
 664 {
 665   do
 666     {
 667       if (root->inner)
 668         walk_all_functions (callback, root->inner);
 669       walk_function (callback, root);
 670       root = root->next;
 671     }
 672   while (root);
 673 }
 674 \f
 675 /* We have to check for a fairly pathological case.  The operands of function
 676    nested function are to be interpreted in the context of the enclosing
 677    function.  So if any are variably-sized, they will get remapped when the
 678    enclosing function is inlined.  But that remapping would also have to be
 679    done in the types of the PARM_DECLs of the nested function, meaning the
 680    argument types of that function will disagree with the arguments in the
 681    calls to that function.  So we'd either have to make a copy of the nested
 682    function corresponding to each time the enclosing function was inlined or
 683    add a VIEW_CONVERT_EXPR to each such operand for each call to the nested
 684    function.  The former is not practical.  The latter would still require
 685    detecting this case to know when to add the conversions.  So, for now at
 686    least, we don't inline such an enclosing function.
 687
 688    We have to do that check recursively, so here return indicating whether
 689    FNDECL has such a nested function.  ORIG_FN is the function we were
 690    trying to inline to use for checking whether any argument is variably
 691    modified by anything in it.
 692
 693    It would be better to do this in tree-inline.c so that we could give
 694    the appropriate warning for why a function can't be inlined, but that's
 695    too late since the nesting structure has already been flattened and
 696    adding a flag just to record this fact seems a waste of a flag.  */
 697
 698 static bool
 699 check_for_nested_with_variably_modified (tree fndecl, tree orig_fndecl)
 700 {
 701   struct cgraph_node *cgn = cgraph_node (fndecl);
 702   tree arg;
 703
 704   for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
 705     {
 706       for (arg = DECL_ARGUMENTS (cgn->decl); arg; arg = TREE_CHAIN (arg))
 707         if (variably_modified_type_p (TREE_TYPE (arg), 0), orig_fndecl)
 708           return true;
 709
 710       if (check_for_nested_with_variably_modified (cgn->decl, orig_fndecl))
 711         return true;
 712     }
 713
 714   return false;
 715 }
 716
 717 /* Construct our local datastructure describing the function nesting
 718    tree rooted by CGN.  */
 719
 720 static struct nesting_info *
 721 create_nesting_tree (struct cgraph_node *cgn)
 722 {
 723   struct nesting_info *info = GGC_CNEW (struct nesting_info);
 724   info->field_map = htab_create_ggc (7, var_map_hash, var_map_eq, ggc_free);
 725   info->var_map = htab_create_ggc (7, var_map_hash, var_map_eq, ggc_free);
 726   info->suppress_expansion = BITMAP_GGC_ALLOC ();
 727   info->context = cgn->decl;
 728
 729   for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
 730     {
 731       struct nesting_info *sub = create_nesting_tree (cgn);
 732       sub->outer = info;
 733       sub->next = info->inner;
 734       info->inner = sub;
 735     }
 736
 737   /* See discussion at check_for_nested_with_variably_modified for a
 738      discussion of why this has to be here.  */
 739   if (check_for_nested_with_variably_modified (info->context, info->context))
 740     DECL_UNINLINABLE (info->context) = true;
 741
 742   return info;
 743 }
 744
 745 /* Return an expression computing the static chain for TARGET_CONTEXT
 746    from INFO->CONTEXT.  Insert any necessary computations before TSI.  */
 747
 748 static tree
 749 get_static_chain (struct nesting_info *info, tree target_context,
 750                   tree_stmt_iterator *tsi)
 751 {
 752   struct nesting_info *i;
 753   tree x;
 754
 755   if (info->context == target_context)
 756     {
 757       x = build_addr (info->frame_decl, target_context);
 758     }
 759   else
 760     {
 761       x = get_chain_decl (info);
 762
 763       for (i = info->outer; i->context != target_context; i = i->outer)
 764         {
 765           tree field = get_chain_field (i);
 766
 767           x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 768           x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
 769           x = init_tmp_var (info, x, tsi);
 770         }
 771     }
 772
 773   return x;
 774 }
 775
 776 /* Return an expression referencing FIELD from TARGET_CONTEXT's non-local
 777    frame as seen from INFO->CONTEXT.  Insert any necessary computations
 778    before TSI.  */
 779
 780 static tree
 781 get_frame_field (struct nesting_info *info, tree target_context,
 782                  tree field, tree_stmt_iterator *tsi)
 783 {
 784   struct nesting_info *i;
 785   tree x;
 786
 787   if (info->context == target_context)
 788     {
 789       /* Make sure frame_decl gets created.  */
 790       (void) get_frame_type (info);
 791       x = info->frame_decl;
 792     }
 793   else
 794     {
 795       x = get_chain_decl (info);
 796
 797       for (i = info->outer; i->context != target_context; i = i->outer)
 798         {
 799           tree field = get_chain_field (i);
 800
 801           x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 802           x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
 803           x = init_tmp_var (info, x, tsi);
 804         }
 805
 806       x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 807     }
 808
 809   x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
 810   return x;
 811 }
 812
 813 /* A subroutine of convert_nonlocal_reference.  Create a local variable
 814    in the nested function with DECL_VALUE_EXPR set to reference the true
 815    variable in the parent function.  This is used both for debug info
 816    and in OpenMP lowering.  */
 817
 818 static tree
 819 get_nonlocal_debug_decl (struct nesting_info *info, tree decl)
 820 {
 821   struct var_map_elt *elt, dummy;
 822   tree target_context;
 823   struct nesting_info *i;
 824   tree x, field, new_decl;
 825   void **slot;
 826
 827   dummy.old = decl;
 828   slot = htab_find_slot (info->var_map, &dummy, INSERT);
 829   elt = *slot;
 830
 831   if (elt)
 832     return elt->new;
 833
 834   target_context = decl_function_context (decl);
 835
 836   /* A copy of the code in get_frame_field, but without the temporaries.  */
 837   if (info->context == target_context)
 838     {
 839       /* Make sure frame_decl gets created.  */
 840       (void) get_frame_type (info);
 841       x = info->frame_decl;
 842       i = info;
 843     }
 844   else
 845     {
 846       x = get_chain_decl (info);
 847       for (i = info->outer; i->context != target_context; i = i->outer)
 848         {
 849           field = get_chain_field (i);
 850           x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 851           x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
 852         }
 853       x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 854     }
 855
 856   field = lookup_field_for_decl (i, decl, INSERT);
 857   x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
 858   if (use_pointer_in_frame (decl))
 859     x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 860
 861   /* ??? We should be remapping types as well, surely.  */
 862   new_decl = build_decl (VAR_DECL, DECL_NAME (decl), TREE_TYPE (decl));
 863   DECL_CONTEXT (new_decl) = info->context;
 864   DECL_SOURCE_LOCATION (new_decl) = DECL_SOURCE_LOCATION (decl);
 865   DECL_ARTIFICIAL (new_decl) = DECL_ARTIFICIAL (decl);
 866   DECL_IGNORED_P (new_decl) = DECL_IGNORED_P (decl);
 867   TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (decl);
 868   TREE_SIDE_EFFECTS (new_decl) = TREE_SIDE_EFFECTS (decl);
 869   TREE_READONLY (new_decl) = TREE_READONLY (decl);
 870   TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (decl);
 871   DECL_SEEN_IN_BIND_EXPR_P (new_decl) = 1;
 872
 873   SET_DECL_VALUE_EXPR (new_decl, x);
 874   DECL_HAS_VALUE_EXPR_P (new_decl) = 1;
 875
 876   elt = ggc_alloc (sizeof (*elt));
 877   elt->old = decl;
 878   elt->new = new_decl;
 879   *slot = elt;
 880
 881   TREE_CHAIN (new_decl) = info->debug_var_chain;
 882   info->debug_var_chain = new_decl;
 883
 884   return new_decl;
 885 }
 886
 887 /* Called via walk_function+walk_tree, rewrite all references to VAR
 888    and PARM_DECLs that belong to outer functions.
 889
 890    The rewrite will involve some number of structure accesses back up
 891    the static chain.  E.g. for a variable FOO up one nesting level it'll
 892    be CHAIN->FOO.  For two levels it'll be CHAIN->__chain->FOO.  Further
 893    indirections apply to decls for which use_pointer_in_frame is true.  */
 894
 895 static bool convert_nonlocal_omp_clauses (tree *, struct walk_stmt_info *);
 896
 897 static tree
 898 convert_nonlocal_reference (tree *tp, int *walk_subtrees, void *data)
 899 {
 900   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 901   struct nesting_info *info = wi->info;
 902   tree t = *tp;
 903   tree save_local_var_chain;
 904   bitmap save_suppress;
 905
 906   *walk_subtrees = 0;
 907   switch (TREE_CODE (t))
 908     {
 909     case VAR_DECL:
 910       /* Non-automatic variables are never processed.  */
 911       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
 912         break;
 913       /* FALLTHRU */
 914
 915     case PARM_DECL:
 916       if (decl_function_context (t) != info->context)
 917         {
 918           tree x;
 919           wi->changed = true;
 920
 921           x = get_nonlocal_debug_decl (info, t);
 922           if (!bitmap_bit_p (info->suppress_expansion, DECL_UID (t)))
 923             {
 924               tree target_context = decl_function_context (t);
 925               struct nesting_info *i;
 926               for (i = info->outer; i->context != target_context; i = i->outer)
 927                 continue;
 928               x = lookup_field_for_decl (i, t, INSERT);
 929               x = get_frame_field (info, target_context, x, &wi->tsi);
 930               if (use_pointer_in_frame (t))
 931                 {
 932                   x = init_tmp_var (info, x, &wi->tsi);
 933                   x = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (x)), x);
 934                 }
 935             }
 936
 937           if (wi->val_only)
 938             {
 939               if (wi->is_lhs)
 940                 x = save_tmp_var (info, x, &wi->tsi);
 941               else
 942                 x = init_tmp_var (info, x, &wi->tsi);
 943             }
 944
 945           *tp = x;
 946         }
 947       break;
 948
 949     case GOTO_EXPR:
 950       /* Don't walk non-local gotos for now.  */
 951       if (TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL)
 952         {
 953           *walk_subtrees = 1;
 954           wi->val_only = true;
 955           wi->is_lhs = false;
 956         }
 957       break;
 958
 959     case LABEL_DECL:
 960       /* We're taking the address of a label from a parent function, but
 961          this is not itself a non-local goto.  Mark the label such that it
 962          will not be deleted, much as we would with a label address in
 963          static storage.  */
 964       if (decl_function_context (t) != info->context)
 965         FORCED_LABEL (t) = 1;
 966       break;
 967
 968     case ADDR_EXPR:
 969       {
 970         bool save_val_only = wi->val_only;
 971
 972         wi->val_only = false;
 973         wi->is_lhs = false;
 974         wi->changed = false;
 975         walk_tree (&TREE_OPERAND (t, 0), convert_nonlocal_reference, wi, NULL);
 976         wi->val_only = true;
 977
 978         if (wi->changed)
 979           {
 980             tree save_context;
 981
 982             /* If we changed anything, then TREE_INVARIANT is be wrong,
 983                since we're no longer directly referencing a decl.  */
 984             save_context = current_function_decl;
 985             current_function_decl = info->context;
 986             recompute_tree_invariant_for_addr_expr (t);
 987             current_function_decl = save_context;
 988
 989             /* If the callback converted the address argument in a context
 990                where we only accept variables (and min_invariant, presumably),
 991                then compute the address into a temporary.  */
 992             if (save_val_only)
 993               *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
 994           }
 995       }
 996       break;
 997
 998     case REALPART_EXPR:
 999     case IMAGPART_EXPR:
1000     case COMPONENT_REF:
1001     case ARRAY_REF:
1002     case ARRAY_RANGE_REF:
1003     case BIT_FIELD_REF:
1004       /* Go down this entire nest and just look at the final prefix and
1005          anything that describes the references.  Otherwise, we lose track
1006          of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value.  */
1007       wi->val_only = true;
1008       wi->is_lhs = false;
1009       for (; handled_component_p (t); tp = &TREE_OPERAND (t, 0), t = *tp)
1010         {
1011           if (TREE_CODE (t) == COMPONENT_REF)
1012             walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
1013                        NULL);
1014           else if (TREE_CODE (t) == ARRAY_REF
1015                    || TREE_CODE (t) == ARRAY_RANGE_REF)
1016             {
1017               walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
1018                          NULL);
1019               walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
1020                          NULL);
1021               walk_tree (&TREE_OPERAND (t, 3), convert_nonlocal_reference, wi,
1022                          NULL);
1023             }
1024           else if (TREE_CODE (t) == BIT_FIELD_REF)
1025             {
1026               walk_tree (&TREE_OPERAND (t, 1), convert_nonlocal_reference, wi,
1027                          NULL);
1028               walk_tree (&TREE_OPERAND (t, 2), convert_nonlocal_reference, wi,
1029                          NULL);
1030             }
1031         }
1032       wi->val_only = false;
1033       walk_tree (tp, convert_nonlocal_reference, wi, NULL);
1034       break;
1035
1036     case OMP_PARALLEL:
1037       save_suppress = info->suppress_expansion;
1038       if (convert_nonlocal_omp_clauses (&OMP_PARALLEL_CLAUSES (t), wi))
1039         {
1040           tree c, decl;
1041           decl = get_chain_decl (info);
1042           c = build_omp_clause (OMP_CLAUSE_FIRSTPRIVATE);
1043           OMP_CLAUSE_DECL (c) = decl;
1044           OMP_CLAUSE_CHAIN (c) = OMP_PARALLEL_CLAUSES (t);
1045           OMP_PARALLEL_CLAUSES (t) = c;
1046         }
1047
1048       save_local_var_chain = info->new_local_var_chain;
1049       info->new_local_var_chain = NULL;
1050
1051       walk_body (convert_nonlocal_reference, info, &OMP_PARALLEL_BODY (t));
1052
1053       if (info->new_local_var_chain)
1054         declare_vars (info->new_local_var_chain, OMP_PARALLEL_BODY (t), false);
1055       info->new_local_var_chain = save_local_var_chain;
1056       info->suppress_expansion = save_suppress;
1057       break;
1058
1059     case OMP_FOR:
1060     case OMP_SECTIONS:
1061     case OMP_SINGLE:
1062       save_suppress = info->suppress_expansion;
1063       convert_nonlocal_omp_clauses (&OMP_CLAUSES (t), wi);
1064       walk_body (convert_nonlocal_reference, info, &OMP_BODY (t));
1065       info->suppress_expansion = save_suppress;
1066       break;
1067
1068     case OMP_SECTION:
1069     case OMP_MASTER:
1070     case OMP_ORDERED:
1071       walk_body (convert_nonlocal_reference, info, &OMP_BODY (t));
1072       break;
1073
1074     default:
1075       if (!IS_TYPE_OR_DECL_P (t))
1076         {
1077           *walk_subtrees = 1;
1078           wi->val_only = true;
1079           wi->is_lhs = false;
1080         }
1081       break;
1082     }
1083
1084   return NULL_TREE;
1085 }
1086
1087 static bool
1088 convert_nonlocal_omp_clauses (tree *pclauses, struct walk_stmt_info *wi)
1089 {
1090   struct nesting_info *info = wi->info;
1091   bool need_chain = false;
1092   tree clause, decl;
1093   int dummy;
1094   bitmap new_suppress;
1095
1096   new_suppress = BITMAP_GGC_ALLOC ();
1097   bitmap_copy (new_suppress, info->suppress_expansion);
1098
1099   for (clause = *pclauses; clause ; clause = OMP_CLAUSE_CHAIN (clause))
1100     {
1101       switch (OMP_CLAUSE_CODE (clause))
1102         {
1103         case OMP_CLAUSE_PRIVATE:
1104         case OMP_CLAUSE_FIRSTPRIVATE:
1105         case OMP_CLAUSE_LASTPRIVATE:
1106         case OMP_CLAUSE_REDUCTION:
1107         case OMP_CLAUSE_COPYPRIVATE:
1108         case OMP_CLAUSE_SHARED:
1109           decl = OMP_CLAUSE_DECL (clause);
1110           if (decl_function_context (decl) != info->context)
1111             {
1112               bitmap_set_bit (new_suppress, DECL_UID (decl));
1113               OMP_CLAUSE_DECL (clause) = get_nonlocal_debug_decl (info, decl);
1114               need_chain = true;
1115             }
1116           break;
1117
1118         case OMP_CLAUSE_SCHEDULE:
1119           if (OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (clause) == NULL)
1120             break;
1121           /* FALLTHRU */
1122         case OMP_CLAUSE_IF:
1123         case OMP_CLAUSE_NUM_THREADS:
1124           wi->val_only = true;
1125           wi->is_lhs = false;
1126           convert_nonlocal_reference (&OMP_CLAUSE_OPERAND (clause, 0), &dummy,
1127                                       wi);
1128           break;
1129
1130         case OMP_CLAUSE_NOWAIT:
1131         case OMP_CLAUSE_ORDERED:
1132         case OMP_CLAUSE_DEFAULT:
1133         case OMP_CLAUSE_COPYIN:
1134           break;
1135
1136         default:
1137           gcc_unreachable ();
1138         }
1139     }
1140
1141   info->suppress_expansion = new_suppress;
1142
1143   return need_chain;
1144 }
1145
1146 /* A subroutine of convert_local_reference.  Create a local variable
1147    in the parent function with DECL_VALUE_EXPR set to reference the
1148    field in FRAME.  This is used both for debug info and in OpenMP
1149    lowering.  */
1150
1151 static tree
1152 get_local_debug_decl (struct nesting_info *info, tree decl, tree field)
1153 {
1154   struct var_map_elt *elt, dummy;
1155   tree x, new_decl;
1156   void **slot;
1157
1158   dummy.old = decl;
1159   slot = htab_find_slot (info->var_map, &dummy, INSERT);
1160   elt = *slot;
1161
1162   if (elt)
1163     return elt->new;
1164
1165   /* Make sure frame_decl gets created.  */
1166   (void) get_frame_type (info);
1167   x = info->frame_decl;
1168   x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
1169
1170   new_decl = build_decl (VAR_DECL, DECL_NAME (decl), TREE_TYPE (decl));
1171   DECL_CONTEXT (new_decl) = info->context;
1172   DECL_SOURCE_LOCATION (new_decl) = DECL_SOURCE_LOCATION (decl);
1173   DECL_ARTIFICIAL (new_decl) = DECL_ARTIFICIAL (decl);
1174   DECL_IGNORED_P (new_decl) = DECL_IGNORED_P (decl);
1175   TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (decl);
1176   TREE_SIDE_EFFECTS (new_decl) = TREE_SIDE_EFFECTS (decl);
1177   TREE_READONLY (new_decl) = TREE_READONLY (decl);
1178   TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (decl);
1179   DECL_SEEN_IN_BIND_EXPR_P (new_decl) = 1;
1180
1181   SET_DECL_VALUE_EXPR (new_decl, x);
1182   DECL_HAS_VALUE_EXPR_P (new_decl) = 1;
1183
1184   elt = ggc_alloc (sizeof (*elt));
1185   elt->old = decl;
1186   elt->new = new_decl;
1187   *slot = elt;
1188
1189   TREE_CHAIN (new_decl) = info->debug_var_chain;
1190   info->debug_var_chain = new_decl;
1191
1192   /* Do not emit debug info twice.  */
1193   DECL_IGNORED_P (decl) = 1;
1194
1195   return new_decl;
1196 }
1197
1198 /* Called via walk_function+walk_tree, rewrite all references to VAR
1199    and PARM_DECLs that were referenced by inner nested functions.
1200    The rewrite will be a structure reference to the local frame variable.  */
1201
1202 static bool convert_local_omp_clauses (tree *, struct walk_stmt_info *);
1203
1204 static tree
1205 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
1206 {
1207   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1208   struct nesting_info *info = wi->info;
1209   tree t = *tp, field, x;
1210   bool save_val_only;
1211   tree save_local_var_chain;
1212   bitmap save_suppress;
1213
1214   *walk_subtrees = 0;
1215   switch (TREE_CODE (t))
1216     {
1217     case VAR_DECL:
1218       /* Non-automatic variables are never processed.  */
1219       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
1220         break;
1221       /* FALLTHRU */
1222
1223     case PARM_DECL:
1224       if (decl_function_context (t) == info->context)
1225         {
1226           /* If we copied a pointer to the frame, then the original decl
1227              is used unchanged in the parent function.  */
1228           if (use_pointer_in_frame (t))
1229             break;
1230
1231           /* No need to transform anything if no child references the
1232              variable.  */
1233           field = lookup_field_for_decl (info, t, NO_INSERT);
1234           if (!field)
1235             break;
1236           wi->changed = true;
1237
1238           x = get_local_debug_decl (info, t, field);
1239           if (!bitmap_bit_p (info->suppress_expansion, DECL_UID (t)))
1240             x = get_frame_field (info, info->context, field, &wi->tsi);
1241
1242           if (wi->val_only)
1243             {
1244               if (wi->is_lhs)
1245                 x = save_tmp_var (info, x, &wi->tsi);
1246               else
1247                 x = init_tmp_var (info, x, &wi->tsi);
1248             }
1249
1250           *tp = x;
1251         }
1252       break;
1253
1254     case ADDR_EXPR:
1255       save_val_only = wi->val_only;
1256       wi->val_only = false;
1257       wi->is_lhs = false;
1258       wi->changed = false;
1259       walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
1260       wi->val_only = save_val_only;
1261
1262       /* If we converted anything ... */
1263       if (wi->changed)
1264         {
1265           tree save_context;
1266
1267           /* Then the frame decl is now addressable.  */
1268           TREE_ADDRESSABLE (info->frame_decl) = 1;
1269
1270           save_context = current_function_decl;
1271           current_function_decl = info->context;
1272           recompute_tree_invariant_for_addr_expr (t);
1273           current_function_decl = save_context;
1274
1275           /* If we are in a context where we only accept values, then
1276              compute the address into a temporary.  */
1277           if (save_val_only)
1278             *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
1279         }
1280       break;
1281
1282     case REALPART_EXPR:
1283     case IMAGPART_EXPR:
1284     case COMPONENT_REF:
1285     case ARRAY_REF:
1286     case ARRAY_RANGE_REF:
1287     case BIT_FIELD_REF:
1288       /* Go down this entire nest and just look at the final prefix and
1289          anything that describes the references.  Otherwise, we lose track
1290          of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value.  */
1291       save_val_only = wi->val_only;
1292       wi->val_only = true;
1293       wi->is_lhs = false;
1294       for (; handled_component_p (t); tp = &TREE_OPERAND (t, 0), t = *tp)
1295         {
1296           if (TREE_CODE (t) == COMPONENT_REF)
1297             walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1298                        NULL);
1299           else if (TREE_CODE (t) == ARRAY_REF
1300                    || TREE_CODE (t) == ARRAY_RANGE_REF)
1301             {
1302               walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1303                          NULL);
1304               walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1305                          NULL);
1306               walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi,
1307                          NULL);
1308             }
1309           else if (TREE_CODE (t) == BIT_FIELD_REF)
1310             {
1311               walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1312                          NULL);
1313               walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1314                          NULL);
1315             }
1316         }
1317       wi->val_only = false;
1318       walk_tree (tp, convert_local_reference, wi, NULL);
1319       wi->val_only = save_val_only;
1320       break;
1321
1322     case OMP_PARALLEL:
1323       save_suppress = info->suppress_expansion;
1324       if (convert_local_omp_clauses (&OMP_PARALLEL_CLAUSES (t), wi))
1325         {
1326           tree c;
1327           (void) get_frame_type (info);
1328           c = build_omp_clause (OMP_CLAUSE_SHARED);
1329           OMP_CLAUSE_DECL (c) = info->frame_decl;
1330           OMP_CLAUSE_CHAIN (c) = OMP_PARALLEL_CLAUSES (t);
1331           OMP_PARALLEL_CLAUSES (t) = c;
1332         }
1333
1334       save_local_var_chain = info->new_local_var_chain;
1335       info->new_local_var_chain = NULL;
1336
1337       walk_body (convert_local_reference, info, &OMP_PARALLEL_BODY (t));
1338
1339       if (info->new_local_var_chain)
1340         declare_vars (info->new_local_var_chain, OMP_PARALLEL_BODY (t), false);
1341       info->new_local_var_chain = save_local_var_chain;
1342       info->suppress_expansion = save_suppress;
1343       break;
1344
1345     case OMP_FOR:
1346     case OMP_SECTIONS:
1347     case OMP_SINGLE:
1348       save_suppress = info->suppress_expansion;
1349       convert_local_omp_clauses (&OMP_CLAUSES (t), wi);
1350       walk_body (convert_local_reference, info, &OMP_BODY (t));
1351       info->suppress_expansion = save_suppress;
1352       break;
1353
1354     case OMP_SECTION:
1355     case OMP_MASTER:
1356     case OMP_ORDERED:
1357       walk_body (convert_local_reference, info, &OMP_BODY (t));
1358       break;
1359
1360     default:
1361       if (!IS_TYPE_OR_DECL_P (t))
1362         {
1363           *walk_subtrees = 1;
1364           wi->val_only = true;
1365           wi->is_lhs = false;
1366         }
1367       break;
1368     }
1369
1370   return NULL_TREE;
1371 }
1372
1373 static bool
1374 convert_local_omp_clauses (tree *pclauses, struct walk_stmt_info *wi)
1375 {
1376   struct nesting_info *info = wi->info;
1377   bool need_frame = false;
1378   tree clause, decl;
1379   int dummy;
1380   bitmap new_suppress;
1381
1382   new_suppress = BITMAP_GGC_ALLOC ();
1383   bitmap_copy (new_suppress, info->suppress_expansion);
1384
1385   for (clause = *pclauses; clause ; clause = OMP_CLAUSE_CHAIN (clause))
1386     {
1387       switch (OMP_CLAUSE_CODE (clause))
1388         {
1389         case OMP_CLAUSE_PRIVATE:
1390         case OMP_CLAUSE_FIRSTPRIVATE:
1391         case OMP_CLAUSE_LASTPRIVATE:
1392         case OMP_CLAUSE_REDUCTION:
1393         case OMP_CLAUSE_COPYPRIVATE:
1394         case OMP_CLAUSE_SHARED:
1395           decl = OMP_CLAUSE_DECL (clause);
1396           if (decl_function_context (decl) == info->context
1397               && !use_pointer_in_frame (decl))
1398             {
1399               tree field = lookup_field_for_decl (info, decl, NO_INSERT);
1400               if (field)
1401                 {
1402                   bitmap_set_bit (new_suppress, DECL_UID (decl));
1403                   OMP_CLAUSE_DECL (clause)
1404                     = get_local_debug_decl (info, decl, field);
1405                   need_frame = true;
1406                 }
1407             }
1408           break;
1409
1410         case OMP_CLAUSE_SCHEDULE:
1411           if (OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (clause) == NULL)
1412             break;
1413           /* FALLTHRU */
1414         case OMP_CLAUSE_IF:
1415         case OMP_CLAUSE_NUM_THREADS:
1416           wi->val_only = true;
1417           wi->is_lhs = false;
1418           convert_local_reference (&OMP_CLAUSE_OPERAND (clause, 0), &dummy, wi);
1419           break;
1420
1421         case OMP_CLAUSE_NOWAIT:
1422         case OMP_CLAUSE_ORDERED:
1423         case OMP_CLAUSE_DEFAULT:
1424         case OMP_CLAUSE_COPYIN:
1425           break;
1426
1427         default:
1428           gcc_unreachable ();
1429         }
1430     }
1431
1432   info->suppress_expansion = new_suppress;
1433
1434   return need_frame;
1435 }
1436
1437 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
1438    reference labels from outer functions.  The rewrite will be a
1439    call to __builtin_nonlocal_goto.  */
1440
1441 static tree
1442 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
1443 {
1444   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1445   struct nesting_info *info = wi->info, *i;
1446   tree t = *tp, label, new_label, target_context, x, arg, field;
1447   struct var_map_elt *elt, dummy;
1448   void **slot;
1449
1450   *walk_subtrees = 0;
1451   if (TREE_CODE (t) != GOTO_EXPR)
1452     return NULL_TREE;
1453   label = GOTO_DESTINATION (t);
1454   if (TREE_CODE (label) != LABEL_DECL)
1455     return NULL_TREE;
1456   target_context = decl_function_context (label);
1457   if (target_context == info->context)
1458     return NULL_TREE;
1459
1460   for (i = info->outer; target_context != i->context; i = i->outer)
1461     continue;
1462
1463   /* The original user label may also be use for a normal goto, therefore
1464      we must create a new label that will actually receive the abnormal
1465      control transfer.  This new label will be marked LABEL_NONLOCAL; this
1466      mark will trigger proper behavior in the cfg, as well as cause the
1467      (hairy target-specific) non-local goto receiver code to be generated
1468      when we expand rtl.  Enter this association into var_map so that we
1469      can insert the new label into the IL during a second pass.  */
1470   dummy.old = label;
1471   slot = htab_find_slot (i->var_map, &dummy, INSERT);
1472   elt = (struct var_map_elt *) *slot;
1473   if (elt == NULL)
1474     {
1475       new_label = create_artificial_label ();
1476       DECL_NONLOCAL (new_label) = 1;
1477
1478       elt = GGC_NEW (struct var_map_elt);
1479       elt->old = label;
1480       elt->new = new_label;
1481       *slot = elt;
1482     }
1483   else
1484     new_label = elt->new;
1485
1486   /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field).  */
1487   field = get_nl_goto_field (i);
1488   x = get_frame_field (info, target_context, field, &wi->tsi);
1489   x = build_addr (x, target_context);
1490   x = tsi_gimplify_val (info, x, &wi->tsi);
1491   arg = tree_cons (NULL, x, NULL);
1492   x = build_addr (new_label, target_context);
1493   arg = tree_cons (NULL, x, arg);
1494   x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1495   x = build_function_call_expr (x, arg);
1496
1497   SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1498   *tsi_stmt_ptr (wi->tsi) = x;
1499
1500   return NULL_TREE;
1501 }
1502
1503 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1504    are referenced via nonlocal goto from a nested function.  The rewrite
1505    will involve installing a newly generated DECL_NONLOCAL label, and
1506    (potentially) a branch around the rtl gunk that is assumed to be
1507    attached to such a label.  */
1508
1509 static tree
1510 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1511 {
1512   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1513   struct nesting_info *info = wi->info;
1514   tree t = *tp, label, new_label, x;
1515   struct var_map_elt *elt, dummy;
1516   tree_stmt_iterator tmp_tsi;
1517
1518   *walk_subtrees = 0;
1519   if (TREE_CODE (t) != LABEL_EXPR)
1520     return NULL_TREE;
1521   label = LABEL_EXPR_LABEL (t);
1522
1523   dummy.old = label;
1524   elt = (struct var_map_elt *) htab_find (info->var_map, &dummy);
1525   if (!elt)
1526     return NULL_TREE;
1527   new_label = elt->new;
1528
1529   /* If there's any possibility that the previous statement falls through,
1530      then we must branch around the new non-local label.  */
1531   tmp_tsi = wi->tsi;
1532   tsi_prev (&tmp_tsi);
1533   if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1534     {
1535       x = build1 (GOTO_EXPR, void_type_node, label);
1536       tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1537     }
1538   x = build1 (LABEL_EXPR, void_type_node, new_label);
1539   tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1540
1541   return NULL_TREE;
1542 }
1543
1544 /* Called via walk_function+walk_tree, rewrite all references to addresses
1545    of nested functions that require the use of trampolines.  The rewrite
1546    will involve a reference a trampoline generated for the occasion.  */
1547
1548 static tree
1549 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1550 {
1551   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1552   struct nesting_info *info = wi->info, *i;
1553   tree t = *tp, decl, target_context, x, arg;
1554
1555   *walk_subtrees = 0;
1556   switch (TREE_CODE (t))
1557     {
1558     case ADDR_EXPR:
1559       /* Build
1560            T.1 = &CHAIN->tramp;
1561            T.2 = __builtin_adjust_trampoline (T.1);
1562            T.3 = (func_type)T.2;
1563       */
1564
1565       decl = TREE_OPERAND (t, 0);
1566       if (TREE_CODE (decl) != FUNCTION_DECL)
1567         break;
1568
1569       /* Only need to process nested functions.  */
1570       target_context = decl_function_context (decl);
1571       if (!target_context)
1572         break;
1573
1574       /* If the nested function doesn't use a static chain, then
1575          it doesn't need a trampoline.  */
1576       if (DECL_NO_STATIC_CHAIN (decl))
1577         break;
1578
1579       /* Lookup the immediate parent of the callee, as that's where
1580          we need to insert the trampoline.  */
1581       for (i = info; i->context != target_context; i = i->outer)
1582         continue;
1583       x = lookup_tramp_for_decl (i, decl, INSERT);
1584
1585       /* Compute the address of the field holding the trampoline.  */
1586       x = get_frame_field (info, target_context, x, &wi->tsi);
1587       x = build_addr (x, target_context);
1588       x = tsi_gimplify_val (info, x, &wi->tsi);
1589       arg = tree_cons (NULL, x, NULL);
1590
1591       /* Do machine-specific ugliness.  Normally this will involve
1592          computing extra alignment, but it can really be anything.  */
1593       x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1594       x = build_function_call_expr (x, arg);
1595       x = init_tmp_var (info, x, &wi->tsi);
1596
1597       /* Cast back to the proper function type.  */
1598       x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1599       x = init_tmp_var (info, x, &wi->tsi);
1600
1601       *tp = x;
1602       break;
1603
1604     case CALL_EXPR:
1605       /* Only walk call arguments, lest we generate trampolines for
1606          direct calls.  */
1607       walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1608       break;
1609
1610     default:
1611       if (!IS_TYPE_OR_DECL_P (t))
1612         *walk_subtrees = 1;
1613       break;
1614     }
1615
1616   return NULL_TREE;
1617 }
1618
1619 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1620    reference nested functions to make sure that the static chain is
1621    set up properly for the call.  */
1622
1623 static tree
1624 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1625 {
1626   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1627   struct nesting_info *info = wi->info;
1628   tree t = *tp, decl, target_context;
1629
1630   *walk_subtrees = 0;
1631   switch (TREE_CODE (t))
1632     {
1633     case CALL_EXPR:
1634       decl = get_callee_fndecl (t);
1635       if (!decl)
1636         break;
1637       target_context = decl_function_context (decl);
1638       if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1639         TREE_OPERAND (t, 2)
1640           = get_static_chain (info, target_context, &wi->tsi);
1641       break;
1642
1643     case RETURN_EXPR:
1644     case MODIFY_EXPR:
1645     case WITH_SIZE_EXPR:
1646       /* Only return modify and with_size_expr may contain calls.  */
1647       *walk_subtrees = 1;
1648       break;
1649
1650     case OMP_FOR:
1651     case OMP_SECTIONS:
1652     case OMP_SINGLE:
1653     case OMP_MASTER:
1654     case OMP_ORDERED:
1655     case OMP_CRITICAL:
1656       walk_body (convert_call_expr, info, &OMP_BODY (t));
1657       break;
1658
1659     default:
1660       break;
1661     }
1662
1663   return NULL_TREE;
1664 }
1665
1666 /* Walk the nesting tree starting with ROOT, depth first.  Convert all
1667    trampolines and call expressions.  On the way back up, determine if
1668    a nested function actually uses its static chain; if not, remember that.  */
1669
1670 static void
1671 convert_all_function_calls (struct nesting_info *root)
1672 {
1673   do
1674     {
1675       if (root->inner)
1676         convert_all_function_calls (root->inner);
1677
1678       walk_function (convert_tramp_reference, root);
1679       walk_function (convert_call_expr, root);
1680
1681       /* If the function does not use a static chain, then remember that.  */
1682       if (root->outer && !root->chain_decl && !root->chain_field)
1683         DECL_NO_STATIC_CHAIN (root->context) = 1;
1684       else
1685         gcc_assert (!DECL_NO_STATIC_CHAIN (root->context));
1686
1687       root = root->next;
1688     }
1689   while (root);
1690 }
1691
1692 /* Do "everything else" to clean up or complete state collected by the
1693    various walking passes -- lay out the types and decls, generate code
1694    to initialize the frame decl, store critical expressions in the
1695    struct function for rtl to find.  */
1696
1697 static void
1698 finalize_nesting_tree_1 (struct nesting_info *root)
1699 {
1700   tree stmt_list = NULL;
1701   tree context = root->context;
1702   struct function *sf;
1703
1704   /* If we created a non-local frame type or decl, we need to lay them
1705      out at this time.  */
1706   if (root->frame_type)
1707     {
1708       /* In some cases the frame type will trigger the -Wpadded warning.
1709          This is not helpful; suppress it. */
1710       int save_warn_padded = warn_padded;
1711       warn_padded = 0;
1712       layout_type (root->frame_type);
1713       warn_padded = save_warn_padded;
1714       layout_decl (root->frame_decl, 0);
1715     }
1716
1717   /* If any parameters were referenced non-locally, then we need to
1718      insert a copy.  Likewise, if any variables were referenced by
1719      pointer, we need to initialize the address.  */
1720   if (root->any_parm_remapped)
1721     {
1722       tree p;
1723       for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1724         {
1725           tree field, x, y;
1726
1727           field = lookup_field_for_decl (root, p, NO_INSERT);
1728           if (!field)
1729             continue;
1730
1731           if (use_pointer_in_frame (p))
1732             x = build_addr (p, context);
1733           else
1734             x = p;
1735
1736           y = build3 (COMPONENT_REF, TREE_TYPE (field),
1737                       root->frame_decl, field, NULL_TREE);
1738           x = build2 (MODIFY_EXPR, TREE_TYPE (field), y, x);
1739           append_to_statement_list (x, &stmt_list);
1740         }
1741     }
1742
1743   /* If a chain_field was created, then it needs to be initialized
1744      from chain_decl.  */
1745   if (root->chain_field)
1746     {
1747       tree x = build3 (COMPONENT_REF, TREE_TYPE (root->chain_field),
1748                        root->frame_decl, root->chain_field, NULL_TREE);
1749       x = build2 (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1750       append_to_statement_list (x, &stmt_list);
1751     }
1752
1753   /* If trampolines were created, then we need to initialize them.  */
1754   if (root->any_tramp_created)
1755     {
1756       struct nesting_info *i;
1757       for (i = root->inner; i ; i = i->next)
1758         {
1759           tree arg, x, field;
1760
1761           field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1762           if (!field)
1763             continue;
1764
1765           if (DECL_NO_STATIC_CHAIN (i->context))
1766             x = null_pointer_node;
1767           else
1768             x = build_addr (root->frame_decl, context);
1769           arg = tree_cons (NULL, x, NULL);
1770
1771           x = build_addr (i->context, context);
1772           arg = tree_cons (NULL, x, arg);
1773
1774           x = build3 (COMPONENT_REF, TREE_TYPE (field),
1775                       root->frame_decl, field, NULL_TREE);
1776           x = build_addr (x, context);
1777           arg = tree_cons (NULL, x, arg);
1778
1779           x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1780           x = build_function_call_expr (x, arg);
1781
1782           append_to_statement_list (x, &stmt_list);
1783         }
1784     }
1785
1786   /* If we created initialization statements, insert them.  */
1787   if (stmt_list)
1788     {
1789       annotate_all_with_locus (&stmt_list,
1790                                DECL_SOURCE_LOCATION (context));
1791       append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1792                                 &stmt_list);
1793       BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1794     }
1795
1796   /* If a chain_decl was created, then it needs to be registered with
1797      struct function so that it gets initialized from the static chain
1798      register at the beginning of the function.  */
1799   sf = DECL_STRUCT_FUNCTION (root->context);
1800   sf->static_chain_decl = root->chain_decl;
1801
1802   /* Similarly for the non-local goto save area.  */
1803   if (root->nl_goto_field)
1804     {
1805       sf->nonlocal_goto_save_area
1806         = get_frame_field (root, context, root->nl_goto_field, NULL);
1807       sf->has_nonlocal_label = 1;
1808     }
1809
1810   /* Make sure all new local variables get inserted into the
1811      proper BIND_EXPR.  */
1812   if (root->new_local_var_chain)
1813     declare_vars (root->new_local_var_chain, DECL_SAVED_TREE (root->context),
1814                   false);
1815   if (root->debug_var_chain)
1816     declare_vars (root->debug_var_chain, DECL_SAVED_TREE (root->context),
1817                   true);
1818
1819   /* Dump the translated tree function.  */
1820   dump_function (TDI_nested, root->context);
1821 }
1822
1823 static void
1824 finalize_nesting_tree (struct nesting_info *root)
1825 {
1826   do
1827     {
1828       if (root->inner)
1829         finalize_nesting_tree (root->inner);
1830       finalize_nesting_tree_1 (root);
1831       root = root->next;
1832     }
1833   while (root);
1834 }
1835
1836 /* Unnest the nodes and pass them to cgraph.  */
1837
1838 static void
1839 unnest_nesting_tree_1 (struct nesting_info *root)
1840 {
1841   struct cgraph_node *node = cgraph_node (root->context);
1842
1843   /* For nested functions update the cgraph to reflect unnesting.
1844      We also delay finalizing of these functions up to this point.  */
1845   if (node->origin)
1846     {
1847        cgraph_unnest_node (cgraph_node (root->context));
1848        cgraph_finalize_function (root->context, true);
1849     }
1850 }
1851
1852 static void
1853 unnest_nesting_tree (struct nesting_info *root)
1854 {
1855   do
1856     {
1857       if (root->inner)
1858         unnest_nesting_tree (root->inner);
1859       unnest_nesting_tree_1 (root);
1860       root = root->next;
1861     }
1862   while (root);
1863 }
1864
1865 /* Free the data structures allocated during this pass.  */
1866
1867 static void
1868 free_nesting_tree (struct nesting_info *root)
1869 {
1870   struct nesting_info *next;
1871   do
1872     {
1873       if (root->inner)
1874         free_nesting_tree (root->inner);
1875       htab_delete (root->var_map);
1876       next = root->next;
1877       ggc_free (root);
1878       root = next;
1879     }
1880   while (root);
1881 }
1882
1883 static GTY(()) struct nesting_info *root;
1884
1885 /* Main entry point for this pass.  Process FNDECL and all of its nested
1886    subroutines and turn them into something less tightly bound.  */
1887
1888 void
1889 lower_nested_functions (tree fndecl)
1890 {
1891   struct cgraph_node *cgn;
1892
1893   /* If there are no nested functions, there's nothing to do.  */
1894   cgn = cgraph_node (fndecl);
1895   if (!cgn->nested)
1896     return;
1897
1898   root = create_nesting_tree (cgn);
1899   walk_all_functions (convert_nonlocal_reference, root);
1900   walk_all_functions (convert_local_reference, root);
1901   walk_all_functions (convert_nl_goto_reference, root);
1902   walk_all_functions (convert_nl_goto_receiver, root);
1903   convert_all_function_calls (root);
1904   finalize_nesting_tree (root);
1905   unnest_nesting_tree (root);
1906   free_nesting_tree (root);
1907   root = NULL;
1908 }
1909
1910 #include "gt-tree-nested.h"