gcc/loop-iv.c

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