gcc/loop-iv.c

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