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;
2021   int was_sharp = false;
2022   rtx old_niter;
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   /* Ignore loops of while (i-- < 10) type.  */
2130   if (cond != NE
2131       && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
2132     goto fail;
2133
2134   /* Some more condition normalization.  We must record some assumptions
2135      due to overflows.  */
2136   switch (cond)
2137     {
2138       case LT:
2139       case LTU:
2140         /* We want to take care only of non-sharp relationals; this is easy,
2141            as in cases the overflow would make the transformation unsafe
2142            the loop does not roll.  Seemingly it would make more sense to want
2143            to take care of sharp relationals instead, as NE is more similar to
2144            them, but the problem is that here the transformation would be more
2145            difficult due to possibly infinite loops.  */
2146         if (iv0.step == const0_rtx)
2147           {
2148             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2149             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2150                                                   mode_mmax);
2151             if (assumption == const_true_rtx)
2152               goto zero_iter;
2153             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2154                                             iv0.base, const1_rtx);
2155           }
2156         else
2157           {
2158             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2159             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2160                                                   mode_mmin);
2161             if (assumption == const_true_rtx)
2162               goto zero_iter;
2163             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2164                                             iv1.base, constm1_rtx);
2165           }
2166
2167         if (assumption != const0_rtx)
2168           desc->noloop_assumptions =
2169                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2170         cond = (cond == LT) ? LE : LEU;
2171
2172         /* It will be useful to be able to tell the difference once more in
2173            LE -> NE reduction.  */
2174         was_sharp = true;
2175         break;
2176       default: ;
2177     }
2178
2179   /* Take care of trivially infinite loops.  */
2180   if (cond != NE)
2181     {
2182       if (iv0.step == const0_rtx)
2183         {
2184           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2185           if (rtx_equal_p (tmp, mode_mmin))
2186             {
2187               desc->infinite =
2188                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2189               return;
2190             }
2191         }
2192       else
2193         {
2194           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2195           if (rtx_equal_p (tmp, mode_mmax))
2196             {
2197               desc->infinite =
2198                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2199               return;
2200             }
2201         }
2202     }
2203
2204   /* If we can we want to take care of NE conditions instead of size
2205      comparisons, as they are much more friendly (most importantly
2206      this takes care of special handling of loops with step 1).  We can
2207      do it if we first check that upper bound is greater or equal to
2208      lower bound, their difference is constant c modulo step and that
2209      there is not an overflow.  */
2210   if (cond != NE)
2211     {
2212       if (iv0.step == const0_rtx)
2213         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2214       else
2215         step = iv0.step;
2216       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2217       delta = lowpart_subreg (mode, delta, comp_mode);
2218       delta = simplify_gen_binary (UMOD, mode, delta, step);
2219       may_xform = const0_rtx;
2220       may_not_xform = const_true_rtx;
2221
2222       if (GET_CODE (delta) == CONST_INT)
2223         {
2224           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2225             {
2226               /* A special case.  We have transformed condition of type
2227                  for (i = 0; i < 4; i += 4)
2228                  into
2229                  for (i = 0; i <= 3; i += 4)
2230                  obviously if the test for overflow during that transformation
2231                  passed, we cannot overflow here.  Most importantly any
2232                  loop with sharp end condition and step 1 falls into this
2233                  category, so handling this case specially is definitely
2234                  worth the troubles.  */
2235               may_xform = const_true_rtx;
2236             }
2237           else if (iv0.step == const0_rtx)
2238             {
2239               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2240               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2241               bound = lowpart_subreg (mode, bound, comp_mode);
2242               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2243               may_xform = simplify_gen_relational (cond, SImode, mode,
2244                                                    bound, tmp);
2245               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2246                                                        SImode, mode,
2247                                                        bound, tmp);
2248             }
2249           else
2250             {
2251               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2252               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2253               bound = lowpart_subreg (mode, bound, comp_mode);
2254               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2255               may_xform = simplify_gen_relational (cond, SImode, mode,
2256                                                    tmp, bound);
2257               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2258                                                        SImode, mode,
2259                                                        tmp, bound);
2260             }
2261         }
2262
2263       if (may_xform != const0_rtx)
2264         {
2265           /* We perform the transformation always provided that it is not
2266              completely senseless.  This is OK, as we would need this assumption
2267              to determine the number of iterations anyway.  */
2268           if (may_xform != const_true_rtx)
2269             {
2270               /* If the step is a power of two and the final value we have
2271                  computed overflows, the cycle is infinite.  Otherwise it
2272                  is nontrivial to compute the number of iterations.  */
2273               s = INTVAL (step);
2274               if ((s & (s - 1)) == 0)
2275                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2276                                                   desc->infinite);
2277               else
2278                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2279                                                      desc->assumptions);
2280             }
2281
2282           /* We are going to lose some information about upper bound on
2283              number of iterations in this step, so record the information
2284              here.  */
2285           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2286           if (GET_CODE (iv1.base) == CONST_INT)
2287             up = INTVAL (iv1.base);
2288           else
2289             up = INTVAL (mode_mmax) - inc;
2290           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2291                          ? iv0.base
2292                          : mode_mmin);
2293           desc->niter_max = (up - down) / inc + 1;
2294
2295           if (iv0.step == const0_rtx)
2296             {
2297               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2298               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2299             }
2300           else
2301             {
2302               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2303               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2304             }
2305
2306           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2307           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2308           assumption = simplify_gen_relational (reverse_condition (cond),
2309                                                 SImode, mode, tmp0, tmp1);
2310           if (assumption == const_true_rtx)
2311             goto zero_iter;
2312           else if (assumption != const0_rtx)
2313             desc->noloop_assumptions =
2314                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2315           cond = NE;
2316         }
2317     }
2318
2319   /* Count the number of iterations.  */
2320   if (cond == NE)
2321     {
2322       /* Everything we do here is just arithmetics modulo size of mode.  This
2323          makes us able to do more involved computations of number of iterations
2324          than in other cases.  First transform the condition into shape
2325          s * i <> c, with s positive.  */
2326       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2327       iv0.base = const0_rtx;
2328       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2329       iv1.step = const0_rtx;
2330       if (INTVAL (iv0.step) < 0)
2331         {
2332           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2333           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2334         }
2335       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2336
2337       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2338          is infinite.  Otherwise, the number of iterations is
2339          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2340       s = INTVAL (iv0.step); d = 1;
2341       while (s % 2 != 1)
2342         {
2343           s /= 2;
2344           d *= 2;
2345           size--;
2346         }
2347       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2348
2349       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2350       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2351       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2352       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2353
2354       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2355       inv = inverse (s, size);
2356       inv = trunc_int_for_mode (inv, mode);
2357       tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
2358       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2359     }
2360   else
2361     {
2362       if (iv1.step == const0_rtx)
2363         /* Condition in shape a + s * i <= b
2364            We must know that b + s does not overflow and a <= b + s and then we
2365            can compute number of iterations as (b + s - a) / s.  (It might
2366            seem that we in fact could be more clever about testing the b + s
2367            overflow condition using some information about b - a mod s,
2368            but it was already taken into account during LE -> NE transform).  */
2369         {
2370           step = iv0.step;
2371           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2372           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2373
2374           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2375                                        lowpart_subreg (mode, step, comp_mode));
2376           assumption = simplify_gen_relational (cond, SImode, mode,
2377                                                 tmp1, bound);
2378           desc->assumptions =
2379                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2380
2381           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2382           tmp = lowpart_subreg (mode, tmp, comp_mode);
2383           assumption = simplify_gen_relational (reverse_condition (cond),
2384                                                 SImode, mode, tmp0, tmp);
2385
2386           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2387           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2388         }
2389       else
2390         {
2391           /* Condition in shape a <= b - s * i
2392              We must know that a - s does not overflow and a - s <= b and then
2393              we can again compute number of iterations as (b - (a - s)) / s.  */
2394           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2395           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2396           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2397
2398           bound = simplify_gen_binary (MINUS, mode, mode_mmin,
2399                                        lowpart_subreg (mode, step, comp_mode));
2400           assumption = simplify_gen_relational (cond, SImode, mode,
2401                                                 bound, tmp0);
2402           desc->assumptions =
2403                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2404
2405           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2406           tmp = lowpart_subreg (mode, tmp, comp_mode);
2407           assumption = simplify_gen_relational (reverse_condition (cond),
2408                                                 SImode, mode,
2409                                                 tmp, tmp1);
2410           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2411           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2412         }
2413       if (assumption == const_true_rtx)
2414         goto zero_iter;
2415       else if (assumption != const0_rtx)
2416         desc->noloop_assumptions =
2417                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2418       delta = simplify_gen_binary (UDIV, mode, delta, step);
2419       desc->niter_expr = delta;
2420     }
2421
2422   old_niter = desc->niter_expr;
2423
2424   simplify_using_initial_values (loop, AND, &desc->assumptions);
2425   if (desc->assumptions
2426       && XEXP (desc->assumptions, 0) == const0_rtx)
2427     goto fail;
2428   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2429   simplify_using_initial_values (loop, IOR, &desc->infinite);
2430   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2431
2432   /* Rerun the simplification.  Consider code (created by copying loop headers)
2433
2434      i = 0;
2435
2436      if (0 < n)
2437        {
2438          do
2439            {
2440              i++;
2441            } while (i < n);
2442        }
2443
2444     The first pass determines that i = 0, the second pass uses it to eliminate
2445     noloop assumption.  */
2446
2447   simplify_using_initial_values (loop, AND, &desc->assumptions);
2448   if (desc->assumptions
2449       && XEXP (desc->assumptions, 0) == const0_rtx)
2450     goto fail;
2451   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2452   simplify_using_initial_values (loop, IOR, &desc->infinite);
2453   simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
2454
2455   if (desc->noloop_assumptions
2456       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2457     goto zero_iter;
2458
2459   if (GET_CODE (desc->niter_expr) == CONST_INT)
2460     {
2461       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2462
2463       desc->const_iter = true;
2464       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2465     }
2466   else
2467     {
2468       if (!desc->niter_max)
2469         desc->niter_max = determine_max_iter (desc);
2470
2471       /* simplify_using_initial_values does a copy propagation on the registers
2472          in the expression for the number of iterations.  This prolongs life
2473          ranges of registers and increases register pressure, and usually
2474          brings no gain (and if it happens to do, the cse pass will take care
2475          of it anyway).  So prevent this behavior, unless it enabled us to
2476          derive that the number of iterations is a constant.  */
2477       desc->niter_expr = old_niter;
2478     }
2479
2480   return;
2481
2482 fail:
2483   desc->simple_p = false;
2484   return;
2485
2486 zero_iter:
2487   desc->const_iter = true;
2488   desc->niter = 0;
2489   desc->niter_max = 0;
2490   desc->niter_expr = const0_rtx;
2491   return;
2492 }
2493
2494 /* Checks whether E is a simple exit from LOOP and stores its description
2495    into DESC.  */
2496
2497 static void
2498 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2499 {
2500   basic_block exit_bb;
2501   rtx condition, at;
2502   edge ein;
2503
2504   exit_bb = e->src;
2505   desc->simple_p = false;
2506
2507   /* It must belong directly to the loop.  */
2508   if (exit_bb->loop_father != loop)
2509     return;
2510
2511   /* It must be tested (at least) once during any iteration.  */
2512   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2513     return;
2514
2515   /* It must end in a simple conditional jump.  */
2516   if (!any_condjump_p (BB_END (exit_bb)))
2517     return;
2518
2519   ein = EDGE_SUCC (exit_bb, 0);
2520   if (ein == e)
2521     ein = EDGE_SUCC (exit_bb, 1);
2522
2523   desc->out_edge = e;
2524   desc->in_edge = ein;
2525
2526   /* Test whether the condition is suitable.  */
2527   if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
2528     return;
2529
2530   if (ein->flags & EDGE_FALLTHRU)
2531     {
2532       condition = reversed_condition (condition);
2533       if (!condition)
2534         return;
2535     }
2536
2537   /* Check that we are able to determine number of iterations and fill
2538      in information about it.  */
2539   iv_number_of_iterations (loop, at, condition, desc);
2540 }
2541
2542 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2543
2544 void
2545 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2546 {
2547   unsigned i;
2548   basic_block *body;
2549   edge e;
2550   struct niter_desc act;
2551   bool any = false;
2552   edge_iterator ei;
2553
2554   desc->simple_p = false;
2555   body = get_loop_body (loop);
2556
2557   for (i = 0; i < loop->num_nodes; i++)
2558     {
2559       FOR_EACH_EDGE (e, ei, body[i]->succs)
2560         {
2561           if (flow_bb_inside_loop_p (loop, e->dest))
2562             continue;
2563
2564           check_simple_exit (loop, e, &act);
2565           if (!act.simple_p)
2566             continue;
2567
2568           /* Prefer constant iterations; the less the better.  */
2569           if (!any)
2570             any = true;
2571           else if (!act.const_iter
2572                    || (desc->const_iter && act.niter >= desc->niter))
2573             continue;
2574           *desc = act;
2575         }
2576     }
2577
2578   if (dump_file)
2579     {
2580       if (desc->simple_p)
2581         {
2582           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2583           fprintf (dump_file, "  simple exit %d -> %d\n",
2584                    desc->out_edge->src->index,
2585                    desc->out_edge->dest->index);
2586           if (desc->assumptions)
2587             {
2588               fprintf (dump_file, "  assumptions: ");
2589               print_rtl (dump_file, desc->assumptions);
2590               fprintf (dump_file, "\n");
2591             }
2592           if (desc->noloop_assumptions)
2593             {
2594               fprintf (dump_file, "  does not roll if: ");
2595               print_rtl (dump_file, desc->noloop_assumptions);
2596               fprintf (dump_file, "\n");
2597             }
2598           if (desc->infinite)
2599             {
2600               fprintf (dump_file, "  infinite if: ");
2601               print_rtl (dump_file, desc->infinite);
2602               fprintf (dump_file, "\n");
2603             }
2604
2605           fprintf (dump_file, "  number of iterations: ");
2606           print_rtl (dump_file, desc->niter_expr);
2607           fprintf (dump_file, "\n");
2608
2609           fprintf (dump_file, "  upper bound: ");
2610           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2611           fprintf (dump_file, "\n");
2612         }
2613       else
2614         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2615     }
2616
2617   free (body);
2618 }
2619
2620 /* Creates a simple loop description of LOOP if it was not computed
2621    already.  */
2622
2623 struct niter_desc *
2624 get_simple_loop_desc (struct loop *loop)
2625 {
2626   struct niter_desc *desc = simple_loop_desc (loop);
2627
2628   if (desc)
2629     return desc;
2630
2631   desc = xmalloc (sizeof (struct niter_desc));
2632   iv_analysis_loop_init (loop);
2633   find_simple_exit (loop, desc);
2634   loop->aux = desc;
2635
2636   return desc;
2637 }
2638
2639 /* Releases simple loop description for LOOP.  */
2640
2641 void
2642 free_simple_loop_desc (struct loop *loop)
2643 {
2644   struct niter_desc *desc = simple_loop_desc (loop);
2645
2646   if (!desc)
2647     return;
2648
2649   free (desc);
2650   loop->aux = NULL;
2651 }