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