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