1169689Skan/* Rtl-level induction variable analysis. 2169689Skan Copyright (C) 2004, 2005 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/* This is a simple analysis of induction variables of the loop. The major use 22169689Skan is for determining the number of iterations of a loop for loop unrolling, 23169689Skan doloop optimization and branch prediction. The iv information is computed 24169689Skan on demand. 25169689Skan 26169689Skan Induction variable is analyzed by walking the use-def chains. When a biv 27169689Skan is found, it is cached in the bivs hash table. When register is proved 28169689Skan to be a giv, its description is stored to DF_REF_DATA of the def reference. 29169689Skan 30169689Skan The analysis works always with one loop -- you must call 31169689Skan iv_analysis_loop_init (loop) for it. All the other functions then work with 32169689Skan this loop. When you need to work with another loop, just call 33169689Skan iv_analysis_loop_init for it. When you no longer need iv analysis, call 34169689Skan iv_analysis_done () to clean up the memory. 35169689Skan 36169689Skan The available functions are: 37169689Skan 38169689Skan iv_analyze (insn, reg, iv): Stores the description of the induction variable 39169689Skan corresponding to the use of register REG in INSN to IV. Returns true if 40169689Skan REG is an induction variable in INSN. false otherwise. 41169689Skan If use of REG is not found in INSN, following insns are scanned (so that 42169689Skan we may call this function on insn returned by get_condition). 43169689Skan iv_analyze_result (insn, def, iv): Stores to IV the description of the iv 44169689Skan corresponding to DEF, which is a register defined in INSN. 45169689Skan iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv 46169689Skan corresponding to expression EXPR evaluated at INSN. All registers used bu 47169689Skan EXPR must also be used in INSN. 48169689Skan iv_current_loop_df (): Returns the dataflow object for the current loop used 49169689Skan by iv analysis. */ 50169689Skan 51169689Skan#include "config.h" 52169689Skan#include "system.h" 53169689Skan#include "coretypes.h" 54169689Skan#include "tm.h" 55169689Skan#include "rtl.h" 56169689Skan#include "hard-reg-set.h" 57169689Skan#include "obstack.h" 58169689Skan#include "basic-block.h" 59169689Skan#include "cfgloop.h" 60169689Skan#include "expr.h" 61169689Skan#include "intl.h" 62169689Skan#include "output.h" 63169689Skan#include "toplev.h" 64169689Skan#include "df.h" 65169689Skan#include "hashtab.h" 66169689Skan 67169689Skan/* Possible return values of iv_get_reaching_def. */ 68169689Skan 69169689Skanenum iv_grd_result 70169689Skan{ 71169689Skan /* More than one reaching def, or reaching def that does not 72169689Skan dominate the use. */ 73169689Skan GRD_INVALID, 74169689Skan 75169689Skan /* The use is trivial invariant of the loop, i.e. is not changed 76169689Skan inside the loop. */ 77169689Skan GRD_INVARIANT, 78169689Skan 79169689Skan /* The use is reached by initial value and a value from the 80169689Skan previous iteration. */ 81169689Skan GRD_MAYBE_BIV, 82169689Skan 83169689Skan /* The use has single dominating def. */ 84169689Skan GRD_SINGLE_DOM 85169689Skan}; 86169689Skan 87169689Skan/* Information about a biv. */ 88169689Skan 89169689Skanstruct biv_entry 90169689Skan{ 91169689Skan unsigned regno; /* The register of the biv. */ 92169689Skan struct rtx_iv iv; /* Value of the biv. */ 93169689Skan}; 94169689Skan 95169689Skan/* Induction variable stored at the reference. */ 96169689Skan#define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF)) 97169689Skan#define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV) 98169689Skan 99169689Skan/* The current loop. */ 100169689Skan 101169689Skanstatic struct loop *current_loop; 102169689Skan 103169689Skan/* Dataflow information for the current loop. */ 104169689Skan 105169689Skanstatic struct df *df = NULL; 106169689Skan 107169689Skan/* Bivs of the current loop. */ 108169689Skan 109169689Skanstatic htab_t bivs; 110169689Skan 111169689Skan/* Return the dataflow object for the current loop. */ 112169689Skanstruct df * 113169689Skaniv_current_loop_df (void) 114169689Skan{ 115169689Skan return df; 116169689Skan} 117169689Skan 118169689Skanstatic bool iv_analyze_op (rtx, rtx, struct rtx_iv *); 119169689Skan 120169689Skan/* Dumps information about IV to FILE. */ 121169689Skan 122169689Skanextern void dump_iv_info (FILE *, struct rtx_iv *); 123169689Skanvoid 124169689Skandump_iv_info (FILE *file, struct rtx_iv *iv) 125169689Skan{ 126169689Skan if (!iv->base) 127169689Skan { 128169689Skan fprintf (file, "not simple"); 129169689Skan return; 130169689Skan } 131169689Skan 132169689Skan if (iv->step == const0_rtx 133169689Skan && !iv->first_special) 134169689Skan fprintf (file, "invariant "); 135169689Skan 136169689Skan print_rtl (file, iv->base); 137169689Skan if (iv->step != const0_rtx) 138169689Skan { 139169689Skan fprintf (file, " + "); 140169689Skan print_rtl (file, iv->step); 141169689Skan fprintf (file, " * iteration"); 142169689Skan } 143169689Skan fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode)); 144169689Skan 145169689Skan if (iv->mode != iv->extend_mode) 146169689Skan fprintf (file, " %s to %s", 147169689Skan rtx_name[iv->extend], 148169689Skan GET_MODE_NAME (iv->extend_mode)); 149169689Skan 150169689Skan if (iv->mult != const1_rtx) 151169689Skan { 152169689Skan fprintf (file, " * "); 153169689Skan print_rtl (file, iv->mult); 154169689Skan } 155169689Skan if (iv->delta != const0_rtx) 156169689Skan { 157169689Skan fprintf (file, " + "); 158169689Skan print_rtl (file, iv->delta); 159169689Skan } 160169689Skan if (iv->first_special) 161169689Skan fprintf (file, " (first special)"); 162169689Skan} 163169689Skan 164169689Skan/* Generates a subreg to get the least significant part of EXPR (in mode 165169689Skan INNER_MODE) to OUTER_MODE. */ 166169689Skan 167169689Skanrtx 168169689Skanlowpart_subreg (enum machine_mode outer_mode, rtx expr, 169169689Skan enum machine_mode inner_mode) 170169689Skan{ 171169689Skan return simplify_gen_subreg (outer_mode, expr, inner_mode, 172169689Skan subreg_lowpart_offset (outer_mode, inner_mode)); 173169689Skan} 174169689Skan 175169689Skan/* Checks whether REG is a well-behaved register. */ 176169689Skan 177169689Skanstatic bool 178169689Skansimple_reg_p (rtx reg) 179169689Skan{ 180169689Skan unsigned r; 181169689Skan 182169689Skan if (GET_CODE (reg) == SUBREG) 183169689Skan { 184169689Skan if (!subreg_lowpart_p (reg)) 185169689Skan return false; 186169689Skan reg = SUBREG_REG (reg); 187169689Skan } 188169689Skan 189169689Skan if (!REG_P (reg)) 190169689Skan return false; 191169689Skan 192169689Skan r = REGNO (reg); 193169689Skan if (HARD_REGISTER_NUM_P (r)) 194169689Skan return false; 195169689Skan 196169689Skan if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT) 197169689Skan return false; 198169689Skan 199169689Skan return true; 200169689Skan} 201169689Skan 202169689Skan/* Clears the information about ivs stored in df. */ 203169689Skan 204169689Skanstatic void 205169689Skanclear_iv_info (void) 206169689Skan{ 207169689Skan unsigned i, n_defs = DF_DEFS_SIZE (df); 208169689Skan struct rtx_iv *iv; 209169689Skan struct df_ref *def; 210169689Skan 211169689Skan for (i = 0; i < n_defs; i++) 212169689Skan { 213169689Skan def = DF_DEFS_GET (df, i); 214169689Skan iv = DF_REF_IV (def); 215169689Skan if (!iv) 216169689Skan continue; 217169689Skan free (iv); 218169689Skan DF_REF_IV_SET (def, NULL); 219169689Skan } 220169689Skan 221169689Skan htab_empty (bivs); 222169689Skan} 223169689Skan 224169689Skan/* Returns hash value for biv B. */ 225169689Skan 226169689Skanstatic hashval_t 227169689Skanbiv_hash (const void *b) 228169689Skan{ 229169689Skan return ((const struct biv_entry *) b)->regno; 230169689Skan} 231169689Skan 232169689Skan/* Compares biv B and register R. */ 233169689Skan 234169689Skanstatic int 235169689Skanbiv_eq (const void *b, const void *r) 236169689Skan{ 237169689Skan return ((const struct biv_entry *) b)->regno == REGNO ((rtx) r); 238169689Skan} 239169689Skan 240169689Skan/* Prepare the data for an induction variable analysis of a LOOP. */ 241169689Skan 242169689Skanvoid 243169689Skaniv_analysis_loop_init (struct loop *loop) 244169689Skan{ 245169689Skan basic_block *body = get_loop_body_in_dom_order (loop), bb; 246169689Skan bitmap blocks = BITMAP_ALLOC (NULL); 247169689Skan unsigned i; 248169689Skan bool first_time = (df == NULL); 249169689Skan 250169689Skan current_loop = loop; 251169689Skan 252169689Skan /* Clear the information from the analysis of the previous loop. */ 253169689Skan if (first_time) 254169689Skan { 255169689Skan df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES); 256169689Skan df_chain_add_problem (df, DF_UD_CHAIN); 257169689Skan bivs = htab_create (10, biv_hash, biv_eq, free); 258169689Skan } 259169689Skan else 260169689Skan clear_iv_info (); 261169689Skan 262169689Skan for (i = 0; i < loop->num_nodes; i++) 263169689Skan { 264169689Skan bb = body[i]; 265169689Skan bitmap_set_bit (blocks, bb->index); 266169689Skan } 267169689Skan df_set_blocks (df, blocks); 268169689Skan df_analyze (df); 269169689Skan BITMAP_FREE (blocks); 270169689Skan free (body); 271169689Skan} 272169689Skan 273169689Skan/* Finds the definition of REG that dominates loop latch and stores 274169689Skan it to DEF. Returns false if there is not a single definition 275169689Skan dominating the latch. If REG has no definition in loop, DEF 276169689Skan is set to NULL and true is returned. */ 277169689Skan 278169689Skanstatic bool 279169689Skanlatch_dominating_def (rtx reg, struct df_ref **def) 280169689Skan{ 281169689Skan struct df_ref *single_rd = NULL, *adef; 282169689Skan unsigned regno = REGNO (reg); 283169689Skan struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno); 284169689Skan struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, current_loop->latch); 285169689Skan 286169689Skan for (adef = reg_info->reg_chain; adef; adef = adef->next_reg) 287169689Skan { 288169689Skan if (!bitmap_bit_p (bb_info->out, DF_REF_ID (adef))) 289169689Skan continue; 290169689Skan 291169689Skan /* More than one reaching definition. */ 292169689Skan if (single_rd) 293169689Skan return false; 294169689Skan 295169689Skan if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef))) 296169689Skan return false; 297169689Skan 298169689Skan single_rd = adef; 299169689Skan } 300169689Skan 301169689Skan *def = single_rd; 302169689Skan return true; 303169689Skan} 304169689Skan 305169689Skan/* Gets definition of REG reaching its use in INSN and stores it to DEF. */ 306169689Skan 307169689Skanstatic enum iv_grd_result 308169689Skaniv_get_reaching_def (rtx insn, rtx reg, struct df_ref **def) 309169689Skan{ 310169689Skan struct df_ref *use, *adef; 311169689Skan basic_block def_bb, use_bb; 312169689Skan rtx def_insn; 313169689Skan bool dom_p; 314169689Skan 315169689Skan *def = NULL; 316169689Skan if (!simple_reg_p (reg)) 317169689Skan return GRD_INVALID; 318169689Skan if (GET_CODE (reg) == SUBREG) 319169689Skan reg = SUBREG_REG (reg); 320169689Skan gcc_assert (REG_P (reg)); 321169689Skan 322169689Skan use = df_find_use (df, insn, reg); 323169689Skan gcc_assert (use != NULL); 324169689Skan 325169689Skan if (!DF_REF_CHAIN (use)) 326169689Skan return GRD_INVARIANT; 327169689Skan 328169689Skan /* More than one reaching def. */ 329169689Skan if (DF_REF_CHAIN (use)->next) 330169689Skan return GRD_INVALID; 331169689Skan 332169689Skan adef = DF_REF_CHAIN (use)->ref; 333169689Skan def_insn = DF_REF_INSN (adef); 334169689Skan def_bb = DF_REF_BB (adef); 335169689Skan use_bb = BLOCK_FOR_INSN (insn); 336169689Skan 337169689Skan if (use_bb == def_bb) 338169689Skan dom_p = (DF_INSN_LUID (df, def_insn) < DF_INSN_LUID (df, insn)); 339169689Skan else 340169689Skan dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb); 341169689Skan 342169689Skan if (dom_p) 343169689Skan { 344169689Skan *def = adef; 345169689Skan return GRD_SINGLE_DOM; 346169689Skan } 347169689Skan 348169689Skan /* The definition does not dominate the use. This is still OK if 349169689Skan this may be a use of a biv, i.e. if the def_bb dominates loop 350169689Skan latch. */ 351169689Skan if (just_once_each_iteration_p (current_loop, def_bb)) 352169689Skan return GRD_MAYBE_BIV; 353169689Skan 354169689Skan return GRD_INVALID; 355169689Skan} 356169689Skan 357169689Skan/* Sets IV to invariant CST in MODE. Always returns true (just for 358169689Skan consistency with other iv manipulation functions that may fail). */ 359169689Skan 360169689Skanstatic bool 361169689Skaniv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode) 362169689Skan{ 363169689Skan if (mode == VOIDmode) 364169689Skan mode = GET_MODE (cst); 365169689Skan 366169689Skan iv->mode = mode; 367169689Skan iv->base = cst; 368169689Skan iv->step = const0_rtx; 369169689Skan iv->first_special = false; 370169689Skan iv->extend = UNKNOWN; 371169689Skan iv->extend_mode = iv->mode; 372169689Skan iv->delta = const0_rtx; 373169689Skan iv->mult = const1_rtx; 374169689Skan 375169689Skan return true; 376169689Skan} 377169689Skan 378169689Skan/* Evaluates application of subreg to MODE on IV. */ 379169689Skan 380169689Skanstatic bool 381169689Skaniv_subreg (struct rtx_iv *iv, enum machine_mode mode) 382169689Skan{ 383169689Skan /* If iv is invariant, just calculate the new value. */ 384169689Skan if (iv->step == const0_rtx 385169689Skan && !iv->first_special) 386169689Skan { 387169689Skan rtx val = get_iv_value (iv, const0_rtx); 388169689Skan val = lowpart_subreg (mode, val, iv->extend_mode); 389169689Skan 390169689Skan iv->base = val; 391169689Skan iv->extend = UNKNOWN; 392169689Skan iv->mode = iv->extend_mode = mode; 393169689Skan iv->delta = const0_rtx; 394169689Skan iv->mult = const1_rtx; 395169689Skan return true; 396169689Skan } 397169689Skan 398169689Skan if (iv->extend_mode == mode) 399169689Skan return true; 400169689Skan 401169689Skan if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode)) 402169689Skan return false; 403169689Skan 404169689Skan iv->extend = UNKNOWN; 405169689Skan iv->mode = mode; 406169689Skan 407169689Skan iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta, 408169689Skan simplify_gen_binary (MULT, iv->extend_mode, 409169689Skan iv->base, iv->mult)); 410169689Skan iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult); 411169689Skan iv->mult = const1_rtx; 412169689Skan iv->delta = const0_rtx; 413169689Skan iv->first_special = false; 414169689Skan 415169689Skan return true; 416169689Skan} 417169689Skan 418169689Skan/* Evaluates application of EXTEND to MODE on IV. */ 419169689Skan 420169689Skanstatic bool 421169689Skaniv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode) 422169689Skan{ 423169689Skan /* If iv is invariant, just calculate the new value. */ 424169689Skan if (iv->step == const0_rtx 425169689Skan && !iv->first_special) 426169689Skan { 427169689Skan rtx val = get_iv_value (iv, const0_rtx); 428169689Skan val = simplify_gen_unary (extend, mode, val, iv->extend_mode); 429169689Skan 430169689Skan iv->base = val; 431169689Skan iv->extend = UNKNOWN; 432169689Skan iv->mode = iv->extend_mode = mode; 433169689Skan iv->delta = const0_rtx; 434169689Skan iv->mult = const1_rtx; 435169689Skan return true; 436169689Skan } 437169689Skan 438169689Skan if (mode != iv->extend_mode) 439169689Skan return false; 440169689Skan 441169689Skan if (iv->extend != UNKNOWN 442169689Skan && iv->extend != extend) 443169689Skan return false; 444169689Skan 445169689Skan iv->extend = extend; 446169689Skan 447169689Skan return true; 448169689Skan} 449169689Skan 450169689Skan/* Evaluates negation of IV. */ 451169689Skan 452169689Skanstatic bool 453169689Skaniv_neg (struct rtx_iv *iv) 454169689Skan{ 455169689Skan if (iv->extend == UNKNOWN) 456169689Skan { 457169689Skan iv->base = simplify_gen_unary (NEG, iv->extend_mode, 458169689Skan iv->base, iv->extend_mode); 459169689Skan iv->step = simplify_gen_unary (NEG, iv->extend_mode, 460169689Skan iv->step, iv->extend_mode); 461169689Skan } 462169689Skan else 463169689Skan { 464169689Skan iv->delta = simplify_gen_unary (NEG, iv->extend_mode, 465169689Skan iv->delta, iv->extend_mode); 466169689Skan iv->mult = simplify_gen_unary (NEG, iv->extend_mode, 467169689Skan iv->mult, iv->extend_mode); 468169689Skan } 469169689Skan 470169689Skan return true; 471169689Skan} 472169689Skan 473169689Skan/* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */ 474169689Skan 475169689Skanstatic bool 476169689Skaniv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op) 477169689Skan{ 478169689Skan enum machine_mode mode; 479169689Skan rtx arg; 480169689Skan 481169689Skan /* Extend the constant to extend_mode of the other operand if necessary. */ 482169689Skan if (iv0->extend == UNKNOWN 483169689Skan && iv0->mode == iv0->extend_mode 484169689Skan && iv0->step == const0_rtx 485169689Skan && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode)) 486169689Skan { 487169689Skan iv0->extend_mode = iv1->extend_mode; 488169689Skan iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode, 489169689Skan iv0->base, iv0->mode); 490169689Skan } 491169689Skan if (iv1->extend == UNKNOWN 492169689Skan && iv1->mode == iv1->extend_mode 493169689Skan && iv1->step == const0_rtx 494169689Skan && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode)) 495169689Skan { 496169689Skan iv1->extend_mode = iv0->extend_mode; 497169689Skan iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode, 498169689Skan iv1->base, iv1->mode); 499169689Skan } 500169689Skan 501169689Skan mode = iv0->extend_mode; 502169689Skan if (mode != iv1->extend_mode) 503169689Skan return false; 504169689Skan 505169689Skan if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN) 506169689Skan { 507169689Skan if (iv0->mode != iv1->mode) 508169689Skan return false; 509169689Skan 510169689Skan iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base); 511169689Skan iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step); 512169689Skan 513169689Skan return true; 514169689Skan } 515169689Skan 516169689Skan /* Handle addition of constant. */ 517169689Skan if (iv1->extend == UNKNOWN 518169689Skan && iv1->mode == mode 519169689Skan && iv1->step == const0_rtx) 520169689Skan { 521169689Skan iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base); 522169689Skan return true; 523169689Skan } 524169689Skan 525169689Skan if (iv0->extend == UNKNOWN 526169689Skan && iv0->mode == mode 527169689Skan && iv0->step == const0_rtx) 528169689Skan { 529169689Skan arg = iv0->base; 530169689Skan *iv0 = *iv1; 531169689Skan if (op == MINUS 532169689Skan && !iv_neg (iv0)) 533169689Skan return false; 534169689Skan 535169689Skan iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg); 536169689Skan return true; 537169689Skan } 538169689Skan 539169689Skan return false; 540169689Skan} 541169689Skan 542169689Skan/* Evaluates multiplication of IV by constant CST. */ 543169689Skan 544169689Skanstatic bool 545169689Skaniv_mult (struct rtx_iv *iv, rtx mby) 546169689Skan{ 547169689Skan enum machine_mode mode = iv->extend_mode; 548169689Skan 549169689Skan if (GET_MODE (mby) != VOIDmode 550169689Skan && GET_MODE (mby) != mode) 551169689Skan return false; 552169689Skan 553169689Skan if (iv->extend == UNKNOWN) 554169689Skan { 555169689Skan iv->base = simplify_gen_binary (MULT, mode, iv->base, mby); 556169689Skan iv->step = simplify_gen_binary (MULT, mode, iv->step, mby); 557169689Skan } 558169689Skan else 559169689Skan { 560169689Skan iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby); 561169689Skan iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby); 562169689Skan } 563169689Skan 564169689Skan return true; 565169689Skan} 566169689Skan 567169689Skan/* Evaluates shift of IV by constant CST. */ 568169689Skan 569169689Skanstatic bool 570169689Skaniv_shift (struct rtx_iv *iv, rtx mby) 571169689Skan{ 572169689Skan enum machine_mode mode = iv->extend_mode; 573169689Skan 574169689Skan if (GET_MODE (mby) != VOIDmode 575169689Skan && GET_MODE (mby) != mode) 576169689Skan return false; 577169689Skan 578169689Skan if (iv->extend == UNKNOWN) 579169689Skan { 580169689Skan iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby); 581169689Skan iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby); 582169689Skan } 583169689Skan else 584169689Skan { 585169689Skan iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby); 586169689Skan iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby); 587169689Skan } 588169689Skan 589169689Skan return true; 590169689Skan} 591169689Skan 592169689Skan/* The recursive part of get_biv_step. Gets the value of the single value 593169689Skan defined by DEF wrto initial value of REG inside loop, in shape described 594169689Skan at get_biv_step. */ 595169689Skan 596169689Skanstatic bool 597169689Skanget_biv_step_1 (struct df_ref *def, rtx reg, 598169689Skan rtx *inner_step, enum machine_mode *inner_mode, 599169689Skan enum rtx_code *extend, enum machine_mode outer_mode, 600169689Skan rtx *outer_step) 601169689Skan{ 602169689Skan rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX; 603169689Skan rtx next, nextr, tmp; 604169689Skan enum rtx_code code; 605169689Skan rtx insn = DF_REF_INSN (def); 606169689Skan struct df_ref *next_def; 607169689Skan enum iv_grd_result res; 608169689Skan 609169689Skan set = single_set (insn); 610169689Skan if (!set) 611169689Skan return false; 612169689Skan 613169689Skan rhs = find_reg_equal_equiv_note (insn); 614169689Skan if (rhs) 615169689Skan rhs = XEXP (rhs, 0); 616169689Skan else 617169689Skan rhs = SET_SRC (set); 618169689Skan 619169689Skan code = GET_CODE (rhs); 620169689Skan switch (code) 621169689Skan { 622169689Skan case SUBREG: 623169689Skan case REG: 624169689Skan next = rhs; 625169689Skan break; 626169689Skan 627169689Skan case PLUS: 628169689Skan case MINUS: 629169689Skan op0 = XEXP (rhs, 0); 630169689Skan op1 = XEXP (rhs, 1); 631169689Skan 632169689Skan if (code == PLUS && CONSTANT_P (op0)) 633169689Skan { 634169689Skan tmp = op0; op0 = op1; op1 = tmp; 635169689Skan } 636169689Skan 637169689Skan if (!simple_reg_p (op0) 638169689Skan || !CONSTANT_P (op1)) 639169689Skan return false; 640169689Skan 641169689Skan if (GET_MODE (rhs) != outer_mode) 642169689Skan { 643169689Skan /* ppc64 uses expressions like 644169689Skan 645169689Skan (set x:SI (plus:SI (subreg:SI y:DI) 1)). 646169689Skan 647169689Skan this is equivalent to 648169689Skan 649169689Skan (set x':DI (plus:DI y:DI 1)) 650169689Skan (set x:SI (subreg:SI (x':DI)). */ 651169689Skan if (GET_CODE (op0) != SUBREG) 652169689Skan return false; 653169689Skan if (GET_MODE (SUBREG_REG (op0)) != outer_mode) 654169689Skan return false; 655169689Skan } 656169689Skan 657169689Skan next = op0; 658169689Skan break; 659169689Skan 660169689Skan case SIGN_EXTEND: 661169689Skan case ZERO_EXTEND: 662169689Skan if (GET_MODE (rhs) != outer_mode) 663169689Skan return false; 664169689Skan 665169689Skan op0 = XEXP (rhs, 0); 666169689Skan if (!simple_reg_p (op0)) 667169689Skan return false; 668169689Skan 669169689Skan next = op0; 670169689Skan break; 671169689Skan 672169689Skan default: 673169689Skan return false; 674169689Skan } 675169689Skan 676169689Skan if (GET_CODE (next) == SUBREG) 677169689Skan { 678169689Skan if (!subreg_lowpart_p (next)) 679169689Skan return false; 680169689Skan 681169689Skan nextr = SUBREG_REG (next); 682169689Skan if (GET_MODE (nextr) != outer_mode) 683169689Skan return false; 684169689Skan } 685169689Skan else 686169689Skan nextr = next; 687169689Skan 688169689Skan res = iv_get_reaching_def (insn, nextr, &next_def); 689169689Skan 690169689Skan if (res == GRD_INVALID || res == GRD_INVARIANT) 691169689Skan return false; 692169689Skan 693169689Skan if (res == GRD_MAYBE_BIV) 694169689Skan { 695169689Skan if (!rtx_equal_p (nextr, reg)) 696169689Skan return false; 697169689Skan 698169689Skan *inner_step = const0_rtx; 699169689Skan *extend = UNKNOWN; 700169689Skan *inner_mode = outer_mode; 701169689Skan *outer_step = const0_rtx; 702169689Skan } 703169689Skan else if (!get_biv_step_1 (next_def, reg, 704169689Skan inner_step, inner_mode, extend, outer_mode, 705169689Skan outer_step)) 706169689Skan return false; 707169689Skan 708169689Skan if (GET_CODE (next) == SUBREG) 709169689Skan { 710169689Skan enum machine_mode amode = GET_MODE (next); 711169689Skan 712169689Skan if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode)) 713169689Skan return false; 714169689Skan 715169689Skan *inner_mode = amode; 716169689Skan *inner_step = simplify_gen_binary (PLUS, outer_mode, 717169689Skan *inner_step, *outer_step); 718169689Skan *outer_step = const0_rtx; 719169689Skan *extend = UNKNOWN; 720169689Skan } 721169689Skan 722169689Skan switch (code) 723169689Skan { 724169689Skan case REG: 725169689Skan case SUBREG: 726169689Skan break; 727169689Skan 728169689Skan case PLUS: 729169689Skan case MINUS: 730169689Skan if (*inner_mode == outer_mode 731169689Skan /* See comment in previous switch. */ 732169689Skan || GET_MODE (rhs) != outer_mode) 733169689Skan *inner_step = simplify_gen_binary (code, outer_mode, 734169689Skan *inner_step, op1); 735169689Skan else 736169689Skan *outer_step = simplify_gen_binary (code, outer_mode, 737169689Skan *outer_step, op1); 738169689Skan break; 739169689Skan 740169689Skan case SIGN_EXTEND: 741169689Skan case ZERO_EXTEND: 742169689Skan gcc_assert (GET_MODE (op0) == *inner_mode 743169689Skan && *extend == UNKNOWN 744169689Skan && *outer_step == const0_rtx); 745169689Skan 746169689Skan *extend = code; 747169689Skan break; 748169689Skan 749169689Skan default: 750169689Skan return false; 751169689Skan } 752169689Skan 753169689Skan return true; 754169689Skan} 755169689Skan 756169689Skan/* Gets the operation on register REG inside loop, in shape 757169689Skan 758169689Skan OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP)) 759169689Skan 760169689Skan If the operation cannot be described in this shape, return false. 761169689Skan LAST_DEF is the definition of REG that dominates loop latch. */ 762169689Skan 763169689Skanstatic bool 764169689Skanget_biv_step (struct df_ref *last_def, rtx reg, rtx *inner_step, 765169689Skan enum machine_mode *inner_mode, enum rtx_code *extend, 766169689Skan enum machine_mode *outer_mode, rtx *outer_step) 767169689Skan{ 768169689Skan *outer_mode = GET_MODE (reg); 769169689Skan 770169689Skan if (!get_biv_step_1 (last_def, reg, 771169689Skan inner_step, inner_mode, extend, *outer_mode, 772169689Skan outer_step)) 773169689Skan return false; 774169689Skan 775169689Skan gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN)); 776169689Skan gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx); 777169689Skan 778169689Skan return true; 779169689Skan} 780169689Skan 781169689Skan/* Records information that DEF is induction variable IV. */ 782169689Skan 783169689Skanstatic void 784169689Skanrecord_iv (struct df_ref *def, struct rtx_iv *iv) 785169689Skan{ 786169689Skan struct rtx_iv *recorded_iv = XNEW (struct rtx_iv); 787169689Skan 788169689Skan *recorded_iv = *iv; 789169689Skan DF_REF_IV_SET (def, recorded_iv); 790169689Skan} 791169689Skan 792169689Skan/* If DEF was already analyzed for bivness, store the description of the biv to 793169689Skan IV and return true. Otherwise return false. */ 794169689Skan 795169689Skanstatic bool 796169689Skananalyzed_for_bivness_p (rtx def, struct rtx_iv *iv) 797169689Skan{ 798169689Skan struct biv_entry *biv = htab_find_with_hash (bivs, def, REGNO (def)); 799169689Skan 800169689Skan if (!biv) 801169689Skan return false; 802169689Skan 803169689Skan *iv = biv->iv; 804169689Skan return true; 805169689Skan} 806169689Skan 807169689Skanstatic void 808169689Skanrecord_biv (rtx def, struct rtx_iv *iv) 809169689Skan{ 810169689Skan struct biv_entry *biv = XNEW (struct biv_entry); 811169689Skan void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT); 812169689Skan 813169689Skan biv->regno = REGNO (def); 814169689Skan biv->iv = *iv; 815169689Skan gcc_assert (!*slot); 816169689Skan *slot = biv; 817169689Skan} 818169689Skan 819169689Skan/* Determines whether DEF is a biv and if so, stores its description 820169689Skan to *IV. */ 821169689Skan 822169689Skanstatic bool 823169689Skaniv_analyze_biv (rtx def, struct rtx_iv *iv) 824169689Skan{ 825169689Skan rtx inner_step, outer_step; 826169689Skan enum machine_mode inner_mode, outer_mode; 827169689Skan enum rtx_code extend; 828169689Skan struct df_ref *last_def; 829169689Skan 830169689Skan if (dump_file) 831169689Skan { 832169689Skan fprintf (dump_file, "Analyzing "); 833169689Skan print_rtl (dump_file, def); 834169689Skan fprintf (dump_file, " for bivness.\n"); 835169689Skan } 836169689Skan 837169689Skan if (!REG_P (def)) 838169689Skan { 839169689Skan if (!CONSTANT_P (def)) 840169689Skan return false; 841169689Skan 842169689Skan return iv_constant (iv, def, VOIDmode); 843169689Skan } 844169689Skan 845169689Skan if (!latch_dominating_def (def, &last_def)) 846169689Skan { 847169689Skan if (dump_file) 848169689Skan fprintf (dump_file, " not simple.\n"); 849169689Skan return false; 850169689Skan } 851169689Skan 852169689Skan if (!last_def) 853169689Skan return iv_constant (iv, def, VOIDmode); 854169689Skan 855169689Skan if (analyzed_for_bivness_p (def, iv)) 856169689Skan { 857169689Skan if (dump_file) 858169689Skan fprintf (dump_file, " already analysed.\n"); 859169689Skan return iv->base != NULL_RTX; 860169689Skan } 861169689Skan 862169689Skan if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend, 863169689Skan &outer_mode, &outer_step)) 864169689Skan { 865169689Skan iv->base = NULL_RTX; 866169689Skan goto end; 867169689Skan } 868169689Skan 869169689Skan /* Loop transforms base to es (base + inner_step) + outer_step, 870169689Skan where es means extend of subreg between inner_mode and outer_mode. 871169689Skan The corresponding induction variable is 872169689Skan 873169689Skan es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */ 874169689Skan 875169689Skan iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step); 876169689Skan iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step); 877169689Skan iv->mode = inner_mode; 878169689Skan iv->extend_mode = outer_mode; 879169689Skan iv->extend = extend; 880169689Skan iv->mult = const1_rtx; 881169689Skan iv->delta = outer_step; 882169689Skan iv->first_special = inner_mode != outer_mode; 883169689Skan 884169689Skan end: 885169689Skan if (dump_file) 886169689Skan { 887169689Skan fprintf (dump_file, " "); 888169689Skan dump_iv_info (dump_file, iv); 889169689Skan fprintf (dump_file, "\n"); 890169689Skan } 891169689Skan 892169689Skan record_biv (def, iv); 893169689Skan return iv->base != NULL_RTX; 894169689Skan} 895169689Skan 896169689Skan/* Analyzes expression RHS used at INSN and stores the result to *IV. 897169689Skan The mode of the induction variable is MODE. */ 898169689Skan 899169689Skanbool 900169689Skaniv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) 901169689Skan{ 902169689Skan rtx mby = NULL_RTX, tmp; 903169689Skan rtx op0 = NULL_RTX, op1 = NULL_RTX; 904169689Skan struct rtx_iv iv0, iv1; 905169689Skan enum rtx_code code = GET_CODE (rhs); 906169689Skan enum machine_mode omode = mode; 907169689Skan 908169689Skan iv->mode = VOIDmode; 909169689Skan iv->base = NULL_RTX; 910169689Skan iv->step = NULL_RTX; 911169689Skan 912169689Skan gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode); 913169689Skan 914169689Skan if (CONSTANT_P (rhs) 915169689Skan || REG_P (rhs) 916169689Skan || code == SUBREG) 917169689Skan { 918169689Skan if (!iv_analyze_op (insn, rhs, iv)) 919169689Skan return false; 920169689Skan 921169689Skan if (iv->mode == VOIDmode) 922169689Skan { 923169689Skan iv->mode = mode; 924169689Skan iv->extend_mode = mode; 925169689Skan } 926169689Skan 927169689Skan return true; 928169689Skan } 929169689Skan 930169689Skan switch (code) 931169689Skan { 932169689Skan case REG: 933169689Skan op0 = rhs; 934169689Skan break; 935169689Skan 936169689Skan case SIGN_EXTEND: 937169689Skan case ZERO_EXTEND: 938169689Skan case NEG: 939169689Skan op0 = XEXP (rhs, 0); 940169689Skan omode = GET_MODE (op0); 941169689Skan break; 942169689Skan 943169689Skan case PLUS: 944169689Skan case MINUS: 945169689Skan op0 = XEXP (rhs, 0); 946169689Skan op1 = XEXP (rhs, 1); 947169689Skan break; 948169689Skan 949169689Skan case MULT: 950169689Skan op0 = XEXP (rhs, 0); 951169689Skan mby = XEXP (rhs, 1); 952169689Skan if (!CONSTANT_P (mby)) 953169689Skan { 954169689Skan tmp = op0; 955169689Skan op0 = mby; 956169689Skan mby = tmp; 957169689Skan } 958169689Skan if (!CONSTANT_P (mby)) 959169689Skan return false; 960169689Skan break; 961169689Skan 962169689Skan case ASHIFT: 963169689Skan op0 = XEXP (rhs, 0); 964169689Skan mby = XEXP (rhs, 1); 965169689Skan if (!CONSTANT_P (mby)) 966169689Skan return false; 967169689Skan break; 968169689Skan 969169689Skan default: 970169689Skan return false; 971169689Skan } 972169689Skan 973169689Skan if (op0 974169689Skan && !iv_analyze_expr (insn, op0, omode, &iv0)) 975169689Skan return false; 976169689Skan 977169689Skan if (op1 978169689Skan && !iv_analyze_expr (insn, op1, omode, &iv1)) 979169689Skan return false; 980169689Skan 981169689Skan switch (code) 982169689Skan { 983169689Skan case SIGN_EXTEND: 984169689Skan case ZERO_EXTEND: 985169689Skan if (!iv_extend (&iv0, code, mode)) 986169689Skan return false; 987169689Skan break; 988169689Skan 989169689Skan case NEG: 990169689Skan if (!iv_neg (&iv0)) 991169689Skan return false; 992169689Skan break; 993169689Skan 994169689Skan case PLUS: 995169689Skan case MINUS: 996169689Skan if (!iv_add (&iv0, &iv1, code)) 997169689Skan return false; 998169689Skan break; 999169689Skan 1000169689Skan case MULT: 1001169689Skan if (!iv_mult (&iv0, mby)) 1002169689Skan return false; 1003169689Skan break; 1004169689Skan 1005169689Skan case ASHIFT: 1006169689Skan if (!iv_shift (&iv0, mby)) 1007169689Skan return false; 1008169689Skan break; 1009169689Skan 1010169689Skan default: 1011169689Skan break; 1012169689Skan } 1013169689Skan 1014169689Skan *iv = iv0; 1015169689Skan return iv->base != NULL_RTX; 1016169689Skan} 1017169689Skan 1018169689Skan/* Analyzes iv DEF and stores the result to *IV. */ 1019169689Skan 1020169689Skanstatic bool 1021169689Skaniv_analyze_def (struct df_ref *def, struct rtx_iv *iv) 1022169689Skan{ 1023169689Skan rtx insn = DF_REF_INSN (def); 1024169689Skan rtx reg = DF_REF_REG (def); 1025169689Skan rtx set, rhs; 1026169689Skan 1027169689Skan if (dump_file) 1028169689Skan { 1029169689Skan fprintf (dump_file, "Analysing def of "); 1030169689Skan print_rtl (dump_file, reg); 1031169689Skan fprintf (dump_file, " in insn "); 1032169689Skan print_rtl_single (dump_file, insn); 1033169689Skan } 1034169689Skan 1035169689Skan if (DF_REF_IV (def)) 1036169689Skan { 1037169689Skan if (dump_file) 1038169689Skan fprintf (dump_file, " already analysed.\n"); 1039169689Skan *iv = *DF_REF_IV (def); 1040169689Skan return iv->base != NULL_RTX; 1041169689Skan } 1042169689Skan 1043169689Skan iv->mode = VOIDmode; 1044169689Skan iv->base = NULL_RTX; 1045169689Skan iv->step = NULL_RTX; 1046169689Skan 1047169689Skan set = single_set (insn); 1048169689Skan if (!set || SET_DEST (set) != reg) 1049169689Skan return false; 1050169689Skan 1051169689Skan rhs = find_reg_equal_equiv_note (insn); 1052169689Skan if (rhs) 1053169689Skan rhs = XEXP (rhs, 0); 1054169689Skan else 1055169689Skan rhs = SET_SRC (set); 1056169689Skan 1057169689Skan iv_analyze_expr (insn, rhs, GET_MODE (reg), iv); 1058169689Skan record_iv (def, iv); 1059169689Skan 1060169689Skan if (dump_file) 1061169689Skan { 1062169689Skan print_rtl (dump_file, reg); 1063169689Skan fprintf (dump_file, " in insn "); 1064169689Skan print_rtl_single (dump_file, insn); 1065169689Skan fprintf (dump_file, " is "); 1066169689Skan dump_iv_info (dump_file, iv); 1067169689Skan fprintf (dump_file, "\n"); 1068169689Skan } 1069169689Skan 1070169689Skan return iv->base != NULL_RTX; 1071169689Skan} 1072169689Skan 1073169689Skan/* Analyzes operand OP of INSN and stores the result to *IV. */ 1074169689Skan 1075169689Skanstatic bool 1076169689Skaniv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) 1077169689Skan{ 1078169689Skan struct df_ref *def = NULL; 1079169689Skan enum iv_grd_result res; 1080169689Skan 1081169689Skan if (dump_file) 1082169689Skan { 1083169689Skan fprintf (dump_file, "Analysing operand "); 1084169689Skan print_rtl (dump_file, op); 1085169689Skan fprintf (dump_file, " of insn "); 1086169689Skan print_rtl_single (dump_file, insn); 1087169689Skan } 1088169689Skan 1089169689Skan if (CONSTANT_P (op)) 1090169689Skan res = GRD_INVARIANT; 1091169689Skan else if (GET_CODE (op) == SUBREG) 1092169689Skan { 1093169689Skan if (!subreg_lowpart_p (op)) 1094169689Skan return false; 1095169689Skan 1096169689Skan if (!iv_analyze_op (insn, SUBREG_REG (op), iv)) 1097169689Skan return false; 1098169689Skan 1099169689Skan return iv_subreg (iv, GET_MODE (op)); 1100169689Skan } 1101169689Skan else 1102169689Skan { 1103169689Skan res = iv_get_reaching_def (insn, op, &def); 1104169689Skan if (res == GRD_INVALID) 1105169689Skan { 1106169689Skan if (dump_file) 1107169689Skan fprintf (dump_file, " not simple.\n"); 1108169689Skan return false; 1109169689Skan } 1110169689Skan } 1111169689Skan 1112169689Skan if (res == GRD_INVARIANT) 1113169689Skan { 1114169689Skan iv_constant (iv, op, VOIDmode); 1115169689Skan 1116169689Skan if (dump_file) 1117169689Skan { 1118169689Skan fprintf (dump_file, " "); 1119169689Skan dump_iv_info (dump_file, iv); 1120169689Skan fprintf (dump_file, "\n"); 1121169689Skan } 1122169689Skan return true; 1123169689Skan } 1124169689Skan 1125169689Skan if (res == GRD_MAYBE_BIV) 1126169689Skan return iv_analyze_biv (op, iv); 1127169689Skan 1128169689Skan return iv_analyze_def (def, iv); 1129169689Skan} 1130169689Skan 1131169689Skan/* Analyzes value VAL at INSN and stores the result to *IV. */ 1132169689Skan 1133169689Skanbool 1134169689Skaniv_analyze (rtx insn, rtx val, struct rtx_iv *iv) 1135169689Skan{ 1136169689Skan rtx reg; 1137169689Skan 1138169689Skan /* We must find the insn in that val is used, so that we get to UD chains. 1139169689Skan Since the function is sometimes called on result of get_condition, 1140169689Skan this does not necessarily have to be directly INSN; scan also the 1141169689Skan following insns. */ 1142169689Skan if (simple_reg_p (val)) 1143169689Skan { 1144169689Skan if (GET_CODE (val) == SUBREG) 1145169689Skan reg = SUBREG_REG (val); 1146169689Skan else 1147169689Skan reg = val; 1148169689Skan 1149169689Skan while (!df_find_use (df, insn, reg)) 1150169689Skan insn = NEXT_INSN (insn); 1151169689Skan } 1152169689Skan 1153169689Skan return iv_analyze_op (insn, val, iv); 1154169689Skan} 1155169689Skan 1156169689Skan/* Analyzes definition of DEF in INSN and stores the result to IV. */ 1157169689Skan 1158169689Skanbool 1159169689Skaniv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv) 1160169689Skan{ 1161169689Skan struct df_ref *adef; 1162169689Skan 1163169689Skan adef = df_find_def (df, insn, def); 1164169689Skan if (!adef) 1165169689Skan return false; 1166169689Skan 1167169689Skan return iv_analyze_def (adef, iv); 1168169689Skan} 1169169689Skan 1170169689Skan/* Checks whether definition of register REG in INSN is a basic induction 1171169689Skan variable. IV analysis must have been initialized (via a call to 1172169689Skan iv_analysis_loop_init) for this function to produce a result. */ 1173169689Skan 1174169689Skanbool 1175169689Skanbiv_p (rtx insn, rtx reg) 1176169689Skan{ 1177169689Skan struct rtx_iv iv; 1178169689Skan struct df_ref *def, *last_def; 1179169689Skan 1180169689Skan if (!simple_reg_p (reg)) 1181169689Skan return false; 1182169689Skan 1183169689Skan def = df_find_def (df, insn, reg); 1184169689Skan gcc_assert (def != NULL); 1185169689Skan if (!latch_dominating_def (reg, &last_def)) 1186169689Skan return false; 1187169689Skan if (last_def != def) 1188169689Skan return false; 1189169689Skan 1190169689Skan if (!iv_analyze_biv (reg, &iv)) 1191169689Skan return false; 1192169689Skan 1193169689Skan return iv.step != const0_rtx; 1194169689Skan} 1195169689Skan 1196169689Skan/* Calculates value of IV at ITERATION-th iteration. */ 1197169689Skan 1198169689Skanrtx 1199169689Skanget_iv_value (struct rtx_iv *iv, rtx iteration) 1200169689Skan{ 1201169689Skan rtx val; 1202169689Skan 1203169689Skan /* We would need to generate some if_then_else patterns, and so far 1204169689Skan it is not needed anywhere. */ 1205169689Skan gcc_assert (!iv->first_special); 1206169689Skan 1207169689Skan if (iv->step != const0_rtx && iteration != const0_rtx) 1208169689Skan val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base, 1209169689Skan simplify_gen_binary (MULT, iv->extend_mode, 1210169689Skan iv->step, iteration)); 1211169689Skan else 1212169689Skan val = iv->base; 1213169689Skan 1214169689Skan if (iv->extend_mode == iv->mode) 1215169689Skan return val; 1216169689Skan 1217169689Skan val = lowpart_subreg (iv->mode, val, iv->extend_mode); 1218169689Skan 1219169689Skan if (iv->extend == UNKNOWN) 1220169689Skan return val; 1221169689Skan 1222169689Skan val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode); 1223169689Skan val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta, 1224169689Skan simplify_gen_binary (MULT, iv->extend_mode, 1225169689Skan iv->mult, val)); 1226169689Skan 1227169689Skan return val; 1228169689Skan} 1229169689Skan 1230169689Skan/* Free the data for an induction variable analysis. */ 1231169689Skan 1232169689Skanvoid 1233169689Skaniv_analysis_done (void) 1234169689Skan{ 1235169689Skan if (df) 1236169689Skan { 1237169689Skan clear_iv_info (); 1238169689Skan df_finish (df); 1239169689Skan df = NULL; 1240169689Skan htab_delete (bivs); 1241169689Skan bivs = NULL; 1242169689Skan } 1243169689Skan} 1244169689Skan 1245169689Skan/* Computes inverse to X modulo (1 << MOD). */ 1246169689Skan 1247169689Skanstatic unsigned HOST_WIDEST_INT 1248169689Skaninverse (unsigned HOST_WIDEST_INT x, int mod) 1249169689Skan{ 1250169689Skan unsigned HOST_WIDEST_INT mask = 1251169689Skan ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1; 1252169689Skan unsigned HOST_WIDEST_INT rslt = 1; 1253169689Skan int i; 1254169689Skan 1255169689Skan for (i = 0; i < mod - 1; i++) 1256169689Skan { 1257169689Skan rslt = (rslt * x) & mask; 1258169689Skan x = (x * x) & mask; 1259169689Skan } 1260169689Skan 1261169689Skan return rslt; 1262169689Skan} 1263169689Skan 1264169689Skan/* Tries to estimate the maximum number of iterations. */ 1265169689Skan 1266169689Skanstatic unsigned HOST_WIDEST_INT 1267169689Skandetermine_max_iter (struct niter_desc *desc) 1268169689Skan{ 1269169689Skan rtx niter = desc->niter_expr; 1270169689Skan rtx mmin, mmax, left, right; 1271169689Skan unsigned HOST_WIDEST_INT nmax, inc; 1272169689Skan 1273169689Skan if (GET_CODE (niter) == AND 1274169689Skan && GET_CODE (XEXP (niter, 0)) == CONST_INT) 1275169689Skan { 1276169689Skan nmax = INTVAL (XEXP (niter, 0)); 1277169689Skan if (!(nmax & (nmax + 1))) 1278169689Skan { 1279169689Skan desc->niter_max = nmax; 1280169689Skan return nmax; 1281169689Skan } 1282169689Skan } 1283169689Skan 1284169689Skan get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); 1285169689Skan nmax = INTVAL (mmax) - INTVAL (mmin); 1286169689Skan 1287169689Skan if (GET_CODE (niter) == UDIV) 1288169689Skan { 1289169689Skan if (GET_CODE (XEXP (niter, 1)) != CONST_INT) 1290169689Skan { 1291169689Skan desc->niter_max = nmax; 1292169689Skan return nmax; 1293169689Skan } 1294169689Skan inc = INTVAL (XEXP (niter, 1)); 1295169689Skan niter = XEXP (niter, 0); 1296169689Skan } 1297169689Skan else 1298169689Skan inc = 1; 1299169689Skan 1300169689Skan if (GET_CODE (niter) == PLUS) 1301169689Skan { 1302169689Skan left = XEXP (niter, 0); 1303169689Skan right = XEXP (niter, 0); 1304169689Skan 1305169689Skan if (GET_CODE (right) == CONST_INT) 1306169689Skan right = GEN_INT (-INTVAL (right)); 1307169689Skan } 1308169689Skan else if (GET_CODE (niter) == MINUS) 1309169689Skan { 1310169689Skan left = XEXP (niter, 0); 1311169689Skan right = XEXP (niter, 0); 1312169689Skan } 1313169689Skan else 1314169689Skan { 1315169689Skan left = niter; 1316169689Skan right = mmin; 1317169689Skan } 1318169689Skan 1319169689Skan if (GET_CODE (left) == CONST_INT) 1320169689Skan mmax = left; 1321169689Skan if (GET_CODE (right) == CONST_INT) 1322169689Skan mmin = right; 1323169689Skan nmax = INTVAL (mmax) - INTVAL (mmin); 1324169689Skan 1325169689Skan desc->niter_max = nmax / inc; 1326169689Skan return nmax / inc; 1327169689Skan} 1328169689Skan 1329169689Skan/* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */ 1330169689Skan 1331169689Skanstatic int 1332169689Skanaltered_reg_used (rtx *reg, void *alt) 1333169689Skan{ 1334169689Skan if (!REG_P (*reg)) 1335169689Skan return 0; 1336169689Skan 1337169689Skan return REGNO_REG_SET_P (alt, REGNO (*reg)); 1338169689Skan} 1339169689Skan 1340169689Skan/* Marks registers altered by EXPR in set ALT. */ 1341169689Skan 1342169689Skanstatic void 1343169689Skanmark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt) 1344169689Skan{ 1345169689Skan if (GET_CODE (expr) == SUBREG) 1346169689Skan expr = SUBREG_REG (expr); 1347169689Skan if (!REG_P (expr)) 1348169689Skan return; 1349169689Skan 1350169689Skan SET_REGNO_REG_SET (alt, REGNO (expr)); 1351169689Skan} 1352169689Skan 1353169689Skan/* Checks whether RHS is simple enough to process. */ 1354169689Skan 1355169689Skanstatic bool 1356169689Skansimple_rhs_p (rtx rhs) 1357169689Skan{ 1358169689Skan rtx op0, op1; 1359169689Skan 1360169689Skan if (CONSTANT_P (rhs) 1361169689Skan || REG_P (rhs)) 1362169689Skan return true; 1363169689Skan 1364169689Skan switch (GET_CODE (rhs)) 1365169689Skan { 1366169689Skan case PLUS: 1367169689Skan case MINUS: 1368169689Skan op0 = XEXP (rhs, 0); 1369169689Skan op1 = XEXP (rhs, 1); 1370169689Skan /* Allow reg + const sets only. */ 1371169689Skan if (REG_P (op0) && CONSTANT_P (op1)) 1372169689Skan return true; 1373169689Skan if (REG_P (op1) && CONSTANT_P (op0)) 1374169689Skan return true; 1375169689Skan 1376169689Skan return false; 1377169689Skan 1378169689Skan default: 1379169689Skan return false; 1380169689Skan } 1381169689Skan} 1382169689Skan 1383169689Skan/* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers 1384169689Skan altered so far. */ 1385169689Skan 1386169689Skanstatic void 1387169689Skansimplify_using_assignment (rtx insn, rtx *expr, regset altered) 1388169689Skan{ 1389169689Skan rtx set = single_set (insn); 1390169689Skan rtx lhs = NULL_RTX, rhs; 1391169689Skan bool ret = false; 1392169689Skan 1393169689Skan if (set) 1394169689Skan { 1395169689Skan lhs = SET_DEST (set); 1396169689Skan if (!REG_P (lhs) 1397169689Skan || altered_reg_used (&lhs, altered)) 1398169689Skan ret = true; 1399169689Skan } 1400169689Skan else 1401169689Skan ret = true; 1402169689Skan 1403169689Skan note_stores (PATTERN (insn), mark_altered, altered); 1404169689Skan if (CALL_P (insn)) 1405169689Skan { 1406169689Skan int i; 1407169689Skan 1408169689Skan /* Kill all call clobbered registers. */ 1409169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1410169689Skan if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1411169689Skan SET_REGNO_REG_SET (altered, i); 1412169689Skan } 1413169689Skan 1414169689Skan if (ret) 1415169689Skan return; 1416169689Skan 1417169689Skan rhs = find_reg_equal_equiv_note (insn); 1418169689Skan if (rhs) 1419169689Skan rhs = XEXP (rhs, 0); 1420169689Skan else 1421169689Skan rhs = SET_SRC (set); 1422169689Skan 1423169689Skan if (!simple_rhs_p (rhs)) 1424169689Skan return; 1425169689Skan 1426169689Skan if (for_each_rtx (&rhs, altered_reg_used, altered)) 1427169689Skan return; 1428169689Skan 1429169689Skan *expr = simplify_replace_rtx (*expr, lhs, rhs); 1430169689Skan} 1431169689Skan 1432169689Skan/* Checks whether A implies B. */ 1433169689Skan 1434169689Skanstatic bool 1435169689Skanimplies_p (rtx a, rtx b) 1436169689Skan{ 1437169689Skan rtx op0, op1, opb0, opb1, r; 1438169689Skan enum machine_mode mode; 1439169689Skan 1440169689Skan if (GET_CODE (a) == EQ) 1441169689Skan { 1442169689Skan op0 = XEXP (a, 0); 1443169689Skan op1 = XEXP (a, 1); 1444169689Skan 1445169689Skan if (REG_P (op0)) 1446169689Skan { 1447169689Skan r = simplify_replace_rtx (b, op0, op1); 1448169689Skan if (r == const_true_rtx) 1449169689Skan return true; 1450169689Skan } 1451169689Skan 1452169689Skan if (REG_P (op1)) 1453169689Skan { 1454169689Skan r = simplify_replace_rtx (b, op1, op0); 1455169689Skan if (r == const_true_rtx) 1456169689Skan return true; 1457169689Skan } 1458169689Skan } 1459169689Skan 1460169689Skan /* A < B implies A + 1 <= B. */ 1461169689Skan if ((GET_CODE (a) == GT || GET_CODE (a) == LT) 1462169689Skan && (GET_CODE (b) == GE || GET_CODE (b) == LE)) 1463169689Skan { 1464169689Skan op0 = XEXP (a, 0); 1465169689Skan op1 = XEXP (a, 1); 1466169689Skan opb0 = XEXP (b, 0); 1467169689Skan opb1 = XEXP (b, 1); 1468169689Skan 1469169689Skan if (GET_CODE (a) == GT) 1470169689Skan { 1471169689Skan r = op0; 1472169689Skan op0 = op1; 1473169689Skan op1 = r; 1474169689Skan } 1475169689Skan 1476169689Skan if (GET_CODE (b) == GE) 1477169689Skan { 1478169689Skan r = opb0; 1479169689Skan opb0 = opb1; 1480169689Skan opb1 = r; 1481169689Skan } 1482169689Skan 1483169689Skan mode = GET_MODE (op0); 1484169689Skan if (mode != GET_MODE (opb0)) 1485169689Skan mode = VOIDmode; 1486169689Skan else if (mode == VOIDmode) 1487169689Skan { 1488169689Skan mode = GET_MODE (op1); 1489169689Skan if (mode != GET_MODE (opb1)) 1490169689Skan mode = VOIDmode; 1491169689Skan } 1492169689Skan 1493171825Skan if (SCALAR_INT_MODE_P (mode) 1494169689Skan && rtx_equal_p (op1, opb1) 1495169689Skan && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx) 1496169689Skan return true; 1497169689Skan } 1498169689Skan 1499169689Skan return false; 1500169689Skan} 1501169689Skan 1502169689Skan/* Canonicalizes COND so that 1503169689Skan 1504169689Skan (1) Ensure that operands are ordered according to 1505169689Skan swap_commutative_operands_p. 1506169689Skan (2) (LE x const) will be replaced with (LT x <const+1>) and similarly 1507169689Skan for GE, GEU, and LEU. */ 1508169689Skan 1509169689Skanrtx 1510169689Skancanon_condition (rtx cond) 1511169689Skan{ 1512169689Skan rtx tem; 1513169689Skan rtx op0, op1; 1514169689Skan enum rtx_code code; 1515169689Skan enum machine_mode mode; 1516169689Skan 1517169689Skan code = GET_CODE (cond); 1518169689Skan op0 = XEXP (cond, 0); 1519169689Skan op1 = XEXP (cond, 1); 1520169689Skan 1521169689Skan if (swap_commutative_operands_p (op0, op1)) 1522169689Skan { 1523169689Skan code = swap_condition (code); 1524169689Skan tem = op0; 1525169689Skan op0 = op1; 1526169689Skan op1 = tem; 1527169689Skan } 1528169689Skan 1529169689Skan mode = GET_MODE (op0); 1530169689Skan if (mode == VOIDmode) 1531169689Skan mode = GET_MODE (op1); 1532169689Skan gcc_assert (mode != VOIDmode); 1533169689Skan 1534169689Skan if (GET_CODE (op1) == CONST_INT 1535169689Skan && GET_MODE_CLASS (mode) != MODE_CC 1536169689Skan && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT) 1537169689Skan { 1538169689Skan HOST_WIDE_INT const_val = INTVAL (op1); 1539169689Skan unsigned HOST_WIDE_INT uconst_val = const_val; 1540169689Skan unsigned HOST_WIDE_INT max_val 1541169689Skan = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode); 1542169689Skan 1543169689Skan switch (code) 1544169689Skan { 1545169689Skan case LE: 1546169689Skan if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1) 1547169689Skan code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0)); 1548169689Skan break; 1549169689Skan 1550169689Skan /* When cross-compiling, const_val might be sign-extended from 1551169689Skan BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */ 1552169689Skan case GE: 1553169689Skan if ((HOST_WIDE_INT) (const_val & max_val) 1554169689Skan != (((HOST_WIDE_INT) 1 1555169689Skan << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1)))) 1556169689Skan code = GT, op1 = gen_int_mode (const_val - 1, mode); 1557169689Skan break; 1558169689Skan 1559169689Skan case LEU: 1560169689Skan if (uconst_val < max_val) 1561169689Skan code = LTU, op1 = gen_int_mode (uconst_val + 1, mode); 1562169689Skan break; 1563169689Skan 1564169689Skan case GEU: 1565169689Skan if (uconst_val != 0) 1566169689Skan code = GTU, op1 = gen_int_mode (uconst_val - 1, mode); 1567169689Skan break; 1568169689Skan 1569169689Skan default: 1570169689Skan break; 1571169689Skan } 1572169689Skan } 1573169689Skan 1574169689Skan if (op0 != XEXP (cond, 0) 1575169689Skan || op1 != XEXP (cond, 1) 1576169689Skan || code != GET_CODE (cond) 1577169689Skan || GET_MODE (cond) != SImode) 1578169689Skan cond = gen_rtx_fmt_ee (code, SImode, op0, op1); 1579169689Skan 1580169689Skan return cond; 1581169689Skan} 1582169689Skan 1583169689Skan/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the 1584169689Skan set of altered regs. */ 1585169689Skan 1586169689Skanvoid 1587169689Skansimplify_using_condition (rtx cond, rtx *expr, regset altered) 1588169689Skan{ 1589169689Skan rtx rev, reve, exp = *expr; 1590169689Skan 1591169689Skan if (!COMPARISON_P (exp)) 1592169689Skan return; 1593169689Skan 1594169689Skan /* If some register gets altered later, we do not really speak about its 1595169689Skan value at the time of comparison. */ 1596169689Skan if (altered 1597169689Skan && for_each_rtx (&cond, altered_reg_used, altered)) 1598169689Skan return; 1599169689Skan 1600169689Skan rev = reversed_condition (cond); 1601169689Skan reve = reversed_condition (exp); 1602169689Skan 1603169689Skan cond = canon_condition (cond); 1604169689Skan exp = canon_condition (exp); 1605169689Skan if (rev) 1606169689Skan rev = canon_condition (rev); 1607169689Skan if (reve) 1608169689Skan reve = canon_condition (reve); 1609169689Skan 1610169689Skan if (rtx_equal_p (exp, cond)) 1611169689Skan { 1612169689Skan *expr = const_true_rtx; 1613169689Skan return; 1614169689Skan } 1615169689Skan 1616169689Skan 1617169689Skan if (rev && rtx_equal_p (exp, rev)) 1618169689Skan { 1619169689Skan *expr = const0_rtx; 1620169689Skan return; 1621169689Skan } 1622169689Skan 1623169689Skan if (implies_p (cond, exp)) 1624169689Skan { 1625169689Skan *expr = const_true_rtx; 1626169689Skan return; 1627169689Skan } 1628169689Skan 1629169689Skan if (reve && implies_p (cond, reve)) 1630169689Skan { 1631169689Skan *expr = const0_rtx; 1632169689Skan return; 1633169689Skan } 1634169689Skan 1635169689Skan /* A proof by contradiction. If *EXPR implies (not cond), *EXPR must 1636169689Skan be false. */ 1637169689Skan if (rev && implies_p (exp, rev)) 1638169689Skan { 1639169689Skan *expr = const0_rtx; 1640169689Skan return; 1641169689Skan } 1642169689Skan 1643169689Skan /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */ 1644169689Skan if (rev && reve && implies_p (reve, rev)) 1645169689Skan { 1646169689Skan *expr = const_true_rtx; 1647169689Skan return; 1648169689Skan } 1649169689Skan 1650169689Skan /* We would like to have some other tests here. TODO. */ 1651169689Skan 1652169689Skan return; 1653169689Skan} 1654169689Skan 1655169689Skan/* Use relationship between A and *B to eventually eliminate *B. 1656169689Skan OP is the operation we consider. */ 1657169689Skan 1658169689Skanstatic void 1659169689Skaneliminate_implied_condition (enum rtx_code op, rtx a, rtx *b) 1660169689Skan{ 1661169689Skan switch (op) 1662169689Skan { 1663169689Skan case AND: 1664169689Skan /* If A implies *B, we may replace *B by true. */ 1665169689Skan if (implies_p (a, *b)) 1666169689Skan *b = const_true_rtx; 1667169689Skan break; 1668169689Skan 1669169689Skan case IOR: 1670169689Skan /* If *B implies A, we may replace *B by false. */ 1671169689Skan if (implies_p (*b, a)) 1672169689Skan *b = const0_rtx; 1673169689Skan break; 1674169689Skan 1675169689Skan default: 1676169689Skan gcc_unreachable (); 1677169689Skan } 1678169689Skan} 1679169689Skan 1680169689Skan/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the 1681169689Skan operation we consider. */ 1682169689Skan 1683169689Skanstatic void 1684169689Skaneliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail) 1685169689Skan{ 1686169689Skan rtx elt; 1687169689Skan 1688169689Skan for (elt = tail; elt; elt = XEXP (elt, 1)) 1689169689Skan eliminate_implied_condition (op, *head, &XEXP (elt, 0)); 1690169689Skan for (elt = tail; elt; elt = XEXP (elt, 1)) 1691169689Skan eliminate_implied_condition (op, XEXP (elt, 0), head); 1692169689Skan} 1693169689Skan 1694169689Skan/* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR 1695169689Skan is a list, its elements are assumed to be combined using OP. */ 1696169689Skan 1697169689Skanstatic void 1698169689Skansimplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) 1699169689Skan{ 1700169689Skan rtx head, tail, insn; 1701169689Skan rtx neutral, aggr; 1702169689Skan regset altered; 1703169689Skan edge e; 1704169689Skan 1705169689Skan if (!*expr) 1706169689Skan return; 1707169689Skan 1708169689Skan if (CONSTANT_P (*expr)) 1709169689Skan return; 1710169689Skan 1711169689Skan if (GET_CODE (*expr) == EXPR_LIST) 1712169689Skan { 1713169689Skan head = XEXP (*expr, 0); 1714169689Skan tail = XEXP (*expr, 1); 1715169689Skan 1716169689Skan eliminate_implied_conditions (op, &head, tail); 1717169689Skan 1718169689Skan switch (op) 1719169689Skan { 1720169689Skan case AND: 1721169689Skan neutral = const_true_rtx; 1722169689Skan aggr = const0_rtx; 1723169689Skan break; 1724169689Skan 1725169689Skan case IOR: 1726169689Skan neutral = const0_rtx; 1727169689Skan aggr = const_true_rtx; 1728169689Skan break; 1729169689Skan 1730169689Skan default: 1731169689Skan gcc_unreachable (); 1732169689Skan } 1733169689Skan 1734169689Skan simplify_using_initial_values (loop, UNKNOWN, &head); 1735169689Skan if (head == aggr) 1736169689Skan { 1737169689Skan XEXP (*expr, 0) = aggr; 1738169689Skan XEXP (*expr, 1) = NULL_RTX; 1739169689Skan return; 1740169689Skan } 1741169689Skan else if (head == neutral) 1742169689Skan { 1743169689Skan *expr = tail; 1744169689Skan simplify_using_initial_values (loop, op, expr); 1745169689Skan return; 1746169689Skan } 1747169689Skan simplify_using_initial_values (loop, op, &tail); 1748169689Skan 1749169689Skan if (tail && XEXP (tail, 0) == aggr) 1750169689Skan { 1751169689Skan *expr = tail; 1752169689Skan return; 1753169689Skan } 1754169689Skan 1755169689Skan XEXP (*expr, 0) = head; 1756169689Skan XEXP (*expr, 1) = tail; 1757169689Skan return; 1758169689Skan } 1759169689Skan 1760169689Skan gcc_assert (op == UNKNOWN); 1761169689Skan 1762169689Skan e = loop_preheader_edge (loop); 1763169689Skan if (e->src == ENTRY_BLOCK_PTR) 1764169689Skan return; 1765169689Skan 1766169689Skan altered = ALLOC_REG_SET (®_obstack); 1767169689Skan 1768169689Skan while (1) 1769169689Skan { 1770169689Skan insn = BB_END (e->src); 1771169689Skan if (any_condjump_p (insn)) 1772169689Skan { 1773169689Skan rtx cond = get_condition (BB_END (e->src), NULL, false, true); 1774169689Skan 1775169689Skan if (cond && (e->flags & EDGE_FALLTHRU)) 1776169689Skan cond = reversed_condition (cond); 1777169689Skan if (cond) 1778169689Skan { 1779169689Skan simplify_using_condition (cond, expr, altered); 1780169689Skan if (CONSTANT_P (*expr)) 1781169689Skan { 1782169689Skan FREE_REG_SET (altered); 1783169689Skan return; 1784169689Skan } 1785169689Skan } 1786169689Skan } 1787169689Skan 1788169689Skan FOR_BB_INSNS_REVERSE (e->src, insn) 1789169689Skan { 1790169689Skan if (!INSN_P (insn)) 1791169689Skan continue; 1792169689Skan 1793169689Skan simplify_using_assignment (insn, expr, altered); 1794169689Skan if (CONSTANT_P (*expr)) 1795169689Skan { 1796169689Skan FREE_REG_SET (altered); 1797169689Skan return; 1798169689Skan } 1799169689Skan } 1800169689Skan 1801169689Skan if (!single_pred_p (e->src) 1802169689Skan || single_pred (e->src) == ENTRY_BLOCK_PTR) 1803169689Skan break; 1804169689Skan e = single_pred_edge (e->src); 1805169689Skan } 1806169689Skan 1807169689Skan FREE_REG_SET (altered); 1808169689Skan} 1809169689Skan 1810169689Skan/* Transforms invariant IV into MODE. Adds assumptions based on the fact 1811169689Skan that IV occurs as left operands of comparison COND and its signedness 1812169689Skan is SIGNED_P to DESC. */ 1813169689Skan 1814169689Skanstatic void 1815169689Skanshorten_into_mode (struct rtx_iv *iv, enum machine_mode mode, 1816169689Skan enum rtx_code cond, bool signed_p, struct niter_desc *desc) 1817169689Skan{ 1818169689Skan rtx mmin, mmax, cond_over, cond_under; 1819169689Skan 1820169689Skan get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax); 1821169689Skan cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode, 1822169689Skan iv->base, mmin); 1823169689Skan cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode, 1824169689Skan iv->base, mmax); 1825169689Skan 1826169689Skan switch (cond) 1827169689Skan { 1828169689Skan case LE: 1829169689Skan case LT: 1830169689Skan case LEU: 1831169689Skan case LTU: 1832169689Skan if (cond_under != const0_rtx) 1833169689Skan desc->infinite = 1834169689Skan alloc_EXPR_LIST (0, cond_under, desc->infinite); 1835169689Skan if (cond_over != const0_rtx) 1836169689Skan desc->noloop_assumptions = 1837169689Skan alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions); 1838169689Skan break; 1839169689Skan 1840169689Skan case GE: 1841169689Skan case GT: 1842169689Skan case GEU: 1843169689Skan case GTU: 1844169689Skan if (cond_over != const0_rtx) 1845169689Skan desc->infinite = 1846169689Skan alloc_EXPR_LIST (0, cond_over, desc->infinite); 1847169689Skan if (cond_under != const0_rtx) 1848169689Skan desc->noloop_assumptions = 1849169689Skan alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions); 1850169689Skan break; 1851169689Skan 1852169689Skan case NE: 1853169689Skan if (cond_over != const0_rtx) 1854169689Skan desc->infinite = 1855169689Skan alloc_EXPR_LIST (0, cond_over, desc->infinite); 1856169689Skan if (cond_under != const0_rtx) 1857169689Skan desc->infinite = 1858169689Skan alloc_EXPR_LIST (0, cond_under, desc->infinite); 1859169689Skan break; 1860169689Skan 1861169689Skan default: 1862169689Skan gcc_unreachable (); 1863169689Skan } 1864169689Skan 1865169689Skan iv->mode = mode; 1866169689Skan iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND; 1867169689Skan} 1868169689Skan 1869169689Skan/* Transforms IV0 and IV1 compared by COND so that they are both compared as 1870169689Skan subregs of the same mode if possible (sometimes it is necessary to add 1871169689Skan some assumptions to DESC). */ 1872169689Skan 1873169689Skanstatic bool 1874169689Skancanonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, 1875169689Skan enum rtx_code cond, struct niter_desc *desc) 1876169689Skan{ 1877169689Skan enum machine_mode comp_mode; 1878169689Skan bool signed_p; 1879169689Skan 1880169689Skan /* If the ivs behave specially in the first iteration, or are 1881169689Skan added/multiplied after extending, we ignore them. */ 1882169689Skan if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx) 1883169689Skan return false; 1884169689Skan if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx) 1885169689Skan return false; 1886169689Skan 1887169689Skan /* If there is some extend, it must match signedness of the comparison. */ 1888169689Skan switch (cond) 1889169689Skan { 1890169689Skan case LE: 1891169689Skan case LT: 1892169689Skan if (iv0->extend == ZERO_EXTEND 1893169689Skan || iv1->extend == ZERO_EXTEND) 1894169689Skan return false; 1895169689Skan signed_p = true; 1896169689Skan break; 1897169689Skan 1898169689Skan case LEU: 1899169689Skan case LTU: 1900169689Skan if (iv0->extend == SIGN_EXTEND 1901169689Skan || iv1->extend == SIGN_EXTEND) 1902169689Skan return false; 1903169689Skan signed_p = false; 1904169689Skan break; 1905169689Skan 1906169689Skan case NE: 1907169689Skan if (iv0->extend != UNKNOWN 1908169689Skan && iv1->extend != UNKNOWN 1909169689Skan && iv0->extend != iv1->extend) 1910169689Skan return false; 1911169689Skan 1912169689Skan signed_p = false; 1913169689Skan if (iv0->extend != UNKNOWN) 1914169689Skan signed_p = iv0->extend == SIGN_EXTEND; 1915169689Skan if (iv1->extend != UNKNOWN) 1916169689Skan signed_p = iv1->extend == SIGN_EXTEND; 1917169689Skan break; 1918169689Skan 1919169689Skan default: 1920169689Skan gcc_unreachable (); 1921169689Skan } 1922169689Skan 1923169689Skan /* Values of both variables should be computed in the same mode. These 1924169689Skan might indeed be different, if we have comparison like 1925169689Skan 1926169689Skan (compare (subreg:SI (iv0)) (subreg:SI (iv1))) 1927169689Skan 1928169689Skan and iv0 and iv1 are both ivs iterating in SI mode, but calculated 1929169689Skan in different modes. This does not seem impossible to handle, but 1930169689Skan it hardly ever occurs in practice. 1931169689Skan 1932169689Skan The only exception is the case when one of operands is invariant. 1933169689Skan For example pentium 3 generates comparisons like 1934169689Skan (lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we 1935169689Skan definitely do not want this prevent the optimization. */ 1936169689Skan comp_mode = iv0->extend_mode; 1937169689Skan if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode)) 1938169689Skan comp_mode = iv1->extend_mode; 1939169689Skan 1940169689Skan if (iv0->extend_mode != comp_mode) 1941169689Skan { 1942169689Skan if (iv0->mode != iv0->extend_mode 1943169689Skan || iv0->step != const0_rtx) 1944169689Skan return false; 1945169689Skan 1946169689Skan iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 1947169689Skan comp_mode, iv0->base, iv0->mode); 1948169689Skan iv0->extend_mode = comp_mode; 1949169689Skan } 1950169689Skan 1951169689Skan if (iv1->extend_mode != comp_mode) 1952169689Skan { 1953169689Skan if (iv1->mode != iv1->extend_mode 1954169689Skan || iv1->step != const0_rtx) 1955169689Skan return false; 1956169689Skan 1957169689Skan iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND, 1958169689Skan comp_mode, iv1->base, iv1->mode); 1959169689Skan iv1->extend_mode = comp_mode; 1960169689Skan } 1961169689Skan 1962169689Skan /* Check that both ivs belong to a range of a single mode. If one of the 1963169689Skan operands is an invariant, we may need to shorten it into the common 1964169689Skan mode. */ 1965169689Skan if (iv0->mode == iv0->extend_mode 1966169689Skan && iv0->step == const0_rtx 1967169689Skan && iv0->mode != iv1->mode) 1968169689Skan shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc); 1969169689Skan 1970169689Skan if (iv1->mode == iv1->extend_mode 1971169689Skan && iv1->step == const0_rtx 1972169689Skan && iv0->mode != iv1->mode) 1973169689Skan shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc); 1974169689Skan 1975169689Skan if (iv0->mode != iv1->mode) 1976169689Skan return false; 1977169689Skan 1978169689Skan desc->mode = iv0->mode; 1979169689Skan desc->signed_p = signed_p; 1980169689Skan 1981169689Skan return true; 1982169689Skan} 1983169689Skan 1984169689Skan/* Computes number of iterations of the CONDITION in INSN in LOOP and stores 1985169689Skan the result into DESC. Very similar to determine_number_of_iterations 1986169689Skan (basically its rtl version), complicated by things like subregs. */ 1987169689Skan 1988169689Skanstatic void 1989169689Skaniv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, 1990169689Skan struct niter_desc *desc) 1991169689Skan{ 1992169689Skan rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1; 1993169689Skan struct rtx_iv iv0, iv1, tmp_iv; 1994169689Skan rtx assumption, may_not_xform; 1995169689Skan enum rtx_code cond; 1996169689Skan enum machine_mode mode, comp_mode; 1997169689Skan rtx mmin, mmax, mode_mmin, mode_mmax; 1998169689Skan unsigned HOST_WIDEST_INT s, size, d, inv; 1999169689Skan HOST_WIDEST_INT up, down, inc, step_val; 2000169689Skan int was_sharp = false; 2001169689Skan rtx old_niter; 2002169689Skan bool step_is_pow2; 2003169689Skan 2004169689Skan /* The meaning of these assumptions is this: 2005169689Skan if !assumptions 2006169689Skan then the rest of information does not have to be valid 2007169689Skan if noloop_assumptions then the loop does not roll 2008169689Skan if infinite then this exit is never used */ 2009169689Skan 2010169689Skan desc->assumptions = NULL_RTX; 2011169689Skan desc->noloop_assumptions = NULL_RTX; 2012169689Skan desc->infinite = NULL_RTX; 2013169689Skan desc->simple_p = true; 2014169689Skan 2015169689Skan desc->const_iter = false; 2016169689Skan desc->niter_expr = NULL_RTX; 2017169689Skan desc->niter_max = 0; 2018169689Skan 2019169689Skan cond = GET_CODE (condition); 2020169689Skan gcc_assert (COMPARISON_P (condition)); 2021169689Skan 2022169689Skan mode = GET_MODE (XEXP (condition, 0)); 2023169689Skan if (mode == VOIDmode) 2024169689Skan mode = GET_MODE (XEXP (condition, 1)); 2025169689Skan /* The constant comparisons should be folded. */ 2026169689Skan gcc_assert (mode != VOIDmode); 2027169689Skan 2028169689Skan /* We only handle integers or pointers. */ 2029169689Skan if (GET_MODE_CLASS (mode) != MODE_INT 2030169689Skan && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT) 2031169689Skan goto fail; 2032169689Skan 2033169689Skan op0 = XEXP (condition, 0); 2034169689Skan if (!iv_analyze (insn, op0, &iv0)) 2035169689Skan goto fail; 2036169689Skan if (iv0.extend_mode == VOIDmode) 2037169689Skan iv0.mode = iv0.extend_mode = mode; 2038169689Skan 2039169689Skan op1 = XEXP (condition, 1); 2040169689Skan if (!iv_analyze (insn, op1, &iv1)) 2041169689Skan goto fail; 2042169689Skan if (iv1.extend_mode == VOIDmode) 2043169689Skan iv1.mode = iv1.extend_mode = mode; 2044169689Skan 2045169689Skan if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT 2046169689Skan || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT) 2047169689Skan goto fail; 2048169689Skan 2049169689Skan /* Check condition and normalize it. */ 2050169689Skan 2051169689Skan switch (cond) 2052169689Skan { 2053169689Skan case GE: 2054169689Skan case GT: 2055169689Skan case GEU: 2056169689Skan case GTU: 2057169689Skan tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv; 2058169689Skan cond = swap_condition (cond); 2059169689Skan break; 2060169689Skan case NE: 2061169689Skan case LE: 2062169689Skan case LEU: 2063169689Skan case LT: 2064169689Skan case LTU: 2065169689Skan break; 2066169689Skan default: 2067169689Skan goto fail; 2068169689Skan } 2069169689Skan 2070169689Skan /* Handle extends. This is relatively nontrivial, so we only try in some 2071169689Skan easy cases, when we can canonicalize the ivs (possibly by adding some 2072169689Skan assumptions) to shape subreg (base + i * step). This function also fills 2073169689Skan in desc->mode and desc->signed_p. */ 2074169689Skan 2075169689Skan if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc)) 2076169689Skan goto fail; 2077169689Skan 2078169689Skan comp_mode = iv0.extend_mode; 2079169689Skan mode = iv0.mode; 2080169689Skan size = GET_MODE_BITSIZE (mode); 2081169689Skan get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax); 2082169689Skan mode_mmin = lowpart_subreg (mode, mmin, comp_mode); 2083169689Skan mode_mmax = lowpart_subreg (mode, mmax, comp_mode); 2084169689Skan 2085169689Skan if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT) 2086169689Skan goto fail; 2087169689Skan 2088169689Skan /* We can take care of the case of two induction variables chasing each other 2089169689Skan if the test is NE. I have never seen a loop using it, but still it is 2090169689Skan cool. */ 2091169689Skan if (iv0.step != const0_rtx && iv1.step != const0_rtx) 2092169689Skan { 2093169689Skan if (cond != NE) 2094169689Skan goto fail; 2095169689Skan 2096169689Skan iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2097169689Skan iv1.step = const0_rtx; 2098169689Skan } 2099169689Skan 2100169689Skan /* This is either infinite loop or the one that ends immediately, depending 2101169689Skan on initial values. Unswitching should remove this kind of conditions. */ 2102169689Skan if (iv0.step == const0_rtx && iv1.step == const0_rtx) 2103169689Skan goto fail; 2104169689Skan 2105169689Skan if (cond != NE) 2106169689Skan { 2107169689Skan if (iv0.step == const0_rtx) 2108169689Skan step_val = -INTVAL (iv1.step); 2109169689Skan else 2110169689Skan step_val = INTVAL (iv0.step); 2111169689Skan 2112169689Skan /* Ignore loops of while (i-- < 10) type. */ 2113169689Skan if (step_val < 0) 2114169689Skan goto fail; 2115169689Skan 2116169689Skan step_is_pow2 = !(step_val & (step_val - 1)); 2117169689Skan } 2118169689Skan else 2119169689Skan { 2120169689Skan /* We do not care about whether the step is power of two in this 2121169689Skan case. */ 2122169689Skan step_is_pow2 = false; 2123169689Skan step_val = 0; 2124169689Skan } 2125169689Skan 2126169689Skan /* Some more condition normalization. We must record some assumptions 2127169689Skan due to overflows. */ 2128169689Skan switch (cond) 2129169689Skan { 2130169689Skan case LT: 2131169689Skan case LTU: 2132169689Skan /* We want to take care only of non-sharp relationals; this is easy, 2133169689Skan as in cases the overflow would make the transformation unsafe 2134169689Skan the loop does not roll. Seemingly it would make more sense to want 2135169689Skan to take care of sharp relationals instead, as NE is more similar to 2136169689Skan them, but the problem is that here the transformation would be more 2137169689Skan difficult due to possibly infinite loops. */ 2138169689Skan if (iv0.step == const0_rtx) 2139169689Skan { 2140169689Skan tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2141169689Skan assumption = simplify_gen_relational (EQ, SImode, mode, tmp, 2142169689Skan mode_mmax); 2143169689Skan if (assumption == const_true_rtx) 2144169689Skan goto zero_iter_simplify; 2145169689Skan iv0.base = simplify_gen_binary (PLUS, comp_mode, 2146169689Skan iv0.base, const1_rtx); 2147169689Skan } 2148169689Skan else 2149169689Skan { 2150169689Skan tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2151169689Skan assumption = simplify_gen_relational (EQ, SImode, mode, tmp, 2152169689Skan mode_mmin); 2153169689Skan if (assumption == const_true_rtx) 2154169689Skan goto zero_iter_simplify; 2155169689Skan iv1.base = simplify_gen_binary (PLUS, comp_mode, 2156169689Skan iv1.base, constm1_rtx); 2157169689Skan } 2158169689Skan 2159169689Skan if (assumption != const0_rtx) 2160169689Skan desc->noloop_assumptions = 2161169689Skan alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2162169689Skan cond = (cond == LT) ? LE : LEU; 2163169689Skan 2164169689Skan /* It will be useful to be able to tell the difference once more in 2165169689Skan LE -> NE reduction. */ 2166169689Skan was_sharp = true; 2167169689Skan break; 2168169689Skan default: ; 2169169689Skan } 2170169689Skan 2171169689Skan /* Take care of trivially infinite loops. */ 2172169689Skan if (cond != NE) 2173169689Skan { 2174169689Skan if (iv0.step == const0_rtx) 2175169689Skan { 2176169689Skan tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2177169689Skan if (rtx_equal_p (tmp, mode_mmin)) 2178169689Skan { 2179169689Skan desc->infinite = 2180169689Skan alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); 2181169689Skan /* Fill in the remaining fields somehow. */ 2182169689Skan goto zero_iter_simplify; 2183169689Skan } 2184169689Skan } 2185169689Skan else 2186169689Skan { 2187169689Skan tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2188169689Skan if (rtx_equal_p (tmp, mode_mmax)) 2189169689Skan { 2190169689Skan desc->infinite = 2191169689Skan alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); 2192169689Skan /* Fill in the remaining fields somehow. */ 2193169689Skan goto zero_iter_simplify; 2194169689Skan } 2195169689Skan } 2196169689Skan } 2197169689Skan 2198169689Skan /* If we can we want to take care of NE conditions instead of size 2199169689Skan comparisons, as they are much more friendly (most importantly 2200169689Skan this takes care of special handling of loops with step 1). We can 2201169689Skan do it if we first check that upper bound is greater or equal to 2202169689Skan lower bound, their difference is constant c modulo step and that 2203169689Skan there is not an overflow. */ 2204169689Skan if (cond != NE) 2205169689Skan { 2206169689Skan if (iv0.step == const0_rtx) 2207169689Skan step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode); 2208169689Skan else 2209169689Skan step = iv0.step; 2210169689Skan delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2211169689Skan delta = lowpart_subreg (mode, delta, comp_mode); 2212169689Skan delta = simplify_gen_binary (UMOD, mode, delta, step); 2213169689Skan may_xform = const0_rtx; 2214169689Skan may_not_xform = const_true_rtx; 2215169689Skan 2216169689Skan if (GET_CODE (delta) == CONST_INT) 2217169689Skan { 2218169689Skan if (was_sharp && INTVAL (delta) == INTVAL (step) - 1) 2219169689Skan { 2220169689Skan /* A special case. We have transformed condition of type 2221169689Skan for (i = 0; i < 4; i += 4) 2222169689Skan into 2223169689Skan for (i = 0; i <= 3; i += 4) 2224169689Skan obviously if the test for overflow during that transformation 2225169689Skan passed, we cannot overflow here. Most importantly any 2226169689Skan loop with sharp end condition and step 1 falls into this 2227169689Skan category, so handling this case specially is definitely 2228169689Skan worth the troubles. */ 2229169689Skan may_xform = const_true_rtx; 2230169689Skan } 2231169689Skan else if (iv0.step == const0_rtx) 2232169689Skan { 2233169689Skan bound = simplify_gen_binary (PLUS, comp_mode, mmin, step); 2234169689Skan bound = simplify_gen_binary (MINUS, comp_mode, bound, delta); 2235169689Skan bound = lowpart_subreg (mode, bound, comp_mode); 2236169689Skan tmp = lowpart_subreg (mode, iv0.base, comp_mode); 2237169689Skan may_xform = simplify_gen_relational (cond, SImode, mode, 2238169689Skan bound, tmp); 2239169689Skan may_not_xform = simplify_gen_relational (reverse_condition (cond), 2240169689Skan SImode, mode, 2241169689Skan bound, tmp); 2242169689Skan } 2243169689Skan else 2244169689Skan { 2245169689Skan bound = simplify_gen_binary (MINUS, comp_mode, mmax, step); 2246169689Skan bound = simplify_gen_binary (PLUS, comp_mode, bound, delta); 2247169689Skan bound = lowpart_subreg (mode, bound, comp_mode); 2248169689Skan tmp = lowpart_subreg (mode, iv1.base, comp_mode); 2249169689Skan may_xform = simplify_gen_relational (cond, SImode, mode, 2250169689Skan tmp, bound); 2251169689Skan may_not_xform = simplify_gen_relational (reverse_condition (cond), 2252169689Skan SImode, mode, 2253169689Skan tmp, bound); 2254169689Skan } 2255169689Skan } 2256169689Skan 2257169689Skan if (may_xform != const0_rtx) 2258169689Skan { 2259169689Skan /* We perform the transformation always provided that it is not 2260169689Skan completely senseless. This is OK, as we would need this assumption 2261169689Skan to determine the number of iterations anyway. */ 2262169689Skan if (may_xform != const_true_rtx) 2263169689Skan { 2264169689Skan /* If the step is a power of two and the final value we have 2265169689Skan computed overflows, the cycle is infinite. Otherwise it 2266169689Skan is nontrivial to compute the number of iterations. */ 2267169689Skan if (step_is_pow2) 2268169689Skan desc->infinite = alloc_EXPR_LIST (0, may_not_xform, 2269169689Skan desc->infinite); 2270169689Skan else 2271169689Skan desc->assumptions = alloc_EXPR_LIST (0, may_xform, 2272169689Skan desc->assumptions); 2273169689Skan } 2274169689Skan 2275169689Skan /* We are going to lose some information about upper bound on 2276169689Skan number of iterations in this step, so record the information 2277169689Skan here. */ 2278169689Skan inc = INTVAL (iv0.step) - INTVAL (iv1.step); 2279169689Skan if (GET_CODE (iv1.base) == CONST_INT) 2280169689Skan up = INTVAL (iv1.base); 2281169689Skan else 2282169689Skan up = INTVAL (mode_mmax) - inc; 2283169689Skan down = INTVAL (GET_CODE (iv0.base) == CONST_INT 2284169689Skan ? iv0.base 2285169689Skan : mode_mmin); 2286169689Skan desc->niter_max = (up - down) / inc + 1; 2287169689Skan 2288169689Skan if (iv0.step == const0_rtx) 2289169689Skan { 2290169689Skan iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta); 2291169689Skan iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step); 2292169689Skan } 2293169689Skan else 2294169689Skan { 2295169689Skan iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta); 2296169689Skan iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step); 2297169689Skan } 2298169689Skan 2299169689Skan tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2300169689Skan tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2301169689Skan assumption = simplify_gen_relational (reverse_condition (cond), 2302169689Skan SImode, mode, tmp0, tmp1); 2303169689Skan if (assumption == const_true_rtx) 2304169689Skan goto zero_iter_simplify; 2305169689Skan else if (assumption != const0_rtx) 2306169689Skan desc->noloop_assumptions = 2307169689Skan alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2308169689Skan cond = NE; 2309169689Skan } 2310169689Skan } 2311169689Skan 2312169689Skan /* Count the number of iterations. */ 2313169689Skan if (cond == NE) 2314169689Skan { 2315169689Skan /* Everything we do here is just arithmetics modulo size of mode. This 2316169689Skan makes us able to do more involved computations of number of iterations 2317169689Skan than in other cases. First transform the condition into shape 2318169689Skan s * i <> c, with s positive. */ 2319169689Skan iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base); 2320169689Skan iv0.base = const0_rtx; 2321169689Skan iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step); 2322169689Skan iv1.step = const0_rtx; 2323169689Skan if (INTVAL (iv0.step) < 0) 2324169689Skan { 2325169689Skan iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode); 2326169689Skan iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode); 2327169689Skan } 2328169689Skan iv0.step = lowpart_subreg (mode, iv0.step, comp_mode); 2329169689Skan 2330169689Skan /* Let nsd (s, size of mode) = d. If d does not divide c, the loop 2331169689Skan is infinite. Otherwise, the number of iterations is 2332169689Skan (inverse(s/d) * (c/d)) mod (size of mode/d). */ 2333169689Skan s = INTVAL (iv0.step); d = 1; 2334169689Skan while (s % 2 != 1) 2335169689Skan { 2336169689Skan s /= 2; 2337169689Skan d *= 2; 2338169689Skan size--; 2339169689Skan } 2340169689Skan bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1); 2341169689Skan 2342169689Skan tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2343169689Skan tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d)); 2344169689Skan assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx); 2345169689Skan desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite); 2346169689Skan 2347169689Skan tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d)); 2348169689Skan inv = inverse (s, size); 2349169689Skan tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode)); 2350169689Skan desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound); 2351169689Skan } 2352169689Skan else 2353169689Skan { 2354169689Skan if (iv1.step == const0_rtx) 2355169689Skan /* Condition in shape a + s * i <= b 2356169689Skan We must know that b + s does not overflow and a <= b + s and then we 2357169689Skan can compute number of iterations as (b + s - a) / s. (It might 2358169689Skan seem that we in fact could be more clever about testing the b + s 2359169689Skan overflow condition using some information about b - a mod s, 2360169689Skan but it was already taken into account during LE -> NE transform). */ 2361169689Skan { 2362169689Skan step = iv0.step; 2363169689Skan tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2364169689Skan tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2365169689Skan 2366169689Skan bound = simplify_gen_binary (MINUS, mode, mode_mmax, 2367169689Skan lowpart_subreg (mode, step, 2368169689Skan comp_mode)); 2369169689Skan if (step_is_pow2) 2370169689Skan { 2371169689Skan rtx t0, t1; 2372169689Skan 2373169689Skan /* If s is power of 2, we know that the loop is infinite if 2374169689Skan a % s <= b % s and b + s overflows. */ 2375169689Skan assumption = simplify_gen_relational (reverse_condition (cond), 2376169689Skan SImode, mode, 2377169689Skan tmp1, bound); 2378169689Skan 2379169689Skan t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2380169689Skan t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2381169689Skan tmp = simplify_gen_relational (cond, SImode, mode, t0, t1); 2382169689Skan assumption = simplify_gen_binary (AND, SImode, assumption, tmp); 2383169689Skan desc->infinite = 2384169689Skan alloc_EXPR_LIST (0, assumption, desc->infinite); 2385169689Skan } 2386169689Skan else 2387169689Skan { 2388169689Skan assumption = simplify_gen_relational (cond, SImode, mode, 2389169689Skan tmp1, bound); 2390169689Skan desc->assumptions = 2391169689Skan alloc_EXPR_LIST (0, assumption, desc->assumptions); 2392169689Skan } 2393169689Skan 2394169689Skan tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step); 2395169689Skan tmp = lowpart_subreg (mode, tmp, comp_mode); 2396169689Skan assumption = simplify_gen_relational (reverse_condition (cond), 2397169689Skan SImode, mode, tmp0, tmp); 2398169689Skan 2399169689Skan delta = simplify_gen_binary (PLUS, mode, tmp1, step); 2400169689Skan delta = simplify_gen_binary (MINUS, mode, delta, tmp0); 2401169689Skan } 2402169689Skan else 2403169689Skan { 2404169689Skan /* Condition in shape a <= b - s * i 2405169689Skan We must know that a - s does not overflow and a - s <= b and then 2406169689Skan we can again compute number of iterations as (b - (a - s)) / s. */ 2407169689Skan step = simplify_gen_unary (NEG, mode, iv1.step, mode); 2408169689Skan tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); 2409169689Skan tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); 2410169689Skan 2411169689Skan bound = simplify_gen_binary (PLUS, mode, mode_mmin, 2412169689Skan lowpart_subreg (mode, step, comp_mode)); 2413169689Skan if (step_is_pow2) 2414169689Skan { 2415169689Skan rtx t0, t1; 2416169689Skan 2417169689Skan /* If s is power of 2, we know that the loop is infinite if 2418169689Skan a % s <= b % s and a - s overflows. */ 2419169689Skan assumption = simplify_gen_relational (reverse_condition (cond), 2420169689Skan SImode, mode, 2421169689Skan bound, tmp0); 2422169689Skan 2423169689Skan t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step); 2424169689Skan t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step); 2425169689Skan tmp = simplify_gen_relational (cond, SImode, mode, t0, t1); 2426169689Skan assumption = simplify_gen_binary (AND, SImode, assumption, tmp); 2427169689Skan desc->infinite = 2428169689Skan alloc_EXPR_LIST (0, assumption, desc->infinite); 2429169689Skan } 2430169689Skan else 2431169689Skan { 2432169689Skan assumption = simplify_gen_relational (cond, SImode, mode, 2433169689Skan bound, tmp0); 2434169689Skan desc->assumptions = 2435169689Skan alloc_EXPR_LIST (0, assumption, desc->assumptions); 2436169689Skan } 2437169689Skan 2438169689Skan tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step); 2439169689Skan tmp = lowpart_subreg (mode, tmp, comp_mode); 2440169689Skan assumption = simplify_gen_relational (reverse_condition (cond), 2441169689Skan SImode, mode, 2442169689Skan tmp, tmp1); 2443169689Skan delta = simplify_gen_binary (MINUS, mode, tmp0, step); 2444169689Skan delta = simplify_gen_binary (MINUS, mode, tmp1, delta); 2445169689Skan } 2446169689Skan if (assumption == const_true_rtx) 2447169689Skan goto zero_iter_simplify; 2448169689Skan else if (assumption != const0_rtx) 2449169689Skan desc->noloop_assumptions = 2450169689Skan alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); 2451169689Skan delta = simplify_gen_binary (UDIV, mode, delta, step); 2452169689Skan desc->niter_expr = delta; 2453169689Skan } 2454169689Skan 2455169689Skan old_niter = desc->niter_expr; 2456169689Skan 2457169689Skan simplify_using_initial_values (loop, AND, &desc->assumptions); 2458169689Skan if (desc->assumptions 2459169689Skan && XEXP (desc->assumptions, 0) == const0_rtx) 2460169689Skan goto fail; 2461169689Skan simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2462169689Skan simplify_using_initial_values (loop, IOR, &desc->infinite); 2463169689Skan simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2464169689Skan 2465169689Skan /* Rerun the simplification. Consider code (created by copying loop headers) 2466169689Skan 2467169689Skan i = 0; 2468169689Skan 2469169689Skan if (0 < n) 2470169689Skan { 2471169689Skan do 2472169689Skan { 2473169689Skan i++; 2474169689Skan } while (i < n); 2475169689Skan } 2476169689Skan 2477169689Skan The first pass determines that i = 0, the second pass uses it to eliminate 2478169689Skan noloop assumption. */ 2479169689Skan 2480169689Skan simplify_using_initial_values (loop, AND, &desc->assumptions); 2481169689Skan if (desc->assumptions 2482169689Skan && XEXP (desc->assumptions, 0) == const0_rtx) 2483169689Skan goto fail; 2484169689Skan simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions); 2485169689Skan simplify_using_initial_values (loop, IOR, &desc->infinite); 2486169689Skan simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr); 2487169689Skan 2488169689Skan if (desc->noloop_assumptions 2489169689Skan && XEXP (desc->noloop_assumptions, 0) == const_true_rtx) 2490169689Skan goto zero_iter; 2491169689Skan 2492169689Skan if (GET_CODE (desc->niter_expr) == CONST_INT) 2493169689Skan { 2494169689Skan unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr); 2495169689Skan 2496169689Skan desc->const_iter = true; 2497169689Skan desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode); 2498169689Skan } 2499169689Skan else 2500169689Skan { 2501169689Skan if (!desc->niter_max) 2502169689Skan desc->niter_max = determine_max_iter (desc); 2503169689Skan 2504169689Skan /* simplify_using_initial_values does a copy propagation on the registers 2505169689Skan in the expression for the number of iterations. This prolongs life 2506169689Skan ranges of registers and increases register pressure, and usually 2507169689Skan brings no gain (and if it happens to do, the cse pass will take care 2508169689Skan of it anyway). So prevent this behavior, unless it enabled us to 2509169689Skan derive that the number of iterations is a constant. */ 2510169689Skan desc->niter_expr = old_niter; 2511169689Skan } 2512169689Skan 2513169689Skan return; 2514169689Skan 2515169689Skanzero_iter_simplify: 2516169689Skan /* Simplify the assumptions. */ 2517169689Skan simplify_using_initial_values (loop, AND, &desc->assumptions); 2518169689Skan if (desc->assumptions 2519169689Skan && XEXP (desc->assumptions, 0) == const0_rtx) 2520169689Skan goto fail; 2521169689Skan simplify_using_initial_values (loop, IOR, &desc->infinite); 2522169689Skan 2523169689Skan /* Fallthru. */ 2524169689Skanzero_iter: 2525169689Skan desc->const_iter = true; 2526169689Skan desc->niter = 0; 2527169689Skan desc->niter_max = 0; 2528169689Skan desc->noloop_assumptions = NULL_RTX; 2529169689Skan desc->niter_expr = const0_rtx; 2530169689Skan return; 2531169689Skan 2532169689Skanfail: 2533169689Skan desc->simple_p = false; 2534169689Skan return; 2535169689Skan} 2536169689Skan 2537169689Skan/* Checks whether E is a simple exit from LOOP and stores its description 2538169689Skan into DESC. */ 2539169689Skan 2540169689Skanstatic void 2541169689Skancheck_simple_exit (struct loop *loop, edge e, struct niter_desc *desc) 2542169689Skan{ 2543169689Skan basic_block exit_bb; 2544169689Skan rtx condition, at; 2545169689Skan edge ein; 2546169689Skan 2547169689Skan exit_bb = e->src; 2548169689Skan desc->simple_p = false; 2549169689Skan 2550169689Skan /* It must belong directly to the loop. */ 2551169689Skan if (exit_bb->loop_father != loop) 2552169689Skan return; 2553169689Skan 2554169689Skan /* It must be tested (at least) once during any iteration. */ 2555169689Skan if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb)) 2556169689Skan return; 2557169689Skan 2558169689Skan /* It must end in a simple conditional jump. */ 2559169689Skan if (!any_condjump_p (BB_END (exit_bb))) 2560169689Skan return; 2561169689Skan 2562169689Skan ein = EDGE_SUCC (exit_bb, 0); 2563169689Skan if (ein == e) 2564169689Skan ein = EDGE_SUCC (exit_bb, 1); 2565169689Skan 2566169689Skan desc->out_edge = e; 2567169689Skan desc->in_edge = ein; 2568169689Skan 2569169689Skan /* Test whether the condition is suitable. */ 2570169689Skan if (!(condition = get_condition (BB_END (ein->src), &at, false, false))) 2571169689Skan return; 2572169689Skan 2573169689Skan if (ein->flags & EDGE_FALLTHRU) 2574169689Skan { 2575169689Skan condition = reversed_condition (condition); 2576169689Skan if (!condition) 2577169689Skan return; 2578169689Skan } 2579169689Skan 2580169689Skan /* Check that we are able to determine number of iterations and fill 2581169689Skan in information about it. */ 2582169689Skan iv_number_of_iterations (loop, at, condition, desc); 2583169689Skan} 2584169689Skan 2585169689Skan/* Finds a simple exit of LOOP and stores its description into DESC. */ 2586169689Skan 2587169689Skanvoid 2588169689Skanfind_simple_exit (struct loop *loop, struct niter_desc *desc) 2589169689Skan{ 2590169689Skan unsigned i; 2591169689Skan basic_block *body; 2592169689Skan edge e; 2593169689Skan struct niter_desc act; 2594169689Skan bool any = false; 2595169689Skan edge_iterator ei; 2596169689Skan 2597169689Skan desc->simple_p = false; 2598169689Skan body = get_loop_body (loop); 2599169689Skan 2600169689Skan for (i = 0; i < loop->num_nodes; i++) 2601169689Skan { 2602169689Skan FOR_EACH_EDGE (e, ei, body[i]->succs) 2603169689Skan { 2604169689Skan if (flow_bb_inside_loop_p (loop, e->dest)) 2605169689Skan continue; 2606169689Skan 2607169689Skan check_simple_exit (loop, e, &act); 2608169689Skan if (!act.simple_p) 2609169689Skan continue; 2610169689Skan 2611169689Skan if (!any) 2612169689Skan any = true; 2613169689Skan else 2614169689Skan { 2615169689Skan /* Prefer constant iterations; the less the better. */ 2616169689Skan if (!act.const_iter 2617169689Skan || (desc->const_iter && act.niter >= desc->niter)) 2618169689Skan continue; 2619169689Skan 2620169689Skan /* Also if the actual exit may be infinite, while the old one 2621169689Skan not, prefer the old one. */ 2622169689Skan if (act.infinite && !desc->infinite) 2623169689Skan continue; 2624169689Skan } 2625169689Skan 2626169689Skan *desc = act; 2627169689Skan } 2628169689Skan } 2629169689Skan 2630169689Skan if (dump_file) 2631169689Skan { 2632169689Skan if (desc->simple_p) 2633169689Skan { 2634169689Skan fprintf (dump_file, "Loop %d is simple:\n", loop->num); 2635169689Skan fprintf (dump_file, " simple exit %d -> %d\n", 2636169689Skan desc->out_edge->src->index, 2637169689Skan desc->out_edge->dest->index); 2638169689Skan if (desc->assumptions) 2639169689Skan { 2640169689Skan fprintf (dump_file, " assumptions: "); 2641169689Skan print_rtl (dump_file, desc->assumptions); 2642169689Skan fprintf (dump_file, "\n"); 2643169689Skan } 2644169689Skan if (desc->noloop_assumptions) 2645169689Skan { 2646169689Skan fprintf (dump_file, " does not roll if: "); 2647169689Skan print_rtl (dump_file, desc->noloop_assumptions); 2648169689Skan fprintf (dump_file, "\n"); 2649169689Skan } 2650169689Skan if (desc->infinite) 2651169689Skan { 2652169689Skan fprintf (dump_file, " infinite if: "); 2653169689Skan print_rtl (dump_file, desc->infinite); 2654169689Skan fprintf (dump_file, "\n"); 2655169689Skan } 2656169689Skan 2657169689Skan fprintf (dump_file, " number of iterations: "); 2658169689Skan print_rtl (dump_file, desc->niter_expr); 2659169689Skan fprintf (dump_file, "\n"); 2660169689Skan 2661169689Skan fprintf (dump_file, " upper bound: "); 2662169689Skan fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max); 2663169689Skan fprintf (dump_file, "\n"); 2664169689Skan } 2665169689Skan else 2666169689Skan fprintf (dump_file, "Loop %d is not simple.\n", loop->num); 2667169689Skan } 2668169689Skan 2669169689Skan free (body); 2670169689Skan} 2671169689Skan 2672169689Skan/* Creates a simple loop description of LOOP if it was not computed 2673169689Skan already. */ 2674169689Skan 2675169689Skanstruct niter_desc * 2676169689Skanget_simple_loop_desc (struct loop *loop) 2677169689Skan{ 2678169689Skan struct niter_desc *desc = simple_loop_desc (loop); 2679169689Skan 2680169689Skan if (desc) 2681169689Skan return desc; 2682169689Skan 2683169689Skan desc = XNEW (struct niter_desc); 2684169689Skan iv_analysis_loop_init (loop); 2685169689Skan find_simple_exit (loop, desc); 2686169689Skan loop->aux = desc; 2687169689Skan 2688169689Skan if (desc->simple_p && (desc->assumptions || desc->infinite)) 2689169689Skan { 2690169689Skan const char *wording; 2691169689Skan 2692169689Skan /* Assume that no overflow happens and that the loop is finite. 2693169689Skan We already warned at the tree level if we ran optimizations there. */ 2694169689Skan if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations) 2695169689Skan { 2696169689Skan if (desc->infinite) 2697169689Skan { 2698169689Skan wording = 2699169689Skan flag_unsafe_loop_optimizations 2700169689Skan ? N_("assuming that the loop is not infinite") 2701169689Skan : N_("cannot optimize possibly infinite loops"); 2702169689Skan warning (OPT_Wunsafe_loop_optimizations, "%s", 2703169689Skan gettext (wording)); 2704169689Skan } 2705169689Skan if (desc->assumptions) 2706169689Skan { 2707169689Skan wording = 2708169689Skan flag_unsafe_loop_optimizations 2709169689Skan ? N_("assuming that the loop counter does not overflow") 2710169689Skan : N_("cannot optimize loop, the loop counter may overflow"); 2711169689Skan warning (OPT_Wunsafe_loop_optimizations, "%s", 2712169689Skan gettext (wording)); 2713169689Skan } 2714169689Skan } 2715169689Skan 2716169689Skan if (flag_unsafe_loop_optimizations) 2717169689Skan { 2718169689Skan desc->assumptions = NULL_RTX; 2719169689Skan desc->infinite = NULL_RTX; 2720169689Skan } 2721169689Skan } 2722169689Skan 2723169689Skan return desc; 2724169689Skan} 2725169689Skan 2726169689Skan/* Releases simple loop description for LOOP. */ 2727169689Skan 2728169689Skanvoid 2729169689Skanfree_simple_loop_desc (struct loop *loop) 2730169689Skan{ 2731169689Skan struct niter_desc *desc = simple_loop_desc (loop); 2732169689Skan 2733169689Skan if (!desc) 2734169689Skan return; 2735169689Skan 2736169689Skan free (desc); 2737169689Skan loop->aux = NULL; 2738169689Skan} 2739