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