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"
30 #include "stringpool.h"
33 /* Returns true if the function call in FNDECL is __sec_implicit_index. */
36 is_sec_implicit_index_fn (tree fndecl
)
41 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
42 fndecl
= TREE_OPERAND (fndecl
, 0);
45 (TREE_CODE (fndecl
) == FUNCTION_DECL
46 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
47 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CILKPLUS_SEC_IMPLICIT_INDEX
);
50 /* Returns the first and only argument for FN, which should be a
51 sec_implicit_index function. FN's location in the source file is as
52 indicated by LOCATION. The argument to FN must be a constant integer
53 expression, otherwise returns -1. */
56 extract_sec_implicit_index_arg (location_t location
, tree fn
)
59 HOST_WIDE_INT return_int
= 0;
61 if (TREE_CODE (fn
) == CALL_EXPR
)
63 fn_arg
= CALL_EXPR_ARG (fn
, 0);
64 if (TREE_CODE (fn_arg
) == INTEGER_CST
)
65 return_int
= int_cst_value (fn_arg
);
68 /* If the location is unknown, and if fn has a location, then use that
69 information so that the user has a better idea where the error
71 if (location
== UNKNOWN_LOCATION
&& EXPR_HAS_LOCATION (fn
))
72 location
= EXPR_LOCATION (fn
);
73 error_at (location
, "__sec_implicit_index parameter must be an "
74 "integer constant expression");
81 /* Returns true if there is a length mismatch among exprssions that are at the
82 same dimension and one the same side of the equal sign. The Array notation
83 lengths (LIST->LENGTH) is passed in as a 2D vector of trees. */
86 length_mismatch_in_expr_p (location_t loc
, vec
<vec
<an_parts
> >list
)
89 tree length
= NULL_TREE
;
91 size_t x
= list
.length ();
92 size_t y
= list
[0].length ();
94 for (jj
= 0; jj
< y
; jj
++)
97 for (ii
= 0; ii
< x
; ii
++)
100 length
= list
[ii
][jj
].length
;
101 else if (TREE_CODE (length
) == INTEGER_CST
)
103 /* If length is a INTEGER, and list[ii][jj] is an integer then
104 check if they are equal. If they are not equal then return
106 if (TREE_CODE (list
[ii
][jj
].length
) == INTEGER_CST
107 && !tree_int_cst_equal (list
[ii
][jj
].length
, length
))
109 error_at (loc
, "length mismatch in expression");
114 /* We set the length node as the current node just in case it turns
115 out to be an integer. */
116 length
= list
[ii
][jj
].length
;
122 /* Given an FNDECL of type FUNCTION_DECL or ADDR_EXPR, return the corresponding
123 BUILT_IN_CILKPLUS_SEC_REDUCE_* being called. If none, return
126 enum built_in_function
127 is_cilkplus_reduce_builtin (tree fndecl
)
130 return BUILT_IN_NONE
;
131 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
132 fndecl
= TREE_OPERAND (fndecl
, 0);
134 if (TREE_CODE (fndecl
) == FUNCTION_DECL
135 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
136 switch (DECL_FUNCTION_CODE (fndecl
))
138 case BUILT_IN_CILKPLUS_SEC_REDUCE_ADD
:
139 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUL
:
140 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO
:
141 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO
:
142 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX
:
143 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN
:
144 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN_IND
:
145 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX_IND
:
146 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO
:
147 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO
:
148 case BUILT_IN_CILKPLUS_SEC_REDUCE
:
149 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUTATING
:
150 return DECL_FUNCTION_CODE (fndecl
);
155 return BUILT_IN_NONE
;
158 /* This function will recurse into EXPR finding any
159 ARRAY_NOTATION_EXPRs and calculate the overall rank of EXPR,
160 storing it in *RANK. LOC is the location of the original expression.
162 ORIG_EXPR is the original expression used to display if any rank
163 mismatch errors are found.
165 Upon entry, *RANK must be either 0, or the rank of a parent
166 expression that must have the same rank as the one being
167 calculated. It is illegal to have multiple array notation with different
168 rank in the same expression (see examples below for clarification).
170 If there were any rank mismatches while calculating the rank, an
171 error will be issued, and FALSE will be returned. Otherwise, TRUE
174 If IGNORE_BUILTIN_FN is TRUE, ignore array notation specific
175 built-in functions (__sec_reduce_*, etc).
177 Here are some examples of array notations and their rank:
188 D[5][0:10:2] 1 (since D[5] is considered "scalar")
192 F[:][:][:] + E[:] + 5 + X RANKMISMATCH-ERROR since rank (E[:]) = 1 and
193 rank (F[:][:][:]) = 3. They must be equal
194 or have a rank of zero.
195 F[:][5][10] + E[:] * 5 + *Y 1
199 func (B[:][:][:][:]) 4
202 func2 (A[:], B[:][:][:][:]) RANKMISMATCH-ERROR -- Since Rank (A[:]) = 1
203 and Rank (B[:][:][:][:]) = 4
205 A[:] + func (B[:][:][:][:]) RANKMISMATCH-ERROR
206 func2 (A[:], B[:]) + func (A) 1
211 find_rank (location_t loc
, tree orig_expr
, tree expr
, bool ignore_builtin_fn
,
215 size_t ii
= 0, current_rank
= 0;
217 if (TREE_CODE (expr
) == ARRAY_NOTATION_REF
)
222 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
225 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
227 else if (handled_component_p (ii_tree
)
228 || INDIRECT_REF_P (ii_tree
))
229 ii_tree
= TREE_OPERAND (ii_tree
, 0);
230 else if (TREE_CODE (ii_tree
) == PARM_DECL
237 /* In this case, all the expressions this function has encountered thus
238 far have been scalars or expressions with zero rank. Please see
239 header comment for examples of such expression. */
240 *rank
= current_rank
;
241 else if (*rank
!= current_rank
)
243 /* In this case, find rank is being recursed through a set of
244 expression of the form A <OPERATION> B, where A and B both have
245 array notations in them and the rank of A is not equal to rank of
247 A simple example of such case is the following: X[:] + Y[:][:] */
248 *rank
= current_rank
;
252 else if (TREE_CODE (expr
) == STATEMENT_LIST
)
254 tree_stmt_iterator ii_tsi
;
255 for (ii_tsi
= tsi_start (expr
); !tsi_end_p (ii_tsi
);
257 if (!find_rank (loc
, orig_expr
, *tsi_stmt_ptr (ii_tsi
),
258 ignore_builtin_fn
, rank
))
263 if (TREE_CODE (expr
) == CALL_EXPR
)
265 tree func_name
= CALL_EXPR_FN (expr
);
266 tree prev_arg
= NULL_TREE
, arg
;
267 call_expr_arg_iterator iter
;
268 size_t prev_rank
= 0;
269 if (TREE_CODE (func_name
) == ADDR_EXPR
)
270 if (!ignore_builtin_fn
)
271 if (is_cilkplus_reduce_builtin (func_name
))
272 /* If it is a built-in function, then we know it returns a
275 if (!find_rank (loc
, orig_expr
, func_name
, ignore_builtin_fn
, rank
))
277 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
279 if (!find_rank (loc
, orig_expr
, arg
, ignore_builtin_fn
, rank
))
281 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
)
282 && prev_rank
!= *rank
)
283 error_at (EXPR_LOCATION (prev_arg
),
284 "rank mismatch between %qE and %qE", prev_arg
,
286 else if (prev_arg
&& prev_rank
!= *rank
)
287 /* Here the original expression is printed as a "heads-up"
288 to the programmer. This is because since there is no
289 location information for the offending argument, the
290 error could be in some internally generated code that is
291 not visible for the programmer. Thus, the correct fix
292 may lie in the original expression. */
293 error_at (loc
, "rank mismatch in expression %qE",
303 tree prev_arg
= NULL_TREE
;
304 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (expr
)); ii
++)
306 if (TREE_OPERAND (expr
, ii
)
307 && !find_rank (loc
, orig_expr
, TREE_OPERAND (expr
, ii
),
308 ignore_builtin_fn
, rank
))
310 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
))
311 error_at (EXPR_LOCATION (prev_arg
),
312 "rank mismatch between %qE and %qE", prev_arg
,
313 TREE_OPERAND (expr
, ii
));
316 prev_arg
= TREE_OPERAND (expr
, ii
);
323 /* Extracts all array notations in NODE and stores them in ARRAY_LIST. If
324 IGNORE_BUILTIN_FN is set, then array notations inside array notation
325 specific built-in functions are ignored. The NODE can be constants,
326 VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions. */
329 extract_array_notation_exprs (tree node
, bool ignore_builtin_fn
,
330 vec
<tree
, va_gc
> **array_list
)
336 if (TREE_CODE (node
) == ARRAY_NOTATION_REF
)
338 vec_safe_push (*array_list
, node
);
341 if (TREE_CODE (node
) == DECL_EXPR
)
343 tree x
= DECL_EXPR_DECL (node
);
344 if (DECL_INITIAL (x
))
345 extract_array_notation_exprs (DECL_INITIAL (x
),
349 else if (TREE_CODE (node
) == STATEMENT_LIST
)
351 tree_stmt_iterator ii_tsi
;
352 for (ii_tsi
= tsi_start (node
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
353 extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi
),
354 ignore_builtin_fn
, array_list
);
356 else if (TREE_CODE (node
) == CALL_EXPR
)
359 call_expr_arg_iterator iter
;
360 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node
)))
362 if (ignore_builtin_fn
)
366 vec_safe_push (*array_list
, node
);
370 if (is_sec_implicit_index_fn (CALL_EXPR_FN (node
)))
372 vec_safe_push (*array_list
, node
);
375 /* This will extract array notations in function pointers. */
376 extract_array_notation_exprs (CALL_EXPR_FN (node
), ignore_builtin_fn
,
378 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, node
)
379 extract_array_notation_exprs (arg
, ignore_builtin_fn
, array_list
);
382 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (node
)); ii
++)
383 if (TREE_OPERAND (node
, ii
))
384 extract_array_notation_exprs (TREE_OPERAND (node
, ii
),
385 ignore_builtin_fn
, array_list
);
389 /* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
390 contains the expanded ARRAY_REF. E.g., if LIST[<some_index>] contains
391 an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
392 expansion. If *ORIG matches LIST[<some_index>] then *ORIG is set to
393 ARRAY_OPERAND[<some_index>]. This function recursively steps through
394 all the sub-trees of *ORIG, if it is larger than a single
395 ARRAY_NOTATION_REF. */
398 replace_array_notations (tree
*orig
, bool ignore_builtin_fn
,
399 vec
<tree
, va_gc
> *list
,
400 vec
<tree
, va_gc
> *array_operand
)
403 extern tree
build_c_cast (location_t
, tree
, tree
);
404 tree node
= NULL_TREE
, node_replacement
= NULL_TREE
;
406 if (vec_safe_length (list
) == 0)
409 if (TREE_CODE (*orig
) == ARRAY_NOTATION_REF
)
411 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
414 node_replacement
= (*array_operand
)[ii
];
415 *orig
= node_replacement
;
418 else if (TREE_CODE (*orig
) == STATEMENT_LIST
)
420 tree_stmt_iterator ii_tsi
;
421 for (ii_tsi
= tsi_start (*orig
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
422 replace_array_notations (tsi_stmt_ptr (ii_tsi
), ignore_builtin_fn
, list
,
425 else if (TREE_CODE (*orig
) == CALL_EXPR
)
428 call_expr_arg_iterator iter
;
429 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig
)))
431 if (!ignore_builtin_fn
)
433 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
436 node_replacement
= (*array_operand
)[ii
];
437 *orig
= node_replacement
;
442 if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig
)))
444 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
447 node_replacement
= (*array_operand
)[ii
];
448 *orig
= build_c_cast (EXPR_LOCATION (*orig
),
449 TREE_TYPE (*orig
), node_replacement
);
453 /* Fixes array notations in array notations in function pointers. */
454 replace_array_notations (&CALL_EXPR_FN (*orig
), ignore_builtin_fn
, list
,
457 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, *orig
)
459 replace_array_notations (&arg
, ignore_builtin_fn
, list
,
461 CALL_EXPR_ARG (*orig
, ii
) = arg
;
467 for (ii
= 0; ii
< (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig
)); ii
++)
468 if (TREE_OPERAND (*orig
, ii
))
469 replace_array_notations (&TREE_OPERAND (*orig
, ii
), ignore_builtin_fn
,
470 list
, array_operand
);
475 /* Callback for walk_tree. Find all the scalar expressions in *TP and push
476 them in DATA struct, typecasted to (void *). If *WALK_SUBTREES is set to 0
477 then do not go into the *TP's subtrees. Since this function steps through
478 all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively. The
479 function returns NULL_TREE unconditionally. */
482 find_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
484 struct inv_list
*i_list
= (struct inv_list
*) data
;
489 if (TREE_CONSTANT (*tp
))
490 return NULL_TREE
; /* No need to save constant to a variable. */
491 if (TREE_CODE (*tp
) != COMPOUND_EXPR
&& !contains_array_notation_expr (*tp
))
493 vec_safe_push (i_list
->list_values
, *tp
);
496 else if (TREE_CODE (*tp
) == ARRAY_NOTATION_REF
497 || TREE_CODE (*tp
) == ARRAY_REF
498 || TREE_CODE (*tp
) == CALL_EXPR
)
499 /* No need to step through the internals of array notation. */
505 /* This function is used by C and C++ front-ends. In C++, additional
506 tree codes such as TARGET_EXPR must be eliminated. These codes are
507 passed into additional_tcodes and are walked through and checked. */
508 for (ii
= 0; ii
< vec_safe_length (i_list
->additional_tcodes
); ii
++)
509 if (TREE_CODE (*tp
) == (*(i_list
->additional_tcodes
))[ii
])
515 /* Callback for walk_tree. Replace all the scalar expressions in *TP with the
516 appropriate replacement stored in the struct *DATA (typecasted to void*).
517 The subtrees are not touched if *WALK_SUBTREES is set to zero. */
520 replace_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
524 struct inv_list
*i_list
= (struct inv_list
*) data
;
526 if (vec_safe_length (i_list
->list_values
))
528 for (ii
= 0; vec_safe_iterate (i_list
->list_values
, ii
, &t
); ii
++)
529 if (simple_cst_equal (*tp
, t
) == 1)
531 vec_safe_iterate (i_list
->replacement
, ii
, &r
);
532 gcc_assert (r
!= NULL_TREE
);
542 /* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR
546 contains_array_notation_expr (tree expr
)
548 vec
<tree
, va_gc
> *array_list
= NULL
;
552 if (TREE_CODE (expr
) == FUNCTION_DECL
)
553 if (is_cilkplus_reduce_builtin (expr
))
556 extract_array_notation_exprs (expr
, false, &array_list
);
557 if (vec_safe_length (array_list
) == 0)
563 /* This function will check if OP is a CALL_EXPR that is a built-in array
564 notation function. If so, then we will return its type to be the type of
565 the array notation inside. */
568 find_correct_array_notation_type (tree op
)
570 tree fn_arg
, return_type
= NULL_TREE
;
574 return_type
= TREE_TYPE (op
); /* This is the default case. */
575 if (TREE_CODE (op
) == CALL_EXPR
)
576 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op
)))
578 fn_arg
= CALL_EXPR_ARG (op
, 0);
580 return_type
= TREE_TYPE (fn_arg
);
586 /* Extracts all the array notation triplet information from LIST and stores
587 them in the following fields of the 2-D array NODE(size x rank):
588 START, LENGTH and STRIDE, holding the starting index, length, and stride,
589 respectively. In addition, it also sets two bool fields, IS_VECTOR and
590 COUNT_DOWN, in NODE indicating whether a certain value at a certain field
591 is a vector and if the array is accessed from high to low. */
594 cilkplus_extract_an_triplets (vec
<tree
, va_gc
> *list
, size_t size
, size_t rank
,
595 vec
<vec
<struct cilkplus_an_parts
> > *node
)
597 vec
<vec
<tree
> > array_exprs
= vNULL
;
599 node
->safe_grow_cleared (size
);
600 array_exprs
.safe_grow_cleared (size
);
603 for (size_t ii
= 0; ii
< size
; ii
++)
605 (*node
)[ii
].safe_grow_cleared (rank
);
606 array_exprs
[ii
].safe_grow_cleared (rank
);
608 for (size_t ii
= 0; ii
< size
; ii
++)
611 tree ii_tree
= (*list
)[ii
];
614 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
616 array_exprs
[ii
][jj
] = ii_tree
;
618 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
620 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
621 ii_tree
= TREE_OPERAND (ii_tree
, 0);
626 for (size_t ii
= 0; ii
< size
; ii
++)
627 if (TREE_CODE ((*list
)[ii
]) == ARRAY_NOTATION_REF
)
628 for (size_t jj
= 0; jj
< rank
; jj
++)
630 tree ii_tree
= array_exprs
[ii
][jj
];
631 (*node
)[ii
][jj
].is_vector
= true;
632 (*node
)[ii
][jj
].value
= ARRAY_NOTATION_ARRAY (ii_tree
);
633 (*node
)[ii
][jj
].start
634 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
635 ARRAY_NOTATION_START (ii_tree
));
636 (*node
)[ii
][jj
].length
637 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
638 ARRAY_NOTATION_LENGTH (ii_tree
));
639 (*node
)[ii
][jj
].stride
640 = fold_build1 (CONVERT_EXPR
, integer_type_node
,
641 ARRAY_NOTATION_STRIDE (ii_tree
));
644 release_vec_vec (array_exprs
);
647 /* Replaces all the __sec_implicit_arg functions in LIST with the induction
648 variable stored in VAR at the appropriate location pointed by the
649 __sec_implicit_arg's first parameter. Emits an error if the parameter is
650 not between 0 and RANK. */
653 fix_sec_implicit_args (location_t loc
, vec
<tree
, va_gc
> *list
,
654 vec
<an_loop_parts
> an_loop_info
, size_t rank
,
657 vec
<tree
, va_gc
> *array_operand
= NULL
;
658 for (size_t ii
= 0; ii
< vec_safe_length (list
); ii
++)
659 if (TREE_CODE ((*list
)[ii
]) == CALL_EXPR
660 && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list
)[ii
])))
662 int idx
= extract_sec_implicit_index_arg (loc
, (*list
)[ii
]);
664 /* In this case, the returning function would have emitted an
665 error thus it is not necessary to do so again. */
667 else if (idx
< (int) rank
)
668 vec_safe_push (array_operand
, an_loop_info
[idx
].var
);
671 error_at (loc
, "__sec_implicit_index argument %d must be "
672 "less than the rank of %qE", idx
, orig_stmt
);
677 /* Save the existing value into the array operand. */
678 vec_safe_push (array_operand
, (*list
)[ii
]);
679 return array_operand
;
682 /* Returns true if NAME is an IDENTIFIER_NODE with identifier "vector",
683 "__vector", or "__vector__". */
686 is_cilkplus_vector_p (tree name
)
688 return flag_cilkplus
&& is_attribute_p ("vector", name
);