contrib/gcc-5.0/gcc/c-family/cilk.c

   1 /* This file is part of the Intel(R) Cilk(TM) Plus support
   2    This file contains the CilkPlus Intrinsics
   3    Copyright (C) 2013-2015 Free Software Foundation, Inc.
   4    Contributed by Balaji V. Iyer <balaji.v.iyer@intel.com>,
   5    Intel Corporation
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 3, or (at your option)
  12 any later version.
  13
  14 GCC is distributed in the hope that it will be useful, but
  15 WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17 General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "hash-set.h"
  27 #include "machmode.h"
  28 #include "vec.h"
  29 #include "double-int.h"
  30 #include "input.h"
  31 #include "alias.h"
  32 #include "symtab.h"
  33 #include "options.h"
  34 #include "wide-int.h"
  35 #include "inchash.h"
  36 #include "tree.h"
  37 #include "fold-const.h"
  38 #include "stringpool.h"
  39 #include "calls.h"
  40 #include "langhooks.h"
  41 #include "gimple-expr.h"
  42 #include "gimplify.h"
  43 #include "tree-iterator.h"
  44 #include "tree-inline.h"
  45 #include "c-family/c-common.h"
  46 #include "toplev.h"
  47 #include "hash-map.h"
  48 #include "is-a.h"
  49 #include "plugin-api.h"
  50 #include "vec.h"
  51 #include "hashtab.h"
  52 #include "hash-set.h"
  53 #include "machmode.h"
  54 #include "tm.h"
  55 #include "hard-reg-set.h"
  56 #include "input.h"
  57 #include "function.h"
  58 #include "ipa-ref.h"
  59 #include "cgraph.h"
  60 #include "diagnostic.h"
  61 #include "vec.h"
  62 #include "cilk.h"
  63
  64 enum add_variable_type {
  65     /* Reference to previously-defined variable.  */
  66     ADD_READ,
  67     /* Definition of a new variable in inner-scope.  */
  68     ADD_BIND,
  69     /* Write to possibly previously-defined variable.  */
  70     ADD_WRITE
  71 };
  72
  73 enum cilk_block_type {
  74     /* Indicates a _Cilk_spawn block.  30 was an arbitary number picked for
  75        ease of debugging.  */
  76     CILK_BLOCK_SPAWN = 30,
  77     /* Indicates _Cilk_for statement block.  */
  78     CILK_BLOCK_FOR
  79 };
  80
  81 struct wrapper_data
  82 {
  83   /* Kind of function to be created.  */
  84   enum cilk_block_type type;
  85   /* Signature of helper function.  */
  86   tree fntype;
  87   /* Containing function.  */
  88   tree context;
  89   /* Disposition of all variables in the inner statement.  */
  90   hash_map<tree, tree> *decl_map;
  91   /* True if this function needs a static chain.  */
  92   bool nested;
  93   /* Arguments to be passed to wrapper function, currently a list.  */
  94   tree arglist;
  95   /* Argument types, a list.  */
  96   tree argtypes;
  97   /* Incoming parameters.  */
  98   tree parms;
  99   /* Outer BLOCK object.  */
 100   tree block;
 101 };
 102
 103 static void extract_free_variables (tree, struct wrapper_data *,
 104                                     enum add_variable_type);
 105 static HOST_WIDE_INT cilk_wrapper_count;
 106
 107 /* Marks the CALL_EXPR or FUNCTION_DECL, FCALL, as a spawned function call
 108    and the current function as a spawner.  Emit error if the function call
 109    is outside a function or if a non function-call is spawned.  */
 110
 111 inline bool
 112 cilk_set_spawn_marker (location_t loc, tree fcall)
 113 {
 114   if (!current_function_decl)
 115     {
 116       error_at (loc, "%<_Cilk_spawn%> may only be used inside a function");
 117       return false;
 118     }
 119   else if (fcall == error_mark_node)
 120     /* Error reporting here is not necessary here since if FCALL is an
 121        error_mark_node, the function marking it as error would have reported
 122        it.  */
 123     return false;
 124   else if (TREE_CODE (fcall) != CALL_EXPR
 125            /* In C++, TARGET_EXPR is generated when we have an overloaded
 126               '=' operator.  */
 127            && TREE_CODE (fcall) != TARGET_EXPR)
 128     {
 129       error_at (loc, "only function calls can be spawned");
 130       return false;
 131     }
 132   else
 133     {
 134       cfun->calls_cilk_spawn = true;
 135       return true;
 136     }
 137 }
 138
 139 /* This function will output the exit conditions for a spawn call.  */
 140
 141 tree
 142 create_cilk_function_exit (tree frame, bool detaches, bool needs_sync)
 143 {
 144   tree epi = alloc_stmt_list ();
 145
 146   if (needs_sync)
 147     append_to_statement_list (build_cilk_sync (), &epi);
 148   tree func_ptr = build1 (ADDR_EXPR, cilk_frame_ptr_type_decl, frame);
 149   tree pop_frame = build_call_expr (cilk_pop_fndecl, 1, func_ptr);
 150   tree worker = cilk_dot (frame, CILK_TI_FRAME_WORKER, 0);
 151   tree current = cilk_arrow (worker, CILK_TI_WORKER_CUR, 0);
 152   tree parent = cilk_dot (frame, CILK_TI_FRAME_PARENT, 0);
 153   tree set_current = build2 (MODIFY_EXPR, void_type_node, current, parent);
 154   append_to_statement_list (set_current, &epi);
 155   append_to_statement_list (pop_frame, &epi);
 156   tree call = build_call_expr (cilk_leave_fndecl, 1, func_ptr);
 157   if (!detaches)
 158     {
 159       tree flags = cilk_dot (frame, CILK_TI_FRAME_FLAGS, false);
 160       tree flags_cmp_expr = fold_build2 (NE_EXPR, TREE_TYPE (flags), flags,
 161                                          build_int_cst (TREE_TYPE (flags),
 162                                                         CILK_FRAME_VERSION));
 163       call = fold_build3 (COND_EXPR, void_type_node, flags_cmp_expr,
 164                           call, build_empty_stmt (EXPR_LOCATION (flags)));
 165     }
 166   append_to_statement_list (call, &epi);
 167   return epi;
 168 }
 169
 170 /* Trying to get the correct cfun for the FUNCTION_DECL indicated by OUTER.  */
 171
 172 static void
 173 pop_cfun_to (tree outer)
 174 {
 175   pop_cfun ();
 176   current_function_decl = outer;
 177   gcc_assert (cfun == DECL_STRUCT_FUNCTION (current_function_decl));
 178   gcc_assert (cfun->decl == current_function_decl);
 179 }
 180
 181 /* This function does whatever is necessary to make the compiler emit a newly
 182    generated function, FNDECL.  */
 183
 184 static void
 185 call_graph_add_fn (tree fndecl)
 186 {
 187   const tree outer = current_function_decl;
 188   struct function *f = DECL_STRUCT_FUNCTION (fndecl);
 189   gcc_assert (TREE_CODE (fndecl) == FUNCTION_DECL);
 190
 191   f->is_cilk_function = 1;
 192   f->curr_properties = cfun->curr_properties;
 193   gcc_assert (cfun == DECL_STRUCT_FUNCTION (outer));
 194   gcc_assert (cfun->decl == outer);
 195
 196   push_cfun (f);
 197   cgraph_node::create (fndecl);
 198   pop_cfun_to (outer);
 199 }
 200
 201 /* Return true if this is a tree which is allowed to contain a spawn as
 202    operand 0.
 203    A spawn call may be wrapped in a series of unary operations such
 204    as conversions.  These conversions need not be "useless"
 205    to be disregarded because they are retained in the spawned
 206    statement.  They are bypassed only to look for a spawn
 207    within.
 208    A comparison to constant is simple enough to allow, and
 209    is used to convert to bool.  */
 210
 211 static bool
 212 cilk_ignorable_spawn_rhs_op (tree exp)
 213 {
 214   enum tree_code code = TREE_CODE (exp);
 215   switch (TREE_CODE_CLASS (code))
 216     {
 217     case tcc_expression:
 218       return code == ADDR_EXPR;
 219     case tcc_comparison:
 220       /* We need the spawn as operand 0 for now.   That's where it
 221          appears in the only case we really care about, conversion
 222          to bool.  */
 223       return (TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST);
 224     case tcc_unary:
 225     case tcc_reference:
 226       return true;
 227     default:
 228       return false;
 229     }
 230 }
 231
 232 /* Helper function for walk_tree.  If *TP is a CILK_SPAWN_STMT, then unwrap
 233    this "wrapper."  The function returns NULL_TREE regardless.  */
 234
 235 static tree
 236 unwrap_cilk_spawn_stmt (tree *tp, int *walk_subtrees, void *)
 237 {
 238   if (TREE_CODE (*tp) == CILK_SPAWN_STMT)
 239     {
 240       *tp = CILK_SPAWN_FN (*tp);
 241       *walk_subtrees = 0;
 242     }
 243   return NULL_TREE;
 244 }
 245
 246 /* Returns true when EXP is a CALL_EXPR with _Cilk_spawn in front.  Unwraps
 247    CILK_SPAWN_STMT wrapper from the CALL_EXPR in *EXP0 statement.  */
 248
 249 static bool
 250 recognize_spawn (tree exp, tree *exp0)
 251 {
 252   bool spawn_found = false;
 253   if (TREE_CODE (exp) == CILK_SPAWN_STMT)
 254     {
 255       /* Remove the CALL_EXPR from CILK_SPAWN_STMT wrapper.  */
 256       exp = CILK_SPAWN_FN (exp);
 257       walk_tree (exp0, unwrap_cilk_spawn_stmt, NULL, NULL);
 258       spawn_found = true;
 259     }
 260   /* _Cilk_spawn can't be wrapped in expression such as PLUS_EXPR.  */
 261   else if (contains_cilk_spawn_stmt (exp))
 262     error_at (EXPR_LOCATION (exp), "invalid use of %<_Cilk_spawn%>");
 263   return spawn_found;
 264 }
 265
 266 /* Returns true if *EXP0 is a recognized form of spawn.  Recognized forms are,
 267    after conversion to void, a call expression at outer level or an assignment
 268    at outer level with the right hand side being a spawned call.
 269    In addition to this, it also unwraps the CILK_SPAWN_STMT cover from the
 270    CALL_EXPR that is being spawned.
 271    Note that `=' in C++ may turn into a CALL_EXPR rather than a MODIFY_EXPR.  */
 272
 273 bool
 274 cilk_detect_spawn_and_unwrap (tree *exp0)
 275 {
 276   tree exp = *exp0;
 277
 278   if (!TREE_SIDE_EFFECTS (exp))
 279     return false;
 280
 281   /* Strip off any conversion to void.  It does not affect whether spawn
 282      is supported here.  */
 283   if (TREE_CODE (exp) == CONVERT_EXPR && VOID_TYPE_P (TREE_TYPE (exp)))
 284     exp = TREE_OPERAND (exp, 0);
 285
 286   if (TREE_CODE (exp) == MODIFY_EXPR || TREE_CODE (exp) == INIT_EXPR)
 287     exp = TREE_OPERAND (exp, 1);
 288
 289   while (cilk_ignorable_spawn_rhs_op (exp))
 290     exp = TREE_OPERAND (exp, 0);
 291
 292   if (TREE_CODE (exp) == TARGET_EXPR)
 293     if (TARGET_EXPR_INITIAL (exp)
 294         && TREE_CODE (TARGET_EXPR_INITIAL (exp)) != AGGR_INIT_EXPR)
 295       exp = TARGET_EXPR_INITIAL (exp);
 296
 297   /* Happens with C++ TARGET_EXPR.  */
 298   if (exp == NULL_TREE)
 299     return false;
 300
 301   while (TREE_CODE (exp) == CLEANUP_POINT_EXPR || TREE_CODE (exp) == EXPR_STMT)
 302     exp = TREE_OPERAND (exp, 0);
 303
 304   /* Now we should have a CALL_EXPR with a CILK_SPAWN_STMT wrapper around
 305      it, or return false.  */
 306   if (recognize_spawn (exp, exp0))
 307     return true;
 308   return false;
 309 }
 310
 311 /* This function will build and return a FUNCTION_DECL using information
 312    from *WD.  */
 313
 314 static tree
 315 create_cilk_helper_decl (struct wrapper_data *wd)
 316 {
 317   char name[20];
 318   if (wd->type == CILK_BLOCK_FOR)
 319     sprintf (name, "_cilk_for_" HOST_WIDE_INT_PRINT_DEC, cilk_wrapper_count++);
 320   else if (wd->type == CILK_BLOCK_SPAWN)
 321     sprintf (name, "_cilk_spn_" HOST_WIDE_INT_PRINT_DEC, cilk_wrapper_count++);
 322   else
 323     gcc_unreachable ();
 324
 325   clean_symbol_name (name);
 326   tree fndecl = build_decl (UNKNOWN_LOCATION, FUNCTION_DECL,
 327                             get_identifier (name), wd->fntype);
 328
 329   TREE_PUBLIC (fndecl) = 0;
 330   TREE_STATIC (fndecl) = 1;
 331   TREE_USED (fndecl) = 1;
 332   DECL_ARTIFICIAL (fndecl) = 0;
 333   DECL_IGNORED_P (fndecl) = 0;
 334   DECL_EXTERNAL (fndecl) = 0;
 335
 336   DECL_CONTEXT (fndecl) = wd->context;
 337   tree block = make_node (BLOCK);
 338   DECL_INITIAL (fndecl) = block;
 339   TREE_USED (block) = 1;
 340   BLOCK_SUPERCONTEXT (block) = fndecl;
 341   gcc_assert (!DECL_SAVED_TREE (fndecl));
 342
 343   /* Inlining would defeat the purpose of this wrapper.
 344      Either it secretly switches stack frames or it allocates
 345      a stable stack frame to hold function arguments even if
 346      the parent stack frame is stolen.  */
 347   DECL_UNINLINABLE (fndecl) = 1;
 348
 349   tree result_decl = build_decl (UNKNOWN_LOCATION, RESULT_DECL, NULL_TREE,
 350                                  void_type_node);
 351   DECL_ARTIFICIAL (result_decl) = 0;
 352   DECL_IGNORED_P (result_decl) = 1;
 353   DECL_CONTEXT (result_decl) = fndecl;
 354   DECL_RESULT (fndecl) = result_decl;
 355
 356   return fndecl;
 357 }
 358
 359 struct cilk_decls
 360 {
 361   tree key;
 362   tree *val;
 363 };
 364
 365 /* A function used by traversal to fill vector of decls for further work.  */
 366
 367 bool
 368 fill_decls_vec (tree const &key0, tree *val0, auto_vec<struct cilk_decls> *v)
 369 {
 370   tree t1 = key0;
 371   struct cilk_decls dp;
 372
 373   if (DECL_P (t1))
 374     {
 375       dp.key = t1;
 376       dp.val = val0;
 377       v->safe_push (dp);
 378     }
 379   return true;
 380 }
 381
 382 /* Function that actually creates necessary parm lists.  */
 383
 384 static void
 385 create_parm_list (struct wrapper_data *wd, tree *val0, tree arg)
 386 {
 387   tree val = *val0;
 388   tree parm;
 389
 390   if (val == error_mark_node || val == arg)
 391     return;
 392
 393   if (TREE_CODE (val) == PAREN_EXPR)
 394     {
 395       /* We should not reach here with a register receiver.
 396          We may see a register variable modified in the
 397          argument list.  Because register variables are
 398          worker-local we don't need to work hard to support
 399          them in code that spawns.  */
 400       if ((TREE_CODE (arg) == VAR_DECL) && DECL_HARD_REGISTER (arg))
 401         {
 402           error_at (EXPR_LOCATION (arg),
 403                     "explicit register variable %qD may not be modified in "
 404                     "spawn", arg);
 405           arg = null_pointer_node;
 406         }
 407       else
 408         arg = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (arg)), arg);
 409
 410       val = TREE_OPERAND (val, 0);
 411       *val0 = val;
 412       gcc_assert (TREE_CODE (val) == INDIRECT_REF);
 413       parm = TREE_OPERAND (val, 0);
 414       STRIP_NOPS (parm);
 415     }
 416   else
 417     parm = val;
 418   TREE_CHAIN (parm) = wd->parms;
 419   wd->parms = parm;
 420   wd->argtypes = tree_cons (NULL_TREE, TREE_TYPE (parm), wd->argtypes);
 421   wd->arglist = tree_cons (NULL_TREE, arg, wd->arglist);
 422 }
 423
 424 /* Sorting decls in a vector.  */
 425
 426 static int
 427 compare_decls (const void *a, const void *b)
 428 {
 429   const struct cilk_decls *t1 = (const struct cilk_decls *) a;
 430   const struct cilk_decls *t2 = (const struct cilk_decls *) b;
 431
 432   if (DECL_UID (t1->key) > DECL_UID (t2->key))
 433     return 1;
 434   else if (DECL_UID (t1->key) < DECL_UID (t2->key))
 435     return -1;
 436   else
 437     return 0;
 438 }
 439
 440 /* This function is used to build a wrapper of a certain type.  */
 441
 442 static void
 443 build_wrapper_type (struct wrapper_data *wd)
 444 {
 445   unsigned int j;
 446   struct cilk_decls * c;
 447   auto_vec<struct cilk_decls> vd;
 448   wd->arglist = NULL_TREE;
 449   wd->parms = NULL_TREE;
 450   wd->argtypes = void_list_node;
 451
 452   gcc_assert (wd->type != CILK_BLOCK_FOR);
 453   wd->decl_map->traverse<auto_vec<struct cilk_decls> *, fill_decls_vec> (&vd);
 454   vd.qsort (compare_decls);
 455
 456   FOR_EACH_VEC_ELT (vd, j, c)
 457    create_parm_list (wd, c->val, c->key);
 458
 459   /* Now build a function.
 460      Its return type is void (all side effects are via explicit parameters).
 461      Its parameters are WRAPPER_PARMS with type WRAPPER_TYPES.
 462      Actual arguments in the caller are WRAPPER_ARGS.  */
 463   wd->fntype = build_function_type (void_type_node, wd->argtypes);
 464 }
 465
 466 /* This function checks all the CALL_EXPRs in *TP found by cilk_outline.  */
 467
 468 static tree
 469 check_outlined_calls (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 470                       void *data)
 471 {
 472   bool *throws = (bool *) data;
 473   tree t = *tp;
 474   int flags;
 475
 476   if (TREE_CODE (t) != CALL_EXPR)
 477     return 0;
 478   flags = call_expr_flags (t);
 479
 480   if (!(flags & ECF_NOTHROW) && flag_exceptions)
 481     *throws = true;
 482   if (flags & ECF_RETURNS_TWICE)
 483     error_at (EXPR_LOCATION (t),
 484               "cannot spawn call to function that returns twice");
 485   return 0;
 486 }
 487
 488 /* Each DECL in the source code (spawned statement) is passed to this function
 489    once.  Each instance of the DECL is replaced with the result of this
 490    function.
 491
 492    The parameters of the wrapper should have been entered into the map already.
 493    This function only deals with variables with scope limited to the
 494    spawned expression.  */
 495
 496 static tree
 497 copy_decl_for_cilk (tree decl, copy_body_data *id)
 498 {
 499   switch (TREE_CODE (decl))
 500     {
 501     case VAR_DECL:
 502       return copy_decl_no_change (decl, id);
 503
 504     case LABEL_DECL:
 505       error_at (EXPR_LOCATION (decl), "invalid use of label %q+D in "
 506                 "%<_Cilk_spawn%>",
 507                 decl);
 508       return error_mark_node;
 509
 510     case RESULT_DECL:
 511     case PARM_DECL:
 512       /* RESULT_DECL and PARM_DECL has already been entered into the map.  */
 513     default:
 514       gcc_unreachable ();
 515       return error_mark_node;
 516     }
 517 }
 518
 519 /* Alter a tree STMT from OUTER_FN to form the body of INNER_FN.  */
 520
 521 void
 522 cilk_outline (tree inner_fn, tree *stmt_p, void *w)
 523 {
 524   struct wrapper_data *wd = (struct wrapper_data *) w;
 525   const tree outer_fn = wd->context;
 526   const bool nested = (wd->type == CILK_BLOCK_FOR);
 527   copy_body_data id;
 528   bool throws;
 529   auto_vec<struct cilk_decls> vd;
 530   unsigned int j;
 531   struct cilk_decls * c;
 532
 533   DECL_STATIC_CHAIN (outer_fn) = 1;
 534
 535   memset (&id, 0, sizeof (id));
 536   /* Copy from the function containing the spawn...  */
 537   id.src_fn = outer_fn;
 538
 539   /* ...to the wrapper.  */
 540   id.dst_fn = inner_fn;
 541   id.src_cfun = DECL_STRUCT_FUNCTION (outer_fn);
 542
 543   /* There shall be no RETURN in spawn helper.  */
 544   id.retvar = 0;
 545   id.decl_map = wd->decl_map;
 546   id.copy_decl = nested ? copy_decl_no_change : copy_decl_for_cilk;
 547   id.block = DECL_INITIAL (inner_fn);
 548   id.transform_lang_insert_block = NULL;
 549
 550   id.transform_new_cfg = true;
 551   id.transform_call_graph_edges = CB_CGE_MOVE;
 552   id.remap_var_for_cilk = true;
 553   id.regimplify = true; /* unused? */
 554
 555   insert_decl_map (&id, wd->block, DECL_INITIAL (inner_fn));
 556
 557   wd->decl_map->traverse<auto_vec<struct cilk_decls> *, fill_decls_vec> (&vd);
 558   vd.qsort (compare_decls);
 559   /* We don't want the private variables any more.  */
 560   FOR_EACH_VEC_ELT (vd, j, c)
 561    if (*(c->val) == error_mark_node)
 562      *(c->val) = nested ? copy_decl_no_change (c->key, &id)
 563                         : copy_decl_for_cilk (c->key, &id);
 564
 565   walk_tree (stmt_p, copy_tree_body_r, (void *) &id, NULL);
 566
 567   /* See if this function can throw or calls something that should
 568      not be spawned.  The exception part is only necessary if
 569      flag_exceptions && !flag_non_call_exceptions.  */
 570   throws = false ;
 571   (void) walk_tree_without_duplicates (stmt_p, check_outlined_calls, &throws);
 572 }
 573
 574 /* Generate the body of a wrapper function that assigns the
 575    result of the expression RHS into RECEIVER.  RECEIVER must
 576    be NULL if this is not a spawn -- the wrapper will return
 577    a value.  If this is a spawn, the wrapper will return void.  */
 578
 579 static tree
 580 create_cilk_wrapper_body (tree stmt, struct wrapper_data *wd)
 581 {
 582   const tree outer = current_function_decl;
 583   tree fndecl;
 584   tree p;
 585
 586    /* Build the type of the wrapper and its argument list from the
 587      variables that it requires.  */
 588   build_wrapper_type (wd);
 589
 590   /* Emit a function that takes WRAPPER_PARMS incoming and applies ARGS
 591      (modified) to the wrapped function.  Return the wrapper and modified ARGS
 592      to the caller to generate a function call.  */
 593   fndecl = create_cilk_helper_decl (wd);
 594   push_struct_function (fndecl);
 595   if (wd->nested && (wd->type == CILK_BLOCK_FOR))
 596     {
 597       gcc_assert (TREE_VALUE (wd->arglist) == NULL_TREE);
 598       TREE_VALUE (wd->arglist) = build2 (FDESC_EXPR, ptr_type_node,
 599                                          fndecl, integer_one_node);
 600     }
 601   DECL_ARGUMENTS (fndecl) = wd->parms;
 602
 603   for (p = wd->parms; p; p = TREE_CHAIN (p))
 604     DECL_CONTEXT (p) = fndecl;
 605
 606   gcc_assert (!DECL_SAVED_TREE (fndecl));
 607   cilk_install_body_with_frame_cleanup (fndecl, stmt, (void *) wd);
 608   gcc_assert (DECL_SAVED_TREE (fndecl));
 609
 610   pop_cfun_to (outer);
 611
 612   /* Recognize the new function.  */
 613   call_graph_add_fn (fndecl);
 614   return fndecl;
 615 }
 616
 617 /* Initializes the wrapper data structure.  */
 618
 619 static void
 620 init_wd (struct wrapper_data *wd, enum cilk_block_type type)
 621 {
 622   wd->type = type;
 623   wd->fntype = NULL_TREE;
 624   wd->context = current_function_decl;
 625   wd->decl_map = new hash_map<tree, tree>;
 626   /* _Cilk_for bodies are always nested.  Others start off as
 627      normal functions.  */
 628   wd->nested = (type == CILK_BLOCK_FOR);
 629   wd->arglist = NULL_TREE;
 630   wd->argtypes = NULL_TREE;
 631   wd->block = NULL_TREE;
 632 }
 633
 634 /* Clears the wrapper data structure.  */
 635
 636 static void
 637 free_wd (struct wrapper_data *wd)
 638 {
 639   delete wd->decl_map;
 640   wd->nested = false;
 641   wd->arglist = NULL_TREE;
 642   wd->argtypes = NULL_TREE;
 643   wd->parms = NULL_TREE;
 644 }
 645
 646
 647  /* Given a variable in an expression to be extracted into
 648    a helper function, declare the helper function parameter
 649    to receive it.
 650
 651    On entry the value of the (key, value) pair may be
 652
 653    (*, error_mark_node) -- Variable is private to helper function,
 654    do nothing.
 655
 656    (var, var) -- Reference to outer scope (function or global scope).
 657
 658    (var, integer 0) -- Capture by value, save newly-declared PARM_DECL
 659    for value in value slot.
 660
 661    (var, integer 1) -- Capture by reference, declare pointer to type
 662    as new PARM_DECL and store (spawn_stmt (indirect_ref (parm)).
 663
 664    (var, ???) -- Pure output argument, handled similarly to above.
 665 */
 666
 667 bool
 668 declare_one_free_variable (tree var0, tree *map0)
 669 {
 670   const_tree var = var0;
 671   tree map = *map0;
 672   tree var_type = TREE_TYPE (var), arg_type;
 673   bool by_reference;
 674   tree parm;
 675
 676   gcc_assert (DECL_P (var));
 677
 678   /* Ignore truly local variables.  */
 679   if (map == error_mark_node)
 680     return true;
 681   /* Ignore references to the parent function.  */
 682   if (map == var)
 683     return true;
 684
 685   gcc_assert (TREE_CODE (map) == INTEGER_CST);
 686
 687   /* A value is passed by reference if:
 688
 689      1. It is addressable, so that a copy may not be made.
 690      2. It is modified in the spawned statement.
 691      In the future this function may want to arrange
 692      a warning if the spawned statement is a loop body
 693      because an output argument would indicate a race.
 694      Note: Earlier passes must have marked the variable addressable.
 695      3. It is expensive to copy.  */
 696   by_reference =
 697     (TREE_ADDRESSABLE (var_type)
 698      /* Arrays must be passed by reference.  This is required for C
 699         semantics -- arrays are not first class objects.  Other
 700         aggregate types can and should be passed by reference if
 701         they are not passed to the spawned function.  We aren't yet
 702         distinguishing safe uses in argument calculation from unsafe
 703         uses as outgoing function arguments, so we make a copy to
 704         stabilize the value.  */
 705      || TREE_CODE (var_type) == ARRAY_TYPE
 706      || (tree) map == integer_one_node);
 707
 708   if (by_reference)
 709     var_type = build_qualified_type (build_pointer_type (var_type),
 710                                      TYPE_QUAL_RESTRICT);
 711   gcc_assert (!TREE_ADDRESSABLE (var_type));
 712
 713   /* Maybe promote to int.  */
 714   if (INTEGRAL_TYPE_P (var_type) && COMPLETE_TYPE_P (var_type)
 715       && tree_int_cst_lt (TYPE_SIZE (var_type), TYPE_SIZE (integer_type_node)))
 716     arg_type = integer_type_node;
 717   else
 718     arg_type = var_type;
 719
 720   parm = build_decl (UNKNOWN_LOCATION, PARM_DECL, NULL_TREE, var_type);
 721   DECL_ARG_TYPE (parm) = arg_type;
 722   DECL_ARTIFICIAL (parm) = 0;
 723   TREE_READONLY (parm) = 1;
 724
 725   if (by_reference)
 726     {
 727       parm = build1 (INDIRECT_REF, TREE_TYPE (var_type), parm);
 728       parm = build1 (PAREN_EXPR, void_type_node, parm);
 729     }
 730   *map0 = parm;
 731   return true;
 732 }
 733
 734 /* Returns a wrapper function for a _Cilk_spawn.  */
 735
 736 static tree
 737 create_cilk_wrapper (tree exp, tree *args_out)
 738 {
 739   struct wrapper_data wd;
 740   tree fndecl;
 741   unsigned int j;
 742   struct cilk_decls * c;
 743   auto_vec<struct cilk_decls> vd;
 744
 745   init_wd (&wd, CILK_BLOCK_SPAWN);
 746
 747   if (TREE_CODE (exp) == CONVERT_EXPR)
 748     exp = TREE_OPERAND (exp, 0);
 749
 750   /* Special handling for top level INIT_EXPR.  Usually INIT_EXPR means the
 751      variable is defined in the spawned expression and can be private to the
 752      spawn helper.  A top level INIT_EXPR defines a variable to be initialized
 753      by spawn and the variable must remain in the outer function.  */
 754   if (TREE_CODE (exp) == INIT_EXPR)
 755     {
 756       extract_free_variables (TREE_OPERAND (exp, 0), &wd, ADD_WRITE);
 757       extract_free_variables (TREE_OPERAND (exp, 1), &wd, ADD_READ);
 758       /* TREE_TYPE should be void.  Be defensive.  */
 759       if (TREE_TYPE (exp) != void_type_node)
 760         extract_free_variables (TREE_TYPE (exp), &wd, ADD_READ);
 761     }
 762   else
 763     extract_free_variables (exp, &wd, ADD_READ);
 764   wd.decl_map->traverse<auto_vec<struct cilk_decls> *, fill_decls_vec> (&vd);
 765   vd.qsort (compare_decls);
 766   FOR_EACH_VEC_ELT (vd, j, c)
 767    declare_one_free_variable (c->key, c->val);
 768
 769   wd.block = TREE_BLOCK (exp);
 770   if (!wd.block)
 771     wd.block = DECL_INITIAL (current_function_decl);
 772
 773   /* Now fvars maps the old variable to incoming variable.  Update
 774      the expression and arguments to refer to the new names.  */
 775   fndecl = create_cilk_wrapper_body (exp, &wd);
 776   *args_out = wd.arglist;
 777
 778   free_wd (&wd);
 779
 780   return fndecl;
 781 }
 782
 783 /* Transform *SPAWN_P, a spawned CALL_EXPR, to gimple.  *SPAWN_P can be a
 784    CALL_EXPR, INIT_EXPR or MODIFY_EXPR.  Returns GS_OK if everything is fine,
 785    and GS_UNHANDLED, otherwise.  */
 786
 787 int
 788 gimplify_cilk_spawn (tree *spawn_p)
 789 {
 790   tree expr = *spawn_p;
 791   tree function, call1, call2, new_args;
 792   tree ii_args = NULL_TREE;
 793   int total_args = 0, ii = 0;
 794   tree *arg_array;
 795   tree setjmp_cond_expr = NULL_TREE;
 796   tree setjmp_expr, spawn_expr, setjmp_value = NULL_TREE;
 797
 798   cfun->calls_cilk_spawn = 1;
 799   cfun->is_cilk_function = 1;
 800
 801   /* Remove CLEANUP_POINT_EXPR and EXPR_STMT from *spawn_p.  */
 802   while (TREE_CODE (expr) == CLEANUP_POINT_EXPR
 803          || TREE_CODE (expr) == EXPR_STMT)
 804     expr = TREE_OPERAND (expr, 0);
 805
 806   new_args = NULL;
 807   function = create_cilk_wrapper (expr, &new_args);
 808
 809   /* This should give the number of parameters.  */
 810   total_args = list_length (new_args);
 811   if (total_args)
 812     arg_array = XNEWVEC (tree, total_args);
 813   else
 814     arg_array = NULL;
 815
 816   ii_args = new_args;
 817   for (ii = 0; ii < total_args; ii++)
 818     {
 819       arg_array[ii] = TREE_VALUE (ii_args);
 820       ii_args = TREE_CHAIN (ii_args);
 821     }
 822
 823   TREE_USED (function) = 1;
 824   rest_of_decl_compilation (function, 0, 0);
 825
 826   call1 = cilk_call_setjmp (cfun->cilk_frame_decl);
 827
 828   if (arg_array == NULL || *arg_array == NULL_TREE)
 829     call2 = build_call_expr (function, 0);
 830   else
 831     call2 = build_call_expr_loc_array (EXPR_LOCATION (*spawn_p), function,
 832                                          total_args, arg_array);
 833   *spawn_p = alloc_stmt_list ();
 834   tree f_ptr_type = build_pointer_type (TREE_TYPE (cfun->cilk_frame_decl));
 835   tree frame_ptr = build1 (ADDR_EXPR, f_ptr_type, cfun->cilk_frame_decl);
 836   tree save_fp = build_call_expr (cilk_save_fp_fndecl, 1, frame_ptr);
 837   append_to_statement_list (save_fp, spawn_p);
 838   setjmp_value = create_tmp_var (TREE_TYPE (call1));
 839   setjmp_expr = fold_build2 (MODIFY_EXPR, void_type_node, setjmp_value, call1);
 840
 841   append_to_statement_list_force (setjmp_expr, spawn_p);
 842
 843   setjmp_cond_expr = fold_build2 (EQ_EXPR, TREE_TYPE (call1), setjmp_value,
 844                                   build_int_cst (TREE_TYPE (call1), 0));
 845   spawn_expr = fold_build3 (COND_EXPR, void_type_node, setjmp_cond_expr,
 846                             call2, build_empty_stmt (EXPR_LOCATION (call1)));
 847   append_to_statement_list (spawn_expr, spawn_p);
 848
 849   return GS_OK;
 850 }
 851
 852 /* Make the frames necessary for a spawn call.  */
 853
 854 tree
 855 make_cilk_frame (tree fn)
 856 {
 857   struct function *f = DECL_STRUCT_FUNCTION (fn);
 858   tree decl;
 859
 860   if (f->cilk_frame_decl)
 861     return f->cilk_frame_decl;
 862
 863   decl = build_decl (EXPR_LOCATION (fn), VAR_DECL, NULL_TREE,
 864                      cilk_frame_type_decl);
 865   DECL_CONTEXT (decl) = fn;
 866   DECL_SEEN_IN_BIND_EXPR_P (decl) = 1;
 867   f->cilk_frame_decl = decl;
 868   return decl;
 869 }
 870
 871 /* Returns a STATEMENT_LIST with all the pedigree operations required for
 872    install body with frame cleanup functions.  FRAME_PTR is the pointer to
 873    __cilkrts_stack_frame created by make_cilk_frame.  */
 874
 875 tree
 876 cilk_install_body_pedigree_operations (tree frame_ptr)
 877 {
 878   tree body_list = alloc_stmt_list ();
 879   tree enter_frame = build_call_expr (cilk_enter_fast_fndecl, 1, frame_ptr);
 880   append_to_statement_list (enter_frame, &body_list);
 881
 882   tree parent = cilk_arrow (frame_ptr, CILK_TI_FRAME_PARENT, 0);
 883   tree worker = cilk_arrow (frame_ptr, CILK_TI_FRAME_WORKER, 0);
 884
 885   tree pedigree = cilk_arrow (frame_ptr, CILK_TI_FRAME_PEDIGREE, 0);
 886   tree pedigree_rank = cilk_dot (pedigree, CILK_TI_PEDIGREE_RANK, 0);
 887   tree parent_pedigree = cilk_dot (pedigree, CILK_TI_PEDIGREE_PARENT, 0);
 888   tree pedigree_parent = cilk_arrow (parent, CILK_TI_FRAME_PEDIGREE, 0);
 889   tree pedigree_parent_rank = cilk_dot (pedigree_parent,
 890                                         CILK_TI_PEDIGREE_RANK, 0);
 891   tree pedigree_parent_parent = cilk_dot (pedigree_parent,
 892                                      CILK_TI_PEDIGREE_PARENT, 0);
 893   tree worker_pedigree = cilk_arrow (worker, CILK_TI_WORKER_PEDIGREE, 1);
 894   tree w_pedigree_rank = cilk_dot (worker_pedigree, CILK_TI_PEDIGREE_RANK, 0);
 895   tree w_pedigree_parent = cilk_dot (worker_pedigree,
 896                                      CILK_TI_PEDIGREE_PARENT, 0);
 897
 898   /* sf.pedigree.rank = worker->pedigree.rank.  */
 899   tree exp1 = build2 (MODIFY_EXPR, void_type_node, pedigree_rank,
 900                      w_pedigree_rank);
 901   append_to_statement_list (exp1, &body_list);
 902
 903   /* sf.pedigree.parent = worker->pedigree.parent.  */
 904   exp1 = build2 (MODIFY_EXPR, void_type_node, parent_pedigree,
 905                  w_pedigree_parent);
 906   append_to_statement_list (exp1, &body_list);
 907
 908   /* sf.call_parent->pedigree.rank = worker->pedigree.rank.  */
 909   exp1 = build2 (MODIFY_EXPR, void_type_node, pedigree_parent_rank,
 910                  w_pedigree_rank);
 911   append_to_statement_list (exp1, &body_list);
 912
 913   /* sf.call_parent->pedigree.parent = worker->pedigree.parent.  */
 914   exp1 = build2 (MODIFY_EXPR, void_type_node, pedigree_parent_parent,
 915                  w_pedigree_parent);
 916   append_to_statement_list (exp1, &body_list);
 917
 918   /* sf->worker.pedigree.rank = 0.  */
 919   exp1 = build2 (MODIFY_EXPR, void_type_node, w_pedigree_rank,
 920                  build_zero_cst (uint64_type_node));
 921   append_to_statement_list (exp1, &body_list);
 922
 923   /* sf->pedigree.parent = &sf->pedigree.  */
 924   exp1 = build2 (MODIFY_EXPR, void_type_node, w_pedigree_parent,
 925                  build1 (ADDR_EXPR,
 926                          build_pointer_type (cilk_pedigree_type_decl),
 927                          pedigree));
 928   append_to_statement_list (exp1, &body_list);
 929   return body_list;
 930 }
 931
 932 /* Add a new variable, VAR to a variable list in WD->DECL_MAP.  HOW indicates
 933    whether the variable is previously defined, currently defined, or a variable
 934    that is being written to.  */
 935
 936 static void
 937 add_variable (struct wrapper_data *wd, tree var, enum add_variable_type how)
 938 {
 939   tree *valp = wd->decl_map->get (var);
 940   if (valp)
 941     {
 942       tree val = (tree) *valp;
 943       /* If the variable is local, do nothing.  */
 944       if (val == error_mark_node)
 945         return;
 946       /* If the variable was entered with itself as value,
 947          meaning it belongs to an outer scope, do not alter
 948          the value.  */
 949       if (val == var)
 950         return;
 951       /* A statement expression may cause a variable to be
 952          bound twice, once in BIND_EXPR and again in a
 953          DECL_EXPR.  That case caused a return in the
 954          test above.  Any other duplicate definition is
 955          an error.  */
 956       gcc_assert (how != ADD_BIND);
 957       if (how != ADD_WRITE)
 958         return;
 959       /* This variable might have been entered as read but is now written.  */
 960       *valp = var;
 961       wd->nested = true;
 962       return;
 963     }
 964   else
 965     {
 966       tree val = NULL_TREE;
 967
 968       /* Nested function rewriting silently discards hard register
 969          assignments for function scope variables, and they wouldn't
 970          work anyway.  Warn here.  This misses one case: if the
 971          register variable is used as the loop bound or increment it
 972          has already been added to the map.  */
 973       if ((how != ADD_BIND) && (TREE_CODE (var) == VAR_DECL)
 974           && !DECL_EXTERNAL (var) && DECL_HARD_REGISTER (var))
 975         warning (0, "register assignment ignored for %qD used in Cilk block",
 976                  var);
 977
 978       switch (how)
 979         {
 980           /* ADD_BIND means always make a fresh new variable.  */
 981         case ADD_BIND:
 982           val = error_mark_node;
 983           break;
 984           /* ADD_READ means
 985              1. For cilk_for, refer to the outer scope definition as-is
 986              2. For a spawned block, take a scalar in an rgument
 987              and otherwise refer to the outer scope definition as-is.
 988              3. For a spawned call, take a scalar in an argument.  */
 989         case ADD_READ:
 990           switch (wd->type)
 991             {
 992             case CILK_BLOCK_FOR:
 993               val = var;
 994               break;
 995             case CILK_BLOCK_SPAWN:
 996               if (TREE_ADDRESSABLE (var))
 997                 {
 998                   val = var;
 999                   wd->nested = true;
1000                   break;
1001                 }
1002               val = integer_zero_node;
1003               break;
1004             }
1005           break;
1006         case ADD_WRITE:
1007           switch (wd->type)
1008             {
1009             case CILK_BLOCK_FOR:
1010               val = var;
1011               wd->nested = true;
1012               break;
1013             case CILK_BLOCK_SPAWN:
1014               if (TREE_ADDRESSABLE (var))
1015                 val = integer_one_node;
1016               else
1017                 {
1018                   val = var;
1019                   wd->nested = true;
1020                 }
1021               break;
1022             }
1023         }
1024       wd->decl_map->put (var, val);
1025     }
1026 }
1027
1028 /* Find the variables referenced in an expression T.  This does not avoid
1029    duplicates because a variable may be read in one context and written in
1030    another.  HOW describes the context in which the reference is seen.  If
1031    NESTED is true a nested function is being generated and variables in the
1032    original context should not be remapped.  */
1033
1034 static void
1035 extract_free_variables (tree t, struct wrapper_data *wd,
1036                         enum add_variable_type how)
1037 {
1038   if (t == NULL_TREE)
1039     return;
1040
1041   enum tree_code code = TREE_CODE (t);
1042   bool is_expr = IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code));
1043
1044   if (is_expr)
1045     extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1046
1047   switch (code)
1048     {
1049     case ERROR_MARK:
1050     case IDENTIFIER_NODE:
1051     case VOID_CST:
1052     case INTEGER_CST:
1053     case REAL_CST:
1054     case FIXED_CST:
1055     case STRING_CST:
1056     case BLOCK:
1057     case PLACEHOLDER_EXPR:
1058     case FIELD_DECL:
1059     case VOID_TYPE:
1060     case REAL_TYPE:
1061       /* These do not contain variable references.  */
1062       return;
1063
1064     case SSA_NAME:
1065       /* Currently we don't see SSA_NAME.  */
1066       extract_free_variables (SSA_NAME_VAR (t), wd, how);
1067       return;
1068
1069     case LABEL_DECL:
1070       /* This might be a reference to a label outside the Cilk block,
1071          which is an error, or a reference to a label in the Cilk block
1072          that we haven't seen yet.  We can't tell.  Ignore it.  An
1073          invalid use will cause an error later in copy_decl_for_cilk.  */
1074       return;
1075
1076     case RESULT_DECL:
1077       if (wd->type != CILK_BLOCK_SPAWN)
1078         TREE_ADDRESSABLE (t) = 1;
1079     case VAR_DECL:
1080     case PARM_DECL:
1081       if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
1082         add_variable (wd, t, how);
1083       return;
1084
1085     case NON_LVALUE_EXPR:
1086     case CONVERT_EXPR:
1087     case NOP_EXPR:
1088       extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1089       return;
1090
1091     case VEC_INIT_EXPR:
1092     case INIT_EXPR:
1093       extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_BIND);
1094       extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1095       return;
1096
1097     case MODIFY_EXPR:
1098     case PREDECREMENT_EXPR:
1099     case PREINCREMENT_EXPR:
1100     case POSTDECREMENT_EXPR:
1101     case POSTINCREMENT_EXPR:
1102       /* These write their result.  */
1103       extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_WRITE);
1104       extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1105       return;
1106
1107     case ADDR_EXPR:
1108       /* This might modify its argument, and the value needs to be
1109          passed by reference in any case to preserve identity and
1110          type if is a promoting type.  In the case of a nested loop
1111          just notice that we touch the variable.  It will already
1112          be addressable, and marking it modified will cause a spurious
1113          warning about writing the control variable.  */
1114       if (wd->type != CILK_BLOCK_SPAWN)
1115         extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1116       else
1117         extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_WRITE);
1118       return;
1119
1120     case ARRAY_REF:
1121       /* Treating ARRAY_REF and BIT_FIELD_REF identically may
1122          mark the array as written but the end result is correct
1123          because the array is passed by pointer anyway.  */
1124     case BIT_FIELD_REF:
1125       /* Propagate the access type to the object part of which
1126          is being accessed here.  As for ADDR_EXPR, don't do this
1127          in a nested loop, unless the access is to a fixed index.  */
1128       if (wd->type != CILK_BLOCK_FOR || TREE_CONSTANT (TREE_OPERAND (t, 1)))
1129         extract_free_variables (TREE_OPERAND (t, 0), wd, how);
1130       else
1131         extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1132       extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1133       extract_free_variables (TREE_OPERAND (t, 2), wd, ADD_READ);
1134       return;
1135
1136     case TREE_LIST:
1137       extract_free_variables (TREE_PURPOSE (t), wd, ADD_READ);
1138       extract_free_variables (TREE_VALUE (t), wd, ADD_READ);
1139       extract_free_variables (TREE_CHAIN (t), wd, ADD_READ);
1140       return;
1141
1142     case TREE_VEC:
1143       {
1144         int len = TREE_VEC_LENGTH (t);
1145         int i;
1146         for (i = 0; i < len; i++)
1147           extract_free_variables (TREE_VEC_ELT (t, i), wd, ADD_READ);
1148         return;
1149       }
1150
1151     case VECTOR_CST:
1152       {
1153         unsigned ii = 0;
1154         for (ii = 0; ii < VECTOR_CST_NELTS (t); ii++)
1155           extract_free_variables (VECTOR_CST_ELT (t, ii), wd, ADD_READ);
1156         break;
1157       }
1158
1159     case COMPLEX_CST:
1160       extract_free_variables (TREE_REALPART (t), wd, ADD_READ);
1161       extract_free_variables (TREE_IMAGPART (t), wd, ADD_READ);
1162       return;
1163
1164     case BIND_EXPR:
1165       {
1166         tree decl;
1167         for (decl = BIND_EXPR_VARS (t); decl; decl = TREE_CHAIN (decl))
1168           {
1169             add_variable (wd, decl, ADD_BIND);
1170             /* A self-referential initialization is no problem because
1171                we already entered the variable into the map as local.  */
1172             extract_free_variables (DECL_INITIAL (decl), wd, ADD_READ);
1173             extract_free_variables (DECL_SIZE (decl), wd, ADD_READ);
1174             extract_free_variables (DECL_SIZE_UNIT (decl), wd, ADD_READ);
1175           }
1176         extract_free_variables (BIND_EXPR_BODY (t), wd, ADD_READ);
1177         return;
1178       }
1179
1180     case STATEMENT_LIST:
1181       {
1182         tree_stmt_iterator i;
1183         for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
1184           extract_free_variables (*tsi_stmt_ptr (i), wd, ADD_READ);
1185         return;
1186       }
1187
1188     case TARGET_EXPR:
1189       {
1190         extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_BIND);
1191         extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1192         extract_free_variables (TREE_OPERAND (t, 2), wd, ADD_READ);
1193         if (TREE_OPERAND (t, 3) != TREE_OPERAND (t, 1))
1194           extract_free_variables (TREE_OPERAND (t, 3), wd, ADD_READ);
1195         return;
1196       }
1197
1198     case RETURN_EXPR:
1199       if (TREE_NO_WARNING (t))
1200         {
1201           gcc_assert (errorcount);
1202           return;
1203         }
1204       return;
1205
1206     case DECL_EXPR:
1207       if (TREE_CODE (DECL_EXPR_DECL (t)) != TYPE_DECL)
1208         extract_free_variables (DECL_EXPR_DECL (t), wd, ADD_BIND);
1209       return;
1210
1211     case INTEGER_TYPE:
1212     case ENUMERAL_TYPE:
1213     case BOOLEAN_TYPE:
1214       extract_free_variables (TYPE_MIN_VALUE (t), wd, ADD_READ);
1215       extract_free_variables (TYPE_MAX_VALUE (t), wd, ADD_READ);
1216       return;
1217
1218     case POINTER_TYPE:
1219       extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1220       break;
1221
1222     case ARRAY_TYPE:
1223       extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1224       extract_free_variables (TYPE_DOMAIN (t), wd, ADD_READ);
1225       return;
1226
1227     case RECORD_TYPE:
1228       extract_free_variables (TYPE_FIELDS (t), wd, ADD_READ);
1229       return;
1230
1231     case METHOD_TYPE:
1232       extract_free_variables (TYPE_ARG_TYPES (t), wd, ADD_READ);
1233       extract_free_variables (TYPE_METHOD_BASETYPE (t), wd, ADD_READ);
1234       return;
1235
1236     case AGGR_INIT_EXPR:
1237     case CALL_EXPR:
1238       {
1239         int len = 0;
1240         int ii = 0;
1241         if (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST)
1242           {
1243             len = TREE_INT_CST_LOW (TREE_OPERAND (t, 0));
1244
1245             for (ii = 0; ii < len; ii++)
1246               extract_free_variables (TREE_OPERAND (t, ii), wd, ADD_READ);
1247             extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1248           }
1249         break;
1250       }
1251
1252     case CONSTRUCTOR:
1253       {
1254         unsigned HOST_WIDE_INT idx = 0;
1255         constructor_elt *ce;
1256         for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (t), idx, &ce); idx++)
1257           extract_free_variables (ce->value, wd, ADD_READ);
1258         break;
1259       }
1260
1261     default:
1262       if (is_expr)
1263         {
1264           int i, len;
1265
1266           /* Walk over all the sub-trees of this operand.  */
1267           len = TREE_CODE_LENGTH (code);
1268
1269           /* Go through the subtrees.  We need to do this in forward order so
1270              that the scope of a FOR_EXPR is handled properly.  */
1271           for (i = 0; i < len; ++i)
1272             extract_free_variables (TREE_OPERAND (t, i), wd, ADD_READ);
1273         }
1274     }
1275 }
1276
1277 /* Add appropriate frames needed for a Cilk spawned function call, FNDECL.
1278    Returns the __cilkrts_stack_frame * variable.  */
1279
1280 tree
1281 insert_cilk_frame (tree fndecl)
1282 {
1283   tree addr, body, enter, out, orig_body;
1284   location_t loc = EXPR_LOCATION (fndecl);
1285
1286   if (!cfun || cfun->decl != fndecl)
1287     push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1288
1289   tree decl = cfun->cilk_frame_decl;
1290   if (!decl)
1291     {
1292       tree *saved_tree = &DECL_SAVED_TREE (fndecl);
1293       decl = make_cilk_frame (fndecl);
1294       add_local_decl (cfun, decl);
1295
1296       addr = build1 (ADDR_EXPR, cilk_frame_ptr_type_decl, decl);
1297       enter = build_call_expr (cilk_enter_fndecl, 1, addr);
1298       out = create_cilk_function_exit (cfun->cilk_frame_decl, false, true);
1299
1300       /* The new body will be:
1301          __cilkrts_enter_frame_1 (&sf);
1302          try {
1303             orig_body;
1304          }
1305          finally {
1306              __cilkrts_pop_frame (&sf);
1307              __cilkrts_leave_frame (&sf);
1308          }  */
1309
1310       body = alloc_stmt_list ();
1311       orig_body = *saved_tree;
1312
1313       if (TREE_CODE (orig_body) == BIND_EXPR)
1314         orig_body = BIND_EXPR_BODY (orig_body);
1315
1316       append_to_statement_list (enter, &body);
1317       append_to_statement_list (build_stmt (loc, TRY_FINALLY_EXPR, orig_body,
1318                                             out), &body);
1319       if (TREE_CODE (*saved_tree) == BIND_EXPR)
1320         BIND_EXPR_BODY (*saved_tree) = body;
1321       else
1322         *saved_tree = body;
1323     }
1324   return decl;
1325 }
1326
1327 /* Wraps CALL, a CALL_EXPR, into a CILK_SPAWN_STMT tree and returns it.  */
1328
1329 tree
1330 build_cilk_spawn (location_t loc, tree call)
1331 {
1332   if (!cilk_set_spawn_marker (loc, call))
1333     return error_mark_node;
1334   tree spawn_stmt = build1 (CILK_SPAWN_STMT, TREE_TYPE (call), call);
1335   TREE_SIDE_EFFECTS (spawn_stmt) = 1;
1336   return spawn_stmt;
1337 }
1338
1339 /* Returns a tree of type CILK_SYNC_STMT.  */
1340
1341 tree
1342 build_cilk_sync (void)
1343 {
1344   tree sync = build0 (CILK_SYNC_STMT, void_type_node);
1345   TREE_SIDE_EFFECTS (sync) = 1;
1346   return sync;
1347 }
1348
1349 /* Helper for contains_cilk_spawn_stmt, callback for walk_tree.  Return
1350    non-null tree if TP contains CILK_SPAWN_STMT.  */
1351
1352 static tree
1353 contains_cilk_spawn_stmt_walker (tree *tp, int *, void *)
1354 {
1355   if (TREE_CODE (*tp) == CILK_SPAWN_STMT)
1356     return *tp;
1357   else
1358     return NULL_TREE;
1359 }
1360
1361 /* Returns true if EXPR or any of its subtrees contain CILK_SPAWN_STMT
1362    node.  */
1363
1364 bool
1365 contains_cilk_spawn_stmt (tree expr)
1366 {
1367   return walk_tree (&expr, contains_cilk_spawn_stmt_walker, NULL, NULL)
1368          != NULL_TREE;
1369 }
1370
1371 /* Return a error location for EXPR if LOC is not set.  */
1372
1373 static location_t
1374 get_error_location (tree expr, location_t loc)
1375 {
1376   if (loc == UNKNOWN_LOCATION)
1377     {
1378       if (TREE_CODE (expr) == MODIFY_EXPR)
1379         expr = TREE_OPERAND (expr, 0);
1380       loc = EXPR_LOCATION (expr);
1381     }
1382   return loc;
1383 }
1384
1385 /* Check that no array notation or spawn statement is in EXPR.
1386    If not true generate an error at LOC for ARRAY_GMSGID or
1387    SPAWN_MSGID.  */
1388
1389 bool
1390 check_no_cilk (tree expr, const char *array_msgid, const char *spawn_msgid,
1391               location_t loc)
1392 {
1393   if (!flag_cilkplus)
1394     return false;
1395   if (contains_array_notation_expr (expr))
1396     {
1397       loc = get_error_location (expr, loc);
1398       error_at (loc, array_msgid);
1399       return true;
1400     }
1401   if (walk_tree (&expr, contains_cilk_spawn_stmt_walker, NULL, NULL))
1402     {
1403       loc = get_error_location (expr, loc);
1404       error_at (loc, spawn_msgid);
1405       return true;
1406     }
1407   return false;
1408 }