gcc/loop-iv.c

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