gcc/loop-iv.c

   1 /* Rtl-level induction variable analysis.
   2    Copyright (C) 2004-2013 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This is a simple analysis of induction variables of the loop.  The major use
  21    is for determining the number of iterations of a loop for loop unrolling,
  22    doloop optimization and branch prediction.  The iv information is computed
  23    on demand.
  24
  25    Induction variables are analyzed by walking the use-def chains.  When
  26    a basic induction variable (biv) is found, it is cached in the bivs
  27    hash table.  When register is proved to be a biv, its description
  28    is stored to DF_REF_DATA of the def reference.
  29
  30    The analysis works always with one loop -- you must call
  31    iv_analysis_loop_init (loop) for it.  All the other functions then work with
  32    this loop.   When you need to work with another loop, just call
  33    iv_analysis_loop_init for it.  When you no longer need iv analysis, call
  34    iv_analysis_done () to clean up the memory.
  35
  36    The available functions are:
  37
  38    iv_analyze (insn, reg, iv): Stores the description of the induction variable
  39      corresponding to the use of register REG in INSN to IV.  Returns true if
  40      REG is an induction variable in INSN. false otherwise.
  41      If use of REG is not found in INSN, following insns are scanned (so that
  42      we may call this function on insn returned by get_condition).
  43    iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
  44      corresponding to DEF, which is a register defined in INSN.
  45    iv_analyze_expr (insn, rhs, mode, iv):  Stores to IV the description of iv
  46      corresponding to expression EXPR evaluated at INSN.  All registers used bu
  47      EXPR must also be used in INSN.
  48 */
  49
  50 #include "config.h"
  51 #include "system.h"
  52 #include "coretypes.h"
  53 #include "tm.h"
  54 #include "rtl.h"
  55 #include "hard-reg-set.h"
  56 #include "obstack.h"
  57 #include "basic-block.h"
  58 #include "cfgloop.h"
  59 #include "expr.h"
  60 #include "intl.h"
  61 #include "diagnostic-core.h"
  62 #include "df.h"
  63 #include "hashtab.h"
  64 #include "dumpfile.h"
  65
  66 /* Possible return values of iv_get_reaching_def.  */
  67
  68 enum iv_grd_result
  69 {
  70   /* More than one reaching def, or reaching def that does not
  71      dominate the use.  */
  72   GRD_INVALID,
  73
  74   /* The use is trivial invariant of the loop, i.e. is not changed
  75      inside the loop.  */
  76   GRD_INVARIANT,
  77
  78   /* The use is reached by initial value and a value from the
  79      previous iteration.  */
  80   GRD_MAYBE_BIV,
  81
  82   /* The use has single dominating def.  */
  83   GRD_SINGLE_DOM
  84 };
  85
  86 /* Information about a biv.  */
  87
  88 struct biv_entry
  89 {
  90   unsigned regno;       /* The register of the biv.  */
  91   struct rtx_iv iv;     /* Value of the biv.  */
  92 };
  93
  94 static bool clean_slate = true;
  95
  96 static unsigned int iv_ref_table_size = 0;
  97
  98 /* Table of rtx_ivs indexed by the df_ref uid field.  */
  99 static struct rtx_iv ** iv_ref_table;
 100
 101 /* Induction variable stored at the reference.  */
 102 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
 103 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
 104
 105 /* The current loop.  */
 106
 107 static struct loop *current_loop;
 108
 109 /* Bivs of the current loop.  */
 110
 111 static htab_t bivs;
 112
 113 static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
 114
 115 /* Return the RTX code corresponding to the IV extend code EXTEND.  */
 116 static inline enum rtx_code
 117 iv_extend_to_rtx_code (enum iv_extend_code extend)
 118 {
 119   switch (extend)
 120     {
 121     case IV_SIGN_EXTEND:
 122       return SIGN_EXTEND;
 123     case IV_ZERO_EXTEND:
 124       return ZERO_EXTEND;
 125     case IV_UNKNOWN_EXTEND:
 126       return UNKNOWN;
 127     }
 128   gcc_unreachable ();
 129 }
 130
 131 /* Dumps information about IV to FILE.  */
 132
 133 extern void dump_iv_info (FILE *, struct rtx_iv *);
 134 void
 135 dump_iv_info (FILE *file, struct rtx_iv *iv)
 136 {
 137   if (!iv->base)
 138     {
 139       fprintf (file, "not simple");
 140       return;
 141     }
 142
 143   if (iv->step == const0_rtx
 144       && !iv->first_special)
 145     fprintf (file, "invariant ");
 146
 147   print_rtl (file, iv->base);
 148   if (iv->step != const0_rtx)
 149     {
 150       fprintf (file, " + ");
 151       print_rtl (file, iv->step);
 152       fprintf (file, " * iteration");
 153     }
 154   fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
 155
 156   if (iv->mode != iv->extend_mode)
 157     fprintf (file, " %s to %s",
 158              rtx_name[iv_extend_to_rtx_code (iv->extend)],
 159              GET_MODE_NAME (iv->extend_mode));
 160
 161   if (iv->mult != const1_rtx)
 162     {
 163       fprintf (file, " * ");
 164       print_rtl (file, iv->mult);
 165     }
 166   if (iv->delta != const0_rtx)
 167     {
 168       fprintf (file, " + ");
 169       print_rtl (file, iv->delta);
 170     }
 171   if (iv->first_special)
 172     fprintf (file, " (first special)");
 173 }
 174
 175 /* Generates a subreg to get the least significant part of EXPR (in mode
 176    INNER_MODE) to OUTER_MODE.  */
 177
 178 rtx
 179 lowpart_subreg (enum machine_mode outer_mode, rtx expr,
 180                 enum machine_mode inner_mode)
 181 {
 182   return simplify_gen_subreg (outer_mode, expr, inner_mode,
 183                               subreg_lowpart_offset (outer_mode, inner_mode));
 184 }
 185
 186 static void
 187 check_iv_ref_table_size (void)
 188 {
 189   if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
 190     {
 191       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
 192       iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
 193       memset (&iv_ref_table[iv_ref_table_size], 0,
 194               (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
 195       iv_ref_table_size = new_size;
 196     }
 197 }
 198
 199
 200 /* Checks whether REG is a well-behaved register.  */
 201
 202 static bool
 203 simple_reg_p (rtx reg)
 204 {
 205   unsigned r;
 206
 207   if (GET_CODE (reg) == SUBREG)
 208     {
 209       if (!subreg_lowpart_p (reg))
 210         return false;
 211       reg = SUBREG_REG (reg);
 212     }
 213
 214   if (!REG_P (reg))
 215     return false;
 216
 217   r = REGNO (reg);
 218   if (HARD_REGISTER_NUM_P (r))
 219     return false;
 220
 221   if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
 222     return false;
 223
 224   return true;
 225 }
 226
 227 /* Clears the information about ivs stored in df.  */
 228
 229 static void
 230 clear_iv_info (void)
 231 {
 232   unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
 233   struct rtx_iv *iv;
 234
 235   check_iv_ref_table_size ();
 236   for (i = 0; i < n_defs; i++)
 237     {
 238       iv = iv_ref_table[i];
 239       if (iv)
 240         {
 241           free (iv);
 242           iv_ref_table[i] = NULL;
 243         }
 244     }
 245
 246   htab_empty (bivs);
 247 }
 248
 249 /* Returns hash value for biv B.  */
 250
 251 static hashval_t
 252 biv_hash (const void *b)
 253 {
 254   return ((const struct biv_entry *) b)->regno;
 255 }
 256
 257 /* Compares biv B and register R.  */
 258
 259 static int
 260 biv_eq (const void *b, const void *r)
 261 {
 262   return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);
 263 }
 264
 265 /* Prepare the data for an induction variable analysis of a LOOP.  */
 266
 267 void
 268 iv_analysis_loop_init (struct loop *loop)
 269 {
 270   basic_block *body = get_loop_body_in_dom_order (loop), bb;
 271   bitmap blocks = BITMAP_ALLOC (NULL);
 272   unsigned i;
 273
 274   current_loop = loop;
 275
 276   /* Clear the information from the analysis of the previous loop.  */
 277   if (clean_slate)
 278     {
 279       df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
 280       bivs = htab_create (10, biv_hash, biv_eq, free);
 281       clean_slate = false;
 282     }
 283   else
 284     clear_iv_info ();
 285
 286   for (i = 0; i < loop->num_nodes; i++)
 287     {
 288       bb = body[i];
 289       bitmap_set_bit (blocks, bb->index);
 290     }
 291   /* Get rid of the ud chains before processing the rescans.  Then add
 292      the problem back.  */
 293   df_remove_problem (df_chain);
 294   df_process_deferred_rescans ();
 295   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 296   df_chain_add_problem (DF_UD_CHAIN);
 297   df_note_add_problem ();
 298   df_set_blocks (blocks);
 299   df_analyze ();
 300   if (dump_file)
 301     df_dump_region (dump_file);
 302
 303   check_iv_ref_table_size ();
 304   BITMAP_FREE (blocks);
 305   free (body);
 306 }
 307
 308 /* Finds the definition of REG that dominates loop latch and stores
 309    it to DEF.  Returns false if there is not a single definition
 310    dominating the latch.  If REG has no definition in loop, DEF
 311    is set to NULL and true is returned.  */
 312
 313 static bool
 314 latch_dominating_def (rtx reg, df_ref *def)
 315 {
 316   df_ref single_rd = NULL, adef;
 317   unsigned regno = REGNO (reg);
 318   struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
 319
 320   for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
 321     {
 322       if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
 323           || !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
 324         continue;
 325
 326       /* More than one reaching definition.  */
 327       if (single_rd)
 328         return false;
 329
 330       if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
 331         return false;
 332
 333       single_rd = adef;
 334     }
 335
 336   *def = single_rd;
 337   return true;
 338 }
 339
 340 /* Gets definition of REG reaching its use in INSN and stores it to DEF.  */
 341
 342 static enum iv_grd_result
 343 iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
 344 {
 345   df_ref use, adef;
 346   basic_block def_bb, use_bb;
 347   rtx def_insn;
 348   bool dom_p;
 349
 350   *def = NULL;
 351   if (!simple_reg_p (reg))
 352     return GRD_INVALID;
 353   if (GET_CODE (reg) == SUBREG)
 354     reg = SUBREG_REG (reg);
 355   gcc_assert (REG_P (reg));
 356
 357   use = df_find_use (insn, reg);
 358   gcc_assert (use != NULL);
 359
 360   if (!DF_REF_CHAIN (use))
 361     return GRD_INVARIANT;
 362
 363   /* More than one reaching def.  */
 364   if (DF_REF_CHAIN (use)->next)
 365     return GRD_INVALID;
 366
 367   adef = DF_REF_CHAIN (use)->ref;
 368
 369   /* We do not handle setting only part of the register.  */
 370   if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
 371     return GRD_INVALID;
 372
 373   def_insn = DF_REF_INSN (adef);
 374   def_bb = DF_REF_BB (adef);
 375   use_bb = BLOCK_FOR_INSN (insn);
 376
 377   if (use_bb == def_bb)
 378     dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
 379   else
 380     dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
 381
 382   if (dom_p)
 383     {
 384       *def = adef;
 385       return GRD_SINGLE_DOM;
 386     }
 387
 388   /* The definition does not dominate the use.  This is still OK if
 389      this may be a use of a biv, i.e. if the def_bb dominates loop
 390      latch.  */
 391   if (just_once_each_iteration_p (current_loop, def_bb))
 392     return GRD_MAYBE_BIV;
 393
 394   return GRD_INVALID;
 395 }
 396
 397 /* Sets IV to invariant CST in MODE.  Always returns true (just for
 398    consistency with other iv manipulation functions that may fail).  */
 399
 400 static bool
 401 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
 402 {
 403   if (mode == VOIDmode)
 404     mode = GET_MODE (cst);
 405
 406   iv->mode = mode;
 407   iv->base = cst;
 408   iv->step = const0_rtx;
 409   iv->first_special = false;
 410   iv->extend = IV_UNKNOWN_EXTEND;
 411   iv->extend_mode = iv->mode;
 412   iv->delta = const0_rtx;
 413   iv->mult = const1_rtx;
 414
 415   return true;
 416 }
 417
 418 /* Evaluates application of subreg to MODE on IV.  */
 419
 420 static bool
 421 iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
 422 {
 423   /* If iv is invariant, just calculate the new value.  */
 424   if (iv->step == const0_rtx
 425       && !iv->first_special)
 426     {
 427       rtx val = get_iv_value (iv, const0_rtx);
 428       val = lowpart_subreg (mode, val, iv->extend_mode);
 429
 430       iv->base = val;
 431       iv->extend = IV_UNKNOWN_EXTEND;
 432       iv->mode = iv->extend_mode = mode;
 433       iv->delta = const0_rtx;
 434       iv->mult = const1_rtx;
 435       return true;
 436     }
 437
 438   if (iv->extend_mode == mode)
 439     return true;
 440
 441   if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
 442     return false;
 443
 444   iv->extend = IV_UNKNOWN_EXTEND;
 445   iv->mode = mode;
 446
 447   iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
 448                                   simplify_gen_binary (MULT, iv->extend_mode,
 449                                                        iv->base, iv->mult));
 450   iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
 451   iv->mult = const1_rtx;
 452   iv->delta = const0_rtx;
 453   iv->first_special = false;
 454
 455   return true;
 456 }
 457
 458 /* Evaluates application of EXTEND to MODE on IV.  */
 459
 460 static bool
 461 iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode)
 462 {
 463   /* If iv is invariant, just calculate the new value.  */
 464   if (iv->step == const0_rtx
 465       && !iv->first_special)
 466     {
 467       rtx val = get_iv_value (iv, const0_rtx);
 468       val = simplify_gen_unary (iv_extend_to_rtx_code (extend), mode,
 469                                 val, iv->extend_mode);
 470       iv->base = val;
 471       iv->extend = IV_UNKNOWN_EXTEND;
 472       iv->mode = iv->extend_mode = mode;
 473       iv->delta = const0_rtx;
 474       iv->mult = const1_rtx;
 475       return true;
 476     }
 477
 478   if (mode != iv->extend_mode)
 479     return false;
 480
 481   if (iv->extend != IV_UNKNOWN_EXTEND
 482       && iv->extend != extend)
 483     return false;
 484
 485   iv->extend = extend;
 486
 487   return true;
 488 }
 489
 490 /* Evaluates negation of IV.  */
 491
 492 static bool
 493 iv_neg (struct rtx_iv *iv)
 494 {
 495   if (iv->extend == IV_UNKNOWN_EXTEND)
 496     {
 497       iv->base = simplify_gen_unary (NEG, iv->extend_mode,
 498                                      iv->base, iv->extend_mode);
 499       iv->step = simplify_gen_unary (NEG, iv->extend_mode,
 500                                      iv->step, iv->extend_mode);
 501     }
 502   else
 503     {
 504       iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
 505                                       iv->delta, iv->extend_mode);
 506       iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
 507                                      iv->mult, iv->extend_mode);
 508     }
 509
 510   return true;
 511 }
 512
 513 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0.  */
 514
 515 static bool
 516 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
 517 {
 518   enum machine_mode mode;
 519   rtx arg;
 520
 521   /* Extend the constant to extend_mode of the other operand if necessary.  */
 522   if (iv0->extend == IV_UNKNOWN_EXTEND
 523       && iv0->mode == iv0->extend_mode
 524       && iv0->step == const0_rtx
 525       && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
 526     {
 527       iv0->extend_mode = iv1->extend_mode;
 528       iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
 529                                       iv0->base, iv0->mode);
 530     }
 531   if (iv1->extend == IV_UNKNOWN_EXTEND
 532       && iv1->mode == iv1->extend_mode
 533       && iv1->step == const0_rtx
 534       && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
 535     {
 536       iv1->extend_mode = iv0->extend_mode;
 537       iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
 538                                       iv1->base, iv1->mode);
 539     }
 540
 541   mode = iv0->extend_mode;
 542   if (mode != iv1->extend_mode)
 543     return false;
 544
 545   if (iv0->extend == IV_UNKNOWN_EXTEND
 546       && iv1->extend == IV_UNKNOWN_EXTEND)
 547     {
 548       if (iv0->mode != iv1->mode)
 549         return false;
 550
 551       iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
 552       iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
 553
 554       return true;
 555     }
 556
 557   /* Handle addition of constant.  */
 558   if (iv1->extend == IV_UNKNOWN_EXTEND
 559       && iv1->mode == mode
 560       && iv1->step == const0_rtx)
 561     {
 562       iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
 563       return true;
 564     }
 565
 566   if (iv0->extend == IV_UNKNOWN_EXTEND
 567       && iv0->mode == mode
 568       && iv0->step == const0_rtx)
 569     {
 570       arg = iv0->base;
 571       *iv0 = *iv1;
 572       if (op == MINUS
 573           && !iv_neg (iv0))
 574         return false;
 575
 576       iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
 577       return true;
 578     }
 579
 580   return false;
 581 }
 582
 583 /* Evaluates multiplication of IV by constant CST.  */
 584
 585 static bool
 586 iv_mult (struct rtx_iv *iv, rtx mby)
 587 {
 588   enum machine_mode mode = iv->extend_mode;
 589
 590   if (GET_MODE (mby) != VOIDmode
 591       && GET_MODE (mby) != mode)
 592     return false;
 593
 594   if (iv->extend == IV_UNKNOWN_EXTEND)
 595     {
 596       iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
 597       iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
 598     }
 599   else
 600     {
 601       iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
 602       iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
 603     }
 604
 605   return true;
 606 }
 607
 608 /* Evaluates shift of IV by constant CST.  */
 609
 610 static bool
 611 iv_shift (struct rtx_iv *iv, rtx mby)
 612 {
 613   enum machine_mode mode = iv->extend_mode;
 614
 615   if (GET_MODE (mby) != VOIDmode
 616       && GET_MODE (mby) != mode)
 617     return false;
 618
 619   if (iv->extend == IV_UNKNOWN_EXTEND)
 620     {
 621       iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
 622       iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
 623     }
 624   else
 625     {
 626       iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
 627       iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
 628     }
 629
 630   return true;
 631 }
 632
 633 /* The recursive part of get_biv_step.  Gets the value of the single value
 634    defined by DEF wrto initial value of REG inside loop, in shape described
 635    at get_biv_step.  */
 636
 637 static bool
 638 get_biv_step_1 (df_ref def, rtx reg,
 639                 rtx *inner_step, enum machine_mode *inner_mode,
 640                 enum iv_extend_code *extend, enum machine_mode outer_mode,
 641                 rtx *outer_step)
 642 {
 643   rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
 644   rtx next, nextr, tmp;
 645   enum rtx_code code;
 646   rtx insn = DF_REF_INSN (def);
 647   df_ref next_def;
 648   enum iv_grd_result res;
 649
 650   set = single_set (insn);
 651   if (!set)
 652     return false;
 653
 654   rhs = find_reg_equal_equiv_note (insn);
 655   if (rhs)
 656     rhs = XEXP (rhs, 0);
 657   else
 658     rhs = SET_SRC (set);
 659
 660   code = GET_CODE (rhs);
 661   switch (code)
 662     {
 663     case SUBREG:
 664     case REG:
 665       next = rhs;
 666       break;
 667
 668     case PLUS:
 669     case MINUS:
 670       op0 = XEXP (rhs, 0);
 671       op1 = XEXP (rhs, 1);
 672
 673       if (code == PLUS && CONSTANT_P (op0))
 674         {
 675           tmp = op0; op0 = op1; op1 = tmp;
 676         }
 677
 678       if (!simple_reg_p (op0)
 679           || !CONSTANT_P (op1))
 680         return false;
 681
 682       if (GET_MODE (rhs) != outer_mode)
 683         {
 684           /* ppc64 uses expressions like
 685
 686              (set x:SI (plus:SI (subreg:SI y:DI) 1)).
 687
 688              this is equivalent to
 689
 690              (set x':DI (plus:DI y:DI 1))
 691              (set x:SI (subreg:SI (x':DI)).  */
 692           if (GET_CODE (op0) != SUBREG)
 693             return false;
 694           if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
 695             return false;
 696         }
 697
 698       next = op0;
 699       break;
 700
 701     case SIGN_EXTEND:
 702     case ZERO_EXTEND:
 703       if (GET_MODE (rhs) != outer_mode)
 704         return false;
 705
 706       op0 = XEXP (rhs, 0);
 707       if (!simple_reg_p (op0))
 708         return false;
 709
 710       next = op0;
 711       break;
 712
 713     default:
 714       return false;
 715     }
 716
 717   if (GET_CODE (next) == SUBREG)
 718     {
 719       if (!subreg_lowpart_p (next))
 720         return false;
 721
 722       nextr = SUBREG_REG (next);
 723       if (GET_MODE (nextr) != outer_mode)
 724         return false;
 725     }
 726   else
 727     nextr = next;
 728
 729   res = iv_get_reaching_def (insn, nextr, &next_def);
 730
 731   if (res == GRD_INVALID || res == GRD_INVARIANT)
 732     return false;
 733
 734   if (res == GRD_MAYBE_BIV)
 735     {
 736       if (!rtx_equal_p (nextr, reg))
 737         return false;
 738
 739       *inner_step = const0_rtx;
 740       *extend = IV_UNKNOWN_EXTEND;
 741       *inner_mode = outer_mode;
 742       *outer_step = const0_rtx;
 743     }
 744   else if (!get_biv_step_1 (next_def, reg,
 745                             inner_step, inner_mode, extend, outer_mode,
 746                             outer_step))
 747     return false;
 748
 749   if (GET_CODE (next) == SUBREG)
 750     {
 751       enum machine_mode amode = GET_MODE (next);
 752
 753       if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
 754         return false;
 755
 756       *inner_mode = amode;
 757       *inner_step = simplify_gen_binary (PLUS, outer_mode,
 758                                          *inner_step, *outer_step);
 759       *outer_step = const0_rtx;
 760       *extend = IV_UNKNOWN_EXTEND;
 761     }
 762
 763   switch (code)
 764     {
 765     case REG:
 766     case SUBREG:
 767       break;
 768
 769     case PLUS:
 770     case MINUS:
 771       if (*inner_mode == outer_mode
 772           /* See comment in previous switch.  */
 773           || GET_MODE (rhs) != outer_mode)
 774         *inner_step = simplify_gen_binary (code, outer_mode,
 775                                            *inner_step, op1);
 776       else
 777         *outer_step = simplify_gen_binary (code, outer_mode,
 778                                            *outer_step, op1);
 779       break;
 780
 781     case SIGN_EXTEND:
 782     case ZERO_EXTEND:
 783       gcc_assert (GET_MODE (op0) == *inner_mode
 784                   && *extend == IV_UNKNOWN_EXTEND
 785                   && *outer_step == const0_rtx);
 786
 787       *extend = (code == SIGN_EXTEND) ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
 788       break;
 789
 790     default:
 791       return false;
 792     }
 793
 794   return true;
 795 }
 796
 797 /* Gets the operation on register REG inside loop, in shape
 798
 799    OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
 800
 801    If the operation cannot be described in this shape, return false.
 802    LAST_DEF is the definition of REG that dominates loop latch.  */
 803
 804 static bool
 805 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
 806               enum machine_mode *inner_mode, enum iv_extend_code *extend,
 807               enum machine_mode *outer_mode, rtx *outer_step)
 808 {
 809   *outer_mode = GET_MODE (reg);
 810
 811   if (!get_biv_step_1 (last_def, reg,
 812                        inner_step, inner_mode, extend, *outer_mode,
 813                        outer_step))
 814     return false;
 815
 816   gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND));
 817   gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
 818
 819   return true;
 820 }
 821
 822 /* Records information that DEF is induction variable IV.  */
 823
 824 static void
 825 record_iv (df_ref def, struct rtx_iv *iv)
 826 {
 827   struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
 828
 829   *recorded_iv = *iv;
 830   check_iv_ref_table_size ();
 831   DF_REF_IV_SET (def, recorded_iv);
 832 }
 833
 834 /* If DEF was already analyzed for bivness, store the description of the biv to
 835    IV and return true.  Otherwise return false.  */
 836
 837 static bool
 838 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
 839 {
 840   struct biv_entry *biv =
 841     (struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));
 842
 843   if (!biv)
 844     return false;
 845
 846   *iv = biv->iv;
 847   return true;
 848 }
 849
 850 static void
 851 record_biv (rtx def, struct rtx_iv *iv)
 852 {
 853   struct biv_entry *biv = XNEW (struct biv_entry);
 854   void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
 855
 856   biv->regno = REGNO (def);
 857   biv->iv = *iv;
 858   gcc_assert (!*slot);
 859   *slot = biv;
 860 }
 861
 862 /* Determines whether DEF is a biv and if so, stores its description
 863    to *IV.  */
 864
 865 static bool
 866 iv_analyze_biv (rtx def, struct rtx_iv *iv)
 867 {
 868   rtx inner_step, outer_step;
 869   enum machine_mode inner_mode, outer_mode;
 870   enum iv_extend_code extend;
 871   df_ref last_def;
 872
 873   if (dump_file)
 874     {
 875       fprintf (dump_file, "Analyzing ");
 876       print_rtl (dump_file, def);
 877       fprintf (dump_file, " for bivness.\n");
 878     }
 879
 880   if (!REG_P (def))
 881     {
 882       if (!CONSTANT_P (def))
 883         return false;
 884
 885       return iv_constant (iv, def, VOIDmode);
 886     }
 887
 888   if (!latch_dominating_def (def, &last_def))
 889     {
 890       if (dump_file)
 891         fprintf (dump_file, "  not simple.\n");
 892       return false;
 893     }
 894
 895   if (!last_def)
 896     return iv_constant (iv, def, VOIDmode);
 897
 898   if (analyzed_for_bivness_p (def, iv))
 899     {
 900       if (dump_file)
 901         fprintf (dump_file, "  already analysed.\n");
 902       return iv->base != NULL_RTX;
 903     }
 904
 905   if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
 906                      &outer_mode, &outer_step))
 907     {
 908       iv->base = NULL_RTX;
 909       goto end;
 910     }
 911
 912   /* Loop transforms base to es (base + inner_step) + outer_step,
 913      where es means extend of subreg between inner_mode and outer_mode.
 914      The corresponding induction variable is
 915
 916      es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step  */
 917
 918   iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
 919   iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
 920   iv->mode = inner_mode;
 921   iv->extend_mode = outer_mode;
 922   iv->extend = extend;
 923   iv->mult = const1_rtx;
 924   iv->delta = outer_step;
 925   iv->first_special = inner_mode != outer_mode;
 926
 927  end:
 928   if (dump_file)
 929     {
 930       fprintf (dump_file, "  ");
 931       dump_iv_info (dump_file, iv);
 932       fprintf (dump_file, "\n");
 933     }
 934
 935   record_biv (def, iv);
 936   return iv->base != NULL_RTX;
 937 }
 938
 939 /* Analyzes expression RHS used at INSN and stores the result to *IV.
 940    The mode of the induction variable is MODE.  */
 941
 942 bool
 943 iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
 944 {
 945   rtx mby = NULL_RTX, tmp;
 946   rtx op0 = NULL_RTX, op1 = NULL_RTX;
 947   struct rtx_iv iv0, iv1;
 948   enum rtx_code code = GET_CODE (rhs);
 949   enum machine_mode omode = mode;
 950
 951   iv->mode = VOIDmode;
 952   iv->base = NULL_RTX;
 953   iv->step = NULL_RTX;
 954
 955   gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
 956
 957   if (CONSTANT_P (rhs)
 958       || REG_P (rhs)
 959       || code == SUBREG)
 960     {
 961       if (!iv_analyze_op (insn, rhs, iv))
 962         return false;
 963
 964       if (iv->mode == VOIDmode)
 965         {
 966           iv->mode = mode;
 967           iv->extend_mode = mode;
 968         }
 969
 970       return true;
 971     }
 972
 973   switch (code)
 974     {
 975     case REG:
 976       op0 = rhs;
 977       break;
 978
 979     case SIGN_EXTEND:
 980     case ZERO_EXTEND:
 981     case NEG:
 982       op0 = XEXP (rhs, 0);
 983       omode = GET_MODE (op0);
 984       break;
 985
 986     case PLUS:
 987     case MINUS:
 988       op0 = XEXP (rhs, 0);
 989       op1 = XEXP (rhs, 1);
 990       break;
 991
 992     case MULT:
 993       op0 = XEXP (rhs, 0);
 994       mby = XEXP (rhs, 1);
 995       if (!CONSTANT_P (mby))
 996         {
 997           tmp = op0;
 998           op0 = mby;
 999           mby = tmp;
1000         }
1001       if (!CONSTANT_P (mby))
1002         return false;
1003       break;
1004
1005     case ASHIFT:
1006       op0 = XEXP (rhs, 0);
1007       mby = XEXP (rhs, 1);
1008       if (!CONSTANT_P (mby))
1009         return false;
1010       break;
1011
1012     default:
1013       return false;
1014     }
1015
1016   if (op0
1017       && !iv_analyze_expr (insn, op0, omode, &iv0))
1018     return false;
1019
1020   if (op1
1021       && !iv_analyze_expr (insn, op1, omode, &iv1))
1022     return false;
1023
1024   switch (code)
1025     {
1026     case SIGN_EXTEND:
1027       if (!iv_extend (&iv0, IV_SIGN_EXTEND, mode))
1028         return false;
1029       break;
1030
1031     case ZERO_EXTEND:
1032       if (!iv_extend (&iv0, IV_ZERO_EXTEND, mode))
1033         return false;
1034       break;
1035
1036     case NEG:
1037       if (!iv_neg (&iv0))
1038         return false;
1039       break;
1040
1041     case PLUS:
1042     case MINUS:
1043       if (!iv_add (&iv0, &iv1, code))
1044         return false;
1045       break;
1046
1047     case MULT:
1048       if (!iv_mult (&iv0, mby))
1049         return false;
1050       break;
1051
1052     case ASHIFT:
1053       if (!iv_shift (&iv0, mby))
1054         return false;
1055       break;
1056
1057     default:
1058       break;
1059     }
1060
1061   *iv = iv0;
1062   return iv->base != NULL_RTX;
1063 }
1064
1065 /* Analyzes iv DEF and stores the result to *IV.  */
1066
1067 static bool
1068 iv_analyze_def (df_ref def, struct rtx_iv *iv)
1069 {
1070   rtx insn = DF_REF_INSN (def);
1071   rtx reg = DF_REF_REG (def);
1072   rtx set, rhs;
1073
1074   if (dump_file)
1075     {
1076       fprintf (dump_file, "Analyzing def of ");
1077       print_rtl (dump_file, reg);
1078       fprintf (dump_file, " in insn ");
1079       print_rtl_single (dump_file, insn);
1080     }
1081
1082   check_iv_ref_table_size ();
1083   if (DF_REF_IV (def))
1084     {
1085       if (dump_file)
1086         fprintf (dump_file, "  already analysed.\n");
1087       *iv = *DF_REF_IV (def);
1088       return iv->base != NULL_RTX;
1089     }
1090
1091   iv->mode = VOIDmode;
1092   iv->base = NULL_RTX;
1093   iv->step = NULL_RTX;
1094
1095   if (!REG_P (reg))
1096     return false;
1097
1098   set = single_set (insn);
1099   if (!set)
1100     return false;
1101
1102   if (!REG_P (SET_DEST (set)))
1103     return false;
1104
1105   gcc_assert (SET_DEST (set) == reg);
1106   rhs = find_reg_equal_equiv_note (insn);
1107   if (rhs)
1108     rhs = XEXP (rhs, 0);
1109   else
1110     rhs = SET_SRC (set);
1111
1112   iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
1113   record_iv (def, iv);
1114
1115   if (dump_file)
1116     {
1117       print_rtl (dump_file, reg);
1118       fprintf (dump_file, " in insn ");
1119       print_rtl_single (dump_file, insn);
1120       fprintf (dump_file, "  is ");
1121       dump_iv_info (dump_file, iv);
1122       fprintf (dump_file, "\n");
1123     }
1124
1125   return iv->base != NULL_RTX;
1126 }
1127
1128 /* Analyzes operand OP of INSN and stores the result to *IV.  */
1129
1130 static bool
1131 iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
1132 {
1133   df_ref def = NULL;
1134   enum iv_grd_result res;
1135
1136   if (dump_file)
1137     {
1138       fprintf (dump_file, "Analyzing operand ");
1139       print_rtl (dump_file, op);
1140       fprintf (dump_file, " of insn ");
1141       print_rtl_single (dump_file, insn);
1142     }
1143
1144   if (function_invariant_p (op))
1145     res = GRD_INVARIANT;
1146   else if (GET_CODE (op) == SUBREG)
1147     {
1148       if (!subreg_lowpart_p (op))
1149         return false;
1150
1151       if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
1152         return false;
1153
1154       return iv_subreg (iv, GET_MODE (op));
1155     }
1156   else
1157     {
1158       res = iv_get_reaching_def (insn, op, &def);
1159       if (res == GRD_INVALID)
1160         {
1161           if (dump_file)
1162             fprintf (dump_file, "  not simple.\n");
1163           return false;
1164         }
1165     }
1166
1167   if (res == GRD_INVARIANT)
1168     {
1169       iv_constant (iv, op, VOIDmode);
1170
1171       if (dump_file)
1172         {
1173           fprintf (dump_file, "  ");
1174           dump_iv_info (dump_file, iv);
1175           fprintf (dump_file, "\n");
1176         }
1177       return true;
1178     }
1179
1180   if (res == GRD_MAYBE_BIV)
1181     return iv_analyze_biv (op, iv);
1182
1183   return iv_analyze_def (def, iv);
1184 }
1185
1186 /* Analyzes value VAL at INSN and stores the result to *IV.  */
1187
1188 bool
1189 iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
1190 {
1191   rtx reg;
1192
1193   /* We must find the insn in that val is used, so that we get to UD chains.
1194      Since the function is sometimes called on result of get_condition,
1195      this does not necessarily have to be directly INSN; scan also the
1196      following insns.  */
1197   if (simple_reg_p (val))
1198     {
1199       if (GET_CODE (val) == SUBREG)
1200         reg = SUBREG_REG (val);
1201       else
1202         reg = val;
1203
1204       while (!df_find_use (insn, reg))
1205         insn = NEXT_INSN (insn);
1206     }
1207
1208   return iv_analyze_op (insn, val, iv);
1209 }
1210
1211 /* Analyzes definition of DEF in INSN and stores the result to IV.  */
1212
1213 bool
1214 iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
1215 {
1216   df_ref adef;
1217
1218   adef = df_find_def (insn, def);
1219   if (!adef)
1220     return false;
1221
1222   return iv_analyze_def (adef, iv);
1223 }
1224
1225 /* Checks whether definition of register REG in INSN is a basic induction
1226    variable.  IV analysis must have been initialized (via a call to
1227    iv_analysis_loop_init) for this function to produce a result.  */
1228
1229 bool
1230 biv_p (rtx insn, rtx reg)
1231 {
1232   struct rtx_iv iv;
1233   df_ref def, last_def;
1234
1235   if (!simple_reg_p (reg))
1236     return false;
1237
1238   def = df_find_def (insn, reg);
1239   gcc_assert (def != NULL);
1240   if (!latch_dominating_def (reg, &last_def))
1241     return false;
1242   if (last_def != def)
1243     return false;
1244
1245   if (!iv_analyze_biv (reg, &iv))
1246     return false;
1247
1248   return iv.step != const0_rtx;
1249 }
1250
1251 /* Calculates value of IV at ITERATION-th iteration.  */
1252
1253 rtx
1254 get_iv_value (struct rtx_iv *iv, rtx iteration)
1255 {
1256   rtx val;
1257
1258   /* We would need to generate some if_then_else patterns, and so far
1259      it is not needed anywhere.  */
1260   gcc_assert (!iv->first_special);
1261
1262   if (iv->step != const0_rtx && iteration != const0_rtx)
1263     val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1264                                simplify_gen_binary (MULT, iv->extend_mode,
1265                                                     iv->step, iteration));
1266   else
1267     val = iv->base;
1268
1269   if (iv->extend_mode == iv->mode)
1270     return val;
1271
1272   val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1273
1274   if (iv->extend == IV_UNKNOWN_EXTEND)
1275     return val;
1276
1277   val = simplify_gen_unary (iv_extend_to_rtx_code (iv->extend),
1278                             iv->extend_mode, val, iv->mode);
1279   val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1280                              simplify_gen_binary (MULT, iv->extend_mode,
1281                                                   iv->mult, val));
1282
1283   return val;
1284 }
1285
1286 /* Free the data for an induction variable analysis.  */
1287
1288 void
1289 iv_analysis_done (void)
1290 {
1291   if (!clean_slate)
1292     {
1293       clear_iv_info ();
1294       clean_slate = true;
1295       df_finish_pass (true);
1296       htab_delete (bivs);
1297       free (iv_ref_table);
1298       iv_ref_table = NULL;
1299       iv_ref_table_size = 0;
1300       bivs = NULL;
1301     }
1302 }
1303
1304 /* Computes inverse to X modulo (1 << MOD).  */
1305
1306 static unsigned HOST_WIDEST_INT
1307 inverse (unsigned HOST_WIDEST_INT x, int mod)
1308 {
1309   unsigned HOST_WIDEST_INT mask =
1310           ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
1311   unsigned HOST_WIDEST_INT rslt = 1;
1312   int i;
1313
1314   for (i = 0; i < mod - 1; i++)
1315     {
1316       rslt = (rslt * x) & mask;
1317       x = (x * x) & mask;
1318     }
1319
1320   return rslt;
1321 }
1322
1323 /* Checks whether register *REG is in set ALT.  Callback for for_each_rtx.  */
1324
1325 static int
1326 altered_reg_used (rtx *reg, void *alt)
1327 {
1328   if (!REG_P (*reg))
1329     return 0;
1330
1331   return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
1332 }
1333
1334 /* Marks registers altered by EXPR in set ALT.  */
1335
1336 static void
1337 mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
1338 {
1339   if (GET_CODE (expr) == SUBREG)
1340     expr = SUBREG_REG (expr);
1341   if (!REG_P (expr))
1342     return;
1343
1344   SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
1345 }
1346
1347 /* Checks whether RHS is simple enough to process.  */
1348
1349 static bool
1350 simple_rhs_p (rtx rhs)
1351 {
1352   rtx op0, op1;
1353
1354   if (function_invariant_p (rhs)
1355       || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
1356     return true;
1357
1358   switch (GET_CODE (rhs))
1359     {
1360     case PLUS:
1361     case MINUS:
1362     case AND:
1363       op0 = XEXP (rhs, 0);
1364       op1 = XEXP (rhs, 1);
1365       /* Allow reg OP const and reg OP reg.  */
1366       if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1367           && !function_invariant_p (op0))
1368         return false;
1369       if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1370           && !function_invariant_p (op1))
1371         return false;
1372
1373       return true;
1374
1375     case ASHIFT:
1376     case ASHIFTRT:
1377     case LSHIFTRT:
1378     case MULT:
1379       op0 = XEXP (rhs, 0);
1380       op1 = XEXP (rhs, 1);
1381       /* Allow reg OP const.  */
1382       if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1383         return false;
1384       if (!function_invariant_p (op1))
1385         return false;
1386
1387       return true;
1388
1389     default:
1390       return false;
1391     }
1392 }
1393
1394 /* If REG has a single definition, replace it with its known value in EXPR.
1395    Callback for for_each_rtx.  */
1396
1397 static int
1398 replace_single_def_regs (rtx *reg, void *expr1)
1399 {
1400   unsigned regno;
1401   df_ref adef;
1402   rtx set, src;
1403   rtx *expr = (rtx *)expr1;
1404
1405   if (!REG_P (*reg))
1406     return 0;
1407
1408   regno = REGNO (*reg);
1409   for (;;)
1410     {
1411       rtx note;
1412       adef = DF_REG_DEF_CHAIN (regno);
1413       if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1414             || DF_REF_IS_ARTIFICIAL (adef))
1415         return -1;
1416
1417       set = single_set (DF_REF_INSN (adef));
1418       if (set == NULL || !REG_P (SET_DEST (set))
1419           || REGNO (SET_DEST (set)) != regno)
1420         return -1;
1421
1422       note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1423
1424       if (note && function_invariant_p (XEXP (note, 0)))
1425         {
1426           src = XEXP (note, 0);
1427           break;
1428         }
1429       src = SET_SRC (set);
1430
1431       if (REG_P (src))
1432         {
1433           regno = REGNO (src);
1434           continue;
1435         }
1436       break;
1437     }
1438   if (!function_invariant_p (src))
1439     return -1;
1440
1441   *expr = simplify_replace_rtx (*expr, *reg, src);
1442   return 1;
1443 }
1444
1445 /* A subroutine of simplify_using_initial_values, this function examines INSN
1446    to see if it contains a suitable set that we can use to make a replacement.
1447    If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1448    the set; return false otherwise.  */
1449
1450 static bool
1451 suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
1452 {
1453   rtx set = single_set (insn);
1454   rtx lhs = NULL_RTX, rhs;
1455
1456   if (!set)
1457     return false;
1458
1459   lhs = SET_DEST (set);
1460   if (!REG_P (lhs))
1461     return false;
1462
1463   rhs = find_reg_equal_equiv_note (insn);
1464   if (rhs)
1465     rhs = XEXP (rhs, 0);
1466   else
1467     rhs = SET_SRC (set);
1468
1469   if (!simple_rhs_p (rhs))
1470     return false;
1471
1472   *dest = lhs;
1473   *src = rhs;
1474   return true;
1475 }
1476
1477 /* Using the data returned by suitable_set_for_replacement, replace DEST
1478    with SRC in *EXPR and return the new expression.  Also call
1479    replace_single_def_regs if the replacement changed something.  */
1480 static void
1481 replace_in_expr (rtx *expr, rtx dest, rtx src)
1482 {
1483   rtx old = *expr;
1484   *expr = simplify_replace_rtx (*expr, dest, src);
1485   if (old == *expr)
1486     return;
1487   while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
1488     continue;
1489 }
1490
1491 /* Checks whether A implies B.  */
1492
1493 static bool
1494 implies_p (rtx a, rtx b)
1495 {
1496   rtx op0, op1, opb0, opb1, r;
1497   enum machine_mode mode;
1498
1499   if (rtx_equal_p (a, b))
1500     return true;
1501
1502   if (GET_CODE (a) == EQ)
1503     {
1504       op0 = XEXP (a, 0);
1505       op1 = XEXP (a, 1);
1506
1507       if (REG_P (op0)
1508           || (GET_CODE (op0) == SUBREG
1509               && REG_P (SUBREG_REG (op0))))
1510         {
1511           r = simplify_replace_rtx (b, op0, op1);
1512           if (r == const_true_rtx)
1513             return true;
1514         }
1515
1516       if (REG_P (op1)
1517           || (GET_CODE (op1) == SUBREG
1518               && REG_P (SUBREG_REG (op1))))
1519         {
1520           r = simplify_replace_rtx (b, op1, op0);
1521           if (r == const_true_rtx)
1522             return true;
1523         }
1524     }
1525
1526   if (b == const_true_rtx)
1527     return true;
1528
1529   if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1530        && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1531       || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1532           && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1533     return false;
1534
1535   op0 = XEXP (a, 0);
1536   op1 = XEXP (a, 1);
1537   opb0 = XEXP (b, 0);
1538   opb1 = XEXP (b, 1);
1539
1540   mode = GET_MODE (op0);
1541   if (mode != GET_MODE (opb0))
1542     mode = VOIDmode;
1543   else if (mode == VOIDmode)
1544     {
1545       mode = GET_MODE (op1);
1546       if (mode != GET_MODE (opb1))
1547         mode = VOIDmode;
1548     }
1549
1550   /* A < B implies A + 1 <= B.  */
1551   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1552       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1553     {
1554
1555       if (GET_CODE (a) == GT)
1556         {
1557           r = op0;
1558           op0 = op1;
1559           op1 = r;
1560         }
1561
1562       if (GET_CODE (b) == GE)
1563         {
1564           r = opb0;
1565           opb0 = opb1;
1566           opb1 = r;
1567         }
1568
1569       if (SCALAR_INT_MODE_P (mode)
1570           && rtx_equal_p (op1, opb1)
1571           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1572         return true;
1573       return false;
1574     }
1575
1576   /* A < B or A > B imply A != B.  TODO: Likewise
1577      A + n < B implies A != B + n if neither wraps.  */
1578   if (GET_CODE (b) == NE
1579       && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1580           || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1581     {
1582       if (rtx_equal_p (op0, opb0)
1583           && rtx_equal_p (op1, opb1))
1584         return true;
1585     }
1586
1587   /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
1588   if (GET_CODE (a) == NE
1589       && op1 == const0_rtx)
1590     {
1591       if ((GET_CODE (b) == GTU
1592            && opb1 == const0_rtx)
1593           || (GET_CODE (b) == GEU
1594               && opb1 == const1_rtx))
1595         return rtx_equal_p (op0, opb0);
1596     }
1597
1598   /* A != N is equivalent to A - (N + 1) <u -1.  */
1599   if (GET_CODE (a) == NE
1600       && CONST_INT_P (op1)
1601       && GET_CODE (b) == LTU
1602       && opb1 == constm1_rtx
1603       && GET_CODE (opb0) == PLUS
1604       && CONST_INT_P (XEXP (opb0, 1))
1605       /* Avoid overflows.  */
1606       && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1607           != ((unsigned HOST_WIDE_INT)1
1608               << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1609       && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1610     return rtx_equal_p (op0, XEXP (opb0, 0));
1611
1612   /* Likewise, A != N implies A - N > 0.  */
1613   if (GET_CODE (a) == NE
1614       && CONST_INT_P (op1))
1615     {
1616       if (GET_CODE (b) == GTU
1617           && GET_CODE (opb0) == PLUS
1618           && opb1 == const0_rtx
1619           && CONST_INT_P (XEXP (opb0, 1))
1620           /* Avoid overflows.  */
1621           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1622               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1623           && rtx_equal_p (XEXP (opb0, 0), op0))
1624         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1625       if (GET_CODE (b) == GEU
1626           && GET_CODE (opb0) == PLUS
1627           && opb1 == const1_rtx
1628           && CONST_INT_P (XEXP (opb0, 1))
1629           /* Avoid overflows.  */
1630           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1631               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1632           && rtx_equal_p (XEXP (opb0, 0), op0))
1633         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1634     }
1635
1636   /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
1637   if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1638       && CONST_INT_P (op1)
1639       && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1640           || INTVAL (op1) >= 0)
1641       && GET_CODE (b) == LTU
1642       && CONST_INT_P (opb1)
1643       && rtx_equal_p (op0, opb0))
1644     return INTVAL (opb1) < 0;
1645
1646   return false;
1647 }
1648
1649 /* Canonicalizes COND so that
1650
1651    (1) Ensure that operands are ordered according to
1652        swap_commutative_operands_p.
1653    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1654        for GE, GEU, and LEU.  */
1655
1656 rtx
1657 canon_condition (rtx cond)
1658 {
1659   rtx tem;
1660   rtx op0, op1;
1661   enum rtx_code code;
1662   enum machine_mode mode;
1663
1664   code = GET_CODE (cond);
1665   op0 = XEXP (cond, 0);
1666   op1 = XEXP (cond, 1);
1667
1668   if (swap_commutative_operands_p (op0, op1))
1669     {
1670       code = swap_condition (code);
1671       tem = op0;
1672       op0 = op1;
1673       op1 = tem;
1674     }
1675
1676   mode = GET_MODE (op0);
1677   if (mode == VOIDmode)
1678     mode = GET_MODE (op1);
1679   gcc_assert (mode != VOIDmode);
1680
1681   if (CONST_INT_P (op1)
1682       && GET_MODE_CLASS (mode) != MODE_CC
1683       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1684     {
1685       HOST_WIDE_INT const_val = INTVAL (op1);
1686       unsigned HOST_WIDE_INT uconst_val = const_val;
1687       unsigned HOST_WIDE_INT max_val
1688         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1689
1690       switch (code)
1691         {
1692         case LE:
1693           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1694             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1695           break;
1696
1697         /* When cross-compiling, const_val might be sign-extended from
1698            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1699         case GE:
1700           if ((HOST_WIDE_INT) (const_val & max_val)
1701               != (((HOST_WIDE_INT) 1
1702                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1703             code = GT, op1 = gen_int_mode (const_val - 1, mode);
1704           break;
1705
1706         case LEU:
1707           if (uconst_val < max_val)
1708             code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1709           break;
1710
1711         case GEU:
1712           if (uconst_val != 0)
1713             code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1714           break;
1715
1716         default:
1717           break;
1718         }
1719     }
1720
1721   if (op0 != XEXP (cond, 0)
1722       || op1 != XEXP (cond, 1)
1723       || code != GET_CODE (cond)
1724       || GET_MODE (cond) != SImode)
1725     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1726
1727   return cond;
1728 }
1729
1730 /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1731    set of altered regs.  */
1732
1733 void
1734 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1735 {
1736   rtx rev, reve, exp = *expr;
1737
1738   /* If some register gets altered later, we do not really speak about its
1739      value at the time of comparison.  */
1740   if (altered
1741       && for_each_rtx (&cond, altered_reg_used, altered))
1742     return;
1743
1744   if (GET_CODE (cond) == EQ
1745       && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1746     {
1747       *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1748       return;
1749     }
1750
1751   if (!COMPARISON_P (exp))
1752     return;
1753
1754   rev = reversed_condition (cond);
1755   reve = reversed_condition (exp);
1756
1757   cond = canon_condition (cond);
1758   exp = canon_condition (exp);
1759   if (rev)
1760     rev = canon_condition (rev);
1761   if (reve)
1762     reve = canon_condition (reve);
1763
1764   if (rtx_equal_p (exp, cond))
1765     {
1766       *expr = const_true_rtx;
1767       return;
1768     }
1769
1770   if (rev && rtx_equal_p (exp, rev))
1771     {
1772       *expr = const0_rtx;
1773       return;
1774     }
1775
1776   if (implies_p (cond, exp))
1777     {
1778       *expr = const_true_rtx;
1779       return;
1780     }
1781
1782   if (reve && implies_p (cond, reve))
1783     {
1784       *expr = const0_rtx;
1785       return;
1786     }
1787
1788   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1789      be false.  */
1790   if (rev && implies_p (exp, rev))
1791     {
1792       *expr = const0_rtx;
1793       return;
1794     }
1795
1796   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1797   if (rev && reve && implies_p (reve, rev))
1798     {
1799       *expr = const_true_rtx;
1800       return;
1801     }
1802
1803   /* We would like to have some other tests here.  TODO.  */
1804
1805   return;
1806 }
1807
1808 /* Use relationship between A and *B to eventually eliminate *B.
1809    OP is the operation we consider.  */
1810
1811 static void
1812 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1813 {
1814   switch (op)
1815     {
1816     case AND:
1817       /* If A implies *B, we may replace *B by true.  */
1818       if (implies_p (a, *b))
1819         *b = const_true_rtx;
1820       break;
1821
1822     case IOR:
1823       /* If *B implies A, we may replace *B by false.  */
1824       if (implies_p (*b, a))
1825         *b = const0_rtx;
1826       break;
1827
1828     default:
1829       gcc_unreachable ();
1830     }
1831 }
1832
1833 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1834    operation we consider.  */
1835
1836 static void
1837 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1838 {
1839   rtx elt;
1840
1841   for (elt = tail; elt; elt = XEXP (elt, 1))
1842     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1843   for (elt = tail; elt; elt = XEXP (elt, 1))
1844     eliminate_implied_condition (op, XEXP (elt, 0), head);
1845 }
1846
1847 /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1848    is a list, its elements are assumed to be combined using OP.  */
1849
1850 static void
1851 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1852 {
1853   bool expression_valid;
1854   rtx head, tail, insn, cond_list, last_valid_expr;
1855   rtx neutral, aggr;
1856   regset altered, this_altered;
1857   edge e;
1858
1859   if (!*expr)
1860     return;
1861
1862   if (CONSTANT_P (*expr))
1863     return;
1864
1865   if (GET_CODE (*expr) == EXPR_LIST)
1866     {
1867       head = XEXP (*expr, 0);
1868       tail = XEXP (*expr, 1);
1869
1870       eliminate_implied_conditions (op, &head, tail);
1871
1872       switch (op)
1873         {
1874         case AND:
1875           neutral = const_true_rtx;
1876           aggr = const0_rtx;
1877           break;
1878
1879         case IOR:
1880           neutral = const0_rtx;
1881           aggr = const_true_rtx;
1882           break;
1883
1884         default:
1885           gcc_unreachable ();
1886         }
1887
1888       simplify_using_initial_values (loop, UNKNOWN, &head);
1889       if (head == aggr)
1890         {
1891           XEXP (*expr, 0) = aggr;
1892           XEXP (*expr, 1) = NULL_RTX;
1893           return;
1894         }
1895       else if (head == neutral)
1896         {
1897           *expr = tail;
1898           simplify_using_initial_values (loop, op, expr);
1899           return;
1900         }
1901       simplify_using_initial_values (loop, op, &tail);
1902
1903       if (tail && XEXP (tail, 0) == aggr)
1904         {
1905           *expr = tail;
1906           return;
1907         }
1908
1909       XEXP (*expr, 0) = head;
1910       XEXP (*expr, 1) = tail;
1911       return;
1912     }
1913
1914   gcc_assert (op == UNKNOWN);
1915
1916   for (;;)
1917     if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
1918       break;
1919   if (CONSTANT_P (*expr))
1920     return;
1921
1922   e = loop_preheader_edge (loop);
1923   if (e->src == ENTRY_BLOCK_PTR)
1924     return;
1925
1926   altered = ALLOC_REG_SET (&reg_obstack);
1927   this_altered = ALLOC_REG_SET (&reg_obstack);
1928
1929   expression_valid = true;
1930   last_valid_expr = *expr;
1931   cond_list = NULL_RTX;
1932   while (1)
1933     {
1934       insn = BB_END (e->src);
1935       if (any_condjump_p (insn))
1936         {
1937           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1938
1939           if (cond && (e->flags & EDGE_FALLTHRU))
1940             cond = reversed_condition (cond);
1941           if (cond)
1942             {
1943               rtx old = *expr;
1944               simplify_using_condition (cond, expr, altered);
1945               if (old != *expr)
1946                 {
1947                   rtx note;
1948                   if (CONSTANT_P (*expr))
1949                     goto out;
1950                   for (note = cond_list; note; note = XEXP (note, 1))
1951                     {
1952                       simplify_using_condition (XEXP (note, 0), expr, altered);
1953                       if (CONSTANT_P (*expr))
1954                         goto out;
1955                     }
1956                 }
1957               cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1958             }
1959         }
1960
1961       FOR_BB_INSNS_REVERSE (e->src, insn)
1962         {
1963           rtx src, dest;
1964           rtx old = *expr;
1965
1966           if (!INSN_P (insn))
1967             continue;
1968
1969           CLEAR_REG_SET (this_altered);
1970           note_stores (PATTERN (insn), mark_altered, this_altered);
1971           if (CALL_P (insn))
1972             {
1973               /* Kill all call clobbered registers.  */
1974               unsigned int i;
1975               hard_reg_set_iterator hrsi;
1976               EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call,
1977                                               0, i, hrsi)
1978                 SET_REGNO_REG_SET (this_altered, i);
1979             }
1980
1981           if (suitable_set_for_replacement (insn, &dest, &src))
1982             {
1983               rtx *pnote, *pnote_next;
1984
1985               replace_in_expr (expr, dest, src);
1986               if (CONSTANT_P (*expr))
1987                 goto out;
1988
1989               for (pnote = &cond_list; *pnote; pnote = pnote_next)
1990                 {
1991                   rtx note = *pnote;
1992                   rtx old_cond = XEXP (note, 0);
1993
1994                   pnote_next = &XEXP (note, 1);
1995                   replace_in_expr (&XEXP (note, 0), dest, src);
1996
1997                   /* We can no longer use a condition that has been simplified
1998                      to a constant, and simplify_using_condition will abort if
1999                      we try.  */
2000                   if (CONSTANT_P (XEXP (note, 0)))
2001                     {
2002                       *pnote = *pnote_next;
2003                       pnote_next = pnote;
2004                       free_EXPR_LIST_node (note);
2005                     }
2006                   /* Retry simplifications with this condition if either the
2007                      expression or the condition changed.  */
2008                   else if (old_cond != XEXP (note, 0) || old != *expr)
2009                     simplify_using_condition (XEXP (note, 0), expr, altered);
2010                 }
2011             }
2012           else
2013             {
2014               rtx *pnote, *pnote_next;
2015
2016               /* If we did not use this insn to make a replacement, any overlap
2017                  between stores in this insn and our expression will cause the
2018                  expression to become invalid.  */
2019               if (for_each_rtx (expr, altered_reg_used, this_altered))
2020                 goto out;
2021
2022               /* Likewise for the conditions.  */
2023               for (pnote = &cond_list; *pnote; pnote = pnote_next)
2024                 {
2025                   rtx note = *pnote;
2026                   rtx old_cond = XEXP (note, 0);
2027
2028                   pnote_next = &XEXP (note, 1);
2029                   if (for_each_rtx (&old_cond, altered_reg_used, this_altered))
2030                     {
2031                       *pnote = *pnote_next;
2032                       pnote_next = pnote;
2033                       free_EXPR_LIST_node (note);
2034                     }
2035                 }
2036             }
2037
2038           if (CONSTANT_P (*expr))
2039             goto out;
2040
2041           IOR_REG_SET (altered, this_altered);
2042
2043           /* If the expression now contains regs that have been altered, we
2044              can't return it to the caller.  However, it is still valid for
2045              further simplification, so keep searching to see if we can
2046              eventually turn it into a constant.  */
2047           if (for_each_rtx (expr, altered_reg_used, altered))
2048             expression_valid = false;
2049           if (expression_valid)
2050             last_valid_expr = *expr;
2051         }
2052
2053       if (!single_pred_p (e->src)
2054           || single_pred (e->src) == ENTRY_BLOCK_PTR)
2055         break;
2056       e = single_pred_edge (e->src);
2057     }
2058
2059  out:
2060   free_EXPR_LIST_list (&cond_list);
2061   if (!CONSTANT_P (*expr))
2062     *expr = last_valid_expr;
2063   FREE_REG_SET (altered);
2064   FREE_REG_SET (this_altered);
2065 }
2066
2067 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
2068    that IV occurs as left operands of comparison COND and its signedness
2069    is SIGNED_P to DESC.  */
2070
2071 static void
2072 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
2073                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
2074 {
2075   rtx mmin, mmax, cond_over, cond_under;
2076
2077   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2078   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2079                                         iv->base, mmin);
2080   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2081                                        iv->base, mmax);
2082
2083   switch (cond)
2084     {
2085       case LE:
2086       case LT:
2087       case LEU:
2088       case LTU:
2089         if (cond_under != const0_rtx)
2090           desc->infinite =
2091                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
2092         if (cond_over != const0_rtx)
2093           desc->noloop_assumptions =
2094                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2095         break;
2096
2097       case GE:
2098       case GT:
2099       case GEU:
2100       case GTU:
2101         if (cond_over != const0_rtx)
2102           desc->infinite =
2103                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
2104         if (cond_under != const0_rtx)
2105           desc->noloop_assumptions =
2106                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2107         break;
2108
2109       case NE:
2110         if (cond_over != const0_rtx)
2111           desc->infinite =
2112                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
2113         if (cond_under != const0_rtx)
2114           desc->infinite =
2115                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
2116         break;
2117
2118       default:
2119         gcc_unreachable ();
2120     }
2121
2122   iv->mode = mode;
2123   iv->extend = signed_p ? IV_SIGN_EXTEND : IV_ZERO_EXTEND;
2124 }
2125
2126 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2127    subregs of the same mode if possible (sometimes it is necessary to add
2128    some assumptions to DESC).  */
2129
2130 static bool
2131 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
2132                          enum rtx_code cond, struct niter_desc *desc)
2133 {
2134   enum machine_mode comp_mode;
2135   bool signed_p;
2136
2137   /* If the ivs behave specially in the first iteration, or are
2138      added/multiplied after extending, we ignore them.  */
2139   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2140     return false;
2141   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2142     return false;
2143
2144   /* If there is some extend, it must match signedness of the comparison.  */
2145   switch (cond)
2146     {
2147       case LE:
2148       case LT:
2149         if (iv0->extend == IV_ZERO_EXTEND
2150             || iv1->extend == IV_ZERO_EXTEND)
2151           return false;
2152         signed_p = true;
2153         break;
2154
2155       case LEU:
2156       case LTU:
2157         if (iv0->extend == IV_SIGN_EXTEND
2158             || iv1->extend == IV_SIGN_EXTEND)
2159           return false;
2160         signed_p = false;
2161         break;
2162
2163       case NE:
2164         if (iv0->extend != IV_UNKNOWN_EXTEND
2165             && iv1->extend != IV_UNKNOWN_EXTEND
2166             && iv0->extend != iv1->extend)
2167           return false;
2168
2169         signed_p = false;
2170         if (iv0->extend != IV_UNKNOWN_EXTEND)
2171           signed_p = iv0->extend == IV_SIGN_EXTEND;
2172         if (iv1->extend != IV_UNKNOWN_EXTEND)
2173           signed_p = iv1->extend == IV_SIGN_EXTEND;
2174         break;
2175
2176       default:
2177         gcc_unreachable ();
2178     }
2179
2180   /* Values of both variables should be computed in the same mode.  These
2181      might indeed be different, if we have comparison like
2182
2183      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2184
2185      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2186      in different modes.  This does not seem impossible to handle, but
2187      it hardly ever occurs in practice.
2188
2189      The only exception is the case when one of operands is invariant.
2190      For example pentium 3 generates comparisons like
2191      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
2192      definitely do not want this prevent the optimization.  */
2193   comp_mode = iv0->extend_mode;
2194   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2195     comp_mode = iv1->extend_mode;
2196
2197   if (iv0->extend_mode != comp_mode)
2198     {
2199       if (iv0->mode != iv0->extend_mode
2200           || iv0->step != const0_rtx)
2201         return false;
2202
2203       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2204                                       comp_mode, iv0->base, iv0->mode);
2205       iv0->extend_mode = comp_mode;
2206     }
2207
2208   if (iv1->extend_mode != comp_mode)
2209     {
2210       if (iv1->mode != iv1->extend_mode
2211           || iv1->step != const0_rtx)
2212         return false;
2213
2214       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2215                                       comp_mode, iv1->base, iv1->mode);
2216       iv1->extend_mode = comp_mode;
2217     }
2218
2219   /* Check that both ivs belong to a range of a single mode.  If one of the
2220      operands is an invariant, we may need to shorten it into the common
2221      mode.  */
2222   if (iv0->mode == iv0->extend_mode
2223       && iv0->step == const0_rtx
2224       && iv0->mode != iv1->mode)
2225     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2226
2227   if (iv1->mode == iv1->extend_mode
2228       && iv1->step == const0_rtx
2229       && iv0->mode != iv1->mode)
2230     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2231
2232   if (iv0->mode != iv1->mode)
2233     return false;
2234
2235   desc->mode = iv0->mode;
2236   desc->signed_p = signed_p;
2237
2238   return true;
2239 }
2240
2241 /* Tries to estimate the maximum number of iterations in LOOP, and return the
2242    result.  This function is called from iv_number_of_iterations with
2243    a number of fields in DESC already filled in.  OLD_NITER is the original
2244    expression for the number of iterations, before we tried to simplify it.  */
2245
2246 static unsigned HOST_WIDEST_INT
2247 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
2248 {
2249   rtx niter = desc->niter_expr;
2250   rtx mmin, mmax, cmp;
2251   unsigned HOST_WIDEST_INT nmax, inc;
2252   unsigned HOST_WIDEST_INT andmax = 0;
2253
2254   /* We used to look for constant operand 0 of AND,
2255      but canonicalization should always make this impossible.  */
2256   gcc_checking_assert (GET_CODE (niter) != AND
2257                        || !CONST_INT_P (XEXP (niter, 0)));
2258
2259   if (GET_CODE (niter) == AND
2260       && CONST_INT_P (XEXP (niter, 1)))
2261     {
2262       andmax = UINTVAL (XEXP (niter, 1));
2263       niter = XEXP (niter, 0);
2264     }
2265
2266   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2267   nmax = INTVAL (mmax) - INTVAL (mmin);
2268
2269   if (GET_CODE (niter) == UDIV)
2270     {
2271       if (!CONST_INT_P (XEXP (niter, 1)))
2272         return nmax;
2273       inc = INTVAL (XEXP (niter, 1));
2274       niter = XEXP (niter, 0);
2275     }
2276   else
2277     inc = 1;
2278
2279   /* We could use a binary search here, but for now improving the upper
2280      bound by just one eliminates one important corner case.  */
2281   cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2282                                  desc->mode, old_niter, mmax);
2283   simplify_using_initial_values (loop, UNKNOWN, &cmp);
2284   if (cmp == const_true_rtx)
2285     {
2286       nmax--;
2287
2288       if (dump_file)
2289         fprintf (dump_file, ";; improved upper bound by one.\n");
2290     }
2291   nmax /= inc;
2292   if (andmax)
2293     nmax = MIN (nmax, andmax);
2294   if (dump_file)
2295     fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n",
2296              nmax);
2297   return nmax;
2298 }
2299
2300 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2301    the result into DESC.  Very similar to determine_number_of_iterations
2302    (basically its rtl version), complicated by things like subregs.  */
2303
2304 static void
2305 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2306                          struct niter_desc *desc)
2307 {
2308   rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2309   struct rtx_iv iv0, iv1, tmp_iv;
2310   rtx assumption, may_not_xform;
2311   enum rtx_code cond;
2312   enum machine_mode mode, comp_mode;
2313   rtx mmin, mmax, mode_mmin, mode_mmax;
2314   unsigned HOST_WIDEST_INT s, size, d, inv, max;
2315   HOST_WIDEST_INT up, down, inc, step_val;
2316   int was_sharp = false;
2317   rtx old_niter;
2318   bool step_is_pow2;
2319
2320   /* The meaning of these assumptions is this:
2321      if !assumptions
2322        then the rest of information does not have to be valid
2323      if noloop_assumptions then the loop does not roll
2324      if infinite then this exit is never used */
2325
2326   desc->assumptions = NULL_RTX;
2327   desc->noloop_assumptions = NULL_RTX;
2328   desc->infinite = NULL_RTX;
2329   desc->simple_p = true;
2330
2331   desc->const_iter = false;
2332   desc->niter_expr = NULL_RTX;
2333
2334   cond = GET_CODE (condition);
2335   gcc_assert (COMPARISON_P (condition));
2336
2337   mode = GET_MODE (XEXP (condition, 0));
2338   if (mode == VOIDmode)
2339     mode = GET_MODE (XEXP (condition, 1));
2340   /* The constant comparisons should be folded.  */
2341   gcc_assert (mode != VOIDmode);
2342
2343   /* We only handle integers or pointers.  */
2344   if (GET_MODE_CLASS (mode) != MODE_INT
2345       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2346     goto fail;
2347
2348   op0 = XEXP (condition, 0);
2349   if (!iv_analyze (insn, op0, &iv0))
2350     goto fail;
2351   if (iv0.extend_mode == VOIDmode)
2352     iv0.mode = iv0.extend_mode = mode;
2353
2354   op1 = XEXP (condition, 1);
2355   if (!iv_analyze (insn, op1, &iv1))
2356     goto fail;
2357   if (iv1.extend_mode == VOIDmode)
2358     iv1.mode = iv1.extend_mode = mode;
2359
2360   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2361       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2362     goto fail;
2363
2364   /* Check condition and normalize it.  */
2365
2366   switch (cond)
2367     {
2368       case GE:
2369       case GT:
2370       case GEU:
2371       case GTU:
2372         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2373         cond = swap_condition (cond);
2374         break;
2375       case NE:
2376       case LE:
2377       case LEU:
2378       case LT:
2379       case LTU:
2380         break;
2381       default:
2382         goto fail;
2383     }
2384
2385   /* Handle extends.  This is relatively nontrivial, so we only try in some
2386      easy cases, when we can canonicalize the ivs (possibly by adding some
2387      assumptions) to shape subreg (base + i * step).  This function also fills
2388      in desc->mode and desc->signed_p.  */
2389
2390   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2391     goto fail;
2392
2393   comp_mode = iv0.extend_mode;
2394   mode = iv0.mode;
2395   size = GET_MODE_BITSIZE (mode);
2396   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2397   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2398   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2399
2400   if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
2401     goto fail;
2402
2403   /* We can take care of the case of two induction variables chasing each other
2404      if the test is NE. I have never seen a loop using it, but still it is
2405      cool.  */
2406   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2407     {
2408       if (cond != NE)
2409         goto fail;
2410
2411       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2412       iv1.step = const0_rtx;
2413     }
2414
2415   iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2416   iv1.step = lowpart_subreg (mode, iv1.step, comp_mode);
2417
2418   /* This is either infinite loop or the one that ends immediately, depending
2419      on initial values.  Unswitching should remove this kind of conditions.  */
2420   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2421     goto fail;
2422
2423   if (cond != NE)
2424     {
2425       if (iv0.step == const0_rtx)
2426         step_val = -INTVAL (iv1.step);
2427       else
2428         step_val = INTVAL (iv0.step);
2429
2430       /* Ignore loops of while (i-- < 10) type.  */
2431       if (step_val < 0)
2432         goto fail;
2433
2434       step_is_pow2 = !(step_val & (step_val - 1));
2435     }
2436   else
2437     {
2438       /* We do not care about whether the step is power of two in this
2439          case.  */
2440       step_is_pow2 = false;
2441       step_val = 0;
2442     }
2443
2444   /* Some more condition normalization.  We must record some assumptions
2445      due to overflows.  */
2446   switch (cond)
2447     {
2448       case LT:
2449       case LTU:
2450         /* We want to take care only of non-sharp relationals; this is easy,
2451            as in cases the overflow would make the transformation unsafe
2452            the loop does not roll.  Seemingly it would make more sense to want
2453            to take care of sharp relationals instead, as NE is more similar to
2454            them, but the problem is that here the transformation would be more
2455            difficult due to possibly infinite loops.  */
2456         if (iv0.step == const0_rtx)
2457           {
2458             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2459             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2460                                                   mode_mmax);
2461             if (assumption == const_true_rtx)
2462               goto zero_iter_simplify;
2463             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2464                                             iv0.base, const1_rtx);
2465           }
2466         else
2467           {
2468             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2469             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2470                                                   mode_mmin);
2471             if (assumption == const_true_rtx)
2472               goto zero_iter_simplify;
2473             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2474                                             iv1.base, constm1_rtx);
2475           }
2476
2477         if (assumption != const0_rtx)
2478           desc->noloop_assumptions =
2479                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2480         cond = (cond == LT) ? LE : LEU;
2481
2482         /* It will be useful to be able to tell the difference once more in
2483            LE -> NE reduction.  */
2484         was_sharp = true;
2485         break;
2486       default: ;
2487     }
2488
2489   /* Take care of trivially infinite loops.  */
2490   if (cond != NE)
2491     {
2492       if (iv0.step == const0_rtx)
2493         {
2494           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2495           if (rtx_equal_p (tmp, mode_mmin))
2496             {
2497               desc->infinite =
2498                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2499               /* Fill in the remaining fields somehow.  */
2500               goto zero_iter_simplify;
2501             }
2502         }
2503       else
2504         {
2505           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2506           if (rtx_equal_p (tmp, mode_mmax))
2507             {
2508               desc->infinite =
2509                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2510               /* Fill in the remaining fields somehow.  */
2511               goto zero_iter_simplify;
2512             }
2513         }
2514     }
2515
2516   /* If we can we want to take care of NE conditions instead of size
2517      comparisons, as they are much more friendly (most importantly
2518      this takes care of special handling of loops with step 1).  We can
2519      do it if we first check that upper bound is greater or equal to
2520      lower bound, their difference is constant c modulo step and that
2521      there is not an overflow.  */
2522   if (cond != NE)
2523     {
2524       if (iv0.step == const0_rtx)
2525         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2526       else
2527         step = iv0.step;
2528       step = lowpart_subreg (mode, step, comp_mode);
2529       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2530       delta = lowpart_subreg (mode, delta, comp_mode);
2531       delta = simplify_gen_binary (UMOD, mode, delta, step);
2532       may_xform = const0_rtx;
2533       may_not_xform = const_true_rtx;
2534
2535       if (CONST_INT_P (delta))
2536         {
2537           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2538             {
2539               /* A special case.  We have transformed condition of type
2540                  for (i = 0; i < 4; i += 4)
2541                  into
2542                  for (i = 0; i <= 3; i += 4)
2543                  obviously if the test for overflow during that transformation
2544                  passed, we cannot overflow here.  Most importantly any
2545                  loop with sharp end condition and step 1 falls into this
2546                  category, so handling this case specially is definitely
2547                  worth the troubles.  */
2548               may_xform = const_true_rtx;
2549             }
2550           else if (iv0.step == const0_rtx)
2551             {
2552               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2553               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2554               bound = lowpart_subreg (mode, bound, comp_mode);
2555               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2556               may_xform = simplify_gen_relational (cond, SImode, mode,
2557                                                    bound, tmp);
2558               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2559                                                        SImode, mode,
2560                                                        bound, tmp);
2561             }
2562           else
2563             {
2564               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2565               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2566               bound = lowpart_subreg (mode, bound, comp_mode);
2567               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2568               may_xform = simplify_gen_relational (cond, SImode, mode,
2569                                                    tmp, bound);
2570               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2571                                                        SImode, mode,
2572                                                        tmp, bound);
2573             }
2574         }
2575
2576       if (may_xform != const0_rtx)
2577         {
2578           /* We perform the transformation always provided that it is not
2579              completely senseless.  This is OK, as we would need this assumption
2580              to determine the number of iterations anyway.  */
2581           if (may_xform != const_true_rtx)
2582             {
2583               /* If the step is a power of two and the final value we have
2584                  computed overflows, the cycle is infinite.  Otherwise it
2585                  is nontrivial to compute the number of iterations.  */
2586               if (step_is_pow2)
2587                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2588                                                   desc->infinite);
2589               else
2590                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2591                                                      desc->assumptions);
2592             }
2593
2594           /* We are going to lose some information about upper bound on
2595              number of iterations in this step, so record the information
2596              here.  */
2597           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2598           if (CONST_INT_P (iv1.base))
2599             up = INTVAL (iv1.base);
2600           else
2601             up = INTVAL (mode_mmax) - inc;
2602           down = INTVAL (CONST_INT_P (iv0.base)
2603                          ? iv0.base
2604                          : mode_mmin);
2605           max = (up - down) / inc + 1;
2606           if (!desc->infinite
2607               && !desc->assumptions)
2608             record_niter_bound (loop, double_int::from_uhwi (max),
2609                                 false, true);
2610
2611           if (iv0.step == const0_rtx)
2612             {
2613               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2614               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2615             }
2616           else
2617             {
2618               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2619               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2620             }
2621
2622           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2623           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2624           assumption = simplify_gen_relational (reverse_condition (cond),
2625                                                 SImode, mode, tmp0, tmp1);
2626           if (assumption == const_true_rtx)
2627             goto zero_iter_simplify;
2628           else if (assumption != const0_rtx)
2629             desc->noloop_assumptions =
2630                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2631           cond = NE;
2632         }
2633     }
2634
2635   /* Count the number of iterations.  */
2636   if (cond == NE)
2637     {
2638       /* Everything we do here is just arithmetics modulo size of mode.  This
2639          makes us able to do more involved computations of number of iterations
2640          than in other cases.  First transform the condition into shape
2641          s * i <> c, with s positive.  */
2642       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2643       iv0.base = const0_rtx;
2644       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2645       iv1.step = const0_rtx;
2646       if (INTVAL (iv0.step) < 0)
2647         {
2648           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2649           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2650         }
2651       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2652
2653       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2654          is infinite.  Otherwise, the number of iterations is
2655          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2656       s = INTVAL (iv0.step); d = 1;
2657       while (s % 2 != 1)
2658         {
2659           s /= 2;
2660           d *= 2;
2661           size--;
2662         }
2663       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2664
2665       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2666       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2667       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2668       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2669
2670       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2671       inv = inverse (s, size);
2672       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2673       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2674     }
2675   else
2676     {
2677       if (iv1.step == const0_rtx)
2678         /* Condition in shape a + s * i <= b
2679            We must know that b + s does not overflow and a <= b + s and then we
2680            can compute number of iterations as (b + s - a) / s.  (It might
2681            seem that we in fact could be more clever about testing the b + s
2682            overflow condition using some information about b - a mod s,
2683            but it was already taken into account during LE -> NE transform).  */
2684         {
2685           step = iv0.step;
2686           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2687           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2688
2689           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2690                                        lowpart_subreg (mode, step,
2691                                                        comp_mode));
2692           if (step_is_pow2)
2693             {
2694               rtx t0, t1;
2695
2696               /* If s is power of 2, we know that the loop is infinite if
2697                  a % s <= b % s and b + s overflows.  */
2698               assumption = simplify_gen_relational (reverse_condition (cond),
2699                                                     SImode, mode,
2700                                                     tmp1, bound);
2701
2702               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2703               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2704               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2705               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2706               desc->infinite =
2707                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2708             }
2709           else
2710             {
2711               assumption = simplify_gen_relational (cond, SImode, mode,
2712                                                     tmp1, bound);
2713               desc->assumptions =
2714                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2715             }
2716
2717           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2718           tmp = lowpart_subreg (mode, tmp, comp_mode);
2719           assumption = simplify_gen_relational (reverse_condition (cond),
2720                                                 SImode, mode, tmp0, tmp);
2721
2722           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2723           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2724         }
2725       else
2726         {
2727           /* Condition in shape a <= b - s * i
2728              We must know that a - s does not overflow and a - s <= b and then
2729              we can again compute number of iterations as (b - (a - s)) / s.  */
2730           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2731           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2732           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2733
2734           bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2735                                        lowpart_subreg (mode, step, comp_mode));
2736           if (step_is_pow2)
2737             {
2738               rtx t0, t1;
2739
2740               /* If s is power of 2, we know that the loop is infinite if
2741                  a % s <= b % s and a - s overflows.  */
2742               assumption = simplify_gen_relational (reverse_condition (cond),
2743                                                     SImode, mode,
2744                                                     bound, tmp0);
2745
2746               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2747               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2748               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2749               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2750               desc->infinite =
2751                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2752             }
2753           else
2754             {
2755               assumption = simplify_gen_relational (cond, SImode, mode,
2756                                                     bound, tmp0);
2757               desc->assumptions =
2758                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2759             }
2760
2761           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2762           tmp = lowpart_subreg (mode, tmp, comp_mode);
2763           assumption = simplify_gen_relational (reverse_condition (cond),
2764                                                 SImode, mode,
2765                                                 tmp, tmp1);
2766           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2767           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2768         }
2769       if (assumption == const_true_rtx)
2770         goto zero_iter_simplify;
2771       else if (assumption != const0_rtx)
2772         desc->noloop_assumptions =
2773                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2774       delta = simplify_gen_binary (UDIV, mode, delta, step);
2775       desc->niter_expr = delta;
2776     }
2777
2778   old_niter = desc->niter_expr;
2779
2780   simplify_using_initial_values (loop, AND, &desc->assumptions);
2781   if (desc->assumptions
2782       && XEXP (desc->assumptions, 0) == const0_rtx)
2783     goto fail;
2784   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2785   simplify_using_initial_values (loop, IOR, &desc->infinite);
2786   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2787
2788   /* Rerun the simplification.  Consider code (created by copying loop headers)
2789
2790      i = 0;
2791
2792      if (0 < n)
2793        {
2794          do
2795            {
2796              i++;
2797            } while (i < n);
2798        }
2799
2800     The first pass determines that i = 0, the second pass uses it to eliminate
2801     noloop assumption.  */
2802
2803   simplify_using_initial_values (loop, AND, &desc->assumptions);
2804   if (desc->assumptions
2805       && XEXP (desc->assumptions, 0) == const0_rtx)
2806     goto fail;
2807   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2808   simplify_using_initial_values (loop, IOR, &desc->infinite);
2809   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2810
2811   if (desc->noloop_assumptions
2812       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2813     goto zero_iter;
2814
2815   if (CONST_INT_P (desc->niter_expr))
2816     {
2817       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2818
2819       desc->const_iter = true;
2820       desc->niter = val & GET_MODE_MASK (desc->mode);
2821       if (!desc->infinite
2822           && !desc->assumptions)
2823         record_niter_bound (loop, double_int::from_uhwi (desc->niter),
2824                             false, true);
2825     }
2826   else
2827     {
2828       max = determine_max_iter (loop, desc, old_niter);
2829       if (!max)
2830         goto zero_iter_simplify;
2831       if (!desc->infinite
2832           && !desc->assumptions)
2833         record_niter_bound (loop, double_int::from_uhwi (max),
2834                             false, true);
2835
2836       /* simplify_using_initial_values does a copy propagation on the registers
2837          in the expression for the number of iterations.  This prolongs life
2838          ranges of registers and increases register pressure, and usually
2839          brings no gain (and if it happens to do, the cse pass will take care
2840          of it anyway).  So prevent this behavior, unless it enabled us to
2841          derive that the number of iterations is a constant.  */
2842       desc->niter_expr = old_niter;
2843     }
2844
2845   return;
2846
2847 zero_iter_simplify:
2848   /* Simplify the assumptions.  */
2849   simplify_using_initial_values (loop, AND, &desc->assumptions);
2850   if (desc->assumptions
2851       && XEXP (desc->assumptions, 0) == const0_rtx)
2852     goto fail;
2853   simplify_using_initial_values (loop, IOR, &desc->infinite);
2854
2855   /* Fallthru.  */
2856 zero_iter:
2857   desc->const_iter = true;
2858   desc->niter = 0;
2859   record_niter_bound (loop, double_int_zero,
2860                       true, true);
2861   desc->noloop_assumptions = NULL_RTX;
2862   desc->niter_expr = const0_rtx;
2863   return;
2864
2865 fail:
2866   desc->simple_p = false;
2867   return;
2868 }
2869
2870 /* Checks whether E is a simple exit from LOOP and stores its description
2871    into DESC.  */
2872
2873 static void
2874 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2875 {
2876   basic_block exit_bb;
2877   rtx condition, at;
2878   edge ein;
2879
2880   exit_bb = e->src;
2881   desc->simple_p = false;
2882
2883   /* It must belong directly to the loop.  */
2884   if (exit_bb->loop_father != loop)
2885     return;
2886
2887   /* It must be tested (at least) once during any iteration.  */
2888   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2889     return;
2890
2891   /* It must end in a simple conditional jump.  */
2892   if (!any_condjump_p (BB_END (exit_bb)))
2893     return;
2894
2895   ein = EDGE_SUCC (exit_bb, 0);
2896   if (ein == e)
2897     ein = EDGE_SUCC (exit_bb, 1);
2898
2899   desc->out_edge = e;
2900   desc->in_edge = ein;
2901
2902   /* Test whether the condition is suitable.  */
2903   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2904     return;
2905
2906   if (ein->flags & EDGE_FALLTHRU)
2907     {
2908       condition = reversed_condition (condition);
2909       if (!condition)
2910         return;
2911     }
2912
2913   /* Check that we are able to determine number of iterations and fill
2914      in information about it.  */
2915   iv_number_of_iterations (loop, at, condition, desc);
2916 }
2917
2918 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2919
2920 void
2921 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2922 {
2923   unsigned i;
2924   basic_block *body;
2925   edge e;
2926   struct niter_desc act;
2927   bool any = false;
2928   edge_iterator ei;
2929
2930   desc->simple_p = false;
2931   body = get_loop_body (loop);
2932
2933   for (i = 0; i < loop->num_nodes; i++)
2934     {
2935       FOR_EACH_EDGE (e, ei, body[i]->succs)
2936         {
2937           if (flow_bb_inside_loop_p (loop, e->dest))
2938             continue;
2939
2940           check_simple_exit (loop, e, &act);
2941           if (!act.simple_p)
2942             continue;
2943
2944           if (!any)
2945             any = true;
2946           else
2947             {
2948               /* Prefer constant iterations; the less the better.  */
2949               if (!act.const_iter
2950                   || (desc->const_iter && act.niter >= desc->niter))
2951                 continue;
2952
2953               /* Also if the actual exit may be infinite, while the old one
2954                  not, prefer the old one.  */
2955               if (act.infinite && !desc->infinite)
2956                 continue;
2957             }
2958
2959           *desc = act;
2960         }
2961     }
2962
2963   if (dump_file)
2964     {
2965       if (desc->simple_p)
2966         {
2967           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2968           fprintf (dump_file, "  simple exit %d -> %d\n",
2969                    desc->out_edge->src->index,
2970                    desc->out_edge->dest->index);
2971           if (desc->assumptions)
2972             {
2973               fprintf (dump_file, "  assumptions: ");
2974               print_rtl (dump_file, desc->assumptions);
2975               fprintf (dump_file, "\n");
2976             }
2977           if (desc->noloop_assumptions)
2978             {
2979               fprintf (dump_file, "  does not roll if: ");
2980               print_rtl (dump_file, desc->noloop_assumptions);
2981               fprintf (dump_file, "\n");
2982             }
2983           if (desc->infinite)
2984             {
2985               fprintf (dump_file, "  infinite if: ");
2986               print_rtl (dump_file, desc->infinite);
2987               fprintf (dump_file, "\n");
2988             }
2989
2990           fprintf (dump_file, "  number of iterations: ");
2991           print_rtl (dump_file, desc->niter_expr);
2992           fprintf (dump_file, "\n");
2993
2994           fprintf (dump_file, "  upper bound: %li\n",
2995                    (long)max_loop_iterations_int (loop));
2996           fprintf (dump_file, "  realistic bound: %li\n",
2997                    (long)estimated_loop_iterations_int (loop));
2998         }
2999       else
3000         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
3001     }
3002
3003   free (body);
3004 }
3005
3006 /* Creates a simple loop description of LOOP if it was not computed
3007    already.  */
3008
3009 struct niter_desc *
3010 get_simple_loop_desc (struct loop *loop)
3011 {
3012   struct niter_desc *desc = simple_loop_desc (loop);
3013
3014   if (desc)
3015     return desc;
3016
3017   /* At least desc->infinite is not always initialized by
3018      find_simple_loop_exit.  */
3019   desc = XCNEW (struct niter_desc);
3020   iv_analysis_loop_init (loop);
3021   find_simple_exit (loop, desc);
3022   loop->aux = desc;
3023
3024   if (desc->simple_p && (desc->assumptions || desc->infinite))
3025     {
3026       const char *wording;
3027
3028       /* Assume that no overflow happens and that the loop is finite.
3029          We already warned at the tree level if we ran optimizations there.  */
3030       if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
3031         {
3032           if (desc->infinite)
3033             {
3034               wording =
3035                 flag_unsafe_loop_optimizations
3036                 ? N_("assuming that the loop is not infinite")
3037                 : N_("cannot optimize possibly infinite loops");
3038               warning (OPT_Wunsafe_loop_optimizations, "%s",
3039                        gettext (wording));
3040             }
3041           if (desc->assumptions)
3042             {
3043               wording =
3044                 flag_unsafe_loop_optimizations
3045                 ? N_("assuming that the loop counter does not overflow")
3046                 : N_("cannot optimize loop, the loop counter may overflow");
3047               warning (OPT_Wunsafe_loop_optimizations, "%s",
3048                        gettext (wording));
3049             }
3050         }
3051
3052       if (flag_unsafe_loop_optimizations)
3053         {
3054           desc->assumptions = NULL_RTX;
3055           desc->infinite = NULL_RTX;
3056         }
3057     }
3058
3059   return desc;
3060 }
3061
3062 /* Releases simple loop description for LOOP.  */
3063
3064 void
3065 free_simple_loop_desc (struct loop *loop)
3066 {
3067   struct niter_desc *desc = simple_loop_desc (loop);
3068
3069   if (!desc)
3070     return;
3071
3072   free (desc);
3073   loop->aux = NULL;
3074 }