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