1 |
280 |
jeremybenn |
/* Chains of recurrences.
|
2 |
|
|
Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
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 |
|
|
/* This file implements operations on chains of recurrences. Chains
|
23 |
|
|
of recurrences are used for modeling evolution functions of scalar
|
24 |
|
|
variables.
|
25 |
|
|
*/
|
26 |
|
|
|
27 |
|
|
#include "config.h"
|
28 |
|
|
#include "system.h"
|
29 |
|
|
#include "coretypes.h"
|
30 |
|
|
#include "tm.h"
|
31 |
|
|
#include "ggc.h"
|
32 |
|
|
#include "tree.h"
|
33 |
|
|
#include "real.h"
|
34 |
|
|
#include "diagnostic.h"
|
35 |
|
|
#include "cfgloop.h"
|
36 |
|
|
#include "tree-flow.h"
|
37 |
|
|
#include "tree-chrec.h"
|
38 |
|
|
#include "tree-pass.h"
|
39 |
|
|
#include "params.h"
|
40 |
|
|
#include "flags.h"
|
41 |
|
|
#include "tree-scalar-evolution.h"
|
42 |
|
|
|
43 |
|
|
|
44 |
|
|
|
45 |
|
|
/* Extended folder for chrecs. */
|
46 |
|
|
|
47 |
|
|
/* Determines whether CST is not a constant evolution. */
|
48 |
|
|
|
49 |
|
|
static inline bool
|
50 |
|
|
is_not_constant_evolution (const_tree cst)
|
51 |
|
|
{
|
52 |
|
|
return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
|
53 |
|
|
}
|
54 |
|
|
|
55 |
|
|
/* Fold CODE for a polynomial function and a constant. */
|
56 |
|
|
|
57 |
|
|
static inline tree
|
58 |
|
|
chrec_fold_poly_cst (enum tree_code code,
|
59 |
|
|
tree type,
|
60 |
|
|
tree poly,
|
61 |
|
|
tree cst)
|
62 |
|
|
{
|
63 |
|
|
gcc_assert (poly);
|
64 |
|
|
gcc_assert (cst);
|
65 |
|
|
gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
|
66 |
|
|
gcc_assert (!is_not_constant_evolution (cst));
|
67 |
|
|
gcc_assert (type == chrec_type (poly));
|
68 |
|
|
|
69 |
|
|
switch (code)
|
70 |
|
|
{
|
71 |
|
|
case PLUS_EXPR:
|
72 |
|
|
return build_polynomial_chrec
|
73 |
|
|
(CHREC_VARIABLE (poly),
|
74 |
|
|
chrec_fold_plus (type, CHREC_LEFT (poly), cst),
|
75 |
|
|
CHREC_RIGHT (poly));
|
76 |
|
|
|
77 |
|
|
case MINUS_EXPR:
|
78 |
|
|
return build_polynomial_chrec
|
79 |
|
|
(CHREC_VARIABLE (poly),
|
80 |
|
|
chrec_fold_minus (type, CHREC_LEFT (poly), cst),
|
81 |
|
|
CHREC_RIGHT (poly));
|
82 |
|
|
|
83 |
|
|
case MULT_EXPR:
|
84 |
|
|
return build_polynomial_chrec
|
85 |
|
|
(CHREC_VARIABLE (poly),
|
86 |
|
|
chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
|
87 |
|
|
chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
|
88 |
|
|
|
89 |
|
|
default:
|
90 |
|
|
return chrec_dont_know;
|
91 |
|
|
}
|
92 |
|
|
}
|
93 |
|
|
|
94 |
|
|
/* Fold the addition of two polynomial functions. */
|
95 |
|
|
|
96 |
|
|
static inline tree
|
97 |
|
|
chrec_fold_plus_poly_poly (enum tree_code code,
|
98 |
|
|
tree type,
|
99 |
|
|
tree poly0,
|
100 |
|
|
tree poly1)
|
101 |
|
|
{
|
102 |
|
|
tree left, right;
|
103 |
|
|
struct loop *loop0 = get_chrec_loop (poly0);
|
104 |
|
|
struct loop *loop1 = get_chrec_loop (poly1);
|
105 |
|
|
tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;
|
106 |
|
|
|
107 |
|
|
gcc_assert (poly0);
|
108 |
|
|
gcc_assert (poly1);
|
109 |
|
|
gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
|
110 |
|
|
gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
|
111 |
|
|
if (POINTER_TYPE_P (chrec_type (poly0)))
|
112 |
|
|
gcc_assert (chrec_type (poly1) == sizetype);
|
113 |
|
|
else
|
114 |
|
|
gcc_assert (chrec_type (poly0) == chrec_type (poly1));
|
115 |
|
|
gcc_assert (type == chrec_type (poly0));
|
116 |
|
|
|
117 |
|
|
/*
|
118 |
|
|
{a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
|
119 |
|
|
{a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
|
120 |
|
|
{a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
|
121 |
|
|
if (flow_loop_nested_p (loop0, loop1))
|
122 |
|
|
{
|
123 |
|
|
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
124 |
|
|
return build_polynomial_chrec
|
125 |
|
|
(CHREC_VARIABLE (poly1),
|
126 |
|
|
chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
|
127 |
|
|
CHREC_RIGHT (poly1));
|
128 |
|
|
else
|
129 |
|
|
return build_polynomial_chrec
|
130 |
|
|
(CHREC_VARIABLE (poly1),
|
131 |
|
|
chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
|
132 |
|
|
chrec_fold_multiply (type, CHREC_RIGHT (poly1),
|
133 |
|
|
SCALAR_FLOAT_TYPE_P (type)
|
134 |
|
|
? build_real (type, dconstm1)
|
135 |
|
|
: build_int_cst_type (type, -1)));
|
136 |
|
|
}
|
137 |
|
|
|
138 |
|
|
if (flow_loop_nested_p (loop1, loop0))
|
139 |
|
|
{
|
140 |
|
|
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
141 |
|
|
return build_polynomial_chrec
|
142 |
|
|
(CHREC_VARIABLE (poly0),
|
143 |
|
|
chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
|
144 |
|
|
CHREC_RIGHT (poly0));
|
145 |
|
|
else
|
146 |
|
|
return build_polynomial_chrec
|
147 |
|
|
(CHREC_VARIABLE (poly0),
|
148 |
|
|
chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
|
149 |
|
|
CHREC_RIGHT (poly0));
|
150 |
|
|
}
|
151 |
|
|
|
152 |
|
|
/* This function should never be called for chrecs of loops that
|
153 |
|
|
do not belong to the same loop nest. */
|
154 |
|
|
gcc_assert (loop0 == loop1);
|
155 |
|
|
|
156 |
|
|
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
157 |
|
|
{
|
158 |
|
|
left = chrec_fold_plus
|
159 |
|
|
(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
160 |
|
|
right = chrec_fold_plus
|
161 |
|
|
(rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
162 |
|
|
}
|
163 |
|
|
else
|
164 |
|
|
{
|
165 |
|
|
left = chrec_fold_minus
|
166 |
|
|
(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
167 |
|
|
right = chrec_fold_minus
|
168 |
|
|
(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
169 |
|
|
}
|
170 |
|
|
|
171 |
|
|
if (chrec_zerop (right))
|
172 |
|
|
return left;
|
173 |
|
|
else
|
174 |
|
|
return build_polynomial_chrec
|
175 |
|
|
(CHREC_VARIABLE (poly0), left, right);
|
176 |
|
|
}
|
177 |
|
|
|
178 |
|
|
|
179 |
|
|
|
180 |
|
|
/* Fold the multiplication of two polynomial functions. */
|
181 |
|
|
|
182 |
|
|
static inline tree
|
183 |
|
|
chrec_fold_multiply_poly_poly (tree type,
|
184 |
|
|
tree poly0,
|
185 |
|
|
tree poly1)
|
186 |
|
|
{
|
187 |
|
|
tree t0, t1, t2;
|
188 |
|
|
int var;
|
189 |
|
|
struct loop *loop0 = get_chrec_loop (poly0);
|
190 |
|
|
struct loop *loop1 = get_chrec_loop (poly1);
|
191 |
|
|
|
192 |
|
|
gcc_assert (poly0);
|
193 |
|
|
gcc_assert (poly1);
|
194 |
|
|
gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
|
195 |
|
|
gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
|
196 |
|
|
gcc_assert (chrec_type (poly0) == chrec_type (poly1));
|
197 |
|
|
gcc_assert (type == chrec_type (poly0));
|
198 |
|
|
|
199 |
|
|
/* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
|
200 |
|
|
{a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
|
201 |
|
|
{a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
|
202 |
|
|
if (flow_loop_nested_p (loop0, loop1))
|
203 |
|
|
/* poly0 is a constant wrt. poly1. */
|
204 |
|
|
return build_polynomial_chrec
|
205 |
|
|
(CHREC_VARIABLE (poly1),
|
206 |
|
|
chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
|
207 |
|
|
CHREC_RIGHT (poly1));
|
208 |
|
|
|
209 |
|
|
if (flow_loop_nested_p (loop1, loop0))
|
210 |
|
|
/* poly1 is a constant wrt. poly0. */
|
211 |
|
|
return build_polynomial_chrec
|
212 |
|
|
(CHREC_VARIABLE (poly0),
|
213 |
|
|
chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
|
214 |
|
|
CHREC_RIGHT (poly0));
|
215 |
|
|
|
216 |
|
|
gcc_assert (loop0 == loop1);
|
217 |
|
|
|
218 |
|
|
/* poly0 and poly1 are two polynomials in the same variable,
|
219 |
|
|
{a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
|
220 |
|
|
|
221 |
|
|
/* "a*c". */
|
222 |
|
|
t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
|
223 |
|
|
|
224 |
|
|
/* "a*d + b*c". */
|
225 |
|
|
t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
|
226 |
|
|
t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
|
227 |
|
|
CHREC_RIGHT (poly0),
|
228 |
|
|
CHREC_LEFT (poly1)));
|
229 |
|
|
/* "b*d". */
|
230 |
|
|
t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
|
231 |
|
|
/* "a*d + b*c + b*d". */
|
232 |
|
|
t1 = chrec_fold_plus (type, t1, t2);
|
233 |
|
|
/* "2*b*d". */
|
234 |
|
|
t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
|
235 |
|
|
? build_real (type, dconst2)
|
236 |
|
|
: build_int_cst (type, 2), t2);
|
237 |
|
|
|
238 |
|
|
var = CHREC_VARIABLE (poly0);
|
239 |
|
|
return build_polynomial_chrec (var, t0,
|
240 |
|
|
build_polynomial_chrec (var, t1, t2));
|
241 |
|
|
}
|
242 |
|
|
|
243 |
|
|
/* When the operands are automatically_generated_chrec_p, the fold has
|
244 |
|
|
to respect the semantics of the operands. */
|
245 |
|
|
|
246 |
|
|
static inline tree
|
247 |
|
|
chrec_fold_automatically_generated_operands (tree op0,
|
248 |
|
|
tree op1)
|
249 |
|
|
{
|
250 |
|
|
if (op0 == chrec_dont_know
|
251 |
|
|
|| op1 == chrec_dont_know)
|
252 |
|
|
return chrec_dont_know;
|
253 |
|
|
|
254 |
|
|
if (op0 == chrec_known
|
255 |
|
|
|| op1 == chrec_known)
|
256 |
|
|
return chrec_known;
|
257 |
|
|
|
258 |
|
|
if (op0 == chrec_not_analyzed_yet
|
259 |
|
|
|| op1 == chrec_not_analyzed_yet)
|
260 |
|
|
return chrec_not_analyzed_yet;
|
261 |
|
|
|
262 |
|
|
/* The default case produces a safe result. */
|
263 |
|
|
return chrec_dont_know;
|
264 |
|
|
}
|
265 |
|
|
|
266 |
|
|
/* Fold the addition of two chrecs. */
|
267 |
|
|
|
268 |
|
|
static tree
|
269 |
|
|
chrec_fold_plus_1 (enum tree_code code, tree type,
|
270 |
|
|
tree op0, tree op1)
|
271 |
|
|
{
|
272 |
|
|
tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
|
273 |
|
|
|
274 |
|
|
if (automatically_generated_chrec_p (op0)
|
275 |
|
|
|| automatically_generated_chrec_p (op1))
|
276 |
|
|
return chrec_fold_automatically_generated_operands (op0, op1);
|
277 |
|
|
|
278 |
|
|
switch (TREE_CODE (op0))
|
279 |
|
|
{
|
280 |
|
|
case POLYNOMIAL_CHREC:
|
281 |
|
|
switch (TREE_CODE (op1))
|
282 |
|
|
{
|
283 |
|
|
case POLYNOMIAL_CHREC:
|
284 |
|
|
return chrec_fold_plus_poly_poly (code, type, op0, op1);
|
285 |
|
|
|
286 |
|
|
CASE_CONVERT:
|
287 |
|
|
if (tree_contains_chrecs (op1, NULL))
|
288 |
|
|
return chrec_dont_know;
|
289 |
|
|
|
290 |
|
|
default:
|
291 |
|
|
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
292 |
|
|
return build_polynomial_chrec
|
293 |
|
|
(CHREC_VARIABLE (op0),
|
294 |
|
|
chrec_fold_plus (type, CHREC_LEFT (op0), op1),
|
295 |
|
|
CHREC_RIGHT (op0));
|
296 |
|
|
else
|
297 |
|
|
return build_polynomial_chrec
|
298 |
|
|
(CHREC_VARIABLE (op0),
|
299 |
|
|
chrec_fold_minus (type, CHREC_LEFT (op0), op1),
|
300 |
|
|
CHREC_RIGHT (op0));
|
301 |
|
|
}
|
302 |
|
|
|
303 |
|
|
CASE_CONVERT:
|
304 |
|
|
if (tree_contains_chrecs (op0, NULL))
|
305 |
|
|
return chrec_dont_know;
|
306 |
|
|
|
307 |
|
|
default:
|
308 |
|
|
switch (TREE_CODE (op1))
|
309 |
|
|
{
|
310 |
|
|
case POLYNOMIAL_CHREC:
|
311 |
|
|
if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
|
312 |
|
|
return build_polynomial_chrec
|
313 |
|
|
(CHREC_VARIABLE (op1),
|
314 |
|
|
chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
|
315 |
|
|
CHREC_RIGHT (op1));
|
316 |
|
|
else
|
317 |
|
|
return build_polynomial_chrec
|
318 |
|
|
(CHREC_VARIABLE (op1),
|
319 |
|
|
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
|
320 |
|
|
chrec_fold_multiply (type, CHREC_RIGHT (op1),
|
321 |
|
|
SCALAR_FLOAT_TYPE_P (type)
|
322 |
|
|
? build_real (type, dconstm1)
|
323 |
|
|
: build_int_cst_type (type, -1)));
|
324 |
|
|
|
325 |
|
|
CASE_CONVERT:
|
326 |
|
|
if (tree_contains_chrecs (op1, NULL))
|
327 |
|
|
return chrec_dont_know;
|
328 |
|
|
|
329 |
|
|
default:
|
330 |
|
|
{
|
331 |
|
|
int size = 0;
|
332 |
|
|
if ((tree_contains_chrecs (op0, &size)
|
333 |
|
|
|| tree_contains_chrecs (op1, &size))
|
334 |
|
|
&& size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
|
335 |
|
|
return build2 (code, type, op0, op1);
|
336 |
|
|
else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
|
337 |
|
|
return fold_build2 (code, type,
|
338 |
|
|
fold_convert (type, op0),
|
339 |
|
|
fold_convert (op1_type, op1));
|
340 |
|
|
else
|
341 |
|
|
return chrec_dont_know;
|
342 |
|
|
}
|
343 |
|
|
}
|
344 |
|
|
}
|
345 |
|
|
}
|
346 |
|
|
|
347 |
|
|
/* Fold the addition of two chrecs. */
|
348 |
|
|
|
349 |
|
|
tree
|
350 |
|
|
chrec_fold_plus (tree type,
|
351 |
|
|
tree op0,
|
352 |
|
|
tree op1)
|
353 |
|
|
{
|
354 |
|
|
enum tree_code code;
|
355 |
|
|
if (automatically_generated_chrec_p (op0)
|
356 |
|
|
|| automatically_generated_chrec_p (op1))
|
357 |
|
|
return chrec_fold_automatically_generated_operands (op0, op1);
|
358 |
|
|
|
359 |
|
|
if (integer_zerop (op0))
|
360 |
|
|
return chrec_convert (type, op1, NULL);
|
361 |
|
|
if (integer_zerop (op1))
|
362 |
|
|
return chrec_convert (type, op0, NULL);
|
363 |
|
|
|
364 |
|
|
if (POINTER_TYPE_P (type))
|
365 |
|
|
code = POINTER_PLUS_EXPR;
|
366 |
|
|
else
|
367 |
|
|
code = PLUS_EXPR;
|
368 |
|
|
|
369 |
|
|
return chrec_fold_plus_1 (code, type, op0, op1);
|
370 |
|
|
}
|
371 |
|
|
|
372 |
|
|
/* Fold the subtraction of two chrecs. */
|
373 |
|
|
|
374 |
|
|
tree
|
375 |
|
|
chrec_fold_minus (tree type,
|
376 |
|
|
tree op0,
|
377 |
|
|
tree op1)
|
378 |
|
|
{
|
379 |
|
|
if (automatically_generated_chrec_p (op0)
|
380 |
|
|
|| automatically_generated_chrec_p (op1))
|
381 |
|
|
return chrec_fold_automatically_generated_operands (op0, op1);
|
382 |
|
|
|
383 |
|
|
if (integer_zerop (op1))
|
384 |
|
|
return op0;
|
385 |
|
|
|
386 |
|
|
return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
|
387 |
|
|
}
|
388 |
|
|
|
389 |
|
|
/* Fold the multiplication of two chrecs. */
|
390 |
|
|
|
391 |
|
|
tree
|
392 |
|
|
chrec_fold_multiply (tree type,
|
393 |
|
|
tree op0,
|
394 |
|
|
tree op1)
|
395 |
|
|
{
|
396 |
|
|
if (automatically_generated_chrec_p (op0)
|
397 |
|
|
|| automatically_generated_chrec_p (op1))
|
398 |
|
|
return chrec_fold_automatically_generated_operands (op0, op1);
|
399 |
|
|
|
400 |
|
|
switch (TREE_CODE (op0))
|
401 |
|
|
{
|
402 |
|
|
case POLYNOMIAL_CHREC:
|
403 |
|
|
switch (TREE_CODE (op1))
|
404 |
|
|
{
|
405 |
|
|
case POLYNOMIAL_CHREC:
|
406 |
|
|
return chrec_fold_multiply_poly_poly (type, op0, op1);
|
407 |
|
|
|
408 |
|
|
CASE_CONVERT:
|
409 |
|
|
if (tree_contains_chrecs (op1, NULL))
|
410 |
|
|
return chrec_dont_know;
|
411 |
|
|
|
412 |
|
|
default:
|
413 |
|
|
if (integer_onep (op1))
|
414 |
|
|
return op0;
|
415 |
|
|
if (integer_zerop (op1))
|
416 |
|
|
return build_int_cst (type, 0);
|
417 |
|
|
|
418 |
|
|
return build_polynomial_chrec
|
419 |
|
|
(CHREC_VARIABLE (op0),
|
420 |
|
|
chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
|
421 |
|
|
chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
|
422 |
|
|
}
|
423 |
|
|
|
424 |
|
|
CASE_CONVERT:
|
425 |
|
|
if (tree_contains_chrecs (op0, NULL))
|
426 |
|
|
return chrec_dont_know;
|
427 |
|
|
|
428 |
|
|
default:
|
429 |
|
|
if (integer_onep (op0))
|
430 |
|
|
return op1;
|
431 |
|
|
|
432 |
|
|
if (integer_zerop (op0))
|
433 |
|
|
return build_int_cst (type, 0);
|
434 |
|
|
|
435 |
|
|
switch (TREE_CODE (op1))
|
436 |
|
|
{
|
437 |
|
|
case POLYNOMIAL_CHREC:
|
438 |
|
|
return build_polynomial_chrec
|
439 |
|
|
(CHREC_VARIABLE (op1),
|
440 |
|
|
chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
|
441 |
|
|
chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
|
442 |
|
|
|
443 |
|
|
CASE_CONVERT:
|
444 |
|
|
if (tree_contains_chrecs (op1, NULL))
|
445 |
|
|
return chrec_dont_know;
|
446 |
|
|
|
447 |
|
|
default:
|
448 |
|
|
if (integer_onep (op1))
|
449 |
|
|
return op0;
|
450 |
|
|
if (integer_zerop (op1))
|
451 |
|
|
return build_int_cst (type, 0);
|
452 |
|
|
return fold_build2 (MULT_EXPR, type, op0, op1);
|
453 |
|
|
}
|
454 |
|
|
}
|
455 |
|
|
}
|
456 |
|
|
|
457 |
|
|
|
458 |
|
|
|
459 |
|
|
/* Operations. */
|
460 |
|
|
|
461 |
|
|
/* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
|
462 |
|
|
calculation overflows, otherwise return C(n,k) with type TYPE. */
|
463 |
|
|
|
464 |
|
|
static tree
|
465 |
|
|
tree_fold_binomial (tree type, tree n, unsigned int k)
|
466 |
|
|
{
|
467 |
|
|
unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
|
468 |
|
|
HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
|
469 |
|
|
unsigned int i;
|
470 |
|
|
tree res;
|
471 |
|
|
|
472 |
|
|
/* Handle the most frequent cases. */
|
473 |
|
|
if (k == 0)
|
474 |
|
|
return build_int_cst (type, 1);
|
475 |
|
|
if (k == 1)
|
476 |
|
|
return fold_convert (type, n);
|
477 |
|
|
|
478 |
|
|
/* Check that k <= n. */
|
479 |
|
|
if (TREE_INT_CST_HIGH (n) == 0
|
480 |
|
|
&& TREE_INT_CST_LOW (n) < k)
|
481 |
|
|
return NULL_TREE;
|
482 |
|
|
|
483 |
|
|
/* Numerator = n. */
|
484 |
|
|
lnum = TREE_INT_CST_LOW (n);
|
485 |
|
|
hnum = TREE_INT_CST_HIGH (n);
|
486 |
|
|
|
487 |
|
|
/* Denominator = 2. */
|
488 |
|
|
ldenom = 2;
|
489 |
|
|
hdenom = 0;
|
490 |
|
|
|
491 |
|
|
/* Index = Numerator-1. */
|
492 |
|
|
if (lnum == 0)
|
493 |
|
|
{
|
494 |
|
|
hidx = hnum - 1;
|
495 |
|
|
lidx = ~ (unsigned HOST_WIDE_INT) 0;
|
496 |
|
|
}
|
497 |
|
|
else
|
498 |
|
|
{
|
499 |
|
|
hidx = hnum;
|
500 |
|
|
lidx = lnum - 1;
|
501 |
|
|
}
|
502 |
|
|
|
503 |
|
|
/* Numerator = Numerator*Index = n*(n-1). */
|
504 |
|
|
if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
|
505 |
|
|
return NULL_TREE;
|
506 |
|
|
|
507 |
|
|
for (i = 3; i <= k; i++)
|
508 |
|
|
{
|
509 |
|
|
/* Index--. */
|
510 |
|
|
if (lidx == 0)
|
511 |
|
|
{
|
512 |
|
|
hidx--;
|
513 |
|
|
lidx = ~ (unsigned HOST_WIDE_INT) 0;
|
514 |
|
|
}
|
515 |
|
|
else
|
516 |
|
|
lidx--;
|
517 |
|
|
|
518 |
|
|
/* Numerator *= Index. */
|
519 |
|
|
if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
|
520 |
|
|
return NULL_TREE;
|
521 |
|
|
|
522 |
|
|
/* Denominator *= i. */
|
523 |
|
|
mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
|
524 |
|
|
}
|
525 |
|
|
|
526 |
|
|
/* Result = Numerator / Denominator. */
|
527 |
|
|
div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
|
528 |
|
|
&lres, &hres, &ldum, &hdum);
|
529 |
|
|
|
530 |
|
|
res = build_int_cst_wide (type, lres, hres);
|
531 |
|
|
return int_fits_type_p (res, type) ? res : NULL_TREE;
|
532 |
|
|
}
|
533 |
|
|
|
534 |
|
|
/* Helper function. Use the Newton's interpolating formula for
|
535 |
|
|
evaluating the value of the evolution function. */
|
536 |
|
|
|
537 |
|
|
static tree
|
538 |
|
|
chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
|
539 |
|
|
{
|
540 |
|
|
tree arg0, arg1, binomial_n_k;
|
541 |
|
|
tree type = TREE_TYPE (chrec);
|
542 |
|
|
struct loop *var_loop = get_loop (var);
|
543 |
|
|
|
544 |
|
|
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
545 |
|
|
&& flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
|
546 |
|
|
chrec = CHREC_LEFT (chrec);
|
547 |
|
|
|
548 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
549 |
|
|
&& CHREC_VARIABLE (chrec) == var)
|
550 |
|
|
{
|
551 |
|
|
arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
|
552 |
|
|
if (arg1 == chrec_dont_know)
|
553 |
|
|
return chrec_dont_know;
|
554 |
|
|
binomial_n_k = tree_fold_binomial (type, n, k);
|
555 |
|
|
if (!binomial_n_k)
|
556 |
|
|
return chrec_dont_know;
|
557 |
|
|
arg0 = fold_build2 (MULT_EXPR, type,
|
558 |
|
|
CHREC_LEFT (chrec), binomial_n_k);
|
559 |
|
|
return chrec_fold_plus (type, arg0, arg1);
|
560 |
|
|
}
|
561 |
|
|
|
562 |
|
|
binomial_n_k = tree_fold_binomial (type, n, k);
|
563 |
|
|
if (!binomial_n_k)
|
564 |
|
|
return chrec_dont_know;
|
565 |
|
|
|
566 |
|
|
return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
|
567 |
|
|
}
|
568 |
|
|
|
569 |
|
|
/* Evaluates "CHREC (X)" when the varying variable is VAR.
|
570 |
|
|
Example: Given the following parameters,
|
571 |
|
|
|
572 |
|
|
var = 1
|
573 |
|
|
chrec = {3, +, 4}_1
|
574 |
|
|
x = 10
|
575 |
|
|
|
576 |
|
|
The result is given by the Newton's interpolating formula:
|
577 |
|
|
3 * \binom{10}{0} + 4 * \binom{10}{1}.
|
578 |
|
|
*/
|
579 |
|
|
|
580 |
|
|
tree
|
581 |
|
|
chrec_apply (unsigned var,
|
582 |
|
|
tree chrec,
|
583 |
|
|
tree x)
|
584 |
|
|
{
|
585 |
|
|
tree type = chrec_type (chrec);
|
586 |
|
|
tree res = chrec_dont_know;
|
587 |
|
|
|
588 |
|
|
if (automatically_generated_chrec_p (chrec)
|
589 |
|
|
|| automatically_generated_chrec_p (x)
|
590 |
|
|
|
591 |
|
|
/* When the symbols are defined in an outer loop, it is possible
|
592 |
|
|
to symbolically compute the apply, since the symbols are
|
593 |
|
|
constants with respect to the varying loop. */
|
594 |
|
|
|| chrec_contains_symbols_defined_in_loop (chrec, var))
|
595 |
|
|
return chrec_dont_know;
|
596 |
|
|
|
597 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
598 |
|
|
fprintf (dump_file, "(chrec_apply \n");
|
599 |
|
|
|
600 |
|
|
if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
|
601 |
|
|
x = build_real_from_int_cst (type, x);
|
602 |
|
|
|
603 |
|
|
if (evolution_function_is_affine_p (chrec))
|
604 |
|
|
{
|
605 |
|
|
/* "{a, +, b} (x)" -> "a + b*x". */
|
606 |
|
|
x = chrec_convert_rhs (type, x, NULL);
|
607 |
|
|
res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
|
608 |
|
|
res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
|
609 |
|
|
}
|
610 |
|
|
|
611 |
|
|
else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
|
612 |
|
|
res = chrec;
|
613 |
|
|
|
614 |
|
|
else if (TREE_CODE (x) == INTEGER_CST
|
615 |
|
|
&& tree_int_cst_sgn (x) == 1)
|
616 |
|
|
/* testsuite/.../ssa-chrec-38.c. */
|
617 |
|
|
res = chrec_evaluate (var, chrec, x, 0);
|
618 |
|
|
else
|
619 |
|
|
res = chrec_dont_know;
|
620 |
|
|
|
621 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
622 |
|
|
{
|
623 |
|
|
fprintf (dump_file, " (varying_loop = %d\n", var);
|
624 |
|
|
fprintf (dump_file, ")\n (chrec = ");
|
625 |
|
|
print_generic_expr (dump_file, chrec, 0);
|
626 |
|
|
fprintf (dump_file, ")\n (x = ");
|
627 |
|
|
print_generic_expr (dump_file, x, 0);
|
628 |
|
|
fprintf (dump_file, ")\n (res = ");
|
629 |
|
|
print_generic_expr (dump_file, res, 0);
|
630 |
|
|
fprintf (dump_file, "))\n");
|
631 |
|
|
}
|
632 |
|
|
|
633 |
|
|
return res;
|
634 |
|
|
}
|
635 |
|
|
|
636 |
|
|
/* Replaces the initial condition in CHREC with INIT_COND. */
|
637 |
|
|
|
638 |
|
|
tree
|
639 |
|
|
chrec_replace_initial_condition (tree chrec,
|
640 |
|
|
tree init_cond)
|
641 |
|
|
{
|
642 |
|
|
if (automatically_generated_chrec_p (chrec))
|
643 |
|
|
return chrec;
|
644 |
|
|
|
645 |
|
|
gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
|
646 |
|
|
|
647 |
|
|
switch (TREE_CODE (chrec))
|
648 |
|
|
{
|
649 |
|
|
case POLYNOMIAL_CHREC:
|
650 |
|
|
return build_polynomial_chrec
|
651 |
|
|
(CHREC_VARIABLE (chrec),
|
652 |
|
|
chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
|
653 |
|
|
CHREC_RIGHT (chrec));
|
654 |
|
|
|
655 |
|
|
default:
|
656 |
|
|
return init_cond;
|
657 |
|
|
}
|
658 |
|
|
}
|
659 |
|
|
|
660 |
|
|
/* Returns the initial condition of a given CHREC. */
|
661 |
|
|
|
662 |
|
|
tree
|
663 |
|
|
initial_condition (tree chrec)
|
664 |
|
|
{
|
665 |
|
|
if (automatically_generated_chrec_p (chrec))
|
666 |
|
|
return chrec;
|
667 |
|
|
|
668 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
669 |
|
|
return initial_condition (CHREC_LEFT (chrec));
|
670 |
|
|
else
|
671 |
|
|
return chrec;
|
672 |
|
|
}
|
673 |
|
|
|
674 |
|
|
/* Returns a univariate function that represents the evolution in
|
675 |
|
|
LOOP_NUM. Mask the evolution of any other loop. */
|
676 |
|
|
|
677 |
|
|
tree
|
678 |
|
|
hide_evolution_in_other_loops_than_loop (tree chrec,
|
679 |
|
|
unsigned loop_num)
|
680 |
|
|
{
|
681 |
|
|
struct loop *loop = get_loop (loop_num), *chloop;
|
682 |
|
|
if (automatically_generated_chrec_p (chrec))
|
683 |
|
|
return chrec;
|
684 |
|
|
|
685 |
|
|
switch (TREE_CODE (chrec))
|
686 |
|
|
{
|
687 |
|
|
case POLYNOMIAL_CHREC:
|
688 |
|
|
chloop = get_chrec_loop (chrec);
|
689 |
|
|
|
690 |
|
|
if (chloop == loop)
|
691 |
|
|
return build_polynomial_chrec
|
692 |
|
|
(loop_num,
|
693 |
|
|
hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
|
694 |
|
|
loop_num),
|
695 |
|
|
CHREC_RIGHT (chrec));
|
696 |
|
|
|
697 |
|
|
else if (flow_loop_nested_p (chloop, loop))
|
698 |
|
|
/* There is no evolution in this loop. */
|
699 |
|
|
return initial_condition (chrec);
|
700 |
|
|
|
701 |
|
|
else
|
702 |
|
|
{
|
703 |
|
|
gcc_assert (flow_loop_nested_p (loop, chloop));
|
704 |
|
|
return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
|
705 |
|
|
loop_num);
|
706 |
|
|
}
|
707 |
|
|
|
708 |
|
|
default:
|
709 |
|
|
return chrec;
|
710 |
|
|
}
|
711 |
|
|
}
|
712 |
|
|
|
713 |
|
|
/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
|
714 |
|
|
true, otherwise returns the initial condition in LOOP_NUM. */
|
715 |
|
|
|
716 |
|
|
static tree
|
717 |
|
|
chrec_component_in_loop_num (tree chrec,
|
718 |
|
|
unsigned loop_num,
|
719 |
|
|
bool right)
|
720 |
|
|
{
|
721 |
|
|
tree component;
|
722 |
|
|
struct loop *loop = get_loop (loop_num), *chloop;
|
723 |
|
|
|
724 |
|
|
if (automatically_generated_chrec_p (chrec))
|
725 |
|
|
return chrec;
|
726 |
|
|
|
727 |
|
|
switch (TREE_CODE (chrec))
|
728 |
|
|
{
|
729 |
|
|
case POLYNOMIAL_CHREC:
|
730 |
|
|
chloop = get_chrec_loop (chrec);
|
731 |
|
|
|
732 |
|
|
if (chloop == loop)
|
733 |
|
|
{
|
734 |
|
|
if (right)
|
735 |
|
|
component = CHREC_RIGHT (chrec);
|
736 |
|
|
else
|
737 |
|
|
component = CHREC_LEFT (chrec);
|
738 |
|
|
|
739 |
|
|
if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
|
740 |
|
|
|| CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
|
741 |
|
|
return component;
|
742 |
|
|
|
743 |
|
|
else
|
744 |
|
|
return build_polynomial_chrec
|
745 |
|
|
(loop_num,
|
746 |
|
|
chrec_component_in_loop_num (CHREC_LEFT (chrec),
|
747 |
|
|
loop_num,
|
748 |
|
|
right),
|
749 |
|
|
component);
|
750 |
|
|
}
|
751 |
|
|
|
752 |
|
|
else if (flow_loop_nested_p (chloop, loop))
|
753 |
|
|
/* There is no evolution part in this loop. */
|
754 |
|
|
return NULL_TREE;
|
755 |
|
|
|
756 |
|
|
else
|
757 |
|
|
{
|
758 |
|
|
gcc_assert (flow_loop_nested_p (loop, chloop));
|
759 |
|
|
return chrec_component_in_loop_num (CHREC_LEFT (chrec),
|
760 |
|
|
loop_num,
|
761 |
|
|
right);
|
762 |
|
|
}
|
763 |
|
|
|
764 |
|
|
default:
|
765 |
|
|
if (right)
|
766 |
|
|
return NULL_TREE;
|
767 |
|
|
else
|
768 |
|
|
return chrec;
|
769 |
|
|
}
|
770 |
|
|
}
|
771 |
|
|
|
772 |
|
|
/* Returns the evolution part in LOOP_NUM. Example: the call
|
773 |
|
|
evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
|
774 |
|
|
{1, +, 2}_1 */
|
775 |
|
|
|
776 |
|
|
tree
|
777 |
|
|
evolution_part_in_loop_num (tree chrec,
|
778 |
|
|
unsigned loop_num)
|
779 |
|
|
{
|
780 |
|
|
return chrec_component_in_loop_num (chrec, loop_num, true);
|
781 |
|
|
}
|
782 |
|
|
|
783 |
|
|
/* Returns the initial condition in LOOP_NUM. Example: the call
|
784 |
|
|
initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
|
785 |
|
|
{0, +, 1}_1 */
|
786 |
|
|
|
787 |
|
|
tree
|
788 |
|
|
initial_condition_in_loop_num (tree chrec,
|
789 |
|
|
unsigned loop_num)
|
790 |
|
|
{
|
791 |
|
|
return chrec_component_in_loop_num (chrec, loop_num, false);
|
792 |
|
|
}
|
793 |
|
|
|
794 |
|
|
/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
|
795 |
|
|
This function is essentially used for setting the evolution to
|
796 |
|
|
chrec_dont_know, for example after having determined that it is
|
797 |
|
|
impossible to say how many times a loop will execute. */
|
798 |
|
|
|
799 |
|
|
tree
|
800 |
|
|
reset_evolution_in_loop (unsigned loop_num,
|
801 |
|
|
tree chrec,
|
802 |
|
|
tree new_evol)
|
803 |
|
|
{
|
804 |
|
|
struct loop *loop = get_loop (loop_num);
|
805 |
|
|
|
806 |
|
|
if (POINTER_TYPE_P (chrec_type (chrec)))
|
807 |
|
|
gcc_assert (sizetype == chrec_type (new_evol));
|
808 |
|
|
else
|
809 |
|
|
gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
|
810 |
|
|
|
811 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
812 |
|
|
&& flow_loop_nested_p (loop, get_chrec_loop (chrec)))
|
813 |
|
|
{
|
814 |
|
|
tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
|
815 |
|
|
new_evol);
|
816 |
|
|
tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
|
817 |
|
|
new_evol);
|
818 |
|
|
return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
|
819 |
|
|
build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
|
820 |
|
|
left, right);
|
821 |
|
|
}
|
822 |
|
|
|
823 |
|
|
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
|
824 |
|
|
&& CHREC_VARIABLE (chrec) == loop_num)
|
825 |
|
|
chrec = CHREC_LEFT (chrec);
|
826 |
|
|
|
827 |
|
|
return build_polynomial_chrec (loop_num, chrec, new_evol);
|
828 |
|
|
}
|
829 |
|
|
|
830 |
|
|
/* Merges two evolution functions that were found by following two
|
831 |
|
|
alternate paths of a conditional expression. */
|
832 |
|
|
|
833 |
|
|
tree
|
834 |
|
|
chrec_merge (tree chrec1,
|
835 |
|
|
tree chrec2)
|
836 |
|
|
{
|
837 |
|
|
if (chrec1 == chrec_dont_know
|
838 |
|
|
|| chrec2 == chrec_dont_know)
|
839 |
|
|
return chrec_dont_know;
|
840 |
|
|
|
841 |
|
|
if (chrec1 == chrec_known
|
842 |
|
|
|| chrec2 == chrec_known)
|
843 |
|
|
return chrec_known;
|
844 |
|
|
|
845 |
|
|
if (chrec1 == chrec_not_analyzed_yet)
|
846 |
|
|
return chrec2;
|
847 |
|
|
if (chrec2 == chrec_not_analyzed_yet)
|
848 |
|
|
return chrec1;
|
849 |
|
|
|
850 |
|
|
if (eq_evolutions_p (chrec1, chrec2))
|
851 |
|
|
return chrec1;
|
852 |
|
|
|
853 |
|
|
return chrec_dont_know;
|
854 |
|
|
}
|
855 |
|
|
|
856 |
|
|
|
857 |
|
|
|
858 |
|
|
/* Observers. */
|
859 |
|
|
|
860 |
|
|
/* Helper function for is_multivariate_chrec. */
|
861 |
|
|
|
862 |
|
|
static bool
|
863 |
|
|
is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
|
864 |
|
|
{
|
865 |
|
|
if (chrec == NULL_TREE)
|
866 |
|
|
return false;
|
867 |
|
|
|
868 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
869 |
|
|
{
|
870 |
|
|
if (CHREC_VARIABLE (chrec) != rec_var)
|
871 |
|
|
return true;
|
872 |
|
|
else
|
873 |
|
|
return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
|
874 |
|
|
|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
|
875 |
|
|
}
|
876 |
|
|
else
|
877 |
|
|
return false;
|
878 |
|
|
}
|
879 |
|
|
|
880 |
|
|
/* Determine whether the given chrec is multivariate or not. */
|
881 |
|
|
|
882 |
|
|
bool
|
883 |
|
|
is_multivariate_chrec (const_tree chrec)
|
884 |
|
|
{
|
885 |
|
|
if (chrec == NULL_TREE)
|
886 |
|
|
return false;
|
887 |
|
|
|
888 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
889 |
|
|
return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
|
890 |
|
|
CHREC_VARIABLE (chrec))
|
891 |
|
|
|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
|
892 |
|
|
CHREC_VARIABLE (chrec)));
|
893 |
|
|
else
|
894 |
|
|
return false;
|
895 |
|
|
}
|
896 |
|
|
|
897 |
|
|
/* Determines whether the chrec contains symbolic names or not. */
|
898 |
|
|
|
899 |
|
|
bool
|
900 |
|
|
chrec_contains_symbols (const_tree chrec)
|
901 |
|
|
{
|
902 |
|
|
int i, n;
|
903 |
|
|
|
904 |
|
|
if (chrec == NULL_TREE)
|
905 |
|
|
return false;
|
906 |
|
|
|
907 |
|
|
if (TREE_CODE (chrec) == SSA_NAME
|
908 |
|
|
|| TREE_CODE (chrec) == VAR_DECL
|
909 |
|
|
|| TREE_CODE (chrec) == PARM_DECL
|
910 |
|
|
|| TREE_CODE (chrec) == FUNCTION_DECL
|
911 |
|
|
|| TREE_CODE (chrec) == LABEL_DECL
|
912 |
|
|
|| TREE_CODE (chrec) == RESULT_DECL
|
913 |
|
|
|| TREE_CODE (chrec) == FIELD_DECL)
|
914 |
|
|
return true;
|
915 |
|
|
|
916 |
|
|
n = TREE_OPERAND_LENGTH (chrec);
|
917 |
|
|
for (i = 0; i < n; i++)
|
918 |
|
|
if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
|
919 |
|
|
return true;
|
920 |
|
|
return false;
|
921 |
|
|
}
|
922 |
|
|
|
923 |
|
|
/* Determines whether the chrec contains undetermined coefficients. */
|
924 |
|
|
|
925 |
|
|
bool
|
926 |
|
|
chrec_contains_undetermined (const_tree chrec)
|
927 |
|
|
{
|
928 |
|
|
int i, n;
|
929 |
|
|
|
930 |
|
|
if (chrec == chrec_dont_know)
|
931 |
|
|
return true;
|
932 |
|
|
|
933 |
|
|
if (chrec == NULL_TREE)
|
934 |
|
|
return false;
|
935 |
|
|
|
936 |
|
|
n = TREE_OPERAND_LENGTH (chrec);
|
937 |
|
|
for (i = 0; i < n; i++)
|
938 |
|
|
if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
|
939 |
|
|
return true;
|
940 |
|
|
return false;
|
941 |
|
|
}
|
942 |
|
|
|
943 |
|
|
/* Determines whether the tree EXPR contains chrecs, and increment
|
944 |
|
|
SIZE if it is not a NULL pointer by an estimation of the depth of
|
945 |
|
|
the tree. */
|
946 |
|
|
|
947 |
|
|
bool
|
948 |
|
|
tree_contains_chrecs (const_tree expr, int *size)
|
949 |
|
|
{
|
950 |
|
|
int i, n;
|
951 |
|
|
|
952 |
|
|
if (expr == NULL_TREE)
|
953 |
|
|
return false;
|
954 |
|
|
|
955 |
|
|
if (size)
|
956 |
|
|
(*size)++;
|
957 |
|
|
|
958 |
|
|
if (tree_is_chrec (expr))
|
959 |
|
|
return true;
|
960 |
|
|
|
961 |
|
|
n = TREE_OPERAND_LENGTH (expr);
|
962 |
|
|
for (i = 0; i < n; i++)
|
963 |
|
|
if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
|
964 |
|
|
return true;
|
965 |
|
|
return false;
|
966 |
|
|
}
|
967 |
|
|
|
968 |
|
|
/* Recursive helper function. */
|
969 |
|
|
|
970 |
|
|
static bool
|
971 |
|
|
evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
|
972 |
|
|
{
|
973 |
|
|
if (evolution_function_is_constant_p (chrec))
|
974 |
|
|
return true;
|
975 |
|
|
|
976 |
|
|
if (TREE_CODE (chrec) == SSA_NAME
|
977 |
|
|
&& (loopnum == 0
|
978 |
|
|
|| expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
|
979 |
|
|
return true;
|
980 |
|
|
|
981 |
|
|
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
|
982 |
|
|
{
|
983 |
|
|
if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
|
984 |
|
|
|| !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
|
985 |
|
|
loopnum)
|
986 |
|
|
|| !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
|
987 |
|
|
loopnum))
|
988 |
|
|
return false;
|
989 |
|
|
return true;
|
990 |
|
|
}
|
991 |
|
|
|
992 |
|
|
switch (TREE_OPERAND_LENGTH (chrec))
|
993 |
|
|
{
|
994 |
|
|
case 2:
|
995 |
|
|
if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
|
996 |
|
|
loopnum))
|
997 |
|
|
return false;
|
998 |
|
|
|
999 |
|
|
case 1:
|
1000 |
|
|
if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
|
1001 |
|
|
loopnum))
|
1002 |
|
|
return false;
|
1003 |
|
|
return true;
|
1004 |
|
|
|
1005 |
|
|
default:
|
1006 |
|
|
return false;
|
1007 |
|
|
}
|
1008 |
|
|
|
1009 |
|
|
return false;
|
1010 |
|
|
}
|
1011 |
|
|
|
1012 |
|
|
/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
|
1013 |
|
|
|
1014 |
|
|
bool
|
1015 |
|
|
evolution_function_is_invariant_p (tree chrec, int loopnum)
|
1016 |
|
|
{
|
1017 |
|
|
return evolution_function_is_invariant_rec_p (chrec, loopnum);
|
1018 |
|
|
}
|
1019 |
|
|
|
1020 |
|
|
/* Determine whether the given tree is an affine multivariate
|
1021 |
|
|
evolution. */
|
1022 |
|
|
|
1023 |
|
|
bool
|
1024 |
|
|
evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
|
1025 |
|
|
{
|
1026 |
|
|
if (chrec == NULL_TREE)
|
1027 |
|
|
return false;
|
1028 |
|
|
|
1029 |
|
|
switch (TREE_CODE (chrec))
|
1030 |
|
|
{
|
1031 |
|
|
case POLYNOMIAL_CHREC:
|
1032 |
|
|
if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
|
1033 |
|
|
{
|
1034 |
|
|
if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
|
1035 |
|
|
return true;
|
1036 |
|
|
else
|
1037 |
|
|
{
|
1038 |
|
|
if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
|
1039 |
|
|
&& CHREC_VARIABLE (CHREC_RIGHT (chrec))
|
1040 |
|
|
!= CHREC_VARIABLE (chrec)
|
1041 |
|
|
&& evolution_function_is_affine_multivariate_p
|
1042 |
|
|
(CHREC_RIGHT (chrec), loopnum))
|
1043 |
|
|
return true;
|
1044 |
|
|
else
|
1045 |
|
|
return false;
|
1046 |
|
|
}
|
1047 |
|
|
}
|
1048 |
|
|
else
|
1049 |
|
|
{
|
1050 |
|
|
if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
|
1051 |
|
|
&& TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
|
1052 |
|
|
&& CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
|
1053 |
|
|
&& evolution_function_is_affine_multivariate_p
|
1054 |
|
|
(CHREC_LEFT (chrec), loopnum))
|
1055 |
|
|
return true;
|
1056 |
|
|
else
|
1057 |
|
|
return false;
|
1058 |
|
|
}
|
1059 |
|
|
|
1060 |
|
|
default:
|
1061 |
|
|
return false;
|
1062 |
|
|
}
|
1063 |
|
|
}
|
1064 |
|
|
|
1065 |
|
|
/* Determine whether the given tree is a function in zero or one
|
1066 |
|
|
variables. */
|
1067 |
|
|
|
1068 |
|
|
bool
|
1069 |
|
|
evolution_function_is_univariate_p (const_tree chrec)
|
1070 |
|
|
{
|
1071 |
|
|
if (chrec == NULL_TREE)
|
1072 |
|
|
return true;
|
1073 |
|
|
|
1074 |
|
|
switch (TREE_CODE (chrec))
|
1075 |
|
|
{
|
1076 |
|
|
case POLYNOMIAL_CHREC:
|
1077 |
|
|
switch (TREE_CODE (CHREC_LEFT (chrec)))
|
1078 |
|
|
{
|
1079 |
|
|
case POLYNOMIAL_CHREC:
|
1080 |
|
|
if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
|
1081 |
|
|
return false;
|
1082 |
|
|
if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
|
1083 |
|
|
return false;
|
1084 |
|
|
break;
|
1085 |
|
|
|
1086 |
|
|
default:
|
1087 |
|
|
break;
|
1088 |
|
|
}
|
1089 |
|
|
|
1090 |
|
|
switch (TREE_CODE (CHREC_RIGHT (chrec)))
|
1091 |
|
|
{
|
1092 |
|
|
case POLYNOMIAL_CHREC:
|
1093 |
|
|
if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
|
1094 |
|
|
return false;
|
1095 |
|
|
if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
|
1096 |
|
|
return false;
|
1097 |
|
|
break;
|
1098 |
|
|
|
1099 |
|
|
default:
|
1100 |
|
|
break;
|
1101 |
|
|
}
|
1102 |
|
|
|
1103 |
|
|
default:
|
1104 |
|
|
return true;
|
1105 |
|
|
}
|
1106 |
|
|
}
|
1107 |
|
|
|
1108 |
|
|
/* Returns the number of variables of CHREC. Example: the call
|
1109 |
|
|
nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
|
1110 |
|
|
|
1111 |
|
|
unsigned
|
1112 |
|
|
nb_vars_in_chrec (tree chrec)
|
1113 |
|
|
{
|
1114 |
|
|
if (chrec == NULL_TREE)
|
1115 |
|
|
return 0;
|
1116 |
|
|
|
1117 |
|
|
switch (TREE_CODE (chrec))
|
1118 |
|
|
{
|
1119 |
|
|
case POLYNOMIAL_CHREC:
|
1120 |
|
|
return 1 + nb_vars_in_chrec
|
1121 |
|
|
(initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
|
1122 |
|
|
|
1123 |
|
|
default:
|
1124 |
|
|
return 0;
|
1125 |
|
|
}
|
1126 |
|
|
}
|
1127 |
|
|
|
1128 |
|
|
static tree chrec_convert_1 (tree, tree, gimple, bool);
|
1129 |
|
|
|
1130 |
|
|
/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
|
1131 |
|
|
the scev corresponds to. AT_STMT is the statement at that the scev is
|
1132 |
|
|
evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
1133 |
|
|
the rules for overflow of the given language apply (e.g., that signed
|
1134 |
|
|
arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
|
1135 |
|
|
tests, but also to enforce that the result follows them. Returns true if the
|
1136 |
|
|
conversion succeeded, false otherwise. */
|
1137 |
|
|
|
1138 |
|
|
bool
|
1139 |
|
|
convert_affine_scev (struct loop *loop, tree type,
|
1140 |
|
|
tree *base, tree *step, gimple at_stmt,
|
1141 |
|
|
bool use_overflow_semantics)
|
1142 |
|
|
{
|
1143 |
|
|
tree ct = TREE_TYPE (*step);
|
1144 |
|
|
bool enforce_overflow_semantics;
|
1145 |
|
|
bool must_check_src_overflow, must_check_rslt_overflow;
|
1146 |
|
|
tree new_base, new_step;
|
1147 |
|
|
tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
|
1148 |
|
|
|
1149 |
|
|
/* In general,
|
1150 |
|
|
(TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
|
1151 |
|
|
but we must check some assumptions.
|
1152 |
|
|
|
1153 |
|
|
1) If [BASE, +, STEP] wraps, the equation is not valid when precision
|
1154 |
|
|
of CT is smaller than the precision of TYPE. For example, when we
|
1155 |
|
|
cast unsigned char [254, +, 1] to unsigned, the values on left side
|
1156 |
|
|
are 254, 255, 0, 1, ..., but those on the right side are
|
1157 |
|
|
254, 255, 256, 257, ...
|
1158 |
|
|
2) In case that we must also preserve the fact that signed ivs do not
|
1159 |
|
|
overflow, we must additionally check that the new iv does not wrap.
|
1160 |
|
|
For example, unsigned char [125, +, 1] casted to signed char could
|
1161 |
|
|
become a wrapping variable with values 125, 126, 127, -128, -127, ...,
|
1162 |
|
|
which would confuse optimizers that assume that this does not
|
1163 |
|
|
happen. */
|
1164 |
|
|
must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
|
1165 |
|
|
|
1166 |
|
|
enforce_overflow_semantics = (use_overflow_semantics
|
1167 |
|
|
&& nowrap_type_p (type));
|
1168 |
|
|
if (enforce_overflow_semantics)
|
1169 |
|
|
{
|
1170 |
|
|
/* We can avoid checking whether the result overflows in the following
|
1171 |
|
|
cases:
|
1172 |
|
|
|
1173 |
|
|
-- must_check_src_overflow is true, and the range of TYPE is superset
|
1174 |
|
|
of the range of CT -- i.e., in all cases except if CT signed and
|
1175 |
|
|
TYPE unsigned.
|
1176 |
|
|
-- both CT and TYPE have the same precision and signedness, and we
|
1177 |
|
|
verify instead that the source does not overflow (this may be
|
1178 |
|
|
easier than verifying it for the result, as we may use the
|
1179 |
|
|
information about the semantics of overflow in CT). */
|
1180 |
|
|
if (must_check_src_overflow)
|
1181 |
|
|
{
|
1182 |
|
|
if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
|
1183 |
|
|
must_check_rslt_overflow = true;
|
1184 |
|
|
else
|
1185 |
|
|
must_check_rslt_overflow = false;
|
1186 |
|
|
}
|
1187 |
|
|
else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
|
1188 |
|
|
&& TYPE_PRECISION (ct) == TYPE_PRECISION (type))
|
1189 |
|
|
{
|
1190 |
|
|
must_check_rslt_overflow = false;
|
1191 |
|
|
must_check_src_overflow = true;
|
1192 |
|
|
}
|
1193 |
|
|
else
|
1194 |
|
|
must_check_rslt_overflow = true;
|
1195 |
|
|
}
|
1196 |
|
|
else
|
1197 |
|
|
must_check_rslt_overflow = false;
|
1198 |
|
|
|
1199 |
|
|
if (must_check_src_overflow
|
1200 |
|
|
&& scev_probably_wraps_p (*base, *step, at_stmt, loop,
|
1201 |
|
|
use_overflow_semantics))
|
1202 |
|
|
return false;
|
1203 |
|
|
|
1204 |
|
|
new_base = chrec_convert_1 (type, *base, at_stmt,
|
1205 |
|
|
use_overflow_semantics);
|
1206 |
|
|
/* The step must be sign extended, regardless of the signedness
|
1207 |
|
|
of CT and TYPE. This only needs to be handled specially when
|
1208 |
|
|
CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
|
1209 |
|
|
(with values 100, 99, 98, ...) from becoming signed or unsigned
|
1210 |
|
|
[100, +, 255] with values 100, 355, ...; the sign-extension is
|
1211 |
|
|
performed by default when CT is signed. */
|
1212 |
|
|
new_step = *step;
|
1213 |
|
|
if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
|
1214 |
|
|
new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
|
1215 |
|
|
use_overflow_semantics);
|
1216 |
|
|
new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
|
1217 |
|
|
|
1218 |
|
|
if (automatically_generated_chrec_p (new_base)
|
1219 |
|
|
|| automatically_generated_chrec_p (new_step))
|
1220 |
|
|
return false;
|
1221 |
|
|
|
1222 |
|
|
if (must_check_rslt_overflow
|
1223 |
|
|
/* Note that in this case we cannot use the fact that signed variables
|
1224 |
|
|
do not overflow, as this is what we are verifying for the new iv. */
|
1225 |
|
|
&& scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
|
1226 |
|
|
return false;
|
1227 |
|
|
|
1228 |
|
|
*base = new_base;
|
1229 |
|
|
*step = new_step;
|
1230 |
|
|
return true;
|
1231 |
|
|
}
|
1232 |
|
|
|
1233 |
|
|
|
1234 |
|
|
/* Convert CHREC for the right hand side of a CREC.
|
1235 |
|
|
The increment for a pointer type is always sizetype. */
|
1236 |
|
|
tree
|
1237 |
|
|
chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
|
1238 |
|
|
{
|
1239 |
|
|
if (POINTER_TYPE_P (type))
|
1240 |
|
|
type = sizetype;
|
1241 |
|
|
return chrec_convert (type, chrec, at_stmt);
|
1242 |
|
|
}
|
1243 |
|
|
|
1244 |
|
|
/* Convert CHREC to TYPE. When the analyzer knows the context in
|
1245 |
|
|
which the CHREC is built, it sets AT_STMT to the statement that
|
1246 |
|
|
contains the definition of the analyzed variable, otherwise the
|
1247 |
|
|
conversion is less accurate: the information is used for
|
1248 |
|
|
determining a more accurate estimation of the number of iterations.
|
1249 |
|
|
By default AT_STMT could be safely set to NULL_TREE.
|
1250 |
|
|
|
1251 |
|
|
The following rule is always true: TREE_TYPE (chrec) ==
|
1252 |
|
|
TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
|
1253 |
|
|
An example of what could happen when adding two chrecs and the type
|
1254 |
|
|
of the CHREC_RIGHT is different than CHREC_LEFT is:
|
1255 |
|
|
|
1256 |
|
|
{(uint) 0, +, (uchar) 10} +
|
1257 |
|
|
{(uint) 0, +, (uchar) 250}
|
1258 |
|
|
|
1259 |
|
|
that would produce a wrong result if CHREC_RIGHT is not (uint):
|
1260 |
|
|
|
1261 |
|
|
{(uint) 0, +, (uchar) 4}
|
1262 |
|
|
|
1263 |
|
|
instead of
|
1264 |
|
|
|
1265 |
|
|
{(uint) 0, +, (uint) 260}
|
1266 |
|
|
*/
|
1267 |
|
|
|
1268 |
|
|
tree
|
1269 |
|
|
chrec_convert (tree type, tree chrec, gimple at_stmt)
|
1270 |
|
|
{
|
1271 |
|
|
return chrec_convert_1 (type, chrec, at_stmt, true);
|
1272 |
|
|
}
|
1273 |
|
|
|
1274 |
|
|
/* Convert CHREC to TYPE. When the analyzer knows the context in
|
1275 |
|
|
which the CHREC is built, it sets AT_STMT to the statement that
|
1276 |
|
|
contains the definition of the analyzed variable, otherwise the
|
1277 |
|
|
conversion is less accurate: the information is used for
|
1278 |
|
|
determining a more accurate estimation of the number of iterations.
|
1279 |
|
|
By default AT_STMT could be safely set to NULL_TREE.
|
1280 |
|
|
|
1281 |
|
|
USE_OVERFLOW_SEMANTICS is true if this function should assume that
|
1282 |
|
|
the rules for overflow of the given language apply (e.g., that signed
|
1283 |
|
|
arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
|
1284 |
|
|
tests, but also to enforce that the result follows them. */
|
1285 |
|
|
|
1286 |
|
|
static tree
|
1287 |
|
|
chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
|
1288 |
|
|
bool use_overflow_semantics)
|
1289 |
|
|
{
|
1290 |
|
|
tree ct, res;
|
1291 |
|
|
tree base, step;
|
1292 |
|
|
struct loop *loop;
|
1293 |
|
|
|
1294 |
|
|
if (automatically_generated_chrec_p (chrec))
|
1295 |
|
|
return chrec;
|
1296 |
|
|
|
1297 |
|
|
ct = chrec_type (chrec);
|
1298 |
|
|
if (ct == type)
|
1299 |
|
|
return chrec;
|
1300 |
|
|
|
1301 |
|
|
if (!evolution_function_is_affine_p (chrec))
|
1302 |
|
|
goto keep_cast;
|
1303 |
|
|
|
1304 |
|
|
loop = get_chrec_loop (chrec);
|
1305 |
|
|
base = CHREC_LEFT (chrec);
|
1306 |
|
|
step = CHREC_RIGHT (chrec);
|
1307 |
|
|
|
1308 |
|
|
if (convert_affine_scev (loop, type, &base, &step, at_stmt,
|
1309 |
|
|
use_overflow_semantics))
|
1310 |
|
|
return build_polynomial_chrec (loop->num, base, step);
|
1311 |
|
|
|
1312 |
|
|
/* If we cannot propagate the cast inside the chrec, just keep the cast. */
|
1313 |
|
|
keep_cast:
|
1314 |
|
|
/* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
|
1315 |
|
|
may be more expensive. We do want to perform this optimization here
|
1316 |
|
|
though for canonicalization reasons. */
|
1317 |
|
|
if (use_overflow_semantics
|
1318 |
|
|
&& (TREE_CODE (chrec) == PLUS_EXPR
|
1319 |
|
|
|| TREE_CODE (chrec) == MINUS_EXPR)
|
1320 |
|
|
&& TREE_CODE (type) == INTEGER_TYPE
|
1321 |
|
|
&& TREE_CODE (ct) == INTEGER_TYPE
|
1322 |
|
|
&& TYPE_PRECISION (type) > TYPE_PRECISION (ct)
|
1323 |
|
|
&& TYPE_OVERFLOW_UNDEFINED (ct))
|
1324 |
|
|
res = fold_build2 (TREE_CODE (chrec), type,
|
1325 |
|
|
fold_convert (type, TREE_OPERAND (chrec, 0)),
|
1326 |
|
|
fold_convert (type, TREE_OPERAND (chrec, 1)));
|
1327 |
|
|
else
|
1328 |
|
|
res = fold_convert (type, chrec);
|
1329 |
|
|
|
1330 |
|
|
/* Don't propagate overflows. */
|
1331 |
|
|
if (CONSTANT_CLASS_P (res))
|
1332 |
|
|
TREE_OVERFLOW (res) = 0;
|
1333 |
|
|
|
1334 |
|
|
/* But reject constants that don't fit in their type after conversion.
|
1335 |
|
|
This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
|
1336 |
|
|
natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
|
1337 |
|
|
and can cause problems later when computing niters of loops. Note
|
1338 |
|
|
that we don't do the check before converting because we don't want
|
1339 |
|
|
to reject conversions of negative chrecs to unsigned types. */
|
1340 |
|
|
if (TREE_CODE (res) == INTEGER_CST
|
1341 |
|
|
&& TREE_CODE (type) == INTEGER_TYPE
|
1342 |
|
|
&& !int_fits_type_p (res, type))
|
1343 |
|
|
res = chrec_dont_know;
|
1344 |
|
|
|
1345 |
|
|
return res;
|
1346 |
|
|
}
|
1347 |
|
|
|
1348 |
|
|
/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
|
1349 |
|
|
chrec if something else than what chrec_convert would do happens, NULL_TREE
|
1350 |
|
|
otherwise. */
|
1351 |
|
|
|
1352 |
|
|
tree
|
1353 |
|
|
chrec_convert_aggressive (tree type, tree chrec)
|
1354 |
|
|
{
|
1355 |
|
|
tree inner_type, left, right, lc, rc, rtype;
|
1356 |
|
|
|
1357 |
|
|
if (automatically_generated_chrec_p (chrec)
|
1358 |
|
|
|| TREE_CODE (chrec) != POLYNOMIAL_CHREC)
|
1359 |
|
|
return NULL_TREE;
|
1360 |
|
|
|
1361 |
|
|
inner_type = TREE_TYPE (chrec);
|
1362 |
|
|
if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
|
1363 |
|
|
return NULL_TREE;
|
1364 |
|
|
|
1365 |
|
|
rtype = POINTER_TYPE_P (type) ? sizetype : type;
|
1366 |
|
|
|
1367 |
|
|
left = CHREC_LEFT (chrec);
|
1368 |
|
|
right = CHREC_RIGHT (chrec);
|
1369 |
|
|
lc = chrec_convert_aggressive (type, left);
|
1370 |
|
|
if (!lc)
|
1371 |
|
|
lc = chrec_convert (type, left, NULL);
|
1372 |
|
|
rc = chrec_convert_aggressive (rtype, right);
|
1373 |
|
|
if (!rc)
|
1374 |
|
|
rc = chrec_convert (rtype, right, NULL);
|
1375 |
|
|
|
1376 |
|
|
return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
|
1377 |
|
|
}
|
1378 |
|
|
|
1379 |
|
|
/* Returns true when CHREC0 == CHREC1. */
|
1380 |
|
|
|
1381 |
|
|
bool
|
1382 |
|
|
eq_evolutions_p (const_tree chrec0, const_tree chrec1)
|
1383 |
|
|
{
|
1384 |
|
|
if (chrec0 == NULL_TREE
|
1385 |
|
|
|| chrec1 == NULL_TREE
|
1386 |
|
|
|| TREE_CODE (chrec0) != TREE_CODE (chrec1))
|
1387 |
|
|
return false;
|
1388 |
|
|
|
1389 |
|
|
if (chrec0 == chrec1)
|
1390 |
|
|
return true;
|
1391 |
|
|
|
1392 |
|
|
switch (TREE_CODE (chrec0))
|
1393 |
|
|
{
|
1394 |
|
|
case INTEGER_CST:
|
1395 |
|
|
return operand_equal_p (chrec0, chrec1, 0);
|
1396 |
|
|
|
1397 |
|
|
case POLYNOMIAL_CHREC:
|
1398 |
|
|
return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
|
1399 |
|
|
&& eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
|
1400 |
|
|
&& eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
|
1401 |
|
|
default:
|
1402 |
|
|
return false;
|
1403 |
|
|
}
|
1404 |
|
|
}
|
1405 |
|
|
|
1406 |
|
|
/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
|
1407 |
|
|
EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
|
1408 |
|
|
which of these cases happens. */
|
1409 |
|
|
|
1410 |
|
|
enum ev_direction
|
1411 |
|
|
scev_direction (const_tree chrec)
|
1412 |
|
|
{
|
1413 |
|
|
const_tree step;
|
1414 |
|
|
|
1415 |
|
|
if (!evolution_function_is_affine_p (chrec))
|
1416 |
|
|
return EV_DIR_UNKNOWN;
|
1417 |
|
|
|
1418 |
|
|
step = CHREC_RIGHT (chrec);
|
1419 |
|
|
if (TREE_CODE (step) != INTEGER_CST)
|
1420 |
|
|
return EV_DIR_UNKNOWN;
|
1421 |
|
|
|
1422 |
|
|
if (tree_int_cst_sign_bit (step))
|
1423 |
|
|
return EV_DIR_DECREASES;
|
1424 |
|
|
else
|
1425 |
|
|
return EV_DIR_GROWS;
|
1426 |
|
|
}
|
1427 |
|
|
|
1428 |
|
|
/* Iterates over all the components of SCEV, and calls CBCK. */
|
1429 |
|
|
|
1430 |
|
|
void
|
1431 |
|
|
for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
|
1432 |
|
|
{
|
1433 |
|
|
switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
|
1434 |
|
|
{
|
1435 |
|
|
case 3:
|
1436 |
|
|
for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
|
1437 |
|
|
|
1438 |
|
|
case 2:
|
1439 |
|
|
for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
|
1440 |
|
|
|
1441 |
|
|
case 1:
|
1442 |
|
|
for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
|
1443 |
|
|
|
1444 |
|
|
default:
|
1445 |
|
|
cbck (scev, data);
|
1446 |
|
|
break;
|
1447 |
|
|
}
|
1448 |
|
|
}
|
1449 |
|
|
|
1450 |
|
|
/* Returns true when the operation can be part of a linear
|
1451 |
|
|
expression. */
|
1452 |
|
|
|
1453 |
|
|
static inline bool
|
1454 |
|
|
operator_is_linear (tree scev)
|
1455 |
|
|
{
|
1456 |
|
|
switch (TREE_CODE (scev))
|
1457 |
|
|
{
|
1458 |
|
|
case INTEGER_CST:
|
1459 |
|
|
case POLYNOMIAL_CHREC:
|
1460 |
|
|
case PLUS_EXPR:
|
1461 |
|
|
case POINTER_PLUS_EXPR:
|
1462 |
|
|
case MULT_EXPR:
|
1463 |
|
|
case MINUS_EXPR:
|
1464 |
|
|
case NEGATE_EXPR:
|
1465 |
|
|
case SSA_NAME:
|
1466 |
|
|
case NON_LVALUE_EXPR:
|
1467 |
|
|
case BIT_NOT_EXPR:
|
1468 |
|
|
CASE_CONVERT:
|
1469 |
|
|
return true;
|
1470 |
|
|
|
1471 |
|
|
default:
|
1472 |
|
|
return false;
|
1473 |
|
|
}
|
1474 |
|
|
}
|
1475 |
|
|
|
1476 |
|
|
/* Return true when SCEV is a linear expression. Linear expressions
|
1477 |
|
|
can contain additions, substractions and multiplications.
|
1478 |
|
|
Multiplications are restricted to constant scaling: "cst * x". */
|
1479 |
|
|
|
1480 |
|
|
bool
|
1481 |
|
|
scev_is_linear_expression (tree scev)
|
1482 |
|
|
{
|
1483 |
|
|
if (scev == NULL
|
1484 |
|
|
|| !operator_is_linear (scev))
|
1485 |
|
|
return false;
|
1486 |
|
|
|
1487 |
|
|
if (TREE_CODE (scev) == MULT_EXPR)
|
1488 |
|
|
return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
|
1489 |
|
|
&& tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
|
1490 |
|
|
|
1491 |
|
|
if (TREE_CODE (scev) == POLYNOMIAL_CHREC
|
1492 |
|
|
&& !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
|
1493 |
|
|
return false;
|
1494 |
|
|
|
1495 |
|
|
switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
|
1496 |
|
|
{
|
1497 |
|
|
case 3:
|
1498 |
|
|
return scev_is_linear_expression (TREE_OPERAND (scev, 0))
|
1499 |
|
|
&& scev_is_linear_expression (TREE_OPERAND (scev, 1))
|
1500 |
|
|
&& scev_is_linear_expression (TREE_OPERAND (scev, 2));
|
1501 |
|
|
|
1502 |
|
|
case 2:
|
1503 |
|
|
return scev_is_linear_expression (TREE_OPERAND (scev, 0))
|
1504 |
|
|
&& scev_is_linear_expression (TREE_OPERAND (scev, 1));
|
1505 |
|
|
|
1506 |
|
|
case 1:
|
1507 |
|
|
return scev_is_linear_expression (TREE_OPERAND (scev, 0));
|
1508 |
|
|
|
1509 |
|
|
case 0:
|
1510 |
|
|
return true;
|
1511 |
|
|
|
1512 |
|
|
default:
|
1513 |
|
|
return false;
|
1514 |
|
|
}
|
1515 |
|
|
}
|
1516 |
|
|
|
1517 |
|
|
/* Determines whether the expression CHREC contains only interger consts
|
1518 |
|
|
in the right parts. */
|
1519 |
|
|
|
1520 |
|
|
bool
|
1521 |
|
|
evolution_function_right_is_integer_cst (const_tree chrec)
|
1522 |
|
|
{
|
1523 |
|
|
if (chrec == NULL_TREE)
|
1524 |
|
|
return false;
|
1525 |
|
|
|
1526 |
|
|
switch (TREE_CODE (chrec))
|
1527 |
|
|
{
|
1528 |
|
|
case INTEGER_CST:
|
1529 |
|
|
return true;
|
1530 |
|
|
|
1531 |
|
|
case POLYNOMIAL_CHREC:
|
1532 |
|
|
return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
|
1533 |
|
|
&& (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
|
1534 |
|
|
|| evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
|
1535 |
|
|
|
1536 |
|
|
CASE_CONVERT:
|
1537 |
|
|
return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
|
1538 |
|
|
|
1539 |
|
|
default:
|
1540 |
|
|
return false;
|
1541 |
|
|
}
|
1542 |
|
|
}
|
1543 |
|
|
|