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     case AND:
1340       op0 = XEXP (rhs, 0);
1341       op1 = XEXP (rhs, 1);
1342       /* Allow reg OP const and reg OP reg.  */
1343       if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
1344           && !function_invariant_p (op0))
1345         return false;
1346       if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
1347           && !function_invariant_p (op1))
1348         return false;
1349
1350       return true;
1351
1352     case ASHIFT:
1353     case ASHIFTRT:
1354     case LSHIFTRT:
1355     case MULT:
1356       op0 = XEXP (rhs, 0);
1357       op1 = XEXP (rhs, 1);
1358       /* Allow reg OP const.  */
1359       if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
1360         return false;
1361       if (!function_invariant_p (op1))
1362         return false;
1363
1364       return true;
1365
1366     default:
1367       return false;
1368     }
1369 }
1370
1371 /* If REG has a single definition, replace it with its known value in EXPR.
1372    Callback for for_each_rtx.  */
1373
1374 static int
1375 replace_single_def_regs (rtx *reg, void *expr1)
1376 {
1377   unsigned regno;
1378   df_ref adef;
1379   rtx set, src;
1380   rtx *expr = (rtx *)expr1;
1381
1382   if (!REG_P (*reg))
1383     return 0;
1384
1385   regno = REGNO (*reg);
1386   for (;;)
1387     {
1388       rtx note;
1389       adef = DF_REG_DEF_CHAIN (regno);
1390       if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
1391             || DF_REF_IS_ARTIFICIAL (adef))
1392         return -1;
1393
1394       set = single_set (DF_REF_INSN (adef));
1395       if (set == NULL || !REG_P (SET_DEST (set))
1396           || REGNO (SET_DEST (set)) != regno)
1397         return -1;
1398
1399       note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
1400
1401       if (note && function_invariant_p (XEXP (note, 0)))
1402         {
1403           src = XEXP (note, 0);
1404           break;
1405         }
1406       src = SET_SRC (set);
1407
1408       if (REG_P (src))
1409         {
1410           regno = REGNO (src);
1411           continue;
1412         }
1413       break;
1414     }
1415   if (!function_invariant_p (src))
1416     return -1;
1417
1418   *expr = simplify_replace_rtx (*expr, *reg, src);
1419   return 1;
1420 }
1421
1422 /* A subroutine of simplify_using_initial_values, this function examines INSN
1423    to see if it contains a suitable set that we can use to make a replacement.
1424    If it is suitable, return true and set DEST and SRC to the lhs and rhs of
1425    the set; return false otherwise.  */
1426
1427 static bool
1428 suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
1429 {
1430   rtx set = single_set (insn);
1431   rtx lhs = NULL_RTX, rhs;
1432
1433   if (!set)
1434     return false;
1435
1436   lhs = SET_DEST (set);
1437   if (!REG_P (lhs))
1438     return false;
1439
1440   rhs = find_reg_equal_equiv_note (insn);
1441   if (rhs)
1442     rhs = XEXP (rhs, 0);
1443   else
1444     rhs = SET_SRC (set);
1445
1446   if (!simple_rhs_p (rhs))
1447     return false;
1448
1449   *dest = lhs;
1450   *src = rhs;
1451   return true;
1452 }
1453
1454 /* Using the data returned by suitable_set_for_replacement, replace DEST
1455    with SRC in *EXPR and return the new expression.  Also call
1456    replace_single_def_regs if the replacement changed something.  */
1457 static void
1458 replace_in_expr (rtx *expr, rtx dest, rtx src)
1459 {
1460   rtx old = *expr;
1461   *expr = simplify_replace_rtx (*expr, dest, src);
1462   if (old == *expr)
1463     return;
1464   while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
1465     continue;
1466 }
1467
1468 /* Checks whether A implies B.  */
1469
1470 static bool
1471 implies_p (rtx a, rtx b)
1472 {
1473   rtx op0, op1, opb0, opb1, r;
1474   enum machine_mode mode;
1475
1476   if (GET_CODE (a) == EQ)
1477     {
1478       op0 = XEXP (a, 0);
1479       op1 = XEXP (a, 1);
1480
1481       if (REG_P (op0))
1482         {
1483           r = simplify_replace_rtx (b, op0, op1);
1484           if (r == const_true_rtx)
1485             return true;
1486         }
1487
1488       if (REG_P (op1))
1489         {
1490           r = simplify_replace_rtx (b, op1, op0);
1491           if (r == const_true_rtx)
1492             return true;
1493         }
1494     }
1495
1496   if (b == const_true_rtx)
1497     return true;
1498
1499   if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
1500        && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
1501       || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
1502           && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
1503     return false;
1504
1505   op0 = XEXP (a, 0);
1506   op1 = XEXP (a, 1);
1507   opb0 = XEXP (b, 0);
1508   opb1 = XEXP (b, 1);
1509
1510   mode = GET_MODE (op0);
1511   if (mode != GET_MODE (opb0))
1512     mode = VOIDmode;
1513   else if (mode == VOIDmode)
1514     {
1515       mode = GET_MODE (op1);
1516       if (mode != GET_MODE (opb1))
1517         mode = VOIDmode;
1518     }
1519
1520   /* A < B implies A + 1 <= B.  */
1521   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1522       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1523     {
1524
1525       if (GET_CODE (a) == GT)
1526         {
1527           r = op0;
1528           op0 = op1;
1529           op1 = r;
1530         }
1531
1532       if (GET_CODE (b) == GE)
1533         {
1534           r = opb0;
1535           opb0 = opb1;
1536           opb1 = r;
1537         }
1538
1539       if (SCALAR_INT_MODE_P (mode)
1540           && rtx_equal_p (op1, opb1)
1541           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1542         return true;
1543       return false;
1544     }
1545
1546   /* A < B or A > B imply A != B.  TODO: Likewise
1547      A + n < B implies A != B + n if neither wraps.  */
1548   if (GET_CODE (b) == NE
1549       && (GET_CODE (a) == GT || GET_CODE (a) == GTU
1550           || GET_CODE (a) == LT || GET_CODE (a) == LTU))
1551     {
1552       if (rtx_equal_p (op0, opb0)
1553           && rtx_equal_p (op1, opb1))
1554         return true;
1555     }
1556
1557   /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
1558   if (GET_CODE (a) == NE
1559       && op1 == const0_rtx)
1560     {
1561       if ((GET_CODE (b) == GTU
1562            && opb1 == const0_rtx)
1563           || (GET_CODE (b) == GEU
1564               && opb1 == const1_rtx))
1565         return rtx_equal_p (op0, opb0);
1566     }
1567
1568   /* A != N is equivalent to A - (N + 1) <u -1.  */
1569   if (GET_CODE (a) == NE
1570       && GET_CODE (op1) == CONST_INT
1571       && GET_CODE (b) == LTU
1572       && opb1 == constm1_rtx
1573       && GET_CODE (opb0) == PLUS
1574       && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1575       /* Avoid overflows.  */
1576       && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1577           != ((unsigned HOST_WIDE_INT)1
1578               << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
1579       && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
1580     return rtx_equal_p (op0, XEXP (opb0, 0));
1581
1582   /* Likewise, A != N implies A - N > 0.  */
1583   if (GET_CODE (a) == NE
1584       && GET_CODE (op1) == CONST_INT)
1585     {
1586       if (GET_CODE (b) == GTU
1587           && GET_CODE (opb0) == PLUS
1588           && opb1 == const0_rtx
1589           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1590           /* Avoid overflows.  */
1591           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1592               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1593           && rtx_equal_p (XEXP (opb0, 0), op0))
1594         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1595       if (GET_CODE (b) == GEU
1596           && GET_CODE (opb0) == PLUS
1597           && opb1 == const1_rtx
1598           && GET_CODE (XEXP (opb0, 1)) == CONST_INT
1599           /* Avoid overflows.  */
1600           && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
1601               != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
1602           && rtx_equal_p (XEXP (opb0, 0), op0))
1603         return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
1604     }
1605
1606   /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
1607   if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
1608       && GET_CODE (op1) == CONST_INT
1609       && ((GET_CODE (a) == GT && op1 == constm1_rtx)
1610           || INTVAL (op1) >= 0)
1611       && GET_CODE (b) == LTU
1612       && GET_CODE (opb1) == CONST_INT
1613       && rtx_equal_p (op0, opb0))
1614     return INTVAL (opb1) < 0;
1615
1616   return false;
1617 }
1618
1619 /* Canonicalizes COND so that
1620
1621    (1) Ensure that operands are ordered according to
1622        swap_commutative_operands_p.
1623    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1624        for GE, GEU, and LEU.  */
1625
1626 rtx
1627 canon_condition (rtx cond)
1628 {
1629   rtx tem;
1630   rtx op0, op1;
1631   enum rtx_code code;
1632   enum machine_mode mode;
1633
1634   code = GET_CODE (cond);
1635   op0 = XEXP (cond, 0);
1636   op1 = XEXP (cond, 1);
1637
1638   if (swap_commutative_operands_p (op0, op1))
1639     {
1640       code = swap_condition (code);
1641       tem = op0;
1642       op0 = op1;
1643       op1 = tem;
1644     }
1645
1646   mode = GET_MODE (op0);
1647   if (mode == VOIDmode)
1648     mode = GET_MODE (op1);
1649   gcc_assert (mode != VOIDmode);
1650
1651   if (GET_CODE (op1) == CONST_INT
1652       && GET_MODE_CLASS (mode) != MODE_CC
1653       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1654     {
1655       HOST_WIDE_INT const_val = INTVAL (op1);
1656       unsigned HOST_WIDE_INT uconst_val = const_val;
1657       unsigned HOST_WIDE_INT max_val
1658         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1659
1660       switch (code)
1661         {
1662         case LE:
1663           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1664             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1665           break;
1666
1667         /* When cross-compiling, const_val might be sign-extended from
1668            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1669         case GE:
1670           if ((HOST_WIDE_INT) (const_val & max_val)
1671               != (((HOST_WIDE_INT) 1
1672                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1673             code = GT, op1 = gen_int_mode (const_val - 1, mode);
1674           break;
1675
1676         case LEU:
1677           if (uconst_val < max_val)
1678             code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1679           break;
1680
1681         case GEU:
1682           if (uconst_val != 0)
1683             code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1684           break;
1685
1686         default:
1687           break;
1688         }
1689     }
1690
1691   if (op0 != XEXP (cond, 0)
1692       || op1 != XEXP (cond, 1)
1693       || code != GET_CODE (cond)
1694       || GET_MODE (cond) != SImode)
1695     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1696
1697   return cond;
1698 }
1699
1700 /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1701    set of altered regs.  */
1702
1703 void
1704 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1705 {
1706   rtx rev, reve, exp = *expr;
1707
1708   /* If some register gets altered later, we do not really speak about its
1709      value at the time of comparison.  */
1710   if (altered
1711       && for_each_rtx (&cond, altered_reg_used, altered))
1712     return;
1713
1714   if (GET_CODE (cond) == EQ
1715       && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
1716     {
1717       *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
1718       return;
1719     }
1720
1721   if (!COMPARISON_P (exp))
1722     return;
1723
1724   rev = reversed_condition (cond);
1725   reve = reversed_condition (exp);
1726
1727   cond = canon_condition (cond);
1728   exp = canon_condition (exp);
1729   if (rev)
1730     rev = canon_condition (rev);
1731   if (reve)
1732     reve = canon_condition (reve);
1733
1734   if (rtx_equal_p (exp, cond))
1735     {
1736       *expr = const_true_rtx;
1737       return;
1738     }
1739
1740   if (rev && rtx_equal_p (exp, rev))
1741     {
1742       *expr = const0_rtx;
1743       return;
1744     }
1745
1746   if (implies_p (cond, exp))
1747     {
1748       *expr = const_true_rtx;
1749       return;
1750     }
1751
1752   if (reve && implies_p (cond, reve))
1753     {
1754       *expr = const0_rtx;
1755       return;
1756     }
1757
1758   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1759      be false.  */
1760   if (rev && implies_p (exp, rev))
1761     {
1762       *expr = const0_rtx;
1763       return;
1764     }
1765
1766   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1767   if (rev && reve && implies_p (reve, rev))
1768     {
1769       *expr = const_true_rtx;
1770       return;
1771     }
1772
1773   /* We would like to have some other tests here.  TODO.  */
1774
1775   return;
1776 }
1777
1778 /* Use relationship between A and *B to eventually eliminate *B.
1779    OP is the operation we consider.  */
1780
1781 static void
1782 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1783 {
1784   switch (op)
1785     {
1786     case AND:
1787       /* If A implies *B, we may replace *B by true.  */
1788       if (implies_p (a, *b))
1789         *b = const_true_rtx;
1790       break;
1791
1792     case IOR:
1793       /* If *B implies A, we may replace *B by false.  */
1794       if (implies_p (*b, a))
1795         *b = const0_rtx;
1796       break;
1797
1798     default:
1799       gcc_unreachable ();
1800     }
1801 }
1802
1803 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1804    operation we consider.  */
1805
1806 static void
1807 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1808 {
1809   rtx elt;
1810
1811   for (elt = tail; elt; elt = XEXP (elt, 1))
1812     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1813   for (elt = tail; elt; elt = XEXP (elt, 1))
1814     eliminate_implied_condition (op, XEXP (elt, 0), head);
1815 }
1816
1817 /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1818    is a list, its elements are assumed to be combined using OP.  */
1819
1820 static void
1821 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1822 {
1823   bool expression_valid;
1824   rtx head, tail, insn, cond_list, last_valid_expr;
1825   rtx neutral, aggr;
1826   regset altered, this_altered;
1827   edge e;
1828
1829   if (!*expr)
1830     return;
1831
1832   if (CONSTANT_P (*expr))
1833     return;
1834
1835   if (GET_CODE (*expr) == EXPR_LIST)
1836     {
1837       head = XEXP (*expr, 0);
1838       tail = XEXP (*expr, 1);
1839
1840       eliminate_implied_conditions (op, &head, tail);
1841
1842       switch (op)
1843         {
1844         case AND:
1845           neutral = const_true_rtx;
1846           aggr = const0_rtx;
1847           break;
1848
1849         case IOR:
1850           neutral = const0_rtx;
1851           aggr = const_true_rtx;
1852           break;
1853
1854         default:
1855           gcc_unreachable ();
1856         }
1857
1858       simplify_using_initial_values (loop, UNKNOWN, &head);
1859       if (head == aggr)
1860         {
1861           XEXP (*expr, 0) = aggr;
1862           XEXP (*expr, 1) = NULL_RTX;
1863           return;
1864         }
1865       else if (head == neutral)
1866         {
1867           *expr = tail;
1868           simplify_using_initial_values (loop, op, expr);
1869           return;
1870         }
1871       simplify_using_initial_values (loop, op, &tail);
1872
1873       if (tail && XEXP (tail, 0) == aggr)
1874         {
1875           *expr = tail;
1876           return;
1877         }
1878
1879       XEXP (*expr, 0) = head;
1880       XEXP (*expr, 1) = tail;
1881       return;
1882     }
1883
1884   gcc_assert (op == UNKNOWN);
1885
1886   for (;;)
1887     if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
1888       break;
1889   if (CONSTANT_P (*expr))
1890     return;
1891
1892   e = loop_preheader_edge (loop);
1893   if (e->src == ENTRY_BLOCK_PTR)
1894     return;
1895
1896   altered = ALLOC_REG_SET (&reg_obstack);
1897   this_altered = ALLOC_REG_SET (&reg_obstack);
1898
1899   expression_valid = true;
1900   last_valid_expr = *expr;
1901   cond_list = NULL_RTX;
1902   while (1)
1903     {
1904       insn = BB_END (e->src);
1905       if (any_condjump_p (insn))
1906         {
1907           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1908
1909           if (cond && (e->flags & EDGE_FALLTHRU))
1910             cond = reversed_condition (cond);
1911           if (cond)
1912             {
1913               rtx old = *expr;
1914               simplify_using_condition (cond, expr, altered);
1915               if (old != *expr)
1916                 {
1917                   rtx note;
1918                   if (CONSTANT_P (*expr))
1919                     goto out;
1920                   for (note = cond_list; note; note = XEXP (note, 1))
1921                     {
1922                       simplify_using_condition (XEXP (note, 0), expr, altered);
1923                       if (CONSTANT_P (*expr))
1924                         goto out;
1925                     }
1926                 }
1927               cond_list = alloc_EXPR_LIST (0, cond, cond_list);
1928             }
1929         }
1930
1931       FOR_BB_INSNS_REVERSE (e->src, insn)
1932         {
1933           rtx src, dest;
1934           rtx old = *expr;
1935
1936           if (!INSN_P (insn))
1937             continue;
1938
1939           CLEAR_REG_SET (this_altered);
1940           note_stores (PATTERN (insn), mark_altered, this_altered);
1941           if (CALL_P (insn))
1942             {
1943               int i;
1944
1945               /* Kill all call clobbered registers.  */
1946               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1947                 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1948                   SET_REGNO_REG_SET (this_altered, i);
1949             }
1950
1951           if (suitable_set_for_replacement (insn, &dest, &src))
1952             {
1953               rtx *pnote, *pnote_next;
1954
1955               replace_in_expr (expr, dest, src);
1956               if (CONSTANT_P (*expr))
1957                 goto out;
1958
1959               for (pnote = &cond_list; *pnote; pnote = pnote_next)
1960                 {
1961                   rtx note = *pnote;
1962                   rtx old_cond = XEXP (note, 0);
1963
1964                   pnote_next = &XEXP (note, 1);
1965                   replace_in_expr (&XEXP (note, 0), dest, src);
1966
1967                   /* We can no longer use a condition that has been simplified
1968                      to a constant, and simplify_using_condition will abort if
1969                      we try.  */
1970                   if (CONSTANT_P (XEXP (note, 0)))
1971                     {
1972                       *pnote = *pnote_next;
1973                       pnote_next = pnote;
1974                       free_EXPR_LIST_node (note);
1975                     }
1976                   /* Retry simplifications with this condition if either the
1977                      expression or the condition changed.  */
1978                   else if (old_cond != XEXP (note, 0) || old != *expr)
1979                     simplify_using_condition (XEXP (note, 0), expr, altered);
1980                 }
1981             }
1982           else
1983             /* If we did not use this insn to make a replacement, any overlap
1984                between stores in this insn and our expression will cause the
1985                expression to become invalid.  */
1986             if (for_each_rtx (expr, altered_reg_used, this_altered))
1987               goto out;
1988
1989           if (CONSTANT_P (*expr))
1990             goto out;
1991
1992           IOR_REG_SET (altered, this_altered);
1993
1994           /* If the expression now contains regs that have been altered, we
1995              can't return it to the caller.  However, it is still valid for
1996              further simplification, so keep searching to see if we can
1997              eventually turn it into a constant.  */
1998           if (for_each_rtx (expr, altered_reg_used, altered))
1999             expression_valid = false;
2000           if (expression_valid)
2001             last_valid_expr = *expr;
2002         }
2003
2004       if (!single_pred_p (e->src)
2005           || single_pred (e->src) == ENTRY_BLOCK_PTR)
2006         break;
2007       e = single_pred_edge (e->src);
2008     }
2009
2010  out:
2011   free_EXPR_LIST_list (&cond_list);
2012   if (!CONSTANT_P (*expr))
2013     *expr = last_valid_expr;
2014   FREE_REG_SET (altered);
2015   FREE_REG_SET (this_altered);
2016 }
2017
2018 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
2019    that IV occurs as left operands of comparison COND and its signedness
2020    is SIGNED_P to DESC.  */
2021
2022 static void
2023 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
2024                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
2025 {
2026   rtx mmin, mmax, cond_over, cond_under;
2027
2028   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
2029   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
2030                                         iv->base, mmin);
2031   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
2032                                        iv->base, mmax);
2033
2034   switch (cond)
2035     {
2036       case LE:
2037       case LT:
2038       case LEU:
2039       case LTU:
2040         if (cond_under != const0_rtx)
2041           desc->infinite =
2042                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
2043         if (cond_over != const0_rtx)
2044           desc->noloop_assumptions =
2045                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
2046         break;
2047
2048       case GE:
2049       case GT:
2050       case GEU:
2051       case GTU:
2052         if (cond_over != const0_rtx)
2053           desc->infinite =
2054                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
2055         if (cond_under != const0_rtx)
2056           desc->noloop_assumptions =
2057                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
2058         break;
2059
2060       case NE:
2061         if (cond_over != const0_rtx)
2062           desc->infinite =
2063                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
2064         if (cond_under != const0_rtx)
2065           desc->infinite =
2066                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
2067         break;
2068
2069       default:
2070         gcc_unreachable ();
2071     }
2072
2073   iv->mode = mode;
2074   iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
2075 }
2076
2077 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
2078    subregs of the same mode if possible (sometimes it is necessary to add
2079    some assumptions to DESC).  */
2080
2081 static bool
2082 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
2083                          enum rtx_code cond, struct niter_desc *desc)
2084 {
2085   enum machine_mode comp_mode;
2086   bool signed_p;
2087
2088   /* If the ivs behave specially in the first iteration, or are
2089      added/multiplied after extending, we ignore them.  */
2090   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
2091     return false;
2092   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
2093     return false;
2094
2095   /* If there is some extend, it must match signedness of the comparison.  */
2096   switch (cond)
2097     {
2098       case LE:
2099       case LT:
2100         if (iv0->extend == ZERO_EXTEND
2101             || iv1->extend == ZERO_EXTEND)
2102           return false;
2103         signed_p = true;
2104         break;
2105
2106       case LEU:
2107       case LTU:
2108         if (iv0->extend == SIGN_EXTEND
2109             || iv1->extend == SIGN_EXTEND)
2110           return false;
2111         signed_p = false;
2112         break;
2113
2114       case NE:
2115         if (iv0->extend != UNKNOWN
2116             && iv1->extend != UNKNOWN
2117             && iv0->extend != iv1->extend)
2118           return false;
2119
2120         signed_p = false;
2121         if (iv0->extend != UNKNOWN)
2122           signed_p = iv0->extend == SIGN_EXTEND;
2123         if (iv1->extend != UNKNOWN)
2124           signed_p = iv1->extend == SIGN_EXTEND;
2125         break;
2126
2127       default:
2128         gcc_unreachable ();
2129     }
2130
2131   /* Values of both variables should be computed in the same mode.  These
2132      might indeed be different, if we have comparison like
2133
2134      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
2135
2136      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
2137      in different modes.  This does not seem impossible to handle, but
2138      it hardly ever occurs in practice.
2139
2140      The only exception is the case when one of operands is invariant.
2141      For example pentium 3 generates comparisons like
2142      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
2143      definitely do not want this prevent the optimization.  */
2144   comp_mode = iv0->extend_mode;
2145   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
2146     comp_mode = iv1->extend_mode;
2147
2148   if (iv0->extend_mode != comp_mode)
2149     {
2150       if (iv0->mode != iv0->extend_mode
2151           || iv0->step != const0_rtx)
2152         return false;
2153
2154       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2155                                       comp_mode, iv0->base, iv0->mode);
2156       iv0->extend_mode = comp_mode;
2157     }
2158
2159   if (iv1->extend_mode != comp_mode)
2160     {
2161       if (iv1->mode != iv1->extend_mode
2162           || iv1->step != const0_rtx)
2163         return false;
2164
2165       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
2166                                       comp_mode, iv1->base, iv1->mode);
2167       iv1->extend_mode = comp_mode;
2168     }
2169
2170   /* Check that both ivs belong to a range of a single mode.  If one of the
2171      operands is an invariant, we may need to shorten it into the common
2172      mode.  */
2173   if (iv0->mode == iv0->extend_mode
2174       && iv0->step == const0_rtx
2175       && iv0->mode != iv1->mode)
2176     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
2177
2178   if (iv1->mode == iv1->extend_mode
2179       && iv1->step == const0_rtx
2180       && iv0->mode != iv1->mode)
2181     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
2182
2183   if (iv0->mode != iv1->mode)
2184     return false;
2185
2186   desc->mode = iv0->mode;
2187   desc->signed_p = signed_p;
2188
2189   return true;
2190 }
2191
2192 /* Tries to estimate the maximum number of iterations in LOOP, and store the
2193    result in DESC.  This function is called from iv_number_of_iterations with
2194    a number of fields in DESC already filled in.  OLD_NITER is the original
2195    expression for the number of iterations, before we tried to simplify it.  */
2196
2197 static unsigned HOST_WIDEST_INT
2198 determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
2199 {
2200   rtx niter = desc->niter_expr;
2201   rtx mmin, mmax, cmp;
2202   unsigned HOST_WIDEST_INT nmax, inc;
2203
2204   if (GET_CODE (niter) == AND
2205       && GET_CODE (XEXP (niter, 0)) == CONST_INT)
2206     {
2207       nmax = INTVAL (XEXP (niter, 0));
2208       if (!(nmax & (nmax + 1)))
2209         {
2210           desc->niter_max = nmax;
2211           return nmax;
2212         }
2213     }
2214
2215   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
2216   nmax = INTVAL (mmax) - INTVAL (mmin);
2217
2218   if (GET_CODE (niter) == UDIV)
2219     {
2220       if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
2221         {
2222           desc->niter_max = nmax;
2223           return nmax;
2224         }
2225       inc = INTVAL (XEXP (niter, 1));
2226       niter = XEXP (niter, 0);
2227     }
2228   else
2229     inc = 1;
2230
2231   /* We could use a binary search here, but for now improving the upper
2232      bound by just one eliminates one important corner case.  */
2233   cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
2234                                  desc->mode, old_niter, mmax);
2235   simplify_using_initial_values (loop, UNKNOWN, &cmp);
2236   if (cmp == const_true_rtx)
2237     {
2238       nmax--;
2239
2240       if (dump_file)
2241         fprintf (dump_file, ";; improved upper bound by one.\n");
2242     }
2243   desc->niter_max = nmax / inc;
2244   return nmax / inc;
2245 }
2246
2247 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2248    the result into DESC.  Very similar to determine_number_of_iterations
2249    (basically its rtl version), complicated by things like subregs.  */
2250
2251 static void
2252 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2253                          struct niter_desc *desc)
2254 {
2255   rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
2256   struct rtx_iv iv0, iv1, tmp_iv;
2257   rtx assumption, may_not_xform;
2258   enum rtx_code cond;
2259   enum machine_mode mode, comp_mode;
2260   rtx mmin, mmax, mode_mmin, mode_mmax;
2261   unsigned HOST_WIDEST_INT s, size, d, inv;
2262   HOST_WIDEST_INT up, down, inc, step_val;
2263   int was_sharp = false;
2264   rtx old_niter;
2265   bool step_is_pow2;
2266
2267   /* The meaning of these assumptions is this:
2268      if !assumptions
2269        then the rest of information does not have to be valid
2270      if noloop_assumptions then the loop does not roll
2271      if infinite then this exit is never used */
2272
2273   desc->assumptions = NULL_RTX;
2274   desc->noloop_assumptions = NULL_RTX;
2275   desc->infinite = NULL_RTX;
2276   desc->simple_p = true;
2277
2278   desc->const_iter = false;
2279   desc->niter_expr = NULL_RTX;
2280   desc->niter_max = 0;
2281
2282   cond = GET_CODE (condition);
2283   gcc_assert (COMPARISON_P (condition));
2284
2285   mode = GET_MODE (XEXP (condition, 0));
2286   if (mode == VOIDmode)
2287     mode = GET_MODE (XEXP (condition, 1));
2288   /* The constant comparisons should be folded.  */
2289   gcc_assert (mode != VOIDmode);
2290
2291   /* We only handle integers or pointers.  */
2292   if (GET_MODE_CLASS (mode) != MODE_INT
2293       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2294     goto fail;
2295
2296   op0 = XEXP (condition, 0);
2297   if (!iv_analyze (insn, op0, &iv0))
2298     goto fail;
2299   if (iv0.extend_mode == VOIDmode)
2300     iv0.mode = iv0.extend_mode = mode;
2301
2302   op1 = XEXP (condition, 1);
2303   if (!iv_analyze (insn, op1, &iv1))
2304     goto fail;
2305   if (iv1.extend_mode == VOIDmode)
2306     iv1.mode = iv1.extend_mode = mode;
2307
2308   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2309       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2310     goto fail;
2311
2312   /* Check condition and normalize it.  */
2313
2314   switch (cond)
2315     {
2316       case GE:
2317       case GT:
2318       case GEU:
2319       case GTU:
2320         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2321         cond = swap_condition (cond);
2322         break;
2323       case NE:
2324       case LE:
2325       case LEU:
2326       case LT:
2327       case LTU:
2328         break;
2329       default:
2330         goto fail;
2331     }
2332
2333   /* Handle extends.  This is relatively nontrivial, so we only try in some
2334      easy cases, when we can canonicalize the ivs (possibly by adding some
2335      assumptions) to shape subreg (base + i * step).  This function also fills
2336      in desc->mode and desc->signed_p.  */
2337
2338   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2339     goto fail;
2340
2341   comp_mode = iv0.extend_mode;
2342   mode = iv0.mode;
2343   size = GET_MODE_BITSIZE (mode);
2344   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2345   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2346   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2347
2348   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2349     goto fail;
2350
2351   /* We can take care of the case of two induction variables chasing each other
2352      if the test is NE. I have never seen a loop using it, but still it is
2353      cool.  */
2354   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2355     {
2356       if (cond != NE)
2357         goto fail;
2358
2359       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2360       iv1.step = const0_rtx;
2361     }
2362
2363   /* This is either infinite loop or the one that ends immediately, depending
2364      on initial values.  Unswitching should remove this kind of conditions.  */
2365   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2366     goto fail;
2367
2368   if (cond != NE)
2369     {
2370       if (iv0.step == const0_rtx)
2371         step_val = -INTVAL (iv1.step);
2372       else
2373         step_val = INTVAL (iv0.step);
2374
2375       /* Ignore loops of while (i-- < 10) type.  */
2376       if (step_val < 0)
2377         goto fail;
2378
2379       step_is_pow2 = !(step_val & (step_val - 1));
2380     }
2381   else
2382     {
2383       /* We do not care about whether the step is power of two in this
2384          case.  */
2385       step_is_pow2 = false;
2386       step_val = 0;
2387     }
2388
2389   /* Some more condition normalization.  We must record some assumptions
2390      due to overflows.  */
2391   switch (cond)
2392     {
2393       case LT:
2394       case LTU:
2395         /* We want to take care only of non-sharp relationals; this is easy,
2396            as in cases the overflow would make the transformation unsafe
2397            the loop does not roll.  Seemingly it would make more sense to want
2398            to take care of sharp relationals instead, as NE is more similar to
2399            them, but the problem is that here the transformation would be more
2400            difficult due to possibly infinite loops.  */
2401         if (iv0.step == const0_rtx)
2402           {
2403             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2404             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2405                                                   mode_mmax);
2406             if (assumption == const_true_rtx)
2407               goto zero_iter_simplify;
2408             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2409                                             iv0.base, const1_rtx);
2410           }
2411         else
2412           {
2413             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2414             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2415                                                   mode_mmin);
2416             if (assumption == const_true_rtx)
2417               goto zero_iter_simplify;
2418             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2419                                             iv1.base, constm1_rtx);
2420           }
2421
2422         if (assumption != const0_rtx)
2423           desc->noloop_assumptions =
2424                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2425         cond = (cond == LT) ? LE : LEU;
2426
2427         /* It will be useful to be able to tell the difference once more in
2428            LE -> NE reduction.  */
2429         was_sharp = true;
2430         break;
2431       default: ;
2432     }
2433
2434   /* Take care of trivially infinite loops.  */
2435   if (cond != NE)
2436     {
2437       if (iv0.step == const0_rtx)
2438         {
2439           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2440           if (rtx_equal_p (tmp, mode_mmin))
2441             {
2442               desc->infinite =
2443                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2444               /* Fill in the remaining fields somehow.  */
2445               goto zero_iter_simplify;
2446             }
2447         }
2448       else
2449         {
2450           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2451           if (rtx_equal_p (tmp, mode_mmax))
2452             {
2453               desc->infinite =
2454                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2455               /* Fill in the remaining fields somehow.  */
2456               goto zero_iter_simplify;
2457             }
2458         }
2459     }
2460
2461   /* If we can we want to take care of NE conditions instead of size
2462      comparisons, as they are much more friendly (most importantly
2463      this takes care of special handling of loops with step 1).  We can
2464      do it if we first check that upper bound is greater or equal to
2465      lower bound, their difference is constant c modulo step and that
2466      there is not an overflow.  */
2467   if (cond != NE)
2468     {
2469       if (iv0.step == const0_rtx)
2470         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2471       else
2472         step = iv0.step;
2473       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2474       delta = lowpart_subreg (mode, delta, comp_mode);
2475       delta = simplify_gen_binary (UMOD, mode, delta, step);
2476       may_xform = const0_rtx;
2477       may_not_xform = const_true_rtx;
2478
2479       if (GET_CODE (delta) == CONST_INT)
2480         {
2481           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2482             {
2483               /* A special case.  We have transformed condition of type
2484                  for (i = 0; i < 4; i += 4)
2485                  into
2486                  for (i = 0; i <= 3; i += 4)
2487                  obviously if the test for overflow during that transformation
2488                  passed, we cannot overflow here.  Most importantly any
2489                  loop with sharp end condition and step 1 falls into this
2490                  category, so handling this case specially is definitely
2491                  worth the troubles.  */
2492               may_xform = const_true_rtx;
2493             }
2494           else if (iv0.step == const0_rtx)
2495             {
2496               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2497               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2498               bound = lowpart_subreg (mode, bound, comp_mode);
2499               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2500               may_xform = simplify_gen_relational (cond, SImode, mode,
2501                                                    bound, tmp);
2502               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2503                                                        SImode, mode,
2504                                                        bound, tmp);
2505             }
2506           else
2507             {
2508               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2509               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2510               bound = lowpart_subreg (mode, bound, comp_mode);
2511               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2512               may_xform = simplify_gen_relational (cond, SImode, mode,
2513                                                    tmp, bound);
2514               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2515                                                        SImode, mode,
2516                                                        tmp, bound);
2517             }
2518         }
2519
2520       if (may_xform != const0_rtx)
2521         {
2522           /* We perform the transformation always provided that it is not
2523              completely senseless.  This is OK, as we would need this assumption
2524              to determine the number of iterations anyway.  */
2525           if (may_xform != const_true_rtx)
2526             {
2527               /* If the step is a power of two and the final value we have
2528                  computed overflows, the cycle is infinite.  Otherwise it
2529                  is nontrivial to compute the number of iterations.  */
2530               if (step_is_pow2)
2531                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2532                                                   desc->infinite);
2533               else
2534                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2535                                                      desc->assumptions);
2536             }
2537
2538           /* We are going to lose some information about upper bound on
2539              number of iterations in this step, so record the information
2540              here.  */
2541           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2542           if (GET_CODE (iv1.base) == CONST_INT)
2543             up = INTVAL (iv1.base);
2544           else
2545             up = INTVAL (mode_mmax) - inc;
2546           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2547                          ? iv0.base
2548                          : mode_mmin);
2549           desc->niter_max = (up - down) / inc + 1;
2550
2551           if (iv0.step == const0_rtx)
2552             {
2553               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2554               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2555             }
2556           else
2557             {
2558               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2559               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2560             }
2561
2562           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2563           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2564           assumption = simplify_gen_relational (reverse_condition (cond),
2565                                                 SImode, mode, tmp0, tmp1);
2566           if (assumption == const_true_rtx)
2567             goto zero_iter_simplify;
2568           else if (assumption != const0_rtx)
2569             desc->noloop_assumptions =
2570                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2571           cond = NE;
2572         }
2573     }
2574
2575   /* Count the number of iterations.  */
2576   if (cond == NE)
2577     {
2578       /* Everything we do here is just arithmetics modulo size of mode.  This
2579          makes us able to do more involved computations of number of iterations
2580          than in other cases.  First transform the condition into shape
2581          s * i <> c, with s positive.  */
2582       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2583       iv0.base = const0_rtx;
2584       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2585       iv1.step = const0_rtx;
2586       if (INTVAL (iv0.step) < 0)
2587         {
2588           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2589           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2590         }
2591       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2592
2593       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2594          is infinite.  Otherwise, the number of iterations is
2595          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2596       s = INTVAL (iv0.step); d = 1;
2597       while (s % 2 != 1)
2598         {
2599           s /= 2;
2600           d *= 2;
2601           size--;
2602         }
2603       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2604
2605       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2606       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2607       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2608       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2609
2610       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2611       inv = inverse (s, size);
2612       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2613       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2614     }
2615   else
2616     {
2617       if (iv1.step == const0_rtx)
2618         /* Condition in shape a + s * i <= b
2619            We must know that b + s does not overflow and a <= b + s and then we
2620            can compute number of iterations as (b + s - a) / s.  (It might
2621            seem that we in fact could be more clever about testing the b + s
2622            overflow condition using some information about b - a mod s,
2623            but it was already taken into account during LE -> NE transform).  */
2624         {
2625           step = iv0.step;
2626           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2627           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2628
2629           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2630                                        lowpart_subreg (mode, step,
2631                                                        comp_mode));
2632           if (step_is_pow2)
2633             {
2634               rtx t0, t1;
2635
2636               /* If s is power of 2, we know that the loop is infinite if
2637                  a % s <= b % s and b + s overflows.  */
2638               assumption = simplify_gen_relational (reverse_condition (cond),
2639                                                     SImode, mode,
2640                                                     tmp1, bound);
2641
2642               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2643               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2644               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2645               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2646               desc->infinite =
2647                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2648             }
2649           else
2650             {
2651               assumption = simplify_gen_relational (cond, SImode, mode,
2652                                                     tmp1, bound);
2653               desc->assumptions =
2654                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2655             }
2656
2657           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2658           tmp = lowpart_subreg (mode, tmp, comp_mode);
2659           assumption = simplify_gen_relational (reverse_condition (cond),
2660                                                 SImode, mode, tmp0, tmp);
2661
2662           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2663           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2664         }
2665       else
2666         {
2667           /* Condition in shape a <= b - s * i
2668              We must know that a - s does not overflow and a - s <= b and then
2669              we can again compute number of iterations as (b - (a - s)) / s.  */
2670           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2671           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2672           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2673
2674           bound = simplify_gen_binary (PLUS, mode, mode_mmin,
2675                                        lowpart_subreg (mode, step, comp_mode));
2676           if (step_is_pow2)
2677             {
2678               rtx t0, t1;
2679
2680               /* If s is power of 2, we know that the loop is infinite if
2681                  a % s <= b % s and a - s overflows.  */
2682               assumption = simplify_gen_relational (reverse_condition (cond),
2683                                                     SImode, mode,
2684                                                     bound, tmp0);
2685
2686               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2687               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2688               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2689               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2690               desc->infinite =
2691                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2692             }
2693           else
2694             {
2695               assumption = simplify_gen_relational (cond, SImode, mode,
2696                                                     bound, tmp0);
2697               desc->assumptions =
2698                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2699             }
2700
2701           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2702           tmp = lowpart_subreg (mode, tmp, comp_mode);
2703           assumption = simplify_gen_relational (reverse_condition (cond),
2704                                                 SImode, mode,
2705                                                 tmp, tmp1);
2706           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2707           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2708         }
2709       if (assumption == const_true_rtx)
2710         goto zero_iter_simplify;
2711       else if (assumption != const0_rtx)
2712         desc->noloop_assumptions =
2713                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2714       delta = simplify_gen_binary (UDIV, mode, delta, step);
2715       desc->niter_expr = delta;
2716     }
2717
2718   old_niter = desc->niter_expr;
2719
2720   simplify_using_initial_values (loop, AND, &desc->assumptions);
2721   if (desc->assumptions
2722       && XEXP (desc->assumptions, 0) == const0_rtx)
2723     goto fail;
2724   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2725   simplify_using_initial_values (loop, IOR, &desc->infinite);
2726   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2727
2728   /* Rerun the simplification.  Consider code (created by copying loop headers)
2729
2730      i = 0;
2731
2732      if (0 < n)
2733        {
2734          do
2735            {
2736              i++;
2737            } while (i < n);
2738        }
2739
2740     The first pass determines that i = 0, the second pass uses it to eliminate
2741     noloop assumption.  */
2742
2743   simplify_using_initial_values (loop, AND, &desc->assumptions);
2744   if (desc->assumptions
2745       && XEXP (desc->assumptions, 0) == const0_rtx)
2746     goto fail;
2747   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2748   simplify_using_initial_values (loop, IOR, &desc->infinite);
2749   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2750
2751   if (desc->noloop_assumptions
2752       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2753     goto zero_iter;
2754
2755   if (GET_CODE (desc->niter_expr) == CONST_INT)
2756     {
2757       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2758
2759       desc->const_iter = true;
2760       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2761     }
2762   else
2763     {
2764       if (!desc->niter_max)
2765         desc->niter_max = determine_max_iter (loop, desc, old_niter);
2766
2767       /* simplify_using_initial_values does a copy propagation on the registers
2768          in the expression for the number of iterations.  This prolongs life
2769          ranges of registers and increases register pressure, and usually
2770          brings no gain (and if it happens to do, the cse pass will take care
2771          of it anyway).  So prevent this behavior, unless it enabled us to
2772          derive that the number of iterations is a constant.  */
2773       desc->niter_expr = old_niter;
2774     }
2775
2776   return;
2777
2778 zero_iter_simplify:
2779   /* Simplify the assumptions.  */
2780   simplify_using_initial_values (loop, AND, &desc->assumptions);
2781   if (desc->assumptions
2782       && XEXP (desc->assumptions, 0) == const0_rtx)
2783     goto fail;
2784   simplify_using_initial_values (loop, IOR, &desc->infinite);
2785
2786   /* Fallthru.  */
2787 zero_iter:
2788   desc->const_iter = true;
2789   desc->niter = 0;
2790   desc->niter_max = 0;
2791   desc->noloop_assumptions = NULL_RTX;
2792   desc->niter_expr = const0_rtx;
2793   return;
2794
2795 fail:
2796   desc->simple_p = false;
2797   return;
2798 }
2799
2800 /* Checks whether E is a simple exit from LOOP and stores its description
2801    into DESC.  */
2802
2803 static void
2804 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2805 {
2806   basic_block exit_bb;
2807   rtx condition, at;
2808   edge ein;
2809
2810   exit_bb = e->src;
2811   desc->simple_p = false;
2812
2813   /* It must belong directly to the loop.  */
2814   if (exit_bb->loop_father != loop)
2815     return;
2816
2817   /* It must be tested (at least) once during any iteration.  */
2818   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2819     return;
2820
2821   /* It must end in a simple conditional jump.  */
2822   if (!any_condjump_p (BB_END (exit_bb)))
2823     return;
2824
2825   ein = EDGE_SUCC (exit_bb, 0);
2826   if (ein == e)
2827     ein = EDGE_SUCC (exit_bb, 1);
2828
2829   desc->out_edge = e;
2830   desc->in_edge = ein;
2831
2832   /* Test whether the condition is suitable.  */
2833   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2834     return;
2835
2836   if (ein->flags & EDGE_FALLTHRU)
2837     {
2838       condition = reversed_condition (condition);
2839       if (!condition)
2840         return;
2841     }
2842
2843   /* Check that we are able to determine number of iterations and fill
2844      in information about it.  */
2845   iv_number_of_iterations (loop, at, condition, desc);
2846 }
2847
2848 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2849
2850 void
2851 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2852 {
2853   unsigned i;
2854   basic_block *body;
2855   edge e;
2856   struct niter_desc act;
2857   bool any = false;
2858   edge_iterator ei;
2859
2860   desc->simple_p = false;
2861   body = get_loop_body (loop);
2862
2863   for (i = 0; i < loop->num_nodes; i++)
2864     {
2865       FOR_EACH_EDGE (e, ei, body[i]->succs)
2866         {
2867           if (flow_bb_inside_loop_p (loop, e->dest))
2868             continue;
2869
2870           check_simple_exit (loop, e, &act);
2871           if (!act.simple_p)
2872             continue;
2873
2874           if (!any)
2875             any = true;
2876           else
2877             {
2878               /* Prefer constant iterations; the less the better.  */
2879               if (!act.const_iter
2880                   || (desc->const_iter && act.niter >= desc->niter))
2881                 continue;
2882
2883               /* Also if the actual exit may be infinite, while the old one
2884                  not, prefer the old one.  */
2885               if (act.infinite && !desc->infinite)
2886                 continue;
2887             }
2888
2889           *desc = act;
2890         }
2891     }
2892
2893   if (dump_file)
2894     {
2895       if (desc->simple_p)
2896         {
2897           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2898           fprintf (dump_file, "  simple exit %d -> %d\n",
2899                    desc->out_edge->src->index,
2900                    desc->out_edge->dest->index);
2901           if (desc->assumptions)
2902             {
2903               fprintf (dump_file, "  assumptions: ");
2904               print_rtl (dump_file, desc->assumptions);
2905               fprintf (dump_file, "\n");
2906             }
2907           if (desc->noloop_assumptions)
2908             {
2909               fprintf (dump_file, "  does not roll if: ");
2910               print_rtl (dump_file, desc->noloop_assumptions);
2911               fprintf (dump_file, "\n");
2912             }
2913           if (desc->infinite)
2914             {
2915               fprintf (dump_file, "  infinite if: ");
2916               print_rtl (dump_file, desc->infinite);
2917               fprintf (dump_file, "\n");
2918             }
2919
2920           fprintf (dump_file, "  number of iterations: ");
2921           print_rtl (dump_file, desc->niter_expr);
2922           fprintf (dump_file, "\n");
2923
2924           fprintf (dump_file, "  upper bound: ");
2925           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2926           fprintf (dump_file, "\n");
2927         }
2928       else
2929         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2930     }
2931
2932   free (body);
2933 }
2934
2935 /* Creates a simple loop description of LOOP if it was not computed
2936    already.  */
2937
2938 struct niter_desc *
2939 get_simple_loop_desc (struct loop *loop)
2940 {
2941   struct niter_desc *desc = simple_loop_desc (loop);
2942
2943   if (desc)
2944     return desc;
2945
2946   /* At least desc->infinite is not always initialized by
2947      find_simple_loop_exit.  */
2948   desc = XCNEW (struct niter_desc);
2949   iv_analysis_loop_init (loop);
2950   find_simple_exit (loop, desc);
2951   loop->aux = desc;
2952
2953   if (desc->simple_p && (desc->assumptions || desc->infinite))
2954     {
2955       const char *wording;
2956
2957       /* Assume that no overflow happens and that the loop is finite.
2958          We already warned at the tree level if we ran optimizations there.  */
2959       if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
2960         {
2961           if (desc->infinite)
2962             {
2963               wording =
2964                 flag_unsafe_loop_optimizations
2965                 ? N_("assuming that the loop is not infinite")
2966                 : N_("cannot optimize possibly infinite loops");
2967               warning (OPT_Wunsafe_loop_optimizations, "%s",
2968                        gettext (wording));
2969             }
2970           if (desc->assumptions)
2971             {
2972               wording =
2973                 flag_unsafe_loop_optimizations
2974                 ? N_("assuming that the loop counter does not overflow")
2975                 : N_("cannot optimize loop, the loop counter may overflow");
2976               warning (OPT_Wunsafe_loop_optimizations, "%s",
2977                        gettext (wording));
2978             }
2979         }
2980
2981       if (flag_unsafe_loop_optimizations)
2982         {
2983           desc->assumptions = NULL_RTX;
2984           desc->infinite = NULL_RTX;
2985         }
2986     }
2987
2988   return desc;
2989 }
2990
2991 /* Releases simple loop description for LOOP.  */
2992
2993 void
2994 free_simple_loop_desc (struct loop *loop)
2995 {
2996   struct niter_desc *desc = simple_loop_desc (loop);
2997
2998   if (!desc)
2999     return;
3000
3001   free (desc);
3002   loop->aux = NULL;
3003 }