contrib/gcc-4.4/gcc/loop-iv.c

   1 /* Rtl-level induction variable analysis.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This is a simple analysis of induction variables of the loop.  The major use
  22    is for determining the number of iterations of a loop for loop unrolling,
  23    doloop optimization and branch prediction.  The iv information is computed
  24    on demand.
  25
  26    Induction variables are analyzed by walking the use-def chains.  When
  27    a basic induction variable (biv) is found, it is cached in the bivs
  28    hash table.  When register is proved to be a biv, its description
  29    is stored to DF_REF_DATA of the def reference.
  30
  31    The analysis works always with one loop -- you must call
  32    iv_analysis_loop_init (loop) for it.  All the other functions then work with
  33    this loop.   When you need to work with another loop, just call
  34    iv_analysis_loop_init for it.  When you no longer need iv analysis, call
  35    iv_analysis_done () to clean up the memory.
  36
  37    The available functions are:
  38
  39    iv_analyze (insn, reg, iv): Stores the description of the induction variable
  40      corresponding to the use of register REG in INSN to IV.  Returns true if
  41      REG is an induction variable in INSN. false otherwise.
  42      If use of REG is not found in INSN, following insns are scanned (so that
  43      we may call this function on insn returned by get_condition).
  44    iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
  45      corresponding to DEF, which is a register defined in INSN.
  46    iv_analyze_expr (insn, rhs, mode, iv):  Stores to IV the description of iv
  47      corresponding to expression EXPR evaluated at INSN.  All registers used bu
  48      EXPR must also be used in INSN.
  49 */
  50
  51 #include "config.h"
  52 #include "system.h"
  53 #include "coretypes.h"
  54 #include "tm.h"
  55 #include "rtl.h"
  56 #include "hard-reg-set.h"
  57 #include "obstack.h"
  58 #include "basic-block.h"
  59 #include "cfgloop.h"
  60 #include "expr.h"
  61 #include "intl.h"
  62 #include "output.h"
  63 #include "toplev.h"
  64 #include "df.h"
  65 #include "hashtab.h"
  66
  67 /* Possible return values of iv_get_reaching_def.  */
  68
  69 enum iv_grd_result
  70 {
  71   /* More than one reaching def, or reaching def that does not
  72      dominate the use.  */
  73   GRD_INVALID,
  74
  75   /* The use is trivial invariant of the loop, i.e. is not changed
  76      inside the loop.  */
  77   GRD_INVARIANT,
  78
  79   /* The use is reached by initial value and a value from the
  80      previous iteration.  */
  81   GRD_MAYBE_BIV,
  82
  83   /* The use has single dominating def.  */
  84   GRD_SINGLE_DOM
  85 };
  86
  87 /* Information about a biv.  */
  88
  89 struct biv_entry
  90 {
  91   unsigned regno;       /* The register of the biv.  */
  92   struct rtx_iv iv;     /* Value of the biv.  */
  93 };
  94
  95 static bool clean_slate = true;
  96
  97 static unsigned int iv_ref_table_size = 0;
  98
  99 /* Table of rtx_ivs indexed by the df_ref uid field.  */
 100 static struct rtx_iv ** iv_ref_table;
 101
 102 /* Induction variable stored at the reference.  */
 103 #define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
 104 #define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
 105
 106 /* The current loop.  */
 107
 108 static struct loop *current_loop;
 109
 110 /* Bivs of the current loop.  */
 111
 112 static htab_t bivs;
 113
 114 static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
 115
 116 /* Dumps information about IV to FILE.  */
 117
 118 extern void dump_iv_info (FILE *, struct rtx_iv *);
 119 void
 120 dump_iv_info (FILE *file, struct rtx_iv *iv)
 121 {
 122   if (!iv->base)
 123     {
 124       fprintf (file, "not simple");
 125       return;
 126     }
 127
 128   if (iv->step == const0_rtx
 129       && !iv->first_special)
 130     fprintf (file, "invariant ");
 131
 132   print_rtl (file, iv->base);
 133   if (iv->step != const0_rtx)
 134     {
 135       fprintf (file, " + ");
 136       print_rtl (file, iv->step);
 137       fprintf (file, " * iteration");
 138     }
 139   fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
 140
 141   if (iv->mode != iv->extend_mode)
 142     fprintf (file, " %s to %s",
 143              rtx_name[iv->extend],
 144              GET_MODE_NAME (iv->extend_mode));
 145
 146   if (iv->mult != const1_rtx)
 147     {
 148       fprintf (file, " * ");
 149       print_rtl (file, iv->mult);
 150     }
 151   if (iv->delta != const0_rtx)
 152     {
 153       fprintf (file, " + ");
 154       print_rtl (file, iv->delta);
 155     }
 156   if (iv->first_special)
 157     fprintf (file, " (first special)");
 158 }
 159
 160 /* Generates a subreg to get the least significant part of EXPR (in mode
 161    INNER_MODE) to OUTER_MODE.  */
 162
 163 rtx
 164 lowpart_subreg (enum machine_mode outer_mode, rtx expr,
 165                 enum machine_mode inner_mode)
 166 {
 167   return simplify_gen_subreg (outer_mode, expr, inner_mode,
 168                               subreg_lowpart_offset (outer_mode, inner_mode));
 169 }
 170
 171 static void
 172 check_iv_ref_table_size (void)
 173 {
 174   if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
 175     {
 176       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
 177       iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, 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_blocks (blocks);
 282   df_analyze ();
 283   if (dump_file)
 284     df_dump_region (dump_file);
 285
 286   check_iv_ref_table_size ();
 287   BITMAP_FREE (blocks);
 288   free (body);
 289 }
 290
 291 /* Finds the definition of REG that dominates loop latch and stores
 292    it to DEF.  Returns false if there is not a single definition
 293    dominating the latch.  If REG has no definition in loop, DEF
 294    is set to NULL and true is returned.  */
 295
 296 static bool
 297 latch_dominating_def (rtx reg, df_ref *def)
 298 {
 299   df_ref single_rd = NULL, adef;
 300   unsigned regno = REGNO (reg);
 301   struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
 302
 303   for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
 304     {
 305       if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
 306           || !bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
 307         continue;
 308
 309       /* More than one reaching definition.  */
 310       if (single_rd)
 311         return false;
 312
 313       if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
 314         return false;
 315
 316       single_rd = adef;
 317     }
 318
 319   *def = single_rd;
 320   return true;
 321 }
 322
 323 /* Gets definition of REG reaching its use in INSN and stores it to DEF.  */
 324
 325 static enum iv_grd_result
 326 iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
 327 {
 328   df_ref use, adef;
 329   basic_block def_bb, use_bb;
 330   rtx def_insn;
 331   bool dom_p;
 332
 333   *def = NULL;
 334   if (!simple_reg_p (reg))
 335     return GRD_INVALID;
 336   if (GET_CODE (reg) == SUBREG)
 337     reg = SUBREG_REG (reg);
 338   gcc_assert (REG_P (reg));
 339
 340   use = df_find_use (insn, reg);
 341   gcc_assert (use != NULL);
 342
 343   if (!DF_REF_CHAIN (use))
 344     return GRD_INVARIANT;
 345
 346   /* More than one reaching def.  */
 347   if (DF_REF_CHAIN (use)->next)
 348     return GRD_INVALID;
 349
 350   adef = DF_REF_CHAIN (use)->ref;
 351
 352   /* We do not handle setting only part of the register.  */
 353   if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
 354     return GRD_INVALID;
 355
 356   def_insn = DF_REF_INSN (adef);
 357   def_bb = DF_REF_BB (adef);
 358   use_bb = BLOCK_FOR_INSN (insn);
 359
 360   if (use_bb == def_bb)
 361     dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
 362   else
 363     dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
 364
 365   if (dom_p)
 366     {
 367       *def = adef;
 368       return GRD_SINGLE_DOM;
 369     }
 370
 371   /* The definition does not dominate the use.  This is still OK if
 372      this may be a use of a biv, i.e. if the def_bb dominates loop
 373      latch.  */
 374   if (just_once_each_iteration_p (current_loop, def_bb))
 375     return GRD_MAYBE_BIV;
 376
 377   return GRD_INVALID;
 378 }
 379
 380 /* Sets IV to invariant CST in MODE.  Always returns true (just for
 381    consistency with other iv manipulation functions that may fail).  */
 382
 383 static bool
 384 iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
 385 {
 386   if (mode == VOIDmode)
 387     mode = GET_MODE (cst);
 388
 389   iv->mode = mode;
 390   iv->base = cst;
 391   iv->step = const0_rtx;
 392   iv->first_special = false;
 393   iv->extend = UNKNOWN;
 394   iv->extend_mode = iv->mode;
 395   iv->delta = const0_rtx;
 396   iv->mult = const1_rtx;
 397
 398   return true;
 399 }
 400
 401 /* Evaluates application of subreg to MODE on IV.  */
 402
 403 static bool
 404 iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
 405 {
 406   /* If iv is invariant, just calculate the new value.  */
 407   if (iv->step == const0_rtx
 408       && !iv->first_special)
 409     {
 410       rtx val = get_iv_value (iv, const0_rtx);
 411       val = lowpart_subreg (mode, val, iv->extend_mode);
 412
 413       iv->base = val;
 414       iv->extend = UNKNOWN;
 415       iv->mode = iv->extend_mode = mode;
 416       iv->delta = const0_rtx;
 417       iv->mult = const1_rtx;
 418       return true;
 419     }
 420
 421   if (iv->extend_mode == mode)
 422     return true;
 423
 424   if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
 425     return false;
 426
 427   iv->extend = UNKNOWN;
 428   iv->mode = mode;
 429
 430   iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
 431                                   simplify_gen_binary (MULT, iv->extend_mode,
 432                                                        iv->base, iv->mult));
 433   iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
 434   iv->mult = const1_rtx;
 435   iv->delta = const0_rtx;
 436   iv->first_special = false;
 437
 438   return true;
 439 }
 440
 441 /* Evaluates application of EXTEND to MODE on IV.  */
 442
 443 static bool
 444 iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
 445 {
 446   /* If iv is invariant, just calculate the new value.  */
 447   if (iv->step == const0_rtx
 448       && !iv->first_special)
 449     {
 450       rtx val = get_iv_value (iv, const0_rtx);
 451       val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
 452
 453       iv->base = val;
 454       iv->extend = UNKNOWN;
 455       iv->mode = iv->extend_mode = mode;
 456       iv->delta = const0_rtx;
 457       iv->mult = const1_rtx;
 458       return true;
 459     }
 460
 461   if (mode != iv->extend_mode)
 462     return false;
 463
 464   if (iv->extend != UNKNOWN
 465       && iv->extend != extend)
 466     return false;
 467
 468   iv->extend = extend;
 469
 470   return true;
 471 }
 472
 473 /* Evaluates negation of IV.  */
 474
 475 static bool
 476 iv_neg (struct rtx_iv *iv)
 477 {
 478   if (iv->extend == UNKNOWN)
 479     {
 480       iv->base = simplify_gen_unary (NEG, iv->extend_mode,
 481                                      iv->base, iv->extend_mode);
 482       iv->step = simplify_gen_unary (NEG, iv->extend_mode,
 483                                      iv->step, iv->extend_mode);
 484     }
 485   else
 486     {
 487       iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
 488                                       iv->delta, iv->extend_mode);
 489       iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
 490                                      iv->mult, iv->extend_mode);
 491     }
 492
 493   return true;
 494 }
 495
 496 /* Evaluates addition or subtraction (according to OP) of IV1 to IV0.  */
 497
 498 static bool
 499 iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
 500 {
 501   enum machine_mode mode;
 502   rtx arg;
 503
 504   /* Extend the constant to extend_mode of the other operand if necessary.  */
 505   if (iv0->extend == UNKNOWN
 506       && iv0->mode == iv0->extend_mode
 507       && iv0->step == const0_rtx
 508       && GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
 509     {
 510       iv0->extend_mode = iv1->extend_mode;
 511       iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
 512                                       iv0->base, iv0->mode);
 513     }
 514   if (iv1->extend == UNKNOWN
 515       && iv1->mode == iv1->extend_mode
 516       && iv1->step == const0_rtx
 517       && GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
 518     {
 519       iv1->extend_mode = iv0->extend_mode;
 520       iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
 521                                       iv1->base, iv1->mode);
 522     }
 523
 524   mode = iv0->extend_mode;
 525   if (mode != iv1->extend_mode)
 526     return false;
 527
 528   if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
 529     {
 530       if (iv0->mode != iv1->mode)
 531         return false;
 532
 533       iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
 534       iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
 535
 536       return true;
 537     }
 538
 539   /* Handle addition of constant.  */
 540   if (iv1->extend == UNKNOWN
 541       && iv1->mode == mode
 542       && iv1->step == const0_rtx)
 543     {
 544       iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
 545       return true;
 546     }
 547
 548   if (iv0->extend == UNKNOWN
 549       && iv0->mode == mode
 550       && iv0->step == const0_rtx)
 551     {
 552       arg = iv0->base;
 553       *iv0 = *iv1;
 554       if (op == MINUS
 555           && !iv_neg (iv0))
 556         return false;
 557
 558       iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
 559       return true;
 560     }
 561
 562   return false;
 563 }
 564
 565 /* Evaluates multiplication of IV by constant CST.  */
 566
 567 static bool
 568 iv_mult (struct rtx_iv *iv, rtx mby)
 569 {
 570   enum machine_mode mode = iv->extend_mode;
 571
 572   if (GET_MODE (mby) != VOIDmode
 573       && GET_MODE (mby) != mode)
 574     return false;
 575
 576   if (iv->extend == UNKNOWN)
 577     {
 578       iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
 579       iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
 580     }
 581   else
 582     {
 583       iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
 584       iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
 585     }
 586
 587   return true;
 588 }
 589
 590 /* Evaluates shift of IV by constant CST.  */
 591
 592 static bool
 593 iv_shift (struct rtx_iv *iv, rtx mby)
 594 {
 595   enum machine_mode mode = iv->extend_mode;
 596
 597   if (GET_MODE (mby) != VOIDmode
 598       && GET_MODE (mby) != mode)
 599     return false;
 600
 601   if (iv->extend == UNKNOWN)
 602     {
 603       iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
 604       iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
 605     }
 606   else
 607     {
 608       iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
 609       iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
 610     }
 611
 612   return true;
 613 }
 614
 615 /* The recursive part of get_biv_step.  Gets the value of the single value
 616    defined by DEF wrto initial value of REG inside loop, in shape described
 617    at get_biv_step.  */
 618
 619 static bool
 620 get_biv_step_1 (df_ref def, rtx reg,
 621                 rtx *inner_step, enum machine_mode *inner_mode,
 622                 enum rtx_code *extend, enum machine_mode outer_mode,
 623                 rtx *outer_step)
 624 {
 625   rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
 626   rtx next, nextr, tmp;
 627   enum rtx_code code;
 628   rtx insn = DF_REF_INSN (def);
 629   df_ref next_def;
 630   enum iv_grd_result res;
 631
 632   set = single_set (insn);
 633   if (!set)
 634     return false;
 635
 636   rhs = find_reg_equal_equiv_note (insn);
 637   if (rhs)
 638     rhs = XEXP (rhs, 0);
 639   else
 640     rhs = SET_SRC (set);
 641
 642   code = GET_CODE (rhs);
 643   switch (code)
 644     {
 645     case SUBREG:
 646     case REG:
 647       next = rhs;
 648       break;
 649
 650     case PLUS:
 651     case MINUS:
 652       op0 = XEXP (rhs, 0);
 653       op1 = XEXP (rhs, 1);
 654
 655       if (code == PLUS && CONSTANT_P (op0))
 656         {
 657           tmp = op0; op0 = op1; op1 = tmp;
 658         }
 659
 660       if (!simple_reg_p (op0)
 661           || !CONSTANT_P (op1))
 662         return false;
 663
 664       if (GET_MODE (rhs) != outer_mode)
 665         {
 666           /* ppc64 uses expressions like
 667
 668              (set x:SI (plus:SI (subreg:SI y:DI) 1)).
 669
 670              this is equivalent to
 671
 672              (set x':DI (plus:DI y:DI 1))
 673              (set x:SI (subreg:SI (x':DI)).  */
 674           if (GET_CODE (op0) != SUBREG)
 675             return false;
 676           if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
 677             return false;
 678         }
 679
 680       next = op0;
 681       break;
 682
 683     case SIGN_EXTEND:
 684     case ZERO_EXTEND:
 685       if (GET_MODE (rhs) != outer_mode)
 686         return false;
 687
 688       op0 = XEXP (rhs, 0);
 689       if (!simple_reg_p (op0))
 690         return false;
 691
 692       next = op0;
 693       break;
 694
 695     default:
 696       return false;
 697     }
 698
 699   if (GET_CODE (next) == SUBREG)
 700     {
 701       if (!subreg_lowpart_p (next))
 702         return false;
 703
 704       nextr = SUBREG_REG (next);
 705       if (GET_MODE (nextr) != outer_mode)
 706         return false;
 707     }
 708   else
 709     nextr = next;
 710
 711   res = iv_get_reaching_def (insn, nextr, &next_def);
 712
 713   if (res == GRD_INVALID || res == GRD_INVARIANT)
 714     return false;
 715
 716   if (res == GRD_MAYBE_BIV)
 717     {
 718       if (!rtx_equal_p (nextr, reg))
 719         return false;
 720
 721       *inner_step = const0_rtx;
 722       *extend = UNKNOWN;
 723       *inner_mode = outer_mode;
 724       *outer_step = const0_rtx;
 725     }
 726   else if (!get_biv_step_1 (next_def, reg,
 727                             inner_step, inner_mode, extend, outer_mode,
 728                             outer_step))
 729     return false;
 730
 731   if (GET_CODE (next) == SUBREG)
 732     {
 733       enum machine_mode amode = GET_MODE (next);
 734
 735       if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
 736         return false;
 737
 738       *inner_mode = amode;
 739       *inner_step = simplify_gen_binary (PLUS, outer_mode,
 740                                          *inner_step, *outer_step);
 741       *outer_step = const0_rtx;
 742       *extend = UNKNOWN;
 743     }
 744
 745   switch (code)
 746     {
 747     case REG:
 748     case SUBREG:
 749       break;
 750
 751     case PLUS:
 752     case MINUS:
 753       if (*inner_mode == outer_mode
 754           /* See comment in previous switch.  */
 755           || GET_MODE (rhs) != outer_mode)
 756         *inner_step = simplify_gen_binary (code, outer_mode,
 757                                            *inner_step, op1);
 758       else
 759         *outer_step = simplify_gen_binary (code, outer_mode,
 760                                            *outer_step, op1);
 761       break;
 762
 763     case SIGN_EXTEND:
 764     case ZERO_EXTEND:
 765       gcc_assert (GET_MODE (op0) == *inner_mode
 766                   && *extend == UNKNOWN
 767                   && *outer_step == const0_rtx);
 768
 769       *extend = code;
 770       break;
 771
 772     default:
 773       return false;
 774     }
 775
 776   return true;
 777 }
 778
 779 /* Gets the operation on register REG inside loop, in shape
 780
 781    OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
 782
 783    If the operation cannot be described in this shape, return false.
 784    LAST_DEF is the definition of REG that dominates loop latch.  */
 785
 786 static bool
 787 get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
 788               enum machine_mode *inner_mode, enum rtx_code *extend,
 789               enum machine_mode *outer_mode, rtx *outer_step)
 790 {
 791   *outer_mode = GET_MODE (reg);
 792
 793   if (!get_biv_step_1 (last_def, reg,
 794                        inner_step, inner_mode, extend, *outer_mode,
 795                        outer_step))
 796     return false;
 797
 798   gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
 799   gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
 800
 801   return true;
 802 }
 803
 804 /* Records information that DEF is induction variable IV.  */
 805
 806 static void
 807 record_iv (df_ref def, struct rtx_iv *iv)
 808 {
 809   struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
 810
 811   *recorded_iv = *iv;
 812   check_iv_ref_table_size ();
 813   DF_REF_IV_SET (def, recorded_iv);
 814 }
 815
 816 /* If DEF was already analyzed for bivness, store the description of the biv to
 817    IV and return true.  Otherwise return false.  */
 818
 819 static bool
 820 analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
 821 {
 822   struct biv_entry *biv =
 823     (struct biv_entry *) 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   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 (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   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   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   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 ((bitmap) 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 ((bitmap) 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 and reg + reg.  */
1342       if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1343           && !CONSTANT_P (op0))
1344         return false;
1345       if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1346           && !CONSTANT_P (op1))
1347         return false;
1348
1349       return true;
1350
1351     case ASHIFT:
1352       op0 = XEXP (rhs, 0);
1353       op1 = XEXP (rhs, 1);
1354       /* Allow reg << const.  */
1355       if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1356         return false;
1357       if (!CONSTANT_P (op1))
1358         return false;
1359
1360       return true;
1361
1362     default:
1363       return false;
1364     }
1365 }
1366
1367 /* Simplifies *EXPR using assignment in INSN.  ALTERED is the set of registers
1368    altered so far.  */
1369
1370 static void
1371 simplify_using_assignment (rtx insn, rtx *expr, regset altered)
1372 {
1373   rtx set = single_set (insn);
1374   rtx lhs = NULL_RTX, rhs;
1375   bool ret = false;
1376
1377   if (set)
1378     {
1379       lhs = SET_DEST (set);
1380       if (!REG_P (lhs)
1381           || altered_reg_used (&lhs, altered))
1382         ret = true;
1383     }
1384   else
1385     ret = true;
1386
1387   note_stores (PATTERN (insn), mark_altered, altered);
1388   if (CALL_P (insn))
1389     {
1390       int i;
1391
1392       /* Kill all call clobbered registers.  */
1393       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1394         if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1395           SET_REGNO_REG_SET (altered, i);
1396     }
1397
1398   if (ret)
1399     return;
1400
1401   rhs = find_reg_equal_equiv_note (insn);
1402   if (rhs)
1403     rhs = XEXP (rhs, 0);
1404   else
1405     rhs = SET_SRC (set);
1406
1407   if (!simple_rhs_p (rhs))
1408     return;
1409
1410   if (for_each_rtx (&rhs, altered_reg_used, altered))
1411     return;
1412
1413   *expr = simplify_replace_rtx (*expr, lhs, rhs);
1414 }
1415
1416 /* Checks whether A implies B.  */
1417
1418 static bool
1419 implies_p (rtx a, rtx b)
1420 {
1421   rtx op0, op1, opb0, opb1, r;
1422   enum machine_mode mode;
1423
1424   if (GET_CODE (a) == EQ)
1425     {
1426       op0 = XEXP (a, 0);
1427       op1 = XEXP (a, 1);
1428
1429       if (REG_P (op0))
1430         {
1431           r = simplify_replace_rtx (b, op0, op1);
1432           if (r == const_true_rtx)
1433             return true;
1434         }
1435
1436       if (REG_P (op1))
1437         {
1438           r = simplify_replace_rtx (b, op1, op0);
1439           if (r == const_true_rtx)
1440             return true;
1441         }
1442     }
1443
1444   if (b == const_true_rtx)
1445     return true;
1446
1447   if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1448        && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1449       || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1450           && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1451     return false;
1452
1453   op0 = XEXP (a, 0);
1454   op1 = XEXP (a, 1);
1455   opb0 = XEXP (b, 0);
1456   opb1 = XEXP (b, 1);
1457
1458   mode = GET_MODE (op0);
1459   if (mode != GET_MODE (opb0))
1460     mode = VOIDmode;
1461   else if (mode == VOIDmode)
1462     {
1463       mode = GET_MODE (op1);
1464       if (mode != GET_MODE (opb1))
1465         mode = VOIDmode;
1466     }
1467
1468   /* A < B implies A + 1 <= B.  */
1469   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1470       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1471     {
1472
1473       if (GET_CODE (a) == GT)
1474         {
1475           r = op0;
1476           op0 = op1;
1477           op1 = r;
1478         }
1479
1480       if (GET_CODE (b) == GE)
1481         {
1482           r = opb0;
1483           opb0 = opb1;
1484           opb1 = r;
1485         }
1486
1487       if (SCALAR_INT_MODE_P (mode)
1488           && rtx_equal_p (op1, opb1)
1489           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1490         return true;
1491       return false;
1492     }
1493
1494   /* A < B or A > B imply A != B.  TODO: Likewise
1495      A + n < B implies A != B + n if neither wraps.  */
1496   if (GET_CODE (b) == NE
1497       && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1498           || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1499     {
1500       if (rtx_equal_p (op0, opb0)
1501           && rtx_equal_p (op1, opb1))
1502         return true;
1503     }
1504
1505   /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
1506   if (GET_CODE (a) == NE
1507       && op1 == const0_rtx)
1508     {
1509       if ((GET_CODE (b) == GTU
1510            && opb1 == const0_rtx)
1511           || (GET_CODE (b) == GEU
1512               && opb1 == const1_rtx))
1513         return rtx_equal_p (op0, opb0);
1514     }
1515
1516   /* A != N is equivalent to A - (N + 1) <u -1.  */
1517   if (GET_CODE (a) == NE
1518       && GET_CODE (op1) == CONST_INT
1519       && GET_CODE (b) == LTU
1520       && opb1 == constm1_rtx
1521       && GET_CODE (opb0) == PLUS
1522       && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1523       /* Avoid overflows.  */
1524       && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1525           != ((unsigned HOST_WIDE_INT)1
1526               << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1527       && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1528     return rtx_equal_p (op0, XEXP (opb0, 0));
1529
1530   /* Likewise, A != N implies A - N > 0.  */
1531   if (GET_CODE (a) == NE
1532       && GET_CODE (op1) == CONST_INT)
1533     {
1534       if (GET_CODE (b) == GTU
1535           && GET_CODE (opb0) == PLUS
1536           && opb1 == const0_rtx
1537           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1538           /* Avoid overflows.  */
1539           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1540               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1541           && rtx_equal_p (XEXP (opb0, 0), op0))
1542         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1543       if (GET_CODE (b) == GEU
1544           && GET_CODE (opb0) == PLUS
1545           && opb1 == const1_rtx
1546           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1547           /* Avoid overflows.  */
1548           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1549               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1550           && rtx_equal_p (XEXP (opb0, 0), op0))
1551         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1552     }
1553
1554   /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
1555   if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1556       && GET_CODE (op1) == CONST_INT
1557       && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1558           || INTVAL (op1) >= 0)
1559       && GET_CODE (b) == LTU
1560       && GET_CODE (opb1) == CONST_INT
1561       && rtx_equal_p (op0, opb0))
1562     return INTVAL (opb1) < 0;
1563
1564   return false;
1565 }
1566
1567 /* Canonicalizes COND so that
1568
1569    (1) Ensure that operands are ordered according to
1570        swap_commutative_operands_p.
1571    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1572        for GE, GEU, and LEU.  */
1573
1574 rtx
1575 canon_condition (rtx cond)
1576 {
1577   rtx tem;
1578   rtx op0, op1;
1579   enum rtx_code code;
1580   enum machine_mode mode;
1581
1582   code = GET_CODE (cond);
1583   op0 = XEXP (cond, 0);
1584   op1 = XEXP (cond, 1);
1585
1586   if (swap_commutative_operands_p (op0, op1))
1587     {
1588       code = swap_condition (code);
1589       tem = op0;
1590       op0 = op1;
1591       op1 = tem;
1592     }
1593
1594   mode = GET_MODE (op0);
1595   if (mode == VOIDmode)
1596     mode = GET_MODE (op1);
1597   gcc_assert (mode != VOIDmode);
1598
1599   if (GET_CODE (op1) == CONST_INT
1600       && GET_MODE_CLASS (mode) != MODE_CC
1601       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1602     {
1603       HOST_WIDE_INT const_val = INTVAL (op1);
1604       unsigned HOST_WIDE_INT uconst_val = const_val;
1605       unsigned HOST_WIDE_INT max_val
1606         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1607
1608       switch (code)
1609         {
1610         case LE:
1611           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1612             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1613           break;
1614
1615         /* When cross-compiling, const_val might be sign-extended from
1616            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1617         case GE:
1618           if ((HOST_WIDE_INT) (const_val & max_val)
1619               != (((HOST_WIDE_INT) 1
1620                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1621             code = GT, op1 = gen_int_mode (const_val - 1, mode);
1622           break;
1623
1624         case LEU:
1625           if (uconst_val < max_val)
1626             code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1627           break;
1628
1629         case GEU:
1630           if (uconst_val != 0)
1631             code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1632           break;
1633
1634         default:
1635           break;
1636         }
1637     }
1638
1639   if (op0 != XEXP (cond, 0)
1640       || op1 != XEXP (cond, 1)
1641       || code != GET_CODE (cond)
1642       || GET_MODE (cond) != SImode)
1643     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1644
1645   return cond;
1646 }
1647
1648 /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1649    set of altered regs.  */
1650
1651 void
1652 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1653 {
1654   rtx rev, reve, exp = *expr;
1655
1656   if (!COMPARISON_P (exp))
1657     return;
1658
1659   /* If some register gets altered later, we do not really speak about its
1660      value at the time of comparison.  */
1661   if (altered
1662       && for_each_rtx (&cond, altered_reg_used, altered))
1663     return;
1664
1665   rev = reversed_condition (cond);
1666   reve = reversed_condition (exp);
1667
1668   cond = canon_condition (cond);
1669   exp = canon_condition (exp);
1670   if (rev)
1671     rev = canon_condition (rev);
1672   if (reve)
1673     reve = canon_condition (reve);
1674
1675   if (rtx_equal_p (exp, cond))
1676     {
1677       *expr = const_true_rtx;
1678       return;
1679     }
1680
1681
1682   if (rev && rtx_equal_p (exp, rev))
1683     {
1684       *expr = const0_rtx;
1685       return;
1686     }
1687
1688   if (implies_p (cond, exp))
1689     {
1690       *expr = const_true_rtx;
1691       return;
1692     }
1693
1694   if (reve && implies_p (cond, reve))
1695     {
1696       *expr = const0_rtx;
1697       return;
1698     }
1699
1700   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1701      be false.  */
1702   if (rev && implies_p (exp, rev))
1703     {
1704       *expr = const0_rtx;
1705       return;
1706     }
1707
1708   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1709   if (rev && reve && implies_p (reve, rev))
1710     {
1711       *expr = const_true_rtx;
1712       return;
1713     }
1714
1715   /* We would like to have some other tests here.  TODO.  */
1716
1717   return;
1718 }
1719
1720 /* Use relationship between A and *B to eventually eliminate *B.
1721    OP is the operation we consider.  */
1722
1723 static void
1724 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1725 {
1726   switch (op)
1727     {
1728     case AND:
1729       /* If A implies *B, we may replace *B by true.  */
1730       if (implies_p (a, *b))
1731         *b = const_true_rtx;
1732       break;
1733
1734     case IOR:
1735       /* If *B implies A, we may replace *B by false.  */
1736       if (implies_p (*b, a))
1737         *b = const0_rtx;
1738       break;
1739
1740     default:
1741       gcc_unreachable ();
1742     }
1743 }
1744
1745 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1746    operation we consider.  */
1747
1748 static void
1749 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1750 {
1751   rtx elt;
1752
1753   for (elt = tail; elt; elt = XEXP (elt, 1))
1754     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1755   for (elt = tail; elt; elt = XEXP (elt, 1))
1756     eliminate_implied_condition (op, XEXP (elt, 0), head);
1757 }
1758
1759 /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1760    is a list, its elements are assumed to be combined using OP.  */
1761
1762 static void
1763 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1764 {
1765   rtx head, tail, insn;
1766   rtx neutral, aggr;
1767   regset altered;
1768   edge e;
1769
1770   if (!*expr)
1771     return;
1772
1773   if (CONSTANT_P (*expr))
1774     return;
1775
1776   if (GET_CODE (*expr) == EXPR_LIST)
1777     {
1778       head = XEXP (*expr, 0);
1779       tail = XEXP (*expr, 1);
1780
1781       eliminate_implied_conditions (op, &head, tail);
1782
1783       switch (op)
1784         {
1785         case AND:
1786           neutral = const_true_rtx;
1787           aggr = const0_rtx;
1788           break;
1789
1790         case IOR:
1791           neutral = const0_rtx;
1792           aggr = const_true_rtx;
1793           break;
1794
1795         default:
1796           gcc_unreachable ();
1797         }
1798
1799       simplify_using_initial_values (loop, UNKNOWN, &head);
1800       if (head == aggr)
1801         {
1802           XEXP (*expr, 0) = aggr;
1803           XEXP (*expr, 1) = NULL_RTX;
1804           return;
1805         }
1806       else if (head == neutral)
1807         {
1808           *expr = tail;
1809           simplify_using_initial_values (loop, op, expr);
1810           return;
1811         }
1812       simplify_using_initial_values (loop, op, &tail);
1813
1814       if (tail && XEXP (tail, 0) == aggr)
1815         {
1816           *expr = tail;
1817           return;
1818         }
1819
1820       XEXP (*expr, 0) = head;
1821       XEXP (*expr, 1) = tail;
1822       return;
1823     }
1824
1825   gcc_assert (op == UNKNOWN);
1826
1827   e = loop_preheader_edge (loop);
1828   if (e->src == ENTRY_BLOCK_PTR)
1829     return;
1830
1831   altered = ALLOC_REG_SET (&reg_obstack);
1832
1833   while (1)
1834     {
1835       insn = BB_END (e->src);
1836       if (any_condjump_p (insn))
1837         {
1838           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1839
1840           if (cond && (e->flags & EDGE_FALLTHRU))
1841             cond = reversed_condition (cond);
1842           if (cond)
1843             {
1844               simplify_using_condition (cond, expr, altered);
1845               if (CONSTANT_P (*expr))
1846                 {
1847                   FREE_REG_SET (altered);
1848                   return;
1849                 }
1850             }
1851         }
1852
1853       FOR_BB_INSNS_REVERSE (e->src, insn)
1854         {
1855           if (!INSN_P (insn))
1856             continue;
1857
1858           simplify_using_assignment (insn, expr, altered);
1859           if (CONSTANT_P (*expr))
1860             {
1861               FREE_REG_SET (altered);
1862               return;
1863             }
1864           if (for_each_rtx (expr, altered_reg_used, altered))
1865             {
1866               FREE_REG_SET (altered);
1867               return;
1868             }
1869         }
1870
1871       if (!single_pred_p (e->src)
1872           || single_pred (e->src) == ENTRY_BLOCK_PTR)
1873         break;
1874       e = single_pred_edge (e->src);
1875     }
1876
1877   FREE_REG_SET (altered);
1878 }
1879
1880 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
1881    that IV occurs as left operands of comparison COND and its signedness
1882    is SIGNED_P to DESC.  */
1883
1884 static void
1885 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1886                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1887 {
1888   rtx mmin, mmax, cond_over, cond_under;
1889
1890   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1891   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1892                                         iv->base, mmin);
1893   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1894                                        iv->base, mmax);
1895
1896   switch (cond)
1897     {
1898       case LE:
1899       case LT:
1900       case LEU:
1901       case LTU:
1902         if (cond_under != const0_rtx)
1903           desc->infinite =
1904                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1905         if (cond_over != const0_rtx)
1906           desc->noloop_assumptions =
1907                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1908         break;
1909
1910       case GE:
1911       case GT:
1912       case GEU:
1913       case GTU:
1914         if (cond_over != const0_rtx)
1915           desc->infinite =
1916                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1917         if (cond_under != const0_rtx)
1918           desc->noloop_assumptions =
1919                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1920         break;
1921
1922       case NE:
1923         if (cond_over != const0_rtx)
1924           desc->infinite =
1925                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1926         if (cond_under != const0_rtx)
1927           desc->infinite =
1928                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1929         break;
1930
1931       default:
1932         gcc_unreachable ();
1933     }
1934
1935   iv->mode = mode;
1936   iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1937 }
1938
1939 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1940    subregs of the same mode if possible (sometimes it is necessary to add
1941    some assumptions to DESC).  */
1942
1943 static bool
1944 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1945                          enum rtx_code cond, struct niter_desc *desc)
1946 {
1947   enum machine_mode comp_mode;
1948   bool signed_p;
1949
1950   /* If the ivs behave specially in the first iteration, or are
1951      added/multiplied after extending, we ignore them.  */
1952   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1953     return false;
1954   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1955     return false;
1956
1957   /* If there is some extend, it must match signedness of the comparison.  */
1958   switch (cond)
1959     {
1960       case LE:
1961       case LT:
1962         if (iv0->extend == ZERO_EXTEND
1963             || iv1->extend == ZERO_EXTEND)
1964           return false;
1965         signed_p = true;
1966         break;
1967
1968       case LEU:
1969       case LTU:
1970         if (iv0->extend == SIGN_EXTEND
1971             || iv1->extend == SIGN_EXTEND)
1972           return false;
1973         signed_p = false;
1974         break;
1975
1976       case NE:
1977         if (iv0->extend != UNKNOWN
1978             && iv1->extend != UNKNOWN
1979             && iv0->extend != iv1->extend)
1980           return false;
1981
1982         signed_p = false;
1983         if (iv0->extend != UNKNOWN)
1984           signed_p = iv0->extend == SIGN_EXTEND;
1985         if (iv1->extend != UNKNOWN)
1986           signed_p = iv1->extend == SIGN_EXTEND;
1987         break;
1988
1989       default:
1990         gcc_unreachable ();
1991     }
1992
1993   /* Values of both variables should be computed in the same mode.  These
1994      might indeed be different, if we have comparison like
1995
1996      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1997
1998      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1999      in different modes.  This does not seem impossible to handle, but
2000      it hardly ever occurs in practice.
2001
2002      The only exception is the case when one of operands is invariant.
2003      For example pentium 3 generates comparisons like
2004      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
2005      definitely do not want this prevent the optimization.  */
2006   comp_mode = iv0->extend_mode;
2007   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2008     comp_mode = iv1->extend_mode;
2009
2010   if (iv0->extend_mode != comp_mode)
2011     {
2012       if (iv0->mode != iv0->extend_mode
2013           || iv0->step != const0_rtx)
2014         return false;
2015
2016       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2017                                       comp_mode, iv0->base, iv0->mode);
2018       iv0->extend_mode = comp_mode;
2019     }
2020
2021   if (iv1->extend_mode != comp_mode)
2022     {
2023       if (iv1->mode != iv1->extend_mode
2024           || iv1->step != const0_rtx)
2025         return false;
2026
2027       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2028                                       comp_mode, iv1->base, iv1->mode);
2029       iv1->extend_mode = comp_mode;
2030     }
2031
2032   /* Check that both ivs belong to a range of a single mode.  If one of the
2033      operands is an invariant, we may need to shorten it into the common
2034      mode.  */
2035   if (iv0->mode == iv0->extend_mode
2036       && iv0->step == const0_rtx
2037       && iv0->mode != iv1->mode)
2038     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2039
2040   if (iv1->mode == iv1->extend_mode
2041       && iv1->step == const0_rtx
2042       && iv0->mode != iv1->mode)
2043     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2044
2045   if (iv0->mode != iv1->mode)
2046     return false;
2047
2048   desc->mode = iv0->mode;
2049   desc->signed_p = signed_p;
2050
2051   return true;
2052 }
2053
2054 /* Tries to estimate the maximum number of iterations.  */
2055
2056 static unsigned HOST_WIDEST_INT
2057 determine_max_iter (struct loop *loop, struct niter_desc *desc)
2058 {
2059   rtx niter = desc->niter_expr;
2060   rtx mmin, mmax, cmp;
2061   unsigned HOST_WIDEST_INT nmax, inc;
2062
2063   if (GET_CODE (niter) == AND
2064       && GET_CODE (XEXP (niter, 0)) == CONST_INT)
2065     {
2066       nmax = INTVAL (XEXP (niter, 0));
2067       if (!(nmax & (nmax + 1)))
2068         {
2069           desc->niter_max = nmax;
2070           return nmax;
2071         }
2072     }
2073
2074   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2075   nmax = INTVAL (mmax) - INTVAL (mmin);
2076
2077   if (GET_CODE (niter) == UDIV)
2078     {
2079       if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
2080         {
2081           desc->niter_max = nmax;
2082           return nmax;
2083         }
2084       inc = INTVAL (XEXP (niter, 1));
2085       niter = XEXP (niter, 0);
2086     }
2087   else
2088     inc = 1;
2089
2090   /* We could use a binary search here, but for now improving the upper
2091      bound by just one eliminates one important corner case.  */
2092   cmp = gen_rtx_fmt_ee (desc->signed_p ? LT : LTU, VOIDmode, niter, mmax);
2093   simplify_using_initial_values (loop, UNKNOWN, &cmp);
2094   if (cmp == const_true_rtx)
2095     {
2096       nmax--;
2097
2098       if (dump_file)
2099         fprintf (dump_file, ";; improved upper bound by one.\n");
2100     }
2101   desc->niter_max = nmax / inc;
2102   return nmax / inc;
2103 }
2104
2105 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2106    the result into DESC.  Very similar to determine_number_of_iterations
2107    (basically its rtl version), complicated by things like subregs.  */
2108
2109 static void
2110 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2111                          struct niter_desc *desc)
2112 {
2113   rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2114   struct rtx_iv iv0, iv1, tmp_iv;
2115   rtx assumption, may_not_xform;
2116   enum rtx_code cond;
2117   enum machine_mode mode, comp_mode;
2118   rtx mmin, mmax, mode_mmin, mode_mmax;
2119   unsigned HOST_WIDEST_INT s, size, d, inv;
2120   HOST_WIDEST_INT up, down, inc, step_val;
2121   int was_sharp = false;
2122   rtx old_niter;
2123   bool step_is_pow2;
2124
2125   /* The meaning of these assumptions is this:
2126      if !assumptions
2127        then the rest of information does not have to be valid
2128      if noloop_assumptions then the loop does not roll
2129      if infinite then this exit is never used */
2130
2131   desc->assumptions = NULL_RTX;
2132   desc->noloop_assumptions = NULL_RTX;
2133   desc->infinite = NULL_RTX;
2134   desc->simple_p = true;
2135
2136   desc->const_iter = false;
2137   desc->niter_expr = NULL_RTX;
2138   desc->niter_max = 0;
2139
2140   cond = GET_CODE (condition);
2141   gcc_assert (COMPARISON_P (condition));
2142
2143   mode = GET_MODE (XEXP (condition, 0));
2144   if (mode == VOIDmode)
2145     mode = GET_MODE (XEXP (condition, 1));
2146   /* The constant comparisons should be folded.  */
2147   gcc_assert (mode != VOIDmode);
2148
2149   /* We only handle integers or pointers.  */
2150   if (GET_MODE_CLASS (mode) != MODE_INT
2151       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2152     goto fail;
2153
2154   op0 = XEXP (condition, 0);
2155   if (!iv_analyze (insn, op0, &iv0))
2156     goto fail;
2157   if (iv0.extend_mode == VOIDmode)
2158     iv0.mode = iv0.extend_mode = mode;
2159
2160   op1 = XEXP (condition, 1);
2161   if (!iv_analyze (insn, op1, &iv1))
2162     goto fail;
2163   if (iv1.extend_mode == VOIDmode)
2164     iv1.mode = iv1.extend_mode = mode;
2165
2166   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2167       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2168     goto fail;
2169
2170   /* Check condition and normalize it.  */
2171
2172   switch (cond)
2173     {
2174       case GE:
2175       case GT:
2176       case GEU:
2177       case GTU:
2178         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2179         cond = swap_condition (cond);
2180         break;
2181       case NE:
2182       case LE:
2183       case LEU:
2184       case LT:
2185       case LTU:
2186         break;
2187       default:
2188         goto fail;
2189     }
2190
2191   /* Handle extends.  This is relatively nontrivial, so we only try in some
2192      easy cases, when we can canonicalize the ivs (possibly by adding some
2193      assumptions) to shape subreg (base + i * step).  This function also fills
2194      in desc->mode and desc->signed_p.  */
2195
2196   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2197     goto fail;
2198
2199   comp_mode = iv0.extend_mode;
2200   mode = iv0.mode;
2201   size = GET_MODE_BITSIZE (mode);
2202   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2203   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2204   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2205
2206   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2207     goto fail;
2208
2209   /* We can take care of the case of two induction variables chasing each other
2210      if the test is NE. I have never seen a loop using it, but still it is
2211      cool.  */
2212   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2213     {
2214       if (cond != NE)
2215         goto fail;
2216
2217       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2218       iv1.step = const0_rtx;
2219     }
2220
2221   /* This is either infinite loop or the one that ends immediately, depending
2222      on initial values.  Unswitching should remove this kind of conditions.  */
2223   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2224     goto fail;
2225
2226   if (cond != NE)
2227     {
2228       if (iv0.step == const0_rtx)
2229         step_val = -INTVAL (iv1.step);
2230       else
2231         step_val = INTVAL (iv0.step);
2232
2233       /* Ignore loops of while (i-- < 10) type.  */
2234       if (step_val < 0)
2235         goto fail;
2236
2237       step_is_pow2 = !(step_val & (step_val - 1));
2238     }
2239   else
2240     {
2241       /* We do not care about whether the step is power of two in this
2242          case.  */
2243       step_is_pow2 = false;
2244       step_val = 0;
2245     }
2246
2247   /* Some more condition normalization.  We must record some assumptions
2248      due to overflows.  */
2249   switch (cond)
2250     {
2251       case LT:
2252       case LTU:
2253         /* We want to take care only of non-sharp relationals; this is easy,
2254            as in cases the overflow would make the transformation unsafe
2255            the loop does not roll.  Seemingly it would make more sense to want
2256            to take care of sharp relationals instead, as NE is more similar to
2257            them, but the problem is that here the transformation would be more
2258            difficult due to possibly infinite loops.  */
2259         if (iv0.step == const0_rtx)
2260           {
2261             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2262             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2263                                                   mode_mmax);
2264             if (assumption == const_true_rtx)
2265               goto zero_iter_simplify;
2266             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2267                                             iv0.base, const1_rtx);
2268           }
2269         else
2270           {
2271             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2272             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2273                                                   mode_mmin);
2274             if (assumption == const_true_rtx)
2275               goto zero_iter_simplify;
2276             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2277                                             iv1.base, constm1_rtx);
2278           }
2279
2280         if (assumption != const0_rtx)
2281           desc->noloop_assumptions =
2282                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2283         cond = (cond == LT) ? LE : LEU;
2284
2285         /* It will be useful to be able to tell the difference once more in
2286            LE -> NE reduction.  */
2287         was_sharp = true;
2288         break;
2289       default: ;
2290     }
2291
2292   /* Take care of trivially infinite loops.  */
2293   if (cond != NE)
2294     {
2295       if (iv0.step == const0_rtx)
2296         {
2297           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2298           if (rtx_equal_p (tmp, mode_mmin))
2299             {
2300               desc->infinite =
2301                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2302               /* Fill in the remaining fields somehow.  */
2303               goto zero_iter_simplify;
2304             }
2305         }
2306       else
2307         {
2308           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2309           if (rtx_equal_p (tmp, mode_mmax))
2310             {
2311               desc->infinite =
2312                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2313               /* Fill in the remaining fields somehow.  */
2314               goto zero_iter_simplify;
2315             }
2316         }
2317     }
2318
2319   /* If we can we want to take care of NE conditions instead of size
2320      comparisons, as they are much more friendly (most importantly
2321      this takes care of special handling of loops with step 1).  We can
2322      do it if we first check that upper bound is greater or equal to
2323      lower bound, their difference is constant c modulo step and that
2324      there is not an overflow.  */
2325   if (cond != NE)
2326     {
2327       if (iv0.step == const0_rtx)
2328         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2329       else
2330         step = iv0.step;
2331       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2332       delta = lowpart_subreg (mode, delta, comp_mode);
2333       delta = simplify_gen_binary (UMOD, mode, delta, step);
2334       may_xform = const0_rtx;
2335       may_not_xform = const_true_rtx;
2336
2337       if (GET_CODE (delta) == CONST_INT)
2338         {
2339           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2340             {
2341               /* A special case.  We have transformed condition of type
2342                  for (i = 0; i < 4; i += 4)
2343                  into
2344                  for (i = 0; i <= 3; i += 4)
2345                  obviously if the test for overflow during that transformation
2346                  passed, we cannot overflow here.  Most importantly any
2347                  loop with sharp end condition and step 1 falls into this
2348                  category, so handling this case specially is definitely
2349                  worth the troubles.  */
2350               may_xform = const_true_rtx;
2351             }
2352           else if (iv0.step == const0_rtx)
2353             {
2354               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2355               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2356               bound = lowpart_subreg (mode, bound, comp_mode);
2357               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2358               may_xform = simplify_gen_relational (cond, SImode, mode,
2359                                                    bound, tmp);
2360               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2361                                                        SImode, mode,
2362                                                        bound, tmp);
2363             }
2364           else
2365             {
2366               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2367               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2368               bound = lowpart_subreg (mode, bound, comp_mode);
2369               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2370               may_xform = simplify_gen_relational (cond, SImode, mode,
2371                                                    tmp, bound);
2372               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2373                                                        SImode, mode,
2374                                                        tmp, bound);
2375             }
2376         }
2377
2378       if (may_xform != const0_rtx)
2379         {
2380           /* We perform the transformation always provided that it is not
2381              completely senseless.  This is OK, as we would need this assumption
2382              to determine the number of iterations anyway.  */
2383           if (may_xform != const_true_rtx)
2384             {
2385               /* If the step is a power of two and the final value we have
2386                  computed overflows, the cycle is infinite.  Otherwise it
2387                  is nontrivial to compute the number of iterations.  */
2388               if (step_is_pow2)
2389                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2390                                                   desc->infinite);
2391               else
2392                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2393                                                      desc->assumptions);
2394             }
2395
2396           /* We are going to lose some information about upper bound on
2397              number of iterations in this step, so record the information
2398              here.  */
2399           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2400           if (GET_CODE (iv1.base) == CONST_INT)
2401             up = INTVAL (iv1.base);
2402           else
2403             up = INTVAL (mode_mmax) - inc;
2404           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2405                          ? iv0.base
2406                          : mode_mmin);
2407           desc->niter_max = (up - down) / inc + 1;
2408
2409           if (iv0.step == const0_rtx)
2410             {
2411               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2412               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2413             }
2414           else
2415             {
2416               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2417               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2418             }
2419
2420           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2421           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2422           assumption = simplify_gen_relational (reverse_condition (cond),
2423                                                 SImode, mode, tmp0, tmp1);
2424           if (assumption == const_true_rtx)
2425             goto zero_iter_simplify;
2426           else if (assumption != const0_rtx)
2427             desc->noloop_assumptions =
2428                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2429           cond = NE;
2430         }
2431     }
2432
2433   /* Count the number of iterations.  */
2434   if (cond == NE)
2435     {
2436       /* Everything we do here is just arithmetics modulo size of mode.  This
2437          makes us able to do more involved computations of number of iterations
2438          than in other cases.  First transform the condition into shape
2439          s * i <> c, with s positive.  */
2440       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2441       iv0.base = const0_rtx;
2442       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2443       iv1.step = const0_rtx;
2444       if (INTVAL (iv0.step) < 0)
2445         {
2446           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2447           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2448         }
2449       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2450
2451       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2452          is infinite.  Otherwise, the number of iterations is
2453          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2454       s = INTVAL (iv0.step); d = 1;
2455       while (s % 2 != 1)
2456         {
2457           s /= 2;
2458           d *= 2;
2459           size--;
2460         }
2461       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2462
2463       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2464       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2465       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2466       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2467
2468       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2469       inv = inverse (s, size);
2470       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2471       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2472     }
2473   else
2474     {
2475       if (iv1.step == const0_rtx)
2476         /* Condition in shape a + s * i <= b
2477            We must know that b + s does not overflow and a <= b + s and then we
2478            can compute number of iterations as (b + s - a) / s.  (It might
2479            seem that we in fact could be more clever about testing the b + s
2480            overflow condition using some information about b - a mod s,
2481            but it was already taken into account during LE -> NE transform).  */
2482         {
2483           step = iv0.step;
2484           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2485           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2486
2487           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2488                                        lowpart_subreg (mode, step,
2489                                                        comp_mode));
2490           if (step_is_pow2)
2491             {
2492               rtx t0, t1;
2493
2494               /* If s is power of 2, we know that the loop is infinite if
2495                  a % s <= b % s and b + s overflows.  */
2496               assumption = simplify_gen_relational (reverse_condition (cond),
2497                                                     SImode, mode,
2498                                                     tmp1, bound);
2499
2500               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2501               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2502               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2503               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2504               desc->infinite =
2505                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2506             }
2507           else
2508             {
2509               assumption = simplify_gen_relational (cond, SImode, mode,
2510                                                     tmp1, bound);
2511               desc->assumptions =
2512                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2513             }
2514
2515           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2516           tmp = lowpart_subreg (mode, tmp, comp_mode);
2517           assumption = simplify_gen_relational (reverse_condition (cond),
2518                                                 SImode, mode, tmp0, tmp);
2519
2520           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2521           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2522         }
2523       else
2524         {
2525           /* Condition in shape a <= b - s * i
2526              We must know that a - s does not overflow and a - s <= b and then
2527              we can again compute number of iterations as (b - (a - s)) / s.  */
2528           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2529           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2530           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2531
2532           bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2533                                        lowpart_subreg (mode, step, comp_mode));
2534           if (step_is_pow2)
2535             {
2536               rtx t0, t1;
2537
2538               /* If s is power of 2, we know that the loop is infinite if
2539                  a % s <= b % s and a - s overflows.  */
2540               assumption = simplify_gen_relational (reverse_condition (cond),
2541                                                     SImode, mode,
2542                                                     bound, tmp0);
2543
2544               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2545               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2546               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2547               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2548               desc->infinite =
2549                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2550             }
2551           else
2552             {
2553               assumption = simplify_gen_relational (cond, SImode, mode,
2554                                                     bound, tmp0);
2555               desc->assumptions =
2556                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2557             }
2558
2559           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2560           tmp = lowpart_subreg (mode, tmp, comp_mode);
2561           assumption = simplify_gen_relational (reverse_condition (cond),
2562                                                 SImode, mode,
2563                                                 tmp, tmp1);
2564           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2565           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2566         }
2567       if (assumption == const_true_rtx)
2568         goto zero_iter_simplify;
2569       else if (assumption != const0_rtx)
2570         desc->noloop_assumptions =
2571                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2572       delta = simplify_gen_binary (UDIV, mode, delta, step);
2573       desc->niter_expr = delta;
2574     }
2575
2576   old_niter = desc->niter_expr;
2577
2578   simplify_using_initial_values (loop, AND, &desc->assumptions);
2579   if (desc->assumptions
2580       && XEXP (desc->assumptions, 0) == const0_rtx)
2581     goto fail;
2582   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2583   simplify_using_initial_values (loop, IOR, &desc->infinite);
2584   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2585
2586   /* Rerun the simplification.  Consider code (created by copying loop headers)
2587
2588      i = 0;
2589
2590      if (0 < n)
2591        {
2592          do
2593            {
2594              i++;
2595            } while (i < n);
2596        }
2597
2598     The first pass determines that i = 0, the second pass uses it to eliminate
2599     noloop assumption.  */
2600
2601   simplify_using_initial_values (loop, AND, &desc->assumptions);
2602   if (desc->assumptions
2603       && XEXP (desc->assumptions, 0) == const0_rtx)
2604     goto fail;
2605   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2606   simplify_using_initial_values (loop, IOR, &desc->infinite);
2607   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2608
2609   if (desc->noloop_assumptions
2610       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2611     goto zero_iter;
2612
2613   if (GET_CODE (desc->niter_expr) == CONST_INT)
2614     {
2615       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2616
2617       desc->const_iter = true;
2618       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2619     }
2620   else
2621     {
2622       if (!desc->niter_max)
2623         desc->niter_max = determine_max_iter (loop, desc);
2624
2625       /* simplify_using_initial_values does a copy propagation on the registers
2626          in the expression for the number of iterations.  This prolongs life
2627          ranges of registers and increases register pressure, and usually
2628          brings no gain (and if it happens to do, the cse pass will take care
2629          of it anyway).  So prevent this behavior, unless it enabled us to
2630          derive that the number of iterations is a constant.  */
2631       desc->niter_expr = old_niter;
2632     }
2633
2634   return;
2635
2636 zero_iter_simplify:
2637   /* Simplify the assumptions.  */
2638   simplify_using_initial_values (loop, AND, &desc->assumptions);
2639   if (desc->assumptions
2640       && XEXP (desc->assumptions, 0) == const0_rtx)
2641     goto fail;
2642   simplify_using_initial_values (loop, IOR, &desc->infinite);
2643
2644   /* Fallthru.  */
2645 zero_iter:
2646   desc->const_iter = true;
2647   desc->niter = 0;
2648   desc->niter_max = 0;
2649   desc->noloop_assumptions = NULL_RTX;
2650   desc->niter_expr = const0_rtx;
2651   return;
2652
2653 fail:
2654   desc->simple_p = false;
2655   return;
2656 }
2657
2658 /* Checks whether E is a simple exit from LOOP and stores its description
2659    into DESC.  */
2660
2661 static void
2662 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2663 {
2664   basic_block exit_bb;
2665   rtx condition, at;
2666   edge ein;
2667
2668   exit_bb = e->src;
2669   desc->simple_p = false;
2670
2671   /* It must belong directly to the loop.  */
2672   if (exit_bb->loop_father != loop)
2673     return;
2674
2675   /* It must be tested (at least) once during any iteration.  */
2676   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2677     return;
2678
2679   /* It must end in a simple conditional jump.  */
2680   if (!any_condjump_p (BB_END (exit_bb)))
2681     return;
2682
2683   ein = EDGE_SUCC (exit_bb, 0);
2684   if (ein == e)
2685     ein = EDGE_SUCC (exit_bb, 1);
2686
2687   desc->out_edge = e;
2688   desc->in_edge = ein;
2689
2690   /* Test whether the condition is suitable.  */
2691   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2692     return;
2693
2694   if (ein->flags & EDGE_FALLTHRU)
2695     {
2696       condition = reversed_condition (condition);
2697       if (!condition)
2698         return;
2699     }
2700
2701   /* Check that we are able to determine number of iterations and fill
2702      in information about it.  */
2703   iv_number_of_iterations (loop, at, condition, desc);
2704 }
2705
2706 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2707
2708 void
2709 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2710 {
2711   unsigned i;
2712   basic_block *body;
2713   edge e;
2714   struct niter_desc act;
2715   bool any = false;
2716   edge_iterator ei;
2717
2718   desc->simple_p = false;
2719   body = get_loop_body (loop);
2720
2721   for (i = 0; i < loop->num_nodes; i++)
2722     {
2723       FOR_EACH_EDGE (e, ei, body[i]->succs)
2724         {
2725           if (flow_bb_inside_loop_p (loop, e->dest))
2726             continue;
2727
2728           check_simple_exit (loop, e, &act);
2729           if (!act.simple_p)
2730             continue;
2731
2732           if (!any)
2733             any = true;
2734           else
2735             {
2736               /* Prefer constant iterations; the less the better.  */
2737               if (!act.const_iter
2738                   || (desc->const_iter && act.niter >= desc->niter))
2739                 continue;
2740
2741               /* Also if the actual exit may be infinite, while the old one
2742                  not, prefer the old one.  */
2743               if (act.infinite && !desc->infinite)
2744                 continue;
2745             }
2746
2747           *desc = act;
2748         }
2749     }
2750
2751   if (dump_file)
2752     {
2753       if (desc->simple_p)
2754         {
2755           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2756           fprintf (dump_file, "  simple exit %d -> %d\n",
2757                    desc->out_edge->src->index,
2758                    desc->out_edge->dest->index);
2759           if (desc->assumptions)
2760             {
2761               fprintf (dump_file, "  assumptions: ");
2762               print_rtl (dump_file, desc->assumptions);
2763               fprintf (dump_file, "\n");
2764             }
2765           if (desc->noloop_assumptions)
2766             {
2767               fprintf (dump_file, "  does not roll if: ");
2768               print_rtl (dump_file, desc->noloop_assumptions);
2769               fprintf (dump_file, "\n");
2770             }
2771           if (desc->infinite)
2772             {
2773               fprintf (dump_file, "  infinite if: ");
2774               print_rtl (dump_file, desc->infinite);
2775               fprintf (dump_file, "\n");
2776             }
2777
2778           fprintf (dump_file, "  number of iterations: ");
2779           print_rtl (dump_file, desc->niter_expr);
2780           fprintf (dump_file, "\n");
2781
2782           fprintf (dump_file, "  upper bound: ");
2783           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2784           fprintf (dump_file, "\n");
2785         }
2786       else
2787         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2788     }
2789
2790   free (body);
2791 }
2792
2793 /* Creates a simple loop description of LOOP if it was not computed
2794    already.  */
2795
2796 struct niter_desc *
2797 get_simple_loop_desc (struct loop *loop)
2798 {
2799   struct niter_desc *desc = simple_loop_desc (loop);
2800
2801   if (desc)
2802     return desc;
2803
2804   /* At least desc->infinite is not always initialized by
2805      find_simple_loop_exit.  */
2806   desc = XCNEW (struct niter_desc);
2807   iv_analysis_loop_init (loop);
2808   find_simple_exit (loop, desc);
2809   loop->aux = desc;
2810
2811   if (desc->simple_p && (desc->assumptions || desc->infinite))
2812     {
2813       const char *wording;
2814
2815       /* Assume that no overflow happens and that the loop is finite.
2816          We already warned at the tree level if we ran optimizations there.  */
2817       if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
2818         {
2819           if (desc->infinite)
2820             {
2821               wording =
2822                 flag_unsafe_loop_optimizations
2823                 ? N_("assuming that the loop is not infinite")
2824                 : N_("cannot optimize possibly infinite loops");
2825               warning (OPT_Wunsafe_loop_optimizations, "%s",
2826                        gettext (wording));
2827             }
2828           if (desc->assumptions)
2829             {
2830               wording =
2831                 flag_unsafe_loop_optimizations
2832                 ? N_("assuming that the loop counter does not overflow")
2833                 : N_("cannot optimize loop, the loop counter may overflow");
2834               warning (OPT_Wunsafe_loop_optimizations, "%s",
2835                        gettext (wording));
2836             }
2837         }
2838
2839       if (flag_unsafe_loop_optimizations)
2840         {
2841           desc->assumptions = NULL_RTX;
2842           desc->infinite = NULL_RTX;
2843         }
2844     }
2845
2846   return desc;
2847 }
2848
2849 /* Releases simple loop description for LOOP.  */
2850
2851 void
2852 free_simple_loop_desc (struct loop *loop)
2853 {
2854   struct niter_desc *desc = simple_loop_desc (loop);
2855
2856   if (!desc)
2857     return;
2858
2859   free (desc);
2860   loop->aux = NULL;
2861 }