gcc/loop-iv.c

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