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