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