2014-07-29 Ed Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / c-family / cilk.c
blobb864bb1eb63a610bfc65ba77db29f0efd04c7f53
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
7 This file is part of GCC.
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.
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.
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/>. */
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"
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
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
58 struct wrapper_data
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;
80 static void extract_free_variables (tree, struct wrapper_data *,
81 enum add_variable_type);
82 static HOST_WIDE_INT cilk_wrapper_count;
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. */
88 inline bool
89 cilk_set_spawn_marker (location_t loc, tree fcall)
91 if (!current_function_decl)
93 error_at (loc, "%<_Cilk_spawn%> may only be used inside a function");
94 return false;
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)
106 error_at (loc, "only function calls can be spawned");
107 return false;
109 else
111 cfun->calls_cilk_spawn = true;
112 return true;
116 /* This function will output the exit conditions for a spawn call. */
118 tree
119 create_cilk_function_exit (tree frame, bool detaches, bool needs_sync)
121 tree epi = alloc_stmt_list ();
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)
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)));
143 append_to_statement_list (call, &epi);
144 return epi;
147 /* Trying to get the correct cfun for the FUNCTION_DECL indicated by OUTER. */
149 static void
150 pop_cfun_to (tree outer)
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);
158 /* This function does whatever is necessary to make the compiler emit a newly
159 generated function, FNDECL. */
161 static void
162 call_graph_add_fn (tree fndecl)
164 const tree outer = current_function_decl;
165 struct function *f = DECL_STRUCT_FUNCTION (fndecl);
166 gcc_assert (TREE_CODE (fndecl) == FUNCTION_DECL);
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);
173 push_cfun (f);
174 cgraph_node::create (fndecl);
175 pop_cfun_to (outer);
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. */
188 static bool
189 cilk_ignorable_spawn_rhs_op (tree exp)
191 enum tree_code code = TREE_CODE (exp);
192 switch (TREE_CODE_CLASS (code))
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;
209 /* Helper function for walk_tree. If *TP is a CILK_SPAWN_STMT, then unwrap
210 this "wrapper." The function returns NULL_TREE regardless. */
212 static tree
213 unwrap_cilk_spawn_stmt (tree *tp, int *walk_subtrees, void *)
215 if (TREE_CODE (*tp) == CILK_SPAWN_STMT)
217 *tp = CILK_SPAWN_FN (*tp);
218 *walk_subtrees = 0;
220 return NULL_TREE;
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. */
226 static bool
227 recognize_spawn (tree exp, tree *exp0)
229 bool spawn_found = false;
230 if (TREE_CODE (exp) == CILK_SPAWN_STMT)
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;
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;
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. */
250 bool
251 cilk_detect_spawn_and_unwrap (tree *exp0)
253 tree exp = *exp0;
255 if (!TREE_SIDE_EFFECTS (exp))
256 return false;
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);
263 if (TREE_CODE (exp) == MODIFY_EXPR || TREE_CODE (exp) == INIT_EXPR)
264 exp = TREE_OPERAND (exp, 1);
266 while (cilk_ignorable_spawn_rhs_op (exp))
267 exp = TREE_OPERAND (exp, 0);
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);
274 /* Happens with C++ TARGET_EXPR. */
275 if (exp == NULL_TREE)
276 return false;
278 while (TREE_CODE (exp) == CLEANUP_POINT_EXPR || TREE_CODE (exp) == EXPR_STMT)
279 exp = TREE_OPERAND (exp, 0);
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;
288 /* This function will build and return a FUNCTION_DECL using information
289 from *WD. */
291 static tree
292 create_cilk_helper_decl (struct wrapper_data *wd)
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 ();
302 clean_symbol_name (name);
303 tree fndecl = build_decl (UNKNOWN_LOCATION, FUNCTION_DECL,
304 get_identifier (name), wd->fntype);
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;
313 DECL_CONTEXT (fndecl) = wd->context;
314 tree block = make_node (BLOCK);
315 DECL_INITIAL (fndecl) = block;
316 TREE_USED (block) = 1;
317 BLOCK_SUPERCONTEXT (block) = fndecl;
318 gcc_assert (!DECL_SAVED_TREE (fndecl));
320 /* Inlining would defeat the purpose of this wrapper.
321 Either it secretly switches stack frames or it allocates
322 a stable stack frame to hold function arguments even if
323 the parent stack frame is stolen. */
324 DECL_UNINLINABLE (fndecl) = 1;
326 tree result_decl = build_decl (UNKNOWN_LOCATION, RESULT_DECL, NULL_TREE,
327 void_type_node);
328 DECL_ARTIFICIAL (result_decl) = 0;
329 DECL_IGNORED_P (result_decl) = 1;
330 DECL_CONTEXT (result_decl) = fndecl;
331 DECL_RESULT (fndecl) = result_decl;
333 return fndecl;
336 /* A function used by walk tree to find wrapper parms. */
338 static bool
339 wrapper_parm_cb (const void *key0, void **val0, void *data)
341 struct wrapper_data *wd = (struct wrapper_data *) data;
342 tree arg = * (tree *)&key0;
343 tree val = (tree)*val0;
344 tree parm;
346 if (val == error_mark_node || val == arg)
347 return true;
349 if (TREE_CODE (val) == PAREN_EXPR)
351 /* We should not reach here with a register receiver.
352 We may see a register variable modified in the
353 argument list. Because register variables are
354 worker-local we don't need to work hard to support
355 them in code that spawns. */
356 if ((TREE_CODE (arg) == VAR_DECL) && DECL_HARD_REGISTER (arg))
358 error_at (EXPR_LOCATION (arg),
359 "explicit register variable %qD may not be modified in "
360 "spawn", arg);
361 arg = null_pointer_node;
363 else
364 arg = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (arg)), arg);
366 val = TREE_OPERAND (val, 0);
367 *val0 = val;
368 gcc_assert (TREE_CODE (val) == INDIRECT_REF);
369 parm = TREE_OPERAND (val, 0);
370 STRIP_NOPS (parm);
372 else
373 parm = val;
374 TREE_CHAIN (parm) = wd->parms;
375 wd->parms = parm;
376 wd->argtypes = tree_cons (NULL_TREE, TREE_TYPE (parm), wd->argtypes);
377 wd->arglist = tree_cons (NULL_TREE, arg, wd->arglist);
378 return true;
381 /* This function is used to build a wrapper of a certain type. */
383 static void
384 build_wrapper_type (struct wrapper_data *wd)
386 wd->arglist = NULL_TREE;
387 wd->parms = NULL_TREE;
388 wd->argtypes = void_list_node;
390 pointer_map_traverse (wd->decl_map, wrapper_parm_cb, wd);
391 gcc_assert (wd->type != CILK_BLOCK_FOR);
393 /* Now build a function.
394 Its return type is void (all side effects are via explicit parameters).
395 Its parameters are WRAPPER_PARMS with type WRAPPER_TYPES.
396 Actual arguments in the caller are WRAPPER_ARGS. */
397 wd->fntype = build_function_type (void_type_node, wd->argtypes);
400 /* This function checks all the CALL_EXPRs in *TP found by cilk_outline. */
402 static tree
403 check_outlined_calls (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
404 void *data)
406 bool *throws = (bool *) data;
407 tree t = *tp;
408 int flags;
410 if (TREE_CODE (t) != CALL_EXPR)
411 return 0;
412 flags = call_expr_flags (t);
414 if (!(flags & ECF_NOTHROW) && flag_exceptions)
415 *throws = true;
416 if (flags & ECF_RETURNS_TWICE)
417 error_at (EXPR_LOCATION (t),
418 "cannot spawn call to function that returns twice");
419 return 0;
422 /* Each DECL in the source code (spawned statement) is passed to this function
423 once. Each instance of the DECL is replaced with the result of this
424 function.
426 The parameters of the wrapper should have been entered into the map already.
427 This function only deals with variables with scope limited to the
428 spawned expression. */
430 static tree
431 copy_decl_for_cilk (tree decl, copy_body_data *id)
433 switch (TREE_CODE (decl))
435 case VAR_DECL:
436 return copy_decl_no_change (decl, id);
438 case LABEL_DECL:
439 error_at (EXPR_LOCATION (decl), "invalid use of label %q+D in "
440 "%<_Cilk_spawn%>",
441 decl);
442 return error_mark_node;
444 case RESULT_DECL:
445 case PARM_DECL:
446 /* RESULT_DECL and PARM_DECL has already been entered into the map. */
447 default:
448 gcc_unreachable ();
449 return error_mark_node;
453 /* Copy all local variables. */
455 static bool
456 for_local_cb (const void *k_v, void **vp, void *p)
458 tree k = *(tree *) &k_v;
459 tree v = (tree) *vp;
461 if (v == error_mark_node)
462 *vp = copy_decl_no_change (k, (copy_body_data *) p);
463 return true;
466 /* Copy all local declarations from a _Cilk_spawned function's body. */
468 static bool
469 wrapper_local_cb (const void *k_v, void **vp, void *data)
471 copy_body_data *id = (copy_body_data *) data;
472 tree key = *(tree *) &k_v;
473 tree val = (tree) *vp;
475 if (val == error_mark_node)
476 *vp = copy_decl_for_cilk (key, id);
478 return true;
481 /* Alter a tree STMT from OUTER_FN to form the body of INNER_FN. */
483 void
484 cilk_outline (tree inner_fn, tree *stmt_p, void *w)
486 struct wrapper_data *wd = (struct wrapper_data *) w;
487 const tree outer_fn = wd->context;
488 const bool nested = (wd->type == CILK_BLOCK_FOR);
489 copy_body_data id;
490 bool throws;
492 DECL_STATIC_CHAIN (outer_fn) = 1;
494 memset (&id, 0, sizeof (id));
495 /* Copy from the function containing the spawn... */
496 id.src_fn = outer_fn;
498 /* ...to the wrapper. */
499 id.dst_fn = inner_fn;
500 id.src_cfun = DECL_STRUCT_FUNCTION (outer_fn);
502 /* There shall be no RETURN in spawn helper. */
503 id.retvar = 0;
504 id.decl_map = wd->decl_map;
505 id.copy_decl = nested ? copy_decl_no_change : copy_decl_for_cilk;
506 id.block = DECL_INITIAL (inner_fn);
507 id.transform_lang_insert_block = NULL;
509 id.transform_new_cfg = true;
510 id.transform_call_graph_edges = CB_CGE_MOVE;
511 id.remap_var_for_cilk = true;
512 id.regimplify = true; /* unused? */
514 insert_decl_map (&id, wd->block, DECL_INITIAL (inner_fn));
516 /* We don't want the private variables any more. */
517 pointer_map_traverse (wd->decl_map, nested ? for_local_cb : wrapper_local_cb,
518 &id);
519 walk_tree (stmt_p, copy_tree_body_r, (void *) &id, NULL);
521 /* See if this function can throw or calls something that should
522 not be spawned. The exception part is only necessary if
523 flag_exceptions && !flag_non_call_exceptions. */
524 throws = false ;
525 (void) walk_tree_without_duplicates (stmt_p, check_outlined_calls, &throws);
528 /* Generate the body of a wrapper function that assigns the
529 result of the expression RHS into RECEIVER. RECEIVER must
530 be NULL if this is not a spawn -- the wrapper will return
531 a value. If this is a spawn, the wrapper will return void. */
533 static tree
534 create_cilk_wrapper_body (tree stmt, struct wrapper_data *wd)
536 const tree outer = current_function_decl;
537 tree fndecl;
538 tree p;
540 /* Build the type of the wrapper and its argument list from the
541 variables that it requires. */
542 build_wrapper_type (wd);
544 /* Emit a function that takes WRAPPER_PARMS incoming and applies ARGS
545 (modified) to the wrapped function. Return the wrapper and modified ARGS
546 to the caller to generate a function call. */
547 fndecl = create_cilk_helper_decl (wd);
548 push_struct_function (fndecl);
549 if (wd->nested && (wd->type == CILK_BLOCK_FOR))
551 gcc_assert (TREE_VALUE (wd->arglist) == NULL_TREE);
552 TREE_VALUE (wd->arglist) = build2 (FDESC_EXPR, ptr_type_node,
553 fndecl, integer_one_node);
555 DECL_ARGUMENTS (fndecl) = wd->parms;
557 for (p = wd->parms; p; p = TREE_CHAIN (p))
558 DECL_CONTEXT (p) = fndecl;
560 gcc_assert (!DECL_SAVED_TREE (fndecl));
561 cilk_install_body_with_frame_cleanup (fndecl, stmt, (void *) wd);
562 gcc_assert (DECL_SAVED_TREE (fndecl));
564 pop_cfun_to (outer);
566 /* Recognize the new function. */
567 call_graph_add_fn (fndecl);
568 return fndecl;
571 /* Initializes the wrapper data structure. */
573 static void
574 init_wd (struct wrapper_data *wd, enum cilk_block_type type)
576 wd->type = type;
577 wd->fntype = NULL_TREE;
578 wd->context = current_function_decl;
579 wd->decl_map = pointer_map_create ();
580 /* _Cilk_for bodies are always nested. Others start off as
581 normal functions. */
582 wd->nested = (type == CILK_BLOCK_FOR);
583 wd->arglist = NULL_TREE;
584 wd->argtypes = NULL_TREE;
585 wd->block = NULL_TREE;
588 /* Clears the wrapper data structure. */
590 static void
591 free_wd (struct wrapper_data *wd)
593 pointer_map_destroy (wd->decl_map);
594 wd->nested = false;
595 wd->arglist = NULL_TREE;
596 wd->argtypes = NULL_TREE;
597 wd->parms = NULL_TREE;
601 /* Given a variable in an expression to be extracted into
602 a helper function, declare the helper function parameter
603 to receive it.
605 On entry the value of the (key, value) pair may be
607 (*, error_mark_node) -- Variable is private to helper function,
608 do nothing.
610 (var, var) -- Reference to outer scope (function or global scope).
612 (var, integer 0) -- Capture by value, save newly-declared PARM_DECL
613 for value in value slot.
615 (var, integer 1) -- Capture by reference, declare pointer to type
616 as new PARM_DECL and store (spawn_stmt (indirect_ref (parm)).
618 (var, ???) -- Pure output argument, handled similarly to above.
621 static bool
622 declare_one_free_variable (const void *var0, void **map0,
623 void *data ATTRIBUTE_UNUSED)
625 const_tree var = (const_tree) var0;
626 tree map = (tree)*map0;
627 tree var_type = TREE_TYPE (var), arg_type;
628 bool by_reference;
629 tree parm;
631 gcc_assert (DECL_P (var));
633 /* Ignore truly local variables. */
634 if (map == error_mark_node)
635 return true;
636 /* Ignore references to the parent function. */
637 if (map == var)
638 return true;
640 gcc_assert (TREE_CODE (map) == INTEGER_CST);
642 /* A value is passed by reference if:
644 1. It is addressable, so that a copy may not be made.
645 2. It is modified in the spawned statement.
646 In the future this function may want to arrange
647 a warning if the spawned statement is a loop body
648 because an output argument would indicate a race.
649 Note: Earlier passes must have marked the variable addressable.
650 3. It is expensive to copy. */
651 by_reference =
652 (TREE_ADDRESSABLE (var_type)
653 /* Arrays must be passed by reference. This is required for C
654 semantics -- arrays are not first class objects. Other
655 aggregate types can and should be passed by reference if
656 they are not passed to the spawned function. We aren't yet
657 distinguishing safe uses in argument calculation from unsafe
658 uses as outgoing function arguments, so we make a copy to
659 stabilize the value. */
660 || TREE_CODE (var_type) == ARRAY_TYPE
661 || (tree) map == integer_one_node);
663 if (by_reference)
664 var_type = build_qualified_type (build_pointer_type (var_type),
665 TYPE_QUAL_RESTRICT);
666 gcc_assert (!TREE_ADDRESSABLE (var_type));
668 /* Maybe promote to int. */
669 if (INTEGRAL_TYPE_P (var_type) && COMPLETE_TYPE_P (var_type)
670 && tree_int_cst_lt (TYPE_SIZE (var_type), TYPE_SIZE (integer_type_node)))
671 arg_type = integer_type_node;
672 else
673 arg_type = var_type;
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;
680 if (by_reference)
682 parm = build1 (INDIRECT_REF, TREE_TYPE (var_type), parm);
683 parm = build1 (PAREN_EXPR, void_type_node, parm);
685 *map0 = parm;
686 return true;
689 /* Returns a wrapper function for a _Cilk_spawn. */
691 static tree
692 create_cilk_wrapper (tree exp, tree *args_out)
694 struct wrapper_data wd;
695 tree fndecl;
697 init_wd (&wd, CILK_BLOCK_SPAWN);
699 if (TREE_CODE (exp) == CONVERT_EXPR)
700 exp = TREE_OPERAND (exp, 0);
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)
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);
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);
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;
726 free_wd (&wd);
728 return fndecl;
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. */
736 gimplify_cilk_spawn (tree *spawn_p)
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;
746 cfun->calls_cilk_spawn = 1;
747 cfun->is_cilk_function = 1;
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);
754 new_args = NULL;
755 function = create_cilk_wrapper (expr, &new_args);
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;
764 ii_args = new_args;
765 for (ii = 0; ii < total_args; ii++)
767 arg_array[ii] = TREE_VALUE (ii_args);
768 ii_args = TREE_CHAIN (ii_args);
771 TREE_USED (function) = 1;
772 rest_of_decl_compilation (function, 0, 0);
774 call1 = cilk_call_setjmp (cfun->cilk_frame_decl);
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);
789 append_to_statement_list_force (setjmp_expr, spawn_p);
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);
797 return GS_OK;
800 /* Make the frames necessary for a spawn call. */
802 tree
803 make_cilk_frame (tree fn)
805 struct function *f = DECL_STRUCT_FUNCTION (fn);
806 tree decl;
808 if (f->cilk_frame_decl)
809 return f->cilk_frame_decl;
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;
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. */
823 tree
824 cilk_install_body_pedigree_operations (tree frame_ptr)
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);
830 tree parent = cilk_arrow (frame_ptr, CILK_TI_FRAME_PARENT, 0);
831 tree worker = cilk_arrow (frame_ptr, CILK_TI_FRAME_WORKER, 0);
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);
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);
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);
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);
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);
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);
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;
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. */
884 static void
885 add_variable (struct wrapper_data *wd, tree var, enum add_variable_type how)
887 void **valp;
889 valp = pointer_map_contains (wd->decl_map, (void *) var);
890 if (valp)
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;
914 else
916 tree val = NULL_TREE;
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);
928 switch (how)
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)
942 case CILK_BLOCK_FOR:
943 val = var;
944 break;
945 case CILK_BLOCK_SPAWN:
946 if (TREE_ADDRESSABLE (var))
948 val = var;
949 wd->nested = true;
950 break;
952 val = integer_zero_node;
953 break;
955 break;
956 case ADD_WRITE:
957 switch (wd->type)
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
968 val = var;
969 wd->nested = true;
971 break;
974 *pointer_map_insert (wd->decl_map, (void *) var) = val;
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. */
984 static void
985 extract_free_variables (tree t, struct wrapper_data *wd,
986 enum add_variable_type how)
988 if (t == NULL_TREE)
989 return;
991 enum tree_code code = TREE_CODE (t);
992 bool is_expr = IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code));
994 if (is_expr)
995 extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
997 switch (code)
999 case ERROR_MARK:
1000 case IDENTIFIER_NODE:
1001 case VOID_CST:
1002 case INTEGER_CST:
1003 case REAL_CST:
1004 case FIXED_CST:
1005 case STRING_CST:
1006 case BLOCK:
1007 case PLACEHOLDER_EXPR:
1008 case FIELD_DECL:
1009 case VOID_TYPE:
1010 case REAL_TYPE:
1011 /* These do not contain variable references. */
1012 return;
1014 case SSA_NAME:
1015 /* Currently we don't see SSA_NAME. */
1016 extract_free_variables (SSA_NAME_VAR (t), wd, how);
1017 return;
1019 case LABEL_DECL:
1020 /* This might be a reference to a label outside the Cilk block,
1021 which is an error, or a reference to a label in the Cilk block
1022 that we haven't seen yet. We can't tell. Ignore it. An
1023 invalid use will cause an error later in copy_decl_for_cilk. */
1024 return;
1026 case RESULT_DECL:
1027 if (wd->type != CILK_BLOCK_SPAWN)
1028 TREE_ADDRESSABLE (t) = 1;
1029 case VAR_DECL:
1030 case PARM_DECL:
1031 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
1032 add_variable (wd, t, how);
1033 return;
1035 case NON_LVALUE_EXPR:
1036 case CONVERT_EXPR:
1037 case NOP_EXPR:
1038 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1039 return;
1041 case VEC_INIT_EXPR:
1042 case INIT_EXPR:
1043 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_BIND);
1044 extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1045 return;
1047 case MODIFY_EXPR:
1048 case PREDECREMENT_EXPR:
1049 case PREINCREMENT_EXPR:
1050 case POSTDECREMENT_EXPR:
1051 case POSTINCREMENT_EXPR:
1052 /* These write their result. */
1053 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_WRITE);
1054 extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1055 return;
1057 case ADDR_EXPR:
1058 /* This might modify its argument, and the value needs to be
1059 passed by reference in any case to preserve identity and
1060 type if is a promoting type. In the case of a nested loop
1061 just notice that we touch the variable. It will already
1062 be addressable, and marking it modified will cause a spurious
1063 warning about writing the control variable. */
1064 if (wd->type != CILK_BLOCK_SPAWN)
1065 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1066 else
1067 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_WRITE);
1068 return;
1070 case ARRAY_REF:
1071 /* Treating ARRAY_REF and BIT_FIELD_REF identically may
1072 mark the array as written but the end result is correct
1073 because the array is passed by pointer anyway. */
1074 case BIT_FIELD_REF:
1075 /* Propagate the access type to the object part of which
1076 is being accessed here. As for ADDR_EXPR, don't do this
1077 in a nested loop, unless the access is to a fixed index. */
1078 if (wd->type != CILK_BLOCK_FOR || TREE_CONSTANT (TREE_OPERAND (t, 1)))
1079 extract_free_variables (TREE_OPERAND (t, 0), wd, how);
1080 else
1081 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_READ);
1082 extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1083 extract_free_variables (TREE_OPERAND (t, 2), wd, ADD_READ);
1084 return;
1086 case TREE_LIST:
1087 extract_free_variables (TREE_PURPOSE (t), wd, ADD_READ);
1088 extract_free_variables (TREE_VALUE (t), wd, ADD_READ);
1089 extract_free_variables (TREE_CHAIN (t), wd, ADD_READ);
1090 return;
1092 case TREE_VEC:
1094 int len = TREE_VEC_LENGTH (t);
1095 int i;
1096 for (i = 0; i < len; i++)
1097 extract_free_variables (TREE_VEC_ELT (t, i), wd, ADD_READ);
1098 return;
1101 case VECTOR_CST:
1103 unsigned ii = 0;
1104 for (ii = 0; ii < VECTOR_CST_NELTS (t); ii++)
1105 extract_free_variables (VECTOR_CST_ELT (t, ii), wd, ADD_READ);
1106 break;
1109 case COMPLEX_CST:
1110 extract_free_variables (TREE_REALPART (t), wd, ADD_READ);
1111 extract_free_variables (TREE_IMAGPART (t), wd, ADD_READ);
1112 return;
1114 case BIND_EXPR:
1116 tree decl;
1117 for (decl = BIND_EXPR_VARS (t); decl; decl = TREE_CHAIN (decl))
1119 add_variable (wd, decl, ADD_BIND);
1120 /* A self-referential initialization is no problem because
1121 we already entered the variable into the map as local. */
1122 extract_free_variables (DECL_INITIAL (decl), wd, ADD_READ);
1123 extract_free_variables (DECL_SIZE (decl), wd, ADD_READ);
1124 extract_free_variables (DECL_SIZE_UNIT (decl), wd, ADD_READ);
1126 extract_free_variables (BIND_EXPR_BODY (t), wd, ADD_READ);
1127 return;
1130 case STATEMENT_LIST:
1132 tree_stmt_iterator i;
1133 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
1134 extract_free_variables (*tsi_stmt_ptr (i), wd, ADD_READ);
1135 return;
1138 case TARGET_EXPR:
1140 extract_free_variables (TREE_OPERAND (t, 0), wd, ADD_BIND);
1141 extract_free_variables (TREE_OPERAND (t, 1), wd, ADD_READ);
1142 extract_free_variables (TREE_OPERAND (t, 2), wd, ADD_READ);
1143 if (TREE_OPERAND (t, 3) != TREE_OPERAND (t, 1))
1144 extract_free_variables (TREE_OPERAND (t, 3), wd, ADD_READ);
1145 return;
1148 case RETURN_EXPR:
1149 if (TREE_NO_WARNING (t))
1151 gcc_assert (errorcount);
1152 return;
1154 return;
1156 case DECL_EXPR:
1157 if (TREE_CODE (DECL_EXPR_DECL (t)) != TYPE_DECL)
1158 extract_free_variables (DECL_EXPR_DECL (t), wd, ADD_BIND);
1159 return;
1161 case INTEGER_TYPE:
1162 case ENUMERAL_TYPE:
1163 case BOOLEAN_TYPE:
1164 extract_free_variables (TYPE_MIN_VALUE (t), wd, ADD_READ);
1165 extract_free_variables (TYPE_MAX_VALUE (t), wd, ADD_READ);
1166 return;
1168 case POINTER_TYPE:
1169 extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1170 break;
1172 case ARRAY_TYPE:
1173 extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1174 extract_free_variables (TYPE_DOMAIN (t), wd, ADD_READ);
1175 return;
1177 case RECORD_TYPE:
1178 extract_free_variables (TYPE_FIELDS (t), wd, ADD_READ);
1179 return;
1181 case METHOD_TYPE:
1182 extract_free_variables (TYPE_ARG_TYPES (t), wd, ADD_READ);
1183 extract_free_variables (TYPE_METHOD_BASETYPE (t), wd, ADD_READ);
1184 return;
1186 case AGGR_INIT_EXPR:
1187 case CALL_EXPR:
1189 int len = 0;
1190 int ii = 0;
1191 if (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST)
1193 len = TREE_INT_CST_LOW (TREE_OPERAND (t, 0));
1195 for (ii = 0; ii < len; ii++)
1196 extract_free_variables (TREE_OPERAND (t, ii), wd, ADD_READ);
1197 extract_free_variables (TREE_TYPE (t), wd, ADD_READ);
1199 break;
1202 case CONSTRUCTOR:
1204 unsigned HOST_WIDE_INT idx = 0;
1205 constructor_elt *ce;
1206 for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (t), idx, &ce); idx++)
1207 extract_free_variables (ce->value, wd, ADD_READ);
1208 break;
1211 default:
1212 if (is_expr)
1214 int i, len;
1216 /* Walk over all the sub-trees of this operand. */
1217 len = TREE_CODE_LENGTH (code);
1219 /* Go through the subtrees. We need to do this in forward order so
1220 that the scope of a FOR_EXPR is handled properly. */
1221 for (i = 0; i < len; ++i)
1222 extract_free_variables (TREE_OPERAND (t, i), wd, ADD_READ);
1227 /* Add appropriate frames needed for a Cilk spawned function call, FNDECL.
1228 Returns the __cilkrts_stack_frame * variable. */
1230 tree
1231 insert_cilk_frame (tree fndecl)
1233 tree addr, body, enter, out, orig_body;
1234 location_t loc = EXPR_LOCATION (fndecl);
1236 if (!cfun || cfun->decl != fndecl)
1237 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1239 tree decl = cfun->cilk_frame_decl;
1240 if (!decl)
1242 tree *saved_tree = &DECL_SAVED_TREE (fndecl);
1243 decl = make_cilk_frame (fndecl);
1244 add_local_decl (cfun, decl);
1246 addr = build1 (ADDR_EXPR, cilk_frame_ptr_type_decl, decl);
1247 enter = build_call_expr (cilk_enter_fndecl, 1, addr);
1248 out = create_cilk_function_exit (cfun->cilk_frame_decl, false, true);
1250 /* The new body will be:
1251 __cilkrts_enter_frame_1 (&sf);
1252 try {
1253 orig_body;
1255 finally {
1256 __cilkrts_pop_frame (&sf);
1257 __cilkrts_leave_frame (&sf);
1258 } */
1260 body = alloc_stmt_list ();
1261 orig_body = *saved_tree;
1263 if (TREE_CODE (orig_body) == BIND_EXPR)
1264 orig_body = BIND_EXPR_BODY (orig_body);
1266 append_to_statement_list (enter, &body);
1267 append_to_statement_list (build_stmt (loc, TRY_FINALLY_EXPR, orig_body,
1268 out), &body);
1269 if (TREE_CODE (*saved_tree) == BIND_EXPR)
1270 BIND_EXPR_BODY (*saved_tree) = body;
1271 else
1272 *saved_tree = body;
1274 return decl;
1277 /* Wraps CALL, a CALL_EXPR, into a CILK_SPAWN_STMT tree and returns it. */
1279 tree
1280 build_cilk_spawn (location_t loc, tree call)
1282 if (!cilk_set_spawn_marker (loc, call))
1283 return error_mark_node;
1284 tree spawn_stmt = build1 (CILK_SPAWN_STMT, TREE_TYPE (call), call);
1285 TREE_SIDE_EFFECTS (spawn_stmt) = 1;
1286 return spawn_stmt;
1289 /* Returns a tree of type CILK_SYNC_STMT. */
1291 tree
1292 build_cilk_sync (void)
1294 tree sync = build0 (CILK_SYNC_STMT, void_type_node);
1295 TREE_SIDE_EFFECTS (sync) = 1;
1296 return sync;
1299 /* Helper for contains_cilk_spawn_stmt, callback for walk_tree. Return
1300 non-null tree if TP contains CILK_SPAWN_STMT. */
1302 static tree
1303 contains_cilk_spawn_stmt_walker (tree *tp, int *, void *)
1305 if (TREE_CODE (*tp) == CILK_SPAWN_STMT)
1306 return *tp;
1307 else
1308 return NULL_TREE;
1311 /* Returns true if EXPR or any of its subtrees contain CILK_SPAWN_STMT
1312 node. */
1314 bool
1315 contains_cilk_spawn_stmt (tree expr)
1317 return walk_tree (&expr, contains_cilk_spawn_stmt_walker, NULL, NULL)
1318 != NULL_TREE;