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