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