1 /* This file is part of the Intel(R) Cilk(TM) Plus support
2 This file contains the CilkPlus Intrinsics
3 Copyright (C) 2013-2015 Free Software Foundation, Inc.
4 Contributed by Balaji V. Iyer <balaji.v.iyer@intel.com>,
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)
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/>. */
25 #include "coretypes.h"
30 #include "fold-const.h"
31 #include "stringpool.h"
32 #include "langhooks.h"
33 #include "gimple-expr.h"
35 #include "tree-iterator.h"
36 #include "tree-inline.h"
37 #include "c-family/c-common.h"
40 #include "hard-reg-set.h"
44 #include "diagnostic.h"
47 enum add_variable_type
{
48 /* Reference to previously-defined variable. */
50 /* Definition of a new variable in inner-scope. */
52 /* Write to possibly previously-defined variable. */
56 enum cilk_block_type
{
57 /* Indicates a _Cilk_spawn block. 30 was an arbitary number picked for
59 CILK_BLOCK_SPAWN
= 30,
60 /* Indicates _Cilk_for statement block. */
66 /* Kind of function to be created. */
67 enum cilk_block_type type
;
68 /* Signature of helper function. */
70 /* Containing function. */
72 /* Disposition of all variables in the inner statement. */
73 hash_map
<tree
, tree
> *decl_map
;
74 /* True if this function needs a static chain. */
76 /* Arguments to be passed to wrapper function, currently a list. */
78 /* Argument types, a list. */
80 /* Incoming parameters. */
82 /* Outer BLOCK object. */
86 static void extract_free_variables (tree
, struct wrapper_data
*,
87 enum add_variable_type
);
88 static HOST_WIDE_INT cilk_wrapper_count
;
90 /* Marks the CALL_EXPR or FUNCTION_DECL, FCALL, as a spawned function call
91 and the current function as a spawner. Emit error if the function call
92 is outside a function or if a non function-call is spawned. */
95 cilk_set_spawn_marker (location_t loc
, tree fcall
)
97 if (!current_function_decl
)
99 error_at (loc
, "%<_Cilk_spawn%> may only be used inside a function");
102 else if (fcall
== error_mark_node
)
103 /* Error reporting here is not necessary here since if FCALL is an
104 error_mark_node, the function marking it as error would have reported
107 else if (TREE_CODE (fcall
) != CALL_EXPR
108 /* In C++, TARGET_EXPR is generated when we have an overloaded
110 && TREE_CODE (fcall
) != TARGET_EXPR
)
112 error_at (loc
, "only function calls can be spawned");
117 cfun
->calls_cilk_spawn
= true;
122 /* This function will output the exit conditions for a spawn call. */
125 create_cilk_function_exit (tree frame
, bool detaches
, bool needs_sync
)
127 tree epi
= alloc_stmt_list ();
130 append_to_statement_list (build_cilk_sync (), &epi
);
131 tree func_ptr
= build1 (ADDR_EXPR
, cilk_frame_ptr_type_decl
, frame
);
132 tree pop_frame
= build_call_expr (cilk_pop_fndecl
, 1, func_ptr
);
133 tree worker
= cilk_dot (frame
, CILK_TI_FRAME_WORKER
, 0);
134 tree current
= cilk_arrow (worker
, CILK_TI_WORKER_CUR
, 0);
135 tree parent
= cilk_dot (frame
, CILK_TI_FRAME_PARENT
, 0);
136 tree set_current
= build2 (MODIFY_EXPR
, void_type_node
, current
, parent
);
137 append_to_statement_list (set_current
, &epi
);
138 append_to_statement_list (pop_frame
, &epi
);
139 tree call
= build_call_expr (cilk_leave_fndecl
, 1, func_ptr
);
142 tree flags
= cilk_dot (frame
, CILK_TI_FRAME_FLAGS
, false);
143 tree flags_cmp_expr
= fold_build2 (NE_EXPR
, TREE_TYPE (flags
), flags
,
144 build_int_cst (TREE_TYPE (flags
),
145 CILK_FRAME_VERSION
));
146 call
= fold_build3 (COND_EXPR
, void_type_node
, flags_cmp_expr
,
147 call
, build_empty_stmt (EXPR_LOCATION (flags
)));
149 append_to_statement_list (call
, &epi
);
153 /* Trying to get the correct cfun for the FUNCTION_DECL indicated by OUTER. */
156 pop_cfun_to (tree outer
)
159 current_function_decl
= outer
;
160 gcc_assert (cfun
== DECL_STRUCT_FUNCTION (current_function_decl
));
161 gcc_assert (cfun
->decl
== current_function_decl
);
164 /* This function does whatever is necessary to make the compiler emit a newly
165 generated function, FNDECL. */
168 call_graph_add_fn (tree fndecl
)
170 const tree outer
= current_function_decl
;
171 struct function
*f
= DECL_STRUCT_FUNCTION (fndecl
);
172 gcc_assert (TREE_CODE (fndecl
) == FUNCTION_DECL
);
174 f
->is_cilk_function
= 1;
175 f
->curr_properties
= cfun
->curr_properties
;
176 gcc_assert (cfun
== DECL_STRUCT_FUNCTION (outer
));
177 gcc_assert (cfun
->decl
== outer
);
180 cgraph_node::create (fndecl
);
184 /* Return true if this is a tree which is allowed to contain a spawn as
186 A spawn call may be wrapped in a series of unary operations such
187 as conversions. These conversions need not be "useless"
188 to be disregarded because they are retained in the spawned
189 statement. They are bypassed only to look for a spawn
191 A comparison to constant is simple enough to allow, and
192 is used to convert to bool. */
195 cilk_ignorable_spawn_rhs_op (tree exp
)
197 enum tree_code code
= TREE_CODE (exp
);
198 switch (TREE_CODE_CLASS (code
))
201 return code
== ADDR_EXPR
;
203 /* We need the spawn as operand 0 for now. That's where it
204 appears in the only case we really care about, conversion
206 return (TREE_CODE (TREE_OPERAND (exp
, 1)) == INTEGER_CST
);
215 /* Helper function for walk_tree. If *TP is a CILK_SPAWN_STMT, then unwrap
216 this "wrapper." The function returns NULL_TREE regardless. */
219 unwrap_cilk_spawn_stmt (tree
*tp
, int *walk_subtrees
, void *)
221 if (TREE_CODE (*tp
) == CILK_SPAWN_STMT
)
223 *tp
= CILK_SPAWN_FN (*tp
);
229 /* Returns true when EXP is a CALL_EXPR with _Cilk_spawn in front. Unwraps
230 CILK_SPAWN_STMT wrapper from the CALL_EXPR in *EXP0 statement. */
233 recognize_spawn (tree exp
, tree
*exp0
)
235 bool spawn_found
= false;
236 if (TREE_CODE (exp
) == CILK_SPAWN_STMT
)
238 /* Remove the CALL_EXPR from CILK_SPAWN_STMT wrapper. */
239 exp
= CILK_SPAWN_FN (exp
);
240 walk_tree (exp0
, unwrap_cilk_spawn_stmt
, NULL
, NULL
);
243 /* _Cilk_spawn can't be wrapped in expression such as PLUS_EXPR. */
244 else if (contains_cilk_spawn_stmt (exp
))
245 error_at (EXPR_LOCATION (exp
), "invalid use of %<_Cilk_spawn%>");
249 /* Returns true if *EXP0 is a recognized form of spawn. Recognized forms are,
250 after conversion to void, a call expression at outer level or an assignment
251 at outer level with the right hand side being a spawned call.
252 In addition to this, it also unwraps the CILK_SPAWN_STMT cover from the
253 CALL_EXPR that is being spawned.
254 Note that `=' in C++ may turn into a CALL_EXPR rather than a MODIFY_EXPR. */
257 cilk_detect_spawn_and_unwrap (tree
*exp0
)
261 if (!TREE_SIDE_EFFECTS (exp
))
264 /* Strip off any conversion to void. It does not affect whether spawn
265 is supported here. */
266 if (TREE_CODE (exp
) == CONVERT_EXPR
&& VOID_TYPE_P (TREE_TYPE (exp
)))
267 exp
= TREE_OPERAND (exp
, 0);
269 if (TREE_CODE (exp
) == MODIFY_EXPR
|| TREE_CODE (exp
) == INIT_EXPR
)
270 exp
= TREE_OPERAND (exp
, 1);
272 while (cilk_ignorable_spawn_rhs_op (exp
))
273 exp
= TREE_OPERAND (exp
, 0);
275 if (TREE_CODE (exp
) == TARGET_EXPR
)
276 if (TARGET_EXPR_INITIAL (exp
)
277 && TREE_CODE (TARGET_EXPR_INITIAL (exp
)) != AGGR_INIT_EXPR
)
278 exp
= TARGET_EXPR_INITIAL (exp
);
280 /* Happens with C++ TARGET_EXPR. */
281 if (exp
== NULL_TREE
)
284 while (TREE_CODE (exp
) == CLEANUP_POINT_EXPR
|| TREE_CODE (exp
) == EXPR_STMT
)
285 exp
= TREE_OPERAND (exp
, 0);
287 /* Now we should have a CALL_EXPR with a CILK_SPAWN_STMT wrapper around
288 it, or return false. */
289 if (recognize_spawn (exp
, exp0
))
294 /* This function will build and return a FUNCTION_DECL using information
298 create_cilk_helper_decl (struct wrapper_data
*wd
)
301 if (wd
->type
== CILK_BLOCK_FOR
)
302 sprintf (name
, "_cilk_for_" HOST_WIDE_INT_PRINT_DEC
, cilk_wrapper_count
++);
303 else if (wd
->type
== CILK_BLOCK_SPAWN
)
304 sprintf (name
, "_cilk_spn_" HOST_WIDE_INT_PRINT_DEC
, cilk_wrapper_count
++);
308 clean_symbol_name (name
);
309 tree fndecl
= build_decl (UNKNOWN_LOCATION
, FUNCTION_DECL
,
310 get_identifier (name
), wd
->fntype
);
312 TREE_PUBLIC (fndecl
) = 0;
313 TREE_STATIC (fndecl
) = 1;
314 TREE_USED (fndecl
) = 1;
315 DECL_ARTIFICIAL (fndecl
) = 0;
316 DECL_IGNORED_P (fndecl
) = 0;
317 DECL_EXTERNAL (fndecl
) = 0;
319 DECL_CONTEXT (fndecl
) = wd
->context
;
320 tree block
= make_node (BLOCK
);
321 DECL_INITIAL (fndecl
) = block
;
322 TREE_USED (block
) = 1;
323 BLOCK_SUPERCONTEXT (block
) = fndecl
;
324 gcc_assert (!DECL_SAVED_TREE (fndecl
));
326 /* Inlining would defeat the purpose of this wrapper.
327 Either it secretly switches stack frames or it allocates
328 a stable stack frame to hold function arguments even if
329 the parent stack frame is stolen. */
330 DECL_UNINLINABLE (fndecl
) = 1;
332 tree result_decl
= build_decl (UNKNOWN_LOCATION
, RESULT_DECL
, NULL_TREE
,
334 DECL_ARTIFICIAL (result_decl
) = 0;
335 DECL_IGNORED_P (result_decl
) = 1;
336 DECL_CONTEXT (result_decl
) = fndecl
;
337 DECL_RESULT (fndecl
) = result_decl
;
348 /* A function used by traversal to fill vector of decls for further work. */
351 fill_decls_vec (tree
const &key0
, tree
*val0
, auto_vec
<struct cilk_decls
> *v
)
354 struct cilk_decls dp
;
365 /* Function that actually creates necessary parm lists. */
368 create_parm_list (struct wrapper_data
*wd
, tree
*val0
, tree arg
)
373 if (val
== error_mark_node
|| val
== arg
)
376 if (TREE_CODE (val
) == PAREN_EXPR
)
378 /* We should not reach here with a register receiver.
379 We may see a register variable modified in the
380 argument list. Because register variables are
381 worker-local we don't need to work hard to support
382 them in code that spawns. */
383 if (VAR_P (arg
) && DECL_HARD_REGISTER (arg
))
385 error_at (EXPR_LOCATION (arg
),
386 "explicit register variable %qD may not be modified in "
388 arg
= null_pointer_node
;
391 arg
= build1 (ADDR_EXPR
, build_pointer_type (TREE_TYPE (arg
)), arg
);
393 val
= TREE_OPERAND (val
, 0);
395 gcc_assert (INDIRECT_REF_P (val
));
396 parm
= TREE_OPERAND (val
, 0);
401 TREE_CHAIN (parm
) = wd
->parms
;
403 wd
->argtypes
= tree_cons (NULL_TREE
, TREE_TYPE (parm
), wd
->argtypes
);
404 wd
->arglist
= tree_cons (NULL_TREE
, arg
, wd
->arglist
);
407 /* Sorting decls in a vector. */
410 compare_decls (const void *a
, const void *b
)
412 const struct cilk_decls
*t1
= (const struct cilk_decls
*) a
;
413 const struct cilk_decls
*t2
= (const struct cilk_decls
*) b
;
415 if (DECL_UID (t1
->key
) > DECL_UID (t2
->key
))
417 else if (DECL_UID (t1
->key
) < DECL_UID (t2
->key
))
423 /* This function is used to build a wrapper of a certain type. */
426 build_wrapper_type (struct wrapper_data
*wd
)
429 struct cilk_decls
* c
;
430 auto_vec
<struct cilk_decls
> vd
;
431 wd
->arglist
= NULL_TREE
;
432 wd
->parms
= NULL_TREE
;
433 wd
->argtypes
= void_list_node
;
435 gcc_assert (wd
->type
!= CILK_BLOCK_FOR
);
436 wd
->decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
437 vd
.qsort (compare_decls
);
439 FOR_EACH_VEC_ELT (vd
, j
, c
)
440 create_parm_list (wd
, c
->val
, c
->key
);
442 /* Now build a function.
443 Its return type is void (all side effects are via explicit parameters).
444 Its parameters are WRAPPER_PARMS with type WRAPPER_TYPES.
445 Actual arguments in the caller are WRAPPER_ARGS. */
446 wd
->fntype
= build_function_type (void_type_node
, wd
->argtypes
);
449 /* This function checks all the CALL_EXPRs in *TP found by cilk_outline. */
452 check_outlined_calls (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
455 bool *throws
= (bool *) data
;
459 if (TREE_CODE (t
) != CALL_EXPR
)
461 flags
= call_expr_flags (t
);
463 if (!(flags
& ECF_NOTHROW
) && flag_exceptions
)
465 if (flags
& ECF_RETURNS_TWICE
)
466 error_at (EXPR_LOCATION (t
),
467 "cannot spawn call to function that returns twice");
471 /* Each DECL in the source code (spawned statement) is passed to this function
472 once. Each instance of the DECL is replaced with the result of this
475 The parameters of the wrapper should have been entered into the map already.
476 This function only deals with variables with scope limited to the
477 spawned expression. */
480 copy_decl_for_cilk (tree decl
, copy_body_data
*id
)
482 switch (TREE_CODE (decl
))
485 return copy_decl_no_change (decl
, id
);
488 error_at (EXPR_LOCATION (decl
), "invalid use of label %q+D in "
491 return error_mark_node
;
495 /* RESULT_DECL and PARM_DECL has already been entered into the map. */
498 return error_mark_node
;
502 /* Alter a tree STMT from OUTER_FN to form the body of INNER_FN. */
505 cilk_outline (tree inner_fn
, tree
*stmt_p
, void *w
)
507 struct wrapper_data
*wd
= (struct wrapper_data
*) w
;
508 const tree outer_fn
= wd
->context
;
509 const bool nested
= (wd
->type
== CILK_BLOCK_FOR
);
512 auto_vec
<struct cilk_decls
> vd
;
514 struct cilk_decls
* c
;
516 DECL_STATIC_CHAIN (outer_fn
) = 1;
518 memset (&id
, 0, sizeof (id
));
519 /* Copy from the function containing the spawn... */
520 id
.src_fn
= outer_fn
;
522 /* ...to the wrapper. */
523 id
.dst_fn
= inner_fn
;
524 id
.src_cfun
= DECL_STRUCT_FUNCTION (outer_fn
);
526 /* There shall be no RETURN in spawn helper. */
528 id
.decl_map
= wd
->decl_map
;
529 id
.copy_decl
= nested
? copy_decl_no_change
: copy_decl_for_cilk
;
530 id
.block
= DECL_INITIAL (inner_fn
);
531 id
.transform_lang_insert_block
= NULL
;
533 id
.transform_new_cfg
= true;
534 id
.transform_call_graph_edges
= CB_CGE_MOVE
;
535 id
.remap_var_for_cilk
= true;
536 id
.regimplify
= true; /* unused? */
538 insert_decl_map (&id
, wd
->block
, DECL_INITIAL (inner_fn
));
540 wd
->decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
541 vd
.qsort (compare_decls
);
542 /* We don't want the private variables any more. */
543 FOR_EACH_VEC_ELT (vd
, j
, c
)
544 if (*(c
->val
) == error_mark_node
)
545 *(c
->val
) = nested
? copy_decl_no_change (c
->key
, &id
)
546 : copy_decl_for_cilk (c
->key
, &id
);
548 walk_tree (stmt_p
, copy_tree_body_r
, (void *) &id
, NULL
);
550 /* See if this function can throw or calls something that should
551 not be spawned. The exception part is only necessary if
552 flag_exceptions && !flag_non_call_exceptions. */
554 (void) walk_tree_without_duplicates (stmt_p
, check_outlined_calls
, &throws
);
557 /* Generate the body of a wrapper function that assigns the
558 result of the expression RHS into RECEIVER. RECEIVER must
559 be NULL if this is not a spawn -- the wrapper will return
560 a value. If this is a spawn, the wrapper will return void. */
563 create_cilk_wrapper_body (tree stmt
, struct wrapper_data
*wd
)
565 const tree outer
= current_function_decl
;
569 /* Build the type of the wrapper and its argument list from the
570 variables that it requires. */
571 build_wrapper_type (wd
);
573 /* Emit a function that takes WRAPPER_PARMS incoming and applies ARGS
574 (modified) to the wrapped function. Return the wrapper and modified ARGS
575 to the caller to generate a function call. */
576 fndecl
= create_cilk_helper_decl (wd
);
577 push_struct_function (fndecl
);
578 if (wd
->nested
&& (wd
->type
== CILK_BLOCK_FOR
))
580 gcc_assert (TREE_VALUE (wd
->arglist
) == NULL_TREE
);
581 TREE_VALUE (wd
->arglist
) = build2 (FDESC_EXPR
, ptr_type_node
,
582 fndecl
, integer_one_node
);
584 DECL_ARGUMENTS (fndecl
) = wd
->parms
;
586 for (p
= wd
->parms
; p
; p
= TREE_CHAIN (p
))
587 DECL_CONTEXT (p
) = fndecl
;
589 gcc_assert (!DECL_SAVED_TREE (fndecl
));
590 cilk_install_body_with_frame_cleanup (fndecl
, stmt
, (void *) wd
);
591 gcc_assert (DECL_SAVED_TREE (fndecl
));
595 /* Recognize the new function. */
596 call_graph_add_fn (fndecl
);
600 /* Initializes the wrapper data structure. */
603 init_wd (struct wrapper_data
*wd
, enum cilk_block_type type
)
606 wd
->fntype
= NULL_TREE
;
607 wd
->context
= current_function_decl
;
608 wd
->decl_map
= new hash_map
<tree
, tree
>;
609 /* _Cilk_for bodies are always nested. Others start off as
611 wd
->nested
= (type
== CILK_BLOCK_FOR
);
612 wd
->arglist
= NULL_TREE
;
613 wd
->argtypes
= NULL_TREE
;
614 wd
->block
= NULL_TREE
;
617 /* Clears the wrapper data structure. */
620 free_wd (struct wrapper_data
*wd
)
624 wd
->arglist
= NULL_TREE
;
625 wd
->argtypes
= NULL_TREE
;
626 wd
->parms
= NULL_TREE
;
630 /* Given a variable in an expression to be extracted into
631 a helper function, declare the helper function parameter
634 On entry the value of the (key, value) pair may be
636 (*, error_mark_node) -- Variable is private to helper function,
639 (var, var) -- Reference to outer scope (function or global scope).
641 (var, integer 0) -- Capture by value, save newly-declared PARM_DECL
642 for value in value slot.
644 (var, integer 1) -- Capture by reference, declare pointer to type
645 as new PARM_DECL and store (spawn_stmt (indirect_ref (parm)).
647 (var, ???) -- Pure output argument, handled similarly to above.
651 declare_one_free_variable (tree var0
, tree
*map0
)
653 const_tree var
= var0
;
655 tree var_type
= TREE_TYPE (var
), arg_type
;
659 gcc_assert (DECL_P (var
));
661 /* Ignore truly local variables. */
662 if (map
== error_mark_node
)
664 /* Ignore references to the parent function. */
668 gcc_assert (TREE_CODE (map
) == INTEGER_CST
);
670 /* A value is passed by reference if:
672 1. It is addressable, so that a copy may not be made.
673 2. It is modified in the spawned statement.
674 In the future this function may want to arrange
675 a warning if the spawned statement is a loop body
676 because an output argument would indicate a race.
677 Note: Earlier passes must have marked the variable addressable.
678 3. It is expensive to copy. */
680 (TREE_ADDRESSABLE (var_type
)
681 /* Arrays must be passed by reference. This is required for C
682 semantics -- arrays are not first class objects. Other
683 aggregate types can and should be passed by reference if
684 they are not passed to the spawned function. We aren't yet
685 distinguishing safe uses in argument calculation from unsafe
686 uses as outgoing function arguments, so we make a copy to
687 stabilize the value. */
688 || TREE_CODE (var_type
) == ARRAY_TYPE
689 || (tree
) map
== integer_one_node
);
692 var_type
= build_qualified_type (build_pointer_type (var_type
),
694 gcc_assert (!TREE_ADDRESSABLE (var_type
));
696 /* Maybe promote to int. */
697 if (INTEGRAL_TYPE_P (var_type
) && COMPLETE_TYPE_P (var_type
)
698 && tree_int_cst_lt (TYPE_SIZE (var_type
), TYPE_SIZE (integer_type_node
)))
699 arg_type
= integer_type_node
;
703 parm
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
, NULL_TREE
, var_type
);
704 DECL_ARG_TYPE (parm
) = arg_type
;
705 DECL_ARTIFICIAL (parm
) = 0;
706 TREE_READONLY (parm
) = 1;
710 parm
= build1 (INDIRECT_REF
, TREE_TYPE (var_type
), parm
);
711 parm
= build1 (PAREN_EXPR
, void_type_node
, parm
);
717 /* Returns a wrapper function for a _Cilk_spawn. */
720 create_cilk_wrapper (tree exp
, tree
*args_out
)
722 struct wrapper_data wd
;
725 struct cilk_decls
* c
;
726 auto_vec
<struct cilk_decls
> vd
;
728 init_wd (&wd
, CILK_BLOCK_SPAWN
);
730 if (TREE_CODE (exp
) == CONVERT_EXPR
)
731 exp
= TREE_OPERAND (exp
, 0);
733 /* Special handling for top level INIT_EXPR. Usually INIT_EXPR means the
734 variable is defined in the spawned expression and can be private to the
735 spawn helper. A top level INIT_EXPR defines a variable to be initialized
736 by spawn and the variable must remain in the outer function. */
737 if (TREE_CODE (exp
) == INIT_EXPR
)
739 extract_free_variables (TREE_OPERAND (exp
, 0), &wd
, ADD_WRITE
);
740 extract_free_variables (TREE_OPERAND (exp
, 1), &wd
, ADD_READ
);
741 /* TREE_TYPE should be void. Be defensive. */
742 if (TREE_TYPE (exp
) != void_type_node
)
743 extract_free_variables (TREE_TYPE (exp
), &wd
, ADD_READ
);
746 extract_free_variables (exp
, &wd
, ADD_READ
);
747 wd
.decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
748 vd
.qsort (compare_decls
);
749 FOR_EACH_VEC_ELT (vd
, j
, c
)
750 declare_one_free_variable (c
->key
, c
->val
);
752 wd
.block
= TREE_BLOCK (exp
);
754 wd
.block
= DECL_INITIAL (current_function_decl
);
756 /* Now fvars maps the old variable to incoming variable. Update
757 the expression and arguments to refer to the new names. */
758 fndecl
= create_cilk_wrapper_body (exp
, &wd
);
759 *args_out
= wd
.arglist
;
766 /* Transform *SPAWN_P, a spawned CALL_EXPR, to gimple. *SPAWN_P can be a
767 CALL_EXPR, INIT_EXPR or MODIFY_EXPR. Returns GS_OK if everything is fine,
768 and GS_UNHANDLED, otherwise. */
771 gimplify_cilk_spawn (tree
*spawn_p
)
773 tree expr
= *spawn_p
;
774 tree function
, call1
, call2
, new_args
;
775 tree ii_args
= NULL_TREE
;
776 int total_args
= 0, ii
= 0;
778 tree setjmp_cond_expr
= NULL_TREE
;
779 tree setjmp_expr
, spawn_expr
, setjmp_value
= NULL_TREE
;
781 cfun
->calls_cilk_spawn
= 1;
782 cfun
->is_cilk_function
= 1;
784 /* Remove CLEANUP_POINT_EXPR and EXPR_STMT from *spawn_p. */
785 while (TREE_CODE (expr
) == CLEANUP_POINT_EXPR
786 || TREE_CODE (expr
) == EXPR_STMT
)
787 expr
= TREE_OPERAND (expr
, 0);
790 function
= create_cilk_wrapper (expr
, &new_args
);
792 /* This should give the number of parameters. */
793 total_args
= list_length (new_args
);
795 arg_array
= XNEWVEC (tree
, total_args
);
800 for (ii
= 0; ii
< total_args
; ii
++)
802 arg_array
[ii
] = TREE_VALUE (ii_args
);
803 ii_args
= TREE_CHAIN (ii_args
);
806 TREE_USED (function
) = 1;
807 rest_of_decl_compilation (function
, 0, 0);
809 call1
= cilk_call_setjmp (cfun
->cilk_frame_decl
);
811 if (arg_array
== NULL
|| *arg_array
== NULL_TREE
)
812 call2
= build_call_expr (function
, 0);
814 call2
= build_call_expr_loc_array (EXPR_LOCATION (*spawn_p
), function
,
815 total_args
, arg_array
);
816 *spawn_p
= alloc_stmt_list ();
817 tree f_ptr_type
= build_pointer_type (TREE_TYPE (cfun
->cilk_frame_decl
));
818 tree frame_ptr
= build1 (ADDR_EXPR
, f_ptr_type
, cfun
->cilk_frame_decl
);
819 tree save_fp
= build_call_expr (cilk_save_fp_fndecl
, 1, frame_ptr
);
820 append_to_statement_list (save_fp
, spawn_p
);
821 setjmp_value
= create_tmp_var (TREE_TYPE (call1
));
822 setjmp_expr
= fold_build2 (MODIFY_EXPR
, void_type_node
, setjmp_value
, call1
);
824 append_to_statement_list_force (setjmp_expr
, spawn_p
);
826 setjmp_cond_expr
= fold_build2 (EQ_EXPR
, TREE_TYPE (call1
), setjmp_value
,
827 build_int_cst (TREE_TYPE (call1
), 0));
828 spawn_expr
= fold_build3 (COND_EXPR
, void_type_node
, setjmp_cond_expr
,
829 call2
, build_empty_stmt (EXPR_LOCATION (call1
)));
830 append_to_statement_list (spawn_expr
, spawn_p
);
835 /* Make the frames necessary for a spawn call. */
838 make_cilk_frame (tree fn
)
840 struct function
*f
= DECL_STRUCT_FUNCTION (fn
);
843 if (f
->cilk_frame_decl
)
844 return f
->cilk_frame_decl
;
846 decl
= build_decl (EXPR_LOCATION (fn
), VAR_DECL
, NULL_TREE
,
847 cilk_frame_type_decl
);
848 DECL_CONTEXT (decl
) = fn
;
849 DECL_SEEN_IN_BIND_EXPR_P (decl
) = 1;
850 f
->cilk_frame_decl
= decl
;
854 /* Returns a STATEMENT_LIST with all the pedigree operations required for
855 install body with frame cleanup functions. FRAME_PTR is the pointer to
856 __cilkrts_stack_frame created by make_cilk_frame. */
859 cilk_install_body_pedigree_operations (tree frame_ptr
)
861 tree body_list
= alloc_stmt_list ();
862 tree enter_frame
= build_call_expr (cilk_enter_fast_fndecl
, 1, frame_ptr
);
863 append_to_statement_list (enter_frame
, &body_list
);
865 tree parent
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_PARENT
, 0);
866 tree worker
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_WORKER
, 0);
868 tree pedigree
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_PEDIGREE
, 0);
869 tree pedigree_rank
= cilk_dot (pedigree
, CILK_TI_PEDIGREE_RANK
, 0);
870 tree parent_pedigree
= cilk_dot (pedigree
, CILK_TI_PEDIGREE_PARENT
, 0);
871 tree pedigree_parent
= cilk_arrow (parent
, CILK_TI_FRAME_PEDIGREE
, 0);
872 tree pedigree_parent_rank
= cilk_dot (pedigree_parent
,
873 CILK_TI_PEDIGREE_RANK
, 0);
874 tree pedigree_parent_parent
= cilk_dot (pedigree_parent
,
875 CILK_TI_PEDIGREE_PARENT
, 0);
876 tree worker_pedigree
= cilk_arrow (worker
, CILK_TI_WORKER_PEDIGREE
, 1);
877 tree w_pedigree_rank
= cilk_dot (worker_pedigree
, CILK_TI_PEDIGREE_RANK
, 0);
878 tree w_pedigree_parent
= cilk_dot (worker_pedigree
,
879 CILK_TI_PEDIGREE_PARENT
, 0);
881 /* sf.pedigree.rank = worker->pedigree.rank. */
882 tree exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_rank
,
884 append_to_statement_list (exp1
, &body_list
);
886 /* sf.pedigree.parent = worker->pedigree.parent. */
887 exp1
= build2 (MODIFY_EXPR
, void_type_node
, parent_pedigree
,
889 append_to_statement_list (exp1
, &body_list
);
891 /* sf.call_parent->pedigree.rank = worker->pedigree.rank. */
892 exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_parent_rank
,
894 append_to_statement_list (exp1
, &body_list
);
896 /* sf.call_parent->pedigree.parent = worker->pedigree.parent. */
897 exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_parent_parent
,
899 append_to_statement_list (exp1
, &body_list
);
901 /* sf->worker.pedigree.rank = 0. */
902 exp1
= build2 (MODIFY_EXPR
, void_type_node
, w_pedigree_rank
,
903 build_zero_cst (uint64_type_node
));
904 append_to_statement_list (exp1
, &body_list
);
906 /* sf->pedigree.parent = &sf->pedigree. */
907 exp1
= build2 (MODIFY_EXPR
, void_type_node
, w_pedigree_parent
,
909 build_pointer_type (cilk_pedigree_type_decl
),
911 append_to_statement_list (exp1
, &body_list
);
915 /* Add a new variable, VAR to a variable list in WD->DECL_MAP. HOW indicates
916 whether the variable is previously defined, currently defined, or a variable
917 that is being written to. */
920 add_variable (struct wrapper_data
*wd
, tree var
, enum add_variable_type how
)
922 tree
*valp
= wd
->decl_map
->get (var
);
925 tree val
= (tree
) *valp
;
926 /* If the variable is local, do nothing. */
927 if (val
== error_mark_node
)
929 /* If the variable was entered with itself as value,
930 meaning it belongs to an outer scope, do not alter
934 /* A statement expression may cause a variable to be
935 bound twice, once in BIND_EXPR and again in a
936 DECL_EXPR. That case caused a return in the
937 test above. Any other duplicate definition is
939 gcc_assert (how
!= ADD_BIND
);
940 if (how
!= ADD_WRITE
)
942 /* This variable might have been entered as read but is now written. */
949 tree val
= NULL_TREE
;
951 /* Nested function rewriting silently discards hard register
952 assignments for function scope variables, and they wouldn't
953 work anyway. Warn here. This misses one case: if the
954 register variable is used as the loop bound or increment it
955 has already been added to the map. */
956 if ((how
!= ADD_BIND
) && VAR_P (var
)
957 && !DECL_EXTERNAL (var
) && DECL_HARD_REGISTER (var
))
958 warning (0, "register assignment ignored for %qD used in Cilk block",
963 /* ADD_BIND means always make a fresh new variable. */
965 val
= error_mark_node
;
968 1. For cilk_for, refer to the outer scope definition as-is
969 2. For a spawned block, take a scalar in an rgument
970 and otherwise refer to the outer scope definition as-is.
971 3. For a spawned call, take a scalar in an argument. */
978 case CILK_BLOCK_SPAWN
:
979 if (TREE_ADDRESSABLE (var
))
985 val
= integer_zero_node
;
996 case CILK_BLOCK_SPAWN
:
997 if (TREE_ADDRESSABLE (var
))
998 val
= integer_one_node
;
1007 wd
->decl_map
->put (var
, val
);
1011 /* Find the variables referenced in an expression T. This does not avoid
1012 duplicates because a variable may be read in one context and written in
1013 another. HOW describes the context in which the reference is seen. If
1014 NESTED is true a nested function is being generated and variables in the
1015 original context should not be remapped. */
1018 extract_free_variables (tree t
, struct wrapper_data
*wd
,
1019 enum add_variable_type how
)
1024 enum tree_code code
= TREE_CODE (t
);
1025 bool is_expr
= IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
));
1028 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1033 case IDENTIFIER_NODE
:
1040 case PLACEHOLDER_EXPR
:
1044 /* These do not contain variable references. */
1048 /* Currently we don't see SSA_NAME. */
1049 extract_free_variables (SSA_NAME_VAR (t
), wd
, how
);
1053 /* This might be a reference to a label outside the Cilk block,
1054 which is an error, or a reference to a label in the Cilk block
1055 that we haven't seen yet. We can't tell. Ignore it. An
1056 invalid use will cause an error later in copy_decl_for_cilk. */
1060 if (wd
->type
!= CILK_BLOCK_SPAWN
)
1061 TREE_ADDRESSABLE (t
) = 1;
1064 if (!is_global_var (t
))
1065 add_variable (wd
, t
, how
);
1068 case NON_LVALUE_EXPR
:
1071 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1076 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_BIND
);
1077 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1081 case PREDECREMENT_EXPR
:
1082 case PREINCREMENT_EXPR
:
1083 case POSTDECREMENT_EXPR
:
1084 case POSTINCREMENT_EXPR
:
1085 /* These write their result. */
1086 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_WRITE
);
1087 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1091 /* This might modify its argument, and the value needs to be
1092 passed by reference in any case to preserve identity and
1093 type if is a promoting type. In the case of a nested loop
1094 just notice that we touch the variable. It will already
1095 be addressable, and marking it modified will cause a spurious
1096 warning about writing the control variable. */
1097 if (wd
->type
!= CILK_BLOCK_SPAWN
)
1098 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1100 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_WRITE
);
1104 /* Treating ARRAY_REF and BIT_FIELD_REF identically may
1105 mark the array as written but the end result is correct
1106 because the array is passed by pointer anyway. */
1108 /* Propagate the access type to the object part of which
1109 is being accessed here. As for ADDR_EXPR, don't do this
1110 in a nested loop, unless the access is to a fixed index. */
1111 if (wd
->type
!= CILK_BLOCK_FOR
|| TREE_CONSTANT (TREE_OPERAND (t
, 1)))
1112 extract_free_variables (TREE_OPERAND (t
, 0), wd
, how
);
1114 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1115 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1116 extract_free_variables (TREE_OPERAND (t
, 2), wd
, ADD_READ
);
1120 extract_free_variables (TREE_PURPOSE (t
), wd
, ADD_READ
);
1121 extract_free_variables (TREE_VALUE (t
), wd
, ADD_READ
);
1122 extract_free_variables (TREE_CHAIN (t
), wd
, ADD_READ
);
1127 int len
= TREE_VEC_LENGTH (t
);
1129 for (i
= 0; i
< len
; i
++)
1130 extract_free_variables (TREE_VEC_ELT (t
, i
), wd
, ADD_READ
);
1137 for (ii
= 0; ii
< VECTOR_CST_NELTS (t
); ii
++)
1138 extract_free_variables (VECTOR_CST_ELT (t
, ii
), wd
, ADD_READ
);
1143 extract_free_variables (TREE_REALPART (t
), wd
, ADD_READ
);
1144 extract_free_variables (TREE_IMAGPART (t
), wd
, ADD_READ
);
1150 for (decl
= BIND_EXPR_VARS (t
); decl
; decl
= TREE_CHAIN (decl
))
1152 add_variable (wd
, decl
, ADD_BIND
);
1153 /* A self-referential initialization is no problem because
1154 we already entered the variable into the map as local. */
1155 extract_free_variables (DECL_INITIAL (decl
), wd
, ADD_READ
);
1156 extract_free_variables (DECL_SIZE (decl
), wd
, ADD_READ
);
1157 extract_free_variables (DECL_SIZE_UNIT (decl
), wd
, ADD_READ
);
1159 extract_free_variables (BIND_EXPR_BODY (t
), wd
, ADD_READ
);
1163 case STATEMENT_LIST
:
1165 tree_stmt_iterator i
;
1166 for (i
= tsi_start (t
); !tsi_end_p (i
); tsi_next (&i
))
1167 extract_free_variables (*tsi_stmt_ptr (i
), wd
, ADD_READ
);
1173 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_BIND
);
1174 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1175 extract_free_variables (TREE_OPERAND (t
, 2), wd
, ADD_READ
);
1176 if (TREE_OPERAND (t
, 3) != TREE_OPERAND (t
, 1))
1177 extract_free_variables (TREE_OPERAND (t
, 3), wd
, ADD_READ
);
1182 if (TREE_NO_WARNING (t
))
1184 gcc_assert (errorcount
);
1190 if (TREE_CODE (DECL_EXPR_DECL (t
)) != TYPE_DECL
)
1191 extract_free_variables (DECL_EXPR_DECL (t
), wd
, ADD_BIND
);
1197 extract_free_variables (TYPE_MIN_VALUE (t
), wd
, ADD_READ
);
1198 extract_free_variables (TYPE_MAX_VALUE (t
), wd
, ADD_READ
);
1202 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1206 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1207 extract_free_variables (TYPE_DOMAIN (t
), wd
, ADD_READ
);
1211 extract_free_variables (TYPE_FIELDS (t
), wd
, ADD_READ
);
1215 extract_free_variables (TYPE_ARG_TYPES (t
), wd
, ADD_READ
);
1216 extract_free_variables (TYPE_METHOD_BASETYPE (t
), wd
, ADD_READ
);
1219 case AGGR_INIT_EXPR
:
1224 if (TREE_CODE (TREE_OPERAND (t
, 0)) == INTEGER_CST
)
1226 len
= TREE_INT_CST_LOW (TREE_OPERAND (t
, 0));
1228 for (ii
= 0; ii
< len
; ii
++)
1229 extract_free_variables (TREE_OPERAND (t
, ii
), wd
, ADD_READ
);
1230 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1237 unsigned HOST_WIDE_INT idx
= 0;
1238 constructor_elt
*ce
;
1239 for (idx
= 0; vec_safe_iterate (CONSTRUCTOR_ELTS (t
), idx
, &ce
); idx
++)
1240 extract_free_variables (ce
->value
, wd
, ADD_READ
);
1249 /* Walk over all the sub-trees of this operand. */
1250 len
= TREE_CODE_LENGTH (code
);
1252 /* Go through the subtrees. We need to do this in forward order so
1253 that the scope of a FOR_EXPR is handled properly. */
1254 for (i
= 0; i
< len
; ++i
)
1255 extract_free_variables (TREE_OPERAND (t
, i
), wd
, ADD_READ
);
1260 /* Add appropriate frames needed for a Cilk spawned function call, FNDECL.
1261 Returns the __cilkrts_stack_frame * variable. */
1264 insert_cilk_frame (tree fndecl
)
1266 tree addr
, body
, enter
, out
, orig_body
;
1267 location_t loc
= EXPR_LOCATION (fndecl
);
1269 if (!cfun
|| cfun
->decl
!= fndecl
)
1270 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1272 tree decl
= cfun
->cilk_frame_decl
;
1275 tree
*saved_tree
= &DECL_SAVED_TREE (fndecl
);
1276 decl
= make_cilk_frame (fndecl
);
1277 add_local_decl (cfun
, decl
);
1279 addr
= build1 (ADDR_EXPR
, cilk_frame_ptr_type_decl
, decl
);
1280 enter
= build_call_expr (cilk_enter_fndecl
, 1, addr
);
1281 out
= create_cilk_function_exit (cfun
->cilk_frame_decl
, false, true);
1283 /* The new body will be:
1284 __cilkrts_enter_frame_1 (&sf);
1289 __cilkrts_pop_frame (&sf);
1290 __cilkrts_leave_frame (&sf);
1293 body
= alloc_stmt_list ();
1294 orig_body
= *saved_tree
;
1296 if (TREE_CODE (orig_body
) == BIND_EXPR
)
1297 orig_body
= BIND_EXPR_BODY (orig_body
);
1299 append_to_statement_list (enter
, &body
);
1300 append_to_statement_list (build_stmt (loc
, TRY_FINALLY_EXPR
, orig_body
,
1302 if (TREE_CODE (*saved_tree
) == BIND_EXPR
)
1303 BIND_EXPR_BODY (*saved_tree
) = body
;
1310 /* Wraps CALL, a CALL_EXPR, into a CILK_SPAWN_STMT tree and returns it. */
1313 build_cilk_spawn (location_t loc
, tree call
)
1315 if (!cilk_set_spawn_marker (loc
, call
))
1316 return error_mark_node
;
1317 tree spawn_stmt
= build1 (CILK_SPAWN_STMT
, TREE_TYPE (call
), call
);
1318 TREE_SIDE_EFFECTS (spawn_stmt
) = 1;
1322 /* Returns a tree of type CILK_SYNC_STMT. */
1325 build_cilk_sync (void)
1327 tree sync
= build0 (CILK_SYNC_STMT
, void_type_node
);
1328 TREE_SIDE_EFFECTS (sync
) = 1;
1332 /* Helper for contains_cilk_spawn_stmt, callback for walk_tree. Return
1333 non-null tree if TP contains CILK_SPAWN_STMT. */
1336 contains_cilk_spawn_stmt_walker (tree
*tp
, int *, void *)
1338 if (TREE_CODE (*tp
) == CILK_SPAWN_STMT
)
1344 /* Returns true if EXPR or any of its subtrees contain CILK_SPAWN_STMT
1348 contains_cilk_spawn_stmt (tree expr
)
1350 return walk_tree (&expr
, contains_cilk_spawn_stmt_walker
, NULL
, NULL
)
1354 /* Return a error location for EXPR if LOC is not set. */
1357 get_error_location (tree expr
, location_t loc
)
1359 if (loc
== UNKNOWN_LOCATION
)
1361 if (TREE_CODE (expr
) == MODIFY_EXPR
)
1362 expr
= TREE_OPERAND (expr
, 0);
1363 loc
= EXPR_LOCATION (expr
);
1368 /* Check that no array notation or spawn statement is in EXPR.
1369 If not true generate an error at LOC for ARRAY_GMSGID or
1373 check_no_cilk (tree expr
, const char *array_msgid
, const char *spawn_msgid
,
1378 if (contains_array_notation_expr (expr
))
1380 loc
= get_error_location (expr
, loc
);
1381 error_at (loc
, array_msgid
);
1384 if (walk_tree (&expr
, contains_cilk_spawn_stmt_walker
, NULL
, NULL
))
1386 loc
= get_error_location (expr
, loc
);
1387 error_at (loc
, spawn_msgid
);