contrib/gcc-3.4/gcc/cfgloopanal.c

   1 /* Natural loop analysis code for GNU compiler.
   2    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "expr.h"
  30 #include "output.h"
  31 /* Needed for doloop_condition_get().  */
  32 #include "loop.h"
  33
  34 struct unmark_altered_insn_data;
  35 static void unmark_altered (rtx, rtx, regset);
  36 static void blocks_invariant_registers (basic_block *, int, regset);
  37 static void unmark_altered_insn (rtx, rtx, struct unmark_altered_insn_data *);
  38 static void blocks_single_set_registers (basic_block *, int, rtx *);
  39 static int invariant_rtx_wrto_regs_p_helper (rtx *, regset);
  40 static bool invariant_rtx_wrto_regs_p (rtx, regset);
  41 static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
  42 static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
  43                                  bool *);
  44 static bool simple_loop_exit_p (struct loop *, edge, regset,
  45                                 rtx *, struct loop_desc *);
  46 static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
  47 static rtx variable_initial_values (edge, rtx, enum machine_mode);
  48 static bool simple_condition_p (struct loop *, rtx, regset,
  49                                 struct loop_desc *);
  50 static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
  51 static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
  52                                           int, rtx, enum machine_mode,
  53                                           enum machine_mode);
  54 static unsigned HOST_WIDEST_INT inverse (unsigned HOST_WIDEST_INT, int);
  55 static bool fits_in_mode_p (enum machine_mode mode, rtx expr);
  56
  57 /* Computes inverse to X modulo (1 << MOD).  */
  58 static unsigned HOST_WIDEST_INT
  59 inverse (unsigned HOST_WIDEST_INT x, int mod)
  60 {
  61   unsigned HOST_WIDEST_INT mask =
  62           ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
  63   unsigned HOST_WIDEST_INT rslt = 1;
  64   int i;
  65
  66   for (i = 0; i < mod - 1; i++)
  67     {
  68       rslt = (rslt * x) & mask;
  69       x = (x * x) & mask;
  70     }
  71
  72   return rslt;
  73 }
  74
  75 /* Checks whether BB is executed exactly once in each LOOP iteration.  */
  76 bool
  77 just_once_each_iteration_p (struct loop *loop, basic_block bb)
  78 {
  79   /* It must be executed at least once each iteration.  */
  80   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
  81     return false;
  82
  83   /* And just once.  */
  84   if (bb->loop_father != loop)
  85     return false;
  86
  87   /* But this was not enough.  We might have some irreducible loop here.  */
  88   if (bb->flags & BB_IRREDUCIBLE_LOOP)
  89     return false;
  90
  91   return true;
  92 }
  93
  94
  95 /* Unmarks modified registers; helper to blocks_invariant_registers.  */
  96 static void
  97 unmark_altered (rtx what, rtx by ATTRIBUTE_UNUSED, regset regs)
  98 {
  99   if (GET_CODE (what) == SUBREG)
 100     what = SUBREG_REG (what);
 101   if (!REG_P (what))
 102     return;
 103   CLEAR_REGNO_REG_SET (regs, REGNO (what));
 104 }
 105
 106 /* Marks registers that are invariant inside blocks BBS.  */
 107 static void
 108 blocks_invariant_registers (basic_block *bbs, int nbbs, regset regs)
 109 {
 110   rtx insn;
 111   int i;
 112
 113   for (i = 0; i < max_reg_num (); i++)
 114     SET_REGNO_REG_SET (regs, i);
 115   for (i = 0; i < nbbs; i++)
 116     for (insn = BB_HEAD (bbs[i]);
 117          insn != NEXT_INSN (BB_END (bbs[i]));
 118          insn = NEXT_INSN (insn))
 119       if (INSN_P (insn))
 120         note_stores (PATTERN (insn),
 121                      (void (*) (rtx, rtx, void *)) unmark_altered,
 122                      regs);
 123 }
 124
 125 /* Unmarks modified registers; helper to blocks_single_set_registers.  */
 126 struct unmark_altered_insn_data
 127 {
 128   rtx *regs;
 129   rtx insn;
 130 };
 131
 132 static void
 133 unmark_altered_insn (rtx what, rtx by ATTRIBUTE_UNUSED,
 134                      struct unmark_altered_insn_data *data)
 135 {
 136   int rn;
 137
 138   if (GET_CODE (what) == SUBREG)
 139     what = SUBREG_REG (what);
 140   if (!REG_P (what))
 141     return;
 142   rn = REGNO (what);
 143   if (data->regs[rn] == data->insn)
 144     return;
 145   data->regs[rn] = NULL;
 146 }
 147
 148 /* Marks registers that have just single simple set in BBS; the relevant
 149    insn is returned in REGS.  */
 150 static void
 151 blocks_single_set_registers (basic_block *bbs, int nbbs, rtx *regs)
 152 {
 153   rtx insn;
 154   int i;
 155   struct unmark_altered_insn_data data;
 156
 157   for (i = 0; i < max_reg_num (); i++)
 158     regs[i] = NULL;
 159
 160   for (i = 0; i < nbbs; i++)
 161     for (insn = BB_HEAD (bbs[i]);
 162          insn != NEXT_INSN (BB_END (bbs[i]));
 163          insn = NEXT_INSN (insn))
 164       {
 165         rtx set = single_set (insn);
 166
 167         if (!set && is_bct_cond (insn))
 168           set = get_var_set_from_bct(insn);
 169
 170         if (!set)
 171           continue;
 172         if (!REG_P (SET_DEST (set)))
 173           continue;
 174         regs[REGNO (SET_DEST (set))] = insn;
 175       }
 176
 177   data.regs = regs;
 178   for (i = 0; i < nbbs; i++)
 179     for (insn = BB_HEAD (bbs[i]);
 180          insn != NEXT_INSN (BB_END (bbs[i]));
 181          insn = NEXT_INSN (insn))
 182       {
 183         if (!INSN_P (insn))
 184           continue;
 185         data.insn = insn;
 186         note_stores (PATTERN (insn),
 187             (void (*) (rtx, rtx, void *)) unmark_altered_insn,
 188             &data);
 189       }
 190 }
 191
 192 /* Helper for invariant_rtx_wrto_regs_p.  */
 193 static int
 194 invariant_rtx_wrto_regs_p_helper (rtx *expr, regset invariant_regs)
 195 {
 196   switch (GET_CODE (*expr))
 197     {
 198     case CC0:
 199     case PC:
 200     case UNSPEC_VOLATILE:
 201       return 1;
 202
 203     case CONST_INT:
 204     case CONST_DOUBLE:
 205     case CONST:
 206     case SYMBOL_REF:
 207     case LABEL_REF:
 208       return 0;
 209
 210     case ASM_OPERANDS:
 211       return MEM_VOLATILE_P (*expr);
 212
 213     case MEM:
 214       /* If the memory is not constant, assume it is modified.  If it is
 215          constant, we still have to check the address.  */
 216       return !RTX_UNCHANGING_P (*expr);
 217
 218     case REG:
 219       return !REGNO_REG_SET_P (invariant_regs, REGNO (*expr));
 220
 221     default:
 222       return 0;
 223     }
 224 }
 225
 226 /* Checks that EXPR is invariant provided that INVARIANT_REGS are invariant.  */
 227 static bool
 228 invariant_rtx_wrto_regs_p (rtx expr, regset invariant_regs)
 229 {
 230   return !for_each_rtx (&expr, (rtx_function) invariant_rtx_wrto_regs_p_helper,
 231                         invariant_regs);
 232 }
 233
 234 /* Checks whether CONDITION is a simple comparison in that one of operands
 235    is register and the other one is invariant in the LOOP. Fills var, lim
 236    and cond fields in DESC.  */
 237 static bool
 238 simple_condition_p (struct loop *loop ATTRIBUTE_UNUSED, rtx condition,
 239                     regset invariant_regs, struct loop_desc *desc)
 240 {
 241   rtx op0, op1;
 242
 243   /* Check condition.  */
 244   switch (GET_CODE (condition))
 245     {
 246       case EQ:
 247       case NE:
 248       case LE:
 249       case LT:
 250       case GE:
 251       case GT:
 252       case GEU:
 253       case GTU:
 254       case LEU:
 255       case LTU:
 256         break;
 257       default:
 258         return false;
 259     }
 260
 261   /* Of integers or pointers.  */
 262   if (GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_INT
 263       && GET_MODE_CLASS (GET_MODE (XEXP (condition, 0))) != MODE_PARTIAL_INT)
 264     return false;
 265
 266   /* One of operands must be a simple register.  */
 267   op0 = XEXP (condition, 0);
 268   op1 = XEXP (condition, 1);
 269
 270   /* One of operands must be invariant.  */
 271   if (invariant_rtx_wrto_regs_p (op0, invariant_regs))
 272     {
 273       /* And the other one must be a register.  */
 274       if (!REG_P (op1))
 275         return false;
 276       desc->var = op1;
 277       desc->lim = op0;
 278
 279       desc->cond = swap_condition (GET_CODE (condition));
 280       if (desc->cond == UNKNOWN)
 281         return false;
 282       return true;
 283     }
 284
 285   /* Check the other operand.  */
 286   if (!invariant_rtx_wrto_regs_p (op1, invariant_regs))
 287     return false;
 288   if (!REG_P (op0))
 289     return false;
 290
 291   desc->var = op0;
 292   desc->lim = op1;
 293
 294   desc->cond = GET_CODE (condition);
 295
 296   return true;
 297 }
 298
 299 /* Checks whether DESC->var is incremented/decremented exactly once each
 300    iteration.  Fills in DESC->stride and returns block in that DESC->var is
 301    modified.  */
 302 static basic_block
 303 simple_increment (struct loop *loop, rtx *simple_increment_regs,
 304                   struct loop_desc *desc)
 305 {
 306   rtx mod_insn, mod_insn1, set, set_src, set_add;
 307   basic_block mod_bb, mod_bb1;
 308
 309   /* Find insn that modifies var.  */
 310   mod_insn = simple_increment_regs[REGNO (desc->var)];
 311   if (!mod_insn)
 312     return NULL;
 313   mod_bb = BLOCK_FOR_INSN (mod_insn);
 314
 315   /* Check that it is executed exactly once each iteration.  */
 316   if (!just_once_each_iteration_p (loop, mod_bb))
 317     return NULL;
 318
 319   /* mod_insn must be a simple increment/decrement.  */
 320   set = single_set (mod_insn);
 321
 322   if (!set && is_bct_cond (mod_insn))
 323     set = get_var_set_from_bct(mod_insn);
 324
 325   if (!set)
 326     abort ();
 327   if (!rtx_equal_p (SET_DEST (set), desc->var))
 328     abort ();
 329
 330   set_src = find_reg_equal_equiv_note (mod_insn);
 331   if (!set_src)
 332     set_src = SET_SRC (set);
 333
 334   /* Check for variables that iterate in narrower mode.  */
 335   if (GET_CODE (set_src) == SIGN_EXTEND
 336       || GET_CODE (set_src) == ZERO_EXTEND)
 337     {
 338       /* If we are sign extending variable that is then compared unsigned
 339          or vice versa, there is something weird happening.  */
 340       if (desc->cond != EQ
 341           && desc->cond != NE
 342           && ((desc->cond == LEU
 343                || desc->cond == LTU
 344                || desc->cond == GEU
 345                || desc->cond == GTU)
 346               ^ (GET_CODE (set_src) == ZERO_EXTEND)))
 347         return NULL;
 348
 349       if (GET_CODE (XEXP (set_src, 0)) != SUBREG
 350           || SUBREG_BYTE (XEXP (set_src, 0)) != 0
 351           || GET_MODE (SUBREG_REG (XEXP (set_src, 0))) != GET_MODE (desc->var))
 352         return NULL;
 353
 354       desc->inner_mode = GET_MODE (XEXP (set_src, 0));
 355       desc->extend = GET_CODE (set_src);
 356       set_src = SUBREG_REG (XEXP (set_src, 0));
 357
 358       if (GET_CODE (set_src) != REG)
 359         return NULL;
 360
 361       /* Find where the reg is set.  */
 362       mod_insn1 = simple_increment_regs[REGNO (set_src)];
 363       if (!mod_insn1)
 364         return NULL;
 365
 366       mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
 367       if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
 368         return NULL;
 369       if (mod_bb1 == mod_bb)
 370         {
 371           for (;
 372                mod_insn != PREV_INSN (BB_HEAD (mod_bb));
 373                mod_insn = PREV_INSN (mod_insn))
 374             if (mod_insn == mod_insn1)
 375               break;
 376
 377           if (mod_insn == PREV_INSN (BB_HEAD (mod_bb)))
 378             return NULL;
 379         }
 380
 381       /* Replace the source with the possible place of increment.  */
 382       set = single_set (mod_insn1);
 383       if (!set)
 384         abort ();
 385       if (!rtx_equal_p (SET_DEST (set), set_src))
 386         abort ();
 387
 388       set_src = find_reg_equal_equiv_note (mod_insn1);
 389       if (!set_src)
 390         set_src = SET_SRC (set);
 391     }
 392   else
 393     {
 394       desc->inner_mode = GET_MODE (desc->var);
 395       desc->extend = NIL;
 396     }
 397
 398   if (GET_CODE (set_src) != PLUS)
 399     return NULL;
 400   if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
 401     return NULL;
 402
 403   /* Set desc->stride.  */
 404   set_add = XEXP (set_src, 1);
 405   if (CONSTANT_P (set_add))
 406     desc->stride = set_add;
 407   else
 408     return NULL;
 409
 410   return mod_bb;
 411 }
 412
 413 /* Tries to find initial value of VAR in INSN.  This value must be invariant
 414    wrto INVARIANT_REGS.  If SET_INSN is not NULL, insn in that var is set is
 415    placed here.  INNER_MODE is mode in that induction variable VAR iterates.  */
 416 static rtx
 417 variable_initial_value (rtx insn, regset invariant_regs,
 418                         rtx var, rtx *set_insn, enum machine_mode inner_mode)
 419 {
 420   basic_block bb;
 421   rtx set;
 422   rtx ret = NULL;
 423
 424   /* Go back through cfg.  */
 425   bb = BLOCK_FOR_INSN (insn);
 426   while (1)
 427     {
 428       for (; insn != BB_HEAD (bb); insn = PREV_INSN (insn))
 429         {
 430           if (INSN_P (insn))
 431             note_stores (PATTERN (insn),
 432                 (void (*) (rtx, rtx, void *)) unmark_altered,
 433                 invariant_regs);
 434           if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
 435             break;
 436         }
 437
 438       if (insn != BB_HEAD (bb))
 439         {
 440           /* We found place where var is set.  */
 441           rtx set_dest;
 442           rtx val;
 443           rtx note;
 444
 445           set = single_set (insn);
 446           if (!set)
 447             return NULL;
 448           set_dest = SET_DEST (set);
 449           if (!rtx_equal_p (set_dest, var))
 450             return NULL;
 451
 452           note = find_reg_equal_equiv_note (insn);
 453           if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
 454             val = XEXP (note, 0);
 455           else
 456             val = SET_SRC (set);
 457
 458           /* If we know that the initial value is indeed in range of
 459              the inner mode, record the fact even in case the value itself
 460              is useless.  */
 461           if ((GET_CODE (val) == SIGN_EXTEND
 462                || GET_CODE (val) == ZERO_EXTEND)
 463               && GET_MODE (XEXP (val, 0)) == inner_mode)
 464             ret = gen_rtx_fmt_e (GET_CODE (val),
 465                                  GET_MODE (var),
 466                                  gen_rtx_fmt_ei (SUBREG,
 467                                                  inner_mode,
 468                                                  var, 0));
 469
 470           if (!invariant_rtx_wrto_regs_p (val, invariant_regs))
 471             return ret;
 472
 473           if (set_insn)
 474             *set_insn = insn;
 475           return val;
 476         }
 477
 478
 479       if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
 480         return NULL;
 481
 482       bb = bb->pred->src;
 483       insn = BB_END (bb);
 484     }
 485
 486   return NULL;
 487 }
 488
 489 /* Returns list of definitions of initial value of VAR at edge E.  INNER_MODE
 490    is mode in that induction variable VAR really iterates.  */
 491 static rtx
 492 variable_initial_values (edge e, rtx var, enum machine_mode inner_mode)
 493 {
 494   rtx set_insn, list;
 495   regset invariant_regs;
 496   regset_head invariant_regs_head;
 497   int i;
 498
 499   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
 500   for (i = 0; i < max_reg_num (); i++)
 501     SET_REGNO_REG_SET (invariant_regs, i);
 502
 503   list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
 504
 505   if (e->src == ENTRY_BLOCK_PTR)
 506     return list;
 507
 508   set_insn = BB_END (e->src);
 509   while (REG_P (var)
 510          && (var = variable_initial_value (set_insn, invariant_regs, var,
 511                                            &set_insn, inner_mode)))
 512     list = alloc_EXPR_LIST (0, copy_rtx (var), list);
 513
 514   FREE_REG_SET (invariant_regs);
 515   return list;
 516 }
 517
 518 /* Counts constant number of iterations of the loop described by DESC;
 519    returns false if impossible.  */
 520 static bool
 521 constant_iterations (struct loop_desc *desc, unsigned HOST_WIDE_INT *niter,
 522                      bool *may_be_zero)
 523 {
 524   rtx test, expr;
 525   rtx ainit, alim;
 526
 527   test = test_for_iteration (desc, 0);
 528   if (test == const0_rtx)
 529     {
 530       *niter = 0;
 531       *may_be_zero = false;
 532       return true;
 533     }
 534
 535   *may_be_zero = (test != const_true_rtx);
 536
 537   /* It would make a little sense to check every with every when we
 538      know that all but the first alternative are simply registers.  */
 539   for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
 540     {
 541       alim = XEXP (desc->lim_alts, 0);
 542       if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), alim)))
 543         continue;
 544       if (GET_CODE (expr) == CONST_INT)
 545         {
 546           *niter = INTVAL (expr);
 547           return true;
 548         }
 549     }
 550   for (alim = XEXP (desc->lim_alts, 1); alim; alim = XEXP (alim, 1))
 551     {
 552       ainit = XEXP (desc->var_alts, 0);
 553       if (!(expr = count_loop_iterations (desc, ainit, XEXP (alim, 0))))
 554         continue;
 555       if (GET_CODE (expr) == CONST_INT)
 556         {
 557           *niter = INTVAL (expr);
 558           return true;
 559         }
 560     }
 561
 562   return false;
 563 }
 564
 565 /* Attempts to determine a number of iterations of a "strange" loop.
 566    Its induction variable starts with value INIT, is compared by COND
 567    with LIM.  If POSTINCR, it is incremented after the test.  It is incremented
 568    by STRIDE each iteration, has mode MODE but iterates in INNER_MODE.
 569
 570    By "strange" we mean loops where induction variable increases in the wrong
 571    direction wrto comparison, i.e. for (i = 6; i > 5; i++).  */
 572 static rtx
 573 count_strange_loop_iterations (rtx init, rtx lim, enum rtx_code cond,
 574                                int postincr, rtx stride, enum machine_mode mode,
 575                                enum machine_mode inner_mode)
 576 {
 577   rtx rqmt, n_to_wrap, before_wrap, after_wrap;
 578   rtx mode_min, mode_max;
 579   int size;
 580
 581   /* This could be handled, but it is not important enough to lose time with
 582      it just now.  */
 583   if (mode != inner_mode)
 584     return NULL_RTX;
 585
 586   if (!postincr)
 587     init = simplify_gen_binary (PLUS, mode, init, stride);
 588
 589   /* If we are able to prove that we don't pass the first test, we are
 590      done.  */
 591   rqmt = simplify_relational_operation (cond, mode, init, lim);
 592   if (rqmt == const0_rtx)
 593     return const0_rtx;
 594
 595   /* And if we don't know we pass it, the things are too complicated for us.  */
 596   if (rqmt != const_true_rtx)
 597     return NULL_RTX;
 598
 599   switch (cond)
 600     {
 601     case GE:
 602     case GT:
 603     case LE:
 604     case LT:
 605       size = GET_MODE_BITSIZE (mode);
 606       mode_min = gen_int_mode (-((unsigned HOST_WIDEST_INT) 1 << (size - 1)),
 607                                mode);
 608       mode_max = gen_int_mode (((unsigned HOST_WIDEST_INT) 1 << (size - 1)) - 1,
 609                                mode);
 610
 611       break;
 612
 613     case GEU:
 614     case GTU:
 615     case LEU:
 616     case LTU:
 617     case EQ:
 618       mode_min = const0_rtx;
 619       mode_max = simplify_gen_binary (MINUS, mode, const0_rtx, const1_rtx);
 620       break;
 621
 622     default:
 623       abort ();
 624     }
 625
 626   switch (cond)
 627     {
 628     case EQ:
 629       /* This iterates once, as init == lim.  */
 630       return const1_rtx;
 631
 632       /* The behavior is undefined in signed cases.  Never mind, we still
 633          try to behave sanely.  */
 634     case GE:
 635     case GT:
 636     case GEU:
 637     case GTU:
 638       if (INTVAL (stride) <= 0)
 639         abort ();
 640       n_to_wrap = simplify_gen_binary (MINUS, mode, mode_max, copy_rtx (init));
 641       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
 642       before_wrap = simplify_gen_binary (MULT, mode,
 643                                          copy_rtx (n_to_wrap), stride);
 644       before_wrap = simplify_gen_binary (PLUS, mode,
 645                                          before_wrap, copy_rtx (init));
 646       after_wrap = simplify_gen_binary (PLUS, mode,
 647                                         before_wrap, stride);
 648       if (GET_CODE (after_wrap) != CONST_INT)
 649         {
 650           after_wrap = simplify_gen_binary (PLUS, mode, mode_min, stride);
 651           after_wrap = simplify_gen_binary (MINUS, mode, after_wrap, const1_rtx);
 652         }
 653       break;
 654
 655     case LE:
 656     case LT:
 657     case LEU:
 658     case LTU:
 659       if (INTVAL (stride) >= 0)
 660         abort ();
 661       stride = simplify_gen_unary (NEG, mode, stride, mode);
 662       n_to_wrap = simplify_gen_binary (MINUS, mode, copy_rtx (init), mode_min);
 663       n_to_wrap = simplify_gen_binary (UDIV, mode, n_to_wrap, stride);
 664       before_wrap = simplify_gen_binary (MULT, mode,
 665                                          copy_rtx (n_to_wrap), stride);
 666       before_wrap = simplify_gen_binary (MINUS, mode,
 667                                          copy_rtx (init), before_wrap);
 668       after_wrap = simplify_gen_binary (MINUS, mode,
 669                                         before_wrap, stride);
 670       if (GET_CODE (after_wrap) != CONST_INT)
 671         {
 672           after_wrap = simplify_gen_binary (MINUS, mode, mode_max, stride);
 673           after_wrap = simplify_gen_binary (PLUS, mode, after_wrap, const1_rtx);
 674         }
 675       break;
 676     default:
 677       abort ();
 678     }
 679
 680   /* If this is const_true_rtx and we did not take a conservative approximation
 681      of after_wrap above, we might iterate the calculation (but of course we
 682      would have to take care about infinite cases).  Ignore this for now.  */
 683   rqmt = simplify_relational_operation (cond, mode, after_wrap, lim);
 684   if (rqmt != const0_rtx)
 685     return NULL_RTX;
 686
 687   return simplify_gen_binary (PLUS, mode, n_to_wrap, const1_rtx);
 688 }
 689
 690 /* Checks whether value of EXPR fits into range of MODE.  */
 691 static bool
 692 fits_in_mode_p (enum machine_mode mode, rtx expr)
 693 {
 694   unsigned HOST_WIDEST_INT val;
 695   int n_bits = 0;
 696
 697   if (GET_CODE (expr) == CONST_INT)
 698     {
 699       for (val = INTVAL (expr); val; val >>= 1)
 700         n_bits++;
 701
 702       return n_bits <= GET_MODE_BITSIZE (mode);
 703     }
 704
 705   if (GET_CODE (expr) == SIGN_EXTEND
 706       || GET_CODE (expr) == ZERO_EXTEND)
 707     return GET_MODE (XEXP (expr, 0)) == mode;
 708
 709   return false;
 710 }
 711
 712 /* Return RTX expression representing number of iterations of loop as bounded
 713    by test described by DESC (in the case loop really has multiple exit
 714    edges, fewer iterations may happen in the practice).
 715
 716    Return NULL if it is unknown.  Additionally the value may be invalid for
 717    paradoxical loop (lets define paradoxical loops as loops whose test is
 718    failing at -1th iteration, for instance "for (i=5;i<1;i++);").
 719
 720    These cases needs to be either cared by copying the loop test in the front
 721    of loop or keeping the test in first iteration of loop.
 722
 723    When INIT/LIM are set, they are used instead of var/lim of DESC.  */
 724 rtx
 725 count_loop_iterations (struct loop_desc *desc, rtx init, rtx lim)
 726 {
 727   enum rtx_code cond = desc->cond;
 728   rtx stride = desc->stride;
 729   rtx mod, exp, ainit, bound;
 730   rtx overflow_check, mx, mxp;
 731   enum machine_mode mode = GET_MODE (desc->var);
 732   unsigned HOST_WIDEST_INT s, size, d;
 733
 734   /* Give up on floating point modes and friends.  It can be possible to do
 735      the job for constant loop bounds, but it is probably not worthwhile.  */
 736   if (!INTEGRAL_MODE_P (mode))
 737     return NULL;
 738
 739   init = copy_rtx (init ? init : desc->var);
 740   lim = copy_rtx (lim ? lim : desc->lim);
 741
 742   /* Ensure that we always handle the condition to stay inside loop.  */
 743   if (desc->neg)
 744     cond = reverse_condition (cond);
 745
 746   if (desc->inner_mode != mode)
 747     {
 748       /* We have a case when the variable in fact iterates in the narrower
 749          mode.  This has following consequences:
 750
 751          For induction variable itself, if !desc->postincr, it does not mean
 752          anything too special, since we know the variable is already in range
 753          of the inner mode when we compare it (so it is just needed to shorten
 754          it into the mode before calculations are done, so that we don't risk
 755          wrong results).  More complicated case is when desc->postincr; then
 756          the first two iterations are special (the first one because the value
 757          may be out of range, the second one because after shortening it to the
 758          range it may have absolutely any value), and we do not handle this in
 759          unrolling.  So if we aren't able to prove that the initial value is in
 760          the range, we fail in this case.
 761
 762          Step is just moduled to fit into inner mode.
 763
 764          If lim is out of range, then either the loop is infinite (and then
 765          we may unroll however we like to), or exits in the first iteration
 766          (this is also ok, since we handle it specially for this case anyway).
 767          So we may safely assume that it fits into the inner mode.  */
 768
 769       for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
 770         if (fits_in_mode_p (desc->inner_mode, XEXP (ainit, 0)))
 771           break;
 772
 773       if (!ainit)
 774         {
 775           if (desc->postincr)
 776             return NULL_RTX;
 777
 778           init = simplify_gen_unary (desc->extend,
 779                                      mode,
 780                                      simplify_gen_subreg (desc->inner_mode,
 781                                                           init,
 782                                                           mode,
 783                                                           0),
 784                                      desc->inner_mode);
 785         }
 786
 787       stride = simplify_gen_subreg (desc->inner_mode, stride, mode, 0);
 788       if (stride == const0_rtx)
 789         return NULL_RTX;
 790     }
 791
 792   /* Prepare condition to verify that we do not risk overflow.  */
 793   if (stride == const1_rtx
 794       || stride == constm1_rtx
 795       || cond == NE
 796       || cond == EQ)
 797     {
 798       /* Overflow at NE conditions does not occur.  EQ condition
 799          is weird and is handled in count_strange_loop_iterations.
 800          If stride is 1, overflow may occur only for <= and >= conditions,
 801          and then they are infinite, so it does not bother us.  */
 802       overflow_check = const0_rtx;
 803     }
 804   else
 805     {
 806       if (cond == LT || cond == LTU)
 807         mx = simplify_gen_binary (MINUS, mode, lim, const1_rtx);
 808       else if (cond == GT || cond == GTU)
 809         mx = simplify_gen_binary (PLUS, mode, lim, const1_rtx);
 810       else
 811         mx = lim;
 812       if (mode != desc->inner_mode)
 813         mxp = simplify_gen_subreg (desc->inner_mode, mx, mode, 0);
 814       else
 815         mxp = mx;
 816       mxp = simplify_gen_binary (PLUS, desc->inner_mode, mxp, stride);
 817       if (mode != desc->inner_mode)
 818         mxp = simplify_gen_unary (desc->extend, mode, mxp, desc->inner_mode);
 819       overflow_check = simplify_gen_relational (cond, SImode, mode, mx, mxp);
 820     }
 821
 822   /* Compute absolute value of the difference of initial and final value.  */
 823   if (INTVAL (stride) > 0)
 824     {
 825       /* Handle strange tests specially.  */
 826       if (cond == EQ || cond == GE || cond == GT || cond == GEU
 827           || cond == GTU)
 828         return count_strange_loop_iterations (init, lim, cond, desc->postincr,
 829                                               stride, mode, desc->inner_mode);
 830       exp = simplify_gen_binary (MINUS, mode, lim, init);
 831     }
 832   else
 833     {
 834       if (cond == EQ || cond == LE || cond == LT || cond == LEU
 835           || cond == LTU)
 836         return count_strange_loop_iterations (init, lim, cond, desc->postincr,
 837                                               stride, mode, desc->inner_mode);
 838       exp = simplify_gen_binary (MINUS, mode, init, lim);
 839       stride = simplify_gen_unary (NEG, mode, stride, mode);
 840     }
 841
 842   /* If there is a risk of overflow (i.e. when we increment value satisfying
 843      a condition, we may again obtain a value satisfying the condition),
 844      fail.  */
 845   if (overflow_check != const0_rtx)
 846     return NULL_RTX;
 847
 848   /* Normalize difference so the value is always first examined
 849      and later incremented.  Do not do this for a loop ending with a branch
 850      and count register.  */
 851   if (!is_bct_cond (BB_END (desc->out_edge->src)) && (!desc->postincr))
 852      exp = simplify_gen_binary (MINUS, mode, exp, stride);
 853
 854   /* Determine delta caused by exit condition.  */
 855   switch (cond)
 856     {
 857     case NE:
 858       /* NE tests are easy to handle, because we just perform simple
 859          arithmetics modulo power of 2.  Let's use the fact to compute the
 860          number of iterations exactly.  We are now in situation when we want to
 861          solve an equation stride * i = c (mod size of inner_mode).
 862          Let nsd (stride, size of mode) = d.  If d does not divide c, the
 863          loop is infinite.  Otherwise, the number of iterations is
 864          (inverse(s/d) * (c/d)) mod (size of mode/d).  */
 865       size = GET_MODE_BITSIZE (desc->inner_mode);
 866       s = INTVAL (stride);
 867       d = 1;
 868       while (s % 2 != 1)
 869         {
 870           s /= 2;
 871           d *= 2;
 872           size--;
 873         }
 874       bound = gen_int_mode (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1,
 875                             mode);
 876       exp = simplify_gen_binary (UDIV, mode, exp, gen_int_mode (d, mode));
 877       exp = simplify_gen_binary (MULT, mode,
 878                                  exp, gen_int_mode (inverse (s, size), mode));
 879       exp = simplify_gen_binary (AND, mode, exp, bound);
 880       break;
 881
 882     case LT:
 883     case GT:
 884     case LTU:
 885     case GTU:
 886       break;
 887     case LE:
 888     case GE:
 889     case LEU:
 890     case GEU:
 891       exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
 892       break;
 893     default:
 894       abort ();
 895     }
 896
 897   if (cond != NE && stride != const1_rtx)
 898     {
 899       /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
 900          but we need to take care for overflows.  */
 901
 902       mod = simplify_gen_binary (UMOD, mode, exp, stride);
 903
 904       /* This is dirty trick.  When we can't compute number of iterations
 905          to be constant, we simply ignore the possible overflow, as
 906          runtime unroller always use power of 2 amounts and does not
 907          care about possible lost bits.  */
 908
 909       if (GET_CODE (mod) != CONST_INT)
 910         {
 911           rtx stridem1 = simplify_gen_binary (PLUS, mode, stride, constm1_rtx);
 912           exp = simplify_gen_binary (PLUS, mode, exp, stridem1);
 913           exp = simplify_gen_binary (UDIV, mode, exp, stride);
 914         }
 915       else
 916         {
 917           exp = simplify_gen_binary (UDIV, mode, exp, stride);
 918           if (mod != const0_rtx)
 919             exp = simplify_gen_binary (PLUS, mode, exp, const1_rtx);
 920         }
 921     }
 922
 923   if (rtl_dump_file)
 924     {
 925       fprintf (rtl_dump_file, ";  Number of iterations: ");
 926       print_simple_rtl (rtl_dump_file, exp);
 927       fprintf (rtl_dump_file, "\n");
 928     }
 929
 930   return exp;
 931 }
 932
 933 /* Return simplified RTX expression representing the value of test
 934    described of DESC at given iteration of loop.  */
 935
 936 static rtx
 937 test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT iter)
 938 {
 939   enum rtx_code cond = desc->cond;
 940   rtx exp = XEXP (desc->var_alts, 0);
 941   rtx addval;
 942
 943   /* Give up on floating point modes and friends.  It can be possible to do
 944      the job for constant loop bounds, but it is probably not worthwhile.  */
 945   if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
 946     return NULL;
 947
 948   /* Ensure that we always handle the condition to stay inside loop.  */
 949   if (desc->neg)
 950     cond = reverse_condition (cond);
 951
 952   /* Compute the value of induction variable.  */
 953   addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
 954                                 desc->stride,
 955                                 gen_int_mode (desc->postincr
 956                                               ? iter : iter + 1,
 957                                               GET_MODE (desc->var)));
 958   exp = simplify_gen_binary (PLUS, GET_MODE (desc->var), exp, addval);
 959   /* Test at given condition.  */
 960   exp = simplify_gen_relational (cond, SImode,
 961                                  GET_MODE (desc->var), exp, desc->lim);
 962
 963   if (rtl_dump_file)
 964     {
 965       fprintf (rtl_dump_file, ";  Conditional to continue loop at "
 966                HOST_WIDE_INT_PRINT_UNSIGNED "th iteration: ", iter);
 967       print_simple_rtl (rtl_dump_file, exp);
 968       fprintf (rtl_dump_file, "\n");
 969     }
 970   return exp;
 971 }
 972
 973
 974 /* Tests whether exit at EXIT_EDGE from LOOP is simple.  Returns simple loop
 975    description joined to it in in DESC.  INVARIANT_REGS and SINGLE_SET_REGS
 976    are results of blocks_{invariant,single_set}_regs over BODY.  */
 977 static bool
 978 simple_loop_exit_p (struct loop *loop, edge exit_edge,
 979                     regset invariant_regs, rtx *single_set_regs,
 980                     struct loop_desc *desc)
 981 {
 982   basic_block mod_bb, exit_bb;
 983   int fallthru_out;
 984   rtx condition;
 985   edge ei, e;
 986
 987   exit_bb = exit_edge->src;
 988
 989   fallthru_out = (exit_edge->flags & EDGE_FALLTHRU);
 990
 991   if (!exit_bb)
 992     return false;
 993
 994   /* It must be tested (at least) once during any iteration.  */
 995   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
 996     return false;
 997
 998   /* It must end in a simple conditional jump.  */
 999   if (!any_condjump_p (BB_END (exit_bb)))
1000     return false;
1001
1002   ei = exit_bb->succ;
1003   if (ei == exit_edge)
1004     ei = ei->succ_next;
1005
1006   desc->out_edge = exit_edge;
1007   desc->in_edge = ei;
1008
1009   /* Condition must be a simple comparison in that one of operands
1010      is register and the other one is invariant.  */
1011   if (!(condition = get_condition (BB_END (exit_bb), NULL, false)))
1012     return false;
1013
1014   if (!simple_condition_p (loop, condition, invariant_regs, desc))
1015     return false;
1016
1017   /*  Var must be simply incremented or decremented in exactly one insn that
1018      is executed just once every iteration.  */
1019   if (!(mod_bb = simple_increment (loop, single_set_regs, desc)))
1020     return false;
1021
1022   /* OK, it is simple loop.  Now just fill in remaining info.  */
1023   desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
1024   desc->neg = !fallthru_out;
1025
1026   /* Find initial value of var and alternative values for lim.  */
1027   e = loop_preheader_edge (loop);
1028   desc->var_alts = variable_initial_values (e, desc->var, desc->inner_mode);
1029   desc->lim_alts = variable_initial_values (e, desc->lim, desc->inner_mode);
1030
1031   /* Number of iterations.  */
1032   desc->const_iter =
1033     constant_iterations (desc, &desc->niter, &desc->may_be_zero);
1034   if (!desc->const_iter && !count_loop_iterations (desc, NULL, NULL))
1035     return false;
1036   return true;
1037 }
1038
1039 /* Tests whether LOOP is simple for loop.  Returns simple loop description
1040    in DESC.  */
1041 bool
1042 simple_loop_p (struct loop *loop, struct loop_desc *desc)
1043 {
1044   unsigned i;
1045   basic_block *body;
1046   edge e;
1047   struct loop_desc act;
1048   bool any = false;
1049   regset invariant_regs;
1050   regset_head invariant_regs_head;
1051   rtx *single_set_regs;
1052   int n_branches;
1053
1054   body = get_loop_body (loop);
1055
1056   invariant_regs = INITIALIZE_REG_SET (invariant_regs_head);
1057   single_set_regs = xmalloc (max_reg_num () * sizeof (rtx));
1058
1059   blocks_invariant_registers (body, loop->num_nodes, invariant_regs);
1060   blocks_single_set_registers (body, loop->num_nodes, single_set_regs);
1061
1062   n_branches = 0;
1063   for (i = 0; i < loop->num_nodes; i++)
1064     {
1065       for (e = body[i]->succ; e; e = e->succ_next)
1066         if (!flow_bb_inside_loop_p (loop, e->dest)
1067             && simple_loop_exit_p (loop, e,
1068                    invariant_regs, single_set_regs, &act))
1069           {
1070             /* Prefer constant iterations; the less the better.  */
1071             if (!any)
1072               any = true;
1073             else if (!act.const_iter
1074                      || (desc->const_iter && act.niter >= desc->niter))
1075               continue;
1076             *desc = act;
1077           }
1078
1079       if (body[i]->succ && body[i]->succ->succ_next)
1080         n_branches++;
1081     }
1082   desc->n_branches = n_branches;
1083
1084   if (rtl_dump_file && any)
1085     {
1086       fprintf (rtl_dump_file, "; Simple loop %i\n", loop->num);
1087       if (desc->postincr)
1088         fprintf (rtl_dump_file,
1089                  ";  does postincrement after loop exit condition\n");
1090
1091       fprintf (rtl_dump_file, ";  Induction variable:");
1092       print_simple_rtl (rtl_dump_file, desc->var);
1093       fputc ('\n', rtl_dump_file);
1094
1095       fprintf (rtl_dump_file, ";  Initial values:");
1096       print_simple_rtl (rtl_dump_file, desc->var_alts);
1097       fputc ('\n', rtl_dump_file);
1098
1099       fprintf (rtl_dump_file, ";  Stride:");
1100       print_simple_rtl (rtl_dump_file, desc->stride);
1101       fputc ('\n', rtl_dump_file);
1102
1103       fprintf (rtl_dump_file, ";  Compared with:");
1104       print_simple_rtl (rtl_dump_file, desc->lim);
1105       fputc ('\n', rtl_dump_file);
1106
1107       fprintf (rtl_dump_file, ";  Alternative values:");
1108       print_simple_rtl (rtl_dump_file, desc->lim_alts);
1109       fputc ('\n', rtl_dump_file);
1110
1111       fprintf (rtl_dump_file, ";  Exit condition:");
1112       if (desc->neg)
1113         fprintf (rtl_dump_file, "(negated)");
1114       fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
1115
1116       fprintf (rtl_dump_file, ";  Number of branches:");
1117       fprintf (rtl_dump_file, "%d\n", desc->n_branches);
1118
1119       fputc ('\n', rtl_dump_file);
1120     }
1121
1122   free (body);
1123   FREE_REG_SET (invariant_regs);
1124   free (single_set_regs);
1125   return any;
1126 }
1127
1128 /* Marks blocks and edges that are part of non-recognized loops; i.e. we
1129    throw away all latch edges and mark blocks inside any remaining cycle.
1130    Everything is a bit complicated due to fact we do not want to do this
1131    for parts of cycles that only "pass" through some loop -- i.e. for
1132    each cycle, we want to mark blocks that belong directly to innermost
1133    loop containing the whole cycle.  */
1134 void
1135 mark_irreducible_loops (struct loops *loops)
1136 {
1137   int *dfs_in, *closed, *mr, *mri, *n_edges, *stack;
1138   unsigned i;
1139   edge **edges, e;
1140   edge *estack;
1141   basic_block act;
1142   int stack_top, tick, depth;
1143   struct loop *cloop;
1144
1145   /* Reset the flags.  */
1146   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1147     {
1148       act->flags &= ~BB_IRREDUCIBLE_LOOP;
1149       for (e = act->succ; e; e = e->succ_next)
1150         e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1151     }
1152
1153   /* The first last_basic_block + 1 entries are for real blocks (including
1154      entry); then we have loops->num - 1 fake blocks for loops to that we
1155      assign edges leading from loops (fake loop 0 is not interesting).  */
1156   dfs_in = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1157   closed = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1158   mr = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1159   mri = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1160   n_edges = xmalloc ((last_basic_block + loops->num) * sizeof (int));
1161   edges = xmalloc ((last_basic_block + loops->num) * sizeof (edge *));
1162   stack = xmalloc ((n_basic_blocks + loops->num) * sizeof (int));
1163   estack = xmalloc ((n_basic_blocks + loops->num) * sizeof (edge));
1164
1165   /* Create the edge lists.  */
1166   for (i = 0; i < last_basic_block + loops->num; i++)
1167     n_edges[i] = 0;
1168   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1169     for (e = act->succ; e; e = e->succ_next)
1170       {
1171         /* Ignore edges to exit.  */
1172         if (e->dest == EXIT_BLOCK_PTR)
1173           continue;
1174         /* And latch edges.  */
1175         if (e->dest->loop_father->header == e->dest
1176             && e->dest->loop_father->latch == act)
1177           continue;
1178         /* Edges inside a single loop should be left where they are.  Edges
1179            to subloop headers should lead to representative of the subloop,
1180            but from the same place.  */
1181         if (act->loop_father == e->dest->loop_father
1182             || act->loop_father == e->dest->loop_father->outer)
1183           {
1184             n_edges[act->index + 1]++;
1185             continue;
1186           }
1187         /* Edges exiting loops remain.  They should lead from representative
1188            of the son of nearest common ancestor of the loops in that
1189            act lays.  */
1190         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
1191         if (depth == act->loop_father->depth)
1192           cloop = act->loop_father;
1193         else
1194           cloop = act->loop_father->pred[depth];
1195         n_edges[cloop->num + last_basic_block]++;
1196       }
1197
1198   for (i = 0; i < last_basic_block + loops->num; i++)
1199     {
1200       edges[i] = xmalloc (n_edges[i] * sizeof (edge));
1201       n_edges[i] = 0;
1202     }
1203
1204   FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1205     for (e = act->succ; e; e = e->succ_next)
1206       {
1207         if (e->dest == EXIT_BLOCK_PTR)
1208           continue;
1209         if (e->dest->loop_father->header == e->dest
1210             && e->dest->loop_father->latch == act)
1211           continue;
1212         if (act->loop_father == e->dest->loop_father
1213             || act->loop_father == e->dest->loop_father->outer)
1214           {
1215             edges[act->index + 1][n_edges[act->index + 1]++] = e;
1216             continue;
1217           }
1218         depth = find_common_loop (act->loop_father, e->dest->loop_father)->depth + 1;
1219         if (depth == act->loop_father->depth)
1220           cloop = act->loop_father;
1221         else
1222           cloop = act->loop_father->pred[depth];
1223         i = cloop->num + last_basic_block;
1224         edges[i][n_edges[i]++] = e;
1225       }
1226
1227   /* Compute dfs numbering, starting from loop headers, and mark found
1228      loops.  */
1229   tick = 0;
1230   for (i = 0; i < last_basic_block + loops->num; i++)
1231     {
1232       dfs_in[i] = -1;
1233       closed[i] = 0;
1234       mr[i] = last_basic_block + loops->num;
1235       mri[i] = -1;
1236     }
1237
1238   stack_top = 0;
1239   for (i = 0; i < loops->num; i++)
1240     if (loops->parray[i])
1241       {
1242         stack[stack_top] = loops->parray[i]->header->index + 1;
1243         estack[stack_top] = NULL;
1244         stack_top++;
1245       }
1246
1247   while (stack_top)
1248     {
1249       int idx, sidx;
1250
1251       idx = stack[stack_top - 1];
1252       if (dfs_in[idx] < 0)
1253         dfs_in[idx] = tick++;
1254
1255       while (n_edges[idx])
1256         {
1257           e = edges[idx][--n_edges[idx]];
1258           sidx = e->dest->loop_father->header == e->dest
1259                    ? e->dest->loop_father->num + last_basic_block
1260                    : e->dest->index + 1;
1261           if (closed[sidx])
1262             {
1263               if (mri[sidx] != -1 && !closed[mri[sidx]])
1264                 {
1265                   if (mr[sidx] < mr[idx])
1266                     {
1267                       mr[idx] = mr[sidx];
1268                       mri[idx] = mri[sidx];
1269                     }
1270
1271                   if (mr[sidx] <= dfs_in[idx])
1272                     e->flags |= EDGE_IRREDUCIBLE_LOOP;
1273                 }
1274               continue;
1275             }
1276           if (dfs_in[sidx] < 0)
1277             {
1278               stack[stack_top] = sidx;
1279               estack[stack_top] = e;
1280               stack_top++;
1281               goto next;
1282             }
1283           if (dfs_in[sidx] < mr[idx])
1284             {
1285               mr[idx] = dfs_in[sidx];
1286               mri[idx] = sidx;
1287             }
1288           e->flags |= EDGE_IRREDUCIBLE_LOOP;
1289         }
1290
1291       /* Return back.  */
1292       closed[idx] = 1;
1293       e = estack[stack_top - 1];
1294       stack_top--;
1295       if (e)
1296         {
1297           /* Propagate information back.  */
1298           sidx = stack[stack_top - 1];
1299           if (mr[sidx] > mr[idx])
1300             {
1301               mr[sidx] = mr[idx];
1302               mri[sidx] = mri[idx];
1303             }
1304           if (mr[idx] <= dfs_in[sidx])
1305             e->flags |= EDGE_IRREDUCIBLE_LOOP;
1306         }
1307       /* Mark the block if relevant.  */
1308       if (idx && idx <= last_basic_block && mr[idx] <= dfs_in[idx])
1309         BASIC_BLOCK (idx - 1)->flags |= BB_IRREDUCIBLE_LOOP;
1310 next:;
1311     }
1312
1313   free (stack);
1314   free (estack);
1315   free (dfs_in);
1316   free (closed);
1317   free (mr);
1318   free (mri);
1319   for (i = 0; i < last_basic_block + loops->num; i++)
1320     free (edges[i]);
1321   free (edges);
1322   free (n_edges);
1323   loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
1324 }
1325
1326 /* Counts number of insns inside LOOP.  */
1327 int
1328 num_loop_insns (struct loop *loop)
1329 {
1330   basic_block *bbs, bb;
1331   unsigned i, ninsns = 0;
1332   rtx insn;
1333
1334   bbs = get_loop_body (loop);
1335   for (i = 0; i < loop->num_nodes; i++)
1336     {
1337       bb = bbs[i];
1338       ninsns++;
1339       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
1340         if (INSN_P (insn))
1341           ninsns++;
1342     }
1343   free(bbs);
1344
1345   return ninsns;
1346 }
1347
1348 /* Counts number of insns executed on average per iteration LOOP.  */
1349 int
1350 average_num_loop_insns (struct loop *loop)
1351 {
1352   basic_block *bbs, bb;
1353   unsigned i, binsns, ninsns, ratio;
1354   rtx insn;
1355
1356   ninsns = 0;
1357   bbs = get_loop_body (loop);
1358   for (i = 0; i < loop->num_nodes; i++)
1359     {
1360       bb = bbs[i];
1361
1362       binsns = 1;
1363       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
1364         if (INSN_P (insn))
1365           binsns++;
1366
1367       ratio = loop->header->frequency == 0
1368               ? BB_FREQ_MAX
1369               : (bb->frequency * BB_FREQ_MAX) / loop->header->frequency;
1370       ninsns += binsns * ratio;
1371     }
1372   free(bbs);
1373
1374   ninsns /= BB_FREQ_MAX;
1375   if (!ninsns)
1376     ninsns = 1; /* To avoid division by zero.  */
1377
1378   return ninsns;
1379 }
1380
1381 /* Returns expected number of LOOP iterations.
1382    Compute upper bound on number of iterations in case they do not fit integer
1383    to help loop peeling heuristics.  Use exact counts if at all possible.  */
1384 unsigned
1385 expected_loop_iterations (const struct loop *loop)
1386 {
1387   edge e;
1388
1389   if (loop->header->count)
1390     {
1391       gcov_type count_in, count_latch, expected;
1392
1393       count_in = 0;
1394       count_latch = 0;
1395
1396       for (e = loop->header->pred; e; e = e->pred_next)
1397         if (e->src == loop->latch)
1398           count_latch = e->count;
1399         else
1400           count_in += e->count;
1401
1402       if (count_in == 0)
1403         return 0;
1404
1405       expected = (count_latch + count_in - 1) / count_in;
1406
1407       /* Avoid overflows.  */
1408       return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected);
1409     }
1410   else
1411     {
1412       int freq_in, freq_latch;
1413
1414       freq_in = 0;
1415       freq_latch = 0;
1416
1417       for (e = loop->header->pred; e; e = e->pred_next)
1418         if (e->src == loop->latch)
1419           freq_latch = EDGE_FREQUENCY (e);
1420         else
1421           freq_in += EDGE_FREQUENCY (e);
1422
1423       if (freq_in == 0)
1424         return 0;
1425
1426       return (freq_latch + freq_in - 1) / freq_in;
1427     }
1428 }
1429
1430 /* This function checks if an instruction is a branch and count instruction
1431    no matter if the flag HAVE_doloop_end is enabled or not.  An alternative
1432    would be the modification of doloop_condition_get function itself.  */
1433 bool
1434 is_bct_cond (rtx insn)
1435 {
1436   if (GET_CODE (insn) != JUMP_INSN)
1437     return false;
1438
1439 #ifdef HAVE_doloop_end
1440   if (!doloop_condition_get (PATTERN(insn)))
1441     return false;
1442 #else
1443   return false;
1444 #endif
1445
1446   return true;
1447 }
1448
1449 /* Extract the increment of the count register from the branch and count
1450    instruction.  */
1451 rtx
1452 get_var_set_from_bct (rtx insn)
1453 {
1454   rtx rhs, lhs, cond;
1455   rtx pattern;
1456   rtx set;
1457   pattern = PATTERN (insn);
1458
1459   if (!is_bct_cond (insn))
1460     abort ();
1461
1462   set = XVECEXP (pattern, 0, 1);
1463
1464   /* IA64 has the decrement conditional, i.e. done only when the loop does not
1465      end.  We match (set (x (if_then_else (ne x 0) (plus x -1) x))) here.  */
1466
1467   lhs = XEXP (set, 0);
1468   rhs = XEXP (set, 1);
1469   if (GET_CODE (set) != IF_THEN_ELSE)
1470     return set;
1471
1472   cond = XEXP (rhs, 0);
1473   if (GET_CODE (cond) != NE
1474       || !rtx_equal_p (XEXP (cond, 0), lhs)
1475       || !rtx_equal_p (XEXP (cond, 1), const0_rtx))
1476          return set;
1477
1478   rhs = XEXP (rhs, 1);
1479
1480   return gen_rtx_SET (GET_MODE (lhs), lhs, rhs);
1481 }
1482