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 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 "langhooks.h"
29 #include "tree-iterator.h"
30 #include "c-family/c-common.h"
31 #include "diagnostic-core.h"
33 /* Returns true if the function call in FNDECL is __sec_implicit_index. */
36 is_sec_implicit_index_fn (tree fndecl
)
38 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
39 fndecl
= TREE_OPERAND (fndecl
, 0);
42 (TREE_CODE (fndecl
) == FUNCTION_DECL
43 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
44 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CILKPLUS_SEC_IMPLICIT_INDEX
);
47 /* Returns the first and only argument for FN, which should be a
48 sec_implicit_index function. FN's location in the source file is as
49 indicated by LOCATION. The argument to FN must be a constant integer
50 expression, otherwise returns -1. */
53 extract_sec_implicit_index_arg (location_t location
, tree fn
)
56 HOST_WIDE_INT return_int
= 0;
58 if (TREE_CODE (fn
) == CALL_EXPR
)
60 fn_arg
= CALL_EXPR_ARG (fn
, 0);
61 if (TREE_CODE (fn_arg
) == INTEGER_CST
)
62 return_int
= int_cst_value (fn_arg
);
65 /* If the location is unknown, and if fn has a location, then use that
66 information so that the user has a better idea where the error
68 if (location
== UNKNOWN_LOCATION
&& EXPR_HAS_LOCATION (fn
))
69 location
= EXPR_LOCATION (fn
);
70 error_at (location
, "__sec_implicit_index parameter must be an "
71 "integer constant expression");
78 /* Returns true if there is a length mismatch among exprssions that are at the
79 same dimension and one the same side of the equal sign. The Array notation
80 lengths (LIST->LENGTH) is passed in as a 2D vector of trees. */
83 length_mismatch_in_expr_p (location_t loc
, vec
<vec
<an_parts
> >list
)
86 tree length
= NULL_TREE
;
88 size_t x
= list
.length ();
89 size_t y
= list
[0].length ();
91 for (jj
= 0; jj
< y
; jj
++)
94 for (ii
= 0; ii
< x
; ii
++)
97 length
= list
[ii
][jj
].length
;
98 else if (TREE_CODE (length
) == INTEGER_CST
)
100 /* If length is a INTEGER, and list[ii][jj] is an integer then
101 check if they are equal. If they are not equal then return
103 if (TREE_CODE (list
[ii
][jj
].length
) == INTEGER_CST
104 && !tree_int_cst_equal (list
[ii
][jj
].length
, length
))
106 error_at (loc
, "length mismatch in expression");
111 /* We set the length node as the current node just in case it turns
112 out to be an integer. */
113 length
= list
[ii
][jj
].length
;
119 /* Given an FNDECL of type FUNCTION_DECL or ADDR_EXPR, return the corresponding
120 BUILT_IN_CILKPLUS_SEC_REDUCE_* being called. If none, return
123 enum built_in_function
124 is_cilkplus_reduce_builtin (tree fndecl
)
127 return BUILT_IN_NONE
;
128 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
129 fndecl
= TREE_OPERAND (fndecl
, 0);
131 if (TREE_CODE (fndecl
) == FUNCTION_DECL
132 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
133 switch (DECL_FUNCTION_CODE (fndecl
))
135 case BUILT_IN_CILKPLUS_SEC_REDUCE_ADD
:
136 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUL
:
137 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO
:
138 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO
:
139 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX
:
140 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN
:
141 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN_IND
:
142 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX_IND
:
143 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO
:
144 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO
:
145 case BUILT_IN_CILKPLUS_SEC_REDUCE
:
146 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUTATING
:
147 return DECL_FUNCTION_CODE (fndecl
);
152 return BUILT_IN_NONE
;
155 /* This function will recurse into EXPR finding any
156 ARRAY_NOTATION_EXPRs and calculate the overall rank of EXPR,
157 storing it in *RANK. LOC is the location of the original expression.
159 ORIG_EXPR is the original expression used to display if any rank
160 mismatch errors are found.
162 Upon entry, *RANK must be either 0, or the rank of a parent
163 expression that must have the same rank as the one being
164 calculated. It is illegal to have multiple array notation with different
165 rank in the same expression (see examples below for clarification).
167 If there were any rank mismatches while calculating the rank, an
168 error will be issued, and FALSE will be returned. Otherwise, TRUE
171 If IGNORE_BUILTIN_FN is TRUE, ignore array notation specific
172 built-in functions (__sec_reduce_*, etc).
174 Here are some examples of array notations and their rank:
185 D[5][0:10:2] 1 (since D[5] is considered "scalar")
189 F[:][:][:] + E[:] + 5 + X RANKMISMATCH-ERROR since rank (E[:]) = 1 and
190 rank (F[:][:][:]) = 3. They must be equal
191 or have a rank of zero.
192 F[:][5][10] + E[:] * 5 + *Y 1
196 func (B[:][:][:][:]) 4
199 func2 (A[:], B[:][:][:][:]) RANKMISMATCH-ERROR -- Since Rank (A[:]) = 1
200 and Rank (B[:][:][:][:]) = 4
202 A[:] + func (B[:][:][:][:]) RANKMISMATCH-ERROR
203 func2 (A[:], B[:]) + func (A) 1
208 find_rank (location_t loc
, tree orig_expr
, tree expr
, bool ignore_builtin_fn
,
212 size_t ii
= 0, current_rank
= 0;
214 if (TREE_CODE (expr
) == ARRAY_NOTATION_REF
)
219 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
222 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
224 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
225 ii_tree
= TREE_OPERAND (ii_tree
, 0);
226 else if (TREE_CODE (ii_tree
) == PARM_DECL
227 || TREE_CODE (ii_tree
) == VAR_DECL
)
231 /* In this case, all the expressions this function has encountered thus
232 far have been scalars or expressions with zero rank. Please see
233 header comment for examples of such expression. */
234 *rank
= current_rank
;
235 else if (*rank
!= current_rank
)
237 /* In this case, find rank is being recursed through a set of
238 expression of the form A <OPERATION> B, where A and B both have
239 array notations in them and the rank of A is not equal to rank of
241 A simple example of such case is the following: X[:] + Y[:][:] */
242 *rank
= current_rank
;
246 else if (TREE_CODE (expr
) == STATEMENT_LIST
)
248 tree_stmt_iterator ii_tsi
;
249 for (ii_tsi
= tsi_start (expr
); !tsi_end_p (ii_tsi
);
251 if (!find_rank (loc
, orig_expr
, *tsi_stmt_ptr (ii_tsi
),
252 ignore_builtin_fn
, rank
))
257 if (TREE_CODE (expr
) == CALL_EXPR
)
259 tree func_name
= CALL_EXPR_FN (expr
);
260 tree prev_arg
= NULL_TREE
, arg
;
261 call_expr_arg_iterator iter
;
262 size_t prev_rank
= 0;
263 if (TREE_CODE (func_name
) == ADDR_EXPR
)
264 if (!ignore_builtin_fn
)
265 if (is_cilkplus_reduce_builtin (func_name
))
266 /* If it is a built-in function, then we know it returns a
269 if (!find_rank (loc
, orig_expr
, func_name
, ignore_builtin_fn
, rank
))
271 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
273 if (!find_rank (loc
, orig_expr
, arg
, ignore_builtin_fn
, rank
))
275 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
)
276 && prev_rank
!= *rank
)
277 error_at (EXPR_LOCATION (prev_arg
),
278 "rank mismatch between %qE and %qE", prev_arg
,
280 else if (prev_arg
&& prev_rank
!= *rank
)
281 /* Here the original expression is printed as a "heads-up"
282 to the programmer. This is because since there is no
283 location information for the offending argument, the
284 error could be in some internally generated code that is
285 not visible for the programmer. Thus, the correct fix
286 may lie in the original expression. */
287 error_at (loc
, "rank mismatch in expression %qE",
297 tree prev_arg
= NULL_TREE
;
298 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (expr
)); ii
++)
300 if (TREE_OPERAND (expr
, ii
)
301 && !find_rank (loc
, orig_expr
, TREE_OPERAND (expr
, ii
),
302 ignore_builtin_fn
, rank
))
304 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
))
305 error_at (EXPR_LOCATION (prev_arg
),
306 "rank mismatch between %qE and %qE", prev_arg
,
307 TREE_OPERAND (expr
, ii
));
310 prev_arg
= TREE_OPERAND (expr
, ii
);
317 /* Extracts all array notations in NODE and stores them in ARRAY_LIST. If
318 IGNORE_BUILTIN_FN is set, then array notations inside array notation
319 specific built-in functions are ignored. The NODE can be constants,
320 VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions. */
323 extract_array_notation_exprs (tree node
, bool ignore_builtin_fn
,
324 vec
<tree
, va_gc
> **array_list
)
327 if (TREE_CODE (node
) == ARRAY_NOTATION_REF
)
329 vec_safe_push (*array_list
, node
);
332 else if (TREE_CODE (node
) == STATEMENT_LIST
)
334 tree_stmt_iterator ii_tsi
;
335 for (ii_tsi
= tsi_start (node
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
336 extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi
),
337 ignore_builtin_fn
, array_list
);
339 else if (TREE_CODE (node
) == CALL_EXPR
)
342 call_expr_arg_iterator iter
;
343 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node
)))
345 if (ignore_builtin_fn
)
349 vec_safe_push (*array_list
, node
);
353 if (is_sec_implicit_index_fn (CALL_EXPR_FN (node
)))
355 vec_safe_push (*array_list
, node
);
358 /* This will extract array notations in function pointers. */
359 extract_array_notation_exprs (CALL_EXPR_FN (node
), ignore_builtin_fn
,
361 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, node
)
362 extract_array_notation_exprs (arg
, ignore_builtin_fn
, array_list
);
365 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (node
)); ii
++)
366 if (TREE_OPERAND (node
, ii
))
367 extract_array_notation_exprs (TREE_OPERAND (node
, ii
),
368 ignore_builtin_fn
, array_list
);
372 /* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
373 contains the expanded ARRAY_REF. E.g., if LIST[<some_index>] contains
374 an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
375 expansion. If *ORIG matches LIST[<some_index>] then *ORIG is set to
376 ARRAY_OPERAND[<some_index>]. This function recursively steps through
377 all the sub-trees of *ORIG, if it is larger than a single
378 ARRAY_NOTATION_REF. */
381 replace_array_notations (tree
*orig
, bool ignore_builtin_fn
,
382 vec
<tree
, va_gc
> *list
,
383 vec
<tree
, va_gc
> *array_operand
)
386 extern tree
build_c_cast (location_t
, tree
, tree
);
387 tree node
= NULL_TREE
, node_replacement
= NULL_TREE
;
389 if (vec_safe_length (list
) == 0)
392 if (TREE_CODE (*orig
) == ARRAY_NOTATION_REF
)
394 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
397 node_replacement
= (*array_operand
)[ii
];
398 *orig
= node_replacement
;
401 else if (TREE_CODE (*orig
) == STATEMENT_LIST
)
403 tree_stmt_iterator ii_tsi
;
404 for (ii_tsi
= tsi_start (*orig
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
405 replace_array_notations (tsi_stmt_ptr (ii_tsi
), ignore_builtin_fn
, list
,
408 else if (TREE_CODE (*orig
) == CALL_EXPR
)
411 call_expr_arg_iterator iter
;
412 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig
)))
414 if (!ignore_builtin_fn
)
416 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
419 node_replacement
= (*array_operand
)[ii
];
420 *orig
= node_replacement
;
425 if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig
)))
427 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
430 node_replacement
= (*array_operand
)[ii
];
431 *orig
= build_c_cast (EXPR_LOCATION (*orig
),
432 TREE_TYPE (*orig
), node_replacement
);
436 /* Fixes array notations in array notations in function pointers. */
437 replace_array_notations (&CALL_EXPR_FN (*orig
), ignore_builtin_fn
, list
,
440 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, *orig
)
442 replace_array_notations (&arg
, ignore_builtin_fn
, list
,
444 CALL_EXPR_ARG (*orig
, ii
) = arg
;
450 for (ii
= 0; ii
< (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig
)); ii
++)
451 if (TREE_OPERAND (*orig
, ii
))
452 replace_array_notations (&TREE_OPERAND (*orig
, ii
), ignore_builtin_fn
,
453 list
, array_operand
);
458 /* Callback for walk_tree. Find all the scalar expressions in *TP and push
459 them in DATA struct, typecasted to (void *). If *WALK_SUBTREES is set to 0
460 then do not go into the *TP's subtrees. Since this function steps through
461 all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively. The
462 function returns NULL_TREE unconditionally. */
465 find_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
467 struct inv_list
*i_list
= (struct inv_list
*) data
;
472 if (TREE_CONSTANT (*tp
))
473 return NULL_TREE
; /* No need to save constant to a variable. */
474 if (TREE_CODE (*tp
) != COMPOUND_EXPR
&& !contains_array_notation_expr (*tp
))
476 vec_safe_push (i_list
->list_values
, *tp
);
479 else if (TREE_CODE (*tp
) == ARRAY_NOTATION_REF
480 || TREE_CODE (*tp
) == ARRAY_REF
481 || TREE_CODE (*tp
) == CALL_EXPR
)
482 /* No need to step through the internals of array notation. */
488 /* This function is used by C and C++ front-ends. In C++, additional
489 tree codes such as TARGET_EXPR must be eliminated. These codes are
490 passed into additional_tcodes and are walked through and checked. */
491 for (ii
= 0; ii
< vec_safe_length (i_list
->additional_tcodes
); ii
++)
492 if (TREE_CODE (*tp
) == (*(i_list
->additional_tcodes
))[ii
])
498 /* Callback for walk_tree. Replace all the scalar expressions in *TP with the
499 appropriate replacement stored in the struct *DATA (typecasted to void*).
500 The subtrees are not touched if *WALK_SUBTREES is set to zero. */
503 replace_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
507 struct inv_list
*i_list
= (struct inv_list
*) data
;
509 if (vec_safe_length (i_list
->list_values
))
511 for (ii
= 0; vec_safe_iterate (i_list
->list_values
, ii
, &t
); ii
++)
512 if (simple_cst_equal (*tp
, t
) == 1)
514 vec_safe_iterate (i_list
->replacement
, ii
, &r
);
515 gcc_assert (r
!= NULL_TREE
);
525 /* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR
529 contains_array_notation_expr (tree expr
)
531 vec
<tree
, va_gc
> *array_list
= NULL
;
535 if (TREE_CODE (expr
) == FUNCTION_DECL
)
536 if (is_cilkplus_reduce_builtin (expr
))
539 extract_array_notation_exprs (expr
, false, &array_list
);
540 if (vec_safe_length (array_list
) == 0)
546 /* This function will check if OP is a CALL_EXPR that is a built-in array
547 notation function. If so, then we will return its type to be the type of
548 the array notation inside. */
551 find_correct_array_notation_type (tree op
)
553 tree fn_arg
, return_type
= NULL_TREE
;
557 return_type
= TREE_TYPE (op
); /* This is the default case. */
558 if (TREE_CODE (op
) == CALL_EXPR
)
559 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op
)))
561 fn_arg
= CALL_EXPR_ARG (op
, 0);
563 return_type
= TREE_TYPE (fn_arg
);
569 /* Extracts all the array notation triplet information from LIST and stores
570 them in the following fields of the 2-D array NODE(size x rank):
571 START, LENGTH and STRIDE, holding the starting index, length, and stride,
572 respectively. In addition, it also sets two bool fields, IS_VECTOR and
573 COUNT_DOWN, in NODE indicating whether a certain value at a certain field
574 is a vector and if the array is accessed from high to low. */
577 cilkplus_extract_an_triplets (vec
<tree
, va_gc
> *list
, size_t size
, size_t rank
,
578 vec
<vec
<struct cilkplus_an_parts
> > *node
)
580 vec
<vec
<tree
> > array_exprs
= vNULL
;
582 node
->safe_grow_cleared (size
);
583 array_exprs
.safe_grow_cleared (size
);
586 for (size_t ii
= 0; ii
< size
; ii
++)
588 (*node
)[ii
].safe_grow_cleared (rank
);
589 array_exprs
[ii
].safe_grow_cleared (rank
);
591 for (size_t ii
= 0; ii
< size
; ii
++)
594 tree ii_tree
= (*list
)[ii
];
597 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
599 array_exprs
[ii
][jj
] = ii_tree
;
601 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
603 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
604 ii_tree
= TREE_OPERAND (ii_tree
, 0);
609 for (size_t ii
= 0; ii
< size
; ii
++)
610 if (TREE_CODE ((*list
)[ii
]) == ARRAY_NOTATION_REF
)
611 for (size_t jj
= 0; jj
< rank
; jj
++)
613 tree ii_tree
= array_exprs
[ii
][jj
];
614 (*node
)[ii
][jj
].is_vector
= true;
615 (*node
)[ii
][jj
].value
= ARRAY_NOTATION_ARRAY (ii_tree
);
616 (*node
)[ii
][jj
].start
= ARRAY_NOTATION_START (ii_tree
);
617 (*node
)[ii
][jj
].length
=
618 fold_build1 (CONVERT_EXPR
, integer_type_node
,
619 ARRAY_NOTATION_LENGTH (ii_tree
));
620 (*node
)[ii
][jj
].stride
=
621 fold_build1 (CONVERT_EXPR
, integer_type_node
,
622 ARRAY_NOTATION_STRIDE (ii_tree
));
626 /* Replaces all the __sec_implicit_arg functions in LIST with the induction
627 variable stored in VAR at the appropriate location pointed by the
628 __sec_implicit_arg's first parameter. Emits an error if the parameter is
629 not between 0 and RANK. */
632 fix_sec_implicit_args (location_t loc
, vec
<tree
, va_gc
> *list
,
633 vec
<an_loop_parts
> an_loop_info
, size_t rank
,
636 vec
<tree
, va_gc
> *array_operand
= NULL
;
637 for (size_t ii
= 0; ii
< vec_safe_length (list
); ii
++)
638 if (TREE_CODE ((*list
)[ii
]) == CALL_EXPR
639 && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list
)[ii
])))
641 int idx
= extract_sec_implicit_index_arg (loc
, (*list
)[ii
]);
643 /* In this case, the returning function would have emitted an
644 error thus it is not necessary to do so again. */
646 else if (idx
< (int) rank
)
647 vec_safe_push (array_operand
, an_loop_info
[idx
].var
);
650 error_at (loc
, "__sec_implicit_index argument %d must be "
651 "less than the rank of %qE", idx
, orig_stmt
);
656 /* Save the existing value into the array operand. */
657 vec_safe_push (array_operand
, (*list
)[ii
]);
658 return array_operand
;