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-2015 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"
31 #include "langhooks.h"
32 #include "tree-iterator.h"
33 #include "c-family/c-common.h"
34 #include "diagnostic-core.h"
36 /* Returns true if the function call in FNDECL is __sec_implicit_index. */
39 is_sec_implicit_index_fn (tree fndecl
)
44 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
45 fndecl
= TREE_OPERAND (fndecl
, 0);
48 (TREE_CODE (fndecl
) == FUNCTION_DECL
49 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
50 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CILKPLUS_SEC_IMPLICIT_INDEX
);
53 /* Returns the first and only argument for FN, which should be a
54 sec_implicit_index function. FN's location in the source file is as
55 indicated by LOCATION. The argument to FN must be a constant integer
56 expression, otherwise returns -1. */
59 extract_sec_implicit_index_arg (location_t location
, tree fn
)
62 HOST_WIDE_INT return_int
= 0;
64 if (TREE_CODE (fn
) == CALL_EXPR
)
66 fn_arg
= CALL_EXPR_ARG (fn
, 0);
67 if (TREE_CODE (fn_arg
) == INTEGER_CST
)
68 return_int
= int_cst_value (fn_arg
);
71 /* If the location is unknown, and if fn has a location, then use that
72 information so that the user has a better idea where the error
74 if (location
== UNKNOWN_LOCATION
&& EXPR_HAS_LOCATION (fn
))
75 location
= EXPR_LOCATION (fn
);
76 error_at (location
, "__sec_implicit_index parameter must be an "
77 "integer constant expression");
84 /* Returns true if there is a length mismatch among exprssions that are at the
85 same dimension and one the same side of the equal sign. The Array notation
86 lengths (LIST->LENGTH) is passed in as a 2D vector of trees. */
89 length_mismatch_in_expr_p (location_t loc
, vec
<vec
<an_parts
> >list
)
92 tree length
= NULL_TREE
;
94 size_t x
= list
.length ();
95 size_t y
= list
[0].length ();
97 for (jj
= 0; jj
< y
; jj
++)
100 for (ii
= 0; ii
< x
; ii
++)
103 length
= list
[ii
][jj
].length
;
104 else if (TREE_CODE (length
) == INTEGER_CST
)
106 /* If length is a INTEGER, and list[ii][jj] is an integer then
107 check if they are equal. If they are not equal then return
109 if (TREE_CODE (list
[ii
][jj
].length
) == INTEGER_CST
110 && !tree_int_cst_equal (list
[ii
][jj
].length
, length
))
112 error_at (loc
, "length mismatch in expression");
117 /* We set the length node as the current node just in case it turns
118 out to be an integer. */
119 length
= list
[ii
][jj
].length
;
125 /* Given an FNDECL of type FUNCTION_DECL or ADDR_EXPR, return the corresponding
126 BUILT_IN_CILKPLUS_SEC_REDUCE_* being called. If none, return
129 enum built_in_function
130 is_cilkplus_reduce_builtin (tree fndecl
)
133 return BUILT_IN_NONE
;
134 if (TREE_CODE (fndecl
) == ADDR_EXPR
)
135 fndecl
= TREE_OPERAND (fndecl
, 0);
137 if (TREE_CODE (fndecl
) == FUNCTION_DECL
138 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
139 switch (DECL_FUNCTION_CODE (fndecl
))
141 case BUILT_IN_CILKPLUS_SEC_REDUCE_ADD
:
142 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUL
:
143 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_ZERO
:
144 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_ZERO
:
145 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX
:
146 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN
:
147 case BUILT_IN_CILKPLUS_SEC_REDUCE_MIN_IND
:
148 case BUILT_IN_CILKPLUS_SEC_REDUCE_MAX_IND
:
149 case BUILT_IN_CILKPLUS_SEC_REDUCE_ANY_NONZERO
:
150 case BUILT_IN_CILKPLUS_SEC_REDUCE_ALL_NONZERO
:
151 case BUILT_IN_CILKPLUS_SEC_REDUCE
:
152 case BUILT_IN_CILKPLUS_SEC_REDUCE_MUTATING
:
153 return DECL_FUNCTION_CODE (fndecl
);
158 return BUILT_IN_NONE
;
161 /* This function will recurse into EXPR finding any
162 ARRAY_NOTATION_EXPRs and calculate the overall rank of EXPR,
163 storing it in *RANK. LOC is the location of the original expression.
165 ORIG_EXPR is the original expression used to display if any rank
166 mismatch errors are found.
168 Upon entry, *RANK must be either 0, or the rank of a parent
169 expression that must have the same rank as the one being
170 calculated. It is illegal to have multiple array notation with different
171 rank in the same expression (see examples below for clarification).
173 If there were any rank mismatches while calculating the rank, an
174 error will be issued, and FALSE will be returned. Otherwise, TRUE
177 If IGNORE_BUILTIN_FN is TRUE, ignore array notation specific
178 built-in functions (__sec_reduce_*, etc).
180 Here are some examples of array notations and their rank:
191 D[5][0:10:2] 1 (since D[5] is considered "scalar")
195 F[:][:][:] + E[:] + 5 + X RANKMISMATCH-ERROR since rank (E[:]) = 1 and
196 rank (F[:][:][:]) = 3. They must be equal
197 or have a rank of zero.
198 F[:][5][10] + E[:] * 5 + *Y 1
202 func (B[:][:][:][:]) 4
205 func2 (A[:], B[:][:][:][:]) RANKMISMATCH-ERROR -- Since Rank (A[:]) = 1
206 and Rank (B[:][:][:][:]) = 4
208 A[:] + func (B[:][:][:][:]) RANKMISMATCH-ERROR
209 func2 (A[:], B[:]) + func (A) 1
214 find_rank (location_t loc
, tree orig_expr
, tree expr
, bool ignore_builtin_fn
,
218 size_t ii
= 0, current_rank
= 0;
220 if (TREE_CODE (expr
) == ARRAY_NOTATION_REF
)
225 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
228 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
230 else if (handled_component_p (ii_tree
)
231 || INDIRECT_REF_P (ii_tree
))
232 ii_tree
= TREE_OPERAND (ii_tree
, 0);
233 else if (TREE_CODE (ii_tree
) == PARM_DECL
240 /* In this case, all the expressions this function has encountered thus
241 far have been scalars or expressions with zero rank. Please see
242 header comment for examples of such expression. */
243 *rank
= current_rank
;
244 else if (*rank
!= current_rank
)
246 /* In this case, find rank is being recursed through a set of
247 expression of the form A <OPERATION> B, where A and B both have
248 array notations in them and the rank of A is not equal to rank of
250 A simple example of such case is the following: X[:] + Y[:][:] */
251 *rank
= current_rank
;
255 else if (TREE_CODE (expr
) == STATEMENT_LIST
)
257 tree_stmt_iterator ii_tsi
;
258 for (ii_tsi
= tsi_start (expr
); !tsi_end_p (ii_tsi
);
260 if (!find_rank (loc
, orig_expr
, *tsi_stmt_ptr (ii_tsi
),
261 ignore_builtin_fn
, rank
))
266 if (TREE_CODE (expr
) == CALL_EXPR
)
268 tree func_name
= CALL_EXPR_FN (expr
);
269 tree prev_arg
= NULL_TREE
, arg
;
270 call_expr_arg_iterator iter
;
271 size_t prev_rank
= 0;
272 if (TREE_CODE (func_name
) == ADDR_EXPR
)
273 if (!ignore_builtin_fn
)
274 if (is_cilkplus_reduce_builtin (func_name
))
275 /* If it is a built-in function, then we know it returns a
278 if (!find_rank (loc
, orig_expr
, func_name
, ignore_builtin_fn
, rank
))
280 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
282 if (!find_rank (loc
, orig_expr
, arg
, ignore_builtin_fn
, rank
))
284 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
)
285 && prev_rank
!= *rank
)
286 error_at (EXPR_LOCATION (prev_arg
),
287 "rank mismatch between %qE and %qE", prev_arg
,
289 else if (prev_arg
&& prev_rank
!= *rank
)
290 /* Here the original expression is printed as a "heads-up"
291 to the programmer. This is because since there is no
292 location information for the offending argument, the
293 error could be in some internally generated code that is
294 not visible for the programmer. Thus, the correct fix
295 may lie in the original expression. */
296 error_at (loc
, "rank mismatch in expression %qE",
306 tree prev_arg
= NULL_TREE
;
307 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (expr
)); ii
++)
309 if (TREE_OPERAND (expr
, ii
)
310 && !find_rank (loc
, orig_expr
, TREE_OPERAND (expr
, ii
),
311 ignore_builtin_fn
, rank
))
313 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
))
314 error_at (EXPR_LOCATION (prev_arg
),
315 "rank mismatch between %qE and %qE", prev_arg
,
316 TREE_OPERAND (expr
, ii
));
319 prev_arg
= TREE_OPERAND (expr
, ii
);
326 /* Extracts all array notations in NODE and stores them in ARRAY_LIST. If
327 IGNORE_BUILTIN_FN is set, then array notations inside array notation
328 specific built-in functions are ignored. The NODE can be constants,
329 VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions. */
332 extract_array_notation_exprs (tree node
, bool ignore_builtin_fn
,
333 vec
<tree
, va_gc
> **array_list
)
339 if (TREE_CODE (node
) == ARRAY_NOTATION_REF
)
341 vec_safe_push (*array_list
, node
);
344 if (TREE_CODE (node
) == DECL_EXPR
)
346 tree x
= DECL_EXPR_DECL (node
);
347 if (DECL_INITIAL (x
))
348 extract_array_notation_exprs (DECL_INITIAL (x
),
352 else if (TREE_CODE (node
) == STATEMENT_LIST
)
354 tree_stmt_iterator ii_tsi
;
355 for (ii_tsi
= tsi_start (node
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
356 extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi
),
357 ignore_builtin_fn
, array_list
);
359 else if (TREE_CODE (node
) == CALL_EXPR
)
362 call_expr_arg_iterator iter
;
363 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node
)))
365 if (ignore_builtin_fn
)
369 vec_safe_push (*array_list
, node
);
373 if (is_sec_implicit_index_fn (CALL_EXPR_FN (node
)))
375 vec_safe_push (*array_list
, node
);
378 /* This will extract array notations in function pointers. */
379 extract_array_notation_exprs (CALL_EXPR_FN (node
), ignore_builtin_fn
,
381 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, node
)
382 extract_array_notation_exprs (arg
, ignore_builtin_fn
, array_list
);
385 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (node
)); ii
++)
386 if (TREE_OPERAND (node
, ii
))
387 extract_array_notation_exprs (TREE_OPERAND (node
, ii
),
388 ignore_builtin_fn
, array_list
);
392 /* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
393 contains the expanded ARRAY_REF. E.g., if LIST[<some_index>] contains
394 an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
395 expansion. If *ORIG matches LIST[<some_index>] then *ORIG is set to
396 ARRAY_OPERAND[<some_index>]. This function recursively steps through
397 all the sub-trees of *ORIG, if it is larger than a single
398 ARRAY_NOTATION_REF. */
401 replace_array_notations (tree
*orig
, bool ignore_builtin_fn
,
402 vec
<tree
, va_gc
> *list
,
403 vec
<tree
, va_gc
> *array_operand
)
406 extern tree
build_c_cast (location_t
, tree
, tree
);
407 tree node
= NULL_TREE
, node_replacement
= NULL_TREE
;
409 if (vec_safe_length (list
) == 0)
412 if (TREE_CODE (*orig
) == ARRAY_NOTATION_REF
)
414 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
417 node_replacement
= (*array_operand
)[ii
];
418 *orig
= node_replacement
;
421 else if (TREE_CODE (*orig
) == STATEMENT_LIST
)
423 tree_stmt_iterator ii_tsi
;
424 for (ii_tsi
= tsi_start (*orig
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
425 replace_array_notations (tsi_stmt_ptr (ii_tsi
), ignore_builtin_fn
, list
,
428 else if (TREE_CODE (*orig
) == CALL_EXPR
)
431 call_expr_arg_iterator iter
;
432 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig
)))
434 if (!ignore_builtin_fn
)
436 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
439 node_replacement
= (*array_operand
)[ii
];
440 *orig
= node_replacement
;
445 if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig
)))
447 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
450 node_replacement
= (*array_operand
)[ii
];
451 *orig
= build_c_cast (EXPR_LOCATION (*orig
),
452 TREE_TYPE (*orig
), node_replacement
);
456 /* Fixes array notations in array notations in function pointers. */
457 replace_array_notations (&CALL_EXPR_FN (*orig
), ignore_builtin_fn
, list
,
460 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, *orig
)
462 replace_array_notations (&arg
, ignore_builtin_fn
, list
,
464 CALL_EXPR_ARG (*orig
, ii
) = arg
;
470 for (ii
= 0; ii
< (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig
)); ii
++)
471 if (TREE_OPERAND (*orig
, ii
))
472 replace_array_notations (&TREE_OPERAND (*orig
, ii
), ignore_builtin_fn
,
473 list
, array_operand
);
478 /* Callback for walk_tree. Find all the scalar expressions in *TP and push
479 them in DATA struct, typecasted to (void *). If *WALK_SUBTREES is set to 0
480 then do not go into the *TP's subtrees. Since this function steps through
481 all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively. The
482 function returns NULL_TREE unconditionally. */
485 find_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
487 struct inv_list
*i_list
= (struct inv_list
*) data
;
492 if (TREE_CONSTANT (*tp
))
493 return NULL_TREE
; /* No need to save constant to a variable. */
494 if (TREE_CODE (*tp
) != COMPOUND_EXPR
&& !contains_array_notation_expr (*tp
))
496 vec_safe_push (i_list
->list_values
, *tp
);
499 else if (TREE_CODE (*tp
) == ARRAY_NOTATION_REF
500 || TREE_CODE (*tp
) == ARRAY_REF
501 || TREE_CODE (*tp
) == CALL_EXPR
)
502 /* No need to step through the internals of array notation. */
508 /* This function is used by C and C++ front-ends. In C++, additional
509 tree codes such as TARGET_EXPR must be eliminated. These codes are
510 passed into additional_tcodes and are walked through and checked. */
511 for (ii
= 0; ii
< vec_safe_length (i_list
->additional_tcodes
); ii
++)
512 if (TREE_CODE (*tp
) == (*(i_list
->additional_tcodes
))[ii
])
518 /* Callback for walk_tree. Replace all the scalar expressions in *TP with the
519 appropriate replacement stored in the struct *DATA (typecasted to void*).
520 The subtrees are not touched if *WALK_SUBTREES is set to zero. */
523 replace_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
527 struct inv_list
*i_list
= (struct inv_list
*) data
;
529 if (vec_safe_length (i_list
->list_values
))
531 for (ii
= 0; vec_safe_iterate (i_list
->list_values
, ii
, &t
); ii
++)
532 if (simple_cst_equal (*tp
, t
) == 1)
534 vec_safe_iterate (i_list
->replacement
, ii
, &r
);
535 gcc_assert (r
!= NULL_TREE
);
545 /* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR
549 contains_array_notation_expr (tree expr
)
551 vec
<tree
, va_gc
> *array_list
= NULL
;
555 if (TREE_CODE (expr
) == FUNCTION_DECL
)
556 if (is_cilkplus_reduce_builtin (expr
))
559 extract_array_notation_exprs (expr
, false, &array_list
);
560 if (vec_safe_length (array_list
) == 0)
566 /* This function will check if OP is a CALL_EXPR that is a built-in array
567 notation function. If so, then we will return its type to be the type of
568 the array notation inside. */
571 find_correct_array_notation_type (tree op
)
573 tree fn_arg
, return_type
= NULL_TREE
;
577 return_type
= TREE_TYPE (op
); /* This is the default case. */
578 if (TREE_CODE (op
) == CALL_EXPR
)
579 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op
)))
581 fn_arg
= CALL_EXPR_ARG (op
, 0);
583 return_type
= TREE_TYPE (fn_arg
);
589 /* Extracts all the array notation triplet information from LIST and stores
590 them in the following fields of the 2-D array NODE(size x rank):
591 START, LENGTH and STRIDE, holding the starting index, length, and stride,
592 respectively. In addition, it also sets two bool fields, IS_VECTOR and
593 COUNT_DOWN, in NODE indicating whether a certain value at a certain field
594 is a vector and if the array is accessed from high to low. */
597 cilkplus_extract_an_triplets (vec
<tree
, va_gc
> *list
, size_t size
, size_t rank
,
598 vec
<vec
<struct cilkplus_an_parts
> > *node
)
600 vec
<vec
<tree
> > array_exprs
= vNULL
;
602 node
->safe_grow_cleared (size
);
603 array_exprs
.safe_grow_cleared (size
);
606 for (size_t ii
= 0; ii
< size
; ii
++)
608 (*node
)[ii
].safe_grow_cleared (rank
);
609 array_exprs
[ii
].safe_grow_cleared (rank
);
611 for (size_t ii
= 0; ii
< size
; ii
++)
614 tree ii_tree
= (*list
)[ii
];
617 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
619 array_exprs
[ii
][jj
] = ii_tree
;
621 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
623 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
624 ii_tree
= TREE_OPERAND (ii_tree
, 0);
629 for (size_t ii
= 0; ii
< size
; ii
++)
630 if (TREE_CODE ((*list
)[ii
]) == ARRAY_NOTATION_REF
)
631 for (size_t jj
= 0; jj
< rank
; jj
++)
633 tree ii_tree
= array_exprs
[ii
][jj
];
634 (*node
)[ii
][jj
].is_vector
= true;
635 (*node
)[ii
][jj
].value
= ARRAY_NOTATION_ARRAY (ii_tree
);
636 (*node
)[ii
][jj
].start
= ARRAY_NOTATION_START (ii_tree
);
637 (*node
)[ii
][jj
].length
=
638 fold_build1 (CONVERT_EXPR
, integer_type_node
,
639 ARRAY_NOTATION_LENGTH (ii_tree
));
640 (*node
)[ii
][jj
].stride
=
641 fold_build1 (CONVERT_EXPR
, integer_type_node
,
642 ARRAY_NOTATION_STRIDE (ii_tree
));
646 /* Replaces all the __sec_implicit_arg functions in LIST with the induction
647 variable stored in VAR at the appropriate location pointed by the
648 __sec_implicit_arg's first parameter. Emits an error if the parameter is
649 not between 0 and RANK. */
652 fix_sec_implicit_args (location_t loc
, vec
<tree
, va_gc
> *list
,
653 vec
<an_loop_parts
> an_loop_info
, size_t rank
,
656 vec
<tree
, va_gc
> *array_operand
= NULL
;
657 for (size_t ii
= 0; ii
< vec_safe_length (list
); ii
++)
658 if (TREE_CODE ((*list
)[ii
]) == CALL_EXPR
659 && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list
)[ii
])))
661 int idx
= extract_sec_implicit_index_arg (loc
, (*list
)[ii
]);
663 /* In this case, the returning function would have emitted an
664 error thus it is not necessary to do so again. */
666 else if (idx
< (int) rank
)
667 vec_safe_push (array_operand
, an_loop_info
[idx
].var
);
670 error_at (loc
, "__sec_implicit_index argument %d must be "
671 "less than the rank of %qE", idx
, orig_stmt
);
676 /* Save the existing value into the array operand. */
677 vec_safe_push (array_operand
, (*list
)[ii
]);
678 return array_operand
;