gcc/loop-iv.c

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