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 = NULL_RTX, 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           rtx cond = get_condition (BB_END (e->src), NULL, false, true);
1741
1742           if (cond && (e->flags & EDGE_FALLTHRU))
1743             cond = reversed_condition (cond);
1744           if (cond)
1745             {
1746               simplify_using_condition (cond, expr, altered);
1747               if (CONSTANT_P (*expr))
1748                 {
1749                   FREE_REG_SET (altered);
1750                   return;
1751                 }
1752             }
1753         }
1754
1755       FOR_BB_INSNS_REVERSE (e->src, insn)
1756         {
1757           if (!INSN_P (insn))
1758             continue;
1759
1760           simplify_using_assignment (insn, expr, altered);
1761           if (CONSTANT_P (*expr))
1762             {
1763               FREE_REG_SET (altered);
1764               return;
1765             }
1766         }
1767
1768       e = e->src->pred;
1769       if (e->pred_next
1770           || e->src == ENTRY_BLOCK_PTR)
1771         break;
1772     }
1773
1774   FREE_REG_SET (altered);
1775 }
1776
1777 /* Transforms invariant IV into MODE.  Adds assumptions based on the fact
1778    that IV occurs as left operands of comparison COND and its signedness
1779    is SIGNED_P to DESC.  */
1780
1781 static void
1782 shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
1783                    enum rtx_code cond, bool signed_p, struct niter_desc *desc)
1784 {
1785   rtx mmin, mmax, cond_over, cond_under;
1786
1787   get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
1788   cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
1789                                         iv->base, mmin);
1790   cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
1791                                        iv->base, mmax);
1792
1793   switch (cond)
1794     {
1795       case LE:
1796       case LT:
1797       case LEU:
1798       case LTU:
1799         if (cond_under != const0_rtx)
1800           desc->infinite =
1801                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1802         if (cond_over != const0_rtx)
1803           desc->noloop_assumptions =
1804                   alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
1805         break;
1806
1807       case GE:
1808       case GT:
1809       case GEU:
1810       case GTU:
1811         if (cond_over != const0_rtx)
1812           desc->infinite =
1813                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1814         if (cond_under != const0_rtx)
1815           desc->noloop_assumptions =
1816                   alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
1817         break;
1818
1819       case NE:
1820         if (cond_over != const0_rtx)
1821           desc->infinite =
1822                   alloc_EXPR_LIST (0, cond_over, desc->infinite);
1823         if (cond_under != const0_rtx)
1824           desc->infinite =
1825                   alloc_EXPR_LIST (0, cond_under, desc->infinite);
1826         break;
1827
1828       default:
1829         abort ();
1830     }
1831
1832   iv->mode = mode;
1833   iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
1834 }
1835
1836 /* Transforms IV0 and IV1 compared by COND so that they are both compared as
1837    subregs of the same mode if possible (sometimes it is necessary to add
1838    some assumptions to DESC).  */
1839
1840 static bool
1841 canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
1842                          enum rtx_code cond, struct niter_desc *desc)
1843 {
1844   enum machine_mode comp_mode;
1845   bool signed_p;
1846
1847   /* If the ivs behave specially in the first iteration, or are
1848      added/multiplied after extending, we ignore them.  */
1849   if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
1850     return false;
1851   if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
1852     return false;
1853
1854   /* If there is some extend, it must match signedness of the comparison.  */
1855   switch (cond)
1856     {
1857       case LE:
1858       case LT:
1859         if (iv0->extend == ZERO_EXTEND
1860             || iv1->extend == ZERO_EXTEND)
1861           return false;
1862         signed_p = true;
1863         break;
1864
1865       case LEU:
1866       case LTU:
1867         if (iv0->extend == SIGN_EXTEND
1868             || iv1->extend == SIGN_EXTEND)
1869           return false;
1870         signed_p = false;
1871         break;
1872
1873       case NE:
1874         if (iv0->extend != NIL
1875             && iv1->extend != NIL
1876             && iv0->extend != iv1->extend)
1877           return false;
1878
1879         signed_p = false;
1880         if (iv0->extend != NIL)
1881           signed_p = iv0->extend == SIGN_EXTEND;
1882         if (iv1->extend != NIL)
1883           signed_p = iv1->extend == SIGN_EXTEND;
1884         break;
1885
1886       default:
1887         abort ();
1888     }
1889
1890   /* Values of both variables should be computed in the same mode.  These
1891      might indeed be different, if we have comparison like
1892
1893      (compare (subreg:SI (iv0)) (subreg:SI (iv1)))
1894
1895      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
1896      in different modes.  This does not seem impossible to handle, but
1897      it hardly ever occurs in practice.
1898
1899      The only exception is the case when one of operands is invariant.
1900      For example pentium 3 generates comparisons like
1901      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
1902      definitely do not want this prevent the optimization.  */
1903   comp_mode = iv0->extend_mode;
1904   if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
1905     comp_mode = iv1->extend_mode;
1906
1907   if (iv0->extend_mode != comp_mode)
1908     {
1909       if (iv0->mode != iv0->extend_mode
1910           || iv0->step != const0_rtx)
1911         return false;
1912
1913       iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1914                                       comp_mode, iv0->base, iv0->mode);
1915       iv0->extend_mode = comp_mode;
1916     }
1917
1918   if (iv1->extend_mode != comp_mode)
1919     {
1920       if (iv1->mode != iv1->extend_mode
1921           || iv1->step != const0_rtx)
1922         return false;
1923
1924       iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
1925                                       comp_mode, iv1->base, iv1->mode);
1926       iv1->extend_mode = comp_mode;
1927     }
1928
1929   /* Check that both ivs belong to a range of a single mode.  If one of the
1930      operands is an invariant, we may need to shorten it into the common
1931      mode.  */
1932   if (iv0->mode == iv0->extend_mode
1933       && iv0->step == const0_rtx
1934       && iv0->mode != iv1->mode)
1935     shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
1936
1937   if (iv1->mode == iv1->extend_mode
1938       && iv1->step == const0_rtx
1939       && iv0->mode != iv1->mode)
1940     shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
1941
1942   if (iv0->mode != iv1->mode)
1943     return false;
1944
1945   desc->mode = iv0->mode;
1946   desc->signed_p = signed_p;
1947
1948   return true;
1949 }
1950
1951 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
1952    the result into DESC.  Very similar to determine_number_of_iterations
1953    (basically its rtl version), complicated by things like subregs.  */
1954
1955 void
1956 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
1957                          struct niter_desc *desc)
1958 {
1959   rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1;
1960   struct rtx_iv iv0, iv1, tmp_iv;
1961   rtx assumption, may_not_xform;
1962   enum rtx_code cond;
1963   enum machine_mode mode, comp_mode;
1964   rtx mmin, mmax, mode_mmin, mode_mmax;
1965   unsigned HOST_WIDEST_INT s, size, d, inv;
1966   HOST_WIDEST_INT up, down, inc;
1967   int was_sharp = false;
1968   rtx old_niter;
1969
1970   /* The meaning of these assumptions is this:
1971      if !assumptions
1972        then the rest of information does not have to be valid
1973      if noloop_assumptions then the loop does not roll
1974      if infinite then this exit is never used */
1975
1976   desc->assumptions = NULL_RTX;
1977   desc->noloop_assumptions = NULL_RTX;
1978   desc->infinite = NULL_RTX;
1979   desc->simple_p = true;
1980
1981   desc->const_iter = false;
1982   desc->niter_expr = NULL_RTX;
1983   desc->niter_max = 0;
1984
1985   cond = GET_CODE (condition);
1986   if (!COMPARISON_P (condition))
1987     abort ();
1988
1989   mode = GET_MODE (XEXP (condition, 0));
1990   if (mode == VOIDmode)
1991     mode = GET_MODE (XEXP (condition, 1));
1992   /* The constant comparisons should be folded.  */
1993   if (mode == VOIDmode)
1994     abort ();
1995
1996   /* We only handle integers or pointers.  */
1997   if (GET_MODE_CLASS (mode) != MODE_INT
1998       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1999     goto fail;
2000
2001   op0 = XEXP (condition, 0);
2002   def_insn = iv_get_reaching_def (insn, op0);
2003   if (!iv_analyze (def_insn, op0, &iv0))
2004     goto fail;
2005   if (iv0.extend_mode == VOIDmode)
2006     iv0.mode = iv0.extend_mode = mode;
2007
2008   op1 = XEXP (condition, 1);
2009   def_insn = iv_get_reaching_def (insn, op1);
2010   if (!iv_analyze (def_insn, op1, &iv1))
2011     goto fail;
2012   if (iv1.extend_mode == VOIDmode)
2013     iv1.mode = iv1.extend_mode = mode;
2014
2015   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2016       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2017     goto fail;
2018
2019   /* Check condition and normalize it.  */
2020
2021   switch (cond)
2022     {
2023       case GE:
2024       case GT:
2025       case GEU:
2026       case GTU:
2027         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2028         cond = swap_condition (cond);
2029         break;
2030       case NE:
2031       case LE:
2032       case LEU:
2033       case LT:
2034       case LTU:
2035         break;
2036       default:
2037         goto fail;
2038     }
2039
2040   /* Handle extends.  This is relatively nontrivial, so we only try in some
2041      easy cases, when we can canonicalize the ivs (possibly by adding some
2042      assumptions) to shape subreg (base + i * step).  This function also fills
2043      in desc->mode and desc->signed_p.  */
2044
2045   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2046     goto fail;
2047
2048   comp_mode = iv0.extend_mode;
2049   mode = iv0.mode;
2050   size = GET_MODE_BITSIZE (mode);
2051   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2052   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2053   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2054
2055   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2056     goto fail;
2057
2058   /* We can take care of the case of two induction variables chasing each other
2059      if the test is NE. I have never seen a loop using it, but still it is
2060      cool.  */
2061   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2062     {
2063       if (cond != NE)
2064         goto fail;
2065
2066       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2067       iv1.step = const0_rtx;
2068     }
2069
2070   /* This is either infinite loop or the one that ends immediately, depending
2071      on initial values.  Unswitching should remove this kind of conditions.  */
2072   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2073     goto fail;
2074
2075   /* Ignore loops of while (i-- < 10) type.  */
2076   if (cond != NE
2077       && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
2078     goto fail;
2079
2080   /* Some more condition normalization.  We must record some assumptions
2081      due to overflows.  */
2082   switch (cond)
2083     {
2084       case LT:
2085       case LTU:
2086         /* We want to take care only of non-sharp relationals; this is easy,
2087            as in cases the overflow would make the transformation unsafe
2088            the loop does not roll.  Seemingly it would make more sense to want
2089            to take care of sharp relationals instead, as NE is more similar to
2090            them, but the problem is that here the transformation would be more
2091            difficult due to possibly infinite loops.  */
2092         if (iv0.step == const0_rtx)
2093           {
2094             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2095             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2096                                                   mode_mmax);
2097             if (assumption == const_true_rtx)
2098               goto zero_iter;
2099             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2100                                             iv0.base, const1_rtx);
2101           }
2102         else
2103           {
2104             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2105             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2106                                                   mode_mmin);
2107             if (assumption == const_true_rtx)
2108               goto zero_iter;
2109             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2110                                             iv1.base, constm1_rtx);
2111           }
2112
2113         if (assumption != const0_rtx)
2114           desc->noloop_assumptions =
2115                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2116         cond = (cond == LT) ? LE : LEU;
2117
2118         /* It will be useful to be able to tell the difference once more in
2119            LE -> NE reduction.  */
2120         was_sharp = true;
2121         break;
2122       default: ;
2123     }
2124
2125   /* Take care of trivially infinite loops.  */
2126   if (cond != NE)
2127     {
2128       if (iv0.step == const0_rtx)
2129         {
2130           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2131           if (rtx_equal_p (tmp, mode_mmin))
2132             {
2133               desc->infinite =
2134                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2135               return;
2136             }
2137         }
2138       else
2139         {
2140           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2141           if (rtx_equal_p (tmp, mode_mmax))
2142             {
2143               desc->infinite =
2144                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2145               return;
2146             }
2147         }
2148     }
2149
2150   /* If we can we want to take care of NE conditions instead of size
2151      comparisons, as they are much more friendly (most importantly
2152      this takes care of special handling of loops with step 1).  We can
2153      do it if we first check that upper bound is greater or equal to
2154      lower bound, their difference is constant c modulo step and that
2155      there is not an overflow.  */
2156   if (cond != NE)
2157     {
2158       if (iv0.step == const0_rtx)
2159         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2160       else
2161         step = iv0.step;
2162       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2163       delta = lowpart_subreg (mode, delta, comp_mode);
2164       delta = simplify_gen_binary (UMOD, mode, delta, step);
2165       may_xform = const0_rtx;
2166       may_not_xform = const_true_rtx;
2167
2168       if (GET_CODE (delta) == CONST_INT)
2169         {
2170           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2171             {
2172               /* A special case.  We have transformed condition of type
2173                  for (i = 0; i < 4; i += 4)
2174                  into
2175                  for (i = 0; i <= 3; i += 4)
2176                  obviously if the test for overflow during that transformation
2177                  passed, we cannot overflow here.  Most importantly any
2178                  loop with sharp end condition and step 1 falls into this
2179                  category, so handling this case specially is definitely
2180                  worth the troubles.  */
2181               may_xform = const_true_rtx;
2182             }
2183           else if (iv0.step == const0_rtx)
2184             {
2185               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2186               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2187               bound = lowpart_subreg (mode, bound, comp_mode);
2188               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2189               may_xform = simplify_gen_relational (cond, SImode, mode,
2190                                                    bound, tmp);
2191               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2192                                                        SImode, mode,
2193                                                        bound, tmp);
2194             }
2195           else
2196             {
2197               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2198               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2199               bound = lowpart_subreg (mode, bound, comp_mode);
2200               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2201               may_xform = simplify_gen_relational (cond, SImode, mode,
2202                                                    tmp, bound);
2203               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2204                                                        SImode, mode,
2205                                                        tmp, bound);
2206             }
2207         }
2208
2209       if (may_xform != const0_rtx)
2210         {
2211           /* We perform the transformation always provided that it is not
2212              completely senseless.  This is OK, as we would need this assumption
2213              to determine the number of iterations anyway.  */
2214           if (may_xform != const_true_rtx)
2215             {
2216               /* If the step is a power of two and the final value we have
2217                  computed overflows, the cycle is infinite.  Otherwise it
2218                  is nontrivial to compute the number of iterations.  */
2219               s = INTVAL (step);
2220               if ((s & (s - 1)) == 0)
2221                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2222                                                   desc->infinite);
2223               else
2224                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2225                                                      desc->assumptions);
2226             }
2227
2228           /* We are going to lose some information about upper bound on
2229              number of iterations in this step, so record the information
2230              here.  */
2231           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2232           if (GET_CODE (iv1.base) == CONST_INT)
2233             up = INTVAL (iv1.base);
2234           else
2235             up = INTVAL (mode_mmax) - inc;
2236           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2237                          ? iv0.base
2238                          : mode_mmin);
2239           desc->niter_max = (up - down) / inc + 1;
2240
2241           if (iv0.step == const0_rtx)
2242             {
2243               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2244               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2245             }
2246           else
2247             {
2248               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2249               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2250             }
2251
2252           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2253           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2254           assumption = simplify_gen_relational (reverse_condition (cond),
2255                                                 SImode, mode, tmp0, tmp1);
2256           if (assumption == const_true_rtx)
2257             goto zero_iter;
2258           else if (assumption != const0_rtx)
2259             desc->noloop_assumptions =
2260                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2261           cond = NE;
2262         }
2263     }
2264
2265   /* Count the number of iterations.  */
2266   if (cond == NE)
2267     {
2268       /* Everything we do here is just arithmetics modulo size of mode.  This
2269          makes us able to do more involved computations of number of iterations
2270          than in other cases.  First transform the condition into shape
2271          s * i <> c, with s positive.  */
2272       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2273       iv0.base = const0_rtx;
2274       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2275       iv1.step = const0_rtx;
2276       if (INTVAL (iv0.step) < 0)
2277         {
2278           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2279           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2280         }
2281       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2282
2283       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2284          is infinite.  Otherwise, the number of iterations is
2285          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2286       s = INTVAL (iv0.step); d = 1;
2287       while (s % 2 != 1)
2288         {
2289           s /= 2;
2290           d *= 2;
2291           size--;
2292         }
2293       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2294
2295       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2296       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2297       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2298       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2299
2300       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2301       inv = inverse (s, size);
2302       inv = trunc_int_for_mode (inv, mode);
2303       tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
2304       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2305     }
2306   else
2307     {
2308       if (iv1.step == const0_rtx)
2309         /* Condition in shape a + s * i <= b
2310            We must know that b + s does not overflow and a <= b + s and then we
2311            can compute number of iterations as (b + s - a) / s.  (It might
2312            seem that we in fact could be more clever about testing the b + s
2313            overflow condition using some information about b - a mod s,
2314            but it was already taken into account during LE -> NE transform).  */
2315         {
2316           step = iv0.step;
2317           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2318           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2319
2320           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2321                                        lowpart_subreg (mode, step, comp_mode));
2322           assumption = simplify_gen_relational (cond, SImode, mode,
2323                                                 tmp1, bound);
2324           desc->assumptions =
2325                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2326
2327           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2328           tmp = lowpart_subreg (mode, tmp, comp_mode);
2329           assumption = simplify_gen_relational (reverse_condition (cond),
2330                                                 SImode, mode, tmp0, tmp);
2331
2332           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2333           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2334         }
2335       else
2336         {
2337           /* Condition in shape a <= b - s * i
2338              We must know that a - s does not overflow and a - s <= b and then
2339              we can again compute number of iterations as (b - (a - s)) / s.  */
2340           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2341           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2342           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2343
2344           bound = simplify_gen_binary (MINUS, mode, mode_mmin,
2345                                        lowpart_subreg (mode, step, comp_mode));
2346           assumption = simplify_gen_relational (cond, SImode, mode,
2347                                                 bound, tmp0);
2348           desc->assumptions =
2349                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2350
2351           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2352           tmp = lowpart_subreg (mode, tmp, comp_mode);
2353           assumption = simplify_gen_relational (reverse_condition (cond),
2354                                                 SImode, mode,
2355                                                 tmp, tmp1);
2356           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2357           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2358         }
2359       if (assumption == const_true_rtx)
2360         goto zero_iter;
2361       else if (assumption != const0_rtx)
2362         desc->noloop_assumptions =
2363                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2364       delta = simplify_gen_binary (UDIV, mode, delta, step);
2365       desc->niter_expr = delta;
2366     }
2367
2368   old_niter = desc->niter_expr;
2369
2370   simplify_using_initial_values (loop, AND, &desc->assumptions);
2371   if (desc->assumptions
2372       && XEXP (desc->assumptions, 0) == const0_rtx)
2373     goto fail;
2374   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2375   simplify_using_initial_values (loop, IOR, &desc->infinite);
2376   simplify_using_initial_values (loop, NIL, &desc->niter_expr);
2377
2378   /* Rerun the simplification.  Consider code (created by copying loop headers)
2379
2380      i = 0;
2381
2382      if (0 < n)
2383        {
2384          do
2385            {
2386              i++;
2387            } while (i < n);
2388        }
2389
2390     The first pass determines that i = 0, the second pass uses it to eliminate
2391     noloop assumption.  */
2392
2393   simplify_using_initial_values (loop, AND, &desc->assumptions);
2394   if (desc->assumptions
2395       && XEXP (desc->assumptions, 0) == const0_rtx)
2396     goto fail;
2397   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2398   simplify_using_initial_values (loop, IOR, &desc->infinite);
2399   simplify_using_initial_values (loop, NIL, &desc->niter_expr);
2400
2401   if (desc->noloop_assumptions
2402       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2403     goto zero_iter;
2404
2405   if (GET_CODE (desc->niter_expr) == CONST_INT)
2406     {
2407       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2408
2409       desc->const_iter = true;
2410       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2411     }
2412   else
2413     {
2414       if (!desc->niter_max)
2415         desc->niter_max = determine_max_iter (desc);
2416
2417       /* simplify_using_initial_values does a copy propagation on the registers
2418          in the expression for the number of iterations.  This prolongs life
2419          ranges of registers and increases register pressure, and usually
2420          brings no gain (and if it happens to do, the cse pass will take care
2421          of it anyway).  So prevent this behavior, unless it enabled us to
2422          derive that the number of iterations is a constant.  */
2423       desc->niter_expr = old_niter;
2424     }
2425
2426   return;
2427
2428 fail:
2429   desc->simple_p = false;
2430   return;
2431
2432 zero_iter:
2433   desc->const_iter = true;
2434   desc->niter = 0;
2435   desc->niter_max = 0;
2436   desc->niter_expr = const0_rtx;
2437   return;
2438 }
2439
2440 /* Checks whether E is a simple exit from LOOP and stores its description
2441    into DESC.  */
2442
2443 static void
2444 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2445 {
2446   basic_block exit_bb;
2447   rtx condition, at;
2448   edge ei;
2449
2450   exit_bb = e->src;
2451   desc->simple_p = false;
2452
2453   /* It must belong directly to the loop.  */
2454   if (exit_bb->loop_father != loop)
2455     return;
2456
2457   /* It must be tested (at least) once during any iteration.  */
2458   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2459     return;
2460
2461   /* It must end in a simple conditional jump.  */
2462   if (!any_condjump_p (BB_END (exit_bb)))
2463     return;
2464
2465   ei = exit_bb->succ;
2466   if (ei == e)
2467     ei = ei->succ_next;
2468
2469   desc->out_edge = e;
2470   desc->in_edge = ei;
2471
2472   /* Test whether the condition is suitable.  */
2473   if (!(condition = get_condition (BB_END (ei->src), &at, false, false)))
2474     return;
2475
2476   if (ei->flags & EDGE_FALLTHRU)
2477     {
2478       condition = reversed_condition (condition);
2479       if (!condition)
2480         return;
2481     }
2482
2483   /* Check that we are able to determine number of iterations and fill
2484      in information about it.  */
2485   iv_number_of_iterations (loop, at, condition, desc);
2486 }
2487
2488 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2489
2490 void
2491 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2492 {
2493   unsigned i;
2494   basic_block *body;
2495   edge e;
2496   struct niter_desc act;
2497   bool any = false;
2498
2499   desc->simple_p = false;
2500   body = get_loop_body (loop);
2501
2502   for (i = 0; i < loop->num_nodes; i++)
2503     {
2504       for (e = body[i]->succ; e; e = e->succ_next)
2505         {
2506           if (flow_bb_inside_loop_p (loop, e->dest))
2507             continue;
2508
2509           check_simple_exit (loop, e, &act);
2510           if (!act.simple_p)
2511             continue;
2512
2513           /* Prefer constant iterations; the less the better.  */
2514           if (!any)
2515             any = true;
2516           else if (!act.const_iter
2517                    || (desc->const_iter && act.niter >= desc->niter))
2518             continue;
2519           *desc = act;
2520         }
2521     }
2522
2523   if (dump_file)
2524     {
2525       if (desc->simple_p)
2526         {
2527           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2528           fprintf (dump_file, "  simple exit %d -> %d\n",
2529                    desc->out_edge->src->index,
2530                    desc->out_edge->dest->index);
2531           if (desc->assumptions)
2532             {
2533               fprintf (dump_file, "  assumptions: ");
2534               print_rtl (dump_file, desc->assumptions);
2535               fprintf (dump_file, "\n");
2536             }
2537           if (desc->noloop_assumptions)
2538             {
2539               fprintf (dump_file, "  does not roll if: ");
2540               print_rtl (dump_file, desc->noloop_assumptions);
2541               fprintf (dump_file, "\n");
2542             }
2543           if (desc->infinite)
2544             {
2545               fprintf (dump_file, "  infinite if: ");
2546               print_rtl (dump_file, desc->infinite);
2547               fprintf (dump_file, "\n");
2548             }
2549
2550           fprintf (dump_file, "  number of iterations: ");
2551           print_rtl (dump_file, desc->niter_expr);
2552           fprintf (dump_file, "\n");
2553
2554           fprintf (dump_file, "  upper bound: ");
2555           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2556           fprintf (dump_file, "\n");
2557         }
2558       else
2559         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2560     }
2561
2562   free (body);
2563 }
2564
2565 /* Creates a simple loop description of LOOP if it was not computed
2566    already.  */
2567
2568 struct niter_desc *
2569 get_simple_loop_desc (struct loop *loop)
2570 {
2571   struct niter_desc *desc = simple_loop_desc (loop);
2572
2573   if (desc)
2574     return desc;
2575
2576   desc = xmalloc (sizeof (struct niter_desc));
2577   iv_analysis_loop_init (loop);
2578   find_simple_exit (loop, desc);
2579   loop->aux = desc;
2580
2581   return desc;
2582 }
2583
2584 /* Releases simple loop description for LOOP.  */
2585
2586 void
2587 free_simple_loop_desc (struct loop *loop)
2588 {
2589   struct niter_desc *desc = simple_loop_desc (loop);
2590
2591   if (!desc)
2592     return;
2593
2594   free (desc);
2595   loop->aux = NULL;
2596 }