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-2014 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 (handled_component_p (ii_tree
)
225 || TREE_CODE (ii_tree
) == INDIRECT_REF
)
226 ii_tree
= TREE_OPERAND (ii_tree
, 0);
227 else if (TREE_CODE (ii_tree
) == PARM_DECL
228 || TREE_CODE (ii_tree
) == VAR_DECL
)
234 /* In this case, all the expressions this function has encountered thus
235 far have been scalars or expressions with zero rank. Please see
236 header comment for examples of such expression. */
237 *rank
= current_rank
;
238 else if (*rank
!= current_rank
)
240 /* In this case, find rank is being recursed through a set of
241 expression of the form A <OPERATION> B, where A and B both have
242 array notations in them and the rank of A is not equal to rank of
244 A simple example of such case is the following: X[:] + Y[:][:] */
245 *rank
= current_rank
;
249 else if (TREE_CODE (expr
) == STATEMENT_LIST
)
251 tree_stmt_iterator ii_tsi
;
252 for (ii_tsi
= tsi_start (expr
); !tsi_end_p (ii_tsi
);
254 if (!find_rank (loc
, orig_expr
, *tsi_stmt_ptr (ii_tsi
),
255 ignore_builtin_fn
, rank
))
260 if (TREE_CODE (expr
) == CALL_EXPR
)
262 tree func_name
= CALL_EXPR_FN (expr
);
263 tree prev_arg
= NULL_TREE
, arg
;
264 call_expr_arg_iterator iter
;
265 size_t prev_rank
= 0;
266 if (TREE_CODE (func_name
) == ADDR_EXPR
)
267 if (!ignore_builtin_fn
)
268 if (is_cilkplus_reduce_builtin (func_name
))
269 /* If it is a built-in function, then we know it returns a
272 if (!find_rank (loc
, orig_expr
, func_name
, ignore_builtin_fn
, rank
))
274 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, expr
)
276 if (!find_rank (loc
, orig_expr
, arg
, ignore_builtin_fn
, rank
))
278 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
)
279 && prev_rank
!= *rank
)
280 error_at (EXPR_LOCATION (prev_arg
),
281 "rank mismatch between %qE and %qE", prev_arg
,
283 else if (prev_arg
&& prev_rank
!= *rank
)
284 /* Here the original expression is printed as a "heads-up"
285 to the programmer. This is because since there is no
286 location information for the offending argument, the
287 error could be in some internally generated code that is
288 not visible for the programmer. Thus, the correct fix
289 may lie in the original expression. */
290 error_at (loc
, "rank mismatch in expression %qE",
300 tree prev_arg
= NULL_TREE
;
301 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (expr
)); ii
++)
303 if (TREE_OPERAND (expr
, ii
)
304 && !find_rank (loc
, orig_expr
, TREE_OPERAND (expr
, ii
),
305 ignore_builtin_fn
, rank
))
307 if (prev_arg
&& EXPR_HAS_LOCATION (prev_arg
))
308 error_at (EXPR_LOCATION (prev_arg
),
309 "rank mismatch between %qE and %qE", prev_arg
,
310 TREE_OPERAND (expr
, ii
));
313 prev_arg
= TREE_OPERAND (expr
, ii
);
320 /* Extracts all array notations in NODE and stores them in ARRAY_LIST. If
321 IGNORE_BUILTIN_FN is set, then array notations inside array notation
322 specific built-in functions are ignored. The NODE can be constants,
323 VAR_DECL, PARM_DECLS, STATEMENT_LISTS or full expressions. */
326 extract_array_notation_exprs (tree node
, bool ignore_builtin_fn
,
327 vec
<tree
, va_gc
> **array_list
)
330 if (TREE_CODE (node
) == ARRAY_NOTATION_REF
)
332 vec_safe_push (*array_list
, node
);
335 if (TREE_CODE (node
) == DECL_EXPR
)
337 tree x
= DECL_EXPR_DECL (node
);
338 if (DECL_INITIAL (x
))
339 extract_array_notation_exprs (DECL_INITIAL (x
),
343 else if (TREE_CODE (node
) == STATEMENT_LIST
)
345 tree_stmt_iterator ii_tsi
;
346 for (ii_tsi
= tsi_start (node
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
347 extract_array_notation_exprs (*tsi_stmt_ptr (ii_tsi
),
348 ignore_builtin_fn
, array_list
);
350 else if (TREE_CODE (node
) == CALL_EXPR
)
353 call_expr_arg_iterator iter
;
354 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (node
)))
356 if (ignore_builtin_fn
)
360 vec_safe_push (*array_list
, node
);
364 if (is_sec_implicit_index_fn (CALL_EXPR_FN (node
)))
366 vec_safe_push (*array_list
, node
);
369 /* This will extract array notations in function pointers. */
370 extract_array_notation_exprs (CALL_EXPR_FN (node
), ignore_builtin_fn
,
372 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, node
)
373 extract_array_notation_exprs (arg
, ignore_builtin_fn
, array_list
);
376 for (ii
= 0; ii
< TREE_CODE_LENGTH (TREE_CODE (node
)); ii
++)
377 if (TREE_OPERAND (node
, ii
))
378 extract_array_notation_exprs (TREE_OPERAND (node
, ii
),
379 ignore_builtin_fn
, array_list
);
383 /* LIST contains all the array notations found in *ORIG and ARRAY_OPERAND
384 contains the expanded ARRAY_REF. E.g., if LIST[<some_index>] contains
385 an array_notation expression, then ARRAY_OPERAND[<some_index>] contains its
386 expansion. If *ORIG matches LIST[<some_index>] then *ORIG is set to
387 ARRAY_OPERAND[<some_index>]. This function recursively steps through
388 all the sub-trees of *ORIG, if it is larger than a single
389 ARRAY_NOTATION_REF. */
392 replace_array_notations (tree
*orig
, bool ignore_builtin_fn
,
393 vec
<tree
, va_gc
> *list
,
394 vec
<tree
, va_gc
> *array_operand
)
397 extern tree
build_c_cast (location_t
, tree
, tree
);
398 tree node
= NULL_TREE
, node_replacement
= NULL_TREE
;
400 if (vec_safe_length (list
) == 0)
403 if (TREE_CODE (*orig
) == ARRAY_NOTATION_REF
)
405 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
408 node_replacement
= (*array_operand
)[ii
];
409 *orig
= node_replacement
;
412 else if (TREE_CODE (*orig
) == STATEMENT_LIST
)
414 tree_stmt_iterator ii_tsi
;
415 for (ii_tsi
= tsi_start (*orig
); !tsi_end_p (ii_tsi
); tsi_next (&ii_tsi
))
416 replace_array_notations (tsi_stmt_ptr (ii_tsi
), ignore_builtin_fn
, list
,
419 else if (TREE_CODE (*orig
) == CALL_EXPR
)
422 call_expr_arg_iterator iter
;
423 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (*orig
)))
425 if (!ignore_builtin_fn
)
427 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
430 node_replacement
= (*array_operand
)[ii
];
431 *orig
= node_replacement
;
436 if (is_sec_implicit_index_fn (CALL_EXPR_FN (*orig
)))
438 for (ii
= 0; vec_safe_iterate (list
, ii
, &node
); ii
++)
441 node_replacement
= (*array_operand
)[ii
];
442 *orig
= build_c_cast (EXPR_LOCATION (*orig
),
443 TREE_TYPE (*orig
), node_replacement
);
447 /* Fixes array notations in array notations in function pointers. */
448 replace_array_notations (&CALL_EXPR_FN (*orig
), ignore_builtin_fn
, list
,
451 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, *orig
)
453 replace_array_notations (&arg
, ignore_builtin_fn
, list
,
455 CALL_EXPR_ARG (*orig
, ii
) = arg
;
461 for (ii
= 0; ii
< (size_t) TREE_CODE_LENGTH (TREE_CODE (*orig
)); ii
++)
462 if (TREE_OPERAND (*orig
, ii
))
463 replace_array_notations (&TREE_OPERAND (*orig
, ii
), ignore_builtin_fn
,
464 list
, array_operand
);
469 /* Callback for walk_tree. Find all the scalar expressions in *TP and push
470 them in DATA struct, typecasted to (void *). If *WALK_SUBTREES is set to 0
471 then do not go into the *TP's subtrees. Since this function steps through
472 all the subtrees, *TP and TP can be NULL_TREE and NULL, respectively. The
473 function returns NULL_TREE unconditionally. */
476 find_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
478 struct inv_list
*i_list
= (struct inv_list
*) data
;
483 if (TREE_CONSTANT (*tp
))
484 return NULL_TREE
; /* No need to save constant to a variable. */
485 if (TREE_CODE (*tp
) != COMPOUND_EXPR
&& !contains_array_notation_expr (*tp
))
487 vec_safe_push (i_list
->list_values
, *tp
);
490 else if (TREE_CODE (*tp
) == ARRAY_NOTATION_REF
491 || TREE_CODE (*tp
) == ARRAY_REF
492 || TREE_CODE (*tp
) == CALL_EXPR
)
493 /* No need to step through the internals of array notation. */
499 /* This function is used by C and C++ front-ends. In C++, additional
500 tree codes such as TARGET_EXPR must be eliminated. These codes are
501 passed into additional_tcodes and are walked through and checked. */
502 for (ii
= 0; ii
< vec_safe_length (i_list
->additional_tcodes
); ii
++)
503 if (TREE_CODE (*tp
) == (*(i_list
->additional_tcodes
))[ii
])
509 /* Callback for walk_tree. Replace all the scalar expressions in *TP with the
510 appropriate replacement stored in the struct *DATA (typecasted to void*).
511 The subtrees are not touched if *WALK_SUBTREES is set to zero. */
514 replace_inv_trees (tree
*tp
, int *walk_subtrees
, void *data
)
518 struct inv_list
*i_list
= (struct inv_list
*) data
;
520 if (vec_safe_length (i_list
->list_values
))
522 for (ii
= 0; vec_safe_iterate (i_list
->list_values
, ii
, &t
); ii
++)
523 if (simple_cst_equal (*tp
, t
) == 1)
525 vec_safe_iterate (i_list
->replacement
, ii
, &r
);
526 gcc_assert (r
!= NULL_TREE
);
536 /* Returns true if EXPR or any of its subtrees contain ARRAY_NOTATION_EXPR
540 contains_array_notation_expr (tree expr
)
542 vec
<tree
, va_gc
> *array_list
= NULL
;
546 if (TREE_CODE (expr
) == FUNCTION_DECL
)
547 if (is_cilkplus_reduce_builtin (expr
))
550 extract_array_notation_exprs (expr
, false, &array_list
);
551 if (vec_safe_length (array_list
) == 0)
557 /* This function will check if OP is a CALL_EXPR that is a built-in array
558 notation function. If so, then we will return its type to be the type of
559 the array notation inside. */
562 find_correct_array_notation_type (tree op
)
564 tree fn_arg
, return_type
= NULL_TREE
;
568 return_type
= TREE_TYPE (op
); /* This is the default case. */
569 if (TREE_CODE (op
) == CALL_EXPR
)
570 if (is_cilkplus_reduce_builtin (CALL_EXPR_FN (op
)))
572 fn_arg
= CALL_EXPR_ARG (op
, 0);
574 return_type
= TREE_TYPE (fn_arg
);
580 /* Extracts all the array notation triplet information from LIST and stores
581 them in the following fields of the 2-D array NODE(size x rank):
582 START, LENGTH and STRIDE, holding the starting index, length, and stride,
583 respectively. In addition, it also sets two bool fields, IS_VECTOR and
584 COUNT_DOWN, in NODE indicating whether a certain value at a certain field
585 is a vector and if the array is accessed from high to low. */
588 cilkplus_extract_an_triplets (vec
<tree
, va_gc
> *list
, size_t size
, size_t rank
,
589 vec
<vec
<struct cilkplus_an_parts
> > *node
)
591 vec
<vec
<tree
> > array_exprs
= vNULL
;
593 node
->safe_grow_cleared (size
);
594 array_exprs
.safe_grow_cleared (size
);
597 for (size_t ii
= 0; ii
< size
; ii
++)
599 (*node
)[ii
].safe_grow_cleared (rank
);
600 array_exprs
[ii
].safe_grow_cleared (rank
);
602 for (size_t ii
= 0; ii
< size
; ii
++)
605 tree ii_tree
= (*list
)[ii
];
608 if (TREE_CODE (ii_tree
) == ARRAY_NOTATION_REF
)
610 array_exprs
[ii
][jj
] = ii_tree
;
612 ii_tree
= ARRAY_NOTATION_ARRAY (ii_tree
);
614 else if (TREE_CODE (ii_tree
) == ARRAY_REF
)
615 ii_tree
= TREE_OPERAND (ii_tree
, 0);
620 for (size_t ii
= 0; ii
< size
; ii
++)
621 if (TREE_CODE ((*list
)[ii
]) == ARRAY_NOTATION_REF
)
622 for (size_t jj
= 0; jj
< rank
; jj
++)
624 tree ii_tree
= array_exprs
[ii
][jj
];
625 (*node
)[ii
][jj
].is_vector
= true;
626 (*node
)[ii
][jj
].value
= ARRAY_NOTATION_ARRAY (ii_tree
);
627 (*node
)[ii
][jj
].start
= ARRAY_NOTATION_START (ii_tree
);
628 (*node
)[ii
][jj
].length
=
629 fold_build1 (CONVERT_EXPR
, integer_type_node
,
630 ARRAY_NOTATION_LENGTH (ii_tree
));
631 (*node
)[ii
][jj
].stride
=
632 fold_build1 (CONVERT_EXPR
, integer_type_node
,
633 ARRAY_NOTATION_STRIDE (ii_tree
));
637 /* Replaces all the __sec_implicit_arg functions in LIST with the induction
638 variable stored in VAR at the appropriate location pointed by the
639 __sec_implicit_arg's first parameter. Emits an error if the parameter is
640 not between 0 and RANK. */
643 fix_sec_implicit_args (location_t loc
, vec
<tree
, va_gc
> *list
,
644 vec
<an_loop_parts
> an_loop_info
, size_t rank
,
647 vec
<tree
, va_gc
> *array_operand
= NULL
;
648 for (size_t ii
= 0; ii
< vec_safe_length (list
); ii
++)
649 if (TREE_CODE ((*list
)[ii
]) == CALL_EXPR
650 && is_sec_implicit_index_fn (CALL_EXPR_FN ((*list
)[ii
])))
652 int idx
= extract_sec_implicit_index_arg (loc
, (*list
)[ii
]);
654 /* In this case, the returning function would have emitted an
655 error thus it is not necessary to do so again. */
657 else if (idx
< (int) rank
)
658 vec_safe_push (array_operand
, an_loop_info
[idx
].var
);
661 error_at (loc
, "__sec_implicit_index argument %d must be "
662 "less than the rank of %qE", idx
, orig_stmt
);
667 /* Save the existing value into the array operand. */
668 vec_safe_push (array_operand
, (*list
)[ii
]);
669 return array_operand
;