1169689Skan/* Functions to determine/estimate number of iterations of a loop. 2169689Skan Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "rtl.h" 27169689Skan#include "tm_p.h" 28169689Skan#include "hard-reg-set.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "output.h" 31169689Skan#include "diagnostic.h" 32169689Skan#include "intl.h" 33169689Skan#include "tree-flow.h" 34169689Skan#include "tree-dump.h" 35169689Skan#include "cfgloop.h" 36169689Skan#include "tree-pass.h" 37169689Skan#include "ggc.h" 38169689Skan#include "tree-chrec.h" 39169689Skan#include "tree-scalar-evolution.h" 40169689Skan#include "tree-data-ref.h" 41169689Skan#include "params.h" 42169689Skan#include "flags.h" 43169689Skan#include "toplev.h" 44169689Skan#include "tree-inline.h" 45169689Skan 46169689Skan#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) 47169689Skan 48169689Skan 49169689Skan/* 50169689Skan 51169689Skan Analysis of number of iterations of an affine exit test. 52169689Skan 53169689Skan*/ 54169689Skan 55169689Skan/* Returns true if ARG is either NULL_TREE or constant zero. Unlike 56169689Skan integer_zerop, it does not care about overflow flags. */ 57169689Skan 58169689Skanbool 59169689Skanzero_p (tree arg) 60169689Skan{ 61169689Skan if (!arg) 62169689Skan return true; 63169689Skan 64169689Skan if (TREE_CODE (arg) != INTEGER_CST) 65169689Skan return false; 66169689Skan 67169689Skan return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0); 68169689Skan} 69169689Skan 70169689Skan/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does 71169689Skan not care about overflow flags. */ 72169689Skan 73169689Skanstatic bool 74169689Skannonzero_p (tree arg) 75169689Skan{ 76169689Skan if (!arg) 77169689Skan return false; 78169689Skan 79169689Skan if (TREE_CODE (arg) != INTEGER_CST) 80169689Skan return false; 81169689Skan 82169689Skan return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0); 83169689Skan} 84169689Skan 85169689Skan/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ 86169689Skan 87169689Skanstatic tree 88169689Skaninverse (tree x, tree mask) 89169689Skan{ 90169689Skan tree type = TREE_TYPE (x); 91169689Skan tree rslt; 92169689Skan unsigned ctr = tree_floor_log2 (mask); 93169689Skan 94169689Skan if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) 95169689Skan { 96169689Skan unsigned HOST_WIDE_INT ix; 97169689Skan unsigned HOST_WIDE_INT imask; 98169689Skan unsigned HOST_WIDE_INT irslt = 1; 99169689Skan 100169689Skan gcc_assert (cst_and_fits_in_hwi (x)); 101169689Skan gcc_assert (cst_and_fits_in_hwi (mask)); 102169689Skan 103169689Skan ix = int_cst_value (x); 104169689Skan imask = int_cst_value (mask); 105169689Skan 106169689Skan for (; ctr; ctr--) 107169689Skan { 108169689Skan irslt *= ix; 109169689Skan ix *= ix; 110169689Skan } 111169689Skan irslt &= imask; 112169689Skan 113169689Skan rslt = build_int_cst_type (type, irslt); 114169689Skan } 115169689Skan else 116169689Skan { 117169689Skan rslt = build_int_cst (type, 1); 118169689Skan for (; ctr; ctr--) 119169689Skan { 120169689Skan rslt = int_const_binop (MULT_EXPR, rslt, x, 0); 121169689Skan x = int_const_binop (MULT_EXPR, x, x, 0); 122169689Skan } 123169689Skan rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0); 124169689Skan } 125169689Skan 126169689Skan return rslt; 127169689Skan} 128169689Skan 129169689Skan/* Determines number of iterations of loop whose ending condition 130169689Skan is IV <> FINAL. TYPE is the type of the iv. The number of 131169689Skan iterations is stored to NITER. NEVER_INFINITE is true if 132169689Skan we know that the exit must be taken eventually, i.e., that the IV 133169689Skan ever reaches the value FINAL (we derived this earlier, and possibly set 134169689Skan NITER->assumptions to make sure this is the case). */ 135169689Skan 136169689Skanstatic bool 137169689Skannumber_of_iterations_ne (tree type, affine_iv *iv, tree final, 138169689Skan struct tree_niter_desc *niter, bool never_infinite) 139169689Skan{ 140169689Skan tree niter_type = unsigned_type_for (type); 141169689Skan tree s, c, d, bits, assumption, tmp, bound; 142169689Skan 143169689Skan niter->control = *iv; 144169689Skan niter->bound = final; 145169689Skan niter->cmp = NE_EXPR; 146169689Skan 147169689Skan /* Rearrange the terms so that we get inequality s * i <> c, with s 148169689Skan positive. Also cast everything to the unsigned type. */ 149169689Skan if (tree_int_cst_sign_bit (iv->step)) 150169689Skan { 151169689Skan s = fold_convert (niter_type, 152169689Skan fold_build1 (NEGATE_EXPR, type, iv->step)); 153169689Skan c = fold_build2 (MINUS_EXPR, niter_type, 154169689Skan fold_convert (niter_type, iv->base), 155169689Skan fold_convert (niter_type, final)); 156169689Skan } 157169689Skan else 158169689Skan { 159169689Skan s = fold_convert (niter_type, iv->step); 160169689Skan c = fold_build2 (MINUS_EXPR, niter_type, 161169689Skan fold_convert (niter_type, final), 162169689Skan fold_convert (niter_type, iv->base)); 163169689Skan } 164169689Skan 165169689Skan /* First the trivial cases -- when the step is 1. */ 166169689Skan if (integer_onep (s)) 167169689Skan { 168169689Skan niter->niter = c; 169169689Skan return true; 170169689Skan } 171169689Skan 172169689Skan /* Let nsd (step, size of mode) = d. If d does not divide c, the loop 173169689Skan is infinite. Otherwise, the number of iterations is 174169689Skan (inverse(s/d) * (c/d)) mod (size of mode/d). */ 175169689Skan bits = num_ending_zeros (s); 176169689Skan bound = build_low_bits_mask (niter_type, 177169689Skan (TYPE_PRECISION (niter_type) 178169689Skan - tree_low_cst (bits, 1))); 179169689Skan 180169689Skan d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, 181169689Skan build_int_cst (niter_type, 1), bits); 182169689Skan s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); 183169689Skan 184169689Skan if (!never_infinite) 185169689Skan { 186169689Skan /* If we cannot assume that the loop is not infinite, record the 187169689Skan assumptions for divisibility of c. */ 188169689Skan assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d); 189169689Skan assumption = fold_build2 (EQ_EXPR, boolean_type_node, 190169689Skan assumption, build_int_cst (niter_type, 0)); 191169689Skan if (!nonzero_p (assumption)) 192169689Skan niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 193169689Skan niter->assumptions, assumption); 194169689Skan } 195169689Skan 196169689Skan c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); 197169689Skan tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); 198169689Skan niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); 199169689Skan return true; 200169689Skan} 201169689Skan 202169689Skan/* Checks whether we can determine the final value of the control variable 203169689Skan of the loop with ending condition IV0 < IV1 (computed in TYPE). 204169689Skan DELTA is the difference IV1->base - IV0->base, STEP is the absolute value 205169689Skan of the step. The assumptions necessary to ensure that the computation 206169689Skan of the final value does not overflow are recorded in NITER. If we 207169689Skan find the final value, we adjust DELTA and return TRUE. Otherwise 208169689Skan we return false. */ 209169689Skan 210169689Skanstatic bool 211169689Skannumber_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, 212169689Skan struct tree_niter_desc *niter, 213169689Skan tree *delta, tree step) 214169689Skan{ 215169689Skan tree niter_type = TREE_TYPE (step); 216169689Skan tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); 217169689Skan tree tmod; 218169689Skan tree assumption = boolean_true_node, bound, noloop; 219169689Skan 220169689Skan if (TREE_CODE (mod) != INTEGER_CST) 221169689Skan return false; 222169689Skan if (nonzero_p (mod)) 223169689Skan mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); 224169689Skan tmod = fold_convert (type, mod); 225169689Skan 226169689Skan if (nonzero_p (iv0->step)) 227169689Skan { 228169689Skan /* The final value of the iv is iv1->base + MOD, assuming that this 229169689Skan computation does not overflow, and that 230169689Skan iv0->base <= iv1->base + MOD. */ 231169689Skan if (!iv1->no_overflow && !zero_p (mod)) 232169689Skan { 233169689Skan bound = fold_build2 (MINUS_EXPR, type, 234169689Skan TYPE_MAX_VALUE (type), tmod); 235169689Skan assumption = fold_build2 (LE_EXPR, boolean_type_node, 236169689Skan iv1->base, bound); 237169689Skan if (zero_p (assumption)) 238169689Skan return false; 239169689Skan } 240169689Skan noloop = fold_build2 (GT_EXPR, boolean_type_node, 241169689Skan iv0->base, 242169689Skan fold_build2 (PLUS_EXPR, type, 243169689Skan iv1->base, tmod)); 244169689Skan } 245169689Skan else 246169689Skan { 247169689Skan /* The final value of the iv is iv0->base - MOD, assuming that this 248169689Skan computation does not overflow, and that 249169689Skan iv0->base - MOD <= iv1->base. */ 250169689Skan if (!iv0->no_overflow && !zero_p (mod)) 251169689Skan { 252169689Skan bound = fold_build2 (PLUS_EXPR, type, 253169689Skan TYPE_MIN_VALUE (type), tmod); 254169689Skan assumption = fold_build2 (GE_EXPR, boolean_type_node, 255169689Skan iv0->base, bound); 256169689Skan if (zero_p (assumption)) 257169689Skan return false; 258169689Skan } 259169689Skan noloop = fold_build2 (GT_EXPR, boolean_type_node, 260169689Skan fold_build2 (MINUS_EXPR, type, 261169689Skan iv0->base, tmod), 262169689Skan iv1->base); 263169689Skan } 264169689Skan 265169689Skan if (!nonzero_p (assumption)) 266169689Skan niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 267169689Skan niter->assumptions, 268169689Skan assumption); 269169689Skan if (!zero_p (noloop)) 270169689Skan niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 271169689Skan niter->may_be_zero, 272169689Skan noloop); 273169689Skan *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); 274169689Skan return true; 275169689Skan} 276169689Skan 277169689Skan/* Add assertions to NITER that ensure that the control variable of the loop 278169689Skan with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 279169689Skan are TYPE. Returns false if we can prove that there is an overflow, true 280169689Skan otherwise. STEP is the absolute value of the step. */ 281169689Skan 282169689Skanstatic bool 283169689Skanassert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, 284169689Skan struct tree_niter_desc *niter, tree step) 285169689Skan{ 286169689Skan tree bound, d, assumption, diff; 287169689Skan tree niter_type = TREE_TYPE (step); 288169689Skan 289169689Skan if (nonzero_p (iv0->step)) 290169689Skan { 291169689Skan /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ 292169689Skan if (iv0->no_overflow) 293169689Skan return true; 294169689Skan 295169689Skan /* If iv0->base is a constant, we can determine the last value before 296169689Skan overflow precisely; otherwise we conservatively assume 297169689Skan MAX - STEP + 1. */ 298169689Skan 299169689Skan if (TREE_CODE (iv0->base) == INTEGER_CST) 300169689Skan { 301169689Skan d = fold_build2 (MINUS_EXPR, niter_type, 302169689Skan fold_convert (niter_type, TYPE_MAX_VALUE (type)), 303169689Skan fold_convert (niter_type, iv0->base)); 304169689Skan diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 305169689Skan } 306169689Skan else 307169689Skan diff = fold_build2 (MINUS_EXPR, niter_type, step, 308169689Skan build_int_cst (niter_type, 1)); 309169689Skan bound = fold_build2 (MINUS_EXPR, type, 310169689Skan TYPE_MAX_VALUE (type), fold_convert (type, diff)); 311169689Skan assumption = fold_build2 (LE_EXPR, boolean_type_node, 312169689Skan iv1->base, bound); 313169689Skan } 314169689Skan else 315169689Skan { 316169689Skan /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ 317169689Skan if (iv1->no_overflow) 318169689Skan return true; 319169689Skan 320169689Skan if (TREE_CODE (iv1->base) == INTEGER_CST) 321169689Skan { 322169689Skan d = fold_build2 (MINUS_EXPR, niter_type, 323169689Skan fold_convert (niter_type, iv1->base), 324169689Skan fold_convert (niter_type, TYPE_MIN_VALUE (type))); 325169689Skan diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); 326169689Skan } 327169689Skan else 328169689Skan diff = fold_build2 (MINUS_EXPR, niter_type, step, 329169689Skan build_int_cst (niter_type, 1)); 330169689Skan bound = fold_build2 (PLUS_EXPR, type, 331169689Skan TYPE_MIN_VALUE (type), fold_convert (type, diff)); 332169689Skan assumption = fold_build2 (GE_EXPR, boolean_type_node, 333169689Skan iv0->base, bound); 334169689Skan } 335169689Skan 336169689Skan if (zero_p (assumption)) 337169689Skan return false; 338169689Skan if (!nonzero_p (assumption)) 339169689Skan niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 340169689Skan niter->assumptions, assumption); 341169689Skan 342169689Skan iv0->no_overflow = true; 343169689Skan iv1->no_overflow = true; 344169689Skan return true; 345169689Skan} 346169689Skan 347169689Skan/* Add an assumption to NITER that a loop whose ending condition 348169689Skan is IV0 < IV1 rolls. TYPE is the type of the control iv. */ 349169689Skan 350169689Skanstatic void 351169689Skanassert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, 352169689Skan struct tree_niter_desc *niter) 353169689Skan{ 354169689Skan tree assumption = boolean_true_node, bound, diff; 355169689Skan tree mbz, mbzl, mbzr; 356169689Skan 357169689Skan if (nonzero_p (iv0->step)) 358169689Skan { 359169689Skan diff = fold_build2 (MINUS_EXPR, type, 360169689Skan iv0->step, build_int_cst (type, 1)); 361169689Skan 362169689Skan /* We need to know that iv0->base >= MIN + iv0->step - 1. Since 363169689Skan 0 address never belongs to any object, we can assume this for 364169689Skan pointers. */ 365169689Skan if (!POINTER_TYPE_P (type)) 366169689Skan { 367169689Skan bound = fold_build2 (PLUS_EXPR, type, 368169689Skan TYPE_MIN_VALUE (type), diff); 369169689Skan assumption = fold_build2 (GE_EXPR, boolean_type_node, 370169689Skan iv0->base, bound); 371169689Skan } 372169689Skan 373169689Skan /* And then we can compute iv0->base - diff, and compare it with 374169689Skan iv1->base. */ 375169689Skan mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff); 376169689Skan mbzr = iv1->base; 377169689Skan } 378169689Skan else 379169689Skan { 380169689Skan diff = fold_build2 (PLUS_EXPR, type, 381169689Skan iv1->step, build_int_cst (type, 1)); 382169689Skan 383169689Skan if (!POINTER_TYPE_P (type)) 384169689Skan { 385169689Skan bound = fold_build2 (PLUS_EXPR, type, 386169689Skan TYPE_MAX_VALUE (type), diff); 387169689Skan assumption = fold_build2 (LE_EXPR, boolean_type_node, 388169689Skan iv1->base, bound); 389169689Skan } 390169689Skan 391169689Skan mbzl = iv0->base; 392169689Skan mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff); 393169689Skan } 394169689Skan 395169689Skan mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); 396169689Skan 397169689Skan if (!nonzero_p (assumption)) 398169689Skan niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 399169689Skan niter->assumptions, assumption); 400169689Skan if (!zero_p (mbz)) 401169689Skan niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 402169689Skan niter->may_be_zero, mbz); 403169689Skan} 404169689Skan 405169689Skan/* Determines number of iterations of loop whose ending condition 406169689Skan is IV0 < IV1. TYPE is the type of the iv. The number of 407169689Skan iterations is stored to NITER. */ 408169689Skan 409169689Skanstatic bool 410169689Skannumber_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, 411169689Skan struct tree_niter_desc *niter, 412169689Skan bool never_infinite ATTRIBUTE_UNUSED) 413169689Skan{ 414169689Skan tree niter_type = unsigned_type_for (type); 415169689Skan tree delta, step, s; 416169689Skan 417169689Skan if (nonzero_p (iv0->step)) 418169689Skan { 419169689Skan niter->control = *iv0; 420169689Skan niter->cmp = LT_EXPR; 421169689Skan niter->bound = iv1->base; 422169689Skan } 423169689Skan else 424169689Skan { 425169689Skan niter->control = *iv1; 426169689Skan niter->cmp = GT_EXPR; 427169689Skan niter->bound = iv0->base; 428169689Skan } 429169689Skan 430169689Skan delta = fold_build2 (MINUS_EXPR, niter_type, 431169689Skan fold_convert (niter_type, iv1->base), 432169689Skan fold_convert (niter_type, iv0->base)); 433169689Skan 434169689Skan /* First handle the special case that the step is +-1. */ 435169689Skan if ((iv0->step && integer_onep (iv0->step) 436169689Skan && zero_p (iv1->step)) 437169689Skan || (iv1->step && integer_all_onesp (iv1->step) 438169689Skan && zero_p (iv0->step))) 439169689Skan { 440169689Skan /* for (i = iv0->base; i < iv1->base; i++) 441169689Skan 442169689Skan or 443169689Skan 444169689Skan for (i = iv1->base; i > iv0->base; i--). 445169689Skan 446169689Skan In both cases # of iterations is iv1->base - iv0->base, assuming that 447169689Skan iv1->base >= iv0->base. */ 448169689Skan niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, 449169689Skan iv1->base, iv0->base); 450169689Skan niter->niter = delta; 451169689Skan return true; 452169689Skan } 453169689Skan 454169689Skan if (nonzero_p (iv0->step)) 455169689Skan step = fold_convert (niter_type, iv0->step); 456169689Skan else 457169689Skan step = fold_convert (niter_type, 458169689Skan fold_build1 (NEGATE_EXPR, type, iv1->step)); 459169689Skan 460169689Skan /* If we can determine the final value of the control iv exactly, we can 461169689Skan transform the condition to != comparison. In particular, this will be 462169689Skan the case if DELTA is constant. */ 463169689Skan if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step)) 464169689Skan { 465169689Skan affine_iv zps; 466169689Skan 467169689Skan zps.base = build_int_cst (niter_type, 0); 468169689Skan zps.step = step; 469169689Skan /* number_of_iterations_lt_to_ne will add assumptions that ensure that 470169689Skan zps does not overflow. */ 471169689Skan zps.no_overflow = true; 472169689Skan 473169689Skan return number_of_iterations_ne (type, &zps, delta, niter, true); 474169689Skan } 475169689Skan 476169689Skan /* Make sure that the control iv does not overflow. */ 477169689Skan if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) 478169689Skan return false; 479169689Skan 480169689Skan /* We determine the number of iterations as (delta + step - 1) / step. For 481169689Skan this to work, we must know that iv1->base >= iv0->base - step + 1, 482169689Skan otherwise the loop does not roll. */ 483169689Skan assert_loop_rolls_lt (type, iv0, iv1, niter); 484169689Skan 485169689Skan s = fold_build2 (MINUS_EXPR, niter_type, 486169689Skan step, build_int_cst (niter_type, 1)); 487169689Skan delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); 488169689Skan niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); 489169689Skan return true; 490169689Skan} 491169689Skan 492169689Skan/* Determines number of iterations of loop whose ending condition 493169689Skan is IV0 <= IV1. TYPE is the type of the iv. The number of 494169689Skan iterations is stored to NITER. NEVER_INFINITE is true if 495169689Skan we know that this condition must eventually become false (we derived this 496169689Skan earlier, and possibly set NITER->assumptions to make sure this 497169689Skan is the case). */ 498169689Skan 499169689Skanstatic bool 500169689Skannumber_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, 501169689Skan struct tree_niter_desc *niter, bool never_infinite) 502169689Skan{ 503169689Skan tree assumption; 504169689Skan 505169689Skan /* Say that IV0 is the control variable. Then IV0 <= IV1 iff 506169689Skan IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest 507169689Skan value of the type. This we must know anyway, since if it is 508169689Skan equal to this value, the loop rolls forever. */ 509169689Skan 510169689Skan if (!never_infinite) 511169689Skan { 512169689Skan if (nonzero_p (iv0->step)) 513169689Skan assumption = fold_build2 (NE_EXPR, boolean_type_node, 514169689Skan iv1->base, TYPE_MAX_VALUE (type)); 515169689Skan else 516169689Skan assumption = fold_build2 (NE_EXPR, boolean_type_node, 517169689Skan iv0->base, TYPE_MIN_VALUE (type)); 518169689Skan 519169689Skan if (zero_p (assumption)) 520169689Skan return false; 521169689Skan if (!nonzero_p (assumption)) 522169689Skan niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 523169689Skan niter->assumptions, assumption); 524169689Skan } 525169689Skan 526169689Skan if (nonzero_p (iv0->step)) 527169689Skan iv1->base = fold_build2 (PLUS_EXPR, type, 528169689Skan iv1->base, build_int_cst (type, 1)); 529169689Skan else 530169689Skan iv0->base = fold_build2 (MINUS_EXPR, type, 531169689Skan iv0->base, build_int_cst (type, 1)); 532169689Skan return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); 533169689Skan} 534169689Skan 535169689Skan/* Determine the number of iterations according to condition (for staying 536169689Skan inside loop) which compares two induction variables using comparison 537169689Skan operator CODE. The induction variable on left side of the comparison 538169689Skan is IV0, the right-hand side is IV1. Both induction variables must have 539169689Skan type TYPE, which must be an integer or pointer type. The steps of the 540169689Skan ivs must be constants (or NULL_TREE, which is interpreted as constant zero). 541169689Skan 542169689Skan ONLY_EXIT is true if we are sure this is the only way the loop could be 543169689Skan exited (including possibly non-returning function calls, exceptions, etc.) 544169689Skan -- in this case we can use the information whether the control induction 545169689Skan variables can overflow or not in a more efficient way. 546169689Skan 547169689Skan The results (number of iterations and assumptions as described in 548169689Skan comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. 549169689Skan Returns false if it fails to determine number of iterations, true if it 550169689Skan was determined (possibly with some assumptions). */ 551169689Skan 552169689Skanstatic bool 553169689Skannumber_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, 554169689Skan affine_iv *iv1, struct tree_niter_desc *niter, 555169689Skan bool only_exit) 556169689Skan{ 557169689Skan bool never_infinite; 558169689Skan 559169689Skan /* The meaning of these assumptions is this: 560169689Skan if !assumptions 561169689Skan then the rest of information does not have to be valid 562169689Skan if may_be_zero then the loop does not roll, even if 563169689Skan niter != 0. */ 564169689Skan niter->assumptions = boolean_true_node; 565169689Skan niter->may_be_zero = boolean_false_node; 566169689Skan niter->niter = NULL_TREE; 567169689Skan niter->additional_info = boolean_true_node; 568169689Skan 569169689Skan niter->bound = NULL_TREE; 570169689Skan niter->cmp = ERROR_MARK; 571169689Skan 572169689Skan /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that 573169689Skan the control variable is on lhs. */ 574169689Skan if (code == GE_EXPR || code == GT_EXPR 575169689Skan || (code == NE_EXPR && zero_p (iv0->step))) 576169689Skan { 577169689Skan SWAP (iv0, iv1); 578169689Skan code = swap_tree_comparison (code); 579169689Skan } 580169689Skan 581169689Skan if (!only_exit) 582169689Skan { 583169689Skan /* If this is not the only possible exit from the loop, the information 584169689Skan that the induction variables cannot overflow as derived from 585169689Skan signedness analysis cannot be relied upon. We use them e.g. in the 586169689Skan following way: given loop for (i = 0; i <= n; i++), if i is 587169689Skan signed, it cannot overflow, thus this loop is equivalent to 588169689Skan for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop 589169689Skan is exited in some other way before i overflows, this transformation 590169689Skan is incorrect (the new loop exits immediately). */ 591169689Skan iv0->no_overflow = false; 592169689Skan iv1->no_overflow = false; 593169689Skan } 594169689Skan 595169689Skan if (POINTER_TYPE_P (type)) 596169689Skan { 597169689Skan /* Comparison of pointers is undefined unless both iv0 and iv1 point 598169689Skan to the same object. If they do, the control variable cannot wrap 599169689Skan (as wrap around the bounds of memory will never return a pointer 600169689Skan that would be guaranteed to point to the same object, even if we 601169689Skan avoid undefined behavior by casting to size_t and back). The 602169689Skan restrictions on pointer arithmetics and comparisons of pointers 603169689Skan ensure that using the no-overflow assumptions is correct in this 604169689Skan case even if ONLY_EXIT is false. */ 605169689Skan iv0->no_overflow = true; 606169689Skan iv1->no_overflow = true; 607169689Skan } 608169689Skan 609169689Skan /* If the control induction variable does not overflow, the loop obviously 610169689Skan cannot be infinite. */ 611169689Skan if (!zero_p (iv0->step) && iv0->no_overflow) 612169689Skan never_infinite = true; 613169689Skan else if (!zero_p (iv1->step) && iv1->no_overflow) 614169689Skan never_infinite = true; 615169689Skan else 616169689Skan never_infinite = false; 617169689Skan 618169689Skan /* We can handle the case when neither of the sides of the comparison is 619169689Skan invariant, provided that the test is NE_EXPR. This rarely occurs in 620169689Skan practice, but it is simple enough to manage. */ 621169689Skan if (!zero_p (iv0->step) && !zero_p (iv1->step)) 622169689Skan { 623169689Skan if (code != NE_EXPR) 624169689Skan return false; 625169689Skan 626169689Skan iv0->step = fold_binary_to_constant (MINUS_EXPR, type, 627169689Skan iv0->step, iv1->step); 628169689Skan iv0->no_overflow = false; 629169689Skan iv1->step = NULL_TREE; 630169689Skan iv1->no_overflow = true; 631169689Skan } 632169689Skan 633169689Skan /* If the result of the comparison is a constant, the loop is weird. More 634169689Skan precise handling would be possible, but the situation is not common enough 635169689Skan to waste time on it. */ 636169689Skan if (zero_p (iv0->step) && zero_p (iv1->step)) 637169689Skan return false; 638169689Skan 639169689Skan /* Ignore loops of while (i-- < 10) type. */ 640169689Skan if (code != NE_EXPR) 641169689Skan { 642169689Skan if (iv0->step && tree_int_cst_sign_bit (iv0->step)) 643169689Skan return false; 644169689Skan 645169689Skan if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) 646169689Skan return false; 647169689Skan } 648169689Skan 649169689Skan /* If the loop exits immediately, there is nothing to do. */ 650169689Skan if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) 651169689Skan { 652169689Skan niter->niter = build_int_cst (unsigned_type_for (type), 0); 653169689Skan return true; 654169689Skan } 655169689Skan 656169689Skan /* OK, now we know we have a senseful loop. Handle several cases, depending 657169689Skan on what comparison operator is used. */ 658169689Skan switch (code) 659169689Skan { 660169689Skan case NE_EXPR: 661169689Skan gcc_assert (zero_p (iv1->step)); 662169689Skan return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite); 663169689Skan case LT_EXPR: 664169689Skan return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); 665169689Skan case LE_EXPR: 666169689Skan return number_of_iterations_le (type, iv0, iv1, niter, never_infinite); 667169689Skan default: 668169689Skan gcc_unreachable (); 669169689Skan } 670169689Skan} 671169689Skan 672169689Skan/* Substitute NEW for OLD in EXPR and fold the result. */ 673169689Skan 674169689Skanstatic tree 675169689Skansimplify_replace_tree (tree expr, tree old, tree new) 676169689Skan{ 677169689Skan unsigned i, n; 678169689Skan tree ret = NULL_TREE, e, se; 679169689Skan 680169689Skan if (!expr) 681169689Skan return NULL_TREE; 682169689Skan 683169689Skan if (expr == old 684169689Skan || operand_equal_p (expr, old, 0)) 685169689Skan return unshare_expr (new); 686169689Skan 687169689Skan if (!EXPR_P (expr)) 688169689Skan return expr; 689169689Skan 690169689Skan n = TREE_CODE_LENGTH (TREE_CODE (expr)); 691169689Skan for (i = 0; i < n; i++) 692169689Skan { 693169689Skan e = TREE_OPERAND (expr, i); 694169689Skan se = simplify_replace_tree (e, old, new); 695169689Skan if (e == se) 696169689Skan continue; 697169689Skan 698169689Skan if (!ret) 699169689Skan ret = copy_node (expr); 700169689Skan 701169689Skan TREE_OPERAND (ret, i) = se; 702169689Skan } 703169689Skan 704169689Skan return (ret ? fold (ret) : expr); 705169689Skan} 706169689Skan 707169689Skan/* Expand definitions of ssa names in EXPR as long as they are simple 708169689Skan enough, and return the new expression. */ 709169689Skan 710169689Skantree 711169689Skanexpand_simple_operations (tree expr) 712169689Skan{ 713169689Skan unsigned i, n; 714169689Skan tree ret = NULL_TREE, e, ee, stmt; 715169689Skan enum tree_code code; 716169689Skan 717169689Skan if (expr == NULL_TREE) 718169689Skan return expr; 719169689Skan 720169689Skan if (is_gimple_min_invariant (expr)) 721169689Skan return expr; 722169689Skan 723169689Skan code = TREE_CODE (expr); 724169689Skan if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) 725169689Skan { 726169689Skan n = TREE_CODE_LENGTH (code); 727169689Skan for (i = 0; i < n; i++) 728169689Skan { 729169689Skan e = TREE_OPERAND (expr, i); 730169689Skan ee = expand_simple_operations (e); 731169689Skan if (e == ee) 732169689Skan continue; 733169689Skan 734169689Skan if (!ret) 735169689Skan ret = copy_node (expr); 736169689Skan 737169689Skan TREE_OPERAND (ret, i) = ee; 738169689Skan } 739169689Skan 740169689Skan if (!ret) 741169689Skan return expr; 742169689Skan 743169689Skan fold_defer_overflow_warnings (); 744169689Skan ret = fold (ret); 745169689Skan fold_undefer_and_ignore_overflow_warnings (); 746169689Skan return ret; 747169689Skan } 748169689Skan 749169689Skan if (TREE_CODE (expr) != SSA_NAME) 750169689Skan return expr; 751169689Skan 752169689Skan stmt = SSA_NAME_DEF_STMT (expr); 753169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 754169689Skan return expr; 755169689Skan 756169689Skan e = TREE_OPERAND (stmt, 1); 757169689Skan if (/* Casts are simple. */ 758169689Skan TREE_CODE (e) != NOP_EXPR 759169689Skan && TREE_CODE (e) != CONVERT_EXPR 760169689Skan /* Copies are simple. */ 761169689Skan && TREE_CODE (e) != SSA_NAME 762169689Skan /* Assignments of invariants are simple. */ 763169689Skan && !is_gimple_min_invariant (e) 764169689Skan /* And increments and decrements by a constant are simple. */ 765169689Skan && !((TREE_CODE (e) == PLUS_EXPR 766169689Skan || TREE_CODE (e) == MINUS_EXPR) 767169689Skan && is_gimple_min_invariant (TREE_OPERAND (e, 1)))) 768169689Skan return expr; 769169689Skan 770169689Skan return expand_simple_operations (e); 771169689Skan} 772169689Skan 773169689Skan/* Tries to simplify EXPR using the condition COND. Returns the simplified 774169689Skan expression (or EXPR unchanged, if no simplification was possible). */ 775169689Skan 776169689Skanstatic tree 777169689Skantree_simplify_using_condition_1 (tree cond, tree expr) 778169689Skan{ 779169689Skan bool changed; 780169689Skan tree e, te, e0, e1, e2, notcond; 781169689Skan enum tree_code code = TREE_CODE (expr); 782169689Skan 783169689Skan if (code == INTEGER_CST) 784169689Skan return expr; 785169689Skan 786169689Skan if (code == TRUTH_OR_EXPR 787169689Skan || code == TRUTH_AND_EXPR 788169689Skan || code == COND_EXPR) 789169689Skan { 790169689Skan changed = false; 791169689Skan 792169689Skan e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); 793169689Skan if (TREE_OPERAND (expr, 0) != e0) 794169689Skan changed = true; 795169689Skan 796169689Skan e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); 797169689Skan if (TREE_OPERAND (expr, 1) != e1) 798169689Skan changed = true; 799169689Skan 800169689Skan if (code == COND_EXPR) 801169689Skan { 802169689Skan e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); 803169689Skan if (TREE_OPERAND (expr, 2) != e2) 804169689Skan changed = true; 805169689Skan } 806169689Skan else 807169689Skan e2 = NULL_TREE; 808169689Skan 809169689Skan if (changed) 810169689Skan { 811169689Skan if (code == COND_EXPR) 812169689Skan expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 813169689Skan else 814169689Skan expr = fold_build2 (code, boolean_type_node, e0, e1); 815169689Skan } 816169689Skan 817169689Skan return expr; 818169689Skan } 819169689Skan 820169689Skan /* In case COND is equality, we may be able to simplify EXPR by copy/constant 821169689Skan propagation, and vice versa. Fold does not handle this, since it is 822169689Skan considered too expensive. */ 823169689Skan if (TREE_CODE (cond) == EQ_EXPR) 824169689Skan { 825169689Skan e0 = TREE_OPERAND (cond, 0); 826169689Skan e1 = TREE_OPERAND (cond, 1); 827169689Skan 828169689Skan /* We know that e0 == e1. Check whether we cannot simplify expr 829169689Skan using this fact. */ 830169689Skan e = simplify_replace_tree (expr, e0, e1); 831169689Skan if (zero_p (e) || nonzero_p (e)) 832169689Skan return e; 833169689Skan 834169689Skan e = simplify_replace_tree (expr, e1, e0); 835169689Skan if (zero_p (e) || nonzero_p (e)) 836169689Skan return e; 837169689Skan } 838169689Skan if (TREE_CODE (expr) == EQ_EXPR) 839169689Skan { 840169689Skan e0 = TREE_OPERAND (expr, 0); 841169689Skan e1 = TREE_OPERAND (expr, 1); 842169689Skan 843169689Skan /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ 844169689Skan e = simplify_replace_tree (cond, e0, e1); 845169689Skan if (zero_p (e)) 846169689Skan return e; 847169689Skan e = simplify_replace_tree (cond, e1, e0); 848169689Skan if (zero_p (e)) 849169689Skan return e; 850169689Skan } 851169689Skan if (TREE_CODE (expr) == NE_EXPR) 852169689Skan { 853169689Skan e0 = TREE_OPERAND (expr, 0); 854169689Skan e1 = TREE_OPERAND (expr, 1); 855169689Skan 856169689Skan /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ 857169689Skan e = simplify_replace_tree (cond, e0, e1); 858169689Skan if (zero_p (e)) 859169689Skan return boolean_true_node; 860169689Skan e = simplify_replace_tree (cond, e1, e0); 861169689Skan if (zero_p (e)) 862169689Skan return boolean_true_node; 863169689Skan } 864169689Skan 865169689Skan te = expand_simple_operations (expr); 866169689Skan 867169689Skan /* Check whether COND ==> EXPR. */ 868169689Skan notcond = invert_truthvalue (cond); 869169689Skan e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); 870169689Skan if (nonzero_p (e)) 871169689Skan return e; 872169689Skan 873169689Skan /* Check whether COND ==> not EXPR. */ 874169689Skan e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); 875169689Skan if (e && zero_p (e)) 876169689Skan return e; 877169689Skan 878169689Skan return expr; 879169689Skan} 880169689Skan 881169689Skan/* Tries to simplify EXPR using the condition COND. Returns the simplified 882169689Skan expression (or EXPR unchanged, if no simplification was possible). 883169689Skan Wrapper around tree_simplify_using_condition_1 that ensures that chains 884169689Skan of simple operations in definitions of ssa names in COND are expanded, 885169689Skan so that things like casts or incrementing the value of the bound before 886169689Skan the loop do not cause us to fail. */ 887169689Skan 888169689Skanstatic tree 889169689Skantree_simplify_using_condition (tree cond, tree expr) 890169689Skan{ 891169689Skan cond = expand_simple_operations (cond); 892169689Skan 893169689Skan return tree_simplify_using_condition_1 (cond, expr); 894169689Skan} 895169689Skan 896169689Skan/* The maximum number of dominator BBs we search for conditions 897169689Skan of loop header copies we use for simplifying a conditional 898169689Skan expression. */ 899169689Skan#define MAX_DOMINATORS_TO_WALK 8 900169689Skan 901169689Skan/* Tries to simplify EXPR using the conditions on entry to LOOP. 902169689Skan Record the conditions used for simplification to CONDS_USED. 903169689Skan Returns the simplified expression (or EXPR unchanged, if no 904169689Skan simplification was possible).*/ 905169689Skan 906169689Skanstatic tree 907169689Skansimplify_using_initial_conditions (struct loop *loop, tree expr, 908169689Skan tree *conds_used) 909169689Skan{ 910169689Skan edge e; 911169689Skan basic_block bb; 912169689Skan tree exp, cond; 913169689Skan int cnt = 0; 914169689Skan 915169689Skan if (TREE_CODE (expr) == INTEGER_CST) 916169689Skan return expr; 917169689Skan 918169689Skan /* Limit walking the dominators to avoid quadraticness in 919169689Skan the number of BBs times the number of loops in degenerate 920169689Skan cases. */ 921169689Skan for (bb = loop->header; 922169689Skan bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; 923169689Skan bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 924169689Skan { 925169689Skan if (!single_pred_p (bb)) 926169689Skan continue; 927169689Skan e = single_pred_edge (bb); 928169689Skan 929169689Skan if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 930169689Skan continue; 931169689Skan 932169689Skan cond = COND_EXPR_COND (last_stmt (e->src)); 933169689Skan if (e->flags & EDGE_FALSE_VALUE) 934169689Skan cond = invert_truthvalue (cond); 935169689Skan exp = tree_simplify_using_condition (cond, expr); 936169689Skan 937169689Skan if (exp != expr) 938169689Skan *conds_used = fold_build2 (TRUTH_AND_EXPR, 939169689Skan boolean_type_node, 940169689Skan *conds_used, 941169689Skan cond); 942169689Skan 943169689Skan expr = exp; 944169689Skan ++cnt; 945169689Skan } 946169689Skan 947169689Skan return expr; 948169689Skan} 949169689Skan 950169689Skan/* Tries to simplify EXPR using the evolutions of the loop invariants 951169689Skan in the superloops of LOOP. Returns the simplified expression 952169689Skan (or EXPR unchanged, if no simplification was possible). */ 953169689Skan 954169689Skanstatic tree 955169689Skansimplify_using_outer_evolutions (struct loop *loop, tree expr) 956169689Skan{ 957169689Skan enum tree_code code = TREE_CODE (expr); 958169689Skan bool changed; 959169689Skan tree e, e0, e1, e2; 960169689Skan 961169689Skan if (is_gimple_min_invariant (expr)) 962169689Skan return expr; 963169689Skan 964169689Skan if (code == TRUTH_OR_EXPR 965169689Skan || code == TRUTH_AND_EXPR 966169689Skan || code == COND_EXPR) 967169689Skan { 968169689Skan changed = false; 969169689Skan 970169689Skan e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); 971169689Skan if (TREE_OPERAND (expr, 0) != e0) 972169689Skan changed = true; 973169689Skan 974169689Skan e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); 975169689Skan if (TREE_OPERAND (expr, 1) != e1) 976169689Skan changed = true; 977169689Skan 978169689Skan if (code == COND_EXPR) 979169689Skan { 980169689Skan e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); 981169689Skan if (TREE_OPERAND (expr, 2) != e2) 982169689Skan changed = true; 983169689Skan } 984169689Skan else 985169689Skan e2 = NULL_TREE; 986169689Skan 987169689Skan if (changed) 988169689Skan { 989169689Skan if (code == COND_EXPR) 990169689Skan expr = fold_build3 (code, boolean_type_node, e0, e1, e2); 991169689Skan else 992169689Skan expr = fold_build2 (code, boolean_type_node, e0, e1); 993169689Skan } 994169689Skan 995169689Skan return expr; 996169689Skan } 997169689Skan 998169689Skan e = instantiate_parameters (loop, expr); 999169689Skan if (is_gimple_min_invariant (e)) 1000169689Skan return e; 1001169689Skan 1002169689Skan return expr; 1003169689Skan} 1004169689Skan 1005169689Skan/* Returns true if EXIT is the only possible exit from LOOP. */ 1006169689Skan 1007169689Skanstatic bool 1008169689Skanloop_only_exit_p (struct loop *loop, edge exit) 1009169689Skan{ 1010169689Skan basic_block *body; 1011169689Skan block_stmt_iterator bsi; 1012169689Skan unsigned i; 1013169689Skan tree call; 1014169689Skan 1015169689Skan if (exit != loop->single_exit) 1016169689Skan return false; 1017169689Skan 1018169689Skan body = get_loop_body (loop); 1019169689Skan for (i = 0; i < loop->num_nodes; i++) 1020169689Skan { 1021169689Skan for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi)) 1022169689Skan { 1023169689Skan call = get_call_expr_in (bsi_stmt (bsi)); 1024169689Skan if (call && TREE_SIDE_EFFECTS (call)) 1025169689Skan { 1026169689Skan free (body); 1027169689Skan return false; 1028169689Skan } 1029169689Skan } 1030169689Skan } 1031169689Skan 1032169689Skan free (body); 1033169689Skan return true; 1034169689Skan} 1035169689Skan 1036169689Skan/* Stores description of number of iterations of LOOP derived from 1037169689Skan EXIT (an exit edge of the LOOP) in NITER. Returns true if some 1038169689Skan useful information could be derived (and fields of NITER has 1039169689Skan meaning described in comments at struct tree_niter_desc 1040169689Skan declaration), false otherwise. If WARN is true and 1041169689Skan -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use 1042169689Skan potentially unsafe assumptions. */ 1043169689Skan 1044169689Skanbool 1045169689Skannumber_of_iterations_exit (struct loop *loop, edge exit, 1046169689Skan struct tree_niter_desc *niter, 1047169689Skan bool warn) 1048169689Skan{ 1049169689Skan tree stmt, cond, type; 1050169689Skan tree op0, op1; 1051169689Skan enum tree_code code; 1052169689Skan affine_iv iv0, iv1; 1053169689Skan 1054169689Skan if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) 1055169689Skan return false; 1056169689Skan 1057169689Skan niter->assumptions = boolean_false_node; 1058169689Skan stmt = last_stmt (exit->src); 1059169689Skan if (!stmt || TREE_CODE (stmt) != COND_EXPR) 1060169689Skan return false; 1061169689Skan 1062169689Skan /* We want the condition for staying inside loop. */ 1063169689Skan cond = COND_EXPR_COND (stmt); 1064169689Skan if (exit->flags & EDGE_TRUE_VALUE) 1065169689Skan cond = invert_truthvalue (cond); 1066169689Skan 1067169689Skan code = TREE_CODE (cond); 1068169689Skan switch (code) 1069169689Skan { 1070169689Skan case GT_EXPR: 1071169689Skan case GE_EXPR: 1072169689Skan case NE_EXPR: 1073169689Skan case LT_EXPR: 1074169689Skan case LE_EXPR: 1075169689Skan break; 1076169689Skan 1077169689Skan default: 1078169689Skan return false; 1079169689Skan } 1080169689Skan 1081169689Skan op0 = TREE_OPERAND (cond, 0); 1082169689Skan op1 = TREE_OPERAND (cond, 1); 1083169689Skan type = TREE_TYPE (op0); 1084169689Skan 1085169689Skan if (TREE_CODE (type) != INTEGER_TYPE 1086169689Skan && !POINTER_TYPE_P (type)) 1087169689Skan return false; 1088169689Skan 1089169689Skan if (!simple_iv (loop, stmt, op0, &iv0, false)) 1090169689Skan return false; 1091169689Skan if (!simple_iv (loop, stmt, op1, &iv1, false)) 1092169689Skan return false; 1093169689Skan 1094169689Skan /* We don't want to see undefined signed overflow warnings while 1095169689Skan computing the nmber of iterations. */ 1096169689Skan fold_defer_overflow_warnings (); 1097169689Skan 1098169689Skan iv0.base = expand_simple_operations (iv0.base); 1099169689Skan iv1.base = expand_simple_operations (iv1.base); 1100169689Skan if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter, 1101169689Skan loop_only_exit_p (loop, exit))) 1102169689Skan { 1103169689Skan fold_undefer_and_ignore_overflow_warnings (); 1104169689Skan return false; 1105169689Skan } 1106169689Skan 1107169689Skan if (optimize >= 3) 1108169689Skan { 1109169689Skan niter->assumptions = simplify_using_outer_evolutions (loop, 1110169689Skan niter->assumptions); 1111169689Skan niter->may_be_zero = simplify_using_outer_evolutions (loop, 1112169689Skan niter->may_be_zero); 1113169689Skan niter->niter = simplify_using_outer_evolutions (loop, niter->niter); 1114169689Skan } 1115169689Skan 1116169689Skan niter->additional_info = boolean_true_node; 1117169689Skan niter->assumptions 1118169689Skan = simplify_using_initial_conditions (loop, 1119169689Skan niter->assumptions, 1120169689Skan &niter->additional_info); 1121169689Skan niter->may_be_zero 1122169689Skan = simplify_using_initial_conditions (loop, 1123169689Skan niter->may_be_zero, 1124169689Skan &niter->additional_info); 1125169689Skan 1126169689Skan fold_undefer_and_ignore_overflow_warnings (); 1127169689Skan 1128169689Skan if (integer_onep (niter->assumptions)) 1129169689Skan return true; 1130169689Skan 1131169689Skan /* With -funsafe-loop-optimizations we assume that nothing bad can happen. 1132169689Skan But if we can prove that there is overflow or some other source of weird 1133169689Skan behavior, ignore the loop even with -funsafe-loop-optimizations. */ 1134169689Skan if (integer_zerop (niter->assumptions)) 1135169689Skan return false; 1136169689Skan 1137169689Skan if (flag_unsafe_loop_optimizations) 1138169689Skan niter->assumptions = boolean_true_node; 1139169689Skan 1140169689Skan if (warn) 1141169689Skan { 1142169689Skan const char *wording; 1143169689Skan location_t loc = EXPR_LOCATION (stmt); 1144169689Skan 1145169689Skan /* We can provide a more specific warning if one of the operator is 1146169689Skan constant and the other advances by +1 or -1. */ 1147169689Skan if (!zero_p (iv1.step) 1148169689Skan ? (zero_p (iv0.step) 1149169689Skan && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) 1150169689Skan : (iv0.step 1151169689Skan && (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))) 1152169689Skan wording = 1153169689Skan flag_unsafe_loop_optimizations 1154169689Skan ? N_("assuming that the loop is not infinite") 1155169689Skan : N_("cannot optimize possibly infinite loops"); 1156169689Skan else 1157169689Skan wording = 1158169689Skan flag_unsafe_loop_optimizations 1159169689Skan ? N_("assuming that the loop counter does not overflow") 1160169689Skan : N_("cannot optimize loop, the loop counter may overflow"); 1161169689Skan 1162169689Skan if (LOCATION_LINE (loc) > 0) 1163169689Skan warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording)); 1164169689Skan else 1165169689Skan warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); 1166169689Skan } 1167169689Skan 1168169689Skan return flag_unsafe_loop_optimizations; 1169169689Skan} 1170169689Skan 1171169689Skan/* Try to determine the number of iterations of LOOP. If we succeed, 1172169689Skan expression giving number of iterations is returned and *EXIT is 1173169689Skan set to the edge from that the information is obtained. Otherwise 1174169689Skan chrec_dont_know is returned. */ 1175169689Skan 1176169689Skantree 1177169689Skanfind_loop_niter (struct loop *loop, edge *exit) 1178169689Skan{ 1179169689Skan unsigned n_exits, i; 1180169689Skan edge *exits = get_loop_exit_edges (loop, &n_exits); 1181169689Skan edge ex; 1182169689Skan tree niter = NULL_TREE, aniter; 1183169689Skan struct tree_niter_desc desc; 1184169689Skan 1185169689Skan *exit = NULL; 1186169689Skan for (i = 0; i < n_exits; i++) 1187169689Skan { 1188169689Skan ex = exits[i]; 1189169689Skan if (!just_once_each_iteration_p (loop, ex->src)) 1190169689Skan continue; 1191169689Skan 1192169689Skan if (!number_of_iterations_exit (loop, ex, &desc, false)) 1193169689Skan continue; 1194169689Skan 1195169689Skan if (nonzero_p (desc.may_be_zero)) 1196169689Skan { 1197169689Skan /* We exit in the first iteration through this exit. 1198169689Skan We won't find anything better. */ 1199169689Skan niter = build_int_cst (unsigned_type_node, 0); 1200169689Skan *exit = ex; 1201169689Skan break; 1202169689Skan } 1203169689Skan 1204169689Skan if (!zero_p (desc.may_be_zero)) 1205169689Skan continue; 1206169689Skan 1207169689Skan aniter = desc.niter; 1208169689Skan 1209169689Skan if (!niter) 1210169689Skan { 1211169689Skan /* Nothing recorded yet. */ 1212169689Skan niter = aniter; 1213169689Skan *exit = ex; 1214169689Skan continue; 1215169689Skan } 1216169689Skan 1217169689Skan /* Prefer constants, the lower the better. */ 1218169689Skan if (TREE_CODE (aniter) != INTEGER_CST) 1219169689Skan continue; 1220169689Skan 1221169689Skan if (TREE_CODE (niter) != INTEGER_CST) 1222169689Skan { 1223169689Skan niter = aniter; 1224169689Skan *exit = ex; 1225169689Skan continue; 1226169689Skan } 1227169689Skan 1228169689Skan if (tree_int_cst_lt (aniter, niter)) 1229169689Skan { 1230169689Skan niter = aniter; 1231169689Skan *exit = ex; 1232169689Skan continue; 1233169689Skan } 1234169689Skan } 1235169689Skan free (exits); 1236169689Skan 1237169689Skan return niter ? niter : chrec_dont_know; 1238169689Skan} 1239169689Skan 1240169689Skan/* 1241169689Skan 1242169689Skan Analysis of a number of iterations of a loop by a brute-force evaluation. 1243169689Skan 1244169689Skan*/ 1245169689Skan 1246169689Skan/* Bound on the number of iterations we try to evaluate. */ 1247169689Skan 1248169689Skan#define MAX_ITERATIONS_TO_TRACK \ 1249169689Skan ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) 1250169689Skan 1251169689Skan/* Returns the loop phi node of LOOP such that ssa name X is derived from its 1252169689Skan result by a chain of operations such that all but exactly one of their 1253169689Skan operands are constants. */ 1254169689Skan 1255169689Skanstatic tree 1256169689Skanchain_of_csts_start (struct loop *loop, tree x) 1257169689Skan{ 1258169689Skan tree stmt = SSA_NAME_DEF_STMT (x); 1259169689Skan tree use; 1260169689Skan basic_block bb = bb_for_stmt (stmt); 1261169689Skan 1262169689Skan if (!bb 1263169689Skan || !flow_bb_inside_loop_p (loop, bb)) 1264169689Skan return NULL_TREE; 1265169689Skan 1266169689Skan if (TREE_CODE (stmt) == PHI_NODE) 1267169689Skan { 1268169689Skan if (bb == loop->header) 1269169689Skan return stmt; 1270169689Skan 1271169689Skan return NULL_TREE; 1272169689Skan } 1273169689Skan 1274169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1275169689Skan return NULL_TREE; 1276169689Skan 1277169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 1278169689Skan return NULL_TREE; 1279169689Skan if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P) 1280169689Skan return NULL_TREE; 1281169689Skan 1282169689Skan use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 1283169689Skan if (use == NULL_USE_OPERAND_P) 1284169689Skan return NULL_TREE; 1285169689Skan 1286169689Skan return chain_of_csts_start (loop, use); 1287169689Skan} 1288169689Skan 1289169689Skan/* Determines whether the expression X is derived from a result of a phi node 1290169689Skan in header of LOOP such that 1291169689Skan 1292169689Skan * the derivation of X consists only from operations with constants 1293169689Skan * the initial value of the phi node is constant 1294169689Skan * the value of the phi node in the next iteration can be derived from the 1295169689Skan value in the current iteration by a chain of operations with constants. 1296169689Skan 1297169689Skan If such phi node exists, it is returned. If X is a constant, X is returned 1298169689Skan unchanged. Otherwise NULL_TREE is returned. */ 1299169689Skan 1300169689Skanstatic tree 1301169689Skanget_base_for (struct loop *loop, tree x) 1302169689Skan{ 1303169689Skan tree phi, init, next; 1304169689Skan 1305169689Skan if (is_gimple_min_invariant (x)) 1306169689Skan return x; 1307169689Skan 1308169689Skan phi = chain_of_csts_start (loop, x); 1309169689Skan if (!phi) 1310169689Skan return NULL_TREE; 1311169689Skan 1312169689Skan init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 1313169689Skan next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); 1314169689Skan 1315169689Skan if (TREE_CODE (next) != SSA_NAME) 1316169689Skan return NULL_TREE; 1317169689Skan 1318169689Skan if (!is_gimple_min_invariant (init)) 1319169689Skan return NULL_TREE; 1320169689Skan 1321169689Skan if (chain_of_csts_start (loop, next) != phi) 1322169689Skan return NULL_TREE; 1323169689Skan 1324169689Skan return phi; 1325169689Skan} 1326169689Skan 1327169689Skan/* Given an expression X, then 1328169689Skan 1329169689Skan * if X is NULL_TREE, we return the constant BASE. 1330169689Skan * otherwise X is a SSA name, whose value in the considered loop is derived 1331169689Skan by a chain of operations with constant from a result of a phi node in 1332169689Skan the header of the loop. Then we return value of X when the value of the 1333169689Skan result of this phi node is given by the constant BASE. */ 1334169689Skan 1335169689Skanstatic tree 1336169689Skanget_val_for (tree x, tree base) 1337169689Skan{ 1338169689Skan tree stmt, nx, val; 1339169689Skan use_operand_p op; 1340169689Skan ssa_op_iter iter; 1341169689Skan 1342169689Skan gcc_assert (is_gimple_min_invariant (base)); 1343169689Skan 1344169689Skan if (!x) 1345169689Skan return base; 1346169689Skan 1347169689Skan stmt = SSA_NAME_DEF_STMT (x); 1348169689Skan if (TREE_CODE (stmt) == PHI_NODE) 1349169689Skan return base; 1350169689Skan 1351169689Skan FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE) 1352169689Skan { 1353169689Skan nx = USE_FROM_PTR (op); 1354169689Skan val = get_val_for (nx, base); 1355169689Skan SET_USE (op, val); 1356169689Skan val = fold (TREE_OPERAND (stmt, 1)); 1357169689Skan SET_USE (op, nx); 1358169689Skan /* only iterate loop once. */ 1359169689Skan return val; 1360169689Skan } 1361169689Skan 1362169689Skan /* Should never reach here. */ 1363169689Skan gcc_unreachable(); 1364169689Skan} 1365169689Skan 1366169689Skan/* Tries to count the number of iterations of LOOP till it exits by EXIT 1367169689Skan by brute force -- i.e. by determining the value of the operands of the 1368169689Skan condition at EXIT in first few iterations of the loop (assuming that 1369169689Skan these values are constant) and determining the first one in that the 1370169689Skan condition is not satisfied. Returns the constant giving the number 1371169689Skan of the iterations of LOOP if successful, chrec_dont_know otherwise. */ 1372169689Skan 1373169689Skantree 1374169689Skanloop_niter_by_eval (struct loop *loop, edge exit) 1375169689Skan{ 1376169689Skan tree cond, cnd, acnd; 1377169689Skan tree op[2], val[2], next[2], aval[2], phi[2]; 1378169689Skan unsigned i, j; 1379169689Skan enum tree_code cmp; 1380169689Skan 1381169689Skan cond = last_stmt (exit->src); 1382169689Skan if (!cond || TREE_CODE (cond) != COND_EXPR) 1383169689Skan return chrec_dont_know; 1384169689Skan 1385169689Skan cnd = COND_EXPR_COND (cond); 1386169689Skan if (exit->flags & EDGE_TRUE_VALUE) 1387169689Skan cnd = invert_truthvalue (cnd); 1388169689Skan 1389169689Skan cmp = TREE_CODE (cnd); 1390169689Skan switch (cmp) 1391169689Skan { 1392169689Skan case EQ_EXPR: 1393169689Skan case NE_EXPR: 1394169689Skan case GT_EXPR: 1395169689Skan case GE_EXPR: 1396169689Skan case LT_EXPR: 1397169689Skan case LE_EXPR: 1398169689Skan for (j = 0; j < 2; j++) 1399169689Skan op[j] = TREE_OPERAND (cnd, j); 1400169689Skan break; 1401169689Skan 1402169689Skan default: 1403169689Skan return chrec_dont_know; 1404169689Skan } 1405169689Skan 1406169689Skan for (j = 0; j < 2; j++) 1407169689Skan { 1408169689Skan phi[j] = get_base_for (loop, op[j]); 1409169689Skan if (!phi[j]) 1410169689Skan return chrec_dont_know; 1411169689Skan } 1412169689Skan 1413169689Skan for (j = 0; j < 2; j++) 1414169689Skan { 1415169689Skan if (TREE_CODE (phi[j]) == PHI_NODE) 1416169689Skan { 1417169689Skan val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop)); 1418169689Skan next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop)); 1419169689Skan } 1420169689Skan else 1421169689Skan { 1422169689Skan val[j] = phi[j]; 1423169689Skan next[j] = NULL_TREE; 1424169689Skan op[j] = NULL_TREE; 1425169689Skan } 1426169689Skan } 1427169689Skan 1428169689Skan /* Don't issue signed overflow warnings. */ 1429169689Skan fold_defer_overflow_warnings (); 1430169689Skan 1431169689Skan for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) 1432169689Skan { 1433169689Skan for (j = 0; j < 2; j++) 1434169689Skan aval[j] = get_val_for (op[j], val[j]); 1435169689Skan 1436169689Skan acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); 1437169689Skan if (acnd && zero_p (acnd)) 1438169689Skan { 1439169689Skan fold_undefer_and_ignore_overflow_warnings (); 1440169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1441169689Skan fprintf (dump_file, 1442169689Skan "Proved that loop %d iterates %d times using brute force.\n", 1443169689Skan loop->num, i); 1444169689Skan return build_int_cst (unsigned_type_node, i); 1445169689Skan } 1446169689Skan 1447169689Skan for (j = 0; j < 2; j++) 1448169689Skan { 1449169689Skan val[j] = get_val_for (next[j], val[j]); 1450169689Skan if (!is_gimple_min_invariant (val[j])) 1451169689Skan { 1452169689Skan fold_undefer_and_ignore_overflow_warnings (); 1453169689Skan return chrec_dont_know; 1454169689Skan } 1455169689Skan } 1456169689Skan } 1457169689Skan 1458169689Skan fold_undefer_and_ignore_overflow_warnings (); 1459169689Skan 1460169689Skan return chrec_dont_know; 1461169689Skan} 1462169689Skan 1463169689Skan/* Finds the exit of the LOOP by that the loop exits after a constant 1464169689Skan number of iterations and stores the exit edge to *EXIT. The constant 1465169689Skan giving the number of iterations of LOOP is returned. The number of 1466169689Skan iterations is determined using loop_niter_by_eval (i.e. by brute force 1467169689Skan evaluation). If we are unable to find the exit for that loop_niter_by_eval 1468169689Skan determines the number of iterations, chrec_dont_know is returned. */ 1469169689Skan 1470169689Skantree 1471169689Skanfind_loop_niter_by_eval (struct loop *loop, edge *exit) 1472169689Skan{ 1473169689Skan unsigned n_exits, i; 1474169689Skan edge *exits = get_loop_exit_edges (loop, &n_exits); 1475169689Skan edge ex; 1476169689Skan tree niter = NULL_TREE, aniter; 1477169689Skan 1478169689Skan *exit = NULL; 1479169689Skan for (i = 0; i < n_exits; i++) 1480169689Skan { 1481169689Skan ex = exits[i]; 1482169689Skan if (!just_once_each_iteration_p (loop, ex->src)) 1483169689Skan continue; 1484169689Skan 1485169689Skan aniter = loop_niter_by_eval (loop, ex); 1486169689Skan if (chrec_contains_undetermined (aniter)) 1487169689Skan continue; 1488169689Skan 1489169689Skan if (niter 1490169689Skan && !tree_int_cst_lt (aniter, niter)) 1491169689Skan continue; 1492169689Skan 1493169689Skan niter = aniter; 1494169689Skan *exit = ex; 1495169689Skan } 1496169689Skan free (exits); 1497169689Skan 1498169689Skan return niter ? niter : chrec_dont_know; 1499169689Skan} 1500169689Skan 1501169689Skan/* 1502169689Skan 1503169689Skan Analysis of upper bounds on number of iterations of a loop. 1504169689Skan 1505169689Skan*/ 1506169689Skan 1507169689Skan/* Returns true if we can prove that COND ==> VAL >= 0. */ 1508169689Skan 1509169689Skanstatic bool 1510169689Skanimplies_nonnegative_p (tree cond, tree val) 1511169689Skan{ 1512169689Skan tree type = TREE_TYPE (val); 1513169689Skan tree compare; 1514169689Skan 1515169689Skan if (tree_expr_nonnegative_p (val)) 1516169689Skan return true; 1517169689Skan 1518169689Skan if (nonzero_p (cond)) 1519169689Skan return false; 1520169689Skan 1521169689Skan compare = fold_build2 (GE_EXPR, 1522169689Skan boolean_type_node, val, build_int_cst (type, 0)); 1523169689Skan compare = tree_simplify_using_condition_1 (cond, compare); 1524169689Skan 1525169689Skan return nonzero_p (compare); 1526169689Skan} 1527169689Skan 1528169689Skan/* Returns true if we can prove that COND ==> A >= B. */ 1529169689Skan 1530169689Skanstatic bool 1531169689Skanimplies_ge_p (tree cond, tree a, tree b) 1532169689Skan{ 1533169689Skan tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b); 1534169689Skan 1535169689Skan if (nonzero_p (compare)) 1536169689Skan return true; 1537169689Skan 1538169689Skan if (nonzero_p (cond)) 1539169689Skan return false; 1540169689Skan 1541169689Skan compare = tree_simplify_using_condition_1 (cond, compare); 1542169689Skan 1543169689Skan return nonzero_p (compare); 1544169689Skan} 1545169689Skan 1546169689Skan/* Returns a constant upper bound on the value of expression VAL. VAL 1547169689Skan is considered to be unsigned. If its type is signed, its value must 1548169689Skan be nonnegative. 1549169689Skan 1550169689Skan The condition ADDITIONAL must be satisfied (for example, if VAL is 1551169689Skan "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that 1552169689Skan VAL is at most (unsigned) MAX_INT). */ 1553169689Skan 1554169689Skanstatic double_int 1555169689Skanderive_constant_upper_bound (tree val, tree additional) 1556169689Skan{ 1557169689Skan tree type = TREE_TYPE (val); 1558169689Skan tree op0, op1, subtype, maxt; 1559169689Skan double_int bnd, max, mmax, cst; 1560169689Skan 1561169689Skan if (INTEGRAL_TYPE_P (type)) 1562169689Skan maxt = TYPE_MAX_VALUE (type); 1563169689Skan else 1564169689Skan maxt = upper_bound_in_type (type, type); 1565169689Skan 1566169689Skan max = tree_to_double_int (maxt); 1567169689Skan 1568169689Skan switch (TREE_CODE (val)) 1569169689Skan { 1570169689Skan case INTEGER_CST: 1571169689Skan return tree_to_double_int (val); 1572169689Skan 1573169689Skan case NOP_EXPR: 1574169689Skan case CONVERT_EXPR: 1575169689Skan op0 = TREE_OPERAND (val, 0); 1576169689Skan subtype = TREE_TYPE (op0); 1577169689Skan if (!TYPE_UNSIGNED (subtype) 1578169689Skan /* If TYPE is also signed, the fact that VAL is nonnegative implies 1579169689Skan that OP0 is nonnegative. */ 1580169689Skan && TYPE_UNSIGNED (type) 1581169689Skan && !implies_nonnegative_p (additional, op0)) 1582169689Skan { 1583169689Skan /* If we cannot prove that the casted expression is nonnegative, 1584169689Skan we cannot establish more useful upper bound than the precision 1585169689Skan of the type gives us. */ 1586169689Skan return max; 1587169689Skan } 1588169689Skan 1589169689Skan /* We now know that op0 is an nonnegative value. Try deriving an upper 1590169689Skan bound for it. */ 1591169689Skan bnd = derive_constant_upper_bound (op0, additional); 1592169689Skan 1593169689Skan /* If the bound does not fit in TYPE, max. value of TYPE could be 1594169689Skan attained. */ 1595169689Skan if (double_int_ucmp (max, bnd) < 0) 1596169689Skan return max; 1597169689Skan 1598169689Skan return bnd; 1599169689Skan 1600169689Skan case PLUS_EXPR: 1601169689Skan case MINUS_EXPR: 1602169689Skan op0 = TREE_OPERAND (val, 0); 1603169689Skan op1 = TREE_OPERAND (val, 1); 1604169689Skan 1605169689Skan if (TREE_CODE (op1) != INTEGER_CST 1606169689Skan || !implies_nonnegative_p (additional, op0)) 1607169689Skan return max; 1608169689Skan 1609169689Skan /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to 1610169689Skan choose the most logical way how to treat this constant regardless 1611169689Skan of the signedness of the type. */ 1612169689Skan cst = tree_to_double_int (op1); 1613169689Skan cst = double_int_sext (cst, TYPE_PRECISION (type)); 1614169689Skan if (TREE_CODE (val) == PLUS_EXPR) 1615169689Skan cst = double_int_neg (cst); 1616169689Skan 1617169689Skan bnd = derive_constant_upper_bound (op0, additional); 1618169689Skan 1619169689Skan if (double_int_negative_p (cst)) 1620169689Skan { 1621169689Skan cst = double_int_neg (cst); 1622169689Skan /* Avoid CST == 0x80000... */ 1623169689Skan if (double_int_negative_p (cst)) 1624169689Skan return max;; 1625169689Skan 1626169689Skan /* OP0 + CST. We need to check that 1627169689Skan BND <= MAX (type) - CST. */ 1628169689Skan 1629169689Skan mmax = double_int_add (max, double_int_neg (cst)); 1630169689Skan if (double_int_ucmp (bnd, mmax) > 0) 1631169689Skan return max; 1632169689Skan 1633169689Skan return double_int_add (bnd, cst); 1634169689Skan } 1635169689Skan else 1636169689Skan { 1637169689Skan /* OP0 - CST, where CST >= 0. 1638169689Skan 1639169689Skan If TYPE is signed, we have already verified that OP0 >= 0, and we 1640169689Skan know that the result is nonnegative. This implies that 1641169689Skan VAL <= BND - CST. 1642169689Skan 1643169689Skan If TYPE is unsigned, we must additionally know that OP0 >= CST, 1644169689Skan otherwise the operation underflows. 1645169689Skan */ 1646169689Skan 1647169689Skan /* This should only happen if the type is unsigned; however, for 1648169689Skan programs that use overflowing signed arithmetics even with 1649169689Skan -fno-wrapv, this condition may also be true for signed values. */ 1650169689Skan if (double_int_ucmp (bnd, cst) < 0) 1651169689Skan return max; 1652169689Skan 1653169689Skan if (TYPE_UNSIGNED (type) 1654169689Skan && !implies_ge_p (additional, 1655169689Skan op0, double_int_to_tree (type, cst))) 1656169689Skan return max; 1657169689Skan 1658169689Skan bnd = double_int_add (bnd, double_int_neg (cst)); 1659169689Skan } 1660169689Skan 1661169689Skan return bnd; 1662169689Skan 1663169689Skan case FLOOR_DIV_EXPR: 1664169689Skan case EXACT_DIV_EXPR: 1665169689Skan op0 = TREE_OPERAND (val, 0); 1666169689Skan op1 = TREE_OPERAND (val, 1); 1667169689Skan if (TREE_CODE (op1) != INTEGER_CST 1668169689Skan || tree_int_cst_sign_bit (op1)) 1669169689Skan return max; 1670169689Skan 1671169689Skan bnd = derive_constant_upper_bound (op0, additional); 1672169689Skan return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); 1673169689Skan 1674169689Skan default: 1675169689Skan return max; 1676169689Skan } 1677169689Skan} 1678169689Skan 1679169689Skan/* Records that AT_STMT is executed at most BOUND times in LOOP. The 1680169689Skan additional condition ADDITIONAL is recorded with the bound. */ 1681169689Skan 1682169689Skanvoid 1683169689Skanrecord_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) 1684169689Skan{ 1685169689Skan struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); 1686169689Skan double_int i_bound = derive_constant_upper_bound (bound, additional); 1687169689Skan tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)), 1688169689Skan i_bound); 1689169689Skan 1690169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1691169689Skan { 1692169689Skan fprintf (dump_file, "Statements after "); 1693169689Skan print_generic_expr (dump_file, at_stmt, TDF_SLIM); 1694169689Skan fprintf (dump_file, " are executed at most "); 1695169689Skan print_generic_expr (dump_file, bound, TDF_SLIM); 1696169689Skan fprintf (dump_file, " (bounded by "); 1697169689Skan print_generic_expr (dump_file, c_bound, TDF_SLIM); 1698169689Skan fprintf (dump_file, ") times in loop %d.\n", loop->num); 1699169689Skan } 1700169689Skan 1701169689Skan elt->bound = c_bound; 1702169689Skan elt->at_stmt = at_stmt; 1703169689Skan elt->next = loop->bounds; 1704169689Skan loop->bounds = elt; 1705169689Skan} 1706169689Skan 1707169689Skan/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe 1708169689Skan approximation of the number of iterations for LOOP. */ 1709169689Skan 1710169689Skanstatic void 1711169689Skancompute_estimated_nb_iterations (struct loop *loop) 1712169689Skan{ 1713169689Skan struct nb_iter_bound *bound; 1714169689Skan 1715169689Skan for (bound = loop->bounds; bound; bound = bound->next) 1716169689Skan { 1717169689Skan if (TREE_CODE (bound->bound) != INTEGER_CST) 1718169689Skan continue; 1719169689Skan 1720169689Skan /* Update only when there is no previous estimation, or when the current 1721169689Skan estimation is smaller. */ 1722169689Skan if (chrec_contains_undetermined (loop->estimated_nb_iterations) 1723169689Skan || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)) 1724169689Skan loop->estimated_nb_iterations = bound->bound; 1725169689Skan } 1726169689Skan} 1727169689Skan 1728169689Skan/* The following analyzers are extracting informations on the bounds 1729169689Skan of LOOP from the following undefined behaviors: 1730169689Skan 1731169689Skan - data references should not access elements over the statically 1732169689Skan allocated size, 1733169689Skan 1734169689Skan - signed variables should not overflow when flag_wrapv is not set. 1735169689Skan*/ 1736169689Skan 1737169689Skanstatic void 1738169689Skaninfer_loop_bounds_from_undefined (struct loop *loop) 1739169689Skan{ 1740169689Skan unsigned i; 1741169689Skan basic_block bb, *bbs; 1742169689Skan block_stmt_iterator bsi; 1743169689Skan 1744169689Skan bbs = get_loop_body (loop); 1745169689Skan 1746169689Skan for (i = 0; i < loop->num_nodes; i++) 1747169689Skan { 1748169689Skan bb = bbs[i]; 1749169689Skan 1750171825Skan /* If BB is not executed in each iteration of the loop, we cannot 1751171825Skan use the operations in it to infer reliable upper bound on the 1752171825Skan # of iterations of the loop. */ 1753171825Skan if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1754171825Skan continue; 1755171825Skan 1756169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1757169689Skan { 1758169689Skan tree stmt = bsi_stmt (bsi); 1759169689Skan 1760169689Skan switch (TREE_CODE (stmt)) 1761169689Skan { 1762169689Skan case MODIFY_EXPR: 1763169689Skan { 1764169689Skan tree op0 = TREE_OPERAND (stmt, 0); 1765169689Skan tree op1 = TREE_OPERAND (stmt, 1); 1766169689Skan 1767169689Skan /* For each array access, analyze its access function 1768169689Skan and record a bound on the loop iteration domain. */ 1769169689Skan if (TREE_CODE (op1) == ARRAY_REF 1770169689Skan && !array_ref_contains_indirect_ref (op1)) 1771169689Skan estimate_iters_using_array (stmt, op1); 1772169689Skan 1773169689Skan if (TREE_CODE (op0) == ARRAY_REF 1774169689Skan && !array_ref_contains_indirect_ref (op0)) 1775169689Skan estimate_iters_using_array (stmt, op0); 1776169689Skan 1777169689Skan /* For each signed type variable in LOOP, analyze its 1778169689Skan scalar evolution and record a bound of the loop 1779169689Skan based on the type's ranges. */ 1780169689Skan else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME) 1781169689Skan { 1782169689Skan tree init, step, diff, estimation; 1783169689Skan tree scev = instantiate_parameters 1784169689Skan (loop, analyze_scalar_evolution (loop, op0)); 1785169689Skan tree type = chrec_type (scev); 1786169689Skan 1787169689Skan if (chrec_contains_undetermined (scev) 1788169689Skan || TYPE_OVERFLOW_WRAPS (type)) 1789169689Skan break; 1790169689Skan 1791169689Skan init = initial_condition_in_loop_num (scev, loop->num); 1792169689Skan step = evolution_part_in_loop_num (scev, loop->num); 1793169689Skan 1794169689Skan if (init == NULL_TREE 1795169689Skan || step == NULL_TREE 1796169689Skan || TREE_CODE (init) != INTEGER_CST 1797169689Skan || TREE_CODE (step) != INTEGER_CST 1798169689Skan || TYPE_MIN_VALUE (type) == NULL_TREE 1799169689Skan || TYPE_MAX_VALUE (type) == NULL_TREE) 1800169689Skan break; 1801169689Skan 1802169689Skan if (integer_nonzerop (step)) 1803169689Skan { 1804169689Skan tree utype; 1805169689Skan 1806169689Skan if (tree_int_cst_lt (step, integer_zero_node)) 1807169689Skan diff = fold_build2 (MINUS_EXPR, type, init, 1808169689Skan TYPE_MIN_VALUE (type)); 1809169689Skan else 1810169689Skan diff = fold_build2 (MINUS_EXPR, type, 1811169689Skan TYPE_MAX_VALUE (type), init); 1812169689Skan 1813169689Skan utype = unsigned_type_for (type); 1814169689Skan estimation = fold_build2 (CEIL_DIV_EXPR, type, diff, 1815169689Skan step); 1816169689Skan record_estimate (loop, 1817169689Skan fold_convert (utype, estimation), 1818169689Skan boolean_true_node, stmt); 1819169689Skan } 1820169689Skan } 1821169689Skan 1822169689Skan break; 1823169689Skan } 1824169689Skan 1825169689Skan case CALL_EXPR: 1826169689Skan { 1827169689Skan tree args; 1828169689Skan 1829169689Skan for (args = TREE_OPERAND (stmt, 1); args; 1830169689Skan args = TREE_CHAIN (args)) 1831169689Skan if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF 1832169689Skan && !array_ref_contains_indirect_ref (TREE_VALUE (args))) 1833169689Skan estimate_iters_using_array (stmt, TREE_VALUE (args)); 1834169689Skan 1835169689Skan break; 1836169689Skan } 1837169689Skan 1838169689Skan default: 1839169689Skan break; 1840169689Skan } 1841169689Skan } 1842169689Skan } 1843169689Skan 1844169689Skan compute_estimated_nb_iterations (loop); 1845169689Skan free (bbs); 1846169689Skan} 1847169689Skan 1848169689Skan/* Records estimates on numbers of iterations of LOOP. */ 1849169689Skan 1850169689Skanstatic void 1851169689Skanestimate_numbers_of_iterations_loop (struct loop *loop) 1852169689Skan{ 1853169689Skan edge *exits; 1854169689Skan tree niter, type; 1855169689Skan unsigned i, n_exits; 1856169689Skan struct tree_niter_desc niter_desc; 1857169689Skan 1858169689Skan /* Give up if we already have tried to compute an estimation. */ 1859169689Skan if (loop->estimated_nb_iterations == chrec_dont_know 1860169689Skan /* Or when we already have an estimation. */ 1861169689Skan || (loop->estimated_nb_iterations != NULL_TREE 1862169689Skan && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST)) 1863169689Skan return; 1864169689Skan else 1865169689Skan loop->estimated_nb_iterations = chrec_dont_know; 1866169689Skan 1867169689Skan exits = get_loop_exit_edges (loop, &n_exits); 1868169689Skan for (i = 0; i < n_exits; i++) 1869169689Skan { 1870169689Skan if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false)) 1871169689Skan continue; 1872169689Skan 1873169689Skan niter = niter_desc.niter; 1874169689Skan type = TREE_TYPE (niter); 1875169689Skan if (!zero_p (niter_desc.may_be_zero) 1876169689Skan && !nonzero_p (niter_desc.may_be_zero)) 1877169689Skan niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, 1878169689Skan build_int_cst (type, 0), 1879169689Skan niter); 1880169689Skan record_estimate (loop, niter, 1881169689Skan niter_desc.additional_info, 1882169689Skan last_stmt (exits[i]->src)); 1883169689Skan } 1884169689Skan free (exits); 1885169689Skan 1886169689Skan if (chrec_contains_undetermined (loop->estimated_nb_iterations)) 1887169689Skan infer_loop_bounds_from_undefined (loop); 1888169689Skan} 1889169689Skan 1890169689Skan/* Records estimates on numbers of iterations of LOOPS. */ 1891169689Skan 1892169689Skanvoid 1893169689Skanestimate_numbers_of_iterations (struct loops *loops) 1894169689Skan{ 1895169689Skan unsigned i; 1896169689Skan struct loop *loop; 1897169689Skan 1898169689Skan /* We don't want to issue signed overflow warnings while getting 1899169689Skan loop iteration estimates. */ 1900169689Skan fold_defer_overflow_warnings (); 1901169689Skan 1902169689Skan for (i = 1; i < loops->num; i++) 1903169689Skan { 1904169689Skan loop = loops->parray[i]; 1905169689Skan if (loop) 1906169689Skan estimate_numbers_of_iterations_loop (loop); 1907169689Skan } 1908169689Skan 1909169689Skan fold_undefer_and_ignore_overflow_warnings (); 1910169689Skan} 1911169689Skan 1912169689Skan/* Returns true if statement S1 dominates statement S2. */ 1913169689Skan 1914169689Skanstatic bool 1915169689Skanstmt_dominates_stmt_p (tree s1, tree s2) 1916169689Skan{ 1917169689Skan basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2); 1918169689Skan 1919169689Skan if (!bb1 1920169689Skan || s1 == s2) 1921169689Skan return true; 1922169689Skan 1923169689Skan if (bb1 == bb2) 1924169689Skan { 1925169689Skan block_stmt_iterator bsi; 1926169689Skan 1927169689Skan for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi)) 1928169689Skan if (bsi_stmt (bsi) == s1) 1929169689Skan return true; 1930169689Skan 1931169689Skan return false; 1932169689Skan } 1933169689Skan 1934169689Skan return dominated_by_p (CDI_DOMINATORS, bb2, bb1); 1935169689Skan} 1936169689Skan 1937169689Skan/* Returns true when we can prove that the number of executions of 1938169689Skan STMT in the loop is at most NITER, according to the fact 1939169689Skan that the statement NITER_BOUND->at_stmt is executed at most 1940169689Skan NITER_BOUND->bound times. */ 1941169689Skan 1942169689Skanstatic bool 1943169689Skann_of_executions_at_most (tree stmt, 1944169689Skan struct nb_iter_bound *niter_bound, 1945169689Skan tree niter) 1946169689Skan{ 1947169689Skan tree cond; 1948169689Skan tree bound = niter_bound->bound; 1949169689Skan tree bound_type = TREE_TYPE (bound); 1950169689Skan tree nit_type = TREE_TYPE (niter); 1951169689Skan enum tree_code cmp; 1952169689Skan 1953169689Skan gcc_assert (TYPE_UNSIGNED (bound_type) 1954169689Skan && TYPE_UNSIGNED (nit_type) 1955169689Skan && is_gimple_min_invariant (bound)); 1956169689Skan if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type)) 1957169689Skan bound = fold_convert (nit_type, bound); 1958169689Skan else 1959169689Skan niter = fold_convert (bound_type, niter); 1960169689Skan 1961169689Skan /* After the statement niter_bound->at_stmt we know that anything is 1962169689Skan executed at most BOUND times. */ 1963169689Skan if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt)) 1964169689Skan cmp = GE_EXPR; 1965169689Skan /* Before the statement niter_bound->at_stmt we know that anything 1966169689Skan is executed at most BOUND + 1 times. */ 1967169689Skan else 1968169689Skan cmp = GT_EXPR; 1969169689Skan 1970169689Skan cond = fold_binary (cmp, boolean_type_node, niter, bound); 1971169689Skan return nonzero_p (cond); 1972169689Skan} 1973169689Skan 1974169689Skan/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ 1975169689Skan 1976169689Skanbool 1977169689Skannowrap_type_p (tree type) 1978169689Skan{ 1979169689Skan if (INTEGRAL_TYPE_P (type) 1980169689Skan && TYPE_OVERFLOW_UNDEFINED (type)) 1981169689Skan return true; 1982169689Skan 1983169689Skan if (POINTER_TYPE_P (type)) 1984169689Skan return true; 1985169689Skan 1986169689Skan return false; 1987169689Skan} 1988169689Skan 1989169689Skan/* Return false only when the induction variable BASE + STEP * I is 1990169689Skan known to not overflow: i.e. when the number of iterations is small 1991169689Skan enough with respect to the step and initial condition in order to 1992169689Skan keep the evolution confined in TYPEs bounds. Return true when the 1993169689Skan iv is known to overflow or when the property is not computable. 1994169689Skan 1995169689Skan USE_OVERFLOW_SEMANTICS is true if this function should assume that 1996169689Skan the rules for overflow of the given language apply (e.g., that signed 1997169689Skan arithmetics in C does not overflow). */ 1998169689Skan 1999169689Skanbool 2000169689Skanscev_probably_wraps_p (tree base, tree step, 2001169689Skan tree at_stmt, struct loop *loop, 2002169689Skan bool use_overflow_semantics) 2003169689Skan{ 2004169689Skan struct nb_iter_bound *bound; 2005169689Skan tree delta, step_abs; 2006169689Skan tree unsigned_type, valid_niter; 2007169689Skan tree type = TREE_TYPE (step); 2008169689Skan 2009169689Skan /* FIXME: We really need something like 2010169689Skan http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. 2011169689Skan 2012169689Skan We used to test for the following situation that frequently appears 2013169689Skan during address arithmetics: 2014169689Skan 2015169689Skan D.1621_13 = (long unsigned intD.4) D.1620_12; 2016169689Skan D.1622_14 = D.1621_13 * 8; 2017169689Skan D.1623_15 = (doubleD.29 *) D.1622_14; 2018169689Skan 2019169689Skan And derived that the sequence corresponding to D_14 2020169689Skan can be proved to not wrap because it is used for computing a 2021169689Skan memory access; however, this is not really the case -- for example, 2022169689Skan if D_12 = (unsigned char) [254,+,1], then D_14 has values 2023169689Skan 2032, 2040, 0, 8, ..., but the code is still legal. */ 2024169689Skan 2025169689Skan if (chrec_contains_undetermined (base) 2026169689Skan || chrec_contains_undetermined (step) 2027169689Skan || TREE_CODE (step) != INTEGER_CST) 2028169689Skan return true; 2029169689Skan 2030169689Skan if (zero_p (step)) 2031169689Skan return false; 2032169689Skan 2033169689Skan /* If we can use the fact that signed and pointer arithmetics does not 2034169689Skan wrap, we are done. */ 2035169689Skan if (use_overflow_semantics && nowrap_type_p (type)) 2036169689Skan return false; 2037169689Skan 2038169689Skan /* Don't issue signed overflow warnings. */ 2039169689Skan fold_defer_overflow_warnings (); 2040169689Skan 2041169689Skan /* Otherwise, compute the number of iterations before we reach the 2042169689Skan bound of the type, and verify that the loop is exited before this 2043169689Skan occurs. */ 2044169689Skan unsigned_type = unsigned_type_for (type); 2045169689Skan base = fold_convert (unsigned_type, base); 2046169689Skan 2047169689Skan if (tree_int_cst_sign_bit (step)) 2048169689Skan { 2049169689Skan tree extreme = fold_convert (unsigned_type, 2050169689Skan lower_bound_in_type (type, type)); 2051169689Skan delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); 2052169689Skan step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, 2053169689Skan fold_convert (unsigned_type, step)); 2054169689Skan } 2055169689Skan else 2056169689Skan { 2057169689Skan tree extreme = fold_convert (unsigned_type, 2058169689Skan upper_bound_in_type (type, type)); 2059169689Skan delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); 2060169689Skan step_abs = fold_convert (unsigned_type, step); 2061169689Skan } 2062169689Skan 2063169689Skan valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); 2064169689Skan 2065169689Skan estimate_numbers_of_iterations_loop (loop); 2066169689Skan for (bound = loop->bounds; bound; bound = bound->next) 2067169689Skan { 2068169689Skan if (n_of_executions_at_most (at_stmt, bound, valid_niter)) 2069169689Skan { 2070169689Skan fold_undefer_and_ignore_overflow_warnings (); 2071169689Skan return false; 2072169689Skan } 2073169689Skan } 2074169689Skan 2075169689Skan fold_undefer_and_ignore_overflow_warnings (); 2076169689Skan 2077169689Skan /* At this point we still don't have a proof that the iv does not 2078169689Skan overflow: give up. */ 2079169689Skan return true; 2080169689Skan} 2081169689Skan 2082169689Skan/* Frees the information on upper bounds on numbers of iterations of LOOP. */ 2083169689Skan 2084169689Skanvoid 2085169689Skanfree_numbers_of_iterations_estimates_loop (struct loop *loop) 2086169689Skan{ 2087169689Skan struct nb_iter_bound *bound, *next; 2088169689Skan 2089169689Skan loop->nb_iterations = NULL; 2090169689Skan loop->estimated_nb_iterations = NULL; 2091169689Skan for (bound = loop->bounds; bound; bound = next) 2092169689Skan { 2093169689Skan next = bound->next; 2094169689Skan free (bound); 2095169689Skan } 2096169689Skan 2097169689Skan loop->bounds = NULL; 2098169689Skan} 2099169689Skan 2100169689Skan/* Frees the information on upper bounds on numbers of iterations of LOOPS. */ 2101169689Skan 2102169689Skanvoid 2103169689Skanfree_numbers_of_iterations_estimates (struct loops *loops) 2104169689Skan{ 2105169689Skan unsigned i; 2106169689Skan struct loop *loop; 2107169689Skan 2108169689Skan for (i = 1; i < loops->num; i++) 2109169689Skan { 2110169689Skan loop = loops->parray[i]; 2111169689Skan if (loop) 2112169689Skan free_numbers_of_iterations_estimates_loop (loop); 2113169689Skan } 2114169689Skan} 2115169689Skan 2116169689Skan/* Substitute value VAL for ssa name NAME inside expressions held 2117169689Skan at LOOP. */ 2118169689Skan 2119169689Skanvoid 2120169689Skansubstitute_in_loop_info (struct loop *loop, tree name, tree val) 2121169689Skan{ 2122169689Skan loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); 2123169689Skan loop->estimated_nb_iterations 2124169689Skan = simplify_replace_tree (loop->estimated_nb_iterations, name, val); 2125169689Skan} 2126