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