gcc/loop-iv.c

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