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