gcc/loop-iv.c

   1 /* Rtl-level induction variable analysis.
   2    Copyright (C) 2004, 2005 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, 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
 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 /* Checks whether definition of register REG in INSN a basic induction
1187    variable.  IV analysis must have been initialized (via a call to
1188    iv_analysis_loop_init) for this function to produce a result.  */
1189
1190 bool
1191 biv_p (rtx insn, rtx reg)
1192 {
1193   struct rtx_iv iv;
1194
1195   if (!REG_P (reg))
1196     return false;
1197
1198   if (last_def[REGNO (reg)] != insn)
1199     return false;
1200
1201   return iv_analyze_biv (reg, &iv);
1202 }
1203
1204 /* Calculates value of IV at ITERATION-th iteration.  */
1205
1206 rtx
1207 get_iv_value (struct rtx_iv *iv, rtx iteration)
1208 {
1209   rtx val;
1210
1211   /* We would need to generate some if_then_else patterns, and so far
1212      it is not needed anywhere.  */
1213   if (iv->first_special)
1214     abort ();
1215
1216   if (iv->step != const0_rtx && iteration != const0_rtx)
1217     val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
1218                                simplify_gen_binary (MULT, iv->extend_mode,
1219                                                     iv->step, iteration));
1220   else
1221     val = iv->base;
1222
1223   if (iv->extend_mode == iv->mode)
1224     return val;
1225
1226   val = lowpart_subreg (iv->mode, val, iv->extend_mode);
1227
1228   if (iv->extend == UNKNOWN)
1229     return val;
1230
1231   val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
1232   val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
1233                              simplify_gen_binary (MULT, iv->extend_mode,
1234                                                   iv->mult, val));
1235
1236   return val;
1237 }
1238
1239 /* Free the data for an induction variable analysis.  */
1240
1241 void
1242 iv_analysis_done (void)
1243 {
1244   max_insn_no = 0;
1245   max_reg_no = 0;
1246   if (insn_info)
1247     {
1248       free (insn_info);
1249       insn_info = NULL;
1250     }
1251   if (last_def)
1252     {
1253       free (last_def);
1254       last_def = NULL;
1255     }
1256   if (bivs)
1257     {
1258       free (bivs);
1259       bivs = NULL;
1260     }
1261 }
1262
1263 /* Computes inverse to X modulo (1 << MOD).  */
1264
1265 static unsigned HOST_WIDEST_INT
1266 inverse (unsigned HOST_WIDEST_INT x, int mod)
1267 {
1268   unsigned HOST_WIDEST_INT mask =
1269           ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
1270   unsigned HOST_WIDEST_INT rslt = 1;
1271   int i;
1272
1273   for (i = 0; i < mod - 1; i++)
1274     {
1275       rslt = (rslt * x) & mask;
1276       x = (x * x) & mask;
1277     }
1278
1279   return rslt;
1280 }
1281
1282 /* Tries to estimate the maximum number of iterations.  */
1283
1284 static unsigned HOST_WIDEST_INT
1285 determine_max_iter (struct niter_desc *desc)
1286 {
1287   rtx niter = desc->niter_expr;
1288   rtx mmin, mmax, left, right;
1289   unsigned HOST_WIDEST_INT nmax, inc;
1290
1291   if (GET_CODE (niter) == AND
1292       && GET_CODE (XEXP (niter, 0)) == CONST_INT)
1293     {
1294       nmax = INTVAL (XEXP (niter, 0));
1295       if (!(nmax & (nmax + 1)))
1296         {
1297           desc->niter_max = nmax;
1298           return nmax;
1299         }
1300     }
1301
1302   get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
1303   nmax = INTVAL (mmax) - INTVAL (mmin);
1304
1305   if (GET_CODE (niter) == UDIV)
1306     {
1307       if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
1308         {
1309           desc->niter_max = nmax;
1310           return nmax;
1311         }
1312       inc = INTVAL (XEXP (niter, 1));
1313       niter = XEXP (niter, 0);
1314     }
1315   else
1316     inc = 1;
1317
1318   if (GET_CODE (niter) == PLUS)
1319     {
1320       left = XEXP (niter, 0);
1321       right = XEXP (niter, 0);
1322
1323       if (GET_CODE (right) == CONST_INT)
1324         right = GEN_INT (-INTVAL (right));
1325     }
1326   else if (GET_CODE (niter) == MINUS)
1327     {
1328       left = XEXP (niter, 0);
1329       right = XEXP (niter, 0);
1330     }
1331   else
1332     {
1333       left = niter;
1334       right = mmin;
1335     }
1336
1337   if (GET_CODE (left) == CONST_INT)
1338     mmax = left;
1339   if (GET_CODE (right) == CONST_INT)
1340     mmin = right;
1341   nmax = INTVAL (mmax) - INTVAL (mmin);
1342
1343   desc->niter_max = nmax / inc;
1344   return nmax / inc;
1345 }
1346
1347 /* Checks whether register *REG is in set ALT.  Callback for for_each_rtx.  */
1348
1349 static int
1350 altered_reg_used (rtx *reg, void *alt)
1351 {
1352   if (!REG_P (*reg))
1353     return 0;
1354
1355   return REGNO_REG_SET_P (alt, REGNO (*reg));
1356 }
1357
1358 /* Marks registers altered by EXPR in set ALT.  */
1359
1360 static void
1361 mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
1362 {
1363   if (GET_CODE (expr) == SUBREG)
1364     expr = SUBREG_REG (expr);
1365   if (!REG_P (expr))
1366     return;
1367
1368   SET_REGNO_REG_SET (alt, REGNO (expr));
1369 }
1370
1371 /* Checks whether RHS is simple enough to process.  */
1372
1373 static bool
1374 simple_rhs_p (rtx rhs)
1375 {
1376   rtx op0, op1;
1377
1378   if (CONSTANT_P (rhs)
1379       || REG_P (rhs))
1380     return true;
1381
1382   switch (GET_CODE (rhs))
1383     {
1384     case PLUS:
1385     case MINUS:
1386       op0 = XEXP (rhs, 0);
1387       op1 = XEXP (rhs, 1);
1388       /* Allow reg + const sets only.  */
1389       if (REG_P (op0) && CONSTANT_P (op1))
1390         return true;
1391       if (REG_P (op1) && CONSTANT_P (op0))
1392         return true;
1393
1394       return false;
1395
1396     default:
1397       return false;
1398     }
1399 }
1400
1401 /* Simplifies *EXPR using assignment in INSN.  ALTERED is the set of registers
1402    altered so far.  */
1403
1404 static void
1405 simplify_using_assignment (rtx insn, rtx *expr, regset altered)
1406 {
1407   rtx set = single_set (insn);
1408   rtx lhs = NULL_RTX, rhs;
1409   bool ret = false;
1410
1411   if (set)
1412     {
1413       lhs = SET_DEST (set);
1414       if (!REG_P (lhs)
1415           || altered_reg_used (&lhs, altered))
1416         ret = true;
1417     }
1418   else
1419     ret = true;
1420
1421   note_stores (PATTERN (insn), mark_altered, altered);
1422   if (CALL_P (insn))
1423     {
1424       int i;
1425
1426       /* Kill all call clobbered registers.  */
1427       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1428         if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1429           SET_REGNO_REG_SET (altered, i);
1430     }
1431
1432   if (ret)
1433     return;
1434
1435   rhs = find_reg_equal_equiv_note (insn);
1436   if (rhs)
1437     rhs = XEXP (rhs, 0);
1438   else
1439     rhs = SET_SRC (set);
1440
1441   if (!simple_rhs_p (rhs))
1442     return;
1443
1444   if (for_each_rtx (&rhs, altered_reg_used, altered))
1445     return;
1446
1447   *expr = simplify_replace_rtx (*expr, lhs, rhs);
1448 }
1449
1450 /* Checks whether A implies B.  */
1451
1452 static bool
1453 implies_p (rtx a, rtx b)
1454 {
1455   rtx op0, op1, opb0, opb1, r;
1456   enum machine_mode mode;
1457
1458   if (GET_CODE (a) == EQ)
1459     {
1460       op0 = XEXP (a, 0);
1461       op1 = XEXP (a, 1);
1462
1463       if (REG_P (op0))
1464         {
1465           r = simplify_replace_rtx (b, op0, op1);
1466           if (r == const_true_rtx)
1467             return true;
1468         }
1469
1470       if (REG_P (op1))
1471         {
1472           r = simplify_replace_rtx (b, op1, op0);
1473           if (r == const_true_rtx)
1474             return true;
1475         }
1476     }
1477
1478   /* A < B implies A + 1 <= B.  */
1479   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
1480       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
1481     {
1482       op0 = XEXP (a, 0);
1483       op1 = XEXP (a, 1);
1484       opb0 = XEXP (b, 0);
1485       opb1 = XEXP (b, 1);
1486
1487       if (GET_CODE (a) == GT)
1488         {
1489           r = op0;
1490           op0 = op1;
1491           op1 = r;
1492         }
1493
1494       if (GET_CODE (b) == GE)
1495         {
1496           r = opb0;
1497           opb0 = opb1;
1498           opb1 = r;
1499         }
1500
1501       mode = GET_MODE (op0);
1502       if (mode != GET_MODE (opb0))
1503         mode = VOIDmode;
1504       else if (mode == VOIDmode)
1505         {
1506           mode = GET_MODE (op1);
1507           if (mode != GET_MODE (opb1))
1508             mode = VOIDmode;
1509         }
1510
1511       if (mode != VOIDmode
1512           && rtx_equal_p (op1, opb1)
1513           && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
1514         return true;
1515     }
1516
1517   return false;
1518 }
1519
1520 /* Canonicalizes COND so that
1521
1522    (1) Ensure that operands are ordered according to
1523        swap_commutative_operands_p.
1524    (2) (LE x const) will be replaced with (LT x <const+1>) and similarly
1525        for GE, GEU, and LEU.  */
1526
1527 rtx
1528 canon_condition (rtx cond)
1529 {
1530   rtx tem;
1531   rtx op0, op1;
1532   enum rtx_code code;
1533   enum machine_mode mode;
1534
1535   code = GET_CODE (cond);
1536   op0 = XEXP (cond, 0);
1537   op1 = XEXP (cond, 1);
1538
1539   if (swap_commutative_operands_p (op0, op1))
1540     {
1541       code = swap_condition (code);
1542       tem = op0;
1543       op0 = op1;
1544       op1 = tem;
1545     }
1546
1547   mode = GET_MODE (op0);
1548   if (mode == VOIDmode)
1549     mode = GET_MODE (op1);
1550   if (mode == VOIDmode)
1551     abort ();
1552
1553   if (GET_CODE (op1) == CONST_INT
1554       && GET_MODE_CLASS (mode) != MODE_CC
1555       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
1556     {
1557       HOST_WIDE_INT const_val = INTVAL (op1);
1558       unsigned HOST_WIDE_INT uconst_val = const_val;
1559       unsigned HOST_WIDE_INT max_val
1560         = (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
1561
1562       switch (code)
1563         {
1564         case LE:
1565           if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
1566             code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
1567           break;
1568
1569         /* When cross-compiling, const_val might be sign-extended from
1570            BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
1571         case GE:
1572           if ((HOST_WIDE_INT) (const_val & max_val)
1573               != (((HOST_WIDE_INT) 1
1574                    << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
1575             code = GT, op1 = gen_int_mode (const_val - 1, mode);
1576           break;
1577
1578         case LEU:
1579           if (uconst_val < max_val)
1580             code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
1581           break;
1582
1583         case GEU:
1584           if (uconst_val != 0)
1585             code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
1586           break;
1587
1588         default:
1589           break;
1590         }
1591     }
1592
1593   if (op0 != XEXP (cond, 0)
1594       || op1 != XEXP (cond, 1)
1595       || code != GET_CODE (cond)
1596       || GET_MODE (cond) != SImode)
1597     cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
1598
1599   return cond;
1600 }
1601
1602 /* Tries to use the fact that COND holds to simplify EXPR.  ALTERED is the
1603    set of altered regs.  */
1604
1605 void
1606 simplify_using_condition (rtx cond, rtx *expr, regset altered)
1607 {
1608   rtx rev, reve, exp = *expr;
1609
1610   if (!COMPARISON_P (exp))
1611     return;
1612
1613   /* If some register gets altered later, we do not really speak about its
1614      value at the time of comparison.  */
1615   if (altered
1616       && for_each_rtx (&cond, altered_reg_used, altered))
1617     return;
1618
1619   rev = reversed_condition (cond);
1620   reve = reversed_condition (exp);
1621
1622   cond = canon_condition (cond);
1623   exp = canon_condition (exp);
1624   if (rev)
1625     rev = canon_condition (rev);
1626   if (reve)
1627     reve = canon_condition (reve);
1628
1629   if (rtx_equal_p (exp, cond))
1630     {
1631       *expr = const_true_rtx;
1632       return;
1633     }
1634
1635
1636   if (rev && rtx_equal_p (exp, rev))
1637     {
1638       *expr = const0_rtx;
1639       return;
1640     }
1641
1642   if (implies_p (cond, exp))
1643     {
1644       *expr = const_true_rtx;
1645       return;
1646     }
1647
1648   if (reve && implies_p (cond, reve))
1649     {
1650       *expr = const0_rtx;
1651       return;
1652     }
1653
1654   /* A proof by contradiction.  If *EXPR implies (not cond), *EXPR must
1655      be false.  */
1656   if (rev && implies_p (exp, rev))
1657     {
1658       *expr = const0_rtx;
1659       return;
1660     }
1661
1662   /* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true.  */
1663   if (rev && reve && implies_p (reve, rev))
1664     {
1665       *expr = const_true_rtx;
1666       return;
1667     }
1668
1669   /* We would like to have some other tests here.  TODO.  */
1670
1671   return;
1672 }
1673
1674 /* Use relationship between A and *B to eventually eliminate *B.
1675    OP is the operation we consider.  */
1676
1677 static void
1678 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
1679 {
1680   if (op == AND)
1681     {
1682       /* If A implies *B, we may replace *B by true.  */
1683       if (implies_p (a, *b))
1684         *b = const_true_rtx;
1685     }
1686   else if (op == IOR)
1687     {
1688       /* If *B implies A, we may replace *B by false.  */
1689       if (implies_p (*b, a))
1690         *b = const0_rtx;
1691     }
1692   else
1693     abort ();
1694 }
1695
1696 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
1697    operation we consider.  */
1698
1699 static void
1700 eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
1701 {
1702   rtx elt;
1703
1704   for (elt = tail; elt; elt = XEXP (elt, 1))
1705     eliminate_implied_condition (op, *head, &XEXP (elt, 0));
1706   for (elt = tail; elt; elt = XEXP (elt, 1))
1707     eliminate_implied_condition (op, XEXP (elt, 0), head);
1708 }
1709
1710 /* Simplifies *EXPR using initial values at the start of the LOOP.  If *EXPR
1711    is a list, its elements are assumed to be combined using OP.  */
1712
1713 static void
1714 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
1715 {
1716   rtx head, tail, insn;
1717   rtx neutral, aggr;
1718   regset altered;
1719   edge e;
1720
1721   if (!*expr)
1722     return;
1723
1724   if (CONSTANT_P (*expr))
1725     return;
1726
1727   if (GET_CODE (*expr) == EXPR_LIST)
1728     {
1729       head = XEXP (*expr, 0);
1730       tail = XEXP (*expr, 1);
1731
1732       eliminate_implied_conditions (op, &head, tail);
1733
1734       if (op == AND)
1735         {
1736           neutral = const_true_rtx;
1737           aggr = const0_rtx;
1738         }
1739       else if (op == IOR)
1740         {
1741           neutral = const0_rtx;
1742           aggr = const_true_rtx;
1743         }
1744       else
1745         abort ();
1746
1747       simplify_using_initial_values (loop, UNKNOWN, &head);
1748       if (head == aggr)
1749         {
1750           XEXP (*expr, 0) = aggr;
1751           XEXP (*expr, 1) = NULL_RTX;
1752           return;
1753         }
1754       else if (head == neutral)
1755         {
1756           *expr = tail;
1757           simplify_using_initial_values (loop, op, expr);
1758           return;
1759         }
1760       simplify_using_initial_values (loop, op, &tail);
1761
1762       if (tail && XEXP (tail, 0) == aggr)
1763         {
1764           *expr = tail;
1765           return;
1766         }
1767
1768       XEXP (*expr, 0) = head;
1769       XEXP (*expr, 1) = tail;
1770       return;
1771     }
1772
1773   if (op != UNKNOWN)
1774     abort ();
1775
1776   e = loop_preheader_edge (loop);
1777   if (e->src == ENTRY_BLOCK_PTR)
1778     return;
1779
1780   altered = ALLOC_REG_SET (&reg_obstack);
1781
1782   while (1)
1783     {
1784       basic_block tmp_bb;
1785
1786       insn = BB_END (e->src);
1787       if (any_condjump_p (insn))
1788         {
1789           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1790
1791           if (cond && (e->flags & EDGE_FALLTHRU))
1792             cond = reversed_condition (cond);
1793           if (cond)
1794             {
1795               simplify_using_condition (cond, expr, altered);
1796               if (CONSTANT_P (*expr))
1797                 {
1798                   FREE_REG_SET (altered);
1799                   return;
1800                 }
1801             }
1802         }
1803
1804       FOR_BB_INSNS_REVERSE (e->src, insn)
1805         {
1806           if (!INSN_P (insn))
1807             continue;
1808
1809           simplify_using_assignment (insn, expr, altered);
1810           if (CONSTANT_P (*expr))
1811             {
1812               FREE_REG_SET (altered);
1813               return;
1814             }
1815         }
1816
1817       /* This is a bit subtle.  Store away e->src in tmp_bb, since we
1818          modify `e' and this can invalidate the subsequent count of
1819          e->src's predecessors by looking at the wrong block.  */
1820       tmp_bb = e->src;
1821       e = EDGE_PRED (tmp_bb, 0);
1822       if (EDGE_COUNT (tmp_bb->preds) > 1
1823           || e->src == ENTRY_BLOCK_PTR)
1824         break;
1825     }
1826
1827   FREE_REG_SET (altered);
1828 }
1829
1830 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
1831    that IV occurs as left operands of comparison COND and its signedness
1832    is SIGNED_P to DESC.  */
1833
1834 static void
1835 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1836                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1837 {
1838   rtx mmin, mmax, cond_over, cond_under;
1839
1840   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1841   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1842                                         iv->base, mmin);
1843   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1844                                        iv->base, mmax);
1845
1846   switch (cond)
1847     {
1848       case LE:
1849       case LT:
1850       case LEU:
1851       case LTU:
1852         if (cond_under != const0_rtx)
1853           desc->infinite =
1854                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1855         if (cond_over != const0_rtx)
1856           desc->noloop_assumptions =
1857                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1858         break;
1859
1860       case GE:
1861       case GT:
1862       case GEU:
1863       case GTU:
1864         if (cond_over != const0_rtx)
1865           desc->infinite =
1866                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1867         if (cond_under != const0_rtx)
1868           desc->noloop_assumptions =
1869                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1870         break;
1871
1872       case NE:
1873         if (cond_over != const0_rtx)
1874           desc->infinite =
1875                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1876         if (cond_under != const0_rtx)
1877           desc->infinite =
1878                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1879         break;
1880
1881       default:
1882         abort ();
1883     }
1884
1885   iv->mode = mode;
1886   iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1887 }
1888
1889 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1890    subregs of the same mode if possible (sometimes it is necessary to add
1891    some assumptions to DESC).  */
1892
1893 static bool
1894 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1895                          enum rtx_code cond, struct niter_desc *desc)
1896 {
1897   enum machine_mode comp_mode;
1898   bool signed_p;
1899
1900   /* If the ivs behave specially in the first iteration, or are
1901      added/multiplied after extending, we ignore them.  */
1902   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1903     return false;
1904   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1905     return false;
1906
1907   /* If there is some extend, it must match signedness of the comparison.  */
1908   switch (cond)
1909     {
1910       case LE:
1911       case LT:
1912         if (iv0->extend == ZERO_EXTEND
1913             || iv1->extend == ZERO_EXTEND)
1914           return false;
1915         signed_p = true;
1916         break;
1917
1918       case LEU:
1919       case LTU:
1920         if (iv0->extend == SIGN_EXTEND
1921             || iv1->extend == SIGN_EXTEND)
1922           return false;
1923         signed_p = false;
1924         break;
1925
1926       case NE:
1927         if (iv0->extend != UNKNOWN
1928             && iv1->extend != UNKNOWN
1929             && iv0->extend != iv1->extend)
1930           return false;
1931
1932         signed_p = false;
1933         if (iv0->extend != UNKNOWN)
1934           signed_p = iv0->extend == SIGN_EXTEND;
1935         if (iv1->extend != UNKNOWN)
1936           signed_p = iv1->extend == SIGN_EXTEND;
1937         break;
1938
1939       default:
1940         abort ();
1941     }
1942
1943   /* Values of both variables should be computed in the same mode.  These
1944      might indeed be different, if we have comparison like
1945
1946      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1947
1948      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1949      in different modes.  This does not seem impossible to handle, but
1950      it hardly ever occurs in practice.
1951
1952      The only exception is the case when one of operands is invariant.
1953      For example pentium 3 generates comparisons like
1954      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
1955      definitely do not want this prevent the optimization.  */
1956   comp_mode = iv0->extend_mode;
1957   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
1958     comp_mode = iv1->extend_mode;
1959
1960   if (iv0->extend_mode != comp_mode)
1961     {
1962       if (iv0->mode != iv0->extend_mode
1963           || iv0->step != const0_rtx)
1964         return false;
1965
1966       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1967                                       comp_mode, iv0->base, iv0->mode);
1968       iv0->extend_mode = comp_mode;
1969     }
1970
1971   if (iv1->extend_mode != comp_mode)
1972     {
1973       if (iv1->mode != iv1->extend_mode
1974           || iv1->step != const0_rtx)
1975         return false;
1976
1977       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1978                                       comp_mode, iv1->base, iv1->mode);
1979       iv1->extend_mode = comp_mode;
1980     }
1981
1982   /* Check that both ivs belong to a range of a single mode.  If one of the
1983      operands is an invariant, we may need to shorten it into the common
1984      mode.  */
1985   if (iv0->mode == iv0->extend_mode
1986       && iv0->step == const0_rtx
1987       && iv0->mode != iv1->mode)
1988     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
1989
1990   if (iv1->mode == iv1->extend_mode
1991       && iv1->step == const0_rtx
1992       && iv0->mode != iv1->mode)
1993     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
1994
1995   if (iv0->mode != iv1->mode)
1996     return false;
1997
1998   desc->mode = iv0->mode;
1999   desc->signed_p = signed_p;
2000
2001   return true;
2002 }
2003
2004 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
2005    the result into DESC.  Very similar to determine_number_of_iterations
2006    (basically its rtl version), complicated by things like subregs.  */
2007
2008 static void
2009 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
2010                          struct niter_desc *desc)
2011 {
2012   rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1;
2013   struct rtx_iv iv0, iv1, tmp_iv;
2014   rtx assumption, may_not_xform;
2015   enum rtx_code cond;
2016   enum machine_mode mode, comp_mode;
2017   rtx mmin, mmax, mode_mmin, mode_mmax;
2018   unsigned HOST_WIDEST_INT s, size, d, inv;
2019   HOST_WIDEST_INT up, down, inc, step_val;
2020   int was_sharp = false;
2021   rtx old_niter;
2022   bool step_is_pow2;
2023
2024   /* The meaning of these assumptions is this:
2025      if !assumptions
2026        then the rest of information does not have to be valid
2027      if noloop_assumptions then the loop does not roll
2028      if infinite then this exit is never used */
2029
2030   desc->assumptions = NULL_RTX;
2031   desc->noloop_assumptions = NULL_RTX;
2032   desc->infinite = NULL_RTX;
2033   desc->simple_p = true;
2034
2035   desc->const_iter = false;
2036   desc->niter_expr = NULL_RTX;
2037   desc->niter_max = 0;
2038
2039   cond = GET_CODE (condition);
2040   if (!COMPARISON_P (condition))
2041     abort ();
2042
2043   mode = GET_MODE (XEXP (condition, 0));
2044   if (mode == VOIDmode)
2045     mode = GET_MODE (XEXP (condition, 1));
2046   /* The constant comparisons should be folded.  */
2047   if (mode == VOIDmode)
2048     abort ();
2049
2050   /* We only handle integers or pointers.  */
2051   if (GET_MODE_CLASS (mode) != MODE_INT
2052       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2053     goto fail;
2054
2055   op0 = XEXP (condition, 0);
2056   def_insn = iv_get_reaching_def (insn, op0);
2057   if (!iv_analyze (def_insn, op0, &iv0))
2058     goto fail;
2059   if (iv0.extend_mode == VOIDmode)
2060     iv0.mode = iv0.extend_mode = mode;
2061
2062   op1 = XEXP (condition, 1);
2063   def_insn = iv_get_reaching_def (insn, op1);
2064   if (!iv_analyze (def_insn, op1, &iv1))
2065     goto fail;
2066   if (iv1.extend_mode == VOIDmode)
2067     iv1.mode = iv1.extend_mode = mode;
2068
2069   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2070       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2071     goto fail;
2072
2073   /* Check condition and normalize it.  */
2074
2075   switch (cond)
2076     {
2077       case GE:
2078       case GT:
2079       case GEU:
2080       case GTU:
2081         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2082         cond = swap_condition (cond);
2083         break;
2084       case NE:
2085       case LE:
2086       case LEU:
2087       case LT:
2088       case LTU:
2089         break;
2090       default:
2091         goto fail;
2092     }
2093
2094   /* Handle extends.  This is relatively nontrivial, so we only try in some
2095      easy cases, when we can canonicalize the ivs (possibly by adding some
2096      assumptions) to shape subreg (base + i * step).  This function also fills
2097      in desc->mode and desc->signed_p.  */
2098
2099   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2100     goto fail;
2101
2102   comp_mode = iv0.extend_mode;
2103   mode = iv0.mode;
2104   size = GET_MODE_BITSIZE (mode);
2105   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2106   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2107   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2108
2109   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2110     goto fail;
2111
2112   /* We can take care of the case of two induction variables chasing each other
2113      if the test is NE. I have never seen a loop using it, but still it is
2114      cool.  */
2115   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2116     {
2117       if (cond != NE)
2118         goto fail;
2119
2120       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2121       iv1.step = const0_rtx;
2122     }
2123
2124   /* This is either infinite loop or the one that ends immediately, depending
2125      on initial values.  Unswitching should remove this kind of conditions.  */
2126   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2127     goto fail;
2128
2129   if (cond != NE)
2130     {
2131       if (iv0.step == const0_rtx)
2132         step_val = -INTVAL (iv1.step);
2133       else
2134         step_val = INTVAL (iv0.step);
2135
2136       /* Ignore loops of while (i-- < 10) type.  */
2137       if (step_val < 0)
2138         goto fail;
2139
2140       step_is_pow2 = !(step_val & (step_val - 1));
2141     }
2142   else
2143     {
2144       /* We do not care about whether the step is power of two in this
2145          case.  */
2146       step_is_pow2 = false;
2147       step_val = 0;
2148     }
2149
2150   /* Some more condition normalization.  We must record some assumptions
2151      due to overflows.  */
2152   switch (cond)
2153     {
2154       case LT:
2155       case LTU:
2156         /* We want to take care only of non-sharp relationals; this is easy,
2157            as in cases the overflow would make the transformation unsafe
2158            the loop does not roll.  Seemingly it would make more sense to want
2159            to take care of sharp relationals instead, as NE is more similar to
2160            them, but the problem is that here the transformation would be more
2161            difficult due to possibly infinite loops.  */
2162         if (iv0.step == const0_rtx)
2163           {
2164             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2165             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2166                                                   mode_mmax);
2167             if (assumption == const_true_rtx)
2168               goto zero_iter;
2169             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2170                                             iv0.base, const1_rtx);
2171           }
2172         else
2173           {
2174             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2175             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2176                                                   mode_mmin);
2177             if (assumption == const_true_rtx)
2178               goto zero_iter;
2179             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2180                                             iv1.base, constm1_rtx);
2181           }
2182
2183         if (assumption != const0_rtx)
2184           desc->noloop_assumptions =
2185                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2186         cond = (cond == LT) ? LE : LEU;
2187
2188         /* It will be useful to be able to tell the difference once more in
2189            LE -> NE reduction.  */
2190         was_sharp = true;
2191         break;
2192       default: ;
2193     }
2194
2195   /* Take care of trivially infinite loops.  */
2196   if (cond != NE)
2197     {
2198       if (iv0.step == const0_rtx)
2199         {
2200           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2201           if (rtx_equal_p (tmp, mode_mmin))
2202             {
2203               desc->infinite =
2204                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2205               return;
2206             }
2207         }
2208       else
2209         {
2210           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2211           if (rtx_equal_p (tmp, mode_mmax))
2212             {
2213               desc->infinite =
2214                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2215               return;
2216             }
2217         }
2218     }
2219
2220   /* If we can we want to take care of NE conditions instead of size
2221      comparisons, as they are much more friendly (most importantly
2222      this takes care of special handling of loops with step 1).  We can
2223      do it if we first check that upper bound is greater or equal to
2224      lower bound, their difference is constant c modulo step and that
2225      there is not an overflow.  */
2226   if (cond != NE)
2227     {
2228       if (iv0.step == const0_rtx)
2229         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2230       else
2231         step = iv0.step;
2232       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2233       delta = lowpart_subreg (mode, delta, comp_mode);
2234       delta = simplify_gen_binary (UMOD, mode, delta, step);
2235       may_xform = const0_rtx;
2236       may_not_xform = const_true_rtx;
2237
2238       if (GET_CODE (delta) == CONST_INT)
2239         {
2240           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2241             {
2242               /* A special case.  We have transformed condition of type
2243                  for (i = 0; i < 4; i += 4)
2244                  into
2245                  for (i = 0; i <= 3; i += 4)
2246                  obviously if the test for overflow during that transformation
2247                  passed, we cannot overflow here.  Most importantly any
2248                  loop with sharp end condition and step 1 falls into this
2249                  category, so handling this case specially is definitely
2250                  worth the troubles.  */
2251               may_xform = const_true_rtx;
2252             }
2253           else if (iv0.step == const0_rtx)
2254             {
2255               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2256               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2257               bound = lowpart_subreg (mode, bound, comp_mode);
2258               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2259               may_xform = simplify_gen_relational (cond, SImode, mode,
2260                                                    bound, tmp);
2261               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2262                                                        SImode, mode,
2263                                                        bound, tmp);
2264             }
2265           else
2266             {
2267               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2268               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2269               bound = lowpart_subreg (mode, bound, comp_mode);
2270               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2271               may_xform = simplify_gen_relational (cond, SImode, mode,
2272                                                    tmp, bound);
2273               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2274                                                        SImode, mode,
2275                                                        tmp, bound);
2276             }
2277         }
2278
2279       if (may_xform != const0_rtx)
2280         {
2281           /* We perform the transformation always provided that it is not
2282              completely senseless.  This is OK, as we would need this assumption
2283              to determine the number of iterations anyway.  */
2284           if (may_xform != const_true_rtx)
2285             {
2286               /* If the step is a power of two and the final value we have
2287                  computed overflows, the cycle is infinite.  Otherwise it
2288                  is nontrivial to compute the number of iterations.  */
2289               if (step_is_pow2)
2290                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2291                                                   desc->infinite);
2292               else
2293                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2294                                                      desc->assumptions);
2295             }
2296
2297           /* We are going to lose some information about upper bound on
2298              number of iterations in this step, so record the information
2299              here.  */
2300           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2301           if (GET_CODE (iv1.base) == CONST_INT)
2302             up = INTVAL (iv1.base);
2303           else
2304             up = INTVAL (mode_mmax) - inc;
2305           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2306                          ? iv0.base
2307                          : mode_mmin);
2308           desc->niter_max = (up - down) / inc + 1;
2309
2310           if (iv0.step == const0_rtx)
2311             {
2312               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2313               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2314             }
2315           else
2316             {
2317               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2318               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2319             }
2320
2321           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2322           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2323           assumption = simplify_gen_relational (reverse_condition (cond),
2324                                                 SImode, mode, tmp0, tmp1);
2325           if (assumption == const_true_rtx)
2326             goto zero_iter;
2327           else if (assumption != const0_rtx)
2328             desc->noloop_assumptions =
2329                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2330           cond = NE;
2331         }
2332     }
2333
2334   /* Count the number of iterations.  */
2335   if (cond == NE)
2336     {
2337       /* Everything we do here is just arithmetics modulo size of mode.  This
2338          makes us able to do more involved computations of number of iterations
2339          than in other cases.  First transform the condition into shape
2340          s * i <> c, with s positive.  */
2341       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2342       iv0.base = const0_rtx;
2343       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2344       iv1.step = const0_rtx;
2345       if (INTVAL (iv0.step) < 0)
2346         {
2347           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2348           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2349         }
2350       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2351
2352       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2353          is infinite.  Otherwise, the number of iterations is
2354          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2355       s = INTVAL (iv0.step); d = 1;
2356       while (s % 2 != 1)
2357         {
2358           s /= 2;
2359           d *= 2;
2360           size--;
2361         }
2362       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2363
2364       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2365       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2366       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2367       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2368
2369       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2370       inv = inverse (s, size);
2371       tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
2372       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2373     }
2374   else
2375     {
2376       if (iv1.step == const0_rtx)
2377         /* Condition in shape a + s * i <= b
2378            We must know that b + s does not overflow and a <= b + s and then we
2379            can compute number of iterations as (b + s - a) / s.  (It might
2380            seem that we in fact could be more clever about testing the b + s
2381            overflow condition using some information about b - a mod s,
2382            but it was already taken into account during LE -> NE transform).  */
2383         {
2384           step = iv0.step;
2385           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2386           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2387
2388           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2389                                        lowpart_subreg (mode, step,
2390                                                        comp_mode));
2391           if (step_is_pow2)
2392             {
2393               rtx t0, t1;
2394
2395               /* If s is power of 2, we know that the loop is infinite if
2396                  a % s <= b % s and b + s overflows.  */
2397               assumption = simplify_gen_relational (reverse_condition (cond),
2398                                                     SImode, mode,
2399                                                     tmp1, bound);
2400
2401               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2402               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2403               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2404               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2405               desc->infinite =
2406                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2407             }
2408           else
2409             {
2410               assumption = simplify_gen_relational (cond, SImode, mode,
2411                                                     tmp1, bound);
2412               desc->assumptions =
2413                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2414             }
2415
2416           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2417           tmp = lowpart_subreg (mode, tmp, comp_mode);
2418           assumption = simplify_gen_relational (reverse_condition (cond),
2419                                                 SImode, mode, tmp0, tmp);
2420
2421           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2422           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2423         }
2424       else
2425         {
2426           /* Condition in shape a <= b - s * i
2427              We must know that a - s does not overflow and a - s <= b and then
2428              we can again compute number of iterations as (b - (a - s)) / s.  */
2429           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2430           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2431           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2432
2433           bound = simplify_gen_binary (MINUS, mode, mode_mmin,
2434                                        lowpart_subreg (mode, step, comp_mode));
2435           if (step_is_pow2)
2436             {
2437               rtx t0, t1;
2438
2439               /* If s is power of 2, we know that the loop is infinite if
2440                  a % s <= b % s and a - s overflows.  */
2441               assumption = simplify_gen_relational (reverse_condition (cond),
2442                                                     SImode, mode,
2443                                                     bound, tmp0);
2444
2445               t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
2446               t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
2447               tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
2448               assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
2449               desc->infinite =
2450                       alloc_EXPR_LIST (0, assumption, desc->infinite);
2451             }
2452           else
2453             {
2454               assumption = simplify_gen_relational (cond, SImode, mode,
2455                                                     bound, tmp0);
2456               desc->assumptions =
2457                       alloc_EXPR_LIST (0, assumption, desc->assumptions);
2458             }
2459
2460           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2461           tmp = lowpart_subreg (mode, tmp, comp_mode);
2462           assumption = simplify_gen_relational (reverse_condition (cond),
2463                                                 SImode, mode,
2464                                                 tmp, tmp1);
2465           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2466           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2467         }
2468       if (assumption == const_true_rtx)
2469         goto zero_iter;
2470       else if (assumption != const0_rtx)
2471         desc->noloop_assumptions =
2472                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2473       delta = simplify_gen_binary (UDIV, mode, delta, step);
2474       desc->niter_expr = delta;
2475     }
2476
2477   old_niter = desc->niter_expr;
2478
2479   simplify_using_initial_values (loop, AND, &desc->assumptions);
2480   if (desc->assumptions
2481       && XEXP (desc->assumptions, 0) == const0_rtx)
2482     goto fail;
2483   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2484   simplify_using_initial_values (loop, IOR, &desc->infinite);
2485   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2486
2487   /* Rerun the simplification.  Consider code (created by copying loop headers)
2488
2489      i = 0;
2490
2491      if (0 < n)
2492        {
2493          do
2494            {
2495              i++;
2496            } while (i < n);
2497        }
2498
2499     The first pass determines that i = 0, the second pass uses it to eliminate
2500     noloop assumption.  */
2501
2502   simplify_using_initial_values (loop, AND, &desc->assumptions);
2503   if (desc->assumptions
2504       && XEXP (desc->assumptions, 0) == const0_rtx)
2505     goto fail;
2506   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2507   simplify_using_initial_values (loop, IOR, &desc->infinite);
2508   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2509
2510   if (desc->noloop_assumptions
2511       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2512     goto zero_iter;
2513
2514   if (GET_CODE (desc->niter_expr) == CONST_INT)
2515     {
2516       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2517
2518       desc->const_iter = true;
2519       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2520     }
2521   else
2522     {
2523       if (!desc->niter_max)
2524         desc->niter_max = determine_max_iter (desc);
2525
2526       /* simplify_using_initial_values does a copy propagation on the registers
2527          in the expression for the number of iterations.  This prolongs life
2528          ranges of registers and increases register pressure, and usually
2529          brings no gain (and if it happens to do, the cse pass will take care
2530          of it anyway).  So prevent this behavior, unless it enabled us to
2531          derive that the number of iterations is a constant.  */
2532       desc->niter_expr = old_niter;
2533     }
2534
2535   return;
2536
2537 fail:
2538   desc->simple_p = false;
2539   return;
2540
2541 zero_iter:
2542   desc->const_iter = true;
2543   desc->niter = 0;
2544   desc->niter_max = 0;
2545   desc->niter_expr = const0_rtx;
2546   return;
2547 }
2548
2549 /* Checks whether E is a simple exit from LOOP and stores its description
2550    into DESC.  */
2551
2552 static void
2553 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2554 {
2555   basic_block exit_bb;
2556   rtx condition, at;
2557   edge ein;
2558
2559   exit_bb = e->src;
2560   desc->simple_p = false;
2561
2562   /* It must belong directly to the loop.  */
2563   if (exit_bb->loop_father != loop)
2564     return;
2565
2566   /* It must be tested (at least) once during any iteration.  */
2567   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2568     return;
2569
2570   /* It must end in a simple conditional jump.  */
2571   if (!any_condjump_p (BB_END (exit_bb)))
2572     return;
2573
2574   ein = EDGE_SUCC (exit_bb, 0);
2575   if (ein == e)
2576     ein = EDGE_SUCC (exit_bb, 1);
2577
2578   desc->out_edge = e;
2579   desc->in_edge = ein;
2580
2581   /* Test whether the condition is suitable.  */
2582   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2583     return;
2584
2585   if (ein->flags & EDGE_FALLTHRU)
2586     {
2587       condition = reversed_condition (condition);
2588       if (!condition)
2589         return;
2590     }
2591
2592   /* Check that we are able to determine number of iterations and fill
2593      in information about it.  */
2594   iv_number_of_iterations (loop, at, condition, desc);
2595 }
2596
2597 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2598
2599 void
2600 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2601 {
2602   unsigned i;
2603   basic_block *body;
2604   edge e;
2605   struct niter_desc act;
2606   bool any = false;
2607   edge_iterator ei;
2608
2609   desc->simple_p = false;
2610   body = get_loop_body (loop);
2611
2612   for (i = 0; i < loop->num_nodes; i++)
2613     {
2614       FOR_EACH_EDGE (e, ei, body[i]->succs)
2615         {
2616           if (flow_bb_inside_loop_p (loop, e->dest))
2617             continue;
2618
2619           check_simple_exit (loop, e, &act);
2620           if (!act.simple_p)
2621             continue;
2622
2623           /* Prefer constant iterations; the less the better.  */
2624           if (!any)
2625             any = true;
2626           else if (!act.const_iter
2627                    || (desc->const_iter && act.niter >= desc->niter))
2628             continue;
2629           *desc = act;
2630         }
2631     }
2632
2633   if (dump_file)
2634     {
2635       if (desc->simple_p)
2636         {
2637           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2638           fprintf (dump_file, "  simple exit %d -> %d\n",
2639                    desc->out_edge->src->index,
2640                    desc->out_edge->dest->index);
2641           if (desc->assumptions)
2642             {
2643               fprintf (dump_file, "  assumptions: ");
2644               print_rtl (dump_file, desc->assumptions);
2645               fprintf (dump_file, "\n");
2646             }
2647           if (desc->noloop_assumptions)
2648             {
2649               fprintf (dump_file, "  does not roll if: ");
2650               print_rtl (dump_file, desc->noloop_assumptions);
2651               fprintf (dump_file, "\n");
2652             }
2653           if (desc->infinite)
2654             {
2655               fprintf (dump_file, "  infinite if: ");
2656               print_rtl (dump_file, desc->infinite);
2657               fprintf (dump_file, "\n");
2658             }
2659
2660           fprintf (dump_file, "  number of iterations: ");
2661           print_rtl (dump_file, desc->niter_expr);
2662           fprintf (dump_file, "\n");
2663
2664           fprintf (dump_file, "  upper bound: ");
2665           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2666           fprintf (dump_file, "\n");
2667         }
2668       else
2669         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2670     }
2671
2672   free (body);
2673 }
2674
2675 /* Creates a simple loop description of LOOP if it was not computed
2676    already.  */
2677
2678 struct niter_desc *
2679 get_simple_loop_desc (struct loop *loop)
2680 {
2681   struct niter_desc *desc = simple_loop_desc (loop);
2682
2683   if (desc)
2684     return desc;
2685
2686   desc = xmalloc (sizeof (struct niter_desc));
2687   iv_analysis_loop_init (loop);
2688   find_simple_exit (loop, desc);
2689   loop->aux = desc;
2690
2691   return desc;
2692 }
2693
2694 /* Releases simple loop description for LOOP.  */
2695
2696 void
2697 free_simple_loop_desc (struct loop *loop)
2698 {
2699   struct niter_desc *desc = simple_loop_desc (loop);
2700
2701   if (!desc)
2702     return;
2703
2704   free (desc);
2705   loop->aux = NULL;
2706 }