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 (GET_CODE (insn) == CALL_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
1971   /* The meaning of these assumptions is this:
1972      if !assumptions
1973        then the rest of information does not have to be valid
1974      if noloop_assumptions then the loop does not roll
1975      if infinite then this exit is never used */
1976
1977   desc->assumptions = NULL_RTX;
1978   desc->noloop_assumptions = NULL_RTX;
1979   desc->infinite = NULL_RTX;
1980   desc->simple_p = true;
1981
1982   desc->const_iter = false;
1983   desc->niter_expr = NULL_RTX;
1984   desc->niter_max = 0;
1985
1986   cond = GET_CODE (condition);
1987   if (!COMPARISON_P (condition))
1988     abort ();
1989
1990   mode = GET_MODE (XEXP (condition, 0));
1991   if (mode == VOIDmode)
1992     mode = GET_MODE (XEXP (condition, 1));
1993   /* The constant comparisons should be folded.  */
1994   if (mode == VOIDmode)
1995     abort ();
1996
1997   /* We only handle integers or pointers.  */
1998   if (GET_MODE_CLASS (mode) != MODE_INT
1999       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
2000     goto fail;
2001
2002   op0 = XEXP (condition, 0);
2003   def_insn = iv_get_reaching_def (insn, op0);
2004   if (!iv_analyze (def_insn, op0, &iv0))
2005     goto fail;
2006   if (iv0.extend_mode == VOIDmode)
2007     iv0.mode = iv0.extend_mode = mode;
2008
2009   op1 = XEXP (condition, 1);
2010   def_insn = iv_get_reaching_def (insn, op1);
2011   if (!iv_analyze (def_insn, op1, &iv1))
2012     goto fail;
2013   if (iv1.extend_mode == VOIDmode)
2014     iv1.mode = iv1.extend_mode = mode;
2015
2016   if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
2017       || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
2018     goto fail;
2019
2020   /* Check condition and normalize it.  */
2021
2022   switch (cond)
2023     {
2024       case GE:
2025       case GT:
2026       case GEU:
2027       case GTU:
2028         tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
2029         cond = swap_condition (cond);
2030         break;
2031       case NE:
2032       case LE:
2033       case LEU:
2034       case LT:
2035       case LTU:
2036         break;
2037       default:
2038         goto fail;
2039     }
2040
2041   /* Handle extends.  This is relatively nontrivial, so we only try in some
2042      easy cases, when we can canonicalize the ivs (possibly by adding some
2043      assumptions) to shape subreg (base + i * step).  This function also fills
2044      in desc->mode and desc->signed_p.  */
2045
2046   if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
2047     goto fail;
2048
2049   comp_mode = iv0.extend_mode;
2050   mode = iv0.mode;
2051   size = GET_MODE_BITSIZE (mode);
2052   get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
2053   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
2054   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
2055
2056   if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
2057     goto fail;
2058
2059   /* We can take care of the case of two induction variables chasing each other
2060      if the test is NE. I have never seen a loop using it, but still it is
2061      cool.  */
2062   if (iv0.step != const0_rtx && iv1.step != const0_rtx)
2063     {
2064       if (cond != NE)
2065         goto fail;
2066
2067       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2068       iv1.step = const0_rtx;
2069     }
2070
2071   /* This is either infinite loop or the one that ends immediately, depending
2072      on initial values.  Unswitching should remove this kind of conditions.  */
2073   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
2074     goto fail;
2075
2076   /* Ignore loops of while (i-- < 10) type.  */
2077   if (cond != NE
2078       && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
2079     goto fail;
2080
2081   /* Some more condition normalization.  We must record some assumptions
2082      due to overflows.  */
2083   switch (cond)
2084     {
2085       case LT:
2086       case LTU:
2087         /* We want to take care only of non-sharp relationals; this is easy,
2088            as in cases the overflow would make the transformation unsafe
2089            the loop does not roll.  Seemingly it would make more sense to want
2090            to take care of sharp relationals instead, as NE is more similar to
2091            them, but the problem is that here the transformation would be more
2092            difficult due to possibly infinite loops.  */
2093         if (iv0.step == const0_rtx)
2094           {
2095             tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2096             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2097                                                   mode_mmax);
2098             if (assumption == const_true_rtx)
2099               goto zero_iter;
2100             iv0.base = simplify_gen_binary (PLUS, comp_mode,
2101                                             iv0.base, const1_rtx);
2102           }
2103         else
2104           {
2105             tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2106             assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
2107                                                   mode_mmin);
2108             if (assumption == const_true_rtx)
2109               goto zero_iter;
2110             iv1.base = simplify_gen_binary (PLUS, comp_mode,
2111                                             iv1.base, constm1_rtx);
2112           }
2113
2114         if (assumption != const0_rtx)
2115           desc->noloop_assumptions =
2116                   alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2117         cond = (cond == LT) ? LE : LEU;
2118
2119         /* It will be useful to be able to tell the difference once more in
2120            LE -> NE reduction.  */
2121         was_sharp = true;
2122         break;
2123       default: ;
2124     }
2125
2126   /* Take care of trivially infinite loops.  */
2127   if (cond != NE)
2128     {
2129       if (iv0.step == const0_rtx)
2130         {
2131           tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2132           if (rtx_equal_p (tmp, mode_mmin))
2133             {
2134               desc->infinite =
2135                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2136               return;
2137             }
2138         }
2139       else
2140         {
2141           tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2142           if (rtx_equal_p (tmp, mode_mmax))
2143             {
2144               desc->infinite =
2145                       alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
2146               return;
2147             }
2148         }
2149     }
2150
2151   /* If we can we want to take care of NE conditions instead of size
2152      comparisons, as they are much more friendly (most importantly
2153      this takes care of special handling of loops with step 1).  We can
2154      do it if we first check that upper bound is greater or equal to
2155      lower bound, their difference is constant c modulo step and that
2156      there is not an overflow.  */
2157   if (cond != NE)
2158     {
2159       if (iv0.step == const0_rtx)
2160         step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
2161       else
2162         step = iv0.step;
2163       delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2164       delta = lowpart_subreg (mode, delta, comp_mode);
2165       delta = simplify_gen_binary (UMOD, mode, delta, step);
2166       may_xform = const0_rtx;
2167       may_not_xform = const_true_rtx;
2168
2169       if (GET_CODE (delta) == CONST_INT)
2170         {
2171           if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
2172             {
2173               /* A special case.  We have transformed condition of type
2174                  for (i = 0; i < 4; i += 4)
2175                  into
2176                  for (i = 0; i <= 3; i += 4)
2177                  obviously if the test for overflow during that transformation
2178                  passed, we cannot overflow here.  Most importantly any
2179                  loop with sharp end condition and step 1 falls into this
2180                  category, so handling this case specially is definitely
2181                  worth the troubles.  */
2182               may_xform = const_true_rtx;
2183             }
2184           else if (iv0.step == const0_rtx)
2185             {
2186               bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
2187               bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
2188               bound = lowpart_subreg (mode, bound, comp_mode);
2189               tmp = lowpart_subreg (mode, iv0.base, comp_mode);
2190               may_xform = simplify_gen_relational (cond, SImode, mode,
2191                                                    bound, tmp);
2192               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2193                                                        SImode, mode,
2194                                                        bound, tmp);
2195             }
2196           else
2197             {
2198               bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
2199               bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
2200               bound = lowpart_subreg (mode, bound, comp_mode);
2201               tmp = lowpart_subreg (mode, iv1.base, comp_mode);
2202               may_xform = simplify_gen_relational (cond, SImode, mode,
2203                                                    tmp, bound);
2204               may_not_xform = simplify_gen_relational (reverse_condition (cond),
2205                                                        SImode, mode,
2206                                                        tmp, bound);
2207             }
2208         }
2209
2210       if (may_xform != const0_rtx)
2211         {
2212           /* We perform the transformation always provided that it is not
2213              completely senseless.  This is OK, as we would need this assumption
2214              to determine the number of iterations anyway.  */
2215           if (may_xform != const_true_rtx)
2216             {
2217               /* If the step is a power of two and the final value we have
2218                  computed overflows, the cycle is infinite.  Otherwise it
2219                  is nontrivial to compute the number of iterations.  */
2220               s = INTVAL (step);
2221               if ((s & (s - 1)) == 0)
2222                 desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
2223                                                   desc->infinite);
2224               else
2225                 desc->assumptions = alloc_EXPR_LIST (0, may_xform,
2226                                                      desc->assumptions);
2227             }
2228
2229           /* We are going to lose some information about upper bound on
2230              number of iterations in this step, so record the information
2231              here.  */
2232           inc = INTVAL (iv0.step) - INTVAL (iv1.step);
2233           if (GET_CODE (iv1.base) == CONST_INT)
2234             up = INTVAL (iv1.base);
2235           else
2236             up = INTVAL (mode_mmax) - inc;
2237           down = INTVAL (GET_CODE (iv0.base) == CONST_INT
2238                          ? iv0.base
2239                          : mode_mmin);
2240           desc->niter_max = (up - down) / inc + 1;
2241
2242           if (iv0.step == const0_rtx)
2243             {
2244               iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
2245               iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
2246             }
2247           else
2248             {
2249               iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
2250               iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
2251             }
2252
2253           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2254           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2255           assumption = simplify_gen_relational (reverse_condition (cond),
2256                                                 SImode, mode, tmp0, tmp1);
2257           if (assumption == const_true_rtx)
2258             goto zero_iter;
2259           else if (assumption != const0_rtx)
2260             desc->noloop_assumptions =
2261                     alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2262           cond = NE;
2263         }
2264     }
2265
2266   /* Count the number of iterations.  */
2267   if (cond == NE)
2268     {
2269       /* Everything we do here is just arithmetics modulo size of mode.  This
2270          makes us able to do more involved computations of number of iterations
2271          than in other cases.  First transform the condition into shape
2272          s * i <> c, with s positive.  */
2273       iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
2274       iv0.base = const0_rtx;
2275       iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
2276       iv1.step = const0_rtx;
2277       if (INTVAL (iv0.step) < 0)
2278         {
2279           iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
2280           iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
2281         }
2282       iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
2283
2284       /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
2285          is infinite.  Otherwise, the number of iterations is
2286          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
2287       s = INTVAL (iv0.step); d = 1;
2288       while (s % 2 != 1)
2289         {
2290           s /= 2;
2291           d *= 2;
2292           size--;
2293         }
2294       bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
2295
2296       tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2297       tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
2298       assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
2299       desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
2300
2301       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
2302       inv = inverse (s, size);
2303       inv = trunc_int_for_mode (inv, mode);
2304       tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
2305       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
2306     }
2307   else
2308     {
2309       if (iv1.step == const0_rtx)
2310         /* Condition in shape a + s * i <= b
2311            We must know that b + s does not overflow and a <= b + s and then we
2312            can compute number of iterations as (b + s - a) / s.  (It might
2313            seem that we in fact could be more clever about testing the b + s
2314            overflow condition using some information about b - a mod s,
2315            but it was already taken into account during LE -> NE transform).  */
2316         {
2317           step = iv0.step;
2318           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2319           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2320
2321           bound = simplify_gen_binary (MINUS, mode, mode_mmax,
2322                                        lowpart_subreg (mode, step, comp_mode));
2323           assumption = simplify_gen_relational (cond, SImode, mode,
2324                                                 tmp1, bound);
2325           desc->assumptions =
2326                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2327
2328           tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
2329           tmp = lowpart_subreg (mode, tmp, comp_mode);
2330           assumption = simplify_gen_relational (reverse_condition (cond),
2331                                                 SImode, mode, tmp0, tmp);
2332
2333           delta = simplify_gen_binary (PLUS, mode, tmp1, step);
2334           delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
2335         }
2336       else
2337         {
2338           /* Condition in shape a <= b - s * i
2339              We must know that a - s does not overflow and a - s <= b and then
2340              we can again compute number of iterations as (b - (a - s)) / s.  */
2341           step = simplify_gen_unary (NEG, mode, iv1.step, mode);
2342           tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
2343           tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
2344
2345           bound = simplify_gen_binary (MINUS, mode, mode_mmin,
2346                                        lowpart_subreg (mode, step, comp_mode));
2347           assumption = simplify_gen_relational (cond, SImode, mode,
2348                                                 bound, tmp0);
2349           desc->assumptions =
2350                   alloc_EXPR_LIST (0, assumption, desc->assumptions);
2351
2352           tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
2353           tmp = lowpart_subreg (mode, tmp, comp_mode);
2354           assumption = simplify_gen_relational (reverse_condition (cond),
2355                                                 SImode, mode,
2356                                                 tmp, tmp1);
2357           delta = simplify_gen_binary (MINUS, mode, tmp0, step);
2358           delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
2359         }
2360       if (assumption == const_true_rtx)
2361         goto zero_iter;
2362       else if (assumption != const0_rtx)
2363         desc->noloop_assumptions =
2364                 alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
2365       delta = simplify_gen_binary (UDIV, mode, delta, step);
2366       desc->niter_expr = delta;
2367     }
2368
2369   simplify_using_initial_values (loop, AND, &desc->assumptions);
2370   if (desc->assumptions
2371       && XEXP (desc->assumptions, 0) == const0_rtx)
2372     goto fail;
2373   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2374   simplify_using_initial_values (loop, IOR, &desc->infinite);
2375   simplify_using_initial_values (loop, NIL, &desc->niter_expr);
2376
2377   /* Rerun the simplification.  Consider code (created by copying loop headers)
2378
2379      i = 0;
2380
2381      if (0 < n)
2382        {
2383          do
2384            {
2385              i++;
2386            } while (i < n);
2387        }
2388
2389     The first pass determines that i = 0, the second pass uses it to eliminate
2390     noloop assumption.  */
2391
2392   simplify_using_initial_values (loop, AND, &desc->assumptions);
2393   if (desc->assumptions
2394       && XEXP (desc->assumptions, 0) == const0_rtx)
2395     goto fail;
2396   simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
2397   simplify_using_initial_values (loop, IOR, &desc->infinite);
2398   simplify_using_initial_values (loop, NIL, &desc->niter_expr);
2399
2400   if (desc->noloop_assumptions
2401       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
2402     goto zero_iter;
2403
2404   if (GET_CODE (desc->niter_expr) == CONST_INT)
2405     {
2406       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
2407
2408       desc->const_iter = true;
2409       desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
2410     }
2411   else if (!desc->niter_max)
2412     desc->niter_max = determine_max_iter (desc);
2413
2414   return;
2415
2416 fail:
2417   desc->simple_p = false;
2418   return;
2419
2420 zero_iter:
2421   desc->const_iter = true;
2422   desc->niter = 0;
2423   desc->niter_max = 0;
2424   desc->niter_expr = const0_rtx;
2425   return;
2426 }
2427
2428 /* Checks whether E is a simple exit from LOOP and stores its description
2429    into DESC.  */
2430
2431 static void
2432 check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
2433 {
2434   basic_block exit_bb;
2435   rtx condition, at;
2436   edge ei;
2437
2438   exit_bb = e->src;
2439   desc->simple_p = false;
2440
2441   /* It must belong directly to the loop.  */
2442   if (exit_bb->loop_father != loop)
2443     return;
2444
2445   /* It must be tested (at least) once during any iteration.  */
2446   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
2447     return;
2448
2449   /* It must end in a simple conditional jump.  */
2450   if (!any_condjump_p (BB_END (exit_bb)))
2451     return;
2452
2453   ei = exit_bb->succ;
2454   if (ei == e)
2455     ei = ei->succ_next;
2456
2457   desc->out_edge = e;
2458   desc->in_edge = ei;
2459
2460   /* Test whether the condition is suitable.  */
2461   if (!(condition = get_condition (BB_END (ei->src), &at, false)))
2462     return;
2463
2464   if (ei->flags & EDGE_FALLTHRU)
2465     {
2466       condition = reversed_condition (condition);
2467       if (!condition)
2468         return;
2469     }
2470
2471   /* Check that we are able to determine number of iterations and fill
2472      in information about it.  */
2473   iv_number_of_iterations (loop, at, condition, desc);
2474 }
2475
2476 /* Finds a simple exit of LOOP and stores its description into DESC.  */
2477
2478 void
2479 find_simple_exit (struct loop *loop, struct niter_desc *desc)
2480 {
2481   unsigned i;
2482   basic_block *body;
2483   edge e;
2484   struct niter_desc act;
2485   bool any = false;
2486
2487   desc->simple_p = false;
2488   body = get_loop_body (loop);
2489
2490   for (i = 0; i < loop->num_nodes; i++)
2491     {
2492       for (e = body[i]->succ; e; e = e->succ_next)
2493         {
2494           if (flow_bb_inside_loop_p (loop, e->dest))
2495             continue;
2496
2497           check_simple_exit (loop, e, &act);
2498           if (!act.simple_p)
2499             continue;
2500
2501           /* Prefer constant iterations; the less the better.  */
2502           if (!any)
2503             any = true;
2504           else if (!act.const_iter
2505                    || (desc->const_iter && act.niter >= desc->niter))
2506             continue;
2507           *desc = act;
2508         }
2509     }
2510
2511   if (dump_file)
2512     {
2513       if (desc->simple_p)
2514         {
2515           fprintf (dump_file, "Loop %d is simple:\n", loop->num);
2516           fprintf (dump_file, "  simple exit %d -> %d\n",
2517                    desc->out_edge->src->index,
2518                    desc->out_edge->dest->index);
2519           if (desc->assumptions)
2520             {
2521               fprintf (dump_file, "  assumptions: ");
2522               print_rtl (dump_file, desc->assumptions);
2523               fprintf (dump_file, "\n");
2524             }
2525           if (desc->noloop_assumptions)
2526             {
2527               fprintf (dump_file, "  does not roll if: ");
2528               print_rtl (dump_file, desc->noloop_assumptions);
2529               fprintf (dump_file, "\n");
2530             }
2531           if (desc->infinite)
2532             {
2533               fprintf (dump_file, "  infinite if: ");
2534               print_rtl (dump_file, desc->infinite);
2535               fprintf (dump_file, "\n");
2536             }
2537
2538           fprintf (dump_file, "  number of iterations: ");
2539           print_rtl (dump_file, desc->niter_expr);
2540           fprintf (dump_file, "\n");
2541
2542           fprintf (dump_file, "  upper bound: ");
2543           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
2544           fprintf (dump_file, "\n");
2545         }
2546       else
2547         fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
2548     }
2549
2550   free (body);
2551 }
2552
2553 /* Creates a simple loop description of LOOP if it was not computed
2554    already.  */
2555
2556 struct niter_desc *
2557 get_simple_loop_desc (struct loop *loop)
2558 {
2559   struct niter_desc *desc = simple_loop_desc (loop);
2560
2561   if (desc)
2562     return desc;
2563
2564   desc = xmalloc (sizeof (struct niter_desc));
2565   iv_analysis_loop_init (loop);
2566   find_simple_exit (loop, desc);
2567   loop->aux = desc;
2568
2569   return desc;
2570 }
2571
2572 /* Releases simple loop description for LOOP.  */
2573
2574 void
2575 free_simple_loop_desc (struct loop *loop)
2576 {
2577   struct niter_desc *desc = simple_loop_desc (loop);
2578
2579   if (!desc)
2580     return;
2581
2582   free (desc);
2583   loop->aux = NULL;
2584 }