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;
1038           c = get_chain_decl (info);
1039           c = build1 (OMP_CLAUSE_FIRSTPRIVATE, void_type_node, c);
1040           OMP_CLAUSE_CHAIN (c) = OMP_PARALLEL_CLAUSES (t);
1041           OMP_PARALLEL_CLAUSES (t) = c;
1042         }
1043
1044       save_local_var_chain = info->new_local_var_chain;
1045       info->new_local_var_chain = NULL;
1046
1047       walk_body (convert_nonlocal_reference, info, &OMP_PARALLEL_BODY (t));
1048
1049       if (info->new_local_var_chain)
1050         declare_tmp_vars (info->new_local_var_chain, OMP_PARALLEL_BODY (t));
1051       info->new_local_var_chain = save_local_var_chain;
1052       info->suppress_expansion = save_suppress;
1053       break;
1054
1055     case OMP_FOR:
1056     case OMP_SECTIONS:
1057     case OMP_SINGLE:
1058       save_suppress = info->suppress_expansion;
1059       convert_nonlocal_omp_clauses (&OMP_CLAUSES (t), wi);
1060       walk_body (convert_nonlocal_reference, info, &OMP_BODY (t));
1061       info->suppress_expansion = save_suppress;
1062       break;
1063
1064     case OMP_SECTION:
1065     case OMP_MASTER:
1066     case OMP_ORDERED:
1067       walk_body (convert_nonlocal_reference, info, &OMP_BODY (t));
1068       break;
1069
1070     default:
1071       if (!IS_TYPE_OR_DECL_P (t))
1072         {
1073           *walk_subtrees = 1;
1074           wi->val_only = true;
1075           wi->is_lhs = false;
1076         }
1077       break;
1078     }
1079
1080   return NULL_TREE;
1081 }
1082
1083 static bool
1084 convert_nonlocal_omp_clauses (tree *pclauses, struct walk_stmt_info *wi)
1085 {
1086   struct nesting_info *info = wi->info;
1087   bool need_chain = false;
1088   tree clause, decl;
1089   int dummy;
1090   bitmap new_suppress;
1091
1092   new_suppress = BITMAP_GGC_ALLOC ();
1093   bitmap_copy (new_suppress, info->suppress_expansion);
1094
1095   for (clause = *pclauses; clause ; clause = OMP_CLAUSE_CHAIN (clause))
1096     {
1097       switch (TREE_CODE (clause))
1098         {
1099         case OMP_CLAUSE_PRIVATE:
1100         case OMP_CLAUSE_FIRSTPRIVATE:
1101         case OMP_CLAUSE_LASTPRIVATE:
1102         case OMP_CLAUSE_REDUCTION:
1103         case OMP_CLAUSE_COPYPRIVATE:
1104         case OMP_CLAUSE_SHARED:
1105           decl = OMP_CLAUSE_DECL (clause);
1106           if (decl_function_context (decl) != info->context)
1107             {
1108               bitmap_set_bit (new_suppress, DECL_UID (decl));
1109               OMP_CLAUSE_DECL (clause) = get_nonlocal_debug_decl (info, decl);
1110               need_chain = true;
1111             }
1112           break;
1113
1114         case OMP_CLAUSE_SCHEDULE:
1115           if (OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (clause) == NULL)
1116             break;
1117           /* FALLTHRU */
1118         case OMP_CLAUSE_IF:
1119         case OMP_CLAUSE_NUM_THREADS:
1120           wi->val_only = true;
1121           wi->is_lhs = false;
1122           convert_nonlocal_reference (&TREE_OPERAND (clause, 0), &dummy, wi);
1123           break;
1124
1125         case OMP_CLAUSE_NOWAIT:
1126         case OMP_CLAUSE_ORDERED:
1127         case OMP_CLAUSE_DEFAULT:
1128         case OMP_CLAUSE_COPYIN:
1129           break;
1130
1131         default:
1132           gcc_unreachable ();
1133         }
1134     }
1135
1136   info->suppress_expansion = new_suppress;
1137
1138   return need_chain;
1139 }
1140
1141 /* A subroutine of convert_local_reference.  Create a local variable
1142    in the parent function with DECL_VALUE_EXPR set to reference the
1143    field in FRAME.  This is used both for debug info and in OpenMP
1144    lowering.  */
1145
1146 static tree
1147 get_local_debug_decl (struct nesting_info *info, tree decl, tree field)
1148 {
1149   struct var_map_elt *elt, dummy;
1150   tree x, new_decl;
1151   void **slot;
1152
1153   dummy.old = decl;
1154   slot = htab_find_slot (info->var_map, &dummy, INSERT);
1155   elt = *slot;
1156
1157   if (elt)
1158     return elt->new;
1159
1160   /* Make sure frame_decl gets created.  */
1161   (void) get_frame_type (info);
1162   x = info->frame_decl;
1163   x = build3 (COMPONENT_REF, TREE_TYPE (field), x, field, NULL_TREE);
1164
1165   new_decl = build_decl (VAR_DECL, DECL_NAME (decl), TREE_TYPE (decl));
1166   DECL_CONTEXT (new_decl) = info->context;
1167   DECL_SOURCE_LOCATION (new_decl) = DECL_SOURCE_LOCATION (decl);
1168   DECL_ARTIFICIAL (new_decl) = DECL_ARTIFICIAL (decl);
1169   DECL_IGNORED_P (new_decl) = DECL_IGNORED_P (decl);
1170   TREE_THIS_VOLATILE (new_decl) = TREE_THIS_VOLATILE (decl);
1171   TREE_SIDE_EFFECTS (new_decl) = TREE_SIDE_EFFECTS (decl);
1172   TREE_READONLY (new_decl) = TREE_READONLY (decl);
1173   TREE_ADDRESSABLE (new_decl) = TREE_ADDRESSABLE (decl);
1174   DECL_SEEN_IN_BIND_EXPR_P (new_decl) = 1;
1175
1176   SET_DECL_VALUE_EXPR (new_decl, x);
1177   DECL_HAS_VALUE_EXPR_P (new_decl) = 1;
1178
1179   elt = ggc_alloc (sizeof (*elt));
1180   elt->old = decl;
1181   elt->new = new_decl;
1182   *slot = elt;
1183
1184   TREE_CHAIN (new_decl) = info->debug_var_chain;
1185   info->debug_var_chain = new_decl;
1186
1187   return new_decl;
1188 }
1189
1190 /* Called via walk_function+walk_tree, rewrite all references to VAR
1191    and PARM_DECLs that were referenced by inner nested functions.
1192    The rewrite will be a structure reference to the local frame variable.  */
1193
1194 static bool convert_local_omp_clauses (tree *, struct walk_stmt_info *);
1195
1196 static tree
1197 convert_local_reference (tree *tp, int *walk_subtrees, void *data)
1198 {
1199   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1200   struct nesting_info *info = wi->info;
1201   tree t = *tp, field, x;
1202   bool save_val_only;
1203   tree save_local_var_chain;
1204   bitmap save_suppress;
1205
1206   *walk_subtrees = 0;
1207   switch (TREE_CODE (t))
1208     {
1209     case VAR_DECL:
1210       /* Non-automatic variables are never processed.  */
1211       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
1212         break;
1213       /* FALLTHRU */
1214
1215     case PARM_DECL:
1216       if (decl_function_context (t) == info->context)
1217         {
1218           /* If we copied a pointer to the frame, then the original decl
1219              is used unchanged in the parent function.  */
1220           if (use_pointer_in_frame (t))
1221             break;
1222
1223           /* No need to transform anything if no child references the
1224              variable.  */
1225           field = lookup_field_for_decl (info, t, NO_INSERT);
1226           if (!field)
1227             break;
1228           wi->changed = true;
1229
1230           x = get_local_debug_decl (info, t, field);
1231           if (!bitmap_bit_p (info->suppress_expansion, DECL_UID (t)))
1232             x = get_frame_field (info, info->context, field, &wi->tsi);
1233
1234           if (wi->val_only)
1235             {
1236               if (wi->is_lhs)
1237                 x = save_tmp_var (info, x, &wi->tsi);
1238               else
1239                 x = init_tmp_var (info, x, &wi->tsi);
1240             }
1241
1242           *tp = x;
1243         }
1244       break;
1245
1246     case ADDR_EXPR:
1247       save_val_only = wi->val_only;
1248       wi->val_only = false;
1249       wi->is_lhs = false;
1250       wi->changed = false;
1251       walk_tree (&TREE_OPERAND (t, 0), convert_local_reference, wi, NULL);
1252       wi->val_only = save_val_only;
1253
1254       /* If we converted anything ... */
1255       if (wi->changed)
1256         {
1257           tree save_context;
1258
1259           /* Then the frame decl is now addressable.  */
1260           TREE_ADDRESSABLE (info->frame_decl) = 1;
1261
1262           save_context = current_function_decl;
1263           current_function_decl = info->context;
1264           recompute_tree_invariant_for_addr_expr (t);
1265           current_function_decl = save_context;
1266
1267           /* If we are in a context where we only accept values, then
1268              compute the address into a temporary.  */
1269           if (save_val_only)
1270             *tp = tsi_gimplify_val (wi->info, t, &wi->tsi);
1271         }
1272       break;
1273
1274     case REALPART_EXPR:
1275     case IMAGPART_EXPR:
1276     case COMPONENT_REF:
1277     case ARRAY_REF:
1278     case ARRAY_RANGE_REF:
1279     case BIT_FIELD_REF:
1280       /* Go down this entire nest and just look at the final prefix and
1281          anything that describes the references.  Otherwise, we lose track
1282          of whether a NOP_EXPR or VIEW_CONVERT_EXPR needs a simple value.  */
1283       save_val_only = wi->val_only;
1284       wi->val_only = true;
1285       wi->is_lhs = false;
1286       for (; handled_component_p (t); tp = &TREE_OPERAND (t, 0), t = *tp)
1287         {
1288           if (TREE_CODE (t) == COMPONENT_REF)
1289             walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1290                        NULL);
1291           else if (TREE_CODE (t) == ARRAY_REF
1292                    || TREE_CODE (t) == ARRAY_RANGE_REF)
1293             {
1294               walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1295                          NULL);
1296               walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1297                          NULL);
1298               walk_tree (&TREE_OPERAND (t, 3), convert_local_reference, wi,
1299                          NULL);
1300             }
1301           else if (TREE_CODE (t) == BIT_FIELD_REF)
1302             {
1303               walk_tree (&TREE_OPERAND (t, 1), convert_local_reference, wi,
1304                          NULL);
1305               walk_tree (&TREE_OPERAND (t, 2), convert_local_reference, wi,
1306                          NULL);
1307             }
1308         }
1309       wi->val_only = false;
1310       walk_tree (tp, convert_local_reference, wi, NULL);
1311       wi->val_only = save_val_only;
1312       break;
1313
1314     case OMP_PARALLEL:
1315       save_suppress = info->suppress_expansion;
1316       if (convert_local_omp_clauses (&OMP_PARALLEL_CLAUSES (t), wi))
1317         {
1318           tree c;
1319           (void) get_frame_type (info);
1320           c = build1 (OMP_CLAUSE_SHARED, void_type_node, info->frame_decl);
1321           OMP_CLAUSE_CHAIN (c) = OMP_PARALLEL_CLAUSES (t);
1322           OMP_PARALLEL_CLAUSES (t) = c;
1323         }
1324
1325       save_local_var_chain = info->new_local_var_chain;
1326       info->new_local_var_chain = NULL;
1327
1328       walk_body (convert_local_reference, info, &OMP_PARALLEL_BODY (t));
1329
1330       if (info->new_local_var_chain)
1331         declare_tmp_vars (info->new_local_var_chain, OMP_PARALLEL_BODY (t));
1332       info->new_local_var_chain = save_local_var_chain;
1333       info->suppress_expansion = save_suppress;
1334       break;
1335
1336     case OMP_FOR:
1337     case OMP_SECTIONS:
1338     case OMP_SINGLE:
1339       save_suppress = info->suppress_expansion;
1340       convert_local_omp_clauses (&OMP_CLAUSES (t), wi);
1341       walk_body (convert_local_reference, info, &OMP_BODY (t));
1342       info->suppress_expansion = save_suppress;
1343       break;
1344
1345     case OMP_SECTION:
1346     case OMP_MASTER:
1347     case OMP_ORDERED:
1348       walk_body (convert_local_reference, info, &OMP_BODY (t));
1349       break;
1350
1351     default:
1352       if (!IS_TYPE_OR_DECL_P (t))
1353         {
1354           *walk_subtrees = 1;
1355           wi->val_only = true;
1356           wi->is_lhs = false;
1357         }
1358       break;
1359     }
1360
1361   return NULL_TREE;
1362 }
1363
1364 static bool
1365 convert_local_omp_clauses (tree *pclauses, struct walk_stmt_info *wi)
1366 {
1367   struct nesting_info *info = wi->info;
1368   bool need_frame = false;
1369   tree clause, decl;
1370   int dummy;
1371   bitmap new_suppress;
1372
1373   new_suppress = BITMAP_GGC_ALLOC ();
1374   bitmap_copy (new_suppress, info->suppress_expansion);
1375
1376   for (clause = *pclauses; clause ; clause = OMP_CLAUSE_CHAIN (clause))
1377     {
1378       switch (TREE_CODE (clause))
1379         {
1380         case OMP_CLAUSE_PRIVATE:
1381         case OMP_CLAUSE_FIRSTPRIVATE:
1382         case OMP_CLAUSE_LASTPRIVATE:
1383         case OMP_CLAUSE_REDUCTION:
1384         case OMP_CLAUSE_COPYPRIVATE:
1385         case OMP_CLAUSE_SHARED:
1386           decl = OMP_CLAUSE_DECL (clause);
1387           if (decl_function_context (decl) == info->context
1388               && !use_pointer_in_frame (decl))
1389             {
1390               tree field = lookup_field_for_decl (info, decl, NO_INSERT);
1391               if (field)
1392                 {
1393                   bitmap_set_bit (new_suppress, DECL_UID (decl));
1394                   OMP_CLAUSE_DECL (clause)
1395                     = get_local_debug_decl (info, decl, field);
1396                   need_frame = true;
1397                 }
1398             }
1399           break;
1400
1401         case OMP_CLAUSE_SCHEDULE:
1402           if (OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (clause) == NULL)
1403             break;
1404           /* FALLTHRU */
1405         case OMP_CLAUSE_IF:
1406         case OMP_CLAUSE_NUM_THREADS:
1407           wi->val_only = true;
1408           wi->is_lhs = false;
1409           convert_local_reference (&TREE_OPERAND (clause, 0), &dummy, wi);
1410           break;
1411
1412         case OMP_CLAUSE_NOWAIT:
1413         case OMP_CLAUSE_ORDERED:
1414         case OMP_CLAUSE_DEFAULT:
1415         case OMP_CLAUSE_COPYIN:
1416           break;
1417
1418         default:
1419           gcc_unreachable ();
1420         }
1421     }
1422
1423   info->suppress_expansion = new_suppress;
1424
1425   return need_frame;
1426 }
1427
1428 /* Called via walk_function+walk_tree, rewrite all GOTO_EXPRs that
1429    reference labels from outer functions.  The rewrite will be a
1430    call to __builtin_nonlocal_goto.  */
1431
1432 static tree
1433 convert_nl_goto_reference (tree *tp, int *walk_subtrees, void *data)
1434 {
1435   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1436   struct nesting_info *info = wi->info, *i;
1437   tree t = *tp, label, new_label, target_context, x, arg, field;
1438   struct var_map_elt *elt, dummy;
1439   void **slot;
1440
1441   *walk_subtrees = 0;
1442   if (TREE_CODE (t) != GOTO_EXPR)
1443     return NULL_TREE;
1444   label = GOTO_DESTINATION (t);
1445   if (TREE_CODE (label) != LABEL_DECL)
1446     return NULL_TREE;
1447   target_context = decl_function_context (label);
1448   if (target_context == info->context)
1449     return NULL_TREE;
1450
1451   for (i = info->outer; target_context != i->context; i = i->outer)
1452     continue;
1453
1454   /* The original user label may also be use for a normal goto, therefore
1455      we must create a new label that will actually receive the abnormal
1456      control transfer.  This new label will be marked LABEL_NONLOCAL; this
1457      mark will trigger proper behavior in the cfg, as well as cause the
1458      (hairy target-specific) non-local goto receiver code to be generated
1459      when we expand rtl.  Enter this association into var_map so that we
1460      can insert the new label into the IL during a second pass.  */
1461   dummy.old = label;
1462   slot = htab_find_slot (i->var_map, &dummy, INSERT);
1463   elt = (struct var_map_elt *) *slot;
1464   if (elt == NULL)
1465     {
1466       new_label = create_artificial_label ();
1467       DECL_NONLOCAL (new_label) = 1;
1468
1469       elt = GGC_NEW (struct var_map_elt);
1470       elt->old = label;
1471       elt->new = new_label;
1472       *slot = elt;
1473     }
1474   else
1475     new_label = elt->new;
1476
1477   /* Build: __builtin_nl_goto(new_label, &chain->nl_goto_field).  */
1478   field = get_nl_goto_field (i);
1479   x = get_frame_field (info, target_context, field, &wi->tsi);
1480   x = build_addr (x, target_context);
1481   x = tsi_gimplify_val (info, x, &wi->tsi);
1482   arg = tree_cons (NULL, x, NULL);
1483   x = build_addr (new_label, target_context);
1484   arg = tree_cons (NULL, x, arg);
1485   x = implicit_built_in_decls[BUILT_IN_NONLOCAL_GOTO];
1486   x = build_function_call_expr (x, arg);
1487
1488   SET_EXPR_LOCUS (x, EXPR_LOCUS (tsi_stmt (wi->tsi)));
1489   *tsi_stmt_ptr (wi->tsi) = x;
1490
1491   return NULL_TREE;
1492 }
1493
1494 /* Called via walk_function+walk_tree, rewrite all LABEL_EXPRs that
1495    are referenced via nonlocal goto from a nested function.  The rewrite
1496    will involve installing a newly generated DECL_NONLOCAL label, and
1497    (potentially) a branch around the rtl gunk that is assumed to be
1498    attached to such a label.  */
1499
1500 static tree
1501 convert_nl_goto_receiver (tree *tp, int *walk_subtrees, void *data)
1502 {
1503   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1504   struct nesting_info *info = wi->info;
1505   tree t = *tp, label, new_label, x;
1506   struct var_map_elt *elt, dummy;
1507   tree_stmt_iterator tmp_tsi;
1508
1509   *walk_subtrees = 0;
1510   if (TREE_CODE (t) != LABEL_EXPR)
1511     return NULL_TREE;
1512   label = LABEL_EXPR_LABEL (t);
1513
1514   dummy.old = label;
1515   elt = (struct var_map_elt *) htab_find (info->var_map, &dummy);
1516   if (!elt)
1517     return NULL_TREE;
1518   new_label = elt->new;
1519
1520   /* If there's any possibility that the previous statement falls through,
1521      then we must branch around the new non-local label.  */
1522   tmp_tsi = wi->tsi;
1523   tsi_prev (&tmp_tsi);
1524   if (tsi_end_p (tmp_tsi) || block_may_fallthru (tsi_stmt (tmp_tsi)))
1525     {
1526       x = build1 (GOTO_EXPR, void_type_node, label);
1527       tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1528     }
1529   x = build1 (LABEL_EXPR, void_type_node, new_label);
1530   tsi_link_before (&wi->tsi, x, TSI_SAME_STMT);
1531
1532   return NULL_TREE;
1533 }
1534
1535 /* Called via walk_function+walk_tree, rewrite all references to addresses
1536    of nested functions that require the use of trampolines.  The rewrite
1537    will involve a reference a trampoline generated for the occasion.  */
1538
1539 static tree
1540 convert_tramp_reference (tree *tp, int *walk_subtrees, void *data)
1541 {
1542   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1543   struct nesting_info *info = wi->info, *i;
1544   tree t = *tp, decl, target_context, x, arg;
1545
1546   *walk_subtrees = 0;
1547   switch (TREE_CODE (t))
1548     {
1549     case ADDR_EXPR:
1550       /* Build
1551            T.1 = &CHAIN->tramp;
1552            T.2 = __builtin_adjust_trampoline (T.1);
1553            T.3 = (func_type)T.2;
1554       */
1555
1556       decl = TREE_OPERAND (t, 0);
1557       if (TREE_CODE (decl) != FUNCTION_DECL)
1558         break;
1559
1560       /* Only need to process nested functions.  */
1561       target_context = decl_function_context (decl);
1562       if (!target_context)
1563         break;
1564
1565       /* If the nested function doesn't use a static chain, then
1566          it doesn't need a trampoline.  */
1567       if (DECL_NO_STATIC_CHAIN (decl))
1568         break;
1569
1570       /* Lookup the immediate parent of the callee, as that's where
1571          we need to insert the trampoline.  */
1572       for (i = info; i->context != target_context; i = i->outer)
1573         continue;
1574       x = lookup_tramp_for_decl (i, decl, INSERT);
1575
1576       /* Compute the address of the field holding the trampoline.  */
1577       x = get_frame_field (info, target_context, x, &wi->tsi);
1578       x = build_addr (x, target_context);
1579       x = tsi_gimplify_val (info, x, &wi->tsi);
1580       arg = tree_cons (NULL, x, NULL);
1581
1582       /* Do machine-specific ugliness.  Normally this will involve
1583          computing extra alignment, but it can really be anything.  */
1584       x = implicit_built_in_decls[BUILT_IN_ADJUST_TRAMPOLINE];
1585       x = build_function_call_expr (x, arg);
1586       x = init_tmp_var (info, x, &wi->tsi);
1587
1588       /* Cast back to the proper function type.  */
1589       x = build1 (NOP_EXPR, TREE_TYPE (t), x);
1590       x = init_tmp_var (info, x, &wi->tsi);
1591
1592       *tp = x;
1593       break;
1594
1595     case CALL_EXPR:
1596       /* Only walk call arguments, lest we generate trampolines for
1597          direct calls.  */
1598       walk_tree (&TREE_OPERAND (t, 1), convert_tramp_reference, wi, NULL);
1599       break;
1600
1601     default:
1602       if (!IS_TYPE_OR_DECL_P (t))
1603         *walk_subtrees = 1;
1604       break;
1605     }
1606
1607   return NULL_TREE;
1608 }
1609
1610 /* Called via walk_function+walk_tree, rewrite all CALL_EXPRs that
1611    reference nested functions to make sure that the static chain is
1612    set up properly for the call.  */
1613
1614 static tree
1615 convert_call_expr (tree *tp, int *walk_subtrees, void *data)
1616 {
1617   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
1618   struct nesting_info *info = wi->info;
1619   tree t = *tp, decl, target_context;
1620
1621   *walk_subtrees = 0;
1622   switch (TREE_CODE (t))
1623     {
1624     case CALL_EXPR:
1625       decl = get_callee_fndecl (t);
1626       if (!decl)
1627         break;
1628       target_context = decl_function_context (decl);
1629       if (target_context && !DECL_NO_STATIC_CHAIN (decl))
1630         TREE_OPERAND (t, 2)
1631           = get_static_chain (info, target_context, &wi->tsi);
1632       break;
1633
1634     case RETURN_EXPR:
1635     case MODIFY_EXPR:
1636     case WITH_SIZE_EXPR:
1637       /* Only return modify and with_size_expr may contain calls.  */
1638       *walk_subtrees = 1;
1639       break;
1640
1641     case OMP_FOR:
1642     case OMP_SECTIONS:
1643     case OMP_SINGLE:
1644     case OMP_MASTER:
1645     case OMP_ORDERED:
1646     case OMP_CRITICAL:
1647       walk_body (convert_call_expr, info, &OMP_BODY (t));
1648       break;
1649
1650     default:
1651       break;
1652     }
1653
1654   return NULL_TREE;
1655 }
1656
1657 /* Walk the nesting tree starting with ROOT, depth first.  Convert all
1658    trampolines and call expressions.  On the way back up, determine if
1659    a nested function actually uses its static chain; if not, remember that.  */
1660
1661 static void
1662 convert_all_function_calls (struct nesting_info *root)
1663 {
1664   do
1665     {
1666       if (root->inner)
1667         convert_all_function_calls (root->inner);
1668
1669       walk_function (convert_tramp_reference, root);
1670       walk_function (convert_call_expr, root);
1671
1672       /* If the function does not use a static chain, then remember that.  */
1673       if (root->outer && !root->chain_decl && !root->chain_field)
1674         DECL_NO_STATIC_CHAIN (root->context) = 1;
1675       else
1676         gcc_assert (!DECL_NO_STATIC_CHAIN (root->context));
1677
1678       root = root->next;
1679     }
1680   while (root);
1681 }
1682
1683 /* Do "everything else" to clean up or complete state collected by the
1684    various walking passes -- lay out the types and decls, generate code
1685    to initialize the frame decl, store critical expressions in the
1686    struct function for rtl to find.  */
1687
1688 static void
1689 finalize_nesting_tree_1 (struct nesting_info *root)
1690 {
1691   tree stmt_list = NULL;
1692   tree context = root->context;
1693   struct function *sf;
1694
1695   /* If we created a non-local frame type or decl, we need to lay them
1696      out at this time.  */
1697   if (root->frame_type)
1698     {
1699       /* In some cases the frame type will trigger the -Wpadded warning.
1700          This is not helpful; suppress it. */
1701       int save_warn_padded = warn_padded;
1702       warn_padded = 0;
1703       layout_type (root->frame_type);
1704       warn_padded = save_warn_padded;
1705       layout_decl (root->frame_decl, 0);
1706     }
1707
1708   /* If any parameters were referenced non-locally, then we need to
1709      insert a copy.  Likewise, if any variables were referenced by
1710      pointer, we need to initialize the address.  */
1711   if (root->any_parm_remapped)
1712     {
1713       tree p;
1714       for (p = DECL_ARGUMENTS (context); p ; p = TREE_CHAIN (p))
1715         {
1716           tree field, x, y;
1717
1718           field = lookup_field_for_decl (root, p, NO_INSERT);
1719           if (!field)
1720             continue;
1721
1722           if (use_pointer_in_frame (p))
1723             x = build_addr (p, context);
1724           else
1725             x = p;
1726
1727           y = build3 (COMPONENT_REF, TREE_TYPE (field),
1728                       root->frame_decl, field, NULL_TREE);
1729           x = build2 (MODIFY_EXPR, TREE_TYPE (field), y, x);
1730           append_to_statement_list (x, &stmt_list);
1731         }
1732     }
1733
1734   /* If a chain_field was created, then it needs to be initialized
1735      from chain_decl.  */
1736   if (root->chain_field)
1737     {
1738       tree x = build3 (COMPONENT_REF, TREE_TYPE (root->chain_field),
1739                        root->frame_decl, root->chain_field, NULL_TREE);
1740       x = build2 (MODIFY_EXPR, TREE_TYPE (x), x, get_chain_decl (root));
1741       append_to_statement_list (x, &stmt_list);
1742     }
1743
1744   /* If trampolines were created, then we need to initialize them.  */
1745   if (root->any_tramp_created)
1746     {
1747       struct nesting_info *i;
1748       for (i = root->inner; i ; i = i->next)
1749         {
1750           tree arg, x, field;
1751
1752           field = lookup_tramp_for_decl (root, i->context, NO_INSERT);
1753           if (!field)
1754             continue;
1755
1756           if (DECL_NO_STATIC_CHAIN (i->context))
1757             x = null_pointer_node;
1758           else
1759             x = build_addr (root->frame_decl, context);
1760           arg = tree_cons (NULL, x, NULL);
1761
1762           x = build_addr (i->context, context);
1763           arg = tree_cons (NULL, x, arg);
1764
1765           x = build3 (COMPONENT_REF, TREE_TYPE (field),
1766                       root->frame_decl, field, NULL_TREE);
1767           x = build_addr (x, context);
1768           arg = tree_cons (NULL, x, arg);
1769
1770           x = implicit_built_in_decls[BUILT_IN_INIT_TRAMPOLINE];
1771           x = build_function_call_expr (x, arg);
1772
1773           append_to_statement_list (x, &stmt_list);
1774         }
1775     }
1776
1777   /* If we created initialization statements, insert them.  */
1778   if (stmt_list)
1779     {
1780       annotate_all_with_locus (&stmt_list,
1781                                DECL_SOURCE_LOCATION (context));
1782       append_to_statement_list (BIND_EXPR_BODY (DECL_SAVED_TREE (context)),
1783                                 &stmt_list);
1784       BIND_EXPR_BODY (DECL_SAVED_TREE (context)) = stmt_list;
1785     }
1786
1787   /* If a chain_decl was created, then it needs to be registered with
1788      struct function so that it gets initialized from the static chain
1789      register at the beginning of the function.  */
1790   sf = DECL_STRUCT_FUNCTION (root->context);
1791   sf->static_chain_decl = root->chain_decl;
1792
1793   /* Similarly for the non-local goto save area.  */
1794   if (root->nl_goto_field)
1795     {
1796       sf->nonlocal_goto_save_area
1797         = get_frame_field (root, context, root->nl_goto_field, NULL);
1798       sf->has_nonlocal_label = 1;
1799     }
1800
1801   /* Make sure all new local variables get inserted into the
1802      proper BIND_EXPR.  */
1803   if (root->new_local_var_chain)
1804     declare_tmp_vars (root->new_local_var_chain,
1805                       DECL_SAVED_TREE (root->context));
1806   if (root->debug_var_chain)
1807     declare_tmp_vars (root->debug_var_chain,
1808                       DECL_SAVED_TREE (root->context));
1809
1810   /* Dump the translated tree function.  */
1811   dump_function (TDI_nested, root->context);
1812 }
1813
1814 static void
1815 finalize_nesting_tree (struct nesting_info *root)
1816 {
1817   do
1818     {
1819       if (root->inner)
1820         finalize_nesting_tree (root->inner);
1821       finalize_nesting_tree_1 (root);
1822       root = root->next;
1823     }
1824   while (root);
1825 }
1826
1827 /* Unnest the nodes and pass them to cgraph.  */
1828
1829 static void
1830 unnest_nesting_tree_1 (struct nesting_info *root)
1831 {
1832   struct cgraph_node *node = cgraph_node (root->context);
1833
1834   /* For nested functions update the cgraph to reflect unnesting.
1835      We also delay finalizing of these functions up to this point.  */
1836   if (node->origin)
1837     {
1838        cgraph_unnest_node (cgraph_node (root->context));
1839        cgraph_finalize_function (root->context, true);
1840     }
1841 }
1842
1843 static void
1844 unnest_nesting_tree (struct nesting_info *root)
1845 {
1846   do
1847     {
1848       if (root->inner)
1849         unnest_nesting_tree (root->inner);
1850       unnest_nesting_tree_1 (root);
1851       root = root->next;
1852     }
1853   while (root);
1854 }
1855
1856 /* Free the data structures allocated during this pass.  */
1857
1858 static void
1859 free_nesting_tree (struct nesting_info *root)
1860 {
1861   struct nesting_info *next;
1862   do
1863     {
1864       if (root->inner)
1865         free_nesting_tree (root->inner);
1866       htab_delete (root->var_map);
1867       next = root->next;
1868       ggc_free (root);
1869       root = next;
1870     }
1871   while (root);
1872 }
1873
1874 static GTY(()) struct nesting_info *root;
1875
1876 /* Main entry point for this pass.  Process FNDECL and all of its nested
1877    subroutines and turn them into something less tightly bound.  */
1878
1879 void
1880 lower_nested_functions (tree fndecl)
1881 {
1882   struct cgraph_node *cgn;
1883
1884   /* If there are no nested functions, there's nothing to do.  */
1885   cgn = cgraph_node (fndecl);
1886   if (!cgn->nested)
1887     return;
1888
1889   root = create_nesting_tree (cgn);
1890   walk_all_functions (convert_nonlocal_reference, root);
1891   walk_all_functions (convert_local_reference, root);
1892   walk_all_functions (convert_nl_goto_reference, root);
1893   walk_all_functions (convert_nl_goto_receiver, root);
1894   convert_all_function_calls (root);
1895   finalize_nesting_tree (root);
1896   unnest_nesting_tree (root);
1897   free_nesting_tree (root);
1898   root = NULL;
1899 }
1900
1901 #include "gt-tree-nested.h"