gcc/cfgloopanal.c

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