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