1169689Skan/* Chains of recurrences. 2169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* This file implements operations on chains of recurrences. Chains 23169689Skan of recurrences are used for modeling evolution functions of scalar 24169689Skan variables. 25169689Skan*/ 26169689Skan 27169689Skan#include "config.h" 28169689Skan#include "system.h" 29169689Skan#include "coretypes.h" 30169689Skan#include "tm.h" 31169689Skan#include "ggc.h" 32169689Skan#include "tree.h" 33169689Skan#include "real.h" 34169689Skan#include "diagnostic.h" 35169689Skan#include "cfgloop.h" 36169689Skan#include "tree-flow.h" 37169689Skan#include "tree-chrec.h" 38169689Skan#include "tree-pass.h" 39169689Skan#include "params.h" 40169689Skan#include "tree-scalar-evolution.h" 41169689Skan 42169689Skan 43169689Skan 44169689Skan/* Extended folder for chrecs. */ 45169689Skan 46169689Skan/* Determines whether CST is not a constant evolution. */ 47169689Skan 48169689Skanstatic inline bool 49169689Skanis_not_constant_evolution (tree cst) 50169689Skan{ 51169689Skan return (TREE_CODE (cst) == POLYNOMIAL_CHREC); 52169689Skan} 53169689Skan 54169689Skan/* Fold CODE for a polynomial function and a constant. */ 55169689Skan 56169689Skanstatic inline tree 57169689Skanchrec_fold_poly_cst (enum tree_code code, 58169689Skan tree type, 59169689Skan tree poly, 60169689Skan tree cst) 61169689Skan{ 62169689Skan gcc_assert (poly); 63169689Skan gcc_assert (cst); 64169689Skan gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC); 65169689Skan gcc_assert (!is_not_constant_evolution (cst)); 66169689Skan gcc_assert (type == chrec_type (poly)); 67169689Skan 68169689Skan switch (code) 69169689Skan { 70169689Skan case PLUS_EXPR: 71169689Skan return build_polynomial_chrec 72169689Skan (CHREC_VARIABLE (poly), 73169689Skan chrec_fold_plus (type, CHREC_LEFT (poly), cst), 74169689Skan CHREC_RIGHT (poly)); 75169689Skan 76169689Skan case MINUS_EXPR: 77169689Skan return build_polynomial_chrec 78169689Skan (CHREC_VARIABLE (poly), 79169689Skan chrec_fold_minus (type, CHREC_LEFT (poly), cst), 80169689Skan CHREC_RIGHT (poly)); 81169689Skan 82169689Skan case MULT_EXPR: 83169689Skan return build_polynomial_chrec 84169689Skan (CHREC_VARIABLE (poly), 85169689Skan chrec_fold_multiply (type, CHREC_LEFT (poly), cst), 86169689Skan chrec_fold_multiply (type, CHREC_RIGHT (poly), cst)); 87169689Skan 88169689Skan default: 89169689Skan return chrec_dont_know; 90169689Skan } 91169689Skan} 92169689Skan 93169689Skan/* Fold the addition of two polynomial functions. */ 94169689Skan 95169689Skanstatic inline tree 96169689Skanchrec_fold_plus_poly_poly (enum tree_code code, 97169689Skan tree type, 98169689Skan tree poly0, 99169689Skan tree poly1) 100169689Skan{ 101169689Skan tree left, right; 102169689Skan 103169689Skan gcc_assert (poly0); 104169689Skan gcc_assert (poly1); 105169689Skan gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 106169689Skan gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 107169689Skan gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 108169689Skan gcc_assert (type == chrec_type (poly0)); 109169689Skan 110169689Skan /* 111169689Skan {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, 112169689Skan {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, 113169689Skan {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ 114169689Skan if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) 115169689Skan { 116169689Skan if (code == PLUS_EXPR) 117169689Skan return build_polynomial_chrec 118169689Skan (CHREC_VARIABLE (poly1), 119169689Skan chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), 120169689Skan CHREC_RIGHT (poly1)); 121169689Skan else 122169689Skan return build_polynomial_chrec 123169689Skan (CHREC_VARIABLE (poly1), 124169689Skan chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), 125169689Skan chrec_fold_multiply (type, CHREC_RIGHT (poly1), 126169689Skan SCALAR_FLOAT_TYPE_P (type) 127169689Skan ? build_real (type, dconstm1) 128169689Skan : build_int_cst_type (type, -1))); 129169689Skan } 130169689Skan 131169689Skan if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1)) 132169689Skan { 133169689Skan if (code == PLUS_EXPR) 134169689Skan return build_polynomial_chrec 135169689Skan (CHREC_VARIABLE (poly0), 136169689Skan chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), 137169689Skan CHREC_RIGHT (poly0)); 138169689Skan else 139169689Skan return build_polynomial_chrec 140169689Skan (CHREC_VARIABLE (poly0), 141169689Skan chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), 142169689Skan CHREC_RIGHT (poly0)); 143169689Skan } 144169689Skan 145169689Skan if (code == PLUS_EXPR) 146169689Skan { 147169689Skan left = chrec_fold_plus 148169689Skan (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 149169689Skan right = chrec_fold_plus 150169689Skan (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 151169689Skan } 152169689Skan else 153169689Skan { 154169689Skan left = chrec_fold_minus 155169689Skan (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 156169689Skan right = chrec_fold_minus 157169689Skan (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 158169689Skan } 159169689Skan 160169689Skan if (chrec_zerop (right)) 161169689Skan return left; 162169689Skan else 163169689Skan return build_polynomial_chrec 164169689Skan (CHREC_VARIABLE (poly0), left, right); 165169689Skan} 166169689Skan 167169689Skan 168169689Skan 169169689Skan/* Fold the multiplication of two polynomial functions. */ 170169689Skan 171169689Skanstatic inline tree 172169689Skanchrec_fold_multiply_poly_poly (tree type, 173169689Skan tree poly0, 174169689Skan tree poly1) 175169689Skan{ 176169689Skan tree t0, t1, t2; 177169689Skan int var; 178169689Skan 179169689Skan gcc_assert (poly0); 180169689Skan gcc_assert (poly1); 181169689Skan gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 182169689Skan gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 183169689Skan gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 184169689Skan gcc_assert (type == chrec_type (poly0)); 185169689Skan 186169689Skan /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, 187169689Skan {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, 188169689Skan {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 189169689Skan if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1)) 190169689Skan /* poly0 is a constant wrt. poly1. */ 191169689Skan return build_polynomial_chrec 192169689Skan (CHREC_VARIABLE (poly1), 193169689Skan chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), 194169689Skan CHREC_RIGHT (poly1)); 195169689Skan 196169689Skan if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0)) 197169689Skan /* poly1 is a constant wrt. poly0. */ 198169689Skan return build_polynomial_chrec 199169689Skan (CHREC_VARIABLE (poly0), 200169689Skan chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), 201169689Skan CHREC_RIGHT (poly0)); 202169689Skan 203169689Skan /* poly0 and poly1 are two polynomials in the same variable, 204169689Skan {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 205169689Skan 206169689Skan /* "a*c". */ 207169689Skan t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 208169689Skan 209169689Skan /* "a*d + b*c + b*d". */ 210169689Skan t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); 211169689Skan t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, 212169689Skan CHREC_RIGHT (poly0), 213169689Skan CHREC_LEFT (poly1))); 214169689Skan t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, 215169689Skan CHREC_RIGHT (poly0), 216169689Skan CHREC_RIGHT (poly1))); 217169689Skan /* "2*b*d". */ 218169689Skan t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 219169689Skan t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type) 220169689Skan ? build_real (type, dconst2) 221169689Skan : build_int_cst (type, 2), t2); 222169689Skan 223169689Skan var = CHREC_VARIABLE (poly0); 224169689Skan return build_polynomial_chrec (var, t0, 225169689Skan build_polynomial_chrec (var, t1, t2)); 226169689Skan} 227169689Skan 228169689Skan/* When the operands are automatically_generated_chrec_p, the fold has 229169689Skan to respect the semantics of the operands. */ 230169689Skan 231169689Skanstatic inline tree 232169689Skanchrec_fold_automatically_generated_operands (tree op0, 233169689Skan tree op1) 234169689Skan{ 235169689Skan if (op0 == chrec_dont_know 236169689Skan || op1 == chrec_dont_know) 237169689Skan return chrec_dont_know; 238169689Skan 239169689Skan if (op0 == chrec_known 240169689Skan || op1 == chrec_known) 241169689Skan return chrec_known; 242169689Skan 243169689Skan if (op0 == chrec_not_analyzed_yet 244169689Skan || op1 == chrec_not_analyzed_yet) 245169689Skan return chrec_not_analyzed_yet; 246169689Skan 247169689Skan /* The default case produces a safe result. */ 248169689Skan return chrec_dont_know; 249169689Skan} 250169689Skan 251169689Skan/* Fold the addition of two chrecs. */ 252169689Skan 253169689Skanstatic tree 254169689Skanchrec_fold_plus_1 (enum tree_code code, tree type, 255169689Skan tree op0, tree op1) 256169689Skan{ 257169689Skan if (automatically_generated_chrec_p (op0) 258169689Skan || automatically_generated_chrec_p (op1)) 259169689Skan return chrec_fold_automatically_generated_operands (op0, op1); 260169689Skan 261169689Skan switch (TREE_CODE (op0)) 262169689Skan { 263169689Skan case POLYNOMIAL_CHREC: 264169689Skan switch (TREE_CODE (op1)) 265169689Skan { 266169689Skan case POLYNOMIAL_CHREC: 267169689Skan return chrec_fold_plus_poly_poly (code, type, op0, op1); 268169689Skan 269169689Skan default: 270169689Skan if (code == PLUS_EXPR) 271169689Skan return build_polynomial_chrec 272169689Skan (CHREC_VARIABLE (op0), 273169689Skan chrec_fold_plus (type, CHREC_LEFT (op0), op1), 274169689Skan CHREC_RIGHT (op0)); 275169689Skan else 276169689Skan return build_polynomial_chrec 277169689Skan (CHREC_VARIABLE (op0), 278169689Skan chrec_fold_minus (type, CHREC_LEFT (op0), op1), 279169689Skan CHREC_RIGHT (op0)); 280169689Skan } 281169689Skan 282169689Skan default: 283169689Skan switch (TREE_CODE (op1)) 284169689Skan { 285169689Skan case POLYNOMIAL_CHREC: 286169689Skan if (code == PLUS_EXPR) 287169689Skan return build_polynomial_chrec 288169689Skan (CHREC_VARIABLE (op1), 289169689Skan chrec_fold_plus (type, op0, CHREC_LEFT (op1)), 290169689Skan CHREC_RIGHT (op1)); 291169689Skan else 292169689Skan return build_polynomial_chrec 293169689Skan (CHREC_VARIABLE (op1), 294169689Skan chrec_fold_minus (type, op0, CHREC_LEFT (op1)), 295169689Skan chrec_fold_multiply (type, CHREC_RIGHT (op1), 296169689Skan SCALAR_FLOAT_TYPE_P (type) 297169689Skan ? build_real (type, dconstm1) 298169689Skan : build_int_cst_type (type, -1))); 299169689Skan 300169689Skan default: 301169689Skan { 302169689Skan int size = 0; 303169689Skan if ((tree_contains_chrecs (op0, &size) 304169689Skan || tree_contains_chrecs (op1, &size)) 305169689Skan && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 306169689Skan return build2 (code, type, op0, op1); 307169689Skan else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 308169689Skan return fold_build2 (code, type, 309169689Skan fold_convert (type, op0), 310169689Skan fold_convert (type, op1)); 311169689Skan else 312169689Skan return chrec_dont_know; 313169689Skan } 314169689Skan } 315169689Skan } 316169689Skan} 317169689Skan 318169689Skan/* Fold the addition of two chrecs. */ 319169689Skan 320169689Skantree 321169689Skanchrec_fold_plus (tree type, 322169689Skan tree op0, 323169689Skan tree op1) 324169689Skan{ 325169689Skan if (automatically_generated_chrec_p (op0) 326169689Skan || automatically_generated_chrec_p (op1)) 327169689Skan return chrec_fold_automatically_generated_operands (op0, op1); 328169689Skan 329169689Skan if (integer_zerop (op0)) 330169689Skan return op1; 331169689Skan if (integer_zerop (op1)) 332169689Skan return op0; 333169689Skan 334169689Skan return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1); 335169689Skan} 336169689Skan 337169689Skan/* Fold the subtraction of two chrecs. */ 338169689Skan 339169689Skantree 340169689Skanchrec_fold_minus (tree type, 341169689Skan tree op0, 342169689Skan tree op1) 343169689Skan{ 344169689Skan if (automatically_generated_chrec_p (op0) 345169689Skan || automatically_generated_chrec_p (op1)) 346169689Skan return chrec_fold_automatically_generated_operands (op0, op1); 347169689Skan 348169689Skan if (integer_zerop (op1)) 349169689Skan return op0; 350169689Skan 351169689Skan return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); 352169689Skan} 353169689Skan 354169689Skan/* Fold the multiplication of two chrecs. */ 355169689Skan 356169689Skantree 357169689Skanchrec_fold_multiply (tree type, 358169689Skan tree op0, 359169689Skan tree op1) 360169689Skan{ 361169689Skan if (automatically_generated_chrec_p (op0) 362169689Skan || automatically_generated_chrec_p (op1)) 363169689Skan return chrec_fold_automatically_generated_operands (op0, op1); 364169689Skan 365169689Skan switch (TREE_CODE (op0)) 366169689Skan { 367169689Skan case POLYNOMIAL_CHREC: 368169689Skan switch (TREE_CODE (op1)) 369169689Skan { 370169689Skan case POLYNOMIAL_CHREC: 371169689Skan return chrec_fold_multiply_poly_poly (type, op0, op1); 372169689Skan 373169689Skan default: 374169689Skan if (integer_onep (op1)) 375169689Skan return op0; 376169689Skan if (integer_zerop (op1)) 377169689Skan return build_int_cst (type, 0); 378169689Skan 379169689Skan return build_polynomial_chrec 380169689Skan (CHREC_VARIABLE (op0), 381169689Skan chrec_fold_multiply (type, CHREC_LEFT (op0), op1), 382169689Skan chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); 383169689Skan } 384169689Skan 385169689Skan default: 386169689Skan if (integer_onep (op0)) 387169689Skan return op1; 388169689Skan 389169689Skan if (integer_zerop (op0)) 390169689Skan return build_int_cst (type, 0); 391169689Skan 392169689Skan switch (TREE_CODE (op1)) 393169689Skan { 394169689Skan case POLYNOMIAL_CHREC: 395169689Skan return build_polynomial_chrec 396169689Skan (CHREC_VARIABLE (op1), 397169689Skan chrec_fold_multiply (type, CHREC_LEFT (op1), op0), 398169689Skan chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); 399169689Skan 400169689Skan default: 401169689Skan if (integer_onep (op1)) 402169689Skan return op0; 403169689Skan if (integer_zerop (op1)) 404169689Skan return build_int_cst (type, 0); 405169689Skan return fold_build2 (MULT_EXPR, type, op0, op1); 406169689Skan } 407169689Skan } 408169689Skan} 409169689Skan 410169689Skan 411169689Skan 412169689Skan/* Operations. */ 413169689Skan 414169689Skan/* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate 415169689Skan calculation overflows, otherwise return C(n,k) with type TYPE. */ 416169689Skan 417169689Skanstatic tree 418169689Skantree_fold_binomial (tree type, tree n, unsigned int k) 419169689Skan{ 420169689Skan unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; 421169689Skan HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum; 422169689Skan unsigned int i; 423169689Skan tree res; 424169689Skan 425169689Skan /* Handle the most frequent cases. */ 426169689Skan if (k == 0) 427169689Skan return build_int_cst (type, 1); 428169689Skan if (k == 1) 429169689Skan return fold_convert (type, n); 430169689Skan 431169689Skan /* Check that k <= n. */ 432169689Skan if (TREE_INT_CST_HIGH (n) == 0 433169689Skan && TREE_INT_CST_LOW (n) < k) 434169689Skan return NULL_TREE; 435169689Skan 436169689Skan /* Numerator = n. */ 437169689Skan lnum = TREE_INT_CST_LOW (n); 438169689Skan hnum = TREE_INT_CST_HIGH (n); 439169689Skan 440169689Skan /* Denominator = 2. */ 441169689Skan ldenom = 2; 442169689Skan hdenom = 0; 443169689Skan 444169689Skan /* Index = Numerator-1. */ 445169689Skan if (lnum == 0) 446169689Skan { 447169689Skan hidx = hnum - 1; 448169689Skan lidx = ~ (unsigned HOST_WIDE_INT) 0; 449169689Skan } 450169689Skan else 451169689Skan { 452169689Skan hidx = hnum; 453169689Skan lidx = lnum - 1; 454169689Skan } 455169689Skan 456169689Skan /* Numerator = Numerator*Index = n*(n-1). */ 457169689Skan if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 458169689Skan return NULL_TREE; 459169689Skan 460169689Skan for (i = 3; i <= k; i++) 461169689Skan { 462169689Skan /* Index--. */ 463169689Skan if (lidx == 0) 464169689Skan { 465169689Skan hidx--; 466169689Skan lidx = ~ (unsigned HOST_WIDE_INT) 0; 467169689Skan } 468169689Skan else 469169689Skan lidx--; 470169689Skan 471169689Skan /* Numerator *= Index. */ 472169689Skan if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) 473169689Skan return NULL_TREE; 474169689Skan 475169689Skan /* Denominator *= i. */ 476169689Skan mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom); 477169689Skan } 478169689Skan 479169689Skan /* Result = Numerator / Denominator. */ 480169689Skan div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom, 481169689Skan &lres, &hres, &ldum, &hdum); 482169689Skan 483169689Skan res = build_int_cst_wide (type, lres, hres); 484169689Skan return int_fits_type_p (res, type) ? res : NULL_TREE; 485169689Skan} 486169689Skan 487169689Skan/* Helper function. Use the Newton's interpolating formula for 488169689Skan evaluating the value of the evolution function. */ 489169689Skan 490169689Skanstatic tree 491169689Skanchrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) 492169689Skan{ 493169689Skan tree arg0, arg1, binomial_n_k; 494169689Skan tree type = TREE_TYPE (chrec); 495169689Skan 496169689Skan while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 497169689Skan && CHREC_VARIABLE (chrec) > var) 498169689Skan chrec = CHREC_LEFT (chrec); 499169689Skan 500169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 501169689Skan && CHREC_VARIABLE (chrec) == var) 502169689Skan { 503169689Skan arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); 504169689Skan if (arg0 == chrec_dont_know) 505169689Skan return chrec_dont_know; 506169689Skan binomial_n_k = tree_fold_binomial (type, n, k); 507169689Skan if (!binomial_n_k) 508169689Skan return chrec_dont_know; 509169689Skan arg1 = fold_build2 (MULT_EXPR, type, 510169689Skan CHREC_LEFT (chrec), binomial_n_k); 511169689Skan return chrec_fold_plus (type, arg0, arg1); 512169689Skan } 513169689Skan 514169689Skan binomial_n_k = tree_fold_binomial (type, n, k); 515169689Skan if (!binomial_n_k) 516169689Skan return chrec_dont_know; 517169689Skan 518169689Skan return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); 519169689Skan} 520169689Skan 521169689Skan/* Evaluates "CHREC (X)" when the varying variable is VAR. 522169689Skan Example: Given the following parameters, 523169689Skan 524169689Skan var = 1 525169689Skan chrec = {3, +, 4}_1 526169689Skan x = 10 527169689Skan 528169689Skan The result is given by the Newton's interpolating formula: 529169689Skan 3 * \binom{10}{0} + 4 * \binom{10}{1}. 530169689Skan*/ 531169689Skan 532169689Skantree 533169689Skanchrec_apply (unsigned var, 534169689Skan tree chrec, 535169689Skan tree x) 536169689Skan{ 537169689Skan tree type = chrec_type (chrec); 538169689Skan tree res = chrec_dont_know; 539169689Skan 540169689Skan if (automatically_generated_chrec_p (chrec) 541169689Skan || automatically_generated_chrec_p (x) 542169689Skan 543169689Skan /* When the symbols are defined in an outer loop, it is possible 544169689Skan to symbolically compute the apply, since the symbols are 545169689Skan constants with respect to the varying loop. */ 546169689Skan || chrec_contains_symbols_defined_in_loop (chrec, var)) 547169689Skan return chrec_dont_know; 548169689Skan 549169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 550169689Skan fprintf (dump_file, "(chrec_apply \n"); 551169689Skan 552169689Skan if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) 553169689Skan x = build_real_from_int_cst (type, x); 554169689Skan 555169689Skan if (evolution_function_is_affine_p (chrec)) 556169689Skan { 557169689Skan /* "{a, +, b} (x)" -> "a + b*x". */ 558169689Skan x = chrec_convert (type, x, NULL_TREE); 559169689Skan res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); 560169689Skan if (!integer_zerop (CHREC_LEFT (chrec))) 561169689Skan res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); 562169689Skan } 563169689Skan 564169689Skan else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 565169689Skan res = chrec; 566169689Skan 567169689Skan else if (TREE_CODE (x) == INTEGER_CST 568169689Skan && tree_int_cst_sgn (x) == 1) 569169689Skan /* testsuite/.../ssa-chrec-38.c. */ 570169689Skan res = chrec_evaluate (var, chrec, x, 0); 571169689Skan else 572169689Skan res = chrec_dont_know; 573169689Skan 574169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 575169689Skan { 576169689Skan fprintf (dump_file, " (varying_loop = %d\n", var); 577169689Skan fprintf (dump_file, ")\n (chrec = "); 578169689Skan print_generic_expr (dump_file, chrec, 0); 579169689Skan fprintf (dump_file, ")\n (x = "); 580169689Skan print_generic_expr (dump_file, x, 0); 581169689Skan fprintf (dump_file, ")\n (res = "); 582169689Skan print_generic_expr (dump_file, res, 0); 583169689Skan fprintf (dump_file, "))\n"); 584169689Skan } 585169689Skan 586169689Skan return res; 587169689Skan} 588169689Skan 589169689Skan/* Replaces the initial condition in CHREC with INIT_COND. */ 590169689Skan 591169689Skantree 592169689Skanchrec_replace_initial_condition (tree chrec, 593169689Skan tree init_cond) 594169689Skan{ 595169689Skan if (automatically_generated_chrec_p (chrec)) 596169689Skan return chrec; 597169689Skan 598169689Skan gcc_assert (chrec_type (chrec) == chrec_type (init_cond)); 599169689Skan 600169689Skan switch (TREE_CODE (chrec)) 601169689Skan { 602169689Skan case POLYNOMIAL_CHREC: 603169689Skan return build_polynomial_chrec 604169689Skan (CHREC_VARIABLE (chrec), 605169689Skan chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), 606169689Skan CHREC_RIGHT (chrec)); 607169689Skan 608169689Skan default: 609169689Skan return init_cond; 610169689Skan } 611169689Skan} 612169689Skan 613169689Skan/* Returns the initial condition of a given CHREC. */ 614169689Skan 615169689Skantree 616169689Skaninitial_condition (tree chrec) 617169689Skan{ 618169689Skan if (automatically_generated_chrec_p (chrec)) 619169689Skan return chrec; 620169689Skan 621169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 622169689Skan return initial_condition (CHREC_LEFT (chrec)); 623169689Skan else 624169689Skan return chrec; 625169689Skan} 626169689Skan 627169689Skan/* Returns a univariate function that represents the evolution in 628169689Skan LOOP_NUM. Mask the evolution of any other loop. */ 629169689Skan 630169689Skantree 631169689Skanhide_evolution_in_other_loops_than_loop (tree chrec, 632169689Skan unsigned loop_num) 633169689Skan{ 634169689Skan if (automatically_generated_chrec_p (chrec)) 635169689Skan return chrec; 636169689Skan 637169689Skan switch (TREE_CODE (chrec)) 638169689Skan { 639169689Skan case POLYNOMIAL_CHREC: 640169689Skan if (CHREC_VARIABLE (chrec) == loop_num) 641169689Skan return build_polynomial_chrec 642169689Skan (loop_num, 643169689Skan hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 644169689Skan loop_num), 645169689Skan CHREC_RIGHT (chrec)); 646169689Skan 647169689Skan else if (CHREC_VARIABLE (chrec) < loop_num) 648169689Skan /* There is no evolution in this loop. */ 649169689Skan return initial_condition (chrec); 650169689Skan 651169689Skan else 652169689Skan return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 653169689Skan loop_num); 654169689Skan 655169689Skan default: 656169689Skan return chrec; 657169689Skan } 658169689Skan} 659169689Skan 660169689Skan/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is 661169689Skan true, otherwise returns the initial condition in LOOP_NUM. */ 662169689Skan 663169689Skanstatic tree 664169689Skanchrec_component_in_loop_num (tree chrec, 665169689Skan unsigned loop_num, 666169689Skan bool right) 667169689Skan{ 668169689Skan tree component; 669169689Skan 670169689Skan if (automatically_generated_chrec_p (chrec)) 671169689Skan return chrec; 672169689Skan 673169689Skan switch (TREE_CODE (chrec)) 674169689Skan { 675169689Skan case POLYNOMIAL_CHREC: 676169689Skan if (CHREC_VARIABLE (chrec) == loop_num) 677169689Skan { 678169689Skan if (right) 679169689Skan component = CHREC_RIGHT (chrec); 680169689Skan else 681169689Skan component = CHREC_LEFT (chrec); 682169689Skan 683169689Skan if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC 684169689Skan || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) 685169689Skan return component; 686169689Skan 687169689Skan else 688169689Skan return build_polynomial_chrec 689169689Skan (loop_num, 690169689Skan chrec_component_in_loop_num (CHREC_LEFT (chrec), 691169689Skan loop_num, 692169689Skan right), 693169689Skan component); 694169689Skan } 695169689Skan 696169689Skan else if (CHREC_VARIABLE (chrec) < loop_num) 697169689Skan /* There is no evolution part in this loop. */ 698169689Skan return NULL_TREE; 699169689Skan 700169689Skan else 701169689Skan return chrec_component_in_loop_num (CHREC_LEFT (chrec), 702169689Skan loop_num, 703169689Skan right); 704169689Skan 705169689Skan default: 706169689Skan if (right) 707169689Skan return NULL_TREE; 708169689Skan else 709169689Skan return chrec; 710169689Skan } 711169689Skan} 712169689Skan 713169689Skan/* Returns the evolution part in LOOP_NUM. Example: the call 714169689Skan evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 715169689Skan {1, +, 2}_1 */ 716169689Skan 717169689Skantree 718169689Skanevolution_part_in_loop_num (tree chrec, 719169689Skan unsigned loop_num) 720169689Skan{ 721169689Skan return chrec_component_in_loop_num (chrec, loop_num, true); 722169689Skan} 723169689Skan 724169689Skan/* Returns the initial condition in LOOP_NUM. Example: the call 725169689Skan initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 726169689Skan {0, +, 1}_1 */ 727169689Skan 728169689Skantree 729169689Skaninitial_condition_in_loop_num (tree chrec, 730169689Skan unsigned loop_num) 731169689Skan{ 732169689Skan return chrec_component_in_loop_num (chrec, loop_num, false); 733169689Skan} 734169689Skan 735169689Skan/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. 736169689Skan This function is essentially used for setting the evolution to 737169689Skan chrec_dont_know, for example after having determined that it is 738169689Skan impossible to say how many times a loop will execute. */ 739169689Skan 740169689Skantree 741169689Skanreset_evolution_in_loop (unsigned loop_num, 742169689Skan tree chrec, 743169689Skan tree new_evol) 744169689Skan{ 745169689Skan gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); 746169689Skan 747169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 748169689Skan && CHREC_VARIABLE (chrec) > loop_num) 749169689Skan { 750169689Skan tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), 751169689Skan new_evol); 752169689Skan tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), 753169689Skan new_evol); 754169689Skan return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 755169689Skan build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), 756169689Skan left, right); 757169689Skan } 758169689Skan 759169689Skan while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 760169689Skan && CHREC_VARIABLE (chrec) == loop_num) 761169689Skan chrec = CHREC_LEFT (chrec); 762169689Skan 763169689Skan return build_polynomial_chrec (loop_num, chrec, new_evol); 764169689Skan} 765169689Skan 766169689Skan/* Merges two evolution functions that were found by following two 767169689Skan alternate paths of a conditional expression. */ 768169689Skan 769169689Skantree 770169689Skanchrec_merge (tree chrec1, 771169689Skan tree chrec2) 772169689Skan{ 773169689Skan if (chrec1 == chrec_dont_know 774169689Skan || chrec2 == chrec_dont_know) 775169689Skan return chrec_dont_know; 776169689Skan 777169689Skan if (chrec1 == chrec_known 778169689Skan || chrec2 == chrec_known) 779169689Skan return chrec_known; 780169689Skan 781169689Skan if (chrec1 == chrec_not_analyzed_yet) 782169689Skan return chrec2; 783169689Skan if (chrec2 == chrec_not_analyzed_yet) 784169689Skan return chrec1; 785169689Skan 786169689Skan if (eq_evolutions_p (chrec1, chrec2)) 787169689Skan return chrec1; 788169689Skan 789169689Skan return chrec_dont_know; 790169689Skan} 791169689Skan 792169689Skan 793169689Skan 794169689Skan/* Observers. */ 795169689Skan 796169689Skan/* Helper function for is_multivariate_chrec. */ 797169689Skan 798169689Skanstatic bool 799169689Skanis_multivariate_chrec_rec (tree chrec, unsigned int rec_var) 800169689Skan{ 801169689Skan if (chrec == NULL_TREE) 802169689Skan return false; 803169689Skan 804169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 805169689Skan { 806169689Skan if (CHREC_VARIABLE (chrec) != rec_var) 807169689Skan return true; 808169689Skan else 809169689Skan return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) 810169689Skan || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); 811169689Skan } 812169689Skan else 813169689Skan return false; 814169689Skan} 815169689Skan 816169689Skan/* Determine whether the given chrec is multivariate or not. */ 817169689Skan 818169689Skanbool 819169689Skanis_multivariate_chrec (tree chrec) 820169689Skan{ 821169689Skan if (chrec == NULL_TREE) 822169689Skan return false; 823169689Skan 824169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 825169689Skan return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), 826169689Skan CHREC_VARIABLE (chrec)) 827169689Skan || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), 828169689Skan CHREC_VARIABLE (chrec))); 829169689Skan else 830169689Skan return false; 831169689Skan} 832169689Skan 833169689Skan/* Determines whether the chrec contains symbolic names or not. */ 834169689Skan 835169689Skanbool 836169689Skanchrec_contains_symbols (tree chrec) 837169689Skan{ 838169689Skan if (chrec == NULL_TREE) 839169689Skan return false; 840169689Skan 841169689Skan if (TREE_CODE (chrec) == SSA_NAME 842169689Skan || TREE_CODE (chrec) == VAR_DECL 843169689Skan || TREE_CODE (chrec) == PARM_DECL 844169689Skan || TREE_CODE (chrec) == FUNCTION_DECL 845169689Skan || TREE_CODE (chrec) == LABEL_DECL 846169689Skan || TREE_CODE (chrec) == RESULT_DECL 847169689Skan || TREE_CODE (chrec) == FIELD_DECL) 848169689Skan return true; 849169689Skan 850169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 851169689Skan { 852169689Skan case 3: 853169689Skan if (chrec_contains_symbols (TREE_OPERAND (chrec, 2))) 854169689Skan return true; 855169689Skan 856169689Skan case 2: 857169689Skan if (chrec_contains_symbols (TREE_OPERAND (chrec, 1))) 858169689Skan return true; 859169689Skan 860169689Skan case 1: 861169689Skan if (chrec_contains_symbols (TREE_OPERAND (chrec, 0))) 862169689Skan return true; 863169689Skan 864169689Skan default: 865169689Skan return false; 866169689Skan } 867169689Skan} 868169689Skan 869169689Skan/* Determines whether the chrec contains undetermined coefficients. */ 870169689Skan 871169689Skanbool 872169689Skanchrec_contains_undetermined (tree chrec) 873169689Skan{ 874169689Skan if (chrec == chrec_dont_know 875169689Skan || chrec == chrec_not_analyzed_yet 876169689Skan || chrec == NULL_TREE) 877169689Skan return true; 878169689Skan 879169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 880169689Skan { 881169689Skan case 3: 882169689Skan if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2))) 883169689Skan return true; 884169689Skan 885169689Skan case 2: 886169689Skan if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1))) 887169689Skan return true; 888169689Skan 889169689Skan case 1: 890169689Skan if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0))) 891169689Skan return true; 892169689Skan 893169689Skan default: 894169689Skan return false; 895169689Skan } 896169689Skan} 897169689Skan 898169689Skan/* Determines whether the tree EXPR contains chrecs, and increment 899169689Skan SIZE if it is not a NULL pointer by an estimation of the depth of 900169689Skan the tree. */ 901169689Skan 902169689Skanbool 903169689Skantree_contains_chrecs (tree expr, int *size) 904169689Skan{ 905169689Skan if (expr == NULL_TREE) 906169689Skan return false; 907169689Skan 908169689Skan if (size) 909169689Skan (*size)++; 910169689Skan 911169689Skan if (tree_is_chrec (expr)) 912169689Skan return true; 913169689Skan 914169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (expr))) 915169689Skan { 916169689Skan case 3: 917169689Skan if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size)) 918169689Skan return true; 919169689Skan 920169689Skan case 2: 921169689Skan if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size)) 922169689Skan return true; 923169689Skan 924169689Skan case 1: 925169689Skan if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size)) 926169689Skan return true; 927169689Skan 928169689Skan default: 929169689Skan return false; 930169689Skan } 931169689Skan} 932169689Skan 933169689Skan/* Recursive helper function. */ 934169689Skan 935169689Skanstatic bool 936169689Skanevolution_function_is_invariant_rec_p (tree chrec, int loopnum) 937169689Skan{ 938169689Skan if (evolution_function_is_constant_p (chrec)) 939169689Skan return true; 940169689Skan 941169689Skan if (TREE_CODE (chrec) == SSA_NAME 942169689Skan && expr_invariant_in_loop_p (current_loops->parray[loopnum], 943169689Skan chrec)) 944169689Skan return true; 945169689Skan 946169689Skan if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 947169689Skan { 948169689Skan if (CHREC_VARIABLE (chrec) == (unsigned) loopnum 949169689Skan || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), 950169689Skan loopnum) 951169689Skan || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), 952169689Skan loopnum)) 953169689Skan return false; 954169689Skan return true; 955169689Skan } 956169689Skan 957169689Skan switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) 958169689Skan { 959169689Skan case 2: 960169689Skan if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), 961169689Skan loopnum)) 962169689Skan return false; 963169689Skan 964169689Skan case 1: 965169689Skan if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), 966169689Skan loopnum)) 967169689Skan return false; 968169689Skan return true; 969169689Skan 970169689Skan default: 971169689Skan return false; 972169689Skan } 973169689Skan 974169689Skan return false; 975169689Skan} 976169689Skan 977169689Skan/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ 978169689Skan 979169689Skanbool 980169689Skanevolution_function_is_invariant_p (tree chrec, int loopnum) 981169689Skan{ 982169689Skan if (evolution_function_is_constant_p (chrec)) 983169689Skan return true; 984169689Skan 985169689Skan if (current_loops != NULL) 986169689Skan return evolution_function_is_invariant_rec_p (chrec, loopnum); 987169689Skan 988169689Skan return false; 989169689Skan} 990169689Skan 991169689Skan/* Determine whether the given tree is an affine multivariate 992169689Skan evolution. */ 993169689Skan 994169689Skanbool 995169689Skanevolution_function_is_affine_multivariate_p (tree chrec) 996169689Skan{ 997169689Skan if (chrec == NULL_TREE) 998169689Skan return false; 999169689Skan 1000169689Skan switch (TREE_CODE (chrec)) 1001169689Skan { 1002169689Skan case POLYNOMIAL_CHREC: 1003169689Skan if (evolution_function_is_constant_p (CHREC_LEFT (chrec))) 1004169689Skan { 1005169689Skan if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))) 1006169689Skan return true; 1007169689Skan else 1008169689Skan { 1009169689Skan if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC 1010169689Skan && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 1011169689Skan != CHREC_VARIABLE (chrec) 1012169689Skan && evolution_function_is_affine_multivariate_p 1013169689Skan (CHREC_RIGHT (chrec))) 1014169689Skan return true; 1015169689Skan else 1016169689Skan return false; 1017169689Skan } 1018169689Skan } 1019169689Skan else 1020169689Skan { 1021169689Skan if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)) 1022169689Skan && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC 1023169689Skan && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) 1024169689Skan && evolution_function_is_affine_multivariate_p 1025169689Skan (CHREC_LEFT (chrec))) 1026169689Skan return true; 1027169689Skan else 1028169689Skan return false; 1029169689Skan } 1030169689Skan 1031169689Skan default: 1032169689Skan return false; 1033169689Skan } 1034169689Skan} 1035169689Skan 1036169689Skan/* Determine whether the given tree is a function in zero or one 1037169689Skan variables. */ 1038169689Skan 1039169689Skanbool 1040169689Skanevolution_function_is_univariate_p (tree chrec) 1041169689Skan{ 1042169689Skan if (chrec == NULL_TREE) 1043169689Skan return true; 1044169689Skan 1045169689Skan switch (TREE_CODE (chrec)) 1046169689Skan { 1047169689Skan case POLYNOMIAL_CHREC: 1048169689Skan switch (TREE_CODE (CHREC_LEFT (chrec))) 1049169689Skan { 1050169689Skan case POLYNOMIAL_CHREC: 1051169689Skan if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec))) 1052169689Skan return false; 1053169689Skan if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) 1054169689Skan return false; 1055169689Skan break; 1056169689Skan 1057169689Skan default: 1058169689Skan break; 1059169689Skan } 1060169689Skan 1061169689Skan switch (TREE_CODE (CHREC_RIGHT (chrec))) 1062169689Skan { 1063169689Skan case POLYNOMIAL_CHREC: 1064169689Skan if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec))) 1065169689Skan return false; 1066169689Skan if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) 1067169689Skan return false; 1068169689Skan break; 1069169689Skan 1070169689Skan default: 1071169689Skan break; 1072169689Skan } 1073169689Skan 1074169689Skan default: 1075169689Skan return true; 1076169689Skan } 1077169689Skan} 1078169689Skan 1079169689Skan/* Returns the number of variables of CHREC. Example: the call 1080169689Skan nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ 1081169689Skan 1082169689Skanunsigned 1083169689Skannb_vars_in_chrec (tree chrec) 1084169689Skan{ 1085169689Skan if (chrec == NULL_TREE) 1086169689Skan return 0; 1087169689Skan 1088169689Skan switch (TREE_CODE (chrec)) 1089169689Skan { 1090169689Skan case POLYNOMIAL_CHREC: 1091169689Skan return 1 + nb_vars_in_chrec 1092169689Skan (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); 1093169689Skan 1094169689Skan default: 1095169689Skan return 0; 1096169689Skan } 1097169689Skan} 1098169689Skan 1099169689Skan/* Returns true if TYPE is a type in that we cannot directly perform 1100169689Skan arithmetics, even though it is a scalar type. */ 1101169689Skan 1102169689Skanstatic bool 1103169689Skanavoid_arithmetics_in_type_p (tree type) 1104169689Skan{ 1105169689Skan /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed 1106169689Skan in the subtype, but a base type must be used, and the result then can 1107169689Skan be casted to the subtype. */ 1108169689Skan if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE) 1109169689Skan return true; 1110169689Skan 1111169689Skan return false; 1112169689Skan} 1113169689Skan 1114169689Skanstatic tree chrec_convert_1 (tree, tree, tree, bool); 1115169689Skan 1116169689Skan/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv 1117169689Skan the scev corresponds to. AT_STMT is the statement at that the scev is 1118169689Skan evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume that 1119169689Skan the rules for overflow of the given language apply (e.g., that signed 1120169689Skan arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1121169689Skan tests, but also to enforce that the result follows them. Returns true if the 1122169689Skan conversion succeeded, false otherwise. */ 1123169689Skan 1124169689Skanbool 1125169689Skanconvert_affine_scev (struct loop *loop, tree type, 1126169689Skan tree *base, tree *step, tree at_stmt, 1127169689Skan bool use_overflow_semantics) 1128169689Skan{ 1129169689Skan tree ct = TREE_TYPE (*step); 1130169689Skan bool enforce_overflow_semantics; 1131169689Skan bool must_check_src_overflow, must_check_rslt_overflow; 1132169689Skan tree new_base, new_step; 1133169689Skan 1134169689Skan /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */ 1135169689Skan if (avoid_arithmetics_in_type_p (type)) 1136169689Skan return false; 1137169689Skan 1138169689Skan /* In general, 1139169689Skan (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, 1140169689Skan but we must check some assumptions. 1141169689Skan 1142169689Skan 1) If [BASE, +, STEP] wraps, the equation is not valid when precision 1143169689Skan of CT is smaller than the precision of TYPE. For example, when we 1144169689Skan cast unsigned char [254, +, 1] to unsigned, the values on left side 1145169689Skan are 254, 255, 0, 1, ..., but those on the right side are 1146169689Skan 254, 255, 256, 257, ... 1147169689Skan 2) In case that we must also preserve the fact that signed ivs do not 1148169689Skan overflow, we must additionally check that the new iv does not wrap. 1149169689Skan For example, unsigned char [125, +, 1] casted to signed char could 1150169689Skan become a wrapping variable with values 125, 126, 127, -128, -127, ..., 1151169689Skan which would confuse optimizers that assume that this does not 1152169689Skan happen. */ 1153169689Skan must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type); 1154169689Skan 1155169689Skan enforce_overflow_semantics = (use_overflow_semantics 1156169689Skan && nowrap_type_p (type)); 1157169689Skan if (enforce_overflow_semantics) 1158169689Skan { 1159169689Skan /* We can avoid checking whether the result overflows in the following 1160169689Skan cases: 1161169689Skan 1162169689Skan -- must_check_src_overflow is true, and the range of TYPE is superset 1163169689Skan of the range of CT -- i.e., in all cases except if CT signed and 1164169689Skan TYPE unsigned. 1165169689Skan -- both CT and TYPE have the same precision and signedness, and we 1166169689Skan verify instead that the source does not overflow (this may be 1167169689Skan easier than verifying it for the result, as we may use the 1168169689Skan information about the semantics of overflow in CT). */ 1169169689Skan if (must_check_src_overflow) 1170169689Skan { 1171169689Skan if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct)) 1172169689Skan must_check_rslt_overflow = true; 1173169689Skan else 1174169689Skan must_check_rslt_overflow = false; 1175169689Skan } 1176169689Skan else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type) 1177169689Skan && TYPE_PRECISION (ct) == TYPE_PRECISION (type)) 1178169689Skan { 1179169689Skan must_check_rslt_overflow = false; 1180169689Skan must_check_src_overflow = true; 1181169689Skan } 1182169689Skan else 1183169689Skan must_check_rslt_overflow = true; 1184169689Skan } 1185169689Skan else 1186169689Skan must_check_rslt_overflow = false; 1187169689Skan 1188169689Skan if (must_check_src_overflow 1189169689Skan && scev_probably_wraps_p (*base, *step, at_stmt, loop, 1190169689Skan use_overflow_semantics)) 1191169689Skan return false; 1192169689Skan 1193169689Skan new_base = chrec_convert_1 (type, *base, at_stmt, 1194169689Skan use_overflow_semantics); 1195169689Skan /* The step must be sign extended, regardless of the signedness 1196169689Skan of CT and TYPE. This only needs to be handled specially when 1197169689Skan CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] 1198169689Skan (with values 100, 99, 98, ...) from becoming signed or unsigned 1199169689Skan [100, +, 255] with values 100, 355, ...; the sign-extension is 1200169689Skan performed by default when CT is signed. */ 1201169689Skan new_step = *step; 1202169689Skan if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) 1203169689Skan new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt, 1204169689Skan use_overflow_semantics); 1205169689Skan new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics); 1206169689Skan 1207169689Skan if (automatically_generated_chrec_p (new_base) 1208169689Skan || automatically_generated_chrec_p (new_step)) 1209169689Skan return false; 1210169689Skan 1211169689Skan if (must_check_rslt_overflow 1212169689Skan /* Note that in this case we cannot use the fact that signed variables 1213169689Skan do not overflow, as this is what we are verifying for the new iv. */ 1214169689Skan && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false)) 1215169689Skan return false; 1216169689Skan 1217169689Skan *base = new_base; 1218169689Skan *step = new_step; 1219169689Skan return true; 1220169689Skan} 1221169689Skan 1222169689Skan 1223169689Skan/* Convert CHREC to TYPE. When the analyzer knows the context in 1224169689Skan which the CHREC is built, it sets AT_STMT to the statement that 1225169689Skan contains the definition of the analyzed variable, otherwise the 1226169689Skan conversion is less accurate: the information is used for 1227169689Skan determining a more accurate estimation of the number of iterations. 1228169689Skan By default AT_STMT could be safely set to NULL_TREE. 1229169689Skan 1230169689Skan The following rule is always true: TREE_TYPE (chrec) == 1231169689Skan TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). 1232169689Skan An example of what could happen when adding two chrecs and the type 1233169689Skan of the CHREC_RIGHT is different than CHREC_LEFT is: 1234169689Skan 1235169689Skan {(uint) 0, +, (uchar) 10} + 1236169689Skan {(uint) 0, +, (uchar) 250} 1237169689Skan 1238169689Skan that would produce a wrong result if CHREC_RIGHT is not (uint): 1239169689Skan 1240169689Skan {(uint) 0, +, (uchar) 4} 1241169689Skan 1242169689Skan instead of 1243169689Skan 1244169689Skan {(uint) 0, +, (uint) 260} 1245169689Skan*/ 1246169689Skan 1247169689Skantree 1248169689Skanchrec_convert (tree type, tree chrec, tree at_stmt) 1249169689Skan{ 1250169689Skan return chrec_convert_1 (type, chrec, at_stmt, true); 1251169689Skan} 1252169689Skan 1253169689Skan/* Convert CHREC to TYPE. When the analyzer knows the context in 1254169689Skan which the CHREC is built, it sets AT_STMT to the statement that 1255169689Skan contains the definition of the analyzed variable, otherwise the 1256169689Skan conversion is less accurate: the information is used for 1257169689Skan determining a more accurate estimation of the number of iterations. 1258169689Skan By default AT_STMT could be safely set to NULL_TREE. 1259169689Skan 1260169689Skan USE_OVERFLOW_SEMANTICS is true if this function should assume that 1261169689Skan the rules for overflow of the given language apply (e.g., that signed 1262169689Skan arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1263169689Skan tests, but also to enforce that the result follows them. */ 1264169689Skan 1265169689Skanstatic tree 1266169689Skanchrec_convert_1 (tree type, tree chrec, tree at_stmt, 1267169689Skan bool use_overflow_semantics) 1268169689Skan{ 1269169689Skan tree ct, res; 1270169689Skan tree base, step; 1271169689Skan struct loop *loop; 1272169689Skan 1273169689Skan if (automatically_generated_chrec_p (chrec)) 1274169689Skan return chrec; 1275169689Skan 1276169689Skan ct = chrec_type (chrec); 1277169689Skan if (ct == type) 1278169689Skan return chrec; 1279169689Skan 1280169689Skan if (!evolution_function_is_affine_p (chrec)) 1281169689Skan goto keep_cast; 1282169689Skan 1283169689Skan loop = current_loops->parray[CHREC_VARIABLE (chrec)]; 1284169689Skan base = CHREC_LEFT (chrec); 1285169689Skan step = CHREC_RIGHT (chrec); 1286169689Skan 1287169689Skan if (convert_affine_scev (loop, type, &base, &step, at_stmt, 1288169689Skan use_overflow_semantics)) 1289169689Skan return build_polynomial_chrec (loop->num, base, step); 1290169689Skan 1291169689Skan /* If we cannot propagate the cast inside the chrec, just keep the cast. */ 1292169689Skankeep_cast: 1293169689Skan res = fold_convert (type, chrec); 1294169689Skan 1295169689Skan /* Don't propagate overflows. */ 1296169689Skan if (CONSTANT_CLASS_P (res)) 1297169689Skan { 1298169689Skan TREE_CONSTANT_OVERFLOW (res) = 0; 1299169689Skan TREE_OVERFLOW (res) = 0; 1300169689Skan } 1301169689Skan 1302169689Skan /* But reject constants that don't fit in their type after conversion. 1303169689Skan This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the 1304169689Skan natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, 1305169689Skan and can cause problems later when computing niters of loops. Note 1306169689Skan that we don't do the check before converting because we don't want 1307169689Skan to reject conversions of negative chrecs to unsigned types. */ 1308169689Skan if (TREE_CODE (res) == INTEGER_CST 1309169689Skan && TREE_CODE (type) == INTEGER_TYPE 1310169689Skan && !int_fits_type_p (res, type)) 1311169689Skan res = chrec_dont_know; 1312169689Skan 1313169689Skan return res; 1314169689Skan} 1315169689Skan 1316169689Skan/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new 1317169689Skan chrec if something else than what chrec_convert would do happens, NULL_TREE 1318169689Skan otherwise. */ 1319169689Skan 1320169689Skantree 1321169689Skanchrec_convert_aggressive (tree type, tree chrec) 1322169689Skan{ 1323169689Skan tree inner_type, left, right, lc, rc; 1324169689Skan 1325169689Skan if (automatically_generated_chrec_p (chrec) 1326169689Skan || TREE_CODE (chrec) != POLYNOMIAL_CHREC) 1327169689Skan return NULL_TREE; 1328169689Skan 1329169689Skan inner_type = TREE_TYPE (chrec); 1330169689Skan if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) 1331169689Skan return NULL_TREE; 1332169689Skan 1333169689Skan /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */ 1334169689Skan if (avoid_arithmetics_in_type_p (type)) 1335169689Skan return NULL_TREE; 1336169689Skan 1337169689Skan left = CHREC_LEFT (chrec); 1338169689Skan right = CHREC_RIGHT (chrec); 1339169689Skan lc = chrec_convert_aggressive (type, left); 1340169689Skan if (!lc) 1341169689Skan lc = chrec_convert (type, left, NULL_TREE); 1342169689Skan rc = chrec_convert_aggressive (type, right); 1343169689Skan if (!rc) 1344169689Skan rc = chrec_convert (type, right, NULL_TREE); 1345169689Skan 1346169689Skan return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); 1347169689Skan} 1348169689Skan 1349169689Skan/* Returns true when CHREC0 == CHREC1. */ 1350169689Skan 1351169689Skanbool 1352169689Skaneq_evolutions_p (tree chrec0, 1353169689Skan tree chrec1) 1354169689Skan{ 1355169689Skan if (chrec0 == NULL_TREE 1356169689Skan || chrec1 == NULL_TREE 1357169689Skan || TREE_CODE (chrec0) != TREE_CODE (chrec1)) 1358169689Skan return false; 1359169689Skan 1360169689Skan if (chrec0 == chrec1) 1361169689Skan return true; 1362169689Skan 1363169689Skan switch (TREE_CODE (chrec0)) 1364169689Skan { 1365169689Skan case INTEGER_CST: 1366169689Skan return operand_equal_p (chrec0, chrec1, 0); 1367169689Skan 1368169689Skan case POLYNOMIAL_CHREC: 1369169689Skan return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 1370169689Skan && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 1371169689Skan && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 1372169689Skan default: 1373169689Skan return false; 1374169689Skan } 1375169689Skan} 1376169689Skan 1377169689Skan/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), 1378169689Skan EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine 1379169689Skan which of these cases happens. */ 1380169689Skan 1381169689Skanenum ev_direction 1382169689Skanscev_direction (tree chrec) 1383169689Skan{ 1384169689Skan tree step; 1385169689Skan 1386169689Skan if (!evolution_function_is_affine_p (chrec)) 1387169689Skan return EV_DIR_UNKNOWN; 1388169689Skan 1389169689Skan step = CHREC_RIGHT (chrec); 1390169689Skan if (TREE_CODE (step) != INTEGER_CST) 1391169689Skan return EV_DIR_UNKNOWN; 1392169689Skan 1393169689Skan if (tree_int_cst_sign_bit (step)) 1394169689Skan return EV_DIR_DECREASES; 1395169689Skan else 1396169689Skan return EV_DIR_GROWS; 1397169689Skan} 1398