Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-niter.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 24 May 2010 12:47:05 +0900 |
parents | 77e2b8dfacca |
children | f6334be47118 |
rev | line source |
---|---|
0 | 1 /* Functions to determine/estimate number of iterations of a loop. |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Free Software Foundation, Inc. |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
4 |
0 | 5 This file is part of GCC. |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
6 |
0 | 7 GCC is free software; you can redistribute it and/or modify it |
8 under the terms of the GNU General Public License as published by the | |
9 Free Software Foundation; either version 3, or (at your option) any | |
10 later version. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
11 |
0 | 12 GCC is distributed in the hope that it will be useful, but WITHOUT |
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
16 |
0 | 17 You should have received a copy of the GNU General Public License |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
24 #include "tm.h" | |
25 #include "tree.h" | |
26 #include "tm_p.h" | |
27 #include "basic-block.h" | |
28 #include "output.h" | |
29 #include "diagnostic.h" | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
30 #include "tree-pretty-print.h" |
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
31 #include "gimple-pretty-print.h" |
0 | 32 #include "intl.h" |
33 #include "tree-flow.h" | |
34 #include "tree-dump.h" | |
35 #include "cfgloop.h" | |
36 #include "tree-pass.h" | |
37 #include "ggc.h" | |
38 #include "tree-chrec.h" | |
39 #include "tree-scalar-evolution.h" | |
40 #include "tree-data-ref.h" | |
41 #include "params.h" | |
42 #include "flags.h" | |
43 #include "toplev.h" | |
44 #include "tree-inline.h" | |
45 #include "gmp.h" | |
46 | |
47 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) | |
48 | |
49 /* The maximum number of dominator BBs we search for conditions | |
50 of loop header copies we use for simplifying a conditional | |
51 expression. */ | |
52 #define MAX_DOMINATORS_TO_WALK 8 | |
53 | |
54 /* | |
55 | |
56 Analysis of number of iterations of an affine exit test. | |
57 | |
58 */ | |
59 | |
60 /* Bounds on some value, BELOW <= X <= UP. */ | |
61 | |
62 typedef struct | |
63 { | |
64 mpz_t below, up; | |
65 } bounds; | |
66 | |
67 | |
68 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */ | |
69 | |
70 static void | |
71 split_to_var_and_offset (tree expr, tree *var, mpz_t offset) | |
72 { | |
73 tree type = TREE_TYPE (expr); | |
74 tree op0, op1; | |
75 double_int off; | |
76 bool negate = false; | |
77 | |
78 *var = expr; | |
79 mpz_set_ui (offset, 0); | |
80 | |
81 switch (TREE_CODE (expr)) | |
82 { | |
83 case MINUS_EXPR: | |
84 negate = true; | |
85 /* Fallthru. */ | |
86 | |
87 case PLUS_EXPR: | |
88 case POINTER_PLUS_EXPR: | |
89 op0 = TREE_OPERAND (expr, 0); | |
90 op1 = TREE_OPERAND (expr, 1); | |
91 | |
92 if (TREE_CODE (op1) != INTEGER_CST) | |
93 break; | |
94 | |
95 *var = op0; | |
96 /* Always sign extend the offset. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
97 off = tree_to_double_int (op1); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
98 if (negate) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
99 off = double_int_neg (off); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
100 off = double_int_sext (off, TYPE_PRECISION (type)); |
0 | 101 mpz_set_double_int (offset, off, false); |
102 break; | |
103 | |
104 case INTEGER_CST: | |
105 *var = build_int_cst_type (type, 0); | |
106 off = tree_to_double_int (expr); | |
107 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type)); | |
108 break; | |
109 | |
110 default: | |
111 break; | |
112 } | |
113 } | |
114 | |
115 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF | |
116 in TYPE to MIN and MAX. */ | |
117 | |
118 static void | |
119 determine_value_range (tree type, tree var, mpz_t off, | |
120 mpz_t min, mpz_t max) | |
121 { | |
122 /* If the expression is a constant, we know its value exactly. */ | |
123 if (integer_zerop (var)) | |
124 { | |
125 mpz_set (min, off); | |
126 mpz_set (max, off); | |
127 return; | |
128 } | |
129 | |
130 /* If the computation may wrap, we know nothing about the value, except for | |
131 the range of the type. */ | |
132 get_type_static_bounds (type, min, max); | |
133 if (!nowrap_type_p (type)) | |
134 return; | |
135 | |
136 /* Since the addition of OFF does not wrap, if OFF is positive, then we may | |
137 add it to MIN, otherwise to MAX. */ | |
138 if (mpz_sgn (off) < 0) | |
139 mpz_add (max, max, off); | |
140 else | |
141 mpz_add (min, min, off); | |
142 } | |
143 | |
144 /* Stores the bounds on the difference of the values of the expressions | |
145 (var + X) and (var + Y), computed in TYPE, to BNDS. */ | |
146 | |
147 static void | |
148 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, | |
149 bounds *bnds) | |
150 { | |
151 int rel = mpz_cmp (x, y); | |
152 bool may_wrap = !nowrap_type_p (type); | |
153 mpz_t m; | |
154 | |
155 /* If X == Y, then the expressions are always equal. | |
156 If X > Y, there are the following possibilities: | |
157 a) neither of var + X and var + Y overflow or underflow, or both of | |
158 them do. Then their difference is X - Y. | |
159 b) var + X overflows, and var + Y does not. Then the values of the | |
160 expressions are var + X - M and var + Y, where M is the range of | |
161 the type, and their difference is X - Y - M. | |
162 c) var + Y underflows and var + X does not. Their difference again | |
163 is M - X + Y. | |
164 Therefore, if the arithmetics in type does not overflow, then the | |
165 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y) | |
166 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or | |
167 (X - Y, X - Y + M). */ | |
168 | |
169 if (rel == 0) | |
170 { | |
171 mpz_set_ui (bnds->below, 0); | |
172 mpz_set_ui (bnds->up, 0); | |
173 return; | |
174 } | |
175 | |
176 mpz_init (m); | |
177 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true); | |
178 mpz_add_ui (m, m, 1); | |
179 mpz_sub (bnds->up, x, y); | |
180 mpz_set (bnds->below, bnds->up); | |
181 | |
182 if (may_wrap) | |
183 { | |
184 if (rel > 0) | |
185 mpz_sub (bnds->below, bnds->below, m); | |
186 else | |
187 mpz_add (bnds->up, bnds->up, m); | |
188 } | |
189 | |
190 mpz_clear (m); | |
191 } | |
192 | |
193 /* From condition C0 CMP C1 derives information regarding the | |
194 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, | |
195 and stores it to BNDS. */ | |
196 | |
197 static void | |
198 refine_bounds_using_guard (tree type, tree varx, mpz_t offx, | |
199 tree vary, mpz_t offy, | |
200 tree c0, enum tree_code cmp, tree c1, | |
201 bounds *bnds) | |
202 { | |
203 tree varc0, varc1, tmp, ctype; | |
204 mpz_t offc0, offc1, loffx, loffy, bnd; | |
205 bool lbound = false; | |
206 bool no_wrap = nowrap_type_p (type); | |
207 bool x_ok, y_ok; | |
208 | |
209 switch (cmp) | |
210 { | |
211 case LT_EXPR: | |
212 case LE_EXPR: | |
213 case GT_EXPR: | |
214 case GE_EXPR: | |
215 STRIP_SIGN_NOPS (c0); | |
216 STRIP_SIGN_NOPS (c1); | |
217 ctype = TREE_TYPE (c0); | |
218 if (!useless_type_conversion_p (ctype, type)) | |
219 return; | |
220 | |
221 break; | |
222 | |
223 case EQ_EXPR: | |
224 /* We could derive quite precise information from EQ_EXPR, however, such | |
225 a guard is unlikely to appear, so we do not bother with handling | |
226 it. */ | |
227 return; | |
228 | |
229 case NE_EXPR: | |
230 /* NE_EXPR comparisons do not contain much of useful information, except for | |
231 special case of comparing with the bounds of the type. */ | |
232 if (TREE_CODE (c1) != INTEGER_CST | |
233 || !INTEGRAL_TYPE_P (type)) | |
234 return; | |
235 | |
236 /* Ensure that the condition speaks about an expression in the same type | |
237 as X and Y. */ | |
238 ctype = TREE_TYPE (c0); | |
239 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type)) | |
240 return; | |
241 c0 = fold_convert (type, c0); | |
242 c1 = fold_convert (type, c1); | |
243 | |
244 if (TYPE_MIN_VALUE (type) | |
245 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0)) | |
246 { | |
247 cmp = GT_EXPR; | |
248 break; | |
249 } | |
250 if (TYPE_MAX_VALUE (type) | |
251 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0)) | |
252 { | |
253 cmp = LT_EXPR; | |
254 break; | |
255 } | |
256 | |
257 return; | |
258 default: | |
259 return; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
260 } |
0 | 261 |
262 mpz_init (offc0); | |
263 mpz_init (offc1); | |
264 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); | |
265 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); | |
266 | |
267 /* We are only interested in comparisons of expressions based on VARX and | |
268 VARY. TODO -- we might also be able to derive some bounds from | |
269 expressions containing just one of the variables. */ | |
270 | |
271 if (operand_equal_p (varx, varc1, 0)) | |
272 { | |
273 tmp = varc0; varc0 = varc1; varc1 = tmp; | |
274 mpz_swap (offc0, offc1); | |
275 cmp = swap_tree_comparison (cmp); | |
276 } | |
277 | |
278 if (!operand_equal_p (varx, varc0, 0) | |
279 || !operand_equal_p (vary, varc1, 0)) | |
280 goto end; | |
281 | |
282 mpz_init_set (loffx, offx); | |
283 mpz_init_set (loffy, offy); | |
284 | |
285 if (cmp == GT_EXPR || cmp == GE_EXPR) | |
286 { | |
287 tmp = varx; varx = vary; vary = tmp; | |
288 mpz_swap (offc0, offc1); | |
289 mpz_swap (loffx, loffy); | |
290 cmp = swap_tree_comparison (cmp); | |
291 lbound = true; | |
292 } | |
293 | |
294 /* If there is no overflow, the condition implies that | |
295 | |
296 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0). | |
297 | |
298 The overflows and underflows may complicate things a bit; each | |
299 overflow decreases the appropriate offset by M, and underflow | |
300 increases it by M. The above inequality would not necessarily be | |
301 true if | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
302 |
0 | 303 -- VARX + OFFX underflows and VARX + OFFC0 does not, or |
304 VARX + OFFC0 overflows, but VARX + OFFX does not. | |
305 This may only happen if OFFX < OFFC0. | |
306 -- VARY + OFFY overflows and VARY + OFFC1 does not, or | |
307 VARY + OFFC1 underflows and VARY + OFFY does not. | |
308 This may only happen if OFFY > OFFC1. */ | |
309 | |
310 if (no_wrap) | |
311 { | |
312 x_ok = true; | |
313 y_ok = true; | |
314 } | |
315 else | |
316 { | |
317 x_ok = (integer_zerop (varx) | |
318 || mpz_cmp (loffx, offc0) >= 0); | |
319 y_ok = (integer_zerop (vary) | |
320 || mpz_cmp (loffy, offc1) <= 0); | |
321 } | |
322 | |
323 if (x_ok && y_ok) | |
324 { | |
325 mpz_init (bnd); | |
326 mpz_sub (bnd, loffx, loffy); | |
327 mpz_add (bnd, bnd, offc1); | |
328 mpz_sub (bnd, bnd, offc0); | |
329 | |
330 if (cmp == LT_EXPR) | |
331 mpz_sub_ui (bnd, bnd, 1); | |
332 | |
333 if (lbound) | |
334 { | |
335 mpz_neg (bnd, bnd); | |
336 if (mpz_cmp (bnds->below, bnd) < 0) | |
337 mpz_set (bnds->below, bnd); | |
338 } | |
339 else | |
340 { | |
341 if (mpz_cmp (bnd, bnds->up) < 0) | |
342 mpz_set (bnds->up, bnd); | |
343 } | |
344 mpz_clear (bnd); | |
345 } | |
346 | |
347 mpz_clear (loffx); | |
348 mpz_clear (loffy); | |
349 end: | |
350 mpz_clear (offc0); | |
351 mpz_clear (offc1); | |
352 } | |
353 | |
354 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. | |
355 The subtraction is considered to be performed in arbitrary precision, | |
356 without overflows. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
357 |
0 | 358 We do not attempt to be too clever regarding the value ranges of X and |
359 Y; most of the time, they are just integers or ssa names offsetted by | |
360 integer. However, we try to use the information contained in the | |
361 comparisons before the loop (usually created by loop header copying). */ | |
362 | |
363 static void | |
364 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) | |
365 { | |
366 tree type = TREE_TYPE (x); | |
367 tree varx, vary; | |
368 mpz_t offx, offy; | |
369 mpz_t minx, maxx, miny, maxy; | |
370 int cnt = 0; | |
371 edge e; | |
372 basic_block bb; | |
373 tree c0, c1; | |
374 gimple cond; | |
375 enum tree_code cmp; | |
376 | |
377 /* Get rid of unnecessary casts, but preserve the value of | |
378 the expressions. */ | |
379 STRIP_SIGN_NOPS (x); | |
380 STRIP_SIGN_NOPS (y); | |
381 | |
382 mpz_init (bnds->below); | |
383 mpz_init (bnds->up); | |
384 mpz_init (offx); | |
385 mpz_init (offy); | |
386 split_to_var_and_offset (x, &varx, offx); | |
387 split_to_var_and_offset (y, &vary, offy); | |
388 | |
389 if (!integer_zerop (varx) | |
390 && operand_equal_p (varx, vary, 0)) | |
391 { | |
392 /* Special case VARX == VARY -- we just need to compare the | |
393 offsets. The matters are a bit more complicated in the | |
394 case addition of offsets may wrap. */ | |
395 bound_difference_of_offsetted_base (type, offx, offy, bnds); | |
396 } | |
397 else | |
398 { | |
399 /* Otherwise, use the value ranges to determine the initial | |
400 estimates on below and up. */ | |
401 mpz_init (minx); | |
402 mpz_init (maxx); | |
403 mpz_init (miny); | |
404 mpz_init (maxy); | |
405 determine_value_range (type, varx, offx, minx, maxx); | |
406 determine_value_range (type, vary, offy, miny, maxy); | |
407 | |
408 mpz_sub (bnds->below, minx, maxy); | |
409 mpz_sub (bnds->up, maxx, miny); | |
410 mpz_clear (minx); | |
411 mpz_clear (maxx); | |
412 mpz_clear (miny); | |
413 mpz_clear (maxy); | |
414 } | |
415 | |
416 /* If both X and Y are constants, we cannot get any more precise. */ | |
417 if (integer_zerop (varx) && integer_zerop (vary)) | |
418 goto end; | |
419 | |
420 /* Now walk the dominators of the loop header and use the entry | |
421 guards to refine the estimates. */ | |
422 for (bb = loop->header; | |
423 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; | |
424 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
425 { | |
426 if (!single_pred_p (bb)) | |
427 continue; | |
428 e = single_pred_edge (bb); | |
429 | |
430 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) | |
431 continue; | |
432 | |
433 cond = last_stmt (e->src); | |
434 c0 = gimple_cond_lhs (cond); | |
435 cmp = gimple_cond_code (cond); | |
436 c1 = gimple_cond_rhs (cond); | |
437 | |
438 if (e->flags & EDGE_FALSE_VALUE) | |
439 cmp = invert_tree_comparison (cmp, false); | |
440 | |
441 refine_bounds_using_guard (type, varx, offx, vary, offy, | |
442 c0, cmp, c1, bnds); | |
443 ++cnt; | |
444 } | |
445 | |
446 end: | |
447 mpz_clear (offx); | |
448 mpz_clear (offy); | |
449 } | |
450 | |
451 /* Update the bounds in BNDS that restrict the value of X to the bounds | |
452 that restrict the value of X + DELTA. X can be obtained as a | |
453 difference of two values in TYPE. */ | |
454 | |
455 static void | |
456 bounds_add (bounds *bnds, double_int delta, tree type) | |
457 { | |
458 mpz_t mdelta, max; | |
459 | |
460 mpz_init (mdelta); | |
461 mpz_set_double_int (mdelta, delta, false); | |
462 | |
463 mpz_init (max); | |
464 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); | |
465 | |
466 mpz_add (bnds->up, bnds->up, mdelta); | |
467 mpz_add (bnds->below, bnds->below, mdelta); | |
468 | |
469 if (mpz_cmp (bnds->up, max) > 0) | |
470 mpz_set (bnds->up, max); | |
471 | |
472 mpz_neg (max, max); | |
473 if (mpz_cmp (bnds->below, max) < 0) | |
474 mpz_set (bnds->below, max); | |
475 | |
476 mpz_clear (mdelta); | |
477 mpz_clear (max); | |
478 } | |
479 | |
480 /* Update the bounds in BNDS that restrict the value of X to the bounds | |
481 that restrict the value of -X. */ | |
482 | |
483 static void | |
484 bounds_negate (bounds *bnds) | |
485 { | |
486 mpz_t tmp; | |
487 | |
488 mpz_init_set (tmp, bnds->up); | |
489 mpz_neg (bnds->up, bnds->below); | |
490 mpz_neg (bnds->below, tmp); | |
491 mpz_clear (tmp); | |
492 } | |
493 | |
494 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ | |
495 | |
496 static tree | |
497 inverse (tree x, tree mask) | |
498 { | |
499 tree type = TREE_TYPE (x); | |
500 tree rslt; | |
501 unsigned ctr = tree_floor_log2 (mask); | |
502 | |
503 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) | |
504 { | |
505 unsigned HOST_WIDE_INT ix; | |
506 unsigned HOST_WIDE_INT imask; | |
507 unsigned HOST_WIDE_INT irslt = 1; | |
508 | |
509 gcc_assert (cst_and_fits_in_hwi (x)); | |
510 gcc_assert (cst_and_fits_in_hwi (mask)); | |
511 | |
512 ix = int_cst_value (x); | |
513 imask = int_cst_value (mask); | |
514 | |
515 for (; ctr; ctr--) | |
516 { | |
517 irslt *= ix; | |
518 ix *= ix; | |
519 } | |
520 irslt &= imask; | |
521 | |
522 rslt = build_int_cst_type (type, irslt); | |
523 } | |
524 else | |
525 { | |
526 rslt = build_int_cst (type, 1); | |
527 for (; ctr; ctr--) | |
528 { | |
529 rslt = int_const_binop (MULT_EXPR, rslt, x, 0); | |
530 x = int_const_binop (MULT_EXPR, x, x, 0); | |
531 } | |
532 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0); | |
533 } | |
534 | |
535 return rslt; | |
536 } | |
537 | |
538 /* Derives the upper bound BND on the number of executions of loop with exit | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
539 condition S * i <> C, assuming that this exit is taken. If |
0 | 540 NO_OVERFLOW is true, then the control variable of the loop does not |
541 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up | |
542 contains the upper bound on the value of C. */ | |
543 | |
544 static void | |
545 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, | |
546 bounds *bnds) | |
547 { | |
548 double_int max; | |
549 mpz_t d; | |
550 | |
551 /* If the control variable does not overflow, the number of iterations is | |
552 at most c / s. Otherwise it is at most the period of the control | |
553 variable. */ | |
554 if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s)) | |
555 { | |
556 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c)) | |
557 - tree_low_cst (num_ending_zeros (s), 1)); | |
558 mpz_set_double_int (bnd, max, true); | |
559 return; | |
560 } | |
561 | |
562 /* Determine the upper bound on C. */ | |
563 if (no_overflow || mpz_sgn (bnds->below) >= 0) | |
564 mpz_set (bnd, bnds->up); | |
565 else if (TREE_CODE (c) == INTEGER_CST) | |
566 mpz_set_double_int (bnd, tree_to_double_int (c), true); | |
567 else | |
568 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))), | |
569 true); | |
570 | |
571 mpz_init (d); | |
572 mpz_set_double_int (d, tree_to_double_int (s), true); | |
573 mpz_fdiv_q (bnd, bnd, d); | |
574 mpz_clear (d); | |
575 } | |
576 | |
577 /* Determines number of iterations of loop whose ending condition | |
578 is IV <> FINAL. TYPE is the type of the iv. The number of | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
579 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if |
0 | 580 we know that the exit must be taken eventually, i.e., that the IV |
581 ever reaches the value FINAL (we derived this earlier, and possibly set | |
582 NITER->assumptions to make sure this is the case). BNDS contains the | |
583 bounds on the difference FINAL - IV->base. */ | |
584 | |
585 static bool | |
586 number_of_iterations_ne (tree type, affine_iv *iv, tree final, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
587 struct tree_niter_desc *niter, bool exit_must_be_taken, |
0 | 588 bounds *bnds) |
589 { | |
590 tree niter_type = unsigned_type_for (type); | |
591 tree s, c, d, bits, assumption, tmp, bound; | |
592 mpz_t max; | |
593 | |
594 niter->control = *iv; | |
595 niter->bound = final; | |
596 niter->cmp = NE_EXPR; | |
597 | |
598 /* Rearrange the terms so that we get inequality S * i <> C, with S | |
599 positive. Also cast everything to the unsigned type. If IV does | |
600 not overflow, BNDS bounds the value of C. Also, this is the | |
601 case if the computation |FINAL - IV->base| does not overflow, i.e., | |
602 if BNDS->below in the result is nonnegative. */ | |
603 if (tree_int_cst_sign_bit (iv->step)) | |
604 { | |
605 s = fold_convert (niter_type, | |
606 fold_build1 (NEGATE_EXPR, type, iv->step)); | |
607 c = fold_build2 (MINUS_EXPR, niter_type, | |
608 fold_convert (niter_type, iv->base), | |
609 fold_convert (niter_type, final)); | |
610 bounds_negate (bnds); | |
611 } | |
612 else | |
613 { | |
614 s = fold_convert (niter_type, iv->step); | |
615 c = fold_build2 (MINUS_EXPR, niter_type, | |
616 fold_convert (niter_type, final), | |
617 fold_convert (niter_type, iv->base)); | |
618 } | |
619 | |
620 mpz_init (max); | |
621 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds); | |
622 niter->max = mpz_get_double_int (niter_type, max, false); | |
623 mpz_clear (max); | |
624 | |
625 /* First the trivial cases -- when the step is 1. */ | |
626 if (integer_onep (s)) | |
627 { | |
628 niter->niter = c; | |
629 return true; | |
630 } | |
631 | |
632 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop | |
633 is infinite. Otherwise, the number of iterations is | |
634 (inverse(s/d) * (c/d)) mod (size of mode/d). */ | |
635 bits = num_ending_zeros (s); | |
636 bound = build_low_bits_mask (niter_type, | |
637 (TYPE_PRECISION (niter_type) | |
638 - tree_low_cst (bits, 1))); | |
639 | |
640 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, | |
641 build_int_cst (niter_type, 1), bits); | |
642 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); | |
643 | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
644 if (!exit_must_be_taken) |
0 | 645 { |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
646 /* If we cannot assume that the exit is taken eventually, record the |
0 | 647 assumptions for divisibility of c. */ |
648 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d); | |
649 assumption = fold_build2 (EQ_EXPR, boolean_type_node, | |
650 assumption, build_int_cst (niter_type, 0)); | |
651 if (!integer_nonzerop (assumption)) | |
652 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
653 niter->assumptions, assumption); | |
654 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
655 |
0 | 656 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); |
657 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); | |
658 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); | |
659 return true; | |
660 } | |
661 | |
662 /* Checks whether we can determine the final value of the control variable | |
663 of the loop with ending condition IV0 < IV1 (computed in TYPE). | |
664 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value | |
665 of the step. The assumptions necessary to ensure that the computation | |
666 of the final value does not overflow are recorded in NITER. If we | |
667 find the final value, we adjust DELTA and return TRUE. Otherwise | |
668 we return false. BNDS bounds the value of IV1->base - IV0->base, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
669 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
670 true if we know that the exit must be taken eventually. */ |
0 | 671 |
672 static bool | |
673 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, | |
674 struct tree_niter_desc *niter, | |
675 tree *delta, tree step, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
676 bool exit_must_be_taken, bounds *bnds) |
0 | 677 { |
678 tree niter_type = TREE_TYPE (step); | |
679 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); | |
680 tree tmod; | |
681 mpz_t mmod; | |
682 tree assumption = boolean_true_node, bound, noloop; | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
683 bool ret = false, fv_comp_no_overflow; |
0 | 684 tree type1 = type; |
685 if (POINTER_TYPE_P (type)) | |
686 type1 = sizetype; | |
687 | |
688 if (TREE_CODE (mod) != INTEGER_CST) | |
689 return false; | |
690 if (integer_nonzerop (mod)) | |
691 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); | |
692 tmod = fold_convert (type1, mod); | |
693 | |
694 mpz_init (mmod); | |
695 mpz_set_double_int (mmod, tree_to_double_int (mod), true); | |
696 mpz_neg (mmod, mmod); | |
697 | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
698 /* If the induction variable does not overflow and the exit is taken, |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
699 then the computation of the final value does not overflow. This is |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
700 also obviously the case if the new final value is equal to the |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
701 current one. Finally, we postulate this for pointer type variables, |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
702 as the code cannot rely on the object to that the pointer points being |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
703 placed at the end of the address space (and more pragmatically, |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
704 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */ |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
705 if (integer_zerop (mod) || POINTER_TYPE_P (type)) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
706 fv_comp_no_overflow = true; |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
707 else if (!exit_must_be_taken) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
708 fv_comp_no_overflow = false; |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
709 else |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
710 fv_comp_no_overflow = |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
711 (iv0->no_overflow && integer_nonzerop (iv0->step)) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
712 || (iv1->no_overflow && integer_nonzerop (iv1->step)); |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
713 |
0 | 714 if (integer_nonzerop (iv0->step)) |
715 { | |
716 /* The final value of the iv is iv1->base + MOD, assuming that this | |
717 computation does not overflow, and that | |
718 iv0->base <= iv1->base + MOD. */ | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
719 if (!fv_comp_no_overflow) |
0 | 720 { |
721 bound = fold_build2 (MINUS_EXPR, type1, | |
722 TYPE_MAX_VALUE (type1), tmod); | |
723 assumption = fold_build2 (LE_EXPR, boolean_type_node, | |
724 iv1->base, bound); | |
725 if (integer_zerop (assumption)) | |
726 goto end; | |
727 } | |
728 if (mpz_cmp (mmod, bnds->below) < 0) | |
729 noloop = boolean_false_node; | |
730 else if (POINTER_TYPE_P (type)) | |
731 noloop = fold_build2 (GT_EXPR, boolean_type_node, | |
732 iv0->base, | |
733 fold_build2 (POINTER_PLUS_EXPR, type, | |
734 iv1->base, tmod)); | |
735 else | |
736 noloop = fold_build2 (GT_EXPR, boolean_type_node, | |
737 iv0->base, | |
738 fold_build2 (PLUS_EXPR, type1, | |
739 iv1->base, tmod)); | |
740 } | |
741 else | |
742 { | |
743 /* The final value of the iv is iv0->base - MOD, assuming that this | |
744 computation does not overflow, and that | |
745 iv0->base - MOD <= iv1->base. */ | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
746 if (!fv_comp_no_overflow) |
0 | 747 { |
748 bound = fold_build2 (PLUS_EXPR, type1, | |
749 TYPE_MIN_VALUE (type1), tmod); | |
750 assumption = fold_build2 (GE_EXPR, boolean_type_node, | |
751 iv0->base, bound); | |
752 if (integer_zerop (assumption)) | |
753 goto end; | |
754 } | |
755 if (mpz_cmp (mmod, bnds->below) < 0) | |
756 noloop = boolean_false_node; | |
757 else if (POINTER_TYPE_P (type)) | |
758 noloop = fold_build2 (GT_EXPR, boolean_type_node, | |
759 fold_build2 (POINTER_PLUS_EXPR, type, | |
760 iv0->base, | |
761 fold_build1 (NEGATE_EXPR, | |
762 type1, tmod)), | |
763 iv1->base); | |
764 else | |
765 noloop = fold_build2 (GT_EXPR, boolean_type_node, | |
766 fold_build2 (MINUS_EXPR, type1, | |
767 iv0->base, tmod), | |
768 iv1->base); | |
769 } | |
770 | |
771 if (!integer_nonzerop (assumption)) | |
772 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
773 niter->assumptions, | |
774 assumption); | |
775 if (!integer_zerop (noloop)) | |
776 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, | |
777 niter->may_be_zero, | |
778 noloop); | |
779 bounds_add (bnds, tree_to_double_int (mod), type); | |
780 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); | |
781 | |
782 ret = true; | |
783 end: | |
784 mpz_clear (mmod); | |
785 return ret; | |
786 } | |
787 | |
788 /* Add assertions to NITER that ensure that the control variable of the loop | |
789 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 | |
790 are TYPE. Returns false if we can prove that there is an overflow, true | |
791 otherwise. STEP is the absolute value of the step. */ | |
792 | |
793 static bool | |
794 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, | |
795 struct tree_niter_desc *niter, tree step) | |
796 { | |
797 tree bound, d, assumption, diff; | |
798 tree niter_type = TREE_TYPE (step); | |
799 | |
800 if (integer_nonzerop (iv0->step)) | |
801 { | |
802 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ | |
803 if (iv0->no_overflow) | |
804 return true; | |
805 | |
806 /* If iv0->base is a constant, we can determine the last value before | |
807 overflow precisely; otherwise we conservatively assume | |
808 MAX - STEP + 1. */ | |
809 | |
810 if (TREE_CODE (iv0->base) == INTEGER_CST) | |
811 { | |
812 d = fold_build2 (MINUS_EXPR, niter_type, | |
813 fold_convert (niter_type, TYPE_MAX_VALUE (type)), | |
814 fold_convert (niter_type, iv0->base)); | |
815 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); | |
816 } | |
817 else | |
818 diff = fold_build2 (MINUS_EXPR, niter_type, step, | |
819 build_int_cst (niter_type, 1)); | |
820 bound = fold_build2 (MINUS_EXPR, type, | |
821 TYPE_MAX_VALUE (type), fold_convert (type, diff)); | |
822 assumption = fold_build2 (LE_EXPR, boolean_type_node, | |
823 iv1->base, bound); | |
824 } | |
825 else | |
826 { | |
827 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ | |
828 if (iv1->no_overflow) | |
829 return true; | |
830 | |
831 if (TREE_CODE (iv1->base) == INTEGER_CST) | |
832 { | |
833 d = fold_build2 (MINUS_EXPR, niter_type, | |
834 fold_convert (niter_type, iv1->base), | |
835 fold_convert (niter_type, TYPE_MIN_VALUE (type))); | |
836 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); | |
837 } | |
838 else | |
839 diff = fold_build2 (MINUS_EXPR, niter_type, step, | |
840 build_int_cst (niter_type, 1)); | |
841 bound = fold_build2 (PLUS_EXPR, type, | |
842 TYPE_MIN_VALUE (type), fold_convert (type, diff)); | |
843 assumption = fold_build2 (GE_EXPR, boolean_type_node, | |
844 iv0->base, bound); | |
845 } | |
846 | |
847 if (integer_zerop (assumption)) | |
848 return false; | |
849 if (!integer_nonzerop (assumption)) | |
850 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
851 niter->assumptions, assumption); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
852 |
0 | 853 iv0->no_overflow = true; |
854 iv1->no_overflow = true; | |
855 return true; | |
856 } | |
857 | |
858 /* Add an assumption to NITER that a loop whose ending condition | |
859 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS | |
860 bounds the value of IV1->base - IV0->base. */ | |
861 | |
862 static void | |
863 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, | |
864 struct tree_niter_desc *niter, bounds *bnds) | |
865 { | |
866 tree assumption = boolean_true_node, bound, diff; | |
867 tree mbz, mbzl, mbzr, type1; | |
868 bool rolls_p, no_overflow_p; | |
869 double_int dstep; | |
870 mpz_t mstep, max; | |
871 | |
872 /* We are going to compute the number of iterations as | |
873 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
874 variant of TYPE. This formula only works if |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
875 |
0 | 876 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
877 |
0 | 878 (where MAX is the maximum value of the unsigned variant of TYPE, and |
879 the computations in this formula are performed in full precision | |
880 (without overflows). | |
881 | |
882 Usually, for loops with exit condition iv0->base + step * i < iv1->base, | |
883 we have a condition of form iv0->base - step < iv1->base before the loop, | |
884 and for loops iv0->base < iv1->base - step * i the condition | |
885 iv0->base < iv1->base + step, due to loop header copying, which enable us | |
886 to prove the lower bound. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
887 |
0 | 888 The upper bound is more complicated. Unless the expressions for initial |
889 and final value themselves contain enough information, we usually cannot | |
890 derive it from the context. */ | |
891 | |
892 /* First check whether the answer does not follow from the bounds we gathered | |
893 before. */ | |
894 if (integer_nonzerop (iv0->step)) | |
895 dstep = tree_to_double_int (iv0->step); | |
896 else | |
897 { | |
898 dstep = double_int_sext (tree_to_double_int (iv1->step), | |
899 TYPE_PRECISION (type)); | |
900 dstep = double_int_neg (dstep); | |
901 } | |
902 | |
903 mpz_init (mstep); | |
904 mpz_set_double_int (mstep, dstep, true); | |
905 mpz_neg (mstep, mstep); | |
906 mpz_add_ui (mstep, mstep, 1); | |
907 | |
908 rolls_p = mpz_cmp (mstep, bnds->below) <= 0; | |
909 | |
910 mpz_init (max); | |
911 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); | |
912 mpz_add (max, max, mstep); | |
913 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0 | |
914 /* For pointers, only values lying inside a single object | |
915 can be compared or manipulated by pointer arithmetics. | |
916 Gcc in general does not allow or handle objects larger | |
917 than half of the address space, hence the upper bound | |
918 is satisfied for pointers. */ | |
919 || POINTER_TYPE_P (type)); | |
920 mpz_clear (mstep); | |
921 mpz_clear (max); | |
922 | |
923 if (rolls_p && no_overflow_p) | |
924 return; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
925 |
0 | 926 type1 = type; |
927 if (POINTER_TYPE_P (type)) | |
928 type1 = sizetype; | |
929 | |
930 /* Now the hard part; we must formulate the assumption(s) as expressions, and | |
931 we must be careful not to introduce overflow. */ | |
932 | |
933 if (integer_nonzerop (iv0->step)) | |
934 { | |
935 diff = fold_build2 (MINUS_EXPR, type1, | |
936 iv0->step, build_int_cst (type1, 1)); | |
937 | |
938 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since | |
939 0 address never belongs to any object, we can assume this for | |
940 pointers. */ | |
941 if (!POINTER_TYPE_P (type)) | |
942 { | |
943 bound = fold_build2 (PLUS_EXPR, type1, | |
944 TYPE_MIN_VALUE (type), diff); | |
945 assumption = fold_build2 (GE_EXPR, boolean_type_node, | |
946 iv0->base, bound); | |
947 } | |
948 | |
949 /* And then we can compute iv0->base - diff, and compare it with | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
950 iv1->base. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
951 mbzl = fold_build2 (MINUS_EXPR, type1, |
0 | 952 fold_convert (type1, iv0->base), diff); |
953 mbzr = fold_convert (type1, iv1->base); | |
954 } | |
955 else | |
956 { | |
957 diff = fold_build2 (PLUS_EXPR, type1, | |
958 iv1->step, build_int_cst (type1, 1)); | |
959 | |
960 if (!POINTER_TYPE_P (type)) | |
961 { | |
962 bound = fold_build2 (PLUS_EXPR, type1, | |
963 TYPE_MAX_VALUE (type), diff); | |
964 assumption = fold_build2 (LE_EXPR, boolean_type_node, | |
965 iv1->base, bound); | |
966 } | |
967 | |
968 mbzl = fold_convert (type1, iv0->base); | |
969 mbzr = fold_build2 (MINUS_EXPR, type1, | |
970 fold_convert (type1, iv1->base), diff); | |
971 } | |
972 | |
973 if (!integer_nonzerop (assumption)) | |
974 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
975 niter->assumptions, assumption); | |
976 if (!rolls_p) | |
977 { | |
978 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); | |
979 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, | |
980 niter->may_be_zero, mbz); | |
981 } | |
982 } | |
983 | |
984 /* Determines number of iterations of loop whose ending condition | |
985 is IV0 < IV1. TYPE is the type of the iv. The number of | |
986 iterations is stored to NITER. BNDS bounds the difference | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
987 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
988 that the exit must be taken eventually. */ |
0 | 989 |
990 static bool | |
991 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, | |
992 struct tree_niter_desc *niter, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
993 bool exit_must_be_taken, bounds *bnds) |
0 | 994 { |
995 tree niter_type = unsigned_type_for (type); | |
996 tree delta, step, s; | |
997 mpz_t mstep, tmp; | |
998 | |
999 if (integer_nonzerop (iv0->step)) | |
1000 { | |
1001 niter->control = *iv0; | |
1002 niter->cmp = LT_EXPR; | |
1003 niter->bound = iv1->base; | |
1004 } | |
1005 else | |
1006 { | |
1007 niter->control = *iv1; | |
1008 niter->cmp = GT_EXPR; | |
1009 niter->bound = iv0->base; | |
1010 } | |
1011 | |
1012 delta = fold_build2 (MINUS_EXPR, niter_type, | |
1013 fold_convert (niter_type, iv1->base), | |
1014 fold_convert (niter_type, iv0->base)); | |
1015 | |
1016 /* First handle the special case that the step is +-1. */ | |
1017 if ((integer_onep (iv0->step) && integer_zerop (iv1->step)) | |
1018 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step))) | |
1019 { | |
1020 /* for (i = iv0->base; i < iv1->base; i++) | |
1021 | |
1022 or | |
1023 | |
1024 for (i = iv1->base; i > iv0->base; i--). | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1025 |
0 | 1026 In both cases # of iterations is iv1->base - iv0->base, assuming that |
1027 iv1->base >= iv0->base. | |
1028 | |
1029 First try to derive a lower bound on the value of | |
1030 iv1->base - iv0->base, computed in full precision. If the difference | |
1031 is nonnegative, we are done, otherwise we must record the | |
1032 condition. */ | |
1033 | |
1034 if (mpz_sgn (bnds->below) < 0) | |
1035 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, | |
1036 iv1->base, iv0->base); | |
1037 niter->niter = delta; | |
1038 niter->max = mpz_get_double_int (niter_type, bnds->up, false); | |
1039 return true; | |
1040 } | |
1041 | |
1042 if (integer_nonzerop (iv0->step)) | |
1043 step = fold_convert (niter_type, iv0->step); | |
1044 else | |
1045 step = fold_convert (niter_type, | |
1046 fold_build1 (NEGATE_EXPR, type, iv1->step)); | |
1047 | |
1048 /* If we can determine the final value of the control iv exactly, we can | |
1049 transform the condition to != comparison. In particular, this will be | |
1050 the case if DELTA is constant. */ | |
1051 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1052 exit_must_be_taken, bnds)) |
0 | 1053 { |
1054 affine_iv zps; | |
1055 | |
1056 zps.base = build_int_cst (niter_type, 0); | |
1057 zps.step = step; | |
1058 /* number_of_iterations_lt_to_ne will add assumptions that ensure that | |
1059 zps does not overflow. */ | |
1060 zps.no_overflow = true; | |
1061 | |
1062 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds); | |
1063 } | |
1064 | |
1065 /* Make sure that the control iv does not overflow. */ | |
1066 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) | |
1067 return false; | |
1068 | |
1069 /* We determine the number of iterations as (delta + step - 1) / step. For | |
1070 this to work, we must know that iv1->base >= iv0->base - step + 1, | |
1071 otherwise the loop does not roll. */ | |
1072 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds); | |
1073 | |
1074 s = fold_build2 (MINUS_EXPR, niter_type, | |
1075 step, build_int_cst (niter_type, 1)); | |
1076 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); | |
1077 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); | |
1078 | |
1079 mpz_init (mstep); | |
1080 mpz_init (tmp); | |
1081 mpz_set_double_int (mstep, tree_to_double_int (step), true); | |
1082 mpz_add (tmp, bnds->up, mstep); | |
1083 mpz_sub_ui (tmp, tmp, 1); | |
1084 mpz_fdiv_q (tmp, tmp, mstep); | |
1085 niter->max = mpz_get_double_int (niter_type, tmp, false); | |
1086 mpz_clear (mstep); | |
1087 mpz_clear (tmp); | |
1088 | |
1089 return true; | |
1090 } | |
1091 | |
1092 /* Determines number of iterations of loop whose ending condition | |
1093 is IV0 <= IV1. TYPE is the type of the iv. The number of | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1094 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if |
0 | 1095 we know that this condition must eventually become false (we derived this |
1096 earlier, and possibly set NITER->assumptions to make sure this | |
1097 is the case). BNDS bounds the difference IV1->base - IV0->base. */ | |
1098 | |
1099 static bool | |
1100 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1101 struct tree_niter_desc *niter, bool exit_must_be_taken, |
0 | 1102 bounds *bnds) |
1103 { | |
1104 tree assumption; | |
1105 tree type1 = type; | |
1106 if (POINTER_TYPE_P (type)) | |
1107 type1 = sizetype; | |
1108 | |
1109 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff | |
1110 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest | |
1111 value of the type. This we must know anyway, since if it is | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1112 equal to this value, the loop rolls forever. We do not check |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1113 this condition for pointer type ivs, as the code cannot rely on |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1114 the object to that the pointer points being placed at the end of |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1115 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1116 not defined for pointers). */ |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1117 |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1118 if (!exit_must_be_taken && !POINTER_TYPE_P (type)) |
0 | 1119 { |
1120 if (integer_nonzerop (iv0->step)) | |
1121 assumption = fold_build2 (NE_EXPR, boolean_type_node, | |
1122 iv1->base, TYPE_MAX_VALUE (type)); | |
1123 else | |
1124 assumption = fold_build2 (NE_EXPR, boolean_type_node, | |
1125 iv0->base, TYPE_MIN_VALUE (type)); | |
1126 | |
1127 if (integer_zerop (assumption)) | |
1128 return false; | |
1129 if (!integer_nonzerop (assumption)) | |
1130 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, | |
1131 niter->assumptions, assumption); | |
1132 } | |
1133 | |
1134 if (integer_nonzerop (iv0->step)) | |
1135 { | |
1136 if (POINTER_TYPE_P (type)) | |
1137 iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base, | |
1138 build_int_cst (type1, 1)); | |
1139 else | |
1140 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base, | |
1141 build_int_cst (type1, 1)); | |
1142 } | |
1143 else if (POINTER_TYPE_P (type)) | |
1144 iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base, | |
1145 fold_build1 (NEGATE_EXPR, type1, | |
1146 build_int_cst (type1, 1))); | |
1147 else | |
1148 iv0->base = fold_build2 (MINUS_EXPR, type1, | |
1149 iv0->base, build_int_cst (type1, 1)); | |
1150 | |
1151 bounds_add (bnds, double_int_one, type1); | |
1152 | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1153 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1154 bnds); |
0 | 1155 } |
1156 | |
1157 /* Dumps description of affine induction variable IV to FILE. */ | |
1158 | |
1159 static void | |
1160 dump_affine_iv (FILE *file, affine_iv *iv) | |
1161 { | |
1162 if (!integer_zerop (iv->step)) | |
1163 fprintf (file, "["); | |
1164 | |
1165 print_generic_expr (dump_file, iv->base, TDF_SLIM); | |
1166 | |
1167 if (!integer_zerop (iv->step)) | |
1168 { | |
1169 fprintf (file, ", + , "); | |
1170 print_generic_expr (dump_file, iv->step, TDF_SLIM); | |
1171 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : ""); | |
1172 } | |
1173 } | |
1174 | |
1175 /* Determine the number of iterations according to condition (for staying | |
1176 inside loop) which compares two induction variables using comparison | |
1177 operator CODE. The induction variable on left side of the comparison | |
1178 is IV0, the right-hand side is IV1. Both induction variables must have | |
1179 type TYPE, which must be an integer or pointer type. The steps of the | |
1180 ivs must be constants (or NULL_TREE, which is interpreted as constant zero). | |
1181 | |
1182 LOOP is the loop whose number of iterations we are determining. | |
1183 | |
1184 ONLY_EXIT is true if we are sure this is the only way the loop could be | |
1185 exited (including possibly non-returning function calls, exceptions, etc.) | |
1186 -- in this case we can use the information whether the control induction | |
1187 variables can overflow or not in a more efficient way. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1188 |
0 | 1189 The results (number of iterations and assumptions as described in |
1190 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. | |
1191 Returns false if it fails to determine number of iterations, true if it | |
1192 was determined (possibly with some assumptions). */ | |
1193 | |
1194 static bool | |
1195 number_of_iterations_cond (struct loop *loop, | |
1196 tree type, affine_iv *iv0, enum tree_code code, | |
1197 affine_iv *iv1, struct tree_niter_desc *niter, | |
1198 bool only_exit) | |
1199 { | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1200 bool exit_must_be_taken = false, ret; |
0 | 1201 bounds bnds; |
1202 | |
1203 /* The meaning of these assumptions is this: | |
1204 if !assumptions | |
1205 then the rest of information does not have to be valid | |
1206 if may_be_zero then the loop does not roll, even if | |
1207 niter != 0. */ | |
1208 niter->assumptions = boolean_true_node; | |
1209 niter->may_be_zero = boolean_false_node; | |
1210 niter->niter = NULL_TREE; | |
1211 niter->max = double_int_zero; | |
1212 | |
1213 niter->bound = NULL_TREE; | |
1214 niter->cmp = ERROR_MARK; | |
1215 | |
1216 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that | |
1217 the control variable is on lhs. */ | |
1218 if (code == GE_EXPR || code == GT_EXPR | |
1219 || (code == NE_EXPR && integer_zerop (iv0->step))) | |
1220 { | |
1221 SWAP (iv0, iv1); | |
1222 code = swap_tree_comparison (code); | |
1223 } | |
1224 | |
1225 if (POINTER_TYPE_P (type)) | |
1226 { | |
1227 /* Comparison of pointers is undefined unless both iv0 and iv1 point | |
1228 to the same object. If they do, the control variable cannot wrap | |
1229 (as wrap around the bounds of memory will never return a pointer | |
1230 that would be guaranteed to point to the same object, even if we | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1231 avoid undefined behavior by casting to size_t and back). */ |
0 | 1232 iv0->no_overflow = true; |
1233 iv1->no_overflow = true; | |
1234 } | |
1235 | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1236 /* If the control induction variable does not overflow and the only exit |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1237 from the loop is the one that we analyze, we know it must be taken |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1238 eventually. */ |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1239 if (only_exit) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1240 { |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1241 if (!integer_zerop (iv0->step) && iv0->no_overflow) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1242 exit_must_be_taken = true; |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1243 else if (!integer_zerop (iv1->step) && iv1->no_overflow) |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1244 exit_must_be_taken = true; |
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1245 } |
0 | 1246 |
1247 /* We can handle the case when neither of the sides of the comparison is | |
1248 invariant, provided that the test is NE_EXPR. This rarely occurs in | |
1249 practice, but it is simple enough to manage. */ | |
1250 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step)) | |
1251 { | |
1252 if (code != NE_EXPR) | |
1253 return false; | |
1254 | |
1255 iv0->step = fold_binary_to_constant (MINUS_EXPR, type, | |
1256 iv0->step, iv1->step); | |
1257 iv0->no_overflow = false; | |
1258 iv1->step = build_int_cst (type, 0); | |
1259 iv1->no_overflow = true; | |
1260 } | |
1261 | |
1262 /* If the result of the comparison is a constant, the loop is weird. More | |
1263 precise handling would be possible, but the situation is not common enough | |
1264 to waste time on it. */ | |
1265 if (integer_zerop (iv0->step) && integer_zerop (iv1->step)) | |
1266 return false; | |
1267 | |
1268 /* Ignore loops of while (i-- < 10) type. */ | |
1269 if (code != NE_EXPR) | |
1270 { | |
1271 if (iv0->step && tree_int_cst_sign_bit (iv0->step)) | |
1272 return false; | |
1273 | |
1274 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) | |
1275 return false; | |
1276 } | |
1277 | |
1278 /* If the loop exits immediately, there is nothing to do. */ | |
1279 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) | |
1280 { | |
1281 niter->niter = build_int_cst (unsigned_type_for (type), 0); | |
1282 niter->max = double_int_zero; | |
1283 return true; | |
1284 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1285 |
0 | 1286 /* OK, now we know we have a senseful loop. Handle several cases, depending |
1287 on what comparison operator is used. */ | |
1288 bound_difference (loop, iv1->base, iv0->base, &bnds); | |
1289 | |
1290 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1291 { | |
1292 fprintf (dump_file, | |
1293 "Analyzing # of iterations of loop %d\n", loop->num); | |
1294 | |
1295 fprintf (dump_file, " exit condition "); | |
1296 dump_affine_iv (dump_file, iv0); | |
1297 fprintf (dump_file, " %s ", | |
1298 code == NE_EXPR ? "!=" | |
1299 : code == LT_EXPR ? "<" | |
1300 : "<="); | |
1301 dump_affine_iv (dump_file, iv1); | |
1302 fprintf (dump_file, "\n"); | |
1303 | |
1304 fprintf (dump_file, " bounds on difference of bases: "); | |
1305 mpz_out_str (dump_file, 10, bnds.below); | |
1306 fprintf (dump_file, " ... "); | |
1307 mpz_out_str (dump_file, 10, bnds.up); | |
1308 fprintf (dump_file, "\n"); | |
1309 } | |
1310 | |
1311 switch (code) | |
1312 { | |
1313 case NE_EXPR: | |
1314 gcc_assert (integer_zerop (iv1->step)); | |
1315 ret = number_of_iterations_ne (type, iv0, iv1->base, niter, | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1316 exit_must_be_taken, &bnds); |
0 | 1317 break; |
1318 | |
1319 case LT_EXPR: | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1320 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, |
0 | 1321 &bnds); |
1322 break; | |
1323 | |
1324 case LE_EXPR: | |
19
58ad6c70ea60
update gcc from 4.4.0 to 4.4.1.
kent@firefly.cr.ie.u-ryukyu.ac.jp
parents:
0
diff
changeset
|
1325 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken, |
0 | 1326 &bnds); |
1327 break; | |
1328 | |
1329 default: | |
1330 gcc_unreachable (); | |
1331 } | |
1332 | |
1333 mpz_clear (bnds.up); | |
1334 mpz_clear (bnds.below); | |
1335 | |
1336 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1337 { | |
1338 if (ret) | |
1339 { | |
1340 fprintf (dump_file, " result:\n"); | |
1341 if (!integer_nonzerop (niter->assumptions)) | |
1342 { | |
1343 fprintf (dump_file, " under assumptions "); | |
1344 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM); | |
1345 fprintf (dump_file, "\n"); | |
1346 } | |
1347 | |
1348 if (!integer_zerop (niter->may_be_zero)) | |
1349 { | |
1350 fprintf (dump_file, " zero if "); | |
1351 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM); | |
1352 fprintf (dump_file, "\n"); | |
1353 } | |
1354 | |
1355 fprintf (dump_file, " # of iterations "); | |
1356 print_generic_expr (dump_file, niter->niter, TDF_SLIM); | |
1357 fprintf (dump_file, ", bounded by "); | |
1358 dump_double_int (dump_file, niter->max, true); | |
1359 fprintf (dump_file, "\n"); | |
1360 } | |
1361 else | |
1362 fprintf (dump_file, " failed\n\n"); | |
1363 } | |
1364 return ret; | |
1365 } | |
1366 | |
1367 /* Substitute NEW for OLD in EXPR and fold the result. */ | |
1368 | |
1369 static tree | |
1370 simplify_replace_tree (tree expr, tree old, tree new_tree) | |
1371 { | |
1372 unsigned i, n; | |
1373 tree ret = NULL_TREE, e, se; | |
1374 | |
1375 if (!expr) | |
1376 return NULL_TREE; | |
1377 | |
1378 if (expr == old | |
1379 || operand_equal_p (expr, old, 0)) | |
1380 return unshare_expr (new_tree); | |
1381 | |
1382 if (!EXPR_P (expr)) | |
1383 return expr; | |
1384 | |
1385 n = TREE_OPERAND_LENGTH (expr); | |
1386 for (i = 0; i < n; i++) | |
1387 { | |
1388 e = TREE_OPERAND (expr, i); | |
1389 se = simplify_replace_tree (e, old, new_tree); | |
1390 if (e == se) | |
1391 continue; | |
1392 | |
1393 if (!ret) | |
1394 ret = copy_node (expr); | |
1395 | |
1396 TREE_OPERAND (ret, i) = se; | |
1397 } | |
1398 | |
1399 return (ret ? fold (ret) : expr); | |
1400 } | |
1401 | |
1402 /* Expand definitions of ssa names in EXPR as long as they are simple | |
1403 enough, and return the new expression. */ | |
1404 | |
1405 tree | |
1406 expand_simple_operations (tree expr) | |
1407 { | |
1408 unsigned i, n; | |
1409 tree ret = NULL_TREE, e, ee, e1; | |
1410 enum tree_code code; | |
1411 gimple stmt; | |
1412 | |
1413 if (expr == NULL_TREE) | |
1414 return expr; | |
1415 | |
1416 if (is_gimple_min_invariant (expr)) | |
1417 return expr; | |
1418 | |
1419 code = TREE_CODE (expr); | |
1420 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) | |
1421 { | |
1422 n = TREE_OPERAND_LENGTH (expr); | |
1423 for (i = 0; i < n; i++) | |
1424 { | |
1425 e = TREE_OPERAND (expr, i); | |
1426 ee = expand_simple_operations (e); | |
1427 if (e == ee) | |
1428 continue; | |
1429 | |
1430 if (!ret) | |
1431 ret = copy_node (expr); | |
1432 | |
1433 TREE_OPERAND (ret, i) = ee; | |
1434 } | |
1435 | |
1436 if (!ret) | |
1437 return expr; | |
1438 | |
1439 fold_defer_overflow_warnings (); | |
1440 ret = fold (ret); | |
1441 fold_undefer_and_ignore_overflow_warnings (); | |
1442 return ret; | |
1443 } | |
1444 | |
1445 if (TREE_CODE (expr) != SSA_NAME) | |
1446 return expr; | |
1447 | |
1448 stmt = SSA_NAME_DEF_STMT (expr); | |
1449 if (gimple_code (stmt) == GIMPLE_PHI) | |
1450 { | |
1451 basic_block src, dest; | |
1452 | |
1453 if (gimple_phi_num_args (stmt) != 1) | |
1454 return expr; | |
1455 e = PHI_ARG_DEF (stmt, 0); | |
1456 | |
1457 /* Avoid propagating through loop exit phi nodes, which | |
1458 could break loop-closed SSA form restrictions. */ | |
1459 dest = gimple_bb (stmt); | |
1460 src = single_pred (dest); | |
1461 if (TREE_CODE (e) == SSA_NAME | |
1462 && src->loop_father != dest->loop_father) | |
1463 return expr; | |
1464 | |
1465 return expand_simple_operations (e); | |
1466 } | |
1467 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
1468 return expr; | |
1469 | |
1470 e = gimple_assign_rhs1 (stmt); | |
1471 code = gimple_assign_rhs_code (stmt); | |
1472 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) | |
1473 { | |
1474 if (is_gimple_min_invariant (e)) | |
1475 return e; | |
1476 | |
1477 if (code == SSA_NAME) | |
1478 return expand_simple_operations (e); | |
1479 | |
1480 return expr; | |
1481 } | |
1482 | |
1483 switch (code) | |
1484 { | |
1485 CASE_CONVERT: | |
1486 /* Casts are simple. */ | |
1487 ee = expand_simple_operations (e); | |
1488 return fold_build1 (code, TREE_TYPE (expr), ee); | |
1489 | |
1490 case PLUS_EXPR: | |
1491 case MINUS_EXPR: | |
1492 case POINTER_PLUS_EXPR: | |
1493 /* And increments and decrements by a constant are simple. */ | |
1494 e1 = gimple_assign_rhs2 (stmt); | |
1495 if (!is_gimple_min_invariant (e1)) | |
1496 return expr; | |
1497 | |
1498 ee = expand_simple_operations (e); | |
1499 return fold_build2 (code, TREE_TYPE (expr), ee, e1); | |
1500 | |
1501 default: | |
1502 return expr; | |
1503 } | |
1504 } | |
1505 | |
1506 /* Tries to simplify EXPR using the condition COND. Returns the simplified | |
1507 expression (or EXPR unchanged, if no simplification was possible). */ | |
1508 | |
1509 static tree | |
1510 tree_simplify_using_condition_1 (tree cond, tree expr) | |
1511 { | |
1512 bool changed; | |
1513 tree e, te, e0, e1, e2, notcond; | |
1514 enum tree_code code = TREE_CODE (expr); | |
1515 | |
1516 if (code == INTEGER_CST) | |
1517 return expr; | |
1518 | |
1519 if (code == TRUTH_OR_EXPR | |
1520 || code == TRUTH_AND_EXPR | |
1521 || code == COND_EXPR) | |
1522 { | |
1523 changed = false; | |
1524 | |
1525 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); | |
1526 if (TREE_OPERAND (expr, 0) != e0) | |
1527 changed = true; | |
1528 | |
1529 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); | |
1530 if (TREE_OPERAND (expr, 1) != e1) | |
1531 changed = true; | |
1532 | |
1533 if (code == COND_EXPR) | |
1534 { | |
1535 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); | |
1536 if (TREE_OPERAND (expr, 2) != e2) | |
1537 changed = true; | |
1538 } | |
1539 else | |
1540 e2 = NULL_TREE; | |
1541 | |
1542 if (changed) | |
1543 { | |
1544 if (code == COND_EXPR) | |
1545 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); | |
1546 else | |
1547 expr = fold_build2 (code, boolean_type_node, e0, e1); | |
1548 } | |
1549 | |
1550 return expr; | |
1551 } | |
1552 | |
1553 /* In case COND is equality, we may be able to simplify EXPR by copy/constant | |
1554 propagation, and vice versa. Fold does not handle this, since it is | |
1555 considered too expensive. */ | |
1556 if (TREE_CODE (cond) == EQ_EXPR) | |
1557 { | |
1558 e0 = TREE_OPERAND (cond, 0); | |
1559 e1 = TREE_OPERAND (cond, 1); | |
1560 | |
1561 /* We know that e0 == e1. Check whether we cannot simplify expr | |
1562 using this fact. */ | |
1563 e = simplify_replace_tree (expr, e0, e1); | |
1564 if (integer_zerop (e) || integer_nonzerop (e)) | |
1565 return e; | |
1566 | |
1567 e = simplify_replace_tree (expr, e1, e0); | |
1568 if (integer_zerop (e) || integer_nonzerop (e)) | |
1569 return e; | |
1570 } | |
1571 if (TREE_CODE (expr) == EQ_EXPR) | |
1572 { | |
1573 e0 = TREE_OPERAND (expr, 0); | |
1574 e1 = TREE_OPERAND (expr, 1); | |
1575 | |
1576 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ | |
1577 e = simplify_replace_tree (cond, e0, e1); | |
1578 if (integer_zerop (e)) | |
1579 return e; | |
1580 e = simplify_replace_tree (cond, e1, e0); | |
1581 if (integer_zerop (e)) | |
1582 return e; | |
1583 } | |
1584 if (TREE_CODE (expr) == NE_EXPR) | |
1585 { | |
1586 e0 = TREE_OPERAND (expr, 0); | |
1587 e1 = TREE_OPERAND (expr, 1); | |
1588 | |
1589 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ | |
1590 e = simplify_replace_tree (cond, e0, e1); | |
1591 if (integer_zerop (e)) | |
1592 return boolean_true_node; | |
1593 e = simplify_replace_tree (cond, e1, e0); | |
1594 if (integer_zerop (e)) | |
1595 return boolean_true_node; | |
1596 } | |
1597 | |
1598 te = expand_simple_operations (expr); | |
1599 | |
1600 /* Check whether COND ==> EXPR. */ | |
1601 notcond = invert_truthvalue (cond); | |
1602 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); | |
1603 if (e && integer_nonzerop (e)) | |
1604 return e; | |
1605 | |
1606 /* Check whether COND ==> not EXPR. */ | |
1607 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); | |
1608 if (e && integer_zerop (e)) | |
1609 return e; | |
1610 | |
1611 return expr; | |
1612 } | |
1613 | |
1614 /* Tries to simplify EXPR using the condition COND. Returns the simplified | |
1615 expression (or EXPR unchanged, if no simplification was possible). | |
1616 Wrapper around tree_simplify_using_condition_1 that ensures that chains | |
1617 of simple operations in definitions of ssa names in COND are expanded, | |
1618 so that things like casts or incrementing the value of the bound before | |
1619 the loop do not cause us to fail. */ | |
1620 | |
1621 static tree | |
1622 tree_simplify_using_condition (tree cond, tree expr) | |
1623 { | |
1624 cond = expand_simple_operations (cond); | |
1625 | |
1626 return tree_simplify_using_condition_1 (cond, expr); | |
1627 } | |
1628 | |
1629 /* Tries to simplify EXPR using the conditions on entry to LOOP. | |
1630 Returns the simplified expression (or EXPR unchanged, if no | |
1631 simplification was possible).*/ | |
1632 | |
1633 static tree | |
1634 simplify_using_initial_conditions (struct loop *loop, tree expr) | |
1635 { | |
1636 edge e; | |
1637 basic_block bb; | |
1638 gimple stmt; | |
1639 tree cond; | |
1640 int cnt = 0; | |
1641 | |
1642 if (TREE_CODE (expr) == INTEGER_CST) | |
1643 return expr; | |
1644 | |
1645 /* Limit walking the dominators to avoid quadraticness in | |
1646 the number of BBs times the number of loops in degenerate | |
1647 cases. */ | |
1648 for (bb = loop->header; | |
1649 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; | |
1650 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |
1651 { | |
1652 if (!single_pred_p (bb)) | |
1653 continue; | |
1654 e = single_pred_edge (bb); | |
1655 | |
1656 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) | |
1657 continue; | |
1658 | |
1659 stmt = last_stmt (e->src); | |
1660 cond = fold_build2 (gimple_cond_code (stmt), | |
1661 boolean_type_node, | |
1662 gimple_cond_lhs (stmt), | |
1663 gimple_cond_rhs (stmt)); | |
1664 if (e->flags & EDGE_FALSE_VALUE) | |
1665 cond = invert_truthvalue (cond); | |
1666 expr = tree_simplify_using_condition (cond, expr); | |
1667 ++cnt; | |
1668 } | |
1669 | |
1670 return expr; | |
1671 } | |
1672 | |
1673 /* Tries to simplify EXPR using the evolutions of the loop invariants | |
1674 in the superloops of LOOP. Returns the simplified expression | |
1675 (or EXPR unchanged, if no simplification was possible). */ | |
1676 | |
1677 static tree | |
1678 simplify_using_outer_evolutions (struct loop *loop, tree expr) | |
1679 { | |
1680 enum tree_code code = TREE_CODE (expr); | |
1681 bool changed; | |
1682 tree e, e0, e1, e2; | |
1683 | |
1684 if (is_gimple_min_invariant (expr)) | |
1685 return expr; | |
1686 | |
1687 if (code == TRUTH_OR_EXPR | |
1688 || code == TRUTH_AND_EXPR | |
1689 || code == COND_EXPR) | |
1690 { | |
1691 changed = false; | |
1692 | |
1693 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); | |
1694 if (TREE_OPERAND (expr, 0) != e0) | |
1695 changed = true; | |
1696 | |
1697 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); | |
1698 if (TREE_OPERAND (expr, 1) != e1) | |
1699 changed = true; | |
1700 | |
1701 if (code == COND_EXPR) | |
1702 { | |
1703 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); | |
1704 if (TREE_OPERAND (expr, 2) != e2) | |
1705 changed = true; | |
1706 } | |
1707 else | |
1708 e2 = NULL_TREE; | |
1709 | |
1710 if (changed) | |
1711 { | |
1712 if (code == COND_EXPR) | |
1713 expr = fold_build3 (code, boolean_type_node, e0, e1, e2); | |
1714 else | |
1715 expr = fold_build2 (code, boolean_type_node, e0, e1); | |
1716 } | |
1717 | |
1718 return expr; | |
1719 } | |
1720 | |
1721 e = instantiate_parameters (loop, expr); | |
1722 if (is_gimple_min_invariant (e)) | |
1723 return e; | |
1724 | |
1725 return expr; | |
1726 } | |
1727 | |
1728 /* Returns true if EXIT is the only possible exit from LOOP. */ | |
1729 | |
1730 bool | |
1731 loop_only_exit_p (const struct loop *loop, const_edge exit) | |
1732 { | |
1733 basic_block *body; | |
1734 gimple_stmt_iterator bsi; | |
1735 unsigned i; | |
1736 gimple call; | |
1737 | |
1738 if (exit != single_exit (loop)) | |
1739 return false; | |
1740 | |
1741 body = get_loop_body (loop); | |
1742 for (i = 0; i < loop->num_nodes; i++) | |
1743 { | |
1744 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) | |
1745 { | |
1746 call = gsi_stmt (bsi); | |
1747 if (gimple_code (call) != GIMPLE_CALL) | |
1748 continue; | |
1749 | |
1750 if (gimple_has_side_effects (call)) | |
1751 { | |
1752 free (body); | |
1753 return false; | |
1754 } | |
1755 } | |
1756 } | |
1757 | |
1758 free (body); | |
1759 return true; | |
1760 } | |
1761 | |
1762 /* Stores description of number of iterations of LOOP derived from | |
1763 EXIT (an exit edge of the LOOP) in NITER. Returns true if some | |
1764 useful information could be derived (and fields of NITER has | |
1765 meaning described in comments at struct tree_niter_desc | |
1766 declaration), false otherwise. If WARN is true and | |
1767 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use | |
1768 potentially unsafe assumptions. */ | |
1769 | |
1770 bool | |
1771 number_of_iterations_exit (struct loop *loop, edge exit, | |
1772 struct tree_niter_desc *niter, | |
1773 bool warn) | |
1774 { | |
1775 gimple stmt; | |
1776 tree type; | |
1777 tree op0, op1; | |
1778 enum tree_code code; | |
1779 affine_iv iv0, iv1; | |
1780 | |
1781 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) | |
1782 return false; | |
1783 | |
1784 niter->assumptions = boolean_false_node; | |
1785 stmt = last_stmt (exit->src); | |
1786 if (!stmt || gimple_code (stmt) != GIMPLE_COND) | |
1787 return false; | |
1788 | |
1789 /* We want the condition for staying inside loop. */ | |
1790 code = gimple_cond_code (stmt); | |
1791 if (exit->flags & EDGE_TRUE_VALUE) | |
1792 code = invert_tree_comparison (code, false); | |
1793 | |
1794 switch (code) | |
1795 { | |
1796 case GT_EXPR: | |
1797 case GE_EXPR: | |
1798 case NE_EXPR: | |
1799 case LT_EXPR: | |
1800 case LE_EXPR: | |
1801 break; | |
1802 | |
1803 default: | |
1804 return false; | |
1805 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1806 |
0 | 1807 op0 = gimple_cond_lhs (stmt); |
1808 op1 = gimple_cond_rhs (stmt); | |
1809 type = TREE_TYPE (op0); | |
1810 | |
1811 if (TREE_CODE (type) != INTEGER_TYPE | |
1812 && !POINTER_TYPE_P (type)) | |
1813 return false; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1814 |
0 | 1815 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) |
1816 return false; | |
1817 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) | |
1818 return false; | |
1819 | |
1820 /* We don't want to see undefined signed overflow warnings while | |
1821 computing the number of iterations. */ | |
1822 fold_defer_overflow_warnings (); | |
1823 | |
1824 iv0.base = expand_simple_operations (iv0.base); | |
1825 iv1.base = expand_simple_operations (iv1.base); | |
1826 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, | |
1827 loop_only_exit_p (loop, exit))) | |
1828 { | |
1829 fold_undefer_and_ignore_overflow_warnings (); | |
1830 return false; | |
1831 } | |
1832 | |
1833 if (optimize >= 3) | |
1834 { | |
1835 niter->assumptions = simplify_using_outer_evolutions (loop, | |
1836 niter->assumptions); | |
1837 niter->may_be_zero = simplify_using_outer_evolutions (loop, | |
1838 niter->may_be_zero); | |
1839 niter->niter = simplify_using_outer_evolutions (loop, niter->niter); | |
1840 } | |
1841 | |
1842 niter->assumptions | |
1843 = simplify_using_initial_conditions (loop, | |
1844 niter->assumptions); | |
1845 niter->may_be_zero | |
1846 = simplify_using_initial_conditions (loop, | |
1847 niter->may_be_zero); | |
1848 | |
1849 fold_undefer_and_ignore_overflow_warnings (); | |
1850 | |
1851 if (integer_onep (niter->assumptions)) | |
1852 return true; | |
1853 | |
1854 /* With -funsafe-loop-optimizations we assume that nothing bad can happen. | |
1855 But if we can prove that there is overflow or some other source of weird | |
1856 behavior, ignore the loop even with -funsafe-loop-optimizations. */ | |
1857 if (integer_zerop (niter->assumptions)) | |
1858 return false; | |
1859 | |
1860 if (flag_unsafe_loop_optimizations) | |
1861 niter->assumptions = boolean_true_node; | |
1862 | |
1863 if (warn) | |
1864 { | |
1865 const char *wording; | |
1866 location_t loc = gimple_location (stmt); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1867 |
0 | 1868 /* We can provide a more specific warning if one of the operator is |
1869 constant and the other advances by +1 or -1. */ | |
1870 if (!integer_zerop (iv1.step) | |
1871 ? (integer_zerop (iv0.step) | |
1872 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) | |
1873 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step))) | |
1874 wording = | |
1875 flag_unsafe_loop_optimizations | |
1876 ? N_("assuming that the loop is not infinite") | |
1877 : N_("cannot optimize possibly infinite loops"); | |
1878 else | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1879 wording = |
0 | 1880 flag_unsafe_loop_optimizations |
1881 ? N_("assuming that the loop counter does not overflow") | |
1882 : N_("cannot optimize loop, the loop counter may overflow"); | |
1883 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1884 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1885 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); |
0 | 1886 } |
1887 | |
1888 return flag_unsafe_loop_optimizations; | |
1889 } | |
1890 | |
1891 /* Try to determine the number of iterations of LOOP. If we succeed, | |
1892 expression giving number of iterations is returned and *EXIT is | |
1893 set to the edge from that the information is obtained. Otherwise | |
1894 chrec_dont_know is returned. */ | |
1895 | |
1896 tree | |
1897 find_loop_niter (struct loop *loop, edge *exit) | |
1898 { | |
1899 unsigned i; | |
1900 VEC (edge, heap) *exits = get_loop_exit_edges (loop); | |
1901 edge ex; | |
1902 tree niter = NULL_TREE, aniter; | |
1903 struct tree_niter_desc desc; | |
1904 | |
1905 *exit = NULL; | |
1906 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) | |
1907 { | |
1908 if (!just_once_each_iteration_p (loop, ex->src)) | |
1909 continue; | |
1910 | |
1911 if (!number_of_iterations_exit (loop, ex, &desc, false)) | |
1912 continue; | |
1913 | |
1914 if (integer_nonzerop (desc.may_be_zero)) | |
1915 { | |
1916 /* We exit in the first iteration through this exit. | |
1917 We won't find anything better. */ | |
1918 niter = build_int_cst (unsigned_type_node, 0); | |
1919 *exit = ex; | |
1920 break; | |
1921 } | |
1922 | |
1923 if (!integer_zerop (desc.may_be_zero)) | |
1924 continue; | |
1925 | |
1926 aniter = desc.niter; | |
1927 | |
1928 if (!niter) | |
1929 { | |
1930 /* Nothing recorded yet. */ | |
1931 niter = aniter; | |
1932 *exit = ex; | |
1933 continue; | |
1934 } | |
1935 | |
1936 /* Prefer constants, the lower the better. */ | |
1937 if (TREE_CODE (aniter) != INTEGER_CST) | |
1938 continue; | |
1939 | |
1940 if (TREE_CODE (niter) != INTEGER_CST) | |
1941 { | |
1942 niter = aniter; | |
1943 *exit = ex; | |
1944 continue; | |
1945 } | |
1946 | |
1947 if (tree_int_cst_lt (aniter, niter)) | |
1948 { | |
1949 niter = aniter; | |
1950 *exit = ex; | |
1951 continue; | |
1952 } | |
1953 } | |
1954 VEC_free (edge, heap, exits); | |
1955 | |
1956 return niter ? niter : chrec_dont_know; | |
1957 } | |
1958 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1959 /* Return true if loop is known to have bounded number of iterations. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1960 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1961 bool |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1962 finite_loop_p (struct loop *loop) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1963 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1964 unsigned i; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1965 VEC (edge, heap) *exits; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1966 edge ex; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1967 struct tree_niter_desc desc; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1968 bool finite = false; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1969 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1970 if (flag_unsafe_loop_optimizations) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1971 return true; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1972 if ((TREE_READONLY (current_function_decl) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1973 || DECL_PURE_P (current_function_decl)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1974 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1975 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1976 if (dump_file && (dump_flags & TDF_DETAILS)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1977 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1978 loop->num); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1979 return true; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1980 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1981 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1982 exits = get_loop_exit_edges (loop); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1983 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1984 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1985 if (!just_once_each_iteration_p (loop, ex->src)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1986 continue; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1987 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1988 if (number_of_iterations_exit (loop, ex, &desc, false)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1989 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1990 if (dump_file && (dump_flags & TDF_DETAILS)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1991 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1992 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1993 print_generic_expr (dump_file, desc.niter, TDF_SLIM); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1994 fprintf (dump_file, " times\n"); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1995 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1996 finite = true; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1997 break; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1998 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
1999 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2000 VEC_free (edge, heap, exits); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2001 return finite; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2002 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2003 |
0 | 2004 /* |
2005 | |
2006 Analysis of a number of iterations of a loop by a brute-force evaluation. | |
2007 | |
2008 */ | |
2009 | |
2010 /* Bound on the number of iterations we try to evaluate. */ | |
2011 | |
2012 #define MAX_ITERATIONS_TO_TRACK \ | |
2013 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) | |
2014 | |
2015 /* Returns the loop phi node of LOOP such that ssa name X is derived from its | |
2016 result by a chain of operations such that all but exactly one of their | |
2017 operands are constants. */ | |
2018 | |
2019 static gimple | |
2020 chain_of_csts_start (struct loop *loop, tree x) | |
2021 { | |
2022 gimple stmt = SSA_NAME_DEF_STMT (x); | |
2023 tree use; | |
2024 basic_block bb = gimple_bb (stmt); | |
2025 enum tree_code code; | |
2026 | |
2027 if (!bb | |
2028 || !flow_bb_inside_loop_p (loop, bb)) | |
2029 return NULL; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2030 |
0 | 2031 if (gimple_code (stmt) == GIMPLE_PHI) |
2032 { | |
2033 if (bb == loop->header) | |
2034 return stmt; | |
2035 | |
2036 return NULL; | |
2037 } | |
2038 | |
2039 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
2040 return NULL; | |
2041 | |
2042 code = gimple_assign_rhs_code (stmt); | |
2043 if (gimple_references_memory_p (stmt) | |
2044 || TREE_CODE_CLASS (code) == tcc_reference | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2045 || (code == ADDR_EXPR |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2046 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) |
0 | 2047 return NULL; |
2048 | |
2049 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2050 if (use == NULL_TREE) |
0 | 2051 return NULL; |
2052 | |
2053 return chain_of_csts_start (loop, use); | |
2054 } | |
2055 | |
2056 /* Determines whether the expression X is derived from a result of a phi node | |
2057 in header of LOOP such that | |
2058 | |
2059 * the derivation of X consists only from operations with constants | |
2060 * the initial value of the phi node is constant | |
2061 * the value of the phi node in the next iteration can be derived from the | |
2062 value in the current iteration by a chain of operations with constants. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2063 |
0 | 2064 If such phi node exists, it is returned, otherwise NULL is returned. */ |
2065 | |
2066 static gimple | |
2067 get_base_for (struct loop *loop, tree x) | |
2068 { | |
2069 gimple phi; | |
2070 tree init, next; | |
2071 | |
2072 if (is_gimple_min_invariant (x)) | |
2073 return NULL; | |
2074 | |
2075 phi = chain_of_csts_start (loop, x); | |
2076 if (!phi) | |
2077 return NULL; | |
2078 | |
2079 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
2080 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); | |
2081 | |
2082 if (TREE_CODE (next) != SSA_NAME) | |
2083 return NULL; | |
2084 | |
2085 if (!is_gimple_min_invariant (init)) | |
2086 return NULL; | |
2087 | |
2088 if (chain_of_csts_start (loop, next) != phi) | |
2089 return NULL; | |
2090 | |
2091 return phi; | |
2092 } | |
2093 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2094 /* Given an expression X, then |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2095 |
0 | 2096 * if X is NULL_TREE, we return the constant BASE. |
2097 * otherwise X is a SSA name, whose value in the considered loop is derived | |
2098 by a chain of operations with constant from a result of a phi node in | |
2099 the header of the loop. Then we return value of X when the value of the | |
2100 result of this phi node is given by the constant BASE. */ | |
2101 | |
2102 static tree | |
2103 get_val_for (tree x, tree base) | |
2104 { | |
2105 gimple stmt; | |
2106 | |
2107 gcc_assert (is_gimple_min_invariant (base)); | |
2108 | |
2109 if (!x) | |
2110 return base; | |
2111 | |
2112 stmt = SSA_NAME_DEF_STMT (x); | |
2113 if (gimple_code (stmt) == GIMPLE_PHI) | |
2114 return base; | |
2115 | |
2116 gcc_assert (is_gimple_assign (stmt)); | |
2117 | |
2118 /* STMT must be either an assignment of a single SSA name or an | |
2119 expression involving an SSA name and a constant. Try to fold that | |
2120 expression using the value for the SSA name. */ | |
2121 if (gimple_assign_ssa_name_copy_p (stmt)) | |
2122 return get_val_for (gimple_assign_rhs1 (stmt), base); | |
2123 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS | |
2124 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
2125 { | |
2126 return fold_build1 (gimple_assign_rhs_code (stmt), | |
2127 gimple_expr_type (stmt), | |
2128 get_val_for (gimple_assign_rhs1 (stmt), base)); | |
2129 } | |
2130 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS) | |
2131 { | |
2132 tree rhs1 = gimple_assign_rhs1 (stmt); | |
2133 tree rhs2 = gimple_assign_rhs2 (stmt); | |
2134 if (TREE_CODE (rhs1) == SSA_NAME) | |
2135 rhs1 = get_val_for (rhs1, base); | |
2136 else if (TREE_CODE (rhs2) == SSA_NAME) | |
2137 rhs2 = get_val_for (rhs2, base); | |
2138 else | |
2139 gcc_unreachable (); | |
2140 return fold_build2 (gimple_assign_rhs_code (stmt), | |
2141 gimple_expr_type (stmt), rhs1, rhs2); | |
2142 } | |
2143 else | |
2144 gcc_unreachable (); | |
2145 } | |
2146 | |
2147 | |
2148 /* Tries to count the number of iterations of LOOP till it exits by EXIT | |
2149 by brute force -- i.e. by determining the value of the operands of the | |
2150 condition at EXIT in first few iterations of the loop (assuming that | |
2151 these values are constant) and determining the first one in that the | |
2152 condition is not satisfied. Returns the constant giving the number | |
2153 of the iterations of LOOP if successful, chrec_dont_know otherwise. */ | |
2154 | |
2155 tree | |
2156 loop_niter_by_eval (struct loop *loop, edge exit) | |
2157 { | |
2158 tree acnd; | |
2159 tree op[2], val[2], next[2], aval[2]; | |
2160 gimple phi, cond; | |
2161 unsigned i, j; | |
2162 enum tree_code cmp; | |
2163 | |
2164 cond = last_stmt (exit->src); | |
2165 if (!cond || gimple_code (cond) != GIMPLE_COND) | |
2166 return chrec_dont_know; | |
2167 | |
2168 cmp = gimple_cond_code (cond); | |
2169 if (exit->flags & EDGE_TRUE_VALUE) | |
2170 cmp = invert_tree_comparison (cmp, false); | |
2171 | |
2172 switch (cmp) | |
2173 { | |
2174 case EQ_EXPR: | |
2175 case NE_EXPR: | |
2176 case GT_EXPR: | |
2177 case GE_EXPR: | |
2178 case LT_EXPR: | |
2179 case LE_EXPR: | |
2180 op[0] = gimple_cond_lhs (cond); | |
2181 op[1] = gimple_cond_rhs (cond); | |
2182 break; | |
2183 | |
2184 default: | |
2185 return chrec_dont_know; | |
2186 } | |
2187 | |
2188 for (j = 0; j < 2; j++) | |
2189 { | |
2190 if (is_gimple_min_invariant (op[j])) | |
2191 { | |
2192 val[j] = op[j]; | |
2193 next[j] = NULL_TREE; | |
2194 op[j] = NULL_TREE; | |
2195 } | |
2196 else | |
2197 { | |
2198 phi = get_base_for (loop, op[j]); | |
2199 if (!phi) | |
2200 return chrec_dont_know; | |
2201 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |
2202 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); | |
2203 } | |
2204 } | |
2205 | |
2206 /* Don't issue signed overflow warnings. */ | |
2207 fold_defer_overflow_warnings (); | |
2208 | |
2209 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) | |
2210 { | |
2211 for (j = 0; j < 2; j++) | |
2212 aval[j] = get_val_for (op[j], val[j]); | |
2213 | |
2214 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); | |
2215 if (acnd && integer_zerop (acnd)) | |
2216 { | |
2217 fold_undefer_and_ignore_overflow_warnings (); | |
2218 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2219 fprintf (dump_file, | |
2220 "Proved that loop %d iterates %d times using brute force.\n", | |
2221 loop->num, i); | |
2222 return build_int_cst (unsigned_type_node, i); | |
2223 } | |
2224 | |
2225 for (j = 0; j < 2; j++) | |
2226 { | |
2227 val[j] = get_val_for (next[j], val[j]); | |
2228 if (!is_gimple_min_invariant (val[j])) | |
2229 { | |
2230 fold_undefer_and_ignore_overflow_warnings (); | |
2231 return chrec_dont_know; | |
2232 } | |
2233 } | |
2234 } | |
2235 | |
2236 fold_undefer_and_ignore_overflow_warnings (); | |
2237 | |
2238 return chrec_dont_know; | |
2239 } | |
2240 | |
2241 /* Finds the exit of the LOOP by that the loop exits after a constant | |
2242 number of iterations and stores the exit edge to *EXIT. The constant | |
2243 giving the number of iterations of LOOP is returned. The number of | |
2244 iterations is determined using loop_niter_by_eval (i.e. by brute force | |
2245 evaluation). If we are unable to find the exit for that loop_niter_by_eval | |
2246 determines the number of iterations, chrec_dont_know is returned. */ | |
2247 | |
2248 tree | |
2249 find_loop_niter_by_eval (struct loop *loop, edge *exit) | |
2250 { | |
2251 unsigned i; | |
2252 VEC (edge, heap) *exits = get_loop_exit_edges (loop); | |
2253 edge ex; | |
2254 tree niter = NULL_TREE, aniter; | |
2255 | |
2256 *exit = NULL; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2257 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2258 /* Loops with multiple exits are expensive to handle and less important. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2259 if (!flag_expensive_optimizations |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2260 && VEC_length (edge, exits) > 1) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2261 return chrec_dont_know; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2262 |
0 | 2263 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) |
2264 { | |
2265 if (!just_once_each_iteration_p (loop, ex->src)) | |
2266 continue; | |
2267 | |
2268 aniter = loop_niter_by_eval (loop, ex); | |
2269 if (chrec_contains_undetermined (aniter)) | |
2270 continue; | |
2271 | |
2272 if (niter | |
2273 && !tree_int_cst_lt (aniter, niter)) | |
2274 continue; | |
2275 | |
2276 niter = aniter; | |
2277 *exit = ex; | |
2278 } | |
2279 VEC_free (edge, heap, exits); | |
2280 | |
2281 return niter ? niter : chrec_dont_know; | |
2282 } | |
2283 | |
2284 /* | |
2285 | |
2286 Analysis of upper bounds on number of iterations of a loop. | |
2287 | |
2288 */ | |
2289 | |
2290 static double_int derive_constant_upper_bound_ops (tree, tree, | |
2291 enum tree_code, tree); | |
2292 | |
2293 /* Returns a constant upper bound on the value of the right-hand side of | |
2294 an assignment statement STMT. */ | |
2295 | |
2296 static double_int | |
2297 derive_constant_upper_bound_assign (gimple stmt) | |
2298 { | |
2299 enum tree_code code = gimple_assign_rhs_code (stmt); | |
2300 tree op0 = gimple_assign_rhs1 (stmt); | |
2301 tree op1 = gimple_assign_rhs2 (stmt); | |
2302 | |
2303 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)), | |
2304 op0, code, op1); | |
2305 } | |
2306 | |
2307 /* Returns a constant upper bound on the value of expression VAL. VAL | |
2308 is considered to be unsigned. If its type is signed, its value must | |
2309 be nonnegative. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2310 |
0 | 2311 static double_int |
2312 derive_constant_upper_bound (tree val) | |
2313 { | |
2314 enum tree_code code; | |
2315 tree op0, op1; | |
2316 | |
2317 extract_ops_from_tree (val, &code, &op0, &op1); | |
2318 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1); | |
2319 } | |
2320 | |
2321 /* Returns a constant upper bound on the value of expression OP0 CODE OP1, | |
2322 whose type is TYPE. The expression is considered to be unsigned. If | |
2323 its type is signed, its value must be nonnegative. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2324 |
0 | 2325 static double_int |
2326 derive_constant_upper_bound_ops (tree type, tree op0, | |
2327 enum tree_code code, tree op1) | |
2328 { | |
2329 tree subtype, maxt; | |
2330 double_int bnd, max, mmax, cst; | |
2331 gimple stmt; | |
2332 | |
2333 if (INTEGRAL_TYPE_P (type)) | |
2334 maxt = TYPE_MAX_VALUE (type); | |
2335 else | |
2336 maxt = upper_bound_in_type (type, type); | |
2337 | |
2338 max = tree_to_double_int (maxt); | |
2339 | |
2340 switch (code) | |
2341 { | |
2342 case INTEGER_CST: | |
2343 return tree_to_double_int (op0); | |
2344 | |
2345 CASE_CONVERT: | |
2346 subtype = TREE_TYPE (op0); | |
2347 if (!TYPE_UNSIGNED (subtype) | |
2348 /* If TYPE is also signed, the fact that VAL is nonnegative implies | |
2349 that OP0 is nonnegative. */ | |
2350 && TYPE_UNSIGNED (type) | |
2351 && !tree_expr_nonnegative_p (op0)) | |
2352 { | |
2353 /* If we cannot prove that the casted expression is nonnegative, | |
2354 we cannot establish more useful upper bound than the precision | |
2355 of the type gives us. */ | |
2356 return max; | |
2357 } | |
2358 | |
2359 /* We now know that op0 is an nonnegative value. Try deriving an upper | |
2360 bound for it. */ | |
2361 bnd = derive_constant_upper_bound (op0); | |
2362 | |
2363 /* If the bound does not fit in TYPE, max. value of TYPE could be | |
2364 attained. */ | |
2365 if (double_int_ucmp (max, bnd) < 0) | |
2366 return max; | |
2367 | |
2368 return bnd; | |
2369 | |
2370 case PLUS_EXPR: | |
2371 case POINTER_PLUS_EXPR: | |
2372 case MINUS_EXPR: | |
2373 if (TREE_CODE (op1) != INTEGER_CST | |
2374 || !tree_expr_nonnegative_p (op0)) | |
2375 return max; | |
2376 | |
2377 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to | |
2378 choose the most logical way how to treat this constant regardless | |
2379 of the signedness of the type. */ | |
2380 cst = tree_to_double_int (op1); | |
2381 cst = double_int_sext (cst, TYPE_PRECISION (type)); | |
2382 if (code != MINUS_EXPR) | |
2383 cst = double_int_neg (cst); | |
2384 | |
2385 bnd = derive_constant_upper_bound (op0); | |
2386 | |
2387 if (double_int_negative_p (cst)) | |
2388 { | |
2389 cst = double_int_neg (cst); | |
2390 /* Avoid CST == 0x80000... */ | |
2391 if (double_int_negative_p (cst)) | |
2392 return max;; | |
2393 | |
2394 /* OP0 + CST. We need to check that | |
2395 BND <= MAX (type) - CST. */ | |
2396 | |
2397 mmax = double_int_add (max, double_int_neg (cst)); | |
2398 if (double_int_ucmp (bnd, mmax) > 0) | |
2399 return max; | |
2400 | |
2401 return double_int_add (bnd, cst); | |
2402 } | |
2403 else | |
2404 { | |
2405 /* OP0 - CST, where CST >= 0. | |
2406 | |
2407 If TYPE is signed, we have already verified that OP0 >= 0, and we | |
2408 know that the result is nonnegative. This implies that | |
2409 VAL <= BND - CST. | |
2410 | |
2411 If TYPE is unsigned, we must additionally know that OP0 >= CST, | |
2412 otherwise the operation underflows. | |
2413 */ | |
2414 | |
2415 /* This should only happen if the type is unsigned; however, for | |
2416 buggy programs that use overflowing signed arithmetics even with | |
2417 -fno-wrapv, this condition may also be true for signed values. */ | |
2418 if (double_int_ucmp (bnd, cst) < 0) | |
2419 return max; | |
2420 | |
2421 if (TYPE_UNSIGNED (type)) | |
2422 { | |
2423 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, | |
2424 double_int_to_tree (type, cst)); | |
2425 if (!tem || integer_nonzerop (tem)) | |
2426 return max; | |
2427 } | |
2428 | |
2429 bnd = double_int_add (bnd, double_int_neg (cst)); | |
2430 } | |
2431 | |
2432 return bnd; | |
2433 | |
2434 case FLOOR_DIV_EXPR: | |
2435 case EXACT_DIV_EXPR: | |
2436 if (TREE_CODE (op1) != INTEGER_CST | |
2437 || tree_int_cst_sign_bit (op1)) | |
2438 return max; | |
2439 | |
2440 bnd = derive_constant_upper_bound (op0); | |
2441 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); | |
2442 | |
2443 case BIT_AND_EXPR: | |
2444 if (TREE_CODE (op1) != INTEGER_CST | |
2445 || tree_int_cst_sign_bit (op1)) | |
2446 return max; | |
2447 return tree_to_double_int (op1); | |
2448 | |
2449 case SSA_NAME: | |
2450 stmt = SSA_NAME_DEF_STMT (op0); | |
2451 if (gimple_code (stmt) != GIMPLE_ASSIGN | |
2452 || gimple_assign_lhs (stmt) != op0) | |
2453 return max; | |
2454 return derive_constant_upper_bound_assign (stmt); | |
2455 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2456 default: |
0 | 2457 return max; |
2458 } | |
2459 } | |
2460 | |
2461 /* Records that every statement in LOOP is executed I_BOUND times. | |
2462 REALISTIC is true if I_BOUND is expected to be close to the real number | |
2463 of iterations. UPPER is true if we are sure the loop iterates at most | |
2464 I_BOUND times. */ | |
2465 | |
2466 static void | |
2467 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, | |
2468 bool upper) | |
2469 { | |
2470 /* Update the bounds only when there is no previous estimation, or when the current | |
2471 estimation is smaller. */ | |
2472 if (upper | |
2473 && (!loop->any_upper_bound | |
2474 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0)) | |
2475 { | |
2476 loop->any_upper_bound = true; | |
2477 loop->nb_iterations_upper_bound = i_bound; | |
2478 } | |
2479 if (realistic | |
2480 && (!loop->any_estimate | |
2481 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0)) | |
2482 { | |
2483 loop->any_estimate = true; | |
2484 loop->nb_iterations_estimate = i_bound; | |
2485 } | |
2486 } | |
2487 | |
2488 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT | |
2489 is true if the loop is exited immediately after STMT, and this exit | |
2490 is taken at last when the STMT is executed BOUND + 1 times. | |
2491 REALISTIC is true if BOUND is expected to be close to the real number | |
2492 of iterations. UPPER is true if we are sure the loop iterates at most | |
2493 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */ | |
2494 | |
2495 static void | |
2496 record_estimate (struct loop *loop, tree bound, double_int i_bound, | |
2497 gimple at_stmt, bool is_exit, bool realistic, bool upper) | |
2498 { | |
2499 double_int delta; | |
2500 edge exit; | |
2501 | |
2502 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2503 { | |
2504 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : ""); | |
2505 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM); | |
2506 fprintf (dump_file, " is %sexecuted at most ", | |
2507 upper ? "" : "probably "); | |
2508 print_generic_expr (dump_file, bound, TDF_SLIM); | |
2509 fprintf (dump_file, " (bounded by "); | |
2510 dump_double_int (dump_file, i_bound, true); | |
2511 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num); | |
2512 } | |
2513 | |
2514 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the | |
2515 real number of iterations. */ | |
2516 if (TREE_CODE (bound) != INTEGER_CST) | |
2517 realistic = false; | |
2518 if (!upper && !realistic) | |
2519 return; | |
2520 | |
2521 /* If we have a guaranteed upper bound, record it in the appropriate | |
2522 list. */ | |
2523 if (upper) | |
2524 { | |
2525 struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound); | |
2526 | |
2527 elt->bound = i_bound; | |
2528 elt->stmt = at_stmt; | |
2529 elt->is_exit = is_exit; | |
2530 elt->next = loop->bounds; | |
2531 loop->bounds = elt; | |
2532 } | |
2533 | |
2534 /* Update the number of iteration estimates according to the bound. | |
2535 If at_stmt is an exit, then every statement in the loop is | |
2536 executed at most BOUND + 1 times. If it is not an exit, then | |
2537 some of the statements before it could be executed BOUND + 2 | |
2538 times, if an exit of LOOP is before stmt. */ | |
2539 exit = single_exit (loop); | |
2540 if (is_exit | |
2541 || (exit != NULL | |
2542 && dominated_by_p (CDI_DOMINATORS, | |
2543 exit->src, gimple_bb (at_stmt)))) | |
2544 delta = double_int_one; | |
2545 else | |
2546 delta = double_int_two; | |
2547 i_bound = double_int_add (i_bound, delta); | |
2548 | |
2549 /* If an overflow occurred, ignore the result. */ | |
2550 if (double_int_ucmp (i_bound, delta) < 0) | |
2551 return; | |
2552 | |
2553 record_niter_bound (loop, i_bound, realistic, upper); | |
2554 } | |
2555 | |
2556 /* Record the estimate on number of iterations of LOOP based on the fact that | |
2557 the induction variable BASE + STEP * i evaluated in STMT does not wrap and | |
2558 its values belong to the range <LOW, HIGH>. REALISTIC is true if the | |
2559 estimated number of iterations is expected to be close to the real one. | |
2560 UPPER is true if we are sure the induction variable does not wrap. */ | |
2561 | |
2562 static void | |
2563 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, | |
2564 tree low, tree high, bool realistic, bool upper) | |
2565 { | |
2566 tree niter_bound, extreme, delta; | |
2567 tree type = TREE_TYPE (base), unsigned_type; | |
2568 double_int max; | |
2569 | |
2570 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) | |
2571 return; | |
2572 | |
2573 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2574 { | |
2575 fprintf (dump_file, "Induction variable ("); | |
2576 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM); | |
2577 fprintf (dump_file, ") "); | |
2578 print_generic_expr (dump_file, base, TDF_SLIM); | |
2579 fprintf (dump_file, " + "); | |
2580 print_generic_expr (dump_file, step, TDF_SLIM); | |
2581 fprintf (dump_file, " * iteration does not wrap in statement "); | |
2582 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
2583 fprintf (dump_file, " in loop %d.\n", loop->num); | |
2584 } | |
2585 | |
2586 unsigned_type = unsigned_type_for (type); | |
2587 base = fold_convert (unsigned_type, base); | |
2588 step = fold_convert (unsigned_type, step); | |
2589 | |
2590 if (tree_int_cst_sign_bit (step)) | |
2591 { | |
2592 extreme = fold_convert (unsigned_type, low); | |
2593 if (TREE_CODE (base) != INTEGER_CST) | |
2594 base = fold_convert (unsigned_type, high); | |
2595 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); | |
2596 step = fold_build1 (NEGATE_EXPR, unsigned_type, step); | |
2597 } | |
2598 else | |
2599 { | |
2600 extreme = fold_convert (unsigned_type, high); | |
2601 if (TREE_CODE (base) != INTEGER_CST) | |
2602 base = fold_convert (unsigned_type, low); | |
2603 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); | |
2604 } | |
2605 | |
2606 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value | |
2607 would get out of the range. */ | |
2608 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); | |
2609 max = derive_constant_upper_bound (niter_bound); | |
2610 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); | |
2611 } | |
2612 | |
2613 /* Returns true if REF is a reference to an array at the end of a dynamically | |
2614 allocated structure. If this is the case, the array may be allocated larger | |
2615 than its upper bound implies. */ | |
2616 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2617 bool |
0 | 2618 array_at_struct_end_p (tree ref) |
2619 { | |
2620 tree base = get_base_address (ref); | |
2621 tree parent, field; | |
2622 | |
2623 /* Unless the reference is through a pointer, the size of the array matches | |
2624 its declaration. */ | |
2625 if (!base || !INDIRECT_REF_P (base)) | |
2626 return false; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2627 |
0 | 2628 for (;handled_component_p (ref); ref = parent) |
2629 { | |
2630 parent = TREE_OPERAND (ref, 0); | |
2631 | |
2632 if (TREE_CODE (ref) == COMPONENT_REF) | |
2633 { | |
2634 /* All fields of a union are at its end. */ | |
2635 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE) | |
2636 continue; | |
2637 | |
2638 /* Unless the field is at the end of the struct, we are done. */ | |
2639 field = TREE_OPERAND (ref, 1); | |
2640 if (TREE_CHAIN (field)) | |
2641 return false; | |
2642 } | |
2643 | |
2644 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR. | |
2645 In all these cases, we might be accessing the last element, and | |
2646 although in practice this will probably never happen, it is legal for | |
2647 the indices of this last element to exceed the bounds of the array. | |
2648 Therefore, continue checking. */ | |
2649 } | |
2650 | |
2651 gcc_assert (INDIRECT_REF_P (ref)); | |
2652 return true; | |
2653 } | |
2654 | |
2655 /* Determine information about number of iterations a LOOP from the index | |
2656 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is | |
2657 guaranteed to be executed in every iteration of LOOP. Callback for | |
2658 for_each_index. */ | |
2659 | |
2660 struct ilb_data | |
2661 { | |
2662 struct loop *loop; | |
2663 gimple stmt; | |
2664 bool reliable; | |
2665 }; | |
2666 | |
2667 static bool | |
2668 idx_infer_loop_bounds (tree base, tree *idx, void *dta) | |
2669 { | |
2670 struct ilb_data *data = (struct ilb_data *) dta; | |
2671 tree ev, init, step; | |
2672 tree low, high, type, next; | |
2673 bool sign, upper = data->reliable, at_end = false; | |
2674 struct loop *loop = data->loop; | |
2675 | |
2676 if (TREE_CODE (base) != ARRAY_REF) | |
2677 return true; | |
2678 | |
2679 /* For arrays at the end of the structure, we are not guaranteed that they | |
2680 do not really extend over their declared size. However, for arrays of | |
2681 size greater than one, this is unlikely to be intended. */ | |
2682 if (array_at_struct_end_p (base)) | |
2683 { | |
2684 at_end = true; | |
2685 upper = false; | |
2686 } | |
2687 | |
2688 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx)); | |
2689 init = initial_condition (ev); | |
2690 step = evolution_part_in_loop_num (ev, loop->num); | |
2691 | |
2692 if (!init | |
2693 || !step | |
2694 || TREE_CODE (step) != INTEGER_CST | |
2695 || integer_zerop (step) | |
2696 || tree_contains_chrecs (init, NULL) | |
2697 || chrec_contains_symbols_defined_in_loop (init, loop->num)) | |
2698 return true; | |
2699 | |
2700 low = array_ref_low_bound (base); | |
2701 high = array_ref_up_bound (base); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2702 |
0 | 2703 /* The case of nonconstant bounds could be handled, but it would be |
2704 complicated. */ | |
2705 if (TREE_CODE (low) != INTEGER_CST | |
2706 || !high | |
2707 || TREE_CODE (high) != INTEGER_CST) | |
2708 return true; | |
2709 sign = tree_int_cst_sign_bit (step); | |
2710 type = TREE_TYPE (step); | |
2711 | |
2712 /* The array of length 1 at the end of a structure most likely extends | |
2713 beyond its bounds. */ | |
2714 if (at_end | |
2715 && operand_equal_p (low, high, 0)) | |
2716 return true; | |
2717 | |
2718 /* In case the relevant bound of the array does not fit in type, or | |
2719 it does, but bound + step (in type) still belongs into the range of the | |
2720 array, the index may wrap and still stay within the range of the array | |
2721 (consider e.g. if the array is indexed by the full range of | |
2722 unsigned char). | |
2723 | |
2724 To make things simpler, we require both bounds to fit into type, although | |
2725 there are cases where this would not be strictly necessary. */ | |
2726 if (!int_fits_type_p (high, type) | |
2727 || !int_fits_type_p (low, type)) | |
2728 return true; | |
2729 low = fold_convert (type, low); | |
2730 high = fold_convert (type, high); | |
2731 | |
2732 if (sign) | |
2733 next = fold_binary (PLUS_EXPR, type, low, step); | |
2734 else | |
2735 next = fold_binary (PLUS_EXPR, type, high, step); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2736 |
0 | 2737 if (tree_int_cst_compare (low, next) <= 0 |
2738 && tree_int_cst_compare (next, high) <= 0) | |
2739 return true; | |
2740 | |
2741 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); | |
2742 return true; | |
2743 } | |
2744 | |
2745 /* Determine information about number of iterations a LOOP from the bounds | |
2746 of arrays in the data reference REF accessed in STMT. RELIABLE is true if | |
2747 STMT is guaranteed to be executed in every iteration of LOOP.*/ | |
2748 | |
2749 static void | |
2750 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref, | |
2751 bool reliable) | |
2752 { | |
2753 struct ilb_data data; | |
2754 | |
2755 data.loop = loop; | |
2756 data.stmt = stmt; | |
2757 data.reliable = reliable; | |
2758 for_each_index (&ref, idx_infer_loop_bounds, &data); | |
2759 } | |
2760 | |
2761 /* Determine information about number of iterations of a LOOP from the way | |
2762 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be | |
2763 executed in every iteration of LOOP. */ | |
2764 | |
2765 static void | |
2766 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable) | |
2767 { | |
2768 if (is_gimple_assign (stmt)) | |
2769 { | |
2770 tree op0 = gimple_assign_lhs (stmt); | |
2771 tree op1 = gimple_assign_rhs1 (stmt); | |
2772 | |
2773 /* For each memory access, analyze its access function | |
2774 and record a bound on the loop iteration domain. */ | |
2775 if (REFERENCE_CLASS_P (op0)) | |
2776 infer_loop_bounds_from_ref (loop, stmt, op0, reliable); | |
2777 | |
2778 if (REFERENCE_CLASS_P (op1)) | |
2779 infer_loop_bounds_from_ref (loop, stmt, op1, reliable); | |
2780 } | |
2781 else if (is_gimple_call (stmt)) | |
2782 { | |
2783 tree arg, lhs; | |
2784 unsigned i, n = gimple_call_num_args (stmt); | |
2785 | |
2786 lhs = gimple_call_lhs (stmt); | |
2787 if (lhs && REFERENCE_CLASS_P (lhs)) | |
2788 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable); | |
2789 | |
2790 for (i = 0; i < n; i++) | |
2791 { | |
2792 arg = gimple_call_arg (stmt, i); | |
2793 if (REFERENCE_CLASS_P (arg)) | |
2794 infer_loop_bounds_from_ref (loop, stmt, arg, reliable); | |
2795 } | |
2796 } | |
2797 } | |
2798 | |
2799 /* Determine information about number of iterations of a LOOP from the fact | |
2800 that signed arithmetics in STMT does not overflow. */ | |
2801 | |
2802 static void | |
2803 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt) | |
2804 { | |
2805 tree def, base, step, scev, type, low, high; | |
2806 | |
2807 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
2808 return; | |
2809 | |
2810 def = gimple_assign_lhs (stmt); | |
2811 | |
2812 if (TREE_CODE (def) != SSA_NAME) | |
2813 return; | |
2814 | |
2815 type = TREE_TYPE (def); | |
2816 if (!INTEGRAL_TYPE_P (type) | |
2817 || !TYPE_OVERFLOW_UNDEFINED (type)) | |
2818 return; | |
2819 | |
2820 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); | |
2821 if (chrec_contains_undetermined (scev)) | |
2822 return; | |
2823 | |
2824 base = initial_condition_in_loop_num (scev, loop->num); | |
2825 step = evolution_part_in_loop_num (scev, loop->num); | |
2826 | |
2827 if (!base || !step | |
2828 || TREE_CODE (step) != INTEGER_CST | |
2829 || tree_contains_chrecs (base, NULL) | |
2830 || chrec_contains_symbols_defined_in_loop (base, loop->num)) | |
2831 return; | |
2832 | |
2833 low = lower_bound_in_type (type, type); | |
2834 high = upper_bound_in_type (type, type); | |
2835 | |
2836 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); | |
2837 } | |
2838 | |
2839 /* The following analyzers are extracting informations on the bounds | |
2840 of LOOP from the following undefined behaviors: | |
2841 | |
2842 - data references should not access elements over the statically | |
2843 allocated size, | |
2844 | |
2845 - signed variables should not overflow when flag_wrapv is not set. | |
2846 */ | |
2847 | |
2848 static void | |
2849 infer_loop_bounds_from_undefined (struct loop *loop) | |
2850 { | |
2851 unsigned i; | |
2852 basic_block *bbs; | |
2853 gimple_stmt_iterator bsi; | |
2854 basic_block bb; | |
2855 bool reliable; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2856 |
0 | 2857 bbs = get_loop_body (loop); |
2858 | |
2859 for (i = 0; i < loop->num_nodes; i++) | |
2860 { | |
2861 bb = bbs[i]; | |
2862 | |
2863 /* If BB is not executed in each iteration of the loop, we cannot | |
2864 use the operations in it to infer reliable upper bound on the | |
2865 # of iterations of the loop. However, we can use it as a guess. */ | |
2866 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); | |
2867 | |
2868 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
2869 { | |
2870 gimple stmt = gsi_stmt (bsi); | |
2871 | |
2872 infer_loop_bounds_from_array (loop, stmt, reliable); | |
2873 | |
2874 if (reliable) | |
2875 infer_loop_bounds_from_signedness (loop, stmt); | |
2876 } | |
2877 | |
2878 } | |
2879 | |
2880 free (bbs); | |
2881 } | |
2882 | |
2883 /* Converts VAL to double_int. */ | |
2884 | |
2885 static double_int | |
2886 gcov_type_to_double_int (gcov_type val) | |
2887 { | |
2888 double_int ret; | |
2889 | |
2890 ret.low = (unsigned HOST_WIDE_INT) val; | |
2891 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by | |
2892 the size of type. */ | |
2893 val >>= HOST_BITS_PER_WIDE_INT - 1; | |
2894 val >>= 1; | |
2895 ret.high = (unsigned HOST_WIDE_INT) val; | |
2896 | |
2897 return ret; | |
2898 } | |
2899 | |
2900 /* Records estimates on numbers of iterations of LOOP. */ | |
2901 | |
2902 void | |
2903 estimate_numbers_of_iterations_loop (struct loop *loop) | |
2904 { | |
2905 VEC (edge, heap) *exits; | |
2906 tree niter, type; | |
2907 unsigned i; | |
2908 struct tree_niter_desc niter_desc; | |
2909 edge ex; | |
2910 double_int bound; | |
2911 | |
2912 /* Give up if we already have tried to compute an estimation. */ | |
2913 if (loop->estimate_state != EST_NOT_COMPUTED) | |
2914 return; | |
2915 loop->estimate_state = EST_AVAILABLE; | |
2916 loop->any_upper_bound = false; | |
2917 loop->any_estimate = false; | |
2918 | |
2919 exits = get_loop_exit_edges (loop); | |
2920 for (i = 0; VEC_iterate (edge, exits, i, ex); i++) | |
2921 { | |
2922 if (!number_of_iterations_exit (loop, ex, &niter_desc, false)) | |
2923 continue; | |
2924 | |
2925 niter = niter_desc.niter; | |
2926 type = TREE_TYPE (niter); | |
2927 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST) | |
2928 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, | |
2929 build_int_cst (type, 0), | |
2930 niter); | |
2931 record_estimate (loop, niter, niter_desc.max, | |
2932 last_stmt (ex->src), | |
2933 true, true, true); | |
2934 } | |
2935 VEC_free (edge, heap, exits); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
2936 |
0 | 2937 infer_loop_bounds_from_undefined (loop); |
2938 | |
2939 /* If we have a measured profile, use it to estimate the number of | |
2940 iterations. */ | |
2941 if (loop->header->count != 0) | |
2942 { | |
2943 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1; | |
2944 bound = gcov_type_to_double_int (nit); | |
2945 record_niter_bound (loop, bound, true, false); | |
2946 } | |
2947 | |
2948 /* If an upper bound is smaller than the realistic estimate of the | |
2949 number of iterations, use the upper bound instead. */ | |
2950 if (loop->any_upper_bound | |
2951 && loop->any_estimate | |
2952 && double_int_ucmp (loop->nb_iterations_upper_bound, | |
2953 loop->nb_iterations_estimate) < 0) | |
2954 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; | |
2955 } | |
2956 | |
2957 /* Records estimates on numbers of iterations of loops. */ | |
2958 | |
2959 void | |
2960 estimate_numbers_of_iterations (void) | |
2961 { | |
2962 loop_iterator li; | |
2963 struct loop *loop; | |
2964 | |
2965 /* We don't want to issue signed overflow warnings while getting | |
2966 loop iteration estimates. */ | |
2967 fold_defer_overflow_warnings (); | |
2968 | |
2969 FOR_EACH_LOOP (li, loop, 0) | |
2970 { | |
2971 estimate_numbers_of_iterations_loop (loop); | |
2972 } | |
2973 | |
2974 fold_undefer_and_ignore_overflow_warnings (); | |
2975 } | |
2976 | |
2977 /* Returns true if statement S1 dominates statement S2. */ | |
2978 | |
2979 bool | |
2980 stmt_dominates_stmt_p (gimple s1, gimple s2) | |
2981 { | |
2982 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); | |
2983 | |
2984 if (!bb1 | |
2985 || s1 == s2) | |
2986 return true; | |
2987 | |
2988 if (bb1 == bb2) | |
2989 { | |
2990 gimple_stmt_iterator bsi; | |
2991 | |
2992 if (gimple_code (s2) == GIMPLE_PHI) | |
2993 return false; | |
2994 | |
2995 if (gimple_code (s1) == GIMPLE_PHI) | |
2996 return true; | |
2997 | |
2998 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi)) | |
2999 if (gsi_stmt (bsi) == s1) | |
3000 return true; | |
3001 | |
3002 return false; | |
3003 } | |
3004 | |
3005 return dominated_by_p (CDI_DOMINATORS, bb2, bb1); | |
3006 } | |
3007 | |
3008 /* Returns true when we can prove that the number of executions of | |
3009 STMT in the loop is at most NITER, according to the bound on | |
3010 the number of executions of the statement NITER_BOUND->stmt recorded in | |
3011 NITER_BOUND. If STMT is NULL, we must prove this bound for all | |
3012 statements in the loop. */ | |
3013 | |
3014 static bool | |
3015 n_of_executions_at_most (gimple stmt, | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
3016 struct nb_iter_bound *niter_bound, |
0 | 3017 tree niter) |
3018 { | |
3019 double_int bound = niter_bound->bound; | |
3020 tree nit_type = TREE_TYPE (niter), e; | |
3021 enum tree_code cmp; | |
3022 | |
3023 gcc_assert (TYPE_UNSIGNED (nit_type)); | |
3024 | |
3025 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that | |
3026 the number of iterations is small. */ | |
3027 if (!double_int_fits_to_tree_p (nit_type, bound)) | |
3028 return false; | |
3029 | |
3030 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 | |
3031 times. This means that: | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
3032 |
0 | 3033 -- if NITER_BOUND->is_exit is true, then everything before |
3034 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 | |
3035 times, and everything after it at most NITER_BOUND->bound times. | |
3036 | |
3037 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT | |
3038 is executed, then NITER_BOUND->stmt is executed as well in the same | |
3039 iteration (we conclude that if both statements belong to the same | |
3040 basic block, or if STMT is after NITER_BOUND->stmt), then STMT | |
3041 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is | |
3042 executed at most NITER_BOUND->bound + 2 times. */ | |
3043 | |
3044 if (niter_bound->is_exit) | |
3045 { | |
3046 if (stmt | |
3047 && stmt != niter_bound->stmt | |
3048 && stmt_dominates_stmt_p (niter_bound->stmt, stmt)) | |
3049 cmp = GE_EXPR; | |
3050 else | |
3051 cmp = GT_EXPR; | |
3052 } | |
3053 else | |
3054 { | |
3055 if (!stmt | |
3056 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) | |
3057 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt))) | |
3058 { | |
3059 bound = double_int_add (bound, double_int_one); | |
3060 if (double_int_zero_p (bound) | |
3061 || !double_int_fits_to_tree_p (nit_type, bound)) | |
3062 return false; | |
3063 } | |
3064 cmp = GT_EXPR; | |
3065 } | |
3066 | |
3067 e = fold_binary (cmp, boolean_type_node, | |
3068 niter, double_int_to_tree (nit_type, bound)); | |
3069 return e && integer_nonzerop (e); | |
3070 } | |
3071 | |
3072 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ | |
3073 | |
3074 bool | |
3075 nowrap_type_p (tree type) | |
3076 { | |
3077 if (INTEGRAL_TYPE_P (type) | |
3078 && TYPE_OVERFLOW_UNDEFINED (type)) | |
3079 return true; | |
3080 | |
3081 if (POINTER_TYPE_P (type)) | |
3082 return true; | |
3083 | |
3084 return false; | |
3085 } | |
3086 | |
3087 /* Return false only when the induction variable BASE + STEP * I is | |
3088 known to not overflow: i.e. when the number of iterations is small | |
3089 enough with respect to the step and initial condition in order to | |
3090 keep the evolution confined in TYPEs bounds. Return true when the | |
3091 iv is known to overflow or when the property is not computable. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
3092 |
0 | 3093 USE_OVERFLOW_SEMANTICS is true if this function should assume that |
3094 the rules for overflow of the given language apply (e.g., that signed | |
3095 arithmetics in C does not overflow). */ | |
3096 | |
3097 bool | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
3098 scev_probably_wraps_p (tree base, tree step, |
0 | 3099 gimple at_stmt, struct loop *loop, |
3100 bool use_overflow_semantics) | |
3101 { | |
3102 struct nb_iter_bound *bound; | |
3103 tree delta, step_abs; | |
3104 tree unsigned_type, valid_niter; | |
3105 tree type = TREE_TYPE (step); | |
3106 | |
3107 /* FIXME: We really need something like | |
3108 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. | |
3109 | |
3110 We used to test for the following situation that frequently appears | |
3111 during address arithmetics: | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
3112 |
0 | 3113 D.1621_13 = (long unsigned intD.4) D.1620_12; |
3114 D.1622_14 = D.1621_13 * 8; | |
3115 D.1623_15 = (doubleD.29 *) D.1622_14; | |
3116 | |
3117 And derived that the sequence corresponding to D_14 | |
3118 can be proved to not wrap because it is used for computing a | |
3119 memory access; however, this is not really the case -- for example, | |
3120 if D_12 = (unsigned char) [254,+,1], then D_14 has values | |
3121 2032, 2040, 0, 8, ..., but the code is still legal. */ | |
3122 | |
3123 if (chrec_contains_undetermined (base) | |
3124 || chrec_contains_undetermined (step)) | |
3125 return true; | |
3126 | |
3127 if (integer_zerop (step)) | |
3128 return false; | |
3129 | |
3130 /* If we can use the fact that signed and pointer arithmetics does not | |
3131 wrap, we are done. */ | |
3132 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base))) | |
3133 return false; | |
3134 | |
3135 /* To be able to use estimates on number of iterations of the loop, | |
3136 we must have an upper bound on the absolute value of the step. */ | |
3137 if (TREE_CODE (step) != INTEGER_CST) | |
3138 return true; | |
3139 | |
3140 /* Don't issue signed overflow warnings. */ | |
3141 fold_defer_overflow_warnings (); | |
3142 | |
3143 /* Otherwise, compute the number of iterations before we reach the | |
3144 bound of the type, and verify that the loop is exited before this | |
3145 occurs. */ | |
3146 unsigned_type = unsigned_type_for (type); | |
3147 base = fold_convert (unsigned_type, base); | |
3148 | |
3149 if (tree_int_cst_sign_bit (step)) | |
3150 { | |
3151 tree extreme = fold_convert (unsigned_type, | |
3152 lower_bound_in_type (type, type)); | |
3153 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); | |
3154 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, | |
3155 fold_convert (unsigned_type, step)); | |
3156 } | |
3157 else | |
3158 { | |
3159 tree extreme = fold_convert (unsigned_type, | |
3160 upper_bound_in_type (type, type)); | |
3161 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); | |
3162 step_abs = fold_convert (unsigned_type, step); | |
3163 } | |
3164 | |
3165 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); | |
3166 | |
3167 estimate_numbers_of_iterations_loop (loop); | |
3168 for (bound = loop->bounds; bound; bound = bound->next) | |
3169 { | |
3170 if (n_of_executions_at_most (at_stmt, bound, valid_niter)) | |
3171 { | |
3172 fold_undefer_and_ignore_overflow_warnings (); | |
3173 return false; | |
3174 } | |
3175 } | |
3176 | |
3177 fold_undefer_and_ignore_overflow_warnings (); | |
3178 | |
3179 /* At this point we still don't have a proof that the iv does not | |
3180 overflow: give up. */ | |
3181 return true; | |
3182 } | |
3183 | |
3184 /* Frees the information on upper bounds on numbers of iterations of LOOP. */ | |
3185 | |
3186 void | |
3187 free_numbers_of_iterations_estimates_loop (struct loop *loop) | |
3188 { | |
3189 struct nb_iter_bound *bound, *next; | |
3190 | |
3191 loop->nb_iterations = NULL; | |
3192 loop->estimate_state = EST_NOT_COMPUTED; | |
3193 for (bound = loop->bounds; bound; bound = next) | |
3194 { | |
3195 next = bound->next; | |
3196 ggc_free (bound); | |
3197 } | |
3198 | |
3199 loop->bounds = NULL; | |
3200 } | |
3201 | |
3202 /* Frees the information on upper bounds on numbers of iterations of loops. */ | |
3203 | |
3204 void | |
3205 free_numbers_of_iterations_estimates (void) | |
3206 { | |
3207 loop_iterator li; | |
3208 struct loop *loop; | |
3209 | |
3210 FOR_EACH_LOOP (li, loop, 0) | |
3211 { | |
3212 free_numbers_of_iterations_estimates_loop (loop); | |
3213 } | |
3214 } | |
3215 | |
3216 /* Substitute value VAL for ssa name NAME inside expressions held | |
3217 at LOOP. */ | |
3218 | |
3219 void | |
3220 substitute_in_loop_info (struct loop *loop, tree name, tree val) | |
3221 { | |
3222 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); | |
3223 } |