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