gcc/loop-iv.c

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