Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-loop-niter.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | 58ad6c70ea60 |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Functions to determine/estimate number of iterations of a loop. |
| 2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, | |
| 3 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 "rtl.h" | |
| 27 #include "tm_p.h" | |
| 28 #include "hard-reg-set.h" | |
| 29 #include "basic-block.h" | |
| 30 #include "output.h" | |
| 31 #include "diagnostic.h" | |
| 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 } |