contrib/gcc-5.0/gcc/loop-iv.c

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