gcc/loop-iv.c

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