1/* Chains of recurrences.
2   Copyright (C) 2003-2020 Free Software Foundation, Inc.
3   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#ifndef GCC_TREE_CHREC_H
22#define GCC_TREE_CHREC_H
23
24/* The following trees are unique elements.  Thus the comparison of another
25   element to these elements should be done on the pointer to these trees,
26   and not on their value.
27
28   extern tree chrec_not_analyzed_yet;
29   extern tree chrec_dont_know;
30   extern tree chrec_known;
31
32   chrec_not_analyzed_yet is NULL_TREE and the others are defined
33   in global_trees[].  */
34
35/* After having added an automatically generated element, please
36   include it in the following function.  */
37
38static inline bool
39automatically_generated_chrec_p (const_tree chrec)
40{
41  return (chrec == chrec_dont_know
42	  || chrec == chrec_known);
43}
44
45/* The tree nodes aka. CHRECs.  */
46
47static inline bool
48tree_is_chrec (const_tree expr)
49{
50  if (TREE_CODE (expr) == POLYNOMIAL_CHREC
51      || automatically_generated_chrec_p (expr))
52    return true;
53  else
54    return false;
55}
56
57
58enum ev_direction {EV_DIR_GROWS, EV_DIR_DECREASES, EV_DIR_UNKNOWN};
59enum ev_direction scev_direction (const_tree);
60
61/* Chrec folding functions.  */
62extern tree chrec_fold_plus (tree, tree, tree);
63extern tree chrec_fold_minus (tree, tree, tree);
64extern tree chrec_fold_multiply (tree, tree, tree);
65extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL);
66extern tree chrec_convert_rhs (tree, tree, gimple *);
67extern tree chrec_convert_aggressive (tree, tree, bool *);
68
69/* Operations.  */
70extern tree chrec_apply (unsigned, tree, tree);
71extern tree chrec_apply_map (tree, vec<tree> );
72extern tree chrec_replace_initial_condition (tree, tree);
73extern tree initial_condition (tree);
74extern tree initial_condition_in_loop_num (tree, unsigned);
75extern tree evolution_part_in_loop_num (tree, unsigned);
76extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
77extern tree reset_evolution_in_loop (unsigned, tree, tree);
78extern tree chrec_merge (tree, tree);
79extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
80extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
81				 bool, tree = NULL);
82
83/* Observers.  */
84extern bool eq_evolutions_p (const_tree, const_tree);
85extern bool is_multivariate_chrec (const_tree);
86extern bool chrec_contains_symbols (const_tree, class loop * = NULL);
87extern bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned);
88extern bool chrec_contains_undetermined (const_tree);
89extern bool tree_contains_chrecs (const_tree, int *);
90extern bool evolution_function_is_affine_multivariate_p (const_tree, int);
91extern bool evolution_function_is_univariate_p (const_tree, int = 0);
92extern unsigned nb_vars_in_chrec (tree);
93extern bool evolution_function_is_invariant_p (tree, int);
94extern bool scev_is_linear_expression (tree);
95extern bool evolution_function_right_is_integer_cst (const_tree);
96
97/* Determines whether CHREC is equal to zero.  */
98
99static inline bool
100chrec_zerop (const_tree chrec)
101{
102  if (chrec == NULL_TREE)
103    return false;
104
105  if (TREE_CODE (chrec) == INTEGER_CST)
106    return integer_zerop (chrec);
107
108  return false;
109}
110
111/* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
112   Set the result in RES and return true when the property can be computed.  */
113
114static inline bool
115no_evolution_in_loop_p (tree chrec, unsigned loop_num, bool *res)
116{
117  tree scev;
118
119  if (chrec == chrec_not_analyzed_yet
120      || chrec == chrec_dont_know
121      || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
122    return false;
123
124  STRIP_NOPS (chrec);
125  scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
126  *res = !tree_contains_chrecs (scev, NULL);
127  return true;
128}
129
130/* Build a polynomial chain of recurrence.  */
131
132static inline tree
133build_polynomial_chrec (unsigned loop_num,
134			tree left,
135			tree right)
136{
137  bool val;
138
139  if (left == chrec_dont_know
140      || right == chrec_dont_know)
141    return chrec_dont_know;
142
143  if (!no_evolution_in_loop_p (left, loop_num, &val)
144      || !val)
145    return chrec_dont_know;
146
147  /* Types of left and right sides of a chrec should be compatible, but
148     pointer CHRECs are special in that the evolution is of ptroff type.  */
149  if (POINTER_TYPE_P (TREE_TYPE (left)))
150    gcc_checking_assert (ptrofftype_p (TREE_TYPE (right)));
151  else
152    {
153      /* Pointer types should occur only on the left hand side, i.e. in
154	 the base of the chrec, and not in the step.  */
155      gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (right))
156			   && types_compatible_p (TREE_TYPE (left),
157						  TREE_TYPE (right)));
158    }
159
160  if (chrec_zerop (right))
161    return left;
162
163  tree chrec = build2 (POLYNOMIAL_CHREC, TREE_TYPE (left), left, right);
164  CHREC_VARIABLE (chrec) = loop_num;
165  return chrec;
166}
167
168/* Determines whether the expression CHREC is a constant.  */
169
170static inline bool
171evolution_function_is_constant_p (const_tree chrec)
172{
173  if (chrec == NULL_TREE)
174    return false;
175
176  return is_gimple_min_invariant (chrec);
177}
178
179/* Determine whether CHREC is an affine evolution function in LOOPNUM.  */
180
181static inline bool
182evolution_function_is_affine_in_loop (const_tree chrec, int loopnum)
183{
184  if (chrec == NULL_TREE)
185    return false;
186
187  switch (TREE_CODE (chrec))
188    {
189    case POLYNOMIAL_CHREC:
190      if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum)
191	  && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum))
192	return true;
193      else
194	return false;
195
196    default:
197      return false;
198    }
199}
200
201/* Determine whether CHREC is an affine evolution function or not.  */
202
203static inline bool
204evolution_function_is_affine_p (const_tree chrec)
205{
206  return chrec
207    && TREE_CODE (chrec) == POLYNOMIAL_CHREC
208    && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
209					  CHREC_VARIABLE (chrec))
210    && (TREE_CODE (CHREC_RIGHT (chrec)) != POLYNOMIAL_CHREC
211	|| evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
212}
213
214/* Determines whether EXPR does not contains chrec expressions.  */
215
216static inline bool
217tree_does_not_contain_chrecs (const_tree expr)
218{
219  return !tree_contains_chrecs (expr, NULL);
220}
221
222/* Returns the type of the chrec.  */
223
224static inline tree
225chrec_type (const_tree chrec)
226{
227  if (automatically_generated_chrec_p (chrec))
228    return NULL_TREE;
229
230  return TREE_TYPE (chrec);
231}
232
233static inline tree
234chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1)
235{
236  switch (code)
237    {
238    case PLUS_EXPR:
239      return chrec_fold_plus (type, op0, op1);
240
241    case MINUS_EXPR:
242      return chrec_fold_minus (type, op0, op1);
243
244    case MULT_EXPR:
245      return chrec_fold_multiply (type, op0, op1);
246
247    default:
248      gcc_unreachable ();
249    }
250
251}
252
253#endif  /* GCC_TREE_CHREC_H  */
254