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"
29 #include "fold-const.h"
30 #include "stringpool.h"
31 #include "langhooks.h"
32 #include "gimple-expr.h"
34 #include "tree-iterator.h"
35 #include "tree-inline.h"
36 #include "c-family/c-common.h"
39 #include "hard-reg-set.h"
43 #include "diagnostic.h"
46 enum add_variable_type
{
47 /* Reference to previously-defined variable. */
49 /* Definition of a new variable in inner-scope. */
51 /* Write to possibly previously-defined variable. */
55 enum cilk_block_type
{
56 /* Indicates a _Cilk_spawn block. 30 was an arbitary number picked for
58 CILK_BLOCK_SPAWN
= 30,
59 /* Indicates _Cilk_for statement block. */
65 /* Kind of function to be created. */
66 enum cilk_block_type type
;
67 /* Signature of helper function. */
69 /* Containing function. */
71 /* Disposition of all variables in the inner statement. */
72 hash_map
<tree
, tree
> *decl_map
;
73 /* True if this function needs a static chain. */
75 /* Arguments to be passed to wrapper function, currently a list. */
77 /* Argument types, a list. */
79 /* Incoming parameters. */
81 /* Outer BLOCK object. */
85 static void extract_free_variables (tree
, struct wrapper_data
*,
86 enum add_variable_type
);
87 static HOST_WIDE_INT cilk_wrapper_count
;
89 /* Marks the CALL_EXPR or FUNCTION_DECL, FCALL, as a spawned function call
90 and the current function as a spawner. Emit error if the function call
91 is outside a function or if a non function-call is spawned. */
94 cilk_set_spawn_marker (location_t loc
, tree fcall
)
96 if (!current_function_decl
)
98 error_at (loc
, "%<_Cilk_spawn%> may only be used inside a function");
101 else if (fcall
== error_mark_node
)
102 /* Error reporting here is not necessary here since if FCALL is an
103 error_mark_node, the function marking it as error would have reported
106 else if (TREE_CODE (fcall
) != CALL_EXPR
107 /* In C++, TARGET_EXPR is generated when we have an overloaded
109 && TREE_CODE (fcall
) != TARGET_EXPR
)
111 error_at (loc
, "only function calls can be spawned");
116 cfun
->calls_cilk_spawn
= true;
121 /* This function will output the exit conditions for a spawn call. */
124 create_cilk_function_exit (tree frame
, bool detaches
, bool needs_sync
)
126 tree epi
= alloc_stmt_list ();
129 append_to_statement_list (build_cilk_sync (), &epi
);
130 tree func_ptr
= build1 (ADDR_EXPR
, cilk_frame_ptr_type_decl
, frame
);
131 tree pop_frame
= build_call_expr (cilk_pop_fndecl
, 1, func_ptr
);
132 tree worker
= cilk_dot (frame
, CILK_TI_FRAME_WORKER
, 0);
133 tree current
= cilk_arrow (worker
, CILK_TI_WORKER_CUR
, 0);
134 tree parent
= cilk_dot (frame
, CILK_TI_FRAME_PARENT
, 0);
135 tree set_current
= build2 (MODIFY_EXPR
, void_type_node
, current
, parent
);
136 append_to_statement_list (set_current
, &epi
);
137 append_to_statement_list (pop_frame
, &epi
);
138 tree call
= build_call_expr (cilk_leave_fndecl
, 1, func_ptr
);
141 tree flags
= cilk_dot (frame
, CILK_TI_FRAME_FLAGS
, false);
142 tree flags_cmp_expr
= fold_build2 (NE_EXPR
, TREE_TYPE (flags
), flags
,
143 build_int_cst (TREE_TYPE (flags
),
144 CILK_FRAME_VERSION
));
145 call
= fold_build3 (COND_EXPR
, void_type_node
, flags_cmp_expr
,
146 call
, build_empty_stmt (EXPR_LOCATION (flags
)));
148 append_to_statement_list (call
, &epi
);
152 /* Trying to get the correct cfun for the FUNCTION_DECL indicated by OUTER. */
155 pop_cfun_to (tree outer
)
158 current_function_decl
= outer
;
159 gcc_assert (cfun
== DECL_STRUCT_FUNCTION (current_function_decl
));
160 gcc_assert (cfun
->decl
== current_function_decl
);
163 /* This function does whatever is necessary to make the compiler emit a newly
164 generated function, FNDECL. */
167 call_graph_add_fn (tree fndecl
)
169 const tree outer
= current_function_decl
;
170 struct function
*f
= DECL_STRUCT_FUNCTION (fndecl
);
171 gcc_assert (TREE_CODE (fndecl
) == FUNCTION_DECL
);
173 f
->is_cilk_function
= 1;
174 f
->curr_properties
= cfun
->curr_properties
;
175 gcc_assert (cfun
== DECL_STRUCT_FUNCTION (outer
));
176 gcc_assert (cfun
->decl
== outer
);
179 cgraph_node::create (fndecl
);
183 /* Return true if this is a tree which is allowed to contain a spawn as
185 A spawn call may be wrapped in a series of unary operations such
186 as conversions. These conversions need not be "useless"
187 to be disregarded because they are retained in the spawned
188 statement. They are bypassed only to look for a spawn
190 A comparison to constant is simple enough to allow, and
191 is used to convert to bool. */
194 cilk_ignorable_spawn_rhs_op (tree exp
)
196 enum tree_code code
= TREE_CODE (exp
);
197 switch (TREE_CODE_CLASS (code
))
200 return code
== ADDR_EXPR
;
202 /* We need the spawn as operand 0 for now. That's where it
203 appears in the only case we really care about, conversion
205 return (TREE_CODE (TREE_OPERAND (exp
, 1)) == INTEGER_CST
);
214 /* Helper function for walk_tree. If *TP is a CILK_SPAWN_STMT, then unwrap
215 this "wrapper." The function returns NULL_TREE regardless. */
218 unwrap_cilk_spawn_stmt (tree
*tp
, int *walk_subtrees
, void *)
220 if (TREE_CODE (*tp
) == CILK_SPAWN_STMT
)
222 *tp
= CILK_SPAWN_FN (*tp
);
228 /* Returns true when EXP is a CALL_EXPR with _Cilk_spawn in front. Unwraps
229 CILK_SPAWN_STMT wrapper from the CALL_EXPR in *EXP0 statement. */
232 recognize_spawn (tree exp
, tree
*exp0
)
234 bool spawn_found
= false;
235 if (TREE_CODE (exp
) == CILK_SPAWN_STMT
)
237 /* Remove the CALL_EXPR from CILK_SPAWN_STMT wrapper. */
238 exp
= CILK_SPAWN_FN (exp
);
239 walk_tree (exp0
, unwrap_cilk_spawn_stmt
, NULL
, NULL
);
242 /* _Cilk_spawn can't be wrapped in expression such as PLUS_EXPR. */
243 else if (contains_cilk_spawn_stmt (exp
))
244 error_at (EXPR_LOCATION (exp
), "invalid use of %<_Cilk_spawn%>");
248 /* Returns true if *EXP0 is a recognized form of spawn. Recognized forms are,
249 after conversion to void, a call expression at outer level or an assignment
250 at outer level with the right hand side being a spawned call.
251 In addition to this, it also unwraps the CILK_SPAWN_STMT cover from the
252 CALL_EXPR that is being spawned.
253 Note that `=' in C++ may turn into a CALL_EXPR rather than a MODIFY_EXPR. */
256 cilk_detect_spawn_and_unwrap (tree
*exp0
)
260 if (!TREE_SIDE_EFFECTS (exp
))
263 /* Strip off any conversion to void. It does not affect whether spawn
264 is supported here. */
265 if (TREE_CODE (exp
) == CONVERT_EXPR
&& VOID_TYPE_P (TREE_TYPE (exp
)))
266 exp
= TREE_OPERAND (exp
, 0);
268 if (TREE_CODE (exp
) == MODIFY_EXPR
|| TREE_CODE (exp
) == INIT_EXPR
)
269 exp
= TREE_OPERAND (exp
, 1);
271 while (cilk_ignorable_spawn_rhs_op (exp
))
272 exp
= TREE_OPERAND (exp
, 0);
274 if (TREE_CODE (exp
) == TARGET_EXPR
)
275 if (TARGET_EXPR_INITIAL (exp
)
276 && TREE_CODE (TARGET_EXPR_INITIAL (exp
)) != AGGR_INIT_EXPR
)
277 exp
= TARGET_EXPR_INITIAL (exp
);
279 /* Happens with C++ TARGET_EXPR. */
280 if (exp
== NULL_TREE
)
283 while (TREE_CODE (exp
) == CLEANUP_POINT_EXPR
|| TREE_CODE (exp
) == EXPR_STMT
)
284 exp
= TREE_OPERAND (exp
, 0);
286 /* Now we should have a CALL_EXPR with a CILK_SPAWN_STMT wrapper around
287 it, or return false. */
288 if (recognize_spawn (exp
, exp0
))
293 /* This function will build and return a FUNCTION_DECL using information
297 create_cilk_helper_decl (struct wrapper_data
*wd
)
300 if (wd
->type
== CILK_BLOCK_FOR
)
301 sprintf (name
, "_cilk_for_" HOST_WIDE_INT_PRINT_DEC
, cilk_wrapper_count
++);
302 else if (wd
->type
== CILK_BLOCK_SPAWN
)
303 sprintf (name
, "_cilk_spn_" HOST_WIDE_INT_PRINT_DEC
, cilk_wrapper_count
++);
307 clean_symbol_name (name
);
308 tree fndecl
= build_decl (UNKNOWN_LOCATION
, FUNCTION_DECL
,
309 get_identifier (name
), wd
->fntype
);
311 TREE_PUBLIC (fndecl
) = 0;
312 TREE_STATIC (fndecl
) = 1;
313 TREE_USED (fndecl
) = 1;
314 DECL_ARTIFICIAL (fndecl
) = 0;
315 DECL_IGNORED_P (fndecl
) = 0;
316 DECL_EXTERNAL (fndecl
) = 0;
318 DECL_CONTEXT (fndecl
) = wd
->context
;
319 tree block
= make_node (BLOCK
);
320 DECL_INITIAL (fndecl
) = block
;
321 TREE_USED (block
) = 1;
322 BLOCK_SUPERCONTEXT (block
) = fndecl
;
323 gcc_assert (!DECL_SAVED_TREE (fndecl
));
325 /* Inlining would defeat the purpose of this wrapper.
326 Either it secretly switches stack frames or it allocates
327 a stable stack frame to hold function arguments even if
328 the parent stack frame is stolen. */
329 DECL_UNINLINABLE (fndecl
) = 1;
331 tree result_decl
= build_decl (UNKNOWN_LOCATION
, RESULT_DECL
, NULL_TREE
,
333 DECL_ARTIFICIAL (result_decl
) = 0;
334 DECL_IGNORED_P (result_decl
) = 1;
335 DECL_CONTEXT (result_decl
) = fndecl
;
336 DECL_RESULT (fndecl
) = result_decl
;
347 /* A function used by traversal to fill vector of decls for further work. */
350 fill_decls_vec (tree
const &key0
, tree
*val0
, auto_vec
<struct cilk_decls
> *v
)
353 struct cilk_decls dp
;
364 /* Function that actually creates necessary parm lists. */
367 create_parm_list (struct wrapper_data
*wd
, tree
*val0
, tree arg
)
372 if (val
== error_mark_node
|| val
== arg
)
375 if (TREE_CODE (val
) == PAREN_EXPR
)
377 /* We should not reach here with a register receiver.
378 We may see a register variable modified in the
379 argument list. Because register variables are
380 worker-local we don't need to work hard to support
381 them in code that spawns. */
382 if (VAR_P (arg
) && DECL_HARD_REGISTER (arg
))
384 error_at (EXPR_LOCATION (arg
),
385 "explicit register variable %qD may not be modified in "
387 arg
= null_pointer_node
;
390 arg
= build1 (ADDR_EXPR
, build_pointer_type (TREE_TYPE (arg
)), arg
);
392 val
= TREE_OPERAND (val
, 0);
394 gcc_assert (INDIRECT_REF_P (val
));
395 parm
= TREE_OPERAND (val
, 0);
400 TREE_CHAIN (parm
) = wd
->parms
;
402 wd
->argtypes
= tree_cons (NULL_TREE
, TREE_TYPE (parm
), wd
->argtypes
);
403 wd
->arglist
= tree_cons (NULL_TREE
, arg
, wd
->arglist
);
406 /* Sorting decls in a vector. */
409 compare_decls (const void *a
, const void *b
)
411 const struct cilk_decls
*t1
= (const struct cilk_decls
*) a
;
412 const struct cilk_decls
*t2
= (const struct cilk_decls
*) b
;
414 if (DECL_UID (t1
->key
) > DECL_UID (t2
->key
))
416 else if (DECL_UID (t1
->key
) < DECL_UID (t2
->key
))
422 /* This function is used to build a wrapper of a certain type. */
425 build_wrapper_type (struct wrapper_data
*wd
)
428 struct cilk_decls
* c
;
429 auto_vec
<struct cilk_decls
> vd
;
430 wd
->arglist
= NULL_TREE
;
431 wd
->parms
= NULL_TREE
;
432 wd
->argtypes
= void_list_node
;
434 gcc_assert (wd
->type
!= CILK_BLOCK_FOR
);
435 wd
->decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
436 vd
.qsort (compare_decls
);
438 FOR_EACH_VEC_ELT (vd
, j
, c
)
439 create_parm_list (wd
, c
->val
, c
->key
);
441 /* Now build a function.
442 Its return type is void (all side effects are via explicit parameters).
443 Its parameters are WRAPPER_PARMS with type WRAPPER_TYPES.
444 Actual arguments in the caller are WRAPPER_ARGS. */
445 wd
->fntype
= build_function_type (void_type_node
, wd
->argtypes
);
448 /* This function checks all the CALL_EXPRs in *TP found by cilk_outline. */
451 check_outlined_calls (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
454 bool *throws
= (bool *) data
;
458 if (TREE_CODE (t
) != CALL_EXPR
)
460 flags
= call_expr_flags (t
);
462 if (!(flags
& ECF_NOTHROW
) && flag_exceptions
)
464 if (flags
& ECF_RETURNS_TWICE
)
465 error_at (EXPR_LOCATION (t
),
466 "cannot spawn call to function that returns twice");
470 /* Each DECL in the source code (spawned statement) is passed to this function
471 once. Each instance of the DECL is replaced with the result of this
474 The parameters of the wrapper should have been entered into the map already.
475 This function only deals with variables with scope limited to the
476 spawned expression. */
479 copy_decl_for_cilk (tree decl
, copy_body_data
*id
)
481 switch (TREE_CODE (decl
))
484 return copy_decl_no_change (decl
, id
);
487 error_at (EXPR_LOCATION (decl
), "invalid use of label %q+D in "
490 return error_mark_node
;
494 /* RESULT_DECL and PARM_DECL has already been entered into the map. */
497 return error_mark_node
;
501 /* Alter a tree STMT from OUTER_FN to form the body of INNER_FN. */
504 cilk_outline (tree inner_fn
, tree
*stmt_p
, void *w
)
506 struct wrapper_data
*wd
= (struct wrapper_data
*) w
;
507 const tree outer_fn
= wd
->context
;
508 const bool nested
= (wd
->type
== CILK_BLOCK_FOR
);
511 auto_vec
<struct cilk_decls
> vd
;
513 struct cilk_decls
* c
;
515 DECL_STATIC_CHAIN (outer_fn
) = 1;
517 memset (&id
, 0, sizeof (id
));
518 /* Copy from the function containing the spawn... */
519 id
.src_fn
= outer_fn
;
521 /* ...to the wrapper. */
522 id
.dst_fn
= inner_fn
;
523 id
.src_cfun
= DECL_STRUCT_FUNCTION (outer_fn
);
525 /* There shall be no RETURN in spawn helper. */
527 id
.decl_map
= wd
->decl_map
;
528 id
.copy_decl
= nested
? copy_decl_no_change
: copy_decl_for_cilk
;
529 id
.block
= DECL_INITIAL (inner_fn
);
530 id
.transform_lang_insert_block
= NULL
;
532 id
.transform_new_cfg
= true;
533 id
.transform_call_graph_edges
= CB_CGE_MOVE
;
534 id
.remap_var_for_cilk
= true;
535 id
.regimplify
= true; /* unused? */
537 insert_decl_map (&id
, wd
->block
, DECL_INITIAL (inner_fn
));
539 wd
->decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
540 vd
.qsort (compare_decls
);
541 /* We don't want the private variables any more. */
542 FOR_EACH_VEC_ELT (vd
, j
, c
)
543 if (*(c
->val
) == error_mark_node
)
544 *(c
->val
) = nested
? copy_decl_no_change (c
->key
, &id
)
545 : copy_decl_for_cilk (c
->key
, &id
);
547 walk_tree (stmt_p
, copy_tree_body_r
, (void *) &id
, NULL
);
549 /* See if this function can throw or calls something that should
550 not be spawned. The exception part is only necessary if
551 flag_exceptions && !flag_non_call_exceptions. */
553 (void) walk_tree_without_duplicates (stmt_p
, check_outlined_calls
, &throws
);
556 /* Generate the body of a wrapper function that assigns the
557 result of the expression RHS into RECEIVER. RECEIVER must
558 be NULL if this is not a spawn -- the wrapper will return
559 a value. If this is a spawn, the wrapper will return void. */
562 create_cilk_wrapper_body (tree stmt
, struct wrapper_data
*wd
)
564 const tree outer
= current_function_decl
;
568 /* Build the type of the wrapper and its argument list from the
569 variables that it requires. */
570 build_wrapper_type (wd
);
572 /* Emit a function that takes WRAPPER_PARMS incoming and applies ARGS
573 (modified) to the wrapped function. Return the wrapper and modified ARGS
574 to the caller to generate a function call. */
575 fndecl
= create_cilk_helper_decl (wd
);
576 push_struct_function (fndecl
);
577 if (wd
->nested
&& (wd
->type
== CILK_BLOCK_FOR
))
579 gcc_assert (TREE_VALUE (wd
->arglist
) == NULL_TREE
);
580 TREE_VALUE (wd
->arglist
) = build2 (FDESC_EXPR
, ptr_type_node
,
581 fndecl
, integer_one_node
);
583 DECL_ARGUMENTS (fndecl
) = wd
->parms
;
585 for (p
= wd
->parms
; p
; p
= TREE_CHAIN (p
))
586 DECL_CONTEXT (p
) = fndecl
;
588 gcc_assert (!DECL_SAVED_TREE (fndecl
));
589 cilk_install_body_with_frame_cleanup (fndecl
, stmt
, (void *) wd
);
590 gcc_assert (DECL_SAVED_TREE (fndecl
));
594 /* Recognize the new function. */
595 call_graph_add_fn (fndecl
);
599 /* Initializes the wrapper data structure. */
602 init_wd (struct wrapper_data
*wd
, enum cilk_block_type type
)
605 wd
->fntype
= NULL_TREE
;
606 wd
->context
= current_function_decl
;
607 wd
->decl_map
= new hash_map
<tree
, tree
>;
608 /* _Cilk_for bodies are always nested. Others start off as
610 wd
->nested
= (type
== CILK_BLOCK_FOR
);
611 wd
->arglist
= NULL_TREE
;
612 wd
->argtypes
= NULL_TREE
;
613 wd
->block
= NULL_TREE
;
616 /* Clears the wrapper data structure. */
619 free_wd (struct wrapper_data
*wd
)
623 wd
->arglist
= NULL_TREE
;
624 wd
->argtypes
= NULL_TREE
;
625 wd
->parms
= NULL_TREE
;
629 /* Given a variable in an expression to be extracted into
630 a helper function, declare the helper function parameter
633 On entry the value of the (key, value) pair may be
635 (*, error_mark_node) -- Variable is private to helper function,
638 (var, var) -- Reference to outer scope (function or global scope).
640 (var, integer 0) -- Capture by value, save newly-declared PARM_DECL
641 for value in value slot.
643 (var, integer 1) -- Capture by reference, declare pointer to type
644 as new PARM_DECL and store (spawn_stmt (indirect_ref (parm)).
646 (var, ???) -- Pure output argument, handled similarly to above.
650 declare_one_free_variable (tree var0
, tree
*map0
)
652 const_tree var
= var0
;
654 tree var_type
= TREE_TYPE (var
), arg_type
;
658 gcc_assert (DECL_P (var
));
660 /* Ignore truly local variables. */
661 if (map
== error_mark_node
)
663 /* Ignore references to the parent function. */
667 gcc_assert (TREE_CODE (map
) == INTEGER_CST
);
669 /* A value is passed by reference if:
671 1. It is addressable, so that a copy may not be made.
672 2. It is modified in the spawned statement.
673 In the future this function may want to arrange
674 a warning if the spawned statement is a loop body
675 because an output argument would indicate a race.
676 Note: Earlier passes must have marked the variable addressable.
677 3. It is expensive to copy. */
679 (TREE_ADDRESSABLE (var_type
)
680 /* Arrays must be passed by reference. This is required for C
681 semantics -- arrays are not first class objects. Other
682 aggregate types can and should be passed by reference if
683 they are not passed to the spawned function. We aren't yet
684 distinguishing safe uses in argument calculation from unsafe
685 uses as outgoing function arguments, so we make a copy to
686 stabilize the value. */
687 || TREE_CODE (var_type
) == ARRAY_TYPE
688 || (tree
) map
== integer_one_node
);
691 var_type
= build_qualified_type (build_pointer_type (var_type
),
693 gcc_assert (!TREE_ADDRESSABLE (var_type
));
695 /* Maybe promote to int. */
696 if (INTEGRAL_TYPE_P (var_type
) && COMPLETE_TYPE_P (var_type
)
697 && tree_int_cst_lt (TYPE_SIZE (var_type
), TYPE_SIZE (integer_type_node
)))
698 arg_type
= integer_type_node
;
702 parm
= build_decl (UNKNOWN_LOCATION
, PARM_DECL
, NULL_TREE
, var_type
);
703 DECL_ARG_TYPE (parm
) = arg_type
;
704 DECL_ARTIFICIAL (parm
) = 0;
705 TREE_READONLY (parm
) = 1;
709 parm
= build1 (INDIRECT_REF
, TREE_TYPE (var_type
), parm
);
710 parm
= build1 (PAREN_EXPR
, void_type_node
, parm
);
716 /* Returns a wrapper function for a _Cilk_spawn. */
719 create_cilk_wrapper (tree exp
, tree
*args_out
)
721 struct wrapper_data wd
;
724 struct cilk_decls
* c
;
725 auto_vec
<struct cilk_decls
> vd
;
727 init_wd (&wd
, CILK_BLOCK_SPAWN
);
729 if (TREE_CODE (exp
) == CONVERT_EXPR
)
730 exp
= TREE_OPERAND (exp
, 0);
732 /* Special handling for top level INIT_EXPR. Usually INIT_EXPR means the
733 variable is defined in the spawned expression and can be private to the
734 spawn helper. A top level INIT_EXPR defines a variable to be initialized
735 by spawn and the variable must remain in the outer function. */
736 if (TREE_CODE (exp
) == INIT_EXPR
)
738 extract_free_variables (TREE_OPERAND (exp
, 0), &wd
, ADD_WRITE
);
739 extract_free_variables (TREE_OPERAND (exp
, 1), &wd
, ADD_READ
);
740 /* TREE_TYPE should be void. Be defensive. */
741 if (TREE_TYPE (exp
) != void_type_node
)
742 extract_free_variables (TREE_TYPE (exp
), &wd
, ADD_READ
);
745 extract_free_variables (exp
, &wd
, ADD_READ
);
746 wd
.decl_map
->traverse
<auto_vec
<struct cilk_decls
> *, fill_decls_vec
> (&vd
);
747 vd
.qsort (compare_decls
);
748 FOR_EACH_VEC_ELT (vd
, j
, c
)
749 declare_one_free_variable (c
->key
, c
->val
);
751 wd
.block
= TREE_BLOCK (exp
);
753 wd
.block
= DECL_INITIAL (current_function_decl
);
755 /* Now fvars maps the old variable to incoming variable. Update
756 the expression and arguments to refer to the new names. */
757 fndecl
= create_cilk_wrapper_body (exp
, &wd
);
758 *args_out
= wd
.arglist
;
765 /* Transform *SPAWN_P, a spawned CALL_EXPR, to gimple. *SPAWN_P can be a
766 CALL_EXPR, INIT_EXPR or MODIFY_EXPR. Returns GS_OK if everything is fine,
767 and GS_UNHANDLED, otherwise. */
770 gimplify_cilk_spawn (tree
*spawn_p
)
772 tree expr
= *spawn_p
;
773 tree function
, call1
, call2
, new_args
;
774 tree ii_args
= NULL_TREE
;
775 int total_args
= 0, ii
= 0;
777 tree setjmp_cond_expr
= NULL_TREE
;
778 tree setjmp_expr
, spawn_expr
, setjmp_value
= NULL_TREE
;
780 cfun
->calls_cilk_spawn
= 1;
781 cfun
->is_cilk_function
= 1;
783 /* Remove CLEANUP_POINT_EXPR and EXPR_STMT from *spawn_p. */
784 while (TREE_CODE (expr
) == CLEANUP_POINT_EXPR
785 || TREE_CODE (expr
) == EXPR_STMT
)
786 expr
= TREE_OPERAND (expr
, 0);
789 function
= create_cilk_wrapper (expr
, &new_args
);
791 /* This should give the number of parameters. */
792 total_args
= list_length (new_args
);
794 arg_array
= XNEWVEC (tree
, total_args
);
799 for (ii
= 0; ii
< total_args
; ii
++)
801 arg_array
[ii
] = TREE_VALUE (ii_args
);
802 ii_args
= TREE_CHAIN (ii_args
);
805 TREE_USED (function
) = 1;
806 rest_of_decl_compilation (function
, 0, 0);
808 call1
= cilk_call_setjmp (cfun
->cilk_frame_decl
);
810 if (arg_array
== NULL
|| *arg_array
== NULL_TREE
)
811 call2
= build_call_expr (function
, 0);
813 call2
= build_call_expr_loc_array (EXPR_LOCATION (*spawn_p
), function
,
814 total_args
, arg_array
);
815 *spawn_p
= alloc_stmt_list ();
816 tree f_ptr_type
= build_pointer_type (TREE_TYPE (cfun
->cilk_frame_decl
));
817 tree frame_ptr
= build1 (ADDR_EXPR
, f_ptr_type
, cfun
->cilk_frame_decl
);
818 tree save_fp
= build_call_expr (cilk_save_fp_fndecl
, 1, frame_ptr
);
819 append_to_statement_list (save_fp
, spawn_p
);
820 setjmp_value
= create_tmp_var (TREE_TYPE (call1
));
821 setjmp_expr
= fold_build2 (MODIFY_EXPR
, void_type_node
, setjmp_value
, call1
);
823 append_to_statement_list_force (setjmp_expr
, spawn_p
);
825 setjmp_cond_expr
= fold_build2 (EQ_EXPR
, TREE_TYPE (call1
), setjmp_value
,
826 build_int_cst (TREE_TYPE (call1
), 0));
827 spawn_expr
= fold_build3 (COND_EXPR
, void_type_node
, setjmp_cond_expr
,
828 call2
, build_empty_stmt (EXPR_LOCATION (call1
)));
829 append_to_statement_list (spawn_expr
, spawn_p
);
834 /* Make the frames necessary for a spawn call. */
837 make_cilk_frame (tree fn
)
839 struct function
*f
= DECL_STRUCT_FUNCTION (fn
);
842 if (f
->cilk_frame_decl
)
843 return f
->cilk_frame_decl
;
845 decl
= build_decl (EXPR_LOCATION (fn
), VAR_DECL
, NULL_TREE
,
846 cilk_frame_type_decl
);
847 DECL_CONTEXT (decl
) = fn
;
848 DECL_SEEN_IN_BIND_EXPR_P (decl
) = 1;
849 f
->cilk_frame_decl
= decl
;
853 /* Returns a STATEMENT_LIST with all the pedigree operations required for
854 install body with frame cleanup functions. FRAME_PTR is the pointer to
855 __cilkrts_stack_frame created by make_cilk_frame. */
858 cilk_install_body_pedigree_operations (tree frame_ptr
)
860 tree body_list
= alloc_stmt_list ();
861 tree enter_frame
= build_call_expr (cilk_enter_fast_fndecl
, 1, frame_ptr
);
862 append_to_statement_list (enter_frame
, &body_list
);
864 tree parent
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_PARENT
, 0);
865 tree worker
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_WORKER
, 0);
867 tree pedigree
= cilk_arrow (frame_ptr
, CILK_TI_FRAME_PEDIGREE
, 0);
868 tree pedigree_rank
= cilk_dot (pedigree
, CILK_TI_PEDIGREE_RANK
, 0);
869 tree parent_pedigree
= cilk_dot (pedigree
, CILK_TI_PEDIGREE_PARENT
, 0);
870 tree pedigree_parent
= cilk_arrow (parent
, CILK_TI_FRAME_PEDIGREE
, 0);
871 tree pedigree_parent_rank
= cilk_dot (pedigree_parent
,
872 CILK_TI_PEDIGREE_RANK
, 0);
873 tree pedigree_parent_parent
= cilk_dot (pedigree_parent
,
874 CILK_TI_PEDIGREE_PARENT
, 0);
875 tree worker_pedigree
= cilk_arrow (worker
, CILK_TI_WORKER_PEDIGREE
, 1);
876 tree w_pedigree_rank
= cilk_dot (worker_pedigree
, CILK_TI_PEDIGREE_RANK
, 0);
877 tree w_pedigree_parent
= cilk_dot (worker_pedigree
,
878 CILK_TI_PEDIGREE_PARENT
, 0);
880 /* sf.pedigree.rank = worker->pedigree.rank. */
881 tree exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_rank
,
883 append_to_statement_list (exp1
, &body_list
);
885 /* sf.pedigree.parent = worker->pedigree.parent. */
886 exp1
= build2 (MODIFY_EXPR
, void_type_node
, parent_pedigree
,
888 append_to_statement_list (exp1
, &body_list
);
890 /* sf.call_parent->pedigree.rank = worker->pedigree.rank. */
891 exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_parent_rank
,
893 append_to_statement_list (exp1
, &body_list
);
895 /* sf.call_parent->pedigree.parent = worker->pedigree.parent. */
896 exp1
= build2 (MODIFY_EXPR
, void_type_node
, pedigree_parent_parent
,
898 append_to_statement_list (exp1
, &body_list
);
900 /* sf->worker.pedigree.rank = 0. */
901 exp1
= build2 (MODIFY_EXPR
, void_type_node
, w_pedigree_rank
,
902 build_zero_cst (uint64_type_node
));
903 append_to_statement_list (exp1
, &body_list
);
905 /* sf->pedigree.parent = &sf->pedigree. */
906 exp1
= build2 (MODIFY_EXPR
, void_type_node
, w_pedigree_parent
,
908 build_pointer_type (cilk_pedigree_type_decl
),
910 append_to_statement_list (exp1
, &body_list
);
914 /* Add a new variable, VAR to a variable list in WD->DECL_MAP. HOW indicates
915 whether the variable is previously defined, currently defined, or a variable
916 that is being written to. */
919 add_variable (struct wrapper_data
*wd
, tree var
, enum add_variable_type how
)
921 tree
*valp
= wd
->decl_map
->get (var
);
924 tree val
= (tree
) *valp
;
925 /* If the variable is local, do nothing. */
926 if (val
== error_mark_node
)
928 /* If the variable was entered with itself as value,
929 meaning it belongs to an outer scope, do not alter
933 /* A statement expression may cause a variable to be
934 bound twice, once in BIND_EXPR and again in a
935 DECL_EXPR. That case caused a return in the
936 test above. Any other duplicate definition is
938 gcc_assert (how
!= ADD_BIND
);
939 if (how
!= ADD_WRITE
)
941 /* This variable might have been entered as read but is now written. */
948 tree val
= NULL_TREE
;
950 /* Nested function rewriting silently discards hard register
951 assignments for function scope variables, and they wouldn't
952 work anyway. Warn here. This misses one case: if the
953 register variable is used as the loop bound or increment it
954 has already been added to the map. */
955 if ((how
!= ADD_BIND
) && VAR_P (var
)
956 && !DECL_EXTERNAL (var
) && DECL_HARD_REGISTER (var
))
957 warning (0, "register assignment ignored for %qD used in Cilk block",
962 /* ADD_BIND means always make a fresh new variable. */
964 val
= error_mark_node
;
967 1. For cilk_for, refer to the outer scope definition as-is
968 2. For a spawned block, take a scalar in an rgument
969 and otherwise refer to the outer scope definition as-is.
970 3. For a spawned call, take a scalar in an argument. */
977 case CILK_BLOCK_SPAWN
:
978 if (TREE_ADDRESSABLE (var
))
984 val
= integer_zero_node
;
995 case CILK_BLOCK_SPAWN
:
996 if (TREE_ADDRESSABLE (var
))
997 val
= integer_one_node
;
1006 wd
->decl_map
->put (var
, val
);
1010 /* Find the variables referenced in an expression T. This does not avoid
1011 duplicates because a variable may be read in one context and written in
1012 another. HOW describes the context in which the reference is seen. If
1013 NESTED is true a nested function is being generated and variables in the
1014 original context should not be remapped. */
1017 extract_free_variables (tree t
, struct wrapper_data
*wd
,
1018 enum add_variable_type how
)
1023 enum tree_code code
= TREE_CODE (t
);
1024 bool is_expr
= IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
));
1027 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1032 case IDENTIFIER_NODE
:
1039 case PLACEHOLDER_EXPR
:
1043 /* These do not contain variable references. */
1047 /* Currently we don't see SSA_NAME. */
1048 extract_free_variables (SSA_NAME_VAR (t
), wd
, how
);
1052 /* This might be a reference to a label outside the Cilk block,
1053 which is an error, or a reference to a label in the Cilk block
1054 that we haven't seen yet. We can't tell. Ignore it. An
1055 invalid use will cause an error later in copy_decl_for_cilk. */
1059 if (wd
->type
!= CILK_BLOCK_SPAWN
)
1060 TREE_ADDRESSABLE (t
) = 1;
1063 if (!is_global_var (t
))
1064 add_variable (wd
, t
, how
);
1067 case NON_LVALUE_EXPR
:
1070 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1075 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_BIND
);
1076 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1080 case PREDECREMENT_EXPR
:
1081 case PREINCREMENT_EXPR
:
1082 case POSTDECREMENT_EXPR
:
1083 case POSTINCREMENT_EXPR
:
1084 /* These write their result. */
1085 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_WRITE
);
1086 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1090 /* This might modify its argument, and the value needs to be
1091 passed by reference in any case to preserve identity and
1092 type if is a promoting type. In the case of a nested loop
1093 just notice that we touch the variable. It will already
1094 be addressable, and marking it modified will cause a spurious
1095 warning about writing the control variable. */
1096 if (wd
->type
!= CILK_BLOCK_SPAWN
)
1097 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1099 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_WRITE
);
1103 /* Treating ARRAY_REF and BIT_FIELD_REF identically may
1104 mark the array as written but the end result is correct
1105 because the array is passed by pointer anyway. */
1107 /* Propagate the access type to the object part of which
1108 is being accessed here. As for ADDR_EXPR, don't do this
1109 in a nested loop, unless the access is to a fixed index. */
1110 if (wd
->type
!= CILK_BLOCK_FOR
|| TREE_CONSTANT (TREE_OPERAND (t
, 1)))
1111 extract_free_variables (TREE_OPERAND (t
, 0), wd
, how
);
1113 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_READ
);
1114 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1115 extract_free_variables (TREE_OPERAND (t
, 2), wd
, ADD_READ
);
1119 extract_free_variables (TREE_PURPOSE (t
), wd
, ADD_READ
);
1120 extract_free_variables (TREE_VALUE (t
), wd
, ADD_READ
);
1121 extract_free_variables (TREE_CHAIN (t
), wd
, ADD_READ
);
1126 int len
= TREE_VEC_LENGTH (t
);
1128 for (i
= 0; i
< len
; i
++)
1129 extract_free_variables (TREE_VEC_ELT (t
, i
), wd
, ADD_READ
);
1136 for (ii
= 0; ii
< VECTOR_CST_NELTS (t
); ii
++)
1137 extract_free_variables (VECTOR_CST_ELT (t
, ii
), wd
, ADD_READ
);
1142 extract_free_variables (TREE_REALPART (t
), wd
, ADD_READ
);
1143 extract_free_variables (TREE_IMAGPART (t
), wd
, ADD_READ
);
1149 for (decl
= BIND_EXPR_VARS (t
); decl
; decl
= TREE_CHAIN (decl
))
1151 add_variable (wd
, decl
, ADD_BIND
);
1152 /* A self-referential initialization is no problem because
1153 we already entered the variable into the map as local. */
1154 extract_free_variables (DECL_INITIAL (decl
), wd
, ADD_READ
);
1155 extract_free_variables (DECL_SIZE (decl
), wd
, ADD_READ
);
1156 extract_free_variables (DECL_SIZE_UNIT (decl
), wd
, ADD_READ
);
1158 extract_free_variables (BIND_EXPR_BODY (t
), wd
, ADD_READ
);
1162 case STATEMENT_LIST
:
1164 tree_stmt_iterator i
;
1165 for (i
= tsi_start (t
); !tsi_end_p (i
); tsi_next (&i
))
1166 extract_free_variables (*tsi_stmt_ptr (i
), wd
, ADD_READ
);
1172 extract_free_variables (TREE_OPERAND (t
, 0), wd
, ADD_BIND
);
1173 extract_free_variables (TREE_OPERAND (t
, 1), wd
, ADD_READ
);
1174 extract_free_variables (TREE_OPERAND (t
, 2), wd
, ADD_READ
);
1175 if (TREE_OPERAND (t
, 3) != TREE_OPERAND (t
, 1))
1176 extract_free_variables (TREE_OPERAND (t
, 3), wd
, ADD_READ
);
1181 if (TREE_NO_WARNING (t
))
1183 gcc_assert (errorcount
);
1189 if (TREE_CODE (DECL_EXPR_DECL (t
)) != TYPE_DECL
)
1190 extract_free_variables (DECL_EXPR_DECL (t
), wd
, ADD_BIND
);
1196 extract_free_variables (TYPE_MIN_VALUE (t
), wd
, ADD_READ
);
1197 extract_free_variables (TYPE_MAX_VALUE (t
), wd
, ADD_READ
);
1201 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1205 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1206 extract_free_variables (TYPE_DOMAIN (t
), wd
, ADD_READ
);
1210 extract_free_variables (TYPE_FIELDS (t
), wd
, ADD_READ
);
1214 extract_free_variables (TYPE_ARG_TYPES (t
), wd
, ADD_READ
);
1215 extract_free_variables (TYPE_METHOD_BASETYPE (t
), wd
, ADD_READ
);
1218 case AGGR_INIT_EXPR
:
1223 if (TREE_CODE (TREE_OPERAND (t
, 0)) == INTEGER_CST
)
1225 len
= TREE_INT_CST_LOW (TREE_OPERAND (t
, 0));
1227 for (ii
= 0; ii
< len
; ii
++)
1228 extract_free_variables (TREE_OPERAND (t
, ii
), wd
, ADD_READ
);
1229 extract_free_variables (TREE_TYPE (t
), wd
, ADD_READ
);
1236 unsigned HOST_WIDE_INT idx
= 0;
1237 constructor_elt
*ce
;
1238 for (idx
= 0; vec_safe_iterate (CONSTRUCTOR_ELTS (t
), idx
, &ce
); idx
++)
1239 extract_free_variables (ce
->value
, wd
, ADD_READ
);
1248 /* Walk over all the sub-trees of this operand. */
1249 len
= TREE_CODE_LENGTH (code
);
1251 /* Go through the subtrees. We need to do this in forward order so
1252 that the scope of a FOR_EXPR is handled properly. */
1253 for (i
= 0; i
< len
; ++i
)
1254 extract_free_variables (TREE_OPERAND (t
, i
), wd
, ADD_READ
);
1259 /* Add appropriate frames needed for a Cilk spawned function call, FNDECL.
1260 Returns the __cilkrts_stack_frame * variable. */
1263 insert_cilk_frame (tree fndecl
)
1265 tree addr
, body
, enter
, out
, orig_body
;
1266 location_t loc
= EXPR_LOCATION (fndecl
);
1268 if (!cfun
|| cfun
->decl
!= fndecl
)
1269 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1271 tree decl
= cfun
->cilk_frame_decl
;
1274 tree
*saved_tree
= &DECL_SAVED_TREE (fndecl
);
1275 decl
= make_cilk_frame (fndecl
);
1276 add_local_decl (cfun
, decl
);
1278 addr
= build1 (ADDR_EXPR
, cilk_frame_ptr_type_decl
, decl
);
1279 enter
= build_call_expr (cilk_enter_fndecl
, 1, addr
);
1280 out
= create_cilk_function_exit (cfun
->cilk_frame_decl
, false, true);
1282 /* The new body will be:
1283 __cilkrts_enter_frame_1 (&sf);
1288 __cilkrts_pop_frame (&sf);
1289 __cilkrts_leave_frame (&sf);
1292 body
= alloc_stmt_list ();
1293 orig_body
= *saved_tree
;
1295 if (TREE_CODE (orig_body
) == BIND_EXPR
)
1296 orig_body
= BIND_EXPR_BODY (orig_body
);
1298 append_to_statement_list (enter
, &body
);
1299 append_to_statement_list (build_stmt (loc
, TRY_FINALLY_EXPR
, orig_body
,
1301 if (TREE_CODE (*saved_tree
) == BIND_EXPR
)
1302 BIND_EXPR_BODY (*saved_tree
) = body
;
1309 /* Wraps CALL, a CALL_EXPR, into a CILK_SPAWN_STMT tree and returns it. */
1312 build_cilk_spawn (location_t loc
, tree call
)
1314 if (!cilk_set_spawn_marker (loc
, call
))
1315 return error_mark_node
;
1316 tree spawn_stmt
= build1 (CILK_SPAWN_STMT
, TREE_TYPE (call
), call
);
1317 TREE_SIDE_EFFECTS (spawn_stmt
) = 1;
1321 /* Returns a tree of type CILK_SYNC_STMT. */
1324 build_cilk_sync (void)
1326 tree sync
= build0 (CILK_SYNC_STMT
, void_type_node
);
1327 TREE_SIDE_EFFECTS (sync
) = 1;
1331 /* Helper for contains_cilk_spawn_stmt, callback for walk_tree. Return
1332 non-null tree if TP contains CILK_SPAWN_STMT. */
1335 contains_cilk_spawn_stmt_walker (tree
*tp
, int *, void *)
1337 if (TREE_CODE (*tp
) == CILK_SPAWN_STMT
)
1343 /* Returns true if EXPR or any of its subtrees contain CILK_SPAWN_STMT
1347 contains_cilk_spawn_stmt (tree expr
)
1349 return walk_tree (&expr
, contains_cilk_spawn_stmt_walker
, NULL
, NULL
)
1353 /* Return a error location for EXPR if LOC is not set. */
1356 get_error_location (tree expr
, location_t loc
)
1358 if (loc
== UNKNOWN_LOCATION
)
1360 if (TREE_CODE (expr
) == MODIFY_EXPR
)
1361 expr
= TREE_OPERAND (expr
, 0);
1362 loc
= EXPR_LOCATION (expr
);
1367 /* Check that no array notation or spawn statement is in EXPR.
1368 If not true generate an error at LOC for ARRAY_GMSGID or
1372 check_no_cilk (tree expr
, const char *array_msgid
, const char *spawn_msgid
,
1377 if (contains_array_notation_expr (expr
))
1379 loc
= get_error_location (expr
, loc
);
1380 error_at (loc
, array_msgid
);
1383 if (walk_tree (&expr
, contains_cilk_spawn_stmt_walker
, NULL
, NULL
))
1385 loc
= get_error_location (expr
, loc
);
1386 error_at (loc
, spawn_msgid
);