1 /* This file is part of the Intel(R) Cilk(TM) Plus support
2 This file contains the builtin functions for Array
4 Copyright (C) 2013-2017 Free Software Foundation, Inc.
5 Contributed by Balaji V. Iyer <balaji.v.iyer@intel.com>,
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 3, or (at your option)
15 GCC is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
28 #include "c-family/c-common.h"
29 #include "tree-iterator.h"
31 /* Returns true if the function call in FNDECL is __sec_implicit_index. */
34 is_sec_implicit_index_fn (tree fndecl
)
39 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
40 fndecl
= TREE_OPERAND (fndecl
, 0);
43 (TREE_CODE (fndecl
) == FUNCTION_DECL
44 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
45 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CILKPLUS_SEC_IMPLICIT_INDEX
);
48 /* Returns the first and only argument for FN, which should be a
49 sec_implicit_index function. FN's location in the source file is as
50 indicated by LOCATION. The argument to FN must be a constant integer
51 expression, otherwise returns -1. */
54 extract_sec_implicit_index_arg (location_t location
, tree fn
)
57 HOST_WIDE_INT return_int
= 0;
59 if (TREE_CODE (fn
) == CALL_EXPR
)
61 fn_arg
= CALL_EXPR_ARG (fn
, 0);
62 if (TREE_CODE (fn_arg
) == INTEGER_CST
)
63 return_int
= int_cst_value (fn_arg
);
66 /* If the location is unknown, and if fn has a location, then use that
67 information so that the user has a better idea where the error
69 if (location
== UNKNOWN_LOCATION
&& EXPR_HAS_LOCATION (fn
))
70 location
= EXPR_LOCATION (fn
);
71 error_at (location
, "__sec_implicit_index parameter must be an "
72 "integer constant expression");
79 /* Returns true if there is a length mismatch among exprssions that are at the
80 same dimension and one the same side of the equal sign. The Array notation
81 lengths (LIST->LENGTH) is passed in as a 2D vector of trees. */
84 length_mismatch_in_expr_p (location_t loc
, vec
<vec
<an_parts
> >list
)
87 tree length
= NULL_TREE
;
89 size_t x
= list
.length ();
90 size_t y
= list
[0].length ();
92 for (jj
= 0; jj
< y
; jj
++)
95 for (ii
= 0; ii
< x
; ii
++)
98 length
= list
[ii
][jj
].length
;
99 else if (TREE_CODE (length
) == INTEGER_CST
)
101 /* If length is a INTEGER, and list[ii][jj] is an integer then
102 check if they are equal. If they are not equal then return
104 if (TREE_CODE (list
[ii
][jj
].length
) == INTEGER_CST
105 && !tree_int_cst_equal (list
[ii
][jj
].length
, length
))
107 error_at (loc
, "length mismatch in expression");
112 /* We set the length node as the current node just in case it turns
113 out to be an integer. */
114 length
= list
[ii
][jj
].length
;
120 /* Given an FNDECL of type FUNCTION_DECL or ADDR_EXPR, return the corresponding
121 BUILT_IN_CILKPLUS_SEC_REDUCE_* being called. If none, return
124 enum built_in_function
125 is_cilkplus_reduce_builtin (tree fndecl
)
128 return BUILT_IN_NONE
;
129 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
130 fndecl
= TREE_OPERAND (fndecl
, 0);
132 if (TREE_CODE (fndecl
) == FUNCTION_DECL
133 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
134 switch (DECL_FUNCTION_CODE (fndecl
))
136 case BUILT_IN_CILKPLUS_SEC_REDUCE_ADD
:
137 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUL
:
138 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO
:
139 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO
:
140 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX
:
141 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN
:
142 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN_IND
:
143 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX_IND
:
144 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO
:
145 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO
:
146 case BUILT_IN_CILKPLUS_SEC_REDUCE
:
147 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUTATING
:
148 return DECL_FUNCTION_CODE (fndecl
);
153 return BUILT_IN_NONE
;
156 /* This function will recurse into EXPR finding any
157 ARRAY_NOTATION_EXPRs and calculate the overall rank of EXPR,
158 storing it in *RANK. LOC is the location of the original expression.
160 ORIG_EXPR is the original expression used to display if any rank
161 mismatch errors are found.
163 Upon entry, *RANK must be either 0, or the rank of a parent
164 expression that must have the same rank as the one being
165 calculated. It is illegal to have multiple array notation with different
166 rank in the same expression (see examples below for clarification).
168 If there were any rank mismatches while calculating the rank, an
169 error will be issued, and FALSE will be returned. Otherwise, TRUE
172 If IGNORE_BUILTIN_FN is TRUE, ignore array notation specific
173 built-in functions (__sec_reduce_*, etc).
175 Here are some examples of array notations and their rank:
186 D[5][0:10:2] 1 (since D[5] is considered "scalar")
190 F[:][:][:] + E[:] + 5 + X RANKMISMATCH-ERROR since rank (E[:]) = 1 and
191 rank (F[:][:][:]) = 3. They must be equal
192 or have a rank of zero.
193 F[:][5][10] + E[:] * 5 + *Y 1
197 func (B[:][:][:][:]) 4
200 func2 (A[:], B[:][:][:][:]) RANKMISMATCH-ERROR -- Since Rank (A[:]) = 1
201 and Rank (B[:][:][:][:]) = 4
203 A[:] + func (B[:][:][:][:]) RANKMISMATCH-ERROR
204 func2 (A[:], B[:]) + func (A) 1
209 find_rank (location_t loc
, tree orig_expr
, tree expr
, bool ignore_builtin_fn
,
213 size_t ii
= 0, current_rank
= 0;
215 if (TREE_CODE (expr
) == ARRAY_NOTATION_REF
)
220 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
223 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
225 else if (handled_component_p (ii_tree
)
226 || INDIRECT_REF_P (ii_tree
))
227 ii_tree
= TREE_OPERAND (ii_tree
, 0);
228 else if (TREE_CODE (ii_tree
) == PARM_DECL
235 /* In this case, all the expressions this function has encountered thus
236 far have been scalars or expressions with zero rank. Please see
237 header comment for examples of such expression. */
238 *rank
= current_rank
;
239 else if (*rank
!= current_rank
)
241 /* In this case, find rank is being recursed through a set of
242 expression of the form A <OPERATION> B, where A and B both have
243 array notations in them and the rank of A is not equal to rank of
245 A simple example of such case is the following: X[:] + Y[:][:] */
246 *rank
= current_rank
;
250 else if (TREE_CODE (expr
) == STATEMENT_LIST
)
252 tree_stmt_iterator ii_tsi
;
253 for (ii_tsi
= tsi_start (expr
); !tsi_end_p (ii_tsi
);
255 if (!find_rank (loc
, orig_expr
, *tsi_stmt_ptr (ii_tsi
),
256 ignore_builtin_fn
, rank
))
261 if (TREE_CODE (expr
) == CALL_EXPR
)
263 tree func_name
= CALL_EXPR_FN (expr
);
264 tree prev_arg
= NULL_TREE
, arg
;
265 call_expr_arg_iterator iter
;
266 size_t prev_rank
= 0;
267 if (TREE_CODE (func_name
) == ADDR_EXPR
)
268 if (!ignore_builtin_fn
)
269 if (is_cilkplus_reduce_builtin (func_name
))
270 /* If it is a built-in function, then we know it returns a
273 if (!find_rank (loc
, orig_expr
, func_name
, ignore_builtin_fn
, rank
))
275 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
277 if (!find_rank (loc
, orig_expr
, arg
, ignore_builtin_fn
, rank
))
279 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
)
280 && prev_rank
!= *rank
)
281 error_at (EXPR_LOCATION (prev_arg
),
282 "rank mismatch between %qE and %qE", prev_arg
,
284 else if (prev_arg
&& prev_rank
!= *rank
)
285 /* Here the original expression is printed as a "heads-up"
286 to the programmer. This is because since there is no
287 location information for the offending argument, the
288 error could be in some internally generated code that is
289 not visible for the programmer. Thus, the correct fix
290 may lie in the original expression. */
291 error_at (loc
, "rank mismatch in expression %qE",
301 tree prev_arg
= NULL_TREE
;
302 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (expr
)); ii
++)
304 if (TREE_OPERAND (expr
, ii
)
305 && !find_rank (loc
, orig_expr
, TREE_OPERAND (expr
, ii
),
306 ignore_builtin_fn
, rank
))
308 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
))
309 error_at (EXPR_LOCATION (prev_arg
),
310 "rank mismatch between %qE and %qE", prev_arg
,
311 TREE_OPERAND (expr
, ii
));
314 prev_arg
= TREE_OPERAND (expr
, ii
);
321 /* Extracts all array notations in NODE and stores them in ARRAY_LIST. If
322 IGNORE_BUILTIN_FN is set, then array notations inside array notation
323 specific built-in functions are ignored. The NODE can be constants,
324 VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions. */
327 extract_array_notation_exprs (tree node
, bool ignore_builtin_fn
,
328 vec
<tree
, va_gc
> **array_list
)
334 if (TREE_CODE (node
) == ARRAY_NOTATION_REF
)
336 vec_safe_push (*array_list
, node
);
339 if (TREE_CODE (node
) == DECL_EXPR
)
341 tree x
= DECL_EXPR_DECL (node
);
342 if (DECL_INITIAL (x
))
343 extract_array_notation_exprs (DECL_INITIAL (x
),
347 else if (TREE_CODE (node
) == STATEMENT_LIST
)
349 tree_stmt_iterator ii_tsi
;
350 for (ii_tsi
= tsi_start (node
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
351 extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi
),
352 ignore_builtin_fn
, array_list
);
354 else if (TREE_CODE (node
) == CALL_EXPR
)
357 call_expr_arg_iterator iter
;
358 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node
)))
360 if (ignore_builtin_fn
)
364 vec_safe_push (*array_list
, node
);
368 if (is_sec_implicit_index_fn (CALL_EXPR_FN (node
)))
370 vec_safe_push (*array_list
, node
);
373 /* This will extract array notations in function pointers. */
374 extract_array_notation_exprs (CALL_EXPR_FN (node
), ignore_builtin_fn
,
376 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, node
)
377 extract_array_notation_exprs (arg
, ignore_builtin_fn
, array_list
);
380 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (node
)); ii
++)
381 if (TREE_OPERAND (node
, ii
))
382 extract_array_notation_exprs (TREE_OPERAND (node
, ii
),
383 ignore_builtin_fn
, array_list
);
387 /* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
388 contains the expanded ARRAY_REF. E.g., if LIST[<some_index>] contains
389 an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
390 expansion. If *ORIG matches LIST[<some_index>] then *ORIG is set to
391 ARRAY_OPERAND[<some_index>]. This function recursively steps through
392 all the sub-trees of *ORIG, if it is larger than a single
393 ARRAY_NOTATION_REF. */
396 replace_array_notations (tree
*orig
, bool ignore_builtin_fn
,
397 vec
<tree
, va_gc
> *list
,
398 vec
<tree
, va_gc
> *array_operand
)
401 extern tree
build_c_cast (location_t
, tree
, tree
);
402 tree node
= NULL_TREE
, node_replacement
= NULL_TREE
;
404 if (vec_safe_length (list
) == 0)
407 if (TREE_CODE (*orig
) == ARRAY_NOTATION_REF
)
409 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
412 node_replacement
= (*array_operand
)[ii
];
413 *orig
= node_replacement
;
416 else if (TREE_CODE (*orig
) == STATEMENT_LIST
)
418 tree_stmt_iterator ii_tsi
;
419 for (ii_tsi
= tsi_start (*orig
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
420 replace_array_notations (tsi_stmt_ptr (ii_tsi
), ignore_builtin_fn
, list
,
423 else if (TREE_CODE (*orig
) == CALL_EXPR
)
426 call_expr_arg_iterator iter
;
427 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig
)))
429 if (!ignore_builtin_fn
)
431 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
434 node_replacement
= (*array_operand
)[ii
];
435 *orig
= node_replacement
;
440 if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig
)))
442 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
445 node_replacement
= (*array_operand
)[ii
];
446 *orig
= build_c_cast (EXPR_LOCATION (*orig
),
447 TREE_TYPE (*orig
), node_replacement
);
451 /* Fixes array notations in array notations in function pointers. */
452 replace_array_notations (&CALL_EXPR_FN (*orig
), ignore_builtin_fn
, list
,
455 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, *orig
)
457 replace_array_notations (&arg
, ignore_builtin_fn
, list
,
459 CALL_EXPR_ARG (*orig
, ii
) = arg
;
465 for (ii
= 0; ii
< (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig
)); ii
++)
466 if (TREE_OPERAND (*orig
, ii
))
467 replace_array_notations (&TREE_OPERAND (*orig
, ii
), ignore_builtin_fn
,
468 list
, array_operand
);
473 /* Callback for walk_tree. Find all the scalar expressions in *TP and push
474 them in DATA struct, typecasted to (void *). If *WALK_SUBTREES is set to 0
475 then do not go into the *TP's subtrees. Since this function steps through
476 all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively. The
477 function returns NULL_TREE unconditionally. */
480 find_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
482 struct inv_list
*i_list
= (struct inv_list
*) data
;
487 if (TREE_CONSTANT (*tp
))
488 return NULL_TREE
; /* No need to save constant to a variable. */
489 if (TREE_CODE (*tp
) != COMPOUND_EXPR
&& !contains_array_notation_expr (*tp
))
491 vec_safe_push (i_list
->list_values
, *tp
);
494 else if (TREE_CODE (*tp
) == ARRAY_NOTATION_REF
495 || TREE_CODE (*tp
) == ARRAY_REF
496 || TREE_CODE (*tp
) == CALL_EXPR
)
497 /* No need to step through the internals of array notation. */
503 /* This function is used by C and C++ front-ends. In C++, additional
504 tree codes such as TARGET_EXPR must be eliminated. These codes are
505 passed into additional_tcodes and are walked through and checked. */
506 for (ii
= 0; ii
< vec_safe_length (i_list
->additional_tcodes
); ii
++)
507 if (TREE_CODE (*tp
) == (*(i_list
->additional_tcodes
))[ii
])
513 /* Callback for walk_tree. Replace all the scalar expressions in *TP with the
514 appropriate replacement stored in the struct *DATA (typecasted to void*).
515 The subtrees are not touched if *WALK_SUBTREES is set to zero. */
518 replace_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
522 struct inv_list
*i_list
= (struct inv_list
*) data
;
524 if (vec_safe_length (i_list
->list_values
))
526 for (ii
= 0; vec_safe_iterate (i_list
->list_values
, ii
, &t
); ii
++)
527 if (simple_cst_equal (*tp
, t
) == 1)
529 vec_safe_iterate (i_list
->replacement
, ii
, &r
);
530 gcc_assert (r
!= NULL_TREE
);
540 /* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR
544 contains_array_notation_expr (tree expr
)
546 vec
<tree
, va_gc
> *array_list
= NULL
;
550 if (TREE_CODE (expr
) == FUNCTION_DECL
)
551 if (is_cilkplus_reduce_builtin (expr
))
554 extract_array_notation_exprs (expr
, false, &array_list
);
555 if (vec_safe_length (array_list
) == 0)
561 /* This function will check if OP is a CALL_EXPR that is a built-in array
562 notation function. If so, then we will return its type to be the type of
563 the array notation inside. */
566 find_correct_array_notation_type (tree op
)
568 tree fn_arg
, return_type
= NULL_TREE
;
572 return_type
= TREE_TYPE (op
); /* This is the default case. */
573 if (TREE_CODE (op
) == CALL_EXPR
)
574 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op
)))
576 fn_arg
= CALL_EXPR_ARG (op
, 0);
578 return_type
= TREE_TYPE (fn_arg
);
584 /* Extracts all the array notation triplet information from LIST and stores
585 them in the following fields of the 2-D array NODE(size x rank):
586 START, LENGTH and STRIDE, holding the starting index, length, and stride,
587 respectively. In addition, it also sets two bool fields, IS_VECTOR and
588 COUNT_DOWN, in NODE indicating whether a certain value at a certain field
589 is a vector and if the array is accessed from high to low. */
592 cilkplus_extract_an_triplets (vec
<tree
, va_gc
> *list
, size_t size
, size_t rank
,
593 vec
<vec
<struct cilkplus_an_parts
> > *node
)
595 vec
<vec
<tree
> > array_exprs
= vNULL
;
597 node
->safe_grow_cleared (size
);
598 array_exprs
.safe_grow_cleared (size
);
601 for (size_t ii
= 0; ii
< size
; ii
++)
603 (*node
)[ii
].safe_grow_cleared (rank
);
604 array_exprs
[ii
].safe_grow_cleared (rank
);
606 for (size_t ii
= 0; ii
< size
; ii
++)
609 tree ii_tree
= (*list
)[ii
];
612 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
614 array_exprs
[ii
][jj
] = ii_tree
;
616 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
618 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
619 ii_tree
= TREE_OPERAND (ii_tree
, 0);
624 for (size_t ii
= 0; ii
< size
; ii
++)
625 if (TREE_CODE ((*list
)[ii
]) == ARRAY_NOTATION_REF
)
626 for (size_t jj
= 0; jj
< rank
; jj
++)
628 tree ii_tree
= array_exprs
[ii
][jj
];
629 (*node
)[ii
][jj
].is_vector
= true;
630 (*node
)[ii
][jj
].value
= ARRAY_NOTATION_ARRAY (ii_tree
);
631 (*node
)[ii
][jj
].start
632 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
633 ARRAY_NOTATION_START (ii_tree
));
634 (*node
)[ii
][jj
].length
635 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
636 ARRAY_NOTATION_LENGTH (ii_tree
));
637 (*node
)[ii
][jj
].stride
638 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
639 ARRAY_NOTATION_STRIDE (ii_tree
));
642 release_vec_vec (array_exprs
);
645 /* Replaces all the __sec_implicit_arg functions in LIST with the induction
646 variable stored in VAR at the appropriate location pointed by the
647 __sec_implicit_arg's first parameter. Emits an error if the parameter is
648 not between 0 and RANK. */
651 fix_sec_implicit_args (location_t loc
, vec
<tree
, va_gc
> *list
,
652 vec
<an_loop_parts
> an_loop_info
, size_t rank
,
655 vec
<tree
, va_gc
> *array_operand
= NULL
;
656 for (size_t ii
= 0; ii
< vec_safe_length (list
); ii
++)
657 if (TREE_CODE ((*list
)[ii
]) == CALL_EXPR
658 && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list
)[ii
])))
660 int idx
= extract_sec_implicit_index_arg (loc
, (*list
)[ii
]);
662 /* In this case, the returning function would have emitted an
663 error thus it is not necessary to do so again. */
665 else if (idx
< (int) rank
)
666 vec_safe_push (array_operand
, an_loop_info
[idx
].var
);
669 error_at (loc
, "__sec_implicit_index argument %d must be "
670 "less than the rank of %qE", idx
, orig_stmt
);
675 /* Save the existing value into the array operand. */
676 vec_safe_push (array_operand
, (*list
)[ii
]);
677 return array_operand
;
680 /* Returns true if NAME is an IDENTIFIER_NODE with identifier "vector",
681 "__vector", or "__vector__". */
684 is_cilkplus_vector_p (tree name
)
686 return flag_cilkplus
&& is_attribute_p ("vector", name
);