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